iko.soy/diskra/DZ2

turingSolver.swift

import Foundation
#if os(Linux)
    import SwiftGlibc
    
    SwiftGlibc.srandom(UInt32(time(nil)))
    
    public func arc4random_uniform(_ max: UInt32) -> Int32 {
        return (SwiftGlibc.rand() % Int32(max-1))
    }
#endif

extension String {
    func write(toFile path: String) -> Bool {
        let fp = fopen(path, "w"); defer {fclose(fp)}
        var byteArray: [UInt8] = self.utf8.map {$0}
        let count = fwrite(&byteArray, 1, byteArray.count, fp)
        return count == self.utf8.count
    }
}

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.dropFirst().reduce(out.first!) {$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(2))
        ],
        [ // 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))
        ]
    }
    let translation = [0, 4, 2, 6, 1, 5, 3, 7]
    states += (0..<function.count).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: function[translation[n]], move: .right, next: .other(24))
        ]
    }
    states += [ // 24
        [   // 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 += (26...28).map { n in // 25-27
        [   // 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),
            .one: Operation(place: .one, move: .stay, next: .self),
            .a: Operation(place: .a, move: .stay, next: .self),
            .star: Operation(place: .star, move: .stay, next: .self),
            .none: Operation(place: .none, 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]))

let args = Array(CommandLine.arguments.dropFirst())
var out: String?

var i = 0
while i < args.count {
    switch args[i] {
    case "-o":
        if i + 1 < args.count {
            i += 1
            out = args[i]
        }
    default:
        break
    }
    i += 1
}

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})
    let rez = machine.description(for: [.a, .none, .one, .star, .zero])
    #if os(Linux)
        if let out = out {
            if !rez.write(toFile: out) {
                print("Something went wrong with writing the file...\nI am just going to print to console")
            } else {
                exit(0)
            }
        }

        #else
        
    if let out = out {
        do {
            try rez.write(to: URL.init(fileURLWithPath: out), atomically: true, encoding: .utf8)
            exit(0)
        } catch {
            print("Something went wrong with writing the file...\nI am just going to print to console")
        }
    }
        #endif
    print("Copy the folowing text into a .txt file.")
    print("NOTE: you must preserve tabs. (Some text editors convert tabs to spaces.)")
    print(rez)
    
}