Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Challenge

Given a 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!

Edit1: update the rules and Testcases from comments

Edit2: update rules to define format of input.

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

share|improve this question
2  
Shouldn't there be 10 different combinations of (5,5) for the final test case? –  Gareth Nov 13 '12 at 17:00
    
@Gareth It looks like the values get used up when they make pairs –  Matt Nov 13 '12 at 17:21
    
Could you post a few more test cases? Perhaps something like (1,2,3,3,4,5,6,7) –  Matt Nov 13 '12 at 17:22
    
@Matt edited. Thanks for the feedback –  user1655072 Nov 13 '12 at 18:05
    
Does the input have to include the parentheses, or can it be inputted as 1,2,3,4,5,5,6,7? –  jdstankosky Nov 15 '12 at 18:54

14 Answers 14

up vote 7 down vote accepted

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]
share|improve this answer

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.

share|improve this answer
    
I think I replicated this method in PHP, but it only works occasionally and not with all pairs. Any idea why? <?$a=fgetcsv(STDIN);while($a){$b=10-array_pop($a);if($a[$b]){unset($a[$b]);echo‌​"($b,",10-$b,")";}} –  jdstankosky Nov 29 '12 at 21:01

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

share|improve this answer
1  
You can replace i>=0 with i+1 and j>=0 with j+1 to save 2 chars. –  mellamokb Nov 13 '12 at 23:38
1  
I applied the change to a bit field array (u=[] instead of x), rearranged the loops to go from 0 upward, assigned a[i] and a[j] to temp variables to save repeated references, moved some variable initializations into other statements, converted the if logic to chained || logic, and converted the int parsing to the more succinct a[i]|=0, to get a total savings of 30 characters :). Here's my test harness demonstrating the accuracy of the solution: jsfiddle.net/GKUDb/8, and the 151-character golfed working solution: jsfiddle.net/DVtW2. –  mellamokb Nov 14 '12 at 17:37
1  
Array.toString() will save you a few characters as well (i.e. o+="("+[p,k]+")"). –  Paul Walls Nov 16 '12 at 5:43
1  
If you are ok with output like that of golfscript, then you can do this: for(a=eval(prompt(o=[])),i=-1;k=a[j=++i]|=0;)for(;p=a[--j];)k+p-10||(o.push("["‌​+[p,k]+"]"),k=a[i]=a[j]=-1);alert(o), brings it down to 115 –  ryan Nov 16 '12 at 21:15
1  
You forgot my suggestion to initialize i to 0. You can fold a=eval(prompt(o=[])),i=-1 into a=eval(prompt(i=o=[])) without loss of fidelity, for a further 3 character savings. –  mellamokb Nov 17 '12 at 3:23

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.
share|improve this answer

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)))
share|improve this answer

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 ")"
share|improve this answer

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.

share|improve this answer
    
Seriously, not even one point for this, with the explanations and all ?... :( –  Orabîg Nov 28 '12 at 19:53

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?

share|improve this answer

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

share|improve this answer

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
share|improve this answer

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.

share|improve this answer

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;
        }
    }
}

?>
share|improve this answer

SED, 112 chars

Probably somewhat simpler than the other solutions

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

Perl, 72 with the -p flag

perl -p -e 's/^/@/;1while s/(@.*)(.)(.*)((??{10-$2}))/($2,$4)$1$3/;s/(.*)@.*/($1)/'
share|improve this answer
    
I think the -p should be counted since the equivalent would add LINE: while (<ARGV>){...}continue{die "-p destination: $!\n" unless print $_} –  Brad Gilbert Nov 17 '12 at 17:14
    
On every automated golf server, this would be counted as 80 bytes, as it requires the shebang #!perl -p plus newline. –  primo Dec 1 '12 at 13:57

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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