The Locker Problem

I was recently given a puzzle to solve in Ruby called “The Locker Problem”. Hearing it for the first time kind of made me feel overwhelmed, but that’s what motivated me to try to solve it. After a lot of thinking, I’ve finally figured it out. The solution actually ended up being a lot simpler than I made it out to be in my head. Here’s the puzzle, as well as the solution and my thought process in solving it:

In front of you, there are 100 open gym lockers in a row.
You walk around the entire row 100 times. The first time,
you stop at each locker and close all the opened ones. The
second time around, you stop at each 2nd locker and open
the ones that are closed. The third time around, you stop at each
3rd locker and close the ones that are opened and open the ones
that are closed. You continue this pattern until you’ve done it a
total of 100 times.
At the end, which lockers are opened and which are closed?

Did reading that puzzle make your head hurt? This is actually pretty simple to solve after breaking it down piece by piece. First, I’ll show you my solution:


As you can see, it doesn’t take a lot of code to solve this puzzle but there’s a lot going on. Let’s break it down.

First we create an array representing 100 opened lockers (true == open). For our loop that will represent walking around the lockers 100 times, we use 'i' as a placeholder and assign 1 to it. This will represent the first time walking around the lockers, stopping at each locker. Therefore, 'i' will represent the rounds we take around the lockers. At first glance, it may seem to you that we’re only walking around the lockers 99 times but remember that we’re already starting at the first round (i = 1) and therefore adding 1 to 'i' 99 more times. Totaling 100 times that we’ll walk around the lockers.

(0..open_lockers.size - 1) is a range from 0-99 that represents the index positions of all 100 lockers in our array. .step is a method that iterates through a range and passes every nth element to the supplied block. For example, lets say we’re walking around the lockers for the 2nd time. This means that 2 will be supplied to the .step method as a parameter. .step will then start at 0 and pass each 2nd element to the block, including 0. (0, 2, 4, 6, 8,…). If this made you notice a potential problem with properly identifying the lockers, then you’re doing great (I figured it out the hard way). The problem is that if we’re trying to identify every 2nd locker, the 0, 2, 4, 6, 8,… index positions are actually going to identify the 1st, 3rd, 5th, 7th, 9th,… lockers. This is why we subtract 1 from the index positions to properly identify the correct locker that we’re trying to access within the array. So in actuality, the index positions we’ll be accessing are [-1, 1, 3, 5, 7,…]. This will properly identify every 2nd locker (100th, 2nd, 4th, 6th, 8th,…98th). Now we can be certain that all 100 times that we walk around the lockers, we’ll be closing or opening the correct ones.

We then use a boolean expression (or flow control) that represents closing a locker if it is open, or opening a locker if it is closed.

Lastly, we pass the each_with_index method to the open_lockers array that iterates
through the array, grabbing each locker and it’s index position. We then use string interpolation to add 1 to the index position to properly display the locker onto the screen. i.e. Locker #1 instead of Locker #0 (that wouldn’t make much sense). We also use string interpolation to display “Opened” onto the screen if the locker is ‘true’ or “Closed” if ‘false’.

Tagged , , , , ,

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: