Це одна з тих задач які дає на своїх співбесідах 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;
}

 

Задача

Згенерувати лабіринт в якому можна було б дістатися у будь-яку клітину.

Рішення

Насправді існує більше одного алгоритму рішення цієї проблеми, деякі можна знайти ось тут – https://en.wikipedia.org/wiki/Maze_generation_algorithm. До того ж важливо знати що вимоги до лабіринту можуть бути змінені. Наприклад має бути необхідним щоб був лише один вхід та вихід, чи щоб вхід/вихід були у заданих точках. І так далі.

Спосіб який пояснюю далі на мою думку є найпростішим для розуміння, саме через те я на ньому і зупинився :)

Використовує цей спосіб техніку пошуку з вертанням в якому для усих знайдених, але ще не обролених шляхів зберігаємо їх і повертаємося щоб їх обробити коли зайшли в тупик.

Отже послідовність приблизно така:

  1. Вибираємо випадкову позицію в лабіринті, робимо її поточною та додаємо її в пройдений шлях, клітинку позначаємо як відвідану. Зменшуємо кількість невідвіданих клітин на одну.
  2. Якщо обробили усі клітини – ми завершили генерацію лабіринту.
  3. Для поточної клітини визначаємо напрямки у яких з неї можна переміститися: у напрямку (північ/вгору, південь/вниз, захід/вліво, схід/вправо) можна переміститися лише якщо там є невідвідана клітинка.
  4. Додаємо поточну клітину у пройдений шлях.
  5. Якщо можливих напрямків нема переходимо до кроку 9.
  6. З усих можливих напрямків випадковим чином вибираємо один і прибираємо відповідні стіни у поточної клітини та сусідньої для неї клітини у обраному напрямку. Наприклад, якщо вибрали йти вправо то у поточної клітини прибираємо східну стіну, а у клітини зправа від неї прибираємо ліву стіну.
  7. Робимо клітину до якої переходимо поточною і позначаємо її як відвідану.
  8. Повертаємося до кроку 2.
  9. Прибираємо останню клітину з пройдено шляху.
  10. Якщо у пройденому шляху ще лишилися клітини робимо останню з них поточною. <– Саме тут відбувається вертання звідки і походить назва алгоритму
  11. Повертаємося до кроку 2.

Реалізація

В моєму коді нижче я зберігаю кожну клітинку лабіринту у чарунці двомірного масиву цілих чисел. Значення числа показує які у клітинки є стіни. Навіть якусь кривеньку функцію відобреаження додав, але вона буде працювати лише з певними шрифтами (у мене Lucida Console).

#include "stdafx.h"

#include "time.h"

#include <array>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

#define WALL_NORTH 1
#define WALL_SOUTH 2
#define WALL_EAST  4
#define WALL_WEST  8
#define WALLS_ALL (WALL_NORTH | WALL_SOUTH | WALL_EAST | WALL_WEST)

#define DIR_NORTH 1
#define DIR_SOUTH 2
#define DIR_EAST  4
#define DIR_WEST  8

struct Cell
{
  Cell() : walls(WALLS_ALL), visited(false) {}

  int walls;
  bool visited;
};

struct CellCoords
{
  CellCoords(int _x, int _y) : x(_x), y(_y) {}
  int x, y;
};

class Maze
{
public:
  Maze(int w, int h)
  :
  w_(w), h_(h)
  {
    for (int x = 0; x < h; ++x)
    {
      cells_.push_back(vector<Cell>(w));
    }
  }

  void Generate()
  {
    int unvisited = w_ * h_;

    CellCoords currCell(rand() % h_, rand() % w_);

    stack<CellCoords> trail;
    trail.push(currCell);
    cells_[currCell.x][currCell.y].visited = true;
    --unvisited;

    while (unvisited > 0)
    {
      vector<int> dirs;

      if ((currCell.x > 0) && (!cells_[currCell.x - 1][currCell.y].visited))
      {
        dirs.push_back(DIR_NORTH);
      }
      
      if ((currCell.x < h_ - 1) && (!cells_[currCell.x + 1][currCell.y].visited))
      {
        dirs.push_back(DIR_SOUTH);
      }

      if ((currCell.y > 0) && (!cells_[currCell.x][currCell.y - 1].visited))
      {
        dirs.push_back(DIR_WEST);
      }

      if ((currCell.y < w_ - 1) && (!cells_[currCell.x][currCell.y + 1].visited))
      {
        dirs.push_back(DIR_EAST);
      }

      trail.push(currCell);

      if (!dirs.empty())
      {
        switch (dirs[rand() % dirs.size()])
        {
        case DIR_NORTH:
          cells_[currCell.x][currCell.y].walls &= ~WALL_NORTH;
          cells_[--currCell.x][currCell.y].walls &= ~WALL_SOUTH;
          break;

        case DIR_SOUTH:
          cells_[currCell.x][currCell.y].walls &= ~WALL_SOUTH;
          cells_[++currCell.x][currCell.y].walls &= ~WALL_NORTH;
          break;

        case DIR_EAST:
          cells_[currCell.x][currCell.y].walls &= ~WALL_EAST;
          cells_[currCell.x][++currCell.y].walls &= ~WALL_WEST;
          break;

        default: // case DIR_WEST:
          cells_[currCell.x][currCell.y].walls &= ~WALL_WEST;
          cells_[currCell.x][--currCell.y].walls &= ~WALL_EAST;
          break;
        }

        cells_[currCell.x][currCell.y].visited = true;
        --unvisited;
      }
      else
      {
        trail.pop();

        if (!trail.empty())
        {
          currCell = trail.top();
          trail.pop();
        }
      }
    }

    // add random entrance and exit
    cells_[rand() % h_][0].walls &= ~WALL_WEST;
    cells_[rand() % h_][w_ - 1].walls &= ~WALL_EAST;
  }

  int GetWidth() const { return w_; }
  int GetHeight() const { return h_; }

  vector<Cell>& operator[](unsigned i) { return cells_[i]; }

private:
  int w_, h_;
  vector<vector<Cell>> cells_;
};

// Finds out what wall character to draw for cells
// -----
// |a|b|
// -----
// |c|d|
// -----
// where a, b, c, d are walls value for the cells.
char getWallChar(int a, int b, int c, int d)
{
  const char aWallChars[] = 
  { 
    ' ',    '\xb3', '\xc4', '\xda', 
    '\xb3', '\xb3', '\xc0', '\xc3', 
    '\xc4', '\xbf', '\xc4', '\xc2', 
    '\xd9', '\xb4', '\xc1', '\xc5' 
  };
  bool bWallToWest = (a & WALL_SOUTH) || (c & WALL_NORTH);
  bool bWallToNorth = (a & WALL_EAST) || (b & WALL_WEST);
  bool bWallToEast = (b & WALL_SOUTH) || (d & WALL_NORTH);
  bool bWallToSouth = (c & WALL_EAST) || (d & WALL_WEST);

  int nIndex = ((bWallToWest ? 1 : 0) << 3) |
    ((bWallToNorth ? 1 : 0) << 2) |
    ((bWallToEast ? 1 : 0) << 1) |
    (bWallToSouth ? 1 : 0);
  
  return aWallChars[nIndex];
}

// Finds out what wall character to draw for cells
// -----
// |a|b|
// -----
// where a, b are walls value for the cells.
char getVerticalWallChar(int a, int b)
{
  char ch = ' ';

  if ((a & WALL_EAST) || (b & WALL_WEST))
  {
    ch = '\xb3';
  }

  return ch;
}

// Finds out what wall character to draw for cells
// ---
// |a|
// ---
// |b|
// ---
// where a, b are walls value for the cells.
char getHorizontalWallChar(int a, int b)
{
  char ch = ' ';

  if ((a & WALL_SOUTH) || (b & WALL_NORTH))
  {
    ch = '\xc4';
  }

  return ch;
}

void drawMaze(Maze& a)
{
  int h = a.GetHeight();
  int w = a.GetWidth();

  // draw top row
  for (int y = 0; y < w; ++y)
  {
    if (0 == y)
    {
      // top left corner
      cout << getWallChar(0, 0, 0, a[0][y].walls);
    }
    cout << getHorizontalWallChar(0, a[0][y].walls);
    cout << getWallChar(0, 0, a[0][y].walls, (y == w - 1) ? 0 : a[0][y + 1].walls);
  }
  cout << endl;

  // for the rest of the matrix only draw walls on south, east and south-east
  for (int x = 0; x < h; ++x)
  {
    // draw vertical walls
    for (int y = 0; y < w; ++y)
    {
      if (y == 0)
      {
        // leftmost column
        cout << getVerticalWallChar(0, a[x][y].walls);
      }

      // labyrinth cell - just empty room
      cout << ' ';
      
      // cout << hex << a[x][y].walls; // show cell walls value

      cout << getVerticalWallChar(a[x][y].walls, (y == w - 1) ? 0 : a[x][y + 1].walls);
    }
    cout << endl;

    // draw bottom wall
    for (int y = 0; y < w; ++y)
    {
      bool bLastRow = x == h - 1;
      if (y == 0)
      {
        // leftmost column
        cout << getWallChar(0, a[x][0].walls, 0, bLastRow ? 0 : a[x + 1][0].walls);
      }

      cout << getHorizontalWallChar(a[x][y].walls, bLastRow ? 0 : a[x + 1][y].walls);
      
      bool bLastColumn = y == w - 1;
      cout << getWallChar(a[x][y].walls, 
                          bLastColumn ? 0 : a[x][y + 1].walls, 
                          bLastRow ? 0 : a[x + 1][y].walls,
                          (bLastColumn || bLastRow) ? 0 : a[x + 1][y + 1].walls);
    }
    cout << endl;
  }

  cout << endl;
}

int _tmain(int argc, _TCHAR* argv[])
{
  srand(time(NULL));

  int w = 10, h = 7;
  
  Maze m(w, h);
  m.Generate();
  
  drawMaze(m);

  return 0;
}

 

Приклад згенерованого лабіринту

┌───┬─┬─────────────┐
│   │ │             │
│ │ │ │ ┌───────┐ ──┤
│ │   │ │       │   │
│ └───┤ └─┐ ──┐ └─┬─┤
│     │   │   │   │ │
├───┐ ├── │ │ ├─┐ │ │
│   │ │   │ │ │ │ │ │
│ │ │ │ ──┴─┤ │ │ │ │
│ │   │     │ │   │ │
│ └───┴──── │ │ ──┘ │
│           │ │
│ ──────────┘ ├──── │
              │     │
──────────────┴─────┘