32
\$\begingroup\$

Disclaimer: This challenge inspired by me trying to find pairs in a large pile of socks.

Disclaimer: This is looking for a very different process and output to Help me sort my socks!. Please don't claim it as a duplicate until you've read both ;)


So, I have a huge pile of socks. Of course I keep them categorized by compatibility number. Compatible socks, which I can wear together, have the same number. (Of course, every programmer does this).

My super-convenient plot device quickly scans the pile and outputs an array of compatibility numbers for the pile. It looks a bit like this:

[2, 3, 3, 6, 0, 4, 9, 1, 6, 7, 11, 3, 13, 3, 
5, 12, 2, 1, 10, 2, 1, 11, 2, 13, 12, 10, 1, 
7, 0, 0, 12, 12, 6, 2, 13, 6, 10, 0, 0, 12, 
5, 0, 2, 3, 4, 0, 5, 8, 1, 6, 9, 7, 10, 14, 
10, 8, 3, 8, 9, 8, 5, 11, 7, 9, 9, 9, 7, 14, 
4, 2, 8, 14, 3, 11, 12, 14, 7, 13, 11, 13, 4, 
7, 5, 12, 3, 1, 12, 4, 5, 13, 2, 13, 2, 14, 1, 
13, 11, 1, 4, 8]

That's good data, but it's about as much use to me as scanning the pile myself by eye. What I want to know is how many compatible pairs I need to look for, and which are going to be 'odds', which I can discard for now.

In the above example, I am looking for these pairs of socks:

{3=>4, 6=>2, 2=>4, 1=>4, 11=>3, 13=>4, 12=>4, 10=>2, 7=>3, 0=>3, 5=>3, 4=>3, 9=>3, 8=>3, 14=>2}

(4 pairs of number 3, 2 pairs of number 6 etc.)

And these numbers will have 'odd ones out'. When I've found all the pairs for these, I can discard the last one.

[0, 6, 10, 7, 2, 14] 

The challenge

  • Convert a list of compatible numbers to a count of pairs for each number and an array of 'odds'.
    • The pairs will be composed of a data structure (hash, or other) showing how many pairs can be made of each compatibility number (can be skipped if no pairs can be made).
    • The odds will be composed of a list of numbers which occur and odd number of times in the array.
  • The order of the outputs is not significant.
  • The size of my sock pile can, of course, be arbitrarily large.

The Rules

  • It's golf, make it short.
  • No standard loopholes.
  • Use any language you like.
  • Please include a link to an online interpreter.

Test Cases

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

Output:

Pairs: {2=>1, 3=>1, 4=>2, 5=>2}

Odds: [1, 3, 5]


Input: [2, 3, 3, 6, 0, 4, 9, 1, 6, 7, 11, 3, 13, 3, 5, 12, 2, 1, 10, 2, 1, 11, 2, 13, 12, 10, 1, 7, 0, 0, 12, 12, 6, 2, 13, 6, 10, 0, 0, 12, 5, 0, 2, 3, 4, 0, 5, 8, 1, 6, 9, 7, 10, 14, 10, 8, 3, 8, 9, 8, 5, 11, 7, 9, 9, 9, 7, 14, 4, 2, 8, 14, 3, 11, 12, 14, 7, 13, 11, 13, 4, 7, 5, 12, 3, 1, 12, 4, 5, 13, 2, 13, 2, 14, 1, 13, 11, 1, 4, 8]

Output:

Pairs: {3=>4, 6=>2, 2=>4, 1=>4, 11=>3, 13=>4, 12=>4, 10=>2, 7=>3, 0=>3, 5=>3, 4=>3, 9=>3, 8=>3, 14=>2}

Odds: [0, 6, 10, 7, 2, 14]


Input: [1, 2, 1, 2]

Output:

Pairs: {1=>1, 2=>1}

Odds: []


Input: [1,2,3]

Output:

Pairs {}

Odds: [1,2,3]


Input: []

Output:

Pairs: {}

Odds: []

\$\endgroup\$
0

33 Answers 33

1
2
1
\$\begingroup\$

[Python 2.x or 3.x], 52 43 bytes (thanks to isaacg)

Retruns a Python dict with a tuple as value: (<pairs of socks>, <1 if a sock remains; 0 otherwise>). As fas as I understand this comment of the OP, this is now within spec. Please let me know if this is (still) not the case.

lambda s:{c:divmod(s.count(c),2)for c in s}

Try it online!

Output for the example case in the question:

{2: (4, 1), 3: (4, 0), 6: (2, 1), 0: (3, 1), 4: (3, 0), 9: (3, 0), 1: (4, 0), 7: (3, 1), 11: (3, 0), 13: (4, 0), 5: (3, 0), 12: (4, 0), 10: (2, 1), 8: (3, 0), 14: (2, 1)}
\$\endgroup\$
5
  • 1
    \$\begingroup\$ I don't think this is within spec; this doesn't list how many pairs there are for socks with odd-numbered counts. My understanding is that the output should consist of a list of pairs/counts, and a list of which socks have odd counts. This answer has the latter (sort of), but does not completely have the former. \$\endgroup\$
    – squid
    Nov 21, 2019 at 20:02
  • \$\begingroup\$ @ReinstateMonica : you are completely right. My bad. I think I corrected it (and shaved one byte off in the process) - see above. \$\endgroup\$
    – agtoever
    Nov 21, 2019 at 20:43
  • \$\begingroup\$ I still don't think I agree that the updated solution is to spec either, since it hasn't quite made a list of the socks that have odd counts per se... but then again, I'm not OP; maybe it is. \$\endgroup\$
    – squid
    Nov 21, 2019 at 22:18
  • 1
    \$\begingroup\$ Assuming this approach is allowed (clarification needed), you can use the divmod function to save 8 bytes, and remove a space to save a ninth. \$\endgroup\$
    – isaacg
    Nov 22, 2019 at 6:08
  • \$\begingroup\$ Also works in Python 3(.7) \$\endgroup\$ Dec 1, 2019 at 4:20
1
\$\begingroup\$

Burlesque, 27 bytes

raf:Jf{-]2.%})[-jm{g_2./_+}

Try it online!

ra   #Read input as array
f:   #Calculate frequency list
J    #Duplicate
f{   #Filter for
 -]  #Frequency
 2.% #Mod 2 != 0
}
)[-  #Get odd IDs
j    #Swap
m{   #For each block of the frequency list
 g_  #Pop count
 2./ #Divide by 2
 _+  #Concatenate back on
}
\$\endgroup\$
1
\$\begingroup\$

Ruby, 58 bytes

Returns an array with the odds first, then the pairs.

->a,*b{[a.tally.filter_map{_2%2<1?(b<<[_1,_2/2];p):_1},b]}

Attempt This Online!

\$\endgroup\$
1
2

Your Answer

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

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