Banana-only Scrabble, part 3

main.swift

//
//  main.swift
//  banana
//
//  Created by Greg Titus on 7/15/23.
//

import Foundation

import Cocoa

enum Letter: Hashable {
    case empty
    case b
    case a
    case n

    static let banana: [Letter] = [.b, .a, .n, .a, .n, .a]

    var matchingIndices: [Int8] {
        switch self {
        case .empty: return []
        case .b: return [0]
        case .a: return [1,3,5]
        case .n: return [2,4]
        }
    }
}

struct Position: Hashable, Comparable {
    let row: Int8
    let column: Int8

    var up: Position { Position(row: row-1, column: column) }
    var down: Position { Position(row: row+1, column: column) }
    var left: Position { Position(row: row, column: column-1) }
    var right: Position { Position(row: row, column: column+1) }

    static func < (lhs: Position, rhs: Position) -> Bool {
        lhs.row == rhs.row ? lhs.column < rhs.column : lhs.row < rhs.row
    }
}

struct Move: Hashable, Comparable {
    let position: Position
    let vertical: Bool
//    let firstPlayer: Bool

    static func < (lhs: Move, rhs: Move) -> Bool {
        if lhs.position == rhs.position {
            return lhs.vertical && !rhs.vertical
        } else {
            return lhs.position < rhs.position
        }
    }
}

struct Moves: Hashable {
    var hMoves: [Position] = []
    var vMoves: [Position] = []
    
    static let bananaLength: Int8 = 6

    func hMoveThatPlayed(_ p: Position) -> Position? {
        for move in hMoves {
            guard move <= p else { break }
            guard move.row == p.row else { continue }
            if move.column <= p.column && move.column > (p.column - Self.bananaLength) {
                return move
            }
        }
        return nil
    }

    func vMoveThatPlayed(_ p: Position) -> Position? {
        for move in vMoves {
            guard move <= p else { break }
            guard move.column == p.column else { continue }
            if move.row <= p.row && move.row > (p.row - Self.bananaLength) {
                return move
            }
        }
        return nil
    }

    func moveThatPlayed(_ p: Position) -> Move? {
        if let result = hMoveThatPlayed(p) {
            return Move(position: result, vertical: false)
        }
        if let result = vMoveThatPlayed(p) {
            return Move(position: result, vertical: true)
        }
        return nil
    }
}

struct Encoded: Hashable {
    let data: Data

    static func encode(_ ps: [Position]) -> Data {
        var result = Data(count: ps.count)
        for (p, index) in zip(ps, ps.indices) {
            result[index] = UInt8(p.row) << 4 | UInt8(p.column)
        }
        return result
    }

    static func decode(_ data: Data) -> ([Position], Int) {
        var result: [Position] = []
        for i in data.indices {
            let c = (data[i] & 15)
            let r = ((data[i] >> 4) & 15)
            guard c != 15, r != 15 else { return (result.sorted(), i+1) }
            result.append(Position(row: Int8(r), column: Int8(c)))
        }
        result.sort()
        return (result, data.count)
    }

    init(_ b: Board) {
        var data = Self.encode(b.history.hMoves)
        var divider = UInt8(255)
        data.append(&divider, count: 1)
        data.append(Self.encode(b.history.vMoves))
        self.data = data
    }
}

struct Board {
    static let size: Int8 = 15
    static let bananaLength: Int8 = 6
    var history: Moves

    init() {
        self.history = Moves()
    }

    init(_ e: Encoded) {
        let (h, i) = Encoded.decode(e.data)
        let (v, _) = Encoded.decode(e.data.advanced(by: i))
        self.history = Moves(hMoves: h, vMoves: v)
    }

    mutating func addBanana(_ startP: Position, vertical: Bool) {
        if vertical {
            history.vMoves.append(startP)
            history.vMoves.sort()
        } else {
            history.hMoves.append(startP)
            history.hMoves.sort()
        }
    }

    func byAdding(_ p: Position, vertical: Bool) -> Board {
        var result = self
        result.addBanana(p, vertical: vertical)
        return result
    }

    func moveThatPlayed(_ p: Position) -> Move? {
        history.moveThatPlayed(p)
    }

    func isEmpty(_ p: Position) -> Bool { moveThatPlayed(p) == nil }

    func verticallyInterferes(_ at: Position) -> Bool {
        history.vMoves.contains(where: { move in
            move.column == at.column && move.row <= at.row+6 && move.row >= at.row-6
        })
    }

    func canAddVertically(_ at: Position) -> Bool {
        guard at.row >= 0 else { return false }
        guard at.row + 5 < Board.size else { return false }
        guard !verticallyInterferes(at) else { return false }

        var p = at
        guard isEmpty(p.up) else { return false }
        for tile in Letter.banana {
            let match = history.hMoves.first(where: { $0.row == p.row && $0.column <= p.column+1 && $0.column >= p.column-6})
            if let match = match {
                guard tile.matchingIndices.contains(p.column - match.column) else { return false }
            } else {
                guard history.vMoveThatPlayed(p.left) == nil else { return false }
                guard history.vMoveThatPlayed(p.right) == nil else { return false }
            }
            p = p.down
        }
        guard isEmpty(p) else { return false }
        return true
    }

    func horizontallyInterferes(_ at: Position) -> Bool {
        history.hMoves.contains(where: { move in
            move.row == at.row && move.column <= at.column+6 && move.column >= at.column-6
        })
    }

    func canAddHorizontally(_ at: Position) -> Bool {
        guard at.column >= 0 else { return false }
        guard at.column + 5 < Board.size else { return false}
        guard !horizontallyInterferes(at) else { return false }

        var p = at
        guard isEmpty(p.left) else { return false }
        for tile in Letter.banana {
            let match = history.vMoves.first(where: { $0.column == p.column && $0.row <= p.row+1 && $0.row >= p.row-6})
            if let match = match {
                guard tile.matchingIndices.contains(p.row - match.row) else { return false }
            } else {
                guard history.hMoveThatPlayed(p.up) == nil else { return false }
                guard history.hMoveThatPlayed(p.down) == nil else { return false }
            }
            p = p.right
        }
        guard isEmpty(p) else { return false }
        return true
    }

    func nextMoves() -> [Board] {
        var result: [Board] = []
        for m in history.hMoves {
            var p = m
            for tile in Letter.banana {
                for index in tile.matchingIndices {
                    let p = Position(row: p.row-index, column: p.column)
                    if canAddVertically(p) {
                        result.append(self.byAdding(p, vertical: true))
                    }
                }
                p = p.right
            }
        }
        for m in history.vMoves {
            var p = m
            for tile in Letter.banana {
                for index in tile.matchingIndices {
                    let p = Position(row: p.row, column: p.column-index)
                    if canAddHorizontally(p) {
                        result.append(self.byAdding(p, vertical: false))
                    }
                }
                p = p.down
            }
        }
        return result
    }

    func description() -> String {
        func tileAt(_ p: Position) -> Letter {
            guard let move = moveThatPlayed(p) else { return .empty }
            let index = move.vertical ? p.row - move.position.row : p.column - move.position.column
            return Letter.banana[Int(index)]
        }

        var result = ""
        for row: Int8 in 0..<15 {
            for column: Int8 in 0..<15 {
                let c: Character
                switch tileAt(Position(row: row, column: column)) {
                case .a: c = "A"
                case .b: c = "B"
                case .n: c = "N"
                case .empty: c = "."
                }
                result.append(c)
            }
            result.append("\n")
        }
        return result
    }
}

var beginTime = Date()
var start = Board()
start.addBanana(Position(row: 7, column: 7), vertical: false)

var lastMoves: Set<Encoded> = [Encoded(start)]
var allEndings = 0
print("move 1: 1 move")
for move in 1..<32 {
    var new = Set<Encoded>()
    var endings = 0
    for e in lastMoves {
        let board = Board(e)
        let next = board.nextMoves()
        if next.isEmpty {
            if endings < 5 {
                print(board.description())
            }
            endings += 1
        } else {
            new.formUnion(next.map(Encoded.init))
        }
    }

    //print(Board(new.first!).description())

    let newMoves = new.count
    let branching = Double(newMoves) / Double(lastMoves.count)
    let time = (-beginTime.timeIntervalSinceNow).formatted(.number.precision(.fractionLength(2)))
    print("\(time) move \(move+1): \(newMoves.formatted()) moves, branch \(branching.formatted(.number.precision(.significantDigits(3))))")
    allEndings += endings
    print("end games: \(endings), total: \(allEndings)")
    lastMoves = new
    beginTime = Date()
}