Al Zimmermann: non-coplanar points

[dimkadimon]

Herbert Kociemba в сообщении #1108520 писал(а):

I suspected it, but now it is sure. It is Tomas.

Wow big leap forward! If he wins this competition, he will become the first to win 3 in a row! I thought that he was unusually quiet...

He still has some records to go, so there is still hope.

[dimkadimon]

Цитата:

1 24.99 Tomas Rokicki Palo Alto, California, United States 23 Mar 2016 16:08

It's game over.

[Vovka17]

Если Tomas Rokicki выиграет в очередной раз, то это ещё не показатель, что "game over". Я до последнего останусь при своей мысли, что найти оптимальные значения для больших $n$ невозможно в настоящее время. А значит шансы остаются у всех до последнего дня конкурса.
Мне, например, до сих пор не удается даже $n=7$ решить полностью. Интересно до каких $n$ удалось достигнуть текущих максимумов остальным присутствующим (Без указания самих максимумов, разумеется. Кажется это нарушит правила).

[dimkadimon]

Какое то время у меня были максимумы для первых 17 $n$. Несколько даже уникальные рекорды. Но потом пришёл Tomas... Теперь даже не знаю, наверное потерял половину максимумов. N=7 уже две недели ищу рекорд, близко но никак.

[Vovka17]

dimkadimon в сообщении #1108738 писал(а):

N=7 уже две недели ищу рекорд, близко но никак.

О, как! А я думал, что только у меня такие трудности.

dimkadimon в сообщении #1108738 писал(а):

Какое то время у меня были максимумы для первых 17 $n$. Несколько даже уникальные рекорды. Но потом пришёл Tomas... Теперь даже не знаю, наверное потерял половину максимумов.

Я стараюсь отслеживать текущие рекорды. С тех пор, как Jeremy Sawicki потерял свои 25.00, все рекорды для $n>7$ были так или иначе улучшены.

Может кто-нибудь подскажет как визуализировать массив точек в Вольфраме. Уж очень хочется посмотреть на "сферическое распределение" со всех сторон, да нет никаких инструментов для этого.

[dimkadimon]

Vovka17 в сообщении #1108754 писал(а):

О, как! А я думал, что только у меня такие трудности.

Я даже не уверен что рекорд существует, но вроде так близко...

Vovka17 в сообщении #1108754 писал(а):

Может кто-нибудь подскажет как визуализировать массив точек в Вольфраме.

Про Вольфрам не знаю, а в Матлабе несложно используя scatter3.

[Vovka17]

dimkadimon в сообщении #1108784 писал(а):

Я даже не уверен что рекорд существует, но вроде так близко...

А вот здесь не понятно. Я имел ввиду повторить текущий рекорд для $n=7$. Конечно он существует - кто-то же решил уже!

В вольфраме есть функция:

ListPointPlot3D[{{x1,y1,z1},{x2,y2,z2},…}]
generates a 3D scatter plot of points with coordinates .

Казалось бы это то, что надо. Но не работает . Наверное в онлайн-версии не будет. Жаль. Хотелось просто поглядеть что там, да как, не устанавливая для этого сурьезного софта.

[dimkadimon]

Vovka17 в сообщении #1108786 писал(а):

А вот здесь не понятно. Я имел ввиду повторить текущий рекорд для $n=7$. Конечно он существует - кто-то же решил уже!

У меня есть текущий рекорд, а вот улучшить его никак не получается. Хотя может текущий рекорд уже изменился.

Посмотрите что Tomas делает с ближайшими соперниками, он их почти до 24 опустил. У него какой то супер метод, аж страшно!

[Vovka17]

Есть семерка!
Текущий рекорд $n=7$ не изменялся давно. Думаю, что у вас, Дмитрий, максимум и улучшить его уже не удастся.

dimkadimon в сообщении #1108794 писал(а):

Посмотрите что Tomas делает с ближайшими соперниками, он их почти до 24 опустил. У него какой то супер метод, аж страшно!

Он их опережает на 1-2 точки в заданиях, но начиная с достаточно младших $n$, а это самые дорогие баллы.

[dimkadimon]

Vovka17 в сообщении #1108804 писал(а):

Есть семерка!
Текущий рекорд $n=7$ не изменялся давно. Думаю, что у вас, Дмитрий, максимум и улучшить его уже не удастся.

Поздравляю! А вот насчет рекорда у меня еще есть надежда, ведь мы имеем дело с огромным количеством вариантов, даже для $n=7$.

[Pavlovsky]

Herbert Kociemba в сообщении #1106395 писал(а):

As I had expected I made the method work today. Given three arbitrary points it generates a list of all integer grid points which are in the plane defined by the tree points. And this of course without testing all the points of the cube grid individually.

Наконец то и я решил эту задачу для общего случая. Получился простой, красивый и эффективный алгоритм.

1) Представим плоскость в виде: $ax+by+cz+d=0$
2) В цикле переберем координату z из интервала [0,N-1]
3) Получается линейное диафантово уравнение с двумя неизвестными (x,y). Решаем его расширенным алгоритмом Евклида.

Все!

[Vovka17]

Herbert Kociemba в сообщении #1106395 писал(а):

As I had expected I made the method work today. Given three arbitrary points it generates a list of all integer grid points which are in the plane defined by the tree points. And this of course without testing all the points of the cube grid individually.

Раньше я прикидывал сколько плоскостей, содержащих 4 и более точек, содержит куб. Получились следующие цифры (могу и наврать, конечно):

n planes   for1point
2     12       6...6
3    147     25...33
5  16077   349...674
7 346743 3217...5326
...

В третьей колонке - число таких плоскостей, проходящих через одну точку куба.
Получается, что да, в таком подходе нам не надо проверять все сочетания по 4 точки на компланарность, и это круто! Но надо хранить огромный массив с количеством точек на каждой плоскости. И, при добавлении новой точки, отмечать её во всех пересекаемых плоскостях, которых не мало.
Выигрываем ли мы при этом что-то? Хмм...

[dimkadimon]

Pavlovsky в сообщении #1108980 писал(а):

Наконец то и я решил эту задачу для общего случая. Получился простой, красивый и эффективный алгоритм.

1) Представим плоскость в виде: $ax+by+cz+d=0$
2) В цикле переберем координату z из интервала [0,N-1]
3) Получается линейное диафантово уравнение с двумя неизвестными (x,y). Решаем его расширенным алгоритмом Евклида.

Все!

Гениально! Но будет ли это быстрее?

[dmd]

dimkadimon в сообщении #1109002 писал(а):

Но будет ли это быстрее?

Не похоже, чтоб было сильно быстрее. Ведь основная вычислительная трудность в переборе всех вариантов трёх точек для получения $a,b,c,d$. Перебор четвёртой точки для получения $x,y,z$ в максимальном случае N25 составляет порядка $10^6$ обращений к массиву в памяти. Тогда решением вышеуказанного диофантова уравнения мы заменяем порядка $10^4$ переборных операций.

Вот если бы весь перебор у нас состоял из перебора точек $x,y,z$, помноженный на перебор допустимого диапазона значений $d$, а значения $a,b,c$ находились решением соответствующего диофантова уравнения - тогда если решений всего три, то точка $x,y,z$ подходяща и вычислительный выигрыш возможно сильнее.

[Pavlovsky]

Получается забавная теоремка
$ax+by+cz+d=0$
Если a,b,c,d целые числа. a,b<>0
Тогда d+ct делится нацело на gcd(a,b) при любом целом t.