遠い昔、はるか彼方の銀河系の カレンダー の、解題と皆様の実装
「遠い昔、はるか彼方の銀河系の カレンダー」という問題を「初級編 ( https://codeiq.jp/q/2597 )」と「ややリアル編( https://codeiq.jp/q/2598 )」の2題に分けて出した。
多くの方に挑戦いただき、うれしく思っています。ありがとうございます。
解題
問題の内容や解説は
遠い昔、はるか彼方の銀河系の カレンダー - Qiita
や
「遠い昔、はるか彼方の銀河系の カレンダー」問題解答 ( CodeIQ ) - ange1のブログ
を御覧ください。(書いていただき ありがとうございます)
で。
出題意図は:
「ツェラーの公式 を発明してください」
というものだった。これを「ツェラーの公式」をにおわせないで出したい。
そいで。
- 現実のカレンダーを使うと発明ではなく引用になってしまうので、架空のカレンダーにする。
- ただ問題を出すだけだとツェラーの公式は不要になってしまうので、ゴルフにする。
ということになった。
とはいえ。下記リンクを見ていただければわかる通り、ツェラーの公式を発明せずともバイト数の要件を満たしてしまうので、その意味では出題者(私)の敗北である。
皆様の実装など
上記の解説ページ以外では、以下のものを発見した。みなさまありがとうございます。
Ruby(53)
— masaki goto (@g_m_k) 2016年3月25日
putc eval("2*"+gets.tr('.A-K','+036363636262'))%7+116https://t.co/dt7PTLYOTj
Ruby(99)
— masaki goto (@g_m_k) 2016年3月25日
y,m,d=gets.split ?.
m=(m.ord+7)%11+2;y=y.to_i-m/8
putc 122+(2*y-y/20+y/80-y/4000+219*m/7+d.to_i)%-7https://t.co/LtqQpEGCz2
Ruby(104)
— 海老コチニール (@ebicochineal) 2016年3月25日
putc 116+eval("(y=%s)*2+(m=?%c.ord-65)*3-5+(m*7|15)%%5-(m>3?y:y-=1)/20+y/80-y/4000+%s"%gets.split(?.))%7https://t.co/mt2SzHU8n4
#キュラ暦 (Perl(60)) ($y,$_,$d)=<>=~/\w+/g;print chr(($y*2+$d+2+3.417*ord)%7+116)
— stephen_dole (@stephen_dole) 2016年3月25日
#ラゲ暦 (Perl(110)) ($y,$_,$d)=<>=~/\w+/g;$m=(7+ord)%11;$y--if$m>5;print chr(($y*3-$y%4e3*2+$y%80*2-$y%20+($m*23+4)/7+$d-2)%7+116)
— stephen_dole (@stephen_dole) 2016年3月25日
※ 他にもあったら Twitter などでお知らせください。追記します。
今まで CodeIQ に出した問題
今まで CodeIQ に何問出したのかもわからないということに気づき、まとめてみた。
番号は出題順ではなく、URL順。
# | 問題へのリンク | 挑戦/募集 | 難易度 | 締切 |
0 | カードゲームの役を判定する | 不明/50 | ★☆☆☆ | 2013年10月15日 |
1 | テトロミノ+ビンゴ! | 不明/50 | ★☆☆☆ | 2013年11月18日 |
2 | メソッド名を当てる空欄補充問題 | 不明/50 | ★☆☆☆ | 2013年12月23日 |
3 | 最大公約フィボナッチ数(?) | 19/100 | ★☆☆☆ | 2014年1月20日 |
4 | カラフルな八面体を転がそう。 | 50/50 | ★☆☆☆ | 2014年2月19日 |
5 | hello, world × 3 | 67/100 | ★★★☆ | 2014年3月17日 |
6 | 4つの数と四則と括弧 | 57/100 | ★☆☆☆ | 2014年4月22日 |
7 | JavaScriptじゃんけん大会! | 40/100 | ★☆☆☆ | 2014年6月09日 |
8 | 長くなるように、増え続けるように | 44/100 | ★☆☆☆ | 2014年7月14日 |
9 | 中学入試から:数列の和 | 35/100 | ★☆☆☆ | 2014年8月19日 |
10 | 中学入試から:単位のある計算 | 41/100 | ★☆☆☆ | 2014年9月24日 |
11 | 中学入試から:正三角形?二等辺? | 67/100 | ★☆☆☆ | 2014年10月16日 |
12 | 中学入試から:数字の個数 | 34/100 | ★☆☆☆ | 2014年11月18日 |
13 | 中学入試から:図形と場合の数 | 34/100 | ★☆☆☆ | 2014年12月19日 |
14 | 中学入試から:概数と計算 | 22/100 | ★☆☆☆ | 2015年1月31日 |
15 | 中学入試から:対称軸の本数を数えよう | 23/100 | ★☆☆☆ | 2015年2月23日 |
16 | 対戦型 hello, world! | 100/100 | ★☆☆☆ | 2015年3月31日 |
17 | Minority's hello, world | 87/100 | ★☆☆☆ | 2015年7月03日 |
18 | 直角を探せ! 〜ピタゴラスさんありがとう〜 | 141/- | ★★☆☆ | 2015年10月23日 |
19 | テトロミノの置き方を数えよう | 72/- | ★☆☆☆ | 2015年11月13日 |
20 | バスの料金を計算しよう(ややリアル編) | 125/- | ★★★☆ | 2016年3月31日 |
21 | バスの料金を計算しよう(初級編) | 199/- | ★★☆☆ | 2016年3月31日 |
22 | 先制 hello, world | 106/150 | ★☆☆☆ | 2015年9月21日 |
23 | ボタンを押して数を作ろう | 264/- | ★★☆☆ | 2016年3月31日 |
24 | くねくね最短経路 | 67/- | ★★☆☆ | 2016年3月31日 |
25 | 最寄りの素数 | 100/- | ★★★☆ | 2016年3月31日 |
26 | 【機械学習 超初級】【選択式】機械学習の基本のようなそうでもないような問題です | 359/- | ★☆☆☆ | 2016年3月31日 |
27 | 遠い昔、はるか彼方の銀河系の カレンダー(初級編) | 165/- | ★★☆☆ | 2016年3月24日 |
28 | 遠い昔、はるか彼方の銀河系の カレンダー(ややリアル編) | 93/- | ★★★☆ | 2016年3月24日 |
29 | パスカルの 三角形では ありません(字余り) | 140/- | ★★☆☆ | 2016年3月21日 |
初めて出題したのが 2013年9月。それから二年半近く。
数えてみたら丁度 30問だった。
難易度が全然実態と合ってないような気がするけどキニシナイキニシナイ。
上記のリストには、挑戦募集中の問題も(これを書いている時点では)含まれている。
挑戦募集中の問題については
codeiq.jp
からどうぞ。
先制 hello, world のこと
先日、CodeIQ に「先制hello, world」という問題を出した。
単純なプログラムのソースコード同士を戦わせるというコンセプトとしては二回目なんじゃないかと思うけどよく憶えていない。
いつもここに書いているような解説解題の記事は CodeIQ Magazine に掲載していただいたので、普通の解説解題については https://codeiq.jp/magazine/2015/10/30191/ の方をご覧頂きたい。
で。
こちらはサブノート。
今回のルール(ルールについては 前出の CodeIQ Magazine の方を御覧ください)に至る経緯を書いてみよう。
最初のアイディアは、一文字ずつ互いに闘うという、以前出した「対戦型hello, world」と同じようなコンセプトだった。勝敗は文字コードの大小。
「負けたほうが退場」をやめて、n 文字目同士が闘うことにしたらどうだろう。とかいう感じ。
しかしそれだと文字数を揃えなくてはいけない。「対戦型hello, world」では揃えていただいたが、バラバラのほうが面白いと思う。
であれば。
n文字目がn文字目と戦うのをやめればよい。
どうやめるか。
文字のインデックスではなく、文字コードで戦う相手を決めればよいか。
戦いの順序はインデックスで決まり、戦う相手は文字コードで決める。よさ気。
戦うからには勝敗を決める必要がある。文字コードが同じ文字が相手なので、インデックスで勝敗を決めるしかない。インデックスが小さいほうが勝ち。
最終的な勝敗を生存者数にしてしまうと、長いコードを書けば勝てることになりそう。よろしくない。
じゃあ殺された数が少ない方はどうか。これだとコードを短くしたくなるので、いい感じに見える。
で。
このあと。
前後の文字も巻き添えでダメージを食らうとか、ヒットポイントがあって3ダメージで死ぬとか、直前にスペースがあると防御力が上がるとか、遠すぎる文字には攻撃できないとか、いろいろルールを考えたものの。
結局出題したようなシンプルなルールが一番面白そうだということになり、出題に至った。
そんな次第。
ちなみに。
同じような問題を出したいと思っていて、アイディアはあるものの、まだ出題できるところまでルールが仕上がっていない。
出題できるといいなぁ。
Minority's hello, world の 解説・解題
CodeIQ に「Minority's hello, world」という問題
https://codeiq.jp/q/1579
を出した。
問題について
ideone にある言語で hello, world! を書いて、競わせようという問題。
提出コードに課された条件は
という具合。
今回は対戦ではなく、ポイント争い。
ルールはこんな感じ:
提出されたプログラムで使われている文字を、全挑戦者について集計します。
各文字には「(その文字を利用した挑戦者の人数)の2乗」というポイントが割り当てられます。
提出されたプログラムのポイントは、そのプログラムで使われている文字のポイントの合計となります。
提出コードのポイントが少ない順に順位をつけます。最小ポイントの方が優勝です。
という感じ。
戦いの結果は
で見ることが出来る。
勝つために
他の挑戦者の送り込むコードを予想することがまず大事。
予想した上で、ポイントの低いコードを書くための技術力が必要。
様々な言語について何ができるのかを把握していることが求められている内容になっている。
問題の設定はかなり馬鹿げているが、どうやっても勝てない問題というわけではない。
勝つための方法は以下のとおりである:
- 各投稿がどの文字を使っているのかを適当に予想する。
- 予想をもとに、各文字のポイントを計算する。
- 計算結果を元に、自分の書いたコードのポイントを計算し、ゴルフ頑張る。
たぶん、この作業をきちんとやれば、優勝とは言わないまでも、15位ぐらいには入れたのではないかと思う。
もちろん、ある程度、ruby や perl などの素養がないと無理ではあるけれど。
出題意図など
hello, world で競い合う面白いゲームを提供したかった、というのが出題意図である。
必要な能力は
- 複数の言語の素養
- 予測しにくい環境に対応する力
- イレギュラーなゴルフに対応するパズル力
辺りだと思う。
母集団が違うと全然違う戦いになるので、同じルールのゲームを別のところでやっても面白いと思う。
言語を限定しても楽しめると思う。
しかし。
PHP に文字列と文字列の xor があるのは知らなかった。
勉強になりました。
総評的な何か
前回同様、勝ち負けはまあいいんだけど、要求仕様である
- 改行不可
- 「"hello, world"」や「Hello World!」ではなく「hello, world」を出力する
- Ideone で実行可能
などのルールを守れていない方が10名以上いたのが残念だった。
出題文面はだいぶ工夫したつもりなんだけど、全然足りてなかった感じ。
また問題出します。
よろしくお願いします。
バイナリカウント解いてみた
バイナリカウント問題解いてみた。
提出コードはこんな感じ。
# 平易で遅い計算。テスト用。 def solve_slow(x) (1..x).inject(0) do |acc,x| acc+x.to_s(2).count("1") end end # F(x) の xが奇数の場合のアルゴリズム。 def solve_odd( x ) (x+1)/2 + 2*solve(x/2) end # 10**100 でも計算できるアルゴリズム。 def solve( x ) return x if x<3 if x.odd? solve_odd(x) else x.to_s(2).count(?1) + solve_odd( x-1 ) end end # 計算が正しいことの確認 GIVEN_DATA = [ [3, 4], [13, 25] ].freeze TEST_DATA = GIVEN_DATA + (1..1000).map{ |s| [s, solve_slow(s)] } TEST_DATA.each do |src, expected| actual = solve(src) okay = actual==expected p [ src, expected, actual ] unless okay end # 答えを出力する { "・第1問:"=>3, "・第2問:"=>10 }.each do |name, pow| puts "#{name}#{solve(10**pow)}" end
もともと solve_odd は solve の中に埋め込まれていて
# 10**100 でも計算できるアルゴリズム。 def solve( x ) return x if x<3 cur = ( x.even? ? x.to_s(2).count(?1) : 0 ) cur + (x+1)/2 + 2*solve((x-1)/2) end
という感じだった。
これではわかりにくいということで、説明の都合でふたつに分けて提出してみた。
計算量としては大いに改善の余地ありなんだけど、目標だった 10の10乗を大きく超える数でも問題なく計算できるので、計算量の削減作業はこれ以上は行うのをやめた。
対戦型 hello, world! の解説・解題
CodeIQ に「対戦型 hello, world! 」という問題
https://codeiq.jp/q/1356
を出した。
問題について
ideone にある言語で hello, world! を書いて、対戦させようという問題。
提出コードに課された条件は
- ideone にある言語のどれかで書くこと。
- 過不足なく「hello, world!」を出力すること。
- ソースコードに使える文字は、アスキーコード 0x20〜0x7e の文字のみ。
- ソースコードに使える文字は、100文字まで。
という具合。
戦いのルールはちょっと長くなるど
1文字目から順に対戦する。文字と文字の戦いのことを「マッチ」と呼ぶ。
マッチの勝敗は
- 数字, 大文字, 小文字 が グー, チョキ, パー の関係。
- 空白以外の記号は、数字・大文字・小文字 のいずれにも負ける。
- 空白は 9, Z, z にだけは勝つが、それ以外のすべての文字に負ける。
- 文字の種類が同じ場合は文字コードが大きいほうが勝ち。
というルールで決まる。
- マッチで勝敗がついた場合は、負けた文字が退場する。
- 引き分けの場合は両者が退場する。
- これを、一方の文字がなくなるまで繰り返す。
- 先に文字がなくなったほうが負け。
という感じ。
これで総当り戦を行い、勝ち点が多い人が優勝。という遊び。
実際に戦っている様子を
で見ることが出来る。
勝つために
ゲームのルールを理解し、どうすれば勝てるのかを正しく考察し、考察の結果を実現するということが求められている内容になっている。
問題の設定はやや馬鹿げているけど、挑戦した人が勝つためにすべきことは普通の課題解決の体裁になっているので、なんなら入社試験に使ってもいいぐらいに思っている。どうでしょうか。
ルールをきちんと理解すると、
- ある文字が対戦する相手は、自分の前の文字を倒した相手になる(直前が引き分けた場合は例外となる)
ということがわかる。
引き分けを度外視すると「ZyZyZyZyZ」のような
- あるカテゴリの最高位の文字(上記のZ)
- 直前のカテゴリに勝つカテゴリに勝つカテゴリの、最高位のひとつ前の文字(上記のy)
を並べると連敗はしないということがわかる。
「z8z8z8」でも「9Y9Y9Y」でも良い。このようなパターンをできるだけ長く仕込みつつ、どう「hello, world!」を出すかが勝負になる。
あと。
- 同じ文字を繰り返しても連敗する可能性が高く、得策とはいえない。
- 同じカテゴリも避けたい。
という辺りも気にするといいと思う。
とはいえ。
全勝がいないことからもわかる通り、最後は運。予測できない他人に勝つことが必要で、同しようもない部分が多い。
あと。
「hello, world」という、「y」や「A」で薙ぎ払われる文字列を回避するために文字を費やすのか、ここを諦めるのかが難しいところ。
優勝コードは回避するために工夫をし、2位のコードは諦めてシンプルにまとめている。
言語の選択も難しい。
辺りが強そうかと思っていたんだが、SQL の方はいなかった。残念。
総評的な何か
勝ち負けはまあいいんだけど、要求仕様である
- 100文字以内
- 改行不可
- 「"hello, world!"」や「hello world!」ではなく「hello, world!」を出力する
を守れていない方が10名以上いたのが残念だった。
出題文面の工夫がもう少し必要だったかもしれないとも思う。
宣伝
オフラインリアルタイムどう書くやります。
4/18 土 です。
詳しくは https://yhpg.doorkeeper.jp/events/22168 を御覧下さい。
「中学入試から:対称軸の本数を数えよう」の実装リンク集
というわけで、実装リンク集。
まだ解いていない方は、
CodeIQ に出した「中学入試から:対称軸の本数を数えよう」の 解説・解題 - Codeへの愛とCuriosity
をまずはご覧下さい。
- http://ideone.com/Qf51fB @bananawani_mc 様 / Java / 偶数奇数分離版
- http://ideone.com/okYEZU @bananawani_mc 様 / Java / 偶数奇数統合版
- http://ideone.com/JoxCKi @suppy193 様 / Ruby
- http://ideone.com/qgxdSI @cielavenir 様 / Ruby
- http://ideone.com/gmGTlp @cielavenir 様 / Python2/3
- http://ideone.com/TxOVrc @cielavenir 様 / C++11
- https://gist.github.com/mikecat/8732fcdffacf3ead0222 @mikecat_mixc 様 / C言語
- https://gist.github.com/all-user/0ac0efeb7859cd1f0e4d @all__user 様 / Swift
- http://d.hatena.ne.jp/haruya12/20150224/1424783188 @haruya1212 様/ ruby
- http://ideone.com/JUUcw1 @R_learner 様 / Python 3