2021/day23.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Usage: m4 [-Dhashsize=H] [-Dfile=day23.input] day23.m4
   3 # Optionally use -Dverbose=1 to see some progress
   4 # Optionally use -Dalgo=dfs|dijkstra|astar to choose search algorithm
   5 # Optionally use -Dpriority=0|1|2|3|4|5 to choose priority queue algorithms
   6
   7 include(`common.m4')ifelse(common(23, 1000003), `ok', `',
   8 `errprint(`Missing common initialization
   9 ')m4exit(1)')
  10
  11 include(`priority.m4')
  12 ifdef(`algo', `', `define(`algo', `astar')')
  13
  14 define(`init', translit(include(defn(`file')), `ABCD .#'nl, `1234'))
  15
  16 # At most 28 possible valid moves in a turn, board can be represented as:
  17 # AB_C_D_E_FG
  18 #   H I J K
  19 #   L M N O
  20 #   P Q R S
  21 #   T U V W
  22 define(`count', 0)
  23 define(`r1', `HLPT')
  24 define(`r2', `IMQU')
  25 define(`r3', `JNRV')
  26 define(`r4', `KOSW')
  27 define(`setup', `_$0(count, $@)')
  28 define(`_setup', `define(`p$1', `$2, `$3', `$4', 'dquote(defn(
  29   `r$5'))`, $5, $6')define(`count', incr($1))')
  30 setup(   0,    `B', `A', 1, 2)
  31 setup(    ,     `', `B', 1, 1)
  32 setup(    ,     `', `C', 1, 1)
  33 setup(   0,    `C', `D', 1, 3)
  34 setup(  00,   `CD', `E', 1, 5)
  35 setup( 000,  `CDE', `F', 1, 7)
  36 setup(0000, `CDEF', `G', 1, 8)
  37 setup(  00,   `BC', `A', 2, 4)
  38 setup(   0,    `C', `B', 2, 3)
  39 setup(    ,     `', `C', 2, 1)
  40 setup(    ,     `', `D', 2, 1)
  41 setup(   0,    `D', `E', 2, 3)
  42 setup(  00,   `DE', `F', 2, 5)
  43 setup( 000,  `DEF', `G', 2, 6)
  44 setup( 000,  `BCD', `A', 3, 6)
  45 setup(  00,   `CD', `B', 3, 5)
  46 setup(   0,    `D', `C', 3, 3)
  47 setup(    ,     `', `D', 3, 1)
  48 setup(    ,     `', `E', 3, 1)
  49 setup(   0,    `E', `F', 3, 3)
  50 setup(  00,   `EF', `G', 3, 4)
  51 setup(0000, `BCDE', `A', 4, 8)
  52 setup( 000,  `CDE', `B', 4, 7)
  53 setup(  00,   `DE', `C', 4, 5)
  54 setup(   0,    `E', `D', 4, 3)
  55 setup(    ,     `', `E', 4, 1)
  56 setup(    ,     `', `F', 4, 1)
  57 setup(   0,    `F', `G', 4, 2)
  58 define(`s01', 1)
  59 define(`s02', 10)
  60 define(`s03', 100)
  61 define(`s04', 1000)
  62 define(`s10', 1)
  63 define(`s20', 10)
  64 define(`s30', 100)
  65 define(`s40', 1000)
  66 define(`v1C', `translit(`eval((A>1)+(B>1)+(H>1)+(L>1)+(P>1)+(T>1) >= 3)',
  67   'dquote(defn(`ALPHA'))`, $1)')
  68 define(`x', `+($1!=0&&$1!=2)')
  69 define(`v2D', `translit(`eval(x(A)x(B)x(C)x(I)x(M)x(Q)x(U) >= 4)',
  70   'dquote(defn(`ALPHA'))`, $1)')
  71 define(`y', `+($1!=0&&$1!=3)')
  72 define(`v3D', `translit(`eval(y(E)y(F)y(G)y(J)y(N)y(R)y(V) >= 4)',
  73   'dquote(defn(`ALPHA'))`, $1)')
  74 define(`v4E', `translit(`eval(!!(F%4)+!!(G%4)+!!(K%4)+!!(O%4)+!!(S%4)+!!(W%4)
  75   >= 3)', 'dquote(defn(`ALPHA'))`, $1)')
  76
  77 ifelse(algo, `dfs', `
  78 output(1, `Using unsorted depth-first-search')
  79 define(`addwork', `define(`d$1', `$2')neighbors($1, $2)')
  80 define(`_distance', `d00000001234123412341234$1')
  81
  82 ', algo, `dijkstra', `
  83 output(1, `Using Dijkstra search')
  84 define(`addwork', `define(`d$1', `$2')insert($2, $1)')
  85 define(`_distance', `loop(pop, $1)clearall()')
  86 define(`loop', `ifelse($2, `00000001234123412341234$3', $1, `neighbors($2,
  87   d$2)loop(pop, $3)')')
  88
  89 ', algo, `astar', `
  90 output(1, `Using A* search')
  91 define(`setup', `_$0(index(-ALPHA, `$1'), $2, $3, $4, $5, $6)')
  92 define(`_setup', `define(`h$1'0, $2)define(`h$1'1, $3)define(`h$1'2,
  93   $4)define(`h$1'3, $5)define(`h$1'4, $6)')
  94 setup(`A', 0, 3, 50, 700, 9000)
  95 setup(`B', 0, 2, 40, 600, 8000)
  96 setup(`C', 0, 2, 20, 400, 6000)
  97 setup(`D', 0, 4, 20, 200, 4000)
  98 setup(`E', 0, 6, 40, 200, 2000)
  99 setup(`F', 0, 8, 60, 400, 2000)
 100 setup(`G', 0, 9, 70, 500, 3000)
 101 setup(`H', 0, 0, 40, 600, 8000)
 102 setup(`I', 0, 4, 0, 400, 6000)
 103 setup(`J', 0, 6, 40, 0, 4000)
 104 setup(`K', 0, 8, 60, 400, 0)
 105 setup(`L', 1, 0, 51, 701, 9001)
 106 setup(`M', 10, 15, 0, 510, 7010)
 107 setup(`N', 100, 107, 150, 0, 5100)
 108 setup(`O', 1000, 1009, 1070, 1500, 0)
 109 setup(`P', 2, 0, 62, 802, 10002)
 110 setup(`Q', 20, 26, 0, 620, 8020)
 111 setup(`R', 200, 208, 260, 0, 6200)
 112 setup(`S', 2000, 2010, 2080, 2600, 0)
 113 setup(`T', 3, 0, 73, 903, 11003)
 114 setup(`U', 30, 37, 0, 730, 9030)
 115 setup(`V', 300, 309, 370, 0, 7300)
 116 setup(`W', 3000, 3011, 3090, 3700, 0)
 117
 118 define(`heur', `translit(`eval(h1A+h2B+h3C+h4D+h5E+h6F+h7G+h8H+h9I+h10J+
 119   h11K+h12L+h13M+h14N+h15O+h16P+h17Q+h18R+h19S+h20T+h21U+h22V+h23W)',
 120   'dquote(defn(`ALPHA'))`, `$1')')
 121 define(`addwork', `define(`d$1', `$2')_$0(eval($2 + heur($1)), $1)')
 122 define(`_addwork', `define(`f$2', $1)insert($@)')
 123 define(`_distance', `loop(pop, $1)clearall()')
 124 define(`loop', `ifelse($2, `00000001234123412341234$3', $1, ifdef(`f$2',
 125   `eval($1 > f$2)', 0), 1, `loop(pop, $3)', `neighbors($2, d$2)loop(pop, $3)')')
 126
 127 ', `output(0, `unknown search algorithm')m4exit(1)')
 128
 129 define(`drop')
 130 define(`check', `_$0(p$1, $2, $3)')
 131 define(`_check', `path($1, translit(`$2, $3$4', 'dquote(defn(`ALPHA'))`, $7),
 132   `$3', `$4', $5, $6, $7, $8)')
 133 define(`path', `ifelse($1, $2, `_$0(translit(`V, W, X, Y, Z', `VWXYZ', $3),
 134   $6), `$4', `$5', $7, $8, $9)')')
 135 define(`_path', `ifelse($1$2$3$4$5, $6`0000', `use(4,$1,0', $1$2$3$4$5,
 136   $6`000'$6, `use(3,$1,0', $1$2$3$4$5, $6`00'$6$6, `use(2,$1,0', $1$2$3$4$5,
 137   $6`0'$6$6$6, `use(1,$1,0', $1$2$3$4$5, 00000, `drop(', $1$2$3$4$5, 0000$6,
 138   `drop(', $1$2$3$4, 0000, `use(4,0,$5', $1$2$3$4$5, 000$6$6, `drop(',
 139   $1$2$3, 000, `use(3,0,$4', $1$2$3$4$5, 00$6$6$6, `drop(', $1$2, 00,
 140   `use(2,0,$3', $1$2$3$4$5, 0$6$6$6$6, `drop(', $1, 0, `use(1,0,$2', `drop(')')
 141 define(`use', `pushdef(`n'ifelse($3, 0, 0, 1), `_$0(translit(''dquote(dquote(
 142   defn(`ALPHA')))``, translit(``0$1'', 01234, `$4$5')''dquote(dquote(
 143   defn(`ALPHA')))``, $3$2$7), eval($8+($1+$6)*s$2$3), `$3$4')')')
 144 define(`_use', `ifelse(ifdef(`v$3', `v$3($1)', 0), 1, `', ifdef(`d$1',
 145   `eval($2 < d$1)', 1), 1, `addwork($1, $2)show(progress)')')
 146 define(`progress', 0)
 147 define(`rename', `define(`$2', defn(`$1'))popdef(`$1')')
 148 define(`show1000', `output(1, `...$1')rename(`show$1', `show'eval($1+1000))')
 149 define(`show', `ifdef(`$0$1', `$0$1($1)')define(`progress', incr($1))')
 150 define(`neighbors', forloop(0, decr(count), ``check('', ``, $'`1, $'`2)'')dnl
 151 `first(ifdef(`n0', `defn(`n0')undefine(`n0')undefine(`n1')', `_$0()'))')
 152 define(`_neighbors', `ifdef(`n1', `defn(`n1')popdef(`n1')$0()')')
 153 define(`distance', `output(1, `...part $2')addwork(`0000000$1$2', 0)_$0($2)')
 154 define(`part1', distance(init`'12341234, 1))
 155 define(`part2', distance(translit(`IJKL43214213MNOP', `IJKLMNOP', init), 2))
 156
 157 divert`'part1
 158 part2