52
15
The challenge
The shortest code by character count to help Robot find kitten in the fewest steps possible.
Golfers, this is a time of crisis - Kitten gone missing and it's Robot's job to find it! Robot needs to reach Kitten in the shortest path possible. However, there are a lot of obstacles in Robot's way, and he needs you to program a solution for him.
Robot used to have a program do it for him, but that program was lost and Robot have no backup :(.
Robot's runtime is not the best, and the least characters Robot has to read from the source code, the least time it will spend processing, and that means Kitten will be found faster!
Robot's memory contains a map of the location he is currently in with the top representing North, bottom representing South, right representing East and left representing West. Robot is always in a rectangular room of an unknown size surrounded by walls, represented by #
in his radar map. Areas Robot can walk in are represented by a space .
Robot's radar also scans for many obstacles in the room and marks them in various ASCII letters. Robot cannot walk across those obstacles. The radar will mark Kitten as the special ASCII character K
, while Robot's location is marked with R
.
Robot's navigation system works this way: He can understand a duo of direction and number of movement units he should travel to - for example, N 3
means 'go north 3 movement units'. Robot's radar map is made such that a movement unit is one ASCII character. Robot can only go in 4 directions and cannot travel diagonally.
Your task, brave Kitten saver, is to read Robot's radar map once, and output the least amount of directions, with the least movement unit travel distance. Robot is guaranteed to have at least one path to Kitten.
To ensure Robot does not waste time executing a malfunctioning program that will not help Robot find Kitten, I encourage you, brave Kitten saver, to use this output of Robot's past program to ensure no time is wasted on finding Kitten!
Test cases
Input:
######################
# d 3 Kj #
# #
# R #
# q #
######################
Output:
E 13
N 2
Input:
######################
# d r 3 Kj #
# p p #
# T X #
# q s t #
# #
# R o d W #
# #
# g t U #
# #
######################
Output:
N 1
E 10
N 4
E 2
Input:
######################
# spdfmsdlwe9mw WEK3#
# we hi #
# rdf fsszr#
# sdfg gjkti #
# fc d g i #
# dfg sdd #
# g zfg #
# df df #
# xcf R#
######################
Output:
N 1
W 9
N 5
E 4
N 1
E 4
N 1
Code count includes input/output (i.e full program).
1
Possibly inspired by this game? http://www.kongregate.com/games/Hamumu/robot-wants-kitty
– Nabb – 2011-02-06T05:02:01.8171
Nope, http://www.robotfindskitten.org/
– LiraNuna – 2011-02-06T05:05:01.7374The goal isn't unambigious. "output the least amount of directions, with the least movement unit travel distance." There might be a way with n directions and m steps and another one with less than n directions but more steps, or more directions and less steps. Is there an exchange rate? – user unknown – 2011-02-06T05:29:27.743
2Number of steps is better than number of direction. – LiraNuna – 2011-02-06T06:14:20.603
1If the idea is having the least number of steps, and break ties by the least number of directions, then the second example has a wrong solution. See my answer for a shortest path. – Daniel C. Sobral – 2011-02-06T18:35:53.690
Thank you Daniel, my example is fixed - I guess my demo app wasn't perfect :( – LiraNuna – 2011-02-06T22:00:11.047
@LiraNuna I came back from your link, my eyes hurts because the black-white contrasting :/ – ajax333221 – 2012-03-27T00:20:21.717
See my slightly less than perfect solution for a simple map that will detect distance non-optimization for some solvers. Mine included. A fine job of setting the challenge, as usual. – dmckee --- ex-moderator kitten – 2011-02-07T04:36:39.017
Is there a limit on the size of the radar map? I'd like to hard-code an arry in my C solution. – FUZxxl – 2012-07-29T17:31:26.053
@FUZxxl: "Robot is always in a rectangular room of an unknown size surrounded by walls", however people have "cheated" and got up to 99x99 grids in the past. That is not a concern, as golfers normally "cheat" to gain better number of strokes. – LiraNuna – 2012-08-04T00:36:09.217