Yesterday I used a programming challenge to illustrate a use of generators. The solution to the problem given in that post was far from ideal – just a brute force hack, really. Today, let’s look at a respectable solution to the problem.
Again, the problem:
Imagine you are given a set of weights, each weight in the series increasing by a factor of three. The weights are the power series of 3, in other words:
[1, 3, 9, 27, 81, 243, 729, 2187, ...]
You also have a balance. You can put each weight in the series on one side or the other of the scale. This can be represented as follows:
['R', '-', '-', 'L', 'R', 'L', '-', 'R']
The letter represents which side of the balance the weight is on, if it’s on the scale at all:
"R" means "right" "L" means "left" "-" means "not on the scale"
The position of the letter in the list represents the amount of weight. So, in the example above, the "R" in the 0-position in the list means the 1lb weight is on the right side of the scale, because 30 is 1. The "L" at index 3 means the 27lb weight is on the left side of the balance, because 33 is 27. Etc.
[1, 3, 9, 27, 81, 243, 729, 2187] ['R', '-', '-', 'L', 'R', 'L', '-', 'R']
This makes it easy to see that there are 2269lbs of weight on the right-hand side of the balance:
1 + 81 + 2187 = 2269
and 270lbs of weight on the left-hand side:
27 + 243 = 270
Now, the challenge is to write a program that takes in a number representing an arbitrary amount of weight that will be placed on the left side of the scale as input and outputs a list of Ls, Rs and -s that represents a combination of weights from your collection that will balance the scale with the input weight placed on the left.
The example given would be the answer for input 1999, for example – because it represents 2269lbs on the right and 270lbs on the left and:
2269 - 270 = 1999
Yesterday’s "solution" found the asnwer by brute force: just generate every possible combination of weights for a list of a certain lenght and test them all until you find the solution.
But it’s possible to do this MUCH more efficiently … by recognizing that this is actually a number system – a number system base 3, to be exact, since our weights are powers of 3. The weights represent columns in a base-3 representation, really. Just like powers of 10 do for our everyday number system. A number like
11 tells you you have 1
10 and 0
1s – that is, one 101 and 1 100.
So, in a base 3 number system,
11 would be
4 – 1 31 and 1 30. So,
3 + 1 = 4.
And that’s pretty easy to see if you print out a bunch of results from yesterday’s program. I’ve added the weights for convenience here:
0, ['-'], ) (1, ['R'], ) (2, ['L', 'R'], [1, 3]) (3, ['-', 'R'], [1, 3]) (4, ['R', 'R'], [1, 3, 9]) (5, ['L', 'L', 'R'], [1, 3, 9]) (6, ['-', 'L', 'R'], [1, 3, 9]) (7, ['R', 'L', 'R'], [1, 3, 9]) (8, ['L', '-', 'R'], [1, 3, 9]) (9, ['-', '-', 'R'], [1, 3, 9])
It’s easy to see that there’s a real sense in which these increment by
1 each time:
(2, ['L', 'R']) (3, ['-', 'R']) (4, ['R', 'R'])
Add 1 to an "L" and you get "-"
Add 1 to a "-" and you get "R"
['L', 'R'] + 1 = ['-', 'R']
So, this is a regular number system. With two important quirks:
The order of significance is reversed. The "ones column" is the leftmost column … the mirror image of our everyday number system, where it’s the rightmost
These numbers aren’t direct representations of their decimal equivalents – rather, you get the decimal equivalent by subtracting the "L" total from the "R" total. Which is another way of saying that this number system has both additive and subtractive elements in its representation, whereas our everyday base-10 system is only additive.
An illustration of this aspect comes from adding
1 to the
['R', 'R'] + 1 = ['L', 'L', 'R']
It’s just like "carrying the one" in our traditional arithmetic (though keep in mind (1) from above – the order of significance is reversed).
Both columns are "full" – since they contain "R". So, we max out by adding a new column. Then we have to "zero" all the remaining columns – which in this case means setting them to "L". That’s because of the second quirk.
In our own everyday number system, when you carry, you carry a 1, the lowest positive value in a column.
9‘s successor is
10 – the highest positive value in one column is succeeded by returning that column to no value and adding the lowest possible value. That’s how an additive number system works. But this system is an offset system. So, you carry the highest possible value into the next column, and you counterweight it in the other columns.
successor(['R']) = ['L','R']
In fact, an interesting property of this system is that it always "ends in R." The most significant column is always maxed out. Again, that’s because this is an offset system, not an additive system. The number we’re representing is actually the weight that would need to be added to balance the system out. We always express the counterweight in some power of 3 plus some adjustements. The power of 3 is always to the right, and the adjustments are to its left.
So, in some important sense,
5 in this system:
['L', 'L', 'R']
Is 32 = 9:
['-', '-', 'R']
Plus some adjustments:
4 in "counterweights."
(9, ['-', '-', 'R']) (-4,['L', 'L']) (5, ['L', 'L', 'R'])
Which in turn suggests an efficient solution to the programming challenge.
Let’s recap what we did in clearer terms: we found
5 in the system by finding the nearest power of
3, which is
9, and then counterweighting it down to
5. The question is whether there is a quick way to find the counterweight?
Well, there is.
Take a look at how you represent
4 in this system:
(4, ['R', 'R'])
It should strike you as not at all a coincidence – because it isn’t at all a coincidence – that this is the "flip" of what we had to
merge on to
9 to get
5. The nice thing about an offset system is that subtraction is damn easy. You just take a number, flip all the digits around the
0 value, and drop it right on in. If
['R', 'R'], then
-4 is automatically
['L', 'L'], and since any power of
3 is just an
R in the proper column with
0 values) in every other column, all you have to do is replace the dashes with the
flip of whatever number you’re trying to offest by.
(5, ['L', 'L', 'R']) = (9, ['-', '-', 'R']) - (4,['R', 'R']) (5, ['L', 'L', 'R']) = (9, ['-', '-', 'R']) + (-4,['L', 'L'])
So, the algorithm is more or less (with one wrinkle):
- Find your number
- Find the power of
3that’s strictly higher than the number
- Subtract your number from that
- Represent the difference in this system
- Flip the representation
- Merge it with the representation of the power of
3that’s strictly higher than your number
In this case:
['L', 'L', 'R']
And of course step (4) is what presents the wrinkle.
"Represent the number in this system" is just a recursive call to – what else? – this same algorithm. But you’ll have noticed that if you always go to the next-highest power of
3, you’ll fall into an infinite loop – since the difference in this case would of course be
9 - 4 = 5 which is the same case that led us here…
So, there’s also a branch condition – if the difference is greater than my target number (and
5 > 4), then instead you should find the next lowest power of
3, find the difference, and add. Which means basically taking the difference and merging it with the next-lowest power of
- 5 is greater than 4 – OOPS!
- 4 – 3 = 1
- 1 is
- Therefore 4 is
If you want to be complete, you can also account for the case where you’re supposed to return a power of
3, in which case just generate it and you’re done, but this branch is just a minor optimization.
The code I wrote for this is below, but in the intersted of full disclosure, a funny thing happened on the way to submitting it: it got rejected, with the cryptic message "Failed 4 out of 5 tests." No indication of what these tests were was given. Since I am convinced this code is correct, I’m chalking it up to the shadiness of the source of the challenge. The challenge imposed a limit of 1billion for the numbers they would run the code over. I haven’t run this ALL the way up to 1billion yet (it turns out to take a very long time to run a billion trials of this), but I’ve run it most of the way there and failed to find a case that doesn’t check out. Not to mention, the proof that it’s correct seems to write itself – this is, after all, a straightforward number system with a straightforward successor function. If someone knows what I’m missing, please point it out in the comments.
def gen_weights(n): i = 0 acc =  while 3**i < n: acc.append(3**i) i += 1 acc.append(3**i) return acc def flip_char(c): if c is "R": return "L" elif c is "L": return "R" elif c is "-": return "-" else: print("INVALID") def flip(a): return [flip_char(c) for c in a] def merge(a,b): a = a[:] for i,item in enumerate(b): a[i] = item return a def answer(n): if n is 0: return ["-"] elif n is 1: return ["R"] elif n is 2: return ["L", "R"] elif n is 3: return ["-", "R"] else: ws = gen_weights(n) an = ws[-1] targ = an - n if targ > n: return merge(["-" for i in range(len(ws) - 2)] + ["R"], answer(n - 3**(len(ws) - 2))) elif n == an: return ["-" for i in range(len(ws) - 1)] + ["R"] else: return merge(["-" for i in range(len(ws) - 1)] + ["R"], flip(answer(targ))) def is_solution(n,a): ws = gen_weights(n) lhs = n rhs = 0 for ind,i in enumerate(a): if i is "L": lhs += ws[ind] elif i is "R": rhs += ws[ind] return lhs == rhs limit = 1000000000 while i < limit: if not is_solution(i,answer(i)): print(i,answer(i)) i += 1