Merge pull request #10643 from atschneid/master

ATSchneid PWC 282 solutions

6 files changed, 319 insertions, 85 deletions

diff --git a/challenge-282/atschneid/README.md b/challenge-282/atschneid/README.md
index 88ea651719..7344132b12 100644
--- a/challenge-282/atschneid/README.md
+++ b/challenge-282/atschneid/README.md
@@ -1,137 +1,240 @@
-# Chess Moves
+# Exact Triples and Modulation
 
-**Challenge 281 solutions by Andrew Schneider**
+**Challenge 282 solutions by Andrew Schneider**
 
-[PWC 281](https://theweeklychallenge.org/blog/perl-weekly-challenge-281/)
+[PWC 282](https://theweeklychallenge.org/blog/perl-weekly-challenge-282/)
 
-Two related challenges this week, both involving the chess board. The first one has a trick regarding odds and evens. The second one I solve via Breadth First Search
+Two challenges both related to repetitions this week. I solved them in two languages each with a very different kind of solution.
 
-## TASK 1: Check Color
+## Task 1: Good Integer
 
-> Task 1: Check Color</br>
+> Task 1: Good Integer</br>
 > Submitted by: Mohammad Sajid Anwar</br>
-> You are given coordinates, a string that represents the coordinates of a square of the chessboard as shown below:</br>
+> You are given a positive integer, $int, having 3 or more digits.</br>
 > </br>
-> Write a script to return true if the square is light, and false if the square is dark.</br>
+> Write a script to return the Good Integer in the given integer or -1 if none found.</br>
+> </br>
+> A good integer is exactly three consecutive matching digits.</br>
 > </br>
 > Example 1</br>
-> Input: $coordinates = "d3"</br>
-> Output: true</br>
+> Input: $int = 12344456</br>
+> Output: "444"</br>
 > </br>
 > Example 2</br>
-> Input: $coordinates = "g5"</br>
-> Output: false</br>
+> Input: $int = 1233334</br>
+> Output: -1</br>
 > </br>
 > Example 3</br>
-> Input: $coordinates = "e6"</br>
-> Output: true
+> Input: $int = 10020003</br>
+> Output: "000"</br>
+
+Pretty clear description, but what are we to do if there are more than 1 Good Integers in a number? I could have returned the first and been done, but it really felt like we should return them all, so that's how I did it.
+
+### Perl
+
+With Perl, for both challenges this week I went full in with regexes, because, of course, Perl! 
+
+```perl
+sub good_integer( $int ) {
+    my @val = $int =~ /((\d)(?!\g-1)|(^))((\d)\g-1{2})(?!\g-1)/g;
+    if (@val) {
+        my @retval;
+        my $idx = 3;
+        while ($idx <= $#val) {
+            push @retval, $val[$idx];
+            $idx += 5;
+        }
+        return @retval;
+    }
+    return (-1);
+}
+```
+
+Ok, that looks bad. There are two parts here: finding the GIs and pushing the GI values into a list to return.
+
+For finding the GIs it's regex
+
+```perl
+    my @val = $int =~ /((\d)(?!\g-1)|(^))((\d)\g-1{2})(?!\g-1)/g;
+```
 
-The trick to this one is to realize that if you convert the letters to numbers, in a sensible way such as 'a' -> 1, 'b' -> 2, etc., you can figure out the color of the space by summing the index, and checking if it is odd or even. Which one you want for the black or white square depends on your conversion.
+Which can be split into 2 logical pieces:
+
+```((\d)(?!\g-1)|(^))``` matches either: a decimal which is followed by a different decimal value (which is checked by a non-consuming, non-capturing lookahead) or the beginning of the string. The purpose of this piece is to make sure we don't match the end of a sequence of the same decimal values that is longer than 3.
+
+I capture the start of string anchor because later, when I want to find the GIs I want them to be at predictable indices in the match array.
+
+```((\d)\g-1{2})(?!\g-1)``` this will match a decimal followed by 2 more of the same decimal value, followed by anything except the same value (as a non-consuming, non-capturing lookahead). This makes sure that we don't match the start of a sequence of the same decimal values that is longer than 3. Combined with the first part of the regex, this is the part that will capture the GI (and the decimal value).
+
+I never really did much with lookaheads before. I was aware they existed but I never had a good use case for them. They turned out to be pretty intuitive. Originally I tried to use a lookbehind for the first part of the regex, but I couldn't get that to work (and suspect it was doomed anyway, without some acrobatics). Covering the first part with a lookahead wasn't too bad once I had the idea.
+
+This whole match is global so it should capture GIs, plus some other stuff, as many times as they are found.
+
+Now on to the second part of the function. This checks if the regex matched, and if so it extracts the captures that cover the GIs.
+
+```perl
+    if (@val) {
+        my @retval;
+        my $idx = 3;
+        while ($idx <= $#val) {
+            push @retval, $val[$idx];
+            $idx += 5;
+        }
+        return @retval;
+    }
+    return (-1);
+```
+
+Because of all the captures we use as references within the regex, we end up with values in our matching list besides just the GIs. If there is/are match(es) the first GI is in the match list at index 3. For each GI match we add 5 values to the match list. I figured out these values by counting! So if there is a match we push the value at index 3, then step forward at step size 5 pushing the value we land on until we exhaust the match list. This gives us our matches.
+
+If we didn't find any GIs then we directly return a list of `(-1)`
+
+*UPDATE:* At press time I peeked at some other solutions and realized a much simpler way to handle ... most of this. For the regex we could capture all runs of consecutive same values. Then `grep` the results for array values of length exactly 3. Of course!
 
 ```perl
-sub check_square( $key ) {
-    return sum( map { ord($_) } split '', $key ) % 2;
+sub good_integer_v2( $int ) {
+    my @val = grep { 3 == length $_ } $int =~ /((\d)\g-1*)/g;
+    if (@val) {
+        return @val;
+    }
+    return (-1);
 }
 ```
 
-Conveniently the character '1' and the character 'a' both are represented by an odd number, so we don't need to do any conversion besides converting the characters into their ascii using `ord`.
+Very nearly a one-liner there, if not for the `-1` return ...
 
-We pass this function a space index, like 'a1', as a string. We split the string into its characters, convert each to its ascii, sum up the values, and modulo it by 2. 
+### Rust
 
-This function works on the example input. It would also output a value for any two character string, or any string at all for that matter! Is this a feature or a bug? Not sure! but we could always add in some length and value checks to error on bad input.
+For Rust, for both of my solutions, I didn't use regex at all, instead I iterated directly over the characters of a string. For one, it is annoying to impossible to use external crates in Rust without going through a whole `cargo` build, which I try to avoid where I can, and regexes in Rust come via an external crate. But also, for these problems, looking at each character doesn't lead to an obviously less complicated solution. Although certainly more verbose.
+
+```rust
+fn good_integer(input: &u64) -> Vec<String> {
+    let input_string = input.to_string();
+    if input_string.len() < 3 {
+        return ["-1".to_string()].to_vec();
+    }
+
+    let mut vec = Vec::new();
+    let mut count = 1;
+    let mut chars = input_string.chars();
+    let mut last = chars.next().unwrap();
+    for current in chars {
+        if last == current {
+            count += 1;
+        } else {
+            if count == 3 {
+                vec.push(format!("{}{}{}", last, last, last));
+            }
+            count = 1;
+        }
+        last = current;
+    }
+    // catch possible trailing valid ints
+    if count == 3 {
+        vec.push(format!("{}{}{}", last, last, last));
+    }
+
+    if vec.len() > 0 {
+        return vec;
+    }
+    ["-1".to_string()].to_vec()
+}
+```
+
+To start we convert the integer input to a string. We need to make sure that the string is at least length 1, but while we're at it we may as well check if it's less than length 3 since in either case the result will be the same: no GIs. I think there is a neater solultion for handling an empty string than what I have here, more on that below.
+
+Next I make an empty vector for storing our results and initialize a counter to 1. Then convert our string to an iterable of chars, and get the first. Currently I assume this will succeed because I have already checked the length, but instead of checking the length I could check for an error getting the first char and interpret this to mean an empty string. Future work!
+
+Now the loop. While the current character matches the previous we increment the counter. Once we find a mismatch we check if the count is 3. If yes we can add a string of 3 of the previous character to the results vector. Then we reset the counter.
+
+We have to repeat the last bit after the loop one last time in case of a GI that falls at the end of the int.
+
+Finally, if we have anything in our results vec we return it, otherwise we return a vec with "-1". Easy!
 
-## Task 2: Knight's Move
 
-> Task 2: Knight’s Move</br>
-> Submitted by: Peter Campbell Smith</br>
-> A Knight in chess can move from its current position to any square two rows or columns plus one column or row away. So in the diagram below, if it starts a S, it can move to any of the squares marked E.</br>
+## Task 2: Changing Keys
+
+> Task 2: Changing Keys</br>
+> Submitted by: Mohammad Sajid Anwar</br>
+> You are given an alphabetic string, $str, as typed by user.</br>
 > </br>
-> Write a script which takes a starting position and an ending position and calculates the least number of moves required.</br>
+> Write a script to find the number of times user had to change the key to type the given string. Changing key is defined as using a key different from the last used key. The shift and caps lock keys won’t be counted.</br>
 > </br>
 > Example 1</br>
-> Input: $start = 'g2', $end = 'a8'</br>
-> Ouput: 4</br>
+> Input: $str = 'pPeERrLl'</br>
+> Ouput: 3</br>
 > </br>
-> g2 -> e3 -> d5 -> c7 -> a8</br>
+> p -> P : 0 key change</br>
+> P -> e : 1 key change</br>
+> e -> E : 0 key change</br>
+> E -> R : 1 key change</br>
+> R -> r : 0 key change</br>
+> r -> L : 1 key change</br>
+> L -> l : 0 key change</br>
 > </br>
 > Example 2</br>
-> Input: $start = 'g2', $end = 'h2'</br>
-> Ouput: 3</br>
+> Input: $str = 'rRr'</br>
+> Ouput: 0</br>
 > </br>
-> g2 -> e3 -> f1 -> h2
+> Example 3</br>
+> Input: $str = 'GoO'</br>
+> Ouput: 1</br>
+
+Similar to the previous task, we are concerned with repetitions here. This time ignoring them.
 
-The high level idea here is: to get to the start space takes zero moves. To get to any space takes 1 additional move, and any space from there is 1+1 moves, and so on.
+### Perl
 
-So we mark the start space with value 0, then find all spaces we can reach from this one, mark them with value 1, then repeat the same for each space, and repeat, and repeat. If the space has been visited already, we skip it, since we have already found the shortest number of moves to get there. And if we land on the end space we return its value.
+I iterated on my regex solution to this one. 
 
-To store the list of spaces to inspect I use a FIFO queue to ensure the search is breadth-first, which makes the algorithm more efficient -- we don't have to check if the value is the minimum and we can reliably inspect each space only once. The BFS solution for this problem is $\mathcal O (8 \times 8)$, that is, it's linear in the board size.
+In an early version I did 2 steps, first substituting all case insensitive consecutive matches to one char, then finding the length of the resulting string. The answer is this length minus 1, which is the number of changes
 
 ```perl
-sub knight_path( $start_key, $end_key ){
-    my @queue = ($start_key);
-    my %board;
-    $board{ $start_key } = 0;
-
-    while ( $#queue >= 0 ) {
-	my $current = shift @queue;
-	if ($current eq $end_key) {
-	    return $board{ $current };
-	}
-	for ( get_moves( $current ) ) {
-	    if ( !exists $board{ $_ } ) {
-		push @queue, $_;
-		$board{ $_ } = $board{ $current } + 1;
-	    }
-	}
-    }
+sub count_change_v1( $str ) {
+    $str =~ s/(.)\g1*/$1/gi;
+    return -1 + length $str;
 }
 ```
 
-For the queue I use a normal list and access elements using `shift` and add elements using `push`. For the board I use a hashmap with the string index key as the key, if the key is in the map then we know we have inspected the space already.
+I liked this solution, but it felt like it was one line too long. 
 
-The trickiest part here was generating the list of possible next moves from each space
+Instead of substituting I could directly capture a char and consume all following identical chars (case insensitive of course), then count the number of captures.
 
 ```perl
-sub get_moves( $key ) {
-    my @moves = (
-	[2, 1], [1, 2], [-2, 1], [1, -2],
-	[2, -1], [-1, 2], [-2, -1], [-1, -2]
-	);
-
-    my @idx = split '', $key;
-    my @next_moves = ();
-    for (@moves) {
-	my @candidate = (
-	    ord($idx[0]) + $_->[0],
-	    ord($idx[1]) + $_->[1]
-	    );
-	if (
-	    $candidate[0] >= ord('a') and
-	    $candidate[0] <= ord('h') and
-	    $candidate[1] >= ord('1') and
-	    $candidate[1] <= ord('8')
-	    ) {
-	    push @next_moves, join '', map { chr( $_ ) } @candidate;
-	}
-    }
-    return @next_moves;
+sub count_change_v2( $str ) {
+    return scalar ( () = $str =~ /(.)\g1*/gi ) - 1;
 }
 ```
 
-The knight can move in a 1,2 L shape from its current location. For each of the 8 possibilities, we return a list of only the legal moves that land within the board dimensions.
+The trickiest bit here was getting the perlism exactly right to return the count.
 
-That's about that. The Perl solution is pretty speedy.
+### Rust
 
-## Others
+My Rust solution turned out much like a stripped down version of my solution for Task 1
 
-I also wrote solutions in Julia and Racket this week. Task 1 was easy in each. For task 2, in Julia I used a 8 by 8 matrix for the board, becuaes it felt intuitive, but addressing each square seemed more complicated than it should have been. In Julia you can do something like `*(1, 2)` to return the values `1` and `2`, but you can't seem to do this with a variable. Like `v = (1, 2); *v` throws an error. Also the Julia version takes longer (anecdotally) to run than the Perl version. I'm sure there are some easy changes that would speed things up.
+```rust
+fn count_change(s: &str) -> u32 {
+    if s.len() < 2 {
+        return 0;
+    }
 
-As for Racket, well, ... it's done and it gives the correct answer. I used a library to get a queue data structure. For stacks, oh you want stacks? Racket can do stacks! But queues are a problem. I probably should have implemented my own using structs. Or, as i did in Julia, just use an array with a start index to simulate a queue. 
+    let mut count = 0;
+    let binding = s.to_lowercase();
+    let mut chars = binding.as_str().chars();
+    let mut last = chars.next().unwrap();
+    for current in chars {
+        if last != current {
+            count += 1;
+        }
+        last = current;
+    }
+    count
+}
+```
 
-## Conclusion
+Again we check the length of the string, we really care if it is less than 1 but we might as well check if it is less than length 2 because the result will be the same. Then we iterate over the chars of the string counting how many times the char changes. Easy!
 
-That's it for this week. I did these challenges while on vacation. They helped to keep my brain from otherwise atrophying.
+## Conclusion
 
-Oh, also, thanks to Mohammad and the Perl Weekly Challenge committee for acknowledging me! Why do I do this? Surely not for the fame and notoriety, but those things help! Ha!
+That's it for this week. Two challenges, two languages, two different ways to solve the problems! Which one did you like better? The character iterating solutions were easy to write and very direct for the problems, but doing some moderately complicated stuff with regexes makes me feel like I'm operating on a higher plane. I'm torn!
 
-See you next week!
+Thanks for reading. See you next week!
diff --git a/challenge-282/atschneid/blog.txt b/challenge-282/atschneid/blog.txt
new file mode 100644
index 0000000000..7d555608e7
--- /dev/null
+++ b/challenge-282/atschneid/blog.txt
@@ -0,0 +1 @@
+https://github.com/atschneid/perlweeklychallenge-club/blob/master/challenge-282/atschneid/README.md
diff --git a/challenge-282/atschneid/perl/ch-1.pl b/challenge-282/atschneid/perl/ch-1.pl
new file mode 100644
index 0000000000..9897f63c53
--- /dev/null
+++ b/challenge-282/atschneid/perl/ch-1.pl
@@ -0,0 +1,40 @@
+use strict;
+use warnings;
+
+use v5.38;
+
+sub good_integer( $int ) {
+    my @val = $int =~ /((\d)(?!\g-1)|(^))((\d)\g-1{2})(?!\g-1)/g;
+    if (@val) {
+	my @retval;
+	my $idx = 3;
+	while ($idx <= $#val) {
+	    push @retval, $val[$idx];
+	    $idx += 5;
+	}
+	return @retval;
+    }
+    return (-1);
+}
+
+sub good_integer_v2( $int ) {
+    my @val = grep { 3 == length $_ } $int =~ /((\d)\g-1*)/g;
+    if (@val) {
+	return @val;
+    }
+    return (-1);
+}
+
+my @inputs = (
+    12333,
+    12333455557,
+    1233345557,
+    1233333,
+    333,
+    3331,
+    3333
+    );
+for (@inputs) {
+    say $_ . ' => ' . join ', ', good_integer( $_ );
+    say $_ . ' => ' . join ', ', good_integer_v2( $_ );
+}
diff --git a/challenge-282/atschneid/perl/ch-2.pl b/challenge-282/atschneid/perl/ch-2.pl
new file mode 100644
index 0000000000..9601f40a5d
--- /dev/null
+++ b/challenge-282/atschneid/perl/ch-2.pl
@@ -0,0 +1,26 @@
+use strict;
+use warnings;
+
+use v5.38;
+
+sub count_change_v1( $str ) {
+    $str =~ s/(.)\g1*/$1/gi;
+    return -1 + length $str;
+}
+
+sub count_change_v2( $str ) {
+    return scalar ( () = $str =~ /(.)\g1*/gi ) - 1;
+}
+
+my @inputs = (
+    'pPeERrLl',
+    'rRr',
+    'GoO',
+    'gooooo',
+    'goOOood'
+    );
+for (@inputs) {
+    say $_ . ' =v1=> ' . count_change_v1( $_ );
+    say $_ . ' =v2=> ' . count_change_v2( $_ );
+    say '****';
+}
diff --git a/challenge-282/atschneid/rust/ch-1.rs b/challenge-282/atschneid/rust/ch-1.rs
new file mode 100644
index 0000000000..6427b20519
--- /dev/null
+++ b/challenge-282/atschneid/rust/ch-1.rs
@@ -0,0 +1,39 @@
+fn good_integer(input: &u64) -> Vec<String> {
+    let input_string = input.to_string();
+    if input_string.len() < 3 {
+        return ["-1".to_string()].to_vec();
+    }
+
+    let mut vec = Vec::new();
+    let mut count = 1;
+    let mut chars = input_string.chars();
+    let mut last = chars.next().unwrap();
+    for current in chars {
+        if last == current {
+            count += 1;
+        } else {
+            if count == 3 {
+                vec.push(format!("{}{}{}", last, last, last));
+            }
+            count = 1;
+        }
+        last = current;
+    }
+    // catch possible trailing valid ints
+    if count == 3 {
+        vec.push(format!("{}{}{}", last, last, last));
+    }
+
+    if vec.len() > 0 {
+        return vec;
+    }
+    ["-1".to_string()].to_vec()
+}
+
+fn main() {
+    let inputs = [12333, 12333455557, 1233345557, 1233333, 333, 3331, 3333];
+    for input in inputs {
+        let goodness = good_integer(&input);
+        println!("{} => {:?}", input, goodness);
+    }
+}
diff --git a/challenge-282/atschneid/rust/ch-2.rs b/challenge-282/atschneid/rust/ch-2.rs
new file mode 100644
index 0000000000..9a4146b56d
--- /dev/null
+++ b/challenge-282/atschneid/rust/ch-2.rs
@@ -0,0 +1,25 @@
+fn count_change(s: &str) -> u32 {
+    if s.len() < 2 {
+        return 0;
+    }
+
+    let mut count = 0;
+    let binding = s.to_lowercase();
+    let mut chars = binding.as_str().chars();
+    let mut last = chars.next().unwrap();
+    for current in chars {
+        if last != current {
+            count += 1;
+        }
+        last = current;
+    }
+    count
+}
+
+fn main() {
+    let inputs = ["pPeERrLl", "rRr", "GoO", "gooooo", "goOOood"];
+    for str in inputs {
+        let changes = count_change(&str);
+        println!("{} => {}", str, changes);
+    }
+}