11
\$\begingroup\$

Given a list of fractions, group them so that each group sums to a whole number. This should be done in such a way to maximize the number of non-empty groups.

You may assume a solution exists. Order does not matter, both for the groups and their contents. You may output in any order.

Test Cases

Fractions Groups
1/2, 1/2, 1/2, 1/2 (1/2, 1/2), (1/2, 1/2)
1/2, 1/3, 1/6, 6/7, 8/7 (1/2, 1/3, 1/6), (8/7, 6/7)
5/3, 2/3, 2/3, 1/3, 1/3, 1/3 (1/3, 5/3), (1/3, 2/3), (1/3, 2/3)
9/2, 3/4, 1/12, 7/4, 2/3, 2/3, 7/12 (9/2, 3/4, 1/12, 2/3), (7/4, 2/3, 7/12)
1/10, 1/5, 1/2, 7/10, 1/2 (1/10, 1/5, 7/10), (1/2, 1/2)

IO

You may take fractions as a tuple or list of [numerator, denominator], and output in the same format. You can also use your language's built-in fraction type if it exists.

If there are multiple optimal solutions you may output any of them, some of them, or all of them. Do not output any non-optimal solutions.

\$\endgroup\$
7
  • \$\begingroup\$ Sandbox \$\endgroup\$
    – mousetail
    Commented Feb 21, 2023 at 13:21
  • \$\begingroup\$ Because of floating point errors I think this test case can be also added: 1/10, 1/5, 1/2, 7/10, 1/2 -> (1/10, 1/5, 7/10), (1/2, 1/2) \$\endgroup\$
    – EzioMercer
    Commented Feb 21, 2023 at 13:33
  • \$\begingroup\$ Can we take two lists, one of numerators and one of denominators? \$\endgroup\$ Commented Feb 21, 2023 at 14:14
  • \$\begingroup\$ @CommandMaster I can't really imagine why that would be helpful but sure. Looking forward to see what kind of loophole you find with that format. \$\endgroup\$
    – mousetail
    Commented Feb 21, 2023 at 14:16
  • 2
    \$\begingroup\$ Just as a clarification for everyone: the 4th test case has 3 valid solutions: (1/12, 2/3, 2/3, 7/12), (3/4, 7/4, 9/2), (1/12, 2/3, 3/4, 9/2), (2/3, 7/12, 7/4) and (1/12, 2/3, 7/4, 9/2), (2/3, 3/4, 7/12). \$\endgroup\$
    – Arnauld
    Commented Feb 21, 2023 at 15:50

5 Answers 5

6
\$\begingroup\$

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

Try it online!

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[]
}                          //
\$\endgroup\$
2
  • \$\begingroup\$ So the eval is just a way to avoid the braces and the return? \$\endgroup\$
    – Jonah
    Commented Feb 22, 2023 at 0:55
  • \$\begingroup\$ @Jonah Yes. It saves 3 bytes here because o is the last thing that gets evaluated by the one liner. Otherwise, we'd have to end it with an extra ;o and it would save only one byte. \$\endgroup\$
    – Arnauld
    Commented Feb 22, 2023 at 1:08
5
\$\begingroup\$

Vyxal, 14 bytes

ṖvøṖÞf'Ṡ¨=⌊;ÞG

Try it Online!

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

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

Try it online!

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

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

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.

\$\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.