Tweakers dev challenge writeup - 15

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

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!

Volgende: Tweakers dev challenge writeup - 14 10-'15 Tweakers dev challenge writeup - 14

Reacties


Door Tweakers user addo2, donderdag 1 oktober 2015 07:53

Als iemand die niet kan programmeren maar wel aardig kan rekenen was de 1e opgave onmogelijk. Vervolgens komen er ongeveer 10 opgaven die bijna allemaal met wat standaard wiskunde/excel/pen-en-papier kan oplossen. Ik vind dat deze volgorde wel wat flauw: programmeerkennis is nodig voor vraag 1 en boeren logica komt daarna pas...

Het lijkt er ook op dat de programeeropdrachten (vanuit het oogpunt van iemand die niet kan programmeren) meer met brute-forcen te maken hebben dan met tactvol programeren. Het enige probleem met pen en papier is de grootte van de groep.

Door Tweakers user nietorigineel, donderdag 1 oktober 2015 10:47

addo2 schreef op donderdag 01 oktober 2015 @ 07:53:
Het lijkt er ook op dat de programeeropdrachten (vanuit het oogpunt van iemand die niet kan programmeren) meer met brute-forcen te maken hebben dan met tactvol programeren. Het enige probleem met pen en papier is de grootte van de groep.
Je kon de meeste dingen brute-forcen, maar dat hoefde zeker niet. Boel elegante/supercompacte oplossingen gezien (niet van mijzelf zal ik direct toegeven).

De challenge nodigde niet perse uit tot het vinden van dat soort elegante oplossingen, omdat de focus lag op puur het juiste antwoord.

Reactie formulier
(verplicht)
(verplicht, maar wordt niet getoond)
(optioneel)

Voer de code van onderstaand anti-spam plaatje in: