Facebook Puzzels

[Davio]

Naar aanleiding van een korte discussie in de coffee corner maar deze topic aangemaakt.

De Facebook puzzels zijn kleine programmeeruitdagingen die je hier kunt vinden:
http://www.facebook.com/careers/puzzles.php

De bedoeling is om ze te programmeren via thrift, zodat je ze kunt submitten, thrift vind je hier:
http://thrift.apache.org/

Ik snap echter zelf niet hoe het precies werkt met thrift, de tutorials zijn schaars en niet altijd even duidelijk.


Als iemand die het wel gelukt is om via thrift een puzzel op te lossen een korte beschrijving kan maken, dan zou ik, en met mij meerdere denk ik, daar erg dankbaar voor zijn.

Ik heb zelf de eerste (Hoppity) in PHP gebakken, niet veel spannends, zal hem wel posten als voorbeeld, ook al is het een beetje een spoiler. Maar omdat het zo'n simpel voorbeeld is, valt er niet veel te spoilen.

PHP:

<?php

$max = trim(file_get_contents($argv[1]));

// De volgorde is altijd hetzelfde:
// 3 -5 -6 -9 -10-12-15
// 18-20-21-24-25-27-30 etc..
// Dus: %3, %5, %3, %3, %5, %3, %15
// Maar hoeveel herhalingen hebben we nodig en wat komt er dan op het eind?
// Herhalingen is floor(n / 15)

// n%15 - Extra termen
// 0 - 0
// 1 - 0
// 2 - 0
// 3 - 1
// 4 - 1
// 5 - 2
// 6 - 3
// 7 - 3
// 8 - 3
// 9 - 4
// 10 - 5
// 11 - 5
// 12 - 6
// 13 - 6
// 14 - 6

$hops = array("Hoppity","Hophop","Hoppity","Hoppity","Hophop","Hoppity","Hop");
$terms = array(0,0,0,1,1,2,3,3,3,4,5,5,6,6,6);

for($i=0;$i<floor($max/15);$i++) fwrite(STDOUT, implode("\r\n", $hops)."\r\n");
for($i=0;$i<$terms[$max%15];$i++) fwrite(STDOUT, $hops[$i]."\r\n");
    
?>

Natuurlijk kan het simpeler met een for-loop van 1 tot n en dan alles van %3, %5 en %15 afvangen, maar dit is sneller voor grotere input.

[Anoniem: 180316]

Is dat niet een overdreven complexe oplossing?

C:

#include <stdio.h>

int main (int argc, char **argv)
{
    int n = 0;

    // File inlezen, bla, naar (int) n converten

    for (int i = 0; i < n; i++) 
    {
        if (!(i %3) && !(i % 5)) {
            printf ("Hop\n"); 
            continue;
        }
        if (!(i % 3)) {
            printf ("Hoppity\n");
            continue;
        }
        if (!(i % 5)) {
            printf ("Hophop\n");
            continue;
        }
    }

    printf ("\n");
    return 0;
}

[Xuj]

Hmm, grappig.

Een afgeleide van de eerste vraag van Project Euler.
Of waren deze puzzels er eerder...?

Edit: Oh. Met behulp van Thrift. Eens even kijken dan.

[ Voor 60% gewijzigd door Xuj op 01-01-2011 04:29 . Reden: Voortaan beter lezen ]

[Davio]

Anoniem: 180316 schreef op zaterdag 01 januari 2011 @ 00:36:
Is dat niet een overdreven complexe oplossing?

Ja, dat zei ik ook, maar voor grotere input werkt het beter. Ik had het eerst net als jij gedaan, maar later toch aangepast.

Dan is het O(n/15) ipv O(n) en je hoeft niet elke keer alle %-checks uit te voeren, gewoon één keer uitrekenen en de rest is outputten.

[Megamind]

Davio schreef op vrijdag 31 december 2010 @ 21:51:

De bedoeling is om ze te programmeren via thrift, zodat je ze kunt submitten, thrift vind je hier:
http://thrift.apache.org/

Volgens mij mag je gewoon submitten in deze talen:

All submissions must execute in a *NIX type environment (sorry, no Windows specific solutions are accepted). You are not guaranteed any libraries or plugins beyond what is part of the language/interpreter itself. The following languages are accepted:

* GNU C/C++ 4.2.3
* Ericsson Erlang 5.5.5
* GHC Haskell 6.8.2
* Sun Java 1.5.0_15
* INRIA OCaml 3.10.0
* Perl 5.8.8
* PHP 5.2.4
* Python 2.5.2
* Ruby 1.8.6

Some puzzles may require being solved with the following libraries:

* Thrift r760184

[webschaapje]

Ik ben zelf begonnen met de Battleship puzzle in Java, waar je ook Thrift voor nodig hebt. Alleen krijg ik zelf de hele tijd time-outs op thriftpuzzle.facebook.com (poort 9031). Maar dit is de code die ik tot nu heb:

Java:

try {
    
    // Setup connection
    TTransport transport = new TSocket("thriftpuzzle.facebook.com", 9031);
    TProtocol protocol = new TBinaryProtocol(transport);
    
    // Create client & connect
    Client client = new Client(protocol);
    transport.open();
    
    // Register with server
    client.registerClient("[e-mail]");
    
    // Close connection
    transport.close();
    
} catch (Exception x) {
    x.printStackTrace();
}

En ik krijg zelf een time-out op regel 12.

[Davio]

Megamind schreef op zaterdag 01 januari 2011 @ 12:23:
[...]

Volgens mij mag je gewoon submitten in deze talen:

[...]

Ja, maar om te verifiëren heb je volgens mij thrift nodig om te submitten en een hash te krijgen.

[YopY]

Oplossingkje voor puzzel 1 in Java, ik verveelde me. http://pastebin.com/22zKUS5C

Gebruikt een enum om de output en de voorwaarden waarop die moet tonen te bepalen. Is wel grappig .

[Light]

YopY schreef op zaterdag 01 januari 2011 @ 17:02:
Oplossingkje voor puzzel 1 in Java, ik verveelde me. http://pastebin.com/22zKUS5C

Gebruikt een enum om de output en de voorwaarden waarop die moet tonen te bepalen. Is wel grappig .

Leuk, maar de uitkomst voldoet niet aan de opgave. Als een getal deelbaar is door 15 moet je het anders behandelen dan wanneer het deelbaar is door 3 of door 5.

[YopY]

Light schreef op zaterdag 01 januari 2011 @ 17:39:
[...]

Leuk, maar de uitkomst voldoet niet aan de opgave. Als een getal deelbaar is door 15 moet je het anders behandelen dan wanneer het deelbaar is door 3 of door 5.

Ai ja, ik zie het. De volgorde van enums word verkeerd gedaan en hij doet dubbele uitvoer. Dat had ik eerst goed, maar toen schoot ik te ver door . Gefixte main uit de losse pols / half-lui:

Java:

public static void main(String[] args) {
                int limit = getFileContentsAsInt(args[0]);
                for (int iter = 1; iter <= limit; iter++) {
                        if (Output.HOP.isDivisable(iter)) System.out.println(Output.HOP);
                        else if (Output.HOPPITY.isDivisable(iter)) System.out.println(Output.HOPPITY);
                        else if (Output.HOPHOP.isDivisable(iter)) System.out.println(Output.HOPHOP);
                }
        }
}

[Cartman!]

Heb net hoppity & meepmeep maar even ingezonden in php om te kijken of t werkt.

[Davio]

Cartman! schreef op dinsdag 04 januari 2011 @ 15:56:
Heb net hoppity & meepmeep maar even ingezonden in php om te kijken of t werkt.

Ok, kun je hier dan verslag doen als het succesvol is verlopen?

[Cartman!]

Uiteraard laat ik t weten Ik begreep dat t uren kan duren voordat je iets terugkrijgt dus ik wacht geduldig af...

krijg net m'n reply...

code:

Dear submitter,

Thank you for your submission of a puzzle solution to Facebook! Unfortunately, your solution to the hoppity puzzle (received on January 4, 2011, 6:50 am) could not be built and/or run. For security reasons, I cannot give out exact errors. Please double check your submission for the following things:

- Due to a bug in Microsoft Exchange 2010, if your email is sent with the header:

Content-Disposition: inline

it will not be readable by the robot. Please send your solutions without inline attachments. Some web mail systems such as Yahoo! Mail and Google Mail send attachments as inline by default. Hotmail currently does not send attachments inline.

- If you compressed your solution, it needs to be compressed either as a .zip file, a .tgz file, .tar.gz, or a .tar.bz2 file.

- Furthermore, if your solution was submitted as a compressed file, please make sure that the executable file or Makefile/build.xml uncompresses into the same directory as the compressed file. The robot does not search arbitrary sub-directories!

- If your email system used a digital signature, it may not be understood by our system. Try submitting your submission without a digital signature.

- If you used a compiled language, check that your submission includes a Makefile or an Ant build.xml file that can be used with the commands 'make' or 'ant'. Make sure your Makefil/build.xml file is in the top level directory, and not in a sub-directory (sub-directories are acceptable for source code organization).

- Was your solution written in one of the accepted languages and versions? See http://www.facebook.com/careers/puzzles.php for the complete list.

- The final executable result needs to be a file with the exact name of 'hoppity'. A common error is leaving file extensions on script solutions. Do not worry about file permissions, I will do that for you. Make sure the executable named after the puzzle keyword is not in a sub-directory.

If nothing else works, try creating a discussion at the Facebook Puzzle Master Page at http://www.facebook.com/PuzzleMaster and asking your question.

Sincerely,
-The puzzle robot

Ik heb gestuurd met Gmail dus dan zal ie t wel inline gestuurd hebben. Ik zal de boel eens zippen en nogmaals insturen dan, hopelijk verstuurt ie t dan wel goed

update: de file gezipt insturen werkt ook niet Ik heb nu een file zonder extensie de hoppity heet ingezipt gestuurd.

[ Voor 93% gewijzigd door Cartman! op 04-01-2011 18:12 ]

[Davio]

OK, keep us posted.

Wat betreft thrift:

Ik heb van Simon Says de trhift-file gedownload en met behulp van de thrift compiler voor Windows (v 0.5) kreeg ik toen 2 PHP-bestanden (--gen php): SimonSays.php en simonsays_types.php.

Maar hoe nu verder? Moet ik zelf een PHP-file maken die deze include? En dan een klasse SimonSaysClient aanmaken en daar mee het één en ander doen?

[Cartman!]

Het schijnt dus dat je helemaal niet via GMail kunt meedoen Moet je eerst een mailclient installeren om via Gmail te gaan insturen, wat een gezeik

Gestuurd via Outlook:

code:

Dear submitter,

Thank you for your test submission of a puzzle solution to Facebook! After running your solution to hoppity (received on January 5, 2011, 1:41 am), I have determined it to be correct. Since your test has been successful, you are all set to try one of the other puzzles. Best of luck!

Sincerely,
-The puzzle robot

Jeuj...nu eens uitzoeken hoe dat liar liar werkt

[ Voor 58% gewijzigd door Cartman! op 05-01-2011 11:30 ]

[Tharulerz]

Zijn er mensen zich aan het voorbereiden op de Facebook Hacker cup?

[Soultaker]

Ik niet echt, ik zie wel wat het wordt. De kwalificatieronde kan sowieso nooit heel erg spannend worden.

[Soultaker]

Bump! Nog iemand meegedaan/van plan mee te doen? Kwalificeren kan nog tot maandagavond!

[Tharulerz]

Had de eerste puzzel gedaan (Double Squares), maar niet binnden de 6 minuten ingeleverd... PHP performance probleempje (wie maakt het dan ook in PHP hoor ik je al denken).

In C# deed exact hetzelfde algoritme 12 seconden over de opgave...

Ik zal nog wel 1 of beide andere oplossen, zodat ik gekwalificeerd ben, maar ik vrees dat ik in de volgende rondes toch nooit kan winnen als ik niet 3 op 3 op de kwalificaties heb gehaald?

[Soultaker]

Da's jammer! Het is natuurlijk belangrijk om vóór je de invoer downloadt, een inschatting te maken van hoeveel tijd je maximaal nodig zal hebben. PHP hoeft niet problematisch te zijn. Ter vergelijking: mijn Python-code heeft nog geen seconde nodig.

En "winnen"... tja, ik verwacht ook niet het tot aan de laatste ronde te redden (laat staan te winnen), maar meedoen is op zich al leuk, wat mij betreft.

[ Voor 24% gewijzigd door Soultaker op 08-01-2011 22:10 ]

[Megamind]

Ik ga denk ik ook even kijken, toch rustig op werk

[Tharulerz]

Soultaker schreef op zaterdag 08 januari 2011 @ 22:09:
Da's jammer! Het is natuurlijk belangrijk om vóór je de invoer downloadt, een inschatting te maken van hoeveel tijd je maximaal nodig zal hebben. PHP hoeft niet problematisch te zijn. Ter vergelijking: mijn Python-code heeft nog geen seconde nodig.

En "winnen"... tja, ik verwacht ook niet het tot aan de laatste ronde te redden (laat staan te winnen), maar meedoen is op zich al leuk, wat mij betreft.

De opgave was zo simpel en mijn tests waren zo snel dat ik niet eens op performantie bezig was (ik sla bijvoorbeeld bij double squares niet elk kwadraat op in een array, dus ik ga ze elke keer opnieuw berekenen). Als je dat doet samen met nog wat optimalisaties ga je vlot onder de seconde denk ik.

[Tharulerz]

Net dan maar studious student gedaan, tijd tussen downloaden input file en submitten: 10 sec

Edit: sorry voor dubbel post, zag niet dat ik laatste was

[ Voor 24% gewijzigd door Tharulerz op 08-01-2011 22:20 ]

[Soultaker]

Nice, dat is het betere werk. Nog steeds met PHP, of nu toch maar direct voor C# gegaan? (Lijkt me sowieso een betere taal voor dit soort problemen.)

[Pete]

Ik zit nu net naar Studious Student te kijken en zit me te verbazen over hoe simpel het is. Ik zit zo te twijfelen of er niet een of andere valstrik in zit....

[Tharulerz]

Soultaker schreef op zaterdag 08 januari 2011 @ 22:23:
Nice, dat is het betere werk. Nog steeds met PHP, of nu toch maar direct voor C# gegaan? (Lijkt me sowieso een betere taal voor dit soort problemen.)

Direkt voor C#.

Het enige leuke aan PHP is dat alles net iets sneller geschreven is (dynamische arrays, strings niet moeten casten naar ints, etc).

en pete:
dat gedacht had ik ook, maar het is dan ook een kwalificatieronde. Heb algoritme geschreven, test erop uitgevoerd, resultaat kwam overeen met opgave. Dan testset gemaakt van maximum woordsets van maximum woorden, en performance zat nog onder de seconde.

Dan zo snel mogelijk klikken en submitten

[Megamind]

Ik ben bezig met C# nu, maar ik de uitleg is raar bij de eerste puzzel:

or example, 10 can only be written as 32 + 12 (we don't count 12 + 32 as being different).

Dus dat betekent: 10 heeft 1 oplossing?

Staat er een voorbeeld onder:
5
10
25
3
0
1

wordt

1
2
0
1
1

Er mist dus zowiezo al 1 output en bij 10 staan er 2 output

Edit: oh wacht beter lezen Eerste getal is het aantal testcases.

[ Voor 8% gewijzigd door Megamind op 08-01-2011 22:33 ]

[Pete]

Tharulerz schreef op zaterdag 08 januari 2011 @ 22:28:
[...]
en pete:
dat gedacht had ik ook, maar het is dan ook een kwalificatieronde. Heb algoritme geschreven, test erop uitgevoerd, resultaat kwam overeen met opgave. Dan testset gemaakt van maximum woordsets van maximum woorden, en performance zat nog onder de seconde.

Dan zo snel mogelijk klikken en submitten

Ik heb een kleine valstrik gevonden. Weet je zeker dat alle testcases goed waren?

[Tharulerz]

Bah. Net nagekeken, nu je het zegt, zie ik hem. Heb hem dus fout.

Had men eigen programmeerniveau wel hoger ingeschat Me zo laten vangen

[ Voor 62% gewijzigd door Tharulerz op 09-01-2011 01:43 ]

[Soultaker]

@Tharulerz: misschien is het sportief om die link weg te halen tot de ronde voorbij is?

En nu rest je dus nog Peg Game om je te kwalificeren. Wel het lastigste probleem in de set.

[ Voor 36% gewijzigd door Soultaker op 08-01-2011 23:17 ]

[Megamind]

De eerst heb ik ook gesubmit, kreeg wel een rare list, had bijna geen antwoorden op de 25 en 100 na in de lijst

[webschaapje]

Vanmiddag alle puzzels opgelost in Java. Ze vielen me nog behoorlijk mee. Maar de organisatie kan nog wel wat beter. Ik dacht dat je ook source code moest sturen, maar dat bleek dus niet het geval. Verder is 6 minuten zonder herkansing een beetje... onhandig.

Double Squared
Duurde maar 45ms om op te lossen. Deze kun je met wat simpel rekenwerk supersnel oplossen. Hier heb je helemaal geen DP voor nodig.

Peg Game
Deze was ook niet al te moeilijk op te lossen. Het runnen van m'n input file duurde hier helaas wel 20 seconden, maar ben er verder wel tevreden mee.

Studious Student
Was waarschijnlijk de makkelijkste puzzel van allemaal. Het duurde ongeveer 20ms om deze op te lossen.

Nu is het wachten op de resultaten...

[Tharulerz]

Soultaker schreef op zaterdag 08 januari 2011 @ 23:16:
@Tharulerz: misschien is het sportief om die link weg te halen tot de ronde voorbij is?

En nu rest je dus nog Peg Game om je te kwalificeren. Wel het lastigste probleem in de set.

Weggehaald.

Had jij de valstrik wel door dan?

Edit: Net dan toch maar even de Peg Game gesubmit, al was het maar om aan mezelf te bewijzen dat ik door een stomme Facebook kwalificiatieronde kan komen...

Algoritme van peg game doet er iets langer over als een seconde, al bij al best tevreden (als het juist is).

[ Voor 27% gewijzigd door Tharulerz op 09-01-2011 05:14 ]

[Megamind]

Welk algorithme hebben jullie gebruikt voor de peg game, mijn wiskunde is niet zo goed Ik zat te klooien met binomial coefficienten, maar komt niet uit.

Hmm nu al wel wat, alleen nog uitvinden hoe ik die missende pegs kan compenseren.

[ Voor 21% gewijzigd door Megamind op 09-01-2011 13:53 ]

[Anoniem: 341513]

Pffff probleem 1 is heel gemakkelijk druk ik op de knop voor mijn input file te krijgen zie ik direct al dat mijn time expired is...

Bij probleem 2 had ik nog een debug output laten staan bij de output dus die was ook mis. (Wel mijn eigen stomme fout)

Probleem 3 ga ik nu doen. Maar als je 1 van de 3 oplost ben je dan ook door naar de volgende ronde?

[Bv202]

Snel even "Studious Student" gemaakt, lekker simpel

EDIT:
Blijkbaar krijg je punten aan de hand van hoe snel je je antwoord instuurt na de start van de nieuwe ronde. Redelijk lastig als de ronde 's nachts of tijdens de werkuren begint.

En de antwoorden worden waarschijnlijk toch verspreidt, ik wou ff info zoeken over double-square numbers en het eerste de eerste 3 Google-resultaten zijn al een copy-paste van de Facebook-opgave

[ Voor 87% gewijzigd door Bv202 op 09-01-2011 13:45 ]

[Soultaker]

Tharulerz schreef op zondag 09 januari 2011 @ 01:43:
Had jij de valstrik wel door dan?

Als je met "valstrik" de case bedoelt die ook al in de sample data zit, dan wel. Ik denk dat ik alledrie de problemen goed opgelost heb, maar dat zegt alleen dat ik nog geen bugs gevonden heb.

Bv202 schreef op zondag 09 januari 2011 @ 13:31:
Blijkbaar krijg je punten aan de hand van hoe snel je je antwoord instuurt na de start van de nieuwe ronde. Redelijk lastig als de ronde 's nachts of tijdens de werkuren begint.

Volgende rondes duren kort (drie uur ieder volgens de huidige informatie) dus dan heb je dat niet, en voor de kwalificatieronde maakt penalty time überhaupt niet uit.

En de antwoorden worden waarschijnlijk toch verspreid.

Ook dat zal wel meevallen in de latere ronden, waarbij de tijd beperkt is. Mensen die dan meedoen hebben de beschikbare tijd hard nodig om de problemen zelf op te lossen, dus dan zijn ze waarschijnlijk niet bezig ze online te posten, en als je zelf van plan bent oplossingen van internet te plukken moet je ze maar net op tijd zien te vinden en er maar op vertrouwen dat ze daadwerkelijk correct zijn.

[Tharulerz]

De 6 minuten limiet is lifted. Je kan dus als je te laat was (of ik denk ook fout was) nu de juiste solution submitten.

De kwalificatieronde begint meer en meer op een 'klik-en-je-bent-door-ronde' te lijken...

[Pete]

@Tharulerz Waar zie jij dat de 6 minuten limiet weg is? Voor mij staat er nog altijd "Time expired" bij alle opgaven (terwijl ik waarschijnlijk goede antwoorden heb gesubmit). Ook staat daar niets over op de HackerCup pagina.

Edit:
Gevonden!

[ Voor 25% gewijzigd door Pete op 10-01-2011 10:00 . Reden: url gevonden ]

[Anoniem: 341513]

Wanneer krijg je te horen welke oefeningen je allemaal juist/mis had?

[Soultaker]

Sowieso niet voor 1 uur vanacht, want dan eindigt de ronde pas. Bij de Google CodeJam waren de scores dan direct beschikbaar, maar het is maar de vraag of Facebook het net zo goed geregeld heeft.

[Pete]

Net een emailtje gekregen dat ik door ben naar de volgende ronde, ik had ze alledrie goed

[Megamind]

Nice, hoop dat ik ze ook alle 3 goed heb. Kreeg je nog een penaltyscoren?

[Tharulerz]

Ook alle 3 goed hierzo. Niets van score vermeld, maakte ook niet uit voor qualifier.

Zonder de 6 minute time limit had ik er dus toch eentje goed gehad (peg game). Minor minor ego boost \o/

[Pete]

Wat is dit nu weer. Kreeg nu een emailtje dat ik alleen Double Squares goed had. Nog steeds door naar de volgende ronde natuurlijk, maar ik vraag me af wat ze daar bij facebook aan het doen zijn...

spoiler:

Er een rotzooitje van maken

[Soultaker]

Ik kreeg ook twee mailtjes maar wel met dezelfde inhoud. Weet je zeker dat je oplossingen voor de andere twee problemen juist waren?

[Anoniem: 341513]

Ik kreeg 2 mails dat ik niet door ben. (Waarvan ik 1 zeker weet en een andere betwijfel ik...) maar van die derde weet ik 100% zeker dat het juist is. Heeft iedereen 3 mails gekregen?

[Tharulerz]

Ze hadden blijkbaar een fout gemaakt bij de eerste mail, en sommigen hadden teveel juist gekregen. De 2e en laatste mail is definitief

[Pete]

Soultaker schreef op dinsdag 11 januari 2011 @ 17:16:
Ik kreeg ook twee mailtjes maar wel met dezelfde inhoud. Weet je zeker dat je oplossingen voor de andere twee problemen juist waren?

Ik was er vrij zeker van dat Peg Game en Studious Student ook correct waren, maar ik heb het niet met oplossingen van anderen vergeleken.

Tharulerz schreef op dinsdag 11 januari 2011 @ 18:16:
Ze hadden blijkbaar een fout gemaakt bij de eerste mail, en sommigen hadden teveel juist gekregen. De 2e en laatste mail is definitief

Heb je een bron hiervan? Ik kan niets officieels vinden op de hackercup wall...

[Tharulerz]

Ik had het ergens in de reacties op de wall gelezen, geen idee of het officieel was.

Maakt op zich ook niet veel uit, gekwalificeerd is gekwalificeerd

Edit: kunnen we beter de algoritmes niet overlopen die iedereen gebruikt heeft in de 3 opgaven? Kan nog leerrijk zijn

Aftrap: Voor double squares:

- wortel berekenen van het getal, afronden naar beneden
- 2 nested for loops, 1e loop van 0 tot en met wortel (i), 2e loop van i tot en met wortel
- in binnenste loop kijken of (i*i)+(j*j) == getal, zoja combinations++
- en dan wegschrijven naar output file

Iemand die een andere/betere manier had? Enige optimalisatie die ik direct zie in mijn code is de kwadraten bijhouden in een array zodat je niet elk kwadraat opnieuw hoeft te berekenen.

[ Voor 66% gewijzigd door Tharulerz op 11-01-2011 19:21 ]

[Megamind]

Tharulerz schreef op dinsdag 11 januari 2011 @ 19:17:
Ik had het ergens in de reacties op de wall gelezen, geen idee of het officieel was.

Maakt op zich ook niet veel uit, gekwalificeerd is gekwalificeerd

Edit: kunnen we beter de algoritmes niet overlopen die iedereen gebruikt heeft in de 3 opgaven? Kan nog leerrijk zijn

Aftrap: Voor double squares:

- wortel berekenen van het getal, afronden naar beneden
- 2 nested for loops, 1e loop van 0 tot en met wortel (i), 2e loop van i tot en met wortel
- in binnenste loop kijken of (i*i)+(j*j) == getal, zoja combinations++
- en dan wegschrijven naar output file

Iemand die een andere/betere manier had? Enige optimalisatie die ik direct zie in mijn code is de kwadraten bijhouden in een array zodat je niet elk kwadraat opnieuw hoeft te berekenen.

Ik maakte bij elke run een nieuwe kwadratenlist waarna ik de dubbele eruit verwijderde, dubbele telde namelijk niet mee.

Maar had die wel fout Had volgens mij alleen Studious Student goed, de rest stond er niet bij.

[ Voor 4% gewijzigd door Megamind op 11-01-2011 20:01 ]

[Pete]

Studious Student (van welke de tweede email zei dat ik die niet goed had) had ik opgelost met een bijna oneliner in python:

Python:

"".join(sorted(words,key=lambda x:x+x[0]*10))

Iemand die hier iets fouts aan ziet?

[Megamind]

Er zat een uitzondering in op geloof ik de 4e testcase Denk dat een boel mensen deze niet goed hebben.

[Soultaker]

Tharulerz schreef op dinsdag 11 januari 2011 @ 19:17:
Edit: kunnen we beter de algoritmes niet overlopen die iedereen gebruikt heeft in de 3 opgaven? Kan nog leerrijk zijn

Sure. Bij Double Squares gaat het om het vinden van oplossingen van de vergelijking N = a² + b² waarbij N gegeven wordt en a en b geheeltallig zijn. Dat is inderdaad een kwestie van een getal a proberen, en dan kijken of N - a² een kwadraat oplevert. Aangezien je a kwadrateert hoef je niet meer dan √N te proberen. Checken of een getal een kwadraat is kan op verschillende manieren; ik doe het simpelweg door te worteltrekken en af te ronden. Dat levert een geheel getal b op. Als vervolgens a² + b² = N dan hebben we een nieuwe manier gevonden om een double square te maken (mijn code).

Peg Game is een simpel voorbeeld van dynamic programming. Als je het grid handig geparset hebt, dan is het eenvoudig om aan elke cel op de onderste rij de kans toe te kennen dat 'ie tot het doel leidt: die is 1 voor kolom K en 0 voor alle andere cellen. Nu kun je de kansen voor de rij erboven eenvoudig berekenen. Immers, als een cel leeg is, dan neem je de kans van de cel eronder over. Zit er echter een spijker, dan neem je het gemiddelde van de cel rechtsonder en linksonder (tenzij je aan de rand zit, dan maar één van de twee). Zo loop je van onder naar boven door je grid, en uiteindelijk heb je de kansen voor alle kolommen bovenaan het grid. Daar moet je dan het maxium in vinden.

(Een fout in de vraagstelling was overigens dat er niet gespecificeerd was wat er moest gebeuren als er meerdere kolommen met dezelfde maximale kans zijn. De voorbeeldinvoer, waar dat ook al in voor kwam, suggereerde dat je dan de meest linker kolom moest nemen.)

Verder was het vooral prutsen met rij/kolom-coördinaten. (mijn code).

Tenslotte Studious Student. Dit probleem is moeilijker dan het lijkt, omdat je niet gevraagd wordt om de strings te sorteren en dan te concateneren, maar de minimale concatenatie te geven. Zoals ook al uit de testinvoer bleek verschillen die twee interpretaties als er een woord in de invoer zit, die het begin van een ander woord vormt. Bijvoorbeeld "zuur" < "zuurkool", maar "zuurkoolzuur" < "zuurzuurkool".

Wie hierdoor een foute oplossing inzond, moet zich schamen, want deze case werd al in de voorbeeldinvoer gegeven. De les voor de volgende ronde is dus om pas in te zenden nadat je hebt gecontroleerd dat je programma in ieder geval voor de voorbeeldinvoer (en liefst ook voor andere tricky cases die je zelf kunt verzinnen) het juiste antwoord geeft.

Aangezien het aantal woorden vrij laag was, kon je voor dit probleem simpelweg alle mogelijke concatenaties uitproberen en de minimale pakken. (mijn code)

Een leuke uitbreiding van dit probleem (en een leuke voorbereiding voor volgende ronde): hoe zou je het aan kunnen pakken als er niet slechts negen, maar (zeg) een stuk of honderd woorden van elk (zeg) maximaal honderd letters gegeven zouden worden? Ik denk dat er een simpel en efficiënt algoritme is, maar het bewijs dat het ook correct is, is lastig (dat wil zeggen: ik heb het zelf nog niet volledig weten te bewijzen!)

[Tharulerz]

Om op je uitbreidingsvraag te antwoorden, ik zag deze code op een blog staan:

C#:

Arrays.sort(words, new Comparator<String>() {
  int compare(String a, String b) {
    return (a + b).compareTo(b + a);
  }
});
String s = "";
for (String w : words) s += w;
System.out.println(s);

Lijkt te doen wat het moet?

[Soultaker]

Dat is inderdaad de aanpak die ik ook bedacht had. Nu nog een bewijs van correctheid? (Het werkt overigens al wel op de Facebook test data, maar die is niet zo uitgebreid dat dat echt overtuigend is.)

[ Voor 39% gewijzigd door Soultaker op 11-01-2011 21:36 ]

[Xuj]

Disclaimer: Arme ik had maar de tijd om er eentje te maken. Die was overigens fout omdat ik mijn testdata er nog voor had staan...

Voor Double Squares:

Aangezien er al een bovenlimiet vastgesteld was, had ik in python een dictionary gegenereerd met getallen tot aan wortel 2.147.483.647, met hun kwadraten.

Vervolgens was het kijken of het kijken of n - kwadraat in mijn dict stond.

[Pete]

Er is nu een scorebord gepubliceerd. Ik ben verbaasd dat minder dan 6000 mensen gekwalificeerd zijn, alhoewel ik denk dat een hoop afvallers slachtoffer zijn van een niet zo goed werkende interface.

[ Voor 16% gewijzigd door Pete op 12-01-2011 11:27 ]

[RayNbow]

Ik doe niet mee, maar zijn er Tweakers die een functionele taal gebruiken voor het oplossen van de puzzels?

Soultaker schreef op dinsdag 11 januari 2011 @ 20:49:
[...] om een double square te maken (mijn code).

* RayNbow kon het btw niet laten om dit stukje Python van Soultaker om te zetten naar Haskell... (pastebin)

[Davio]

Als dit topic een beetje loopt, zal ik de TS wel een keer vervangen met iets informatievers en met links naar soortgelijke challenges voor wie dat leuk vindt.

[Xuj]

Davio schreef op donderdag 13 januari 2011 @ 09:30:
Als dit topic een beetje loopt, zal ik de TS wel een keer vervangen met iets informatievers en met links naar soortgelijke challenges voor wie dat leuk vindt.

Dat lijkt me wel interessant. Is het dan niet beter om een nieuwe thread te starten?

Waar ik me momenteel mee bezig houd, is Project Euler. Nu weet ik niet of daar al een topic of iets voor is, maar zulke problemen zijn vrij leuk om te maken.

Het archief van Google CodeJam is ook wel interessant.

[Davio]

Xuj schreef op donderdag 13 januari 2011 @ 16:29:
[...]


Dat lijkt me wel interessant. Is het dan niet beter om een nieuwe thread te starten?

Waar ik me momenteel mee bezig houd, is Project Euler. Nu weet ik niet of daar al een topic of iets voor is, maar zulke problemen zijn vrij leuk om te maken.

Het archief van Google CodeJam is ook wel interessant.

Meh, misschien een nieuw topic, kan altijd, zie het wel.

Ik heb zelf ook een stuk of 60 van die Project Eulers gedaan, is wel leuk, eerst de oplossing hacken en dan iets elegants verzinnen.

[Soultaker]

RayNbow schreef op woensdag 12 januari 2011 @ 17:16:
Ik doe niet mee, maar zijn er Tweakers die een functionele taal gebruiken voor het oplossen van de puzzels?

Ik heb het wel eens overwogen, maar uiteindelijk kies ik zelf meestal toch voor C++, omdat ten eerste de performance van functionele talen te wensen over laat (bij sommige constructies tenminste), ten tweede omdat het paradigma gewoon beperkender is (wat voor goed ontworpen programma's geen echt probleem is, maar als het er om gaat ad-hoc een programma in elkaar te hacken voor éénmalig gebruik, dan is dat in een imperatieve taal toch vaak makkelijker) en ten derde omdat ik zelf niet genoeg ervaring heb met functioneel programmeren om het net zo snel te doen als in C++. Dat laatste is natuurlijk persoonlijk en geen tekortkoming van functionele talen en sich.

Ik heb in de kwalificatieronde van de Google CodeJam wel Haskell gebruikt voor Fair Warning:

Haskell:

solve :: [Integer] -> Integer
solve a = let k = foldl1 gcd [j-i | i<-a, j<-a, i<j] in mod(k - mod (head a) k)k

doCase c = getLine >>= (\line -> let args = drop 1 (map read (words line))
              in putStrLn("Case #"++show c++": "++show (solve args)))

main = getLine >>= (\line -> mapM_ doCase [1..read line])

(Zoals je ziet kende ik interact/lines/unlines nog niet.)

En ik heb een jaar eerder een inzending in Clean gedaan. Maar dat zijn toch minder serieuze inzendingen omdat in de kwalificatieronde geen tijdlimiet geldt (en je dus rustig na kunt denken hoe je een probleem zo mooi mogelijk op kan lossen).

Ik vind het wel leuk om te zien als mensen met onconventionele talen een goed resultaat weten te boeken. In de CodeCup van dit jaar maakt Leon Schoorl bijvoorbeeld goede kans op een plek in de top 10 met een speler geschreven in Haskell, wat best een goede prestatie is, aangezien runtime performance en geheugengebruik best relevant zijn voor de speelsterkte.

[Tharulerz]

Hoeveel tweakers zijn er nu eigenlijk in de volgende ronde? 4? 5?

En zijn er mensen die 1 specifieke subronde hebben uitgekozen, of gaan jullie ze allemaal proberen tot je door bent?

Sowieso lijkt me de kans om te kwalificeren voor ronde 2 vrij groot, daar er maar een kleine 6000 gekwalificeerd zijn voor ronde 1, en waarschijnlijk niet eens iedereen meedoet aan ronde 1.

[Soultaker]

Tharulerz schreef op vrijdag 14 januari 2011 @ 19:11:
Hoeveel tweakers zijn er nu eigenlijk in de volgende ronde? 4? 5?

Zoiets misschien... volgens statistieken elders zouden er minstens 21 Nederlanders gekwalificeerd moeten zijn, maar die zitten natuurlijk niet allemaal op GoT. Misschien leuk om elkaar toe te voegen op Facebook voor scorebordpowers? (Ik heb m'n profiel speciaal aangemaakt voor de HackerCup in ieder geval. Weet niet of andere mensen privacygevoelige info op Facebook hebben.)

Ik ga zo in ieder geval wel de eerste ronde proberen. Succes gewenst aan de verdere deelnemers

[Megamind]

Ik zit er al klaar voor

http://www.facebook.com/h...php?round=144428782277390

Ben benieuwd wat we krijgen:
After the Dance Battle
Power Overwhelming
First or Last

[ Voor 36% gewijzigd door Megamind op 15-01-2011 16:08 ]

[Soultaker]

Heuh? Hoe heb je die link gevonden?

edit:
Ahh, de wall. Aan het werk!

edit:
Ok, wat een prutsers bij Facebook. Submissions werken de helft van de tijd niet, bij het eerste probleem is de testinvoer nogal incompleet, bij het tweede probleem klopt er niets van de sample invoer/uitvoer (prove me wrong?) en nu cancellen ze de hele ronde 20 minuten voor het einde. Wat een zooitje. Ik heb nog nooit zo'n grootschalige programmeerwedstrijd zó slecht georganiseerd zien worden.

[ Voor 112% gewijzigd door Soultaker op 15-01-2011 18:45 ]

[Tharulerz]

Given the high rate of submission failures we are experiencing, we are shutting down the first subround a little early. Check back here before the next subround to see whether it will be held on schedule and who needs to plan to compete in it.

Epic Fail = fail

Ik was zelf nog niet gekwalificeerd, ik zag dat Soultaker al wel gekwalificeerd was (geen idee of dat nu nog geldig blijft).

Ik ben bezig aan het Poweroverwhelming probleem, ik kon de vertex van de vergelijking vinden, maar van daaruit naar het gehele punt gaan was nogal moeilijk blijkbaar

[Soultaker]

Volgens mij klopt dat probleem ook helemaal niet. In ieder geval kan ik de uitvoer niet reproduceren. Verder weet ik niet of 't jou opgevallen is, maar ze hebben de tekst van in ieder geval het tweede en misschien ook het derde probleem stilzwijgend veranderd tijdens de contest. Lekker verwarrend als je de tekst van vóór de wijziging nog in je hoofd hebt.

Ik had trouwens twee problemen opgelost (eerste en derde). In geen van beide gevallen kreeg ik een respons van de server. Ik was daar al pissed over, maar tien minuten na inzending stond de ene opeens op het scorebord. Van de andere heb ik nog niets teruggezien.

Ben benieuwd of we 't vanavond opnieuw mogen proberen. Ik hoop dat het systeem dan wat betrouwbaarder werkt, maar ik betwijfel of ze veel bugs kunnen fixen in een paar uur, zeker als je ziet dat het nu al zo'n rommetlje is.

[Tharulerz]

Ja toen ik vlak voor het einde checkte hoeveel mensen het tweede probleem juist hadden, waren dat er heeeeeel weinig. Terwijl het wiskundig redelijk simpel is...
Maarja, als ik mijn output niet kan laten matchen met die van hun, dan denk je dat de fout bij mij ligt...

Heb je een voorbeeld van die probleemomschrijving verandering? Niet gemerkt iig...

[Soultaker]

Eerst was de vraag om het aantal warriors te outputten. Een klein verschil, maar dan klopt de voorbeelduitvoer niet. Als je daar eenmaal achter bent heb je een groter probleem; je weet dan niet welke interpretatie je aan moet houden: W en G in de invoer omdraaien, of inverse van de uitvoer geven? Dat verschil is relevant voor het afronden (je moest immers, bij gevallen met gelijke damage, de voorkeur geven aan méér warriors).

Vooralsnog ga ik er uit dat de voorbeelduitvoer onder geen enkele zinnige interpretatie correct is. Ik ben wel benieuwd wat mensen die het probleem hebben ingestuurd (want dat zijn er wel enkelen) er precies mee gedaan hebben.

Ik vind het sowieso heel slecht dat nu menig deelnemer z'n tijd heeft verspild aan een probleem wat gewoon niet klopt, terwijl ze ondertussen ook aan een ander probleem hadden kunnen werken.

[Tharulerz]

Ja ik ben er altijd van uitgegaan dat ik het aantal warriors moest outputten... Geen wonder dat het niet klopte.

Achja, geen rondes meer tot volgend weekend, eerlijkste zou zijn om alles te whipen...

[Megamind]

Tharulerz schreef op zaterdag 15 januari 2011 @ 19:54:
Ja ik ben er altijd van uitgegaan dat ik het aantal warriors moest outputten... Geen wonder dat het niet klopte.

Achja, geen rondes meer tot volgend weekend, eerlijkste zou zijn om alles te whipen...

Same here, al dat ik het wiskunde niet echt voor elkaar kreeg Naja denk dat ik er maar mee kap, gezeur de hele tijd hiermee.

[Dennis Degryse]

Mijn oplossingen voor de Qualification Round: http://dennisdegryse.be/blog/read/ref/18 . De oplossingen voor Online Round I - Subround I post ik asap.

[Soultaker]

Hier alvast een oplossing voor het derde probleem (First or Last) in GolfScript:

code:

[~]({
    ((:o;(.+/(2/              # parse input into list of pairs of integers
    {.~(*8.?*\~\(*/}$         # sort integers as required
    .o<{0=}%\o>{1=}%+         # select probabilities to be used
    [.{(}%{*}*\{*}*]          # calculate numerator & denominator (unnormalized)
    .~{.@\%.}do;              # calculate GCD of N and D
    :f;{f/}%                  # normalize fraction
    '/'*n                     # format output
    @[]*                      # restore flattened input data for next case
}\*

(Kan natuurlijk ook op één regel van 99 karakters.)

[Dennis Degryse]

Soultaker schreef op zondag 16 januari 2011 @ 19:18:
Hier alvast een oplossing voor het derde probleem (First or Last) in GolfScript:

code:

[~]({
    ((:o;(.+/(2/              # parse input into list of pairs of integers
    {.~(*8.?*\~\(*/}$         # sort integers as required
    .o<{0=}%\o>{1=}%+         # select probabilities to be used
    [.{(}%{*}*\{*}*]          # calculate numerator & denominator (unnormalized)
    .~{.@\%.}do;              # calculate GCD of N and D
    :f;{f/}%                  # normalize fraction
    '/'*n                     # format output
    @[]*                      # restore flattened input data for next case
}\*

(Kan natuurlijk ook op één regel van 99 karakters.)

mooie oplossing en matcht ook met mijn oplossing op 1 bug na: wanneer de kans 0 is print die van jouw niets in plaats van "0".
EDIT: nvm, ik gaf een verkeerde inputfile mee.

[Soultaker]

Je hebt wel gelijk: als de kans op een crash bij inhalen 1 is, dan krijg je een deling door nul. Ik heb dat niet gefixt omdat me niet duidelijk was of dat een fout is in de vraagstelling was, want in de testdata komt kans 1/1 namelijk niet voor, terwijl 1/2, 1/3, 1/4 enz. wel voorkomen, dus het lijkt er op dat ze die case bewust achterwege hebben gelaten.

De GolfScript code is gebaseerd op een oplossing in Haskell:

Haskell:

import List

solve (r:t:p) = show num ++ "/" ++ show den
  where
    (a,b)           = splitAt (read r - 1) $ sortBy cmp $ pairs $ map read p
    pairs []        = []
    pairs (a:b:c)   = (a,b):pairs c
    cmp (a,b) (c,d) = compare (a*(b-1)*d*(c-1)) (c*(d-1)*b*(a-1))
    (num, den)      = foldl mult (1,1) $ map fst a ++ map snd b
    mult (a,b) c    = norm (a*(c-1), b*c)
    norm (a,b)      = (div a f, div b f) where f = gcd a b

main = interact $ unlines.map(solve.words).tail.lines

Daar omzeil ik het probleem door kruislings te vermenigvuldigen bij het vergelijken van twee breuken (zie cmp) maar in Golfscript werkt dat niet, omdat je wel kunt sorteren met een bepaalde key per item, maar niet met een algemene functie die twee elementen vergelijkt.

En als ik toch code aan het posten zijn, dit is dezelfde oplossing in Python:

Python:

from fractions import Fraction
from operator import mul

def solve(R, T, *PQ):
    PQ = [1-Fraction(1, n) for n in PQ]
    PQ = zip(PQ[0::2], PQ[1::2])
    PQ.sort(key=lambda (p,q): q/p)
    return reduce(mul, [ PQ[i][i>=R-1] for i in range(T) ])

if __name__ == '__main__':
    from sys import stdin
    for c in range(int(stdin.readline())):
        print solve(*map(int, stdin.readline().split()))

Groot voordeel van Python voor dit soort problemen is standaard support voor breuken met willekeurig grote noemer en teller. Dat maakt het allemaal een stuk eenvoudiger. edit: Deze Python code is om dezelfde reden fout, ware het niet dat het problematische geval niet voorkomt in de officiële invoer.

[ Voor 79% gewijzigd door Soultaker op 17-01-2011 00:51 ]

[Dennis Degryse]

Bij mijn input kwam er een paar (*, 1) wel voor, maar niet het paar (1, 1). In het geval (*, 1) moet je sowieso deze bocht als 'normale' bocht nemen en in het geval (1, *) neem je die sowieso als inhaalbocht. Zij zijn dus beide extrema in de gesorteerde lijst (ratio 0 en oneindig). Thans, zo heb ik ze behandeld in mijn comparison-functie.

Hieronder vind je mijn implementatie in PHP. Helaas vertraagt het wat door de BC Math operaties (voor integers > 2^64) en heb ik een eigen GGD-functie moeten implementeren om de breuk te vereenvoudigen:

code:

#!/usr/bin/php -q
<?
$fd = fopen($argv[1], 'r');
$n = intval(fgets($fd));
$den = $nom = 1;

function gcd ($a, $b) {
    if (bccomp($a, '0') == 0)
        if (bccomp($b, '0') == 0)
            return 1;
        else
            return $b;

    while (bccomp($b, '0') != 0)
        if (bccomp($a, $b) > 0)
            $a = bcsub($a, $b);
        else
            $b = bcsub($b, $a);

    return $a;
}

function cmp ($a, $b) {
    if ($a[0] == 1 || $b[1] == 1)
        return 1;

    if ($b[0] == 1 || $a[1] == 1)
        return -1;

    $a0 = ($a[0] - 1) / $a[0];
    $a1 = ($a[1] - 1) / $a[1];
    $b0 = ($b[0] - 1) / $b[0];
    $b1 = ($b[1] - 1) / $b[1];

    return ($b0 / $b1) < ($a0 / $a1) ? -1 : 1;
}

function turn ($t) {
    global $den, $nom;

    $den = bcmul($den, bcsub($t, 1));
    $nom = bcmul($nom, $t);

    $g = gcd($den, $nom);
    
    $den = bcdiv($den, $g);
    $nom = bcdiv($nom, $g);
}

while ($n-- > 0) {
    $parts = preg_split('/\s+/', trim(fgets($fd)));
    $R = $parts[0];
    $T = $parts[1];
    $P = array();
    $den = $nom = 1;

    foreach (range(0, $T-1) as $i)
        $P[] = array(intval($parts[($i << 1) + 2]), intval($parts[($i << 1) + 3]));

    usort($P, 'cmp');
    $P = array_reverse($P);

    for ($i = $T - $R + 1; $i < $T; $i++)
        turn($P[$i][0]);

    for ($i = 0; $i < $T - $R + 1; $i++)
        turn($P[$i][1]);

    if ($den == '0')
        echo "0\n";
    else
        echo "$den/$nom\n";
}

[ Voor 69% gewijzigd door Dennis Degryse op 16-01-2011 23:51 ]

[Soultaker]

Nice. PHP lijkt me wel een rottaal voor dit soort problemen.

Die gcd() functie lijkt me in z'n huidige vorm onnodig traag. Met behulp van de modulo operator heb je minder iteraties nodig:

PHP:

while (bccomp($b, '0') != 0) list($a, $b) = array($b, bcmod($a, $b));

(Het is me trouwens niet duidelijk hoe efficient die list(..) = array(..) constructie in PHP nu precies is.)

Verder vind ik je comparison-functie maar dubieus: je returnt wel -1 of +1, maar nooit 0, ook al zijn je argumenten gelijk! Dat lijkt me technisch niet correct. Afhankelijk van het gebruikte sorteeralgoritme, zou het kunnen dat je programma nu niet termineert.

[Dennis Degryse]

Soultaker schreef op maandag 17 januari 2011 @ 00:04:
Nice. PHP lijkt me wel een rottaal voor dit soort problemen.

Het klopt dat PHP weinig relevante out-of-the-box structuren bezit, dus je moet af en toe het warm water zelf uitvinden, maar dat vind ik niet zo erg. Uiteindelijk doe ik dit soort opdrachten net om uit te leren.

Soultaker schreef op maandag 17 januari 2011 @ 00:04:
Die gcd() functie lijkt me in z'n huidige vorm onnodig traag. Met behulp van de modulo operator heb je minder iteraties nodig:

PHP:

while (bccomp($b, '0') != 0) list($a, $b) = array($b, bcmod($a, $b));

(Het is me trouwens niet duidelijk hoe efficient die list(..) = array(..) constructie in PHP nu precies is.)

Ik heb recursie uitgesloten om mijn stack te sparen, maar het is inderdaad discutabel.

Soultaker schreef op maandag 17 januari 2011 @ 00:04:
Verder vind ik je comparison-functie maar dubieus: je returnt wel -1 of +1, maar nooit 0, ook al zijn je argumenten gelijk! Dat lijkt me technisch niet correct. Afhankelijk van het gebruikte sorteeralgoritme, zou het kunnen dat je programma nu niet termineert.

usort gebruikt quicksort, dus iirc kan het geen kwaad, maar je hebt zeker een punt.

[Soultaker]

Dennis Degryse schreef op maandag 17 januari 2011 @ 00:23:
Ik heb recursie uitgesloten om mijn stack te sparen, maar het is inderdaad discutabel.

Wat heeft dit met recursie te maken

[Dennis Degryse]

Soultaker schreef op maandag 17 januari 2011 @ 02:09:
[...]

Wat heeft dit met recursie te maken

Mijn fout, ik had je code te snel gelezen... Ze is idd ook iteratief. Het klopt ook dat mijn bcd een bottleneck is, maar de oplossing kwam nog steeds in een 2-tal seconden, terwijl de limiet 6 minuten is.

Ondertussen heb ik ff een benchmark tussen gmp en bc math gedaan en gmp blijkt veel sneller te zijn (volgens mij grotendeels omdat bcmath telkens conversie van - naar strings doet). Daarom heb ik mijn nieuwe implementatie met gmp gedaan.

Mijn oplossingen voor online round I - subround I: http://dennisdegryse.be/blog/read/ref/19 .

[Soultaker]

Mooie post. Je complexiteitsanalyse klopt trouwens niet helemaal. |E| kan veel groter zijn dan 4|V| omdat je van elk gekleurd vakje naar elk ander gekleurd vakje kunt stappen. Bij de simpelste methode is |E| dan ongeveer |V|² oftewel 10⁸, wat best veel is.

Helaas bevat de officiële testdata niet zulke moeilijke cases, anders denk ik dat een heleboel oplossingen niet door de tests gekomen waren. Run je PHP code maar eens op deze drie cases (die mijns inziens gewoon in de officiële data hadden moeten voorkomen, samen met nog wat moeilijke varianten).

Uitdaging: verzin een algoritme voor dit probleem dat wél in O(V) tijd runt.

Trouwens, ik zag dat je voor Studious Student ook de oplossing van sorteren met de regel s-voor-t indien s.t < t.s gebruikte. Heb je daar ook een sluitend bewijs voor? Ik ben er zelf namelijk nog niet helemaal uit; ik denk dat als je kunt bewijzen dat die ordeningsrelatie transitief is (en dus een equivalence relation oplevert) de rest wel kloppend te maken is, maar ik heb nog geen simpel bewijs voor transitiviteit. (Met andere woorden, de vraag is of geldt: s.t < t.s /\ t.u < u.t --> s.u < u.s; of eigenlijk met <= i.p.v <, maar een bewijs voor < helpt ook al.)

[Dennis Degryse]

Soultaker schreef op maandag 17 januari 2011 @ 13:12:
Mooie post. Je complexiteitsanalyse klopt trouwens niet helemaal. |E| kan veel groter zijn dan 4|V| omdat je van elk gekleurd vakje naar elk ander gekleurd vakje kunt stappen. Bij de simpelste methode is |E| dan ongeveer |V|² oftewel 10⁸, wat best veel is.

In het slechtste geval is de tijdscomplexiteit idd veel slechter, daarom dat ik 'gemiddeld' geval zeg

Soultaker schreef op maandag 17 januari 2011 @ 13:12:
Helaas bevat de officiële testdata niet zulke moeilijke cases, anders denk ik dat een heleboel oplossingen niet door de tests gekomen waren. Run je PHP code maar eens op deze drie cases (die mijns inziens gewoon in de officiële data hadden moeten voorkomen, samen met nog wat moeilijke varianten).

Uitdaging: verzin een algoritme voor dit probleem dat wél in O(V) tijd runt.

Door mijn buckets (per kleur) leeg te maken na het bezoeken van 1 knoop van die kleur (zodat ik voor de kinderen in de zoekboom van dezelfde kleur niet meer opnieuw branches naar de andere knopen met die kleur moet controleren) bekom ik O(V). (zie Graph::emptyBucket($v) in mijn aangepaste code). Bedankt voor de aanleiding.

Soultaker schreef op maandag 17 januari 2011 @ 13:12:Trouwens, ik zag dat je voor Studious Student ook de oplossing van sorteren met de regel s-voor-t indien s.t < t.s gebruikte. Heb je daar ook een sluitend bewijs voor? Ik ben er zelf namelijk nog niet helemaal uit; ik denk dat als je kunt bewijzen dat die ordeningsrelatie transitief is (en dus een equivalence relation oplevert) de rest wel kloppend te maken is, maar ik heb nog geen simpel bewijs voor transitiviteit. (Met andere woorden, de vraag is of geldt: s.t < t.s /\ t.u < u.t --> s.u < u.s; of eigenlijk met <= i.p.v <, maar een bewijs voor < helpt ook al.)

Over deze zal ik eens nadenken. Dat bewijs ziet me er op het eerste zicht niet al te moeilijk uit.

[ Voor 10% gewijzigd door Dennis Degryse op 17-01-2011 21:31 ]

[Soultaker]

Dennis Degryse schreef op maandag 17 januari 2011 @ 17:33:
In het slechtste geval is de tijdscomplexiteit idd veel slechter, daarom dat ik 'gemiddeld' geval zeg

Het gaat natuurlijk om het slechtste geval, want als de problem setters hun werk een beetje goed doen (wat bij Facebook tot nu toe niet echt het geval lijkt te zijn) dan stoppen ze ook een paar moeilijke cases in de testinvoer. (Ik blijf erbij dat het gros van de inzendingen af had moeten vallen, op basis van de gegeven probleemstelling.)

Door mijn buckets (per kleur) leeg te maken na het bezoeken van 1 knoop van die kleur (zodat ik voor de kinderen in de zoekboom van dezelfde kleur niet meer opnieuw branches naar de andere knopen met die kleur moet controleren) bekom ik O(V). (zie Graph::emptyBucket($v) in mijn aangepaste code)

Dit is best een mooie oplossing! Je delete dan eigenlijk in één klap een heleboel edges die naar vertices leiden die je al bezocht hebt, wat inderdaad O(V) worst-case complexiteit geeft.

Ik had een andere aanpak in gedachten. Stel je bouwt eerst een graaf van het doolhof waarbij je kleuren negeert. Daarna voeg je voor elke kleur een teleporter-vertex toe. Elk gekleurde vakje krijgt vervolgens een extra edge van en naar de teleporter corresponderend met die kleur, met lengte ½. Vervolgens zoek je gewoon het korste pad. (Aangezien |E| < 6|V| kan dit nu vrij efficiënt.)

Het feit dat je edges nu verschillende lengtes hebben compliceert het systeem enigzins. Behalve simpelweg Dijkstra te implementeren (wat ik tijdens de wedstrijd had gedaan) kun je er op een aantal manieren omheen werken. Bijvoorbeeld door beide edges wel lengte 1 te geven, maar edges vanuit de teleporter niet naar vakjes met de betreffende kleur te leiden, maar juist naar de buren van die vakjes. Dat werkt aangezien een gekleurd vakje nooit een eindpunt is, maar het betekent wel dat je meer edges creëert.

De meest aantrekkelijke oplossing is waarschijnlijk om edges naar de teleporter lengte 0 te geven en van de teleporter lengte 1 (of andersom, natuurlijk) en vervolgens je breadth-first search iets aan te passen: in plaats van een queue waarin je vertices altijd aan het einde toevoegt, gebruik je nu een deque; vertices die je bereikt via een edge met lengte 0 push je voorin de queue in plaats van achterin.

Dit trucje is niet heel bekend, geloof ik, maar het is een methode die werkt om het kortste pad te vinden in alle grafen met binaire lengtes van edges, en nauwelijks moeilijker te implementeren dan een breadth-first search.

[Dennis Degryse]

Soultaker schreef op maandag 17 januari 2011 @ 13:12:Trouwens, ik zag dat je voor Studious Student ook de oplossing van sorteren met de regel s-voor-t indien s.t < t.s gebruikte. Heb je daar ook een sluitend bewijs voor? Ik ben er zelf namelijk nog niet helemaal uit; ik denk dat als je kunt bewijzen dat die ordeningsrelatie transitief is (en dus een equivalence relation oplevert) de rest wel kloppend te maken is, maar ik heb nog geen simpel bewijs voor transitiviteit. (Met andere woorden, de vraag is of geldt: s.t < t.s /\ t.u < u.t --> s.u < u.s; of eigenlijk met <= i.p.v <, maar een bewijs voor < helpt ook al.)

Gegeven:
Zij een woord een positief geheel getal met basis k (in dit geval k = 26). De waarde van een cijfer c op positie n, geteld van rechts (0-based) is dus c·kⁿ. De lexicografische waarde van een woord w = {c₁, c₂, ..., c_n} is dan de som van de waarden van elke c_i waaruit w bestaat of dus de waarde van w als een getal met basis k.
Zij de lengte van een woord a een functie ⁎(a) = max(1, ⎡log_k(a + 1)⎤)
Zij de concatenatie van 2 woorden a en b een functie ◇(a, b) = a·k^⁎(b) + b

lemma 1:
∀ x, y : ◇(x, y) ≤ ◇(y, x) ⇔ (k^⁎(y) - 1) / (k^⁎(x) - 1) ≤ y / x

Bewijs:
∀ x, y : ◇(x, y) ≤ ◇(y, x) ⇔ x·k^⁎(y) + y ≤ y·k^⁎(x) + x
⇔ x·k^⁎(y) - x ≤ y·k^⁎(x) - y
⇔ x·(k^⁎(y) - 1) ≤ y·(k^⁎(x) - 1)
⇔ (k^⁎(y) - 1) / (k^⁎(x) - 1) ≤ y / x

Te bewijzen:
∀ a, b, c: ◇(a, b) ≤ ◇(b, a) ∧ ◇(b, c) ≤ ◇(c, b) ⇒ ◇(a, c) ≤ ◇(c, a)

Bewijs:
∀ a, b, c: (a, b) ≤ ◇(b, a) ∧ ◇(b, c) ≤ ◇(c, b)
⇔ (k^⁎(b) - 1) / (k^⁎(a) - 1) ≤ b / a ∧ (k^⁎(c) - 1) / (k^⁎(b) - 1) ≤ c / b [lemma 1]
⇒ ((k^⁎(b) - 1)·(k^⁎(c) - 1)) / ((k^⁎(a) - 1)·(k^⁎(b) - 1)) ≤ (b·c) / (a·b)
⇒ (k^⁎(c) - 1) / (k^⁎(a) - 1) ≤ c / a
⇔ ◇(a, c) ≤ ◇(c, a) [lemma 1]
q.e.d.

Soultaker schreef op dinsdag 18 januari 2011 @ 01:24:
Het gaat natuurlijk om het slechtste geval, want als de problem setters hun werk een beetje goed doen (wat bij Facebook tot nu toe niet echt het geval lijkt te zijn) dan stoppen ze ook een paar moeilijke cases in de testinvoer. (Ik blijf erbij dat het gros van de inzendingen af had moeten vallen, op basis van de gegeven probleemstelling.)

Ja, er zijn inderdaad veel bugs zowel in de opgaven, de UI en dan heb je ook nog de test-cases die (zoals je aanhaalde) veel lastiger hadden kunnen zijn. Ook had ik in deze ronde al veel moeilijkere opgaven verwacht. Nuja, daarnaast maakt een discussie rond de problemen (zoals hier) het nog steeds interessant.

Ik post binnenkort nog over Power Overwhelm en de equivalente user bin crash puzzel bij hun career puzzles. (beide zijn te reduceren naar een unbound knapsack problem, wat in pseudo-polynomiale tijd op te lossen is via DP)

[ Voor 20% gewijzigd door Dennis Degryse op 18-01-2011 06:50 ]

[Soultaker]

Dennis Degryse schreef op dinsdag 18 januari 2011 @ 03:08:
Zij de lengte van een woord a een functie ⁎(a) = max(1, ⎡log_k(a + 1)⎤)

Als ik je goed begrijp wil je woorden representeren als getallen, waarbij letters a-z cijfers van 0-25 zijn. Die codering behoudt echter geen informatie over de lengte. Bijvoorbeeld "a", "aa" en "aaa" worden allemaal als 0 gerepresenteerd en zouden (volgens deze formule) allemaal lengte 1 hebben. Als dit juist is, dan klopt je lengte-formule dus niet, en de rest van je bewijs ook niet, helaas.

Hoe schrijf je deze tekst trouwens? Ik kan wel wat symbolen als ≤ intypen, maar veel andere symbolen zou ik moeten copy/pasten, of handmatig de Unicode identifiers intypen), en geen van beide werkt heel prettig.

Dennis Degryse schreef op dinsdag 18 januari 2011 @ 03:08:
Ik post binnenkort nog over Power Overwhelm en de equivalente user bin crash puzzel bij hun career puzzles. (beide zijn te reduceren naar een unbound knapsack problem, wat in pseudo-polynomiale tijd op te lossen is via DP)

Een knapsack van grootte 10¹² lijkt me echter niet ideaal. Ik ben wel benieuwd hoe je het oplost.

edit:
Hier is alvast een oplossing van Power Overwhelming:

code:

[~](;3/{~:M;:W;:G;W.+,{M G.+/+W-)}%.{.G*M\-W/*}%.$)\;?=p}/

Fijn aan GolfScript is dat spoiler tags niet nodig zijn.

[ Voor 11% gewijzigd door Soultaker op 19-01-2011 00:00 ]

[Dennis Degryse]

Soultaker schreef op dinsdag 18 januari 2011 @ 17:22:
[...]

Als ik je goed begrijp wil je woorden representeren als getallen, waarbij letters a-z cijfers van 0-25 zijn. Die codering behoudt echter geen informatie over de lengte. Bijvoorbeeld "a", "aa" en "aaa" worden allemaal als 0 gerepresenteerd en zouden (volgens deze formule) allemaal lengte 1 hebben. Als dit juist is, dan klopt je lengte-formule dus niet, en de rest van je bewijs ook niet, helaas.

Je hebt gelijk, eigenlijk moet ik k = 27 en 0 = ongebruikt karakter (vb spatie of eender wat). De afstand tussen de woorden is dan uitgedrukt in basis 27, wat geen probleem is.

Soultaker schreef op dinsdag 18 januari 2011 @ 17:22:Hoe schrijf je deze tekst trouwens? Ik kan wel wat symbolen als ≤ intypen, maar veel andere symbolen zou ik moeten copy/pasten, of handmatig de Unicode identifiers intypen), en geen van beide werkt heel prettig.

Ik heb ze gwn uit gucharmap gehaald, maar in principe zou ik mijn keymap eens moeten aanpassen om enkele symbolen meteen te kunnen typen.

[Soultaker]

Dennis Degryse schreef op woensdag 19 januari 2011 @ 11:10:
Je hebt gelijk, eigenlijk moet ik k = 27 en 0 = ongebruikt karakter (vb spatie of eender wat). De afstand tussen de woorden is dan uitgedrukt in basis 27, wat geen probleem is.

Maar dan correspondeert lexicografische ordening niet meer met ordening van de getallen waar je ze op mapt. Simpel voorbeeld: "b" > "aa", maar 2 < 28.

[Dennis Degryse]

Soultaker schreef op woensdag 19 januari 2011 @ 17:09:
[...]

Maar dan correspondeert lexicografische ordening niet meer met ordening van de getallen waar je ze op mapt. Simpel voorbeeld: "b" > "aa", maar 2 < 28.

Die klopt idd niet omdat ⁎("b") < ⁎("aa"), maar de transitiviteit moet enkel kloppen voor strings van gelijke lengte. Bij de vergelijking is ⁎(◇(a, b)) = ⁎(◇(b, a)) ook steeds het geval.

[Soultaker]

Je hebt gelijk, nu zie ik 'm inderdaad. Dat is wel een mooi bewijs. Je moet er maar op komen!

[Tharulerz]

De source code van alle puzzles van de test ronde van alle deelnemers staat online en is downloadbaar.

Heb even je code gedownload Soultaker, maar een heel framework MET disclaimer speciaal voor de Facebook Hacker cup maakt me duidelijk dat jij dit op een hele andere manier bekijkt als mij

[Soultaker]

Ik denk dat je minder onder de indruk bent als je 'm vergelijkt met m'n template voor de Google CodeJam, want dan zie je dat ik alleen "CodeJam" vervangen heb door "HackerCup" en "Case #" heb weggehaald in de uitvoer.

Heb je trouwens mijn broncode van het derde probleem ("Characters") ook bekeken?
edit: Die is niet in C++, beloof ik je.

[ Voor 8% gewijzigd door Soultaker op 21-01-2011 18:34 ]

[Tharulerz]

Nope, ben niet zon held in c++ dus heb er maar vluchtig een blik op geworpen

[Dennis Degryse]

Soultaker schreef op vrijdag 21 januari 2011 @ 18:30:
Ik denk dat je minder onder de indruk bent als je 'm vergelijkt met m'n template voor de Google CodeJam, want dan zie je dat ik alleen "CodeJam" vervangen heb door "HackerCup" en "Case #" heb weggehaald in de uitvoer.

Heb je trouwens mijn broncode van het derde probleem ("Characters") ook bekeken?
edit: Die is niet in C++, beloof ik je.

Nice, brainf*ck 'k heb gisteren nog een PHP interpreter voor bf geschreven: http://dennisdegryse.be/blog/read/ref/20

[Tharulerz]

Bah. Was vergeten dat het vandaag 1e ronde was. Thuisgekomen toen het nog half uur over was, even problemen bekeken maar zag niet iets dat ik binnen een half uur kon oplossen.

Volgend weekend dan maar

[Dennis Degryse]

Tharulerz schreef op zaterdag 22 januari 2011 @ 21:35:
Bah. Was vergeten dat het vandaag 1e ronde was. Thuisgekomen toen het nog half uur over was, even problemen bekeken maar zag niet iets dat ik binnen een half uur kon oplossen.

Volgend weekend dan maar

Volgende subround is op 25 jan. om 22u.

[Tharulerz]

Dennis Degryse schreef op zondag 23 januari 2011 @ 17:35:
[...]


Volgende subround is op 25 jan. om 22u.

Tnx voor de headsup

Niet dat het iets uitmaakt, want ik zit hier nu al 7 minuten te refreshen maar hun competition is nog altijd niet online...

Prutsers daar

[Megamind]

http://www.facebook.com/h...hp/?round=167482453296629

nog 1 minuut wachten

[Anoniem: 323791]

Soultaker schreef op donderdag 20 januari 2011 @ 17:22:
Je hebt gelijk, nu zie ik 'm inderdaad. Dat is wel een mooi bewijs. Je moet er maar op komen!

Of het ertoe doet,maar ook ik was er niet van op de hoogte.