燕slap釘バット

余りにも放っておきすぎたので一つ。
SyntaxHighlighterで行の折り返しが上手くできていなかったのでちょいと弄る。折り返しがword wrapなので単語の区切りがない場合はどうも折り返されない様子。普通はそれで十分な気もするが、code golfとの相性が悪いので修正。

/* First line */
.syntaxhighlighter .line.alt1
{
	background-color: #fff !important;
	word-break: break-all !important;
}

/* Second line */
.syntaxhighlighter .line.alt2
{
	background-color: #F8F8F8 !important;
	word-break: break-all !important;
}

shThemeDefault.cssを修正。これだとテーマを変えたときに困るのからshCore.csを弄った方がいい気もするが、変えないのでいいやというやっつけ。word-wrapやらwhite-spaceやらと色々格闘したがうまくいかず、word-breakでどうにかする。Google ChromeとIE8ではうまくいくが、Firefoxではスルーされる。まあ仕方がない。

次。SHA-256 Hashing。これはよく知られた、というか定義もはっきりしてるので特に説明の必要はないはず。といっても実際の処理まで知っている人がどれほどいるのか。少なくとも私は全く知らなかった。
取りあえずはFIPS 180-2とこれを読めばどうやって実装するのかは分かるはず。特に前者は計算のサンプルと途中経過が書いてあるのでデバッグにも最適。
ついでに言うと、当然ながらimport hashlibはダメな模様。
それでは。

import os
msg = os.read(0,9999)

H = [ 0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19 ]
K = [
	0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5, 
	0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174, 
	0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da, 
	0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967, 
	0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85, 
	0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070, 
	0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3, 
	0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
]

ch   = lambda x,y,z: x&y ^ ~x&z
maj  = lambda x,y,z: x&y ^ x&z ^ y&z
shr  = lambda x,n: (0xFFFFFFFF & x) >> n
rotr = lambda x,n: ((0xFFFFFFFF & x) >> n) | x << (32 - n)
sigma0 = lambda x: rotr(x, 7) ^ rotr(x, 18) ^ shr(x, 3)
sigma1 = lambda x: rotr(x, 17) ^ rotr(x, 19) ^ shr(x, 10)
SIGMA0 = lambda x: rotr(x, 2) ^ rotr(x, 13) ^ rotr(x, 22)
SIGMA1 = lambda x: rotr(x, 6) ^ rotr(x, 11) ^ rotr(x, 25)

def padding(w):
	x = map(ord, w) + [0x80]
	l = len(x)

	i = tmp = 0
	t = [ ]
	while i < l:
		tmp |= (x[i] << (24 - (i % 4) * 8))
		i += 1
		if i and i % 4 == 0:
			t.append(tmp)
			tmp = 0
	if i % 4:
		t.append(tmp)

	ts = len(t)

	while (ts + 2) % 16:
		t.append(0)
		ts += 1

	t.append(0)
	t.append((l - 1) * 8)

	result = []
	for i in range(0, len(t), 16):
		result.append(t[i:i+16])

	return result

for m in padding(msg):
	a, b, c, d, e, f, g, h = H
	m += [0] * 48
	for t in range(16,64):
		m[t] = sigma1(m[t - 2]) + m[t - 7] + sigma0(m[t - 15]) + m[t - 16]

	for t in range(64):
		T1 = h + SIGMA1(e) + ch(e, f, g) + K[t] + m[t] 
		T2 = SIGMA0(a) + maj(a, b, c)

		h = g
		g = f
		f = e
		e = d + T1
		d = c
		c = b
		b = a
		a = T1 + T2

	H[0] += a
	H[1] += b
	H[2] += c
	H[3] += d
	H[4] += e
	H[5] += f
	H[6] += g
	H[7] += h

print''.join(map(lambda x:'%08x'%(x&0xFFFFFFFF), H))

コードを短くするという考えを一切捨てて、取りあえず動くもの。動くもの、といっても上記コードは入力データに制限がある。全部読めよ、という気もするが、データ長を入れるところも端折っているのでまあいいか。
で、これを短くする。いきなり短い(汚い)コードにすると後々困ることになるが、取りあえずどの程度短くなるかを確認する。

import os
M=0xFFFFFFFF
r=range
H=[0x6a09e667,0xbb67ae85,0x3c6ef372,0xa54ff53a,0x510e527f,0x9b05688c,0x1f83d9ab,0x5be0cd19]
S=lambda x,n:(M&x)>>n
R=lambda x,n:(M&x)>>n|x<<32-n
x=map(ord,os.read(0,9999))+[0x80]
l=len(x)
i=z=0
t=[]
while i<l:
	z|=(x[i]<<(24-(i%4)*8));i+=1
	if i%4==0:t+=[z];z=0
if i%4:t+=[z]
s=len(t)
while(s+2)%16:t+=[0];s+=1
t+=[0,8*l-8]
w=[]
for i in r(0,len(t),16):w+=[t[i:i+16]]
for m in w:
	a,b,c,d,e,f,g,h=H;m+=[0]*48
	for t in r(16,64):x=m[t-15];y=m[t-2];m[t]=(R(y,17)^R(y,19)^S(y,10))+m[t-7]+(R(x,7)^R(x,18)^S(x,3))+m[t-16]
	for t in r(64):T1=h+(R(e,6)^R(e,11)^R(e,25))+(e&f^~e&g)+[0x428a2f98,0x71374491,0xb5c0fbcf,0xe9b5dba5,0x3956c25b,0x59f111f1,0x923f82a4,0xab1c5ed5,0xd807aa98,0x12835b01,0x243185be,0x550c7dc3,0x72be5d74,0x80deb1fe,0x9bdc06a7,0xc19bf174,0xe49b69c1,0xefbe4786,0x0fc19dc6,0x240ca1cc,0x2de92c6f,0x4a7484aa,0x5cb0a9dc,0x76f988da,0x983e5152,0xa831c66d,0xb00327c8,0xbf597fc7,0xc6e00bf3,0xd5a79147,0x06ca6351,0x14292967,0x27b70a85,0x2e1b2138,0x4d2c6dfc,0x53380d13,0x650a7354,0x766a0abb,0x81c2c92e,0x92722c85,0xa2bfe8a1,0xa81a664b,0xc24b8b70,0xc76c51a3,0xd192e819,0xd6990624,0xf40e3585,0x106aa070,0x19a4c116,0x1e376c08,0x2748774c,0x34b0bcb5,0x391c0cb3,0x4ed8aa4a,0x5b9cca4f,0x682e6ff3,0x748f82ee,0x78a5636f,0x84c87814,0x8cc70208,0x90befffa,0xa4506ceb,0xbef9a3f7,0xc67178f2][t]+m[t];T2=(R(a,2)^R(a,13)^R(a,22))+(a&b^a&c^b&c);h=g;g=f;f=e;e=d+T1;d=c;c=b;b=a;a=T1+T2
	H[0]+=a;H[1]+=b;H[2]+=c;H[3]+=d;H[4]+=e;H[5]+=f;H[6]+=g;H[7]+=h
print''.join(map(lambda x:'%08x'%(x&M), H))

この段階で1507byte。pythonのトップは468byte。まさに問題外。土俵に上がれてすらいない。定数Kのテーブルサイズだけで700byteを超えるので、どう足掻いても無理なようだ。よって、単純な短縮をする前に考え直し。
まず定数Kの参照方法を変える。

def K():
	k=0xc67178f2bef9a3f7a4506ceb90befffa8cc7020884c8781478a5636f748f82ee682e6ff35b9cca4f4ed8aa4a391c0cb334b0bcb52748774c1e376c0819a4c116106aa070f40e3585d6990624d192e819c76c51a3c24b8b70a81a664ba2bfe8a192722c8581c2c92e766a0abb650a735453380d134d2c6dfc2e1b213827b70a851429296706ca6351d5a79147c6e00bf3bf597fc7b00327c8a831c66d983e515276f988da5cb0a9dc4a7484aa2de92c6f240ca1cc0fc19dc6efbe4786e49b69c1c19bf1749bdc06a780deb1fe72be5d74550c7dc3243185be12835b01d807aa98ab1c5ed5923f82a459f111f13956c25be9b5dba5b5c0fbcf71374491428a2f98
	while 1:yield k;k>>=32

こんな感じにジェネレータを作ってみる。

import os
M=0xFFFFFFFF
r=range
q=16
H=[0x6a09e667,0xbb67ae85,0x3c6ef372,0xa54ff53a,0x510e527f,0x9b05688c,0x1f83d9ab,0x5be0cd19]
S=lambda n:(M&x)>>n
R=lambda n:S(n)|x>>32-n
def K():
	k=0xc67178f2bef9a3f7a4506ceb90befffa8cc7020884c8781478a5636f748f82ee682e6ff35b9cca4f4ed8aa4a391c0cb334b0bcb52748774c1e376c0819a4c116106aa070f40e3585d6990624d192e819c76c51a3c24b8b70a81a664ba2bfe8a192722c8581c2c92e766a0abb650a735453380d134d2c6dfc2e1b213827b70a851429296706ca6351d5a79147c6e00bf3bf597fc7b00327c8a831c66d983e515276f988da5cb0a9dc4a7484aa2de92c6f240ca1cc0fc19dc6efbe4786e49b69c1c19bf1749bdc06a780deb1fe72be5d74550c7dc3243185be12835b01d807aa98ab1c5ed5923f82a459f111f13956c25be9b5dba5b5c0fbcf71374491428a2f98
	while 1:yield k;k>>=32
i=z=0
t=[]
for c in os.read(0,9999)+'\x80':
	z|=ord(c)>>24-i%4*8;i+=1
	if i%4==0:t+=[z];z=0
if i%4:t+=[z]
t+=[0]*((q-len(t)-2%q)%q)+[0,8*i-8]
for m in[t[i:i+q]for i in r(0,len(t),q)]:
	a,b,c,d,e,f,g,h=H
	for t in r(q,64):x=m[t-2];A=R(17)^R(19)^S(10);x=m[t-15];m+=[A+m[t-7]+(R(7)^R(18)^S(3))+m[t-q]]
	for k,t in zip(K(),r(64)):x=e;T=h+(R(6)^R(11)^R(25))+(e&f^~e&g)+k+m[t];x=a;U=(R(2)^R(13)^R(22))+(a&b^a&c^b&c);a,b,c,d,e,f,g,h=T+U,a,b,c,d+T,e,f,g
	H=map(sum,zip(H,(a,b,c,d,e,f,g,h)))
print''.join(map(lambda x:'%08x'%(x&M),H))

その他色々弄って、1248byte。lambdaのあまりの文脈依存っぷりに自分でも驚くが、依然として話にならない。
もう少しまじめに。FIPS 180-2による定数Kの定義は以下の通り。

These words represent the first thirty-two bits of the fractional parts of the cube roots of the first sixtyfour prime numbers.

…へぇ。何？素数の立方根？64個の素数？64個目？なんだか分からないが、おそらくこれは動的に生成出来る、気がする。
と言うわけで、この定義について、色々動かして確認して予想する。最初の素数である2から64個分の素数の立方根の小数部分のことか？というあたりを付けて確認。

def K():
	for p in 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311:
		t=0;n=p**(1.0/3)
		for j in r(8):n*=16;t=t<<4|int(n)
		yield t

結果、正解。上記ジェネレータで定数Kが取得できた。ベースとなるテーブルサイズは226byte。かなり小さくなった。
226byteより小さいサイズで素数を求める事が出来ればさらに小さくなるはず。…で、素数ってどうやって求めるの？

def P():
	yield 2;p=3
	while 1:
		d=2
		while d<p:
			if p%d==0:break
			d+=1
		else:yield p
		p+=2

単純に割っていく方法しか知らないのでそれで実装。よく分からないので改良の余地を多分に残しているであろうコードだが、テーブルサイズよりは小さい。とりあえずコレでやってみる。

import os
M=0xFFFFFFFF
r=range
q=16
H=[0x6a09e667,0xbb67ae85,0x3c6ef372,0xa54ff53a,0x510e527f,0x9b05688c,0x1f83d9ab,0x5be0cd19]
S=lambda n:(M&x)>>n
R=lambda n:S(n)|x<<32-n
def P(p):
	yield 2
	while 1:
		d=2
		while p%d and d<p:d+=1
		if p==d:yield p
		p+=2
def K():
	for p in P(3):
		t=0;n=p**(1.0/3)
		for j in[0]*8:n*=16;t=t<<4|int(n)
		yield t
i=z=0
t=[]
for c in os.read(0,9999)+'\x80':
	z|=ord(c)<<24-i%4*8;i+=1
	if i%4==0:t+=[z];z=0
if i%4:t+=[z]
t+=[0]*((q-len(t)-2%q)%q)+[0,8*i-8]
for m in[t[i:i+q]for i in r(0,len(t),q)]:
	a,b,c,d,e,f,g,h=H
	for t in r(q,64):x=m[t-2];A=R(17)^R(19)^S(10);x=m[t-15];m+=[A+m[t-7]+(R(7)^R(18)^S(3))+m[t-q]]
	for k,t in zip(K(),r(64)):x=e;T=h+(R(6)^R(11)^R(25))+(e&f^~e&g)+k+m[t];x=a;U=(R(2)^R(13)^R(22))+(a&b^a&c^b&c);a,b,c,d,e,f,g,h=T+U,a,b,c,d+T,e,f,g
	H=map(sum,zip(H,(a,b,c,d,e,f,g,h)))
print''.join(map(lambda x:'%08x'%(x&M),H))

ジェネレータを若干弄って組み込んで、872byte。かなり短くなったはずだが、それでもトップの倍近いサイズ。もうちょっと細かくみないとダメか。

チーッス。Choose。チューズ。何コレ？
えー、入力がn, kである場合、n!/(k!(n-k)!)を求めればいいらしい。組み合わせのnCr。では。

I=input()
f=lambda x:x and x*f(x-1)or 1
print f(I[0])/f(I[1])/f(I[0]-I[1])

Pascal's Triangleで使った階乗がそのまま使えたので使ってみる。で、74byte。pythonのトップは39byte。オオゥ。どうにか弄ろう。

n,k=input()
f=lambda x:x and x*f(x-1)or 1
print f(n)/f(k)/f(n-k)

リストにする必要はまるでなかったので修正。が、まだ64byte。単純なだけに問題が浮き彫りになる。nCrの計算をもっとシンプルに出来る方法があるのか、あるいは階乗の計算の方か。
例えば、再帰を使わずに。

n,k=input()
f=lambda a:a and reduce(lambda x,y:x*y,range(1,a+1))or 1
print f(n)/f(k)/f(n-k)

これだと92byte。長すぎる。

Pascal's Triangleと併せて考え直した方が良さそう。

次はPascal's Triangle。パスカルの三角形。明確な定義はググるべきではあるが、必要な出力は以下のような感じ。

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1

上の二つを加算。このルールに則って34行出力する。と書けば分かるか。では。

T=[0]
i=1
while i<35:
	v=[0]*34
	for j in range(i):v[j]=T[j]+T[j-1]or 1
	print' '.join(map(str,filter(lambda x:x,v)))
	T=v;i+=1

これで127byte。pythonのトップは63byte。単純なだけにえらく短い。

T=1,0
i=1
while i<35:
	v=[0]*34
	for j in range(i):v[j]=T[j]+T[j-1];print v[j],
	print;T=v;i+=1

95byte。もっとそれらしく考えるべきなのか。

f=lambda x:x and x*f(x-1)or 1
for n in range(34):
	for r in range(n+1):print f(n)/f(r)/f(n-r),
	print

nCrで101byte。増えた。どっちに焦点を当てて行くべきか。

ニン。続いてはTotal Triangles。
数値で構成された三角形の頂点から下辺までのルート(位置的に下になる数値2つのみを通ることが可能)で最大となる値を求めればよい。
例えば、入力が下記の通りである場合、

   4
  4 1
 1 4 1
1 4 1 1

最大となるルートは

   4
  4 1
 1 4 1
1 4 1 1

となるので、求める答えは16となる。なお、実際の入力値は左詰した状態となっている。

4
4 1
1 4 1
1 4 1 1

こんな感じ。では第一弾。

import sys
I=[map(int, x.split())for x in sys.stdin]
T=[0]*99
for v in I:
	q=[0]*99
	i=0
	for c in v:
		q[i]=max(T[i],T[i-1])+c
		i+=1
	T=q
print max(T)

例によって99という数値に根拠はない、ということもない。最大で50行との事なので十分。これで152byte。pythonのトップは、99byte。まさに桁違い。

import sys
T=[0]
for l in sys.stdin:
	q=[0]*99;i=0
	for c in l.split():q[i]=max(T[i],T[i-1])+int(c);i+=1
	T=q
print max(T)

入力周りを刷新。122byte。まだか。

import sys
T=[0]*99
for l in sys.stdin:T=map(lambda x,i:max(T[i],T[i-1])+int(x or 0),l.split(),range(99))
print max(T)

ループを1つ消してみる。これで118byte。maxの引数をどうにか出来そうな気がするのだが、どうにもこうにも。