Talk:I'm a software engineer, get me out of here: Difference between revisions
Talk:I'm a software engineer, get me out of here (view source)
Revision as of 17:33, 4 January 2021
, 3 years ago→The Problem's Wording
No edit summary |
|||
| (9 intermediate revisions by 4 users not shown) | |||
Line 6:
:::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?--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk: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?--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk: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.--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk: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.--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk: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. [[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]]) 13:34, 30 August 2018 (UTC)
==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. --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|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.
--[[User:Wherrera|Wherrera]] ([[User talk: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:
<pre>
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.
</pre>
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? --[[User:Adlai|Adlai]] ([[User talk: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. --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|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. --[[User:Adlai|Adlai]] ([[User talk: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. <del>However better/novel/interesting and just plain weird alternative algorithms are of course also welcome, and each language can have more than one.</del> Oh, scratch that, I forgot this task specifically asks that Dijkstra's and Floyd-Warshall algorithms be used. --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]]) 17:19, 4 January 2021 (UTC)
| |||