Created
May 16, 2017 16:39
-
-
Save dhilipsiva/ff61a8e4a5f962590c86b3beb02b24e6 to your computer and use it in GitHub Desktop.
Speardheet
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#! /usr/bin/env python | |
# -*- coding: utf-8 -*- | |
# | |
# vim: fenc=utf-8 | |
# vim: tabstop=4 expandtab shiftwidth=4 softtabstop=4 | |
# | |
# | |
""" | |
File name: spreadsheet.py | |
Author: dhilipsiva <dhilipsiva@gmail.com> | |
Date created: 2017-04-20 | |
""" | |
import re | |
from string import ascii_lowercase | |
ascii_lowercase_len = len(ascii_lowercase) | |
def tokenize(input_string): | |
""" | |
Clean and tokenize the input | |
""" | |
input_string = input_string.lower().strip() | |
if input_string == "": | |
return [] | |
return input_string.split(" ") | |
def cell_to_indices(cell_id): | |
""" | |
Convert cell_id like A1 & B2 to indices like (0,0) and (1,1) respectively | |
""" | |
row_id, column_id, _ = re.split('(\d+)', cell_id) | |
row_index = 0 | |
column_index = int(column_id) - 1 | |
for idx, letter in enumerate(reversed(row_id)): | |
row_index += (ascii_lowercase_len ** idx) * \ | |
(ascii_lowercase.index(letter) + 1) | |
row_index -= 1 | |
""" | |
PHEW! I got to admit, this logic took a lot of my time. | |
Looked simple, but had to do a lot of trial and error. | |
Please, please, please let me know if there is a simpler way :P | |
""" | |
return row_index, column_index | |
class CircularDependencyException(Exception): | |
""" | |
Just a custom exception to raise when we encounter circular dependency | |
""" | |
pass | |
class RPNEvaluationException(Exception): | |
""" | |
A Custom Exception to raise when there is an error in RPN Evauvation Error | |
""" | |
pass | |
class SpreadSheet(list): | |
""" | |
This class extends `list`. Since matrix is expressed as a list of lists, | |
it makes sense to entend from `list` and add more functionalities to it. | |
""" | |
def __init__(self, column_count, row_count): | |
""" | |
Initialize with row count, column count and empty arrays | |
""" | |
super(SpreadSheet, self).__init__() | |
self.column_count = column_count | |
self.row_count = row_count | |
for row in range(row_count): | |
self.append([]) | |
def detect_circular_dependency(self, source_cell, cell_contents): | |
""" | |
Detect circular dependency | |
""" | |
for cell_content in cell_contents: | |
if not re.match('[a-z]+[0-9]+', cell_content): | |
continue | |
inner_cell = cell_to_indices(cell_content) | |
if inner_cell == source_cell: | |
raise CircularDependencyException(source_cell) | |
inner_row, inner_column = inner_cell | |
inner_cell_contents = self[inner_row][inner_column] | |
self.detect_circular_dependency(source_cell, inner_cell_contents) | |
def validate(self): | |
""" | |
Validate our matrix and check if there is any circular dependency | |
""" | |
for row in range(self.row_count): | |
for column in range(self.column_count): | |
cell = (row, column) | |
cell_contents = self[row][column] | |
self.detect_circular_dependency(cell, cell_contents) | |
def read(self): | |
""" | |
Read the input for the cells from stdin | |
""" | |
for row in range(row_count): | |
for column in range(column_count): | |
token = tokenize(input()) | |
self[row].append(token) | |
def parse_rpn(self, cell_contents): | |
""" | |
Evaluate a reverse polish notation | |
""" | |
stack = [] | |
for cell_content in cell_contents: | |
if cell_content in ['-', '+', '*', '/']: | |
num1 = stack.pop() | |
num2 = stack.pop() | |
if cell_content == '-': | |
result = num2 - num1 | |
elif cell_content == '+': | |
result = num2 + num1 | |
elif cell_content == '*': | |
result = num2 * num1 | |
elif cell_content == '/': | |
result = num2 / num1 | |
stack.append(result) | |
elif cell_content in ['--', '++']: | |
num = stack.pop() | |
if cell_content == '--': | |
num -= 1 | |
elif cell_content == '++': | |
num += 1 | |
stack.append(num) | |
elif cell_content.isdecimal() or cell_content.startswith("-"): | |
stack.append(float(cell_content)) | |
elif re.match('[a-z]+[0-9]+', cell_content): | |
row, column = cell_to_indices(cell_content) | |
result = self.parse_rpn(self[row][column]) | |
stack.append(result) | |
else: | |
raise RPNEvaluationException( | |
"Please check RPN expression %s" % cell_contents) | |
return stack.pop() | |
def evaluvate(self): | |
""" | |
Evaluvate and return the result | |
""" | |
# Automatically validate before evaluvating | |
self.validate() | |
print("%s %s" % (self.column_count, self.row_count)) | |
for row in range(self.row_count): | |
for column in range(self.column_count): | |
print("%.5f" % self.parse_rpn(self[row][column])) | |
n_m = input() | |
column_count, row_count = [int(i) for i in n_m.split(" ")] | |
spreadsheet = SpreadSheet(column_count, row_count) | |
spreadsheet.read() | |
spreadsheet.evaluvate() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment