--- Day 11: Forever and ever ---
It keeps running. And running. And the longer you sit there, staring at the blank output as the terminal's fans whir louder and louder, the heavier the pit in your stomach grows. Did you get it wrong? This soup delivery is critical to sustain those depending on it. Wait, maybe it was a different chara--
Before you can finish your thought, Patch blatantly remarks "This will never stop! We'll be here forever," yanking you back to reality. She shoves her way onto the console, and restarts the program, this time in debug mode.
"Nooooo!!" exclaims the head packing elf. "What if it would have finished right then?! And what do you know about JollyScript, anyway?"
"Maybe no more than you do," she admits, "but I do have some computer literacy. And look --" Patch points to the debug output. "It's not the triangular numbers that are the problem. It's some other module."
"Ah --" the elf blurted before he could stop himself, then froze, hoping nobody noticed. Patch whirled around, her gaze snapping to him, and he shrank back, caught red-handed.
"That module was written by a JollyScript intern. It hasn't been tested this year."
"So you're testing in production?"
"Uhh... maybe?"
As they argue, you squint at the code. Then it clicks. Your experience with JollyScript from the last fiasco leads you to realize the module only ever outputs the same thing -- it takes no input at all. If you can figure out what it outputs, you can cut the module entirely and just replace it with that result. The solution suddenly feels within reach. The pit in your stomach lightens slightly, replaced by a surge of focus.
JollyScript is an enterprise-grade language for intelligent elves. It's so festive, that every JollyScript program is shaped like a Christmas tree!
JollyScript operates on a stack of 4-bit integers, also known as nibbles.
The program is executed via a cursor on a 2-dimensional grid. The cursor starts at the asterisk symbol *, usually at the top of the tree, and moves downwards diagonally.
It can go either left or right, but its initial direction is left.
After the cursor encounters a command, it continues in the same direction as before, unless the command changes the direction. Here are the commands for JollyScript:
/: Set the direction to left.\: Set the direction to right.^: Fork the program into two serial (non-parallel) threads, one going left, and one going right. Run the left in the left direction completely. When that terminates, run the right branch.~: Terminate this thread.+: Pop a, then pop b. Push a + b onto the stack.-: Pop a, then pop b. Push b - a onto the stack.:: Duplicate the top of the stack.%: Swap the top two values of the stack.$: Pop and discard the top of the stack.?: Look at the top of the stack. If it is zero, set the direction to left. Otherwise, decrement the top of the stack, and set the direction to right.0-9, A-F: Push a hexadecimal digit onto the stack..: Print the top of the stack as a hexadecimal digit.": Toggle printing mode. Characters encountered will instead be printed until printing mode is turned off.n: Print a newline.{: Remember this cursor location (but not the direction).}: Go back to the location you remembered, continuing in the same direction.The following is an example program in JollyScript.
*
{
^ \
^ \ ^
^ - ? "
4 % . n #
5 . } n "
~~~~~~~~~~~~~
|_|
This is the output of the example program.
41
#00
As you grab your tools and head to the JollyScript Console, the elves cheer behind you. "You're the only one who can fix this! We believe in you!"
You've been tasked with optimising a program that would take too long to execute on traditional hardware. It may be useful to note that there exists source code for JollyScript interpreters online - but these won't be able to execute the program in a reasonable amount of time.
Can you find the number of 1s that would be printed by the program if it was run to completion?
Your answer should be total number of 1s. (e.g. for 11111, answer 5). Expect this number to be quite large - it won't fit in a standard 32-bit integer.