≡ Menu

Clojure ProjectEuler No. 11 – The Naive Way

Featured

Problem 11 di Euler bener-bener ngeselin, ini dia problemnya:

In the 20×20 grid below, four numbers along a diagonal line have been marked in red.

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

The product of these numbers is 26 × 63 × 78 × 14 = 1788696.

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

So gimana kita bisa nemuin 4 angka yang berdekatan, baik horizontal, vertical, diagonal kiri, atau diagonal kanan?

Cara ini saya selesaikan dengan naive-way, saya secara brute force memeriksa semua kemungkinan.

Pertama saya download soalnya dulu:

(def p11-data
  (->> (slurp "https://projecteuler.net/problem=11")
       (re-seq #"\w+")
       (filter #(re-seq #"^[0-9]{2}$" %))
       (drop 6)
       (take 400)
       (map #(. Integer parseInt %))))

Representasi p11-data di atas adalah list satu dimensi:

(8 2 22 97 38 15 0 40 0 75 ... 48)

p11-data adalah input argumen yang berupa list satu dimensi. Karena yang kita cari adalah 4 angka berdekatan searah, maka kita harus membuat p11-data menjadi dua dimensi. Caranya dengan mempartisi p11-data ke dalam beberapa bagian yang satu arah. Baik horizontal, vertical, maupun diagonal kiri/kanan.

Untuk horizontal, kita tinggal menggunakan fungsi partition-all

(partition-all 20 p11-data)
 
;; data dua dimensi horizontal
 
((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))

Untuk vertical kita tinggal menggunakan melakukan mapping (partition-all 20 p11-data) ke dalam sebuah vector.

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

Bagian diagonal agak ribet. Pertama kita akan membuat list dua dimensi secara rekursif yang me-list n data ke n-1 data. Sehingga selanjutnya kita bisa melakukan mapping secara diagonal.

(defn p11-n-to-n--1 [data-coll]
  (loop [coll []
         data data-coll]
    (if data
      (recur (conj coll data) (next data))
      coll)))
 
(p11-n-to-n--1 p11-data)
 
;; => p11-data dua dimensi n sampai n-1.
 
[ ...
 (54 1 70 54 71 83 51 54 69 16 92 33 48 61 43 52 1 89 19 67 48)
 (1 70 54 71 83 51 54 69 16 92 33 48 61 43 52 1 89 19 67 48)
 (70 54 71 83 51 54 69 16 92 33 48 61 43 52 1 89 19 67 48)
 (54 71 83 51 54 69 16 92 33 48 61 43 52 1 89 19 67 48)
 (71 83 51 54 69 16 92 33 48 61 43 52 1 89 19 67 48)
 (83 51 54 69 16 92 33 48 61 43 52 1 89 19 67 48)
 (51 54 69 16 92 33 48 61 43 52 1 89 19 67 48)
 (54 69 16 92 33 48 61 43 52 1 89 19 67 48)
 (69 16 92 33 48 61 43 52 1 89 19 67 48)
 (16 92 33 48 61 43 52 1 89 19 67 48)
 (92 33 48 61 43 52 1 89 19 67 48)
 (33 48 61 43 52 1 89 19 67 48)
 (48 61 43 52 1 89 19 67 48)
 (61 43 52 1 89 19 67 48)
 (43 52 1 89 19 67 48)
 (52 1 89 19 67 48)
 (1 89 19 67 48)
 (89 19 67 48)
 (19 67 48)
 (67 48)
 (48)]

Untuk membuat diagonal list data dua dimensi kita hanya perlu mapping partition setiap 21 step.

(->> (map #(partition 1 21 %) (p11-n-to-n--1 p11-data))
     (map #(map first %))
     (take 20))
 
;;=> diagonal data list
 
((8 49 31 23 51 3 67 20 97 45 3 24 44 52 26 32 40 4 5 48)
 (2 99 73 4 67 45 10 95 17 35 80 0 60 17 79 63 62 36 54)
 (22 40 55 60 63 2 26 63 78 14 4 17 21 77 33 93 76 16 1)
 (97 17 79 11 89 44 38 94 78 0 62 54 58 4 27 53 36 20 70)
 (38 81 14 42 41 75 40 39 96 61 16 24 51 89 98 69 20 73 54)
 (15 18 29 69 92 33 67 63 83 33 14 36 54 55 66 4 69 35 71)
 (0 57 93 24 36 53 59 8 14 97 9 29 17 40 88 42 36 29 83)
 (40 60 71 68 54 78 54 40 88 34 53 85 58 4 36 16 41 78 51)
 (0 87 40 56 22 36 70 91 34 31 56 57 19 52 68 73 72 31 54)
 (75 17 67 1 40 84 66 66 89 33 92 86 80 8 87 38 30 90 69)
 (4 40 53 32 40 20 18 49 63 95 16 56 81 83 57 25 23 1 16)
 (5 98 88 56 28 35 38 94 72 78 39 0 68 97 62 39 88 74 92)
 (7 43 30 71 66 17 64 21 21 17 5 48 5 35 20 11 34 31 33)
 (78 69 3 37 33 12 70 24 36 53 42 35 94 99 72 24 62 49 48)
 (52 48 49 2 13 50 67 55 23 28 96 71 47 16 3 94 99 71 61)
 (12 4 13 36 80 32 26 58 9 22 35 89 69 7 46 72 69 48 43)
 (50 56 36 91 24 98 20 5 75 75 31 7 28 97 33 18 82 86 52)
 (77 62 65 22 47 81 68 66 0 31 47 5 73 57 67 8 67 81 1)
 (91 0 52 31 32 28 2 73 76 67 55 44 92 32 46 46 59 16 89)
 (8 81 70 16 60 64 62 99 44 15 58 44 13 16 55 29 85 23 19))

Data diagonal list di atas masih ada bug. Karena untuk data ke 2 sampai data ke-n, list diagonal salah. Diagonal data list hanya valid untuk setengah bagian atas, setengah bagian bawah salah.

Untuk itu, secar rekursif kita hanya akan mengambil data diagonal setengah atas.

(defn p11-half-diagonal
  [data-n-to-n--1-list]
  (let [diagonal-data (->> (map #(partition 1 21 %) data-n-to-n--1-list)
                           (map #(map first %))
                           (take 20))]
    (loop [top-half-diagonal-data []
           data diagonal-data
           n-line 20]
      (if data
        (recur (conj top-half-diagonal-data
                     (take n-line (first data)))
               (next data)
               (dec n-line))
        top-half-diagonal-data))))
 
;; 
 
(-> p11-data
    (p11-n-to-n--1)
    (p11-half-diagonal))
 
[(8 49 31 23 51 3 67 20 97 45 3 24 44 52 26 32 40 4 5 48)
 (2 99 73 4 67 45 10 95 17 35 80 0 60 17 79 63 62 36 54)
 (22 40 55 60 63 2 26 63 78 14 4 17 21 77 33 93 76 16)
 (97 17 79 11 89 44 38 94 78 0 62 54 58 4 27 53 36)
 (38 81 14 42 41 75 40 39 96 61 16 24 51 89 98 69)
 (15 18 29 69 92 33 67 63 83 33 14 36 54 55 66)
 (0 57 93 24 36 53 59 8 14 97 9 29 17 40)
 (40 60 71 68 54 78 54 40 88 34 53 85 58)
 (0 87 40 56 22 36 70 91 34 31 56 57)
 (75 17 67 1 40 84 66 66 89 33 92)
 (4 40 53 32 40 20 18 49 63 95)
 (5 98 88 56 28 35 38 94 72)
 (7 43 30 71 66 17 64 21)
 (78 69 3 37 33 12 70)
 (52 48 49 2 13 50)
 (12 4 13 36 80)
 (50 56 36 91)
 (77 62 65)
 (91 0)
 (8)]

Ok, kita sudah memiliki data horizontal, data vertical, data diagonal. Untuk data diagonal lain, kita hanya perlu melakukan mirroring atau reverse data.

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

Terakhir, kita tinggal membuat fungsi yang akan membagi setiap list dalam data dua dimensi menjadi beberapa list yang memiliki 4 entitas data berdekatan saja.

 
(->> p11-data ;; contoh data horizontal
     (partition-all 20)
     (map #(partition-all 4 1 %))
     (map #(filter (fn [x] (= 4 (count x))) %))
 
;; contoh data horizontal line pertama
(((8 2 22 97)
  (2 22 97 38)
  (22 97 38 15)
  (97 38 15 0)
  (38 15 0 40)
  (15 0 40 0)
  (0 40 0 75)
  (40 0 75 4)
  (0 75 4 5)
  (75 4 5 7)
  (4 5 7 78)
  (5 7 78 52)
  (7 78 52 12)
  (78 52 12 50)
  (52 12 50 77)
  (12 50 77 91)
  (50 77 91 8))
...)

Selanjutnya cari produk terbesar:

(defn p11-max [c]
  (->> p11-data
       (map #(partition-all 4 1 %))
       (map #(filter (fn [x] (= 4 (count x))) %))
       (map #(map (fn [c] (reduce * c)) %))
       (flatten)
       (apply max)))

Sehingga, fungsi keseluruhan adalah:

(defn p11 [data]
  (let [horizontal (partition-all 20 data)
        vertical (->> horizontal
                      (apply map vector))
        fhalf-right (-> data p11-n-to-n--1 p11-half-diagonal)
        shalf-right (-> (reverse data) p11-n-to-n--1 p11-half-diagonal)
        fhalf-left (-> (p11-mirror data) p11-n-to-n--1 p11-half-diagonal)
        shalf-left (-> (reverse (p11-mirror data)) p11-n-to-n--1 p11-half-diagonal)]
    (max (p11-max horizontal)
         (p11-max vertical)
         (p11-max fhalf-right)
         (p11-max shalf-right)
         (p11-max fhalf-left)
         (p11-max shalf-left))))

**

Saya harap teman-teman bisa berbagi kode yang lebih sederhana dan lebih cantik dengan saya. Thanks.

{ 1 comment… add one }
  • Nurul nisa March 28, 2018, 12:55 pm

    Apa yang dimaksud list dua dimensi?

Leave a Comment