Help me pair my left and right socks!

Question

Inspired by Help me pair my socks, and the fact that I have some pairs of socks where the left sock is distinct from the right.

---

Background

Again, I have a huge pile of socks. And a machine that can give the list of labels of the socks for me. This time, the labels follow these rules:

• Some socks have left and right versions. In this case, left socks are labelled -n and right socks are labelled n, where n is a unique positive integer. The list of such socks will be explicitly given to you.
• The others don't have such a thing, and they just match themselves. All socks of this type are simply labelled n (no negative labels).

An example pile would look like this:

[3, 3, -2, 4, -1, -1, 1, 4, 4, 3, 2, 3, -1, 4, 4]

where 1 and 2 have left and right versions. Then the pairs and leftovers are:

pairs: {3: 2, 4: 2, 1: 1, 2: 1} or [1, 2, 3, 3, 4, 4]
leftovers: {4: 1, -1: 2} or [-1, -1, 4]

Note that two -1s don't make a pair because both are left socks.

Challenge

Given the pile of socks and the list of sock labels having L/R versions, output the pairs that can be made from the pile, and leftovers that are not part of any pairs.

Input and output

You can assume the following for input:

• Zeros won't appear in either list.
• L/R labels are unique and all positive, but possibly not sorted.
• Negative numbers that are not part of L/R labels won't appear in the pile.

Both outputs can be represented as either a mapping type (label to count) or a flat list (each item appearing once per count). You can output in following ways:

• Pairs can be represented as either a pair (3, 3) / (-1, 1) or a single number 3 / 1 / -1, or a mixture of both. But the same pairs should be represented in the same way in a single run, e.g. outputting [3, (3, 3)] or [(-1, 1), (1, -1)] or [1, -1] is not allowed.
• For both pairs and leftovers, a pair and single number can be wrapped in any kind of containers, e.g. singleton arrays can be used to represent a single leftover.
• For both pairs and leftovers, the order of items is not important.
• If you use a mapping type, zero-count items are allowed, even the ones not in the pile of socks.

Scoring and winning criterion

Standard code-golf rules apply. The shortest code in bytes wins.

Test cases

Pile: [3, 3, -2, 4, -1, -1, 1, 4, 4, 3, 2, 3, -1, 4, 4]
LR: [1, 2]
Pairs: [1, 2, 3, 3, 4, 4]
Leftovers: [-1, -1, 4]

Pile: [1, 1, 2, 2]
LR: [1]
Pairs: [2] (two right 1's and two simple 2's, so only 2's make a pair)
Leftovers: [1, 1]

Pile: [5, -10, 5, 10, -10, 10]
LR: [10, 20]
Pairs: [5, 10, 10]
Leftovers: []

Pile: [-6, 7, -9, 3, 4, -6, 4, -9, 8]
LR: [6, 9, 4]
Pairs: []
Leftovers: [-6, 7, -9, 3, 4, -6, 4, -9, 8]

Pile: []
LR: [1, 2]
Pairs: []
Leftovers: []

Answer 1

05AB1E, 40 27 bytes

.¡Ä}εDÄIåài{γζðδKë2ô]€`é.¡g

Inputs are in the order Pile, LR and outputs in the order Leftovers, Pairs in the format ([[1],[2],[3]], [[1,1], [-2,2], [3,3]]).

-13 bytes by porting @AZTECCO's Japt answer, so make sure to upvote him!

Try it online or verify all test cases.

Explanation:

.¡ }              # Group the (implicit) input integer-list `Pile` by:
  Ä               #  Their absolute values
    ε             # Then map each group to:
          i       #  If
       Iåà        #  any values of the second input-list `LR`
     DÄ           #  is in the current group's absolute values:
           {      #   Sort the values in the group
            γ     #   And then group it on subsequent equal values
             ζ    #   Zip/transpose to create pairs of positive & negative values,
                  #   with space as default filler if the lists are of unequal length
              ðδK #   And remove all those spaces
          ë       #  Else:
           2ô     #   Split split the group into parts of size 2
    ]             # Close the if-else statement and map
     €`           # Flatten each inner list once to remove the groups again
       é          # Sort each inner list by length
        .¡g       # And also group by length
                  # (after which this result is output implicitly as result)

Answer 2

APL (Dyalog Unicode), 62 bytes (SBCS)

,⌿⎕{⍺∊⍺⍺:((∊|⍴¨⍺××)n)(⍺/⍨0⌈2÷⍨≢⍵↓⍨n←⍺÷⍨+/⍵)⋄/∘⍺¨⌽0 2⊤≢⍵}⌸⍨∘|⍨⎕

Try it online!

The initial "straightforward" version was around 76 bytes long; folks at The APL Orchard helped me golf it substantially to the snippet above. Thanks!

How does it work?

Explanations written for the original "straightforward" version, not for the most golfed version above.

At a high level, the ⌸ Key operator groups items from the pile such that we get an absolute-valued item as a key on the left and an array of all its occurences (with or without a minus sign) on the right.

┌─┬──────────┐
│3│3 3 3 3   │
├─┼──────────┤
│2│¯2 2      │
├─┼──────────┤
│4│4 4 4 4 4 │
├─┼──────────┤
│1│¯1 ¯1 1 ¯1│
└─┴──────────┘

Then we essentially do:

if the key is in the list of LRs:
    compute leftovers and pairs for LRs
else:
    compute leftovers and pairs for normal socks

After doing that for each row, we concatenate the columns (given to us in leftovers, pairs order) to a single array each and return those two arrays as a final result.

Leftovers for LRs:

We sum the items on the right and divide them by the key; this gives us a number of leftovers; we absolute-value that (since it can be negative, eg. -1 -1 1 -1 -> -2) and then replicate the key (with the right sign applied) that many times.

¯2 ¯2 2 ¯2   ⍝ +/ sum:
¯4           ⍝ ÷2 divide by key:
¯2           ⍝ |  absolute value:
2            ⍝ = number of times to replicate

¯2           ⍝ ×  get sign
¯1           ⍝ ×2 multiply by key:
¯2           ⍝ = item to replicate

2/¯2 ---> ¯2 ¯2

Pairs for LRs:

We sum the items on the right, divide that by the key and get the absolute value. That gives us number of leftovers. We subtract that from the original number of items, which gives us the number of paired items. We divide that by two to get the number of pairs. We repeat the key that many times (it's guaranteed to be positive).

¯2 ¯2 2 ¯2   ⍝ +/    sum:
¯4           ⍝ ÷2    divide by key:
¯2           ⍝ |     absolute value:
2            ⍝ (≢⍵)- subtract from count of items:
2            ⍝ ÷2    divide by 2:
1            = number of times to replicate

1/2 ---> 2

Leftovers for normal socks:

We count the items, take remainder after division by 2 (either 0 or 1 odd sock can be the leftover). By problem definition we're guaranteed this number is not negative. We repeat the key that many times.

2 2 2        ⍝ ≢  count:
3            ⍝ 2| mod by 2:
1            ⍝ = number of times to replicate

1/2 ---> 2

Pairs for normal socks:

We count the items, divide by two and round down. We repeat the key that many times.

2 2 2        ⍝ ≢  count:
3            ⍝ ÷2 divide by 2:
1.5          ⍝ ⌊  round down
1            ⍝ = number of times to replicate

1/2 ---> 2

Answer 3

R, 138 134 138 bytes

-2 bytes thanks to Giuseppe; +4 bytes to adhere to the output format

f=function(p,l,a={},b=a,z=p[1],w=abs(z))`if`(any(p),`if`(m<-match(z-2*z*w%in%l,y<-p[-1],0),f(y[-m],l,c(a,w),b),f(y,l,a,c(b,z))),list(a,b))

Try it online!

Recursive function.

Takes the first sock z off the pile, and searches the pile for either z or -z depending on whether w=abs(z) is in LR. If a match is found, adds w to the list of pairs and removes both socks from the pile before recursing, else adds z to the list of leftovers and recurses.

Ungolfed:

# p is pile of socks
# l is vector of LR socks
# a will be vector of pairs
# b will be vector of leftovers
f = function(p, l, a={}, b=a, z=p[1],  # initialize a and b as NULL; z is first sock of pile
               w=abs(z)}
  if(any(p)){                          # check that p is not empty (would mean end of recursion)
    y <- p[-1]                         # y is all socks except the first
    m <- match(z - 2*z*w%in%l,         # look for either z or -z depending on whether w=abs(z) is in l
             y, 0)                     # find position of first match in y; if no match is found, return 0
    if(m){                             # if a match was found
      f(y[-m], l, c(a, w), b)          # append w to a, remove the matching sock from y, and recurse
      } else {
        f(y, l, a, c(b, z))            # else append z to b and recurse
      }
    } else {
      list(a,b)                        # when p is empty, return a and b
  }
}

Answer 4

Japt, 28 31 23 bytes

üa c_ca øV ?ZüÎyf:ZòÃül

Try it

Takes input as pile, labels.
Returns leftovers, every pair list.

üa                    group by same absolute value        
   c_           Ã     for each group:
     ca øV ?              if labeled (using absolute values)
        ZüÎyf          - group by sign and transpose (saving only truthy values)
            :Zò        :  else slice every 2 elements
                ül    group the result by length

g1_cg1 no needed

Answer 5

JavaScript (ES6), 85 bytes

Takes input as (pile)(lr), where pile is an array and lr is an object.

Returns the pairs as a list and the leftovers as an object which may contain zero-count items.

a=>L=>[a.filter(x=>s[i=L[A(x)]?-x:x]?s[i]--:!(s[x]=-~s[x]),s={},A=Math.abs).map(A),s]

Try it online!

---

JavaScript (ES6), 99 bytes

Takes input as (pile)(lr), where pile is an array and lr is an object.

Returns two lists.

a=>L=>[a.filter(x=>~(i=s.indexOf(L[A(x)]?-x:x))?s.splice(i,1):!s.push(x),s=[],A=Math.abs).map(A),s]

Try it online!

Answer 6

Jelly, 25 23 bytes

AĠị$ŒHAf⁹Ɗ?Z$ƙ$ẎL=¥ƇⱮؽ

Try it online!

A dyadic link taking the socks as its left argument and LR list as its right. Returns a list of lists with the leftovers as the first sublist (each wrapped on its own in a list) and the pairs as the second sublist.

Thanks to @JonathanAllan for saving a byte!

Explanation

              $          | Following as a monad:
A           $ƙ           | - For each group of the sock list defined by the absolute of the sock list, do the following as a monad:
         Ɗ?              |   - If the following is non-empty:
      A                  |     - Absolute
       f⁹                |     - Filtered to keep only elememts in LR list
   $                     |   - Then:
 Ġị                      |      - Split into groups based on sign
    ŒH                   |   - Else: split into two (almost) equal halves
           Z             |   - Transpose
                Ẏ        | Join outermost lists together
                   ¥ƇⱮؽ | Filter the list using the following as a dyad and each of [1, 2] as the right argument:
                 L       | - Length
                  =      | - Equals right argument

Answer 7

Perl 5, 151 bytes

sub f{
  $_="@{[sort{abs$a<=>abs$b}sort@{+pop}]}";
  ($p,@p)=sub{push@p,$1;''};
  for$l(@_){1while s/-($l) +$l\b/&$p/e}
  s/\b(\d+) \1\b/$1~~\@_?$&:&$p/ge;
  "@p",$_
}

Try it online!

...151 bytes with \n\s+ removed.

Answer 8

Zsh, 179 177 bytes

typeset -A p l
for x (`<&0`)((l[$x]++))
for k;((p[$k]=l[$k]<l[-$k]?l[$k]:l[-$k],l[$k]-=p[$k],l[-$k]-=p[$k]))
a=({,-}$^@)
for k (${(k)l:|a})((p[$k]=l[$k]/2,l[$k]%=2))
typeset p l

Try it online!

Takes the sock pile on stdin, and the achiral pairs as arguments.

Due to Zsh's lack of filtering and mapping tools, we simply loop over the pile incrementing to create a sock->count map. Thankfully zero-count items are allowed; otherwise this would probably be in the 220-byte range, since filtering by value isn't easily done.

typeset -A p l            # declare p, l as associative arrays
for x (`<&0`)((l[$x]++))  # for each sock in the pile, increment that key of the leftover array
for k; {                  # for each argument (an achiral pair)
  ((p[$k]=l[$k]<l[-$k]?l[$k]:l[-$k]))  # set the paired array to the minimum of the l/r socks
  ((l[$k]-=p[$k],l[-$k]-=p[$k]))       # decrement the leftovers we just paired
}
a=({,-}$^@)               # if our achiral pairs were (2 3), set a=(2 -2 3 -3)
for k (${(k)l:|a})        # take the keys of the leftovers, remove all elements of a
  ((p[$k]=l[$k]/2,l[$k]%=2))    # divmod gets us the pairs and leftovers for the chiral socks
typeset p l               # using typeset to print the current definitions is shorter than
                          # using something like '<<<${(kv)p},${(kv)l}'

Answer 9

Python 3.7, 183 Bytes

Try it online! Link includes uncommented version of code with the five test cases.

def f(p,l):
 a,b=[],[]          #a = pairs, b = loners
 while p:           #iterate through pile
  i=p.pop(0)        #remove and look at first sock in pile
  n=abs(i)          #Prepare to compare abs(i) to LR list
  #If there is a +ve/-ve pair from LR list
  if(-i in p)*(n in l): 
   a+=n,            #Add to pairs
   p.remove(-i)     #Remove other half of pair from the pile
  #If there is a +ve/+ve pair not from LR list
  elif(n in p)*(not n in l):
   a+=n,            #Add to pairs
   p.remove(i)      #Remove other half of pair from the pile
  #Otherwise, add sock to loner list
  else:b+=i,
 return a,b         #Return the completed lists

This is my first attempt at a code golf challenge so feel free to comment on any obvious optimizations I have missed.

Cheers

Answer 10

Charcoal, 58 bytes

Ｉ⟦↔Φθ⎇№η↔ι›№…θκ±ι№…θκι﹪№…θκι²Φθ⎇№η↔ι›№…θ⊕κι№θ±ι›﹪№θι²№…θκι

Try it online! Link is to verbose version of code. Outputs two double-spaced lists of newline-separated socks in a reproducible but unobvious order. Explanation:

Ｉ⟦

Cast both lists of socks to string for implicit print and double-space between the lists.

↔Φθ

Find the matched socks and print their absolute values so that we don't mix left and right socks in the output.

⎇№η↔ι

Is this a self-pairing sock?

›№…θκ±ι№…θκι

If not then it matches if there have been more opposite socks in the list so far (not including this sock, so at least as many opposite socks including this sock).

﹪№…θκι²

If it is then it matches if there have been an odd number of this type of sock so far (not including this sock). (If there are an odd number in total then this sock is actually matched against the next sock of this type.)

Φθ

Find the mismatched socks.

⎇№η↔ι

Is this a self-pairing sock?

›№…θ⊕κι№θ±ι

If not it is mismatched if the number of this type of sock so far (including this sock) is greater than the total number of opposite socks.

›﹪№θι²№…θκι

If it is then it is mismatched if this is the first of a total number of odd socks of this type.

Explanation for which socks get output as (mis)matches:

[[3, 3, -2, 4, -1, -1, 1, 4, 4, 3, 2, 3, -1, 4, 4], [1, 2]]

• The 1 gets output as a match for the first -1 and the second and third -1 are output as mismatches.
• The 2 gets output as a match for the -2.
• The second and fourth 3s get output as matches for the first and third 3s.
• The second and fourth 4s get output as matches for the third and fifth 4s, while the first 4 is a mismatch.

Answer 11

Ruby, 143 95 bytes

->a,l,*b{c=[];(s=a.index [w=a.pop,-w][l.count z=w.abs])?(a.slice!s;b<<z):c<<w while a[0];[b,c]}

Try it online!