diff options
| -rw-r--r-- | challenge-075/paulo-custodio/perl/ch-1.pl | 2 | ||||
| -rw-r--r-- | challenge-075/paulo-custodio/perl/ch-2.pl | 2 | ||||
| -rw-r--r-- | challenge-075/paulo-custodio/python/ch-1.py | 47 | ||||
| -rw-r--r-- | challenge-075/paulo-custodio/python/ch-2.py | 77 |
4 files changed, 126 insertions, 2 deletions
diff --git a/challenge-075/paulo-custodio/perl/ch-1.pl b/challenge-075/paulo-custodio/perl/ch-1.pl index 390a2f3bd1..680f944ca0 100644 --- a/challenge-075/paulo-custodio/perl/ch-1.pl +++ b/challenge-075/paulo-custodio/perl/ch-1.pl @@ -2,7 +2,7 @@ # Challenge 075 # -# TASK #1 › Coins Sum +# TASK #1 > Coins Sum # Submitted by: Mohammad S Anwar # You are given a set of coins @C, assuming you have infinite amount of each # coin in the set. diff --git a/challenge-075/paulo-custodio/perl/ch-2.pl b/challenge-075/paulo-custodio/perl/ch-2.pl index 4979fec29f..4549745fe2 100644 --- a/challenge-075/paulo-custodio/perl/ch-2.pl +++ b/challenge-075/paulo-custodio/perl/ch-2.pl @@ -2,7 +2,7 @@ # Challenge 075 # -# TASK #2 › Largest Rectangle Histogram +# TASK #2 > Largest Rectangle Histogram # Submitted by: Mohammad S Anwar # You are given an array of positive numbers @A. # diff --git a/challenge-075/paulo-custodio/python/ch-1.py b/challenge-075/paulo-custodio/python/ch-1.py new file mode 100644 index 0000000000..b86bde2230 --- /dev/null +++ b/challenge-075/paulo-custodio/python/ch-1.py @@ -0,0 +1,47 @@ +#!/usr/bin/env python3 + +# Challenge 075 +# +# TASK #1 > Coins Sum +# Submitted by: Mohammad S Anwar +# 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) + +import sys + +def show_coins(want, coins): + def show_coins1(want, have, coins, seen): + sum_have = sum(have) + if sum_have > want: + pass # busted sum + elif sum_have == want: + out = ", ".join([str(x) for x in sorted(have)]) + if not out in seen: + seen[out] = 1 + print(out) + else: + for coin in coins: + show_coins1(want, have+[coin], coins, seen) + + show_coins1(want, [], coins, {}) + +S = int(sys.argv[1]) +C = [int(x) for x in sys.argv[2:]] +show_coins(S, C) diff --git a/challenge-075/paulo-custodio/python/ch-2.py b/challenge-075/paulo-custodio/python/ch-2.py new file mode 100644 index 0000000000..f98bad8242 --- /dev/null +++ b/challenge-075/paulo-custodio/python/ch-2.py @@ -0,0 +1,77 @@ +#!/usr/bin/env python3 + +# Challenge 075 +# +# TASK #2 > Largest Rectangle Histogram +# Submitted by: Mohammad S Anwar +# You are given an array of positive numbers @A. +# +# Write a script to find the largest rectangle histogram created by the given +# array. +# +# BONUS: Try to print the histogram as shown in the example, if possible. +# +# 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). +# +# Output: 12 +# +# 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). +# +# Output: 15 + +import sys + +def make_histogram(a): + max_ = max(a) + hist = [[0 for c in range(len(a))] for r in range(max_)] + for c in range(len(a)): + for r in range(max_-1+1): + hist[r][c] = False if r >= a[c] else True + return hist + +def calc_max_area(hist): + max_area = 0 + for r0 in range(len(hist)): + for c0 in range(len(hist[0])): + if hist[r0][c0]: + for height in range(1, len(hist)-r0+1): + for width in range(1, len(hist[0])-c0+1): + all_ones = True + for r in range(r0, r0+height): + for c in range (c0, c0+width): + if not hist[r][c]: + all_ones = False; + if all_ones: + max_area = max(max_area, width*height) + return max_area + +n = [int(x) for x in sys.argv[1:]] +hist = make_histogram(n) +max_area = calc_max_area(hist) +print(max_area) |