diff options
Diffstat (limited to 'challenge-077')
23 files changed, 638 insertions, 1 deletions
diff --git a/challenge-077/abigail/Part1/input1 b/challenge-077/abigail/Part1/input1 new file mode 100644 index 0000000000..1e8b314962 --- /dev/null +++ b/challenge-077/abigail/Part1/input1 @@ -0,0 +1 @@ +6 diff --git a/challenge-077/abigail/Part1/input2 b/challenge-077/abigail/Part1/input2 new file mode 100644 index 0000000000..ec635144f6 --- /dev/null +++ b/challenge-077/abigail/Part1/input2 @@ -0,0 +1 @@ +9 diff --git a/challenge-077/abigail/Part1/input3 b/challenge-077/abigail/Part1/input3 new file mode 100644 index 0000000000..83b33d238d --- /dev/null +++ b/challenge-077/abigail/Part1/input3 @@ -0,0 +1 @@ +1000 diff --git a/challenge-077/abigail/Part1/input4 b/challenge-077/abigail/Part1/input4 new file mode 100644 index 0000000000..66a899ac41 --- /dev/null +++ b/challenge-077/abigail/Part1/input4 @@ -0,0 +1 @@ +377 diff --git a/challenge-077/abigail/Part1/output1.exp b/challenge-077/abigail/Part1/output1.exp new file mode 100644 index 0000000000..170feacebb --- /dev/null +++ b/challenge-077/abigail/Part1/output1.exp @@ -0,0 +1,2 @@ +1 + 2 + 3 = 6 +1 + 5 = 6 diff --git a/challenge-077/abigail/Part1/output2.exp b/challenge-077/abigail/Part1/output2.exp new file mode 100644 index 0000000000..d029569c34 --- /dev/null +++ b/challenge-077/abigail/Part1/output2.exp @@ -0,0 +1,2 @@ +1 + 3 + 5 = 9 +1 + 8 = 9 diff --git a/challenge-077/abigail/Part1/output3.exp b/challenge-077/abigail/Part1/output3.exp new file mode 100644 index 0000000000..88b8b236eb --- /dev/null +++ b/challenge-077/abigail/Part1/output3.exp @@ -0,0 +1,15 @@ +2 + 3 + 8 + 21 + 34 + 89 + 233 + 610 = 1000 +2 + 3 + 8 + 55 + 89 + 233 + 610 = 1000 +2 + 3 + 8 + 144 + 233 + 610 = 1000 +2 + 3 + 8 + 377 + 610 = 1000 +2 + 3 + 8 + 987 = 1000 +5 + 8 + 21 + 34 + 89 + 233 + 610 = 1000 +5 + 8 + 55 + 89 + 233 + 610 = 1000 +5 + 8 + 144 + 233 + 610 = 1000 +5 + 8 + 377 + 610 = 1000 +5 + 8 + 987 = 1000 +13 + 21 + 34 + 89 + 233 + 610 = 1000 +13 + 55 + 89 + 233 + 610 = 1000 +13 + 144 + 233 + 610 = 1000 +13 + 377 + 610 = 1000 +13 + 987 = 1000 diff --git a/challenge-077/abigail/Part1/output4.exp b/challenge-077/abigail/Part1/output4.exp new file mode 100644 index 0000000000..4fc109d510 --- /dev/null +++ b/challenge-077/abigail/Part1/output4.exp @@ -0,0 +1,7 @@ +1 + 2 + 5 + 13 + 34 + 89 + 233 = 377 +3 + 5 + 13 + 34 + 89 + 233 = 377 +8 + 13 + 34 + 89 + 233 = 377 +21 + 34 + 89 + 233 = 377 +55 + 89 + 233 = 377 +144 + 233 = 377 +377 = 377 diff --git a/challenge-077/abigail/Part1/solution.js b/challenge-077/abigail/Part1/solution.js new file mode 100644 index 0000000000..f2d7173403 --- /dev/null +++ b/challenge-077/abigail/Part1/solution.js @@ -0,0 +1,97 @@ +// +// Exercise: +// You are given a positive integer $N. +// Write a script to find out all possible combination of Fibonacci +// Numbers required to get $N on addition. +// +// You are NOT allowed to repeat a number. Print 0 if none found. +// + +// +// Note: +// The "Print 0 if none found." is irrelevant. There is always at +// least one way to write any positive integer as a sum of distinct +// Fibonacci Numbers. (Zeckendorf's theorem states: "very positive +// integer can be represented uniquely as the sum of one or more +// distinct Fibonacci numbers in such a way that the sum does not +// include any two consecutive Fibonacci numbers") +// + +// +// Read the input number from STDIN +// +let fs = require ("fs"); +let N = +fs . readFileSync (0) . toString () . trim (); + +// +// Generate a list of Fibonacci numbers, starting with (1, 2), +// up to the target number. Store this in FIB. +// +let FIB = [1, 2]; +while (FIB [FIB . length - 1] + FIB [FIB . length - 2] <= N) { + FIB . push (FIB [FIB . length - 1] + FIB [FIB . length - 2]); +} + +// +// Recursive function to find the sums. First argument is the target +// number, second argument is the index of smallest number which can +// be used. +// +function solutions (target, index = 0) { + let output = []; + // + // Iterate over the list of Fibonacci numbers, looking for + // candidates. We're starting with the given index. + // + for (let i = index; i < FIB . length; i ++) { + let fib = FIB [i]; + if (fib > target) { + // + // If the candidate is larger than the target number, + // we can stop looking, as each subsequent number will + // be larger. + // + break; + } + if (fib == target) { + // + // If the candidate is equal to the target number, + // then it's a trivial solution (a sum of 1 number). + // Add it to the list of possibilities, and stop + // searching. + // + output . push ([fib]); + break; + } + else { + // + // Find solutions for the difference between the + // candidate and the target number, with the restriction + // that each number in that sum is larger than the numbers + // used so far. + // + let rec_solutions = solutions (target - fib, i + 1); + + // + // For each solution found in recursion, we have a solution + // for this call, by adding the candidate to it. + // + for (let j = 0; j < rec_solutions . length; j ++) { + output . push ([fib] . concat (rec_solutions [j])); + } + } + } + return output; +} + +// +// Find the solutions +// +let sols = solutions (N); + +// +// And print the results +// +for (let i = 0; i < sols . length; i ++) { + console . log (sols [i] . join (" + ") + " = " + N); +} diff --git a/challenge-077/abigail/Part1/solution.pl b/challenge-077/abigail/Part1/solution.pl new file mode 100644 index 0000000000..b39028c5b9 --- /dev/null +++ b/challenge-077/abigail/Part1/solution.pl @@ -0,0 +1,63 @@ +#!/opt/perl/bin/perl + +# +# Exercise: +# You are given a positive integer $N. +# Write a script to find out all possible combination of Fibonacci +# Numbers required to get $N on addition. +# +# You are NOT allowed to repeat a number. Print 0 if none found. +# + +# +# Note: +# The "Print 0 if none found." is irrelevant. There is always at +# least one way to write any positive integer as a sum of distinct +# Fibonacci Numbers. (Zeckendorf's theorem states: "very positive +# integer can be represented uniquely as the sum of one or more +# distinct Fibonacci numbers in such a way that the sum does not +# include any two consecutive Fibonacci numbers") +# + +use 5.032; + +use strict; +use warnings; +no warnings 'syntax'; + +use experimental 'signatures'; +use experimental 'lexical_subs'; + +chomp (my $N = <>); + +# +# Create a list of Fibonacci Numbers up to $N. We will start with (1, 2), +# skipping the first two numbers 0 and 1. 0 doesn't add anything, and +# we cannot duplicate numbers, so we just need one 1. +# +my @FIB = (1, 2); +while ($FIB [-1] + $FIB [-2] <= $N) { + push @FIB => $FIB [-1] + $FIB [-2]; +} + +sub solutions; + +# +# Create all solutions for number $target, with all Fibonnaci numbers +# having index $index or above. +# +sub solutions ($target, $index = 0) { + map { + my $fib = $FIB [$_]; + $target < $fib ? () + : $target == $fib ? [$target] + : map {[$fib, @$_]} solutions ($target - $fib, $_ + 1) + } $index .. @FIB - 1; +} + +my @all = solutions $N; + +local $" = " + "; +say "@$_ = $N" for @all; + +__END__ diff --git a/challenge-077/abigail/Part2/input1 b/challenge-077/abigail/Part2/input1 new file mode 100644 index 0000000000..f8beeb613f --- /dev/null +++ b/challenge-077/abigail/Part2/input1 @@ -0,0 +1,3 @@ +O O X +X O O +X O O diff --git a/challenge-077/abigail/Part2/input2 b/challenge-077/abigail/Part2/input2 new file mode 100644 index 0000000000..d81104f1b2 --- /dev/null +++ b/challenge-077/abigail/Part2/input2 @@ -0,0 +1,4 @@ +O O X O +X O O O +X O O X +O X O O diff --git a/challenge-077/abigail/Part2/output1.exp b/challenge-077/abigail/Part2/output1.exp new file mode 100644 index 0000000000..d00491fd7e --- /dev/null +++ b/challenge-077/abigail/Part2/output1.exp @@ -0,0 +1 @@ +1 diff --git a/challenge-077/abigail/Part2/output2.exp b/challenge-077/abigail/Part2/output2.exp new file mode 100644 index 0000000000..0cfbf08886 --- /dev/null +++ b/challenge-077/abigail/Part2/output2.exp @@ -0,0 +1 @@ +2 diff --git a/challenge-077/abigail/Part2/solution.js b/challenge-077/abigail/Part2/solution.js new file mode 100644 index 0000000000..ee04d5c605 --- /dev/null +++ b/challenge-077/abigail/Part2/solution.js @@ -0,0 +1,60 @@ +// +// Exercise: +// You are given m x n character matrix consists of O and X only. +// Write a script to count the total number of X surrounded by O only. +// Print 0 if none found. +// + +// +// Read in the board: +// - Read STDIN +// - Split by newlines +// - Split each line on spaces +// - Map an 'X' to a 1, 'O' to a 0. +// - Add a 0 to the beginning and end of each line. +// +let fs = require ("fs"); +let board = fs . readFileSync (0) . toString () . trim () . split ("\n") . + map (line => (line . split (" ")) . map (c => c == "X" ? 1 : 0)) . + map (line => ([0] . concat (line) . concat ([0]))); + +// +// Add top and bottom with 0s +// +board . push (board [0] . map (x => 0)); +board . unshift (board [0] . map (x => 0)); + +let count = 0; + +// +// Iterate over the cells of the board board, skipping cells on the edge +// (as we added them). For each 1, check the 8 cells surrounding the cell +// (this will never be outside of the board). If one of the neighbouring +// cells is a 1, move on the next cell. If no neighbouring cell is 1, +// we add 1 to the count. +// +for (let x = 1; x < board . length - 1; x ++) { + ELEMENT: + for (let y = 1; y < board [x] . length - 1; y ++) { + if (!board [x] [y]) { + continue; + } + for (let dx = -1; dx <= 1; dx ++) { + for (let dy = -1; dy <= 1; dy ++) { + if (dx == 0 && dy == 0) { + continue; + } + if (board [x + dx] [y + dy]) { + continue ELEMENT; + } + } + } + count ++; + } +} + + +// +// Print the results. +// +console . log (count); diff --git a/challenge-077/abigail/Part2/solution.pl b/challenge-077/abigail/Part2/solution.pl new file mode 100644 index 0000000000..784f4cd662 --- /dev/null +++ b/challenge-077/abigail/Part2/solution.pl @@ -0,0 +1,56 @@ +#!/opt/perl/bin/perl + +# +# Exercise: +# You are given m x n character matrix consists of O and X only. +# Write a script to count the total number of X surrounded by O only. +# Print 0 if none found. +# + +use 5.032; + +use strict; +use warnings; +no warnings 'syntax'; + +use experimental 'signatures'; +use experimental 'lexical_subs'; + +# +# Read in the board. Use 1 for an X, and 0 for an 0. Add a band +# of 0's around the board. +# + +my @board = map {[0, map ({/O/ ? 0 : 1} /[OX]/g), 0]} <>; +push @board => [(0) x @{$board [0]}]; +unshift @board => [(0) x @{$board [0]}]; + +my $count = 0; + +# +# Iterate over the cells of the board board, skipping cells on the edge +# (as we added them). For each 1, check the 8 cells surrounding the cell +# (this will never be outside of the board). If one of the neighbouring +# cells is a 1, move on the next cell. If no neighbouring cell is 1, +# we add 1 to the count. +# +for (my $x = 1; $x < @board - 1; $x ++) { + ELEMENT: + for (my $y = 1; $y < @{$board [$x]} - 1; $y ++) { + next unless $board [$x] [$y]; + foreach my $dx (-1 .. 1) { + foreach my $dy (-1 .. 1) { + next unless $dx || $dy; + next ELEMENT if $board [$x + $dx] [$y + $dy]; + } + } + $count ++; + } +} + +# +# Print solution. +# +say $count; + +__END__ diff --git a/challenge-077/abigail/node/ch-1.js b/challenge-077/abigail/node/ch-1.js new file mode 100644 index 0000000000..f2d7173403 --- /dev/null +++ b/challenge-077/abigail/node/ch-1.js @@ -0,0 +1,97 @@ +// +// Exercise: +// You are given a positive integer $N. +// Write a script to find out all possible combination of Fibonacci +// Numbers required to get $N on addition. +// +// You are NOT allowed to repeat a number. Print 0 if none found. +// + +// +// Note: +// The "Print 0 if none found." is irrelevant. There is always at +// least one way to write any positive integer as a sum of distinct +// Fibonacci Numbers. (Zeckendorf's theorem states: "very positive +// integer can be represented uniquely as the sum of one or more +// distinct Fibonacci numbers in such a way that the sum does not +// include any two consecutive Fibonacci numbers") +// + +// +// Read the input number from STDIN +// +let fs = require ("fs"); +let N = +fs . readFileSync (0) . toString () . trim (); + +// +// Generate a list of Fibonacci numbers, starting with (1, 2), +// up to the target number. Store this in FIB. +// +let FIB = [1, 2]; +while (FIB [FIB . length - 1] + FIB [FIB . length - 2] <= N) { + FIB . push (FIB [FIB . length - 1] + FIB [FIB . length - 2]); +} + +// +// Recursive function to find the sums. First argument is the target +// number, second argument is the index of smallest number which can +// be used. +// +function solutions (target, index = 0) { + let output = []; + // + // Iterate over the list of Fibonacci numbers, looking for + // candidates. We're starting with the given index. + // + for (let i = index; i < FIB . length; i ++) { + let fib = FIB [i]; + if (fib > target) { + // + // If the candidate is larger than the target number, + // we can stop looking, as each subsequent number will + // be larger. + // + break; + } + if (fib == target) { + // + // If the candidate is equal to the target number, + // then it's a trivial solution (a sum of 1 number). + // Add it to the list of possibilities, and stop + // searching. + // + output . push ([fib]); + break; + } + else { + // + // Find solutions for the difference between the + // candidate and the target number, with the restriction + // that each number in that sum is larger than the numbers + // used so far. + // + let rec_solutions = solutions (target - fib, i + 1); + + // + // For each solution found in recursion, we have a solution + // for this call, by adding the candidate to it. + // + for (let j = 0; j < rec_solutions . length; j ++) { + output . push ([fib] . concat (rec_solutions [j])); + } + } + } + return output; +} + +// +// Find the solutions +// +let sols = solutions (N); + +// +// And print the results +// +for (let i = 0; i < sols . length; i ++) { + console . log (sols [i] . join (" + ") + " = " + N); +} diff --git a/challenge-077/abigail/node/ch-2.js b/challenge-077/abigail/node/ch-2.js new file mode 100644 index 0000000000..ee04d5c605 --- /dev/null +++ b/challenge-077/abigail/node/ch-2.js @@ -0,0 +1,60 @@ +// +// Exercise: +// You are given m x n character matrix consists of O and X only. +// Write a script to count the total number of X surrounded by O only. +// Print 0 if none found. +// + +// +// Read in the board: +// - Read STDIN +// - Split by newlines +// - Split each line on spaces +// - Map an 'X' to a 1, 'O' to a 0. +// - Add a 0 to the beginning and end of each line. +// +let fs = require ("fs"); +let board = fs . readFileSync (0) . toString () . trim () . split ("\n") . + map (line => (line . split (" ")) . map (c => c == "X" ? 1 : 0)) . + map (line => ([0] . concat (line) . concat ([0]))); + +// +// Add top and bottom with 0s +// +board . push (board [0] . map (x => 0)); +board . unshift (board [0] . map (x => 0)); + +let count = 0; + +// +// Iterate over the cells of the board board, skipping cells on the edge +// (as we added them). For each 1, check the 8 cells surrounding the cell +// (this will never be outside of the board). If one of the neighbouring +// cells is a 1, move on the next cell. If no neighbouring cell is 1, +// we add 1 to the count. +// +for (let x = 1; x < board . length - 1; x ++) { + ELEMENT: + for (let y = 1; y < board [x] . length - 1; y ++) { + if (!board [x] [y]) { + continue; + } + for (let dx = -1; dx <= 1; dx ++) { + for (let dy = -1; dy <= 1; dy ++) { + if (dx == 0 && dy == 0) { + continue; + } + if (board [x + dx] [y + dy]) { + continue ELEMENT; + } + } + } + count ++; + } +} + + +// +// Print the results. +// +console . log (count); diff --git a/challenge-077/abigail/perl/ch-1.pl b/challenge-077/abigail/perl/ch-1.pl new file mode 100644 index 0000000000..b39028c5b9 --- /dev/null +++ b/challenge-077/abigail/perl/ch-1.pl @@ -0,0 +1,63 @@ +#!/opt/perl/bin/perl + +# +# Exercise: +# You are given a positive integer $N. +# Write a script to find out all possible combination of Fibonacci +# Numbers required to get $N on addition. +# +# You are NOT allowed to repeat a number. Print 0 if none found. +# + +# +# Note: +# The "Print 0 if none found." is irrelevant. There is always at +# least one way to write any positive integer as a sum of distinct +# Fibonacci Numbers. (Zeckendorf's theorem states: "very positive +# integer can be represented uniquely as the sum of one or more +# distinct Fibonacci numbers in such a way that the sum does not +# include any two consecutive Fibonacci numbers") +# + +use 5.032; + +use strict; +use warnings; +no warnings 'syntax'; + +use experimental 'signatures'; +use experimental 'lexical_subs'; + +chomp (my $N = <>); + +# +# Create a list of Fibonacci Numbers up to $N. We will start with (1, 2), +# skipping the first two numbers 0 and 1. 0 doesn't add anything, and +# we cannot duplicate numbers, so we just need one 1. +# +my @FIB = (1, 2); +while ($FIB [-1] + $FIB [-2] <= $N) { + push @FIB => $FIB [-1] + $FIB [-2]; +} + +sub solutions; + +# +# Create all solutions for number $target, with all Fibonnaci numbers +# having index $index or above. +# +sub solutions ($target, $index = 0) { + map { + my $fib = $FIB [$_]; + $target < $fib ? () + : $target == $fib ? [$target] + : map {[$fib, @$_]} solutions ($target - $fib, $_ + 1) + } $index .. @FIB - 1; +} + +my @all = solutions $N; + +local $" = " + "; +say "@$_ = $N" for @all; + +__END__ diff --git a/challenge-077/abigail/perl/ch-2.pl b/challenge-077/abigail/perl/ch-2.pl new file mode 100644 index 0000000000..784f4cd662 --- /dev/null +++ b/challenge-077/abigail/perl/ch-2.pl @@ -0,0 +1,56 @@ +#!/opt/perl/bin/perl + +# +# Exercise: +# You are given m x n character matrix consists of O and X only. +# Write a script to count the total number of X surrounded by O only. +# Print 0 if none found. +# + +use 5.032; + +use strict; +use warnings; +no warnings 'syntax'; + +use experimental 'signatures'; +use experimental 'lexical_subs'; + +# +# Read in the board. Use 1 for an X, and 0 for an 0. Add a band +# of 0's around the board. +# + +my @board = map {[0, map ({/O/ ? 0 : 1} /[OX]/g), 0]} <>; +push @board => [(0) x @{$board [0]}]; +unshift @board => [(0) x @{$board [0]}]; + +my $count = 0; + +# +# Iterate over the cells of the board board, skipping cells on the edge +# (as we added them). For each 1, check the 8 cells surrounding the cell +# (this will never be outside of the board). If one of the neighbouring +# cells is a 1, move on the next cell. If no neighbouring cell is 1, +# we add 1 to the count. +# +for (my $x = 1; $x < @board - 1; $x ++) { + ELEMENT: + for (my $y = 1; $y < @{$board [$x]} - 1; $y ++) { + next unless $board [$x] [$y]; + foreach my $dx (-1 .. 1) { + foreach my $dy (-1 .. 1) { + next unless $dx || $dy; + next ELEMENT if $board [$x + $dx] [$y + $dy]; + } + } + $count ++; + } +} + +# +# Print solution. +# +say $count; + +__END__ diff --git a/challenge-077/abigail/test.pl b/challenge-077/abigail/test.pl new file mode 100755 index 0000000000..115e570c62 --- /dev/null +++ b/challenge-077/abigail/test.pl @@ -0,0 +1,44 @@ +#!/opt/perl/bin/perl + +# +# Test the solutions. Either call it with the directory name you +# want to test in, or call it as "../test.pl" from within the directory. +# + +use 5.032; + +use strict; +use warnings; +no warnings 'syntax'; + +chdir shift if @ARGV; + +use experimental 'signatures'; + +use Test::More; + +my %languages = ( + Perl => ["/opt/perl/bin/perl" => 'pl'], + JavaScript => ["/usr/local/bin/node" => 'js'], +); + + +my @inputs = <input*>; + +foreach my $language (sort keys %languages) { + my ($exe, $ext) = @{$languages {$language}}; + next unless -r "solution.$ext"; + subtest $language => sub { + foreach my $input (@inputs) { + my $output_exp = ($input =~ s/input/output/r) . ".exp"; + my $exp = `cat $output_exp`; + my $got = `$exe ./solution.$ext < $input`; + is $got, $exp, $input; + } + } +} + +done_testing; + + +__END__ diff --git a/challenge-077/cheok-yin-fung/perl/ch-2.pl b/challenge-077/cheok-yin-fung/perl/ch-2.pl index e5b4026bed..69b9ee0cf3 100644 --- a/challenge-077/cheok-yin-fung/perl/ch-2.pl +++ b/challenge-077/cheok-yin-fung/perl/ch-2.pl @@ -50,9 +50,10 @@ print_matrix(\@matrix); sub detect { my $segment = join "", @_; + $segment =~ s/XX/II/g; $segment =~ s/XI/II/g; $segment =~ s/IX/II/g; - $segment =~ s/XX/II/g; +# $segment =~ s/XX/II/g; modify after deadline return split //, $segment; } diff --git a/challenge-077/mohammad-anwar/blog1.txt b/challenge-077/mohammad-anwar/blog1.txt new file mode 100644 index 0000000000..dcb1ac636c --- /dev/null +++ b/challenge-077/mohammad-anwar/blog1.txt @@ -0,0 +1 @@ +https://www.youtube.com/watch?v=dgz4T4GwKxQ |