Two sum: Difference between revisions
m
→{{header|Wren}}: Changed to Wren S/H
Jazzedpineda (talk | contribs) (Added EasyLang implementation) |
m (→{{header|Wren}}: Changed to Wren S/H) |
||
| (9 intermediate revisions by 6 users not shown) | |||
Line 1:
{{
Line 42:
[1, 3]
[]
</pre>
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits <br> or android 64 bits with application Termux }}
<syntaxhighlight lang AArch64 Assembly>
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program twosum64.s */
/************************************/
/* Constantes */
/************************************/
.include "../includeConstantesARM64.inc"
/*********************************/
/* Initialized data */
/*********************************/
.data
szMessResult: .asciz "Result : ["
szMessResult1: .asciz ","
szMessResult2: .asciz "]\n"
szMessStart: .asciz "Program 64 bits start.\n"
szCarriageReturn: .asciz "\n"
szMessErreur: .asciz "No soluce ! \n"
tabArray: .quad 0, 2, 11, 19, 90
.equ TABARRAYSIZE, (. - tabArray) / 8
/*********************************/
/* UnInitialized data */
/*********************************/
.bss
sZoneConv: .skip 24
sZoneConv1: .skip 24
/*********************************/
/* code section */
/*********************************/
.text
.global main
main: // entry of program
ldr x0,qAdrszMessStart
bl affichageMess
ldr x0,qAdrtabArray
mov x1,#21
bl rechTwoNumbers
cmp x0,#-1 // no soluce
beq 100f
mov x2,x1
ldr x1,qAdrsZoneConv
bl conversion10 // decimal conversion
strb wzr,[x1,x0]
mov x0,x2
ldr x1,qAdrsZoneConv1
bl conversion10 // decimal conversion
strb wzr,[x1,x0]
mov x0,#5 // number string to display
ldr x1,qAdrszMessResult
ldr x2,qAdrsZoneConv // insert conversion in message
ldr x3,qAdrszMessResult1
ldr x4,qAdrsZoneConv1
ldr x5,qAdrszMessResult2
stp x5,x4,[sp,-16]! // save registers
bl displayStrings // display message
add sp,sp,#16
100: // standard end of the program
mov x0, #0 // return code
mov x8,EXIT
svc #0 // perform the system call
qAdrszCarriageReturn: .quad szCarriageReturn
qAdrsZoneConv: .quad sZoneConv
qAdrsZoneConv1: .quad sZoneConv1
qAdrszMessResult: .quad szMessResult
qAdrszMessResult1: .quad szMessResult1
qAdrszMessResult2: .quad szMessResult2
qAdrszMessErreur: .quad szMessErreur
qAdrszMessStart: .quad szMessStart
qAdrtabArray: .quad tabArray
/******************************************************************/
/* search two numbers to sum */
/******************************************************************/
/* x0 array addressr */
/* x1 sum */
/* x0 return first index */
/* x1 return second index */
rechTwoNumbers:
stp x2,lr,[sp,-16]! // save registers
stp x3,x4,[sp,-16]! // save registers
stp x5,x6,[sp,-16]! // save registers
stp x7,x8,[sp,-16]! // save registers
mov x3,#0 // init result
1: // loop
ldr x4,[x0,x3,lsl #3] // load first number
mov x5,x3 // indice2
2:
ldr x6,[x0,x5,lsl #3] // load 2th number
add x7,x6,x4 // add the two numbers
cmp x7,x1 // equal to origin
beq 3f // yes -> ok
add x5,x5,#1 // increment indice2
cmp x5,#TABARRAYSIZE // end ?
blt 2b // no -> loop
add x3,x3,#1 // increment indice1
cmp x3,#TABARRAYSIZE - 1 // end ?
blt 1b // no loop
// not found
ldr x0,qAdrszMessErreur
bl affichageMess
mov x0,#-1
mov x1,#-1
b 100f // end
3:
mov x0,x3 // return results
mov x1,x5
100:
ldp x7,x8,[sp],16 // restaur registers
ldp x5,x6,[sp],16 // restaur registers
ldp x3,x4,[sp],16 // restaur registers
ldp x2,lr,[sp],16 // restaur registers
ret
/***************************************************/
/* display multi strings */
/***************************************************/
/* x0 contains number strings address */
/* x1 address string1 */
/* x2 address string2 */
/* x3 address string3 */
/* other address on the stack */
/* thinck to add number other address * 4 to add to the stack */
displayStrings: // INFO: displayStrings
stp x1,lr,[sp,-16]! // save registers
stp x2,x3,[sp,-16]! // save registers
stp x4,x5,[sp,-16]! // save registers
add fp,sp,#48 // save paraméters address (6 registers saved * 8 bytes)
mov x4,x0 // save strings number
cmp x4,#0 // 0 string -> end
ble 100f
mov x0,x1 // string 1
bl affichageMess
cmp x4,#1 // number > 1
ble 100f
mov x0,x2
bl affichageMess
cmp x4,#2
ble 100f
mov x0,x3
bl affichageMess
cmp x4,#3
ble 100f
mov x3,#3
sub x2,x4,#4
1: // loop extract address string on stack
ldr x0,[fp,x2,lsl #3]
bl affichageMess
subs x2,x2,#1
bge 1b
100:
ldp x4,x5,[sp],16 // restaur registers
ldp x2,x3,[sp],16 // restaur registers
ldp x1,lr,[sp],16 // restaur registers
ret
/***************************************************/
/* ROUTINES INCLUDE */
/***************************************************/
.include "../includeARM64.inc"
</syntaxhighlight>
{{Out}}
<pre>
Program 64 bits start.
Result : [1,3]
</pre>
Line 397 ⟶ 564:
{}
{{1, 11}, {2, 8}, {2, 9}, {2, 10}, {3, 8}, {3, 9}, {3, 10}, {4, 7}, {5, 6}}</syntaxhighlight>
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi <br> or android 32 bits with application Termux}}
<syntaxhighlight lang ARM Assembly>
/* ARM assembly Raspberry PI */
/* program twosum.s */
/* REMARK 1 : this program use routines in a include file
see task Include a file language arm assembly
for the routine affichageMess conversion10
see at end of this program the instruction include */
/* for constantes see task include a file in arm assembly */
/************************************/
/* Constantes */
/************************************/
.include "../constantes.inc"
/*********************************/
/* Initialized data */
/*********************************/
.data
szMessResult: .asciz "Result : ["
szMessResult1: .asciz ","
szMessResult2: .asciz "]\n"
szMessStart: .asciz "Program 32 bits start.\n"
szCarriageReturn: .asciz "\n"
szMessErreur: .asciz "No soluce ! \n"
tabArray: .int 0, 2, 11, 19, 90
.equ TABARRAYSIZE, (. - tabArray) / 4
/*********************************/
/* UnInitialized data */
/*********************************/
.bss
sZoneConv: .skip 24
sZoneConv1: .skip 24
/*********************************/
/* code section */
/*********************************/
.text
.global main
main: @ entry of program
ldr r0,iAdrszMessStart
bl affichageMess
ldr r0,iAdrtabArray
mov r1,#21
bl rechTwoNumbers
cmp r0,#-1 @ no soluce
beq 100f
mov r2,r1
ldr r1,iAdrsZoneConv
bl conversion10 @ decimal conversion
mov r3,#0
strb r3,[r1,r0]
mov r0,r2
ldr r1,iAdrsZoneConv1
bl conversion10 @ decimal conversion
mov r3,#0
strb r3,[r1,r0]
mov r0,#5 @ number string to display
ldr r1,iAdrszMessResult
ldr r2,iAdrsZoneConv @ insert conversion in message
ldr r3,iAdrszMessResult1
ldr r4,iAdrsZoneConv1
push {r4}
ldr r4,iAdrszMessResult2
push {r4}
bl displayStrings @ display message
add sp,#8
100: @ standard end of the program
mov r0, #0 @ return code
mov r7, #EXIT @ request to exit program
svc #0 @ perform the system call
iAdrszCarriageReturn: .int szCarriageReturn
iAdrsZoneConv: .int sZoneConv
iAdrsZoneConv1: .int sZoneConv1
iAdrszMessResult: .int szMessResult
iAdrszMessResult1: .int szMessResult1
iAdrszMessResult2: .int szMessResult2
iAdrszMessErreur: .int szMessErreur
iAdrszMessStart: .int szMessStart
iAdrtabArray: .int tabArray
/******************************************************************/
/* search two numbers from sum */
/******************************************************************/
/* r0 array addressr */
/* r1 sum */
/* r0 return fist index */
/* r1 return second index */
rechTwoNumbers:
push {r2-r7,lr} @ save registers
mov r3,#0 @ init result
1: @ loop
ldr r4,[r0,r3,lsl #2] @ load first number
mov r5,r3 @ indice2
2:
ldr r6,[r0,r5,lsl #2] @ load 2th number
add r7,r6,r4 @ add the two numbers
cmp r7,r1 @ equal to origin
beq 3f @ yes -> ok
add r5,r5,#1 @ increment indice2
cmp r5,#TABARRAYSIZE @ end ?
blt 2b @ no -> loop
add r3,r3,#1 @ increment indice1
cmp r3,#TABARRAYSIZE - 1 @ end ?
blt 1b @ no loop
@ not found
ldr r0,iAdrszMessErreur
bl affichageMess
mov r0,#-1
mov r1,#-1
b 100f @ end
3:
mov r0,r3 @ return results
mov r1,r5
100:
pop {r2-r7,pc}
/***************************************************/
/* display multi strings */
/***************************************************/
/* r0 contains number strings address */
/* r1 address string1 */
/* r2 address string2 */
/* r3 address string3 */
/* other address on the stack */
/* thinck to add number other address * 4 to add to the stack */
displayStrings: @ INFO: displayStrings
push {r1-r4,fp,lr} @ save des registres
add fp,sp,#24 @ save paraméters address (6 registers saved * 4 bytes)
mov r4,r0 @ save strings number
cmp r4,#0 @ 0 string -> end
ble 100f
mov r0,r1 @ string 1
bl affichageMess
cmp r4,#1 @ number > 1
ble 100f
mov r0,r2
bl affichageMess
cmp r4,#2
ble 100f
mov r0,r3
bl affichageMess
cmp r4,#3
ble 100f
mov r3,#3
sub r2,r4,#4
1: @ loop extract address string on stack
ldr r0,[fp,r2,lsl #2]
bl affichageMess
subs r2,#1
bge 1b
100:
pop {r1-r4,fp,pc}
/***************************************************/
/* ROUTINES INCLUDE */
/***************************************************/
.include "../affichage.inc"
</syntaxhighlight>
{{Out}}
<pre>
Program 32 bits start.
Result : [1,3]
</pre>
=={{header|Arturo}}==
Line 721 ⟶ 1,052:
EasyLang arrays are one-based, so the indices returned are also one-based.
<syntaxhighlight lang="easylang">
i = 1
j = len array[]
pair[] = [ ]
repeat
if array[i] + array[j] = sum
pair[] = [ i j ]
elif array[i] + array[j] > sum
j -= 1
Line 739 ⟶ 1,069:
.
numbers[] = [ 0 2 11 19 90 ]
print
</syntaxhighlight>
{{out}}
<pre>[ 2
=={{header|Elixir}}==
Line 808 ⟶ 1,138:
{ 0 2 }
</pre>
A version that maintains a point-free style while still iterating over the numbers once:
<syntaxhighlight lang="factor">USING: accessors arrays assocs combinators.extras hashtables
kernel math math.combinatorics sequences ;
IN: rosetta-code.two-sum
DEFER: (two-sum)
TUPLE: helper sum seq index hash ;
: <two-sum-helper> ( sum seq -- helper )
\ helper new
swap [ >>seq ] keep length <hashtable> >>hash
swap >>sum 0 >>index ;
: no-sum ( helper -- empty ) drop { } ;
: in-bounds? ( helper -- ? )
[ index>> ] [ seq>> length ] bi < ;
: next-sum ( helper -- pair )
dup in-bounds? [ (two-sum) ] [ no-sum ] if ;
: next-index ( helper -- helper ) [ 1 + ] change-index ;
: result ( helper index -- helper ) swap index>> 2array ;
: find-compliment-index ( helper -- helper index/f )
dup [ sum>> ] [ index>> ] [ seq>> nth - ] [ ] quad hash>> at ;
: remember-item ( helper -- helper )
dup [ hash>> ] [ index>> ] [ seq>> nth ] [ index>> ]
quad set-of drop ;
: (two-sum) ( helper -- pair )
remember-item find-compliment-index
[ result ] [ next-index next-sum ] if* ;
: two-sum ( sum seq -- pair ) <two-sum-helper> (two-sum) ;
MAIN: [ { 21 55 11 } [ { 0 2 11 19 90 } two-sum . ] each ]
</syntaxhighlight>
=={{header|Forth}}==
Line 2,425 ⟶ 2,797:
target sum: 21
a solution: [1 3]
</pre>
=={{header|RPL}}==
≪ → array sum
≪ { }
1 array SIZE '''FOR''' j
array j 0 PUT
sum array j GET -
'''IF''' POS '''THEN'''
j LAST
'''IF''' DUP2 > '''THEN''' SWAP '''END'''
R→C
'''IF''' DUP2 POS '''THEN''' DROP '''ELSE''' + '''END'''
'''END NEXT'''
≫ ≫ ‘<span style="color:blue">TWOSUM</span>’ STO
{0 2 11 19 90} 21 <span style="color:blue">TWOSUM</span>
{0 2 11 19 90} 22 <span style="color:blue">TWOSUM</span>
{0 2 3 3 4 11 17 17 18 19 90} 21 <span style="color:blue">TWOSUM</span>
{{out}}
<pre>
3: { (2,4) }
2: { }
1: { (2,10) (3,9) (4,9) (5,7) (5,8) }
</pre>
Line 2,644 ⟶ 3,040:
=={{header|V (Vlang)}}==
{{trans|Go}}
<syntaxhighlight lang="v (vlang)">
fn two_sum(a []int, target_sum int) (int, int, bool) {
len := a.len
if len < 2 {return 0, 0, false}
for i in 0..len - 1 {
if a[i] <= target_sum {
for j in i + 1..len {
sum := a[i] + a[j]
if sum == target_sum {return i, j, true}
if sum > target_sum
}
}
else
}
return 0, 0, false
Line 2,671 ⟶ 3,061:
target_sum := 21
p1, p2, ok := two_sum(a, target_sum)
if !ok {println("No two numbers were found whose sum is $target_sum")}
else
}
</syntaxhighlight>
{{out}}
Line 2,731 ⟶ 3,119:
=={{header|Wren}}==
<syntaxhighlight lang="
var c = a.count
if (c < 2) return []
Line 2,837 ⟶ 3,225:
<pre>The numbers with indices 2 and 4 sum to 21
---Program done, press RETURN---</pre>
=={{header|Zig}}==
'''Works with:''' 0.11.x, 0.12.0-dev.1389+42d4d07ef
<syntaxhighlight lang="zig">pub fn sumsUpTo(comptime T: type, input: []const T, target_sum: T) ?struct { usize, usize } {
if (input.len <= 1) return null;
return result: for (input[0 .. input.len - 1], 0..) |left, left_i| {
if (left > target_sum) break :result null;
const offset = left_i + 1;
for (input[offset..], offset..) |right, right_i| {
const current_sum = left + right;
if (current_sum < target_sum) continue;
if (current_sum == target_sum) break :result .{ left_i, right_i };
if (current_sum > target_sum) break;
}
} else null;
}</syntaxhighlight>
<syntaxhighlight lang="zig">const std = @import("std");
pub fn main() std.fs.File.WriteError!void {
const stdout = std.io.getStdOut();
const stdout_w = stdout.writer();
const stderr = std.io.getStdErr();
const stderr_w = stderr.writer();
const a = [_]u32{ 0, 2, 11, 19, 90 };
const target_sum: u32 = 21;
const optional_indexes = sumsUpTo(u32, &a, target_sum);
if (optional_indexes) |indexes| {
try stdout_w.print("Result: [{d}, {d}].\n", .{ indexes[0], indexes[1] });
} else {
try stderr_w.print("Numbers with sum {d} were not found!\n", .{target_sum});
}
}</syntaxhighlight>
{{Out}}
<pre>
Result: [1, 3].
</pre>
=={{header|zkl}}==
| |||