読者です 読者をやめる 読者になる 読者になる

オフラインリアルタイムどう書くE03参加しました

はじめに

2016/4/2開催の「オフラインリアルタイムどう書くE03」に参加しましたので、そのレポートです。

どんな感じ?

年度初めでもあり?? キャンセルも出てやや人数は少なめでした…。

しかしながら、花見に勤しむ世間の人々をよそ目に問題を解くのでした。まあ、問題の図がちょうどお花のような形でこれが我々の花見なのです! ( 眉唾 )

問題としては、前回・前々回よりやや易しめでしょうか。何とか時間内に ( 初めて!! ) 解くことができました。

今回は自己紹介、「最近聞く音楽」私音楽聞いてるのなんだろう…と思ったら、実は下の子と一緒に見ている特撮ものしか思い浮かばなかったという。( 他に“Sofia the First”もあったか )

問題

問題は鍋谷さんのサイトにあります。

内容は…サイトをそのままご覧ください。

解説

方針

まず、ですが、問題に出てくる六角形 ( 以下ヘクス ) は1a~4tまでの計80個あります。これを連番で管理します。次の図の通り、1で始まるヘクスは40~59…といったように、です。なぜ40からなんだ??というところ、あからさまに怪しいですが、その理由はまた後程。

f:id:ange1:20160403174926p:plain

さて。入力により指定されたヘクス ( もしくは00の多角形 ) の中で、「どの頂点がイキるか」を考える訳ですが。問題にある「内角が180°より小さい」は、実は隣接のヘクスが入力にあるかどうかに置き換えることができます。

f:id:ange1:20160403175622p:plain

この図のように、ヘクスのある頂点、後もう2つの隣接ヘクスと共有されているところ、隣接ヘクスが入力になければ「イキ」そうでなければ除外、ということになります。
ということは、入力にあるヘクスの隣接ヘクスの状況を調べ、各頂点がイキになるかどうかを決定する、ということでヘクス×頂点のループで処理できそうです。
なお、隣接ヘクスの番号については次の図のように整理できます。

f:id:ange1:20160403180154p:plain

図中p,nに関しては、mod 20 で考えた時の 0 をまたぐかどうかで、必ずしも連番にはなってませんが、内側・外側の隣接ヘクスに関しては単純に±20で番号が分かります。

…さて。ここまで触れてこなかったのが、00 の多角形。ヘクスでないので例外的に扱わなければなりません。面倒です。ここをどうするか…が1つの焦点だったのですが、次のように考えました。
「実は、00 って 20個のヘクスの集合体と見做せるんじゃないの」と。

どういうことかというと、00 の頂点でイキになる可能性があるのはトゲ状の20か所だけですから、20個のヘクスをつなぎ合せて隣接ヘクスのある頂点を全て除外したのと状況は変わらないのですね。図にすると次の通り。

f:id:ange1:20160403180819p:plain

00 の多角形は、20~39番の集合体とみなし、また扱いを共通化するため、裾領域として 0~19・120~139のヘクスを追加します。20~39の内側の頂点を殺すため0~19は無条件で入力あり、逆に120~139は入力なしという扱いにします。…最初に1a~を40~にマップしたのは、実はこれがあったためでした。

実装

ということで、会場ではPerlで実装しました。デバッグプリントを取り除いたのが以下の実装です。前回よりも空白が増えてます!! ( 当社比150% ) …いやまあ、今回も「(コードが見辛いから)空白入れようよ」という有り難いコメントを頂いておりまして。

上の方針で説明した通りです。入力にあるヘクスは、配列@mの当該要素の1/0で管理します。0~19は無条件で1、20~39は00の入力があれば全部1といった具合です。( ハッシュで管理しても良いような気がしますが特に直してません )

袖領域を除いた、20~119 ( 20~39は00に対応 ) のヘクスの中で入力ありのものに対し、grepでイキになる頂点を数えて合計していく…という実装です。

おまけ

その1

図をつくるの、出題者の鍋谷さんがRubyhamlSVGを作る…とおっしゃっていたのが良く分からなかったのですが。まあ座標計算すればエエんじゃろ的なノリでPerlで組んでみました。

その2

図がな~んかに似てるなあ…、と思ったら、これでした。

実際、ひまわりの花から種ができたところ見てみると、今回の問題の図にそっくりだったりします。

終わりに

皆さまお疲れ様でした。5月はゴールデンウィークで色々あるでしょう、ということで次は6月になるとのことです。
終了後の飲み会では買ってきたオセロを碁盤・碁石として流用してやんちゃさんと9路盤対決をしたり…。短い時間でできるので19路盤よりやり易くて面白いですね。その後はしえるさんとゲーセンでチュウニズム。World Endというメチャクチャ難しいモード始めてみました。ここらへんも参加者が増えると楽しいですね。