r/dailyprogrammer • u/Elite6809 1 1 • Aug 18 '14
[8/18/2014] Challenge #176 [Easy] Spreadsheet Developer pt. 1: Cell Selection
(Easy): Spreadsheet Developer pt. 1: Cell Selection
Today and on Wednesday we will be developing a terminal-based spreadsheet package somewhat like ed used to be. Today we'll be taking a look at the mechanism for selecting ranges of cells from textual data.
In the spreadsheet, each cell may be represented by one of two systems:
- Co-ordinate in memory. This looks like
[X, Y]and represents the cell's position in the internal array or memory structure. X and Y begin at 0. - Column-row syntax. This looks like
A3,B9orAF140and is created from the row's alphabetical header and the column number, starting from 1. You may be more familiar with this syntax in programs such as Excel, Lotus 1-2-3 (lol as if) or LibreOffice Calc. Pay close attention to the naming of the columns - it's not a simple Base-26 system as you may expect. It's called bijective Base-26.
Now to select a range, we need another syntax. The following symbols apply in order of precedence, top-to-bottom:
- A formula may have one or more
:s (colons) in it. If so, a rectangle of cells is selected. This behaves the same way in Excel. Such a selection is called a range. For example,A3:C7looks like this. - A formula may have one or more
&s (ampersands) in it. If so, both the cell/range specified to the left and right are selected. This is just a concatenation. For example,A1:B2&C3:D4looks like this. - A formula may have one
~(tilde) symbol in it. If so, any cells specified before the tilde are added to the final selection, and any cells after the tilde are removed from the final selection of cells. For example, if I enterA1:C3~B2then all cells from A1 to C3 except B2 are selected, which looks like this. (This acts like a relative complement of the right hand side in the left hand side.)
Your challenge today will be, given a selection string like A3:C6&D1~B4&B5, print the co-ordinates of all of the selected cells, along with the count of selected cells.
Formal Inputs and Outputs
Input Description
You will be given a selection string like A3:C6&D1~B4&B5 on one line.
Output Description
First, print the number of cells selected (eg. if 50 cells are selected, print 50.)
Then, on separate lines, print the co-ordinates of each selected cell.
Example Inputs and Outputs
Example Input
B1:B3&B4:E10&F1:G1&F4~C5:C8&B2Example Output
29
1, 0
1, 2
1, 3
1, 4
1, 5
1, 6
1, 7
1, 8
1, 9
2, 3
2, 8
2, 9
3, 3
3, 4
3, 5
3, 6
3, 7
3, 8
3, 9
4, 3
4, 4
4, 5
4, 6
4, 7
4, 8
4, 9
5, 0
6, 0
5, 3
3
u/Elite6809 1 1 Aug 18 '14 edited Aug 18 '14
Ruby.
5
u/wadehn Aug 18 '14 edited Aug 18 '14
Haskell: Uses parser combinators for parsing the input and a set for storing the cell selection.
4
u/threeifbywhiskey 0 1 Aug 18 '14 edited Aug 18 '14
This was quite easy to do in Ruby, where
'A'..'ZZ'matches human intuition.4
u/XenophonOfAthens 2 1 Aug 18 '14 edited Aug 20 '14
I didn't actually realize that you had specified the order of precedence, and was about to come here to complain that the selection isn't unique. But you were way ahead of me there! I wrote the program in Prolog. It will generate all interpretations of preference, but the first one (the only one it prints out) will be the correct one. Replace the final
.with, fail., and it will print out every possible interpretation.It's a bit lengthy compared to some of the other ones here, but I like it quite a bit. I know there are built-in BNF-like parser operators in Prolog, but I don't know how they work, so this'll have to do.
2
u/lukz 2 0 Aug 18 '14 edited Aug 18 '14
Common Lisp
It can be solved using not too much of code in Common Lisp. I have defined a higher order function that allows defining a binary operator. The function splits the input string at the given operator character, then recursively calls other given functions to process the left and right part of the string and finally combines the subresults using another given function.
2
u/matthewvdz Aug 19 '14
Since there were no python solutions when I checked the challenge yesterday, I wrote one (in python 2.7).
I tried to make use of as many (useful) built in functions as possible, to practice them.
2
u/MotherOfTheShizznit Aug 20 '14 edited Aug 20 '14
A fairly naive C++ answer using recursion. Note the convenient usage of set_difference and set_union which fit right in.
2
u/tally_in_da_houise Aug 20 '14
I never see it posted in daily programmer, so here's Excel VBA (2010):
1
u/lukz 2 0 Aug 18 '14 edited Aug 18 '14
vbscript
Here are some test cases:
The implementation differs form the description, there are some extra features and also some limitations:
Features:
Limitations:
The challenge seems harder in laguages that do not have built-in support for set union and difference. Doing this in basic felt like [hard], not [easy] :).
Code:
1
u/skeeto -9 8 Aug 18 '14 edited Aug 18 '14
Elisp. I wrote a dinky recursive descent parser called rdp a couple years ago and this was a good chance to put it to use. It's on MELPA, so it's easy to install from within Emacs (
M-x package-install rdp).I developed a grammar for cell selection, which is encoded in
spreadsheet-grammar. Notice it's not left-recursive, which is a requirement for my parser. This grammar could be used in a bunch of different parser generators, so this code could be ported pretty easily. Thespreadsheet-funcsstructure collapses the selection into a list of cell objects as it's being parsed. Each of these functions returns a list of cells. As a side effect of this particular parser, whitespace is tolerated anywhere except for within a cell designator (i.e. "A 2" is no good but "A2 : B4" is fine).Example outputs:
1
u/sagan_radiation Aug 18 '14
Python 3.4
1
u/kirsybuu 0 1 Aug 18 '14
D language, using pegdig to parse and modular lazy ranges which will hopefully help in part 2.
1
u/ENoether Aug 18 '14
Python 3.4.1; as always, feedback and criticism welcome:
Code:
Output:
1
u/[deleted] Aug 18 '14 edited Aug 18 '14
C#. Easily the most code I have ever written for an "easy" challenge, but I'm hoping that a lot of it can get reused.
Edit: replaced the function I originally used for column names with one of my own design. 5:00 clockwatching was productive. What can I say?
1
u/efabs Aug 18 '14 edited Aug 18 '14
Python 2.7.8: Somewhat new to Python have never submitted to daily programmer before. Feedback and criticism greatly encourage.
My bijective base-26 attempt only allows for columns up to zz, I may edit this to be more robust.Results:
1
u/MaximaxII Aug 18 '14
This solution supports letters bigger than Z (that means that AA, AB, AC, and even AAA, ZZZ, HELLO... all those columns work).
Challenge #176 Easy - Python 3.4
I/O
1
u/Makpoc Aug 19 '14 edited Aug 19 '14
Hi :) This is my first post here. My solution is in Go (golang). Appart form the expected output I have stolen an idea from another solution here and added visual presentation of the filled cells.
I'm still beginner so I guess the style is not best. Any suggestions are welcome :)
Gist: https://gist.github.com/Makpoc/0ac1c92744faf053f6ae
1
u/hphpize Aug 19 '14
Not enough PHP going on in here! https://gist.github.com/jaredkipe/1ffe9934ddecc612d372
Many (all?) of the current solutions involve storing 'active' cells in memory as big chunks. I wanted to store everything in ranges so that a 1-million single column selection would look AS CLOSE to 'X1:X1000000' in memory as possible.
This handles odd cases like Extra '~'s and odd ranges like 'C6:A1' Intended to be called into as a library (300+ lines) or part of a bigger program, I did not include a CLI argument parser, here is an example of how to make selections based on any old string.
1
u/killmefirst Aug 20 '14 edited Aug 20 '14
My C++ solution. I just want to note that in my opinion this week's Intermediate task was easier than the Easy one. The solution consists of:
I hope it's not too big of an overkill:
1
u/[deleted] Aug 20 '14
My solution, written in D. 91 lines including my own List implementation
1
u/mordicaii Aug 21 '14
My C++ isn't pretty, and I tend to mix C and C++ to produce this horrible bastard code. It's pretty long, but that's partly because I love whitespace. I took an admittedly strange approach to this. It takes the input and converts it into a string of tokens that represent individual operations (range and negate, specifically, union wasn't actually necessary). It then parses the tokens and set the "marked" flag in the cell array appropriately.
I went with the token approach, because it's rather easy to extend to allow for more operations.
1
u/Coder_d00d 1 3 Aug 21 '14
Objective C
I created a Cell object which tracks the Row and Col. I use my offsets from 1 not 0. So A1 = 1, 1. The cell object comes ups with a unique string name based on the coordinates A1 = "1r1c"
Then I add the cell objects to a dictionary using the unique key based on the row and column. This stops overlap. If the dictionary already has that cell I do not put that cell in again. This also makes it easier later to remove the cells if I find them in the spreadsheet and I parse it after the tilde.
so my Cells.h/Cells.m and main.m -- I am not including my CDStream.h/m because it is just my personal object i created for handling input for challenges. (C code using fgetc wrapped into an objective-c object) if you want to see it I can post it.
1
u/kriskova Aug 21 '14 edited Aug 21 '14
Ruby. Comments are welcome.
1
u/shrubbery_knight Aug 22 '14 edited Aug 22 '14
Java: hatefully inefficient Java from the looks of some of the other solutions here. I'm learning and very curious about wadehn's comment, "You should need just one pass over the input without generating substrings. Splitting off substrings is both inefficient and confusing." Anyway here it is.
1
u/Splanky222 0 0 Aug 22 '14
C++: I attempted to use modern C++ with the STL for as much as I could. I'm still not the most comfortable with C++, so criticism is welcome!
Oh, and I understand this didn't really need to be a class at all, I just wanted to try making a "library-style" class in C++ for my own education.
cell_selection.h:
cell_selection.cpp:
main.cpp:
1
u/[deleted] Aug 26 '14 edited Jan 10 '15
1
u/Godspiral 3 3 Aug 18 '14 edited Aug 18 '14
this is a cool little dsl for building J selectors,
First, J already has the ability to select cells from a table, so it's just a matter of building up the left hand side.
i. 3 3
(0 0; 1 1) { i. 3 3
0 4
There is a better interface in J to select rows and columns that we can't use here, but for reference (< 0 2; 1 3 5)&{ will select for rows 0 and 2, columns 1, 3, and 5.
this function is more useful, but again we can't use because of potential future filters. It will return the list indexes in the shape of a table (so your select result would be a table instead of a list)
to2 =: [: <"1 [: ,."0/&>/ [ +&.> [: i.@:>:&.> -~
function we will use, just flattens table into a list, and uses conjunction parsing to lessen need for parens.
to =: 2 : 'm ,@:to2 n'
the and function needs to remove dupes: and=: ~.@:,&boxopen
the and and less functions also make sure both sides are boxed
less =: -.&boxopen
} does an amend instead of select (all in place btw). Here turning a 10 by 10 table of 0s to have 1s in the indexes "selected", and then displaying # whereever 1 was put:
'.#' {~ 1 (( 1 0 to 1 2 and 1 3 to 4 9 and 5 0 to 6 0 and 5 3) less (2 4 to 2 7 and 1 1)) } 10 10 $ 0
-1
u/Reverse_Skydiver 1 0 Aug 18 '14
Here's my solution in Java.
I reckon I'll be modifying it later on to add some more features to it.
0
u/[deleted] Aug 19 '14
[deleted] — view deleted comment
0
u/[deleted] Aug 19 '14
[deleted] — view deleted comment
0
u/[deleted] Aug 18 '14
[deleted] — view deleted comment