The weekly challenge 297 - Task 2: Semi-Ordered Permutation

 1 #!/usr/bin/env perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-297/#TASK2
 3 #
 4 # Task 2: Semi-Ordered Permutation
 5 # ================================
 6 #
 7 # You are given permutation of $n integers, @ints.
 8 #
 9 # Write a script to find the minimum number of swaps needed to make the @ints a
10 # semi-ordered permutation.
11 #
12 # A permutation is a sequence of integers from 1 to n of length n containing
13 # each number exactly once.
14 # A permutation is called semi-ordered if the first number is 1 and the last
15 # number equals n.
16 #
17 # You are ONLY allowed to pick adjacent elements and swap them.
18 #
19 ## Example 1
20 ##
21 ## Input: @ints = (2, 1, 4, 3)
22 ## Output: 2
23 ##
24 ## Swap 2 <=> 1 => (1, 2, 4, 3)
25 ## Swap 4 <=> 3 => (1, 2, 3, 4)
26 #
27 ## Example 2
28 ##
29 ## Input: @ints = (2, 4, 1, 3)
30 ## Output: 3
31 ##
32 ## Swap 4 <=> 1 => (2, 1, 4, 3)
33 ## Swap 2 <=> 1 => (1, 2, 4, 3)
34 ## Swap 4 <=> 3 => (1, 2, 3, 4)
35 #
36 ## Example 3
37 ##
38 ## Input: @ints = (1, 3, 2, 4, 5)
39 ## Output: 0
40 ##
41 ## Already a semi-ordered permutation.
42 #
43 ############################################################
44 ##
45 ## discussion
46 ##
47 ############################################################
48 #
49 # The number of swaps to get the "1" to the beginning of the array
50 # is equal to the index of the "1" inside the array. The number of
51 # swaps to get n to the end of the array is the index of the last
52 # element in the array minus the index of n in the array. The
53 # result is therefore the sum of those two numbers (minus 1 if
54 # in the beginning, the 1 is later in the array than n because one
55 # swap will swap the 1 and the n and would otherwise be counted
56 # twice).
57 
58 use strict;
59 use warnings;
60 
61 semi_ordered_permutation(2, 1, 4, 3);
62 semi_ordered_permutation(2, 4, 1, 3);
63 semi_ordered_permutation(1, 3, 2, 4, 5);
64 
65 sub semi_ordered_permutation {
66    my @ints = @_;
67    print "Input: (" . join(", ", @ints) . ")\n";
68    my $index_of_1 = 0;
69    my $index_of_n = 0;
70    foreach my $i (0..$#ints) {
71       if($ints[$i] == 1) {
72          $index_of_1 = $i;
73       }
74       if($ints[$i] == scalar(@ints)) {
75          $index_of_n = $i;
76       }
77    }
78    my $result = 0;
79    if($index_of_1 < $index_of_n) {
80       $result = $index_of_1 + ($#ints - $index_of_n);
81    } else {
82       $result = $index_of_1 + ($#ints - $index_of_n - 1);
83    }
84    print "Output: $result\n";
85 }