Sane's Monthly Algorithms Challenge: November 2008

Befungulator (Beginner Level)

For no apparent reason (why else?), you have decided to create your own interpreter which evaluates mathematical expressions by “befungulating” an inputted grid of characters.

The grid is given to you as an n x m (n rows, m columns) matrix of the following characters:

0-9 Each of the 10 digits represents a single digit number as usual
+ Add
- Subtract
* Multiply
/ Integer division
% Remainder (mod)
> Continue reading instructions in the right direction
< Continue reading instructions in the left direction
^ Continue reading instructions in the upward direction
v Continue reading instructions in the downward direction
X Print the integer value followed by a newline. Stop and exit.

Any other characters should be ignored.

To befungulate a grid of characters, you start at the top-left of the grid, and read right until you find a valid character. If the character is an operator or operand, you intuitively use the character in the evaluation of the mathematical expression (i.e. as you would with a normal calculator).

If you hit a directional operator (>, <, ^, or v), you change the direction of reading the grid.

You may assume:
  • All operands are single digits.
  • The sequence of operators and operands makes sense.
    (e.g. 5+3*9 is valid. 53, +3*, and 3**9 are not)
    With exception to an expression interrupted by an error (see Error Handling, below).
  • The order of operations does not matter (evaluate left to right).
  • An X will not be interpreted if no value has been defined.
  • The calculation will fit within a normal integer data type.
Error Handling:

If you end up reading off the grid, then output Invalid Direction with a newline and quit.
If you divide by zero, then output Zero Division Error with a newline and quit.
If you modulate by zero, then output Invalid Modulo with a newline and quit.
If you end up in an infinite loop, then output Infinite Loop with a newline and quit.
Errors occur in the order that they are interpreted (e.g. If there is both Zero Division and Invalid Direction, Zero Division must be interpreted first).


On the first line are integers n and m (1 ≤ n, m ≤ 100).
On the next n lines are m characters each, representing the row of characters. These characters are listed from “left” to “right”. The rows are listed from “top” to “bottom”.


See problem statement.

Sample Input 1

1 14

Sample Output 1


Explanation of Sample Data 1:

= 3*3/4+9%4-1
= 9/4+9%4-1
= 2+9%4-1
= 11%4-1
= 3-1
= 2

Sample Input 2

2 2

Sample Output 2

Infinite Loop

Sample Input 3

7 8

Sample Output 3


Explanation of Sample Data 3

= 12*2+1*9/5
= 24+1*9/5
= 25*9/5
= 225/5
= 45

Sample Input 4

3 15
vPrimality test
X......for 8!%<

Sample Output 4


All Submissions
Best Solutions

Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Jan 16, 2009
Author: DrSane

Languages Allowed:

Comments (Search)

It's quiet in here...