Last list item: Difference between revisions
→{{header|ALGOL 68}}: Re-added sorted version, with the correct positioning of the new element (was wrong due to an error in translation) |
m Algol 68 →With sorting |
||
Line 12: | Line 12: | ||
===With sorting=== |
===With sorting=== |
||
{{trans|Wren}} |
{{trans|Wren}} |
||
⚫ | |||
<lang algol68> |
|||
⚫ | |||
# of the two smallest elements and removing them # |
# of the two smallest elements and removing them # |
||
# Quicksorts in-place the array of integers a, from lb to ub # |
# Quicksorts in-place the array of integers a, from lb to ub # |
||
Line 55: | Line 54: | ||
OD; |
OD; |
||
print( ( "Last item is ", whole( a[ 1 ], 0 ), ".", newline ) ) |
print( ( "Last item is ", whole( a[ 1 ], 0 ), ".", newline ) ) |
||
END |
END</lang> |
||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
Revision as of 12:57, 24 October 2021
- 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"
ALGOL 68
With sorting
<lang algol68>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</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
Was a translation of the sorted Wren version but the sorting has been removed as per the revised task requirements. <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.
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.
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.
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])
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
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...
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.