loading...

Daily Challenge #72 - Matrix Shift

thepracticaldev profile image dev.to staff ・1 min read

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 matrix to the beginning and shift all other indices over.

Examples:

  ['a','b','c','d']      ['h','a','b','c']
  ['1','2','3','4']  =>  ['d','1','2','3']
  ['c','o','d','e']      ['4','c','o','d']
  ['b','l','a','h']      ['e','b','l','a']
  ['d','u','d','e']      ['g','d','u','d']
  ['i','m','c','o']  =>  ['e','i','m','c']
  ['d','i','n','g']      ['c','o','d','i']
  ['h','i']      ['k','h']
  ['o','k']  =>  ['i','o']

Good luck!


This challenge comes from Jomo Pipi on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

Posted on by:

thepracticaldev profile

dev.to staff

@thepracticaldev

The hardworking team behind dev.to ❤️

Discussion

pic
Editor guide
 

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
 

pretty esoteric but interesting! 🥴🥴🥴

 

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

 

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:

  1. Flatten the matrix.
  2. Take the n last elements and prepend them to the beginning of the list.
  3. 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" ]
 

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

 

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

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

 

F#, slightly naive in that it assumes input is well-formed.

module DailyChallenge

let shiftMatrix (m : 'a list list) (n : int) =
    let flattend = List.concat m
    let split = flattend.Length - n
    flattend.[split..] @ flattend.[0..split - 1]
    |> List.chunkBySize m.[0].Length

Tests:

module DailyChallengeTest

open FsUnit.Xunit
open Xunit
open DailyChallenge

[<Fact>]
let ``shift 4x4 matrix by 1``() =
    let m =
        [ [ 'a'; 'b'; 'c'; 'd' ]
          [ '1'; '2'; '3'; '4' ]
          [ 'c'; 'o'; 'd'; 'e' ]
          [ 'b'; 'l'; 'a'; 'h' ] ]

    let expected =
        [ [ 'h'; 'a'; 'b'; 'c' ]
          [ 'd'; '1'; '2'; '3' ]
          [ '4'; 'c'; 'o'; 'd' ]
          [ 'e'; 'b'; 'l'; 'a' ] ]

    shiftMatrix m 1 |> should equal expected

[<Fact>]
let ``shift 4x3 matrix by 1``() =
    let m =
        [ [ 'd'; 'u'; 'd'; 'e' ]
          [ 'i'; 'm'; 'c'; 'o' ]
          [ 'd'; 'i'; 'n'; 'g' ] ]

    let expected =
        [ [ 'g'; 'd'; 'u'; 'd' ]
          [ 'e'; 'i'; 'm'; 'c' ]
          [ 'o'; 'd'; 'i'; 'n' ] ]

    shiftMatrix m 1 |> should equal expected

[<Fact>]
let ``shift 2x2 matrix by 3``() =
    let m =
        [ [ 'a'; 'b' ]
          [ 'c'; 'd' ] ]

    let expected =
        [ [ 'b'; 'c' ]
          [ 'd'; 'a' ] ]

    shiftMatrix m 3 |> should equal expected
 

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());
}                                                                          
 

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"]
 

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
 

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
        ]
 

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)