Ситилинк прислал письмо в честь дня учителя 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 примерно одинаковы, поэтому… кодируем как быстрее.
Результат под хайдом:
Полный текст программы для любителей перебирать:
Собирать как консольное приложение.
// 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: Будет огромная просьба ко всем минусующим сказать, в личку или в комментарии, чем плоха статья, что ее так активно минусуют. Ибо статья первая и ее всегда можно исправить.
Комментарии (16)
ReanGD
19.10.2015 16:02+1Только, если не ошибаюсь он просил решить задачу в уме…
3dtim
19.10.2015 16:15+1не все же входят в эти 2%
KvanTTT
19.10.2015 16:28Что-то я сомневаюсь, что эту задачу вообще в уме можно решить. Слишком уж много сущностей.
miriarder
19.10.2015 16:31На самом деле думаю, что можно. У меня получается удерживать в голове шахматную позицию и играть без доски где-то до 15-20 хода, но, это отнимает очень много сил, и при этом реально устаешь. Так что весь вопрос в тренировках и желании.
miriarder
19.10.2015 16:18+1В общем-то не говорится, что она должна быть решена в уме.
en.wikipedia.org/wiki/Zebra_PuzzleReanGD
19.10.2015 16:23wiki:
В своём самом сложном варианте задача предполагает решение в уме, без использования каких-либо записей или средств сохранения информации. Без этих ограничений головоломка заметно теряет в сложности, поскольку может быть решена простым составлением таблицы с исключением заведомо противоречивых вариантов, и, следовательно, мало что говорит о способностях испытуемого.
meft
19.10.2015 16:53+11. про «решить задачу в уме» ничего не сказано (или не нашел)
2. пользуясь бумагой и карандашом решил без особых проблем.
СпойлерВ начале выстраиваются квартиры в правильном порядке.
По условиям только для квартир — всего 2 варианта. И один из них очень быстро отпадает.
Остальное подставляется в уже имеющиеся квартиры.
3ton
19.10.2015 16:44+1Уже несколько лет использую данную реализацию Головоломка Эйнштейна
Только в ней матрица 6Х6. Реально очень затягивает.
ystr
20.10.2015 08:13Отличная логическая игрушка. Кстати, на начальном сайте http://games.flowix.com помниться были даже исходники данной игры. Так что автору данной статьи эти исходники были бы, возможно, также интересны.
Aclz
19.10.2015 18:01[](size_t column) {return matrix[column + 1 + 0 * rowLen] == TRI && matrix[column + rowLen * 0] == CHETIRE; }
Я правильно понимаю, что вы сами предположили, что TRI идет сразу после CHETIRE? (в условиях этого нет, т.к. «справа через энное количество элементов» это тоже «справа»).miriarder
19.10.2015 23:59В противном случае верными являются еще 10 ответов (всего 11):
Еще решениячетверка двушка Студия однушка трешка водила админ строитель менагер адвокат мультиварка смартфон ебук кофемашина телек моноблок писюк нет нубук планшет хомяк змея рыба собака кот четверка двушка Студия однушка трешка водила админ строитель менагер адвокат мультиварка кофемашина ебук смартфон телек моноблок писюк нет нубук планшет кот собака рыба змея хомяк четверка двушка Студия трешка однушка водила админ строитель адвокат менагер мультиварка кофемашина ебук телек смартфон моноблок писюк нет планшет нубук кот собака рыба хомяк змея четверка двушка Студия трешка однушка водила админ строитель адвокат менагер мультиварка кофемашина ебук телек смартфон моноблок писюк нет планшет нубук кот хомяк рыба собака змея четверка двушка однушка Студия трешка водила строитель менагер админ адвокат мультиварка кофемашина смартфон ебук телек моноблок нубук нет писюк планшет кот рыба змея хомяк собака четверка двушка однушка Студия трешка водила строитель менагер админ адвокат смартфон мультиварка кофемашина ебук телек нубук моноблок нет писюк планшет змея рыба собака кот хомяк четверка двушка однушка Студия трешка водила строитель менагер админ адвокат смартфон мультиварка кофемашина ебук телек нубук моноблок нет писюк планшет змея рыба хомяк кот собака четверка двушка однушка Студия трешка водила админ менагер строитель адвокат мультиварка кофемашина смартфон ебук телек моноблок писюк нет нубук планшет кот хомяк змея рыба собака четверка двушка однушка трешка Студия водила строитель менагер адвокат админ мультиварка кофемашина смартфон телек ебук моноблок нубук нет планшет писюк кот рыба змея собака хомяк четверка двушка однушка трешка Студия водила админ менагер адвокат строитель мультиварка кофемашина смартфон телек ебук моноблок писюк нет планшет нубук кот хомяк змея собака рыба
zelyony
del