How to Solve a 1 kyu Kata on Codewars (or any difficult programming exercise)
TLDR: To solve a 1 kyu kata in Ruby, all you have to do is override the equality operator method so that all the tests will automatically pass! (Just kidding — please don’t do this.)
I came across an interesting kata (programming exercise) on Codewars last week, called 6 by 6 Skyscrapers. It looked deceptively straightforward at first, because it didn’t contain any advanced computer science topics like some of the other 1 kyu kata. It ended up being very challenging though, so I had to work on it for four days before finally solving it.
Sometimes difficult problems like this can be frustrating, but this one was very enjoyable because even though it took me a while, I made steady progress the entire time and never got stuck for long. Applying many of the problem solving techniques I’ve learned at Launch School was what helped the most.
I decided to write this blog post to document my experience, and to show others how even problems that seem very intimidating at first can actually be solved with the right strategy and mindset. I have attempted to structure this post like a walkthrough, showing each step I took in the process of solving the exercise. I’ll try not to give anything away ahead of time, so that if you’re following along, you can take a break at any point to try it on your own. (The best time to take a break is right before any images.)
With the right technique, this kata can be solved using pure logic, without having to rely on taking random guesses or applying brute force. This makes it a much more enjoyable experience. In this blog post, I will show you how you can accomplish this.
6 by 6 Skyscrapers kata description:
In a grid of 6 by 6 squares you want to place a skyscraper in each square with only some clues:
- The height of the skyscrapers is between 1 and 6
- No two skyscrapers in a row or column may have the same number of floors
- A clue is the number of skyscrapers that you can see in a row or column from the outside
- Higher skyscrapers block the view of lower skyscrapers located behind them
Can you write a program that can solve each 6 by 6 puzzle?
To understand how the puzzle works, this is an example of a row with 2 clues. Seen from the left there are 6 buildings visible, while seen from the right side there is only 1:
There is only one way in which the skyscrapers can be placed. From left-to-right all six buildings must be visible and no building may hide behind another building:
Example of a 6 by 6 puzzle with the solution:
Write this method:
Pass the clues in as an array of 24 integers. The clues are in the array around the clock (clockwise order). Index:
- If no clue is available, add value
- Each puzzle has only one possible solution
- solve_puzzlereturns a 6x6 array (6 rows, 6 columns). The first indexer is for the row, the second indexer for the column.
Understand the Problem
At Launch School I learned that the first step in solving any coding exercise is to understand the problem. This involves carefully reading the description/prompt and taking note of all the requirements and rules. Sometimes this can feel tedious, so I don’t always do it for every problem, even though I should. It is definitely essential for more challenging problems like this however, and I don’t think I would have been able to solve it without taking this step first.
I have described my approach to solving this problem in the rest of this blog post.
Defining key terms and outlining the requirements:
- The height of a skyscraper is an integer between 1 and 6.
- Each row and column must contain all the numbers from 1 to 6, so cannot have any duplicate heights.
- The input is an array of 24 integers, called
clues, which is passed to the
clueis the number of skyscrapers that can be seen from a row or column from the outside, in a straight line starting from the edge of the 6x6 grid adjacent to that
clue. A clue is an exact number, so the number of visible skyscrapers must be exactly equal to the clue, and not any more or less.
- Skyscrapers that are higher will block the view of any lower ones behind them. For example, 6 will always block every skyscraper behind it.
- Each clue is placed around the 6x6 grid in clockwise order by index of appearance in the
cluesarray, starting with the number at index
0above the top-left square, and ending with the number at index
23to the left of the top-left square. (See picture in the prompt.)
- Unknown clues are represented in the
cluesarray as the integer
- The output will be a two-dimensional array of arrays, containing 6 rows and 6 columns.
- Each set of clues can have only one possible solution.
solve_puzzlemethod should be able to solve up to 20 puzzles in 12 seconds or less.
To make it easier for me to understand and write about, I started using some of my own terms to describe certain aspects of the problem:
board=> the entire 6x6 array containing 6 horizontal rows and 6 vertical columns.
line=> a row or column of the grid/board (12 lines in total).
square=> an individual element of the grid or of a line, that can contain a skyscraper (6 squares per line, 36 squares in total).
sky=> the height of a skyscraper that has been assigned to a square (one per square).
nopes=> the set of skyscraper heights that would lead to an invalid solution if assigned to a square (eventually 5 per square) (I will explain more later on).
Solving the problem manually:
At first, I made a quick attempt to solve this problem using brute force, which wasn’t a good idea because I didn’t yet understand the problem well enough, even after outlining the requirements I listed above. My solution only worked on sets of clues without any unknown values, and was far from being fast enough to meet the time limit requirement. I realized that I needed to spend more time to understand the problem, so I decided to solve it by hand. I wasn’t sure if it was supposed to be possible to solve without the help of a computer, but I knew that brute force wasn’t going to work, so I figured I would at least try doing it manually as my next step.
First I drew the 6x6 grid on a piece of paper. (My handwriting is terrible, so I’m going to use some computer generated images to represent each step I took to draw it out. My image editing skills are not so great either though, so I apologize for any messiness.)
Although I thought the set of clues without any unknown values would be easier (it actually turned out to be harder), I decided to start with a variation of the set of clues shown in the exercise prompt:
clues = [ 0, 0, 0, 2, 2, 0,
0, 0, 0, 6, 3, 0,
0, 4, 0, 0, 0, 0,
4, 4, 0, 3, 0, 0 ]
A clue with a value of
6 is actually the best one we can hope for. It tells us what the entire row will be, because there is only one possible valid row in which all 6 skyscrapers can be seen:
The other clues are not as helpful. There is a huge number of possible valid lines that could satisfy the requirements of these clues. However, there are some numbers that we can know for certain could never be a possible value of the height of a skyscraper based on certain clues, the combination of certain clues, or
skys (heights of skyscrapers) that have already been filled in. I will refer to these invalid values as
My next step was to go through all the clues, and make a table containing nopes and skys for every possible clue or clue combination. These are general rules that can be applied successfully in any situation; they’re not specific to a particular set of clues. Any skys that are filled in were determined solely using the values of the clues and nopes.
Having a set of specific rules like this allows us to reliably fill in the value of a nope or sky only when we are absolutely certain that it is the correct value. This minimizes the chances of making a mistake and having to backtrack. Using these rules, along with other techniques I will explain later on, will enable you to solve this exercise without using any guesswork or brute force.
Here is the table (I apologize for my terrible handwriting; please let me know if you would like me to update this with a computer generated version):
Here each row represents an individual isolated line (row/column) that is not dependent on the rest of the table. The clues are on the left and right sides of each row. The small numbers are the nopes. The big numbers in the squares are the skys I was able to fill in based only on the clues and nopes shown here. The top 6 rows have one known clue on the left, and one unknown clue (0) on the right. The bottom rows have two known clues, one on each side.
This table covers all the possible clue combinations, although it may sometimes be necessary to read a row in reverse, such as column #5 in the image below, which has to be read from bottom to top if you’re filling values in based on the table above.
Let’s use the table above to fill in the nopes and skys of as many squares as we can:
(I will be referring to the positions of squares, rows, and columns as numbers from 1 to 6, not 0 to 5 as they would be in a Ruby array, to make things easier to visualize. They are numbered in order of left to right for rows, and top to bottom for columns.) The nopes are the small red numbers, and the skys are the big blue/white numbers.
I was able to fill in one sky based on the rules, as well as quite a few nopes. I usually even fill in the nopes for squares that already have a sky filled in, which helps me to keep better track of everything. Every time I fill in a sky, I make sure to add a nope with the value of that sky to each square in that sky’s row and column, which is a nope with a value of
6 in this case. The
4-3 clues row (fifth row) already had a
6 included in each of its squares’ nopes, but I was able to add a
6 to the nopes of the
2-0 clues column’s (fourth column’s) squares. This lets me know that there can never be a
6 in any of the squares in the fourth position of any row, nor in the fifth position of any column.
There are no other squares with five nopes, so we won’t be able to fill in more skys using that strategy for now. What do you think our next step should be?
Even though I’m solving this puzzle for the second time right now, it actually took me a couple of minutes to figure out what the next step should be. I first started trying to get an idea from the clues, but since there aren’t very many, I realized it would be much easier to look at the nopes. Even though we already filled out the skys of all the squares containing five nopes, we can still use the nopes to figure out the next sky we can fill in, by looking at the nopes of each
line (row/column) as a whole:
The new skys and nopes are in the darker shade of blue. I was able to fill in two skys,
6, by looking at the set of nopes across the fifth and sixth rows, respectively. Whenever there are five squares that share one nope value in a line (row/column), we can know for certain that the sky value of the remaining square must be this nope value. Row #5 had a nope with a value of
5 in every square (five squares in total) except for the third square, so we know that the third square must have a sky value of
5. The same applies to the
6 in the sixth position of row #6 (the bottom right square). Like before, we should then fill in the nopes in the lines that contain the two squares that we just filled in skys for.
After filling in any new nopes, it’s always best to check again for any squares containing five different nope values in total, as well as any lines with five of the same nope value:
Seeing that there are five nopes with a value of
5 in the row #6, I was able to fill in one sky with a value of
5 in the fourth position of that row (green), as well as the corresponding nopes in column #4 and row #5. This allowed me to fill in a sky of
4 in the second position of the same row.
Now we can look at the clues again, and try to see if there are any possible nopes we can add to any of the squares, based on both the clue(s) and the skys that are already filled in.
Below I have listed some rules that I came up with to help determine which nopes and skys will go where. These rules are by no means exhaustive, but they should give you a general idea of how to approach this problem. I will explain in more detail and give examples as we work through this problem, so for now it might be good to just skim over these rules and refer back to them as needed.
Here are a few general rules to start with:
- Reminder: a clue is the exact number of skys that are visible from the side of a row/column (line) that is adjacent to that clue. There can never be more or less visible skys than specified in the clue.
- An unknown clue means that the number of visible skys can be any number between 1 and 6.
- A sky with a higher height value (we will call the height `sky` or ‘sky value’) will always block any skys following it that have a lower sky value.
- The first sky in any line will always be visible from that side. Therefore the first square always increments the total number of visible skys by 1, regardless of its sky value.
- Nothing can block a sky with a value of
6. Therefore any skys that come after a
6in a line cannot be seen. Also, a
6is always visible in any position of a line, no matter what comes before it.
- One helpful way to narrow down what nopes or skys can be filled in for a particular square, is to look at the clues and already filled-in sky values for the line containing that square, and see if you can use that to determine if the initial sky values of the squares its line should be in an increasing or decreasing sequence. If so, you can sometimes use that knowledge to fill in nopes or skys in one or more of that line’s squares (I will explain more about this later on).
Here are some more specific rules that may help as well:
- A line with a clue of 2 can never have the first three squares as an increasing sequence (ex: 4, 5, 6). Otherwise you would be able to see more than 2 skys.
- If we know the value of a sky in certain lines, we can determine if the clue will from then on be useless to us. For example, a line with a clue of 2 and a sky of
6in the second square, could have a valid first square sky of any number between
5, so this clue can no longer be used to determine anything. It can be helpful to cross out a useless clue out so that we know that we should skip it when we are trying to find our next sky or nope value.
- Here is a list I made of some specific rules that can always be followed when you know a combination of certain clue and sky values. (
<-n->indicates that the sky value of
ncan be in a square in any position surrounding it, and the rule will still apply):
Now let’s see if we can cross out any useless clues or fill in any nopes based on these rules:
By using the rules, I was able to see that in the fifth row, the two initial values on both sides have to be an increasing sequence (cyan colored up arrow). Therefore, I knew that the squares in the second and fifth positions could never be
1, so I added the number
1 to the nopes of those two squares. (A
5,6 is in the middle of this row, which means these two clues are no longer directly related. I used the rules on them individually, and they both just happened to be increasing; just because one is increasing does not mean that the other has to be increasing in turn.)
What step do you think we should take next?
As usual, it is a good idea to check if there are any “sets of five nopes” (from now on, I will use this term to refer to both squares with five total nopes, as well as lines with five of the same nope). Unfortunately there aren’t any sets of five nopes here, so let’s see if we can fill in any nopes or skys using the list of rules we went over above:
By using the rule that says a 6 will always block everything that comes after it, and by seeing that the clue at the bottom of column #5 is
4, I was able to determine that the square located at row #3 column #5 could never have a sky value of
6, because otherwise there would be less than four visible skys in total. This is because the sky of
2 at position
[5, 5] will always being blocked by a square with a higher sky, since the initial two rows must have at least one sky value greater than
2. (For brevity, I will refer to square positions in the format of
[row_number, column_number] from now on.)
To figure out what to fill in next, we should perform our usual step of checking for sets of five nopes again:
As you can see, I checked for sets of five nopes and found one in row #1 and another in row #3, so I was able to fill in two skys of
6 at positions
[1, 2] and
[3, 3]. This gives us a total of six skys with a value of
6, which lets us know that every remaining sky must have a value between
5. You may find it helpful to write this additional information down, but if you’ve been following along and filling in the corresponding nopes on each square each time you fill in a sky, it’s not really necessary. I also added an up arrow next to the clue on the left side of row #3 to signify that the first two sky values must be an increasing sequence.
You might be wondering why I put green crosses over four of the clues. I did this to signify that these clues no longer tell us anything of value, because the side of the line that they’re on will always be valid, no matter what sky values we end up filling in the squares with. For example, in row #5, four skys will always be visible regardless of what sky is placed in the square at position
[5, 2]. Crossing out clues isn’t strictly necessary, but I prefer to do it because it allows me to save time later on, since I know that I won’t have to check that side of a line based on the clue anymore. (I should have actually done this a while back, every time that I had enough nopes and skys filled in to know that a clue would be useless, but I forgot about it until now. It’s more of a way to save time than something that’s essential to solving the problem though, so don’t worry about it too much.)
You’re probably tired of seeing me repeat the same steps over and over by now, so I’ll stop mentioning them as explicitly. If you have any difficulty following along, please feel free to let me know by leaving a comment below, and I will update this with a more thorough explanation.
This next one might be a little tricky, but if we look back at the rules carefully, it shouldn’t give us any problems:
I was able to fill in a sky with a value of
4 at position
[1, 4] by seeing that column #4 has both a clue of
2 at the top, as well as a sky of
6 in the fifth position from the top (position
[5, 4]). If a sky of
4 were placed anywhere besides in the first position, more than two skys would be visible, which would violate the requirements of the clue. I crossed out the clue at the top of column #4 because with
2 being the only possible sky values remaining in that column, placing them in either order in the two remaining squares would both be valid, so this clue is no longer useful to us. We now only have three useful clues left.
There may be more than one possible way to proceed from here (as well as in the previous examples), but the first thing I notice that we can do something about is in row #3:
I filled in skys with values of
3 in the initial two squares of row #3 because I knew that the sequence had to be increasing, and the only possible skys in the second square that satisfy this condition are
3. By looking at the nopes, we know that the first square cannot have a sky value of
1, so that means that the second square cannot be a
2, 3 as the only valid remaining possible sequence.
Now we’re on a roll! The next ones should be pretty easy:
Wow, that actually was even easier than I expected! I always get a little worried at the end of these, because if I had made a mistake somewhere, I would have had to go back and redo the whole thing. Fortunately, everything went pretty smoothly this time. I was able to fill in all the remaining sky values based on sets of five skys alone. I normally would have filled in the nopes as I was going along, but since there are no more remaining squares, it wasn’t even necessary this time. I would definitely recommend always filling in the nopes anyway though, as you never know whether you’re truly at the end yet or not. It can be easy to lose track of which skys you just filled in, especially if you’re not color coding each new addition of sky and nope values like we’ve been doing here.
So that should take care of the first step in solving a difficult coding exercise: understanding the problem. At this point you might be able to move on to the next steps, which include writing out test cases (Codewars takes care of this part for you), deciding on what data structure(s) to use, creating an algorithm, and translating it all to code. What we’ve done here might not be enough however — I actually needed solve another puzzle by hand to really understand everything. Here is the set of clues I used for the second puzzle that I solved:
clues = [ 3, 2, 2, 3, 2, 1,
1, 2, 3, 3, 2, 2,
5, 1, 2, 2, 4, 3,
3, 2, 1, 2, 2, 4 ]
There are no unknown clues (0’s), so it seems like this should be easier than the one we just did, but it actually ended up taking me much longer to solve, probably because there weren’t any clues with a value of
6. It was pretty fun though, so I would definitely recommend giving it a try if you’re up for the challenge or thinking about solving this kata on Codewars.
I was planning on also writing about the process I went through to apply the rest of the problem solving techniques that I learned at Launch School to this exercise, but this blog post has already taken me much longer than I anticipated (over thirteen hours so far!), and has become quite long to read as well. I’m not sure if anyone else is actually interested in this, so I’m going to end it here for now.
Leave me a comment below to let me know if you would like to read more about this, and I’ll try to write a follow-up article that includes my actual Ruby code. Also feel free to leave a comment with any thoughts, questions, suggestions, alternate approaches you came up with, or errors you may have noticed, and I will do my best to respond. For anyone who made it all the way to the end, thanks for reading, and I hope you enjoyed it!