Week 12: Diagonal Problem-Solving

This will be my problem-solving post, but there's some old stuff I'll need to bring up again that I missed in past weeks, so don't worry, you'll hear more of me.

The problem is a diagonal-counting one, as can be seen here:
https://wwwcgi.cdf.toronto.edu/~heap/cgi-bin/Solvent/wiki.pl?Problem_Solving_Home_Page/DiagonalCount
(username sleuth, password eureka)

So here goes:

Step 1: Understand the problem

Our problem here involves a rectangular grid made up of squares. There are m rows and n columns of squares (m and n are integers).
We are looking for an integer d which represents the number of squares crossed by a diagonal cutting through our grid from square (0,0) to square (m,n) (where the coordinates represent the square's position along the grid). We want to devise a formula to know how many squares are crossed by the diagonal, not counting squares where the diagonal passes between them (i.e. the diagonal cuts through the meeting-corner of 4 squares, and the squares counted are the origin square and the destination square).

Step 2: Devise a plan

We can test small grids and look for patterns, and then suggest a formula based on our findings. There will be certain special cases: when m=n, when n can be divided by m (and vice-versa), and when n=m+1 (and vice-versa). We'll simplify and set that n>=m so that we don't test grids that are reflections of each other (for instance, m=3 and n=4 would have the same diagonal crossings as m=4 and n=3).
We'll want to pay attention to when the diagonal crosses another line, as this signifies that it has entered a new square.

Step 3: Carry out the plan

Testing a number of different values of m and n, we can find that:
When m=1, the diagonals d=n.
When m=2, the diagonals d=((ceiling of n/2)*2)
At first I considered the possibility that the diagonals would be (ceiling of n/m)*m, but this does not continue into m=3.
After some investigation, I came across the hint on another blog to examine boundaries (added to the plan above). Let's examine those with a table:

As we can see, the number of boundaries crossed is equal to (m-1)+(n-1), which makes sense given that the grid has m-1 horizontal lines and n-1 vertical lines.

Given this information, we can further say that each boundary crossing means another square is added... right? Well, not all crossings are equal. For instance, what if a diagonal crosses horizontally and vertically at the same time? Then, on a 2x2 grid, only 2 squares would be entered.

As the image shows (yeah, yeah, there's a small offset), we only enter 2 squares!

This occurs whenever m=n, as in every case of m=n the grid can be reduced to 2x2 grids (a 3x3 grid would simply have 3 squares entered and 4 boundary crossings, even though it may be 2 overlapping 2x2 grids).

These sorts of reductions work for different m & n pairs too, when there is a common factor between m & n. In such situations, we can divide and simplify:

In these moments, the formula for the number of squares appears to be closer to the length of n, or m*n/GCD.

As well, when these larger grids can be reduced to smaller grids, they produce more intersections (rather than traditional boundary crossings). For instance, 3x6 produces 3 intersections, which means it only covers 6 squares, rather than the 7 of 3x5 or the 9 of 3x7.

Primes then seem to be the mysterious grids. A grid of 2x5 produces 6 squares; 3x11 produces 13 squares. What might the pattern be? (cue some time spent trying to come up with something complicated... before resorting to the simple)

Well, let's make a big graph with squares, GCD and boundaries.

As we can see, when the GCD is 1, the number of squares crossed is m+n-1, which is also the number of boundaries crossed +1. This makes sense as there will be the starting square which is counted though the line does not cross 'into' it.
When the GCD is not 1, we can reduce the problem, but m*n/GCD is not quite correct, as otherwise 4x6 would be 12, not 8. What gives? Well, actually, the problem is reduced to a smaller problem times the GCD, in such that it becomes GCD*((m/GCD)+(n/GCD)-1).

Thus, we end up with a formula:
squares(m,n):
factor=1;
if m>n, factor=m//n; else, factor=m%n;
if factor==1, return m+n-1; else, return factor*squares(m/factor,n/factor);

Hurray!
Here's the Python code:

Let us never speak of this again ;)

Weeks 10 & 11: Catching Up & Halting

Not really sure what week's material needs to be covered at this point. I've been a bit scatterbrained recently with computer science, and today I really felt that way as Danny discussed infinite sets and I just sat there thinking, "Whaaaaaaaaaaat?"

I mean, if there are infinite natural numbers in the set of natural numbers, and we can produce all rational numbers by dividing each natural number by every other natural number (since that would produce every fraction possible), wouldn't that mean that the size of the set of rational numbers is equal to the size of the set of natural numbers squared? This whole diagonal-function thing seemed to come out of thin air to me.

I think I have one more week before I have to formally outline a problem-solving episode, so let's procrastinate on that front a little longer.

I have to say I am curious to see how CSC236 will go, given how theoretical our discussions are becoming. Computability is causing me a bit of a headache on that front. The use of "halt" appears to be for any situation in which the function stops running - it returns or it breaks or it has an error or exception. Not sure if that's right....

If such is the case, then it seems like there are definitely interesting implications to such a problem of what can a computer compute or fail to compute. Once again, we're using proofs to solve those kinds of questions.
What I've been wondering about is as follows: is it possible to write a piece of code that you can know if it's looping forever or if it's just taking a while?
I know I've had times where I've accidentally created infinite while loops in the past, but it's usually pretty obvious that the while loop is the problem and that the rest of the code executes normally.
Say my code was:

f(n):
while True: pass
return n

Then it's obvious that my code will either loop forever or return right away. But does this prove anything? Not really, except that f() loops forever for all n.

The problem is about the bits of code that could just be taking a long time. It's like Schrödinger's Cat in a sense: we cannot be sure based on our models of whether the code is "dead" (reaching some eventual end) or "alive" (looping forever) -- although I can't imagine anyone has posited these bits of code are both looping forever and eventually going to end, so I guess it's a bad analogy.

But again, if we had a function which looped forever, then any calls on that function would loop, and any calls on those calls would loop. So we can't simply pass it to another function to call.

Suppose we did know that a function ran for a really long time n. Then no matter what we add to the function, aside from infinite loops, the function will always run for some finite amount of time. Another assignment might make it n+1, or a search through the elements could make it n*n. But so long as we have a finite number, we can predict how long it should take, right?

So then we should be able to look at functions and identify the step which causes the question of infinite loops. If we are able to evaluate smaller parts to finite amounts, then we can determine which part makes the function non-computable. For f(n), we know that the "while True" causes the problem... we could make it something else which would have the same effect.

g(n):
while abs(n/2) > 0: return g(n/2)
return n

Unless n is 0, g(n) will loop forever, which we know because of how the set of real numbers works. Half of something is always a real number, so we are always going to end up with a smaller real number that approaches 0 but never quite gets there.

If we take the limit, we can see that as the denominator approaches infinity (being 2^n), abs(n/2) gets closer and closer to 0 but never reaches it unless n is assigned to be 0.
And there are an infinite number of powers of 2 after all, as there are infinitely many integers. Oh boy.

Week 9: big-Oh and big-Omega (updated!)

Week 9 had us busy working on proofs again, now looking more in depth at big-Oh and big-Omega.

One thing I've found interesting in this course has been the way we take a concept that is superficially simple and break it down into its complex parts. That is, taking something one may simply take to be true because it just is and finding out why. It's part of what I love about mathematics and computer science: the discovery of why. Once you understand the logical reasoning behind stuff, it becomes so much easier to conceptualize, and then you can extrapolate what you've learned in all kinds of interesting ways.

For instance, last week we began to really investigate big-Oh for functions, and - while it took some headscratching - I feel like I know understand the underlying implications of writing speedy code now, which I had just accepted in 148. And while it's still a fair bit of hand-waving when it comes to restricting variables, it's clear to see from class what's happening at an abstract level in the call stack when we write more or less complicated code.

So, for instance, when dealing with our max_sum(L) slices, we can try to find a way to reduce the runtime once we actually have a sense of how it works. We know that the maximum slice of L will contain the largest value of L and that if we find the single largest value (worst-case runtime n), then we can determine what to do.

UPDATE:

Adding to this post as I find myself thinking about big-Oh again with A3.

big-Oh and big-Omega became a billion times funner for the dopamine part of my brain once we started applying them to these polynomials. There's a deep inner satisfaction, like fitting together puzzle pieces, that comes from meshing 2 functions together, and it was very fun to experiment with that for A3, where we dealt with oscillating functions.

Week 8: A2 and Runtime Funtime

Things have moved into more interesting territory now with discussions about runtime and performance. I found myself wishing I had taken CSC165 last year, as I had a number of times in CSC148 where approximating runtime in a function perplexed me.

We've married together the proof structure with runtime by analyzing upper and lower bounds, which I must say helps remind me that all the course material is under computer science for a reason. Computers do like logic.

These discussions about runtime have also encouraged me to go back to Project Euler again and do some experimentation. One problem there which caused me a great headache was finding the sum of primes, as I kept running into code that took too long to evaluate (I'll need to see exactly what kind of runtime it was experiencing, but given that it had to reiterate over a growing list several times, it was probably x to some large power or even something terrible like x^x).

However, that will have to wait until I finish off A2, due tomorrow. I have to admit, doing it in bits really helps: I spent three days stuck at one point, certain that I was proceeding the right way, only to have a friend suggest that I was supposed to be disproving rather than proving that particular claim. D'oh. Hence, breaking the task apart is very useful, and I also often found myself writing down little pieces of the proofs to test them, like comparing the results of |x-w| with a positive x and w, a positive x and a negative w, a negative x and w, or a negative x and a positive w. This sort of stuff often helped me recognize a better way to proceed based on how things turned out (different signs make a larger end number, while identical signs make a smaller end number).

Unfortunately, I cannot express many more thoughts than this at the moment, thanks to the midterm mush that is my brain. But we may be able to discuss more deeply next week...

Week 7: Penny Piles Pose Peculiar Problems

Proof territory continues.

This Friday we had a very fun swing at a difficult problem involving moving penny piles. We worked at trying to move 64 pennies (2 to the power of 6) from one bin to the other, dividing the pile in half when it was even. What we found was that 64 pennies can, with the correct series of divisions, give back a pile of pennies of any size between 1 and 64. For instance:

Operation L: take 1/2 left drawer, put in right (left drawer must be even)
Operation R: take 1/2 right drawer, put in left (right drawer must be even)
(Drawer 1, Drawer 2)

To get the number 37, we must perform:
L(64, 0) -> (32, 32)
R(32, 32) -> (48, 16)

Now we have (2^5, 2^5) becoming (3*2^4, 1*2^4). This point is significant because we no longer have only powers of 2, but we now can use multiples of 3 to produce odd numbers. This will be handy for reaching 37, though it is not a multiple of 2 or 3 (in fact, it's a prime - but it can be multiplied with 2 and 3!)

R(48, 16) -> (56, 8)
L(56, 8) -> (28, 36)
L(28, 36) -> (14, 50)
.
.
.

Okay, this is taking too long.
What essentially occurs is that we must consider two numbers where the sum is 64 and one number is 37. Obviously, the other number in this scenario is 27, so let's think about those two for a minute.

27 is also prime, but its double is 54, which may be a bit more manageable. When one number is 54, the other is 10 - halving 54 here would thus get us our 37. We're working backwards towards the solution...
So now our aim is to get to 54, but let's say 10 because that sounds easier (10 is small and we know its multiples well, while 54 is a bit big and unwieldy). To get 10, we'd need to have (20, 44) before - to get that answer, we'd need to have (40, 24) before.

Let's work from here: (40, 24) is the same as (8*5, 8*3). That sounds fairly manageable, given that our starting number is 8*8. To get the (5, 3) division, let's just work within that area:
L(8*8, 0) -> (8*4, 8*4)
R(8*4, 8*4) -> (8*2, 8*6)
L(8*2, 8*6) -> (8*5, 8*3)

Now we can take the final steps to get 37. We'll have to break the 8s apart, so let's just use powers of 2 from here on to show the factors.
L(5*2^3, 3*2^3) -> (5*2^2, 3*2^3+5*2^2) --matching the factors--> (5*2^2, 11*2^2)
L(5*2^2, 11*2^2) -> (5*2, 11*2^2+5*2) --matching the factors--> (5*2, 27*2)
R(5*2, 27*2) -> (5*2+3^3, 3^3).

And 5*2+3^3 is 37. Hurray! Thus, by working backward, we are able to determine what steps to follow through solving the problem.
I'll add more to this later.

Week 6: Prove it.

Well we're in clear proof territory now. The midterm behind us, it's now become all about proving this or that statement. It's a fairly fun process to be honest: a sort of puzzle that you fill in. We start with the corners - what we start with, and what we have to get to - and gradually connect them. Maybe there's fewer pieces than a puzzle: most proofs we do have around ten steps. We do, however, have more people working on each proof than would be tackling a puzzle.

What is neat about proofs is the step where you have to make the connection: where you're looking at the structure and considering, "What can I change to make this work?" I remember doing a lot of that in math in school, and it was always exhilarating when you came across a connection between the solution and the starting proof.

It's a skill that is really all intuition: you can't memorize it because proofs always vary in form. But there makes the dopamine rush all the better when you do discover the right way to proceed. What I've found, and what Prof. Heap is pushing towards, is that it nonetheless helps to have a few basic ideas to fiddle with the proof:

A. Transform
Transforming, i.e. rearranging the elements, either the end or the beginning can help. Using the contrapositive can often suggest a new way to proceed, or for more mathematical proofs, we can move the elements around.

B. Disprove
If it's not working, try the opposite: disprove it! And, if it's impossible to disprove, then you have a proof by contradiction.

C. Replace
I would often forget to consider this, but replacing elements with their equivalents is probably the best way to find the answer to a proof. If you can get rid of variables (starting to remind myself of optimization), then you are vastly simplifying the task at hand; if you replace a difficult variable with a simpler one, then you are vastly simplifying the task at hand. Be careful when doing this, of course. You don't want to make a mistake and mangle your proof. Use an appropriate replacement. One of which we've used several times has been replacing general even or odd integers n with a 2k or 2k+1, respectively. This can be really useful, and you should always consider it.

There's a few more ways to proceed: we talked about proof by cases and splitting up the proof on Friday, but these main three have been my standbys for a long time, and I recommend them. Share any methods you may have in the comments.

Week 5: Midterm - Feeling Good

Well the midterm went very well... lots of concepts which were familiar from the past midterm and the course as a whole. So I must have listened well in class.

We're moving into more detailed proofs now, which is fun (for now). I'm a problem-solver, so I like looking at the problem and the solution and trying to mash them together. The technique of "work-from-the-end" is one I've often used in the past, and I'm glad to see that going backwards is still useful when confronted with two seemingly different functions to be reconciled.

I enjoy the notion of using contrapositives and negation to work through a problem. In class today we worked towards proving a statement was a contradiction in order to prove its negation. Useful stuff - Euclid apparently thought so at any rate.

I'm curious about how else we can play around with that sort of thing. The converse doesn't seem to have much value at first in my head, aside from the possibility that, if the converse and the statement are true, then the statement is an "iff statement." But that doesn't seem all that helpful in most scenarios. More musing will be necessary.

I'm impressed with the course, overall. I did some logic in high school and found it a bit annoyingly anal after a while, but I guess I'm more comfortable with dealing with incredibly anal systems. Probably thanks to computer science.

Week 4: Assignment 1

Well the week continues to be full of learning!

Working on A1 has been a good test of how well I understand the concepts. I found myself often combining all kinds of tests to find answers - many Venn diagrams were drawn before I wrote answers to questions.

I find that I sometimes get confused about what precisely is meant by conjunctions and disjunctions in a statement. When P(d) /\ Q(d), are we talking about the truth of each statement, or the truth of the intersection of those statements? And is there a fundamental difference between those two distinctions?

But I enjoyed trying to come up with symbols for English and English for symbols, perhaps because I've done a lot of language learning over the years and it felt very much like an activity in translation. Even though the symbolic terms like "for all" or "there exists" are not to be used in English, you can get away with usually the same phrases to represent them, although the best was when a complicated logical statement could simply be wrapped up as "the least of some group." That felt very satisfyingly complete and concise.

This will have to be a short week for the CLOG, but we shall see where things go next!

Week 3: Folding Madness!

Really cool class today on developing a systematic approach to problem solving - working with determining the pattern of creases in a folded strip of paper. It produces a sequence as expressed in this Wikipedia article: http://en.wikipedia.org/wiki/Regular_paperfolding_sequence - which also goes by the more dramatic name "dragon curve sequence," after its similarity to a very beautiful fractal: http://en.wikipedia.org/wiki/Dragon_curve

The problem ultimately was not about the solution but about the process of solving, in a sort of "the journey is more important than the destination" scenario, so I won't go into what the solution actually is, although read the article if you want to know. It was a bit amusing that virtually every group proceeded by the same method to finding a solution: examine small cases to establish a pattern, a method hammered in by programming and math classes over the years, and one which I often use in my day-to-day life - for instance, while trying to find a function to represent a curve in a graph, which is essentially the same problem with some slight changes (paper folding has a number of folds n which provides a pattern of two alternating variables, written as 0s and 1s in the Wikipedia article; representing a curve has a group of coordinates - usually two, x and y, but sometimes three, with z added in 3D space - which can be gathered to produce a function of how each variable changes relative to the other(s)).

It made me wonder if our reliance on this method is potentially too lazy: what happens when we come across a circumstance which can't be solved using small cases to establish a pattern? It's difficult for me to even conceive of such a problem, since it would require:
- a large sample
- cases which vary over a great area and seemingly with no pattern

But there's always got to be a pattern, right? Just thinking about something occurring with no resolvable pattern is... scary. I can't imagine we'd come up against something like that in 165, but it's interesting to think about it. How does one solve such a problem?

If there's no pattern, then there can be no general case. So then we aren't dealing with a series or sequence, right? There will be no n which can be adjusted to fit any example.

The whole scenario is so difficult to conceptualize, and I have to wonder if it's worth the trouble. We can't effectively predict what a person will want to do in their life if they are born in this place, in this year on this day of the month, with these people as parents (who have their own lives where we were supposed to have calculated this) and with these people around them who they are likely to interact with and these political, social and economic forces working on their world... we can't even do this effectively if the person was abandoned in the woods.

Moving back to computer science, it raises a question about how do you effectively build AI, which run on pattern recognition and learning from pattern recognition. If your computer butler wakes you up early and you're visibly upset (visible in the sense that the computer butler says, "Oh hey, you are upset,") then the computer butler can use the patterns to determine when is a better time to wake you.

But what should the computer butler do for waking a baby or raising a baby? Could a computer raise a child based on predictions and patterns? What kind of child would that be?

This has shot off into the aether a little, but I suppose the question I'm hopping around is "What is a pattern?" And this little exercise put a really interesting spin on how we try to answer that question. We can look at the little bit of data we have and try to figure out what to do. Then we produce a hypothesis or two, tinker and see if they work, and start over if they don't. If the paper folds aren't in a Fibonacci sequence, then we try a different hypothesis based on where we went wrong. At some point, it should work. It just better be soon.

Weeks 1 & 2: Return of the Clog!

The CLOG-SLOG is back!

CSC165 has begun, and the change is material is refreshing for now. Given that we haven't really touched much code, I am inclined to believe the course will remain fairly theoretical. So be it. I can handle theory.

The lectures have remained mainly in the field (or Venn diagram, if you will) of logic and Venn diagrams so far. I am familiar with these sorts of techniques from some logic lectures in high school, although there are some differences. Our work has mostly covered "if" at the moment ("only if" just recently reared its head) and "iff" still has a class or two to emerge fully. For now, I've made a small table to help me work through implications. It's neat how different "if" and "iff" ultimately are when determining information from a statement. Observe:

In these tables, we are checking to see whether our implication is TRUE or FALSE each time. What is interesting is that a regular "if" only limits a contradiction - when A occurs but B does not, even though A implies B. Anything goes if A does not occur, as the right column shows.
By contrast, "iff" excludes all results but the implication: B can only happen if A happens first (which is another way of stating "B only if A" - for this scenario at least, and as far as I can tell).

I don't know why the example comes to mind, but I like to consider an apocalyptic prophecy in this scenario. If 2012 or Ragnarok is upon us, then everyone will die very quickly. That's an "if" statement, and if 2012 or Ragnarok is NOT upon us (~A), then...?
Well, there are other ways to have everyone die very quickly. So don't get too hopeful if 2012 or Ragnarok is not upon us: that doesn't mean you're safe - there could be something else brewing. The Rapture, for instance.
The Rapture is a bit more strict compared to 2012 or Ragnarok. If and only if you were a good person while alive, you will go to heaven during the Rapture. If you weren't good enough, tough. Enjoy hell on earth.

One thing about "if" statements is that they can be more precise when there's fewer options. If a bit isn't 1, then it's 0. If a bit isn't 0, then it's 1. This can be used in statements in programs easily: if the value is True, then print "success!" Barring errors, you know that this code won't ever print anything aside from "success!":

def bool_success(value):
"""Return "success!" if value boolean is True."""
return "success!" if value

But again, now the "if" is just functioning as an "iff," since it's waiting for 1 particular possibility to occur. That's how I like to conceive of it: "if" checks for 1 possibility to produce the result, but doesn't care if another possibility triggers it (consider an "elif" statement which produces the same result after an "if", or an "or" statement within an "if"), while "iff" is the only way to get a particular result (all other answers lead elsewhither).

The other area I briefly mentioned that we touched on was Venn diagrams, a very useful tool for visualizing how areas interact. I am enjoying the opportunity to learn the new symbols ("for all" and "there exists," to name two) and the new terminology ("converse", "contrapositive") although I admit it can be disorienting if I lose focus. Nonetheless, all seems to mesh together in a fun set of patterns:
my TA imparted a very useful trick to remember when testing universal or existential claims, which he referred to as "big or small" - distinguishing between when an example or counterexample is needed (just one thing to find!), or when we need to prove no examples or counterexamples exist (check all the things!). This has helped somewhat.

From here on, it will be a matter of seeing how the Venn diagrams can grow more complicated: we've already looked at subsets and intersections - but is there any way a Venn diagram can express an "or" visually?

Sorting & Efficiency

I may be so bold as to say that everything we have done so far in this course has been about efficiency. The very nature of computing information is limited foremost by the resources you have to compute said information.

Hence, a computer which spends an hour doing something another computer can do in five minutes is going to be an inferior computer. However, a computer which can't run a code that another computer can run is perhaps not a question of better or worse computer, but of better or worse code.

And so we come to a question of efficiency, and one of the most important places for efficiency: sorting.

Once again I'm going to use a real-life analogy. If you have a bajillion eggs and you need one particular egg (probably because you're a crazy person), it would be horrible to look through each individual egg. However, if the eggs were, say, organized by colour or mass, then already you can discard any egg that isn't the colour or mass of the one you're looking for.

Heck, there are robots that do this for Lego bricks. But what of code, then?
Well,  code is wonderful for coming up with ways to sort things because there are a lot of different ways you can create a code to sort things.
Nonetheless, if we are indeed searching through our eggs, what is the best way to organize a hodge-podge batch, barring Rube Goldberg-esque machinery antics (as seen above)?
Well let's say for convenience all the eggs are lined up. We can compare each egg and place smaller ones to the right of larger ones (bubblesort), but there's no way you would be willing to just swap two eggs every time until you cover all the eggs - that would take forever with a bajillion eggs!
On the other end of the spectrum, you could divide up the eggs around the most average egg (quicksort), and then find the most average egg in each division and sort out which eggs are larger and which eggs are smaller. That goes much faster since you are working with smaller and smaller values-- wait, something smells like recursion!

Yes, that beautiful aroma of recursion is back. While something like grabbing two eggs and swapping them is all fine and well, it requires many attempts, usually as many as there are eggs - hence eggs squared to get through the entire thing. Yuck.
Rather, with quicksort or mergesort, we can look at smaller and smaller sets of eggs. When we work backwards, we can compare the sets and quickly organize them again, thereby finishing with a big sorted line of eggs after much less time since we are dividing the eggs into smaller sets (logarithmically smaller sets!).

Thus, efficiency is perhaps the most crucial part of sorting giant amounts of information (smaller sets can, of course, use more performance if the information needs to be found more quickly). With well-crafted code, and often recursion, it is possible to vastly reduce the amount of work we need to do when sorting or looking at other problems which require high efficiency. And so we can sort our eggs so much faster than before.

Assignment Two & Other Such Business

The assignments are now wrapped up, embalmed, buried. Good good.

This last one in particular was a bit of a struggle towards the end -- our code was developed very smoothly and efficiently, but with lots of clumsy extra parts, long strings of redundant code and a lack of polish despite the fact that it worked relatively well.

So we tore out its guts and rebuilt it. And there were a few scares when you realize a thing or two went missing during the process. One example was our implementation of regex_match, which took the longest of everything -- at one point, we were gathering every conceivable example which would work with a string, which led to exponential runtime for our niggling StarTree. We were able to fix that by taking out the helper function altogether and allowing regex_match to return recursive bools to answer other bools. Our StarTree ended up checking slices of the the indices of the string along the string's length until it found an example which conformed to the tree we were after, breaking it up into little pieces.

But then, horror of horrors, BarTree was returning True for things which should return False. Again, pen and paper had to leap to work to visualize what exactly was being done by the code to make it keep making this mistake. Lo and behold, there was an unnecessary line of code - a 'for' loop left over from the StarTree. What was lovely about BarTree is that the comparison was ultimately very simple: it's either one side of the bar, or the other side of the bar. Nothing else matters.

That, though it was a revelation within the final hours of our time with A2, proved exceptionally helpful in understanding the inner workings of the assignment and why the trees were an effective way of storing regex information.
Rather than relying on a string, which requires all manner of complicated indexing to break apart each time you want some information, a tree holds it all neatly and allows effective recursion. Checking the inside of another pair of brackets? Go a level deeper. Especially useful was the fact that the tree system made it easily visible what was or wasn't needed to investigate the code. You don't need to worry about a StarTree having a DotTree inside until you provide the answer to the DotTree. The StarTree cannot affect the DotTree's result. Understanding this albeit basic concept did greatly aid in contextualizing how our functions worked.

After the assignment is done, our sights are now turned to the midterm, and to runtime again. I can say that I understand the way runtime works, although I am not entirely sure that I can safely navigate it without a good bit of brain-training, which will undoubtedly be occurring for most of the week leading up to the midterm. I am sure I will have to revisit some 108 notes on sorting, but that should be a boon in and of itself anyway.

Progress

I had another "I'm going to destroy this computer" moment while working on E3 this week (the exercise name makes me so happy - look everyone, I'm working on E3!)

After hours of working on the code without progress, I gave up and slept. One Eureka moment and eight hours earlier, I fixed the code.

The error was an early subscription. Just a tiny, tiny miniscule [0] in the wrong spot. Down falls the house of cards.

In the end, I feel like it was so obvious: my code was returning tuples, and I was supposed to compare all the tuples and then use part of the end result. Instead, I was comparing half of all the tuples and using the part as the end result. The answer was so delicately thwarted off course, like a paper boat, that it didn't even seem like a possible error at first.

I stand by my love for recursion. Brian has reminded me in a comment on a post two weeks back that passing lots of changing parameters like that can cause a lot of hidden arguments to appear, but I think part of the beauty of recursion is that it works like a human mind. Your own mind will skip steps and store only useful information - it's not going to keep every part clean and neat. Perhaps that is the advantage of a computer, but perhaps it also makes it work more like you do. Which makes it easier for you to understand.

I'm still making progress though. Breaks are lovely, and a real privilege to have - code can't always be set aside and worked on later. But to be able to stare at something, try one thing, fail, draw out exactly what you want to have done, and jingle with the parts until it works is something so ritualistic, so mystical and magical, that I truly believe it is one of the greatest, most beautiful things about human innovation and problem-solving. No matter how advanced the computer, there will always be some information that must be discovered by hand. Until the computer isn't a computer anymore - then it's just a human which computes and diagrams its plans.

The brain often seems a lot like a bunch of floating nodes: you access one piece to access another, to access another, to access another.

In fact, what makes the brain so fancy is that you can have multiple nodes in a web, like Jimmy Neutron's brain in his old TV show. This point connects to this point connects to this point.
The brain is just recursively running through its own sub-trees of information, but really really well. If I want to eat, I start at my "hungry" root and go through a whole bunch of options - when, where, for what amount of time, with whom. If I want to have fun, I start at my "bored" root and check where, for what amount of time, with whom, doing what, when, how.

And then I get a nice list back of possible suggestions based on which trees I go into: Thai food after 6 with my girlfriend; video games for an hour until class.
It's creepy, in the sense of unexpected, how much this course actually has to do with life. Or maybe just my life. Because I'm a big nerd.

Moving Along

I wasn't so sure about linked lists at first. I'm still a bit confused.

I mean logically they make plenty of sense. You have an item connected to another item. But when it comes to implementation, I feel a bit like my head's come off and I don't know what to do with the rest.

The nodes and wrapper concept helped. It seems like what is to be learned this year in computer science is that pictures really are worth a thousand words. And that brings me to __str__ in code, because we need more stuff like that.

String representations came up a little with the assignment as well, so let's talk about them. Far and away, the nicest thing you can do for a user is make what they do as clear as possible. I have seen the countless times with my older family members: it must be really obvious what you're doing, otherwise you're going to miss it and get confused.

If your program doesn't identify what is going on well enough for a 75 year-old to follow along perfectly, you need to work on user interface and graphics, and the baby steps of that are definitely found in __str__.

I had a similar problem when we did trees: it is so much easier to visualize a tree when you draw it like a tree. Shocking, yes.

Linked lists, on the other hand, are actually really easy: a beautiful example was given on a lab handout. Just do arrows between values until None.

1 --> 5 --> 3 --> 2 --> None

Voila! Your linked list is easy to visualize. Of course, it's missing the levels of indentation, but presumably there will be some kind of understanding for the user that the elements are each other's rests.

For trees, you need some fancy indents. There was an example given in class, but in all honesty it didn't look very clean and simple. There's a good spot to find a nice way to code that sort of information.

And now the assignment, which at least for part 1 seemed deceptively simple. No string representations yet, just class design.

There was a good bit of time spent wondering how specific the classes should be: how much information should the user need to provide? We settled on some restrictions, but the nice thing again about the regex classes is that they shouldn't screw up and fail to be represented correctly because the specific subclasses can all be represented as regular regexes.

And the best part is? There's a string representation, and it's sensible. Very sensible. Part of the advantage is that a leaf's parent will generally be a fancy operator-type element that looks nice between values in our ternary alphabet ((0.1) or (2|0*)).

So that's this week's lesson: make your code visually helpful.

Recursion Returns

More about recursion this week, after a very good midterm.

In all honesty, recursion is probably the biggest thing I will take away out of what we have examined so far in computer science, and the reason is twofold: it's really useful and it is a very regular occurrence in day-to-day life.

Picture this: every time you perform an action to complete the same action again on a different number of things, you are doing recursion. For instance, you have a pile of eight books, and you want a book towards the bottom. Because I'm in a good mood we can do this with a picture.

------ Book A ------
------ Book B ------
------ Book C ------
------ Book D ------
------ Book E ------

We'll start with five and see where that gets us. Let's say the books are really heavy. Like, biology textbook levels of heavy. You can't move a whole bunch at once, but you need that damn Book E.
You could shove the pile over, but most of the time that creates a mess and risks damaging your nice books, so instead you remove Book A and Book B (I realize at this point I am basically recreating Assignment 1, but this proves it actually was a sensible assignment to write).

------ Book C ------
------ Book D ------  ------ Book A ------
------ Book E ------  ------ Book B ------

Now presumably you don't need the books in a particular order so you can put C and D on top of A and B (although if they had different sizes you would). Cool. But we just did recursion, guys. The pile is smaller so that we can do the same thing again for a smaller parameter, in this case books C and D.
That's recursion in your life right now, being all sneaky and recursive. What makes it so useful is that it is a wired-into-your-head feature for completing an action. Doing similar things in multiple steps is often recursive. It's to make things more efficient: that's why in language you can have recursive statements in which an inner part is embedded in a larger one, rather than repeating yourself or making two sentences.

This is what makes computer science recursion really neat, because it's letting our computers be more like our brains (of course, Skynet and all, but live optimistically). And computers aren't quite as good as our brains (yet) so recursion is even more useful for them.

Better example: packaging. There's a fair amount of "packaging"-type stuff in computer science, and when I say "packaging" I mean putting things within things within things, like you've got something in a package in a package.

Let's pretend I am really awesome and built a robot to wrap presents for me because I am the worst at wrapping presents. And because the wrapping robot was lonely I built an unwrapping robot to hang out with it. And let's, just for the sake of the example, pretend they wrap things like so:

Wrapper sees an object 'book'
Wrapper computes how fragile 'book' is and determines the value 2 (out of 5) for a little fragile
Wrapper decides it will repeat its wrapping algorithm a number of times until the book's fragile value is equal to its wrapping value (i.e. it is wrapped enough that there's no danger in it being damaged).
Wrapper begins to run its algorithm on 'book':
Start:
object: 'book'
fragile value: 2
wrap value: 0
fragile value != wrap value
First run-through: (put object in a list)
object: ['book']
fragile value: 2
wrap value: 1 (determined based on number of lists - can be found with recursion!)
fragile value != wrap value
Second run-through: (as before)
object: [['book']]
fragile value: 2
wrap value: 2 (as before)
fragile value == wrap value
object wrapped

Now the 'book' is wrapped through recursive run-throughs, so Unwrapper can unwrap it!
Unwrapper works like Wrapper but reversed, and without a fragile value because Unwrapper gets a little crazy - it just unwraps until the object's wrap value is 0.
Start:
object: [['book']]
wrap value: 2 (again, determined recursively)
wrap value != 0
First run-through: (take object out of one list - you can just re-assign object to object[0])
object: ['book']
wrap value: 1 (as before)
wrap value != 0
Second run-through: (as before)
object: 'book'
wrap value: 0 (as before)
wrap value == 0
object unwrapped

Tadah! The book was on efficiency, which is Unwrapper's favourite subject! What good friends those two robots are.

Thus, a simple example of recursion. You can make a code that sums the number of nested lists; even one which can work for multiple objects in the same wrapping.

But to hammer the point home, this is what makes recursion so neat. It has the power to understand more tasks than, say, a for loop (recursion works for any depth of object - a for loop on its own requires a certain number of specified inner loops). You can even make recursion only go a certain number of times!
For instance, say you have a very deep nested list and you want to go to a certain point and have the computer show you how deep you are. Well you could make a function which takes recursive depth as a parameter, and then reduce the size of that parameter each time you recursively run the function! I.e.

rec_depth([[[[[[[['eight layers deep']]]]]]]], goto=4)
so the code starts by checking the number of lists in and comparing that to goto - it's not deep enough so it starts again
rec_depth([[[[[[['eight layers deep']]]]]]], goto=3)
why is the goto changed? because the list is smaller, so its position is actually further up - this would continue until you get a goto of 0
rec_depth([[[['eight layers deep']]]], goto=0)
at this point, you would stop and do something else. maybe, for instance, the computer prints the new list, or prepends 'you are here' inside (so it prints [[[['you are here', [[[['eight layers deep']]]]]]]]).

Anyway, I think I've gone a bit over the limit here - that's recursion though, in all its glory!

Assignment 1 and Pioneering

Bit late but oh well, last week was rather crazy.

Assignment 1 is slain, and a mild repose has been won through Reading Week. Let's catch up, shall we?

The assignment wound up going much more smoothly than predicted. In 108, we had assignments that would paralyze us for hours with no navigable solution in sight. Now, it's a bit more clearly - something I think is in part thanks to classes.

As far as assignments go, A1 was actually pretty intimidating: making a functioning game?! We did that with the word-search in 108, but most of that was already written: here, all we really got pre-built were a few controllers for storing the sequences of moves and the graphical interface that wasn't even necessary to submit, since we would make a console interface anyway.

But lo and behold, it came together. Perhaps the worst moment was, after deliberating on the fastest possible recursion formula for hours, we looked through the handout again and saw that the formula was given to us. Ouch.

Nonetheless, that final part was by far the most interesting, since it required a fair amount of brain-work to complete. We did ours in three parts:
1. Finding the best i-value to solve for four stools. A somewhat ugly "best_min" function was made to calculate the ideal i by just running the formula and taking the best result. With that information, which was reinstituted for varying stacks of cheeses, we could proceed to
2. A four-stool function. Looking at the given recursive function, it worked in three steps:
a. Move n - i cheeses to a middle stool and stack them up.
b. Move the i remaining cheeses to the destination stool using the remaining three stools (since the remaining i cheeses were the biggest ones).
c. Move the old n - i cheeses to the destination.
This required a small bit of brain work, but Dustin's formula that he showed in class for three stools helped us deliberate on how to complete the work.
3. The three stool function, as shown by Dustin in class, for the middle step (2b).

That was the assignment. The other subject examined was related to the week's lab, which took on some fun and funky trees. I must say, the language can be a little defamiliarizing at first, but the diagrams are a godsend in computer science. I find it so helpful to see how our information is relating to one another, and trees themselves are very much built on creating that sort of diagram-form. It would be fun to develop a graphical interface to display that kind of information neatly.

The one thing I still need to wrangle before the midterm shall have to be linked lists, which seem straightforward enough (I can reason the idea of a "head" and a "rest") but shall require more review before they become entirely clear. As well, looking over old midterms I find my mathematical brain is getting a bit dusty - complexity requires due review to deliberate how complex a code is (i.e. how many operations needed in worst-case scenarios, with all these simple O(log n) and such algorithms.

A-cheese-ment

The profs have a sense of humour. That's good. It's a necessary tool in life, in my opinion.

This was an amusing week. Busy and enlightening, too.

More recursion was on the plate for the lab, and our instructor suggested we "trace" our code as we went. Basically, take down the simplest form and then add levels of complexity. Such brilliance.

It may not work for everyone, but tracing works fantastically for me. Seeing how the code is "built" has always been helpful (I'm a visual learner, as humankind likes to compartmentalize nowadays), but actually going through from simple to complex is brilliant. It made such a difference when puzzling out the code (lo, we did puzzle out that code!)

The pain of computer science often lies in the discovery of the tiny error that made you waste half an hour when all it required was more care. I used to make mistakes like that in math class, where one small problem (forgot to change the sign when moving something over, usually) made me burn in hell for eternity.

We had that sort of thing during the lab. Thankfully, it was resolved before we called it a night, but still, not fun.

In other news, I appreciated the experience of sitting front and centre in lecture - it is great for paying attention. And A1 is surprisingly easy once you parse all the pieces out and make sense of it all.

Ultimately, 'twas a week of good cheer and good learning. I understand all the more the value of being a careful programmer and working with visual aids. It doesn't require a full map of every assignment and value, but just drawing out what you're trying to do is a huge help.

The Topic of this Post is "The Topic of this Post is 'The Topic of this Post is "'The Topic of this Post is...

Recursion may not be this week's official topic of choice, but it's a topic of discussion nonetheless, and a very intriguing one at that.

Recursion as a concept is not completely novel: I am also encountering it in Linguistics, which provides a sort of "compass" to how I should navigate the notions (or n-oceans) of recursion.

In a more CS-way, however, recursion is another example of obviously helpful computer logic. To go back to linguistics, recursion occurs when you embed a clause inside another ("when you embed a clause inside another" is an example of language recursion). Recursive humour occurs in the post title, or when I tell you that "to understand recursion, you must understand recursion."

If I want to write a program to track recursion in a string, I could write sentences into a list. For instance:

"Alice looked out from the window, where she watched the birds that ate worms in the yard, and waited for the mailman who came down the road each morning when it wasn't raining."

If I make lists within lists to show the embedded clauses:

['Alice looked out from the window,', ['where she watched the birds', ['that ate worms in the yard,']] 'and waited for the mailman', ['who came down the road each morning', ['when it wasn't raining.']]]

A program which did this would obviously need to be pretty complex. In the example, we can see that we would need it to end the current clause each time a preposition ("where", "that", "who", "when") appears, find some way to distinguish conjunctions ("and") as linking to a different clause, and ending a clause when punctuation or a preposition or a conjunction (sometimes) is encountered. Pretty complicated, but if we say that we can divide it up properly already, then all that is needed is for the program to check if there is a preposition introducing a clause, in which case, it calls itself recursively a creates a smaller list within the list. Otherwise, it encloses the current clause and moves on.

Of course, we discussed other uses for recursion in class that were more simple: using it to create "treebursts" with the Turtle program, or removing 3s from a nested list.
The treebursts were amusing to fiddle with: changing the level caused the recursion to go deeper, and at one point I was able to make the function create a large hexagon made up of smaller hexagons and triangles by fiddling with the number and length of the branches (although colour had to be disabled as there were only three colours given originally). The program was nonetheless very good at literally illustrating the use of recursion, which I now can see coming in handy in the looming assignment 1 (we discussed the formula briefly in class, which only served at first to bring back dark memories of examining the continuity of graphs in math class).
Removing 3s was a simple example as well, but still powerful, although the main thing I took away was the use of "continue" to keep the while loop moving.

The course feels more organized all the same. I still occasionally feel a bit daunted when staring at a new exercise, but the lab-work is always a great aid in providing relief in that regard. I couldn't help but feel a sense of achievement when the class Vehicle code we worked on in our lab was mirrored on the prof's screen in class.

The one last thing I have been really noticing is how much everytime I interact with technology, I envision the code underneath. While watching someone play solitaire, I imagine how the computer stores and displays the information (a list could hold the cards randomly assigned to each line, and another list holds the remaining deck; rules govern whether cards can be moved from a list to another based on stored variables). I look forward to a chance to see how we create the graphical interfaces used by programs in future CS courses. For now, I can simply ponder the code behind it all.

OBJECTS ORIENTED WITH PROGRAMMING POW

Python, though it is named after the delightful sketch comedy group, in essence actually best resembles the mythological monster which gave every other python (snake or comedian) its name.

Nonetheless, this Course bLOG (courSe bLOG is a lame name) begins with a little discussion of Object Oriented Programming [Stuff] (OOP[S]).

Dealing with this form of programming was a bit jarring at first. I had some experience with objects at first from the last semester's computer science class, but I was not out of the proverbial jungle yet. My old knowledge was simple and undeveloped. Now was the time to enhance.

Our first forays into OOP involved actually conceptualizing those very objects that we were to orient using programming. Points, turtles, graphs - nothing was safe. We drilled through it all. It was fast (and occasionally furious), but it made sense with the help of additional online information and the variety of painful educational exercises upon which we embarked.

So it came that we were building classes, which are really cool and useful. Extremely cool and useful. I like classes and objects a lot, and the magical combinations they create. Basically, we were developing a variety of classes based on what we had to complete (so for Point, we needed an n-dimensional point). This is the fun part, because we got to plow through what kinds of tools we should use to create the Point (at this point [ha ha] we were working with ADTs). The methods are fun and all, but what was fascinating is how logical and simple this process is. Much like how we organize our various tools for each problem we encounter in the regular world (for instance, if you're building IKEA furniture, you prepare to lift things, use the little allan-key thing, or screw stuff in). Python's OOP works the same, which was really refreshing to understand (given that I made the connection independently) and made it seem clear how we were supposed to approach these kinds of problems.

Actually writing methods was simple enough. We had done plenty of that in the past; albeit, without the conveniences of the classes. What was ultimately the most interesting about using objects was the way it organized development. If we wanted to develop a class that stored how a person did something complicated, like fill a spreadsheet, it was possible to do so. That was vastly daunting before as a pile of methods would have redundancies and ambiguities, but using classes we can signal what we want to do clearly and concisely in an organized way. It was heaven.

This week has nonetheless been an effort in compiling thoughts. The increased amount of abstraction is a boon and a curse: on the one hand, it gives us the possibility to develop code that is specific enough to accomplish our tasks (a class for a graph, for a restaurant menu, or for a calculator), but which also requires us to think about how we divide up the concepts (for the above examples: putting points or lines, adding meals or wine items, or adding mathematical operators). The topics we discussed in the lecture: developing superclasses or subclasses just bring the whole thing together. Now we can create even more specific functions within our code: a menu of operations for the graph, or a form of the calculator that only performs simple arithmetic (i.e. it can only compare two operands at a time). The power is almost overwhelming.

Ultimately, the first few experiences have felt disorienting and confusing at times -- but also really cool. It's clear that the way object oriented programming is going to work will be really useful for solving problems, in the sense that there is a giant pile of information before you, and you organize it into meaningful chunks which perform clear tasks. It's more cooperative, and it feels like I may be edging towards actually being able to finally build a program that will live my life for me and win fame and fortune in my stead. I can't wait.