19.10.2015 12:14
miriarder 16 4225 Источник


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

Комментарии (16)


  1. zelyony
    19.10.2015 15:39
    #8842428

    del


  1. ReanGD
    19.10.2015 16:02
    #8842462
    +1

    Только, если не ошибаюсь он просил решить задачу в уме…


    1. 3dtim
      19.10.2015 16:15
      #8842482
      +1

      не все же входят в эти 2%


      1. KvanTTT
        19.10.2015 16:28
        #8842510

        Что-то я сомневаюсь, что эту задачу вообще в уме можно решить. Слишком уж много сущностей.


        1. miriarder
          19.10.2015 16:31
          #8842520

          На самом деле думаю, что можно. У меня получается удерживать в голове шахматную позицию и играть без доски где-то до 15-20 хода, но, это отнимает очень много сил, и при этом реально устаешь. Так что весь вопрос в тренировках и желании.


    1. miriarder
      19.10.2015 16:18
      #8842490
      +1

      В общем-то не говорится, что она должна быть решена в уме.
      en.wikipedia.org/wiki/Zebra_Puzzle


      1. ReanGD
        19.10.2015 16:23
        #8842500

        wiki:

        В своём самом сложном варианте задача предполагает решение в уме, без использования каких-либо записей или средств сохранения информации. Без этих ограничений головоломка заметно теряет в сложности, поскольку может быть решена простым составлением таблицы с исключением заведомо противоречивых вариантов, и, следовательно, мало что говорит о способностях испытуемого.



    1. meft
      19.10.2015 16:53
      #8842550
      +1

      1. про «решить задачу в уме» ничего не сказано (или не нашел)
      2. пользуясь бумагой и карандашом решил без особых проблем.

      Спойлер
      В начале выстраиваются квартиры в правильном порядке.
      По условиям только для квартир — всего 2 варианта. И один из них очень быстро отпадает.
      Остальное подставляется в уже имеющиеся квартиры.


  1. Denai
    19.10.2015 16:16
    #8842486
    +6

    На хабре эту задачу, кажется, раз в 3 месяца решают перебором


  1. Filippok
    19.10.2015 16:20
    #8842496

    Что ж вы код не причесали перед публикацией? Глазкам больно же :(


    1. miriarder
      19.10.2015 18:33
      #8842666

      Немного подправил. Спасибо за конструктивную критику.


  1. 3ton
    19.10.2015 16:44
    #8842534
    +1

    Уже несколько лет использую данную реализацию Головоломка Эйнштейна

    Только в ней матрица 6Х6. Реально очень затягивает.


    1. ystr
      20.10.2015 08:13
      #8843182

      Отличная логическая игрушка. Кстати, на начальном сайте http://games.flowix.com помниться были даже исходники данной игры. Так что автору данной статьи эти исходники были бы, возможно, также интересны.


  1. Aclz
    19.10.2015 18:01
    #8842642

    [](size_t column) {return matrix[column + 1 + 0 * rowLen] == TRI && matrix[column + rowLen * 0] == CHETIRE; }

    Я правильно понимаю, что вы сами предположили, что TRI идет сразу после CHETIRE? (в условиях этого нет, т.к. «справа через энное количество элементов» это тоже «справа»).


    1. miriarder
      19.10.2015 18:33
      #8842664

      Да. Исходя из того условия, что решение должно быть одно.


    1. miriarder
      19.10.2015 23:59
      #8843014

      В противном случае верными являются еще 10 ответов (всего 11):

      Еще решения
        четверка	    двушка	    Студия	   однушка	    трешка	
    водила	     админ	 строитель	   менагер	   адвокат	
мультиварка	  смартфон	      ебук	кофемашина	     телек	
  моноблок	     писюк	       нет	     нубук	   планшет	
     хомяк	      змея	      рыба	    собака	       кот	

  четверка	    двушка	    Студия	   однушка	    трешка	
    водила	     админ	 строитель	   менагер	   адвокат	
мультиварка	кофемашина	      ебук	  смартфон	     телек	
  моноблок	     писюк	       нет	     нубук	   планшет	
       кот	    собака	      рыба	      змея	     хомяк	

  четверка	    двушка	    Студия	    трешка	   однушка	
    водила	     админ	 строитель	   адвокат	   менагер	
мультиварка	кофемашина	      ебук	     телек	  смартфон	
  моноблок	     писюк	       нет	   планшет	     нубук	
       кот	    собака	      рыба	     хомяк	      змея	

  четверка	    двушка	    Студия	    трешка	   однушка	
    водила	     админ	 строитель	   адвокат	   менагер	
мультиварка	кофемашина	      ебук	     телек	  смартфон	
  моноблок	     писюк	       нет	   планшет	     нубук	
       кот	     хомяк	      рыба	    собака	      змея	

  четверка	    двушка	   однушка	    Студия	    трешка	
    водила	 строитель	   менагер	     админ	   адвокат	
мультиварка	кофемашина	  смартфон	      ебук	     телек	
  моноблок	     нубук	       нет	     писюк	   планшет	
       кот	      рыба	      змея	     хомяк	    собака	

  четверка	    двушка	   однушка	    Студия	    трешка	
    водила	 строитель	   менагер	     админ	   адвокат	
  смартфон	мультиварка	кофемашина	      ебук	     телек	
     нубук	  моноблок	       нет	     писюк	   планшет	
      змея	      рыба	    собака	       кот	     хомяк	

  четверка	    двушка	   однушка	    Студия	    трешка	
    водила	 строитель	   менагер	     админ	   адвокат	
  смартфон	мультиварка	кофемашина	      ебук	     телек	
     нубук	  моноблок	       нет	     писюк	   планшет	
      змея	      рыба	     хомяк	       кот	    собака	

  четверка	    двушка	   однушка	    Студия	    трешка	
    водила	     админ	   менагер	 строитель	   адвокат	
мультиварка	кофемашина	  смартфон	      ебук	     телек	
  моноблок	     писюк	       нет	     нубук	   планшет	
       кот	     хомяк	      змея	      рыба	    собака	

  четверка	    двушка	   однушка	    трешка	    Студия	
    водила	 строитель	   менагер	   адвокат	     админ	
мультиварка	кофемашина	  смартфон	     телек	      ебук	
  моноблок	     нубук	       нет	   планшет	     писюк	
       кот	      рыба	      змея	    собака	     хомяк	

  четверка	    двушка	   однушка	    трешка	    Студия	
    водила	     админ	   менагер	   адвокат	 строитель	
мультиварка	кофемашина	  смартфон	     телек	      ебук	
  моноблок	     писюк	       нет	   планшет	     нубук	
       кот	     хомяк	      змея	    собака	      рыба