width = len(matrix)
height = len(matrix)
#if the square is not the same color as the starting point
if matrix[x][y] != start_color:
#if the square is not the new color
elif matrix[x][y] == color_to_update:
#update the color of the current square to the replacement color
matrix[x][y] = color_to_update
neighbors = [(x-1,y),(x+1,y),(x-1,y-1),(x+1,y+1),(x-1,y+1),(x+1,y-1),(x,y-1),(x,y+1)]
for n in neighbors:
if 0 <= n <= width-1 and 0 <= n <= height-1:
#pick a random starting point
start_x = random.randint(0,width-1)
start_y = random.randint(0,height-1)
start_color = matrix[start_x][start_y]
This is the same code used to create the animation, and the colors correspond to numbers, so color_to_update is initialized to 9, which is mapped to the gray color that the connected pixels are updated to.
With depth-first search, the algorithm explores one path completely until reaching a pixel with a different color.
Then it comes back to the starting point and pursues the next neighbor's path.
Notice that only the dark blue pixels that are connected are changed. The other dark blue pixels that are not adjacent to the starting point are left alone.
With this example the colors are all uniform, so we just have to compare pixels to see if they have an equal value.
But with a real image like the sweatshirt, it is not so simple.
Colors are not uniform in many (most?) images
If you look closely at the orange sweatshirt in the image earlier, you can see that there are many different shades of orange that make up even just the sweatshirt part of the image.
There are lighter and darker shades of orange due to lighting, shadows, creases, etc.
Two pixels right next to each other might be slightly different shades of orange, but look the same to our human eyes.
So we need to be more flexible and instead check to see if the colors are similar.
How can we tell if two colors are similar?
We are working with RGB colors.
An RGB color has a red, green and blue parameter, which together combine to create all other colors.
Each parameter has a value between 0 and 255, which defines the intensity of that color parameter.
An example would be rgb(242, 103, 51), which is one of the shades of orange found in the sweatshirt.
So colors are on a spectrum, and instead of checking for an exact match, we could compare a new pixel color to the starting point, and decide if they are close enough of a match.
One way to compare two colors would be to subtract the red, green and blue values of the colors separately and see if all of them are within a certain threshold.
def is_similar(start_color, new_color):
threshold = 40
red,green,blue,alpha = start_color
new_red,new_green,new_blue,new_alpha = new_color
if abs(red-new_red) <= threshold and abs(green-new_green) <= threshold and abs(blue-new_blue) <= threshold:
In this function I've set a threshold of 40, so if the absolute value of the difference between each of the red, green and blue values in the two colors is greater than or equal to 40, then they are similar enough.
Side note: the image is actually an RGBA image, where the A represents an alpha channel for opacity, but we are only concerned with the red, green and blue values here.
Here you can see the difference between thresholds.
Top left = threshold 10
Top right = threshold 40
Bottom left = threshold 100
Bottom right = threshold 200
There is a green star on each image that shows where the starting point is.
The green arrow on the bottom right points it out as well, in case it's not easy to see!
It makes sense because with a large threshold like 200, we are defining almost all other RGB colors as similar.
Interview questions about islands
Another use for this algorithm is in interview questions that ask about islands.
If they want you to count all the islands in a matrix or something like that, which seems to be a popular interview question.
You can use the flood fill algorithm to determine the nodes that belong to each island.
As the saying goes, don't reinvent the wheel!
There are implementations of the flood fill algorithm that have been tested and are probably a better choice than rolling your own solution.
You can do a lot of interesting things with the Spotify API, like searching for artists and playlists, following and sharing them, and more. In this post we will access the API using Python to get featured playlists and associated artists and genres.
Pictograms have been around for a long time, and with good reason. They are interesting and engaging, and might even help your audience to remember the information better. In this post we will build a pictogram grid in D3.js.
Let's play Minesweeper in Python. In this post we will treat Minesweeper as a constraint satisfaction problem and use common algorithms like constraint propagation and backtracking search to mimic logic we would use to play the game as humans.