diff options
| author | Mohammad S Anwar <mohammad.anwar@yahoo.com> | 2020-08-24 05:22:13 +0100 |
|---|---|---|
| committer | Mohammad S Anwar <mohammad.anwar@yahoo.com> | 2020-08-24 05:22:13 +0100 |
| commit | ab2670bec6b5a091b61b3d3a6f6211cefa68a425 (patch) | |
| tree | 61bf1c06364221c79bc413dfa4b6ddd678406052 | |
| parent | c1f276b80199b37dc4023c7f9a67fc29f899f5ab (diff) | |
| download | perlweeklychallenge-club-ab2670bec6b5a091b61b3d3a6f6211cefa68a425.tar.gz perlweeklychallenge-club-ab2670bec6b5a091b61b3d3a6f6211cefa68a425.tar.bz2 perlweeklychallenge-club-ab2670bec6b5a091b61b3d3a6f6211cefa68a425.zip | |
- Added solutions in Perl, Raku and Swift.
23 files changed, 3060 insertions, 1901 deletions
diff --git a/challenge-075/mohammad-anwar/perl/ch-1.pl b/challenge-075/mohammad-anwar/perl/ch-1.pl new file mode 100755 index 0000000000..7749fa9364 --- /dev/null +++ b/challenge-075/mohammad-anwar/perl/ch-1.pl @@ -0,0 +1,64 @@ +#!/usr/bin/perl + +# +# Perl Weekly Challenge - 075 +# +# Task #1: Coins Sum +# +# https://perlweeklychallenge.org/blog/perl-weekly-challenge-075 +# + +use strict; +use warnings; + +my $COINS = $ARGV[0] || "1, 2, 4"; +my $SUM = $ARGV[1] || 6; + +print "Possible ways to achieve the target: ", + coins_sum(prepare($COINS), $SUM), "\n"; + +# +# +# METHODS + +sub coins_sum { + my ($coins, $sum) = @_; + + my $size = $#$coins; + return 0 if ($size == -1 || $sum <= 0); + + my $matrix; + + # Sum of 0 can be achieved in one possible way. + $matrix->[$_][0] = 1 for (0 .. $size+1); + + foreach my $i (0 .. $size) { + + foreach my $j (1 .. $sum) { + + my $include_current = 0; + my $exclude_current = 0; + + if ($coins->[$i] <= $j) { + $include_current = $matrix->[$i][$j - $coins->[$i]]; + } + + if ($i > 0) { + $exclude_current = $matrix->[$i - 1][$j]; + } + + $matrix->[$i][$j] = $include_current + $exclude_current; + } + } + + return $matrix->[$size][$sum]; +} + +sub prepare { + my ($coins) = @_; + + if (defined $coins) { + $coins =~ s/\s//g; + return [ split /\,/, $coins ]; + } +} diff --git a/challenge-075/mohammad-anwar/perl/ch-1.t b/challenge-075/mohammad-anwar/perl/ch-1.t new file mode 100755 index 0000000000..c2d32443b5 --- /dev/null +++ b/challenge-075/mohammad-anwar/perl/ch-1.t @@ -0,0 +1,67 @@ +#!/usr/bin/perl + +# +# Perl Weekly Challenge - 075 +# +# Task #1: Coins Sum +# +# https://perlweeklychallenge.org/blog/perl-weekly-challenge-075 +# + +use strict; +use warnings; +use Test::More; + +is coins_sum(prepare("1, 2"), 5), 3; +is coins_sum(prepare("1, 2, 3"), 5), 5; +is coins_sum(prepare("1, 2, 4"), 6), 6; +is coins_sum(prepare("25, 10, 5"), 30), 5; +is coins_sum(prepare("9, 6, 5, 1"), 11), 6; + +done_testing; + +# +# +# METHODS + +sub coins_sum { + my ($coins, $sum) = @_; + + my $size = $#$coins; + return 0 if ($size == -1 || $sum <= 0); + + my $matrix; + + # Sum of 0 can be achieved in one possible way. + $matrix->[$_][0] = 1 for (0 .. $size+1); + + foreach my $i (0 .. $size) { + + foreach my $j (1 .. $sum) { + + my $include_current = 0; + my $exclude_current = 0; + + if ($coins->[$i] <= $j) { + $include_current = $matrix->[$i][$j - $coins->[$i]]; + } + + if ($i > 0) { + $exclude_current = $matrix->[$i - 1][$j]; + } + + $matrix->[$i][$j] = $include_current + $exclude_current; + } + } + + return $matrix->[$size][$sum]; +} + +sub prepare { + my ($coins) = @_; + + if (defined $coins) { + $coins =~ s/\s//g; + return [ split /\,/, $coins ]; + } +} diff --git a/challenge-075/mohammad-anwar/perl/ch-2.pl b/challenge-075/mohammad-anwar/perl/ch-2.pl new file mode 100755 index 0000000000..7749fa9364 --- /dev/null +++ b/challenge-075/mohammad-anwar/perl/ch-2.pl @@ -0,0 +1,64 @@ +#!/usr/bin/perl + +# +# Perl Weekly Challenge - 075 +# +# Task #1: Coins Sum +# +# https://perlweeklychallenge.org/blog/perl-weekly-challenge-075 +# + +use strict; +use warnings; + +my $COINS = $ARGV[0] || "1, 2, 4"; +my $SUM = $ARGV[1] || 6; + +print "Possible ways to achieve the target: ", + coins_sum(prepare($COINS), $SUM), "\n"; + +# +# +# METHODS + +sub coins_sum { + my ($coins, $sum) = @_; + + my $size = $#$coins; + return 0 if ($size == -1 || $sum <= 0); + + my $matrix; + + # Sum of 0 can be achieved in one possible way. + $matrix->[$_][0] = 1 for (0 .. $size+1); + + foreach my $i (0 .. $size) { + + foreach my $j (1 .. $sum) { + + my $include_current = 0; + my $exclude_current = 0; + + if ($coins->[$i] <= $j) { + $include_current = $matrix->[$i][$j - $coins->[$i]]; + } + + if ($i > 0) { + $exclude_current = $matrix->[$i - 1][$j]; + } + + $matrix->[$i][$j] = $include_current + $exclude_current; + } + } + + return $matrix->[$size][$sum]; +} + +sub prepare { + my ($coins) = @_; + + if (defined $coins) { + $coins =~ s/\s//g; + return [ split /\,/, $coins ]; + } +} diff --git a/challenge-075/mohammad-anwar/perl/ch-2.t b/challenge-075/mohammad-anwar/perl/ch-2.t new file mode 100755 index 0000000000..c2d32443b5 --- /dev/null +++ b/challenge-075/mohammad-anwar/perl/ch-2.t @@ -0,0 +1,67 @@ +#!/usr/bin/perl + +# +# Perl Weekly Challenge - 075 +# +# Task #1: Coins Sum +# +# https://perlweeklychallenge.org/blog/perl-weekly-challenge-075 +# + +use strict; +use warnings; +use Test::More; + +is coins_sum(prepare("1, 2"), 5), 3; +is coins_sum(prepare("1, 2, 3"), 5), 5; +is coins_sum(prepare("1, 2, 4"), 6), 6; +is coins_sum(prepare("25, 10, 5"), 30), 5; +is coins_sum(prepare("9, 6, 5, 1"), 11), 6; + +done_testing; + +# +# +# METHODS + +sub coins_sum { + my ($coins, $sum) = @_; + + my $size = $#$coins; + return 0 if ($size == -1 || $sum <= 0); + + my $matrix; + + # Sum of 0 can be achieved in one possible way. + $matrix->[$_][0] = 1 for (0 .. $size+1); + + foreach my $i (0 .. $size) { + + foreach my $j (1 .. $sum) { + + my $include_current = 0; + my $exclude_current = 0; + + if ($coins->[$i] <= $j) { + $include_current = $matrix->[$i][$j - $coins->[$i]]; + } + + if ($i > 0) { + $exclude_current = $matrix->[$i - 1][$j]; + } + + $matrix->[$i][$j] = $include_current + $exclude_current; + } + } + + return $matrix->[$size][$sum]; +} + +sub prepare { + my ($coins) = @_; + + if (defined $coins) { + $coins =~ s/\s//g; + return [ split /\,/, $coins ]; + } +} diff --git a/challenge-075/mohammad-anwar/raku/ch-1.raku b/challenge-075/mohammad-anwar/raku/ch-1.raku new file mode 100755 index 0000000000..f6bade8c9f --- /dev/null +++ b/challenge-075/mohammad-anwar/raku/ch-1.raku @@ -0,0 +1,55 @@ +#!/usr/bin/env raku + +# +# Perl Weekly Challenge - 075 +# +# Task #1: Coins Sum +# +# https://perlweeklychallenge.org/blog/perl-weekly-challenge-075 +# + +use v6.d; + +sub MAIN(Str :$COINS = "1, 2, 4", Int :$SUM = 6) { + say "Possible ways to achieve the target: " ~ + coins-sum($COINS, $SUM); +} + +sub coins-sum(Str $coins is copy, Int $sum) returns Int { + + die "ERROR: Invalid coins [$coins].\n" + unless $coins ~~ /^[\s?\-?\d\,?\s?]+$/; + + say "Coins: $coins"; + $coins ~~ s:g/\s//; + my $_coins = [ $coins.split(',').map({ .Int }) ]; + + my $size = $_coins.elems; + return 0 if ($size == 0 || $sum <= 0); + + my $matrix; + + # Sum of 0 can be achieved in one possible way. + $matrix.[$_][0] = 1 for (0 .. $size-1); + + for 0 .. $size-1 -> $i { + + for 1 .. $sum -> $j { + + my Int $include-current = 0; + my Int $exclude-current = 0; + + if $_coins.[$i] <= $j { + $include-current = $matrix.[$i][$j - $_coins.[$i]]; + } + + if $i > 0 { + $exclude-current = $matrix.[$i - 1][$j]; + } + + $matrix.[$i][$j] = $include-current + $exclude-current; + } + } + + return $matrix.[$size-1][$sum]; +} diff --git a/challenge-075/mohammad-anwar/raku/ch-1.t b/challenge-075/mohammad-anwar/raku/ch-1.t new file mode 100755 index 0000000000..e1a0e5b656 --- /dev/null +++ b/challenge-075/mohammad-anwar/raku/ch-1.t @@ -0,0 +1,57 @@ +#!/usr/bin/env raku + +# +# Perl Weekly Challenge - 075 +# +# Task #1: Coins Sum +# +# https://perlweeklychallenge.org/blog/perl-weekly-challenge-075 +# + +use Test; + +is coins-sum("1, 2", 5), 3, "Coins=[1, 2] Sum=5"; +is coins-sum("1, 2, 3", 5), 5, "Coins=[1, 2, 3] Sum=5"; +is coins-sum("1, 2, 4", 6), 6, "Coins=[1, 2, 4] Sum=6"; +is coins-sum("25, 10, 5", 30), 5, "Coins=[25, 10, 5] Sum=30"; +is coins-sum("9, 6, 5, 1", 11), 6, "Coins=[9, 6, 5, 1] Sum=6"; + +done-testing; + +sub coins-sum(Str $coins is copy, Int $sum) returns Int { + + die "ERROR: Invalid coins [$coins].\n" + unless $coins ~~ /^[\s?\-?\d\,?\s?]+$/; + + $coins ~~ s:g/\s//; + my $_coins = [ $coins.split(',').map({ .Int }) ]; + + my $size = $_coins.elems; + return 0 if ($size == 0 || $sum <= 0); + + my $matrix; + + # Sum of 0 can be achieved in one possible way. + $matrix.[$_][0] = 1 for (0 .. $size-1); + + for 0 .. $size-1 -> $i { + + for 1 .. $sum -> $j { + + my Int $include-current = 0; + my Int $exclude-current = 0; + + if $_coins.[$i] <= $j { + $include-current = $matrix.[$i][$j - $_coins.[$i]]; + } + + if $i > 0 { + $exclude-current = $matrix.[$i - 1][$j]; + } + + $matrix.[$i][$j] = $include-current + $exclude-current; + } + } + + return $matrix.[$size-1][$sum]; +} diff --git a/challenge-075/mohammad-anwar/raku/ch-2.raku b/challenge-075/mohammad-anwar/raku/ch-2.raku new file mode 100755 index 0000000000..024006d590 --- /dev/null +++ b/challenge-075/mohammad-anwar/raku/ch-2.raku @@ -0,0 +1,204 @@ +#!/usr/bin/env raku + +# +# Perl Weekly Challenge - 075 +# +# Task #2: Largest Rectangle Histogram +# +# https://perlweeklychallenge.org/blog/perl-weekly-challenge-075 +# + +use v6.d; + +sub MAIN(Str :$LIST = "2, 1, 4, 5, 3, 7") { + my $list = prepare($LIST); + chart($list).say; + say "Largest Rectangle Histogram: " ~ + largest-rectangle-histogram($list); +} + +# +# +# METHODS + +sub largest-rectangle-histogram($list where .all ~~ Int) returns Int { + + my Int $i = 0; + my Int $max = 0; + + for 0 .. $list.elems-1 -> $i { + + my (Int $left, Int $right) = (0, 0); + $left = go-left($i, $list) if $i > 0; + $right = go-right($i, $list) if $i < $list.elems; + + my $heights = $list.[$i - $left .. $i + $right]; + my $size = $heights.min * $heights.elems; + + $max = $size if $size > $max; + } + + return $max; +} + +sub go-left(Int $i is copy, $list where .all ~~ Int) returns Int { + + my $c = $list.[$i]; + my $j = 0; + while $i > 0 { + $i = $i - 1; + last if $list.[$i] < $c; + $j = $j + 1; + } + + return $j; +} + +sub go-right(Int $i is copy, $list where .all ~~ Int) returns Int { + + my $c = $list.[$i]; + my $j = 0; + while $i < $list.elems-1 { + $i += 1; + last if $list.[$i] < $c; + $j += 1; + } + + return $j; +} + +sub chart($list where .all ~~ Int) { + + my $max = $list.max; + my $chart = []; + my $row = 1; + for 1 .. $max -> $n { + my Str $data = ""; + for 0 .. $list.elems-1 -> $i { + if $row <= $list.[$i] { + $data ~= " #"; + } + else { + $data ~= " "; + } + } + + $row += 1; + + $chart.push: sprintf("%d%s", $n, $data); + } + + my (Str $histogram, Str $line, Str $size) = ("", "", " "); + $histogram = $chart.reverse.join("\n"); + $line ~= "_ " for 0 .. $list.elems; + $size ~= $list.join(" "); + + return ($histogram, $line, $size).join("\n"); +} + +sub prepare(Str $list is copy) { + + return unless $list.defined; + + die "ERROR: Invalid list [$list].\n" + unless $list ~~ /^[\s?\-?\d\,?\s?]+$/; + + $list ~~ s:g/\s//; + return [ $list.split(',').map({ .Int }) ]; +} + +=finish + +my $list = prepare($L); +print chart($list), "\n\n"; +print "Largest Rectangle Histogram: ", largest_rectangle_histogram($list), "\n"; + +# +# +# METHODS + +sub largest_rectangle_histogram { + my ($list) = @_; + + my $i = 0; + my $max = 0; + foreach my $n (@$list) { + + my ($left, $right) = (0, 0); + $left = go_left($i, $list) if ($i > 0); + $right = go_right($i, $list) if ($i <= $#$list); + + my @heights = (@$list)[$i - $left .. $i + $right]; + my $size = min(@heights) * @heights; + $max = $size if ($size > $max); + + $i++; + } + + return $max; +} + +sub go_left { + my ($i, $list) = @_; + + my $c = $list->[$i]; + my $j = 0; + while ($i > 0) { + $i--; + last if ($list->[$i] < $c); + $j++; + } + + return $j; +} + +sub go_right { + my ($i, $list) = @_; + + my $c = $list->[$i]; + my $j = 0; + while ($i < $#$list) { + $i++; + last if ($list->[$i] < $c); + $j++; + } + + return $j; +} + +sub chart { + my ($list) = @_; + + my $max = max(@$list); + my $chart = []; + my $row = 1; + foreach (1..$max) { + my $data = ""; + foreach my $i (0..$#$list) { + if ($row <= $list->[$i]) { + $data .= " #"; + } + else { + $data .= " "; + } + } + $row++; + push @$chart, sprintf("%d%s", $_, $data); + } + + my ($histogram, $line, $size) = ("", "", " "); + $histogram = join "\n", (reverse @$chart); + $line .= "_ " for (0..$#$list + 1); + $size .= join " ", @$list; + + return join "\n", $histogram, $line, $size; +} + +sub prepare { + my ($list) = @_; + + if (defined $list) { + $list =~ s/\s//g; + return [ split /\,/, $list ]; + } +} diff --git a/challenge-075/mohammad-anwar/raku/ch-2.t b/challenge-075/mohammad-anwar/raku/ch-2.t new file mode 100755 index 0000000000..b0e420faa3 --- /dev/null +++ b/challenge-075/mohammad-anwar/raku/ch-2.t @@ -0,0 +1,202 @@ +#!/usr/bin/env raku + +# +# Perl Weekly Challenge - 075 +# +# Task #2: Largest Rectangle Histogram +# +# https://perlweeklychallenge.org/blog/perl-weekly-challenge-075 +# + +use Test; + +is largest-rectangle-histogram(prepare("2, 1, 4, 5, 3, 7")), 12, "example 1"; +is largest-rectangle-histogram(prepare("3, 2, 3, 5, 7, 5")), 15, "example 2"; + +done-testing; + +# +# +# METHODS + +sub largest-rectangle-histogram($list where .all ~~ Int) returns Int { + + my Int $i = 0; + my Int $max = 0; + + for 0 .. $list.elems-1 -> $i { + + my (Int $left, Int $right) = (0, 0); + $left = go-left($i, $list) if $i > 0; + $right = go-right($i, $list) if $i < $list.elems; + + my $heights = $list.[$i - $left .. $i + $right]; + my $size = $heights.min * $heights.elems; + + $max = $size if $size > $max; + } + + return $max; +} + +sub go-left(Int $i is copy, $list where .all ~~ Int) returns Int { + + my $c = $list.[$i]; + my $j = 0; + while $i > 0 { + $i = $i - 1; + last if $list.[$i] < $c; + $j = $j + 1; + } + + return $j; +} + +sub go-right(Int $i is copy, $list where .all ~~ Int) returns Int { + + my $c = $list.[$i]; + my $j = 0; + while $i < $list.elems-1 { + $i += 1; + last if $list.[$i] < $c; + $j += 1; + } + + return $j; +} + +sub chart($list where .all ~~ Int) { + + my $max = $list.max; + my $chart = []; + my $row = 1; + for 1 .. $max -> $n { + my Str $data = ""; + for 0 .. $list.elems-1 -> $i { + if $row <= $list.[$i] { + $data ~= " #"; + } + else { + $data ~= " "; + } + } + + $row += 1; + + $chart.push: sprintf("%d%s", $n, $data); + } + + my (Str $histogram, Str $line, Str $size) = ("", "", " "); + $histogram = $chart.reverse.join("\n"); + $line ~= "_ " for 0 .. $list.elems; + $size ~= $list.join(" "); + + return ($histogram, $line, $size).join("\n"); +} + +sub prepare(Str $list is copy) { + + return unless $list.defined; + + die "ERROR: Invalid list [$list].\n" + unless $list ~~ /^[\s?\-?\d\,?\s?]+$/; + + $list ~~ s:g/\s//; + return [ $list.split(',').map({ .Int }) ]; +} + +=finish + +my $list = prepare($L); +print chart($list), "\n\n"; +print "Largest Rectangle Histogram: ", largest_rectangle_histogram($list), "\n"; + +# +# +# METHODS + +sub largest_rectangle_histogram { + my ($list) = @_; + + my $i = 0; + my $max = 0; + foreach my $n (@$list) { + + my ($left, $right) = (0, 0); + $left = go_left($i, $list) if ($i > 0); + $right = go_right($i, $list) if ($i <= $#$list); + + my @heights = (@$list)[$i - $left .. $i + $right]; + my $size = min(@heights) * @heights; + $max = $size if ($size > $max); + + $i++; + } + + return $max; +} + +sub go_left { + my ($i, $list) = @_; + + my $c = $list->[$i]; + my $j = 0; + while ($i > 0) { + $i--; + last if ($list->[$i] < $c); + $j++; + } + + return $j; +} + +sub go_right { + my ($i, $list) = @_; + + my $c = $list->[$i]; + my $j = 0; + while ($i < $#$list) { + $i++; + last if ($list->[$i] < $c); + $j++; + } + + return $j; +} + +sub chart { + my ($list) = @_; + + my $max = max(@$list); + my $chart = []; + my $row = 1; + foreach (1..$max) { + my $data = ""; + foreach my $i (0..$#$list) { + if ($row <= $list->[$i]) { + $data .= " #"; + } + else { + $data .= " "; + } + } + $row++; + push @$chart, sprintf("%d%s", $_, $data); + } + + my ($histogram, $line, $size) = ("", "", " "); + $histogram = join "\n", (reverse @$chart); + $line .= "_ " for (0..$#$list + 1); + $size .= join " ", @$list; + + return join "\n", $histogram, $line, $size; +} + +sub prepare { + my ($list) = @_; + + if (defined $list) { + $list =~ s/\s//g; + return [ split /\,/, $list ]; + } +} diff --git a/challenge-075/mohammad-anwar/swift/ch-1.swift b/challenge-075/mohammad-anwar/swift/ch-1.swift new file mode 100755 index 0000000000..016bfba8bf --- /dev/null +++ b/challenge-075/mohammad-anwar/swift/ch-1.swift @@ -0,0 +1,110 @@ +import Foundation + +/* + +Perl Weekly Challenge - 075 + +Task #1: Coins Sum + +https://perlweeklychallenge.org/blog/perl-weekly-challenge-075 + +*/ + +enum ParamError: Error { + case missingList + case missingSum + case invalidList + case invalidSum +} + +do { + let paramCount:Int = Int(CommandLine.argc) + + if paramCount <= 1 { + throw ParamError.missingList + } + + let list:String = CommandLine.arguments[1] + + if isValidList(list) { + + let sum:Int = Int(CommandLine.arguments[2])! + if sum > 0 { + let coins = list.components(separatedBy: ", ") + let size:Int = coins.count - 1 + + if size >= 1 { + + var matrix = [[Int]]() + + // Sum of 0 can be achieved in one possible way. + for _ in 0...size { + var row = [Int]() + row.append(1) + matrix.append(row) + } + + for i in 0...size { + + for j in 1...sum { + + var includeCurrent:Int = 0 + var excludeCurrent:Int = 0 + let currentCoin:Int = Int(coins[i])! + + if currentCoin <= j { + includeCurrent = matrix[i][j - currentCoin] + } + + if i > 0 { + excludeCurrent = matrix[i - 1][j] + } + + matrix[i].append(includeCurrent + excludeCurrent) + } + } + + print(matrix[size][sum]) + } + } + else { + throw ParamError.invalidSum + } + } + else { + throw ParamError.invalidList + } +} +catch ParamError.missingList { + print("Missing list.") +} +catch ParamError.missingSum { + print("Missinng sum.") +} +catch ParamError.invalidList { + print("Invalid list.") +} +catch ParamError.invalidSum { + print("Invalid Sum.") +} +catch let error { + print(error) +} + +// +// +// Function + +func isValidList(_ list:String) -> Bool { + + let pattern = "^[\\-?\\d\\,?\\s?]+$" + let regex = try! NSRegularExpression(pattern: pattern) + let range = NSRange(location: 0, length: list.utf16.count) + + if regex.firstMatch(in: list, options: [], range: range) != nil { + return true + } + else { + return false + } +} diff --git a/challenge-075/mohammad-anwar/swift/ch-2.swift b/challenge-075/mohammad-anwar/swift/ch-2.swift new file mode 100755 index 0000000000..cc38ea1a7c --- /dev/null +++ b/challenge-075/mohammad-anwar/swift/ch-2.swift @@ -0,0 +1,179 @@ +import Foundation + +/* + +Perl Weekly Challenge - 075 + +Task #2: Largest Rectangle Histogram + +https://perlweeklychallenge.org/blog/perl-weekly-challenge-075 + +*/ + +enum ParamError: Error { + case missingList + case invalidList +} + +do { + let paramCount:Int = Int(CommandLine.argc) + + if paramCount <= 1 { + throw ParamError.missingList + } + + let list:String = CommandLine.arguments[1] + + if isValidList(list) { + let heights:[Int] = prepare(list) + + print(chart(heights)) + print("\nLargest Rectangle Histogram: " + + String(largestRectangleHistogram(heights))) + } + else { + throw ParamError.invalidList + } +} +catch ParamError.missingList { + print("Missing list.") +} +catch ParamError.invalidList { + print("Invalid list.") +} +catch let error { + print(error) +} + +// +// +// Functions + +func isValidList(_ list:String) -> Bool { + + let pattern = "^[\\-?\\d\\,?\\s?]+$" + let regex = try! NSRegularExpression(pattern: pattern) + let range = NSRange(location: 0, length: list.utf16.count) + + if regex.firstMatch(in: list, options: [], range: range) != nil { + return true + } + else { + return false + } +} + +func largestRectangleHistogram(_ heights:[Int]) -> Int { + + var max:Int = 0 + + for i in 0...heights.count-1 { + + var left:Int = 0 + var right:Int = 0 + + if i > 0 { + left = goLeft(i, heights) + } + + if i <= heights.count-1 { + right = goRight(i, heights) + } + + let _heights:[Int] = Array(heights[i - left ... i + right]) + let size:Int = _heights.min()! * _heights.count + + if size > max { + max = size + } + + } + + return max +} + +func goLeft(_ i:Int, _ heights:[Int]) -> Int { + + let c:Int = heights[i] + var j:Int = 0 + var _i:Int = i + while _i > 0 { + _i -= 1 + if heights[_i] < c { + break + } + j += 1 + } + + return j +} + +func goRight(_ i:Int, _ heights:[Int]) -> Int { + + let c:Int = heights[i] + var j:Int = 0 + var _i:Int = i + while _i < heights.count-1 { + _i += 1 + if heights[_i] < c { + break + } + j += 1 + } + + return j + +} + +func chart(_ heights:[Int]) -> String { + + let max:Int = heights.max()! + var chart:[String] = [String]() + var row:Int = 1 + var line:String = "" + var size:String = " " + + for i in 1...max |
