Google Code Jam 2016

[TheDevilOnLine]

Wat is dat?

De Google Code Jam is een jaarlijkse programmeerwedstrijd die georganiseerd wordt door Google, met (tien)duizenden deelnemers over de hele wereld. Deelnemers moeten programmeerproblemen van algoritmische aard oplossen door een programma te schrijven en dat lokaal uit te voeren op de door Google gegenereerde testinvoer.

Voordeel van dit format is dat je je programma in een programmeertaal naar keuze kunt schrijven omdat je programma alleen op je eigen computer uitgevoerd wordt, wat ook makkelijk is met debuggen. Uiteindelijk stuur je de door jouw gegeneerde uitvoer in (en een kopie van je broncode, om plagiaat te voorkomen).

Als je voor het eerst meedoet, is het aan te raden om op z'n minst de officiële FAQ en QuickStart te lezen. Als het je nog niet duidelijk is wat voor soort problemen je voorgeschoteld zal krijgen, kun je oefenen op vragen van de vorige ronden; begin bijvoorbeeld met de vragen van de kwalificatieronde van 2013.

Wat kan ik winnen?

De hoofdprijs is $15.000! Verder zijn er kleinere prijzen voor alle 26 finalisten, die sowieso op Google's kosten op reis naar Californië gaan. Tenslotte krijgen de 1000 beste deelnemers een exclusief Google Code Jam T-shirt toegestuurd.

Een goede prestatie bij de Google Code Jam kan je ook helpen een baan als software engineer bij Google, als je daar in geïnteresseerd bent, en staat sowieso goed op je CV.

Hoe kan ik meedoen?

Wil je mee doen? Dan moet je je hier inschrijven en zaterdag 9 april meedoen aan de kwalificatieronde. (Deze ronde is 27 uur lang geopend, van zaterdag 01:00 tot zondag 04:00).

Het is bij de kwalificatieronde alleen van belang dat je een bepaald aantal punten binnensleept om je te plaatsen voor de eerste eliminatieronde. Pas in latere ronden (die elk tweeënhalf uur duren) is de tijd van belang. Je kunt rustig ergens om zaterdagmiddag beginnen, mits je een paar uur vrij hebt om een aantal problemen op te lossen. Hoeveel tijd je precies nodig hebt hangt er vanaf hoe goed je kunt programmeren, en hoeveel problemen je op wil lossen.

Zie ook het het volledige schema voor alle data en tijden, en de volledige regels voor alle verdere details.

Oorspronkelijk geschreven door Soultaker op woensdag 09 april 2014 @ 19:19, aangepast naar de huidige situatie

Opvallend is dit jaar dat voor het eerst de input file van een probleem al gegeven wordt, voordat je deze hoeft te downloaden. Hierdoor is het mogelijk om het resultaat te berekenen voordat de timer gaat lopen.

[patrick.k]

Ik vond het al vreemd dat er hier nog geen topic voor was, maar ik ben toch niet de enige die mee doet blijkt.

Net al de eerste 3 ingeleverd en zometeen nog maar even naar de laatste kijken.

[ Voor 2% gewijzigd door patrick.k op 09-04-2016 14:08 . Reden: derde was al geweest; laatste moet nog ]

[TheDevilOnLine]

Ik moet zeggen dat ik voor mijn gevoel er makkelijker doorheen kwam dan voorgaande jaren (heb voor het eerst volgens mij de volle 100 punten).

Ik ben er alleen nog niet over uit of dit komtrent doordat de vragen makkelijker zijn, of dat ik dit jaar Python ben gaan gebruiken (tot gisteren nog nooit wat met Python gedaan trouwens)

[Rikkiz0r]

Ik heb net snel even de eerste twee opgaves gemaakt, vond ze vrij simpel.
Als het goed is nu automatisch genoeg punten om door te gaan.

[Verwijderd]

Ik denk dat ik ook de volle 100 punten heb gehaald. Het is wel een beetje gek dat relatief weinig mensen voor het coin jam probleem gaan. De input is al bekend, dus je hebt tijd zat om daar een output bij te verzinnen, en als dat je lukt heb je je in feite al gelijk gekwalificeerd voor de volgende ronde.

[hydrargyrum]

Ik ben nu bezig met het coin jam probleem, de counting sheep is al gelukt. Alleen vindt mijn laptop coin jam niet zo leuk omdat het een hoop tijd kost om te berekenen

[TheDevilOnLine]

The day after

De kwalificaties zijn voorbij, mooi moment om even terug te blikken.

Counting sheep

Na wat kleine tests bleek zelfs de grote input binnen enkele itteraties op te halen. Wat ik heb gedaan is mijn huidige waarde (in het begin N) mod 10 te doen, het resultaat bitwise or met mijn validatie variabele te doen, mijn huidige waarde door 10 delen en dat herhalen totdat ik het gehele getal gehad heb. Mocht ik in mijn validatie variabele dan nog geen waarde van 1023 hebben, dan ga ik naar 2N etc.

Volgens mij was in deze casus de waarde 0 de enige waarde zonder geldig resultaat.

Note: voorgaande jaren heb ik dit altijd in PHP gedaan en had ik dus eigenlijk altijd problemen met de grote data set. Door dit jaar Python te gebruiken had ik dit probleem niet. Als je momenteel nog PHP gebruikt is de overstap naar Python echt aan te raden, de basis syntax voor dit soort problemen is best makkelijk te schrijven als je de logica ook in PHP kan bedenken.

Revenge of the Pancakes

Op het eerste oog een complex probleem, zeker omdat in een situatie als +-+ je niet de bovenste 2 pancakes kon omflippen, omdat dan het resultaat niet wijzigt.

Al snel bleek de oplossing echter relatief makkelijk. Doorloop de string van achter na voren, waarbij je begint met zoeken naar een -. Elke keer dat je een nieuwe groep tegen komt, heb je een extra 'flip' nodig.

Bijv. +-+ heeft 2 flips nodig, maar -+- 3

Coin Jam

Een opvallende opdracht omdat de inputs al bekend waren. In het begin zat ik er over te denken om alle primes te downloaden en van te voren op te slaan, maar aangezien je niet de eerste resultaten moest laten zien, maar gewoon een aantal willekeurige heb ik besloten om gewoon op zoek te gaan naar de divider en als ik bij divider 5000 nog geen geldig resultaat had, die case over te slaan.

Het enige wat toen nog overbleef is hoe je alle mogelijke binaire combinaties zou vinden die mogelijk geldig waren. Ik heb hier gekozen om de min en max waarde te berekenen (min = 1(gevulde met N-2 0-en)1, max = min = 1(gevulde met N-2 1-en)1) en dit in een for loop te gooien. Vervolgens check je bij elke waarde of de binaire string met een 1 begint en eindigt en dan pas gaan rekenen. (Mochten mensen een tip hebben hoe je met xrange in Python increments van 2 kan doen, please let me know)

Dit bleek snel genoeg om binnen enkele seconden zelfs de grote input te berekenen.

Fractiles

De kleine input was opvallend makkelijk, doordat K = S. Je kon hierdoor gewoon de eerste S karakters van de uitkomst lezen en dan wist je of er een G in zat of niet (als er geen G was, dan had je de volledige originele string gelezen, was er wel een G, dan was je deze gegarandeerd tegen gekomen).

De grote input bleek ik fout te hebben. Mijn logica was hierbij als volgt (Als je ziet waar ik fout denk, let me know):
- Als C = 1, dan moet S=K, anders kan je nooit zeker weten over er een G is of niet
- Als C > 1 dan moet je minimaal K -1 tegels kunnen zien. Mocht 1 G zijn, dan kan je dit ook op de 2de tegel zien, dus de eerste tegel hoef je eigenlijk nooit te testen. Echter moet je de rest van de tegels uit de originele string wel testen (als het eerste teken een L is, dan staat de gehele start string altijd aan het begin van de uiteindelijke reeks). Dit dacht ik ook uit sample case #5 te halen. Ze geven daar als voorbeeld dat je #2 en #6 moet kijken om het te weten, maar als je naar #2 en #3 kijkt, heb je het zelfde resultaat.

Overal analysis

Zoals eerder gezegd zijn voor mijn gevoel de kwalificatie vragen van dit jaar makkelijker dan vorig jaar, omdat voor de meeste opdracht geen berekening nodig is, of als dat wel zo is, dat het met simpel brute force haalbaar is. Ook Google's eigen analyse staat ondertussen online, waar nog een hoop extra info in te vinden is.

Voor mij dus 75 van de 100 punten. Hoe hebben jullie het gedaan?

[patrick.k]

Voor mij ook 75 van de 100 punten. Voor de grote set van Fractiles heb ik geen oplossing bedacht.

Voor Counting sheep heb ik simpelweg een lijstje bijgehouden welke getallen ik gevonden had. Daarna ben ik voor alle getallen behalve 0 gaan optellen tot ik alle getallen had gehad. 0 was het enige getal waarvoor geen oplossing was, dus dat maakte het een stuk simpeler.

Bij Revenge of the Pancakes heb ik hetzelfde idee gebruikt.

Ik heb het genereren van de coins iets anders opgelost bij Coin Jam. Hierdoor was de voorwaarde van een 1 op het begin en eind altijd waar. Ik heb de volgende code gebruikt om ze aan te maken:

Python:

results = 0
current = 0 
while results < J:
    coin_core = "{0:b}".format(current).zfill(N - 2)
    coin = "1%s1" % coin_core
    result = get_solution(coin)
    if result != None:
        results += 1
        print coin + " " + " ".join(map(str, result))
    current += 1

Om je vraag over xrange te beantwoorden. Als derde paramater kun je de stapgrootte opgeven. Bijvoorbeeld: xrange(0, 1000, 2)

Met Fractiles ben je verder gekomen dan ik dus daar heb ik niet veel over te zeggen.

Op de laatste vraag na vond ik de problemen inderdaad ook redelijk makkelijk. Ik vermoed dat het niveau een stuk hoger zal zijn in de eerste rondes.

[Verwijderd]

TheDevilOnLine schreef op zondag 10 april 2016 @ 09:23:

Fractiles

De kleine input was opvallend makkelijk, doordat K = S. Je kon hierdoor gewoon de eerste S karakters van de uitkomst lezen en dan wist je of er een G in zat of niet (als er geen G was, dan had je de volledige originele string gelezen, was er wel een G, dan was je deze gegarandeerd tegen gekomen).

De grote input bleek ik fout te hebben. Mijn logica was hierbij als volgt (Als je ziet waar ik fout denk, let me know):
- Als C = 1, dan moet S=K, anders kan je nooit zeker weten over er een G is of niet
- Als C > 1 dan moet je minimaal K -1 tegels kunnen zien. Mocht 1 G zijn, dan kan je dit ook op de 2de tegel zien, dus de eerste tegel hoef je eigenlijk nooit te testen. Echter moet je de rest van de tegels uit de originele string wel testen (als het eerste teken een L is, dan staat de gehele start string altijd aan het begin van de uiteindelijke reeks). Dit dacht ik ook uit sample case #5 te halen. Ze geven daar als voorbeeld dat je #2 en #6 moet kijken om het te weten, maar als je naar #2 en #3 kijkt, heb je het zelfde resultaat.

Je redenatie is prima, maar je kunt dat veel meer uitbuiten. Ik heb dat iets meer gedaan, maar ook nog niet genoeg waardoor ik ook niet de volle punten heb gekregen voor de laatste opgave. Als je in de (enkele) expansie van tegel 1 kiest voor de oorspronkelijke tegel 2 en in de expansie daarvan voor 3 enzovoort tot je uiteindelijk tegel C kiest in de laatste expansie, dan weet je dat als ook maar een van die eerste C tegels goud is, dan is de uiteindelijk geteste tegel ook van goud. Hetzelfde trucje kun je dan ook uithalen voor tegels C+1 t/m 2*C, zodat het altijd mogelijk als S*C >= K.

Het genereren van de coins kan trouwens makkelijk met bitmasks gedaan worden

Python:

for mask in xrange(1<<(n-2)): 
  coin = 1<<(n-1) | mask << 1 | 1

[Soultaker]

Verwijderd schreef op zondag 10 april 2016 @ 17:37:
Het genereren van de coins kan trouwens makkelijk met bitmasks gedaan worden

Python:

for mask in xrange(1<<(n-2)): 
  coin = 1<<(n-1) | mask << 1 | 1

Is 1<<(n-1) | 1 echt makkelijker dan 2**(n-1) + 1?

[ Voor 3% gewijzigd door Soultaker op 10-04-2016 18:23 ]