使用Bitlist求解Advent of Code 2015 Day06的Haskell代码问题咨询

Let's tackle your questions one by one, starting with the most critical issue causing incorrect results, then moving to idiomatic Haskell style and performance tweaks.

1. Why Your Results Are Wrong (The Critical Bug) #

The core issue lies in your parse function—you're misinterpreting coordinate strings entirely. Here's the breakdown:

Your current parse takes a string like "x,y" and runs range (read c1, read (tail c2)), which treats "x,y" as a range of integers from x to y (e.g., "0,2" becomes [0,1,2]). But each coordinate string represents a single (x,y) point, not a sequential range of numbers.

For example, an instruction like toggle 0,0 through 9,9 would be processed by your code to only flip 2 bits (0 + 0*1000 and 0 +9*1000) instead of the full 1000x1000 grid. That's why your count is drastically off!

Here's how to fix the parsing logic to correctly handle (x,y) tuples:

parseCoord :: String -> (Int, Int)
parseCoord s = case break (==',') s of
  (xStr, ',' : yStr) -> (read xStr, read yStr)
  _ -> error $ "Invalid coordinate: " ++ s -- Use Maybe/Either for safer error handling

Then generate all bit indices for the target rectangle properly:

bitIndices :: (Int, Int) -> (Int, Int) -> [Int]
bitIndices (x1, y1) (x2, y2) = [x + y*1000 | x <- [x1..x2], y <- [y1..y2]]

Update your action function to use these corrected helpers, and your popCount will start returning accurate results.

2. More Idiomatic Haskell Style #

Your code is a solid starting point, but we can make it more readable, type-safe, and maintainable with Haskell best practices:

• Use algebraic data types for actions: Replace string pattern matching with a dedicated type to represent light operations—this makes the code self-documenting and catches errors at compile time.
• Avoid partial functions: read and tail can crash on bad input. Use readMaybe from Text.Read to handle parsing errors gracefully.
• Split into small, single-purpose functions: Break down parsing and logic into tiny, testable components.
• Add strategic type annotations: Clarify top-level functions instead of only annotating in main.

Here's a revised, idiomatic version:

module Day06 where

import Data.Bits
import Data.List (foldl')
import Text.Read (readMaybe)

-- Algebraic type to represent light actions
data Action = Toggle | TurnOn | TurnOff deriving (Show, Eq)

-- Safely parse a coordinate string into (x,y)
parseCoord :: String -> Maybe (Int, Int)
parseCoord s = case break (==',') s of
  (xStr, ',' : yStr) -> (,) <$> readMaybe xStr <*> readMaybe yStr
  _ -> Nothing

-- Parse a line into an Action and coordinate range
parseInstruction :: String -> Maybe (Action, (Int, Int), (Int, Int))
parseInstruction line = case words line of
  ["toggle", a, "through", b] -> (,,) Toggle <$> parseCoord a <*> parseCoord b
  ["turn", "on", a, "through", b] -> (,,) TurnOn <$> parseCoord a <*> parseCoord b
  ["turn", "off", a, "through", b] -> (,,) TurnOff <$> parseCoord a <*> parseCoord b
  _ -> Nothing

-- Generate all bit indices for a rectangle
bitIndices :: (Int, Int) -> (Int, Int) -> [Int]
bitIndices (x1, y1) (x2, y2) = [x + y*1000 | x <- [x1..x2], y <- [y1..y2]]

-- Apply a single action to the current state
applyAction :: Integer -> (Action, (Int, Int), (Int, Int)) -> Integer
applyAction state (action, start, end) = case action of
  Toggle -> foldl' complementBit state indices
  TurnOn -> foldl' setBit state indices
  TurnOff -> foldl' clearBit state indices
  where indices = bitIndices start end

main :: IO ()
main = do
  input <- readFile "input"
  let instructions = map parseInstruction (lines input)
      validInstructions = [inst | Just inst <- instructions] -- Filter invalid entries
      finalState = foldl' applyAction 0 validInstructions
  print $ popCount finalState

3. Performance Improvements #

Your current approach modifies bits one by one, which works but is slow for large grids (1e6 bits total). Instead, use bulk bitwise operations with precomputed masks—CPU bitwise ops are optimized for this kind of work, making it drastically faster.

First, write functions to generate masks for ranges and rectangles:

-- Create a mask where bits from start to end (inclusive) are set
rangeMask :: Int -> Int -> Integer
rangeMask start end = (shiftL 1 (end - start + 1) - 1) `shiftL` start

-- Create a mask for an entire rectangle (x1<=x<=x2, y1<=y<=y2)
rectMask :: (Int, Int) -> (Int, Int) -> Integer
rectMask (x1, y1) (x2, y2) = foldl' (.|.) 0 [rowMask y | y <- [y1..y2]]
  where rowMask y = rangeMask (x1 + y*1000) (x2 + y*1000)

Then update applyAction to use these masks for bulk operations:

applyAction :: Integer -> (Action, (Int, Int), (Int, Int)) -> Integer
applyAction state (action, start, end) = case action of
  Toggle -> state `xor` mask
  TurnOn -> state .|. mask
  TurnOff -> state .&. complement mask
  where mask = rectMask start end

This reduces operations from O(n) (n = number of bits) to O(number of rows), cutting down from 1e6 operations to 1000 for a full grid.

内容的提问来源于stack exchange，提问作者haskeller