I’ve been doing the Weekly
Challenges. The
latest
involved sequence filtering and tree walks. (Note that this ends
today.)
Since it's Everybody Codes time I've been cutting down the languages I
use for these problems — particularly part 2, which felt like a bit of a
slog at times.
Task 1: Largest Interval
You are given a positive integer.
Write a script that generates a sequence of integers from 1 to given
positive integer, filtering out any numbers that contain repeating
digits (e.g., 11, 99, 100, and 101 are excluded) and return the
biggest jump.
Two parts to this, therefore, and finding repeated digits seems like a
good thing to break out into its own function. By going step by step,
I can short-circuit a longer calculation (e.g. "11234567890" would
drop out after examining the second character), which the purely
functional approach of splitting it into a counted set couldn't do. In
Perl:
sub hasrepeateddigits($a) {
my %cs;
foreach my $c (split '', $a) {
if (exists $cs{$c}) {
return 1;
}
$cs{$c} = 1;
}
0;
}
Then it's just a matter of generating the numbers. Fairly verbose
here.
sub largestinterval($a) {
Find the numbers with no repeated digits.
my @v = grep {!hasrepeateddigits($_)} (1 .. $a);
Compare them in overlapping pairs to get the differences, and retain
the largest.
my $it = slideatatime(1, 2, @v);
my $d = 0;
my @va;
while (@va = $it->()) {
if (scalar @va == 2) {
$d = max($d, $va[1] - $va[0]);
}
}
$d;
}
A more functional approach, in Scala:
def largestinterval(a: Int): Int = {
val v = (1 to a).filter(x => !hasrepeateddigits(x))
v.sliding(2).map(x => x(1) - x(0)).max
}
Task 2: Minimum Genetic Mutation
You are given start and end gene string along with gene bank.
Write a script to return the minimum number of mutations required to
mutate from start to end gene. Return -1 if there is no such
mutation. A gene must be in a bank to make it a valid gene string.
A gene string can be represented by an 8-character long string, with
choices from 'A', 'C', 'G', and 'T'.
In Rust it's easier to deal with a Vec of char than with a string.
(Better in fact would have been to interpret these as base-36 numbers,
which would have fit in a u64. But in my code for these problems I
try not to go too far down the route of optimisation for a specific
language.)
fn s2v(a: &str) -> Vec<char> {
a.chars().collect::<Vec<char>>()
}
fn minimumgeneticmutation(from0: &str, to0: &str, bank: Vec<&str>) -> i32 {
If start equals end, drop out now and avoid all the work.
if from0 == to0 {
return 0;
}
Generate a map to hold paths.
let mut paths: HashMap<Vec<char>, Vec<Vec<char>>> = HashMap::new();
And set up a list of valid nodes, which will include "from" but not
"to".
let mut nodes = bank.iter().map(|x| s2v(x)).collect::<Vec<_>>();
let from = s2v(from0);
let to = s2v(to0);
nodes.push(from.clone());
Then go through each pair in that list, generating forward and reverse
links if they are exactly one character apart.
for a in 0..nodes.len() - 2 {
for b in a + 1..nodes.len() {
let mut delta = 0;
for c in 0..nodes[a].len() {
if nodes[a][c] != nodes[b][c] {
delta += 1;
if delta > 1 {
break;
}
}
}
if delta == 1 {
let l = paths.entry(nodes[a].clone()).or_insert(Vec::new());
l.push(nodes[b].clone());
let m = paths.entry(nodes[b].clone()).or_insert(Vec::new());
m.push(nodes[a].clone());
}
}
}
Then it's time for a depth-first search. To avoid backtracking, I'll
keep a list of nodes seen.
let mut seen = HashSet::new();
let mut queue: VecDeque<(Vec<char>, usize)> = VecDeque::new();
queue.push_back((from.clone(), 0));
while let Some((gene, depth)) = queue.pop_front() {
Exit if we've reached the target.
if gene == to {
return depth as i32;
}
If this is otherwise a valid node,
if let Some(e) = paths.get(&gene) {
Work out each possible path that doesn't go to a node we've previously
used, and add that to the queue.
let mut sseen = seen.clone();
let d = depth + 1;
for g in e {
if !seen.contains(g) {
queue.push_back((g.clone(), d));
sseen.insert(g.clone());
}
}
seen = sseen;
}
}
If none of that worked, report failure.
-1
}
Full code in all tagged languages is on
codeberg.