12
\$\begingroup\$

Reducing fractions the wrong way

In this code-golf challenge you have to find fractions that can be reduced the wrong way but still end up in the same number.

Note: reducing fractions the wrong way does here have an exact definition, see details.

Example:

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

Of course you cannot just strike both 6es but here you still end up with the correct value. In this challenge you have to find examples like this.

Details

You have to write a function/program that accepts one positive integer n as input and outputs/returns a list/array of the fractions in format
numerator1,denominator1,numerator2,denominator2,...

The program has to find out for each fraction a/b with a+b=n and a,b>0 whether it can be reduced the wrong way. (It does not matter whether if it can be reduced in the conventional way or whether there are many possibilities of reductions, it just has to be possible to reduce it the wrong way in at least one way.)

Definition of the wrong way: A fraction can be reduced the wrong way if and only if the same sequence of successive digits appears in a and b and if the value of the fraction stays the same if you remove the substring.

Example: 1536/353 can be 'reduced' to 16/3 but those two values are not equal so you cannot reduce this fraction the wrong way.

Note that this definition of reducing the wrong way can also include fractions that are reduced the right way: 110/10 = 11/1 is within the definition of reducing the wrong way even though it is a valid step.

Scoring

The least number of bytes wins. You can write a function or program that accepts an integer and returns an array or a program that uses stdin/stdout or you can consider n saved in a variable and in the end of the program the list must be saved in an other variable.

Test cases

Please include following testcases (Tell me which ones I should add, I have no idea how many of those fractions there are / how many examples to expect)

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
\$\endgroup\$
  • 3
    \$\begingroup\$ Consider defining a term for "the wrong way", such as "goofy" or "freaky". I think the post would be easier to understand, because readers immediately grok that there must be a definition for the term. \$\endgroup\$ – Michael Easter Sep 14 '14 at 12:06
  • 3
    \$\begingroup\$ What if there are multiple ways to reduce a fraction and only some of them are wrong? 1010/10 = 101/1 && 1010/10 /= 110/1 \$\endgroup\$ – John Dvorak Sep 14 '14 at 12:07
  • 1
    \$\begingroup\$ Variant of projecteuler.net/problem=33 ? \$\endgroup\$ – user80551 Sep 14 '14 at 12:57
  • 1
    \$\begingroup\$ Your second test case (n=147) is incorrect: 49/89 != 4/8. \$\endgroup\$ – Beta Decay Sep 14 '14 at 16:42
  • 1
    \$\begingroup\$ If there's more than one way to reduce a fraction, may we include it multiple times in the result set? \$\endgroup\$ – John Dvorak Sep 14 '14 at 17:58
3
\$\begingroup\$

Python 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],[])

the input must be stored in n, the output will be stored in l.

Test cases:

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]

Should duplicates in the output be forbidden, it gets 10 characters longer:

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}),[])
\$\endgroup\$
3
\$\begingroup\$

Haskell, 207 206 (209?) characters

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]

If it's not allowable to return the same ratio more than once (400/400 = 40/40 = 4/4), use f n=nub[... to filter them out.

Returns a list of pairs. A list of two-element pairs costs the same. A list of actual fractions would require importing Data.Ratio or fully qualifying Data.Ratio.% (which also collides with the % function defined here)

test cases (with 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)]

ungolfed and commented:

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]
\$\endgroup\$
  • \$\begingroup\$ can you change ';' to newlines (in the golfed code)? it doesn't change the byte count and it makes the code much more readable \$\endgroup\$ – proud haskeller Sep 14 '14 at 19:01
  • \$\begingroup\$ @proudhaskeller That's deliberate; I like having fewer lines in the golfed code. Also, the line lengths are more balanced this way. Do you think I should change? \$\endgroup\$ – John Dvorak Sep 14 '14 at 19:03
  • \$\begingroup\$ do whatever you want, but i would like the lines to be spread out so i would be able to read the code better (rather then resorting to the ungolfed code) \$\endgroup\$ – proud haskeller Sep 14 '14 at 19:04
  • \$\begingroup\$ Are you fine with the current version? I can't split the last line, unfortunately (except at spaces, which would kill readability) \$\endgroup\$ – John Dvorak Sep 14 '14 at 19:06
  • \$\begingroup\$ as I said, do whatever you feel like \$\endgroup\$ – proud haskeller Sep 14 '14 at 19:07
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

Python 3 - 302

Note: Due to parsing difficulties, there are no fractions with the number 0 in (so no fractions are calculated using the correct method).

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])

With n=80:

[[64, 16]]

With n=147

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

With 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]]
\$\endgroup\$
  • \$\begingroup\$ For n=80 this prints [[64, 16], [65, 26]], but obviously 65 + 26 = 91 > 80. \$\endgroup\$ – Ingo Bürk Sep 14 '14 at 14:38
  • \$\begingroup\$ Turn all the ifs into a single big if with ands connecting all the conditions? Saves quite a few chars, I think. \$\endgroup\$ – Soham Chowdhury Sep 14 '14 at 15:46
  • \$\begingroup\$ @Soham Yes, it does, thanks! \$\endgroup\$ – Beta Decay Sep 14 '14 at 15:53
  • \$\begingroup\$ Could you also include the testcases I've added? (And could you perhaps see if you find some interesting test cases I should add too?) \$\endgroup\$ – flawr Sep 14 '14 at 16:36
  • 2
    \$\begingroup\$ Where are 10/70, 20/60 and 30/50? \$\endgroup\$ – John Dvorak Sep 14 '14 at 17:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.