iko.soy/diskra/DZ2

turingTester.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 {
    var binInt: Int {
        return self == "0" ? 0 : 1
    }
}

class Tester {
    private let turing: TuringMachine<String>
    private var function: [Int: String] = [:]
    init(turing: TuringMachine<String>, function: [String]) {
        self.turing = turing
        for (k, v) in function.enumerated() {
            self.function[k] = v
        }
    }
    
    enum TestResult {
        case passed
        case loop
        case failed(expected: [String], got: [String])
    }
    
    func test(input: [String],a inA: [String], b inB: [String], c inC: [String]) -> TestResult {
        var expected: [String] = []
        var a = inA
        var b = inB
        var c = inC
        while a.count > 0 || b.count > 0 || c.count > 0 {
            let aa = a.popLast()?.binInt ?? 0
            let bb = b.popLast()?.binInt ?? 0
            let cc = c.popLast()?.binInt ?? 0
            let i = (aa << 2) + (bb << 1) + cc
            expected.append(function[i]!)
        }
        expected = Array(expected.reversed())
        switch turing.run(with: input) {
        case .loop:
            return .loop
        case .result(let res):
            if res == expected {
                //                print(expected.joined())
                return .passed
            } else {
                return .failed(expected: expected, got: res)
            }
        }
    }
}

extension Int {
    var toArray: [Bool] {
        if self == 0 {
            return [false]
        } else {
            var outp: [Bool] = []
            var temp = self
            while temp > 0 {
                outp.append(temp & 1 == 1)
                temp = temp >> 1
            }
            return Array(outp.reversed())
        }
    }
    func toArray(paddingTo: Int) -> [Bool] {
        let out = self.toArray
        let foo = paddingTo - out.count
        let count = foo > 0 ? foo : 0
        return Array(repeatElement(false, count: count)) + out
    }
}


func stringFromBytes(bytes: UnsafeMutablePointer<UInt8>, count: Int) -> String {
    return String((0..<count).map ({Character(UnicodeScalar(bytes[$0]))}))
}
func readStringFromFile(path: String) -> String {
    let fp = fopen(path, "r"); defer {fclose(fp)}
    var outputString = ""
    let chunkSize = 1024
    let buffer: UnsafeMutablePointer<UInt8> = UnsafeMutablePointer.allocate(capacity: chunkSize); defer {buffer.deallocate(capacity: chunkSize)}
    repeat {
        let count: Int = fread(buffer, 1, chunkSize, fp)
        guard ferror(fp) == 0 else {break}
        if count > 0 {
            outputString += stringFromBytes(bytes: buffer, count: count)
        }
    } while feof(fp) == 0
    
    return outputString
}

class TuringMachine<A: Hashable & Descriptable & Alphabet> {
    let names: [String]
    var states: [State<A>] = []
    init(names: [String]) {
        self.names = names
    }
    init(from s: String) {
        let ss = String(s.map({$0 == "\r\n" ? "\n" : $0})).split(separator: "\n").map {$0.split(separator: "\t", omittingEmptySubsequences: false)}
        let alphabet = ss.first!.dropFirst().map {String($0)}
        let alphabetIndexesToDrop = Set(alphabet.lazy.enumerated().map({(count: $0.element.count, index: $0.offset)}).filter({$0.count > 1}).map({$0.index}))
        self.names = ss.dropFirst().map {String($0.first!)}
        let mstates = ss.lazy.dropFirst().map({$0.dropFirst()}).enumerated().flatMap({ (arg) -> State<String> in
            let (j, inp) = arg
            var sss: [String: Operation<String>] = [:]
            for (i, cs) in inp.lazy.enumerated().filter({$0.element != ""}).filter({!alphabetIndexesToDrop.contains($0.offset)}) {
                if cs == "halt" {
                    sss[alphabet[i]] = Operation(place: alphabet[i], move: Direction.stay, next: .self)
                    continue
                }
                let opp = cs.split(separator: " ")
                let foo = String(opp[2]) == names[j]
                let nnext: NextState = foo ? .self : .other(names.index(of: String(opp[2]))!)
                sss[alphabet[i]] = Operation(place: String(opp[0]), move: Direction(rawValue: Character.init(String(opp[1])))!, next: nnext)
            }
            return State(name: names[j], operations: sss)
        })
        self.states = mstates as! [State<A>]
    }
    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 = Array(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}
    }
    
    enum TuringResult {
        case loop
        case result([A])
    }
    
    var maxNumberOfIterations = 10000000
    
    func run(with input: [A]) -> TuringResult {
        var tape = Tape(with: input)
        var currentState = 0
        for _ in 0...maxNumberOfIterations {
            let state = states[currentState]
            let operation = state.operations[tape.value]!
            if operation.move == .stay && operation.nextState == .self && operation.place == tape.value {
                return .result(tape.result)
            }
            tape.value = operation.place
            tape.move(operation.move)
            switch operation.nextState {
            case .other(let i):
                currentState = i
            case .self:
                break
            }
        }
        return .loop
    }
}

protocol Alphabet {
    static var empty: Self {get}
    var isEmpty: Bool {get}
}

extension String: Alphabet {
    static var empty: String {
        return "_"
    }
    var isEmpty: Bool {
        return self == String.empty
    }
}


extension Character: Alphabet {
    static var empty: Character {
        return "_"
    }
    var isEmpty: Bool {
        return self == Character.empty
    }
}

struct Tape<A> where A: Alphabet {
    var line: [A] = []
    init(with input: [A]) {
        self.line = input
    }
    private var index = 0
    mutating func move(_ direction: Direction) {
        switch direction {
        case .left:
            index -= 1
        case .right:
            index += 1
        case .stay:
            break
        }
    }
    var value: A {
        get {
            if index < 0 || index >= line.count {
                return A.empty
            } else {
                return line[index]
            }
        }
        set {
            if index < 0 {
                line = [newValue] + (1..<(-index)).map {_ in A.empty} + line
                index = 0
            } else if index >= line.count {
                line += (0..<(index - line.count)).map {_ in A.empty} + [newValue]
                index = line.count - 1
            } else {
                line[index] = newValue
            }
        }
    }
    
    var result: [A] {
        return Array(line.lazy.drop(while: {$0.isEmpty}).reversed().drop(while: {$0.isEmpty}).reversed())
    }
}

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"
}

extension String: Descriptable {
    func description() -> String {
        return self
    }
}

protocol Descriptable {
    func description() -> String
}

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]
        }
    }
}

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
    }
}


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
    }
}

var input: String?

let args = Array(CommandLine.arguments.dropFirst())

var i = 0
while i < args.count {
    switch args[i] {
    case "-i":
        if i + 1 < args.count {
            i += 1
            input = args[i]
        }
    default:
        print("I don't know what you are trying to do...\nBut I am still going to try my best.")
    }
    i += 1
}
if input == nil {
    print("You did not provide an input path")
    exit(0)
}
#if os(Linux)
let inp = readStringFromFile(path: input!)
#else
    
guard let inp = try? String.init(contentsOf: URL.init(fileURLWithPath: input!)) else {
    print("Something is wrong with the input path")
    exit(0)
}
#endif

let turing = TuringMachine<String>(from: inp)

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 tester = Tester(turing: turing, function: onesAndZeros.map {String($0)})
    
    let maxNumberOfBits = 9
    let maxNumber = 1 << (maxNumberOfBits * 3)
    
    func process(result: Tester.TestResult, with input: [String]) {
        switch result {
        case .passed:
            //            print("\(input.joined())\t ok")
            break
        case .loop:
            print("Looped on input:\t \(input.joined())")
            exit(0)
        case .failed(expected: let expexted, got: let got):
            print("Failed on:\t \(input.joined())\t Expected:\t \(expexted.joined())\t Got:\t \(got.joined())")
            exit(0)
        }
    }
    
    
    let max = Double(maxNumber)
    
    process(result: tester.test(input: ["*", "*"], a: ["0"], b: ["0"], c: ["0"]), with: ["*", "*"])
    
    for i in 0..<maxNumber {
        let a = i & ((1 << maxNumberOfBits) - 1)
        let b = (i >> maxNumberOfBits) & ((1 << maxNumberOfBits) - 1)
        let c = (i >> (maxNumberOfBits * 2)) & ((1 << maxNumberOfBits) - 1)
        let aa = a.toArray.map({$0 ? "1" : "0"})
        let bb = b.toArray.map({$0 ? "1" : "0"})
        let cc = c.toArray.map({$0 ? "1" : "0"})
        for ai in 0...2 {
            for bi in 0...2 {
                for ci in 0...2 {
                    let az = Array(repeatElement("0", count: ai)) + aa
                    let bz = Array(repeatElement("0", count: bi)) + bb
                    let cz = Array(repeatElement("0", count: ci)) + cc
                    let input = az + ["*"] + bz + ["*"] + cz
                    process(result: tester.test(input: input, a: az, b: bz, c: cz), with: input)
                }
            }
        }
        if i % 10000 == 0 {
            print(Double(i) * 100 / max, "%")
        }
    }
    print("You seem to be fine...")
} else {
    print("¯\\_(ツ)_/¯")
}