#algoviz

[100daysofalgorithms]

Day 73 - Tower of Hanoi

Tower of Hanoi is a classic puzzle.  The goal is to move all blocks from one column to another column while preserving the order of the blocks.  The trick is that at no point can a larger block be on top of a smaller block.

[100daysofalgorithms]

Day 100 - Linked List Cycle

How can we check if a linked list has a cycle in it?  There’s a pretty clever way to do it - keep two pointers, one that moves forward by one node (blue), and one the moves forward by two nodes (black).  If there’s a cycle, then the black node wrap around and “catch” the blue node.  If the nodes never overlap, then there can’t be a cycle.

[100daysofalgorithms]

Day 90 - Chaos Game V3

I was curious to see what other patterns would emerge from the chaos game process.  This animation loops through regular polygons, decreasing the number of vertices.  There are patterns to be seen, somewhat like the Menger Sponge, but they’re tough to see without more points,

[100daysofalgorithms]

Day 99 - Flatten a Nested Array

If we get an array that has other arrays in them, which in turn could have more arrays in them, how can we flatten the structure out to a single array?  We simply look at the type of the element, and if it’s an array, we recursively apply the same flatten functionality. 

[100daysofalgorithms]

Day 91 - Matched Brackets

A programming problem I came across recently.  The goal is to figure out if a string of brackets is balanced (i.e. closed properly).  The idea is to add open brackets to a stack, and when we encounter a closing bracket, if it’s matching open bracket is at the top of the stack, then we know we have a match and we remove the top of the stack.  If at any point we find a mismatch, we return that the string is unbalanced.

[100daysofalgorithms]

Day 98 - Anagrams

How can we tell if strings are anagrams of each other, i.e., they have the same letters, but the order doesn’t matter.  So “monk” and “konm” are anagrams.  This one is really easy, we just sort all the strings, then we can directly compare.  But how can we improve the comparison step so we dont’ have to compare every sorted word against every other sorted word?  We can use a dictionary to store sorted words as keys, and all their unsorted words as an array.  Then, we simply do a dictionary lookup, which is constant time, and then we just have to compare our input word to the words in the anagram dictionary.

[100daysofalgorithms]

Day 97 - Next Smallest

Another programming challenge question.  This questions asks you to, given an array of integers, find the next smallest integer for each integer in the original array.

[100daysofalgorithms]

Day 93 - 100 Doors

Another little puzzle.  You have 100 doors that are initially closed.  First, you go through each door and toggle it (if it’s closed, open it; if it’s open, close it).  On the first pass, we just open each door.  On the second pass, don’t visit every door, but visit every second door, and toggle it.  On the third pass, visit every third door and toggle it.  Continue this pattern (i.e on the 47th pass, you visit every 47th door - which is just the 47th door and the 94th door) until you’ve performed 100 passes through the doors.  What’s fascinating about this puzzle is that the open doors will always be the perfect squares; that is, the 1st door, the 4th, the 9th, the 16th, 25th, 36th, and so on.