Citando esta pregunta en SO (¡alerta de spoiler!):
Esta pregunta ha sido formulada en una entrevista de Oracle.
¿Cómo dividiría un número por 3 sin usar operadores *, /, +, -,%?
El número puede estar firmado o sin firmar.
La tarea es solucionable, pero vea si puede escribir el código más corto.
Reglas:
- Realice la división entera requerida (
/3
) - No utilice los operadores no basados en texto
*
,/
,+
,-
, o%
(o sus equivalentes, tales como__div__
oadd()
). Esto también se aplica a operadores de incremento y decremento, comoi++
oi--
. El uso de operadores para la concatenación y formateo de cadenas está bien. El uso de estos caracteres para diferentes operadores, como el-
operador unario para números negativos, o*
para representar un puntero en C también está bien. - El valor de entrada puede ser arbitrariamente grande (lo que sea que su sistema pueda manejar), tanto positivo como negativo
- La entrada puede estar en STDIN o ARGV o ingresada de cualquier otra manera
- Crea el código más corto que puedas para hacer lo anterior
Respuestas:
J,
45 4410 caracteres".,&'r3'":
Funciona con negativos:
":
- formatear como texto,&'r3'
- agregarr3
hasta el final".
- ejecutar la cadena, por ejemplo15r3
fuente
3 3 3 #: 9
. Parece que necesita saber cuánto durará su número ternario._3]\i.
También es un posible punto de partida para algo, pero no sé si sería más corto que su solución aquí. El problema con#_3]\i.
su estado actual es que siempre se redondea hacia arriba en lugar de hacia abajo.##~3=_3#\i.
para 11 personajes?##~0 0 1$~
.3#.}:(#:~$&3)
pero aún es más largo y no soluciona el problema del número negativo.^:
o de la Agenda@.
para unaif
oif...else
reemplazo. En este caso, puede usar@.
dos verbos conectados con un carácter '' '(un gerundio en J-speak) para seleccionar uno u otro en función de una condición.C, 167503724710
Aquí está mi solución al problema. Admito que es poco probable que gane una competencia de golf de código estricto, pero no utiliza ningún truco para llamar indirectamente a la funcionalidad de división incorporada, está escrito en C portátil (como se preguntó en la pregunta original de desbordamiento de pila), funciona perfectamente para números negativos, y el código es excepcionalmente claro y explícito.
Mi programa es la salida del siguiente script:
Recuento de caracteres: 71 + 39 * 2 ** 32 + 95 = 167503724710
Puntos de referencia
Se le preguntó cuánto tiempo tomaría esto y cuánta memoria usaría, así que aquí hay algunos puntos de referencia:
./test.py | pv --buffer-size=1M --average-rate > /dev/null
durante aproximadamente 30 segundos proporciona una velocidad de aproximadamente 14.8 MB / s. Se puede suponer razonablemente que la tasa de salida es aproximadamente constante, por lo que el tiempo de ejecución hasta la finalización debe ser de aproximadamente 167503724710 B / (14.8 * 1048576 B / s) ≈ 10794 s../test.py | tcc -c - -o /dev/stdout | pv --buffer-size=1M --average-rate > /dev/null
, pero parecetcc
que no genera nada hasta que lee todo el archivo fuente.fuente
a[b]
es un azúcar sintáctico para*(a + b)
, que hace la adición.Rubí 28
Para dividir por 3 solo necesitamos eliminar el cero final en el número de base 3:
120 -> 11110 -> 1111 -> 40
Funciona con negativos:
Rubí,
6045Alternativamente, sin usar la conversión de base:
d = -> n {x = n.abs; r = (0..1.0 / 0) .step (3) .take (x) .index x; n> 0? r: -r}fuente
/
operador prohibido donde seFloat::INFINITY
convirtió1.0/0
. Con Ruby 2.1, un campo de mayo(0..1.0/0).step(3)
en0.step(p,3)
, la eliminación de la/
. El mayor problema es que se-r
usa-
para negar. Cambia-r
a 5 caracteres~r.pred
, abusando de Integer # pred para restar 1 sin el operador de resta.Mathematica, 13 caracteres
fuente
&
y usar una variable simple (otros aquí también lo hacen).JavaScript, 56
Hace una cadena de longitud
n
de repetición,
sy reemplaza,,,
con1
. Luego, mide la longitud resultante de la cadena. (¡Ojalá sea unario-
!)fuente
-
operador de negación.-~
conparseInt()
-~prompt()
es mayor queparseInt(prompt())
. No estoy seguro de cómo lidiar con eso.alert(Array(parseInt(prompt())).slice(1).join().replace(/,,,/g,1).length)
Pitón,
4138xrange
parece ser capaz de manejar grandes números (creo que el límite es el mismo que para un largo en C) casi al instante.fuente
10/3
es igual a 3, no 4.print" -"[x<0]+
len (rango (2, abs (x), 3)) `` lo reducirá a 39 caractereslen()
como forma abreviada derepr()
range
, porque en realidad creará la lista.xrange
solo pretende hacerlo, por lo que es capaz de manejar grandes números sin perder tiempo / memoria.Haskell, 90
106Crea una lista de búsqueda infinita (perezosa)
[(0,0),(0,0),(-1,0),(1,0),(-2,0),(2,0),(-3,-1),(3,1), ...]
, recorta todos los elementos que no coincidenn
(/=
es desigualdad en Haskell) y devuelve el primero que sí.Esto se vuelve mucho más simple si no hay números negativos:
25
27simplemente devuelve el
n
elemento th de la lista[0,0,0,1,1,1,2, ...]
.fuente
C #, 232 bytes
Mi primer código de golf ... Y como no había ningún C # y quería probar un método diferente que no había probado aquí, pensé en probarlo. Como algunos otros aquí, solo números no negativos.
Sin golf
fuente
string[] g
, convirtiéndolo enstring[]g
.Add
?Perl (
2622)Esta versión (ab) usa el motor de expresiones regulares de Perl. Lee un número como el último argumento de línea de comando (
pop
) y construye una cadena de3
s de esta longitud ("3" x $number
). El operador de sustitución de expresiones regulares (s///
aquí escrito con diferentes delimitadores debido a las reglas del rompecabezas y con unag
bandera lobal) sustituye tres caracteres por la cadena vacía y devuelve el número de sustituciones, que es el número de entrada entero dividido por tres. Incluso podría escribirse sin él3
, pero la versión anterior parece más divertida.fuente
$_=3x pop;say s|333||g
.'$_=3x pop;say s|333||g||0
. Lento con números grandes como 99999999, y no funciona con números negativos.-p
en la línea de comandos, y puede hacer:$_=3x$_;$_=0|s|...||g
para un total de 22, incluida la cobertura de las entradas 0, 1 o 2.C, 160 caracteres
Solución de división larga carácter por carácter utilizando tablas de búsqueda, es decir, sin cadena atoi () o printf () para convertir entre cadenas de base 10 y enteros.
La salida a veces incluirá un cero inicial, parte de su encanto.
Nota:
Pruebas:
fuente
Python 42
Dado que cada solución publicada aquí que he verificado trunca los decimales aquí es mi solución que hace eso.
Python
5051Dado que Python hace la división de piso, aquí está mi solución que implementa eso.
El entero de entrada está en la variable x.
Probado en Python 2.7 pero sospecho que también funciona en 3.
fuente
-3
es la respuesta correcta-10/3
.JavaScript, 55
Si no se puede usar
-1
, entonces aquí hay una versión que lo reemplaza~0
(¡gracias Peter Taylor!).fuente
~
es un operador Bitwise que invierte los bits del operando (primero lo convierte en un número). Esta es la forma más corta de convertir una cadena en un número (que yo sepa).~~
convierte en un entero, en lugar de hacerlo+
.C 83 caracteres
El número para dividir se pasa a través de stdin, y lo devuelve como el código de salida de
main()
(% ERRORLEVEL% en CMD). Este código abusa de algunas versiones de MinGW porque cuando las optimizaciones no están activadas, trata el último valor de asignación como una declaración de retorno. Probablemente se puede reducir un poco. Admite todos los números que pueden caber en unint
Si no se permite la anulación unaria (-): (129)
Si se niega unario IS : (123)
EDITAR: ugoren me señaló que - ~ es un incremento ...
83 caracteres si se permite la anulación unaria: D
fuente
x+3
es-~-~-~x
.C, 139 caracteres
Ejecutar con número como argumento de línea de comando
Pruebas:
Ediciones:
fuente
A
cómo funciona, mi función solo verifica el bit i en el número n. ¿El estándar C permite omitir declaraciones de tipo o es algo del compilador?ZSH -
3120/21Para números negativos:
Con números negativos (ZSH +
bc
) -6261Probablemente no debería dar dos programas como respuesta, así que aquí hay uno que funciona para cualquier signo de número:
Utiliza el mismo truco de conversión base que la respuesta de Artem Ice .
fuente
C,
8173 caracteresSolo admite números no negativos.
La idea es utilizar puntero aritmético. El número se lee en el puntero
x
, que no apunta a ninguna parte.&x[~2]
=&x[-3]
=x-3
se usa para restar 3. Esto se repite siempre que el número sea superior a 2.i
cuenta el número de veces que se hace (&i[1]
=i+1
).fuente
Java
8679Suponga que el entero está en y:
Convierte en una cadena en la base 3, elimina el último carácter (desplazamiento a la derecha ">>" en la base 3), luego vuelve a convertir a entero.
Funciona para números negativos.
Si el número, y, es <3 o> -3, entonces da 0.
Publicación por primera vez en código golf. =) Entonces no puedo comentar todavía.
Gracias Kevin Cruijssen por los consejos.
fuente
&&
a&
, y 2xInteger
aLong
. (Además, ¿por qué lo usas en~2
lugar de solo-3
? Son el mismo conteo de bytes.)-
, pero no sé si eso cuenta para la negación unaria.Python2.6 (
29) (71) (57) (52) (43)Editar: acabo de darme cuenta de que también tenemos que manejar enteros negativos. Lo arreglará más tarde
Edit2 - Fijo
Edit3 - Guardado 5 caracteres siguiendo el consejo de Joel Cornett
Edit4: dado que la entrada no tiene que ser necesariamente de STDIN o ARGV, se guardaron 9 caracteres al no tomar ninguna entrada de stdin
fuente
abs()
print z if x==abs(x) else -z
print (z,-z)[x<0]
Javascript,
4729Usos
eval
para generar dinámicamente a/
.+
Solo se usa para la concatenación de cadenas, no para la suma.EDITAR: utilizado en
"\57"
lugar deString.fromCharCode(47)
fuente
alert(eval(prompt()+"\573"))
?Rubí (
432217)No solo golf, sino también elegancia :)
La salida será como
(41/1)
. Si debe ser entero, entonces debemos agregar.to_i
al resultado, y si cambiamosto_i
ato_f
, también podremos obtener resultados para flotantes.fuente
rational
línea requerida en Ruby 1.9.3. Omitir los paréntesis ahorra un carácter más .TI-Basic, 8 bytes
¿Ganador? :)
PS Redondea hacia el infinito para números negativos (vea aquí por qué). Para redondear a cero en su lugar, reemplace
int(
coniPart(
sin cambio de byte.Casos de prueba
fuente
Python 2.x,
545351print' -'[x<0],len(range(*(2,-2,x,x,3,-3)[x<0::2]))
¿Dónde
_
está el dividendo y se ingresa como tal?Nota: No estoy seguro si se permite el uso del intérprete interactivo, pero de acuerdo con el OP: "La entrada puede estar en STDIN o ARGV o ingresada de cualquier otra manera"
Editar: ahora para Python 3 (funciona en 2.x, pero imprime una tupla). Funciona con negativos.
fuente
__len__
es suficiente.len(range(100,1000))
cede900
en 3.2.3 en linux.len(xrange(0,_,3))
es más corto y masivamente más rápido de todos modos.C ++, 191
Con principal e incluye, es 246, sin principal e incluye, es solo 178. Las líneas nuevas cuentan como 1 personaje. Trata todos los números como sin signo. No recibo advertencias por tener una devolución principal de un int sin firmar, así que es un juego justo.
Mi primera presentación de codegolf.
usa turnos para dividir el número entre 4 repetidamente y calcula la suma (que converge a 1/3)
Pseudocódigo:
Por otro lado, podría eliminar el método main nombrando d main y haciendo que tome un char ** y usando el valor de retorno de los programas como salida. Devolverá el número de argumentos de la línea de comando dividido por tres, redondeado hacia abajo. Esto lleva su longitud a los 191 anunciados:
fuente
Golfscript - 13 caracteres
fuente
s/seem to //
:(. Tendré que pensarloPowerShell 57 o 46
En 57 caracteres utilizando
%
como operador foreach de PowerShell, no módulo. Esta solución puede aceptar enteros positivos o negativos.En 46 caracteres, si
*
está permitido como operador de repetición de cadena, no se multiplica. Esta opción requiere enteros positivos como valores de entrada.fuente
R
Estos solo funcionan con enteros positivos:
O:
O:
O:
[[EDITAR]] Y uno feo:
[[EDIT2]] Además, probablemente el mejor, inspirado en el código matlab anterior de Elliot G:
fuente
wrong sign in 'by' argument
SmileBASIC,
585136 bytes (¡sin funciones matemáticas!)Explicación:
El programa mueve la capa de fondo suavemente sobre 3 cuadros, y luego obtiene el ángulo después de 1 cuadro, cuando ha recorrido 1/3 de su distancia total.
Versión de división flotante, 38 bytes:
Explicación:
fuente
Haskell
4139 caracteresFunciona con el conjunto completo de enteros positivos y negativos.
Primero crea una lista de 1 o (-1) '(dependiendo del signo de la entrada) para cada tercer entero desde 0 hasta la entrada
n
.abs(n)
para números negativos inclusive.p.ej
n=8 -> [0,3,6]
Luego devuelve la suma de esta lista.
fuente
Clojure, 87; trabaja con negativos; basado en lazyseqs
Sin golf:
fuente
Cuaderno Sabio (21)
fuente