Quirky without being annoying. Amazing acting brought to bear in depicting the struggle of life in the teens. Seeing Jason Bateman and Michael Cera together made it hard to keep Arrested Development out of my head but that wasn’t a bad thing.

Thirty three essays by thirty three authors describing code they consider to be beautiful. A few were inane, a few were exceptional and the majority were generally good. I’ve long wanted to start a blog or magazine that consisted solely of engineers describing interesting complex systems they developed or encountered in the real world. Many of these essays fit that criterion and were, as I suspected, very interesting for that reason alone.

Surprise surprise. Another excellent Zelda title. I particularly dug the control scheme, poking the screen with the stylus, slashing monsters and drawing little circles around Link were all nicely tactile and intuitive. Even driving the boat around was pretty fun, and anyone reading this blog will know how much I like to have my own boat to drive around.

Problem 023:

import scala.collection.mutable.Set;

object Euler23 extends Application {
  def sumdiv (x :Int) :Int = (1 :: List.flatten(for {
    divis <- List.range(2, Math.sqrt(x)+1)
    if x % divis == 0
  } yield List(divis, x / divis).removeDuplicates)).foldLeft(0)(_+_);

  val max = 28123;
  val abundant = List.range(1, max+1).filter(a => (a < sumdiv(a))).toArray;

  def filter (abund :Array[Int], ints :Set[Int], a :Int, b :Int) :Set[Int] = {
    ints -= (abund(a) + abund(b));
    if (b == abund.length-1)
      if (a == abund.length-1) return ints;
      else return filter(abund, ints, a+1, 0);
    else return filter(abund, ints, a, b+1);
  }
  println(filter(abundant, Set() ++ List.range(1, max+1), 0, 0).foldLeft(0)(_+_));
}

This was an annoying excercise in trying to get Scala not be idiotic about performance. Instead of that cumbersome recursive function, I wanted to simply write:

   var integers = Set() ++ List.range(1, max+1);
   for (a <- List.range(0, abundant.length);
        b <- List.range(a, abundant.length))
     integers -= (abundant(a) + abundant(b));
   println(integers.foldLeft(0)(_+_));

However, for some reason that took 164 seconds to execute. I wrote the same algorithm in Java which took about 450ms to execute. Clearly Scala was doing something ridiculous.

Looking at the decompiled byte codes we see where Scala gets into trouble. The for-comprehension approach generates code that looks plus or minus like so:

public Euler23 () {
    // ... compute abundant, etc.
    List.range(0, abundant().length).foreach(new AnonFunc() {
        public void apply (Object value) { apply(unbox(val)); }
        public void apply (int a) {
            List.range(a, abundant().length).foreach(new AnonFunc() {
                public void apply (Object value) { apply(unbox(val)); }
                public void apply (int b) {
                    integers().remove(box(abundant()[a] + abundant()[b]));
                }
            });
       }
    });
    // ... foldLeft, print sum, etc.
}

public int[] abundant () { return abundant; }
public Set integers () { return integers; }

private int[] abundant;
private Set integers;

So each time through the outer loop, we’re creating a new anonymous function (probably not a huge deal, abundant.length is only ~6600) and each time through the inner loop we’re accessing “integers” and “abundant” through non-final public method calls.

After seeing this, I suspected that if I passed “abundant” and “integers” to a recursive function call, it would pass those references directly rather than access them through a public method call. This would reduce the inner loop to a single recursive function call. As it turns out, Scala did me one better as you can see below:

public Set filter (int[] abund, Set ints, int a, int b) {
    do {
        ints.remove(box(abund[a] + abund[b]));
        if (b == abund.length - 1) {
            if (a == abund.length - 1)
                return ints;
            b = 0;
            a = a + 1;
        } else {
            b++;
        }
    } while(true);
}

Now it’s exceedingly clear why this code runs in ~2400ms compared to the ~164000ms of the for-comprehension-based code. Not only does Scala indeed pass the array and set directly, but it determined that my function was tail-recursive and turned it into a while loop.

The moral of the story here is perhaps not to map in your head “val something :Int” in Scala to “final int value” in Java because that’s clearly not what the compiler is doing. Perhaps using Scala in a more object oriented way by declaring classes and members would avoid this funny business. Using Application and writing my solution directly therein may result in semantics I neither need nor expect.

A peculiar film about a woman beating her head against the hierarchy and rigidity of corporate Japan. Strangely French and strangely Japanese at the same time. There are no doubt parallels to be discovered in comparing the two cultures.

Problem 022:

import scala.io.Source;
object Euler22 extends Application {
  def trim (name :String) = name.slice(1, name.length-1);
  val names = Source.fromFile("names.txt").getLine(0).split(',').map(trim).toList.sort(_<_);
  def score (name :String) = name.foldLeft(0)((s, l) => (s + (l - 'A' + 1)))
  println(List.range(0, names.length).map(i => ((i+1) * score(names(i)))).foldLeft(0)(_+_));
}

Another reasonably legible solution. I resisted the urge to do it all in a single expression.

I can see how language designers might succumb to the urge to expose a loop counter in their iteration functions because it would be nice to do:

  println(names.map(name => ((_INDEX_+1) * score(name))).foldLeft(0)(_+_));

Problem 021:

object Euler21 extends Application {
  def sumdiv (n :Int) = List.range(1, n/2+1).filter(div => n % div == 0).foldLeft(0)(_+_)
  println(List.range(1, 10000).filter(n => {
    val sdn = sumdiv(n); (n == sumdiv(sdn) && n != sdn && sdn < 10000)
  }).foldLeft(0)(_+_));
}

This one is almost readable — if you’ve been staring at a lot of Scala recently. It also uses a less efficient method for computing divisors because it fits on one line.

The above runs in 1176ms but the version using:

  def sumdiv (x :Int) = (1 :: List.flatten(for {
    divis < - List.range(2, Math.sqrt(x)+1)
    if x % divis == 0
  } yield List(divis, x / divis).removeDuplicates)).foldLeft(0)(_+_)

runs in 157ms. Oh the sacrifices we make for brevity.

Problem 020:

object Euler20 extends Application {
  def fact (n: BigInt): BigInt = if (n == 0) 1 else n * fact(n - 1)
  println(fact(100).toString().foldRight(0)((a, b) => (b + (a - '0'))));
}

Another one where BigInt does all the heavy lifting.

Problem 019:

object Euler19 extends Application {
  def norm (days :Int) :Function1[Int,Int] = ((year :Int) => (days));
  def leap (days :Int) :Function1[Int,Int] = ((year :Int) => {
    if ((year % 4 == 0) && (year % 100 != 0 || year % 400 == 0)) days+1;
    else days;
  });
  val length = Array(norm(31), leap(28), norm(31), norm(30), norm(31), norm(30),
                     norm(31), norm(31), norm(30), norm(31), norm(30), norm(31));

  println((for (year <- List.range(1900, 2001); month <- List.range(0, 12))
           yield Pair(year, month)).foldLeft(Pair(0, 0))(
             (acc :Pair[Int,Int], cur :Pair[Int,Int]) => (
               Pair(if (cur._1 > 1900 && acc._2 % 7 == 6) 1+acc._1 else acc._1,
                    acc._2 + length(cur._2)(cur._1))))._1);
}

This is a fine example of one of the big problems with functional languages. One is tempted to write ridiculous code like the above.

My first offense was minor. I started with a function that computed the length of a given month for a specified year like so:

  val monlens = Array(31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31);
  def length (year :Int, month :Int) :Int = {
    if ((month == 1) && (year % 4 == 0) && (year % 100 != 0 || year % 400 == 0))
      return monlens(month)+1;
    else
      return monlens(month);
  }

Then I decided to be clever and replace that with an array of functions each of which returned the number of days in the month in question when called with a particular year. This points toward the reason I suspect Odersky uses parenthesis for array dereference:

length(cur._2)(cur._1)

That’s actually an array dereference followed by a function call.

But then I went overboard and replaced my perfectly reasonable iterative solution:

  var days = 0;
  var firstSundays = 0;
  for (year < - List.range(1900, 2001)) {
    for (month <- List.range(0, 12)) {
      if (year > 1900 && days % 7 == 6) {
        firstSundays = firstSundays + 1;
      }
      days += length(month)(year);
    }
  }
  println(firstSundays);

with the single expression monstrosity you see above.

Back when I was learning functional programming with SML, we used to joke that you could implement any algorithm in one line with foldl. That may indeed be true, but readability ends up sacrificed and bleeding on the floor as a result.

Problem 018:

object Euler18 extends Application {
  val triangle = List(
     4, 62, 98, 27, 23,  9, 70, 98, 73, 93, 38, 53, 60,  4, 23,
      63, 66,  4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31,
        91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48,
          70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57,
            53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14,
              41, 48, 72, 33, 47, 32, 37, 16, 94, 29,
                41, 41, 26, 56, 83, 40, 80, 70, 33,
                  99, 65,  4, 28,  6, 16, 70, 92,
                    88,  2, 77, 73,  7, 63, 67,
                      19,  1, 23, 75,  3, 34,
                        20,  4, 82, 47, 65,
                          18, 35, 87, 10,
                            17, 47, 82,
                              95, 64,
                                75
  );

  def fold (triangle :List[Int], max :List[Int]) :Int = {
    if (max.length == 1) {
      return max(0);
    } else {
      return fold(triangle.drop(max.length-1), List.range(0, max.length-1).map(
        (i) => (triangle(i) + Math.max(max(i), max(i+1)))));
    }
  }
  var base = (Math.sqrt(1+8*triangle.length) - 1) / 2; // 15
  println(fold(triangle.drop(base), triangle.slice(0, base)));
}

The interesting thing about this one (other than my excellent triangle array formatting) is that we can simply fold the triangle up on itself computing the larger of each pair of elements in the bottom row and adding that larger value to the row above it.

A reduction step takes something like this:

        91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48,
      63, 66,  4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31,
     4, 62, 98, 27, 23,  9, 70, 98, 73, 93, 38, 53, 60,  4, 23,

and turns it into:

   91,  71,  52,  38,  17,  14,  91,  43,  58,  50,  27,  29,  48,
125, 164, 102,  95, 112, 123, 165, 128, 166, 109, 122, 145, 100, 54,

Then we fold that up into the next line and so on until we’ve got our solution in the top row.

Problem 017:

object Euler17 extends Application {
  val ones = Array("", "one", "two", "three", "four",
                   "five", "six", "seven", "eight", "nine");
  val tens = Array("ten", "twenty", "thirty", "forty",
                   "fifty", "sixty", "seventy", "eighty", "ninety");
  val teens = Array("ten", "eleven", "twelve", "thirteen", "fourteen",
                    "fifteen", "sixteen", "seventeen", "eighteen", "nineteen");

  def speak (number :Int) :String = {
    if (number >= 1000) {
      return "onethousand";
    } else if (number >= 100) {
      if (number % 100 == 0) {
        return speak(number/100) + "hundred";
      } else {
        return speak(number/100) + "hundredand" + speak(number%100);
      }
    } else if (number >= 20) {
      if (number % 10 == 0) {
        return tens(number/10-1);
      } else {
        return tens(number/10-1) + speak(number%10);
      }
    } else if (number >= 10) {
      return teens(number-10);
    } else {
      return ones(number);
    }
  }

  println(List.range(1, 1001).foldRight(0) { (a, b) => (b + speak(a).length) });
}

Nothing too exciting here.

Problem 016:

object Euler16 extends Application {
  println(BigInt(2).pow(1000).toString().foldRight(0) {(a, b) => (b + (a - '0'))});
}

This one almost seemed like cheating, since BigInt takes care of all the hard work for me.

Problem 015:

object Euler15 extends Application {
  val size = 20;
  def fact (n: BigInt): BigInt = if (n == 0) 1 else n * fact(n - 1)
  println(fact(size * 2) / (fact(size) * fact(size)))
}

I first started thinking about this as a caching problem, having just finished problem 14 which was reduced to a reasonable runtime by caching. At any coordinate in the grid, there are some number of unique paths from that position to the destination, so one could start in the bottom right and traverse the graph breadth first from the end to the start, caching the number of paths at each intersection and using that to efficiently compute the number of paths as you made your way to the start. I implemented this solution in Java and indeed 841 calls to a recursive function later I had my solution.

Then I realized that every path from the start to the finish is the same length and a series of an equal number of horizontal and vertical segments (20 horizontal and 20 vertical). Thus each unique path was a unique arrangement of those horizontal and vertical segments. If we consider the 40 positions in our path to be distinct elements then the problem becomes how many ways can we choose 20 of our positions in the path to contain horizontal segments (or vertical segments if you swing that way), which any good computer scientist knows is 40 choose 20: 40! / 20! (40 – 20)!.

The funny thing is that the caching solution in Java runs in less than 1 millisecond whereas computing the factorial in Scala above requires 2 milliseconds. It isn’t a tail recursive factorial function though, so that and the BigInt math probably take up all the time.

Problem 014:

import scala.collection.mutable.Map;

object Euler14 extends Application {
  var seen :Map[Long,Int] = Map();

  def iterate (value :Long) :Int = {
    val seenlen :Option[Int] = seen.get(value);
    if (seenlen != None) {
      return seenlen.get;
    } else if (value == 1) {
      return 1;
    } else if (value % 2 == 0) {
      val newlen = iterate(value/2)+1;
      seen.put(value, newlen);
      return newlen;
    } else {
      val newlen = iterate(3*value+1)+1;
      seen.put(value, newlen);
      return newlen;
    }
  }

  var longest = List.range(1, 1000000).map((n) => (Pair(n, iterate(n)))).foldLeft(Pair(0, 0))(
    (lpair, pair) => (if (lpair._2 > pair._2) lpair else pair));
  println(longest._1);
}

Because any given number will always converge to 1 in the same number of steps, once you reach a number for which you’ve already calculated the distance to 1 you can simply tack the previously calculated distance onto your current solution and Bob is your proverbial uncle.

Problem 013:

object Euler13 extends Application {
  val data = List("37107287533902102798797998220837590246510135740250",
                  "46376937677490009712648124896970078050417018260538",
                  "74324986199524741059474233309513058123726617309629",
                  "91942213363574161572522430563301811072406154908250",
                  "23067588207539346171171980310421047513778063246676",
                  "89261670696623633820136378418383684178734361726757",
                  "28112879812849979408065481931592621691275889832738",
                  "44274228917432520321923589422876796487670272189318",
                  "47451445736001306439091167216856844588711603153276",
                  "70386486105843025439939619828917593665686757934951",
                  "62176457141856560629502157223196586755079324193331",
                  "64906352462741904929101432445813822663347944758178",
                  "92575867718337217661963751590579239728245598838407",
                  "58203565325359399008402633568948830189458628227828",
                  "80181199384826282014278194139940567587151170094390",
                  "35398664372827112653829987240784473053190104293586",
                  "86515506006295864861532075273371959191420517255829",
                  "71693888707715466499115593487603532921714970056938",
                  "54370070576826684624621495650076471787294438377604",
                  "53282654108756828443191190634694037855217779295145",
                  "36123272525000296071075082563815656710885258350721",
                  "45876576172410976447339110607218265236877223636045",
                  "17423706905851860660448207621209813287860733969412",
                  "81142660418086830619328460811191061556940512689692",
                  "51934325451728388641918047049293215058642563049483",
                  "62467221648435076201727918039944693004732956340691",
                  "15732444386908125794514089057706229429197107928209",
                  "55037687525678773091862540744969844508330393682126",
                  "18336384825330154686196124348767681297534375946515",
                  "80386287592878490201521685554828717201219257766954",
                  "78182833757993103614740356856449095527097864797581",
                  "16726320100436897842553539920931837441497806860984",
                  "48403098129077791799088218795327364475675590848030",
                  "87086987551392711854517078544161852424320693150332",
                  "59959406895756536782107074926966537676326235447210",
                  "69793950679652694742597709739166693763042633987085",
                  "41052684708299085211399427365734116182760315001271",
                  "65378607361501080857009149939512557028198746004375",
                  "35829035317434717326932123578154982629742552737307",
                  "94953759765105305946966067683156574377167401875275",
                  "88902802571733229619176668713819931811048770190271",
                  "25267680276078003013678680992525463401061632866526",
                  "36270218540497705585629946580636237993140746255962",
                  "24074486908231174977792365466257246923322810917141",
                  "91430288197103288597806669760892938638285025333403",
                  "34413065578016127815921815005561868836468420090470",
                  "23053081172816430487623791969842487255036638784583",
                  "11487696932154902810424020138335124462181441773470",
                  "63783299490636259666498587618221225225512486764533",
                  "67720186971698544312419572409913959008952310058822",
                  "95548255300263520781532296796249481641953868218774",
                  "76085327132285723110424803456124867697064507995236",
                  "37774242535411291684276865538926205024910326572967",
                  "23701913275725675285653248258265463092207058596522",
                  "29798860272258331913126375147341994889534765745501",
                  "18495701454879288984856827726077713721403798879715",
                  "38298203783031473527721580348144513491373226651381",
                  "34829543829199918180278916522431027392251122869539",
                  "40957953066405232632538044100059654939159879593635",
                  "29746152185502371307642255121183693803580388584903",
                  "41698116222072977186158236678424689157993532961922",
                  "62467957194401269043877107275048102390895523597457",
                  "23189706772547915061505504953922979530901129967519",
                  "86188088225875314529584099251203829009407770775672",
                  "11306739708304724483816533873502340845647058077308",
                  "82959174767140363198008187129011875491310547126581",
                  "97623331044818386269515456334926366572897563400500",
                  "42846280183517070527831839425882145521227251250327",
                  "55121603546981200581762165212827652751691296897789",
                  "32238195734329339946437501907836945765883352399886",
                  "75506164965184775180738168837861091527357929701337",
                  "62177842752192623401942399639168044983993173312731",
                  "32924185707147349566916674687634660915035914677504",
                  "99518671430235219628894890102423325116913619626622",
                  "73267460800591547471830798392868535206946944540724",
                  "76841822524674417161514036427982273348055556214818",
                  "97142617910342598647204516893989422179826088076852",
                  "87783646182799346313767754307809363333018982642090",
                  "10848802521674670883215120185883543223812876952786",
                  "71329612474782464538636993009049310363619763878039",
                  "62184073572399794223406235393808339651327408011116",
                  "66627891981488087797941876876144230030984490851411",
                  "60661826293682836764744779239180335110989069790714",
                  "85786944089552990653640447425576083659976645795096",
                  "66024396409905389607120198219976047599490197230297",
                  "64913982680032973156037120041377903785566085089252",
                  "16730939319872750275468906903707539413042652315011",
                  "94809377245048795150954100921645863754710598436791",
                  "78639167021187492431995700641917969777599028300699",
                  "15368713711936614952811305876380278410754449733078",
                  "40789923115535562561142322423255033685442488917353",
                  "44889911501440648020369068063960672322193204149535",
                  "41503128880339536053299340368006977710650566631954",
                  "81234880673210146739058568557934581403627822703280",
                  "82616570773948327592232845941706525094512325230608",
                  "22918802058777319719839450180888072429661980811197",
                  "77158542502016545090413245809786882778948721859617",
                  "72107838435069186155435662884062257473692284509516",
                  "20849603980134001723930671666823555245252804609722",
                  "53503534226472524250874054075591789781264330331690");

  def toList (number :String) :List[Int] = {
    number.toList.map((c) => (c - '0'));
  }

  def toNumber (list :List[Int]) :Long = {
    list.foldLeft(0L)((a :Long, b :Int) => a*10 + b)
  }

  def sumTens (numbers :List[List[Int]]) :List[Int] = {
    var sum = 0;
    for (number <- numbers) {
      if (number.length > 0) {
        sum = sum + number.last;
      }
    }
    return toList(sum.toString());
  }

  def rightShift (numbers :List[List[Int]]) :List[List[Int]] = {
    numbers.map((list) => list.slice(0, list.length-1))
  }

  def sum (numbers :List[List[Int]]) :Long = {
    if (numbers.last.length < 9) {
      numbers.foldLeft(0L)((a :Long, b :List[Int]) => a + toNumber(b))
    } else {
      sum(rightShift(sumTens(numbers) :: numbers));
    }
  }

  println(sum(data.map((n) => toList(n))));
}

For this one, I simply summed the tens column of all the numbers and then tacked that sum onto the list of numbers and lopped off the tens column of all the numbers in the list. When I got down to 8 digit numbers, I simply summed them to get the final result.