Podziękowania dla @ Agawa001 za wymyślenie tego pytania.

Wyjaśnienie

Mój nowy „keybore” ma tylko 2 przyciski, a mianowicie +i -.

Numer w pamięci zaczyna się od 0.

Każde kolejne naciśnięcie +lub -zwiększy / zmniejszy pamięć dokładnie tyle razy, ile razy zostało naciśnięte kolejno.

Dlatego, jeśli naciśniesz +4 razy, za pierwszym razem dodaje 1, za drugim razem dodaje 2, za trzecim razem dodaje 3, po raz czwarty dodaje 4, dając ci 10(dziesięć).

Teraz, jeśli naciśniesz -3 razy, za pierwszym razem odejmie 1, drugi raz 2, trzeci raz 3, pozostawiając ci 4(cztery).

TL; DR

Biorąc pod uwagę ciąg + i -, dziel go przy każdej zmianie charakteru. Następnie każdy wynikowy ciąg m +symboli dodaje m-ty numer trójkąta, a każdy ciąg n -symboli odejmuje n-ty numer trójkąta.

Walk-through

Teraz, jeśli nadal nie rozumiesz, pokażę ci, jak +++--+--tworzy 1.

Program   | Counter | Memory
----------------------------
          |  0      | 0
+         | +1      | 1
++        | +2      | 3
+++       | +3      | 6
+++-      | -1      | 5
+++--     | -2      | 3
+++--+    | +1      | 4
+++--+-   | -1      | 3
+++--+--  | -2      | 1

Zadanie

• Jako dane wejściowe weźmiesz dodatnią liczbę całkowitą, albo jako argument funkcjonalny, albo ze STDIN.
• Następnie wydrukujesz / wydrukujesz minimalną liczbę naciśnięć klawiszy potrzebnych do utworzenia tej liczby, korzystając z powyższej metody.

Przypadki testowe

Ponieważ przestawienie sekwencji +lub -daje ten sam numer, dla każdej takiej grupy wymieniona jest tylko najwcześniejsza sekwencja leksykograficzna.

Input | Output | Possible corresponding sequences
-------------------------------------------------
    4 |      5 | -+++-
    6 |      3 | +++
    9 |      5 | ++++-
   11 |      7 | +++-+++
   12 |      7 | +++++--, ++++-++
   19 |      8 | -++++++-
   39 |     12 | +++++++++---
   40 |     13 | +++++++++---+, ++++++++-+++-
   45 |      9 | +++++++++
   97 |     20 | ++++++++++++++--+---, +++++++++++++-++++--, ++++++++++++-++++++-
  361 |     34 | ++++++++++++++++++++++++++-+++-+++

Dodatkowe zasoby

• Dowód, że można wykonać dowolną liczbę : w zasadzie powtarzając ++-, można uzyskać dowolną liczbę parzystą. Aby uzyskać liczby nieparzyste, po prostu umieść +na końcu.
• Kolejny ogólny sposób na uzyskanie dowolnej liczby. Na przykład, aby wygenerować 50, można nacisnąć +50 razy, a następnie nacisnąć -49 razy.
• Rozwiązanie pierwszych 50 liczb .
• Obowiązkowe JSFiddle .

Punktacja

To jest golf golfowy . Najkrótsze rozwiązanie w bajtach wygrywa.

Python 2, 119 bajtów

def g(n,i=0,s=''):
 c=x=t=0
 for d in s:C=int(d)*2-1;t=(c==C)*t+1;c=C;x+=c*t
 return(x==n)*len(s)or g(n,i+1,bin(i)[3:])

Bardzo wolne podejście z użyciem siły brutalnej. Trzecia linia oblicza wynik ciągu x; pozostałe linie zapętlają wszystkie możliwe ciągi binarne, dopóki nie zostanie znaleziony taki, którego wynik jest równy argumentowi.

@Leaky zapisał trzy bajty!

Pyth, 25 bajtów

ffqyQ.as-Mc*RhdY2{s.pM./T

Wypróbuj online.

Jest to wyjątkowo nieefektywne i zabraknie pamięci dla f(n)≥ 11. Oblicza f(22)= 10 w około 10 sekund na moim laptopie.

Wyjaśnienie

• Począwszy od 1, zapętlaj liczby T. ( f)
  • Wygeneruj wszystkie partycje T. ( ./T)
  • Wygeneruj wszystkie kombinacje tych. ( .pM)
  • Spłaszcz listę. ( s)
  • Ujednolic listę. ( {) Ten krok można usunąć, ale znacznie przyspiesza kod.
  • Filtruj wynikowe permutacje partycji: ( f)
    • Pomnóż każdą liczbę dpartycji ( *R) przez siebie plus jedną ( hd). To daje podwójną liczbę, aby dodać / odjąć do wyniku.
    • Posiekaj listę na części o długości 2. ( c… 2)
    • Odejmij dowolną drugą liczbę w tych częściach od drugiej liczby. ( -M)
    • Zsumuj wyniki. Daje to podwójną liczbę wynikową, jeśli permutacja partycji była interpretowana jako liczba dodatków, a następnie odejmowań itp.
    • Weź wartość bezwzględną. ( .a) Jeśli wynik był ujemny, zamiana dodawania i odejmowania daje wynik dodatni.
    • Sprawdź, czy wynik jest równy dwukrotności wartości wejściowej. ( qyQ) W takim przypadku permutacja partycji jest poprawna, zwróć ją.
  • Jeśli filtr zwrócił jakiekolwiek wyniki, istnieje rozwiązanie długości T. Wróć i wydrukuj T.

MATL , 43 29 bajtów

E:"@TFEqZ^!"@Y'tQ**s]vGE=a?@.

Jest to nieefektywne pod względem pamięci i czasu. Kompilator online może obsługiwać 45tylko dane wejściowe .

Wypróbuj online!

Oto zmodyfikowana wersja ze wszystkimi przypadkami testowymi do 40(zajmuje to prawie minutę w kompilatorze online).

Wyjaśnienie

Testuje to wszystkie możliwe sekwencje naciskania klawiszy dla każdej długości, w kolejności rosnącej długości, aż do znalezienia prawidłowej sekwencji.

E:       % Range [1 2 ... 2*N] where N is implicit input. The required sequence length is
         % less than 2*N, so this is enough
"        % For each
  @      %   Push current value: length of sequence
  TFEq   %   Push array [1 -1]
  Z^     %   Cartesian power. Gives all possible sequences of 1, -1 of that length
  !      %   Transpose. Each sequence is now a row
  "      %   For each sequence
    @    %     Push current sequence
    Y'   %     Run-length decoding: Pushes an array of values 1 and -1, and then an
         %     array of run-lengths
    tQ*  %     Duplicate, add 1, multiply. Gives twice the triangular number for each run
    *    %     Multiply element-wise by 1 or -1 to produce correct sign
    s    %     Sum of array. This is the number produced by the current sequence
  ]      %   End for
  v      %   Concatenate all numbers into an array
  GE=a   %   True if any of those numbers equals twice the input
  ?      %   If so
    @    %     Push current sequence length. This is the final result
    .    %     Break loop
         %   End if
         % End for
         % Implicit display

Python, 105 100 bajtów

Korzysta z nieefektywnego wyszukiwania szerokości.

def k(n):
 m=t=l=0;h=[]
 while m-n:o=1-2*(t>0);(m,t,l),*h=h+[(m+t-o,t-o,l+1),(m+o,o,l+1)]
 return l

• h to lista używana jako kolejka
• m to wartość sekwencji na początku listy
• t jest ostatnim numerem dodanym do m
• l to długość wygenerowanej sekwencji m
• o wynosi +/- 1, znak jest przeciwny do znaku t

Edycja: Dziurawa Zakonnica ogoliła pięć bajtów.