Merge pull request #10784 from JTimothyKing/challenge-285

Solutions to challenge 285 by Tim King

4 files changed, 117 insertions, 0 deletions

diff --git a/challenge-285/jtimothyking/csharp/ch-1.cs b/challenge-285/jtimothyking/csharp/ch-1.cs
new file mode 100644
index 0000000000..d767a65cb7
--- /dev/null
+++ b/challenge-285/jtimothyking/csharp/ch-1.cs
@@ -0,0 +1,27 @@
+namespace _1_no_connection;
+
+public static class NoConnection
+{
+    public static async Task Main()
+    {
+        // Read the input, a series of lines in the format "start end", followed by a blank line.
+        var connections = await Console.In.ReadLinesAsync()
+            .TakeWhile(line => !string.IsNullOrWhiteSpace(line))
+            .Select(line => line.Trim().Split(' ', 2, StringSplitOptions.RemoveEmptyEntries))
+            .Select(parts => (start: parts[0], end: parts[1]))
+            .ToListAsync();
+
+        var startPoints = connections.Select(connection => connection.start).ToHashSet();
+        var unconnectedEndpoints = connections.Select(connection => connection.end)
+            .Where(endpoint => !startPoints.Contains(endpoint))
+            .ToHashSet();
+        foreach (var endpoint in unconnectedEndpoints.Order())
+            Console.WriteLine(endpoint);
+    }
+
+    private static async IAsyncEnumerable<string> ReadLinesAsync(this TextReader reader)
+    {
+        while (await reader.ReadLineAsync() is { } line)
+            yield return line;
+    }
+}
\ No newline at end of file
diff --git a/challenge-285/jtimothyking/csharp/ch-2.cs b/challenge-285/jtimothyking/csharp/ch-2.cs
new file mode 100644
index 0000000000..eecd7616ec
--- /dev/null
+++ b/challenge-285/jtimothyking/csharp/ch-2.cs
@@ -0,0 +1,42 @@
+using System.Collections.Concurrent;
+
+namespace _2_making_change;
+
+public static class MakingChange
+{
+    private static readonly int[] Coins = [1, 5, 10, 25, 50];
+    private static readonly ConcurrentDictionary<ChangeKey, Task<int>> NumWaysTasks = new();
+
+    public static async Task Main()
+    {
+        var amount = int.Parse(await Console.In.ReadLineAsync() ?? "");
+        var numWays = await GetNumWaysToMakeChangeAsync(amount);
+        Console.WriteLine(numWays);
+    }
+
+    private static Task<int> GetNumWaysToMakeChangeAsync(int amount) =>
+        GetNumWaysToMakeChangeAsync(amount, Coins.Length);
+
+    private static Task<int> GetNumWaysToMakeChangeAsync(int amount, int numCoins)
+    {
+        // Calculate the number of ways to make change using recursion.
+
+        // Parallelize and memoize by storing a task for each recursive call.
+        // Each call to CalculateAsync creates a new task, which is executed in a
+        // worker thread managed by the .NET thread pool. This task is stored in
+        // the NumWays concurrent dictionary, and awaiting it returns the result.
+        return NumWaysTasks.GetOrAdd(new ChangeKey(amount, numCoins), CalculateAsync);
+
+        async Task<int> CalculateAsync(ChangeKey key)
+        {
+            if (key.Amount == 0) return 1;
+            if (key.Amount < 0 || key.NumCoins == 0) return 0;
+            // Execute the recursive calls in parallel.
+            var useCoinTask = GetNumWaysToMakeChangeAsync(key.Amount - Coins[key.NumCoins - 1], key.NumCoins);
+            var skipCoinTask = GetNumWaysToMakeChangeAsync(key.Amount, key.NumCoins - 1);
+            return await useCoinTask + await skipCoinTask;
+        }
+    }
+
+    private record struct ChangeKey(int Amount, int NumCoins);
+}
\ No newline at end of file
diff --git a/challenge-285/jtimothyking/perl/ch-1.pl b/challenge-285/jtimothyking/perl/ch-1.pl
new file mode 100644
index 0000000000..e5d7d21cfd
--- /dev/null
+++ b/challenge-285/jtimothyking/perl/ch-1.pl
@@ -0,0 +1,23 @@
+#!/usr/bin/perl
+use v5.38;
+
+# This script solves the problem "No Connection" in the PWC #285.
+# The input is a list of connections, each line containing two points
+# separated by a space. The output is a list of endpoints that are not
+# connected to any other point.
+
+my @connections;
+while (<>) {
+    chomp;
+    last if !length;
+    my ($a, $b) = split ' ';
+    die "Invalid input: $_" unless length $a && length $b;
+    push @connections, [ $a, $b ];
+}
+
+my %is_startpoint = map { $_->[0] => 1 } @connections;
+my %is_unconnected_endpoint = map { $_->[1] => 1 }
+    grep { !exists $is_startpoint{$_->[1]} } @connections;
+say $_ for sort keys %is_unconnected_endpoint;
+
+__END__
diff --git a/challenge-285/jtimothyking/perl/ch-2.pl b/challenge-285/jtimothyking/perl/ch-2.pl
new file mode 100644
index 0000000000..ea5db768ad
--- /dev/null
+++ b/challenge-285/jtimothyking/perl/ch-2.pl
@@ -0,0 +1,25 @@
+#!/usr/bin/perl
+use v5.38;
+
+# This script solves the problem "Making Change" in the PWC #285.
+# The input is a single integer representing the amount of money to make change for.
+# The output is the number of ways to make change for that amount using the coins 1, 5, 10, 25, 50.
+
+my $amount = <>;
+chomp $amount;
+die "Invalid input: $amount" unless $amount =~ /^\d+$/;
+
+# Calculate the number of ways to make change for the given amount
+# using space-optimized tabulation (aka space-optimized DP).
+my @coins = (1, 5, 10, 25, 50);
+my @num_ways = (0) x ($amount + 1);
+$num_ways[0] = 1;
+for my $coin (@coins) {
+    for my $i ($coin..$amount) {
+        $num_ways[$i] += $num_ways[$i - $coin];
+    }
+}
+
+say $num_ways[$amount];
+
+__END__