{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "480599a9-9f15-4d40-ba36-cddfac8cd436",
   "metadata": {},
   "outputs": [],
   "source": [
    "def SumDQ(A, p, r):\n",
    "    if (p == r):\n",
    "        return A[p - 1]\n",
    "    q = (p + r) // 2\n",
    "    s_l = SumDQ(A, p, q)\n",
    "    s_r = SumDQ(A, q + 1, r)\n",
    "    return s_l + s_r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "fffc8fce-95ac-4741-bbd2-0f428eea8c14",
   "metadata": {},
   "outputs": [],
   "source": [
    "def permutations(iterable, r=None):\n",
    "    # permutations('ABCD', 2) → AB AC AD BA BC BD CA CB CD DA DB DC\n",
    "    # permutations(range(3)) → 012 021 102 120 201 210\n",
    "\n",
    "    pool = tuple(iterable)\n",
    "    n = len(pool)\n",
    "    r = n if r is None else r\n",
    "    if r > n:\n",
    "        return\n",
    "\n",
    "    indices = list(range(n))\n",
    "    cycles = list(range(n, n-r, -1))\n",
    "    yield tuple(pool[i] for i in indices[:r])\n",
    "\n",
    "    while n:\n",
    "        for i in reversed(range(r)):\n",
    "            cycles[i] -= 1\n",
    "            if cycles[i] == 0:\n",
    "                indices[i:] = indices[i+1:] + indices[i:i+1]\n",
    "                cycles[i] = n - i\n",
    "            else:\n",
    "                j = cycles[i]\n",
    "                indices[i], indices[-j] = indices[-j], indices[i]\n",
    "                yield tuple(pool[i] for i in indices[:r])\n",
    "                break\n",
    "        else:\n",
    "            return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "e68027af-3256-452d-911c-85d8c3b35bf7",
   "metadata": {},
   "outputs": [],
   "source": [
    "def id(x): return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a0299a59-3de4-4701-9296-e07988f8df61",
   "metadata": {},
   "outputs": [],
   "source": [
    "import collections\n",
    "\n",
    "def is_costas(lst: collections.deque[int]) -> bool:\n",
    "    if len(set(lst)) != len(lst):\n",
    "        return False\n",
    "\n",
    "    l = len(lst)\n",
    "    for h in range(1,l):\n",
    "        diffs = []\n",
    "        for i in range(h - 1, l - 1):\n",
    "            diffs.append(lst[(h + i) % l] - lst[i])\n",
    "        if len(diffs) != len(set(diffs)):\n",
    "            return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "3aaf8ac1-3511-4c20-934c-916245dd8d25",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n"
     ]
    }
   ],
   "source": [
    "print(is_costas([1,2,3]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "89241374-c3d9-4006-a84c-0d8e98f71a82",
   "metadata": {},
   "outputs": [],
   "source": [
    "def costas_nxn(i: int) -> list[tuple[list[int], bool]]:\n",
    "    return list(filter(lambda x: x[1], [(lst, is_costas(lst)) for lst in permutations(range(1, i + 1))]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "374fa23d-62fe-4932-9839-a56c329e1347",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.0\n",
      "2.0\n",
      "4.0\n",
      "16.0\n",
      "41.0\n",
      "104.0\n",
      "93.0\n",
      "159.0\n",
      "342.0\n",
      "655.0\n"
     ]
    }
   ],
   "source": [
    "for i in range(2, 20):\n",
    "    print(len(costas_nxn(i)) / 2.0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "5234cde1-e0d4-4fda-9ee8-199f93cef470",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[True, True]"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(filter(id, [True,False,True]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "id": "5ee066a1-199e-48ca-abc1-db53e1c6080c",
   "metadata": {},
   "outputs": [],
   "source": [
    "import collections\n",
    "\n",
    "def is_costas(lst: list[int]) -> bool:\n",
    "    if len(set(lst)) != len(lst):\n",
    "        return False\n",
    "        \n",
    "    n = len(lst)\n",
    "    for k in range(1, n):\n",
    "        diffs = []\n",
    "        for i in range(0, n - k):\n",
    "            a = lst[(i + k) % n]\n",
    "            b = lst[i]\n",
    "            result = a - b\n",
    "            diffs.append(result)\n",
    "        if len(diffs) != len(set(diffs)):\n",
    "            return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "id": "e3bc84ac-a4d0-43b2-b25b-1bff3e48c4af",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "print(is_costas([1,3,2]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "0d87444b-8c2a-40d7-9269-e31b4b6947d3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_costas(lst: list[int]) -> bool:\n",
    "    if len(set(lst)) != len(lst):\n",
    "        return False\n",
    "        \n",
    "    n = len(lst)\n",
    "    flag = False\n",
    "    for k in range(1, n):\n",
    "        diffs = [False] * (2 * n)\n",
    "        if flag:\n",
    "            continue\n",
    "        for i in range(0, n - k):\n",
    "            a = lst[(i + k) % n]\n",
    "            b = lst[i]\n",
    "            result = a - b + n\n",
    "            if diffs[result]:\n",
    "                return False\n",
    "            else:\n",
    "                diffs[result] = True\n",
    "\n",
    "            flag = diffs[result]\n",
    "    return flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "1da9d034-be34-4810-a3bc-ca2d0ff277be",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n"
     ]
    }
   ],
   "source": [
    "print(is_costas([1, 2, 3,4]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "b6bea522-2054-42bc-a449-0040cbad6d20",
   "metadata": {},
   "outputs": [],
   "source": [
    "def build_all_naive(lst: list[int], x: int) -> list[int]:\n",
    "    out = []\n",
    "    for i in range(len(lst) + 1):\n",
    "        lst2 = list(lst).copy()\n",
    "        lst2.insert(i, x)\n",
    "        if is_costas(lst2):\n",
    "            out.append(lst2)\n",
    "    return out\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "id": "7bbbbf79-0ee1-4e7e-b781-871afd330d63",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2]\n",
      "2 [3, 1, 2]\n",
      "1 [4, 3, 1, 2]\n",
      "2 [4, 3, 5, 1, 2]\n",
      "1 [6, 4, 3, 5, 1, 2]\n",
      "1 [6, 4, 3, 5, 1, 7, 2]\n",
      "3 [6, 4, 3, 8, 5, 1, 7, 2]\n",
      "2 [6, 4, 3, 8, 5, 9, 1, 7, 2]\n",
      "2 [10, 6, 4, 3, 8, 5, 9, 1, 7, 2]\n",
      "2 [10, 6, 4, 3, 8, 11, 5, 9, 1, 7, 2]\n",
      "3 [10, 6, 4, 12, 3, 8, 11, 5, 9, 1, 7, 2]\n",
      "3 [13, 10, 6, 4, 12, 3, 8, 11, 5, 9, 1, 7, 2]\n",
      "4 [14, 13, 10, 6, 4, 12, 3, 8, 11, 5, 9, 1, 7, 2]\n",
      "2 [14, 13, 10, 6, 15, 4, 12, 3, 8, 11, 5, 9, 1, 7, 2]\n",
      "4 [16, 14, 13, 10, 6, 15, 4, 12, 3, 8, 11, 5, 9, 1, 7, 2]\n",
      "3 [16, 14, 13, 10, 6, 15, 17, 4, 12, 3, 8, 11, 5, 9, 1, 7, 2]\n",
      "5 [16, 14, 13, 10, 6, 15, 17, 18, 4, 12, 3, 8, 11, 5, 9, 1, 7, 2]\n",
      "7 [16, 14, 13, 10, 6, 15, 17, 18, 4, 19, 12, 3, 8, 11, 5, 9, 1, 7, 2]\n",
      "6 [16, 14, 13, 20, 10, 6, 15, 17, 18, 4, 19, 12, 3, 8, 11, 5, 9, 1, 7, 2]\n",
      "6 [16, 14, 13, 20, 10, 21, 6, 15, 17, 18, 4, 19, 12, 3, 8, 11, 5, 9, 1, 7, 2]\n",
      "5 [16, 14, 13, 20, 10, 21, 6, 15, 17, 18, 4, 22, 19, 12, 3, 8, 11, 5, 9, 1, 7, 2]\n",
      "5 [16, 14, 13, 20, 10, 21, 6, 15, 17, 18, 4, 22, 19, 12, 3, 8, 23, 11, 5, 9, 1, 7, 2]\n",
      "7 [16, 14, 24, 13, 20, 10, 21, 6, 15, 17, 18, 4, 22, 19, 12, 3, 8, 23, 11, 5, 9, 1, 7, 2]\n",
      "6 [16, 14, 24, 13, 20, 10, 21, 6, 15, 17, 18, 4, 22, 19, 12, 25, 3, 8, 23, 11, 5, 9, 1, 7, 2]\n",
      "7 [16, 14, 24, 13, 20, 10, 21, 6, 15, 17, 18, 4, 26, 22, 19, 12, 25, 3, 8, 23, 11, 5, 9, 1, 7, 2]\n",
      "5 [16, 14, 24, 13, 20, 10, 21, 6, 15, 17, 18, 4, 27, 26, 22, 19, 12, 25, 3, 8, 23, 11, 5, 9, 1, 7, 2]\n",
      "8 [16, 14, 24, 13, 20, 28, 10, 21, 6, 15, 17, 18, 4, 27, 26, 22, 19, 12, 25, 3, 8, 23, 11, 5, 9, 1, 7, 2]\n",
      "7 [29, 16, 14, 24, 13, 20, 28, 10, 21, 6, 15, 17, 18, 4, 27, 26, 22, 19, 12, 25, 3, 8, 23, 11, 5, 9, 1, 7, 2]\n"
     ]
    }
   ],
   "source": [
    "lst = [1, 2]\n",
    "print(lst)\n",
    "for i in range(3, 30):\n",
    "    lsts = build_all(lst, i)\n",
    "    print(len(lsts), lsts[0])\n",
    "    lst = lsts[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "0d6e7633-4e64-4ab9-8668-3c50e0179c59",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 2\n",
      "3 4\n",
      "4 8\n",
      "5 20\n",
      "6 50\n",
      "7 130\n",
      "8 362\n",
      "9 1104\n",
      "10 3614\n"
     ]
    }
   ],
   "source": [
    "prev = set([(1,2), (2,1)])\n",
    "counts2 = []\n",
    "for i in range(2, 11):\n",
    "    print(i, len(prev))\n",
    "    counts2.append(prev)\n",
    "    nxt = [build_all_naive(lst, i + 1) for lst in prev]\n",
    "    prev = set()\n",
    "    for lsts in nxt:\n",
    "        for lst in lsts:\n",
    "            prev.add(tuple(lst))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "dbf6794e-1237-476b-a733-611cf5ce9107",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[[4, 5, 2, 1, 3], [4, 2, 5, 1, 3]],\n",
       " [[5, 1, 3, 4, 2], [1, 3, 4, 2, 5]],\n",
       " [[5, 2, 3, 1, 4], [2, 3, 5, 1, 4], [2, 3, 1, 5, 4]],\n",
       " [[4, 3, 5, 1, 2], [4, 3, 1, 5, 2], [4, 3, 1, 2, 5]],\n",
       " [[3, 1, 5, 2, 4], [3, 1, 2, 5, 4]],\n",
       " [[5, 2, 4, 3, 1], [2, 4, 3, 1, 5]],\n",
       " [[5, 2, 1, 3, 4], [2, 5, 1, 3, 4], [2, 1, 5, 3, 4]],\n",
       " [[4, 5, 1, 3, 2], [4, 1, 5, 3, 2], [4, 1, 3, 2, 5]]]"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nxt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "d551e2cb-0a40-479e-b72b-95fbc13571be",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "20\n",
      "{(2, 1, 5, 3, 4), (4, 3, 1, 5, 2), (4, 2, 5, 1, 3), (5, 1, 3, 4, 2), (2, 5, 1, 3, 4), (4, 5, 1, 3, 2), (2, 4, 3, 1, 5), (4, 1, 5, 3, 2), (3, 1, 5, 2, 4), (2, 3, 5, 1, 4), (4, 3, 1, 2, 5), (4, 3, 5, 1, 2), (5, 2, 4, 3, 1), (1, 3, 4, 2, 5), (3, 1, 2, 5, 4), (4, 1, 3, 2, 5), (5, 2, 3, 1, 4), (5, 2, 1, 3, 4), (4, 5, 2, 1, 3), (2, 3, 1, 5, 4)}\n"
     ]
    }
   ],
   "source": [
    "print(len(prev))\n",
    "print(prev)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "e480bc98-5188-44e1-a9db-940d42cc5c11",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 2\n",
      "3 4\n",
      "4 12\n",
      "5 44\n",
      "6 176\n",
      "7 788\n",
      "8 3936\n",
      "9 23264\n",
      "10 152112\n"
     ]
    }
   ],
   "source": [
    "counts = []\n",
    "for i in range(2, 11):\n",
    "    s = set()\n",
    "    for lst in permutations(range(1, i + 1)):\n",
    "        if is_costas(lst):\n",
    "            s.add(lst)\n",
    "    counts.append(s)\n",
    "    print(i, len(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "0d74a5bc-226e-419e-8261-afe7984404d7",
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "IOPub data rate exceeded.\n",
      "The Jupyter server will temporarily stop sending output\n",
      "to the client in order to avoid crashing it.\n",
      "To change this limit, set the config variable\n",
      "`--ServerApp.iopub_data_rate_limit`.\n",
      "\n",
      "Current values:\n",
      "ServerApp.iopub_data_rate_limit=1000000.0 (bytes/sec)\n",
      "ServerApp.rate_limit_window=3.0 (secs)\n",
      "\n"
     ]
    },
    {
     "ename": "IndexError",
     "evalue": "list index out of range",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mIndexError\u001b[0m                                Traceback (most recent call last)",
      "Cell \u001b[0;32mIn[8], line 2\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[38;5;28;01mfor\u001b[39;00m i \u001b[38;5;129;01min\u001b[39;00m \u001b[38;5;28mrange\u001b[39m(\u001b[38;5;241m10\u001b[39m):\n\u001b[0;32m----> 2\u001b[0m     \u001b[38;5;28mprint\u001b[39m(\u001b[43mcounts\u001b[49m\u001b[43m[\u001b[49m\u001b[43mi\u001b[49m\u001b[43m]\u001b[49m \u001b[38;5;241m-\u001b[39m counts2[i])\n",
      "\u001b[0;31mIndexError\u001b[0m: list index out of range"
     ]
    }
   ],
   "source": [
    "for i in range(10):\n",
    "    print(counts[i] - counts2[i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "506d6572-2cdb-4a5d-a262-154a673917b2",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{(1, 3, 4, 2),\n",
       " (2, 1, 3, 4),\n",
       " (2, 3, 1, 4),\n",
       " (2, 4, 3, 1),\n",
       " (3, 1, 2, 4),\n",
       " (4, 1, 3, 2),\n",
       " (4, 2, 1, 3),\n",
       " (4, 3, 1, 2)}"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "counts2[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "2d5537f2-d7a6-4873-b679-568ff3409f88",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{(1, 2, 4, 3),\n",
       " (1, 3, 4, 2),\n",
       " (1, 4, 2, 3),\n",
       " (2, 1, 3, 4),\n",
       " (2, 3, 1, 4),\n",
       " (2, 4, 3, 1),\n",
       " (3, 1, 2, 4),\n",
       " (3, 2, 4, 1),\n",
       " (3, 4, 2, 1),\n",
       " (4, 1, 3, 2),\n",
       " (4, 2, 1, 3),\n",
       " (4, 3, 1, 2)}"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "counts[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "b0560c92-81d3-415f-a92a-0f629dd251f8",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{(1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2)}"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "counts2[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "ad91bac9-6641-46ce-8d5c-8f96242ad611",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 'a', 'b', 'c']\n",
      "['a', 1, 'b', 'c']\n",
      "['a', 'b', 1, 'c']\n",
      "['a', 'b', 'c', 1]\n"
     ]
    }
   ],
   "source": [
    "for i in range(4):\n",
    "    lst = ['a','b','c']\n",
    "    lst.insert(i, 1)\n",
    "    print(lst)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "7d6705e6-380a-45ed-b486-032fa5d39dcb",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[4, 1, 3, 2], [1, 3, 4, 2]]"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "build_all_naive((1,3,2), 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "53f40627-5ba1-4acd-aa63-2125e8a47455",
   "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
}