--- /dev/null
+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))
},
{
"cell_type": "code",
- "execution_count": 2,
+ "execution_count": 1,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 3,
+ "execution_count": 2,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 4,
+ "execution_count": 3,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 5,
+ "execution_count": 4,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 6,
+ "execution_count": 5,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 7,
+ "execution_count": 6,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 8,
+ "execution_count": 7,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 9,
+ "execution_count": 8,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 10,
+ "execution_count": 9,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 11,
+ "execution_count": 10,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 12,
+ "execution_count": 11,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 13,
+ "execution_count": 12,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 14,
+ "execution_count": 13,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 15,
+ "execution_count": 14,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 16,
+ "execution_count": 15,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 17,
+ "execution_count": 16,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 18,
+ "execution_count": 17,
"metadata": {},
"outputs": [
{
"226"
]
},
- "execution_count": 18,
+ "execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 19,
+ "execution_count": 18,
"metadata": {},
"outputs": [
{
"61762"
]
},
- "execution_count": 19,
+ "execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 31,
+ "execution_count": 19,
"metadata": {},
"outputs": [
{
"100"
]
},
- "execution_count": 31,
+ "execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
"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"
]
}
],
},
{
"cell_type": "code",
- "execution_count": 23,
- "metadata": {},
+ "execution_count": 22,
+ "metadata": {
+ "collapsed": true
+ },
"outputs": [],
"source": [
"# %%timeit\n",
},
{
"cell_type": "code",
- "execution_count": null,
- "metadata": {},
+ "execution_count": 23,
+ "metadata": {
+ "collapsed": true
+ },
"outputs": [],
"source": [
"# [(i, j) \n",
},
{
"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",
},
{
"cell_type": "code",
- "execution_count": 24,
+ "execution_count": 25,
"metadata": {},
"outputs": [
{
},
{
"cell_type": "code",
- "execution_count": 25,
+ "execution_count": 26,
"metadata": {},
"outputs": [
{
" (19, 1)]"
]
},
- "execution_count": 25,
+ "execution_count": 26,
"metadata": {},
"output_type": "execute_result"
}
{
"cell_type": "code",
"execution_count": 27,
- "metadata": {},
+ "metadata": {
+ "collapsed": true
+ },
"outputs": [],
"source": [
"# %%timeit\n",
},
{
"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"
]
}
],
},
{
"cell_type": "code",
- "execution_count": 33,
+ "execution_count": 31,
"metadata": {},
"outputs": [
{
"13"
]
},
- "execution_count": 33,
+ "execution_count": 31,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 37,
+ "execution_count": 32,
"metadata": {},
"outputs": [
{
" (212, 113)]"
]
},
- "execution_count": 37,
+ "execution_count": 32,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 38,
+ "execution_count": 33,
"metadata": {},
"outputs": [
{
" (208, 204)]"
]
},
- "execution_count": 38,
+ "execution_count": 33,
"metadata": {},
"output_type": "execute_result"
}
"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,
projects / ou-summer-of-code-2017.git / commitdiff