import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.Comparator;
import java.util.Collections;
import java.util.Set;
import java.util.HashSet;

class SortbyMht implements Comparator<State>
{
    // Used for sorting in ascending order of
    // roll number
    public int compare(State a, State b)
    {
        return a.mhtDistance - b.mhtDistance;
    }
}

class State {
    class Coord {
        public int x;
        public int y;
        Coord(int x,int y) {
            this.x = x;
            this.y = y;
        }
    }

    int[] plates = new int[9];
    int mhtDistance;
    Coord[] coords = new Coord[] {
        new Coord(0, 0),
        new Coord(0, 1),
        new Coord(0, 2),
        new Coord(1, 0),
        new Coord(1, 1),
        new Coord(1, 2),
        new Coord(2, 0),
        new Coord(2, 1),
        new Coord(2, 2),
    };
    State(int[] plates) {
        for(int i=0; i < plates.length; i++) {
            this.plates[i] = plates[i];
        }
        this.mhtDistance = calculateMhtDist();
    }

    private int calculateMhtDist() {
        int sum = 0;
        for (int i = 0; i < this.plates.length; i++) {
            int x1 = coords[this.plates[i]].x;
            int y1 = coords[this.plates[i]].y;
            int x0 = coords[i].x;
            int y0 = coords[i].y;
            sum += Math.abs(x1-x0) + Math.abs(y1-y0);
        }
        return sum;
    }

    public void print() {
        for(int i : this.plates) {
            System.out.print(i + " ");
        }
        System.out.println(this.mhtDistance);
    }
}

public class Genetic8Puzzle {

    public static int randInt(int min, int max) {

        // NOTE: This will (intentionally) not run as written so that folks
        // copy-pasting have to think about how to initialize their
        // Random instance.  Initialization of the Random instance is outside
        // the main scope of the question, but some decent options are to have
        // a field that is initialized once and then re-used as needed or to
        // use ThreadLocalRandom (if using at least Java 1.7).
        //
        // In particular, do NOT do 'Random rand = new Random()' here or you
        // will get not very good / not very random results.
        Random rand = new Random();

        // nextInt is normally exclusive of the top value,
        // so add 1 to make it inclusive
        int randomNum = rand.nextInt((max - min) + 1) + min;

        return randomNum;
    }

    static List<State> population = new ArrayList<>();
    private static int[] goalState = new int[]{0, 1 , 2, 3, 4, 5 ,6 ,7 ,8};

    public static void init() {
        try {
            BufferedReader reader = new BufferedReader(new FileReader(
                        "test.txt"));
            String line = reader.readLine();
            int[] plates = new int[9];
            while (line != null) {
                String[] parts = line.split(" ");
                for(int i=0; i < parts.length; i++) {
                    plates[i] = Integer.parseInt(parts[i]);
                }
                population.add(new State(plates));
                line = reader.readLine();
            }
            reader.close();
        } catch (IOException e) {
                e.printStackTrace();
        }
    }
    static State reproduce(State x, State y) {
        int splitter = randInt(0, 8);
        int[] newPlates = new int[9];
        for (int i = 0; i < splitter; i++) {
            newPlates[i] = x.plates[i];
        }
        for (int i = splitter; i < 9; i++) {
            newPlates[i] = y.plates[i];
        }
        return new State(newPlates);
    }
    static State mutate(State child) {
        int i = randInt(0, child.plates.length - 1);
        int j = randInt(0, child.plates.length - 1);
        int temp = child.plates[i];
        child.plates[i] = child.plates[j];
        child.plates[j] = temp;
        return child;
    }

    public static State randomSelection(List<State> population) {
        int randNum = randInt(0, Math.min(population.size(), 6));
        return population.get(randNum);
    }
    public static boolean  distinctValues(int[] plates){
        Set<Integer> foundPlates = new HashSet<>();
        for(Integer plate : plates){
            if(foundPlates.contains(plate)){
                return false;
            }
            foundPlates.add(plate);
        }
        return true;
    }

    public static void main(String[] args) {
        init();
        int i = 0;
        while (true) {
            i++;
                System.out.println("in");
                // random select x
                State x = population.get(randInt(0, population.size() - 1));
                // random select y
                State y = population.get(randInt(0, population.size() - 1));
                // create child
                State child = reproduce(x, y);

                child.print();
                // check if goal
                if (child.mhtDistance == 0) {
                    // success
                    break;
                }
                //mutate if necessary
                int randomNumber = randInt(0, 9);
                if (randomNumber == 1) {
                    child = mutate(child);
                }
                //if (distinctValues(child.plates)) {
                    population.add(child);
                    // sort
                    Collections.sort(population, new SortbyMht());
                //}

        }

    }
}