Tweakers dev challenge writeup - 10

Door Boudewijn op donderdag 1 oktober 2015 00:10 - Reacties (0)
Categorie: Tweakers dev challenge, Views: 1.359

Een leuke opgave omdat je zelf even na moet denken hoe je dingen aan gaat pakken.

De driehoek is ook te vinden op https://github.com/boudew...challenge/10.triangle.txt en de code https://github.com/boudew.../tweakers-challenge/10.py:
Je kunt in een driehoek van boven naar beneden wandelen door naar aangrenzende 'vakjes' te stappen. Zoek de route door de driehoek die de hoogste som oplevert zoals in het voorbeeld hieronder:

59
41 73
40 52 09

De maximale som is 184
Download de driehoek in de bijlage hieronder.

Vind hierin de optimale route die de hoogst mogelijke som oplevert van boven naar beneden. Je mag hierbij van boven naar beneden vanuit elk vakje alleen naar de vakjes direct beneden en rechtsonder het betreffende getal stappen, alle andere vakjes zijn te ver weg.

Antwoord als positief integer, bijvoorbeeld 15000
Tsja en dan begin je bovenaan en weet je niet meer hoeveel paden je uit moet rekenen. Dat zijn er heel veel. Ik heb even kort naar Dijkstra (https://nl.wikipedia.org/wiki/Kortstepad-algoritme) gekeken maar dat wordt hem ook niet direct.

Echter, waarom niet de andere kant op rekenen?

Neem de een na onderste (!) rij en tel bij elk van de waarden van die onderste rij de hoogste kandidaat van de onderste rij op.

Dus als je een rij hebt:


code:
1
2
1 2 3 4 5
6 9 8 3 1 2


Dan wordt de nieuwe rij:

code:
1
2
(1+9) (2+9) (3+8) (4+3) (5+2)
10 11 11 7 7



Het leuke is dat je je probleem met 1 rij hebt gereduceerd en je deze truc tot de bovenste rij uit kunt voeren.... en dat doe ik dan ook in de code:
https://github.com/boudew.../tweakers-challenge/10.py



code:
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
def leesDrieHoekIn(bestand):  
    result =[]
    with open(bestand,'r') as f:
        result+= f.readlines()
    result = map(lambda x: map(lambda y: int(y),x.rstrip().split(" ")), result)
    return result


def reduceerRijen(r1, r2):
    if not (len(r2)-len(r1) == 1 ):
        print ("Lengte mismatch, stop er nu mee!" )
        exit(1)
    result=[]
    for i in range(0,len(r1)):
        if (r2[i] > r2[i+1]):
            result.append(r1[i]+r2[i])
        else:
            result.append(r1[i]+r2[i+1])
        
    return (result)



triangle=(leesDrieHoekIn("10.triangle.txt"))

# TODO: De functie omschrijven zodat hij reduceert, dan hoef je ook niet meer te indiceren.
# we gaan nu een voor een de rijen reduceren, van onderaf (daarom de truc met de indices)
for i in range(0,199):
    triangle[198-i]=reduceerRijen(triangle[198-i], triangle[198-i+1])

print(triangle)


Tsja de TODO die ik er zelf in heb gezet is wel waar... eigenlijk wil je de code onafhankelijk van de grootte van de driehoek hebben. Niet veel werk, maar ik heb er even geen zin meer in :Y.

Deze serie gaat verder op:
Boudewijns blog

Volgende: Tweakers dev challenge writeup - 11 10-'15 Tweakers dev challenge writeup - 11
Volgende: Tweakers dev challenge writeup - 9 10-'15 Tweakers dev challenge writeup - 9

Reacties

Er zijn nog geen reacties op deze post


Om te kunnen reageren moet je ingelogd zijn. Via deze link kun je inloggen als je al geregistreerd bent. Indien je nog geen account hebt kun je er hier één aanmaken.