How to resolve the algorithm I'm a software engineer, get me out of here step by step in the J programming language
Published on 12 May 2024 09:40 PM
How to resolve the algorithm I'm a software engineer, get me out of here step by step in the J programming language
Table of Contents
Problem Statement
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. 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
Related tasks:
Let's start with the solution:
Step by Step solution about How to resolve the algorithm I'm a software engineer, get me out of here step by step in the J programming language
Source code in the j programming language
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 }}
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
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
}}
#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
#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
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
You may also check:How to resolve the algorithm Perfect numbers step by step in the MAXScript programming language
You may also check:How to resolve the algorithm Show ASCII table step by step in the Jsish programming language
You may also check:How to resolve the algorithm JSON step by step in the Gosu programming language
You may also check:How to resolve the algorithm Pythagorean triples step by step in the Perl programming language
You may also check:How to resolve the algorithm Sleep step by step in the Nanoquery programming language