DEV Community

Daily Challenge #72 - Matrix Shift

dev.to staff on September 20, 2019

Write a function that will shift a matrix n times. You will be given a rectangular matrix called m and must bring n characters at the end of the ...

Read full post

Michael Baas • Sep 20 '19

I think the 2nd example is wrong...

And the solution in APL (Dyalog APL) is:

shift←{(⍴⍵)⍴(-⍺)⌽,⍵}

The left argument is the number of characters to shift and the right argument is the matrix. The approach (read from right to left) is as follows:

ravel (flatten) the argument (using monadic ,)
rotate the resulting vector by ⍺ characters
reshape the vector to the original shape of the argument

Test cases:

      1 shift 2 2⍴'hiok'
kh
io


      2 shift 3 4⍴'dudeimcoding'
ngdu
deim
codi

      1 shift 4 4⍴'abcd1234codeblah'
habc
d123
4cod
ebla

@nobody • Sep 20 '19

pretty esoteric but interesting! 🥴🥴🥴

Amin • Sep 20 '19

Yes indeed, the second example is wrong, I just noticed that when doing the unit tests!

Avalander • Sep 20 '19 • Edited

Haskell

shift :: Int -> [String] -> [String]
shift n m =
  foldr unflatten [""] shifted
  where
    columns  = length $ head m
    flat_m   = concat m
    split_at = (length flat_m) - n
    shifted  = (drop split_at flat_m) ++ (take split_at flat_m)
    unflatten :: Char -> [String] -> [String]
    unflatten y (x:xs)
      | length x == columns = [y] : x : xs
      | otherwise           = ([y] ++ x) : xs

Basically the algorithm is as follows:

Flatten the matrix.
Take the n last elements and prepend them to the beginning of the list.
Unflatten the matrix.

-- In haskell strings are lists of chars, so "abcd" is the same as ['a','b','c','d'] but shorter to type.
shift 1 [ "abcd", "1234", "code", "blah" ]
-- [ "habc", "d123", "4cod", "ebla" ]

@nobody • Sep 20 '19

simple. 👍🏿
i still feel like Haskell has too many non-alpha characters in the syntax set. 🙄

Avalander • Sep 20 '19

Haha, yeah, it's marginally easier once you get used to them though.

@nobody • Sep 25 '19

i'll take your word for it and stay in my (((safe (space)))) for now . . .
🤗

Oleksii Filonenko • Sep 20 '19 • Edited

Rust:

fn shift<T: Clone>(matrix: Vec<Vec<T>>, n: usize) -> Vec<Vec<T>> {
    match matrix.get(1).map(|row| row.len()) {
        None => matrix,
        Some(len) => {
            let mut flat = matrix.into_iter().flatten().collect::<Vec<_>>();
            flat.rotate_right(n);
            flat.chunks_exact(len).map(|chunk| chunk.to_vec()).collect()
        }
    }
}

The match allows for this test to pass:

#[test]                                                                    
fn test_empty_1() {                                                        
    assert_eq!(shift(Vec::<Vec<char>>::new(), 1), Vec::<Vec<char>>::new());
}

André Adriano • Sep 20 '19

Javascript


function mxShift(matrix) {
    const flat = matrix.flat();
    const shiftedFlat = [
        ...matrix.flatMap((d,i) => i === 0 ? [flat.pop(), ...d] : d)
    ].slice(0, flat.length+1);

    const newMatrix = [];
    while (shiftedFlat.length > 0) {
        newMatrix.push(shiftedFlat.splice(0, matrix[0].length));
    }

    return newMatrix;
}

mxShift(a);
// 0: (4) ["h", "a", "b", "c"]
// 1: (4) ["d", "1", "2", "3"]
// 2: (4) ["4", "c", "o", "d"]
// 3: (4) ["e", "b", "l", "a"]

mxShift(b);
// 0: (4) ["g", "d", "u", "d"]
// 1: (4) ["e", "i", "m", "c"]
// 2: (4) ["o", "d", "i", "n"]

mxShift(c);
// 0: (2) ["k", "h"]
// 1: (2) ["i", "o"]

Melvin Yeo • Sep 22 '19

In Python, using list splicing to shift the matrix and extract part of the flattened list to reconstruct the matrix.

def matrix_shift(matrix, shift_count):
    concat_list = [elem for row in matrix for elem in row]
    concat_list = concat_list[-shift_count:] + concat_list[:-shift_count]

    if shift_count == len(concat_list):
        return matrix

    height = len(matrix)
    width = int(len(concat_list) / height)

    result = []
    for i in range(0, height):
        result += [concat_list[(i * width):(i * width)+width]]

    return result

dillan teagle • Sep 20 '19

quick python solution and headache for the rest of the day


def shift_matrix(matrix):
    arr = [i for row in matrix for i in row]
    print(arr)
    result = sorted(arr, key=lambda x: x == arr[-1], reverse=True)]
    return result


m = [['d','u','d','e'], ['i','m','c','o'], ['d','i','n','g']]
shift_matrix(m)

Amin • Sep 20 '19

Elm

module MatrixShift exposing (matrixShiftRight)


split : Int -> List anything -> List (List anything)
split count list =
    case list of
        [] ->
            []

        _ ->
            let
                toAppend : List anything
                toAppend =
                    List.take count list

                newList : List anything
                newList =
                    List.drop count list

            in
                toAppend :: (split count newList)


headLength : List (List anything) -> Int
headLength list =
    list
        |> List.head
        |> Maybe.withDefault []
        |> List.length


matrixShiftRight : List (List Char) -> List (List Char)
matrixShiftRight matrix =
    let
        concatenated : List Char
        concatenated =
            List.concat matrix

        reversed : List Char
        reversed =
            List.reverse concatenated

        last : Char
        last =
            List.head reversed
                |> Maybe.withDefault ' '
    in
    reversed
        |> List.drop 1
        |> List.reverse
        |> (++) [ last ]
        |> split (headLength matrix)

Tests

module MatrixShiftTest exposing (suite)

import Expect exposing (equal)
import MatrixShift exposing (matrixShiftRight)
import Test exposing (Test, describe, test)


suite : Test
suite =
    describe "Matrix Shift"
        [ test "It should return the array shifted #1" <|
            \_ ->
                let
                    input =
                        [ [ 'a', 'b', 'c', 'd' ]
                        , [ '1', '2', '3', '4' ]
                        , [ 'c', 'o', 'd', 'e' ]
                        , [ 'b', 'l', 'a', 'h' ]
                        ]

                    output : List (List Char)
                    output =
                        [ [ 'h', 'a', 'b', 'c' ]
                        , [ 'd', '1', '2', '3' ]
                        , [ '4', 'c', 'o', 'd' ]
                        , [ 'e', 'b', 'l', 'a' ]
                        ]
                in
                equal output <| matrixShiftRight input
        , test "It should return the array shifted #2" <|
            \_ ->
                let
                    input =
                        [ [ 'h', 'i' ]
                        , [ 'o', 'k' ]
                        ]

                    output : List (List Char)
                    output =
                        [ [ 'k', 'h' ]
                        , [ 'i', 'o' ]
                        ]
                in
                equal output <| matrixShiftRight input
        , test "It should return the array shifted #3" <|
            \_ ->
                let
                    input : List (List Char)
                    input =
                        [ [ 'd', 'u', 'd', 'e' ]
                        , [ 'i', 'm', 'c', 'o' ]
                        , [ 'd', 'i', 'n', 'g' ]
                        ]

                    output : List (List Char)
                    output =
                        [ [ 'g', 'd', 'u', 'd' ]
                        , [ 'e', 'i', 'm', 'c' ]
                        , [ 'o', 'd', 'i', 'n' ]
                        ]
                in
                equal output <| matrixShiftRight input
        ]