バイナリカウント解いてみた
バイナリカウント問題解いてみた。
提出コードはこんな感じ。
# 平易で遅い計算。テスト用。 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
CodeIQ に出した「中学入試から:対称軸の本数を数えよう」の 解説・解題
CodeIQ に「中学入試から:対称軸の本数を数えよう」という問題
https://codeiq.jp/ace/nabetani_takenori/q1318
を出した。
中学入試算数問題第7弾。
挑戦の募集はすでに締めきっている。
というわけで、解説・解題。
で。
まずは問題
問題
■問題の概要
中学入試算数の範囲で、以下の様な問題を作ることが出来ます。円周上を6等分する点を考え、順に点Aから点Fとします。 ここで、BE, EC, CF, FB の4本の線でできている図形を考えます。 この図形には線対称となる対称軸は何本あるでしょうか。 ただし、線対称ではない場合は 0 と答えること。この問題を
円周上を【あ】等分する点を考え、点の名前を点A, 点B, ... と順につけます。 ここで、【い】の【いの要素の数】本の線でできている図形を考えます。 この図形には線対称となる対称軸は何本あるでしょうか。 ただし、線対称ではない場合は 0 と答えること。と考え、【あ】と【い】を入力として与えます。問題の答えを計算するプログラムを書いて下さい。
【あ】には、正の整数が入ります。
【い】には、「BE,EC,CF,FB」のような形式で、この図形を構成する線分がコンマ区切りでならべられます。■具体的な課題
下記リンクの zip 内に data.txt というファイルがあります。
このファイルの各行は
データID、【あ】の内容、【い】の内容、【あ】【い】の内容に対応した答え
の4件を TAB区切りでならべたものになっています。
ほとんどのデータは正しい答えになっています。
答えが間違っているデータが数件あります。それらのデータの ID を答えて下さい。■補足
・データIDがTで始まるデータは、すべて正しい答えになっています。テストにお使い下さい。
・不正な入力に対処する必要はありません。
・間違いの数は、5件より多く、20件より少なくなっています。■資料
http://nabetani.sakura.ne.jp/codeiq/q1318.zip
上記リンク先の zip ファイルの中には、以下のファイル含まれています。・ data.txt
→ 調査対象およびテストデータです。■解答形式
「【解答】」の行に続いて解答をお書き下さい。
「【感想・工夫した点など】」の行に続いて、感想、引っかかった点、工夫した点、問題が曖昧だと感じた場合はそこをどう解釈したか、などをお書き下さい。
「【言語と処理系】」の行に続いて、言語名、処理系のバージョン、コマンドラインオプションなどをお書き下さい。
「【ソースコード】」の行に続いて、【あ】、【い】の値を元に問題を解くプログラムのソースコードをお書き下さい。ソースコードが複数になるようでしたら、その旨がわかるようにお願いします。
こんな感じ。
逆リファクタリング問題
tbpgr さんの逆リファクタリング問題
https://codeiq.jp/magazine/2015/02/21347/
に挑戦した。
優秀解答として紹介していただいたので、解説する。
ソース
まずはソース。
#coding:utf-8 def static(*);yield if block_given?;:!end alias void static alias Main void class System;def self.in; self;end;def self.eof; STDIN.eof?;end def self.out;Kernel;end;def self.read; STDIN.getc;end;end def If(x);yield if ($g=x);end def Else;yield unless $g;end def While(x);yield while x.(); end class BasicObject;def method_missing(method, *args); args[0].upcase if args.size==1 && args[0].is_a?( "".class );end;end alias lambda ! 謎言語風です。 ! 入出力がSystem.inだったりSystem.outだったりする辺りはJava風。 ! メインがMainなのはC#風。 ! コメントは苦し紛れに FORTRAN 風。 ! もっとWhileを見慣れた感じにしたかったんだけど、これ以上アイディアがなく。 public static void Main(){ string s=null; While {! System.in.eof()} { If ( s==null ){ s=""; } Else{ s=" "+upcase(s); } s=System.in.read()+s; } System.out.print(s); }
全体的な話
実は、『Cプログラミング診断室』( http://www.amazon.co.jp/dp/4774117870 )の「第8章 Pascalが好き」へのオマージュのつもりで書き始めた。
ダメなソースコードの例が解説付きで載っている名著なので、未読の方は是非。
それはさておき。
当初は Java 風にしようとしていたんだけど、どうもうまく出来なくて。
特に while ループを
While(条件){ループ内}
のようにする方法がわからず、仕方なく謎言語風という形に逃げた。
順に解説
謎言語部に登場する部品を、概ね登場順に解説する。
FORTRAN風のコメント
FORTRAN 風のコメントは、普通に 否定演算子 + ruby のメソッド呼び出しに なっている。
つまり「謎言語風です。」などはメソッド呼び出し。そんなメソッドはないんだけど、method_missing でエラーにならなくなる。
「! メインがMainなのはC#風。」の部分は、# 以下がrubyのコメントになっている。
ちなみに、
「! Mainメソッドが云々」
のようなコメントを書くと、大文字始まりなのでメソッドではなく定数になり、実行時エラーになる。
以下、method_missing に到達する処理を「無駄メソッド」と記述する。
public static void Main
public は ruby の予約語……ではなく、Module クラスの private メソッド。static以下の実行結果を public にする。
static も void も Main もメソッドで、
static( void( Main(){略} ) )
ということになっている。
public に何かを渡さなくてはいけないので、static は「:!」を返している。
Main の引数のブロックを実行しなくてはいけないので、Main はブロックを受け取ったらそれを実行するようになっている。
string s=null;
型を指定して変数を宣言しているようにみえる
string s=null;
は、
string( s=null() )
という意味である。
string も null も無駄メソッドだけど、s は本当にローカル変数。
無駄メソッドは、引数がないと nil を返すようになっているので、これで
無駄メソッド( s=nil )
となり、無事、本当に s が nil になる。
While
難儀した割に無様な While なんだけど、
alias 全角空白 lambda
によって、While の部分は
While( lambda{条件} ){ ループ内 }
System クラス
System.in.eof()
は、比較的普通な感じ。System クラスには以下の様な4つの特異メソッドがある。
メソッド | 意味 |
---|---|
in | System クラスを返す |
out | Kernel クラスを返す |
eof | STDIN.eof? |
read | STDIN.getc |
で。System.in.eof() は、System.eof() で、つまり STDIN.eof? になる。
最後の方にある System.in.read() は、System.read() なので、STDIN.getc になる。
一番最後の System.out.print(s) は、System.print(s) なので、Kernel.print(s)、つまり、print(s) になる。
まとめ
こうして書いてみると、工夫が足らんなあという気分になる。
もうちょっと馬鹿げた意味のわからないことを書きたかったなぁ。
「中学入試から:概数と計算」の、実装リンク集
というわけで、実装リンク集。
まだ解いていない方は、
CodeIQ に出した「中学入試から:概数と計算」の 解説解題 - Codeへの愛とCuriosity
をまずはご覧下さい。
- CodeIQ の 数学問題「中学入試から:概数と計算」( https://codeiq.jp/ace/nabetani_takenori/q1282 ) の求解プログラム by Julia。 antimon2 様。
- http://ideone.com/ZnVu3U @bananawani_mc 様。Java。
- http://ideone.com/7za7iI @cielavenir 様。Ruby。
- CodeIQ「中学入試から:概数と計算」解答コード @mikecat_mixc 様。Java。
- CodeIQ「中学入試から:概数と計算」 - 計算用紙 @haruya1212 様。Ruby。
- CodeIQ 「中学入試から:概数と計算」提出コード @all__user 様。Swift。
CodeIQ に出した「中学入試から:概数と計算」の 解説解題
CodeIQ に「中学入試から:概数と計算」という問題
https://codeiq.jp/ace/nabetani_takenori/q1282
を出した。
中学入試算数問題第6弾。
挑戦の募集はすでに締めきっている。
というわけで、解説・解題。
で。
まずは問題
問題
■問題の概要
中学入試算数の範囲で、以下の様な問題を作ることが出来ます。ある数の小数第3位を四捨五入した結果を 1.7 倍してから小数第1位を四捨五入すると42になります。 この数はどんな範囲にありますか。 範囲は、「以上」「より大きく」「以下」「未満」を用いて答えなさい。 ある数にあてはまる数が全くない場合は「なし」と答えなさい。この問題を
ある数の小数第【あ】位を【い】した結果を【う】倍してから小数第【え】位を【お】すると【か】になります。 この数はどんな範囲にありますか。 範囲は、「以上」「より大きく」「以下」「未満」を用いて答えなさい。 ある数にあてはまる数が全くない場合は「なし」と答えなさい。と考え、【あ】〜【か】を入力として与えます。問題の答えを計算するプログラムを書いて下さい。
【あ】【え】 には、正の整数が入ります。
【い】【お】には、「四捨五入」「切り捨て」「切り上げ」 のいずれかが入ります。■具体的な課題
下記リンクの zip 内に data.utf8.txt および data.sjis.txt というファイルがあります。
これらのファイルの各行は
「データID、【あ】〜【か】の内容、【あ】〜【か】の内容に対応した答え」
を TAB区切りでならべたものです。
ほとんどのデータは正しい答えになっています。
答えが間違っているデータが数件あります。それらのデータの ID を答えて下さい。data.utf8.txt と data.sjis.txt は、文字コードが異なるだけで内容はまったく同じです。
お好きな方をお使い下さい。■補足
・データIDがTで始まるデータは、すべて正しい答えになっています。テストにお使い下さい。
・不正な入力に対処する必要はありません。
・間違いの数は、5件より多く、20件より少なくなっています。■資料
http://nabetani.sakura.ne.jp/codeiq/q1282.zip
上記リンク先の zip ファイルの中には、以下のファイル含まれています。・ data.utf8.txt
→ 調査対象およびテストデータです。文字コードは UTF-8 になっています。
・ data.sjis.txt
→ 調査対象およびテストデータです。文字コードは SHIFT_JIS になっています。ふたつのファイルは、文字コードが異なるだけで内容は同じです。
■解答形式
「【解答】」の行に続いて解答をお書き下さい。
「【感想・工夫した点など】」の行に続いて、感想、引っかかった点、工夫した点、問題が曖昧だと感じた場合はそこをどう解釈したか、などをお書き下さい。
「【言語と処理系】」の行に続いて、言語名、処理系のバージョン、コマンドラインオプションなどをお書き下さい。
「【ソースコード】」の行に続いて、【あ】〜【か】の値を元に問題を解くプログラムのソースコードをお書き下さい。ソースコードが複数になるようでしたら、その旨がわかるようにお願いします。
こんな感じ。