Bucles de división entera

8

Desafío

Dado cualquier número entero positivo soportado por su idioma:

  1. Tome la entrada y divídala en dos mitades. Para todas las divisiones en este programa, si la entrada es impar, redondee la mitad hacia arriba y la mitad hacia abajo (ej .: 7 -> 3,4no 7 -> 3.5,3.5).
  2. Divida cualquier número por la mitad, luego tome la mayor de estas dos mitades nuevas y agréguela nuevamente al número que no se dividió. Ej: 3,4 -> (1,2),4 -> 1,6o 3,4 -> 3,(2,2) -> 5,2.
  3. Repita el paso 2 hasta llegar a un conjunto que haya visto antes. Ej: 5 -> 3,2 -> (1,2),2 -> 1,4 -> 1,(2,2) -> 3,2. Como hemos visto 3,2antes, podemos dejar de repetir. Puede agotar completamente una pila en el proceso de hacer esto. Ej: 5 -> 3,2 -> (1,2),2 -> 1,4 -> (0,1),4 -> 0,5.
  4. Salida de cada par en el bucle (es decir, lo anterior sin los pasos intermedios, desde la primera aparición de un par hasta el segundo, pero sin incluir el segundo). Ej: 3,2 -> 1,4. Si se incluye la entrada, no envíe una salida 0con ella 5 -> 3,2 -> 1,4, no 0,5 -> 3,2 -> 1,4.
  5. Repita los pasos 1-4 dividiendo los pares de manera diferente.

I / O

La entrada es un número entero positivo mayor 1y menor que el número entero máximo admitido por su idioma o el número entero máximo que no bloqueará la computadora, lo que sea menor.

La salida es los bucles de arriba en cualquier formato que desee (cadena, lista, matriz, etc.). Se permite el espacio en blanco final.

No envíe el mismo bucle dos veces, ni diferentes versiones del mismo bucle. Ej: 2 -> 1,1y 1,1 -> 2son dos bucles válidos, pero describen el mismo bucle, comenzando en diferentes puntos del bucle. Del mismo modo, dos bucles que son idénticos pero van en el orden inverso no se deben generar. Ej: 3 -> 1,2 -> 2,1y 3 -> 2,1 -> 1,2son el mismo bucle, pero van en la dirección opuesta entre sí.

Puede usar cualquier delimitador para diferenciar entre los pares, entre cada número en los pares y entre cada bucle, siempre que sean tres caracteres o cadenas distintos. Arriba, dividí los números usando comas, los pares usando ->'s, y los bucles usando instrucciones aburridas. En mis ejemplos a continuación, usaré paréntesis alrededor de cada par, comas entre cada número dentro de un par y nuevas líneas entre cada bucle.

Ejemplos

Crédito al código de @ WheatWizard para arreglar mi lista de ejemplos. Como dije en un borrador anterior, estaba seguro de que me faltaban algunos, ya que lo hacía a mano, pero vaya, me faltaban algunos.

Entrada: 2
Salida:(2)(1,1)

Entrada: 3
Salida:

(3)(1,2)
(1,2)(2,1)
(3)(1,2)(2,1)

Entrada: 4
Salida:

(4)(2,2)(1,3)
(1,3)(3,1)
(4)(2,2)(1,3)(3,1)
(4)(2,2)(3,1)(1,3)
(3,1)(1,3)
(4)(2,2)(3,1)

Entrada: 5

Salida:

(5)(2,3)(1,4)
(1,4)(3,2)
(2,3)(1,4)(3,2)(4,1)
(5)(2,3)(1,4)(3,2)(4,1)
(2,3)(4,1)
(5)(2,3)(4,1)

Entrada: 6

Salida:

(6)(3,3)(1,5)
(1,5)(4,2)(2,4)
(4,2)(2,4)
(1,5)(4,2)(5,1)(2,4)
(4,2)(5,1)(2,4)
(6)(3,3)(1,5)(4,2)(5,1)
(6)(3,3)(5,1)(2,4)(1,5)
(2,4)(1,5)(4,2)
(5,1)(2,4)(1,5)(4,2)
(2,4)(4,2)
(5,1)(2,4)(4,2)
(6)(3,3)(5,1)

Entrada: 7

Salida:

(7)(3,4)(1,6)
(1,6)(4,3)(2,5)
(2,5)(5,2)
(3,4)(1,6)(4,3)(2,5)(5,2)(6,1)
(7)(3,4)(1,6)(4,3)(2,5)(5,2)(6,1)
(3,4)(1,6)(4,3)(6,1)
(7)(3,4)(1,6)(4,3)(6,1)
(7)(3,4)(5,2)(2,5)(1,6)
(2,5)(1,6)(4,3)
(3,4)(5,2)(2,5)(1,6)(4,3)(6,1)
(7)(3,4)(5,2)(2,5)(1,6)(4,3)(6,1)
(5,2)(2,5)
(3,4)(5,2)(6,1)
(7)(3,4)(5,2)(6,1)

Puntuación

Este es el , por lo que gana el conteo de bytes más bajo.


Este es mi primer desafío aquí, por lo que cualquier comentario sería muy apreciado. Enlace al sandbox aquí .

Dato curioso: un día me aburrí y jugué con pequeñas piezas al azar de mina de lápiz de esta manera y finalmente noté que podía seguir en este tipo de bucles. Por alguna razón, mi primera reacción fue "oye, este sería un gran desafío para el golf de código".

DonielF
fuente
44
Bienvenido a PPCG, ¡buen primer desafío!
FlipTack
¿Podemos imprimir (a,0)en el lugar de (a)? Esto tiende a tener sentido en idiomas fuertemente tipados.
Ad Hoc Garf Hunter
@WheatWizard Nope. Al imprimir la entrada, simplemente imprime la entrada sin el cero. No he visto un desafío aquí donde se reduce a solo uno o dos bytes.
DonielF
Ok, eso es lo suficientemente justo. Pero para el registro, ciertamente no lo llamaría uno o dos bytes. Para mí, parece que aproximadamente el 30% de mi recuento de bytes proviene de eliminar el cero.
Ad Hoc Garf Hunter
Dado que el mismo bucle en reversa es el mismo, ¿podemos generar los bucles en reversa?
Agradable

Respuestas:

2

Limpio , 267 ... 167 bytes

import StdEnv
f s l|any((==)s)l=[dropWhile((<>)s)l]#[h,t:_]=s
|1>h*t=f[max h t]l=f[h/2,(h+1)/2+t](l++[s])++(f[(t+1)/2+h,t/2](l++[s]))
@n=removeDup(f[n/2,(n+1)/2][[n]])

Pruébalo en línea!

Sin golf:

loops num
    = removeDup (half (divide num) [[num]])
where
    divide num
        = [num/2, (num+1)/2]
    half [_, 0] list
        = list
    half [0, _] list
        = list
    half [a, b] list
        | isMember [a, b] list
            = [dropWhile ((<>) [a, b]) list]
        # [u, v: _]
            = divide a
        # [x, y: _]
            = divide b
        = (half [u, v+b] (list ++ [a, b])) ++ (half [a+y, x] (list ++ [a, b]))
Οurous
fuente
2

Haskell , 227 203 bytes

17 bytes guardados gracias a Οurous

(%)=div
u x|odd x=x%2+1|1>0=x%2
[0,b]!l=[b]!l
[b,0]!l=[b]!l
t!l|elem t l=[dropWhile(/=t)l]
t@[a,b]!l|q<-l++[t]=[a%2,u a+b]!q++[u b+a,b%2]!q
f x|q<-[x%2,u x]![[x]]=[a|(a,b)<-zip q[0..],notElem a$take b q]

Pruébalo en línea!

Ad Hoc Garf Hunter
fuente
¿El uso de listas no sería más corto que las tuplas, ya que podría manejar los casos de elementos 1 y 2 con el mismo show?
Οurous
@ Οurous En realidad tienes razón, es más corto, solo requiere un poco de trabajo.
Ad Hoc Garf Hunter