Qbi's Weblog

Als ich kürzlich mit Sven über das Projekt Euler sprach, hatte er recht schnell einen Lösungsvorschlag parat. Auf die Frage, wie er das gemacht habe, antwortetet er: vim..

Nun war das elfte Problem an der Reihe und ich erinnerte mich wieder an Svens Worte. In dem Problem ist eine 20x20 Matrix gegeben und man soll das größte Produkt von vier nebeneinanderliegenden Zahlen finden:

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

Nach einigen Überlegungen kam ich zu dem Schluss, dass die Zahlen in der Lösung größer als 74 sein müssen. Dann kam sed zum Einsatz: sed ‘s,\([0-6][0-9]\|7[0-4]\) , ,g’ problem11. Übrig blieb die untenstehende Matrix:

         97                75          78          77 91    
      99       81          87       98                      
81             79       93             88                   
      95                                                 91 
                     89    92                            80 
            99             75       78    84                
   98 81                                                    
                        95    94             91       94    
                  99    97    78 78 96 83    88    89       
            75    76                         97          95 
78             75          94    80                      92 
            96                88                      85    
86                89                                        
   80 81       94             92    86       77    89       
         83 97    99       97                79       98    
88       87                                        93       
                           94                         76    
                     88       99    82       85             
            78    90                   86 81                
            83             92                   89          


Hier fielen mir sofor die markierten Viererblöcke ins Auge, wobei das Produkt der rot markierten Zahlen größer sein muss als das der blau markierten. Als gab ich die Lösung ein und hatte schnell die richtige Lösung.