第4回 社内プログラミングコンテスト『コラッツリス』

皆さん、こんにちは! 社内プログラミングコンテスト担当の二木です。

以前、社内プログラミングコンテスト(以下、社内プロコン)について、ブログ記事を書かせて頂きました。その時は、社内プロコン開催のきっかけや、運営側の仕事とその内容、そして第1回から第3回までの簡単な説明をしました。それが2年前のことです。そして、社内プロコンは年1回の間隔で開催されており、この2年間で第4回と第5回が開催されました。

• 第4回 Fixstars社内プログラミングコンテスト2015 『コラッツリス(Collatzris)』
• 第5回 Fixstars社内プログラミングコンテスト2016 『ライフゲームGO』

今回は2015年に行った第4回社内プロコン『コラッツリス』についての記事となります。

コラッツリス(Collatzris)

コラッツリス(Collatzris)とは、コラッツ問題(Collatz problem)とテトリス(Tetris)から作られた名称で、今回の社内プロコンのために作ったオリジナルの落ち物ゲーム(落ちゲー)のことです。ルールは簡単で、3桁の数字(数字ブロック)を指定されたフィールド内に積み上げて、横一列がすべて数字で埋まるとその列が消えて得点になります。これだけであれば、簡易テトリスですが、得点の計算方法が特殊で、消した数字からコラッツの数列を求めて、その数列の項数が得点となります。

コラッツの数列とは、任意の正の整数 n に対し、以下のルールを適用し、n が 1 になるまで繰り返した際に計算された n を並べたものです。

• n が偶数の場合、n を 2 で割る
• n が奇数の場合、n に 3 を掛けて 1 を足す

そして、コラッツの問題は n が必ず 1 になるという予想のことです。予想とあるようにこの問題は未解決問題の一つとなっています。つまり、この予想が外れるということは、ある n に対して無限数列が存在することになりますが、現在のところそのような n は見つかっていません。

下記のPythonの関数は n を与えた際にコラッツの数列の項数を求めます。そして、コラッツリスでは消した数字ブロックを n としたときのそれが得点となります。

def calc_score(n):
    score = 0
    while n > 1:
         n = (n << 1) + n + 1 if n & 1 else n >> 1
         score += 1
    return score

では、試しにプレイしてみましょう。フィールドは7×7マスとして”362″, “589”, “302”が順番に落ちてくるとします。”362″と”302″を以下のように落としました。

次に”302″が落ちてきますが、”362″と”589″の間には1マスしかないので、”302″のブロックを縦にしてそのまま落としてみます。そうすると以下のような状態になります。

見事、横の7マスが埋まりました! これでこの数字”3622589″を消すことができます。この数字を使って、コラッツの問題のアルゴリズム通りに数列を求めてみます。

3622589-10867768-5433884-2716942-1358471-4075414-2037707-6113122-3056561-9169684-4584842-2292421-6877264-3438632-1719316-859658-429829-1289488-644744-322372-161186-80593-241780-120890-60445-181336-90668-45334-22667-68002-34001-102004-51002-25501-76504-38252-19126-9563-28690-14345-43036-21518-10759-32278-16139-48418-24209-72628-36314-18157-54472-27236-13618-6809-20428-10214-5107-15322-7661-22984-11492-5746-2873-8620-4310-2155-6466-3233-9700-4850-2425-7276-3638-1819-5458-2729-8188-4094-2047-6142-3071-9214-4607-13822-6911-20734-10367-31102-15551-46654-23327-69982-34991-104974-52487-157462-78731-236194-118097-354292-177146-88573-265720-132860-66430-33215-99646-49823-149470-74735-224206-112103-336310-168155-504466-252233-756700-378350-189175-567526-283763-851290-425645-1276936-638468-319234-159617-478852-239426-119713-359140-179570-89785-269356-134678-67339-202018-101009-303028-151514-75757-227272-113636-56818-28409-85228-42614-21307-63922-31961-95884-47942-23971-71914-35957-107872-53936-26968-13484-6742-3371-10114-5057-15172-7586-3793-11380-5690-2845-8536-4268-2134-1067-3202-1601-4804-2402-1201-3604-1802-901-2704-1352-676-338-169-508-254-127-382-191-574-287-862-431-1294-647-1942-971-2914-1457-4372-2186-1093-3280-1640-820-410-205-616-308-154-77-232-116-58-29-88-44-22-11-34-17-52-26-13-40-20-10-5-16-8-4-2-1

最後は1になって終了です。これで求めた数列の項を数えてみます(ただし最後の1は省きます)。234個入っていましたので、スコアは234になります。

では実際にプレイしてみましょう。プログラムはPython 2.7で書かれていてプロンプトやターミナル上で実行できます。一応、Windows, Mac, Linuxで動作することは確認しています。

• collatzris.py

さて、数列が最も長くなるような数字を考えて数字ブロックを消していきましょう! …といいたいところですが、さすがに人間がプレイ中にコラッツの数列を計算するのには無理があります。

そこでコラッツリスのソルバを作り、その得点ができるだけ高得点になるようにみんなで競い合う、というのが今回のプロコンの目的になります。

どうやって解く?

さて、どのようにコラッツリスのソルバを作れば良いのでしょうか?

目的としては、高いスコア、つまり長い数列を作ることになるのですが、これが一筋縄では行きません。ある程度以下の桁数であれば全部計算してしまう方法もあります。しかし、今回は時間制限もありますし、最大の幅が200桁で3段まで増えますので、最大600桁のコラッツの数列を求めることになります。600桁でなく100桁であっても数列の項数が多くなるような値をきちんと求めるのは非常に困難です。

一方、ある数字に対してコラッツの数列を求めるのは上述のコードを見ても比較的簡単であることが分かります。それであれば、たくさんの数字をできるだけ多く調べ上げて、その中で最も項数の多かった数字を選ぶという方法が考えられます。そして、そのためにはプログラムの高速化が必須になってきます。いわゆる、高速化ゲームです。

今回の優勝者の簡単な解説スライドとソルバを載せておきます。かなりガチに高速化してあるコードですが、是非解読してみてください。

• 優勝者のソルバプログラム(C++)

また、結果発表会も毎回開催しているのですが、その時の資料を匿名化して上げておきます。

最後に

『コラッツリス』は高速化ゲームでしたが、社内プロコンでは毎年いろいろなジャンルの問題を出題しています。第5回の『ライフゲームGO』は2人対戦型ゲームの思考ルーチンを考える問題でした。これについてはまた機会を設けて記事にしたいと思います。

そして、今年も第6回となる社内プロコンを開催する予定です。社内とありますが社外の方のエントリーも受け付けていますので、興味のある方は是非参加してみてください!

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください。