Problem 18

Projekt Euler w Ruby
1

Problem 18

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

[color=red]3[/color]

[color=red]7[/color] 5
2 [color=red]4[/color] 6
8 5 [color=red]9[/color] 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:

                        75
                      95 64
                    17 47 82
                  18 35 87 10
                20 04 82 47 65
              19 01 23 75 03 34
            88 02 77 73 07 63 67
          99 65 04 28 06 16 70 92
        41 41 26 56 83 40 80 70 33
      41 48 72 33 47 32 37 16 94 29  
    53 71 44 65 25 43 91 52 97 51 14
  70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48

63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)

2

taa, tutaj proponuję specjalne wyróżnienie publiczności dla zawodnika, któremu uda się rozwiązać zadanie bez odwracania rzeczy “do góry nogami” - i jednocześnie nie będzie liczeniem wszystkich możliwych ścieżek :wink:

3

Co masz na myśli pisząc “do góry nogami”?

4

ogólnie to perspektywę - taki mały tip (ale chyba oczywisty) - przynajmniej ja tak podszedłem do problemu - poczekajmy na rozwiązania …

5

[code]#!/usr/bin/env ruby
s = "
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23"

#s = "

3

7 5

2 4 6

#8 5 9 3"

t = s.strip.split("\n").collect { |l| l.split(" ").collect { |s| s.to_i } }

(t.length-2).downto(0) { |i| 0.upto(t[i].length-1) { |j| t[i][j] += t[i+1][j…j+1].max } }
p t[0][0][/code]
moze byc cos takiego?

6

jasne że może :slight_smile: - bardzo ładnie …