I'm a software engineer, get me out of here
You are encouraged to solve this task according to the task description, using any language you may know.
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.
00000
00003130000
000321322221000
00231222432132200
0041433223233211100
0232231612142618530
003152122326114121200
031252235216111132210
022211246332311115210
00113232262121317213200
03152118212313211411110
03231234121132221411410
03513213411311414112320
00427534125412213211400
013322444412122123210
015132331312411123120
003333612214233913300
0219126511415312570
0021321524341325100
00211415413523200
000122111322000
00001120000
00000
Part 1 Use Dijkstra's algorithm to find a list of the shortest routes from HQ to safety.
Part 2
Six days later and you are called to another briefing. The good news is The President and his gold are safe, so your invoice may be paid if you can get out of here. To do this a number of troop repositions will be required. It is concluded that you need to know the shortest route from each cell to every other cell. You decide to use Floyd's algorithm. Print the shortest route from (21,11) to (1,11) and from (1,11) to (21,11), and the longest shortest route between any two points.
Extra Credit
- Is there any cell in the country that can not be reached from HQ?
- Which cells will it take longest to send reinforcements to from HQ?
Related tasks:
- See also
C++
#include <cstdint>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
const std::string gmooh = R"(
.........00000.........
......00003130000......
....000321322221000....
...00231222432132200...
..0041433223233211100..
..0232231612142618530..
.003152122326114121200.
.031252235216111132210.
.022211246332311115210.
00113232262121317213200
03152118212313211411110
03231234121132221411410
03513213411311414112320
00427534125412213211400
.013322444412122123210.
.015132331312411123120.
.003333612214233913300.
..0219126511415312570..
..0021321524341325100..
...00211415413523200...
....000122111322000....
......00001120000......
.........00000.........)";
std::vector<std::string> split_string(const std::string& text, const char& delimiter) {
std::vector<std::string> lines;
std::istringstream stream(text);
std::string line;
while ( std::getline(stream, line, delimiter) ) {
if ( ! line.empty() ) {
lines.emplace_back(line);
}
}
return lines;
}
const std::vector<std::string> GMOOH = split_string(gmooh, '\n');
const int32_t WIDTH = GMOOH[0].length();
const int32_t HEIGHT = GMOOH.size();
class Cell {
public:
Cell(const int32_t& aRow, const int32_t& aCol) : row(aRow), col(aCol) { }
std::string to_string() const {
return "(" + std::to_string(row) + ", " + std::to_string(col) + ")";
}
int32_t row, col;
};
class Cell_With_Cost {
public:
Cell_With_Cost(const int32_t& aFrom_Row, const int32_t& aFrom_Col, const int32_t& aCost)
: from_row(aFrom_Row), from_col(aFrom_Col), cost(aCost) { }
std::string to_string() const {
return "(" + std::to_string(from_row) + ", " + std::to_string(from_col) + " : " + std::to_string(cost) + ")";
}
bool operator==(const Cell_With_Cost& other) const {
return cost == other.cost && from_row == other.from_row && from_col == other.from_col;
}
int32_t from_row, from_col, cost;
};
const Cell_With_Cost ZERO_CELL_WITH_COST = Cell_With_Cost(0, 0, 0);
const std::vector<Cell> directions = { Cell(1, -1), Cell(1, 0), Cell(1, 1),
Cell(0, -1), Cell(0, 1),
Cell(-1, -1), Cell(-1, 0), Cell(-1, 1) };
std::vector<std::vector<Cell_With_Cost>> routes = { };
void print_vector(const std::vector<Cell>& cells) {
std::cout << "[";
for ( uint64_t i = 0; i < cells.size() - 1; ++i ) {
std::cout << cells[i].to_string() << ", ";
}
std::cout << cells.back().to_string() << "]" << std::endl;
}
std::vector<Cell> create_route_to_cell(int32_t row, int32_t col) {
std::vector<Cell> route = { };
route.emplace_back(Cell(row, col));
while ( true ) {
Cell_With_Cost current_cell = routes[row][col];
if ( current_cell.cost == 0 ) {
break;
}
row = current_cell.from_row;
col = current_cell.from_col;
route.insert(route.begin(), Cell(row, col));
}
return route;
}
void show_cells_with_longest_route_from_HQ() {
int32_t maximum_cost = INT_MIN;
std::vector<Cell> cells = { };
for ( int32_t col = 0; col < WIDTH; ++col ) {
for ( int32_t row = 0; row < HEIGHT; ++row ) {
if ( GMOOH[row][col] >= '0' ) {
Cell_With_Cost current_cell = routes[row][col];
if ( ! ( current_cell == ZERO_CELL_WITH_COST ) ) {
const int32_t cost = current_cell.cost;
if ( cost >= maximum_cost) {
if ( cost > maximum_cost ) {
cells.clear();
maximum_cost = cost;
}
cells.emplace_back(Cell(row, col));
}
}
}
}
}
std::cout << "There are " << cells.size() << " cells that require " << maximum_cost
<< " days to receive reinforcements from HQ:" << std::endl;
for ( const Cell& cell : cells ) {
print_vector(create_route_to_cell(cell.row, cell.col));
}
}
void show_unreachable_cells() {
std::vector<Cell> unreachableCells = { };
for ( int32_t col = 0; col < WIDTH; ++col ) {
for ( int32_t row = 0; row < HEIGHT; ++row ) {
if ( GMOOH[row][col] >= '0' && routes[row][col] == ZERO_CELL_WITH_COST ) {
unreachableCells.emplace_back(Cell(row, col));
}
}
}
std::cout << "The following cells are unreachable:" << std::endl;
print_vector(unreachableCells);
}
void search_from_cell(int32_t row, int32_t col) {
routes = { static_cast<uint64_t>(HEIGHT), std::vector<Cell_With_Cost>(WIDTH, ZERO_CELL_WITH_COST) };
routes[row][col] = Cell_With_Cost(row, col, 0);
std::vector<Cell_With_Cost> route = { };
int32_t cost = 0;
while ( true ) {
const int32_t start_digit = GMOOH[row][col] - '0';
for ( Cell direction : directions ) {
const int32_t next_row = row + start_digit * direction.row;
const int32_t next_col = col + start_digit * direction.col;
if ( next_col >= 0 && next_col < WIDTH && next_row >= 0 && next_row < HEIGHT
&& GMOOH[next_row][next_col] >= '0' ) {
Cell_With_Cost current_cell = routes[next_row][next_col];
if ( current_cell == ZERO_CELL_WITH_COST || current_cell.cost > cost + 1 ) {
routes[next_row][next_col] = Cell_With_Cost(row, col, cost + 1);
if ( GMOOH[next_row][next_col] > '0' ) {
route.emplace_back(Cell_With_Cost(next_row, next_col, cost + 1));
}
}
}
}
if ( route.empty() ) { // All routes have been searched
break;
}
Cell_With_Cost next_cell = route.front();
route.erase(route.begin());
row = next_cell.from_row;
col = next_cell.from_col;
cost = next_cell.cost;
}
}
void show_shortest_routes_to_safety() {
int32_t minimum_cost = INT_MAX;
std::vector<Cell> route = { };
for ( int32_t col = 0; col < WIDTH; ++col ) {
for ( int32_t row = 0; row < HEIGHT; ++row ) {
if ( GMOOH[row][col] == '0' ) {
Cell_With_Cost current_cell = routes[row][col];
if ( ! ( current_cell == ZERO_CELL_WITH_COST ) ) {
const int32_t cost = current_cell.cost;
if ( cost <= minimum_cost ) {
if ( cost < minimum_cost ) {
route.clear();
minimum_cost = cost;
}
route.emplace_back(Cell(row, col));
}
}
}
}
}
const std::string are_is = ( route.size() > 1 ) ? "are " : "is ";
const std::string plural = ( route.size() > 1 ) ? "s" : "";
std::cout << "There " << are_is << route.size() << " shortest route" << plural
<< " of " << minimum_cost << " days to safety:" << std::endl;
for ( const Cell& cell : route ) {
print_vector(create_route_to_cell(cell.row, cell.col));
}
}
int main() {
search_from_cell(11, 11);
show_shortest_routes_to_safety();
std::cout << std::endl;
search_from_cell(21, 11);
std::cout << "The shortest route from (21, 11) to (1, 11):" << std::endl;
print_vector((create_route_to_cell(1, 11)));
std::cout << std::endl;
search_from_cell(1, 11);
std::cout << "The shortest route from (1, 11) to (21, 11):" << std::endl;
print_vector((create_route_to_cell(21, 11)));
std::cout << std::endl;
search_from_cell(11, 11);
show_unreachable_cells();
std::cout << std::endl;
show_cells_with_longest_route_from_HQ();
}
- Output:
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), (12, 11), (12, 8), (12, 4), (9, 1)] [(11, 11), (12, 11), (12, 8), (16, 4), (13, 1)] [(11, 11), (12, 11), (12, 8), (12, 4), (15, 1)] [(11, 11), (12, 11), (12, 8), (16, 4), (16, 1)] [(11, 11), (12, 11), (12, 8), (8, 4), (6, 2)] [(11, 11), (12, 11), (15, 8), (15, 5), (18, 2)] [(11, 11), (12, 10), (11, 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), (12, 10), (13, 10), (18, 5), (19, 4)] [(11, 11), (10, 11), (7, 8), (7, 5), (2, 5)] [(11, 11), (10, 11), (7, 11), (7, 12), (1, 6)] [(11, 11), (11, 12), (8, 9), (2, 9), (1, 8)] [(11, 11), (11, 12), (8, 9), (2, 9), (1, 9)] [(11, 11), (11, 12), (14, 9), (18, 13), (22, 9)] [(11, 11), (12, 11), (15, 8), (18, 11), (22, 11)] [(11, 11), (11, 12), (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), (11, 12), (8, 9), (2, 15), (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), (12, 11), (15, 11), (16, 12), (20, 16)] [(11, 11), (12, 11), (12, 14), (8, 18), (3, 18)] [(11, 11), (12, 11), (15, 14), (16, 15), (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), (21, 10), (20, 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 require 6 days to receive reinforcements from HQ: [(11, 11), (12, 10), (13, 10), (18, 10), (20, 10), (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), (4, 18), (3, 19)] [(11, 11), (12, 11), (9, 14), (9, 17), (7, 17), (7, 20), (6, 20)] [(11, 11), (12, 11), (12, 14), (12, 18), (13, 19), (13, 20), (17, 20)]
F#
This task uses Dijkstra's algorithm (F#)
This task uses readCSV (F#)
Part 1
let safety=readCSV '\t' "gmooh.dat"|>Seq.choose(fun n->if n.value="0" then Some (n.row,n.col) else None)
let board=readCSV '\t' "gmooh.dat"|>Seq.choose(fun n->match n.value with |"0"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9" as g->Some((n.row,n.col),int g)|_->None)|>Map.ofSeq
let adjacent((n,g),v)=List.choose(fun y->if y=(n,g) then None else match Map.tryFind y board with |None->None|_->Some ((y),1)) [(n+v,g);(n-v,g);(n,g+v);(n,g-v);(n+v,g+v);(n+v,g-v);(n-v,g+v);(n-v,g-v);]
let adjacencyList=new System.Collections.Generic.Dictionary<(int*int),list<(int*int)*int>>()
let rec mkAdj start=
let n=((start),Map.find start board)
let g=adjacent n
adjacencyList.Add((fst n),g)
List.iter(fun ((n),_)->if (not (adjacencyList.ContainsKey n )) then mkAdj n) g
mkAdj (11,11)
let nodes=adjacencyList.Keys |> List.ofSeq
let G=nodes |>List.collect(fun n->List.map(fun (n',g)->(((n),(n')),g))(adjacencyList.Item n))|>Map.ofList
let paths=Dijkstra nodes G (11,11)
let _,res=safety|>Seq.choose(fun n->paths n) |> Seq.groupBy(fun n->List.length n)|>Seq.minBy fst
res |> Seq.iter (printfn "%A")
- Output:
[(11, 11); (10, 11); (7, 11); (6, 12); (0, 12)] [(11, 11); (10, 11); (7, 11); (7, 12); (1, 6)] [(11, 11); (10, 10); (8, 8); (4, 8); (1, 8)] [(11, 11); (11, 12); (8, 9); (2, 9); (1, 9)] [(11, 11); (10, 10); (8, 10); (5, 13); (1, 13)] [(11, 11); (10, 11); (7, 8); (4, 11); (1, 14)] [(11, 11); (11, 12); (8, 9); (2, 15); (1, 15)] [(11, 11); (11, 12); (8, 9); (2, 15); (1, 16)] [(11, 11); (10, 10); (8, 10); (5, 7); (2, 4)] [(11, 11); (10, 11); (7, 8); (7, 5); (2, 5)] [(11, 11); (11, 12); (8, 15); (9, 16); (2, 16)] [(11, 11); (12, 10); (11, 9); (9, 9); (3, 3)] [(11, 11); (10, 11); (7, 8); (4, 5); (3, 4)] [(11, 11); (12, 11); (12, 14); (8, 18); (3, 18)] [(11, 11); (12, 11); (9, 14); (6, 17); (4, 19)] [(11, 11); (11, 12); (8, 9); (8, 3); (6, 1)] [(11, 11); (12, 11); (12, 8); (8, 4); (6, 2)] [(11, 11); (11, 12); (11, 15); (11, 17); (7, 21)] [(11, 11); (11, 12); (8, 9); (8, 3); (8, 1)] [(11, 11); (12, 11); (12, 8); (12, 4); (9, 1)] [(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); (12, 11); (12, 8); (16, 4); (13, 1)] [(11, 11); (12, 11); (12, 14); (16, 18); (13, 21)] [(11, 11); (12, 11); (12, 8); (12, 4); (15, 1)] [(11, 11); (11, 12); (11, 15); (11, 17); (15, 21)] [(11, 11); (12, 11); (12, 8); (16, 4); (16, 1)] [(11, 11); (10, 11); (10, 14); (12, 16); (16, 20)] [(11, 11); (12, 11); (12, 14); (16, 18); (16, 21)] [(11, 11); (12, 11); (15, 8); (15, 5); (18, 2)] [(11, 11); (10, 11); (13, 8); (14, 7); (18, 3)] [(11, 11); (12, 11); (15, 8); (18, 5); (19, 4)] [(11, 11); (11, 12); (14, 15); (16, 15); (19, 18)] [(11, 11); (12, 11); (15, 11); (16, 12); (20, 16)] [(11, 11); (10, 11); (13, 11); (17, 15); (20, 18)] [(11, 11); (12, 10); (13, 10); (18, 15); (21, 15)] [(11, 11); (11, 12); (14, 9); (18, 13); (22, 9)] [(11, 11); (12, 11); (15, 8); (18, 11); (22, 11)] [(11, 11); (11, 12); (14, 9); (18, 13); (22, 13)]
Part 2
This task uses Floyd-Warshall algorithm#F.23
let board=readCSV '\t' "gmooh.dat"|>Seq.choose(fun n->match n.value with |"0"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9" as g->Some((n.row,n.col),int g)|_->None)|>Map.ofSeq
let nodes=board|>Seq.map(fun n->n.Key)|>Set.ofSeq
let adjacent (n,g) v=List.choose(fun y->if y=(n,g) then None else match Set.contains y nodes with |true->Some ((y),1)|_->None) [(n+v,g);(n-v,g);(n,g+v);(n,g-v);(n+v,g+v);(n+v,g-v);(n-v,g+v);(n-v,g-v);]
let adjacencyList=board |>Seq.collect (fun n->Seq.map(fun ((n'),g')->((n.Key,n'),g'))(adjacent n.Key n.Value))|> Map.ofSeq
let _,paths=Floyd (nodes|>Set.toArray) adjacencyList
paths (21,11) (1,11) |>Seq.iteri(fun n g->if n>0 then printf "->"; printf "%A" g else printf "%A" g) ; printfn ""
paths (1,11) (21,11) |>Seq.iteri(fun n g->if n>0 then printf "->"; printf "%A" g else printf "%A" g) ; printfn ""
- Output:
(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)
Go
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.
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()
}
- Output:
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]]
Alternative using Floyd-Warshall for Part 2, and finding the longest shortest path between any two points.
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()
}
- Output:
[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]
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:
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 }}
And here's what that gives us:
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
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.
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
}}
And the task examples:
#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
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:
#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
(Other than this sample, all J presentation here assumes row number before column number.)
J Extra Credit
Our map 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 M 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).)
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
Java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public final class ImASoftwareEngineerGetMeOutOfHere {
public static void main(String[] args) {
searchFromCell(11, 11);
showShortestRoutesToSafety();
System.out.println();
searchFromCell(21, 11);
System.out.println("The shortest route from (21, 11) to (1, 11):");
System.out.println(createRouteToCell(1, 11));
System.out.println();
searchFromCell(1, 11);
System.out.println("The shortest route from (1, 11) to (21, 11):");
System.out.println(createRouteToCell(21, 11));
System.out.println();
searchFromCell(11, 11);
showUnreachableCells();
System.out.println();
showCellsWithLongestRouteFromHQ();
}
private static void searchFromCell(int row, int col) {
routes = IntStream.range(0, HEIGHT).boxed()
.map( i -> new ArrayList<CellWithCost>(Collections.nCopies(WIDTH, CellWithCost.ZERO)) )
.collect(Collectors.toList());
routes.get(row).set(col, new CellWithCost(row, col, 0));
List<CellWithCost> route = new ArrayList<CellWithCost>();
int cost = 0;
while ( true ) {
final int startDigit = Character.digit(GMOOH[row].charAt(col), 10);
for ( Cell direction : directions ) {
final int nextRow = row + startDigit * direction.row;
final int nextCol = col + startDigit * direction.col;
if ( nextCol >= 0 && nextCol < WIDTH && nextRow >= 0 && nextRow < HEIGHT
&& Character.digit(GMOOH[nextRow].charAt(nextCol), 10) >= 0 ) {
CellWithCost currentCell = routes.get(nextRow).get(nextCol);
if ( currentCell.equals(CellWithCost.ZERO) || currentCell.cost > cost + 1 ) {
routes.get(nextRow).set(nextCol, new CellWithCost(row, col, cost + 1));
if ( Character.digit(GMOOH[nextRow].charAt(nextCol), 10) > 0 ) {
route.addLast( new CellWithCost(nextRow, nextCol, cost + 1) );
}
}
}
}
if ( route.isEmpty() ) { // All routes have been searched
break;
}
CellWithCost nextCell = route.removeFirst();
row = nextCell.fromRow;
col = nextCell.fromCol;
cost = nextCell.cost;
}
}
private static void showShortestRoutesToSafety() {
int minimumCost = Integer.MAX_VALUE;
List<Cell> cells = new ArrayList<Cell>();
for ( int col = 0; col < WIDTH; col++ ) {
for ( int row = 0; row < HEIGHT; row++ ) {
if ( Character.digit(GMOOH[row].charAt(col), 10) == 0 ) {
CellWithCost currentCell = routes.get(row).get(col);
if ( ! currentCell.equals(CellWithCost.ZERO) ) {
final int cost = currentCell.cost;
if ( cost <= minimumCost ) {
if ( cost < minimumCost ) {
cells.clear();
minimumCost = cost;
}
cells.addLast( new Cell(row, col) );
}
}
}
}
}
String areIs = ( cells.size() > 1 ) ? "are " : "is ";
String plural = ( cells.size() > 1 ) ? "s" : "";
System.out.println("There " + areIs + cells.size() + " shortest route" + plural
+ " of " + minimumCost + " days to safety:");
for ( Cell cell : cells ) {
System.out.println(createRouteToCell(cell.row, cell.col));
}
}
private static List<Cell> createRouteToCell(int row, int col) {
List<Cell> route = new ArrayList<Cell>();
route.addLast( new Cell(row, col) );
while ( true ) {
CellWithCost currentCell = routes.get(row).get(col);
if ( currentCell.cost == 0 ) {
break;
}
row = currentCell.fromRow;
col = currentCell.fromCol;
route.addFirst( new Cell(row, col) );
}
return route;
}
private static void showUnreachableCells() {
List<Cell> unreachableCells = new ArrayList<Cell>();
for ( int col = 0; col < WIDTH; col++ ) {
for ( int row = 0; row < HEIGHT; row++ ) {
if ( Character.digit(GMOOH[row].charAt(col), 10) >= 0
&& routes.get(row).get(col).equals(CellWithCost.ZERO) ) {
unreachableCells.addLast( new Cell(row, col) );
}
}
}
System.out.println("The following cells are unreachable:");
System.out.println(unreachableCells);
}
private static void showCellsWithLongestRouteFromHQ() {
int maximumCost = Integer.MIN_VALUE;
List<Cell> cells = new ArrayList<Cell>();
for ( int col = 0; col < WIDTH; col++ ) {
for ( int row = 0; row < HEIGHT; row++ ) {
if ( Character.digit(GMOOH[row].charAt(col), 10) >= 0 ) {
CellWithCost currentCell = routes.get(row).get(col);
if ( ! currentCell.equals(CellWithCost.ZERO) ) {
final int cost = currentCell.cost;
if ( cost >= maximumCost) {
if ( cost > maximumCost ) {
cells.clear();
maximumCost = cost;
}
cells.addLast( new Cell(row, col) );
}
}
}
}
}
System.out.println("There are " + cells.size() + " cells that require " + maximumCost
+ " days to receive reinforcements from HQ:");
for ( Cell cell : cells ) {
System.out.println(createRouteToCell(cell.row, cell.col));
}
}
private static List<List<CellWithCost>> routes;
private static final List<Cell> directions = List.of( new Cell(1, -1), new Cell(1, 0), new Cell(1, 1),
new Cell(0, -1), new Cell(0, 1),
new Cell(-1, -1), new Cell(-1, 0), new Cell(-1, 1) );
private static record CellWithCost(int fromRow, int fromCol, int cost) {
public boolean equals(CellWithCost other) {
return cost == other.cost && fromRow == other.fromRow && fromCol == other.fromCol;
}
public static CellWithCost ZERO = new CellWithCost(0, 0, 0);
}
private static record Cell(int row, int col) {
public String toString() {
return "(" + row + ", " + col + ")";
}
}
private static final String[] 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");
private static final int WIDTH = GMOOH[0].length();
private static final int HEIGHT = GMOOH.length;
}
- Output:
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), (12, 11), (12, 8), (12, 4), (9, 1)] [(11, 11), (12, 11), (12, 8), (16, 4), (13, 1)] [(11, 11), (12, 11), (12, 8), (12, 4), (15, 1)] [(11, 11), (12, 11), (12, 8), (16, 4), (16, 1)] [(11, 11), (12, 11), (12, 8), (8, 4), (6, 2)] [(11, 11), (12, 11), (15, 8), (15, 5), (18, 2)] [(11, 11), (12, 10), (11, 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), (12, 10), (13, 10), (18, 5), (19, 4)] [(11, 11), (10, 11), (7, 8), (7, 5), (2, 5)] [(11, 11), (10, 11), (7, 11), (7, 12), (1, 6)] [(11, 11), (11, 12), (8, 9), (2, 9), (1, 8)] [(11, 11), (11, 12), (8, 9), (2, 9), (1, 9)] [(11, 11), (11, 12), (14, 9), (18, 13), (22, 9)] [(11, 11), (12, 11), (15, 8), (18, 11), (22, 11)] [(11, 11), (11, 12), (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), (11, 12), (8, 9), (2, 15), (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), (12, 11), (15, 11), (16, 12), (20, 16)] [(11, 11), (12, 11), (12, 14), (8, 18), (3, 18)] [(11, 11), (12, 11), (15, 14), (16, 15), (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), (21, 10), (20, 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 require 6 days to receive reinforcements from HQ: [(11, 11), (12, 10), (13, 10), (18, 10), (20, 10), (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), (4, 18), (3, 19)] [(11, 11), (12, 11), (9, 14), (9, 17), (7, 17), (7, 20), (6, 20)] [(11, 11), (12, 11), (12, 14), (12, 18), (13, 19), (13, 20), (17, 20)]
Julia
Uses the LightGraphs package.
using LightGraphs
const grid = reshape(Vector{UInt8}(replace("""
00000
00003130000
000321322221000
00231222432132200
0041433223233211100
0232231612142618530
003152122326114121200
031252235216111132210
022211246332311115210
00113232262121317213200
03152118212313211411110
03231234121132221411410
03513213411311414112320
00427534125412213211400
013322444412122123210
015132331312411123120
003333612214233913300
0219126511415312570
0021321524341325100
00211415413523200
000122111322000
00001120000
00000 """, "\n" => "")), 23, 23)
const board = map(c -> c == UInt8(' ') ? -1 : c - UInt8('0'), grid)
const startingpoints = [i for i in 1:529 if board[i] > 0]
const safety = [i for i in 1:529 if board[i] == 0]
const legalendpoints = [i for i in 1:529 if board[i] >= 0]
function adjacent(i)
k, ret = board[i], Int[]
row, col = divrem(i - 1, 23) .+ 1
col > k && push!(ret, i - k)
23 - col >= k && push!(ret, i + k)
row > k && push!(ret, i - 23 * k)
row + k <= 23 && push!(ret, i + 23 * k)
row > k && col > k && push!(ret, i - 24 * k)
row + k <= 23 && (23 - col >= k) && push!(ret, i + 24 * k)
row > k && (23 - col >= k) && push!(ret, i - 22 * k)
row + k <= 23 && col > k && push!(ret, i + 22 * k)
ret
end
const graph = SimpleDiGraph(529)
for i in 1:529
if board[i] > 0
for p in adjacent(i)
if board[p] >= 0
add_edge!(graph, i, p)
end
end
end
end
"""
allnpaths(graph, a, b, vec, n)
Return a vector of int vectors, each of which is a path from a to a member of
vec and where n is the length of each path and the nodes in a path do not repeat.
"""
function allnpaths(graph, a, vec, n)
ret = [[a]]
for j in 2:n
nextret = Vector{Vector{Int}}()
for path in ret, x in neighbors(graph, path[end])
if !(x in path) && (j < n || x in vec)
push!(nextret, [path; x])
end
end
ret = nextret
end
return (ret == [[a]] && a != b) ? [] : ret
end
function pathtostring(path)
ret = ""
for node in path
c = CartesianIndices(board)[node]
ret *= "($(c[2]-1), $(c[1]-1)) "
end
ret
end
function pathlisting(paths)
join([pathtostring(p) for p in paths], "\n")
end
println("Part 1:")
let
start = 23 * 11 + 12
pathsfromcenter = dijkstra_shortest_paths(graph, start)
safepaths = filter(p -> length(p) > 1, enumerate_paths(pathsfromcenter, safety))
safelen = mapreduce(length, min, safepaths)
paths = unique(allnpaths(graph, start, safety, safelen))
println("The $(length(paths)) shortest paths to safety are:\n",
pathlisting(paths))
end
println("\nPart 2:")
let
p = enumerate_paths(bellman_ford_shortest_paths(graph, 21 * 23 + 12), 23 + 12)
println("One shortest route from (21, 11) to (1, 11): ", pathtostring(p))
p = enumerate_paths(bellman_ford_shortest_paths(graph, 23 + 12), 21 * 23 + 12)
println("\nOne shortest route from (1, 11) to (21, 11): ", pathtostring(p))
allshortpaths = [enumerate_paths(bellman_ford_shortest_paths(graph, 23 + 12), p) for p in startingpoints]
maxlen, idx = findmax(map(length, allshortpaths))
println("\nLongest Shortest Route (length $(maxlen - 1)) is: ", pathtostring(allshortpaths[idx]))
end
println("\nExtra Credit Questions:")
let
println("\nIs there any cell in the country that can not be reached from HQ (11, 11)?")
frombase = bellman_ford_shortest_paths(graph, 11 * 23 + 12)
unreached = Int[]
for pt in legalendpoints
path = enumerate_paths(frombase, pt)
if isempty(path) && pt != 11 * 23 + 12
push!(unreached, pt)
end
end
print("There are $(length(unreached)): ")
println(pathtostring(unreached))
println("\nWhich cells will it take longest to send reinforcements to from HQ (11, 11)?")
p = [enumerate_paths(frombase, x) for x in legalendpoints]
maxlen = mapreduce(length, max, p)
allmax = [path for path in p if length(path) == maxlen]
println("There are $(length(allmax)) of length $(maxlen - 1):")
println(pathlisting(allmax))
end
- Output:
Part 1: The 71 shortest paths to safety are: (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, 0) (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, 0) (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, 0) (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) Part 2: One shortest route from (21, 11) to (1, 11): (21, 11) (21, 12) (19, 14) (14, 14) (12, 14) (8, 18) (3, 13) (1, 11) One shortest route from (1, 11) to (21, 11): (1, 11) (2, 10) (5, 13) (9, 9) (15, 3) (20, 8) (20, 10) (21, 11) Longest Shortest Route (length 9) is: (1, 11) (2, 10) (5, 13) (9, 9) (15, 15) (16, 14) (16, 17) (17, 16) (18, 16) (20, 14) Extra Credit Questions: Is there any cell in the country that can not be reached from HQ (11, 11)? There are 3: (2, 18) (4, 3) (18, 20) Which cells will it take longest to send reinforcements to from HQ (11, 11)? There are 5 of length 6: (11, 11) (12, 11) (9, 14) (6, 17) (4, 17) (4, 18) (3, 19) (11, 11) (10, 11) (7, 11) (7, 12) (7, 18) (7, 20) (6, 20) (11, 11) (11, 12) (11, 15) (13, 17) (15, 19) (15, 20) (17, 20) (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)
Nim
With some borrowings from Go and Wren's versions.
Using a simple breadth-first search. Parts 1 and 2 and extra credit.
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()
- Output:
As Nim indexes are 0-based, output differs from Phix program output. It is similar to Go and Wren outputs.
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)]
Alternative using Floyd-Warshall for Part 2, and finding the longest shortest path between any two points.
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()
- Output:
(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)
Perl
#!/usr/bin/perl
use strict;
use warnings;
use List::Util 'first';
my $w = 0;
my $d = join '', <DATA>;
length > $w and $w = length for split "\n", $d;
$d =~ s/.+/ sprintf "%-${w}s", $& /ge; # padding for single number addressing
$w++;
sub to_xy { my($i) = shift; '(' . join(',', int ($i/$w), $i%$w) . ')' }
sub from_xy { my($x,$y) = @_; $x * $w + $y }
my @directions = ( 1, -1, -$w-1 .. -$w+1, $w-1 .. $w+1 );
my @nodes;
push @nodes, $-[0] while $d =~ /\d/g;
my %dist = map { $_ => all_destinations($_) } @nodes; # all shortest from-to paths
sub all_destinations
{
my @queue = shift;
my $dd = $d;
my %to;
while( my $path = shift @queue )
{
my $from = (split ' ', $path)[-1];
my $steps = substr $dd, $from, 1;
' ' eq $steps and next;
$to{$from} //= $path;
$steps or next;
substr $dd, $from, 1, '0';
for my $dir ( @directions )
{
my $next = $from + $steps * $dir;
next if $next < 0 or $next > length $dd;
(substr $dd, $next, 1) =~ /\d/ and push @queue, "$path $next";
}
}
return \%to;
}
my $startpos = from_xy 11, 11;
my @best;
$best[ tr/ // ] .= "\t$_\n" for grep $_, map $dist{$startpos}{$_},
grep { '0' eq substr $d, $_, 1 } @nodes;
my $short = first { $best[$_] } 0 .. $#best;
my $n = $best[$short] =~ tr/\n//;
print "shortest escape routes ($n) of length $short:\n",
$best[$short] =~ s/\d+/ to_xy $& /ger;
print "\nshortest from (21,11) to (1,11):\n\t",
$dist{from_xy 21, 11}{from_xy 1, 11} =~ s/\d+/ to_xy $& /ger, "\n";
print "\nshortest from (1,11) to (21,11):\n\t",
$dist{from_xy 1, 11}{from_xy 21, 11} =~ s/\d+/ to_xy $& /ger, "\n";
@best = ();
$best[tr/ //] .= "\t$_\n" for map { values %$_ } values %dist;
print "\nlongestshortest paths (length $#best) :\n",
$best[-1] =~ s/\d+/ to_xy $& /ger;
my @notreach = grep !$dist{$startpos}{$_}, @nodes;
print "\nnot reached from HQ:\n\t@notreach\n" =~ s/\d+/ to_xy $& /ger;
@best = ();
$best[tr/ //] .= "\t$_\n" for values %{ $dist{$startpos} };
print "\nlongest reinforcement from HQ is $#best for:\n",
$best[-1] =~ s/\d+/ to_xy $& /ger;
__DATA__
00000
00003130000
000321322221000
00231222432132200
0041433223233211100
0232231612142618530
003152122326114121200
031252235216111132210
022211246332311115210
00113232262121317213200
03152118212313211411110
03231234121132221411410
03513213411311414112320
00427534125412213211400
013322444412122123210
015132331312411123120
003333612214233913300
0219126511415312570
0021321524341325100
00211415413523200
000122111322000
00001120000
00000
- Output:
shortest escape routes (40) of length 4:
(11,11) (11,12) (8,12) (6,12) (0,12)
(11,11) (10,11) (7,11) (7,12) (1,6)
(11,11) (11,12) (8,9) (2,9) (1,8)
(11,11) (11,12) (8,9) (2,9) (1,9)
(11,11) (10,10) (8,10) (5,13) (1,13)
(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) (10,10) (8,10) (5,7) (2,4)
(11,11) (10,11) (7,8) (7,5) (2,5)
(11,11) (11,12) (8,9) (2,15) (2,16)
(11,11) (11,12) (11,9) (9,9) (3,3)
(11,11) (10,11) (7,8) (4,5) (3,4)
(11,11) (12,11) (12,14) (8,18) (3,18)
(11,11) (12,11) (9,14) (6,17) (4,19)
(11,11) (11,12) (8,9) (8,3) (6,1)
(11,11) (10,10) (8,8) (8,4) (6,2)
(11,11) (11,12) (11,15) (11,17) (7,21)
(11,11) (11,12) (8,9) (8,3) (8,1)
(11,11) (10,10) (8,8) (12,4) (9,1)
(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) (10,10) (12,8) (16,4) (13,1)
(11,11) (12,11) (12,14) (16,18) (13,21)
(11,11) (10,10) (8,8) (12,4) (15,1)
(11,11) (11,12) (11,15) (11,17) (15,21)
(11,11) (10,10) (12,8) (16,4) (16,1)
(11,11) (10,11) (10,14) (12,16) (16,20)
(11,11) (12,11) (12,14) (16,18) (16,21)
(11,11) (12,11) (15,8) (15,5) (18,2)
(11,11) (10,11) (13,8) (14,7) (18,3)
(11,11) (11,12) (14,9) (18,5) (19,4)
(11,11) (11,12) (14,15) (16,15) (19,18)
(11,11) (11,12) (14,12) (16,12) (20,16)
(11,11) (10,11) (13,11) (17,15) (20,18)
(11,11) (12,10) (13,10) (18,15) (21,15)
(11,11) (11,12) (14,9) (18,13) (22,9)
(11,11) (12,11) (15,8) (18,11) (22,11)
(11,11) (11,12) (14,9) (18,13) (22,13)
shortest from (21,11) to (1,11):
(21,11) (21,12) (19,10) (14,10) (10,10) (8,8) (4,8) (1,11)
shortest from (1,11) to (21,11):
(1,11) (2,10) (5,13) (9,9) (15,3) (20,8) (20,10) (21,11)
longestshortest paths (length 9) :
(1,11) (1,12) (4,9) (6,9) (8,9) (14,15) (16,17) (17,16) (18,16) (20,14)
(2,9) (2,10) (5,7) (8,7) (8,9) (14,15) (16,17) (17,16) (18,16) (20,14)
(12,21) (12,19) (12,17) (12,16) (12,12) (12,11) (15,8) (15,5) (15,2) (14,2)
(7,3) (7,4) (5,4) (8,7) (8,9) (14,15) (16,17) (17,16) (18,16) (20,14)
(10,21) (10,20) (9,19) (9,16) (9,9) (15,3) (15,8) (15,5) (15,2) (14,2)
(2,13) (2,15) (3,15) (6,12) (12,18) (13,19) (13,20) (17,16) (18,16) (20,14)
(11,21) (11,20) (11,16) (11,17) (11,13) (13,11) (17,7) (15,5) (15,2) (14,2)
not reached from HQ:
(2,18) (4,3) (18,20)
longest reinforcement from HQ is 6 for:
(11,11) (11,12) (11,15) (13,17) (13,19) (13,20) (17,20)
(11,11) (11,12) (11,15) (11,17) (7,17) (7,20) (6,20)
(11,11) (12,11) (9,14) (6,17) (4,17) (4,18) (3,19)
(11,11) (11,12) (14,12) (16,12) (20,12) (21,11) (22,12)
(11,11) (11,12) (14,15) (16,17) (17,16) (18,16) (20,14)
Phix
Using a simple breadth-first search. Parts 1 and 2 and extra credit.
constant gmooh = 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') constant width = length(gmooh[1]), height = length(gmooh), d = {{-1,-1},{0,-1},{+1,-1}, {-1, 0}, {+1, 0}, {-1,+1},{0,+1},{+1,+1}} sequence routes -- {cost,fromy,fromx} for each gmooh[][]. procedure search(integer y, x) -- simple breadth-first search, populates routes -- (this isn't strictly dijkstra, because graph edges are not weighted) integer cost = 0 sequence route = {{y,x}}, next = {} routes = repeat(repeat(0,width),height) routes[y,x] = {0,y,x} -- zero-cost the starting point while 1 do integer n = gmooh[y,x]-'0' for di=1 to length(d) do integer {dx,dy} = d[di] integer {rx,ry} = {x+n*dx,y+n*dy} if rx>=1 and rx<=width and ry>=1 and ry<=height and gmooh[ry,rx]>='0' then object ryx = routes[ry,rx] if ryx=0 or ryx[1]>cost+1 then routes[ry,rx] = {cost+1,y,x} if gmooh[ry,rx]>'0' then next = append(next,{cost+1,ry,rx}) -- (if the graph was weighted, at this point -- that would get shuffled up into place.) end if end if end if end for if length(next)=0 then exit end if {cost,y,x} = next[1] next = next[2..$] end while end procedure function get_route(sequence yx) integer {y,x} = yx integer cost sequence res = {{y,x}} while 1 do {cost,y,x} = routes[y,x] if cost=0 then exit end if res = prepend(res,{y,x}) end while return res end function procedure show_shortest_routes_to_safety() integer shortest = 9999 sequence res = {} for x=1 to width do for y=1 to height do if gmooh[y,x]='0' then object ryx = routes[y,x] if ryx!=0 then integer cost = ryx[1] if cost<=shortest then if cost<shortest then res = {} shortest = cost end if res = append(res,{y,x}) end if end if end if end for end for string {areis,s} = iff(length(res)>1?{"are","s"}:{"is",""}) printf(1,"There %s %d shortest route%s of %d days to safety:\n",{areis,length(res),s,shortest}) for i=1 to length(res) do ?get_route(res[i]) end for end procedure procedure show_unreachable() sequence res = {} for x=1 to width do for y=1 to height do if gmooh[y,x]>='0' and routes[y,x]=0 then res = append(res,{y,x}) end if end for end for puts(1,"The following cells are unreachable:\n") ?res end procedure procedure show_longest() integer longest = 0 sequence res = {} for x=1 to width do for y=1 to height do if gmooh[y,x]>='0' then object ryx = routes[y,x] if ryx!=0 then integer rl = ryx[1] if rl>=longest then if rl>longest then res = {} longest = rl end if res = append(res,{y,x}) end if end if end if end for end for printf(1,"There are %d cells that take %d days to send reinforcements to\n",{length(res),longest}) for i=1 to length(res) do ?get_route(res[i]) end for end procedure procedure main() search(12,12) show_shortest_routes_to_safety() -- see also below search(22,12) puts(1,"The shortest route from 22,12 to 2,12:\n") ?get_route({2,12}) search(2,12) puts(1,"The shortest route from 2,12 to 22,12:\n") ?get_route({22,12}) search(12,12) -- </see also below> show_unreachable() show_longest() end procedure main()
- Output:
Note: Phix indexes are 1-based and therefore so too are these results.
There are 40 shortest routes of 4 days to safety:
{{12,12},{12,13},{9,10},{15,4},{12,1}}
{{12,12},{11,12},{8,9},{8,6},{13,1}}
{{12,12},{13,11},{14,11},{14,6},{14,1}}
{{12,12},{12,13},{9,10},{9,4},{7,2}}
{{12,12},{12,13},{9,10},{9,4},{9,2}}
{{12,12},{11,11},{9,9},{13,5},{10,2}}
{{12,12},{11,11},{13,9},{17,5},{14,2}}
{{12,12},{11,11},{9,9},{13,5},{16,2}}
{{12,12},{11,11},{13,9},{17,5},{17,2}}
{{12,12},{11,11},{9,9},{9,5},{7,3}}
{{12,12},{13,12},{16,9},{16,6},{19,3}}
{{12,12},{12,11},{11,10},{10,10},{4,4}}
{{12,12},{11,12},{14,9},{15,8},{19,4}}
{{12,12},{11,11},{9,11},{6,8},{3,5}}
{{12,12},{11,12},{8,9},{5,6},{4,5}}
{{12,12},{11,11},{13,9},{17,5},{20,5}}
{{12,12},{11,12},{8,9},{8,6},{3,6}}
{{12,12},{11,12},{8,12},{8,13},{2,7}}
{{12,12},{11,11},{9,9},{5,9},{2,9}}
{{12,12},{11,11},{9,11},{6,14},{2,10}}
{{12,12},{12,13},{15,10},{19,14},{23,10}}
{{12,12},{13,12},{16,9},{19,12},{23,12}}
{{12,12},{11,11},{9,13},{7,13},{1,13}}
{{12,12},{11,11},{9,11},{6,14},{2,14}}
{{12,12},{12,13},{15,10},{19,14},{23,14}}
{{12,12},{11,12},{8,9},{5,12},{2,15}}
{{12,12},{12,13},{9,10},{3,16},{2,16}}
{{12,12},{13,11},{14,11},{19,16},{22,16}}
{{12,12},{12,13},{9,10},{3,16},{2,17}}
{{12,12},{12,13},{9,10},{3,16},{3,17}}
{{12,12},{11,11},{13,9},{17,13},{21,17}}
{{12,12},{13,12},{13,15},{9,19},{4,19}}
{{12,12},{12,13},{15,16},{17,16},{20,19}}
{{12,12},{11,12},{14,12},{18,16},{21,19}}
{{12,12},{13,12},{10,15},{7,18},{5,20}}
{{12,12},{11,12},{11,15},{13,17},{17,21}}
{{12,12},{12,13},{12,16},{12,18},{8,22}}
{{12,12},{13,12},{13,15},{17,19},{14,22}}
{{12,12},{12,13},{12,16},{12,18},{16,22}}
{{12,12},{13,12},{13,15},{17,19},{17,22}}
The shortest route from 22,12 to 2,12:
{{22,12},{21,11},{20,10},{19,10},{14,5},{7,12},{5,12},{2,12}}
The shortest route from 2,12 to 22,12:
{{2,12},{3,11},{6,14},{10,10},{16,4},{21,9},{21,11},{22,12}}
The following cells are unreachable:
{{5,4},{3,19},{19,21}}
There are 5 cells that take 6 days to send reinforcements to
{{12,12},{11,11},{13,9},{17,13},{21,13},{22,12},{23,13}}
{{12,12},{12,13},{15,16},{17,18},{18,17},{19,17},{21,15}}
{{12,12},{13,12},{10,15},{7,18},{5,18},{4,18},{4,20}}
{{12,12},{11,12},{8,12},{8,13},{8,19},{8,21},{7,21}}
{{12,12},{11,12},{11,15},{13,17},{13,21},{16,21},{18,21}}
Alternative using Floyd-Warshall for Part 2, and finding the longest shortest path between any two points.
--(same constants as above: gmooh, width, height, d) constant inf = 1e300*1e300 sequence dist, next, pmap = {} function fw_path(integer u, v) sequence res = {} if next[u,v]!=null then sequence path = {sprintf("{%d,%d}",pmap[u])} while u!=v do u = next[u,v] path = append(path,sprintf("{%d,%d}",pmap[u])) end while res = join(path,"->") end if return res end function procedure show_fw_path(integer u, v) printf(1,"{%d,%d}->{%d,%d} %2d %s\n",pmap[u]&pmap[v]&{dist[u,v],fw_path(u,v)}) end procedure procedure FloydWarshall() integer point = 0 sequence weights = {}, points = repeat(repeat(0,width),height) -- First number the points... for x=1 to width do for y=1 to height do if gmooh[y,x]>='0' then point += 1 points[y,x] = point pmap = append(pmap,{y,x}) end if end for end for -- ...and then a set of edges (all of which have a "weight" of 1 day) for x=1 to width do for y=1 to height do if gmooh[y,x]>'0' then integer n = gmooh[y,x]-'0' for di=1 to length(d) do integer {dx,dy} = d[di] integer {rx,ry} = {x+n*dx,y+n*dy} if rx>=1 and rx<=width and ry>=1 and ry<=height and gmooh[ry,rx]>='0' then -- weights = append(weights,{points[y,x],points[ry,rx],1}) weights = append(weights,{points[y,x],points[ry,rx]}) end if end for end if end for end for -- Before applying Floyd-Warshall integer V = length(pmap) dist = repeat(repeat(inf,V),V) next = repeat(repeat(null,V),V) for k=1 to length(weights) do -- integer {u,v,w} = weights[k] integer {u,v} = weights[k] -- dist[u,v] := w -- the weight of the edge (u,v) dist[u,v] := 1 -- the weight of the edge (u,v) next[u,v] := v end for -- standard Floyd-Warshall implementation, -- with the optimisation of avoiding processing of self/infs, -- which surprisingly makes quite a noticeable difference. for k=1 to V do for i=1 to V do if i!=k and dist[i,k]!=inf then for j=1 to V do if j!=i and j!=k and dist[k,j]!=inf then atom d = dist[i,k] + dist[k,j] if d<dist[i,j] then dist[i,j] := d next[i,j] := next[i,k] end if end if end for end if end for end for show_fw_path(points[22,12],points[2,12]) show_fw_path(points[2,12],points[22,12]) integer maxd = 0, mi, mj for i=1 to V do for j=1 to V do if j!=i then atom d = dist[i,j] if d!=inf and d>maxd then {maxd,mi,mj} = {d,i,j} end if end if end for end for printf(1,"Maximum shortest distance:\n") show_fw_path(mi,mj) end procedure FloydWarshall()
- Output:
{22,12}->{2,12} 7 {22,12}->{21,11}->{20,11}->{15,11}->{11,11}->{9,9}->{5,9}->{2,12}
{2,12}->{22,12} 7 {2,12}->{3,11}->{6,14}->{10,10}->{16,4}->{21,9}->{21,11}->{22,12}
Maximum shortest distance:
{8,4}->{21,15} 9 {8,4}->{9,5}->{11,7}->{12,8}->{16,12}->{17,12}->{18,13}->{18,17}->{19,17}->{21,15}
Python
from collections import deque
from dataclasses import dataclass
from typing import List
@dataclass(frozen=True)
class CellWithCost:
fromRow: int
fromCol: int
cost: int
ZERO = CellWithCost(0, 0, 0)
@dataclass
class Cell:
row: int
col: int
def __repr__(self):
return f"({self.row}, {self.col})"
GMOOH = (
".........00000.........\n"
"......00003130000......\n"
"....000321322221000....\n"
"...00231222432132200...\n"
"..0041433223233211100..\n"
"..0232231612142618530..\n"
".003152122326114121200.\n"
".031252235216111132210.\n"
".022211246332311115210.\n"
"00113232262121317213200\n"
"03152118212313211411110\n"
"03231234121132221411410\n"
"03513213411311414112320\n"
"00427534125412213211400\n"
".013322444412122123210.\n"
".015132331312411123120.\n"
".003333612214233913300.\n"
"..0219126511415312570..\n"
"..0021321524341325100..\n"
"...00211415413523200...\n"
"....000122111322000....\n"
"......00001120000......\n"
".........00000.........\n"
).strip().splitlines()
HEIGHT, WIDTH = len(GMOOH), len(GMOOH[0])
directions = [
Cell(1, -1), Cell(1, 0), Cell(1, 1),
Cell(0, -1), Cell(0, 1),
Cell(-1, -1), Cell(-1, 0), Cell(-1, 1)
]
routes: List[List[CellWithCost]] = []
#### Helper functions ####
def digit(ch: str) -> int:
return int(ch) if ch.isdigit() else -1
#### End of helper functions ####
def searchFromCell(startRow: int, startCol: int):
global routes
routes = [[ZERO for _ in range(WIDTH)] for _ in range(HEIGHT)]
routes[startRow][startCol] = CellWithCost(startRow, startCol, 0)
queue = deque()
row, col, cost = startRow, startCol, 0
while True:
step = digit(GMOOH[row][col])
for d in directions:
nr = row + step * d.row
nc = col + step * d.col
if 0 <= nr < HEIGHT and 0 <= nc < WIDTH and digit(GMOOH[nr][nc]) >= 0:
current = routes[nr][nc]
if current == ZERO or current.cost > cost + 1:
routes[nr][nc] = CellWithCost(row, col, cost+1)
if digit(GMOOH[nr][nc]) > 0:
queue.append(CellWithCost(nr, nc, cost+1))
if not queue:
break
nextCell = queue.popleft()
row, col, cost = nextCell.fromRow, nextCell.fromCol, nextCell.cost
def createRouteToCell(endRow: int, endCol: int) -> List[Cell]:
route: deque[Cell] = deque()
route.append(Cell(endRow, endCol))
while True:
cw = routes[endRow][endCol]
if cw.cost == 0:
break
endRow, endCol = cw.fromRow, cw.fromCol
route.appendleft(Cell(endRow, endCol))
return list(route)
def showShortestRoutes():
minCost = float("inf")
bestCells: List[Cell] = []
for r in range(HEIGHT):
for c in range(WIDTH):
if digit(GMOOH[r][c]) == 0:
cw = routes[r][c]
if cw != ZERO:
if cw.cost < minCost:
minCost = cw.cost
bestCells.clear()
if cw.cost == minCost:
bestCells.append(Cell(r, c))
plural = "s" if len(bestCells) != 1 else ""
isAre = "are" if len(bestCells) != 1 else "is"
print(f"There {isAre} {len(bestCells)} shortest route{plural} of {minCost} days to safety:")
for cell in bestCells:
print(createRouteToCell(cell.row, cell.col))
def showUnreachableCells():
unreachable: List[Cell] = []
for r in range(HEIGHT):
for c in range(WIDTH):
if digit(GMOOH[r][c]) == 0 and routes[r][c] == ZERO:
unreachable.append(Cell(r, c))
print("The following cells are unreachable:")
print(unreachable)
def showCellsWithLongestRoute():
maxCost = -1
worstCells: List[Cell] = []
for r in range(HEIGHT):
for c in range(WIDTH):
if digit(GMOOH[r][c]) >= 0:
cw = routes[r][c]
if cw != ZERO:
if cw.cost > maxCost:
maxCost = cw.cost
worstCells.clear()
if cw.cost == maxCost:
worstCells.append(Cell(r, c))
plural = "s" if len(worstCells) != 1 else ""
isAre = "are" if len(worstCells) != 1 else "is"
print(f"There {isAre} {len(worstCells)} cell{plural} that require {maxCost} days to receive reinforcements from HQ:")
for cell in worstCells:
print(createRouteToCell(cell.row, cell.col))
if __name__ == "__main__":
searchFromCell(11, 11)
showShortestRoutes()
print()
searchFromCell(21, 11)
print("The shortest route from (21, 11) to (1, 11):")
print(createRouteToCell(1, 11))
print()
searchFromCell(1, 11)
print("The shortest route from (1, 11) to (21, 11):")
print(createRouteToCell(21, 11))
print()
searchFromCell(11, 11)
showUnreachableCells()
print()
showCellsWithLongestRoute()
Raku
my $d = qq:to/END/;
00000
00003130000
000321322221000
00231222432132200
0041433223233211100
0232231612142618530
003152122326114121200
031252235216111132210
022211246332311115210
00113232262121317213200
03152118212313211411110
03231234121132221411410
03513213411311414112320
00427534125412213211400
013322444412122123210
015132331312411123120
003333612214233913300
0219126511415312570
0021321524341325100
00211415413523200
000122111322000
00001120000
00000
END
my $w = $d.split("\n")».chars.max;
$d = $d.split("\n")».fmt("%-{$w}s").join("\n"); # pad lines to same length
$w++;
my @directions = ( 1, -1, -$w-1, -$w, -$w+1, $w-1, $w, $w+1);
my @nodes.push: .pos - 1 for $d ~~ m:g/\d/;
my %dist = @nodes.race.map: { $_ => all-destinations([$_]) };
sub all-destinations (@queue) {
my %to;
my $dd = $d;
while shift @queue -> $path {
my $from = ($path.split(' '))[*-1];
my $steps = $dd.substr($from, 1);
next if $steps eq ' ';
%to{$from} //= $path;
next if $steps eq '0';
$dd.substr-rw($from, 1) = '0';
for @directions -> $dir {
my $next = $from + $steps × $dir;
next if $next < 0 or $next > $dd.chars;
@queue.push: "$path $next" if $dd.substr($next, 1) ~~ /\d/;
}
}
%to;
}
sub to-xy ($nodes) { join ' ', $nodes.split(' ').map: { '(' ~ join(',', floor($_/$w), $_%$w) ~ ')' } }
sub from-xy ($x, $y) { $x × $w + $y }
my $startpos = from-xy 11, 11;
my %routes;
%routes{.split(' ').elems}.push: .&to-xy
for grep { .so }, map { %dist{$startpos}{$_} }, grep { '0' eq $d.substr($_, 1) }, @nodes;
my $n = %routes{ my $short-route = %routes.keys.sort.first }.elems;
say "Shortest escape routes ($n) of length {$short-route - 1}:\n\t" ~
%routes{$short-route}.join("\n\t");
say "\nShortest from (21,11) to (1,11):\n\t" ~ %dist{from-xy 21, 11}{from-xy 1, 11}.&to-xy;
say "\nShortest from (1,11) to (21,11):\n\t" ~ %dist{from-xy 1, 11}{from-xy 21, 11}.&to-xy;
my @long-short = reverse sort { .split(' ').elems }, gather %dist.deepmap(*.take);
my $l = @long-short[0].split(' ').elems;
say "\nLongest 'shortest' paths (length {$l-1}):";
say "\t" ~ .&to-xy for grep { .split(' ').elems == $l }, @long-short;
say "\nNot reachable from HQ:\n\t" ~ @nodes.grep({not %dist{$startpos}{$_}}).&to-xy;
my @HQ;
@HQ[.split(' ').elems].push: .&to-xy for %dist{$startpos}.values;
say "\nLongest reinforcement from HQ is {@HQ - 2} for:\n\t" ~ @HQ[*-1].join("\n\t");
- Output:
Shortest escape routes (40) of length 4:
(11,11) (11,12) (8,12) (6,12) (0,12)
(11,11) (10,11) (7,11) (7,12) (1,6)
(11,11) (11,12) (8,9) (2,9) (1,8)
(11,11) (11,12) (8,9) (2,9) (1,9)
(11,11) (10,10) (8,10) (5,13) (1,13)
(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) (10,10) (8,10) (5,7) (2,4)
(11,11) (10,11) (7,8) (7,5) (2,5)
(11,11) (11,12) (8,9) (2,15) (2,16)
(11,11) (11,12) (11,9) (9,9) (3,3)
(11,11) (10,11) (7,8) (4,5) (3,4)
(11,11) (12,11) (12,14) (8,18) (3,18)
(11,11) (12,11) (9,14) (6,17) (4,19)
(11,11) (11,12) (8,9) (8,3) (6,1)
(11,11) (10,10) (8,8) (8,4) (6,2)
(11,11) (11,12) (11,15) (11,17) (7,21)
(11,11) (11,12) (8,9) (8,3) (8,1)
(11,11) (10,10) (8,8) (12,4) (9,1)
(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) (10,10) (12,8) (16,4) (13,1)
(11,11) (12,11) (12,14) (16,18) (13,21)
(11,11) (10,10) (8,8) (12,4) (15,1)
(11,11) (11,12) (11,15) (11,17) (15,21)
(11,11) (10,10) (12,8) (16,4) (16,1)
(11,11) (10,11) (10,14) (12,16) (16,20)
(11,11) (12,11) (12,14) (16,18) (16,21)
(11,11) (12,11) (15,8) (15,5) (18,2)
(11,11) (10,11) (13,8) (14,7) (18,3)
(11,11) (11,12) (14,9) (18,5) (19,4)
(11,11) (11,12) (14,15) (16,15) (19,18)
(11,11) (11,12) (14,12) (16,12) (20,16)
(11,11) (10,11) (13,11) (17,15) (20,18)
(11,11) (12,10) (13,10) (18,15) (21,15)
(11,11) (11,12) (14,9) (18,13) (22,9)
(11,11) (12,11) (15,8) (18,11) (22,11)
(11,11) (11,12) (14,9) (18,13) (22,13)
Shortest from (21,11) to (1,11):
(21,11) (21,12) (19,10) (14,10) (10,10) (8,8) (4,8) (1,11)
Shortest from (1,11) to (21,11):
(1,11) (2,10) (5,13) (9,9) (15,3) (20,8) (20,10) (21,11)
Longest 'shortest' paths (length 9):
(7,3) (7,4) (5,4) (8,7) (8,9) (14,15) (16,17) (17,16) (18,16) (20,14)
(10,21) (10,20) (9,19) (9,16) (9,9) (15,3) (15,8) (15,5) (15,2) (14,2)
(11,21) (11,20) (11,16) (11,17) (11,13) (13,11) (17,7) (15,5) (15,2) (14,2)
(12,21) (12,19) (12,17) (12,16) (12,12) (12,11) (15,8) (15,5) (15,2) (14,2)
(1,11) (1,12) (4,9) (6,9) (8,9) (14,15) (16,17) (17,16) (18,16) (20,14)
(2,9) (2,10) (5,7) (8,7) (8,9) (14,15) (16,17) (17,16) (18,16) (20,14)
(2,13) (2,15) (3,15) (6,12) (12,18) (13,19) (13,20) (17,16) (18,16) (20,14)
Not reachable from HQ:
(2,18) (4,3) (18,20)
Longest reinforcement from HQ is 6 for:
(11,11) (11,12) (11,15) (11,17) (7,17) (7,20) (6,20)
(11,11) (11,12) (11,15) (13,17) (13,19) (13,20) (17,20)
(11,11) (11,12) (14,12) (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) (4,18) (3,19)
Wren
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.
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()
- Output:
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]]
Alternative using Floyd-Warshall for Part 2, and finding the longest shortest path between any two points.
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()
- Output:
[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]