Google Code Jam 2012

[Soultaker]

De Google Code Jam 2012 gaat over een paar uur beginnen met een kwalificatieronde die loopt vanaf 1 uur vanacht tot 2 uur 's nachts op zaterdag. Voor wie de Code Jam niet kent: het is een algoritmische programmeerwedstrijd die inhoudelijk een beetje vergelijkbaar is met de Facebook Hacker Cup eerder dit jaar (topic).

Er is een hoofdprijs van $10,000 voor de winnaar, een reisje naar New York City voor de top 25 scorers, en een Code Jam T-shirt voor de top 1000 scorers, maar de voornaamste reden om mee te doen is natuurlijk dat het leuk is om vraagstukken met een programma op te lossen. Ik ga natuurlijk ook een poging wagen. Zijn er nog meer Tweakers die meedoen?

(Je kunt tot het einde van de kwalificatieronde registreren, dus ook bijvoorbeeld morgenmiddag nog. Om je te kwalificeren voor de eerste ronde moet je minstens één probleem correct oplossen.)

[Jegorex]

een kwalificatieronde die loopt vanaf 1 uur vanacht tot 2 uur 's nachts op zaterdag.

Nu lijkt het dat de kwalificatieronde maar 1 uur duurt terwijl het 25 uur is.

Ik heb me ook aangemeld, maar meestal strand ik in de 2e ronde.

[ Voor 16% gewijzigd door Jegorex op 13-04-2012 22:07 ]

[SaphuA]

.

[ Voor 143% gewijzigd door SaphuA op 31-01-2022 15:28 ]

[Verwijderd]

Voor Vlaamse scholieren is er volgende week woensdag een soortgelijk evenement: http://www.vlaamseprogrammeerwedstrijd.be/current/

[Tharulerz]

Heb net A en B opgelost (small), heb dus al 25 punten en ben sowieso door naar de volgende ronde. Ik kan alleen niet direct vinden of je punten gereset worden na elke ronde?

Overigens klopt het dus niet wat Soultaker zegt, je moet minstens _twee_ problemen oplossen om door te zijn, aangezien 1 probleem 15 punten is en in mijn mail dit stond:

The Qualification Round lasts 25 hours, and you will need to score at least 20 points to advance.

@Rubinski Ik ga daar ook naartoe, is ook voor niet-scholieren trouwens. Cu there?

[Verwijderd]

Oh, dat wist ik niet. Ik heb me ingeschreven maar weet nog niet in welke toestand ik naar daar zal gaan. Volgende week beginnen de verkiezingen van mijn studentenvereniging dus dat wil zeggen:



Daarnaast heb ik nogal moeite gehad bij het zoeken van een kwalitatief team. Ik zit in het 2e jaar maar heb in mijn team een klasgenoot die nooit naar de les gaat en een andere jongen die nog maar in het eerste jaar zit en dus enkel over basiskennis beschikt. Nuja, ... deelnemen is belangrijker dan winnen

Je kan dus ook gewoon meedoen als non-student? Zijn daar bepaalde voorwaarden aan verbonden?

[Tharulerz]

Er komen 173 teams van 3 personen en dit in één van de volgende categoriën:
Categorie I: 32 teams, leerlingen van het secundair onderwijs,
Categorie II: 118 teams, bachelorstudenten (zowel professionele als academische bachelors) en
Categorie III: 23 teams, masters, doctoraatstudenten, afgestudeerden en professionals.

Staat letterlijk op de site... Je komt dan gewoon in een andere categorie terecht (Ik zit echter in categorie 2)

[Verwijderd]

Ik wist dat er verschillende categoriëen waren maar van die 3e categorie wist ik niet dat er ook afgestudeerden en professionals bijzaten. (ik vergeet zoiets nogal vlug).

offtopic:
Mag ik je vragen waar en wat je precies studeert?

[Tharulerz]

Ik heb A B en C opgelost (zowel small als large voor B en C) en sta nu op 60 punten, morgen even kijken naar de laatste.

Weet er iemand of je punten bewaard blijven over rondes heen? Ik vind het echt nergens...

[Robbiedobbie]

Fantastisch, dacht ik ook eventjes mee te kunnen doen, lig ik er al bij A uit. Niet doordat ik het niet kan oplossen, maar doordat de inputfile niet wil downloaden Daardoor de 4 minuten al voorbij...
Balen zeg...

[SumBeam]

Ik heb inmiddels A en de small/large van C gedaan, ik sta nu op 40 punten. Nu B nog even goed doorlezen, misschien nog een poging aan D doen, maar dat is alweer een paar jaar geleden dat ik dat heb gehad.

Ik vind deze opdrachten trouwens wel leuker als die van FBHC, ook wel een stukje pittiger

[MrHaas]

Ik doe ook mee, A, B en C opgelost, straks nog even kijken hoe ver ik met D kom. Die ziet er lastig uit...

[Soultaker]

Zo, nu zelf ook maar eens beginnen.

Tharulerz schreef op zaterdag 14 april 2012 @ 02:47:
Overigens klopt het dus niet wat Soultaker zegt, je moet minstens _twee_ problemen oplossen om door te zijn, aangezien 1 probleem 15 punten is.

Klopt, ik ging uit van de puntenverdeling van vorig jaar, waarin je één probleem geheel moest oplossen.

Weet er iemand of je punten bewaard blijven over rondes heen? Ik vind het echt nergens...

Die worden niet bewaard.

Robbiedobbie schreef op zaterdag 14 april 2012 @ 10:30:
Fantastisch, dacht ik ook eventjes mee te kunnen doen, lig ik er al bij A uit. Niet doordat ik het niet kan oplossen, maar doordat de inputfile niet wil downloaden

Je kunt die opnieuw downloaden, toch? Normaal gesproken kost dat je straftijd maar dat maakt voor de kwalificatieronde niet uit. (Let op: voor de large sets heb je wél maar één poging.)

[ Voor 3% gewijzigd door Soultaker op 14-04-2012 13:46 ]

[Robbiedobbie]

Ja daar ben ik net ook achter gekomen Het is de eerste keer dat ik aan zoiets meedoe, waardoor ik nog niet wist dat dit mogelijk was. Via internet explorer werkte hij deze keer wel. Chrome doet het blijkbaar niet goed. A opgelost, B bijna.

[ Voor 25% gewijzigd door Robbiedobbie op 14-04-2012 13:56 ]

[Justhim]

Soultaker schreef op zaterdag 14 april 2012 @ 13:45:
(Let op: voor de large sets heb je wél maar één poging.)

Klopt, dit heb ik zojuist gemerkt, helaas.
Mijn oplossing voor Probleem-C was goed genoeg voor de Small input, maar de berekening voor de Large input duurde helaas te lang en mn 8 minuten zijn verstreken

Nu nog Problem-D, maar ben bang dat dit net wat te zwaar is voor me

[Tharulerz]

Justhim een tip voor de volgende ronde: je kan vaak zelf een large set zelf maken, en die eerst testen voor je de officiele download. In het geval van probleem C is dit dus gewoon 50 lijnen met telkens "1 2000000"

[Justhim]

Tharulerz schreef op zaterdag 14 april 2012 @ 21:02:
Justhim een top voor de volgende ronde: je kan vaak zelf een large set zelf maken, en die eerst testen voor je de officiele download. In het geval van probleem C is dit dus gewoon 50 lijnen met telkens "1 2000000"

Inderdaad, goeie tip!
Was er eerlijk gezegd ook helemaal niet vanuit gegaan dat de berekening wel eens veel te lang kon gaan duren.

Ik denk dat ik er later nog eens voor ga zitten, want zelfs via een multi-core (dual) berekening was ik er niet op tijd bij geweest.
'slechte' code dus

[Soultaker]

Tharulerz schreef op zaterdag 14 april 2012 @ 21:02:
In het geval van probleem C is dit dus gewoon 50 lijnen met telkens "1 2000000"

Da's niet eens geldige invoer voor probleem C.

[Jegorex]

Tharulerz schreef op zaterdag 14 april 2012 @ 21:02:
Justhim een tip voor de volgende ronde: je kan vaak zelf een large set zelf maken, en die eerst testen voor je de officiele download. In het geval van probleem C is dit dus gewoon 50 lijnen met telkens "1 2000000"

Ik had het getest met 50x "1000000 2000000" en dat lukte in 35 seconden.
De uiteindelijke large set duurde ongeveer 10 seconden om te berekenen.

[Soultaker]

De uitvoer van probleem A is wel vermakelijk.

[Verwijderd]

Die had ik met powershell opgelost. Probleem B ook, trouwens.

Probleem C, Recycled Numbers, is ook niet moeilijk. Ik had hem met powershell gemaakt, maar dat was te traag. (> 5 minuten voor de maximale input). In C++ een halve seconde. Dat is het betere werk.

Probleem D is mij nog niet gelukt. Ik heb in mijn kop hoe je hem moet doen. Maar dat lukt mij simpelweg niet binnen de tijd. Voor de volgende ronde: niet uitslapen tot halverwege de middag en vervolgens eerst het huiswerk gaan maken

[sub0kelvin]

.... 5, 4, 3, 2, 1 en de kwalificaties zijn voorbij.... pennen neer allemaal!

Ik heb dit jaar ook maar eens meegedaan. Kwam er halverwege de middag achter, en heb zojuist mijn laatste materiaal ingestuurd.
Ik heb A, B en C gedaan, waarbij alle small goed waren en alle large zonder gedoe zijn ingestuurd.

Bij C uiteindelijk toch voor de langzame manier gegaan, want ik had een bug in de snellere methode die ik er maar niet uit kreeg. Langzaam was nog steeds binnen de 3 minuten voor het worst-case scenario.

edit:
C-large had ik toch een fout in helaas. B-large was wel goed. In totaal 45 punten.

Voor Ronde 1 kan ik waarschijnlijk helaas niet meedoen met subronde A, dan ben ik op vakantie. Ik moet het dus hebben van B en/of C.

[ Voor 18% gewijzigd door sub0kelvin op 15-04-2012 02:03 ]

[Soultaker]

Ik heb zoals gebruikelijk weer een aantal esoterische/archaïsche programmeertalen gebruikt (behalve voor probleem C++, daar had ik geen zin meer in tegen twaalf uur 's nachts). Mijn oplossingen:

	A. Speaking in Tongues	B. Dancing With the Googlers	C. Recycled Numbers	D. Hall of Mirrors
Small	sed	Befunge	COBOL	C++
Large		Brainfuck	Pascal

[Verwijderd]

Je hebt C slimmer opgelost dan mij. Ik roteer elk getal N keer. Waar N is het aantal digits. Maar in zeldzame gevallen gaat dat fout. Zoals met 1212:

Draaien, wordt. 2121, tel een op bij counter
Draaien, wordt. 1212
Draaien, wordt. 2121, tel een op bij counter.

Om dat op te lossen hou ik alle pairs bij in een map. Maar simpelweg roteren totdat je bij hetzelfde getal uitkomt is veel slimmer. Misschien is hij dan ook in powershell mogelijk.

[Tharulerz]

Soultaker schreef op zondag 15 april 2012 @ 00:22:
[...]

Da's niet eens geldige invoer voor probleem C.

Hoezo niet?
Bedoel je dat het aantal cases ontbreekt? Want verder zie ik niet wat je bedoelt...

[Soultaker]

A en B moeten een gelijk aantal cijfers hebben..

[azerty]

Soultaker schreef op zondag 15 april 2012 @ 02:17:
Ik heb zoals gebruikelijk weer een aantal esoterische/archaïsche programmeertalen gebruikt (behalve voor probleem C++, daar had ik geen zin meer in tegen twaalf uur 's nachts). Mijn oplossingen:

	A. Speaking in Tongues	B. Dancing With the Googlers	C. Recycled Numbers	D. Hall of Mirrors
Small	sed	Befunge	COBOL	C++
Large		Brainfuck	Pascal

Petje af!

Had ik niet zoveel werk gehad voor school had ik waarschijnlijk ook wel een poging gewaagd, maar goed...

[MrHaas]

Soultaker schreef op zondag 15 april 2012 @ 02:17:
Ik heb zoals gebruikelijk weer een aantal esoterische/archaïsche programmeertalen gebruikt (behalve voor probleem C++, daar had ik geen zin meer in tegen twaalf uur 's nachts). Mijn oplossingen:

	A. Speaking in Tongues	B. Dancing With the Googlers	C. Recycled Numbers	D. Hall of Mirrors
Small	sed	Befunge	COBOL	C++
Large		Brainfuck	Pascal

Nice, ziet er goed uit. Ik was wel op de goede weg met D zie ik en als ik er wat meer tijd in had gestoken was de Small me nog wel gelukt misschien. Nu moest ik het doen met 60 punten, alweer zin in de volgende ronde.

[Soultaker]

Mja, voor Hall of Mirrors zijn er eigenlijk twee mogelijke manieren om het probleem aan te pakken. Als je er van uitgaat dat de kamer een lege rechthoek is dan kun je de positie van het mannetje simpelweg horizontaal en verticaal spiegelen en dan kijken welke spiegelbeelden binnen de maximumafstand vallen als je er een rechte lijn naar toe trekt. Die aanpak werkt alleen bij de kleine invoer (die alleen van de "grote" verschilt in dat de kamer leeg is).

Voor de grote heb je een ray tracing aanpak nodig, maar als je die direct al gebruikt had, dan is 'ie niet veel moelijker dan de kleine. Je moet dan wel die (letterlijke) corner cases met licht dat gereflecteerd/geabsorbeerd wordt als een straal op een hoekje terecht komt goed afhandelen. Het is zo'n oplossing die niet moeilijk te verzinnen is, maar nog best lastig om correct te implementeren is.

[ Voor 6% gewijzigd door Soultaker op 16-04-2012 23:18 ]

[Tharulerz]

Interessante link: http://www.go-hero.net/jam/12/multilang
Ook: http://www.reddit.com/r/p...ats_and_solutions/c4cr0wz


Straks VPW, proberen om voor Rubinski te eindigen!

[ Voor 33% gewijzigd door Tharulerz op 18-04-2012 05:57 ]

[SumBeam]

De volgende ronde begint wel om 3 uur 's nachts op 28 april. Tot half 6, duurt dus 2.5 uur. Dat is dan dus weer iets minder fijn

[Tharulerz]

SumBeam schreef op woensdag 18 april 2012 @ 10:08:
De volgende ronde begint wel om 3 uur 's nachts op 28 april. Tot half 6, duurt dus 2.5 uur. Dat is dan dus weer iets minder fijn

Voor de volgende rondes kan je aan 1 van de 3 meedoen, ze zijn telkens in verschillende tijdzones. Even de regels goed lezen!

[Soultaker]

Tharulerz schreef op woensdag 18 april 2012 @ 05:55:
Interessante link: http://www.go-hero.net/jam/12/multilang
Ook: http://www.reddit.com/r/p...ats_and_solutions/c4cr0wz

Die oplossing van Nabb is helemaal cool. Het is een polyglot; één programma dat gecompileerd/uitgevoerd kan worden in meerdere talen en dan wat anders doet. Het is een oplossing voor A-small in vim, B-small in dc, B-large in Brainfuck, C-small in shell script, C-large in bc, D-small in Whitespace and D-large in PHP (of omgekeerd?) en los daarvan is het een quine in C, C++, Ruby én PHP. Ik kreeg het niet 100% werkend (onder andere de whitespace code niet) maar het principe is erg gaaf.

[sub0kelvin]

Shit, ik zie net dat ik geen van de eerste rondes kan maken omdat ik op vakantie ben Dacht eerst dat rondes B en C later waren, maar blijkbaar heb ik verkeerd gekeken.

[Jegorex]

De eerste rondes zijn verdeelt over 2 weekenden, komend weekend is er 1 ronde en volgend weekend 2.
http://code.google.com/codejam/schedule.html
Dit weekend kan ik in elk geval niet meedoen, 5/6 mei heb ik denk ik wel tijd.

[Soultaker]

Ronde 1A begint om drie uur 's nachts (tot half zes 's ochtends). Lijkt me niet echt een aantrekkelijk tijdstip.

Ronde 1B is volgende week om 6 uur 's avonds op zaterdag, en 1C om 11 uur 's ochtends op zondag. Dat lijken me meer geschikte tijden voor Europese deelnemers.

Maar als je je ogen open kunt houden belet niets je om mee te doen komende zaterdag; misschien is er wat minder concurrentie en het is sowieso een extra kans om je te plaatsen voor de tweede ronde. (Maar ik denk dat ik tot ronde 2B wacht.)

[ Voor 30% gewijzigd door Soultaker op 25-04-2012 21:23 ]

[Devilly]

Soultaker schreef op woensdag 25 april 2012 @ 21:22:
(Maar ik denk dat ik tot ronde 21B wacht.)

Zoiets?

[Soultaker]

Oh ja, 1B inderdaad. Verwarrend dat de kwalificatieronde niet meetelde, hoewel het misschien wel weer logisch is om die als ronde 0 te zien.

[Tharulerz]

Nachtmens als ik ben doe ik uiteraard mee met 1A

[Soultaker]

Hm, ronde begint over een uur, en ik ben nog wakker. Ik ga toch maar een poging wagen, denk ik. Kan ik Tharulerz proberen te verslaan.

[Tharulerz]

Soultaker schreef op zaterdag 28 april 2012 @ 02:02:
Hm, ronde begint over een uur, en ik ben nog wakker. Ik ga toch maar een poging wagen, denk ik. Kan ik Tharulerz proberen te verslaan.

Dat is je dan niet gelukt!

Was met teveel andere zaken op zelfde moment bezig (oh ironie om 4 uur snachts) en dus de B niet afgekregen (2 keer ingediend met kleine foutjes die ik er niet uitkreeg), ook al leek het algoritme achter B redelijk simpel...

Ach, volgende keer beter!

[Soultaker]

Mja, ik probeerde C eerst op te lossen maar 'k kreeg de boel niet werkend. Probleem B is wel leuk; klinkt simpel maar is tricky. Volgende keer beter, inderdaad.

[ Voor 20% gewijzigd door Soultaker op 28-04-2012 07:18 ]

[SumBeam]

Ik was aan B begonnen, sample ging perfect maar de small input niet. En ik had ook geen idee waar ik het moest zoeken.

Heb het toen maar opgegeven, teveel tijd aan B besteed en ben gaan slapen om 5 uur. We hebben toch nog twee kansen

[Tharulerz]

Wie doet er straks nog allemaal mee?

Ik hoop er deze keer wel door te geraken

Cu on the battlefield Soultaker

[Soultaker]

Ik zal er zijn, inderdaad. En morgenochtend weer als het moet.

[MrHaas]

Ik ben er ook bij! Good luck alvast.

[Soultaker]

Veel succes allemaal!

[Tharulerz]

Zucht... A al een tijdje af, ik dien hem in, krijg ik invalid... Vrij moeilijk om je fout te zoeken als alles werkt op voorbeeld input

[MrHaas]

Ja, het voorbeeld heeft alleen sets zonder uitzondering. Ben er ook te lang mee bezig geweest. Inmiddels A helemaal en C-small gedaan. Nu eerst B doen.

[Soultaker]

B was een hoop werk.

Ik heb alleen C large nog open, maar die is lastig!

[Tharulerz]

Heb men fout in A gevonden, maar helaas niet genoeg tijd over om nog genoeg punten te halen (C small alleen oplossen is niet genoeg, B small duurt te lang). Poging 3 it is!

[MrHaas]

Arg, arg, arg, net te laat klaar met B, had te laat door dat je al mocht gaan varen voor water begon te dalen. Net niet genoeg tijd om dat er nog in te krijgen...

/edit: hmm, en blijkbaar A-large fout... vermoed dat ik verkeerde bestand heb gesubmit

[ Voor 22% gewijzigd door MrHaas op 05-05-2012 20:44 ]

[Soultaker]

Nou, ik mag uitslapen morgenochtend. Ik heb inmiddels ook C uitgevogeld -- veel te laat natuurlijk.

Ik hoop dat jullie 't morgen nog een keer proberen, en zo ja, veel succes gewenst!

[Jegorex]

Ik heb alleen C small kunnen inleveren. A heb ik meerdere keren geprobeerd, maar ik kon de fout niet vinden.

[Tharulerz]

Jegorex schreef op zaterdag 05 mei 2012 @ 21:40:
Ik heb alleen C small kunnen inleveren. A heb ik meerdere keren geprobeerd, maar ik kon de fout niet vinden.

Mijn fout was: als je iemand hebt met een resultaat die zeker doorgaat, moet je bij de andere deelnemers die persoon niet in rekening brengen (wel het totaal natuurlijk).

[Verwijderd]

Morgen maar eens meedoen. Lijkt me leuk.

[azerty]

Verwijderd schreef op zaterdag 05 mei 2012 @ 23:20:
Morgen maar eens meedoen. Lijkt me leuk.

Vergis ik me nu of kon je alleen meedoen als je door de voorrronde was?

[Verwijderd]

wsitedesign schreef op zaterdag 05 mei 2012 @ 23:37:
[...]


Vergis ik me nu of kon je alleen meedoen als je door de voorrronde was?

Ik had dus niet goed gelezen: http://code.google.com/codejam/faq.html#rounds

[MrHaas]

A en C-small opgelost, maar krijg niet zo'n grip op B. C-large heb ik wel een idee hoe ik het wil doen, maar denk dat half uur te kort is om het nog werkend te krijgen. Anders maar hopen dat m'n 40 puntjes genoeg zijn

[Soultaker]

Het lijkt er wel op dat 40 punten genoeg is.

Ik heb de problemen ook opgelost. Tenminste, dat denk ik; ik zal ze zometeen eens met de officiële testdata moeten uitproberen.

[MrHaas]

Jep, 544e uiteindelijk.

[Soultaker]

Hm, mijn logica voor A klopt niet helemaal. Maar m'n oplossingen voor B en C waren wel goed, wat goed geweest zou zijn voor 72 punten en een 100e plek. (Maar in werkelijkheid zou ik waarschijnlijk A zijn gaan debuggen, natuurlijk.)