Pojedynczo stratne liczby całkowite: Połączone sekwencje pozbawione jednego elementu

18

Definiuję metodę łączenia sekwencji, aby każda liczba w sekwencji była konkatenowana jako ciąg znaków, a następnie wynikiem jest liczba całkowita.

[1, 2, 3] -> 123

Dla każdej skończonej sekwencji co najmniej 3 kolejnych liczb całkowitych, brakuje dokładnie jednego elementu w sekwencji, a ten brakujący element może nie być pierwszym lub ostatnim elementem w sekwencji, wypisz liczbę całkowitą wynikającą z połączonej sekwencji. Mówię o tym jako o „liczbie pojedynczej stratnej”.

[1, 2, 3] -> {1, 3} (missing an element) -> 13

Ta sekwencja pojedynczo stratnych liczb całkowitych jest sumą następujących podsekwencji (partycji?):

Pierwsza podsekwencja {n, n+2}to A032607 .

{n, n+2}            -> 13, 24, 35, 46, 57, 68, 79, 810, 911, 1012, ...
{n, n+1, n+3}       -> 124, 235, 346, ...
{n, n+2, n+3}       -> 134, 245, 356, ...
{n, n+1, n+2, n+4}  -> 1235, 2346, 3457, ...
{n, n+1, n+3, n+4}  -> 1245, 2356, 3467, ...
{n, n+2, n+3, n+4}  -> 1345, 2456, 3567, ...
... 
for n ∈ ℕ (integers >= 1)

Te liczby całkowite muszą być drukowane w kolejności rosnącej. Pierwszych 25 pojedynczych stratnych liczb całkowitych znajduje się poniżej :

13, 24, 35, 46, 57, 68, 79, 124, 134, 235, 245, 346, 356, 457, 467, 568, 578, 679, 689, 810, 911, 1012, 1113, 1214, 1235, ...

Pierwsze liczby całkowite 7597 Singly Lossy

Implementacje referencyjne bez golfisty. Sprawiłem, że jest szybszy niż mniejszy.

Zasady:

  • Najkrótszy kod wygrywa
  • Możesz albo (powiedzieć, który):
    • Wydrukuj zawsze stratne liczby całkowite
    • Biorąc pod uwagę dodatnią liczbę całkowitą n , wydrukuj lub zwróć pierwsze n elementów jako listę lub ciąg znaków rozdzielany przecinkami lub białymi znakami.
  • Powinieneś obsługiwać dowolnie duże liczby całkowite, jeśli Twój język na to pozwala, zwłaszcza jeśli drukujesz w nieskończoność.

Inspirowany przez / Powiązane

Uwaga: Nie ma jeszcze wpisu w OEIS dla tej sekwencji.

Kolejna uwaga: nazwałem je „Singly Lossy Integers”, aby z kolei mogły być „Doubly Lossy Integers”, „N-ly Lossy Integers”, „(N + 1)-Lossy Integers” oraz „Lossy Integers” „(połączenie wszystkich tych elementów).

mbomb007
źródło
Dodałem listę pierwszych ~ 7600 elementów, a także referencyjną implementację, którą właśnie ukończyłem w Pythonie.
mbomb007
2
To byłoby zabawne fastest-codewyzwanie.
Michael Klein
Tak by było. Czy dopuszczalne jest ponowne opublikowanie wyzwania, ale z innym kryterium wygranej? Jeśli tak, i tak najpierw zaczekam tydzień lub dłużej.
mbomb007
O ile mi wiadomo, powinno być dobrze. Może jednak chcę wejść na czat i poprosić o modyfikację, na wszelki wypadek / po wskazówki.
Michael Klein

Odpowiedzi:

3

Mathematica, 101 bajtów

Sort@Flatten@Table[FromDigits[""<>ToString/@(z~Range~x~Delete~y)],{x,3,#},{z,1,x-1},{y,2,x-z}][[1;;#]]&

Tak! Tym razem mam najkrótszą odpowiedź!Party[Hard]

CalculatorFeline
źródło
1
Czy to jest rzeczywiście wbudowany Mathematica? Nie byłbym zaskoczony. : D
mbomb007
4
Nie, ale można to poprawić za pomocą Party[_]:=While[True,Print["PARTY!!!"]]. Argument jest ignorowany, ponieważ wszystkie imprezy są imprezowe.
CalculatorFeline
1
@CatsAreFluffy Nie zgadzam się. Party[Where]powinien drukować Here!, Party[When]powinien drukować Now!itp. Nie myśl lekko o przyjęciu.
Sanchises
Party[x_]:=Switch[x,Where,"Here!",When,"Now!",How,Pause[1];"...Really?",_,While [True,Print["PARTY!!!"]]]
CalculatorFeline
3

Haskell, 131 , 114 , 106 bajtów

iterate(\n->minimum[x|x<-[read(show=<<filter(/=k)[i..j])::Int|i<-[1..n],j<-[i+2..n],k<-[i+1..j-1]],x>n])13

To jest ograniczona przez rozmiar Int, ale może być łatwo rozszerzony poprzez zastąpienie Intz Integer.

Mniej golfa:

concatInt x = read (concatMap show x) ::Int
allUpToN n = [concatInt $ filter (/=k) [i..j] | i <- [1..n], j <- [i+2..n], k <- [i+1..j-1]]
f n = minimum[x | x <- allUpToN, x > n ]
iterate f 13

8 bajtów golfowanych przez @nimi.

Michael Klein
źródło
Czy to jest nieskończone, czy to zajmuje n?
mbomb007
@ mbomb007 Z Integer, będzie kontynuować, dopóki nie zabraknie pamięci (lub cierpliwości). Będzie kontynuował Int, ale zacznie dawać błędne odpowiedzi, gdy się przepełni ( > 2^29-1).
Michael Klein
Czy możesz podać link do tłumacza, w którym mogę to uruchomić? Wkleiłem go do TryHaskell.org i nie działało.
mbomb007
@ mbomb007 Najlepsze, jakie do tej pory znalazłem, to takie , chociaż wymaga main=print$tego GHCi. W GHC.io zabrakło pamięci, a zestaw funkcji TryHaskell.org jest zbyt ograniczony.
Michael Klein,
Wow, nie robi to daleko, zanim upłynie limit czasu. : D
mbomb007
2

Python 3, 136 127 126 122 bajtów

rozwiązanie brute force, nawet nie próbuję n = 7000 (to już trwa 10s dla n = 100)

r=range
f=lambda n:sorted(int(''.join(str(i+k)for i in r(1,j)if l-i))for k in r(n)for j in r(4,n)for l in r(2,j-1))[:n]

Wyjaśnienie

# f=lambda n:sorted( int(''.join(str(i+k) for i in r(1,j)   if l-i)) for k in r(n) for j in r(4,n) for l in r(2,j-1))[:n]
#            ──┬──                        ───────┬───────    ───┬──  ──────┬──────  ──────┬──────  ────────┬──────── ─┬─
#              │                                 │              │          │              │                │          └── selection of the n first numbers
#              │                                 │              │          │              │                └── loop to remove missing element
#              │                                 │              │          │              └── loop for the dimension of the list n to be sure we miss nothing xD
#              │                                 │              │          └── loop on the n in op description 
#              │                                 │              └── Test to remove missing element
#              │                                 └── loop on {n, n+1 ...} in the op description
#              └──── sort the list

Wyniki

>>> f(25)
[13, 24, 35, 46, 57, 68, 79, 124, 134, 235, 245, 346, 356, 457, 467, 568, 578, 679, 689, 810, 911, 1012, 1113, 1214, 1235]

>>> f(100)
[13, 24, 35, 46, 57, 68, 79, 124, 134, 235, 245, 346, 356, 457, 467, 568, 578, 679, 689, 810, 911, 1012, 1113, 1214, 1235, 1245, 1315, 1345, 1416, 1517, 1618, 1719, 1820, 1921, 2022, 2123, 2224, 2325, 2346, 2356, 2426, 2456, 2527, 2628, 2729, 2830, 2931, 3032, 3133, 3234, 3335, 3436, 3457, 3467, 3537, 3567, 3638, 3739, 3840, 3941, 4042, 4143, 4244, 4345, 4446, 4547, 4568, 4578, 4648, 4678, 4749, 4850, 4951, 5052, 5153, 5254, 5355, 5456, 5557, 5658, 5679, 5689, 5759, 5789, 5860, 5961, 6062, 6163, 6264, 6365, 6466, 6567, 6668, 6769, 6870, 6971, 7072, 7173, 7274, 7375]

Dzięki @ mbomb007 i @FricativeMelon za pomoc

Erwan
źródło
Nie potrzebujesz spacji między a )i następującym znakiem, możesz dodać t=rangena początku programu i zastąpić wszystkie rangewywołania funkcji twywołaniami. To powinno znacznie zmniejszyć liczbę bajtów.
Fricative Melon
@FricativeMelon racja, usunę bezużyteczne miejsce
Erwan
i!=l+kmożna również zastąpić l+k-i, co oszczędza bajt.
Fricative Melon
@FricativeMelon dodałem mały opis :)
Erwan
str(i)for i in r(1+k,j+k)if l+k-imożna zastąpić str(i+k)for i in r(1,j)if l-i, oszczędzając 4 bajty.
mbomb007
1

Python 3, 319 , 270 , 251 bajtów

t,h,n,k,q*=range,input(),1,2,
while h>len(q)or n*k<=len(str(q[h])):
 q+=[int("".join([str(c+s)for c in t(k+1)if c-y]))for s in t(10**~-n,10**n)for y in t(1,k)]
 if~-n:n*=k;k+=1
 else:n,k=k+1,2
 while n//k*k-n:k+=1
 n//=k;q.sort()
print(q[:h])

Pobiera dane hwejściowe ze STDIN i wypisuje tablicę pierwszych hliczb całkowitych bez strat. Jest również bardzo szybki, zajmuje tylko kilka sekund h=7000.

Objaśnienie: Zauważ, że gdybyśmy mieli nieskończony czas, moglibyśmy po prostu iterować wszystkie n,ki dla każdej pary upuścić każdą z n+1,n+2,...,n+k-1( k-1możliwości) i uzyskać wszystkie (nieskończenie wiele) wartości z tych, a następnie po prostu posortować sekwencję w kolejności rosnącej i skrócić do helementy. Oczywiście nie możemy tego zrobić, ale jeśli osiągniemy punkt, w którym pierwsze posortowane helementy nie będą już mogły się zmienić, dodając wartości dowolnych przyszłych n,kpar, możemy po prostu obciąć i wykonać w skończonym czasie. Dla każdej n,kpary ma co najmniej floor(log10(n)+1)*kcyfry, a może nawet więcej. Pozwólmy więc pogrupować te pary według wartości c(n,k)=floor(log10(n)+1)*k, gdzie gwarantujemy, że jeśli c(a,b)<c(n,k)przetworzymy a,bwcześniej n,k. Jeśli mamy posortowaną listę, a jej ostatni element mad cyfry, i d<c(n,k)dla następnejn,kprzetwarzamy, możemy przerwać, ponieważ nie możemy już uzyskać liczby z taką liczbą cyfr lub mniejszą, ponieważ dzięki naszej gwarancji powinniśmy ją już przetworzyć, a zatem bez względu na to, jakie liczby skończymy obliczać, pierwszyh elementy nie mogą się zmienić, więc możemy je po prostu zwrócić.

Teraz potrzebujemy tylko funkcji, która gwarantuje ustaloną kolejność c(n,k). Dla każdego ymożliwego do uzyskania c(n,k), musimy przetwarzać wszystkie (n,k)takie y=c(n,k). Powiedzmy L=floor(log10(n)+1)za trochę n. Dlatego y=L*kmusi trzymać. Zacznij od k=2,L=y/2, a następnie k=3,L=y/3;k=4,L=y/4...k=y,L=1pomiń wartości inne niż całkowite L. Aby wygenerować całą c(n,k)funkcję, należy zacząć (1,2)się y=2i zwiększyć yo 1 i uruchomić ponownie, gdy można dostać L==1. Teraz mamy wyliczenie par (L,k)i spełnia nasze warunki. Jednak musimy pobrać wszystkie możliwe nod L, co robimy przez wyliczanie wszystkich liczb całkowitych zL cyfr. Następnie dla każdej z tych (n,k)par, dla każdej zk-1możliwe usunięte elementy musimy wygenerować liczbę stratną, którą otrzymamy, i dodać ją do naszej listy, która zaczyna się pusta. Następnie sortujemy listę i powtarzamy na następnej (L,k)parze, zatrzymując się, gdy mamy to już d<c(n,k)wcześniej.

Podział kodu (nieco przestarzały):

t=range                     #shortens code
def f(r,n,k):               #helper function
 for s in t(10**~-n,10**n): #for the (L,k) pair, add value of (s,k,y)
  for y in t(1,k):r+=[(int("".join(map(str,[c+s for c in t(k+1)if c!=y]))))]
 if n>1:                    #case where L!=1
  n*=k;k+=1                 #multiply n (which is n'/k from prev iter), inc k
 else:n,k=k+1,2             #reset n and k
 while n//k*k-n:k+=1        #find next proper divisor of n
 return(r,n//k,k)           #divide by that divisor and return
def g(h):                   #main function
 q,a,b=[],1,2               #initial values
 while h>=len(q)or a*b<=len(str(q[h])):(q,a,b)=f(q,a,b);q.sort()
 return q[:h]               #continues until at least h numbers and surpassed current max
Fricative Melon
źródło
Myślę, że len(`q[h]`)powinno być len(str(q[h]))wspieranie dowolnych liczb całkowitych? Lub po prostu powiedz, czy to działa tylko do pewnego ograniczenia, ponieważ bierzesz parametr, a nie drukujesz na zawsze.
mbomb007
Myślałem, że `x` == repr (x) == str (x) dla nieujemnych liczb całkowitych i nie mogę znaleźć żadnego odniesienia do tego, że to nie jest prawda. Jak myślisz, dlaczego to nie jest prawda?
Fricative Melon
Ja wiem , że to nieprawda, bo częściej w golfa w Pythonie. Przykład . Jeśli jest używana, wartość większa niż całkowita wartość maksymalna ( 2**63-1) będzie miała Lna końcu wartość repr. Zauważ, że ten wpis jest prawdopodobnie bardzo daleko w sekwencji.
mbomb007