diff options
Diffstat (limited to 'challenge-075')
23 files changed, 824 insertions, 1 deletions
diff --git a/challenge-075/abigail/README b/challenge-075/abigail/README deleted file mode 100644 index 5f0d73ae16..0000000000 --- a/challenge-075/abigail/README +++ /dev/null @@ -1 +0,0 @@ -Solution by Abigail diff --git a/challenge-075/abigail/README.md b/challenge-075/abigail/README.md new file mode 100644 index 0000000000..0e2ef80c9d --- /dev/null +++ b/challenge-075/abigail/README.md @@ -0,0 +1,89 @@ +# Solutions by Abigail + +## [Coins Sum](https://theweeklychallenge.org/blog/perl-weekly-challenge-075/#task-1--coins-sum) + +> You are given a set of coins `@C`, assuming you have infinite amount +> of each coin in the set. +> +> Write a script to find how many ways you make sum `$S` using the coins +> from the set `@C`. + +### Example +~~~~ +Input: + @C = (1, 2, 4) + $S = 6 + +Output: 6 +There are 6 possible ways to make sum 6. +a) (1, 1, 1, 1, 1, 1) +b) (1, 1, 1, 1, 2) +c) (1, 1, 2, 2) +d) (1, 1, 4) +e) (2, 2, 2) +f) (2, 4) +~~~~ + +### Solutions +* [AWK](awk/ch-1.awk) +* [Bash](bash/ch-1.sh) +* [C](c/ch-1.c) +* [Lua](lua/ch-1.lua) +* [Node.js](node/ch-1.js) +* [Perl](perl/ch-1.pl) +* [Python](python/ch-1.py) +* [Ruby](ruby/ch-1.rb) + + +## [Largest Rectangle Histogram](https://theweeklychallenge.org/blog/perl-weekly-challenge-075/#task-2--largest-rectangle-histogram) + +> You are given an array of positive numbers @A. +> +> Write a script to find the largest rectangle histogram created by +> the given array.<br> +> *BONUS: Try to print the histogram as shown in the example, if possible.* + +### Examples +#### Example 1 +~~~~ +Input: @A = (2, 1, 4, 5, 3, 7) + + 7 # + 6 # + 5 # # + 4 # # # + 3 # # # # + 2 # # # # # + 1 # # # # # # + _ _ _ _ _ _ _ + 2 1 4 5 3 7 +~~~~ +Looking at the above histogram, the largest rectangle `(4 x 3)` +is formed by columns `(4, 5, 3 and 7)`. + +#### Example 2 +~~~~ +Input: @A = (3, 2, 3, 5, 7, 5) + + 7 # + 6 # + 5 # # # + 4 # # # + 3 # # # # # + 2 # # # # # # + 1 # # # # # # + _ _ _ _ _ _ _ + 3 2 3 5 7 5 +~~~~ +Looking at the above histogram, the largest rectangle `(3 x 5)` +is formed by columns `(5, 7 and 5)`. + +### Solutions +* [AWK](awk/ch-2.awk) +* [Bash](bash/ch-2.sh) +* [C](c/ch-2.c) +* [Lua](lua/ch-2.lua) +* [Node.js](node/ch-2.js) +* [Perl](perl/ch-2.pl) +* [Python](python/ch-2.py) +* [Ruby](ruby/ch-1.rb) diff --git a/challenge-075/abigail/awk/ch-1.awk b/challenge-075/abigail/awk/ch-1.awk new file mode 100644 index 0000000000..59be0ed92f --- /dev/null +++ b/challenge-075/abigail/awk/ch-1.awk @@ -0,0 +1,32 @@ +#!/usr/bin/awk + +# +# See ../README.md +# + +# +# Run as: awk -f ch-1.awk < input-file +# + +function possibilities (target, from, to, sum, i) { + if (target == 0) {return 1} + if (target < 0 || from > to) {return 0} + + sum = 0 + + for (i = 0; i * coins [from] <= target; i ++) { + sum += possibilities(target - i * coins [from], from + 1, to) + } + + return sum +} + +{ + for (i = 2; i <= NF; i ++) { + coins [i] = $i + } + + print (possibilities($1, 2, NF)) +} + + diff --git a/challenge-075/abigail/awk/ch-2.awk b/challenge-075/abigail/awk/ch-2.awk new file mode 100644 index 0000000000..87458981ce --- /dev/null +++ b/challenge-075/abigail/awk/ch-2.awk @@ -0,0 +1,54 @@ +#!/usr/bin/awk + +# +# See ../README.md +# + +# +# Run as: awk -f ch-2.awk < input-file +# + + +{ + max_height = 0 + for (i = 1; i <= NF; i ++) { + height [i] = $i + if (height [i] > max_height) { + max_height = height [i] + } + } + + max_area = 0; + + # + # For each height, determine the maximum rectangle + # which fits -- which means we need to maximum amount + # of consequitive columns which are at least that heigh. + # + + for (h = 1; h <= max_height; h ++) { + max = 0; + cur = 0; + for (i = 1; i <= NF; i ++) { + if (height [i] >= h) { + cur ++ + } + else { + if (cur > max) { + max = cur + } + cur = 0 + } + } + if (cur > max) { + max = cur + } + + area = max * h + if (area > max_area) { + max_area = area + } + } + + print (max_area) +} diff --git a/challenge-075/abigail/bash/ch-1.sh b/challenge-075/abigail/bash/ch-1.sh new file mode 100644 index 0000000000..8ece29a51a --- /dev/null +++ b/challenge-075/abigail/bash/ch-1.sh @@ -0,0 +1,43 @@ +#!/bin/sh + +# +# See ../README.md +# + +# +# Run as: bash ch-1.sh < input-file +# + +set -f + +function possibilities () { + local target=$1 + local from=$2 + local to=$3 + local i=0 + + if ((target == 0)) + then result=1 + return + fi + + if (((target < 0) || (from > to))) + then result=0 + return + fi + + local sum=0 + for ((i = 0; i * ${coins[from]} <= target; i ++)) + do possibilities $((target - i * ${coins[from]})) $((from + 1)) $to + ((sum += result)) + done + + ((result = sum)) + return +} + +while read -a coins +do target=${coins[0]} + possibilities $target 1 $((${#coins[@]} - 1)) + echo $result +done diff --git a/challenge-075/abigail/bash/ch-2.sh b/challenge-075/abigail/bash/ch-2.sh new file mode 100644 index 0000000000..e52994e66e --- /dev/null +++ b/challenge-075/abigail/bash/ch-2.sh @@ -0,0 +1,45 @@ +#!/bin/sh + +# +# See ../README.md +# + +# +# Run as: bash ch-2.sh < input-file +# + +set -f + +while read -a heights +do ((max_height = 0)) + for ((i = 0; i < ${#heights[@]}; i ++)) + do if ((max_height < ${heights[$i]})) + then ((max_height = ${heights[$i]})) + fi + done + + ((max_area = 0)) + for ((h = 1; h <= max_height; h ++)) + do ((max = 0)) + ((cur = 0)) + for ((i = 0; i < ${#heights[@]}; i ++)) + do if ((${heights[$i]} >= h)) + then ((cur ++)) + else if ((cur > max)) + then ((max = cur)) + fi + ((cur = 0)) + fi + done + if ((cur > max)) + then ((max = cur)) + fi + + ((area = max * h)) + if ((max_area < area)) + then ((max_area = area)) + fi + done + + echo $max_area +done diff --git a/challenge-075/abigail/c/ch-1.c b/challenge-075/abigail/c/ch-1.c new file mode 100644 index 0000000000..ccf201b68a --- /dev/null +++ b/challenge-075/abigail/c/ch-1.c @@ -0,0 +1,65 @@ +# include <stdlib.h> +# include <stdio.h> +# include <string.h> + +/* + * See ../README.md + */ + +/* + * Run as: cc -o ch-1.o ch-1.c; ./ch-1.o < input-file + */ + +int possibilities (int target, int * coins, int from, int to) { + if (target == 0) { + return 1; + } + if (target < 0 || from > to) { + return 0; + } + + int sum = 0; + for (int i = 0; i * coins [from] <= target; i ++) { + sum += possibilities (target - i * coins [from], coins, from + 1, to); + } + + return sum; +} + +int main (void) { + char * line = NULL; + size_t len = 0; + size_t str_len; + + while ((str_len = getline (&line, &len, stdin)) != -1) { + int coin; + int n; + int offset = 0; + int c = 0; + while (sscanf (line + offset, "%d%n", &coin, &n) == 1) { + offset += n; + c ++; + } + /* + * Now c will be the amount of integers on the line. + * We need this to determine the size of the to be + * allocated array + */ + int * coins; + if ((coins = (int *) malloc (c * sizeof (int))) == NULL) { + perror ("Malloc failed"); + exit (1); + } + offset = 0; + c = 0; + while (sscanf (line + offset, "%d%n", &coin, &n) == 1) { + offset += n; + coins [c ++] = coin; /* If c == 0, it's our target */ + } + + printf ("%d\n", possibilities (coins [0], coins, 1, c - 1)); + } + free (line); + + return (0); +} diff --git a/challenge-075/abigail/c/ch-2.c b/challenge-075/abigail/c/ch-2.c new file mode 100644 index 0000000000..5fda685e14 --- /dev/null +++ b/challenge-075/abigail/c/ch-2.c @@ -0,0 +1,84 @@ +# include <stdlib.h> +# include <stdio.h> +# include <string.h> + +/* + * See ../README.md + */ + +/* + * Run as: cc -o ch-2.o ch-2.c; ./ch-2.o < input-file + */ + +int main (void) { + char * line = NULL; + size_t len = 0; + size_t str_len; + + while ((str_len = getline (&line, &len, stdin)) != -1) { + int height; + int n; + int offset = 0; + int c = 0; + while (sscanf (line + offset, "%d%n", &height, &n) == 1) { + offset += n; + c ++; + } + /* + * Now c will be the amount of integers on the line. + * We need this to determine the size of the to be + * allocated array + */ + int * heights; + if ((heights = (int *) malloc (c * sizeof (int))) == NULL) { + perror ("Malloc failed"); + exit (1); + } + offset = 0; + c = 0; + int max_height = 0; + while (sscanf (line + offset, "%d%n", &height, &n) == 1) { + offset += n; + heights [c ++] = height; + if (max_height < height) { + max_height = height; + } + } + + /* + * For each height, find the longest sequence of consecutive + * columns with at least that height, and calculate the + * rectangle with that height. Remember the largest. + */ + + int max_area = 0; + for (int h = 1; h <= max_height; h ++) { + int cur = 0; + int max = 0; + for (int i = 0; i < c; i ++) { + if (heights [i] >= h) { + cur ++; + } + else { + if (max < cur) { + max = cur; + } + cur = 0; + } + } + if (max < cur) { + max = cur; + } + + int area = max * h; + if (max_area < area) { + max_area = area; + } + } + + printf ("%d\n", max_area); + } + free (line); + + return (0); +} diff --git a/challenge-075/abigail/lua/ch-1.lua b/challenge-075/abigail/lua/ch-1.lua new file mode 100644 index 0000000000..6d46469469 --- /dev/null +++ b/challenge-075/abigail/lua/ch-1.lua @@ -0,0 +1,43 @@ +#!/opt/local/bin/lua + +-- +-- See ../README.md +-- + +-- +-- Run as: lua ch-1.lua < input-file +-- + +function possibilities (target, coins, from, to) + if target == 0 then + return 1 + end + if target < 0 or from > to then + return 0 + end + + local sum = 0 + + for i = 0, math . floor (target / coins [from]) do + sum = sum + possibilities (target - i * coins [from], + coins, from + 1, to) + end + + return sum +end + + +for line in io . lines () do + local target + local coins = {} + local i + for i in line : gmatch ("%d+") do + if target == nil then + target = tonumber (i) + else + table . insert (coins, tonumber (i)) + end + end + print (possibilities (target, coins, 1, #coins)) + +end diff --git a/challenge-075/abigail/lua/ch-2.lua b/challenge-075/abigail/lua/ch-2.lua new file mode 100644 index 0000000000..0765ff81b1 --- /dev/null +++ b/challenge-075/abigail/lua/ch-2.lua @@ -0,0 +1,49 @@ +#!/opt/local/bin/lua + +-- +-- See ../README.md +-- + +-- +-- Run as: lua ch-2.lua < input-file +-- + +for line in io . lines () do + local heights = {} + local h, i + local max_height = 0 + for h in line : gmatch ("%d+") do + h = tonumber (h) + table . insert (heights, h) + if max_height < h then + max_height = h + end + end + + local max_area = 0 + for h = 1, max_height do + local max = 0 + local cur = 0 + for i = 1, #heights do + if heights [i] >= h then + cur = cur + 1 + else + if max < cur then + max = cur + end + cur = 0 + end + end + + if max < cur then + max = cur + end + + local area = max * h + if max_area < area then + max_area = area + end + end + + print (max_area) +end diff --git a/challenge-075/abigail/node/ch-1.js b/challenge-075/abigail/node/ch-1.js new file mode 100644 index 0000000000..99ea6b661e --- /dev/null +++ b/challenge-075/abigail/node/ch-1.js @@ -0,0 +1,33 @@ +#!/usr/local/bin/node + +// +// See ../README.md +// + +// +// Run as: node ch-1.js < input-file +// + +function possibilities (target, coins, from, to) { + if (target == 0) { + return (1) + } + if (target < 0 || from > to) { + return (0) + } + + let sum = 0 + let i + for (i = 0; i * coins [from] <= target; i ++) { + sum += possibilities (target - i * coins [from], coins, from + 1, to) + } + + return sum +} + + require ('readline') +. createInterface ({input: process . stdin}) +. on ('line', line => { + let coins = line . split (' ') . map (_ => +_) + console . log (possibilities (coins [0], coins, 1, coins . length - 1)) +}) diff --git a/challenge-075/abigail/node/ch-2.js b/challenge-075/abigail/node/ch-2.js new file mode 100644 index 0000000000..64b04898ad --- /dev/null +++ b/challenge-075/abigail/node/ch-2.js @@ -0,0 +1,43 @@ +#!/usr/local/bin/node + +// +// See ../README.md +// + +// +// Run as: node ch-2.js < input-file +// + + require ('readline') +. createInterface ({input: process . stdin}) +. on ('line', line => { + let heights = line . split (" ") . map (_ => +_) + let max_height = Math . max (... heights) + + let max_area = 0 + let i, h + for (h = 1; h <= max_height; h ++) { + let cur = 0 + let max = 0 + for (i = 0; i < heights . length; i ++) { + if (heights [i] >= h) { + cur ++ + } + else { + if (max < cur) { + max = cur + } + cur = 0 + } + } + if (max < cur) { + max = cur + } + + let area = max * h + if (max_area < area) { + max_area = area + } + } + console . log (max_area) +}) diff --git a/challenge-075/abigail/perl/ch-1.pl b/challenge-075/abigail/perl/ch-1.pl new file mode 100644 index 0000000000..ba8ceb4938 --- /dev/null +++ b/challenge-075/abigail/perl/ch-1.pl @@ -0,0 +1,31 @@ +#!/opt/perl/bin/perl + +use 5.032; + +use strict; +use warnings; +no warnings 'syntax'; + +use experimental 'signatures'; +use experimental 'lexical_subs'; + +# +# See ../README.md +# + +# +# Run as: perl ch-1.pl < input-file +# + +use List::Util qw [sum]; + + +sub possibilities ($target, @coins) { + return $target == 0 ? 1 + : $target < 0 || !@coins ? 0 + : sum map {possibilities ($target - $_ * $coins [0], + @coins [1 .. $#coins])} + 0 .. int ($target / $coins [0]); +} + +say possibilities /[0-9]+/g while <>; diff --git a/challenge-075/abigail/perl/ch-2.pl b/challenge-075/abigail/perl/ch-2.pl new file mode 100644 index 0000000000..c74dbb2616 --- /dev/null +++ b/challenge-075/abigail/perl/ch-2.pl @@ -0,0 +1,62 @@ +#!/opt/perl/bin/perl + +use 5.032; + +use strict; +use warnings; +no warnings 'syntax'; + +use experimental 'signatures'; +use experimental 'lexical_subs'; + +# +# See ../README.md +# + +# +# Run as: perl ch-2.pl < input-file +# + +while (<>) { + my @a = split; + + # + # Get all the different heights. Note that the largest + # rectangle will have a height which is equal to the + # height of at least one column. + # + my %seen; + my @heights = sort {$a <=> $b} grep {!$seen {$_} ++} @a; + + my $max_area = 0; + + foreach my $h (@heights) { + # + # Find the longest amount of sequentical columns with + # at least that height. + # + my $max = 0; + my $cur = 0; + foreach my $ch (@a) { + if ($ch >= $h) { + $cur ++ + } + else { + $max = $cur if $cur > $max; + $cur = 0; + } + } + $max = $cur if $cur > $max; + + # + # Calculate the max area for a rectangle with height $h. + # + my $area = $max * $h; + + # + # Remember the max of all possible heights. + # + $max_area = $area if $area > $max_area; + } + say $max_area; +} diff --git a/challenge-075/abigail/python/ch-1.py b/challenge-075/abigail/python/ch-1.py new file mode 100644 index 0000000000..8b3ce4f9fb --- /dev/null +++ b/challenge-075/abigail/python/ch-1.py @@ -0,0 +1,29 @@ +#!/opt/local/bin/python + +# +# See ../README.md +# + +# +# Run as: python ch-1.py < input-file +# + +import fileinput + +def possibilities (target, coins, first, last): + if target == 0: + return 1 + + if target < 0 or first > last: + return 0 + + sum = 0 + for i in range (1 + int (target / coins [first])): + sum = sum + possibilities (target - i * coins [first], + coins, first + 1, last) + + return sum + +for line in fileinput . input (): + coins = list (map (lambda _: int (_), line . split (" "))) + print (possibilities (coins [0], coins, 1, len (coins) - 1)) diff --git a/challenge-075/abigail/python/ch-2.py b/challenge-075/abigail/python/ch-2.py new file mode 100644 index 0000000000..80045b335c --- /dev/null +++ b/challenge-075/abigail/python/ch-2.py @@ -0,0 +1,35 @@ +#!/opt/local/bin/python + +# +# See ../README.md +# + +# +# Run as: python ch-2.py < input-file +# + +import fileinput + +for line in fileinput . input (): + heights = list (map (lambda _: int (_), line . split (" "))) + max_height = max (heights) + + max_area = 0 + for h in range (1, max_height + 1): + xam = 0 # max clashes with function max() + cur = 0 + for i in range (0, len (heights)): + if heights [i] >= h: + cur = cur + 1 + else: + if xam < cur: + xam = cur + cur = 0 + if xam < cur: + xam = cur + + area = xam * h + if max_area < area: + max_area = area + + print (max_area) diff --git a/challenge-075/abigail/ruby/ch-1.rb b/challenge-075/abigail/ruby/ch-1.rb new file mode 100644 index 0000000000..be67045a1a --- /dev/null +++ b/challenge-075/abigail/ruby/ch-1.rb @@ -0,0 +1,33 @@ +#!/usr/bin/ruby + +# +# See ../README.md +# + +# +# Run as: ruby ch-1.rb < input-file +# + +def possibilities (target, coins) + return 1 if target == 0 + return 0 if target < 0 || coins . length == 0 + + sum = 0 + for i in 0 .. (target / coins [0]) . to_i do + sum += possibilities(target - i * coins [0], coins [1 .. -1]) + end + + return sum +end + +ARGF . each_line do + |line| + coins = line . split . map do + |c| + c . to_i + end + + target = coins . shift + + puts (possibilities(target, coins)) +end diff --git a/challenge-075/abigail/ruby/ch-2.rb b/challenge-075/abigail/ruby/ch-2.rb new file mode 100644 index 0000000000..757184d399 --- /dev/null +++ b/challenge-075/abigail/ruby/ch-2.rb @@ -0,0 +1,45 @@ +#!/usr/bin/ruby + +# +# See ../README.md +# + +# +# Run as: ruby ch-2.rb < input-file +# + +ARGF . each_line do + |line| + heights = line . split . map do + |h| + h . to_i + end + + max_height = heights . max + + max_area = 0 + for h in 1 .. max_height do + max = 0 + cur = 0 + heights . map do + |height| + if height >= h + cur += 1 + else + if max < cur + max = cur + end + cur = 0 + end + end + if max < cur + max = cur + end + + area = max * h + if max_area < area + max_area = area + end + end + puts (max_area) +end diff --git a/challenge-075/abigail/t/ctest.ini b/challenge-075/abigail/t/ctest.ini new file mode 100644 index 0000000000..0ae9d07567 --- /dev/null +++ b/challenge-075/abigail/t/ctest.ini @@ -0,0 +1,3 @@ +[names]
+1-1 = Given example
+2-1 = Given examples
diff --git a/challenge-075/abigail/t/input-1-1 b/challenge-075/abigail/t/input-1-1 new file mode 100644 index 0000000000..39f0c0749c --- /dev/null +++ b/challenge-075/abigail/t/input-1-1 @@ -0,0 +1 @@ +6 1 2 4 diff --git a/challenge-075/abigail/t/input-2-1 b/challenge-075/abigail/t/input-2-1 new file mode 100644 index 0000000000..c6863ac025 --- /dev/null +++ b/challenge-075/abigail/t/input-2-1 @@ -0,0 +1,2 @@ +2 1 4 5 3 7 +3 2 3 5 7 5 diff --git a/challenge-075/abigail/t/output-1-1.exp b/challenge-075/abigail/t/output-1-1.exp new file mode 100644 index 0000000000..1e8b314962 --- /dev/null +++ b/challenge-075/abigail/t/output-1-1.exp @@ -0,0 +1 @@ +6 diff --git a/challenge-075/abigail/t/output-2-1.exp b/challenge-075/abigail/t/output-2-1.exp new file mode 100644 index 0000000000..908cea31f9 --- /dev/null +++ b/challenge-075/abigail/t/output-2-1.exp @@ -0,0 +1,2 @@ +12 +15 |