06-tour-shapes/day6.lua

   1 sample_tours = {'FFLRLLFLRL', 'FLLFFLFFFLFFLFLLRRFR', 'FFRLLFRLLFFFRFLLRLLRRLLRLL'}
   2
   3 UP = 0
   4 RIGHT = 1
   5 DOWN = 2
   6 LEFT = 3
   7
   8 function turn_left(direction)
   9   return(direction - 1) % 4
  10 end
  11
  12 function turn_right(direction)
  13   return(direction + 1) % 4
  14 end
  15
  16 function advance(pos, d)
  17   if d == UP then
  18     return {x = pos.x, y = pos.y + 1, direction = d}
  19   elseif d == DOWN then
  20     return {x = pos.x, y = pos.y - 1, direction = d}
  21   elseif d == LEFT then
  22     return {x = pos.x - 1, y = pos.y, direction = d}
  23   elseif d == RIGHT then
  24     return {x = pos.x + 1, y = pos.y, direction = d}
  25   else
  26     return pos
  27   end
  28 end
  29
  30 function step(s, current)
  31   -- print(s, current.x, current.y, current.direction)
  32   if s == 'F' then
  33     return advance(current, current.direction)
  34   elseif s == 'L' then
  35     return advance(current, turn_left(current.direction))
  36   elseif s == 'R' then
  37     return advance(current, turn_right(current.direction))
  38   else
  39     error("Invalid instruction")
  40   end
  41 end
  42
  43 function trace_tour(tour, startx, starty, startdir)
  44   startx = startx or 0
  45   starty = starty or 0
  46   startdir = startdir or RIGHT
  47
  48   local current = {x = startx, y = starty, direction = startdir}
  49   local trace = {current}
  50   for c in tour:gmatch"." do
  51     current = step(c, current)
  52     table.insert(trace, current)
  53   end
  54
  55   return trace
  56 end
  57
  58
  59 function positions(trace)
  60   local psns = {}
  61   for _, p in ipairs(trace) do
  62     psns[p.x .. ':' .. p.y] = true
  63   end
  64   return psns
  65 end
  66
  67
  68 function valid(trace)
  69   local psns = 1
  70   for _, _ in pairs(positions(trace)) do
  71     psns = psns + 1
  72   end
  73   return trace[#trace].x == 0 and trace[#trace].y == 0 and psns == #trace
  74 end
  75
  76
  77 function read_tours()
  78   local tours = {}
  79   for tour in io.lines('06-tours.txt') do
  80     table.insert(tours, tour)
  81   end
  82   return tours
  83 end
  84
  85
  86 function valid_tours(tours)
  87   local valids = {}
  88   for _, t in ipairs(tours) do
  89     if valid(trace_tour(t)) then
  90       table.insert(valids, t)
  91     end
  92   end
  93   return valids
  94 end
  95
  96
  97 function steps_total(tours)
  98   local steps = 0
  99   for _, t in ipairs(tours) do
 100     steps = steps + #t
 101   end
 102   return steps
 103 end
 104
 105
 106 function trace_distances(tours)
 107   local tds = {}
 108   for _, tour in ipairs(tours) do
 109     local t = trace_tour(tour)
 110     local l1 = math.abs(t[#t].x) + math.abs(t[#t].y)
 111     local l1s = tds[l1] or {}
 112     table.insert(l1s, tour)
 113     tds[l1] = l1s
 114   end
 115   return tds
 116 end
 117
 118
 119 function merge_tours(tour_distances)
 120   local goods = {}
 121   for d1, t1s in pairs(tour_distances) do
 122     for d2, t2s in pairs(tour_distances) do
 123       if d1 ~= 0 and d2 ~= 0 and math.abs(d1 - d2) <= 1 then
 124         for _, t1 in ipairs(t1s) do
 125           for _, t2 in ipairs(t2s) do
 126             if t1 ~= t2 then
 127               local t12 = t1 .. t2
 128               if valid(trace_tour(t12)) then
 129                 table.insert(goods, t12)
 130               end
 131             end
 132           end
 133         end
 134       end
 135     end
 136   end
 137   return goods
 138 end
 139
 140 function show_step(step)
 141   -- sstr = ""
 142   -- for k, v in pairs(step) do
 143   --   sstr = sstr .. ', ' .. k .. ': ' .. v
 144   -- end
 145   -- return sstr
 146   return '(' .. step.x .. ', ' .. step.y .. ', ' .. step.direction .. ')'
 147 end
 148
 149 function show_trace(trace)
 150   local stour = ''
 151   for _, s in ipairs(trace) do
 152     stour = stour .. '; ' .. show_step(s)
 153   end
 154   return stour
 155 end
 156
 157 trs = read_tours()
 158 tdists = trace_distances(trs)
 159 tpairs = merge_tours(tdists)
 160 -- print(#trs, #valid_tours(trs), steps_total(valid_tours(trs)))
 161 print(steps_total(valid_tours(trs)),
 162   steps_total(valid_tours(trs)) + steps_total(tpairs))