Home › Blogs › garrett's blog ›

Project Euler Problem 11

garrett // Jun 15, 2009
//

The problem difficulty seems pretty random -- I'm pretty sure there were 'easier' problems which were harder to solve. Oh well.

My solution to Project Euler: Problem 11 is pretty straight-forward. And by that I mean brutish: Iterate across the columns of the 20x20 grid and keep track of the maximal product.

There are some optimizations to be made, I'm sure, but this will still crank out an answer in less than a second -- which is 'fast enough' for me.

Perl code below

  1. #!/usr/bin/perl -w
  2.  
  3. use strict;
  4.  
  5. # given a grid like this
  6. # 1 2 3
  7. # 4 5 6
  8. # 7 8 9
  9. #
  10. # find the largest product of three numers.  er--four numbers, i guess.
  11. # ie: 7 * 8 * 9 = 50,4
  12.  
  13. use Data::Dumper;
  14. use List::Util qw(min max);
  15.  
  16. my @array = (
  17. [8, 02, 22, 97, 38, 15, 00, 40, 00, 75, 04, 05, 07, 78, 52, 12, 50, 77, 91, 8],
  18. [49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 04, 56, 62, 00],
  19. [81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 03, 49, 13, 36, 65],
  20. [52, 70, 95, 23, 04, 60, 11, 42, 69, 24, 68, 56, 01, 32, 56, 71, 37, 02, 36, 91],
  21. [22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80],
  22. [24, 47, 32, 60, 99, 03, 45, 02, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50],
  23. [32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70],
  24. [67, 26, 20, 68, 2, 62, 12, 20, 95, 63, 94, 39, 63, 8, 40, 91, 66, 49, 94, 21],
  25. [24, 55, 58, 05, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72],
  26. [21, 36, 23, 9, 75, 00, 76, 44, 20, 45, 35, 14, 00, 61, 33, 97, 34, 31, 33, 95],
  27. [78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 03, 80, 04, 62, 16, 14, 9, 53, 56, 92],
  28. [16, 39, 05, 42, 96, 35, 31, 47, 55, 58, 88, 24, 00, 17, 54, 24, 36, 29, 85, 57],
  29. [86, 56, 00, 48, 35, 71, 89, 07, 05, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58],
  30. [19, 80, 81, 68, 5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 04, 89, 55, 40],
  31. [04, 52, 8, 83, 97, 35, 99, 16, 07, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66],
  32. [88, 36, 68, 87, 57, 62, 20, 72, 03, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69],
  33. [04, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18, 8, 46, 29, 32, 40, 62, 76, 36],
  34. [20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 04, 36, 16],
  35. [20, 73, 35, 29, 78, 31, 90, 01, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 05, 54],
  36. [01, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 01, 89, 19, 67, 48],
  37. );
  38.  
  39. # probably an easier way of getting the dimensions.
  40. # also multidim arrays in perl blow.
  41. my $cols;
  42. my $rows;
  43.  
  44. foreach my $row (@array) {
  45.   $rows++;
  46. }
  47. $cols = $rows;
  48.  
  49. # iterate across the grid and find the max product
  50. my $max = 0;
  51.  
  52. for(my $row = 0; $row < $rows; $row++) {
  53.   for(my $col = 0; $col < $cols; $col++) {
  54.     my $max_row_col = findRowCol($row, $col);
  55.     my $max_diag    = findDiag($row, $col);
  56.     $max = max($max, $max_row_col, $max_diag);
  57.   }
  58. }
  59.  
  60. printf("%d\n", $max);
  61.  
  62. # find the max row or column product from a given x,y position in the grid
  63. sub findRowCol {
  64.   my $row   = shift;
  65.   my $col   = shift;
  66.   my $prod  = 1;
  67.   for(my $x = $row; $x < $row+4; $x++) {
  68.     my $t_prod  = 1;
  69.     my $t2_prod = 1;
  70.     for(my $y = $col; $y < $col+4; $y++) {
  71.       $t_prod *= $array[$x][$y]   if($array[$x][$y]);
  72.       $t2_prod *= $array[$y][$x]  if($array[$y][$x]);
  73.     }
  74.     $prod = max($prod, $t_prod, $t2_prod);
  75.   }
  76.   return $prod;
  77. }
  78.  
  79. # find the max diagonal product from a given x,y position in the grid
  80. sub findDiag {
  81.   my $row     = shift;
  82.   my $col     = shift;
  83.   my $prod    = 0;
  84.   my $t_prod  = 1;
  85.   my $t2_prod = 1;
  86.   for(my $i = 0; $i < 4; $i++) {
  87.     # NW->SE diag
  88.     $t_prod  *= $array[$col+$i][$row+$i] if($array[$col+$i][$row+$i]);
  89.     # SW->NE diag
  90.     $t2_prod *= $array[$col+(3-$i)][$row+$i] if($array[$col+(3-$i)][$row+$i]);
  91.   }
  92.   $prod = max($prod, $t_prod, $t2_prod);
  93.   return $prod;
  94. }