Last list item

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.

ALGOL 68

Translation of: Wren

<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;
       print( ( newline ) );
       INT sum = a[ 1 ] + a[ 2 ];
       print( ( "Two smallest: " , whole( a[ 1 ], 0 )
              , " + ", whole( a[ 2 ], 0 )
              , " = ", whole( sum, 0 )
              , newline
              )
            );
       a[ 2 ] := sum;
       a[ 1 : a count - 1 ] := a[ 2 : a count ];
       a count -:= 1  
   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.

C

Translation of: Wren

<lang c>#include <stdio.h>

1. 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.

Go

Translation of: Wren

<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, a[0]+a[1])
       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.

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]

Ring

<lang ring> see "working..." + nl

List = [6,81,243,14,25,49,123,69,11] Temp = [] n = 0 while true

     n++
     Temp = sort(List)
     first = Temp[1]
     second = Temp[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 = [81,243,14,25,49,123,69,17]

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

<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.