From e6761723253fc9cd60e644bcaef35b833614340c Mon Sep 17 00:00:00 2001 From: j-james Date: Thu, 3 Nov 2022 23:42:03 -0700 Subject: Switch to bitsets for that sweet sweet 4% speed increase --- entries/jj/tm/tm.nim | 224 +++++++++++++++++++++++++-------------------------- 1 file 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) = -- cgit v1.2.3-70-g09d2 From 707163ddd8df67f4691f6f105a8b067974f6a4e6 Mon Sep 17 00:00:00 2001 From: j-james Date: Fri, 4 Nov 2022 03:37:36 -0700 Subject: Partial Wang tiling --- entries/jj/tiles/README.md | 7 +++++++ entries/jj/tiles/fib.png | Bin 0 -> 26917 bytes people.json | 4 ++++ 3 files changed, 11 insertions(+) create mode 100644 entries/jj/tiles/README.md create mode 100644 entries/jj/tiles/fib.png diff --git a/entries/jj/tiles/README.md b/entries/jj/tiles/README.md new file mode 100644 index 0000000..a7b5fd1 --- /dev/null +++ b/entries/jj/tiles/README.md @@ -0,0 +1,7 @@ +# Partial Wang Tiling + +These are Wang tiles. For more information, see https://en.wikipedia.org/wiki/Wang_tile. + +Provided that the third tile (the one with the North and West edges being black, the East edge being green, and the South edge being yellow) is placed down first, there is only one arrangement of tiles such that the tiles tile the infinite quarter-plane. This arrangement forms the Fibonacci numbers. 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 algorithm for this is adapted from https://grahamshawcross.com/2012/10/12/wang-tiles-and-turing-machines/ (with some fixes and optimizations). diff --git a/entries/jj/tiles/fib.png b/entries/jj/tiles/fib.png new file mode 100644 index 0000000..66e8404 Binary files /dev/null and b/entries/jj/tiles/fib.png differ 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" } ] }, -- cgit v1.2.3-70-g09d2 From 013fe632bfe4d9e9e4446d08998ac01863195000 Mon Sep 17 00:00:00 2001 From: j-james Date: Fri, 4 Nov 2022 14:28:54 -0700 Subject: Tweak tiles and add an example --- entries/jj/tiles/README.md | 8 +++++--- entries/jj/tiles/example.png | Bin 0 -> 94057 bytes entries/jj/tiles/fib.png | Bin 26917 -> 26282 bytes 3 files changed, 5 insertions(+), 3 deletions(-) create mode 100644 entries/jj/tiles/example.png diff --git a/entries/jj/tiles/README.md b/entries/jj/tiles/README.md index a7b5fd1..104d69e 100644 --- a/entries/jj/tiles/README.md +++ b/entries/jj/tiles/README.md @@ -1,7 +1,9 @@ -# Partial Wang Tiling +# Wang Tiling These are Wang tiles. For more information, see https://en.wikipedia.org/wiki/Wang_tile. -Provided that the third tile (the one with the North and West edges being black, the East edge being green, and the South edge being yellow) is placed down first, there is only one arrangement of tiles such that the tiles tile the infinite quarter-plane. This arrangement forms the Fibonacci numbers. 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. +There is only one arrangement of these tiles that tiles the infinite plane _aperiodically_. This arrangement forms the Fibonacci sequence. -The algorithm for this is adapted from https://grahamshawcross.com/2012/10/12/wang-tiles-and-turing-machines/ (with some fixes and optimizations). +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 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 Binary files /dev/null and b/entries/jj/tiles/example.png differ diff --git a/entries/jj/tiles/fib.png b/entries/jj/tiles/fib.png index 66e8404..7668696 100644 Binary files a/entries/jj/tiles/fib.png and b/entries/jj/tiles/fib.png differ -- cgit v1.2.3-70-g09d2 From 2b5ac5ef3264e56c373fd6bb7dc671e1b90329eb Mon Sep 17 00:00:00 2001 From: j-james Date: Sat, 5 Nov 2022 02:58:22 -0700 Subject: Embed pictures in the README --- entries/jj/tiles/README.md | 4 ++++ 1 file changed, 4 insertions(+) diff --git a/entries/jj/tiles/README.md b/entries/jj/tiles/README.md index 104d69e..ba10578 100644 --- a/entries/jj/tiles/README.md +++ b/entries/jj/tiles/README.md @@ -2,8 +2,12 @@ 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). -- cgit v1.2.3-70-g09d2