A halfling is searching for treasure hidden in a maze in the dwarfs' mine. He has a map of the maze and would like to find the shortest path to the treasure.
The maze has a specific shape. It is placed on a square grid with M2 cells, where M = 2N+1+1 for some given size N. Each cell has coordinates (x, y), where 0 ≤ x, y < M, and can either be empty or contain a rock.
The mazes of sizes N = 1 and N = 2 are presented in the pictures below:
A maze of size N is constructed recursively from the layout of the maze of size N−1 (like the Hilbert curve). It contains four mazes of size N−1, each maze in one quarter. The maze in the bottom-left quarter is rotated by 90 degrees clockwise and the maze in the bottom-right quarter is rotated by 90 degrees counter-clockwise. The mazes in the top quarters are not rotated. There are three additional rocks (squares marked in green in the picture below) in the areas where the mazes intersect. The construction of the maze of size N = 3 is shown below:
The halfling would like to reach the treasure in the smallest number of steps possible. At each step, he can move to any one of the four adjacent cells (north, south, west, east) that does not contain a rock and is not outside of the grid.
For example, given N = 1, the halfling needs 8 steps to move from cell (2, 1) to cell (3, 4):
Write a function:
class Solution { public int solution(int N, int A, int B, int C, int D); }
that, given the size of the maze N, coordinates of the halfling (A, B) and coordinates of the treasure (C, D), returns the minimum number of steps required for the halfling to reach the treasure.
Examples
Given N = 1, A = 2, B = 1, C = 3 and D = 4 the function should return 8, as shown above.
Given N = 2, A = 2, B = 5, C = 6 and D = 6 the function should return 7:
Given N = 3, A = 6, B = 6, C = 10 and D = 13 the function should return 39:
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..25];
- A, B, C, D are integers within the range [0..2N+1];
- cells (A, B) and (C, D) do not contain rocks;
- the result will be an integer smaller than 2,147,483,647.
import Foundation
import Glibc
// you can write to stdout for debugging purposes, e.g.
// print("this is a debug message")
private struct Point {
var x = 0
var y = 0
}
private func ==(left: Point, right: Point) -> Bool {
return left.x == right.x && left.y == right.y
}
private func -(left: Point, right: Point) -> Int {
return abs(left.x - right.x) + abs(left.y - right.y)
}
private struct Maze {
let lowerLeft: Point
let upperRight: Point
}
private enum Orientation: Int {
case up, right, down, left
}
private let mazeOreintations: [Orientation] = [.up, .up, .left, .right, .up, .up, .left, .right]
private func +(left: Orientation, right: Orientation) -> Orientation {
return Orientation(rawValue: (left.rawValue + right.rawValue) % 4)!
}
private struct OrientedMaze {
let maze: Maze
let orientation: Orientation
func smallerMaze(forPoint point: Point) -> OrientedMaze {
let midX = (maze.lowerLeft.x + maze.upperRight.x) / 2
let midY = (maze.lowerLeft.y + maze.upperRight.y) / 2
if point.x <= midX && point.y <= midY {
return OrientedMaze(maze: Maze(lowerLeft: maze.lowerLeft, upperRight: Point(x: midX, y: midY)), orientation: mazeOreintations[(7 - orientation.rawValue) % 4] + orientation)
}
if point.x <= midX && point.y > midY {
return OrientedMaze(maze: Maze(lowerLeft: Point(x: maze.lowerLeft.x, y: midY), upperRight: Point(x: midX, y: maze.upperRight.y)), orientation: mazeOreintations[(4 - orientation.rawValue) % 4] + orientation)
}
if point.x > midX && point.y <= midY {
return OrientedMaze(maze: Maze(lowerLeft: Point(x: midX, y: maze.lowerLeft.y), upperRight: Point(x: maze.upperRight.x, y: midY)), orientation: mazeOreintations[(6 - orientation.rawValue) % 4] + orientation)
}
if point.x > midX && point.y > midY {
return OrientedMaze(maze: Maze(lowerLeft: Point(x: midX, y: midY), upperRight: maze.upperRight), orientation: mazeOreintations[(5 - orientation.rawValue) % 4] + orientation)
}
return OrientedMaze(maze: Maze(lowerLeft: Point(), upperRight: Point()), orientation: .up)
}
func moveOut(point: Point) -> Point {
if point.x == maze.lowerLeft.x || point.x == maze.upperRight.x || point.y == maze.lowerLeft.y || point.y == maze.upperRight.y {
return point
}
let midX = (maze.lowerLeft.x + maze.upperRight.x) / 2
let midY = (maze.lowerLeft.y + maze.upperRight.y) / 2
switch orientation {
case .up:
return point.y <= midY ? Point(x: midX, y: maze.lowerLeft.y) : Point(x: midX, y: maze.upperRight.y)
case .right:
return point.x <= midX ? Point(x: maze.lowerLeft.x, y: midY) : Point(x: maze.upperRight.x, y: midY)
case .left:
return point.x >= midX ? Point(x: maze.upperRight.x, y: midY) : Point(x: maze.lowerLeft.x, y: midY)
case .down:
return point.y >= midY ? Point(x: midX, y: maze.upperRight.y) : Point(x: midX, y: maze.lowerLeft.y)
}
}
}
public func solution(_ N : Int, _ A : Int, _ B : Int, _ C : Int, _ D : Int) -> Int {
let pointF = Point(x: A, y: B)
let pointS = Point(x: C, y: D)
if pointS == pointF {
return 0
}
let basicMazeSize = Int(pow(2, Double(N + 1)))
let basicMaze = Maze(lowerLeft: Point(x: 0, y: 0), upperRight: Point(x: basicMazeSize, y: basicMazeSize))
var mazesF = [OrientedMaze(maze: basicMaze, orientation: .up)]
var mazesS = [OrientedMaze(maze: basicMaze, orientation: .up)]
var i = 1
while i < N {
mazesF.append(mazesF.last!.smallerMaze(forPoint: pointF))
mazesS.append(mazesS.last!.smallerMaze(forPoint: pointS))
i += 1
}
var moveOutF = [pointF]
var moveOutS = [pointS]
for i in (0...mazesF.count - 1).reversed() {
moveOutF.append(mazesF[i].moveOut(point: moveOutF.last!))
moveOutS.append(mazesS[i].moveOut(point: moveOutS.last!))
}
var commonPoint = -1
i = 0
while i < moveOutF.count && commonPoint == -1 {
if moveOutF[i] == moveOutS[i] {
commonPoint = i
}
i += 1
}
var distance = 0
if commonPoint > -1 {
for _ in commonPoint...moveOutS.count - 1 {
moveOutS.removeLast()
moveOutF.removeLast()
}
distance = moveOutF.last! - moveOutS.last!
} else {
let endPointF = moveOutF.last!
let endPointS = moveOutS.last!
let minXF = min(endPointF.x, basicMazeSize - endPointF.x)
let minXS = min(endPointS.x, basicMazeSize - endPointS.x)
let minYF = min(endPointF.y, basicMazeSize - endPointF.y)
let minYS = min(endPointS.y, basicMazeSize - endPointS.y)
let minX = 2 * min(minXF, minXS) * (endPointS.y == endPointF.y ? 0 : 1)
let minY = 2 * min(minYF, minYS) * (endPointS.x == endPointF.x ? 0 : 1)
distance = endPointF - endPointS + minX + minY
}
i = moveOutF.count - 2
while i > -1 {
distance += (moveOutF[i] - moveOutF[i + 1]) + (moveOutS[i] - moveOutS[i + 1])
i -= 1
}
return distance
}
import Foundation
import Glibc
// you can write to stdout for debugging purposes, e.g.
// print("this is a debug message")
private struct Point {
var x = 0
var y = 0
}
private func ==(left: Point, right: Point) -> Bool {
return left.x == right.x && left.y == right.y
}
private func -(left: Point, right: Point) -> Int {
return abs(left.x - right.x) + abs(left.y - right.y)
}
private struct Maze {
let lowerLeft: Point
let upperRight: Point
}
private enum Orientation: Int {
case up, right, down, left
}
private let mazeOreintations: [Orientation] = [.up, .up, .left, .right, .up, .up, .left, .right]
private func +(left: Orientation, right: Orientation) -> Orientation {
return Orientation(rawValue: (left.rawValue + right.rawValue) % 4)!
}
private struct OrientedMaze {
let maze: Maze
let orientation: Orientation
func smallerMaze(forPoint point: Point) -> OrientedMaze {
let midX = (maze.lowerLeft.x + maze.upperRight.x) / 2
let midY = (maze.lowerLeft.y + maze.upperRight.y) / 2
if point.x <= midX && point.y <= midY {
return OrientedMaze(maze: Maze(lowerLeft: maze.lowerLeft, upperRight: Point(x: midX, y: midY)), orientation: mazeOreintations[(7 - orientation.rawValue) % 4] + orientation)
}
if point.x <= midX && point.y > midY {
return OrientedMaze(maze: Maze(lowerLeft: Point(x: maze.lowerLeft.x, y: midY), upperRight: Point(x: midX, y: maze.upperRight.y)), orientation: mazeOreintations[(4 - orientation.rawValue) % 4] + orientation)
}
if point.x > midX && point.y <= midY {
return OrientedMaze(maze: Maze(lowerLeft: Point(x: midX, y: maze.lowerLeft.y), upperRight: Point(x: maze.upperRight.x, y: midY)), orientation: mazeOreintations[(6 - orientation.rawValue) % 4] + orientation)
}
if point.x > midX && point.y > midY {
return OrientedMaze(maze: Maze(lowerLeft: Point(x: midX, y: midY), upperRight: maze.upperRight), orientation: mazeOreintations[(5 - orientation.rawValue) % 4] + orientation)
}
return OrientedMaze(maze: Maze(lowerLeft: Point(), upperRight: Point()), orientation: .up)
}
func moveOut(point: Point) -> Point {
if point.x == maze.lowerLeft.x || point.x == maze.upperRight.x || point.y == maze.lowerLeft.y || point.y == maze.upperRight.y {
return point
}
let midX = (maze.lowerLeft.x + maze.upperRight.x) / 2
let midY = (maze.lowerLeft.y + maze.upperRight.y) / 2
switch orientation {
case .up:
return point.y <= midY ? Point(x: midX, y: maze.lowerLeft.y) : Point(x: midX, y: maze.upperRight.y)
case .right:
return point.x <= midX ? Point(x: maze.lowerLeft.x, y: midY) : Point(x: maze.upperRight.x, y: midY)
case .left:
return point.x >= midX ? Point(x: maze.upperRight.x, y: midY) : Point(x: maze.lowerLeft.x, y: midY)
case .down:
return point.y >= midY ? Point(x: midX, y: maze.upperRight.y) : Point(x: midX, y: maze.lowerLeft.y)
}
}
}
public func solution(_ N : Int, _ A : Int, _ B : Int, _ C : Int, _ D : Int) -> Int {
let pointF = Point(x: A, y: B)
let pointS = Point(x: C, y: D)
if pointS == pointF {
return 0
}
let basicMazeSize = Int(pow(2, Double(N + 1)))
let basicMaze = Maze(lowerLeft: Point(x: 0, y: 0), upperRight: Point(x: basicMazeSize, y: basicMazeSize))
var mazesF = [OrientedMaze(maze: basicMaze, orientation: .up)]
var mazesS = [OrientedMaze(maze: basicMaze, orientation: .up)]
var i = 1
while i < N {
mazesF.append(mazesF.last!.smallerMaze(forPoint: pointF))
mazesS.append(mazesS.last!.smallerMaze(forPoint: pointS))
i += 1
}
var moveOutF = [pointF]
var moveOutS = [pointS]
for i in (0...mazesF.count - 1).reversed() {
moveOutF.append(mazesF[i].moveOut(point: moveOutF.last!))
moveOutS.append(mazesS[i].moveOut(point: moveOutS.last!))
}
var commonPoint = -1
i = 0
while i < moveOutF.count && commonPoint == -1 {
if moveOutF[i] == moveOutS[i] {
commonPoint = i
}
i += 1
}
var distance = 0
if commonPoint > -1 {
for _ in commonPoint...moveOutS.count - 1 {
moveOutS.removeLast()
moveOutF.removeLast()
}
distance = moveOutF.last! - moveOutS.last!
} else {
let endPointF = moveOutF.last!
let endPointS = moveOutS.last!
let minXF = min(endPointF.x, basicMazeSize - endPointF.x)
let minXS = min(endPointS.x, basicMazeSize - endPointS.x)
let minYF = min(endPointF.y, basicMazeSize - endPointF.y)
let minYS = min(endPointS.y, basicMazeSize - endPointS.y)
let minX = 2 * min(minXF, minXS) * (endPointS.y == endPointF.y ? 0 : 1)
let minY = 2 * min(minYF, minYS) * (endPointS.x == endPointF.x ? 0 : 1)
distance = endPointF - endPointS + minX + minY
}
i = moveOutF.count - 2
while i > -1 {
distance += (moveOutF[i] - moveOutF[i + 1]) + (moveOutS[i] - moveOutS[i + 1])
i -= 1
}
return distance
}
import Foundation
import Glibc
// you can write to stdout for debugging purposes, e.g.
// print("this is a debug message")
private struct Point {
var x = 0
var y = 0
}
private func ==(left: Point, right: Point) -> Bool {
return left.x == right.x && left.y == right.y
}
private func -(left: Point, right: Point) -> Int {
return abs(left.x - right.x) + abs(left.y - right.y)
}
private struct Maze {
let lowerLeft: Point
let upperRight: Point
}
private enum Orientation: Int {
case up, right, down, left
}
private let mazeOreintations: [Orientation] = [.up, .up, .left, .right, .up, .up, .left, .right]
private func +(left: Orientation, right: Orientation) -> Orientation {
return Orientation(rawValue: (left.rawValue + right.rawValue) % 4)!
}
private struct OrientedMaze {
let maze: Maze
let orientation: Orientation
func smallerMaze(forPoint point: Point) -> OrientedMaze {
let midX = (maze.lowerLeft.x + maze.upperRight.x) / 2
let midY = (maze.lowerLeft.y + maze.upperRight.y) / 2
if point.x <= midX && point.y <= midY {
return OrientedMaze(maze: Maze(lowerLeft: maze.lowerLeft, upperRight: Point(x: midX, y: midY)), orientation: mazeOreintations[(7 - orientation.rawValue) % 4] + orientation)
}
if point.x <= midX && point.y > midY {
return OrientedMaze(maze: Maze(lowerLeft: Point(x: maze.lowerLeft.x, y: midY), upperRight: Point(x: midX, y: maze.upperRight.y)), orientation: mazeOreintations[(4 - orientation.rawValue) % 4] + orientation)
}
if point.x > midX && point.y <= midY {
return OrientedMaze(maze: Maze(lowerLeft: Point(x: midX, y: maze.lowerLeft.y), upperRight: Point(x: maze.upperRight.x, y: midY)), orientation: mazeOreintations[(6 - orientation.rawValue) % 4] + orientation)
}
if point.x > midX && point.y > midY {
return OrientedMaze(maze: Maze(lowerLeft: Point(x: midX, y: midY), upperRight: maze.upperRight), orientation: mazeOreintations[(5 - orientation.rawValue) % 4] + orientation)
}
return OrientedMaze(maze: Maze(lowerLeft: Point(), upperRight: Point()), orientation: .up)
}
func moveOut(point: Point) -> Point {
if point.x == maze.lowerLeft.x || point.x == maze.upperRight.x || point.y == maze.lowerLeft.y || point.y == maze.upperRight.y {
return point
}
let midX = (maze.lowerLeft.x + maze.upperRight.x) / 2
let midY = (maze.lowerLeft.y + maze.upperRight.y) / 2
switch orientation {
case .up:
return point.y <= midY ? Point(x: midX, y: maze.lowerLeft.y) : Point(x: midX, y: maze.upperRight.y)
case .right:
return point.x <= midX ? Point(x: maze.lowerLeft.x, y: midY) : Point(x: maze.upperRight.x, y: midY)
case .left:
return point.x >= midX ? Point(x: maze.upperRight.x, y: midY) : Point(x: maze.lowerLeft.x, y: midY)
case .down:
return point.y >= midY ? Point(x: midX, y: maze.upperRight.y) : Point(x: midX, y: maze.lowerLeft.y)
}
}
}
public func solution(_ N : Int, _ A : Int, _ B : Int, _ C : Int, _ D : Int) -> Int {
let pointF = Point(x: A, y: B)
let pointS = Point(x: C, y: D)
if pointS == pointF {
return 0
}
let basicMazeSize = Int(pow(2, Double(N + 1)))
let basicMaze = Maze(lowerLeft: Point(x: 0, y: 0), upperRight: Point(x: basicMazeSize, y: basicMazeSize))
var mazesF = [OrientedMaze(maze: basicMaze, orientation: .up)]
var mazesS = [OrientedMaze(maze: basicMaze, orientation: .up)]
var i = 1
while i < N {
mazesF.append(mazesF.last!.smallerMaze(forPoint: pointF))
mazesS.append(mazesS.last!.smallerMaze(forPoint: pointS))
i += 1
}
var moveOutF = [pointF]
var moveOutS = [pointS]
for i in (0...mazesF.count - 1).reversed() {
moveOutF.append(mazesF[i].moveOut(point: moveOutF.last!))
moveOutS.append(mazesS[i].moveOut(point: moveOutS.last!))
}
var commonPoint = -1
i = 0
while i < moveOutF.count && commonPoint == -1 {
if moveOutF[i] == moveOutS[i] {
commonPoint = i
}
i += 1
}
var distance = 0
if commonPoint > -1 {
for _ in commonPoint...moveOutS.count - 1 {
moveOutS.removeLast()
moveOutF.removeLast()
}
distance = moveOutF.last! - moveOutS.last!
} else {
let endPointF = moveOutF.last!
let endPointS = moveOutS.last!
let minXF = min(endPointF.x, basicMazeSize - endPointF.x)
let minXS = min(endPointS.x, basicMazeSize - endPointS.x)
let minYF = min(endPointF.y, basicMazeSize - endPointF.y)
let minYS = min(endPointS.y, basicMazeSize - endPointS.y)
let minX = 2 * min(minXF, minXS) * (endPointS.y == endPointF.y ? 0 : 1)
let minY = 2 * min(minYF, minYS) * (endPointS.x == endPointF.x ? 0 : 1)
distance = endPointF - endPointS + minX + minY
}
i = moveOutF.count - 2
while i > -1 {
distance += (moveOutF[i] - moveOutF[i + 1]) + (moveOutS[i] - moveOutS[i + 1])
i -= 1
}
return distance
}
The solution obtained perfect score.