Задачка Эйнштейна для программиста

Ситилинк прислал письмо в честь дня учителя 16 октября. В письме содержалась ссылка на задачку, решив которую, можно было получить 50 баллов эквивалентных 50 рублям. На работе решать задачку было некогда, а вот в воскресенье время появилось. Вполне очевидно, что задачка решается на основе элементарной логики с использованием бумажки и карандаша со стирательной резинкой, но что делать, если время есть, а голове думать лень. При этом есть дополнительное условие: у вас есть компьютер и за листиком с карандашом идти тоже очень лениво? Автор в курсе, что у Эйнштейна компьютера не было.

Первая пришедшая в голову идея — организовать полный перебор вариантов. Однако, перед написанием кода было вычислено общее количество вариантов, ибо хотелось перебрать в течение одного вечера, и надо было прикинуть шансы.

Ставим задачу: Надо угадать перестановку матрицы 5х5, то есть угадать расположение 25 элементов в матрице. Общее число вариантов: 25! Лучше не браться. Но на самом деле это не так: перестановке подвергаются только элементы матрицы в строках, поэтому общее число вариантов: 24 883 200 000 = 5!^5 = 120^5. А вот это уже реальное число, особенно с учетом того, что пока будут перебираться варианты можно посмотреть Cross Ange.
Решено, кодируем.
В качестве платформы выберем x64 по одной простой причине: нам явно понадобится рекурсия, а за счет ABI на x64 она чуточку быстрее.
Нам понадобятся 3 алгоритма:

1. Алгоритм генерации перестановок. Берем со stackoverflow.
2. Алгоритм печати матрицы и
3. Алгоритм проверки всех условий напишем сами.

  bool CheckMatrix(Terms const *matrix)
  {
    bool b = true;
    for (size_t i = 0; b && i < sizeof(ColConds) / sizeof(*ColConds); i++)
    {
      bool c = false;
      for (size_t j = 0; !c && j < rowLen; j++)
      {
        c = c || ColConds[i](j);
      }
      b = b && c;
    }
    progress++;
    if ((progress & (1024 * 1024 - 1)) == 0)
    {
      printf("%I64u\n", progress);
    }
    return b;
  }

Алгоритм печати тривиален, а алгоритм проверки чуть похитрее соберем из двух перегруженных функций, одна из которых собирает рекурсию, а вторая печатает прогресс и проверяет текущее состояние матрицы.
Также нам пригодится массив с условиями, при выполнении которых, перестановку матрицы будем считать подходящей под условие задачи:

  std::function<bool(size_t)>  ColConds[] =
  {
    [](size_t column) {return matrix[0 + 1 * rowLen] == DRIVER; },
    [](size_t column) {return matrix[2 + 3 * rowLen] == NO; },
    [](size_t column) {return matrix[column + 0 * rowLen] == TRI     && matrix[column + rowLen * 3] == TABLET; },
    [](size_t column) {return matrix[column + 2 * rowLen] == SMART   && matrix[column + rowLen * 4] == SNAKE; },
    [](size_t column) {return matrix[column + 1 * rowLen] == MANAGER && matrix[column + rowLen * 0] == ODIN; },
    [](size_t column) {return matrix[column + 1 * rowLen] == ADVOKAT && matrix[column + rowLen * 2] == TV; },
    [](size_t column) {return matrix[column + 0 * rowLen] == STUDIO  && matrix[column + rowLen * 2] == EBOOK; },
    [](size_t column) {return (matrix[column + 2 * rowLen] == COFFEE && matrix[column + 1 + rowLen * 4] == CAT) || (matrix[column + 2 * rowLen] == COFFEE && matrix[column - 1 + rowLen * 4] == CAT); },
    [](size_t column) {return (matrix[column + 1 + 2 * rowLen] == EBOOK  && matrix[column + rowLen * 4] == DOG) || (matrix[column - 1 + 2 * rowLen] == EBOOK  && matrix[column + rowLen * 4] == DOG); },
    [](size_t column) {return matrix[column + 1 * rowLen] == SYSADM  && matrix[column + rowLen * 3] == PC; },
    [](size_t column) {return matrix[column + 1 * rowLen] == BUILDER && matrix[column + rowLen * 4] == FISH; },
    [](size_t column) {return matrix[column + 2 * rowLen] == MULTI   && matrix[column + rowLen * 3] == MONO; },
    [](size_t column) {return (matrix[column + 1 + 1 * rowLen] == DRIVER  && matrix[column + rowLen * 0] == DVA) || (matrix[column - 1 + 1 * rowLen] == DRIVER  && matrix[column + rowLen * 0] == DVA); },
    [](size_t column) {return matrix[column + 1 + 0 * rowLen] == TRI && matrix[column + rowLen * 0] == CHETIRE; }
  };

Да, мне было лень придумывать название для 14 функций, и поэтому я использовал лямбды. Также могу сказать, что в условиях включенных оптимизаций стоимости вызова функции по адресу и через std::function примерно одинаковы, поэтому… кодируем как быстрее.

Результат под хайдом:

Полный текст программы для любителей перебирать:

// EinstainTask.cpp : Defines the entry point for the console application.
#include "stdafx.h"
#include <functional>

//total task complexity: 24 883 200 000 variants = 120^5
namespace
{
  enum Terms
  {
    STUDIO ,  ODIN   , DVA    , TRI    , CHETIRE,
    DRIVER , ADVOKAT , MANAGER, BUILDER, SYSADM,
    MULTI  ,  SMART  , EBOOK  , COFFEE , TV     ,
    PC     ,  MONO   , TABLET , NO     , NOTEBOOK,
    CAT    ,  DOG    , SNAKE  , FISH   , HOMA
  };
  TCHAR const * textDB[] = {
    _T("Студия")     , _T("однушка") , _T("двушка") , _T("трешка")    , _T("четверка"),
    _T("водила")     , _T("адвокат") , _T("менагер"), _T("строитель") , _T("админ"),
    _T("мультиварка"), _T("смартфон"), _T("ебук")   , _T("кофемашина"), _T("телек"),
    _T("писюк")      , _T("моноблок"), _T("планшет"), _T("нет")       , _T("нубук"),
    _T("кот")        , _T("собака")  , _T("змея")   , _T("рыба")      , _T("хомяк"),
  };
  Terms matrix[sizeof(textDB) / sizeof(*textDB)];
  const size_t rowLen = 5;
  unsigned long long progress = 0;
  std::function<bool(size_t)>  ColConds[] =
  {
    [](size_t column) {return matrix[0 + 1 * rowLen] == DRIVER; },
    [](size_t column) {return matrix[2 + 3 * rowLen] == NO; },
    [](size_t column) {return matrix[column + 0 * rowLen] == TRI     && matrix[column + rowLen * 3] == TABLET; },
    [](size_t column) {return matrix[column + 2 * rowLen] == SMART   && matrix[column + rowLen * 4] == SNAKE; },
    [](size_t column) {return matrix[column + 1 * rowLen] == MANAGER && matrix[column + rowLen * 0] == ODIN; },
    [](size_t column) {return matrix[column + 1 * rowLen] == ADVOKAT && matrix[column + rowLen * 2] == TV; },
    [](size_t column) {return matrix[column + 0 * rowLen] == STUDIO  && matrix[column + rowLen * 2] == EBOOK; },
    [](size_t column) {return (matrix[column + 2 * rowLen] == COFFEE && matrix[column + 1 + rowLen * 4] == CAT) || (matrix[column + 2 * rowLen] == COFFEE && matrix[column - 1 + rowLen * 4] == CAT); },
    [](size_t column) {return (matrix[column + 1 + 2 * rowLen] == EBOOK  && matrix[column + rowLen * 4] == DOG) || (matrix[column - 1 + 2 * rowLen] == EBOOK  && matrix[column + rowLen * 4] == DOG); },
    [](size_t column) {return matrix[column + 1 * rowLen] == SYSADM  && matrix[column + rowLen * 3] == PC; },
    [](size_t column) {return matrix[column + 1 * rowLen] == BUILDER && matrix[column + rowLen * 4] == FISH; },
    [](size_t column) {return matrix[column + 2 * rowLen] == MULTI   && matrix[column + rowLen * 3] == MONO; },
    [](size_t column) {return (matrix[column + 1 + 1 * rowLen] == DRIVER  && matrix[column + rowLen * 0] == DVA) || (matrix[column - 1 + 1 * rowLen] == DRIVER  && matrix[column + rowLen * 0] == DVA); },
    [](size_t column) {return matrix[column + 1 + 0 * rowLen] == TRI && matrix[column + rowLen * 0] == CHETIRE; }
  };
  void print()
  {
    for (int i = 0; i < sizeof(textDB) / sizeof(*textDB); i++)
    {
      if (i % rowLen == 0)
        _tcprintf(_T("\n"));
      _tcprintf(_T("%10s\t"), textDB[matrix[i]]);
    }
  }

  bool CheckMatrix(Terms const *matrix)
  {
    bool b = true;
    for (size_t i = 0; b && i < sizeof(ColConds) / sizeof(*ColConds); i++)
    {
      bool c = false;
      for (size_t j = 0; !c && j < rowLen; j++)
      {
        c = c || ColConds[i](j);
      }
      b = b && c;
    }
    progress++;
    if ((progress & (1024 * 1024 - 1)) == 0)
    {
      printf("%I64u\n", progress);
    }
    return b;
  }

  template<typename T>  bool permute(T *v, const size_t start, const size_t n, size_t row);
  bool CheckMatrix(Terms *matrix, size_t row)
  {
    size_t rowCount = 5;
    if (row == (rowCount - 1))
    {
      return  CheckMatrix(matrix);
    }
    else
    {
      return permute(matrix + (row + 1) * rowLen, 0, rowLen, row + 1);
    }
  }

  template<typename T> 
  void swap(T *v, const size_t i, const size_t j)
  {
    T t(v[i]);
    v[i] = v[j];
    v[j] = t;
  }

  template<typename T>
  void rotateLeft(T *v, const size_t start, const size_t n)
  {
    T tmp = v[start];
    for (size_t i = start; i < n - 1; i++) 
    {
      v[i] = v[i + 1];
    }
    v[n - 1] = tmp;
  } // rotateLeft

  template<typename T>
  bool permute(T *v, const size_t start, const size_t n, size_t row)
  {
    if (CheckMatrix(matrix, row))
      return true;
    if (start < n) 
    {
      size_t i, j;
      for (i = n - 2; i >= start; i--)
      {
        for (j = i + 1; j < n; j++) 
        {
          swap(v, i, j);
          if (permute(v, i + 1, n, row))
            return true;
        } // for j
        rotateLeft(v, i, n);
        if (i == 0)
          break;
      } // for i
    }
    return false;
  } // permute
};




int _tmain(int argc, _TCHAR* argv[])
{
  for (int i = 0; i < sizeof(textDB) / sizeof(*textDB); i++)
  {
    matrix[i] = (Terms)i;
  }

  if (permute(matrix, 0, rowLen, 0))
  {
    print();
  }

	return 0;
}

Собирать как консольное приложение.

PS: Серию посмотреть не успел. Перебрало быстрее. По ощущениям, компьютер справился за 4 минуты.
PPS: Тем, кто хочет решить задачку самостоятельно, заглядывать под хайд не советую настоятельно.
PPPS: Будет огромная просьба ко всем минусующим сказать, в личку или в комментарии, чем плоха статья, что ее так активно минусуют. Ибо статья первая и ее всегда можно исправить.