Depth First Search - For Babies!

Old MacDonald Had A Farm

I wanted to play around with AWS Polly, which is a service that converts text into speech for you. What better way to test this out than with an "Old MacDonald Had A Farm" song generator. But first, I needed to do some research. Song Variations There are actually many different ways to sing this song. I spent a few minutes listening to various versions and here are some important differences I discovered: The list of animals is different every time. The Wiggles version shortens the previous animal sounds so there is no "here a woof, there a woof, everywhere a woof woof". They simple sing "woof woof here, woof woof there". The previous animal sounds can either be in order, reversed or left out entirely. Generator Program The code to generate the lyrics is quite simple. I have it uploaded on Github . For every animal in the given list of animal names/sounds, it writes a verse. Each verse has a intro lines ("Old MacDonald had a f...

Word Changer

I found this little challenge in a puzzle booklet and instantly thought "I wonder if I can get a computer to figure this out for me?". Not long after that first thought, I had a second thought "I wonder if I can get a computer to give me the LONGEST chain of words!". The source code for this project is on Github . Version 1: Find Longest Path I figured that finding the longest chain will probably take a lot of compute, so designing for performance was a priority. Dictionary words We need a list of English words and we need to be able to quickly check if a word of a certain length is a real word. For this, I created a hashmap where the key is the length of words and the values are a set of all words of that length. A set gives us constant-time lookups, which we definitely need. Search Algorithm Next, I needed to decide an overall approach to take to find the longest path. For this, I decided to use a depth-first-search algorithm. This algorith...

Karl's Blog

Search This Blog