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:25, 26 May 2021
, 3 years agoAdded Wren
m (→{{header|Phix}}: added syntax colouring the hard way) |
(Added Wren) |
||
Line 1,433:
(11,11) (11,12) (14,15) (16,17) (17,16) (18,16) (20,14)
(11,11) (12,11) (9,14) (6,17) (4,17) (4,18) (3,19)</pre>
=={{header|Wren}}==
{{trans|Phix}}
{{libheader|Wren-dynamic}}
{{libheader|Wren-fmt}}
Translated via the Go entry which, like Wren, uses 0-based indices. The cell coordinates are therefore 1 less than Phix.
Initially, using a simple breadth-first search. Parts 1 and 2 and extra credit.
<lang ecmascript>import "/dynamic" for Struct
import "/fmt" for Fmt
var 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")
var width = gmooh[0].count
var height = gmooh.count
var d = [[-1, -1], [0, -1], [1, -1], [-1, 0], [1, 0], [-1, 1], [0, 1], [1, 1]]
var Route = Struct.create("Route", ["cost", "fromy", "fromx"])
var zeroRoute = Route.new(0, 0, 0)
var routes = [] // route for each gmooh[][]
var equalRoutes = Fn.new { |r1, r2| r1.cost == r2.cost && r1.fromy == r2.fromy && r1.fromx == r2.fromx }
var search = Fn.new { |y, x|
// Simple breadth-first search, populates routes.
// This isn't strictly Dijkstra because graph edges are not weighted.
var cost = 0
routes = List.filled(height, null)
for (i in 0...height) {
routes[i] = List.filled(width, null)
for (j in 0...width) routes[i][j] = Route.new(0, 0, 0)
}
routes[y][x] = Route.new(0, y, x) // zero-cost, the starting point
var next = []
while (true) {
var n = gmooh[y][x].bytes[0] - 48
for (di in 0...d.count) {
var dx = d[di][0]
var dy = d[di][1]
var rx = x + n * dx
var ry = y + n * dy
if (rx >= 0 && rx < width && ry >= 0 && ry < height && gmooh[rx][ry].bytes[0] >= 48) {
var ryx = routes[ry][rx]
if (equalRoutes.call(ryx, zeroRoute) || ryx.cost > cost+1) {
routes[ry][rx] = Route.new(cost + 1, y, x)
if (gmooh[ry][rx].bytes[0] > 48) {
next.add(Route.new(cost + 1, ry, rx))
// If the graph was weighted, at this point
// that would get shuffled up into place.
}
}
}
}
if (next.count == 0) break
cost = next[0].cost
y = next[0].fromy
x = next[0].fromx
next.removeAt(0)
}
}
var getRoute = Fn.new { |y, x|
var cost = 0
var res = [[y, x]]
while(true) {
cost = routes[y][x].cost
var oldy = y
y = routes[y][x].fromy
x = routes[oldy][x].fromx
if (cost == 0) break
res.insert(0, [y, x])
}
return res
}
var showShortest = Fn.new {
var shortest = 9999
var res = []
for (x in 0...width) {
for (y in 0...height) {
if (gmooh[y][x] == "0") {
var ryx = routes[y][x]
if (!equalRoutes.call(ryx, zeroRoute)) {
var cost = ryx.cost
if (cost <= shortest) {
if (cost < shortest) {
res.clear()
shortest = cost
}
res.add([y, x])
}
}
}
}
}
var areis = (res.count > 1) ? "are" :"is"
var s = (res.count > 1) ? "s" : ""
Fmt.print("There $s $d shortest route$s of $d days to safety:", areis, res.count, s, shortest)
for (r in res) System.print(getRoute.call(r[0], r[1]))
}
var showUnreachable = Fn.new {
var res = []
for (x in 0...width) {
for (y in 0...height) {
if (gmooh[y][x].bytes[0] >= 48 && equalRoutes.call(routes[y][x], zeroRoute)) {
res.add([y, x])
}
}
}
System.print("\nThe following cells are unreachable:")
System.print(res)
}
var showLongest = Fn.new {
var longest = 0
var res = []
for (x in 0...width) {
for (y in 0...height) {
if (gmooh[y][x].bytes[0] >= 48) {
var ryx = routes[y][x]
if (!equalRoutes.call(ryx, zeroRoute)) {
var rl = ryx.cost
if (rl >= longest) {
if (rl > longest) {
res.clear()
longest = rl
}
res.add([y, x])
}
}
}
}
}
Fmt.print("\nThere are $d cells that take $d days to send reinforcements to:\n", res.count, longest)
for (r in res) System.print(getRoute.call(r[0], r[1]))
}
search.call(11, 11)
showShortest.call()
search.call(21, 11)
System.print("\nThe shortest route from [21,11] to [1,11]:")
System.print(getRoute.call(1, 11))
search.call(1, 11)
System.print("\nThe shortest route from [1,11] to [21,11]:")
System.print(getRoute.call(21, 11))
search.call(11, 11)
showUnreachable.call()
showLongest.call()</lang>
{{out}}
<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], [11, 12], [14, 15], [16, 15], [19, 18]]
[[11, 11], [10, 11], [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>
<br>
Alternative using Floyd-Warshall for Part 2, and finding the longest shortest path between any two points.
<lang ecmascript>import "/fmt" for Fmt
var 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")
var width = gmooh[0].count
var height = gmooh.count
var d = [[-1, -1], [0, -1], [1, -1], [-1, 0], [1, 0], [-1, 1], [0, 1], [1, 1]]
var dist = []
var next = []
var pmap = []
var max = 2147483647
var min = -1
var fwPath = Fn.new { |u, v|
var res = ""
if (next[u][v] != min) {
var path = [pmap[u].toString]
while (u != v) {
u = next[u][v]
path.add(pmap[u].toString)
}
res = path.join("->")
}
return res
}
var showFwPath = Fn.new { |u, v|
Fmt.print("$n->$n $2d $s", pmap[u], pmap[v], dist[u][v], fwPath.call(u, v))
}
var floydWarshall = Fn.new {
var point = 0
var weights = []
var points = List.filled(height, null)
for (i in 0...height) points[i] = List.filled(width, 0)
// First number the points.
for (x in 0...width) {
for (y in 0...width) {
if (gmooh[y][x].bytes[0] >= 48) {
points[y][x] = point
point = point + 1
pmap.add([y, x])
}
}
}
// ...and then a set of edges (all of which have a "weight" of 1 day)
for (x in 0...width) {
for (y in 0...height) {
if (gmooh[y][x].bytes[0] > 48) {
var n = gmooh[y][x].bytes[0] - 48
for (di in 0...d.count) {
var dx = d[di][0]
var dy = d[di][1]
var rx = x + n * dx
var ry = y + n * dy
if (rx >= 0 && rx < width && ry >= 0 && ry < height && gmooh[rx][ry].bytes[0] >= 48) {
weights.add([points[y][x], points[ry][rx]])
}
}
}
}
}
// Before applying Floyd-Warshall.
var vv = pmap.count
dist = List.filled(vv, null)
next = List.filled(vv, null)
for (i in 0...vv) {
dist[i] = List.filled(vv, 0)
next[i] = List.filled(vv, 0)
for (j in 0...vv) {
dist[i][j] = max
next[i][j] = min
}
}
for (k in 0...weights.count) {
var u = weights[k][0]
var v = weights[k][1]
dist[u][v] = 1 // the weight of the edge (u,v)
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...vv) {
for (i in 0...vv) {
if (i != k && dist[i][k] != max) {
for (j in 0...vv) {
if (j != i && j != k && dist[k][j] != max) {
var dd = dist[i][k] + dist[k][j]
if (dd < dist[i][j]) {
dist[i][j] = dd
next[i][j] = next[i][k]
}
}
}
}
}
}
showFwPath.call(points[21][11], points[1][11])
showFwPath.call(points[1][11], points[21][11])
var maxd = 0
var mi = 0
var mj = 0
for (i in 0...vv) {
for (j in 0...vv) {
if (j != i) {
var dd = dist[i][j]
if (dd != max && dd > maxd) {
maxd = dd
mi = i
mj = j
}
}
}
}
System.print("\nMaximum shortest distance:")
showFwPath.call(mi, mj)
}
floydWarshall.call()</lang>
{{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>
| |||