Minimiere diese [geschlossen]

12

Ihre Aufgabe ist es, eine natürliche Zahl mit der geringsten Anzahl von Einsen und nur den Operatoren +oder zu erstellen -. Zum Beispiel kann die Zahl Sieben geschrieben werden 1+1+1+1+1+1+1=7, aber es kann auch als geschrieben werden 11-1-1-1-1=7. Der erste verwendet 7diejenigen, während der letztere nur verwendet 6. Ihre Aufgabe ist es, die Mindestanzahl von Einsern zurückzugeben, die bei Eingabe einer natürlichen Zahl verwendet werden können n.

Dies ist Codegolf, daher gewinnt der kürzeste gültige Code in Bytes.

Testfälle

Eingabe => Ausgabe

0 => 2 (since 1-1=0)
7 => 6
121 => 6
72 => 15
1000 => 7
2016 => 21
Codecomputer
quelle
Schöne erste Herausforderung. Ich würde vorschlagen, mehr Testfälle einzuschließen. Ist "VALID OUTPUTS" ein Fehler, da es nur einen Ausgang gibt? Ist 0 auch eine gültige Eingabe, und wenn ja, welche sollte ausgegeben werden?
xnor
Dies ist eine interessante Herausforderung. Sie können eine Erklärung für die Ausgänge hinzufügen, ändern VALID OUTPUTS. Sie haben die Wahl, aber im Allgemeinen mögen die Leute Fettdruck oder Kursivdruck anstelle von GROSSBUCHSTABEN (sie lassen es so aussehen, als würden Sie schreien, anstatt es hervorzuheben). Fett **bold text**und kursiv *italics text*. Sie könnten auch ### Textfür fetteren Text verwenden. Wie auch immer, willkommen bei PPCG!
NoOneIsHere
Sie sollten eine computerlesbare Tabelle oder Liste von Testfällen erstellen, auf denen die Benutzer ihren Code ausführen können. Siehe diesen Tipp .
xnor
6
Ich stimme dafür, diese Frage zu schließen, da es sich bei dieser Frage um ein Duplikat der aktuellen (aktiven !!) Golfherausforderung unter codefights.com/challenges handelt . Auch wenn das OP auch der Autor der ursprünglichen Herausforderung für Codefights ist (was ich bezweifle), sollte die Frage geschlossen werden, bis die Herausforderung für Codefights nicht mehr aktiv ist.
Jakube
1
@ Jakube der direkte Link hätte hilfreich sein können, aber ich stimme zu. Ich werde stimmen, um zu schließen.
NoOneIsHere

Antworten:

3

JavaScript (ES6), 127 126 87 Byte

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>

Sollte bis ungefähr 10 14 15 funktionieren. Ab diesem Punkt stoßen Sie auf die Ganzzahlgrenzen von JavaScript. Erläuterung:

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

Dies nutzt die n*9Magie zweimal; Erstens, es gibt mir die Länge der nächsten Repunit - Zahl, zweitens, wenn die ersten beiden Ziffern n*9sind 55oder höher, dann müssen wir subtrahieren nvon der nächsten Repunit - Zahl, sonst müssen wir die vorherige Repunit - Zahl (die durch Subtrahieren von 1 berechnet wird , subtrahieren und durch 10 teilen). Dies sollte bis zu 10 15 funktionieren .

Neil
quelle
2

Pyth, 19 16 Bytes

ffqQvs+R1Y^c3"+-

Testsuite

Brute-Force-Algorithmus. Die erforderlichen Zeichenfolgen werden generiert, indem alle Listen, deren Elemente ['+', '-', '']gleich der Anzahl der zu testenden Einsen lang sind, mit einer 1 versehen und zu einer einzelnen Zeichenfolge verkettet werden. Diese Zeichenfolgen werden dann ausgewertet und mit der Eingabe verglichen. Dies wird wiederholt, bis eine erfolgreiche Zeichenfolge gefunden wurde.

Einige Zeichenfolgen mit einem führenden +oder -werden getestet, dies ist jedoch kein Problem. Es wäre allerdings, wenn die Eingabe negativ wäre.

Es kann bis zu einer Länge von 9 laufen, bevor es zu langsam wird.

Erläuterung:

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.
isaacg
quelle
2

JavaScript (ES6), 92 Byte

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>

Erläuterung

Rekursive Funktion. Dies erzeugt alle möglichen Permutationen von 1s, die entweder +durch -oder durch nichts getrennt sind. Dazu wird eine Zahl zur Basis 3 inkrementiert, in ein Array von Ziffern umgewandelt, jede Ziffer 0in -, 1in +und 2in eine leere Zeichenfolge konvertiert und anschließend mit 1s verbunden. Die resultierende Zeichenfolge ist evald als JavaScript-Anweisung, die das Ergebnis der Gleichung zurückgibt.

Da die Operatoren mit 1s in between (like +1+1+1+) verbunden sind, gibt es length - 1 1s. Der erste Operator wird ignoriert (da +1= 1, <nothing>1= 1und es ist eine Zahl , so wird es nie ein führender sein 0für -) und der letzte Operator wird auch ignoriert (durch Anhängen .0der Gleichung).

Höhere Ausgabeversion, 96 Bytes

Die andere Version kann aufgrund des Rekursions-Call-Stack-Limits keine höheren Ausgaben als ~ 10 zurückgeben. Diese Version verwendet eine for-Schleife anstelle einer Rekursion, sodass Ausgaben bis zu ~ 33 zurückgegeben werden können. Der Zeitaufwand steigt jedoch exponentiell an, weshalb ich das Testen nicht empfehle.

n=>eval('for(a=3;eval([...s=a.toString(3)].map(d=>"-+"[d]||"").join`1`+".0")-n;)a++;s.length-1')
user81655
quelle
Das klingt zu kompliziert, ich mag es.
Bálint