undefined

    
import Control.Monad
import Data.List
import Data.Map (Map)
import Data.Map qualified as Map
import Data.Maybe
import Data.Set qualified as Set

type Pos = (Int, Int)

readInput :: String -> Map Pos Char
readInput s = Map.fromList [((i, j), c) | (i, l) <- zip [0 ..] (lines s), (j, c) <- zip [0 ..] l]

solveMaze :: Map Pos Char -> Maybe [Pos]
solveMaze maze = listToMaybe $ go [] start
  where
    walls = Map.keysSet $ Map.filter (== '#') maze
    Just [start, end] = traverse (\c -> fst <$> find ((== c) . snd) (Map.assocs maze)) ['S', 'E']
    go h p@(i, j)
      | p == end = return [end]
      | otherwise = do
          p' <- [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]
          guard $ p' `notElem` h
          guard $ p' `Set.notMember` walls
          (p :) <$> go [p] p'

dist (i1, j1) (i2, j2) = abs (i2 - i1) + abs (j2 - j1)

findCheats :: [Pos] -> Int -> Int -> [((Pos, Pos), Int)]
findCheats path minScore maxLen = do
  (t2, end) <- zip [0 ..] path
  (t1, start) <- zip [0 .. t2 - minScore] path
  let len = dist start end
      score = t2 - t1 - len
  guard $ len <= maxLen
  guard $ score >= minScore
  return ((start, end), score)

main = do
  Just path <- solveMaze . readInput <$> readFile "input20"
  mapM_ (print . length . findCheats path 100) [2, 20]

  

 undefined

    
import 'dart:math';
import 'package:more/more.dart';

List<Point<num>> d4 = [Point(1, 0), Point(-1, 0), Point(0, 1), Point(0, -1)];

List<Point<num>> findPath(List<String> lines) {
  var maze = {
    for (var r in lines.indexed())
      for (var c in r.value.split('').indexed().where((e) => e.value != '#'))
        Point<num>(c.index, r.index): c.value
  }.withDefault('#');
  var path = AStarSearchIterable<Point>(
      startVertices: [maze.entries.firstWhere((e) => e.value == 'S').key],
      successorsOf: (p) => d4.map((e) => (e + p)).where((n) => maze[n] != '#'),
      costEstimate: (p) => 1,
      targetPredicate: (p) => maze[p] == 'E').first.vertices;
  return path;
}

num dist(Point p1, Point p2) => (p1.x - p2.x).abs() + (p1.y - p2.y).abs();

solve(List<String> lines, int cheat, int target) {
  List<Point<num>> path = findPath(lines);
  var cheats = 0;
  for (int s = 0; s < path.length - cheat; s++) {
    for (int e = s + cheat; e < path.length; e++) {
      var d = dist(path[e], path[s]);
      var diff = e - s - d;
      if (d <= cheat && diff >= target) cheats += 1;
    }
  }
  return cheats;
}

  

 haskell

    
import Control.Arrow

import qualified Data.List as List
import qualified Data.Set as Set
import qualified Data.Map as Map
import qualified Data.Maybe as Maybe

parse s = Map.fromList [ ((y, x), c) | (l, y) <- zip ls [0..], (c, x) <- zip l [0..]]
        where
        ls = lines s

floodFill m = floodFill' m startPosition (Map.singleton startPosition 0)
        where
                startPosition = Map.assocs
                        >>> filter ((== 'S') . snd)
                        >>> head
                        >>> fst
                        $ m

neighbors (p1, p2) = [(p1-1, p2), (p1, p2-1), (p1, p2+1), (p1+1, p2)]

floodFill' m p f
        | m Map.! p == 'E' = f
        | otherwise = floodFill' m n f'
        where
                seconds = f Map.! p
                ns = neighbors p
                n = List.filter ((m Map.!) >>> (`Set.member` (Set.fromList ".E")))
                        >>> List.filter ((f Map.!?) >>> Maybe.isNothing)
                        >>> head
                        $ ns
                f' = Map.insert n (succ seconds) f

taxiCabDistance (a1, a2) (b1, b2) = abs (a1 - b1) + abs (a2 - b2)

calculateCheatAdvantage f (p1, p2) = c2 - c1 - taxiCabDistance p1 p2
        where
                c1 = f Map.! p1
                c2 = f Map.! p2

cheatDeltas :: Int -> Int -> [(Int, Int)]
cheatDeltas l h = [(y, x) | x <- [-h..h], y <- [-h..h], let d = abs x + abs y, d <= h, d >= l]

(a1, a2) .+. (b1, b2) = (a1 + b1, a2 + b2)

solve l h (f, ps) = Set.toList
        >>> List.map ( repeat
                >>> zip (cheatDeltas l h)
                >>> List.map (snd &&& uncurry (.+.))
                >>> List.filter (snd >>> (`Set.member` ps))
                >>> List.map (calculateCheatAdvantage f)
                >>> List.filter (>= 100)
                >>> List.length
                )
        >>> List.sum
        $ ps
part1 = solve 2 2
part2 = solve 1 20

main = getContents
        >>= print
        . (part1 &&& part2)
        . (id &&& Map.keysSet)
        . floodFill
        . parse