import java.util.Scanner;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.concurrent.atomic.AtomicInteger;



class Uke9_Oppg2 {
    public static void main (String [] args) {
        if (args.length != 1) {
            System.out.println("Usage: java Uke9_Oppg2 <num_cities_to_visit>");
        } else {
            new SeqRSelger(Integer.parseInt(args[0])).utfoer();
        }
    }
}

class SeqRSelger {
    final int [][] avstand ;
    int bestHittil = Integer.MAX_VALUE;
    int [] besteRute;
    final int n;
    final AtomicInteger threadCount = new AtomicInteger();
    final int cores = Runtime.getRuntime().availableProcessors();

    SeqRSelger(int n) {
        this.n = n;
        avstand = new int[26][26];
        readFile("bydata.txt");
    }

    /**
     * Kj?r koden
     */
    void utfoer() {
        /* ***** Parallell l?sning ***** */
        besteRute = new int[n];
        bestHittil = Integer.MAX_VALUE;

        long parStart = System.nanoTime();
        parRSR(1, 0, 0, new boolean[n], new int[n]);
        long parTime = System.nanoTime() - parStart;

        printResultat("Parallell", parTime);

        /* ***** Sekvensiell l?sning ***** */
        besteRute = new int[n];
        bestHittil = Integer.MAX_VALUE;

        long sekStart = System.nanoTime();
        sekRSR(1, 0, 0, new boolean[n], new int[n]);
        long sekTime = System.nanoTime() - sekStart;

        printResultat("Sekvensiell", sekTime);
    }

    /**
     * Skriver ut resultatet fra en kj?ring.
     * @param type typen av kj?ring (sekvensiell eller parallell)
     */
    void printResultat(String type, long time) {
        System.out.printf("%s l?sning beregnet p? %.2f ms ble rute med %d byer: \n",
                          type, (time/1000000.0), n);
        for (int i = 0; i < besteRute.length; i++) {
            System.out.print(" " + besteRute[i]);
        }
        System.out.println("\n");
    }


    void parRSR(int nivaa, int by, int lengde, boolean[] besoekt, int[] reiseRute) {
        if(nivaa == n) { // gjenst?r bare reisen tilbake til by:0
            synchronized(this) {
                if (lengde + avstand[by][0] < bestHittil){
                    // Noterer ny beste reisevei og lengde
                    bestHittil = lengde + avstand[by][0];
                    System.arraycopy(reiseRute, 0, besteRute, 0, n);
                }
            }
        } else {
            /*
              Vi har denne begrensningen p? antall tr?der vi starter,
              om det ikke hadde v?rt noen begrensing ville vi f?tt
              alt for mange tr?der.
            */
            Thread[] t = null;
            int threadIndex = 0;

            if (threadCount.get() < cores) {
                t = new Thread[cores];
            }

            for (int nesteBy = 1; nesteBy < n; nesteBy++) {
                // proev ? bes?ke alle ikke-bes?kte byer unntatt 0
                if (!besoekt[nesteBy]) {
                    besoekt[nesteBy] = true;
                    reiseRute[nivaa] = nesteBy;

                    if (threadCount.get() >= cores || threadIndex >= cores) {
                        parRSR (nivaa + 1, nesteBy, lengde + avstand[by][nesteBy], besoekt, reiseRute);
                    } else {
                        // Increment threadCount so we don't start too many threads
                        threadCount.incrementAndGet();

                        t[threadIndex] = new Thread(new WorkerThread(nivaa+1, nesteBy,
                                                                     lengde + avstand[by][nesteBy],
                                                                     besoekt.clone(),
                                                                     reiseRute.clone()));
                        t[threadIndex++].start();
                    }
                    besoekt[nesteBy] = false;
                }
            }

            for (int i = 0; i < threadIndex; i++) {
                try {
                    t[i].join();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                    System.exit(1);
                }
            }
        }
    }

    void sekRSR(int nivaa, int by, int lengde, boolean[] besoekt, int[] reiseRute) {
        if(nivaa == n) { // gjenst?r bare reisen tilbake til by:0
            if (lengde + avstand[by][0] < bestHittil){
                // Noterer ny beste reisevei og lengde
                bestHittil = lengde + avstand[by][0];
                System.arraycopy(reiseRute, 0, besteRute, 0, n);
            }
        } else {
            for (int nesteBy = 1; nesteBy < n; nesteBy++) {
                // proev ? bes?ke alle ikke-bes?kte byer unntatt 0
                if (!besoekt[nesteBy]) {
                    besoekt[nesteBy] = true;
                    reiseRute[nivaa] = nesteBy;
                    sekRSR (nivaa + 1, nesteBy, lengde + avstand[by][nesteBy], besoekt, reiseRute);
                    besoekt[nesteBy] = false;
                }
            }
        }

    }


    class WorkerThread implements Runnable {
        private final int nivaa, by, lengde;
        private boolean[] besoekt;
        private int[] reiseRute;

        /**
         * @param nivaa hvor mange byer vi har bes?kt (inkludert denne)
         * @param by indeksen til den byen vi er p? n?
         * @param lengde hvor langt vi har reist til n?
         * @param besoekt om et element er false betyr det at byen med
         * samme indeks er bes?kt
         * @param reiseRute den ruta vi har fulgt s? langt
         */
        WorkerThread(int nivaa, int by, int lengde, boolean[] besoekt, int[] reiseRute) {
            this.nivaa = nivaa;
            this.by = by;
            this.lengde = lengde;
            this.besoekt = besoekt;
            this.reiseRute = reiseRute;
        }

        public void run() {
            System.err.println("Startet tr?d " + threadCount.get());

            parRSR(nivaa, by, lengde, besoekt, reiseRute);
            System.err.println("ferdig tr?d " + threadCount.get());

            // Now we are finished, we can start new threads
            //threadCount.decrementAndGet();
        }
    }

    public void readFile(String filename) {
        Scanner scan = null;

        try {
            scan = new Scanner(new File(filename));
        } catch (FileNotFoundException e) {
            e.printStackTrace();
            System.exit(1);
        }

        int row = 0;
        while(scan.hasNextLine()) {
            String[] distances = scan.nextLine().split("\\s+");

            for (int column = 1; column < distances.length; column++) {
                avstand[row][column-1] = Integer.parseInt(distances[column]);
            }

            row++;
        }

        scan.close();
    }
}