脳log[2011-03-03～]

最終更新: 2011-03-04T22:27+0900

♪ 20110223p01の続き。

認証結果(GET/POSTデータ)の再利用によるなりすましを防ぐために nonceを使うのが一般的。でもそうするとコメントのプレビュー時にはまだ認証ができないことになる。事前に認証してしまったら自分自身がその結果を再利用するかたちになるから。tDiaryはアカウントやログインって概念を管理してないから OpenIDによる認証結果をそれらと結びつけて持続させることができない。認証とコメントの投稿が同時のぶっつけ本番。書き込み前にどういう表示になるのかはやっぱり知りたいよ。

Bloggerの解。

表示名には、OpenID プロバイダから Google に送信されたあなたの名前が使用されます。表示名がない場合は、OpenID の URL から表示名の取得を試みます。

Blogger で OpenID を使用してコメントを書き込む - Blogger ヘルプ

こういう割り切りが必要なのかな。でも Yahoo!!!なんかは味気ない URLしか返してこないよね(※1)。mixiしか聞かない、表示名が取得できたってのは。もちろん、myOpenIDもユーザーフレンドリーな名前を返す。ペルソナをかぶることすらできるから選んだ。OpenID Providerとしての Googleはひと味違って claimed_idが realmごとに固有のものに変化するらしい(※2)。Webサービスからすると、ユーザーをリダイレクトしたときと返ってきたときの claimed_idが変わったように見える。OpenIDをいろんなサービスへのログイン手段としてだけみるなら、余分な情報を渡さないのはメリット。自己紹介として URLを提示したときにはそれと違うものが claimed_idとして Webアプリに渡るのはデメリット。さて、独自ドメインの URLを提示しておいて、そのドメインから Googleへ認証を delegateした場合の claimed_idはどうなる？

※1 知らぬ間に AX(Attribute Exchange)に対応してた。「Yahoo! JAPAN、OpenIDでプロフィール情報を提供　拡張仕様「AX」「UI」に対応：CodeZine」でも、SREGには対応しないってどういうこと？ AXの汎用性は却って対応が面倒なんだけど。「Attribute Exchange のメモ - Yet Another Hackadelic」定義済みのシェーマがあるらしいが、すでに二つもある。

※2 もっとも、そのことを知ったのはこういうタイトルの記事。「OpenIDでGoogleからグローバルユニークなユーザー識別子を取得できるかもしれない方法 - r-weblife」realm(Webサービスのドメイン)固有の claimed_id ↔ 「グローバルユニークなユーザー識別子」

閑話休題。nonceをワンタイムでなく時限式にするしかないのだろうか。タイムアウトって嫌いなんだけど。

 @2011-03-04

OpenID Providerへコメントの全文ごとユーザーをリダイレクトするのはまずいかなと思って、通常通りコメントを保存した後でリダイレクトし、正しく認証されて返ってきたときに、その印としてコメントに OP名を付与することを考えた。問題はその認証がどのコメントに対するものなのかだ。ユーザーを送り出すときに「このパラメータと一緒に返ってきてね」ということはできるが……。コメントを他者が推測できない UUIDみたいなものとともに保存しておいてユーザーにそれを運んでもらおうか。(もちろんどの日の日記に対するコメントなのかを表すパラメータもユーザーに運んでもらう)

最終更新: 2011-03-02T05:24+0900

♪ [ProjectEuler] Q61

 Q61

何も考えずにコーディングしただけ。一瞬 CPUが考え込みます。

generators = [
	lambda{ n = 0
		lambda{ n+=1; n*(n+1)/2 }
	}.call,
	lambda{ n = 0
		lambda{ n+=1; n*n }
	}.call,
	lambda{ n = 0
		lambda{ n+=1; n*(3*n-1)/2 }
	}.call,
	lambda{ n = 0
		lambda{ n+=1; n*(2*n-1) }
	}.call,
	lambda{ n = 0
		lambda{ n+=1; n*(5*n-3)/2 }
	}.call,
	lambda{ n = 0
		lambda{ n+=1; n*(3*n-2) }
	}.call,
]
# 数を準備
d4polynumbers = generators.map{|g|
	() while (p = g.call) < 1000
	a = [p]
	a.push(p) while (p = g.call) < 10000
	a
}
# 端緒(の集まり)
bunch_of_chain = d4polynumbers[d4polynumbers.size-1].map{|p|
	[[p, d4polynumbers.size-1]]
}
# 端緒を伸ばすもの
extender = lambda{|chain, pool|
	xx = chain.last.first.to_s[-2,2]
	( (0...(pool.size)).to_a - chain.map{|_| _.last } ).map{|i|
		[i, pool[i]]
	}.map{|i, nums|
		nums.find_all{|num|
			num.to_s[0,2] == xx
		}.map{|num|
			chain + [[num, i]]
		}
	}.inject(&:+)
}
# 伸ばしていく
(d4polynumbers.size-1).times{
	bunch_of_chain = bunch_of_chain.map{|chain|
		extender[chain, d4polynumbers]
	}.inject(&:+)
}
# 輪っか？
bunch_of_cyclic_chain = bunch_of_chain.reject{|chain|
	chain.first.first.to_s[0,2] != chain.last.first.to_s[-2,2]
}
# 出力
bunch_of_cyclic_chain.each{|chain|
	puts chain.map{|a,_| a }.join("\t")
	puts chain.map{|_,b| "P#{b+3}" }.join("\t")
	puts "sum: #{chain.map{|a,_| a }.inject(&:+)}"
}

先は長いのにもう失速してる。「良いもの。悪いもの。: Project Eulerを100問解いてみた」テトレーションとか聞いたこともない単語なんだけど……。

中学生の時に $3^{50}$ の一の位は何かという問題が出た。でも Problem 188は何乗したらいいかもわからない。下手の考え休むに似たりっていうけどどうしたもんかなあ。ない知恵を絞るのも悪くないと思うんだけど。

最終更新: 2011-08-08T21:28+0900

♪ myOpenID (www.myopenid.com)に登録した。

目当てはペルソナ機能。OpenIDは自分が何者かを名乗るためのもので、また他人に自分の名を騙らせないためのものだと思っている。だもんで、IDとなる URLとは別に表示名として、どう名乗るのかを対象 Webアプリごとに選べるペルソナ機能は魅力。

OpenIDについて認証結果(Webアプリに対する GET/POSTリクエスト)の改ざんを防ぐ仕組みと再利用を防ぐ仕組みを勉強した。再利用が悪なのかはわからないけど。

日記データとしては openid.claimed_idと openid.sreg.email, openid.sreg.nicknameを保存するとする。email, nicknameは従来の自由入力欄と同じ扱い。オプションだし自由に書き換えられる。認証と同時に取得できたらそれをデフォルト値にするってだけ。URLの形をした openid.claimed_idはこれまでなかったもので、ユーザーの識別情報として使いなりすましを排除する。と同時にユーザーのホームページであることが期待される。Facebookやはてなダイアリーなど、人となりがわかる主たる活動場の URL。俺だったら「http://vvvvvv.sakura.ne.jp/ds14050/ (identified by www.myopenid.com)」となる。本当はアイコンも取得してそのリンク先を claimed_idとしたい。URLは表示するには長すぎる。

Cookieには openid.claimed_idを保存しておいて、ダメ元で JavaScriptに immediateモードで認証を行わせると二回目から便利かも。どういうフローだと迷わず最小の手間でコメントを投稿できるだろう。Webサービスを利用した経験が皆無で模範が思い浮かばない。

最終更新: 2011-02-20T21:45+0900

♪ [ProjectEuler] Q58, Q59, Q60

 Q58

10%未満っていうのは絶妙なポイントなのかな。全然 9%未満に落ちない。

def prime? x
	return false if x < 2
	return true if x == 2
	quo, rem = x.divmod(2)
	return false if rem == 0
	t = 1
	while t < quo
		t += 2
		quo, rem = x.divmod(t)
		return false if rem == 0
	end
	return true
end

x, t = 1, 0
primes_on_diagonals = 0
loop{
	t += 2
	3.times{
		x += t
		primes_on_diagonals += 1 if prime? x
	}
	x += t
	puts "#{primes_on_diagonals} primes out of #{2*t+1} (#{100*primes_on_diagonals/(2*t+1)}%, side length=#{t+1})"
	exit if 100 * primes_on_diagonals / (2*t+1) < 10
}

 Q59

1. 暗号化キーの長さが 3文字なのがわかってるので、数列を 3列に並べて各列を眺める。
2. 英単語には eが一番使われるとか、単語では theが再頻出だとかの統計データがあるらしい。(と書いてあるのを何度も目にしたが実際のデータは見たことがない)
3. 文章なら文字としてはスペースが一番多いはずだ。
4. 単語で theが一番多いなら、theの前後の空白は右下に向いて、(1行1列目)↘(2行2列目), (1行2列目)↘(2行3列目), (1行3列目)↘(2行1列目) の並びで現れるはずだ。
5. というかんじでマジックナンバーが出てきた。
6. あ、問題文のサマリに「Using a brute force attack, can you ...」って書いてある。しまった。

encrypted_text = [79,59,12,...,22,73,0,0] # last 2 elements are padding.
text = ""
0.step(encrypted_text.size-1, 3){|i|
	text += (encrypted_text[i+0] ^ (71 ^ " "[0])).chr
	text += (encrypted_text[i+1] ^ (79 ^ " "[0])).chr
	text += (encrypted_text[i+2] ^ (68 ^ " "[0])).chr
}
text.chop!.chop! # remove padding
puts text
puts "sum: #{text.bytes.inject(:+)}"

 Q60

1. 素数二つ(A,B)に分割できてローテートしても素数な素数(AB,BA)。⇒ a set of 2 primes (A,B)
2. (AX,XA),(BX,XB)が 1の条件を満たす 2 sets of 2 primes が見つかる。⇒ a set of 3 primes (A,B,X)
3. (AY,YA),(BY,YB),(XY,YX)が 1の条件を満たす 3 sets of 2 primesが見つかる。⇒ a set of 4 primes (A,B,X,Y)
4. (AZ,ZA),(BZ,ZB),(XZ,ZX),(YZ,ZY)が 1の条件を満たす 4 sets of 2 primesが見つかる。⇒ a set of 5 primes (A,B,X,Y,Z)

1を満たす素数を発見しながらそれを使って、1の集合から2へ、2の集合から3へ、3の集合から4へ、要素をプロモートしていけばよさそう。

# 寝る前にやる。

寝てしまった。答えが出ない。素数を分割するんでなく、素数のペアを組み合わせて素数かどうか判定した方がいいかもしれない。そろそろ身にしみて理解してきたけど、素数って印象よりありふれ過ぎてる。

 @2011-02-17

ちょっとくらい時間がかかってもいーやって考えてたけど、何日もかけても四つ組みが 7つと、五つ組が 0個しか見つからないことがわかったので、1分以内に答えを出すべくもうちょっと考える。

1. 小中学生の頃に読んだ数字遊びの本から得た知識によれば、10進表記の各桁の和が 3の倍数の数はそれ自体も 3の倍数だという。だというwww
2. 各桁の和を 3で割った余りが 0の素数は 3だけ。
3. 各桁の和を 3で割った余りが 1の素数と 2の素数を組にすると、それをつなげた数は 3の倍数になってしまい素数ではなくなるので組にできない。
4. 各桁の和を 3で割った余りで素数を分類すると 5つ組みとして考えられるのは (0,1,1,1,1), (0,2,2,2,2), (1,1,1,1,1), (2,2,2,2,2)の 4パターンだけ。
5. 3桁までの素数で総当たりしてみよう。
6. 見つからなかったので 4桁までで総当たり。

def prime? x
	return false if x < 2
	return true if x == 2
	quo, rem = x.divmod(2)
	return false if rem == 0
	t = 1
	while t < quo
		t += 2
		quo, rem = x.divmod(t)
		return false if rem == 0
	end
	return true
end

set012 = [[],[3],[]]
require 'mathn'
Prime.new.each{|prime|
	break if 10000 <= prime
	dmod3 = prime.to_s.bytes.inject(0){|sum,byte| sum+byte-?0 } % 3
	set012[dmod3] << prime
}
set1, set2 = set012[1], set012[2]
set2[0] = 3
# set1 = [3,7,13,...]
# set2 = [3,5,11,...]

make_group_of_two = lambda{|set|
	pair = {}
	0.upto(set.size-2){|i|
		(i+1).upto(set.size-1){|j|
			if prime?("#{set[i]}#{set[j]}".to_i) and prime?("#{set[j]}#{set[i]}".to_i) 
				(pair[[set[i]]]||=[]) << set[j]
			end
		}
	}
	return pair
}
group1, group2 = make_group_of_two.call(set1), make_group_of_two.call(set2)

extend_group = lambda{|g|
	group = {}
	g.each_pair{|rest, last1s| # rest + one of last1s = group
		last1s.each{|last1|
			next1s = last1s
			gg, out = rest.clone, last1
			gg.size.times{|i|
				gg[gg.size-1-i], out = out, gg[gg.size-1-i]
				next1s &= g[gg]||[]
			}
			if ! next1s.empty?
				group[rest+[last1]] = next1s
			end
		}
	}
	return group
}
group1, group2 = extend_group.call(group1), extend_group.call(group2) # sets of 3 primes
group1, group2 = extend_group.call(group1), extend_group.call(group2) # sets of 4 primes
group1, group2 = extend_group.call(group1), extend_group.call(group2) # sets of 5 primes

printer = lambda{|rest, last1s|
	last1s.each{|last1|
		puts %[#{rest.inject(&:+)+last1}:\t#{rest.join("\t")}\t#{last1}]
	}
}
group1.each(&printer)
group2.each(&printer)

分単位の時間で答えはでたけどもその五つ組の合計が意外に大きくて、10000以上の素数を組に加えても最小の組み合わせになりうる。計算量の増大の仕方がひどくて、これ以上桁数を増やして試行するのは無理だというのに。

 「だという わらわらわら」@昨日

じゃないよね。

$$\begin{array}{rcl}q& =& a_0+10a_1+{10}^2{a}_2+\dots \dots +{10}^n{a}_n\text{(}{a}_n\text{は 0以上 9以下の整数)}\\ & =& (a_0+a_1+a_2+\dots \dots +a_n)+9a_1+99a_2+\dots \dots +({10}^n-1)a_n\end{array}$$

$a_0+a_1+a_2+\dots \dots +a_n$ が 3の倍数の整数 qは 3の倍数です。

たしか 4の倍数についても同じような判定規則があった気がした。忘れたけど。

たしか 5の倍数についてもどこかの桁を見るだけで(略

 @2011-02-19

4は 100を作るから下2桁だけ。5は 10を作るから下1桁だけを見ればいい。

 「計算量の増大の仕方がひどくて」

一番時間を食ってるのは make_group_of_two. 異なる二要素の組み合わせということで $n^2-n$ 回の素数判定を行ってる。素数判定自体も nの大きさに比例する(※1:1ではないけど)ループを持っている。大変なはずだ。

とりあえず、今の素数判定より賢い素数判定があるのはわかってるけどわからないので使ってない。(注:わかる => 知ってる, 理解できる) 丁寧にコードを読んだらわかるかもだけどそれはチートっぽい。大学入試の数論関係の問題だって、解答をチラ見したら誰だって理解できんだよ。

最終更新: 2011-02-13T04:35+0900

♪ やばかった。

7500の正の約数は何個あるか。

Fラン大学の実態:ハムスター速報

素因数の数を数えてしまってた。その間違いに気づいたら今度は、1って約数に数えるの？その数自身も約数のうち？なんて、約数の定義が消えかかってる。(補足。素数の定義を思い出せば疑問は解ける)

復習～。

1. 7500 = 5×5×5×5×3×2×2
2. 約数は $5^i\times 3^j\times 2^k$ (i=0,1,2,3,4, j=0,1, k=0,1,2) で表される。(0乗が 1とか、0の階乗が 1とか、何気に落とし穴)
3. 組み合わせは 5×2×3 = 30通り
4. 重複はないので約数の数も 30個。
5. たぶん。

コメントに↑そのまんま書いてあった(変数名まで一緒)。無駄なエントリになってしまった。

最終更新: 2012-12-12T02:17+0900

♪ [tDiary] MathMLが使いたかったので。>「ひらくの工房 - tDiary XHTML化キット」

• HTMLモードなんていらないから拡張子は xhtmlでなく htmlで、とか
• \times より × って書きたい、とか
• <option selected="selected"> <input checked="checked"> みたいに属性名を省略してない HTMLもあるのよ、置換しすぎないで、とか

適当にカスタマイズして設置した。

XHTML化キットの存在は投稿されたアナウンスを読んで知ってたんだけど、XHTML好きにもかかわらず今まで導入してなかったのは、日記に数式を書く機会がなかったのと、出力段階での文字列置換による XHTML化が乱暴に思えたから。結局、他に方法がないので目をつぶったが。

閲覧不可能になった日記がないか月別表示で全日記を表示してみたら 10か所くらい見つかった。パターンは以下の通り。

• プラグインが埋め込む JavaScriptに含まれる & 記号
• etDiaryスタイルがエスケープしてくれなかった本文中の & 記号
• プラグイン記法( {{～}} )で直接埋め込んだ HTML片に含まれる & 記号

 JavaScriptの &

<script>タグの中であっても & は &amp; と書かなければいけない。不等号も。でも if(a && b) {} とか置換してしまったらアホだ。CDATAセクションを使う。

scriptタグが解釈できないブラウザなんて PCを手に入れた当時から持ってなかったので

<script><!--
--></script>

なんて最初から書かなかったし、XHTMLを知ってからは下のように書くことにしてる。

<script>/*<![CDATA[*/
/*]]>*/</script>

コメントで囲うのは JavaScriptとして正しくあるため。より字数の少ない行コメントにしないのは、なにかでエラーになったから。MSがリリースしてた JavaScriptを暗号化(難読化)するツールに <script>タグを含んだ HTMLファイルを通したときだったか……。

 etDiaryの &

但し書きを付けても無駄。HTMLと日本語は混ぜるな危険。中途半端な HTMLの隠蔽は悪。tDiaryスタイルと etDiaryスタイルより Wikiスタイル。

 手書き HTMLの &

自業自得。さすがに、タグに挟まれた部分に & や <, > を放置してたわけではない。

<a href="ttp://hoge/script.cgi?a=b&c=d">
<img src="ttp://hoge/script.cgi?a=b&c=d">

すべてこの形の & がエラーになっていた。HTMLを出力するスクリプトでは、属性値は機械的に必ず HTMLエスケープするようにしてるんだけど、手書きだと上のような (X)HTMLは正しく見えてしまうのか、忘れられてた。こんなことがあるとやっぱりセミコロンで区切りたいねえ。

それにしても、ちらちら目に入る古い日記が恥ずかしくて死ねる。読む人間も、そもそも読める内容もないのであえて気づかぬふりで放置するけども。

最終更新: 2011-02-12T22:42+0900

♪ [ProjectEuler] Q56, Q57

 Q56

Bignumはできれば使いたくない。aが 100未満なので 8桁ずつ。

answer = [0, 0, 0] # sum, a, b
1.upto(99){|a|
	digits = "1"
	1.upto(99){|b|
		sum = 0
		carry = 0
		0.step(digits.size-1, 8) {|i|
			l, r = [0, digits.size-i-8].max, digits.size-i
			carry, digits8 = (digits[l...r].to_i * a + carry).divmod(100000000)
			digits8 = "00000000#{digits8}"[-8,8]
			digits[l...r] = digits8
			digits8.each_byte{|byte|
				sum += byte - ?0
			}
		}
		if carry != 0
			digits8 = carry.to_s
			digits = digits8 + digits
			digits8.each_byte{|byte|
				sum += byte - ?0
			}
		end
		if answer[0] < sum
			*answer = sum, a, b
		end
	}
}
p answer

 Q57

とかいいながら Bignum。

count = 0
numer, denom = 1, 1
1000.times{
	numer, denom = numer + denom + denom, numer + denom
	count += 1 if numer.to_s.length != denom.to_s.length
}
p count

最終更新: 2011-02-10T23:58+0900

♪ それは無理でしょ。>クロネコヤマト(金沢物流システム支店)

受付は昨日のはずだ。このせいで一切のトラッキングができなくて、今日着くのか明日着くのかがわからなかった。時間帯指定で不在はくらいたくないでしょうに。

最終更新: 2011-02-11T00:59+0900

♪ [SakuraEditor] SourceForge.net Repository - [sakura-editor] Revision 1887

Fix: 検索(ツールバー)を使うとプラグインコマンドが実行される(2)

検索ボックスのコードをほとんどコピーした自作ツールバーボタンもやばい気がするものの、CBN_SELCHANGEはツールバーボタンで処理してるんだよね。処理しなかったメッセージが誤った取り扱いを受ける、ということなんだろうか。わからないよん。

>>脳log[2008-06-04-p01] 現在適用されているファイルタイプを表示/変更するツールバーボタン