1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
|
#! /opt/local/bin/perl
#
# law_and_order_lineup.pl
#
# PWC 58 TASK #2 › Ordered Lineup
# Reviewed by Ryan Thompson
# Write a script to arrange people in a lineup according to how many
# taller people are in front of each person in line. You are given two
# arrays. @H is a list of unique heights, in any order. @T is a list of
# how many taller people are to be put in front of the corresponding
# person in @H. The output is the final ordering of people’s heights, or
# an error if there is no solution.
#
# Here is a small example:
#
# @H = (2, 6, 4, 5, 1, 3) # Heights
# @T = (1, 0, 2, 0, 1, 2) # Number of taller people in front
#
# The ordering of both arrays lines up, so H[i] and T[i] refer to the same
# person. For example, there are 2 taller people in front of the person
# with height 4, and there is 1 person in front of the person with height
# 1.
#
# As per the last diagram, your script would then output the ordering (5,
# 1, 2, 6, 3, 4) in this case. (The leftmost element is the “front” of the
# array.)
#
# Here’s a 64-person example, with answer provided:
#
# # Heights
# @H = (27, 21, 37, 4, 19, 52, 23, 64, 1, 7, 51, 17, 24, 50, 3, 2,
# 34, 40, 47, 20, 8, 56, 14, 16, 42, 38, 62, 53, 31, 41, 55, 59,
# 48, 12, 32, 61, 9, 60, 46, 26, 58, 25, 15, 36, 11, 44, 63, 28,
# 5, 54, 10, 49, 57, 30, 29, 22, 35, 39, 45, 43, 18, 6, 13, 33);
#
# # Number taller people in front
# @T = ( 6, 41, 1, 49, 38, 12, 1, 0, 58, 47, 4, 17, 26, 1, 61, 12,
# 29, 3, 4, 11, 45, 1, 32, 5, 9, 19, 1, 4, 28, 12, 2, 2,
# 13, 18, 19, 3, 4, 1, 10, 16, 4, 3, 29, 5, 49, 1, 1, 24,
# 2, 1, 38, 7, 7, 14, 35, 25, 0, 5, 4, 19, 10, 13, 4, 12);
#
# # Expected answer
# @A = (35, 23, 5, 64, 37, 9, 13, 25, 16, 44, 50, 40, 2, 27, 36, 6,
# 18, 54, 20, 39, 56, 45, 12, 47, 17, 33, 55, 30, 26, 51, 42, 53,
# 49, 41, 32, 15, 22, 60, 14, 46, 24, 59, 10, 28, 62, 38, 58, 63,
# 8, 48, 4, 7, 31, 19, 61, 43, 57, 11, 1, 34, 21, 52, 29, 3);
#
#
# method: I have to admit this one threw me for a loop for a while.
# After taking the requisite time just to understand the challenge
# posed, I at first became convinced the solution lay in some
# reconfigured sort algorithm. Something involving selectively
# swapping pairs of people in line and making successive passes over
# the list until no more rearrangement was required. That sounded...
# messy.
#
# One thing was clear from the outset, that the first thing to do
# would be to sort the people by height from tallest to shortest.
# Since heights are defined to be unique, we can refer to
# individuals by their height. To preserve synchronization with the
# parallel array of people in front, it would be necessary to either
# make matching moves of those indices too, or record the
# association in a hash for future reference.
#
# Once I had the people sorted by height, it became clear that if
# the input required more people to be in front of a given person
# than there were individuals taller than that person, the dataset
# would not be solvable; that number, the people in front, directly
# relates to the index of the person in the sorted line. In fact
# they were the same.
#
# Now we were getting somewhere. If the number of people required to
# be in front was always less than or equal to the number of people
# taller than that person, which in turn was that person's index in
# the sorted line, then any movement of that person in the line to
# the sorted position must be toward the front of the line in all
# cases.
#
# Furthermore, if people are only being moved in one direction,
# towards the front, then the number of people taller than a person
# in the line will never change, and the index of a given person
# remains constant, as long as all rearragement of the line involves
# people taller than themselves.
#
# Therefore if we rearrange the people in line starting
# with the tallest, proceding in descending order, upon arrival of a given
# person's time to move, all people in front of that person will still be
# taller, and that person will only need to move forward a number of
# positions to leave the required number of taller people in front
# of them. The starting number of people taller is the index of that
# person, and any given person has a lookup of the required number
# of taller people, so that person needs to move
#
# index - taller_than_lookup
#
# spaces forward to the correct spot. But as the index of a person
# does not alter by the rearrangements of any people before their given
# turn, the final placement index of a person is determined by
#
# index - (index - taller_than_lookup)
#
# which is simply the value of the taller_than_lookup.
#
# What started seeming quite complex has turned out to be remarkably
# simple: After preserving the association between heights and the
# required number of taller people in front in a lookup, we sort the
# line from tallest to shortest. Then we proceed down this line
# starting with the tallest, moving each person in turn to the new
# index determined by the lookup. That's it. When we have moved
# every person we are done.
#
#
#
#
# 2020 colin crain
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
use warnings;
use strict;
use feature ":5.26";
## ## ## ## ## MAIN:
## @heights elems are unique
my @heights = (
27, 21, 37, 4, 19, 52, 23, 64, 1, 7, 51, 17, 24, 50, 3, 2,
34, 40, 47, 20, 8, 56, 14, 16, 42, 38, 62, 53, 31, 41, 55, 59,
48, 12, 32, 61, 9, 60, 46, 26, 58, 25, 15, 36, 11, 44, 63, 28,
5, 54, 10, 49, 57, 30, 29, 22, 35, 39, 45, 43, 18, 6, 13, 33
);
# Number taller people in front
my @taller_than = (
6, 41, 1, 49, 38, 12, 1, 0, 58, 47, 4, 17, 26, 1, 61, 12,
29, 3, 4, 11, 45, 1, 32, 5, 9, 19, 1, 4, 28, 12, 2, 2,
13, 18, 19, 3, 4, 1, 10, 16, 4, 3, 29, 5, 49, 1, 1, 24,
2, 1, 38, 7, 7, 14, 35, 25, 0, 5, 4, 19, 10, 13, 4, 12
);
my %in_front;
## load the parallel hashes with a hash slice
@in_front{@heights} = @taller_than;
my @ordered_lineup = sort {$b <=> $a} @heights;
## iterate through the indices
for my $idx (0..scalar(@heights) - 1) {
## if the sort requires more people in front than are in fact taller, the group cannot be sorted
unless ($in_front{$ordered_lineup[$idx]} <= $idx) { die "there is no solution to this problem!"}
## find the position to reinsert the person
my $insert_index = $in_front{$ordered_lineup[$idx]};
next if $idx == $insert_index; ## nop and jump
## remove the person from this index and reinsert at the new index
splice(@ordered_lineup, $insert_index, 0, ( splice(@ordered_lineup, $idx, 1) ) );
}
say join ', ', @ordered_lineup;
|
