Wyraź liczbę
W latach 60. Francuzi wymyślili program telewizyjny „Des Chiffres et des Lettres” (Cyfry i litery). Celem części programu „Cyfry” było zbliżenie się jak najbliżej określonej 3-cyfrowej liczby docelowej, przy użyciu częściowo losowo wybranych liczb. Zawodnicy mogli korzystać z następujących operatorów:
- konkatenacja (1 i 2 to 12)
- dodatek (1 + 2 to 3)
- odejmowanie (5 - 3 = 2)
- podział (8/2 = 4); dzielenie jest dozwolone tylko wtedy, gdy wynikiem jest liczba naturalna
- mnożenie (2 * 3 = 6)
- w nawiasach, aby zastąpić regularne pierwszeństwo operacji: 2 * (3 + 4) = 14
Każdej podanej liczby można użyć tylko raz lub wcale.
Na przykład liczbę docelową 728 można dokładnie dopasować do liczb: 6, 10, 25, 75, 5 i 50 za pomocą następującego wyrażenia:
75 * 10 - ( ( 6 + 5 ) * ( 50 / 25 ) ) = 750 - ( 11 * 2 ) = 750 - 22 = 728
W tym wyzwaniu dla kodu masz za zadanie znaleźć wyrażenie jak najbliżej określonej liczby docelowej. Ponieważ żyjemy w XXI wieku, wprowadzimy większe liczby docelowe i więcej liczb do pracy niż w latach 60.
Zasady
- Dozwolone operatory: konkatenacja, +, -, /, *, (i)
- Operator konkatenacji nie ma symbolu. Po prostu połącz liczby.
- Nie ma „odwrotnej konkatenacji”. 69 to 69 i nie można jej podzielić na 6 i 9.
- Liczba docelowa jest dodatnią liczbą całkowitą i może zawierać maksymalnie 18 cyfr.
- Istnieją co najmniej dwie liczby do pracy i maksymalnie 99 liczb. Liczby te są również dodatnimi liczbami całkowitymi z maksymalnie 18 cyframi.
- Jest możliwe (a właściwie całkiem prawdopodobne), że liczby docelowej nie można wyrazić w kategoriach liczb i operatorów. Celem jest zbliżenie się jak najbliżej.
- Program powinien zakończyć się w rozsądnym czasie (kilka minut na nowoczesnym komputerze stacjonarnym).
- Obowiązują standardowe luki.
- Twój program może nie zostać zoptymalizowany pod kątem zestawu testowego w sekcji „punktacja” tej układanki. Zastrzegam sobie prawo do zmiany zestawu testowego, jeśli podejrzewam, że ktoś naruszy tę zasadę.
- To nie jest codegolf.
Wejście
Dane wejściowe składają się z tablicy liczb, które można sformatować w dowolny dogodny sposób. Pierwsza liczba to liczba docelowa. Reszta liczb to liczby, z którymi powinieneś pracować, aby utworzyć liczbę docelową.
Wynik
Wymagania dotyczące danych wyjściowych są następujące:
- Powinien to być ciąg znaków, który składa się z:
- dowolny podzbiór liczb wejściowych (oprócz numeru docelowego)
- dowolna liczba operatorów
- Wolę, aby wynik był pojedynczą linią bez spacji, ale jeśli musisz, możesz dodawać spacje i znaki nowej linii według własnego uznania. Zostaną one zignorowane w programie sterującym.
- Wynik powinien być poprawnym wyrażeniem matematycznym.
Przykłady
Dla czytelności wszystkie te przykłady mają dokładne rozwiązanie, a każdy numer wejściowy jest używany dokładnie raz.
Wejście: 1515483, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
Wyjście:111*111*(111+11+1)
Wejście: 153135, 1, 2, 3, 4, 5, 6, 7, 8, 9
Wyjście:123*(456+789)
Wejście: 8888888888, 9, 9, 9, 99, 99, 99, 999, 999, 999, 9999, 9999, 9999, 99999, 99999, 99999, 1
Wyjście:9*99*999*9999-9999999-999999-99999-99999-99999-9999-999-9-1
Wejście: 207901, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0
Wyjście:1+2*(3+4)*(5+6)*(7+8)*90
Dane wejściowe: Dane 34943, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0
wyjściowe: 1+2*(3+4*(5+6*(7+8*90)))
Ale również poprawny wynik to:34957-6-8
Punktacja
Punktacja karna programu jest sumą błędów względnych wyrażeń dla poniższego zestawu testowego.
Na przykład, jeśli wartość docelowa wynosi 125, a twoje wyrażenie daje 120, twój wynik karny to abs (1 - 120/125) = 0,04.
Program z najniższym wynikiem (najniższy całkowity błąd względny) wygrywa. Jeśli dwa programy zakończą się równo, wygrywa pierwsze zgłoszenie.
Wreszcie zestaw testowy (8 przypadków):
14142, 10, 11, 12, 13, 14, 15
48077691, 6, 9, 66, 69, 666, 669, 696, 699, 966, 969, 996, 999
333723173, 3, 3, 3, 33, 333, 3333, 33333, 333333, 3333333, 33333333, 333333333
589637567, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
8067171096, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199
78649377055, 0, 2, 6, 12, 20, 30, 42, 56, 72, 90, 110, 132, 156, 182, 210, 240, 272, 306, 342, 380, 420, 462, 506, 552, 600, 650, 702, 756, 812, 870, 930, 992
792787123866, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169
2423473942768, 1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000, 100000, 2000000, 5000000, 10000000, 20000000, 50000000
Poprzednie podobne łamigłówki
Po utworzeniu tej układanki i umieszczeniu jej w piaskownicy zauważyłem coś podobnego (ale nie tego samego!) W dwóch poprzednich łamigłówkach: tutaj (brak rozwiązań) i tutaj . Ta łamigłówka jest nieco inna, ponieważ wprowadza operatora konkatenacji, nie szukam dokładnego dopasowania i lubię widzieć strategie zbliżania się do rozwiązania bez brutalnej siły. Myślę, że to trudne.
Odpowiedzi:
C ++ 17, wynik 0,0086
Ten program ma niedeterministyczny wynik karny ze względu na wyścigi w wątkach, więc deklaruję na podstawie średnio trzech przebiegów, z których każdy obsłużył zestaw testów w niecałą minutę:
Oto program; wyjaśnienie znajduje się w komentarzach. Można zdefiniować
CONCAT_NONE
dla tradycyjnych reguł odliczania, które nie zezwalają na konkatenację lubCONCAT_DIGITS
na konkatenację wartości wejściowych, ale nie wyników pośrednich. Domyślnie, bez żadnej z tych definicji, stosowane są najbardziej liberalne reguły.Skompilowałem to za pomocą GCC 6.2, używając
g++ -std=c++17 -fopenmp -march=native -O3
(wraz z kilkoma opcjami debugowania i ostrzeżeń).źródło
Python 2.7. Wynik: 167039106
Postanowiłem więc rzucić na to okiem. Nic nadzwyczajnego. Ten program sortuje liczby w odwrotnej kolejności (od dużej do małej) i wypróbowuje kolejno wszystkich operatorów. Płonący szybko, ale wydajność, która zasługuje na zastąpienie.
Oto program:
Dane wyjściowe dla wszystkich przypadków testowych to:
źródło