Problem 061:

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))
                        yield s) headOption
    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
  def answer = (sets head) map(_.value) sum
}

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).

Problem 060:

object Euler60 extends EulerApp {
  val primes = genprimes(10000) filter(0.!=)
  val ppairs = Set() ++
    (for { ii <- 0 until primes.length-1; jj <- ii until primes.length;
          val pi = primes(ii); val pj = primes(jj);
          if (isprime((pi.toString+pj).toInt) && isprime((pj.toString+pi).toInt))
    } yield (pi, pj))
  def isset (pset :List[Int], prime :Int) =
    pset.foldLeft(true)((b, a) => b && ppairs((a, prime)))
  def find (pset :List[Int], plist :List[Int]) :Option[List[Int]] = {
    if (pset.size == 5) Some(pset)
    else if (plist.isEmpty) None
    else if (!isset(pset, plist.head)) find(pset, plist.tail)
    else find(plist.head :: pset, plist.tail).orElse(find(pset, plist.tail))
  }
  def answer = find(Nil, primes.toList).get.sum
}

This one’s not particularly concise, but it’s fairly readable (or at least I think so since I wrote the code just shy of two years ago and it wasn’t too hard to regrok it in order to write this blog post).

First we generate a “reasonable” number of primes (which is cheating a little, but also really simplifies things). Then we precompute which of those primes pair with one another so that we can check a given pair of primes for pair-ness quickly later. Being able to concisely turn a sequence into a set, and having structurally-comparable tuples for free is so nice.

Now we climb up the list of primes, each time checking whether the current prime can expand our current set of concatenable primes. This check only requires that the candidate prime properly pair with each prime in the set, since we already know that all the primes in the set pair with one another (because they were each checked before they were added). If it does pair, add it to the set and either way we continue with the next prime. If we reach the end of our list of primes and we haven’t found a set of five, we backtrack (making use of the call stack) and execute the orElse and try again without that most recently added pairable prime.

When we first start out, our set is empty, so the first prime trivially pairs with our existing empty set and is added to the set. When that turns out not to yield a set of five concatenable primes, we pop that first prime off and try the second prime, and so on down the line.

Problem 059:

object Euler59 extends EulerApp {
  val cipher = readline("cipher1.txt") split(',') map(_.toInt)
  def decode (cipher :Array[Int], key :Array[Char]) =
    (0 until cipher.length) map(ii => cipher(ii) ^ key(ii%key.length))
  def answer = (for {
    a <- 'a' to 'z'; b <- 'a' to 'z'; c <- 'a' to 'z'
    val decoded = decode(cipher, Array(a, b, c))
    if (decoded.map(_.toChar).mkString.contains(" chapter"))
  } yield decoded.sum).head
}

Nothing fancy here. I do a brute force search, trying each key in turn and looking for a particular English word to indicate that the decoding is correct. I’m cheating a little in that I first had the program print out the decoded text, and once I saw the correct decoding, I selected a word therefrom to use in the final version. I suppose I could read in a dictionary of English words and assume I’d found the key when my decoding contained a few of the words in the dictionary. That sounds like way too much work for an Euler problem.

Problem 058:

object Euler58 extends EulerApp {
  def checkring (r :Int, primes :Int, nums :Int) :Int = {
    if (primes*10/nums < 1) 2*r-1
    else {
      val skip = 2*r
      val base = (skip-1)*(skip-1)
      val rp = List(1, 2, 3).map(base+skip*_).filter(isprime).length
      checkring(r+1, primes+rp, nums+4);
    }
  }
  def answer = checkring(2, 3, 5)
}

This one is pretty easy after observing that you skip twice the “radius” to get from one corner to the next for a given ring of the spiral. So we just tail-recurse on out the rings, checking the corners for primality and counting them up. We precompute the first ring, because if I start with a ring of radius 1, with 0 primes and 1 number in total, our condition of fewer than 10% primes is prematurely satisfied.

Problem 057:

object Euler57 extends EulerApp {
  case class Frac (numer :BigInt, denom :BigInt) {
    def add (n :BigInt) = Frac(n * denom + numer, denom)
    def invert = Frac(denom, numer)
    def numheavy = numer.toString.length > denom.toString.length
  }
  def expand (count :Int) :Frac = if (count == 0) Frac(1, 2)
                                  else expand(count-1).add(2).invert
  def answer = (0 to 1000) filter(i => expand(i).add(1).numheavy) length
}

I took the opportunity to use a case class to model just enough of a rational to get the job done. The only other thinking required was figuring out how to perform the infinite expansion iteratively: start with ½, add two, invert, repeat as desired, then finally add one.

I was lazy in two ways: I used BigInt instead of reducing the numerator and denominator along the way to keep things fitting in 32 (or 64) bits, and I could have probably structured the code differently to make use of incremental results, but this already runs in about two seconds, so I didn’t feel the need. Oh, and I also probably shouldn’t be abusing the stack like I am in expand, so call it three ways lazy.

Problem 056:

object Euler56 extends EulerApp {
  def answer = (for { a <- 90 to 100; b <- 90 to 100 }
                yield BigInt(a).pow(b).toString.map(_-'0').sum) max
}

I’m in Switzerland at the moment, so my mind naturally turns to Project Euler.

I have made some changes to my problem harness. Previously, I relied on Scala’s Application class’s jiggery pokery to stuff your whole program into a static initializer and execute it. This interacts poorly with a HotSpot optimization optimization which dictates that it not optimize code run in a static initializer. This led me to stick some of my solutions in a main method, which grated against my delicate sensibilities. Now EulerApp defines an abstract answer method to be implemented by the solution class. It then runs said method in a standard main method, yielding optimized (just-in-time) compilation and a reasonable aesthetic to boot.

This particular problem is pretty simple. We rely on BigInt to do the heavy lifting, and simply do a brute force scan of the likely candidates (values between 90⁹⁰ and 100¹⁰⁰).

I have graduated to the ranks of property ownership in sunny Seattle. I present photographic proof for your visual enjoyment.

A distillation of various traditional animation knowledge that Lasseter apparently picked up while working with the grand old men of Disney. Well outside my research area but still fascinating.

Source: PDF ACM