$20\times 20$ tablodaki komşu $4$ sayının çarpımının en büyük değeri kaçtır?

Question

Project Euler'den problem $11$ şu şekildedir: 

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 $\color{red}{26}$ 38 40 67 59 54 70 66 18 38 64 70

67 26 20 68 02 62 12 20 95 $\color{red}{63}$ 94 39 63 08 40 91 66 49 94 21

24 55 58 05 66 73 99 26 97 17 $\color{red}{78}$ 78 96 83 14 88 34 89 63 72

21 36 23 09 75 00 76 44 20 45 35 $\color{red}{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

 

Kırmızı ile renklendirilmiş dört sayı komşudur: Bunların çarpımı $26\cdot 63 \cdot 78 \cdot 14 = 1788696$ dır. Yukarı, aşağı, sağ, sol veya köşegen yönünde komşu olan dört sayının çarpımı en fazla kaçtır?

 

Not: Soruların çözümlerinin kod yazarak yapılması beklenmektedir. Ben de daha sonra python çözümümü paylaşacağım.

 

 

Comments

emin olmak icin soruyorum sadece 45 dereceli diagonellere bakacagim degil mi ? At gibi hareketleri diagonelden saymiyoruz ?

---

At'ın hareketi gibi olmuyor. Aynı köşegen üzerindeki komşu olan sayılar olur. Ana köşegenlerden herhangi birine paralel olan dört doğrusal komşu sayı da olabilir. Örnekteki kırmızı renkli sayılar gibi. Yukarı-aşağı, sağ-sol yönler ve diğer köşegen yönü de unutulmamalı tabii.

Answer 1

Mathematica ile soyle yapabiliriz.

dikeyYatay[mat_] := Flatten[Partition[#, 4, 1] & /@ mat, 1]
kosegenAl[mat_] := dikeyYatay@(Diagonal[mat, #] & /@ Range[-16, 16])
Times @@@  Flatten[Through[{dikeyYatay, kosegenAl}[#]] & /@ {mat, Transpose@mat}, 2] // Max

Test etmek icin su matrisi kullandim

$mat=\left(
\begin{array}{cccccccccccccccccccc}
 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 \\
 21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 & 29 & 30 & 31 & 32 & 33 & 34 & 35 & 36 & 37 & 38 & 39 & 40 \\
 41 & 42 & 43 & 44 & 45 & 46 & 47 & 48 & 49 & 50 & 51 & 52 & 53 & 54 & 55 & 56 & 57 & 58 & 59 & 60 \\
 61 & 62 & 63 & 64 & 65 & 66 & 67 & 68 & 69 & 70 & 71 & 72 & 73 & 74 & 75 & 76 & 77 & 78 & 79 & 80 \\
 81 & 82 & 83 & 84 & 85 & 86 & 87 & 88 & 89 & 90 & 91 & 92 & 93 & 94 & 95 & 96 & 97 & 98 & 99 & 100 \\
 101 & 102 & 103 & 104 & 105 & 106 & 107 & 108 & 109 & 110 & 111 & 112 & 113 & 114 & 115 & 116 & 117 & 118 & 119 & 120 \\
 121 & 122 & 123 & 124 & 125 & 126 & 127 & 128 & 129 & 130 & 131 & 132 & 133 & 134 & 135 & 136 & 137 & 138 & 139 & 140 \\
 141 & 142 & 143 & 144 & 145 & 146 & 147 & 148 & 149 & 150 & 151 & 152 & 153 & 154 & 155 & 156 & 157 & 158 & 159 & 160 \\
 161 & 162 & 163 & 164 & 165 & 166 & 167 & 168 & 169 & 170 & 171 & 172 & 173 & 174 & 175 & 176 & 177 & 178 & 179 & 180 \\
 181 & 182 & 183 & 184 & 185 & 186 & 187 & 188 & 189 & 190 & 191 & 192 & 193 & 194 & 195 & 196 & 197 & 198 & 199 & 200 \\
 201 & 202 & 203 & 204 & 205 & 206 & 207 & 208 & 209 & 210 & 211 & 212 & 213 & 214 & 215 & 216 & 217 & 218 & 219 & 220 \\
 221 & 222 & 223 & 224 & 225 & 226 & 227 & 228 & 229 & 230 & 231 & 232 & 233 & 234 & 235 & 236 & 237 & 238 & 239 & 240 \\
 241 & 242 & 243 & 244 & 245 & 246 & 247 & 248 & 249 & 250 & 251 & 252 & 253 & 254 & 255 & 256 & 257 & 258 & 259 & 260 \\
 261 & 262 & 263 & 264 & 265 & 266 & 267 & 268 & 269 & 270 & 271 & 272 & 273 & 274 & 275 & 276 & 277 & 278 & 279 & 280 \\
 281 & 282 & 283 & 284 & 285 & 286 & 287 & 288 & 289 & 290 & 291 & 292 & 293 & 294 & 295 & 296 & 297 & 298 & 299 & 300 \\
 301 & 302 & 303 & 304 & 305 & 306 & 307 & 308 & 309 & 310 & 311 & 312 & 313 & 314 & 315 & 316 & 317 & 318 & 319 & 320 \\
 321 & 322 & 323 & 324 & 325 & 326 & 327 & 328 & 329 & 330 & 331 & 332 & 333 & 334 & 335 & 336 & 337 & 338 & 339 & 340 \\
 341 & 342 & 343 & 344 & 345 & 346 & 347 & 348 & 349 & 350 & 351 & 352 & 353 & 354 & 355 & 356 & 357 & 358 & 359 & 360 \\
 361 & 362 & 363 & 364 & 365 & 366 & 367 & 368 & 369 & 370 & 371 & 372 & 373 & 374 & 375 & 376 & 377 & 378 & 379 & 380 \\
 381 & 382 & 383 & 384 & 385 & 386 & 387 & 388 & 389 & 390 & 391 & 392 & 393 & 394 & 395 & 396 & 397 & 398 & 399 & 400 \\
\end{array}
\right)$

 

Cevabin $397*398*399*400=25217757600$ oldugu asikar ve kod bu cevabi veriyor.

Answer 2

Julia dilinde soyle hizli brute force bir cozumum oldu. Dogrulugundan yuzde yuz emin degilim ama paylasayim

julia> a = [ 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]
20×20 Matrix{Int64}:
  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

julia> function candidates(a)  ## BU cozum eksik/hatali 4 kisiye bakmak yerine 5 kisiye bakiyor
       s = Set()
       for i ∈ 1:16
           for j ∈ 1:16
               ret = a[i:i+4,j:j+4]
               for k ∈ 1:4
                   push!(s,ret[k,:])
                   push!(s,ret[:,k])
               end
               push!(s,diag(ret))
               push!(s,antidiag(ret))
           end
       end
       s
       end
candidates (generic function with 1 method)


julia> function candidates(a,n)  ## BU cozum eksik/hatali 4 kisiye bakmak yerine 5 kisiye bakiyor
       n = n-1
       s = Set()
       for i ∈ 1:16
           for j ∈ 1:16
               ret = a[i:i+n,j:j+n]
               for k ∈ 1:n
                   push!(s,ret[k,:])
                   push!(s,ret[:,k])
               end
               push!(s,diag(ret))
               push!(s,antidiag(ret))
           end
       end
       s
       end
candidates (generic function with 1 method)

julia> antidiag(x) = [x[i,end - i+1] for i in 1:size(x)[1] ]
antidiag (generic function with 1 method)

julia> candidates(a,4) .|> prod |> maximum
3318231678

 

Comments

Doğru cevap $3318231678$ den daha farklı bir sayıdır. $100^4 = 10^8$ olduğundan, yanıt en fazla $8$ basamaklı olabilir.

---

70600674 bu mu acaba buysa cok sacma bir hata yapmisim

---

Tebrikler @eloi doğru yanıt $70600674$

---

yukaridaki algoritma calisiyor sadece 4 tane yerine 5 tane komsuya bakiyordum

---

@eloi , yanıttaki kodunuzu güncelleyebilirseniz sevinirim. (Özel mesaj yazdım ama görünmedi belki.) Teşekkürler.

---

pardon yeni zamanim olabildi

Answer 3

num = '''
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
'''

# Önce string türündeki 400 sayıyı liste1'te tutuyoruz. liste2 isimli liste ile 20x20 türünde ve elemanları integer (tam sayı) türünde bir matris (veya listelerin listesini) oluşturuyoruz.

liste1 = num.split()
liste2 = []
for i in range(0,20):
  liste3 = []
  for j in range(0,20):
    liste3.append(int(liste1[20*i+j]))
  liste2.append(liste3)

# Yatay yönde komşu olan 4 sayının çarpımını prod isimli listede tutuyoruz.
prod = []
for i in range(0, 20):
    for j in range(0,17):
        p = liste2[i][j]*liste2[i][j+1]*liste2[i][j+2]*liste2[i][j+3]
        prod.append(p)


# Dikey yönde komşu olan 4 sayının çarpımını prod isimli listeye ekliyoruz. 
for i in range(0,17):
    for j in range(0,20):
        p = liste2[i][j]*liste2[i+1][j]*liste2[i+2][j]*liste2[i+3][j]
        prod.append(p)

# Esas köşegen yönünde komşu olan 4 sayının çarpımını prod isimli listeye ekliyoruz. 
for i in range(0,17):
    for j in range(0,17):
        p = liste2[i][j]*liste2[i+1][j+1]*liste2[i+2][j+2]*liste2[i+3][j+3]
        prod.append(p)

# İkinci köşegen yönünde komşu olan 4 sayının çarpımını prod isimli listeye ekliyoruz. 
for i in range(0,17):
    for j in range(0,17):
        p = liste2[i+3][j]*liste2[i+2][j+1]*liste2[i+1][j+2]*liste2[i][j+3]
        prod.append(p)

# Oluşabilecek tüm dörtlü çarpımlar prod isimli listededir. Bu listenin en büyük elemanını seçerek çözümümüzü tamamlarız.

print(max(prod))