I'm a software engineer, get me out of here: Difference between revisions
I'm a software engineer, get me out of here (view source)
Revision as of 00:55, 18 September 2019
, 4 years agojulia example
(Added Go) |
(julia example) |
||
Line 542:
[7 3]->[20 14] 9 [7 3]->[8 4]->[10 6]->[11 7]->[15 11]->[16 11]->[17 12]->[17 16]->[18 16]->[20 14]
</pre>
=={{header|Julia}}==
Uses the LightGraphs package.
<lang julia>
using LightGraphs
const grid = reshape(Vector{UInt8}(replace("""
00000
00003130000
000321322221000
00231222432132200
0041433223233211100
0232231612142618530
003152122326114121200
031252235216111132210
022211246332311115210
00113232262121317213200
03152118212313211411110
03231234121132221411410
03513213411311414112320
00427534125412213211400
013322444412122123210
015132331312411123120
003333612214233913300
0219126511415312570
0021321524341325100
00211415413523200
000122111322000
00001120000
00000 """, "\n" => "")), 23, 23)
const board = map(c -> c == UInt8(' ') ? -1 : c - UInt8('0'), grid)
const startingpoints = [i for i in 1:529 if board[i] > 0]
const safety = [i for i in 1:529 if board[i] == 0]
const legalendpoints = [i for i in 1:529 if board[i] >= 0]
function adjacent(i)
k, ret = board[i], Int[]
row, col = divrem(i - 1, 23) .+ 1
col > k && push!(ret, i - k)
23 - col >= k && push!(ret, i + k)
row > k && push!(ret, i - 23 * k)
row + k <= 23 && push!(ret, i + 23 * k)
row > k && col > k && push!(ret, i - 24 * k)
row + k <= 23 && (23 - col >= k) && push!(ret, i + 24 * k)
row > k && (23 - col >= k) && push!(ret, i - 22 * k)
row + k <= 23 && col > k && push!(ret, i + 22 * k)
ret
end
const graph = SimpleDiGraph(529)
for i in 1:529
if board[i] > 0
for p in adjacent(i)
if board[p] >= 0
add_edge!(graph, i, p)
end
end
end
end
"""
allnpaths(graph, a, b, len)
Return a vector of int vectors, each of which is a path from a to b, where
len is the length of each path, and the nodes in a path do not repeat.
"""
function allnpaths(graph, a, vec, n)
ret = [[a]]
for j in 2:n
nextret = Vector{Vector{Int}}()
for path in ret, x in neighbors(graph, path[end])
if !(x in path) && (j < n || x in vec)
push!(nextret, [path; x])
end
end
ret = nextret
end
return (ret == [[a]] && a != b) ? [] : ret
end
function pathtostring(path)
ret = ""
for node in path
c = CartesianIndices(board)[node]
ret *= "($(c[2]-1), $(c[1]-1)) "
end
ret
end
function pathlisting(paths)
join([pathtostring(p) for p in paths], "\n")
end
println("Part 1:")
let
start = 23 * 11 + 12
pathsfromcenter = dijkstra_shortest_paths(graph, start)
safepaths = filter(p -> length(p) > 1, enumerate_paths(pathsfromcenter, safety))
safelen = mapreduce(length, min, safepaths)
paths = unique(allnpaths(graph, start, safety, safelen))
println("The $(length(paths)) shortest paths to safety are:\n",
pathlisting(paths))
end
println("\nPart 2:")
let
p = enumerate_paths(bellman_ford_shortest_paths(graph, 21 * 23 + 12), 23 + 12)
println("One shortest route from (21, 11) to (1, 11): ", pathtostring(p))
p = enumerate_paths(bellman_ford_shortest_paths(graph, 23 + 12), 21 * 23 + 12)
println("\nOne shortest route from (1, 11) to (21, 11): ", pathtostring(p))
allshortpaths = [enumerate_paths(bellman_ford_shortest_paths(graph, 23 + 12), p) for p in startingpoints]
maxlen, idx = findmax(map(length, allshortpaths))
println("\nLongest Shortest Route (length $(maxlen - 1)) is: ", pathtostring(allshortpaths[idx]))
end
println("\nExtra Credit Questions:")
let
println("\nIs there any cell in the country that can not be reached from HQ (11, 11)?")
frombase = bellman_ford_shortest_paths(graph, 11 * 23 + 12)
unreached = Int[]
for pt in legalendpoints
path = enumerate_paths(frombase, pt)
if isempty(path) && pt != 11 * 23 + 12
push!(unreached, pt)
end
end
print("There are $(length(unreached)): ")
println(pathtostring(unreached))
println("\nWhich cells will it take longest to send reinforcements to from HQ (11, 11)?")
p = [enumerate_paths(frombase, x) for x in legalendpoints]
maxlen = mapreduce(length, max, p)
allmax = [path for path in p if length(path) == maxlen]
println("There are $(length(allmax)) of length $(maxlen - 1):")
println(pathlisting(allmax))
end
</lang>{{out}}
<pre>
Part 1:
The 71 shortest paths to safety are:
(11, 11) (10, 10) (8, 8) (4, 8) (1, 8)
(11, 11) (10, 10) (8, 8) (8, 4) (6, 2)
(11, 11) (10, 10) (8, 8) (12, 4) (9, 1)
(11, 11) (10, 10) (8, 8) (12, 4) (15, 1)
(11, 11) (10, 10) (8, 10) (5, 7) (2, 4)
(11, 11) (10, 10) (8, 10) (5, 13) (1, 9)
(11, 11) (10, 10) (8, 10) (5, 13) (1, 13)
(11, 11) (10, 10) (8, 12) (6, 12) (0, 12)
(11, 11) (10, 10) (12, 8) (8, 4) (6, 2)
(11, 11) (10, 10) (12, 8) (12, 4) (9, 1)
(11, 11) (10, 10) (12, 8) (12, 4) (15, 1)
(11, 11) (10, 10) (12, 8) (16, 4) (13, 1)
(11, 11) (10, 10) (12, 8) (16, 4) (16, 1)
(11, 11) (10, 10) (12, 8) (16, 4) (19, 4)
(11, 11) (10, 10) (12, 8) (16, 12) (20, 16)
(11, 11) (10, 11) (7, 8) (4, 5) (3, 4)
(11, 11) (10, 11) (7, 8) (4, 8) (1, 8)
(11, 11) (10, 11) (7, 8) (4, 11) (1, 8)
(11, 11) (10, 11) (7, 8) (4, 11) (1, 14)
(11, 11) (10, 11) (7, 8) (7, 5) (2, 5)
(11, 11) (10, 11) (7, 8) (7, 5) (12, 0)
(11, 11) (10, 11) (7, 11) (6, 12) (0, 12)
(11, 11) (10, 11) (7, 11) (7, 12) (1, 6)
(11, 11) (10, 11) (10, 14) (12, 16) (16, 20)
(11, 11) (10, 11) (13, 8) (14, 7) (18, 3)
(11, 11) (10, 11) (13, 11) (17, 15) (20, 18)
(11, 11) (10, 12) (9, 12) (7, 12) (1, 6)
(11, 11) (11, 10) (10, 9) (9, 9) (3, 3)
(11, 11) (11, 10) (11, 9) (9, 9) (3, 3)
(11, 11) (11, 12) (8, 9) (2, 9) (1, 8)
(11, 11) (11, 12) (8, 9) (2, 9) (1, 9)
(11, 11) (11, 12) (8, 9) (2, 15) (1, 14)
(11, 11) (11, 12) (8, 9) (2, 15) (1, 15)
(11, 11) (11, 12) (8, 9) (2, 15) (1, 16)
(11, 11) (11, 12) (8, 9) (2, 15) (2, 16)
(11, 11) (11, 12) (8, 9) (8, 3) (6, 1)
(11, 11) (11, 12) (8, 9) (8, 3) (8, 1)
(11, 11) (11, 12) (8, 9) (14, 3) (11, 0)
(11, 11) (11, 12) (8, 12) (6, 12) (0, 12)
(11, 11) (11, 12) (8, 15) (9, 16) (2, 16)
(11, 11) (11, 12) (11, 9) (9, 9) (3, 3)
(11, 11) (11, 12) (11, 15) (11, 17) (7, 21)
(11, 11) (11, 12) (11, 15) (11, 17) (15, 21)
(11, 11) (11, 12) (14, 9) (18, 5) (19, 4)
(11, 11) (11, 12) (14, 9) (18, 13) (22, 9)
(11, 11) (11, 12) (14, 9) (18, 13) (22, 13)
(11, 11) (11, 12) (14, 12) (16, 12) (20, 16)
(11, 11) (11, 12) (14, 15) (16, 15) (19, 18)
(11, 11) (12, 10) (11, 9) (9, 9) (3, 3)
(11, 11) (12, 10) (13, 10) (13, 5) (13, 0)
(11, 11) (12, 10) (13, 10) (18, 5) (19, 4)
(11, 11) (12, 10) (13, 10) (18, 15) (21, 15)
(11, 11) (12, 10) (13, 11) (17, 15) (20, 18)
(11, 11) (12, 11) (9, 14) (6, 17) (4, 19)
(11, 11) (12, 11) (12, 8) (8, 4) (6, 2)
(11, 11) (12, 11) (12, 8) (12, 4) (9, 1)
(11, 11) (12, 11) (12, 8) (12, 4) (15, 1)
(11, 11) (12, 11) (12, 8) (16, 4) (13, 1)
(11, 11) (12, 11) (12, 8) (16, 4) (16, 1)
(11, 11) (12, 11) (12, 8) (16, 4) (19, 4)
(11, 11) (12, 11) (12, 8) (16, 12) (20, 16)
(11, 11) (12, 11) (12, 14) (8, 18) (3, 18)
(11, 11) (12, 11) (12, 14) (16, 18) (13, 21)
(11, 11) (12, 11) (12, 14) (16, 18) (16, 21)
(11, 11) (12, 11) (12, 14) (16, 18) (19, 18)
(11, 11) (12, 11) (15, 8) (15, 5) (18, 2)
(11, 11) (12, 11) (15, 8) (18, 5) (19, 4)
(11, 11) (12, 11) (15, 8) (18, 11) (22, 11)
(11, 11) (12, 11) (15, 11) (16, 12) (20, 16)
(11, 11) (12, 11) (15, 14) (16, 15) (19, 18)
(11, 11) (12, 12) (13, 11) (17, 15) (20, 18)
Part 2:
One shortest route from (21, 11) to (1, 11): (21, 11) (21, 12) (19, 14) (14, 14) (12, 14) (8, 18) (3, 13) (1, 11)
One shortest route from (1, 11) to (21, 11): (1, 11) (2, 10) (5, 13) (9, 9) (15, 3) (20, 8) (20, 10) (21, 11)
Longest Shortest Route (length 9) is: (1, 11) (2, 10) (5, 13) (9, 9) (15, 15) (16, 14) (16, 17) (17, 16) (18, 16) (20, 14)
Extra Credit Questions:
Is there any cell in the country that can not be reached from HQ (11, 11)?
There are 3: (2, 18) (4, 3) (18, 20)
Which cells will it take longest to send reinforcements to from HQ (11, 11)?
There are 5 of length 6:
(11, 11) (12, 11) (9, 14) (6, 17) (4, 17) (4, 18) (3, 19)
(11, 11) (10, 11) (7, 11) (7, 12) (7, 18) (7, 20) (6, 20)
(11, 11) (11, 12) (11, 15) (13, 17) (15, 19) (15, 20) (17, 20)
(11, 11) (11, 12) (14, 15) (16, 17) (17, 16) (18, 16) (20, 14)
(11, 11) (12, 12) (13, 11) (17, 15) (20, 12) (21, 11) (22, 12)
</pre>
=={{header|Phix}}==
| |||