Комментарии 26
А то, ради чего это затевалось в итоге и забыли написать :) Действительно количество решений совпадает с заявленным производителем?
+3
Почему наиболее эффективным оказывается заполнение клеток именно по строкам, потом по слоям?
Вероятно сказывается кэш процессора
0
Это вряд ли. При таком способе обхода оказывается меньше, чем при других число вызовов Solve() — примерно 887 миллионов. Когда я пустил биты для обхода «змейкой», это число увеличилось до 895 млн, а при обходе по кривой Пеано или «от углов к центру» результата я вообще не дождался.
Возможно, сказывается такой факт: для каждой ориентации и каждой клетки есть не более одного положения каждой фигуры, в котором именно эта клетка является «первой». Так что распределение в каком-то смысле самое равномерное. Но важдо ли это для длины обхода — не знаю.
Возможно, сказывается такой факт: для каждой ориентации и каждой клетки есть не более одного положения каждой фигуры, в котором именно эта клетка является «первой». Так что распределение в каком-то смысле самое равномерное. Но важдо ли это для длины обхода — не знаю.
0
По первому вопросу я бы сделал так:
массив из 64 чисел-сумматоров, пробегаемся по всем числам суммируя поднятые биты в соответствующий сумматор, и в конце просто пробегаемся по массиву, выявляю наибольший элемент.
Как то так.
массив из 64 чисел-сумматоров, пробегаемся по всем числам суммируя поднятые биты в соответствующий сумматор, и в конце просто пробегаемся по массиву, выявляю наибольший элемент.
Как то так.
+1
Я так и сделал, но это слишком долго. Можно для каждого положения завести дополнительный массив. в котором явно перечислить поднятые биты — и увеличивать счетчики только для них. Может дать выигрыш до 10 раз (на эту операцию). Но нет ли чего быстрее — через операции над масками?
После такой «сортировки» достаточно найти последний ненулевой элемент — в нем будет маска максимальных битов. Но это еще дольше. Надо искать аналог бинарных вставок (учитывая, что в массиве не более 65 различных элементов).
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 различных элементов).
0
Ничего и недолго, специально проверил в Delphi 7 у меня ушло меньше секунды:
Там где я извращался — это из-за глюков среды — не обращайте внимания.
Для вас здесь представляет интерес работа с битами в строке if (A[i] and Base2[j]) <> 0 then
Удачи!
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
Удачи!
0
Вторая строка
B = Base2
Простите, опечатался.
B = Base2
Простите, опечатался.
0
Для С++ это может выглядеть примерно так
for(int i=1;i<N;i++)
for(int j=0;j<64;j++)
C[j] += (A[i] & Base2[j]) > 0;
0
Сейчас у меня предельная скорость перебора вариантов — около 8 миллионов вызовов Solve секунду. Когда я ввел суммирование, скорость уменьшилась раз в 100. Суммирование выглядело примерно так:
Но это слишком долго. И что хуже всего — эффективность перебора от этого не улучшается.
void AddSum(ulong x){
for(int i=0;x!=0;i++,x>>=1)
if(x&1) C[i]++;
}
}
Но это слишком долго. И что хуже всего — эффективность перебора от этого не улучшается.
0
Вот с этим не поможете:
![image](https://habrastorage.org/r/w780q1/storage/habraeffect/67/c1/67c1330473b442e47b2feb5b41b51d2e.jpg)
Дети у начальника на работе «быстренько разобрали» данную головоломку, теперь начальник требует собрать :)
![image](https://habrastorage.org/storage/habraeffect/67/c1/67c1330473b442e47b2feb5b41b51d2e.jpg)
Дети у начальника на работе «быстренько разобрали» данную головоломку, теперь начальник требует собрать :)
+3
А что у Вас за работа, если не секрет? )
+2
А как называется? Хочу собирать у себя на работе такие.
0
Я правильно вижу, что их 11 штук, из них 10 из 4 кубиков и 1 из 5? И собрать надо треугольную призму 5x5x3? А коричневые кубики что-нибудь значат?
0
Что означают коричневые кубики не знаю, т.к. в первоначальной упаковке головоломку не видел, а собрать не удавалось, но Ваше решение ниже в понедельник проверю.
Возможно это доп. условие — собрать такой вариант, чтобы коричневые были в ряд или еще как, а может и просто отвлекающий маневр…
Возможно это доп. условие — собрать такой вариант, чтобы коричневые были в ряд или еще как, а может и просто отвлекающий маневр…
0
CII CCI FFJ FHH BBH CIG CFD BHJ BJJ KGG EDD EEA KGD EAA KKA
Только надо быть осторожным с ориентацией фигуры I — она несимметрична, и у нее нет пары.
Надеюсь, ничего не перепутал.
+1
Самый важный вопрос — на столе убраться-то удалось? Или так за компьютером и просидел? :)
+1
Я недавно занимался похожей задачей — складывал кубики сома. Вот мои 200 строчек.
+1
Мои 135 строчек для кубиков сома здесь. За 0.0017 секунды нашлось 240 решений (для куба).
0
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Собираем Mini Bedlam Cube