RSS
RSS / Subscribe
Given problem x, can you compute the answer? Is it feasible to brute-force the answer?
This is easy to answer experimentally. If I define computable as something that I can run on my laptop in under 1 minutes with a slow language (Python):
--------------------
Loop 2^24 in 1.30s
Loop 2^25 in 2.60s
Loop 2^26 in 5.21s
Loop 2^27 in 10.54s
Loop 2^28 in 20.83s
Loop 2^29 in 41.72s
--------------------
Loop 10^1 in 0.00s
Loop 10^2 in 0.00s
Loop 10^3 in 0.00s
Loop 10^4 in 0.00s
Loop 10^5 in 0.01s
Loop 10^6 in 0.08s
Loop 10^7 in 0.78s
Loop 10^8 in 7.93s
Loop 10^9 in 78.62s
--------------------
So there it is, above 2^30 or 10^9 operations your computer runs in serious trouble.
We can scale the result above in order to get the results in terms of years:
1 year: ~ 10^14 ~= 2^46
10 years: ~ 10^15 ~= 2^49
100 years: ~ 10^16 ~= 2^52
Conclusion: if napkin-calculations reveal that your problem needs less than 10^9 operations, you can easily brute-force your way through it.
import math
import timeit
def timeMe(base):
limit = int(math.log(1e10) / math.log(base))
for exponent in range(1, limit + 1):
n = 0
cmd = 'for i in range(%d**%d): n = i+i' % (base, exponent)
nSecs = timeit.timeit(cmd, number=1)
print('Loop %d^%d in %.2fs' % (base, exponent, nSecs))
print('-' * 10)
timeMe(2)
print('-' * 10)
timeMe(10)
print('-' * 10)
I was solving the Equal Sums problem of Google Code Jam. Looking at the numbers limit, it seemed like it was feasible to brute-force through all 1, 2 and 3-tuples. This is a O(n^3) algorithm with n == 500. Since it is ~10^8 operations, we know that we should be able to reasonably brute-force this. Now, I suggest that you read the math section of the problem in order to understand why this is likely to work (but not guaranteed -- if they had a set where only >= 6-tuples could be solution then I would never have been able to prove that no solution can be found). But our questions is different: how long is it going to take to go through all the possible 3-tuples and how does it match with the result we have above.
All 2-tuples (500^2 ~= 10^5): 00.66 secs
All 3-tuples (500^3 ~= 10^8): 20.57 secs
Now, we should not be surprised that it takes more time than our estimate in the first section: in this problem we do MUCH more every iteration. The fudge factor is from ~60 to ~2.5. Also, as we slow down as we go which is expected because we have an ever-expanding dictionary that keeps track of all the answers in memory. But the ~10^8 limit as what is feasible to brute-force in a few seconds remains!
Given the constraints we did not have to solve the problem; brute force was enough!
import copy
import collections
import timeit
def startSmall():
N = "279723182299 376876333524 998067966121 403485644442 153635442114 399189277664 230203543364 317963821285 351345530822 148151584645 684971615669 135054212116 636307404388 623840919365 742186585581 261949667274 262985372168 456696918121 936200521159 262459964519 259367083572 405184756642 104095058407 52695575854 40109000701 786793234470 734315378491 76992992268 343786892924 697121153437 725714221703 895499931981 805467280153 196880330941 912165217021 70727548109 716021033204 53114833551 922877781847 773905963417 522513695105 812014766958 957151120167 534064397354 911573744097 998468086343 89252943844 453000312834 130161459074 569342457998 741809185948 46156906233 653624819175 944102929433 440009999356 484138801997 545648063331 555647844367 132201400220 235093862869 48840881731 949992883063 565627740876 212811725246 379870929286 206687302384 176371061529 117940879646 206204221514 25847501412 475235734321 728265674918 579394496800 864821221996 434116969604 996414146286 461599230089 69222744440 454690170897 9332645752 517144199870 323451331247 442177489557 968905696256 955683650226 110223094609 707994487197 968530741843 852218104020 720002104839 725351165376 9027153496 335247652855 954562251546 808073535166 218393270859 599421082705 153343365071 216088953944 55834519300 714266890546 973433485465 431747834536 331538991874 16887455023 919086107825 579623133938 853255424721 224134281919 974004216022 269441870173 531878276261 209771521469 409569176727 287282320121 649495488479 962543296720 899988343728 685706115716 256427996423 947841194523 221988840996 591466177571 676266006532 805088660087 814389168694 370749563588 916801120284 139145883894 996783134695 711357521523 342786470645 488923106867 375357995366 993887191145 383560524196 276316552464 973090377739 564282848803 499952346473 587462551177 314927306722 925760832003 290454868288 995135389077 548596045607 18136150640 284044933438 462874905432 86778469460 499821118003 702082398584 947150974490 334166547275 318729226971 309434372864 56121272203 806236239653 944345639608 827033828285 23884589175 53701978400 208049169387 65565756421 484730728058 937419555518 655661076856 295305222653 520829289037 23085236422 689536294175 288327038999 173088638691 591582521414 80894095692 161635917358 238273979699 121164566861 68210256654 716550390513 187097624772 987704938826 587326269843 489678268711 612579120662 671099604776 579945460183 945652179518 533158973878 206623874528 15361093901 438763311435 66510178687 592671188129 25254268284 926093530739 29753496711 972106937243 836935680025 99552727965 152129519913 31888111685 970320516248 954623937776 196884228781 159308519818 573186299879 673082153573 675184624880 500383165150 795259635545 964178699555 475009554049 676605004496 640635085290 53579287832 1913459626 41873949270 150126105973 70413831347 620454122317 699311867962 947583072596 654978145418 179077936733 538017785993 246845280868 161900167188 713468756400 56589663664 924032139875 358360299207 164287297522 709655903773 146669094741 280966486552 455492935058 523404134965 416410005704 707024175232 434454145770 903876308587 306478534707 944818660643 639604054559 80361014715 706058028590 267730683033 341835672166 292008657032 67977393638 74685590289 104393119848 220594475091 29361134608 996244317459 273900394474 643463788410 846608572826 737592770472 771750536858 481225166575 351515975362 155283617236 17297030317 862385306067 124266914562 866870342609 133388007188 327211512177 64261248653 867403251494 260668585689 578998346493 908484204153 839989780134 779309535944 814381847671 926932150373 456651627976 738853811387 201178352885 779026346463 507207750043 130903374284 535658844881 806844111858 940587831461 954756413427 310124621613 541558935209 318094960610 217212392685 411445565875 405259892854 367788760341 837001969043 739387799262 43930599507 965666662405 684597848144 12462522360 53378054946 641102090099 931917402864 366714259241 920051882306 271138244987 789366143359 131296187662 97665061044 570843387093 546117270610 274064681979 738375486019 520673307362 603012854724 55039512239 364005390006 765847472863 974010523756 180381147556 830741190317 8195139325 376131721162 171107473099 432201696118 843213005487 599043220784 825553719281 663801049493 802676117092 917270232909 644503978767 432594910426 864183413927 609942122399 464426369994 618341164568 612052621609 170848393480 812343509384 987039743102 415588253658 7282335403 249491610185 40922331206 494457045440 151543041284 143846607151 221646335968 446869541047 624565131007 771409411612 587648652551 645033145227 809994200932 112190344198 809571691636 906660315960 735712147673 554748785928 600979467835 558267774285 920487366873 188577276342 182251711835 860292249215 703738632162 257359413039 384837010906 783116572808 346386427343 509065801790 178875633877 33732015651 25117441089 841957919344 314959902728 408321173908 998036958289 496301760417 168655107263 393674356114 990237227678 966411569146 889233648758 498074703486 594138949070 765321710390 893540232908 973774958366 174134228533 633706687507 6378288724 142421780911 793680885022 204644431433 765644419542 986129761085 760005018775 969230560580 276963282129 33474269929 401984033030 38053752946 117139580994 572675229060 922829637193 235966087980 760168087345 626033587909 633136639237 779766204193 726223444639 557157358614 545783814166 454756812151 101218544995 616331296503 58365886906 876764354162 435356700764 479444946574 298870257418 470685258227 390765087939 503494627463 266069920537 873719022948 715634856383 126866834622 19501868589 526261627962 318791462892 324946049245 385204079706 878737357277 326950923978 870381926401 5639204449 263198597868 682513940227 4345919081 896000553254 15512357080 656811489544 39723829293 292341969267 5459733999 921140546432 230364209167 264410653243 473794768466 685269518825 624161746675 823528219154 8332436584 219752861503 768420573336 75894745397 427137517822 501095542606 15666855955 573879228968 155904593898 227765828793 724786686470 428729034263 631949427550 303444387613 397472911452 56807290224 192578593237 461136029508 629644711830 965162215333 964805593622 866489274136 727566795152 923578697230 813260995968 807164500327 843775845627 682230751102 266037288904 302425231558 807228641715 672007702571 54316762137 328925386368 491239950009 281419905721 657332715130 745066995960 693927837925 753243333720 483109392031 899842291847 654658217180"
N = [int(n) for n in N.split(' ')]
sumMap = {}
stack = collections.deque([([], 0, 0)])
maxDepth = 3
while len(stack) > 0:
#pds = stack.popleft()
pds = stack.pop()
for i in range(len(N)):
P, sm, depth = pds
if N[i] in P:
continue
PP = copy.copy(P)
PP.append(N[i])
PP.sort()
depth += 1
sm += N[i]
if sumMap.get(sm) is None:
sumMap[sm] = PP
else:
if PP != sumMap[sm]:
return (sumMap[sm], PP)
if depth < maxDepth:
stack.append((PP, sm, depth))
return None
nSecs = timeit.timeit(
"startSmall()", 'from __main__ import startSmall', number=1)
print('Took %.2f secs.' % nSecs)