Solution to Befuddled

Back to Puzzle

Answer: MULTIPART

by Xander Hughes, Zack Chroman

The body of this puzzle is a program written in Befunge, an esoteric programming language developed in 1993. Befunge is a stack-based programming language, but it's different from most other languages in that its behavior is controlled by an instruction pointer on a 2D grid.

Finding/Identifying Outputs

When we run the Befunge program without an input, it prints 'XXXXX' and terminates. We inspect the program and see that it expects five characters of input (the ~ instruction in Befunge takes a character of input, and there are five of them). The flavortext helpfully provides five five-letter words: USAGE, INPUT, FIELD, VALUE, and WATCH. Inputting each of these words (in all-caps) yields five different outputs (still preceded by XXXXX, which we can ignore):

  1. USAGE: X=chobas;e${l:0:3} 8J+SrFjwn5Ks8J+Uo/CfkqziloHwn5Ks8J+Uo/CfjIrwn5KsMTHwn5Ks8J+UovCfkarwn5SN4p6hCg==|${l:3:3}e64 -d
  2. INPUT: {M[maA!sS!oO!f"ruhosup[pzp"=i<11>=/if*i*<1>as.?si.?s(sn).?<3>as.?s(ns).?Xo.?ii*<1>as.?=\]}
  3. FIELD: ;#35#49#48#53#4X!(((...#115#115..;#35#49#48#48#40!(((((.....#88.
  4. VALUE: Kj\w[k*3\W*4\Wr\x1k)J(2 3)=d15FNU6=+K"WWwWWWwvw";=+K+*\W2*\w11FN[4 7 9 11dd)=+K+*N\W\w;X
  5. WATCH: 
    " _")""";""_""""""""""""""";"_""""""".
    " (       (                 (        2
    1_";_94%X _                 _.23_.01 3
           :  "                        " "
           _  .                        1 _
           8  0                        _ .
           4%"1                        . 0
            ;                          " 1
            _                          8 1
            99._104._105._99._107.:_70%8 _
                                      ;  .
                                      _101

We next notice that there are words hidden in the Befunge program which don't seem to be part of an execution path. Further inspection shows that these are all names of programming languages (albeit obscure ones). The languages are, in no particular order: Bash, Chicken, Pyth, Emmental, Emoji, Labyrinth, Wepmlrio, Deadfish, Glass, and Grass. We look up the languages and see that the USAGE, INPUT, FIELD, VALUE, and WATCH outputs look like they're written in Bash, Glass, Emmental, Pyth, and Labyrinth, respectively.

Filling in Letters

None of these programs run properly on their respective interpreters, and all of them have an X somewhere in the program. We must now find the missing character that will cause the program to print good output. The following section goes in to detail about what's going on; skip to the next header for a summary.

USAGE

X=chobas;e${l:0:3} 8J+SrFjwn5Ks8J+Uo/CfkqziloHwn5Ks8J+Uo/CfjIrwn5KsMTHwn5Ks8J+UovCfkarwn5SN4p6hCg==|${l:3:3}e64 -d

This program is a command in Bash, a common UNIX shell. The ${} notation indexes into a variable, but the variable l isn't set to anything. Changing the X to l fixes this; e${l:0:3} and ${l:3:3}e64 resolve to the familiar commands echo and base64

The fixed program outputs:
💬X💬🔣💬▁💬🔣🌊💬11💬🔢👪🔍➡

INPUT

{M[maA!sS!oO!f"ruhosup[pzp"=i<11>=/if*i*<1>as.?si.?s(sn).?<3>as.?s(ns).?Xo.?ii*<1>as.?=\]}

This is a program written in Glass, an esoteric (and quite impractical) programming language. The program sets the variable f to the string "ruhosup[pzp" and indexes through it in reverse, shifting each character by 3 and then performing an unknown operation on it with Xo.?. No output has occured so far, so this unknown function must be output! The instruction oO! has set the name o to be an instance of the Output class, so we must change the X to o.

The fixed program outputs:

mwmXmrplero

FIELD

;#35#49#48#53#4X!(((...#115#115..;#35#49#48#48#40!(((((.....#88.

This is a program written in Emmental. In Emmental's syntax, the first section up to the ! redefines the ASCII character identified by the decimal number4X to mean the Emmental sequence #105, which pushes the number 105 to the stack. The ((( that immediately follows only makes sense if the character ( (ASCII #40) was the one just redefined. We can make it so by changing the X to a 0. This particular problem has a few solutions that look plausible, but only the stated solution outputs cleanly and explains the (((.

The fixed program outputs:

iiissdddddX

VALUE

Kj\w[k*3\W*4\Wr\x1k)J(2 3)=d15FNU6=+K"WWwWWWwvw";=+K+*\W2*\w11FN[4 7 9 11dd)=+K+*N\W\w;X

This is a Pyth program. Pyth is a golfing language that's essentially condensed Python. The program initializes the variable K with a character and then adds characters to it over the course of a few loops. At the end, the sequence X prints the contents of variable X. K, the variable that everything's been added to, hasn't been printed at all. Therefore the X should be a K

The fixed program outputs:
wWWWwWWWWwXwWWwWWWwvwWWwWWWwvwWWwWWWwvwWWwWWWwvwWWwWWWwvwWWwWWWwvwWWwwwwwwwwwwwWWWWwWWWWWWWwWWWWWWWWWwWWWWWWWWWWWwWWWWWWWWWWWWWWWwWWWWWWWWWWWWWWWw

WATCH

" _")""";""_""""""""""""""";"_""""""".
" (       (                 (        2
1_";_94%X _                 _.23_.01 3
       :  "                        " "
       _  .                        1 _
       8  0                        _ .
       4%"1                        . 0
        ;                          " 1
        _                          8 1
        99._104._105._99._107.:_70%8 _
                                  ;  .
                                  _101

This is a program written in Labyrinth, another 2D esoteric programming language. Run as is, the program never terminates. This is because it does not contain @, the Labyrinth 'stop' command. The X must be changed to @.

The fixed program outputs lots of chickens.

Filling in Letters, Part 2

We now recognise that these 5 new outputs are programs in the remaining 5 languages. Each has an X, and each also needs a replacement character to give good outputs. Incidentally, the first five characters we substituted in read lo0K@, which encouragingly looks like the first half of a cluephrase.

USAGE, Pt.2

💬X💬🔣💬▁💬🔣🌊💬11💬🔢👪🔍➡

This is an Emoji program. The program subtracts the numerical value of two unicode characters, multiplies it by 11, converts the number to a character, and prints it. There are a few possibilites that might make sense here; we'll come back to it later.

INPUT, Pt.2

mwmXmrplero

This is a program written in Wepmlrio, a (somewhat lazy) BrainFuck dialect. With the substitution of X with m, the program outputs the character U.

FIELD, Pt.2

iiissdddddX

This is a Deadfish program. It's missing the output instruction, which can be fixed by changing the X to o yields a program with output 76, the ASCII code for L.

VALUE, Pt.2

wWWWwWWWWwXwWWwWWWwvwWWwWWWwvwWWwWWWwvwWWwWWWwvwWWwWWWwvwWWwWWWwvwWWwwwwwwwwwwwWWWWwWWWWWWWwWWWWWWWWWwWWWWWWWWWWWwWWWWWWWWWWWWWWWwWWWWWWWWWWWWWWWw

Grass is an esoteric programming language rooted in lambda calculus. Working through it is a significant headache, but luckily the missing character can only be one of three values, so we can try all three fairly easily. Replacing X with v yields the output T.

WATCH, Pt.2

The program is written in Chicken, a programming language in which each line is some number of repeats of the word chicken. Since the only allowed word is chicken, the X must be replaced with e. The resulting program outputs I.

At this point we notice that all of the final outputs are uppercase characters. Of the options for the Emoji program, the substitution of X with outputs M, forming the word MULTI

Extraction

To recap, the initial five programs output by the Befunge code each had some missing character, marked with an X. When fixed, they each printed five new programs, each of which also needed a character substitution. These programs then each printed a single character.

The substituted characters spell lo0K@█move, and reading from the final outputs we obtain the word MULTI (using the other letters to resolve the Emoji ambiguity). MULTI is a five-letter word, so it can be plugged back in to the original Befunge program. When we do this, the instruction pointer (which looks like █) ends its motion by tracing out:

_ _ _ _ _ PART

This is easier to see if we slow down the interpreter. The below image shows what we see if we highlight every character the instruction pointer passes through:

Filling in the blanks with the previously obtained MULTI yields the puzzle answer, MULTIPART.

Authors’ Notes

This puzzle was a ton of fun to write, and taught us a bunch of weird languages we'd never seen before. The Befunge program as you see it is right at the program size limit in the 1993 spec, so a lot of work went into getting the character counts of the subcomponents (and their encodings in the overall program) as low as possible. If you're interested in esoteric programming languages, check out Chris Pressey's site - there are a lot of cool ones there we couldn't quite fit in.