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 10:54, 10 December 2023
, 5 months ago→{{header|Wren}}: Minor tidy
Tag: Undo |
m (→{{header|Wren}}: Minor tidy) |
||
| (14 intermediate revisions by 5 users not shown) | |||
Line 1:
{{
Your latest contract has hit a snag. You came to update the army payroll system, but awoke this morning to the sound of mortars landing not far away and panicked generals banging on you door. The President has loaded his gold on trucks and needs to find the shortest route to safety. You are given the following map. The top left hand corner is (0,0). You and The President are located at HQ in the centre of the country (11,11). Cells marked 0 indicate safety. Numbers other than 0 indicate the number of cells that his party will travel in a day in any direction up, down, left, right, or diagonally.
<pre>
Line 38:
# [[Dijkstra's algorithm]]
# [[Floyd-Warshall algorithm]]
;See also:
* [https://en.wikipedia.org/wiki/Back_from_the_Klondike Back from the Klondike].
=={{header|F_Sharp|F#}}==
Line 542 ⟶ 545:
[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|J}}==
Here, the task specification is "magic" (or "software engineer fantasy"):
One interpretation of this task would be that, for example, "4" means that it takes 6 hours to traverse that map position. Instead, it looks like "4" means we launch ourselves in one of eight directions and land four squares away -- this process takes one day. This concept adds some complexity to the task (we have to make sure we do not launch ourselves off the map, or outside the safe zones), but also reduces the size of intermediate results.
=== J Part 1 ===
Here's how we can find escape routes for el presidente:<syntaxhighlight lang=J>map=: <:,"_1 {.@>:@".@>>cutLF{{)n
00000
00003130000
000321322221000
00231222432132200
0041433223233211100
0232231612142618530
003152122326114121200
031252235216111132210
022211246332311115210
00113232262121317213200
03152118212313211411110
03231234121132221411410
03513213411311414112320
00427534125412213211400
013322444412122123210
015132331312411123120
003333612214233913300
0219126511415312570
0021321524341325100
00211415413523200
000122111322000
00001120000
00000
}}
adjacent=: 0 0-.~>,{;~i:1
plan=: {{
loc=. {:y
range=. (<loc){map
next=. (loc+"1/range*adjacent)-.y
next=. next #~ */"1]0 <: next
next=. next #~ */"1]($map) >"1 next
next=. next #~ 0 <: (<"1 next) { map
assert. 2={:$next
y,"2 1 next
}}
dijkpaths=: {{
K=: 0
adjacent=: 0 0-.~>,{;~i:1 NB. horizontal, diagonal, vertical
plans=: ,:,:y NB. list of paths
while. -.0 e. distances=: (<@{:"2 plans){map do.
plans=: ; <@plan"_1 plans
end.
(0=distances)#plans
}}
fmtpaths=: {{ rplc&'j,'"1":j./"1 y }}</syntaxhighlight>
And here's what that gives us:
<syntaxhighlight lang=J> fmtpaths dijkpaths 11 11
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
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
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
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</syntaxhighlight>
=== J Part 2 ===
For troop movements, we assume that our troops move in exactly the same way as our president's gold convoy. (Note that this means that no cells are reachable from the safe zone. Which might be why it is the safe zone...)
We need to form a distance graph, and some supporting code. <syntaxhighlight lang=J>floyd=: {{for_j.i.#y do. y=. y<.j({"1+/{) y end.}}
cells=: I.,0<:,map
pairs=: cells i.;<@(($map) #. plan)"_1 ($map)#:,.I.0<,map
graph=: floyd 1 (<"1 pairs)} (,~#cells)$_
floydpaths=: {{
start=: cells i. ($map)#.x
end=: cells i. ($map)#.y
distance=: (<start,end){graph
if. _ = distance do. EMPTY end.
paths=: ,:start
targets=: end{"1 graph
for_d. }:i.-distance do.
viable=: I.d=targets
paths=.; <@{{
p=. plan&.(($map)&#:)&.({&cells) y
p#~ ({:"_1 p) e. viable
}}"1 paths
end.
($map)#:cells {~paths,.end
}}</syntaxhighlight>
And the task examples: <syntaxhighlight lang=J> #21 11 floydpaths 1 11
10
#1 11 floydpaths 21 11
1
fmtpaths {. 21 11 floydpaths 1 11
21,11 20,10 19,9 18,9 13,4 6,11 4,11 1,11
fmtpaths 1 11 floydpaths 21 11
1,11 2,10 5,13 9,9 15,3 20,8 20,10 21,11
NB. shortest path distances:
\:~ ~.,graph
_ 9 8 7 6 5 4 3 2 1
longestshortest=: ($map)#:cells{~($graph)#:I.9=,graph
fmtpaths longestshortest NB. start,end for paths of length 9
1,11 20,14
2,9 20,14
2,13 20,14
7,3 20,14
10,21 14,2
11,21 14,2
12,21 14,2
fmtpaths {.@floydpaths/"2 longestshortest NB. examples
1,11 1,10 4,10 6,12 12,18 13,19 13,20 17,16 18,16 20,14
2,9 1,10 4,10 6,12 12,18 13,19 13,20 17,16 18,16 20,14
2,13 2,11 4,9 6,9 8,9 14,15 16,17 17,16 18,16 20,14
7,3 6,3 3,6 6,9 8,9 14,15 16,17 17,16 18,16 20,14
10,21 9,20 7,18 9,16 9,9 15,3 15,8 15,5 15,2 14,2
11,21 10,20 9,19 9,16 9,9 15,3 15,8 15,5 15,2 14,2
12,21 10,19 9,18 8,18 13,13 13,11 17,7 15,5 15,2 14,2</syntaxhighlight>
Note that we have assumed, here, that 1,11 is row 1, column 11. If instead, we wanted column 1 row 11, we should have also been displaying the above results with coordinates swapped. Still, just in case, we can venture into that realm where column numbers appear before row numbers for a brief moment:<syntaxhighlight lang=J> #1 11 floydpaths&.:(|."1) 21 11
3
#21 11 floydpaths&.:(|."1) 1 11
1
fmtpaths {.1 11 floydpaths&.:(|."1) 21 11
1,11 4,8 6,8 7,7 9,5 15,5 21,11
fmtpaths 21 11 floydpaths&.:(|."1) 1 11
21,11 20,10 19,9 16,9 9,9 3,9 2,10 1,11</syntaxhighlight>
(Other than this sample, all J presentation here assumes row number before column number.)
=== J Extra Credit ===
Our <code>map</code> is a 23 by 23 matrix of "ranges" -- how far we get launched when we leave the cell at that location on the map. We use _1 to indicate locations which we ignore (spaces). We've preserved the original text of the map in <code>M</code> which is a 23 by 23 matrix of characters.
Locations are generally represented by a pair of indices (row, column) into the above structures. But for the floyd warshall algorithm we need a distance graph. To translate between the graph format and the map data structure, we have a list of cells. Cells are a base 23 representation of the row,column indices (In other words 9 represents row 0, column 9, while 23 represents row 1, column 0, and HQ has a cell value of (23*11)+11).)
<syntaxhighlight lang=J> HQ=: cells i.($map)#.11 11 NB. HQ as a graph index
\:~ ~. HQ{graph NB. all path lengths starting at HQ
_ 6 5 4 3 2 1
($map)#:cells{~I._=HQ{graph NB. can't get there from HQ
2 18
4 3
18 20
($map)#:cells{~I.6=HQ{graph NB. 6 days from HQ
3 19
6 20
17 20
20 14
22 12</syntaxhighlight>
=={{header|Julia}}==
Line 777 ⟶ 1,000:
(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|Nim}}==
{{trans|Phix}}
With some borrowings from Go and Wren's versions.
Using a simple breadth-first search. Parts 1 and 2 and extra credit.
<syntaxhighlight lang="Nim">import std/[sequtils, strformat, strutils]
const Gmooh = """
.........00000.........
......00003130000......
....000321322221000....
...00231222432132200...
..0041433223233211100..
..0232231612142618530..
.003152122326114121200.
.031252235216111132210.
.022211246332311115210.
00113232262121317213200
03152118212313211411110
03231234121132221411410
03513213411311414112320
00427534125412213211400
.013322444412122123210.
.015132331312411123120.
.003333612214233913300.
..0219126511415312570..
..0021321524341325100..
...00211415413523200...
....000122111322000....
......00001120000......
.........00000.........""".split("\n")
const
Width = Gmooh[0].len
Height = Gmooh.len
type
Pyx = tuple[y, x: int]
Route = tuple[cost, fromy, fromx: int]
Routes = seq[seq[Route]]
const D: array[8, Pyx] = [(-1, -1), (0, -1), (1, -1), (-1, 0), (1, 0), (-1, 1), (0, 1), (1, 1)]
const ZeroRoute: Route = (0, 0, 0)
var routes: Routes # Route for each Gmooh[][].
proc `$`(pyx: Pyx): string =
&"({pyx.y}, {pyx.x})"
proc `$`(pyxSeq: seq[Pyx]): string =
result = "["
for pyx in pyxSeq:
result.addSep(startLen = 2)
result.add $pyx
result.add ']'
func search(routes: var Routes; y, x: int) =
## Simple breadth-first search, populates "routes".
## This isn't strictly Dijkstra because graph edges are not weighted.
var x = x
var y = y
var cost = 0
routes = newSeqWith(Height, newSeq[Route](Width))
routes[y][x] = (0, y, x) # Zero-cost, the starting point.
var next: seq[Route]
while true:
var n = ord(Gmooh[y][x]) - ord('0')
for (dy, dx) in D:
let rx = x + n * dx
let ry = y + n * dy
if rx >= 0 and rx < Width and ry >= 0 and ry < Height and Gmooh[ry][rx] >= '0':
let ryx = routes[ry][rx]
if ryx == ZeroRoute or ryx.cost > cost + 1:
routes[ry][rx] = (cost + 1, y, x)
if Gmooh[ry][rx] > '0':
next.add (cost + 1, ry, rx)
# If the graph was weighted, at this point
# that would get shuffled up into place.
if next.len == 0: break
(cost, y, x) = next[0]
next.delete 0
func getRoute(routes: Routes; yx: Pyx): seq[Pyx] =
var (y, x) = yx
var cost: int
result = @[yx]
while true:
(cost, y, x) = routes[y][x]
if cost == 0: break
result.insert (y, x)
proc showShortest(routes: Routes) =
var shortest = 9999
var res: seq[Pyx]
for x in 0..<Width:
for y in 0..<Height:
if Gmooh[y][x] == '0':
let ryx = routes[y][x]
if ryx != ZeroRoute:
let cost = ryx.cost
if cost <= shortest:
if cost < shortest:
res.reset()
shortest = cost
res.add (y, x)
let (areis, s) = if res.len > 1: ("are", "s") else: ("is", "")
echo &"There {areis} {res.len} shortest route{s}] of {shortest} days to safety:"
for r in res:
echo routes.getRoute(r)
proc showUnreachable(routes: Routes) =
var res: seq[Pyx]
for x in 0..<Width:
for y in 0..<Height:
if Gmooh[y][x] >= '0' and routes[y][x] == ZeroRoute:
res.add (y, x)
echo "\nThe following cells are unreachable:"
echo res
proc showLongest(routes: Routes) =
var longest = 0
var res: seq[Pyx]
for x in 0..<Width:
for y in 0..<Height:
if Gmooh[y][x] >= '0':
var ryx = routes[y][x]
if ryx != ZeroRoute:
var rl = ryx.cost
if rl >= longest:
if rl > longest:
res.reset()
longest = rl
res.add (y, x)
echo &"\nThere are {res.len} cells that take {longest} days to send reinforcements to:"
for r in res:
echo routes.getRoute(r)
routes.search(11, 11)
routes.showShortest()
routes.search(21, 11)
echo "\nThe shortest route from [21,11] to [1,11]:"
echo routes.getRoute((1, 11))
routes.search(1, 11)
echo "\nThe shortest route from [1,11] to [21,11]:"
echo routes.getRoute((21, 11))
routes.search(11, 11)
routes.showUnreachable()
routes.showLongest()
</syntaxhighlight>
{{out}}
As Nim indexes are 0-based, output differs from Phix program output. It is similar to Go and Wren outputs.
<pre>There are 40 shortest routes] of 4 days to safety:
[(11, 11), (11, 12), (8, 9), (14, 3), (11, 0)]
[(11, 11), (10, 11), (7, 8), (7, 5), (12, 0)]
[(11, 11), (12, 10), (13, 10), (13, 5), (13, 0)]
[(11, 11), (11, 12), (8, 9), (8, 3), (6, 1)]
[(11, 11), (11, 12), (8, 9), (8, 3), (8, 1)]
[(11, 11), (10, 10), (8, 8), (12, 4), (9, 1)]
[(11, 11), (10, 10), (12, 8), (16, 4), (13, 1)]
[(11, 11), (10, 10), (8, 8), (12, 4), (15, 1)]
[(11, 11), (10, 10), (12, 8), (16, 4), (16, 1)]
[(11, 11), (10, 10), (8, 8), (8, 4), (6, 2)]
[(11, 11), (12, 11), (15, 8), (15, 5), (18, 2)]
[(11, 11), (11, 10), (10, 9), (9, 9), (3, 3)]
[(11, 11), (10, 11), (13, 8), (14, 7), (18, 3)]
[(11, 11), (10, 10), (8, 10), (5, 7), (2, 4)]
[(11, 11), (10, 11), (7, 8), (4, 5), (3, 4)]
[(11, 11), (10, 10), (12, 8), (16, 4), (19, 4)]
[(11, 11), (10, 11), (7, 8), (7, 5), (2, 5)]
[(11, 11), (10, 11), (7, 11), (7, 12), (1, 6)]
[(11, 11), (10, 10), (8, 8), (4, 8), (1, 8)]
[(11, 11), (10, 10), (8, 10), (5, 13), (1, 9)]
[(11, 11), (11, 12), (14, 9), (18, 13), (22, 9)]
[(11, 11), (12, 11), (15, 8), (18, 11), (22, 11)]
[(11, 11), (10, 10), (8, 12), (6, 12), (0, 12)]
[(11, 11), (10, 10), (8, 10), (5, 13), (1, 13)]
[(11, 11), (11, 12), (14, 9), (18, 13), (22, 13)]
[(11, 11), (10, 11), (7, 8), (4, 11), (1, 14)]
[(11, 11), (11, 12), (8, 9), (2, 15), (1, 15)]
[(11, 11), (12, 10), (13, 10), (18, 15), (21, 15)]
[(11, 11), (11, 12), (8, 9), (2, 15), (1, 16)]
[(11, 11), (11, 12), (8, 9), (2, 15), (2, 16)]
[(11, 11), (10, 10), (12, 8), (16, 12), (20, 16)]
[(11, 11), (12, 11), (12, 14), (8, 18), (3, 18)]
[(11, 11), (12, 11), (12, 14), (16, 18), (19, 18)]
[(11, 11), (12, 10), (13, 11), (17, 15), (20, 18)]
[(11, 11), (12, 11), (9, 14), (6, 17), (4, 19)]
[(11, 11), (10, 11), (10, 14), (12, 16), (16, 20)]
[(11, 11), (11, 12), (11, 15), (11, 17), (7, 21)]
[(11, 11), (12, 11), (12, 14), (16, 18), (13, 21)]
[(11, 11), (11, 12), (11, 15), (11, 17), (15, 21)]
[(11, 11), (12, 11), (12, 14), (16, 18), (16, 21)]
The shortest route from [21,11] to [1,11]:
[(21, 11), (20, 10), (19, 9), (18, 9), (13, 4), (6, 11), (4, 11), (1, 11)]
The shortest route from [1,11] to [21,11]:
[(1, 11), (2, 10), (5, 13), (9, 9), (15, 3), (20, 8), (20, 10), (21, 11)]
The following cells are unreachable:
[(4, 3), (2, 18), (18, 20)]
There are 5 cells that take 6 days to send reinforcements to:
[(11, 11), (10, 10), (12, 8), (16, 12), (20, 12), (21, 11), (22, 12)]
[(11, 11), (11, 12), (14, 15), (16, 17), (17, 16), (18, 16), (20, 14)]
[(11, 11), (12, 11), (9, 14), (6, 17), (4, 17), (3, 17), (3, 19)]
[(11, 11), (10, 11), (7, 11), (7, 12), (7, 18), (7, 20), (6, 20)]
[(11, 11), (10, 11), (10, 14), (12, 16), (12, 20), (15, 20), (17, 20)]
</pre>
Alternative using Floyd-Warshall for Part 2, and finding the longest shortest path between any two points.
<syntaxhighlight lang="Nim">import std/[sequtils, strformat, strutils]
const Gmooh = """
.........00000.........
......00003130000......
....000321322221000....
...00231222432132200...
..0041433223233211100..
..0232231612142618530..
.003152122326114121200.
.031252235216111132210.
.022211246332311115210.
00113232262121317213200
03152118212313211411110
03231234121132221411410
03513213411311414112320
00427534125412213211400
.013322444412122123210.
.015132331312411123120.
.003333612214233913300.
..0219126511415312570..
..0021321524341325100..
...00211415413523200...
....000122111322000....
......00001120000......
.........00000.........""".split("\n")
const
Width = Gmooh[0].len
Height = Gmooh.len
Infinity = int.high
None = -1
type
Pyx = tuple[y, x: int]
FloydWarshall = object
dist, next: seq[seq[int]]
pmap: seq[Pyx]
const D: array[8, Pyx] = [(-1, -1), (0, -1), (1, -1), (-1, 0), (1, 0), (-1, 1), (0, 1), (1, 1)]
proc `$`(pyx: Pyx): string =
&"({pyx.y}, {pyx.x})"
func fwPath(fw: FloydWarshall; u, v: int): string =
var u = u
if fw.next[u][v] != None:
var path = @[$fw.pmap[u]]
while u != v:
u = fw.next[u][v]
path.add $fw.pmap[u]
result = path.join(" → ")
proc showPath(fw: FloydWarshall; u, v: int) =
echo &"{fw.pmap[u]} → {fw.pmap[v]} {fw.dist[u][v]:>2} {fw.fwPath(u, v)}"
proc floydWarshall =
var fw: FloydWarshall
var point = 0
var weights: seq[Pyx]
var points = newSeqWith(Height, newSeq[int](Width))
# First, number the points...
for x in 0..<Width:
for y in 0..<Height:
if Gmooh[y][x] >= '0':
points[y][x] = point
inc point
fw.pmap.add (y, x)
# ...and then a set of edges (all of which have a "weight" of one day).
for x in 0..<Width:
for y in 0..<Height:
if Gmooh[y][x] > '0':
let n = ord(Gmooh[y][x]) - ord('0')
for (dy, dx) in D:
let rx = x + n * dx
let ry = y + n * dy
if rx >= 0 and rx < Width and ry >= 0 and ry < Height and Gmooh[ry][rx] >= '0':
weights.add (points[y][x], points[ry][rx])
# Before applying Floyd-Warshall.
let v = fw.pmap.len
fw.dist = newSeqWith(v, repeat(Infinity, v))
fw.next = newSeqWith(v, repeat(None, v))
for (u, v) in weights:
fw.dist[u][v] = 1 # The weight of the edge (u, v).
fw.next[u][v] = v
# Standard Floyd-Warshall implementation, with the optimization of avoiding
# processing of self/infs, which surprisingly makes quite a noticeable difference.
for k in 0..<v:
for i in 0..<v:
if i != k and fw.dist[i][k] != Infinity:
for j in 0..<v:
if j != i and j != k and fw.dist[k][j] != Infinity:
let d = fw.dist[i][k] + fw.dist[k][j]
if d < fw.dist[i][j]:
fw.dist[i][j] = d
fw.next[i][j] = fw.next[i][k]
fw.showPath(points[21][11], points[1][11])
fw.showPath(points[1][11], points[21][11])
var maxd = 0
var mi, mj: int
for i in 0..<v:
for j in 0..<v:
if j != i:
let d = fw.dist[i][j]
if d != Infinity and d > maxd:
maxd = d
mi = i
mj = j
echo "\nMaximum shortest distance:"
fw.showPath(mi, mj)
floydWarshall()
</syntaxhighlight>
{{out}}
<pre>(21, 11) → (1, 11) 7 (21, 11) → (20, 10) → (19, 10) → (14, 10) → (10, 10) → (8, 8) → (4, 8) → (1, 11)
(1, 11) → (21, 11) 7 (1, 11) → (2, 10) → (5, 13) → (9, 9) → (15, 3) → (20, 8) → (20, 10) → (21, 11)
Maximum shortest distance:
(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>
Line 1,441 ⟶ 2,003:
Initially, using a simple breadth-first search. Parts 1 and 2 and extra credit.
<syntaxhighlight lang="
import "./fmt" for Fmt
var gmooh = """
Line 1,674 ⟶ 2,236:
<br>
Alternative using Floyd-Warshall for Part 2, and finding the longest shortest path between any two points.
<syntaxhighlight lang="
var gmooh = """
| |||