Codeへの愛とCuriosity

CodeIQ への出題・解説解題・その周辺について、思いつくままに。

位置関係2題の解説・解題

先日、CodeIQ に出していた

という2つの問題が締め切られた。

私が出した問題が締め切られるのは久々だったので、ちょっと慣れない感じ。

で。

この問題は、タイトルの通り、2つの図形の位置関係を分類する問題になっている。
2つの円の方は、中心と中心の距離を見ればいいだけなので簡単。
円と線分はいろいろ見なくちゃいけないし、分類も多いのでちょっと大変、ということになっている。

数学力はあまり問うていないつもり。高校程度なんだと思う。

いつもなら、一つの事象をひとつのテストデータにするんだけど、今回はそれだと件数が多くなりすぎる感じなので、ひとつのテストデータにたくさんの事象を仕込むことにした。


問題の概要については
http://ange1.hateblo.jp/entry/2016/07/23/001128
をご覧いただくことにして、出題意図を列挙すると。

  • ごちゃごちゃした分類を誤らずに実装できるかどうか
  • 浮動小数点の除算や平方根を使うべきではないという判断ができるかどうか

というつもり。浮動小数点を使っても解決できてしまう場合が多かったようで、この点はテストデータの追い込みが足りなかったと反省している。


「接する」というデリケートな条件を判断する必要がある問題になっているので、誤差がまったくない計算をする必要がある。そして、この問題はそのような実装を無理なくできる問題になっている。入力は整数だし。


誤差のない計算ということで、有理数が簡単に扱える rubypython だと実装が楽になる。
JavaScript だと苦しい感じかもしれない。


私の場合はやっぱり ruby でこんな感じ:

2つの円の位置関係の実装例:

def solve_one(s)
  x0,y0,r0,x1,y1,r1 = s.scan( /\d+/ ).map(&:to_i)
  d2 = (x0-x1)**2 + (y0-y1)**2
  r0,r1=[r0,r1].minmax
  return "A" if d2==0 && r0==r1
  sr2 = (r0+r1)**2
  return "F" if sr2<d2
  return "E" if sr2==d2
  dr2=(r1-r0)**2
  return "B" if d2<dr2
  return "C" if d2==dr2
  return "D" if d2>dr2
  raise "unexpected"
end

def solve( src )
  src.split(" ").map{ |s|
    solve_one( s )
  }.join("")
end

puts solve(gets)

円と線分の位置関係の実装例:

def calc_min2( a, b, c )
  candidates=[
    c, # x==0
    a+b+c # x==1
  ]
  x=-b/2.to_r/a
  candidates.push( a*x*x+b*x+c ) if 0<=x && x<=1
  candidates.min
end

def solve_one(s)
  cx,cy,r,ax,ay,bx,by = s.scan( /\d+/ ).map(&:to_r)
  ax-=cx
  ay-=cy
  bx-=cx
  by-=cy
  a=ax*ax+ay*ay<=>r*r
  b=bx*bx+by*by<=>r*r
  return "A" if a<0 && b<0
  return "C" if a==0 && b==0
  return "B" if a<=0 && b<=0
  return "F" if a*b<0
  vx=bx-ax
  vy=by-ay
  min2 = calc_min2(vx*vx+vy*vy, 2*(ax*vx+ay*vy), ax*ax+ay*ay )
  case min2<=>r*r
  when -1; a*b==0  ? "D": "E"
  when 0; a*b==0  ? "G": "H"
  when 1; "I"
  end
end

def solve( src )
  src.split(" ").map{ |s|
    solve_one( s )
  }.join("")
end

puts solve(gets)

我ながらもう少しなんとかならなかったのかと思わなくもない。

ともあれ。


多くの方に挑戦いただき大変うれしく思っています。ありがとうございました。

遠い昔、はるか彼方の銀河系の カレンダー の、解題と皆様の実装

「遠い昔、はるか彼方の銀河系の カレンダー」という問題を「初級編 ( https://codeiq.jp/q/2597 )」と「ややリアル編( https://codeiq.jp/q/2598 )」の2題に分けて出した。

多くの方に挑戦いただき、うれしく思っています。ありがとうございます。

解題

問題の内容や解説は
遠い昔、はるか彼方の銀河系の カレンダー - Qiita

「遠い昔、はるか彼方の銀河系の カレンダー」問題解答 ( CodeIQ ) - ange1のブログ
を御覧ください。(書いていただき ありがとうございます)

で。

出題意図は:
ツェラーの公式 を発明してください」
というものだった。これを「ツェラーの公式」をにおわせないで出したい。

そいで。

  • 現実のカレンダーを使うと発明ではなく引用になってしまうので、架空のカレンダーにする。
  • ただ問題を出すだけだとツェラーの公式は不要になってしまうので、ゴルフにする。

ということになった。

とはいえ。下記リンクを見ていただければわかる通り、ツェラーの公式を発明せずともバイト数の要件を満たしてしまうので、その意味では出題者(私)の敗北である。

タイトルは、ちょうどスターウォーズの公開が近かったので、スターウォーズ感のあるものにしてみた。

皆様の実装など

上記の解説ページ以外では、以下のものを発見した。みなさまありがとうございます。







※ 他にもあったら 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! を書いて、競わせようという問題。

提出コードに課された条件は

  • ideone にある言語のどれかで書くこと。
  • 過不足なく「hello, world」を出力すること。
  • ソースコードに使える文字は、アスキーコード 0x20〜0x7e の文字のみ。

という具合。

今回は対戦ではなく、ポイント争い。
ルールはこんな感じ:

提出されたプログラムで使われている文字を、全挑戦者について集計します。
各文字には「(その文字を利用した挑戦者の人数)の2乗」というポイントが割り当てられます。
提出されたプログラムのポイントは、そのプログラムで使われている文字のポイントの合計となります。
提出コードのポイントが少ない順に順位をつけます。最小ポイントの方が優勝です。

という感じ。

戦いの結果は

で見ることが出来る。

勝つために

他の挑戦者の送り込むコードを予想することがまず大事。
予想した上で、ポイントの低いコードを書くための技術力が必要。
様々な言語について何ができるのかを把握していることが求められている内容になっている。

問題の設定はかなり馬鹿げているが、どうやっても勝てない問題というわけではない。

勝つための方法は以下のとおりである:

  1. 各投稿がどの文字を使っているのかを適当に予想する。
  2. 予想をもとに、各文字のポイントを計算する。
  3. 計算結果を元に、自分の書いたコードのポイントを計算し、ゴルフ頑張る。

たぶん、この作業をきちんとやれば、優勝とは言わないまでも、15位ぐらいには入れたのではないかと思う。
もちろん、ある程度、rubyperl などの素養がないと無理ではあるけれど。

出題意図など

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位のコードは諦めてシンプルにまとめている。

言語の選択も難しい。

  • 引用符が不要な Bash
  • 文字列の xor が使える Perl
  • say が3文字だし「y」を含んでいて強そうな Perl6
  • 大文字小文字が混ぜ放題の SQL

辺りが強そうかと思っていたんだが、SQL の方はいなかった。残念。

総評的な何か

勝ち負けはまあいいんだけど、要求仕様である

  • 100文字以内
  • 改行不可
  • 「"hello, world!"」や「hello world!」ではなく「hello, world!」を出力する

を守れていない方が10名以上いたのが残念だった。

出題文面の工夫がもう少し必要だったかもしれないとも思う。

宣伝

オフラインリアルタイムどう書くやります。
4/18 土 です。
詳しくは https://yhpg.doorkeeper.jp/events/22168 を御覧下さい。