samskivert » Euler 032

February 23, 2008

Euler 032

Problem 032:

object Euler32 extends Application {
  def digits (n :Int) = n.toString.toList.map(c => c - '0');
  def ispan (a :Int, b :Int, n :Int) :Boolean =
    (digits(a) ::: digits(n) ::: digits(b)).sort(_<_).equals(List.range(1,10));
  def haspanfact (n :Int) :Boolean =
    List.range(2, 100).find((a) => (n % a == 0 && ispan(a, n/a, n))) != None;
  println(List.range(1000, 10000).filter(haspanfact).foldRight(0)(_+_));
}

We want a factorization of a four digit number (which will be either two digits times three or one digit times four), so we enumerate all 4 digit numbers from 1000 to 9999, filter them by checking all possible one and two digit divisors first for divisibility and second for pandigitality, then sum the matches. Being able to decompose numbers into lists of digits, jam those lists together, sort them and compare them to a list with 1 through 9 in consecutive order in three lines of code sure is handy.

Posted to euler by mdb at 8:03 pm | Comments (0)       

Leave a Reply

Yandex Mail.ru Google LiveJournal myOpenId Flickr claimId Blogger Wordpress OpenID Yahoo Technorati Vidoop Verisign AOL

©2001 - 2010 Michael Bayne <mdb@samskivert.com>