Last active
March 3, 2018 17:35
-
-
Save janice-wong/d87ac04484b0c7adc758a91317e0abd4 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # ASSUMPTION | |
| # image is an array of arrays | |
| # EDGE CASES | |
| # if image is empty | |
| # if point is out of bounds | |
| # if image consists of one pixel | |
| # if point is already filled | |
| def flood_fill(image, point) | |
| # if image is empty | |
| return 'image is empty' if image[0].empty? | |
| # if point is out of bounds | |
| # find a better way to write the line below | |
| x = point[0] | |
| y = point[1] | |
| return 'point is out of bounds' if x < 0 || x > image.length - 1 || y < 0 || y > image.length - 1 | |
| # if image consists of one pixel | |
| return [[true]] if image[0].length == 1 | |
| # if point is already filled | |
| return image if image[x][y] | |
| # fill the point | |
| image[x][y] = true | |
| # identify surroundings if within bounds | |
| north = [x - 1, y] if x > 0 | |
| south = [x + 1, y] if x < image.length - 1 | |
| west = [x, y - 1] if y > 0 | |
| east = [x, y + 1] if y < image[0].length - 1 | |
| # identify borders | |
| borders = [north, south, east, west].select { |direction| direction } | |
| # identify unfilled borders | |
| fill = borders.select { |coordinate| !image[coordinate[0]][coordinate[1]] } | |
| # fill each unfilled border | |
| fill.each_with_index do |coordinate| | |
| flood_fill(image, coordinate) | |
| end | |
| return image | |
| end | |
| # # TEST EDGE CASES | |
| # p flood_fill([[]], [0,0]) | |
| # p flood_fill([[true, false]], [1,0]) | |
| # p flood_fill([[false]], [0,0]) | |
| # p flood_fill([[true, false, true]], [0,0]) | |
| # p '-' * 100 | |
| # # TEST REGULAR(?) CASES | |
| # image_zero = [[true, true, false, true], [true, false, false, true], [true, true, false, false], [false, false, false, true]] | |
| # p flood_fill(image_zero, [1, 2]) | |
| # p '-' * 100 | |
| # image_one = [[true, true, false, true], [true, false, false, true], [true, true, false, false], [false, true, false, true]] | |
| # p flood_fill(image_one, [1, 2]) | |
| # p flood_fill(image_one, [0, 2]) | |
| # p '-' * 100 | |
| # image_two = [[true, true, false], | |
| # [true, false, true], | |
| # [true, false, true]] | |
| # p flood_fill(image_two, [0,0]) | |
| # p flood_fill(image_two, [1,1]) | |
| # p '-' * 100 | |
| # image_three = [[true, true, false, true], | |
| # [false, true, false, false], | |
| # [false, true, false, true], | |
| # [true, true, true, false]] | |
| # p flood_fill(image_three, [1, 2]) #=> [[true, true, true, true], | |
| # # [false, true, true, true], | |
| # # [false, true, true, true], | |
| # # [true, true, true, false]] | |
| # p '-' * 100 | |
| image_four = [[true, true, false, true, false, true], | |
| [false, true, false, false, false, true], | |
| [false, true, false, true, false, true], | |
| [true, true, true, false, false, false]] | |
| p flood_fill(image_four, [0, 2]) #=> [[true, true, true, true, true, true], | |
| # [false, true, true, true, true, true], | |
| # [false, true, true, true, true, true], | |
| # [true, true, true, true, true, true]] | |
| # p '-' * 100 | |
| # image_five = [[true, true, false, true, false, true], | |
| # [false, true, false, false, false, true], | |
| # [false, true, false, true, false, true], | |
| # [true, true, true, false, false, false]] | |
| # p flood_fill(image_five, [1, 0]) #=> [[true, true, false, true, false, true], | |
| # # [true, true, false, false, false, true], | |
| # # [true, true, false, true, false, true], | |
| # # [true, true, true, false, false, false]] |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment