I’ve been doing the Weekly
Challenges. The
latest
involved list processing and string assembly. (Note that this ends
today.)
Task 1: Distinct Average
You are given an array of numbers with even length.
Write a script to return the count of distinct average. The average
is calculate by removing the minimum and the maximum, then average
of the two.
Well, we don't need to go that far; if the average of A and B is a
distinct number, so is A+B. So none of that messy floating point
nonsense. Perl:
sub distinctaverage($a0) {
We'll need lots of maxima and minima, so sort the list.
my @a = sort { $::a <=> $::b } @{$a0};
Work out the offset for second elements.
my $offset = scalar @a - 1;
my %res;
Iterate through the indices of the first half of the array
foreach my $i (0 .. (scalar @a) / 2) {
combining each element with its mirror (first plus Nth, second plus
(N-1)th, etc.) and storing the sums in a set. (A true set in languages
that have them, a hash otherwise.)
$res{$a[$i] + $a[$offset - $i]} = 1;
}
Number of set keys is number of distinct values.
scalar keys %res;
}
Obviously one could equally well shift and pop the first and last
elements off the sorted array.
Task 2: Backspace Compare
You are given two strings containing zero or more #.
Write a script to return true if the two given strings are same by
treating # as backspace.
The obvious thing to do here seems to me to be to build up the output
string one character at a time. I'm happier doing this with
variable-length arrays than with actual strings, so in Rust:
fn backspacecompare(a: &str, b: &str) -> bool {
I'll stow the output strings here.
let mut sa: Vec<String> = Vec::new();
Do the same thing to each string. (Yeah, I could write a separate
function to do this. In retrospect I might well do that.)
for i in [a, b] {
let mut oa = Vec::new();
Iterate over characters.
for c in i.chars() {
If it's a "#", discard it and the previous character.
if c == '#' {
oa.pop();
Otherwise, append it.
} else {
oa.push(c)
}
}
Join the output into a string, and store it.
sa.push(oa.iter().collect());
}
Return the comparison.
sa[0] == sa[1]
}
PostScript is of course especially well suited to this kind of
stack-based manipulation, and it can be done without even any local variables.
/backspacecompare {
Turn the two input parameters into a 2-element array.
2 array astore
Iterate over that array.
{
Start a new array, and push that start down below the string we're
about to work on.
[ exch
Convert that string to an array of chars, and interate over it.
s2a {
We may need to use it twice.
dup
If it's a hash sign, discard the duplicate and the previous character.
Otherwise the duplicate is left on top of the stack.
35 eq {
pop pop
} if
} forall
End the array.
]
} forall
So by this point we have two arrays of processed character sequences.
Compare them. (We could convert them to strings first, but my deepeq
works on either.)
deepeq
} bind def
Full code on
github.