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
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
|
use v6d;
################################################################################
=begin comment
Perl Weekly Challenge 071
=========================
Task #2
-------
*Trim Linked List*
*Submitted by:* Mohammad S Anwar
You are given a singly linked list and a positive integer _$N_ (>0).
Write a script to remove the _$Nth_ node from the end of the linked list and
print the linked list.
If _$N_ is greater than the size of the linked list then remove the first node
of the list.
NOTE: Please use pure linked list implementation.
*Example*
Given Linked List: 1 -> 2 -> 3 -> 4 -> 5
when $N = 1
Output: 1 -> 2 -> 3 -> 4
when $N = 2
Output: 1 -> 2 -> 3 -> 5
when $N = 3
Output: 1 -> 2 -> 4 -> 5
when $N = 4
Output: 1 -> 3 -> 4 -> 5
when $N = 5
Output: 2 -> 3 -> 4 -> 5
when $N = 6
Output: 2 -> 3 -> 4 -> 5
=end comment
################################################################################
#--------------------------------------#
# Copyright © 2020 PerlMonk Athanasius #
#--------------------------------------#
#*******************************************************************************
=begin comment
For a doubly-linked list, counting backwards from the tail of the list would be
straightforward. For a singly-linked list, it is necessary to first know the
total number of elements in the list (i.e., its size); once this is known, it is
easy to find the required node by counting forwards from the head.
One way to find the list size is to traverse the whole list from head to tail,
counting the traversals. For long lists, this could be a costly procedure. The
following SinglyLinkedList implementation therefore adds a "$!elems" attribute
which records the list size. This value is maintained by ensuring that it is
- incremented on each call to append() or insert()
- decremented on each call to remove().
Note: The implementation provided for SinglyLinkedList is only the minimum
needed for this Task. Method insert() is omitted. A robust implementation would
also provide a dedicated iterator for list traversal.
=end comment
#*******************************************************************************
#===============================================================================
class Node
#===============================================================================
{
has Str $.datum is required;
has Node $.next is rw = Nil;
}
#===============================================================================
class SinglyLinkedList
#===============================================================================
{
has UInt $.elems = 0; # List size
has Node $.head = Node.new: datum => 'HEAD'; # Sentinel
#---------------------------------------------------------------------------
method append(Str:D $element --> SinglyLinkedList:D)
#---------------------------------------------------------------------------
{
my Node $node = Node.new: datum => $element;
my Node $current = $!head;
$current = $current.next while $current.next;
$current.next = $node;
++$!elems;
return self; # Facilitate chaining
}
#---------------------------------------------------------------------------
method remove(Node:D $preceding --> SinglyLinkedList:D)
#---------------------------------------------------------------------------
{
my Node $target;
if $preceding.next
{
$target = $preceding.next;
$preceding.next = $target.next;
--$!elems;
}
else # Sanity check only
{
$!elems == 0 or die "ERROR: \$!elems = $!elems, should be 0";
}
return self; # Facilitate chaining
}
#---------------------------------------------------------------------------
method print(Str:D $title)
#---------------------------------------------------------------------------
{
"$title [$!elems]: ".print;
if $!elems > 0
{
(my Node $current = $!head.next).datum.print;
" -> { $current.datum }".print while $current = $current.next;
''.put;
}
else
{
'<empty>'.put;
}
}
}
################################################################################
subset Natural of UInt where * > 0;
#-------------------------------------------------------------------------------
BEGIN
#-------------------------------------------------------------------------------
{
"\nChallenge 071, Task #2: Trim Linked List (Raku)\n".put;
}
#===============================================================================
multi sub MAIN
(
Natural:D :$N, #= No. of the node to remove, counting from the list end
UInt:D :$S, #= List size: elements will have values '1', '2', ..., 'S'
)
#===============================================================================
{
main($N, 1 .. $S);
}
#===============================================================================
multi sub MAIN
(
Natural:D :$N,
*@elements, #= Explicit element values (strings), in order
)
#===============================================================================
{
main($N, @elements);
}
#-------------------------------------------------------------------------------
sub main(Natural:D $N, *@elements)
#-------------------------------------------------------------------------------
{
# 1. Build and display the linked list
my SinglyLinkedList $list = SinglyLinkedList.new;
$list.append: .Str for @elements;
$list.print: 'Input ';
# 2. Remove the Nth-last element and display the resulting list
my Int $diff = $list.elems - $N;
my UInt $count = $diff < 0 ?? 0 !! $diff;
my Node $prev = $list.head;
$prev = $prev.next for 1 .. $count;
$list.remove($prev)
.print: "N = $N\nOutput";
}
#-------------------------------------------------------------------------------
sub USAGE()
#-------------------------------------------------------------------------------
{
my Str $usage = $*USAGE;
$usage ~~ s:g/ ($*PROGRAM-NAME) /raku $0/;
$usage.put;
}
################################################################################
|
