This tutorial shows you how to leverage some of PHP’s functional programming abilities.
This is just a simple solution to Problem 22 from ProjectEuler.net, but it’s a good example of showing how to use a hybrid of OOP and Functional Programming to arrive at the correct solution.
We’ll use basic OOP for the structure and for encapsulation, and then we’ll implement the actual solution using the infamous Map Reduce pattern.
Here’s a look at the full implementation, then we’ll go over each piece individually.
ProjectEuler.net Problem 22
namespace ProjectEuler\Problems;
class Problem22
{
private $inputData = array();
function __construct()
{
$filename = "./p022_names.txt";
$this->readInCsv($filename);
// Would never do this. Only invoking from the
// constructor for brevity since not a real app.
//
// Invoking methods on this class should
// come from your controllers.
// And a class with this type of logic would be classified
// as domain logic, aka *business logic*.
//
// This "business logic" should be structured as
// Domain Objects (or a service depending
// on reusability) in your application as
// part of your Model *layer*.
$result = $this->mapReduce();
$this->displayResult($result);
}
private function readInCsv($filename)
{
$handle = fopen($filename, "r");
$this->inputData = fgetcsv($handle, 0, ",");
fclose($handle);
sort($this->inputData);
}
private function mapReduce()
{
$nameTotal = array_map(function($name, $index) {
$charsTotal = array_reduce(str_split($name),
function($runningCharTotal, $char) {
// calculate value by offsetting from capital
// ascii char values to get sequential values
$runningCharTotal += ord(strtoupper($char)) - 64;
return $runningCharTotal;
});
// return the name position
// multiplied by the name's char total
return ($index + 1) * $charsTotal;
}, $this->inputData, array_keys($this->inputData));
$total = array_reduce($nameTotal,
function($runningNameTotal, $item) {
$runningNameTotal += $item;
return $runningNameTotal;
});
return $total;
}
private function displayResult($result)
{
echo 'The total is: ';
print_r($result);
}
}
First we’ll take a look at how to read in data from our .txt file.
The readInCsv method uses fopen to open the file, bind it to a data stream, and then fgetcsv parses each line (using commas as the delimiter) into an array.
This array is then sorted alphabetically using one of the native PHP sorting algorithms (I believe it’s an implementation of QuickSort for those wondering)
private function readInCsv($filename)
{
$handle = fopen($filename, "r");
$this->inputData = fgetcsv($handle, 0, ",");
fclose($handle);
sort($this->inputData);
}
Next, after we have our input file data read into an array, we do some functional programming magic using array_map, array_reduce, and anonymous functions (lambdas).
Let’s look at array_map
In functional programming a map function takes an array and a *callback function* as input (and other *optional* arguments, but we’ll leave that out for brevity) and then performs a transformation (functionality/algorithm) specified in the callback function on every element in the array. The new values calculated for each element are added to a new array.
Now, for our heavy hitter… array_reduce
In functional programming a reduce function starts with an initial value and passes this initial value to the callback function. The initial value plus the first element in the array is passed to the callback function and the callback function’s functionality is performed.
After this callback functionality completes, the data returned is now passed to the callback function again. The functionality is performed again with the data return from the previous call, and the *second* element in the array. The data accumulates with each call.
This continues through each element in the array until the last element completes. When done a single value/object/etc (meaning the array was reduced to its last element) is returned.
Confused?
Simple pseudo code example:
array intExample = [1, 2, 3, 4]
result = reduce(intExample, "callback")
function callback(previous, current)
{
previous *= current
return previous
}
The output of the above looks like:
2 = (1 * 2)
6 = (2 * 3)
24 = (6 * 4)
So the array [1, 2, 3, 4] was reduced to 24.
**NOTE: If no initial value is given, NULL is passed, and the reduce starts with the array’s first element as the initial value (like above).
Using both map and reduce together:
$nameTotal = array_map(function($name, $index) {
$charsTotal = array_reduce(str_split($name),
function($runningCharTotal, $char) {
// calculate value by offsetting from capital
// ascii char values to get sequential values
$runningCharTotal += ord(strtoupper($char)) - 64;
return $runningCharTotal;
});
// calculate a name total, which is
// (name position * name's char total)
return ($index + 1) * $charsTotal;
}, $this->inputData, array_keys($this->inputData));
**NOTE: The callback function does not have to be defined inline, nor does it have to be an anonymous function. We could have just as easily defined the function:
Callback Function
function callBackAction($name, $index)
{
// Do stuff...
}
And then passed the callback like:
$names = array("Name", "AnotherName");
array_map("callBackAction", $names);
However, it’s much easier to read (and cleaner) using an anonymous function instead.
**NOTE: Our parameters used in our callback functions are implicitly passed as arguments from the previously returned result (previous) from the callback.
Now… Why str_split?
Since array_reduce only takes an array as the datatype, we create one on the fly using PHP’s str_split.
str_split is just a quick (and dirty?) way of taking a string and storing each character as an element in an array, which is exactly what we want to do, in order to reduce on it.
Now… I know what you’re probably thinking..
WTF does the following mean? 🙂
$runningCharTotal += ord(strtoupper($char)) - 64;
Well….
Since we want the sequential value of each character in a name, we need a quick and non super hacky way of doing this.
To do this, we just use ord() to get the ASCII value of a character. However, before passing the value to ord() we first want to convert (or make sure) our character is uppercase using strtoupper(), and then offset it by 64.
Offsetting by 64 gives us the sequential value for that character.
For example, suppose we have the lowercase character ‘a’.
First we convert ‘a’ to the capital character ‘A’ using strtoupper(), and then pass ‘A’ to ord().
ord() will return ‘A’ in ASCII (under base 10), which equals 65.
Then if we offset this by 64, the character ‘A’ will give us decimal 1, and ‘B’ will give us decimal 2, and ‘C’ decimal 3, and so on…
Now let’s look at our return.
The return is straight forward.
We need an easy way to calculate our row value in our rowValue * nameValue = totalNameValue calculation. In order to do this, we pass our array to PHP’s array_keys(), which will give us access to each indice in our array during the reduce.
**NOTE: Just a heads up if you didn’t notice. PHP has yet another annoying quirk with it’s naming consistency of the parameters for the array_map and array_reduce signatures.
With array_map the callback is the first parameter, with the second the array, where as in array_reduce the array is supplied first, and then the callback second…. grrrrr….
>> I know.. I know..
>> *insert non PHP developers mocking tone of voice here*
>> Somethin.. Somethin.. PHP is the *worst* language.. Somethin.. Somethin..
>> *now insert PHP developers mocking tone of voice here*
>> Somethin.. Somethin.. Don’t care about the language.. I just use the right tool for the job.. Somethin.. Somethin..
😀
Calculating the Overall Total
$total = array_reduce($nameTotal,
function($runningNameTotal, $item) {
$runningNameTotal += $item;
return $runningNameTotal;
});
return $total;
}
Our final reduce is straight forward as well. The accumulator and each element perform a summation and the total returned is the solution.
Output the solution and that’s it! 😀