A little known function, with not too many use cases, but a powerful and elegant tool to have in your belt.

The transpose function takes a multi-dimensional array, and switches the row indices with the column indices. A visualisation might explain things more clearly:

Consider we have a 2D array of columns 1 to 4 and rows A to D:

A1 A2 A3 A4
B1 B2 B3 B4
C1 C2 C3 C4
D1 D2 D3 D4

By transposing that array we end up with the following:

A1 B1 C1 D1
A2 B2 C2 D2
A3 B3 C3 D3
A4 B4 C4 D4

It's the same data, but the columns and rows have been switched around.

Use cases

We used this in a code kata last week, the exercise was to convert an ascii representation of digits and transform that to a string of numbers e.g.

 _     _  _ 
| |  | _| _|
|_|  ||_  _|

becomes "0123"

Each number is 4 lines tall and three characters wide (space, pipe or underscore only).

Here is the pseudo code and steps for how we solved this:

Split the ascii string into lines

[
    " _     _  _ ",
    "| |  | _| _|",
    "|_|  ||_  _|",
    "            ",
]

Map over each line, splitting the line into an array of strings of length 3

[
    [ " _ ", "   ", " _ ", " _ " ],
    [ "| |", "  |", " _|", " _|" ],
    [ "|_|", "  |", "|_ ", " _|" ],
    [ "   ", "   ", "   ", "   " ],
]

Transpose the array, so we have an array of ascii characters

[
    [ " _ ", "| |", "|_|", "   " ], // zero
    [ "   ", "  |", "  |", "   " ], // one
    [ " _ ", " _|", "|_ ", "   " ], // two
    [ " _ ", " _|", " |_", "   " ], // three
]

Lets map over and concat the above into an array of strings

[
    " _ | ||_|   ", // zero
    "     |  |   ", // one
    " _  _||_    ", // two
    " _  _| |_   ", // three
]

Now we have an array of chars in string form we can use this to lookup the numeric value from a hash map.

function lookup ($ascii)
{
    $asciiMap = [
        " _ | ||_|   ",
        "     |  |   ",
        " _  _||_    ",
        " _  _| _|   ",
        "   |_|  |   ",
        " _ |_  _|   ",
        " _ |_ |_|   ",
        " _   |  |   ",
        " _ |_||_|   ",
        " _ |_| _|   ",
    ];

    if (false !== $n = array_search($ascii, $asciiMap)) {
        return (string) $n;
    }
}

If we map our lookup function over our previous strings we get

[
    "0",
    "1",
    "2",
    "3",
]

Hopefully you can see now that we just need to concat the above array to return our final result

"0123"

et voilà!

Some more solutions to the kata above, implemented in Haskell, JavaScript and PHP. http://github.com/petemcfarlane/ascii-number-ocr-kata PRs in other languages welcome!

If you're using a language without the transpose function, you may have to write something like this:

$rows = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
];

function transpose ($rows)
{
    $temp = [];

    foreach ($rows as $r => $columns) {
        foreach ($columns as $c => $value) {
            $temp[$c][$r] = $value;
        }
    }

    return $temp;
}

or you could just pull in a function from another library, e.g. PHP 😉

Another use case for transpose, for cleaning up form input, by Adam Wathan: http://adamwathan.me/2016/04/06/cleaning-up-form-input-with-transpose/

Have you ever needed to group an array of data in PHP and had to write awkward loops or array_reduce code to accomplish this?

I've created a small package (just one function actually) and published it on Packagist.com so you can conveniently install it into your PHP applications with Composer.

composer install group-by/group-by

It adds a grouping functionality to arrays, allowing you to group by passing each item in the array to a callback.

Here's how you might want to use it:

<?php

use function GroupBy\groupBy;

// $students in an array of `stdClass Object`
$students = [
    (object) ['name' => 'adam', 'year' => '10'],
    (object) ['name' => 'becky', 'year' => '12'],
    (object) ['name' => 'chris', 'year' => '11'],
    (object) ['name' => 'deborah', 'year' => '10'],
    (object) ['name' => 'edward', 'year' => '12'],
];

$groupByYear = function ($student) {
    return $student->year;
};

$groupedByYear = groupBy($students, $groupByYear);

/*
$groupedByYear is now equal to
[
    [10] => [
        [0] => stdClass Object
            (
                [name] => adam
                [year] => 10
            )
        [1] => stdClass Object
            (
                [name] => deborah
                [year] => 10
            )
        ]
    [12] => [
        [0] => stdClass Object
            (
                [name] => becky
                [year] => 12
            )
        [1] => stdClass Object
            (
                [name] => edward
                [year] => 12
            )
        ]
    [11] => [
        [0] => stdClass Object
            (
                [name] => chris
                [year] => 11
            )
    ]
]
*/

You could also group an array of arrays, like so:

<?php

use function GroupBy\groupBy;

$numberList = [1, 2, 3, 4, 5, 987, 554, 32];

// The array item value will be passed to the callback.
$oddOrEven = function ($n) {
    return $n % 2 == 0 ? 'even' : 'odd';
};

$oddAndEven = groupBy($numberList, $oddOrEven);

/*
$oddAndEven is now equal to
[
    'odd' => [1, 3, 5, 987],
    'even' => [2, 4, 554, 32],
];
*/

If you are grouping a group of arrays by a sub array key, you can just pass the string value of that key, like so:

<?php

use function GroupBy\groupBy;

$students = [
    ['name' => 'adam', 'year' => '10'],
    ['name' => 'becky', 'year' => '12'],
    ['name' => 'chris', 'year' => '11'],
    ['name' => 'deborah', 'year' => '10'],
    ['name' => 'edward', 'year' => '12'],
];

$groupedByYear = groupBy($students, 'year');

/*
$groupedByYear is equal to
[
    10 => [
        ['name' => 'adam', 'year' => '10'],
        ['name' => 'deborah', 'year' => '10'],
    ],
    11 => [
        ['name' => 'chris', 'year' => '11'],
    ],
    12 => [
        ['name' => 'becky', 'year' => '12'],
        ['name' => 'edward', 'year' => '12'],
    ],
]
*/

I have been using Haskell and Scala more recently and have found these groupBy methods very useful. I'm surprised I couldn't find a simple way to do this in PHP, so hopefully this will be useful to other people too.

Let me know if you like it or have any suggestions to improve it.

Last week at the Leeds Code Dojo I was introduced to a dynamic programming problem often referred to as the minimum change problem or coin problem. The premise is:

Given an infinite supply of coins of different values, what is the least amount of coins you will need to make a desired amount of change.

As an example using British Pound Sterling (where we have coins of value 1, 2, 5, 10, 20, 50 and 100 pence), whats the fewest coins required to make 14p. Some possible options are:

• [1,1,1,1,1,1,1,1,1,1,1,1,1,1]
• [2,2,2,2,2,2,2]
• [5,5,2,2]
• [10,2,2]

There are more combinations possible, this is just illustrative. The solution using the least number of coins is [10,2,2] = 3 coins.

The greedy solution

The first solution uses a greedy algorithm, so subtracts the largest coin and so on, so in the above example take 10 from 14, leaving 4, then take 2 and take 2 again. This seems to work in this case but for some currencies where the denomination has different values, such as Lilliputian coins [1,4,15,20,50] this doesn't always work. Take 23 for example. The greedy algorithm would choose 20 first as the biggest coin that fits the change, then require 3 x 1 coins, totaling 4 [20,1,1,1]. But [15,4,4] also totals 23 and in one fewer coin!

The recursive solution

A more correct solution uses recursion to find the minimum number of coins required to get to the target value (minus the value of some coin).

minNumCoins :: [Int] -> Int -> Int
minNumCoins coins target = map numCoins [0..] !! target
    where
        numCoins 0 = 0
        numCoins i | i `elem` coins = 1
        numCoins i = minimum [1 + minNumCoins coins (i-c) | c <- coins, c < i]

I will try to briefly describe what each line is doing

minNumCoins :: [Int] -> Int -> Int
minNumCoins coins target = map numCoins [0..] !! target
    where numCoins = ...

The first line is defining the method signature. It takes a list of coins of type [Int] and a target change value of type Int and returns the minimum number of coins, also an Int.

In the second line I am mapping a function numCoins over an infinite list [0..], then extracting the value using the !! index function, returning the value from the resulting list at target. I can use an infinite list because Haskell is lazy, and won't actually commute the next list elements value until the last possible moment. So although in theory it is infinite, it will stop at the target value.

    where
        numCoins 0 = 0
        numCoins i | i `elem` coins = 1
        numCoins i = ...

Then comes the numCoins method. The first two cases capture the edge cases. If the index value is 0, return 0. If the index matches the value of one of our coins then just return 1, for 1 coin.

        numCoins i = minimum [1 + minNumCoins coins (i-c) | c <- coins, c < i]

And then the final case, if the other two statements are not matched. minimum selects the minimum value from a list. The list in our case comes from the list comprehension [1 + minNumCoins coins (i-c) | c <- coins, c < i]. This maps through each of our list of coins as c (the c <- coins part), then filters the coins that are less than the value we are trying to find i (in c < i). For each value of c resulting, we're mapping it through 1 + minNumCoins coins (i-c). This is the recursive part of our solution - we're calling minNumCoins again but this time not with our original target, but with our target less the value of a coin (i-c), and adding 1 to compensate for the fact that we are adding some coin.

This works and will give us the correct answer, but it is not very efficient because for large numbers there may be lots of paths it has to go back through and re-calculate.

Dynamic Programming

An even better solution that is still correct but more efficient, uses memoization to cache the result of each method call so it doesn't have to recursively look through the numCoins for every value. In some languages this is done by creating an array the size of the target value, and working out the value for each step in between going up to the target. Haskell provides a better way, using a lazy array. If we refer to the array from inside our function, and the array refers to other points in itself, Haskell will only compute each step value once, and remember that for us.

import Data.Array

minNumCoins :: [Int] -> Int -> Int
minNumCoins coins target = lookup ! target
    where
        lookup = listArray (0, target) $ map numCoins [0..]
        numCoins 0 = 0
        numCoins i | i `elem` coins = 1
        numCoins i = minimum [1 + lookup ! (i-c) | c <- coins, c < i]

Not much has changed, but we are now selecting the target from a lookup value. This is instantiated as an array the size of our target value, and filled from mapping over the numCoins [0..] infinite list. Instead of recursively calling the minNumCoins method on the last line, we can simply select the value from our lookup array. This provides us with huge performance gains for looking up large values.

Further reading

• Dynamic Programming - Python
• Lazy Dynamic Programming - Haskell
• Leeds Code Dojo - Dynamic Programming