# samskivert: Euler 61

## 27 July 2010

``````object Euler61 extends EulerApp {
case class Pn (card :Int, value :Int) {
def valid = (value < 10000) && (value > 999)
def ab = value / 100
def cd = value % 100
}

def tri (n :Int) = Pn(3, n*(n+1)/2)
def square (n :Int) = Pn(4, n*n)
def pent (n :Int) = Pn(5, n*(3*n-1)/2)
def hex (n :Int) = Pn(6, n*(2*n-1))
def hept (n :Int) = Pn(7, n*(5*n-3)/2)
def oct (n :Int) = Pn(8, n*(3*n-2))
def gen (max :Int)(gen :(Int) => Pn) = (1 to max) map(gen) filter(_.valid)
val nums = List(square _, pent _, hex _, hept _, oct _) flatMap(gen(100))

def search (nums :Seq[Pn], set :List[Pn]) :Option[List[Pn]] = {
if (!nums.isEmpty) (for (n <- nums; if (n.ab == set.last.cd);
s <- search(nums filter(_.card != n.card), set :+ n))
else if (set.last.cd == set.head.ab) Some(set)
else None
}
def sets = for (n <- gen(150)(tri); s <- search(nums, n::Nil)) yield s
}``````

I model a polygonal number with a case class to track it's value and cardinality. Since I care about four-digitality and two digit prefixes and suffixes, those fit nicely as methods on the class. The main search proceeds by starting with a given triangle number (since all sets must have one triangular element), and then looks for a number that matches the suffix of said number. If one is found, it is added to the ordered set, all other numbers with the same cardinality are dropped from the candidates list, and a new number is sought that matches the suffix of the value just added.

If we match a number for each cardinality, then we'll finally end up in the `search` procedure with an empty candidates list, in which case we check whether the last number in the ordered set matches the first.

Functional programming comment: when I first wrote this, I was using `Nil` to indicate a non-match, and had a few `find(Nil.!=)` calls sprinkled around to find matching elements. That smelled suspiciously like using `null`, so I decided to be a good functional programmer and use `Option`. However, this left me in situations where I'd have a `List[Option[Pn]]` and I'd need the first non-`None` element. I know that I can take such a list and do `list flatMap(x => x) head` but that seems insufficiently scrutable to people not familiar with the idiom.

This motivated me to switch to for-comprehensions. Instead of writing:

``nums filter(_.ab == set.last.cd) map(n => search(...)) flatMap(s => s) headOption``

I use what you see above:

``(for (n <- nums; if (n.ab == set.last.cd); s <- search(...)) yield s) headOption``

The for-comprehension turns out to be a little shorter, a lot easier to line-wrap (if needed), and I think probably slightly more comprehensible. You still have to deduce that `Option` behaves like a zero-or-one element list when used in a for-comprehension, but that seems more intuitive than figuring out that `List(Some(1), None, Some(2)) flatMap(x => x)` gives you `List(1, 2)`.