Return to Blog entry

Sorry bit late for this one... Mike 3rd November, 2008 16:48 (UTC)

Tweaked the standard recipe for a pascal triangle to (n+m!/(n!m!)), reduced with mul, adding a twist of xrange, and broke down the factorial into ranges, neutralising some of the original ingredients. Not sure, but looks to me like it is O(max(m,n)) for (m+n)! < 2^32 (I guess I'm running 32 bit python).

Gentlemen, behold…

from operator import mul
def robots(n,m):
    if m>n: n,m = m,n
    f = lambda x,y: reduce(mul, xrange(x, y+1))
    return f(n+1,n+m)/f(1,m)
robots(3,4)
35
robots(3,3)
20
robots(3,2)
10
robots(3,1)
4
robots(2,1)
3
robots(1,1)
2
from datetime import datetime
    now = datetime.now
    def diff_time(l,*args):
        t = now()
        print l(*args)
        print "computed in ", now() - t
diff_time(robots,10000,10000)

22456026627463455415515694361578631475897369657798782436207104320723802203235940 45444472025293862316422309263843389696601194422592336037980842489107531389451830 67228061243365753004045401767907357590223719236481107085677533059823146064411721 93681187633251827746864325250802130901601156739196898621079810423548516709668189 48676564830140501103187863794706664465811607040131101683992056451405543094155968 81192045257194950755760046717491232807285045572996972019178070145268885425760361 18470378276055525828598342427882362626707366034554662195931519990636507498568231 66968850527296485588202270430832568539209738210376363912068348046527593712676598 11427505772544807476299438971671422801497271799066565554271981886574333945418361 50308358303051396165184926951186021468158606652238086331762685717265932839888246 07425355592984356868896869862580500515357846009974598198321288825579426658640907 41300296784147606716047829020298331451316346303828066040752718282387096083805185 59938125070514919086680193980129123694563657623156661695549941913354266446924334 53363187237190602132828961650920658565301500509193119884570874258737247485829216 38561834248644784494721319623803013452498305477047405358502379397889257738752645 79189465882689299078286823261966336991562345818164139048724887285079258548134501 76908651564852721569388770569930287248915922924411545263754812143287478042214444 62106548140647939808062131884402954545402858517601348930111382371018148562087438 23182818573868379199207018908946251088039331767220693364617816835414221210869916 47087652147284822317663570743148764774033648397327468021594942679125884694968969 33220482873144175424902142934965659853560947105210861480168582926998970083275550 14890201287106560140068362161979877564445496330396806077363124062125881758980695 00611632946947799529169692574582589750518632839394752980774225093724027495379809 48403497720032190359684446261573432906760843254941370794087131989046939384496357 14074573773348772167724540333890841426762858069026377974887633534734660668228092 10584101235225998953947938915377769021982654883558206998963272164596600775488971 68038736753812234455741381862166240649624710999180453179510051779716706399687864 26833279792642235676998916656157136110095262994621267969852072457887166556504262 18579366699329579858511381654502622302912582882684792066014962942240394597348645 27078250971883295146643389109097854133625414358546250026346168404283950778958781 12042797102549939420258929456016951706448875632915153682743740635208350688321311 67187474842828579719937909391112117195041857108857239562691726726702643007507039 36260539453563709732771376422241548562034138154076723316764413282679192602420304 06673294215307401936775514746549930174507826483334440902226745856309830081866529 24657628834644834897637100207827867875420310837070750573815531470530524180034731 72433210103167289034560362855928501998613784104111670965280480313942662837729961 54302160273995190260446793500678862174672635245910150205319070484632080634885283 12685913072745794836545662380385834140814999378490244024780995338812025730352455 52967677035865954765024980428390001183836864650931743158095115737690547462906327 11698339487078938130392828166169076780524935447039002152853850584576773075990200 83956655910704396742375774315427582021313456558410563793441233057058025144411029 75761220356971067208077916566882816852128959676178739732568162566065319297788867 02462619112163992436622057393707700463723543742209363638974578987804056244439248 14889011338090769117051737746754985734497557778663312693365179886144225951173871 12808484404044980350049192933273475436831830243021449721797569293129899025832380 46207570349184045603661638408410724410003206755148350792478800640478690156303801 57609814514040932220403437718337488877890778238494014391690425601864031323957135 12002755508247706315045993070165078028538445338833607737712105533862837714698113 78891988423408696327420539060287705573410603368786538008149746155469686623622732 90989476934259302767216729596126488039964396176141919113223267501056191536248753 81836673136731240669290343761763893226758196293085716534596313681073419821393666 80883567415532196938811626772304247849978612437752116754335798540323308368887513 73327882252412206557991081886624898878359998751193051401516964683179243936067892 26218882540132707230871620236291125678879932985762769827777068714942600182166387 57266946612447476317210524100854308904099287406223340892177565428956712622531239 36763801115074889013481254745081915197784943512915677779444963105849446755664215 50639583689477246991008623768710542174597737692057077162673350459922354296684123 62471023705340368190888802183082090240503115366557936583379987907626067141558682 86812188839118472616299802565927495745940284528240254386499939523999520596277132 21218609507041157010653825985576947098265670746121056257149032692621062080383414 88784829720896011331635710139471120839555299812538797379661653036837903411655600 24646236523972553574840278821681074979776329411205810819665855189239707931962605 27072795097442669805862724440051506627839690258416274456873610520741213565601068 97660402825729396801721492570443407048297198797216876082581499654622522450804429 31266857021277237131024139647963633885493260096879685394128359963116428519583664 69493457656947532569982146584238669125469753209777187398797804750441383815874806 89688922158629836761735402738745348620013077521005365886882928287058517574479497 14769417190412694714297744044392104416757585732254330156026932813617502416565242 65346978694032625761844877005998952516848576265562492189804643825458085934175100 72125868276316433289476597111464049465029030006896362851948751983205796984916365 49172232925641059923504741712671910317948432372246260690133335427497606680877732 27363989637814362639532641408614509509972338789240726288995354301271436982173410 07847666568098669001377099498604113130627126602649102916393899823144994347214958 89186429885229838000591785792876272266149104236799504939344487686719027471999185 87069616823680247136104688901372570598945305087528476254954749408718935950084141 8426659486453916640L

computed in 0:00:00.313945

Sorry bit late for this one... Kirit Sælensminde 3rd November, 2008 16:53 (UTC)

Wow!

Do you want a job?


To join in the discussion you should register or log in
Sorry bit late for this one... Kirit Sælensminde 3rd November, 2008 17:00 (UTC)
Kirit Sælensminde said

Wow!

Although technically of course you made the same mistake I did. If the grid is 1x1 you're already at the destination — you need to subtract 1 from each of m and n before doing the next part of your calculations. I have a very nasty feeling that this ruins some of the clean symmetry you have, but I'm sure you can show me I'm wrong on that.


To join in the discussion you should register or log in
Sorry bit late for this one... Mike 3rd November, 2008 17:05 (UTC)
Ok, I thought m and n were the length of the sides…
Sorry bit late for this one... Mike 3rd November, 2008 17:20 (UTC)

Even better:

def robots2(n,m):
    if m>n: n,m = m,n
    f = lambda x,y: reduce(mul, xrange(x, y), 1)
    return f(n,n+m-1)/f(1,m)

Although the basic algorithm is fast, an extra speed boost comes from the reduce, mul, and xrange builtin python functions, as they are all implemented in C.

Sorry bit late for this one... Mike 3rd November, 2008 17:23 (UTC)
That implementation seems to fix it BTW.
kirit.com