体験を伝える―『ガジェット通信』の考え方

面白いものを探しにいこう 本物を体験し体感しよう 会いたい人に会いに行こう 見たことのないものを見に行こう そしてそれをやわらかくみんなに伝えよう [→ガジェ通についてもっと詳しく] [→ガジェット通信フロアについて]

大人気ダンジョンシリーズ!循環のダンジョンの解説+最短コード発表

循環のダンジョン

今回の ダンジョンは、以下のような問題でした。

【問題】

標準入力から得られる値は「[213213213213,114214114214,434343439679]」のような、「角括弧で囲まれたカンマ区切りの数値」が並んだ文字列です。

このカンマ区切りの各要素を数値と見なして、2回以上繰り返されている場合は1を、そうでない場合は0を得て、「1,1,0」のような「カンマ区切り」にして、標準出力に戻します。

また、もし「12345 12345 12」のように、繰り返しが途切れている場合は「0」になります。

以下、例を示します。

例)
◆入力
[213213213213,114214114214,434343439679]

◆処理
213213213213の場合。
213 213 213 213 と繰り返されているので 1。

114214114214の場合。
114214 114214 と繰り返されているので 1。

434343439679の場合。
繰り返されていないので 0。

◆出力
1,1,0

【問題生成コード(JavaScript)】

// 疑似乱数
var rnd = (function() {
var z = 1234567890, x = z;
return function(){return(x=(x*z+z)&0x7FFFFFFF)>>16}
})();

var getS = function(n1, n2, n3) {
var r = “”, s = “”;
for (var i = n1; i–;) {s += n3 + rnd() % 4}
for (var i = n2; i–;) {r += s}
return r;
};

// 問題生成
var q = (function() {
var arr = [];
for (var i = 0; i < smplMax; i ++) {
var a = [1, 2, 3, 4, 6][rnd() % 5];
var b = 1 + rnd() % 12;
var c = [3, 4, 6][rnd() % 3];
var d = 12 – b;
var s = getS(a, b, 1) + getS(c, d, 6);
s = s.substr(0, 12);
arr.push(s);
}
return JSON.stringify(arr).replace(/”/g, “”);
})();
return q;
})(200);

この問題は、レベルごとに禁止事項が増えていきます。そのポイントと、解答コードを、以下に掲載します。

この問題は、言語不問ですが、解答例はJavaScriptで書きます。

レベル1解説

レベル1の禁止文字は、なしです。文字数制限600文字がありますが、基本的に自由にコードを書けます。

この問題は、いろいろな方法で解くことができます。ここでは、繰り返しパターンの認識ということで、正規表現を使って、答えを求めてみます。後方参照を使えば判定できます。

// 正規表現(85文字)
var a = eval(readline());
for (i in a) {
a[i] = +/^(.+)1+$/.test(a[i]);
}
print(a);

実はこの問題には、仕掛けがほどこされています。生成コードをよく見ると、繰り返される部分に使用されている文字は、1~4です。繰り返されない部分に使用されている文字は、6~9です。

そのことに気づくと、もっと短くコードを書くことができます。

// 末尾を見る1(82文字)
var a = eval(readline());
for (i in a) {
a[i] = +/[1-4]$/.test(a[i]);
}
print(a);

// 末尾を見る2(79文字)
var a = eval(readline());
for (i in a) {
a[i] = a[i] % 10 < 5 | 0; } print(a);

レベル2解説

レベル2では新たに、「 % /eval/i /for/i /while/i /until/i /loop/i /end/i /do/i > <」の禁止文字および正規表現が追加されています。これは、様々なプログラミング言語でループ処理を禁止するためのものです。

ループを使わず、配列をmapなどで処理それは、この制限は避けることができます。

以下、例を示します。分かりやすいように、処理を分解して書きます。

// 末尾を見る(100文字)
var a = readline().match(/[0-9]+/g);
a = a.map(function(s) {
return +/[1-4]$/.test(s)
});
print(a);

それでは以下、上位者のコードを紹介していきます。いろんなコードが見たいと思いますので、同じ方のコードでも、順位に当てはめて掲載しています。

レベル1「総合」の上位者コード(20位~11位)

20位のコード(72文字)

// みけCAT 様 (PHP)
<?php system(“perl -pe'”.’$_=~s/[?(w+)]?/0|$1=~m!^(.+)1+$!/eg’.”‘”);

19位のコード(70文字)

// iehn 様 (Ruby)
puts gets[1..-3].split(“,”).map{|s|s[0..3]*3==s||s==s[0..5]*2?1:0}*”,”

18位のコード(69文字)

// べーにー 様 (Python 3)
print(‘,’.join(str(1>>int(_)%9901)for _ in input()[1:-1].split(‘,’)))

17位のコード(68文字)

// ebicochineal 様 (Python)
print’,’.join(str((0in(i%(i/10**6),i%(i/10**8)))*1)for i in input())

// fine_M_account 様 (Ruby)
$><<gets[1..-3].split(“,”).map{|s|s[0,6]*2==s||s[0,4]*3==s ?1:0}*”,”

1 2 3 4 5 6 7 8 9 10 11 12次のページ
CodeIQ MAGAZINEの記事一覧をみる
  • 誤字を発見した方はこちらからご連絡ください。
  • ガジェット通信編集部への情報提供はこちらから
  • 記事内の筆者見解は明示のない限りガジェット通信を代表するものではありません。