diff options
54 files changed, 1062 insertions, 470 deletions
diff --git a/challenge-001/paulo-custodio/go.pl b/challenge-001/paulo-custodio/go.pl new file mode 100644 index 0000000000..97670bc755 --- /dev/null +++ b/challenge-001/paulo-custodio/go.pl @@ -0,0 +1,15 @@ +#!/usr/bin/env perl + +use Modern::Perl; +use Path::Tiny; + +@ARGV==1 && $ARGV[0]=~/^\d+$/ && $ARGV[0]>0 + or die "Usage: ",path($0)->basename," nr\n"; +my $nr = sprintf("%03d", $ARGV[0]); + +for my $dir (qw( ada awk basic c cpp d forth lua perl python t )) { + path("challenge-$nr/paulo-custodio/$dir")->mkpath; +} +path("challenge-$nr/paulo-custodio/README")->spew("Solution by Paulo Custodio\n"); +chdir("challenge-$nr/paulo-custodio"); +system("bash"); diff --git a/challenge-001/paulo-custodio/stats.pl b/challenge-001/paulo-custodio/stats.pl new file mode 100644 index 0000000000..1cb928a96a --- /dev/null +++ b/challenge-001/paulo-custodio/stats.pl @@ -0,0 +1,61 @@ +#!/usr/bin/env perl + +# show stats of challenge submissions + +use Modern::Perl; +use Path::Tiny; + +my $USER = "paulo-custodio"; + +our %LANG = ( + ada => 'adb', + awk => 'awk', + basic => 'bas', + bc => 'bc', + c => 'c', + cpp => 'cpp', + d => 'd', + forth => 'fs', + lua => 'lua', + perl => 'pl', + python => 'py', +); + +# collect data +my @sols; +for my $chall_dir (path(".")->children(qr/challenge-\d+/)) { + my($chall) = $chall_dir =~ /(\d+)/ or die; + $chall += 0; + + for my $lang (sort keys %LANG) { + my $dir = path($chall_dir, $USER, $lang); + next unless $dir->is_dir; + + my $sols = scalar($dir->children(qr/^ch[-_]\d\.$LANG{$lang}$/)); + + $sols[$chall]{$lang} = $sols; + } +} + +# output +for my $chall (1 .. $#sols) { + if (($chall) % 10 == 1) { + say "-" x 80; + print " " x 4; + for my $lang (sort keys %LANG) { + print " ", $lang; + } + say ""; + say "-" x 80; + } + + printf("%3d ", $chall); + for my $lang (sort keys %LANG) { + my $width = length($lang); + my $before = int(($width-1)/2); + my $after = $width - 1 - $before; + my $value = $sols[$chall]{$lang} || " "; + print " ", " " x $before, $value, " " x $after; + } + say ""; +} diff --git a/challenge-001/paulo-custodio/untabify.pl b/challenge-001/paulo-custodio/untabify.pl new file mode 100644 index 0000000000..9f3c5657d4 --- /dev/null +++ b/challenge-001/paulo-custodio/untabify.pl @@ -0,0 +1,30 @@ +#!/usr/bin/env perl + +# convert my code from 4-tabs to spaces + +use Modern::Perl; +use Path::Tiny; +use Text::Tabs; $Text::Tabs::tabstop = 4; + +for my $dir (<challenge-*/paulo-custodio>) { + my $iter = path($dir)->iterator({recurse=>1}); + while (defined(my $path = $iter->())) { + next unless $path->is_file; + next if $path =~ /~$/; # temp files + my $ext = ""; $path->basename =~ /(\.\w+)$/ and $ext = $1; + next if $ext eq "" || $ext =~ /\.(exe|o|obj|ali|ads)$/; # binaries + untabify($path); + } +} + +sub untabify { + my($file) = @_; + my $text = path($file)->slurp_raw; + my @lines = expand(map {s/\s+$//r} split(/\n/, $text)); + my $new_text = join "\n", (@lines, ""); + if ($text ne $new_text) { + path($file)->copy("$file~"); + say "Formatting $file"; + path($file)->spew_raw($new_text); + } +} diff --git a/challenge-121/paulo-custodio/perl/ch-2.pl b/challenge-121/paulo-custodio/perl/ch-2.pl index 4a45cb60ee..a2ae24043f 100644 --- a/challenge-121/paulo-custodio/perl/ch-2.pl +++ b/challenge-121/paulo-custodio/perl/ch-2.pl @@ -64,5 +64,3 @@ sub tour { } } } - - diff --git a/challenge-127/paulo-custodio/perl/ch-1.pl b/challenge-127/paulo-custodio/perl/ch-1.pl new file mode 100644 index 0000000000..dd8de28b85 --- /dev/null +++ b/challenge-127/paulo-custodio/perl/ch-1.pl @@ -0,0 +1,28 @@ +#!/usr/bin/env perl + +# Challenge 127 +# +# TASK #1 > Disjoint Sets +# Submitted by: Mohammad S Anwar +# You are given two sets with unique integers. +# +# Write a script to figure out if they are disjoint. +# +# The two sets are disjoint if they don’t have any common members. +# +# Example +# Input: @S1 = (1, 2, 5, 3, 4) +# @S2 = (4, 6, 7, 8, 9) +# Output: 0 as the given two sets have common member 4. +# +# Input: @S1 = (1, 3, 5, 7, 9) +# @S2 = (0, 2, 4, 6, 8) +# Output: 1 as the given two sets do not have common member. + +use Modern::Perl; +use Set::Intersection; + +my @s1 = split(' ', scalar(<>)); +my @s2 = split(' ', scalar(<>)); +my @intersection = get_intersection(\@s1, \@s2); +say @intersection ? 0 : 1; diff --git a/challenge-127/paulo-custodio/perl/ch-2.pl b/challenge-127/paulo-custodio/perl/ch-2.pl new file mode 100644 index 0000000000..3fefaca3e5 --- /dev/null +++ b/challenge-127/paulo-custodio/perl/ch-2.pl @@ -0,0 +1,85 @@ +#!/usr/bin/env perl + +# TASK #2 > Conflict Intervals +# Submitted by: Mohammad S Anwar +# You are given a list of intervals. +# +# Write a script to find out if the current interval conflicts with any of the +# previous intervals. +# +# Example +# Input: @Intervals = [ (1,4), (3,5), (6,8), (12, 13), (3,20) ] +# Output: [ (3,5), (3,20) ] +# +# - The 1st interval (1,4) do not have any previous intervals to compare +# with, so skip it. +# - The 2nd interval (3,5) does conflict with previous interval (1,4). +# - The 3rd interval (6,8) do not conflicts with any of the previous intervals +# (1,4) and (3,5), so skip it. +# - The 4th interval (12,13) again do not conflicts with any of the previous +# intervals (1,4), (3,5) and (6,8), so skip it. +# - The 5th interval (3,20) conflicts with the first interval (1,4). +# +# Input: @Intervals = [ (3,4), (5,7), (6,9), (10, 12), (13,15) ] +# Output: [ (6,9) ] +# +# - The 1st interval (3,4) do not have any previous intervals to compare +# with, so skip it. +# - The 2nd interval (5,7) do not conflicts with the previous interval (3,4), +# so skip it. +# - The 3rd interval (6,9) does conflict with one of the previous intervals (5,7). +# - The 4th interval (10,12) do not conflicts with any of the previous +# intervals (3,4), (5,7) and (6,9), so skip it. +# - The 5th interval (13,15) do not conflicts with any of the previous +# intervals (3,4), (5,7), (6,9) and (10,12), so skip it. + +use Modern::Perl; + +my @intervals = parse_intervals(@ARGV); +my @conflicts = find_conflicts(@intervals); +print_conflicts(@conflicts); + + +sub parse_intervals { + my(@in) = @_; + my @out; + while (@in) { + my($s, $e) = splice(@in, 0, 2); + push @out, [$s, $e]; + } + return @out; +} + +sub find_conflicts { + my(@intervals) = @_; + my @conflicts; + for my $i (1 .. $#intervals) { + for my $j (0 .. $i-1) { + my $i1s = $intervals[$i][0]; + my $i1e = $intervals[$i][1]; + my $i2s = $intervals[$j][0]; + my $i2e = $intervals[$j][1]; + if (($i1s >= $i2s && $i1s < $i2e) || + ($i1e >= $i2s && $i1e < $i2e) || + ($i1s < $i2s && $i1e >= $i2e)) { + push @conflicts, $intervals[$i]; + last; + } + } + } + + return @conflicts; +} + +sub print_conflicts { + my(@conflicts) = @_; + use Data::Dump 'dump'; + print "[ "; + my $sep = ""; + for (@conflicts) { + my($s, $e) = @$_; + print $sep,"($s,$e)"; + $sep = ", "; + } + print " ]\n"; +} diff --git a/challenge-127/paulo-custodio/t/test-1.yaml b/challenge-127/paulo-custodio/t/test-1.yaml new file mode 100644 index 0000000000..be7529e7e4 --- /dev/null +++ b/challenge-127/paulo-custodio/t/test-1.yaml @@ -0,0 +1,14 @@ +- setup: + cleanup: + args: + input: | + 1 2 5 3 4 + 4 6 7 8 9 + output: 0 +- setup: + cleanup: + args: + input: | + 1 3 5 7 9 + 0 2 4 6 8 + output: 1 diff --git a/challenge-127/paulo-custodio/t/test-2.yaml b/challenge-127/paulo-custodio/t/test-2.yaml new file mode 100644 index 0000000000..23446cc7dc --- /dev/null +++ b/challenge-127/paulo-custodio/t/test-2.yaml @@ -0,0 +1,10 @@ +- setup: + cleanup: + args: 1 4 3 5 6 8 12 13 3 20 + input: + output: [ (3,5), (3,20) ] +- setup: + cleanup: + args: 3 4 5 7 6 9 10 12 13 15 + input: + output: [ (6,9) ] diff --git a/challenge-127/paulo-custodio/test.pl b/challenge-127/paulo-custodio/test.pl new file mode 100644 index 0000000000..ba6c37260b --- /dev/null +++ b/challenge-127/paulo-custodio/test.pl @@ -0,0 +1,4 @@ +#!/usr/bin/env perl +use Modern::Perl; +use Test::More; +require '../../challenge-001/paulo-custodio/test.pl'; diff --git a/challenge-128/paulo-custodio/perl/ch-1.pl b/challenge-128/paulo-custodio/perl/ch-1.pl new file mode 100644 index 0000000000..ac750c3abc --- /dev/null +++ b/challenge-128/paulo-custodio/perl/ch-1.pl @@ -0,0 +1,85 @@ +#!/usr/bin/env perl + +# TASK #1 > Maximum Sub-Matrix +# Submitted by: Mohammad S Anwar +# You are given m x n binary matrix having 0 or 1. +# +# Write a script to find out maximum sub-matrix having only 0. +# +# Example 1: +# Input : [ 1 0 0 0 1 0 ] +# [ 1 1 0 0 0 1 ] +# [ 1 0 0 0 0 0 ] +# +# Output: [ 0 0 0 ] +# [ 0 0 0 ] +# Example 2: +# Input : [ 0 0 1 1 ] +# [ 0 0 0 1 ] +# [ 0 0 1 0 ] +# +# Output: [ 0 0 ] +# [ 0 0 ] +# [ 0 0 ] + +use Modern::Perl; + +my @mx = parse_matrix(); +my @submx = find_zeros(@mx); +print_matrix(@submx); + +sub parse_matrix { + my @mx; + while (<>) { + s/^\s*\[([01 ]+)\]\s*$/$1/ or die "malformed matrix\n"; + my @row = split(' ', $_); + push @mx, \@row; + } + return @mx; +} + +sub print_matrix { + my(@mx) = @_; + for (@mx) { + my @row = @$_; + say "[ ", join(" ", @row), " ]"; + } +} + +sub find_zeros { + my(@mx) = @_; + my($max_rows, $max_cols) = (0, 0); + + for my $r1 (0 .. $#mx) { + for my $c1 (0 .. $#{$mx[$r1]}) { + next unless $mx[$r1][$c1]==0; + for my $r2 ($r1 .. $#mx) { + for my $c2 ($c1 .. $#{$mx[$r1]}) { + next unless $mx[$r2][$c2]==0; + my $rows = $r2-$r1+1; + my $cols = $c2-$c1+1; + if ($rows*$cols > $max_rows*$max_cols) { + if (all_zeros(\@mx, $r1, $c1, $r2, $c2)) { + ($max_rows, $max_cols) = ($rows, $cols); + } + } + } + } + } + } + my @submx; + for my $r (1 .. $max_rows) { + push @submx, [(0) x $max_cols]; + } + return @submx; +} + +sub all_zeros { + my($mx, $r1, $c1, $r2, $c2) = @_; + for my $r ($r1 .. $r2) { + for my $c ($c1 .. $c2) { + return 0 if $mx->[$r][$c]; + } + } + return 1; +} diff --git a/challenge-128/paulo-custodio/perl/ch-2.pl b/challenge-128/paulo-custodio/perl/ch-2.pl new file mode 100644 index 0000000000..74e75713e1 --- /dev/null +++ b/challenge-128/paulo-custodio/perl/ch-2.pl @@ -0,0 +1,82 @@ +#!/usr/bin/env perl + +# TASK #2 > Minimum Platforms +# Submitted by: Mohammad S Anwar +# You are given two arrays of arrival and departure times of trains at a railway +# station. +# +# Write a script to find out the minimum number of platforms needed so that no +# train needs to wait. +# +# Example 1: +# Input: @arrivals = (11:20, 14:30) +# @departures = (11:50, 15:00) +# Output: 1 +# +# The 1st arrival of train is at 11:20 and this is the only train at the +# station, so you need 1 platform. +# Before the second arrival at 14:30, the first train left the station at +# 11:50, so you still need only 1 platform. +# Example 2: +# Input: @arrivals = (10:20, 11:00, 11:10, 12:20, 16:20, 19:00) +# @departures = (10:30, 13:20, 12:40, 12:50, 20:20, 21:20) +# Output: 3 +# +# Between 12:20 and 12:40, there would be at least 3 trains at the station, +# so we need minimum 3 platforms. + +use Modern::Perl; +use Time::Piece; + +my @stops = parse_arrivals_departures(); +my @platforms = allocate_platforms(@stops); +say scalar(@platforms); + +sub parse_arrivals_departures { + my @arrivals = parse_times(); + my @departures = parse_times(); + + my @stops; + while (@arrivals && @departures) { + push @stops, [shift @arrivals, shift @departures]; + } + return @stops; +} + +sub parse_times { + my @times = map {Time::Piece->strptime($_, "%H:%M")->epoch} + split(' ', scalar(<>)); +} + +sub allocate_platforms { + my(@stops) = @_; + my @platforms; + + for my $stop (@stops) { + allocate_stop(\@platforms, @$stop); + } + return @platforms; +} + +sub allocate_stop { + my($platforms, $s, $e) = @_; + for my $p (0 .. $#$platforms) { + if (platform_free($platforms->[$p], $s, $e)) { + push @{$platforms->[$p]}, [$s, $e]; + return; + } + } + push @$platforms, [[$s, $e]]; +} + +sub platform_free { + my($platform, $s, $e) = @_; + for my $stop (@$platform) { + if (($s >= $stop->[0] && $s < $stop->[1]) || + ($e >= $stop->[0] && $e < $stop->[1]) || + ($s < $stop->[0] && $e >= $stop->[1])) { + return 0; + } + } + return 1; +} diff --git a/challenge-128/paulo-custodio/python/ch-1.py b/challenge-128/paulo-custodio/python/ch-1.py new file mode 100644 index 0000000000..2a0d27b894 --- /dev/null +++ b/challenge-128/paulo-custodio/python/ch-1.py @@ -0,0 +1,74 @@ +#!/usr/bin/env python3 + +# TASK #1 > Maximum Sub-Matrix +# Submitted by: Mohammad S Anwar +# You are given m x n binary matrix having 0 or 1. +# +# Write a script to find out maximum sub-matrix having only 0. +# +# Example 1: +# Input : [ 1 0 0 0 1 0 ] +# [ 1 1 0 0 0 1 ] +# [ 1 0 0 0 0 0 ] +# +# Output: [ 0 0 0 ] +# [ 0 0 0 ] +# Example 2: +# Input : [ 0 0 1 1 ] +# [ 0 0 0 1 ] +# [ 0 0 1 0 ] +# +# Output: [ 0 0 ] +# [ 0 0 ] +# [ 0 0 ] + +import fileinput +import re + +def read_input(): + lines = [] + for line in fileinput.input(): + lines.append(line) + return lines + +def parse_matrix(lines): + mx = [] + for line in lines: + found = re.match(r"^\s*\[([01 ]+)\]\s*$", line) + if found: + row = [int(x) for x in found.group(1).split()] + mx.append(row) + return mx + +def print_matrix(mx): + for row in mx: + print("[ "+ " ".join([str(x) for x in row]) +" ]") + +def find_zeros(mx): + def all_zeros(mx, r1, c1, r2, c2): + for r in range(r1, r2+1): + for c in range(c1, c2+1): + if mx[r][c]!=0: + return False + return True + + max_rows,max_cols = 0,0 + for r1 in range(0, len(mx)): + for c1 in range(0, len(mx[r1])): + if mx[r1][c1]==0: + for r2 in range(r1, len(mx)): + for c2 in range(c1, len(mx[r1])): + if mx[r2][c2]==0: + rows,cols = r2-r1+1,c2-c1+1 + if rows*cols > max_rows*max_cols: + if all_zeros(mx, r1, c1, r2, c2): + max_rows,max_cols = rows,cols + submx = [] + for r in range(0, max_rows): + submx.append([0]*max_cols) + + return submx + +mx = parse_matrix(read_input()) +submx = find_zeros(mx); +print_matrix(submx) diff --git a/challenge-128/paulo-custodio/python/ch-2.py b/challenge-128/paulo-custodio/python/ch-2.py new file mode 100644 index 0000000000..d7f73d821a --- /dev/null +++ b/challenge-128/paulo-custodio/python/ch-2.py @@ -0,0 +1,67 @@ +#!/usr/bin/env python3 + +# TASK #2 > Minimum Platforms +# Submitted by: Mohammad S Anwar +# You are given two arrays of arrival and departure times of trains at a railway +# station. +# +# Write a script to find out the minimum number of platforms needed so that no +# train needs to wait. +# +# Example 1: +# Input: @arrivals = (11:20, 14:30) +# @departures = (11:50, 15:00) +# Output: 1 +# +# The 1st arrival of train is at 11:20 and this is the only train at the +# station, so you need 1 platform. +# Before the second arrival at 14:30, the first train left the station at +# 11:50, so you still need only 1 platform. +# Example 2: +# Input: @arrivals = (10:20, 11:00, 11:10, 12:20, 16:20, 19:00) +# @departures = (10:30, 13:20, 12:40, 12:50, 20:20, 21:20) +# Output: 3 +# +# Between 12:20 and 12:40, there would be at least 3 trains at the station, +# so we need minimum 3 platforms. + +import time + +def parse_arrivals_departures(): + def parse_times(): + line = input() + times = [time.strptime(x, "%H:%M") for x in line.split()] + return times + + arrivals = parse_times() + departures = parse_times() + stops = [] + while len(arrivals) > 0 and len(departures) > 0: + stops.append([arrivals.pop(0), departures.pop(0)]) + return stops + +def allocate_platforms(stops): + platforms = [] + + def platform_free(platform, s, e): + for stop in platform: + if (s >= stop[0] and s < stop[1]) or \ + (e >= stop[0] and e < stop[1]) or \ + (s < stop[0] and e >= stop[1]): + return False + return True + + def allocate_stop(s, e): + for platform in platforms: + if platform_free(platform, s, e): + platform.append([s, e]) + return + platforms.append([[s, e]]) + + for stop in stops: + allocate_stop(stop[0], stop[1]) + return platforms + +stops = parse_arrivals_departures() +platforms = allocate_platforms(stops) +print(len(platforms)) diff --git a/challenge-128/paulo-custodio/t/test-1.yaml b/challenge-128/paulo-custodio/t/test-1.yaml new file mode 100644 index 0000000000..4c66347089 --- /dev/null +++ b/challenge-128/paulo-custodio/t/test-1.yaml @@ -0,0 +1,22 @@ +- setup: + cleanup: + args: + input: | + [ 1 0 0 0 1 0 ] + [ 1 1 0 0 0 1 ] + [ 1 0 0 0 0 0 ] + output: | + [ 0 0 ] + [ 0 0 ] + [ 0 0 ] +- setup: + cleanup: + args: + input: | + [ 0 0 1 1 ] + [ 0 0 0 1 ] + [ 0 0 1 0 ] + output: | + [ 0 0 ] + [ 0 0 ] + [ 0 0 ] diff --git a/challenge-128/paulo-custodio/t/test-2.yaml b/challenge-128/paulo-custodio/t/test-2.yaml new file mode 100644 index 0000000000..b1be9371b6 --- /dev/null +++ b/challenge-128/paulo-custodio/t/test-2.yaml @@ -0,0 +1,14 @@ +- setup: + cleanup: + args: + input: | + 11:20 14:30 + 11:50 15:00 + output: 1 +- setup: + cleanup: + args: + input: | + 10:20 11:00 11:10 12:20 16:20 19:00 + 10:30 13:20 12:40 12:50 20:20 21:20 + output: 3 diff --git a/challenge-128/paulo-custodio/test.pl b/challenge-128/paul |