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.