diff options
32 files changed, 962 insertions, 44 deletions
diff --git a/challenge-121/abigail/README.md b/challenge-121/abigail/README.md index 84e45df14e..6179e4c324 100644 --- a/challenge-121/abigail/README.md +++ b/challenge-121/abigail/README.md @@ -1,35 +1,39 @@ # Solutions by Abigail -## [Swap Odd/Even Bits](https://perlweeklychallenge.org/blog/perl-weekly-challenge-120/#TASK1) +## [Invert Bit][task1] -> You are given a positive integer `$N` less than or equal to 255. -> -> Write a script to swap the odd positioned bit with even positioned -> bit and print the decimal equivalent of the new binary representation. +[task1]: https://perlweeklychallenge.org/blog/perl-weekly-challenge-121/#TASK1 + +> You are given integers `0 <= $m <= 255` and `1 <= $n <= 8`. +> +> Write a script to invert `$n` bit from the end of the binary +> representation of `$m` and print the decimal representation of +> the new binary number. ### Examples ~~~~ -Input: $N = 101 -Output: 154 +Input: $m = 12, $n = 3 +Output: 8 ~~~~ -Binary representation of the given number is `01 10 01 01`. -The new binary representation after the odd/even swap is `10 01 10 10`. -The decimal equivalent of `10011010` is `154`. +* Binary representation of `$m = 00001100` +* Invert 3rd bit from the end `= 00001000` +* Decimal equivalent of `00001000 = 8` ~~~~ -Input: $N = 18 -Output: 33 +Input: $m = 18, $n = 4 +Output: 26 ~~~~ -Binary representation of the given number is `00 01 00 10`. -The new binary representation after the odd/even swap is `00 10 00 01`. -The decimal equivalent of `100001` is `33`. +* Binary representation of `$m = 00010010` +* Invert 3rd bit from the end `= 00011010` +* Decimal equivalent of `00011010 = 26` + ### Solutions * [AWK](awk/ch-1.awk) * [Bash](bash/ch-1.sh) * [bc](bc/ch-1.bc) -* [Befunge-93](befunge-93/ch-1.bf93) +* [Befunge-93](befunge-93/ch-1.bf) * [C](c/ch-1.c) * [Go](go/ch-1.go) * [Java](java/ch-1.java) @@ -44,50 +48,43 @@ The decimal equivalent of `100001` is `33`. * [Tcl](tcl/ch-1.tcl) ### Blog -[Swap Odd/Even Bits](https://abigail.github.io/HTML/Perl-Weekly-Challenge/week-120-1.html) +[Invert Bit][blog1] -## [Clock Angle](https://perlweeklychallenge.org/blog/perl-weekly-challenge-119/#TASK2) +## [The Travelling Salesman][task2] -> You are given time `$T` in the format `hh:mm`. +> You are given a `NxN` matrix containing the distances between `N` cities. > -> Write a script to find the smaller angle formed by the hands of an -> analog clock at a given time.<br> -> **HINT: A analog clock is divided up into `12` sectors. One sector -> represents `30` degree (`360/12 = 30`).** +> Write a script to find a round trip of minimum length visiting all `N` +> cities exactly once and returning to the start. -### Examples -~~~~ -Input: $T = '03:10' -Output: 35 degree +### Example ~~~~ +Matrix: [0, 5, 2, 7] + [5, 0, 5, 3] + [3, 1, 0, 6] + [4, 5, 4, 0] -The distance between the `2` and the `3` on the clock is `30` degree. -For the `10` minutes i.e. `1/6` of an hour that have passed. The hour -hand has also moved `1/6` of the distance between the `3` and the `4`, -which adds `5` degree (`1/6` of `30`). The total measure of the angle -is `35` degree. - -~~~~ -Input: $T = '04:00' -Output: 120 degree +Output: + length = 10 + tour = (0 2 1 3 0) ~~~~ ### Solutions * [AWK](awk/ch-2.awk) * [Bash](bash/ch-2.sh) -* [bc](bc/ch-2.bc) -* [Befunge-93](befunge-93/ch-2.bf93) * [C](c/ch-2.c) -* [Go](go/ch-2.go) -* [Java](java/ch-2.java) * [Lua](lua/ch-2.lua) * [Node.js](node/ch-2.js) -* [Pascal](pascal/ch-2.p) * [Perl](perl/ch-2.pl) * [Python](python/ch-2.py) -* [R](r/ch-2.r) * [Ruby](ruby/ch-2.rb) -* [Tcl](tcl/ch-2.tcl) ### Blog -[Clock Angle](https://abigail.github.io/HTML/Perl-Weekly-Challenge/week-120-2.html) +[The Travelling Salesman][blog2] + + + +[task1]: https://perlweeklychallenge.org/blog/perl-weekly-challenge-121/#TASK1 +[task1]: https://perlweeklychallenge.org/blog/perl-weekly-challenge-121/#TASK2 +[blog1]: https://abigail.github.io/HTML/Perl-Weekly-Challenge/week-121-1.html +[blog2]: https://abigail.github.io/HTML/Perl-Weekly-Challenge/week-121-2.html diff --git a/challenge-121/abigail/awk/ch-1.gawk b/challenge-121/abigail/awk/ch-1.gawk new file mode 100644 index 0000000000..2dac5aea72 --- /dev/null +++ b/challenge-121/abigail/awk/ch-1.gawk @@ -0,0 +1,13 @@ +#!/opt/local/bin/gawk + +# +# See ../README.md +# + +# +# Run as: gawk -f ch-1.gawk < input-file +# + +{ + print xor ($1, lshift (1, $2 - 1)) +} diff --git a/challenge-121/abigail/awk/ch-2.awk b/challenge-121/abigail/awk/ch-2.awk new file mode 100644 index 0000000000..d37870f9e7 --- /dev/null +++ b/challenge-121/abigail/awk/ch-2.awk @@ -0,0 +1,86 @@ +#!/usr/bin/awk + +# +# See ../README.md +# + +# +# Run as: awk -f ch-2.awk < input-file +# + +# +# Given a path, return its length +# +function path_length (path, path_nodes, l, i) { + l = 0 + split (path, path_nodes, " ") + for (i = 1; i < length (path_nodes); i ++) { + l += matrix [path_nodes [i - 1], path_nodes [i]] + } + return l +} + +# +# Find the shorted path between 'from' and 'to', visiting +# all the nodes, except the ones already in 'path'. +# +function shortest_path (from, to, path, + visited, path_nodes, shortest, sh_path, l, n, i) { + split (path, path_nodes, " ") + + # + # If 'path' already has all the nodes, close the path and return + # + if (length (path_nodes) == NR) { + return path " " to + } + + # + # For all the nodes in the path, mark them in 'visited' + # + for (i = 0; i < length (path_nodes); i ++) { + visited [path_nodes [i]] = 1 + } + + + # + # Try all posibilities, keep the shortest + # + shortest = max + for (n = 0; n < NR; n ++) { + if (!visited [n]) { + new_path = shortest_path(n, to, path " " n) + l = path_length(new_path) + if (shortest > l) { + shortest = l + sh_path = new_path + } + } + } + + return sh_path +} + + + +BEGIN { + line = 0 + max = 0 # Sum off all path, *no* path will be longer. +} + +{ + # + # Read in the data + # + for (i = 1; i <= NF; i ++) { + matrix [line, i - 1] = $i + max += $i + } + line ++ +} + +END { + path = shortest_path(0, 0, "0") + print (path_length(path)) + print (path) +} diff --git a/challenge-121/abigail/bash/ch-1.sh b/challenge-121/abigail/bash/ch-1.sh new file mode 100644 index 0000000000..affeeb846e --- /dev/null +++ b/challenge-121/abigail/bash/ch-1.sh @@ -0,0 +1,20 @@ +#!/bin/sh + +# +# See ../README.md +# + +# +# Run as: bash ch-1.sh < input-file +# + +set -f + +while read m n +do ((n = 2 ** (n - 1))) + if (((m / n) % 2)) + then ((m = m - n)) + else ((m = m + n)) + fi + echo $m +done diff --git a/challenge-121/abigail/bash/ch-2.sh b/challenge-121/abigail/bash/ch-2.sh new file mode 100644 index 0000000000..63d9751e70 --- /dev/null +++ b/challenge-121/abigail/bash/ch-2.sh @@ -0,0 +1,104 @@ +#!/bin/sh + +# +# See ../README.md +# + +# +# Run as: bash ch-2.sh < input-file +# + +set -f + +declare -A matrix + +# +# Given a path, calculate its length. The path is given as +# a (single) space separated string. +# +function f_path_length () { + local path=$1 + local l=0 + local pat="("${path// /) (}")" + [[ $path =~ $pat ]] + for ((i = 2; i <= ${#BASH_REMATCH[@]}; i ++)) + do ((from = BASH_REMATCH[i - 1])) + ((to = BASH_REMATCH[i])) + ((l += matrix["$from,$to"])) + done + ((path_length = l)) +} + +function f_shortest_path () { + local from=$1 + local to=$2 + local path=$3 + local i + + # + # Split the path so we have the already visited vertices in nodes + # + local pat="("${path// /) (}")" + [[ $path =~ $pat ]] + local nodes=() + for ((i = 1; i < ${#BASH_REMATCH[@]}; i ++)) + do ((nodes[i - 1] = BASH_REMATCH[i])) + done + + # + # If 'path' already has all the nodes, we're done + # + if ((rows == ${#nodes[@]})) + then shortest_path=$path" "$to + return + fi + + # + # Create a mapping of nodes already seen + # + declare -A visited + local seen + for ((i = 0; i < ${#nodes[@]}; i ++)) + do ((seen = nodes[i])) + ((visited[$seen] = 1)) + done + + # + # Try all possibilities, keep the shortest + # + local shortest=9223372036854775807 + local sh_path + local n + local new_path + for ((n = 0; n < rows; n ++)) + do if ((visited[$n] != 1)) + then f_shortest_path $n $to "$path $n" + f_path_length "$shortest_path" + if ((shortest > path_length)) + then ((shortest = path_length)) + sh_path="$shortest_path" + fi + fi + done + + shortest_path=$sh_path +} + +# +# Read in the matrix. Since bash lacks proper multidimensional +# arrays, we use an associative array, using "$x,$y" as key. +# +((rows = 0)) +while read -a row +do for ((c = 0; c < ${#row[@]}; c ++)) + do ((matrix["$rows,$c"] = row[c])) + done + ((rows ++)) +done + + +f_shortest_path 0 0 "0" +f_path_length "$shortest_path" + +echo $path_length +echo $shortest_path diff --git a/challenge-121/abigail/bc/ch-1.bc b/challenge-121/abigail/bc/ch-1.bc new file mode 100644 index 0000000000..70a4aec17b --- /dev/null +++ b/challenge-121/abigail/bc/ch-1.bc @@ -0,0 +1,26 @@ +# +# See ../README.md +# + +# +# Run as: bc ch-1.bc < input-file +# +# The input-file should end with -1 +# + +while (1) { + m = read () + if (m == -1) { + break + } + n = read () + p = 2 ^ (n - 1) + b = (m / p) % 2 + if (b == 1) { + m = m - p + } + if (b == 0) { + m = m + p + } + m +} diff --git a/challenge-121/abigail/befunge-93/ch-1.bf93 b/challenge-121/abigail/befunge-93/ch-1.bf93 new file mode 100644 index 0000000000..b001430bab --- /dev/null +++ b/challenge-121/abigail/befunge-93/ch-1.bf93 @@ -0,0 +1,6 @@ +>>> & :1+!#@_ :& 1- 1 >> \ :! #v_ 1- \ 2* v +^ ^ $ v +^ ^<<<<<<< <<<<<<<<<< +^ v - < v +^< ,+55 . < | %2 \g11 / p11: < + ^ + < diff --git a/challenge-121/abigail/blog.txt b/challenge-121/abigail/blog.txt new file mode 100644 index 0000000000..e7cb6bc94e --- /dev/null +++ b/challenge-121/abigail/blog.txt @@ -0,0 +1 @@ +https://abigail.github.io/HTML/Perl-Weekly-Challenge/week-121-1.html diff --git a/challenge-121/abigail/blog1.txt b/challenge-121/abigail/blog1.txt new file mode 100644 index 0000000000..86e745a56c --- /dev/null +++ b/challenge-121/abigail/blog1.txt @@ -0,0 +1 @@ +https://abigail.github.io/HTML/Perl-Weekly-Challenge/week-121-2.html diff --git a/challenge-121/abigail/c/ch-1.c b/challenge-121/abigail/c/ch-1.c new file mode 100644 index 0000000000..5232ef7262 --- /dev/null +++ b/challenge-121/abigail/c/ch-1.c @@ -0,0 +1,21 @@ +# include <stdlib.h> +# include <stdio.h> +# include <string.h> + +/* + * See ../README.md + */ + +/* + * Run as: cc -o ch-1.o ch-1.c; ./ch-1.o < input-file + */ + +int main (void) { + int m, n; + + while (scanf ("%d %d", &m, &n) == 2) { + printf ("%d\n", m ^ (1 << -- n)); + } + + return (0); +} diff --git a/challenge-121/abigail/c/ch-2.c b/challenge-121/abigail/c/ch-2.c new file mode 100644 index 0000000000..2095c27e21 --- /dev/null +++ b/challenge-121/abigail/c/ch-2.c @@ -0,0 +1,141 @@ +# include <stdlib.h> +# include <stdio.h> +# include <string.h> +# include <stdbool.h> + +/* + * See ../README.md + */ + +/* + * Run as: cc -o ch-2.o ch-2.c; ./ch-2.o < input-file + */ + +typedef unsigned int number; + +number * shortest_path (number ** matrix, number size, number from, number to, + bool * exclude, int exclude_size) { + if (exclude_size + 1 == size) { + number * result; + if ((result = (number *) malloc (3 * sizeof (number))) == NULL) { + perror ("Malloc result failed"); + exit (1); + } + result [0] = 1; + result [1] = matrix [from] [to]; + result [2] = to; + return result; + } + + number * shortest_result; + bool * new_exclude; + if ((new_exclude = (bool *) malloc (size * sizeof (bool))) == NULL) { + perror ("Malloc new_exclude failed"); + exit (1); + } + for (number i = 0; i < size; i ++) { + new_exclude [i] = exclude [i]; + } + new_exclude [from] = true; + + if ((shortest_result = + (number *) malloc ((2 + size) * sizeof (number))) == NULL) { + perror ("Malloc shortest_result failed"); + exit (1); + } + shortest_result [1] = ~0; + for (number i = 2; i < size + 2; i ++) { + shortest_result [i] = -1; + } + + for (number next = 0; next < size; next ++) { + if (next == from || next == to || exclude [next]) { + continue; + } + number * result = shortest_path (matrix, size, next, to, + new_exclude, exclude_size + 1); + if (shortest_result [1] > result [1] + matrix [from] [next]) { + shortest_result [1] = result [1] + matrix [from] [next]; + shortest_result [2] = next; + for (number i = 0; i < result [0]; i ++) { + shortest_result [i + 3] = result [i + 2]; + } + shortest_result [0] = result [0] + 1; + } + + free (result); + } + + return shortest_result; +} + + +int main (void) { + char * line = NULL; + size_t len = 0; + number ** matrix; + bool first_line = true; + + number size = 0; /* Number of nodes */ + number row = 0; /* Count lines/rows */ + + while (getline (&line, &len, stdin) != -1) { + int offset = 0; + number distance; + int off; + /* + * Use the first line to calculate the size + */ + if (first_line) { + int offset = 0; + number distance; + int off; + while (sscanf (line + offset, "%u%n", &distance, &off) == 1) { + offset += off; + size ++; + } + if ((matrix = (number **) + malloc (size * sizeof (number *))) == NULL) { + perror ("Malloc matrix failed"); + exit (1); + } + first_line = false; + } + if ((matrix [row] = (number *) + malloc (size * sizeof (number))) == NULL) { + perror ("Mallocing row failed"); + exit (1); + } + int col = 0; + while (sscanf (line + offset, "%d%n", &distance, &off) == 1) { + offset += off; + matrix [row] [col ++] = distance; + } + row ++; + } + free (line); + + bool * exclude; + if ((exclude = (bool *) malloc ((size) * sizeof (bool))) == NULL) { + perror ("Malloc exclude failed"); + exit (1); + } + for (number i = 0; i < size; i ++) { + exclude [i] = false; + } + + number * result = shortest_path (matrix, size, 0, 0, exclude, 0); + + printf ("%u\n", result [1]); + printf ("0"); + for (number i = 0; i < result [0]; i ++) { + printf (" %u", result [i + 2]); + } + printf ("\n"); + + free (matrix); + free (result); + free (exclude); + + return (0); +} diff --git a/challenge-121/abigail/go/ch-1.go b/challenge-121/abigail/go/ch-1.go new file mode 100644 index 0000000000..32f293ac3a --- /dev/null +++ b/challenge-121/abigail/go/ch-1.go @@ -0,0 +1,25 @@ +package main + +// +// See ../README.md +// + +// +// Run as: go run ch-1.go +// + +import ( + "fmt" +) + +func main () { + var m, n, c int + + for { + c, _ = fmt . Scanf ("%d %d", &m, &n) + if (c != 2) { + break + } + fmt . Printf ("%d\n", m ^ (1 << (n - 1))) + } +} diff --git a/challenge-121/abigail/java/ch-1.java b/challenge-121/abigail/java/ch-1.java new file mode 100644 index 0000000000..db7264601e --- /dev/null +++ b/challenge-121/abigail/java/ch-1.java @@ -0,0 +1,27 @@ +// +// See ../README.md +// + +// +// Run as: ln ch-1.java ch1.java; javac ch1.java; java ch1 < input-file +// + +import java.util.*; + +public class ch1 { + public static void main (String [] args) { + Scanner scanner = new Scanner (System . in); + try { + while (true) { + int m = scanner . nextInt (); + int n = scanner . nextInt (); + System . out . println (m ^ (1 << (n - 1))); + } + } + catch (Exception e) { + // + // EOF + // + } + } +} diff --git a/challenge-121/abigail/lua/ch-1.lua b/challenge-121/abigail/lua/ch-1.lua new file mode 100644 index 0000000000..52b7529007 --- /dev/null +++ b/challenge-121/abigail/lua/ch-1.lua @@ -0,0 +1,23 @@ +#!/opt/local/bin/lua + +-- +-- See ../README.md +-- + +-- +-- Run as: lua ch-1.lua < input-file +-- + +for line in io . lines () do + _, _, m, n = line : find ("(%d+)%s+(%d+)") + x = 1 + for i = 1, n - 1 do + x = x * 2 + end + if math . floor (m / x) % 2 == 1 then + m = m - x + else + m = m + x + end + print (m) +end diff --git a/challenge-121/abigail/lua/ch-2.lua b/challenge-121/abigail/lua/ch-2.lua new file mode 100644 index 0000000000..72ad70f2eb --- /dev/null +++ b/challenge-121/abigail/lua/ch-2.lua @@ -0,0 +1,69 @@ +#!/opt/local/bin/lua + +-- +-- See ../README.md +-- + +-- +-- Run as: lua ch-2.lua < input-file +-- + +function shortest_path (matrix, from, to, exclude) + if (1 + #exclude == #matrix) then + return matrix [from] [to], {to} + end + + local shortest = 10 ^ 999 -- Should be big enough... + local sh_path = {} + local new_exclude = {} + for k, v in pairs (exclude) do + new_exclude [k] = v + end + new_exclude [from] = 1 + + local next + for next = 1, #matrix do + if next == from or next == to or new_exclude [next] == 1 then + goto end_loop + end + + local length + local path + length, path = shortest_path (matrix, next, to, new_exclude) + if shortest > length + matrix [from] [next] then + shortest = length + matrix [from] [next] + sh_path = {} + sh_path [1] = next + for k, v in pairs (path) do + sh_path [k + 1] = v + end + end + ::end_loop:: + end + + return shortest, sh_path +end + + +matrix = {} + +for line in io . lines () do + row = {} + for d in line : gmatch ("%d+") do + table . insert (row, d) + end + table . insert (matrix, row) +end + + +local length +local path +length, path = shortest_path (matrix, 1, 1, {}) + +print (length) +io . write ("0") +for i = 1, #path do + io . write (" ") + io . write (path [i] - 1) +end +print ("") diff --git a/challenge-121/abigail/node/ch-1.js b/challenge-121/abigail/node/ch-1.js new file mode 100644 index 0000000000..77ccfc32f2 --- /dev/null +++ b/challenge-121/abigail/node/ch-1.js @@ -0,0 +1,16 @@ +#!/usr/local/bin/node + +// +// See ../README.md +// + +// +// Run as: node ch-1.js < input-file +// + + require ('readline') +. createInterface ({input: process . stdin}) +. on ('line', line => { + [m, n] = line . split (" ") . map (_ => +_) + console . log (m ^ (1 << -- n)) +}) diff --git a/challenge-121/abigail/node/ch-2.js b/challenge-121/abigail/node/ch-2.js new file mode 100644 index 0000000000..0642115355 --- /dev/null +++ b/challenge-121/abigail/node/ch-2.js @@ -0,0 +1,45 @@ +#!/usr/local/bin/node + +// +// See ../README.md +// + +// +// Run as: node ch-2.js < input-file +// + +let matrix = + require ('fs') +. readFileSync (0) // Read all. +. toString () // Turn it into a string. +. split ("\n") // Split on newlines. +. filter (_ => _ . length) // Filter out empty lines. +. map (_ => _ . split (' ') // Split each line on commas. + . map (_ => +_)) // Turn into numbers. + +function shortest_path (matrix, from, to, exclude) { + if (1 + Object . keys (exclude) . length == matrix . length) { + return [matrix [from] [to], [to]] + } + let shortest = Number . MAX_SAFE_INTEGER + let sh_path = [] + let new_exclude = Object . assign ({}, exclude) + new_exclude [from] = 1 + for (let next = 0; next < matrix . length; next ++) { + if (next == from || next == to || exclude [next] == 1) { + continue + } + let [l, path] = shortest_path (matrix, next, to, new_exclude) + if (shortest > l + matrix [from] [next]) { + shortest = l + matrix [from] [next] + sh_path = path . slice () + sh_path . unshift (next) + } + } + return [shortest, sh_path] +} + +let [length, path] = shortest_path (matrix, 0, 0, {}) + +process . stdout . write (length + "\n") +process . stdout . write ("0 " + path . join (" ") + "\n") diff --git a/challenge-121/abigail/pascal/ch-1.p b/challenge-121/abigail/pascal/ch-1.p new file mode 100644 index 0000000000..2b2c5c71d0 --- /dev/null +++ b/challenge-121/abigail/pascal/ch-1.p @@ -0,0 +1,18 @@ +Program XXX; + +(* *) +(* See ../README.md *) +(* *) + +(* *) +(* Run as: fpc -och-1.out ch-1.p; ./ch-1.out < input-file *) +(* *) + +var m, n: integer; + +begin + while not eof () do begin + readln (m, n); + writeln (m xor (1 shl (n - 1))); + end +end. diff --git a/challenge-121/abigail/perl/ch-1.pl b/challenge-121/abigail/perl/ch-1.pl new file mode 100644 index 0000000000..3ac18cee35 --- /dev/null +++ b/challenge-121/abigail/perl/ch-1.pl @@ -0,0 +1,31 @@ +#!/opt/perl/bin/perl -pla + +use 5.032; + +use strict; +use warnings; +no warnings 'syntax'; + +use experimental 'signatures'; +use experimental 'lexical_subs'; + +# +# See ../README.md +# + +# +# Run as: perl -pla ch-1.pl < input-file +# + +# +# Third week in a row with some trivial bit fiddling... +# +# Restricting ourselves to 8 bit input doesn't make the code any simpler +# -- this code works up to $m = 2^63 - 1, $n = 63 (or 2^31 - 1/31 if +# you're running a 32-bit integer perl). +# + +$_=$F[0]^1<<--$F[1] + + +__END__ diff --git a/challenge-121/abigail/perl/ch-2.pl b/challenge-121/abigail/perl/ch-2.pl new file mode 100644 index 0000000000..2490cf84ce --- /dev/null +++ b/challenge-121/abigail/perl/ch-2.pl @@ -0,0 +1,57 @@ +#!/opt/perl/bin/perl + +use 5.032; + +use strict; +use warnings; +no warnings 'syntax'; + +use experimental 'signatures'; +use experimental 'lexical_subs'; + +# +# See ../README.md +# + +# +# Run as: perl ch-2.pl < input-file +# + +# +# Find the shorted path from '$from' to '$to', using all entries +# in '$matrix', except the ones in '$exclude'. +# +sub shortest_path ($matrix, $from, $to, $exclude) { + if (1 + keys %$exclude == @$matrix) { + # + # We have excluded everything, except the destination. + # This makes it the only, and hence, shortest path. + # + return ($$matrix [$from] [$to], [$to]); + } + + # + # Else, try each node other than $from, $to, and what's in $exclude, + # as the first step. Then recurse, and return the shortest. + # + my |