Minimizar esos unos [cerrado]

12

Su tarea es construir un número natural utilizando el menor número de unidades y solo los operadores +o -. Por ejemplo, el número siete se puede escribir 1+1+1+1+1+1+1=7, pero también se puede escribir como 11-1-1-1-1=7. El primero usa 7unos, mientras que el último solo usa 6. Su tarea es devolver el número mínimo de los que pueden ser utilizados dan la entrada de algún número natural, n.

Este es el código golf, por lo que gana el código válido más corto en bytes.

Casos de prueba

Entrada => Salida

0 => 2 (since 1-1=0)
7 => 6
121 => 6
72 => 15
1000 => 7
2016 => 21
codeputer
fuente
Bonito primer desafío. Sugeriría incluir más casos de prueba. ¿Es "SALIDAS VÁLIDAS" un error, dado que hay una sola salida? Además, ¿es 0 una entrada válida y, en caso afirmativo, qué salida debería?
xnor
Este es un desafío interesante. Es posible que desee agregar una explicación para las salidas, cambiar VALID OUTPUTS. Es su elección, pero en general a las personas les gusta negrita o cursiva en lugar de LETRAS MAYÚSCULAS (hacen que parezca gritar en lugar de énfasis). Negrita es **bold text**y cursiva es *italics text*. También puede usar ### Textpara texto en negrita. De todos modos, ¡bienvenido a PPCG!
NoOneIsHere
Debe hacer una tabla legible por computadora o una lista de casos de prueba en los que las personas puedan ejecutar su código. Mira este consejo .
xnor
66
Estoy votando para cerrar esta pregunta porque esta es una duplicación del desafío de golf actual (¡activo!) En codefights.com/challenges . Incluso si el OP también es el autor del desafío original en codefights (que dudo), la pregunta debe cerrarse hasta que el desafío en codefights ya no esté activo.
Jakube
1
@Jakube, el enlace directo podría haber sido útil, pero estoy de acuerdo. Voy a votar para cerrar.
NoOneIsHere

Respuestas:

3

JavaScript (ES6), 127 126 87 bytes

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>

Debería funcionar hasta aproximadamente 10 14 15, momento en el que comenzará a encontrarse con los límites enteros de JavaScript. Explicación:

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

Esto usa la n*9magia dos veces; en primer lugar, me da la longitud de la próxima repunidad, en segundo lugar, si los dos primeros dígitos de n*9son 55o más, entonces tenemos que restar nde la próxima repunidad, de lo contrario, tenemos que restar la repunidad anterior (que se calcula restando 1 y dividido por 10). Esto debería funcionar hasta 10 15 .

Neil
fuente
2

Pyth, 19 16 bytes

ffqQvs+R1Y^c3"+-

Banco de pruebas

Algoritmo de fuerza bruta. Las cadenas necesarias se generan tomando todas las listas cuyos elementos tienen una ['+', '-', '']longitud igual al número de 1s que se están probando, agregando un 1 a cada uno y concatenando a una sola cadena. Estas cadenas se evalúan y comparan con la entrada. Esto se repite hasta que se encuentra una cadena exitosa.

Algunas cadenas con un líder +o -se prueban, pero esto no es un problema. Sin embargo, sería si la entrada fuera negativa.

Puede correr hasta la longitud 9 antes de que sea demasiado lento.

Explicación:

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
fuente
2

JavaScript (ES6), 92 bytes

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>

Explicación

Función recursiva. Esto genera todas las posibles permutaciones de 1s separados por cualquiera +, -o nada. Lo hace incrementando un número de base 3, convirtiéndolo en una matriz de dígitos, convirtiendo cada dígito 0a -, 1en +y 2a una cadena vacía, luego uniéndolos con 1s. La cadena resultante es evald como una declaración de JavaScript que devuelve el resultado de la ecuación.

Debido a que los operadores están unidos con 1s en el medio (como +1+1+1+), hay length - 1 1s. El primer operador es ignorado (porque +1= 1, <nothing>1= 1y es un número de modo que nunca habrá un líder 0para -) y el operador final también se ignora (añadiendo .0a la ecuación).

Versión de salida superior, 96 bytes

La otra versión no puede devolver salidas superiores a ~ 10 debido al límite de la pila de llamadas de recursión. Esta versión utiliza un bucle for en lugar de recursividad, por lo que puede devolver salidas de hasta ~ 33. Sin embargo, la cantidad de tiempo requerida aumenta exponencialmente, por lo que no recomiendo probarlo.

n=>eval('for(a=3;eval([...s=a.toString(3)].map(d=>"-+"[d]||"").join`1`+".0")-n;)a++;s.length-1')
usuario81655
fuente
Esto suena demasiado complicado, me gusta.
Bálint