MCM de números racionales

18

El mínimo común múltiplo (LCM) de un conjunto de números Aes el más pequeño número entero btal que b/aes un número entero para todos los enteros aen A. ¡Esta definición se puede extender a números racionales!

Tarea

Encuentre el racional positivo más pequeño btal que b/asea ​​un número entero para todos los racionales a en la entrada.

Reglas

  • Las lagunas estándar están prohibidas.
  • Puede tomar numeradores y denominadores por separado en la entrada, pero no puede tomar dobles, flotantes, etc.
  • La entrada puede no reducirse completamente.
  • Puede tomar entradas enteras como racionales con denominador de 1.
  • Los envíos que alimentarían números racionales a un LCM / GCD incorporado están permitidos, pero no son competitivos.

Casos de prueba

In:  3
Out: 3

In:  1/17
Out: 1/17

In:  1/2, 3/4
Out: 3/2

In:  1/3, 2/8
Out: 1

In:  1/4, 3
Out: 3

In:  2/5, 3
Out: 6

In:  1/2, 3/4, 5/6, 7/8
Out: 105/2

Este es el , por lo que las presentaciones que utilizan la menor cantidad de bytes ganan.

JungHwan Min
fuente
44
Nota: la informática LCM[numerators]/GCD[denominators]puede no funcionar cuando la entrada contiene un número racional no reducido. por ej 1/3, 2/8.
JungHwan Min
Entonces, si lo reduzco, ¿funcionará?
Leaky Nun
@LeakyNun Sí, lo hará.
JungHwan Min
Para alentar a las personas a enviar respuestas no integradas, he editado la pregunta, haciendo que las respuestas integradas no sean competitivas (todavía está permitido). Si esto es un problema, revertiré mi edición.
JungHwan Min
¿Qué pasa con el uso de un LCM incorporado pero solo con enteros, compitiendo o no?
Jonathan Allan

Respuestas:

5

Jalea , 19 bytes

g/:@$€Z©Ḣæl/;®Ḣg/$¤

Pruébalo en línea!

Monja permeable
fuente
1
tfw Jelly apesta con fracciones
Erik the Outgolfer
2
g/:@$€->:g/$€
Jonathan Allan
2
Guarde otros dos bytes con::g/$€ZµḢæl/,Ḣg/$
Jonathan Allan
@JonathanAllan Ese es un buen código ...
Erik the Outgolfer
6

J, 3 bytes, no competitivos.

*./

Dada una lista de entradas racionales, esto dobla LCM a través de ella.

zgrep
fuente
4

sed, 374 (373 + 1) bytes

La -Ebandera de sed cuenta como un byte. Nota: No he intentado jugar golf todavía, y probablemente no lo haga durante bastante tiempo.
La entrada se toma en unario y la salida en unario. Los espacios deben rodear cada fracción. Ejemplo: echo " 1/111 111/11111 111111/111 ".

:d;s, (1*)/\1(1*), \1/\22,;s,(1*)(1*)/\2 ,2\1/\2 ,;td;s,1*(1/22*),\1,g;s,(22*/1)1*,\1,g;:r;s,((1*)/1*)2,\1\2,;s,2(1*/(1*)),\2\1,;tr;h;s,1*/,,g;:g;s/^(1*) 1(1*) 1(1*)/1\1 \2 \3/;tg;s/  */ /g;s/^/ /;/1 1/bg;x;s,/1*,,g;s/^( 1*)( 1*)/\1\2\2/;:l;s/^(1*) (1*) \2(1*)/\1\2 \2 \3/;tl;/  $/be;/  /{s/^(1*) 1*  1*( 1*)/ \1\2\2/;bl};s/^(1* 1* )(1*) (1*)/\1\2\3 \3/;bl;:e;G;s, *\n *,/,

Pruébalo en línea!

zgrep
fuente
3

JavaScript (ES6), 85 bytes

a=>a.reduce(([b,c],[d,e,g=(b,c)=>c?g(c,b%c):b,h=g(b*e,c*d),i=g(b*d,h)])=>[b*d/i,h/i])

¡No busques construcciones! Sin duda alguien superará esto usando un enfoque recursivo o algo así.

Neil
fuente
3

Pari / GP , 3 bytes, no competidor

lcm

Pruébalo en línea!

alephalpha
fuente
@JungHwanMin ¿Significa que se permite un GCD incorporado?
alephalpha
Buen punto. Sí, siempre y cuando sus entradas sean solo enteros.
JungHwan Min
2

Perl 6 ,  46  42 bytes

{[lcm](@_».numerator)/[gcd] @_».denominator}

Pruébalo

{[lcm](($/=@_».nude)[*;0])/[gcd] $/[*;1]}

Pruébalo

La entrada es una lista de números racionales .

Expandido:

{ # bare block lambda with implicit parameter list 「@_」

  [lcm](            # reduce using &infix:<lcm>
    (
      $/ = @_».nude # store in 「$/」 a list of the NUmerators and DEnominiators
                    # ((1,2), (3,4))

    )[
      *;            # from all of the first level 「*」,
      0             # but only the 0th of the second level (numerators)
    ]
  )
  /
  [gcd] $/[ *; 1 ]  # gcd of the denominators
}
Brad Gilbert b2gills
fuente
2

Retina , 117 bytes

\d+
$*
\b(1+)(\1)*/(\1)+\b
$#2$*11/$#3$*
{`^((1+)\2*)/(1+)+ (\2)+/\3+\b
$1 $#4$*1/$3
}`\G1(?=1* (1+))|\G 1+
$1
1+
$.&

Pruébalo en línea! Toma datos como una serie de fracciones impropias separadas por espacios (sin números enteros o mixtos). Explicación:

\d+
$*

Convierte decimal a unario.

\b(1+)(\1)*/(\1)+\b
$#2$*11/$#3$*

Esto reduce cada fracción a sus términos más bajos. El grupo de captura 1 representa el MCD del numerador y el denominador, por lo que contamos el número de capturas antes y después de /. \b(1+)+/(\1)+\bno parece contar el número de capturas correctamente por alguna razón, por lo que uso un grupo de captura adicional y agrego 1 al resultado.

{`^((1+)\2*)/(1+)+ (\2)+/\3+\b
$1 $#4$*1/$3

Esto hace una serie de cosas. El grupo de captura 2 representa el MCD de los numeradores de las dos primeras fracciones, mientras que el grupo de captura 3 representa el MCD de los denominadores. $#4es, por lo tanto, el segundo numerador dividido por su MCD. (Nuevamente, no pude ver la cantidad de capturas del primer numerador, pero solo necesito dividir un numerador por su GCD, por lo que no me cuesta tanto).

}`\G1(?=1* (1+))|\G 1+
$1

Ahora que el segundo numerador se ha dividido por su MCD, solo usamos esta expresión del tutorial aritmético unario para multiplicar los dos juntos, lo que resulta en el MCM. Luego repetimos el ejercicio para las fracciones restantes.

1+
$.&

Convierte unario de nuevo a decimal.

Neil
fuente
2

Lisp común, 154 bytes

(defun f(l &aux(s(pairlis l l)))(loop(and(eval`(=,@(mapcar'car s)))(return(caar s)))(let((x(assoc(reduce'min s :key'car)s)))(rplaca x(+(car x)(cdr x))))))

Algoritmo utilizado (especificado para enteros, pero también funciona para racionales).

Primero haga una lista asociativa de los datos de entrada consigo mismo, para hacer un seguimiento de los valores iniciales de los elementos, de modo que la secuencia de operación esté dada por el "automóvil" de la lista.

(defun f(l &aux (s (pairlis l l)))        ; make the associative list
  (loop
     (when (eval `(= ,@(mapcar 'car s))) ; when the car are all equal
       (return (caar s)))                 ; exit with the first one
     (let ((x (assoc (reduce 'min s :key 'car) s))) ; find the (first) least element
       (rplaca x (+ (car x) (cdr x))))))  ; replace its car adding the original value (cdr)

Casos de prueba:

CL-USER> (f '(3))
3
CL-USER> (f '(1/17))
1/17
CL-USER> (f '(1/2 3/4))
3/2
CL-USER> (f '(1/3 2/8))
1
CL-USER> (f '(1/4 3))
3
CL-USER> (f '(2/5 3))
6
CL-USER> (f '(1/2 3/4 5/6 7/8))
105/2

Nota: La solución es sin el uso de la construcción lcmy gcd, que aceptan enteros.

Renzo
fuente
W00t? Prueba esto en tu REPL (/ (lcm 1 3 5 7) (gcd 2 4 6 8)).
Kaz
@Kaz, ya que, como se dijo en el problema, "Las presentaciones que alimentarían números racionales a un LCM / GCD incorporado están permitidas, pero no compiten".
Renzo
En términos de Lisp, estrictamente hablando, de hecho estamos alimentando racionales cuando llamamos (lcm 1 3 5 7), ya que los enteros son un subtipo de racionales, pero creo que se supone que la regla excluye el uso de a lcmo gcdque permite entradas racionales.
Kaz
@Kaz, operaciones ... ¡Interpreté mal las reglas! ¿Debo eliminar la publicación? (tal vez no sea buen marketing para Common Lisp :)
Renzo
Acabo de poner una nota de que esta es una solución sin usar el entero incorporado lcmy gcd.
Kaz
1

Mathematica, 3 bytes, no competitiva

LCM

Mathematica incorporado en LCMla función es capaz de manejar las entradas de números racionales.

JungHwan Min
fuente
3
Si bien responder a su propia pregunta está bien, no creo que sea muy deportivo contestarla con una solución que tenga una posibilidad muy real de ganar: P
Beta Decay
@BetaDecay Sí ... Así que ahora no está compitiendo.
JungHwan Min
1

PHP , 194 bytes

<?for(list($n,$d)=$_GET,$p=array_product($d);$x=$n[+$k];)$r[]=$x*$p/$d[+$k++];for($l=1;$l&&++$i;$l=!$l)foreach($r as$v)$l*=$i%$v<1;for($t=1+$i;$p%--$t||$i%$t;);echo$p/$t>1?$i/$t."/".$p/$t:$i/$t;

-4 Bytes con PHP> = 7.1 en [$n,$d]=$_GETlugar delist($n,$d)=$_GET

Pruébalo en línea!

Jörg Hülsermann
fuente
1

Lisp común, 87 78 bytes

Utilizando lcm y gcd, que tienen entradas enteras:

(defun l(a)(/(apply #'lcm(mapcar #'numerator a))(apply #'gcd(mapcar #'denominator a))))

Más golfizado:

(defun l(a)(eval`(/(lcm,@(mapcar'numerator a))(gcd,@(mapcar'denominator a))))
Kaz
fuente