Talk:I'm a software engineer, get me out of here: Difference between revisions

Content added Content deleted

Inline

Revision as of 13:49, 30 August 2018

Algorithm

I think the use of Dijkstra's and Floyd-Warshall algorithms should be a suggestion rather than a requirement. Anyway, I've used a simple breadth-first algorithm for the Phix entry. Pete Lomax (talk) 21:00, 17 August 2018 (UTC)

Thank you for your contribution, sadly your last as I read in this morning's standing orders that you were shot at dawn. Part 1 is to find a list of the shortest routes to safety. I interpreted this as meaning all points of safety which could be reached in 5 days. Having supplied only one which turned out to have LARC (Liberation Army of RosettaCode - objective Liberate the president's gold) waiting, the president assumed you were part of the conspiracy. Just because he's paranoid it doesn't mean no-one is out to get him. Further the extra credit is "Which cells will it take longest to send reinforcements to from HQ?". HQ is at (11,11) (or 12,12 if indexing starts at 1 as God intended), so I'm not sure what {"show_longest",{{23,13},{21,15},{4,20},{7,21},{18,21}}} answers. At the end of 2011 people were asking why RC's Dijkstra task was still draft. Mid 2018 I have updated that task so that it may be implemented consistently and raised it to full status. One of the requests was for a non trivial example, I would like this maze to be that. They also suggest that Floyd could be used equivalently, which may be for the trivial examples they give, tried here one sees the difference. So I think this task's specification is clear and should be adhered to.--Nigel Galloway (talk) 12:04, 29 August 2018 (UTC)

Reports of my demise have been greatly exaggerated, the firing squad were all cross-eyed and missed. Perhaps some sort of proof that using those specific algorithms are better in this case than some other alternative should be shown (in the output, dunno what though).

The edges are not weighted (they all cost 1 day), so Dijkstra is an unnecessary overhead compared to breadth-first, albeit the relatively small one of maintaining and retrieving the lowest-cost node next (in my code the "next" variable only ever holds {cost}{cost+1}). Perhaps if the numbers on the map, instead of some magical "teleport" number were a terrain difficulty, with 1 being "straight fast motorways" and 9 being "dense undergrowth, steep difficult climbs, boggy marshes, minefields, and similar obstacles", so to move 1 square costs (this+dest) days travel, then that might justify using Dijkstra. It would of course mean there are no unreachable cells.

As it stands, Part 2 can be completed with a simple breadth-first search (or two), calculating at most 820 routes, whereas using Floyd-Warshall creates 170,156 routes.

When you say "tried here one sees the difference", did you mean a large negative one?

You could justify Floyd by asking for the maximum shortest route between any two points, so I've added that to the task and done just that.

I have extended the output (as well as showing all 40 shortest routes) of show_longest to show the full routes for those 5 nodes, maybe that will make more sense to you. Pete Lomax (talk) 13:34, 30 August 2018 (UTC)

@@ Line 5: / Line 5: @@
 ::Reports of my demise have been greatly exaggerated, the firing squad were all cross-eyed and missed. Perhaps some sort of proof that using those specific algorithms are better in this case than some other alternative should be shown (in the output, dunno what though).
-::The edges are not weighted (they all cost 1 day), so Dijkstra is an unnecessary overhead compared to breadth-first, albeit the relatively small one of maintaining and retrieving the lowest-cost node next (in my code the "next" variable only ever holds {cost}{cost+1}). Perhaps if the numbers on the map, instead of some magical "teleport" number were a terrain difficulty, with 1 being "straight fast motorways" and 9 being "dense undergrowth, steep difficult climbs, boggy marshes, minefields, and similar obstacles", so to move 1 square costs (this+dest) days travel, then that might justify using Dijkstra.
+::The edges are not weighted (they all cost 1 day), so Dijkstra is an unnecessary overhead compared to breadth-first, albeit the relatively small one of maintaining and retrieving the lowest-cost node next (in my code the "next" variable only ever holds {cost}{cost+1}). Perhaps if the numbers on the map, instead of some magical "teleport" number were a terrain difficulty, with 1 being "straight fast motorways" and 9 being "dense undergrowth, steep difficult climbs, boggy marshes, minefields, and similar obstacles", so to move 1 square costs (this+dest) days travel, then that might justify using Dijkstra. It would of course mean there are no unreachable cells.
 ::As it stands, Part 2 can be completed with a simple breadth-first search (or two), calculating at most 820 routes, whereas using Floyd-Warshall creates 170,156 routes.