[задача] Послідовність коду сейфа

Це одна з тих задач які дає на своїх співбесідах google. А я знаю про неї тому що один мій знайомих ходив до них на співбесіду і отримав саме таку задачу.

На мою думку рішення задачі цілком реально знайти і написати за годину, проблема лише в тому що на саме кодування разом з обговоренням задачі вам дадуть 45 хвилин і треба ще буде запропонувати набір тестів, недоліки та можливі оптимізації рішення і таке інше.

Отже…

Задача

У нас є сейф який відкривається 4-значним набором з цифр від 0 до 9. Кожна нова введена цифра зсовує вже введений набір на одну позицію вліво – тобто послідовність 1234567 означає що було введено комбінації 1234, 2345, 3456, та 4567.

Треба реалізувати алгоритм який будує найкоротший рядок в якому були б усі можливі комбінації для відкриття сейфу.

Рішення

Перше – визначимося з довжиною згенерованого рядка. Усього існує 10000 комбінацій – від 0000 до 9999. Якщо враховувати що кожна нова цифра створює нову комбінацію то для 10000 комбінацій нам треба усього 10000 цифр плюс три цифри для першої комбінації. Тобто найкоротший рядок матиме 10003 цифри в ньому.

Щодо генерації комбінації моє рішення виглядає наступним чином:

  1. Для будь-якої початкової комбінації (візьмемо 0000 для простори) позначаємо її як використану і встановлюємо лічильник використаних комбінації в 1.
  2. Якщо знайдено всі комбінації – закінчити.
  3. До останніх трьох цифр згенерованої послідовності додаємо цифру від 0 до 9.
  4. Якщо знайдено комбінацію яку ще не використовували то позначаємо її і збільшуємо лічильник комбінацій на 1, переходимо на крок 2.
  5. Не вдалося знайти не використану комбінацію –  то беремо останні 4 цифри послідовності, знімаємо позначку з відповідної комбінації і зменшуємо лічильник комбінацій на 1. Далі збільшуємо останню цифру до 9.
  6. Якщо знайдено комбінацію яку ще не використано – позначаємо її, збільшуємо лічильник на 1, переходимо на крок 2.
  7. Не вдалося знайти не використану комбінацію і треба повертнутися ще на крок назад. Прибираємо останню цифру з послідовності (послідовність стає коротшою – вертання) і переходимо на крок 5.

Вище наведений алгоритм є алгоритмом з веранням коли ми для знайдення рішення маємо відміняти деякі раніше зроблені кроки. Інший приклад алгоритма з вертанням – задача про генерацію лабіринту.

Ну а тепер моя реалізація.

#include <assert.h>

#include <iostream>
#include <map>
#include <set>

using namespace std;

// Функція знаходить ще не використану комбінацію для останніх трьох цифр поточної послідовності
// і повертає true якщо таку комбінацію вдалося знайти.
// lastDigitStart - з якої цифри починати пошук останньої цифри.
// lastSequence - поточна остання комбінація.
// sequenceUsed - ознака чи використано вже комбінацію (сама комбінація і є індексом).
// sequence - згенерована послідовність.
// idx - індекс нової цифри у згенерованій послідовності.
bool findNewLastDigit(int lastDigitStart, int& lastSequence, bool *sequenceUsed, int* sequence, int& idx)
{
  int lastDigit = lastDigitStart;
  for (int newSequence = (lastSequence % 1000) * 10 + lastDigit; lastDigit <= 9; ++lastDigit, ++newSequence)
  {
    if (!sequenceUsed[newSequence])
    {
      sequenceUsed[newSequence] = true;
      sequence[idx++] = lastDigit;
      lastSequence = newSequence;
      return true;
    }
  }

  return false;
}


// Сам алгоритм.
// sequence - сюди буде записано знайдену послідовність.
void generateSequence(int* sequence)
{
  // позначаємо усі можливі комбінації як ще не використані
  bool sequenceUsed[10000] = { false };

  // перша комбінація у послідовності - 0000
  sequence[0] = sequence[1] = sequence[2] = sequence[3] = 0;
  sequenceUsed[0] = true;

  int foundSequences = 1; // усього знайдено комбінацій

  int lastSequence = 0; // остання знайдена комбінація

  for (int idx = 4; foundSequences < 10000;)
  {
    if (findNewLastDigit(0, lastSequence, sequenceUsed, sequence, idx))
    {
      ++foundSequences; // вдалося знайти нову комбінацію
      continue;
    }

    for (;;)
    {
      // тут ми опинилися бо не вдалося знайти нову комбінацію
      // додаванням цифри і тому треба повернутися до попередньої цифри і змінити її

      // останню комбінацію позначаємо як не використану
      sequenceUsed[lastSequence] = false;
      // зменшуємо лічильник знайдених комбінацій
      --foundSequences;

      // у послідовності переміщуємося на одну цифру вліво...
      lastSequence /= 10;
      --idx;
      lastSequence += sequence[idx - 4] * 1000;

      
      // ...і пробудемо знайти іншу останню цифру
      if (findNewLastDigit(sequence[idx] + 1, lastSequence, sequenceUsed, sequence, idx))
      {
        ++foundSequences; // знайшли іншу останню цифру
        break;
      }

    }
  }
}

int main()
{
  int sequence[10003] = { 0 };

  generateSequence(sequence);

  // прості перевірки далі
  map<int, int> counters;

  // підраховуємо кількість кожної зі знайдених комбінацій
  for (int idx = 3; idx < 10003; ++idx)
  {
    int seq = sequence[idx] + sequence[idx - 1] * 10 + sequence[idx - 2] * 100 + sequence[idx - 3] * 1000;
    counters[seq]++;
  }

  // усього їх має бути 10000
  cout << "Found sequences: " << counters.size() << endl;
  for (const auto &p : counters)
  {
    auto seq = p.first;
    auto count = p.second;

    if (seq < 0 || seq > 9999)
    {
      // комбінація має неприпустиме значення
      cout << "Sequence " << seq << " is illegal" << endl;
    }

    if (count != 1)
    {
      // комбінацію було використано більше одного разу
      cout << "Sequence " << seq << " was used " << count << " times" << endl;
    }

  }

    return 0;
}

 

4 коментаря для “[задача] Послідовність коду сейфа”

    1. Має працювати з будь-якою початковою комбінацією – кожна нова цифра перевіряється від 0 до 9, і лише якщо треба вернутися на крок назад то пробуємо усі цифри починаючи з наступною за тою яка зараз є в останній позиції. Мабуть можна оптимізувати ще якось, але це вже як правило додаткове питання :)

Залишити відповідь