13
\$\begingroup\$

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: [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: []
\$\endgroup\$
  • \$\begingroup\$ 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]. \$\endgroup\$ – Robin Ryder Dec 10 '19 at 13:25
  • \$\begingroup\$ @RobinRyder No, all pairs of 10 should appear in the same way. I tried to clarify the output rule. \$\endgroup\$ – Bubbler Dec 10 '19 at 23:27
  • \$\begingroup\$ Are the values still wrapped in inner lists allowed (i.e. [[4],[-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)? \$\endgroup\$ – Kevin Cruijssen Dec 11 '19 at 13:38
  • 1
    \$\begingroup\$ @KevinCruijssen It's allowed. \$\endgroup\$ – Bubbler Dec 11 '19 at 23:09
  • \$\begingroup\$ 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 [[[1],[1]], [[2,2]]] ([Leftovers, Pairs]) while another test case results in [[[3,3],[-2,2]], [[2],[2],[5]]] (Pairs, Leftovers])? \$\endgroup\$ – Kevin Cruijssen Dec 12 '19 at 9:16

10 Answers 10

3
\$\begingroup\$

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
  }
}
\$\endgroup\$
  • \$\begingroup\$ you can use {} in place of c() and sum(p|1) instead of length(p) to save 2 bytes. \$\endgroup\$ – Giuseppe Dec 10 '19 at 15:11
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Robin Ryder Dec 10 '19 at 15:15
3
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ I think é is redundant, .¡g should be enough ? \$\endgroup\$ – AZTECCO Dec 12 '19 at 8:58
  • \$\begingroup\$ @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. \$\endgroup\$ – Kevin Cruijssen Dec 12 '19 at 9:12
  • \$\begingroup\$ Oh.. I see, there are some subtle differences between the languages, anyway seems like they have a similar structure. \$\endgroup\$ – AZTECCO Dec 12 '19 at 17:53
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ It's allowed to output pairs as [[-1,1], [3,3], ...], so the second line is not necessary. \$\endgroup\$ – Bubbler Dec 11 '19 at 23:16
  • \$\begingroup\$ @Bubbler thanks! This saves a lot \$\endgroup\$ – AZTECCO Dec 12 '19 at 0:02
  • \$\begingroup\$ 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. \$\endgroup\$ – Kevin Cruijssen Dec 12 '19 at 7:40
  • \$\begingroup\$ @Kevin Cruijssen thanks for the patience ! Your help is always appreciated \$\endgroup\$ – AZTECCO Dec 12 '19 at 8:52
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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}'
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

Jelly, 25 24 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.

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

Charcoal, 58 bytes

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

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:

I⟦

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

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!

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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