Ситилинк прислал письмо в честь дня учителя 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: Будет огромная просьба ко всем минусующим сказать, в личку или в комментарии, чем плоха статья, что ее так активно минусуют. Ибо статья первая и ее всегда можно исправить.
