Tävlingsprogrammering/Uppgifter/Digital Signal Processor
Digital Signal Processor
Anna-Maria tänker bygga ett vindkraftverk, och har uppfunnit en ny sorts processor som hon tänker använda som komponent i vindkraftverkets styrsystem. Processorn är en s.k. DSP, Digital Signal Processor, som bearbetar digitala signaler. I praktiken innebär detta att DSP:n matas med en serie heltal som indata, bearbetar dessa enligt den mjukvara som är inprogrammerad, och producerar en serie heltal som utdata.
Anna-Maria har skickat en beställning till en fabrik som ska producera DSP:n åt henne, men på grund av den ekonomiska krisen drar produktionen ut på tiden. Anna-Maria, som redan har skrivit massor av program till sin DSP, blir lite otålig och vill försäkra sig om att hennes program verkligen kommer fungera på en gång när DSP:erna är klara. Hon ber dig därför skriva ett program som simulerar DSP:ns beteende, så hon kan testa sina program innan DSP:n finns tillgänglig.
Mjukvaran som definierar DSP:ns beteende består av en sekvens av N (upp till 256) maskininstruktioner (även kallade assemblerinstruktioner), numrerade från 0 till N-1. Det finns 7 sorters instruktioner: CONST, ADD, SUB, JNZ, INPUT, OUTPUT och HALT. Varje instruktion har 0-2 parametrar, som var och en är ett heltal 0..255. DSP:n har också ett arbetsminne som består av 256 st register, vart och ett av dessa innehåller en byte (dvs, ett heltal 0..255).
Ett program körs genom att DSP:n börjar exekvera instruktion 0, sedan instruktion 1, o.s.v., tills en HALT-instruktion exekveras, då avslutas programmets körning. När körningen börjar har alla register värdet 0.
Maskininstruktionerna definieras på följande vis:
| CONST x y | Sätt register nr y till värdet x. ([y] = x) |
| ADD x y | Addera värdet i register nr x till register nr y. ([y] = [y] + [x]) |
| SUB x y | Subtrahera värdet i register nr x från värdet i register nr y. ([y] = [y] - [x]) |
| JNZ x y | Jump if Not Zero: Om register nr x inte är 0, "hoppa" till instruktion nr y, dvs låt instruktion y bli nästa instruktion att exekvera. Om register nr x däremot är 0, fortsätt exekveringen som vanligt med instruktionen efter JNZ. |
| INPUT x | Läs in nästa byte från DSP:ns indata, lagra den i register nr x. |
| OUTPUT x | Skicka innehållet i register nr x som utdata från DSP:n. |
| HALT | Avsluta körningen. |
Indata
Indata består av programmet som ska köras på DSP:n, följt av det indata som DSP:n kommer matas med.
På första raden står ett heltal N, 0<N<256, antalet maskininstruktioner i programmet. Därpå följer N rader med instruktioner. Varje instruktion består av instruktionens namn, följt av instruktionens parametrar. Varje parameter beskrivs av ett heltal i intervallet 0..255. Efter de N raderna med maskininstruktioner, följer ett antal tal i intervallet 0..255, ett tal på varje rad. Talen utgör indata till DSP:n, dvs den talserie som DSP-programmets INPUT-instruktioner läser från.
Du kan förutsätta att DSP-programmet och dess indata uppfyller följande:
Ingen ADD-instruktion kommer ge en summa större än 255, och ingen SUB-instruktion kommer ge ett tal mindre än 0 som resultat. Programmet kommer alltid att avslutas korrekt genom att komma fram till en HALT-instruktion. Dvs, programmet kommer inte fastna i en evig loop. Antalet instruktioner som behöver exekveras kommer inte att överstiga en miljon. Det kommer alltid finnas tillräckligt med indata för att räcka till alla INPUT-instruktioner som behöver exekveras. Programmet kommer aldrig försöka exekvera andra instruktioner än nr 0..N-1. Dvs, JNZ kommer aldrig att hoppa till en instruktion >= N, och instruktion nr N-1 kommer alltid antingen vara en HALT-instruktion, eller en JNZ-instruktion som hoppar till en tidigare instruktion. Utdata
Ditt program ska simulera DSP:ns körning av det program som ges av uppgiftens indata, och skriva ut DSP:ns utdata: För varje exekvering av en OUTPUT-instruktion, ska ditt program skriva ut en rad med ett heltal i intervallet 0..255, utdatat som skickas från OUTPUT-instruktionen.
Exempel: Indata
15
INPUT 4
JNZ 4 3
HALT
INPUT 0
INPUT 1
CONST 0 2
JNZ 0 11
OUTPUT 2
CONST 1 0
SUB 0 4
JNZ 0 1
ADD 1 2
CONST 1 3
SUB 3 0
JNZ 3 6
5
1
1
2
2
3
3
4
4
5
6
Exempel: Utdata
1
4
9
16
30
Exempel: Förklaring
Programmet tar ett tal M följt av M par av tal som indata, och skriver ut, för varje par, produkten av de två talen.
Lösning[redigera]
Det här är en simpel simuleringsuppgift som inte har några speciella svårigheter i sig.
#include <stdio.h>
static unsigned char minne[256];
static unsigned char programkod[256][3];
static inline void readbyte(unsigned char* dest){
//Läser in ett tal 0..255 och stoppar in i *dest
int tmp;
scanf("%d", &tmp);
*dest = tmp;
}
int main(){
int N, tmp;
scanf("%d", &N);
for(int i=0; i<N; i++){
//Läs in instruktionerna
//Spara enbart första bokstaven av instruktionen, vilket räcker för att urskilja dem
char instruktion[7];
scanf("%s", instruktion);
programkod[i][0] = instruktion[0];
//Läs in x- och y-variablerna
if (programkod[i][0] == 'O' || programkod[i][0] == 'I'){
//INPUT, OUTPUT
readbyte(&programkod[i][1]);
} else if (programkod[i][0] != 'H'){
//CONST, ADD, SUB, JNZ
readbyte(&programkod[i][1]);
readbyte(&programkod[i][2]);
}
}
//Initiera minnet så att allt är 0
for(int i=0; i<256; i++)
minne[i] = 0;
//Programräknare, vilken den aktuella kodraden är
int pc = 0;
//Själva simuleringen
for(;;){
const unsigned char& x = programkod[pc][1];
const unsigned char& y = programkod[pc][2];
switch(programkod[pc][0]){
case 'C': //CONST x y
minne[y] = x;
pc++;
break;
case 'A': //ADD x y
minne[y] += minne[x];
pc++;
break;
case 'S': //SUB x y
minne[y] -= minne[x];
pc++;
break;
case 'J': //JNZ x y
if (minne[x] != 0)
pc = y;
else
pc++;
break;
case 'I': //INPUT x
readbyte(&minne[x]);
pc++;
break;
case 'O': //OUTPUT x
printf("%d\n", (int)minne[x]);
pc++;
break;
case 'H': //HALT
return 0;
}
}
}
Här följer en lösning (av Anton Fors Hurdén) som översätter DSP-instruktionerna till C-kod, anropar en C-kompilator och till sist anropar det kompilerade programmet, notera att denna lösning inte accepteras av Kattis då den använder det underliggande systemet:
#include <stdio.h>
#include <stdlib.h>
int main() {
FILE *f;
char i, n, x, y, m[8], b[16];
f = fopen("dspp.c", "w");
fputs( "#include <stdio.h>\n"
"#define CONST(x,y) m[y]=x;\n"
"#define ADD(x,y) m[y]+=m[x];\n"
"#define SUB(x,y) m[y]-=m[x];\n"
"#define JNZ(x,y) if(m[x]) goto l##y;\n"
"#define INPUT(x,y) scanf(\"%hhu\",&m[x]);\n"
"#define OUTPUT(x,y) printf(\"%hhu\\n\",m[x]);\n"
"#define HALT(x,y) return 0;\n"
"int main() {\n"
"char m[256]={0};\n", f);
scanf("%hhu\n", &n);
for (i = 0; i < n; i++) {
fgets(b, 16, stdin);
sscanf(b, "%s%hhu%hhu", m, &x, &y);
fprintf(f, "l%hhu: %s(%hhu,%hhu)\n", i, m, x, y);
}
fputs("}\n", f);
fclose(f);
system("clang -O4 -o dspp dspp.c");
system("./dspp");
}
Och ytterligare en lösning i C (av Anton Fors Hurdén), då den första som är listad här vägrar att kompilera i både GCC och Clang:
#include <stdio.h>
int main() {
char i, n, b[16], m[256] = {0}, p[256][3];
scanf("%hhu\n", &n);
for (i = 0; i < n; i++) {
fgets(b, 16, stdin);
sscanf(b, "%c%*s%hhu%hhu", &p[i][0], &p[i][1], &p[i][2]);
}
for (i = 0; p[i][0] != 'H'; (p[i][0] == 'J' && m[p[i][1]]) ? i = p[i][2] : i++) {
switch (p[i][0]) {
case 'C': m[p[i][2]] = p[i][1]; break;
case 'A': m[p[i][2]] += m[p[i][1]]; break;
case 'S': m[p[i][2]] -= m[p[i][1]]; break;
case 'I': scanf("%hhu", &m[p[i][1]]); break;
case 'O': printf("%hhu\n", m[p[i][1]]);
}
}
}
Och här följer en rättfram rekursiv lösning i Haskell (av Anton Fors Hurdén):
import Data.Array.IO
import Control.Monad
x p n = fst (snd (p !! n))
y p n = snd (snd (p !! n))
run m p n = case fst (p !! n) of
"CONST" -> do
writeArray m (y p n) (x p n)
run m p (n + 1)
"ADD" -> do
mx <- readArray m (x p n)
my <- readArray m (y p n)
writeArray m (y p n) (my + mx)
run m p (n + 1)
"SUB" -> do
mx <- readArray m (x p n)
my <- readArray m (y p n)
writeArray m (y p n) (my - mx)
run m p (n + 1)
"JNZ" -> do
mx <- readArray m (x p n)
run m p (if mx /= 0 then y p n else n + 1)
"INPUT" -> do
readLn >>= writeArray m (x p n)
run m p (n + 1)
"OUTPUT" -> do
readArray m (x p n) >>= print
run m p (n + 1)
"HALT" -> return 0
parse [m] = (m, (0, 0))
parse [m, x] = (m, (read x, 0))
parse [m, x, y] = (m, (read x, read y))
main = do
m <- newArray (0, 255) 0 :: IO (IOArray Int Int)
n <- readLn
p <- replicateM n $ getLine >>= return . parse . words
run m p 0
Och en något värdigare Haskell-lösning (av Anton Fors Hurdén):
import Data.Sequence
x p n = fst $ snd $ index p n
y p n = snd $ snd $ index p n
run m p n = case fst (index p n) of
'C' -> run (update (y p n) (x p n) m) p (n + 1)
'A' -> run (adjust (index m (x p n) +) (y p n) m) p (n + 1)
'S' -> run (adjust (subtract $ index m (x p n)) (y p n) m) p (n + 1)
'J' -> run m p (if index m (x p n) == 0 then n + 1 else y p n)
'I' -> readLn >>= (\mx -> run (update (x p n) mx m) p (n + 1))
'O' -> print (index m (x p n)) >> run m p (n + 1)
'H' -> return 0
parse [m] = (head m, (0, 0))
parse [m, x] = (head m, (read x, 0))
parse [m, x, y] = (head m, (read x, read y))
main = do
n <- readLn
p <- replicateM n $ getLine >>= return . parse . words
run (Data.Sequence.replicate 256 0) p 0