Facebook Hacker Cup 2015

[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.

[frickY]

Dat is vergelijkbaar met wat ik doe.
Ik genereer 4 mazes; elk omringt met een muur en alles in de range van turrets en turrets zelf ook als muur.
Vervolgens ook breadth-first waarbij ik bij elke stap test met de maze die bij die stap hoort en alleen nog hoef te kijken naar wel/geen muur.
Nog even opslaan welk posities in welke maze je al hebt gehad en je voorkomt eindeloos dezelfde routes opnieuw proberen en dat je na 100 stappen tienduizenden moves moet controleren, wat kijkend naar je CPU wellicht bij jou wel nog gebeurd.

[ Voor 18% gewijzigd door frickY op 13-01-2015 13:21 ]

[Camulos]

@WernerL: de CPU omlaag krijgen is een kwestie van cycle detectie (zoals frickY al zegt).

Mijn tactiek was ongeveer hetzelfde:
- genereer de 4 mazes + lasers
- maak 4 boolean mazes (voor cycle detectie)
- Daarna breadth-first, waarbij geldt: Als je in een maze beweegt, zet je een boolean op true in cycle-detectie-maze. Indien je op een vakje komt die al op true staat, betekend dat er een snellere manier is om daar te komen.

Voorbeeld (L staat voor Laser), op te lossen in 16 stappen:

code:

input   step 0  step 1  step 2  step 3

#^^#S.  #^^#S.  #>>#L.  #vv#S.  #<<#S.
vG.#<.  vG.#<.  <G.#^.  ^LL#>L  >LL#v.
...v..  L..v..  LLL<..  .LL^..  ..L>LL
..>v#.  L.>v#.  ..v<#.  LL<^#.  ..^>#.
#.....  #..L..  #.L...  #L....  #.....

Nu hoef je slechts te kijken of je op een '.' loopt
Mijn algoritme doet de sample-input van dcm360 binnen 50ms

Tip: gebruik zoveel mogelijk arrays ipv lijsten, deze zijn vaak (veel) sneller maar moet je van te voren instantieren.
Voor mijn mazes waren dit: char[step][row][position] en bool[step][row][position]

Complete C# code voor opgave 3 is in deze GIST te zien
Ja ik weet dat ik zeer verbose code met veel comment

[dcm360]

Ook bij mij even een kijkje in de keuken: mijn code maakte 4 blacklists, met locaties waar geen move naar gemaakt kan worden in een bepaalde stap. Bij het maken van een move wordt de huidige positie in de blacklist voor (stappen % 4) toegevoegd, en op die manier kan ik ook depth-first door de hele boom heen zonder oneindig door te zoeken. Mijn blacklists zijn gemaakt met immutable sets, dus iedere volgende stap gaan er een aangevulde en 3 ongewijzigde sets de volgende aanroep van de recursieve functie in.

Voor mijn code is een laserstraal, een muur, of een positie van n*4 stappen geleden dus hetzelfde: een plaats die niet (meer) bereikbaar is. Leuke theorie, maar in de praktijk werkte het in de vorm van mijn implementatie niet niet.

edit: En ik heb mijn probleem gevonden: mijn memoizatie werkt op basis van (stappen % 4) en de positie. Dat heb ik nu aangepast naar stappen (geen restwaarde na deling) en positie, en er komen wel de juiste antwoorden uit. Wel weer een beetje jammer dat de kleinste route waar het fout ging al 31 stappen groot was, dus of ik dat nog eens ga uitschrijven...

[ Voor 19% gewijzigd door dcm360 op 14-01-2015 01:23 ]

[Woy]

Ah, ik zie wat ik fout gedaan heb bij de eerste opgave. Per ongeluk met het grootste getal ook van voor naar achter gezocht voor een vervanger, maar dat moet natuurlijk van achter naar voren gebeuren.

[WernerL]

Er ging blijkbaar wat mis met het opbouwen van de history bij challenge3. Had het redelijk snel opgelost.

werner@werner-desktop:~/Documents/Projects/Facebook hackerscup/challenge3/attempt2$ scala Main smalllevel.txt
Solution found in 39 steps
Executiontime: 5814 msecs

Hij doet er bijna 6 seconden over, maar het werkt met deze level.

code:

S...#..#...#############################
..........<..###..######.............###
........................................
#......v...#.##########.................
..#...^..##..################.....##..##
....###......##########.................
##########...##########........G........

Code staat op github: https://github.com/Werner...llenge3/fbchallenge.scala

Er zullen vast genoeg mogelijkheden zijn om hem sneller te krijgen maar nu ben ik er echt klaar mee.

[terje7601]

Hoe gebeurt de puntentelling voor Round 1? Is dit: punten uit Qualification Round + punten uit Round 1? Of herbegint iedereen weer vanaf 0? En hoeveel punten zijn er te verdienen in Round 1?
Ik had maar 45 punten, dus ik vraag me af of ik nog wel kans maak om naar Round 2 door te gaan (backtracking werkte nochtans prima op de sample input voor de laser maze...en dan download je de werkelijke input en besef je dat je programma in de eerste 6 jaar niet klaar zal zijn )

[ Voor 15% gewijzigd door terje7601 op 14-01-2015 20:23 ]

[Soultaker]

Elke ronde is onafhankelijk van de vorigen. Hoeveel punten er te verdienen zijn maakt dus ook niet uit; het gaat er puur om hoe je scoret relatief aan de andere deelnemers.

[frickY]

En we zijn los met de volgende ronde

De eeste maar even los gelaten. Ik zie ongetwijfeld iets doms over het hoofd maar alleen al een lijst met primes genereren die tussen A en B ligt duurt te lang
Bij twee kan ik het voorbeeld niet rijmen met de opdracht, dus daar moet ik me nog even langer blind op staren Waarom is de "h" goed genoeg om "hi" te maken..

[ Voor 118% gewijzigd door frickY op 17-01-2015 22:05 ]

[WernerL]

Die eerste is niet zo moeilijk. Lang leve streams in Scala. (Oplossingen mag ik nog niet bespreken neem ik aan dus dat komt morgenavond wel) Het gaat fout bij het parsen van de input. Grote getallen duurt lang. Ik durf mijn code nog niet te submitten. Bang dat ik weer een out of memory error krijg.

Met deze input blijft hij bij case 8 hangen:

code:

8
5 15 2
2 10 1
24 42 3
1000000 1000000 1
1000000 1000000 2
55500 60000 3
300 900 5
200000 300000 5

Even zien wat er nou precies fout gaat.

//edit
Mijn algoritme is traag bij getallen van 50000 80000 100, maargoed, als de stream van primes en primacities is opgebouwd zou hij alles snel moeten kunnen uitrekenen. Als hij nu binnen 6 minuten klaar is maar submitten.

//edit2

[info] Running Homework
Case #1 0
Case #2 5
Case #3 7
Case #4 2
Case #5 1791
Case #6 0
[success] Total time: 93 s, completed Jan 17, 2015 8:40:02 PM

93 seconden met deze input:

code:

6
50000 80000 100
5 15 2
2 10 1
24 42 3
55500 60000 3
300 900 5

Ik heb er vertrouwen in.

//laatste edit
1000000 1000000 1
Daar is mijn programma nu al een kwartier mee bezig. Waarom moeten die getallen toch zo groot zijn?

[ Voor 41% gewijzigd door WernerL op 17-01-2015 20:59 ]

[frickY]

Ik snap de autocomplete-opdracht nog steeds niet
Waarom is "h" genoeg voor "hi"...

[ Voor 52% gewijzigd door frickY op 17-01-2015 22:08 ]

[Horeamus]

frickY schreef op zaterdag 17 januari 2015 @ 22:06:
Ik snap de autocomplete-opdracht nog steeds niet
Waarom is "h" genoeg voor "hi"...

Volgens mij moet je het lezen als dat je elke keer voordat je een nieuw woord wil gaan typen, eerst zorgt dat het in je woordenboek staat. Dus het ziet er als volgt uit:

Voor het typen van 'hi' voeg je het toe aan je woordenboek:

code:

woordenboek = { 'hi' }

Vervolgens typ je het in je bericht, als je aan 'h' intypt, is het al uniek en heb je dus 1 aanslag nodig.

Daarna voeg je, voor het typen, het nieuwe woord 'hello' toe aan je woordenboek:

code:

woordenboek = { 'hi', 'hello' }

Als je de 'h' nu intypt, weet het systeem niet of je 'hi' of 'hello' wil hebben, maar zodra je 'he' intypt, is er nog maar één mogelijkheid. Hiervoor heb je dus 2 aanslagen nodig.

Als je dus het bericht 'hi hello' wil typen, heb je in totaal 3 aanslagen nodig.

Hoop dat dit helpt :-)

[ Voor 4% gewijzigd door Horeamus op 18-01-2015 00:43 ]

[dcm360]

Het duurde inderdaad even voordat ik die ook doorhad, waarschijnlijk hetzelfde probleem als frickY. Met de voorbeeldtests kwam ik met de derde testcase ook telkens uit op 15 of 9, afhankelijk van hoe ik een woord koos. Nu komen er wel braaf de juiste antwoorden uit, en als ik bij wijze van test een lompe woordenlijst er doorheen mik (164313 woorden, ongeveer 2MB) gaat dat in iets meer dan een seconde door mijn algoritme heen.

De eerste opgave heb ik op zich ook al een oplossing voor, al twijfel ik nog een beetje over de uitkomsten. Daar wil ik dus nog even wat langer over nadenken voordat ik die instuur. De performance is naar wat ik inschatten hier nu wel redelijk, iets als '2 10000000 3' gaat er door in 50 seconden.

* dcm360 zucht:

code:

Case #1: 4 (148)
Case #2: 10 (0)
Case #3: 7 (47)
Case #4: 12 (15)
Case #5: 12 (0)

Achja, nu maar wat blijslapen, morgen verder aanklooien

[ Voor 11% gewijzigd door dcm360 op 18-01-2015 03:28 ]

[frickY]

Ahhh.. Ik dacht dat het woordenboek vooraf helemaal gevuld werd, maar zo staat het et inderdaad niet. Helder, thanks!
Zo blijkt het naast een hacker-challenge ook nog een uitdaging begrijpend lezen #4 interpreteerde ik ook al verkeerd

//edit
Helemaal blij programma even aangepast en de goede antwoorden rollen er uit. Blind de input data gedownload en even vergeten dat dit die set van 20MB zou zijn
Dit wordt niet mijn ronde denk

[ Voor 84% gewijzigd door frickY op 18-01-2015 10:34 ]

[dcm360]

Nee, dat was de autocomplete Vergeten de timing erachter weg te slopen
Daarnaast moest er nog even snel een limiet van ongeveer 6000 ergens hard de code in. De kans op goede antwoorden was daarmee wel aanzienlijk, maar zeker weten of de antwoorden echt juist waren...


Met de 4e krijg ik nu overigens wel de juiste antwoorden op de testset. Echter, als ik de set iets groter maak (10000 werknemers) lukt het al voor geen meter meer.

Jeej, en de eerste geeft nu antwoorden die op zijn minst acceptabel zijn als ik ze vergelijk met wat ik zo snel even aan Wolfram Alpha vraag. Een shortcut met de priemgetallen bleek een beetje te short te zijn, een extra check verhielp dat. Worst-case looptijd zou nu zo ongeveer anderhalve minuut moeten zijn.

[ Voor 96% gewijzigd door dcm360 op 18-01-2015 15:22 ]

[kaesve]

voor opdrachten 2 en 3 denk ik nu een goede en efficiente oplossing te hebben. de anderen kom ik nog niet echt uit helaas. nuja, als ik 2 en 3 inderdaad goed heb, is het al een beter resultaat dan vorig jaar

edit:
probleem 1 en 4 maar opgegeven en besloten de rest van de tijd te gebruiken om mijn implementaties van 2 en 3 te testen. Echt grote test sets maken is nog best lastig, maar alles wat ik er naar gooi lijkt (correct) opgelost te worden in < 1 seconde

[ Voor 38% gewijzigd door kaesve op 18-01-2015 17:53 ]

[Soultaker]

Ik was 't hele weekend weg; ik heb nu de opgaven snel even in de trein opgelost. Ik was bang dat het mis zou gaan op die 20 MB grote inputs, maar dat internet blijkt behoorlijk snel te zijn.

[dcm360]

Nou, 4 was dus te traag... Dan blijft er de eerste opgave over die ik mogelijk correct kan hebben, en dat lijkt me net wat te weinig. Stomme is nog wel dat ik gisteren dacht: wellicht moet ik de gegeven input parallel gaan verwerken. Als ik dat nu had gedaan, dan was ik 8 keer sneller door opgave 4 gekomen en had het wel gelukt...

[Soultaker]

Ik heb een foutje in m'n implementatie van D gevonden.

[dcm360]

Hm, mijn inzending van Corporate Gifting is verdwenen... Feedback over gegeven, eens zien wat dat nog gaat doen.

[kaesve]

Ik ben heel erg benieuwd naar wat de juiste oplossing is voor opdracht 1. Mogen we het hier al over hebben? Ik heb hem niet ingeleverd maar dit was de beste aanpak die ik kon bedenken:

1] Vind de set van priemgetallen (lazy, of precomputed ofzo)
2] Vind alle k-combinaties in die set waarvan het product <= B
3] Voor elke combinatie, tel de getallen tussen A en B die de combinatie als 'distinct prime factors' heeft.

Maar naar mijn gevoel kon dit nooit efficient genoeg zijn om aan de gegeven constraints te kunnen voldoen..

[dcm360]

Dat mag wel onderhand, je mag niet meer inzenden nu.

1. Reken priemgetallen uit totaan de wortel van de upper-bound. Hoger hoeft niet Sla deze globaal op zodat herberekenen per opgave niet nodig is.
2. Stel n is de gegeven primacity, pak dan de n kleinste priemgetallen en vermenigvuldig die met elkaar. Als dit groter is dan de lower-bound, stel dit in als de lower-bound. Een primacitie van hoger dan 8 of 9 (even vergeten welke exact) is sowieso hoger dan de upper-bound overigens.
3 Bereken voor de getallen tussen de (nieuwe) lower en upper bounds de primacity. Sla deze ook globaal op.

Met deze aanpak is het berekenen van de cache met priemgetallen in verwaarloosbare tijd gedaan, en als de eerste opgave iets als '2 10000000 1' is, kan dat met deze aanpak binnen 20 seconden. Iedere volgende opgave kan met 'warme' cache binnen een seconde.

[Soultaker]

Jullie doen veel te moeilijk. De priemgetallen zijn impliciet de getallen met primacity 1.

C:

#include <stdio.h>

#define MAX 10000000

static int P[MAX+1];

int main() {
    // Hier worden alle primacities berekend:
    for (int i = 2; i <= MAX; ++i) {
        if (!P[i]) for (int j = i; j <= MAX; j += i) P[j]++;
    }
    int T = 0;
    scanf("%d", &T);
    for (int t = 1; t <= T; ++t) {
        int A = 0, B = 0, K = 0;
        scanf("%d %d %d", &A, &B, &K);
        int ans = 0;
        for (int i = A; i <= B; ++i) ans += (P[i] == K);
        printf("Case #%d: %d\n", t, ans);
    }   
}

[ Voor 5% gewijzigd door Soultaker op 18-01-2015 19:21 ]

[dcm360]

Priemgetallen hebben inderdaad een primacity van 1. Echter een getal als 9 is enkel deelbaar door het priemgetal 3 en heeft dus ook een primacity van 1. Niet alle getallen met een primacity van 1 zijn dus een priemgetal. Subtiel verschil, en dat maakt met jouw code niet uit zo te zien

[kaesve]

Dat ik veel te moeilijk dacht, was ook mijn verwachting. Maar niet alleen priemgetallen hebben primacity 1, toch? Ik nam aan dat alle machtsverheffingen van priemgetallen ook primacity 1 hadden.

[Soultaker]

dcm360 schreef op zondag 18 januari 2015 @ 19:27:
Priemgetallen hebben inderdaad een primacity van 1. Echter een getal als 9 is enkel deelbaar door het priemgetal 3 en heeft dus ook een primacity van 1. Niet alle getallen met een primacity van 1 zijn dus een priemgetal. Subtiel verschil, en dat maakt met jouw code niet uit zo te zien

Mja, mijn uitleg klopte niet helemaal bij m'n code. Als je een getal tegenkomt met primacity 0, dan is het een priemgetal. Vervolgens tel je één op bij de primacity van alle veelvouden van dat getal, inclusief het priemgetal zelf, vandaar dat je dan ook op een primacity van 1 uitkomt voor priemgetallen.

edit:
Heeft iemand anders probleem 4 nog opgelost? Ik wil checken of de gebugfixte versie van m'n code klopt...

[ Voor 7% gewijzigd door Soultaker op 18-01-2015 19:51 ]

[dcm360]

Op zich heb ik het 4e probleem dus wel opgelost (alleen Facebook is ergens mijn upload kwijtgeraakt). Ik wil wel jouw testbestand door mijn code halen (kan evt gestuurd worden naar <nickname>@<nickname>.nl), dan zien we op zijn minst of we dezelfde uitvoer krijgen.

Op de bekende locatie ben ik nu mijn invoer- en uitvoerbestanden aan het plaatsen (ik moet alleen nginx nog even zo ver krijgen om de wat grotere bestanden ook te willen).

[ Voor 6% gewijzigd door dcm360 op 18-01-2015 21:02 ]

[Soultaker]

Dit zijn mijn oplossingen, en hier is mijn testdata (in- en uitvoer).

[dcm360]

Even vergeleken:

A gaat bij mij gewoon fout (helaas de enige die wel correct bij FB is ingezonden).

B krijgen we dezelfde antwoorden uit, ondanks dat mijn code aantoonbaar steken laat vallen: er staat ergens Math.min(word.length(), 6000) om er voor te zorgen dat het binnen de geheugenlimieten blijft (zijnde niet over 20GB geen). Helaas is het antwoordformaat bij mij incorrect en zal ik dus geen punten krijgen.

C had ik niet, dus daar ben ik snel klaar mee

D is dan wel wat interessanter: bij #4 kom ik een factor 3 lager uit, #5 en #7 zit ik iets hoger, en bij #8 weer lomp veel (factor 14) lager. #9 en #10 heb ik weer een beetje hoger, net als #12 en #16. Ik ben nog een run aan het doen met wat aanpassingen, dat edit ik zo even bij.

Maar al met al lijkt dit zo zonder correcte inzendingen voor mij wel op te houden. Over het al dan niet ingezonden hebben van D heb ik nog feedback gestuurd, en op verzoek meer uitleg gegeven, maar daar vooralsnog geen verder antwoord van gehad, dus dat lijkt niets meer te worden. Jammer, het schoot dit jaar wel al iets meer op dan de vorige keer.

edit: D heeft bij mij issues met niet oplopend zijn van de invoergetallen. Dat verklaart de hier en daar lomp veel lagere uitkomsten bij mij.

[ Voor 6% gewijzigd door dcm360 op 19-01-2015 01:45 ]

[Soultaker]

De resultaten van de eerste ronde staan nu online. Alleen deelnemers die alle opgaven goed hadden, gaan door naar de volgende ronde.

Zoals verwacht had ik D fout (de nog binnen wedstrijdtijd gefixte versie was wel goed, maar die heb ik niet kunnen submitten) dus voor mij is het voorbij dit jaar.

[Ghehe]

Heb effe het originele bericht aangepast met de oplossingen.

- en ninja edit (voor één of andere redenen druk ik altijd op Quote i.p.v. edit ) -

[ Voor 182% gewijzigd door Ghehe op 20-01-2015 20:51 ]

[WernerL]

* WernerL ligt er ook uit. Voor de eerste opdracht wel een werkend algoritme gevonden maar die bleek niet snel genoeg te zijn. Ook nog een poging gewaagd aan winning the sports. Een oplossing gevonden, maar wederom rete traag. Deze challenges zijn niet helemaal geschikt voor mij denk ik.


Bij de eerste opdracht maakte ik 2 streams. 1 voor priemgetallen en 1 voor alle primacities. Priemgetallen gaan snel genoeg, maar het uitrekenen van 100000 primacities ging niet zo snel.

code:

lazy val numbers: Stream[Int] = 2 #:: Stream.from(3).filter(x =>
        numbers.takeWhile(y => y * y <= x).forall( z => x % z > 0))
        
lazy val primacities:Stream[Int] = 0 #:: Stream.from(1).map(x =>
        numbers.takeWhile(y => y <= x).filter(z => x % z == 0).length)

[Camulos]

iemand nog gekeken naar Ronde 2?
https://www.facebook.com/...php?round=323882677799153

[Soultaker]

Ik (nog) niet. Zitten er leuke problemen bij?