November 29, 2008

What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 2020 grid?


This solution scans four rows at a time, saves the max adjacent product and scans the next four rows.

(defparameter *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)))

(defun max-r (grid)
"Returns the maximum product of each rows elements"
(apply #'max (mapcar #'(lambda (lst) (apply #'* lst))
grid)))

(defun max-c (grid)
"Returns the maximum product of each columns elements"
;; Transpose the grid then call max-r
(max-r (apply #'mapcar #'list grid)))

(defun diag-prod (grid &optional (accum 1))
"Returns the product of the grids diagonal elements,
starting from the top left to the bottom right.
The function works recursively. If there is a top-left
element in the grid, it multiplies accum by the element.
Then it calls itself with the top row and first column
of the grid removed"
(if grid
(diag-prod (mapcar #'cdr (cdr grid)) (* accum (caar grid)))
accum))

(defun max-d (grid)
"Returns the maximum product of each diagonals elements"
(max (diag-prod grid)
(diag-prod (mapcar #'reverse grid))))

(defun max-adj (grid)
"Returns the maximum product of the grids adjacent elements.
Elements are multiplied in rows, columns, and diagonals"
(max (max-r grid) (max-c grid) (max-d grid)))

(defun max-in-4byX (grid &optional (result 0))
"Returns the maximum product of 4 adjacent elements in
a grid with 4 rows and a variable number of columns"
(if (< (length (car grid)) 4)
result
(let* ((subgrid (mapcar #'(lambda (lst)
(subseq lst 0 4))
grid))
(max-in-subgrid (max-adj subgrid))
(cur-result (cond ((< result max-in-subgrid) max-in-subgrid)
(t result))))
(max-in-4byX (mapcar #'cdr grid) cur-result))))

(defun euler-11 (grid &optional (result 0))
"Calculates the max prod of 4 adjacent elements in the top 4 rows
of a grid, removes the top row and repeats. Returns the maximum
product of 4 adjacent numbers in the entire grid"
(if (< (length grid) 4)
result
(let* ((top-4-rows (subseq grid 0 4))
(max-in-top-4 (max-in-4byX top-4-rows))
(cur-result (cond ((< result max-in-top-4) max-in-top-4)
(t result))))
(euler-11 (cdr grid) cur-result))))

0 comments: