When Generators Are Brute Force Enablers

An interesting (if mysterious) programming challenge popped up in my business partner’s browser the other day.

You’re given an odd set of weights which represents the series of powers of three. So, the first one is 1lb, the second 3lbs, the third 9lbs, the fourth 27lbs, etc. You also have a scale. If someone puts a weight of arbitrary mass on one side (the left side) of the scale, come up with a combination of weights that balances the scale.

For example – if someone puts an 8lb weight on the left side of the scale, you would need to put the 1lb weight on the left side and the 9lb weight on the right side … because 8 + 1 is 9.

For another example – if someone puts a 22lb weight on the left side, you would need to add the 9lb weight to the left side (total: 31lbs) and then put the 1, 3, and 27lb weights on the right side (1lb + 3lbs + 27lbs = 31lbs).

The challenge is to write a program that solves this for any weight (up to some arbitrary number like 10million, I can’t remember what the limit was). The program should define a main function answer that takes a number n and returns a list containing only (combinations of) the strings "L", "R", and "-". The position of the string in the list indicates which weight it is a placement instruction for. "L" means put the weight on the left, "R" means put the weight on the right and "-" means don’t use the weight. An "L" as the first string in the list, thereofre, means "put the 1lb. weight on the left side of the scale." The fact that it’s at position 0 tells us it’s the 1lb weight (30 = 1), and the fact that it’s an "L" tells us to put that weight on the left-hand side.

So, the answers it should come up with for the examples given are:

8: ['L', '-', 'R']

22: ['R', 'R', 'L', 'R']

The obvious, brute-force way to solve this is to generate all combinations of "L", "R" and "-" for a list of given length and then test each one to see whether it’s the solution. And indeed, the real solution is probably something like that. The problem is that for large numbers you can quickly run out of memory, because the number of lists you have to generate is factorial in the length of the list.

Sounds like a job for generators!

A generator is a type of function that acts like an iterator. The difference is that rather than iterating through a loop and building a collection that it returns at once, a generator yields the next item in the sequence each time it’s called. Python has generators built into the language, so it’s convenient that it was also one of the languages that the mysterious programming challenge showrunners are willing to accept solutions in.

Consider generating the list of weights. The iterative solution to this would take a number – the number of weights we want – and looping that many times, adding the next power of 3 each time around the loop:

def iterate_weights(n):
  return [3**i for i in range(n)]

This one uses a list comprehension for compactness, so it might be a little obscure to some people, but you get the idea. range(n) generates the sequence of numbers 0 up to (but not including) n. Then the comprehension loops over that list, returning 3 to the power of the current number. Since its a list comprehension, it saves the results in sequence in a list, which it then returns.

iterate_weights(8) # [1, 3, 9, 27, 81, 243, 729, 2187]

A generator, by contrast, returns the next item in the sequence each time it’s called. Think of it like a function with state (a functor). Python kindly gives us a way to write generator functions in its native syntax – you simply yield rather than returning. yield means "exit the function with the value given as the return value, but save the internal state and, when the function is called again, resume execution at this point.

def generate_weights(n):
  for i in range(n):
    yield 3**i

If we run it now, we get:

iterate_weights(8) # [1, 3, 9, 27, 81, 243, 729, 2187]
generate_weights(8) # <generator object generate_weights at 0x10da65ca8>

Oops. Apparently generators don’t work like regular functions. Indeed, calling one actually returns the generator, which you then access by passing to the built-in next() function. Hey, good ol’ Python, right? Why keep a clean interface?

Alright, so you actually run it like this:

gw = generate_weights(8)
print(next(gw)) # 1
print(next(gw)) # 3
print(next(gw)) # 9
print(next(gw)) # 27

Which, when you think about it, illustrates the power of generators. Because you’ll probably have noticed that if it’s capable of just generating the next value, we can do away with the limit – like so:

def generate_weights():
  i = 0
  while True:
    yield 3**i
    i += 1

This one will run forever, whereas the other one stopped at 3 to the 8th.

Thinking through what it does is helpful.

On the first call to next(gw):

  1. We enter the function.
  2. set i to 0
  3. Enter the loop and yield 3**i. Since i is 0, this yields 1
  4. Stop right there. Wait for the function to be called again.

On all subsequent calls:

  1. increment i
  2. yield 3**i
  3. Stop right there. Wait for the function to be called again.

So, this is just what we need – something that can give us only the next combination of "L", "-" and "R". That way, we never run out of memory, since we just keep testing the "next" one to see if it’s a solution, and if it is, stop because we’re done, and if it’s not, throw it away and generate the "next" one.

The rub, of course, is deciding what the "next" one is.

Here’s what I came up with:

def find_advanceable_index(a):
  retval = []
  for index,i in enumerate(a):
    if i < 2:
      retval.append(index)
  return max(retval)

def completed(a):
  for i in a:
    if i != 2:
      return False
  return True
      
def successor(a):
  if completed(a):
    return [0 for i in range(len(a) + 1)]
  else:
    indx = find_advanceable_index(a)
    a[indx] += 1
    return a[:indx+1] + [0 for i in range(len(a) - indx-1)]

def gen_list():
  bl = ["L", "-", "R"]
  anchor = [0]
  while True:
    yield [bl[i] for i in anchor]
    anchor = successor(anchor)

So, let’s start with gen_list, since this is the main point. The concept should be clear:

  1. define our range of components – the "alphabet," if you like
  2. start with a list of just 0
  3. enter the infinite "generator" loop
  4. yield the anchor list mapped to characters. So, loop over everything in the anchor list, which should be an integer – 0, 1, or 2 – and replace it with the character from the alphabet that corresponds to that number. So – the first item in our sequence is ['L']
  5. Call successor, passing it our current anchor, to get the anchor we’ll use the next time someone calls this function.

The next interesting bit is, of course, the successor function itself, since this tells us "what comes next."

  1. check whether the anchor (called just a here) is "completed" – which just means "is it all 2s?"
  2. if it’s all 2s, we’re maxed out, and so the next item is just a list of all 0s that’s one longer than the previous list. So, [2,2,2]‘s successor is [0.0.0.0]
  3. if it’s not all 2s, the next item is the current item with the rightmost non-2 member incremented, and also every item following the incremented member set to 0. It’s easier to understand this by example, so:
    1. successor([1,0,0]) # [1,0,1]
    2. successor([1,0,1]) # [1,0,2]
    3. successor([1,0,3]) # [1,1,0]
    4. successor([1,0,3]) # [1,1,1]
    5. successor([1,0,3]) # [1,1,2]
    6. successor([1,0,3]) # [1,2,0]

Obviously, find_advanceable_index(a) just takes a list and finds the rightmost non-2 member. The rest of the function implements the rest of it – increment the number at the index and then zero out everything that follows it (if anything).

And that’s how it works! Testing whether one of these is a solution is straightforward:

def is_solution(n,l):
  global weightlist
  lhs = n
  rhs = 0
  if len(weightlist) < len(l):
    weightlist.append(3**len(weightlist))
    #weightlist = next(iw)
  for inx,item in enumerate(l):
    if inx <= len(weightlist):
      weightlist.append(3**len(weightlist))
    if item is "L":
      lhs += weightlist[inx]
    elif item is "R":
      rhs += weightlist[inx]
    else:
      continue
  return lhs == rhs

My implementation’s a bit lazy, really. I’m referencing a global weightlist and passing in the next solution. If the weightlist is shorter than the candidate solution (l), go ahead and add the next member to it. Then, set lhs to n (the starting weight), rhs to 0, iterate over the candidate solution (l), follow the instructions (add the weight to lhs if it’s an "L", rhs if an "R", and otherwise just continue around the loop) and then, when you’re done iterating, test whether the total weight on lhs is the same as on rhs. If they are, you’ve found a solution!

Here’s some sample output followed by the entire program (more on this below):

(1, ['R'])
(2, ['L', 'R'])
(3, ['-', 'R'])
(4, ['R', 'R'])
(5, ['L', 'L', 'R'])
(6, ['-', 'L', 'R'])
(7, ['R', 'L', 'R'])
(8, ['L', '-', 'R'])
(9, ['-', '-', 'R'])
(10, ['R', '-', 'R'])
(11, ['L', 'R', 'R'])
(12, ['-', 'R', 'R'])
(13, ['R', 'R', 'R'])
(14, ['L', 'L', 'L', 'R'])
(15, ['-', 'L', 'L', 'R'])
(16, ['R', 'L', 'L', 'R'])
(17, ['L', '-', 'L', 'R'])
(18, ['-', '-', 'L', 'R'])
(19, ['R', '-', 'L', 'R'])
(20, ['L', 'R', 'L', 'R'])
(21, ['-', 'R', 'L', 'R'])
(22, ['R', 'R', 'L', 'R'])
(23, ['L', 'L', '-', 'R'])
(24, ['-', 'L', '-', 'R'])
(25, ['R', 'L', '-', 'R'])
(26, ['L', '-', '-', 'R'])
(27, ['-', '-', '-', 'R'])
(28, ['R', '-', '-', 'R'])

The full program contains an alternate implementation as well, where you first generate the last possible candidate solution and cound down from that – i.e. it uses a predecessor function. But this way is much less efficient, and returns lists padded with lots of redundancy. Apparently generating from the bottom up is better. It should be obvious how to switch the implementation from within the main answer function, though, if you’re so inclined.

def completed(a):
  for i in a:
    if i != 2:
      return False
  return True

def find_advanceable_index(a):
  retval = []
  for index,i in enumerate(a):
    if i < 2:
      retval.append(index)
  return max(retval)
  
def pcompleted(a):
  for i in a:
    if i != 0:
      return False
  return True
  
def successor(a):
  if completed(a):
    return [0 for i in range(len(a) + 1)]
  else:
    indx = find_advanceable_index(a)
    a[indx] += 1
    return a[:indx+1] + [0 for i in range(len(a) - indx-1)]

def predecessor(a):
  if pcompleted(a):
    return [2 for i in range(len(a) - 1)]
  else:
    indx = max([i for i,item in enumerate(a) if item != 0])
    a[indx] -= 1
    return a[:indx+1] + [2 for i in range(len(a) - indx-1)]

def gen_reverse_list(w):
  anchor = [2 for i in range(w)]
  bl = ["L", "-", "R"]
  while True:
    yield [bl[i] for i in anchor]
    anchor = predecessor(anchor)

def gen_list():
  bl = ["L", "-", "R"]
  anchor = [0]
  while True:
    yield [bl[i] for i in anchor]
    anchor = successor(anchor)

def is_solution(n,l):
  global weightlist
  lhs = n
  rhs = 0
  if len(weightlist) < len(l):
    weightlist.append(3**len(weightlist))
  for inx,item in enumerate(l):
    if inx <= len(weightlist):
      weightlist.append(3**len(weightlist))
    if item is "L":
      lhs += weightlist[inx]
    elif item is "R":
      rhs += weightlist[inx]
    else:
      continue
  return lhs == rhs

def answer(n):
  global weightlist
  weightlist = []
  handle = 0
  base = 0
  while handle < n:
    handle = 3**base
    weightlist.append(handle)
    base += 1
  genl = gen_list()
  #genl = gen_reverse_list(n)
  candidate = next(genl)
  while not is_solution(n,candidate):
    candidate = next(genl)
  return candidate

i = 0
while True:
  i += 1
  print(i,answer(i))

Of course, this is just a brute-force hack. No doubt there is plenty of potential for optimization here. The point of the post is just to show how to use generators in cases where you need each item in a sequence that’s potentially unbounded.

The real solution would recognize that this is actually a number system. Which you can see by looking at the example output above, actually: anything that’s an actual power of 3 is a bunch of "-"s followed by an "R". See the entries for 1, 3, 9 and 27 above for confirmation. From there, everything is just an increment of 1 in this system, where the leftmost column is the least significant digit.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>