day-23.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 128,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.next = None\n",
    "\n",
    "class Circle:\n",
    "    def __init__(self, seed):\n",
    "        self.size = len(seed)\n",
    "        self.head = Node(seed[0])\n",
    "        \n",
    "        self.current_node = self.head\n",
    "        \n",
    "        tail = self.head\n",
    "        \n",
    "        for i in range(1, len(seed)):\n",
    "            tail.next = Node(seed[i])\n",
    "            tail = tail.next\n",
    "            \n",
    "        tail.next = self.head\n",
    "        \n",
    "        self.__build_node_ref()\n",
    "    \n",
    "    def __build_node_ref(self):\n",
    "        cur = self.head\n",
    "        \n",
    "        self.node_ref = [None for _ in range(self.size + 1)]\n",
    "        \n",
    "        for i in range(self.size):\n",
    "            self.node_ref[cur.value] = cur            \n",
    "            cur = cur.next\n",
    "    \n",
    "    def remove_after_ref(self, node):\n",
    "        value = node.next.value\n",
    "        node.next = node.next.next\n",
    "        self.node_ref[value] = None\n",
    "        \n",
    "        return value\n",
    "    \n",
    "    def find_destination_ref(self):\n",
    "        destination_value = self.current_node.value\n",
    "        while True:\n",
    "            destination_value -= 1\n",
    "            if destination_value < 0:\n",
    "                destination_value = len(self.node_ref) - 1\n",
    "            if self.node_ref[destination_value] is not None:\n",
    "                return self.node_ref[destination_value]\n",
    "    \n",
    "    def insert_after_ref(self, after_node, value):\n",
    "        node = Node(value)        \n",
    "        node.next = after_node.next\n",
    "        after_node.next = node\n",
    "        \n",
    "        self.node_ref[value] = node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 133,
   "metadata": {},
   "outputs": [],
   "source": [
    "def play_game(seed, rounds):\n",
    "    circle = Circle(seed)\n",
    "    \n",
    "    for _ in range(rounds):\n",
    "        first = circle.remove_after_ref(circle.current_node)\n",
    "        second = circle.remove_after_ref(circle.current_node)\n",
    "        third = circle.remove_after_ref(circle.current_node)\n",
    "        \n",
    "        destination_node = circle.find_destination_ref()\n",
    "        \n",
    "        circle.insert_after_ref(destination_node, third)\n",
    "        circle.insert_after_ref(destination_node, second)\n",
    "        circle.insert_after_ref(destination_node, first)\n",
    "        \n",
    "        circle.current_node = circle.current_node.next\n",
    "    \n",
    "    return circle"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 134,
   "metadata": {},
   "outputs": [],
   "source": [
    "def part1(circle):\n",
    "    current = circle.node_ref[1].next\n",
    "    answer = []\n",
    "    while current.value != 1:\n",
    "        answer.append(current.value)\n",
    "        current = current.next\n",
    "    return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 135,
   "metadata": {},
   "outputs": [],
   "source": [
    "def part2(circle):\n",
    "    return circle.node_ref[1].next.value * circle.node_ref[1].next.next.value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 137,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 574 µs, sys: 1 µs, total: 575 µs\n",
      "Wall time: 579 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'98752463'"
      ]
     },
     "execution_count": 137,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "''.join(str(x) for x in part1(play_game([7,8,9,4,6,5,1,2,3], 100)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 126,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 52.9 s, sys: 352 ms, total: 53.3 s\n",
      "Wall time: 53.6 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "2000455861"
      ]
     },
     "execution_count": 126,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "part2(play_game([7,8,9,4,6,5,1,2,3] + [x for x in range(10, 1_000_000 + 1)], 10_000_000))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}