6
In this challenge, your job is to find the straightest path from point A to point B in a two-dimensional maze. This is very similar to finding the shortest path, which has been done to death, but instead of minimizing the length of the path, you minimize the number of turns (or angles or corners, whatever you want to call them).
Input
A single string, divided into rows of equal lengths by either newlines or hyphens - (your choice). The rows form a rectangular maze, with . representing an empty space, # representing an impassable wall, and A and B representing the starting point and the goal. There is guaranteed to be exactly one A and exactly one B, and a path between them.
Output
The minimal number of turns in a path from A to B. The paths can only go in the four cardinal directions, not diagonally. Note that the number of turns is 0, if there is an unobstructed straight path from A to B.
Example
The shortest path in the maze on the left below is shown in the middle, while the straightest path is shown on the right. The turns are shown as plus signs +.
##......# ##...+-+# ##+--+..#
...#.B#.# ...#.B#|# ..|#.B#.#
.#.####.# .#.####|# .#|####.#
.#...#... .#...#++. .#|..#...
...#...#. ...#..|#. ..|#...#.
#......A# #.....+A# #.+----A#
The shortest path has length 10 and 5 turns, while the straightest path has length 14 and 3 turns. The correct output would be 3.
Additional Rules
You can write either a full program (STDIN to STDOUT) or a function. The shortest byte count wins, and standard loopholes are disallowed.
Your program need not be efficient, so brute forcing is allowed. However, there is a bonus of -20 % for being able to compute the final test case in a reasonable time (max. 15 minutes on my 6-year-old computer).
Test Cases
A trivial maze:
A..B
Output 0
A small maze:
##......#
...#.B#.#
.#.####.#
.#...#...
...#...#.
#......A#
Output 3
A medium-sized maze:
.....#..#.........##.
#.........#....##....
#..B#....##..........
...#...#.....##.....#
..#..##....##.....#..
#........#..........#
####....######.......
..A#......###...#####
..######..........###
........###........##
#....................
##...........########
Output 9
Another medium-sized maze, but slightly more complex:
......#####...#####............####.....
......#.....#.#...#....###...#..........
........#.#.#.#...#....#.....#....#...##
##....#...#..............##..#.#.##...##
#.....##.######.#.#..#####...#.......###
#..##.......#...#....#.....###....#...##
#...###...#.#.###....#.#.....###..#....#
#.....###.#...#......#.#####...##.#.....
##......#.##.......#...##...........#...
....#.....#.....#......#....#...........
A.........#..#......#..#B..........#####
Output 12
A large maze (A and B are in the corners):
##..#...#.##....#.#....###...##....#.....#........#....##..#...#......###..#........#.#..#.......#.A
###....##....##..#.......##...##......#.......#...#..#..........#.#........#...#..##.....#....##.#.#
..........#...#.#..#...##.#..#.###............#.##...#.#........#...#.#...####......#.#..#..........
.......##.....#.............#..##.....###.....#...#......##...#....#..##....######.#.##.......#.....
...##.#.......#..#.#.#...#......#....#..#.#.............................#.#.##..#.....#.#........#..
##.#..#..##......#...#..........#..#...##........#..#.....##.##...##.....#.##..###..#..#............
....#.#...#...#.#....##....#......#..##.....#.###..#..#.....#....#.#...#..###.#...###.....#...#...#.
...#..#.........##...#.....#..#..#.#.....#...........##...#.##..#.............#...#...##...#........
....#####..#..#..#...#..#.#........##...........#####...#.......##.#...##......#.....#.....#.##.....
.#..........#....#.##.....###.........#...........#......#.#.#..##.....#........#.#.##....##....#...
..#.....#....#....#....#......##.#...#..###...............#..............#....#..#..#.#..###...#....
...........##.##..#...#.#.#..........#..#.........#.##...######......................#..............
.....#.....#..#..........#..##..#.#..###...#..#.......#..#............#..#.#.##.......#.....##...#..
...###....#........#.##......#.#............#..##......#..###...##..#......#..#.#.#..#..#.#..##....#
......#.....#..#.#......##..#......#................#..####..#....#...........#..............#..#.#.
......#............#...#.#..#...#..##..............#....#..#........##..##.......#.....#...#.#......
........#...........##...............#.....#.#.....#.#.####.##..#...#.###.....#.....#...#.......#...
........##..###.....#.#...#....##......#.#..#......................#.#.##.#.#......#..#...#.##..#..#
.........#......#.......###............#.#.##...#...#........#..#..#.....#.#.......#....#...........
.##.......#.....#.##.#..#...###..........#......#..........#.....#.......#...#....##.#.......#.....#
..#.#....##..##......#..#.........#....#...#....#..#.#.#.....#..#.#..#..##....#.......#.##..#......#
.......##.....#....#.##.....##....#..........#.....##.........#........#...##......#.#....#....#....
....#.............#.#...........#.#.#......##......#.......###......#......#.##..#...#...#.#....#...
#...#....#.#.#...#..#.##..#.....##.......#.#......#....#..#.#.#.#....#.........#...#............#...
....#.......#.......#.#...............##........#.#..#..#.#..###.#..#.......##.#...#..##..#.#.......
...#....#..#..##.##..##.##.#....#......##.###..#.....#...##...........#.#..........##..#..#.#.......
...........#.#.#.##.#.#.##.##..###...#......#.#.#.......####.......#....###.........#.#.......##....
.........##.....#..#.#....#..##...#....###.....#......#..##.#.....#....#....##.#.......#........#..#
####.#....###......#..#....#..#.....#....#......#....#....#...#...............#....#.....#.##.##..#.
#..#.#...#...................#.#.#...........#....#.......#..............##...##.#......#....#.##...
#..#........#....#..............###..####...##.##..#...#....#...#....#.....#.........#..#..#..#.....
.....##.......##.......#.#....#...#.......#...##....#.......#....#...#.#........##...#.....##...####
.......##........#......##.....##...#..........##........#.....#..#.#.#.......#......##.......#.....
......##..#...#..........#....#......#..#....#...#.#...#..#....#.#.##...............#.....#.##...#.#
.#..##............###.#....#..#.......##...#...#.#...#...........##.........##.#.#........#..##.....
.............#....#....#..#.#.......#......#..##..#...#............#.#........##..####...#..........
..#....#####.#...##.#.#...........##.##...#.#.......#.##.###...#..#.#.......#....#..#......##.......
.........#..#....#..###.........#..#..#.##........#...................#.##.........###.........#.##.
..#..#..#.........#..#...........#...#.......#.##.......##.........#.#.....#...#.#...###...#...#..#.
B##.#..........#...........#.#.##...#......##....###.#..#.......................#....#.....#..#..#.#
Output 21
Zgarb
Posted 2015-01-13T16:57:05.027
Reputation: 39 083
@FryAmTheEggman Good point, I updated the condition. – Zgarb – 2015-01-13T17:21:22.653
This isn't very similar to finding the shortest path: it is finding the shortest path, which as you rightly state has been done to death. – Peter Taylor – 2015-01-13T18:13:36.397
@PeterTaylor And an almost exact duplicate too... should've done my research. :/ – Zgarb – 2015-01-13T18:24:38.130
Too bad, that this question got closed. Found a 255 char solution in Python (and I still see a few golfing opportunities). Way shorter solution than the other answers. But too lazy to implement printing of the directions. – Jakube – 2015-01-13T20:24:40.893
@PeterTaylor even though this is a dupe, finding straightest path is still not exactly equal to finding the shortest one. – Optimizer – 2015-01-13T22:57:37.383
@Optimizer, it is, it's just that the graph isn't the one normally associated with the textual representation. – Peter Taylor – 2015-01-13T23:07:57.833
@PeterTaylor I am talking wrt ASCII based maze (like this question). Lets not change the context please. – Optimizer – 2015-01-13T23:23:41.577
@Optimizer, I'm not changing the context, just explaining what I meant by my original comment. In fact, if someone wants to get a non-dupe question out of this one it would be to take the grid and output some nice representation of the graph over which it requires running a shortest path calculation. (I'm about to go to bed, so I'm not going to try to check my intuition that it's not always planar, but if it were then a planar representation ready to pass into http://codegolf.stackexchange.com/q/153/194 would be very cool).
– Peter Taylor – 2015-01-13T23:32:54.440@PeterTaylor I think you and I are not talking about the same thing here. The very first example in this question clearly proves that shortest path is not always the straightest. I am still not sure about what you meant in your original comment. – Optimizer – 2015-01-13T23:41:18.160