diff options
| -rw-r--r-- | challenge-287/ppentchev/LICENSES/BSD-2-Clause.txt | 9 | ||||
| -rw-r--r-- | challenge-287/ppentchev/README | 140 | ||||
| -rw-r--r-- | challenge-287/ppentchev/blog.txt | 1 | ||||
| -rw-r--r-- | challenge-287/ppentchev/docs/index.md | 320 | ||||
| -rw-r--r-- | challenge-287/ppentchev/mkdocs.yml | 48 | ||||
| -rwxr-xr-x | challenge-287/ppentchev/perl/scripts/ch-1.pl | 161 | ||||
| -rwxr-xr-x | challenge-287/ppentchev/perl/scripts/ch-2.pl | 79 | ||||
| -rw-r--r-- | challenge-287/ppentchev/pyproject.toml | 17 | ||||
| -rw-r--r-- | challenge-287/ppentchev/requirements/docs.txt | 7 | ||||
| -rw-r--r-- | challenge-287/ppentchev/tests/01-perl-ch-1.t | 30 | ||||
| -rw-r--r-- | challenge-287/ppentchev/tests/02-perl-ch-2.t | 30 | ||||
| -rw-r--r-- | challenge-287/ppentchev/tests/lib/PWCTest/Ch287.pm | 176 | ||||
| -rw-r--r-- | challenge-287/ppentchev/tox.ini | 28 |
13 files changed, 830 insertions, 216 deletions
diff --git a/challenge-287/ppentchev/LICENSES/BSD-2-Clause.txt b/challenge-287/ppentchev/LICENSES/BSD-2-Clause.txt new file mode 100644 index 0000000000..5f662b354c --- /dev/null +++ b/challenge-287/ppentchev/LICENSES/BSD-2-Clause.txt @@ -0,0 +1,9 @@ +Copyright (c) <year> <owner> + +Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: + +1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. + +2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. diff --git a/challenge-287/ppentchev/README b/challenge-287/ppentchev/README index aadceb51f2..b0b0bb5c11 100644 --- a/challenge-287/ppentchev/README +++ b/challenge-287/ppentchev/README @@ -3,52 +3,26 @@ SPDX-FileCopyrightText: Peter Pentchev <roam@ringlet.net> SPDX-License-Identifier: BSD-2-Clause --> -# Peter Pentchev's solutions to PWC 286 +# Peter Pentchev's solutions to PWC 287 -\[[Home][ringlet-home] | [GitHub][github] +\[[Home][ringlet-home] | [GitHub][github]\] ## Overview This directory contains Peter Pentchev's solutions to the two tasks in -the [Perl & Raku Weekly Challenge 286][pwc-286]. +the [Perl & Raku Weekly Challenge 287][pwc-287]. ## General remarks -### Task 1: Self Spammer - -Most programming languages have (different or the same) string-processing -functions that can: - -- read a file and split it into lines at the same time -- split the whole contents read from a file into lines -- split a string by some commonly-accepted set of whitespace characters - -The tricky part here is finding the program source. -In most of the so-called "interpreted" languages, e.g. Perl, Python, Ruby et al, -there is either a file-global variable or a function that one can call to -obtain the path to the file containing this particular source code line -(note that I put "interpreted" in quotes, since it is common for these languages to -do a precompilation phase to some intermediate representation, e.g. byte-code). -For compiled languages such as Rust, Go, C, C++, etc., this part may be a bit -more difficult since the end result does not generally include the program source code, -so this part may have to depend on some specifics of the build environment and -only be capable to run directly from a build directory near to its source code. - -### Task 2: Order Game +### Task 2: Valid Number There are several approaches to solving this problem: -- trivial: take a pair of numbers, flip a "do we want the smaller or the larger one" flag, - produce the corresponding result, move on to the next pair -- keep this information in an object, feed it numbers one by one or in pairs, let it - update its inner state (or, if it is an immutable object, let it produce a new one with - the inner state updated) -- keep this information in an object, feed it number by number or the whole sequence, - have it work as an iterator that produces numbers for the programming language's - constructs to consume - -Some languages have built-in constructs for dealing with iterators, others can -handle immutable objects easily and efficiently, so the approach depends on +- match the input string against a regular expression +- try to parse the input string using a pre-built parser + +Some languages have built-in constructs for building parsers, others can handle +regular expressions with ease, and some are good at both, so the approach depends on the programming language. ## Running the test suite @@ -56,50 +30,21 @@ the programming language. The `tests/` subdirectory contains a Perl test suite that outputs TAP, so that it can be run using `prove tests` (or, for the more adventurous, `prove -v tests`). -The Python implementation has its own set of static checkers (linters). -Those can be run from the `python/` directory using Tox 4.x - either directly -(`tox run-parallel`) or using [the tox-stages tool][python-tox-stages] -(`tox-stages run`). - -### Task 1: Self Spammer - -This task does not involve any input data (except for the program source itself), -so the programs are executed without any parameters. - -The `PWCTest::Ch286` module in `tests/lib/` defines a `test_self_spammer` function that -runs the specified program, checks whether it output a single line containing a single word, and -then looks for that word in the specified source file (the program itself by default). -Of course, for the Perl implementation there is a bit of a chicken-and-egg problem, since -the test itself must implement the same algorithm to check whether the word that -the program output is actually present as a separate word in the source file. -I played around a bit with the idea of using an external `grep` program to look for -the word, but it turns out that at least GNU grep has some... idionsyncrasies regarding -character sequences like `\<`, `\>`, `'')`, etc, so the output of Perl's `quotemeta` -function was not suitable for feeding to `grep` directly. -Eh, let's hope my solution is correct anyway :) - -The `tests/03-python-ch-1.t` test first looks for a suitable Python 3 interpreter. -If the `PYTHON3` environment variable is defined, it is used as the name or path of -the Python 3 interpreter; oterhwise, `python3` is used. -The test tries to run the Python 3 interpreter for a `pass` command; if that fails, -the tests are skipped. - -### Task 2: Order Game +### Task 2: Valid Number -This task takes some input, so there are two ways of running the program: +This task takes a string as input, so there are two ways of running the program: - if the `PWC_FROM_STDIN` environment variable is not set to the exact value `1`, - the program runs the three sequences given as examples, and produces three numbers on + the program examines the seven strings given as examples, and produces seven words on its standard output stream, each one on a line by itself. - In other words, the program must output `1\n0\n2\n` exactly. + In other words, the program must output `true\nfalse\nfalse\nfalse\ntrue\ntrue\ntrue\n` exactly. - if the `PWC_FROM_STDIN` environment variable is set, the program reads a single line of - text from its standard input, treats it as a sequence of decimal integers separated by - one or more whitespace characters, runs the order game on that sequence, and produces - a single number on a line by itself on its standard output stream. + text from its standard input, treats it as an expression to be examined, and produces + a single word (either "true" or "false") on a line by itself on its standard output stream. -The `PWCTest::Ch286` module in `tests/lib/` defines a `test_order_game_default` function that +The `PWCTest::Ch287` module in `tests/lib/` defines a `test_valid_number_default` function that runs a program with `PWC_FROM_STDIN` unset and expects the exact output, and also -a `test_order_game` function that runs a series of tests with different sequences, +a `test_valid_number` function that runs a series of tests with different sequences, each time running the program with `PWC_FROM_STDIN` set to 1 and feeding it the sequence. If the implementation in any language should provide more than one method, then @@ -114,48 +59,19 @@ the index of the last supported methods, it is ignored and the program proceeds The `tests/02-perl-ch-2.t` test runs these functions on the Perl implementation and produces TAP output suitable for the `prove` tool. -The `tests/03-python-ch-2.t` test first looks for a suitable Python 3 interpreter. -If the `PYTHON3` environment variable is defined, it is used as the name or path of -the Python 3 interpreter; oterhwise, `python3` is used. -The test tries to run the Python 3 interpreter for a `pass` command; if that fails, -the tests are skipped. - ## Implementation details -### Task 1: Self Spammer +### Task 2: Valid Number #### Perl -We use the [FindBin core module][perl-findbin] and its `$Bin` and `$Script` variables to -figure out where the program source is. - -#### Python - -We use Python's built-in `__file__` pseudoglobal variable to find the path to our source file. -Then we use `random.choice()` to select a random word directly without bothering with -an index into the words array. - -### Task 2: Order Game - -#### Perl - -The Perl solution has three major functions: - -- `round_trivial` - run a single round on a list, producing a list with half the number of - elements using the trivial approach: take numbers in pairs, keep a flag, produce - the smaller or the larger one as the flag says, flip it. -- `run_order_game` - run the whole order game on the specified sequence of numbers. - This function currently only uses a single "run a round" implementation, `round_trivial`. - The `PWC_METHOD` environment variable is ignored even if set. -- `parse_stdin` - read a line of numbers from the standard input, break it down into - a list of integers. - -#### Python +The Perl solution has three major elements: -The Python solution defines an `OrderIter` class and an `OrderIterState` enumeration. -The class serves as an iterator, stashing a value and then performing a `min()` or -`max()` operation on the next value fetched from the supplied input. -The `OrderState` enumeration is used to keep track of the stash/yield state. +- `$re_valid_number` - a documented (using the `/x` modifier) regular expression that + determines whether a string represents a valid number or not +- `valid_number` - a function that returns either the string "true" or the string "false" + depending on whether the argument represents a valid number +- `parse_stdin` - read a line from the standard input, return it as a string to be examined ## Contact @@ -164,9 +80,7 @@ They are developed in [the common PWC-club GitHub repository][github]. This documentation is hosted at [Ringlet][ringlet-home]. [roam]: mailto:roam@ringlet.net "Peter Pentchev" -[github]: https://github.com/manwar/perlweeklychallenge-club/tree/master/challenge-286/ppentchev "These solutions at GitHub" -[ringlet-home]: https://devel.ringlet.net/misc/perlweeklychallenge-club/286/ "This documentation at Ringlet" +[github]: https://github.com/manwar/perlweeklychallenge-club/tree/master/challenge-287/ppentchev "These solutions at GitHub" +[ringlet-home]: https://devel.ringlet.net/misc/perlweeklychallenge-club/287/ "This documentation at Ringlet" -[perl-findbin]: https://perldoc.perl.org/FindBin "The FindBin Perl core module" -[pwc-286]: https://theweeklychallenge.org/blog/perl-weekly-challenge-286/ "The 286th Perl & Raku Weekly Challenge" -[python-tox-stages]: https://devel.ringlet.net/devel/test-stages "Run Tox tests in groups" +[pwc-287]: https://theweeklychallenge.org/blog/perl-weekly-challenge-287/ "The 287th Perl & Raku Weekly Challenge" diff --git a/challenge-287/ppentchev/blog.txt b/challenge-287/ppentchev/blog.txt new file mode 100644 index 0000000000..18df411bb5 --- /dev/null +++ b/challenge-287/ppentchev/blog.txt @@ -0,0 +1 @@ +https://devel.ringlet.net/misc/perlweeklychallenge-club/287/ diff --git a/challenge-287/ppentchev/docs/index.md b/challenge-287/ppentchev/docs/index.md index 388239e6f1..ff6dd94112 100644 --- a/challenge-287/ppentchev/docs/index.md +++ b/challenge-287/ppentchev/docs/index.md @@ -3,52 +3,163 @@ SPDX-FileCopyrightText: Peter Pentchev <roam@ringlet.net> SPDX-License-Identifier: BSD-2-Clause --> -# Peter Pentchev's solutions to PWC 286 +# Peter Pentchev's solutions to PWC 287 \[[Home][ringlet-home] | [GitHub][github]\] ## Overview This directory contains Peter Pentchev's solutions to the two tasks in -the [Perl & Raku Weekly Challenge 286][pwc-286]. +the [Perl & Raku Weekly Challenge 287][pwc-287]. ## General remarks -### Task 1: Self Spammer +### Task 1: Strong Password -Most programming languages have (different or the same) string-processing -functions that can: - -- read a file and split it into lines at the same time -- split the whole contents read from a file into lines -- split a string by some commonly-accepted set of whitespace characters - -The tricky part here is finding the program source. -In most of the so-called "interpreted" languages, e.g. Perl, Python, Ruby et al, -there is either a file-global variable or a function that one can call to -obtain the path to the file containing this particular source code line -(note that I put "interpreted" in quotes, since it is common for these languages to -do a precompilation phase to some intermediate representation, e.g. byte-code). -For compiled languages such as Rust, Go, C, C++, etc., this part may be a bit -more difficult since the end result does not generally include the program source code, -so this part may have to depend on some specifics of the build environment and -only be capable to run directly from a build directory near to its source code. - -### Task 2: Order Game +#### What we have to do + +There are three things that could be wrong with a string: + +- it may be too short +- it may not have characters of enough distinct classes +- it may have one or more too long runs of repeating characters + +#### What we can do + +There are two actions that we will perform on a string to improve its strength as +a password: + +- add a character to the end; this may increase the string length if necessary and + also mark another character class as represented in the string +- replace a character within the string; this may mark another character class as + represented, and also break a long run of characters + +Note that we will not delete characters from the string at all; there is no case in +which deleting a character will lead to fewer steps in strengthening a password. + +It is always possible to add a character to the end of the string in such a way that +it is in a different character class than the one before it (if the string is not empty). +An even stronger assertion is that if a string does not yet contain characters of +a specific class, it is always possible to add a character to the end in such a way that +the new one will be in the required class, so that a single change will improve +the password strength in two ways at the same time. + +Since there are three different character classes, it is also always possible to +replace an existing character in such a way that the class of the new one is not +the same as the class of either the previous or the next character (if those exist). +An even stronger assertion is that if a string does not yet contain characters of +a specific class, it is always possible to replace a specific character so that +the new one will be in the required class, so that a single change will improve +the password strength in two ways at the same time. + +#### Examining a string + +The exact character classes of the specific characters within the string or the ones +added or replaced do not really matter; they are practically interchangeable. +For the purposes of judging a string's password strength it is enough to count +the different classes, no need to keep track of which ones are represented. +This means that we can define a function that examines a string and reports on three of +its aspects: + +- its length in characters as a single number +- the number of character classes already represented in it +- a set (possibly empty) of numbers representing the lengths of the different runs of + repeating characters (three or more) within the string + +Once we have examined a string, we can start "fixing" it, improving the strength of +the password. + +#### Fixing long runs of characters + +If there are any long runs, then it is mandatory to fix them. +This can be done by replacing as many characters as necessary in each run to break it into +pieces of two or more characters. +The number of characters to replace in each run is equal to the length of the run +divided by three and rounded down: + +- for runs of 0, 1, or 2 characters, we don't need to replace anything +- for runs of 3, 4, or 5 characters, it is enough to replace a single one +- for runs of 6, 7, or 8 characters, it is enough to replace two, etc. + +As mentioned above, each time we replace a character we can also make the new one +represent a new character class within the password. + +Thus, a function that fixes the long runs can take as input the result of +examining a string (its length, the number of its character classes, and +the lengths of the long runs), and return the number of "replace a character" +actions needed along with the updated state of the string. +We do not need to examine any new strings to get the updated state; all we need to do is +decrease the number of not-yet-represented character classes by the number of +characters replaced, possibly bringing it down to zero. +The string length will not change. + +#### Fixing the string length + +If the string is too short, then it is mandatory to add characters to the end. +The number of characters to add is equal to the difference between the desired length (6) and +the current length of the string. + +As mentioned above, each time we add a character we can also make the new one +represent a new character class within the password. + +Thus, a function that fixes the string length can take as input the result of +examining a string (its length, the number of its character classes, and +the lengths of the long runs), and return the number of "add a character" +actions needed along with the updated state of the string. +We do not need to examine any new strings to get the updated state; all we need to do is +decrease the number of not-yet-represented character classes by the number of +characters added, possibly bringing it down to zero. +The number and respective length of too-long runs of the same characters will not change. + +#### Adding more character classes + +If after breaking the long runs and extending the string to the desired length it should +turn out that it still does not contain characters of enough different classes, it is +mandatory to fix that, too. +The shortest way to do it is to replace as many characters as needed (at most two, since +there must be at least one character class represented in a string of six characters or more); +as noted above, since each character has at most two neighbors, we can always replace it +with one of a character class that is different from those of its neighbors, so at each step +we can always replace a character with one in the desired missing class. + +Thus, a function that fixes the missing classes can take as input the result of +examining a string (its length, the number of its character classes, and +the lengths of the long runs), and return the number of "replace a character" +actions needed along with the updated state of the string. +We do not need to examine any new strings to get the updated state; all we need to do is +decrease the number of not-yet-represented character classes by the number of +characters replaced, possibly bringing it down to zero. +If we do this as a third step, after fixing the other two classes of problems, then +neither the string length (already enough) nor the number and length of too-long runs +(already none) will change. + +#### Bringing it all together + +The algorithm for improving a password's strength will then look as follows: + +- examine the initial string, noting its length, the number of character classes missing, + and the number and respective lengths of the too-long runs of the same characters +- start with 0 as the number of actions taken +- fix the too-long runs: for each run, increase the number of actions by its length + divided by 3 and rounded down; at the same time, decrease the number of missing + character classes by the same amount if needed +- fix the string length: if needed, increase the number of actions by the difference between + the desired length (6) and the current string length; decrease the number of + missing character classes by the same amount if needed +- fix any remaining missing character classes: increase the number of actions by + the number of character classes still not represented, and bring that number to zero in + the state of the string +- return the total number of actions that need to be taken + +### Task 2: Valid Number There are several approaches to solving this problem: -- trivial: take a pair of numbers, flip a "do we want the smaller or the larger one" flag, - produce the corresponding result, move on to the next pair -- keep this information in an object, feed it numbers one by one or in pairs, let it - update its inner state (or, if it is an immutable object, let it produce a new one with - the inner state updated) -- keep this information in an object, feed it number by number or the whole sequence, - have it work as an iterator that produces numbers for the programming language's - constructs to consume - -Some languages have built-in constructs for dealing with iterators, others can -handle immutable objects easily and efficiently, so the approach depends on +- match the input string against a regular expression +- try to parse the input string using a pre-built parser + +Some languages have built-in constructs for building parsers, others can handle +regular expressions with ease, and some are good at both, so the approach depends on the programming language. ## Running the test suite @@ -56,50 +167,50 @@ the programming language. The `tests/` subdirectory contains a Perl test suite that outputs TAP, so that it can be run using `prove tests` (or, for the more adventurous, `prove -v tests`). -The Python implementation has its own set of static checkers (linters). -Those can be run from the `python/` directory using Tox 4.x - either directly -(`tox run-parallel`) or using [the tox-stages tool][python-tox-stages] -(`tox-stages run`). +### Task 1: Strong Password -### Task 1: Self Spammer +This task takes a string as input, so there are two ways of running the program: -This task does not involve any input data (except for the program source itself), -so the programs are executed without any parameters. +- if the `PWC_FROM_STDIN` environment variable is not set to the exact value `1`, + the program examines the seven strings given as examples, and produces seven words on + its standard output stream, each one on a line by itself. + In other words, the program must output `true\nfalse\nfalse\nfalse\ntrue\ntrue\ntrue\n` exactly. +- if the `PWC_FROM_STDIN` environment variable is set, the program reads a single line of + text from its standard input, treats it as an expression to be examined, and produces + a single word (either "true" or "false") on a line by itself on its standard output stream. -The `PWCTest::Ch286` module in `tests/lib/` defines a `test_self_spammer` function that -runs the specified program, checks whether it output a single line containing a single word, and -then looks for that word in the specified source file (the program itself by default). -Of course, for the Perl implementation there is a bit of a chicken-and-egg problem, since -the test itself must implement the same algorithm to check whether the word that -the program output is actually present as a separate word in the source file. -I played around a bit with the idea of using an external `grep` program to look for -the word, but it turns out that at least GNU grep has some... idionsyncrasies regarding -character sequences like `\<`, `\>`, `'')`, etc, so the output of Perl's `quotemeta` -function was not suitable for feeding to `grep` directly. -Eh, let's hope my solution is correct anyway :) +The `PWCTest::Ch287` module in `tests/lib/` defines a `test_strong_password_default` function that +runs a program with `PWC_FROM_STDIN` unset and expects the exact output, and also +a `test_strong_password` function that runs a series of tests with different sequences, +each time running the program with `PWC_FROM_STDIN` set to 1 and feeding it the sequence. -The `tests/03-python-ch-1.t` test first looks for a suitable Python 3 interpreter. -If the `PYTHON3` environment variable is defined, it is used as the name or path of -the Python 3 interpreter; oterhwise, `python3` is used. -The test tries to run the Python 3 interpreter for a `pass` command; if that fails, -the tests are skipped. +If the implementation in any language should provide more than one method, then +the program should honor the `PWC_METHOD` environment variable. +The value "0" indicates the use of the most natural method for the language, +the value "1" indicates the use of an alternative method, and if there are more than two, +then the values "2", "3", etc, are used to select them. +If `PWC_METHOD` is set to a non-numeric value or to a value that is higher than +the index of the last supported methods, it is ignored and the program proceeds as if +`PWC_METHOD` was set to "0". + +The `tests/01-perl-ch-1.t` test runs these functions on the Perl implementation and +produces TAP output suitable for the `prove` tool. -### Task 2: Order Game +### Task 2: Valid Number -This task takes some input, so there are two ways of running the program: +This task takes a string as input, so there are two ways of running the program: - if the `PWC_FROM_STDIN` environment variable is not set to the exact value `1`, - the program runs the three sequences given as examples, and produces three numbers on + the program examines the seven strings given as examples, and produces seven words on its standard output stream, each one on a line by itself. - In other words, the program must output `1\n0\n2\n` exactly. + In other words, the program must output `true\nfalse\nfalse\nfalse\ntrue\ntrue\ntrue\n` exactly. - if the `PWC_FROM_STDIN` environment variable is set, the program reads a single line of - text from its standard input, treats it as a sequence of decimal integers separated by - one or more whitespace characters, runs the order game on that sequence, and produces - a single number on a line by itself on its standard output stream. + text from its standard input, treats it as an expression to be examined, and produces + a single word (either "true" or "false") on a line by itself on its standard output stream. -The `PWCTest::Ch286` module in `tests/lib/` defines a `test_order_game_default` function that +The `PWCTest::Ch287` module in `tests/lib/` defines a `test_valid_number_default` function that runs a program with `PWC_FROM_STDIN` unset and expects the exact output, and also -a `test_order_game` function that runs a series of tests with different sequences, +a `test_valid_number` function that runs a series of tests with different sequences, each time running the program with `PWC_FROM_STDIN` set to 1 and feeding it the sequence. If the implementation in any language should provide more than one method, then @@ -114,48 +225,53 @@ the index of the last supported methods, it is ignored and the program proceeds The `tests/02-perl-ch-2.t` test runs these functions on the Perl implementation and produces TAP output suitable for the `prove` tool. -The `tests/03-python-ch-2.t` test first looks for a suitable Python 3 interpreter. -If the `PYTHON3` environment variable is defined, it is used as the name or path of -the Python 3 interpreter; oterhwise, `python3` is used. -The test tries to run the Python 3 interpreter for a `pass` command; if that fails, -the tests are skipped. - ## Implementation details -### Task 1: Self Spammer +### Task 1: Strong Password #### Perl -We use the [FindBin core module][perl-findbin] and its `$Bin` and `$Script` variables to -figure out where the program source is. - -#### Python - -We use Python's built-in `__file__` pseudoglobal variable to find the path to our source file. -Then we use `random.choice()` to select a random word directly without bothering with -an index into the words array. - -### Task 2: Order Game +The Perl solution has several important functions: + +- `classify()` - examine a single character passed as an argument and return the name of + its character class ( `lower`, `upper`, `digit`, or `unknown`). + If the `PWC_USE_LOCALE` environment variable is set exactly to the value "1", then + this function will use the current locale settings; otherwise it will only recognize + ASCII Latin uppercase and lowercase letters and ASCII digits. +- `examine_password()` - perform the initial examination of the password string. + Determine its length, the number of character classses not represented in it, and + the number and length of successive runs of the same character. + There are several ways to detect successive runs; a comment in the source code + refers to a regular expression that uses Perl's `/e` modifier to replace a run with + its length as an integer. + This solution processes the string character by character and keeps track of what + the last character was and how many of it we have seen so far. +- `fix_runs()` - count the "replace a single character" actions that must be performed to + break too-long runs of the same character. + At the same time, decrease the number of missing character classes by the same amount. +- `fix_length()` - count the "add a single character" actions that must be performed to + bring the string up to the desired length if it is shorter. + At the same time, decrease the number of missing character classes by the same amount. +- `fix_missing()` - count the "replace a single character" actions that must be performed to + represent all the required character classes in the password string. +- `strong_password()` - invoke the above functions, sum up the number of required actions. + +Note that the `examine_password()` and the `fix_*()` functions return the current state +directly as three scalar variables instead of any kind of structured data. +Of course it would be possible to stash them into a hash or a simple object, but +this way was a bit simpler. + +### Task 2: Valid Number #### Perl -The Perl solution has three major functions: - -- `round_trivial` - run a single round on a list, producing a list with half the number of - elements using the trivial approach: take numbers in pairs, keep a flag, produce - the smaller or the larger one as the flag says, flip it. -- `run_order_game` - run the whole order game on the specified sequence of numbers. - This function currently only uses a single "run a round" implementation, `round_trivial`. - The `PWC_METHOD` environment variable is ignored even if set. -- `parse_stdin` - read a line of numbers from the standard input, break it down into - a list of integers. - -#### Python +The Perl solution has three major elements: -The Python solution defines an `OrderIter` class and an `OrderIterState` enumeration. -The class serves as an iterator, stashing a value and then performing a `min()` or -`max()` operation on the next value fetched from the supplied input. -The `OrderState` enumeration is used to keep track of the stash/yield state. +- `$re_valid_number` - a documented (using the `/x` modifier) regular expression that + determines whether a string represents a valid number or not +- `valid_number` - a function that returns either the string "true" or the string "false" + depending on whether the argument represents a valid number +- `parse_stdin` - read a line from the standard input, return it as a string to be examined ## Contact @@ -164,9 +280,7 @@ They are developed in [the common PWC-club GitHub repository][github]. This documentation is hosted at [Ringlet][ringlet-home]. [roam]: mailto:roam@ringlet.net "Peter Pentchev" -[github]: https://github.com/manwar/perlweeklychallenge-club/tree/master/challenge-286/ppentchev "These solutions at GitHub" -[ringlet-home]: https://devel.ringlet.net/misc/perlweeklychallenge-club/286/ "This documentation at Ringlet" +[github]: https://github.com/manwar/perlweeklychallenge-club/tree/master/challenge-287/ppentchev "These solutions at GitHub" +[ringlet-home]: https://devel.ringlet.net/misc/perlweeklychallenge-club/287/ "This documentation at Ringlet" -[perl-findbin]: https://perldoc.perl.org/FindBin "The FindBin Perl core module" -[pwc-286]: https://theweeklychallenge.org/blog/perl-weekly-challenge-286/ "The 286th Perl & Raku Weekly Challenge" -[python-tox-stages]: https://devel.ringlet.net/devel/test-stages "Run Tox tests in groups" +[pwc-287]: https://theweeklychallenge.org/blog/perl-weekly-challenge-287/ "The 287th Perl & Raku Weekly Challenge" diff --git a/challenge-287/ppentchev/mkdocs.yml b/challenge-287/ppentchev/mkdocs.yml new file mode 100644 index 0000000000..65bda23bda --- /dev/null +++ b/challenge-287/ppentchev/mkdocs.yml @@ -0,0 +1,48 @@ +# SPDX-FileCopyrightText: Peter Pentchev <roam@ringlet.net> +# SPDX-License-Identifier: BSD-2-Clause + +theme: + name: material + features: + - navigation.instant + - navigation.tracking + - toc.integrate + - toc.follow + - content.code.copy + palette: + - media: "(prefers-color-scheme: light)" + scheme: default + toggle: + icon: material/weather-sunny + name: Switch to dark mode + - media: "(prefers-color-scheme: dark)" + scheme: slate + toggle: + icon: material/weather-night + name: Switch to light mode +site_name: pwc-287-ppentchev +repo_url: https://github.com/manwar/perlweeklychallenge-club/tree/master/challenge-287/ppentchev +repo_name: perlweeklychallenge-club +site_author: ppentchev +site_url: https://devel.ringlet.net/misc/perlweeklychallenge-club/287/ +site_dir: site/docs +nav: + - 'index.md' +markdown_extensions: + - toc: + - pymdownx.highlight: + anchor_linenums: true + - pymdownx.inlinehilite: + - pymdownx.superfences: +plugins: + - mkdocstrings: + default_handler: python + handlers: + python: + paths: [python/src] + options: + heading_level: 3 + show_root_heading: true + - search +# watch: +# - 'src/parse_stages' diff --git a/challenge-287/ppentchev/perl/scripts/ch-1.pl b/challenge-287/ppentchev/perl/scripts/ch-1.pl new file mode 100755 index 0000000000..925cbf5ba2 --- /dev/null +++ b/challenge-287/ppentchev/perl/scripts/ch-1.pl @@ -0,0 +1,161 @@ +#!/usr/bin/perl +# SPDX-FileCopyrightText: Peter Pentchev <roam@ringlet.net> +# SPDX-License-Identifier: BSD-2-Clause + +use v5.16; +use strict; +use warnings; + +use locale qw(:ctype); +use utf8; + +use List::Util qw(reduce); + +use constant DESIRED_LENGTH => 6; +use constant PWC_QUIET => ($ENV{PWC_QUIET} // '') eq 1; +use constant PWC_USE_LOCALE => ($ENV{PWC_USE_LOCALE} // '') eq 1; + +my @TEST_STRINGS = ( + 'a', + 'aB2', + 'PaaSW0rd', + 'PaaaSW0rd', + 'aaaaa', +); + +sub diag($) { + say STDERR $_[0] unless PWC_QUIET; +} + +sub classify($) +{ + my ($char) = @_; + + if (PWC_USE_LOCALE) { + return 'lower' if $char =~ /[[:lower:]]/; + return 'upper' if $char =~ /[[:upper:]]/; + return 'digit' if $char =~ /[[:digit:]]/; + return 'unknown'; + } + + return 'lower' if $char =~ /[a-z]/; + return 'upper' if $char =~ /[A-Z]/; + return 'digit' if $char =~ /[0-9]/; + return 'unknown'; +} + +sub examine_password($) +{ + my ($password) = @_; + + my %seen = map { $_ eq 'unknown' ? () : ($_, 1) } map { classify $_ } split //, $password; + + # This part can also be done with something like: + # s/((.)\2*)/length($1)." "/eg + # ...and then parsing the integers, but I don't think it's worth it. + my $runs_state = reduce { + my ($runs, $last, $count) = @{$a}; + if ($b eq $last) { + [$runs, $last, $count + 1] + } elsif ($count >= 3) { + [[@{$runs}, $count], $b, 1] + } else { + [$runs, $b, 1] + } + } ([[], ' ', 0], split //, $password); + my ($runs, $last, $count) = @{$runs_state}; + if ($count >= 3) { + push @{$runs}, $count; + } + + (length $password, 3 - scalar keys %seen, $runs) +} + +sub diag_state($ $ $ $ $) +{ + my ($tag, $actions, $length, $missing, $runs) = @_; + + diag "state $tag: actions $actions, length $length, missing $missing, runs @{$runs}"; +} + +sub fix_runs($ $ $) +{ + my ($length, $missing, $runs) = @_; + my $actions = 0; + + for my $run (@{$runs}) { + my $delta = int($run / 3); + $actions += $delta; + if ($missing >= $delta) { + $missing -= $delta; + } else { + $missing = 0; + } + } + + ($actions, $length, $missing, []) +} + +sub fix_length($ $ $) +{ + my ($length, $missing, $runs) = @_; + + if ($length >= DESIRED_LENGTH) { + |