This was a fun challenge to work on, on and off, in between Christmas celebrations. Thank you for posting! Golfing this was interesting because the specification is full of exceptions and special cases, which required lots of if conditions. Also, while I didn’t need to convert to and from decimal this time, I did need a “max” function of sorts to determine the largest number of digits in each number and the largest value of the digits in each place.
The first version of this was 4844 bytes, just to give you an idea of how much I golfed this.
The program expects the input as a comma-separated list of integers. No spaces or newlines. Using those will produce undefined behavior.
'""""""'""'""'""'""'""'"""'""""""'"""'""'""'""'""'""'""'""'""'""'""'""""""'""'""'""'""'""'""'"""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""""""'""""""""'"""'""'""'""'""'""'""""""'""'"""'""'""'""'""'""'""'""'""'"""'"""""'""""""'"""'""""""""'"""""""'"""'""""""'""""""""'"""'""'""'"""""""'""""""""'"""'"""""'""'""""""'""'""'""'"""'""""""""""'""""'""""""'""'""'"""'"""""""'""'""'""'""'""'""'"""'"""""""""'""""""'""""""'""'"""'""'"""""""'""'"""'""'"""""'""""""'""'""'"""'""""""""'"""""""'""'""'"""'""""""'""'""'""'"""'""""""""'"""""""'""'""'""'"""'""""""'""""""'"""'""""""""'"""""""'"""'"""'""""""'"""'""""""""'"""'""""""'""'""'"""'"""""'"""""""'"""""""'"""'""""""'"""'""""""""'"""""""'"""'"""""'""""""'"""'""'"""""""'"""'""""'""""""'""'""'""'"""'""""""""'"""'"""""'""""""""'""""""'"""""""'"""'""'"""""""'"""""""'"""'"""""""""'"""""""""'"""""""'"""""""'"""'"""'"""""""""'""'"""""""'"""'"""'""""""""'"""'""""'""""'""""""'""'"""'""'""'""'""'""'""'""'""'"""'"""""'"""""""'""""""'""'"""'""'"""""""'""'"""'""""'""""'"""""'""""""'""'""'""'""'""'""'""'"""'""""""'""'""'""'""'"""'"""""""'""""""'""'"""'""'"""""""'""'"""'"""'"""""'"""""""'""""""'""'"""'""""""""'"""""""'""'"""'"""""""""'""""""""'"""""""'""""""'""'""'""'""'""'""'""'"""'""""""""'"""""""'""'""'""'""'""'""'""'"""'"""""""""'""""""""'""""""""'"""""""'"""""""'"""'"""""""""'"""""""'""'""'""'"""'""""""'""'""'""'""'"""'"'"""""""""'""'"""""""'"""""""'""'"""'"""""""""'""'""'"""""""'"""""""'""'"""'""""'""""""'"""""""'""'"""'"""""""""'"""""""""'""'"""""""'"""'"""'"""""""""'""'""'"""""""'"""""""'"""'"""'"""""""""'""'""'""'"""""""'"""""""'""'"""'"""'""""""""'"""'""'"""""""'"""""""'""'"""'""""""""'""""""""'"""'"""""""'""""""""'"""'"""""""""'"""""""'"""""""'"""'"""""""""'""'"""""""'"""'"""""""'""'""'""'""'""'""'"""'""'""'"""""""'""'""'""'""'""'"""'"""""""'""""""""'"""'"""""""'""'""'""'""'""'"""'""""'"""""""""'"""""""""'""'"""""'"""""""'""""""'""'""'"""'""""""""'"""""""'""'""'"""'""""""'"""""""'""'"""'""""""""'"""""""'"""""""'""'"""'"""'"""""""""'"""""""'""'""'""'""'""'"""""""'""'""'"""'"""'"""""""""'""'"""""""'"""'"""'""""""""'"""'""""""'"""""""'""'"""'""""""""'"""""""'"""""""'""'"""'"""'"""""'"""""""'""""""'""'""'"""'""'"""""""'""'""'"""'"""'""""'""""'"""""'""""""'"""""""'""'"""'""""""""'"""""""'"""""""'""'"""'""""""'""""""'""'""'"""'""""""""'"""""""'""'""'"""'"""'"""""'"""""""'""""""'""'""'"""'""'"""""""'""'""'"""'""""""'"""""""'""'"""'""'"""""""'"""""""'""'"""'"""""""""'""'"""""""'"""'""""""'""""""""'""""""""'""""""""'""""""""'"""""""'""'""'"""'"""'"""'"""'"""""""""'"""""'"""""""'""""""'""'"""'""'"""""""'""'"""'"""""""'""'""'""'""'"""'"""'"""""""""'"""""""'""'""'""'"""'"'"""""""'""""""""'"""'"""'"""""""""'""""""""'""""""""'""""""""'"""""""'"""""""'"""'"""""""""'"""""""'""'""'""'"""'"'""'""'""'""'""'""'""'""'""'"""'"""'""""""'"""""""'"""'""""""""'""""""'""'""'""'"""'"""""'"""""""'""""""'""'""'"""'""""""""'"""""""'""'""'"""'""""""'"""""""'"""'""""""""'"""""""'"""""""'"""'"""
Explanation
I’m going to walk you through how the program works by showing you how it processes the specific input 202,100,1.
In the beginning, we construct a few values that we will need later — mostly the ASCII codes of the characters we will output.
As you can see, '8' and '.' are already available. '|', however, is really 124, not 14. We use a while loop to add twice the temporary value in slot #1 onto it to get 124 (which is 14 + 55×2, because the while loop runs for 56−1 = 55 iterations). This saves some bytes because large integer literals like 124 are really long. In the following diagram, I show the location of every variable the program uses.
Next, we want to input all the characters and store them on the tape starting at cell #12 (p is the running pointer for this). At the same time, we want to know how long the longest number is (how many digits). To achieve this, we keep a running total in unary going leftwards starting at cell #−1 (we use q as the running pointer). After the first input number (202), the tape now looks like this:
You will have noticed that the numbers are off by 4. Well, when we first input them, they are their ASCII values, so they’re “off” by 48 and the comma is 44. For each character, we copy the 46 from '.' into r and then subtract it with a while loop (which subtracts 45) and then we add 1. We do that so that the comma (our separator) is 0, so we can use a conditional to recognize it.
Also, you will have noticed that we leave cell #11 at 0. We need that to recognize the boundary of the first number.
The next character will be a comma, so we store a 0 in #15, but of course this time we don’t advance q. Instead, we set q back to 0 and start “overwriting” the 1s we’ve already placed.
After all the remaining characters are processed, we get this:
As you can see, the 1s written by q now indicate (in unary) the length of the longest number.
We now use a while loop to move q to the very left, and then place another pointer there which I will call r2. The purpose of r2 will become clear later.
At this point, let me clarify the terminology that I will use throughout this.
- By number, I mean one of the input numbers that are separated by commas. In our example, they are 202, 100 and 1.
- By digit, I mean a single digit in a specific one of the numbers. The first number has 3 digits.
- By place, I mean the ones place, tens place, hundreds place, etc. So if I say “the digits in the current place”, and the current place is the ones place, those digits are 2, 0, and 1 in that order.
Now back to our regular programming. The entire rest of the program is a big loop that moves q forward until it reaches cell #0. Each of the cells along the way represents a place, with the ones place on the far right, and q will start at the most significant. In our example, that is the hundreds place.
We proceed by incrementing the cell q points at (that is, *q).
We are now at “stage 2” for the hundreds place. In this stage, we will find out what the largest digit is among all the digits in the hundreds place. We use the same unary counting trick for this, except this time the pointer is called r and the pointer r2 marks its starting position to which we need to reset it every time we move on to the next number.
Let’s start with the first number. We begin by setting p to 11 (the hard-coded starting position of all the numbers). We then use a while loop to find the end of the number and set p2 there to mark the position. At the same time, we also set q2 to 0:
Don’t be distracted by the fact that q2 is pointing into the vars. We don’t have a padding of a blank cell there because we can detect cell #0 simply because it’s number zero.
Next, we go through the current number by decrementing p and q2 together until *p is zero. At each place, the value of *q2 tells us what we need to do. 1 means “do nothing”, so we keep going. Eventually we encounter the 2 in cell #−3. Every time *q2 is not equal to 1, q2 is always equal to q.
As I already stated, stage 2 is “determine the largest digit in this place”. So we set r to r2, use a while loop to decrement *p and move r leftwards and fill the tape with 1s, and then use another while loop to move r back to the right and increment *p again to restore the value. Remember that every while loop runs for one fewer iteration than the value we use it on; because of this, the number of 1s written will be 3 more (rather than 4 more) than the digit value, and the final value stored back in *p will be 2 more. Thus, this has effectively decremented *p by 2.
After that, we set p to the value of p2 and then we do all that again. For the second time, set q2 to 0, find the end of the number by moving p to the right, and then go through the digits of this number by decrementing p and q2 together. Once again we will encounter the 2 in cell #−3 and write that many 1s left of *r.
In the case of the third number, we end up doing nothing because it doesn’t have a hundreds place (so q2 never reaches q), but that’s OK because that doesn’t affect the calculation of the maximum digit value.
We also set the cell *(r − 4), which I’ve marked with an unlabeled arrow here, to 1 (even though it’s already at 1). I’m not going to tell you why yet, but maybe you’ve already guessed?
The next increment of *q takes us to stage 3, which is “subtract the maximum digit from all digits in the current place”. As before, we reset p to 11 and q2 to 0 and then go through all the numbers just like we did in the previous stage; except this time, *q = 3 instead of 2. Every time q2 meets q and p is in a hundreds place, we use a while loop to decrement *p as many times as there are 1s in the block left of *r2 (5 in our example) by using r as a running pointer. We actually decrement it once more than that so that the largest digit ends up at −2, for a reason that will become clear later:
After we’ve processed all the numbers, we are now at the end of stage 3. Here we perform two singular things.
- First, we also subtract the size of the r-block (plus 1) from *q, but using the r2 pointer, which leaves it on the left. *q becomes negative this way. In our case, the r-block has five 1s, so *q becomes −3.
- Second, we set a variable out to a non-zero value to indicate that we are now entering the output stage. (Technically, the fact that *q is negative already indicates the output stage, but this is too difficult to check for, hence the extra variable.)
You now understand that we keep going through the numbers, find the current place (indicated by the non-1 value of *q) within each number, and do something depending on the value of *q. We see that *q is first incremented to 2 (= calculate maximum digit value), then 3 (subtract maximum digit value from every digit in this place) and then we subtract from it to make it negative. From there, it will continue to go up until it reaches 1, thus restoring the value that means “do nothing”. At that point, we move on to the next place.
Now, when *q is negative, we’re outputting. *q is at exactly the right value so that we will output the right number of rows of characters before it reaches 1; if the largest digit is 2, we need to output 3 rows. Let’s see what happens at each value of *q:
- *q = −2:
- For the first number, *p is −2, which indicates that we need to output a
'.' (dot) or a ':' (colon). We decide which by looking at q: if it’s −1, we’re in the ones place, so output a ':' (which we calculate as '8'+2), otherwise a '.'.
- For the second number, *p is −3. Anything that is not −2 means we output a
'|' (pipe) and then increment the value. This way it will reach −2 in the right place and then we output '.'s/':'s for the rest of that digit.
- In each case, we also set a variable pd to 0 before we process the number, and set pd (= “printed”) to a non-zero value to indicate that we have printed a character.
- For the third number, no processing occurs because the third number does not have a hundreds place. In this case, pd will still be 0 after processing the number, indicating that we still need to output a
'|' (but only if out is non-zero, because otherwise we’re still in stage 2 or 3).
- After processing all numbers, if out is non-zero, output a newline. Note that we need the out variable so that we don’t output the newline in stage 2 or 3.
- *q = −1: Same as before, except that *p is −2 for both the first two numbers, so both output a
'.' (and the third outputs a '|' as before).
- *q = 0: When *q is 0, this means “do nothing if we’re in the ones place, otherwise output a row of
'|'s regardless of *p”. This way we get the padding between the digits.
Now we increment q to move on to the next place, the tens place, and increment *q there. At the beginning of Stage 2, the tape looks like this:
Then we perform Stage 2 just as before. Remember this effectively subtracts 2 from every digit in this place and also leaves a unary number left of *r2 indicating the maximum digit. We leave the previous unary number alone and just keep extending the tape to the left; it would only cost unnecessary extra code to “clean up”. When we’re done and we increment *q, at the start of Stage 3 the tape is now:
Actually, this is a lie. Remember earlier where I said we set *(r − 4) to 1 and I didn’t tell you why? Now I’ll tell you why. It’s for cases like this one, where the largest digit is in fact 0, meaning all the digits in this place are 0. Setting *(r − 4), indicated by the unlabeled arrow above, to 1 extends the unary number by 1, but only in this special case. This way we pretend as if the largest digit was 1, which means we will output one extra row.
After Stage 3 (subtract maximum digit from all digits in the current place), including the extra step that makes *q negative, the tape looks like this. Last time the biggest digit was represented by −2 in the *p block, but this time they’re all −3 because they’re all actually zeroes but we’re pretending as if the maximum digit was a 1.
Now let’s see what happens as *q progresses towards 1:
- When *q = −1, the *p values are all −3, which means we output
'|'s and increment them.
- When *q = 0, we output
'|' because that’s what we always do when *q = 0, regardless of *p.
Thus, we get two rows of pipes.
Finally, we move *q to the one’s place. This one gets interesting because we need to output ':'s if the actual digit is anything but 1, but an '8' if it’s 1. Let’s see how the program proceeds. First, we increment *q to initiate Stage 2:
After Stage 2 (“calculate maximum digit value”), we’re left with this:
After Stage 3 (“subtract maximum digit value from all digits in current place”) the tape looks like this:
Now let’s go through each iteration of *q in turn:
- *q = −2:
- First number: already at −2, so output a
':' (rather than a '.' because q = −1).
- Second number: at −4, so output a
'|' and increment.
- Third number: at −3, so output a
'|'. However, this time, instead of incrementing, a special case triggers. Only if we’re outputting the last place (q = −1), and we’re in the second-last row for that (*q = −2), and the digit is actually a 1 (*p = −3), then instead of incrementing it to −2, we set it to −1. In other words, we use −1 as a special value to indicate that in the next iteration, we will need to output '8' instead of ':'.
- *q = −1:
- First number: already at −2, so output a
':'.
- Second number: at −3, so output a
'|'. The special condition does not trigger because *q is no longer −2. Therefore, increment.
- Third number: at −1, so output
'8'.
- *q = 0: Ordinarily, we would output the padding row of
'|'s here, but in the special case where we’re in the ones place (q = −1), we skip that.
After this, q is incremented to 0 and the big while loop ends.
Now you know how an input like 202,100,1 works. However, there’s one more special case that we still haven’t covered. You may remember that while we were processing the last place, when *p was −3 we set it to −1 for the 1 (instead of incrementing it to −2) so that the next iteration would output an '8' instead. This only works because we have an iteration in which *p is −3 and we make a decision as to whether to increment it or set it to −1. We do not have such an iteration if all of the digits in the ones place are 0 or 1. In such a case all the *p values for the 1s would start out at −2; there is no opportunity to decide to set it to −1 rather than to increment it from −3. Because of this, there is another special-casing condition inside Stage 3 (“subtract maximum digit from every digit in the current place”). I claimed that after subtracting the maximum digit value from every digit (at which point the maximum digit is at −1), we just decrement it once more, but actually there’s a condition on that which goes as follows:
If the digit we’re looking at is equal to the maximum digit in this place (*p = −1), and this place is the ones place (q = −1), and the maximum digit is 1 (*(r + 5) = 0, i.e. the unary block at the very left is only 5 cells long), only then we leave *p at −1 to indicate that the only iteration of the output must output an '8'. In all other cases we decrement it once more.
Done. Happy new year!
Edit 1 (3183 → 3001): Some Happy New Year golfing! I managed to get rid of the variables p2 and r2 entirely! p now races back and forth to keep finding the beginning and end of numbers, but it seems to be shorter in code. I tried to get rid of q2 as well, but I couldn’t make the code shorter that way.
I also found a few more places where I could apply typical Unreadable golfing tricks like re-using the last value of a while loop. To give you an example, instead of
while *(++p) { 1 } // just increment p until *p is 0; the 1 is a noop
if (pd) { x } else { y } // where pd is a variable
I can save the '"""" (do the first, then the second) and the '""" (constant 1) by writing it in a way that is kind of like
if (while *(++p) { pd }) { x } else { y }
Of course, this only works if I know that the while loop will run for at least one iteration, but if it does, its return value is pd so I can use that as the condition for the if.
A related challenge on Maya numbers – Fatalize – 2015-12-28T14:57:51.987