I'm a software engineer, get me out of here: Difference between revisions
Content added Content deleted
(Promoted to full task) |
(Created Nim version.) |
||
Line 997: | Line 997: | ||
(11, 11) (11, 12) (14, 15) (16, 17) (17, 16) (18, 16) (20, 14) |
(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) |
(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> |
</pre> |
||