Skip to content

Instantly share code, notes, and snippets.

@TomasDrozdik
Last active November 25, 2018 19:29
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save TomasDrozdik/a80e84373dc66715609ba02c4c7d5b92 to your computer and use it in GitHub Desktop.
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
namespace Uloha7_Excel
{
class Program
{
static void Main(string[] args)
{
if (args.Length != 2) {
Console.WriteLine("Argument Error");
return;
}
try {
StreamReader reader;
using (reader = new StreamReader(args[0])) {
Sheet sheet = Sheet.ReadSheet(reader);
sheet.Eval();
StreamWriter writer;
using (writer = new StreamWriter(args[1])) {
sheet.Print(writer);
}
}
}
catch (IOException) {
Console.WriteLine("File Error");
return;
}
}
}
class Sheet
{
public static Sheet ReadSheet(StreamReader input)
{
Sheet sheet = new Sheet();
char[] charSeparators = new char[] { ' ' };
string line;
int row = 0, column = 0;
while ((line = input.ReadLine()) != null) {
sheet.data.Add(new List<Cell>());
foreach (string cellToken in line.Split(charSeparators, StringSplitOptions.RemoveEmptyEntries)) {
sheet.data[row].Add(Cell.ParseCell(cellToken));
++column;
}
++row;
column = 1;
}
return sheet;
}
public Cell this[Address adr]
{
get {
int row = adr.Row - 1;
int column = adr.Column - 1;
if (row < data.Count && column < data[row].Count) {
return data[row][column];
}
else {
return Sheet.zeroCell;
}
}
}
public void Eval()
{
var evaluator = new EvalSheet(this);
Address adr = new Address();
int row, column;
for (row = 0; row < data.Count; ++row) {
for (column = 0; column < data[row].Count; ++column) {
adr.Row = row + 1;
adr.Column = column + 1;
evaluator.Eval(adr);
}
}
}
public void Print(StreamWriter writer)
{
int row, column;
for (row = 0; row < data.Count; ++row) {
for (column = 0; column < data[row].Count - 1; ++column) {
writer.Write(data[row][column].ToString() + ' ');
}
if (column < data[row].Count) {
writer.WriteLine(data[row][column].ToString());
}
else {
writer.WriteLine();
}
}
}
private Cell this[int row, int column]
{
// It's private we assume row and column are valid => should be faster.
get {
return data[row][column];
}
}
private List<List<Cell>> data = new List<List<Cell>>();
internal static Cell zeroCell = new Cell(new CellValue(0));
internal static Cell emptyCell = new Cell(new CellValue());
}
class Address
{
public Address(int row = 1, int column = 1)
{
this.Row = row;
this.Column = column;
}
public int Row
{
get;
internal set;
}
public int Column
{
get;
internal set;
}
public override bool Equals(object value)
{
Address adr = value as Address;
return Row == adr.Row && Column == adr.Column;
}
public override int GetHashCode()
{
return (Row + Column).GetHashCode();
}
}
class AddressComparer : IEqualityComparer<Address>
{
public bool Equals(Address adr1, Address adr2)
{
return adr1.Equals(adr2);
}
public int GetHashCode(Address obj)
{
return obj.GetHashCode();
}
}
class Cell
{
public Cell(CellValue val)
{
this.Val = val;
}
public Cell(Formula formula)
{
this.Formula = formula;
}
public static Cell ParseCell(string s)
{
int val;
Formula formula;
if (s[0] == '=') {
Errno err = Formula.TryParseFormula(s, out formula);
if (err != Errno.NULL) {
return new Cell(new CellValue(err));
}
else {
return new Cell(formula);
}
}
else if (int.TryParse(s, out val)) {
return new Cell(new CellValue(val));
}
else if (s == "[]") {
// Empty cells in the input should be also present in the output
// so we add them to the sheet.
// Since value doestn't change add reference to static value.
return Sheet.emptyCell;
}
else {
return new Cell(new CellValue(Errno.INVVAL));
}
}
public override string ToString()
{
if (Formula != null) {
// When calling ToString the sheet should be evaluated as a whole.
throw new NotCalculatedException();
}
return Val.ToString();
}
internal Formula Formula
{
get; set;
} = null;
internal CellValue Val
{
get; set;
} = null;
}
class CellValue
{
public CellValue(bool empty = true)
{
this.Empty = empty;
}
public CellValue(int val)
{
this.Val = val;
}
public CellValue(Errno err)
{
this.Err = err;
}
public bool IsError()
{
return Err != Errno.NULL;
}
public override string ToString()
{
if (Err != Errno.NULL) {
return "#" + Err.ToString();
}
else if (Empty == false) {
return Val.ToString();
}
else {
return "[]";
}
}
//TODO redifine setters so that changing one value would preserve logic.
public Errno Err
{
get; set;
} = Errno.NULL;
public int Val
{
get; set;
} = default(int);
private bool Empty
{
get; set;
} = false;
}
class NotCalculatedException : Exception
{
}
class Formula
{
public Formula(char op, Address operand1, Address operand2)
{
this.op = op;
this.Operand1 = operand1;
this.Operand2 = operand2;
}
public static Errno TryParseFormula(string token, out Formula formula)
{
int i, row, column;
formula = null;
char op = (char)0;
Address op1 = null;
Address op2 = null;
if (token.IndexOfAny(Formula.operands) == -1) {
return Errno.MISSOP;
}
i = 0;
if (token[i] != '=') {
return Errno.FORMULA;
}
++i;
column = 0;
while (i < token.Length && Char.IsUpper(token[i])) /* construct adr1 column with Horners scheme */ {
column = column * 26 + (token[i] - 'A' + 1);
++i;
}
//TODO: add first iteration so that it doestn't accept row number begining with 0.
row = 0;
while (i < token.Length && Char.IsDigit(token[i])) /* construct adr1 row with Horners scheme */ {
row = row * 10 + (token[i] - '0');
++i;
}
if (row != 0 && column != 0) {
op1 = new Address(row, column);
}
// Check for operand
if (i < token.Length && token[i] == '*') {
op = '*';
}
else if (token[i] == '+') {
op = '+';
}
else if (token[i] == '-') {
op = '-';
}
else if (token[i] == '/') {
op = '/';
}
++i;
column = 0;
while (i < token.Length && Char.IsUpper(token[i])) /* construct adr2 column with Horners scheme */ {
column = column * 26 + (token[i] - 'A' + 1);
++i;
}
//TODO: add first iteration so that it doestn't accept row number begining with 0.
row = 0;
while (i < token.Length && Char.IsDigit(token[i])) /* construct adr2 row with Horners scheme */ {
row = row * 10 + (token[i] - '0');
++i;
}
if (row != 0 && column != 0) {
op2 = new Address(row, column);
}
if (op1 != null && op2 != null && op != (char)0 && i == token.Length) {
formula = new Formula(op, op1, op2);
return Errno.NULL;
}
return Errno.FORMULA;
}
public CellValue EvalFormula(CellValue op1val, CellValue op2val)
{
if (op1val.IsError() || op2val.IsError()) {
return new CellValue(Errno.ERROR);
}
if (op == '/' && op2val.Val == 0)
return new CellValue(Errno.DIV0);
int result = Compute(op1val.Val, op2val.Val);
return new CellValue(result);
}
private int Compute(int op1val, int op2val)
{
int result;
switch (op) {
case '+': {
result = op1val + op2val;
break;
}
case '-': {
result = op1val - op2val;
break;
}
case '*': {
result = op1val * op2val;
break;
}
case '/': {
result = op1val / op2val;
break;
}
default: {
throw new InvalidOperationException();
}
}
return result;
}
public Address Operand1
{
get;
private set;
}
public Address Operand2
{
get;
private set;
}
private readonly char op;
private static char[] operands = { '+', '-', '*', '/' };
}
enum Errno
{
INVVAL,
ERROR,
DIV0,
CYCLE,
MISSOP,
FORMULA,
NULL,
}
class EvalSheet
{
public EvalSheet(Sheet sheet)
{
this.sheet = sheet;
}
public void Eval(Address adr)
{
Cell cellToEval = sheet[adr];
// If there is no formula continue.
if (cellToEval.Formula == null) {
return;
}
executionStack = new Stack<Address>();
visitedFormulas = new HashSet<Address>(new AddressComparer());
values = new HashSet<Address>(new AddressComparer());
executionStack.Push(adr);
visitedFormulas.Add(adr);
while (executionStack.Count != 0) {
topAdr = executionStack.Peek();
topCell = sheet[topAdr];
if (topCell.Formula != null) /* there is a FORMULA at the top */ {
// Add the address of the processed formula to the stack of the visited cells.
visitedFormulas.Add(topAdr);
// HACK: this code is a not nice hotfix.
if (values.Contains(topCell.Formula.Operand1)
&& values.Contains(topCell.Formula.Operand2)) /* compute formula */ {
topCell.Val = topCell.Formula.EvalFormula(sheet[topCell.Formula.Operand1].Val,
sheet[topCell.Formula.Operand2].Val);
topCell.Formula = null;
// Add the value of the formula to the operands stack.
values.Add(topAdr);
// Remove the formula from the seen formulas cuz now it holds value.
visitedFormulas.Remove(topAdr);
executionStack.Pop();
}
else /* this is new formula process it */{
CheckFormula(topCell.Formula);
}
}
else /* there is a VAL at the top */ {
// When there is a cell with already computed value at the top of the stack
// we store that value for further computation and remove it from the top.
values.Add(topAdr);
executionStack.Pop();
}
}
}
private void CheckFormula(Formula formula)
{
Address op1 = formula.Operand1;
Address op2 = formula.Operand2;
if (CheckOperand(op1) == -1) {
// If operand1 is in a cycle then we don't need to eval operand2
return;
}
CheckOperand(op2);
}
private int CheckOperand(Address op)
{
// Check if we have already seen operand => cycle
if (visitedFormulas.Contains(op)) {
TrackCycle(op);
return -1;
}
// Add the address to the stack for further processing.
executionStack.Push(op);
return 0;
}
private void TrackCycle(Address cycleOrigin)
{
// Assign Errno.Cycle to all formulas on the executionStack
// until we find the origin of the cycle.
topAdr = executionStack.Pop();
topCell = sheet[topAdr];
while (true) {
if (topCell.Formula != null) {
topCell.Formula = null;
topCell.Val = new CellValue(Errno.CYCLE);
visitedFormulas.Remove(topAdr);
if (cycleOrigin.Equals(topAdr)) {
// Now cycle origin is evaluated as Errno.CYCLE
values.Add(cycleOrigin);
return;
}
}
if (executionStack.Count == 0) {
// For codex evaluation hints :))
throw new IndexOutOfRangeException();
}
topAdr = executionStack.Pop();
topCell = sheet[topAdr];
}
}
private Address topAdr;
private Cell topCell;
private readonly Sheet sheet;
private Stack<Address> executionStack;
private HashSet<Address> visitedFormulas;
private HashSet<Address> values;
}
}
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace TestInputGenerator
{
class Program
{
static void Main(string[] args)
{
try {
StreamWriter writer;
using (writer = new StreamWriter(args[0])) {
Test10(writer);
writer.Close();
}
}
catch (IOException) {
Console.WriteLine("File Error");
}
}
static void Test10(StreamWriter wr)
{
int i;
for (i = 0; i < 1_000_000; ++i) {
wr.Write("1 ");
}
wr.WriteLine();
for (i = 0; i < 1_000_000 - 2; ++i) {
wr.WriteLine("1 ");
}
for (i = 0; i < 1_000_000; ++i) {
wr.Write("1 ");
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment