// L?sningsforslag, Inf110 oppgaver, uke 4

//////////////////////////////////////////////////////////////////////////
// Oppgave 1: Plassering av 9 sifre

class RSiffer {
  int r;        // r-tallsystemet
  int rm1;      // r-1
  int [] sekv;
  static long num =0;
  boolean [] brukt;

  RSiffer(int r){
    this.r=r; rm1=r-1;
    sekv = new int[r];
    brukt = new boolean[r];
  }

  void finnSiffer (int i) {
     num++;
     for (int tall = 1; tall < r; tall++) {
       if (! brukt [tall]) {
         brukt[tall] = true;
         sekv[i] = tall;
         if (i == rm1 && erDelelig(rm1)) 
           skrivUt(); // l?sning
         else if (erDelelig(i)) // avskj?ring
           finnSiffer(i+1);
         brukt[tall] = false;
       }
     }
  } // end finnSiffer

  int finntall (int i) { 
    int t = 0, rpot = 1;
    for( int k = i; k >= 1 ; k --)
      { t = t + sekv[k] *rpot; rpot *=r;}
    return t;
  }

 boolean erDelelig(int k) {
     int t = finntall(k);
     if (t % (k) == 0) return true;
     else return false;
 }

 void skrivUt() {
        System.out.print(" Sekvens " + num + " :");
        for (int i = 1; i < r; i++)
          System.out.print  (" " + sekv[i]);
        System.out.println  (" " );
 }
}

///////////////////////////////////
public class Rm1Sifre{
  // start program: >java Rm1Sifre <r>
  public static void main (String [] args) {
    int r = Integer.parseInt(args[0]);
	RSiffer kv = new RSiffer (r);
    System.out.println(r+"-tallsystemet.");
    long tid = System.currentTimeMillis();
    kv.finnSiffer (1);
    tid =  System.currentTimeMillis() - tid;
    System.out.println("Tid brukt: " + tid + " millisekunder, ant. rek. kall:" + kv.num);
  }
}

/* Resultat av kj?ringer:
2-tallsystemet (trivielt oppfylt pga tom betingelse).
 Sekvens 1 : 1 
Tid brukt: 2 millisekunder, ant. rek. kall:1

4-tallsystemet.
 Sekvens 3 : 1 2 3 
 Sekvens 6 : 3 2 1 
Tid brukt: 80 millisekunder, ant. rek. kall:6

6-tallsystemet.
 Sekvens 7 : 1 4 3 2 5 
 Sekvens 22 : 5 4 3 2 1 
Tid brukt: 20 millisekunder, ant. rek. kall:22

8-tallsystemet.
 Sekvens 33 : 3 2 5 4 1 6 7 
 Sekvens 51 : 5 2 3 4 7 6 1 
 Sekvens 65 : 5 6 7 4 3 2 1 
Tid brukt: 261 millisekunder, ant. rek. kall:88

10-tallsystemet.
 Sekvens 109 : 3 8 1 6 5 4 7 2 9 

De andre R-tallsystemene opp til 20 ga ingen l?sning.
*/

//////////////////////////////////////////////////////////////////////////
// Oppgave 2: Magiske firkanter

class Firkant {
  int n;
  int [][] ruter ;
  int [] sumKol, sumRad;
  static long num =0;
  int sum,n2;
  boolean [] brukt;
  int antL =0;

  Firkant(int n){
	  this.n = n;
	  sum = n*(n*n+1)/2;
	  ruter = new int [n][n];
	  sumKol = new int [n];
	  sumRad = new int [n];
	  brukt = new boolean [n*n+1];
   } // end Kontrukt?r


   void finnFirkant (int i) {
	 int rad = i/n, kol = i%n;

     num++;
     for (int tall = 1; tall <= n2; tall++) {
       if (! brukt [tall]) { 
         brukt[tall] = true;
         ruter[rad][kol] = tall;
         sumKol[kol] += tall;
         sumRad[rad] += tall;

         // System.out.println("i:"+i); skrivUt();
         if (i+1 == n2 && diagSum() && sumKol[kol] == sum && sumRad[rad]==sum )
            { antL++;
              //System.out.print(", " + antL);
              skrivUt();
            }
        else if ( i == 0 ||
                 ( (rad == n-1) &&  sumKol[kol] == sum && sumRad[n-1] <= sum) ||
                 ((kol == n-1) && (sumRad[rad] == sum) && (sumKol[kol] <= sum)) ||
                 ((kol < n-1) && sumRad[rad] < sum && sumKol[kol] <sum ) )

                       finnFirkant(i+1);

        sumRad[rad] -= tall;
        sumKol[kol] -= tall;
        brukt[tall] = false;
      }
     }
    } // end finnFirkant

    boolean diagSum(){
		int s1 =0, s2=0;
		for (int i = 0; i < n; i++)
		{ s1 += ruter[i][i];
		  s2 += ruter[n-1-i][i];
	     }
	     return (s1==sum)&& (s2==sum);
	}// end diagSum

   void skrivUt() {
         for (int i = 0; i < n; i++)
 		 System.out.print("---");
 		 System.out.println("-");
 		 for (int i = 0; i < n; i++)
 		 {
 			 for (int j = 0; j < n ; j++)
 			    System.out.print("|"+Ut.writeInt(ruter[i][j],2));

 			 System.out.println("|");
 			 for (int j = 0; j < n ; j++)
 			 System.out.print("---");
 			 System.out.println("-");
 		 }
 		 System.out.println("");
 	 } // end skrivUt
}

///////////////////////////////////
  // start program: >java MagiskFirkant 'n'
  public static void main (String [] args) {
	    Firkant kv = new Firkant (Integer.parseInt(args[0]));

        long tid = System.currentTimeMillis();
        kv.finnFirkant (0);
  	    tid =  System.currentTimeMillis() - tid;

		System.out.println("Tid brukt: " + tid +
		                   " millisek, rek. kall:" + kv.num +
		                   ", ant l?sn:" + kv.antL);
  }
}

// Bedre avskj?ring? Jeg vet ikke.

////////////////////////////////////////////////////////////////////////////
/* Oppgave 3: Fargelegging av land
Se notatet av Harald Askestad: "Fargelegg Ruritania"
*/
////////////////////////////////////////////////////////////////////////////
/* Oppgave 4: O-notasjon
Se notatet av Harald Askestad: "Enkel analyse med O-notasjon"

2.11
a)	2.5ms
b)	log 5 ~= 2.32  log 100 ~= 6.64
	T(500)=c*500*log 500 = 0.5/(100*log 100)*500*log 500=
		 2.5*(1+log 5/log 100) ~= 3.4ms
c)	12.5ms
d)	62.5ms

2.12
a)	12 000 000
b)	T(100)=c*100*log 100=0.5  
	n*log n=60000*200*log 100 = 79 680 000
      n ~= 3 654 000
c)	34 600
d)	4 900
*/
////////////////////////////////////////////////////////////////////////////
/* Oppgave 5: Mer O-notasjon
Se notatet av Harald Askestad: "Enkel analyse med O-notasjon"
*/