CrackingTheCode-Chap9.swift

import Foundation

//9.1

public func memoize<T:Hashable,U>(body: (T->U, T)->U) -> T->U {
    var memo = [T : U]()
    var result: (T->U)!
    result = { x in
        if let q = memo[x] { return q }
        let r = body(result, x)
        memo[x] = r
        return r
    }
    return result
}

///A child is running up a staircase with n steps, and can hop either 1step, 2 steps, or 3 steps at a time.
///Implement a method to count how many possible ways the child can run up the stairs.
public let countWays: Int -> Int = memoize { f, n in
    if n < 0 { return 0 }
    if n == 1 { return 1 }
    return f(n-3) + f(n-2) + f(n-1)
}

countWays(4)


//9.2

public enum Direction { case Up, Right, Down, Left}
public enum PositionError: ErrorType { case UnableToMoveToDirection(String) }

public struct Position<T>: Hashable {
    
    ///the current position
    public private(set) var position: (x: Int, y: Int)
    
    ///the map
    public let matrix: Matrix<T>
    
    //Hashable
    private let id: Int
    public var hashValue: Int {
        return "\(id),\(position.x),\(position.y)".hash
    }
    
    public init(atOriginWithMatrix matrix: Matrix<T>, initialPosition: (Int, Int) = (0,0), _id: Int = NSUUID().UUIDString.hash) {
        self.matrix = matrix
        self.position = initialPosition
        self.id = _id
    }
    
    ///Creates a new position in the directon passed as argument
    public func move(direction: Direction) throws -> Position<T> {
        
        func mv(increment: (Int,Int)) throws -> Position<T> {
            
            let (x,y) = (self.position.x + increment.0, self.position.y + increment.1)
            if x < 0 || y < 0 || x >= matrix.columns || y >= matrix.rows { throw PositionError.UnableToMoveToDirection("Unable to move to the desired direction") }
            
            //creates a new position
            return Position(atOriginWithMatrix: matrix, initialPosition: (x,y), _id: self.id)
        }
        
        switch direction {
        case .Up:   return try mv((0,1))
        case .Right: return try mv((1,0))
        case .Down: return try mv((1,0))
        case .Left: return try mv((-1,0))
        }
    }
    
    ///Returns 'true' if there's a possible path in the direction passed as argument,
    ///'false' otherwise
    public func canMove(direction: Direction) -> Bool {
        do {
            try move(direction)
            return true
            
        } catch {
            return false
        }
    }
}

public func ==<T>(lhs: Position<T>, rhs: Position<T>) -> Bool {
    return lhs.position.x == rhs.position.x && lhs.position.y == lhs.position.y && lhs.id == rhs.id
}

public typealias MatrixType = Int

///magine a robot sitting on the upper left comer of an X by Y grid.
///The robot can only move in two directions: right and down. How many possible paths are there for the robot to go from (0, 0) to (X, Y) ?
public let countPaths: Position<MatrixType> -> Int = memoize { f, p in

    if !p.canMove(Direction.Down) && !p.canMove(Direction.Right) {
        return 1
    }
    
    var result = 0
    
    if p.canMove(Direction.Down) {
        result += f(try! p.move(Direction.Down))
    }
    
    if p.canMove(Direction.Right) {
        result += f(try! p.move(Direction.Down))
    }
    
   return result
}

let matrix = Matrix<Int>(rows: 3, columns: 4, repeatedValue: 0)
let initialPosition = Position(atOriginWithMatrix: matrix)

countPaths(initialPosition)


//9.4

extension String {
    
    ///Write a method to compute all permutations of a string
    public func permutations() -> Set<String> {
        
        func str(charArray: [unichar]) -> String {
            return charArray.reduce("", combine: { return $0 + String(Character(UnicodeScalar($1))) })
        }
        
        func makePermutations(string: NSString, inout result: Set<String>) {
            
            if string.length == 0 { return }
            if string.length == 1 {
                result.insert(string as String)
                return
            }
            
            result.insert(string as String)

            //creates the char array
            var array = [unichar]()
            for var i = 0; i < string.length; i++ {
                array.append(string.characterAtIndex(i))
            }
            
            result.insert(str([array[0]]))
            makePermutations(string.substringFromIndex(1) as String, result: &result)
            
            //moves the char around
            for var i = 0; i < string.length; i++ {
                for var j = 0; j < string.length; j++ {
                    
                    //creates the substring
                    let sub = str(array)
                    
                    //adds it to the result
                    result.insert(sub)


                    let swap = array[i]
                    array[i] = array[j]
                    array[j] = swap
                }
            }
        
        }
        
        var result = Set<String>()
        makePermutations(self as NSString, result: &result)
        
        return result
    }
    
}

"ab".permutations().map() { return $0 }.count


//9.5

///Implement an algorithm to print all valid (i.e., properly opened and closed) 
///combi- nations ofn-pairs of parentheses.
public func parentheses(n: Int, before: String = "", after: String = "") -> [String] {
    
    if n == 0 { return [""] }
    if n == 1 { return ["\(before)()\(after)"] }
    
    var result = [String]()
    
    result += parentheses(n-1, before: "\(before)(", after: ")\(after)")
    result += parentheses(n-1, before: "\(before)()", after: "\(after)")
    result += parentheses(n-1, before: "\(before)", after: "()\(after)")

    var set = Set<String>()
    for s in result { set.insert(s) }
    
    return set.map() { return $0 }
}

parentheses(3)