Mrrl Feb 24 2011 at 23:55

Собираем Mini Bedlam Cube

6 min

+30

Comments 26

Smi1e Feb 25 2011 at 01:59

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

Mrrl Feb 25 2011 at 04:32

Совпадает. Так что здесь возразить нечего :)

Tishka17 Feb 25 2011 at 06:53

Почему наиболее эффективным оказывается заполнение клеток именно по строкам, потом по слоям?

Вероятно сказывается кэш процессора

Mrrl Feb 25 2011 at 07:05

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

toxicdream Feb 25 2011 at 06:55

По первому вопросу я бы сделал так:
массив из 64 чисел-сумматоров, пробегаемся по всем числам суммируя поднятые биты в соответствующий сумматор, и в конце просто пробегаемся по массиву, выявляю наибольший элемент.
Как то так.

Mrrl Feb 25 2011 at 07:10

Я так и сделал, но это слишком долго. Можно для каждого положения завести дополнительный массив. в котором явно перечислить поднятые биты — и увеличивать счетчики только для них. Может дать выигрыш до 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 различных элементов).

toxicdream Feb 25 2011 at 15:53

Ничего и недолго, специально проверил в 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
Удачи!

toxicdream Feb 25 2011 at 15:54

Вторая строка
B = Base2
Простите, опечатался.

toxicdream Feb 25 2011 at 16:34

Для С++ это может выглядеть примерно так

for(int i=1;i<N;i++)
  for(int j=0;j<64;j++)
    C[j] += (A[i] & Base2[j]) > 0;

Mrrl Feb 25 2011 at 16:48

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

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

Но это слишком долго. И что хуже всего — эффективность перебора от этого не улучшается.

toxicdream Feb 25 2011 at 17:06

Тогда даже не знаю чем вам помочь :(

mihmig Feb 25 2011 at 12:02

Вот с этим не поможете:

Дети у начальника на работе «быстренько разобрали» данную головоломку, теперь начальник требует собрать :)

Xarakternik Feb 25 2011 at 12:25

А что у Вас за работа, если не секрет? )

mihmig Feb 25 2011 at 12:28

Сорри, не у меня, а у супруги. А так то это брендированная подарочная штучка (на обратной стороне на дереве выгравировано Протек).

infom Feb 25 2011 at 12:25

А как называется? Хочу собирать у себя на работе такие.

Mrrl Feb 25 2011 at 16:53

Я правильно вижу, что их 11 штук, из них 10 из 4 кубиков и 1 из 5? И собрать надо треугольную призму 5x5x3? А коричневые кубики что-нибудь значат?

mihmig Feb 26 2011 at 11:52

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

Mrrl Feb 26 2011 at 12:05

Программа говорит, что решение единственно.

Mrrl Feb 25 2011 at 19:04

CII CCI FFJ FHH BBH
  CIG CFD BHJ BJJ
    KGG EDD EEA
      KGD EAA
        KKA

Только надо быть осторожным с ориентацией фигуры I — она несимметрична, и у нее нет пары.
Надеюсь, ничего не перепутал.

mihmig Feb 28 2011 at 12:18

Спасибо!

twelve Feb 25 2011 at 12:31

Самый важный вопрос — на столе убраться-то удалось? Или так за компьютером и просидел? :)

UFO just landed and posted this here

Mrrl Feb 25 2011 at 16:50

Как и обещали — 19186.

Mrrl Feb 25 2011 at 16:54

Не удалось. И никогда не удастся — будем реалистами.

les_sosna Feb 25 2011 at 12:41

Я недавно занимался похожей задачей — складывал кубики сома. Вот мои 200 строчек.

Mrrl Feb 27 2011 at 19:07

Мои 135 строчек для кубиков сома здесь. За 0.0017 секунды нашлось 240 решений (для куба).

Show the best of all time