DevFest 2010 Japan(以下DevFest)に参加したく事前Quizが出題されたため回答してみた。
(※回答は2010/2/25に締め切られております)
DevFestは3/11に開催されるGoogle主催のイベント。
参加者が多くなると全員を会場に入れなくなるという理由から参加者を絞るためにQuizを行って高得点者から400人が参加できるというものです。
QuizはいかにもGoogleのサービス・プロダクトを使ってくださいといっているようなものばかりで
全10問中プログラミングする問題が3問ありました。
最初に取り掛かったのが暗号化の問題。
登録したメールアドレスを問題文にしたがって暗号化してjson形式でサーバにpostせよという問題。
暗号化はすぐにできたが、postの方法がわからなかった。
普通にサーブレットでform作ってpostしてみたものの不正解。
形式が悪いのかといろいろformでできないか試行錯誤したけれどうまくいかず。
なので、後回し。
次にパッチワークの問題。
600×600のテキスト(AまたはBのみで構成されている)を入力する。
AまたはBで縦横で繋がっているものの中で一番繋がっている数が多いところを”_”に置換し
各行で”_”の数を答えるという問題。
これは意外と簡単だった。
実は7年ぐらい前に某落ちゲーのぷよぷよをパクったようなのを作ったことがあるんだけど、
同じ色が繋がっている判定とその数が4つ以上だったら消えるという部分で
今回の問題で同じアルゴリズムが使えるということで、早速組んでみた。
当時はCで書いていたけど、今回は時間もないということでJavaで書くことに。
Javaのほうが文字列処理など楽なので。
これは一発で正解。
次に漢字変換サーバの問題
これはWebサーバにGetメソッドでn=<数字>というリクエストに対して数字部分を漢数字に直し、それを問題文にあるアルファベットに変換してtext/plainで返すというもの。
幸いWebサーバを構築していたのでGoogleAppEngineを使わずにPHPで書きました。
数字部は高々9999兆9999億9999万9999までの数字なのでゴリゴリ再利用性のないコードを書きましたｗ
こんなコード見せられません。仕事でこんなことしてたら怒られますｗ
0の扱いだとか1の扱い(1000万は「千万」とする)でちょっとだけ考えただけで、そんなに難しくありませんでした。
んで、最初にやろうとしていた暗号化の問題。
結局サーブレットを使わずにJavaから直接サーバにpostするということで正解することができました。
しかし、問題文のjsonの書き方が悪く、ペアとペアの間の”,”がいるとは思いませんでした。
とりあえず、他の問題も答えられるものだけ答えておきました。
回答状況はこんな感じです。
最後にパッチワークのコードを晒してみる。
メソッド名とか変数名とか酷いですけどｗ
しかもパッチワークの綴りが間違っているという。orz 正しくはpatchworkですね。
package com.toro.java.pachwork;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
public class PachworkJava {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
PachworkJava a = new PachworkJava();
a.execMain();
}
private void execMain(){
readFile();
int[] execNum = getResult();
writeFile(execNum);
}
char[][] inputChars = new char[600][600];
private void readFile(){
try{
BufferedReader br = new BufferedReader(
new FileReader("C:\\work\\patchworkinput.txt"));
String s;
for(int i = 0; i < 600; i++){
s = br.readLine();
if(s == null){
break;
}
for(int j = 0; j < 600; j++){
inputChars[i][j] = s.charAt(j);
}
}
br.close();
}catch(Exception e){
}
}
private void writeFile(int[] execNum){
try{
BufferedWriter bw = new BufferedWriter(
new FileWriter("C:\\work\\patchworkoutput.txt"));
String s;
for(int i = 0; i < 600; i++){
s = String.valueOf(execNum[i]);
bw.write(s);
bw.newLine();
}
bw.close();
}catch(Exception e){
}
}
int[][] sameAB = new int[600][600]; // 繋がっているところは同じ数字になる
int[][] flagT = new int[600][600]; // 既に探索済みかどうか
int maxNum = 0; // 繋がっている数
private int[] getResult(){
// 初期化
for(int i = 0; i < 600; i++){
for(int j = 0; j < 600; j++){
sameAB[i][j] = 0;
flagT[i][j] = 0;
}
}
maxNum = 0;
// 同じものを探し
searchAB();
// 一番繋がった部分を探す
int[] numNum = new int[maxNum];
for(int i = 0; i < maxNum; i++){
numNum[i] = 0;
}
for(int i = 0; i < 600; i++){
for(int j = 0; j < 600; j++){
numNum[sameAB[i][j]-1]++;
}
}
int maxNumNum = 0; // 一番繋がっている数
for(int i = 0; i < maxNum; i++){
if(numNum[i] > maxNumNum){
maxNumNum = numNum[i];
}
}
// 一番繋がっている数の部分を置換する
for(int k = 0; k < maxNum; k++){
if(numNum[k] == maxNumNum){
// 置換対象の数である
// その部分を見つけて置換する
for(int i = 0; i < 600; i++){
for(int j = 0; j < 600; j++){
if(sameAB[i][j] == k+1){
inputChars[i][j] = '_';
}
}
}
}
}
int[] retInt = new int[600];
for(int i = 0; i < 600; i++){
retInt[i] = 0;
for(int j = 0; j < 600; j++){
if(inputChars[i][j] == '_'){
retInt[i]++;
}
}
}
return retInt;
}
private void searchAB(){
int num = 0;
for(int i = 0; i < 600; i++){
for(int j = 0; j < 600; j++){
// 調査済みなら次へ
if(flagT[i][j] == 1){
continue;
}
num++;
flagT[i][j] = 1;
sameAB[i][j] = num;
// 自分自身と同じところを探す
researchAB(num, i, j);
}
}
maxNum = num;
}
private void researchAB(int num, int i, int j){
char t = inputChars[i][j];
// 上を探す
if(i > 0){
if(flagT[i-1][j] == 0){
if(inputChars[i-1][j] == t){
flagT[i-1][j] = 1;
sameAB[i-1][j] = num;
researchAB(num, i-1, j);
}
}
}
// 左を探す
if(j > 0){
if(flagT[i][j-1] == 0){
if(inputChars[i][j-1] == t){
flagT[i][j-1] = 1;
sameAB[i][j-1] = num;
researchAB(num, i, j-1);
}
}
}
// 右を探す
if(j < 599){
if(flagT[i][j+1] == 0){
if(inputChars[i][j+1] == t){
flagT[i][j+1] = 1;
sameAB[i][j+1] = num;
researchAB(num, i, j+1);
}
}
}
// 下を探す
if(i < 599){
if(flagT[i+1][j] == 0){
if(inputChars[i+1][j] == t){
flagT[i+1][j] = 1;
sameAB[i+1][j] = num;
researchAB(num, i+1, j);
}
}
}
}
}
RSSを取得する