2019 2/3

『いまさらですがソ連邦』★★★★

 速水螺旋人(著、イラスト)、津久田重吾(著)。Kindle Unlimitedのキャンペーンで読んだけど、面白かった。

『数学パズル大図鑑: 名問・難問を解いて楽しむパズルの思考と歴史』★★

 イワン・モスコビッチ著。フルカラーかつ大きめで楽しい。パズル的にも水準高し。

『交雑する人類―古代DNAが解き明かす新サピエンス史』★★

 デイヴィッド・ライク著。専門的。個別にはすでにぽつぽつ漏れ聞いてる内容が多かったけど面白い。

『ぼくたちに、もうモノは必要ない。 – 断捨離からミニマリストへ』★

 佐々木典士著。妻経由。男性視点の断捨離本は珍しい(?)ので。アイリスオーヤマのエアリーマットレスとやらがいいというので子供の敷き布団として買ってみたが、確かによかった。

『世界一シンプルで科学的に証明された究極の食事』★★★

 津川友介著。個人的に改めて特にこれという内容はなかったが、このタイトルで名前負けしてないだけでも十分か。

『タコの心身問題――頭足類から考える意識の起源』★★★

 ピーター・ゴドフリー=スミス著。原題”Other Minds: The Octopus, the Sea, and the Deep Origins of Consciousness”(『異なる心:蛸・海・意識の深い起源』)まだまだこれからの話だと思うが興味深い。

『若い読者のための経済学史』★

 ナイアル・キシテイニー著。タイトル通りの内容。中高生にもいいかも。

『鳥居りんこの親の介護は知らなきゃバカ見ることだらけーーー申請から施設探しまで、介護初心者には想定外の事態が待っていた!』★

 まだ具体的に必要にはなっていないが、心構えとしては役に立った。

by 木戸孝紀 tags:

2014 10/15

37ピース クムクムパズル 妖怪ウォッチ ジバニャン KM-54

 なんで流行ってるんだと思ってアニメを見始めた『妖怪ウォッチ』だが、しっかりハマっちゃってたりする。こんなフィギュア(?)まで買っちゃったりして。

 しかし、ポケモンの後継としても、子供向けアニメのムーブメントとしても、容易ならぬものではないかなこれ。

 特に根拠はないが、体感ではちびまる子ちゃんもクレヨンしんちゃんも軽く超えてるし、ドラえもん、ドラゴンボール、アラレちゃんぐらいまでさかのぼらないと比較対象ないような気がする。

by 木戸孝紀 tags:

2014 5/19

プログラマの数学

 珍しくCodeIQの問題をやってみたので回答期限と同時にここでも発表。コードは以下。

見積もり

 ダブりを考慮しない場合、ありうるプランの総数は、


2^162 ≒ 5.8 * 10^48

 もある。いくらダブりを省けるといっても、可能なプランを全て作って互いに比較していくようなやり方で正解を見つけるのは難しそう。

下準備

 まず計算しやすいように日付を整数に変換しておく。とりあえず1/1からの経過日数で表すことにする。2/29日はデータ中に存在するようなので、うるう年が存在する366日基準で。


1/1 => 0
12/31 => 365

 名前・出国日・帰国日を保持する国クラスを作っておこう。


case class Country(name:String, start:Int, end:Int)

考え方

 可能なチケットが有限である以上、ある日xまでに行ける国の数には上限がある。それを


mc(x)

 と書くことにする。

 問題の条件は12/31までに多くの国に行かせることだから、最終的に求めたいのは、


mc(365)

 であり、1/1の時点ではまだどこにも行ってないので


mc(0) = 0

である。

 一般のmc(x)を求めたい。帰国日がxの国がA, Bの2国あるとしよう、xの日に起こることは、以下の3パターンがありうる。

1.前日からすでに日本にいる
2.A国から帰国する
3.B国から帰国する

1.前日からすでに日本にいる場合

 今日はどこからも帰国していないので「今日までに行ける数」は「昨日までに行けた数」と同じ。


mc(x) = mc(x-1)

2.A国から帰国する場合

 A国に出国する前日(出国日と帰国日が同日になれない条件のため)までに行けた国の数は、


mc(A.start-1)

 と書ける。それにA国に行ってきたので1を足す。


mc(x) = mc(A.start-1) + 1

3.B国から帰国する場合

 2.と同様に、


mc(x) = mc(B.start-1) + 1

 となる。以下同一の帰国日が3ヶ国以上あっても同じ。

 実際のmc(x)はこれらのうち最大の場合の結果なので、擬似コードで書けばこうなる。


mc(x) = max(
	mc(x-1),
	(mc(A.start-1) + 1),
	(mc(B.start-1) + 1)
)

 再帰的なパターンに何か見覚えがある。動的計画法のメモ化再帰にできそうだ。これで最大国数が計算できる。しかも数字の1ではなく国名をリストに追加する計算をすれば、国数だけでなく直接旅程リストが出る。

コード

 本質的な部分は、こうなる。


package com.tkido.ticketgobble

object main extends App {
  import scala.collection.mutable.{Map => MMap}
  
  val countries = Parser("data/tickets.txt")
  val emap = countries.groupBy(_.end)
  
  val memo = MMap[Int, List[Country]]()
  def mc(day:Int) :List[Country] = {
    if(memo.contains(day)){
      memo(day)
    }else{
      val rst =
        if(day < 0)
          List()
        else if(emap.contains(day))
          ( mc(day-1) :: emap(day).map(c => c :: mc(c.start - 1)) ).maxBy(_.size)
        else
          mc(day-1)
      memo(day) = rst
      rst
    }
  }
  val list = mc(365)
  
  println("%d %s".format(list.size, list.map(_.name).sorted.mkString(" ")))

}

 中でも最も重要なのはこの行


( mc(day-1) :: emap(day).map(c => c :: mc(c.start - 1)) ).maxBy(_.size)

 その日が帰国日の国ごとに「その国の出国日の前日の最高のリストにその国を付け加えたリスト」を作成し、さらに前日の最高のリストをそれに追加し、そこからサイズ最大のリストを選択する。

 ちなみにemapは帰国日からその帰国日を持つ国のリストを引けるようにするマップ。

 これで可能な最大の国に行けるリストが出る。最大の国数になるリストは複数ありそうだが、少なくともそのうちどれかになるはず。もう少しいじれば最大の国に行けるリストを全て出すようにもできそうだが、

あなた「もしも、枚数が同じ複数のプランがあった場合にはどうしましょうか」
依頼者「プランはひとつだけ作っていただければ結構です」

 という問題の条件なので、ここまでで十分のはず。

by 木戸孝紀 tags:

2013 11/11

『すすんでダマされる人たち ネットに潜むカウンターナレッジの危険な罠』★

 ダミアン・トンプソン著。欧米の事例ばかりだが悪くない。『1421』というトンデモ本については存在自体を初めて知った。日本ではそんなに知られていないのかね?

『世紀の相場師ジェシー・リバモア』★★★★

 リチャード・スミッテン著。まず単純に伝記としても面白い。投資の参考になる話もあるし、贅沢ぶりとか家族のスポイルぶりとか破滅ぶりの反面教師としても最高。一粒で三度美味しい感じ。

『相場師一代』★★★★

 是川銀蔵著。東証Project経由。もちろんある程度は盛っているのかも知れないが、思わず笑っちゃうぐらい波瀾万丈の人生。私とリバモアとかこの人では、絶対に脳の遺伝子に違いがあると思う。たとえ長者番付に載れるとしても絶対真似できん、というかしたくない。

『ミンスクのにわとり―やわらかな発想を養う100問』★

 ユーリ・B・チェルニャーク著、ロバート・M・ローズ著。よくある数学クイズ本ともいえるが、物理が混じってるのとロシアジョークと結びついているのが特徴的。

『「銅メダル英語」をめざせ!~発想を変えれば今すぐ話せる~』★★

 林則行著。投資の本が良かったので著者つながりで。読む書く話す聞くのうち、話すが一番簡単など、既成観念を崩される部分多し。

『「超」勉強法』★★★★

 野口悠紀雄著。三語にまとめると「面白いことが大事」「全体から部分へ」「8割主義」。言い換えれば「モチベーション」「インターレース」「パレートの法則」。概ね同意だが、子供の頃に読みたかった。並べた2冊は補足程度に。

『株でゼロから30億円稼いだ私の投資法―大株主への道こそ株式投資の本道』★

 遠藤四郎著。やや古い本であり、今日の状況に適用することはできないが、時代が違っても変わらない心構え等の部分だけ有益。

『テンバガーを探せ! 10倍儲かる低位株投資術』★

 鮎川健著。上の本の現代版がこれになる……のかな?

『ファンドマネジメント―マーケットの本質と運用の実際』★

 山崎元著。個人向けの良い本をよく出している方。プロはこういうことまで考えないといかんのね、という参考程度に。

『なぜゴッホは貧乏で、ピカソは金持ちだったのか?』★

 山口揚平著。『なぜか日本人が知らなかった新しい株の本』が良かったので著者つながりで。タイトルにもなっているピカソのエピソードは非常に面白かったが、それ以外はややありがちな感じ。

『みけねこキャラコ』★★

 どいかや著。絵本。なんか好き。

『無印良品は、仕組みが9割 仕事はシンプルにやりなさい』★★★

 松井忠三著。カンブリア宮殿経由。マニュアルというものへの認識がちょっと変わったかも。

『オニールの成長株発掘法【第4版】』★

 ウィリアム・J・オニール著。これをうんと圧縮して日本に適応させれば『伝説のファンドマネージャーが教える株の公式』に近くなるかも。こちらは大部なので、読むならまずそちらからおすすめ。

『ラ・ロシュフコー箴言集』★★

 ラ・ロシュフコー著。何で知ったか忘れたが、なかなか濃い。

by 木戸孝紀 tags:

2011 5/11

オレンジボックス【CEROレーティング「Z」】

 以前3D酔いで断念した『Portal』。

 その後もたまに聞く評判が非常に良いので、動画で見た。ゲームとしてのアイデアもSFとしての世界観も素晴らしかった。自分で初見プレイしたかった。

 それにしても、目から入る画像としてはなにも変わらないはずなのに、自分でプレイしてなければまったく酔わない。理屈では説明はつくが、不思議なものだ。

おまけ

by 木戸孝紀 tags:

2010 9/18

日経サイエンス 2010年 10月号 [雑誌]

 Twitterのmentionで知ったのだが、いつぞやの嘘つき天秤の問題が日経サイエンス2010年10月号に載ってたらしい。

 あれは確かに予想外の良問だったので嬉しいな。Twitterの人と同一なのかは不明だけど、その紹介して下さった読者の方どうもです。

 木戸氏がこの問題をどういう経緯で思いついたかはわからないが,

 とか書かれているけど、自分でも忘れていた。記録を見る限りここのコメント欄での、天さんとのやり取りがきっかけだったみたいだ。

おまけ

by 木戸孝紀 tags:

2010 8/8

プログラミング in OCaml ~関数型プログラミングの基礎からGUI構築まで~

 OCamlの練習に、長年の疑問だった

  • 切符算で解がある全ての組み合わせ

 を求めようとしている。

 ただ、自分の知っているバージョンはローカルルール(?)があり、四則演算と括弧だけではなく、

  • 最初から存在する数字をくっつけて2〜4桁の数字にする

 という操作が可能である。意味があるのは2ケタだけだが。

 まだインチキしているのでコード公開できないけど、とりあえず答えは出たはず。これ合ってる?

0001 0011 0012 0013 0014 0015 0016 0017 0018 0019
0022 0023 0025 0028 0033 0034 0037 0044 0045 0046
0055 0056 0066 0067 0077 0078 0088 0089 0099 0111
0112 0115 0118 0119 0122 0123 0124 0125 0126 0127
0128 0129 0133 0134 0135 0136 0137 0138 0139 0144
0145 0146 0147 0149 0155 0156 0158 0159 0166 0167
0169 0177 0178 0179 0188 0189 0199 0223 0224 0225
0226 0227 0228 0229 0234 0235 0236 0237 0238 0239
0244 0245 0246 0247 0248 0249 0255 0256 0257 0258
0259 0266 0267 0268 0278 0279 0288 0289 0334 0336
0337 0339 0345 0346 0347 0349 0355 0356 0357 0358
0367 0368 0369 0377 0378 0379 0446 0448 0449 0455
0456 0457 0458 0459 0466 0467 0468 0469 0477 0488
0555 0556 0557 0558 0559 0568 0569 0578 0579 0589
0669 0679 0688 0779 0789 0889 0899 0999 1111 1112
1114 1115 1116 1117 1118 1119 1122 1123 1124 1125
1126 1127 1128 1129 1133 1134 1135 1136 1137 1138
1139 1144 1145 1146 1147 1148 1149 1155 1156 1157
1158 1159 1166 1167 1168 1177 1178 1188 1189 1199
1222 1223 1224 1225 1226 1227 1228 1229 1233 1234
1235 1236 1237 1238 1239 1244 1245 1246 1247 1248
1249 1255 1256 1257 1258 1259 1266 1267 1268 1269
1277 1278 1279 1288 1289 1299 1333 1334 1335 1336
1337 1338 1339 1344 1345 1346 1347 1348 1349 1355
1356 1357 1358 1359 1366 1367 1368 1369 1377 1378
1379 1388 1389 1444 1445 1446 1447 1448 1449 1455
1456 1457 1458 1459 1466 1467 1468 1469 1477 1478
1479 1488 1489 1555 1556 1557 1558 1559 1566 1567
1568 1569 1577 1578 1579 1588 1589 1599 1666 1668
1669 1678 1679 1688 1689 1777 1778 1779 1788 1789
1799 1888 1889 1899 1999 2222 2223 2224 2225 2226
2227 2228 2229 2233 2234 2235 2236 2237 2238 2239
2244 2245 2246 2247 2248 2249 2255 2256 2257 2258
2259 2266 2267 2268 2269 2277 2278 2279 2288 2289
2299 2333 2334 2335 2336 2337 2338 2339 2344 2345
2346 2347 2348 2349 2355 2356 2357 2358 2359 2366
2367 2368 2369 2377 2378 2379 2388 2389 2399 2444
2445 2446 2447 2448 2449 2455 2456 2457 2458 2459
2466 2467 2468 2469 2477 2478 2479 2488 2489 2499
2555 2556 2557 2558 2559 2566 2567 2568 2569 2577
2578 2579 2588 2589 2599 2666 2667 2668 2669 2677
2678 2679 2688 2689 2699 2777 2778 2779 2788 2789
2799 2888 2889 2899 2999 3333 3334 3335 3336 3337
3338 3339 3344 3345 3346 3347 3348 3349 3355 3356
3357 3358 3359 3366 3367 3368 3369 3377 3378 3379
3388 3389 3399 3444 3445 3446 3447 3448 3449 3455
3456 3457 3458 3459 3466 3467 3468 3469 3477 3478
3479 3488 3489 3499 3555 3556 3557 3558 3559 3566
3567 3568 3569 3577 3578 3579 3588 3589 3599 3666
3667 3668 3669 3677 3678 3679 3688 3689 3699 3777
3778 3779 3788 3789 3799 3888 3889 3899 4444 4445
4446 4447 4448 4449 4455 4456 4457 4458 4459 4466
4467 4468 4469 4477 4478 4479 4488 4489 4499 4555
4556 4557 4559 4566 4567 4568 4569 4577 4578 4579
4588 4589 4599 4666 4667 4668 4669 4677 4678 4679
4688 4689 4699 4777 4778 4779 4788 4789 4799 4888
4889 5555 5556 5557 5558 5559 5566 5567 5568 5569
5577 5578 5579 5588 5589 5599 5666 5667 5669 5677
5678 5679 5688 5689 5699 5777 5778 5779 5789 5888
5889 5999 6666 6667 6668 6669 6677 6678 6679 6688
6689 6699 6777 6779 6788 6789 6799 6889 7777 7778
7779 7788 7789 7799 7888 7889 7899 8888 8889 8899
8999 9999

参考リンク

おまけ

by 木戸孝紀 tags:

2009 11/8

プログラミング言語 Ruby

 一昨日のパズル。もう終わっちゃってるけど、乱数でのゴリ押しだけでは芸がなさ過ぎるでしょう常識的に考えて……ということで、ちょっと改良した。

 互いに行き着けないノードの数をスコア(当然低い方が良い)として、ステップごとに上位1/4だけ残してそれを4倍に複製。二本のエッジをちょん切ってつなぎ替える。

 N=4で15個の解はわりとすんなり見つけられるようになった。


15個のノード。
30本のエッジ。
0のスコア。
0:[9, 12, 5, 8]
1:[3, 9, 11, 6]
2:[5, 11, 13, 12]
3:[1, 5, 10, 13]
4:[7, 5, 14, 6]
5:[2, 4, 3, 0]
6:[14, 12, 1, 4]
7:[4, 11, 9, 10]
8:[10, 14, 11, 0]
9:[13, 0, 7, 1]
10:[8, 12, 7, 3]
11:[2, 7, 1, 8]
12:[6, 10, 0, 2]
13:[9, 14, 2, 3]
14:[6, 13, 8, 4]

 まだやってないけど、パラメータ設定とかける時間次第ではN=5もいけるかもしれん。

11/9追記

 ちょっと時間かかったけどN=5で24個いけた。populationは800に設定。


24個のノード。
60本のエッジ。
0のスコア。
0:[6, 11, 7, 16, 13]
1:[15, 3, 13, 4, 18]
2:[6, 5, 14, 3, 23]
3:[1, 7, 20, 2, 11]
4:[19, 13, 17, 1, 5]
5:[2, 16, 4, 12, 10]
6:[2, 0, 23, 15, 19]
7:[17, 21, 0, 3, 10]
8:[12, 10, 23, 13, 20]
9:[14, 20, 17, 15, 16]
10:[8, 22, 15, 7, 5]
11:[12, 0, 22, 3, 17]
12:[8, 11, 21, 15, 5]
13:[14, 4, 1, 8, 0]
14:[13, 9, 21, 2, 22]
15:[1, 6, 9, 12, 10]
16:[20, 0, 5, 18, 9]
17:[23, 7, 4, 9, 11]
18:[23, 21, 1, 22, 16]
19:[20, 22, 4, 6, 21]
20:[19, 16, 9, 3, 8]
21:[7, 18, 14, 12, 19]
22:[19, 10, 11, 14, 18]
23:[18, 17, 8, 6, 2]

おまけ

 もうすぐCDが出るらしい。

by 木戸孝紀 tags: