Weekly Challenge 128
Tags: perl, theweeklychallenge
Published: 2021-08-30 11:04:31

[Challenge](https://theweeklychallenge.org/blog/perl-weekly-challenge-128/), [My solutions](https://github.com/manwar/perlweeklychallenge-club/tree/master/challenge-128/sgreen)

## TASK #1 › Maximum Sub-Matrix

### Task

You are given m x n binary matrix having 0 or 1.

Write a script to find out maximum sub-matrix having only 0.

### My solution

This is similar to the second task in [Challenge 126](https://theweeklychallenge.org/blog/perl-weekly-challenge-126/#TASK2), so a lot of code comes from that.

I take input from STDIN, so a file can be piped in to provide the input. Like with challenge 126, I get all the `0` and `1` from the input file and check the rows are of the same length.

I then go through each cell, considering that as the top left of the smaller matrix. If that value is `1`, I move to the next cell.

Now that we have the top left of a smaller matrix, we need to work out what matrices we can make. This is a little complicated, so strap yourself in.

* For the current row, we calculate how many positions to the right we can move before we hit a one or the end of the row. This is the `$width` value.
* When then repeat this for the second row (if that is a `0`), and count the positions to the right before we hit a one or the maximum matches from the first row (the `$max_width` value).
* We repeat this for subsequent rows, until we reach the last row or a one. 
* For each row, we calculate the size of the inner matrix. If it's larger than any previous found matrix, we update the `$best_width` and `$best_height` values. Both the width and height are positions down/rightward from the top left, so we add one when doing these comparisons.

Finally, we use the best_width and best_height values to show the output in the appropriate format.

### Examples

My result from the first example differs from that provided in the task. Turns out there is both a 2 × 3 and a 3 × 2 solution.

```
$ ./ch-1.pl < example1.txt 
[ 0 0 ]
[ 0 0 ]
[ 0 0 ]

$ ./ch-1.pl < example2.txt 
[ 0 0 ]
[ 0 0 ]
[ 0 0 ]
```
## TASK #2 › Minimum Platforms

### Task

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.

### My solution

One thing that is not clarified is if a train arrives the same time as another one departs, does this require one platform or two? I've made the assumption that two platforms are required. The wonderful people at [Sydney Trains](https://www.transport.nsw.gov.au/sydneytrains) would just hold up the second train, but that's a different story.

I then broke down the task into the following steps.

1. Take anything that looks like a time, and put it into the `@times` array.
1. Pair up the arrival times with the matching departure time, and put them in the `@trains` array.
    * I also turn the HH:MM format to minutes since midnight.
    * If a train appears to depart before it arrives, it means that the time spans midnight. In this scenario, I treat it as two separate trains, one from arrival to 11:59pm and one from midnight to departure.
1. I set the `@platform` array to be 1440 occurrences of 0, indicating the number of platforms used at that minute.
1. I then work through every minute of every train, and add one to the required platforms for that minute.
1. Finally I get the maximum number of platforms required, and display that value.

### Examples

```
 ./ch-2.pl "(11:20, 14:30)" "(11:50, 15:00)"
1

$ ./ch-2.pl "(10:20, 11:00, 11:10, 12:20, 16:20, 19:00)" "(10:30, 13:20, 12:40, 12:50, 20:20, 21:20)"
3
```