Ditjes en datjes over mijn werk studie en rest van mijn leven (welk leven? :+).

Tweakers dev challenge writeup - 15

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

Dit is de laatste opgave van de challenge, ik wil hierna nog even kort terugblikken op dingen die ik anders zou doen of willen zien volgend jaar. Ondanks dat ik wat kritisch ben heb ik hier best een leuke avond (nou ja meerdere korte fragmenten die bij elkaar een avond vormen) aan gehad.
Je bent bezig met een kassasysteem voor de horeca. De afnemer heeft een speciale vraag: om te voorkomen dat de klanten continu met stapels muntgeld in hun broekzakken moeten rondlopen wil hij zo min mogelijk munten teruggeven. Concreet wil hij na 1 aankoop nooit meer dan 5 muntstukken teruggeven.

Stel nu dat er in je kasla de volgende muntstukken liggen:

4 * ¤ 2,-
2 * ¤ 1,-
8 * ¤ 0,50
1 * ¤ 0,20
4 * ¤ 0,10
3 * ¤ 0,05
Hoeveel unieke bedragen kun je teruggeven met minimaal 1 en maximaal 5 munten?

Antwoord met een positieve integer (bijv. 15000).
Eigenlijk is de vraag dus: Als je maximaal 5 munten uit bovenstaande set kunt nemen, hoeveel unieke bedragen kun je genereren. Wat opvalt is dat de 8*0.50 euro natuurlijk onzin is in dat geval.

Mijn aanpak is redelijk brute-forceig, maar wel redelijk snel. Ik ga uit van het Cartesisch product van de set munten met zichzelf. Het aantal munten wordt bepaald door de repeat parameter van de product call.

Deze hieruit krijg ik een list van lists voor het aantal ingezette munten. De items in die list maak ik uniek ("3x 1 euro en 2x 2 euro" is gelijk aan "1x 2 euro, 3x 1 euro en 1x 2 euro"), wat een enorme besparing oplevert ... van 137560 items naar 1554 items in een voorbeeld. Wow, dat scheelt.
Dit doe ik voor alle omvangen van de set te gebruiken munten (dus 1 munt, 2 munten etc) en die resultaten veeg ik op 1 hoop in de for-lus.

Hierna ga ik kijken of de set munten valide is (we niet teveel munten van 1 soort hebben bijvoorbeeld), regel 29. Weer een filter-actie op een list :).

Daarna moeten we nog even de bedragen netjes afronden (werken met floats heeft wat quirks nu en dan) en stoppen we de bedragen weer in een set om ze uniek te krijgen. Hierna tellen we de lengte en dat is ons antwoord.


https://github.com/boudew.../tweakers-challenge/15.py

Python:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import itertools

# we berekenen een cartesiaans product en doen de check op de aantallen pas later...
coins=[2,1,0.5,0.2,0.1,0.05]

def setIsValid(s):
    if (s.count(2.0) > 4 or  s.count(1.0) > 2 or s.count(0.5) > 5 or s.count(0.2) >1 or s.count(0.1) > 4 or s.count(0.05)>3):
        return False
    else:
        return True
    
    
results=[]
for i in range(1,6):
    # de results als een list geeft 137560 opties
    # als set daarentegen 1554...
    results+= set(itertools.product(coins,repeat=i))    
# filter alle invalide combinaties uit (dwz: teveel munten)
results=list(filter(setIsValid,results))
# en tel alle bedragen bij elkaar op en stop ze in een set zodat ze uniek zijn....    
results=list(set(map(lambda i: round(sum(i),2),results)))
print(len(results))

Mijn algemene opmerkingen voor de challenge

Dit was een leuke challenge met afwisselende vragen, maar er was best wat kritiek over de kwaliteit en de consistentie van de vragen. 13 was echt een drama.

Een paar andere puntjes:
  • Volgende keer is het wellicht handig wat meer proefpersonen te nemen.
  • Sommige vragen zijn makkelijk te shortcutten, zoals de maanfase vraag.
  • De meeste vragen waren erg makkelijk, zeker als je standaardfuncties gebruikt, zoals de PIL library, het algoritme van Atkin en Fibonacci. Wellicht is het leuk om mensen zelf wat te laten ontwerpen?
  • Sommige vragen waren met een spreadsheet op te lossen. Op zich geen nadeel, maar is dat nog ontwikkelen? Ik zie het als op een slimme manier zo snel mogelijk zo goedkoop mogelijk aan een correct en beredeneer antwoord komen. En dan kan een spreadsheet prima.
  • De meeste vragen zijn te bruteforcen. Als je project euler bekijkt (vast een inspiratiebron van deze challenge, of de AIVD Cyber Challenge 2015 dan zie je dat de vragen minder brute-forcebaar zijn waardoor je je spelers meer na laat denken in plaats van op de CPU te vertrouwen. Met name de stage 0 hier vond ik erg leuk en leerzaam: https://github.com/smokel.../2015/AIVD_CYBERCHALLENGE . Eigenlijk helemaal niet zo moeilijk om op te zetten ;).
Tot volgend jaar!

Tweakers dev challenge writeup - 14

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

Ondanks dat ik een python fan ben lenen sommige problemen zich niet per definitie om in python op te lossen.
Dit is er een uit de categorie: met een bierviltje en enig denkwerk kom je net zo ver.
Een webwinkel heeft meerdere types korting door elkaar lopen. Wanneer een bestelling geplaatst wordt door een klant, kunnen al deze kortingen toepasselijk zijn. Onder aan de streep moeten de kortingen dusdanig zijn toegepast dat de totaalprijs zo gunstig mogelijk is voor de klant. Er kan wel telkens maar 1 korting op een product van toepassing zijn.

De mogelijke kortingen zijn:

*Korting op artikelniveau

*Korting op artikelgroepniveau

*Kortingen op klantniveau

*Kortingcode via een coupon


De volgende artikelen en artikelgroepen zijn aanwezig in het assortiment van de webwinkel.

Groepen:

*Beeldschermen (Momenteel een algemene korting van 10% op artikelen in deze groep)

*Adapters

*Harde schijven

*Moederborden (Momenteel een algemene korting van 5% op artikelen in deze groep)

Producten

*17 inch Retina Display in groep 'Beeldschermen'. ¤ 599,00

*15 inch VGA Display in groep 'Beeldschermen'. ¤ 59,00

*Kabeltje met adapter in groep 'Adapters'. ¤ 16,00

*1TB SSD Bikkelschijf 'Harde schijven'. ¤ 129,00 (Bij aanschaf van 5 '1TB SSD Bikkelschijf' schijven 30% korting op alle vijf de schijven).

*15TB NSA SSD in groep 'Harde schijven'. ¤ 412,00

*Gaming ZFER4 in groep 'Moederborden'. ¤ 165,00

*Office SSS4 in groep 'Moederborden'. ¤ 95,00


Momenteel heeft de webshop ook 1 geregistreerde klant:

*Klant A met 30% korting op producten uit de groep 'Adapters'


Vandaag komen onderstaande 2 bestellingen binnen bij de webshop:


Bestelling 1 door 'Klant A''
5 stuks 15 inch VGA Display
12 stuks Kabeltje met adapter
3 stuks 15TB NSA SSD
6 stuks Office SSS4

Bestelling 2 door 'gast'
'gast' gebruikt tevens de couponcode 'SCHIJF' voor 20% korting op artikelen uit de groep 'Harde schijven'

1 stuk Gaming ZFER4
2 stuks 17 inch Retina Display
5 stuks 1TB SSD Bikkelschijf


Hoe hoog was de omzet van de webshop vandaag?
Wat van belang is is dat je in de gaten houdt of er overlappende kortingen zijn, en dat is er helaas maar 1. Hierdoor is het triviaal om met de hand de goede korting te introduceren in plaats van beide of de verkeerde.
Als deze opgave meer artikelen, kortingen en klanten had geteld was het wel leuk geweest om even in Python te coden.
Ik heb een macje van de baas en heb eens gekeken naar de meegeleverde office-applicatie, resultaat. De XLSX versie staat hier.

Invuloefening, jammer hier had meer ingezeten met dynamische kortingen per dag, meer klanten en wellicht iets met valuta?


Op naar de laatste

Tweakers dev challenge writeup - 13

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

Tsja ik vond dit de minste opgave van deze challenge, niet vanwege de technische uitdagingen of het gebrek eraan maar vanwege de ambigue opgave.
Het zou enorm schelen als de logica duidelijker en eenduidiger was opgeschreven, nu was het een groot vragenfestijn. Daar is best wat discussie over geweest.

Sterker nog, ik draai net de code die ik ingecheckt heb en het spel zoekt een ander antwoord. Ik weet vrij zeker dat mijn antwoord kloppend was; ik heb na dit gedoe weinig zin gehad om nog een keer te gaan proberen en pielen. Maar, your mileage may vary. Als mensen een implementatie hebben die nu goed wordt gerekend wil ik deze graag hier delen, uiteraard met bronvermelding.

Goed, de vraagstelling:
De zombie apocalypse heeft toegeslagen. Patient zero is besmet geraakt nadat hij was gebeten door een mier tijdens het nachtelijk wildplassen. Precies om 0:00 zelfs.

De volgende waarden zijn van toepassing

*Op het moment van de besmetting van patient zero zijn er 7.000.000.000 mensen niet besmet.

*Elke zombie valt 2 mensen aan per uur tussen 8:00 en 22:00. In de nachtelijke uren is dit er 1 per uur.

*Elk uur raakt per 5 aanvallen afgerond naar beneden gemiddeld 1 lichaam van een gezond persoon te zwaar beschadigd om opnieuw op te staan. Deze persoon kan dus geen anderen infecteren.

*Vanaf 8:00 op de eerste dag heeft de mensheid door wat er aan de hand is en weet vanaf dan elk uur per drie aanvallen één aanval af te slaan en daarbij aan de zombie te ontsnappen.

*Omdat we uitgaan van gemiddelden, beginnen we elk uur opnieuw met het tellen van beschadigde lichamen en afgeweerde zombies.

Na hoeveel uren is het menselijk ras uitgestorven?
Je ziet hier wel al wat logica naar voren komen, maar het kan veel duidelijker. User gammuts heeft het hier heel veel beter verwoord:
Ik doe een poging tot herschrijven van vraag 13 - Zombie Nation:

De zombie-apocalypse heeft toegeslagen. Patient zero is besmet geraakt nadat hij was gebeten door een mier tijdens het nachtelijk wildplassen. Hij is gebeten tussen 00:00 en 00:59. Wanneer precies weten we niet en het boeit ons ook niet. Z'n eerste aanval komt toch tussen 01:00 en 02:00 (02:00 niet meegerekend, want dat is alweer het volgende uur). Precies om 00:00 zelfs. Daarom kan ie z'n eerste aanval nog gewoon doen tussen 00:00 en 01:00.


De volgende waarden zijn van toepassing:
Voor de besmetting zijn er 7.000.000.001 mensen. Na de besmeting zijn er dus 7.000.000.000 gezonde mensen en is er 1 actieve zombie.
Standaard valt elke zombie elk uur 1x aan. Van 08:00 tot 22:00 schijnt de zon en is elke zombie actiever: elke zombie valt dan elk uur 2x aan. (08:00-08:59 is het eerste uur, 21:00-21:59 is het laatste uur)
Nederland vergrijst nogal snel. 1 op de 5 heeft daarom een kunstgebit, is blind of doof of whatever. In ieder geval zal 1 op 5 nieuwe zombies zelf nooit anderen infecteren aanvallen (en daarom ook niet infecteren). Decimale mensen of zombies kennen we niet. Het aantal nieuwe zombies dat zelf niet kan infecteren aanvallen, ronden we af naar beneden. Ergo: het aantal nieuwe zombies dat zelf wel kan infecteren aanvallen, ronden we naar boven af.
Om 07:59:59 op de eerste dag heeft de mensheid door wat er aan de hand is en weet vanaf dan elk uur 1 op de 3 aanvallen af te slaan en daarbij de zombie uit te schakelen. Bij een afgeslagen aanval blijft de gezonde mens een gezond mens. Een uitgeschakelde zombie is nooit meer in staat om iemand te infecteren. Op de eerste dag is het eerste uur dat de mens aanvallen pareert het uur tussen 08:00 en 09:00. Afgeslagen aanvallen afronden naar beneden, geslaagde aanvallen naar boven afronden.
Vreemd genoeg lijkt een uur in een atomaire flits voorbij te gaan.
De oudjes hebben net zo veel kans om een aanval te pareren als enig ander mens; die gebeurtenissen hebben geen relatie.
Na hoeveel uren is het menselijk ras uitgestorven?
Goed, mijn toenmalig werkende implementatie:

https://github.com/boudew.../tweakers-challenge/13.py

Python:
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
import math

mensen=7000000000
tijd=0
zombies=1


    
    
    
while mensen > 0:
    tijd+=1
    uur = tijd % 24 
    aanvallen_per_uur=1 
    # aanvallen...
    if uur >=8 and uur < 22 : 
        aanvallen_per_uur=2
    aanvallen_per_uur*=zombies
    
    # de te zwaar gewonde persoons
    #mensen-= math.ceil(aanvallen_per_uur*0.2)

    if tijd > 8:
        aanvallen_per_uur=math.ceil(aanvallen_per_uur*0.6666666666666666666666666666666666)
        
    mensen-=aanvallen_per_uur
    zombies+=aanvallen_per_uur    
        
    print ("Tijd: "+str(tijd)+ " \t Uur: "+str(uur)+"  \tAanvallen per uur: "+str(aanvallen_per_uur)+" \tMensen "+str(mensen)+"\t Zombies: "+str(zombies))



Na deze draak van een opgave snel naar de webwinkel op: Boudewijns blog

Tweakers dev challenge writeup - 12

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

Deze opgave volgthetzelfde stramien als de romeinse cijfers opgave die we hier zagen:
  • Neem een staat
  • Voer acties uit en muteer de staat
  • Evalueer en herhaal indien nodig
Een Warrior, Mage en Rogue trekken een kerker in om deze vrij te waren van monsters. De aanval op ieder nieuw monster begint hetzelfde: de Warrior leidt de aanval en brengt de eerste slag toe. De Mage start net voor de eerste aanval van de Warrior met de casting tijd en als laatste begint de Roque met aanvallen. Omdat de heren avonturiers zo op elkaar afgestemd zijn gebeurt dit alles in een fractie van een seconde.

Warrior: Elke 4s 35 punten schade
Mage: 2s casting tijd en daarna elke 8s 80 punten schade
Rogue: Elke 4s 30 punten schade vanuit het primaire wapen en elke 3s 20 punten schade vanuit het secundaire wapen
Wanneer twee of meer avonturiers in dezelfde seconde aanvallen wordt de schade die door de Warrior gedaan wordt altijd eerst berekend, gevolgd door de schade van de Mage terwijl de Rogue binnen die seconde pas als laatste zijn schade toedient.
In de kerker komen de heren avonturiers de volgende monsters tegen

Monster 1 met 300 hitpoints
Monster 2 met 600 hitpoints
Monster 3 met 850 hitpoints
Monster 4 met 900 hitpoints
Monster 5 met 1100 hitpoints
Bossman met 3500 hitpoints


Wat is de totale hoeveelheid overkill die de Warrior toebrengt aan de monsters waarbij hij de doodslag toedient? De overkill is de hoeveelheid 'overbodige' schade omdat het monster voor het toedienen daarvan al verslagen is.
Als je redelijk leest en de gameplay-regels goed implementeert is het erg straightforward.

Wat het overzichtelijk maakt is een lijstje maken met de game-logica (ja nu wat overkill...) en daarbij noteren welke bondgenoot vanaf welk moment welke schade toebrengt.
Hierna maak je een functie waar je je hitpoints opgeeft, die vanaf tijdstip 0 tot tijdstip X gaat lopen en telkens deze regels toepast. Is het aantal hitpoints 0? Dan stop je. Is het aantal hitpoints kleiner dan 0... dan heb je overkill en geef je dat terug.
Aangezien alle bondgenoten tegelijk de schade toebrengen moet je eerst alle schade die seconde bij elkaar optellen, en daarna pas van de hitpoints aftrekken.

En zo geschiedde:
https://github.com/boudew.../tweakers-challenge/12.py

Python:
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
32
33
34
35
# retourneert overgebleven hitpoints. Van belang is je te realiseren dat OF de warrior iemand killt en dan is de overkill relevant, of iemand anders doet het en dan telt de overkill niet
def voerStrijd(vijand_hp):
    seconden=0
    while (vijand_hp > 0 ):
        #print ("Staat na seconden: "+str(seconden)+" @HP :"+str(vijand_hp))
        schade_deze_seconde=0
        # de warrior
        if (seconden %4 == 0):
            schade_deze_seconde += 35
            if vijand_hp-schade_deze_seconde<=0:
                return (abs(vijand_hp-schade_deze_seconde))
        # de mage
        if (seconden %8 == 2 ):
            schade_deze_seconde += 80
        # de rogue , primair
        if (seconden %4 == 0 ):
            schade_deze_seconde +=30
        # de rogue, secundair
        if ( seconden %3 ==0 ):
            schade_deze_seconde+=20
    
        seconden +=1
        vijand_hp-=schade_deze_seconde
        
    # de warrior heeft de vijand niet gedood dus score is niet relevant
    return 0    
        
warrior_overkill = voerStrijd(300)
warrior_overkill += voerStrijd(600)
warrior_overkill += voerStrijd(850)
warrior_overkill += voerStrijd(900)
warrior_overkill += voerStrijd(1100)
warrior_overkill += voerStrijd(3500)

print ("Warrior overkill: "+str(warrior_overkill))




Op naar de volgende dungeon, op:
Boudewijns blog

Tweakers dev challenge writeup - 11

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

Deze vond ik minder uitdagend, vooral omdat het standaardcode is.


De lijst getallen staat sowieso hier:
https://github.com/boudew...tweakers-challenge/11.txt


Wat ik als eerste gedaan heb is in de shell alvast optimaliseren door:

code:
1
johns-MacBook-Pro:tweakers-challenge john$ tr ' ' '\n' < 11.txt  | sort -u > 11.txt


Te draaien.
Dit levert 45595 hits in plaats va 54998 hits en alles staat meteen op een eigen regel en op volgorde. Altijd handig, maar uiteindelijk heb ik dat niet in de python code gebruikt.

De code in Python: https://github.com/boudew.../tweakers-challenge/11.py

Python:
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
32
33
34
35
36
37
38
39
40
41
import math

# het importeren van het bestand in een array...
lines=[]
with open('11.txt','r') as f:
    lines+= f.readlines()
    
input_getallen=[]
for i in lines:
    input_getallen+=map(lambda x: int(x), i.rstrip().split(" "))

# nu hebben we een list met de getallen uit de file.we sorteren die ook maar meteen.
input_getallen=sorted(input_getallen)

# we kunnen elk getal wel controleren op of het priem is, maar waarom niet alle priemgetallen tot het grootste getal uit de array nemen en die 2 sets over elkaar leggen?
#bron: http://stackoverflow.com/questions/21783160/sieve-of-atkin-implementation-in-python
def sieveOfAtkin(limit):
    P = [1,2,3]
    sieve=[False]*(limit+1)
    for x in range(1,int(math.sqrt(limit))+1):
        for y in range(1,int(math.sqrt(limit))+1):
            n = 4*x**2 + y**2
            if n<=limit and (n%12==1 or n%12==5) : sieve[n] = not sieve[n]
            n = 3*x**2+y**2
            if n<= limit and n%12==7 : sieve[n] = not sieve[n]
            n = 3*x**2 - y**2
            if x>y and n<=limit and n%12==11 : sieve[n] = not sieve[n]
    for x in range(5,int(math.sqrt(limit))):
        if sieve[x]:
            for y in range(x**2,limit+1,x**2):
                sieve[y] = False
    for p in range(5,limit):
        if sieve[p] : P.append(p)
    return P

# genereer alle priemgetallen tot het hoogste getal in. We maken er een set van omdat we zo een union operatie willen gebruiken 
priemgetallen=sorted(set(sieveOfAtkin(input_getallen[-1]+1)))

# deze filter en lambda voert in feite een intersectie in beide sets uit... items worden alleen bewaard indien ze in beide sets voorkomen
input_getallen=filter(lambda x: x in priemgetallen, input_getallen)
print (len(input_getallen))


Voor de priemgetal-test heb je een aantal welbekende functies, waaronder de zeef van Eratosthenes en het algoritme van Atkin. Die van Atkin is lekker snel en heb ik van internet gehaald.
ik heb voor Atikin gekozen omdat je makkelijk een limiet op kunt geven en dan gat het algoritme alle priemgetallen tot die limiet voor je genereren.

Omdat de getallen op regel 45 gesorteerd worden kan ik het laatste getal in de list als limiet voor atkin opgeven. Vervolgens le je de twee lijsten over elkaar en neem je alleen de getallen uit de vraagset die ook in de lijst met priemen voorkomen.

Verbeterpunt voor de volgende keer zou een set-union zijn wmb :).


Snel door naar: Boudewijns blog