Daaada

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package pal;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 *
 * @author Dada
 */
class MatchBelts {

    private int numberOfBelts;
    private int numberOfSegments;
    private int numberOfDisks;

    private int actualFreePositionInOutput;
    private boolean directionOfDiskOnBelt; //true = left; false = right
    private int maxBeltsOnRow;
    private int minBeltsOnRow;
    private int actualPositionInOutput;

    private String[][] loadedBelts;
    private String[] output;
    private int[][] outputNumeric;
    private int[][] sortedOutput;
    private int occurrence[];
    private boolean[] isSorted;

    void loadValues() throws IOException {
        BufferedReader bi = new BufferedReader(new InputStreamReader(System.in));
        String line;

        //load first row
        setBasicValues(bi);

        //vytvoreni potrebnych poli
        createArrays();

        //nacitani pasku
        for (int i = 0; i < numberOfBelts; i++) {
            loadBelt(bi, i);
        }

//zda jsou dobre nactene
//        for (int i = 0; i < numberOfBelts; i++) {
//            for (int j = 0; j < numberOfDisks; j++) {
//                System.out.print(loadedBelts[i][j] + "|");
//            }
//            System.out.println("");
//        }
//jak je nadefinovane pole isSorted
//        for (int i = 0; i < numberOfBelts; i++) {
//            System.out.println(isSorted[i]);
//        }
//jak je nadefinovane pole output
//        for (int i = 0; i < numberOfBelts; i++) {
//            System.out.println(output[i]);
//        }
    }

    private void setBasicValues(BufferedReader bi) throws IOException {
        actualFreePositionInOutput = 0;
        directionOfDiskOnBelt = false;
        maxBeltsOnRow = 0;
        minBeltsOnRow = 0;

        String line = bi.readLine();
        String[] split = line.split("\\s");
        numberOfBelts = Integer.parseInt(split[0]);
        numberOfSegments = Integer.parseInt(split[1]);
        numberOfDisks = Integer.parseInt(split[2]);
    }

    private void createArrays() {
        //ulozene stringy z nactenych disku
        loadedBelts = new String[numberOfBelts][numberOfDisks];

        //pole stringu pro vypis
        output = new String[numberOfBelts];
        //pole pro sortovani vystupu
        outputNumeric = new int[numberOfBelts][2];
        sortedOutput = new int[numberOfBelts][2];

        //pole jiz zarazenych beltu
        isSorted = new boolean[numberOfBelts];
    }

    private void loadBelt(BufferedReader bi, int i) throws IOException {
        String line;
        line = bi.readLine();
        String[] split = line.split("\\s");

        //nacita jednotlive stringy
        for (int j = 0; j < numberOfDisks; j++) {
            loadedBelts[i][j] = split[j + 1];
        }
    }

    void findMatches() {
        String doubledDisk;//zdvojeny string jednoho disku
        actualPositionInOutput = 0;
        boolean actualPositionInOutpusIsSet = false;
        boolean sameBelts = false;

        for (int i = 0; i < numberOfBelts; i++) {//kazdy pasek postupne. 0,1,2...
            actualPositionInOutpusIsSet = false;
            for (int j = i + 1; j < numberOfBelts; j++) {//musim porovnat s kazdym paskem, ale uz nemusim s tim ktery jsem kontroloval predtim proto od i
                if (isSorted[j] == false) {//pokud uz je pasek zarazen je zbytecne ho znovu kontrolovat

                    for (int k = 0; k < numberOfDisks; k++) {//z prvniho pasku z prvniho foru bere jeden disk za druhym, bude je kontrolvoat s disky z dalsiho
                        doubledDisk = loadedBelts[i][k] + loadedBelts[i][k];//definuji uz tady aby se nemusel tento string vytvaret porad
                        for (int l = 0; l < numberOfDisks; l++) {//s disky z druheho foru bude kontrolovat disk z foru tretiho
                            if (isSame(doubledDisk, j, l) == true) {//pokud je nalezena shoda disku
                                //System.out.println("same " + i + "-" + k + " | " + j + "-" + l);//funguje
                                sameBelts = checkBelts(i, k, j, l);//resi zda jsou dalsi disky vedle nalezene shody ty spravne
                                if (sameBelts == true) {//nalezena shoda
                                    isSorted[i] = true;//uz jsou nalezeny schody je zbytecny ej znova pouzivat
                                    isSorted[j] = true;//uz jsou nalezeny schody je zbytecny ej znova pouzivat
                                    if (actualPositionInOutpusIsSet == false) {//pokud nebyl jeste do outputu zarazen zadny prvek ktery by se schodoval s paskem na pozici "i"
                                        actualPositionInOutput++;
                                    }
                                    addToOuput(i, j, actualPositionInOutput - 1);//prida do stringu outputu labely shodnych pasku

                                    actualPositionInOutpusIsSet = true;
                                    break;
                                }
                            }
                        }
                        if (sameBelts == true) {
                            break;
                        }
                    }

                }
            }
            if (isSorted[i] == false) {//resi kdyz porovnam pasek se vsemi a nidke nenajdu shodu
                actualPositionInOutput++;
                addToOuput(-1, i, actualPositionInOutput - 1);//bacha lehka modifikace i a j je prohozene
            }
        }

//        System.out.println("--------------------------OUTPUT--------------------------");
//        int position = 0;
//        System.out.println(actualPositionInOutput);
//        while (output[position] != null) {
//            System.out.println(output[position]);
//            position++;
//        }

    }

    private boolean isSame(String doubledDisk, int j, int l) {
        //disky jsou stejne
        if (doubledDisk.contains(loadedBelts[j][l])) {
            return true;
        }

        //zda obsahuje rotaci disku
        return doubledDisk.contains(rotate(loadedBelts[j][l]));
    }

    private CharSequence rotate(String disk) {
        StringBuilder diskBuilder = new StringBuilder(disk);
        return diskBuilder.reverse().toString();
    }

    private boolean checkBelts(int firstBelt, int firstDisk, int secondBelt, int secondDisk) {
        int actualSecondDisk;
        int actualFirstDisk;

        ////////////////kotrola zda je vpravo////////////////
        actualFirstDisk = firstDisk + 1;//posun o jeden doprava
        if (actualFirstDisk == numberOfDisks) {//pokud to byl disk ktery byl oznacen na pasku jako posledni tak dalsi vpravo je prvni z pasku
            actualFirstDisk = 0;
        }
        String doubledDisk = loadedBelts[firstBelt][actualFirstDisk] + loadedBelts[firstBelt][actualFirstDisk];//definuji uz tady aby se nemusel tento string vytvaret porad

        actualSecondDisk = secondDisk + 1;//posun o jeden doprava
        if (actualSecondDisk == numberOfDisks) {//pokud to byl disk ktery byl oznacen na pasku jako posledni tak dalsi vpravo je prvni z pasku
            actualSecondDisk = 0;
        }

        if (isSame(doubledDisk, secondBelt, actualSecondDisk) == true) {//pokud je nalezena shoda disku tak je smer doprava
            //System.out.println("vpravo");
            while (actualFirstDisk != firstDisk) {//objizdi cele kolo
                actualFirstDisk = actualFirstDisk + 1;//posun o jeden doprava
                if (actualFirstDisk == numberOfDisks) {//pokud to byl disk ktery byl oznacen na pasku jako posledni tak dalsi vpravo je prvni z pasku
                    actualFirstDisk = 0;
                }
                doubledDisk = loadedBelts[firstBelt][actualFirstDisk] + loadedBelts[firstBelt][actualFirstDisk];//definuji uz tady aby se nemusel tento string vytvaret porad

                actualSecondDisk = actualSecondDisk + 1;//posun o jeden doprava
                if (actualSecondDisk == numberOfDisks) {//pokud to byl disk ktery byl oznacen na pasku jako posledni tak dalsi vpravo je prvni z pasku
                    actualSecondDisk = 0;
                }

                //System.out.println(doubledDisk + "  " + loadedBelts[secondBelt][actualSecondDisk]);
                if (isSame(doubledDisk, secondBelt, actualSecondDisk) == false) {
                    return false;
                }
            }
            return true;
        }

        ////////////////kotrola zda je vlevo////////////////
        actualSecondDisk = secondDisk - 1;//posun o jeden doprava
        if (actualSecondDisk == - 1) {//pokud to byl disk ktery byl oznacen na pasku jako prvni tak dalsi vlevo je vlastne posledni
            actualSecondDisk = numberOfDisks - 1;
        }

        if (isSame(doubledDisk, secondBelt, actualSecondDisk) == true) {//pokud je nalezena shoda disku tak je smer vlevo
            //System.out.println("vlevo");
            while (actualFirstDisk != firstDisk) {//objizdi cele kolo
                actualFirstDisk = actualFirstDisk + 1;//posun o jeden doprava
                if (actualFirstDisk == numberOfDisks) {//pokud to byl disk ktery byl oznacen na pasku jako posledni tak dalsi vpravo je prvni z pasku
                    actualFirstDisk = 0;
                }
                doubledDisk = loadedBelts[firstBelt][actualFirstDisk] + loadedBelts[firstBelt][actualFirstDisk];//definuji uz tady aby se nemusel tento string vytvaret porad

                actualSecondDisk = actualSecondDisk - 1;//posun o jeden doprava
                if (actualSecondDisk == - 1) {//pokud to byl disk ktery byl oznacen na pasku jako prvni tak dalsi vlevo je vlastne posledni
                    actualSecondDisk = numberOfDisks - 1;
                }

                if (isSame(doubledDisk, secondBelt, actualSecondDisk) == false) {
                    return false;
                }
            }
            return true;
        }

        return false;
    }

    private void addToOuput(int i, int j, int actualPositionInOutput) {
        //System.out.println("addion to output...");
        String helpa;

        if (i == -1) {
            helpa = Integer.toString(j);
            output[actualPositionInOutput] = helpa;
            outputNumeric[actualPositionInOutput][1]++;
            outputNumeric[actualPositionInOutput][0] = actualPositionInOutput;
            if (outputNumeric[actualPositionInOutput][1] > maxBeltsOnRow) {
                maxBeltsOnRow = outputNumeric[actualPositionInOutput][1];
            }
            return;
        }

        if (output[actualPositionInOutput] == null) {
            helpa = i + " " + j;
            output[actualPositionInOutput] = helpa;
            outputNumeric[actualPositionInOutput][1] += 2;
            outputNumeric[actualPositionInOutput][0] = actualPositionInOutput;
            if (outputNumeric[actualPositionInOutput][1] > maxBeltsOnRow) {
                maxBeltsOnRow = outputNumeric[actualPositionInOutput][1];
            }
            return;
        } else {
            helpa = " " + j;
            output[actualPositionInOutput] = output[actualPositionInOutput] + helpa;
            outputNumeric[actualPositionInOutput][1]++;
            outputNumeric[actualPositionInOutput][0] = actualPositionInOutput;
            if (outputNumeric[actualPositionInOutput][1] > maxBeltsOnRow) {
                maxBeltsOnRow = outputNumeric[actualPositionInOutput][1];
            }
            return;
        }
    }

    void sortOutput() {
//        System.out.println("---------------------------SORTED INTEGERS--------------------");
//        for (int i = 0; i < actualPositionInOutput; i++) {
//            System.out.println(outputNumeric[i][0] + " | " + outputNumeric[i][1]);
//        }

//        System.out.println("---------------------------SORTING--------------------");
        countingSort();
    }

    void countingSort() {
        //nastavi velikost priznakoveho pole
        setOccurrenceSize();
        //nastavi priznakovemu poly pocty vyskytu
        setNumberOfOccurrence();
//        for (int i = 0; i < occurrence.length; i++) {
//            System.out.println(occurrence[i]);
//        }
        //nastavi posledni indexy
        setTheLastIndex();
        //serad pole
        sortArray();

//        for (int i = 0; i < actualPositionInOutput; i++) {
//            System.out.print(sortedOutput[i][0] + " " + sortedOutput[i][1]);
//            System.out.println("");
//        }
    }

    private void setOccurrenceSize() {
        occurrence = new int[maxBeltsOnRow - minBeltsOnRow + 1];//new int[maxBeltsOnRow - minBeltsOnRow + 1];//TODO
    }

    private void setNumberOfOccurrence() {
        for (int i = 0; i < actualPositionInOutput; i++) {
//            System.out.println(outputNumeric[i][1]);
            occurrence[outputNumeric[i][1] - minBeltsOnRow]++;
        }
    }

    private void setTheLastIndex() {
        occurrence[0]--;
        for (int i = 1; i < occurrence.length; i++) {
            occurrence[i] += occurrence[i - 1];
        }
    }

    private void sortArray() {
//        System.out.println("sort array");
        for (int i = 0; i  < actualPositionInOutput; i++) {
        //for (int i = actualPositionInOutput - 1; i >= 0; i--) {
            int c = outputNumeric[i][1] - minBeltsOnRow;
//            System.out.println("pozice v vyskytu " + c);
            int s = occurrence[c];
//            System.out.println("pozice cisla " + s);
            sortedOutput[s][0] = outputNumeric[i][0];
            sortedOutput[s][1] = outputNumeric[i][1];

            occurrence[c]--;
        }

    }

    void output() {
//        System.out.println("----------------------OUTPUT------------------------");
        System.out.println(actualPositionInOutput);
        for (int i = actualPositionInOutput-1; i >=0; i--) {
            System.out.println(output[sortedOutput[i][0]]);
        }
    }
}