Vin Diagrams: Difference between revisions
Jump to navigation
Jump to search
imported>Kmk21 Created page with "This problem effectively asks us the number of dots inside two loops on an ascii grid. Algorithmically, this isn't super challenging, it's just we have to code it up right. O..." |
imported>Kmk21 No edit summary |
||
| Line 1: | Line 1: | ||
This problem effectively asks us the number of dots inside two loops on an ascii grid. | This problem effectively asks us the number of dots inside two loops on an ascii grid. Algorithmicaly, this isn't super challenging, it's just we have to code it up right. | ||
One easy way to do it is to: | One easy way to do it is to: | ||
| Line 5: | Line 5: | ||
# identify the A and then flood-fill the A ring with all A's (except for intersections...they can stay X | # identify the A and then flood-fill the A ring with all A's (except for intersections...they can stay X | ||
# repeat with B | # repeat with B | ||
* these two steps just allow us to more easily identify loops moving on forward | #* these two steps just allow us to more easily identify loops moving on forward | ||
# walk around the edge of the input grid and flood fill any '.' to something else to easily determine what is and is not inside a loop. | # walk around the edge of the input grid and flood fill any '.' to something else to easily determine what is and is not inside a loop. | ||
# find some '.' which is still left. Flood fill to the edge. We can determine whether it's A, B, or both depending on the boundaries we hit while flood filling | # find some '.' which is still left. Flood fill to the edge. We can determine whether it's A, B, or both depending on the boundaries we hit while flood filling | ||
Latest revision as of 22:48, 3 November 2017
This problem effectively asks us the number of dots inside two loops on an ascii grid. Algorithmicaly, this isn't super challenging, it's just we have to code it up right.
One easy way to do it is to:
- identify the A and then flood-fill the A ring with all A's (except for intersections...they can stay X
- repeat with B
- these two steps just allow us to more easily identify loops moving on forward
- walk around the edge of the input grid and flood fill any '.' to something else to easily determine what is and is not inside a loop.
- find some '.' which is still left. Flood fill to the edge. We can determine whether it's A, B, or both depending on the boundaries we hit while flood filling
- repeat for any remaining dots