某氏の Ruby スクリプトを撃墜するためのランダムケースジェネレーター

Takezo.java

import java.io.*;
import java.util.ArrayList;
import java.util.Random;

public class Takezo {
  public static void main(String[] args) throws IOException {

    Random random = new Random();
    File dir = new File("/Users/um003282/Desktop");
    while (true) {

      Process solution = Runtime.getRuntime().exec("ruby takezo.rb", null, dir);
      BufferedReader reader = new BufferedReader(new InputStreamReader(
        solution.getInputStream()));
      PrintWriter writer = new PrintWriter(solution.getOutputStream());

      int N = 8;
      ArrayList<int[]> list = new ArrayList<>();
      for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
          if (random.nextInt(3) == 0) list.add(new int[]{i, j});
        }
      }
      System.out.println(N + " " + list.size());
      writer.println(N + " " + list.size());
      for (int[] e : list) {
        System.out.println((e[0] + 1) + " " + (e[1] + 1));
        writer.println((e[0] + 1) + " " + (e[1] + 1));
      }
      writer.flush();

      Task kenkoooo = new Task();
      long rubyAns = Long.parseLong(reader.readLine());
      if (rubyAns != kenkoooo.solve(list, N)) throw new AssertionError();

    }
  }

  static class Task {
    long[] dp;
    boolean[][] graph;
    int N;
    long dfs(int mask) {
      if (dp[mask] > 0) return dp[mask];
      if (Integer.bitCount(mask) == 1) return 1;

      long ans = 0;
      for (int v = 0; v < N; v++) {
        if ((mask & (1 << v)) == 0) continue;

        boolean ok = true;
        for (int i = 0; i < N; i++) {
          if ((mask & (1 << i)) == 0) continue;
          if (i == v) continue;
          if (graph[v][i]) {
            ok = false;
            break;
          }
        }

        if (ok) {
          ans += dfs(mask ^ (1 << v));
        }
      }
      return dp[mask] = ans;
    }

    long solve(ArrayList<int[]> list, int N) {
      this.N = N;
      dp = new long[1 << N];
      graph = new boolean[N][N];
      for (int i = 0; i < list.size(); i++) {
        int x = list.get(i)[0];
        int y = list.get(i)[1];
        graph[x][y] = true;
      }

      return dfs((1 << N) - 1);
    }
  }
}