Last list item
- 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"
11l
<lang 11l>F add_least_reduce(&lis)
L lis.len > 1 V el1 = lis.pop(lis.index(min(lis))) V el2 = lis.pop(lis.index(min(lis))) lis.append(el1 + el2) print(‘Interim list: ’lis) R lis
V LIST = [6, 81, 243, 14, 25, 49, 123, 69, 11]
print(LIST‘ ==> ’add_least_reduce(©(LIST)))</lang>
- 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]
Ada
With sorting
<lang Ada>with Ada.Text_IO; with Ada.Containers.Vectors;
procedure Last_List_Item_Sorted is
package Integer_IO is new Ada.Text_IO.Integer_IO (Integer);
package Vectors is new Ada.Containers.Vectors (Index_Type => Positive, Element_Type => Integer); package Vector_Sorting is new Vectors.Generic_Sorting; use Ada.Containers, Vectors, Ada.Text_IO, Integer_IO;
procedure Put (List : Vector) is begin Put ("["); for V of List loop Put (" "); Put (V, Width => 0); end loop; Put ("]"); end Put;
List : Vector := 6 & 81 & 243 & 14 & 25 & 49 & 123 & 69 & 11;
begin
Default_Width := 0; while List.Length >= 2 loop Vector_Sorting.Sort (List); Put (List); declare Small_1 : constant Integer := List (List.First_Index + 0); Small_2 : constant Integer := List (List.First_Index + 1); Sum : constant Integer := Small_1 + Small_2; begin List.Delete_First (2); Put (". Smallest: "); Put (Small_1); Put (" and "); Put (Small_2); Put (". Sum: "); Put (Sum); New_Line; List.Append (Sum); end; end loop; Put (List); New_Line;
end Last_List_Item_Sorted;</lang>
- Output:
[ 6 11 14 25 49 69 81 123 243]. Smallest: 6 and 11. Sum: 17 [ 14 17 25 49 69 81 123 243]. Smallest: 14 and 17. Sum: 31 [ 25 31 49 69 81 123 243]. Smallest: 25 and 31. Sum: 56 [ 49 56 69 81 123 243]. Smallest: 49 and 56. Sum: 105 [ 69 81 105 123 243]. Smallest: 69 and 81. Sum: 150 [ 105 123 150 243]. Smallest: 105 and 123. Sum: 228 [ 150 228 243]. Smallest: 150 and 228. Sum: 378 [ 243 378]. Smallest: 243 and 378. Sum: 621 [ 621]
Without sorting
<lang Ada>with Ada.Text_IO; with Ada.Containers.Vectors;
procedure Last_List_Item is
package Integer_IO is new Ada.Text_IO.Integer_IO (Integer);
package Element_Vectors is new Ada.Containers.Vectors (Index_Type => Positive, Element_Type => Integer); use Ada.Containers, Element_Vectors, Ada.Text_IO, Integer_IO;
function Pick_Smallest (List : in out Vector) return Integer is Value : Integer := Integer'Last; begin if List.Is_Empty then raise Constraint_Error; end if;
for V of List loop Value := Integer'Min (Value, V); end loop; List.Delete (List.Find_Index (Value)); return Value; end Pick_Smallest;
procedure Put (List : Vector) is begin Put ("["); for V of List loop Put (" "); Put (V, Width => 0); end loop; Put ("]"); end Put;
List : Vector := 6 & 81 & 243 & 14 & 25 & 49 & 123 & 69 & 11;
begin
Default_Width := 0; while List.Length >= 2 loop Put (List); Put (". Smallest: "); declare Small_1 : constant Integer := Pick_Smallest (List); Small_2 : constant Integer := Pick_Smallest (List); Sum : constant Integer := Small_1 + Small_2; begin Put (Small_1); Put (" and "); Put (Small_2); Put (". Sum: "); Put (Sum); New_Line;
List.Append (Sum); end; end loop; Put (List); New_Line;
end Last_List_Item;</lang>
- Output:
[ 6 81 243 14 25 49 123 69 11]. Smallest: 6 and 11. Sum: 17 [ 81 243 14 25 49 123 69 17]. Smallest: 14 and 17. Sum: 31 [ 81 243 25 49 123 69 31]. Smallest: 25 and 31. Sum: 56 [ 81 243 49 123 69 56]. Smallest: 49 and 56. Sum: 105 [ 81 243 123 69 105]. Smallest: 69 and 81. Sum: 150 [ 243 123 105 150]. Smallest: 105 and 123. Sum: 228 [ 243 150 228]. Smallest: 150 and 228. Sum: 378 [ 243 378]. Smallest: 243 and 378. Sum: 621 [ 621]
ALGOL 68
With sorting
<lang algol68>BEGIN # find the last element after repeatedely adding the sum #
# of the two smallest elements and removing them # PR read "rows.incl.a68" PR # row related utilities #
[ 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 FROMELEMENT LWB a TOELEMENT 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</lang>
- 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
Translation of the sorted Wren version with the sorting removed. <lang algol68>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</lang>
- 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.
AppleScript
<lang applescript>on lastListItem(lst)
set astid to AppleScript's text item delimiters set AppleScript's text item delimiters to ", " set output to {"Steps:", "{" & lst & "} ← Original"} set len to (count lst) if (len > 1) then repeat with len from len to 3 by -1 set {i, j} to {1, 2} set {s1, s2} to lst if (s2 < s1) then set {i, s1, j, s2} to {j, s2, i, s1} repeat with k from 3 to len set v to lst's item k if (v < s1) then set {i, s1, j, s2} to {k, v, i, s1} else if (v < s2) then set {j, s2} to {k, v} end if end repeat tell lst to set {item i, item j} to {missing value, missing value} set lst to lst's numbers set lst's end to s1 + s2 set output's end to "{" & lst & "} ← " & s1 & " + " & s2 & " = " & result end repeat tell lst to set end of output to "{" & (beginning + end) & "} ← " & beginning & " + " & end & " = " & (beginning + end) end if set AppleScript's text item delimiters to linefeed set output to output as text set AppleScript's text item delimiters to astid return output
end lastListItem
lastListItem({6, 81, 243, 14, 25, 49, 123, 69, 11})</lang>
- Output:
<lang applescript>"Steps: {6, 81, 243, 14, 25, 49, 123, 69, 11} ← Original {81, 243, 14, 25, 49, 123, 69, 17} ← 6 + 11 = 17 {81, 243, 25, 49, 123, 69, 31} ← 14 + 17 = 31 {81, 243, 49, 123, 69, 56} ← 25 + 31 = 56 {81, 243, 123, 69, 105} ← 49 + 56 = 105 {243, 123, 105, 150} ← 69 + 81 = 150 {243, 150, 228} ← 105 + 123 = 228 {243, 378} ← 150 + 228 = 378 {621} ← 243 + 378 = 621"</lang>
AutoHotkey
<lang AutoHotkey>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, ", ") "]"
}</lang>
- 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
<lang AWK>
- 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)
} </lang>
- 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
BQN
With and without sorting
<lang bqn>list ← ⟨6, 81, 243, 14, 25, 49, 123, 69, 11⟩
W_sort ← {{i←2↑∧𝕩, (𝕩/˜¬𝕩∊i)∾+´i}⍟(↕≠𝕩)𝕩}
WO_sort ← {{m←⌊´𝕩, n←⌊´𝕩/˜¬m=𝕩, (𝕩/˜¬𝕩∊m‿n)∾m+n}⍟(↕≠𝕩)𝕩}
•Show¨W_sort list •Show¨WO_sort list</lang> <lang>⟨ 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 ⟩ ⟨ 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 ⟩</lang>
C
With sorting
<lang c>#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;
}</lang>
- 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
<lang c>#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;
}</lang>
- 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
<lang factor>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</lang>
- 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
<lang freebasic>#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 print 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 print
wend</lang>
- 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
With sorting
<lang go>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.")
}</lang>
- 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
<lang go>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.")
}</lang>
- 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.
J
Here we maintain the unsorted order in the intermediate steps:<lang J> rplc&(' 0';)"1": ((-. , +/@]) 2 {. /:~)^:a: 81 243 14 25 49 123 69 17
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</lang>
jq
Adapted from Wren
Works with gojq, the Go implementation of jq
With sorting
<lang jq>def task_with_sorting:
foreach range(1; length) as $i ( {a: .}; .a |= sort | .emit = "Sorted list: \(.a)\n" | (.a[0] + .a[1]) as $sum | .emit += "Two smallest: \(.a[0]) + \(.a[1]) = \($sum)" | .a += [$sum] | .a |= .[2:] ; .emit, (select(.a|length==1) | "Last item is \(.a[0]).") );
[6, 81, 243, 14, 25, 49, 123, 69, 11] | task_with_sorting</lang>
- 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
<lang jq>def min_index:
. as $in | reduce range(0; length) as $i ( null; $in[$i] as $x | if . == null then {ix: 0, min: $x} elif $x < .min then {ix: $i, min: $x} else . end) | .ix;
def task_without_sorting:
# Output: [min, remainder] def remove_min: min_index as $ix | [.[$ix], (.[:$ix] + .[$ix + 1:])];
foreach range(1; length) as $i ( {a: .}; .emit = "Unsorted list: \(.a)\n" | (.a | remove_min) as [$m1, $x] | ($x | remove_min) as [$m2, $y] | ($m1 + $m2) as $sum | .emit += "Two smallest: \($m1) + \($m2) = \($sum)" | .a = $y + [$sum] ; .emit, (select(.a|length==1) | "Last item is \(.a[0]).") );
[6, 81, 243, 14, 25, 49, 123, 69, 11] | task_without_sorting </lang>
- Output:
Unsorted list: [6,81,243,14,25,49,123,69,11] Two smallest: 6 + 11 = 17 Unsorted list: [81,243,14,25,49,123,69,17] Two smallest: 14 + 17 = 31 Unsorted list: [81,243,25,49,123,69,31] Two smallest: 25 + 31 = 56 Unsorted list: [81,243,49,123,69,56] Two smallest: 49 + 56 = 105 Unsorted list: [81,243,123,69,105] Two smallest: 69 + 81 = 150 Unsorted list: [243,123,105,150] Two smallest: 105 + 123 = 228 Unsorted list: [243,150,228] Two smallest: 150 + 228 = 378 Unsorted list: [243,378] Two smallest: 243 + 378 = 621 Last item is 621.
Julia
<lang julia>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))
</lang>
- 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])
Mathematica/Wolfram Language
With and without sorting
<lang Mathematica>list = {6, 81, 243, 14, 25, 49, 123, 69, 11};
Print[list] Do[
poss = Ordering[list, 2]; extr = Extract[list, List /@ poss]; extr //= Total; list = Delete[list, List /@ poss]; AppendTo[list, extr]; Print[list] , {Length[list] - 1} ]</lang>
- 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}
Nim
With sorting
We sort in descending order as it is more efficient. <lang Nim># 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]}."</lang>
- 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
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).
<lang Nim># 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]}."</lang>
- Output:
List: @[6, 81, 243, 14, 25, 49, 123, 69, 11]; two smallest: 6@0 and 11@8; sum = 17 List: @[69, 81, 243, 14, 25, 49, 123, 17]; two smallest: 14@3 and 17@7; sum = 31 List: @[69, 81, 243, 123, 25, 49, 31]; two smallest: 25@4 and 31@6; sum = 56 List: @[69, 81, 243, 123, 49, 56]; two smallest: 49@4 and 56@5; sum = 105 List: @[69, 81, 243, 123, 105]; two smallest: 69@0 and 81@1; sum = 150 List: @[123, 105, 243, 150]; two smallest: 105@1 and 123@0; sum = 228 List: @[243, 150, 228]; two smallest: 150@1 and 228@2; sum = 378 List: @[243, 378]; two smallest: 243@0 and 378@1; sum = 621 Last item is 621.
Perl
<lang perl>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;
}</lang>
- 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
With sorting
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
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
<lang python>""" 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()))
</lang>
- 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
Uses no sorting; does not modify overall list order while processing. <lang perl6>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;
}</lang>
- 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
With sorting
<lang rexx>/* 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)</lang>
- 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
<lang rexx>/* 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</lang>
- 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
With sorting
<lang ring> 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
</lang>
- 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
<lang ring> 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
</lang>
- 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...
Sidef
With sorting
<lang ruby>var k = 2 var list = [6, 81, 243, 14, 25, 49, 123, 69, 11]
while (list.len >= k) {
var a = list.sort!.shift(k) list << a.sum say "#{a.map{'%3s' % _}.join(' ')} : #{list}"
}</lang>
- Output:
6 11 : [14, 25, 49, 69, 81, 123, 243, 17] 14 17 : [25, 49, 69, 81, 123, 243, 31] 25 31 : [49, 69, 81, 123, 243, 56] 49 56 : [69, 81, 123, 243, 105] 69 81 : [105, 123, 243, 150] 105 123 : [150, 243, 228] 150 228 : [243, 378] 243 378 : [621]
Without sorting
<lang ruby>var k = 2 var list = [6, 81, 243, 14, 25, 49, 123, 69, 11]
while (list.len >= k) {
var a = gather { k.times { take(var v = list.min) list.delete_first(v) } }
list << a.sum say "#{a.map{'%3s' % _}.join(' ')} : #{list}"
}</lang>
- Output:
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]
Vlang
With sorting
<lang vlang>fn main() {
mut a := [6, 81, 243, 14, 25, 49, 123, 69, 11] for a.len > 1 { a.sort() println("Sorted list: $a") sum := a[0] + a[1] println("Two smallest: ${a[0]} + ${a[1]} = $sum") a << sum a = a[2..] } println("Last item is ${a[0]}.")
}</lang>
- 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
<lang vlang>fn find_min(a []int) (int, int) {
mut ix := 0 mut min := a[0] for i in 1..a.len { if a[i] < min { ix = i min = a[i] } } return min, ix
} fn main() {
mut a := [6, 81, 243, 14, 25, 49, 123, 69, 11] for a.len > 1 { println("List: $a") mut s := [2]int{} for i in 0..2 { min, ix := find_min(a) s[i] = min a.delete(ix) } sum := s[0] + s[1] println("Two smallest: ${s[0]} + ${s[1]} = $sum") a << sum } println("Last item is ${a[0]}.")
}</lang>
- 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: [24,3 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.
Wren
With sorting
<lang ecmascript>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]).")</lang>
- 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
<lang ecmascript>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]).")</lang>
- 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
<lang XPL0>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; ];
]</lang>
- 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