This is my response to The Weekly Challenge #400.
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.
#! /usr/bin/env raku
unit sub MAIN (Int $n where $n > 0,
:v(:$verbose));
my @kept;
my $best = 0;
for 1 .. $n -> $i
{
my @digits = $i.comb;
next if @digits.repeated;
if @kept
{
my $jump = $i - @kept.tail;
if $jump > $best
{
$best = $jump;
say ": { @kept.tail } -> $i, jump $jump" if $verbose;
}
}
@kept.push: $i;
}
say ": seq: @kept[]" if $verbose;
say $best;
[3] A positive integer.
[6] The values we have kept so far.
[7] The best (largest) jump so far. The initial value of 0 is the default result if we give the program the value 1 as input.
[9] Iterate over all the integers from 1 to the given upper limit.
[11] Get a list of individual digits.
[13] Skip the number if it has repeating digits.
See docs.raku.org/routine/repeated for more information about repeated.
[15] Have we kept at least one value already?
[17] Calculate the jump. tail gives us the last elent in an
array.
See docs.raku.org/routine/tail for more information about tail.
[18] Is the new jump better than the current record?
[20] If so, use the new jump.
[25] Keep the value, as all the digits are distinct.
[28] Print the result.
Running it:
$ ./largest-interval-tail 20
2
$ ./largest-interval-tail 110
4
$ ./largest-interval-tail 500
11
$ ./largest-interval-tail 2026
105
$ ./largest-interval-tail 10000
105
Looking good.
With verbose mode:
$ ./largest-interval-tail -v 20
: 1 -> 2, jump 1
: 10 -> 12, jump 2
: seq: 1 2 3 4 5 6 7 8 9 10 12 13 14 15 16 17 18 19 20
2
$ ./largest-interval-tail -v 110
: 1 -> 2, jump 1
: 10 -> 12, jump 2
: 98 -> 102, jump 4
: seq: 1 2 3 4 5 6 7 8 9 10 12 13 14 15 16 17 18 19 20 21 23 24 25 26 27 28 \
29 30 31 32 34 35 36 37 38 39 40 41 42 43 45 46 47 48 49 50 51 52 53 54 56 \
57 58 59 60 61 62 63 64 65 67 68 69 70 71 72 73 74 75 76 78 79 80 81 82 83 \
84 85 86 87 89 90 91 92 93 94 95 96 97 98 102 103 104 105 106 107 108 109
4
Printing the kept values does not scale very well, so let us stop here.
We do not actually need to keep the kept values, if we drop them from the verbose output (line [28]). All we need is the last one.
File: largest-interval#! /usr/bin/env raku
unit sub MAIN (Int $n where $n > 0,
:v(:$verbose));
my $prev;
my $best = 0;
for 1 .. $n -> $i
{
my @digits = $i.comb;
next if @digits.repeated;
if defined $prev
{
my $jump = $i - $prev;
if $jump > $best
{
$best = $jump;
say ": $prev -> $i, jump $jump" if $verbose;
}
}
$prev = $i;
}
say $best;
[6] Only keep one previous value.
[15] Check for the existene of a previous value.
[25] Ipdate the previous value.
$ ./largest-interval 20
2
$ ./largest-interval 110
4
$ ./largest-interval 500
11
$ ./largest-interval 2026
105
$ ./largest-interval 10000
105
Looking good.
Verbose mode is presentable now:
$ ./largest-interval -v 20
: 1 -> 2, jump 1
: 10 -> 12, jump 2
2
$ ./largest-interval -v 110
: 1 -> 2, jump 1
: 10 -> 12, jump 2
: 98 -> 102, jump 4
4
$ ./largest-interval -v 500
: 1 -> 2, jump 1
: 10 -> 12, jump 2
: 98 -> 102, jump 4
: 109 -> 120, jump 11
11
$ ./largest-interval -v 2026
: 1 -> 2, jump 1
: 10 -> 12, jump 2
: 98 -> 102, jump 4
: 109 -> 120, jump 11
: 987 -> 1023, jump 36
: 1098 -> 1203, jump 105
105
$ ./largest-interval -v 10000
: 1 -> 2, jump 1
: 10 -> 12, jump 2
: 98 -> 102, jump 4
: 109 -> 120, jump 11
: 987 -> 1023, jump 36
: 1098 -> 1203, jump 105
105
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"
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.
#! /usr/bin/env raku
subset GENESTRING where * ~~ /^ <[ACGT]> ** 8 $/;
unit sub MAIN (GENESTRING $start,
GENESTRING $end,
*@bank where @bank.elems > 0
&& all(@bank) ~~ GENESTRING,
:v(:$verbose));
if $start eq $end
{
say ": start=end" if $verbose;
say 0;
exit;
}
my %bank = @bank.Bag;
unless %bank{$end}
{
say ": $end is not in the bank" if $verbose;
say -1;
exit;
}
my @queue = $start;
my @seen-order = $start;
my %seen = $start => 1;
my %parent;
my $steps = 0;
while @queue
{
$steps++;
my @next;
for @queue -> $gene
{
for $gene.comb.kv -> $i, $orig
{
for <A C G T> -> $c
{
next if $c eq $orig;
my $mut = $gene.substr(0, $i) ~ $c ~ $gene.substr($i + 1);
next unless %bank{$mut} && !%seen{$mut};
%parent{$mut} = $gene;
if $mut eq $end
{
my @path = $end;
my $g = $end;
while %parent{$g}
{
$g = %parent{$g};
@path.push: $g;
}
for @path.reverse -> $g
{
say ": $g" if $verbose;
}
say $steps;
exit;
}
@seen-order.push: $mut;
%seen{$mut} = 1;
@next.push: $mut;
}
}
}
@queue = @next;
}
for @seen-order -> $g
{
say ": $g" if $verbose;
}
say -1;
[3] A custom type with susbset for the gene strings.
See docs.raku.org/routine/subset for more information about subset.
[5-7] Apply the custom type on the expected gene string input.
[11-15] No mutiations required? If so, say so and exit.
[18] A hash of the gene values in the bank (for easy lookup later on).
[20-24] Is the end missing from the bank? If so, report an error and exit.
We are doing a breadth-first search of all the possible mutations; apply one mutation, and send it off to the end of the queue for further round(s), if we have not reached the target string. We are doing this until we find a match (the check in [49]) or we run out of mutations (which is a failure).
[28] Used by verbose mode only.
[29] Gene strings we have seen already (to avoid loops).
[30] A hash of parent strings, also used by verbose mode.
[31] The number of mutations (or steps).
[33] As long as the queue is non-empty.
[35] One more iteration.
[36] A list of mutated gene strings that we get from this single string.
[38] Iterate over the queue.
[40] Iterate over the gene string, as single characters. The kv part
gives us the character and the index in the string; key - value.
See docs.raku.org/routine/kv for more information about kv.
[42] Iterate over the 4 legal characters.
[44] Skip the character if it is the same as the source (as that would not be a mutation).
[45] The mutated string.
[46] Skip it if it is not in the bank - or we have seen it already.
[47] Record the parent path, for verbose mode.
[48] Have we reached the end?
[51] This is the shortest path (or one of many equally short ones).
[52] For traversing back the path.
[53] Traverse back to the start.
[55+56] Get the parent, and add it to the path.
[48] Print the path in reverse order, but only if verbose mode is requested.
This is sloppy programming on my part. A lot of stuff is happening that is only used by verbose mode, even if verbose mode is not requested. I'll get back to that later.
[62] Print the number of steps.
[63] Finished!
[66+67] We have not finished yet if we come here. Add the mutation to the seen mutations, both the path and the hash.
[68] Add the mutation to the list of new mutations.
[73] We have finished with the current mutation (or start string), but we have a list of new mutations to add to to the queue.
[76-79] Verbose mode.
[91] We have failed to reach the end mutation. Say so.
Running it:
$ ./minimum-genetic-mutation AACCGGTT AACCGGTA AACCGCTA AAACGGTA
-1
$ ./minimum-genetic-mutation AACCGGTT AACCGGAA AACCGGTA AACCGGAA AACCGCTA \
AACCCTAA AACCGTAA
2
$ ./minimum-genetic-mutation AAAAAAAA AAAAACCC CAAAAAAA CCAAAAAA AAAAAAAC
-1
$ ./minimum-genetic-mutation GAAAAAAA GCCCCCCC GCAAAAAA GCCAAAAA GCCCAAAA \
GCCCCAAA GCCCCCAA GCCCCCCA GCCCCCCC
7
$ ./minimum-genetic-mutation AACCGGTT AACCGGTT AACCGGTA
0
Looking good.
With verbose mode:
$ ./minimum-genetic-mutation -v AACCGGTT AACCGGTA AACCGCTA AAACGGTA
: AACCGGTA is not in the bank
-1
$ ./minimum-genetic-mutation -v AACCGGTT AACCGGAA AACCGGTA AACCGGAA AACCGCTA \
AACCCTAA AACCGTAA
: AACCGGTT
: AACCGGTA
: AACCGGAA
2
$ ./minimum-genetic-mutation -v AAAAAAAA AAAAACCC CAAAAAAA CCAAAAAA AAAAAAAC
: AAAAACCC is not in the bank
-1
$ ./minimum-genetic-mutation -v GAAAAAAA GCCCCCCC GCAAAAAA GCCAAAAA GCCCAAAA \
GCCCCAAA GCCCCCAA GCCCCCCA GCCCCCCC
: GAAAAAAA
: GCAAAAAA
: GCCAAAAA
: GCCCAAAA
: GCCCCAAA
: GCCCCCAA
: GCCCCCCA
: GCCCCCCC
7
$ ./minimum-genetic-mutation -v AACCGGTT AACCGGTT AACCGGTA
: AACCGGTT
0
The program is much easier to follow if we remove verbose mode:
File: minimum-genetic-mutation-verboseless#! /usr/bin/env raku
subset GENESTRING where * ~~ /^ <[ACGT]> ** 8 $/;
unit sub MAIN (GENESTRING $start,
GENESTRING $end,
*@bank where @bank.elems > 0
&& all(@bank) ~~ GENESTRING);
if $start eq $end
{
say 0;
exit;
}
my %bank = @bank.Bag;
unless %bank{$end}
{
say -1;
exit;
}
my @queue = $start;
my %seen = $start => 1;
my $steps = 0;
while @queue
{
$steps++;
my @next;
for @queue -> $gene
{
for $gene.comb.kv -> $i, $orig
{
for <A C G T> -> $c
{
next if $c eq $orig;
my $mut = $gene.substr(0, $i) ~ $c ~ $gene.substr($i + 1);
next unless %bank{$mut} && !%seen{$mut};
if $mut eq $end
{
say $steps;
exit;
}
%seen{$mut} = 1;
@next.push: $mut;
}
}
}
@queue = @next;
}
say -1;
And that's it.