第8回 フィックスターズ社内プログラミングコンテスト『素数大貧民』開催

2019年12月27日

問い合わせ先: contest2019@fixstars.com

※ 諸事情により、コンテストの締め切りを 2020年5月8日(金) 12:00 に延長いたします。また、2020年3月中にコンテストサイトの公開を予定しております。

はじめに

今年度もフィックスターズ社内プログラミングコンテストが開催されました。今年度から社内のSaaS事業部に協力してもらい、Web上から参加登録とコードの投稿ができるようになります。本コンテストのサイトは来年2020年1月3月公開予定です。

今回のコンテストテーマ「素数大貧民」について説明します。必要なプログラムや実例コードは公開していますので、年末年始で挑戦してみてはいかがでしょうか。締め切りは2020年3月5月を予定していますので余裕をもって取り組めるかと思います。

概要

「素数大貧民」は素数大富豪として知られているトランプゲームのコンピュータ対戦版となります。対戦プログラムにターゲットを絞ったオリジナルのルールなどが追加されていますので、知略戦略を駆使したコーディングで対戦相手に勝利しましょう!

素数大貧民

ゲームの流れ

  1. カード(3001枚; 1～9のカードが各300枚、0のカードが301枚)をよくシャッフルしたうえで4人のプレイヤーに同枚数ずつ(原則は素数枚数ずつ 199枚)配り、残ったカードは山札として中央に積む。
  2. 最初の親が手札から最初の数を出し、以降順番に次のプレイヤーがカードを出し重ねていく。最初の数はカードを最大5枚まで使用してよい。最上位桁には0は使えない。
  3. 次のプレイヤーは、手番が回ってきた時点で「場に出されたすべてのカードと同じ枚数」かつ「直前に出された数より大きい数」しか出すことができない
    • 例1: 場には2のカードが1枚出ている → 1枚で3以上の大きさのカードしか出せない
    • 例2: 場には2, 5, 13で全部で4枚のカードが出ている → 4枚で4桁の素数を出す
  4. 出せるカードがない時、もしくは戦略上出したくない時にはパスが許される。パスの回数は制限されない。パスの際には山札からカードを5枚引く。
  5. 他のプレイヤー全員がパスし、再び場にあるカードを出したプレイヤーまで順番が回ってきたらそのプレイヤーは親になる。このとき、場にあるカードは流され(場から退けられ)、親は手札から5枚までの好きな素数を出せる。
  6. 以上を繰り返し、手札が無くなった(上がった)プレイヤーが出るか、山札がなくなった時点でゲームが終了する。

勝敗・スコア

ゲーム終了時の手札の枚数がスコアとなる。
より小さいスコアを得た者が勝者となる。

ペナルティ

素数でない数を出す等、プレイヤーがルールに反する行動を取った場合は、そのプレイヤーは即座に失格となり以降そのゲームに参加できずスコアは3001点となる。

特別ルール

メルセンヌ素数切り

メルセンヌ素数(2p-1)が出たら即座に場が流れ、メルセンヌ素数を出した者が次の親になる。「メルセンカット」とも呼ばれる。

ベルフェゴール素数切り

自分の手番であればいつでもベルフェゴール素数(1000000000000066600000000000001)を出して即座に場を流すことができる。ベルフェゴール素数を出した者が次の親になる。「ベルフェカット」とも呼ばれる。

悪魔ベルフェゴール

コンテスト内容

制御プログラム

概要

制御プログラム( prime_daihinmin.py )は対戦する参加者の名前とその対戦プログラムを引数に取ることで、その対戦プログラム同士の対戦をさせることができます。

実行方法は以下の通りです。

$ ./prime_daihinmin.py [オプション] プレイヤー1の名前 プレイヤー1の対戦プログラム プレイヤー2の名前 プレイヤー2の対戦プログラム プレイヤー3の名前 プレイヤー3の対戦プログラム プレイヤー4の名前 プレイヤー4の対戦プログラム

オプション( -s )により対戦の途中結果を出力することが可能です。

実行例

プレイヤー A, B, C, D の4人の対戦で、それぞれの対戦プログラムは a, b, c, d とします。

$ ./prime_daihinmin.py A ./a B ./b C ./c D ./d

出力は以下のようになります。

players: A, B, C, D
stock: 2205
time limit: 10.0
Winner: B
1 : B 0 OK 9.986
3 : C 13 OK 9.947
3 : D 13 OK 9.985
4 : A 16 OK 9.871
stock: 2070
time (s): 0.338

下記のフォーマットに従っています。

players: [対戦者名]
stock: [残りの山札の枚数] (3001枚-199枚*4人=2205枚)
time limit: [一人当たりの持ち時間(秒)]
Winner: [勝者の名前]
[順位] : [名前] [残り枚数] [最後のステータス] [残り時間(秒)]
[順位] : [名前] [残り枚数] [最後のステータス] [残り時間(秒)]
[順位] : [名前] [残り枚数] [最後のステータス] [残り時間(秒)]
[順位] : [名前] [残り枚数] [最後のステータス] [残り時間(秒)]
stock: [ゲーム終了時の山札の枚数]
time (s): [経過時間]

対戦中のプレイ情報を表示した場合は以下のような出力になります。

players: A, B, C, D
stock: 2205
time limit: 10.0
init: A 0000000000000000001111111111111111122222222222222222333333333333333333344444444444444444444455555555555555666666666666666666666666666666677777777777777777788888888888888888888888888999999999999999999 () [OK]
init: B 0000000000000000000000000011111111111111111122222222222222222223333333333333333333333344444444444444444555555555555555556666666666666666666777777777777777777777888888888888888888888888999999999999999 () [OK]
init: C 0000000000000000000000111111111111111112222222222222222222222233333333333333333333344444444444444444444455555555555555555666666666666666677777777777777777888888888888888888888899999999999999999999999 () [OK]
init: D 0000000000000000111111111111111111111222222222222222222222333333333333333444444444444444444455555555555666666666666666666666666666777777777777777788888888888888888888889999999999999999999999999999999 () [OK]
play: A 00000000000000000011111111111111112222222222222222233333333333333333344444444444444444444455555555555555666666666666666666666666666667777777777777777788888888888888888888888888999999999999999999 (67631) [OK]
play: B 111111111111111122222222222222222223333333333333333333333344444444444444444555555555555555556666666666666666777777777777777777777888888888888888888888888999999999999999 (67631,1000000000000066600000000000001) [BELPHEGOR]
play: B 11111111111111222222222222222222233333333333333333333333444444444444444445555555555555555566666666666666667777777777777777777778888888888888888888888899999999999999 (8191) [MERSENNE]
play: B 1111111111112222222222222222222333333333333333333333334444444444444444455555555555555555666666666666666677777777777777777777788888888888888888888889999999999999 (8191) [MERSENNE]
play: B 1111111111122222222222222222233333333333333333333333444444444444444445555555555555555566666666666666667777777777777777777788888888888888888888889999999999999 (127) [MERSENNE]
play: B 111111111112222222222222222223333333333333333333333444444444444444445555555555555555566666666666666667777777777777777777788888888888888888888889999999999999 (3) [MERSENNE]
play: B 11111111122222222222222222233333333333333333333334444444444444444455555555555555555666666666666666677777777777777777777888888888888888888888999999999999 (8191) [MERSENNE]
play: B 1111111112222222222222222223333333333333333333334444444444444444455555555555555555666666666666666677777777777777777777888888888888888888888999999999999 (3) [MERSENNE]
play: B 111111122222222222222222233333333333333333333344444444444444444555555555555555556666666666666666777777777777777777778888888888888888888899999999999 (8191) [MERSENNE]
play: B 111111222222222222222223333333333333333333334444444444444444455555555555555555666666666666666677777777777777777778888888888888888888899999999999 (127) [MERSENNE]
play: B 1111112222222222222222233333333333333333333344444444444444445555555555555555666666666666666777777777777777778888888888888888888899999999999 (57467) [OK]
play: C 00000000000000000000001111111111111111122222222222222222222222333333333333333333344444444444444444444555555555555555556666666666666677777777777777777888888888888888888888899999999999999999999999 (57467,63463) [OK]
play: D 000000000000000011111111111111111111222222222222222222223333333333333344444444444444445555555555566666666666666666666666666777777777777778888888888888888888889999999999999999999999999999999 (57467,63463,2147483647) [MERSENNE]
play: D 00000000000000001111111111111111111122222222222222222222333333333333344444444444444445555555555566666666666666666666666666777777777777778888888888888888888889999999999999999999999999999999 (3) [MERSENNE]
play: D 000000000000000011111111111111111112222222222222222222233333333333344444444444444445555555555566666666666666666666666666777777777777778888888888888888888889999999999999999999999999999999 (31) [MERSENNE]
play: D 0000000000000000111111111111111111222222222222222222223333333333344444444444444445555555555566666666666666666666666666777777777777778888888888888888888889999999999999999999999999999999 (31) [MERSENNE]
play: D 0000000000000000111111111111111112222222222222222222333333333334444444444444444555555555556666666666666666666666666677777777777778888888888888888888889999999999999999999999999999999 (127) [MERSENNE]
play: D 00000000000000111111111111111122222222222222222233333333333444444444444444455555555555666666666666666666666666667777777777777888888888888888888889999999999999999999999999999999 (80021) [OK]
play: A 000000000000000000111111111111111222222222222222233333333333333333344444444444444444444455555555555555666666666666666666666666666677777777777777777888888888888888888888888899999999999999999 (80021,82619) [OK]
play: B 111112222222222222222333333333333333333334444444444444555555555555555566666666666666777777777777777888888888888888888899999999999 (80021,82619,2147483647) [MERSENNE]
play: B 1111222222222222222233333333333333333334444444444444555555555555555566666666666666777777777777777888888888888888888899999999999 (31) [MERSENNE]
play: B 11122222222222222223333333333333333334444444444444555555555555555566666666666666777777777777777888888888888888888899999999999 (31) [MERSENNE]
play: B 112222222222222222333333333333333334444444444444555555555555555566666666666666777777777777777888888888888888888899999999999 (31) [MERSENNE]
play: B 122222222222222233333333333333333444444444444455555555555555556666666666666677777777777777888888888888888888899999999999 (127) [MERSENNE]
play: B 12222222222222223333333333333333444444444444455555555555555556666666666666677777777777777888888888888888888899999999999 (3) [MERSENNE]
play: B 122222222222222233333333333333344444444444455555555555555566666666666666777777777777888888888888888888899999999999 (74357) [OK]
play: C 000000000000000000000011111111111111122222222222222222222222333333333333333333344444444444444444445555555555555555666666666666667777777777777777788888888888888888888889999999999999999999999 (74357,91541) [OK]
play: D 0000000000000011111111111111122222222222222222333333333344444444444445555555555566666666666666666666666667777777777788888888888888888889999999999999999999999999999999 (74357,91541,2147483647) [MERSENNE]
play: D 000000000000001111111111111112222222222222222233333333344444444444445555555555566666666666666666666666667777777777788888888888888888889999999999999999999999999999999 (3) [MERSENNE]
play: D 00000000000000111111111111122222222222222222333333333444444444444455555555555666666666666666666666666677777777777888888888888888888999999999999999999999999999999 (8191) [MERSENNE]
play: D 000000000000001111111111111222222222222222223333333334444444444445555555555566666666666666666666666777777777778888888888888888889999999999999999999999999999 (66949) [OK]
play: A 0000000000000000001111111111111112222222222222222333333333333333333444444444444444444445555555555555566666666666666666666666666677777777777777778888888888888888888888889999999999999999 (66949,96847) [OK]
play: B 22222222222222333333333333334444444445555555555555556666666666666777777777788888888888888888899999999999 (66949,96847,2147483647) [MERSENNE]
play: B 22222222222222333333333333334444444445555555555555556666666666666777777778888888888888888889999999999 (977) [OK]
play: C 000000000000000000000011111111111111122222222222222222222222333333333333333333444444444444444444455555555555555556666666666666677777777777777777888888888888888888888999999999999999999999 (977,983) [OK]
play: D 000000000000001111111111111222222222222222333333333444444444445555555555666666666666666666666667777777777888888888888888889999999999999999999999999999 (977,983,524287) [MERSENNE]
play: D 000000000000001111111111112222222222222233333333344444444444555555555566666666666666666666666777777777888888888888888889999999999999999999999999999 (127) [MERSENNE]
play: D 00000000000000111111111122222222222222333333333444444444445555555555666666666666666666666667777777778888888888888888999999999999999999999999999 (8191) [MERSENNE]
play: D 000000000000001111111111222222222222233333333344444444444555555555566666666666666666666667777777788888888888888899999999999999999999999999 (68927) [OK]
play: A 00000000000000000011111111111111222222222222222233333333333333333444444444444444444455555555555555666666666666666666666666666777777777777777788888888888888888888888999999999999999 (68927,84319) [OK]
play: B 2222222222222233333333333334444444445555555555556666666666666777777778888888888888899999999 (68927,84319,9588558983) [OK]
play: C 0000000000000000000011111111111111222222222222222222222233333333333333344444444444444445555555555555556666666666666677777777777777788888888888888888899999999999999999 (68927,84319,9588558983,49284957903383810497) [OK]
play: D 00000000001111111222222223333333444444455555556666666666666666677888888888888889999999999999999999 (68927,84319,9588558983,49284957903383810497,2587317562910472260647754790319699209469) [OK]
play: A 000000000111111111222222222233333333333444444444444455555556666666666666667777777778888888888899999 (68927,84319,9588558983,49284957903383810497,2587317562910472260647754790319699209469,51996435469706948835986588808252692463519038072976760652883784007601412198606379) [OK]
pass: B 222222222222222333333333333344444444455555555555555666666666666677777777888888888888888899999999 (68927,84319,9588558983,49284957903383810497,2587317562910472260647754790319699209469,51996435469706948835986588808252692463519038072976760652883784007601412198606379) [PASSED]
play: C 246669 (68927,84319,9588558983,49284957903383810497,2587317562910472260647754790319699209469,51996435469706948835986588808252692463519038072976760652883784007601412198606379,8930826576091108588020743078399536277756250024892814043441520906532921934270279180977889825312094208892264955514893630037710304712652594342351681677142814852603) [OK]
pass: D 0000000000011111111222222223333333444444445555555566666666666666666778888888888888889999999999999999999 (68927,84319,9588558983,49284957903383810497,2587317562910472260647754790319699209469,51996435469706948835986588808252692463519038072976760652883784007601412198606379,8930826576091108588020743078399536277756250024892814043441520906532921934270279180977889825312094208892264955514893630037710304712652594342351681677142814852603) [PASSED]
pass: A 00000000011111111112222222222333333333334444444444444555555566666666666666677777777777888888888888999999 (68927,84319,9588558983,49284957903383810497,2587317562910472260647754790319699209469,51996435469706948835986588808252692463519038072976760652883784007601412198606379,8930826576091108588020743078399536277756250024892814043441520906532921934270279180977889825312094208892264955514893630037710304712652594342351681677142814852603) [PASSED]
pass: B 12222222222222223333333333333344444444445555555555555556666666666666677777777888888888888888899999999 (68927,84319,9588558983,49284957903383810497,2587317562910472260647754790319699209469,51996435469706948835986588808252692463519038072976760652883784007601412198606379,8930826576091108588020743078399536277756250024892814043441520906532921934270279180977889825312094208892264955514893630037710304712652594342351681677142814852603) [PASSED]
play: C 466 (269) [OK]
play: D 0000000000011111111222222223333333444444445555555666666666666666667788888888888888999999999999999999 (269,859) [OK]
play: A 00000000011111111112222222222333333333344444444444445555555666666666666677777777788888888888999999 (269,859,386677) [OK]
play: B 12222222222222333333333333344444444455555555555555566666666666777777778888888888888999999 (269,859,386677,689468322689) [OK]
pass: C 34466699 (269,859,386677,689468322689) [PASSED]
play: D 0000000000111111122222223334444455555566666666666666678888888889999999999999 (269,859,386677,689468322689,888468396932048954179393) [OK]
play: A 00001111222222333334444445566666667777788888889999 (269,859,386677,689468322689,888468396932048954179393,314461316665223684455504127310088406271099438757) [OK]
pass: B 1122222222222223333333333333444444444555555555555555566666666666777777778888888888888899999999 (269,859,386677,689468322689,888468396932048954179393,314461316665223684455504127310088406271099438757) [PASSED]
pass: C 0234445566699 (269,859,386677,689468322689,888468396932048954179393,314461316665223684455504127310088406271099438757) [PASSED]
pass: D 000000000011111111122222222333444444555555666666666666666778888888889999999999999 (269,859,386677,689468322689,888468396932048954179393,314461316665223684455504127310088406271099438757) [PASSED]
play: A 000111122222233334444445566666677777888889999 (80863) [OK]
play: B 11222222222222233333333333344444444455555555555555566666666666777777788888888888889999999 (80863,89753) [OK]
play: C 046 (80863,89753,4692435569) [OK]
play: D 0000000011111112222344444555556666666666666778888888999999999 (80863,89753,4692435569,14859221293200389669) [OK]
play: A 24447 (80863,89753,4692435569,14859221293200389669,3276461569491726573324230160888089821697) [OK]
play: B 245566889 (80863,89753,4692435569,14859221293200389669,3276461569491726573324230160888089821697,53242668328525876338894565325425248357524557353894366628326757498341632997287981) [OK]
pass: C 00346689 (80863,89753,4692435569,14859221293200389669,3276461569491726573324230160888089821697,53242668328525876338894565325425248357524557353894366628326757498341632997287981) [PASSED]
pass: D 000000000011111112222334444445555566666666666667788888888999999999 (80863,89753,4692435569,14859221293200389669,3276461569491726573324230160888089821697,53242668328525876338894565325425248357524557353894366628326757498341632997287981) [PASSED]
pass: A 0222444679 (80863,89753,4692435569,14859221293200389669,3276461569491726573324230160888089821697,53242668328525876338894565325425248357524557353894366628326757498341632997287981) [PASSED]
play: B 24688 (5569) [OK]
play: C 0689 (5569,6043) [OK]
play: D 0000000001111111222334444455555666666666667788888889999999 (5569,6043,68490629) [OK]
pass: A 000222444566779 (5569,6043,68490629) [PASSED]
pass: B 0234668889 (5569,6043,68490629) [PASSED]
pass: C 013556889 (5569,6043,68490629) [PASSED]
play: D 000000000111111122234444455555666666666667788888889999999 (3) [MERSENNE]
play: D 0000000011111112223444445555566666666677888888999999 (86069) [OK]
play: A 0002245667 (86069,94427) [OK]
pass: B 022344456688899 (86069,94427) [PASSED]
pass: C 00133455678899 (86069,94427) [PASSED]
play: D 000000001111112244555556666666688888999999 (86069,94427,2147483647) [MERSENNE]
play: D 00000000111111244555556666666688888999999 (2) [OK]
play: A 000224667 (2,5) [OK]
play: B 0234445668889 (2,5,29) [OK]
play: C 0045567889 (2,5,29,1933) [OK]
play: D 000000011111244555666666888899999 (2,5,29,1933,66585091) [OK]
pass: A 00022234446677 (2,5,29,1933,66585091) [PASSED]
pass: B 002233344456688899 (2,5,29,1933,66585091) [PASSED]
pass: C 002455567788899 (2,5,29,1933,66585091) [PASSED]
play: D 0000000111124455566666888899999 (61) [OK]
play: A 000222444667 (61,73) [OK]
play: B 02233444566889 (61,73,8039) [OK]
play: C 0255778 (61,73,8039,64808599) [OK]
play: D 001124456668889 (61,73,8039,64808599,9665900099850011) [OK]
pass: A 00002222444466778 (61,73,8039,64808599,9665900099850011) [PASSED]
pass: B 0022334444566678889 (61,73,8039,64808599,9665900099850011) [PASSED]
pass: C 001245557778 (61,73,8039,64808599,9665900099850011) [PASSED]
play: D 00114456668889 (2) [OK]
play: A 0000222244446678 (2,7) [MERSENNE]
play: A 0000222244466 (487) [OK]
play: B 0022344445666888 (487,739) [OK]
play: C 055778 (487,739,207541) [OK]
play: D 05 (487,739,207541,616898464081) [OK]
pass: A 000001222224446669 (487,739,207541,616898464081) [PASSED]
pass: B 000022234444566678888 (487,739,207541,616898464081) [PASSED]
pass: C 00245577899 (487,739,207541,616898464081) [PASSED]
pass: D 0044569 () [PASSED]
play: A 000001222444666 (229) [OK]
play: B 000022444456667888 (229,283) [OK]
play: C 05778 (229,283,509429) [OK]
pass: D 000234445699 (229,283,509429) [PASSED]
play: A 246 (229,283,509429,204660020401) [OK]
pass: B 00000222344445666678889 (229,283,509429,204660020401) [PASSED]
pass: C 0122356778 (229,283,509429,204660020401) [PASSED]
pass: D 00002223344456899 (229,283,509429,204660020401) [PASSED]
pass: A 02455667 () [PASSED]
play: B 000002224446666788 (95483) [OK]
pass: C 011223356777889 (95483) [PASSED]
play: D 000022344458 (95483,96329) [OK]
pass: A 0124555667788 (95483,96329) [PASSED]
play: B 00224688 (95483,96329,6040460627) [OK]
pass: C 01122233335567777889 (95483,96329,6040460627) [PASSED]
pass: D 00002233444456889 (95483,96329,6040460627) [PASSED]
pass: A 012224455566777888 (95483,96329,6040460627) [PASSED]
pass: B 0022446668899 () [PASSED]
play: C 012223333556788 (77719) [OK]
play: D 000223444456 (77719,83089) [OK]
play: A 02455568 (77719,83089,7782827461) [OK]
pass: B 002244456666788899 (77719,83089,7782827461) [PASSED]
pass: C 01122233335567788889 (77719,83089,7782827461) [PASSED]
pass: D 00022234444555677 (77719,83089,7782827461) [PASSED]
pass: A 0233455556789 () [PASSED]
play: B 0022445666688899 (47) [OK]
play: C 011222333556778889 (47,83) [OK]
play: D 0022344455567 (47,83,4027) [OK]
play: A 33567 (47,83,4027,82555049) [OK]
play: B (47,83,4027,82555049,6246669588284009) [OK]
Winner: B
1 : B 0 OK 9.959
2 : A 5 OK 9.901
3 : D 13 OK 9.974
4 : C 18 OK 9.843
stock: 2000
time (s): 0.467

以下のフォーマットに従っています。

players: [対戦者名]
stock: [残りの山札の枚数] (3001枚-199枚*4人=2205枚)
time limit: [一人当たりの持ち時間(秒)]
[行動]: [名前] [カード] ([場札]) [[ステータス]]
[行動]: [名前] [カード] ([場札]) [[ステータス]]
[行動]: [名前] [カード] ([場札]) [[ステータス]]
[行動]: [名前] [カード] ([場札]) [[ステータス]]
[行動]: [名前] [カード] ([場札]) [[ステータス]]
.
.
.
[行動]: [名前] [カード] ([場札]) [[ステータス]]
[行動]: [名前] [カード] ([場札]) [[ステータス]]
[行動]: [名前] [カード] ([場札]) [[ステータス]]
Winner: [勝者の名前]
[順位] : [名前] [残り枚数] [最後のステータス] [残り時間(秒)]
[順位] : [名前] [残り枚数] [最後のステータス] [残り時間(秒)]
[順位] : [名前] [残り枚数] [最後のステータス] [残り時間(秒)]
[順位] : [名前] [残り枚数] [最後のステータス] [残り時間(秒)]
stock: [ゲーム終了時の山札の枚数]
time (s): [経過時間]

行動には init, play, pass があります。
ステータスには OK, PASSED, MERSENNE, BELPHEGOR, ERROR があります。
ERROR の場合には、エラーの概要について付記されています。

ソースコード ( prime_daihinmin.py )

#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""In-house Contest 2019: Prime Daihinmin (C) 2019 Fixstars Corp.
"""

import sys
import os
import time
import subprocess
import threading
import random
import json
import re
from optparse import OptionParser

VERSION  = "0.11"
REVISION = "a"
VER_DATE = "20191225"

TIME_LIMIT = 10.0
SHOW_GAME = False
DEBUG_PRINT = False

def debug_print(msg):
    if DEBUG_PRINT:
        print(msg, file=sys.stderr)

def read_response(player):
    if player.time <= 0.0:
        return None, 0.0
    start_time = time.time()
    class ExecThread(threading.Thread):
        def __init__(self, solver):
            self.solver = solver
            self.response = None
            threading.Thread.__init__(self)
        def run(self):
            self.response = self.solver.stdout.readline().strip()
        def get_response(self):
            return self.response
    t = ExecThread(player.solver)
    t.setDaemon(True)
    t.start()
    if t.isAlive(): t.join(player.time)
    player.time -= time.time() - start_time
    return t.get_response(), player.time

class Player:
    def __init__(self, uid, name, solver, hand, status="OK"):
        self.uid = uid
        self.name = name
        self.solver = solver
        self.time = TIME_LIMIT
        self.hand = hand
        self.status = status

class PrimeDaihinmin:
    """PrimeDaihinmin class
    """

    NORMAL_STATES = ("OK", "MERSENNE", "BELPHEGOR")
    BELPHEGOR_PRIME = 1000000000000066600000000000001

    def __init__(self, players):
        self.num_players = len(players)
        self.num_draw_cards = 5
        self.num_hand = 199  # initial number of cards in a hand
        self.num_first_cards = 5
        self.stock = [i for i in range(10)] * 300 + [0]
        self.max_cards = len(self.stock)
        random.shuffle(self.stock)
        self.players = []
        self.player = None
        for uid, (name, solver) in enumerate(players):
            solver = subprocess.Popen(solver, shell=True, stdin=subprocess.PIPE, stdout=subprocess.PIPE)
            hand, self.stock = self.stock[:self.num_hand], self.stock[self.num_hand:]
            self.players.append(Player(uid, name, solver, sorted(hand)))
            debug_print("0 in hand: {}".format(hand.count(0))) #####
        self.numbers = []
        self.record = []

        print("players: {}".format(", ".join([player.name for player in self.players])), file=sys.stderr)
        print("stock: {}".format(len(self.stock)), file=sys.stderr)
        print("time limit: {}".format(TIME_LIMIT), file=sys.stderr)

    # Miller-Rabin primality test
    def is_prime(self, q, k=50):
       if q == 2: return True
       if q < 2 or q & 1 == 0: return False
       d = q - 1
       d //= d & -d
       for _ in range(k):
           a = random.randint(1, q - 1)
           t = d
           y = pow(a, t, q)
           while t != q - 1 and y != 1 and y != q - 1: 
               y = pow(y, 2, q)
               t <<= 1
           if y != q - 1 and t & 1 == 0:
               return False
       return True

    def is_Mersenne(self, n):
        while n:
            if n & 1 == 0:
                return False
            n >>= 1
        return True

    def check_TLE(self, player):
        if player.time <= 0.0:
            print("Error: time limit exceeded: {}".format(player.name,), file=sys.stderr)
            return True
        return False

    def record_cards(self, player, msg=""):
        global SHOW_GAME
        if SHOW_GAME:
            print("{} {} {} ({}) [{}]".format(msg, player.name, "".join(map(str, player.hand)), ",".join(map(str, self.numbers)), player.status), file=sys.stderr)
        self.record.append((player.name, player.status, len(player.hand), list(map(str, self.numbers[:]))))

    def clean_players(self):
        for p in self.players:
            if p.status == "PASSED":
                p.status = "OK"

    def next_player(self):
        if not self.player:
            return self.players[0]
        uid = self.player.uid
        cnt = 0
        while True:
            uid += 1
            uid %= self.num_players
            if self.players[uid].status in ("OK", "PASSED"):
               break
            if self.num_players == cnt:
                print("Error: invalid status in next_player", file=sys.stderr)
                break
            cnt += 1
        return self.players[uid]

    def check_finish(self):
        if not self.player.hand:
            print("Winner: {}".format(self.player.name), file=sys.stderr)
            self.clean_players()
            return True
        return False

    def initialize(self):
        names = [player.name for player in self.players]
        for player in self.players:
            try:
                data = json.dumps({"action": "init", "uid": player.uid, "names": names, "hand": player.hand, "time": TIME_LIMIT})
                debug_print("{}: {}".format(player.name, data)) ###
                player.solver.stdin.write(("%s\n" % data).encode("utf-8"))
                player.solver.stdin.flush()
                _, player.time = read_response(player)
                if self.check_TLE(player):
                    player.status = "ERROR:TLE in initialize"
            except Exception as e:
                player.status = "ERROR:ERROR in initialize"
                print("{}: {}".format(self.player.name, str(e)), file=sys.stderr)
        for player in self.players:
            self.record_cards(player, "init:")
        return True

    def play(self):
        while True:
            if self.num_players - 1 <= [bool(re.match("ERROR", p.status)) for p in self.players].count(True):
                self.clean_players()
                print("Only one survivor", file=sys.stderr) ###
                return True
            if self.num_players - [p.status not in self.NORMAL_STATES for p in self.players].count(True) == 1 and self.next_player().status in self.NORMAL_STATES:
                self.clean_players()
                self.numbers = []
                continue
            elif self.player and self.player.status in ("MERSENNE", "BELPHEGOR"):
                self.clean_players()
                self.numbers = []
            else:
                self.player = self.next_player()
            if re.match("ERROR", self.player.status):
                continue

            try:
                response = None
                if not re.match("ERROR", self.player.status):
                    data = json.dumps({"action": "play", "name": self.player.name, "hand": self.player.hand, "numbers": list(map(str, self.numbers)), "hands": [(p.name, len(p.hand)) for p in self.players], "record": self.record})
                    #debug_print("{}: {}".format(self.player.name, data)) ##### debug
                    self.player.solver.stdin.write(("{}\n".format(data)).encode("utf-8"))
                    self.player.solver.stdin.flush()
                    response, self.player.time = read_response(self.player)
                    data = json.loads(response.decode("utf-8"))
                    action = data["action"]  # number, pass, draw
                    if action == "number":
                        self.player.status = "OK"
                        cards = data["cards"]

                        # cards in self.players[current_uid].hand -> True
                        if False in [card in self.player.hand for card in cards]:
                            self.player.status = "ERROR:cards in self.players[current_uid].hand -> False"
                            debug_print("{}: {}".format(self.player.name, "cards in self.players[current_uid].hand -> False")) ### debug
                            continue

                        # removes cards from player.hand -> player.hand
                        for card in cards:
                            self.player.hand.remove(card)

                        # check_digits(number) -> True
                        debug_print("debug cards: {}".format(cards)) ##### debug
                        number = "".join(map(str, cards))

                        # check Belphegor prime -> True
                        if int(number) == self.BELPHEGOR_PRIME:
                            self.player.status = "BELPHEGOR"
                            self.numbers.append(int(number))
                            if self.check_finish():
                                return True
                            debug_print("number: {}: {}".format(self.player.name, number)) ##### debug
                            self.record_cards(self.player, "play:")
                            continue

                        if (len(self.numbers) == 0 and len(number) > self.num_first_cards) or (self.numbers and len(number) != len("".join(map(str, self.numbers)))):
                            self.player.status = "ERROR:check_digits(number) -> False"
                            debug_print("{}: {} {} {} {}".format(self.player.name, number, cards, self.numbers, self.player.status)) ### debug
                            continue

                        # cards -> number
                        number = int(number)

                        # prime_check(number) -> False
                        if not self.is_prime(number):
                            self.player.status = "ERROR:prime_check(number) -> False"
                            debug_print("{}: {}".format(self.player.name, self.player.status)) ### debug
                            continue

                        # Mersenne number -> True
                        if self.is_Mersenne(number):
                            self.player.status = "MERSENNE"

                        # numbers[-1] < number -> False
                        if self.numbers and number < self.numbers[-1]:
                            self.player.status = "ERROR:numbers[-1] < number -> False"
                            debug_print("{}: {}".format(self.player.name, self.player.status)) ### debug
                            continue

                        self.numbers.append(number)
                        debug_print("number: {}: {}".format(self.player.name, number)) ##### debug
                        self.record_cards(self.player, "play:")

                        # check passes
                        # len(player.hand) == 0 -> winner
                        if self.check_finish():
                            return True

                    elif action == "pass":
                        draw = []
                        for _ in range(self.num_draw_cards):
                            draw.append(self.stock.pop())
                            if not self.stock:
                                break
                        data = json.dumps({"action": "pass", "name": self.player.name, "draw": draw, "record": self.record})
                        self.player.solver.stdin.write(("{}\n".format(data)).encode("utf-8"))
                        self.player.solver.stdin.flush()
                        _, self.player.time = read_response(self.player)
                        self.player.status = "PASSED"
                        self.player.hand.extend(draw)
                        self.player.hand.sort()
                        debug_print("ctrl-pass: {}: {}, {}".format(self.player.name, draw, self.player.hand)) ##### debug
                        self.record_cards(self.player, "pass:")
                        if not self.stock:
                            print("No stock", file=sys.stderr) ###
                            self.clean_players()
                            return True
                    else:
                        pass

            except Exception as e:
                if self.check_TLE(self.player):
                    self.player.status = "ERROR:TLE in play"
                    debug_print("{}: {}".format(self.player.name, "TLE in play")) ### debug
                else:
                    self.player.status = "ERROR:ERROR in play ({})".format(str(e))
                print("{}: {}".format(self.player.name, str(e)), file=sys.stderr)

        return False

    def quit_game(self):
        for player in self.players:
            try:
                player.solver.stdin.write(("%s\n" % json.dumps({"action": "quit"})).encode("utf-8"))
                player.solver.stdin.flush()
                _, player.times = read_response(player)
            except:
                pass

    def finish(self):
        results = []
        for player in self.players:
            results.append([len(player.hand) if player.status in ("OK", "PASSED", "MERSENNE") else self.max_cards, player.name, player.status, player.time])
        results.sort()

        rank = self.num_players
        order = self.num_players
        prev_score = self.max_cards + 1
        for i in range(len(results)-1, -1, -1):
            if prev_score > results[i][0]:
                rank = order
            prev_score = results[i][0]
            results[i].append(rank)
            order -= 1

        for score, name, status, t, rank in results:
            print("{} : {} {} {} {:.3f}".format(rank, name, score, status, t))
        print("stock: {}".format(len(self.stock)))

        self.quit_game()
        if os.name == "posix":
            for player in self.players:
                pid = player.solver.pid
                #os.system("kill -{}".format(pid))
                os.system("pkill -TERM -P {}".format(pid))

def main():
    global TIME_LIMIT, SHOW_GAME, DEBUG_PRINT

    parser = OptionParser(usage="Usage: %prog [options] name1 command1 name2 command2 [name3 command3 ...]")
    parser.add_option("-s", "--show", action="store_true", dest="show", default=False, help="show game")
    parser.add_option("-t", "--time", action="store", type="float", dest="time", default=10.0, help="time limit")
    parser.add_option("-d", "--debug", action="store_true", dest="debug", default=False, help="print for debug")

    (options, args) = parser.parse_args()

    if len(args) < 4:
        parser.error("incorrect number of arguments")

    SHOW_GAME = options.show
    TIME_LIMIT = options.time
    DEBUG_PRINT = options.debug

    start_time = time.time()
    n = len(args) // 2
    players = [(name, solver) for name, solver in zip(args[0:2*n-1:2], args[1:2*n:2])]
    prime_daihinmin = PrimeDaihinmin(players)
    if prime_daihinmin.initialize():
        prime_daihinmin.play()
        prime_daihinmin.finish()
    print("time (s): {:.3f}".format(time.time() - start_time), file=sys.stderr) ###

if __name__ == "__main__":
    main()

対戦プログラム

対戦プログラムはコンテスト参加者が作成し、制御プログラムと標準入出力により情報の授受を行います。

図中の赤で示した文字列は、制御プログラムと対戦プログラムとの間で標準出力を介して通知するコマンドになっています。制御プログラム側からのコマンドは、すべてJSON形式で記述されています。後述のJSONの例では読みやすいように項目ごとに改行されていますが、実際に制御プログラムから送られてくるコマンドでは改行されていないのでご注意ください。

制御プログラムと対戦プログラムのコマンドの授受はすべて標準入出力を介して行われます。また、制御プログラムからコマンドが渡された場合、必ず標準出力で返さなくてはなりません。

実際の対戦プログラム内の処理については、後述の実例を参考にしてください。

プログラムのフロー

対戦のフロー

初期情報

ゲーム開始時に与えられる情報をJSON形式で受け取ります。

{
    "action": "init",
    "uid": プレイヤーの順番,
    "names": 全プレイヤーの名前,
    "hand": 自分の手札,
    "time": 制限時間
}

制御プログラムに改行コードを出力してJSON情報を受け取ったことを伝えます。

初期情報の例

{"action": "init", "uid": 0, "names": ["A", "B", "C", "D"], "hand": [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9], "time": 10.0}

プレイ情報

プレイ時に自分の手番で与えられる情報をJSON形式で受け取ります。

{
    "action": "play",
    "name": 自分の名前,
    "hand": 自分の手札,
    "numbers": 場札のリスト,
    "hands": プレイヤーの名前とその手札の枚数の組のリスト,
    "record": プレイ履歴
}

プレイ情報を受け取ったら以下の情報を制御プログラムに伝えます。場に出すカードのリストは、例えば手札を組み合わせて189を出したい場合、 [1, 8, 9] のような形式で記述します。

{
    "action": "number",
    "cards": [場に出すカードのリスト]
}

場にカードを出さずにパスする場合は以下の情報を伝えます。

{
    "action": "pass"
}

また、パスした場合は次のJSON情報を制御プログラムから受け取ります。

{
    "action": "pass",
    "name": 自分の名前,
    "draw": 場札から引いた札のリスト,
    "record": プレイ履歴
}

JSON情報を受け取った際には必ず改行コードを制御プログラムに伝えます。

プレイ情報の例

play の場合

{"action": "play", "name": "B", "hand": [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9], "numbers": ["5023", "9161", "75643823", "2874583935771349", "35404025429274045449205432555649", "5715069813304886242646945926773535452733380420623722734793008007"], "hands": [["A", 117], ["B", 149], ["C", 168], ["D", 89]], "record": [["A", "OK", 199, []], ["B", "OK", 199, []], ["C", "OK", 199, []], ["D", "OK", 199, []], ["A", "OK", 195, ["7699"]], ["B", "MERSENNE", 195, ["7699", "8191"]], ["B", "OK", 190, ["43013"]], ["C", "OK", 194, ["43013", "61559"]], ["D", "MERSENNE", 189, ["43013", "61559", "2147483647"]], ["D", "MERSENNE", 185, ["8191"]], ["D", "MERSENNE", 182, ["127"]], ["D", "MERSENNE", 181, ["3"]], ["D", "MERSENNE", 179, ["31"]], ["D", "MERSENNE", 176, ["127"]], ["D", "MERSENNE", 174, ["31"]], ["D", "MERSENNE", 172, ["31"]], ["D", "MERSENNE", 168, ["8191"]], ["D", "OK", 163, ["96469"]], ["A", "OK", 190, ["96469", "97883"]], ["B", "MERSENNE", 180, ["96469", "97883", "2147483647"]], ["B", "MERSENNE", 179, ["3"]], ["B", "OK", 174, ["65167"]], ["C", "OK", 189, ["65167", "76519"]], ["D", "MERSENNE", 153, ["65167", "76519", "2147483647"]], ["D", "MERSENNE", 151, ["31"]], ["D", "MERSENNE", 147, ["8191"]], ["D", "MERSENNE", 145, ["31"]], ["D", "MERSENNE", 143, ["31"]], ["D", "MERSENNE", 142, ["3"]], ["D", "MERSENNE", 140, ["31"]], ["D", "OK", 135, ["65053"]], ["A", "OK", 185, ["65053", "74411"]], ["B", "MERSENNE", 164, ["65053", "74411", "2147483647"]], ["B", "MERSENNE", 163, ["3"]], ["B", "MERSENNE", 162, ["3"]], ["B", "OK", 157, ["63781"]], ["C", "OK", 184, ["63781", "75653"]], ["D", "MERSENNE", 125, ["63781", "75653", "2147483647"]], ["D", "OK", 121, ["5023"]], ["A", "OK", 181, ["5023", "9161"]], ["B", "OK", 149, ["5023", "9161", "75643823"]], ["C", "OK", 168, ["5023", "9161", "75643823", "2874583935771349"]], ["D", "OK", 89, ["5023", "9161", "75643823", "2874583935771349", "35404025429274045449205432555649"]], ["A", "OK", 117, ["5023", "9161", "75643823", "2874583935771349", "35404025429274045449205432555649", "5715069813304886242646945926773535452733380420623722734793008007"]]]}

pass の場合

{"action": "pass", "name": "B", "draw": [3, 7, 9, 1, 8], "record": [["A", "OK", 199, []], ["B", "OK", 199, []], ["C", "OK", 199, []], ["D", "OK", 199, []], ["A", "OK", 198, ["5"]], ["B", "MERSENNE", 198, ["5", "7"]], ["B", "MERSENNE", 195, ["127"]], ["B", "OK", 190, ["11527"]], ["C", "OK", 194, ["11527", "28099"]], ["D", "MERSENNE", 189, ["11527", "28099", "2147483647"]], ["D", "MERSENNE", 188, ["3"]], ["D", "OK", 183, ["93281"]], ["A", "OK", 193, ["93281", "95429"]], ["B", "MERSENNE", 180, ["93281", "95429", "2147483647"]], ["B", "MERSENNE", 178, ["31"]], ["B", "OK", 173, ["69899"]], ["C", "OK", 189, ["69899", "85523"]], ["D", "MERSENNE", 173, ["69899", "85523", "2147483647"]], ["D", "MERSENNE", 170, ["127"]], ["D", "MERSENNE", 168, ["31"]], ["D", "MERSENNE", 165, ["127"]], ["D", "OK", 160, ["44549"]], ["A", "OK", 188, ["44549", "57329"]], ["B", "MERSENNE", 163, ["44549", "57329", "2147483647"]], ["B", "OK", 158, ["66851"]], ["C", "OK", 184, ["66851", "68993"]], ["D", "MERSENNE", 150, ["66851", "68993", "2147483647"]], ["D", "MERSENNE", 149, ["3"]], ["D", "MERSENNE", 147, ["31"]], ["D", "MERSENNE", 144, ["127"]], ["D", "MERSENNE", 143, ["3"]], ["D", "MERSENNE", 142, ["3"]], ["D", "OK", 137, ["94291"]], ["A", "OK", 183, ["94291", "98213"]], ["B", "MERSENNE", 148, ["94291", "98213", "2147483647"]], ["B", "OK", 143, ["72053"]], ["C", "OK", 179, ["72053", "85661"]], ["D", "MERSENNE", 127, ["72053", "85661", "2147483647"]], ["D", "MERSENNE", 126, ["3"]], ["D", "MERSENNE", 123, ["127"]], ["D", "MERSENNE", 121, ["31"]], ["D", "MERSENNE", 119, ["31"]], ["D", "MERSENNE", 116, ["127"]], ["D", "MERSENNE", 112, ["8191"]], ["D", "MERSENNE", 111, ["3"]], ["D", "OK", 106, ["69029"]], ["A", "OK", 178, ["69029", "89021"]], ["B", "MERSENNE", 133, ["69029", "89021", "2147483647"]], ["B", "MERSENNE", 130, ["127"]], ["B", "MERSENNE", 128, ["31"]], ["B", "OK", 123, ["88589"]], ["C", "OK", 174, ["88589", "90977"]], ["D", "OK", 96, ["88589", "90977", "6546860659"]], ["A", "OK", 158, ["88589", "90977", "6546860659", "91962251780691074309"]], ["B", "OK", 83, ["88589", "90977", "6546860659", "91962251780691074309", "2079064903797220801625795595787452852857"]], ["C", "OK", 94, ["88589", "90977", "6546860659", "91962251780691074309", "2079064903797220801625795595787452852857", "58880503313648081293450490406601846860466655951037994174011759755128840036343453"]], ["D", "PASSED", 101, ["88589", "90977", "6546860659", "91962251780691074309", "2079064903797220801625795595787452852857", "58880503313648081293450490406601846860466655951037994174011759755128840036343453"]], ["A", "PASSED", 163, ["88589", "90977", "6546860659", "91962251780691074309", "2079064903797220801625795595787452852857", "58880503313648081293450490406601846860466655951037994174011759755128840036343453"]]]}

レコード情報

プレイ情報に含まれるレコード情報(record)は以下のフォーマットとなっています。

[["プレイヤー名", "ステータス", 手札の枚数, [場札のリスト]], ..., ["プレイヤー名", "ステータス", 手札の枚数, [場札のリスト]]]

各プレイヤーが行動するたびにレコード情報に追加されます。

終了情報

ゲーム終了時に受け取る情報です。

{
    "action": "quit"
}

終了情報を受け取ったら対戦プログラムは改行コードを出力してからプログラムを終了します。

持ち時間について

それぞれの対戦プログラムには全部で10秒の持ち時間が定められており、制御プログラムから通知を受け取り、制御プログラムに通知を返すまでの時間が差し引かれていきます。持ち時間がすべて消費され、それ以上の時間を使おうとした場合、その対戦プログラムは負けとなります。

参加方法

本サイトでコンテストの登録をしてください。

  • 希望するユーザID
  • 32文字以内
  • 使用可能な文字は英数字・ピリオド(.)・ハイフン(-)
  • 先頭文字は英数字
  • ユーザIDが既に使用されている場合は別のユーザIDを再送信
  • 希望するユーザIDを指定しない場合は社内アカウントで登録

外部参加者においては、所属と氏名についてもご記入ください。ランキング等はすべてユーザIDで表示され、所属と氏名については外部に公開されることはありません。
コンテスト登録の後、最初のプログラムを提出した時点でコンテスト参加者となります。

プログラム提出

ソースコードは本サイトから提出してください。対戦プログラムは何度でも提出でき、ペナルティもありません。最後に提出したソースコードが最終スコアの対象となります。

テスト

提出されたプログラムが正式に登録されるためには、提出時に行われるシステムテストにパスする必要があります。システムテストでエラーが出た場合、提出者にフィードバックされます。

スコア

最終ランキングのスコアを求めるために、全参加者に対して総当たり戦を行います。

対戦の順位で点数が決まり順位がそのまま点数になり、全対戦の合計がスコアとなります。スコアが低いほど良いスコアとなります。同率1位が2名いる場合は、それぞれが2位となり2点、4人全員が同率の場合は、全員4位で4点となります。なお、参加人数などの条件によっては、対戦時のプレイヤー数や対戦数などを変更する場合があります。変更する場合は告知します。

制限事項

  • 使用するプログラミング言語はコンテストの実行マシン環境で利用できる言語であれば種類を問いません。一般的でない言語を使用する場合は、利用できるかどうか問い合わせをお願いします。
  • 確認済みプログラミング言語リスト
    • C++ (GCC 5.4.0)
    • C++ (Clang 3.8.0)
    • C (GCC 5.4.0)
    • C (Clang 3.8.0)
    • Python (3.6.4)
    • Python (2.7.14)
    • Java (OpenJDK 1.8.0)
    • C# (csc 2.8.2.62916 / Mono 5.16.0.220)
    • Ruby (2.3.1)
    • Haskell (GHC 7.10.3)
  • 対戦プログラムは複数スレッド・複数プロセスの使用を禁止します。
  • 相手の手番時のメッセージ待ち受け以外の処理は禁止とします。
  • 対戦プログラムは1プロセスで実行することを想定しており、制御プログラムで正しく実行時間が測定される対戦プログラムを前提とします。
  • 対戦プログラムのソースコードは1ファイルで提出してください。ただし、指定されたライブラリ、対戦時に実行しない対戦プログラムを作成する上で利用したコードなどについてはこれに含めません。
  • 実行ファイルのコンパイル・構築については、Makefileなどを利用して可能な限り1コマンドで構築できるようにしてください。
  • 指定以外の外部ライブラリ・モジュール、OSSなどのソースコードからの流用は認めません。ただし、実例で示した、ただしくん(tadashi.py)、あけみさん(akemi.cpp)の対戦プログラム、制御プログラム(prime_daihinmin.py)、および許可されたライブラリ等の利用は認めます。
  • 利用可能ライブラリC++
    • JSON for Modern C++ 3.7.3 (json.hpp)
      • https://github.com/nlohmann/json/releases
    • Boost 1.58
    • GMP 6.1.0
  • 利用可能ライブラリ Python
    • NumPy 1.16.4
  • 利用可能ライブラリ C#
    • Utf8Json
      • https://github.com/neuecc/Utf8Json
  • 使用可能メモリは1 GBとし、それ以上のメモリ使用は正しく実行されることを保証しません。
  • ソースコードサイズの制限は1MBとします。それ以上のサイズは正しく実行されることを保証しません。
  • 故意の難読化は禁止とします。
  • 外部へのネットワーク接続およびファイルアクセスを禁止します。
  • 提出したソースコードの内容を説明できる必要があります。
  • 上記の記載について変更される場合があります。その場合は告知します。

注意事項

  • コンテストの期間は、2019年12月25日(水) 18:00 ～ 2019年3月6日(金) 12:00とします。
  • コンテスト結果においては実名ではなくユーザIDで公表します。
  • コンテストの実行マシン環境は以下を予定しています。実行環境が変更される場合は参加者に告知します。
    • (AWS; コンテストサイト公開時に詳細を記載予定)
  • コンテストの参加は本人のみとし、複数人・グループでの参加はできません。
  • コンテスト期間中、コンテスト内容に関わる解法や実装をコンテスト管理者以外の第三者に知らせる行為を禁じます。
  • 不正が発覚した場合、その参加者は失格となります。

結果発表

2019年3月中旬に社内プログラミングコンテスト結果発表会および懇親会を行います。詳細が決まり次第報告します。また、結果発表会では作成したプログラムの簡単な説明をして頂く予定です (スライド1～数枚・5分程度)。

賞品

今回も様々な賞品を用意しています! 詳細についてはしばらくお待ちください。

実例: ただしくんとあけみさん

実例として、ただしくんのPythonコード、あけみさんのC++コードを示します。

実例1: ただしくんの場合 ( tadashi.py )

#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""tadashi's PrimeDaihinmin Solver (C) 2019 Fixstars Corp.
"""

import sys
import os
import random
import itertools
import json

VERSION  = "0.07"
REVISION = "a"
VER_DATE = "20191225"

TIME_LIMIT = 10.0
DEBUG_PRINT = False

def debug_print(msg):
    if DEBUG_PRINT:
        print(msg, file=sys.stderr)

# Miller-Rabin primality test
def is_prime(q, k=50):
   if q == 2: return True
   if q < 2 or q & 1 == 0: return False
   d = q - 1
   d //= d & -d
   for _ in range(k):
       a = random.randint(1, q - 1)
       t = d
       y = pow(a, t, q)
       while t != q - 1 and y != 1 and y != q - 1: 
           y = pow(y, 2, q)
           t <<= 1
       if y != q - 1 and t & 1 == 0:
           return False
   return True

def make_candidate(hand, length):
    h = hand[:]
    if length == 1:
        h = list(set(h) & {2, 3, 5, 7})
        return [random.choice(h)] if h else None
    hh = [x for x in h if x > 0]
    ht = [x for x in h if x in (1, 3, 7, 9)]
    if not ht:
        return None
    tail = random.choice(ht)
    hh.remove(tail)
    if not hh:
        return None
    head = random.choice(hh)
    h.remove(tail)
    h.remove(head)
    remain = length - 2
    m = random.sample(h, remain)
    return [head] + m + [tail]

def solver(hand, number, length):
    if len(hand) < length:
        return None
    for _ in range(10000):
        candidate = make_candidate(hand, length)
        if candidate:
            n = int("".join(map(str, candidate)))
            if n > number and is_prime(n):
                return candidate
    return None

def main(args):
    global TIME_LIMIT

    hand = []
    num_first_cards = 5

    while True:
        text = sys.stdin.readline().strip()
        data = json.loads(text)
        action = data["action"]
        if action == "play":
            name = data["name"]
            hand = data["hand"]
            numbers = list(map(int, data["numbers"]))
            record = data["record"]
            hands = data["hands"]
            debug_print("name: {}".format(name)) ###
            debug_print("hand: {}".format(hand)) ###
            debug_print("record: {}".format(record)) ###
            debug_print("hands: {}".format(hands)) ###
            length = len("".join(map(str, numbers)))
            if length == 0:
                if len(hand) <= num_first_cards:
                    length = len(hand)
                else:
                    length = random.randint(1, num_first_cards)
            cards = solver(hand, numbers[-1] if numbers else 0, length)
            if cards is not None:
                jsondata = json.dumps({"action": "number", "cards": cards})
            else:
                jsondata = json.dumps({"action": "pass"})
            sys.stdout.write("{}\n".format(jsondata))
            sys.stdout.flush()
        elif action == "pass":
            draw = data["draw"]
            hand.extend(draw)
            hand.sort()
            sys.stdout.write("\n")
            sys.stdout.flush()
        elif action == "init":
            uid = data["uid"]
            names = data["names"]
            name = names[uid]
            hand = data["hand"]
            TIME_LIMIT = data["time"]
            sys.stdout.write("\n")
            sys.stdout.flush()
        elif action == "quit":
            sys.stdout.flush()
            break

if __name__ == "__main__":
    main(sys.argv)

実例2: あけみさんの場合 ( akemi.cpp )

// akemi's PrimeDaihinmin Solver (C) 2019 Fixstars Corp.
// g++ akemi.cpp -std=c++17 -o akemi -O3 -Wall -Wno-unused-but-set-variable -lgmp

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <random>
#include <algorithm>
#include <utility>

#include <gmpxx.h>
#include "json.hpp"

constexpr const char* version  = "0.06";
constexpr const char* revision = "a";
constexpr const char* ver_date = "20191225";

static double TIME_LIMIT = 10.0;

void remove_newline(std::string& s)
{
    std::string target("\n");
    std::string::size_type pos = s.find(target);
    while (pos != std::string::npos) {
        s.replace(pos, target.size(), "");
        pos = s.find(target, pos);
    }
}

// Miller-Rabin primality test
int is_prime(const mpz_t q, int k=50)
{
    return mpz_probab_prime_p(q, k);
}

void string2digits(const std::string& s, std::vector<int>& v)
{
    for (const char c : s) {
        int n = c - '0';
        if (n < 0 || n > 9) continue;
        v.push_back(n);
    }
}

std::string make_candidate(std::vector<int> hand, int length)
{
    std::random_device seed_gen;
    std::default_random_engine engine(seed_gen());
    std::stringstream ss("");

    if (length == 1) {
        std::vector<int> h(hand);
        h.erase(std::unique(h.begin(), h.end()), h.end());
        auto p = std::remove(h.begin(),h.end(), 0);
        p = std::remove(h.begin(), p, 1);
        p = std::remove(h.begin(), p, 4);
        p = std::remove(h.begin(), p, 6);
        p = std::remove(h.begin(), p, 8);
        p = std::remove(h.begin(), p, 9);
        h.erase(p, h.end());
        if (h.empty()) {
            return "";
        } else {
            std::uniform_int_distribution<> randint(0, h.size() - 1);
            int n = h[randint(engine)];
            ss << n;
            return ss.str();
        }
    }

    std::vector<int> hh;
    std::vector<int> ht;
    std::copy_if(hand.begin(), hand.end(), std::back_inserter(hh), [](int n){ return n > 0; });
    std::copy_if(hand.begin(), hand.end(), std::back_inserter(ht), [](int n){ return (n & 1) == 1 && n != 5; });
    if (ht.empty()) return "";
    std::uniform_int_distribution<> randht(0, ht.size() - 1);
    int tail = ht[randht(engine)];
    hh.erase(std::find(hh.begin(), hh.end(), tail));
    if (hh.empty()) return "";
    std::uniform_int_distribution<> randhh(0, hh.size() - 1);
    int head = hh[randhh(engine)];
    hand.erase(std::find(hand.begin(), hand.end(), tail));
    hand.erase(std::find(hand.begin(), hand.end(), head));
    std::shuffle(hand.begin(), hand.end(), engine);
    ss << head;
    for (int i = 0; i < length - 2; i++) {
        ss << hand[i];
    }
    ss << tail;
    return ss.str();
}

std::string make_Mersenne(std::vector<int> hand, int length)
{
    std::vector<int> u;

    switch (length) {
    case 1:
        if (std::find(hand.begin(), hand.end(), 3) != hand.end()) return "3";
        if (std::find(hand.begin(), hand.end(), 7) != hand.end()) return "7";
        break;
    case 2:
        u = {1, 3};
        if (std::includes(hand.begin(), hand.end(), u.begin(), u.end())) return "31";
        break;
    case 3:
        u = {1, 2, 7};
        if (std::includes(hand.begin(), hand.end(), u.begin(), u.end())) return "127";
        break;
    case 4:
        u = {1, 8, 9};
        if (std::includes(hand.begin(), hand.end(), u.begin(), u.end())
            && std::count(hand.begin(), hand.end(), 1) >= 2) return "8191";
        break;
    case 6:
        u = {2, 4, 5, 7, 8};
        if (std::includes(hand.begin(), hand.end(), u.begin(), u.end())
            && std::count(hand.begin(), hand.end(), 2) >= 2) return "524287";
        u = {0, 1, 3, 7};
        if (std::includes(hand.begin(), hand.end(), u.begin(), u.end())
            && std::count(hand.begin(), hand.end(), 1) >= 3) return "131071";
        break;
    case 10:
        u = {1, 2, 3, 4, 6, 7, 8};
        if (std::includes(hand.begin(), hand.end(), u.begin(), u.end())
            && std::count(hand.begin(), hand.end(), 4) >= 3 
            && std::count(hand.begin(), hand.end(), 7) >= 2) return "2147483647";
        break;
    }

    return "";
}

std::vector<int> solver(std::vector<int> hand, const mpz_class& number, int length)
{
      std::random_device seed_gen;
      std::default_random_engine engine(seed_gen());
    std::vector<int> cards;
    std::vector<int> ret({});

    if (static_cast<int>(hand.size()) < length) return cards;

    // check Belphegor prime
    int cnt_0 = std::count(hand.begin(), hand.end(), 0);
    int cnt_1 = std::count(hand.begin(), hand.end(), 1);
    int cnt_6 = std::count(hand.begin(), hand.end(), 6);
    if (cnt_0 >=26 && cnt_1 >= 2 && cnt_6 >= 3) {
        ret = {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 6, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1};
        return ret;
    }

    // check Mersenne prime
    std::string mersenne = make_Mersenne(hand, length);
    if (!mersenne.empty()) {
        mpz_class m;
        m.set_str(mersenne, 10);
        if (m > number) {
            string2digits(mersenne, ret);
            return ret;
        }
    }

    mpz_class candidate;
    for (int i = 0; i < 10000; i++) {
        std::string s = make_candidate(hand, length);
        if (!s.empty()) {
            candidate.set_str(s, 10);
            if (candidate > number && is_prime(candidate.get_mpz_t())) {
                string2digits(s, ret);
                return ret;
            }
        }
    }

    return ret;
}

int main(int argc, char* argv[])
{
    std::string s;
    const int num_first_cards = 5;
      std::random_device seed_gen;
      std::default_random_engine engine(seed_gen());

    for (;;) {
        getline(std::cin, s);
        nlohmann::json obj = nlohmann::json::parse(s);
        auto action = obj["action"];

        if (action == "play") {
            auto name(obj["name"]);
            auto hand_(obj["hand"]);
            auto numbers_(obj["numbers"]);
            auto record(obj["record"]);
            auto hands(obj["hands"]);

            std::vector<int> hand;
            for (const auto card : hand_) {
                hand.push_back(card);
            }

            std::vector<mpz_class> numbers;
            std::string number_str("");
            mpz_class n;
            for (const auto number : numbers_) {
                number_str += number;
                n.set_str(number, 10);
                numbers.push_back(n);
            }

            int length = number_str.length();
            if (length == 0) {
                if (hand.size() <= num_first_cards) {
                    length = hand.size();
                } else {
                    std::uniform_int_distribution<> dist(1, num_first_cards);
                    length = dist(engine);
                }
            }

            const mpz_class ZERO("0");
            auto cards = solver(hand, numbers.empty() ? ZERO : numbers.back(), length);

            nlohmann::json out;
            if (!cards.empty()) {
                out["action"] = "number";
                out["cards"] = cards;
            } else {
                out["action"] = "pass";
            }
            std::string json(out.dump());
            remove_newline(json);
            std::cout << json << std::endl << std::flush;

        } else if (action == "pass") {
            auto draw(obj["draw"]);
            std::cout << std::endl << std::flush;

        } else if (action == "init") {
            int uid(obj["uid"]);
            auto names(obj["names"]);
            auto name(names[uid]);
            auto hand(obj["hand"]);
            TIME_LIMIT = obj["time"];
            std::cout << std::endl << std::flush;

        } else if (action == "quit") {
            std::cout << std::endl << std::flush;
            break;
        }
    }

    return 0;
}

About Author

nox

Leave a Comment

メールアドレスが公開されることはありません。 ※ が付いている欄は必須項目です

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Recent Comments

Social Media