Solutions to challenge 216

2 files changed, 182 insertions, 0 deletions

diff --git a/challenge-216/jo-37/octave/ch-2.m b/challenge-216/jo-37/octave/ch-2.m
new file mode 100755
index 0000000000..d5cea66c09
--- /dev/null
+++ b/challenge-216/jo-37/octave/ch-2.m
@@ -0,0 +1,112 @@
+#!/usr/bin/octave -qf
+
+#{
+Building the target from some stickers may be formulated as an
+integer linear programming problem.
+
+For each letter in the target word, its quantity needs to be covered by
+the selected stickers.  This results in one linear inequality for each
+unique letter in the target.  The objective is to minimize the total
+number of stickers.
+
+The integer restriction is crucial as "feo" might be build from 1/2 of
+"fee" and "foo" otherwise.
+
+Usage:
+./ch-2.m target sticker...
+#}
+
+function [xopt, fmin] = min_stickers (target, stickers)
+	# Find unique required letters.
+	required = unique(target);
+
+	# RHS of the linear inequations: number of each required letter.
+	for i = 1:numel(required)
+		b(i) = sum(target == required(i));
+	endfor
+
+	# Matrix holding the number of the required letters provided by each
+	# sticker.
+	for i = 1:numel(required)
+		for j = 1:numel(stickers)
+			A(i,j) = sum(stickers{j} == required(i));
+		endfor
+	endfor
+
+	# Objective function: the total number of selected stickers.
+	c = ones(1, numel(stickers));
+
+	# Select ">=" for all inequalities.
+	ctype = repelem("L", numel(b));
+
+	# Select integer type for all variables.
+	vartype = repelem("I", numel(c));
+
+	# Call the LP solver for integer solutions of c'x -> min, A x >= b.
+	[xopt, fmin] = glpk(c, A, b, [], [], ctype, vartype, 1);
+endfunction
+
+# Process program arguments.
+args = argv();
+target = args{1};
+stickers = args(2:nargin);
+printf("target:\t%s\n", target);
+printf("stickers:\n");
+printf("\t%s\n", stickers{:});
+
+# Find the minimum solution.
+[xopt, fmin] = min_stickers(target, stickers);
+
+# Print the solution.
+printf("%d stickers needed to build \"%s\":\n", fmin, target);
+for i = 1:numel(xopt)
+	if xopt(i) > 0
+		printf("%d x %s\n", xopt(i), stickers{i});
+	endif
+endfor
+
+#{
+target:	peon
+stickers:
+	perl
+	raku
+	python
+2 stickers needed to build "peon":
+1 x perl
+1 x python
+#
+target:	goat
+stickers:
+	love
+	hate
+	angry
+3 stickers needed to build "goat":
+1 x love
+1 x hate
+1 x angry
+#
+target:	accommodation
+stickers:
+	come
+	nation
+	delta
+4 stickers needed to build "accommodation":
+2 x come
+1 x nation
+1 x delta
+#
+target:	accommodation
+stickers:
+	come
+	country
+	delta
+NA stickers needed to build "accommodation":
+#
+target:	feo
+stickers:
+	fee
+	foo
+2 stickers needed to build "feo":
+1 x fee
+1 x foo
+#}
diff --git a/challenge-216/jo-37/perl/ch-1.pl b/challenge-216/jo-37/perl/ch-1.pl
new file mode 100755
index 0000000000..be1b89148f
--- /dev/null
+++ b/challenge-216/jo-37/perl/ch-1.pl
@@ -0,0 +1,70 @@
+#!/usr/bin/perl -s
+
+use v5.24;
+use Test2::V0;
+
+our ($tests, $examples);
+
+run_tests() if $tests || $examples;	# does not return
+
+die <<EOS unless @ARGV;
+usage: $0 [-examples] [-tests] [REGNO WORD...]
+
+-examples
+    run the examples from the challenge
+ 
+-tests
+    run some tests
+
+REGNO
+    a registration number
+
+WORD...
+    list of words
+
+EOS
+
+
+### Input and Output
+
+say "@{[filter_words(@ARGV)]}";
+
+
+### Implementation
+
+sub filter_words {
+	my $reg = shift;
+    # Extract all letters from the registration number and transform
+    # them into positive lookahead assertions.
+    my $letters = join '', map "(?=.*?$_)", $reg =~ m/[[:alpha:]]/g;
+
+    # Filter the words for those containing all letters from the
+    # registration number.
+    grep /^$letters/i, @_
+}
+
+
+### Examples and tests
+
+sub run_tests {
+    SKIP: {
+        skip "examples" unless $examples;
+
+        is [filter_words('AB1 2CD', 'abc', 'abcd', 'bcd')], ['abcd'],
+            'example 1';
+
+        is [filter_words('007 JB', 'job', 'james', 'bjorg')],
+            ['job', 'bjorg'], 'example 2';
+
+        is [filter_words('C7 RA2', 'crack', 'road', 'rac')],
+            ['crack', 'rac'], 'example 3';
+
+    }
+
+    SKIP: {
+        skip "tests" unless $tests;
+	}
+
+    done_testing;
+    exit;
+}