Linking it all together + a cool little monkey thing...

Alas, another week, another blog post.

Despite the dawn of Assignment 2, I want to spend this post talking about linked lists, and some other stuff.

I've had some experience with linked lists in high school - but it was at a pretty basic level. Making a list out of nodes, traversing it, finding items, adding, inserting removing, etc - basic stuff. However we also got to deal with some other interesting things. For example, what if each list node contained not only a pointer to its next node, but also to its previous? This would be a Doubly Linked List. Something like this could be visualized practically in something like a web-browser - every page gets added to the end of a list and you can go back and forward in the list, one element at a time. Another type of linked list is a Circular list (I like to call them Circly lists, you'll see why in a bit) - and its feature is that the last element points back to the first. Now what if you take a doubly linked list and link the head to the tail and vice-versa? You get a Circly-Doubly-Linked-List! As comedic as the name seems something like this is quite applicable. Lets take a music playlist as an example. Each song is a node and is doubly linked to its neighbors (so you can skip forwards or backwards). Now what happens when the user turns on "Repeat Playlist"? The first and last nodes get linked, and so the list becomes a Circly-Doubly-Linked-List.

On a totally unrelated note...
Now remember that other thing I wanted to talk about? Well here it is. In High school we got a quite interesting recursion assignment and I thought I would post it here for those who want to take a shot at it - the comical nature of the whole thing combined with the decent challenge makes it a good load of fun. I also think its kinda up the same alley as A2 (just much simpler of course).

Monkey Words

Your goal is to make a program (in any language of your choice, I did it in C#, you can use python) that will determine if an input word is a monkey word (a word from a monkey's vocabulary).

A Monkey Word can be one of two things:

-It can be an A-Word

-Or it can be an A-Word followed by "N" followed by another Monkey Word.

An A-Word can be one of two things:

-It can be just the letter "A"

-Or it can the letter "B" followed by a Monkey Word followed by "S"

Here are some examples of valid words:

BANAS

BANANAS

BASNANA

BASNANANBAS

BANANANANBANASS

BBBANANASNANASNANASNA

Here is a link to two text files you can test with (each line is one word) as well as my version of the program (so you can test your own words and profile [time] your algorithm).

All the words in False1.txt are not valid Monkey Words, and all the words in True1.txt are valid words.

http://snk.to/f-chjqv35k

My algorithm is a total of two methods and 44 lines (including whitespace and documentation).

Let me know what you think of the problem! Was it easy? Hard? If anyone is interested I can post my solution next week.

Well this was quite the post. I hope you enjoyed reading it, and please comment and let me know what you think. Until next week!

Barking up the wrong tree

This week has been a lot about trees. Obviously I mean binary trees not wooden ones. We've been traversing them, picking them apart, and building them back up. As much as I've heard about binary trees before, I've never actually gotten around to seriously working with them. As much as I dislike python syntax, I have to admit that working with trees is much easier in python than the other languages I'm used to.

I'm writing this blog a bit later than I should be (tuesday as opposed to last friday) but at the same time I want to take this opportunity to talk about the new assignment (and exercise). Regular expressions are quite an invaluable tool, and I'm really looking forward to learning about them, even at the simplified level we are provided with. I'm currently working on a personal project, a component of which is document traversal and indexing, and I think regular expressions are just what I need.

Regular expressions are not exactly intuitive however. With expressions like
^[+-]?(\d+\.?\d*|\.\d+)([eE][+-]?\d+)?$ readability is obviously a concern (looks like what they use to censor swearing in cartoons), but I'm guessing its just a matter of getting used to.

As for exercise 5 - it seems pretty straight forward. Part A is obviously significantly easier requiring a simple traversal of the tree and passing along an integer. As for Part B, it seems like I could use a similar recursive traversal as Part A but store the roots separately. I really haven't given all that much thought to it yet, but it does at least seem easier than E4.

Well, that concludes my slog for today (pun intended), thank you for reading it!

P.S. I'm looking for a better name for this blog, suggestions appreciated!

Cheezus

I've never blogged before. I've haven't really even read blogs before. But I guess there's a first time for everything. Here goes.

Alas, the first assignment is over. There was a lot of recursion, and just as much hair pulling.
In the end I did accidentally submit the assignment with the number of disks hard coded, but I fixed it shortly after, and hopefully Danny will consider my new version, since its just a one line difference. I found it interesting that the method that found the ideal value of i (where i is the point at which to split the original stack of cheese) exponentially increased in the time it took as the number of cheeses increased. I'm assuming this is because the method is both iterative and recursive (recurative?), but it made me wonder if there is a more efficient way of solving the problem.



In this post, I also want to comment on OOP and recursion.

OOP is Object Oriented Programming and in my opinion one the most important things to get a solid grasp of in the programming world. Object oriented programming means representing every component of your program as exactly that: an isolated component, in your code. Every component needs to care about itself and only about itself. This concept is extremely useful in organizing code, keeping it neat and tidy, as well as easy to follow. It goes hand in hand with other concepts such as inheritance and polymorphism.

Recursion is a simpler concept to grasp - it is simply when a method or object calls or refers to itself to accomplish a task. Recursion is very useful for specific types of problems, but a lot of problems don't necessarily require it. With that said, the problems that do need a recursive solution, can often be solved with an iterative one, but the recursive one is often more efficient, more flexible, and shorter.

Well that settles the end of my first slog. Please leave comments and feedback since, again, I've never blogged before so I would love to know how I'm doing.

Until next week!