Saturday, January 23, 2010

ウェル ダーン

おとうさん、これ なんて よむの?
ウェル ダーン だよ。
え?well done?
そう、ウェル ダーン
じゃあ、なんで well done って いわないの?
うん。いってるんだけどね。
いってないじゃん。well
ウェル
well
ウェル
well
ウェル
もー、ぜんぜん ちがうじゃん。ちゃんと いってよ。
いってるんだけどね...。 well
そうそう。いえるじゃん。
と、ときどきね...。
well done
ウェル ダーン
もー、なんで ウェル ダーン って いうの?
たしか にほん では そう いうんだよ。
へんなの。きょんちゃん アメリカで うまれたから well done って いうの。
いいなあ。

Wednesday, January 20, 2010

1 2 3 4 5 6 7 8 * * - - / / 9 * * = 2010

ちょっと まえに @hariguchi さんが Knuth せんせいの 誕生日ケーキの 写真を twitter に はっていた

Birthday Cake for Don on Twitpic


なるほど、こういう しきって、あと なんとおり くらい あるんだろう、あとで しらべておこう、って おもったんだけれど、そのことを、せんしゅう にほんに かえった ときに おもいだした。

じかんも あったので、さくっと コードを かいて じっこう。ruby で 100ぎょうくらい。とくに 工夫も せずに ぜんぶ しらべたので えらく じかんが かかった。3じかん じゃく。もし 来年 2011 に なる くみあわせを しらべる ことに なったら、そのときには 半分いかの じかんで うごくように 改良してから じっこう したい。

さて、1 + 2 + 3... という くみあわせを すべて つくって それを 順番に しらべていく のは さすがに むちゃ なので、しきは RPN (Reverse Polish Notation) で ためす。かっこが いらないので シンプル。

けっかは、しきの くみあわせは 93,716,480 とおりで、2010 に 一致 したのは そのうち 186 とおり あった。けっこう ある。

  1. 1 2 3 4 5 - 6 7 * 8 * + 9 * / / *
  2. 1 2 3 4 5 + - 6 7 8 * * * - 9 - +
  3. 1 2 3 4 5 + - 6 * 7 8 * * 9 + - +
  4. 1 2 + 3 4 - 5 - 6 * 7 * 8 * 9 + -
  5. 1 2 + 3 4 5 + - 6 7 8 * * * - 9 -
  6. 1 2 * 3 / 4 5 - 6 7 * 8 * + 9 * *
  7. 1 2 3 4 5 + - 6 * 7 * 8 * - 9 - +
  8. 1 2 * 3 / 4 5 + 6 7 * * 8 * 9 - *
  9. 1 2 3 4 5 6 * 7 8 * + * 9 - * * *
  10. 1 2 3 4 5 - 6 7 8 * * + / 9 / / *
  11. 1 2 3 4 5 + - 6 * 7 8 * * - + 9 -
  12. 1 2 - 3 4 5 6 / 7 8 * + * - - 9 *
  13. 1 2 3 / 4 5 - 6 7 * 8 * + 9 * * *
  14. 1 2 3 / * 4 5 + 6 * 7 * 8 * 9 - *
  15. 1 2 * 3 / 4 5 - 6 7 8 * * + * 9 *
  16. 1 2 + 3 4 5 + - 6 7 * * 8 * 9 + -
  17. 1 2 3 / 4 5 6 7 * 8 * - - * 9 * *
  18. 1 2 3 / 4 5 - 6 7 8 * * + 9 * * *
  19. 1 2 * 3 / 4 5 6 7 * 8 * - - 9 * *
  20. 1 2 3 * * 4 5 6 * 7 8 * + * 9 - *
  21. 1 2 - 3 - 4 5 + 6 / 7 8 * 9 * - *
  22. 1 2 3 4 5 6 + * * 7 - * 8 * + 9 +
  23. 1 2 3 4 5 + 6 7 * * 8 * 9 - / / *
  24. 1 2 3 4 5 + - 6 7 * 8 * * - 9 - +
  25. 1 2 3 4 * + + 5 6 7 8 + 9 * - - *
  26. 1 2 + 3 4 5 + - 6 * 7 8 * * - 9 -
  27. 1 2 3 / 4 5 + 6 7 * * 8 * 9 - * *
  28. 1 2 3 + - 4 5 + 6 / 7 8 9 * * - *
  29. 1 2 3 4 5 6 7 8 * * - - / / 9 * *
  30. 1 2 3 4 5 + 6 7 * 8 * * 9 - / / *
  31. 1 2 * 3 4 5 6 7 8 * * - - 9 * / /
  32. 1 2 * 3 4 5 + 6 * 7 8 * * 9 - / /
  33. 1 2 3 / 4 5 - 6 7 * 8 * + * 9 * *
  34. 1 2 3 4 5 6 7 * 8 + + * + 9 * + +
  35. 1 2 3 4 5 - 6 7 8 * * + / / 9 * *
  36. 1 2 3 4 5 + 6 * 7 8 * * 9 - / / *
  37. 1 2 3 / * 4 5 + 6 7 * * 8 * 9 - *
  38. 1 2 3 / 4 5 - 6 7 8 * * + * 9 * *
  39. 1 2 + 3 4 5 6 7 * + 8 + * + 9 * +
  40. 1 2 + 3 4 - 5 - 6 * 7 8 * * - 9 -
  41. 1 2 3 + - 4 5 6 / 7 8 * + * + 9 *
  42. 1 2 3 4 5 6 7 8 * * - - / 9 / / *
  43. 1 2 + 3 4 - 5 - 6 7 8 * * * - 9 -
  44. 1 2 3 4 - 5 - 6 * 7 8 * * - 9 - +
  45. 1 2 3 4 5 + - 6 7 * * + 8 * 9 - -
  46. 1 2 3 4 * 5 6 + * 7 - 8 * * + 9 +
  47. 1 2 3 4 * 5 6 + * 7 - * 8 * 9 + +
  48. 1 2 3 / * 4 5 - 6 7 8 * * + * 9 *
  49. 1 2 3 4 5 + - 6 * 7 * 8 * 9 + - +
  50. 1 2 3 4 - 5 - 6 7 * * + 8 * - 9 +
  51. 1 2 + 3 4 * + 5 6 7 8 + 9 * - - *
  52. 1 2 + 3 4 5 6 - 7 8 * + * + 9 * +
  53. 1 2 * 3 4 5 6 7 8 * * - - / / 9 *
  54. 1 2 3 / * 4 5 6 7 * 8 * - - 9 * *
  55. 1 2 3 + 4 5 6 / 7 8 * + * - - 9 *
  56. 1 2 + 3 4 5 + * 6 + 7 * 8 - 9 * +
  57. 1 2 + 3 4 - 5 - 6 7 * * 8 * 9 + -
  58. 1 2 + 3 4 5 6 + * 7 8 + * 9 + * +
  59. 1 2 3 4 - 5 - 6 * 7 * + 8 * 9 - -
  60. 1 2 3 + - 4 5 + 6 / 7 8 * 9 * - *
  61. 1 2 3 / * 4 5 6 7 8 * * - - 9 * *
  62. 1 2 3 4 5 6 / 7 - * - 8 * + 9 * *
  63. 1 2 3 4 5 + - 6 * 7 * 8 * - + 9 -
  64. 1 2 3 4 - 5 - 6 7 * * 8 * 9 + - +
  65. 1 2 3 / * 4 5 - 6 7 * 8 * + 9 * *
  66. 1 2 3 4 5 + 6 * 7 * 8 * 9 - / / *
  67. 1 2 * 3 4 5 - 6 7 8 * * + / 9 / /
  68. 1 2 * 3 / 4 5 6 7 8 * * - - * 9 *
  69. 1 2 3 4 5 + - 6 * 7 * + 8 * - 9 +
  70. 1 2 3 4 - 5 - 6 7 * * 8 * - + 9 -
  71. 1 2 * 3 * 4 5 6 * 7 8 * + * 9 - *
  72. 1 2 * 3 / 4 5 - 6 7 * 8 * + * 9 *
  73. 1 2 3 4 5 - 6 7 8 * * + / / * 9 *
  74. 1 2 3 4 5 + - 6 7 * 8 * * 9 + - +
  75. 1 2 * 3 / 4 5 + 6 * 7 8 * * 9 - *
  76. 1 2 * 3 4 5 6 7 * 8 * - - / 9 / /
  77. 1 2 * 3 4 5 + 6 7 8 * * * 9 - / /
  78. 1 2 3 4 5 + - 6 7 8 * * * 9 + - +
  79. 1 2 3 4 5 + - 6 7 * * 8 * - 9 - +
  80. 1 2 * 3 4 5 + 6 * 7 * 8 * 9 - / /
  81. 1 2 + 3 4 5 6 7 8 * - - * + 9 * +
  82. 1 2 * 3 / 4 5 + 6 7 8 * * * 9 - *
  83. 1 2 3 4 5 + - 6 7 * 8 * * - + 9 -
  84. 1 2 3 4 - 5 - 6 * 7 8 * * 9 + - +
  85. 1 2 3 * 4 5 6 * 7 8 * + * 9 - * *
  86. 1 2 + 3 4 5 + - 6 7 * 8 * * - 9 -
  87. 1 2 + 3 + 4 5 6 * 7 8 * + * 9 - *
  88. 1 2 3 / 4 5 6 7 8 * * - - 9 * * *
  89. 1 2 + 3 4 5 + - 6 * 7 * 8 * - 9 -
  90. 1 2 3 / 4 5 + 6 * 7 8 * * 9 - * *
  91. 1 2 3 / 4 5 6 7 * 8 * - - * * 9 *
  92. 1 2 3 4 5 6 7 8 * * - - 9 * / / *
  93. 1 2 3 4 5 6 + * * 7 - 8 * * 9 + +
  94. 1 2 3 4 5 + - 6 7 8 * * * - + 9 -
  95. 1 2 3 4 - 5 - 6 * 7 * 8 * - 9 - +
  96. 1 2 + 3 4 5 + - 6 7 8 * * * 9 + -
  97. 1 2 * 3 / 4 5 6 7 * 8 * - - * 9 *
  98. 1 2 + 3 4 5 6 7 * 8 + + * + 9 * +
  99. 1 2 * 3 4 5 - 6 7 * 8 * + / 9 / /
  100. 1 2 + 3 4 - 5 - 6 7 * 8 * * - 9 -
  101. 1 2 3 4 5 - 6 7 8 * * + 9 * / / *
  102. 1 2 3 4 5 - 6 7 * 8 * + / / 9 * *
  103. 1 2 3 4 - 5 - 6 * 7 8 * * - + 9 -
  104. 1 2 3 + + 4 5 6 * 7 8 * + * 9 - *
  105. 1 2 + 3 4 - 5 - 6 7 8 * * * 9 + -
  106. 1 2 3 4 5 6 7 8 * * - - / / * 9 *
  107. 1 2 3 4 5 6 - 7 8 * + * + 9 * + +
  108. 1 2 3 4 5 - 6 7 * 8 * + / 9 / / *
  109. 1 2 3 / 4 5 - 6 7 * 8 * + * * 9 *
  110. 1 2 3 / * 4 5 - 6 7 * 8 * + * 9 *
  111. 1 2 3 4 5 6 7 * 8 * - - / / 9 * *
  112. 1 2 3 4 * 5 6 + * 7 - * 8 * + 9 +
  113. 1 2 3 / * 4 5 + 6 * 7 8 * * 9 - *
  114. 1 2 3 / 4 5 - 6 7 8 * * + * * 9 *
  115. 1 2 * 3 4 5 + 6 7 * 8 * * 9 - / /
  116. 1 2 3 4 5 6 7 * 8 * - - / 9 / / *
  117. 1 2 3 / * 4 5 + 6 7 8 * * * 9 - *
  118. 1 2 * 3 4 5 - 6 7 8 * * + 9 * / /
  119. 1 2 3 / 4 5 6 7 8 * * - - * 9 * *
  120. 1 2 3 4 + * + 5 6 - 7 8 + 9 * + *
  121. 1 2 3 4 - 5 - 6 7 * 8 * * - 9 - +
  122. 1 2 + 3 4 5 + - 6 * 7 8 * * 9 + -
  123. 1 2 3 4 - 5 - 6 7 8 * * * - 9 - +
  124. 1 2 3 / * 4 5 6 7 * 8 * - - * 9 *
  125. 1 2 * 3 4 5 6 7 * 8 * - - 9 * / /
  126. 1 2 3 4 5 6 7 8 * - - * + 9 * + +
  127. 1 2 3 4 5 6 / 7 8 * + * - + - 9 *
  128. 1 2 3 4 5 6 + * 7 8 + * 9 + * + +
  129. 1 2 3 4 5 + 6 7 8 * * * 9 - / / *
  130. 1 2 3 4 5 + - 6 7 * * 8 * 9 + - +
  131. 1 2 + 3 4 - 5 - 6 * 7 * 8 * - 9 -
  132. 1 2 3 / * 4 5 6 7 8 * * - - * 9 *
  133. 1 2 + 3 4 - 5 - 6 * 7 8 * * 9 + -
  134. 1 2 * 3 4 5 6 / 7 - * - 8 * + 9 *
  135. 1 2 3 4 5 6 / 7 - * - 8 * + * 9 *
  136. 1 2 * 3 / 4 5 + 6 7 * 8 * * 9 - *
  137. 1 2 * 3 4 5 - 6 7 8 * * + / / 9 *
  138. 1 2 * 3 / 4 5 - 6 7 8 * * + 9 * *
  139. 1 2 3 4 5 + * 6 + 7 * 8 - 9 * + +
  140. 1 2 3 4 5 + - 6 7 * * 8 * - + 9 -
  141. 1 2 3 4 5 + - 6 * 7 8 * * - 9 - +
  142. 1 2 3 / 4 5 + 6 * 7 * 8 * 9 - * *
  143. 1 2 * 3 / 4 5 + 6 * 7 * 8 * 9 - *
  144. 1 2 * 3 4 5 6 * 7 8 * + * 9 - * *
  145. 1 2 * 3 4 5 6 7 * 8 * - - / / 9 *
  146. 1 2 + 3 4 5 6 + 7 8 + * * 9 + * +
  147. 1 2 3 4 - 5 - 6 * 7 * 8 * 9 + - +
  148. 1 2 + 3 4 5 + - 6 7 * 8 * * 9 + -
  149. 1 2 * 3 4 5 - 6 7 * 8 * + 9 * / /
  150. 1 2 3 4 5 6 7 * + 8 + * + 9 * + +
  151. 1 2 3 4 5 + - 6 7 * * + 8 * - 9 +
  152. 1 2 + 3 4 5 + - 6 7 * * 8 * - 9 -
  153. 1 2 3 4 5 6 + * * 7 - 8 * * + 9 +
  154. 1 2 3 4 5 6 + * * 7 - * 8 * 9 + +
  155. 1 2 3 4 - 5 - 6 * 7 * 8 * - + 9 -
  156. 1 2 + 3 4 - 5 - 6 7 * * 8 * - 9 -
  157. 1 2 3 4 5 + - 6 * 7 * + 8 * 9 - -
  158. 1 2 3 4 * + + 5 6 - 7 8 + 9 * + *
  159. 1 2 * 3 4 5 + 6 7 * * 8 * 9 - / /
  160. 1 2 3 4 5 6 7 * 8 * - - 9 * / / *
  161. 1 2 3 4 5 6 + 7 8 + * * 9 + * + +
  162. 1 2 3 4 - 5 - 6 7 * 8 * * 9 + - +
  163. 1 2 3 / * 4 5 - 6 7 8 * * + 9 * *
  164. 1 2 3 / 4 5 + 6 7 * 8 * * 9 - * *
  165. 1 2 3 4 - 5 - 6 * 7 * + 8 * - 9 +
  166. 1 2 3 / * 4 5 + 6 7 * 8 * * 9 - *
  167. 1 2 * 3 4 5 - 6 7 * 8 * + / / 9 *
  168. 1 2 3 4 5 - 6 7 * 8 * + / / * 9 *
  169. 1 2 3 4 - 5 - 6 7 8 * * * 9 + - +
  170. 1 2 3 4 - 5 - 6 7 * * 8 * - 9 - +
  171. 1 2 3 4 - 5 - 6 7 * * + 8 * 9 - -
  172. 1 2 3 4 + * + 5 6 7 8 + 9 * - - *
  173. 1 2 3 / 4 5 + 6 7 8 * * * 9 - * *
  174. 1 2 3 4 * 5 6 + * 7 - 8 * * 9 + +
  175. 1 2 3 4 - 5 - 6 7 * 8 * * - + 9 -
  176. 1 2 * 3 4 5 6 7 8 * * - - / 9 / /
  177. 1 2 3 4 5 6 7 * 8 * - - / / * 9 *
  178. 1 2 3 4 - 5 - 6 7 8 * * * - + 9 -
  179. 1 2 3 / 4 5 6 7 * 8 * - - 9 * * *
  180. 1 2 + 3 4 5 + - 6 * 7 * 8 * 9 + -
  181. 1 2 - 3 - 4 5 + 6 / 7 8 9 * * - *
  182. 1 2 - 3 - 4 5 6 / 7 8 * + * + 9 *
  183. 1 2 3 / 4 5 6 7 8 * * - - * * 9 *
  184. 1 2 * 3 / 4 5 6 7 8 * * - - 9 * *
  185. 1 2 + 3 4 * + 5 6 - 7 8 + 9 * + *
  186. 1 2 + 3 4 - 5 - 6 7 * 8 * * 9 + -

たくさん ある なかで とくに
1 2 3 4 5 6 7 8 * * - - / / 9 * *
は いんしょうてき。1 から 8 まで いっきに ならべられるのも すごいし、たしざんを つかってないのも いい。おぼえやすい。

つぎは これを infix notation に へんかん。うえの しき だと、RPN を しらない ひとには 自慢 できないし。

ちなみに、演算を 全部 かっこで くくる、みたいに して へんかん すると うまく いかない。

たとえば 1 2 + 3 +1 2 3 + + は、それぞれ infix notation に へんかん すると ((1 + 2) + 3)(1 + (2 + 3)) に なって、かっこを てんかい すれば まったく おなじ しきに なる。

なので、たしざんには かっこを つけない、ひきざんは a - b の b に + か - が はいっていたら a - (b) に する、などの 処理を しながら へんかん していく。ちょっと 注意が 必要。

というわけで、へんかんの けっかは いかの 48 とおり。

  1. 1 * 2 / (3 / ((4 + 5) * 6 * 7 * 8 - 9))
  2. 1 * (2 / (3 / ((4 + 5) * 6 * 7 * 8 - 9)))
  3. 1 + 2 + (3 + 4 * (5 - (6 - 7 * 8))) * 9
  4. (1 - (2 + 3 - 4 * (5 / 6 + 7 * 8))) * 9
  5. 1 * (2 / ((3 / (4 - (5 - 6 * 7 * 8))) / 9))
  6. (1 - 2 - (3 - 4 * (5 / 6 + 7 * 8))) * 9
  7. 1 * (2 / (3 / ((4 - 5 + 6 * 7 * 8) * 9)))
  8. 1 + 2 + 3 * (4 * (5 + 6) * (7 + 8) + 9)
  9. (1 - (2 + 3)) * ((4 + 5) / 6 - 7 * 8 * 9)
  10. 1 * (2 / 3) * (4 - (5 - 6 * 7 * 8)) * 9
  11. 1 * (2 / 3) * ((4 + 5) * 6 * 7 * 8 - 9)
  12. 1 * 2 * 3 * (4 * (5 * 6 + 7 * 8) - 9)
  13. (1 - (2 + 3) + 4 * (5 / 6 + 7 * 8)) * 9
  14. 1 * (2 / (3 / (4 - (5 - 6 * 7 * 8)))) * 9
  15. 1 + 2 * (3 * 4 * (5 + 6) - 7) * 8 + 9
  16. (1 * 2 / (3 / (4 - 5 + 6 * 7 * 8))) * 9
  17. (1 * 2 + (3 - 4 * (5 / 6 - 7)) * 8) * 9
  18. 1 - ((2 + (3 - 4 - 5) * 6 * 7) * 8 - 9)
  19. 1 * (2 / (3 / (4 - 5 + 6 * 7 * 8))) * 9
  20. 1 + 2 + (3 + 4 * (5 + 6 * 7 + 8)) * 9
  21. (1 + 2 + 3 * 4) * (5 - 6 + (7 + 8) * 9)
  22. 1 * (2 / (3 / ((4 - (5 - 6 * 7 * 8)) * 9)))
  23. 1 * (2 + (3 - 4 * (5 / 6 - 7)) * 8) * 9
  24. 1 * 2 / (3 / ((4 - (5 - 6 * 7 * 8)) * 9))
  25. (1 + 2 + 3 * 4) * (5 - (6 - (7 + 8) * 9))
  26. (1 * 2 / 3) * ((4 + 5) * 6 * 7 * 8 - 9)
  27. (1 + 2 * (3 + 4)) * (5 - 6 + (7 + 8) * 9)
  28. 1 * 2 / ((3 / (4 - 5 + 6 * 7 * 8)) / 9)
  29. 1 + 2 + ((3 * (4 + 5) + 6) * 7 - 8) * 9
  30. 1 + 2 + (3 + 4 * (5 - 6 + 7 * 8)) * 9
  31. 1 * (2 / 3) * (4 - 5 + 6 * 7 * 8) * 9
  32. 1 + 2 - ((3 - (4 + 5)) * 6 * 7 * 8 + 9)
  33. 1 + 2 - (3 - (4 + 5)) * 6 * 7 * 8 - 9
  34. 1 - (2 + (3 - (4 + 5)) * 6 * 7) * 8 + 9
  35. (1 * 2 / (3 / (4 - (5 - 6 * 7 * 8)))) * 9
  36. (1 - 2 - 3 + 4 * (5 / 6 + 7 * 8)) * 9
  37. (1 + 2 + 3) * (4 * (5 * 6 + 7 * 8) - 9)
  38. 1 - ((2 + (3 - (4 + 5)) * 6 * 7) * 8 - 9)
  39. 1 * (2 / ((3 / (4 - 5 + 6 * 7 * 8)) / 9))
  40. (1 + 2 * (3 + 4)) * (5 - (6 - (7 + 8) * 9))
  41. 1 * 2 / (3 / ((4 - 5 + 6 * 7 * 8) * 9))
  42. 1 * 2 / ((3 / (4 - (5 - 6 * 7 * 8))) / 9)
  43. 1 + 2 - (3 - 4 - 5) * 6 * 7 * 8 - 9
  44. (1 * 2 / 3) * (4 - (5 - 6 * 7 * 8)) * 9
  45. 1 - (2 + (3 - 4 - 5) * 6 * 7) * 8 + 9
  46. (1 - 2 - 3) * ((4 + 5) / 6 - 7 * 8 * 9)
  47. (1 * 2 / 3) * (4 - 5 + 6 * 7 * 8) * 9
  48. 1 + 2 - ((3 - 4 - 5) * 6 * 7 * 8 + 9)

ふつうの しきは Google で かんたんに 確認 できるのが べんり。RPN も けいさんの けっかを 確認 できるように するべき だろうか。

この なかでは、やはり Knuth せんせいの ケーキに えらばれた
1 + 2 + 3 * (4 * (5 + 6) * (7 + 8) + 9)
が いちばん いんしょうてき。たしざんと かけざん しか つかってない。

たしざんと かけざん だけの しき は、もう ひとつ
1 + 2 + (3 + 4 * (5 + 6 * 7 + 8)) * 9
が あるけれど、こちらは 8の うしろに かっこが ふたつ 連続で ならぶ のが うつくしくない。


って、しゅんは とっくに すぎてる 話題 だけれど、今年は まだ なにも かいてなかったので、とりあえず、こんな かんじで スタートを きっておきます。文句が あったら "@n (cont)" あてに twitlonger けいゆで 連絡 ください。さくっと block します。わ