2020/Day 22.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Day 22 - Card game implementation\n",
    "\n",
    "This is a pretty straightforward coding exercise; I used [`collection.deque()` objects](https://docs.python.org/3/library/collections.html#collections.deque) to hold the card numbers as they are more efficient and easier to work with when continuing to add and remove values from either end.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque\n",
    "from dataclasses import dataclass\n",
    "from typing import Deque\n",
    "\n",
    "\n",
    "@dataclass\n",
    "class Hand:\n",
    "    player: int\n",
    "    cards: Deque[int]\n",
    "\n",
    "    @property\n",
    "    def score(self) -> int:\n",
    "        return sum(i * c for i, c in enumerate(reversed(self.cards), 1))\n",
    "\n",
    "    @classmethod\n",
    "    def from_data(cls, data: str) -> \"Hand\":\n",
    "        lines = data.splitlines()\n",
    "        player = int(lines[0][7:-1])\n",
    "        return cls(player, deque([int(c) for c in lines[1:]]))\n",
    "\n",
    "\n",
    "@dataclass\n",
    "class Game:\n",
    "    player1: Hand\n",
    "    player2: Hand\n",
    "\n",
    "    @classmethod\n",
    "    def from_data(cls, data: str) -> \"Game\":\n",
    "        return cls(*map(Hand.from_data, data.split(\"\\n\\n\")))\n",
    "\n",
    "    def play(self) -> Hand:\n",
    "        p1, p2 = self.player1, self.player2\n",
    "        p1c, p2c = p1.cards, p2.cards\n",
    "        while p1c and p2c:\n",
    "            c1, c2 = p1c.popleft(), p2c.popleft()\n",
    "            if c1 > c2:\n",
    "                p1c += c1, c2\n",
    "            else:\n",
    "                p2c += c2, c1\n",
    "        return p1 if p1c else p2\n",
    "\n",
    "\n",
    "test_data = \"\"\"\\\n",
    "Player 1:\n",
    "9\n",
    "2\n",
    "6\n",
    "3\n",
    "1\n",
    "\n",
    "Player 2:\n",
    "5\n",
    "8\n",
    "4\n",
    "7\n",
    "10\n",
    "\"\"\"\n",
    "test_game = Game.from_data(test_data)\n",
    "assert test_game.play().score == 306"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import aocd\n",
    "\n",
    "data = aocd.get_data(day=22, year=2020)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Part 1: 31629\n"
     ]
    }
   ],
   "source": [
    "game = Game.from_data(data)\n",
    "print(\"Part 1:\", game.play().score)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 2\n",
    "\n",
    "For part 2, I created a subclass that simply creates more instances of itself to run the recursive subgames:()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import islice\n",
    "\n",
    "\n",
    "class RecursiveCombatGame(Game):\n",
    "    player1: Hand\n",
    "    player2: Hand\n",
    "\n",
    "    def play(self) -> Hand:\n",
    "        p1, p2 = self.player1, self.player2\n",
    "        p1c, p2c = p1.cards, p2.cards\n",
    "        seen = set()\n",
    "        while p1c and p2c:\n",
    "            if (state := (tuple(p1c), tuple(p2c))) in seen:\n",
    "                # infinite loop, p1 always wins\n",
    "                return p1\n",
    "            seen.add(state)\n",
    "            c1, c2 = p1c.popleft(), p2c.popleft()\n",
    "            if c1 <= len(p1c) and c2 <= len(p2c):\n",
    "                p1wins = self._recurse(c1, c2)\n",
    "            else:\n",
    "                p1wins = c1 > c2\n",
    "\n",
    "            if p1wins:\n",
    "                p1c += c1, c2\n",
    "            else:\n",
    "                p2c += c2, c1\n",
    "\n",
    "        return p1 if p1c else p2\n",
    "\n",
    "    def _recurse(self, c1, c2):\n",
    "        p1 = Hand(1, deque(islice(self.player1.cards, c1)))\n",
    "        p2 = Hand(2, deque(islice(self.player2.cards, c2)))\n",
    "        return RecursiveCombatGame(p1, p2).play().player == 1\n",
    "\n",
    "\n",
    "test_rcombat = RecursiveCombatGame.from_data(test_data)\n",
    "assert test_rcombat.play().score == 291"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Part 2: 35196\n"
     ]
    }
   ],
   "source": [
    "rcombat = RecursiveCombatGame.from_data(data)\n",
    "print(\"Part 2:\", rcombat.play().score)"
   ]
  }
 ],
 "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.12.0"
  },
  "orig_nbformat": 2
 },
 "nbformat": 4,
 "nbformat_minor": 2
}