Stargate SG-1: Cute and Fuzzy (Improved version)
Description:
Note: This kata is the improved/corrected version of this one.
I'm not the original author but, while the former has quit codewars without correcting the bugs in his kata and letting it inconsistent with the description, the latter took a lot of time to debug the thing and improve it (the original algorithm didn't have full coverage), so I published it on my side (and that will make the maintenance easier...).
Enjoy!
I don't even know what they look like.
Furling... Sounds cute and fuzzy to me.
- Jonas Quinn and Jack O'Neill, "Paradise Lost".
Previously on Stargate SG-1
Arriving on P4F-976, SG-1 finally come into contact with the Furlings, one of the four great races within the Milky Way. After several days of deliberation with the Furling Directorate, the Tauri finally have access to the knowledge they have been searching for.
The Furlings, having provided assistance with the Ancient's expansion into the Milky Way, have extensive knowledge of the Stargate Network and it's components. One such component, the Dial Home Device, has caused many disasters at Stargate Command through it's absence. Thankfully, the Furlings have all the necessary blueprints for it's construction, and have handed copies over to the Tauri. After beginning mass production of the control crystals necessary for it's function, Stargate Command has hit a snag. The Ancients had designed the control crystals to function if their inner pathways are as efficient as possible - essentially, the pathways must choose the shortest path between two nodes. Stargate Command has turned to you - a software engineer - to fix their problems.
Your Mission
Given a string containing the current state of the control crystals inner pathways (labeled as "X"
) and its gaps (labeled as "."
), generate the shortest path from the start node (labeled as "S"
) to the goal node (labeled as "G"
) and return the new pathway (labeled with "P"
characters).
If no solution is possible, return the string "Oh for crying out loud..."
(in frustration).
The Rules
- Nodes labeled as
"X"
are not traversable. - Nodes labeled as
"."
are traversable. - A pathway can be grown in eight directions (up, down, left, right, up-left, up-right, down-left, down-right), so diagonals are possible.
- Nodes labeled
"S"
and"G"
are not to be replaced with"P"
in the case of a solution. - The shortest path is defined as the path with the shortest euclidean distance going from one node to the next.
- If several paths are possible with the same shortest distance, return any one of them.
Note that the mazes won't always be squares.
Example #1: Valid solution
.S... .SP..
XXX.. XXXP.
.X.XX => .XPXX
..X.. .PX..
G...X G...X
Example #2: No solution
S....
XX...
...XX => "Oh for crying out loud..."
.XXX.
XX..G
Note: Your solution will have to be efficient because it will have to deal with a lot of maps and big ones.
Caracteristics of the random tests:
- map sizes from 3x3 to 73x73 (step is 5 from one size to the other, mazes won't always be squares)
- 20 random maps for each size.
- Overall, 311 tests to pass with the fixed ones.
Similar Kata:
Stats:
Created | Jul 12, 2017 |
Published | Jul 12, 2017 |
Warriors Trained | 4618 |
Total Skips | 2698 |
Total Code Submissions | 12309 |
Total Times Completed | 606 |
Java Completions | 105 |
Python Completions | 333 |
JavaScript Completions | 135 |
C# Completions | 43 |
Total Stars | 231 |
% of votes with a positive feedback rating | 96% of 128 |
Total "Very Satisfied" Votes | 118 |
Total "Somewhat Satisfied" Votes | 9 |
Total "Not Satisfied" Votes | 1 |
Total Rank Assessments | 5 |
Average Assessed Rank | 3 kyu |
Highest Assessed Rank | 2 kyu |
Lowest Assessed Rank | 5 kyu |