Switch to bitsets for that sweet sweet 4% speed increase

1 files changed, 112 insertions, 112 deletions

diff --git a/entries/jj/tm/tm.nim b/entries/jj/tm/tm.nim
index 8710acb..71debe4 100644
--- a/entries/jj/tm/tm.nim
+++ b/entries/jj/tm/tm.nim
@@ -24,13 +24,13 @@ type State = enum
 
 type Transition = object
   current_state: State
-  read_symbol: seq[Symbol]
+  read_symbol: set[Symbol]
   next_state: State
   write_symbol: Symbol
   move_direction: Direction
 
 # convenience constructor
-func δ(a: State, b: seq[Symbol], c: State, d: Symbol, e: Direction): Transition =
+func δ(a: State, b: set[Symbol], c: State, d: Symbol, e: Direction): Transition =
   return Transition(current_state: a, read_symbol: b, next_state: c, write_symbol: d, move_direction: e)
 
 # safe get for an infinite tape: pretty, right?
@@ -46,116 +46,116 @@ func set(tape: var Tape, i: int, s: Symbol) =
   tape[i] = s
 
 let turing_machine = @[
-  δ(ca, @[`_`], cb, `$`, R),
-  δ(cb, @[`_`], cc, `0`, R),
-  δ(cc, @[`_`], cd, `$`, R),
-  δ(cd, @[`_`], ce, `1*`, R),
-  δ(ce, @[`_`], cf, `$`, R),
-  δ(cf, @[`_`], cg, `1`, R),
-  δ(cg, @[`_`], ch, `$`, R),
-  δ(ch, @[`_`], sa, noop, S),
-
-  δ(sa, @[`_`, `X`], sa, noop, L),
-  δ(sa, @[`$`], sb, noop, L),
-  δ(sb, @[`0*`, `1*`], sb, noop, L),
-  δ(sb, @[`0`], sc, `0*`, R),
-  δ(sb, @[`1`], sc, `1*`, R),
-  δ(sb, @[`$`], sd, noop, R),
-  δ(sc, @[`$`, `X`, `0*`, `1*`], sc, noop, R),
-  δ(sc, @[`_`], sa, `X`, L),
-  δ(sd, @[`$`, `X`], sd, noop, R),
-  δ(sd, @[`0*`], sd, `0`, R),
-  δ(sd, @[`1*`], sd, `1`, R),
-  δ(sd, @[`_`], aa, noop, L),
-
-  δ(aa, @[`X`, `0`, `1`], aa, noop, L),
-  δ(aa, @[`$`], ab, noop, L),
-  δ(ab, @[`0*`, `1*`], ab, noop, L),
-  δ(ab, @[`0`], aaa, `0*`, L),
-  δ(ab, @[`1`], aba, `1*`, L),
-  δ(ab, @[`$`], ac, noop, R),
-  δ(ac, @[`$`, `X`, `0`, `1`, `0*`, `1*`], ac, noop, R),
-  δ(ac, @[`_`], sa, `$`, R),
-
-  δ(aaa, @[`0`, `1`], aaa, noop, L),
-  δ(aaa, @[`$`], aab, noop, L),
-  δ(aab, @[`0*`], aac, `0`, R),
-  δ(aac, @[`$`, `X`, `0`, `1`, `0*`, `1*`], aac, noop, R),
-  δ(aac, @[`_`], aad, noop, L),
-  δ(aad, @[`0`, `1`], aad, noop, L),
-  δ(aad, @[`X`], aa, `0`, L),
-  δ(aab, @[`1*`], aae, `1`, R),
-  δ(aae, @[`$`, `X`, `0`, `1`, `0*`, `1*`], aae, noop, R),
-  δ(aae, @[`_`], aaf, noop, L),
-  δ(aaf, @[`0`, `1`], aaf, noop, L),
-  δ(aaf, @[`X`], aa, `1`, L),
-  δ(aab, @[`0`, `1`], aab, noop, L),
-
-  δ(aba, @[`0`, `1`], aba, noop, L),
-  δ(aba, @[`$`], abb, noop, L),
-  δ(abb, @[`0*`], abc, `0`, R),
-  δ(abc, @[`$`, `X`, `0`, `1`, `0*`, `1*`], abc, noop, R),
-  δ(abc, @[`_`], abd, noop, L),
-  δ(abd, @[`0`, `1`], abd, noop, L),
-  δ(abd, @[`X`], aa, `1`, L),
-  δ(abb, @[`1*`], abe, `1`, R),
-  δ(abe, @[`$`, `X`, `0`, `1`, `0*`, `1*`], abe, noop, R),
-  δ(abe, @[`_`], abf, noop, L),
-  δ(abf, @[`0`, `1`], abf, noop, L),
-  δ(abf, @[`X`], ba, `0`, L),
-  δ(abb, @[`$`], abc, noop, R),
-  δ(abb, @[`0`, `1`], abb, noop, L),
-
-  δ(ba, @[`X`, `0`, `1`], ba, noop, L),
-  δ(ba, @[`$`], bb, noop, L),
-  δ(bb, @[`0*`, `1*`], bb, noop, L),
-  δ(bb, @[`0`], baa, `0*`, L),
-  δ(bb, @[`1`], bba, `1*`, L),
-  δ(bb, @[`$`], bc, noop, R),
-  δ(bc, @[`$`, `X`, `0`, `1`, `0*`, `1*`], bc, noop, R),
-  δ(bc, @[`_`], za, noop, L),
-
-  δ(baa, @[`0`, `1`], baa, noop, L),
-  δ(baa, @[`$`], bab, noop, L),
-  δ(bab, @[`0*`], bac, `0`, R),
-  δ(bac, @[`$`, `X`, `0`, `1`, `0*`, `1*`], bac, noop, R),
-  δ(bac, @[`_`], bad, noop, L),
-  δ(bad, @[`0`, `1`], bad, noop, L),
-  δ(bad, @[`X`], aa, `1`, L),
-  δ(bab, @[`1*`], bae, `1`, R),
-  δ(bae, @[`$`, `X`, `0`, `1`, `0*`, `1*`], bae, noop, R),
-  δ(bae, @[`_`], baf, noop, L),
-  δ(baf, @[`0`, `1`], baf, noop, L),
-  δ(baf, @[`X`], ba, `0`, L),
-  δ(bab, @[`0`, `1`], bab, noop, L),
-
-  δ(bba, @[`0`, `1`], bba, noop, L),
-  δ(bba, @[`$`], bbb, noop, L),
-  δ(bbb, @[`0*`], bbc, `0`, R),
-  δ(bbc, @[`$`, `X`, `0`, `1`, `0*`, `1*`], bbc, noop, R),
-  δ(bbc, @[`_`], bbd, noop, L),
-  δ(bbd, @[`0`, `1`], bbd, noop, L),
-  δ(bbd, @[`X`], ba, `0`, L),
-  δ(bbb, @[`1*`], bbe, `1`, R),
-  δ(bbe, @[`$`, `X`, `0`, `1`, `0*`, `1*`], bbe, noop, R),
-  δ(bbe, @[`_`], bbf, noop, L),
-  δ(bbf, @[`0`, `1`], bbf, noop, L),
-  δ(bbf, @[`X`], ba, `1`, L),
-  δ(bbb, @[`$`], bbc, noop, R),
-  δ(bbb, @[`0`, `1`], bbb, noop, L),
-
-  δ(za, @[`0`, `1`], za, noop, L),
-  δ(za, @[`$`], zb, noop, R),
-
-  δ(zb, @[`0`], zc, `1`, R),
-  δ(zb, @[`1`], zb, `1`, R),
-  δ(zb, @[`_`], zd, `1`, R),
-
-  δ(zc, @[`0`], zc, `0`, R),
-  δ(zc, @[`1`], zb, `0`, R),
-  δ(zc, @[`_`], zd, `0`, R),
-
-  δ(zd, @[`_`], sa, `$`, R)
+  δ(ca, {`_`}, cb, `$`, R),
+  δ(cb, {`_`}, cc, `0`, R),
+  δ(cc, {`_`}, cd, `$`, R),
+  δ(cd, {`_`}, ce, `1*`, R),
+  δ(ce, {`_`}, cf, `$`, R),
+  δ(cf, {`_`}, cg, `1`, R),
+  δ(cg, {`_`}, ch, `$`, R),
+  δ(ch, {`_`}, sa, noop, S),
+
+  δ(sa, {`_`, `X`}, sa, noop, L),
+  δ(sa, {`$`}, sb, noop, L),
+  δ(sb, {`0*`, `1*`}, sb, noop, L),
+  δ(sb, {`0`}, sc, `0*`, R),
+  δ(sb, {`1`}, sc, `1*`, R),
+  δ(sb, {`$`}, sd, noop, R),
+  δ(sc, {`$`, `X`, `0*`, `1*`}, sc, noop, R),
+  δ(sc, {`_`}, sa, `X`, L),
+  δ(sd, {`$`, `X`}, sd, noop, R),
+  δ(sd, {`0*`}, sd, `0`, R),
+  δ(sd, {`1*`}, sd, `1`, R),
+  δ(sd, {`_`}, aa, noop, L),
+
+  δ(aa, {`X`, `0`, `1`}, aa, noop, L),
+  δ(aa, {`$`}, ab, noop, L),
+  δ(ab, {`0*`, `1*`}, ab, noop, L),
+  δ(ab, {`0`}, aaa, `0*`, L),
+  δ(ab, {`1`}, aba, `1*`, L),
+  δ(ab, {`$`}, ac, noop, R),
+  δ(ac, {`$`, `X`, `0`, `1`, `0*`, `1*`}, ac, noop, R),
+  δ(ac, {`_`}, sa, `$`, R),
+
+  δ(aaa, {`0`, `1`}, aaa, noop, L),
+  δ(aaa, {`$`}, aab, noop, L),
+  δ(aab, {`0*`}, aac, `0`, R),
+  δ(aac, {`$`, `X`, `0`, `1`, `0*`, `1*`}, aac, noop, R),
+  δ(aac, {`_`}, aad, noop, L),
+  δ(aad, {`0`, `1`}, aad, noop, L),
+  δ(aad, {`X`}, aa, `0`, L),
+  δ(aab, {`1*`}, aae, `1`, R),
+  δ(aae, {`$`, `X`, `0`, `1`, `0*`, `1*`}, aae, noop, R),
+  δ(aae, {`_`}, aaf, noop, L),
+  δ(aaf, {`0`, `1`}, aaf, noop, L),
+  δ(aaf, {`X`}, aa, `1`, L),
+  δ(aab, {`0`, `1`}, aab, noop, L),
+
+  δ(aba, {`0`, `1`}, aba, noop, L),
+  δ(aba, {`$`}, abb, noop, L),
+  δ(abb, {`0*`}, abc, `0`, R),
+  δ(abc, {`$`, `X`, `0`, `1`, `0*`, `1*`}, abc, noop, R),
+  δ(abc, {`_`}, abd, noop, L),
+  δ(abd, {`0`, `1`}, abd, noop, L),
+  δ(abd, {`X`}, aa, `1`, L),
+  δ(abb, {`1*`}, abe, `1`, R),
+  δ(abe, {`$`, `X`, `0`, `1`, `0*`, `1*`}, abe, noop, R),
+  δ(abe, {`_`}, abf, noop, L),
+  δ(abf, {`0`, `1`}, abf, noop, L),
+  δ(abf, {`X`}, ba, `0`, L),
+  δ(abb, {`$`}, abc, noop, R),
+  δ(abb, {`0`, `1`}, abb, noop, L),
+
+  δ(ba, {`X`, `0`, `1`}, ba, noop, L),
+  δ(ba, {`$`}, bb, noop, L),
+  δ(bb, {`0*`, `1*`}, bb, noop, L),
+  δ(bb, {`0`}, baa, `0*`, L),
+  δ(bb, {`1`}, bba, `1*`, L),
+  δ(bb, {`$`}, bc, noop, R),
+  δ(bc, {`$`, `X`, `0`, `1`, `0*`, `1*`}, bc, noop, R),
+  δ(bc, {`_`}, za, noop, L),
+
+  δ(baa, {`0`, `1`}, baa, noop, L),
+  δ(baa, {`$`}, bab, noop, L),
+  δ(bab, {`0*`}, bac, `0`, R),
+  δ(bac, {`$`, `X`, `0`, `1`, `0*`, `1*`}, bac, noop, R),
+  δ(bac, {`_`}, bad, noop, L),
+  δ(bad, {`0`, `1`}, bad, noop, L),
+  δ(bad, {`X`}, aa, `1`, L),
+  δ(bab, {`1*`}, bae, `1`, R),
+  δ(bae, {`$`, `X`, `0`, `1`, `0*`, `1*`}, bae, noop, R),
+  δ(bae, {`_`}, baf, noop, L),
+  δ(baf, {`0`, `1`}, baf, noop, L),
+  δ(baf, {`X`}, ba, `0`, L),
+  δ(bab, {`0`, `1`}, bab, noop, L),
+
+  δ(bba, {`0`, `1`}, bba, noop, L),
+  δ(bba, {`$`}, bbb, noop, L),
+  δ(bbb, {`0*`}, bbc, `0`, R),
+  δ(bbc, {`$`, `X`, `0`, `1`, `0*`, `1*`}, bbc, noop, R),
+  δ(bbc, {`_`}, bbd, noop, L),
+  δ(bbd, {`0`, `1`}, bbd, noop, L),
+  δ(bbd, {`X`}, ba, `0`, L),
+  δ(bbb, {`1*`}, bbe, `1`, R),
+  δ(bbe, {`$`, `X`, `0`, `1`, `0*`, `1*`}, bbe, noop, R),
+  δ(bbe, {`_`}, bbf, noop, L),
+  δ(bbf, {`0`, `1`}, bbf, noop, L),
+  δ(bbf, {`X`}, ba, `1`, L),
+  δ(bbb, {`$`}, bbc, noop, R),
+  δ(bbb, {`0`, `1`}, bbb, noop, L),
+
+  δ(za, {`0`, `1`}, za, noop, L),
+  δ(za, {`$`}, zb, noop, R),
+
+  δ(zb, {`0`}, zc, `1`, R),
+  δ(zb, {`1`}, zb, `1`, R),
+  δ(zb, {`_`}, zd, `1`, R),
+
+  δ(zc, {`0`}, zc, `0`, R),
+  δ(zc, {`1`}, zb, `0`, R),
+  δ(zc, {`_`}, zd, `0`, R),
+
+  δ(zd, {`_`}, sa, `$`, R)
 ]
 
 proc print(state: State, tape: Tape, position: int) =