// L?sningsforslag, Inf110 oppgaver, uke 5

//////////////////////////////////////////////////////////////////////////
// OPPGAVE 1
class ToveisListe
{  private class Node
   { Object element;
     Node suc = null;  // Successor (neste)
     Node pred = null; // Predescessor (forrige)
   }

   private Node pos = null; // Sist aksesserte element i listen
                           // null betyr at listen er tom
// Metode for ? sette inn objektet x etter noden pos
   public void settinn(Object x)
   {  Node ny = new Node;
      ny.element = x;
      if (pos != null)
      {  ny.pred = pos;
         ny.suc = pos.suc;
         pos.suc = ny;
         if (ny.suc != null) ny.suc.pred = ny;
      }
      pos = ny;
   }

// Metode for ? sette inn objektet x f?rst i listen
   public void settinnFoerst(Object x)
   {  Node ny = new Node;
      ny.element = x;
      if (pos != null)
      {  while (pos.pred != null) pos = pos.pred;
         pos.pred = ny;
         ny.suc = pos;
      }
      pos = ny;
   }

// Metode som fjerner sist aksesserte element fra listen
   void slett()
   {  if (pos != null)
      {  if (pos.suc != null) pos.suc.pred = pos.pred;
         if (pos.pred != null)
         {  pos.pred.suc = pos.suc;
            pos = pos.pred;
         }
         else pos = pos.suc;
      }
   }

//////////////////////////////////////////////////////////////////////////
// OPPGAVE 2

   // MAW 3.2 a
   // Oppgaven blir enklere hvis vi forutsetter at vi har et listehode
   // Hvis ikke, m? vi behandle bytte av de to f?rste i listen s?rskilt
   // Forutsetter at pos peker p? noden f?r de to som skal byttes

   void bytt1()
   {  if (pos != null && pos.neste != null && pos.neste.neste != null)
      {  Node nynabo = pos.neste.neste;
         pos.neste.neste = nynabo.neste;
         nynabo.neste = pos.neste;
         pos.neste = nynabo;
      }
   }

   // MAW 3.2 b
   // Forutsetter at pos peker p? den f?rste av de to som skal byttes

   void bytt2()
   {  if (pos != null && pos.suc != null)
      {  Node nypos = pos.suc;
         if (pos.pred  != null) pos.pred.suc = nypos;
         if (nypos.suc != null) nypos.suc.pred = pos;
         pos.suc = nypos.suc;
         nypos.suc = pos;
         nypos.pred = pos.pred;
         pos.pred = nypos;
         pos = nypos;     // Hvis pos fortsatt skal peke p? den f?rste
      }
   }

   // MAW 3.17
   // Det er noe uklart hva svaret p? oppgave a er tenkt ? v?re.
   // Antakelig ved ? benytte en ekstra peker i hver node.
   // Her l?ses bare oppgave b
   // Forutsetter at variabelen liste peker p? f?rste element

   void reverser()
   {  Node nyListe = null;
      // L?kkens invariant:
      //   nyListe er starten av venstre del som er reversert
      //   liste er starten av h?yre del som enn? ikke er reversert
      // Her kan det v?re instruktivt ? gjennomf?re et "bevis":
      //   invarianten gjelder initielt,
      //   invarianten bevares ved et l?kkeoml?p
      //   det er progress
      //   invariant & liste == null  ==> lista reversert
      while (liste != null)
      {  Node denne = liste;
         liste = liste.neste;
         denne.neste = nyListe;
         nyListe = denne;
      }
      liste = nyListe;
   }

   // MAW 3.35
   // Det er igjen noe uklart hva svaret p? oppgave a er tenkt ? v?re.
   // Antakelig ? benytte en boolean beenHere.
   //   Initielt false i alle noder 
   //   Settes true mens vi g?r.
   // Her f?lger en l?sning p? oppgave b:
   boolean sykelfri(Node liste)
   {  Node p1 = liste; // langsom peker
      Node p2 = liste; // dobbelt s? rask peker
      while (true)
      {  if (p2 == null) return true;
         p2 = p2.neste;
         if (p1 == p2) return false;
         if (p2 == null) return true;
         p1 = p1.neste;
         p2 = p2.neste;
         if (p1 == p2) return false;
       }
   } 
   // Begrunnelse for at metoden terminerer:
   //   Hvis listen er sykelfri, vil p2 n? slutten og bli null.
   //   Hvis listen har en sykel, vil p1 komme inn i den. Deretter
   //   vil p2 jage p1 ved at avstanden mellom dem avtar med 1 for 
   //   hvert gjennoml?p av while-l?kken. Idet p2 tar igjen p1, er 
   //   en sykel p?vist.

//////////////////////////////////////////////////////////////////////////
// OPPGAVE 3 og 4

import java.util.Random;

public class Dekl
{ static Random r=new Random();
  static int deklNo;
  String navn;
  Dekl neste;
  Dekl lokale;

  // Generer tilfeldig en nestet deklarasjon.
  //   p i (0, 1]. H?y p, ?kt sjanse for indre klasser.
  Dekl(boolean cl, Dekl neste, double p) {
    this.neste=neste;
    if (cl) {
      navn = "Cl"+deklNo++;
      while (true) {
        double ra=r.nextFloat()*p;
        if (ra<0.2) break;
        lokale=new Dekl(ra>0.6, lokale, p*0.9);
      }
    } else {
      navn = "int"+deklNo++;
    }
  }
}
//////////////////////////

public class Stakk {
  private Object [] stakk;
  private int topp;

  public Stakk(int kapasitet) {
    stakk = new Object[kapasitet];
    topp = -1;
  }

  public boolean isEmpty() {
    return topp==-1;
  }

  public Object top() {
    if(isEmpty()) return null;
    return stakk[topp];
  }

  public Object topAndPop() {
    if(isEmpty()) return null;
    return stakk[topp--];
  }

  public void push(Object o) {
  // Litt slapt. Overfull stakk gir ArrayIndexOutOfBoundsException
    stakk[++topp]=o; 
  }
}
//////////////////////////

public class SkrivProg {
  static Dekl ma;
  static String indent="                                                    ";
  static int ind=0; // kontroll av identering

  static void skrivProg1(Dekl liste) {
    Dekl denne= liste;
    while (denne != null) {
      System.out.print(denne.navn + " ");
// Dersom en klasse skal kunne ha ingen deklarasjoner, f?r vi anta at
//   utseende av 'denne.navn' skiller.
      if (denne.lokale != null) {
        System.out.println("(");
        ind+=2;
        System.out.print(indent.substring(0, ind));
        skrivProg1(denne.lokale);
        System.out.println(")");
        ind-=2;
        System.out.print(indent.substring(0, ind));
      }
      denne = denne.neste;
    }
  } 

static void skrivProg2(Dekl liste) {
  Stakk s = new Stakk(100);
  Dekl denne= liste;
  while (denne != null || !s.isEmpty()) {
    if (denne == null) {
      // Er p? slutten av en liste, skal tilbake til forrige
      System.out.println(")");
      ind-=2;
      System.out.print(indent.substring(0, ind));
      denne = ((Dekl)s.topAndPop()).neste;
    } else {
      System.out.print(denne.navn + " ");
      if (denne.lokale != null) {
        System.out.println("(");
        ind+=2;
        System.out.print(indent.substring(0, ind));
        s.push(denne);
        denne = denne.lokale;
      } else {
        denne = denne.neste;
      }
    }
  }
}

  public static void main(String[] args) {
    System.out.println(" ");
    System.out.println("Start rekursive ****** ");
	ma = new Dekl(true, null, 1.0);
    skrivProg1(ma);
	System.out.println("Start stakk ****** ");
    skrivProg2(ma);	
  }
}

//////////////////////////////////////////////////////////////////////////
// OPPGAVE 5

public class SjekkProg {
  static String prog="as{h,{{((j(hj)));{h;;j(j(jj)k);}b;;n}b;};}n";
  static int inp=0;

private static String nesteSymb() {
  if (inp>=prog.length()) return "EOF";
  else return prog.substring(inp, ++inp);
}

static boolean sjekkProg() {
  boolean res=true;
  Stakk s = new Stakk(100);
  String symbol = nesteSymb();
  while (!symbol.equals("EOF")) {
    System.out.print(symbol);
    if (symbol.equals("{")) {
      /*
       * Kr?llparenteser m? ikke komme inne i vanlige parenteser.
       * Venstre kr?llparentes m? kunne parres med en h?yre 
       * kr?llparentes, og pushes derfor p? stakken.
       */
      if (s.isEmpty() || !s.top().equals("(")) {
        s.push(symbol);
      } else {
        System.out.println("****Feil i posisjon="+inp+": "+" { etter (");
        res=false;
      }
    } else if (symbol.equals("(")) {
      /* Venstreparentes m? parres med en h?yreparentes */
      s.push(symbol);
    } else if (symbol.equals("}")) {
      /* 
       * H?yre kr?llparentes m? parres med en venstre kr?llparentes som
       * n? ligger ?verst p? stakken.
       */
      if (s.isEmpty()) {
        System.out.println("****Feil i posisjon="+inp+": "+" } finner ikke {");
        res=false;
      } else if (!s.topAndPop().equals("{")) {
        System.out.println("****Feil i posisjon="+inp+": "+" } finner ikke {");
        res=false;
      }
    } else if (symbol.equals(")")) {
      /* H?yreparentes m? parres med venstreparentes ?verst p? stakken */
      if (s.isEmpty()) {
        System.out.println("****Feil i posisjon="+inp+": "+" ) finner ikke (");
        res=false;
      } else if (!s.topAndPop().equals("(")) {
        res=false;
        System.out.println("****Feil i posisjon="+inp+": "+" ) finner ikke (");
      }
    } else if (symbol.equals(";")) {
      /* Semikolon skal ikke forekomme inne i vanlige parenteser */
      if (!s.isEmpty() && s.top().equals("(")) {
        System.out.println("****Feil i posisjon="+inp+": "+" ; etter (");
        res=false;
      }
    }
    symbol = nesteSymb();
  }

  /*
   * Hele programkoden er n? lest. Hvis det fortsatt ligger noe p? stakken,
   * er dette venstre (kr?ll-)parenteser som ikke har f?tt den n?dvendige
   * h?yre (kr?ll-)parentesen, og programmet er ikke syntaktisk korrekt.
   */
  while (!s.isEmpty()) {
    System.out.println("****Feil til slutt: "+s.topAndPop()+" mangler partner.");
    res=false;
  }
  return res;
}

  public static void main(String[] args) {
    System.out.println("Start SjekkProg ****** ");
    if (SjekkProg.sjekkProg())
      System.out.println("\nProg OK ****** ");
    else
      System.out.println("\nProg inneholder feil ****** ");
  }
}

//////////////////////////////////////////////////////////////////////////
// OPPGAVE 6

class SpringerVei{
    int[] isteg;
    int[] jsteg;
    boolean[][] brukt;
    int n;

    public void skrivSpringerVei(int n1, int i, int j) {
      n = n1;
      isteg = new int[n*n];
      jsteg = new int[n*n];
      brukt = new boolean[n][n];
      for (int k = 0; k < n; k++) {
        for (int l = 0; l < n; l++) {
          brukt[k][l] = false;
        }
      }
      let_fra(i, j, 0);
      System.out.println("Dessverre, ingen vei funnet!");
    }

    public void let_fra(int i, int j, int nr) {
    // Innenfor brettet:
    if ((0 <= i && i <= n - 1 && 0 <= j && j <= n - 1) &&
        // Ingen rute to ganger:
        (! brukt[i][j])) {

        isteg[nr] = i;
        jsteg[nr] = j;
        if (nr == (n * n) - 1) {
          System.out.println("Vei funnet: ");
          for (int k = 0; k < n * n; k++) {
            System.out.print("  " + isteg[k] + "," + jsteg[k]);
            if ((k+1)%n == 0) System.out.println("  ");
          }
          System.exit(0);
        } else {
          brukt[i][j] = true;
          let_fra(i + 1, j + 2, nr + 1);
          let_fra(i + 1, j - 2, nr + 1);
          let_fra(i - 1, j + 2, nr + 1);
          let_fra(i - 1, j - 2, nr + 1);
          let_fra(i + 2, j + 1, nr + 1);
          let_fra(i + 2, j - 1, nr + 1);
          let_fra(i - 2, j + 1, nr + 1);
          let_fra(i - 2, j - 1, nr + 1);
          brukt[i][j] = false;
        }
      }
    }

    public static void main(String[] args) {
      SpringerVei s = new SpringerVei();         
      s.skrivSpringerVei(Integer.parseInt(args[0]),
               Integer.parseInt(args[1]),
               Integer.parseInt(args[2]));
    }
}