Matt Parker's Maths Puzzle 5 - Coin puzzle

MPMP5.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Game data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "positions = 10\n",
    "# The 3 seed moves. All other moves are those ones reverted and/or rotated \n",
    "moves_init = [(1, 2, 4), (1, 3, 6), (2, 5, 9)]\n",
    "# The rotations (120°, anti-clockwise): 1 > 7 > 10 > 1, 2 > 8 > 6 > 2, ...\n",
    "rotations = [(1, 7, 10), (2, 8, 6), (4, 9, 3), (5, 5, 5)]\n",
    "# The 3 possible starting positions. All other positions are identical by symetry/rotation\n",
    "starting_positions = [1, 2, 5]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Generating all possible moves\n",
    "\n",
    "Using rotations and reversing the moves, we can generate the complete set from the small provided set"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "rotations {1: 7, 7: 10, 10: 1, 2: 8, 8: 6, 6: 2, 4: 9, 9: 3, 3: 4, 5: 5}\n",
      "moves [(1, 2, 4), (1, 3, 6), (2, 4, 7), (2, 5, 9), (3, 5, 8), (3, 6, 10), (4, 2, 1), (4, 5, 6), (6, 3, 1), (6, 5, 4), (7, 4, 2), (7, 8, 9), (8, 5, 3), (8, 9, 10), (9, 5, 2), (9, 8, 7), (10, 6, 3), (10, 9, 8)]\n"
     ]
    }
   ],
   "source": [
    "r = {}\n",
    "for rotation in rotations:\n",
    "    r.update(dict(zip(rotation, (rotation * 2)[1:4])))\n",
    "print(\"rotations\", r)  # r is a mapping of point > point after 120° rotation (anticlockwise)\n",
    "\n",
    "moves = set(moves_init + [move[::-1] for move in moves_init])  # Add reverted moves\n",
    "rotated_moves = set(moves)\n",
    "for rotation in range(1, 3):\n",
    "    rotated_moves = {tuple(r[e] for e in move) for move in rotated_moves}\n",
    "    moves |= rotated_moves\n",
    "print(\"moves\", sorted(moves))  # moves is all possible moves. format: (start, jump over, end)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Simulating games"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "import collections\n",
    "Game = collections.namedtuple(\"Game\", \"history board\")\n",
    "\n",
    "class Finished(Exception):\n",
    "    pass\n",
    "\n",
    "def explore(game):\n",
    "    \"\"\"\n",
    "    Take a game and yield all possible moves.\n",
    "    If we won, raise Finished.\n",
    "    If no possible move, yield nothing.\n",
    "    \"\"\"\n",
    "    if len(game.board) == 1:\n",
    "        raise Finished\n",
    "    for move in moves:\n",
    "        if set(move) - game.board == {move[2]}:  # if 0 and 1 are in the board but 2 isn't\n",
    "            yield Game(history=game.history + [(move[0], move[2])], board=game.board - set(move) | {move[2]})\n",
    "\n",
    "def explore_all(initial_games):\n",
    "    \"\"\"\n",
    "    From possible starting position, recursively explore all games \n",
    "    \"\"\"\n",
    "    finished_games = list()\n",
    "    games_to_explore = list(initial_games)\n",
    "    while games_to_explore:\n",
    "        game = games_to_explore.pop(0)\n",
    "        try:\n",
    "            games_to_explore.extend(explore(game))\n",
    "        except Finished:\n",
    "            finished_games.append(game)\n",
    "            \n",
    "    return finished_games"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# It's time to compute"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "14\n"
     ]
    }
   ],
   "source": [
    "games_to_explore=[\n",
    "    Game(history=[pos], board=set(range(1, positions + 1)) - {pos})\n",
    "    for pos in starting_positions\n",
    "]\n",
    "finished_games = explore_all(games_to_explore)\n",
    "print(len(finished_games))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4.4 ms ± 113 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "# Just for fun\n",
    "explore_all(games_to_explore)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Formatting the results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "score: 5 - start with 2 - 7-2, 1-4, 9-7-2, 6-4-1-6, 10-3\n",
      "score: 5 - start with 2 - 7-2, 1-4, 9-7-2, 6-1-4-6, 10-3\n",
      "score: 6 - start with 2 - 7-2, 6-4, 1-6, 10-3, 4-1-6, 8-10-3\n",
      "score: 6 - start with 2 - 7-2, 9-7, 1-4, 7-2, 6-4-1-6, 10-3\n",
      "score: 6 - start with 2 - 7-2, 9-7, 1-4, 7-2, 6-1-4-6, 10-3\n",
      "score: 6 - start with 2 - 7-2, 1-4, 6-1, 9-7-2, 1-4-6, 10-3\n",
      "score: 7 - start with 2 - 7-2, 6-4, 1-6, 4-1, 10-3, 1-6, 8-10-3\n",
      "score: 7 - start with 2 - 7-2, 6-4, 1-6, 10-3, 8-10, 4-1-6, 10-3\n",
      "score: 7 - start with 2 - 7-2, 9-7, 1-4, 6-1, 7-2, 1-4-6, 10-3\n",
      "score: 7 - start with 2 - 7-2, 1-4, 9-7, 6-1, 7-2, 1-4-6, 10-3\n",
      "score: 7 - start with 2 - 7-2, 1-4, 6-1, 4-6, 10-3, 1-6, 8-10-3\n",
      "score: 8 - start with 2 - 7-2, 6-4, 1-6, 4-1, 10-3, 8-10, 1-6, 10-3\n",
      "score: 8 - start with 2 - 7-2, 6-4, 1-6, 10-3, 4-1, 8-10, 1-6, 10-3\n",
      "score: 8 - start with 2 - 7-2, 1-4, 6-1, 4-6, 10-3, 8-10, 1-6, 10-3\n"
     ]
    }
   ],
   "source": [
    "import functools\n",
    "\n",
    "def summary(game):\n",
    "    answer = [[game.history[0]]]\n",
    "    for start, end in game.history[1:]:\n",
    "        if answer[-1][-1] == start:\n",
    "            answer[-1].append(end)\n",
    "        else:\n",
    "            answer.append([start, end])\n",
    "    return answer\n",
    "            \n",
    "for start, *game in sorted((summary(game) for game in finished_games), key=len):\n",
    "    print(f\"score: {len(game)} - start with {start[0]} - {', '.join('-'.join(str(e) for e in move) for move in game)}\")"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}

https://www.think-maths.co.uk/coin-puzzle