You have found a weird box in your grandma’s basement. A careful inspection revealed that it is an old-school computer. You tried to run some simple programs but they all behaved very weirdly. It took you some time before you were able to pinpoint the reason: the computer uses ternary logic and arithmetic!
A trit is the ternary equivalent of a bit. Our trits can store the values 0, 1, 2. When doing logical operations with trits we imagine that 0 represents false, 1 represents unknown, and 2 represents true.
The computer has 26 registers, labeled A through Z. Each register is a 40-trit unsigned integer variable.
The computer supports the standard arithmetic operators: +, -, *, / (integer division), and % (modulo). All computations are done modulo 340. Division and modulo by zero cause a runtime error.
The computer also supports the following tritwise operators:
& (and) returns false if either operand is false, true if both are true, and unknown otherwise| (or) returns true if either operand is true, false if both are false, and unknown otherwise^ (xor) is addition (without carry) modulo 3~ (unary not) is subtraction from 2<< (shift left) and >> (shift right) behave as expected, new trits are set to 0Examples (with leading zeros omitted):
& 1113 = 1103| 1113 = 2113^ 1113 = 0213~ 2103 = 222…2220123 (i.e., 37 twos followed by 012)<< 2 = 210003>> 2 = 23.You suspect that there are some instructions for loops and jumps and such, but so far you weren’t able to discover any. Thus, in this problem you will have to do without such fancy tools. A program is therefore a finite sequence of commands. Each command will be executed exactly once, in the given order. Each command has one of three forms:
[register] = [operand][register] = [operand] [operator-with-two-operands] [operand][register] = [operator-with-one-operand] [operand]Here, operators are the ones listed above and each [operand] is either a register or an integer constant that fits into a register.
Constants can be given either in base-10 or in base-3. Base-10 constants have no prefix, base-3 constants have a prefix “0t” (zero, lowercase t). For example, 47 and 0t001202 represent the same number.
At least one space between each two tokens is mandatory.
At the beginning of our program’s execution, the register X contains the input number and all other registers contain zeros. We want to find the last non-zero digit of X (if any) and set it to zero.
One possible program that does this looks as follows:
A = X - 1
B = ~ A
C = B ^ X
X = X & CThe explanation is left as an exercise for the reader.
Write a program that computes ndp: the length of the longest non-decreasing prefix of a number. For example, for any number x that has the form 000122012…3 we have ndp(x)=6 because the first six trits of x are in sorted order but the first seven aren’t.
Formally, let the ternary representation of x be x39x38…x0. We define ndp(x) as the largest i such that x39 ≤ x38 ≤ ⋯ ≤ x39 − i + 1.
At the beginning of your program’s execution, the register X contains the input number and all other registers contain zeros. At the end of your program’s execution the register Y must contain the value ndp(X), all other registers may contain any value.
Your program must contain at most 100 commands.
At the beginning of your program’s execution, the register X contains the input number and all other registers contain zeros. It is guaranteed that X is between 0 and 109, inclusive.
Write a program that will set Y to 1 if X is prime, and leave it at 0 if it isn’t. (Recall that the numbers 0 and 1 are not prime.)
Your program must contain at most 5,000 commands.
There is no input.
Your output file must contain a program that meets the above specifications and solves the given subproblem.
Note that empty lines and extra whitespace on each line are ignored, feel free to use those to format your program for better human readability. Only non-empty lines are counted towards the limit on the number of instructions. Remember that at there must be at least one space between any two tokens in your program, and at least one newline between any two commands.
A very basic interpreter is provided on a best effort basis on an external site. The interpreter will start in a state with zeros in all registers, execute up to 5000 commands of the program you provide, and report either an error that occurred, or the number of commands executed and final values in all registers.