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
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
|
use v6d;
###############################################################################
=begin comment
Perl Weekly Challenge 080
=========================
Task #2
-------
*Count Candies*
Submitted by: Mohammad S Anwar
You are given rankings of @N candidates.
Write a script to find out the total candies needed for all candidates. You are
asked to follow the rules below:
a) You must given at least one candy to each candidate.
b) Candidate with higher ranking get more candies than their immediate neigh-
bors on either side.
Example 1:
Input: @N = (1, 2, 2)
Explanation:
Applying rule #a, each candidate will get one candy. So total candies needed
so far 3. Now applying rule #b, the first candidate do not get any more candy
as its rank is lower than it's neighbours. The second candidate gets one more
candy as it's ranking is higher than it's neighbour. Finally the third candi-
date do not get any extra candy as it's ranking is not higher than neighbour.
Therefore total candies required is 4.
Output: 4
Example 2:
Input: @N = (1, 4, 3, 2)
Explanation:
Applying rule #a, each candidate will get one candy. So total candies needed
so far 4. Now applying rule #b, the first candidate do not get any more candy
as its rank is lower than it's neighbours. The second candidate gets two more
candies as it's ranking is higher than it's both neighbour. The third candi-
date gets one more candy as it's ranking is higher than it's neighbour. Final-
ly the fourth candidate do not get any extra candy as it's ranking is not
higher than neighbour. Therefore total candies required is 7.
Output: 7
=end comment
###############################################################################
#--------------------------------------#
# Copyright © 2020 PerlMonk Athanasius #
#--------------------------------------#
my Bool constant $CHECK-RULE-B = True;
my Bool constant $SHOW-DISTRIBUTION = True;
#------------------------------------------------------------------------------
BEGIN
#------------------------------------------------------------------------------
{
"\nChallenge 080, Task #2: Count Candies (Raku)\n".put;
}
##=============================================================================
sub MAIN
(
*@N #= A list of candidate rankings (numeric)
)
##=============================================================================
{
my Num @rankings;
@rankings.push: .Num for @N;
my UInt @candies = 1 xx @rankings.elems; # Apply Rule (a)
Nil while distribute-candies(@rankings, @candies); # Apply Rule (b)
if $CHECK-RULE-B
{
satisfies-b(@rankings, @candies) or
die 'ERROR: The solution breaks Rule (b)';
}
"Input: @N = (%s)\n".printf: @rankings.join: ', ';
"Candies: (%s)\n".printf: @candies\.join: ', ' if $SHOW-DISTRIBUTION;
"Total candies needed: %d\n".printf: @candies.sum;
CATCH
{
when X::TypeCheck::Assignment
{
'Non-numeric input'.put;
USAGE();
}
}
}
#------------------------------------------------------------------------------
sub distribute-candies
(
Array:D[Num:D] $N, #= Candidate rankings
Array:D[Num:D] $C, #= Candy distribution
--> Bool:D #= The candy distribution has been changed
)
#------------------------------------------------------------------------------
{
my Bool $changed = False;
for 0 .. $N.end - 1 -> UInt $i # 1. Distribute left-to-right
{
my UInt $j = $i + 1;
if $N[$i] > $N[$j] && $C[$i] <= $C[$j]
{
$C[$i] = $C[$j] + 1;
$changed = True;
}
}
for (1 .. $N.end).reverse -> UInt $i # 2. Distribute right-to-left
{
my UInt $j = $i - 1;
if $N[$i] > $N[$j] && $C[$i] <= $C[$j]
{
$C[$i] = $C[$j] + 1;
$changed = True;
}
}
return $changed;
}
#------------------------------------------------------------------------------
sub satisfies-b
(
Array:D[Num:D] $N, #= Candidate rankings
Array:D[Num:D] $C, #= Candy distribution
--> Bool:D #= The candy distribution satisfies Rule (b)
)
#------------------------------------------------------------------------------
{
for 0 .. $N.end - 1 -> UInt $i # 1. Check Rule (b) left-to-right
{
if $N[$i] > $N[$i + 1]
{
$C[$i] > $C[$i + 1] or return False;
}
}
for (1 .. $N.end).reverse -> UInt $i # 2. Check Rule (b) right-to-left
{
if $N[$i] > $N[$i - 1]
{
$C[$i] > $C[$i - 1] or return False;
}
}
return True;
}
#------------------------------------------------------------------------------
sub USAGE()
#------------------------------------------------------------------------------
{
my Str $usage = $*USAGE;
$usage ~~ s/ ($*PROGRAM-NAME) /raku $0/;
$usage.put;
}
###############################################################################
|
