LebGeeks

arithma

Member

Exercise - Arithmetic Grid

You are given a rectangular grid with entries that are whole integers. You start from the cell at row r and column c. You have four operators: +, -, *, /. These operators have double meanings, their usual arithmetic ones and:
+: move to the cell on the right (c increases by one or wraps to the other side)
-: move to the cell on the left (c decreases by one or wraps to the other side)
*: move the cell upwards (r decreases by one or wraps to the other side)
/: move the cell downwards (r increases by one or wraps to the other side)

Exercise 1:
Given a string of operators, and applying them to the cells of the current position of the player (and respecting the rules of precedence) return the result of the expression created by the string.

Example:
Here's the grid, top left is 0, 0

1 2
3 4

You start at (1,0). the cell that has the value 3.
The input expression is: +*.
The resulting expression is: 3 + 4 * 2.
The result of the expression is: 11. (not 14).

Your program must be run in the command line to parse the following input (through standard input):
- Two numbers representing the dimensions of the grid
- Two numbers representing the starting position (guaranteed to be less than the dimensions of the grid)
- The number of operators in the expression
- The characters representing the operators
- The grid numbers in sequence (horizontally through rows then moves to the next row)

The standard stream for this example would be:

2 2 1 0 2 +* 1 2 3 4

Parsing this input, the program must return just 11.
Note that I removed the "-" operator from the expression to keep in sync with the text above.

The next Exercise will be based on the solution of this first one.

Some input into the program has slipped my mind while writing the exercise. Specifically the input expression. Thanks @xterm for pointing it out. Everything is sorted out now. Skim through the example to see how the input file was updated. I should have just posted again for people to see the difference, will keep that in mind next time I correct something.

Last edited by arithma (January 14 2011)

Padre

Member

Re: Exercise - Arithmetic Grid

nice problem !!

i'll see what i can do during lunch break :)

Padre

Member

Re: Exercise - Arithmetic Grid

ok, this is my code :)
i know it's not perfect, maybe a few bugs here and there, and im sure there are a tons of other ways to do it, specially the computing part. but that's all i can do in the lunch break time frame  and i didn't test on any other case than the given one :)

struct myGrid
{
	int **GRID;
	int POSX;
	int POSY;
	int SIZE_X;
	int SIZE_Y;
};

myGrid Grid;

int getGridValue(char *str,int ind)
{
	switch(str[ind])
	{
	case '+':
		Grid.POSX=(Grid.POSX+1)%Grid.SIZE_X ;
		break;
	case '-':
		Grid.POSX=(Grid.POSX?Grid.POSX-1:Grid.SIZE_X-1);
		break;
	case '*':
		Grid.POSY=(Grid.POSY?Grid.POSY-1:Grid.SIZE_Y-1);
		break;
	case '/':
		Grid.POSY=(Grid.POSX+1)%Grid.SIZE_Y;
		break;
	}
	return Grid.GRID [Grid.POSY ][Grid.POSX];
}

void generateGrid(myGrid& Grid,int *cmd)
{
   Grid.SIZE_X =cmd[0];
   Grid.SIZE_Y =cmd[1];
   Grid.POSX =cmd[3];
   Grid.POSY=cmd[2];

   Grid.GRID =new int*[Grid.SIZE_Y];
   for (int i=0;i<Grid.SIZE_Y;i++) 
   {
	   Grid.GRID[i]=new int[Grid.SIZE_X];
	   for (int j=0;j<Grid.SIZE_X;j++)
		   Grid.GRID[i][j]=cmd[4+Grid.SIZE_Y * i +j];
   }


}

computing part

int mult(char* str,int& ind, int acc)
{
 	for(;(str[ind]=='*' || str[ind]=='/');ind++) acc=(str[ind]=='*'?acc*getGridValue(str,ind):acc/getGridValue(str,ind));
	ind--;
	return acc;
}

int compute(char* str,int ind, int acc)
{
	int tmp;
	while (str[ind]!='\0')
	{

		switch (str[ind])
		{
		case '+':
			tmp=getGridValue(str,ind);
			acc+=((str[ind+1]=='*' || str[ind+1]=='/')?mult(str,++ind,tmp):tmp);
			break;
		case '-':
			tmp=getGridValue(str,ind);
			acc-=((str[ind+1]=='*' || str[ind+1]=='/')?mult(str,++ind,tmp):tmp);
			break;
		case '*':
		case '/':
			mult(str,ind,acc);
			break;
		}
		ind++;
	}
	return acc;
}

and main

int main()
{
	int gridCMD[]={2,2,1,0,1,2,3,4};
	generateGrid(Grid,gridCMD);
	for (int i=0;i<Grid.SIZE_Y;i++)
	{
		for (int j=0;j<Grid.SIZE_X;j++)
			printf("%i\t",Grid.GRID [i][j]);
		printf("\n");
	}

	int myVar=Grid.GRID [Grid.POSY ][Grid.POSX ];
	int index=0;
	char *str="+*";
	myVar=compute(str,index,myVar);
	printf("Computing %s : %i \n",str,myVar);
}

edit: Ah well, i didn't see the input mod. wont work on it tho
edit2: just found an obvious bug while re-reading :/

Last edited by Padre (January 14 2011)

xterm

Moderator

Re: Exercise - Arithmetic Grid

As usual, I like adding a twist. This is done in Groovy.

To test this script out, copy the code below and paste it here then execute.

P.S.: I already apologized to arithma for cheating!

def args =  "2 2 1 0 1 2 3 4".split().collect { Integer.parseInt(it) }
def route = "+*-".split('')[1..-1]

(w,h,x,y) = args[0..3]
linear_g = args[4..-1]


linear = { cell,row_size -> cell[0]*row_size + cell[1] }

route_map = [ "+" : { cell -> [cell[0],cell[1]+1] }, 
              "-" : { cell -> [cell[0],cell[1]-1] },
              "/" : { cell -> [cell[0]+1,cell[1]] },
              "*" : { cell -> [cell[0]-1,cell[1]] } ]

              
current_cell = [x,y]
nums_indeces = [linear(current_cell,w)] + route.collect { 
                        res = linear(route_map[it](current_cell),w);
                        current_cell = route_map[it](current_cell);
                        res 
                       }

equation = [ nums_indeces.collect { linear_g[it] }, route + '' ].transpose().flatten().join()

result = new GroovyShell().evaluate(equation)

Last edited by xterm (January 14 2011)

jsaade

Member

Re: Exercise - Arithmetic Grid

The arithmetic part (3+2*4) reminds me of some of my early CS courses [BNF shift reduction].
I do not have time for the full exercise, but because this reminded be of something and I have not touched C++ in over 9months, I implemented an iterative shift reduction without error checking [according to my last memory of the algorithm for binary operations]:

Implementation (hope it is not too buggy)

#include <iostream>
#include <list>
using namespace std;


struct Item{
	bool isOp;
	char prec;
	int value;
	Item(int val=0,bool op=false, char p=0):isOp(op),value(val),prec(p){}
};

list<Item> currentStack;
int Find(list<Item>::iterator &p)
{
	//get the Operation, and operands, evaluate and return result
	Item right = *(p++);
	Item op = *(p++);
	Item left = *p;
	//pop last 3 items from stack:
	currentStack.pop_front();
	currentStack.pop_front();
	currentStack.pop_front();
	switch(op.value){
		case '+':
			return left.value + right.value;
			break;
		case '-':
			return left.value - right.value;
			break;
		case '*':
			return left.value * right.value;
			break;
		case '/':
			return left.value / right.value;
			break;
		default:
			return 0;
	}
	return 0;
}
void Restack(list<Item> &Expression)
{
	//empty stack into Expression
	while(currentStack.size())
	{
		Item t = *currentStack.begin();
		currentStack.pop_front();
		Expression.push_back(t);
	}
}
int Evaluate(list<Item> &Expression)
{
	int result = 0;
	while(Expression.size()){//while there are items in the expression
		//get current Item
		Item t = *Expression.begin();
		Expression.pop_front();
		currentStack.push_front(t); //add item to current oprations
		if(currentStack.size() >= 3) //can be evaluated in a binary operation:
		{
			list<Item>::iterator ip = currentStack.begin();
			++ip;
			Item current = *(ip); //current operation
			if(!Expression.size()) //no more expressions, evaluate current stack
			{
 				ip = currentStack.begin();
				result = Find(ip);//find result from operation
				currentStack.push_front(result);//push the result into the stack of operations
				Restack(Expression);//restack everything into a new operation as it is empty
			}else
			{
				//peek into next operation:
				Item next = *Expression.begin();
				//is the next item an operation? and does it have a lower precedence than the current operation?
				if(next.isOp && next.prec <= current.prec){
					//evaluate current operation
					ip = currentStack.begin();
					result = Find(ip);
					currentStack.push_front(result);//add the result to the current stack of operations
				}
			}
		}
		
	}
	return result;
}

void main(void)
{
	//test-case evaluate expression
	list<Item> Expression;
	cout<<3+2*4-5+2*4+2*4/2*11<<endl;
	Expression.push_back(Item(3));
	Expression.push_back(Item('+',true));
	Expression.push_back(Item(2));
	Expression.push_back(Item('*',true,1));
	Expression.push_back(Item(4));
	Expression.push_back(Item('-',true,1));
	Expression.push_back(Item(5));
	Expression.push_back(Item('+',true));
	Expression.push_back(Item(2));
	Expression.push_back(Item('*',true,1));
	Expression.push_back(Item(4));
	Expression.push_back(Item('+',true));
	Expression.push_back(Item(2));
	Expression.push_back(Item('*',true,1));
	Expression.push_back(Item(4));
	Expression.push_back(Item('/',true,1));
	Expression.push_back(Item(2));
	Expression.push_back(Item('*',true,1));
	Expression.push_back(Item(11));
	cout<<Evaluate(Expression)<<endl;
}

Last edited by ZeRaW (January 17 2011)