Googleが3月にDevFestと呼ばれるイベントを行うそうです。
これの参加申し込み方法が面白く、参加希望者はQuizに答える必要がありました。
Quizといっても色々な問題があり、内いくつかは立派なプログラミングの問題でした。
最近、自分の回答を晒すのが流行っているようなので私の回答も晒しておきます。
暗号通信
あなたの登録したメールアドレスを、このクイズサーバーに転送して下さい。 ただし、次のような暗号化をしてください。
A → G
B → H
C → I
D → J
E → K
中略 → 中略
Z → F
a → g
b → h
c → i
中略 → 中略
z → f
@ → @
1 → 1
変換したメールアドレスと、次のキーワード : "6482agdkZXZxdWl6chsLEhRQYXJ0aWNpcGFudFNvbHV0aW9ucxidaQw" とを一緒に、http://***.***/*** までpostしてください。 二つのデータは以下のようにjson形式にして、POSTの本文に text/plain 形式で入れてください。{
"key": キーワード
"pass": 変換されたメールアドレス
}
この問題は非常に有名なシーザー暗号の問題ですね。
MacやUnixを使っている人ならtrというコマンドで一発で変換できます。
echo your@email.com | tr A-Za-z G-ZA-Fg-za-f
後はこの結果をエディタに突っ込んでJSONを作ります。問題文にはkeyとpassの間に区切り記号のカンマが有りませんがもちろんいります。
それに気付かずに何度も不正解をもらいました。＞＜
POSTにはcurlやwgetといったコマンドを用いると簡単にできます。
以下にJSONをanswerというファイルに入れている場合に、結果をresultに保存する例を示します。
curl -X POST -d@answer http://---.----.com/post > result
結果はHTMLが帰ってきますのでブラウザで開くなりして見てください。
パッチワーク
ここに "A" または "B" という文字のみを含む 600 桁、600 行のテキストがあります。 これを 600 x 600 の升目状に並べ、上下左右に同じ文字がある部分をつながっているとみなします。
まず、最も多くの文字がつながっている領域をすべて "_" で塗りつぶしてください。 最も多くの文字がつながっている領域が複数存在するならば、それらすべての領域を "_"で塗りつぶすこととします。
そして、各行ごとに "_" が何個含まれているかを数え、それらの数値を改行区切りのテキスト（600 行）として答えてください。
問題のファイルはこれです。
http://devquiz.appspot.com/patchworkinput
Aという文字とBという文字にて迷路のような正方形の絵が提供されます。
この迷路の中で一番面積の広い領域に属する文字の各行における個数を提示すれば良い訳です。
実際の回答方法は問題画面から直接POSTするものでしたのでとりあえず結果を表示するプログラムを作り、その結果を画面にて入力してポストしました。
この問題の回答には最初C言語でプログラムを作成し始めました。
文字列を解析するならCのポインタでやるのが一番慣れているからです。
しかしプログラムを始めてから問題が自分が思っているよりもずっと難しいことに気がつきました。
C言語には標準ライブラリにJavaのCollectionsのような素敵なものがありません。
そのため後からJavaで書き直すというおバカなことをしてしまいました。＞＜
プログラムの戦略ですが、いくらかあると思います。
一つは絵を迷路に見たてて解く方法です。この方法はスタート地点を変えながら迷路の中を歩いて歩数を数えます。解き方としては面白いのですが、この方法ですと問題をどこまで解いたのかがわかりにくいのが欠点です。
私は別の方法として、問題を二回に分けて解く方法を選びました。
一回目はファイルを素直に全行読み、一行毎に文字の広さを測り、その開始位置と終了位置を保存します。
行の中での対象文字の領域を島(Island)と呼ぶことにしました。
一回目のスキャンで各行の島を各行別に発見し、保存します。
二回目はn行目とn+1行目を比較して島が重なっていたら、それを同じ領域(Area)として接続します。この時、両方の島の広さをスコアとして合計します。
まず最初の1行だけ特別に全ての島をそれぞれ新しい領域に登録します。全ての島に対し次の行の島と位置が重なるか調べ、その場合、自分の領域にその島を加えます。
ある行の離れた複数の島が次の行の同じ島に接続される場合もあります。次の行の島が既にある領域に属しているのか判断し、その場合には両方の領域を合成する必要があります。
一番難しいケースとして、以下の状態が発生しました。
AAAAAABBBBBBBBBBAAAAAAAAAAA BBBBBBBAAAAAAAABBBBBBBBBBBB AAAAAABBBBBBBBBBAAAAAAAAAAA
二行目を処理する時、1行目の処理にて上二行のBは全て同じ領域に属します。二行目の繰り返しにおいて、二行目の一つ目の島と3行目の島を同じ領域に接続すると、既に二行目の二つ目の島と3行目の島とは同じ領域に接続済みの状態になります。この場合に同じ領域に接続していることのチェックを忘れてCollectionが例外を発生するというバグに悩みました。＞＜
後は全ての行にて繰り返す間に、領域を更新する度に最大領域を記憶しておけばOKです。
これで検索対象をAとBで二回繰り返し、それぞれの文字で最大領域を求めてそのスコアを比較し、最大のものを報告します。
ただし最大の領域が複数ある場合にはそれらを全て報告です。
反省としてはAとBとを別にスキャンしましたが、この問題固定で汎用性がいらなければ一回のスキャンでAとBの両方の島を同時に検出できます。
また最後の各行のスコアを求める段階では面倒なので新しい領域を確保してしまいましたが、領域に属する島のListを行順にソートすれば新しい領域はいらなかったことです。
ですが、時間制限があったので作り直すのをためらいました。＞＜
以下、ソースです。パッケージ無しですのでEclipseでプロジェクトのsrcの直下に放り込みます。ファイルはプロジェクトの直下に放り込んでください。
Island.java
public class Island { public Island(int si, int ei, int ln) { start = si; end = ei; lineNumber = ln; } private int start; private int end; private int lineNumber; private Area area; public int getStart() { return start; } public void setStart(int start) { this.start = start; } public int getEnd() { return end; } public void setEnd(int end) { this.end = end; } public int getLineNumber() { return lineNumber; } public void setLineNumber(int line) { this.lineNumber = line; } public Area getArea() { return area; } public void setArea(Area area) { this.area = area; } public int length() { return end - start + 1; } public boolean intersect(Island j) { return (this.end < j.getStart() || this.start > j.getEnd()) ? false : true; } public String toString() { return "(" + start + "," + end + "," + lineNumber + ")"; } }
Area.java
import java.util.ArrayList; import java.util.HashMap; public class Area implements Comparable<Area> { public HashMap<Integer, ArrayList<Island>> islandsArray = new HashMap<Integer, ArrayList<Island>>(); int score = 0; public Area(Island i) { int lineNumber = i.getLineNumber(); ArrayList<Island> islands = new ArrayList<Island>(); islands.add(i); islandsArray.put(lineNumber, islands); i.setArea(this); score = i.length(); } public void append(Island i) { int lineNumber = i.getLineNumber(); ArrayList<Island> p = islandsArray.get(lineNumber); if (p == null) { p = new ArrayList<Island>(); } p.add(i); islandsArray.put(lineNumber, p); i.setArea(this); score += i.length(); } public void concat(Area ka) { for (ArrayList<Island> a : ka.islandsArray.values()) { for (Island i : a){ this.append(i); } } } public String toString() { String result = ""; for (ArrayList<Island> a : islandsArray.values()) { // System.out.print("!"); for (Island i : a) result = result.concat(i + ","); } result = result.concat("\nscore = " + score); return result; } public int compareTo(Area o) { return o.score - this.score; } public void paint(int[] map, int width) { for (ArrayList<Island> a : islandsArray.values()) { for (Island i : a) { int y = i.getLineNumber(); for (int x = i.getStart(); x <= i.getEnd(); x++) { map[x + y * width] = 1; } } } } }
Patchwork.java
import java.io.BufferedReader; import java.io.FileReader; import java.util.ArrayList; import java.util.Collections; public class Patchwork { private static int mLength; /** * @param args */ public static void main(String[] args) { ArrayList<Area> areaA = createMaxAreaBy('A'); ArrayList<Area> areaB = createMaxAreaBy('B'); areaA.addAll(areaB); Collections.sort(areaA); Area toparea = areaA.get(0); for (int i = 1; i < areaA.size(); i++) { Area tmp = areaA.get(i); if (toparea.score != tmp.score) break; toparea.concat(tmp); } int[] map = new int[mLength * mLength]; toparea.paint(map, mLength); for (int y = 0; y < mLength; y++) { int sum = 0; for (int x = 0; x < mLength; x++) { sum += map[x + y * mLength]; } System.out.printf("%d\n", sum); } } private static ArrayList<Area> createMaxAreaBy(char tgtc) { BufferedReader br; try { br = new BufferedReader(new FileReader("patchworkinput.txt")); String firstline = br.readLine(); mLength = firstline.length(); String[] map = new String[mLength]; ArrayList<ArrayList<Island>> islandsArray = new ArrayList<ArrayList<Island>>(); islandsArray.add(createIslandsInLIne(firstline, 0, tgtc)); map[0] = firstline; int count = 1; for (String str = br.readLine(); str != null; str = br.readLine()) { map[count] = str; //System.out.println("count = " + count); islandsArray.add(createIslandsInLIne(str, count, tgtc)); count++; } if (count != mLength) { System.err.printf("Invalid line nubmers. There must be %d lines, but %d lines.", mLength, count); } ArrayList<Area> areaList; // Make areas for 1st line. every single island is an area ArrayList<Island> prev = islandsArray.get(0); areaList = createAreasFromFirstLine(prev); // For each of the rest of islands, make an area or append it to existing area for (int i = 1; i < count; i++) { ArrayList<Island> curr = islandsArray.get(i); for (Island j : curr) { for (Island k : prev) { //System.out.println("Handle " + j + " and " + k + "\n"); if (k.intersect(j)) { Area ja = j.getArea(); Area ka = k.getArea(); if (ja == null) { ka.append(j); //System.out.println(k + " appends " + j + "\n"); } else { if (ja == ka) continue; //System.out.println("ja = " + ja); //System.out.println("ka = " + ka); ka.concat(ja); areaList.remove(ja); } } } if (j.getArea() == null) { areaList.add(new Area(j)); //System.out.println("Make " + j + "\n"); } } prev = curr; } Collections.sort(areaList); System.out.println("------------------------------------------------------------------------------------"); System.out.println("areaList.length = " + areaList.size()); for (Area a : areaList) { System.out.println(a.toString()); } return areaList; } catch (Exception e) { e.printStackTrace(); return null; } } private static ArrayList<Area> createAreasFromFirstLine(ArrayList<Island> islands) { ArrayList<Area> result = new ArrayList<Area>(); for (Island i : islands) { result.add(new Area(i)); } return result; } private static ArrayList<Island> createIslandsInLIne(String line, int ln, char t) { ArrayList<Island> result = new ArrayList<Island>(); int len = line.length(); int si = 0; // start index int ei = 0; // end index boolean isIn = false; for (int i = 0; i < len; i++) { char c = line.charAt(i); if (isIn) { if (c == t) { } else { isIn = false; ei = i - 1; result.add(new Island(si, ei, ln)); } } else { if (c == t) { isIn = true; si = i; } } } if (isIn) { result.add(new Island(si, len - 1, ln)); } //for (Island i : result) System.out.println(i); return result; } }
それにしてもプログラムが長い。getterやsetterを除いても他の人に比べてかなり長いですね＞＜
漢字変換マシン
数字を漢数字に変換するアプリケーションを作ってください。 http://[あなたのアプリケーションのURL]?n=[数字] にアクセスすると、 text/plain でその数字を漢数字に変換した結果を返すウェブサーバを作ってください。 ただし、漢字はすべて以下の表の通りにアルファベットに変換して出力してください。 零 → N 一 → X 二 → C 三 → U 四 → Y 五 → A 六 → S 七 → Q 八 → T 九 → G 十 → P 百 → B 千 → M 万 → J 億 → H 兆 → Z 注意: 「千万」「千億」「千兆」の前に「一」がつかないようにしてください。 入力は負でない整数で、大きさは高々9999兆9999億9999万9999までです。 標準のポート番号80番のみ扱えます。
この問題は自分でサーバーを用意しないといけません。少し昔ならありえない問題です。
でも質問の回答にてGAEの使用を勧められていたのでやっぱりGAEを使ってくださいという問題だと判断しました。
GAEではPythonを使ってみました。ついでに何か新しいことをしたかったからです。
問題が9999兆まで扱わなければいけないので当然intでは範囲に収まりません。
そこで文字列のまま処理することにしました。
処理の戦略は下からです。文字列のままですと数の大きさがわかりませんので下位の桁から挑戦します。
そこで気付いたのが漢数字に直しても4桁毎に処理は同じということです。
そこで4桁毎の処理は関数にしました。
不正解になっても何故不正解になったのかが表示されない厳しい問題でした。非常にストレスな問題です。
恐らく最後まではまっていたのは、途中の4桁が全部0の時は万や億の文字は付かないことです。＞＜
Pythonは全くのド素人なので詳しい方にこうしたほうがいいよと教えて頂けたらうれしいです。
from google.appengine.ext import webapp from google.appengine.ext.webapp.util import run_wsgi_app class MainPage(webapp.RequestHandler): def handle4(self, s): numc = ['N', 'X', 'C', 'U', 'Y', 'A', 'S', 'Q', 'T', 'G'] keta = ['M', 'B', 'P', ''] result = '' l = len(s) for i in range(l, 0, -1): ci = int(s[0:1]) if ci != 0: ki = 4 - i if ci != 1 or ki == 3: result += numc[ci] result += keta[ki] s = s[1:l] l -= 1 return result def get(self): n = self.request.get('n') l = len(n) r = self.response r.headers['Content-Type'] = 'text/plain' if l > 16: r.out.write('Too big number : ' + n) return if not n.isdigit(): r.out.write('Invalid number format : ' + n) return if int(n) == 0: r.out.write('N'); return; if n[0:1] == '0': r.out.write('Do not start with 0') return keta = ['', 'J', 'H', 'Z']; count = 0; result = '' while (l > 0): four = n[0:l] if (l < 4) else n[l-4:l] n = n[0:l-4] l -= 4 if int(four) != 0: result = keta[count] + result result = self.handle4(four) + result count += 1 r.out.write(result) application = webapp.WSGIApplication([('/', MainPage)], debug=True) def main(): run_wsgi_app(application) if __name__ == "__main__": main()
長すぎ………
皆さんもぜひ自分の回答を晒してください。
では。
