Haskell, alternative approach

The x and y coordinates of robots are independent. 101 and 103 are prime. So, the pattern of x coordinates will repeat every 101 ticks, and the pattern of y coordinates every 103 ticks.

For the first 101 ticks, take the histogram of x-coordinates and test it to see if it’s roughly randomly scattered by performing a chi-squared test using a uniform distrobution as the basis. [That code’s not given below, but it’s a trivial transliteration of the formula on wikipedia, for instance.] In my case I found a massive peak at t=99.

Same for the first 103 ticks and y coordinates. Mine showed up at t=58.

You’re then just looking for solutions of t = 101m + 99, t = 103n + 58 [in this case]. I’ve a library function, maybeCombineDiophantine, which computes the intersection of these things if any exist; again, this is basic wikipedia stuff.

day14b ls =
  let
    rs = parse ls
    size = (101, 103)
    positions = map (\t -> process size t rs) [0..]

    -- analyse x coordinates. These should have period 101
    xs = zip [0..(fst size)] $ map (\rs -> map (\(p,_) -> fst p) rs & C.count & chi_squared (fst size)) positions
    xMax = xs & sortOn snd & last & fst

    -- analyse y coordinates. These should have period 103
    ys = zip [0..(snd size)] $ map (\rs -> map (\(p,_) -> snd p) rs & C.count & chi_squared (snd size)) positions
    yMax = ys & sortOn snd & last & fst

    -- Find intersections of: t = 101 m + xMax, t = 103 n + yMax
    ans = do
      (s,t) <- maybeCombineDiophantine (fromIntegral (fst size), fromIntegral xMax)
                                       (fromIntegral (snd size), fromIntegral yMax)
      pure $ minNonNegative s t
  in
    trace ("xs distributions: " ++ show (sortOn snd xs)) $
    trace ("ys distributions: " ++ show (sortOn snd ys)) $
    trace ("xMax = " ++ show xMax ++ ", yMax = " ++ show yMax) $
    trace ("answer could be " ++ show ans) $
    ans