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
|
#!/usr/bin/env python3
# Challenge 058
#
# 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.
#
# Here is a diagram of the input arrays @H and @T:
#
#
#
# Finally, here is one possible solution that satisfies @H and @T:
#
#
#
# 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);
# You’re free to come up with your own inputs. Here is a 1000-person list,
# if you like!
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]
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]
# zip height and taller
HT = [[H[x], T[x]] for x in range(len(H))]
# reverse sort by height
HT.sort(key=lambda x:x[0])
HT = HT[::-1]
# iterate through the indices
for i in range(len(HT)):
# check if we need more people in front than are taller
if HT[i][1] > i:
print("no solution")
exit(1)
# find position to move person
j = HT[i][1]
if i != j:
# remove from $i and insert in $j
person = HT[i]
HT = HT[:i] + HT[i+1:]
HT = HT[:j] + [person] + HT[j:]
print(", ".join([str(x[0]) for x in HT]))
|
