DevQuizを解いた。

今更ながらDevQuizに挑戦しました。
GDD2010でまたDevQuizがあるらしいので、予習ということです！

暗号問題

この問題は簡単なので、いかに変態的に解けるか、をアピールするところですね。
私はこんな風に解きました。

SQL> SELECT
 2  TRANSLATE(
 3  'tomorrowkey@gmail.com' ,
 4  'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz' ,
 5  'LMNOPQRSTUVWXYZABCDEFGHIJKlmnopqrstuvwxyzabcdefghijk') ANSWER
 6  FROM DUAL;

ANSWER
------------------------------------------
ezxzcczhvpj@rxltw.nzx

SQL>

ばっちりですね！
わたしの知るかぎりではSQLPLUSで解いた人はいないです！

パッチワーク

すこし難しいでした。
まじめに解きました。
合っているかどうか検証に使ったコードはこちらです

DevQuiz パッチワーク: Union-findアルゴリズム版 - Google ドキュメント
http://docs.google.com/Doc?docid=0ARnGrr_FSH1HZG1jcW1rZF82M2Q1NmQyNGRq&hl=ja

どっちがはやいか計測してみたら、私のコードが1346msで、UnionFindが156msでした！
完敗ですね…(;-;)

Pixel.java

public class Pixel {
  /* 処理を管理するバージョン */
  private int version = 0;

  /* 自分の島の広さを持つ重み */
  private int weight = 0;

  /* 値 */
  private char value;

  /**
   * コンストラクタ 値を設定する
   */
  public Pixel(char value) {
    this.value = value;
  }

  /**
   * バージョンを設定する
   */
  public void setVersion(int version) {
    this.version = version;
  }

  /**
   * バージョンを返す
   */
  public int getVersion() {
    return version;
  }

  /**
   * 重みを増やす
   */
  public void incrementWeight() {
    weight++;
  }

  /**
   * 重みを返す
   */
  public int getWeight() {
    return weight;
  }

  /**
   * 値を返す
   */
  public char getValue() {
    return value;
  }
}

PatchWork.java

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintStream;

public class PatchWork {

  /* 全体の幅 */
  private int width;

  /* 全体の高さ */
  private int height;

  /* ピクセルを保持する */
  private Pixel[][] pixels;

  /* 一番大きい重みを保持する */
  private int maxWeight = -1;

  /**
   * コンストラクタ 指定された幅、高さで配列を初期化する
   */
  public PatchWork(int width, int height) {
    this.width = width;
    this.height = height;
    pixels = new Pixel[width][height];
  }

  /**
   * 指定されたファイルからデータを読み込む 一番大きい島を見つけるために、各ピクセルに重みづけをする
   */
  public void search(String filePath) throws FileNotFoundException, IOException {
    // ファイルからデータを読み込んで、ピクセルオブジェクトにパースする
    BufferedReader br = new BufferedReader(new FileReader(filePath));
    String line;
    char[] chars;
    int x = 0;
    int y = 0;
    while ((line = br.readLine()) != null) {

      // 空行は無視する
      if (line.length() == 0) {
        continue;
      }

      // ピクセルの配列にパースする
      chars = line.toCharArray();
      for (x = 0; x < chars.length; x++) {
        pixels[x][y] = new Pixel(chars[x]);
      }

      // 次の行へ
      y++;
    }
    br.close();

    // 各ピクセルに対して重み付けをする
    int version = 0;
    int weight;
    for (y = 0; y < height; y++) {
      for (x = 0; x < width; x++) {
        // バージョンをあげる
        version++;

        // 重みを増やす
        addWeight(x, y, pixels[x][y].getValue(), version);

        // 一番大きい重みを更新する
        weight = pixels[x][y].getWeight();
        if (weight > maxWeight) {
          maxWeight = weight;
        }
      }
    }
  }

  /**
   * 自分のピクセルの重みをインクリメントする 周囲のピクセルの重みを加算するよう再帰的に呼び出す 呼び出し元と値が違う場合、加算しない
   * バージョンが古い・同じ場合すでに処理したピクセルなので、加算しない
   */
  private void addWeight(int x, int y, char value, int version) {

    // 自分のピクセルを取得
    Pixel currentPixel = pixels[x][y];

    // バージョンが高い場合は増やさない
    if (currentPixel.getVersion() >= version) {
      return;
    }

    // 値が異なる場合は増やさない
    if (currentPixel.getValue() != value) {
      return;
    }

    // 新しいバージョンを設定する
    currentPixel.setVersion(version);

    // 重みを増やす
    currentPixel.incrementWeight();

    // 周囲のピクセルを増やす
    if (y - 1 >= 0) {
      // 上
      addWeight(x, y - 1, value, version);
    }
    if (x + 1 < width) {
      // 右
      addWeight(x + 1, y, value, version);
    }
    if (y + 1 < height) {
      // 下
      addWeight(x, y + 1, value, version);
    }
    if (x - 1 >= 0) {
      // 左
      addWeight(x - 1, y, value, version);
    }
  }

  /**
   * パッチワークの答えを出力する
   */
  public void printAnswer(PrintStream out) {
    int count;
    for (int y = 0; y < height; y++) {
      count = 0;
      for (int x = 0; x < width; x++) {
        if (pixels[x][y].getWeight() == maxWeight) {
          count++;
        }
      }
      out.println(String.valueOf(count));
    }
  }

  /**
   * データダンプを出力する（値）
   */
  public void printAllValue(PrintStream out) {
    StringBuffer buffer;
    for (int y = 0; y < height; y++) {
      buffer = new StringBuffer();
      for (int x = 0; x < width; x++) {
        buffer.append(pixels[x][y].getValue()).append(",");
      }
      out.println(buffer.toString());
    }
  }

  /**
   * データダンプを出力する（重み）
   */
  public void printAllWeight(PrintStream out) {
    StringBuffer buffer;
    for (int y = 0; y < height; y++) {
      buffer = new StringBuffer();
      for (int x = 0; x < width; x++) {
        buffer.append(pixels[x][y].getWeight()).append(",");
      }
      out.println(buffer.toString());
    }
  }
}

Main.java

public class Main {
  /* 全体の幅 */
  private static final int WIDTH = 600;

  /* 全体の高さ */
  private static final int HEIGHT = 600;

  /* 入力ファイル名 */
  private static final String INPUT_FILE_PATH = "data.txt";

  /* 出力ファイル名 */
  private static final String OUTPUT_FILE_PATH = "result.txt";

  public static void main(String[] args) throws Exception {

    PatchWork patchWork = new PatchWork(WIDTH, HEIGHT);

    // データ読み込みと処理
    patchWork.search(INPUT_FILE_PATH);

    // コンソールに答えを表示
    patchWork.printAnswer(System.out);

  }
}

漢字サーバ

まだやってないです！
時間があったら、やります！