Weekly Challenge 211

Challenge, My solution

Task 1: Toeplitz Matrix

Task

You are given a matrix m x n.

Write a script to find out if the given matrix is Toeplitz Matrix.

A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same elements.

My solution

The first observation I make is if the matrix is not square (has the same number of row and columns), then there are two 'paths' that need to be compared. If you look at the below two examples, one diagonal is represented by the a and a second by the letter b.

a b x x    a x
x a b x    x a
x x a b    b x
           x b

For the input, I take a JSON string, and make an assumption is that it will be a multi dimensional array of integers.

The first step is to calculate the top left of each path. We know that one will always be the first value in the first row, i.e. matrix[0][0], and the offset list to this position.

If the matrix is not square, we know the second top left will either be in the first row (as per the example on the left), or the first column (as per the other example). I add this position to the offset list.

For each pair in the offset list, I work diagonal downwards comparing the value with the value at the original position. If at any time they don't match, I print 'false' and exit the function. If all the checks have passed, I print 'true'.

Examples

$ ./ch-1.py '[ [4, 3, 2, 1], [5, 4, 3, 2], [6, 5, 4, 3]]'
true

$ ./ch-1.py '[ [1, 2, 3], [3, 2, 1]]'
false

Task 2: Split Same Average

Task

You are given an array of integers. Write a script to find out if the given can be split into two separate arrays whose average are the same.

My solution

This is one of those tasks where some cleverer Team PWC members are going to have a more efficient solution than my one. I'm just going to brute force it.

For this task I have two loops. The outer loop is the number of values I want to compare. It starts at 1 and end at half the length of the array (rounding down there are an odd number of values). The inner array produces all combinations of that many items. If the average of that combination is same as the total average, print 'true' and exit.

Like with previous combination challenges, I've used the combination function from itertools (Python) and Algorithm::Combinatorics (Perl).

I also have an edge case of a single value always returning 'true'. As half of the length of the array is less than 1, the loop doesn't have a chance to run.

Examples

$ ./ch-2.py 1 2 3 4 5 6 7 8
true

$ ./ch-2.py 1 3
false