4
\$\begingroup\$

Your program should take two lists, where each entry (a positive integer) represents the number of members of some group, as input. These lists will have the same sum but may have different lengths.

Your mission, should you choose to accept it, will be to pair up members of the first list with members of the second, outputting a list of triples of the form (i, j, n) where i is an index into the first input list, j is an index into the second input list, and n is the number of members of group i from the first list who are paired up with a member of group j from the second list.

Every member of both lists should be paired up in this way.

In pseudocode, ∀i, sum(n for (i1, _, n) in output if i1 == i) == first_list[i], and ∀j, sum(n for (_, j1, n) in output if j1 == j) == second_list[j], all(n > 0 and is_integer(n) for (_, _, n) in output), where first_list and second_list are the two input lists, and i and j range over valid indices into the respective inputs.

Your output list must have minimal length among all valid solutions. Zero-based and one-based indexing are both acceptable. Shortest answer wins.

Example

Input: [3, 4, 5] [5, 6, 1]

Possible optimal output: [(0, 1, 3), (1, 1, 3), (1, 2, 1), (2, 0, 5)]

   list 1    list 2     i  j  n
  [ 3 0 0 ] [ 0 3 0 ]  (0, 1, 3)
+ [ 0 3 0 ] [ 0 3 0 ]  (1, 1, 3)
+ [ 0 1 0 ] [ 0 0 1 ]  (1, 2, 1)
+ [ 0 0 5 ] [ 5 0 0 ]  (2, 0, 5)
---------------------
= [ 3 4 5 ] [ 5 6 1 ]

Test cases

The test cases use zero-based indexing.

[3, 4, 5] [5, 6, 1]  ->  [(0, 1, 3), (1, 1, 3), (1, 2, 1), (2, 0, 5)] (length 4 optimal)
[4, 3, 1, 5] [2, 1, 3, 7]  ->  [(1, 2, 3), (2, 1, 1), (0, 3, 4), (3, 3, 3), (3, 0, 2)] (length 5 optimal)
[1, 7, 5] [4, 5, 4]  ->  [(0, 0, 1), (1, 2, 4), (1, 0, 3), (2, 1, 5)] (length 4 optimal)
[4, 5, 5] [3, 7, 4]  ->  [(0, 2, 4), (1, 1, 5), (2, 0, 3), (2, 1, 2)] (length 4 optimal)
[4, 3] [3, 1, 3]  ->  [(0, 0, 3), (0, 1, 1), (1, 2, 3)] (length 3 optimal)
[4, 3, 2] [4, 5]  ->  [(0, 0, 4), (1, 1, 3), (2, 1, 2)] (length 3 optimal)
[] [] -> [] (length 0 optimal)
\$\endgroup\$
13
  • 12
    \$\begingroup\$ I've read this probably 50 times and I'm no closer to understanding the problem than the first time I read it. \$\endgroup\$ Jan 7, 2021 at 18:01
  • 7
    \$\begingroup\$ Here's my attempt to translate the idea of the challenge into a more accessible form: You have some of cats of different breeds and the same total number of dogs of different breeds. You want to split them all into groups, each of consists of cats all of one breed and an equal number of dogs all of one breed. How can you do this with as few groups as possible? \$\endgroup\$
    – xnor
    Jan 7, 2021 at 22:52
  • 3
    \$\begingroup\$ @xnor thank you; I don't know if I'm particularly dense or this is still a difficult challenge to understand, but your explanation finally clicked (after reading it and applying it to the test cases in the question a couple more times). I'd recommend adding xnor's explanation to the challenge, to help other people who just aren't getting it like I wasn't - might help it to get re-opened. I like the challenge (now that I get it) and, though I can't cast reopen votes yet, I've upvoted the challenge in hopes of gaining the attention of those who can :) \$\endgroup\$ Jan 7, 2021 at 23:27
  • 4
    \$\begingroup\$ Also using the terminolgy "pair up" is confusing when we are supposed to output triples. It leads me to think incorrectly that each triple somehow represents a pair. I suggest using terminology that more closely matches xnor's example. Rather than pairing them up, talk about putting them into groups, since each tuple represents a group. \$\endgroup\$
    – Wheat Wizard
    Jan 7, 2021 at 23:37
  • 3
    \$\begingroup\$ I've added a detailed example. Feel free to rollback or edit further. \$\endgroup\$
    – Arnauld
    Jan 8, 2021 at 13:00

2 Answers 2

4
\$\begingroup\$

Scala, 222..187 180 bytes

-7 bytes thanks to user!

x=>y=>{var(a,b,r)=(x,y,Set[Any]())
while(a.sum>0){var?,m=a.max min b.max
var p,q= -1
while(p<0|q<0){if(p<0)p=a indexOf?
if(q<0)q=b indexOf?
? +=1}
a(p)-=m
b(q)-=m
r+=Seq(p,q,m)}
r}

Try it online!

\$\endgroup\$
3
  • 1
    \$\begingroup\$ You can use :+=, but it would be even easier to make it a Set[Any] to use +=180 bytes \$\endgroup\$
    – user
    Jan 11, 2021 at 14:06
  • \$\begingroup\$ @user thank you for your tips :) \$\endgroup\$ Jan 11, 2021 at 18:32
  • \$\begingroup\$ You can save 3 more bytes, but the encoding of the triples would become a bit uglier :( \$\endgroup\$
    – user
    Jan 11, 2021 at 19:02
3
\$\begingroup\$

JavaScript (ES6), 137 bytes

a=>g=(b,k=O=0,o=[],n,c)=>O=O&&!O[k]||a.map((p,i)=>b.map((q,j)=>b[a[i]-=n=p<q?p:q,b[j]-=n,n&&g(b,k+1,[...o,[i,j,c=n]]),a[i]=p,j]=q))|c?O:o

Try it online!

Commented

a =>                           // outer function taking the 1st list a[]
g = (                          // inner function taking:
  b,                           //   the 2nd list b[]
  k = O = 0,                   //   k = length of current solution, O = output
  o = [],                      //   o[] = current solution
  n,                           //   n is a local variable
  c                            //   c is a flag telling whether both lists are cleared
) =>                           //
  O =                          // update O:
    O &&                       //   abort if an output is already defined
    !O[k] ||                   //   and it's shorter than the current solution
    a.map((p, i) =>            //   otherwise, for each value p at position i in a[]:
      b.map((q, j) =>          //     for each value q at position j in b[]:
        b[                     //
          a[i] -=              //       subtract n from a[i]
            n = p < q ? p : q, //       where n = min(p, q)
          b[j] -= n,           //       subtract n from b[j]
          n && g(              //       if n > 0, do a recursive call:
            b,                 //         pass b[] unchanged
            k + 1,             //         increment k
            [ ...o,            //         update the solution o[]
              [i, j, c = n] ]  //         with the triplet [i, j, n]
                               //         and set the flag c
          ),                   //       end of recursive call
          a[i] = p,            //       restore a[i]
          j                    //
        ] = q                  //       restore b[j]
      )                        //     end of inner map()
    ) | c ?                    //   end of outer map(); if c is set:
      O                        //     leave O unchanged
    :                          //   else:
      o                        //     update O to o
\$\endgroup\$

Your Answer

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

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