Odwróć numer trójkąta


30

Załóżmy, że podajesz liczby całkowite w trójkącie, a następnie odwracasz je od lewej do prawej. Podając liczbę, wypisz numer, na który została wysłana. To jest odwrotne odwzorowanie.

         1                      1         
       2   3                  3   2       
     4   5   6    <--->     6   5   4     
   7   8   9  10         10   9   8   7   
11  12  13  14  15     15  14  13  12  11

To jest n-ty element A038722 z jednym indeksem:

1, 3, 2, 6, 5, 4, 10, 9, 8, 7, 15, 14, 13, 12, 11, ...

Ta sekwencja odwraca ciągłe fragmenty liczb całkowitych dodatnich wraz ze wzrostem długości:

 1, 3, 2, 6, 5, 4, 10, 9, 8, 7, 15, 14, 13, 12, 11, ...
<-><----><-------><-----------><------------------>

Przypadki testowe:

1 -> 1
2 -> 3
3 -> 2
4 -> 6
14 -> 12
990 -> 947
991 -> 1035
1000 -> 1026
1035 -> 991
1036 -> 1081
12345 -> 12305

Tabela liderów:

Odpowiedzi:


15

JavaScript (ES7), 26 bajtów

n=>((2*n)**.5+.5|0)**2-n+1

Wdrożenie następującej formuły z OEIS :

formula

Próbny


Lubię operację OR, aby podzielić ją na liczbę całkowitą! dobra robota!
CraigR8806

7

Galaretka , 8 7 bajtów

RṁR€UFi

Dzięki @ErikTheOutgolfer za uratowanie 1 bajtu!

Wypróbuj online!

Jak to działa

RṁR€UFi  Main link. Argument: n

R        Range; yield [1, ..., n].
  R€     Range each; yield [[1], [1, 2], [1, 2, 3], ..., [1, ..., n]].
 ṁ       Mold the left argument like the right one, yielding
         [[1], [2, 3], [4, 5, 6], ...]. The elements of the left argument are 
         repeated cyclically to fill all n(n+1)/2 positions in the right argument.
    U    Upend; reverse each flat array, yielding [[1], [3, 2], [6, 5, 4], ...].
     F   Flatten, yielding [1, 3, 2, 6, 5, 4, ...].
      i  Index; find the first index of n in the result.

6

Alice , 27 bajtów

Dzięki Sp3000 za .Cpomysł.

/o
\i@/.2:e2,tE*Y~Z.H2*~.C+

Wypróbuj online!

Wyjaśnienie

Myślę, że może być krótszy sposób na obliczenie tego za pomocą liczb trójkątnych, ale pomyślałem, że jest to ciekawe nadużycie wbudowanej, więc oto inne rozwiązanie.

Podstawową ideą jest wykorzystanie wbudowanych „paczek” i „rozpakowywania” Alicji. „Paczka”, lub Z, bierze dwie liczby całkowite odwzorowuje je biotycznie na jedną liczbę całkowitą. „Rozpakuj” lub Yodwraca ten bijection i zamienia jedną liczbę całkowitą na dwie. Zwykle można tego użyć do przechowywania listy lub drzewa liczb całkowitych w jednej (dużej) liczbie całkowitej i odzyskania poszczególnych wartości później. Jednak w tym przypadku możemy użyć funkcji w odwrotnej kolejności, aby natura bijection działała dla nas.

Rozpakowanie jednej liczby całkowitej na dwie liczby całkowite składa się zasadniczo z trzech kroków:

  1. Mapa ℤ → ℕ (w tym zero) z prostym „składaniem”. Oznacza to, że odwzoruj ujemne liczby całkowite na nieparzyste natury i nieujemne liczby całkowite na parzyste natury.
  2. Mapa ℕ → ℕ 2 , za pomocą funkcji parowania Cantor . Oznacza to, że naturale są zapisywane wzdłuż przekątnych nieskończonej siatki, a my zwracamy indeksy:

       ...
    3  9 ...
    2  5 8 ...
    1  2 4 7 ...
    0  0 1 3 6 ...
    
       0 1 2 3
    

    Np. Zostanie 8zmapowany na parę (1, 2).

  3. Mapa 2 → ℤ 2 , używając odwrotności kroku 1 na każdej liczbie całkowitej osobno. Oznacza to, że nieparzyste naturale są mapowane na ujemne liczby całkowite, a nawet naturale są mapowane na nieujemne liczby całkowite.

Aby spakować dwie liczby całkowite w jedną, po prostu odwracamy każdy z tych kroków.

Teraz widzimy, że struktura funkcji parowania Cantora wygodnie koduje potrzebny nam trójkąt (chociaż wartości są oddzielone od siebie). Aby odwrócić te przekątne, wszystko co trzeba zrobić to zamienić x i y współrzędne do sieci.

Niestety, ponieważ wszystkie trzy powyższe kroki są połączone w jeden wbudowany Y(lub Z), musimy sami cofnąć mapowania ℤ → ℕ lub ℕ → ℤ . Robiąc to, możemy jednak zaoszczędzić kilka bajtów, używając bezpośrednio mapowań + → ℤ lub ℤ → ℕ + , aby zająć się błędem off-by-one w tabeli. Oto cały algorytm:

  1. Mapa + → ℤ pomocą (n / 2) * (-1) n-1 . To mapowanie jest wybrane tak, że anuluje niejawne mapowanie ℤ → ℕ podczas rozpakowywania, z tym wyjątkiem, że przesuwa wartość w dół o 1.
  2. Rozpakuj wynik na dwie liczby całkowite.
  3. Zamień je.
  4. Ponownie spakuj zamienione wartości w jedną liczbę całkowitą.
  5. Mapa ℤ → ℕ + za pomocą | 2n | + (n≥0) . Ponownie, to mapowanie jest wybrane tak, że anuluje niejawne mapowanie ℕ → ℤ podczas pakowania, z tym wyjątkiem, że przesuwa wartość w górę o 1.

W ten sposób możemy spojrzeć na program:

/o
\i@/...

Jest to po prostu struktura liniowych programów arytmetycznych z wejściowymi i wyjściowymi liczbami całkowitymi.

.    Duplicate the input.
2:   Halve it.
e    Push -1.
2,   Pull up the other copy of the input.
t    Decrement.
E    Raise -1 to this power.
*    Multiply. We've now computed (n/2) * (-1)^(n-1).
Y    Unpack.
~    Swap.
Z    Pack.
.H   Duplicate the result and take its absolute value.
2*   Double.
~    Swap with other copy.
.C   Compute k-choose-k. That's 1 for k ≥ 0 and 0 for k < 0.
+    Add. We've now computed |2n| + (n≥0).



4

Oktawa , 71 68 bajtów

3 bajty zapisane dzięki Conorowi O'Brienowi .

x=triu(ones(n=input('')));x(~~x)=1:nnz(x);disp(nonzeros(flip(x))(n))

Nie działa to w przypadku dużych danych wejściowych z powodu ograniczeń pamięci.

Wypróbuj online!

Wyjaśnienie

Rozważ wejście n = 4. Kod najpierw tworzy macierz

 1     1     1     1
 0     1     1     1
 0     0     1     1
 0     0     0     1

Następnie zastępuje niezerowe wpisy w kolejności kolumny-dur (w dół, a następnie w poprzek) przez 1, 2, 3...:

 1     2     4     7
 0     3     5     8
 0     0     6     9
 0     0     0    10

Następnie odwraca matrycę w pionie:

 0     0     0    10
 0     0     6     9
 0     3     5     8
 1     2     4     7

Wreszcie, przyjmuje n-tą niezerową wartość w porządku głównym kolumny, która w tym przypadku jest 6.


1
@ rahnema1 To ejest genialne! Zdecydowanie powinieneś opublikować to jako odpowiedź, wraz z innymi bardzo dobrymi sugestiami. Co do tego ans =, nigdy nie jestem pewien, czy to ważne czy nie
Luis Mendo

4

Haskell , 31 bajtów

r=round
f n=r(sqrt$2*n)^2-r n+1

Wypróbuj online!

Ta odpowiedź używa tylko formuły. Jest to najmniej interesująca odpowiedź tutaj, ale zdarza się również, że jest najbardziej golfowa.

Haskell , 38 36 34 bajtów

x!y|x<=y=1-x|v<-y+1=v+(x-y)!v
(!0)

Wypróbuj online!

(!0) to funkcja bez punktów, o którą nam chodzi.

Wyjaśnienie

Zacznę od stwierdzenia, że ​​jestem bardzo zadowolony z tej odpowiedzi.

Podstawową ideą jest to, że jeśli usuniemy największą trójkątną liczbę mniejszą niż nasze dane wejściowe, możemy ją odwrócić i dodać z powrotem trójkątną liczbę. Zdefiniujemy więc operatora !, !przyjmujemy nasze zwykłe dane wejściowe x, ale także dodatkową liczbę y. yśledzi rozmiar rosnącej liczby trójkątnej. Jeśli x>ychcemy powtórzyć, zmniejszamy xsię yi zwiększamy yo jeden. Obliczamy (x-y)!(y+1)i dodajemy y+1do tego. Jeśli x<=yosiągnęliśmy nasz przypadek podstawowy, aby odwrócić xumieszczenie w rzędzie trójkąta, zwracamy 1-x.

Haskell , 54 bajty

f x|u<-div(x^2-x)2=[u+x,u+x-1..u+1]
(!!)$0:(>>=)[1..]f

Wypróbuj online!

(!!)$0:(>>=)[1..]f jest funkcją bez punktów

Wyjaśnienie

Pierwszą rzeczą, na której nam zależy f, fjest funkcja, która przyjmuje xi zwraca xw odwrotnym rzędzie th trójkąta. Robi to, najpierw obliczając x-1numer trójkątny i przypisując go u. u<-div(x^2-x)2. Następnie zwracamy listę [u+x,u+x-1..u+1]. u+xjest xth trójkątną liczbą i pierwszą liczbą w rzędzie, u+x-1jest o jeden mniejszą liczbą, a druga liczba w rzędzie u+1jest o jeden większa niż ostatnia liczba trójkątna, a zatem ostatnia liczba w rzędzie.

Kiedy już mamy, ftworzymy listę (>>=)[1..]f, która jest spłaszczeniem trójkąta. Z przodu dodajemy zero, 0:dzięki czemu nasze odpowiedzi nie zostaną przesunięte o jeden, i dostarczymy je do naszej funkcji indeksowania (!!).

Haskell , 56 bajtów

f 0=[0]
f x|u<-f(x-1)!!0=[u+x,u+x-1..u+1]
(!!)$[0..]>>=f

Wypróbuj online!

Ten jest o 2 bajty dłuższy, ale moim zdaniem nieco bardziej elegancki.


3

C (gcc) , 48 bajtów

k,j,l;f(n){for(k=j=0;k<n;)l=k,k+=++j;n=1+k-n+l;}

Wypróbuj online!

Prawdopodobnie nieoptymalny, ale jestem z tego zadowolony. Wykorzystuje fakt, że

NTF N = T N + A057944 ( N ) - N + 1

(To znaczy, jeśli poprawnie zapisałem formułę.)


Nie nazywasz return, ale używana jest wartość return. To jest niezdefiniowane zachowanie.
2501

@ 2501 Dopóki program działa, jest dozwolony. Pisanie do pierwszego argumentu funkcji jest równoznaczne ze zwróceniem wartości.
Conor O'Brien

Pisanie do pierwszego argumentu funkcji jest równoznaczne ze zwróceniem wartości. Nie ma czegoś takiego w języku C. Norma nawet wyraźnie mówi, że używanie zwróconej wartości z funkcji, która nie zwraca, jest zachowaniem niezdefiniowanym.
2501

1
@ 2501 Wygląda na to, że mylisz środowisko C (gcc) ze specyfikacją C. Tak, język C / spec nazywa go niezdefiniowanym, ale jest zaimplementowany jako taki. Kiedy mówię „ekwiwalent”, zdecydowanie odnoszę się do implementacji C przez gcc i większość innych kompilatorów. Na PPCG nie piszemy „idealnego” kodu - wiele kodów jest sprzecznych ze specyfikacją ze względu na grę w golfa. Jak powiedziałem, dopóki działa, jest to prawidłowa odpowiedź.
Conor O'Brien

@ 2501 Zachęcam do przeczytania niektórych artykułów na stronie meta, szczególnie tej .
Conor O'Brien

2

05AB1E , 30 bajtów

U1V[YLO>X›iYLOX-UY<LO>X+,q}Y>V

Wypróbuj online!


Już miałem powiedzieć „Co? Odpowiedź 05AB1E bez Unicode?” ale potem jedna postać spoza ASCII rujnuje go ...: P Ale fajna pierwsza odpowiedź, witaj w Programowaniu łamigłówek i Code Golf!
clismique 28.04.17

@ Qwerp-Derp Dziękuję bardzo! Właśnie zacząłem uczyć się tego języka, więc nie jestem zaskoczony, że moja odpowiedź była tak zła.
Eduardo Hoefel

2

Łuska , 6 bajtów

!ṁ↔´CN

Wypróbuj online!

Wyjaśnienie

!ṁ↔´CN  -- implicit input N, for example: 4
   ´ N  -- duplicate the natural numbers:
           [1,2,3,…] [1,2,3,…]
    C   -- cut the second argument into sizes of the first:
           [[1],[2,3],[4,5,6],[7,8,9,10],…]
 ṁ↔     -- map reverse and flatten:
           [1,3,2,6,5,4,10,9,8,7,15,…
!       -- index into that list:
           6

2

tinylisp , 78 bajtów

(d _(q((R N T)(i(l T N)(_(a R 1)N(a T R))(a 2(a T(s T(a N R
(d f(q((N)(_ 2 N 1

Definiuje funkcję, fktóra wykonuje mapowanie. Wypróbuj online!

Bez golfa

Znajdujemy najmniejszą liczbę trójkątną, która jest większa lub równa liczbie wejściowej, a także wiersz, w którym znajduje się nasza liczba. Na ich podstawie możemy obliczyć odwróconą wersję liczby.

  • Jeśli bieżąca liczba trójkątna jest mniejsza niż N, przejdź do następnego rzędu trójkąta. (Traktujemy górny wiersz jak wiersz 2, aby matematyka była prostsza).
  • W przeciwnym razie odwróconą wersją N jest (TN) + (TR) +2.

Główna funkcja flippo prostu wywołuje funkcję pomocnika, _flipzaczynając od górnego rzędu.

(load library)

(def _flip
 (lambda (Num Row Triangular)
  (if (less? Triangular Num)
   (_flip Num (inc Row) (+ Triangular Row))
   (+ 2
    (- Triangular Num)
    (- Triangular Row))))))

(def flip
 (lambda (Num) (_flip Num 2 1)))

1

05AB1E , 9 bajtów

·LD£í˜¹<è

Wypróbuj online!

Wyjaśnienie

·L          # push range [1 ... 2n]
  D         # duplicate
   £        # split the first list into pieces with size dependent on the second list
    í       # reverse each sublist
     ˜      # flatten
      ¹<è   # get the element at index <input>-1

Spłaszczanie tablic niestety nie radzi sobie dobrze z większymi listami.
Kosztem 1 bajtu moglibyśmy zrobić · t2z + ïn¹-> przy użyciu wzoru matematycznego floor(sqrt(2*n)+1/2)^2 - n + 1znalezionego w OEIS .


1

Partia, 70 bajtów

@set/ai=%2+1,j=%3+i
@if %j% lss %1 %0 %1 %i% %j%
@cmd/cset/ai*i+1-%1

Korzysta z pętli, aby znaleźć indeks liczby trójkątnej co najmniej tak dużej jak n.




0

APL (Dyalog), 27 bajtów

Mam dwa rozwiązania w tej samej liczbie bajtów.

Pociąg:

⊢⊃⊃∘(,/{⌽(+/⍳⍵-1)+⍳⍵}¨∘⍳)

Wypróbuj online!

I dfn:

{⍵⊃⊃((⍳⍵),.{1+⍵-⍳⍺}+\⍳⍵)}

Wypróbuj online!

Oba te rozwiązania najpierw tworzą odwrócony trójkąt, a następnie wyodrębniają element o indeksie podanym przez argument (na podstawie 1).


0

J, 25 bajtów

3 :'>:y-~*:>.-:<:%:>:8*y'

Jako wyjaśnienie zastanów się f(n) = n(n+1)/2. f(r), biorąc pod uwagę wiersz r, zwraca lewą liczbę rtrzeciego rzędu lustrzanego trójkąta. Teraz zastanów się g(n) = ceiling[f⁻¹(n)]. g(i), biorąc pod uwagę indeks i, zwraca wiersz, w którym znaleziono indeks i. Następnie f(g(n))zwraca lewą liczbę wiersza, w którym znaleziono indeks n. Tak więc h(n) = f(g(n)) - (n - f(g(n)-1)) + 1jest odpowiedź na powyższy problem.

Upraszczamy, rozumiemy h(n) = [g(n)]² - n + 1 = ceiling[(-1 + sqrt(1 + 8n))/2]² - n + 1.

Z wyglądu formuły @ Arnauld wynika, że:

ceiling[(-1 + sqrt(1 + 8n))/2] = floor[1/2 + sqrt(2n)].


Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.