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
|
use v6d;
################################################################################
=begin comment
Perl Weekly Challenge 059
=========================
Task #1
-------
*Linked List*
*Reviewed by Ryan Thompson*
You are given a linked list and a value _k_. Write a script to partition the
linked list such that all nodes less than _k_ come before nodes greater than or
equal to _k_. Make sure you preserve the original relative order of the nodes in
each of the two partitions.
For example:
Linked List: 1 → 4 → 3 → 2 → 5 → 2
_k_ = 3
Expected Output: 1 → 2 → 2 → 4 → 3 → 5.
=end comment
################################################################################
#--------------------------------------#
# Copyright © 2020 PerlMonk Athanasius #
#--------------------------------------#
# Note: To make the Perl5 module LinkedList::Single work correctly in Raku, I
# found I needed to add a stopper to signify the end of a linked list. I
# chose a value of NaN; Raku has a method Complex::isNaN which I use to
# test for end-of-list in the list-walking loops.
use LinkedList::Single:from<Perl5>;
#-------------------------------------------------------------------------------
BEGIN ''.put;
#-------------------------------------------------------------------------------
#===============================================================================
sub MAIN()
#===============================================================================
{
"Challenge 059, Task #1: Linked List (Raku)".put;
while my Str $line = data()
{
my Real ($k, @values) = $line.split( /\s+/ ).map: { .Real };
my $origl-list = LinkedList::Single.new( @values, NaN );
my $partd-list = partition( $origl-list, $k );
"\nOriginal list: %s\n".printf: sprint-list($origl-list);
"Partitioned on k = %d: %s\n".printf: $k, sprint-list($partd-list);
}
}
#-------------------------------------------------------------------------------
sub partition( $list, Real:D $k )
#-------------------------------------------------------------------------------
{
my $left = LinkedList::Single.new;
my $right = LinkedList::Single.new;
$list.head;
my $data = $list.each;
until $data.isNaN
{
($data < $k ?? $left !! $right).push: $data;
$data = $list.each;
}
$right.push: NaN;
$right.head;
$data = $right.each;
until $data.isNaN
{
$left.push: $data;
$data = $right.each;
}
$left.push: NaN;
return $left;
}
#-------------------------------------------------------------------------------
sub sprint-list( $list --> Str:D )
#-------------------------------------------------------------------------------
{
my Real @array;
$list.head;
my $data = $list.each;
until $data.isNaN
{
@array.push: $data;
$data = $list.each;
}
return '%s'.sprintf: @array.join: ' -> ';
}
#-------------------------------------------------------------------------------
sub data( --> Str:D )
#-------------------------------------------------------------------------------
{
state UInt $index = 0;
state Str @data =
[
'3 1 4 3 2 5 2',
'4 1 4 3 2 5 2',
'5 1 4 3 2 5 2',
'3 1 2 3 2 1',
'4 5 4 3 2 1',
'3 3 6 2 2 1 -1 17 5',
'0 5 4 3 2 1 0 -1 -2 -3 -4 -5',
'1 5 4 3 2 1 0 -1 -2 -3 -4 -5',
];
return $index < @data.elems ?? @data[ $index++ ] !! Nil;
}
###############################################################################
|
