| Bytes | Lang | Time | Link |
|---|---|---|---|
| 227 | Python3 | 251006T181850Z | Ajax1234 |
| 022 | 05AB1E | 230222T080923Z | Kevin Cr |
| 176 | JavaScript ES7 | 230221T151309Z | Arnauld |
| 092 | Charcoal | 230222T005919Z | Neil |
| 148 | Wolfram Language Mathematica | 230221T172833Z | ZaMoC |
| 014 | Vyxal | 230221T134749Z | lyxal |
Python3, 227 bytes
def f(n):
q,r=[(n,[[]])],[]
for n,b in q:
if[]==n:r+=[b[:-1]];continue
q+=[(n[:i]+n[i+1:],b[:-1]+[U,[]]if(U:=b[-1]+[n[i]])and int(Z:=sum(a/b for a,b in U))==Z else b[:-1]+[U])for i in range(len(n))]
return max(r,key=len)
05AB1E, 24 22 bytes
œ€.œ€`éʒε.EOT.òDïQ}P}θ
-2 bytes by taking the input as a list of strings "a/b" instead of list of pairs [a,b].
Try it online or verify all test cases.
Explanation:
œ # Get all permutations of the (implicit) input-list
€.œ # Get all partitions of each permutation
€` # Flatten it one level down to a single list of partitions
é # Sort it by length (shortest to longest)
ʒ # Filter this list of partitions by:
ε # Map over each part of this partition:
.E # Evaluate each inner string as Elixir to get the decimals
O # Sum them together
T.ò # Round it to 10 decimal values to fix floating point errors
DïQ # Check that it's an integer:
D # Duplicate
ï # Cast the copy to an integer (floor for positive integers)
Q # Check if the two are equal
}P # After the map: check if all parts in this partition were truthy
}θ # After the filter: pop and leave the last/longest valid partition
# (which is output implicitly as result)
JavaScript (ES7), 176 bytes
Expects a list of [numerator, denominator] pairs.
a=>eval("for(o=n=a.length,q=n**n;q--;)o[(p=a.map((_,j)=>a.filter((_,i)=>!(q/n**i%n^j))).filter(a=>a+a)).length]||p.some(b=>b.map(([p,q])=>[P=P*q+p*Q,Q*=q],P=0,Q=1)|P%Q)?o:o=p")
Commented
This is a version without eval() for readability.
a => { // a[] = input list of fractions
for( // main loop:
o = // o[] = output, initially not an array
n = a.length, // n = length of a[]
q = n ** n; // q = counter, initialized to n ** n
q--; // stop once q = 0 has been processed
) //
o[ // test o[], using the length of p[]:
( p = // p[] = partition
a.map((_, j) => // for each element at index j in a[]:
a.filter((_, i) => // for each element at index i in a[]:
!( // keep this entry if
q / n ** i % n // floor(q / n ** i) mod n
^ j // is equal to j
) //
) // end of filter()
).filter(a => a + a) // end of map(); remove empty slots
).length // get the final length of p[]
] || // abort if p[] is longer than o[]
p.some(b => // for each list of fractions b[] in p[]:
b.map(([p, q]) => // for each fraction [p, q] in b[]:
[ // we add p/q to P/Q by:
P = P * q + p * Q, // updating the numerator P
Q *= q // updating the denominator Q
], //
P = 0, Q = 1 // start with P/Q = 0/1
) // end of map()
| P % Q // trigger some() if Q is not a divisor of P
) ? 0 // end of some(); do nothing if truthy
: o = p; // otherwise, update o[] to p[]
// (implicit end of for)
return o // return o[]
} //
Charcoal, 92 bytes
≔E⪪S,⁺⟦ικ⟧I⪪ι/θ≔ΠEθ§ι³ηFθ⊞ι×÷η⊟ι⊟ιWθ«≔ΦEX²LθΦθ﹪÷κX²ν²∧κ¬﹪ΣEκ§μ²ηι≔§ι⌕EιLκ⌊EιLκι≔⁻θιθ⟦⪫Eι§κ⁰,
Try it online! Link is to verbose version of code. Explanation:
≔E⪪S,⁺⟦ικ⟧I⪪ι/θ
Input the fractions and split them into numerator and denominator.
≔ΠEθ§ι³η
Calculate a common denominator that will work for all of the fractions.
Fθ⊞ι×÷η⊟ι⊟ι
Calculate the equivalent numerator for each fraction.
Wθ«
Repeat until there are no more fractions to process.
≔ΦEX²LθΦθ﹪÷κX²ν²∧κ¬﹪ΣEκ§μ²ηι
Get all of the subsets of the fractions but filter out the empty set and any set whose sum of numerators isn't a multiple of the common denominator.
≔§ι⌕EιLκ⌊EιLκι
Find the shortest such subset.
≔⁻θιθ
Remove the shortest subset from the remaining fractions.
⟦⪫Eι§κ⁰,
Output the original fractions from the shortest subset.
Wolfram Language (Mathematica), 148 bytes
Last@Sort@(y=Flatten)[(a=#;(x=Select)[a~TakeList~#&/@x[Range@n~Tuples~#&~Array~(n=Length@a)~y~1,Tr@#==n&],Tr@Mod[Tr/@#,1]==0&])&/@Permutations@#,1]&
Vyxal, 14 bytes
ṖvøṖÞf'Ṡ¨=⌊;ÞG
Times out for anything more than 5 fractions if you're lucky. Don't even bother giving it the third and fourth test case.
Inputs as a list of fraction objects. Due to technical limitations, this is done with the a flag for convenience.
Explained
ṖvøṖÞf'Ṡ¨=⌊;ÞG # We'll call the length of the list N so we can see why this takes so long
Ṗ # Permutations of the input - returns a list of N! items
vøṖ # To each of the N! permutations, get all possible partitions. Each permutation has 2^(N-1) partitions, so there are now N! * 2^(N-1) sublists but still N! items
Þf # Flatten the entire thing by one level. This iterates over each of those N! * 2^(N-1) sublists.
' ; # From those partitions of permutations, keep only those where: (also iterating over each of those N! * 2^(N-1) items)
Ṡ # Summating each partition
¨=⌊ # is invariant under flooring
ÞG # Get the longest remaining item.