Building things that matter

Code Challenges

The Shell Game (Ruby)

This was an interesting one.  I have not made a game in a while so the thought in this one was a little more complex than some others.  My solution is far more complex than other solutions on CodeWars, however I do think it represents a more real world and extensible solution, which is kind of one of my things. 


"The Shell Game" involves three shells/cups/etc upturned on a playing surface, with a ball placed underneath one of them. The shells are then rapidly swapped round, and the game involves trying to track the swaps and, once they are complete, identifying the shell containing the ball.

This is usually a con, but you can assume this particular game is fair...

Your task is as follows. Given the shell that the ball starts under, and list of swaps, return the location of the ball at the end. All shells are indexed by the position they are in at the time.

For example, given the starting position 0 and the swap sequence [(0, 1), (1, 2), (1, 0)]:

The first swap moves the ball from 0 to 1
The second swap moves the ball from 1 to 2
The final swap doesn't affect the position of the ball.

swaps = [[0,1], [1,2], [1, 0]] find_the_ball(0, swaps) == 2

There aren't necessarily only three cups in this game, but there will be at least two. You can assume all swaps are valid, and involve two distinct indices.

My Solution

I broke this game into three distinct parts conceptually.  The Game Setup, where you walk up and the game master puts the ball under a cup.  The Cup Swapping, where the game master moves the cups around and you try to keep track of where the ball is.  And finally, what is the main method of this challenge, where you Find the Ball.  

The Game Setup

Game set up was an interesting challenge as, while the game is usually played with three cups, the challenge called for there to be up to 10 cups that could be in play.  So my game_setup method handles several sub tasks.  It sets up the game board, creates the number of cups needed on the board and places the ball under one of the cups as specified by the start parameter.

Game Setup Method

To get the number of cups that may be needed, I flattened the arrays for the swaps and pulled the highest number and added 1 (to account for the 0 index).  From there, I ran an until loop and created the number of cups needed for the game board based on the highest number on the swap array. 

My cups are hashes (you should know me an my hashes by now) and those hashes are configured as follows: 

{ cup_0: { space_position: 0, ball: false} }

The space_position will keep track of where that cup moves as the game is played and the ball attribute simply allows us to know if the ball is under that cup or not.  It will default to false when the cup object is initially created because we will set up our table first, and then put the ball under one of the cups. 

This brings us to the third step in the setup method, the placing of the ball.  We get start as an attribute in our parameters at the onset, so I iterated over my hash of cups, and whichever cup's space_position was equal to the start parameter, that cup has the ball placed under it by changing it's ball attribute to True. 

With that, our game board is set up.  We have a number of cups that we have set up, we have found the person we are going to challenge, and we have placed the ball under one of the cups.  Now we are ready to swap the cups.

Cup Swapping

Once set up, the swap_cups method is the heart of the game.  As with the game_setup method, the swap_cups method is also handling three subtasks.  First we are identifying which cups we are going to be working with based on the swap values we have been given. Second, we execute the swap and set our hash that we will be updating, and finally we merge our original board with our new board to change the positions of the cups.

Swap Cups Method

The swap_cups method actually only takes one swap pair at a time so that it focuses on just the two cups at any given time.  Other ways I tried doing it passing the entire swaps array into the method were too complex, so I decided, in the end, when you are swapping two cups, they are the only two you need to worry about until you are ready to swap the next two.  So I handled this with one swap pair at a time. 

One gotcha on the updating of hashes is that you have to recreate the entire hash to merge, if you attempt to only update a portion of the hash, in my case the space_position is the only value changing, it overwrites the other values, like ball and you lose the granularity and detail of the cup when you merge it.  So each hash update includes a restating of data that didn't necessarily change but that is needed when we merge with the original board hash, which is the final step of for the swap is to merge the new positions with the old to update.

This occurs after every swap, so our board actually updates multiple times in the background while we iterate over the swap pairs, and once done, we have our updated board which is now a shuffled version of our original. 

One way to see this was to print out the board positions before and after each swap.  At the start, our board looked like this, with the ball under cup 1.

Initial Position: [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

Our first swap pair was [0,9], indicating that cups in positions 0 and 9 will switch places, causing our board to look like this:

Swapped Position [0, 8, 7, 6, 5, 4, 3, 2, 1, 9]

In this scenario, we carry out another five swaps ( [9, 3], [3, 7], [7, 8], [8, 2], [4, 5] ) which leave our board looking like this at the end of our swapping:

Swapped Position [0, 7, 3, 6, 4, 5, 9, 8, 1, 2]

You'll note that at no point do we move cup 1, which means that our ball is still in the same position it was in when we started the game so the answer to this sequence will be that the ball is under cup 1. 

Find the Ball

Finally, we are ready to execute our main method of find_the_ball.  This method combines our other two methods with one final action, and that is identifying the correct cup the ball is under.  So we first set up our game board, we then do all of our swaps and finally we return the correct position by looking at our board and selecting the cup where our ball value is true.

Find the Ball Method

One thing to note, as mentioned in the swap_cups method, we only handle one swap at a time.  So in our find_the_ball method, we take our array of swapped pairs, iterate over all of them and call our swap_cups method on each of them.  Because we update our board at the end of each swap, we have the most recent modified board at our disposal for the next swap, instead of reverting back to the board in its original configuration as we started with. 

Yes, as per most of my code challenges this one is far more complex than many of the solutions on the site.  However, by using the hash we have the ability to add functionality in now that other solutions cannot. 

Let's say we want to limit the number of times a cup can move, we can add a move_limit value to the hash and track that as the cups move. 

Or lets say we want to limit a space a given cup can go, we can add a space_refusal value to the hash that we can use to prevent certain cups from going to certain spaces. 

This allows us the ability to create some very complex algorithms with what started off as a simply shell game. 


Robert Cornell