Skip to content

Project Euler mit Shellmitteln lösen

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. :-)

Trackbacks

Keine Trackbacks

Kommentare

Ansicht der Kommentare: Linear | Verschachtelt

Noch keine Kommentare

Kommentar schreiben

Umschließende Sterne heben ein Wort hervor (*wort*), per _wort_ kann ein Wort unterstrichen werden.
Standard-Text Smilies wie :-) und ;-) werden zu Bildern konvertiert.
BBCode-Formatierung erlaubt
Die angegebene E-Mail-Adresse wird nicht dargestellt, sondern nur für eventuelle Benachrichtigungen verwendet.

Um maschinelle und automatische Übertragung von Spamkommentaren zu verhindern, bitte die Zeichenfolge im dargestellten Bild in der Eingabemaske eintragen. Nur wenn die Zeichenfolge richtig eingegeben wurde, kann der Kommentar angenommen werden. Bitte beachten Sie, dass Ihr Browser Cookies unterstützen muss, um dieses Verfahren anzuwenden.
CAPTCHA

Sie können [geshi lang=LANG][/lang] Tags verwenden um Quellcode abhängig von der gewählten Programmiersprache einzubinden
Formular-Optionen
cronjob