diff options
| -rw-r--r-- | challenge-288/sgreen/README.md | 4 | ||||
| -rwxr-xr-x | challenge-288/sgreen/perl/ch-1.pl | 33 | ||||
| -rwxr-xr-x | challenge-288/sgreen/perl/ch-2.pl | 85 | ||||
| -rwxr-xr-x | challenge-288/sgreen/python/ch-1.py | 31 | ||||
| -rwxr-xr-x | challenge-288/sgreen/python/ch-2.py | 82 | ||||
| -rwxr-xr-x | challenge-288/sgreen/python/test.py | 43 |
6 files changed, 275 insertions, 3 deletions
diff --git a/challenge-288/sgreen/README.md b/challenge-288/sgreen/README.md index edb0f8425e..f83d2827dc 100644 --- a/challenge-288/sgreen/README.md +++ b/challenge-288/sgreen/README.md @@ -1,3 +1 @@ -# The Weekly Challenge 287 - -Blog: [Good things](https://dev.to/simongreennet/good-things-1e3a) +# The Weekly Challenge 288 diff --git a/challenge-288/sgreen/perl/ch-1.pl b/challenge-288/sgreen/perl/ch-1.pl new file mode 100755 index 0000000000..d33c8d56a6 --- /dev/null +++ b/challenge-288/sgreen/perl/ch-1.pl @@ -0,0 +1,33 @@ +#!/usr/bin/env perl + +use strict; +use warnings; +use feature 'say'; +use experimental 'signatures'; + +sub closest_palindrome($str) { + # Negative integers always have a closest palindrome of 0 + if ( $str < 0 ) { + say 0; + return; + } + + my $offset = 1; + while (1) { + my $check = $str - $offset; + if ( $check == reverse($check) ) { + say $check; + return; + } + + $check = $str + $offset; + if ( $check == reverse($check) ) { + say $check; + return; + } + + $offset++; + } +} + +closest_palindrome( $ARGV[0] );
\ No newline at end of file diff --git a/challenge-288/sgreen/perl/ch-2.pl b/challenge-288/sgreen/perl/ch-2.pl new file mode 100755 index 0000000000..ccba048493 --- /dev/null +++ b/challenge-288/sgreen/perl/ch-2.pl @@ -0,0 +1,85 @@ +#!/usr/bin/env perl + +use strict; +use warnings; +use feature 'say'; +use experimental 'signatures'; + +use JSON 'decode_json'; + +sub find_block($matrix, $seen, $row, $col) { + my $cols = scalar(@{$matrix->[0]}); + + # The character that we need to match + my $char = $matrix->[$row][$col]; + + # The directions we can move: Up, down, left, right + my @directions = ([-1, 0], [1, 0], [0, -1], [0, 1]); + + # Mark the we have seen the starting cell + $seen->[$row][$col] = 1; + + # Add the starting cell to the stack + my @stack = ([$row, $col]); + my $count = 1; + + while ($#stack > -1) { + # Whether we found a move from the last value in the stack + my $new_pos = 0; + + foreach my $move (@directions) { + # Move in each direction + my $new_row = $stack[-1][0] + $move->[0]; + my $new_col = $stack[-1][1] + $move->[1]; + + # Check that the move is still in bounds of the matrix, we haven't + # already use that position, and it is the correct character + if ($new_row < 0 or $new_row > $#$matrix or $new_col < 0 or $new_col >= $cols or $seen->[$new_row][$new_col] or $matrix->[$new_row][$new_col] ne $char) { + next; + } + + # It is, add it to the stack, and increment the count + push @stack, [$new_row, $new_col]; + $seen->[$new_row][$new_col] = 1; + $new_pos = 1; + $count++; + } + + if (! $new_pos) { + # We didn't find a new move, remove it from that stack. + pop(@stack); + } + } + + return $count; +} + +sub contiguous_block($matrix) { + my $cols = scalar(@{$matrix->[0]}); + my $max_block = 0; + + # Seed the seen table + my $seen = []; + for (0 .. $#$matrix) { + push @$seen, [ (0) x $cols ]; + } + + foreach my $row (0 .. $#$matrix) { + foreach my $col (0 .. $cols - 1) { + if ($seen->[$row][$col]) { + # The item at this position has already been used + next; + } + + # Find how many items in this block. If greater than max_block, replace it + my $count = find_block($matrix, $seen, $row, $col); + if ($count > $max_block) { + $max_block = $count; + } + } + } + + say $max_block; +} + +contiguous_block( decode_json( $ARGV[0] ) );
\ No newline at end of file diff --git a/challenge-288/sgreen/python/ch-1.py b/challenge-288/sgreen/python/ch-1.py new file mode 100755 index 0000000000..eff97cae4b --- /dev/null +++ b/challenge-288/sgreen/python/ch-1.py @@ -0,0 +1,31 @@ +#!/usr/bin/env python3 + +import sys + + +def closest_palindrome(i: int) -> int: + # Negative integers always have a closest palindrome of 0 + if i < 0: + return 0 + + offset = 1 + while True: + check = i - offset + if str(check) == str(check)[::-1]: + return check + + check = i + offset + if str(check) == str(check)[::-1]: + return check + + offset += 1 + + +def main(): + # Convert input into integers + result = closest_palindrome(int(sys.argv[1])) + print(result) + + +if __name__ == '__main__': + main() diff --git a/challenge-288/sgreen/python/ch-2.py b/challenge-288/sgreen/python/ch-2.py new file mode 100755 index 0000000000..631498fb3f --- /dev/null +++ b/challenge-288/sgreen/python/ch-2.py @@ -0,0 +1,82 @@ +#!/usr/bin/env python3 + +import json +import sys + + +def find_block(matrix, seen, row, col): + rows = len(matrix) + cols = len(matrix[0]) + + # The character that we need to match + char = matrix[row][col] + + # The directions we can move: Up, down, left, right + directions = [[-1, 0], [1, 0], [0, -1], [0, 1]] + + # Mark the we have seen the starting cell + seen[row][col] = True + + # Add the starting cell to the stack + stack = [[row, col]] + count = 1 + + while stack: + # Whether we found a move from the last value in the stack + new_pos = False + + for move in directions: + # Move in each direction + new_row = stack[-1][0] + move[0] + new_col = stack[-1][1] + move[1] + + # Check that the move is still in bounds of the matrix, we haven't + # already use that position, and it is the correct character + if new_row < 0 or new_row >= rows or new_col < 0 or new_col >= cols or seen[new_row][new_col] or matrix[new_row][new_col] != char: + continue + + # It is, add it to the stack, and increment the count + stack.append([new_row, new_col]) + seen[new_row][new_col] = True + new_pos = True + count += 1 + + if not new_pos: + # We didn't find a new move, remove it from that stack. + stack.pop() + + return count + + +def contiguous_block(matrix: list) -> int: + rows = len(matrix) + cols = len(matrix[0]) + max_block = 0 + + # Seed the seen table + seen = [] + for i in range(rows): + seen.append([0] * cols) + + for row in range(rows): + for col in range(cols): + if seen[row][col]: + # The item at this position has already been used + continue + + # Find how many items in this block. If greater than max_block, replace it + count = find_block(matrix, seen, row, col) + if count > max_block: + max_block = count + + return max_block + + +def main(): + matrix = json.loads(sys.argv[1]) + result = contiguous_block(matrix) + print(result) + + +if __name__ == '__main__': + main() diff --git a/challenge-288/sgreen/python/test.py b/challenge-288/sgreen/python/test.py new file mode 100755 index 0000000000..51af278fbe --- /dev/null +++ b/challenge-288/sgreen/python/test.py @@ -0,0 +1,43 @@ +#!/usr/bin/env python3 + +import unittest +ch_1 = __import__('ch-1') +ch_2 = __import__('ch-2') + + +class TestClass(unittest.TestCase): + def test_ch_1(self): + self.assertEqual(ch_1.closest_palindrome(123), 121) + self.assertEqual(ch_1.closest_palindrome(2), 1) + self.assertEqual(ch_1.closest_palindrome(1400), 1441) + self.assertEqual(ch_1.closest_palindrome(1001), 999) + + def test_ch_2(self): + matrix_1 = [ + ['x', 'x', 'x', 'x', 'o'], + ['x', 'o', 'o', 'o', 'o'], + ['x', 'o', 'o', 'o', 'o'], + ['x', 'x', 'x', 'o', 'o'], + ] + + matrix_2 = [ + ['x', 'x', 'x', 'x', 'x'], + ['x', 'o', 'o', 'o', 'o'], + ['x', 'x', 'x', 'x', 'o'], + ['x', 'o', 'o', 'o', 'o'], + ] + + matrix_3 = [ + ['x', 'x', 'x', 'o', 'o'], + ['o', 'o', 'o', 'x', 'x'], + ['o', 'x', 'x', 'o', 'o'], + ['o', 'o', 'o', 'x', 'x'], + ] + + self.assertEqual(ch_2.contiguous_block(matrix_1), 11) + self.assertEqual(ch_2.contiguous_block(matrix_2), 11) + self.assertEqual(ch_2.contiguous_block(matrix_3), 7) + + +if __name__ == '__main__': + unittest.main() |