diff options
Diffstat (limited to 'challenge-211')
72 files changed, 2939 insertions, 60 deletions
diff --git a/challenge-211/arne-sommer/blog.txt b/challenge-211/arne-sommer/blog.txt new file mode 100644 index 0000000000..3fb70a3139 --- /dev/null +++ b/challenge-211/arne-sommer/blog.txt @@ -0,0 +1 @@ +https://raku-musings.com/same-toeplitz.html diff --git a/challenge-211/arne-sommer/raku/ch-1.raku b/challenge-211/arne-sommer/raku/ch-1.raku new file mode 100755 index 0000000000..53e3a53d69 --- /dev/null +++ b/challenge-211/arne-sommer/raku/ch-1.raku @@ -0,0 +1,43 @@ +#! /usr/bin/env raku + +unit sub MAIN (Str $matrix = "4 3 2 1 | 5 4 3 2 | 6 5 4 3", :v(:$verbose)); + +my @matrix = $matrix.split("|")>>.words>>.Array; +my @size = @matrix>>.elems; + +die "Must have at least 2 rows" unless @size.elems >= 2; +die "The rows must have the same size" unless [==] @size; + +while @matrix.elems +{ + @matrix.shift if @matrix[0].elems == 0; + + last unless @matrix.elems; + + my $row = 0; + my $col = @matrix[$row].end; + + my $value = @matrix[$row].pop; + + say ": Row:0 { @matrix.raku } -> $value (last value removed from row)" if $verbose; + + loop + { + $row++; + $col++; + last unless defined @matrix[$row]; + last unless defined @matrix[$row][$col]; + + my $new = @matrix[$row].pop; + + say ": Row:$row { @matrix.raku } -> $new (last value removed from row)" if $verbose; + + unless $value eq $new + { + say 'false'; + exit; + } + } +} + +say 'true'; diff --git a/challenge-211/arne-sommer/raku/ch-2.raku b/challenge-211/arne-sommer/raku/ch-2.raku new file mode 100755 index 0000000000..f404108103 --- /dev/null +++ b/challenge-211/arne-sommer/raku/ch-2.raku @@ -0,0 +1,28 @@ +#! /usr/bin/env raku + +unit sub MAIN (*@int where @int.elems > 0 && @int.all ~~ UInt && @int.all > 0, :v(:$verbose)); + +for @int.permutations.unique -> @candidate +{ + say ": Candidate: @candidate[]" if $verbose; + + my @right = @candidate.clone; + my @left; + + while @right.elems > 1 + { + @left.push: @right.shift; + my $left-avg = @left.sum / @left.elems; + my $right-avg = @right.sum / @right.elems; + + say ": - Comparing @left[] (avg: $left-avg) <=> @right[] (avg: $right-avg)" if $verbose; + + if $left-avg == $right-avg + { + say 'true'; + exit; + } + } +} + +say 'false'; diff --git a/challenge-211/arne-sommer/raku/split-same-average b/challenge-211/arne-sommer/raku/split-same-average new file mode 100755 index 0000000000..f404108103 --- /dev/null +++ b/challenge-211/arne-sommer/raku/split-same-average @@ -0,0 +1,28 @@ +#! /usr/bin/env raku + +unit sub MAIN (*@int where @int.elems > 0 && @int.all ~~ UInt && @int.all > 0, :v(:$verbose)); + +for @int.permutations.unique -> @candidate +{ + say ": Candidate: @candidate[]" if $verbose; + + my @right = @candidate.clone; + my @left; + + while @right.elems > 1 + { + @left.push: @right.shift; + my $left-avg = @left.sum / @left.elems; + my $right-avg = @right.sum / @right.elems; + + say ": - Comparing @left[] (avg: $left-avg) <=> @right[] (avg: $right-avg)" if $verbose; + + if $left-avg == $right-avg + { + say 'true'; + exit; + } + } +} + +say 'false'; diff --git a/challenge-211/arne-sommer/raku/toeplitz-matrix b/challenge-211/arne-sommer/raku/toeplitz-matrix new file mode 100755 index 0000000000..53e3a53d69 --- /dev/null +++ b/challenge-211/arne-sommer/raku/toeplitz-matrix @@ -0,0 +1,43 @@ +#! /usr/bin/env raku + +unit sub MAIN (Str $matrix = "4 3 2 1 | 5 4 3 2 | 6 5 4 3", :v(:$verbose)); + +my @matrix = $matrix.split("|")>>.words>>.Array; +my @size = @matrix>>.elems; + +die "Must have at least 2 rows" unless @size.elems >= 2; +die "The rows must have the same size" unless [==] @size; + +while @matrix.elems +{ + @matrix.shift if @matrix[0].elems == 0; + + last unless @matrix.elems; + + my $row = 0; + my $col = @matrix[$row].end; + + my $value = @matrix[$row].pop; + + say ": Row:0 { @matrix.raku } -> $value (last value removed from row)" if $verbose; + + loop + { + $row++; + $col++; + last unless defined @matrix[$row]; + last unless defined @matrix[$row][$col]; + + my $new = @matrix[$row].pop; + + say ": Row:$row { @matrix.raku } -> $new (last value removed from row)" if $verbose; + + unless $value eq $new + { + say 'false'; + exit; + } + } +} + +say 'true'; diff --git a/challenge-211/eric-cheung/python/ch-1.py b/challenge-211/eric-cheung/python/ch-1.py new file mode 100755 index 0000000000..2376aa66d7 --- /dev/null +++ b/challenge-211/eric-cheung/python/ch-1.py @@ -0,0 +1,17 @@ +
+## arrMatrixInput = [[4, 3, 2, 1], [5, 4, 3, 2], [6, 5, 4, 3]] ## Example 1
+arrMatrixInput = [[1, 2, 3], [3, 2, 1]] ## Example 2
+
+nMatrixRow = len(arrMatrixInput)
+nMatrixCol = len(arrMatrixInput[0])
+
+nMinIndx = min(nMatrixRow, nMatrixCol)
+
+bIsToeplitzMatrix = True
+nDiagElem = arrMatrixInput[0][0]
+for nIndxLoop in range(1, nMinIndx):
+ if arrMatrixInput[nIndxLoop][nIndxLoop] != nDiagElem:
+ bIsToeplitzMatrix = False
+ break
+
+print (bIsToeplitzMatrix)
diff --git a/challenge-211/eric-cheung/python/ch-2.py b/challenge-211/eric-cheung/python/ch-2.py new file mode 100755 index 0000000000..20c7925e9f --- /dev/null +++ b/challenge-211/eric-cheung/python/ch-2.py @@ -0,0 +1,64 @@ +
+## Remarks
+## https://github.com/ChiahungTai/LeetCode/blob/master/Python/split-array-with-same-average.py
+
+
+## Time: O(n^4)
+## Space: O(n^3)
+
+## In a given integer array A, we must move every element of A to
+## either list B or list C. (B and C initially start empty.)
+##
+## Return true if and only if after such a move, it is possible that
+## the average value of B is equal to the average value of C, and B and C are both non-empty.
+##
+## Example :
+## Input:
+## [1, 2, 3, 4, 5, 6, 7, 8]
+## Output: true
+## Explanation: We can split the array into [1, 4, 5, 8] and [2, 3, 6, 7],
+## and both of them have the average of 4.5.
+##
+## Note:
+## - The length of A will be in the range [1, 30].
+## - A[i] will be in the range of [0, 10000].
+
+class Solution(object):
+
+ def splitArraySameAverage(self, A):
+ """
+ :type A: List[int]
+ :rtype: bool
+ """
+ def possible(total, n):
+ for i in range(1, n // 2 + 1):
+ if total * i % n == 0:
+ return True
+
+ return False
+
+ n, s = len(A), sum(A)
+
+ if not possible(n, s):
+ return False
+
+ sums = [set() for _ in range(n // 2 + 1)];
+ sums[0].add(0)
+
+ for num in A: # O(n) times
+ for i in reversed(range(1, n // 2 + 1)): ## O(n) times
+ for prev in sums[i - 1]: ## O(1) + O(2) + ... O(n/2) = O(n^2) times
+ sums[i].add(prev + num)
+
+ for i in range(1, n // 2 + 1):
+ if s * i % n == 0 and s * i // n in sums[i]:
+ return True
+
+ return False
+
+
+## arrInput = [1, 2, 3, 4, 5, 6, 7, 8] ## Example 1
+arrInput = [1, 3] ## Example 2
+
+objVar = Solution()
+print (objVar.splitArraySameAverage(arrInput))
diff --git a/challenge-211/james-smith/README.md b/challenge-211/james-smith/README.md index 0985d3892c..fd356c934e 100644 --- a/challenge-211/james-smith/README.md +++ b/challenge-211/james-smith/README.md @@ -1,7 +1,7 @@ -[< Previous 209](https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-209/james-smith) | -[Next 211 >](https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-211/james-smith) +[< Previous 210](https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-210/james-smith) | +[Next 212 >](https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-212/james-smith) -# The Weekly Challenge 210 +# The Weekly Challenge 211 You can find more information about this weeks, and previous weeks challenges at: @@ -13,84 +13,59 @@ submit solutions in whichever language you feel comfortable with. You can find the solutions here on github at: -https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-210/james-smith +https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-211/james-smith -# Task 1: Kill and Win +# Task 1: Toeplitz Matrix -***You are given a list of integers. Write a script to get the maximum points. You are allowed to take out (kill) any integer and remove from the list. However if you do that then all integers exactly one-less or one-more would also be removed. Find out the total of integers removed.*** +***You are given a matrix `m` x `n`. Write a script to find out if the given matrix is Toeplitz Matrix. A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same elements.*** ## Solution -Although it's not fully clear on the rules - we make the assumption that it means once we chose one number all those above and below are killed. - -Firstly we compute counts of each of the numbers, we then for each value compute: - -``` - count{n-1}*(n-1) + count{n}*n + count{n+1}*(n+1) -``` - -We just loop through all the keys of the count and compute the maximum value: ```perl -sub kill_and_win { - my($m,%c,$x)=0; - $c{$_}++ for @_; ## Get freq in hash - ( ( $x = ( $c{$_-1} ? $c{$_-1}*($_-1) : 0 ) ## Compute value - + ( $c{$_ } ? $c{$_ }* $_ : 0 ) ## for current - + ( $c{$_+1} ? $c{$_+1}*($_+1) : 0 ) ## integer - ) > $m ) && ($m = $x) for keys %c; ## if max reset max - $m ## return value +sub toeplitz { + return if @_ > @{$_[0]}; ## unclear but no diagonals... + my @st = @{$_[0]}[ 0 .. @{$_[0]} - @_ ]; + for my $r ( 1 .. $#_ ) { + $st[$_] == $_[$r][$r+$_] || return 0 for 0 .. $#st; + } + 1 } ``` -### A neater solution.... +Firstly we check to see if we have more rows than columns (there are no full diagonals) so there is no result. -```perl -sub kill_and_win { - my($m,%t,$x)=0; - $t{$_} += $_ for @_; ## Get freq in hash - ( ( $x = ( $t{$_-1} // 0 ) ## Compute value - + ( $t{$_ } // 0 ) ## for current - + ( $t{$_+1} // 0 ) ## integer - ) > $m ) && ($m = $x) for keys %t; ## if max reset max - $m ## return value -} -``` +Then we grab the first row of each of the diagonal - the number of possible diagonals is `columns - rows + 1`. +We then loop through each other row - and find the chunk of the row on the diagonal - and compare it with the first row. + +If there is a difference we return `0`; -About the same efficiency as above - we can simplify the sum part of the operation by computing the sum of each number before the 2nd loop. So instead of incrementing by 1 to get the count we just add the value each time.. +If the are no differences we return `1`; # Task 2: Number Collision -***You are given an array of integers which can move in right direction if it is positive and left direction when negative. If two numbers collide then the smaller one will explode. And if both are same then they both explode. We take the absolute value in consideration when comparing. All numbers move at the same speed, therefore any 2 numbers moving in the same direction will never collide. Write a script to find out who survives the collision.*** +***You are given an array of integers. Write a script to find out if the given can be split into two separate arrays whose average are the same..*** ## Solution -We can use a stack to achieve this. We start with an empty stack and follow these simple rules. +First we compute the overall average of the sets of numbers (or at least the sum and the count). We then loop through all subsets of numbers to see if we can find a subset with the same average. - 1) **IF** - 1) the list is empty - 2) the next value is +ve - 3) the last number on the stack is -ve - - **THEN** we push the next value onto the stack; +We can enumerate sub sets by using a binary mask to choose elements - For every solution there are two sets one whic includes the first number and one that doesn't - as we only need to calculate one set - then we can always assume that the first entry is NOT in the set we are summing. - 2) **IF** the absolute value for the top of the stack and the next value **THEN** we remove the value from the stack and throw away the current value; +To compare the means we could use `TOTAL_all / COUNT_all == TOTAL_subset / COUNT_subset` but this involves division which isn't good - but we can rewrite this as: +`TOTAL_all * COUNT_subset == TOTAL_subset * COUNT_all`. - 3) **IF** the absolute value for the top of the stack is less than the absolute value of the next value **THEN** we remove the value from the top of the stack; - - 4) **Otherwise (IF)** the absolute value for the top of the stack is greater than the absolute value of the next value **THEN** we just throw the current value away. +We enumerate the sets from `1` to `2^(n-1) - 1` the bits representing whether or not the number is in one set or the other. ```perl -sub collision { - my @s; - !@s || - $_[0] > 0 || - 0 > $s[-1] ? push @s, shift - : -$_[0] == $s[-1] ? pop @s && shift - : -$_[0] >= $s[-1] ? pop @s - : shift - while @_; - @s +sub equal_split { + my( $t, $c ) = ( 0, scalar @_ ); + $t += $_ for @_; + for my $x ( 1 .. ( 1 << $c-1 ) -1 ) { + my( $m, $n ) = ( 0, 0 ); + ( $x & 1 ) && ( $m += $_[$_], $n++ ), $x >>= 1 for 1 .. $c-1; + return 1 unless $n*$t-$m*$c; + } + 0 } ``` - diff --git a/challenge-211/james-smith/blog.txt b/challenge-211/james-smith/blog.txt new file mode 100644 index 0000000000..30a5f277f3 --- /dev/null +++ b/challenge-211/james-smith/blog.txt @@ -0,0 +1 @@ +https://github.com/manwar/perlweeklychallenge-club/blob/master/challenge-211/james-smith/blog.txt diff --git a/challenge-211/james-smith/perl/ch-1.pl b/challenge-211/james-smith/perl/ch-1.pl new file mode 100644 index 0000000000..c62df391d1 --- /dev/null +++ b/challenge-211/james-smith/perl/ch-1.pl @@ -0,0 +1,22 @@ +#!/usr/local/bin/perl + +use strict; +use warnings; +use feature qw(say); +use Test::More; + +my @TESTS = ( + [ [[4,3,2,1],[5,4,3,2],[6,5,4,3]], 1 ], + [ [[1,2,3],[3,2,1]], 0 ], +); + +sub toeplitz { + return if @_ > @{$_[0]}; ## unclear but no diagonals.. + my @st = @{$_[0]}[ 0 .. @{$_[0]} - @_ ]; + for my $r ( 1 .. $#_ ) { + $st[$_] == $_[$r][$r+$_] || return 0 for 0 .. $#st; + } + 1 +} + +is( toeplitz( @{$_->[0]} ), $_->[1] ) for @TESTS; diff --git a/challenge-211/james-smith/perl/ch-2.pl b/challenge-211/james-smith/perl/ch-2.pl new file mode 100644 index 0000000000..8c259b88c1 --- /dev/null +++ b/challenge-211/james-smith/perl/ch-2.pl @@ -0,0 +1,24 @@ +#!/usr/local/bin/perl + +use strict; +use warnings; +use feature qw(say); +use Test::More; + +my @TESTS = ( + [ [1,2,3,4,5,6,7,8], 1 ], + [ [1,3], 0 ], +); + +sub equal_split { + my( $t, $c ) = ( 0, scalar @_ ); + $t += $_ for @_; + for my $x ( 1 .. ( 1 << $c-1 ) -1 ) { + my($m,$n)=(0,0); my @T; + ( $x & 1 ) && ( $m += $_[$_], $n++, push @T, $_[$_] ), $x >>= 1 for 1 .. $c-1; + return 1 unless $n*$t-$m*$c; + } + 0 +} + +is( equal_split( @{$_->[0]} ), $_->[1] ) for @TESTS; diff --git a/challenge-211/jo-37/perl/ch-1.pl b/challenge-211/jo-37/perl/ch-1.pl new file mode 100755 index 0000000000..586b91905e --- /dev/null |