Perl Weekly Challenge 400‘s tasks are “Largest Interval” and “Minimum Genetic Mutation”.
When I saw the word “largest”, I immediately thought of The Biggest Ball of Twine in Minnesota.
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.
Example 1
Input: $int = 20
Output: 2
Biggest jump between 10 and 12.
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
c) 329 and 340 => 11
d) 439 and 450 => 11
Example 4
Input: $int = 2026
Output: 105
Biggest jump between 1098 and 1203.
Example 5
Input: $int = 10000
Output: 105
The largest gap is 105, between 1098 and 1203. And again between 8796 and 8901.
Approach
There’s probably a way to do this cleverly, but I’m going to brute force the solution: generate a list of integers without repeated digits, and then find the maximum gap.
Raku
In Raku, we’re using the .grep routine on the List type with a none Junction to find the integers without repeated digits. Then we declare a hash, loop over the indices of the integer list from 2 to the last element, and calculate the difference between the element at that index and the element at the previous element. Then I use the magic of autovivication to initialize a list if one doesn’t already exist and push onto the list for that difference what the previous and current values are.
Then once we’re done with the loop, we grab the maximum key from the hash, making sure we compare the keys as integers, and then we return the maximum key and the list of integers it was between.
sub largestInterval($int) {
my @integers = (1 .. $int).grep(none /(.).*$0/);
my %diffs;
for 2 .. @integers.end -> $i {
my ($prev, $cur) = (@integers[$i-1], @integers[$i]);
my $d = $cur - $prev;
push %diffs{$d}, "$prev and $cur";
}
my $largest = %diffs.keys.max: *.Int;
return $largest, %diffs{$largest};
}View the entire Raku script for this task on GitHub.
$ raku/ch-1.raku
Example 1
Input: $int = 20
Output: 2
Biggest jump between:
• 10 and 12
Example 2
Input: $int = 110
Output: 4
Biggest jump between:
• 98 and 102
Example 3
Input: $int = 500
Output: 11
Biggest jump between:
• 109 and 120
• 219 and 230
• 329 and 340
• 439 and 450
Example 4
Input: $int = 2026
Output: 105
Biggest jump between:
• 1098 and 1203
Example 5
Input: $int = 10000
Output: 105
Biggest jump between:
• 1098 and 1203
• 8796 and 8901Perl
The Perl Version is pretty much the same as the Raku version. I have to import max_by from List::AllUtils, but everything else is pretty much the same.
use List::AllUtils qw( max_by );
sub largestInterval($int) {
my @integers = grep {! /(.).*\1/ } (1 .. $int);
my %diffs;
for my $i ( 2 .. $#integers ) {
my ($prev, $cur) = ($integers[$i-1], $integers[$i]);
my $d = $cur - $prev;
push @{$diffs{$d}}, "$prev and $cur";
}
my $largest = max_by { int($_) } keys %diffs;
return $largest, $diffs{$largest};
}View the entire Perl script for this task on GitHub.
Python
Even the Python solution doesn’t look all that different. I compiled the regex matching whether the number has repeating digits, but the list comprehension putting together the list of integers reads pretty much the same.
The big difference is that I found out a way to have Python autovivify dict entries if they didn’t exist: collections.defaultdict. There’s even an example for doing exactly what I wanted to do: create an empty list at an element if there wasn’t a value already.
import re
from collections import defaultdict
has_repeating = re.compile(r"(.).*\1")
def largest_interval(intval):
integers = [
i for i in range(1, intval+1)
if not has_repeating.search(str(i))
]
diffs = defaultdict(list)
for i in range(2, len(integers)):
prev, cur = integers[i-1], integers[i]
d = cur - prev
diffs[d].append(f'{prev} and {cur}')
largest = max(diffs.keys())
return largest, diffs[largest]View the entire Python script for this task on GitHub.
Elixir
And the Elixir solution was, as always, fun. I discovered that there was a Kernel.=~/2 function that allowed me to work with regular expressions much the way I can in Perl. The (diffs[d] || []) on line 19 lets me simulate autovivication: if there exists an element for key d, it returns it, but if there isn’t an element, it returns an empty list, and Kernel.put_in/2 lets me put the resulting value back in diffs[d] without invoking Map.put/3 using a longer syntax.
def largest_interval(int) do
integers =
1..int
|> Enum.filter(&(!(Integer.to_string(&1) =~ ~r/(.).*\1/)))
diffs =
2..(length(integers) - 1)
|> Enum.reduce(%{}, fn i, diffs ->
{last, cur} =
{Enum.at(integers, i - 1), Enum.at(integers, i)}
d = cur - last
put_in(
diffs[d],
(diffs[d] || []) ++ ["#{last} and #{cur}"]
)
end)
largest = diffs |> Map.keys() |> Enum.max()
{largest, Map.get(diffs, largest)}
endView the entire Elixir script for this task on GitHub.
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’.
Example 1
Input: $start_gene = "AACCGGTT"
$end_gene = "AACCGGTA"
@gene_bank = ("AACCGCTA", "AAACGGTA")
Output: -1
To reach end gene, every intermediate gene and the end gene itself must exist in bank.
Since "AACCGGTA" is missing from bank, it is impossible to complete the mutation sequence.
Example 2
Input: $start_gene = "AACCGGTT"
$end_gene = "AACCGGAA"
@gene_bank = ("AACCGGTA", "AACCGGAA", "AACCGCTA", "AACCCTAA", "AACCGTAA")
Output: 2
Path 1 (2 steps): "AACCGGTT" => "AACCGGTA" => "AACCGGAA"
Path 2 (3 steps): "AACCGGTT" => "AACCGGTA" => "AACCGTAA" => "AACCGGAA"
Example 3
Input: $start_gene = "AAAAAAAA"
$end_gene = "AAAAACCC"
@gene_bank = ("CAAAAAAA", "CCAAAAAA", "AAAAAAAC")
Output: -1
Example 4
Input: $start_gene = "GAAAAAAA"
$end_gene = "GCCCCCCC"
@gene_bank = ("GCAAAAAA", "GCCAAAAA", "GCCCAAAA", "GCCCCAAA", "GCCCCCAA", "GCCCCCCA", "GCCCCCCC")
Output: 7
"GAAAAAAA" => "GCAAAAAA"
"GCAAAAAA" => "GCCAAAAA"
"GCCAAAAA" => "GCCCAAAA"
"GCCCAAAA" => "GCCCCAAA"
"GCCCCAAA" => "GCCCCCAA"
"GCCCCCAA" => "GCCCCCCA"
"GCCCCCCA" => "GCCCCCCC"
Example 5
Input: $start_gene = "AACCGGTT"
$end_gene = "AACCGGTT"
@gene_bank = ("AACCGGTA")
Output: 0
The current genetic sequence already matches the desired end gene.
No mutations are necessary, so the result is 0.
Approach
I think the way to do this is to handle the trivial cases first (end gene is the same as the start gene, end gene or start gene isn’t in the bank), and then treat the gene bank as a tree traversal, where we recurse down paths for each possible path in the bank, and keep the one that returns the most efficient path.
Raku
One of the problems I had was when I was filtering the bank to not include the starting gene for the next recursive call on line 22, I wasn’t getting ANY results. So I dropped into the Raku REPL and tested my code:
[0] > my @bank = ["AACCGGTA", "AACCGGAA", "AACCGCTA", "AACCCTAA", "AACCGTAA"];
[AACCGGTA AACCGGAA AACCGCTA AACCCTAA AACCGTAA]
[1] > my $this = "AACCGGTA";
AACCGGTA
[2] > say @bank.grep({! $_ eq $this });
()What? That’s not right! So I immediately tried ditching the ! and switching the comparator:
[2] > say @bank.grep({ $_ ne $this });
(AACCGGAA AACCGCTA AACCCTAA AACCGTAA)
[2] >Why was that happening? I finally figured it out: the ! was operating on $_ and then using the result in the eq comparison. When I put parenthesis around it, it worked:
[2] > say @bank.grep({! ($_ eq $this) });
(AACCGGAA AACCGCTA AACCCTAA AACCGTAA)
[2] >But I like the ne version better anyway. So one of the things I did was make a function to compare two genes and count how many differences (mutations) there were between them. Since we’re only allowed to step through single mutations (because each single mutation needs to be in the gene bank), we compare the count with 1 and skip any genes that have more than one mutation from the last gene.
Lines 22-24 is my recursive call, where I use my current gene as the new starting point, and I filter it out of the gene bank so we don’t wind up with any infinite loops bopping back and forth between two values.
If we get back a valid result from the recursive call, we add to the number of mutations we’re counting, add the transition from $start to the current $gene to the front of the transition list, and then move on to the next gene. Once we’ve gone through all the genes in the bank, we return the one that produced the best path.
sub mutations($gene1, $gene2) {
my $count = 0;
my @g1 = $gene1.comb;
my @g2 = $gene2.comb;
for 0 .. @g1.end -> $i {
$count++ if @g1[$i] ne @g2[$i];
}
$count
}
sub minimumGeneticMutation($start, $end, @bank) {
return (0, []) if $start eq $end;
return (-1, []) unless $end eq @bank.any;
my @branches;
for @bank -> $gene {
next unless mutations($start, $gene) == 1;
my ($count, $transitions) = minimumGeneticMutation(
$gene, $end, @bank.grep({ $_ ne $gene })
);
next if $count < 0;
$count++;
$transitions.unshift(qq{ "$start" => "$gene"});
@branches.push({
count => $count, transitions => $transitions
});
}
return (-1, []) unless @branches;
my $best = @branches.min: *.{"count"};
return ($best.{"count"}, $best.{"transitions"});
}View the entire Raku script for this task on GitHub.
$ raku/ch-2.raku
Example 1
Input: $start_gene = AACCGGTT
$end_gene = AACCGGTA
@gene_bank = ("AACCGCTA", "AAACGGTA")
Output: -1
Example 2
Input: $start_gene = AACCGGTT
$end_gene = AACCGGAA
@gene_bank = ("AACCGGTA", "AACCGGAA", "AACCGCTA", "AACCCTAA", "AACCGTAA")
Output: 2
Transitions:
"AACCGGTT" => "AACCGGTA"
"AACCGGTA" => "AACCGGAA"
Example 3
Input: $start_gene = AAAAAAAA
$end_gene = AAAAACCC
@gene_bank = ("CAAAAAAA", "CCAAAAAA", "AAAAAAAC")
Output: -1
Example 4
Input: $start_gene = GAAAAAAA
$end_gene = GCCCCCCC
@gene_bank = ("GCAAAAAA", "GCCAAAAA", "GCCCAAAA", "GCCCCAAA", "GCCCCCAA", "GCCCCCCA", "GCCCCCCC")
Output: 7
Transitions:
"GAAAAAAA" => "GCAAAAAA"
"GCAAAAAA" => "GCCAAAAA"
"GCCAAAAA" => "GCCCAAAA"
"GCCCAAAA" => "GCCCCAAA"
"GCCCCAAA" => "GCCCCCAA"
"GCCCCCAA" => "GCCCCCCA"
"GCCCCCCA" => "GCCCCCCC"
Example 5
Input: $start_gene = AACCGGTT
$end_gene = AACCGGTT
@gene_bank = ("AACCGGTA")
Output: 0Perl
Really, the Perl solution is the same as the Raku solution, except we need to import any and min_by from List::AllUtils.
use List::AllUtils qw( any min_by );
sub mutations($gene1, $gene2) {
my $count = 0;
my @g1 = split //, $gene1;
my @g2 = split //, $gene2;
for my $i ( 0 .. $#g1 ) {
$count++ if $g1[$i] ne $g2[$i];
}
$count
}
sub minimumGeneticMutation($start, $end, @bank) {
return (0, []) if $start eq $end;
return (-1, []) unless any { $end eq $_ } @bank;
my @branches;
for my $gene ( @bank ) {
next unless mutations($start, $gene) == 1;
my ($count, $transitions) = minimumGeneticMutation(
$gene, $end, @{[ grep { $_ ne $gene } @bank ]}
);
next if $count < 0;
$count++;
unshift @$transitions, qq{ "$start" => "$gene"};
push @branches, {
count => $count, transitions => $transitions
};
}
return (-1, []) unless @branches;
my $best = min_by { $_->{count} } @branches;
return ($best->{count}, $best->{transitions});
}
View the entire Perl script for this task on GitHub.
Python
To my eyes, the Python solution looks a lot like the Raku and Perl solutions. I was using a list.insert(), but then I read about the deque (double-ended queue) objects from the collections class, which allow you to quickly append and pop elements from either end of the queue, and I had to use them.
from collections import deque
def mutations(gene1, gene2):
count = 0
g1 = list(gene1)
g2 = list(gene2)
for i in range(0, len(g1)):
if g1[i] != g2[i]: count += 1
return count
def minimum_genetic_mutation(start, end, bank):
if start == end: return 0, deque([])
if end not in bank: return -1, deque([])
branches = []
for gene in bank:
if mutations(start, gene) != 1: continue
count, transitions = minimum_genetic_mutation(
gene, end, [ g for g in bank if g != gene ]
)
if count < 0: continue
count += 1
transitions.appendleft(f' "{start}" => "{gene}"')
branches.append({
"count": count, "transitions": transitions
})
if not branches: return -1, deque([])
best = min(branches, key=lambda e: e["count"])
return best["count"], best["transitions"]View the entire Python script for this task on GitHub.
Elixir
First, because end is a reserved word in Elixir, I had to change the name of that variable to stop. I could have used end_gene, but I wanted to keep the variable name short.
In my Elixir code, I’m starting to play some more with the functionality of the Access module. One of the things that Access lets you do with Maps is access individual elements of a Map using map[key], which is much more concise than Map.get(map, key). Sadly, we can’t use this syntax for Lists, so I defined an anonymous function on lines 5-9 to convert the list produced by String.graphemes/1 and turn it into a map with the character positions as the keys.
Then I used the feature from Access where, if my map map is made of predefined Atom keys, I can use the syntax map.key instead of map[key]. By pushing maps with predefined atom keys onto my branches list, I could use the map.key syntax in line 59 when determining the minimum path using Enum.min_by/4, or on line 60 when returning the values for :count and :transitions from that map.
def mutations(gene1, gene2) do
str_to_map = fn str ->
str
|> String.graphemes()
|> then(&(Enum.zip(0..length(&1), &1) |> Map.new()))
end
g1 = str_to_map.(gene1)
g2 = str_to_map.(gene2)
Enum.reduce(0..map_size(g1), 0, fn i, count ->
if g1[i] != g2[i], do: count + 1, else: count
end)
end
def minimum_genetic_mutation(start, stop, _)
when start == stop, do: {0, []}
def minimum_genetic_mutation(start, stop, bank) do
if not Enum.any?(bank, &(&1 == stop)) do
{-1, []}
else
branches =
bank
|> Enum.reduce([], fn gene, branches ->
if mutations(start, gene) == 1 do
{count, transitions} =
minimum_genetic_mutation(
gene,
stop,
Enum.filter(bank, &(&1 != gene))
)
if count >= 0 do
branches ++
[
%{
count: count + 1,
transitions:
[" \"#{start}\" => \"#{gene}\""] ++
transitions
}
]
else
branches
end
else
branches
end
end)
if length(branches) == 0 do
{-1, []}
else
branches
|> Enum.min_by(& &1.count)
|> then(& {&1.count, &1.transitions})
end
end
endView the entire Elixir script for this task on GitHub.
Here’s all my solutions in GitHub: https://github.com/packy/perlweeklychallenge-club/tree/challenge-400-packy-anderson/challenge-400/packy-anderson