2016/day11.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Usage: m4 [-Dhashsize=H] [-Dfile=day11.input] day11.m4
   3 # Optionally use -Dverbose=[12] to see some progress
   4 # Optionally use -Donly=[12] to skip a part
   5 # Optionally use -Dpriority=1|2|3|4|5 to choose priority queue algorithms
   6
   7 include(`common.m4')ifelse(common(11, 65537), `ok', `',
   8 `errprint(`Missing common initialization
   9 ')m4exit(1)')
  10
  11 include(`priority.m4')
  12
  13 # Encode state as 8 hex digits: first is floor (0-3), remaining 7 cover pairs
  14 # Each pair is bbBB, bb for chip floor, BB for generator floor
  15 # Pairs are interchangeable, so normalize packed pairs in descending order
  16 # Packing in hex requires more eval, so favor exploded lists instead
  17 define(`state', 0)define(`floor', 0)define(`pairs', 0)
  18 define(`explode', `_$0($1, pairs)')
  19 define(`_explode', `eval(`($1&0x30000000)>>28')forloop(0, decr($2),
  20   `,eval(($1>>4*', `)&15)')')
  21 define(`pack', ``0x'eval(($1<<28)|_$0(shift($@)), 16, 8)')
  22 define(`_pack', `ifelse(`$#', 1, `$1', `(($0(shift($@)))<<4)|$1')')
  23 define(`map0', `40')define(`map1', `41')define(`map2', `42')
  24 define(`map3', `43')define(`map4', `50')define(`map5', `51')
  25 define(`map6', `52')define(`map7', `53')define(`map8', `60')
  26 define(`map9', `61')define(`map10', `62')define(`map11', `63')
  27 define(`map12', `70')define(`map13', `71')define(`map14', `72')
  28 define(`map15', `73')
  29 define(`map', `ifelse(`$#', 1, `', `$0$2`'$0(shift($@))')')
  30 define(`perfloor', `_$0(map($@))')
  31 define(`_perfloor', `$0_($1, `40')$0_($1, `51')$0_($1, `62')$0_($1, `73')')
  32 define(`_perfloor_', `,len(translit($1, $2`'01234567, --))')
  33 define(`heur', `eval(_$0($1perfloor($@)))')
  34 define(`_heur', `ifelse($2$3$4, 000, 0, $2$3, 00, `$0_1(decr(decr($1)), $4)',
  35   $2, 0, `$0_2(decr($1), $3, $4)', $1$2, 01, `1 + $0_2(0, incr($3), $4)',
  36   $1, 0, `(2*$2-3) + $0_2(0, eval($2+$3), $4)', `(2*$2+$1-1) + $0_2(0,
  37   eval($2+$3+($1>1)), eval($4-($1==2)))')')
  38 define(`_heur_2', `ifelse($1, 0, `(2*$2-3) + _heur_1(0, eval($2+$3))',
  39   `(2*$2+$1-1) + _heur_1(0, eval($2+$3+($1>1)))')')
  40 define(`_heur_1', `ifelse($1, 0, `(2*$2-3)', `(2*$2)')')
  41 define(`prep', `forloop(0, 15, `_$0(', `, $1)')')
  42 define(`_prep', `define(`sort_$1_$2', eval($1 <= $2))')
  43 forloop_arg(0, 15, `prep')
  44 define(`sort_', `ifdef(`$0$1_$2', `$0$1_$2', `eval(`$1 <= $2')')')
  45 define(`sort', `ifelse(`$2', `', ``,$1'', `ifelse($0_($1, $2), 1,
  46   ``,$@'', ``,$2'$0(`$1', shift(shift($@)))')')')
  47 define(`addpair', `define(`state', first(state)sort(eval($1),
  48   shift(state)))define(`pairs', incr(pairs))')
  49
  50 define(`canon', `$1_$0(,shift($@))')
  51 define(`_canon', `ifelse(`$2', `', `$1', `$0(sort($2, shift($1)),
  52   shift(shift($@)))')')
  53 define(`mapat0', `40')define(`mapat1', `51')define(`mapat2', `62')
  54 define(`mapat3', `73')
  55 define(`mapat', `translit(map($@), mapat$1`'40516273, `CGcgcgcgcg')')
  56 define(`safeat', `_$0(mapat($@))')
  57 define(`_safeat', `ifelse(index(`$1', `G'), -1, 1, `eval((`0x'translit(`$1',
  58   `CcGg', `10')` & 0x'translit(`$1', `GgCc', `01')) == 0)')')
  59 define(`safe', `ifelse(safeat(0,shift($@))safeat(1,shift($@))safeat(2,
  60   shift($@))safeat(3,shift($@)), 1111, 1, 0)')
  61 define(`neighbors', `ifelse($1, 0, `', `_$0(decr($1), $@)')ifelse($1, 3, `',
  62   `_$0(incr($1), $@)')')
  63 define(`_neighbors1', `ifelse($3, eval(`$2*5'), `try($1, eval(`$1*5'),
  64   $4,$5,$6,$7,$8,$9)')ifelse(eval(`$3/4'), $2, `try($1, eval(`$1*4+$3%4'),
  65   $4,$5,$6,$7,$8,$9)')ifelse(eval(`$3%4'), $2, `try($1, eval(`$1+($3&12)'),
  66   $4,$5,$6,$7,$8,$9)')')
  67 define(`_neighbors2', `ifelse(eval(`$3/4*10+$4/4', 10, 2), $2$2,
  68   `try($1,eval(`$1*4+$3%4'),eval(`$1*4+$4%4'),$5,$6,$7,$8,$9)')ifelse(eval(
  69   `$3%4*10+$4%4', 10, 2), $2$2, `try($1,eval(`$1+($3&12)'), eval(`$1+($4&12)'),
  70   $5,$6,$7,$8,$9)')')
  71 define(`_neighbors',
  72 `_neighbors1($1,$2,$3,$4,$5,$6,$7,$8,$9)'dnl
  73 `_neighbors1($1,$2,$4,$3,$5,$6,$7,$8,$9)'dnl
  74 `ifelse(`$5', `', `', `_neighbors1($1,$2,$5,$3,$4,$6,$7,$8,$9)')'dnl
  75 `ifelse(`$6', `', `', `_neighbors1($1,$2,$6,$3,$4,$5,$7,$8,$9)')'dnl
  76 `ifelse(`$7', `', `', `_neighbors1($1,$2,$7,$3,$4,$5,$6,$8,$9)')'dnl
  77 `ifelse(`$8', `', `', `_neighbors1($1,$2,$8,$3,$4,$5,$6,$7,$9)')'dnl
  78 `ifelse(`$9', `', `', `_neighbors1($1,$2,$9,$3,$4,$5,$6,$7,$8)')'dnl
  79 dnl
  80 `_neighbors2($1,$2,$3,$4,$5,$6,$7,$8,$9)'dnl
  81 `ifelse(`$5', `', `', `_neighbors2($1,$2,$3,$5,$4,$6,$7,$8,$9)')'dnl
  82 `ifelse(`$6', `', `', `_neighbors2($1,$2,$3,$6,$4,$5,$7,$8,$9)')'dnl
  83 `ifelse(`$7', `', `', `_neighbors2($1,$2,$3,$7,$4,$5,$6,$8,$9)')'dnl
  84 `ifelse(`$8', `', `', `_neighbors2($1,$2,$3,$8,$4,$5,$6,$7,$9)')'dnl
  85 `ifelse(`$9', `', `', `_neighbors2($1,$2,$3,$9,$4,$5,$6,$7,$8)')'dnl
  86 dnl
  87 `ifelse(`$5', `', `', `_neighbors2($1,$2,$4,$5,$3,$6,$7,$8,$9)')'dnl
  88 `ifelse(`$6', `', `', `_neighbors2($1,$2,$4,$6,$3,$5,$7,$8,$9)')'dnl
  89 `ifelse(`$7', `', `', `_neighbors2($1,$2,$4,$7,$3,$5,$6,$8,$9)')'dnl
  90 `ifelse(`$8', `', `', `_neighbors2($1,$2,$4,$8,$3,$5,$6,$7,$9)')'dnl
  91 `ifelse(`$9', `', `', `_neighbors2($1,$2,$4,$9,$3,$5,$6,$7,$8)')'dnl
  92 dnl
  93 `ifelse(`$6', `', `', `_neighbors2($1,$2,$5,$6,$3,$4,$7,$8,$9)')'dnl
  94 `ifelse(`$7', `', `', `_neighbors2($1,$2,$5,$7,$3,$4,$6,$8,$9)')'dnl
  95 `ifelse(`$8', `', `', `_neighbors2($1,$2,$5,$8,$3,$4,$6,$7,$9)')'dnl
  96 `ifelse(`$9', `', `', `_neighbors2($1,$2,$5,$9,$3,$4,$6,$7,$8)')'dnl
  97 dnl
  98 `ifelse(`$7', `', `', `_neighbors2($1,$2,$6,$7,$3,$4,$5,$8,$9)')'dnl
  99 `ifelse(`$8', `', `', `_neighbors2($1,$2,$6,$8,$3,$4,$5,$7,$9)')'dnl
 100 `ifelse(`$9', `', `', `_neighbors2($1,$2,$6,$9,$3,$4,$5,$7,$8)')'dnl
 101 dnl
 102 `ifelse(`$8', `', `', `_neighbors2($1,$2,$7,$8,$3,$4,$5,$6,$9)')'dnl
 103 `ifelse(`$9', `', `', `_neighbors2($1,$2,$7,$9,$3,$4,$5,$6,$8)')'dnl
 104 dnl
 105 `ifelse(`$9', `', `', `_neighbors2($1,$2,$8,$9,$3,$4,$5,$6,$7)')'dnl
 106 )
 107
 108 define(`parse_second', `define(`floor', 1)')
 109 define(`parse_third', `define(`floor', 2)')
 110 define(`parse_fourth', `define(`floor', 3)')
 111 define(`parse_generator', `ifdef(`type$1', `addpair(type$1 + floor)',
 112   `define(`type$1', floor)')')
 113 define(`parse_compatible', `ifdef(`type$1', `addpair(floor * 4 + type$1)',
 114   `define(`type$1', floor * 4)')')
 115 define(`parse', `ifelse(`$1$2', `', `', `parse_$2(`$1')$0(shift($@))')')
 116 parse(translit((include(defn(`file'))), -nl` .()', `,,,'))
 117
 118 output(1, `parse complete: 'pairs` pairs, initial state 'pack(state))
 119
 120 define(`hit', 0)
 121 define(`miss', 0)
 122 define(`iter', 0)
 123 define(`progress', `define(`$1', incr($1))ifelse(eval((hit + miss + iter) %
 124   10000), 0, `output(2, `progress:'eval(hit + miss + iter))')')
 125
 126 define(`addwork', `define(`g$4', ``$2', `$1'')_$0(eval($2 + heur($3)),
 127   `$3', `$4')')
 128 define(`_addwork', `define(`f$3', $1)progress(`hit')insert($@)')
 129 define(`distance', `define(`goal', quote(_explode(-1, decr(`$#'))))addwork(`',
 130   0, `$*', translit(``$*'', `,', `_'))loop(pop)clearall()')
 131 define(`loop', `ifelse($1, `', ``no solution possible'', eval($1 > f$3), 1,
 132   `progress(`miss')loop(pop)', `$2', defn(`goal'), `$1', `progress(
 133   `iter')pushdef(`current', ``$3','incr(first(g$3)))neighbors($2)popdef(
 134   `current')loop(pop)')')
 135 define(`follow', `_$0(translit(quote(_explode(-1, decr(`$#'))), `,', `_'))')
 136 define(`_follow', `$0_(shift(g$1), `$1')')
 137 define(`_follow_', `ifelse(`$1', `', `$2', `_follow(`$1')` $2'')')
 138
 139 define(`try', `_$0(canon($@))')
 140 define(`_try', `ifdef(translit(``g$*'', `,', `_'), `', `ifelse(safe($@), 1,
 141   `addwork(current, `$*', translit(``$*'', `,', `_'))')')')
 142
 143 ifelse(ifdef(`only', only, 1), 1, `
 144 output(1, `starting part 1')
 145 define(`part1', distance(state))
 146 output(1, `hits:'hit` misses:'miss` iters:'iter)
 147 ')
 148 ifelse(ifdef(`only', only, 2), 2, `
 149 output(1, `starting part 2')
 150 define(`hit', 0)
 151 define(`miss', 0)
 152 define(`iter', 0)
 153 define(`part2', distance(state, 0, 0))
 154 output(1, `hits:'hit` misses:'miss` iters:'iter)
 155 ')
 156
 157 divert`'part1`'ifelse(verbose, 2, ` (follow(state))')
 158 part2`'ifelse(verbose, 2, ` (follow(state, 0, 0))')