As always, we start by parsing the input into something more manageable:
import Data.Set
parse :: String -> Set (Int, Int)
parse = grid . linesgrid is a helper function that produces a
Set of points. An interesting note about this problem
is that the points that do not contain rolls (points that
are not @) are inconsequential to the problem itself,
and we can fully ignore them. Using a list comprehension, we first
enumerate each line of the input, and then enumerate each
character of that line, and only preserve the characters that are
@:
grid l =
fromList
[ (x, y)
| (r, x) <- zip l [0 ..],
(c, y) <- zip r [0 ..],
c == '@'
]Now that are input has been munged, lets move onto the problem itself.
This part requires us to first calculate all points adjacent to a roll, if there are more than 4 rolls at these adjacent locations, disqualify the roll, as it cannot be lifted by a forklift. First, lets generate a list comprehension that produces the points adjacent to a given point. We ignore the offset (0, 0) because that is the point itself:
adjs (x, y) =
[ (x + x', y + y')
| x' <- [-1, 0, 1],
y' <- [-1, 0, 1],
(x', y') /= (0, 0)
]Then, a roll is liftable by a forklift if the adjacent points
only have upto 4 rolls. We can use Set.filter to
traverse the entire grid. Our filter predicate first collects
adjacent points, filters out ones that are within the boundaries
of the grid, and counts them. Remember that our grid does not
contain points that are not rolls anyway!
liftable g = Data.Set.filter pred g
where
pred =
(< 4)
. length
. Prelude.filter (`member` g)
. adjsThus, the solution to part one is given as:
p1 = size . liftableThis part is very similar to the previous part. We need to
sequentially remove liftable rolls until we can lift no more. A
simple recursive function can do the trick. The base case: if no
more rolls can be lifted from the grid, return the number of rolls
lifted thus far. The recursive case: accumulate the rolls that are
liftable in the current state of the grid, and recurse into the
grid where the rolls are removed! The removal is calculated simply
using Set.\\, which performs set difference:
go s g
| size lifted == 0 = s
| otherwise = go (s + size lifted) (g \\ lifted)
where
lifted = liftable gThus, the solution for the second part is given like so:
p2 = go 0Finally, a main function to wrap it all up:
main = do
n <- parse <$> getContents
print $ p1 n
print $ p2 n