Cómo NO reducir fracciones

13

Reducir fracciones de manera incorrecta

En este desafío de código de golf tienes que encontrar fracciones que se puedan reducir de manera incorrecta pero que terminen en el mismo número.

Nota: la reducción de fracciones de la manera incorrecta aquí tiene una definición exacta, ver detalles.

Ejemplo:

64/16 = 6 4/1 6 = 4/1 = 4

Por supuesto, no puede simplemente golpear ambos 6es, pero aquí todavía termina con el valor correcto. En este desafío tienes que encontrar ejemplos como este.

Detalles

Debe escribir una función / programa que acepte un entero positivo ncomo entrada y salidas / devuelva una lista / matriz de las fracciones en formato
numerator1,denominator1,numerator2,denominator2,...

El programa tiene que averiguar para cada fracción a/bcon a+b=ny a,b>0si puede reducirse de manera incorrecta . (No importa si se puede reducir de la manera convencional o si hay muchas posibilidades de reducciones, solo tiene que ser posible reducirlo de la manera incorrecta al menos de una manera).

Definición de la manera incorrecta: una fracción se puede reducir de manera incorrecta si y solo si la misma secuencia de dígitos sucesivos aparece en ayb y si el valor de la fracción permanece igual si quita la subcadena.

Ejemplo: 1536/353 se puede 'reducir' a 16/3 pero esos dos valores no son iguales, por lo que no puede reducir esta fracción de manera incorrecta .

Tenga en cuenta que esta definición de reducir el camino equivocado también puede incluir fracciones que se reducen del modo correcto: 110/10 = 11/1está dentro de la definición de reducir el camino equivocado aunque sea un paso válido.

Puntuación

El menor número de bytes gana. Puede escribir una función o programa que acepte un número entero y devuelva una matriz o un programa que use stdin / stdout o puede considerar n guardado en una variable y al final del programa, la lista debe guardarse en otra variable.

Casos de prueba

Incluya los siguientes casos de prueba (dígame cuáles debo agregar, no tengo idea de cuántas de esas fracciones hay / cuántos ejemplos esperar)

n=80 (64/16 should be in this list)
n=147 (98/49 should be in this list)
n=500 (294/196 should be in this list) WRONG since 294+196 != 500 Thanks Falko
falla
fuente
3
Considere definir un término para "el camino equivocado", como "tonto" o "extraño". Creo que la publicación sería más fácil de entender, porque los lectores inmediatamente entienden que debe haber una definición para el término.
Michael Easter
3
¿Qué pasa si hay varias formas de reducir una fracción y solo algunas están equivocadas? 1010/10 = 101/1 && 1010/10 /= 110/1
John Dvorak
1
¿Variante de projecteuler.net/problem=33 ?
user80551
1
Su segundo caso de prueba ( n=147) es incorrecta: 49/89 != 4/8.
Beta Decay
1
Si hay más de una forma de reducir una fracción, ¿podemos incluirla varias veces en el conjunto de resultados?
John Dvorak

Respuestas:

3

Pitón 2-183 180

r=range
s=lambda a:[(a[i:j],int(a[:i]+a[j:]))for i in r(len(a))for j in r(i+1,len(a)+(i>0))]
l=sum([[a,n-a]for a in r(n)for p,x in s(`a`)for q,y in s(`n-a`)if(n-a)*x==a*y<p==q],[])

la entrada debe almacenarse en n, la salida se almacenará en l.

Casos de prueba:

n = 80:

[10, 70, 16, 64, 20, 60, 30, 50, 40, 40, 40, 40, 50, 30, 60, 20, 64, 16, 70, 10]

n = 147:

[49, 98, 98, 49]

n = 490:

[10, 480, 20, 470, 30, 460, 40, 450, 50, 440, 60, 430, 70, 420, 80, 410, 90, 400, 90, 400, 98, 392, 100, 390, 100, 390, 110, 380, 120, 370, 130, 360, 140, 350, 150, 340, 160, 330, 170, 320, 180, 310, 190, 300, 190, 300, 196, 294, 200, 290, 200, 290, 210, 280, 220, 270, 230, 260, 240, 250, 245, 245, 245, 245, 245, 245, 245, 245, 245, 245, 250, 240, 260, 230, 270, 220, 280, 210, 290, 200, 290, 200, 294, 196, 300, 190, 300, 190, 310, 180, 320, 170, 330, 160, 340, 150, 350, 140, 360, 130, 370, 120, 380, 110, 390, 100, 390, 100, 392, 98, 400, 90, 400, 90, 410, 80, 420, 70, 430, 60, 440, 50, 450, 40, 460, 30, 470, 20, 480, 10]

En caso de que se prohíban los duplicados en la salida, obtendrá 10 caracteres más:

r=range
s=lambda a:[(a[i:j],int(a[:i]+a[j:]))for i in r(len(a))for j in r(i+1,len(a)+(i>0))]
l=sum(map(list,{(a,n-a)for a in r(n)for p,x in s(`a`)for q,y in s(`n-a`)if(n-a)*x==a*y<p==q}),[])
Wrzlprmft
fuente
3

Haskell 207 206 (¿209?) Caracteres

import Data.List
x![]=[x];(w:x)!(y:z)|w==y=x!z;_!_=[]
a@(w:x)%b=a!b++[w:e|e<-x%b];a%b=a!b
h=show
f n=[(c,n-c)|c<-[1..n-1],i<-inits$h c,s<-init$tails i,s/=h c,a<-h c%s,b<-h(n-c)%s,read a*(n-c)==read('0':b)*c]

Si no está permitido devolver la misma proporción más de una vez (400/400 = 40/40 = 4/4), use f n=nub[...para filtrarlos.

Devuelve una lista de pares. Una lista de pares de dos elementos cuesta lo mismo. Una lista de fracciones reales requeriría importación Data.Ratioo calificación completa Data.Ratio.%(que también colisiona con la %función definida aquí)

casos de prueba (con nub):

Prelude Data.List> f 80
[(10,70),(16,64),(20,60),(30,50),(40,40),(50,30),(60,20),(64,16),(70,10)]
Prelude Data.List> f 147
[(49,98),(98,49)]
Prelude Data.List> f 500
[(10,490),(20,480),(30,470),(40,460),(50,450),(60,440),(70,430),(80,420),(90,410
),(100,400),(110,390),(120,380),(130,370),(140,360),(150,350),(160,340),(170,330
),(180,320),(190,310),(200,300),(210,290),(220,280),(230,270),(240,260),(250,250
),(260,240),(270,230),(280,220),(290,210),(300,200),(310,190),(320,180),(330,170
),(340,160),(350,150),(360,140),(370,130),(380,120),(390,110),(400,100),(410,90)
,(420,80),(430,70),(440,60),(450,50),(460,40),(470,30),(480,20),(490,10)]

sin golf y comentado :

import Data.List

-- haystack ! needle - the haystack with the needle removed, wrapped in a single-element list
--                       or an empty array if the haystack does not start with the needle

x ! [] = [x]                        -- case: empty needle = match with the full haystack left
(h:hs) ! (n:ns) | h == n = hs ! ns  -- case: needle and haystack match
_ ! _ = []                          -- case: no match

-- haystack % needle - the haystack with the needle removed 
--                       for all positions of the needle in the haystack

a@(h:hs) % b = a ! b ++ map (h:) (hs%b) -- either remove the needle here, or elsewhere
a % b = a                               -- empty haystack cannot be popped

-- f - the function we are interested in

f total = [ (num, total - num) 
          | num   <- [1 .. total-1],            -- for each numerator in range
            i     <- inits $ show num,          -- for each postfix of the numerator
            sub   <- init $ tails i,            -- for each prefix of the postfix except the last (empty) one
            sub /= show num,                    -- that isn't equal to the numerator
            reNum <- show num % sub,            -- remove the substring from the numerator
            reDiv <- show (total - num) % sub,  -- as well as from the denominator.

                                                -- the resulting ratios must be equal by value:
            (read reNum) ^ (total - num) == (read '0':reDiv) * num]
John Dvorak
fuente
puedes cambiar ';' a las nuevas líneas (en el código de golf)? no cambia el conteo de bytes y hace que el código sea mucho más legible
orgulloso haskeller
@proudhaskeller Eso es deliberado; Me gusta tener menos líneas en el código de golf. Además, las longitudes de línea están más equilibradas de esta manera. ¿Crees que debería cambiar?
John Dvorak
haga lo que quiera, pero me gustaría que las líneas se extendieran para poder leer el código mejor (en lugar de recurrir al código no protegido)
orgulloso Haskeller
¿Estás bien con la versión actual? Desafortunadamente, no puedo dividir la última línea (excepto en los espacios, lo que mataría la legibilidad)
John Dvorak
como dije, haz lo que quieras
orgulloso Haskeller
1

Python 2 - 236

n=input()
r=range
f=float
l=len
for a in r(n):
 A=`a`;B=`n-a`
 for i in r(l(A)):
  for j in r(i+1,l(A)+1):
   for u in r(l(B)):
    C=A[:i]+A[j:];D=B[:u]+B[u+j-i:]
    if A[i:j]==B[u:u+j-i]and l(C)*l(D)and f(C)==f(A)/f(B)*f(D):print A,B
Falko
fuente
1

Python 3 - 302

Nota: Debido a dificultades de análisis, no hay fracciones con el número 0 (por lo que no se calculan fracciones utilizando el método correcto).

n=int(input());s=str;r=range
print([[a,b]for a in r(1,n)for b in r(1,a)for i in r(1,n)if i!=a and i!=b and s(i)in s(a)and s(i)in s(b)and s(a).count(s(i))<len(s(a))and s(b).count(s(i))<len(s(b))and not'0'in s(a)and not'0'in s(b)and eval(s(a).replace(s(i),'')+'/'+s(b).replace(s(i),''))==a/b and a+b<=n])

Con n = 80:

[[64, 16]]

Con n = 147

[[64, 16], [65, 26], [95, 19], [98, 49]]

Con n = 500

[[64, 16], [65, 26], [95, 19], [98, 49], [136, 34], [192, 96], [194, 97], [195, 39], [196, 49], [196, 98], [231, 132], [238, 34], [238, 136], [242, 143], [253, 154], [264, 165], [268, 67], [275, 176], [286, 187], [291, 97], [291, 194], [294, 49], [294, 98], [294, 196], [295, 59], [297, 198], [298, 149], [325, 13], [341, 143], [345, 138], [392, 49], [392, 98], [395, 79]]
Decaimiento Beta
fuente
Para n=80esto imprime [[64, 16], [65, 26]], pero obviamente 65 + 26 = 91 > 80.
Ingo Bürk
¿Convertir todos los ifs en un solo grande ifcon ands conectando todas las condiciones? Ahorra bastantes caracteres, creo.
Soham Chowdhury
@Soham Sí, gracias.
Beta Decay
¿Podría incluir también los casos de prueba que he agregado? (¿Y podría ver si encuentra algunos casos de prueba interesantes que debería agregar también?)
error
2
¿Dónde están 10/70, 20/60y 30/50?
John Dvorak