diff options
66 files changed, 3743 insertions, 1897 deletions
diff --git a/challenge-125/sgreen/README.md b/challenge-125/sgreen/README.md deleted file mode 100644 index e025103f4b..0000000000 --- a/challenge-125/sgreen/README.md +++ /dev/null @@ -1,3 +0,0 @@ -# The Weekly Challenge 124 - -Solution by Simon Green. [Blog](https://dev.to/simongreennet/weekly-challenge-124-2gi7) diff --git a/challenge-125/simon-proctor/raku/ch-2.raku b/challenge-125/simon-proctor/raku/ch-2.raku index 2ab4173e5a..45a70774c7 100644 --- a/challenge-125/simon-proctor/raku/ch-2.raku +++ b/challenge-125/simon-proctor/raku/ch-2.raku @@ -146,10 +146,10 @@ multi sub MAIN( *@data ) { say $tree; my $long = shift @routes; - my $result = $long.elems; + my $result = $long.elems - 1; for @routes -> $pos { if ($long (&) $pos).elems == 1 { - $result = $long.elems + $pos.elems - 1; + $result = $long.elems + $pos.elems - 2; last; } } diff --git a/challenge-126/ash/raku/ch-1.raku b/challenge-126/ash/raku/ch-1.raku new file mode 100644 index 0000000000..08d68052e4 --- /dev/null +++ b/challenge-126/ash/raku/ch-1.raku @@ -0,0 +1,18 @@ +sub count($n) { + my @items = (2..$n).grep: * !~~ /1/; + given @items.elems { + when 0 { + say "There are no numbers up to $n that contain no digit 1."; + } + when 1 { + say "There is 1 number between 1 and $n that doesn't contain digit 1."; + } + default { + say "There are {+@items} numbers between 1 and $n that don't contain digit 1."; + } + } + + say @items.join(', ') ~ '.' if @items; +} + +.&count for 1, 2, 5, 15, 25; diff --git a/challenge-126/cristian-heredia/perl/ch-1.pl b/challenge-126/cristian-heredia/perl/ch-1.pl new file mode 100755 index 0000000000..d70f4756fd --- /dev/null +++ b/challenge-126/cristian-heredia/perl/ch-1.pl @@ -0,0 +1,36 @@ +=begin + TASK #1 › Count Numbers + Submitted by: Mohammad S Anwar + You are given a positive integer $N. + + Write a script to print count of numbers from 1 to $N that don’t contain digit 1. + + Example + Input: $N = 15 + Output: 8 + + There are 8 numbers between 1 and 15 that don't contain digit 1. + 2, 3, 4, 5, 6, 7, 8, 9. + + Input: $N = 25 + Output: 13 + + There are 13 numbers between 1 and 25 that don't contain digit 1. + 2, 3, 4, 5, 6, 7, 8, 9, 20, 22, 23, 24, 25. + +=end +=cut + +use strict; +use warnings; +use Data::Dumper; + +my $N = 15; +my $counter = 0; + +for my $iter (1 .. $N) { + if ( $iter !~ /1+/) { + $counter++; + } +} +print("Output: $counter\n");
\ No newline at end of file diff --git a/challenge-126/cristian-heredia/python/ch-1.py b/challenge-126/cristian-heredia/python/ch-1.py new file mode 100755 index 0000000000..f0ec59c383 --- /dev/null +++ b/challenge-126/cristian-heredia/python/ch-1.py @@ -0,0 +1,30 @@ +''' + TASK #1 › Count Numbers + Submitted by: Mohammad S Anwar + You are given a positive integer $N. + + Write a script to print count of numbers from 1 to $N that don’t contain digit 1. + + Example + Input: $N = 15 + Output: 8 + + There are 8 numbers between 1 and 15 that don't contain digit 1. + 2, 3, 4, 5, 6, 7, 8, 9. + + Input: $N = 25 + Output: 13 + + There are 13 numbers between 1 and 25 that don't contain digit 1. + 2, 3, 4, 5, 6, 7, 8, 9, 20, 22, 23, 24, 25. + +''' + +N = 15 +counter = 0 + +for iter in range(1, N+1): + if not '1' in str(iter): + counter += 1 + +print(f"Output: {counter}");
\ No newline at end of file diff --git a/challenge-126/eric-cheung/excel-vba/Challenge_126.xlsm b/challenge-126/eric-cheung/excel-vba/Challenge_126.xlsm Binary files differnew file mode 100644 index 0000000000..b870075d23 --- /dev/null +++ b/challenge-126/eric-cheung/excel-vba/Challenge_126.xlsm diff --git a/challenge-126/eric-cheung/excel-vba/ch-1.bas b/challenge-126/eric-cheung/excel-vba/ch-1.bas new file mode 100644 index 0000000000..0f3d5fdba1 --- /dev/null +++ b/challenge-126/eric-cheung/excel-vba/ch-1.bas @@ -0,0 +1,62 @@ +Attribute VB_Name = "ModTask_01"
+Option Explicit
+Option Base 1
+Public Const strMyTitle As String = "Eric Cheung"
+
+Function GetCountNum(nNum) As Long
+
+ Dim nLoop As Long, nCntItem As Long, nTenNum As Long, nResult As Long, nTemp As Long, nTenPower As Long
+ Dim nNumArr As Variant
+
+ If nNum <= 1 Then
+ GetCountNum = 0
+ Exit Function
+ End If
+
+ nCntItem = 9
+ nNumArr = Array(0, 2, 3, 4, 5, 6, 7, 8, 9)
+
+ nTenNum = 0
+ nResult = 0
+ nTenPower = 1
+
+ Do While True
+ For nLoop = 1 To nCntItem
+ nTemp = nTenNum * 10 + nNumArr(nLoop)
+ If nTemp = nNum Then
+ GetCountNum = nResult 'Exclude 0
+ Exit Function
+ ElseIf nTemp > nNum Then
+ GetCountNum = nResult - 1 'Exclude 0
+ Exit Function
+ End If
+ nResult = nResult + 1
+ Next nLoop
+
+ If nTenNum Mod 10 = 0 Then ''E.g. nTenNum: 0, 20, 30, 40, ...
+ nTenNum = nTenNum + 2
+ ElseIf nTenNum = nTenPower * 10 - 1 Then ''E.g. nTenNum: 9, 99, 999, ...
+ nTenPower = nTenPower * 10
+ nTenNum = nTenNum + nTenPower + 1
+ Else
+ nTenNum = nTenNum + 1
+ End If
+ Loop
+
+End Function
+
+Sub Task_01()
+
+ Dim varInputNum
+ Dim strMsg As String
+
+ Do
+ varInputNum = InputBox("Please enter a positive number", strMyTitle, 15)
+ If varInputNum = "" Then Exit Sub
+ Loop Until varInputNum > 0
+
+ strMsg = "There are " & GetCountNum(varInputNum) & " numbers between 1 and " & varInputNum & " that don't contain digit 1"
+
+ MsgBox strMsg, vbOKOnly, strMyTitle
+
+End Sub
diff --git a/challenge-126/eric-cheung/excel-vba/ch-2.bas b/challenge-126/eric-cheung/excel-vba/ch-2.bas new file mode 100644 index 0000000000..1d75c8adba --- /dev/null +++ b/challenge-126/eric-cheung/excel-vba/ch-2.bas @@ -0,0 +1,157 @@ +Attribute VB_Name = "ModTask_02"
+Option Explicit
+Option Base 1
+
+Function PrintArr(nMatrix, Optional bHide As Boolean = True) As String
+
+ Dim nRowLoop As Integer, nColLoop As Integer
+
+ For nRowLoop = LBound(nMatrix, 1) To UBound(nMatrix, 1)
+ For nColLoop = LBound(nMatrix, 2) To UBound(nMatrix, 2)
+ If PrintArr <> "" Then
+ PrintArr = PrintArr & " "
+ End If
+
+ If bHide And nMatrix(nRowLoop, nColLoop) = 0 Then
+ PrintArr = PrintArr & "*"
+ ElseIf nMatrix(nRowLoop, nColLoop) = -1 Then
+ PrintArr = PrintArr & "x"
+ Else
+ PrintArr = PrintArr & nMatrix(nRowLoop, nColLoop)
+ End If
+ Next nColLoop
+ PrintArr = PrintArr & vbNewLine
+ Next nRowLoop
+
+End Function
+
+Function CountLandMineNearBy(ByRef nMatrix, nRowIndex As Integer, nColIndex As Integer) As Integer
+
+ Dim nRowSize As Integer, nColSize As Integer
+
+ If nMatrix(nRowIndex, nColIndex) = -1 Then
+ CountLandMineNearBy = -1
+ Exit Function
+ End If
+
+ nRowSize = UBound(nMatrix, 1) - LBound(nMatrix, 1) + 1
+ nColSize = UBound(nMatrix, 2) - LBound(nMatrix, 2) + 1
+
+ If nRowIndex - 1 > 0 And nColIndex - 1 > 0 Then
+ If nMatrix(nRowIndex - 1, nColIndex - 1) = -1 Then
+ CountLandMineNearBy = CountLandMineNearBy + 1
+ End If
+ End If
+
+ If nRowIndex - 1 > 0 Then
+ If nMatrix(nRowIndex - 1, nColIndex) = -1 Then
+ CountLandMineNearBy = CountLandMineNearBy + 1
+ End If
+ End If
+
+ If nRowIndex - 1 > 0 And nColIndex < nColSize Then
+ If nMatrix(nRowIndex - 1, nColIndex + 1) = -1 Then
+ CountLandMineNearBy = CountLandMineNearBy + 1
+ End If
+ End If
+
+ If nColIndex - 1 > 0 Then
+ If nMatrix(nRowIndex, nColIndex - 1) = -1 Then
+ CountLandMineNearBy = CountLandMineNearBy + 1
+ End If
+ End If
+
+ If nColIndex < nColSize Then
+ If nMatrix(nRowIndex, nColIndex + 1) = -1 Then
+ CountLandMineNearBy = CountLandMineNearBy + 1
+ End If
+ End If
+
+ If nRowIndex < nRowSize And nColIndex - 1 > 0 Then
+ If nMatrix(nRowIndex + 1, nColIndex - 1) = -1 Then
+ CountLandMineNearBy = CountLandMineNearBy + 1
+ End If
+ End If
+
+ If nRowIndex < nRowSize Then
+ If nMatrix(nRowIndex + 1, nColIndex) = -1 Then
+ CountLandMineNearBy = CountLandMineNearBy + 1
+ End If
+ End If
+
+ If nRowIndex < nRowSize And nColIndex < nColSize Then
+ If nMatrix(nRowIndex + 1, nColIndex + 1) = -1 Then
+ CountLandMineNearBy = CountLandMineNearBy + 1
+ End If
+ End If
+
+End Function
+
+Sub CountLandMineNearByAll(ByRef nMatrix)
+
+ Dim nRowLoop As Integer, nColLoop As Integer
+
+ For nRowLoop = LBound(nMatrix, 1) To UBound(nMatrix, 1)
+ For nColLoop = LBound(nMatrix, 2) To UBound(nMatrix, 2)
+ If nMatrix(nRowLoop, nColLoop) > -1 Then
+ nMatrix(nRowLoop, nColLoop) = CountLandMineNearBy(nMatrix, nRowLoop, nColLoop)
+ End If
+ Next nColLoop
+ Next nRowLoop
+
+End Sub
+
+Sub Task_02()
+
+ Const nRowNum As Integer = 5
+ Const nColNum As Integer = 10
+
+ Dim strMsg As String
+
+ '' Define Rectangle
+ Dim nMineArr(1 To nRowNum, 1 To nColNum) As Integer
+
+ '' ======== Land Mine ========
+ '' Initialize, -1 Represents Land Mine
+ nMineArr(1, 1) = -1
+ nMineArr(5, 1) = -1
+
+ nMineArr(4, 4) = -1
+
+ nMineArr(1, 5) = -1
+ nMineArr(3, 5) = -1
+ nMineArr(4, 5) = -1
+ nMineArr(5, 5) = -1
+
+ nMineArr(1, 7) = -1
+ nMineArr(3, 7) = -1
+
+ nMineArr(1, 8) = -1
+
+ nMineArr(1, 9) = -1
+ nMineArr(3, 9) = -1
+
+ nMineArr(1, 10) = -1
+ nMineArr(2, 10) = -1
+ nMineArr(5, 10) = -1
+ '' ======== Land Mine ========
+
+
+ '' ======== Print Original Array ========
+ ''strMsg = PrintArr(nMineArr)
+ '' ======== Print Original Array ========
+
+ '' ======== Count ========
+ CountLandMineNearByAll nMineArr
+ '' ======== Count ========
+
+ '' ======== Print Count Array ========
+ strMsg = PrintArr(nMineArr, False)
+ '' ======== Print Count Array ========
+
+ '' ======== Output Result ========
+ MsgBox strMsg, vbOKOnly, strMyTitle
+ '' ======== Output Result ========
+
+End Sub
+
diff --git a/challenge-126/james-smith/README.md b/challenge-126/james-smith/README.md index 97ebd934cd..6f2ffee2f8 100644 --- a/challenge-126/james-smith/README.md +++ b/challenge-126/james-smith/README.md @@ -1,4 +1,4 @@ -# Perl Weekly Challenge #125 +# Perl Weekly Challenge #126 You can find more information about this weeks, and previous weeks challenges at: @@ -10,67 +10,85 @@ 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-125/james-smith/perl +https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-126/james-smith/perl -# Task 1 - Pythagorean Triples +# Task 1 - Count Numbers -***You are given a positive integer `$N`. Write a script to print all Pythagorean Triples containing `$N` as a member. Print `-1` if it can’t be a member of any. Triples with the same set of elements are considered the same, i.e. if your script has already printed (3, 4, 5), (4, 3, 5) should not be printed.*** +***You are given a positive integer `$N` - Write a script to print count of numbers from `1` to `$N` that don’t contain digit `1`.*** ## The solution -There are two cases to consider - whether `$N` is the hypotenuse or one of the shorter sides. +First pass - just do the simple `O(n)` thing which is to loop through all `$N` numbers and count those without `1`s. - * `$N` is the hypotenuse - we just need to work out whether `$N**2 - $a**2` is a square for `$a` between `3` and `$N/sqrt 2` +```perl +sub get_no_one_count { + my $n = shift; + return scalar grep { ! m{1} } 2..$n; +} +``` - * `$N` is not the hypotenuse - we need to loop through `$a` from `$N+1` such that `$a**2-$N**2` is a square. +If we look at a few numbers we see that for powers of 10 we see we have values 8, 80, 728, 6560, 59048, ... what we notices these are all of the form `9^$N-1`.... For multiples of these we see that for the total is `(n-1)*9^N`. + +We see we can then add these up - with one exception if we find a 1 we stop the loop (or if working backwards) throw any calculations away - giving us the order `O(ln n)` solution: -This gives: ```perl -sub get_triples { - my $n = shift; - return $n < 3 ? -1 : join '; ', map { sprintf '(%s)', join ', ', @{$_} } - ( - grep { $_->[1] == int $_->[1] } ## Check if all int - map { [ $_, sqrt($n**2-$_**2), $n ] } ## Generate triple - 3 .. sqrt($n**2/2) ## Shortest side ($n is hypotenuse) - ),( - map { $_->[0]>$_->[1] ? [@{$_}[1,0,2]] : $_ } ## put in numerical order - grep { $_->[1] == int $_->[1] } ## Check all int - map { [ $n, sqrt($_**2-$n**2), $_ ] } ## Generate triple - ($n+1) .. ($n**2/2+1) ## Hypotenuse ($n is one of other two sides) - ); +sub get_no_one_count_9 { + my ( $n, $count, $pow_9 ) = ( shift, 0, 1 ); + while($n) { + my $t = $n % 10; ## get last digit + $count = 0 if $t==1; ## Throw everything away we've found a 1 + $count += $t ? ( $t == 1 ? ($pow_9-1) : ($t-1)*$pow_9 ) : 0; + ## 0 it contributes nothing + ## 1 contributes 9^X-1 + ## 2-9 contributes (n-1)9^X + $pow_9 *= 9; ## update power of nine + $n = ( $n - $t )/10; ## drop last digit + } + return $count; } ``` -# Task 2 - Binary Tree Diameter -*** Write a script to find the diameter of the given binary tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. It doesn’t have to pass through the root.*** +## Comparison +Even for 2 digit numbers this speed up is good (72x), but as N increases +we see that gain gets higher and higher.. for 7 digit numbers the speed +up is 6 orders of magnitude. -## Solution +| N | scan | opt | Speed-up | +| --------: | --------: | --------: | ---------: | +| 98 | 16,027 | 1,173,850 | 72 | +| 987 | 2,623 | 867,796 | 330 | +| 9,876 | 253 | 685,956 | 2,715 | +| 98,765 | 24.4 | 565,427 | 23,155 | +| 987,654 | 1.23 | 482,800 | 392,998 | +| 9,876,543 | 0.23 | 418,410 | 1,853,771 | -For any node - we can compute the longest tree which goes through the node itself - this is the sum of the maximum lengths of the left tree and the depth of the right. We do know that there will be trees for which this is not the diameter - there could be another node for which the left and right depths sum to a larger value... +# Task 2 - Minesweeper Game -So to compute the diameter of the tree we just choose the maximum value of the maximum lengths of the left/right sub tree. +***You are given a rectangle with points marked with either `x` or `*`. Consider the `x` as a land mine. Write a script to print a rectangle with numbers and `x` as in the Minesweeper game.*** -We will re-use the BinaryTree module from a previous challenge and so need to define walk functions to work out the maximum length of a subtree and consequently diameter... +## Solution ```perl -sub max_length { - my $self = shift; - my $d = 0; - $d = $self->left->max_length if $self->has_left; - return 1+$d unless $self->has_right; - my $t = $self->right->max_length; - return $t > $d ? 1+$t : 1+$d; -} - -sub diameter { - my $self = shift; - my $global = { 'diameter' => 0 }; - $self->walk( sub { - my $d = ($_[0]->has_left ? $_[0]->left->max_length : 0 ) + - ($_[0]->has_right ? $_[0]->right->max_length : 0 ); - $_[1]{'diameter'} = $d if $d > $_[1]->{'diameter'}; - }, $global ); - return $global->{'diameter'}; +sub solve { + my @res = (); + my @g = map { [ map { $_ eq 'x' ? 1 : 0 } split //, $_ ] } @_; + + my( $h, $w ) = ( $#_, -1 + length $_[0] ); + foreach my $y ( 0 .. $h ) { + push @res, join '', map { + $g[$y][$_] ? 'x' : + ( $y ? ( $_ ? $g[$y-1][$_-1] : 0 ) + $g[$y-1][$_] + ( $_<$w ? $g[$y-1][$_+1] : 0 ) : 0 ) + + ( $_ ? $g[$y ][$_-1] : 0 ) + $g[$y ][$_] + ( $_<$w ? $g[$y ][$_+1] : 0 ) + + ( $y<$h ? ( $_ ? $g[$y+1][$_-1] : 0 ) + $g[$y+1][$_] + ( $_<$w ? $g[$y+1][$_+1] : 0 ) : 0 ) + } 0 .. $w; + } + return join "\n", @res; } ``` + +There are two stages to this: + + 1. convert the strings into an array of `1`s and `0`s representing mines and spaces. + 2. we compute the convulation - counting the number of mines in adjacent squares (or tagging with a "x" if the square is bomb). + Rather than using loops and if statements we use nested ternary operators in a single line + diff --git a/challenge-126/james-smith/blog.txt b/challenge-126/james-smith/blog.txt new file mode 100644 index 0000000000..7562bfe1b6 --- /dev/null +++ b/challenge-126/james-smith/blog.txt @@ -0,0 +1 @@ +https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-126/james-smith
\ No newline at end of file diff --git a/challenge-126/james-smith/perl/ch-1.pl b/challenge-126/james-smith/perl/ch-1.pl new file mode 100644 index 0000000000..a42ad642c7 --- /dev/null +++ b/challenge-126/james-smith/perl/ch-1.pl |