Tävlingsprogrammering/Uppgifter/Castlevania
Castlevania
Du spelar Castlevania IV, men du dör hela tiden. För att kunna fortsätta där du dog måste du skriva in en kod varje gång du dött. Det tar tid att skriva in koden, därför bestämmer du dig för att skriva ett program som beräknar det snabbaste sättet att skriva in koden.
Koden i Castlevania skrivs in genom att fylla ett från början blankt 4x4 rutnät med figurer. I en helt separat “räls” med fyra rutor (överst i figuren nedan) väljer man den figur som för tillfället är aktiv, d.v.s. som kan sättas in i rutnätet.
Det finns sålunda tre sorters kommandon:
- Flytta rut-markören i rutnätet ett steg. Markören kan flyttas i alla fyra riktningar. När den går över någon av kanterna går den över till andra sidan.
- Flytta figur-markören i rälsen ett steg. Markören kan flyttas åt höger eller vänster, även denna går över till andra sidan då den går över kanten.
- Placera in den aktiva figuren i rutnätet (på rut-markörens position).
Det finns fyra figurer. De ligger i följande fördefinierade ordning i rälsen: den blanka figuren (_), hjärtat (H), yxan (Y) och svärdet (S). I startläget står rut-markören längst upp till vänster och figur-markören längst till vänster (se figur nedan). Samtliga rutor är blanka.
FIGUR 2. Startläget när man ska börja skriva in koden. Översta raden är figur-markörens räls, nedanför finns 4x4 rutnätet där man ska fylla i koden. Notera de två rundade fyrkanterna som representerar markörerna.
Att för hand fylla i figuren med ovanstående regler är visserligen lätt, men du ska skriva ett program som gör det på så få kommandon som möjligt! Programmet ska fråga efter fyra rader med fyra tecken på varje rad: den kod som ska ifyllas i rutnätet. De möjliga tecknen är: _, H, Y, S. Programmet ska skriva ut det minsta antalet kommandon som behövs för att fylla i koden.
Körningsexempel 1
Rad 1? ____ Rad 2? ____ Rad 3? ____ Rad 4? ___S Minsta antal kommandon: 4
Kommentar: I detta testexempel ska båda markörerna gå över kanten i de möjliga dimensionerna (2 steg för rut- och 1 steg för figurmarkör), samt ett sista kommando för utsättning av svärdet.
Körningsexempel 2
Rad 1? _H__ Rad 2? _Y__ Rad 3? _Y__ Rad 4? _SH_ Minsta antal kommandon: 15
Lösning[redigera]
Den här lösningen kan lösas på (minst) tre olika sätt. Här visas de i ordning från bäst till sämst (tidsmässigt):
- Se vilken ordning man ska lägga ut figurerna för att minimera antal drag.
- Bredden först-sökning (BFS)
- Djupet först-sökning (DFS)
Metod nr 1: Vi kan se att uppgiften går ut på att man ska placera ut de (max) 16 symbolerna i en viss ordning för att minimera antal drag. Det finns 16! olika permutationer, dvs. sätt att placera ut dem på, vilket är alldeles för mycket för att man ska kunna gå igenom en i taget. Det vi däremot kan notera är att när man ska lägga ut nästa symbol kommer fortsättningen inte bero på i vilken ordning de föregående symbolerna lades ut (förutom sista), utan enbart vilka symboler som var utlagda. Om vi kör dynamisk programmering behöver vi alltså gå igenom totalt ca 2^16*16 möjligheter. Dvs 2^20 gånger. Om vi till en början tänker oss en rekursiv funktion ska den ta emot den aktuella ställningen (2^16 olika möjligheter), vilken som var den sista symbolen som lades ut, och returnera det minimala antal drag vi har kvar för att komma till slutet, dvs. när alla symboler är utlagda. Eftersom funktionen enbart kan ha 2^16*16 olika indata kan vi spara svaret tills nästa gång den körs med samma indata. Detta kan dock skrivas iterativt och räknas ut "baklänges", vilket kommer göra programmet aningen snabbare. Det kräver oftast också mindre minne, fast dock inte i det här fallet. 16 bitar av ett tal räcker för att representera en ställning. En bit är satt om symbolen är utlagd, annars ej satt. Körningstiden för nedanstående kod är < 0.03 sekunder för värsta möjliga testdatan på en Intel Core i7 920 3.20 GHz.
#include <cstdio>
#include <cstdlib>
#define NUM_BITS(x) __builtin_popcount(x)
//Representerar en symbol som ska läggas ut, alltså vilken ruta den ska ligga i samt vilken typ det är.
struct Symbol {
int y, x, t;
Symbol(){}
Symbol(int y, int x, int t) : y(y), x(x), t(t) {}
};
//Tabell som håller koll på antalet drag som måste göras för att flytta markören från position a till position b i en dimension.
int Distance[4][4] = {{0, 1, 2, 1}, {1, 0, 1, 2}, {2, 1, 0, 1}, {1, 2, 1, 0}};
Symbol symboler[16];
int N = 0;
int dist[16][16]; //Antal drag som behöver göras från dess att man har lagt ut symbol nr i, tills symbol nr j är utlagd.
unsigned char dp[65536][16]; //Antalet extra drag som behöver göras till dess att man är klar, om första indexet representerar en aktuell ställning, och andra indexet vilken senast utlagda symbolen var.
int main(){
for(int i=0; i<4; i++){
char buffer[5];
printf("Rad %d ? ", i+1);
scanf("%s", buffer);
for(int j=0; j<4; j++) switch(buffer[j]){
case '_': break;
case 'H': symboler[N++] = Symbol(i, j, 1); break;
case 'Y': symboler[N++] = Symbol(i, j, 2); break;
case 'S': symboler[N++] = Symbol(i, j, 3); break;
}
}
if (N == 0){
//Trivialfall
printf("Minsta antal kommandon: 0\n");
exit(0);
}
for(int i=0; i<N; i++) for(int j=0; j<N; j++) if (i != j) {
//Räkna på förhand ut hur många drag som behövs från dess att man har lagt ut symbol nr i, tills symbol nr j är utlagd.
Symbol& s1 = symboler[i];
Symbol& s2 = symboler[j];
dist[i][j] = Distance[s1.y][s2.y] + Distance[s1.x][s2.x] + Distance[s1.t][s2.t] + 1;
}
//Räknar ut "baklänges" vad en rekursiv funktion skulle få för svar
for(int i=N; i-->1;){ //Loopar på intervallet (N, 1]
//Vi har hittills lagt ut i symboler, och ska lägga ut nästa.
for(int j=0; j<(1<<N); j++) if (NUM_BITS(j) == i){
//Loopar över alla möjliga ställningar där vi har i symboler utlagda
for(int l=0; l<N; l++) if (j & (1<<l)){
//Antag att bit nr l var den senast lagda
int best = 100000;
for(int k=0; k<N; k++) if (!(j & (1<<k))){
//Lägg ut symbol nr k om den inte ännu är utlagd
int ny_stallning = j | (1<<k);
int res = dp[ny_stallning][k] + dist[l][k];
if (best > res)
best = res;
}
dp[j][l] = best;
}
}
}
//Vi måste också lägga ut den första biten någonstans, eftersom loopen ovanför inte täcker det.
int best = 100000;
for(int i=0; i<N; i++){
Symbol& s = symboler[i];
int cost = dp[1<<i][i];
cost += Distance[0][s.y] + Distance[0][s.x] + Distance[0][s.t] + 1;
if (best > cost)
best = cost;
}
printf("Minsta antal kommandon: %d\n", best);
}
Metod nr 2: När man har en uppgift som går ut på att man ska räkna ut "minsta antalet drag", och antal möjliga ställningar är ganska begränsade (dvs. ungefär sisådär maximalt 20 miljoner olika möjligheter), ska det direkt plinga en klocka i huvudet som säger "BFS". En ställning representeras av på vilka positioner markörerna är på, samt vilka symboler som hittills är utlagda. Antal möjliga ställningar blir då 4*16*2^16 = 2^22 = 4 194 304. Dessa kan vi gå igenom ganska snabbt. Ett drag är då att antingen flytta övre markören, flytta undre markören, eller lägga ut en symbol. Här är en lösning som kör denna metod:
#include <cstdio>
#include <cstdlib>
#define ANTAL_MOJLIGA_STALLNINGAR 4*16*65536 //Första markören, andra markören, rutorna
//En ställning representerad som 32 bitar.
//Övre markören använder 2 bitar, undre använder 2 för y-värdet och 2 för x-värdet.
//16 bitar går åt till själva rutfältet. Om en bit är satt (1) betyder det att rätt
//objekt är utsatt. Om en bit inte är satt (0) betyder det att det ännu inte ligger
//rätt symbol på den platsen. Rutor som inte ska ha en symbol har redan (1) på sig
//från början.
struct Stallning {
unsigned int m1: 2;
unsigned int m2y: 2;
unsigned int m2x: 2;
unsigned int rutor: 16;
unsigned int padding: 10;
int& get_int(){
return *(int*)this;
}
bool done(){
return rutor == 0xFFFF;
}
void clear(){
get_int() = 0;
}
};
//Array som lagrar minsta antal kommandon för att uppnå en viss ställning
int* minst_antal_kommandon; // int[ANTAL_MOJLIGA_STALLNINGAR]
//BFS-kö
Stallning* queue; // Stallning[ANTAL_MOJLIGA_STALLNINGAR]
Stallning* front;
Stallning* back;
//Lägg till en ställning längst bak i kön, om den inte är besökt tidigare
static void add(Stallning s, int kommandon){
if(minst_antal_kommandon[s.get_int()] == -1){
minst_antal_kommandon[s.get_int()] = kommandon;
*back++ = s;
}
}
//Hjälpfunktion för att ta fram en viss bit givet en position
static int pos(int y, int x){
return 1<<(y*4 + x);
}
//Indatan till programmet, dvs. ställningen som skall uppnås
char map[4][4];
int main(){
//Använd malloc eftersom det är det enda sättet att få minne utan att
//behöva initialiseras till 0 (tidsslösning), då programstacken är för liten
minst_antal_kommandon = (int*)malloc(ANTAL_MOJLIGA_STALLNINGAR*sizeof(int));
queue = (Stallning*)malloc(ANTAL_MOJLIGA_STALLNINGAR*sizeof(Stallning));
front = &queue[0];
back = &queue[1];
//init kommer att placeras längst fram i kön
Stallning& init = *front;
init.clear();
for(int i=0; i<4; i++){
char buffer[5];
printf("Rad %d: ", i+1);
scanf("%s", buffer);
for(int j=0; j<4; j++){
switch(buffer[j]){
case '_': init.rutor |= pos(i, j); break; //Sätt denna ruta som 'klar' om inget behöver läggas ut här
case 'H': map[i][j] = 1; break;
case 'Y': map[i][j] = 2; break;
case 'S': map[i][j] = 3; break;
}
}
}
//Sätt alla ställningar som 'ej besökta'
for(int i=0; i<ANTAL_MOJLIGA_STALLNINGAR; i++) minst_antal_kommandon[i] = -1;
//Startställningen sätter vi till att det krävs minst 0 drag att uppnå denna
minst_antal_kommandon[init.get_int()] = 0;
while(1/*front != back*/){
//Hämta ut den ställning som står först i kön
Stallning s = *front++;
int kommandon = minst_antal_kommandon[s.get_int()];
if (s.done()){
printf("\nMinst antal kommandon: %d\n", kommandon);
break;
}
//Testa att flytta övre markören först till vänster, sedan till höger
//Eftersom det är 2 bitar per positionsvariabel så flippas den automatiskt runt när den går utanför kanten
{
Stallning copy = s;
copy.m1--;
add(copy, kommandon+1);
copy.m1 += 2;
add(copy, kommandon+1);
}
//Testa att flytta undre markören i alla fyra riktningar
{ Stallning copy = s; copy.m2x++; add(copy, kommandon+1); }
{ Stallning copy = s; copy.m2y++; add(copy, kommandon+1); }
{ Stallning copy = s; copy.m2x--; add(copy, kommandon+1); }
{ Stallning copy = s; copy.m2y--; add(copy, kommandon+1); }
//Om vi har övre markören på det objekt som ska läggas ut här, och ifall det behövs, testa att lägga ut objektet
{
Stallning copy = s;
if (copy.m1 == map[copy.m2y][copy.m2x] && (copy.rutor & pos(copy.m2y, copy.m2x)) == 0){
copy.rutor |= pos(copy.m2y, copy.m2x);
add(copy, kommandon+1);
}
}
}
free(minst_antal_kommandon);
free(queue);
}
Metod nr 3: Det stora problemet med DFS är att när man når slutpositionen inte kan vara säker på att man nådde den med så få antal drag som möjligt. Ofta blir det så att man kör om en viss "delväg" flera gånger fast med olika antal drag man hade på starten av den vägen. Det enda man kan göra är att spara, för varje ställning, vilket det hittills bästa hittills antalet drag är. Om man kommer hit med ett sämre hittills antalet drag än tidigare struntar man i att gå vidare. Man vet inte heller direkt hur djupt man ska gå innan man ska ge upp, utan får försöka hitta något teoretiskt max-djup. Det är först när man är klar med hela sökningen man kan få reda på minsta antalet drag som krävdes.
Det går dock att lösa uppgiften med lite klassisk DFS, men för att man ska klara 10 sek gränsen krävs lite optimeringar. En optimering man kan göra är att spara antalet drag som krävts för att nå en viss position (x,y) när symbol-markören står på en viss position och man placerat ut några specifika symboler. Når man den positionen med samma position för symbol-markören och samma "fixade" symboler i gridet och med fler eller lika många drag, så finns det ingen anledning att fortsätta. (I detta läge tog programmet nedan ca 23 sek att exekvera för elakartade testfall.)
Vad som kan vara svårt att inse är att det i vissa fall kan löna sig att spara en ruta (som behöver "fixas") tills senare när man ändå befinner sig på den om det är så att symbol-markören står på en annan symbol än den som rutan kräver. Dock förlorar man inget på att placera ut en symbol om symbol-markören står rätt och man ändå befinner sig på rutan. (I detta läge tog programmet ca 19 sek.)
Vill man starta med en bra undre gräns för när man kan avbryta rekursionen kan man gå igenom rutnätet med 15 drag och sedan fixa den symbol som krävs för respektive ruta (i värsta fall 3 drag, 2 drag att flytta symbol-markören och 1 drag att placera ut symbolen). I lösningen nedan nöjer vi oss dock med att sätta gränsen till det värsta fallet 15 + nr*3 där nr är antalet symboler i gridet vi vill uppnå.
Vad som också kan vara bra att inse är att när vi når en position och har nr symboler kvar att fixa, så är det minimala antalet drag i vilket vi kan "fixa" dessa nr återstående symboler 2*nr-1 stycken (vi står på en av symbolerna som ska fixas, alla kräver symbolen markören står på, och alla ligger i en sammanhängande serie). Att ta detta i beaktade för när man kan avbryta rekursionen snabbade upp programmet nedan avsevärt. (I detta läge tog programmet ca 8 sek.)
Slutligen, cache is king. Bytes må kanske vara lite långsammare att jobba med än ints, men genom att spara antalet drag för en viss position (med viss markör och vissa fixade symboler) i en byte istället för i en int snabbar upp programmet nedan. Varför? Jo för att då kommer mer av den 4-dimensionella arrayen rymmas i cache-minnet, vilket innebär färre cache-missar, vilket gör att vi desto oftare kommer hitta den undansparade positionen (med antalet drag) i det snabba cache-minnet och således slipper processorn att gå ut och hämta in informationen från det långsammare RAM-minnet. (I detta läge tar programmet ca 6 sek. Dator med AMD Turion 2GHz Dual Core och 2GB minne.)
import java.util.*;
public class Castlevania
{
//Minsta antalet drag som krävs.
static byte min;
//Antalet symboler vi har kvar att placera ut.
static byte nr = 0;
//Vilken symbol vår markör för att välja symbol står på.
static int mrk = 0;
//Gridet där vi placerar ut symboler.
static int [][] grid = new int [4][4];
//Gridet som vi vill ha det.
static int [][] goal = new int [4][4];
//[x][y][mrk][bp] = Minsta antalet drag som vi nått positionen (x,y)
//på när symbol-markören står på mrk och vi har fixat de symboler i
//gridet som anges av bitmönstret bp. (Byte-lagring ger time-gain: ~2sek.)
static byte [][][][] mem = new byte [4][4][4][1<<16];
//(x,y) = koordinaten i gridet vi befinner oss på.
//done = antalet gjorda drag.
//bp = 16 bitars bitmönster som beskriver vilka symboler vi har fixat.
// T.ex. beskriver 0100 0100 0011 1000 situationen att vi placerat ut symboler
// på positionerna (1,0), (1,1), (2,2), (3,2) och (0,3).
public static void rek(byte done, int x, int y, int bp)
{
//Ingen idé att fortsätta. Att fixa nr stycken figurer kräver i bästa fall 2*nr-1 drag (Time-gain: ~10sek).
if(done+(2*nr-1)>=min) return;
//Nu är vi klara.
if(nr==0)
{
min = done;
return;
}
//Markören har "gått över kanten".
if(x>3) x = 0;
else if(x<0) x = 3;
if(y>3) y = 0;
else if(y<0) y = 3;
//Har vi lyckats nå denna ruta på färre drag med samma markör och fixade symboler,
//så finns det ingen idé att fortsätta.
if(done>=mem[x][y][mrk][bp]) return;
mem[x][y][mrk][bp] = done;
int bp2 = bp;
//Skiljer sig denna ruta från målet? Om så fallet, så fixar vi den.
if(goal[y][x]!=grid[y][x])
{
//Antalet steg vi måste flytta symbol-markern.
int dist = Math.abs(mrk-goal[y][x]);
//Om vi flyttar marker över kanten, behöver vi bara flytta ett steg.
if(dist==3) dist = 1;
//Dist drag för att flytta symbol-marker, 1 drag för att placera ut symbolen, 1 drag för att gå till nästa ruta.
done += dist+2;
//Spara hur symbol-markern var vi detta läge.
int tmp = mrk;
//Placera ut symbolen på planen och se till att symbol-markern står på rätt symbol.
mrk = grid[y][x] = goal[y][x];
//Nu har vi en färre symbol att placera ut.
nr--;
bp |= 1<<(y*4+x);
//Gå i alla riktningar.
rek(done,x-1,y,bp);
rek(done,x,y-1,bp);
rek(done,x+1,y,bp);
rek(done,x,y+1,bp);
//Återställ.
nr++;
grid[y][x] = 0;
mrk = tmp;
done -= dist+2;
}
//Ibland kan det löna sig att hoppa över en ruta som kan fixas för att fixa den senare.
//Men om markören redan är inställd på rätt symbol för rutan, så finns det ingen anledning
//att hoppa över den. (Time-gain: ~4sek.)
if(mrk==0 || goal[y][x]!=mrk || goal[y][x]==grid[y][x])
{
//Gå i alla riktningar (vilket kräver ett drag).
done++;
rek(done,x-1,y,bp2);
rek(done,x,y-1,bp2);
rek(done,x+1,y,bp2);
rek(done,x,y+1,bp2);
}
}
public static void main(String [] klein)
{
Scanner scan = new Scanner(System.in);
String [] s = new String [4];
//Läser in raderna.
for(int i = 1; i<=4; i++)
{
System.out.print("Rad "+i+" ? ");
s[i-1] = scan.next();
}
//Placerar ut symbolerna på planen som beskriver hur vi vill att det ska bli.
//Samt räknar hur många dessa är.
// 0 = _, 1 = H, 2 = Y, 3 = S.
for(int i = 0; i<4; i++)
for(int j = 0; j<4; j++)
if(s[i].charAt(j)=='H'){ goal[i][j] = 1; nr++; }
else if(s[i].charAt(j)=='Y'){ goal[i][j] = 2; nr++; }
else if(s[i].charAt(j)=='S'){ goal[i][j] = 3; nr++; }
//Triviallösningen. Det krävs max 2 drag att flytta markern till rätt symbol.
//1 drag för att sätta symbolen. Det krävs 15 drag för att besöka alla rutor.
min = (byte)(15+3*nr);
//Initierar alla värden i vår 4-dimensionella array till triviallösningen.
for(int i = 0; i<4; i++)
for(int j = 0; j<4; j++)
for(int p = 0; p<4; p++)
for(int k = 0; k<1<<16; k++)
mem[i][j][p][k] = min;
//Let's brute force. Vi startar med 0 gjorda drag i ruta (0,0) med 0 fixade symboler.
rek((byte)0,0,0,0);
//Eftersom vi hinner förflytta oss en ruta efter det att vi är klara, så är
//minsta antalet drag ett mindre.
min--;
//Skriver ut svaret.
System.out.println("\nMinsta antal kommandon: " + min);
}
}