# Help me pair my left and right socks!

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 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: 
Pairs:  (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: []

• If we output pairs as single numbers, is it OK if some of those numbers are negative? E.g. in example 3, output [5, 10, -10]. Dec 10, 2019 at 13:25
• @RobinRyder No, all pairs of 10 should appear in the same way. I tried to clarify the output rule. Dec 10, 2019 at 23:27
• Are the values still wrapped in inner lists allowed (i.e. [,[-1],[-1]],[[3,3],[3,3],[-2,2],[4,4],[4,4],[-1,1]] - this is the current output of the Jelly answer, or the output of the Japt answer without its second line), or is it mandatory to simplify it (like the Japt answer did with its second line)? Dec 11, 2019 at 13:38
• @KevinCruijssen It's allowed. Dec 11, 2019 at 23:09
• Can we have a non-consistent order of the outputs, as long as it's clear which ones are the Pairs and which ones are the Leftovers? I.e. can one test case result in [[,], [[2,2]]] ([Leftovers, Pairs]) while another test case results in [[[3,3],[-2,2]], [,,]] (Pairs, Leftovers])? Dec 12, 2019 at 9:16

# 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,1], [-2,2], [3,3]]).

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

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)

• I think é is redundant, .¡g should be enough ? Dec 12, 2019 at 8:58
• @AZTECCO Unfortunately no, since the groups remain in the same order in 05AB1E. You can try removing it in the Test suite TIO to see that the output of some of the test cases are then reversed, while others aren't. EDIT: I guess I could remove it, since it's clear that the paired integers are the Pairs and the single wrapped integers are the Leftovers, but a non-consistent output-order seems a bit weird imo. Dec 12, 2019 at 9:12
• Oh.. I see, there are some subtle differences between the languages, anyway seems like they have a similar structure. Dec 12, 2019 at 17:53

# 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


# 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,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,  # 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
}
}

• you can use {} in place of c() and sum(p|1) instead of length(p) to save 2 bytes. Dec 10, 2019 at 15:11
• @Giuseppe Thanks! I golfed it 2 bytes further: here, any(p) does what I need, since all entries are non-zero and I just want to check that p is not the empty vector. Dec 10, 2019 at 15:15

# Japt, 2831 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

• It's allowed to output pairs as [[-1,1], [3,3], ...], so the second line is not necessary. Dec 11, 2019 at 23:16
• @Bubbler thanks! This saves a lot Dec 12, 2019 at 0:02
• Sorry to be the bringer of bad news again, but this seems to fail for [3, 3, -2, 2, 2, 2, 5] [1, 2]. It pairs the remaining 2s with null, instead of being in the Leftovers-pile. Dec 12, 2019 at 7:40
• @Kevin Cruijssen thanks for the patience ! Your help is always appreciated Dec 12, 2019 at 8:52

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

# 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

• Save one with Ġị$ in place of Ṡ¹ƙ$ TIO May 29, 2021 at 14:15
• @JonathanAllan thanks! May 29, 2021 at 18:36

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


# 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):
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):
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

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

# 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;[b,c]}


Try it online!