* ProjectEuler
在projecteuler.net，很多小的程序题，可以用来练习键盘指法。限制比较宽松，只要不是很过分，暴力过关也没有关系。
虽说要尽量多用用数学知识来求解吧，不过拿出图灵完备的机器来辅助过关话，其实能算是很正当的方式呦。
高德納学派的可以用ASM，习惯传统方式可以用C++，天书般的J，函数式的Haskell，各种数学计算系统，或者偷懒用用Python，这些都是可以的做法。
既然我这里纯粹是出于娱乐目的的过关而已，就以Python2为主要工具了，也恰巧手头可以使用。
下面的内容算是流程的记录，这里粘贴在一个页面里而已。当初是正确的得到结果，并且性能可以说得过去，在这里就不再做什么改进了。
话说 Level 1 的内容实在十分基础了，没什么好说的了，下面闪入正文吧。
* Problem 1
print sum(i for i in xrange(1000) if (i%3==0) or (i%5==0))
这题的较好的做法是用等差数列求和，注意不把项记录重复了。
* Problem 2
(let loop ((s 0) (a 1) (b 2))
(if (> b 4000000)
s
(loop (if (even? b) (+ s b) s) b (+ a b))))
这道题的优化方法是利用数列满足：奇偶奇奇偶奇奇偶奇...来计算。
* Problem 3
(let loop ((x 600851475143) (i 2))
(if (> i (sqrt x))
x
(if (zero? (remainder x i))
(loop (/ x i) i)
(loop x (+ i 1)))))
偷懒可以用Maxima的factor函数，或者手写用正整数数列不断去除它，最后留下来的就是结果。
* Problem 4
(let loop ((r 0) (i 100) (j 100))
(cond
((= i 1000) r)
((= j 1000) (loop r (+ i 1) (+ i 1)))
(else
(let* ((p (* i j))
(s (string->list (number->string p))))
(loop (if (and (equal? s (reverse s)) (> p r)) p r) i (+ j 1))))))
纯暴力，考虑了乘法交换积不变。不过这里回文判断实现得大不好，貌似可以推导出什么数学式子。
* Problem 5
(do((i 1 (+ i 1))
(s 1 (lcm s i)))
((> i 20) s))
最小公倍数的算法貌似是欧几里德发明的。
* Problem 6
print sum(i for i in range(101))**2-sum(i**2 for i in range(101))
又暴力了，不过数列求和有那啥啥公式来着，不知道那些数学软件优化了没。
* Problem 7
(define (prime? x)
(let loop ((i 2))
(cond ((> (* i i) x) #t)
((zero? (remainder x i)) #f)
(else (loop (+ 1 i))))))
(let loop ((i 2) (n 0))
(if (prime? i)
(if (= n 10000)
i
(loop (+ i 1) (+ n 1)))
(loop (+ i 1) n)))
判断质数，后面会遇到更加丰富的用法的。
* Problem 8
import operator
s= ...
print max(reduce(operator.mul,map(int,s[i:i+5])) for i in xrange(len(s)-4))
又是暴力...题目字面的意思...不说什么了...
* Problem 9
a, b, c = 200, 375, 425
我才不告诉人家我是慢慢试出来的呢...
* Problem 10
m = 2000000
s = [True] * m
s[0] = False
s[1] = False
for i in xrange(2,m):
if not s[i]:
continue
j = 2
while True :
k = i * j
if k >= m:
break
s[k] = False
j+=1
print sum(i for i,v in enumerate(s) if v)
传说中的划杠杠法，终于没有出现尾递归...
* Problem 11
from operator import mul
x = [
...
]
def s(r1,r2,d):
return max(reduce(mul,[x[i+d[0]*n][j+d[1]*n] for n in range(4)]) for i in r1 for j in r2)
print max(
s(xrange(0,20-3),xrange(0,20-0),(+1,+0)),
s(xrange(0,20-0),xrange(0,20-3),(+0,+1)),
s(xrange(0,20-3),xrange(0,20-3),(+1,+1)),
s(xrange(0,20-3),xrange(0+3,20),(+1,-1)),
)
字符串数据源直接拿正则表达式处理了，然后是幸好没差点把尝试的情况和范围弄错掉。
* Problem 12
(define (factor x)
(let loop ((x x) (i 2) (n 1) (r '()))
(if (> i (sqrt x))
(cons x r)
(if (zero? (remainder x i))
(loop (/ x i) i (+ n 1) (cons i r))
(loop x (+ i 1) n r)))))
(define (factor-exp x)
(let ((x (factor x)))
(let loop ((a (cdr x))(b '())(c (car x))(d 1))
(if (null? a)
(cons d b)
(if (not (= (car a) c))
(loop (cdr a) (cons d b) (car a) 1)
(loop (cdr a) b c (+ d 1)))))))
(define (factor-num x)
;(assert (> x 1))
(apply * (map (lambda (x) (+ x 1)) (factor-exp x))))
(let loop ((s 0)(i 1))
(if (> (factor-num s) 500)
s
(loop (+ s i) (+ i 1))))
这题暴力的话效率实在不够，只好手疼地用排列组合的知识来优化一下了。
* Problem 13
x=[
...
]
print str(sum(x))[:10]
性能居然够，那我就不手疼了，不然从左往右算？根据100个n位数的和的位数肯定小于(n+3)来着...Java也有自带类似的库的说。
* Problem 14
m = 1000000
c = {}
c[1]=1
def n(x):
if x in c:
return c[x]
if x%2==0:
nx = x/2
else:
nx = 3*x+1
v = n(nx)+1
c[nx] = v
return v
mx=0
mv=1
for i in xrange(1,m):
t = n(i)
if t>mx:
mx, mv = t, i
print mv
代码写丑了我会直接说出来吗...这题超过边界不记忆的话估计性能也够了。
* Problem 15
load(functs);
combination(20+20,20);
这貌似是学排列组合的例题，那么就数学软件Maxima应对吧。
或者从左上角一步一步往右下角慢慢迭代推过去也是可以的。
* Problem 16
print sum(map(int,str(2**1000)))
依然高精度，性能没有问题就不优化了。
* Problem 17
(define (en n)
;(assert (<= 1 n 1000))
(cond
((zero? n) "")
((= n 1000) "onethousand")
((zero? (remainder n 100))
(string-append (en (quotient n 100)) "hundred"))
((< 100 n 1000)
(string-append (en (quotient n 100)) "hundredand" (en (remainder n 100))))
((< 19 n 100)
(string-append (vector-ref #("ten" "twenty" "thirty" "forty" "fifty" "sixty" "seventy" "eighty" "ninety") (- (quotient n 10) 1)) (en (remainder n 10))))
((< n 20)
(vector-ref #("one" "two" "three" "four" "five" "six" "seven" "eight" "nine" "ten" "eleven" "twelve" "thirteen" "fourteen" "fifteen" "sixteen" "seventeen" "eighteen" "nineteen") (- n 1)))))
(do ((i 1 (+ i 1))(s 0 (+ s (string-length (en i)) )))((= i 1001) s))
我这里zero?的处理不大合代码的逻辑，只是在题目的范围内还不会影响到结果。不过这题其实扳手指算一个总数出来也就可以了。
* Problem 18
x = [
...
]
m = [[0]*i for i in range(1,len(x)+1)]
m[0][0]=x[0][0]
for i in range(len(x)-1):
for j in range(i+1):
print i, j
t = m[i][j]+x[i+1][j]
if m[i+1][j] < t:
m[i+1][j] = t
m[i+1][j+1] = m[i][j]+x[i+1][j+1]
print max(m[len(m)-1])
传统的DP题终于出现了呵，这里是手工用正则表达式获得数据后按照套路来处理。
* Problem 19
def getDaysOfMouth(yyyy,mm):
_daysOfMouth = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
def isLeap(y):
return y%4==0 and y%400!=0
return 29 if mm==1 and isLeap(yyyy) else _daysOfMouth[mm]
daysAfter = 0
daysOfSunday = 0
mod = sum(getDaysOfMouth(1990,m) for m in range(12)) % 7
for y in range(1901,2001):
for m in range(12):
if daysAfter%7==6 - mod :
daysOfSunday += 1
daysAfter += getDaysOfMouth(y,m)
print daysOfSunday
数字中用来好多魔法，千万小心别出Bug，这算法是代替手工操作的，需要小心和测试。话说一些语言的标准库里可是有Date和Calendar，而后者中能获取到星期相关的信息的。
* Problem 20
from math import factorial
print sum(map(int,str(factorial(100))))
高精度计算，拆位处可不涉及字符串，不过解释语言内置方法实现的比自己写的会效率好一些。
* Problem 21
c={}
def d(x):
if x in c:
return c[x]
else:
d = sum(i for i in xrange(1,x) if x%i==0)
c[x] = d
return d
s = 0
for i in range(1,10000):
a = i
b = d(a)
if d(b)==a and a!=b:
s += a
print s
前面某题做过求因数的优化了，这题暴力的话勉强够了。从实际命中的情况看，缓存用定长10000的数组对这题其实效率更好。
* Problem 22
f = open("names.txt","r")
l = f.readline()
c = l.split(",")
c.sort()
def s(x):
return sum(ord(i)-ord('A')+1 for i in x[1:-1])
print sum(s(v)*i for i,v in enumerate(c,start=1))
第六行的里把引号过滤掉就目的达到，话说这次终于在IO方面没法省事直接内嵌数据了。
* Problem 23
m = 28123
def d(x):
return sum(i for i in xrange(1,x) if x%i==0)
a = {}
for i in xrange(1,m):
if d(i) > i:
a[i] = True
def c(x):
return any(True for i in xrange(1,x) if i in a and x-i in a)
print sum(i for i in xrange(1,m+1) if not c(i))
虽然结果对，但是像目前这样不优化的肯定超时。用Py2.7的特性可以把生产字典写为单行，可以省掉5~7th行。
另外用列表类型要注意Py的下标为负数也能取到元素，别弄错了。列表的话就写作“... a = [None]*m ... if a[i] and a[x-i] ... ”。
* Problem 24
from itertools import permutations,islice
print "".join(map(str,[i for i in islice(permutations(range(10)),999999,1000000)][0]))
某种意义的开挂，不过Py2的itertools代码明显不如Py3美观。优化的方法是位数从左到右计算可能的个数，排列的情况其实只用阶乘，然后手工调试出结果即可。
* Problem 25
(let loop ((a 1) (b 1) (n 1))
(if (= (string-length (number->string a)) 1000)
n
(loop b (+ a b) (+ n 1))))
在Scheme里用尾递归表示迭代是相当好用的，有named-let和do两个宏可用。
* Problem 26
from itertools import count
def c(x):
c = {}
r = 1
for i in count(0):
t = r%x
if t==0:
return 0
elif t in c:
return i-c[r%x]
else:
c[t] = i
r*=10
m, v = 0, 0
for i in range(1,1000):
t = c(i)
if t>v:
m ,v = i ,t
print m
这里是模拟手工操作，不过貌似有数学推导式来着。
* Problem 27
from math import *
from itertools import *
c = {}
def p(x):
if x in c:
return c[x]
else:
p = (x==2 or
(x>2 and x%2!=0 and
all(x%i!=0 for i in xrange(3,int(sqrt(x))+1,2))))
c[x] = p
return p
def q(n,a,b):
return n**2+a*n+b
m, v = (), 0
for a in xrange(-999,1000):
for b in xrange(-999,1000):
for x in count(0):
if not p(q(x,a,b)):
if x-1>v:
m,v=(a,b),x-1
break
print m[0]*m[1]
怎么就没有带参数的max函数呢，不然派生一个Comparable类型出来更加累赘啊。
* Problem 28
size = 1001
def delta(x):
return (x+2)**2-x**2
s,d = 1,1
for i in xrange(1,size,2):
d += delta(i)
s += d
print s*4-sum(range(2,size,2))*(1+2+3)-4+1
先算了右上角，然后扩展到四个角。其中用到的递推式（4~7th中的d）貌似可以化简。
* Problem 29
print len(set(a**b for a in xrange(2,101) for b in xrange(2,101)))
唉，又暴力了，居然性能还行，那就不用优化了。不用大数运算的话，其实重复项也只是底数呈指数关系的项。注意指数如果展开的话，不能用浮点数运算。
* Problem 30
from math import *
from operator import pow
from itertools import *
w = 0
for i in count(1):
if 9**5*i < 10**i:
w = i
break
def t():
for digits in product(range(10),repeat=w):
m = reduce(lambda x,y:x*10+y,digits)
if m!=0 and m!=1 and m==sum(i**5 for i in digits):
yield m
print sum(t())
当位数达到一定大小后，和的最大值就已经满足不了位数了。由于 多项式函数==o(指数函数) ，从而可以求出全部解。
* Problem 31
from itertools import *
r = 200
p = [1,2,5,10,20,50,100,200]
n = 0
def t(s,pc):
if pc>=len(p):
return
for i in count(0):
l = s+i*p[pc]
if l == r:
global n
n+=1
if l >= r:
return
t(l,pc+1)
t(0,0)
print n
这次代码真的写丑了，不过运行效果良好。
* Problem 32
from itertools import *
digits2int = lambda ds: reduce(lambda h,l:10*h+l,ds)
def enum():
for i in permutations(range(1,10)):
for j in range(1,9):
for k in range(j+1,9):
if not (j-1)+(k-j-1)+1 <= k < (j-1)+(k-j-1)+3:
continue
a,b,c = map(digits2int,(i[0:j],i[j:k],i[k:9]))
if a*b==c:
yield c
print sum(set(enum()))
目前性能不行，如果把permutations展开写的话，可能可以免去一些方向的尝试。
* Problem 33
from functools import *
from itertools import *
from operator import *
from fractions import *
print apply(Fraction,reduce(partial(map,mul),((10*a+b,10*b+c) for a,b,c in product(range(1,10), repeat=3) if a<c and (10*a+b)*c==(10*b+c)*a))).denominator
好吧我承认这题很简单，但是我一开始愣是没明白题目要做什么。约分可以请欧几里德来算得最大公约数做除数，其他没什么好说的。
* Problem 34
from math import *
print sum(x for x in xrange(3,10**6) if sum(map(factorial,map(int,str(x))))==x)
以每一位都是9的情况和函数间的高阶关系来考虑上限，然后暴力。上限的位数是最大使得“factorial(9)*i>=10**i-1”成立的正整数。顺带说些Py带的若干函数是C实现的，性能比手工写要好很多。
* Problem 35
from math import *
from itertools import *
m = 10**6
s = [False,True] * (m/2)
s[0:3] = False, False, True
for i in xrange(3,m,2):
if not s[i]:
continue
j = 2
while True :
k = i * j
if k >= m:
break
s[k] = False
j+=1
def primep(x):
return s[x]
def rotations(x):
s = str(x)
return [s[i:len(s)]+s[0:i] for i in range(len(s))]
def cpp(x):
return all(map(
lambda t:primep(int("".join(t))),rotations(x)))
print len([True for i,v in enumerate(s) if v and cpp(i)])
一开始的时候每没意识到要优化，后来就好多了。有点等价代码的草稿，被我擦掉了。
* Problem 36
pp = lambda x:(lambda s:s==s[::-1])(str(x))
d2b = lambda x:"{:b}".format(x)
print sum(i for i in xrange(1,10**6) if pp(i) and pp(d2b(i)))
按照题目的意思来就可以了，没有遇到很糟糕的性能。
* Problem 37
from math import *
from itertools import *
from functools import *
m = 10**6
s = [False,True] * (m/2)
s[0:3] = False, False, True
for i in xrange(3,m,2):
if not s[i]:
continue
j = 2
while True :
k = i * j
if k >= m:
break
s[k] = False
j+=1
primep = lambda x:s[x]
truncate = lambda x:(lambda s:
imap(partial(map,int),
((s[:i+1],s[i:]) for i in range(len(s)))))(str(x))
tpp = lambda x:all(primep(a) and primep(b) for a,b in truncate(x))
t = [i for i in xrange(10,m) if tpp(i)]
print len(t)
print sum(t)
题目里说十一个，所以就算了这么一些，得到了answer。代码中用到了惰性求值，不然性能会很糟糕，避免了列表被完全展开。虽然没有编译时优化惰性求值有多余的开销，不过不必要的计算才是这里最影响性能的东西。
* Problem 38
from itertools import *
from functools import *
def t(x):
"int->int"
s = ""
for i in count(start=1):
s += str(x*i)
if '0' in s:
return 0
if 9==len(s)==len(set(s)):
return int(s)
elif 9<=len(s):
return 0
print max(t(reduce(lambda a,b:a*10+b,j,9))
for i in range(0,4) for j in permutations(range(1,9),i))
需要尝试位数小于5的数，并注意没有零出现。
* Problem 39
print(reduce((lambda f,s:f if f[1]>s[1] else s),((m,len([a for a in xrange(1,m/3) for b in xrange(a,(m-a)/2) for c in (m-a-b,) if b-a<c<a+b and a**2+b**2==c**2])) for m in xrange(1001)))[0])
性能啊性能啊
* Problem 40
from operator import *
from itertools import *
from functools import *
print reduce(mul,(int(v) for i,v in islice(enumerate(chain.from_iterable(imap(str,count()))),1000001) if i in (1,10,100,1000,10000,100000,1000000)))
边迭代边判断即可。
* Problem 41
from math import *
from itertools import *
primep = lambda x:(x==2 or (x>2 and x%2!=0 and all(x%i!=0 for i in xrange(3,int(sqrt(x))+1,2))))
print max(k for i in range(1,10) for j in permutations(range(1,i+1),i) for k in (reduce(lambda x,y:10*x+y,j,0),) if primep(k))
就是题目字面的意思。
* Problem 42
c = (open("words.txt","r").readline()[1:-1]).split('","')
v = lambda x:sum(ord(i)-ord('A')+1 for i in x)
t = lambda n:(n*(n+1))/2
ts = [1]
def tp(x):
while ts[-1]<x:
ts.append(t(len(ts)+1))
return x in ts
print len([i for i in c if tp(v(i))])
还有明显的优化空间，不过没感觉到性能瓶颈。
* Problem 43
from itertools import *
digits2int = lambda it:reduce(lambda a,b:10*a+b,it,0)
satisfy = lambda x:all(imap(lambda a,b:a%b==0,(digits2int(x[j:j+3]) for j in xrange(1,8)),(2,3,5,7,11,13,17)))
print sum(digits2int(i) for i in permutations(range(10)) if satisfy(i))
来多说说一些关于permutations函数的话题吧这里，因为最近用得较多了。话说STL里面也有同样作用的函数提供，而自己实现的话可以简单地利用树的遍历。
* Problem 44
from math import *
#from bisect import *
from itertools import *
p = lambda n:n*(3*n-1)/2
#ps = [p(1)]
#def pp(x):
# while ps[-1]<x:ps.append(p(len(ps)+1))
# return (lambda i:i<len(ps) and ps[i]==x)(bisect_left(ps,x))
pp = lambda x:((1+sqrt(1+24*x))/6)%1==0
print list(islice((p(i)-p(j) for i in count(1) for j in xrange(1,i) if (lambda x,y:pp(x+y) and pp(x-y))(p(i),p(j))),1))[0]
注释掉的代码是被重写了的，用了一元二次方程的求根公式（结合函数图形看，其实这里用错了，还没来及修改）。不用bin-search用hash-set貌似也行。
* Problem 45
(let loop ((i 286) (j 166) (k 144))
(let ((t (* i (+ i 1) 1/2))
(p (* j (- (* 3 j) 1) 1/2))
(h (* k (- (* 2 k) 1))))
(cond ((= t p h) t)
((<= t (min p h)) (loop (+ i 1) j k))
((<= p (min t h)) (loop i (+ j 1) k))
((<= h (min t p)) (loop i j (+ k 1)))
(else #f))))
话说好久没用Scheme来写写了。
* Problem 46
from math import *
from itertools import *
oddp = lambda x:x%2!=0
primep = lambda x:(x==2 or (x>2 and x%2!=0 and all(x%i!=0 for i in xrange(3,int(sqrt(x))+1,2))))
conjecturep = lambda x:any(i for i in xrange(2,x) if primep(i) and sqrt((x-i)*.5)%1==0)
failp = lambda x:oddp(x) and not primep(x) and not conjecturep(x)
for i in count(4):
if failp(i):
print i
break
#from functools import *
#from operator import *
#print list(islice(ifilter(failp,count(4)),1))[0]
直接算吧，然后直接答案取走。这里注释掉的是最后几行另一种运行很慢的写法。
* Problem 47
(define (factor x)
(let loop ((x x) (i 2) (r '()))
(if (> i (sqrt x))
(cons x r)
(if (zero? (remainder x i))
(loop (/ x i) i (cons i r))
(loop x (+ i 1) r)))))
(define (unique-sroted-list x)
(define (list-not-starts-with xs x)
(cond ((null? xs) '())
((eq? (car xs) x)
(list-not-starts-with (cdr xs) x))
(else xs)))
(if (null? x) '()
(cons (car x)
(unique-sroted-list
(list-not-starts-with (cdr x) (car x))))))
(define (number-of-distinct-primes x)
(length (unique-sroted-list (factor x))))
(do ((n 1 (+ n 1))
(a 0 (number-of-distinct-primes n))
(b 0 (if (= a 4) (+ b 1) 0)))
((= b 4)(- n 4 2)))
现在越来越觉得Scheme代码想撮面团拧麻花的样子。理解清楚题意才是最重要的，然后运用对应的知识即可。
* Problem 48
last_ten_digits = lambda x:str(x) if x<10**11 else str(x)[-10:]
print last_ten_digits(sum(int(last_ten_digits(i**i)) for i in xrange(1,1001)))
求指数过程中只保留10位即可，可以获得更好的性能。以Python的性能还是算了，内置函数和手写落差太大，还是不修改了。
* Problem 49
from math import sqrt
print (lambda c:(lambda p:[''.join(map(str,(i,j,k))) for a in xrange(len(c)) for b in xrange(a+1,len(c)) for i,j,k in [(c[a],c[b],2*c[b]-c[a])] if k>j and k in p and sorted(str(i))==sorted(str(j))==sorted(str(k))])(set(c)))(filter(lambda x:(x==2 or (x>2 and x%2!=0 and all(x%i!=0 for i in xrange(3,int(sqrt(x))+1,2)))),range(1000,10000)))
把for语句压缩为单行代码后的产物，“import”那行不算数。
* Problem 50
m = 10**6
def prime(m):
s = [False,True] * (m/2)
s[0:3] = False, False, True
for i in xrange(3,m,2):
if not s[i]:
continue
j = 2
while True :
k = i * j
if k >= m:
break
s[k] = False
j+=1
primep = lambda x:s[x]
primes = tuple(i for i in xrange(m) if primep(i))
return primep,primes
primep, primes = prime(m)
mr = 0
r = 0
for i in xrange(len(primes)):
su = sum(primes[i:i+22])
for j in xrange(i+22,len(primes)):
lp = j-i+1
su += primes[j]
if su>=m:
break
if primep(su):
if lp>mr:
mr,r = lp,su
print r
一开始不专心弄复杂题目意思了，造成了不必要的浪费，本来是很简单的问题。这次未用函数式风格，话说控制不好状态的变化很容易出错的说。
* Level 1
前50题就是这些了，这是些算全部题目的 Level One 部分。
撒花，撒花。
接下来朝着别的目标前进吧，就先暂且做这几道题作为练手和娱乐了。
其实吧PE的前50道题目还是比较浅显的，因为涉及到的数据结构和数学上的知识点不是很多。
题目差不多都是根据题目的意思直接翻译为代码，把程序语言作为一个强大的计算器来使用。
所以在这前50道题里，更关注的是对机算工具的使用，而不是问题本身的经验积累。
那么其中有什么积极的价值呢，我想，或多或少总是有的吧，我只能这么说了。
上面的代码太偷懒了，不知道这种懒惰时候会让自己对正常向的使用态度有副作用呢。
好害怕...
其他的就不多说了，收工。
----
此外Problem 8试了试common lisp，不过代码没写漂亮，所以上面整理时被我略去了。
<blockquote>(defparameter s ...)
(reduce #'max (loop for i from 1 to (- (length s) 5) collect (reduce #'* (map 'list #'(lambda (x) (parse-integer (string x))) (subseq s i (+ i 5))))))</blockquote>
如果想临时试试代码的话可以用用codepad.org或者ideone.com。
----
最初在uushare发贴说一天一题，然后在QQ空间上整理出了上文，然后又把纯文字版备份于此（可惜格式图片都丢失了）。
没有评论:
发表评论