『第7回デスマコロシアム』答案
CodeIQの『第7回デスマコロシアム』(※)に参戦しました。
※以下を特徴とするコードゴルフ大会です。
- ideoneで使用可能な言語なら何でもOK。
- 有利な言語に偏りすぎないよう、参戦人数の多い言語にはハンディあり。
- バイト数でなく、文字数で競う。
- import文は文字数カウント対象外、ideoneの自動生成部分もカウント対象外。(本稿のコードも、自動生成部分は略記しています)
第7回出題テーマは、「"deathma colosseum"を出力するbrainf**kのコード」を標準出力に出力する問題。brainf**kのコード自体は問題文で指定されているので、あまり深く考える必要は無く、要は「>("deathma colosseum"の各文字のasciiコード).」という文字列を出力するだけです。問題もシンプルなので、以下を以下に短く書けるかが短縮化のポイントとなったのかなと思います。
- 文字列から各文字をiterateする
- 文字をasciiコード(数値)に変換する
- "+"を指定した回数繰り返す
- 上記の結果を標準出力に出力する
いつもCOBOLでばかり参加していたので、今回は勉強がてら色々な言語で書いてみました。
Clojure(70)
(doseq[%"deathma colosseum"](printf">%s."(apply str(repeat(int%)'+))))
- 普通にmap関数とかを使って書くと遅延シーケンスに苦しめられるので、doseqで書くのが良さそうです。
C#(74)
foreach(int c in"efbuinb!dpmpttfvn")Console.Write(">"+".".PadLeft(c,'+'));
- 「"+"を指定した回数繰り返す」&「その後に"."を出力する」処理を「"."を指定桁になるよう"+"で桁揃えして出力」として一遍に行うことで、多少文字が稼げます。そのために"deathma colosseum"の文字そのものでなく、各文字をrot-1した"efbuinb!dpmpttfvn"をiterateしてやる必要があります。
F#(73)
"efbuinb!dpmpttfvn"|>Seq.iter(fun c->printf">%s"(".".PadLeft(int c,'+')))
- 同上。文字列とかのiterateがC#よりも1文字だけ楽なのかな。
Go(72)
import . "strings" for _,c:=range"deathma colosseum"{fmt.Printf(">%s.",Repeat("+",int(c)))}
- 冒頭に挙げたポイントのどれもが少しずつ書き辛く、もどかしい言語です。
Groovy(48)
'deathma colosseum'.any{print">${'+'*(int)it}."}
- 今回書いた言語では唯一、無名関数の引数を宣言しなくても"it"として参照できる点が有利そうでした。(一応Scalaもできるけど、癖が有って今回の短縮には使えなそうでした)
- ".each"でなく".any"を使って1文字短縮するあたりがちょっとしたコツでしょうか。
Haskell(64)
import Data.Char mapM putStr$[">"++([1..ord c]>>"+")++"."|c<-"deathma colosseum"]
- 文字列の結合に"++"と2文字必要となるのが辛い。
Java/Java7(95)
import static java.lang.System.out; import static java.lang.String.format; for(int i:"efbuinb!dpmpttfvn".toCharArray())out.print(format(">%"+i+"s",'.').replace(' ','+'));
Java/Java7(91)※機種依存でCodeIQ投稿不可、ideoneでは稼働
for(int i:"𐮑n".toCharArray())out.print(format(">%"+i%200+"s",'.').replace(' ','+'));
Nemerle(69)
using System.Console; using System.Convert; foreach(c in"deathma colosseum")Write($">$(String('+',ToInt32(c))).")
- これもどうも、今回は活躍し辛い言語。
PHP(74)
for($s="efbuinb!dpmpttfvn";$i<17;)echo str_pad(">",ord($s[$i++]),"+").".";
Python(59)
print"".join('>'+'+'*ord(c)+'.'for c in"deathma colosseum")
- 末尾の改行/空白無しでのprintが結構面倒なので、printは一度に抑える形の方が楽そうです。
- foreach的なことをするために、リスト内包表記([f(n) for n in ほげほげ])とするよりも、ジェネレータ式(f(n) for n in ほげほげ)とすることで括弧がちょっと減らせます。
Python 3(54)
for b in b"deathma colosseum":print('>'+'+'*b,end=".")
Pythonのジェネレータによる、べき集合列挙の高速化
前回の問3.5「真に平等な分割」を力技で解くためのべき集合列挙を、
ジェネレータを用いて再帰的にやってみました。
def main(): #〜〜〜中略〜〜〜 for s in powerset_generator(numbers_to_divide): if sum(s) == sum1 and square_sum(s) == sum2 and cube_sum(s) == sum3: print(s) end = datetime.now() print("Time: " + str(end - start)) #与えられた集合(配列)のべき集合の要素を順に返すジェネレータ def powerset_generator(provided_set): if len(provided_set) > 0: for c in powerset_generator(provided_set[1:]): yield [provided_set[0]] + c yield c else: yield []
結果は下記の通り。マスキング変数を用いた手続的な方法よりも7倍以上高速でした。
[*************]
[*************]
Time: 0:00:00.105000
『続・とっておきの数学パズル』を力技で解く、またはべき集合の列挙を実装してみた
帰省の暇つぶしに、と衝動買い。
- 作者: ピーター・ウィンクラー,坂井 公,岩沢 宏和,小副川 健
- 出版社/メーカー: 日本評論社
- 発売日: 2012/07/09
- メディア: 単行本
- クリック: 2回
- この商品を含むブログを見る
新鮮でバラエティに富んだ、しかも歯応えのある問題が多く、
頭の体操――かなりハードな――として非常にお買い得な一冊でした。
以下は本書の問3.5「真に平等な分割」という問題。
1から16までの整数を、要素の個数が等しい2つの集合に分ける。
2つの集合は、それぞれの和が等しく、各々の数の2乗の和も等しく、さらに各々の数の3乗の和も等しいように分けたい。
さて、どのように分ければいいだろうか?
これがなかなか解けなかったので、あきらめて力技で解くことにしました。
1〜16の集合を2分割する全てのパターン、要はべき集合について各種の和を求めていくことになります。
べき集合の要素を順に返すイテレータを作成する方針で実装してみました。
from datetime import datetime def main(): #問題3.5の各種定義 def square_sum(s): #数値配列の二乗和を返す return sum(map(lambda x: x*x, s)) def cube_sum(s): #数値配列の三乗和を返す return sum(map(lambda x: x*x*x, s)) numbers_to_divide = range(1,17) #分割対象となる配列([1,2,3,..,16]) sum1 = sum(numbers_to_divide) / 2 sum2 = square_sum(numbers_to_divide) / 2 sum3 = cube_sum(numbers_to_divide) / 2 #配列のべき集合を走査 start = datetime.now() #計算時間測定用 for s in PowersetProvider(numbers_to_divide): if sum(s) == sum1 and square_sum(s) == sum2 and cube_sum(s) == sum3: print(s) end = datetime.now() print("Time: " + str(end - start)) #与えられた集合(※)のべき集合の要素を順に返すイテレータ #(※ただし、入出力ともに集合は配列の形式をとる) #nextでの出力対象を決定するための、マスキング変数(※)をメンバとして持つ。 # #※マスキング変数を2進表示した数をb(bn,...,b2,b1)とすると、 # 与えられた配列のi番目を次回出力に... # 含める:bi桁目=1, 含めない:bi=0 の値を持つ # 例) # 与えられた集合が[3,1,4,5]でマスキング変数が9(2進で1010)の場合 # [1,5]を次回のイテレーションで出力する。 class PowersetProvider: #出力を制御するマスキング変数を初期化する。 def __init__(self, provided_set): #マスキング変数を初期化(初回出力は空集合となる) self.mask = 0 self.set = provided_set def __iter__(self): return self #現在のマスキング変数に相当する集合を出力し、 #その後マスキング変数を1加算する。 def __next__(self): #イテレーションが終了していた場合、StopIteration例外を投げる if self.mask == 2 ** len(self.set): raise StopIteration rtn = [] #マスキング変数を2進数と見て、各桁の0/1により出力を制御する for i in range(0, len(self.set)): if (self.mask >> i & 1) == 1: rtn.append(self.set[i]) self.mask += 1 return rtn if __name__ == '__main__': main()
結果は下記の通り。
べき集合の全要素(65536集合)を走査している割には、思ったより早いですね。
(ネタバレになるので、出力部分は*で伏せています)
再帰でのべき集合列挙も考えられるので、また暇なときにやってみようと思います。
[*************]
[*************]
Time: 0:00:00.738000
「7つの言語 7つの世界」 Prolog 2日目セルフスタディ(sort)
- リスト内の要素をソートせよ.
という単純な課題。セオリー通りクイックソートでチャレンジ。
divide ルールの条件分岐っぽい部分など、もうちょっと書き方が有る気がする。
% Main program of quick sort which allows duplicate elements. % ex) % qsort([3, 1, 4, 1, 4], [1, 1, 3, 4, 4]). qsort([], []). qsort([Head|Tail], Sorted) :- divide(Tail, Head, Lessor, Greator), qsort(Lessor, SortedLessor), qsort(Greator, SortedGreator), appendAll([SortedLessor, [Head], SortedGreator] , Sorted). % Divide a list into two lists, % one consists of elements which is smaller than or equal to the pivot, % the other consists of elements which is bigger than the pivot, % ex) % divide([1, 2, 3], 2, [1, 2], [3]). divide([], _, [], []). divide([Head|Tail], Pivot, Lessor, Greator) :- Pivot >= Head, divide(Tail, Pivot, SubLessor, Greator), append(SubLessor, [Head], Lessor). divide([Head|Tail], Pivot, Lessor, Greator) :- Pivot < Head, divide(Tail, Pivot, Lessor, SubGreator), append(SubGreator, [Head], Greator). % Binds the concatenation of more than two lists. % ex) % appendAll([[1, 2], [3, 4], [5, 6]], [1, 2, 3, 4, 5, 6]). appendAll([], []). appendAll([Head|Tail], ResultList) :- appendAll(Tail, SubList), append(Head, SubList, ResultList).
「論理少女」
数学ガール、とか、論理トレーニング、とかが好きな身としてタイトルに抗しきれず衝動買い。
- 作者: つじ要
- 出版社/メーカー: 講談社
- 発売日: 2008/09/22
- メディア: コミック
- 購入: 56人 クリック: 2,332回
- この商品を含むブログ (60件) を見る
「津隠問答」と呼ばれる、場所・道具なんでもありの対戦型論理クイズが流行する津隠市。
そんな津隠に転入した主人公(論理音痴)が、不良から、生徒会長から問答を叩きつけられるお話。
嘘喰をとってもほのぼのさせて、パズルを簡単にした感じ。
(とはいえ、完全情報な問題が多いだけ、本書の方がフェア感は有る。)
冒頭、自販機の故障に出会った生徒会長の
私が本来何を飲みたかったのか・・・
論理的に当てなさい
から始まる物語に、論理パズルへのワクワクが高まったものの、
1巻の問題には簡単/有名なものが多く、やや拍子抜けした感じはします。
とはいえ、有名なパズルを身近な状況にアレンジするという見せ方、
物語を考えている方も楽しいだろうなーと思いました。
「ヴォルフズムント」「キガタガキタ」
ちょっとした資格試験を受けた帰りに、
開放感もあって2冊を衝動買い。
- 作者: 久慈光久
- 出版社/メーカー: エンターブレイン
- 発売日: 2010/02/15
- メディア: コミック
- 購入: 16人 クリック: 175回
- この商品を含むブログ (60件) を見る
舞台背景としては以下のような感じ。
14世紀初頭、アルプス地方。イタリアへと通じるザンクト=ゴットハルト峠には、非情な番人が守る関所があった。難攻不落をもって知られるその場所を、人々はこう呼んだ。ヴォルフスムント
舞台設定や絵の雰囲気、過酷さに比しての救いの薄さなど、ヴィンランド・サガに近いものを感じますが、あちらに比べると奥深さに欠ける印象。
一巻を終えた時点では、特定の主人公不在(峠を抜けようとする人々の群像物)というのもその一因でしょう。
さらになにより、敵役のヴォルフラム(赤法師レゾと市丸ギンを足したような狐目キャラ)が冷血/超人すぎて感情移入し辛いというのが大きいかもしれません。
今後の展開やストーリーの深まりが気になるといえば気になりますが……この調子で続くと単純に憂鬱になりそうなので、2巻の購入は様子見でいきたいと思います。
キガタガキタ!~「恐怖新聞」より~ 1 (少年チャンピオン・コミックス)
- 作者: つのだじろう,西条真二
- 出版社/メーカー: 秋田書店
- 発売日: 2010/12/08
- メディア: コミック
- クリック: 24回
- この商品を含むブログ (9件) を見る
こっちを後に読みましたが、読後の気分が良い漫画でした。後に回して正解
恐怖新聞のスピンアウト作品であり、あちらの主人公、鬼形礼の血族にあたる「鬼形冥」が本策の主人公となっています。
鉄鍋のジャンの作者が描く「鬼形」は、攻撃的で、悪ぶっていながら正義臭くて、隅から隅までとても痛快なのです。
脇役も魅力的です。
男勝りだけど動物大好きで悪霊まで自宅で飼ってしまう「真淵沢妖湖」や、
冥に救われて以来彼に惚れ込み半ばストーカーと化してしまった「首(オビト)加世」など、病的だけれど愛嬌のある少女がちょこちょこ出てきます。
加えて悪役も、なんだかエロい味付けをされた「恐怖新聞」を中心に、それぞれ良い味を出しています。
これは買って読み続けたいなーと思わせる一冊でした!
Django 導入メモ(Part 1)
プロジェクト/アプリケーション作成〜サーバ起動
C:\etc\src\django>django-admin.py startproject test14
C:\etc\src>cd django\test14
C:\etc\src\django\test14>manage.py startapp microblog
C:\etc\src\django\test14>manage.py runserver