Ping Pong 200 Solution
by Jakob Degen
FLAG: PP_0234FB97AA342D
This problem obviously has many solutions, but the code below is a working solution:
;`01#/ '1-=\!:@
\^'+`"`/
In order to solve this problem, we will begin by determining a layout for the two stacks. In the future, we will format all summaries of the contents of the stacks as follows:
(Main Stack Bottom) , (Main Stack 2nd from Bot) , (Main stack 3rd from Bot) , … , (Main Stack Top) || (Help Stack Top) , (Help Stack 2nd From top) , … , (Help Stack Bot).
If either side is empty then that side of the || will be left blank.
For example, 1,2,3,4 || 6,7,8 means that the main stack has 4,3,2,1 from top to bottom, and the help stack has 6,7,8 from top to bottom. An advantage of this is that we then know that we can only operate on the parts of the data close to the || divider.
In order to solve this problem, we will format our stack as follows: S|L || N + 1 where S and L are the two numbers that need to be added to create the next fibonacci number (each are fibonacci numbers of their own) and N + 1 a value we will discuss later.
We begin our program by getting the input with the ; command. Then we will push it onto the help stack, followed by pushing 0 and 1 onto the main stack. After this our stacks will contain 0,1 || (input). This is already the setup of the stack we want. In order to create the second fibonacci number, we need to add 0 (the “0th” fibonacci number, and 1, the first fibonacci number).
After all this is implemented our code will look like this:
;`01
It is now time to start computing Fibonacci numbers. We will need a loop in order to successively add them. Let’s begin by calculating how many times we need to run that loop. We will assume that we want L to be equal to the Fibonacci number that we want. Usually, we would simply have to run the loop N times, where N is the input, to get the nth Fibonacci number. However, here we begin with 1, which is already the first Fibonacci number. Therefore, we will need to run the loop N = input - 1 times. This gives us a definition for N, as seen before: The number of times that we still need to run our loop. This also shows why we can let N + 1 be equal to our input- We need to run the loop one time less than inputted. With this knowledge, as well as the format of the stacks as S,L || N + 1, we can then begin to build our loop. In our loop we will need to: 1. Check if we need to execute it again, 2. Decrement N + 1, and 3. Find the next S and L.
We can actually switch steps 1 and 2, and complete step 2 somewhat retroactively. So let’s begin by decrementing N + 1. In order to do this, we will first move it onto the main stack from the help stack, so that we can operate on it. Then we will push one onto the stack, followed by subtracting. Our stack will change like this: S,L || N + 1 => S,L,N + 1 || => S,L,N + 1,1 || => S,L,N ||. However, notice that the values for S, L, and N are still the same, we have only changed the things inside the stack. We will leave N where it is for now, it can be moved back to the help stack later. Next we need to check if we actually need to execute the loop again. This is very simple. Since N represents the number of times that we need to execute the loop, and N is already in an ideal position to test it, the stack is now perfectly set up to check if the loop needs to be executed again. The = operator will do this for us.
After having done all this, our code will look as follows.
;`01#/ '1-=\
\ /
The # operator is there so that we can enter the loop, which is created by putting the slashes in the way that we see here. If the = operator finds that N is equal to 0, then it will break out of the loop and continue reading right after the \ on the first line, at (13, 0). Otherwise, the loop needs to run, and we will have to move on to step 3.
Step 3 involves finding the next S and L values. When step 3 begins, the stacks are in the following format: S,L,N ||. In order to operate on S and L, begin by moving N to the other stack. Then, S and L need to be added, however since L will become the next S, the value of that first needs to be copied and stored somewhere else. This can be done by duplicating L and pushing it onto the help stack. The code for Step 3 will then look like this:
`"`
With the stacks changing:
S,L,N || => S,L || N => S,L,L || N => S,L || L,N
The stacks have now been prepared to compute the next number. The next number in the sequence can then be found by adding S and L. Afterward, the stack needs to be brought back into its original format of S,L || N. Moving L back onto the main stack and then switching the top two values will complete this as well. The code then extends to the following:
`"`+’^
And the stacks will change as follows:
S,L || L,N => S+L || L,N => S+L,L || N => L,S+L || N.
The loop can then restart, effectively remapping all the values to perfectly fit the original setup. To add this code the existing code, the code will need to be reversed because the cursor will be reading backwards on the bottom side of the loop, however after making this change, the code can simply be inserted into the program, to reach:
;`01#/ '1-=\
\^'+`"`/
This completes the code for the loop. After the loop completes, the stacks will then be formatted as follows:
fib(input - 1),fib(input),0 ||
To print out the final answer, simply remove the top value from the main stack, print, and then terminate the program. Adding these three commands gives us the final solution:
;`01#/ '1-=\!:@
\^'+`"`/