はじめに 久しぶりの講座ネタとして、最近締め切りを迎えた、CodeIQの「あしあと」を題材に、Brainf**kでのコードを設計し実装するまでを解説してみたいと思います。 ※なお、Brainf**k講座本編に関しては、最後の第8回をご覧ください。 codeiq.jp 問題 この問題は、次のような内容でした。 9×9のマス目の上を、入力に従って動く時、最終的な状態を出力する。 入力は、最後の改行以外は^v<>の4種類の文字からなり、それぞれ上下左右の1マス移動を表す。移動の順序は入力の順番そのまま。 開始地点は1行1マス目、とする。なお、移動によってマス目外に出ることは考慮しなくて良い。 マス目の状態の出力は、1行9文字、9行で行い、一度でも通ったマスはY、それ以外はxに置き換える。 例えば、>>>>>>>>vvvvvvvv<<<<<<<<^^^^^^^^という入力であれば、外周をぐるりと一

はじめに 今回でいよいよ最後になりました。トリとして、BCD演算を紹介したいと思います。 講座一覧 Hello, BF! 導入およびシンプルなループによる数値生成 数値入力と簡単なループ ,による入力と数値解釈、簡単なループの実例 スライド型ループ ループ継続の判断を行うセルの位置をずらしていくループ 条件分岐 if文、if-else文相当の処理 条件分岐の多段化 switch文相当の処理 非破壊的条件分岐 条件変数を壊さない条件分岐 divmodアルゴリズムと数値出力 除算・剰余算のアルゴリズムと、それを利用した不定長の数値出力 BCD演算 10進数による任意長の数値の計算 実行環境 ideone オンラインのIDE環境で、bffという処理系が使えます。この講座は基本的にこのbffに対応したものです。 Brainf**kインタープリタ あじさんという方が作られたブラウザ上で動くインタプリ

はじめに 既に基本機能をマスターされたことと思われますBrainf**k講座、ループ処理の幅を広げるために、実践的なコードに触れていきたいと思います。 講座一覧 Hello, BF! 導入およびシンプルなループによる数値生成 数値入力と簡単なループ ,による入力と数値解釈、簡単なループの実例 スライド型ループ ループ継続の判断を行うセルの位置をずらしていくループ 実行環境 ideone オンラインのIDE環境で、bffという処理系が使えます。この講座は基本的にこのbffに対応したものです。 [Brainf**kインタープリタ(http://azisava.sakura.ne.jp/js/bf/) あじさんという方が作られたブラウザ上で動くインタプリタです。細かい挙動の調整や、途中のセルの状態のダンプができたり、重宝しています。 ※オプションで「バッファの型」を「4バイト符号付き整数」、「標

はじめに 前回より始まりましたBrainf**k講座、実際のコードを通じて、少しずつできることを増やしていく予定です。 講座一覧 Hello, BF! 導入およびシンプルなループによる数値生成 数値入力と簡単なループ ,による入力と数値解釈、簡単なループの実例 実行環境 前回紹介していませんでしたが、Brainf**kを実行できる環境について。ちょっと組んでみたコードを動かしたくなった時に使えるものを紹介します。 ideone オンラインのIDE環境で、bffという処理系が使えます。この講座は基本的にこのbffに対応したものです。 Brainf**kインタープリタ あじさんという方が作られたブラウザ上で動くインタプリタです。細かい挙動の調整や、途中のセルの状態のダンプができたり、重宝しています。 ※オプションで「バッファの型」を「4バイト符号付き整数」、「標準入力の終端」を「-1」と設定す

はじめに Brainf**kは、命令が+-<>[],.のたった8種類という、超シンプルなプログラミング言語であり、初心者にも易しい ( はず!! 絶対! …多分 ) のですが、実用的な組み方の指針と言うのがなかなかなく、興味を持ってもとっつきにくいのではないかと感じています。 そこで、実際のコードを元に、どのように組んでいくのか、講座形式で紹介していきたいと思います。全部で8回の予定です。 講座一覧 Hello, BF! 導入およびシンプルなループによる数値生成 今回の話題 まずはお約束ということで、“Hello, world!”ならぬ“Hello, BF!”を題材とした導入、シンプルなループによる数値生成を紹介したいと思います。 Brainf**kの実行モデル コードの実行 Brainf**kのコードは、+-<>[],.の8種類の命令からなります。それ以外の文字はコメントとして無視されま

はじめに CodeIQというところで、結城さんのプログラミング問題に解答しましたので、そのネタばれです。 codeiq.jp 問題 標準入力Lに対し、次の図にあるような図で、Xを出てYに辿り着く方法が何通りあるかを出力します。 ただし、Zには到着せず、かつ方向転換できるのはA,B,Cの地点のみ、その回数の上限はLとします。 数学的なアプローチ 方針 折り返し点毎に規則性を整理し、漸化式を導くことを目指します。 規則性 まず、「Xから出発」は、「AからZ方向に出発」と置き換えてもと同じです。 そうしたうえで、「AからZ方向に出発」「BからZ方向に出発」の2ケースを考えてみます。 ※「CからZ方向に出発」はすぐにZについてしまうため除外します。 Aから出発した場合、 A→B(反転)→A→Y A→B→C(反転)→B→A→Y A→B(反転)→A(反転して再出発) A→B→C(反転)→B→A(反転し

はじめに CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。 codeiq.jp 問題 問題は1人～6人組を列車の座席に割り当てる場合の数を求めるものですが、少々ややこしい条件でした。詳しくは次の記事をご参照ください。 codeiq.jp ちなみに、座席の列数をnとした場合、n=12のケースの答え、2754844344633 を出力するプログラムを実装します。 解答 提出コード 以下のRubyのコードを提出しました。一応131文字で、1tweetに収まる文字数になっています。 x=[1,1] y=[1,2] z=[1,4] f=->n{x[n+1]||=(0..n).inject(0){|s,i|s+(y[i]||=y[i-1]*2+y[i-2])*(z[i]||=z[i-1]*4+z[i-2])*f[n-1-i]}} p f[12] 解説 方針

はじめに CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。 codeiq.jp 問題 デジタル時計 ( 24h制 ) は、各桁が数個のLEDのON/OFFで表示が制御されています。ここで、「合計n箇所のLEDが表示される時刻は?」を考え、時刻が何通りあるか、その場合の数を出力する、という問題でした。 なお、問題文には明記されていませんが、10の位が0の場合、「LEDが全てOFF」ではなく「0に対応したLEDがON」としていたようです。すなわち、例えば午前1時ちょうどの場合、“ 1: 0: 0”や“ 1:00:00”ではなく“01:00:00”に対応するLEDがONになる、ということです。 ケースは控えていないので忘れましたが、n=27に対して答えが8800となることは問題文に載っています。 解答 今回はPerlで実装しました。…特にGolfもし

はじめに CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。 codeiq.jp 問題 格子状に配置されたポストへの投函順序が何通りあるか数えて出力する…、なのですが「最速」という制約が付きます。なので、 *縦・横の隣接移動のみで全ポストを1度ずつ通るやり方 と考えることができます。開始地点は任意です。 なお、ポストの縦・横は、カンマ区切り1行で入力として与えられます。 解答 コード 提出解は、以下のRubyでした。下の解説にある通り、当初はもう少し簡略なコードにしていたのですが、TLEの対策のためにちょっと変更しました。 def f_sup(a,r,d,i) # a: boolean array # r: remained posts # d: distance in up/down move # i: current post index t

はじめに CodeIQというところで、コードゴルフ問題「シンプル・ライフゲーム」に参加したわけですが。折角なので同じPerlで挑戦されたトップのtailsさんのコードを解析してみたいと思います。 codeiq.jp コード tailsさんが公開されたPerl(133)のコードです。CodeIQ環境と違い、ideoneでは“ge for”の部分の空白が省けませんが、そこ以外で大きな違いはありません。 解析 全体像 で、さて。「ライフゲーム」自体、基本的には地道に処理する、つまりセル毎に隣接セルの生き死にを調べ、その数に応じて生き死にを変化させる、そういう処理以外は多分無理だと思います。 tailさんのコードも、そういう意味では地道なものです。まずは、細部を省略したコードに直してみます。 $n=<>; # 世代数 <>; # 行数は無視 $/=<>; # 列数 @a=/./g,s##～#eg

はじめに CodeIQ というところで開催していたコードゴルフ問題、「シンプル・ライフゲーム」に挑戦しました。 d.hatena.ne.jp 出題者ozyさんの上記集計記事にある通り、Brainf**kで堂々の1位、Perlはtailsさんに次ぐ2位という結果になりました…って、いやまあ、Perlで10文字も離されましたが。 問題 ライフゲーム自体は、Wikipediaの説明を見るのが早いと思います。ただし、端は上下・左右ともループして繋がっているものとして扱います。 入力データは、 1行目 … 世代数 2行目 … 格子の行数 ( 高さ ) 3行目 … 格子の列数 ( 幅 ) 4行目以降 … 格子の各行、生/死は */. で表される となっており、指定の世代数を経たのちの格子を、入力データのように */. で出力する、という問題になります。 なお、指定のケースの3番目は、格子サイズ35×4

はじめに CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。 …なお、その前の船の問題は見事に不正解でした…。ちょっと余り吟味する余裕が無かったので、記事は断念です。 codeiq.jp 問題 問題については、次の記事をご覧ください。簡単に言うと、GCPを皆で出して多数決単独トップが生まれる場合の数 ( 「誰が出したか」は区別せず ) を求める問題です。 codeiq.jp 解答 提出解は、以下のRuby(30)でした。 n=eval *$< p ~n**2/2+n%2-n%3/2 解説については、提出時のコメントの流用で。 方針 全ケースから、多数決が決まらない ( トップで引き分けが発生する ) ケースを差し引くことで答えを求めます。 各ケース 全部で n人参加の場合のケースを挙げ、それぞれ何通りかを計算します。 全ケース GCPに各人数を割

はじめに CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。 codeiq.jp 問題 簡単に書くと、 標準入力より数値 ( nとする ) が与えられる n個の相異なる数字に対して「互い違い」に並べる方法が何通りあるか、その数値を出力する。 ただし「互い違い」とは、どの連続する3数をとっても単調増加/減少 ( 1→2→3 とか 6→4→2 とか ) ではない、すなわち増加・減少を繰り返すことを指す。 という問題でした。 CodeIQマガジンに記事も出ましたのでご参照ください。( 2015/10/22追記 ) codeiq.jp 解答 以下が提出版のgolf解、Perl(50)。…自動採点だからといって、コメントつけないのは良くないねと反省したばかりなのに、見事にコメントを付け忘れてました。ゴメンナサイ。 @^=2;$\=0,@^=map$\+=$

はじめに CodeIQという所で週次で出題される ( 最近再開された ) 「今週のお題」シリーズに解答しましたので、ネタバレです。 codeiq.jp 問題 既に問題は公開終了していますから、概要を。 入力値 ( nとします ) に対して、n段の階段と、そこに1人 or 複数の人 ( 同じ段には重複しない ) がいる場面を考えます。 1回の移動で、直下の段が空いている段の人は1段降り、そうでない人は留まります。一番下の段の人は ( 降り切ったということで ) いなくなります。 そうして、何回の移動で全員が階段を降りることができるかを考え、「n段の階段でありうる人の配置」全てに対する回数の和を求めます。 例えばですが、4段で ○×○○ という配置 ( 右の方が低、○が人のいる段を表す ) の場合、 ○×○○→×○○×→×○×○→××○×→×××○**→×××× で5回という数え方になります。

はじめに 先制 hello, worldに参加しました - ange1のブログの続き、CodeIQで開催された「先制 hello, world」というコードバトルについてのお話です。 先制 hello, world 全試合に詳細が公表されましたので、自分の最終提出コードについてネタバレします。 コード …これ見ただけだと、プログラムって分かりませんが、我ながら。一応Perlコードです。 分解すると、次のような構成になっています。 e . "文字列" * s!!コード!ee ベアワード ( 文字列として扱われる ) の e と、""でクォートされた文字列・s演算子 ( デリミタとして、/ の代わりに ! ) の乗算 (*) の結果との文字列結合 (.) を行う、ということになりますが、この評価結果自体に意味はありません。 重要なのは、s演算子の中身です。文字列置換の機能を持つ s演算子に空の

はじめに CodeIQという所で開催していた「先制 hello, world」という、総当たり式変則コードバトルに参加しました。 codeiq.jp 出題者の@Nabetani 鍋谷さんは、これまでもこういった ( ゴルフやタイムアタックでない ) 変則的な、しかしながら面白いコードバトルを出題されています。 最終順位速報が出て、Perlで8位という結果になりました。本記事執筆時点 ( 2015/9/23 ) では、まだ詳細未公開ですが、途中で引っ込めたコード含め、少し解説したいと思います。 問題 レギュレーション コード自体は、“preemptive "hello, world"”という、空白含め25文字を出力するのみ ( 末尾の改行は任意 ) で、ASCIIコード32～126 の範囲の文字しかコードに使えない以外、特に制限はありません ( ※文字数は一応10,000字が上限だと思います

はじめに CodeIQというところで開催していた、多言語コードゴルフトーナメント「デスマコロシアム」に参加しました。↓の結果記事にある通り、惜しくも決勝で敗れましたが、Perl(44byte)で全言語最短タイ&準優勝という結果になりました。 codeiq.jp togetter.com Perlコードについては、優勝者のtailsさんと基本的に同じなのですが、他に挑戦した言語も含めて色々ネタばれしようと思います。 問題 お題 お題は、 abCDEfghIjklmnOpQrstuvwxyzabcDEFghiJklmnoPqRstuvwxyzabcdEFGhijKlmnopQrStuvwxyzabcdeFGHijkLmnopqRsTuvwxyzabcdefGHIjklMnopqrStUvwxyzabcdefgHIJklmNopqrsTuVwxyzabcdefghIJKlmnOpqrstUvWx