Twoim zadaniem jest zbudowanie liczby naturalnej przy użyciu jak najmniejszej liczby jedynek i tylko operatorów +lub -. Na przykład liczbę siedem można zapisać 1+1+1+1+1+1+1=7, ale można ją również zapisać jako 11-1-1-1-1=7. Pierwszy korzysta z 7nich, a drugi tylko 6. Twoim zadaniem jest, aby zwrócić minimalną liczbę tych, które mogą być wykorzystane podanych wejście jakiejś liczby naturalnej, n.

To jest kod golfowy, więc wygrywa najkrótszy prawidłowy kod w bajtach.

Przypadki testowe

Dane wejściowe => Dane wyjściowe

0 => 2 (since 1-1=0)
7 => 6
121 => 6
72 => 15
1000 => 7
2016 => 21

JavaScript (ES6), 127 126 87 bajtów

f=(n,z=2,m=n*9+'',r=m.replace(/./g,1))=>n?m.length+(m<'55'?f(n- --r/10,0)-1:f(r-n,0)):z

Input: <input type="number" oninput="result.textContent=f(this.value)"> Result: <span id="result"></span>

Powinien działać do około 10 ^{14 15,} w którym momencie zaczynasz napotykać limity liczb całkowitych JavaScript. Wyjaśnienie:

f=(                             Recursive function
 n,                             Parameter
 z=2,                           Zero workaround
 m=n*9+'',                      Magic
 r=m.replace(/./g,1)            Find repunit not less than than n
)=>n?                           Nothing to do if n is zero
 m.length+                      Assume subtracting from repunit
 (m<'55'?                       Should we subtract from repunit?
  f(n- --r/10,0)                No, so subtract previous repuint
   -1:                          Which is one 1 shorter
  f(r-n,0)):                    Subtract from repunit
 z                              Return special case if n is zero

To używa n*9magii dwa razy; po pierwsze, daje mi długość następnego powtórzenia, po drugie, jeśli pierwsze dwie cyfry n*9to 55lub więcej, wówczas musimy odjąć nod następnego powtórzenia, w przeciwnym razie musimy odjąć poprzednie powtórzenie (które jest obliczane przez odjęcie 1 i dzielenie przez 10). Powinno to działać do 10 ¹⁵ .

Pyth, 19 16 bajtów

ffqQvs+R1Y^c3"+-

Zestaw testowy

Algorytm siły brutalnej. Niezbędne łańcuchy są generowane przez pobranie wszystkich list, których elementy mają ['+', '-', '']długość równą liczbie testowanych 1, dodanie 1 do każdego i połączenie w pojedynczy łańcuch. Te ciągi są następnie oceniane i porównywane z danymi wejściowymi. Jest to powtarzane do momentu znalezienia pomyślnego ciągu.

Niektóre ciągi z wiodącym +lub -testowane, ale to nie jest problem. Byłoby tak, gdyby dane wejściowe były ujemne.

Może osiągnąć długość 9, zanim stanie się zbyt wolny.

Wyjaśnienie:

ffqQvs+R1Y^c3"+-
ffqQvs+R1Y^c3"+-"T    Implicit variable introduction
                      Q = eval(input())
f                     Starting with T = 1 and counting upwards, repeat until true.
                      The value of T where the result is first true is output.
           c3"+-"     Chop "+-" into thirds, giving ['+', '-', '']
          ^      T    Form every list with those elements of length T.
 f                    Filter over those lists, lambda var Y.
      +R1Y            Append a 1 to each element of the list.
     s                Concatenate.
    v                 Eval.
  qQ                  Compare for equality with the input.
                      The inner filter will let through the successful cases.
                      The outer filter will stop when there is a successful case.

JavaScript (ES6), 92 bajty

f=(n,i=3)=>eval([...s=i.toString(3)].map(d=>"-+"[d]||"").join`1`+".0")-n?f(n,i+1):s.length-1

n = <input type="number" oninput="R.textContent=f(this.value)" /><pre id="R"></pre>

Wyjaśnienie

Funkcja rekurencyjna. Generuje to wszystkie możliwe kombinacje 1s oddzielone albo +, -albo niczym. Robi to, zwiększając liczbę podstawową-3, przekształcając ją w tablicę cyfr, konwertując każdą cyfrę 0na -, 1do +i 2na pusty ciąg znaków, a następnie łącząc je razem z 1s. Otrzymany ciąg jest evald jako instrukcja JavaScript, która zwraca wynik równania.

Ponieważ operatory są połączone za pomocą 1s pomiędzy (jak +1+1+1+), istnieją length - 1 1s. Pierwszy operator jest ignorowany (ponieważ +1= 1, <nothing>1= 1i jest to liczba tak nigdy nie będzie wiodącym 0na -) i ostatnim operatorem jest również ignorowane (przez dodanie .0do równania).

Wyższa wersja wyjściowa, 96 bajtów

Druga wersja nie może zwrócić wyników wyższych niż ~ 10 z powodu limitu stosu wywołań rekurencyjnych. Ta wersja używa pętli for zamiast rekurencji, więc może zwrócić dane wyjściowe do ~ 33. Ilość wymaganego czasu rośnie wykładniczo, więc nie polecam go testować.

n=>eval('for(a=3;eval([...s=a.toString(3)].map(d=>"-+"[d]||"").join`1`+".0")-n;)a++;s.length-1')