Will Crichton

Combinatorics problem: you're arranging 10 people (A .. J) in a row. A and B must sit next to each other. How many arrangements? How could writing this problem as a program help scaffold the problem-solving process?

It seems like there are two styles of programming, which I call "subtractive" and "additive" (like 3D printing). permutations('A' .. 'J').filter(λ p: 'AB' in p or 'BA' in p) ^ subtractive means enumerate all possibilities, then remove constraint violations.

But subtractive is hard to reason about analytically -- how to compute len(..)? Then we rewrite additively: permutations(['AB'] + 'C' .. 'J') + permutations(['BA'] + 'C' .. 'J') Now we can easily derive the formula permutations(9) * 2.

Maybe this is actually a compiler problem: how can you rewrite the subtractive program (which naturally falls out of the problem statement) into an additive one (which is easily countable)? i.e. how do you remove all conditional expressions?