From cbd8108e0dceaaa39b28d2824974780a20c5a5e0 Mon Sep 17 00:00:00 2001 From: arnesom Date: Sun, 5 Sep 2021 13:14:03 +0200 Subject: Arne Sommer --- challenge-128/arne-sommer/blog.txt | 1 + challenge-128/arne-sommer/raku/ch-1.raku | 75 ++++++++++++++++++ challenge-128/arne-sommer/raku/ch-2.raku | 81 +++++++++++++++++++ challenge-128/arne-sommer/raku/maximum-sub-matrix | 75 ++++++++++++++++++ .../arne-sommer/raku/maximum-sub-matrix-swapped | 75 ++++++++++++++++++ challenge-128/arne-sommer/raku/minimum-platforms | 69 ++++++++++++++++ .../arne-sommer/raku/minimum-platforms-nicer | 81 +++++++++++++++++++ .../raku/minimum-platforms-permutations | 92 ++++++++++++++++++++++ .../arne-sommer/raku/minimum-platforms-sorted | 81 +++++++++++++++++++ 9 files changed, 630 insertions(+) create mode 100644 challenge-128/arne-sommer/blog.txt create mode 100755 challenge-128/arne-sommer/raku/ch-1.raku create mode 100755 challenge-128/arne-sommer/raku/ch-2.raku create mode 100755 challenge-128/arne-sommer/raku/maximum-sub-matrix create mode 100755 challenge-128/arne-sommer/raku/maximum-sub-matrix-swapped create mode 100755 challenge-128/arne-sommer/raku/minimum-platforms create mode 100755 challenge-128/arne-sommer/raku/minimum-platforms-nicer create mode 100755 challenge-128/arne-sommer/raku/minimum-platforms-permutations create mode 100755 challenge-128/arne-sommer/raku/minimum-platforms-sorted diff --git a/challenge-128/arne-sommer/blog.txt b/challenge-128/arne-sommer/blog.txt new file mode 100644 index 0000000000..c0fa8037b4 --- /dev/null +++ b/challenge-128/arne-sommer/blog.txt @@ -0,0 +1 @@ +https://raku-musings.com/mums-platform.html diff --git a/challenge-128/arne-sommer/raku/ch-1.raku b/challenge-128/arne-sommer/raku/ch-1.raku new file mode 100755 index 0000000000..064a986b6a --- /dev/null +++ b/challenge-128/arne-sommer/raku/ch-1.raku @@ -0,0 +1,75 @@ +#! /usr/bin/env raku + +unit sub MAIN (Str $matrix = "1 0 0 0 1 0 | 1 1 0 0 0 1 | 1 0 0 0 0 0", :v(:$verbose)); + +my @m = $matrix.split("|")>>.words>>.Numeric; ## .List; + +die "Illegal characters" unless all($matrix.words) eq any(0,1,'|'); + +die "No zeros" unless any($matrix.words) eq '0'; +die "Uneven row length" unless all(@m>>.elems) == @m[0].elems && @m[0].elems > 0; + +my $number-of-rows = @m.elems; my $last-row = $number-of-rows -1; +my $number-of-cols = @m[0].elems; my $last-col = $number-of-cols -1; + +say ": Rows: $number-of-rows, cols: $number-of-cols" if $verbose; + +my $largest-size = 0; +my $largest-rows = 0; +my $largest-cols = 0; + +for 0 .. $last-col -> $from-col +{ + for $last-col ... $from-col -> $to-col + { + for 0 .. $last-row -> $from-row + { + for $last-row ... $from-row -> $to-row + { + my $size = ($to-row - $from-row +1) * ($to-col - $from-col +1); + next if $size <= $largest-size; + + my @rect = get-rectangle(@m, $from-row, $from-col, $to-row, $to-col); + my $zero = zero-rectangle(@rect); + + say ": Checking rectangle [UL: $from-row, $from-col][LR: $to-row, $to-col]: ", + "{ @rect.raku } ---> $zero" if $verbose; + + if $zero + { + my $rows = 1 + $to-row - $from-row; + my $cols = 1 + $to-col - $from-col; + my $size = $rows * $cols ; + + if $size > $largest-size + { + say ": - Largest so far $size ($rows x $cols)" if $verbose; + $largest-size = $size; + $largest-rows = $rows; + $largest-cols = $cols; + } + } + } + } + } +} + +if $largest-size +{ + say ": Largest with size $largest-size ($largest-rows x $largest-cols)" if $verbose; + say "[ { '0' xx $largest-cols } ]" for ^$largest-rows; +} +else +{ + say "[]"; +} + +sub get-rectangle(@matrix, $x1, $y1, $x2, $y2) +{ + return (($x1 .. $x2).map({ @m[$_][$y1 .. $y2] })); +} + +sub zero-rectangle (@matrix) +{ + return so all(@matrix.List.flat) eq "0"; +} diff --git a/challenge-128/arne-sommer/raku/ch-2.raku b/challenge-128/arne-sommer/raku/ch-2.raku new file mode 100755 index 0000000000..3fe1fd3138 --- /dev/null +++ b/challenge-128/arne-sommer/raku/ch-2.raku @@ -0,0 +1,81 @@ +#! /usr/bin/env raku + +subset HHMM where $_ ~~ /^(<[012]>)\d\:<[012345]>\d$/ && $0 <= 23; + +unit sub MAIN (Str $trains = "11:20 11:50 | 14:30 15:00", + :l(:$loquacious), + :v(:$verbose) = $loquacious, +); + +class Platform +{ + has Str $.id; + has Str @.in-use is rw; + + method add-if-vacant (HHMM $from, HHMM $to) + { + for @.in-use -> $interval + { + my ($start, $end) = $interval.split("-"); + next if $to lt $start; + next if $end lt $from; + + return False; + } + + @.in-use.push: "$from-$to"; + return True; + } + + method Str + { + return ": - Platform: $.id: " ~ @.in-use.sort.join(", "); + } +} + +class Station +{ + has Str $.name; + has Platform @.platforms is rw; + + method add-train (HHMM $from, HHMM $to) + { + for self.platforms -> $platform + { + return True if $platform.add-if-vacant($from, $to); + } + + my $platform = Platform.new(id => (self.number-of-platforms + 1).Str); + self.platforms.push: $platform; + return $platform.add-if-vacant($from, $to); + } + + method number-of-platforms + { + return @.platforms.elems; + } + + method Str + { + return ": Station: $.name\n" ~ @.platforms>>.Str.join("\n"); + } +} + +my $station = Station.new(name => 'Grand Central'); + +my @trains = $trains.split(/\s\|\s+/); + +for @trains.sort -> $from-to +{ + my (HHMM $from, HHMM $to) = $from-to.words; + + die "Train departs ($from) before it arrives ($to)" if $from gt $to; + + say ": Visiting train $from -> $to" if $verbose; + + $station.add-train($from, $to); +} + +say $station.Str if $loquacious; + +say $station.number-of-platforms; diff --git a/challenge-128/arne-sommer/raku/maximum-sub-matrix b/challenge-128/arne-sommer/raku/maximum-sub-matrix new file mode 100755 index 0000000000..0ac3271037 --- /dev/null +++ b/challenge-128/arne-sommer/raku/maximum-sub-matrix @@ -0,0 +1,75 @@ +#! /usr/bin/env raku + +unit sub MAIN (Str $matrix = "1 0 0 0 1 0 | 1 1 0 0 0 1 | 1 0 0 0 0 0", :v(:$verbose)); + +my @m = $matrix.split("|")>>.words>>.Numeric; ## .List; + +die "Illegal characters" unless all($matrix.words) eq any(0,1,'|'); + +die "No zeros" unless any($matrix.words) eq '0'; +die "Uneven row length" unless all(@m>>.elems) == @m[0].elems && @m[0].elems > 0; + +my $number-of-rows = @m.elems; my $last-row = $number-of-rows -1; +my $number-of-cols = @m[0].elems; my $last-col = $number-of-cols -1; + +say ": Rows: $number-of-rows, cols: $number-of-cols" if $verbose; + +my $largest-size = 0; +my $largest-rows = 0; +my $largest-cols = 0; + +for 0 .. $last-row -> $from-row +{ + for $last-row ... $from-row -> $to-row + { + for 0 .. $last-col -> $from-col + { + for $last-col ... $from-col -> $to-col + { + my $size = ($to-row - $from-row +1) * ($to-col - $from-col +1); + next if $size <= $largest-size; + + my @rect = get-rectangle(@m, $from-row, $from-col, $to-row, $to-col); + my $zero = zero-rectangle(@rect); + + say ": Checking rectangle [UL: $from-row, $from-col][LR: $to-row, $to-col]: ", + "{ @rect.raku } ---> $zero" if $verbose; + + if $zero + { + my $rows = 1 + $to-row - $from-row; + my $cols = 1 + $to-col - $from-col; + my $size = $rows * $cols ; + + if $size > $largest-size + { + say ": - Largest so far $size ($rows x $cols)" if $verbose; + $largest-size = $size; + $largest-rows = $rows; + $largest-cols = $cols; + } + } + } + } + } +} + +if $largest-size +{ + say ": Largest with size $largest-size ($largest-rows x $largest-cols)" if $verbose; + say "[ { '0' xx $largest-cols } ]" for ^$largest-rows; +} +else +{ + say "[]"; +} + +sub get-rectangle(@matrix, $x1, $y1, $x2, $y2) +{ + return (($x1 .. $x2).map({ @m[$_][$y1 .. $y2] })); +} + +sub zero-rectangle (@matrix) +{ + return so all(@matrix.List.flat) eq "0"; +} diff --git a/challenge-128/arne-sommer/raku/maximum-sub-matrix-swapped b/challenge-128/arne-sommer/raku/maximum-sub-matrix-swapped new file mode 100755 index 0000000000..064a986b6a --- /dev/null +++ b/challenge-128/arne-sommer/raku/maximum-sub-matrix-swapped @@ -0,0 +1,75 @@ +#! /usr/bin/env raku + +unit sub MAIN (Str $matrix = "1 0 0 0 1 0 | 1 1 0 0 0 1 | 1 0 0 0 0 0", :v(:$verbose)); + +my @m = $matrix.split("|")>>.words>>.Numeric; ## .List; + +die "Illegal characters" unless all($matrix.words) eq any(0,1,'|'); + +die "No zeros" unless any($matrix.words) eq '0'; +die "Uneven row length" unless all(@m>>.elems) == @m[0].elems && @m[0].elems > 0; + +my $number-of-rows = @m.elems; my $last-row = $number-of-rows -1; +my $number-of-cols = @m[0].elems; my $last-col = $number-of-cols -1; + +say ": Rows: $number-of-rows, cols: $number-of-cols" if $verbose; + +my $largest-size = 0; +my $largest-rows = 0; +my $largest-cols = 0; + +for 0 .. $last-col -> $from-col +{ + for $last-col ... $from-col -> $to-col + { + for 0 .. $last-row -> $from-row + { + for $last-row ... $from-row -> $to-row + { + my $size = ($to-row - $from-row +1) * ($to-col - $from-col +1); + next if $size <= $largest-size; + + my @rect = get-rectangle(@m, $from-row, $from-col, $to-row, $to-col); + my $zero = zero-rectangle(@rect); + + say ": Checking rectangle [UL: $from-row, $from-col][LR: $to-row, $to-col]: ", + "{ @rect.raku } ---> $zero" if $verbose; + + if $zero + { + my $rows = 1 + $to-row - $from-row; + my $cols = 1 + $to-col - $from-col; + my $size = $rows * $cols ; + + if $size > $largest-size + { + say ": - Largest so far $size ($rows x $cols)" if $verbose; + $largest-size = $size; + $largest-rows = $rows; + $largest-cols = $cols; + } + } + } + } + } +} + +if $largest-size +{ + say ": Largest with size $largest-size ($largest-rows x $largest-cols)" if $verbose; + say "[ { '0' xx $largest-cols } ]" for ^$largest-rows; +} +else +{ + say "[]"; +} + +sub get-rectangle(@matrix, $x1, $y1, $x2, $y2) +{ + return (($x1 .. $x2).map({ @m[$_][$y1 .. $y2] })); +} + +sub zero-rectangle (@matrix) +{ + return so all(@matrix.List.flat) eq "0"; +} diff --git a/challenge-128/arne-sommer/raku/minimum-platforms b/challenge-128/arne-sommer/raku/minimum-platforms new file mode 100755 index 0000000000..9aafcfec5f --- /dev/null +++ b/challenge-128/arne-sommer/raku/minimum-platforms @@ -0,0 +1,69 @@ +#! /usr/bin/env raku + +subset HHMM where $_ ~~ /^(<[012]>)\d\:<[012345]>\d$/ && $0 <= 23; + +unit sub MAIN (Str $trains = "11:20 11:50 | 14:30 15:00", + :l(:$loquacious), + :v(:$verbose) = $loquacious, +); + +class Platform +{ + has Str $.id; + has Str @.in-use is rw; + + method add-if-vacant (HHMM $from, HHMM $to) + { + for @.in-use -> $interval + { + my ($start, $end) = $interval.split("-"); + next if $to lt $start; + next if $end lt $from; + + return False; + } + + @.in-use.push: "$from-$to"; + return True; + } +} + +class Station +{ + has Str $.name; + has Platform @.platforms is rw; + + method add-train (HHMM $from, HHMM $to) + { + for self.platforms -> $platform + { + return True if $platform.add-if-vacant($from, $to); + } + + my $platform = Platform.new(id => (self.number-of-platforms + 1).Str); + self.platforms.push: $platform; + return $platform.add-if-vacant($from, $to); + } + + method number-of-platforms + { + return @.platforms.elems; + } +} + +my $station = Station.new(name => 'Grand Central'); + +my @trains = $trains.split("|"); + +for @trains -> $from-to +{ + my (HHMM $from, HHMM $to) = $from-to.words; + + say ": Visiting train $from -> $to" if $verbose; + + $station.add-train($from, $to); +} + +say ": Station: { $station.raku }" if $loquacious; + +say $station.number-of-platforms; diff --git a/challenge-128/arne-sommer/raku/minimum-platforms-nicer b/challenge-128/arne-sommer/raku/minimum-platforms-nicer new file mode 100755 index 0000000000..d6bb6d39a7 --- /dev/null +++ b/challenge-128/arne-sommer/raku/minimum-platforms-nicer @@ -0,0 +1,81 @@ +#! /usr/bin/env raku + +subset HHMM where $_ ~~ /^(<[012]>)\d\:<[012345]>\d$/ && $0 <= 23; + +unit sub MAIN (Str $trains = "11:20 11:50 | 14:30 15:00", + :l(:$loquacious), + :v(:$verbose) = $loquacious, +); + +class Platform +{ + has Str $.id; + has Str @.in-use is rw; + + method add-if-vacant (HHMM $from, HHMM $to) + { + for @.in-use -> $interval + { + my ($start, $end) = $interval.split("-"); + next if $to lt $start; + next if $end lt $from; + + return False; + } + + @.in-use.push: "$from-$to"; + return True; + } + + method Str + { + return ": - Platform: $.id: " ~ @.in-use.sort.join(", "); + } +} + +class Station +{ + has Str $.name; + has Platform @.platforms is rw; + + method add-train (HHMM $from, HHMM $to) + { + for self.platforms -> $platform + { + return True if $platform.add-if-vacant($from, $to); + } + + my $platform = Platform.new(id => (self.number-of-platforms + 1).Str); + self.platforms.push: $platform; + return $platform.add-if-vacant($from, $to); + } + + method number-of-platforms + { + return @.platforms.elems; + } + + method Str + { + return ": Station: $.name\n" ~ @.platforms>>.Str.join("\n"); + } +} + +my $station = Station.new(name => 'Grand Central'); + +my @trains = $trains.split("|"); + +for @trains -> $from-to +{ + my (HHMM $from, HHMM $to) = $from-to.words; + + die "Train departs ($from) before it arrives ($to)" if $from gt $to; + + say ": Visiting train $from -> $to" if $verbose; + + $station.add-train($from, $to); +} + +say $station.Str if $loquacious; + +say $station.number-of-platforms; diff --git a/challenge-128/arne-sommer/raku/minimum-platforms-permutations b/challenge-128/arne-sommer/raku/minimum-platforms-permutations new file mode 100755 index 0000000000..e61f55f160 --- /dev/null +++ b/challenge-128/arne-sommer/raku/minimum-platforms-permutations @@ -0,0 +1,92 @@ +#! /usr/bin/env raku + +subset HHMM where $_ ~~ /^(<[012]>)\d\:<[012345]>\d$/ && $0 <= 23; + +unit sub MAIN (Str $trains = "11:20 11:50 | 14:30 15:00", + :l(:$loquacious), + :v(:$verbose) = $loquacious, + :p(:$platforms), +); + +class Platform +{ + has Str $.id; + has Str @.in-use is rw; + + method add-if-vacant (HHMM $from, HHMM $to) + { + for @.in-use -> $interval + { + my ($start, $end) = $interval.split("-"); + next if $to lt $start; + next if $end lt $from; + + return False; + } + + @.in-use.push: "$from-$to"; + return True; + } + + method Str + { + return ": - Platform: $.id: " ~ @.in-use.sort.join(", "); + } +} + +class Station +{ + has Str $.name; + has Platform @.platforms is rw; + + method add-train (HHMM $from, HHMM $to) + { + for self.platforms -> $platform + { + return True if $platform.add-if-vacant($from, $to); + } + + my $platform = Platform.new(id => (self.number-of-platforms + 1).Str); + self.platforms.push: $platform; + return $platform.add-if-vacant($from, $to); + } + + method number-of-platforms + { + return @.platforms.elems; + } + + method Str + { + return ": Station: $.name\n" ~ @.platforms>>.Str.join("\n"); + } +} + +my @trains = $trains.split(/\s\|\s+/); + +my $number-of-platforms = Inf; + +for @trains.permutations -> @trains-p +{ + my $station = Station.new(name => 'Grand Central'); + + for @trains-p -> $from-to + { + my (HHMM $from, HHMM $to) = $from-to.words; + + die "Train departs ($from) before it arrives ($to)" if $from gt $to; + + say ": Visiting train $from -> $to" if $verbose; + + $station.add-train($from, $to); + } + + say $station.Str if $loquacious; + + my $platform-count = $station.number-of-platforms; + $number-of-platforms = min($number-of-platforms, $platform-count); + + say ": Platforms: $platforms" if $platforms; +} + +say $number-of-platforms; diff --git a/challenge-128/arne-sommer/raku/minimum-platforms-sorted b/challenge-128/arne-sommer/raku/minimum-platforms-sorted new file mode 100755 index 0000000000..3fe1fd3138 --- /dev/null +++ b/challenge-128/arne-sommer/raku/minimum-platforms-sorted @@ -0,0 +1,81 @@ +#! /usr/bin/env raku + +subset HHMM where $_ ~~ /^(<[012]>)\d\:<[012345]>\d$/ && $0 <= 23; + +unit sub MAIN (Str $trains = "11:20 11:50 | 14:30 15:00", + :l(:$loquacious), + :v(:$verbose) = $loquacious, +); + +class Platform +{ + has Str $.id; + has Str @.in-use is rw; + + method add-if-vacant (HHMM $from, HHMM $to) + { + for @.in-use -> $interval + { + my ($start, $end) = $interval.split("-"); + next if $to lt $start; + next if $end lt $from; + + return False; + } + + @.in-use.push: "$from-$to"; + return True; + } + + method Str + { + return ": - Platform: $.id: " ~ @.in-use.sort.join(", "); + } +} + +class Station +{ + has Str $.name; + has Platform @.platforms is rw; + + method add-train (HHMM $from, HHMM $to) + { + for self.platforms -> $platform + { + return True if $platform.add-if-vacant($from, $to); + } + + my $platform = Platform.new(id => (self.number-of-platforms + 1).Str); + self.platforms.push: $platform; + return $platform.add-if-vacant($from, $to); + } + + method number-of-platforms + { + return @.platforms.elems; + } + + method Str + { + return ": Station: $.name\n" ~ @.platforms>>.Str.join("\n"); + } +} + +my $station = Station.new(name => 'Grand Central'); + +my @trains = $trains.split(/\s\|\s+/); + +for @trains.sort -> $from-to +{ + my (HHMM $from, HHMM $to) = $from-to.words; + + die "Train departs ($from) before it arrives ($to)" if $from gt $to; + + say ": Visiting train $from -> $to" if $verbose; + + $station.add-train($from, $to); +} + +say $station.Str if $loquacious; + +say $station.number-of-platforms; -- cgit