import org.junit.Test;

import java.io.*;
import java.util.*;

public class HilbertCurve {
    class InputValues {
        int x;
        int y;
        int n;
        public InputValues(int x, int y, int n) {
            this.x = x;
            this.y = y;
            this.n = n;
        }

        @Override
        public String toString() {
            return "x: " + x + "\ty: " + y + "\tn: " + n;
        }
    }

    @Test
    public void test() {
        File[] files = readFolder("src/input/HilbertCurve");
        HilbertCurve.InputValues test = readFile(files[12]);
        System.out.println(test);

        int res = hilbertCurve(test.x, test.y, test.n);

        System.out.println(res);
    }

    public void generateOutput() throws IOException {
        File[] files = readFolder("src/input/HilbertCurve");
        for (int i = 0; i < files.length; i++) {
            File file = files[i];
            HilbertCurve.InputValues test = readFile(file);
            String outfileName = "src/output/HilbertCurve/" + file.getName().replace(".in", ".out");
            File outfile = new File(outfileName);
            outfile.getParentFile().mkdirs();
            outfile.createNewFile();
            int result = hilbertCurve(test.x, test.y, test.n);
            PrintWriter printWriter = new PrintWriter(new FileWriter(outfileName));
            printWriter.println(result);
            printWriter.close();
        }
    }

    public int hilbertCurve(int x, int y, int n) {
        // x, y coordinator range
        int len = 1 << n;
        int halfLen = 1 << (n - 1);
        int quadrant = -1;
        int newX = -1;
        int newY = -1;
        if (x < halfLen && y < halfLen) {
            quadrant = 0;
            newX = halfLen - 1 - y;
            newY = x;
        } else if (x < halfLen && y >= halfLen) {
            quadrant = 1;
            newX = x;
            newY = y - halfLen;
        } else if (x >= halfLen && y >= halfLen) {
            quadrant = 2;
            newX = x - halfLen;
            newY = y - halfLen;
        } else {
            quadrant = 3;
            newX = y;
            newY = len - 1 - x;
        }
        if (n == 1) {
            return quadrant;
        }
        int quadrantNum = halfLen * halfLen ;
        if (quadrant == 0) {
            return quadrantNum - 1 - hilbertCurve(newX, newY, n - 1);
        } else if (quadrant == 1) {
            return 1 * quadrantNum + hilbertCurve(newX, newY, n - 1);
        } else if (quadrant == 2) {
            return 2 * quadrantNum + hilbertCurve(newX, newY, n - 1);
        } else {
            return 4 * quadrantNum - 1 - hilbertCurve(newX, newY, n - 1);
        }
    }

    private int getInt(String name) {
        return Integer.parseInt(name.replaceAll("\\D", ""));
    }

    private File[] readFolder(String path) {
        File folder = new File(path);
        File[] files = folder.listFiles();
        Arrays.sort(files, (a, b) -> getInt(a.getName()) - getInt(b.getName()));
        return files;
    }

    private HilbertCurve.InputValues readFile(File file) {
        try {
            // assume the input file is always valid
            Scanner sc = new Scanner(file);
            String[] inputs = sc.nextLine().split(" ");
            int x = Integer.parseInt(inputs[0]), y = Integer.parseInt(inputs[1]), n = Integer.parseInt(inputs[2]);
            sc.close();
            return new HilbertCurve.InputValues(x, y, n);
        } catch (FileNotFoundException e) {
            System.out.println(file.getName() + " not exist");
        }
        return null;
    }
}