Strona główna Polish Python Coders Group
   Strona główna   Pomoc Zaloguj się Rejestracja  
Witamy, Gość. Zaloguj się lub zarejestruj.
Czy dotarł do Ciebie email aktywacyjny?

Zaloguj się podając nazwę użytkownika, hasło i długość sesji

Aktualności:
Szukaj Szukaj
Strony: [1]   Do dołu
Drukuj
Wątek: [codewars] longest_slide_down  (Przeczytany 834 razy)
« : 23:38 15/11/17 »
Guaz Offline
Professional Python User

Zobacz profil
***

Reputacja: 41
Płeć: Mężczyzna
Wiadomości: 334


Hej, mam problem z pewnym zadaniem: (Wersja dla leniwych po cytacie)
Cytuj
###Lyrics... Pyramids are amazing! Both in architectural and mathematical sense. If you have a computer, you can mess with pyramids even if you are not in Egypt at the time. For example, let's consider the following problem. Imagine that you have a plane pyramid built of numbers, like this one here:

Kod:
  /3/
  \7\ 4
 2 \4\ 6
8 5 \9\ 3
Here comes the task...

Let's say that the 'slide down' is a sum of consecutive numbers from the top to the bottom of the pyramid. As you can see, the longest 'slide down' is 3 + 7 + 4 + 9 = 23

Your task is to write a function longestSlideDown (in ruby: longest_slide_down) that takes a pyramid representation as argument and returns its' longest 'slide down'. For example,

longestSlideDown([[3], [7, 4], [2, 4, 6], [8, 5, 9, 3]])
# => 23
###By the way... My tests include some extraordinarily high pyramides so as you can guess, brute-force method is a bad idea unless you have a few centuries to waste. You must come up with something more clever than that.

[Dla leniwych, zjeżdżanie z piramidy po najwyższych wartościach. Będących bezpośrednio pod ostatnią wybraną liczbą (wyobrażając sobie bloki tworzące piramide, to te które są fundamentami wybranego).]

Napisałem rozwiązanie które działa dla krótkiego przykładu, jednak z niezrozumiałych dla mnie powodów nie działa dla średniej piramidy. Nawet przy liczeniu na piechotę, wychodzi mi tak jak w programie, jakby test był nieprawidłowo napisany.

Moja funkcja:
Kod
def longest_slide_down(pyramid):
   suma = pyramid[0][0]
   last_item = 0
   for L in pyramid[1:]:
       if L[last_item] < L[last_item+1]: last_item += 1;
       suma += L[last_item]
       #print(L, suma, L[last_item]) #Taka wskazówka jakie wybiera liczby program jakby ktoś debugował.
   return suma

Testy:
Kod
Test.describe("longest_slide_down")
Test.it("should work for small pyramids")
Test.assert_equals(longest_slide_down([[3], [7, 4], [2, 4, 6], [8, 5, 9, 3]]), 23)
Test.it("should work for medium pyramids")
Test.assert_equals(longest_slide_down([
   [75],
   [95, 64],
   [17, 47, 82],
   [18, 35, 87, 10],
   [20,  4, 82, 47, 65],
   [19,  1, 23, 75,  3, 34],
   [88,  2, 77, 73,  7, 63, 67],
   [99, 65,  4, 28,  6, 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,  4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31],
   [ 4, 62, 98, 27, 23,  9, 70, 98, 73, 93, 38, 53, 60,  4, 23],
   ]), 1074)
 
Zapisane

Python 3.5.2 / Mint
« Odpowiedz #1 : 10:41 16/11/17 »
Guaz Offline
Professional Python User

Zobacz profil
***

Reputacja: 41
Płeć: Mężczyzna
Wiadomości: 334


W sumie już to rozgryzłem. Okazało się że źle to interpretuje. Sztuką tutaj nie ma być zjeżdżanie po najwyższej możliwej wartości, ale zjechanie tak by suma wartości była najwyższa. Trochę to przypomina operacje na macierzu, ale jakby był ktoś ciekaw mojego rozwiązania:
Kod
def longest_slide_down(pyramid):
   sumy = [[0 for j in range(len(pyramid[i]))] for i in range(len(pyramid))]
   sumy[0][0] = pyramid[0][0]
   for os_y, L in enumerate(pyramid, 0):
       for os_x in range(os_y+1):
           if not os_x:
               sumy[os_y][os_x] = max(sumy[os_y][os_x], sumy[os_y-1][os_x] + L[os_x])
           elif os_x < os_y:
               sumy[os_y][os_x] = max(sumy[os_y][os_x], sumy[os_y-1][os_x] + L[os_x], sumy[os_y-1][os_x-1] + L[os_x])
           else:
               sumy[os_y][os_x] = max(sumy[os_y][os_x], sumy[os_y-1][os_x-1] + L[os_x])
           #~ print(sumy[os_x])
   #~ print(max(sumy[:][-1]))
   return max(sumy[:][-1])
Printy zostawiam do debugowania dla ciekawych Uśmiech
Zapisane

Python 3.5.2 / Mint
Strony: [1]   Do góry
Drukuj
Skocz do:  

© 2007 - 2018 Polish Python Coders Group
Powered by SMF 1.1.21 | SMF © 2006-2009, Simple Machines | Theme by PixelSlot