AoC 2017: Ден 9

Това е 9-ата публикация в продължаващата ми поредица за „Advent of Code 2017“. Ще опиша моите решения, внедрени в JS (ES6+) и Node.js.

TL;DR: това е интересен проблем, включващ идеи от сканиране на низове, съвпадение на скоби и малко допълнително мислене.

Описанието на проблема е тук: http://adventofcode.com/2017/day/9, а входът може да бъде намерен тук: http://adventofcode.com/2017/day/9/input.

Част първа

Изчистване на боклука

Проблемът дефинира клас от добре оформени низове, които също могат да съдържат някакъв боклук. Боклукът се държи подобно на коментарите в езиците за програмиране: има специфични разделители (<>), вътре в тях нищо няма значение, а също така вътре в тях има символ за избягване-игнориране (!), който основно изхвърля знака след него.

Преди да се доближим до действителния проблем (преброяване на резултата на групите), нека премахнем целия боклук от низа.

Това е идеално приложение на подхода за сканиране на низове: проверявайте по един знак и запазвайте някакво състояние.

Ето очертанието на алгоритъма:

• поддържаме масив от добри (без боклук) срезове
• запазваме текущия добър срез (обозначен с неговия звезден индекс)
• ние държим флаг дали сме вътре в блока за боклук в момента или не
• сканираме всички знаци един по един
• ако срещнем символа !, просто го пропускаме и следващия. Вече не е нужно да ни е грижа за бягствата
• ако срещнем символа <, отбелязваме, че сега сме в боклука. Ако преди това не сме били, вземаме добрия срез (от началната му точка и до текущия символ) и го добавяме към масива
• ако срещнем символа >, отбелязваме, че вече не сме в боклука и следващият добър отрязък започва от знака точно след >
• когато приключим, може да има опашка на низа след последния боклук, което също е добър отрязък

А ето и изпълнението на алгоритъма:

const clearGarbage = input => {
  const res = [];
  let start = 0;
  let i = 0;
  const l = input.length;
  let inGarbage = false;
  while (i < l) {
    const char = input[i];
    switch (char) {
      case "<":
        if (!inGarbage) {
          res.push(input.substring(start, i));
        }
        inGarbage = true;
        break;
      case "!":
        i++;
        break;
      case ">":
        start = i + 1;
        inGarbage = false;
        break;
    }
    i++;
  }
  res.push(input.substring(start));
  return res.join("");
};

Изчистване на още неподходящи неща

Сега, след като изчистихме целия боклук от низа, оставаме с групите. Групите се означават с {} фигурни скоби и могат да съдържат повече групи вътре в тях. Няколко групи братя и сестри са разделени със запетаи.

Но това, което е интересно за нашия проблем е, че всъщност вече не ни интересуват други символи освен {}. Така че нека получим наистина изчистения вход:

const { readFile } = require("../lib");

const input = readFile("./input");
const clearedInput = clearGarbage(input).replace(/[^{}]/g, "");

Балансирани групи

И накрая, истинският проблем. На всяка група се дава резултат според нейната дълбочина. Как да броим общия резултат на всички групи?

Ето идеите, които ще ни помогнат:

• групите от най-високо ниво имат резултат 1 по дефиниция
• всяка по-дълбока група има резултат по-висок с 1 от своята родителска група
• всеки { започва новата група увеличава текущата дълбочина с 1
• всяко } завършва най-скоро отворената група и намалява текущата дълбочина с 1
• всеки път, когато групата се затвори, знаем нейния резултат - това е текущата стойност на дълбочината точно преди затварянето на групата

И така, ето алгоритъма, базиран на тези идеи:

let total = 0;
let currentWeight = 0;

for (const char of clearedInput) {
  if (char === "{") {
    currentWeight++;
  } else {
    total += currentWeight;
    currentWeight--;
  }
}

console.log(total);

Проследяваме текущия резултат, като започваме от 0, преди да се потопим в която и да е група, съответно го добавяме/намаляваме и добавяме към общия резултат всеки път, когато групата бъде затворена. Свършен.

И пълното решение, както винаги:

Част две

Предишните части биха могли да имат малко по-кратко решение, комбиниращо двете сканирания (за боклук и за групи) в едно. Но благодарение на нашето разделяне на проблемите сега е много по-лесно да го адаптирате към втората част на проблема: пребройте всички ненужни знаци, запазете избягалите игнорирани.

Идеята е основно същата като в скенера за боклук, само с текущ брой, който се увеличава всеки път, когато видим знак (с изключение на ! и знака след него) и сме вътре в блока за боклук.

Освен това тук няма много за обяснение, вижте сами:

Бонус: Clojure