Mercurial > hg > euler
changeset 2:1ca695e32f66
Solutions from tungsten
| author | Dominic Cleal <dominic@computerkb.co.uk> |
|---|---|
| date | Mon, 01 Dec 2008 10:57:01 +0000 |
| parents | |
| children | b94533a8c529 |
| files | keylog.txt problem1.py problem10.py problem14.py problem16.py problem2.py problem20.py problem4.py problem48.py problem5.py problem6.py problem7.py problem79.py problem8.py problem9.py |
| diffstat | 15 files changed, 298 insertions(+), 0 deletions(-) [+] |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/keylog.txt Mon Dec 01 10:57:01 2008 +0000 @@ -0,0 +1,50 @@ +319 +680 +180 +690 +129 +620 +762 +689 +762 +318 +368 +710 +720 +710 +629 +168 +160 +689 +716 +731 +736 +729 +316 +729 +729 +710 +769 +290 +719 +680 +318 +389 +162 +289 +162 +718 +729 +319 +790 +680 +890 +362 +319 +760 +316 +729 +380 +319 +728 +716
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/problem1.py Mon Dec 01 10:57:01 2008 +0000 @@ -0,0 +1,15 @@ +skips = [3,2,1,3,1,2,3] +s = 0 + +tot = 0 +i = 0 + +while i<1000: + tot += i + i += skips[s] + s += 1 + if s==len(skips): + s = 0 + +print tot +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/problem10.py Mon Dec 01 10:57:01 2008 +0000 @@ -0,0 +1,21 @@ +import math + +primes = [ 2 ] + +def isPrime(test): + max = math.floor(math.sqrt(test)) + t = 0 + while t < len(primes) and primes[t] <= max: + if test % primes[t] == 0: + return False + t += 1 + + return True + +i = 3 +while i < 2000000: + if isPrime(i): + primes.append(i) + i += 2 + +print sum(primes)
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/problem14.py Mon Dec 01 10:57:01 2008 +0000 @@ -0,0 +1,25 @@ +def even(x): return x/2 +def odd(x): return 3*x + 1 + +def fn(x): + if x % 2 == 0: + return even(x) + else: + return odd(x) + +def lookup(x, cache): + if not x in cache: + cache[x] = lookup(fn(x), cache) + 1 + return cache[x] + +mx = 0 +ml = 0 +cache = { 1: 1 } +for rx in range(1, 1000001): + l = lookup(rx, cache) + + if l > ml: + mx = rx + ml = l + +print "Best x is %d with len %d" % (mx, ml)
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/problem16.py Mon Dec 01 10:57:01 2008 +0000 @@ -0,0 +1,1 @@ +print sum([int(a) for a in str(2**1000)])
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/problem2.py Mon Dec 01 10:57:01 2008 +0000 @@ -0,0 +1,16 @@ +tot = 2 +f = [ 1, 2 ] + +while True: + f.append(f[0] + f[1]) + f.pop(0) + f.append(f[0] + f[1]) + f.pop(0) + e = f[0] + f[1] + if e>4000000: + break + tot += e + f.append(e) + f.pop(0) + +print tot
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/problem20.py Mon Dec 01 10:57:01 2008 +0000 @@ -0,0 +1,3 @@ +import operator +f = reduce(operator.mul, range(2, 101)) +print sum([int(c) for c in str(f)])
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/problem4.py Mon Dec 01 10:57:01 2008 +0000 @@ -0,0 +1,18 @@ +import math + +def ispal(x): + s = str(x) + for i in range(0, int(len(s) / 2)): + if (s[i] != s[-i - 1]): + return False + return True + +r = range(1000, 99, -1) +p = -1 +for a in r: + for b in r: + m = a*b + if ispal(m) and m > p: + print "Answer: %d x %d = %d (%s)" % (a,b,m, ispal(m)) + p = m +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/problem48.py Mon Dec 01 10:57:01 2008 +0000 @@ -0,0 +1,3 @@ +s = sum([a**a for a in range(1,1001)]) +print s +print str(s)[-10:]
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/problem5.py Mon Dec 01 10:57:01 2008 +0000 @@ -0,0 +1,17 @@ +import math + +m = 20 + +divs = range(int(math.ceil(m / 2)) + 1, m) + +t = m +while True: + for d in divs: + if t % d > 0: + break + else: + print t + exit + t += m + +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/problem6.py Mon Dec 01 10:57:01 2008 +0000 @@ -0,0 +1,6 @@ +def sq(x): return x*x + +r = range(1,101); +a = sum(map(sq, r)); +b = sq(sum(r)); +print (b-a)
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/problem7.py Mon Dec 01 10:57:01 2008 +0000 @@ -0,0 +1,21 @@ +import math + +primes = [ 2 ] + +def isPrime(test): + max = math.floor(math.sqrt(test)) + t = 0 + while t < len(primes) and primes[t] <= max: + if test % primes[t] == 0: + return False + t += 1 + + return True + +i = 3 +while len(primes) < 10001: + if isPrime(i): + primes.append(i) + i += 2 + +print primes.pop()
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/problem79.py Mon Dec 01 10:57:01 2008 +0000 @@ -0,0 +1,35 @@ +import sys + +class Code: + after = [] + + def __init__(self, num, after): + self.num = num + self.after = after + +def code_cmp(a, b): + if a.num == b.num: + return 0 + elif a.num in b.after: + return 1 + elif b.num in a.after: + return -1 + else: + return 0 + +codes = [] + +f = open("keylog.txt") +try: + for line in f: + linecodes = [] + for i in [int(i) for i in line.rstrip()]: + codes.append(Code(i, linecodes)) + linecodes.append(i) +finally: + f.close() + +print ''.join([str(c.num) for c in codes]) +codes.sort(code_cmp) +print ''.join([str(c.num) for c in codes]) +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/problem8.py Mon Dec 01 10:57:01 2008 +0000 @@ -0,0 +1,58 @@ +import sys + + +num = """ +73167176531330624919225119674426574742355349194934 +96983520312774506326239578318016984801869478851843 +85861560789112949495459501737958331952853208805511 +12540698747158523863050715693290963295227443043557 +66896648950445244523161731856403098711121722383113 +62229893423380308135336276614282806444486645238749 +30358907296290491560440772390713810515859307960866 +70172427121883998797908792274921901699720888093776 +65727333001053367881220235421809751254540594752243 +52584907711670556013604839586446706324415722155397 +53697817977846174064955149290862569321978468622482 +83972241375657056057490261407972968652414535100474 +82166370484403199890008895243450658541227588666881 +16427171479924442928230863465674813919123162824586 +17866458359124566529476545682848912883142607690042 +24219022671055626321111109370544217506941658960408 +07198403850962455444362981230987879927244284909188 +84580156166097919133875499200524063689912560717606 +05886116467109405077541002256983155200055935729725 +71636269561882670428252483600823257530420752963450 +""" + +roll = [] +rollt = 0 + +best = [] +bestt = 0 + +for d in num: + if not d.isdigit(): + continue + + n = int(d) + if n == 0: + roll = [] + rollt = 0 + continue + + roll.append(n) + if len(roll) > 5: + rollt -= roll.pop(0) + rollt += n + if rollt > bestt: + best = [] + for c in roll: + best.append(c) + bestt = rollt + +print best +m = 1 +for d in best: + m *= d +print m +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/problem9.py Mon Dec 01 10:57:01 2008 +0000 @@ -0,0 +1,9 @@ +for a in range(1, 1000): + for b in range(a + 1, 1000): + if a + b > 1000: + break + for c in range(b + 1, 1000): + if a + b + c == 1000 and a*a + b*b == c*c: + print "%d^2 %d^2 = %d^2" % (a, b, c) + print "a*b*c = %d" % (a*b*c) +