W przypadku obrazu N na N znajdź zestaw pikseli, tak aby odległość separacji nie występowała więcej niż jeden raz. Oznacza to, że jeśli dwa piksele są oddzielone odległością d , to są to jedyne dwa piksele, które są oddzielone dokładnie przez d (używając odległości euklidesowej ). Zauważ, że d nie musi być liczbą całkowitą.
Wyzwanie polega na znalezieniu większego takiego zestawu niż ktokolwiek inny.
Specyfikacja
Nie jest wymagany żaden wkład - w tym konkursie N zostanie ustalony na 619.
(Ponieważ ludzie ciągle pytają - nie ma nic specjalnego w liczbie 619. Została wybrana tak duża, aby optymalne rozwiązanie była mało prawdopodobna, i wystarczająco mała, aby umożliwić wyświetlanie obrazu N na N bez automatycznego zmniejszania go przez Stack Exchange. Obrazy mogą być wyświetlał pełny rozmiar do 630 na 630 i zdecydowałem się na największą liczbę pierwszą, która tego nie przekracza.)
Dane wyjściowe to oddzielona spacjami lista liczb całkowitych.
Każda liczba całkowita na wyjściu reprezentuje jeden z pikseli, ponumerowany w angielskiej kolejności czytania od 0. Na przykład dla N = 3, lokalizacje byłyby ponumerowane w następującej kolejności:
0 1 2
3 4 5
6 7 8
Jeśli chcesz, możesz wyświetlać informacje o postępie podczas biegu, o ile końcowa ocena punktowa jest łatwo dostępna. Możesz wyprowadzać dane do STDOUT lub do pliku, lub cokolwiek najłatwiejszego do wklejenia do Snippet Judge poniżej.
Przykład
N = 3
Wybrane współrzędne:
(0,0)
(1,0)
(2,1)
Wydajność:
0 1 5
Zwycięski
Wynik to liczba lokalizacji na wyjściu. Z prawidłowych odpowiedzi, które mają najwyższy wynik, wygrywa najwcześniej opublikować wynik z tym wynikiem.
Twój kod nie musi być deterministyczny. Możesz opublikować swoje najlepsze wyniki.
Powiązane obszary badań
(Podziękowania dla Abulafii za linki do Golombów)
Chociaż żaden z nich nie jest taki sam jak ten problem, oba mają podobną koncepcję i mogą dać ci pomysły, jak podejść do tego:
- Linijka Golomb : obudowa 1-wymiarowa.
- Prostokąt Golomb : 2-wymiarowe przedłużenie linijki Golomb. Wariant przypadku NxN (kwadrat) znany jako tablica Costas został rozwiązany dla wszystkich N.
Pamiętaj, że punkty wymagane w tym pytaniu nie podlegają tym samym wymogom co prostokąt Golomb. Prostokąt Golomb rozciąga się od przypadku 1-wymiarowego, wymagając, aby wektor z każdego punktu do siebie był niepowtarzalny. Oznacza to, że mogą być dwa punkty oddzielone w odległości 2 poziomo, a także dwa punkty oddzielone w odległości 2 pionowo.
W przypadku tego pytania to odległość skalarna musi być unikalna, więc nie może być zarówno poziomej, jak i pionowej separacji 2. Każde rozwiązanie tego pytania będzie prostokątem Golomb, ale nie każdy prostokąt Golomb będzie prawidłowym rozwiązaniem to pytanie.
Górne granice
Dennis pomocnie zauważył na czacie, że 487 to górna granica wyniku i dał dowód:
Zgodnie z moim kodem CJam (
619,2m*{2f#:+}%_&,
) istnieje 118800 unikalnych liczb, które można zapisać jako sumę kwadratów dwóch liczb całkowitych od 0 do 618 (obie włącznie). n pikseli wymaga między sobą n (n-1) / 2 unikalnych odległości. Dla n = 488 daje to 118828.
Istnieje więc 118 800 możliwych różnych długości między wszystkimi potencjalnymi pikselami na obrazie, a umieszczenie 488 czarnych pikseli spowodowałoby 118828 długości, co uniemożliwiłoby wszystkim ich unikalność.
Byłbym bardzo zainteresowany, aby dowiedzieć się, czy ktoś ma dowód na dolną górną granicę.
Tabela liderów
(Najlepsza odpowiedź każdego użytkownika)
Sędzia stosu fragmentów
źródło
Odpowiedzi:
Python 3,
135136137Znalezione przy użyciu chciwego algorytmu, który na każdym etapie wybiera prawidłowy piksel, którego zestaw odległości do wybranych pikseli pokrywa się najmniej z pikselami innych pikseli.
W szczególności punktacja to
i wybierany jest piksel o najniższym wyniku.
Wyszukiwanie rozpoczyna się od punktu
10
(tj(0, 10)
.). Ta część jest regulowana, więc rozpoczęcie od różnych pikseli może prowadzić do lepszych lub gorszych wyników.Jest to dość powolny algorytm, więc próbuję dodać optymalizacje / heurystykę, a może trochę cofanie się. PyPy jest zalecany ze względu na szybkość.
Każdy, kto próbuje wymyślić algorytm, powinien przetestować
N = 10
, na co mam 9 (ale wymagało to wielu poprawek i wypróbowania różnych punktów początkowych):Kod
źródło
N=10
i jest wiele różnych układów z 9 punktami, ale to najlepsze, co możesz zrobić.SWI-Prolog, wynik 131
Nieco lepsza niż wstępna odpowiedź, ale myślę, że dzięki temu wszystko zacznie się trochę lepiej. Algorytm jest taki sam jak odpowiedź Pythona, z tym wyjątkiem, że próbuje pikseli w alternatywny sposób, zaczynając od lewego górnego piksela (piksel 0), następnie dolnego prawego piksela (piksel 383160), następnie piksel 1, a następnie piksel 383159 itd.
Wkład:
a(A).
Wydajność:
Obraz z fragmentu stosu
źródło
Haskell—
115130131135136Moją inspiracją było Sito Eratostenesa, aw szczególności „Oryginalne sito Eratostenesa” , artykuł Melissy E. O'Neill z Harvey Mudd College. Moja oryginalna wersja (która uwzględniała punkty w indeksie) przesiewała punkty bardzo szybko, z jakiegoś powodu nie mogę sobie przypomnieć, że postanowiłam przetasować punkty, zanim „przesieję” je w tej wersji (myślę, że wyłącznie w celu ułatwienia generowania różnych odpowiedzi za pomocą nowe ziarno w generatorze losowym). Ponieważ punkty nie są już w jakiejkolwiek kolejności, tak naprawdę nie ma już przesiewania, w wyniku czego uzyskanie pojedynczej odpowiedzi na 115 punktów zajmuje kilka minut. Prawdopodobnie nokaut
Vector
byłby teraz lepszym wyborem.Tak więc z tą wersją jako punktem kontrolnym widzę dwie gałęzie, powracające do algorytmu „Oryginalne sito” i wykorzystujące do wyboru monadę Lista lub zamieniające
Set
operacje na ekwiwalentyVector
.Edycja: Więc dla działającej wersji drugiej skręciłem z powrotem w kierunku algorytmu sita, poprawiłem generowanie „wielokrotności” (wybijanie indeksów przez znajdowanie punktów o współrzędnych całkowitych na okręgach o promieniu równym odległości między dowolnymi dwoma punktami, podobnie jak generowanie pierwszych wielokrotności ) i wprowadzanie kilku ciągłych ulepszeń czasowych poprzez unikanie niepotrzebnego przeliczania.
Z jakiegoś powodu nie mogę ponownie skompilować z włączonym profilowaniem, ale uważam, że głównym wąskim gardłem jest teraz cofanie się. Myślę, że zbadanie odrobiny równoległości i współbieżności spowoduje liniowe przyspieszenie, ale wyczerpanie pamięci prawdopodobnie doprowadzi mnie do 2x poprawy.
Edycja: Wersja 3 trochę się meandrowała, najpierw eksperymentowałem z heurystyką biorąc indeksy następnego next (po przesiewaniu z wcześniejszych wyborów) i wybierając ten, który wytworzył następny minimalny zestaw nokautów. Skończyło się to zbyt wolno, więc wróciłem do metody brutalnej siły w całym obszarze wyszukiwania. Pomysł, aby uporządkować punkty według odległości od jakiegoś pochodzenia, przyszedł do mnie i doprowadził do poprawy o jeden punkt (w czasie mojej cierpliwości). Ta wersja wybiera indeks 0 jako początek, może warto wypróbować punkt środkowy płaszczyzny.
Edycja: Podniosłem 4 punkty, zmieniając kolejność przestrzeni wyszukiwania, aby uszeregować według priorytetu najbardziej odległe punkty od środka. Jeśli testujesz mój kod,
135136 to tak naprawdędrugietrzecie znalezione rozwiązanie. Szybka edycja: ta wersja najprawdopodobniej pozostanie produktywna, jeśli pozostanie uruchomiona. Podejrzewam, że mogę remisować na 137, a potem zabraknie mi cierpliwości, czekając na 138.Jedną rzeczą, którą zauważyłem (może to komuś pomóc) jest to, że jeśli ustawisz kolejność punktów od środka płaszczyzny (tj. Usuniesz
(d*d -)
zoriginDistance
), utworzony obraz będzie wyglądał trochę jak rzadka pierwotna spirala.Wydajność
źródło
d
minimalizuje liczbę innych punktów wykluczonych z rozważania poprzez śledzenie okręgów o promieniu zad
pomocą środków obu wybranych punktów, gdzie obwód dotyka tylko trzech innych współrzędnych całkowitych (o 90, 180 i 270 stopni obraca się koło) i prostopadła przecinająca linia przecinająca się bez współrzędnych całkowitych. Tak więc każdy nowy punktn+1
wyklucza6n
inne punkty z rozważenia (przy optymalnym wyborze).Python 3, wynik 129
To jest przykładowa odpowiedź na rozpoczęcie pracy.
Po prostu naiwne podejście do kolejnych pikseli i wybranie pierwszego piksela, który nie powoduje zdublowania odległości separacji, dopóki piksele się nie wyczerpią.
Kod
Wydajność
Obraz z fragmentu stosu
źródło
Python 3, 130
Dla porównania, oto rekurencyjna implementacja backtrackera:
Szybko znajduje następujące rozwiązanie 130 pikseli, zanim zacznie się dusić:
Co ważniejsze, używam go do sprawdzania rozwiązań dla małych skrzynek. Dla
N <= 8
optymalnych należą:W nawiasach podano pierwsze optymalizacje leksykograficzne.
Niepotwierdzone:
źródło
Scala, 132
Skanuje od lewej do prawej i od góry do dołu jak naiwne rozwiązanie, ale próbuje rozpocząć od różnych lokalizacji pikseli.
Wydajność
źródło
Python, 134
132Oto prosty, który losowo zabija część przestrzeni wyszukiwania, aby objąć większy obszar. Iteruje punkty w odległości od kolejności początku. Pomija punkty, które są w tej samej odległości od miejsca początkowego, i wyprzedza, jeśli nie może poprawić się najlepiej. Działa bez końca.
Szybko znajduje rozwiązania z 134 punktami:
3097 3098 2477 4333 3101 5576 1247 9 8666 8058 12381 1257 6209 15488 6837 21674 19212 26000 24783 1281 29728 33436 6863 37767 26665 14297 4402 43363 50144 52624 18651 9996 58840 42792 6295 69950 48985 34153 113313 88637 122569 11956 36098 79401 61471 135610 31796 4570 150418 57797 4581 125201 151128 115936 165898 127697 162290 33091 20098 189414 187620 186440 91290 206766 35619 69033 351 186511 129058 228458 69096 226 456 1696 179 249115 21544 95185 231226 54354 104483 280665 518 147181 318363 1793 248609 82260 52568 365227 361603 346849 331462 69310 90988 341446 229599 277828 382837 339014 323612 365040 269883 307597 3743416 33282
Dla ciekawskich oto kilka brutalnie wymuszonych małych N:
źródło
Fantom 96
Użyłem algorytmu ewolucji, w zasadzie dodawałem k losowych punktów na raz, robiłem to dla j różnych zestawów losowych, a następnie wybrałem najlepszy i powtórzyłem. W tej chwili dość okropna odpowiedź, ale to działa tylko z 2 dziećmi na pokolenie ze względu na szybkość, która jest prawie losowa. Będę grał trochę z parametrami, aby zobaczyć, jak idzie, i prawdopodobnie potrzebuję lepszej funkcji oceniania niż liczby wolnych miejsc.
Wydajność
źródło
Python 3, 119
Nie pamiętam już, dlaczego nazwałem tę funkcję
mc_usp
, chociaż podejrzewam, że miała ona coś wspólnego z łańcuchami Markowa. Tutaj publikuję mój kod, który działałem z PyPy przez około 7 godzin. Program próbuje zbudować 100 różnych zestawów pikseli, losowo wybierając piksele, aż sprawdzi każdy piksel na obrazie i zwróci jeden z najlepszych zestawów.Z drugiej strony, w pewnym momencie powinniśmy naprawdę spróbować znaleźć górną granicę,
N=619
która jest lepsza niż 488, ponieważ sądząc z odpowiedzi tutaj, liczba ta jest zdecydowanie zbyt wysoka. Komentarz Rowan Blush o tym, jak każdy nowy punktn+1
może potencjalnie usuwać6*n
punkty przy optymalnym wyborze, wydawał się dobrym pomysłem. Niestety, po sprawdzeniu formułya(1) = 1; a(n+1) = a(n) + 6*n + 1
, gdziea(n)
jest liczba punktów usuniętych po dodaniun
punktów do naszego zestawu, ten pomysł może nie być najlepszym rozwiązaniem. Sprawdzanie, kiedya(n)
jest większe niżN**2
,a(200)
bycie większym niż619**2
wydaje się obiecujące, alea(n)
większe niż10**2
jest . Będę Cię informować, gdy będę szukał lepszej górnej granicy, ale wszelkie sugestie są mile widziane.a(7)
i udowodniliśmy, że 9 to rzeczywista górna granica dlaN=10
Na moją odpowiedź. Najpierw mój zestaw 119 pikseli.
Po drugie, mój kod, który losowo wybiera punkt początkowy z oktanu kwadratu 619 x 619 (ponieważ punkt początkowy jest inaczej równy pod względem obrotu i odbicia), a następnie co drugi punkt z reszty kwadratu.
źródło