//
// Voorbeelduitwerking oefenopgave G tweede ronde NIO 1998
// =======================================================
//
// Pieter-Tjerk de Boer, ptdeboer@cs.utwente.nl
// (faculteit Informatica, Universiteit Twente)
//
// Taal: C++, hoewel ik de '++' alleen maar gebruik voor input/output en
//       commentaar.
//
// Algoritme: backtracking, waarmee in principe alle mogelijke zetten
//            worden doorzocht.
//
// Opmerking: ik weet niet of dit programma het altijd haalt binnen de
//            gestelde tijdslimiet.
//


#include <stdio.h>
#include <fstream.h>
#include <string.h>



#define maxringen 7      // maximum aantal ringen per pin
#define maxpinnen 9      // maximum aantal mogelijke kleuren, tevens maximum
			 // aantal mogelijke pinnen



typedef struct {         // een structuur die de gegevens van 1 ring bevat
  char kleur;            // - de kleur van de ring, als 1 letter
  char nr;               // - nummer van de ring, ook 1 character (een cijfer)
} Ring;

typedef struct {         // structuur die 1 pin beschrijft:
  int n;                 // - aantal ringen op deze pin
  Ring r[maxringen+1];   // - van elke ring de details; r[0] bevat de kleur
         		 //   (en het nummer 0) van de pin zelf.
} Pin;	


typedef struct {         // structuur die 1 zet beschrijft:
  int aant;              // - aantal te verplaatsen ringen (1 of 2)
  int van;               // - nummer van de pin waar ze vanaf gaan
  int naar;              // - nummer van de pin waar ze naartoe gaan
} Zet;


ifstream inp("TOWER.IN");     // uit deze file komt de input
ofstream outp("SNELST.UIT");  // en naar deze gaat de output

int aantpinnen=0;        // aantal pinnen (= aantal kleuren) dat we hebben
Pin pin[maxpinnen];      // een array met de gegevens van alle pinnen



void init(void)          // lees inputfile
{
  char s[80];            // string voor in te lezen regel
  char *t;               // pointer daarin om die regel te interpreteren
  Pin *p;                // pointer naar gegevens van 'huidige' pin

  while (aantpinnen<maxpinnen) { // doe voor alle pinnen...
    inp >> s;                    //   lees 1 regel, met gegevens van 1 pin
    if (strlen(s)<2) break;      //   te kort? dan einde van input.
    p=pin+aantpinnen;            
    p->n=0;                     
    p->r[0].kleur=s[0];          
    p->r[0].nr=s[1];
    t=s+2;
    while (*t>='A') {            //   doe voor alle ringen op die pin
      p->n++;
      p->r[p->n].kleur=*t;
      p->r[p->n].nr=t[1];
      t+=2;
    }
    aantpinnen++;
  }
}


int klaar(void)              // test of toestand in array pin eindtoestand is
{
  Pin *p;
  p=pin;
  for (int i=0;i<aantpinnen;i++) {   // voor alle pinnen
    for (int j=1;j<=p->n;j++)        // voor alle ringen op die pin
      if (p->r[j].kleur!=p->r[0].kleur) return 0;  // kleur fout? dan geen
    p++;                                           //            eindtoestand
  }
  return 1;      // geen fout gekleurde ringen gevonden? dan wel eindtoestand
}


int telpin(int pinnr)
{
  int i,n;
  Pin *p;

  n=0;
  p=pin+pinnr;

  for (i=0;i<p->n;i++)
    if (p->r[i].kleur==p->r[0].kleur) n++;

  return n;
}


int geldig(Zet *zet)         // test of zet geldig is
{
  Pin *pvan;   // pointer naar pin zet->van
  Pin *pnaar;   // pointer naar pin zet->naar

  // 1e voorwaarde: er moeten genoeg ringen op de pin zet->van zitten:

  pvan = pin + zet->van;
  if (pvan->n < zet->aant) return 0;  

  // 2e voorwaarde: op pin zet->aant moeten nog genoeg ringen passen:

  pnaar = pin + zet->naar;
  if (pnaar->n + zet->aant > maxringen) return 0;

  // 3e voorwaarde: de onderste van de te verplaatsen ringen moet dezelfde
  // kleur hebben als de ring die nu bovenaan de pin zet->naar ligt:

  if ( pvan->r[pvan->n+1-zet->aant].kleur
       != pnaar->r[pnaar->n].kleur )  return 0;

  // aan alle voorwaarden voldaan? Dan is het een geldige zet:
  return 1;
}


int retour(Zet *z1,Zet *z2)    // test of z1 precies het omgekeerde van z2 is
{
  return     z1->van == z2->naar
	  && z1->naar == z2->van
          && z1->aant == z2->aant ;
}


void doezet(Zet *zet)        // voer de zet uit
{
  Pin *pvan = pin + zet->van;     // pointer naar pin zet->van
  Pin *pnaar = pin + zet->naar;   // pointer naar pin zet->naar

  pvan->n -= zet->aant;
  pnaar->r[pnaar->n+1] = pvan->r[pvan->n+1];    // gegevens van 1 ring kopieren
  if (zet->aant>1)                              // als aant 2 is:
     pnaar->r[pnaar->n+2] = pvan->r[pvan->n+2]; //   gegevens 2e ring kopieren
  pnaar->n += zet->aant;
}


void printzet(Zet *zet)      // print 1 zet in het formaat zoals gegeven
			     // in de opgave:
{
  Pin *pvan = pin + zet->van;     // pointer naar pin zet->van
  Pin *pnaar = pin + zet->naar;   // pointer naar pin zet->naar

  outp << pvan->r[pvan->n].kleur << pvan->r[pvan->n].nr;

  if (zet->aant==2)
    outp << pvan->r[pvan->n-1].kleur << pvan->r[pvan->n-1].nr;

  outp << pnaar->r[pnaar->n].kleur << pnaar->r[pnaar->n].nr << '\n';
}




#define maxzet 12       // maximum aantal toegestane zetten.

Zet reeks[maxzet];      // in dit array houden we onze zetten tot nu toe bij.

Zet bestreeks[maxzet];  // en hierin de reeks zetten van de snelste oplossing
			// tot nu toe.

int bestaant=maxzet+1;  // het aantal zetten voor die snelste oplossing tot
			// nu toe.

// de volgende functie doorzoekt recursief alle mogelijke zetten.
// bij aanroep: array pin[] bevat verdeling van ringen over pinnen.
//              diep = aantal stappen dat we hiervoor al hebben gedaan.
//              reeks, bestreeks, bestaant: zoals hierboven vermeld.

void recur(int diep)
{
  Zet *z;                 // wijst naar actuele zet in array reeks[]
  Pin origpin[maxpinnen]; // kopie van beginverdeling ringen over pinnen

  if (diep>=bestaant-1) return;     // zijn we al te diep? dan niet verder gaan.

  memcpy(origpin,pin,sizeof(pin));  // oorspronkelijke toestand onthouden

  z=reeks+diep;                     // z-pointer waarde geven

  // lus over alle mogelijke zetten:

  for (z->van=0 ; z->van<maxpinnen ; z->van++) {

    for (z->naar=0 ; z->naar<maxpinnen ; z->naar++) {
      if (z->van!=z->naar) {

	for (z->aant=1 ; z->aant<=2 ; z->aant++) {
	  if (geldig(z) && !retour(z,&reeks[diep-1])) {

  // dit stukje wordt dus voor alle mogelijke en zinvolle (niet retour)
  // zetten uitgevoerd:

	    doezet(z);                  // doe de zet
	    if (klaar()) {              // eindtoestand bereikt?
              bestaant=diep+1;          // zo ja, dan gegevens opslaan
              memcpy(bestreeks,reeks,sizeof(reeks));
	      return;                   // en terug naar vorig niveau
	    }
	    recur(diep+1);              // test (recursief!) alle verdere 
					// ("diepere") zetten
	    memcpy(pin,origpin,sizeof(pin)); // herstel oorspronkelijke
					     // toestand
	  }
        }

      }
    }

  }
}


int main(void)
{
  init();                            // lees de inputfile in

  recur(0);                          // doe de recursie

  if (bestaant>maxzet) outp << "-1\n";  // niets gevonden? dan -1 als output
  else {                             // anders:
    outp << bestaant << '\n';        // aantal printen
    for (int i=0;i<bestaant;i++) {   // stappen printen
      printzet(bestreeks+i);
      doezet(bestreeks+i);
    }
  }

  return 0;
}