Merge pull request #81 from j-james/main

Wang tiling

5 files changed, 129 insertions, 112 deletions

diff --git a/entries/jj/tiles/README.md b/entries/jj/tiles/README.md
new file mode 100644
index 0000000..ba10578
--- /dev/null
+++ b/entries/jj/tiles/README.md
@@ -0,0 +1,13 @@
+# Wang Tiling
+
+These are Wang tiles. For more information, see https://en.wikipedia.org/wiki/Wang_tile.
+
+![Wang tiles](fib.png)
+
+There is only one arrangement of these tiles that tiles the infinite plane _aperiodically_. This arrangement forms the Fibonacci sequence.
+
+Begin by placing down the third tile (the one with the North and West edges being black, the East edge being green, and the South edge being yellow), and continue by placing tiles such that the infinite plane can continue to be filled. The eleventh tile (the one with the North edge being black and the West, East, and South edges being purple) will appear in Fibonacci-spaced intervals.
+
+![The aperiodic tiling](example.png)
+
+The algorithm for this is adapted from https://grahamshawcross.com/2012/10/12/wang-tiles-and-turing-machines/ (with some fixes and tweaks).
diff --git a/entries/jj/tiles/example.png b/entries/jj/tiles/example.png
new file mode 100644
index 0000000..28b7365
--- /dev/null
+++ b/entries/jj/tiles/example.png
diff --git a/entries/jj/tiles/fib.png b/entries/jj/tiles/fib.png
new file mode 100644
index 0000000..7668696
--- /dev/null
+++ b/entries/jj/tiles/fib.png
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) =
diff --git a/people.json b/people.json
index 42d580b..bae371e 100644
--- a/people.json
+++ b/people.json
@@ -610,6 +610,10 @@
 			{
 				"name": "turing machine",
 				"link": "./entries/jj/tm/fib.txt"
+			},
+			{
+				"name": "wang tiling",
+				"link": "./entries/jj/tiles/fib.png"
 			}
 		]
 	},