20_maze_teleports.ipynb

{
 "nbformat": 4,
 "nbformat_minor": 2,
 "metadata": {
  "language_info": {
   "name": "python",
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "version": "3.7.1"
  },
  "orig_nbformat": 2,
  "file_extension": ".py",
  "mimetype": "text/x-python",
  "name": "python",
  "npconvert_exporter": "python",
  "pygments_lexer": "ipython3",
  "version": 3
 },
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "from itertools import count\n",
    "\n",
    "with open('inputs/20.txt') as file:\n",
    "    input = file.read()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": "\n                           |       G A     J     I         O       X       O   |                           \n                           |       N V     N     P         H       N       B   |                           \n  #################################\u001b[31m+\u001b[0m#\u001b[31m+\u001b[0m#####\u001b[31m+\u001b[0m#####\u001b[31m+\u001b[0m#########\u001b[31m+\u001b[0m#######\u001b[31m+\u001b[0m#######\u001b[31m+\u001b[0m#############################  \n  #.....#.#.........#...#.......#.......#.#...#.........#.....#...#...#.....#.........#.....#.......#.#.#  \n  #.###.#.#####.#.#####.#.#####.#####.###.#.###.#########.#####.#.###.#.#########.#######.#####.#.###.#.#  \n  #.#.....#...#.#...#...#.#.#.......#.#.......#...#.#.#.......#.#.....#.......#.....#.#.....#.#.#.#.#...#  \n  #####.#####.#####.###.###.###.###.#.#.#######.###.#.#.#.#####.#########.#######.#.#.#.#####.###.#.#.###  \n  #.......#.#.#...#...#.........#...#.#...#...........#.#.#.........#.....#.......#.#.....#.......#...#.#  \n  #.#.#####.#.###.#.###.#.###.#.###.#.#.###.###.#####.#.#####.#.#########.#.#.#######.###.###.###.#.###.#  \n  #.#.#...#...#.#.......#...#.#...#.#.#.#.#.#.#.#.....#...#.#.#.#.......#...#...........#.#.#.#.#.#...#.#  \n  ###.#.#####.#.###.#.#.#.#.#.###.#.#.#.#.###.#####.###.#.#.###.###.#.#######.#####.#######.#.#.###.#.#.#  \n  #...#.#.#.........#.#.#.#.#.#...#.#.#.......#.....#...#.#...#...#.#.......#.....#.#...#.......#...#.#.#  \n  ###.#.#.#.###.###.###.###.###.###.#.###.###.###.#.#.#.###.###.#######.###.#.###.###.#####.#######.###.#  \n  #.....#.#.#.#.#.#...#.#...#.....#.....#...#.#...#.#.#.....#.....#.....#.......#.#.....#...#.#.........#  \n  #####.#.###.###.#.#.###########.###.#.#####.#.#########.###.#.###.###.#####.#####.#######.#.###.#.#.###  \n  #.#.......#.......#...#...........#.#.#.....#...#.........#.#...#.#.......#.#.#.....#.........#.#.#.#.#  \n  #.#.###########.#.###########.#.#####.#.#.#.#.###.#####.#####.###.#.#.#####.#.#.#########.#######.###.#  \n  #.#.....#.....#.#.#.......#.#.#.#...#.#.#.#.#.#.#.#.....#.#.....#.#.#.#...#.........#...#.#.#.........#  \n  #.#.#######.#.###.#####.###.#.###.#######.#.#.#.#######.#.###.#######.#.###.#####.#.#.###.#.#.#####.#.#  \n  #...#...#...#...#.#.#.............#...#.#.#.#.....#.....#...#...#.....#.........#.#.....#.......#.#.#.#  \n  ###.#.#########.###.###.#####.#######.#.###.#.###.###.###.#.#.#####.#.#######.###.#######.#.#####.#.#.#  \n  #.....#.#.#...#.#.#...#.#.#.#.....#.#...#...#...#.#...#...#.#.....#.#.#.#.#...#.....#.#...#.#.#...#.#.#  \n  #.#####.#.###.#.#.###.###.#.#.#.###.#.#.#.###.#####.#.#.###.###.###.#.#.#.###.###.###.###.###.###.#####  \n  #...#...#...#...#...#.#.#...#.#...#...#.#...#.....#.#...#...#...#.#.#.....#...#.#.#...#.#.#...#.#.#...#  \n  #.#####.###.###.#.###.#.###.#.#.###.#.#.###.#.###.#######.###.#.#.###.#########.#####.#.#.###.#.#.#.#.#  \n  #...#.#...#...#.#.#.......#...#...#.#.#.....#...#.....#.....#.#.....#.......#...#.#...#...#.#...#.#.#.#  \n  #.###.#.###.###.#.#####.#####\u001b[31m+\u001b[0m###\u001b[31m+\u001b[0m###\u001b[31m+\u001b[0m#######\u001b[31m+\u001b[0m#########\u001b[31m+\u001b[0m#####\u001b[31m+\u001b[0m#######\u001b[31m+\u001b[0m#########.#.###.###.#.#.###.###.#  \n--#.#.#.#.#.....#.....#...#|---J---P---V-------X---------M-----W-------I-------|#...#...#.#.....#.....#.#--\n  #.#.#.#.###.###.###.###.#|   N   R   R       N         K     J       P       |#.#####.#.#.#######.#.#.#  \n  #...#.....#.#.#.#.......#|                                                   |#.#.#...#.#.#.#.#...#.#.#  \n  ###.###.###.#.#.###.#.#.#|                                                   |#.#.#.#.#.#.#.#.###.###.#  \n  #.............#...#.#.#.\u001b[31m+\u001b[0mXJ                                                  |#...#.#...#...#.#...#.#.#  \n  #####.#.#####.#.#####.###|                                                   |###.###.#####.#.###.#.#.#  \n  #...#.#.....#.#.#.....#.#|                                                   |#.........#.......#...#.#  \n  #.###.#.###########.###.#|                                                   |#.#######.#.#####.#.#.#.#  \nKM\u001b[31m+\u001b[0m.....#.............#.#.#|                                                  OH\u001b[31m+\u001b[0m.#.#.......#.#.....#...#  \n  #####.#####.#.###.#.#.#.#|                                                   |#.#.#####.#.#.#######.#.#  \n  #.....#.#.#.#.#...#.#...\u001b[31m+\u001b[0mQM                                                  |#.#.#.#...#.#.#...#...#.\u001b[31m+\u001b[0mXJ\n  ###.###.#.#############.#|                                                   |###.#.#######.###.#######  \n  #...#.......#.....#...#.#|                                                   |#.....................#.#  \n  #######.#.###.#.#.###.#.#|                                                   |###.###.#.#.#.###.###.#.#  \nUA\u001b[31m+\u001b[0m.......#.....#.#.......#|                                                  KM\u001b[31m+\u001b[0m...#...#.#.#.#.#.#.....#  \n  #.#.#.###################|                                                   |#.#########.###.#######.#  \n  #.#.#.#.#...........#.#.#|                                                   |#.......#.....#.#.#...#.\u001b[31m+\u001b[0mFQ\n  #.#####.#.#.#.#.#.###.#.#|                                                   |###############.#.###.###  \n  #.#.......#.#.#.#...#...\u001b[31m+\u001b[0mIX                                                 CZ\u001b[31m+\u001b[0m...........#...#.#.....\u001b[31m+\u001b[0mRW\n  #.#####.#####.#####.#.###|                                                   |#######.#.###.#.#.#.###.#  \n  #.#.#.......#.#.........#|                                                   |#...#.#.#.....#...#.#.#.#  \n  ###.#####.#.#.###.#.#####|                                                   |#.###.###.#######.#.#.###  \nWJ\u001b[31m+\u001b[0m.........#.#...#.#.....#|                                                   |#.#.#...#.#...#...#.#...#  \n  ###################.#####|                                                   |#.#.#.#.#####.#.###.###.#  \n  #...#.......#...#...#...\u001b[31m+\u001b[0mQP                                                  |#.#...#.#.#.#.#.....#.#.#  \n  #.###.#.###.#.#########.#|                                                   |#.###.###.#.#.#.###.#.#.#  \nVR\u001b[31m+\u001b[0m.#.#.#.#.#.......#...#.#|                                                   |#.............#...#.#...\u001b[31m+\u001b[0mND\n  #.#.#.###.###.#####.#.#.#|                                                   |#.#####.#.###.#########.#  \n  #.....#.#.#.........#...#|                                                   |#.#.#...#.#.....#.....#.#  \n  #######.#.###############|                                                   |#.#.###.#######.#.###.#.#  \n  #.......................#|                                                   |#...#...#.........#.#...#  \n  #.###.###.#####.#####.###|                                                   |###.###########.#.#.#.###  \n  #...#...#.#.....#.#.#.#.#|                                                  GN\u001b[31m+\u001b[0m.........#.#...#.#...#.#  \n  ###.#.###.#####.#.#.#.#.#|                                                   |###.#.#####.###########.#  \nYD\u001b[31m+\u001b[0m.#.#.#.#.#.......#...#.\u001b[31m+\u001b[0mQE                                                 AV\u001b[31m+\u001b[0m.#.#.#...#.............#  \n  #.#.###.#############.#.#|                                                   |#.#####.#####.#########.#  \n  #.....#.#.#.....#.#.#...#|                                                   |#...#.#.....#.......#...#  \n  #.#.###.#.#.#.###.#.#.###|                                                   |#.###.###.###.#####.#.###  \n  #.#...#.....#.#...#.#.#.\u001b[31m+\u001b[0mND                                                  |#.#.#.#.#...#...#...#...\u001b[31m+\u001b[0mMK\n  #######.###.#####.#.###.#|                                                   |#.#.#.#.#.#######.###.#.#  \n  #...#.#.#.#...#.........#|                                                   |#...................#.#.#  \n  ###.#.#.#.#.#.#####.#####|                                                   |#########################  \nUW\u001b[31m+\u001b[0m.......#...#.......#...#|                                                  PE\u001b[31m+\u001b[0m.....#.................#  \n  ###.#################.###|                                                   |###.###.#.###.#.###.###.#  \n  #.#.#...................#|                                                   |#...#...#...#.#...#.#...\u001b[31m+\u001b[0mPR\n  #.#####.#########.###.###|                                                   |#.#.#.###.#####.#.#.###.#  \n  #...#.#...#.#.....#.#...#|                                                   |#.#.#.#.#...#...#.#.#...#  \n  #.###.###.#.#######.#.###|                                                   |###.#.#.#.#.###.###.###.#  \n  #...........#.#.#.#...#.#|                                                   |#.......#.#...#.#.....#.#  \n  #.#.###.###.#.#.#.#.###.#|                                                   |#.###.#######.#.#######.#  \nPE\u001b[31m+\u001b[0m.#.#...#.#...#.........\u001b[31m+\u001b[0mYD                                                  |#.#...#.....#.#.#...#.#.#  \n  #.###.###.#.#.###.#.#.#.#|                                                   |###.###.#.#.###.###.#.#.#  \n  #...#...#...#...#.#.#.#.#|                                                   |#.......#.#...#.#.......#  \n  ###.#.#.###.#.#####.###.#|     U       O   F         U       N       U   R   |#.#.###.###.#####.#.###.#  \n--#...#.#.#...#.#...#...#.#|-----A-------B---Q---------N-------C-------W---W---|#.#.#.....#...#...#.#.#.#--\n  ###.#####.###.###.#.#.#########\u001b[31m+\u001b[0m#######\u001b[31m+\u001b[0m###\u001b[31m+\u001b[0m#########\u001b[31m+\u001b[0m#######\u001b[31m+\u001b[0m#######\u001b[31m+\u001b[0m###\u001b[31m+\u001b[0m#########.###.#######.###.#.#  \n  #.......#.#.....#...#.#.............#...#.........#.....#...#.#...#.....#.......#...#...#.#.......#...#  \n  #.###.###.###.###.#####.#.###.#.#.###.#.#####.#########.###.#.###.###.###.###.#.#######.#.#####.###.#.#  \n  #.#.....#.#...#...#.....#.#...#.#...#.#...#.#.#.#.#.#.#...#.#...#.....#...#.#.#.....#.#.#...#.....#.#.#  \n  ###.#####.#######.###.#.###.#####.###.#.###.#.#.#.#.#.#.###.#.###.#####.###.#.#.#####.###.#########.###  \n  #...#.#...#.......#...#.#.#.#.....#.#.#...#...#.#.....#.....#.#.....#...#...#.#.#.#.............#.....#  \n  #.#.#.###.###.###.#.#####.#####.###.###.###.#.#.#.###.#.###.#.#.#######.#.#.#.#.#.###.#####.#######.#.#  \n  #.#...#...#.....#.#.....#...#.#.....#.....#.#.#...#.#.....#.#.#.#...#.....#.#.#...........#.#.#.#.#.#.#  \n  #.###.#####.#.#.#.#.#######.#.#####.#.#.#.###.#.#.#####.#####.#.###.###.#######.#############.#.#.#.###  \n  #.#.#.#.....#.#.#.#.......#.........#.#.#.#...#.#...#...#.....#...#.........#...........#.#.#...#.#.#.#  \n  #.#.#####.###.###.#.#.#######.###.###.#######.###.#####.#.###.#.#######.#######.#.#####.#.#.#.###.###.#  \n  #.#...#.#...#.#.#.#.#.#.......#.#...#.....#...#.....#...#.#...#.......#...#.#.#.#.....#...#.#.........#  \n  #####.#.#######.###############.###.#.###.###.###.###.#####.###.#.#####.#.#.#.#.#.#.###.#.#.#.#####.###  \n  #.#.#...#.#.........#...#.#.........#...#...#...#...#.#.#...#.#.#...#.#.#.#...#.#.#.#...#.........#...#  \n  #.#.#.###.#########.###.#.###.#.#.#.#.#.#######.###.###.#.###.#.#####.#.###.###########.###.###.###.###  \n  #.#...#.#...#.#...#...........#.#.#.#.#.#.#.#...#...#.....#.....#.#.......#...#.#.....#.#.#...#.#.#...#  \n  #.###.#.#.###.###.#.#######.#.###.###.###.#.###.#.#######.#####.#.#.###.###.###.###.#####.#.#####.#####  \n  #.........#.........#...#...#.#.#.#.....#...#...#...#.#...#.....#.#.#...........#...#.#...#.......#...#  \n  #######.#####.#########.#####.#.#######.#.#.#.###.###.###.#####.#.#####.#.#######.###.###.###.###.###.#  \n  #.........#.#.#...#.#...#.#...#...#.#...#.#.#.#.#.#...#.....#.....#.....#...#.#...........#.#.#.#.#.#.#  \n  #.#####.###.#.#.###.###.#.###.###.#.#.#.#.#.#.#.#.#.###.###.#####.#######.###.#.#.#.###.#.#.###.###.#.#  \n  #.#...........#.............#.#...#.#.#.#.#.....#.....#.#...#.#.......#.........#.#.#.#.#.#.........#.#  \n  #.###.###.#.###.#.#####.#.###.###.#.###.#.#######.#.#######.#.#######.#.#.#.#.#.###.#.#####.#.###.#.#.#  \n  #.#...#...#...#.#.....#.#.............#.#.....#...#.....#.....#.......#.#.#.#.#...#.........#...#.#...#  \n  ###################################\u001b[31m+\u001b[0m###\u001b[31m+\u001b[0m#####\u001b[31m+\u001b[0m#####\u001b[34m+\u001b[0m#\u001b[31m+\u001b[0m#######\u001b[31m+\u001b[0m###\u001b[31m+\u001b[0m###\u001b[32m+\u001b[0m###\u001b[31m+\u001b[0m#############################  \n                           |         Q   U     I     Z C       Q   Q   A   N   |                           \n                           |         P   N     X     Z Z       E   M   A   C   |                           \nWall time: 26.9 ms\n"
    }
   ],
   "source": [
    "%%time\n",
    "\n",
    "maze = defaultdict(lambda:' ')\n",
    "B,R = 0,0\n",
    "for y,row in enumerate(input.split('\\n')):\n",
    "    for x,c in enumerate(row):\n",
    "        maze[x,y] = c\n",
    "        R = max(R,x)\n",
    "        B = max(B,y)\n",
    "\n",
    "IL,IT,IR,IB = R,B,0,0\n",
    "for y in range(2,B-1):\n",
    "    for x in range(2,R-1):\n",
    "        if maze[x,y] == ' ':\n",
    "            IL = min(IL,x)\n",
    "            IR = max(IR,x)\n",
    "            IT = min(IT,y)\n",
    "            IB = max(IB,y)\n",
    "\n",
    "portals = defaultdict(lambda:[])\n",
    "# first value in list\n",
    "for y in range(2,B-1):\n",
    "    if maze[0,y]!=' ':\n",
    "        portals[maze[0,y]+maze[1,y]].append((2,y))\n",
    "    if maze[R,y]!=' ':\n",
    "        portals[maze[R-1,y]+maze[R,y]].append((R-2,y))\n",
    "for x in range(2,R-1):\n",
    "    if maze[x,0]!=' ':\n",
    "        portals[maze[x,0]+maze[x,1]].append((x,2))\n",
    "    if maze[x,B]!=' ':\n",
    "        portals[maze[x,B-1]+maze[x,B]].append((x,B-2))\n",
    "\n",
    "# second value in list\n",
    "for y in range(IT,IB+1):\n",
    "    if maze[IL,y]!=' ':\n",
    "        portals[maze[IL,y]+maze[IL+1,y]].append((IL-1,y))\n",
    "    if maze[IR,y]!=' ':\n",
    "        portals[maze[IR-1,y]+maze[IR,y]].append((IR+1,y))\n",
    "for x in range(IL,IR+1):\n",
    "    if maze[x,IT]!=' ':\n",
    "        portals[maze[x,IT]+maze[x,IT+1]].append((x,IT-1))\n",
    "    if maze[x,IB]!=' ':\n",
    "        portals[maze[x,IB-1]+maze[x,IB]].append((x,IB+1))\n",
    "\n",
    "links = {}\n",
    "for pp in portals.values():\n",
    "    if len(pp)>1:\n",
    "        links[pp[0]]=pp[1]\n",
    "        links[pp[1]]=pp[0]\n",
    "\n",
    "def pretty():\n",
    "    print()\n",
    "    for y in range(B+1):\n",
    "        row = ''\n",
    "        for x in range(R+1):\n",
    "            p = (x,y)\n",
    "            v = maze[p]\n",
    "            if p in links:\n",
    "                row += '\\x1b[31m+\\x1b[0m'\n",
    "                continue\n",
    "            if p == portals['AA'][0]:\n",
    "                row += '\\x1b[32m+\\x1b[0m'\n",
    "                continue\n",
    "            if p == portals['ZZ'][0]:\n",
    "                row += '\\x1b[34m+\\x1b[0m'\n",
    "                continue\n",
    "            if v==' ':\n",
    "                if x==IL or x==IR:\n",
    "                    row += '|'\n",
    "                    continue\n",
    "                if y==IT or y==IB:\n",
    "                    row += '-'\n",
    "                    continue\n",
    "            row += v\n",
    "        print(row)\n",
    "pretty()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": "Wall time: 18.9 ms\n"
    },
    {
     "data": {
      "text/plain": "422"
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "\n",
    "def ttoi(t): return complex(t[0],t[1])\n",
    "def itot(i): return (int(i.real),int(i.imag))\n",
    "def ppi(p,i): return itot(ttoi(p)+i)\n",
    "\n",
    "def walk(start,goal):\n",
    "    been = defaultdict(lambda:False)\n",
    "    been[start] = True\n",
    "    nxt = [start]\n",
    "    for step in count(1):\n",
    "        if len(nxt)==0: break\n",
    "        cur,nxt = nxt,[]\n",
    "        for p in cur:\n",
    "            for d in [1,-1,1j,-1j]:\n",
    "                np = ppi(p,d)\n",
    "                if maze[np] not in '.# ' and p in links:\n",
    "                    np = links[p]\n",
    "                if maze[np]=='.' and not been[np]:\n",
    "                    if np==goal:\n",
    "                        return step\n",
    "                    been[np] = True\n",
    "                    nxt.append(np)\n",
    "\n",
    "walk(portals['AA'][0], portals['ZZ'][0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": "Wall time: 0 ns\n"
    }
   ],
   "source": [
    "%%time\n",
    "\n",
    "links2 = {}\n",
    "for pp in portals.values():\n",
    "    if len(pp)>1:\n",
    "        links2[pp[0]] = pp[1]+(-1,)\n",
    "        links2[pp[1]] = pp[0]+(1,)\n",
    "\n",
    "def walk2(start3,goal3):\n",
    "    print('start', start3, 'goal', goal3)\n",
    "    been = defaultdict(lambda:False)\n",
    "    been[start3] = True\n",
    "    nxt = [start3]\n",
    "    for step in count(1):\n",
    "        if step%1000==0:\n",
    "            a,b=nxt[0][2],nxt[0][2]\n",
    "            for n in nxt:\n",
    "                a=min(a,n[2])\n",
    "                b=max(b,n[2])\n",
    "            print(f'step {step}, running {len(nxt)} robots, in layers from {a} to {b}')\n",
    "        if len(nxt)==0: break\n",
    "        cur,nxt = nxt,[]\n",
    "        for p3 in cur:\n",
    "            p2 = p3[:2]\n",
    "            for d in [1,-1,1j,-1j]:\n",
    "                np2 = ppi(p2,d)\n",
    "                np3 = np2+(p3[2],)\n",
    "                if maze[np2] not in '.# ' and p2 in links2:\n",
    "                    np33 = p3[2]+links2[p2][2]\n",
    "                    if np33>=0:\n",
    "                        np2 = links2[p2][:2]\n",
    "                        np3 = np2+(np33,)\n",
    "                if maze[np2]=='.' and not been[np3] and np3[2]<=len(portals):\n",
    "                    if np3==goal3:\n",
    "                        return step\n",
    "                    been[np3] = True\n",
    "                    nxt.append(np3)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": "start (71, 106, 0) goal (53, 106, 0)\nstep 1000, running 30 robots, in layers from 16 to 23\nstep 2000, running 6 robots, in layers from 6 to 16\nstep 3000, running 5 robots, in layers from 10 to 25\nstep 4000, running 25 robots, in layers from 6 to 23\nstep 5000, running 18 robots, in layers from 0 to 25\nWall time: 449 ms\n"
    },
    {
     "data": {
      "text/plain": "5040"
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "\n",
    "walk2(portals['AA'][0]+(0,), portals['ZZ'][0]+(0,))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ]
}