Facebook Hacker Cup 2015

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