{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "e7bfda56-c9bc-41b8-b123-b7b19407e550",
   "metadata": {},
   "source": [
    "search algorithm, dfs, symmetrical problem\n",
    "\n",
    "1 2 3\n",
    "4 5 6\n",
    "7 8 9\n",
    "\n",
    "0,0 0,1 0,2\n",
    "1,0 1,1 1,2\n",
    "2,0 2,1 2,2\n",
    "\n",
    "I think implementing this in Lua with a table will be a good idea.\n",
    "\n",
    "1 -> 2 (right)\n",
    "  -> 5 (diag)\n",
    "  -> 4 (down)\n",
    "\n",
    "the assumption is that we do not know the correct solution.\n",
    "\n",
    "rules:\n",
    "you may create straight strikes across the grid until all the numbers have disappeared.\n",
    "\n",
    "the lower the number of strikes the better. we know it can be done in 4 strikes and 5 strikes.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 355,
   "id": "52de9df5-45b4-4e13-b9de-4d1233337f12",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "class Grid():\n",
    "    def __init__(self, n, m):\n",
    "        self.n = n\n",
    "        self.m = m\n",
    "        self.pucks = n * m\n",
    "        self.board = np.int32(2**(n*m)-1)\n",
    "        self.lines = generate_lines(n, m)\n",
    "        self.memo = set()\n",
    "\n",
    "    def print_board(self):\n",
    "        arr = str(int_to_bits(self.board, 32))[47:64]\n",
    "        print(arr)\n",
    "\n",
    "    def do_move(self, move):\n",
    "        self.board ^= move\n",
    "        return self.board\n",
    "\n",
    "    def available_moves(self):\n",
    "        moves = []\n",
    "        for line in self.lines:\n",
    "            mask = sum(1 << i for i in line)\n",
    "            if (self.board & mask) == mask:  # all bits are still set (i.e. unvisited)\n",
    "                moves.append(mask)\n",
    "        return moves\n",
    "\n",
    "    def search(self, k, depth=0, visited=None):\n",
    "        if visited is None:\n",
    "            visited = self.board\n",
    "    \n",
    "        if depth == k:\n",
    "            return int(visited == 0)\n",
    "    \n",
    "        count = 0\n",
    "        for line in self.lines:\n",
    "            mask = sum(1 << i for i in line)\n",
    "            if (visited & mask) != mask:\n",
    "                continue  # can't draw over already used dots\n",
    "    \n",
    "            is_first_move = visited == (1 << (self.n * self.m)) - 1\n",
    "            if is_first_move or (mask & ~visited):  # connects to drawn part\n",
    "                new_visited = visited ^ mask\n",
    "                key = canonical(new_visited, self.n, self.m)\n",
    "                if key in self.memo:\n",
    "                    continue\n",
    "                self.memo.add(key)\n",
    "                count += self.search(k, depth + 1, new_visited)\n",
    "        return count\n",
    "\n",
    "def generate_lines(n, m):\n",
    "    lines = []\n",
    "\n",
    "    # horizontal\n",
    "    for i in range(n):\n",
    "        for j in range(m):\n",
    "            for length in range(2, m - j + 1):\n",
    "                line = [i * m + (j + k) for k in range(length)]\n",
    "                lines.append(line)\n",
    "\n",
    "    # vertical\n",
    "    for j in range(m):\n",
    "        for i in range(n):\n",
    "            for length in range(2, n - i + 1):\n",
    "                line = [(i + k) * m + j for k in range(length)]\n",
    "                lines.append(line)\n",
    "\n",
    "    # diagonal down-right\n",
    "    for i in range(n):\n",
    "        for j in range(m):\n",
    "            for length in range(2, min(n - i, m - j) + 1):\n",
    "                line = [(i + k) * m + (j + k) for k in range(length)]\n",
    "                lines.append(line)\n",
    "\n",
    "    # diagonal up-right\n",
    "    for i in range(n):\n",
    "        for j in range(m):\n",
    "            for length in range(2, min(i + 1, m - j) + 1):\n",
    "                line = [(i - k) * m + (j + k) for k in range(length)]\n",
    "                lines.append(line)\n",
    "\n",
    "    return lines\n",
    "\n",
    "def int_to_bits(integer, num_bits=None):\n",
    "    if num_bits is None:\n",
    "        num_bits = integer.bit_length()\n",
    "    binary_string = bin(integer)[2:].zfill(num_bits)\n",
    "    bit_array = np.array([int(bit) for bit in binary_string], dtype=np.int8)\n",
    "    return bit_array\n",
    "\n",
    "def rotate90(board, n, m):\n",
    "    rotated = 0\n",
    "    for i in range(n):       # original rows\n",
    "        for j in range(m):   # original cols\n",
    "            bit = (board >> (i * m + j)) & 1\n",
    "            if bit:\n",
    "                new_i = j\n",
    "                new_j = n - 1 - i\n",
    "                new_index = new_i * n + new_j\n",
    "                rotated |= (1 << new_index)\n",
    "    return rotated, m, n\n",
    "\n",
    "def canonical(board, n, m):\n",
    "    boards = []\n",
    "    for _ in range(4):\n",
    "        board, n, m = rotate90(board, n, m)\n",
    "        boards.append(board)\n",
    "    return min(boards)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 356,
   "id": "057407ad-218e-4650-876f-1e17a9db7504",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Ways with 4 lines: 0\n",
      "Ways with 5 lines: 0\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[[0, 1],\n",
       " [0, 1, 2],\n",
       " [1, 2],\n",
       " [3, 4],\n",
       " [3, 4, 5],\n",
       " [4, 5],\n",
       " [6, 7],\n",
       " [6, 7, 8],\n",
       " [7, 8],\n",
       " [0, 3],\n",
       " [0, 3, 6],\n",
       " [3, 6],\n",
       " [1, 4],\n",
       " [1, 4, 7],\n",
       " [4, 7],\n",
       " [2, 5],\n",
       " [2, 5, 8],\n",
       " [5, 8],\n",
       " [0, 4],\n",
       " [0, 4, 8],\n",
       " [1, 5],\n",
       " [3, 7],\n",
       " [4, 8],\n",
       " [3, 1],\n",
       " [4, 2],\n",
       " [6, 4],\n",
       " [6, 4, 2],\n",
       " [7, 5]]"
      ]
     },
     "execution_count": 356,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g = Grid(3, 3)\n",
    "print(\"Ways with 4 lines:\", g.search(4))\n",
    "print(\"Ways with 5 lines:\", g.search(5))\n",
    "g.lines"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 357,
   "id": "2c0c6cdd-5865-4eb3-9703-b2177644f88c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 1 1 1 1 1 1 1 1\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "{63, 127, 223, 238, 239, 351, 365, 367}"
      ]
     },
     "execution_count": 357,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g.print_board()\n",
    "g.memo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 298,
   "id": "c32b926d-2a91-491c-b3ff-ab13e3653533",
   "metadata": {},
   "outputs": [],
   "source": [
    "bits = [(np.int32(448) >> i) & 1 for i in range(9)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 299,
   "id": "b61a9925-c39f-42da-af5b-a6e0f551c240",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[np.int32(0),\n",
       " np.int32(0),\n",
       " np.int32(0),\n",
       " np.int32(0),\n",
       " np.int32(0),\n",
       " np.int32(0),\n",
       " np.int32(1),\n",
       " np.int32(1),\n",
       " np.int32(1)]"
      ]
     },
     "execution_count": 299,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 308,
   "id": "e149d7eb-a6b0-4dba-b5bc-d843d7555a25",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(73, 3, 3)"
      ]
     },
     "execution_count": 308,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rotate90(np.int32(448),3,3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 320,
   "id": "f9ec5225-ae0c-4e58-b383-4fd02db8ea66",
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_lines(n, m):\n",
    "    lines = []\n",
    "\n",
    "    # horizontal\n",
    "    for i in range(n):\n",
    "        for j in range(m):\n",
    "            for length in range(2, m - j + 1):\n",
    "                line = [i * m + (j + k) for k in range(length)]\n",
    "                lines.append(line)\n",
    "\n",
    "    # vertical\n",
    "    for j in range(m):\n",
    "        for i in range(n):\n",
    "            for length in range(2, n - i + 1):\n",
    "                line = [(i + k) * m + j for k in range(length)]\n",
    "                lines.append(line)\n",
    "\n",
    "    # diagonal (down-right)\n",
    "    for i in range(n):\n",
    "        for j in range(m):\n",
    "            for length in range(2, min(n - i, m - j) + 1):\n",
    "                line = [(i + k) * m + (j + k) for k in range(length)]\n",
    "                lines.append(line)\n",
    "\n",
    "    # diagonal (up-right)\n",
    "    for i in range(n):\n",
    "        for j in range(m):\n",
    "            for length in range(2, min(i + 1, m - j) + 1):\n",
    "                line = [(i - k) * m + (j + k) for k in range(length)]\n",
    "                lines.append(line)\n",
    "\n",
    "    return lines\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 321,
   "id": "0f2f0e05-741b-4c8e-b4cf-56a19f0c575c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def search(n, m, k, lines, visited=0, depth=0, last_endpoints=None):\n",
    "    if depth == k:\n",
    "        if visited == (1 << (n * m)) - 1:\n",
    "            return 1  # found a solution\n",
    "        return 0\n",
    "\n",
    "    count = 0\n",
    "    for line in lines:\n",
    "        bits = sum(1 << i for i in line)\n",
    "        if visited & bits:\n",
    "            continue  # already used\n",
    "\n",
    "        # if first move or connects to previous line\n",
    "        if last_endpoints is None or any(i in last_endpoints for i in line):\n",
    "            new_endpoints = [line[0], line[-1]]\n",
    "            count += search(\n",
    "                n, m, k, lines,\n",
    "                visited | bits,\n",
    "                depth + 1,\n",
    "                new_endpoints\n",
    "            )\n",
    "    return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 322,
   "id": "22b1f4f7-3ba0-4a50-a61c-7518cf668f1d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Ways with 4 lines: 0\n",
      "Ways with 5 lines: 0\n"
     ]
    }
   ],
   "source": [
    "lines = generate_lines(3, 3)\n",
    "ways4 = search(3, 3, 4, lines)\n",
    "ways5 = search(3, 3, 5, lines)\n",
    "print(f\"Ways with 4 lines: {ways4}\")\n",
    "print(f\"Ways with 5 lines: {ways5}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 323,
   "id": "f81a50e7-3fc9-4ac6-8f85-6bd31af1dd8a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[0, 1],\n",
       " [0, 1, 2],\n",
       " [1, 2],\n",
       " [3, 4],\n",
       " [3, 4, 5],\n",
       " [4, 5],\n",
       " [6, 7],\n",
       " [6, 7, 8],\n",
       " [7, 8],\n",
       " [0, 3],\n",
       " [0, 3, 6],\n",
       " [3, 6],\n",
       " [1, 4],\n",
       " [1, 4, 7],\n",
       " [4, 7],\n",
       " [2, 5],\n",
       " [2, 5, 8],\n",
       " [5, 8],\n",
       " [0, 4],\n",
       " [0, 4, 8],\n",
       " [1, 5],\n",
       " [3, 7],\n",
       " [4, 8],\n",
       " [3, 1],\n",
       " [4, 2],\n",
       " [6, 4],\n",
       " [6, 4, 2],\n",
       " [7, 5]]"
      ]
     },
     "execution_count": 323,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lines"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 362,
   "id": "09fc61fd-22c8-4993-a37f-4c5125b77cc0",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "416\n"
     ]
    }
   ],
   "source": [
    "DIRECTIONS = [\n",
    "    (-1,  0), (1,  0),  # up, down\n",
    "    (0, -1), (0,  1),   # left, right\n",
    "    (-1, -1), (1, 1),   # diag ↖ ↘\n",
    "    (-1,  1), (1, -1),  # diag ↗ ↙\n",
    "]\n",
    "\n",
    "def in_bounds(x, y, n, m):\n",
    "    return 0 <= x < n and 0 <= y < m\n",
    "\n",
    "def coord_to_index(x, y, m):\n",
    "    return x * m + y\n",
    "\n",
    "def generate_straight_moves(n, m):\n",
    "    moves = {i: [] for i in range(n * m)}\n",
    "    for i in range(n):\n",
    "        for j in range(m):\n",
    "            origin = coord_to_index(i, j, m)\n",
    "            for dx, dy in DIRECTIONS:\n",
    "                path = []\n",
    "                x, y = i + dx, j + dy\n",
    "                while in_bounds(x, y, n, m):\n",
    "                    path.append(coord_to_index(x, y, m))\n",
    "                    moves[origin].append(list(path))  # all partials\n",
    "                    x += dx\n",
    "                    y += dy\n",
    "    return moves\n",
    "\n",
    "def search_paths(n, m, k):\n",
    "    moves = generate_straight_moves(n, m)\n",
    "    results = []\n",
    "\n",
    "    def dfs(pos, visited, path, segments, last_dir):\n",
    "        if visited == (1 << (n * m)) - 1:\n",
    "            if segments == k:\n",
    "                results.append(path[:])\n",
    "            return\n",
    "\n",
    "        for path_segment in moves[pos]:\n",
    "            next_pos = path_segment[-1]\n",
    "            bitmask = sum(1 << p for p in path_segment)\n",
    "            if visited & bitmask:\n",
    "                continue\n",
    "\n",
    "            dx = (next_pos % m) - (pos % m)\n",
    "            dy = (next_pos // m) - (pos // m)\n",
    "            dirn = (dx and dx // abs(dx), dy and dy // abs(dy))\n",
    "\n",
    "            path.extend(path_segment)\n",
    "            if last_dir is None or dirn != last_dir:\n",
    "                dfs(next_pos, visited | bitmask, path, segments + 1, dirn)\n",
    "            else:\n",
    "                dfs(next_pos, visited | bitmask, path, segments, dirn)\n",
    "            for _ in path_segment:\n",
    "                path.pop()\n",
    "\n",
    "    for start in range(n * m):\n",
    "        dfs(start, 1 << start, [start], 0, None)\n",
    "\n",
    "    return results\n",
    "\n",
    "print(search_path(3, 3, 4))  # number of ways to visit all dots in 4 straight lines\n",
    "print(search_path(3, 3, 5))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 361,
   "id": "7f54d8fc-4d27-4505-9d2c-c1afab8361e3",
   "metadata": {},
   "outputs": [],
   "source": [
    "paths = search_paths(3,3,4)\n",
    "for path in paths:\n",
    "    print(path)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e9d99b97-f5e4-42c8-9068-97ac1291c341",
   "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.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}