Last list item
From Rosetta Code
Last list item is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
- Task
List = [6, 81, 243, 14, 25, 49, 123, 69, 11]
Find the two smallest items, remove them from the list, find their sum, and add the sum to the end of list.
Repeat until the list contains one element.
Show the steps and last item on this page.
Show the unsorted list in output in case "Without sort"
Contents
ALGOL 68[edit]
With sorting[edit]
BEGIN # find the last element after repeatedely adding the sum #
# of the two smallest elements and removing them #
# Quicksorts in-place the array of integers a, from lb to ub #
PROC quicksort = ( REF[]INT a, INT lb, ub )VOID:
IF ub > lb THEN
# more than one element, so must sort #
INT left := lb;
INT right := ub;
# choosing the middle element of the array as the pivot #
INT pivot := a[ left + ( ( right + 1 ) - left ) OVER 2 ];
WHILE
WHILE IF left <= ub THEN a[ left ] < pivot ELSE FALSE FI DO left +:= 1 OD;
WHILE IF right >= lb THEN a[ right ] > pivot ELSE FALSE FI DO right -:= 1 OD;
left <= right
DO
INT t := a[ left ];
a[ left ] := a[ right ];
a[ right ] := t;
left +:= 1;
right -:= 1
OD;
quicksort( a, lb, right );
quicksort( a, left, ub )
FI # quicksort # ;
[ 1 : 9 ]INT a := ( 6, 81, 243, 14, 25, 49, 123, 69, 11 );
INT a count := UPB a;
WHILE a count > 1 DO
quicksort( a, LWB a, a count );
print( ( "Sorted list:" ) );FOR i TO a count DO print( ( " ", whole( a[ i ], 0 ) ) ) OD;
INT sum = a[ 1 ] + a[ 2 ];
print( ( "; two smallest: " , whole( a[ 1 ], 0 )
, " + ", whole( a[ 2 ], 0 )
, " = ", whole( sum, 0 )
, newline
)
);
a[ 1 : a count - 2 ] := a[ 3 : a count ];
a count -:= 1 ;
a[ a count ] := sum
OD;
print( ( "Last item is ", whole( a[ 1 ], 0 ), ".", newline ) )
END
- Output:
Sorted list: 6 11 14 25 49 69 81 123 243; two smallest: 6 + 11 = 17 Sorted list: 14 17 25 49 69 81 123 243; two smallest: 14 + 17 = 31 Sorted list: 25 31 49 69 81 123 243; two smallest: 25 + 31 = 56 Sorted list: 49 56 69 81 123 243; two smallest: 49 + 56 = 105 Sorted list: 69 81 105 123 243; two smallest: 69 + 81 = 150 Sorted list: 105 123 150 243; two smallest: 105 + 123 = 228 Sorted list: 150 228 243; two smallest: 150 + 228 = 378 Sorted list: 243 378; two smallest: 243 + 378 = 621 Last item is 621.
Without sorting[edit]
Translation of the sorted Wren version with the sorting removed.
BEGIN # find the last element after repeatedly adding the sum #
# of the two smallest elements and removing them #
[ 1 : 9 ]INT a := ( 6, 81, 243, 14, 25, 49, 123, 69, 11 );
INT a count := UPB a;
WHILE a count > 1 DO
print( ( "List:" ) );FOR i TO a count DO print( ( " ", whole( a[ i ], 0 ) ) ) OD;
INT s1pos, s2pos;
IF a[ 1 ] < a[ 2 ]
THEN s1pos := 1; s2pos := 2
ELSE s1pos := 2; s2pos := 1
FI;
FOR i FROM 3 TO a count DO
IF a[ i ] < a[ s1pos ] THEN s2pos := s1pos; s1pos := i
ELIF a[ i ] < a[ s2pos ] THEN s2pos := i
FI
OD;
INT sum = a[ s1pos ] + a[ s2pos ];
print( ( "; two smallest: " , whole( a[ s1pos ], 0 ), " @ ", whole( s1pos, 0 )
, " and ", whole( a[ s2pos ], 0 ), " @ ", whole( s2pos, 0 )
, "; sum = ", whole( sum, 0 )
, newline
)
);
INT m pos := 0;
FOR i TO a count DO
IF i /= s1pos AND i /= s2pos THEN a[ m pos +:= 1 ] := a[ i ] FI
OD;
a[ m pos + 1 ] := sum;
a count -:= 1
OD;
print( ( "Last item is ", whole( a[ 1 ], 0 ), ".", newline ) )
END
- Output:
List: 6 81 243 14 25 49 123 69 11; two smallest: 6 @ 1 and 11 @ 9; sum = 17 List: 81 243 14 25 49 123 69 17; two smallest: 14 @ 3 and 17 @ 8; sum = 31 List: 81 243 25 49 123 69 31; two smallest: 25 @ 3 and 31 @ 7; sum = 56 List: 81 243 49 123 69 56; two smallest: 49 @ 3 and 56 @ 6; sum = 105 List: 81 243 123 69 105; two smallest: 69 @ 4 and 81 @ 1; sum = 150 List: 243 123 105 150; two smallest: 105 @ 3 and 123 @ 2; sum = 228 List: 243 150 228; two smallest: 150 @ 2 and 228 @ 3; sum = 378 List: 243 378; two smallest: 243 @ 1 and 378 @ 2; sum = 621 Last item is 621.
AutoHotkey[edit]
List := [6, 81, 243, 14, 25, 49, 123, 69, 11]
steps := "Initial List `t`t`t" List2str(List) "`n"
while List.Count() > 1
{
sum := 0, str := ""
loop 2
{
num := min(List*)
sum += num
removeFromList(List, num)
str .= (!str ? "2 smallest numbers: " : " + ") num
}
List.Push(sum)
steps .= str " = " sum "`t" List2str(List) "`n"
}
MsgBox % result := steps
return
removeFromList(ByRef List, num){
for i, v in List
if (v = num)
{
List.RemoveAt(i)
break
}
}
List2str(List){
for i, v in List
unsorted_List .= v ", "
return "[" Trim(unsorted_List, ", ") "]"
}
- Output:
Initial List [6, 81, 243, 14, 25, 49, 123, 69, 11] 2 smallest numbers: 6 + 11 = 17 [81, 243, 14, 25, 49, 123, 69, 17] 2 smallest numbers: 14 + 17 = 31 [81, 243, 25, 49, 123, 69, 31] 2 smallest numbers: 25 + 31 = 56 [81, 243, 49, 123, 69, 56] 2 smallest numbers: 49 + 56 = 105 [81, 243, 123, 69, 105] 2 smallest numbers: 69 + 81 = 150 [243, 123, 105, 150] 2 smallest numbers: 105 + 123 = 228 [243, 150, 228] 2 smallest numbers: 150 + 228 = 378 [243, 378] 2 smallest numbers: 243 + 378 = 621 [621]
AWK[edit]
# syntax: GAWK -f LAST_LIST_ITEM.AWK
BEGIN {
split("6,81,243,14,25,49,123,69,11",arr1,",")
PROCINFO["sorted_in"] = "@val_num_asc"
while (length(arr1) > 1) {
for (i in arr1) { printf("%s ",arr1[i]) } # show sorted list
j = 0
delete arr2
for (i in arr1) { arr2[++j] = arr1[i] } # copy arr1 into arr2
sum = arr2[1] + arr2[2]
printf(": %s+%s=%s\n",arr2[1],arr2[2],sum)
delete arr2[2]
arr2[1] = sum
delete arr1
for (i in arr2) { arr1[i] = arr2[i] } # copy arr2 into arr1
}
printf("sum=%d\n",sum)
exit(0)
}
- Output:
6 11 14 25 49 69 81 123 243 : 6+11=17 14 17 25 49 69 81 123 243 : 14+17=31 25 31 49 69 81 123 243 : 25+31=56 49 56 69 81 123 243 : 49+56=105 69 81 105 123 243 : 69+81=150 105 123 150 243 : 105+123=228 150 228 243 : 150+228=378 243 378 : 243+378=621 sum=621
C[edit]
With sorting[edit]
#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
int aa = *(const int *)a;
int bb = *(const int *)b;
if (aa < bb) return -1;
if (aa > bb) return 1;
return 0;
}
int main() {
int a[] = {6, 81, 243, 14, 25, 49, 123, 69, 11};
int isize = sizeof(int);
int asize = sizeof(a) / isize;
int i, sum;
while (asize > 1) {
qsort(a, asize, isize, compare);
printf("Sorted list: ");
for (i = 0; i < asize; ++i) printf("%d ", a[i]);
printf("\n");
sum = a[0] + a[1];
printf("Two smallest: %d + %d = %d\n", a[0], a[1], sum);
for (i = 2; i < asize; ++i) a[i-2] = a[i];
a[asize - 2] = sum;
asize--;
}
printf("Last item is %d.\n", a[0]);
return 0;
}
- Output:
Sorted list: 6 11 14 25 49 69 81 123 243 Two smallest: 6 + 11 = 17 Sorted list: 14 17 25 49 69 81 123 243 Two smallest: 14 + 17 = 31 Sorted list: 25 31 49 69 81 123 243 Two smallest: 25 + 31 = 56 Sorted list: 49 56 69 81 123 243 Two smallest: 49 + 56 = 105 Sorted list: 69 81 105 123 243 Two smallest: 69 + 81 = 150 Sorted list: 105 123 150 243 Two smallest: 105 + 123 = 228 Sorted list: 150 228 243 Two smallest: 150 + 228 = 378 Sorted list: 243 378 Two smallest: 243 + 378 = 621 Last item is 621.
Without sorting[edit]
#include <stdio.h>
int findMin(int a[], int asize, int *pmin) {
int i, ix = 0;
*pmin = a[0];
for (i = 0; i < asize; ++i) {
if (a[i] < *pmin) {
ix = i;
*pmin = a[i];
}
}
return ix;
}
int main() {
int a[] = {6, 81, 243, 14, 25, 49, 123, 69, 11};
int isize = sizeof(int);
int asize = sizeof(a) / isize;
int i, j, sum, ix, min = 0, s[2];
while (asize > 1) {
printf("List: ");
for (i = 0; i < asize; ++i) printf("%d ", a[i]);
printf("\n");
for (i = 0; i < 2; ++i) {
ix = findMin(a, asize, &min);
s[i] = min;
for (j = ix+1; j < asize; ++j) a[j-1] = a[j];
asize--;
}
sum = s[0] + s[1];
printf("Two smallest: %d + %d = %d\n", s[0], s[1], sum);
a[asize] = sum;
asize++;
}
printf("Last item is %d.\n", a[0]);
return 0;
}
- Output:
List: 6 81 243 14 25 49 123 69 11 Two smallest: 6 + 11 = 17 List: 81 243 14 25 49 123 69 17 Two smallest: 14 + 17 = 31 List: 81 243 25 49 123 69 31 Two smallest: 25 + 31 = 56 List: 81 243 49 123 69 56 Two smallest: 49 + 56 = 105 List: 81 243 123 69 105 Two smallest: 69 + 81 = 150 List: 243 123 105 150 Two smallest: 105 + 123 = 228 List: 243 150 228 Two smallest: 150 + 228 = 378 List: 243 378 Two smallest: 243 + 378 = 621 Last item is 621.
Factor[edit]
USING: formatting io kernel math math.statistics prettyprint
sequences sequences.extras ;
: list. ( seq -- )
"List: " write [ bl ] [ pprint ] interleave nl ;
: smallest. ( seq -- )
first2 2dup + "Two smallest: %d + %d = %d\n" printf ;
: remove-all-first! ( seq elts -- seq' )
[ swap remove-first! ] each ;
: step ( seq -- seq' )
dup { 0 1 } kth-smallests tuck remove-all-first! over
smallest. swap sum suffix! ;
V{ 6 81 243 14 25 49 123 69 11 }
[ dup length 1 > ] [ dup list. step ] while
last "Last item is %d.\n" printf
- Output:
List: 6 81 243 14 25 49 123 69 11 Two smallest: 6 + 11 = 17 List: 81 243 14 25 49 123 69 17 Two smallest: 14 + 17 = 31 List: 81 243 25 49 123 69 31 Two smallest: 25 + 31 = 56 List: 81 243 49 123 69 56 Two smallest: 49 + 56 = 105 List: 81 243 123 69 105 Two smallest: 69 + 81 = 150 List: 243 123 105 150 Two smallest: 105 + 123 = 228 List: 243 150 228 Two smallest: 150 + 228 = 378 List: 243 378 Two smallest: 243 + 378 = 621 Last item is 621.
FreeBASIC[edit]
#define HUGE 99999999
redim as integer list(0 to 8)
list(0) = 6 :list(1) = 81:list(2) = 243:list(3) = 14:list(4) = 25:list(5) = 49:list(6) = 123:list(7) = 69:list(8) = 11
dim as integer s, si, ss, ssi, i
for i = 0 to ubound(list)
print list(i);" ";
next i
while ubound(list) > 0
s = HUGE
ss = HUGE
for i = 0 to ubound(list)
if list(i)<s then
ss = s
ssi = si
s = list(i)
si = i
elseif list(i)<ss then
ss = list(i)
ssi = i
end if
next i
if ss<s then swap s, ss
for i = si to ubound(list)-1
list(i) = list(i+1)
next i
for i = ssi to ubound(list)-2
list(i) = list(i+1)
next i
list(ubound(list)-1) = s+ss
redim preserve list(0 to ubound(list)-1)
for i = 0 to ubound(list)
print list(i);" ";
next i
wend
- Output:
6 81 243 14 25 49 123 69 11 81 243 14 25 49 123 69 17 81 243 25 49 123 69 31 81 243 49 123 69 56 81 243 123 69 105 243 123 105 150 243 150 228 243 378 621
Go[edit]
With sorting[edit]
package main
import (
"fmt"
"sort"
)
func main() {
a := []int{6, 81, 243, 14, 25, 49, 123, 69, 11}
for len(a) > 1 {
sort.Ints(a)
fmt.Println("Sorted list:", a)
sum := a[0] + a[1]
fmt.Printf("Two smallest: %d + %d = %d\n", a[0], a[1], sum)
a = append(a, sum)
a = a[2:]
}
fmt.Println("Last item is", a[0], "\b.")
}
- Output:
Sorted list: [6 11 14 25 49 69 81 123 243] Two smallest: 6 + 11 = 17 Sorted list: [14 17 25 49 69 81 123 243] Two smallest: 14 + 17 = 31 Sorted list: [25 31 49 69 81 123 243] Two smallest: 25 + 31 = 56 Sorted list: [49 56 69 81 123 243] Two smallest: 49 + 56 = 105 Sorted list: [69 81 105 123 243] Two smallest: 69 + 81 = 150 Sorted list: [105 123 150 243] Two smallest: 105 + 123 = 228 Sorted list: [150 228 243] Two smallest: 150 + 228 = 378 Sorted list: [243 378] Two smallest: 243 + 378 = 621 Last item is 621.
Without sorting[edit]
package main
import "fmt"
func findMin(a []int) (int, int) {
ix := 0
min := a[0]
for i := 1; i < len(a); i++ {
if a[i] < min {
ix = i
min = a[i]
}
}
return min, ix
}
func main() {
a := []int{6, 81, 243, 14, 25, 49, 123, 69, 11}
for len(a) > 1 {
fmt.Println("List:", a)
var s [2]int
for i := 0; i < 2; i++ {
min, ix := findMin(a)
s[i] = min
a = append(a[:ix], a[ix+1:]...)
}
sum := s[0] + s[1]
fmt.Printf("Two smallest: %d + %d = %d\n", s[0], s[1], sum)
a = append(a, sum)
}
fmt.Println("Last item is", a[0], "\b.")
}
- Output:
List: [6 81 243 14 25 49 123 69 11] Two smallest: 6 + 11 = 17 List: [81 243 14 25 49 123 69 17] Two smallest: 14 + 17 = 31 List: [81 243 25 49 123 69 31] Two smallest: 25 + 31 = 56 List: [81 243 49 123 69 56] Two smallest: 49 + 56 = 105 List: [81 243 123 69 105] Two smallest: 69 + 81 = 150 List: [243 123 105 150] Two smallest: 105 + 123 = 228 List: [243 150 228] Two smallest: 150 + 228 = 378 List: [243 378] Two smallest: 243 + 378 = 621 Last item is 621.
Julia[edit]
list = [6, 81, 243, 14, 25, 49, 123, 69, 11]
function addleastreduce!(lis)
while length(lis) > 1
push!(lis, popat!(lis, last(findmin(lis))) + popat!(lis, last(findmin(lis))))
println("Interim list: $lis")
end
return lis
end
@show list, addleastreduce!(copy(list))
- Output:
Interim list: [81, 243, 14, 25, 49, 123, 69, 17] Interim list: [81, 243, 25, 49, 123, 69, 31] Interim list: [81, 243, 49, 123, 69, 56] Interim list: [81, 243, 123, 69, 105] Interim list: [243, 123, 105, 150] Interim list: [243, 150, 228] Interim list: [243, 378] Interim list: [621] (list, addleastreduce!(copy(list))) = ([6, 81, 243, 14, 25, 49, 123, 69, 11], [621])
Nim[edit]
With sorting[edit]
We sort in descending order as it is more efficient.
# With sorting.
import algorithm, strformat
proc extractAndAddTwoSmallest(list: var seq[int]) =
list.sort(Descending)
stdout.write &"Descending sorted list: {list}"
let min1 = list.pop()
let min2 = list.pop()
echo &"; two smallest: {min1} and {min2}; sum = {min1 + min2}"
list.add min1 + min2
var list = @[6, 81, 243, 14, 25, 49, 123, 69, 11]
while list.len >= 2:
list.extractAndAddTwoSmallest()
echo &"Last item is {list[0]}."
- Output:
Descending sorted list: @[243, 123, 81, 69, 49, 25, 14, 11, 6]; two smallest: 6 and 11; sum = 17 Descending sorted list: @[243, 123, 81, 69, 49, 25, 17, 14]; two smallest: 14 and 17; sum = 31 Descending sorted list: @[243, 123, 81, 69, 49, 31, 25]; two smallest: 25 and 31; sum = 56 Descending sorted list: @[243, 123, 81, 69, 56, 49]; two smallest: 49 and 56; sum = 105 Descending sorted list: @[243, 123, 105, 81, 69]; two smallest: 69 and 81; sum = 150 Descending sorted list: @[243, 150, 123, 105]; two smallest: 105 and 123; sum = 228 Descending sorted list: @[243, 228, 150]; two smallest: 150 and 228; sum = 378 Descending sorted list: @[378, 243]; two smallest: 243 and 378; sum = 621 Last item is 621.
Without sorting[edit]
We could use the function minIndex from module sequtils but it would be less efficient. We used a single loop instead. Please note that we remove the elements using function del which is O(1) rather than function delete which is O(n).
# Without sorting.
import strformat
proc extractAndAddTwoSmallest(list: var seq[int]) =
var min1, min2 = int.high
var imin1, imin2 = -1
for i, val in list:
if val < min1:
min2 = min1
min1 = val
imin2 = imin1
imin1 = i
elif val < min2:
min2 = val
imin2 = i
echo &"List: {list}; two smallest: {min1}@{imin1} and {min2}@{imin2}; sum = {min1 + min2}"
if imin1 > imin2: swap imin1, imin2 # Make sure "imin2" is the greatest index.
list.del imin2
list.del imin1
list.add min1 + min2
var list = @[6, 81, 243, 14, 25, 49, 123, 69, 11]
while list.len >= 2:
list.extractAndAddTwoSmallest()
echo &"Last item is {list[0]}."
- Output:
List: @[6, 81, 243, 14, 25, 49, 123, 69, 11]; two smallest: [email protected] and [email protected]; sum = 17 List: @[69, 81, 243, 14, 25, 49, 123, 17]; two smallest: [email protected] and [email protected]; sum = 31 List: @[69, 81, 243, 123, 25, 49, 31]; two smallest: [email protected] and [email protected]; sum = 56 List: @[69, 81, 243, 123, 49, 56]; two smallest: [email protected] and [email protected]; sum = 105 List: @[69, 81, 243, 123, 105]; two smallest: [email protected] and [email protected]; sum = 150 List: @[123, 105, 243, 150]; two smallest: [email protected] and [email protected]; sum = 228 List: @[243, 150, 228]; two smallest: [email protected] and [email protected]; sum = 378 List: @[243, 378]; two smallest: [email protected] and [email protected]; sum = 621 Last item is 621.
Perl[edit]
use strict;
use warnings;
use feature 'say';
use List::AllUtils <min firstidx>;
my @list = <6 81 243 14 25 49 123 69 11>;
say " Original @list";
push @list, get(min @list) + get(min @list) and say "@list" while @list > 1;
sub get {
my($min) = @_;
splice @list, (firstidx { $min == $_ } @list), 1;
printf " %3d ", $min;
$min;
}
- Output:
Original 6 81 243 14 25 49 123 69 11 6 11 81 243 14 25 49 123 69 17 14 17 81 243 25 49 123 69 31 25 31 81 243 49 123 69 56 49 56 81 243 123 69 105 69 81 243 123 105 150 105 123 243 150 228 150 228 243 378 243 378 621
Phix[edit]
With sorting[edit]
with javascript_semantics sequence list = {6, 81, 243, 14, 25, 49, 123, 69, 11} while length(list)>1 do list = sort(deep_copy(list)) integer l1 = list[1], l2 = list[2], l12 = l1+l2 printf(1,"Sorted list: %V, two smallest: %d + %d = %d\n",{list,l1,l2,l12}) list[1..2] = {l12} end while printf(1,"Last item is %d\n",list)
- Output:
Sorted list: {6,11,14,25,49,69,81,123,243}, two smallest: 6 + 11 = 17
Sorted list: {14,17,25,49,69,81,123,243}, two smallest: 14 + 17 = 31
Sorted list: {25,31,49,69,81,123,243}, two smallest: 25 + 31 = 56
Sorted list: {49,56,69,81,123,243}, two smallest: 49 + 56 = 105
Sorted list: {69,81,105,123,243}, two smallest: 69 + 81 = 150
Sorted list: {105,123,150,243}, two smallest: 105 + 123 = 228
Sorted list: {150,228,243}, two smallest: 150 + 228 = 378
Sorted list: {243,378}, two smallest: 243 + 378 = 621
Last item is 621
Without sorting[edit]
with javascript_semantics sequence list = {6, 81, 243, 14, 25, 49, 123, 69, 11} while length(list)>1 do printf(1,"List: %V, two smallest: ",{list}) integer l1, l2 = 0 for i=1 to 2 do l1 = l2 integer ldx = smallest(list,true) l2 = list[ldx] list = list[1..ldx-1] & list[ldx+1..$] end for printf(1,"%d + %d = %d\n",{l1,l2,l1+l2}) list &= l1+l2 end while printf(1,"Last item is %d\n",list)
- Output:
List: {6,81,243,14,25,49,123,69,11}, two smallest: 6 + 11 = 17
List: {81,243,14,25,49,123,69,17}, two smallest: 14 + 17 = 31
List: {81,243,25,49,123,69,31}, two smallest: 25 + 31 = 56
List: {81,243,49,123,69,56}, two smallest: 49 + 56 = 105
List: {81,243,123,69,105}, two smallest: 69 + 81 = 150
List: {243,123,105,150}, two smallest: 105 + 123 = 228
List: {243,150,228}, two smallest: 150 + 228 = 378
List: {243,378}, two smallest: 243 + 378 = 621
Last item is 621
Python[edit]
""" Rosetta code task: Last list item """
def add_least_reduce(lis):
""" Reduce lis: sum least two elements adding sum to list. Will take len(list) - 1 steps """
while len(lis) > 1:
lis.append(lis.pop(lis.index(min(lis))) + lis.pop(lis.index(min(lis))))
print('Interim list:', lis)
return lis
LIST = [6, 81, 243, 14, 25, 49, 123, 69, 11]
print(LIST, ' ==> ', add_least_reduce(LIST.copy()))
- Output:
Interim list: [81, 243, 14, 25, 49, 123, 69, 17] Interim list: [81, 243, 25, 49, 123, 69, 31] Interim list: [81, 243, 49, 123, 69, 56] Interim list: [81, 243, 123, 69, 105] Interim list: [243, 123, 105, 150] Interim list: [243, 150, 228] Interim list: [243, 378] Interim list: [621] [6, 81, 243, 14, 25, 49, 123, 69, 11] ==> [621]
Raku[edit]
Uses no sorting; does not modify overall list order while processing.
say ' Original ', my @list = 6, 81, 243, 14, 25, 49, 123, 69, 11;
say push @list: get(min @list) + get(min @list) while @list > 1;
sub get ($min) {
@list.splice: @list.first(* == $min, :k), 1;
printf " %3d ", $min;
$min;
}
- Output:
Original [6 81 243 14 25 49 123 69 11] 6 11 [81 243 14 25 49 123 69 17] 14 17 [81 243 25 49 123 69 31] 25 31 [81 243 49 123 69 56] 49 56 [81 243 123 69 105] 69 81 [243 123 105 150] 105 123 [243 150 228] 150 228 [243 378] 243 378 [621]
REXX[edit]
With sorting[edit]
/* REXX */
List = '6 81 243 14 25 49 123 69 11'
Do Until words(list)=1
list=wordsort(list)
Say 'Sorted list:' list
Parse Var list a b c
Say 'Two smallest:' a '+' b '=' (a+b)
list=(a+b) c
End
Say 'Last item:' list
Exit
wordsort: Procedure
/**********************************************************************
* Sort the list of words supplied as argument. Return the sorted list
**********************************************************************/
Parse Arg wl
wa.=''
wa.0=0
Do While wl<>''
Parse Var wl w wl
Do i=1 To wa.0
If wa.i>w Then Leave
End
If i<=wa.0 Then Do
Do j=wa.0 To i By -1
ii=j+1
wa.ii=wa.j
End
End
wa.i=w
wa.0=wa.0+1
End
swl=''
Do i=1 To wa.0
swl=swl wa.i
End
Return strip(swl)
- Output:
Sorted list: 6 11 14 25 49 69 81 123 243 Two smallest: 6 + 11 = 17 Sorted list: 14 17 25 49 69 81 123 243 Two smallest: 14 + 17 = 31 Sorted list: 25 31 49 69 81 123 243 Two smallest: 25 + 31 = 56 Sorted list: 49 56 69 81 123 243 Two smallest: 49 + 56 = 105 Sorted list: 69 81 105 123 243 Two smallest: 69 + 81 = 150 Sorted list: 105 123 150 243 Two smallest: 105 + 123 = 228 Sorted list: 150 228 243 Two smallest: 150 + 228 = 378 Sorted list: 243 378 Two smallest: 243 + 378 = 621 Last item: 621
Without sorting[edit]
/* REXX */
List = '6 81 243 14 25 49 123 69 11'
Do Until words(list)=1
Say 'List:' list
a=getmin()
b=getmin()
Say 'Two smallest:' a '+' b '=' (a+b)
list=list (a+b)
End
Say 'Last item:' list
Exit
getmin: Procedure Expose list
/* Return the smallest element of list and remove it from list */
min=1e9
Do i=1 To words(list)
If word(list,i)<min Then Do
m=word(list,i)
min=m
j=i
End
End
list=subword(list,1,j-1) subword(list,j+1)
Return m
- Output:
List: 6 81 243 14 25 49 123 69 11 Two smallest: 6 + 11 = 17 List: 81 243 14 25 49 123 69 17 Two smallest: 14 + 17 = 31 List: 81 243 25 49 123 69 31 Two smallest: 25 + 31 = 56 List: 81 243 49 123 69 56 Two smallest: 49 + 56 = 105 List: 81 243 123 69 105 Two smallest: 69 + 81 = 150 List: 243 123 105 150 Two smallest: 105 + 123 = 228 List: 243 150 228 Two smallest: 150 + 228 = 378 List: 243 378 Two smallest: 243 + 378 = 621 Last item: 621
Ring[edit]
With sorting[edit]
see "working..." + nl
List = [6,81,243,14,25,49,123,69,11]
n = 0
while true
n++
List = sort(List)
first = List[1]
second = List[2]
ind1 = find(List,first)
ind2 = find(List,second)
if ind1 < ind2
del(List,ind2)
del(List,ind1)
else
del(List,ind1)
del(List,ind2)
ok
sum = first + second
add(List,sum)
if len(List) = 1
exit
ok
if n = 1
see nl + "List = "
showArray(List)
see nl
ok
showList(first,second,sum,List)
end
see "Last item is: " +List[1] + nl
see "done..." + nl
func showList(first,second,sum,List)
see "two smallest is = " + first + " + " + second + " = " + sum + nl
see "List = "
showArray(List)
func showArray(array)
txt = ""
see "["
for n = 1 to len(array)
txt = txt + array[n] + ","
next
txt = left(txt,len(txt)-1)
txt = txt + "]"
see txt + nl
- Output:
working... List = [14,25,49,69,81,123,243,17] two smallest is = 6 + 11 = 17 List = [14,25,49,69,81,123,243,17] two smallest is = 14 + 17 = 31 List = [25,49,69,81,123,243,31] two smallest is = 25 + 31 = 56 List = [49,69,81,123,243,56] two smallest is = 49 + 56 = 105 List = [69,81,123,243,105] two smallest is = 69 + 81 = 150 List = [105,123,243,150] two smallest is = 105 + 123 = 228 List = [150,243,228] two smallest is = 150 + 228 = 378 List = [243,378] Last item is: 621 done...
Without sorting[edit]
see "working..." + nl
List = [6,81,243,14,25,49,123,69,11]
n = 0
while true
n++
if n = 1
see nl + "List = "
showArray(List)
see nl
ok
first = min(List)
ind1 = find(List,first)
del(List,ind1)
second = min(List)
ind2 = find(List,second)
del(List,ind2)
sum = first + second
add(List,sum)
if len(List) = 1
exit
ok
showList(first,second,sum,List)
end
see "Last item is: " +List[1] + nl
see "done..." + nl
func showList(first,second,sum,List)
see "two smallest is = " + first + " + " + second + " = " + sum + nl
see "List = "
showArray(List)
func showArray(array)
txt = ""
see "["
for n = 1 to len(array)
txt = txt + array[n] + ","
next
txt = left(txt,len(txt)-1)
txt = txt + "]"
see txt + nl
- Output:
working... List = [6,81,243,14,25,49,123,69,11] two smallest is = 6 + 11 = 17 List = [81,243,14,25,49,123,69,17] two smallest is = 14 + 17 = 31 List = [81,243,25,49,123,69,31] two smallest is = 25 + 31 = 56 List = [81,243,49,123,69,56] two smallest is = 49 + 56 = 105 List = [81,243,123,69,105] two smallest is = 69 + 81 = 150 List = [243,123,105,150] two smallest is = 105 + 123 = 228 List = [243,150,228] two smallest is = 150 + 228 = 378 List = [243,378] Last item is: 621 done...
Wren[edit]
With sorting[edit]
var a = [6, 81, 243, 14, 25, 49, 123, 69, 11]
while (a.count > 1) {
a.sort()
System.print("Sorted list: %(a)")
var sum = a[0] + a[1]
System.print("Two smallest: %(a[0]) + %(a[1]) = %(sum)")
a.add(sum)
a = a[2..-1]
}
System.print("Last item is %(a[0]).")
- Output:
Sorted list: [6, 11, 14, 25, 49, 69, 81, 123, 243] Two smallest: 6 + 11 = 17 Sorted list: [14, 17, 25, 49, 69, 81, 123, 243] Two smallest: 14 + 17 = 31 Sorted list: [25, 31, 49, 69, 81, 123, 243] Two smallest: 25 + 31 = 56 Sorted list: [49, 56, 69, 81, 123, 243] Two smallest: 49 + 56 = 105 Sorted list: [69, 81, 105, 123, 243] Two smallest: 69 + 81 = 150 Sorted list: [105, 123, 150, 243] Two smallest: 105 + 123 = 228 Sorted list: [150, 228, 243] Two smallest: 150 + 228 = 378 Sorted list: [243, 378] Two smallest: 243 + 378 = 621 Last item is 621.
Without sorting[edit]
var findMin = Fn.new { |a|
var ix = 0
var min = a[0]
for (i in 1...a.count) {
if (a[i] < min) {
ix = i
min = a[i]
}
}
return [min, ix]
}
var a = [6, 81, 243, 14, 25, 49, 123, 69, 11]
while (a.count > 1) {
System.print("List: %(a)")
var s = List.filled(2, 0)
for (i in 0..1) {
var m = findMin.call(a)
s[i] = m[0]
a.removeAt(m[1])
}
var sum = s[0] + s[1]
System.print("Two smallest: %(s[0]) + %(s[1]) = %(sum)")
a.add(sum)
}
System.print("Last item is %(a[0]).")
- Output:
List: [6, 81, 243, 14, 25, 49, 123, 69, 11] Two smallest: 6 + 11 = 17 List: [81, 243, 14, 25, 49, 123, 69, 17] Two smallest: 14 + 17 = 31 List: [81, 243, 25, 49, 123, 69, 31] Two smallest: 25 + 31 = 56 List: [81, 243, 49, 123, 69, 56] Two smallest: 49 + 56 = 105 List: [81, 243, 123, 69, 105] Two smallest: 69 + 81 = 150 List: [243, 123, 105, 150] Two smallest: 105 + 123 = 228 List: [243, 150, 228] Two smallest: 150 + 228 = 378 List: [243, 378] Two smallest: 243 + 378 = 621 Last item is 621.
XPL0[edit]
int List, End, Sum, Item, Smallest, I, SI;
[List:= [6, 81, 243, 14, 25, 49, 123, 69, 11];
End:= 8; \last index
loop [for I:= 0 to End do \show List
[IntOut(0, List(I)); ChOut(0, ^ )];
CrLf(0);
if End = 0 then quit; \done when only one element
Sum:= 0; \find two smallest items
for Item:= 1 to 2 do
[Smallest:= -1>>1;
for I:= 0 to End do
if List(I) < Smallest then
[Smallest:= List(I); SI:= I];
Sum:= Sum + Smallest; \add them
for I:= SI to End-1 do \remove them
List(I):= List(I+1);
End:= End-1;
];
End:= End+1; \insert Sum at End
List(End):= Sum;
];
]
- Output:
6 81 243 14 25 49 123 69 11 81 243 14 25 49 123 69 17 81 243 25 49 123 69 31 81 243 49 123 69 56 81 243 123 69 105 243 123 105 150 243 150 228 243 378 621
