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 21:42, 29 December 2018
, 5 years agoAdded Go
No edit summary |
(Added Go) |
||
Line 119:
(20, 10)->(19, 9)->(18, 9)->(13, 4)->(6, 11)->(4, 11)->(1, 11)
(2, 10)->(5, 13)->(9, 9)->(15, 3)->(20, 8)->(20, 10)->(21, 11)
</pre>
=={{header|Go}}==
{{trans|Phix}}
<br>
A more or less faithful translation though adjusted to Go's 0-based indices and the cell coordinates are therefore 1 less than the Phix results.
Initially, using a simple breadth-first search. Parts 1 and 2 and extra credit.
<lang go>package main
import (
"fmt"
"strings"
)
var gmooh = strings.Split(
`.........00000.........
......00003130000......
....000321322221000....
...00231222432132200...
..0041433223233211100..
..0232231612142618530..
.003152122326114121200.
.031252235216111132210.
.022211246332311115210.
00113232262121317213200
03152118212313211411110
03231234121132221411410
03513213411311414112320
00427534125412213211400
.013322444412122123210.
.015132331312411123120.
.003333612214233913300.
..0219126511415312570..
..0021321524341325100..
...00211415413523200...
....000122111322000....
......00001120000......
.........00000.........`, "\n")
var width, height = len(gmooh[0]), len(gmooh)
type pyx [2]int // {y, x}
var d = []pyx{{-1, -1}, {0, -1}, {1, -1}, {-1, 0}, {1, 0}, {-1, 1}, {0, 1}, {1, 1}}
type route [3]int // {cost, fromy, fromx}
var zeroRoute = route{0, 0, 0}
var routes [][]route // route for each gmooh[][]
func (p pyx) destruct() (int, int) {
return p[0], p[1]
}
func (r route) destruct() (int, int, int) {
return r[0], r[1], r[2]
}
func search(y, x int) {
// Simple breadth-first search, populates routes.
// This isn't strictly Dijkstra because graph edges are not weighted.
cost := 0
routes = make([][]route, height)
for i := 0; i < width; i++ {
routes[i] = make([]route, width)
}
routes[y][x] = route{0, y, x} // zero-cost, the starting point
var next []route
for {
n := int(gmooh[y][x] - '0')
for di := 0; di < len(d); di++ {
dx, dy := d[di].destruct()
rx, ry := x+n*dx, y+n*dy
if rx >= 0 && rx < width && ry >= 0 && ry < height && gmooh[rx][ry] >= '0' {
ryx := routes[ry][rx]
if ryx == zeroRoute || ryx[0] > cost+1 {
routes[ry][rx] = route{cost + 1, y, x}
if gmooh[ry][rx] > '0' {
next = append(next, route{cost + 1, ry, rx})
// If the graph was weighted, at this point
// that would get shuffled up into place.
}
}
}
}
if len(next) == 0 {
break
}
cost, y, x = next[0].destruct()
next = next[1:]
}
}
func getRoute(y, x int) []pyx {
cost := 0
res := []pyx{{y, x}}
for {
cost, y, x = routes[y][x].destruct()
if cost == 0 {
break
}
res = append(res, pyx{0, 0})
copy(res[1:], res[0:])
res[0] = pyx{y, x}
}
return res
}
func showShortest() {
shortest := 9999
var res []pyx
for x := 0; x < width; x++ {
for y := 0; y < height; y++ {
if gmooh[y][x] == '0' {
ryx := routes[y][x]
if ryx != zeroRoute {
cost := ryx[0]
if cost <= shortest {
if cost < shortest {
res = res[:0]
shortest = cost
}
res = append(res, pyx{y, x})
}
}
}
}
}
areis, s := "is", ""
if len(res) > 1 {
areis = "are"
s = "s"
}
fmt.Printf("There %s %d shortest route%s of %d days to safety:\n", areis, len(res), s, shortest)
for _, r := range res {
fmt.Println(getRoute(r[0], r[1]))
}
}
func showUnreachable() {
var res []pyx
for x := 0; x < width; x++ {
for y := 0; y < height; y++ {
if gmooh[y][x] >= '0' && routes[y][x] == zeroRoute {
res = append(res, pyx{y, x})
}
}
}
fmt.Println("\nThe following cells are unreachable:")
fmt.Println(res)
}
func showLongest() {
longest := 0
var res []pyx
for x := 0; x < width; x++ {
for y := 0; y < height; y++ {
if gmooh[y][x] >= '0' {
ryx := routes[y][x]
if ryx != zeroRoute {
rl := ryx[0]
if rl >= longest {
if rl > longest {
res = res[:0]
longest = rl
}
res = append(res, pyx{y, x})
}
}
}
}
}
fmt.Printf("\nThere are %d cells that take %d days to send reinforcements to:\n", len(res), longest)
for _, r := range res {
fmt.Println(getRoute(r[0], r[1]))
}
}
func main() {
search(11, 11)
showShortest()
search(21, 11)
fmt.Println("\nThe shortest route from {21,11} to {1,11}:")
fmt.Println(getRoute(1, 11))
search(1, 11)
fmt.Println("\nThe shortest route from {1,11} to {21,11}:")
fmt.Println(getRoute(21, 11))
search(11, 11)
showUnreachable()
showLongest()
}</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>
Alternative using Floyd-Warshall for Part 2, and finding the longest shortest path between any two points.
<lang go>package main
import (
"fmt"
"math"
"strings"
)
var gmooh = strings.Split(
`.........00000.........
......00003130000......
....000321322221000....
...00231222432132200...
..0041433223233211100..
..0232231612142618530..
.003152122326114121200.
.031252235216111132210.
.022211246332311115210.
00113232262121317213200
03152118212313211411110
03231234121132221411410
03513213411311414112320
00427534125412213211400
.013322444412122123210.
.015132331312411123120.
.003333612214233913300.
..0219126511415312570..
..0021321524341325100..
...00211415413523200...
....000122111322000....
......00001120000......
.........00000.........`, "\n")
var width, height = len(gmooh[0]), len(gmooh)
type pyx [2]int // {y, x}
var d = []pyx{{-1, -1}, {0, -1}, {1, -1}, {-1, 0}, {1, 0}, {-1, 1}, {0, 1}, {1, 1}}
var dist, next [][]int
var pmap []pyx
const (
max = math.MaxInt32
min = -1
)
func (p pyx) destruct() (int, int) {
return p[0], p[1]
}
func fwPath(u, v int) string {
res := ""
if next[u][v] != min {
path := []string{fmt.Sprintf("%v", pmap[u])}
for u != v {
u = next[u][v]
path = append(path, fmt.Sprintf("%v", pmap[u]))
}
res = strings.Join(path, "->")
}
return res
}
func showFwPath(u, v int) {
fmt.Printf("%v->%v %2d %s\n", pmap[u], pmap[v], dist[u][v], fwPath(u, v))
}
func floydWarshall() {
point := 0
var weights []pyx
points := make([][]int, height)
for i := 0; i < width; i++ {
points[i] = make([]int, width)
}
// First number the points.
for x := 0; x < width; x++ {
for y := 0; y < height; y++ {
if gmooh[y][x] >= '0' {
points[y][x] = point
point++
pmap = append(pmap, pyx{y, x})
}
}
}
// ...and then a set of edges (all of which have a "weight" of 1 day)
for x := 0; x < width; x++ {
for y := 0; y < height; y++ {
if gmooh[y][x] > '0' {
n := int(gmooh[y][x] - '0')
for di := 0; di < len(d); di++ {
dx, dy := d[di].destruct()
rx, ry := x+n*dx, y+n*dy
if rx >= 0 && rx < width && ry >= 0 && ry < height && gmooh[rx][ry] >= '0' {
weights = append(weights, pyx{points[y][x], points[ry][rx]})
}
}
}
}
}
// Before applying Floyd-Warshall.
vv := len(pmap)
dist = make([][]int, vv)
next = make([][]int, vv)
for i := 0; i < vv; i++ {
dist[i] = make([]int, vv)
next[i] = make([]int, vv)
for j := 0; j < vv; j++ {
dist[i][j] = max
next[i][j] = min
}
}
for k := 0; k < len(weights); k++ {
u, v := weights[k].destruct()
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 := 0; k < vv; k++ {
for i := 0; i < vv; i++ {
if i != k && dist[i][k] != max {
for j := 0; j < vv; j++ {
if j != i && j != k && dist[k][j] != max {
dd := dist[i][k] + dist[k][j]
if dd < dist[i][j] {
dist[i][j] = dd
next[i][j] = next[i][k]
}
}
}
}
}
}
showFwPath(points[21][11], points[1][11])
showFwPath(points[1][11], points[21][11])
var maxd, mi, mj int
for i := 0; i < vv; i++ {
for j := 0; j < vv; j++ {
if j != i {
dd := dist[i][j]
if dd != max && dd > maxd {
maxd, mi, mj = dd, i, j
}
}
}
}
fmt.Println("\nMaximum shortest distance:")
showFwPath(mi, mj)
}
func main() {
floydWarshall()
}</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>
| |||