Codeへの愛とCuriosity

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

対戦型 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 を御覧下さい。

「中学入試から：対称軸の本数を数えよう」の実装リンク集

というわけで、実装リンク集。

まだ解いていない方は、
CodeIQ に出した「中学入試から：対称軸の本数を数えよう」の 解説・解題 - Codeへの愛とCuriosity
をまずはご覧下さい。

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);
}

全体的な話

実は、『Ｃプログラミング診断室』( 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{条件} ){ ループ内 }

となる。
大文字なのは VB 風味とも言えるけど、while は ruby の予約語なので逃げでもある。

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) になる。

If と Else

If( s==null ){ 真の場合 } Else { 偽の場合 }

は、Else のために $g というグローバル変数を使った。

If と Else 自体は、ブロック を受け取る普通のメソッド。

upcase

upcase は定義されていないので、無駄メソッドである。つまり、

s=" "+upcase(s);

は、

s=" "+無駄メソッド(s);

である。
無駄メソッドは
　「引数が1個でそれが文字列なら upcase した値を返す」
という処理になっているので、これで upcase になる。

まとめ

こうして書いてみると、工夫が足らんなあという気分になる。
もうちょっと馬鹿げた意味のわからないことを書きたかったなぁ。

「中学入試から：概数と計算」の、実装リンク集

というわけで、実装リンク集。

まだ解いていない方は、
CodeIQ に出した「中学入試から：概数と計算」の 解説解題 - Codeへの愛とCuriosity
をまずはご覧下さい。

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 になっています。

ふたつのファイルは、文字コードが異なるだけで内容は同じです。

■解答形式
「【解答】」の行に続いて解答をお書き下さい。
「【感想・工夫した点など】」の行に続いて、感想、引っかかった点、工夫した点、問題が曖昧だと感じた場合はそこをどう解釈したか、などをお書き下さい。
「【言語と処理系】」の行に続いて、言語名、処理系のバージョン、コマンドラインオプションなどをお書き下さい。
「【ソースコード】」の行に続いて、【あ】〜【か】の値を元に問題を解くプログラムのソースコードをお書き下さい。ソースコードが複数になるようでしたら、その旨がわかるようにお願いします。

こんな感じ。

続きを読む

神奈川Ruby会議でペアプロ問題出した

先日行われた神奈川Ruby会議01 http://regional.rubykaigi.org/kana01/ 。
ここで行われた最初のセッションがペアプロ大会 http://regional.rubykaigi.org/kana01/contents/02_pair_programing.html だったんだけど、ここで出す問題を作るという大役を仰せつかった。

いろいろ悩んだ結果、ひねりのない、ストレートなコンピュータサイエンス問題にした。

当日までと当日は、問題を用意したり、当日悩んでいる人にヒントを出したり、前に出て解説したり。
必死というほどでもないんだけど、あんまり周りは見えていなくて。

終わるまで気づかなかったんだけど、出題される側の方々のなかに、コミッタ様を始めとして数多くのスーパープレイヤーがいて、なんかすごい空間だったんだなと、畏れ多いなと、いう感じがした。

幸い。私の実装は好評だったみたい。ほ。

念の為に書いておくと。
当日壇上で説明した通り、私の実装は実行速度という点では全然よろしくない。
実装が簡単になるようにという方向にフォーカスしていて、実行速度には全然フォーカスしていない。

問題の解説は、ヒントという形で問題ページからリンクされているので、そちらを。
実装例も、問題ページ問題ページからリンクされているので、そちらを。
足りてないのは解題か。

続きを読む