![](https://habrastorage.org/files/a01/da0/a6a/a01da0a6a0f24e1ba301dec176d1b8ae.png)
Ситилинк прислал письмо в честь дня учителя 16 октября. В письме содержалась ссылка на задачку, решив которую, можно было получить 50 баллов эквивалентных 50 рублям. На работе решать задачку было некогда, а вот в воскресенье время появилось. Вполне очевидно, что задачка решается на основе элементарной логики с использованием бумажки и карандаша со стирательной резинкой, но что делать, если время есть, а голове думать лень. При этом есть дополнительное условие: у вас есть компьютер и за листиком с карандашом идти тоже очень лениво? Автор в курсе, что у Эйнштейна компьютера не было.
Первая пришедшая в голову идея — организовать полный перебор вариантов. Однако, перед написанием кода было вычислено общее количество вариантов, ибо хотелось перебрать в течение одного вечера, и надо было прикинуть шансы.
Ставим задачу: Надо угадать перестановку матрицы 5х5, то есть угадать расположение 25 элементов в матрице. Общее число вариантов: 25! Лучше не браться. Но на самом деле это не так: перестановке подвергаются только элементы матрицы в строках, поэтому общее число вариантов: 24 883 200 000 = 5!^5 = 120^5. А вот это уже реальное число, особенно с учетом того, что пока будут перебираться варианты можно посмотреть Cross Ange.
Решено, кодируем.
В качестве платформы выберем x64 по одной простой причине: нам явно понадобится рекурсия, а за счет ABI на x64 она чуточку быстрее.
Нам понадобятся 3 алгоритма:
- Алгоритм генерации перестановок. Берем со stackoverflow.
- Алгоритм печати матрицы и
- Алгоритм проверки всех условий напишем сами.
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 примерно одинаковы, поэтому… кодируем как быстрее.
Результат под хайдом:![](https://habrastorage.org/r/w1560/files/4c3/e28/678/4c3e286782044b6fb3a97bcdb8863d81.png)
![](https://habrastorage.org/files/4c3/e28/678/4c3e286782044b6fb3a97bcdb8863d81.png)
Полный текст программы для любителей перебирать:
Собирать как консольное приложение.
// 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: Будет огромная просьба ко всем минусующим сказать, в личку или в комментарии, чем плоха статья, что ее так активно минусуют. Ибо статья первая и ее всегда можно исправить.