1 sample_tours = {'FFLRLLFLRL', 'FLLFFLFFFLFFLFLLRRFR', 'FFRLLFRLLFFFRFLLRLLRRLLRLL'}
8 function turn_left(direction)
9 return(direction - 1) % 4
12 function turn_right(direction)
13 return(direction + 1) % 4
16 function advance(pos, d)
18 return {x = pos.x, y = pos.y + 1, direction = d}
20 return {x = pos.x, y = pos.y - 1, direction = d}
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}
30 function step(s, current)
31 -- print(s, current.x, current.y, current.direction)
33 return advance(current, current.direction)
35 return advance(current, turn_left(current.direction))
37 return advance(current, turn_right(current.direction))
39 error("Invalid instruction")
43 function trace_tour(tour, startx, starty, startdir)
46 startdir = startdir or RIGHT
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)
59 function positions(trace)
61 for _, p in ipairs(trace) do
62 psns[p.x .. ':' .. p.y] = true
70 for _, _ in pairs(positions(trace)) do
73 return trace[#trace].x == 0 and trace[#trace].y == 0 and psns == #trace
79 for tour in io.lines('06-tours.txt') do
80 table.insert(tours, tour)
86 function valid_tours(tours)
88 for _, t in ipairs(tours) do
89 if valid(trace_tour(t)) then
90 table.insert(valids, t)
97 function steps_total(tours)
99 for _, t in ipairs(tours) do
106 function trace_distances(tours)
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)
119 function merge_tours(tour_distances)
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
128 if valid(trace_tour(t12)) then
129 table.insert(goods, t12)
140 function show_step(step)
142 -- for k, v in pairs(step) do
143 -- sstr = sstr .. ', ' .. k .. ': ' .. v
146 return '(' .. step.x .. ', ' .. step.y .. ', ' .. step.direction .. ')'
149 function show_trace(trace)
151 for _, s in ipairs(trace) do
152 stour = stour .. '; ' .. show_step(s)
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))