Мое объяснение и решение C++ для этой проблемы.

Проблема

Описание проблемы и пример ввода можно найти по адресу https://adventofcode.com/2022/day/6.

Нам дана строка символов, и мы должны найти первую позицию в этой строке, где есть 4 уникальных символа в строке.

Рассмотрим пример строки «mjqjpqmgb». Первая серия из 4 уникальных символов — «jpqm», которая заканчивается на 7-м символе. (Примечание: мы используем индексацию на основе 1 для подсчета позиций.) Таким образом, наш ответ будет 7.

Решение

Основная идея: сохранить вектор символов размера 4. Для каждого символа входной строки

  • Добавьте его в вектор и измените размер вектора
  • Проверьте, уникален ли каждый символ в векторе
  • Если найден уникальный вектор, вывести текущую позицию в строке

Кодовое решение — основной метод

Во-первых, мы создаем наш основной метод, где мы инициализируем наши переменные и ввод.

int main() {
    string line;
    ifstream file;
    file.open("input/day6.txt");
    getline(file, line);
    int size = 4;
    cout << parseInput(line, size) << endl;
}

Теперь все входные данные хранятся в одной строке line. Отсюда мы вызываем наш метод parseInput(), чтобы получить наш ответ, который мы печатаем.

Кодовое решение — реализация parseInput()

Далее давайте реализуем parseInput(). Параметры:

  • string line, входные данные, которые мы будем анализировать
  • int size, количество уникальных символов, которые мы хотим

Эта функция вернет целое число, представляющее наш ответ.

int parseInput(string line, int size) {
  vector<char> vec;
  for (int i = 0; i < line.length(); i++) {
    vec.push_back(line.at(i));
    if (vec.size() > size) {
        vec.erase(vec.begin());
    }
    if (vec.size() == size && isUnique(vec)) {
        return i + 1;
    }
  }
  return 0;
}

В приведенной выше реализации кода мы создаем вектор vec для хранения наших символов. Мы перебираем строку с помощью цикла for. При каждом символе строки мы добавляем его в vec,изменяя размер vec при необходимости. Мы вызываем другую функцию, isUnique(), передавая vec. Если это возвращает true, то мы возвращаем позицию, наш ответ.

Кодовое решение — реализация isUnique()

Последнее, что нам нужно реализовать, — это наш метод isUnique(). Параметр представляет собой вектор символов. Этот метод возвращает значение true, если каждый символ в векторе уникален.

Мы используем двойной цикл for, который сравнивает каждый символ друг с другом.

bool isUnique(vector<char> vec) {
    for (int i = 0; i < vec.size(); i++) {
        for (int j = 0; j < vec.size(); j++) {
            if (i == j) {
              break;
            }
            if (vec[i] == vec[j]) {
                return false;
            }
        }
    }
    return true;
}

Код Решение

Теперь давайте соберем все это вместе для нашего окончательного решения кода.

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

bool isUnique(vector<char> vec) {
    for (int i = 0; i < vec.size(); i++) {
        for (int j = 0; j < vec.size(); j++) {
            if (i == j) { break; }
            if (vec[i] == vec[j]) {
                return false;
            }
        }
    }
    return true;
}

int parseInput(string line, int size) {
  vector<char> vec;
  for (int i = 0; i < line.length(); i++) {
    vec.push_back(line.at(i));
    if (vec.size() > size) {
        vec.erase(vec.begin());
    }
    if (vec.size() == size && isUnique(vec)) {
        return i + 1;
    }
  }
  return 0;
}

int main() {
    string line;
    ifstream file;
    file.open("input/day6.txt");
    getline(file, line);
    int size = 4;
    cout << parseInput(line, size) << endl;
}

Запуск кода дает наш ответ. Теперь давайте перейдем к части 2.

День 6 — Часть 2

Задача для части 2 точно такая же, за исключением того, что теперь мы должны найти первую серию из 14 уникальных символов подряд.

Мы можем использовать нашу реализацию из части 1. Все, что нам нужно изменить, это одну строку кода в основном методе. Вместо установки size = 4 мы устанавливаем size = 14.

int main() {
    string line;
    ifstream file;
    file.open("input/day6.txt");
    getline(file, line);
    int size = 4;
    cout << parseInput(line, size) << endl;
}

И теперь мы закончили. Вы также можете получить доступ к файлам моего решения на моем GitHub.