4
\$\begingroup\$

Background

BitCycle is a two-dimensional Turing-complete programming language involves moving bits around a playfield.

Because I am too lazy to write BitCycle programs myself, you will be writing a program which outputs BitCycle programs for me! Unfortunately, the storage space on my computer is only about a bit, so you will have to make the BitCycle programs as small as possible.

How does BitCycle Work?

In BitCycle, a program is a 2D grid of characters (the playfield), implicitly right-padded with spaces to form a full rectangle. During execution, bits move around this playfield, encountering various devices that can trigger various effects. All bits move at the same time, which is once per tick.

A 0 or 1 in the program places a single bit of the specified type on the playfield at the start of execution, moving east.

The device ! is a sink. Any bit that hits it is output and removed from the playfield. For simplicity, your outputted program can only contain exactly one sink. Also, programs will be ran with the -u (unsigned integers) flag, which basically indicates that the program will output a positive integer based on how many 1's it receives before the program terminates. Passing a 0 into a sink will have other effects on the output, but for simplicity, outputted BitCycle programs should only pass 1's into the sink, or else the submission is invalid.

The devices <, ^, >, and v change a bit's direction unconditionally. For example, if a bit hits a <, it will start travelling to the left. The device + is a conditional direction change. An incoming 0 bit turns left; an incoming 1 bit turns right.

The devices \ and / are splitters. When the first bit hits them, they reflect it 90 degrees, like the mirrors in ><>. After one reflection, though, they change to their inactive forms - and |, which pass bits straight through.

The device = is a switch. The first bit that hits it passes straight through. If that bit is a 0, the switch becomes {, which redirects all subsequent bits to the west (like <). If the bit is a 1, the switch becomes }, which redirects all subsequent bits to the east (like >).

The device ~, dupneg, creates a negated copy of each incoming bit: if the bit is 0, then the copy is 1, and vice versa. The original bit turns right, and the copy turns left relative to its current direction of travel.

All splitters and switches on the playfield reset to their original states whenever one or more collectors come open (see below).

Any letter except V/v is a collector. A collector maintains a queue of bits. It has two states, closed (represented by an uppercase letter) and open (represented by the corresponding lowercase letter). In both states, bits that hit the collector are added to the end of its queue. When the collector is closed, bits stay in the queue. When it is open, bits are dequeued (one per tick) and sent out eastward from the collector. An open collector stays open until all its bits have been dequeued (including any that may have come in while it was open), at which point it switches back to closed.

There may be multiple collectors with the same letter. Each collector has a separate queue.

When there are no bits moving on the playfield (i.e. all the bits are in collectors), the program finds the earliest-lettered collector with a nonempty queue. All collectors with that letter will then open.

Once a collector is open, it stays open until its queue is emptied; but a closed collector will only open when there are no bits active on the playfield.

When any bit hits the device @, the program terminates. The program also terminates if there are no bits remaining, either on the playfield or in collectors. All unassigned characters are no-ops.

Two or more bits can occupy the same space at the same time. The ordering between them if they hit a collector, splitter, switch, or sink simultaneously is undefined (use at your own risk). Because different implementations of BitCycle deal with undefined behavior in different ways, your outputted BitCycle programs all have to run correctly on Try It Online!.

(Reference: GitHub Page for BitCycle)

Challenge

Given a positive integer as input, your program should output a valid BitCycle program (with the restriction of only having one sink) which outputs the input number and halts under the -u flag. Total score will be calculated by the sum of the lengths of the output BitCycle programs when your program is ran against the test cases shown below. Please provide your submission's score when answering.

If it is suspected that someone is hardcoding the output for this specific test suite, I can change existing test cases or even add new ones.

Test Suite

1
6
20
45
47
127
128
277
420
523
720
1000
2187
2763
4096
4555
7395
8718
9184
9997

Note

The challenge can be trivially solved by printing out the appropriate amount of 1's followed by a !. For example, 5 can be outputted as follows:

11111!

In order to be competitive, your program should aim to output BitCycle programs that are generally shorter than programs generated by this trivial method (especially for larger input numbers). In other words, your score should be less than 51983 (the score obtained when using the trivial method).


This is not , so don't feel obliged to golf your code in any way!

\$\endgroup\$
2

1 Answer 1

4
\$\begingroup\$

Python, scores 1186

Generates a binary to unary converter with a few tricks shortening specific bit patterns.

import re

def f(n):
    if n < 40:
        return n*'1' + '!'
    d = [x.replace('0', '') for x in bin(n)[2:]]
    q = d[1] == '1'
    del d[1]
    return '\n'.join([
        ' '*q + re.sub(r'(?<!^) >v ', ' >v', '>v'.join(d).replace(*'1 ').replace(*' 1', 1))+'~',
        '1'*q + re.sub(r'(?<!^)1~>1', '1~>', '~>'.join(d))+'+',
        ' '*q + re.sub(r'(?<!^) >\^ ', '1>^', '>^'.join(d).replace(*'1 ').replace(*' 1', 1))+'!'
    ])

Try it online and verify all cases!

Converts the number to binary and constructs the program from doublers:

>v
~>
>^

This doubles the number of bits moving east on the middle row. In the end all bits have to be converted to 1's, which can be done with

v~
>+
 !
\$\endgroup\$
2
  • 1
    \$\begingroup\$ If you use a ~ instead of a V or ^ in the top and bottom right of your doubling pattern you can guarantee all numbers will be ones and you can save a few bytes for your conversion at the end. Each step will invert the bits put into it so you'll need to alternate 1s and 0s in the input sequence. \$\endgroup\$
    – mousetail
    May 15 at 17:52
  • \$\begingroup\$ @mousetail thanks, that is a good suggestion. Before adding this, I'll have rewrite the code generation as string replacement is a bit limited for this. (I also have an additional optimization planned which should save a similar amount of bytes) \$\endgroup\$
    – ovs
    May 15 at 18:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.