Pixels Camp Quizshow Challenge #4

Or the art of black magic

The quest for the Pixels Camp Quizshow continues (read about challenge 1, challenge 2 and challenge 3 on their respective posts).

This time, taking a break from his usual of messing with our heads, the quiz-master was kind enough to explain in detail what he wanted: a program that would compute the sum of two natural numbers.

Would seem easy enough… if only we could use anything other than regular expressions. Oh, and all numbers were using octal notation.

The challenge

Essentially, we had to transform this:

+ 10 5

Into this:

15

This is also a code golf challenge, so the shorted the solution, the better.

The foundations

After only about 30 seconds of Google’ing, I found the same Stack Overflow answer I had seen before: http://stackoverflow.com/a/31599758

As it turns out, incrementing a number with regex’s is a known and solved problem. Let’s use the number 9 as our sample input (I won’t worry convert this to octal notation just yet, because we’re all more used to reasoning about decimal numbers).

The algorithm for incrementing 9 is:

1. Adding a lookup table

So 9 becomes 9~01234567890.

2. Left-padding the input

We now have 09~01234567890.

3. Find out what to increment

The overall rule here is that we only increment the last digit, and as long as they are 9’s, we also increment the ones before them. In regular expressions, this could loosely be translated to /(\d)9*$/.

4. Looking ahead

/(\d)(?=9*~\d*?\1(\d))/$2/g

In more detail:

  1. Match a digit: (\d)
  2. Within the lookahead, match all following 9’s (due to the previously mentioned rule, match the lookup table separator, and an arbitrary number of digits until the original one is matched: (?=9*~\d*?\1)
  3. Match the digit right after that: (\d)
  4. Replace the match (which is only the first digit, as the look-ahead doesn’t count) with $2, which matched the incremented digit from the lookup table
  5. Use the /g modifier, so that this matches more than once (i.e.: 1999 must become 2000, so we need to match all four digits)

5. Taking out the trash

But wait, this just incremented a single number. We didn’t sum anything yet!

Adding numbers, one step at a time

Now, remember that the regexes we use are called several times, in a loop?This means we can go back to our primary school days, and increment one number while decrementing the other. When the decrementing one reaches zero, we’re done!

So, knowing all of this, my first submitted solution was:

/\+ (\d+) (\d+)/z$1~012345670 $2#076543210/
/z(\d+)~\d* 0*#\d+/$1/
/z7/z07/
/(\d)(?=7*~\d*?\1(\d))/$2/g
/(\d)(?=0*#\d*?\1(\d))/$2/g

Let’s go through this one step at a time:

/\+ (\d+) (\d+)/z$1~012345670 $2#076543210/

First, I’m adding lookup tables to both digits (using # in the second one to distinguish them.
Also note that they only go up to 7, since the actual problem uses octal numbers only.
I’m also removing the plus sign in favor of a ‘z’, which saved me the back-slach and the unnecessary white-space.

/z(\d+)~\d* 0*#\d+/$1/

This will match only when the second number is zero, and replace the whole string with the captured first number. Because if the second number is zero, the final result is the first number alone.
Once this matches, all other regexes will no longer match, and the algorithm is over.

/z7/z07/

Adding a leading zero, if the first number is a 7

/(\d)(?=7*~\d*?\1(\d))/$2/g
/(\d)(?=0*#\d*?\1(\d))/$2/g

The first one was already explained in detail. It increments the first number.
The second one is mostly equivalent, but it decrements the second one.

And there we go. This will take long to run. N+1 iterations, to be more accurate, where N is equal to the second number. So + 10 7 will take 7 iterations. But it will get there.

Squeezing to the last byte

Note a few things about the whole solution:

/\+ (\d+) (\d+)/z$1~012345670 $2#076543210/
/z(\d+)~\d* 0*#\d+/$1/
/z7/z07/
/(\d)(?=7*~\d*?\1(\d))/$2/g
/(\d)(?=0*#\d*?\1(\d))/$2/g
  1. \d matches a digit. But the quiz-master was nice to us this time, and we can assume the input is valid. So we can just replace this with a . (dot), which matches any single character; Same thing for the \+;
  2. The ‘z’ placeholder was actually an oversight on my part. We can remove it altogether, and match with the beginning of the string (^) instead;
  3. Without that ‘z’ to worry about, we can now more cleverly handle the second regex, where we replace the whole string with the value of the first number we capture.
    It can now be written as follows: /~.* 0*#.+//
    (i.e.: delete everything starting at the tilde, as long as the second number is zero)
  4. The last two expressions look intriguingly alike. Let’s use the pipe operator to merge them into a single one:
    /(.)(?=(7*~|0*#).*?\1(.))/$3/g

This leaves us with the final 92 character solution:

/. (.+) (.+)/$1~012345670 $2#076543210/
/~.* 0*#.+//
/⁷/07/
/(.)(?=(7*~|0*#).*?\1(.))/$3/g

For anyone who managed to reach the end of this post, and who happened to also finish the challenge, feel free to post (or explain) your solution in the comments.
I came up with this approach right from the start, and that ended up blinding me to other alternatives. As a result, I honestly have no idea how everyone else managed to solve it with such different solutions (judging by their solution size and iteration counts).

See you at the quiz!

Professional over-engineer @Subvisual. Building the future of payments @UTRUST. Pathologically sarcastic. Will one day go to outer space.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store