diff options
| -rw-r--r-- | challenge-129/abigail/README.md | 82 | ||||
| -rw-r--r-- | challenge-129/abigail/perl/ch-1.pl | 71 | ||||
| -rw-r--r-- | challenge-129/abigail/perl/ch-2.pl | 85 |
3 files changed, 156 insertions, 82 deletions
diff --git a/challenge-129/abigail/README.md b/challenge-129/abigail/README.md index b4279b09ff..38e51d0b9c 100644 --- a/challenge-129/abigail/README.md +++ b/challenge-129/abigail/README.md @@ -1,83 +1 @@ # Solutions by Abigail -## [Maximum Sub-Matrix][task1] - -> You are given m x n binary matrix having 0 or 1. -> -> Write a script to find out maximum sub-matrix having only 0 - - -### Examples - -~~~~ -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 ] -~~~~ - -~~~~ -Input : [ 0 0 1 1 ] - [ 0 0 0 1 ] - [ 0 0 1 0 ] - -Output: [ 0 0 ] - [ 0 0 ] - [ 0 0 ] -~~~~ - - -### Solutions -* [Perl](perl/ch-1.pl) - -### Blog -[Perl Weekly Challenge 128: Maximum Sub-Matrix][blog1] - -## [Minimum Platforms][task2] - -> 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. - -### Examples - -~~~~ -Input: @arrivals = (11:20, 14:30) - @departutes = (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. - -~~~~ -Input: @arrivals = (10:20, 11:00, 11:10, 12:20, 16:20, 19:00) - @departutes = (10:30, 13:20, 12:40, 12:50, 20:20, 21:20) -Output: 3 -~~~~ - -Between 11:00 and 12:20, there would be at least 3 trains at the -station, so we need minimum 3 platforms. - -### Solutions -* [AWK](awk/ch-2.awk) -* [C](awk/ch-2.c) -* [Lua](lua/ch-2.lua) -* [Node.js](node/ch-2.js) -* [Perl](perl/ch-2.pl) -* [Python](python/ch-2.py) - -### Blog -[Perl Weekly Challenge 128: Minimum Platforms][blog2] - - - -[task1]: https://perlweeklychallenge.org/blog/perl-weekly-challenge-128/#TASK1 -[task2]: https://perlweeklychallenge.org/blog/perl-weekly-challenge-128/#TASK2 -[blog1]: https://abigail.github.io/HTML/Perl-Weekly-Challenge/week-128-1.html -[blog2]: https://abigail.github.io/HTML/Perl-Weekly-Challenge/week-128-2.html diff --git a/challenge-129/abigail/perl/ch-1.pl b/challenge-129/abigail/perl/ch-1.pl new file mode 100644 index 0000000000..4b89a8269c --- /dev/null +++ b/challenge-129/abigail/perl/ch-1.pl @@ -0,0 +1,71 @@ +#!/opt/perl/bin/perl + +use 5.032; + +use strict; +use warnings; +no warnings 'syntax'; + +use experimental 'signatures'; +use experimental 'lexical_subs'; + +# +# See ../README.md +# + +# +# And once again, a stupid challenge about a tree with no +# fucking clue about how the input is structured. For instance, +# a star with 27 elements, how on earth is this going to presented? +# Using examples of tiny, sparse, binary trees is not at all helpful. +# +# We're not going to even attempt to think how the input will be +# structered. We'll just assume magic, and the tree to be there +# once the program starts. +# +# This challenge is just a shortest path algorithm, from algorithms 101. +# The fact the graph is a tree provides us with little benefits (for +# some representations of a tree, we can skip a bit of bookkeepping, +# but this is such a standard algorithm, why bother?) +# +# We will be assuming that the numbers in the examples are just labels +# of the nodes, (instead of actual values); therefore, we can treat the +# numbers as unique numbers, and we don't have to deal with duplicates. +# The root node will always have label 1. +# +# The graph will be representated as hash: the keys are the labels of +# the nodes, the values are a list of neigbhours of the nodes. (Using +# magic to read in the data). +# +# We also assume that "You are given a tree and a node of the given tree." +# is leading, and the examples are misleading, as the examples give +# multiple nodes per tree, contradicting the statement we are given "a node". +# + +my $graph = do {...}; # Uses magic to read in data, which is given in an + # unknown format. + +my $target = do {...}; # Next line of input? No clue. +my $root = 1; + + +# +# Bog standard BFS +# +my @todo = ([$root, 0]); # [node, distance from root]) +my %seen; + +while (@todo) { + my ($node, $distance) = @{shift @todo} + if ($node == $target) { + say $distance; + exit; + } + next if $seen {$node} ++; + push @todo => map {[$_, $distance + 1]} @{$$graph {$node}} +} + +say "$target does not exist, or is not connected to the root node"; + + +__END__ diff --git a/challenge-129/abigail/perl/ch-2.pl b/challenge-129/abigail/perl/ch-2.pl new file mode 100644 index 0000000000..e43ec41f11 --- /dev/null +++ b/challenge-129/abigail/perl/ch-2.pl @@ -0,0 +1,85 @@ +#!/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 +# + +# +# Linked lists? Seriously? Now, there are problems for which a linked +# list is the right datastructure, and for which using an array is a +# bad choice. Advent of Code usually manages to create at least one +# problem each year highlighting this. +# +# For this challenge, forcing to use a linked list feels as clunky as +# writing a novel with using the letter 'e'. Sure, the first guy who +# did so got some recognition, but that was a one time event. It's not +# that e-free novels are storming the top 10 reading lists. +# +# But even if you were to represent numbers as linked lists of single +# digit numbers, why on earth would you represent your number in such +# a way you have to process the linked list back to forth? You'd fail +# algorithms 101 if you ever did that in class. +# + +# +# Also, what's up with the hint? Are we free to come up with our own +# unique way to deal with the task, or should we create a class representing +# a linked list, with a bunch of methods? Those two statements contradict +# each other. +# +# I can't be bothered to come with a full class which does nothing to solve +# the given problem, so I'll be ignoring anything of the hint following its +# first full stop. +# +# (Also: "a method to add new member", At the front? The back? Somewhere +# in the middle? These things matter for linked list. +# And: "It should have methods to create a linked list given list of +# single digit positive numbers" So, you need a method which given a list, +# gives you back a list? That's a no-op, isn't it?) +# + +# +# Helper functions to turn a number into a linked list, +# and a linked list back into a number: +# (If we have to bring in linked lists to add numbers, don't mind +# me if I bring in $& and friends). +# +sub n2ll ($num) {$num =~ /./ ? [my $x = $&, n2ll ($')] : []} +sub ll2n ($ll) {@$ll ? $$ll [0] . ll2n ($$ll [1]) : ""} + +# +# Add two linked lists. We do this by flattening the lists, +# using bigint to add the numbers, then turning the result +# into a list again. +# +sub add ($ll1, $ll2) {use bigint; n2ll (0 + ll2n ($ll1) + ll2n ($ll2))} + + +# +# Read in the two numbers, and turn them into linked lists: +# +my $f_ll = n2ll <> =~ s/[^0-9]+//gr; +my $s_ll = n2ll <> =~ s/[^0-9]+//gr; + +# +# Add them: +# +my $sum_ll = add ($f_ll, $s_ll); + +# +# Pretty print the result: +# +say join " -> " => split // => ll2n $sum_ll; |