Peter
Peter Campbell Smith

Add up the singletons
and clear out the list

Weekly challenge 228 — 31 July 2023

Week 228 - 31 Jul 2023

Task 2

Task — Empty array

You are given an array of integers in which all elements are unique. Write a script to perform the following operations until the array is empty and return the total count of operations.

If the first element is the smallest then remove it otherwise move it to the end.

Examples


Example 1
Input: @int = (3, 4, 2)
Output: 5

Operation 1: move 3 to the end: (4, 2, 3)
Operation 2: move 4 to the end: (2, 3, 4)
Operation 3: remove element 2: (3, 4)
Operation 4: remove element 3: (4)
Operation 5: remove element 4: ()

Example 2
Input: @int = (1, 2, 3)
Output: 3

Operation 1: remove element 1: (2, 3)
Operation 2: remove element 2: (3)
Operation 3: remove element 3: ()

Analysis

This challenge translates fairly literally into Perl:

If the first element is the smallest then remove it:

if ($array[0] == $smallest) { shift @array }

otherwise move it to the end:

else { push(@array, shift @array) }

... and that's it really, aside from keeping track of what you've done.

Try it 

Example: 1, 5, 2, 4, 3

Script


#!/usr/bin/perl

use v5.16;    # The Weekly Challenge - 2023-07-31
use utf8;     # Week 228 task 2 - Empty array
use strict;   # Peter Campbell Smith
use warnings; # Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

my ($j, @int);

empty_array(3, 4, 2);
empty_array(1, 2, 3);
empty_array(1);
empty_array();
empty_array(8, 3, 4, 7, 6, 2, 9, 1);

sub empty_array {
    
    my (@array, $smallest, $operations, $explain);
    
    @array = @_;
    $operations = 0;
    $explain = '';
    while (1) {
        
        # if it's empty we're done
        unless (@array) {
            say qq[\nInput:  \@int = (] . join (', ', @_) . ')';
            say qq[Output: $operations$explain];
            return;
        }
        
        # if the first element is the smallest then remove it
        $operations ++;     
        $smallest = $array[0];
        $smallest = $_ < $smallest ? $_ : $smallest for @array;
        
        if ($array[0] == $smallest) {
            shift @array;   
            $explain .= qq[\n   Operation $operations: remove element $smallest:          (] . join(', ', @array) . ')';

        # otherwise move it to the end
        } else {
            push(@array, shift @array);
            $explain .= qq[\n   Operation $operations: move element $array[-1] to the end: (] . join(', ', @array) . ')';
        }
    }
}

Output


Input:  @int = (3, 4, 2)
Output: 5
   Operation 1: move element 3 to the end: (4, 2, 3)
   Operation 2: move element 4 to the end: (2, 3, 4)
   Operation 3: remove element 2:          (3, 4)
   Operation 4: remove element 3:          (4)
   Operation 5: remove element 4:          ()

Input:  @int = (1, 2, 3)
Output: 3
   Operation 1: remove element 1:          (2, 3)
   Operation 2: remove element 2:          (3)
   Operation 3: remove element 3:          ()

Input:  @int = (1)
Output: 1
   Operation 1: remove element 1:          ()

Input:  @int = ()
Output: 0

Input:  @int = (8, 3, 4, 7, 6, 2, 9, 1)
Output: 26
   Operation 1: move element 8 to the end: (3, 4, 7, 6, 2, 9, 1, 8)
   Operation 2: move element 3 to the end: (4, 7, 6, 2, 9, 1, 8, 3)
   Operation 3: move element 4 to the end: (7, 6, 2, 9, 1, 8, 3, 4)
   Operation 4: move element 7 to the end: (6, 2, 9, 1, 8, 3, 4, 7)
   Operation 5: move element 6 to the end: (2, 9, 1, 8, 3, 4, 7, 6)
   Operation 6: move element 2 to the end: (9, 1, 8, 3, 4, 7, 6, 2)
   Operation 7: move element 9 to the end: (1, 8, 3, 4, 7, 6, 2, 9)
   Operation 8: remove element 1:          (8, 3, 4, 7, 6, 2, 9)
   Operation 9: move element 8 to the end: (3, 4, 7, 6, 2, 9, 8)
   Operation 10: move element 3 to the end: (4, 7, 6, 2, 9, 8, 3)
   Operation 11: move element 4 to the end: (7, 6, 2, 9, 8, 3, 4)
   Operation 12: move element 7 to the end: (6, 2, 9, 8, 3, 4, 7)
   Operation 13: move element 6 to the end: (2, 9, 8, 3, 4, 7, 6)
   Operation 14: remove element 2:          (9, 8, 3, 4, 7, 6)
   Operation 15: move element 9 to the end: (8, 3, 4, 7, 6, 9)
   Operation 16: move element 8 to the end: (3, 4, 7, 6, 9, 8)
   Operation 17: remove element 3:          (4, 7, 6, 9, 8)
   Operation 18: remove element 4:          (7, 6, 9, 8)
   Operation 19: move element 7 to the end: (6, 9, 8, 7)
   Operation 20: remove element 6:          (9, 8, 7)
   Operation 21: move element 9 to the end: (8, 7, 9)
   Operation 22: move element 8 to the end: (7, 9, 8)
   Operation 23: remove element 7:          (9, 8)
   Operation 24: move element 9 to the end: (8, 9)
   Operation 25: remove element 8:          (9)
   Operation 26: remove element 9:          ()

The content of this website which has been created by
Peter Campbell Smith is hereby placed in the public domain