From 2d3f221991090996eff0709c9f803c5003af2da6 Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Wed, 19 Jul 2017 00:57:18 +0100 Subject: [PATCH] Done day 6 in Lua --- 06-tour-shapes/day6.lua | 162 +++++++++++++++++++++ 06-tour-shapes/tour-shapes-solution.ipynb | 167 ++++++++++++++++------ 2 files changed, 288 insertions(+), 41 deletions(-) create mode 100644 06-tour-shapes/day6.lua diff --git a/06-tour-shapes/day6.lua b/06-tour-shapes/day6.lua new file mode 100644 index 0000000..cd0aa50 --- /dev/null +++ b/06-tour-shapes/day6.lua @@ -0,0 +1,162 @@ +sample_tours = {'FFLRLLFLRL', 'FLLFFLFFFLFFLFLLRRFR', 'FFRLLFRLLFFFRFLLRLLRRLLRLL'} + +UP = 0 +RIGHT = 1 +DOWN = 2 +LEFT = 3 + +function turn_left(direction) + return(direction - 1) % 4 +end + +function turn_right(direction) + return(direction + 1) % 4 +end + +function advance(pos, d) + if d == UP then + return {x = pos.x, y = pos.y + 1, direction = d} + elseif d == DOWN then + return {x = pos.x, y = pos.y - 1, direction = d} + elseif d == LEFT then + return {x = pos.x - 1, y = pos.y, direction = d} + elseif d == RIGHT then + return {x = pos.x + 1, y = pos.y, direction = d} + else + return pos + end +end + +function step(s, current) + -- print(s, current.x, current.y, current.direction) + if s == 'F' then + return advance(current, current.direction) + elseif s == 'L' then + return advance(current, turn_left(current.direction)) + elseif s == 'R' then + return advance(current, turn_right(current.direction)) + else + error("Invalid instruction") + end +end + +function trace_tour(tour, startx, starty, startdir) + startx = startx or 0 + starty = starty or 0 + startdir = startdir or RIGHT + + local current = {x = startx, y = starty, direction = startdir} + local trace = {current} + for c in tour:gmatch"." do + current = step(c, current) + table.insert(trace, current) + end + + return trace +end + + +function positions(trace) + local psns = {} + for i, p in ipairs(trace) do + psns[p.x .. ':' .. p.y] = true + end + return psns +end + + +function valid(trace) + local psns = 1 + for k, v in pairs(positions(trace)) do + psns = psns + 1 + end + return trace[#trace].x == 0 and trace[#trace].y == 0 and psns == #trace +end + + +function read_tours() + local tours = {} + for tour in io.lines('06-tours.txt') do + table.insert(tours, tour) + end + return tours +end + + +function valid_tours(tours) + local valids = {} + for i, t in ipairs(tours) do + if valid(trace_tour(t)) then + table.insert(valids, t) + end + end + return valids +end + + +function steps_total(tours) + local steps = 0 + for i, t in ipairs(tours) do + steps = steps + #t + end + return steps +end + + +function trace_distances(tours) + local tds = {} + for i, tour in ipairs(tours) do + local t = trace_tour(tour) + local l1 = math.abs(t[#t].x) + math.abs(t[#t].y) + local l1s = tds[l1] or {} + table.insert(l1s, tour) + tds[l1] = l1s + end + return tds +end + + +function merge_tours(tour_distances) + local goods = {} + for d1, t1s in pairs(tour_distances) do + for d2, t2s in pairs(tour_distances) do + if d1 ~= 0 and d2 ~= 0 and math.abs(d1 - d2) <= 1 then + for k, t1 in ipairs(t1s) do + for l, t2 in ipairs(t2s) do + if t1 ~= t2 then + local t12 = t1 .. t2 + if valid(trace_tour(t12)) then + table.insert(goods, t12) + end + end + end + end + end + end + end + return goods +end + +function show_step(step) + -- sstr = "" + -- for k, v in pairs(step) do + -- sstr = sstr .. ', ' .. k .. ': ' .. v + -- end + -- return sstr + return '(' .. step.x .. ', ' .. step.y .. ', ' .. step.direction .. ')' +end + +function show_trace(trace) + local stour = '' + for i, s in ipairs(trace) do + stour = stour .. '; ' .. show_step(s) + end + return stour +end + +trs = read_tours() +tdists = trace_distances(trs) +tpairs = merge_tours(tdists) +-- print(#trs, #valid_tours(trs), steps_total(valid_tours(trs))) +print(steps_total(valid_tours(trs)), + steps_total(valid_tours(trs)) + steps_total(tpairs)) diff --git a/06-tour-shapes/tour-shapes-solution.ipynb b/06-tour-shapes/tour-shapes-solution.ipynb index 11bba60..5823e5a 100644 --- a/06-tour-shapes/tour-shapes-solution.ipynb +++ b/06-tour-shapes/tour-shapes-solution.ipynb @@ -11,7 +11,7 @@ }, { "cell_type": "code", - "execution_count": 2, + "execution_count": 1, "metadata": { "collapsed": true }, @@ -28,7 +28,7 @@ }, { "cell_type": "code", - "execution_count": 3, + "execution_count": 2, "metadata": { "collapsed": true }, @@ -55,7 +55,7 @@ }, { "cell_type": "code", - "execution_count": 4, + "execution_count": 3, "metadata": { "collapsed": true }, @@ -67,7 +67,7 @@ }, { "cell_type": "code", - "execution_count": 5, + "execution_count": 4, "metadata": { "collapsed": true }, @@ -86,7 +86,7 @@ }, { "cell_type": "code", - "execution_count": 6, + "execution_count": 5, "metadata": { "collapsed": true }, @@ -105,7 +105,7 @@ }, { "cell_type": "code", - "execution_count": 7, + "execution_count": 6, "metadata": { "collapsed": true }, @@ -122,7 +122,7 @@ }, { "cell_type": "code", - "execution_count": 8, + "execution_count": 7, "metadata": { "collapsed": true }, @@ -134,7 +134,7 @@ }, { "cell_type": "code", - "execution_count": 9, + "execution_count": 8, "metadata": { "collapsed": true }, @@ -148,7 +148,7 @@ }, { "cell_type": "code", - "execution_count": 10, + "execution_count": 9, "metadata": { "collapsed": true }, @@ -174,7 +174,7 @@ }, { "cell_type": "code", - "execution_count": 11, + "execution_count": 10, "metadata": { "collapsed": true }, @@ -197,7 +197,7 @@ }, { "cell_type": "code", - "execution_count": 12, + "execution_count": 11, "metadata": { "collapsed": true }, @@ -210,7 +210,7 @@ }, { "cell_type": "code", - "execution_count": 13, + "execution_count": 12, "metadata": { "collapsed": true }, @@ -221,7 +221,7 @@ }, { "cell_type": "code", - "execution_count": 14, + "execution_count": 13, "metadata": { "collapsed": true }, @@ -236,7 +236,7 @@ }, { "cell_type": "code", - "execution_count": 15, + "execution_count": 14, "metadata": { "collapsed": true }, @@ -248,7 +248,7 @@ }, { "cell_type": "code", - "execution_count": 16, + "execution_count": 15, "metadata": { "collapsed": true }, @@ -260,7 +260,7 @@ }, { "cell_type": "code", - "execution_count": 17, + "execution_count": 16, "metadata": { "collapsed": true }, @@ -293,7 +293,7 @@ }, { "cell_type": "code", - "execution_count": 18, + "execution_count": 17, "metadata": {}, "outputs": [ { @@ -302,7 +302,7 @@ "226" ] }, - "execution_count": 18, + "execution_count": 17, "metadata": {}, "output_type": "execute_result" } @@ -315,7 +315,7 @@ }, { "cell_type": "code", - "execution_count": 19, + "execution_count": 18, "metadata": {}, "outputs": [ { @@ -324,7 +324,7 @@ "61762" ] }, - "execution_count": 19, + "execution_count": 18, "metadata": {}, "output_type": "execute_result" } @@ -335,7 +335,7 @@ }, { "cell_type": "code", - "execution_count": 31, + "execution_count": 19, "metadata": {}, "outputs": [ { @@ -344,7 +344,7 @@ "100" ] }, - "execution_count": 31, + "execution_count": 19, "metadata": {}, "output_type": "execute_result" } @@ -382,7 +382,7 @@ "name": "stdout", "output_type": "stream", "text": [ - "1 loop, best of 3: 211 ms per loop\n" + "1 loop, best of 3: 213 ms per loop\n" ] } ], @@ -400,8 +400,10 @@ }, { "cell_type": "code", - "execution_count": 23, - "metadata": {}, + "execution_count": 22, + "metadata": { + "collapsed": true + }, "outputs": [], "source": [ "# %%timeit\n", @@ -416,8 +418,10 @@ }, { "cell_type": "code", - "execution_count": null, - "metadata": {}, + "execution_count": 23, + "metadata": { + "collapsed": true + }, "outputs": [], "source": [ "# [(i, j) \n", @@ -431,8 +435,10 @@ }, { "cell_type": "code", - "execution_count": null, - "metadata": {}, + "execution_count": 24, + "metadata": { + "collapsed": true + }, "outputs": [], "source": [ "# (sum(len(t) for t in tours if valid(trace_tour(t)))\n", @@ -449,7 +455,7 @@ }, { "cell_type": "code", - "execution_count": 24, + "execution_count": 25, "metadata": {}, "outputs": [ { @@ -488,7 +494,7 @@ }, { "cell_type": "code", - "execution_count": 25, + "execution_count": 26, "metadata": {}, "outputs": [ { @@ -508,7 +514,7 @@ " (19, 1)]" ] }, - "execution_count": 25, + "execution_count": 26, "metadata": {}, "output_type": "execute_result" } @@ -520,7 +526,9 @@ { "cell_type": "code", "execution_count": 27, - "metadata": {}, + "metadata": { + "collapsed": true + }, "outputs": [], "source": [ "# %%timeit\n", @@ -586,14 +594,14 @@ }, { "cell_type": "code", - "execution_count": 32, + "execution_count": 30, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ - "1 loop, best of 3: 1.27 s per loop\n" + "1 loop, best of 3: 1.29 s per loop\n" ] } ], @@ -631,7 +639,7 @@ }, { "cell_type": "code", - "execution_count": 33, + "execution_count": 31, "metadata": {}, "outputs": [ { @@ -640,7 +648,7 @@ "13" ] }, - "execution_count": 33, + "execution_count": 31, "metadata": {}, "output_type": "execute_result" } @@ -651,7 +659,7 @@ }, { "cell_type": "code", - "execution_count": 37, + "execution_count": 32, "metadata": {}, "outputs": [ { @@ -672,7 +680,7 @@ " (212, 113)]" ] }, - "execution_count": 37, + "execution_count": 32, "metadata": {}, "output_type": "execute_result" } @@ -683,7 +691,7 @@ }, { "cell_type": "code", - "execution_count": 38, + "execution_count": 33, "metadata": {}, "outputs": [ { @@ -704,7 +712,7 @@ " (208, 204)]" ] }, - "execution_count": 38, + "execution_count": 33, "metadata": {}, "output_type": "execute_result" } @@ -713,6 +721,83 @@ "sorted(good_is, key=lambda p: p[1])" ] }, + { + "cell_type": "code", + "execution_count": 34, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[(1, 1),\n", + " (2, 1),\n", + " (3, 4),\n", + " (4, 5),\n", + " (5, 7),\n", + " (6, 3),\n", + " (7, 1),\n", + " (8, 2),\n", + " (9, 2),\n", + " (11, 2),\n", + " (18, 1),\n", + " (19, 1),\n", + " (21, 1),\n", + " (24, 1),\n", + " (132, 2),\n", + " (26, 2),\n", + " (28, 1),\n", + " (29, 1),\n", + " (34, 2),\n", + " (36, 1),\n", + " (37, 3),\n", + " (166, 2),\n", + " (40, 2),\n", + " (41, 2),\n", + " (44, 3),\n", + " (46, 1),\n", + " (48, 2),\n", + " (50, 3),\n", + " (52, 2),\n", + " (53, 1),\n", + " (54, 1),\n", + " (56, 2),\n", + " (57, 3),\n", + " (58, 1),\n", + " (59, 2),\n", + " (61, 1),\n", + " (64, 1),\n", + " (66, 2),\n", + " (68, 1),\n", + " (70, 1),\n", + " (74, 1),\n", + " (75, 1),\n", + " (76, 3),\n", + " (77, 1),\n", + " (81, 1),\n", + " (82, 2),\n", + " (86, 1),\n", + " (88, 1),\n", + " (90, 1),\n", + " (94, 1),\n", + " (97, 1),\n", + " (98, 1),\n", + " (101, 2),\n", + " (106, 1),\n", + " (107, 1),\n", + " (114, 2),\n", + " (117, 3),\n", + " (127, 1)]" + ] + }, + "execution_count": 34, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "[(l, len(l1s[l])) for l in l1s.keys()]" + ] + }, { "cell_type": "code", "execution_count": null, -- 2.34.1