>g::g- :::+:+:+:+:++\::+:+:+:+:+:+\::+::+::+::+::+::++++++\::+::+:+:+:++\: v
v +::+:+::+::+::\+++++::+:+::+::+:::\+++::+::+:+:+::\++++::+::+:+:+:: <
> +++\:::+:+::+:+::++++\::+:+::+:+::+++\:::+::+:+:+::++++\::+::+:+:+: v
v \+++:+::+::+:+::\+++:+::+::+:+::\++::+:+:+:+::\+++::+:+:+:+:::\+++: <
> ::+\::+::+:++\::+:+:+:+:+:+\::+\::+:+::++\$pp v
Try it online!
A Brief History/Explanation: I originally started writing this answer when I saw Ethan Chapman's first Befunge-93 answer, but progress was hampered by the fact that I didn't know Befunge. I took a lunch break and by the time I came back, it had already been cracked (in a different way)! My original approach was simply to use
! to get 1 on the stack (it implicitly reads a 0 off the stack), and then just duplicate (
:) and add (
+) that to itself to create whatever numbers I needed.
Then, you can take advantage of Befunge's ability to modify the source code to write a
, into some specific location and then print off the stack as ASCII characters. It was easy enough to write the following snippet that prints off the entire stack, which also only has a single
, (which means it only requires one self-write).
v < (Whee!)
, Prints top of stack as ASCII character
>:| Duplicates top of stack, then pops, going down if zero, up otherwise
Fortunately, this general approach didn't change too much between the two answers. The main difference is that I can no longer use
! to get a 1 on top of the stack from the empty stack (I also can't use
@ to terminate, but that's not an issue, since we can just use another self-write for that).
Some simple process of elimination reveals that
x, then push value of ASCII character at location (x,y)) is just about the only way to get non-zero values onto the stack now. Since the stack is implicitly zero, the first
g we hit with an empty stack will simply push the value of character at (0,0). However, unlike some more convenient languages (cough, cough, 05AB1E), we don't have builtin operators to divide by 2 that we might use to reduce this value down to 1.
Thus, we need to use our ability to read again. The simplest way to do this is have the value at (0,0) be ASCII value v, and then put v-1 at (v,v). At this point, I ran into some problems with a lot of the Befunge-93 interpreters on TIO, since by default they only support a 25x80 program, and will complain about reads outside of this range. I can start with a space, which has ASCII value 32, but that's still out of bounds. Fortunately, the FBBI version works just fine, although I can't start with a space because for some reason it doesn't terminate unless you begin with a direction(?).
In any case, I can recover the magic
1 by starting with
> (value 62) at (0,0), then using
g:: to push 62 onto the stack and duplicate it twice, then using
g to read (62,62), where I have
= (value 61), and then finally subtract the top two elements of the stack, 62 and 61, in order to get 1.
From here, it's straightforward, if slightly painful. We just need to produce a stack that looks like our target string (in reverse order), followed by our two writes of
@ (denoted by
Y in the original source). While I could just duplicate the 1 several hundreds of times, I decided it was worth the effort to write a more efficient method, which encodes the target value in binary, then produces the binary decomposition on the stack, before summing (it's easy to get
1,4,16,32, for instance, because I can double with
This, plus the careful positioning of everything so the writes end up in the correct place, is a lot of work, so I just wrote a Python script that does it for me.
from collections import defaultdict
# by convention, assume there is a 1 on top of the stack
# goal is to produce stack:list[int]
if type(ch) is chr:
ch = ord(ch)
binary_decomp = 
cur = ch
while cur > 0: # I know this is inefficient
r = (1 << (cur.bit_length() - 1))
cur -= r
binary_decomp = binary_decomp[::-1]
total = ""
value = 1
for c in binary_decomp:
total += ":"
while value < c:
total += ":+"
value *= 2
return total + "+" * (len(binary_decomp) - 1) + "\\"
return "".join(gen_single(c) for c in stack)
# places string segment starting at (i,j) in given direction
def place_segment(prog, i, j, segment, direction=(1,0)):
for k, c in enumerate(segment):
prog[i + k*direction, j + k*direction] = c
target_string = """,0123456789"~@!"""
# [x,y], use implicit grid
prog = defaultdict(lambda : ' ')
W = 75
offset = 0
offset += place_segment(prog, offset, 0, ">g::g-") # ends at 6,0 excl
# store this for 1-recovery
prog[62,62] = "="
# now have 1 on stack
target_stack = list(map(ord,target_string))[::-1]
target_stack.extend([ord(","),2,10]) # write , to 2,10
target_stack.extend([ord("@"),2,12]) # write @ to 2,12
stack_generation = gen_stack(target_stack)
stack_generation += "$" # pop the 1
stack_generation += "p" # place the @
stack_generation += "p" # place the ,
# program flow routing
for i in range(8):
prog[W,i] = "<" if (i % 2 == 1) else "v"
prog[0,i] = "v" if (i % 2 == 1) else ">"
# makes it more aesthetically pleasing
offset += 1
row = 0
while len(stack_generation) > 0:
# zig-zag segment placement until we're out
if row % 2 == 0:
place_segment(prog, offset, row, stack_generation[:W-offset-1])
stack_generation = stack_generation[W-offset-1:]
place_segment(prog, W - 2, row, stack_generation[:W-offset-1], (-1,0))
stack_generation = stack_generation[W-offset-1:]
row += 1
# first 8 rows were allocated for the stack generation
# place the print-stack block
place_segment(prog, 0, 9, "v <")
place_segment(prog, 0, 10, " X")
place_segment(prog, 0, 11, ">:|")
place_segment(prog, 0, 12, " Y")
# print prog
max_y = max(k for k in prog.keys())
max_x = lambda y : max([0, *[k for k in prog.keys() if k == y]])
# just so we don't print tons of extra spaces
source = "\n".join("".join(prog[i,j] for i in range(max_x(j)+1)) for j in range(max_y+1))
for c in target_string:
if c in source:
print("Failed check for",c)