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

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