diff options
Diffstat (limited to 'challenge-086/jo-37/perl')
| -rw-r--r-- | challenge-086/jo-37/perl/ch-1.md | 179 | ||||
| -rwxr-xr-x | challenge-086/jo-37/perl/ch-1.pl | 32 | ||||
| -rwxr-xr-x | challenge-086/jo-37/perl/ch-2.pl | 94 |
3 files changed, 126 insertions, 179 deletions
diff --git a/challenge-086/jo-37/perl/ch-1.md b/challenge-086/jo-37/perl/ch-1.md deleted file mode 100644 index 7cf7efba8b..0000000000 --- a/challenge-086/jo-37/perl/ch-1.md +++ /dev/null @@ -1,179 +0,0 @@ -# Interwoven numbers - -## The task - -You are given an array of real numbers greater than zero. - -Write a script to find if there exists a triplet `(a,b,c)` such that - - S) 1 < a + b + c < 2 - -Print 1 if you succeed otherwise 0. - -Let's call the inequality chain S) the `sum conditions`. - -## Motivation - -The first attempt to solve this task was a simple combinatorical -approach as given in `triplet_sum_combine`. -To reduce the search space, some sanity checks were added that would -possibly exclude some of the elements. -The idea behind it: If a number plus the smallest sum of two other -numbers exceeds 2, this number cannot be part of a valid triplet. -And the other way round: If a number plus the largest sum of two other -numbers is below one, it cannot be part of a valid triplet neither. - -This worked well from the beginning, but one piece was missing: -There was no test case with a proper list of reduced numbers that failed -the combinatorical part. -Finding such numbers appeared difficult at first and turned out to be -impossible, leading to an unexpected solution to the task. - -Trying to find such a non-existent combination of numbers satisfying the -filter conditions but violating the sum conditions revealed the complex -dependencies between these numbers. -Driving one number towards a certain limit never led to a violation of -a sum condition but instead to the existence of a new valid triplet or -the removal of a number from the reduced list. -This experience led to the title `Interwoven numbers`. - -## List reduction - -Let `sps` be the smallest partial sum of two of the given numbers -and `lps` be the largest partial sum. -These are easily found after the numbers have been sorted. -The list of numbers is then reduced by (repeatedly) applying the filter - - m > 1 - lps && m < 2 - sps - -on the members `m` of the list. - -The filter condition consists of two parts: - - m < 2 - sps - m > 1 - lps - -For the second expression to take effect, `lps` has to be -smaller than one, requiring all numbers and `sps` to be smaller -than one, too. -But in this case all numbers comply to the first part of the filter -condition, making it a no-op, which in turn leaves `lps` unchanged as -there is no modification at the larger values of the list. -In summary, a list modification at the lower values can occur only once. - -As a consequence, the value of `sps` in the first expression may change -only once and thus the whole filter will stay unmodified after it has -been applied twice, making two the maximum number of required filter -applications. - -Note: The maximum loop count of two holds provided that the list has a -length of three or more. -(Otherwise lower and larger values coincide, invalidating the -reasoning.) -Shorter lists can be ignored as these reveal the non-existence of a -solution anyway. - -## Characteristics of a reduced list - -A list shall be called `reduced list` if it is stable under the list -reduction filter. -When the filter has been applied twice to a list, it is a reduced list. - -If a reduced list consists of less than three elements, then there is -obviously no triplet conforming to the sum conditions. - -It is easy to see that a reduced list consisting of three elements -represents a valid triplet. - -So we need to analyse a reduced list consisting of four or more elements. - -Let `a`, `b`, `c` and `d` be the smallest and the largest two numbers -of the reduced list. -Then we have: - - sps = a + b - lps = c + d - -Considering the filter conditions of a reduced list and the order of the -list elements leads to the following chain of inequalities: - - C) 1 - c - d < a <= b <= c <= d < 2 - a - b - -There are three fundamental triplets built from these four elements that -shall be identified by the missing part as follows: - - Xb: (a, c, d) s_xb = a + c + d - Xc: (a, b, d) s_xc = a + b + d - Xd: (a, b, c) s_xd = a + b + c - -We now distinguish four cases depending on the values of `d` and -`s_xb`: - -- Case 1: `d > 1` - - From C) and the condition of case 1 follows: - - a + b + d < 2 - a + b + d > d > 1 - - i.e. - - 1 < s_xc < 2 - - Thus `Xc` is a valid triplet. - -- Case 2: `d < 2/3` - - From C) and the condition of case 2 follows: - - a + c + d > 1 - a + c + d <= 3 * d < 3 * 2/3 = 2 - - i.e. - - 1 < s_xb < 2 - - Hence `Xb` is a valid triplet. - -- Case 3: `2/3 <= d <= 1` and `s_xb < 2` - - Here we have from C) and the condition above: - - a + c + d > 1 - a + c + d = s_xb < 2 - - This identifies `Xb` as a valid triplet. - -- Case 4: `2/3 <= d <= 1` and `s_xb >= 2` - - This is the most interesting and complex case. - Note that there _are_ numbers `a`, `b` and `c` satisfying the - condition `s_xb >= 2` because of `2/3 <= d`. - - From C) and the conditions of case 4 we conclude: - - 2 <= s_xb = a + c + d < a + c + 1 - 1 < a + c - - which in turn leads to: - - 2 > a + b + d >= a + b + c = a + c + b > 1 + b > 1 - 2 > a + b + c = s_xd > 1 - - This reveals `Xd` as a valid triplet. - -In summary, solely from the existence of a reduced list consisting of -three or more members we may conclude the existence of a valid triplet. -Furthermore, there is a fixed set of three triplets that contains at -least one valid triplet. -This provides a source for a solution to the given task. - -There are some test cases at the end of the script comparing the results -from the reduced set implementation with a combinatorical approach for a -number of random sets. - -## Conclusion - -Utilizing these findings, the task can be solved by grep'ing twice over -the list of numbers and then simply comparing the result's length -against three. diff --git a/challenge-086/jo-37/perl/ch-1.pl b/challenge-086/jo-37/perl/ch-1.pl new file mode 100755 index 0000000000..ecc3d718f6 --- /dev/null +++ b/challenge-086/jo-37/perl/ch-1.pl @@ -0,0 +1,32 @@ +#!/usr/bin/perl + +# Cracking the nut with a sledgehammer: +use PDL; +use Test2::V0 '!float'; + +# Check if there is a pair of numbers having the given difference. +# diff is first arg, remaining args are the numbers. +sub find_diff { + my $diff = shift; + my $numbers = long @_; + + # Create a matrix containing all pairwise differences and BAD + # values enabled. + (my $diffs = $numbers - $numbers->transpose)->badflag(1); + + # Invalidate the diagonal. + $diffs->diagonal(0, 1) .= $diffs->badvalue; + + # Check if the given difference exists. + any($diffs == $diff); +} + +is find_diff(7, 10, 8, 12, 15, 5), T(), 'Example 1'; +is find_diff(6, 1, 5, 2, 9, 7), T(), 'Example 2'; +is find_diff(15, 10, 30, 20, 50, 40), F(), 'Example 3'; + +is find_diff(0, 1, 2, 2), T(), 'zero diff exists'; +is find_diff(0, 1, 2, 3), F(), 'zero diff does not exist'; +is find_diff(-2, 1, 2, 4), T(), 'negative diff'; + +done_testing; diff --git a/challenge-086/jo-37/perl/ch-2.pl b/challenge-086/jo-37/perl/ch-2.pl new file mode 100755 index 0000000000..1e9d43bdef --- /dev/null +++ b/challenge-086/jo-37/perl/ch-2.pl @@ -0,0 +1,94 @@ +#!/usr/bin/perl + +use 5.012; +use PDL; +use Test2::V0 '!float'; + +BEGIN { + # Piddle holding valid values as a "constant". + my $valid = sequence(byte, 9) + 1; + sub VALID () {$valid} +} + +# Solver for "beginner sudokus". Only trivial dependencies will be +# examined. +sub sudoku_beginner { + # Convert argument to piddle and turn zeroes to BAD, indicating free + # cells. + my $s = byte(shift)->setvaltobad(0); + + # Check dimensions and values of input data. + die "Invalid sudoku\n" unless $s->ndims == 2 && + $s->dim(0) == 9 && $s->dim(1) == 9 && + all($s->where(isgood $s)->in(VALID)); + + say $s; + + # Loop while there are free cells. + my $bad = nbad $s; + while ($bad) { + # Loop over (the coordinates of) all free cells, identified by + # BAD values. The "byte" type enforces integer arithmetic, + # which is needed for the sub square identification. + # + # A PDL joke: + # The dog bites the flat cat, which is bad - and reversed. + foreach my $free (whichND(isbad $s)->byte->dog) { + # Determine the set difference between the set of valid + # values and the concatenation of row, column and sub square + # values, i.e. find the possible values that are left over + # for the cell. + my $left = setops(VALID, 'XOR', + cat( + $s->dice_axis(0, $free->at(0))->flat, + $s->dice_axis(1, $free->at(1))->flat, + $s->range(($free / 3) * 3, 3)->flat + )->flat); + + # Fix the cell's value if there is a single value left. + $s->indexND($free) .= $left->sclr if $left->nelem == 1; + } + say $s; + + # Give up if there is no progress. + (my $prev_bad, $bad) = ($bad, nbad $s); + die "No straight solution\n" if $bad == $prev_bad; + } + + $s->unpdl; +} + + +# main: + +# Try to solve the puzzle with a beginners-only algorithm. +# Zeroes represent empty fields. +is sudoku_beginner([ + [0, 0, 0, 2, 6, 0, 7, 0, 1], + [6, 8, 0, 0, 7, 0, 0, 9, 0], + [1, 9, 0, 0, 0, 4, 5, 0, 0], + [8, 2, 0, 1, 0, 0, 0, 4, 0], + [0, 0, 4, 6, 0, 2, 9, 0, 0], + [0, 5, 0, 0, 0, 3, 0, 2, 8], + [0, 0, 9, 3, 0, 0, 0, 7, 4], + [0, 4, 0, 0, 5, 0, 0, 3, 6], + [7, 0, 3, 0, 1, 8, 0, 0, 0]]), + + [[4, 3, 5, 2, 6, 9, 7, 8, 1], + [6, 8, 2, 5, 7, 1, 4, 9, 3], + [1, 9, 7, 8, 3, 4, 5, 6, 2], + [8, 2, 6, 1, 9, 5, 3, 4, 7], + [3, 7, 4, 6, 8, 2, 9, 1, 5], + [9, 5, 1, 7, 4, 3, 6, 2, 8], + [5, 1, 9, 3, 2, 6, 8, 7, 4], + [2, 4, 8, 9, 5, 7, 1, 3, 6], + [7, 6, 3, 4, 1, 8, 2, 5, 9]], 'Example 1'; + +like dies {sudoku_beginner(zeroes(9, 9))}, qr/^No straight solution$/, + 'no straight solution'; +like dies {sudoku_beginner(zeroes(9, 9) + 10)}, qr/^Invalid sudoku$/, + 'invalid values'; +like dies {sudoku_beginner(zeroes(9, 9, 9))}, qr/^Invalid sudoku$/, + 'invalid dimensions'; + +done_testing; |