Code Golfing – Smallest Multiple

Code Golfing is the art of taking some code and making it as small as you possibly can. Normally, it takes the form of a function and tests are run against it to make sure your code still works, after you’ve tweaked it for size.

I’ve avoided it, up until now, because other than a form of entertainment, it doesn’t have much useful function. In terms of production code – code that you can understand and easily maintain is much more useful than code that’s difficult to read, but smaller. Now that we’re in the age where it’s fairly normal to download 10gb patch files for games, aside from web pages, I can’t remember the last time I overly worried about the size of the source code.

Anyway. I tried some Code Golfing this weekend, and it’s actually quite fun. I learnt a couple of things, too about stuff I’d never try in production – like if you weld a for loop into an infinite one, by using a blank middle condition, then the compiler is intelligent enough to realise that anything which follows (including the usual default return) will never be reached.

Best of all – it got my brain sparking again.

The challenge I attempted was this one:

Given a positive integer n, find the first positive integer divisible by 2, 3, 5, and 7 with at least n digits. Return the result as a string, as n may be as up to 10³.

So, 1,000 digit numbers. The kind of territory I find fun.

I checked to see whether I could use the System.Numerics.Biginteger class. No such luck. At which point, the problem became how to easily cope with 1,000 digit numbers.

I could write my own Biginteger class, but that would take up a lot of characters. Being Code Golf, that would be a total no-no, but I could jury-rig something just for plain addition.

So, I quickly hacked together a couple of byte arrays to represent individual digits, started at 210 and just added 210 continually, testing to see if I ever reached n digits of use, and taking the result afterwards.

At which point, I ran nose-first into another Code Golf constraint: All solutions have to run in under a second.

While my solution was working and small, it certainly wasn’t fast – and it needed to be all three.

I realised that I needed a completely different approach – and what I ended up with, was this:

string smallestMultiple(int n) {
 // This solution uses several "Tricks".
 // The first "Trick" is realising that the number to be returned will always be
 // within 210 of 10 ^ n.
 
 // The second "Trick" relies on a combination of two divisibility rules, namely:
 
 // Anything divisible by 2 ends in 0,2,4,6, or 8
 // Anything divisible by 5 ends in 0 or 5
 
 // Combine those two rules, and it should be obvious that our number
 // must end with a 0. 
 
 // The third "Trick" is that for a number to be divisible by 3, the sum of all it's
 // digits must also be divisible by 3.
 // In combination with our first trick, for any numbers which have four digits or more,
 // we know that we will always have:
 // A 1, a number of zeros, and a number between 0 and 209.
 // Given that we know it must end in a zero, that leaves valid values for our number as:
 // 20, 50, 80, 110, 140, 170, or 200
 
 // The fourth "Trick" is that for a number to be divisible by 7, the sum of 
 // alternating sets of 3 digits from the right added and subtracted together
 // is also divisible by 7. So, again - for any number that has four digits or more,
 // the number we are looking for is going to look like this:
 //
 // Either: 1 + a number of zeros, and 20, 50, 80, 110, 140, 170, or 200
 // or: 10 + a number of zeros, and 20, 50, 80, 110, 140, 170, or 200
 // or: 100 + a number of zeros, and 20, 50, 80, 110, 140, 170, or 200
 //
 // Depending on how big n is. If n = 4, then it's 1, if n = 5 then it's 10,
 // n=6 = 100, n = 7 = 1 again (and 3 0's) etc.
 // 
 // We need to work out whether to add or subtract the 1, 10 or 100 to our
 // 20, 50, 80, 110, 140, 170, or 200 before testing by divisibility by 7.
 // If n=4-6, we subtract, if it's 7-9 we add, 10-12 we subtract, 13-15 we add, etc.
 // Note that because any other set of 3 digits are zero's, we can ignore them 
 
 // And now - to the code.
 
 // First off - for any number less than 1000 (n = 4), the answer is always
 // 210 (2 * 3 * 5 * 7)
 if (n < 4) return "210";
 
 // Work out if we're going to adjust the number by 100, 10 or 1. 
 int a = n % 3 == 0 ? 100 : n % 3 == 1 ? 1 : 10;
 
 // Work out if we should add or subtract that adjustment (1 is add, -1 is subtract)
 int b = n % 6 > 3 || n % 6 == 0 ? -1 : 1; 
 
 // Loop guesses starting at 20, adding 30 each loop
 for (int x=20;; x+=30)
 {
 
 // if our guess modified by the adjustment is divisible by 7 - then we have our answer.
    if ((x + a * b) % 7 == 0) return "1".PadRight(n - 3, '0')
       + x.ToString().PadLeft(3, '0');
 }

 // Note that there's no return here. Because our for statement is missing it's
 // conditional check to exit, the compiler's intelligent enough to know that it's
 // never going to get this far. As I *know* that I'm going to get an early hit, I can
 // get away with an infinite loop for code golfing purposes, but I'd never advise using
 // one in the real world, other than for tight game loops, etc.
}

In total – 194 characters (Comments aren’t counted). Fairly decent, I thought.

The shortest entry, however, was 104 characters. Looking at their code (you’re allowed to, afterwards), it seems that there’s a repeating pattern of results – curiously not including  140. (I’m sure there’s a good Maths reason for that. Just not sure what it is).

Anyway – I finished 6th overall. Not bad, but not 1st, obviously. Still – for my first code golf outing – pretty pleased with that.