dojo_01.swift

import Cocoa

//: Types to make my typing life simpler
typealias Cell = Int
typealias Board = [Cell]
typealias CellPosition = Int
typealias PackedBoard = Int64
typealias AddNeighbours = (Board, CellPosition) -> Cell
typealias SwapNeighbours = (Board, CellPosition) -> Board
typealias Mutator = (add:AddNeighbours, swap:SwapNeighbours)
typealias Operation = (origin:CellPosition, mutator:Mutator)

//: Factories for functions
func mutatorWithOffset(offset:CellPosition) -> Mutator {
    let add:AddNeighbours = { board, position in
        return board[position] + board[position + offset]
    }
    let swap:SwapNeighbours = { (var board, position) in
        let neighbourPosition = position + offset
        
        let temp = board[position]
        board[position] = board[neighbourPosition]
        board[neighbourPosition] = temp
        
        return board
    }
    
    return (add, swap)
}

//: Functions for accessing cells
let right = mutatorWithOffset(1)
let down = mutatorWithOffset(3)

//: Valid ranges the cell accessors can operate over
let rightValidRange = [0,1,3,4,6,7]
let downValidRange = [0,1,2,3,4,5]

let rightOps:[Operation] = rightValidRange.map {($0, right)}
let downOps:[Operation] = downValidRange.map {($0, down)}
let combinedOps:[Operation] = rightOps + downOps

//: The target board
let TargetBoard:Board = [
    1,2,3,
    4,5,6,
    7,8,9
]

//: Lets have a look at what values they fetch over valid ranges just
//: to check the seem to be working
//rightValidRange.map {
//    right.add(TargetBoard, $0)
//}
//
//downValidRange.map {
//    down.add(TargetBoard, $0)
//}

//: Some helper functions
func prime(n:Int) -> Bool {
    // Dealing with a limited set so lets cheat
    return contains([2,3,5,7,11,13,17], n)
}

func permutations(board:Board, ops:[Operation]) -> [Board] {
    let validOps = ops.filter {prime($0.mutator.add(board, $0.origin))}
    return validOps.map {$0.mutator.swap(board, $0.origin)}
}

//: Lets see what permuting the target board looks like. In theory this
//: is the start of generating all possible valid combinations
permutations(TargetBoard, combinedOps)

func rightDownPermutations(board:Board) -> [Board] {
    return permutations(board, combinedOps)
}

//: For laziness and to avoid writing comparitors, I'll just store a packed
//: representation of the board in a 64 bit value which can then be stuffed
//: into a set. This is what we'll check when looking to see if we've visited
//: a board before
func packBoard(board:Board) -> PackedBoard {
//    var x:PackedBoard = 0
//    
//    x |= Int64(board[0]) << (4 * 8)
//    x |= Int64(board[1]) << (4 * 7)
//    x |= Int64(board[2]) << (4 * 6)
//    x |= Int64(board[3]) << (4 * 5)
//    x |= Int64(board[4]) << (4 * 4)
//    x |= Int64(board[5]) << (4 * 3)
//    x |= Int64(board[6]) << (4 * 2)
//    x |= Int64(board[7]) << (4 * 1)
//    x |= Int64(board[8]) << (4 * 0)
//    
//    return x
    
//    return (Int64(board[0]) << (4 * 8)) |
//           (Int64(board[1]) << (4 * 7)) |
//           (Int64(board[2]) << (4 * 6)) |
//           (Int64(board[3]) << (4 * 5)) |
//           (Int64(board[4]) << (4 * 4)) |
//           (Int64(board[5]) << (4 * 3)) |
//           (Int64(board[6]) << (4 * 2)) |
//           (Int64(board[7]) << (4 * 1)) |
//           (Int64(board[8]) << (4 * 0))
    
    return board.reduce(PackedBoard(0)) { (var packed, cell) in
        let maskedCell = PackedBoard(0xf & cell)
        packed |= maskedCell
        packed <<= 4
        return packed
    }
}

//: Give it a whirl. A nice property of the packing algorithm is that when
//: viewed as hex, the board values are pretty straightforward
//let packed = packBoard(TargetBoard)
//NSString(format:"0x%llx, %llu", packed, packed)

//: Check the cunning plan for storing visited boards works

//var visited = Set<PackedBoard>();
//visited.insert(packBoard(TargetBoard))
//visited.contains(packBoard(TargetBoard))
//visited.contains(packBoard([9,8,7,6,5,4,3,2,1]))

//: Now lets try to solve a test problem
let TestBoard1:Board = [
    7,3,2,
    4,1,5,
    6,8,9
]

let TestBoard2:Board = [
    9,8,5,
    2,4,1,
    3,7,6
]

func solve(board:Board) -> Int {
    let packedTarget = packBoard(TargetBoard)
    var step = 0
    var visited = Set<PackedBoard>()
    var solved = false
    
    func unvisitedPermutations(board:Board) -> [Board] {
        let all:[Board] = rightDownPermutations(board)
        return all.filter { !visited.contains(packBoard($0)) }
    }
    
    func markVisited(boards:[Board]) {
        for board in boards {
            visited.insert(packBoard(board))
        }
    }
    
    markVisited([board])
    
    if visited.contains(packedTarget) {
        // Check if initial board was the final board
        return step
    }
    
    var boards = unvisitedPermutations(board)
    markVisited(boards)
    while boards.count > 0 {
        step++
        if visited.contains(packedTarget) {
            // Solved
            solved = true
            break
        }
        
        var nextLevel:[Board] = []
        for board in boards {
            let unvisited = unvisitedPermutations(board)
            markVisited(unvisited)
            nextLevel = nextLevel + unvisited
        }
        boards = nextLevel
    }
    
    return solved ? step : -1
}

func x(block: () -> ()) -> CFTimeInterval {
    let start = CACurrentMediaTime()
    block();
    let end = CACurrentMediaTime()
    return end - start
}

//print("Testing 3 boards: 0, 6, —1\n")

//let t1 = x { solve(TargetBoard) }
//print("\(t1)\n")

//let t2 = x { solve(TestBoard1) }
//print("\(t2)\n")

//let t3 = x { solve(TestBoard2) }
//print("\(t3)\n")

//print("Done!")





println("\(solve(TargetBoard))")
println("\(solve(TestBoard1))")
println("\(solve(TestBoard2))")