The Weekly Challenge has hit a round-number milestone. Congratulations to our intrepid host for keeping this going for almost five years, with every sign of going on until the collapse of the universe, or the release of Perl 7, whichever comes first.
What have we teed up for this momentous week? One task about finding intervals, and another about sequences of mutations. Our music will be a deep cut from the Moody Blues: Steppin' in a Slide Zone from the 1978 album "Octave". Because slide and steps. Not feeling the classic rock and roll vibe? Well, mutating bases one at a time in a gene reminds me of voice-leading in music, and a good example of that is Bach's Well-Tempered Clavier. (The part of the clavier in this video is played by a guitar.)
Task 1: Largest Interval
You are given a positive integer. Write a script that generates a sequence of integers from 1 to the 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.
-
Example 1: Input:
$int = 20-
Output:
2 - Biggest jump between 10 and 12.
-
Output:
-
Example 2: Input:
$int = 110-
Output:
4 - Biggest jump between 98 and 102.
-
Example 3: Input:
$int = 500 -
Output:
11 - Biggest jump between: a) 109 and 120 => 11; b) 219 and 230 => 11; ) 329 and 340 => 11; d) 439 and 450 => 11.
-
Output:
-
Example 4: Input:
$int = 2026-
Output:
105 - Biggest jump between 1098 and 1203.
-
Output:
-
Example 5: Input:
$int = 10000-
Output:
105 - The largest gap is 1between 1098 and 1203, and again between 8796 and 8901.
-
Output:
Task 1 Thoughts
Example 5 has an interesting quirk: 10000 obviously has duplicate digits, but the answer doesn't include the interval from 9877 to 10000, which would be bigger than 105. Apparently the interval must end with a non-repeating number.
The obvious thing to do is to follow the directions: generate the sequence, cast out numbers with repeating digits, and find the biggest hole that's left. I gave a little thought to doing the inverse (generating numbers with repeating digits, and counting streaks of consecutive numbers), but it seemed like a lot of more error-prone work.
There's a small sub-problem of checking whether a number has repeating digits. We could count digit frequency, but doing a regular expression match is probably the simplest thing that works.
Task 1 Solution
sub task($int)
{
use List::Util qw/max/; use List::MoreUtils qw/slide/;
return max slide { $b - $a } grep !/(.).*\1/, 1 .. $int;
}
Notes:
-
1..$int-- generate the sequence of all possible numbers -
/(.).*\1/-- match numbers that have a repeating character: capture a character, and find the same character zero or more positions farther along -
grep !//-- select the numbers that don't match the pattern - There's a function in
List::MoreUtilscalledduplicates, which could be used in place ofgrep, but internally it builds a frequency table, which seems like too much overhead. -
slide {$b - $a}-- in the resulting list of numbers, reduce to the consecutive differences -
max-- find the biggest interval - Look, ma, no loops!
- This should be written in Hebrew, because you have to read it right-to-left.
Task 2: Minimum Genetic Mutation
You are given start and end gene string along with a 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 the 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’.
| Example | start_gene | end_gene | gene_bank | Output |
|---|---|---|---|---|
| 1 | AACCGGTT | AACCGGTA | AACCGCTA AAACGGTA | -1 |
| 2 | AACCGGTT | AACCGGAA | AACCGGTA AACCGGAA AACCGCTA AACCCTAA AACCGTAA | 2 |
| 3 | AAAAAAAA | AAAAACCC | CAAAAAAA CCAAAAAA AAAAAAAC | -1 |
| 4 | GAAAAAAA | GCCCCCCC | GCAAAAAA GCCAAAAA GCCCAAAA GCCCCAAA GCCCCCAA GCCCCCCA GCCCCCCC | 7 |
| 5 | AACCGGTT | AACCGGTT | AACCGGTA | 0 |
Example 1: To reach the end gene, every intermediate gene and the end gene itself must exist in bank. Since AACCGGTA is missing from the bank, it is impossible to complete the mutation sequence.
Example 2: Path 1 (2 steps): AACCGGTT => AACCGGTA => AACCGGAA
Example 3: No path
Example 4: GAAAAAAA => GCAAAAAA => GCCAAAAA=> GCCCAAAA=> GCCCCAAA=> GCCCCCAA => GCCCCCCA=> GCCCCCCC
Example 5: The current genetic sequence already matches the desired end gene. No mutations are necessary, so the result is 0.
Task 2 Thoughts
Examples 1 and 5 give us two cases we can easily check for: the bank doesn't include the goal; or nothing needs to be done.
Solving the general case looks like a shortest-path problem. I always hesitate, because thinking about search problems takes me back to studying algorithms. Evaluating for best, worst, and average performance; space/time tradeoffs; pruning and optimization; the possibility of really bad exponential or worse complexity; and the frequent use of recursion left me with the feeling that search algorithms are complicated, but really, it's just not that hard. Suck it up and do a breadth-first search.
The task implies that we need to change exactly one base at a time, which gives us the sub-problem of finding genes that differ in exactly one.
Finding the gene difference
Let's tackle the sub-problem first: how different are two genes?
sub genediffCount($beg, $end)
{
return sum0 map
{ substr($beg, $_, 1) eq substr($end, $_, 1) ? 0 : 1 }
( 0 .. length($beg)-1 );
}
We're checking each index of the strings and counting the base characters that are not equal. Using map instead of a loop reduces it to a one-liner.
A related problem we're going to have is to find which genes in the bank are only different by one base from a given gene. With geneDiffCount in hand, that's easily done:
sub oneMutationAway($g, $bank)
{
grep { genediffCount($g, $_) == 1 } $bank->@*;
}
It's just a grep, so it could be in-line when needed, but let's use this simple function for readability.
Find the shortest sequence of mutations
Despite my unwarranted trepidation, a breadth-first search is barely a dozen lines of code. The function begins by clearing out the easy cases.
To search, I prefer to avoid recursion (it's hard to debug and easy to get confused). Instead, set up a queue of possible next steps. Each queue element is a pair: the gene, and the number of steps it took to get to it. The oneMutationAway function gives us a list of candidates; we can iterate over that list with map to give us the pairs in the queue.
To make the algorithm work, we need to avoid loops, so we set up a %seen hash to look up genes we've already worked on.
If we find the goal gene, we can return out of the middle of the loop. This is where recursive algorithms always break for me: getting the right return value passed up the stack. Without the recursion, it's easy to detect the end condition and finish up.
If we don't find the goal, add the next set of possible mutations to the queue and continue working.
If the queue runs out, then there is no path and the return value is -1.
sub task($start_gene, $end_gene, $gene_bank)
{
return 0 if $start_gene eq $end_gene;
# end_gene must exist in gene_bank
return -1 unless first { $_ eq $end_gene } $gene_bank->@*;
# Breadth-first search for shortest path
my @queue = map { [ $_, 1 ] } oneMutationAway($start_gene, $gene_bank);
my %seen;
while ( my $x = shift @queue )
{
my ( $gene, $count ) = $x->@*;
next if $seen{$gene};
return $count if ( $gene eq $end_gene );
$seen{$gene} = true;
push @queue, map { [ $_, $count+1 ] }
grep { ! $seen{$_} } oneMutationAway($gene, $gene_bank);
}
return -1;
}
Top comments (0)