Robotoptimering

En robot befinner sig i ett $N \times M$ rutnät, där vissa rutor är blockerade så att roboten inte kan gå på rutan. Nu vill hon förflytta sig till en annan ruta, och har bett sin ägare att programmera om henne för det. Denna ägare råkar vara du.

Att överföra robotens programmering från din dator till roboten tar väldigt mycket energi, så du vill göra programmet så litet som möjligt - dvs, använda så få kommandon som du kan. Som bekant ser programmeringsspråket för att programmera en robot ut på följande vis:

forward

Flytta fram roboten ett steg i sin nuvarande riktning.

right

Rotera $90\deg $ medsols.

left

Rotera $90\deg $ motsols.

for X { A1 A2 ... An }

Upprepa kommandona A1, A2, ..., An $X$ gånger.

call X

Hoppa till instruktionen som har label X, och lägg till nuvarande position i anropsstacken.

return

Hoppa till den senast inlagda positionen i anropsstacken, och ta bort den.

gotoblocked X

Hoppa till instruktionen som har label X, om rutan framför roboten inte är fri.

En label har syntaxet labelnamn:, och får enbart bestå av bokstäver. En label får inte vara inuti en loop. Exekveringen startar vid labeln main.

Exempelprogram

walkandreturn:
  for 100 {
    forward
  }
  gotoblocked done
  right
  right
  for 100 {
    forward
  }
done:
  return

main:
  for 100 {
    call walkandreturn
    right
  }

När roboten försöker gå mot rutnätets kant, eller till en ruta som inte är fri, så händer ingenting. När roboten når sin målruta så vinner roboten, oavsett om den kört färdigt eller inte.

Indata

Indatat består av 10 olika rutnät, som du kan ladda ner här http://progolymp.se/uploads/robot.zip. Varje rutnät har följande format:

Den första raden innehåller testfilens namn $X$.

Nästa radinnehåller två heltal $1 \le R \le 1000$ och $1 \le C \le 1000$, antal rader och kolumner i rutnätet.

Varje ruta är en av:

.

fri ruta

#

blockerad ruta

M

rutan roboten ska ta sig till.

<>^v

startruta, där roboten är riktad vänster, höger, upp eller ned beroende på tecken.

Utdata

Ska bestå av ett program på formen beskriven ovan, som tar roboten från startpositionen till slutpositionen. Formatet är fritt, d.v.s. det spelar ingen roll vilken typ av whitespace (radbrytningar eller mellanslag) som åtskiljer de olika kommandona. Observera att { och } ska ha whitespace runt sig.

Verktyg

För att hjälpa dig lösa problemet finns ett Java-program som du kan ladda ner här http://progolymp.se/uploads/robot.jar. Du kan använda kommandot java -cp robot.jar parser.Runner testfall.in < testfall.ans för att köra programmet som finns i filen testfall.ans på rutnätet i filen testfall.in. Programmet kommer berätta om din lösning lyckades.

Om du dessutom vill ha en grafisk illustration av exekveringen kan du köra java -cp robot.jar gui.GuiMain.

Inskickning

Det lättaste sättet att skicka in är att använda Java-verktyget igen. För att göra detta ska utdata för varje testfall robot_XYZ.in sparas i en fil robot_XYZ.ans. Sedan kör du kommandot java -cp robot.jar gen.Submission, i mappen där dina lösningar finns. Detta kommer generera en Python-fil som heter robot.py. Denna kan du sedan skicka in på Kattis (välj språket Python 3).

Poängsättning

Poängsättningen baseras på hur långt ditt program är. Längden är antalet gånger du använder något kommando i språket av de som är listade. Så exempelprogrammet har längd 11. I synnerhet bidrar labels inte till längden.

Antag att din längd på ett testfall är $L$, och att den kortaste längden på ett testfall är $B$. Poängen på testfallet är då

OBS: Din poäng kan komma att ändras på denna uppgift under tävlingens gång, allt eftersom andra skickar in bättre lösningar. I början har vi satt bästa lösning som 2000 kommandon, och kommer då och då ersätta dessa med de bästa inskickningarna och döma om poängen. Poängen är alltså inte slutgiltig förrän vi har dömt om poängen efter tävlingen.