## Monday, June 30, 2014

### Cymatic universe

4 and 1/2 years later serious physicists are considering that maybe our universe is a vibrating superfluid.
One I call the Cymatic Universe, one that is in a nonlinear medium and behaves like a non Newtonian superfluid that's lossless.

Published on 12/02/2010

## Tuesday, June 17, 2014

### Reverse Polish Notation - Spreadsheet Calculator

This is for a job I was interviewing for 2 years back.
Beautiful piece of code I wrote although I never got the job.

Hello John,

It was really nice to talk to you.
Attached is the coding question we send to everyone.  Feel free to use
whatever languages/tools
you are most comfortable with to solve it.  It is not really intended
to be an embedded exercise per se, but rather a way to see how you
might tackle a simple problem.

If you have any questions, feel free to ask. Once we cross this stage
I am looking forward to meet you and YYYY our business development
manager will coordinate with you.

Thanks,
XXXX

A spreadsheet consists of a two-dimensional array of cells, labeled A1, A2, .... Each cell contains either an integer (its value) or an expression.
Expressions contain integers, cell references, and the operators '+', '-', '*', '/'. Expressions are given in Reverse Polish Notation (see http://en.wikipedia.org/wiki/Reverse_Polish_notation). Write a program (in Python/C++/Java/C) to read a spreadsheet specification and evaluate the values of all the cells. A spreadsheet is specified as a plain text file:
• Line 1: two integers, defining the width and height of the spreadsheet (n, m)
• n*m lines each containing an expression which is the value of the corresponding cell (cells enumerated in the order A1, A2, A, B1, ...).
Your program should output its data in the same format, but each cell should be reduced to a single floating point value.
Example
2 2
A2
4 5 *
A1 B2 /
3
evaluates to:
2 2
20
20
6.6666667
3
The above example input visually looks like:
1 2
-------------------------
A | A2 | 4 5 * |
-------------------------
B | A1 B2 / | 3 |
-------------------------
Test Cases
• We provide several example input and output files. • We value elegance, simplicity, and readability in your code
Comments • All numbers in the input are positive integers, but internal calculations and output should be with floats. You can assume that there are no more than 26 rows (A-Z) in the spreadsheet. • Your program should detect cyclic dependencies in the input data and report these by throwing CircularReferenceException.
• You may assume that input file is formatted correctly, and all of the expressions are well-formed.
• Just passing the provided test cases does NOT mean you have a correct implementation.

-------------------

Attached is a C++ version of the Spreadsheet Calculator.
input is from Standard in

John

cat test1.in
2 2
A2
4 5 *
A1 B2 /
3

sokol@server:~\$ g++ RPNcalc.cpp
sokol@server:~\$ ./a.out < test1.in
2 2
20
20
6.66667
3

cat test2.in

3 3

2

3 3 4 + *

A1 B1 +

A2
7
10 C1 /
A1 5 /
B2
3

sokol@server:~\$ ./a.out < test2.in
3 3
2
21
23
21
7
25
0.4
7
3

sokol@server:~\$ ./a.out < testfail.in
Circular Reference Exception
sokol@server:~\$

-------------------
RPNCalc.cpp
-------------------

#include <string>
#include <cctype>
#include <iostream>
#include <map>
#include <sstream>
#include <fstream>
#include <stack>

//  Copyright John L. Sokol - May 21, 2012
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
//

using namespace std;

#define FALSE 0
#define TRUE 1

namespace Error
{

struct CircularReferenceException
{
};

struct Zero_divide
{
};

struct Unresolved
{
};

struct Table_error
{
const char *p;
Table_error (const char *q)
{
p = q;
}
};

struct Syntax_error
{
const char *p;
Syntax_error (const char *q)
{
p = q;
}
};
}

{

typedef struct
{
std::string data;
double result;
bool solved;
} ElementType;

typedef map < std::string, ElementType > TableType;

TableType table;
int x, y;

public:
int unresolved_elements;
bool tablefail;

enum Token_value
{
STRING, NUMBER, PRINT, END, ADD = '+', SUB = '-', MUL = '*', DIV = '/'
};

{
};

{
};

double RPNeval (string expr);

void solve_pass ();
void solve ();

void dumpresults ();
void dumpmap ();

};

double
{

double a, b, result;

#define MATH_OPERATION( op ) \
if(mystack.size() < 2) throw Error::Syntax_error("Stack Underrun"); \
a = mystack.top(); mystack.pop(); \
b = mystack.top(); mystack.pop(); \
mystack.push(b op a);

stringstream input (stringstream::in | stringstream::out);
string token;

stack < double >mystack;
char ch;

input << expr;

while (input.get (ch))
{
switch (ch)
{
case 0:
break; // Should never get here

case '\t':
case ' ':
break;

MATH_OPERATION (+)break;
case SUB:
MATH_OPERATION (-)break;
case MUL:
MATH_OPERATION (*)break;
case DIV:
if ((mystack.size () >= 2) && (mystack.top () == 0))
throw Error::Zero_divide ();
MATH_OPERATION (/)break;

case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
input.putback (ch);
input >> result;
mystack.push (result);
break;

default:
if (isalpha (ch))
{
input.putback (ch);
input >> token;

if (table.find (token.c_str ()) != table.end ())
{
if (table[token.c_str ()].solved == 1)
{
mystack.push (table[token.c_str ()].result);
}
else
{
unresolved_elements++;
throw Error::Unresolved ();
}
}
else
throw Error::Syntax_error ("Invalid CELL");

}
else
throw Error::Syntax_error ("Invalid symbol");
}

}

result = mystack.top ();
mystack.pop ();
return result;
}

void
{
char tmpstr[255];
char element[6];
int i, j;
stringstream ss (stringstream::in | stringstream::out);

unresolved_elements = 0;

cin.getline (tmpstr, 255);
ss << tmpstr;
ss >> x;
ss >> y;
// Check x & y size and throw exception for too large
if (x > 26 || y > 100)
{
throw Error::Table_error ("exceeded maximum size");
//     exit(1);
}

for (i = 0; i < x; i++)
for (j = 0; j < y; j++)
{
sprintf (element, "%c%d", 'A' + i, 1 + j);

cin.getline (tmpstr, 255);
table[element].data = tmpstr;
table[element].result = 0;
table[element].solved = FALSE;
unresolved_elements++;
}
}

void
{
TableType::const_iterator iter;

unresolved_elements = 0;
tablefail = FALSE;

for (iter = table.begin (); iter != table.end (); iter++)
{
try
{
if (table[iter->first].solved == FALSE)
{
table[iter->first].result = RPNeval (iter->second.data);
table[iter->first].solved = TRUE;
}
}
catch (Error::Unresolved)
{
// Don't do anything, will try again next passs.
}
catch (Error::Syntax_error e)
{
cerr << "Syntax Error:" << e.p << "\n";
tablefail = TRUE;
}
catch (Error::Zero_divide)
{
cerr << "Divide by Zero Error" << "\n";
tablefail = TRUE;
}
}

}

void
{
int lastunresolved;

do
{
lastunresolved = unresolved_elements;
//dumpresults();
solve_pass ();
}
while ((unresolved_elements != 0)
&& (unresolved_elements < lastunresolved) && !tablefail);

if (unresolved_elements != 0 && !tablefail)
throw Error::CircularReferenceException ();

if (tablefail)
throw Error::Syntax_error ("Unable to resolve table");

}

void
{
TableType::const_iterator iter;

for (iter = table.begin (); iter != table.end (); iter++)
{
cout << iter->first << " = " << iter->second.data << "\n";

}
}

void
{
TableType::const_iterator iter;
cout << x << " " << y << "\n";

for (iter = table.begin (); iter != table.end (); iter++)
{
//cout << iter->first
if (table[iter->first].solved)
cout << table[iter->first].result ;
else
cout << "unresolved ";
cout << "\n";
}

}

int
main (int argc, char *argv[])
{

try
{
ss.solve ();

if (ss.unresolved_elements == 0 && !ss.tablefail)
ss.dumpresults ();

}
catch (Error::CircularReferenceException)
{
cerr << "Circular Reference Exception\n";
}
catch (Error::Syntax_error e)
{
cerr << "Syntax Error:" << e.p << "\n";
}
catch (Error::Table_error e)
{
cerr << "Table Error:" << e.p << "\n";
}
return 0;
}