The current echelon

Weekly Challenge 257

Each week Mohammad S. Anwar sends out The Weekly Challenge, a chance for all of us to come up with solutions to two weekly tasks. My solutions are written in Python first, and then converted to Perl. It’s a great way for us all to practice some coding.

Challenge, My solutions

Task 1: Smaller than Current

Task

You are given a array of integers, @ints.

Write a script to find out how many integers are smaller than current i.e. foreach ints[i], count ints[j] < ints[i] where i != j.

My solution

The second part of the condition does not need to be checked, as ints[j] will never be less than ints[i] when i and j are the same. In Python, this is a simple one liner:


<span>def</span> <span>smaller_than_current</span><span>(</span><span>ints</span><span>:</span> <span>list</span><span>)</span> <span>-></span> <span>list</span><span>:</span>
    <span>return</span> <span>[</span><span>sum</span><span>(</span><span>1</span> <span>for</span> <span>j</span> <span>in</span> <span>ints</span> <span>if</span> <span>j</span> <span><</span> <span>i</span><span>)</span> <span>for</span> <span>i</span> <span>in</span> <span>ints</span><span>]</span>
<span>def</span> <span>smaller_than_current</span><span>(</span><span>ints</span><span>:</span> <span>list</span><span>)</span> <span>-></span> <span>list</span><span>:</span>
    <span>return</span> <span>[</span><span>sum</span><span>(</span><span>1</span> <span>for</span> <span>j</span> <span>in</span> <span>ints</span> <span>if</span> <span>j</span> <span><</span> <span>i</span><span>)</span> <span>for</span> <span>i</span> <span>in</span> <span>ints</span><span>]</span>
def smaller_than_current(ints: list) -> list:
    return [sum(1 for j in ints if j < i) for i in ints]

Enter fullscreen mode Exit fullscreen mode

which probably doesn’t really need much explanation.

The Perl code is a little more complex as it doesn’t easily allow a double for loop in a single line.


<span>sub </span><span>smaller_ints</span> <span>( $ints, $target ) {</span>
    <span>return</span> <span>scalar</span><span>(</span> <span>grep</span> <span>{</span> <span>$_</span> <span><</span> <span>$target</span> <span>}</span> <span>@$ints</span> <span>);</span>
<span>}</span>
<span>sub </span><span>main</span> <span>(@ints) {</span>
    <span>my</span> <span>@results</span> <span>=</span> <span>map</span> <span>{</span> <span>smaller_ints</span><span>(</span> <span>\</span><span>@ints</span><span>,</span> <span>$_</span> <span>)</span> <span>}</span> <span>@ints</span><span>;</span>
    <span>say</span> <span>'</span><span>(</span><span>',</span> <span>join</span><span>(</span> <span>'</span><span>, </span><span>',</span> <span>@results</span> <span>),</span> <span>'</span><span>)</span><span>';</span>
<span>}</span>
<span>sub </span><span>smaller_ints</span> <span>( $ints, $target ) {</span>
    <span>return</span> <span>scalar</span><span>(</span> <span>grep</span> <span>{</span> <span>$_</span> <span><</span> <span>$target</span> <span>}</span> <span>@$ints</span> <span>);</span>
<span>}</span>

<span>sub </span><span>main</span> <span>(@ints) {</span>
    <span>my</span> <span>@results</span> <span>=</span> <span>map</span> <span>{</span> <span>smaller_ints</span><span>(</span> <span>\</span><span>@ints</span><span>,</span> <span>$_</span> <span>)</span> <span>}</span> <span>@ints</span><span>;</span>
    <span>say</span> <span>'</span><span>(</span><span>',</span> <span>join</span><span>(</span> <span>'</span><span>, </span><span>',</span> <span>@results</span> <span>),</span> <span>'</span><span>)</span><span>';</span>
<span>}</span>
sub smaller_ints ( $ints, $target ) {
    return scalar( grep { $_ < $target } @$ints );
}

sub main (@ints) {
    my @results = map { smaller_ints( \@ints, $_ ) } @ints;
    say '(', join( ', ', @results ), ')';
}

Enter fullscreen mode Exit fullscreen mode

Examples


<span>$ </span>./ch-1.py 5 2 1 6
<span>(</span>2, 1, 0, 3<span>)</span>
<span>$ </span>./ch-1.py 1 2 0 3
<span>(</span>1, 2, 0, 3<span>)</span>
<span>$ </span>./ch-1.py 0 1
<span>(</span>0, 1<span>)</span>
<span>$ </span>./ch-1.py 9 4 9 2
<span>(</span>2, 1, 2, 0<span>)</span>
<span>$ </span>./ch-1.py 5 2 1 6
<span>(</span>2, 1, 0, 3<span>)</span>

<span>$ </span>./ch-1.py 1 2 0 3
<span>(</span>1, 2, 0, 3<span>)</span>

<span>$ </span>./ch-1.py 0 1
<span>(</span>0, 1<span>)</span>

<span>$ </span>./ch-1.py 9 4 9 2
<span>(</span>2, 1, 2, 0<span>)</span>
$ ./ch-1.py 5 2 1 6
(2, 1, 0, 3)

$ ./ch-1.py 1 2 0 3
(1, 2, 0, 3)

$ ./ch-1.py 0 1
(0, 1)

$ ./ch-1.py 9 4 9 2
(2, 1, 2, 0)

Enter fullscreen mode Exit fullscreen mode

Task 2: Reduced Row Echelon

Task

Given a matrix M, check whether the matrix is in reduced row echelon form.

A matrix must have the following properties to be in reduced row echelon form:

If a row does not consist entirely of zeros, then the first non-zero number in the row is a 1. We call this the leading 1.
If there are any rows that consist entirely of zeros, then they are grouped together at the bottom of the matrix.
In any two successive rows that do not consist entirely of zeros, the leading 1 in the lower row occurs farther to the right than the leading 1 in the higher row.
Each column that contains a leading 1 has zeros everywhere else in that column.

My solution

These are the tasks that I really like. It challenges me to take the requirements and interpret them into functioning code. I suppose today’s kids just ask ChatGPT or Microsoft Co-pilot to write the code 😛

As this code is a bit more complex than usual, I’ll try and describe my solution as best I can. The first step is to take the JSON input, and validate the rows are all of the size.


<span>def</span> <span>validate_matrix</span><span>(</span><span>matrix</span><span>):</span>
    <span>rows</span> <span>=</span> <span>len</span><span>(</span><span>matrix</span><span>)</span>
    <span>cols</span> <span>=</span> <span>len</span><span>(</span><span>matrix</span><span>[</span><span>0</span><span>])</span>
    <span>for</span> <span>r</span> <span>in</span> <span>range</span><span>(</span><span>1</span><span>,</span> <span>rows</span><span>):</span>
        <span># Check that all columns are of equal length </span>        <span>if</span> <span>len</span><span>(</span><span>matrix</span><span>[</span><span>r</span><span>])</span> <span>!=</span> <span>cols</span><span>:</span>
            <span>raise</span> <span>ValueError</span><span>(</span><span>f</span><span>'</span><span>Row </span><span>{</span><span>r</span><span>}</span><span> has different number of columns</span><span>'</span><span>)</span>
<span>def</span> <span>validate_matrix</span><span>(</span><span>matrix</span><span>):</span>
    <span>rows</span> <span>=</span> <span>len</span><span>(</span><span>matrix</span><span>)</span>
    <span>cols</span> <span>=</span> <span>len</span><span>(</span><span>matrix</span><span>[</span><span>0</span><span>])</span>

    <span>for</span> <span>r</span> <span>in</span> <span>range</span><span>(</span><span>1</span><span>,</span> <span>rows</span><span>):</span>
        <span># Check that all columns are of equal length </span>        <span>if</span> <span>len</span><span>(</span><span>matrix</span><span>[</span><span>r</span><span>])</span> <span>!=</span> <span>cols</span><span>:</span>
            <span>raise</span> <span>ValueError</span><span>(</span><span>f</span><span>'</span><span>Row </span><span>{</span><span>r</span><span>}</span><span> has different number of columns</span><span>'</span><span>)</span>
def validate_matrix(matrix):
    rows = len(matrix)
    cols = len(matrix[0])

    for r in range(1, rows):
        # Check that all columns are of equal length         if len(matrix[r]) != cols:
            raise ValueError(f'Row {r} has different number of columns')

Enter fullscreen mode Exit fullscreen mode

The next thing I do is calculate the position of the leading (first) one in each row (or None in Python or -1 in Perl if there are no ones)


<span>leading_one</span> <span>=</span> <span>[</span><span>None</span> <span>if</span> <span>1</span> <span>not</span> <span>in</span> <span>row</span> <span>else</span> <span>row</span><span>.</span><span>index</span><span>(</span><span>1</span><span>)</span> <span>for</span> <span>row</span> <span>in</span> <span>matrix</span><span>]</span>
<span>leading_one</span> <span>=</span> <span>[</span><span>None</span> <span>if</span> <span>1</span> <span>not</span> <span>in</span> <span>row</span> <span>else</span> <span>row</span><span>.</span><span>index</span><span>(</span><span>1</span><span>)</span> <span>for</span> <span>row</span> <span>in</span> <span>matrix</span><span>]</span>
leading_one = [None if 1 not in row else row.index(1) for row in matrix]

Enter fullscreen mode Exit fullscreen mode

I then iterate over each row. If the row is all zeros, there are no further checks required, so skip it. I also check that the first non-zero number is a one.


<span>for</span> <span>row_num</span> <span>in</span> <span>range</span><span>(</span><span>len</span><span>(</span><span>matrix</span><span>)):</span>
    <span>row</span> <span>=</span> <span>matrix</span><span>[</span><span>row_num</span><span>]</span>
    <span>leading_one_pos</span> <span>=</span> <span>leading_one</span><span>[</span><span>row_num</span><span>]</span>
    <span>if</span> <span>all</span><span>(</span><span>value</span> <span>==</span> <span>0</span> <span>for</span> <span>value</span> <span>in</span> <span>row</span><span>):</span>
        <span>continue</span>
    <span>for</span> <span>value</span> <span>in</span> <span>row</span><span>:</span>
        <span>if</span> <span>value</span> <span>==</span> <span>1</span><span>:</span>
            <span>break</span>
        <span>if</span> <span>value</span> <span>!=</span> <span>0</span><span>:</span>
            <span>return</span> <span>0</span>
<span>for</span> <span>row_num</span> <span>in</span> <span>range</span><span>(</span><span>len</span><span>(</span><span>matrix</span><span>)):</span>
    <span>row</span> <span>=</span> <span>matrix</span><span>[</span><span>row_num</span><span>]</span>
    <span>leading_one_pos</span> <span>=</span> <span>leading_one</span><span>[</span><span>row_num</span><span>]</span>

    <span>if</span> <span>all</span><span>(</span><span>value</span> <span>==</span> <span>0</span> <span>for</span> <span>value</span> <span>in</span> <span>row</span><span>):</span>
        <span>continue</span>

    <span>for</span> <span>value</span> <span>in</span> <span>row</span><span>:</span>
        <span>if</span> <span>value</span> <span>==</span> <span>1</span><span>:</span>
            <span>break</span>
        <span>if</span> <span>value</span> <span>!=</span> <span>0</span><span>:</span>
            <span>return</span> <span>0</span>
for row_num in range(len(matrix)):
    row = matrix[row_num]
    leading_one_pos = leading_one[row_num]

    if all(value == 0 for value in row):
        continue

    for value in row:
        if value == 1:
            break
        if value != 0:
            return 0

Enter fullscreen mode Exit fullscreen mode

The next check I perform is to ensure that if the position of the leading one is higher than the position of the leading one of the previous row. I don’t perform this check on the first row (where row_num == 0). If the previous row doesn’t have any ones (i.e. is None), then the second rule (zeros at the end) isn’t meet.


    <span>if</span> <span>row_num</span> <span>!=</span> <span>0</span><span>:</span>
        <span>if</span> <span>leading_one</span><span>[</span><span>row_num</span> <span>-</span> <span>1</span><span>]</span> <span>is</span> <span>None</span><span>:</span>
            <span>return</span> <span>0</span>
        <span>if</span> <span>leading_one</span><span>[</span><span>row_num</span> <span>-</span> <span>1</span><span>]</span> <span>></span> <span>leading_one_pos</span><span>:</span>
            <span>return</span> <span>0</span>
    <span>if</span> <span>row_num</span> <span>!=</span> <span>0</span><span>:</span>
        <span>if</span> <span>leading_one</span><span>[</span><span>row_num</span> <span>-</span> <span>1</span><span>]</span> <span>is</span> <span>None</span><span>:</span>
            <span>return</span> <span>0</span>
        <span>if</span> <span>leading_one</span><span>[</span><span>row_num</span> <span>-</span> <span>1</span><span>]</span> <span>></span> <span>leading_one_pos</span><span>:</span>
            <span>return</span> <span>0</span>
    if row_num != 0:
        if leading_one[row_num - 1] is None:
            return 0
        if leading_one[row_num - 1] > leading_one_pos:
            return 0

Enter fullscreen mode Exit fullscreen mode

The last check I perform is to ensure that all other rows don’t have a non-zero value at the position of the leading one in the current row. The easiest way to do this is to count the number of non-zero values in this column, and check if it is one (the current row).


    <span>if</span> <span>sum</span><span>(</span><span>1</span> <span>for</span> <span>row</span> <span>in</span> <span>matrix</span> <span>if</span> <span>row</span><span>[</span><span>leading_one_pos</span><span>]</span> <span>!=</span> <span>0</span><span>)</span> <span>!=</span> <span>1</span><span>:</span>
        <span>return</span> <span>0</span>
    <span>if</span> <span>sum</span><span>(</span><span>1</span> <span>for</span> <span>row</span> <span>in</span> <span>matrix</span> <span>if</span> <span>row</span><span>[</span><span>leading_one_pos</span><span>]</span> <span>!=</span> <span>0</span><span>)</span> <span>!=</span> <span>1</span><span>:</span>
        <span>return</span> <span>0</span>
    if sum(1 for row in matrix if row[leading_one_pos] != 0) != 1:
        return 0

Enter fullscreen mode Exit fullscreen mode

If all the rows pass the checks, I’ll return 1 at the end of the loop to indicate the matrix is in reduced row echelon form.

Examples


<span>$ </span>./ch-2.py <span>"[[1, 0, 0, 1], [0, 1, 0, 2], [0, 0, 1, 3]]"</span>
1
<span>$ </span>./ch-2.py <span>"[[1, 1, 0], [0, 1, 0], [0, 0, 0]]"</span>
0
<span>$ </span>./ch-2.py <span>"[[0, 1, -2, 0, 1], [0, 0, 0, 1, 3], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]"</span>
1
<span>$ </span>./ch-2.py <span>"[[1, 0, 0, 4], [0, 1, 0, 7], [0, 0, 1, -1]]"</span>
1
<span>$ </span>./ch-2.py <span>"[[1, 0, 0, 1], [0, 1, 0, 2], [0, 0, 1, 3]]"</span>
1

<span>$ </span>./ch-2.py <span>"[[1, 1, 0], [0, 1, 0], [0, 0, 0]]"</span>
0

<span>$ </span>./ch-2.py <span>"[[0, 1, -2, 0, 1], [0, 0, 0, 1, 3], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]"</span>
1

<span>$ </span>./ch-2.py <span>"[[1, 0, 0, 4], [0, 1, 0, 7], [0, 0, 1, -1]]"</span>
1
$ ./ch-2.py "[[1, 0, 0, 1], [0, 1, 0, 2], [0, 0, 1, 3]]"
1

$ ./ch-2.py "[[1, 1, 0], [0, 1, 0], [0, 0, 0]]"
0

$ ./ch-2.py "[[0, 1, -2, 0, 1], [0, 0, 0, 1, 3], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]"
1

$ ./ch-2.py "[[1, 0, 0, 4], [0, 1, 0, 7], [0, 0, 1, -1]]"
1

Enter fullscreen mode Exit fullscreen mode

原文链接：The current echelon

展开阅读全文

文章版权声明 1、本网站名称：拾光赋
2、本站永久网址：https://www.blogs.ink
3、本网站的文章部分内容可能来源于网络，仅供大家学习与参考，如有侵权，请联系站长QQ：805375623进行删除处理。
4、本站一切资源不代表本站立场，并不代表本站赞同其观点和对其真实性负责。
5、本站一律禁止以任何方式发布或转载任何违法的相关信息，访客发现请向站长举报
6、本站资源大多存储在云盘，如发现链接失效，请联系我们我们会第一时间更新。

THE END