January 8, 2011

Hacker Cup - Studious Student Submitted

I implemented a two-core Concurrent Sort in Java and cut the time in half to 38 seconds for the worst-case scenario. Proof positive that this is a viable avenue for tackling future sort algorithms depending on how it scales.

Soon I would like to refactor this code to use an arbitrary number of cores and allow for threshold configuration so that I wouldn’t have to spin up 8 threads just to sort a list of < 100, for example.

For now, though, I thought this should be sufficient to solve the problem. I downloaded my official data set from Facebook:

20

9 eavcqvv wyuh mkfq not evhlpur eidqnartht pesgphnnlq t ztvu

9 iccrmcrm mwp sil iccrmcrm ic odo iccrm crm odocrm

9 wjxwgm qdhmzkmpzv uhibo gcikegpzv ceqiwekdx rxegvkc ujjvbv kfit peiawyk

9 nnozzwtf ahkjj wtp t sj htawm ihw egzinwju vn

9 nl jtdmdxu ux nlmnyzdxu mnyz jtdm nlmnyz dxu uxdxu

9 z dvqgfh wqx vnajabkqvs sdwkc dlhcnc ezrcvsc teje gzwwj

9 fujv mzr kgukjmokvz schpxugnef p rjojpzbsro wpobp wl od

9 i hsmh hsmheh xgi eh xg xgeh xnfc ihsmh

9 myrzwdyhv pojiires fbjbkcbtq pzdfuxfh rq ukbom ypkffomyl tdko zbwqkbuu

9 qxwd bejf wfaua rvkorigcm psdflr utgcsj iaolpoazv hmzczeg hqktnql

5 uiuy hopji li j dcyi

9 rgh woqg dmabatgbt qrvpcrx eluunoi sy w wnthqxgkg aimallazuc

6 facebook hacker cup for studious students

5 k duz q rc lvraw

9 r wwwr ndtc ndtclp lpb b wwwb www lp

9 rnnabb ldk ndhn rnnaldk zeabbbb zeabb zea rnna bb

9 m xmnz mlk vlk lk iwkf lkiwkf vm v

9 krqeokrq weo usau krqeo eo zltg krq w zltgkrq

9 o zt da wv brorejctww fu phnej ynrdkylwys ekggrmehcl

9 k itqsgpwze ma yhpncg xtf w m kahula zgbo

I generated the following output:

eavcqvveidqnarthtevhlpurmkfqnotpesgphnnlqtwyuhztvu

crmiccrmcrmiccrmcrmiccrmicmwpodocrmodosil

ceqiwekdxgcikegpzvkfitpeiawykqdhmzkmpzvrxegvkcuhiboujjvbvwjxwgm

ahkjjegzinwjuhtawmihwnnozzwtfsjtvnwtp

dxujtdmdxujtdmmnyznlmnyzdxunlmnyznluxdxuux

dlhcncdvqgfhezrcvscgzwwjsdwkctejevnajabkqvswqxz

fujvkgukjmokvzmzrodprjojpzbsroschpxugnefwlwpobp

ehhsmhehhsmhihsmhixgehxgixgxnfc

fbjbkcbtqmyrzwdyhvpojiirespzdfuxfhrqtdkoukbomypkffomylzbwqkbuu

bejfhmzczeghqktnqliaolpoazvpsdflrqxwdrvkorigcmutgcsjwfaua

dcyihopjijliuiuy

aimallazucdmabatgbteluunoiqrvpcrxrghsywnthqxgkgwoqgw

cupfacebookforhackerstudentsstudious

duzklvrawqrc

blpblpndtclpndtcrwwwbwwwrwww

bbldkndhnrnnabbrnnaldkrnnazeabbbbzeabbzea

iwkflkiwkflkmlkmvlkvmvxmnz

eokrqeokrqeokrqkrqusauweowzltgkrqzltg

brorejctwwdaekggrmehclfuophnejwvynrdkylwyszt

itqsgpwzekahulakmamwxtfyhpncgzgbo

5 seconds. Excellent, I’m happy with that.

Seems there is significant lag between solution submittal and receiving your score for the problem. I could whine on the FB discussion board or…

…move on to the next problem. #1 sounds fun…

————-

UPDATE: 01/10/2011

After completing the other two problems in this round, I’m fairly confident there’s a much better algorithm for solving this one and that Facebook expects you to be using it.

Still, getting my little brute force multi-core proggie to solve this problem in 5 seconds is indeed a hack in every sense.

•