Merge pull request #9320 from Util/c249

Add TWC 249 solutions by Bruce Gray (in Raku and F#).

4 files changed, 225 insertions, 0 deletions

diff --git a/challenge-249/bruce-gray/fsharp/ch-1.fsx b/challenge-249/bruce-gray/fsharp/ch-1.fsx
new file mode 100644
index 0000000000..cd56f410ab
--- /dev/null
+++ b/challenge-249/bruce-gray/fsharp/ch-1.fsx
@@ -0,0 +1,37 @@
+// To execute from the command line: `dotnet fsi fsharp/ch-1.fsx`
+
+type tII = int * int      // Tuple of two `int`s
+let make_tII (ns: list<int>):tII = ns.[0], ns.[1]
+let tII_same (x: tII): bool = fst x = snd x
+
+let list_to_sorted_tuples_of_two (xs) =
+    xs  |> List.sort
+        |> List.chunkBySize 2
+        |> List.map (make_tII)
+
+let task1 (ns: list<int>) =
+
+    let n_n: list<tII> = ns |> list_to_sorted_tuples_of_two
+
+    let all_equal: bool = n_n |> List.forall tII_same
+
+    if all_equal then n_n else []
+
+
+// Below this point is test harness and data
+let mutable test_number = 0
+let is (got: 'a) (expected: 'a) (test_name: string) =
+    test_number <- test_number + 1
+    let ok_msg = if (got = expected) then "ok" else "not ok"
+    printfn $"{ok_msg} {test_number} {test_name}"
+    ()
+
+type TestRecord = { ns: list<int>; expected: list<tII>; }
+// Note: first task example changed here to sorted order, to ease testing.
+let tests : list<TestRecord> = [
+    { ns = [3; 2; 3; 2; 2; 2]; expected = [(2, 2); (2, 2); (3, 3)] };
+    { ns = [1; 2; 3; 4]; expected = [] }
+]
+for test : TestRecord in tests do
+    let got : list<tII> = task1 test.ns
+    is got test.expected "Task1 example"
diff --git a/challenge-249/bruce-gray/fsharp/ch-2.fsx b/challenge-249/bruce-gray/fsharp/ch-2.fsx
new file mode 100644
index 0000000000..1357510d31
--- /dev/null
+++ b/challenge-249/bruce-gray/fsharp/ch-2.fsx
@@ -0,0 +1,41 @@
+// To execute from the command line: `dotnet fsi fsharp/ch-2.fsx`
+
+let task2 (d_and_i_s: string) =
+    // lo,hi will be modified via side-effects within .map
+    let mutable lo = -1
+    let mutable hi =  1 + d_and_i_s.Length
+
+    let squeeze_from_ends (di: char): int =
+        if   di = 'D'
+        then hi <- hi - 1; hi
+        else lo <- lo + 1; lo
+
+    (d_and_i_s + "I")
+        |> Seq.map(squeeze_from_ends)
+        |> Seq.toList
+
+// This is only used for extra round-trip testing.
+let ints_to_DI (ns: list<int>) =
+    ns |> List.pairwise
+       |> List.map (fun (a, b) -> if a > b then "D" else "I")
+       |> List.reduce (+)
+
+// Below this point is test harness and data
+let mutable test_number = 0
+let is (got: 'a) (expected: 'a) (test_name: string) =
+    test_number <- test_number + 1
+    let ok_msg = if (got = expected) then "ok" else "not ok"
+    printfn $"{ok_msg} {test_number} {test_name}"
+    ()
+
+type TestRecord = { di: string; expected: list<int> }
+let tests : list<TestRecord> = [
+    { di = "IDID" ; expected = [0; 4; 1; 3; 2] };
+    { di = "III"  ; expected = [0; 1; 2; 3] };
+    { di = "DDI"  ; expected = [3; 2; 0; 1] };
+]
+
+for test : TestRecord in tests do
+    let got: list<int> = task2 test.di
+    is got test.expected ("Task2 example: " + test.di)
+    is (ints_to_DI got) test.di ("Task2 example: " + test.di + " round-trip")
diff --git a/challenge-249/bruce-gray/raku/ch-1.raku b/challenge-249/bruce-gray/raku/ch-1.raku
new file mode 100644
index 0000000000..b31cc902ed
--- /dev/null
+++ b/challenge-249/bruce-gray/raku/ch-1.raku
@@ -0,0 +1,40 @@
+# By storing @a in a Bag, we have all we need to both
+# check for an even count of each input number,
+# and dish them back out in pairs.
+sub task1_bag_unbag ( @a where * %% 2 ) {
+    my $b = @a.Bag;
+    return $b.values.map(* %% 2).all ?? $b.kxxv.batch(2) !! Empty;
+}
+
+# By sorting @a and pairing up neighbors,
+# we have exactly the pairs that need to be returned,
+# but only after checking that the pairs are all (.[0] == .[1]).
+sub task1_check_pairs_equal ( @a where * %% 2 ) {
+    my @ret = @a.sort.batch(2);
+    return @ret.map({ [eqv] .list }).all ?? @ret !! [];
+}
+
+# The two approaches can be combined, yielding a single-expression solution.
+sub task1_concise ( @a where * %% 2 ) {
+    return @a.Bag.values.all %% 2 ?? @a.sort.batch(2) !! Empty;
+}
+
+
+constant @tests =
+    ( (3, 2, 3, 2, 2, 2), [(2, 2), (3, 3), (2, 2)] ),
+    ( (1, 2, 3, 4), [] ),
+
+    ( (3, 3, 3, 2, 2, 2), [] ),
+;
+constant @subs =
+    :&task1_bag_unbag,
+    :&task1_check_pairs_equal,
+    :&task1_concise,
+;
+use Test; plan @subs * @tests;
+for @subs -> ( :key($sub_name), :value(&task1) ) {
+    for @tests -> ( @in, @expected ) {
+        is-deeply task1(@in).sort.Array,
+                   @expected.sort.Array, "$sub_name: @in[]";
+    }
+}
diff --git a/challenge-249/bruce-gray/raku/ch-2.raku b/challenge-249/bruce-gray/raku/ch-2.raku
new file mode 100644
index 0000000000..3fdbb3c787
--- /dev/null
+++ b/challenge-249/bruce-gray/raku/ch-2.raku
@@ -0,0 +1,107 @@
+# Here you can see the evolution of my thinking of the problem,
+# and the resulting changes in my solutions.
+
+# Used by one solution, and to test for validity.
+sub perm_to_DI ( @perm --> Str ) {
+    my Bool @up = @perm Z< @perm.skip;
+    return <D I>[@up].join;
+}
+
+# There are many solutions to most inputs; DID could be any of <1032 2031 2130 3021 3120>.
+# Choice of D/I will produce 2ⁿ possibilities, but permutations will be N!.
+# This can easily generate all of them for analysis; it just returns the first one found.
+# Either way, it will fail to deliver the particular solution given in the task.
+sub task2_many ( Str $s ) {
+    my @a = 0 .. $s.chars;
+    return @a.permutations.first({ .&perm_to_DI eq $s });
+
+    # my @answers = @a.permutations.grep({ .&perm_to_DI eq $s });
+    # return @answers.tail;
+}
+
+# Popping and shifting from ends works well.
+sub task2b ( Str $s ) {
+    my @a = 0 .. $s.chars;
+    my @ret;
+    for $s.comb -> $D_I {
+        push @ret, ($D_I eq 'D') ?? (@a.pop)
+                !! ($D_I eq 'I') ?? (@a.shift)
+                !!                  die
+                ;
+    }
+    warn if @a != 1; # Only one should be left.
+    push @ret, @a.shift;
+    return @ret.List;
+}
+
+# If we add `D` or `I` to the end, we don't need the final shift/pop!
+sub task2c ( Str $s ) {
+    my @a = 0 .. $s.chars;
+    return "{$s}I".comb.map: {
+            $_ eq 'D' ?? @a.pop
+         !! $_ eq 'I' ?? @a.shift
+         !!              die;
+    }
+}
+
+# Hmmm. Could I sweep once and deposit numbers forward for every I, then reverse and deposit for D?
+# Could I classify the index based on D/I? Yes! Works!
+sub task2d ( Str $s ) {
+    my @aa = 0 .. $s.chars;
+    my %DI = "{$s}I".comb.pairs.classify( *.value, :as{.key} );
+
+    my @ret;
+    @ret[ %DI<I>.list ] = @aa.splice(0, %DI<I>.elems)         if %DI<I>;
+    @ret[ %DI<D>.list ] = @aa.splice(0, %DI<D>.elems).reverse if %DI<D>;
+    return @ret;
+}
+
+# Tighter.
+sub task2e ( Str $s ) {
+    my ( $D, $I ) = "{$s}I".comb.pairs.classify( *.value eq 'D', :as{.key} ){True, False};
+    my @ret;
+    @ret[ $I.list ] =       0 ..^ $I.elems                 if $I;
+    @ret[ $D.list ] = $s.chars … ($s.chars - $D.elems + 1) if $D;
+    return @ret;
+}
+
+# Different.
+sub task2f ( Str $s ) {
+    my ( $D, $I ) = "{$s}I".comb.pairs.classify( *.value eq 'D', :as{.key} ){True, False}.map({ $_ // [] });
+    my @ret;
+    @ret[ $I.list ] =       0 ..^ $I.elems;
+    @ret[ $D.list ] = $s.chars … ($s.chars - $D.elems + 1);
+    return @ret;
+}
+
+# Going back to task2c, and realizing that we don't need the whole array when we are only using the endpoints.
+# Best solution!
+sub task2g ( Str $s ) {
+    my ($lo, $hi) = 0, $s.chars;
+
+    return "{$s}I".comb.map({ $_ eq 'D' ?? $hi-- !! $lo++ });
+}
+
+
+my @tests =
+    ( 'IDID' , (0, 4, 1, 3, 2) ),
+    ( 'III'  , (0, 1, 2, 3) ),
+    ( 'DDI'  , (3, 2, 0, 1) ),
+;
+constant @subs =
+    :&task2_many
+    :&task2b,
+    :&task2c,
+    :&task2d,
+    :&task2e,
+    :&task2f,
+    :&task2g,
+;
+use Test; plan @subs * @tests * 2;
+for @subs -> ( :key($sub_name), :value(&task2) ) {
+    for @tests -> ( $in, @expected ) {
+        is-deeply task2($in).List, @expected, "$sub_name: $in";
+
+        is-deeply perm_to_DI(@expected), $in, "$sub_name: $in round-trip";
+    }
+}