API tools faq
paste
Guest User

Untitled

a guest
Feb 3rd, 2018
105
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 13.15 KB | None | 0 0
raw download clone embed print report
  1. import Foundation
  2. #if os(Linux)
  3. import SwiftGlibc
  4.  
  5. SwiftGlibc.srandom(UInt32(time(nil)))
  6.  
  7. public func arc4random_uniform(_ max: UInt32) -> Int32 {
  8. return (SwiftGlibc.rand() % Int32(max-1))
  9. }
  10. #endif
  11.  
  12. extension String {
  13. func write(toFile path: String) -> Bool {
  14. let fp = fopen(path, "w"); defer {fclose(fp)}
  15. var byteArray: [UInt8] = self.utf8.map {$0}
  16. let count = fwrite(&byteArray, 1, byteArray.count, fp)
  17. return count == self.utf8.count
  18. }
  19. }
  20.  
  21. protocol Descriptable {
  22. func description() -> String
  23. }
  24.  
  25. class TuringMachine<A: Hashable & Descriptable> {
  26. let names: [String]
  27. var states: [State<A>] = []
  28. init(names: [String]) {
  29. self.names = names
  30. }
  31. func consume(states inStates: [[A: Operation<A>]?]) {
  32. states = inStates.enumerated().flatMap({ (i, s) in
  33. if let s = s{
  34. return State.init(name: self.names[i], operations: s)
  35. }
  36. return nil
  37. })
  38. }
  39.  
  40. func description(`for` alphabet: [A]) -> String {
  41. let alphabet = alphabet.shuffled()
  42. var out = [alphabet.map {$0.description()}.reduce("Q/A") {$0 + "\t\($1)"}]
  43. out.append((states.first?.description(alphabet: alphabet, names: self.names))!)
  44. out += states.dropFirst().shuffled().map {$0.description(alphabet: alphabet, names: self.names)}
  45. return out.dropFirst().reduce(out.first!) {$0 + "\n" + $1}
  46. }
  47. }
  48.  
  49. struct State<A: Hashable & Descriptable> {
  50. let name: String
  51. let operations: [A:Operation<A>]
  52. func description(alphabet: [A], names: [String]) -> String {
  53. return alphabet.lazy.map {self.operations[$0]?.description(selfName: self.name, names: names) ?? ""}
  54. .reduce(name) {"\($0)\t\($1)"}
  55. }
  56. }
  57.  
  58. enum Direction: Character {
  59. case left = "l"
  60. case right = "r"
  61. case stay = "n"
  62. }
  63.  
  64. class Operation<A: Hashable & Descriptable & Equatable>: Equatable {
  65. static func ==(lhs: Operation<A>, rhs: Operation<A>) -> Bool {
  66. return lhs.place == rhs.place && lhs.move == rhs.move && lhs.nextState == rhs.nextState
  67. }
  68.  
  69. func replace(_ i: Int, with j: Int) {
  70. if nextState == .other(i) {
  71. nextState = .other(j)
  72. }
  73. }
  74.  
  75. let place: A
  76. let move: Direction
  77. var nextState: NextState
  78. func description(selfName: String, names: [String]) -> String {
  79. return "\(place.description()) \(move.rawValue) \(nextState.description(selfName: selfName, names: names))"
  80. }
  81.  
  82. init(place: A, move: Direction, next: NextState) {
  83. self.place = place
  84. self.move = move
  85. self.nextState = next
  86. }
  87. }
  88.  
  89. enum NextState: Equatable {
  90. static func ==(lhs: NextState, rhs: NextState) -> Bool {
  91. switch lhs {
  92. case .self:
  93. switch rhs {
  94. case .self:
  95. return true
  96. default:
  97. return false
  98. }
  99. case .other(let n):
  100. switch rhs {
  101. case .other(let m):
  102. return m == n
  103. default:
  104. return false
  105. }
  106. }
  107. }
  108.  
  109. case `self`
  110. case other(Int)
  111. func description(selfName: String, names: [String]) -> String {
  112. switch self {
  113. case .self:
  114. return selfName
  115. case .other(let s):
  116. return names[s]
  117. }
  118. }
  119. }
  120.  
  121. enum Alphabet: Descriptable {
  122. static var aChar: Character = "a"
  123.  
  124. func description() -> String {
  125. switch self {
  126. case .zero:
  127. return "0"
  128. case .one:
  129. return "1"
  130. case .a:
  131. return String(Alphabet.aChar)
  132. case .none:
  133. return "_"
  134. case .star:
  135. return "*"
  136. }
  137. }
  138.  
  139. case zero
  140. case one
  141. case a
  142. case star
  143. case none
  144. }
  145.  
  146. extension MutableCollection {
  147. /// Shuffles the contents of this collection.
  148. mutating func shuffle() {
  149. let c = count
  150. guard c > 1 else { return }
  151.  
  152. for (firstUnshuffled, unshuffledCount) in zip(indices, stride(from: c, to: 1, by: -1)) {
  153. let d: IndexDistance = numericCast(arc4random_uniform(numericCast(unshuffledCount)))
  154. let i = index(firstUnshuffled, offsetBy: d)
  155. swapAt(firstUnshuffled, i)
  156. }
  157. }
  158. }
  159.  
  160. extension Sequence {
  161. /// Returns an array with the contents of this sequence, shuffled.
  162. func shuffled() -> [Element] {
  163. var result = Array(self)
  164. result.shuffle()
  165. return result
  166. }
  167. }
  168.  
  169. let alpha = "qwertyuiopasdfghjklzxcvbnm"
  170. var names: [String] {
  171. return alpha.map {c in alpha.map {"\(c)\($0)"}}
  172. .reduce([], (+)).shuffled()
  173. }
  174.  
  175. func generateMachine(function: [Alphabet]) -> TuringMachine<Alphabet> {
  176. let machine = TuringMachine<Alphabet>(names: names)
  177. var states: [[Alphabet: Operation<Alphabet>]] = [
  178. [ // 0
  179. .zero: Operation(place: .zero, move: .left, next: .self),
  180. .one: Operation(place: .one, move: .left, next: .self),
  181. .star: Operation(place: .star, move: .left, next: .self),
  182. .none: Operation(place: .star, move: .right, next: .other(2))
  183. ],
  184. [ // 1
  185. .zero: Operation(place: .zero, move: .right, next: .other(2)),
  186. .one: Operation(place: .one, move: .right, next: .other(2)),
  187. .a: Operation(place: .a, move: .right, next: .self),
  188. .star: Operation(place: .star, move: .right, next: .self),
  189. .none: Operation(place: .none, move: .left, next: .other(25))
  190. ],
  191. [ // 2
  192. .zero: Operation(place: .zero, move: .right, next: .self),
  193. .one: Operation(place: .one, move: .right, next: .self),
  194. .a: Operation(place: .a, move: .right, next: .self),
  195. .star: Operation(place: .star, move: .right, next: .self),
  196. .none: Operation(place: .none, move: .left, next: .other(3))
  197. ],
  198. [ // 3
  199. .zero: Operation(place: .none, move: .left, next: .other(4)),
  200. .one: Operation(place: .none, move: .left, next: .other(5)),
  201. .star: Operation(place: .star, move: .left, next: .other(6))
  202. ]
  203. ]
  204. states += (6...7).map {n in // 4-5
  205. [
  206. .zero: Operation(place: .zero, move: .left, next: .self),
  207. .one: Operation(place: .one, move: .left, next: .self),
  208. .star: Operation(place: .star, move: .left, next: .other(n))
  209. ]
  210. }
  211. states += [8, 10].map { n in // 6-7
  212. [
  213. .zero: Operation(place: .a, move: .left, next: .other(n)),
  214. .one: Operation(place: .a, move: .left, next: .other(n + 1)),
  215. .a: Operation(place: .a, move: .left, next: .self),
  216. .star: Operation(place: .star, move: .left, next: .other(n + 4))
  217. ]
  218. }
  219. states += (12...15).map {n in // 8-11
  220. [
  221. .zero: Operation(place: .zero, move: .left, next: .self),
  222. .one: Operation(place: .one, move: .left, next: .self),
  223. .star: Operation(place: .star, move: .left, next: .other(n))
  224. ]
  225. }
  226. states += [16, 18, 20, 22].map { n in //12-15
  227. [
  228. .zero: Operation(place: .a, move: .left, next: .other(n)),
  229. .one: Operation(place: .a, move: .left, next: .other(n + 1)),
  230. .a: Operation(place: .a, move: .left, next: .self),
  231. .star: Operation(place: .star, move: .left, next: .other(n))
  232. ]
  233. }
  234. let translation = [0, 4, 2, 6, 1, 5, 3, 7]
  235. states += (0..<function.count).map { n in // 16-23
  236. [
  237. .zero: Operation(place: .zero, move: .left, next: .self),
  238. .one: Operation(place: .one, move: .left, next: .self),
  239. .star: Operation(place: .star, move: .left, next: .self),
  240. .none: Operation(place: function[translation[n]], move: .right, next: .other(24))
  241. ]
  242. }
  243. states += [ // 24
  244. [ // 24
  245. .zero: Operation(place: .zero, move: .right, next: .self),
  246. .one: Operation(place: .one, move: .right, next: .self),
  247. .a: Operation(place: .a, move: .right, next: .self),
  248. .star: Operation(place: .star, move: .right, next: .other(1))
  249. ],
  250. // [ //25
  251. // .zero: Operation(place: .zero, move: .left, next: .self),
  252. // .one: Operation(place: .one, move: .left, next: .self),
  253. // .a: Operation(place: .a, move: .left, next: .self),
  254. // .star: Operation(place: .star, move: .left, next: .self),
  255. // .none: Operation(place: .zero, move: .right, next: .other(26))
  256. // ],
  257. // [ //26
  258. // .zero: Operation(place: .zero, move: .right, next: .self),
  259. // .one: Operation(place: .one, move: .right, next: .self),
  260. // .a: Operation(place: .a, move: .right, next: .self),
  261. // .star: Operation(place: .star, move: .right, next: .self),
  262. // .none: Operation(place: .none, move: .left, next: .other(27))
  263. // ],
  264. ]
  265. states += (26...28).map { n in // 25-27
  266. [ // 27
  267. .zero: Operation(place: .none, move: .left, next: .self),
  268. .one: Operation(place: .none, move: .left, next: .self),
  269. .a: Operation(place: .none, move: .left, next: .self),
  270. .star: Operation(place: .none, move: .left, next: .other(n))
  271. ]
  272. }
  273.  
  274. states += [
  275. // [ // 30
  276. // .zero: Operation(place: .zero, move: .left, next: .self),
  277. // .one: Operation(place: .one, move: .left, next: .self),
  278. // .none: Operation(place: .none, move: .right, next: .other(31))
  279. // ],
  280. // [ // 31
  281. // .zero: Operation(place: .none, move: .right, next: .self),
  282. // .one: Operation(place: .one, move: .stay, next: .self),
  283. // .none: Operation(place: .zero, move: .stay, next: .other(32))
  284. // ],
  285. [ // 32
  286. .zero: Operation(place: .zero, move: .stay, next: .self),
  287. .one: Operation(place: .one, move: .stay, next: .self),
  288. .a: Operation(place: .a, move: .stay, next: .self),
  289. .star: Operation(place: .star, move: .stay, next: .self),
  290. .none: Operation(place: .none, move: .stay, next: .self)
  291. ]
  292. ]
  293.  
  294. func optimize(states: [[Alphabet: Operation<Alphabet>]]) -> [[Alphabet: Operation<Alphabet>]?] {
  295. var inStates: [[Alphabet: Operation<Alphabet>]?] = states
  296. var didChange = true
  297. while didChange {
  298. didChange = false
  299. var i = 0
  300. while i < inStates.count {
  301. if let state = inStates[i] {
  302. for (j, nextState) in inStates.lazy.enumerated().dropFirst(i + 1) {
  303. if let nextState = nextState {
  304. if state.count == nextState.count && state.keys.reduce(true) {$0 && (state[$1] == nextState[$1])} {
  305. didChange = true
  306. // print(state.map {"\(i) \($0.key): \($0.value.description(selfName: "self", names: (0...32).map {String($0)}))"})
  307. // print(nextState.map {"\(j) \($0.key): \($0.value.description(selfName: "self", names: (0...32).map {String($0)}))"})
  308. // print()
  309. inStates[j] = nil
  310. inStates.forEach {$0?.values.forEach {$0.replace(j, with: i)}}
  311. }
  312. }
  313. }
  314. }
  315. i += 1
  316. }
  317. // inStates.forEach { print($0?.map {"\($0.key): \($0.value.description(selfName: "self", names: (0...32).map {String($0)}))"})}
  318. }
  319. return inStates
  320. }
  321. machine.consume(states: optimize(states: states))
  322. return machine
  323. }
  324.  
  325. //print(generateMachine(function: [.one, .zero,.one, .zero,.one, .zero,.one, .zero,]).description(for: [.a, .none, .one, .star, .zero]))
  326.  
  327. let args = Array(CommandLine.arguments.dropFirst())
  328. var out: String?
  329.  
  330. var i = 0
  331. while i < args.count {
  332. switch args[i] {
  333. case "-o":
  334. if i + 1 < args.count {
  335. i += 1
  336. out = args[i]
  337. }
  338. default:
  339. break
  340. }
  341. i += 1
  342. }
  343.  
  344. print("Please enter your function values F(0,0,0) F(0,0,1) ... F(1,1,1): ", separator: "", terminator: "")
  345. if let input = readLine(strippingNewline: true) {
  346. let onesAndZeros = input.filter({$0 == "0" || $0 == "1"})
  347. if onesAndZeros.count != 8 {
  348. print("Honestly, I was expecting 8 values...")
  349. exit(0)
  350. }
  351. let machine = generateMachine(function: onesAndZeros.map{$0 == "0" ? .zero : .one})
  352. let rez = machine.description(for: [.a, .none, .one, .star, .zero])
  353. #if os(Linux)
  354. if let out = out {
  355. if !rez.write(toFile: out) {
  356. print("Something went wrong with writing the file...\nI am just going to print to console")
  357. } else {
  358. exit(0)
  359. }
  360. }
  361.  
  362. #else
  363.  
  364. if let out = out {
  365. do {
  366. try rez.write(to: URL.init(fileURLWithPath: out), atomically: true, encoding: .utf8)
  367. exit(0)
  368. } catch {
  369. print("Something went wrong with writing the file...\nI am just going to print to console")
  370. }
  371. }
  372. #endif
  373. print("Copy the folowing text into a .txt file.")
  374. print("NOTE: you must preserve tabs. (Some text editors convert tabs to spaces.)")
  375. print(rez)
  376.  
  377. }
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!