Som Michael Schøler fra Hinnerup Net ApS netop gjorde mig opmærksom på er Google Treasure Hunt 2008 skudt igang.

Michael foreslår en Java-baseret rekursiv løsning på den første opgave, som udnytter Javas BigInteger klasse til at håndtere tallene, som ret hurtigt bliver ret store. Løsningen er som sådan fin nok, men jeg foreslår her et alternativ: en PHP-baseret løsning på kun 12 linier (mod Michaels 42), som her er stillet til rådighed som en web service.

Koden ser ud som følger. Den beregner antallet af muligheder iterativt igennem matricen. Antallet af muligheder i det sidste felt returneres:

function google2008_1($w, $h) {
  // Fill matrix
  for ($row = 1; $row <= $h; $row++) {
    for ($col = 1; $col <= $w; $col++) {
      if ($row == 1 || $col == 1) {
        $grid[$row][$col] = "1";
      } else {
        $grid[$row][$col] = bcadd($grid[$row-1][$col], $grid[$row][$col-1]);
      }
    }
  }
  
  // Return result
  return $grid[$h][$w];
}

Koden kan afvikles direkte her (bemærk at servicen af belastningsmæssige årsager er begrænset til maksimalt 100 rækker og kolonner):

Resultatet er: