Skip to content

Instantly share code, notes, and snippets.

@supposedly
Last active May 19, 2018 02:19
Show Gist options
  • Save supposedly/80cb82bc8fb139317b166baef9256efc to your computer and use it in GitHub Desktop.
Save supposedly/80cb82bc8fb139317b166baef9256efc to your computer and use it in GitHub Desktop.
Bitwise Cyclic Tag as a Golly (http://golly.sourceforge.net/) ruletable.
"""
$ python3.6 bct_to_xrle.py "prgm tape" "data tape"
[or]
$ python3.6 bct_to_xrle.py
...then respond to prompts
"""
import itertools
import string
import sys
XNUM = string.printable[10:] # everything but digits
def _encode(*strs):
"""Encode given strings into Golly-compatible RLE"""
return [
''.join(
'{}{}'.format(len(s), s[0])
for s in (
''.join(g)
for _, g in itertools.groupby(i)
)
)
for i in strs
]
def _to_file(prgm, data):
"""Given prgm and data tapes, return as Golly XRLE w/ header"""
prgmlen = len(prgm)
width = 2 + prgmlen + len(data)
prgm, data = _encode(prgm[::-1], data)
file = f'E{1+prgmlen}.{data.upper()}$2.{prgm.upper()}${3+prgmlen}.E!'
return f'x = {width}, y = 3, rule = bct\n' + file
def undangle(prgm, data):
"""Fix dangling 1x instructions (i.e. prgms that go x...1)"""
if prgm[-1] == '0' or '0' not in prgm: # all 1s? doesn't matter then
return prgm, data
# now:
# since we effectively step the program forward one tick to
# eliminate the problem, we have to also step the data tape
# forward to match - by executing the first cmd of the prgm.
if prgm[0] == '0':
# Delete the leftmost data-tape bit, as a 0 usually does.
data = data[1:]
elif data[0] == '1':
# If prgm[0] == '1', the first two prgmtape bits will
# actually be parsed during normal execution as their
# own 1x instruction -- but only on the first cycle,
# because on subsequent runs the first bit will be
# parsed as part of the dangling 1x. So we account
# for that here by appending the second bit of this
# 'ghost' 1x to the right of the data tape iff its
# leftmost bit is 1.
data += prgm[1]
return prgm[1:] + prgm[0], data
def convert(prgm, data):
"""Do everything (including translating 01->AB/CD)"""
to_prgm = str.maketrans('01', 'CD', XNUM)
to_data = str.maketrans('01', 'AB', XNUM)
prgm, data = undangle(prgm, data)
return _to_file(prgm.translate(to_prgm), data.translate(to_data))
if __name__ == '__main__':
prgm, data = sys.argv[1:] or (input('Prgm tape: '), input('Data tape: '))
print(convert(prgm, data))
@RULE bct
An implementation of bitwise cyclic tag.
state 0: Vacuum.
state 1: Data-tape 0.
state 2: Data-tape 1.
state 3: Program-tape 0.
state 4: Program-tape 1.
state 5: Shifter. Moves both itself and the data tape one unit down to render program execution cyclic.
state 6: Transitory program-tape 0.
state 7: Transitory program-tape 1.
state 8: Pre-copying program-tape 0. (Used when a prgm-tape bit is the x in a 1x instruction)
state 9: Pre-copying program-tape 1. (Ditto)
state 10: Transitory program-tape 0.
state 11: Transitory program-tape 1.
state 12: Rightward-moving data-tape 0.
state 13: Rightward-moving data-tape 1.
state 14: Transitory reflector.
state 15: Ditto but about to turn into normal reflector.
state 16: To-be-moved-down data-tape 0.
state 17: To-be-moved-down data-tape 1.
@COLORS
1 235 235 235 lighter gray
2 30 30 30 darker gray
12 235 235 235 lighter gray
13 30 30 30 darker gray
16 235 235 235 lighter gray
17 30 30 30 darker gray
3 200 200 200 light gray
4 90 90 90 dark gray
5 0 255 255 cyan
14 0 255 255 cyan
15 0 255 255 cyan
@TABLE
n_states:18
neighborhood:Moore
symmetries:none
var anya={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17}
var anyb=anya
var anyc=anya
var anyd=anya
var anye=anya
var anyf=anya
var anyg=anya
var anyh=anya
var dataa={1,2}
var datab=dataa
var vacdataa={0,1,2}
var vacdatab=vacdataa
var rdataa={12,13}
var vacrdataa={0,12,13}
var ddataa={16,17}
var vacddataa={0,16,17}
# If a shifter is encountered, reflect + shift data tape down 2 cell
# go right
vacddataa,1,anya,anyb,anyc,anyd,anye,anyf,5,16
vacddataa,2,anya,anyb,anyc,anyd,anye,anyf,5,17
ddataa,0,anya,anyb,anyc,anyd,anye,anyf,5,0
# pull down
vacrdataa,16,anya,anyb,anyc,anyd,anye,anyf,anyg,12
vacrdataa,17,anya,anyb,anyc,anyd,anye,anyf,anyg,13
# go left
vacdataa,12,5,anya,anyb,anyc,anyd,anye,anyf,1
vacdataa,13,5,anya,anyb,anyc,anyd,anye,anyf,2
# Move rightward-moving data to the right
vacrdataa,anya,anyb,anyc,anyd,anye,anyf,rdataa,anyg,rdataa
rdataa,anya,anyb,anyc,anyd,anye,anyf,0,anyg,0
# shift the shifter down two as well
# right
0,5,anya,anyb,anyc,anyd,anye,0,rdataa,14
# left
0,5,dataa,0,anyb,anyc,anyd,anye,anyd,14
# finally
0,14,anya,anyb,anyc,anyd,anye,anyf,anyg,15
14,anya,anyb,anyc,anyd,anye,anyf,anyg,anyh,0
0,15,anya,anyb,anyc,anyd,anye,anyf,anyg,5
15,anya,anyb,anyc,anyd,anye,anyf,anyg,anyh,0
# delete shifter at end of its input stream
5,0,0,0,ddataa,0,0,0,0,0
5,0,0,0,0,0,dataa,0,0,0
# Shift prgm tape down 1 if rightward data above it
3,rdataa,anya,anyb,anyc,anyd,anye,anyf,anyg,10
4,rdataa,anya,anyb,anyc,anyd,anye,anyf,anyg,11
# If a data bit has a shifter to its right,don't attempt to copy it
dataa,anya,anyb,5,anyc,anyd,anye,anyf,anyg,0
# If a prgm-tape 1 is encountered, shift it downward
# and append the command to its left (by copying+shifting down) onto the right end of the data tape,
# if the leftmost bit is 1 -- otherwise just shift it down
# ----
# check the x in 1x
# leftmost bit 1?
3,anya,2,4,anyb,anyc,anyd,anye,anyf,8 # copy+shift down
4,anya,2,4,anyb,anyc,anyd,anye,anyf,9 # copy+shift down
# ----
# leftmost bit 0?
3,anya,1,4,anyb,anyc,anyd,anye,anyf,6 # just shift down
4,anya,1,4,anyb,anyc,anyd,anye,anyf,7 # just shift down
# ----
# shift the 1 in 1x down
4,dataa,anya,anyb,anyc,anyd,anye,anyf,anyg,7
0,7,anya,anyb,anyc,anyd,anye,anyf,anyg,11
# ----
# state 8 becomes state 1 and below it state 3
8,anya,anyb,anyc,anyd,anye,anyf,anyg,anyh,1
0,8,anya,anyb,anyc,anyd,anye,anyf,anyg,10
# state 9 becomes state 2 and below it state 4
9,anya,anyb,anyc,anyd,anye,anyf,anyg,anyh,2
0,9,anya,anyb,anyc,anyd,anye,anyf,anyg,11
# ----
# states 10 and 11 become 3 and 4 moving down
0,10,anya,anyb,anyc,anyd,anye,anyf,anyg,3
0,11,anya,anyb,anyc,anyd,anye,anyf,anyg,4
10,anya,anyb,anyc,anyd,anye,anyf,anyg,anyh,0
11,anya,anyb,anyc,anyd,anye,anyf,anyg,anyh,0
# If a bit of data has reached the right end of the tape,append it
# and delete the waiting data
dataa,anya,anyb,0,anyc,datab,anyd,anye,anyf,datab
# next line accounts for single-item data tape being appended to
dataa,anya,anyb,0,datab,anyd,anye,anyf,anyg,datab
dataa,datab,0,anya,anyb,anyc,anyd,anye,anyf,0
7,anya,anyb,anyc,anyd,anye,anyf,anyg,anyh,0
# If a prgm-tape 0 is encountered, shift it down and delete the leftmost data-tape bit
3,dataa,anya,anyb,anyc,anyd,anye,anyf,anyg,6
0,6,anya,anyb,anyc,anyd,anye,anyf,anyg,10 #3
6,anya,anyb,anyc,anyd,anye,anyf,anyg,anyh,0
# Delete the leftmost bit if a program-tape 0 is encountered
0,anya,anyb,dataa,3,anyc,anyd,anye,anyf,0
# Keep a data-tape bit in place if it's waiting below the data tape (to prepare for moving to the end)
dataa,datab,anya,anyb,anyc,anyd,anye,anyf,anyg,dataa
0,dataa,anya,datab,anyb,anyc,anyd,anye,anyf,0
# Move data tape to the left otherwise
0,anya,dataa,datab,anyb,anyc,anyd,anye,anyf,0
vacdataa,anya,anyb,vacdatab,anyc,anyd,anye,anyf,anyg,vacdatab
x = 53, y = 3, rule = bct
E43.B2AB2AB2A$2.5CDC3DCDC3DCDC3D2CDC3DC2DCDCDC3DCD$45.E!

...AKA:

5...........................................211211211
..333334344434344434344433434443443434344434.........
.............................................5.......

This simulates the Collatz sequence generator provided at http://esolangs.org/wiki/Bitwise_Cyclic_Tag#Example_.28Collatz_sequence.29, being:

BCT program: 10 11 10 10 10 11 0 11 10 10 0 11 10 10 11 10 10 11 10 10 0 0 0 0
Initial data string: 100100100

Its output compared to the chart given in the wiki can be verified by checking the data tape every time it reappears traveling rightward.

NOTE: A program executed through this cannot end in the middle of a 1x instruction due to how I've chosen to implement them. Fortunately, this is easily ameliorable: if a program string ends in a hanging 1, simply step the program forward by one tick to get the data tape as it looks after processing one instruction, then rotate the program string counterclockwise to put the first bit at the end and use these as the new initial state.


The program tape must be input in reverse, i.e. east to west, and its eastmost bit must be at a (−1-n, −1) {n>0} offset from the westmost bit of the data tape.

01 in a program tape correspond respectively to this rule's cell states 3 and 4, and the same in the data tape correspond to cell states 1 and 2.

To satisfy the 'Cyclic' part of 'Bitwise Cyclic Tag', a single state-5 cell must also be placed northwest of the program tape, or at a (−2-n, 1) {n>0} offset from the program's westmost bit. After this, a second state-5 cell must be placed two rows south of any cell in the data tape.


The included Python 3.6 script can be used to convert a traditionally-represented BCT program and data tape to an XRLE compatible with this rule.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment