30
11
Input:
A maze containing the characters:
--
(horizontal wall);|
(vertical wall);+
(connection);(walking space);
I
(entrance);U
(exit).
I.e. an input could look like this:
+--+--+--+--+--+--+--+--+--+--+
I | | |
+ +--+--+--+ + + + +--+ +
| | | | | |
+--+--+--+ +--+--+ + + +--+
| | | | |
+ +--+--+ + +--+--+ +--+ +
| | | | | |
+--+ + +--+--+ +--+--+ + +
| | | | | |
+ +--+--+--+ +--+--+ + + +
| | | | | |
+--+ + +--+--+ +--+--+--+--+
| | | | |
+ + +--+--+--+ +--+ + + +
| | | | | | | |
+--+--+ + +--+ + + +--+ +
| | | | | |
+ +--+--+--+ + + + + +--+
| | | | U
+--+--+--+--+--+--+--+--+--+--+
Output:
The most efficient path you should walk to get from the entrance to the exit of the maze (through the maze), indicated by the characters indicating left, right, up and down (i.e. >
; <
; ^
; v
).
Challenge rules:
- You can take the input in any reasonable format. String-array, single String with new-lines, 2D char-array, etc. are all possible input formats.
- The output can consist of any four distinct characters. I.e.
><^v
;→←↑↓
;⇒⇐⇑⇓
;RLUD
;0123
;ABCD
; etc.). - You are allowed to add spaces or trailing new-line to the output if preferred; this is optional.
- The steps are counted per square (see four
+
-symbols for the squares), and not per character. - The maze can be of size 5x5 through 15x15, and will always be a square (so there won't be any test cases for 5x10 mazes).
- You can assume that every maze has one or more valid paths from start to finish, and you always output the shortest (see test cases 4 and 5).
- If there are multiple paths with the same length, you can choose which one to output (see test case 6).
- You cannot 'walk' outside the borders of the maze (see test cases 7 and 8).
General rules:
- This is code-golf, so shortest answer in bytes wins.
Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language. - Standard rules apply for your answer, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters, full programs. Your call.
- Default Loopholes are forbidden.
- If possible, please add a link with a test for your code.
- Also, please add an explanation if necessary.
Test cases:
1. Input:
+--+--+--+--+--+--+--+--+--+--+
I | | |
+ +--+--+--+ + + + +--+ +
| | | | | |
+--+--+--+ +--+--+ + + +--+
| | | | |
+ +--+--+ + +--+--+ +--+ +
| | | | | |
+--+ + +--+--+ +--+--+ + +
| | | | | |
+ +--+--+--+ +--+--+ + + +
| | | | | |
+--+ + +--+--+ +--+--+--+--+
| | | | |
+ + +--+--+--+ +--+ + + +
| | | | | | | |
+--+--+ + +--+ + + +--+ +
| | | | | |
+ +--+--+--+ + + + + +--+
| | | | U
+--+--+--+--+--+--+--+--+--+--+
1. Output:
>v>>>vv<v>>v>v>>vvv>>>
2. Input:
+--+--+--+--+--+
I | | |
+ +--+--+ + +
| | | |
+ +--+ + + +
| | | | |
+ + +--+ + +
| | |
+--+ + +--+--+
| | U
+--+--+--+--+--+
2. Output:
>vvv>>v>>>
3. Input:
+--+--+--+--+--+
U | |
+ + +--+--+ +
| | | |
+--+--+ + +--+
| | |
+ +--+--+--+ +
| | | |
+ + + + +--+
| | I
+--+--+--+--+--+
3. Output:
<<<^<v<^^>>^<^<<
4. Input (test case with two valid paths):
+--+--+--+--+--+
U | |
+ + +--+--+ +
| | |
+--+--+ + +--+
| | |
+ +--+--+--+ +
| | | |
+ + + + +--+
| | I
+--+--+--+--+--+
4. Output:
<<^>^<^<<^<< (<<<^<v<^^>>^<^<< is less efficient, and therefore not a valid output)
5. Input (test case with two valid paths):
I
+--+--+--+--+--+--+--+--+--+--+ +--+--+--+--+
| | | | |
+ + + +--+--+--+ + +--+--+ +--+--+ + +
| | | | | | | |
+--+--+--+ +--+ + +--+--+--+--+ +--+--+--+
| | | | | | | | |
+ + + + + +--+ + + + +--+--+ +--+ +
| | | | | | | |
+ +--+--+--+ +--+--+ + +--+ +--+--+ +--+
| | | | | | | | |
+ +--+ + +--+ +--+--+ +--+--+ + +--+ +
| | | | | | |
+ + +--+--+--+--+ + +--+--+--+ +--+ +--+
| | | | | | | |
+--+--+--+ + +--+--+ +--+ + +--+ +--+ +
| | | | | | | |
+ +--+--+--+--+ + + +--+--+--+ + + + +
| | | | | | | | | |
+--+ + + + + + +--+--+ + + +--+ + +
| | | | | | | | | |
+--+ +--+--+ + + + +--+--+--+ + + + +
| | | | | | | | | |
+ +--+ +--+--+ + +--+--+ + +--+ + + +
| | | | | | | | | |
+--+--+--+ + + +--+ + +--+--+ +--+ + +
| | | | | | | |
+ + +--+--+--+--+ +--+--+ +--+--+ +--+ +
| | | | | |
+ + + +--+--+--+--+--+--+--+--+ +--+ +--+
| | | |
+--+--+--+--+--+--+--+--+--+ +--+--+--+--+--+
U
5. Output:
v<<<v<vv<<v<v>>^>>^^>vvv>>>v>vv<vv<<v<v<^<^^^^<vvvvv<^<v<<v>v>>>>>>>v (v<<<v<vv<<v<v>>^>>^^>vvv>>>v>vv<vv<<v<v<^<^^^^<vvvvv>v>>>^>>^>^^>vvv<v<v<<v is less efficient, and therefore not a valid output)
6. Input:
+--+--+--+--+--+
I |
+ + + + + +
| |
+ + + + + +
| |
+ + + + + +
| |
+ + + + + +
| U
+--+--+--+--+--+
6. Output:
>>v>v>v>v> or >v>v>v>v>> or >>>>>vvvv> or etc. (all are equally efficient, so all 10-length outputs are valid)
7. Input:
I U
+ + +--+--+--+
| | | |
+ +--+--+ + +
| | | |
+--+ + +--+ +
| | | |
+ +--+ + + +
| | |
+--+ +--+--+ +
| | |
+--+--+--+--+--+
7. Output:
vv>v>^>^<<^
8. Input:
+--+--+--+--+--+
| | |
+ +--+ +--+ +
I | | | |
+ + +--+ + +
U | | | |
+--+--+ + + +
| | | |
+ +--+--+--+ +
|
+--+--+--+--+--+
8. Output:
>v<
Mazes generated using this tool (and in some cases slightly modified).
Related 1; Related 2. (Been in the Sandbox since October 2016.) – Kevin Cruijssen – 2017-02-08T09:07:51.317
11I've found a shorter solution for the third test case!
v<<<<<<^^^^^
(always think outside the box) – Leo – 2017-02-08T10:29:12.6572If one can prove that their code will yield the shortest solution, given enough time and memory, does it compete? Even in the case of a really long running time (end of the universe fashion)? – Yytsi – 2017-02-08T18:57:40.877
@Leo Which one's the third? That solution doesn't work for any I could think of as the third. – None – 2017-02-08T19:00:34.137
1@JackBates It's a joke. He literally walks around the box to the exit :D – Yytsi – 2017-02-08T19:05:26.657
1I think the first test case is wrong, it should be
>v>>>vv<v>>v>v>>vvv>>>
. – smls – 2017-02-08T19:45:48.657@TuukkaX Oh. Didn't realize. – None – 2017-02-08T20:46:24.340
would graphical input be allowed, or does it have to be text? – 12Me21 – 2017-02-08T21:20:03.667
@smls You're indeed correct, fixed – Kevin Cruijssen – 2017-02-10T07:41:48.177
@12Me21 Sorry, the input has to be a maze with the characters you see in the question. How you insert them however is up to you. – Kevin Cruijssen – 2017-02-10T07:42:27.950
@TuukkaX As far as walking around the box is concerned, how does one avoid that? The
I
andU
characters are outside of the box. If they should happen to be on the same side of the box, there is a direct path that does not enter the maze. – Michael Vehrs – 2017-02-10T11:11:08.587@MichaelVehrs The OP has stated (with a grammar error) "though the maze", so solutions not walking through the maze are disallowed. – Yytsi – 2017-02-10T11:23:05.103
Kevin, I don't know if you've missed my comment regarding the time and memory. What's your response? – Yytsi – 2017-02-10T11:24:22.147
@TuukkaX Shouldn't that be a test case, then? – Michael Vehrs – 2017-02-10T11:29:33.597
@MichaelVehrs Sure. A one where U and I are adjacent, would be nice. – Yytsi – 2017-02-10T11:35:40.060
@TuukkaX I'll add a test case for I & U adjacent. Regarding the time/memory, if you can indeed prove it works then I guess it's fine, although I'm curious in what case it would work that long. – Kevin Cruijssen – 2017-02-10T11:40:04.200
1@KevinCruijssen For example, a solution that tests each combination of "v^<>" for a length up to the amount of empty boxes inside the maze. The right solution will be there, but takes astronomical time to compute. – Yytsi – 2017-02-10T11:45:04.387