This page is still under construction.

Parts of this page are still being built. What you see may change.

The Magic Word

Time limit1sMemory limit256 MB

Summary
Interpret a spell of up to 200 lines with variables, arrays, jumps, and prints, and reproduce its output.
Level

Medium5 of 10

Topics
Simulation, Implementation
Solved
No attempts yet

Problem

Do not meddle in the affairs of wizards, for they are subtle and quick to anger.

Gildor

Gandalf works with the arcane arts every day in his fight against Sauron. An arrangement of runes can have consequences nobody planned, so he has asked you, one of his followers, to build a system that tells him the outcome of a set of runes before he casts them.

A spell is a series of instructions, one per line. The instructions are written in elvish. Gandalf has written down what they mean.

Power wordTranslationEffect
arth [lbl]regiongoto [lbl]
pen [var1] [var2] [lbl]lessif [var1] < [var2], goto [lbl]
muindor [var1] [var2] [lbl]brotherif [var1] == [var2], goto [lbl]
sad [lbl]placelabel [lbl]
tangado [var]to establishdeclare [var] as an int and set it to 0
ost [var1] [var2]strongholddeclare [var1] as an int array of size [var2]
teithant [string]to writeprint [string] to stdout, followed by a newline
canad [var]to shoutprint [var] to stdout, followed by a newline
anno [var1] [var2]givevar1 := var2
aderthad [var1] [var2]to reunitevar1 := var1 + var2
adlanna [var1] [var2]to slantvar1 := var1 / var2 (integer division)
adlegi [var1] [var2]to releasevar1 := var1 - var2
athrado [var1] [var2]to crossvar1 := var1 * var2
awarthadto abandonexit

A few notes.

  • [var] takes one of three forms.
    1. An integer constant, for example 6. Assigning to an integer constant does nothing, and execution moves on to the next instruction.
    2. A variable declared with tangado, for example shadowfax. Treat it the way an int behaves in C or Java.
    3. An entry of an array declared with ost, for example moria[4]. The index is itself a [var], so indices nest.
  • [string] is a quote-delimited string constant. It holds no quote character and no newline.
  • [lbl] is a label. A label may share its name with a variable, and the two are unrelated. Labels are not declared ahead of time, so it helps to scan the whole spell for labels before you interpret it.
  • After arth, the next instruction interpreted is the one right after the matching sad. An arth may point at a sad that appears later in the spell.
  • sad changes no variable. It only marks a destination for arth, pen, and muindor.
  • ost sets every cell of the new array to 0.
  • Variable names and label names consist of uppercase and lowercase letters only.
  • Integer division truncates toward zero, so 7 / 2 is 3 and -7 / 2 is -3.
  • Running past the last instruction ends the spell, exactly as awarthad does.

Constraints:

  • The spell holds at most 200 instruction lines.
  • Every array size is between 1 and 1000.
  • The spell ends after at most 100000 executed instructions.
  • Every value the spell computes stays between −231-2^{31} and 231−12^{31}-1.
  • No spell reads an undeclared variable, touches a cell outside an array, divides by zero, or jumps to a label that does not exist.

Input

The input is one spell, one instruction per line. A single line holding END follows the last instruction.

Output

Print what the spell prints: one line for every teithant and every canad it executes, in the order they run.

Examples3

  1. Example 1

    Input
    tangado x
    anno x 3
    aderthad x 2
    canad x
    adlanna x 2
    canad x
    adlegi x 1
    canad x
    athrado x 3
    canad x
    tangado i
    ost sequence 10
    anno sequence[0] 0
    anno sequence[sequence[0]] 0
    anno sequence[2] 1
    anno sequence[3] 1
    anno sequence[4] 1
    anno sequence[5] 1
    anno sequence[6] 0
    anno sequence[7] 3
    anno sequence[8] 4
    anno sequence[9] 5
    sad loop
    muindor i 10 end
    muindor sequence[i] 0 ttthti
    muindor sequence[i] 1 gar
    muindor sequence[i] 2 ggar
    muindor sequence[i] 3 wdys
    muindor sequence[i] 4 th
    muindor sequence[i] 5 ti
    muindor sequence[i] 6 tmwhg
    muindor sequence[i] 7 abom
    muindor sequence[i] 8 sfh
    muindor sequence[i] 9 lnancb
    sad ttthti
    teithant "They're taking the hobbits to Isengard!"
    arth pool
    sad gar
    teithant "Gard"
    arth pool
    sad ggar
    teithant "Ga-gard"
    arth pool
    sad wdys
    teithant "What did you say?"
    arth pool
    sad th
    teithant "The hobbits"
    arth pool
    sad ti
    teithant "To Isengard!"
    arth pool
    sad tmwhg
    teithant "Tell me, where is Gandalf, for I much desire to speak with him."
    arth pool
    sad abom
    teithant "A balrog of Morgoth"
    arth pool
    sad sfh
    teithant "Stupid fat hobbit!"
    arth pool
    sad lnancb
    teithant "Leave now, and never come back!"
    arth pool
    sad pool
    aderthad i 1
    arth loop
    sad end
    awarthad
    END
    
    Expected output
    5
    2
    1
    3
    They're taking the hobbits to Isengard!
    They're taking the hobbits to Isengard!
    Gard
    Gard
    Gard
    Gard
    They're taking the hobbits to Isengard!
    What did you say?
    The hobbits
    To Isengard!
    
  2. Example 2

    Input
    teithant "Hello World"
    awarthad
    END
    
    Expected output
    Hello World
    
  3. Example 3

    Input
    tangado shadowfax
    anno shadowfax 4
    aderthad shadowfax 3
    pen shadowfax 6 mordor
    teithant "to Rohan!"
    awarthad
    sad mordor
    teithant "to Mordor!"
    awarthad
    END
    
    Expected output
    to Rohan!