Google Code Jam 2014

[Soultaker]

Komend weekeinde gaat de Google Code Jam weer van start!

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 vorig jaar.

Wat kan ik winnen?

De hoofdprijs is $15.000 (50% meer dan vorig jaar)! 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 aanstaande zaterdag 12 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.

[StM]

Ook maar weer ingeschreven, al is de kans groot dat ik net als bij die van Facebook simpelweg de tijd niet heb om mee te spelen

[Ghehe]

Ook ingeschreven. Ik heb zaterdag wel wat andere dingen te doen maar misschien vind ik wel wat tijd in de avond (volgens de faq kan je er met 2 uurtjes werk komen).

[JeroenTheStig]

Vorige editie zijn er zelfs gasten geweest die hun opdrachten in LOLCODE of Piet hebben geschreven

Ik denk dat ik het maar bij Java houd

[Soultaker]

Ja, ik ga net als vorige jaren proberen minstens één probleem met Brainfuck op te lossen.

[Soultaker]

Bumpje: de kwalificatieronde is nu begonnen!

[Verwijderd]

Hmm, die mijnenveger-puzzel is lastiger dan ik in eerste instantie dacht.. Doesn't matter - still qualified, maar het zou toch leuk zijn om iets meer dan 25 punten te scoren.

[ Voor 59% gewijzigd door Verwijderd op 12-04-2014 13:15 ]

[Robbiedobbie]

Verwijderd schreef op zaterdag 12 april 2014 @ 12:49:
Hmm, die mijnenveger-puzzel is lastiger dan ik in eerste instantie dacht.. Doesn't matter - still qualified, maar het zou toch leuk zijn om iets meer dan 25 punten te scoren.

The same, ik ga zometeen maar mijn eerste minesweeper attempt doen

[Rikkiz0r]

Maakt het aantal punten in de kwalificatie ronde nog wat uit voor de daarop volgende rondes?

[Soultaker]

Nee, elke ronde staat op zichzelf qua score.

Er is dus geen reden om meer dan 25 punten in de kwalificatieronde te halen (behalve voor de eer ), maar bedenk wel dat je van de large inputs pas aan het einde van de ronde te horen krijgt of je antwoord klopt. Het is dus nuttig om meer oplossingen in te sturen voor het geval één van je inzendingen fout blijkt te zijn.

[koesie10]

Net de eerste ingeleverd. Mijn internet viel net uit toen ik nog 2 minuten had, maar gelukkig nog op tijd gefixt

[Verwijderd]

Toch nog opgelost - alleen Deceitful War nog.

Wat ik wel vreemd vond is dat mijn oplossingen voor 2 en 3 meteen ook snel genoeg waren voor Large, en ik niet echt een minder efficiente maar toch valide oplossing kan bedenken waarvoor dit niet zou gelden. In andere jaren was het nog wel eens het geval dat je met een naïve oplossing Small wel kon vinden, maar Large niet. Thoughts?

[Soultaker]

Ik kan bij zowel C als D wel degelijk oplossingen verzinnen die zeker werken voor de kleine invoer, maar die niet schalen naar de grote. Verder heeft alleen probleem C een significant hoger puntenaantal voor de grote invoer -- mogelijk is dat probleem lastiger dan je nu denkt.

[Verwijderd]

Soultaker schreef op zaterdag 12 april 2014 @ 14:58:
Ik kan bij zowel C als D wel degelijk oplossingen verzinnen die zeker werken voor de kleine invoer, maar die niet schalen naar de grote. Verder heeft alleen probleem C een significant hoger puntenaantal voor de grote invoer -- mogelijk is dat probleem lastiger dan je nu denkt.

Ik denk dat ik bij C juist een eenvoudigere (maar inefficiente) oplossing over het hoofd zie, want daar ging Large juist net zo vlot als Small. Dat is vooral wat ik probeerde op te merken

D ben ik sowieso nog niet uit Overigens levert een oplossing die 'Large' aan kan daar 16 punten op bovenop small, dus als alle oplossingen meteen Large aan zouden kunnen blijft 't vreemd om een onderscheid te maken. Maar goed, het ging mij vooral om B en C dus (die ik onterecht '2' en '3' noemde).

[ Voor 24% gewijzigd door Verwijderd op 12-04-2014 15:03 ]

[Soultaker]

Re: C denk ik dat je gelijk hebt (je hebt de brute force oplossing gemist) maar dat is op zich niet erg. Als je de intelligente oplossing direct goed hebt gedaan dan krijg je de kleine set inderdaad min of meer cadeau.

[Verwijderd]

Je hebt helemaal gelijk. Ik schreef de 'brute force'-aanpak eigenlijk meteen af als onhaalbaar, maar bij nader inzien is het voor 5 x 5 inderdaad wellicht wel vlot genoeg.

EDIT: Ik kon 't toch niet laten om vanavond nog eventjes D te proberen, en kijk eens wie we daar hebben..

[ Voor 51% gewijzigd door Verwijderd op 13-04-2014 00:32 ]

[Douweegbertje]

Ik heb nu 1 en 2 met PHP gedaan, misschien zo nog even naar 3 kijken

[Rikkiz0r]

Ik zit met die Cookie Clicker er een heletijd een klein beetje naast met de uitkomsten, maar net niet genoeg om binnen 10^-6 te komen. En ik heb eigenlijk geen idee hoe het komt

[Douweegbertje]

We recommend outputting y to 7 decimal places

Meer hoef je toch niet te lezen?

[Rikkiz0r]

Ja, dat snap ik ook. Wat is eigenlijk het beste datatype om voor die berekeningen te gebruiken, gebruik nu doubles maar suppose dat dat niet goed genoeg is? (Java).

Edit: even proberen met BigDecimal...

[ Voor 11% gewijzigd door Rikkiz0r op 13-04-2014 00:21 ]

[Douweegbertje]

Het doel is om zelf te leren. Je hebt voorbeelden van zowel input als output en je moet kunnen zien of je eigen code dan klopt (of niet). Ik ga daarom ook totaal niets voor je voorzeggen, vooral niet omdat je vraag vrij simpel is en heel goed zelf op te lossen. Ook al was je vraag moeilijk, dan mocht je het nog steeds zelf uitzoeken daar niet van (geen flame oid naar jou toe hoor, maar Code Jam is om zelf te leren, achteraf kan je alles vragen!).

[Verwijderd]

Rikkiz0r schreef op zondag 13 april 2014 @ 00:20:
[..] gebruik nu doubles maar suppose dat dat niet goed genoeg is? (Java).

Edit: even proberen met BigDecimal...

Wees je ervan bewust dat het niet alleen een kwestie is van de juiste datatypes kiezen, maar dat het ook uitmaakt hoeveel operaties je erop uitvoert. In principe kan je double met elke bewerking die je doet een beetje minder precies worden. Verder is afrondingsprecisie bij Google Code Jam in het algemeen niet een heel strenge eis, dus misschien gaat er toch algoritmisch iets niet helemaal volgens plan..

[ Voor 15% gewijzigd door Verwijderd op 13-04-2014 00:35 ]

[Rikkiz0r]

Ik denk dat ik de fout al weet, ik ga er in mijn systeem van uit dat er elke seconde 2 koekjes bij komen. Ipv dat koekjes continu worden toegevoegd...

Het is uiteindelijk toch gelukt, ik weet alleen niet helemaal precies waar aan het heeft gelegen.
Ik was het namelijk uiteindelijk zo zat dat ik het hele algoritme heb weg gedonderd en hem heb herschreven

Hopelijk ben ik nu door, aangezien ik de small goed had en hoogstwaarschijnlijk daarom de big data set ook.

Not bad voor een eerste poging dacht ik zo.

[ Voor 59% gewijzigd door Rikkiz0r op 13-04-2014 01:37 ]

[StM]

A, B & D goed, C gaat me te lang duren nu nog Op D heb ik wel even gezeten...

[Verwijderd]

Gefeliciteerd aan een ieder die door is Tot over 3 weken in Round 1B! (of over 2 weken, als je graag van 03:00 tot 05:30 meedoet )

EDIT: Voor statistieken, klik hier, en hier voor Nederlanders. Opvallend is dat Python het populairst was in NL, terwijl 't wereldwijd derde is na C++ en Java.

[ Voor 53% gewijzigd door Verwijderd op 13-04-2014 12:57 ]

[Elijan9]

Door! Pas om 23:00 begonnen en alles goed op de grote input van C (minsweepermaster) na (had geen tijd meer om geheugengebruik te verbeteren, tja... ). Een stuk leuker als de opdrachten niet zo cryptisch worden beschreven als bij de Facebook Hacker Cup, kun je je tenminste op de uitdaging zelf richten...

Vond alles best simpel, vooral D, de grote invoer was ook zo klaar (input arrays sorteren en twee keer lineair doorlopen). Alleen C was echt wat denkwerk.

.edit: Hulde voor SoulTaker, Brainfuck gebruiken om toch nog een uitdaging van A te maken en Zimbu Interessant, toch ook eens naar kijken

[ Voor 14% gewijzigd door Elijan9 op 13-04-2014 13:25 ]

[Soultaker]

Verwijderd schreef op zaterdag 12 april 2014 @ 15:21:
EDIT: Ik kon 't toch niet laten om vanavond nog eventjes D te proberen, en kijk eens wie we daar hebben..
[afbeelding]

Het is nu nog mooier:

Scheelt krap een minuut -- jammer van die foute inzendingen (Sowieso wel mooi om te zien hoeveel mensen er foutieve inzendingen hebben gedaan op C-small.)

Verwijderd schreef op zondag 13 april 2014 @ 10:18:
Opvallend is dat Python het populairst was in NL, terwijl 't wereldwijd derde is na C++ en Java.

Die regionale verschillen zijn altijd wel grappig. Java is vooral in Amerika populair; in China wordt vrijwel uitsluitend C++ gebruikt. Python is inderdaad populair in Nederland, en Ruby om vergelijkbare redenen in Japan (hoewel Ruby zelfs daar de strijd tegen Python lijkt te hebben verloren).

Elijan9 schreef op zondag 13 april 2014 @ 13:03:
Een stuk leuker als de opdrachten niet zo cryptisch worden beschreven als bij de Facebook Hacker Cup, kun je je tenminste op de uitdaging zelf richten...

Mee eens. Was een leuke set. Nog niet zo heel moeilijk, maar de komende ronden gaat het niveau vast nog wel omhoog

[ Voor 19% gewijzigd door Soultaker op 13-04-2014 15:54 ]

[Verwijderd]

Soultaker schreef op zondag 13 april 2014 @ 15:51:
Scheelt krap een minuut -- jammer van die foute inzendingen (Sowieso wel mooi om te zien hoeveel mensen er foutieve inzendingen hebben gedaan op C-small.)

De eerste was formatting flaw (in een bepaald speciaal geval een newline teveel), en de tweede keer kwam ik erachter dat ik bij 1 leeg vakje onterecht 'Impossible' claimde. Edge cases! Edge cases everywhere!

Soultaker schreef op zondag 13 april 2014 @ 15:51:
Die regionale verschillen zijn altijd wel grappig. Java is vooral in Amerika populair; in China wordt vrijwel uitsluitend C++ gebruikt. Python is inderdaad populair in Nederland, en Ruby om vergelijkbare redenen in Japan (hoewel Ruby zelfs daar de strijd tegen Python lijkt te hebben verloren).

Oh, ik had 't feit dat Guido van Rossum Nederlands is nog helemaal niet gekoppeld aan de populariteit van Python hier, maar nou je 't zegt.. Grappig dat dat ook op gaat voor Ruby in Japan!

Er zijn overigens wel erg veel deelnemers dit jaar. Dat wordt nog krap, als dat teruggebracht moet worden naar 3000.. Ik overweeg serieus om het zekere voor het onzekere te nemen en om over twee weken om 03:00 op te staan voor R1A

[ Voor 20% gewijzigd door Verwijderd op 13-04-2014 16:03 ]

[Soultaker]

Je kunt het proberen natuurlijk, maar persoonlijk heb ik het idee dat ik nooit zo goed presteer midden in de nacht. Uiteindelijk gaat het er alleen om dat je in één van de drie subronden bij de beste 1000 eindigt. Zelf heb ik het idee dat de kans daarop aanzienlijk groter is als ik een beetje uitgerust ben.

Het tijdstip van de eerste ronde is vooral gunstig voor Amerikanen en Oost-Aziaten. Het voordeel van meedoen in de eerste ronde zou dan vooral zijn dat je relatief weinig concurrentie hebt van Oost-Europa en Rusland, waar heel veel goede deelnemers zitten.

Traditioneel is de laatste ronde juist de makkelijkste, omdat de meeste deelnemers wel de gelegenheid hebben om in (minstens) één van de twee voorgaande ronden mee te doen, en de beste deelnemers zich dus al geplaatst hebben en niet meer meedoen. De laatste ronde heeft daardoor de zwakste deelnemers, en aangezien het tijdstip relatief gunstig is voor Nederland (zondagochtend om 11 uur) zou ik denken dat je daar de grootste kans hebt om je te plaatsen.

[Elijan9]

@SoulTaker: ik ben toch wel héél nieuwsgierig naar die .cjam extensie voor opdracht D. Ik ken .jam en .bjam, maar dat zijn build files, maar "cjam"?

[Ghehe]

Elijan9 schreef op zondag 13 april 2014 @ 18:11:
@SoulTaker: ik ben toch wel héél nieuwsgierig naar die .cjam extensie voor opdracht D. Ik ken .jam en .bjam, maar dat zijn build files, maar "cjam"?

cjam = (google) code jam ? (going on a leap here )
Welke taal het echt is, weet ik niet. Ik heb het eens met Perl proberen runnen maar die verstond er ook weinig van.

* Ghehe is trouwens ook naar de volgende ronde.

[Soultaker]

Elijan9 schreef op zondag 13 april 2014 @ 18:11:
@SoulTaker: ik ben toch wel héél nieuwsgierig naar die .cjam extensie voor opdracht D. Ik ken .jam en .bjam, maar dat zijn build files, maar "cjam"?

Het is CJam (cherry jam), een Golfscript-achtige taal die ontwikkeld is om er zo klein mogelijke programma's (in aantal bytes) in te kunnen schrijven.

[Rikkiz0r]

Ik zat net even jouw solutions door te kijken Soultaker, maar hoe krijg je het in godsnaam voor elkaar om bijvoorbeeld probleem A op te lossen met Brainfuck? Ik vond hem eerlijk gezegd al vrij pittig met java .

[Soultaker]

Java is dan ook een veel ingewikkeldere programmeertaal dan Brainfuck.

[Devilly]

Soultaker schreef op zondag 13 april 2014 @ 22:53:
Java is dan ook een veel ingewikkeldere programmeertaal dan Brainfuck.

Explain yourself.

[Soultaker]

In Java heb je allemaal objecten, klassen, threads, monitors, interfaces, namespaces, access control, de call stack, de heap, lokale variabelen, object- en klasse-attributen, unaire, binaire en ternaire operators, methoden, method calls, recursie, constructors, finalizers, en allerlei primitieve (char, boolean, float, etc.) en niet-primitieve (String, Array, etc.) dataypen, static type checking met generics, en allerlei andere features die ik nog vergeten ben, want de Java specificatie is 780 pagina's lang.

In Brainfuck heb je 8 statements, één datatype (byte) en één soort geheugen (tape), geen functies of expressies, geen standaard (of niet-standaard) libraries om uit je hoofd te leren. De taal kun je specificeren op een half A4tje en een interpreter vereist niet meer dan acht regels code. Simpel.

[Devilly]

Dat is zo, maar een willekeurig probleem oplossen in Brainfuck zul je denk ik sneller iemand in Java zien doen dan in Brainfuck. Dat doet overigens niets af aan het feit dat ik het helemaal met je eens ben.

[DaCoTa]

En, niemand heeft vannacht meegedaan? Ik in ieder geval niet, kreeg het niet voor elkaar om op te staan...

[Ghehe]

Nope, niet meegedaan. Ben nu wel de opgaves aan het bekijken / maken.

[Soultaker]

Even een bumpje ter kennisgeving: ronde 1B begint over 24 uur, op zaterdag om 18:00.

Als je je wil voorbereiden is het nuttig om (in ieder geval) de eerste twee opgaven van ronde 1A te proberen.

[Verwijderd]

Vlak na inleveren van A-large constateerde ik dat ik een foutje heb gemaakt, en heb uiteindelijk alleen voor A-small en B-small punten gepakt. Enfin, ook met A-large erbij was het onvoldoende geweest.

Tot volgende week maar weer!

Hoe ging 't bij jullie?

[ Voor 5% gewijzigd door Verwijderd op 03-05-2014 21:01 ]

[DaCoTa]

Te weinig tijd. A wel, die was op zich vrij eenvoudig. Bij B liep ik vast omdat ik geen oplossing kon bedenken die met grote getallen zou werken. Bij C had ik nog 1 probleem bij de tree traversal voordat de tijd op was. Dus idd, tot volgende week! :-)

[Elijan9]

Heb het (voorlopig) gehaald, nipt bij de eerste 1000. B was uiteindelijk erg gemakkelijk in C++ (gewoon brute-force gedaan van [K .. A - 1] in combinatie met [K .. B - 1]). Voor A wilde ik iets te slim doen, daardoor wel de small maar niet de large gehaald. Stom want de optimalisatie die ik in gedachten had werkte niet en was ook echt niet nodig qua tijd.
Met 10 minuten meer tijd had ik C ook kunnen insturen...

Ik moet zeggen dat ik deze ronde wel beduidend makkelijker vond dan ronde 1a, want die had ik zeker niet gehaald als ik mee had gedaan...

[Verwijderd]

Elijan9 schreef op zondag 04 mei 2014 @ 01:07:
B was uiteindelijk erg gemakkelijk in C++ (gewoon brute-force gedaan van [K .. A - 1] in combinatie met [K .. B - 1]).

Is dat niet nog steeds orde van grootte 10^18? Je kan het hooguit reduceren door altijd de 'kleine kant' van K te bekijken, maar dan blijft 't nog altijd 10^16 lijkt me? Of begrijp ik je verkeerd?

[Elijan9]

Verwijderd schreef op zondag 04 mei 2014 @ 10:49:
[...]


Is dat niet nog steeds orde van grootte 10^18? Je kan het hooguit reduceren door altijd de 'kleine kant' van K te bekijken, maar dan blijft 't nog altijd 10^16 lijkt me? Of begrijp ik je verkeerd?

Ik had ook verwacht dat het een probleem zou zijn, daarom probeer ik mijn eigen testcases te schrijven. Met K = 1 en A = 1.000.000.000 en B = 1.000.000.000 was de code alsnog snel klaar... Anders had ik het wel verder uit moeten/kunnen werken... Oeps, er zat een fout in mijn eigen tescases

Voor de rest, als A < K of B < K gold dat alle mogelijkheden (A*B) kleiner dan K waren (met een AND wordt het getal nooit groter). Zo niet dan zijn er (A + B - K) *K mogelijkheden die sowieso een winnend nummer opleveren. Dan hoeft alleen de combinaties van a = K .. A-1 met b = K ... B - 1 te worden gecheckt.

[ Voor 18% gewijzigd door Elijan9 op 05-05-2014 11:48 . Reden: Oeps ]

[Soultaker]

Ik zie dat die aanpak inderdaad werkt op de officiële testinvoer, waar gewoon geen cases in zitten waarbij K veel kleiner is dan A en B. Dat is stom.

Yoast92 heeft in principe gewoon gelijk: die aanpak is van orde 10¹⁸ en dat zou veel te traag moeten zijn. (Probeer het maar eens op deze random test data.)

[Elijan9]

Soultaker schreef op zondag 04 mei 2014 @ 18:59:
Ik zie dat die aanpak inderdaad werkt op de officiële testinvoer, waar gewoon geen cases in zitten waarbij K veel kleiner is dan A en B. Dat is stom.

Yoast92 heeft in principe gewoon gelijk: die aanpak is van orde 10¹⁸ en dat zou veel te traag moeten zijn. (Probeer het maar eens op deze random test data.)

Inderdaad, er zat een fout in mijn test input Een getal te veel, waardoor alle data daaropvolgend verschoven was, ik kon al niet begrijpen wat voor een slimme optimalisatie gcc had bedacht... Wat een mazzel...

Anders had ik op basis van de bits van A en K de hoeveelheid mogelijk B's moeten uitrekenen die prima waren op basis van "foute" bits, ook te doen, daar was ik in mijn hoofd al mee bezig toen de code desondanks goed genoeg leek te presteren, maar Oeps Zo'n foute test had me de large test kunnen kosten...

[DaCoTa]

Hmm, het blijkt dat ik A large fout heb. Nu vraag ik me af wat ik verkeerd heb gedaan. Bij het bepalen van de minimale zetten per segment (setje letters) ga ik ervanuit dat de gemiddelde lengte degene is die de minste zetten zou moeten hebben, maar vraag me nu af of dat correct is.

Wel een tegenvaller hoor, maar 10 punten :-/

[Verwijderd]

DaCoTa schreef op zondag 04 mei 2014 @ 22:58:
Bij het bepalen van de minimale zetten per segment (setje letters) ga ik ervanuit dat de gemiddelde lengte degene is die de minste zetten zou moeten hebben, maar vraag me nu af of dat correct is.

Dat is ook de fout die ik maakte; terwijl de 8 minuten aftelde kwam ik erachter, maar was niet op tijd met een vervangende aanpak

Achteraf: je moet de mediaan nemen, niet het gemiddelde. Het argument (dat ik oppikte in #GCJ):
- Neem de buitenste 2 lengtes (dwz kleinste en grootste), a en b
- Je waarde zit sowieso ergens tussen a en b, en maakt voor de totale afstand tot a en b niet uit
- Herhaal met de volgende lengtes (dus net eentje groter dan a en eentje kleiner dan b), tot je het midden bereikt
- Besef dat je de mediaan moet hebben

[ Voor 5% gewijzigd door Verwijderd op 04-05-2014 23:16 ]

[Soultaker]

Mediaan inderdaad, maar je kon ook gewoon alle lengtes uitproberen, en dan berekenen hoeveel het kost om de andere segmenten op die lengte te brengen. Da's O(N²) in plaats van O(N log N), maar met N ≤ 100 is dat natuurlijk geen bezwaar.

[DaCoTa]

Ja, lesje geleerd, beter geen premature optimization. En gezien de tijdsdruk is het handiger om zo snel mogelijk naar een oplossing toe te werken, zonder slimmigheden.

[Verwijderd]

FYI: het is vanaf nu nog ongeveer 16 uur tot ronde 1C, de laatste kans om te kwalificeren voor ronde 2. Ronde 1C begint dus om 11 uur morgenochtend! Alvast succes, iedereen.