# Whole Number Groups

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.

• Sandbox Commented Feb 21, 2023 at 13:21
• 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) Commented Feb 21, 2023 at 13:33
• Can we take two lists, one of numerators and one of denominators? Commented Feb 21, 2023 at 14:14
• @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. Commented Feb 21, 2023 at 14:16
• 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). Commented Feb 21, 2023 at 15:50

# 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[]
}                          //

• So the eval is just a way to avoid the braces and the return? Commented Feb 22, 2023 at 0:55
• @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. Commented Feb 22, 2023 at 1:08

# 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.


# 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!

# 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].

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)


# Charcoal, 92 bytes

≔Ｅ⪪Ｓ,⁺⟦ικ⟧Ｉ⪪ι/θ≔ΠＥθ§ι³ηＦθ⊞ι×÷η⊟ι⊟ιＷθ«≔ΦＥＸ²ＬθΦθ﹪÷κＸ²ν²∧κ¬﹪ΣＥκ§μ²ηι≔§ι⌕ＥιＬκ⌊ＥιＬκι≔⁻θιθ⟦⪫Ｅι§κ⁰,


Try it online! Link is to verbose version of code. Explanation:

≔Ｅ⪪Ｓ,⁺⟦ικ⟧Ｉ⪪ι/θ


Input the fractions and split them into numerator and denominator.

≔ΠＥθ§ι³η


Calculate a common denominator that will work for all of the fractions.

Ｆθ⊞ι×÷η⊟ι⊟ι


Calculate the equivalent numerator for each fraction.

Ｗθ«


Repeat until there are no more fractions to process.

≔ΦＥＸ²ＬθΦθ﹪÷κＸ²ν²∧κ¬﹪ΣＥκ§μ²ηι


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.

≔§ι⌕ＥιＬκ⌊ＥιＬκι


Find the shortest such subset.

≔⁻θιθ


Remove the shortest subset from the remaining fractions.

⟦⪫Ｅι§κ⁰,


Output the original fractions from the shortest subset.