Divide un número entre 3 sin usar los operadores *, /, +, -,%

48

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__o add()). Esto también se aplica a operadores de incremento y decremento, como i++o i--. 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
Gaffi
fuente
1
¿Cómo se debe redondear el resultado cuando es positivo? ¿Cómo cuando negativo?
dfeuer

Respuestas:

15

J, 45 44 10 caracteres

".,&'r3'":

Funciona con negativos:

".,&'r3'": 15
5
   ".,&'r3'": _9
_3
   ".,&'r3'": 3e99
1e99

": - formatear como texto

,&'r3'- agregar r3hasta el final

". - ejecutar la cadena, por ejemplo 15r3

defhlt
fuente
1
Funciona si lo haces 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.
Gareth
1
¿Quizás ##~3=_3#\i.para 11 personajes?
Gareth
1
En realidad, puedes reducir el tuyo a 10 caracteres con ##~0 0 1$~.
Gareth
1
Puede reducir eso usando un gancho 3#.}:(#:~$&3)pero aún es más largo y no soluciona el problema del número negativo.
Gareth
1
Sí, se puede utilizar la función de alimentación ^: o de la Agenda @. para una ifo if...elsereemplazo. 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.
Gareth
56

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:

#!/usr/bin/env python3
import sys

# 71
sys.stdout.write('''#include <stdint.h>
#include <stdio.h>
int32_t div_by_3(int32_t input){''')

# 39 * 2**32
for i in range(-2**31, 2**31):
    # 18 + 11 + 10 = 39
    sys.stdout.write('if(input==%11d)return%10d;' % (i, i / 3))

# 95
sys.stdout.write(r'''return 7;}int main(int c,char**v){int32_t n=atoi(a[1]);printf("%d / 3 = %d\n",n, div_by_3(n));}''')

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:

  • Tiempo de ejecución del script: la ejecución ./test.py | pv --buffer-size=1M --average-rate > /dev/nulldurante 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.
  • Tiempo de compilación: el compilador TCC afirma que compila el código C a 29.6 MB / s , lo que hace que el tiempo de compilación sea 167503724710 B / (29.6 * 1048576 B / s) ≈ 5397 s. (Por supuesto, esto puede ejecutarse en una tubería con el script).
  • Tamaño del código compilado: intenté estimarlo usando ./test.py | tcc -c - -o /dev/stdout | pv --buffer-size=1M --average-rate > /dev/null, pero parece tccque no genera nada hasta que lee todo el archivo fuente.
  • Uso de la memoria para ejecutar: dado que el algoritmo es lineal (y tcc no se optimiza entre líneas), la sobrecarga de la memoria debe ser de solo unos pocos kilobytes (aparte del código en sí, por supuesto).
Caracol mecánico
fuente
22
Este es el epítome del hardcoding. ++++++++++
Joe Z.
44
Dicho esto, estoy seguro de que si les das un archivo fuente de 160 GB y les pides que lo compilen y lo prueben, te mirarían como si estuvieras loco.
Joe Z.
16
Si mi jefe me pidiera que calcule una división por tres sin - + / *%, pensaría que está loco.
Mikaël Mayer
Y sin embargo, a[b]es un azúcar sintáctico para *(a + b), que hace la adición.
Konrad Borowski
12
@NicolasBarbulesco Hay una restricción de tamaño en las respuestas de Stack Exchange.
Timtech
38

Rubí 28

b=->n{n.to_s(3).chop.to_i 3}

Para dividir por 3 solo necesitamos eliminar el cero final en el número de base 3: 120 -> 11110 -> 1111 -> 40

Funciona con negativos:

ice distantstar:~/virt/golf [349:1]% ruby ./div3.rb
666
222
ice distantstar:~/virt/golf [349]% ruby ./div3.rb
-15        
-5

Rubí, 60 45

Alternativamente, 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}

d=->n{(r=1.step(n.abs,3).to_a.size);n>0?r:-r}
defhlt
fuente
1
La alternativa sin conversión de base tiene el /operador prohibido donde se Float::INFINITYconvirtió 1.0/0. Con Ruby 2.1, un campo de mayo (0..1.0/0).step(3)en 0.step(p,3), la eliminación de la /. El mayor problema es que se -rusa -para negar. Cambia -ra 5 caracteres ~r.pred, abusando de Integer # pred para restar 1 sin el operador de resta.
kernigh
26

Mathematica, 13 caracteres

Mean@{#,0,0}&
alephalpha
fuente
Esto es perverso: supongo que podría guardar &y usar una variable simple (otros aquí también lo hacen).
Yves Klett
3
@YvesKlett: Mean es intrínsecamente perverso.
GuitarPicker
18

JavaScript, 56

alert(Array(-~prompt()).join().replace(/,,,/g,1).length)

Hace una cadena de longitud nde repetición ,sy reemplaza ,,,con 1. Luego, mide la longitud resultante de la cadena. (¡Ojalá sea unario -!)

Casey Chu
fuente
+1 pero no funciona con valores negativos
Francesco Casula
Uh, pregunta ... ¿cómo cuenta esto? Utiliza el -operador de negación.
Patrick Roberts
@Patrick Tomé la memoria descriptiva para significar que no resta - si se quiere, se puede reemplazar -~conparseInt()
Casey Chu
@CaseyChu el valor devuelto por -~prompt()es mayor que parseInt(prompt()). No estoy seguro de cómo lidiar con eso.
Patrick Roberts
alert(Array(parseInt(prompt())).slice(1).join().replace(/,,,/g,1).length)
Casey Chu
16

Pitón, 41 38

print"-"[x:]+`len(xrange(2,abs(x),3))`

xrange 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.

>>> x = -72
-24

>>> x = 9223372036854775806
3074457345618258602
grc
fuente
2
10/3es igual a 3, no 4.
Joel Cornett
Hacer print" -"[x<0]+len (rango (2, abs (x), 3)) `` lo reducirá a 39 caracteres
Joel Cornett
El formato de comentarios de golfexchange lo está arruinando. en lo anterior he utilizado para encerrar entre comillas sencillas len()como forma abreviada derepr()
Joel Cornett
Lo he actualizado. No puedo usar range, porque en realidad creará la lista. xrangesolo pretende hacerlo, por lo que es capaz de manejar grandes números sin perder tiempo / memoria.
grc
2
Imagina que es Python 3;) Me gusta el corte de char único por cierto.
Joel Cornett
11

Haskell, 90 106

d n=snd.head.dropWhile((/=n).fst)$zip([0..]>>=ν)([0..]>>=replicate 3>>=ν);ν q=[negate q,q]

Crea 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 coinciden n( /=es desigualdad en Haskell) y devuelve el primero que sí.

Esto se vuelve mucho más simple si no hay números negativos:

25 27

(([0..]>>=replicate 3)!!)

simplemente devuelve el nelemento th de la lista [0,0,0,1,1,1,2, ...].

dejó de girar en sentido antihorario
fuente
3
Nunca pensé en esa segunda solución. Podría implementar algo así en Python
acólito el
8

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.

class l:System.Collections.Generic.List<int>{}class p{static void Main(string[] g){int n=int.Parse(g[0]);l b,a=new l();b=new l();while(a.Count<n)a.Add(1);while(a.Count>2){a.RemoveRange(0,3);b.Add(1);}System.Console.Write(b.Count);}}

Sin golf

class l : System.Collections.Generic.List<int>
{ }
class p
{
    static void Main(string[] g)
    {
        int n = int.Parse(g[0]);
        l b, a = new l();
        b = new l();
        while (a.Count < n) a.Add(1);
        while (a.Count > 2)
        {
            a.RemoveRange(0, 3);
            b.Add(1);
        }
        System.Console.Write(b.Count);
    }
}
Drake Clarris
fuente
2
Alrededor de 5 años más tarde .. Puede guardar 1 byte quitando el espacio desde string[] g, convirtiéndolo enstring[]g
Metoniem
Citando "No use los operadores no basados ​​en texto *, /, +, - o% (o sus equivalentes, como div o add ()" - ¿no está usando un equivalente - .Add?
Jonathan Frech
@ JonathanFrech Ese método de agregar no funciona en dos números, solo agrega un valor a una colección
Encarnación de la ignorancia
7

Perl (26 22)

$_=3x pop;say s|333||g

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 de 3s 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 una gbandera 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 él 3, pero la versión anterior parece más divertida.

$ perl -E '$_=3x pop;say s|333||g' 42
14
memowe
fuente
2
¡Hola @memowe, buen trabajo! Puede guardar algunos caracteres más (4) haciendo $_=3x pop;say s|333||g.
Dom Hastings
2
Cuando la entrada es 0, 1 o 2, imprime una cadena vacía. Si necesita imprimir 0, entonces se necesita más de 3 caracteres (25 en total): '$_=3x pop;say s|333||g||0. Lento con números grandes como 99999999, y no funciona con números negativos.
kernigh
1
Use -pen la línea de comandos, y puede hacer: $_=3x$_;$_=0|s|...||gpara un total de 22, incluida la cobertura de las entradas 0, 1 o 2.
Xcali
6

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.

main(int n,char**a){
char*s=a[1],*x=0;
if(*s==45)s=&s[1];
for(;*s;s=&s[1])n=&x[*s&15],x="036"[(int)x],*s=&x["000111222333"[n]&3],x="012012012012"[n]&3;
puts(a[1]);
}

Nota:

  • abusa del acceso a la matriz para implementar la adición.
  • compila con clang 4.0, otros compiladores pueden vomitar.

Pruebas:

./a.out -6            -2
./a.out -5            -1
./a.out -4            -1
./a.out -3            -1
./a.out -2            -0
./a.out -1            -0
./a.out 0             0
./a.out 1             0
./a.out 2             0
./a.out 3             1
./a.out 4             1
./a.out 5             1
./a.out 6             2
./a.out 42            14
./a.out 2011          0670
conejo bebé
fuente
6

Python 42

int(' -'[x<0]+str(len(range(2,abs(x),3))))

Dado que cada solución publicada aquí que he verificado trunca los decimales aquí es mi solución que hace eso.

Python 50 51

int(' -'[x<0]+str(len(range([2,0][x<0],abs(x),3))))

Dado 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.

Mate
fuente
+1 Por ofrecer ambas alternativas a la situación de valor negativo. Como ya hay tantas respuestas, no ajustaré las especificaciones para excluir una u otra opción, aunque personalmente estaría de acuerdo en que esa -3es la respuesta correcta -10/3.
Gaffi
Para aquellos que se preocupan por la división del piso en python: python-history.blogspot.com/2010/08/…
Matt
¿Qué pasa con la multiplicación y la resta en tu segunda solución?
stand
@boothby La segunda solución implementa la división de piso. Quería hacer rango (0, abs (x), 3) para números negativos y rango (2, abs (x), 3) para números positivos. Para hacer eso tuve rango (2 ... luego resté 2 cuando x es negativo. X <0 es verdadero cuando x es negativo, (verdadero) * 2 == 2
Matt
No entiendo la diferencia entre la división del piso y los decimales truncados. ¿Tiene esto que ver con la división negativa?
Joel Cornett
6

JavaScript, 55

alert(parseInt((~~prompt()).toString(3).slice(0,-1),3))

Si no se puede usar -1, entonces aquí hay una versión que lo reemplaza ~0(¡gracias Peter Taylor!).

alert(parseInt((~~prompt()).toString(3).slice(0,~0),3))
Chinche de tinta
fuente
1
@ArtemIce One ~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).
Inkbug
1
Siento que usar el análisis / conversión de cadenas es una trampa, ya que es a) un proceso muy complicado y costoso en comparación con las operaciones bit a bit, b) usa los operadores prohibidos internamente yc) ocuparía muuuucho más caracteres que una solución homologada. Algo así como cómo la gente se vuelve gruñona cuando usas los tipos incorporados cuando se te pide que implementes una clasificación rápida.
Wug
1
@Sam Además, se ~~convierte en un entero, en lugar de hacerlo +.
Inkbug
1
@Wug Es codegolf, por lo que no se trata de eficiencia a menos que se especifique en la tarea.
defhlt
3
+1 para aprovechar diferentes bases. Es una de mis técnicas de golf JavaScript favoritas.
DocMax
6

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)

I(unsigned a){a=a&1?I(a>>1)<<1:a|1;}main(a,b,c){scanf("%i",&b);a=b;a=a<0?a:I(~a);for(c=0;a<~1;a=I(I(I(a))))c=I(c);b=b<0?I(~c):c;}

Si se niega unario IS : (123)

I(unsigned a){a=a&1?I(a>>1)<<1:a|1;}main(a,b,c){scanf("%i",&b);a=b;a=a<0?a:-a;for(c=0;a<~1;a=I(I(I(a))))c=I(c);b=b<0?-c:c;}

EDITAR: ugoren me señaló que - ~ es un incremento ...

83 caracteres si se permite la anulación unaria: D

main(a,b,c){scanf("%i",&b);a=b;a=a<0?a:-a;for(c=0;a<~1;a=-~-~-~a)c=-~c;b=b<0?-c:c;}
Kaslai
fuente
Si se permite la anulación unaria, x+3es -~-~-~x.
Ugoren
Gracias por eso. No sé por qué eso nunca se me ocurrió. Supongo que no me di cuenta de que podías apilar unarios tan gratuitamente, jeje.
Kaslai
5

C, 139 caracteres

t;A(a,b){return a?A((a&b)<<1,a^b):b;}main(int n,char**a){n=atoi(a[1]);for(n=A(n,n<0?2:1);n&~3;t=A(n>>2,t),n=A(n>>2,n&3));printf("%d\n",t);}

Ejecutar con número como argumento de línea de comando

  • Maneja números negativos y positivos.

Pruebas:

 ./a.out -6            -2
 ./a.out -5            -1
 ./a.out -4            -1
 ./a.out -3            -1
 ./a.out -2            0
 ./a.out -1            0
 ./a.out 0             0
 ./a.out 1             0
 ./a.out 2             0
 ./a.out 3             1
 ./a.out 4             1
 ./a.out 5             1
 ./a.out 6             2
 ./a.out 42            14
 ./a.out 2011          670

Ediciones:

  • ahorró 10 caracteres al mezclar la suma (A) para eliminar las variables locales.
conejo bebé
fuente
1
Bien hecho. Hice mi mejor esfuerzo en girar un poco y llegué a 239. Simplemente no puedo entender Acó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?
shiona
1
C asumirá int si no se especifica.
Wug
5

ZSH - 31 20/21

echo {2..x..3}|wc -w

Para números negativos:

echo {-2..x..3}|wc -w

Con números negativos (ZSH + bc) -62 61

Probablemente no debería dar dos programas como respuesta, así que aquí hay uno que funciona para cualquier signo de número:

echo 'obase=10;ibase=3;'`echo 'obase=3;x'|bc|sed 's/.$//'`|bc

Utiliza el mismo truco de conversión base que la respuesta de Artem Ice .

Jon Gauthier
fuente
5

C, 81 73 caracteres

Solo admite números no negativos.

char*x,*i;
main(){
    for(scanf("%d",&x);x>2;x=&x[~2])i=&i[1];
    printf("%d",i);
}

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-3se usa para restar 3. Esto se repite siempre que el número sea superior a 2. icuenta el número de veces que se hace ( &i[1]= i+1).

Ugoren
fuente
Tratando de entender el código, ¿alguien arrojó algunas luces? Gracias
Cong Hui
@Chui, explicación agregada.
ugoren
@ugoren, por lo que entiendo, ¿no debería printf ("% d") imprimir el puntero de dirección de memoria que tengo en Hex? ¿Por qué está imprimiendo un número entero? o char * i se inicializó para apuntar a la dirección de memoria 0 por defecto? Gracias
Cong Hui
5

Java 86 79

Suponga 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.

System.out.print(~2<y&y<3?0:Long.valueOf(Long.toString(y,3).split(".$")[0],3));

Publicación por primera vez en código golf. =) Entonces no puedo comentar todavía.

Gracias Kevin Cruijssen por los consejos.

Vectorizado
fuente
Sé que ha sido hace más de dos años, pero puedes jugar al golf algunas partes: &&a &, y 2x Integera Long. (Además, ¿por qué lo usas en ~2lugar de solo -3? Son el mismo conteo de bytes.)
Kevin Cruijssen
1
@KevinCruijssen Muy nostálgico para editar mi primera publicación después de tanto tiempo. No estaba muy seguro de por qué pensé que ~ 2 era mejor en ese entonces.
Vectorizado el
2
@KevinCruijssen, el desafío dice que no puedes usarlo -, pero no sé si eso cuenta para la negación unaria.
FlipTack
@FlipTack Ah, tienes toda la razón. En ese caso, olvida que lo dije. :)
Kevin Cruijssen
4

Python2.6 ( 29 ) ( 71 ) ( 57 ) ( 52 ) (43)

z=len(range(2,abs(x),3))
print (z,-z)[x<0]

print len(range(2,input(),3))

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

elssar
fuente
abs()
Continúe
más corto de hacerprint z if x==abs(x) else -z
Joel Cornett
mejor aún,print (z,-z)[x<0]
Joel Cornett
@ArtemIce gracias, solo me di cuenta de que podía usar eso después de leer otra respuesta anterior.
elssar
@JoelCornett humm, no sabía sobre eso, gracias
elssar
4

Javascript, 47 29

Usos evalpara generar dinámicamente a /. +Solo se usa para la concatenación de cadenas, no para la suma.

alert(eval(prompt()+"\57"+3))

EDITAR: utilizado en "\57"lugar deString.fromCharCode(47)

Peter Olson
fuente
-1 para alert(eval(prompt()+"\573"))?
Shieru Asakoto
4

Rubí ( 43 22 17)

No solo golf, sino también elegancia :)

p Rational gets,3

La salida será como (41/1). Si debe ser entero, entonces debemos agregar .to_ial resultado, y si cambiamos to_ia to_f, también podremos obtener resultados para flotantes.

Hauleth
fuente
1
Funciona sin la rationallínea requerida en Ruby 1.9.3. Omitir los paréntesis ahorra un carácter más .
steenslag
4

TI-Basic, 8 bytes

¿Ganador? :)

int(mean({Ans,0,0

PS Redondea hacia el infinito para números negativos (vea aquí por qué). Para redondear a cero en su lugar, reemplace int(con iPart(sin cambio de byte.

Casos de prueba

-4:prgmDIVIDE
              -2
11:prgmDIVIDE
               3
109:prgmDIVIDE
              36
Timtech
fuente
3

Python 2.x, 54 53 51

print' -'[x<0],len(range(*(2,-2,x,x,3,-3)[x<0::2]))

¿Dónde _está el dividendo y se ingresa como tal?

>>> x=-19
>>> print' -'[x<0],len(range(*(2,-2,x,x,3,-3)[x<0::2]))
- 6

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.

Joel Cornett
fuente
¿Funciona también en Python 3?
Caracol mecánico el
No tiene que ser subscriptable; Tener __len__es suficiente.
Caracol mecánico el
len(range(100,1000))cede 900en 3.2.3 en linux.
Caracol mecánico el
Esto no funciona para números negativos. Y len(xrange(0,_,3))es más corto y masivamente más rápido de todos modos.
grc
@Mechanicalsnail: punto tomado. Lo concedo Funciona en 3.
Joel Cornett
3

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.

#include<iostream>
#define R return
typedef unsigned int U;U a(U x,U y){R y?a(x^y,(x|y^x^y)<<1):x;}U d(U i){if(i==3)R 1;U t=i&3,r=i>>=2;t=a(t,i&3);while(i>>=2)t=a(t,i&3),r=a(r,i);R r&&t?a(r,d(t)):0;}U main(){U i;std::cin>>i,std::cout<<d(i);R 0;}

usa turnos para dividir el número entre 4 repetidamente y calcula la suma (que converge a 1/3)

Pseudocódigo:

// typedefs and #defines for brevity

function a(x, y):
    magically add x and y using recursion and bitwise things
    return x+y.

function d(x):
    if x = 3:
        return 1.
    variable total, remainder
    until x is zero:
        remainder = x mod 4
        x = x / 4
        total = total + x
    if total and remainder both zero:
        return 0.
    else:
        return a(total, d(remainder)).

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:

#define R return
typedef unsigned int U;U a(U x,U y){R y?a(x^y,(x|y^x^y)<<1):x;}U main(U i,char**q){if(i==3)R 1;U t=i&3,r=i>>=2;t=a(t,i&3);while(i>>=2)t=a(t,i&3),r=a(r,i);R r&&t?a(r,d(t)):0;}
Wug
fuente
3

Golfscript - 13 caracteres

~3base);3base
gnibbler
fuente
no parece manejar la entrada negativa
res
1
@res s/seem to //:(. Tendré que pensarlo
gnibbler
3

PowerShell 57 o 46

En 57 caracteres utilizando %como operador foreach de PowerShell, no módulo. Esta solución puede aceptar enteros positivos o negativos.

(-join(1..(Read-Host)|%{1})-replace111,0-replace1).Length

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.

("1"*(Read-Host)-replace111,0-replace1).Length
Joseph Alcorn
fuente
Si alguna vez regresas, publiqué una corrección de errores. Si quieres que elimine el mío e incorpore el cambio en el tuyo, házmelo saber.
Veskah
3

R

Estos solo funcionan con enteros positivos:

max(sapply(split(1:x,1:3), length))
# Gives a warning that should be ignored

O:

min(table(rep(1:3, x)[1:x]))

O:

length((1:x)[seq(3,x,3)])

O:

sum(rep(1,x)[seq(3,x,3)])

[[EDITAR]] Y uno feo:

trunc(sum(rep(0.3333333333, x)))

[[EDIT2]] Además, probablemente el mejor, inspirado en el código matlab anterior de Elliot G:

length(seq(1,x,3))
lebatsnok
fuente
Quería implementar la misma idea que en su EDIT2 pero no funciona para números negativos:wrong sign in 'by' argument
Andreï Kostyrka
3

SmileBASIC, 58 51 36 bytes (¡sin funciones matemáticas!)

INPUT N
BGANIM.,4,-3,N
WAIT?BGROT(0)

Explicación:

INPUT N           'get input
BGANIM 0,"R",-3,N 'smoothly rotate background layer 0 by N degrees over 3 frames
WAIT              'wait 1 frame
PRINT BGROT(0)    'display angle of layer 0

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:

INPUT N
BGANIM.,7,-3,N
WAIT?BGVAR(0,7)

Explicación:

INPUT N           'input
BGANIM 0,"V",-3,N 'smoothly change layer 0's internal variable to N over 3 frames
WAIT              'wait 1 frame
PRINT BGVAR(0,7)  'display layer 0's internal variable
12Me21
fuente
3

Haskell 41 39 caracteres

Funciona con el conjunto completo de enteros positivos y negativos.

f n=sum[sum$1:[-2|n<0]|i<-[3,6..abs n]]

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.

Charl Kruger
fuente
No funciona en números negativos (-3/3 es -1 no 1).
Cormac
Es bueno que lo hayas hecho funcionar en números negativos, pero no puedes usar /, lee la especificación.
Cormac
Oh dios, me tienes dos veces. Todo arreglado;)
Charl Kruger
¡Agradable! Por cierto, puedes obtener 39 caracteres con fn = sum [sum $ 1: [- 2 | n <0] | i <- [3,6..abs n]]
Cormac
2

Clojure, 87; trabaja con negativos; basado en lazyseqs

(defn d[n](def r(nth(apply interleave(repeat 3(range)))(Math/abs n)))(if(> n 0)r(- r)))

Sin golf:

(defn d [n]
  (let [r (nth (->> (range) (repeat 3) (apply interleave))
               (Math/abs n))]
        (if (pos? n)
          r
          (- r))))
defhlt
fuente