Dart

Simple path-finding + brute force. O(n*sqrt-n) I think but only takes ~200 milliseconds so that’ll do for today. Time to walk the dog!

After being so pleased to have written my own path-finding algorithm the other day, I discovered that my regular more library already includes one. D’oh.

(edit: shaved some milliseconds off)

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;
}