6
\$\begingroup\$

This question already has an answer here:

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
|improve this question
\$\endgroup\$

marked as duplicate by Peter Taylor code-golf Jan 13 '15 at 18:12

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • \$\begingroup\$ @FryAmTheEggman Good point, I updated the condition. \$\endgroup\$ – Zgarb Jan 13 '15 at 17:21
  • \$\begingroup\$ 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. \$\endgroup\$ – Peter Taylor Jan 13 '15 at 18:13
  • \$\begingroup\$ @PeterTaylor And an almost exact duplicate too... should've done my research. :/ \$\endgroup\$ – Zgarb Jan 13 '15 at 18:24
  • \$\begingroup\$ 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. \$\endgroup\$ – Jakube Jan 13 '15 at 20:24
  • \$\begingroup\$ @PeterTaylor even though this is a dupe, finding straightest path is still not exactly equal to finding the shortest one. \$\endgroup\$ – Optimizer Jan 13 '15 at 22:57