I’ve been doing the Weekly
Challenges. The
latest
involved list duplicates and integer parsing. (Note that this ends
today.)
Task 1: Duplicate Removals
You are given a string, $str, consisting of lowercase English
letters.
Write a script to return the final string after all duplicate
removals have been made. Repeat duplicate removals on the given
string until we no longer can.
A duplicate removal consists of choosing two adjacent and equal
letters and removing them.
One could search for duplicates repeatedly, but a once-through
algorithm can get the job done more efficiently. Fairly simple if you
have variable-size arrays, and everything I'm using does. For example
in Python:
def duplicateremovals(a):
Initialise the output list.
b = []
Iterate over the input list.
for c in a:
If there is no output list, or its last element doesn't match the
current one, push the current one.
if len(b) == 0 or c != b[-1]:
b.append(c)
Otherwise remove the last element and discard both it and the current
one.
else:
b.pop()
return ''.join(b)
In PostScript I can assemble this on the stack.
/duplicateremovals {
Split the string to an array of characters. (It's nearly that already,
but this makes some operations easier.)
s2a
Bury an array start marker.
[ exch
Iterate over the input list.
{
If there's something in the array
counttomark 0 gt
And it equals the present value
3 copy pop eq and {
Dump both of them. (Otherwise the current value automatically stays on
the stack.)
pop pop
} if
} forall
]
Assemble the output array back into a string.
a2s
} bind def
Task 2: Ascending Numbers
You are given a string, $str, is a list of tokens separated by a
single space. Every token is either a positive number consisting of
digits 0-9 with no leading zeros, or a word consisting of lowercase
English letters.
Write a script to check if all the numbers in the given string are
strictly increasing from left to right.
The trick here is parsing a string to an integer while having to deal
with strings that aren't. Foe me this usually means some sort of
composite return type (Rust, Scala, Kotlin), or the possibility of a
null or undef value. In some languages (e.g. Typst, which doesn't
have error handling, and Ruby, which returns a zero if it can't parse
the string) I check the string against a regexp to match possible
numbers before feeding it to the converter.
(I do not at any point check for positive numbers; by the
specification, a zero should not be parsed. But there aren't any of
those in the test cases.)
Perl:
sub ascendingnumbers($a) {
Initialise the variable for the previously found value.
my $prev = undef;
Iterate words.
foreach my $c (split ' ', $a) {
If it's a number,
if ($c =~ /^[0-9]+$/) {
If we have a previous number and that's no smaller than this one,
fail.
if (defined $prev && $prev >= $c) {
return 0;
}
Store the previous number.
$prev = $c;
}
}
If we get all the way through, succeed.
1;
}
Rust with the Option class makes this cleaner. (Since that's what
parse() returns, I'm using it for the previous value too.)
fn ascendingnumbers(a: &str) -> bool {
let mut prev: Option<u32> = None;
for c in a.split(" ") {
if let Ok(n) = c.parse::<u32>() {
if !prev.is_none() && prev.unwrap() >= n {
return false;
}
prev = Some(n);
}
}
true
}
And PostScript has error handling, quite extensive and configurable if
you want to get into the weeds, but I took an easier approach: the
stopped keyword returns boolean-true if the previous block caused
an error, something like eval in other languages. So I end up
processing the word via:
{
cvi
} stopped {
If it failed, throw away the uconverted string value
pop
} {
Otherwise, process the integer here.
} ifelse
Full code on
github.