//
//  main.swift
//  DiskraSolverHW2
//
//  Created by Ilya Kos on 11/17/17.
//  Copyright © 2017 Ilya Kos. All rights reserved.
//

import Foundation

protocol Descriptable {
    func description() -> String
}

class TuringMachine<A: Hashable & Descriptable> {
    let names: [String]
    var states: [State<A>] = []
    init(names: [String]) {
        self.names = names
    }
    func consume(states inStates: [[A: Operation<A>]?]) {
        states = inStates.enumerated().flatMap({ (i, s) in
            if let s = s{
                return State.init(name: self.names[i], operations: s)
            }
            return nil
        })
    }

    func description(`for` alphabet: [A]) -> String {
        let alphabet = alphabet.shuffled()
        var out = [alphabet.map {$0.description()}.reduce("Q/A") {$0 + "\t\($1)"}]
        out.append((states.first?.description(alphabet: alphabet, names: self.names))!)
        out += states.dropFirst().shuffled().map {$0.description(alphabet: alphabet, names: self.names)}
        return out.reduce("") {$0 + "\n" + $1}
    }
}

struct State<A: Hashable & Descriptable> {
    let name: String
    let operations: [A:Operation<A>]
    func description(alphabet: [A], names: [String]) -> String {
        return alphabet.lazy.map {self.operations[$0]?.description(selfName: self.name, names: names) ?? ""}
            .reduce(name) {"\($0)\t\($1)"}
    }
}

enum Direction: Character {
    case left = "l"
    case right = "r"
    case stay = "n"
}

class Operation<A: Hashable & Descriptable & Equatable>: Equatable {
    static func ==(lhs: Operation<A>, rhs: Operation<A>) -> Bool {
        return lhs.place == rhs.place && lhs.move == rhs.move && lhs.nextState == rhs.nextState
    }

    func replace(_ i: Int, with j: Int) {
        if nextState == .other(i) {
            nextState = .other(j)
        }
    }

    let place: A
    let move: Direction
    var nextState: NextState
    func description(selfName: String, names: [String]) -> String {
        return "\(place.description()) \(move.rawValue) \(nextState.description(selfName: selfName, names: names))"
    }

    init(place: A, move: Direction, next: NextState) {
        self.place = place
        self.move = move
        self.nextState = next
    }
}

enum NextState: Equatable {
    static func ==(lhs: NextState, rhs: NextState) -> Bool {
        switch lhs {
        case .self:
            switch rhs {
            case .self:
                return true
            default:
                return false
            }
        case .other(let n):
            switch rhs {
            case .other(let m):
                return m == n
            default:
                return false
            }
        }
    }

    case `self`
    case other(Int)
    func description(selfName: String, names: [String]) -> String {
        switch self {
        case .self:
            return selfName
        case .other(let s):
            return names[s]
        }
    }
}

enum Alphabet: Descriptable {
    static var aChar: Character = "a"

    func description() -> String {
        switch self {
        case .zero:
            return "0"
        case .one:
            return "1"
        case .a:
            return String(Alphabet.aChar)
        case .none:
            return "_"
        case .star:
            return "*"
        }
    }

    case zero
    case one
    case a
    case star
    case none
}

extension MutableCollection {
    /// Shuffles the contents of this collection.
    mutating func shuffle() {
        let c = count
        guard c > 1 else { return }

        for (firstUnshuffled, unshuffledCount) in zip(indices, stride(from: c, to: 1, by: -1)) {
            let d: IndexDistance = numericCast(arc4random_uniform(numericCast(unshuffledCount)))
            let i = index(firstUnshuffled, offsetBy: d)
            swapAt(firstUnshuffled, i)
        }
    }
}

extension Sequence {
    /// Returns an array with the contents of this sequence, shuffled.
    func shuffled() -> [Element] {
        var result = Array(self)
        result.shuffle()
        return result
    }
}

let alpha = "qwertyuiopasdfghjklzxcvbnm"
var names: [String] {
    return alpha.map {c in alpha.map {"\(c)\($0)"}}
        .reduce([], (+)).shuffled()
}

func generateMachine(function: [Alphabet]) -> TuringMachine<Alphabet> {
    let machine = TuringMachine<Alphabet>(names: names)
    var states: [[Alphabet: Operation<Alphabet>]] = [
        [ // 0
            .zero: Operation(place: .zero, move: .left, next: .self),
            .one: Operation(place: .one, move: .left, next: .self),
            .star: Operation(place: .star, move: .left, next: .self),
            .none: Operation(place: .star, move: .right, next: .other(1))
        ],
        [ // 1
            .zero: Operation(place: .zero, move: .right, next: .other(2)),
            .one: Operation(place: .one, move: .right, next: .other(2)),
            .a: Operation(place: .a, move: .right, next: .self),
            .star: Operation(place: .star, move: .right, next: .self),
            .none: Operation(place: .none, move: .left, next: .other(25))
        ],
        [ // 2
            .zero: Operation(place: .zero, move: .right, next: .self),
            .one: Operation(place: .one, move: .right, next: .self),
            .a: Operation(place: .a, move: .right, next: .self),
            .star: Operation(place: .star, move: .right, next: .self),
            .none: Operation(place: .none, move: .left, next: .other(3))
        ],
        [ // 3
            .zero: Operation(place: .none, move: .left, next: .other(4)),
            .one: Operation(place: .none, move: .left, next: .other(5)),
            .star: Operation(place: .star, move: .left, next: .other(6))
        ]
    ]
    states += (6...7).map {n in // 4-5
        [
            .zero: Operation(place: .zero, move: .left, next: .self),
            .one: Operation(place: .one, move: .left, next: .self),
            .star: Operation(place: .star, move: .left, next: .other(n))
        ]
    }
    states += [8, 10].map { n in // 6-7
        [
            .zero: Operation(place: .a, move: .left, next: .other(n)),
            .one: Operation(place: .a, move: .left, next: .other(n + 1)),
            .a: Operation(place: .a, move: .left, next: .self),
            .star: Operation(place: .star, move: .left, next: .other(n + 4))
        ]
    }
    states += (12...15).map {n in // 8-11
        [
            .zero: Operation(place: .zero, move: .left, next: .self),
            .one: Operation(place: .one, move: .left, next: .self),
            .star: Operation(place: .star, move: .left, next: .other(n))
        ]
    }
    states += [16, 18, 20, 22].map { n in //12-15
        [
            .zero: Operation(place: .a, move: .left, next: .other(n)),
            .one: Operation(place: .a, move: .left, next: .other(n + 1)),
            .a: Operation(place: .a, move: .left, next: .self),
            .star: Operation(place: .star, move: .left, next: .other(n))
        ]
    }
    states += function.map { n in // 16-23
        [
            .zero: Operation(place: .zero, move: .left, next: .self),
            .one: Operation(place: .one, move: .left, next: .self),
            .star: Operation(place: .star, move: .left, next: .self),
            .none: Operation(place: n, move: .right, next: .other(24))
        ]
    }
    states += [ // 24-26
        [   // 24
            .zero: Operation(place: .zero, move: .right, next: .self),
            .one: Operation(place: .one, move: .right, next: .self),
            .a: Operation(place: .a, move: .right, next: .self),
            .star: Operation(place: .star, move: .right, next: .other(1))
        ],
        [   //25
            .zero: Operation(place: .zero, move: .left, next: .self),
            .one: Operation(place: .one, move: .left, next: .self),
            .a: Operation(place: .a, move: .left, next: .self),
            .star: Operation(place: .star, move: .left, next: .self),
            .none: Operation(place: .zero, move: .right, next: .other(26))
        ],
        [   //26
            .zero: Operation(place: .zero, move: .right, next: .self),
            .one: Operation(place: .one, move: .right, next: .self),
            .a: Operation(place: .a, move: .right, next: .self),
            .star: Operation(place: .star, move: .right, next: .self),
            .none: Operation(place: .none, move: .left, next: .other(27))
        ],
    ]
    states += (28...30).map { n in // 27-29
        [   // 27
            .zero: Operation(place: .none, move: .left, next: .self),
            .one: Operation(place: .none, move: .left, next: .self),
            .a: Operation(place: .none, move: .left, next: .self),
            .star: Operation(place: .none, move: .left, next: .other(n))
        ]
    }

    states += [
        [ // 30
            .zero: Operation(place: .zero, move: .left, next: .self),
            .one: Operation(place: .one, move: .left, next: .self),
            .none: Operation(place: .none, move: .right, next: .other(31))
        ],
        [ // 31
            .zero: Operation(place: .none, move: .right, next: .self),
            .one: Operation(place: .one, move: .stay, next: .self),
            .none: Operation(place: .zero, move: .stay, next: .other(32))
        ],
        [ // 32
            .zero: Operation(place: .zero, move: .stay, next: .self)
        ]
    ]

    func optimize(states: [[Alphabet: Operation<Alphabet>]]) -> [[Alphabet: Operation<Alphabet>]?] {
        var inStates: [[Alphabet: Operation<Alphabet>]?] = states
        var didChange = true
        while didChange {
            didChange = false
            var i = 0
            while i < inStates.count {
                if let state = inStates[i] {
                    for (j, nextState) in inStates.lazy.enumerated().dropFirst(i + 1) {
                        if let nextState = nextState {
                            if state.count == nextState.count && state.keys.reduce(true) {$0 && (state[$1] == nextState[$1])} {
                                didChange = true
//                                print(state.map {"\(i) \($0.key): \($0.value.description(selfName: "self", names: (0...32).map {String($0)}))"})
//                                print(nextState.map {"\(j) \($0.key): \($0.value.description(selfName: "self", names: (0...32).map {String($0)}))"})
//                                print()
                                inStates[j] = nil
                                inStates.forEach {$0?.values.forEach {$0.replace(j, with: i)}}
                            }
                        }
                    }
                }
                i += 1
            }
//            inStates.forEach { print($0?.map {"\($0.key): \($0.value.description(selfName: "self", names: (0...32).map {String($0)}))"})}
        }
        return inStates
    }
    machine.consume(states: optimize(states: states))
    return machine
}

//print(generateMachine(function: [.one, .zero,.one, .zero,.one, .zero,.one, .zero,]).description(for: [.a, .none, .one, .star, .zero]))


print("Please enter your function values F(0,0,0) F(0,0,1) ... F(1,1,1): ", separator: "", terminator: "")
if let input = readLine(strippingNewline: true) {
    let onesAndZeros = input.filter({$0 == "0" || $0 == "1"})
    if onesAndZeros.count != 8 {
        print("Honestly, I was expecting 8 values...")
        exit(0)
    }
    let machine = generateMachine(function: onesAndZeros.map{$0 == "0" ? .zero : .one})
    print("Copy the folowing text into a .txt file.")
    print("NOTE: you must preserve tabs. (Some text editors convert tabs to spaces.)")
    print(machine.description(for: [.a, .none, .one, .star, .zero]))
}