This post is part of a series on Mohammad Anwar’s excellent Weekly Challenge, where hackers submit solutions in Perl, Raku, or any other language, to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.)
For challenge #2 this week, the task is to start with $1, and by either adding $1 or doubling the amount, reach $200 in the smallest possible number of steps.
“Greedy never works”
In a 75-minute lecture some decades ago, my Advanced Algorithms professor said, over and over, “greedy never works,” while all the while showing us exceptions to that mantra. Greedy algorithms operate by always making the locally optimal choice, which might be the biggest/smallest, closest to the goal, etc., depending on the problem. However, for a great many problems, the locally optimal choice is not always the best. For example, suppose you’re trying to climb the following mountain range (The ASCIIHorn):
B
/\
/\A / \
/ \/ \
/ C \
Let’s say you’re at position (A), and your goal is to find the highest point. A greedy algorithm would always choose to go higher, never lower (even temporarily), so you’d reach the smaller left peak, and be stuck there. This is known as a hill climbing problem, for which greedy doesn’t work, because you have to go down through the valley (C) before you go up to the goal (B).
Continue reading “Make it $200”