Sposoby określania losowego generowania w wyzwaniach

Uwaga : Zgodnie z konsensusem w sprawie Meta , wyzwanie pisanie pytania na temat tutaj.

W świetle tej „rzeczy, której należy unikać podczas pisania wyzwań” , zacząłem myśleć o wyzwaniach związanych z losowym generowaniem pewnych rodzajów obiektów.

Czasami zdarza się, że chcę opublikować wyzwanie związane z golfem, które polega na losowym generowaniu foo, gdzie

1. bardzo łatwo jest sprawdzić, czy dana rzecz jest foo, i
2. nieco trudniej jest szybko wygenerować losowego foo „dobrej jakości”.

Na przykład foo może być macierzą binarną, w której nie ma segmentów 4 równych bitów w dowolnym kierunku. Łatwo jest sprawdzić, czy dana macierz binarna jest foo, ale generowanie losowej foo z ładnie rozłożonym rozkładem wydaje się wymagać algorytmu cofania lub czegoś podobnego.

W każdym razie, teraz muszę obiektywnie określić, co kwalifikuje się jako losowy foo, i chciałbym, aby było to „nieprzewidywalne” w intuicyjnym sensie, że kiedy uruchamiam program kilka razy, wyniki zawsze wyglądają inaczej. Najbardziej restrykcyjnym podejściem jest wymaganie, aby dane wyjściowe były jednakowo losowe: wszystkie ważne fo mają takie samo prawdopodobieństwo wygenerowania. Jest to zwykle zbyt restrykcyjne, ponieważ nie mam pojęcia, jak to zrobić, aby wygenerować wszystkie prawidłowe foos, usunąć duplikaty i wybrać taki, który jest nudny i powolny.

Moim następnym pomysłem jest wymaganie, aby wszystkie prawidłowe foos miały dodatnie prawdopodobieństwo wygenerowania. Oznacza to jednak, że obowiązuje następujące podejście: wygeneruj losową rzecz podobną do foo (w naszym przykładzie losową macierz binarną), jeśli jest to foo, zwróć ją, w przeciwnym razie zwróć foo zakodowane na stałe (powiedzmy, macierz tożsamości ). Jest to również nieco nudne, ponieważ jest to po prostu tylko rozpoznawanie foos przyczepionych do generatora losowej macierzy.

Czy może istnieć ładna ogólna definicja nieprzewidywalnie losowego foo?

TL; DR

Czy istnieje dobry sposób na określenie „nieprzewidywalnego” losowo generowanego obiektu, który nie naprawia dystrybucji, ale zniechęca do kodowania?

Zwróć tysiąc różnych pianek

To sprawia, że ​​niemożliwe jest zwracanie zakodowanych wartości i posiadanie pół przyzwoitego golfa. Jednak legalny generator foo ma niewielką szansę na wydanie zduplikowanych plików fo, chyba że faktycznie je sprawdza. Aby usunąć ciężar sprawdzania, można określić empirycznie testowany wskaźnik awarii, powiedzmy 10%, jako dopuszczalny.

Miej świadomość paradoksu urodzinowego , że prawdopodobieństwo duplikatów może być wyższe niż myślisz. Jeśli istnieje tylko milion możliwych foos, tysiąc losowych foos będzie miało prawdopodobieństwo około 0,6, że gdzieś jest duplikat, i to przy założeniu, że generowanie foo jest całkowicie jednolite. Jeśli może to być problem, wymagaj powiedzmy 900 unikalnych foos na każde 1000 wygenerowanych, co jest o wiele bardziej hojne dla prawdziwego generatora foo, ale nadal niepraktyczne dla twardego kodowania.

Pozwala to również na wielokrotne generowanie rzeczy podobnych do foo i sprawdzanie, czy nie ma foo. Myślę, że to jest prawidłowe rozwiązanie, ale jeśli ci się nie podoba:

Zrób to szybko

Szanse na to, że zupełnie przypadkowa foo-foo będzie foo, są prawdopodobnie dość niskie, więc określenie limitu czasowego prawdopodobnie zmusi prawdziwą próbę wygenerowania foo.

Aby dostosować się do różnic prędkości między różnymi językami, możesz chcieć mieć różne ograniczenia czasowe w zależności od języka, takiego jak Hackerrank: https://www.hackerrank.com/environment . Jeśli jednak określisz wystarczająco duże fo, prawdopodobieństwo, że losowe rzeczy podobne do foo będą foo, może być naprawdę niskie, więc reguła „przed śmiercią wszechświata” może być wystarczająca.

Nie twierdzę, że mam najlepsze rozwiązanie problemu (lub że ta lista jest wyczerpująca), ale chcę nakreślić kilka możliwych podejść, które przychodzą mi na myśl i dlaczego one działają lub nie. Nie zajmę się również kwestiami stycznymi, takimi jak to, czy użycie bieżącego znacznika czasu jako źródła losowości jest wystarczająco „nieprzewidywalne” i jak wymusić pewne właściwości rozkładu prawdopodobieństwa - skupię się na unikaniu rozwiązań wykorzystujących kodowanie na twardo.

To nie rozwiązanie: nie zezwalaj na kodowanie w sposób jawny

To jest zły pomysł. Jest to wymóg, którego nie można zaobserwować (co oznacza, że ​​nie można stwierdzić, czy jest on spełniony po prostu przez uruchomienie programu), co jest zdecydowanie odradzane na PPCG i może być całkowicie niemożliwe, jeśli program jest uruchamiany na jakiejkolwiek innej platformie, gdzie zgłoszenia są weryfikowane w sposób automatyczny. Problem z takim wymogiem polega na tym, że musisz zacząć od znalezienia obiektywnej definicji „twardego kodowania”. Ogólnie rzecz biorąc, jeśli spróbujesz tego, tylko pogorszysz sytuację.

Uczyń kodowanie niemożliwym

Jeśli nie możesz całkowicie tego zabronić, ale nie chcesz, aby ludzie z niego korzystali, możesz spróbować zaprojektować takie wyzwanie, aby kodowanie po prostu nie było podejściem konkurencyjnym. Jest to możliwe, jeśli obiekty, które powinny zostać wygenerowane, są wystarczająco duże i nieściśliwe, dlatego umieszczenie jednego przykładu w kodzie wymagałoby znacznie więcej bajtów niż napisanie algorytmu generującego losowo prawidłowe rozwiązania. W twoim konkretnym przykładzie tak nie jest, ponieważ macierze tożsamości są poprawne i generalnie są łatwe do wygenerowania, ale w przypadku innych problemów może tak nie być. Jeśli obiekty docelowe są wystarczająco nieregularne, po prostu wymagają, aby miały duży rozmiar, co prawdopodobnie nie wpłynie na liczbę bajtów rzeczywistego algorytmu, ale spowoduje wysadzenie zakodowanej części.

Sparametryzuj wyjście

Często problemy te mają jeden lub więcej parametrów naturalnych, takich jak rozmiar matrycy w twoim przykładzie. Jeśli tak, uczynienie z tego parametru danych wejściowych może być wystarczające, aby uniemożliwić lub przynajmniej niepraktyczne kodowanie na stałe. W niektórych przypadkach ustalenie jednego konkretnego rozwiązania dla danej wartości parametru, który został znaleziony ręcznie lub za pomocą szczegółowego wyszukiwania, może być łatwe, ale być może nie ma prostej formy zamkniętej dla danego rozwiązania, więc nie jest możliwe jest łatwe wygenerowanie wartości domyślnej dla dowolnych danych wejściowych. Ponownie, nie jest tak w przypadku wspomnianego przykładu, ponieważ macierz tożsamości działa w dowolnym rozmiarze, ale jest optymalnym rozwiązaniem dla tego pokrewnego problemujest zwykle bardzo nieregularna, więc nie można mieć wartości domyślnej bez aktywnego wyszukiwania prawidłowych wartości. Możesz połączyć to z limitem czasowym, aby uniknąć brutalnego poszukiwania wartości domyślnej.

Nałóż pewne ograniczenie na rozkład prawdopodobieństwa

Jeśli chcesz zrezygnować z całkowicie nieograniczonego rozkładu prawdopodobieństwa, możesz nałożyć na niego pewne ograniczenia, które nadal zapewniają odbiorcom dużą swobodę w wyborze ich rozkładu, ale które utrudniają lub utrudniają kodowanie na stałe:

• Najprostszym ograniczeniem, jakie przychodzi na myśl, jest wymaganie różnicy między minimalnym a maksymalnym prawdopodobieństwem, aby każdy możliwy wynik był poniżej pewnego progu. Podejście zakodowane prawdopodobnie będzie miało prawie zerowe prawdopodobieństwo dla prawie wszystkich wyników i prawdopodobieństwo zbliżone do 1 dla wartości domyślnej. Jeśli potrzebujesz, aby maksymalna różnica była mniejsza niż 0,1, powiedzmy, musiałoby być 10 (losowo wybranych) wartości domyślnych, aby podejście było opcją. Podobnie możesz również wymagać minimalnego prawdopodobieństwa dla każdego możliwego wyjścia, np. 1 / (2 * N *), gdzie N jest liczbą możliwych wyjść.
• Alternatywnie możesz wymagać, aby nie było żadnych (prawdopodobieństwa) luk w rozkładzie, aby nie było przedziału wielkości δ (wybranego przez ciebie) , tak aby istniały zarówno wyższe, jak i niższe prawdopodobieństwa. Oznacza to, że nie może być żadnych wartości odstających pod względem prawdopodobieństwa, które prawdopodobnie są generowane przez podejście kodujące.

Głównym problemem związanym z tymi podejściami jest to, że trudniej je uzasadnić, udowodnienie poprawności odpowiedzi jest trudne, a eksperymentalne sprawdzenie poprawności może być niemożliwe w przypadku dużych przestrzeni wyjściowych. Mimo to zapewniają one zasadniczo obserwowalne wymagania dla programu, które mogą uniemożliwić kodowanie na stałe.

Podejścia te mogą również wymagać ograniczenia czasowego, ponieważ jednym ze sposobów zwiększenia prawdopodobieństwa wartości innych niż domyślne byłoby kilkakrotne znalezienie losowego foo przed powrotem do wartości domyślnej.