Inspirowany tym postem na łamigłówkach. Spoilery dla tej układanki są poniżej.
Biorąc pod uwagę trzy dodatnie liczby całkowite jako dane wejściowe, (x, y, z)
skonstruuj obejmujący zakres [x, y]
, połącz ze sobą ten zakres, a następnie usuń z
niekoniecznie kolejne cyfry, aby uzyskać największe i najmniejsze możliwe dodatnie liczby całkowite. Zera wiodące są niedozwolone (tzn. Liczby muszą zaczynać się od [1-9]
). Wypisz te dwie liczby w dowolnej kolejności.
Na przykład z posta „Zagadka” dla wprowadzenia (1, 100, 100)
, największa możliwa liczba to 99999785960616263646566676869707172737475767778798081828384858687888990919293949596979899100
,
a najmniejsza liczba 10000012340616263646566676869707172737475767778798081828384858687888990919293949596979899100
,
zgodnie z poniższą logiką z odpowiedzi Jeffa zamieszczonej tam:
- Nie możemy wpływać na długość liczby (istnieje stała liczba cyfr), więc aby zmaksymalizować wartość, bierzemy maksymalną pierwszą cyfrę, a następnie drugą cyfrę itp.
- Usuń 84 pierwsze nie-dziewiątki (pozostało 16 cyfr do usunięcia):
999995051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100
- Największa liczba w ciągu następnych 17 cyfr to 7, więc odtąd następna cyfra w odpowiedzi może wynosić najwyżej 7 (nie możemy usunąć więcej niż 16 cyfr). Więc usuń 15 nie-7 ... (pozostała 1 cyfra do usunięcia):
999997585960616263646566676869707172737475767778798081828384858687888990919293949596979899100
- Stąd następna cyfra może wynosić najwyżej 8, więc usuń jedną inną niż 8 ze środka:
99999785960616263646566676869707172737475767778798081828384858687888990919293949596979899100
- Podobna logika, ale odwrócona (tzn. Chcemy, aby wiodące
1
s zamiast wiodących9
s) dla najmniejszej liczby.
Oto mniejszy przykład: (1, 10, 5)
.
Konstruujemy zakres 12345678910
i określamy, które 5
cyfry możemy usunąć, pozostawiając możliwie największą liczbę. Oczywiście oznacza to, że chcemy zmaksymalizować cyfrę wiodącą, ponieważ nie możemy wpływać na długość wyjścia. Więc jeśli usuniemy 12345
, zostaniemy z 678910
tym i to jest największe, co możemy zrobić. Tworzenie najmniejszych jest nieco trudniejsze, ponieważ zamiast tego możemy wyciągać liczby ze środka, pozostawiając 123410
możliwie najmniejsze.
Ponieważ (20, 25, 11)
wynik jest raczej nudny, ponieważ 5
i 1
.
Wreszcie, aby wykluczyć odpowiedzi, które próbują zerować, (9, 11, 3)
daje to, 91011
co z kolei daje plon 91
i 10
jest największe i najmniejsze.
I / O i reguły
- Jeśli jest to łatwiejsze / krótsze, możesz zakodować dwa programy / funkcje - jeden dla największego, a drugi dla najmniejszego - w takim przypadku twój wynik jest sumą obu części.
- Dane wejściowe i wyjściowe można podać dowolną dogodną metodą .
- Można założyć, że dane wejściowe pasują do rodzimego typu liczb w twoim języku, jednak nie można założyć, że będzie to połączona liczba ani wynik.
- Dopuszczalny jest pełny program lub funkcja. Jeśli funkcja, możesz zwrócić dane wyjściowe zamiast je drukować.
- Standardowe luki są zabronione.
- To jest golf golfowy, więc obowiązują wszystkie zwykłe zasady gry w golfa, a wygrywa najkrótszy kod (w bajtach).
źródło
9, 11, 3
że tak.Odpowiedzi:
Haskell , 162 bajty
Wypróbuj online!
Korzysta z algorytmu opisanego przez jafe. Może być krótszy, aby użyć mniej wydajnej metody, ale pisanie tego było fajniejsze :)
%
Operacja trwa 4 argumenty (a właściwie 3, ale cokolwiek):m
która to funkcja Wybiera „optymalne” członek z listy (albomaximum
czyminimum
w zależności od tego, co chcemy);f
która jest funkcją „filtrującą”;n
liczba cyfr pozostałych do upuszczenia; is
ciąg. Najpierw sprawdzamy, czy n jest równe liczbie cyfr pozostałych w ciągu (użyłem>=
dla bezpieczeństwa), a resztę odrzucamy,s
jeśli tak. W przeciwnym razie sprawdzamy, czy nadal musimy upuszczać cyfry (n>0
), a następnie używamyspan
do podzielenia naszego ciągu na trzy części:p
cyfry do upuszczenia,c
optymalnie osiągalna cyfra ir
pozostały ciąg. Robimy to, przekazując rozpiętość predykatu, który sprawdza równość względem naszej optymalnej cyfry. Aby znaleźć tę cyfrę, bierzemy pierwszen+1
cyfry ciągu, filtrujemy ją, a następnie przekazujemy do naszej funkcji „selektora”. Teraz uzyskujemy po prostu naszą optymalną cyfrę i powtarzamy, odejmując odp
(liczba upuszczonych cyfr) odn
. Zauważ, że nie przekazujemy naszej funkcji filtrowania do wywołania rekurencyjnego, a zamiast tego zastępujemy jąid
. Wynika to z faktu, że filtr istnieje tylko po to, aby uniknąć wybieraniaminimum
początkowych zer w przypadku, który jest istotny tylko przy pierwszej iteracji. Po tym nie potrzebujemy już żadnego filtra.%
Jest naprawdę tylko funkcję pomocnika dla#
których jest nasza funkcja „prawdziwy”, biorącx
,y
orazz
. Używamy rozumienia listy tylko po to, aby uniknąć odrobiny powtórzeń, iteracji krotek naszej funkcji i przekazywania ich%
wraz zz
łączonym łańcuchem. Ten ciąg jest tworzony za pomocą operatora magicznej monady,(=<<)
który w tym kontekście działa podobnieconcatMap
.źródło
Galaretka , 17 bajtów
Wypróbuj online!
Oblicza wszystkie możliwości, a następnie zachowuje największe i najmniejsze.
Lewy argument:
x,y
konstruować zakres. Właściwy argument:z
cyfry do usunięcia.źródło
Python 2 , 143 bajty
Wypróbuj online!
Działa to poprzez obliczenie wszystkich kombinacji wielkości docelowej (zachowana jest kolejność elementów) i uzyskanie z niej najmniejszych / największych liczb
źródło
Węgiel drzewny , 56 bajtów lub 21 +
4635 =6756 bajtówWypróbuj online! Link jest do pełnej wersji kodu. Wyjaśnienie:
Wprowadź
x
iy
utwórz zakres obejmujący i połącz liczby w ciąg.Zapętlić raz dla każdej cyfry, która ma zostać usunięta
Utwórz listę ciągów utworzonych przez usunięcie każdego możliwego znaku z bieżącego ciągu i weź maksimum.
Wydrukuj wynik.
Wypróbuj online! Link jest do pełnej wersji kodu. Wyjaśnienie:
Wprowadź
x
iy
utwórz zakres obejmujący i połącz liczby w ciąg.Wprowadź
z
i zwiększ to. Następnie tworzę listę o tej długości: muszę mieć możliwość zwiększania wartościz
w następującym filtrze, ale tylko polecenia mogą zwiększać zmienne; istnieje luka, któraPushOperator
zwiększa długość listy.Filtruj według potrzebnych znaków, sprawdzając, czy nie ma niższych znaków w regionie do krojenia. Region zaczyna się od pierwszych
z+1
znaków (ponieważ wz
razie potrzeby możliwe jest odcięcie pierwszego ) i przyrostu punktu końcowego dla każdego przechowywanego znaku. Uważa się, aby nie wybrać zero dla pierwszego znaku.Szybszy algorytm ma 30 bajtów, gdy jest używany do obliczenia największej możliwej liczby:
Wypróbuj online! Link jest do pełnej wersji kodu. Edycja: Od tego czasu udało mi się połączyć powyższe dwa w drugie rozwiązanie 56-bajtowe, które generuje oba wyniki:
Wypróbuj online! Link jest do pełnej wersji kodu. Wyjaśnienie:
Wygeneruj początkowy ciąg.
Reprezentuje
z+1
długość listy.Odwróć listę, klonując ją i zapisz wynik.
Wydrukuj dwa wyniki na osobnych wierszach. (Innym sposobem na to jest rozdzielenie wyników dosłownie
\r
).Wygeneruj największą możliwą liczbę.
Wygeneruj najmniejszą możliwą liczbę za pomocą sklonowanej listy, aby śledzić
z
.źródło
Galaretka ,
1918 bajtówWypróbuj online!
Bardzo nieefektywny, zdecydowanie nie ma sensu,(19292)=305812874887035355118559193163641366325011573739619723360
1, 100, 100
ponieważźródło
05AB1E , 16 bajtów
Wypróbuj online!
Pełny program, odczytuje dane wejściowe w następującej kolejności: y, x, z . Wyświetla listę dwóch list znaków.
Wyjaśnienie
źródło
Ć`‚
to całkiem sprytna, ładna odpowiedź!Matlab, 95 bajtów
Wypróbuj online!
Zwraca macierz 1x2 z min i max.
Jak to działa
źródło