Description_Multiple_Pieces_Tester.md

Multiple Pieces テスター

• これは 日本橋ハーフマラソン予選 問題A - Multiple Pieces のテストケースジェネレータとジャッジのためのプログラムです。これらを用いることで、ローカル環境でプログラムのテストを行うことができます。
• これらのプログラム上で計算された得点は、当コンテストでの得点ではありません。また、これらのプログラム上で計算された得点は、当コンテストでの得点を保証するものではありません。
• これらのプログラムを使用することによるあらゆる損害は保障しかねますので、予めご了承ください。
• これらのプログラムに関する質問は受け付けていません。予めご了承ください。
• これらのプログラムの一部を、コンテストの解答に流用してもかまいません。

コンパイル

Generator.java, Judge.java, TestCase.java の 3 つのファイルを同じディレクトリに設置し、以下のコマンドを実行してください。

javac -encoding UTF-8 Generator.java
javac -encoding UTF-8 Judge.java

テストケース生成

コンパイル後、好きな乱数シードを整数で与えることで、問題文の条件を満たすテストケースを生成できます。以下のコマンドでは 123 という値を乱数シード値として、input.txt というテキストファイルにテストケースを保存しています。

java Generator -seed 123 > input.txt

得点計算

コンパイル後、テストケースのテキストファイルと、自分のプログラムの出力結果のテキストファイルから、テストケースに対する得点を計算することができます。以下のコマンドでは、 input.txt というテキストファイルに保存されたテストケースに対する output.txt というテキストファイル内の出力から得られる得点を計算しています。

java Judge input.txt output.txt

Generator.java

import java.util.Random;

public class Generator {

    public static void main(String[] args) throws Exception {
        long seed = new Random().nextInt();
        for (int i = 0; i < args.length; ++i) {
            if (args[i].equals("-seed")) {
                seed = Long.parseLong(args[++i]);
            }
        }
        TestCase testcase = new TestCase(seed);
        System.out.println(testcase);
    }

}

Judge.java

import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.Scanner;

public class Judge {

    static class Result {
        TestCase input;
        long score;

        @Override
        public String toString() {
            StringBuilder builder = new StringBuilder();
            builder.append("raw score:" + score + "\n");
            builder.append("score:" + ((score + 9999) / 10000) + "\n");
            return builder.toString();
        }
    }

    static class Piece {
        int[] x, y;

        Piece(int[] x, int[] y) {
            this.x = x;
            this.y = y;
        }

        long calcScore(TestCase testcase) {
            long score = 1;
            for (int i = 0; i < this.x.length; i++) {
                score *= testcase.field[this.y[i] - 1][this.x[i] - 1];
            }
            return score;
        }

        boolean isConnected() {
            final int size = this.x.length;
            // ワーシャルフロイド法を使って連結性を判定
            boolean[][] reachable = new boolean[size][size];
            for (int i = 0; i < size; ++i) {
                for (int j = 0; j < i; ++j) {
                    boolean adjacent = Math.abs(x[i] - x[j]) + Math.abs(y[i] - y[j]) == 1;
                    reachable[i][j] = reachable[j][i] = adjacent;
                }
            }
            for (int i = 0; i < size; ++i) {
                for (int j = 0; j < size; ++j) {
                    for (int k = 0; k < size; ++k) {
                        reachable[j][k] |= reachable[j][i] && reachable[i][k];
                    }
                }
            }
            for (int i = 0; i < size; ++i) {
                for (int j = 0; j < i; ++j) {
                    if (!reachable[i][j]) {
                        return false;
                    }
                }
            }
            return true;
        }
    }


    /**
     * 解答の出力をScannerから読み込んでバリデーションを行う
     * バリデーションに失敗した場合はRuntimeExceptionをスローする
     */
    static Piece[] readOutput(TestCase testcase, Scanner sc) throws Exception {
        final int count = sc.nextInt();
        boolean[][] used = new boolean[testcase.H][testcase.W];
        Piece[] ret = new Piece[count];
        for (int i = 0; i < count; ++i) {
            int[] x = new int[testcase.K];
            int[] y = new int[testcase.K];
            for (int j = 0; j < testcase.K; ++j) {
                y[j] = sc.nextInt();
                x[j] = sc.nextInt();
                if (x[j] <= 0 || testcase.W < x[j] || y[j] <= 0 || testcase.H < y[j]) {
                    throw new RuntimeException("position (" + x[j] + "," + y[j] + ") is out of range.");
                }
                if (used[y[j] - 1][x[j] - 1]) {
                    throw new RuntimeException("position (" + x[j] + "," + y[j] + ") used more than once.");
                }
                used[y[j] - 1][x[j] - 1] = true;
            }
            ret[i] = new Piece(x, y);
            if (!ret[i].isConnected()) {
                throw new RuntimeException("piece " + i + " is not connected.");
            }
        }
        if (sc.hasNext()) {
            throw new RuntimeException("there are too many coordinates.");
        }
        return ret;
    }

    /**
     * 盤面とピースの情報を元にスコアを計算する
     * 渡すデータの内容は正しい形式であることが前提
     */
    static Result calcScore(TestCase testcase, Piece[] output) {
        Result res = new Result();
        res.input = testcase;
        for (Piece piece : output) {
            res.score += piece.calcScore(testcase);
        }
        return res;
    }

    public static void main(String[] args) throws Exception {
        if (args.length < 2) {
            System.err.println("usage: java Judge input_file_path output_file_path");
            System.exit(1);
        }
        Path inputFile = Paths.get(args[0]);
        Path outputFile = Paths.get(args[1]);
        try (Scanner input = new Scanner(inputFile); Scanner output = new Scanner(outputFile)) {
            TestCase testcase = new TestCase(input);
            Piece[] pieces = readOutput(testcase, output);
            Result res = calcScore(testcase, pieces);
            System.out.print(res);
        }
    }

}

TestCase.java

import java.security.SecureRandom;
import java.util.Scanner;

public class TestCase {

    static final int MIN_K = 8;
    static final int MAX_K = 8;
    static final int MIN_SIZE = 50;
    static final int MAX_SIZE = 50;

    final int H, W, K;
    final int[][] field;

    TestCase(long seed) throws Exception {
        SecureRandom rnd = SecureRandom.getInstance("SHA1PRNG");
        rnd.setSeed(seed);
        this.H = rnd.nextInt(MAX_SIZE - MIN_SIZE + 1) + MIN_SIZE;
        this.W = rnd.nextInt(MAX_SIZE - MIN_SIZE + 1) + MIN_SIZE;
        this.K = rnd.nextInt(MAX_K - MIN_K + 1) + MIN_K;
        this.field = new int[H][W];
        for (int i = 0; i < H; ++i) {
            for (int j = 0; j < W; ++j) {
                // 盤面の数字をランダムに生成
                this.field[i][j] = rnd.nextInt(10);
            }
        }
    }

    TestCase(Scanner sc) throws Exception {
        this.H = sc.nextInt();
        this.W = sc.nextInt();
        this.K = sc.nextInt();
        this.field = new int[this.H][this.W];
        for (int i = 0; i < this.H; i++) {
            char[] row = sc.next().toCharArray();
            for (int j = 0; j < this.W; j++) {
                this.field[i][j] = row[j] - '0';
            }
        }
    }


    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append(this.H + " " + this.W + " " + this.K + "\n");
        for (int i = 0; i < this.H; ++i) {
            for (int j = 0; j < this.W; ++j) {
                builder.append(this.field[i][j]);
            }
            builder.append("\n");
        }
        return builder.toString();
    }

}