Talk:I'm a software engineer, get me out of here
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).
- Explains a lot about our current situation. Perhaps the president needs opticians, not software engineers. Probably wouldn't make a difference, for a few dollars they'd be blind. Who can blame them given the president's example?--Nigel Galloway (talk) 13:20, 8 September 2018 (UTC)
- 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.
- Sounds good, two examples sometimes better than one. Do you have one in mind?--Nigel Galloway (talk) 13:58, 19 September 2018 (UTC)
- 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?
- At the briefing it was "concluded that you need to know the shortest route from each cell to every other cell". The commanders are not going to tell you where their troops are or where they want them. The two routes are just examples, a database with all routes is required.--Nigel Galloway (talk) 13:58, 19 September 2018 (UTC)
- 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.
- Good for you. An improvement.--Nigel Galloway (talk) 13:20, 8 September 2018 (UTC)
- Lastly, you didn't understand the show_longest output, so, as well as showing all 40 shortest routes, I have extended the output 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)
- 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).
40 or 71 routes
The Julia example shows 71 routes. It has 4 that end at (3,3), whereas the others have only 1 (and Phix has only 1 that ends at {4,4}). As above I thought Dijkstra's ought to be a suggestion anyway, and apart from the fact that should only give 1, I have no preference for whether both are acceptable, but if so the task should probably mention that. --Pete Lomax (talk) 00:54, 20 September 2019 (UTC)
The Julia LightGraphs module actually only gave 1 route from its Dijksrta implementation. Based on the extant examples I thought that must be wrong, but the simplest solution was then to get all routes. --Wherrera (talk) 04:39, 20 September 2019 (UTC)
The Problem's Wording
I have a bit of trouble understanding the wording of the problem, and if my reading is correct, then perhaps the problem should be changed to a slightly more challenging one! Here's a copy of the current wording:
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.
My understanding of this wording is that the small positive integer in each cell of unsafe territory denotes the number of steps that can be taken in a turn that begins in that cell. However, this is slightly unrealistic, unless you allow excuses as far-fetched as the high-numbered cells containing sufficiently level regions for tactical airlifts; perhaps the numbers can denote the reciprocal of a cost function, and the allowance per turn is steps totalling one cost unit? --Adlai (talk) 11:06, 2 January 2021 (UTC)
- Let's see your CommonLisp implementation of this "trivial problem" as it stands, before we complicate matters. --Pete Lomax (talk) 13:56, 2 January 2021 (UTC)
- My questioning of the problem's wording, and the suggestion either it or the challenge istelf be changed, were not intended to imply that the current version was trivial, only to confirm that my understanding of the text was correct, without reading other people's implementations before writing my own. I have noticed that it is common for submitted code to be direct translations from another language, although was not planning on doing that here. --Adlai (talk) 16:44, 4 January 2021 (UTC)
- Yes, your interpretation is correct. The number indicates how many squares to hop horizontally or vertically, or both in the diagonal case. Thus a 2 in (10,10) would land in (8,8), (8,10), (8,12), (10,8), (10,12), (12,8), (12,10), or (12,12). It is however "in a day" rather than a "turn" or "cost", and we're looking for fewest total days rather than shortest travelled distance. One of the reasons why translations are so prevalent and readily accepted is that this is a language comparison site, and that tends to be easier when submissions are using the same algorithm.
However better/novel/interesting and just plain weird alternative algorithms are of course also welcome, and each language can have more than one.Oh, scratch that, I forgot this task specifically asks that Dijkstra's and Floyd-Warshall algorithms be used. --Pete Lomax (talk) 17:19, 4 January 2021 (UTC)
- Yes, your interpretation is correct. The number indicates how many squares to hop horizontally or vertically, or both in the diagonal case. Thus a 2 in (10,10) would land in (8,8), (8,10), (8,12), (10,8), (10,12), (12,8), (12,10), or (12,12). It is however "in a day" rather than a "turn" or "cost", and we're looking for fewest total days rather than shortest travelled distance. One of the reasons why translations are so prevalent and readily accepted is that this is a language comparison site, and that tends to be easier when submissions are using the same algorithm.
- My questioning of the problem's wording, and the suggestion either it or the challenge istelf be changed, were not intended to imply that the current version was trivial, only to confirm that my understanding of the text was correct, without reading other people's implementations before writing my own. I have noticed that it is common for submitted code to be direct translations from another language, although was not planning on doing that here. --Adlai (talk) 16:44, 4 January 2021 (UTC)