Tävlingsprogrammering/Uppgifter/Pyramiden
Pyramiden
I ett klassiskt dataspel ska man styra en liten varelse som hoppar omkring på en pyramid (se figur ovan). Varelsen kan hoppa till “trappstegen” direkt ovanför eller under honom. Det är förstås inte tillåtet att hoppa utanför pyramiden. När varelsen landar på ett trappsteg byter steget färg; från röd till gul, gul till blå eller blå till röd. Skriv ett program som läser in hur trappstegen på pyramiden är färgade vid starttillfället och skriver ut en hoppsekvens på max 5000 hopp som färgar om alla trappsteg till blåa. Du får starta på vilket trappsteg du vill i pyramiden (detta garanterar att en lösning alltid finns). Det första trappsteg som ändrar färg är det som nås efter första hoppet från starttrappsteget.
Första raden i pyramid.dat består av ett heltal: pyramidens höjd (2 ≤ n ≤ 40). Därefter följer n rader som beskriver hur pyramiden är färgad vid starttillfället, uppifrån och ner. Bokstäverna ’R’ (röd), ’G’ (gul) och ’B’ (blå) används för att beskriva trappstegen. Åtminstone ett trappsteg är inte blått från början.
Programmet ska skriva ut två rader. Den första raden ska innehålla två heltal: raden (där 1 är översta raden) och kolumnen (där 1 är kolumnen längst till vänster) som varel- sen ska börja hoppa ifrån. Den andra raden ska bestå av en sträng (max 5000 tecken) som beskriver en hoppsekvens. Tecknen för att beskriva hoppen ska vara ’7’ (uppåt- vänster), ’9’ (uppåt-höger), ’1’ (nedåt-vänster) eller ’3’ (nedåt-höger).
Notera att ditt program inte behöver hitta den kortaste hoppsekvensen som färgar pyramiden blå; vilken sekvens som helst med högst 5000 hopp är godkänd.
Exempel: Filen pyramid.dat med innehållet
4 B RG BGR GBRB
kan exempelvis ge svaret
3 1 193919193919373737717191991919373737
Lösning[redigera]
I det här problemet gäller det att inse att man inte alls behöver testa alla varianter, utan man kan helt enkelt (linjärt) arbeta sig upp från botten till toppen genom att hoppa fram och tillbaka på en och samma ruta tills den blir blå, för att sedan flytta till nästa, i ett sicksack-format mönster. Faktum är att om man studerar output i programexemplet finner man att exakt denna metoden används även där! Sedan får man vara försiktig, för det räcker inte att gå till toppen och se om det fungerar, eftersom slumpen (uppgiftsdesignern) avgör om den kommer att bli blå vid det tillfället. För att få det att fungera optimalt måste man testa alla möjliga startpositioner för figuren. En annan optimering man kan göra är att bädda in slut-checken i hopp-functionen, eftersom man då kan täcka även draget före man hoppar till sista, vilket faktiskt dubblar sannolikheten att få rätt på en specifik runda. Här följer ett programexempel i C++ som gör just det:
#include <iostream> #include <fstream> #include <algorithm> #include <string> #include <vector> using namespace std; //*** Declarations *** class Pyramiden{ private: string gostr; //The output string vector<vector<int> > br; //The tiles int x,y; //Current position of the figure int stX,stY; //Startposition of ditto int w; //The height/width int numBlue; //Number of blue tiles now int endBlue; //Number of tiles totally (number of tiles that must be blue) Pyramiden(){} //Hide the constructor from global use (only the // singelton-function can construct a game-solver) void init(const std::string& file); void go(char dir); void tryRun(); void win(); void lose(); public: static Pyramiden* getSingelton(); void run(const std::string& file); }; //*** Implementations *** //Function returning the singelton (there is only one program, right?) Pyramiden* Pyramiden::getSingelton(){ static Pyramiden obj; //Initiate on first call (ignore destruction issues) return &obj; } //Function called at win. void Pyramiden::win(){ cout << stY+1 << ' ' << stX+1 << '\n' << gostr << endl; throw true; } //Failure function. //Hopefully never called (at least it wasn't called in the test cases). void Pyramiden::lose(){ cout << "FAILURE" << endl; } //Let the figure jump in selected direction. //May throw exceptions regarding win/lose and out-of-range (without roll-back) void Pyramiden::go(char dir){ gostr+=dir; if(gostr.size()>=5000)throw false; if(dir>='7')--y; //A bit wierd, but works with the internal format else ++y; if(dir=='7')--x; else if(dir=='3')++x; ++br.at(y).at(x); //Change the color of the designated tile if(br[y][x]==1){ //If it was blue before, but not now, --numBlue; //decrement the number of blue tiles } if(br[y][x]==3){ //If it is going "overflow" and becoming blue again, br[y][x]=0; //make it blue and check for win ++numBlue; // (of course increment the number of blue tiles) if(numBlue==endBlue)win(); } } //Initiate a test-case. That is, load the pyramid and set some used variables. void Pyramiden::init(const std::string& file){ gostr.reserve(5000); char ch; numBlue=endBlue=0; ifstream fin(file.c_str()); fin >> w; br.resize(w); for(int i=0;i<w;++i){ br[i].resize(i+1); for(int j=0;j<=i;++j){ fin >> ch; //0->blue, 1->red, 2->yellow br[i][j]=((ch=='B')?0:((ch=='R')?1:2)); if(ch=='B')++numBlue; ++endBlue; } } } //Try to run the test-case with a certain startposition void Pyramiden::tryRun(){ //Run to the down-left if not there already while(x || y!=w-1){ if(y==w-1)go('7'); else go('1'); } //Then while not finished running up the pyramid... while(y){ bool way=(((w-y)%2)==1); //1->right 0->left int end=(way?y:0); //First ones: Go to the right/left by going 91/73 until the tile is blue // and then moving to the next one by 93/71 while(x!=end){ while(br[y][x]){ if(way){go('9');go('1');} else{go('7');go('3');} } if(way){go('9');go('3');} else{go('7');go('1');} } //Then handle x equals end (must jump in reverse direction) while(br[y][x]){ if(way){go('7');go('3');} else{go('9');go('1');} } //Finally, go up if(way)go('7'); else go('9'); } //At this point, the problem should be solved in 2/3 of the cases. //Propagate if not (actually just to be consistant). throw false; } //Run a test-case. Much like a main()-function. void Pyramiden::run(const std::string& file){ init(file); vector<vector<int> > br_copy; //Save the original data br_copy.swap(br); int numBlue_copy=numBlue; for(int i=0;i<(w*2)-1;++i){ try{ br=br_copy; numBlue=numBlue_copy; gostr.clear(); //Reset data y=stY=w-1-(i%2); //Use a new start position... x=stX=i/2; tryRun(); //...and try running! } catch(bool ok){ //The results are propagated through exceptions (mere if(ok)return; //return values would require an awful lot of checking) } } // If we can't win in any way we call this slightly depressing function. // It will hopefully never get to this (actually it might, with a board // consisting only of one tile). lose(); } //*** Main function *** int main(){ //Run the program, through the singelton. Pyramiden::getSingelton()->run("pyramid.dat"); return 0; }
Här nedan följer ett lösningsexempel i Java. Exemplet löser problemet på så sätt att man börjar på en ruta, hoppar från den rutan till rutan näst längst ner längst till vänster (där qBert står i bilden i uppgiftstexten) och sedan arbetar sig uppåt från botten genom att hoppa på en ruta tills den blir blå och sedan zick-zacka sig till höger. Sedan när man kommit till den sista rutan så finns det tre möjligheter: rutan är blå, rutan är röd, rutan är gul. Om rutan ä blå är vi klara, om rutan är röd så kan vi lösa det hela genom att utföra en viss hoppsekvens (som programmeraren till detta exempel funderat ut med papper och penna), men om rutan är gul så har vi misslyckats.
Vad gör vi då om den sista rutan är gul? Ja då får vi helt enkelt börja om. Då börjar vi på samma ruta, men istället för att hoppa till rutan näst längst ner längst till vänster, så hoppar vi till rutan näst längst ner längst till höger och zick-zackar oss åt vänster för att sedan arbeta oss uppåt systematiskt. Vad om vi inte heller lyckas denna gång? Ja då testar vi bara en annan startruta och sedan återupprepar ovanstående två processer.
Sedan har det i exemplet lagts till en liten kontrollcheck på slutet för att försäkra oss om att hela pyramiden faktiskt är blå.
import java.util.*;
import java.io.*;
public class Pyramiden
{
//En char-array som beskriver vå pyramid.
static char [][] pyramid;
//En backup kopia av vår ursprungliga pyramid. (Innan vi börjat hoppa.)
static char [][] backup;
//Sparar hoppsekvensen.
static String sequence = "";
//Startkoordinater.
static int startX, startY;
//Pyramidens höjd.
static int height;
//Hur många hopp vi hoppat.
static int antal = 0;
//Våra nuvarande koordinater i pyramiden.
static int x, y;
//Ändrar färg på vår nuvarande ruta.
public static void change()
{
if(pyramid[y][x]=='R') pyramid[y][x] = 'G';
else if(pyramid[y][x]=='G') pyramid[y][x] = 'B';
else pyramid[y][x] = 'R';
}
//Går ett steg i specifierad riktning.
//right: Höger, dvs ett hopp snett-höger ner och sedan ett snett-höger upp.
//Om right==false, dvs left, så sker motsvarande fast för vänster.
public static void proceed(boolean right)
{
if(right)
{
jump(3);
jump(9);
}
else
{
jump(1);
jump(7);
}
}
//Hoppar från vår nuvarande ruta på det specifierade sättet.
//1 = nedåt vänster, 3 = nedåt höger, 7 = uppåt vänster, 9 = uppåt höger.
public static void jump(int how)
{
if(how==1)
{
y++; //Vi går ned en rad.
change(); //Byter färg.
sequence += "1"; //Registrerar hoppet.
}
else if(how==3)
{
x++; y++;
change();
sequence += "3";
}
else if(how==7)
{
x--; y--;
change();
sequence += "7";
}
else
{
y--;
change();
sequence += "9";
}
antal++; //Ett hopp har gjorts.
}
//Utför den hoppsekvens som anges av strängen.
public static void jumpSequence(String s)
{
//Går igenom varje tal i strängen.
for(int i = 0; i<s.length(); i++)
{
//Gör om det till en int och hoppar.
jump( Integer.parseInt(""+s.charAt(i)) );
}
}
//Metod som hoppar till en ruta tills den är blå.
//left: Om det är rutan snett-nedåt till vänster vi ska hoppa på.
//Annars är det rutan snett-nedåt till höger som hoppas på.
public static void makeBlue(boolean left)
{
if(left) //Om vänster.
{
//Så länge rutan inte är blå.
while(pyramid[y+1][x]!='B')
{
jump(1); //Hoppar till rutan.
jump(9); //Hoppar tillbaka.
}
}
else //Om höger.
{
while(pyramid[y+1][x+1]!='B')
{
jump(3);
jump(7);
}
}
}
//Hoppar till en angiven ruta i en lämplig sekvens av hopp.
public static void jumpTo(int toX, int toY)
{
while(true)
{
//Vi är klara,
if(x==toX && y==toY) break;
//Om vi står över rutan vi ska till hoppar vi nedåt.
//Om vi står under hoppar vi uppåt.
if(y<toY) jump(1);
else if(y>toY) jump(9);
//Om vi är till höger om målrutan hoppar vi vänster.
//Om vi är till vänster hoppar vi höger.
if(x>toX) proceed(false);
else if(x<toX) proceed(true);
}
}
//Försöker lösa uppgiften.
//useX, useY: Rutan ifrån vilken vi ska börja zick-zack hoppa.
//how: Om vi ska börja zick-zacka åt höger. (Annars vänster.)
public static boolean solve(int useX, int useY, boolean how)
{
//Först hoppar vi till den angivna rutan.
jumpTo(useX, useY);
//Anger riktningen vi zickzackar i. (true=höger)
boolean mode = how;
//Vilken rad vi är på, samt största index för nuvarande rad.
int row = y;
//Nu kör vi.
while(true)
{
//Om vi kommit till översta rutan.
if(y==0)
{
//Gör rutan till vänster blå.
makeBlue(true);
//Gör rutan till höger blå.
makeBlue(false);
//För många hopp är inte tillåtet.
if(antal>5000) return false;
//Om sista rutan är blå, så är vi klara.
if(pyramid[0][0]=='B')
{
return true;
}
else if(pyramid[0][0]=='R')
{
//Om den är röd, så kan vi utföra följande hoppsekvens för att lösa pusslet.
jumpSequence("37193719371");
return true;
}
else //Annars har vi misslyckats.
{
return false;
}
}
else //Zickzackar som vanligt.
{
//Hoppar på rutan under oss tills den bli blå.
//Om vi går åt höger, så är det den under till vänster som gäller.
makeBlue(mode);
//Ifall vi går åt höger och kommit till sista rutan.
if(x==row && mode)
{
//Då ska vi börja gå åt vänster snart.
mode = false;
//Gör rutan nedåt höger till blå.
makeBlue(mode);
//Hoppar uppåt till nästa rad.
jump(7);
//Nästa rad har en färre ruta i sidled.
row--;
}
else if(x==0 && !mode) //Ifall vi går åt vänster och kommit till "sista rutan".
{
//Då ska vi börja gå åt höger snart.
mode = true;
//Gör rutan nedåt till vänster blå.
makeBlue(mode);
//Hoppar upp en rad.
jump(9);
//Denna rad har en mindre ruta i sidled.
row--;
}
else //Annars gör vi hoppen som tar oss en ruta i sidled.
{
proceed(mode);
}
}
}
}
//Nollställer.
public static void reset()
{
sequence = "";
antal = 0;
//Återställer pyramiden till sitt ursprungliga skick.
for(int i = 0; i<height; i++)
{
pyramid[i] = Arrays.copyOfRange(backup[i], 0, i+1);
}
}
//Orka fånga exceptions. Vi är lata och säkra på vår sak.
public static void main(String [] klein) throws FileNotFoundException
{
//Vi ska läsa av filen pyramid.dat i mappen/katalogen data.
Scanner scan = new Scanner(new File("data\\pyramid.dat"));
height = scan.nextInt();
//Skapar vår pyramid.
pyramid = new char [height][height];
backup = new char [height][height];
//Läser in pyramiden.
for(int i = 0; i<height; i++)
{
String s = scan.next();
pyramid[i] = s.toCharArray();
backup[i] = s.toCharArray();
}
//Har vi löst pusslet?
boolean solved = false;
//Går igenom pyramiden och testar varje ruta som startruta.
for(int i = 0; i<height; i++)
{
for(int j = 0; j<=i; j++)
{
//Anger starkoordinater.
x = startX = j;
y = startY = i;
//Vi försöker lösa problemet genom att först hoppa till rutan
// näst längst ner längst till vänster och höger zickzacka.
if( solve(0, height-2, true) )
{
solved = true;
break;
}
//Ifall det inte gick måste vi nollställa.
reset();
//Vi försöker lösa problemet genom att först hoppa till rutan
// näst längst ner längst till höger och vänster zickzacka.
if( solve(height-2, height-2, false) )
{
solved = true;
break;
}
//Om det inte gick, nollställ!
reset();
}
//Ifall problemet är löst, avbryt.
if(solved) break;
}
//Skriver ut svaret.
System.out.println((startY+1) + " " + (startX+1) + "\n" + sequence);
/*** Kontrollcheck ***/
System.out.println("\nAntal: " + antal);
for(int i = 0; i<height; i++)
{
for(int j = 0; j<=i; j++) System.out.print(pyramid[i][j]);
System.out.println();
}
/*********************/
}
}