Monty Hall

The Monty Hall problem is a great example of how counter-intuitive probability can sometimes be. It goes something like this: say you’re on a gameshow, with the chance to win a car. You’re shown three doors, and the car is behind one, goats behind the other two. You pick a door, say the leftmost, but then the host of the gameshow stops you before it’s opened. He opens one of the two doors you didn’t pick, revealing a goat. He then asks you if you’d like to change your decision. So? Do you?

Read More

Making FlatMap lazy

flatMap() is pretty cool. When I first learned what map() did, it got shoved into every line of code I had, regardless of how applicable it was. (That’s usually a good sign.) Then, along came flatMap(). It’s deceptively simple: its name pretty much explains exactly what it does. Useful, not game-changing, although it does let you do some pretty cool things:

Read More

Swift Protocols: A Strategy

A Misguided, Over-Simplified Strategy

It Makes Sense to Me, so…

So I’ve been drinking the Protocol-Oriented-Programming gatorade for a while now. I’ve taken it to the extreme a little: you won’t find a class in pretty much any of my code these days. So, before I pull it back a little, I thought I’d put down my strategy so far for how to handle these protocol things.

Read More

So Apparently I Can’t Curry

I was reading “Learn You a Haskell for Great Good”, and this jumped out at me:

People who are not well acquainted with how currying and partial application works often use lambdas where they don’t need to. For instance, the expressions map (+3) [1,6,3,2] and map (\x -> x + 3) [1,6,3,2] are equivalent since both (+3) and (\x -> x + 3) are functions that take a number and add 3 to it. Needless to say, making a lambda in this case is stupid since using partial application is much more readable.

(Check it out here)

I’d heard of currying before (and had it explained to me), but never really got it. In this particular passage, it clicked. I rushed through my previous combinations and permutations stuff, and curried the living daylights out of it.

Read More

Functions for Hire: Combinations With Repetition

That last post hurt my head a little. I figured there must be a better way to do what I did: so I googled. Before I found a better way, I found that I wasn’t done. I had written functions for permutations, permutations with repetition, and combinations, but still one thing was left: combinations with repetition. Ugh. Dreading having to muddle through the same things again, I madly went at my already written code, changing it and jostling it. One of my fiddles worked. All I had to do was swap the order of removing from the pivotList in the addCombo function, and hey presto, I had a combinations with repetition function. Here it is:

func combosOfLengthWithRep
  <T>(objects: [T], length: Int) -> [[T]] {
  return [Int](1...length)
    .reduce([(objects, [T]())]) {
      (accum, _) in
      accum.flatMap() {addComboWithRep($0, $1)}
    }.map() {$0.1}

func addComboWithRep
  <T>(var pivotList: [T], prevCombo: [T])
  -> [([T], [T])] {
  return (0..<pivotList.count)
    .map() {
      _ -> ([T], [T]) in (
        prevCombo + [pivotList.removeLast()]

combosOfLengthWithRep([1, 2, 3], 2)
//[[3, 3], [3, 2], [3, 1], [2, 2], [2, 1], [1, 1]]

Basically, it’s doing the same thing as the last combinations function, except every pivotObject is still left in its pivotList, so it can pair with itself.

Functions for Hire

The higher-order functions in Swift (map(), flatMap(), reduce(), filter()) can allow you to write functional, powerful, and beautiful code. They can also allow you to write very bad code. It can be unreadable (“I’m not golfing, I swear, it’s just more functional“) and slow (using reduce() to build an array is O(n²)). For me in particular, they can encourage bad practices, like long, var-less closures: the kinds that produce the error in the picture above. (Xcode’s limitation on expression complexity is definitely more of a help than a hinderance, though: I see that error as a gentle suggestion that my code is golfy, rubbish, and too clever for its own good)

(to be clear, I’m probably blaming the wrong thing: functional programming doesn’t necessitate long closures, golfy code, or arrays from reduce(). But for me, they often go hand in hand.)

Nonetheless, sometimes it’s fun to abuse and overuse map(). And, as an intellectual exercise, maybe it’ll even help me learn some new things! With that in mind, I decided to think of the expression complexity limit as more of an expression complexity target, get out my programming S&M gear, and abuse some higher functions.

Read More

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)

Read More