--- Day 20: Race Condition ---

The Historians are quite pixelated again. This time, a massive, black building looms over you - you're right outside the CPU!

While The Historians get to work, a nearby program sees that you're idle and challenges you to a race. Apparently, you've arrived just in time for the frequently-held race condition festival!

The race takes place on a particularly long and twisting code path; programs compete to see who can finish in the fewest picoseconds. The winner even gets their very own mutex!

They hand you a map of the racetrack (your puzzle input). For example:

###############
#...#...#.....#
#.#.#.#.#.###.#
#S#...#.#.#...#
#######.#.#.###
#######.#.#...#
#######.#.###.#
###..E#...#...#
###.#######.###
#...###...#...#
#.#####.#.###.#
#.#...#.#.#...#
#.#.#.#.#.#.###
#...#...#...###
###############
The map consists of track (.) - including the start (S) and end (E) positions (both of which also count as track) - and walls (#).

When a program runs through the racetrack, it starts at the start position. Then, it is allowed to move up, down, left, or right; each such move takes 1 picosecond. The goal is to reach the end position as quickly as possible. In this example racetrack, the fastest time is 84 picoseconds.

Because there is only a single path from the start to the end and the programs all go the same speed, the races used to be pretty boring. To make things more interesting, they introduced a new rule to the races: programs are allowed to cheat.

The rules for cheating are very strict. Exactly once during a race, a program may disable collision for up to 2 picoseconds. This allows the program to pass through walls as if they were regular track. At the end of the cheat, the program must be back on normal track again; otherwise, it will receive a segmentation fault and get disqualified.

So, a program could complete the course in 72 picoseconds (saving 12 picoseconds) by cheating for the two moves marked 1 and 2:

###############
#...#...12....#
#.#.#.#.#.###.#
#S#...#.#.#...#
#######.#.#.###
#######.#.#...#
#######.#.###.#
###..E#...#...#
###.#######.###
#...###...#...#
#.#####.#.###.#
#.#...#.#.#...#
#.#.#.#.#.#.###
#...#...#...###
###############
Or, a program could complete the course in 64 picoseconds (saving 20 picoseconds) by cheating for the two moves marked 1 and 2:

###############
#...#...#.....#
#.#.#.#.#.###.#
#S#...#.#.#...#
#######.#.#.###
#######.#.#...#
#######.#.###.#
###..E#...12..#
###.#######.###
#...###...#...#
#.#####.#.###.#
#.#...#.#.#...#
#.#.#.#.#.#.###
#...#...#...###
###############
This cheat saves 38 picoseconds:

###############
#...#...#.....#
#.#.#.#.#.###.#
#S#...#.#.#...#
#######.#.#.###
#######.#.#...#
#######.#.###.#
###..E#...#...#
###.####1##.###
#...###.2.#...#
#.#####.#.###.#
#.#...#.#.#...#
#.#.#.#.#.#.###
#...#...#...###
###############
This cheat saves 64 picoseconds and takes the program directly to the end:

###############
#...#...#.....#
#.#.#.#.#.###.#
#S#...#.#.#...#
#######.#.#.###
#######.#.#...#
#######.#.###.#
###..21...#...#
###.#######.###
#...###...#...#
#.#####.#.###.#
#.#...#.#.#...#
#.#.#.#.#.#.###
#...#...#...###
###############
Each cheat has a distinct start position (the position where the cheat is activated, just before the first move that is allowed to go through walls) and end position; cheats are uniquely identified by their start position and end position.

In this example, the total number of cheats (grouped by the amount of time they save) are as follows:

There are 14 cheats that save 2 picoseconds.
There are 14 cheats that save 4 picoseconds.
There are 2 cheats that save 6 picoseconds.
There are 4 cheats that save 8 picoseconds.
There are 2 cheats that save 10 picoseconds.
There are 3 cheats that save 12 picoseconds.
There is one cheat that saves 20 picoseconds.
There is one cheat that saves 36 picoseconds.
There is one cheat that saves 38 picoseconds.
There is one cheat that saves 40 picoseconds.
There is one cheat that saves 64 picoseconds.
You aren't sure what the conditions of the racetrack will be like, so to give yourself as many options as possible, you'll need a list of the best cheats. How many cheats would save you at least 100 picoseconds?
require 'set'

day = "20"
file_name = "12-#{day}-24/sampleIn.txt"
file_name = "input.txt"

data = File.read(file_name).split("\n").map { |i| i.rstrip }

def manhattan(a, b)
  return (a[0] - b[0]).abs + (a[1] - b[1]).abs
end

def aStar(start, goal, walls, memo)
  if walls.include? start
    memo[start] = Float::INFINITY
    return Float::INFINITY
  end
  if memo[start]
    return memo[start]
  end
  seen = Set[start]
  queue = {
    manhattan(start, goal) => [[[start], 0]]
  }

  while queue.size > 0
    quickest = queue.keys.min
    cur = queue[quickest].shift
    curPath = cur[0]
    curLoc = curPath.last
    if queue[quickest].length == 0
      queue.delete(quickest)
    end
    if memo[curLoc]
      return memo[curLoc]
    end
    curDist = cur[1]
    if curLoc == goal
      for i in 0...curPath.length
        memo[curPath[i].clone] = curDist - i
      end
      return curDist
    end

    for d in [[1, 0], [0, 1], [-1, 0], [0, -1]]
      nextLoc = [curLoc[0] + d[0], curLoc[1] + d[1]]
      next if seen.include? nextLoc
      next if walls.include? nextLoc
      seen.add(nextLoc)

      heuristic = curDist + 1 + manhattan(nextLoc, goal)

      newPath = curPath + [nextLoc]

      if not queue[heuristic]
        queue[heuristic] = []
      end
      queue[heuristic].append([newPath, curDist + 1])
    end
  end
  memo[start] = Float::INFINITY
  return Float::INFINITY
end

def cheatStar(start, goal, walls, toBeat, yMax, xMax, noCheatFastest)
  cheats = {}

  seen = Set[start]
  queue = {
    manhattan(start, goal) => [[Set[start], 0, false, start]]
  }

  maxIter = 10
  iter = 0

  while queue.keys.size > 0
    # if iter >= maxIter
    #   break
    # end
    iter += 1
    quickest = queue.keys.min
    cur = queue[quickest].shift
    curPath = cur[0]
    curDist = cur[1]
    cheat = cur[2]
    curLoc = cur[3]
    if queue[quickest].length == 0
      queue.delete(quickest)
    end
    if curLoc == goal
      cheats[cheat] = curDist
      next
    end
    if cheat and not curLoc == cheat
      if not noCheatFastest[curLoc]
        aStar(curLoc, goal, walls, noCheatFastest)
      end
    #   print noCheatFastest
    #   puts
    #   print curLoc
    #   puts
      cheats[cheat] = curDist + noCheatFastest[curLoc] - 1
      next
    end

    for d in [[1, 0], [0, 1], [-1, 0], [0, -1]]
      cheat = cur[2]
      nextLoc = [curLoc[0] + d[0], curLoc[1] + d[1]]
      if nextLoc[0] < 0 or nextLoc[1] < 0 or nextLoc[0] >= yMax or nextLoc[1] >= xMax
        next
      end
      next if curPath.include? nextLoc

      if walls.include? nextLoc
        next if cheat
        next if cheats[nextLoc]
        cheat = nextLoc.clone
      end

      heuristic = curDist + 1 + manhattan(nextLoc, goal)
      next if heuristic >= toBeat - 100

      newPath = curPath + Set[nextLoc]

      if not queue[heuristic]
        queue[heuristic] = []
      end
      queue[heuristic].append([newPath, curDist + 1, cheat, nextLoc])
    end
    # print queue
    # puts
  end

  return cheats
end

def countCheats(start, goal, walls, toBeat, yMax, xMax, noCheatFastest, cheatDist=20, timeSave=100)
    cheats = 0
  
    queue = {
      manhattan(start, goal) => [[Set[start], 0, start]]
    }

    while queue.keys.size > 0
      quickest = queue.keys.min
      cur = queue[quickest].shift
      curPath = cur[0]
      curDist = cur[1]
      curLoc = cur[2]
      if queue[quickest].length == 0
        queue.delete(quickest)
      end
      if curLoc == goal
        return cheats
      end

      for dy in (-1 * cheatDist)..(cheatDist)
        dxMax = cheatDist - dy.abs
        for dx in (-1 * dxMax)..(dxMax)
          cheatTo = [curLoc[0] + dy, curLoc[1] + dx]
          next if walls.include? cheatTo
          if cheatTo[0] < 0 or cheatTo[1] < 0 or cheatTo[0] >= yMax or cheatTo[1] >= xMax
            next
          end
          aStar(cheatTo, goal, walls, noCheatFastest)
          totalDist = curDist + manhattan(curLoc, cheatTo) + noCheatFastest[cheatTo]
          if totalDist <= toBeat - timeSave
            cheats += 1
          end
        end
      end
  
      for d in [[1, 0], [0, 1], [-1, 0], [0, -1]]
        nextLoc = [curLoc[0] + d[0], curLoc[1] + d[1]]
  
        next if walls.include? nextLoc
        next if curPath.include? nextLoc
  
        heuristic = curDist + 1 + manhattan(nextLoc, goal)
        next if heuristic > toBeat - timeSave
  
        newPath = curPath + Set[nextLoc]
  
        if not queue[heuristic]
          queue[heuristic] = []
        end
        queue[heuristic].append([newPath, curDist + 1, nextLoc])
      end
    end
  
    return cheats
end

def part1(input)
  
    start = nil
    goal = nil
    walls = Set[]
    for i in 0...input.length
      for j in 0...input[i].length
        if input[i][j] == "S"
          start = [i, j]
        #   input[i][j] = "."
        end
        if input[i][j] == "E"
          goal = [i, j]
        #   input[i][j] = "."
        end
        if input[i][j] == "#"
          walls.add([i, j])
        end
      end
    end

    memo = {}

    minDist = aStar(start, goal, walls, memo)

    # puts minDist

    # cheatList = cheatStar(start, goal, walls, minDist, input.length, input[0].length, memo)

    # # print cheatList
    # # puts

    # good = 0

    # for i in cheatList.keys
    #   if minDist - cheatList[i] >= 100
    #     good += 1
    #   end
    # end

    # return good
    # 
    return countCheats(start, goal, walls, minDist, input.length, input[0].length, memo, cheatDist=2, timeSave=100)
end

def cheatStar2(start, goal, walls, toBeat, yMax, xMax, noCheatFastest)
    cheats = {}
  
    queue = {
      manhattan(start, goal) => [[Set[start], 0, "unused", start, nil, nil, 0]]
    }


    # path, dist, cheatUsed, curNode, cheatStart, cheatEnd, cheatLen
  
    maxIter = 20000
    iter = 0

    while queue.keys.size > 0
    #   if iter >= maxIter
    #     break
    #   end
    #   iter += 1
      quickest = queue.keys.min
      cur = queue[quickest].shift
      curPath = cur[0]
      curDist = cur[1]
      cheat = cur[2]
      curLoc = cur[3]
      cheatStart = cur[4]
      cheatEnd = cur[5]
      cheatLen = cur[6]
      if queue[quickest].length == 0
        queue.delete(quickest)
      end
      if cheat == "done"
        if walls.include? curLoc
          cheats[[cheatStart, cheatEnd]] = Float::INFINITY
        else
            if not noCheatFastest[curLoc]
                aStar(curLoc, goal, walls, noCheatFastest)
            end
            # print noCheatFastest
            # puts
            # print curLoc
            # puts
            if (not cheats[[cheatStart, cheatEnd]]) or (curDist + noCheatFastest[curLoc] - 1 < cheats[[cheatStart, cheatEnd]])
                cheats[[cheatStart, cheatEnd]] = curDist + noCheatFastest[curLoc]
            end
        end
        next
      end
      if curLoc == goal
        if cheat == "done" or cheat == "in progress"
            if cheatStart == [3, 1]
              puts "here"
            end
            cheats[[cheatStart, goal]] = curDist
        end
        next
      end
  
      for d in [[1, 0], [0, 1], [-1, 0], [0, -1]]
        cheatStart = cur[4]
        cheatEnd = cur[5]
        cheatLen = cur[6]
        cheat = cur[2]
        nextLoc = [curLoc[0] + d[0], curLoc[1] + d[1]]
        if nextLoc[0] < 0 or nextLoc[1] < 0 or nextLoc[0] >= yMax or nextLoc[1] >= xMax
          next
        end
  
        if walls.include? nextLoc
          if cheat == "done"
            raise "I don't think this should happen"
          end
          next if cheatLen >= 20
          if cheat == "unused"
            cheatStart = curLoc
            # nextCheatEnd = nextLoc
            cheatLen = 1
            cheat = "in progress"
          elsif cheat == "in progress"
            # nextCheatEnd = nextLoc
            # nextCheatStart = cheatStart
            cheatLen = cheatLen + 1
            # nextCheat = "in progress"
          end
        elsif cheat == "in progress"
          cheat = "done"
          cheatEnd = nextLoc
          cheatLen = cheatLen
        end
        next if curPath.include? nextLoc
  
        heuristic = curDist + 1 + manhattan(nextLoc, goal)
        aStar(nextLoc, goal, walls, noCheatFastest)
        if cheat == "done"
          heuristic = curDist + noCheatFastest[nextLoc]
        end
        next if heuristic > toBeat - 50
  
        newPath = curPath + Set[nextLoc]
  
        if not queue[heuristic]
          queue[heuristic] = []
        end
        queue[heuristic].append([newPath, curDist + 1, cheat, nextLoc, cheatStart, cheatEnd, cheatLen])
      end
    #   print queue
    #   puts
    end
  
    return cheats
end

puts part1(data)