Tweakers dev challenge writeup - 10

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

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

Tweakers dev challenge writeup - 9

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

Ondanks mijn aversie tegen one-liners... wordt dit er een :Y) .
Dit is wat mij betreft een te makkelijke vraag en ik snap niet zo goed wat deze in de challenge doet, maar dat terzijde.

https://github.com/boudew...r/tweakers-challenge/9.py

Python:
1
2
3
4
5
6
7
#1: reken het getal uit.
#2: maak dat binair
#3: maak er een string van
#4: filter alles wat niet "1" is uit (dat doet de filter met lambda functie)
#5: tel wat over blijft

print (len(filter(lambda x: x== "1", str(bin(5**128)))))



De binair naar string conversie doe ik omdat ik makkelijk op de losse tekens wil kunnen filteren; als ik een integer-list had kunnen maken was dat mooier geweest, maar dat gaat niet 1-2-3.


Deze serie gaat verder op:
Boudewijns blog

Tweakers dev challenge writeup - 8

Door Boudewijn op donderdag 1 oktober 2015 00:08 - Reacties (2)
Categorie: Tweakers dev challenge, Views: 859

TODO

Ik ben mijn code kwijt :(. Als iemand een mooie implementatie met wat commentaar heeft zet ik hem graag met bronvermelding hier neer.


Deze serie gaat verder op:
Boudewijns blog

Tweakers dev challenge writeup - 7

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

Grappige opgave, jammer dat hij erg simpel is als je eenmaal een plaatje in kunt lezen.
De bovenstaande wei staat helemaal vol met schapen.

De meeste schapen zijn wit, te herkennen aan de RGB waarde #ffffff of #fefefe.

Desondanks zijn er drie schapen die helemaal niet op deze lijken. Op welke locatie in de wei staan deze schapen, op volgorde van links naar rechts? Het assenstelsel begint in de linkerbovenhoek bij 0,0.

Antwoord als set van positieve integers, in het formaat X,Y / X,Y / X,Y (bijvoorbeeld: 10,40 / 15,50 / 70,12).
Het gelinkte plaatje is hier te vinden.

Wat we gaan doen is:

- lees het plaatje in in een list
- scan de list voor afwijkende kleuren, tenzij het de rand betreft

Easy as pie, als je tenminste de Python Imaging Library (PIL, http://www.pythonware.com/products/pil/) of Pillow gebruikt. Met easy_install is dit te installeren op je systeem.

https://github.com/boudew...r/tweakers-challenge/7.py

Python:
1
2
3
4
5
6
7
8
9
10
11
from PIL import Image
im = Image.open("7.jpg")
pixels = im.load()

for y in range(0,im.size[1]):
   for x in range(0,im.size[0]):
       # eerst de randen skippen
       if x not in [0,1,im.size[0]-1, im.size[0]-2] and y not in [0,1,im.size[1]-1, im.size[1]-2]:
           # en nu de pixels selecteren... een beetje wit telt ook als wit.
           if pixels[x,y] not in  [(255,255,255), (254, 254, 254),(253, 253, 253)]:
               print ("X: "+str(x)+" Y:"+str(y) + " " + str(pixels[x,y] ))


Waarom loop ik eerst de Y-as af en dan de X-as? Op deze manier zoek ik van boven naar onder, van links naar rechts. Vind ik persoonlijk fijn.
Langs de randen zitten wat net-niet-wit pixels, vermoedelijk door JPG compressie. Die worden genegeerd, dat zijn de 253 en 254 pixels.


Deze serie gaat verder op:
Boudewijns blog

Tweakers dev challenge writeup - 6

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

Pascals driehoek is een bekende piramide waarbij het bovenste getal 1 is en de opvolgende rijen de som zijn van de 2 bovenliggende aangrenzende getallen. Zie hieronder een voorbeeld :

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1


Bereken de som van de onderste rij van een Pascal-driehoek met duizend rijen. De top van de driehoek telt niet mee als rij.

Gebruik in je antwoord de wetenschappelijke notatie, rond af op 4 cijfers achter de komma, bijvoorbeeld: 1.0903E+23
Best leuk, omdat dit eigenlijk niet te bruteforcen is. Vol goede moed ben ik begonnen aan een python implementatie (Tsja ik wilde alles in Python doen) maar dat is gewoon niet te doen.

De driehoek van Pascal heeft echter best wel veel leuke eigenschappen; er komen Fibonacci-rijen in voor en nog veel meer dingen. Een van de leuke eigenschappen is dat de som van de getallen in rij n gelijk is aan 2^n .
Om het helemaal makkelijk te maken heb ik dit in combinatie met de wetenschappelijke notatie in wolphram alfa gegooid:

code:
1
scientific notation of 2^1000 to precision 5


Klaar. De precision was even tweaken.. et voila.


Deze som had ook in Python gekund, maar dat heeft hier te weinig meerwaarde.


Deze serie gaat (gelukkig weer in Python :P) verder op: Boudewijns blog