Prefix/Infix/Postfix

Why can't we all use prefix or postfix notation and get rid of those silly brackets?  I think the answer is people don't like spaces (and/or people have messy handwriting).

Brackets are annoying and quite confusing to read especially when there are a lot of them, and tracing which bracket goes where is even worse.  Consider:

((3*x) + 2) * ((4 / (sqrt((2*y) - (3*z)) - (((((3*4) + 2) - (17*x)) + (y^2)) - 14))) + 5)

 

All the brackets and if you mess that up, retracing brackets is annoying.   

Then we came up with putting the operation before or after the arguments (prefix and postfix respectively), thus doing away with brackets entirely.

Here's postfix: 

3 x * 2 + 4 2 y * 3 z * - sqrt 3 4 * 2 + 1 17 x * - y 2 ^ + 14 - 5 + - / *

Not only is it shorter but also much cleaner.  Every argument is clearly defined (by spacing) and there can be no confusion about what is added to what and what isn't.  Reading left to right, you store arguments as they come, and every operation acts on the last two arguments processed.  Done.  

Prefix: 

* + * 3 x 2 / 4 sqrt - * 2 y * 3 z + - + - + * 3 4 2 * 17 x ^ y 2 14 5 

Read left to right and every operation is stored and when 2 arguments come up, use the first operation on the stack on them.  Also much easier.

I generally like postfix better because storing arguments makes more sense in terms of that an equation processes values and should thus output values instead of operations.  

Either way, it's obvious that this notation doesn't take nearly as much space or effort in processing - so what the hell are we still doing with that silly infix notation?  Spaces.  People don't like putting in spaces and people couldn't be bothered to make their writing look neat.

Silly people.

Towers of Hanoi

I wanted to rant about recursion but apparently I have to save my pent-up anger about that until week 7.

Let's talk about that damn assignment Towers of Anne Hoy (or Reve's Puzzle).

It was pretty quick to design a fast algorithm (called Hanoi4):
For 1 cheese, just move it.
For 2 cheeses, operate move one to an intermediary, move the second, move the first back.
Then for n>2 cheeses, recursive, operate the 2 cheeses method, recursive again.

I found the optimal move counts up until ~20 cheeses on the internet, and found that this quickly-designed, rough algorithm only displayed the optimal number of moves up to about 5 cheeses.  Not very effective.

Refining the algorithm was not very difficult when I decided to actually look at the method stated in the problem: actually using the original code for the Towers of Hanoi in the algorithm.  Thus it was simple to perform:
Hanoi3 - if 1 cheese, move straight to destination
              else Hanoi3 (cheeses - 1) to an intermediary, move from source to destination, Hanoi3 again.
Hanoi4 - if 1 cheese, move straight to destination
              else Hanoi4 (cheeses/2) to an intermediary, Hanoi3(rest of cheeses on that stack), Hanoi4 again.
This solution displayed optimal move counts up to about 8 cheeses, but upon getting 9 cheeses, the solution would start being non-optimal again.

It was obvious that the proper number of cheeses to move to the intermediary, i, was not half the number of cheeses.  This prompted me to re-read the question once more for the clue.  Turns out it is ABSOLUTELY NECESSARY TO HAVE A FULL UNDERSTANDING OF THE PROBLEM BECAUSE THE ANSWER IS STARING YOU IN THE FACE.

FRAAAAAAAA-

How do you find the optimal solution?  Use the optimal moves.  How do you find the optimal number of moves? IT'S GIVEN TO YOU.

Then having found the optimal number of moves using an algorithm it's simple to find to optimal i number.  This turned out to be:
1,1,2,2,2,3,3,3,3,4,4,4,4,4...

Doesn't even take a cryptographer to figure out the pattern on that one.

FRAAAAAAA-

Data Structures

Organization of concepts overlaps many branches of science, and thus the invention of organizational schematics for different purposes is convenient and efficient.  Computer scientists like calling them data structures.

There are the most simple ones - stacks and queues.  Only one output is possible when calling for something from either of these, and they are mostly useful when running a program and ordering what needs to be called.  They don't really interest me that much.

What does interest me are trees.  By following a specific guided set of rules, a tree can be produced based on the data that only comes in one order.  The first one I learned of these was the "binary tree" in which values were ordered by lesser and greater (lesser values go left, and equal or greater go right, so on and so forth).  These allowed a word to be broken down into letter components and then quickly alphabetized.  

But then you can apply whatever rules you like.  Equations are actually written in this format, where the operation is a branching point, the left argument goes to the left, and the right argument goes to the right.  Brackets are used to infer the (leftbranch node rightbranch) setup in an infix equation.  As a result, prefix and postfix notation are actually just writing a tree, with no "branches", and in one line.  In linguistics, the same thought applies to syntax; i.e. a sentence can be broken into their parts, verb phrases, noun phrases, etc.  

Trees are a useful ordering system and I'm probably gonna try to learn all their nuances.