Pull to refresh

Comments 26

А то, ради чего это затевалось в итоге и забыли написать :) Действительно количество решений совпадает с заявленным производителем?
Совпадает. Так что здесь возразить нечего :)
Почему наиболее эффективным оказывается заполнение клеток именно по строкам, потом по слоям?

Вероятно сказывается кэш процессора
Это вряд ли. При таком способе обхода оказывается меньше, чем при других число вызовов Solve() — примерно 887 миллионов. Когда я пустил биты для обхода «змейкой», это число увеличилось до 895 млн, а при обходе по кривой Пеано или «от углов к центру» результата я вообще не дождался.
Возможно, сказывается такой факт: для каждой ориентации и каждой клетки есть не более одного положения каждой фигуры, в котором именно эта клетка является «первой». Так что распределение в каком-то смысле самое равномерное. Но важдо ли это для длины обхода — не знаю.
По первому вопросу я бы сделал так:
массив из 64 чисел-сумматоров, пробегаемся по всем числам суммируя поднятые биты в соответствующий сумматор, и в конце просто пробегаемся по массиву, выявляю наибольший элемент.
Как то так.
Я так и сделал, но это слишком долго. Можно для каждого положения завести дополнительный массив. в котором явно перечислить поднятые биты — и увеличивать счетчики только для них. Может дать выигрыш до 10 раз (на эту операцию). Но нет ли чего быстрее — через операции над масками?


for(int i=1;i<N;i++){
  for(int j=0;j<i;j++){
    ulong a=A[i]|A[j];
    A[i]&=A[j];
    A[j]=a;
  }
}


После такой «сортировки» достаточно найти последний ненулевой элемент — в нем будет маска максимальных битов. Но это еще дольше. Надо искать аналог бинарных вставок (учитывая, что в массиве не более 65 различных элементов).
Ничего и недолго, специально проверил в Delphi 7 у меня ушло меньше секунды:
var
  B: array [1..64] of UInt64 = (
                   $1,               $2,               $4,               $8,
                  $10,              $20,              $40,              $80,
                 $100,             $200,             $400,             $800,
                $1000,            $2000,            $4000,            $8000,
               $10000,           $20000,           $40000,           $80000,
              $100000,          $200000,          $400000,          $800000,
             $1000000,         $2000000,         $4000000,         $8000000,
            $10000000,        $20000000,        $40000000,        $80000000,
           $100000000,       $200000000,       $400000000,       $800000000,
          $1000000000,      $2000000000,      $4000000000,      $8000000000,
         $10000000000,     $20000000000,     $40000000000,     $80000000000,
        $100000000000,    $200000000000,    $400000000000,    $800000000000,
       $1000000000000,   $2000000000000,   $4000000000000,   $8000000000000,
      $10000000000000,  $20000000000000,  $40000000000000,  $80000000000000,
     $100000000000000, $200000000000000, $400000000000000, $800000000000000,
    $1000000000000000,$2000000000000000,$4000000000000000,$7999999999999999 + 1
  );

  C: array [1..64] of Integer = (
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
  );

procedure TForm1.Button1Click(Sender: TObject);
const
  N = 10000;
var
  i, j: Integer;
  A: array [1..N] of UInt64;
begin
  Randomize;
  for i := 1 to N do
    A[i] := UInt64((Random(MaxInt) + 1)) * UInt64((Random(MaxInt) + 1));

  for i := 1 to N do
    for j := 1 to 64 do
      if (A[i] and Base2[j]) <> 0 then
        C[j] := C[j] + 1;

  for j := 1 to 64 do
    Memo1.Lines.Add(IntToStr(C[J]));
end;

Там где я извращался — это из-за глюков среды — не обращайте внимания.
Для вас здесь представляет интерес работа с битами в строке if (A[i] and Base2[j]) <> 0 then
Удачи!
Вторая строка
B = Base2
Простите, опечатался.
Для С++ это может выглядеть примерно так
for(int i=1;i<N;i++)
  for(int j=0;j<64;j++)
    C[j] += (A[i] & Base2[j]) > 0;

Сейчас у меня предельная скорость перебора вариантов — около 8 миллионов вызовов Solve секунду. Когда я ввел суммирование, скорость уменьшилась раз в 100. Суммирование выглядело примерно так:

void AddSum(ulong x){
   for(int i=0;x!=0;i++,x>>=1) 
      if(x&1) C[i]++;
  }
}

Но это слишком долго. И что хуже всего — эффективность перебора от этого не улучшается.
Тогда даже не знаю чем вам помочь :(
Вот с этим не поможете:
image
Дети у начальника на работе «быстренько разобрали» данную головоломку, теперь начальник требует собрать :)
А что у Вас за работа, если не секрет? )
Сорри, не у меня, а у супруги. А так то это брендированная подарочная штучка (на обратной стороне на дереве выгравировано Протек).
А как называется? Хочу собирать у себя на работе такие.
Я правильно вижу, что их 11 штук, из них 10 из 4 кубиков и 1 из 5? И собрать надо треугольную призму 5x5x3? А коричневые кубики что-нибудь значат?
Что означают коричневые кубики не знаю, т.к. в первоначальной упаковке головоломку не видел, а собрать не удавалось, но Ваше решение ниже в понедельник проверю.
Возможно это доп. условие — собрать такой вариант, чтобы коричневые были в ряд или еще как, а может и просто отвлекающий маневр…
Программа говорит, что решение единственно.
CII CCI FFJ FHH BBH
  CIG CFD BHJ BJJ
    KGG EDD EEA
      KGD EAA
        KKA

Только надо быть осторожным с ориентацией фигуры I — она несимметрична, и у нее нет пары.
Надеюсь, ничего не перепутал.
Самый важный вопрос — на столе убраться-то удалось? Или так за компьютером и просидел? :)
UFO landed and left these words here
Как и обещали — 19186.
Не удалось. И никогда не удастся — будем реалистами.
Only those users with full accounts are able to leave comments. Log in, please.