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...