{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "cde771ec-e96e-49c8-bf3f-017bde583b16",
   "metadata": {},
   "outputs": [],
   "source": [
    "from main import *\n",
    "from math import *\n",
    "def mod_ast(x: int, mod: int) -> list[int]:\n",
    "    if (type(x) == int):\n",
    "        return x % mod\n",
    "    return x\n",
    "def f(mod: int):\n",
    "    return lambda x: mod_ast(x, mod)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "df2bf1a7-1304-4011-97b2-c1dc638e77bf",
   "metadata": {},
   "outputs": [],
   "source": [
    "lsts = diff_square(11, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "368cf981-e6f8-471e-b384-a4d3bc92f35d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[-2, -1, 5, -6, 7, -4, 2, 3, '*', '*', 'k = 1'],\n",
       " [-3, 4, -1, 1, 3, -2, 5, '*', -4, '*', 'k = 2'],\n",
       " [2, -2, 6, -3, 5, 1, '*', -1, -6, '*', 'k = 3'],\n",
       " [-4, 5, 2, -1, 8, '*', 1, -3, -7, '*', 'k = 4'],\n",
       " [3, 1, 4, 2, '*', -3, -1, -4, -2, '*', 'k = 5'],\n",
       " [-1, 3, 7, '*', 4, -5, -2, 1, -8, '*', 'k = 6'],\n",
       " [1, 6, '*', -2, 2, -6, 3, -5, -1, '*', 'k = 7'],\n",
       " [4, '*', 3, -4, 1, -1, -3, 2, -5, '*', 'k = 8'],\n",
       " ['*', 2, 1, -5, 6, -7, 4, -2, -3, '*', 'k = 9']]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lsts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "84e69ed4-8684-4291-984c-22678745c809",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[8, 9, 5, 4, 7, 6, 2, 3, '*', '*', 'k = 1'] 8 8\n",
      "[7, 4, 9, 1, 3, 8, 5, '*', 6, '*', 'k = 2'] 8 8\n",
      "[2, 8, 6, 7, 5, 1, '*', 9, 4, '*', 'k = 3'] 8 8\n",
      "[6, 5, 2, 9, 8, '*', 1, 7, 3, '*', 'k = 4'] 8 8\n",
      "[3, 1, 4, 2, '*', 7, 9, 6, 8, '*', 'k = 5'] 8 8\n",
      "[9, 3, 7, '*', 4, 5, 8, 1, 2, '*', 'k = 6'] 8 8\n",
      "[1, 6, '*', 8, 2, 4, 3, 5, 9, '*', 'k = 7'] 8 8\n",
      "[4, '*', 3, 6, 1, 9, 7, 2, 5, '*', 'k = 8'] 8 8\n",
      "['*', 2, 1, 5, 6, 3, 4, 8, 7, '*', 'k = 9'] 8 8\n"
     ]
    }
   ],
   "source": [
    "for lst in [list(map(f(10), lst)) for lst in lsts]:\n",
    "    print(lst, len(set(ints(lst))), len(ints(lst)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "id": "82b0e21a-41bc-4b62-b180-b6769adaa983",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 6, 7, 8]"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "primitive_roots(11)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "9f7848c4-e2de-4494-b0bb-cd5a4c5631c1",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10 10\n",
      "10 10\n",
      "10 10\n",
      "10 10\n",
      "10 10\n",
      "10 10\n"
     ]
    }
   ],
   "source": [
    "for lst in lsts:\n",
    "    print(len(set(ints(lst))), len(ints(lst)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "93051848-7dff-4bc6-b81f-7a5ec1a36f30",
   "metadata": {},
   "outputs": [],
   "source": [
    "lhs = test[:len(test) // 2]\n",
    "rhs = test[ceil(len(test) / 2):]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "618ba557-f427-4544-b2b8-856819f55086",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10 7 3\n",
      "11 8 3\n",
      "5 2 3\n",
      "6 3 3\n"
     ]
    }
   ],
   "source": [
    "for l, r in zip(lhs, rhs):\n",
    "    print(l, r, int(l - r) % 12)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "id": "e0c5029e-500f-4d19-9e81-ed76474266bd",
   "metadata": {},
   "outputs": [],
   "source": [
    "lsts = diff_square(11, 2)\n",
    "lsts = [list(map(lambda x: x % 12, ints(lst))) for lst in lsts]\n",
    "\n",
    "first = lsts[0]\n",
    "lsts = [lst[:-idx] for idx, lst in enumerate(lsts)]\n",
    "lsts[0] = first\n",
    "\n",
    "for lst in lsts:\n",
    "    lhs = lst[:len(lst) // 2]\n",
    "    rhs = lst[ceil(len(lst) / 2):]\n",
    "    diff = (lhs[0] - rhs[0]) % 12\n",
    "    assert(all(map(lambda x: (x[0] - x[1]) % 12 == diff, zip(lhs, rhs))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "e9ca3cfd-c6d7-4001-94d3-67934c1dcdfe",
   "metadata": {},
   "outputs": [],
   "source": [
    "primes = load_file(\"primes.h\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "id": "9dfde2de-3379-41cb-bd83-39bdab613df4",
   "metadata": {},
   "outputs": [],
   "source": [
    "for idx, prime in enumerate(primes):\n",
    "    if idx == 50:\n",
    "        break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "09fb6792-1f48-4885-808c-38d3f206959b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def predicate(prime: int, alpha: int) -> bool:\n",
    "    diffs = diff_square(prime, alpha)\n",
    "    diffs = [list(map(lambda x: x % (prime + 1), ints(lst))) for lst in diffs]\n",
    "    diffs = [diffs[0]] + [lst[:-idx] for idx, lst in enumerate(diffs[1:], 1)]\n",
    "\n",
    "    def inner_pred(prime: int, lst: [int]) -> bool:\n",
    "        lhs = lst[:len(lst) // 2]\n",
    "        rhs = lst[ceil(len(lst) / 2):]\n",
    "        diff = (lhs[0] - rhs[0]) % (prime + 1)\n",
    "        return all(map(lambda x: (x[0] - x[1]) % (prime + 1) == diff, zip(lhs, rhs)))\n",
    "\n",
    "    return all(map(lambda lst: inner_pred(prime, lst), diffs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "0844f3f2-ff4f-44b9-b771-aaf0c1536842",
   "metadata": {},
   "outputs": [
    {
     "ename": "SyntaxError",
     "evalue": "incomplete input (3622495773.py, line 6)",
     "output_type": "error",
     "traceback": [
      "\u001b[0;36m  Cell \u001b[0;32mIn[18], line 6\u001b[0;36m\u001b[0m\n\u001b[0;31m    \u001b[0m\n\u001b[0m    ^\u001b[0m\n\u001b[0;31mSyntaxError\u001b[0m\u001b[0;31m:\u001b[0m incomplete input\n"
     ]
    }
   ],
   "source": [
    "for idx, prime in enumerate(sorted(list(primes))[4:]):\n",
    "    if idx == 10:\n",
    "        break\n",
    "    for root in primitive_roots(prime):\n",
    "        # print(prime, root, predicate(prime, root))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 115,
   "id": "50831976-1716-4836-95d9-57474c344671",
   "metadata": {},
   "outputs": [],
   "source": [
    "diffs = diff_square(11, 7)\n",
    "diffs = [list(map(lambda x: x % 12, ints(lst))) for lst in diffs]\n",
    "diffs = [diffs[0]] + [lst[:-idx] for idx, lst in enumerate(diffs[1:], 1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "id": "695b1a4c-f02e-46b3-9061-e52ccbb7fff7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[11, 4, 3, 7, 6, 10, 9, 2],\n",
       " [3, 7, 10, 1, 4, 7, 11],\n",
       " [6, 2, 4, 11, 1, 9],\n",
       " [1, 8, 2, 8, 3],\n",
       " [7, 6, 11, 10]]"
      ]
     },
     "execution_count": 116,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "diffs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 114,
   "id": "abf7a34b-238d-484c-8578-dbe97867db9d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[-1, 4, 3, -5, 6, -2, -3, 2, '*', '*'],\n",
       " [3, 7, -2, 1, 4, -5, -1, '*', -4, '*'],\n",
       " [6, 2, 4, -1, 1, -3, '*', -2, -5, '*'],\n",
       " [1, 8, 2, -4, 3, '*', -5, -3, -1, '*'],\n",
       " [7, 6, -1, -2, '*', -7, -6, 1, 2, '*']]"
      ]
     },
     "execution_count": 114,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "diff_square(11, 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "82ea7838-94cd-49f0-ae19-b889c4d7ca85",
   "metadata": {},
   "outputs": [],
   "source": [
    "# fn is_costas(Vec<UInt> const& vec) -> Bool {\n",
    "#     using Set = std::unordered_set<UInt>;\n",
    "\n",
    "#     if (Set(vec.cbegin(), vec.cend()).size() != vec.size())\n",
    "#         return false;\n",
    "\n",
    "#     bool flag = false;\n",
    "#     auto const l = vec.size();\n",
    "# #pragma omp parallel for num_threads(16) shared(flag)\n",
    "#     for (Size h = 1; h < l; ++h) {\n",
    "#         if (flag)\n",
    "#             continue;\n",
    "#         var set = Set((l - 2) - (h - 1));\n",
    "#         for (Size i = h - 1; i <= l - 2; --i)\n",
    "#             set.insert(vec[(h + i) % l] - vec[i]);\n",
    "\n",
    "#         if (set.size() != (l - 2) - (h - 1)) {\n",
    "# #pragma omp atomic write\n",
    "#             flag = true;\n",
    "#         }\n",
    "#     }\n",
    "#     return !flag;\n",
    "# }\n",
    "\n",
    "def uniq(vec: list) -> bool:\n",
    "    for idx, x in enumerate(vec):\n",
    "        for idy, y in enumerate(vec):\n",
    "            if idx == idy:\n",
    "                continue\n",
    "            if x == y:\n",
    "                return False\n",
    "    return True\n",
    "\n",
    "def is_costas(vec: list[int]) -> bool:\n",
    "    n = len(vec)\n",
    "\n",
    "    if not uniq(vec):\n",
    "        return False\n",
    "\n",
    "    flag = False\n",
    "    for i in range(n): # parallel\n",
    "        if flag:\n",
    "            continue\n",
    "            \n",
    "        s = set()\n",
    "        for k in range(1, n):\n",
    "            result = vec[(i + k) % n] - vec[i]\n",
    "            if result in s:\n",
    "                print(\"here\")\n",
    "                return False\n",
    "            else:\n",
    "                s.add(result)\n",
    "\n",
    "        if len(s) != n - 1:\n",
    "            return False\n",
    "\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "f72ae2f3-bc33-44d0-9880-11b45034066f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "True\n",
      "True\n",
      "True\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "print(is_costas([1, 2, 4, 3]))\n",
    "print(is_costas([1, 2, 3, 4]))\n",
    "print(is_costas([1, 2]))\n",
    "print(is_costas([2, 1]))\n",
    "print(is_costas([2, 1, 4, 3]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "c1167d60-c9de-41a7-9525-197ebd0f898a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "uniq(list(range(100)) + [1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c3ececd8-87ea-40aa-bf40-896a5ced353f",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}