Proficiency Assignment: Cartagena

Topic: Greedy Algorithms.

In the board game Cartagena each player controls a small gang of pirates attempting to escape from the titular fortress along a narrow and twisting corridor. Each space on the board is marked with one of $6$ symbols, and each segment of the corridor contains the same $6$ symbols although not necessarily in the same order. $($In other words, the corridor consists of $6$ different symbols, followed by the same $6$ symbols in some other order... followed by the same $6$ symbols in yet another order... repeated until the end of the board.$)$ Players move their pirates by playing cards; a card with the Hat symbol on it$,$ for example, can be used to advance a pirate to the next Hat space on the board.

The game itself is a balancing act of getting the cards you need at the right time and moving the right pirates in your crew, but for this assignment let us consider a simple scenario with only one pirate to move and only one turn to worry about:

Consider this simple greedy algorithm for how to play out your entire hand, moving your pirate as far along the corridor as possible:

Play the card that will move you as far along the corridor as possible. Repeat until your hand is empty.

Unfortunately, this algorithm is not optimal! Construct a counterexample showing how it does not always work.