3
\$\begingroup\$

Help! I printed a bunch of rational numbers with no spaces or other delimiters other than the / in the fractions. There is, however, good news! All the numbers are positive. There are no improper fractions, every numerator is less than its denominator and any integers are represented directly, not as fractions. Any non-integers greater than 1 are represented as an integer followed by a fraction. Every fraction is reduced to lowest terms, no numerator and denominator have any common factors other than 1.

Using this information, and given a string that I've printed, I need you to tell me what the original numbers could have been. If there are multiple possibilities, I want to know all of them.

Examples

given as input => output.

1 => 1

1/2 => 1/2

12/3 => 1,2/3 and 1 2/3 (or, equivalently, 5/3)

2/34 => 2/3,4 (cannot be 2/34 because 2 and 34 share a factor of 2)

12/35 => 12/35 and 1 2/35 and 1,2/35 and 1,2/3,5

12/345/678/9 => 1,2/3,4,5/6,7,8/9 and 5/3,29/6,71/9 and 5/3,45/67,8/9 and ...

Rules

You can assume there is at least one valid way to delimit the input.

Your results can contain improper or mixed fractions, you can represent 5/3 as 5/3 or 1 2/3. You can use any kind of delimiters, as long as each type of delimiter (start and end of a list, between numbers, between integer and fraction in a mixed fraction, between numerator and denominator in a fraction) is unique and consistent. You can take input from stdin, or function parameters, or command line options. You can print your results, or return them from a function, or even just leave them in a variable.

\$\endgroup\$
6
  • 2
    \$\begingroup\$ I was following this challenge fine up until the part where the input could contain multiple /s. I think this addition is confusing and poorly explained. Not to mention I think the challenge is more interesting without it. \$\endgroup\$
    – Wheat Wizard
    Commented Apr 14, 2020 at 3:52
  • \$\begingroup\$ @AdHocGarfHunter the input is just one or more numbers concatenated. some of the numbers are integers, some fractions, some mixed integer + fraction. \$\endgroup\$
    – Sparr
    Commented Apr 14, 2020 at 4:02
  • 2
    \$\begingroup\$ Sorry I do understand it. I just am critical of it. \$\endgroup\$
    – Wheat Wizard
    Commented Apr 14, 2020 at 4:04
  • 3
    \$\begingroup\$ It would've been a lot easier if you only required one output.. \$\endgroup\$
    – user92069
    Commented Apr 14, 2020 at 4:22
  • 3
    \$\begingroup\$ It would also be much easier without mixed fractions. \$\endgroup\$ Commented Apr 14, 2020 at 5:31

2 Answers 2

3
\$\begingroup\$

Haskell, 480 bytes

c""=[]
c('/':x)=c x
c x|(f,b)<-span(/='/')x=f:c b
i x[]=[[x]]
i x(y:z)=(x:y):z
s[x]=[[[x]]]
s(x:y)=[p|s<-s y,p<-[i x s,[x]:s]]
m[[b],[c]]=[[b++'/':c]]
m[[a,b],[c]]=[[a++'+':b++'/':c],[a,b++'/':c]]
m([b]:((c:d:e):f))=map((b++'/':c):)$m$(d:e):f
m([a,b]:((c:d:e):f))=[p++s|s<-m((d:e):f),p<-m[[a,b],[c]]]
m((x:y):z)=map(x:)$m$y:z
l=length
o i=[o|s<-sequence$map s$c$i,and[n<d&&gcd n d==1|i<-[1..l s-1],
 let[n,d]=read<$>[last$s!!pred i,s!!i!!0]],
 and[l(s!!i)>1|i<-[1..l s-2]],o<-m s]

Try it online!

Haskell, 650 bytes

chunks""=[]
chunks('/':xs)=chunks xs
chunks xs|(front,back)<-span(/='/')xs=front:chunks back

insert x[]=[[x]]
insert x(y:ys)=(x:y):ys

splits[x]=[[[x]]]
splits(x:xs)=[p|s<-splits xs,p<-[insert x s,[x]:s]]

merges[[b],[c]]=[[b++'/':c]]
merges[[a,b],[c]]=[[a++'+':b++'/':c],[a,b++'/':c]]
merges([b]:((c:d:e):f))=[(b++'/':c):s|s<-merges$(d:e):f]
merges([a,b]:((c:d:e):f))=[p++s|
 s<-merges((d:e):f),p<-merges[[a,b],[c]]]
merges((x:xs):ys)=map(x:)$merges$xs:ys

origins input=[m|s<-sequence$map splits$chunks$input,
 and[length(s!!i)>1|i<-[1..length s-2]],
 and[n<d&&gcd n d==1|i<-[1..length s-1],
 let[n,d]=read<$>[last$s!!pred i,s!!i!!0]],m<-merges s]

Try it online!

\$\endgroup\$
3
\$\begingroup\$

JavaScript (V8), 188 185 bytes

f=([c,...x],y='')=>c?f(x,y+c)-f(x,y+[,c])-f(x,y+' '+c):y.split`,`.some(e=>e.replace(/(?:[1-9]\d* ?)??(?:([1-9]\d*)\/([1-9]\d*))?$/,g=(_,a,b)=>+a>=b|!_?1:a?g(1,b%a,a):b-1||''))||print(y)

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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