Match up to 10 in an array

Question

Challenge

Given an array of single digit number, work out if any 2 of them add up to 10 and print them out

Example

Input

(1,2,3,4,5,5,6,7)

This returns ((4,6),(5,5),(3,7))

Input

(1,2,3,4,5)

This returns (). as there is only one 5

Input

(5,5,5,5,5)

This returns ((5,5),(5,5)) as there is odd number of 5s and each 5 can be used only once

Rules

Here are the rules!

• Assume input will only be an unsorted array of positive single digit integers
• Each number will be pair up only once, which means if there are three 5s it only form 1 pair (5,5). If there are (3,3,7) it will only form 1 pair (3,7)
• For the input: You can use any type of parentheses(or lack of) as long as readers can tell that the input is a single array of numbers.
• For the output: It must look like an array of pairs. Where the array is the same form as your input.(If you did not use any parenheses in your input, you have to use some kind of symbols so that any readers can tell they are pairs in an array)

Test Cases

(1,2,3,4,5,5,6,7) =((4,6),(5,5),(3,7))
(1,2,3,4,5) = ()
(5,5,5,5,5) = ((5,5),(5,5))
(1,2,3,3,4,5,6,7)=((3,7),(4,6))
(9,8,7,6,4,4,3,1)=((9,1),(7,3),(6,4))

Good luck!

The shorter an answer is, the better!

Edit 1: update the rules and Testcases from comments

Edit 2: update rules to define format of input.

Edit 3: update rules to define format of output. trying to be as accommodating as possible.

Answer 1

Python 2.7 (70)

y=input()
while y:
 g=10-y.pop()
 if g in y:y.remove(g);print(g,10-g)

Testcases:

$ echo '[1, 2, 3, 4, 5, 5, 6, 7]' | python p.py
(3, 7)
(4, 6)
(5, 5)

$ echo '[1,2,3,4,5]' | python p.py

$ echo '[5,5,5,5,5]' | python p.py
(5, 5)
(5, 5)

$ echo '[1,2,3,3,4,5,6,7]' | python p.py
(3, 7)
(4, 6)

$ echo '[9,8,7,6,4,4,3,1]' | python p.py
(9, 1)
(7, 3)
(6, 4)

One byte extra for the nice parenthesis.

Answer 2

GolfScript, 45 42 37 chars

~{([.~11+.])@{1$=.{2$p!\}*!},\;\;.}do

The new approach does also take arrays with a single item as input. Moreover, it is several chars shorter.

Previous version:

~{$(\)@.2$+10-.{0>{\}*;+}{;[\]p}if.,1>}do;

The algorithm used in this code is described as follows:

• Sort the array.
• Take the sum of the first and the last item.
  • If the sum is 10 print both numbers and remove them from the array.
  • If the sum is greater than 10, discard the larger number.
  • If the sum is less than 10, discard the smaller number.
• Loop until the array contains only a single digit or is even empty.

The code expects an array of at least two digits on STDIN.

Examples (see online):

>[9 8 7 6 4 4 3 1]
[1 9]
[3 7]
[4 6]

>[5 5 5 5 5]
[5 5]
[5 5]

Answer 3

Javascript, 188 183 181 153 141 121 123 112 105 98 chars

Golfing in JS is somewhat difficult, but I just wanted to have a bash on this problem, so here's the code:

for(a=eval(prompt(i=o=[]));k=a[j=++i];)for(;p=a[--j];)k+p-10||(k=a[i]=a[j]=-o.push([p,k]));console.log(o)

Input: e.g. [1,2,3,3,4,5,6,7]. Output e.g. [[4,6],[3,7]] to the console.

105->98: Used Daniel's awesome algorithm to completely rewrite the code! See his answer for a readable algorithm. Completely messed up stuff so reverted to 105 chars.

112->105: Initialised i to zero, used output of o.push to set k (k=a[i]=a[j]=-o.push...) and logged output to console instead of alerting to eliminate "["+ and +"]" since the console outputs nicely already.

123->112: Now removed outer brackets in output, since golfscript may :) Also finally applied suggestion of removing |=0.

121->123: Changed o+="("+p+","+k+")," to o.push("("+[p,k]+")") (adds 2 chars :( ) and made o an array instead of a string (o=""->o=[]). Now output isn't wrong anymore (like ((5,5),(5,5),)).

141->121: From now on assumed that the question meant that we could get input in the language's array format, which in JS's case is [a,b,c,...] and made o, the output "accumulator" a string instead of an array (o.push(...),->o+=...,).

153->141: Reset array entries instead of removing them after usage.

181->153: Applied changes to u=[], rearranged loops, a[i]&a[j]->temp vars, converted if logic and converted int logic to a[i]|=0.

183->181: Replaced i<=0 with i+1 and the same for j.

188->183: Placed o=[] inside prompt() (;) and replaced for(j=i; with for(j=i-1; (i==j&&).

(Thanks mellamokb, Paul Walls and ryan!)

Answer 4

J, 54 53 50 46 45 44 characters

(>:,.9&-)I.<.4({.,-:@{::)(<.|.)+/|:(1+i.9)=/

Usage:

   (>:,.9&-)I.<.4({.,-:@{::)(<.|.)+/|:(1+i.9)=/5 5 5 5 5
5 5
5 5
   (>:,.9&-)I.<.4({.,-:@{::)(<.|.)+/|:(1+i.9)=/9 8 7 6 4 4 3 1
1 9
3 7
4 6

The algorithm is basically:

• count the instance of each number +/|:(1+i.9)=/
• pair the counts of each pair that would add to 10 (<.|.) (so 1 and 9, 2 and 8 etc.)
• take the minimum of those counts (so if you have three 9s but only one 1, you'll only have one 1 9 pair) and drop everything after the first five pairs
• the 5s are a special case so divide that by 2 (<.4({.,-:@{::) implements both previous steps)
• take the first five items of the list and output the number and 10-the number (>:,.9&-)I.

Answer 5

Python (142)

Input should be given with square brackets instead of round brackets. http://ideone.com/p2QR11

from itertools import*
a=input()
c=lambda:[i for i in product(a,a[1:])if sum(i)==10]
d=c()
while d:print d[0];[a.remove(j)for j in d[0]];d=c()

Algorithm:

1. Get input
2. Generate all pairs of input where the sum is 10
3. If there are no pairs, then END PROGRAM
4. Take the first pair's items and remove them from the input
5. Go back to step 2

If seriously malformed output is allowed (90): http://ideone.com/GR762f

a=input()
c=a.count
for i in range(6):print(`i`+`10-i`+' ')*(min(c(i),c(10-i))/(1+(i==5)))

Answer 6

C, 142,138, 124

char*p,*q;
main(int a,char**s){
    for(p=s[1];*p;p++)
        if(q=strchr(p+1,106-*p))a=*q=printf("%c(%c,%c)",38+a,*p,*q);
    puts("()"+a/6);
}

Testing:

./a.out "(1,2,3,4,5,5,6,7)"
((3,7),(4,6),(5,5))

./a.out "(1,2,3,4,5)"
()

./a.out "(5,5,5,5,5)"
((5,5),(5,5))

./a.out "(1,2,3,3,4,5,6,7)"
((3,7),(4,6))

./a.out "(9,8,7,6,4,4,3,1)"
((9,1),(7,3),(6,4))

Implementation notes:

• initially a=2 (program has two args), set to 6 (printf prints 6 chars) once a match occurs
• 106 = '0'+'0'+10, i.e. uses the sum of the ascii codes
• 38+a, is either 44/40, i.e. '(' or ','
• By setting string characters to 6 it ensures they wont add to 106 on other passes
• "()"+a/6, is either "()" or ")"

Answer 7

Perl 52

perl -ne '$a{$y=9-$_}&&0*$a{$y++}--*print"$y,$_"or$a{$_-1}++'

Proof :

> cat test
1
2
3
4
5
5
6
7
> perl -ne '$a{$y=9-$_}&&0*$a{$y++}--*print"$y,$_"or$a{$_-1}++' < test
5,5
4,6
3,7

And there is an ungolfed commented code :

while(<>) {     # made by the -n option

    # We are looking for (P,Q) pairs where P+Q=10
    # Each P entry will come in $_="P\n" (because $_ will not be chopped)
    # We choose to store the number of occurence of P in $a{P-1}
    # (For instance, if there have been five '3's in the input, then $a{2}=5)

    $y=9-$_;        # if Q=P-10, then $y=Q-1
    if ($a{$y}) {   # check if there was a Q (so $a{Q-1} != 0)
        $a{$y++}--;   # If so 'consume' this Q, and let $y=Q
        print"$y,$_"; # ... and output "Q,P\n"
    } else {
        $a{$_-1}++;   # P is not forming a new pair, so 'count it'.
                    # $a{$_} would not work because of the un-chopped \n, thus the '-1'
    }

}

Maybe the explanations looks like pidgin French (I'm not a native english writer), so if someone wants to edit it and make it more understandable, please do so.

Answer 8

Javascript - 131 129 125 chars

for(i=eval(prompt(r=[])),k=j=i.length;j--;)for(m=k;m--;)if(m!=j&&i[j]+i[m]==10)r.push([i[j],i[m]]),i[j]=i[m]=0;console.log(r)

I assume, the order of and in the nested result arrays is not compulsory :)

Evaluated test cases:

[1,2,3,4,5,5,6,7] returns [[7,3],[6,4],[5,5]]
[1,2,3,4,5]       returns []
[5,5,5,5,5]       returns [[5,5],[5,5]]
[1,2,3,3,4,5,6,7] returns [[7,3],[6,4]]
[9,8,7,6,4,4,3,1] returns [[1,9],[3,7],[4,6]]

Edit: As the problem description says 'Array', we're talking about the language specific notation of an array, right?

Answer 9

Mathematica 70

Cases[#//.{x___,n_,y___,d_,z___}/;n+d==10:>{x,y,z,n~f~d},a_~f~b_:>{a,b}]&

Usage

Cases[# //. {x___, n_, y___, d_, z___} /; n + d == 10 :> {x, y, z, n~f~d}, 
a_~f~b_ :> {a,b}] &[{1, 2, 3, 4, 5, 5, 6, 7}]

{{3, 7}, {4, 6}, {5, 5}}

Answer 10

PostScript (46)

This uses hand-coded binary tokens, therefore, here is a hexdump:

00000000  7b 7b 92 1a 92 3f 7b 32  92 19 92 01 31 30 92 3d  |{{...?{2....10.=|
00000010  7b 32 92 09 92 0b 3d 3d  5b 92 40 7d 69 66 92 1a  |{2....==[.@}if..|
00000020  31 92 87 7d 92 83 92 75  7d 92 65 7d 92 a3        |1..}...u}.e}..|
0000002e

I uploaded the binary file if you want to try it out.

This expects the numbers to be on the stack. They can be prepended to the code or be supplied on the command line, e.g. when using Ghostscript like so:

gsnd -c 2 8 5 5 @ 10_golfed.ps

If you insist on array syntax for input, then this requires two more tokens (aload pop) right at the beginning. In binary tokens, this is four more bytes.

Un-golfed and commented:

{ % stopped                   % we use stopped because we want to catch a
                              % stackunderflow when all numbers have been used up
  { % loop                    % repeat until all numbers have been popped off the stack
    % Test for all numbers on the stack whether they add up to 10 with the topmost number
    count{                    % ... nextNumber number currentTestNumber
      exch                    % ... nextNumber currentTestNumber number 
      2 copy add 10 eq{       % ... nextNumber currentTestNumber number
        2 array astore ==     % ... nextNumber
        % We push "[" on the stack because we want to pop the topmost object after each iteration.
        % As [ is a one byte self delimiting token, this is nice for golfing.
        [ exit                % ... nextNumber [
      }if                     % ... nextNumber currentTestNumber number
      count 1 roll            % number ... nextNumber currentTestNumber 
    }repeat                   % number ... nextNumber currentTestNumber
    pop                       % number ... nextNumber
  }loop                       
}stopped

Answer 11

Python 84

Requires input in brackets instead of parenthesis.

a=input();r=[]
while a:
 n=a.pop(0);m=10-n
 if m in a:a.remove(m);r+=[(n,m)]
print r

For roughly the same answer golfed better see Daniel's answer.

Answer 12

PHP 150 149 148 146 142 --> 140

Use with PHP CLI.

<?$a=fgetcsv(STDIN);for($i=0;$i<$c=count($a);$i++){for($j=$i+1;$j<$c;$j++)if($a[$i]+$a[$j]==10){echo"({$a[$i]},{$a[$j]})";$a[$i]=$a[$j]=0;}}

Input: 1,2,3,4,5,5,6,7

Output: (3,7)(4,6)(5,5)

Un-golfed:

<?php

$a = fgetcsv(STDIN);
$c = count($a);
for ($i = 0; $i < $c; $i++) {
    for ($j = ($i + 1); $j < $c; $j++) {
        if ($a[$i] + $a[$j] == 10) {
            echo "({$a[$i]},{$a[$j]})";
            $a[$i] = 0;
            $a[$j] = 0;
        }
    }
}

?>

Answer 13

SED, 112 chars

Probably somewhat simpler than the other solutions

s/.*/@&;12345678987654321/
:
s/\(@.*\)\(.\)\(.*\)\(.\)\(.*;.*\2.\{7\}\4\)/(\2,\4),\1\3\5/
t
s/^\(.*\),@.*/(\1)/

Answer 14

Perl, 72 with the -p flag

perl -p -e 's/^/@/;1while s/(@.*)(.)(.*)((??{10-$2}))/($2,$4)$1$3/;s/(.*)@.*/($1)/'