Actual Actual Reality: Nobody really cares about his secrets. (Also, I would be hard pressed to find that wrench for $5.)

Brute Force? What Brute Force?

Despite problem 4 being surprisingly tricky, problem 5 was still the large, nasty-looking giant of the set.

Write a program that outputs all possibilities to put + or – or nothing between the numbers 1, 2, …, 9 (in this order) such that the result is always 100. For example: 1 + 2 + 34 – 5 + 67 – 8 + 9 = 100.

Yeah. In the comments, Ps, NPs, and O(n³)s were being thrown around. People seemed to be expecting some intelligent, clever way to solve the problem: turns out, nope. Trying out Every Single Combination was pretty much the best strategy (although trees were suggested by some)

First step, then: let’s get some generator of every permutation of an arbitrary array. Every permutation? And that’s the first step? Algorithmic efficiency is going to be a distant memory by step four. Ah, well.

Permutations with repetition

Diagram for permutations with repetition: On the left are the objects (fromObjects), on the right are the permutations generated (toReturn)

I had an idea of how I wanted to generate the permutations. First of all, I wanted a function that would return an array of arrays, the inner arrays being the permutations. I wanted it to walk down an array of objects, and append to the permutation array that object paired with every other object, and itself. (technically, I’m not talking about permutations here. I’m talking about permutations with repetition, or n-tuples)

So, a function that takes an array of objects, returns an array of arrays that are pairs of those objects. Let’s see what that looks like:

func returnPairs<T>(fromObjects: [T]) -> [[T]] {

  var toReturn = [[T]]()

  for firstOfPair in fromObjects {
    for secondOfPair in fromObjects {
      toReturn.append( [firstOfPair, secondOfPair] )
    }
  }

  return toReturn

}

let ans = returnPairs([1, 2, 3])
//[[1, 1], [1, 2], [2, 1], [2, 2]]

Perfect. But how do we get it to output arrays longer than 2 objects? Well, think about it this way: previously, the function was going through every object, and returning a permutation for that object paired with every other object. What if the function was given an array of permutations, and it would go through every permutation, and return a permutation for that permutation paired with every object.

func returnPairs<T>(pastPerms: [[T]], fromObjects: [T]) -> [[T]] {

  var toReturn = [[T]]()

  for firstOfPair in fromObjects {
    for pastPerm in pastPerms {
      toReturn += [pastPerm + [firstOfPair]]
    }
  }

  return toReturn

}

let pastPerm = [[1, 1], [1, 2], [2, 1], [2, 2]]

let ans = returnPairs(pastPerm, [1, 2])
//[[1, 1, 1], [1, 2, 1], [2, 1, 1], [2, 2, 1], [1, 1, 2], [1, 2, 2], [2, 1, 2], [2, 2, 2]]

So, this new function takes a parameter pastPerms, and layers on all of the objects onto it. Cool.

Still, we can definitely do better. I mean, look at it. var? Two for loops? A variable named toReturn? Do you even lisp? (you were warned about the puns) Let’s make our function a little more functional, then. Time for map() and flatMap():

func addPerm<T>(objects: [T], pastPerms: [[T]]) -> [[T]] {
  return pastPerms.flatMap() {
    perm in objects.map() {
      object in perm + [object]
    }
  }
}

Beautiful. Not a var in sight. I don’t like giving it a pastPerm every time, though. Let’s get a handler function to do that for us. I want something that takes a length, and an array of objects, and returns an array of the permutations of my given length. Right. I’ll have the function apply addPerm to something, repeated a number of times specified by the length:

func permsOfLength<T>(objects: [T], length: Int) -> [[T]] {

  var initial = // ???

  for _ in 1..<length {
    addPerm(objects, initial)
  }

  return initial

}

The initial should be an array of permutations, but I don’t have any until I run addPerm. I can’t just give it the objects, that doesn’t work. I could give it each object, packed into its own array, like an array of permutations, each of length one. map() can do that for us:

 var initial = objects.map() {[$0]} 

Yet again, though, we’re making a var, looping over some other list, and returning the var. There has to be a better way. Let’s try reduce(). reduce() goes through a sequence, carrying an accumulating value with it as it goes, and applying some combining closure to the accumulating value and successive elements in the sequence. Here’s an example, using it to sum a list of numbers:

let numList = [1, 2, 3, 4, 5]

let answer = numList.reduce(0) {
  (accum, element) in
  return accumulating + element
}
// 15

The reduce function itself takes two arguments: an initial value, and a closure. The initial value is the first thing your closure gets as the “accum” argument: from then on in, the accum is the last value you returned from your closure.

For our permutations, we could have reduce start with the initial value we already figured out with map(), and every time, it can apply addPerm to the accumulating value. But what will it iterate over? What array? Well, we can just make an array, from the same range we were using in the for loop, and discard each element in the closure. Here’s what it looks like:

func permsOfLength<T>(objects: [T], length: Int) -> [[T]] {
  return [Int](1..<length)
    .reduce(objects.map() {[$0]}) {

      (pastPerms, _) in

      addPerm(objects, pastPerms)

    }
}

So that’s our permutations figured out. But what about the rest? How do we stick each permutation into our list of numbers from 1 to nine? We’ll need some kind of eval() function, that walks along our array (1-9), and applies our function to it. We don’t need to do much with the functions, all we need is +, -, and our |+ from the last problem. Something like this:

func eval (nums: [Int], ops: [(Int, Int) -> Int]) -> Int {

  var accum = nums.first!

  for i in 0..<ops.count {

    accum = ops[i](nums[i+1]) //This doesn't actually work.

    /*This version, fiddling with closures, does work:
      accum = {$0nums[i+1]}(ops[i]) */

  }

  return accum

}

(Bear in mind there’s one fewer op than there are nums) You should be practically able to smell the reduce(), here. Our holder variable is even called accum! But there’s an issue. We’re iterating through two lists, not one. Happily, among Swift’s hipster structs lies Zip2:

A sequence of pairs built out of two underlying sequences, where the elements of the ith pair are the ith elements of each underlying sequence.

let letrs = ["a", "b", "c"]

let nums = [1, 2, 3]

let ans = zip(letrs, nums) //("a", 1), ("b", 2), ("c", 3)

And putting it into reduce():

func eval (nums: [Int], ops: [(Int, Int) -> Int]) -> Int {

  return reduce(zip(dropFirst(nums), ops), nums[0]) {

    (accum, numOpTuple) in

    return numOpTuple.1(accum, numOpTuple.0)
  }

}

Bear in mind, here, that in the two parameters reduce() normally gives to your closure, the second parameter itself is a tuple of two values. It can get confusing with anonymous parameters ($1.0, $1.1, etc.)

Our eval() function is pretty primitive so far, though. It doesn’t understand precedence. Here’s an example:

4 + 5 |+ 6
9     |+ 6
96    // Wrong

The eval function thinks that all of our operators, +, -, and |+, are equal. But they’re not. In reality, there’s a strict class structure: high-class, high precedence functions (|+), and plebeians (+, -). We really want to perform high-precedence operations first, and then the rest of them:

4 + 5 |+ 6
4 + 56
60    // Right

eval() at the moment is far too egalitarian, just going from left to right, performing the operations as they come. There are a few ways you could add a little elitism, but, since we only need 2 levels of precedence, we could just iterate through ops and nums twice, first with |+, and second with + and -. The loops would look like this:

for (op, num) in zip(ops, mums) {...

Of course, for the first loop, we’d have to remove from our list of numbers and ops as we went, so we don’t repeat operations. So let’s iterate over the indices, then, with a removeAtIndex():

for i in (0..<ops.count) {
  ops.removeAtIndex(i)

Obvious problem, though. Every time we remove an object, we invalidate all indices above the index of that object. The idiomatic way to remove and iterate in Swift is to make your array lazy, and traverse over it backwards:

for i in lazy(0..<ops.count)
  .reverse() {...

But we’re only interested at this point in our high precedence functions. So let’s filter those indices down to only those that correspond to the |+ function in our ops array:

for i in lazy(0..<ops.count)
  .reverse()
  .filter({ ops[$0](1, 1) == 11 }) {...

That’s pretty ugly. Finding equality of functions via their output. (I’d love to see a better way, if anyone knows one). Still, though. Does the job.

The rest is just putting it all together:

func eval (var nums: [Int], var ops: [(Int, Int) -> Int]) -> Int {

  for i in lazy(0...(ops.count - 1))
    .reverse()
    .filter({ ops[$0](1, 1) == 11 }) {

    nums[i] = ops.removeAtIndex(i)(nums[i], nums.removeAtIndex(i + 1))
  }

  return reduce(zip(dropFirst(nums), ops), nums[0]) { $1.1($0, $1.0) }

}

And then, iterating your permutations of operations, and telling you when one gives 100:

for perm in permsOfLength(opList, 8) {
  if eval([1, 2, 3, 4, 5, 6, 7, 8, 9], perm) == 100 {
    print( stringOps(perm) )
  }
}

Slow? You betcha. Efficient? Ha, no. Answers? Oh yeah:

1 + 2 + 3 – 4 + 5 + 6 + 78 + 9
1 + 2 + 34 – 5 + 67 – 8 + 9
1 + 23 – 4 + 5 + 6 + 78 – 9
1 + 23 – 4 + 56 + 7 + 8 + 9
12 + 3 + 4 + 5 – 6 – 7 + 89
12 + 3 – 4 + 5 + 67 + 8 + 9
12 – 3 – 4 + 5 – 6 + 7 + 89
123 + 4 – 5 + 67 – 89
123 + 45 – 67 + 8 – 9
123 – 4 – 5 – 6 – 7 + 8 – 9
123 – 45 – 67 + 89

But is there a better way? I mentioned trees earlier. There were some ideas floating around on reddit, about reducing the number of calculations you would have to do, using a memoization strategy. It would work like this: in the answers above, say, 4 + 5 + 6 shows up twice. Instead of computing 4 + 5 + 6 every time, 4 + 5 + 6 would be an element that you could combine with all of the other possible elements. If you proceeded from the leftmost side (working out 1 + 2, 1 – 2, and 12) and then took that as your root, and only computing everything afterwords as variations on that root, you could potentially save on a lot of computation. However, because of the difficulty with precedence (you can’t really store your value of 1 + 2, because if the value following it is |+ 3, you’d be given 33, rather than 24), the difficulty with not fully understanding the idea, and the difficulty with not having much willpower left, I decided against trying it.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s