Hey, here’s the crazy project that’s been consuming the last year and a half of my life:

How handy that it can be embedded right into my blog. At some point we’ll fix the URL clicking, but for now you can check it out for reals at www.whirled.com.

Nothing like some jovial legal humor from 1949. To its credit, I don’t recall ever seeing a film from that period that so directly tackled women’s rights. My intuition is that this quote captured the general consensus of the time:

Hepburn: Do you believe that women should be treated equally in matters of the law?
Potential Juror: I should say not!

Wow, this film was intense. It’s a rare thing to see a film about the realities of abortion, let alone one set in an oppressive communist society where it has been criminalized in an attempt to raise the birth rate. The portrayal of 1980s Romania was fascinating. It gave the film a gritty matter of factness that strangely amplified both the sense of danger and the feeling of mundanity.

Problem 038:

object Euler38 extends Application {
  def ispan (n :String) = n.toList.sort(_<_).mkString == "123456789";
  def catprod (n :Int, r :Int) = List.range(1, r+1).flatMap(p => (n*p).toString.toList)
  def find (n :Int, r :Int, max :Int) :Int = {
    val cp = catprod(n, r);
    if (cp.length > 9)
      if (r == 2) max
      else find(n, r-1, max);
    else
      if (ispan(cp)) find(n+1, r, Math.max(cp.mkString.toInt, max))
      else find(n+1, r, max);
  }
  println(find(1, 5, 0));
}

I wrote the above general solution which computes the concatenated product with (1, 2, 3, 4, 5) for increasing values of n until the product exceeds 9 digits, then moves down to (1, 2, 3, 4) and so on. Once I had my answer, I read the forums and discovered that a bit of thinking would have led me to the knowledge that the solution had to be a four digit value multiplied by (1, 2). Even less thinking would have made me realize that the solution had to be larger than the example given in the problem statement. Fortunately I did none of that thinking and got to write an interesting algorithm. A more thoughtful me might have written the following:

object Euler38 extends Application {
  def ispan (n :String) = n.toList.sort(_<_).mkString == "123456789";
  println(List.range(9182,9876).reverse.map(n => n+""+(2*n)).filter(ispan).head);
}

Problem 037:

object Euler37 extends EulerApp {
  val primes = genprimes(1000000);
  def isrtrunc (prime :Int) :Boolean =
    (prime == 0) || ((primes(prime) != 0) && isrtrunc(prime/10));
  def isltrunc (prime :String) :Boolean =
    prime.isEmpty || ((primes(prime.toInt) != 0) && isltrunc(prime.substring(1)));
  def istrunc (prime :Int) = isrtrunc(prime) && isltrunc(prime.toString)
  println(primes.drop(10).filter(0.!=).filter(istrunc).foldRight(0)(_+_));
}

I cheated a little and turned the integer into a string in order to easily truncate it from the left, it would perhaps have been more elegant to take the value modulo 10^digits-1 but the code would have been longer and I feel an irrational desire for brevity in these solutions.

Problem 036:

object Euler36 extends Application {
  def ispal (n :String) = n.reverse.sameElements(n)
  def bothpal (n :Int) = ispal(n.toString) && ispal(n.toBinaryString)
  println(List.range(1, 1000000, 2).filter(bothpal).foldRight(0)(_+_));
}

Brief, readable and reasonably efficient, yay for Scala. The only cleverness here is to realize that binary palindromes must be odd.

Problem 035:

object Euler35 extends EulerApp {
  val primes = genprimes(1000000);
  def digits (value :Int) :Int = if (value == 0) 0 else 1 + digits(value/10);
  def rotate (value :Int, turns :Int) :Int = {
    val mod = Math.pow(10, digits(value)-turns).intValue()
    (value % mod) * Math.pow(10, turns).intValue() + (value / mod)
  }
  def circprime (n :Int) :Boolean = {
    List.range(0, digits(n)).foldRight(true)((t, b) => (b && (primes(rotate(n, t)) != 0)))
  }
  println(primes.filter(0.!=).filter(circprime).length);
}

Coming up with rotate() was fun and the rest was pretty straightforward. I first wrote a recursive method that rotated the number one digit at a time, but then I realized I could do it in a single expression. If there existed a built in operator for raising an integer to an integer power, rotate would look much nicer.

Problem 034:

object Euler34 extends Application {
  val facts = Array(1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880);
  def digfact (sum :Int, n :Int) :Int =
    if (n == 0) sum else digfact(facts(n % 10) + sum, n/10);
  def check (sum :Int, n :Int) :Int =
    if (n == 2000000) sum;
    else if (digfact(0, n) == n) check(sum+n, n+1);
    else check(sum, n+1);
  println(check(0, 10));
}

Since we’re only computing factorial for single digit numbers, we pre-compute the values of 0 through 9 factorial and then breeze up through the positive integers accumulating all numbers that meet our criterion. We stop searching at 2000000 because 1999999 is the last number for which the sum of the factorials of the digits is greater than or equal to the number itself.