Euler Solution 11

From ProgSoc Wiki

Jump to: navigation, search

Contents

Solutions for Problem 11

What is the greatest product of four numbers on the same straight line in the 20 by 20 grid shown below?

Python by Althalus

Runtime: 33 ms

from math import sqrt
import time
start_time = time.time()

#Get our grid. Take each line as a string.
grid =["08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08",
       "49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00",
       "81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65",
       "52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91",
       "22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80",
       "24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50",
       "32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70",
       "67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21",
       "24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72",
       "21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95",
       "78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92",
       "16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57",
       "86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58",
       "19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40",
       "04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66",
       "88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69",
       "04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36",
       "20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16",
       "20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54",
       "01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48"]

#Set up some vars
split_grid = []
biggest = 0

#Split each line at the spaces. Yay 2d lists!
for line in grid:
        split_grid.append(line.split())

#Loop thru all the positions
for i in range(0,20):
        for j in range(0,20):
                # loop horizontal.
                #Make sure we don't go out of range.
                if j+3<len(split_grid[i]):
                        value = int(split_grid[i][j])*int(split_grid[i][j+1])*int(split_grid[i][j+2])*int(split_grid[i][j+3])
                        if biggest < value:
                               biggest = value
                #loop vertical.
                if i+3<len(split_grid[j]):
                        value = int(split_grid[j][i])*int(split_grid[j][i+1])*int(split_grid[j][i+2])*int(split_grid[j][i+3])
                        if biggest < value:
                               biggest = value
                #Diagonal is a little different Down and right.
                if i+3 < len(split_grid[i]) and j+3 < len(split_grid[i]):
                        #print(value)
                        value = int(split_grid[i][j])*int(split_grid[i+1][j+1])*int(split_grid[i+2][j+2])*int(split_grid[i+3][j+3])        
                        if biggest < value:
                                biggest = value
                #Down and left.
                if i+3 < len(split_grid) and j-3 > -1:
                        #print(int(split_grid[i][j]),', ',int(split_grid[i-1][j-1]),', ',int(split_grid[i-2][j-2]),', ',int(split_grid[i-3][j-3]))
                        value = int(split_grid[i][j])*int(split_grid[i+1][j-1])*int(split_grid[i+2][j-2])*int(split_grid[i+3][j-3])        
                        if biggest < value:
                                biggest = value
        
print (biggest)
run_time = time.time() - start_time
print (run_time)


Java by tomchristmas

Runtime: 75ms

// Because UTS *is* a JavaSchool(TM) after all :P
// Plus it's a language I haven't used in a while.
// Plus I really enjoyed teaching the newbie (with Justin) how to
// instantiate a class...which is one of the things ProgSoc should be about
// (in addition to solving Euler problems ;)

// A true JavaSchool solution to the problem - brute force!

class Euler11 {

  public static void main(String args[]) {
     int[][] grid = {
                    {8, 2, 22, 97, 38, 15, 0, 40, 0, 75, 4, 5, 7, 78, 52, 12, 50, 77, 91, 8},
                    {49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 4, 56, 62, 0},
                    {81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 3, 49, 13, 36, 65},
                    {52, 70, 95, 23, 4, 60, 11, 42, 69, 24, 68, 56, 1, 32, 56, 71, 37, 2, 36, 91},
                    {22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80},
                    {24, 47, 32, 60, 99, 3, 45, 2, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50},
                    {32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70},
                    {67, 26, 20, 68, 2, 62, 12, 20, 95, 63, 94, 39, 63, 8, 40, 91, 66, 49, 94, 21},
                    {24, 55, 58, 5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72},
                    {21, 36, 23, 9, 75, 0, 76, 44, 20, 45, 35, 14, 0, 61, 33, 97, 34, 31, 33, 95},
                    {78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 3, 80, 4, 62, 16, 14, 9, 53, 56, 92},
                    {16, 39, 5, 42, 96, 35, 31, 47, 55, 58, 88, 24, 0, 17, 54, 24, 36, 29, 85, 57},
                    {86, 56, 0, 48, 35, 71, 89, 7, 5, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58},
                    {19, 80, 81, 68, 5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 4, 89, 55, 40},
                    {4, 52, 8, 83, 97, 35, 99, 16, 7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66},
                    {88, 36, 68, 87, 57, 62, 20, 72, 3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69},
                    {4, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18, 8, 46, 29, 32, 40, 62, 76, 36},
                    {20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 4, 36, 16},
                    {20, 73, 35, 29, 78, 31, 90, 1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 5, 54},
                    {1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 1, 89, 19, 67, 48}
                    };

     int i, j;
     int product = 0;

     for (i = 0; i <= 16; i++) {
         for (j = 0; j <= 16; j++) {
             int p = 0;

             p = grid[i][j] * grid[i][j+1] * grid[i][j+2] * grid[i][j+3];
             if (p > product) product = p;
             p = grid[i+1][j] * grid[i+1][j+1] * grid[i+1][j+2] * grid[i+1][j+3];
             if (p > product) product = p;
             p = grid[i+2][j] * grid[i+2][j+1] * grid[i+2][j+2] * grid[i+2][j+3];
             if (p > product) product = p;
             p = grid[i+3][j] * grid[i+3][j+1] * grid[i+3][j+2] * grid[i+3][j+3];
             if (p > product) product = p;
             p = grid[i][j] * grid[i+1][j] * grid[i+2][j] * grid[i+3][j];
             if (p > product) product = p;
             p = grid[i][j+1] * grid[i+1][j+1] * grid[i+2][j+1] * grid[i+3][j+1];
             if (p > product) product = p;
             p = grid[i][j+2] * grid[i+1][j+2] * grid[i+2][j+2] * grid[i+3][j+2];
             if (p > product) product = p;
             p = grid[i][j+3] * grid[i+1][j+3] * grid[i+2][j+3] * grid[i+3][j+3];
             if (p > product) product = p;
             p = grid[i][j] * grid[i+1][j+1] * grid[i+2][j+2] * grid[i+3][j+3];
             if (p > product) product = p;
             p = grid[i][j+3] * grid[i+1][j+2] * grid[i+2][j+1] * grid[i+3][j];
             if (p > product) product = p;
         }
     }

     System.out.println(Integer.toString(product));
     
   }
}

Lisp by SanguineV

Runtime (Script mode): 52.6ms


; The grid, as a list of lists.
(define grid '(
(08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08)
(49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00)
(81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65)
(52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91)
(22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80)
(24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50)
(32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70)
(67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21)
(24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72)
(21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95)
(78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92)
(16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57)
(86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58)
(19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40)
(04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66)
(88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69)
(04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36)
(20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16)
(20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54)
(01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 4)
))

; Given a list, return the maximum value of multiplying 4 consecutive elements.
(define (mult4 x)
  (if (> (length x) 3)
  (max (* (car x) (car (cdr x)) (car (cdr (cdr x))) (car (cdr (cdr (cdr x))))) (mult4 (cdr x)))
  0))

; Get the first 4 elements of a list (or return an empty list)
(define (get4 x)
  (if (> 4 (length x))
  '()
  (cons (car x) (cons (car (cdr x)) (cons (car (cdr (cdr x))) (cons (car (cdr (cdr (cdr x)))) ()))))))

; Multiply 4 elements diagonally in a list of lists; e.g.
; (takediag '(
; (1 2 3)
; (2 2 2)
; (3 3 2)) 3)
; Results in: (* 1 2 2) ==> 4
; Default to 0 if there is a lack of elements!
(define (takediag x n)
  (cond
    ((null? (car x)) 0)
    ((= n 1) (car (car x)))
    (else (* (car (car x)) (takediag (map cdr (cdr x)) (- n 1))))))

; Given a list of lists, take the 4 diagonals starting on each list in order and return
; the highest calculated value.
(define (iterdiag x)
  (if (> 4 (length x))
  0
  (max (takediag x 4) (iterdiag (cdr x)))))

; Given a list of lists, calculate the maximum using prior functions for each vertical
; and diagonal. (Note prior functions limit this to 4 elements.)
(define (calcvert x)
  (if (= 1 (length (car x)))
  (mult4 (map (lambda (z) (car z)) x))
  (max (mult4 (map (lambda (z) (car z)) x)) (iterdiag (map (lambda (z) (reverse (get4 z))) x)) (iterdiag x) (calcvert (map (lambda (y) (cdr y)) x)) )))

; Find the max of each horizontal and the verticals + diagonals.
(define (findthemax x)
  (max (eval (cons max (map mult4 x))) (calcvert x)))

; Run findthemax on the grid and display the result.
(begin (display (findthemax grid)) (newline))
(exit)

It's a bit ugly and I stopped when it worked - bonus points for people who can find optimisations!

Personal tools