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
|
#!/usr/bin/perl
#
# Task 1: "Linked List
#
# 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.
# "
#
# My notes: why a linked list not an array, it would be so simple with an
# array. Ok, ok, a linked list: but the question is: do we want to reuse
# the existing nodes or build fresh. Building fresh would make it a "pure"
# functional-style implementation. But let's try reusing the existing
# nodes..
# Build two lists (reusing the existing nodes), one "before", the other "after".
# Unlink each node, append it to whichever list is appropriate. Repeat.
#
use strict;
use warnings;
use feature 'say';
use Function::Parameters;
use Data::Dumper;
die "Usage: list-partition k elements\n" if @ARGV==0;
my( $k, @el ) = @ARGV;
# usually I would write the list as an inline bless() class.
# this time, just for the sake of variety, let's not bother with the gloss.
# how to represent the list? [] for nil, [h,t] for cons(h,t)
fun nil() { return [] }
fun cons($h,$t) { return [$h,$t] }
fun single($h) { return [$h,[]] }
fun isnil($l) { return @$l==0?1:0 }
#
# my $list = a2l( @el );
# Convert a plain Perl array @el into a nil/cons list.
# Return the generated list.
#
fun a2l( @el )
{
return nil() unless @el;
my $first = shift @el;
my $l = single($first); # create one-element list
my $last = $l; # "pointer to last node"
foreach my $x (@el)
{
# append $x to list $l via $last
$last = $last->[1] = single($x);
}
return $l;
}
#
# my $str = l2s($l);
# Generate printable (string) format of list $l.
#
fun l2s( $l )
{
return "nil" unless @$l;
( my $h, $l ) = @$l;
my $s = "$h";
# foreach element h in $l
while( @$l )
{
( my $h, $l ) = @$l;
$s .= " -> $h";
}
return $s;
}
#
# partition( $l, $k );
# Partition list $l (modifying it in place)
# such that all elements from $l that are < $k
# come first (in the same order as they were found
# in $l) followed by all elements from $l are >= $k
# (also in the same order as found in $l).
#
fun partition( $l, $k )
{
return if isnil($l);
# before and after lists, and their last node pointer
my $before = nil();
my $lastb = $before;
my $after = nil();
my $lasta = $after;
# keep the original array ref to change @$origl later
my $origl = $l;
# loop over $l, detaching each node, and appending it
# to either $before or $after
my $nil = nil();
while( @$l ) # ! isnil
{
my $p = $l;
( my $h, $l ) = @$l;
$p->[1] = $nil;
if( $h < $k )
{
# add to before
if( @$lastb == 0 )
{
$lastb = $before = $p;
} else
{
$lastb = $lastb->[1] = $p;
}
} else
{
# add to after
if( @$lasta == 0 )
{
$lasta = $after = $p;
} else
{
$lasta = $lasta->[1] = $p;
}
}
}
# now $l is logically empty, reconstruct it
# from before++after
if( @$before == 0 )
{
@$origl = @$after;
} else
{
# connect after to end of before
$lastb->[1] = $after;
@$origl = @$before;
}
}
# first, build input list from @el
my $list = a2l( @el );
say "input list: ", l2s($list);
# second, partition list
partition( $list, $k );
say "partition($k): ", l2s($list);
|
