I hate algorithms. I love puzzles, but somehow when l combine logic puzzles with JavaScript (especially in the context of an interview, which seems to be the only time I deal with these) my mind blanks completely. So in an effort to improve my algorithmic thinking skills and also make solving algorithms more fun, I finally got the book Algorithmic Puzzles by Maria and Anany Levitin.
This book presents well known and less common puzzles that can be require the computational, algorithmic thinking that is present in computer science, but there is no code in this book. These are not coding challenges. Rather, they are all about the fun of thinking through a puzzle rather than the process of translating a solution into code.
I'm starting with the easier puzzles for now and many of these blog posts may fall into the category of "well, duh", but also I find seeing how other people's brains work to solve algorithms like a nerdy personality test, so this may still prove interesting.
The Problem
The basis of this problem is a man trying to ferry his belongings across a river in a boat that can only hold one thing at a time. The book tells me it is one of the OG logic problems, originally written in Latin.
A Wolf, a Goat, and a Cabbage
A man finds himself on a riverbank with a wolf, a goat, and a head of
cabbage. He needs to transport all three to the other side of the river
in his boat. However, the boat has room for only the man himself and
one other item (either the wolf, the goat, or the cabbage). In his
absence, the wolf would eat the goat, and the goat would eat the
cabbage. Show how the man can get all these “passengers” to the
other side
Solving Process
First, we have to mull. I'm in Scotland at the moment, so I'm doing this with a glass of Scotch in a pub that is definitely older than the U.S.
This problem was a nice introduction puzzle using the space state graph introduced in the book's tutorial. In this problem, my space state graph looks like this:
This means 7 trips is the fewest number the man can make to get everything to the other side with no loss.
These graphs will become more complex. With this one, it was relatively easy to see which options would more quickly field the right answer, reducing "wrong turns" in my solving process. As a result, this felt like good practice with this technique and maybe a good warmup for future puzzles.
I'm wondering if I should alternate easy, medium, and hand, but I'm also on vacation and have had more than a few whiskies so anything above easy might be more than I can manage. Cheers from Edinburgh!