Two sum: Difference between revisions
Content added Content deleted
No edit summary |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 22: | Line 22: | ||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="11l">F two_sum(arr, num) |
||
V i = 0 |
V i = 0 |
||
V j = arr.len - 1 |
V j = arr.len - 1 |
||
Line 36: | Line 36: | ||
V numbers = [0, 2, 11, 19, 90] |
V numbers = [0, 2, 11, 19, 90] |
||
print(two_sum(numbers, 21)) |
print(two_sum(numbers, 21)) |
||
print(two_sum(numbers, 25))</ |
print(two_sum(numbers, 25))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 45: | Line 45: | ||
=={{header|Action!}}== |
=={{header|Action!}}== |
||
< |
<syntaxhighlight lang="action!">PROC PrintArray(INT ARRAY a INT len) |
||
INT i |
INT i |
||
Line 98: | Line 98: | ||
Test(a,5,22) |
Test(a,5,22) |
||
Test(b,11,21) |
Test(b,11,21) |
||
RETURN</ |
RETURN</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Two_sum.png Screenshot from Atari 8-bit computer] |
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Two_sum.png Screenshot from Atari 8-bit computer] |
||
Line 116: | Line 116: | ||
=={{header|Aime}}== |
=={{header|Aime}}== |
||
< |
<syntaxhighlight lang="aime">integer i, u, v; |
||
index x; |
index x; |
||
list l; |
list l; |
||
Line 128: | Line 128: | ||
break; |
break; |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>1 3</pre> |
<pre>1 3</pre> |
||
Line 134: | Line 134: | ||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
{{trans|Lua}} |
{{trans|Lua}} |
||
< |
<syntaxhighlight lang="algol68"># returns the subscripts of a pair of numbers in a that sum to sum, a is assumed to be sorted # |
||
# if there isn't a pair of numbers that summs to sum, an empty array is returned # |
# if there isn't a pair of numbers that summs to sum, an empty array is returned # |
||
PRIO TWOSUM = 9; |
PRIO TWOSUM = 9; |
||
Line 170: | Line 170: | ||
print twosum( ( -8, -2, 0, 1, 5, 8, 11 ), 3 ); # should be [0, 6] (or [1, 4]) # |
print twosum( ( -8, -2, 0, 1, 5, 8, 11 ), 3 ); # should be [0, 6] (or [1, 4]) # |
||
print twosum( ( -3, -2, 0, 1, 5, 8, 11 ), 17 ); # should be [] # |
print twosum( ( -3, -2, 0, 1, 5, 8, 11 ), 17 ); # should be [] # |
||
print twosum( ( -8, -2, -1, 1, 5, 9, 11 ), 0 ) # should be [2, 3] #</ |
print twosum( ( -8, -2, -1, 1, 5, 9, 11 ), 0 ) # should be [2, 3] #</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 190: | Line 190: | ||
Then, we just need to find where the right argument (the target) is equal to the matrix, get the indices, and return the first one (⊃). |
Then, we just need to find where the right argument (the target) is equal to the matrix, get the indices, and return the first one (⊃). |
||
<syntaxhighlight lang="apl"> |
|||
<lang APL> |
|||
⎕io ← 0 ⍝ sets index origin to 0 |
⎕io ← 0 ⍝ sets index origin to 0 |
||
ts ← {⊃⍸ ⍵= 0.1@(⍸∘.=⍨⍳≢⍺) ∘.+⍨ ⍺} |
ts ← {⊃⍸ ⍵= 0.1@(⍸∘.=⍨⍳≢⍺) ∘.+⍨ ⍺} |
||
⎕ ← 0 2 11 19 90 ts 21 ⍝ should be 1 3 |
⎕ ← 0 2 11 19 90 ts 21 ⍝ should be 1 3 |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 212: | Line 212: | ||
AppleScript, unusually, happens to make internal use of one-based indices, rigid adherence to which would, of course, in this case, simply produce the wrong result :-) |
AppleScript, unusually, happens to make internal use of one-based indices, rigid adherence to which would, of course, in this case, simply produce the wrong result :-) |
||
< |
<syntaxhighlight lang="applescript">-------------------------- TWO SUM ------------------------- |
||
-- twoSum :: Int -> [Int] -> [(Int, Int)] |
-- twoSum :: Int -> [Int] -> [(Int, Int)] |
||
Line 358: | Line 358: | ||
end repeat |
end repeat |
||
return lst |
return lst |
||
end zip</ |
end zip</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<lang |
<syntaxhighlight lang="applescript">{{1, 3}}</syntaxhighlight> |
||
---- |
---- |
||
Line 366: | Line 366: | ||
Like the "Functional" script above, this returns multiple solutions when they're found. However it assumes a sorted list, as per the clarified task description, which allows some optimisation of the search. Also, the indices returned are 1-based, which is the AppleScript norm. |
Like the "Functional" script above, this returns multiple solutions when they're found. However it assumes a sorted list, as per the clarified task description, which allows some optimisation of the search. Also, the indices returned are 1-based, which is the AppleScript norm. |
||
< |
<syntaxhighlight lang="applescript">on twoSum(givenNumbers, givenSum) |
||
script o |
script o |
||
property lst : givenNumbers |
property lst : givenNumbers |
||
Line 391: | Line 391: | ||
twoSum({0, 2, 11, 19, 90}, 21) -- Task-specified list. |
twoSum({0, 2, 11, 19, 90}, 21) -- Task-specified list. |
||
twoSum({0, 3, 11, 19, 90}, 21) -- No matches. |
twoSum({0, 3, 11, 19, 90}, 21) -- No matches. |
||
twoSum({-44, 0, 0, 2, 10, 11, 19, 21, 21, 21, 65, 90}, 21) -- Multiple solutions.</ |
twoSum({-44, 0, 0, 2, 10, 11, 19, 21, 21, 21, 65, 90}, 21) -- Multiple solutions.</syntaxhighlight> |
||
{{output}} |
{{output}} |
||
< |
<syntaxhighlight lang="applescript">{{2, 4}} |
||
{} |
{} |
||
{{1, 11}, {2, 8}, {2, 9}, {2, 10}, {3, 8}, {3, 9}, {3, 10}, {4, 7}, {5, 6}}</ |
{{1, 11}, {2, 8}, {2, 9}, {2, 10}, {3, 8}, {3, 9}, {3, 10}, {4, 7}, {5, 6}}</syntaxhighlight> |
||
=={{header|Arturo}}== |
=={{header|Arturo}}== |
||
< |
<syntaxhighlight lang="rebol">twoSum: function [numbers, s][ |
||
loop.with:'i numbers 'x [ |
loop.with:'i numbers 'x [ |
||
if not? null? j: <= index numbers s-x -> |
if not? null? j: <= index numbers s-x -> |
||
Line 411: | Line 411: | ||
print ["twoSum 21:" twoSum nums 21] |
print ["twoSum 21:" twoSum nums 21] |
||
print ["twoSum 25:" twoSum nums 25]</ |
print ["twoSum 25:" twoSum nums 25]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 419: | Line 419: | ||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |
||
< |
<syntaxhighlight lang="autohotkey">TwoSum(a, target){ |
||
i := 1, j := a.MaxIndex() |
i := 1, j := a.MaxIndex() |
||
while(i < j){ |
while(i < j){ |
||
Line 430: | Line 430: | ||
} |
} |
||
return "not found" |
return "not found" |
||
}</ |
}</syntaxhighlight> |
||
Examples:< |
Examples:<syntaxhighlight lang="autohotkey">MsgBox % TwoSum([0, 2, 11, 19, 90], 21) ; returns 2, 4 (first index is 1 not 0)</syntaxhighlight> |
||
Outputs:<pre>2,4</pre> |
Outputs:<pre>2,4</pre> |
||
=={{header|AWK}}== |
=={{header|AWK}}== |
||
<syntaxhighlight lang="awk"> |
|||
<lang AWK> |
|||
# syntax: GAWK -f TWO_SUM.AWK |
# syntax: GAWK -f TWO_SUM.AWK |
||
BEGIN { |
BEGIN { |
||
Line 460: | Line 460: | ||
return("[]") |
return("[]") |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 468: | Line 468: | ||
=={{header|Befunge}}== |
=={{header|Befunge}}== |
||
< |
<syntaxhighlight lang="befunge">>000pv |
||
>&:0\`#v_00g:1+00p6p |
>&:0\`#v_00g:1+00p6p |
||
v >$&50p110p020p |
v >$&50p110p020p |
||
Line 483: | Line 483: | ||
>:#,_@ 8 |
>:#,_@ 8 |
||
p |
p |
||
> ^</ |
> ^</syntaxhighlight> |
||
There are a couple of caveats due to limitations of the language. The target cannot be above 127, there can be no more than 47 elements in the list and the list must be delimited by a negative number before the target value as follows: |
There are a couple of caveats due to limitations of the language. The target cannot be above 127, there can be no more than 47 elements in the list and the list must be delimited by a negative number before the target value as follows: |
||
<pre> |
<pre> |
||
Line 493: | Line 493: | ||
=={{header|C}}== |
=={{header|C}}== |
||
<syntaxhighlight lang="c"> |
|||
<lang C> |
|||
#include<stdio.h> |
#include<stdio.h> |
||
Line 515: | Line 515: | ||
return 0; |
return 0; |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output : |
Output : |
||
<pre> |
<pre> |
||
Line 522: | Line 522: | ||
=={{header|C sharp|C#}}== |
=={{header|C sharp|C#}}== |
||
< |
<syntaxhighlight lang="csharp">using System; |
||
using System.Collections.Generic; |
using System.Collections.Generic; |
||
Line 554: | Line 554: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre>1, 3</pre> |
<pre>1, 3</pre> |
||
Line 560: | Line 560: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
{{trans|C#}} |
{{trans|C#}} |
||
< |
<syntaxhighlight lang="cpp">#include <iostream> |
||
#include <map> |
#include <map> |
||
#include <tuple> |
#include <tuple> |
||
Line 594: | Line 594: | ||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>{1,3}</pre> |
<pre>{1,3}</pre> |
||
=={{header|D}}== |
=={{header|D}}== |
||
< |
<syntaxhighlight lang="d">import std.stdio; |
||
void main() { |
void main() { |
||
Line 636: | Line 636: | ||
return []; |
return []; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[1, 3]</pre> |
<pre>[1, 3]</pre> |
||
=={{header|Dart}}== |
=={{header|Dart}}== |
||
<lang> |
<syntaxhighlight lang="text"> |
||
main() { |
main() { |
||
var a = [1,2,3,4,5]; |
var a = [1,2,3,4,5]; |
||
Line 670: | Line 670: | ||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Delphi}}== |
=={{header|Delphi}}== |
||
{{libheader| System.SysUtils}} |
{{libheader| System.SysUtils}} |
||
{{libheader| System.Generics.Collections}} |
{{libheader| System.Generics.Collections}} |
||
{{Trans|Python}} |
{{Trans|Python}} |
||
<syntaxhighlight lang="delphi"> |
|||
<lang Delphi> |
|||
program Two_Sum; |
program Two_Sum; |
||
Line 712: | Line 712: | ||
Writeln('(', i, ',', j, ')'); |
Writeln('(', i, ',', j, ')'); |
||
Readln; |
Readln; |
||
end.</ |
end.</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 718: | Line 718: | ||
</pre> |
</pre> |
||
=={{header|Elixir}}== |
=={{header|Elixir}}== |
||
< |
<syntaxhighlight lang="elixir">defmodule RC do |
||
def two_sum(numbers, sum) do |
def two_sum(numbers, sum) do |
||
Enum.with_index(numbers) |> |
Enum.with_index(numbers) |> |
||
Line 733: | Line 733: | ||
numbers = [0, 2, 11, 19, 90] |
numbers = [0, 2, 11, 19, 90] |
||
IO.inspect RC.two_sum(numbers, 21) |
IO.inspect RC.two_sum(numbers, 21) |
||
IO.inspect RC.two_sum(numbers, 25)</ |
IO.inspect RC.two_sum(numbers, 25)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 742: | Line 742: | ||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
< |
<syntaxhighlight lang="fsharp"> |
||
// Two Sum : Nigel Galloway December 5th., 2017 |
// Two Sum : Nigel Galloway December 5th., 2017 |
||
let fN n i = |
let fN n i = |
||
Line 753: | Line 753: | ||
fN n 0 |
fN n 0 |
||
printfn "%A" (fN [0; 2; 11; 19; 90] 21) |
printfn "%A" (fN [0; 2; 11; 19; 90] 21) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 760: | Line 760: | ||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
< |
<syntaxhighlight lang="factor">USING: combinators fry kernel locals math prettyprint sequences ; |
||
IN: rosetta-code.two-sum |
IN: rosetta-code.two-sum |
||
Line 773: | Line 773: | ||
x y = { } { x y } ? ; |
x y = { } { x y } ? ; |
||
{ 21 55 11 } [ '[ { 0 2 11 19 90 } _ two-sum . ] call ] each</ |
{ 21 55 11 } [ '[ { 0 2 11 19 90 } _ two-sum . ] call ] each</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 783: | Line 783: | ||
=={{header|Forth}}== |
=={{header|Forth}}== |
||
{{works with|Gforth|0.7.3}} |
{{works with|Gforth|0.7.3}} |
||
< |
<syntaxhighlight lang="forth">CREATE A CELL ALLOT |
||
: A[] ( n -- A[n]) CELLS A @ + @ ; |
: A[] ( n -- A[n]) CELLS A @ + @ ; |
||
:NONAME 1- ; |
:NONAME 1- ; |
||
Line 806: | Line 806: | ||
TEST1 3 TWOSUM CR |
TEST1 3 TWOSUM CR |
||
TEST1 8 TWOSUM CR |
TEST1 8 TWOSUM CR |
||
BYE</ |
BYE</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[1, 3] |
<pre>[1, 3] |
||
Line 814: | Line 814: | ||
=={{header|Fortran}}== |
=={{header|Fortran}}== |
||
< |
<syntaxhighlight lang="fortran">program twosum |
||
implicit none |
implicit none |
||
Line 839: | Line 839: | ||
end program twosum |
end program twosum |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 845: | Line 845: | ||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
< |
<syntaxhighlight lang="freebasic">' FB 1.05.0 Win64 |
||
' "a" is the array of sorted non-negative integers |
' "a" is the array of sorted non-negative integers |
||
Line 885: | Line 885: | ||
Print |
Print |
||
Print "Press any number to quit" |
Print "Press any number to quit" |
||
Sleep</ |
Sleep</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 894: | Line 894: | ||
=={{header|Go}}== |
=={{header|Go}}== |
||
{{trans|Kotlin}} |
{{trans|Kotlin}} |
||
< |
<syntaxhighlight lang="go">package main |
||
import "fmt" |
import "fmt" |
||
Line 930: | Line 930: | ||
fmt.Println("The numbers with indices", p1, "and", p2, "sum to", targetSum) |
fmt.Println("The numbers with indices", p1, "and", p2, "sum to", targetSum) |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 939: | Line 939: | ||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
====Returning first match==== |
====Returning first match==== |
||
< |
<syntaxhighlight lang="haskell">twoSum::(Num a,Ord a) => a -> [a] -> [Int] |
||
twoSum num list = sol ls (reverse ls) |
twoSum num list = sol ls (reverse ls) |
||
where |
where |
||
Line 953: | Line 953: | ||
| otherwise = sol xs $ dropWhile ((num <).(+x).fst) vs |
| otherwise = sol xs $ dropWhile ((num <).(+x).fst) vs |
||
main = print $ twoSum 21 [0, 2, 11, 19, 90]</ |
main = print $ twoSum 21 [0, 2, 11, 19, 90]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[1,3]</pre> |
<pre>[1,3]</pre> |
||
Line 960: | Line 960: | ||
Listing multiple solutions (as zero-based indices) where they exist: |
Listing multiple solutions (as zero-based indices) where they exist: |
||
< |
<syntaxhighlight lang="haskell">sumTo :: Int -> [Int] -> [(Int, Int)] |
||
sumTo n ns = |
sumTo n ns = |
||
let ixs = zip [0 ..] ns |
let ixs = zip [0 ..] ns |
||
Line 973: | Line 973: | ||
main :: IO () |
main :: IO () |
||
main = mapM_ print $ sumTo 21 [0, 2, 11, 19, 90, 10]</ |
main = mapM_ print $ sumTo 21 [0, 2, 11, 19, 90, 10]</syntaxhighlight> |
||
Or, resugaring a little – pulling more into the scope of the list comprehension: |
Or, resugaring a little – pulling more into the scope of the list comprehension: |
||
< |
<syntaxhighlight lang="haskell">sumTo :: Int -> [Int] -> [(Int, Int)] |
||
sumTo n ns = |
sumTo n ns = |
||
let ixs = zip [0 ..] ns |
let ixs = zip [0 ..] ns |
||
Line 985: | Line 985: | ||
main :: IO () |
main :: IO () |
||
main = mapM_ print $ sumTo 21 [0, 2, 11, 19, 90, 10]</ |
main = mapM_ print $ sumTo 21 [0, 2, 11, 19, 90, 10]</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>(1,3) |
<pre>(1,3) |
||
Line 996: | Line 996: | ||
<tt>fullimag</tt> library used to pretty print lists. |
<tt>fullimag</tt> library used to pretty print lists. |
||
< |
<syntaxhighlight lang="unicon"># |
||
# twosum.icn, find two array elements that add up to a given sum |
# twosum.icn, find two array elements that add up to a given sum |
||
# Dedicated to the public domain |
# Dedicated to the public domain |
||
Line 1,026: | Line 1,026: | ||
} |
} |
||
return [] |
return [] |
||
end</ |
end</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,038: | Line 1,038: | ||
So, first off, our basic approach will be to find the sums: |
So, first off, our basic approach will be to find the sums: |
||
< |
<syntaxhighlight lang="j"> =+/~0 2 11 19 90 |
||
0 2 11 19 90 |
0 2 11 19 90 |
||
2 4 13 21 92 |
2 4 13 21 92 |
||
11 13 22 30 101 |
11 13 22 30 101 |
||
19 21 30 38 109 |
19 21 30 38 109 |
||
90 92 101 109 180</ |
90 92 101 109 180</syntaxhighlight> |
||
And, check if any of them are our desired value: |
And, check if any of them are our desired value: |
||
< |
<syntaxhighlight lang="j"> 21=+/~0 2 11 19 90 |
||
0 0 0 0 0 |
0 0 0 0 0 |
||
0 0 0 1 0 |
0 0 0 1 0 |
||
0 0 0 0 0 |
0 0 0 0 0 |
||
0 1 0 0 0 |
0 1 0 0 0 |
||
0 0 0 0 0</ |
0 0 0 0 0</syntaxhighlight> |
||
Except, we want indices here, so let's toss the structure so we can get those: |
Except, we want indices here, so let's toss the structure so we can get those: |
||
< |
<syntaxhighlight lang="j"> ,21=+/~0 2 11 19 90 |
||
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 |
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 |
||
I.,21=+/~0 2 11 19 90 |
I.,21=+/~0 2 11 19 90 |
||
8 16</ |
8 16</syntaxhighlight> |
||
Except, we really needed that structure - in this case, since we had a five by five table, we want to interpret this result as a base five pair of numbers: |
Except, we really needed that structure - in this case, since we had a five by five table, we want to interpret this result as a base five pair of numbers: |
||
< |
<syntaxhighlight lang="j"> $21=+/~0 2 11 19 90 |
||
5 5 |
5 5 |
||
5 5#:I.,21=+/~0 2 11 19 90 |
5 5#:I.,21=+/~0 2 11 19 90 |
||
1 3 |
1 3 |
||
3 1</ |
3 1</syntaxhighlight> |
||
Or, taking advantage of being able to use verbs to represent combining their results, when we use three of them: |
Or, taking advantage of being able to use verbs to represent combining their results, when we use three of them: |
||
< |
<syntaxhighlight lang="j"> ($ #: I.@,)21=+/~0 2 11 19 90 |
||
1 3 |
1 3 |
||
3 1</ |
3 1</syntaxhighlight> |
||
But to be more like the other task implementations here, we don't want all the results, we just want zero or one result. We can't just take the first result, though, because that would fill in a 0 0 result if there were none, and 0 0 could have been a valid result which does not make sense for the failure case. So, instead, let's package things up so we can add an empty to the end and take the first of those: |
But to be more like the other task implementations here, we don't want all the results, we just want zero or one result. We can't just take the first result, though, because that would fill in a 0 0 result if there were none, and 0 0 could have been a valid result which does not make sense for the failure case. So, instead, let's package things up so we can add an empty to the end and take the first of those: |
||
< |
<syntaxhighlight lang="j"> ($ <@#: I.@,)21=+/~0 2 11 19 90 |
||
┌───┬───┐ |
┌───┬───┐ |
||
│1 3│3 1│ |
│1 3│3 1│ |
||
Line 1,087: | Line 1,087: | ||
└───┘ |
└───┘ |
||
;{.a:,~($ <@#: I.@,)21=+/~0 2 11 19 90 |
;{.a:,~($ <@#: I.@,)21=+/~0 2 11 19 90 |
||
1 3</ |
1 3</syntaxhighlight> |
||
Finally, let's start pulling our arguments out using that three verbs combining form: |
Finally, let's start pulling our arguments out using that three verbs combining form: |
||
< |
<syntaxhighlight lang="j"> ;{.a:,~($ <@#: I.@,) 21([ = +/~@])0 2 11 19 90 |
||
1 3 |
1 3 |
||
;{.a:,~21 ($ <@#: I.@,)@([ = +/~@])0 2 11 19 90 |
;{.a:,~21 ($ <@#: I.@,)@([ = +/~@])0 2 11 19 90 |
||
1 3</ |
1 3</syntaxhighlight> |
||
a: is not a verb, but we can use a noun as the left verb of three as an implied constant verb whose result is itself: |
a: is not a verb, but we can use a noun as the left verb of three as an implied constant verb whose result is itself: |
||
< |
<syntaxhighlight lang="j"> ;{. 21 (a:,~ ($ <@#: I.@,)@([ = +/~@]))0 2 11 19 90 |
||
1 3</ |
1 3</syntaxhighlight> |
||
And, let's finish the job, give this a name, and test it out: |
And, let's finish the job, give this a name, and test it out: |
||
< |
<syntaxhighlight lang="j"> twosum=: ;@{.@(a:,~ ($ <@#: I.@,)@([ = +/~@])) |
||
21 twosum 0 2 11 19 90 |
21 twosum 0 2 11 19 90 |
||
1 3</ |
1 3</syntaxhighlight> |
||
Except that looks like a bit of a mess. A lot of the reason for this is that ascii is ugly to look at. (Another issue, though, is that a lot of people are not used to architecting control flow as expressions.) |
Except that looks like a bit of a mess. A lot of the reason for this is that ascii is ugly to look at. (Another issue, though, is that a lot of people are not used to architecting control flow as expressions.) |
||
Line 1,109: | Line 1,109: | ||
So... let's do this over again, using a more traditional implementation where we name intermediate results. (We're going to stick with our architecture, though, because changing the architecture to the more traditional approach would change the space/time tradeoff to require more time.) |
So... let's do this over again, using a more traditional implementation where we name intermediate results. (We're going to stick with our architecture, though, because changing the architecture to the more traditional approach would change the space/time tradeoff to require more time.) |
||
< |
<syntaxhighlight lang="j">two_sum=:dyad define |
||
sums=. +/~ y |
sums=. +/~ y |
||
matches=. x = sums |
matches=. x = sums |
||
Line 1,115: | Line 1,115: | ||
pair_inds=. ($matches) #: sum_inds |
pair_inds=. ($matches) #: sum_inds |
||
; {. a: ,~ <"1 pair_inds |
; {. a: ,~ <"1 pair_inds |
||
)</ |
)</syntaxhighlight> |
||
And, testing: |
And, testing: |
||
< |
<syntaxhighlight lang="j"> 21 two_sum 0 2 11 19 90 |
||
1 3</ |
1 3</syntaxhighlight> |
||
Or, we could go slightly more traditional and instead of doing that boxing at the end, use an if/else statement: |
Or, we could go slightly more traditional and instead of doing that boxing at the end, use an if/else statement: |
||
< |
<syntaxhighlight lang="j">two_sum=:dyad define |
||
sums=. +/~ y |
sums=. +/~ y |
||
matches=. x = sums |
matches=. x = sums |
||
Line 1,134: | Line 1,134: | ||
i.0 |
i.0 |
||
end. |
end. |
||
)</ |
)</syntaxhighlight> |
||
Then again, most people don't read J anyways, so maybe just stick with the earlier implementation: |
Then again, most people don't read J anyways, so maybe just stick with the earlier implementation: |
||
< |
<syntaxhighlight lang="j">twosum=: ;@{.@(a:,~ ($ <@#: I.@,)@([ = +/~@]))</syntaxhighlight> |
||
'''Alternative approach''' |
'''Alternative approach''' |
||
Line 1,144: | Line 1,144: | ||
An alternative method for identifying and returning non-duplicate indicies of the pairs follows. |
An alternative method for identifying and returning non-duplicate indicies of the pairs follows. |
||
< |
<syntaxhighlight lang="j"> 21 (= +/~) 0 2 11 19 90 |
||
0 0 0 0 0 |
0 0 0 0 0 |
||
0 0 0 1 0 |
0 0 0 1 0 |
||
0 0 0 0 0 |
0 0 0 0 0 |
||
0 1 0 0 0 |
0 1 0 0 0 |
||
0 0 0 0 0</ |
0 0 0 0 0</syntaxhighlight> |
||
The array is symmetrical so we can zero one half to remove duplicate pairs and then retrieve the remaining indicies using sparse array functionality. |
The array is symmetrical so we can zero one half to remove duplicate pairs and then retrieve the remaining indicies using sparse array functionality. |
||
< |
<syntaxhighlight lang="j">zeroLowerTri=: * [: </~ i.@# |
||
getIdx=: 4 $. $. |
getIdx=: 4 $. $. |
||
twosum_alt=: getIdx@zeroLowerTri@(= +/~)</ |
twosum_alt=: getIdx@zeroLowerTri@(= +/~)</syntaxhighlight> |
||
Testing ... |
Testing ... |
||
< |
<syntaxhighlight lang="j"> 21 twosum_alt 0 2 11 19 90 |
||
1 3</ |
1 3</syntaxhighlight> |
||
=={{header|Java}}== |
=={{header|Java}}== |
||
{{trans|Lua}} |
{{trans|Lua}} |
||
< |
<syntaxhighlight lang="java">import java.util.Arrays; |
||
public class TwoSum { |
public class TwoSum { |
||
Line 1,183: | Line 1,183: | ||
return null; |
return null; |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
<pre>[1, 3]</pre> |
<pre>[1, 3]</pre> |
||
Line 1,197: | Line 1,197: | ||
in the map result are eliminated by the concat. |
in the map result are eliminated by the concat. |
||
< |
<syntaxhighlight lang="javascript">(function () { |
||
var concatMap = function (f, xs) { |
var concatMap = function (f, xs) { |
||
return [].concat.apply([], xs.map(f)) |
return [].concat.apply([], xs.map(f)) |
||
Line 1,212: | Line 1,212: | ||
}(21, [0, 2, 11, 19, 90]); |
}(21, [0, 2, 11, 19, 90]); |
||
})(); |
})(); |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<lang |
<syntaxhighlight lang="javascript">[[1,3]]</syntaxhighlight> |
||
===ES6=== |
===ES6=== |
||
Line 1,221: | Line 1,221: | ||
Composing a solution from generic functions like zip, bind (>>=, or flip concatMap) etc. |
Composing a solution from generic functions like zip, bind (>>=, or flip concatMap) etc. |
||
{{Trans|Haskell}} |
{{Trans|Haskell}} |
||
< |
<syntaxhighlight lang="javascript">(() => { |
||
'use strict'; |
'use strict'; |
||
Line 1,271: | Line 1,271: | ||
sumTwo(21, [0, 2, 11, 19, 90, 10]) |
sumTwo(21, [0, 2, 11, 19, 90, 10]) |
||
); |
); |
||
})();</ |
})();</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>[[1,3],[2,5]]</pre> |
<pre>[[1,3],[2,5]]</pre> |
||
Line 1,277: | Line 1,277: | ||
=={{header|Jsish}}== |
=={{header|Jsish}}== |
||
Based on Javascript entry. |
Based on Javascript entry. |
||
< |
<syntaxhighlight lang="javascript">/* Two Sum, in Jsish */ |
||
function twoSum(target, list) { |
function twoSum(target, list) { |
||
var concatMap = function (f, xs) { |
var concatMap = function (f, xs) { |
||
Line 1,298: | Line 1,298: | ||
;twoSum(21, list); |
;twoSum(21, list); |
||
;list[twoSum(21, list)[0][0]]; |
;list[twoSum(21, list)[0][0]]; |
||
;list[twoSum(21, list)[0][1]];</ |
;list[twoSum(21, list)[0][1]];</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,311: | Line 1,311: | ||
'''Works with gojq, the Go implementation of jq. |
'''Works with gojq, the Go implementation of jq. |
||
{{trans|Julia}} |
{{trans|Julia}} |
||
< |
<syntaxhighlight lang="jq">def twosum($s): |
||
. as $v |
. as $v |
||
| {i: 0, j: ($v|length - 1) } |
| {i: 0, j: ($v|length - 1) } |
||
Line 1,322: | Line 1,322: | ||
[0, 2, 11, 19, 90] |
[0, 2, 11, 19, 90] |
||
| (twosum(21), twosum(25)) |
| (twosum(21), twosum(25)) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,332: | Line 1,332: | ||
{{works with|Julia|0.6}} |
{{works with|Julia|0.6}} |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="julia">function twosum(v::Vector, s) |
||
i = 1 |
i = 1 |
||
j = length(v) |
j = length(v) |
||
Line 1,347: | Line 1,347: | ||
end |
end |
||
@show twosum([0, 2, 11, 19, 90], 21)</ |
@show twosum([0, 2, 11, 19, 90], 21)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,353: | Line 1,353: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
< |
<syntaxhighlight lang="scala">// version 1.1 |
||
fun twoSum(a: IntArray, targetSum: Int): Pair<Int, Int>? { |
fun twoSum(a: IntArray, targetSum: Int): Pair<Int, Int>? { |
||
Line 1,381: | Line 1,381: | ||
println("The numbers with indices ${p.first} and ${p.second} sum to $targetSum") |
println("The numbers with indices ${p.first} and ${p.second} sum to $targetSum") |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,389: | Line 1,389: | ||
=={{header|Liberty BASIC}}== |
=={{header|Liberty BASIC}}== |
||
< |
<syntaxhighlight lang="liberty basic">myArray(0) = 0 |
||
myArray(1) = 2 |
myArray(1) = 2 |
||
myArray(2) = 11 |
myArray(2) = 11 |
||
Line 1,414: | Line 1,414: | ||
Wend |
Wend |
||
twoToSum$ = "[]" |
twoToSum$ = "[]" |
||
End Function</ |
End Function</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[1,3]</pre> |
<pre>[1,3]</pre> |
||
Line 1,420: | Line 1,420: | ||
=={{header|Lua}}== |
=={{header|Lua}}== |
||
Lua uses one-based indexing. |
Lua uses one-based indexing. |
||
< |
<syntaxhighlight lang="lua">function twoSum (numbers, sum) |
||
local i, j, s = 1, #numbers |
local i, j, s = 1, #numbers |
||
while i < j do |
while i < j do |
||
Line 1,435: | Line 1,435: | ||
end |
end |
||
print(table.concat(twoSum({0,2,11,19,90}, 21), ","))</ |
print(table.concat(twoSum({0,2,11,19,90}, 21), ","))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>2,4</pre> |
<pre>2,4</pre> |
||
=={{header|Maple}}== |
=={{header|Maple}}== |
||
< |
<syntaxhighlight lang="maple">two_sum := proc(arr, sum) |
||
local i,j,temp: |
local i,j,temp: |
||
i,j := 1,numelems(arr): |
i,j := 1,numelems(arr): |
||
Line 1,456: | Line 1,456: | ||
end proc: |
end proc: |
||
L := Array([0,2,2,11,19,19,90]); |
L := Array([0,2,2,11,19,19,90]); |
||
two_sum(L, 21);</ |
two_sum(L, 21);</syntaxhighlight> |
||
{{Out|Output}} |
{{Out|Output}} |
||
Note that Maple does 1 based indexing. |
Note that Maple does 1 based indexing. |
||
Line 1,463: | Line 1,463: | ||
</pre> |
</pre> |
||
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
||
< |
<syntaxhighlight lang="mathematica">twoSum[data_List, sum_] := |
||
Block[{indices = Subsets[Range@Length@data, {2}]}, |
Block[{indices = Subsets[Range@Length@data, {2}]}, |
||
Cases[indices, _?(Total@data[[#]] == sum &)]] |
Cases[indices, _?(Total@data[[#]] == sum &)]] |
||
twoSum[{0, 2, 11, 19, 90}, 21] // TableForm</ |
twoSum[{0, 2, 11, 19, 90}, 21] // TableForm</syntaxhighlight> |
||
{{out}}<pre> |
{{out}}<pre> |
||
Line 1,475: | Line 1,475: | ||
=={{header|MiniScript}}== |
=={{header|MiniScript}}== |
||
< |
<syntaxhighlight lang="miniscript">twoSum = function(numbers, sum) |
||
// Make a map of values to their indices in the numbers array |
// Make a map of values to their indices in the numbers array |
||
// as we go, so we will know when we've found a match. |
// as we go, so we will know when we've found a match. |
||
Line 1,486: | Line 1,486: | ||
end function |
end function |
||
print twoSum([0, 2, 11, 19, 90], 21)</ |
print twoSum([0, 2, 11, 19, 90], 21)</syntaxhighlight> |
||
Output: |
Output: |
||
Line 1,492: | Line 1,492: | ||
=={{header|Modula-2}}== |
=={{header|Modula-2}}== |
||
< |
<syntaxhighlight lang="modula2">MODULE TwoSum; |
||
FROM FormatString IMPORT FormatString; |
FROM FormatString IMPORT FormatString; |
||
FROM Terminal IMPORT WriteString,ReadChar; |
FROM Terminal IMPORT WriteString,ReadChar; |
||
Line 1,537: | Line 1,537: | ||
WriteString(buf); |
WriteString(buf); |
||
ReadChar; |
ReadChar; |
||
END TwoSum.</ |
END TwoSum.</syntaxhighlight> |
||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
< |
<syntaxhighlight lang="nim">proc twoSum(src: openarray[int], target: int): array[2, int] = |
||
if src.len < 2: |
if src.len < 2: |
||
return |
return |
||
Line 1,573: | Line 1,573: | ||
main()</ |
main()</syntaxhighlight> |
||
=={{header|Objeck}}== |
=={{header|Objeck}}== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang="objeck">class TwoSum { |
||
function : Main(args : String[]) ~ Nil { |
function : Main(args : String[]) ~ Nil { |
||
sum := 21; |
sum := 21; |
||
Line 1,619: | Line 1,619: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
Line 1,629: | Line 1,629: | ||
{{trans|C}} |
{{trans|C}} |
||
< |
<syntaxhighlight lang="ocaml">let get_sums ~numbers ~sum = |
||
let n = Array.length numbers in |
let n = Array.length numbers in |
||
let res = ref [] in |
let res = ref [] in |
||
Line 1,649: | Line 1,649: | ||
List.iter (fun (i, j) -> |
List.iter (fun (i, j) -> |
||
Printf.printf "# Found: %d %d\n" i j |
Printf.printf "# Found: %d %d\n" i j |
||
) res</ |
) res</syntaxhighlight> |
||
Will return all possible sums, not just the first one found. |
Will return all possible sums, not just the first one found. |
||
Line 1,660: | Line 1,660: | ||
=={{header|ooRexx}}== |
=={{header|ooRexx}}== |
||
< |
<syntaxhighlight lang="oorexx">a=.array~of( -5, 26, 0, 2, 11, 19, 90) |
||
x=21 |
x=21 |
||
n=0 |
n=0 |
||
Line 1,672: | Line 1,672: | ||
End |
End |
||
If n=0 Then |
If n=0 Then |
||
Say '[] - no items found' </ |
Say '[] - no items found' </syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[0,1] |
<pre>[0,1] |
||
Line 1,679: | Line 1,679: | ||
=={{header|Pascal}}== |
=={{header|Pascal}}== |
||
A little bit lengthy. Implemented an unsorted Version with quadratic runtime too and an extra test case with 83667 elements that needs 83667*86666/2 ~ 3.5 billion checks ( ~1 cpu-cycles/check, only if data in cache ). |
A little bit lengthy. Implemented an unsorted Version with quadratic runtime too and an extra test case with 83667 elements that needs 83667*86666/2 ~ 3.5 billion checks ( ~1 cpu-cycles/check, only if data in cache ). |
||
< |
<syntaxhighlight lang="pascal">program twosum; |
||
{$IFDEF FPC}{$MODE DELPHI}{$ELSE}{$APPTYPE CONSOLE}{$ENDIF} |
{$IFDEF FPC}{$MODE DELPHI}{$ELSE}{$APPTYPE CONSOLE}{$ENDIF} |
||
uses |
uses |
||
Line 1,794: | Line 1,794: | ||
else |
else |
||
writeln('No solution found'); |
writeln('No solution found'); |
||
end.</ |
end.</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,808: | Line 1,808: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="perl">use strict; |
||
use warnings; |
use warnings; |
||
use feature 'say'; |
use feature 'say'; |
||
Line 1,830: | Line 1,830: | ||
@indices = two_sum(25, @numbers); |
@indices = two_sum(25, @numbers); |
||
say join(', ', @indices) || 'No match';</ |
say join(', ', @indices) || 'No match';</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>1, 3 |
<pre>1, 3 |
||
Line 1,836: | Line 1,836: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<!--< |
<!--<syntaxhighlight lang="phix">--> |
||
<span style="color: #008080;">function</span> <span style="color: #000000;">twosum</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">)</span> |
<span style="color: #008080;">function</span> <span style="color: #000000;">twosum</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">)</span> |
||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
||
Line 1,848: | Line 1,848: | ||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
||
<span style="color: #0000FF;">?</span><span style="color: #000000;">twosum</span><span style="color: #0000FF;">({</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">11</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">19</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">90</span><span style="color: #0000FF;">},</span><span style="color: #000000;">21</span><span style="color: #0000FF;">)</span> |
<span style="color: #0000FF;">?</span><span style="color: #000000;">twosum</span><span style="color: #0000FF;">({</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">11</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">19</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">90</span><span style="color: #0000FF;">},</span><span style="color: #000000;">21</span><span style="color: #0000FF;">)</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{trans|Raku}} |
{{trans|Raku}} |
||
<!--< |
<!--<syntaxhighlight lang="phix">--> |
||
<span style="color: #008080;">function</span> <span style="color: #000000;">twosum</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">numbers</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">total</span><span style="color: #0000FF;">)</span> |
<span style="color: #008080;">function</span> <span style="color: #000000;">twosum</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">numbers</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">total</span><span style="color: #0000FF;">)</span> |
||
<span style="color: #004080;">integer</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">numbers</span><span style="color: #0000FF;">)</span> |
<span style="color: #004080;">integer</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">numbers</span><span style="color: #0000FF;">)</span> |
||
Line 1,862: | Line 1,862: | ||
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{}</span> |
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{}</span> |
||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{Out}} |
{{Out}} |
||
Phix uses 1-based indexes |
Phix uses 1-based indexes |
||
Line 1,870: | Line 1,870: | ||
=={{header|Phixmonti}}== |
=={{header|Phixmonti}}== |
||
< |
<syntaxhighlight lang="phixmonti">include ..\Utilitys.pmt |
||
def two_sum /# arr num -- n #/ |
def two_sum /# arr num -- n #/ |
||
Line 1,891: | Line 1,891: | ||
( 0 2 11 19 90 ) |
( 0 2 11 19 90 ) |
||
21 two_sum ? |
21 two_sum ? |
||
25 two_sum ?</ |
25 two_sum ?</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[2, 19] |
<pre>[2, 19] |
||
Line 1,899: | Line 1,899: | ||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
< |
<syntaxhighlight lang="picolisp">(de twosum (Lst N) |
||
(for ((I . A) Lst A (cdr A)) |
(for ((I . A) Lst A (cdr A)) |
||
(T |
(T |
||
Line 1,909: | Line 1,909: | ||
(twosum (0 2 11 19 90) 21) |
(twosum (0 2 11 19 90) 21) |
||
(twosum (-3 -2 0 1 5 8 11) 17) |
(twosum (-3 -2 0 1 5 8 11) 17) |
||
(twosum (-8 -2 -1 1 5 9 11) 0) )</ |
(twosum (-8 -2 -1 1 5 9 11) 0) )</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>(2 . 4) NIL (3 . 4)</pre> |
<pre>(2 . 4) NIL (3 . 4)</pre> |
||
Line 1,915: | Line 1,915: | ||
=={{header|PowerShell}}== |
=={{header|PowerShell}}== |
||
Lazy, '''very''' lazy. |
Lazy, '''very''' lazy. |
||
<syntaxhighlight lang="powershell"> |
|||
<lang PowerShell> |
|||
$numbers = @(0, 2, 11, 19, 90) |
$numbers = @(0, 2, 11, 19, 90) |
||
$sum = 21 |
$sum = 21 |
||
Line 1,941: | Line 1,941: | ||
Expression = { @($_.FirstIndex, $_.SecondIndex) } |
Expression = { @($_.FirstIndex, $_.SecondIndex) } |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,951: | Line 1,951: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
{{trans|Raku}} |
{{trans|Raku}} |
||
< |
<syntaxhighlight lang="python">def two_sum(arr, num): |
||
i = 0 |
i = 0 |
||
j = len(arr) - 1 |
j = len(arr) - 1 |
||
Line 1,966: | Line 1,966: | ||
numbers = [0, 2, 11, 19, 90] |
numbers = [0, 2, 11, 19, 90] |
||
print(two_sum(numbers, 21)) |
print(two_sum(numbers, 21)) |
||
print(two_sum(numbers, 25))</ |
print(two_sum(numbers, 25))</syntaxhighlight> |
||
or, in terms of '''itertools.product''': |
or, in terms of '''itertools.product''': |
||
{{Works with|Python|3.7}} |
{{Works with|Python|3.7}} |
||
< |
<syntaxhighlight lang="python">'''Finding two integers that sum to a target value.''' |
||
from itertools import (product) |
from itertools import (product) |
||
Line 2,054: | Line 2,054: | ||
# MAIN --- |
# MAIN --- |
||
if __name__ == '__main__': |
if __name__ == '__main__': |
||
main()</ |
main()</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>The indices of any two integers drawn from [0, 2, 11, 19, 90, 10] |
<pre>The indices of any two integers drawn from [0, 2, 11, 19, 90, 10] |
||
Line 2,079: | Line 2,079: | ||
or, a little more parsimoniously (not generating the entire cartesian product), in terms of '''concatMap''': |
or, a little more parsimoniously (not generating the entire cartesian product), in terms of '''concatMap''': |
||
{{Works with|Python|3.7}} |
{{Works with|Python|3.7}} |
||
< |
<syntaxhighlight lang="python">'''Finding two integers that sum to a target value.''' |
||
from itertools import chain |
from itertools import chain |
||
Line 2,130: | Line 2,130: | ||
if __name__ == '__main__': |
if __name__ == '__main__': |
||
main()</ |
main()</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>[(1, 3), (2, 5)] |
<pre>[(1, 3), (2, 5)] |
||
Line 2,141: | Line 2,141: | ||
The last three lines of <code>task</code> are in case the two integers found by <code>twosum</code> are equal - in which case, as <code>find</code> finds the first instance in the array and the array is sorted, we can safely take the index plus one as the second index. |
The last three lines of <code>task</code> are in case the two integers found by <code>twosum</code> are equal - in which case, as <code>find</code> finds the first instance in the array and the array is sorted, we can safely take the index plus one as the second index. |
||
< |
<syntaxhighlight lang="quackery"> [ 0 peek ] is first ( [ --> n ) |
||
[ -1 peek ] is last ( [ --> n ) |
[ -1 peek ] is last ( [ --> n ) |
||
Line 2,173: | Line 2,173: | ||
' [ 0 2 11 19 20 ] 21 task echo cr |
' [ 0 2 11 19 20 ] 21 task echo cr |
||
' [ 0 2 11 19 20 ] 25 task echo cr |
' [ 0 2 11 19 20 ] 25 task echo cr |
||
' [ 0 2 12 12 20 ] 24 task echo cr</ |
' [ 0 2 12 12 20 ] 24 task echo cr</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,183: | Line 2,183: | ||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
< |
<syntaxhighlight lang="racket">#lang racket/base |
||
(define (two-sum v m) |
(define (two-sum v m) |
||
(let inr ((l 0) (r (sub1 (vector-length v)))) |
(let inr ((l 0) (r (sub1 (vector-length v)))) |
||
Line 2,198: | Line 2,198: | ||
(check-equal? (two-sum #(-8 -2 0 1 5 8 11) 3) '(0 6)) |
(check-equal? (two-sum #(-8 -2 0 1 5 8 11) 3) '(0 6)) |
||
(check-equal? (two-sum #(-3 -2 0 1 5 8 11) 17) #f) |
(check-equal? (two-sum #(-3 -2 0 1 5 8 11) 17) #f) |
||
(check-equal? (two-sum #(-8 -2 -1 1 5 9 11) 0) '(2 3)))</ |
(check-equal? (two-sum #(-8 -2 -1 1 5 9 11) 0) '(2 3)))</syntaxhighlight> |
||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
Line 2,205: | Line 2,205: | ||
===Procedural=== |
===Procedural=== |
||
{{trans|zkl}} |
{{trans|zkl}} |
||
<lang |
<syntaxhighlight lang="raku" line>sub two_sum ( @numbers, $sum ) { |
||
die '@numbers is not sorted' unless [<=] @numbers; |
die '@numbers is not sorted' unless [<=] @numbers; |
||
Line 2,220: | Line 2,220: | ||
say two_sum ( 0, 2, 11, 19, 90 ), 21; |
say two_sum ( 0, 2, 11, 19, 90 ), 21; |
||
say two_sum ( 0, 2, 11, 19, 90 ), 25;</ |
say two_sum ( 0, 2, 11, 19, 90 ), 25;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>(1 3) |
<pre>(1 3) |
||
Line 2,228: | Line 2,228: | ||
The two versions differ only in how one 'reads' the notional flow of processing: left-to-right versus right-to-left. |
The two versions differ only in how one 'reads' the notional flow of processing: left-to-right versus right-to-left. |
||
Both return all pairs that sum to the target value, not just the first (e.g. for input of <code>0 2 10 11 19 90</code> would get indices 1/4 and 2/3). |
Both return all pairs that sum to the target value, not just the first (e.g. for input of <code>0 2 10 11 19 90</code> would get indices 1/4 and 2/3). |
||
<lang |
<syntaxhighlight lang="raku" line>sub two-sum-lr (@a, $sum) { |
||
# (((^@a X ^@a) Z=> (@a X+ @a)).grep($sum == *.value)>>.keys.map:{ .split(' ').sort.join(' ')}).unique |
# (((^@a X ^@a) Z=> (@a X+ @a)).grep($sum == *.value)>>.keys.map:{ .split(' ').sort.join(' ')}).unique |
||
( |
( |
||
Line 2,253: | Line 2,253: | ||
say two-sum-rl(@a, $_); |
say two-sum-rl(@a, $_); |
||
say two-sum-lr(@a, $_); |
say two-sum-lr(@a, $_); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>(1 3) |
<pre>(1 3) |
||
Line 2,262: | Line 2,262: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
===version 1=== |
===version 1=== |
||
< |
<syntaxhighlight lang="rexx">/* REXX */ |
||
list='-5 26 0 2 11 19 90' |
list='-5 26 0 2 11 19 90' |
||
Do i=0 By 1 Until list='' |
Do i=0 By 1 Until list='' |
||
Line 2,282: | Line 2,282: | ||
Say '[] - no items found' |
Say '[] - no items found' |
||
Else |
Else |
||
Say z 'solutions found'</ |
Say z 'solutions found'</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[0,1] -5 26 21 |
<pre>[0,1] -5 26 21 |
||
Line 2,302: | Line 2,302: | ||
A little extra code was added to have the output columns aligned. |
A little extra code was added to have the output columns aligned. |
||
< |
<syntaxhighlight lang="rexx">/*REXX program finds two numbers in a list of numbers that sum to a particular target.*/ |
||
numeric digits 500 /*be able to handle some larger numbers*/ |
numeric digits 500 /*be able to handle some larger numbers*/ |
||
parse arg targ list /*obtain optional arguments from the CL*/ |
parse arg targ list /*obtain optional arguments from the CL*/ |
||
Line 2,325: | Line 2,325: | ||
say |
say |
||
if sol==0 then sol= 'None' /*prettify the number of solutions if 0*/ |
if sol==0 then sol= 'None' /*prettify the number of solutions if 0*/ |
||
say 'number of solutions found: ' sol /*stick a fork in it, we're all done. */</ |
say 'number of solutions found: ' sol /*stick a fork in it, we're all done. */</syntaxhighlight> |
||
{{out|output|text= when using the default inputs:}} |
{{out|output|text= when using the default inputs:}} |
||
<pre> |
<pre> |
||
Line 2,371: | Line 2,371: | ||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang="ring"> |
||
# Project : Two Sum |
# Project : Two Sum |
||
Line 2,391: | Line 2,391: | ||
next |
next |
||
next |
next |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
<pre> |
<pre> |
||
Line 2,400: | Line 2,400: | ||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
< |
<syntaxhighlight lang="ruby">def two_sum(numbers, sum) |
||
numbers.each_with_index do |x,i| |
numbers.each_with_index do |x,i| |
||
if j = numbers.index(sum - x) then return [i,j] end |
if j = numbers.index(sum - x) then return [i,j] end |
||
Line 2,409: | Line 2,409: | ||
numbers = [0, 2, 11, 19, 90] |
numbers = [0, 2, 11, 19, 90] |
||
p two_sum(numbers, 21) |
p two_sum(numbers, 21) |
||
p two_sum(numbers, 25)</ |
p two_sum(numbers, 25)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,418: | Line 2,418: | ||
When the size of the Array is bigger, the following is more suitable. |
When the size of the Array is bigger, the following is more suitable. |
||
< |
<syntaxhighlight lang="ruby">def two_sum(numbers, sum) |
||
numbers.each_with_index do |x,i| |
numbers.each_with_index do |x,i| |
||
key = sum - x |
key = sum - x |
||
Line 2,426: | Line 2,426: | ||
end |
end |
||
[] |
[] |
||
end</ |
end</syntaxhighlight> |
||
=={{header|Rust}}== |
=={{header|Rust}}== |
||
< |
<syntaxhighlight lang="rust">use std::cmp::Ordering; |
||
use std::ops::Add; |
use std::ops::Add; |
||
Line 2,459: | Line 2,459: | ||
println!("{:?}", two_sum(&arr, sum)); |
println!("{:?}", two_sum(&arr, sum)); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,467: | Line 2,467: | ||
=={{header|Scala}}== |
=={{header|Scala}}== |
||
< |
<syntaxhighlight lang="scala">import java.util |
||
object TwoSum extends App { |
object TwoSum extends App { |
||
Line 2,483: | Line 2,483: | ||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{Out}}See it running in your browser by [https://scalafiddle.io/sf/GxVfCE7/0 ScalaFiddle (JavaScript, non JVM)] or by [https://scastie.scala-lang.org/S5aks2gRTcqcy1VUWJ6GzQ Scastie (JVM)]. |
{{Out}}See it running in your browser by [https://scalafiddle.io/sf/GxVfCE7/0 ScalaFiddle (JavaScript, non JVM)] or by [https://scastie.scala-lang.org/S5aks2gRTcqcy1VUWJ6GzQ Scastie (JVM)]. |
||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
{{trans|Raku}} |
{{trans|Raku}} |
||
< |
<syntaxhighlight lang="ruby">func two_sum(numbers, sum) { |
||
var (i, j) = (0, numbers.end) |
var (i, j) = (0, numbers.end) |
||
while (i < j) { |
while (i < j) { |
||
Line 2,501: | Line 2,501: | ||
say two_sum([0, 2, 11, 19, 90], 21) |
say two_sum([0, 2, 11, 19, 90], 21) |
||
say two_sum([0, 2, 11, 19, 90], 25)</ |
say two_sum([0, 2, 11, 19, 90], 25)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,510: | Line 2,510: | ||
=={{header|Stata}}== |
=={{header|Stata}}== |
||
Notice that array indexes start at 1 in Stata. |
Notice that array indexes start at 1 in Stata. |
||
< |
<syntaxhighlight lang="stata">function find(a, x) { |
||
i = 1 |
i = 1 |
||
j = length(a) |
j = length(a) |
||
Line 2,525: | Line 2,525: | ||
+---------+ |
+---------+ |
||
1 | 2 4 | |
1 | 2 4 | |
||
+---------+</ |
+---------+</syntaxhighlight> |
||
=={{header|Vala}}== |
=={{header|Vala}}== |
||
< |
<syntaxhighlight lang="vala">void main() { |
||
int arr[] = { 0, 2, 11, 19, 90 }, sum = 21, i, j, check = 0; |
int arr[] = { 0, 2, 11, 19, 90 }, sum = 21, i, j, check = 0; |
||
Line 2,542: | Line 2,542: | ||
if (check == 0) |
if (check == 0) |
||
print("[]"); |
print("[]"); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[1,3]</pre> |
<pre>[1,3]</pre> |
||
=={{header|VBA}}== |
=={{header|VBA}}== |
||
< |
<syntaxhighlight lang="vb">Option Explicit |
||
Function two_sum(a As Variant, t As Integer) As Variant |
Function two_sum(a As Variant, t As Integer) As Variant |
||
Dim i, j As Integer |
Dim i, j As Integer |
||
Line 2,574: | Line 2,574: | ||
Call prnt(two_sum(Array(-3, -2, 0, 1, 5, 8, 11), 17)) |
Call prnt(two_sum(Array(-3, -2, 0, 1, 5, 8, 11), 17)) |
||
Call prnt(two_sum(Array(-8, -2, -1, 1, 5, 9, 11), 0)) |
Call prnt(two_sum(Array(-8, -2, -1, 1, 5, 9, 11), 0)) |
||
End Sub</ |
End Sub</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,586: | Line 2,586: | ||
=={{header|Visual Basic .NET}}== |
=={{header|Visual Basic .NET}}== |
||
{{trans|C#}} |
{{trans|C#}} |
||
< |
<syntaxhighlight lang="vbnet">Module Module1 |
||
Function TwoSum(numbers As Integer(), sum As Integer) As Integer() |
Function TwoSum(numbers As Integer(), sum As Integer) As Integer() |
||
Line 2,610: | Line 2,610: | ||
End Sub |
End Sub |
||
End Module</ |
End Module</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>1, 3</pre> |
<pre>1, 3</pre> |
||
Line 2,616: | Line 2,616: | ||
=={{header|Vlang}}== |
=={{header|Vlang}}== |
||
{{trans|Go}} |
{{trans|Go}} |
||
< |
<syntaxhighlight lang="vlang">fn two_sum(a []int, target_sum int) (int, int, bool) { |
||
len := a.len |
len := a.len |
||
if len < 2 { |
if len < 2 { |
||
Line 2,648: | Line 2,648: | ||
println("The numbers with indices $p1 and $p2 sum to $target_sum") |
println("The numbers with indices $p1 and $p2 sum to $target_sum") |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,658: | Line 2,658: | ||
{{trans|Python}} |
{{trans|Python}} |
||
{{works with|nasm}} |
{{works with|nasm}} |
||
< |
<syntaxhighlight lang="asm"> |
||
section .data |
section .data |
||
outputArr dd 0,0,0 |
outputArr dd 0,0,0 |
||
Line 2,700: | Line 2,700: | ||
mov eax, outputArr ;address of outputArr is returned in eax |
mov eax, outputArr ;address of outputArr is returned in eax |
||
ret |
ret |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
< |
<syntaxhighlight lang="ecmascript">var twosum = Fn.new { |a, n| |
||
var c = a.count |
var c = a.count |
||
if (c < 2) return [] |
if (c < 2) return [] |
||
Line 2,726: | Line 2,726: | ||
} |
} |
||
System.print() |
System.print() |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,741: | Line 2,741: | ||
=={{header|XPL0}}== |
=={{header|XPL0}}== |
||
Test cases from Algol 68. |
Test cases from Algol 68. |
||
< |
<syntaxhighlight lang="xpl0">proc TwoSum(Size, Array, Sum); |
||
int Size, Array, Sum, I, J; |
int Size, Array, Sum, I, J; |
||
[Text(0, "["); |
[Text(0, "["); |
||
Line 2,757: | Line 2,757: | ||
TwoSum(7, [-3, -2, 0, 1, 5, 8, 11], 17); \ should be [] |
TwoSum(7, [-3, -2, 0, 1, 5, 8, 11], 17); \ should be [] |
||
TwoSum(7, [-8, -2, -1, 1, 5, 9, 11], 0); \ should be [2, 3] |
TwoSum(7, [-8, -2, -1, 1, 5, 9, 11], 0); \ should be [2, 3] |
||
]</ |
]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,769: | Line 2,769: | ||
=={{header|Yabasic}}== |
=={{header|Yabasic}}== |
||
{{trans|FreeBASIC}} |
{{trans|FreeBASIC}} |
||
< |
<syntaxhighlight lang="yabasic">// Rosetta Code problem: http://rosettacode.org/wiki/Two_sum |
||
// by Galileo, 04/2022 |
// by Galileo, 04/2022 |
||
Line 2,805: | Line 2,805: | ||
Else |
Else |
||
Print "The numbers with indices ", b(1), " and ", b(2), " sum to ", targetSum |
Print "The numbers with indices ", b(1), " and ", b(2), " sum to ", targetSum |
||
End If</ |
End If</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>The numbers with indices 2 and 4 sum to 21 |
<pre>The numbers with indices 2 and 4 sum to 21 |
||
Line 2,812: | Line 2,812: | ||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
The sorted O(n) no external storage solution: |
The sorted O(n) no external storage solution: |
||
< |
<syntaxhighlight lang="zkl">fcn twoSum(sum,ns){ |
||
i,j:=0,ns.len()-1; |
i,j:=0,ns.len()-1; |
||
while(i<j){ |
while(i<j){ |
||
Line 2,819: | Line 2,819: | ||
else if(s>sum) j-=1; |
else if(s>sum) j-=1; |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
< |
<syntaxhighlight lang="zkl">twoSum2(21,T(0,2,11,19,90)).println(); |
||
twoSum2(25,T(0,2,11,19,90)).println();</ |
twoSum2(25,T(0,2,11,19,90)).println();</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,828: | Line 2,828: | ||
</pre> |
</pre> |
||
The unsorted O(n!) all solutions solution: |
The unsorted O(n!) all solutions solution: |
||
< |
<syntaxhighlight lang="zkl">fcn twoSum2(sum,ns){ |
||
Utils.Helpers.combosKW(2,ns).filter('wrap([(a,b)]){ a+b==sum }) // lazy combos |
Utils.Helpers.combosKW(2,ns).filter('wrap([(a,b)]){ a+b==sum }) // lazy combos |
||
.apply('wrap([(a,b)]){ return(ns.index(a),ns.index(b)) }) |
.apply('wrap([(a,b)]){ return(ns.index(a),ns.index(b)) }) |
||
}</ |
}</syntaxhighlight> |
||
< |
<syntaxhighlight lang="zkl">twoSum2(21,T(0,2,11,19,90,21)).println(); |
||
twoSum2(25,T(0,2,11,19,90,21)).println();</ |
twoSum2(25,T(0,2,11,19,90,21)).println();</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |