Weekly Challenge 128

Challenge, My solutions

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, 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 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.
2. 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.
3. I set the @platform array to be 1440 occurrences of 0, indicating the number of platforms used at that minute.
4. I then work through every minute of every train, and add one to the required platforms for that minute.
5. 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