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
(Promoted to full task) |
m (→{{header|Wren}}: Minor tidy) |
||
| (2 intermediate revisions by 2 users not shown) | |||
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 997 ⟶ 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,661 ⟶ 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,894 ⟶ 2,236:
<br>
Alternative using Floyd-Warshall for Part 2, and finding the longest shortest path between any two points.
<syntaxhighlight lang="
var gmooh = """
| |||