Facebook Hacker Cup 2015

[Ghehe]

Facebook Hacker Cup 2015

Wat is de Facebook Hacker Cup?

De Facebook Hacker Cup is een jaarlijkse programmeerwedstrijd waarin hackers (efficiënte) oplossingen proberen te bedenken voor bepaalde problemen.

De Facebook Hacker Cup bestaat sinds 2011 en is Facebooks officiële programmeerwedstrijd.

Wanneer is de Facebook Hacker Cup 2015?

Ronde	Start	Duur	Eind
Online Qualification Round	vrijdag 9 januari 01:00	72 uur	maandag 12 januari 01:00
Online Elimination Round 1	zaterdag 17 januari 19:00	24 uur	zondag 18 januari 19:00
Online Elimination Round 2	zaterdag 24 januari 19:00	3 uur	zaterdag 24 januari 22:00
Online Elimination Round 3	zaterdag 31 januari 19:00	3 uur	zaterdag 31 januari 22:00
Onsite Finals at Facebook	5 en 6 maart 2015

(Uren zijn in GMT+1)

Hoe kan ik meedoen

Simpel, als je al een facebook account hebt, kan je met dat account je inschrijven voor de Hacker Cup. Inschrijven doe je op https://www.facebook.com/hackercup/register.

Vragen

Het concept is simpel, je krijgt een probleem en daar moet jij een oplossing voor vinden. Je krijgt bij je probleem al een hele simpel voorbeeld van input en output. Als jij denkt dat je oplossing het probleem kan oplossen dan download je wedstrijd-inputdata en haal je die door je programma. De ouput upload je naar Facebook welke je oplossing zal nakijken en als juist of fout zal beoordelen. Na het downloaden van de input heb je 6 minuten om de output de uploaden, je moet dus zeker weten dat je programma correct en snel genoeg werkt voor je de input downloadt.

Oude opgaven

Year	Round	Problems	Solutions
2015	Final
	3
	2	Lazy sort, All Critical, Autocomplete strikes back, Fox socks
	1	Homework, Autocomplete, Winning at sports, Corporate gifting	Solutions
	Qual	Cooking the Books, New Year's Resolution, Laser Maze	Solutions
2014	Final	Intervals of Love, Lunch at Facebook, Fortunate Wheels, Tours
	3	Secret Santa, Pizza Baking, Restaurant Chains
	2	Magic Pairs, Hold'em Numbers, Ski Resort Planning	Solutions
	1	Labelmaker, Coins Game, AAAAAA, Preventing Alzheimer	Solutions
	Qual	Square Detector, Basketball Game, Tennison
2013	Final	Archiver, Colored Trees, Minesweeping, Teleports
	3	Digits War, Name the Baby, Greedy Entertainers
	2	Cake Cutting, RoboElection, Permutations
	1	Card Game, Security, Dead Pixels	Solutions
	Qual	Beautiful strings, Balanced Smileys, Find the Min	Soultaker's notes
2012	3	Divisor Function Optimization, Trapezoids, Unfriending
	2	Monopoly, Road Removal, Sequence Slicing
	1	Checkpoint, Recover the Sequence, Squished Status
	Qual	Alphabet Soup, Auction, Billboards	Solutions
2011	Final	Alien Game, Party Time, Safest Place
	2	Bonus Assignments, Scott's New Trick, Studious Student II
	1B	Chess 2, Diminishing Circle, Slot Machine Hacker
	1A-2	Diversity Number, Turn on the Lights, Wine Tasting
	1A	After the Dance Battle, First or Last, Power Overwhelming
	Qual	Double Squares, Peg Game, Studious Student

Andere competities

NWERC 2012 (Vragen/Oplossingen)
BAPC 2012 (Vragen/Oplossingen/Testdata) (Zip-bestand)
Vlaamse Programmeerwedstrijd '09, '10, '11, '12 (Vragen/Oplossingen/Testdata)
Project Euler
USACO Training Program
TopCoder
CodeForces
UVa Online Judge
SPOJ
Google Code Jam
Python Challenge

Zie ook de reacties van Soultaker, kokx en MrHaas in het topic van 2013.

Hackers Wall of Fame

Soultaker - Finale 2011 (laatste 25)

Voorgaande topics

In de voorgaande topics kan je vragen, oplossingen en discussies terugvinden.
Facebook Hacker Cup 2011
Facebook Hacker Cup 2012
Facebook Hacker Cup 2013
Facebook Hacker Cup 2014

[ Voor 244% gewijzigd door Ghehe op 25-01-2015 18:26 ]

[HuHu]

Leuk! Ik heb me weer ingeschreven

[WernerL]

* WernerL heeft zich dit jaar ook ingeschreven. Ik heb wel zin een uitdaging.
Programmeertaal is vrij te kiezen als ik het goed begrijp, dan heb ik weer een excuus om Scala uit de kast te halen.

[Woy]

Jammer ook dit jaar komt het weer heel erg slecht uit qua datum aangezien ik vrijdag avond op wintersport vertrek. Ik zal eens kijken of ik vrijdag eind van de dag wat tijd kan vrijmaken, meestal zijn de qualifier opdrachten niet echt complex.

edit:
Ik zie trouwens dat de qualification al op donderdag 01:00 nederlandse tijd begint. Dat scheelt toch weer een dag. ( http://www.timeanddate.co...nd&iso=20150108T00&p1=%3A )

[ Voor 33% gewijzigd door Woy op 06-01-2015 10:16 ]

[Eärendil]

Woy schreef op dinsdag 06 januari 2015 @ 10:12:
edit:
Ik zie trouwens dat de qualification al op donderdag 01:00 nederlandse tijd begint. Dat scheelt toch weer een dag. ( http://www.timeanddate.co...nd&iso=20150108T00&p1=%3A )

Dat is denk ik een foutje in de timeanddate.com link, in de tekst staat January 8, 2015 at 4:00 PM PST, en dat is bij ons 9 januari 1:00 AM

[Woy]

Eärendil schreef op dinsdag 06 januari 2015 @ 12:58:
[...]

Dat is denk ik een foutje in de timeanddate.com link, in de tekst staat January 8, 2015 at 4:00 PM PST, en dat is bij ons 9 januari 1:00 AM

Je hebt gelijk, de link op facebook is ook aangepast: http://www.timeanddate.co...d&iso=20150108T16&p1=1240

[The_Ghost16]

Ik heb me ook ingeschreven. Moet wel even kijken of ik er tijd voor kan vrij maken.

[NotYetBritish]

Ook ingeschreven, eerste keer, eens kijken of het wat kan gaan worden

[Mortis__Rigor]

Ik had goesting om mij in te schrijven, maar omdat al de datums in de voorwaarden het nog over 2013 en 2014 hebben, weiger ik dat te doen. Ik wil sowieso al niet graag mijn adresgegevens aan facebook geven, en zeker niet als ik niet kan opmaken aan de hand van hun algemene voorwaarden voorwat ze allemaal gebruikt kunnen worden.

[Mattie112]

Hm ik heb die velden niet ingevuld -> submit "You have been registered" EN "All fields required" ja wat is het nou jongens? Zit er eigenlijk ook niet op te wachten om mijn adresgegevens te geven (zeker niet omdat ik verder geen facebook gebruik)

[WernerL]

Adres hebben ze blijkbaar nodig om een tshirt te kunnen sturen als je bij de beste 500 hoort in ronde 1.
Waarom ze adresgegevens daarvoor niet achteraf sturen is mij ook een raadsel.

[Megamind]

Zodat je misschien niet met meerdere accounts meedoet? Ik sta al met mijn adres ingeschreven sinds de 1e rond, en nog nooit snailmail van ze mogen ontvangen

[Ealanrian]

Ik heb me ook maar ingeschreven. Ik heb voor de verandering eens wat tijd en ik zie wel hoever ik kom. Het is in ieder geval een goeie oefening

[Zeg]

Beetje apart inderdaad dat je je adresgegevens al bij voorbaat moet invullen. Leek me voor de rest nog best een interessante uitdaging. Jammer!

[Camulos]

Ik ben er bij
(zal helaas niet voorbij ronde 1 komen.. icm wintersport)

[Anoniem: 170251]

Ook dit jaar weer van de partij. Leuk Start over 3 uur!

[Megamind]

Iemand al begonnen? Eerste 2 zijn vrij eenvoudig, derde nog niet naar gekeken.

[WernerL]

Ben even door de challenges aan het lezen. De eerste is me niet helemaal duidelijk. Er zit geen limiet aan het aantal getallen dat je mag omwisselen neem ik aan? Maar het groter of kleiner maken mag niet opvallen dus getallen sorteren van groot naar klein is geen optie.

2 is makkelijk, daar begin ik denk ik mee. 3 moet ook wel te doen zijn. Ik ben er iig al uit welk algorithme ik daar voor wil gebruiken.

//edit
De voorbeeld input en output maakte challenge1 duidelijk, ok eitje. :-)

[ Voor 9% gewijzigd door WernerL op 09-01-2015 09:11 ]

[HuHu]

Challenge 1:

Output
For the ith number, print a line containing "Case #i: " followed by the smallest and largest numbers that can be made from the original number N, using at most a single swap and following the rules above.

Dus 0 of 1 swaps.

[WernerL]

Dat inderdaad over het hoofd gezien.
Challenge 1 ondertussen in elkaar gezet. Die was uiteindelijk erg makkelijk. Ik ga vanavond wel verder met 2 en 3. Het is gewoon een werkdag namelijk.

[boe2]

De eerste is gemakkelijk. Nummer twee vind ik dan weer juist erg moeilijk 1 google opdracht verder was het plots een eitje . Op naar nummer 3.

[ Voor 34% gewijzigd door boe2 op 09-01-2015 13:53 ]

[Woy]

Alle 3 de problemen heb ik redelijk eenvoudig opgelost, nu nog afwachten of ze ook goed opgelost zijn.

[WernerL]

Maakt het trouwens uit hoe je de input inleest? Want volgens mij moet je ook sourcecode uploaden. Gaat Facebook die (geautomatiseerd) uitvoeren? Op dit moment lees ik gewoon een textfile met de naam 'input.txt' in. Ik kan verder ook geen regels vinden wat betreft het inlezen van de inputfile.

[Woy]

WernerL schreef op vrijdag 09 januari 2015 @ 13:24:
Maakt het trouwens uit hoe je de input inleest? Want volgens mij moet je ook sourcecode uploaden. Gaat Facebook die (geautomatiseerd) uitvoeren? Op dit moment lees ik gewoon een textfile met de naam 'input.txt' in. Ik kan verder ook geen regels vinden wat betreft het inlezen van de inputfile.

Volgens mij niet. Ik denk dat Facebook deze code in eerste instantie niet eens bekijkt, het is meer ter controle voor als er later de indruk gewekt is dat je niet eerlijk gespeeld hebt. ( Waarschijnlijk comparen ze de code ook met de andere inzendingen zodat dubbele inzendingen opvallen )

[Eärendil]

Het maakt niet uit hoe je de input in leest en hoe je de output genereert. Dit mag bijv. via stdin/stdout, hardcoded filenames, filenames die je meegeeft op de commandline of een combinatie hiervan. De enige eis aan de code is dat het geschreven is in een taal waar een gratis compiler of interpreter voor beschikbaar is.

Na de ronde kan je de code van alle deelnemers bekijken bij het scoreboard.

[PMBergman]

Ook ingeschreven. Ben pas net begonnen met programmeren in C++, maar ik hou van puzzelen!

[WernerL]

Dus input en output maakt niets uit, mooi :-)

Zojuist even bezig geweest met challenge 2. Ik dacht, doe dat even.

Case #1: yes
Case #2: no
Case #3: yes
java.lang.OutOfMemoryError: GC overhead limit exceeded...

Ik ben er bijna.

[Megamind]

Bij challenge 2 bij de voorbeelden heb ik: yes no yes no no, die laatste krijg ik niet voor elkaar, ik heb 'm zelfs in Excel gestopt en er een solver op losgelaten en die kwam er ook niet uit.

Welke foods tellen jullie bij elkaar op bij de laatste case?

[SirDarkAngel]

Alle 3 met Powershell opgelost, had verwacht dat ze het zouden afkeuren omdat het geen programmeertaal is, maar wordt "gewoon" goedgekeurd.

[Eärendil]

Powershell is toch gewoon een taal waar een gratis interpreter voor beschikbaar is? Dat mag gewoon.
En verder kijken ze in dit stadium volgens mij helemaal niet naar de code, hooguit een plagiaat-check door het te vergelijken met de andere inzendingen.

[WernerL]

Zojuist alvast challenge 1 gesubmit. Stond er een 0 in de input die ik kreeg. Ging mijn applicatie daar op zijn bek. Gelukkig binnen de tijd kunnen fixen.

[Woy]

SirDarkAngel schreef op vrijdag 09 januari 2015 @ 18:25:
Alle 3 met Powershell opgelost, had verwacht dat ze het zouden afkeuren omdat het geen programmeertaal is, maar wordt "gewoon" goedgekeurd.

Tevens is je inzending nog niet eens echt beoordeeld, alleen de inzending is geaccepteerd. De daadwerkelijke beoordeling gebeurt pas later. En reken er maar niet op dat ze in dit stadium de daadwerkelijke code gaan beoordelen.

[Woy]

WernerL schreef op vrijdag 09 januari 2015 @ 19:17:
Zojuist alvast challenge 1 gesubmit. Stond er een 0 in de input die ik kreeg. Ging mijn applicatie daar op zijn bek. Gelukkig binnen de tijd kunnen fixen.

Ja daar kon je natuurlijk donder op zeggen. Het staat niet voor niks zo duidelijk in de omschrijving dat de enige case waar een 0 als eerste getal acceptabel is als de input 0 is

WernerL schreef op vrijdag 09 januari 2015 @ 17:04:
Dus input en output maakt niets uit, mooi :-)

Zojuist even bezig geweest met challenge 2. Ik dacht, doe dat even.


[...]




Ik ben er bijna.

Dat is natuurlijk iets waar je rekening mee moet houden met je oplossing. Vaak is de lompe oplossing niet feasable met de limieten die gegeven zijn. Je zult vaak toch ergens iets slimmer te werk moeten gaan dan puur brute kracht, al valt dat in deze ronde nog wel mee.

[ Voor 37% gewijzigd door Woy op 09-01-2015 19:44 ]

[WernerL]

Ik was al bezig met Streams en lazy vals in Scala, dat mocht allemaal niet baten. Nu heb ik het iets slimmer aangepakt. En een truukje gevonden waarmee scala tail recursive functies kan optimizen:

@scala.annotation.tailrec

En toen kreeg ik dit als output:

werner@werner-desktop:~/Documents/Projects/Facebook hackerscup/challenge2$ scala Main
Case #1: yes
Case #2: no
Case #3: yes
Case #4: no
Case #5: yes

Bij Case 4 blijft hij nog wel een paar seconden hangen omdat hij daar letterlijk alle mogelijke combinaties afgaat voordat hij de conclusie trekt dat er geen oplossing is. En met 20 gerechten zijn dat er nogal wat. Maar dat kan denk ik niet anders.

Op naar challenge 3.

//edit
Challenge 2 gaat nu binnen 1 seonden met de voorbeeld input. Ik ga hem submitten.

//edit2
En met de 20 cases die ik van Facebook kreeg bij het submitten had hij nu ook totaal geen moeite meer
Wat een opluchting na een uur tegen stackoverflows en out of memory errors aan te kijken.

[ Voor 37% gewijzigd door WernerL op 09-01-2015 20:32 ]

[kaesve]

Ik gebruik voor deze challanges voor het eerst C. Volgens mij heb ik een werkende oplossing voor probleem 1, maar wat is mijn implementatie afschuwlijk lelijk

[Qzar]

Ik heb zojuist de eerste challenge gedaan, toen ik de input file downloade en door mijn script haalde zag ik echter een foutje: Het getal 9990999 werd niet goed verwerkt. Hierin moet de nul worden geswapped met het tweede en laatste getal voor minimum en maximum.

Echter geeft mijn score wel 15 punten aan terwijl die voor dit onderdeel staan. Verder waren wel alle 19 andere getallen goed verwerkt. Is er een foutmarge of iets dergelijks, of heeft Facebook hier zelf ook een fout gemaakt?

[dcm360]

De daadwerkelijke controle van de antwoorden gebeurt pas na het beëindigen van de ronde.

[WernerL]

Ow shit dan heb ik de eerste ook fout denk ik. Bij precies die is bij mij 9990999 ook niet goed verwerkt.
Ben nu nog steeds bezig met challenge 3... Die is wat lastiger. Ik kan al het kortste pad uitrekenen zonder rekening te houden met de turrets. Nu nog rekening gaan houden met turrets... pleuris dingen, want in sommige situaties moet je dus een stap terug zetten omdat er geen andere optie is. Mijn algorithme pakt nu alleen stappen naar positities waar hij nog niet geweest is om te voorkomen dat hij in rondjes gaat lopen. Eens zien hoe ik dit aan ga pakken.

[ Voor 46% gewijzigd door WernerL op 10-01-2015 12:31 ]

[Ealanrian]

Helaas wat laat begonnen door een feestje en andere drukte maar zo juist probleem 1 ingevoerd. Nu eens kijken naar 2 en hopelijk morgen nog naar 3.

[dcm360]

De eerste heb ik nu ook opgestuurd, met dank aan de 9990999 testcase die hier genoemd werd ging die (denk ik) goed (mijn eerste versie wisselde de eerste 9 met de 0...), en met wat eigen testcases had ik ook nog wat randgevallen te pakken voordat ik mijn inzending heb gedaan.

De md5 van mijn antwoorden is d625c4e62a4e71a10cd17fc9d4d7a9fc, dus als iemand anders die ook heeft dan hebben we in ieder geval dezelfde oplossingen gevonden.

[HuHu]

Het wachten op het antwoord voor opgave 2 duurde me langer dan me lief was, maar uiteindelijk wel ruim binnen de tijd.

Ik heb een sub-optimale oplossing geïmplementeerd. Moest wel lukken dacht ik, maar ik kneep 'm toch even toen 'ie niet na een paar seconden klaar was .

[dcm360]

En ook de tweede heb ik nu ingeleverd. De truc hier was denk ik om niet al te hard te optimaliseren, de invoergrootte was immers best klein met hooguit 20 testcases en 20 soorten voedsel. Ik heb 3 varianten geprobeerd, waarbij 1 van de 3 een detectie had om snel te kunnen stoppen, en de andere 2 die detectie niet hadden maar de keuzevolgorde omgedraaid was. In alle 3 de gevallen duurde het compilen langer dan de oplossingen berekenen. (net als WernerL ben ik de opgaven ook met Scala aan het oplossen)

[WernerL]

En mijn algoritme voor challenge 3 lijkt nu ook te werken. Nu alleen nog de input parsen en voor iedere case de oplossing zoeken. (Ben er niet heel de dag mee bezig geweest nee, zat vanmiddag in Brabant)

[Xuj]

Zojuist 1 en 2 ingeleverd. Ik las de 'maximaal 1 swap regel' van opdracht 1 in eerste instantie als 'er moet 1 swap plaatsvinden', maar gelukkig is dat nog goed gekomen.

Heb al een ideetje voor 3, morgen maar proberen te implementeren.

[mclegodude]

misschien binnenkort maar weer eens wat meer met dit soort logische puzzeltjes bezig gaan,

als dan blijkt dat je met opdracht 1 al beetje logica-issues tegenkomt is het toch wel een beetje beschamend..

[frickY]

Hou mezelf bij dit soort dingen vaker voor mee te doen,maar doe het vervolgens nooit.
Dit keer toch maar ingeschreven en morgen eens voor gaan zitten.
Weapon of choice; PHP

1 en 2 zullen geen probleem zijn, maar voor 3 heb ik nog geen flauw idee

[WernerL]

3 heb ik niets voor kunnen submitten... Ik had moeten testen met grotere levels. "Java out of memory"... Met de voorbeeld input had mijn algoritme geen enkel probleem. FFUU... nouja, 1 en 2 heb ik wel gesubmit dus ik verwacht gewoon door te mogen naar ronde 1.

Ik had er nog voor gezorgd mijn solver een stream genereerd. Die zou lazy eveluated moeten zijn in Scala. Toch iets wat ervoor gezorgd heeft dat het geheugengebruik sky high werd.

[Soultaker]

Als iemand zich verveeld is hier een extra uitdaging: kun je voor het eerste probleem een oplossing bedenken die ook werkt voor hele grotere getallen (met 100.000 cijfers bijvoorbeeld)?

[Ealanrian]

Ik ga het helaas niet halen, ik dacht dit weekend tijd te hebben maar helaas heb ik nog geen blok van meer als 3 uur gehad om iets te kunnen doen. Volgend jaar maar weer proberen

[Soultaker]

Voor de eerste twee problemen heb je geen 3 uur nodig, hoor.

[Camulos]

Soultaker schreef op zondag 11 januari 2015 @ 13:34:
Als iemand zich verveeld is hier een extra uitdaging: kun je voor het eerste probleem een oplossing bedenken die ook werkt voor hele grotere getallen (met 100.000 cijfers bijvoorbeeld)?

Denk dat 50+ digits al voor de meesten een probleem is, want dan kunnen ze niet meer makkelijk casten naar een integer / long.

Kun je een input file maken en dan delen op github-GIST of pastebin?
Dan kunnen we antwoorden vergelijken ^^

makkelijk voorbeeld (40 digits):
input: 1234567890123456789012345678901234567890
high: 9234567890123456789012345678901234567810
low: 1034567890123456789012345678901234567892

[Ealanrian]

Soultaker schreef op zondag 11 januari 2015 @ 13:57:
Voor de eerste twee problemen heb je geen 3 uur nodig, hoor.

Normaal niet nee. Helaas heb ik een paar maand niet geprogrammeerd en probeer ik het in een voor mij nieuwe taal te doen. Ik heb bij probleem 1 net een fout gevonden in de door mij upgeloade source code dus die zal waarschijnlijk afgekeurd worden en probleem twee heb ik een idee hoe die op te lossen alleen het implementeren moet nog

[Soultaker]

Camulos schreef op zondag 11 januari 2015 @ 13:58:
Denk dat 50+ digits al voor de meesten een probleem is, want dan kunnen ze niet meer makkelijk casten naar een integer / long.

Daar heb je gelijk in. Da's ook een goed tussenstation.

Kun je een input file maken en dan delen op github-GIST of pastebin?
Dan kunnen we antwoorden vergelijken ^^

Misschien later -- ik moet nog even het derde probleem oplossen. (Ja, ik ben vanmiddag pas begonnen. )

[Camulos]

Soultaker schreef op zondag 11 januari 2015 @ 14:02:
[...]
Daar heb je gelijk in. Da's ook een goed tussenstation.
[...]

Misschien later -- ik moet nog even het derde probleem oplossen. (Ja, ik ben vanmiddag pas begonnen. )

hehe, m2! succes nog even
Ga je na afloop weer een blog over je oplossingen schrijven? (vond dat altijd erg interessant)

[Soultaker]

Dunno, in het verleden loste ik op zaterdag de problemen op, en schreef ik op zondag de blogpost. Weet niet of ik daar nu tijd/zin in heb, maar wie weet.

[dcm360]

In mijn poging wat zelfbedachte worst-case levels van opdracht 3 op te lossen:

code:

Case #1: 396 (483)
Case #2: 5149 (109)
Case #3: 6472 (125)
Case #4: 7 (0)
Case #5: 9 (15)
Case #6: 6 (0)
Case #7: 4 (0)
Case #8: 3 (0)
Case #9: impossible (0)
Case #10: 8 (0)

De eerste 5 heb ik zelf bedacht, de laatste 5 zijn de gegeven tests van facebook. De eerste 3 zijn ongeveer 100 bij 100 groot, het getal tussen haakjes is de benodigde rekentijd. Nu maar eens de echte tests gaan doen (en die rekentijden nog even wegslopen).

[Xuj]

dcm360 schreef op zondag 11 januari 2015 @ 14:53:
In mijn poging wat zelfbedachte worst-case levels van opdracht 3 op te lossen:

code:

Case #1: 396 (483)
Case #2: 5149 (109)
Case #3: 6472 (125)
Case #4: 7 (0)
Case #5: 9 (15)
Case #6: 6 (0)
Case #7: 4 (0)
Case #8: 3 (0)
Case #9: impossible (0)
Case #10: 8 (0)

De eerste 5 heb ik zelf bedacht, de laatste 5 zijn de gegeven tests van facebook. De eerste 3 zijn ongeveer 100 bij 100 groot, het getal tussen haakjes is de benodigde rekentijd. Nu maar eens de echte tests gaan doen (en die rekentijden nog even wegslopen).

Zou je die zelfgeschreven levels willen delen?

[dcm360]

Xuj schreef op zondag 11 januari 2015 @ 15:18:
[...]


Zou je die zelfgeschreven levels willen delen?

Linkje

Ondertussen nog een testcase erbij, die specifiek mijn eigen code zou moeten dwarsbomen. Dat valt nog tegen...

En ik heb ook nog even de antwoorden (volgens mijn code dan) en mijn testinvoer voor de andere 2 opdrachten erbij gezet.

[ Voor 13% gewijzigd door dcm360 op 11-01-2015 16:00 ]

[Ealanrian]

Ondertussen toch nog 2 opgelost door terug te gaan naar Java waar ik bekender mee ben. Ik zie wel of ik een ronde door kom

[kaesve]

pft. 2 ingeleverd. de oplossing bedenken en implementeren kostte me niet heel veel tijd. Werken met input/output in C daarintegen wel Nouja, voor de andere twee problemen zou dat nu sneller moeten gaan. Voor p3 moet ik nog best wat werk verzetten omdat ik geen bestaande libraries gebruik voor datastructuren, maar volgens mij gaat het nog wel binnen de tijd lukken.

[dcm360]

Ealanrian schreef op zondag 11 januari 2015 @ 16:22:
Ondertussen toch nog 2 opgelost door terug te gaan naar Java waar ik bekender mee ben. Ik zie wel of ik een ronde door kom

Welke taal was je eerst in bezig? Gewoon uit nieuwsgierigheid.


De derde heb ik ondertussen ingeleverd, en ik ben benieuwd of die goed gegaan is. Ik heb ook nog even een run gedaan met de timers weer aan, en de traagste ging in 265ms (op de eerste na, maar dan is de JVM waarschijnlijk nog spul aan het laden en is de CPU mogelijk nog teruggeklokt). Ik moet overigens wel even toegeven dat ik heb gedraaid met '-Xss500m', wat misschien wel flink te veel was, maar de standaard was te weinig. En voor de uitvoertijd maakte het niet uit.

[frickY]

Ondanks dat ik 1 en 2 ook wat had onderschat die zonder problemen ingeschoten. Maar zit me nu echt al even blind te staren op 3 Heerlijk!

Kwartje is bij mij nog niet gevallen hoe je voorkomt oneindig lang stapjes heen en terug te moeten doorrekenen om te bepalen of iets uiteindelijk misschien tóch 'possible' is.

Camulos schreef op zondag 11 januari 2015 @ 13:58:
makkelijk voorbeeld (40 digits):
input: 1234567890123456789012345678901234567890
high: 9234567890123456789012345678901234567810
low: 1034567890123456789012345678901234567892

Gaat hier goed. Wat doet deze bij jou?

code:

208998628034825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348610454326648213393607260249141273724587006606315588174881520920962829254091715364367892590360011330530548820466521384146951941511609433057270365759591953092186117381932611793105118548074462379962749567351885752724891227938183011949129833673362440656643086021394946395224737190702179860943702770539217176293176752384674818467669405132000568127145263560827785771342757789609173637178721468440901224953430146549585371050792279689258923542019956112129021960864034418159813629774771309960518707211349999998372978049951059731732816096318595024459455346908302642522308253344685035261931188171010

Is een random stukje pi
Hier begint mijn lowest met een 2 Heb dus een bug

[ Voor 89% gewijzigd door frickY op 11-01-2015 17:14 ]

[Ealanrian]

dcm360 schreef op zondag 11 januari 2015 @ 16:39:
[...]

Welke taal was je eerst in bezig? Gewoon uit nieuwsgierigheid.


De derde heb ik ondertussen ingeleverd, en ik ben benieuwd of die goed gegaan is. Ik heb ook nog even een run gedaan met de timers weer aan, en de traagste ging in 265ms (op de eerste na, maar dan is de JVM waarschijnlijk nog spul aan het laden en is de CPU mogelijk nog teruggeklokt). Ik moet overigens wel even toegeven dat ik heb gedraaid met '-Xss500m', wat misschien wel flink te veel was, maar de standaard was te weinig. En voor de uitvoertijd maakte het niet uit.

Ik heb eerst gewerkt in C++ en gistermiddag was dat de eerste keer dat ik er mee heb gewerkt. Helaas ging dat gewoon te veel tijd kosten, ik ga de komende tijd wel proberen de problemen alsnog op te lossen in C++.

[dcm360]

Het heeft denk ik wel een heel andere manier van oplossen nodig dan dat ik doe in Scala. Voor de eerste en derde opgave kwam het er eigenlijk op neer dat ik bedacht welke collections nuttig waren, en er vervolgens op los gaan met map, fold, filter, sort en contains. De 2e opdracht overrompelde me echter een beetje, die bleek nauwelijks iets uit de trucendoos nodig te hebben.

[mclegodude]

frickY schreef op zondag 11 januari 2015 @ 16:46:
Ondanks dat ik 1 en 2 ook wat had onderschat die zonder problemen ingeschoten. Maar zit me nu echt al even blind te staren op 3 Heerlijk!

Kwartje is bij mij nog niet gevallen hoe je voorkomt oneindig lang stapjes heen en terug te moeten doorrekenen om te bepalen of iets uiteindelijk misschien tóch 'possible' is.

[...]

Gaat hier goed. Wat doet deze bij jou?

code:

208998628034825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348610454326648213393607260249141273724587006606315588174881520920962829254091715364367892590360011330530548820466521384146951941511609433057270365759591953092186117381932611793105118548074462379962749567351885752724891227938183011949129833673362440656643086021394946395224737190702179860943702770539217176293176752384674818467669405132000568127145263560827785771342757789609173637178721468440901224953430146549585371050792279689258923542019956112129021960864034418159813629774771309960518707211349999998372978049951059731732816096318595024459455346908302642522308253344685035261931188171010

Is een random stukje pi
Hier begint mijn lowest met een 2 Heb dus een bug

Misschien iets te maken met 32 bits limits? Ik weet niet welke taal je het doet..

Volgens mij is dat getal ook groter dan de limits gesteld door fb

[frickY]

Nee, mijn afhandeling om geen 0 als eerste cijfer te swappen faalde

dcm360 schreef op zondag 11 januari 2015 @ 15:47:
Linkje

Nice, thanks! Hoelang doet jouw programma over bijvoorbeeld de eerste? Hier ~6 minuten. Ik weet wat er moet gebeuren om dat drastisch te verlagen... maar nog niet hoe

edit:
Nu je gehele test-input binnen 50 seconden . Yay

[ Voor 98% gewijzigd door frickY op 11-01-2015 21:08 ]

[Soultaker]

Eigenlijk mag je geen testdata delen (=samenwerken), he.

[Camulos]

opgave 1 en 2 gemaakt

Opgave 3 liep uit het geheugen Eens kijken of we dat nog kunnen tweaken (no submit). Case 4.. meer dan 1800MB

EDIT: opgave 3 getuned.. opgelost in 11ms, helaas zijn mijn 6 minuten allang verstreken. Had initiele cycle-detectie veel beter moeten coden

allen in C#

[ Voor 48% gewijzigd door Camulos op 11-01-2015 22:12 ]

[frickY]

#3 ook gesubmit
Pittig, maar erg leuk als het uiteindelijk lukt.
Kneep hem wel even bij de echte output, maar wat ik zo handmatig kan checken lijkt het te kloppen. Wel zonde van mijn domme fout in #1

[Soultaker]

Ik vond de testdata van Facebook maar laf vergeleken met wat dcm360 had verzonnen. Leek ook niet heel gevarieerd te zijn qua design. Ik geloof dat ik elk jaar klaag over de kwaliteit van de testdata bij de FBHC.

[kaesve]

blegh. Ik moet voor de volgende ronde (als ik nog mee mag doen) een debugger regelen.. dat heeft mij waarschijnlijk opdracht 3 gekost

ik genereer een 3d graaf uit opdracht 3, waar ik a* op uitvoer. Maar volgens mij accepteert mijn a* implementaties nog heel soms moves die niet zouden mogen. Net dcm360s testset uitgevoerd en die doet hij wel helemaal goed.. dus wie weet heb ik 'm toch nog goed.

[Camulos]

Jeuj, eerste 2 helemaal goed

@Soultaker: ik vond de voorbeelden erg laf vergeleken bij de echte input. Voelde behoorlijk zoals ProjectEuler: super easy brute force gaat goed op voorbeeld, maar bij echte challenge wordt de input exponentieel groter (natuurlijk moet je ook nooit brute forces )

@kaesve: ik had opdracht 3 met Breadth First Search gedaan, waarbij de eerste die bij de goal is meteen het minst aantal stappen is.

Maar kan iemand verifieren dat dit het antwoord bij 3 had moeten zijn:

code:

edit: testcases zijn in random volgorde

[ Voor 31% gewijzigd door Camulos op 12-01-2015 09:02 . Reden: testcases zjin in random volgorde ]

[Megamind]

Mijn oplossing voor 2:

code:

from itertools import *
I=lambda:map(int,raw_input().split())
for t in range(input()):
    e=I()
    a=[I()for i in"."*input()]
    print "Case #%d: %s" % (t+1, ["no", "yes"][any(map(sum,zip(*x))==e for r in range(1,len(a)+1) for x in combinations(a,r))])

Niet echt, kwam ik tegen van de gene die op de 2e plek staat.

[frickY]

Camulos schreef op maandag 12 januari 2015 @ 06:21:

Maar kan iemand verifieren dat dit het antwoord bij 3 had moeten zijn:

code:

--

edit;
Input lijkt per deelnemer te wisselen dus is niet te vergelijken.

[ Voor 60% gewijzigd door frickY op 12-01-2015 08:54 ]

[Camulos]

frickY schreef op maandag 12 januari 2015 @ 07:59:
[...]

Goede output was;

code:

Case #1: impossible
Case #2: 12
Case #3: impossible
..Case #19: 3
Case #20: 39

Thnx! maar are you sure?
Bij was laser_maze.txt als eerste:

code:

20
1 7
S...G#^
2 5
##^##
S...G
1 7
S...G.^
74 29
..#............#.#.....#.....
etc

Waarbij de eerste echt wel mogelijk is, en wel in 4 stappen

of krijgen mensen random input?

[HuHu]

Opgave 1 fout . Gelukkig had ik 2 wel goed.

Ik dacht opgave 1 op een "slimme" manier op te lossen. Maar aan de code van de Top10 te zien, ging brute-force ook prima.

[frickY]

@Camulos
Zo te zien is de input dan random ja. Die case die jij als eerste kreeg was bij mij de zesde.
Om mazes te vergelijken kunnen we het dus beter over de width-height hebben in plaats van de case. Behalve de eenvoudige (1-3, 1-7, 2-5) zijn die bij mij uniek.

[ Voor 58% gewijzigd door frickY op 12-01-2015 09:34 ]

[Camulos]

frickY schreef op maandag 12 januari 2015 @ 08:53:
@Camulos
Zo te zien is de input dan random ja. Dit is welke ik als 1ste case krijg;

code:

20
27 5
..#..
..snip..
..#v.
...#.

Die case die jij als eerste kreeg was bij mij de zesde.
Om mazes te vergelijken kunnen we het dus beter over de width-height hebben in plaats van de case. Behalve de eenvoudige (1-3, 1-7, 2-5) zijn die bij mij uniek.

Zou jij jou input en output file op een Github-gist of pastebin willen zetten? Zou heel tof van je zijn!
Draai ik als ik thuis ben mijn programma om te zien of ik hetzelfde heb (en betekend dat mijn algoritme werkt )

[frickY]

Bij deze;
https://gist.github.com/anonymous/43c0ada7b1ff843bb88c

//edit
@ Soultaker

[ Voor 149% gewijzigd door frickY op 12-01-2015 10:15 ]

[Xuj]

Alle 3 goed! Of even afwachten tot dinsdag, wellicht dat er iets doorheen geglipt is..

Hier in ieder geval mijn drie in-en output files:
https://gist.github.com/JackieXu/785de3d747f665f4f5a1

[Soultaker]

Hier ook alles goed. Linkje naar m'n weblogpost met analyse & code, met visualizatie van Laser Maze.

[WernerL]

Ik heb alleen de 2e goed.
Die eerste is dus helemaal fout gekeurd omdat 1 case geen correcte output genereerde.

[Woy]

Soultaker schreef op zondag 11 januari 2015 @ 13:34:
Als iemand zich verveeld is hier een extra uitdaging: kun je voor het eerste probleem een oplossing bedenken die ook werkt voor hele grotere getallen (met 100.000 cijfers bijvoorbeeld)?

Mijn oplossing zou dan in principe moeten werken want heb alles gewoon met chars gedaan. Qua geheugen gebruik zou het met 100.000 ook gewoon moeten werken

Zie net dat ik alleen die fout heb, zal als ik terug ben eens kijken wat ik dan fout gedaan heb. Zal wel een slordig foutje zijn

[ Voor 13% gewijzigd door Woy op 12-01-2015 10:25 ]

[frickY]

Ik hoop hetzelfde als ik, dan voel ik mij weer wat minder dom
Mijn oplossing zou ook met enorme getallen moeten werken; Ik genereer een gesorteerde lijst met unieke cijfers (laag-hoog voor laagste nummer, hoog-laag voor hoogste) in het nummer. Vervolgens probeer ik het eerste gesorteerde nummer op de eerste plek te zetten. Als die daar al staat probeer ik het 2de op de 2de positie te zetten, etc. Die gesorteerde lijst is nooit groter dan 10 cijfers.
Mijn fout zit in de afhandeling om de 0 niet vooraan te zetten. Die zette ik dan op de 2de positie.. terwijl ik gewoon het volgende gesorteerde cijfer vooraan had moeten zetten

[ Voor 12% gewijzigd door frickY op 12-01-2015 10:50 ]

[WernerL]

Soultaker schreef op maandag 12 januari 2015 @ 09:52:
Hier ook alles goed. Linkje naar m'n weblogpost met analyse & code, met visualizatie van Laser Maze.

Jouw oplossing voor 3, waarom dacht ik daar niet aan? Het is zo simpel, maar ik dacht er niet aan om tijd mee te nemen bij iedere stap. Ik ben echt voor iedere stap de hele maze opnieuw gaan genereren met alle turrets 90 graden gedraaid.. waarom zou mijn algoritme toch zoveel geheugen vreten?

Ik zal vanavond mijn code ook even delen voor de geïnteresseerde.

[frickY]

Hier een input file met een nummer van 100.000 posities voor Cooking The Books.
https://gist.githubuserco...94e87dc980ba3033d62/input

[dcm360]

Hm, dat wordt toch eens nagaan wat ik verkeerd gedaan heb bij de derde. Misschien was mijn depth-fist search toch niet ideaal...

[Woy]

WernerL schreef op maandag 12 januari 2015 @ 10:37:
[...]


Jouw oplossing voor 3, waarom dacht ik daar niet aan? Het is zo simpel, maar ik dacht er niet aan om tijd mee te nemen bij iedere stap. Ik ben echt voor iedere stap de hele maze opnieuw gaan genereren met alle turrets 90 graden gedraaid.. waarom zou mijn algoritme toch zoveel geheugen vreten?

Ik zal vanavond mijn code ook even delen voor de geïnteresseerde.

Ik heb bijgehouden welke positie + turn % 4 ik verwerkt had. Die hoeven niet meer meegenomen te worden. Verder gewoon breadth first search.

frickY schreef op maandag 12 januari 2015 @ 10:36:
Ik hoop hetzelfde als ik, dan voel ik mij weer wat minder dom
Mijn oplossing zou ook met enorme getallen moeten werken; Ik genereer een gesorteerde lijst met unieke cijfers (laag-hoog voor laagste nummer, hoog-laag voor hoogste) in het nummer. Vervolgens probeer ik het eerste gesorteerde nummer op de eerste plek te zetten. Als die daar al staat probeer ik het 2de op de 2de positie te zetten, etc. Die gesorteerde lijst is nooit groter dan 10 cijfers.
Mijn fout zit in de afhandeling om de 0 niet vooraan te zetten. Die zette ik dan op de 2de positie.. terwijl ik gewoon het volgende gesorteerde cijfer vooraan had moeten zetten

Ik heb het veel eenvoudiger gedaan. Ik loop eenmaal door de string heen om het kleinste getal groter dan 0 te vinden, als die kleiner is dan het eerste getal wissel ik die om. Daarna zoek ik het kleinste getal inclusief 0 en die wissel ik met het eerste getal dat groter is. Kon nog wel iets efficiënter, maar dat was niet echt nodig.

[ Voor 4% gewijzigd door Woy op 12-01-2015 12:29 ]

[dcm360]

Aangezien ik de derde dus niet goed had, en ik een beetje benieuwd ben waarom, heb ik de invoer die ik heb gekregen even naast de voorbeeldtests neergezet in laser_maze.txt. Zou iemand met een correcte oplossing mij de juiste antwoorden kunnen vertellen? (ik zet er zo ook nog even mijn output naast in laser_maze_output.txt)

[Xuj]

dcm360 schreef op maandag 12 januari 2015 @ 12:36:
Aangezien ik de derde dus niet goed had, en ik een beetje benieuwd ben waarom, heb ik de invoer die ik heb gekregen even naast de voorbeeldtests neergezet in laser_maze.txt. Zou iemand met een correcte oplossing mij de juiste antwoorden kunnen vertellen? (ik zet er zo ook nog even mijn output naast in laser_maze_output.txt)

Dit krijg ik er bij mij uit:

code:

Case #1: impossible
Case #2: impossible
Case #3: 125
Case #4: 3
Case #5: 6
Case #6: 30
Case #7: 4
Case #8: 1
Case #9: 4
Case #10: 143
Case #11: 48
Case #12: 110
Case #13: 56
Case #14: 31
Case #15: 4
Case #16: 56
Case #17: impossible
Case #18: 87
Case #19: 8
Case #20: 8

[Horeamus]

dcm360 schreef op maandag 12 januari 2015 @ 12:36:
Aangezien ik de derde dus niet goed had, en ik een beetje benieuwd ben waarom, heb ik de invoer die ik heb gekregen even naast de voorbeeldtests neergezet in laser_maze.txt. Zou iemand met een correcte oplossing mij de juiste antwoorden kunnen vertellen? (ik zet er zo ook nog even mijn output naast in laser_maze_output.txt)

Bij mij is dit het resultaat.

code:

Case #1: impossible
Case #2: impossible
Case #3: 125
Case #4: 3
Case #5: 6
Case #6: 30
Case #7: 4
Case #8: 1
Case #9: 4
Case #10: 143
Case #11: 48
Case #12: 110
Case #13: 56
Case #14: 31
Case #15: 4
Case #16: 56
Case #17: impossible
Case #18: 87
Case #19: 8
Case #20: 8

dcm360 schreef op maandag 12 januari 2015 @ 11:05:
Hm, dat wordt toch eens nagaan wat ik verkeerd gedaan heb bij de derde. Misschien was mijn depth-fist search toch niet ideaal...

Misschien dat het hier aan ligt? Als je daadwerkelijk DFS hebt gebruikt in plaats van BFS, krijg je niet het kortste pad.

[Soultaker]

Woy schreef op maandag 12 januari 2015 @ 12:26:
Ik heb het veel eenvoudiger gedaan. Ik loop eenmaal door de string heen om het kleinste getal groter dan 0 te vinden, als die kleiner is dan het eerste getal wissel ik die om. Daarna zoek ik het kleinste getal inclusief 0 en die wissel ik met het eerste getal dat groter is.

Als ik dit letterlijk interpreteer, klopt het niet. Neem bijvoorbeeld 1032. Eerst zoek je het kleinste getal groter dan 0 (dat is de 2) maar die is niet groter dan 1, dus laat je 'm staan. Dan zoek je het kleinste getal (dat is 0) en wisselt dat om met... 1? (mag niet), 3 dan? Dat levert 1302 op, terwijl je 1023 kunt maken.

[dcm360]

Beiden bedankt Aangezien in een storinkje tussendoor kreeg plaats ik wat ik had ook maar even hier:

code:

Case #1: impossible (8145)
Case #2: impossible (3)
Case #3: 147 (1670)
Case #4: 3 (3)
Case #5: 6 (2)
Case #6: 30 (1062)
Case #7: 4 (3)
Case #8: 1 (1)
Case #9: 4 (2)
Case #10: 159 (714)
Case #11: 48 (172)
Case #12: 150 (484)
Case #13: 76 (219)
Case #14: 35 (123)
Case #15: 4 (242)
Case #16: 56 (196)
Case #17: impossible (1)
Case #18: 99 (283)
Case #19: 8 (24)
Case #20: 8 (2)

Mijn oplossing was overigens depth-first door de hele boom lopen, en met memoizatie takken overslaan die al geprobeerd zijn. Dat zou er in theorie ook voor moeten zorgen dat er nog wel kortere paden gevonden kunnen worden, maar dat er niet oneindig naar langere paden gezocht wordt. Verder zit er een heuristiekje in die er voor zorgt dat er eerst paden afgezocht worden die richting het doel gaan.

[Woy]

Soultaker schreef op maandag 12 januari 2015 @ 13:08:
[...]

Als ik dit letterlijk interpreteer, klopt het niet. Neem bijvoorbeeld 1032. Eerst zoek je het kleinste getal groter dan 0 (dat is de 2) maar die is niet groter dan 1, dus laat je 'm staan. Dan zoek je het kleinste getal (dat is 0) en wisselt dat om met... 1? (mag niet), 3 dan? Dat levert 1302 op, terwijl je 1023 kunt maken.

Nee ik wissel alleen om als een kleiner getal verderop in de string staat. Met als extra constraint dat het bij de eerste positie geen 0 mag zijn.

Vrij langzaam want ga voor elke positie opnieuw door de string voor een kleiner getal. Maar was geen enkel probleem voor de gegeven opdrachten en limieten.

[ Voor 13% gewijzigd door Woy op 12-01-2015 14:58 ]

[Soultaker]

Aha, dat kan kloppen. Ik dacht dat je een O(N) algoritme beschreef. Dat bestaat wel, maar is iets subtieler.

[Woy]

Soultaker schreef op maandag 12 januari 2015 @ 15:06:
Aha, dat kan kloppen. Ik dacht dat je een O(N) algoritme beschreef. Dat bestaat wel, maar is iets subtieler.

Daar had ik wel over gedacht, maar door tijdsgebrek heb ik voor de eenvoudigere oplossing gekozen.

[dcm360]

Worst-case is de mijne ook O(N²). Maar eigenlijk geldt bij die opdracht dat je wel een heel erg inefficiënt algoritme moet bedenken om het traag te laten worden met deze invoergrootte.

[Camulos]

@Soultaker en @dcm360: bij de lasermaze heb ik nog niet ondekt hoe je n*m stappen moet zetten (10K voor een 100x100 maze). Echter heb ik voor de volgende structuren geen slechte score 2*8 -> 12 stappen, en 4*9 > 29 stappen. Je forceert de cursor telkens naar een veilige plek te laten vinden. Jullie al iets bedacht om minimaal n*m stappen te moeten zetten?

code:

2
2 8
S.....G>
#.#.#.#.
4 9
S.......>
#.#.#.#.#
.#.#.#..#
G.......>

[frickY]

Om meer stappen te creëren in een even groot veld moet aantal herhalingen omhoog; meer turrets

[ Voor 5% gewijzigd door frickY op 13-01-2015 08:31 ]

[WernerL]

Gisteravond nog bezig geweest in een poging die lazer maze te optimaliseren. Ik genereer nu eerst 4 lijsten met dodelijke positities. Deze kan mijn programma nu in +- 100ms genereren. Daarna gewoon breadth width search. Ik hoef nu niet meer voor iedere stap uit te zoeken of een volgende stap dodelijk is (dat kan nu met een simpele deadly.contains(...). Echter lukt het mijn applicatie nog steeds niet om snel een antwoord te vinden. Kleine levels gaan goed, De Facebook input lijkt nog steeds niet te lukken. Geen out of memory error meer, maar de CPU gaat wel naar 300%.

Ik geef op.