DEV Community: Matt Edwards

Towards fluency in JavaScript and other programming languages

Matt Edwards — Sun, 26 Nov 2023 09:22:35 +0000

The joys of language

The English language is endlessly amusing. For example, if the opposite of interior is exterior it surely follows that the opposite of increment must be excrement ... right?

Wrong!

For this and many other reasons I have been fascinated by language for as long as I can remember. At school in year 7 we were taught one lesson a week of Linguistics, which is essentially the study of language. In the end of year exam I scored 98%. It's fair to say, I have always been a linguistic nerd and I went on to study French and German at A-Level. So I know a little about learning languages.

The journey from clunky to fluent

Imagine a native English speaker learning German. In the early stages of the learning process, it's natural to think of a phrase in English and, in ones mind, systematically translate that phrase word-for-word into German.

That process...

think in English
translate the words to German
output the German phrase

...is inefficient and becomes a barrier to fluency. The only way to become fluent in a language is to think in that language. Then you can skip the first two steps in the clunky process above and jump straight to output the German phrase.

Fluency to that extent really only comes after interacting with a language day after day for an extended period.

So what does that have to do with software?

The other day an email arrived from a mailing list that I subscribed to a few years ago. The email was part of a series aimed at junior software engineers preparing for technical interviews. It included an example of the kind of coding exercise that a junior engineer might face. In this case: write a function that takes a string as a parameter and determines whether that string is a pallindrome.

A pallindrome is a word, phrase or expression that reads the same backwards as it does forwards. So, if we assume the function is called isPallindrome():

isPallindrome('level') // should return true

isPallindrome('lever') // should return false

The example solution in the email looked like this:

function isPallindrome(str) {
  let reversedString = '';

  for (let i = str.length - 1; i >= 0; i--) {
    reversedString += str[i];
  }

  if (reversedString === str) {
    return true;
  } else {
    return false;
  }
}

Similarities with learning a spoken language

This made me think about my own evolution as a programmer and the parallels that exist between the twin processes of learning a computer language (JavaScript in this example) and learning a spoken language.

The example solution shown here looks like something I might have written in the early days of my programming journey - the email that contained it was, after all, part of a series of emails aimed at junior software engineers. You can quite clearly discern three steps that line up quite accurately with the three steps in the translation process for a novice German speaker outlined above:

think through the logic
translate that flow of logic to steps in a program
write those steps in your chosen language

That step-by-step logic is most evident in the conditional statement that determines the returned value. The flow of logic runs something like this:

compare the two strings
if they are the same, the input must be a pallindrome, so we should return true
otherwise, the input is not a pallindrome, so we should return false

Translating that step-by-step into JavaScript yields this conditional statement:

if (a === b) {
  return true;
} else {
  return false;
}

Towards fluency - understanding the comparison operator

Going back to the German language example above, I suggested that, in order to become fluent in German, it's necessary to be able to think in German. What that really means is you need to process language the way that a native German speaker processes language.

The same applies when writing a computer language. To become fluent we have to learn to process the language within the context of its built-in rules & structures.

Let's examine one of the most fundamental structures of any programming language: the comparison operator. There is one included in the conditional statement above.

The triple equals is a comparison operator and a === b is a comparison operation. It is asking JavaScript to:

compare the expression on the left of the comparison operator
with the expression on the right of the comparison operator
and let us know if they are the same

A comparison operation evaluates to either true or false, as this Node REPL output demonstrates:

As an aside, there is a subtle difference in JavaScript between the double & triple equals comparison operators. That's not relevant to this post but you can read more about it in MDN Web Docs

Shortcut the return statement

Look again at what the comparison operator is asking JavaScript to do. And compare that to the step-by-step logic that was translated into the conditional statement. You will notice that they do the same thing. In that case, one of them must be redundant in the conditional statement set out above.

This tells us that we don't need to construct a conditional statement that returns a boolean because the comparison operation, that is a part of every conditional statement, already evaluates to a boolean.

So we can replace...

if (a === b) {
  return true;
} else {
  return false;
}

with...

return a === b;

Conclusion

'Word-for-word' translation might well get the job done. But the better understanding of the fundamental structures of a language that comes with experience and practice (otherwise known as fluency) enables us to produce more efficient, concise code.

The way that reversedString is determined in the example solution could be refactored a little too but I will leave you to ponder that one yourself.

Grokking Algorithms in JavaScript - Part 3

Matt Edwards — Sat, 15 Jan 2022 16:02:34 +0000

In Part 2 of this series I introduced graphs. A graph is a representation of connections between nodes in a network. The connections between the nodes are called 'edges'. For example, in a geographical network nodes might be towns and edges might be the roads that connect the towns.

I also introduced you to the breadth-first search ("BFS") algorithm: a means to find the shortest route through a graph. In the context of BFS, shortest route means the route that visits the fewest nodes. In this article I will add a little complexity to graphs by adding "weights" and introduce Dijkstra's Algorithm which will find the shortest route through these more complex weighted graphs.

Weighted graphs

Imagine a graph with nodes representing cities (Manchester, Birmingham, Milton Keynes, London & Edinburgh) and the edges between them representing railway tracks.

Here is a picture of that graph.

You want to get from Manchester to London by train. Which route should you take? Well, we know that BFS will find the shortest path so we feed the graph into the algorithm, set it running, and it confidently tells us to go via Edinburgh.

Ok, that's the route to take if you want the fewest stops - which is what BFS tells you - in the context of BFS, shortest route means the route that visits the fewest nodes.

Let's add distances between cities:

Now we can see quite clearly what we already knew: the shortest route is via Birmingham & Milton Keynes at 200 miles rather than the 610 miles via Edinburgh.

In graph terminology the numbers that represent the distance between nodes are the weights of those edges. Weights don't have to represent distance. It could represent the cost of getting from one node to the next, for example.

If you want to find the shortest path in a weighted graph, BFS simply won't cut the mustard. You need another graph algorithm: you need Dijkstra's algorithm, named after computer scientist Edsger Dijkstra who conceived of the idea about 65 years ago.

Dijkstra's will find the cheapest / shortest path (in other words, the one with the lowest combined edge weights) in a weighted graph.

For example:

nodes on a geographical graph - Dijkstra's will find the shortest route, like the example above.
nodes in a graph of transactions - Dijkstra's will find the lowest cost chain of transactions.

Dijkstra's - the steps

Set up a list of all nodes. The list will hold the cumulative weight of getting to that node. If you can't yet calculate the cumulative weight because your route hasn't yet reached that node, give it a cumulative weight of positive infinity (this may sound odd but it's an integral part of the algorithm's workings)
From the current node, find the lowest cost node. ie. the node you get to by following the lowest weight edge
For all neighbours of that node check if there is a lower cumulative-weight way to get there. If so, update that node's cumulative weight in the list that you set up at the outset. (Remember, any nodes where you can't calculate the cumulative weight from the current node have an infinite cumulative weight)
Repeat until you have done this for every node in the graph.
Then calculate the final path.

Clarification of the values that are being recorded here

In the steps above you will notice that there are two different weight-related values. It's worth spending a moment to think those values through.

Edge weights - this is the "cost" of travelling from one node to another along that particular edge. An edge's weight is a fixed value: it never changes throughout the progress of the algorithm.

Node cumulative weights - these are the values held in the list that was set up at the start. For a given node, this is the cumulative weight of all of the edges along which you have to travel to get to a specific node if you follow the lowest cost route that the algorithm has calculated so far. These values are updated as the algorithm processes the nodes in the graph.

Dijkstra's - initial setup

We need a graph to work with. Here is a simple example that the remainder of this article will refer to:

As we discovered with BFS, setting up the required data structures represents a significant part of the work in graph algorithms.

The graph

First we need a hash table to represent the graph. In BFS each node was a key in the hash table and its value was an array of the node's neighbours. The graph we are building here has an extra data point for every connection: the weight of the edge. To cater for that each node in the hash table will hold its own hash table (as opposed to the simple array in BFS).

The slightly confusing explanation in that previous paragraph will hopefully become clearer when you look at the code below. Again I am using JavaScript's Map() object as a hash table.

const graph = new Map();
graph.set("start", new Map());
graph.get("start").set("a", 6);
graph.get("start").set("b", 2);
graph.set("a", new Map());
graph.get("a").set("fin", 1);
graph.set("b", new Map());
graph.get("b").set("a", 3);
graph.get("b").set("fin", 5);
graph.set("fin", new Map());

Cumulative node weights

Next we need a structure to keep track of the cumulative weight of every node. Again a Map() is the perfect data structure:

costs.set("a", 6);
costs.set("b", 2);
costs.set("fin", Number.POSITIVE_INFINITY);

Notice how the "fin" node has a cumulative cost of POSITIVE_INFINITY (a JavaScript constant). From the start node, we can't "see" the route to the finish node - all we know is that going to A "costs" 6 and going to B "costs" 2. Remember, any nodes where you can't calculate the cumulative weight from the current node have an infinite cumulative weight.

Parents

There is one data requirement that hasn't been mentioned yet. As the algorithm traces its way through the graph, plotting the "lowest cost" route, we need to keep track of that route. Dijkstra's does that by, for every node, keeping track of the previous node in the path. So every node (apart from the start node) will have a "parent" node.

Every node's parent is recorded in a parents hash table (or Map() in JavaScript). At the outset it looks like this:

const parents = new Map();
parents.set("a", "start");
parents.set("b", "start");
parents.set("fin", null);

Every time a node's cumulative weight is updated (because a lower cost path has been found) the parent for that node also needs to be updated.

Notice that the "fin" node's parent starts out having a null value. That's because we won't know that node's parent until the routing process has got that far.

Processed nodes

And the last part of the data structure setup - to avoid loops we need to keep track of nodes already visited. That just takes the form of an array called processed.

const processed = [];

Processing the graph

Now that we have the initial data structures set up we can start processing the graph.

Lowest cost node

The first activity on arriving at a new node is to find the lowest cost node that hasn't already been processed because that node will be the next one to visit. Remember that all nodes (apart from immediate neighbours of start) were initially assigned a cumulative weight of infinity and those figures are only updated as we visit their neighbours. So, ignoring nodes that have already been processed (held in the processed array), the lowest cost node will automatically be a neighbour of the node we are currently processing and we just need to loop through all nodes in the costs hash table and do a comparison.

The findLowestCostNode() function looks like this:

function findLowestCostNode(costs) {
  lowestCost = Number.POSITIVE_INFINITY;
  lowestCostNode = null;
  costs.forEach((cost, node) => {
    if (cost < lowestCost && !processed.includes(node)) {
      lowestCost = cost;
      lowestCostNode = node;
    }
  });
  return lowestCostNode;
}

Graph traversal

We have set up the data structures and we have a function to decide which node to visit next. Now we just need to loop through the nodes and carry out the steps outlined above. Below is the code that achieves that:

let node = findLowestCostNode(costs);
while (node) {
  const nodeCost = costs.get(node);
  const neighbours = graph.get(node);
  neighbours.forEach((cost, neighbour) => {
    newNodeCost = nodeCost + cost;
    if (costs.get(neighbour) > newNodeCost) {
      costs.set(neighbour, newNodeCost);
      parents.set(neighbour, node);
    }
  });
  processed.push(node);
  node = findLowestCostNode(costs);
}

We have to define the first lowest cost node (ie. a neighbour of the start node) before entering the while loop because 'node' being truthy is the while loop condition. The lowest cost node is then updated at the end of each iteration until there are no nodes left to process.

After the algorithm has finished processing the graph, the value of the "fin" node in the costs hash table will contain the cumulative cost of the lowest cost path. (In this case: 6)

console.log(costs.get("fin")); // 6

To find the actual path that the algorithm has plotted you need to begin with the end node and work backwards using the values in the parents hash table. In this simple example, the parents hash table looks like this after processing:

{ 'a' => 'b', 'b' => 'start', 'fin' => 'a' }

So, working backwards:

from fin go to a
from a go to b
from b go to start

There you have the lowest cost route.

Larger example

It's fair to say that the graph we are working with here is trivially small. I am able to confirm however that the method does work on more complex graphs. Take a look at this problem: Part 1 of Day 15 of the 2021 Advent of Code.

The graph in this problem is a 100 x 100 matrix of digits (available here). Your job is to find the lowest cost route from top-left to bottom-right through the matrix, moving one node at a time up, down, left or right, where the cost increases by the value of each node visited.

Here is my code to solve the problem. The first ~half of the code builds the graph hash map and the other data structures that are discussed in this article. The rest of the code is essentially the function and while loop shown above.

On my ~9 year old Mac it took about 13 minutes to come up with the lowest cost route. I dare say there is a more efficient and/or elegant approach but the fact that it provided the correct answer is evidence that the algorithm does work with larger, more complex graphs.

If you want to give it a whirl the correct answer is shown in a comment at the bottom of the file on GitHub.

Summary

In this article I have dug a little deeper into graphs and added weights to the edges. I have also taken you step by step through Dijkstra's algorithm to find the lowest cost route through a weighted graph.

You have also learned how to put together the code that will carry out Dijkstra's algorithm.

The next, and final, part in this series will look at dynamic programming algorithms and how to use one to solve the Knapsack Problem.

Cover image by Gene Jeter on Unsplash

Grokking Algorithms in JavaScript - Part 2

Matt Edwards — Wed, 12 Jan 2022 06:48:33 +0000

This is part 2 in a series of articles about the algorithms covered in Aditya Y. Bhargava's excellent book Grokking Algorithms. In Part 1 I looked at binary search, selection sort and quicksort. In this part I will look at graphs and one of their associated algorithms.

Breadth-first search

Breadth-first search ("BFS") is a means of searching through the nodes in a graph to find a node that has specific properties: eg. find a route from town A to town B, or; find a certain person in your social network.

Given a graph, a start node and an end node, BFS can answer 2 questions:

is there a path from start to end, and
what is the shortest path (in terms of the number of nodes visited) from start to end

So what exactly is a graph?

Graphs in this context don't have x and y axes: we're not talking about line graphs or bar charts. The graphs that we are talking about here are representations of connections in a network.

A graph is made up of nodes which are connected by edges. For example, a graph might be a representation of a geographical area where nodes are towns and edges are the roads that connect them. Or it might represent a social network where nodes are people and edges represent the relationships between them.

Our example graph

The picture below shows a small social network with your immediate connections, their connections and their connections' connections; so, three levels of connection.

Imagine that your central heating boiler has broken down and you want to know if your social network contains a heating engineer. You also want to find the heating engineer that is closest to you in the network.

Before getting into the workings of BFS it's worth thinking about how we are going to represent the graph to be searched. Indeed, a lot of the work in writing graph algorithms is in constructing the graph representation in the first place. The perfect data structure for the job is a hash table and the Grokking Algorithms book devotes an entire chapter to the subject (which is well worth a read). In simple terms, a hash table stores data in key value pairs where keys are unique and values can hold any type of data, including arrays or even other hash tables.

Python and JavaScript each has a native data structure that performs the job of a hash table: Python has its Dictionary data structure while in JavaScript we can use the Map() object.

Representing the graph as a JavaScript Map() object

const graph = new Map();
graph.set("you", [
  {name: "peter", job: "bricklayer"},
  {name: "dimitrios", job: "chef"},
  {name: "katie", job: "architect"}
]);
graph.set("peter", [
  {name: "dean", job: "solicitor"},
  {name: "aleksandra", job: "doctor"},
]);
graph.set("dimitrios", [
  {name: "sam", job: "heating engineer"},
  {name: "shefali", job: "driving instructor"}
]);
graph.set("katie", [
  {name: "shefali", job: "driving instructor"}
]);
graph.set("dean", [
  {name: "james", job: "graphic designer"},
]);
graph.set("aleksandra", []);
graph.set("sam", [
  {name: "molly", job: "software engineerr"},
]);
graph.set("shefali", [
  {name: "andrew", job: "heating engineer"},
  {name: "amy", job: "barrister"},
]);
graph.set("james", []);
graph.set("molly", []);
graph.set("andrew", []);
graph.set("amy", []);

BFS methodology

A quick glance at the image of our small social network above tells you that there are 2 heating engineers in this 3-level network - Sam & Andrew - and that Sam is the nearest connection to you being a level 2 connection whereas Andrew is level 3. But how do you code that into an algorithm?

BFS works by processing all closest connections to a node before moving on to the next closest connections, and so on. The way to enforce that "closest first" rule is to use a queue. A queue data structure works just the same as a queue in real life: people join the queue at the back and leave when they get to the front.

So starting with the "you" node in the graph, the algorithm adds the "you" node's neighbours to the back of the queue. To find the neighbours of a node simply look up that node in the graph hash table. Remember that a hash table is a collection of key/value pairs. In the graph hash table the node is the key and its associated value is an array of the node's neighbours.

The algorithm looks at the queue, removes the person from the front and checks whether they are a heating engineer. If so, the search is over - return that person's name. Otherwise add that person's neighbours to the back of the queue, take the person from the front and continue.

This process repeats until:

a. you find a heating engineer, or
b. the search queue is empty - which means there is no heating engineer in your social network.

It's worth highlighting again here that the First In First Out (FIFO) nature of a queue means that 1st level connections are processed before 2nd level connection; 2nd level connections are processed before 3rd ... and so on. This guarantees that a search for a heating engineer in the above graph will always return Sam, not Andrew, ie: the shortest path.

There is another important aspect to think about here. Have a look at the image above showing the social network. You will note that Shefali is a connection of Dimitrios and Katie. We don't want to add Shefali (and by extension her connections) to the search queue twice. To avoid that happening we can keep a list of people we have already considered. And at the stage above where a person is added to the back of the queue, that needs only happen if that person isn't in the "already processed" list. In the code below that list takes the form of a simple array called searched.

The code that implements the steps above is as follows. This is based on the example in Grokking Algorithms, extended a little and converted to JavaScript. The search function takes two parameters: the start node ("you" in this case) and the job to search for. It searches the graph data structure set out above.

function search(name, job) {
  let searchQueue = graph.get(name);
  const searched = [];
  while (searchQueue.length > 0) {
    const person = searchQueue.shift();
    if (!searched.includes(person)) {
      if (person.job === job) {
        console.log(`${person.name} is a ${job}`);
        return true;
      } else {
        searchQueue = searchQueue.concat(graph.get(person.name));
        searched.push(person);
      }
    }
  }
  console.log(`Nobody in your social network is a ${job}`);
  return false;
}

search("you", "heating engineer"); // "sam is a heating engineer"
search("you", "police officer"); // "Nobody in your social network is a police officer"

Summary

In this article I have introduced the concept of graphs and how to use a hash table to represent a graph in code, specifically using the Map() structure in JavaScript. I have laid out the steps that a BFS algorithm takes to traverse a graph in search of a node with certain properties and demonstrated how such an algorithm might be implemented in JavaScript.

In the next article in this series I will build on the concept of graphs, introduce the idea of weighted graphs and take a look at another graph traversal algorithm called Dijkstra's algorithm.

Cover image by Denys Nevozhai on Unsplash

Grokking Algorithms in JavaScript - Part 1

Matt Edwards — Wed, 12 Jan 2022 06:48:18 +0000

Christmas 2021 - my favourite gift was the book Grokking Algorithms by Aditya Y. Bhargava. This book is perfect for somebody like me who has never formally studied computer science but has developed a deep interest in the subject.

Over the festive period I worked through the chapters and the code examples, making the small changes required to get them to run in Python 3 (the book examples are written in Python 2), and then converting them to JavaScript.

Below is my interpretation of some of the algorithms that the book focuses on, namely:

Binary search
Selection sort
Quicksort

In later parts I will cover:

Breadth-first search
Dijkstra's algorithm &
Solving the Knapsack Problem with dynamic programming

BINARY SEARCH

Imagine you have a sorted array and you are searching for a specific element that may, or may not, be in that array. How would you approach the search?

One way would be to start at array index 0 and work your way through each element until you find what you are looking for. If your target element is the last one in the array, or it isn't in the array at all, you will need to access every element. That's the worst case scenario and it's customary to compare algorithm efficiency based on the worst case.

Binary search - steps

Since the array is sorted you could use a binary search algorithm. Imagine you have a sorted array of 512 elements. Binary search works like this:

Your first step is to look at the middle element (index 256) to see if it is the element you are looking for. If it is, happy days! Chances are though that it won't be, in which case you ask yourself:

"Is this middle element higher or lower than my target element?"

If array[256] is higher, you know that your target element must be in the lower half so you have immediately discarded half of the array.

Next, look at the middle element from those that remain and go through the same steps. Again you have eliminated half of the remaining elements.

Keep doing that until you either find your target element or discover that it's not in the array. Worst case scenario is that your target isn't in the array, or it's the very last element. But how many steps would it take you to find the solution in that worst case scenario?

Well, in an array of 512 elements the answer is log2512. In other words, to what power do you have to raise the number 2 to get 512?

Answer: 9 steps.

Comparison with simple search

Using the first method (known as simple search) on an array of 512 elements would take 512 steps (remember, we're looking at the worst case here). The 9 steps taken by binary search is clearly significantly quicker. And the difference is magnified with larger data sets.

Imagine that you need to search an array of 1 billion elements and your super fast computer can process 1000 elements per second. Binary search would deliver an answer in 30 milliseconds (2³⁰ = 1.073 billion) while simple search would take more than 11 days.

Below is my JavaScript version of binary search.

function binarySearch(arr, target) {
  let low = 0;
  let high = arr.length - 1;
  let mid;

  while (low <= high) {
    mid = Math.floor((low + high) / 2);
    let guess = arr[mid];
    if (guess === target) {
      return mid;
    }
    if (guess > target) {
      high = mid - 1;
    } else {
      low = mid + 1
    }
  }

  return null;
}

  return null;
}

const myList = [1,3,5,7,9,11,13,15];
console.log(binarySearch(myList, 5)); // 2
console.log(binarySearch(myList, 12)); // null

SELECTION SORT

The first algorithm that we looked at, binary search, only works on a sorted array. Selection sort is one method that you can use to get an array into a sorted state and it works as follows:

Selection sort - steps

Loop through your unsorted array;
Find the lowest value element;
Extract said element and place it in a new array at index 0.

Loop through the remaining elements of the unsorted array;
Find the lowest value element;
Extract said element and add it to the end of the new array.

Repeat until the original, unsorted array is empty by which time the new array is a sorted array of the same elements.

Below is my JavaScript version of selection sort. The Python code in the book makes use of a for loop in the main selection_sort() function whose initial length is determined by the length of the original, unsorted array. I preferred to use a while loop to avoid the risk of referencing an out-of-range array index with the original array shrinking on each iteration.

function findSmallest(arr) {
  let smallest = arr[0];
  let smallestIndex = 0;
  arr.forEach((el, index) => {
    if (el < smallest) {
      smallest = el;
      smallestIndex = index;
    }
  });
  return smallestIndex;
}

function selectionSort(arr) {
  newArr = [];
  while (arr.length > 0) {
    const smallest = findSmallest(arr);
    newArr.push(arr.splice(smallest, 1)[0]);
  }
  return newArr;
}

console.log(selectionSort([5,3,6,2,10])); // [ 2, 3, 5, 6, 10 ]
console.log(selectionSort(['grape', 'apple', 'banana', 'kiwi'])); //  'apple', 'banana', 'grape', 'kiwi' ]

Efficiency

It's worth mentioning here that selection sort is a slow algorithm. For an unsorted array of n items, that array has to be looped through n times. It therefore takes n² operations.

But, hang on a minute, n reduces by 1 on each iteration so it's not n²; surely it's more like 1/2n * n operations.

That's true, but in the world of algorithm performance measurement, constants (like the 1/2 in the previous sentence) are ignored so selection sort has an efficiency of n².

QUICKSORT

As its name suggests, quicksort is somewhat quicker than selection sort. It's what's known as a divide and conquer algorithm and uses a technique similar to that used in binary search in that it breaks down the problem into smaller and smaller chunks.

It also relies on recursion, a subject that I won't go into in any depth here other than to say that it is a technique that relies on a function being able to call itself repeatedly until what's known as the "base case" is reached, at which point the function returns its result.

Recursion also relies on the inner workings of the call stack. Until the base case is reached, every call to the function is incomplete and is held in limbo in the call stack. When the base case is reached, and the function finally returns its result, the results of each preceding function call can then be passed down as each completed function is popped off the call stack and the final result is output from the initial call to the recursive function.

It's vitally important to include a valid base case in a recursive function, otherwise the function will continue calling itself forever, or at least until the call stack overflows.

That's probably a rather confusing explanation of the workings of recursion. If you want to understand it more fully I recommend getting your own copy of Grokking Algorithms. Aditya Bhargava does a wonderful job of explaining it with lots of hand-drawn illustrations.

I can also recommend this talk by Al Sweigert on the subject:
https://www.youtube.com/watch?v=fhDsjfLSmVk

Quicksort steps

Quicksort works by selecting an array element at random. This becomes the "pivot". Remaining elements are compared against the pivot and divided into "less than" and "greater than" arrays.

Each of the less and greater arrays is run through the same process, and so on and so on until the base case is reached (ie. the array is only one element long so cannot be sorted) at which point all of the recursive function calls can return and everything is put back together at the end in sorted order.

Below is my JavaScript take on quicksort based on the Python version in the book. The Python version is very succinct. It makes use of list comprehensions, a very neat technique, and Python's ability simply to add lists together.

I used JavaScript's filter function in place of Python's list comprehensions and the array spread operator to facilitate the adding together of all of the elements in the recursive return statement.

function quicksort(arr) {
  if (arr.length < 2) {
    return arr;
  } else {
    const pivotIndex = Math.floor(Math.random() * arr.length);
    const pivot = arr[pivotIndex];
    const reduced = [...arr.slice(0, pivotIndex), ...arr.slice(pivotIndex+1)];
    const less = reduced.filter(v => v <= pivot);
    const greater = reduced.filter(v => v > pivot);
    return [...quicksort(less), pivot, ...quicksort(greater)];
  }
}

console.log(quicksort([10, 5, 2, 3])); // [ 2, 3, 5, 10 ]

Any element can be the pivot in quicksort but choosing an element at random will yield the greatest time efficiency in the average case, namely: n log n. (In algorithm efficiency terms, "log" is assumed always to refer to log2 and it's customary simply to omit the 2)

Summary

This article introduced the concept of algorithms by looking at the simpler examples. Not all algorithms are created equally efficient and the idea of time efficiency was introduced.

The subject of recursion also featured. Recursion is a technique often used in algorithms which is notoriously difficult for beginners to wrap their head around.

Part 2 of this series will look at graphs and breadth-first search.

Cover image by Clem Onojeghuo on Unsplash

Manchester Codes - Software Engineer FastTrack Bootcamp - Week 1

Matt Edwards — Sun, 22 Nov 2020 12:16:09 +0000

Manchester Codes Software Engineer FastTrack is a 24 week, part-time bootcamp structured as two 3-hour lectures per week plus a fair amount of self-study in between. Owing to Covid restrictions it's currently a fully remote course with lectures delivered via Zoom. Tutors are also available for 1-2-1 assistance during Saturday "remote drop-in" sessions. The part-time structure appeals to me because I still work full-time in a non-tech field.

I signed up for this bootcamp a few weeks ago. It seemed to take ages for the start date to roll around and I was excited to get going. I was also apprehensive because I knew I was going to be significantly older than my classmates.

Lecture 1

Lecture 1 wasn't really a lecture, it was more of an introduction. We all introduced ourselves by giving a very brief bio and, as a bit of an ice breaker, offering 3 statements about ourselves two of which were true and the other a lie. There's a whole mix of people in my cohort and some of my fellow students have interesting back stories :-) And, at 54, I'm definitely the Grandaddy of the group. I keep telling myself it's all about mindset: I'm not "old", I "have experience"; and, my age is not a bug; it's a feature! One of these days I might even believe myself! Haha.

The tutors Miguel and Jenny then gave us a brief introduction to the work we will be doing over the next 6 months. After that we all got down to business setting up our development environments. The tutors were on hand to help out when anybody got stuck. I've been playing with Python for a few months so I'm fairly comfortable working in the Mac terminal. I still found the whole process a little stressful.

A Zoom classroom is a slightly weird environment - everybody on camera but quietly getting on with their own stuff except when asking for help. Somehow it still feels like a classroom. My main weakness in a classroom setting is that I fundamentally lack self-confidence and I'm scared of being the one who just doesn't get it and holds everybody up. That self-imposed sense of time pressure causes mild to moderate anxiety that manifests itself as an impaired ability to follow simple instructions. (I have to stress here: it's entirely self-imposed, the tutors put no pressure on us whatsoever; they are nothing but supportive and patient)

Setting up the development environment

This comprised the following steps:

Install Node Version Manager
Install Node Package Manager
Install Node.js
Install Git
Generate SSH key and add to Github
Install Visual Studio Code
Install ESLint
Install the ESLint extension to Visual Studio Code

This mostly went without a hitch. There was a fair amount of copying & pasting bash commands which I find it a little unnerving though because when you're simply copying commands you don't really know what's going on and I have an in-built desire to understand things from first principles as much as possible. I guess it's an unavoidable part of setting up new tools though.

I took the copy/paste process a little too literally with the Node.js installation and failed to follow the simple instructions (for reasons outlined above) and installed an out of date version instead of the latest LTS version. With a little help from tutor Jenny I was able to rectify that the next morning so it was no biggie.

The whole SSH thing this was a bit of a headscratcher! I have used Git before I never had cause to explore its SSH functionality. The GitHub instructions are pretty comprehensive but, again, I found them difficult to follow. I got through it eventually and received the confirmation email from Github. Phew!

So that was it for lecture 1! All done with time to spare. I needn't have got so stressed. Now the first lesson is behind me I should hopefully find it easier to relax.

Study material

The bootcamp material includes a comprehensive online study pack to work through between classroom sessions. Tutors estimate that you need to spend 14-20 hours per week studying on top of the 6 hours of classes so it's a hefty commitment.

Lecture 2

Each lecture session kicks off with a stand up: an industry-standard practice where everybody gives a brief description of what they have been working on, what has gone well and where they have struggled. Miguel then delivered a more traditional style lecture covering the command line interface. After that we all installed a pimped-up replacement for the humble Mac terminal called Oh-My-zsh. It includes Git integrations that should come in handy.

Next we worked through an introduction to Git with the tutors on hand to help out with any questions. They can take people into a Zoom breakout room to deal with questions if necessary so that the rest of the class isn't disturbed. It's a pretty smooth setup.

I spent the rest of the week working through the remaining command line and Git study material which included a Git tutorial, updating the Manchester Codes Student Roster Git repository with our own details and solving a murder mystery using nothing but the command line. I particularly enjoyed that last project, it was great fun.

So, after being so excited ... and nervous ... how did the first week go? I have to say that I absolutely loved it!

I've played around with programming in an amateur fashion for a while, simply because I enjoy it. I have dabbled in Python & Django. I have learned the basics of HTML & CSS and a bit of PHP. I completed Harvard's CS50 introduction to computer science course earlier this year. I am painfully disillusioned with my current career and would like to take programming beyond the amateur level but reailse that I'm unlikely to get anywhere with it on my own.

Manchester Codes has given me a routemap to follow, a curriculum that offers a solid grounding in modern technologies and, more importantly for me, a community that I am part of and a way into the world of professional programming.

Week one has left me energised and optimistic about the future, both pretty rare commodities in these uncertain times. Bring on the next 23 weeks!

Cover photo from Unsplash by @bamagal

Manchester Codes - Software Engineer FastTrack

Matt Edwards — Tue, 15 Sep 2020 20:41:20 +0000

Should I sign up?

The Software Engineer FastTrack is described as a 24-week immersive part-time bootcamp. More about it here https://www.manchestercodes.com/

It's a kind of bootcamp that you can attend while still working fulltime, which I do - in a totally unrelated field.

I'm really tempted. I have a fair amount of amateur experience in various aspects of software development amassed over a few years. I love programming - always have done - and would love to give it a try professionally. The course pretty much ticks the boxes for me.

So why the question at the top of the page?

I'm looking to completely change direction in my career.

"So what?", I hear you say. "Loads of people have successfully done that!"

Thing is, I'm 54 years old. I will be 55 a few days after the course finishes next year.

So, my question to you ... the Dev Community ... is, will I be taken seriously?

Is it possible for somebody of my age to make the switch?
Do you know anybody who has?
How would you react to a junior developer who's old enough to be your dad?

In the brief time that I have been a part of this community I have learned that it is a supportive and welcoming one. If that weren't the case then I don't think I would even be contemplating this. But all things have their limits.

I'm really excited to press the enrol button!

At the same time I'm shitting my pants!

What should I do?

Thanks

First tango with Django? How did the plan go?

Matt Edwards — Sat, 05 Sep 2020 22:09:37 +0000

I have just finished my first Django application as my CS50x final project (Yay!). It's a meal planning and shopping list application. Thrilling eh?

Actually, I am pretty thrilled as it happens.

It's taken the best part of a month to get from blank screen to deployment. And that's while working full time in a completely unrelated job.

Learning curve

I knew very little about Django at the outset, having only worked through the obligatory 'Hello World' and a basic blog tutorial. Tutorials are great but it's only when you start building your own projects that you really learn the workings of a framework or language. On more than one occasion I thought I had bitten off more than I could chew and seriously considered jacking it all in. I'm glad that I persevered though: I'm pretty pleased with the finished article.

Because of the nature of the application, I spent a lot of time wrestling with Django's form-handling capabilities. HTML forms are never easy to work with. Django's built-in Forms module has its own intricacies, but overall I think it greatly simplifies the process.

I also spent some time getting my head around Django's database abstraction API. This is an ORM tool that hugely simplifies interaction with a database. For this project I stuck with the SQLite database that effectively comes bundled with Django.

So, why did I choose to build it?

My wife and I switched to a vegan diet almost a year ago. One of the immediate practical effects was that we started to cook a lot more of our own meals. Clearly, before you can cook a meal you need to have all of the ingredients to hand so cooking also means shopping for ingredients. Before you can go shopping you need a list of ingredients to buy.

Sometimes(!) I actually enjoy cooking. But making a shopping list and going to the supermarket to buy the ingredients is a royal pain in the arse! So, having a brain that naturally leans towards problem-solving, I wondered if I could program something to remove a bit of the pain from the process.

Ok, what does it do?

The app is based on the fundamental premise that a shopping list is composed of two elements:

items that you need to prepare the meals that you plan to eat over the coming days; and,
general 'stock items' to replenish your cupboards.

The app enables you to:

build a database of meals, each with a list of items that you need to buy to cook the meal; and,
build a database of items generally, some of which are marked as favourites (ie. the things that buy regularly)

Each of the items held in the database is associated with a storage location (ie. where you store that kind of item at home) and a shop department (ie. where you find that item in the supermarket). The storage locations and shop departments can be sorted according to the order that you visit them when making a list (storage locations) and navigating the supermarket (shop depts.). The idea there is that the order you add items to your list is probably not the same as the order you put things in your basket.

To compose a new list:

Choose the meals you plan to cook over the next few days. A list of items that you need is then created in storage location order. The list contains all of the items you will need to prepare the chosen meals.
A list of the stock items (that you have marked as favourite) is then created automatically, again in storage location order.
Those separate lists are then combined and presented to you with tick boxes so you can do the tour of your cupboards and tick the items that you need to buy. (You might have some meal ingredients already in stock. eg. the list might tell you that you need garlic for the curry that you chose in step 1 but when you look in the fridge you see that you have plenty of garlic so you don't tick it)
Your final list is presented to you in shop department order (you having previously adjusted the order of departments according to your supermarket). As you put an item in your basket, tap its entry on the list and it is greyed-out to show you've got it.

And that's it!

Finishing touches

I deployed the app, via Git Hub, to Python Anywhere, the service used by the Django Girls in their blog tutorial. They have a free 'beginner' account which supports SQLite databases. Heroku was another hosting option but it looks like they somehow purge their file system daily so SQLite, being a file-based database, is not an option there.

I did a small amount of CSS styling. (If you look at the app you will see that visual design is not my strongest suit! Haha!) It's designed to work on mobile/tablet first and foremost; not many people take their laptop shopping.

I also wrote a single Javascript function to handle the 'greying-out' of list items when tapped. I would like to make the storage location/shop department re-ordering a drag-and-drop activity but that's a Javascript task for another day - mostly because I don't know how!

So, next steps for this app are: drag and drop, as mentioned in the last paragraph, and adding user accounts so that it can be personalised for different users.

After almost giving up mid-project, I'm very pleased with the result of my first tango with Django. I would welcome any feedback; even if it's good feedback! You can see the finished article at: http://shoplist.pythonanywhere.com.

Photo by Dina karan on Unsplash

Virtual environments - first things first

Matt Edwards — Thu, 13 Aug 2020 07:05:14 +0000

If you are aware of the idea of a virtual environment but you don't really understand the concept or you can't see how it applies to your circumstances, then this article is for you. Until quite recently, I was the same: the whole concept confused me and, to be honest, I didn't see the point.

I have played around with various forms of computer code in an amateur fashion for more years than I care to remember. A few months ago - during the early stages of the coronavirus lockdown in the UK - I rediscovered my love of programming, reaquainted myself with Python and made the decision that programming in one form or another needed to become a much bigger part of my life.

My Python journey led me to Django and it was only then that I fully appreciated the concept of a virtual environment and understood why every programming project should start with the creation of a one.

By writing this article I hope to demystify the concept for programmers who either don't get it or can't see the point because I've been that person too!

So, what is a virtual environment?

My son is 7 and he has just finished year 2 at school. The official end of term was just 2 or 3 weeks ago but he has spent only 2 days actually in school since March (4 months ago) because the school effectively closed due to covid-19. Those 2 days that he did spend in school were only possible because of a "bubble" system that the school introduced.

My son was in a "bubble" with 14 other pupils from his class. During those 2 days at school he only interracted with people in his bubble. They sat together in class, ate together, and had break time together, all without interracting with anybody who was not in their bubble. The bubble system aimed to remove the risk of cross-infection between bubbles.

Virtual environments are similar to the bubbles in my son's school. Your application only interracts with software packages in its own bubble. It is insulated from packages in any other bubble or, perhaps more importantly, packages at the system level.

What is the issue that virtual environments address?

Imagine you wrote a Python program some time ago, before you ever heard of virtual environments. To build the program you used a couple of third-party Python packages that you installed specifically to do the job. When you installed those packages you will have installed them at the system level. That's not a problem at that stage. You finished the program, it worked really well and you were pretty chuffed!

A little while later you start work on another Python program on the same machine. Your new program uses one of the packages that you used in the first program and you have read about some whizz-bang new features that the latest version of that package offers. You like to live on the cutting edge of technology so you update that package to the latest version. You implement those awesome new features into your new Python program and you are doubly chuffed when it's finished. Well done you!

A few days later you try to run your first Python program only to discover that the new version of that package that you installed (at the system level remember) no longer supports some of the features that your first program uses. Your first Python program no longer runs. How frustrating!

Imagine if that was a live application with multiple users who might even have paid you money for the privilege of using it. Somewhat more than frustrating!

So how do virtual environments help?

Imagine a different scenario where the first thing you did when you started work on Amazing-Python-Project-1 was to set up a virtual environment - a figurative bubble in which your application could live, insulated from other applications and installations on your machine - and you then installed the two python packages into that same virtual environment and not at a system level.

When you move on to Amazing-Python-Project-2, in this scenario you would again set up a dedicated virtual environment for that program, and install the packages, including the latest whizz bang version, into that virtual environment. Those package installatons have no effect on the first virtual environment.

The two programs, and all of the packages required to run them, co-exist independently in their respective bubbles. The updated packages in the second virtual environment have no impact whatsoever on the program and associated packages in the first virtual environment.

Amazing-Python-Project-1 & Amazing-Python-Project-2 can both still run on the same machine. Your users will be unaffected, remain blissfully happy and continue to hand over their cash.

That sounds pretty amazing! But ... how do I do it??

Confusion reigned once again for me at the point of implementaton. I had read a few different books and tutorials offering advice on setting up your Django application - remember, it was Django that got me embroiled in the whole virtual environment thing in the first place - and it turns out that there's more than one way to skin the virtual environment cat. The author of each book or tutorial seemed to favour a different method.

There are third-party "virtual environment management" packages that you have to install on your machine, counterintuitively at system level, or there is a package which has been part of the standard Python library since version 3.4.

After playing around with the different methods ... and getting thoroughly confused and frustrated in the process ... I decided if something is part of the standard Python library then it makes sense to use it.

It's a package called venv. If you too are new to virtual environments, my advice is just stick with that: why introduce further complication when all the functionality you need is already there within Python? You can always try out different methodologies when you're comfortable with the whole concept.

Implementation steps

Ok, we've decided on the tool for the lob: venv. The following steps show how to set up a Python virtual environment on a Mac or Linux in readiness for the start of a new Django project which will live in a new directory called my_project. The virtual environment also needs a name (because it gets its own dedicated directory); let's call it myvenv

In a Terminal window, navigate to the directory where you plan to put the my_project directory and type...

$ mkdir my_project
$ cd my_project
$ python3 -m venv myvenv

The first 2 lines should be familiar Bash commands. A little explanation is probably in order for line 3. Firstly, I have to add the number 3 to the end of Python because I am using a 6 year old Macbook came with Python version 2 installed as default. I always have to explicitly tell the Python interpreter that I want to use version 3.

If you habitually type python3 to activate the Python shell then you need to add the 3 here too. If not, then simply python -m venv myvenv will work.

venv is the name of the virtual environment package that comes pre-installed with Python since version 3.4 and myvenv is the name that we chose to give to the virtual environment.

When the command on line 3 above is run, a new directory called myvenv is created within the my_project directory.

The myvenv directory contains files that venv will use to manage your virtual environment and which will contain files for the packages that are subsequently installed into the virtual environment. That is how those packages are kept within the "bubble". Ingenious eh?

So that has created your new virtual environment called myvenv. Before we install any packages we have to activate it with

$ source myvenv/bin/activate

You will now notice that your Terminal prompt is prefixed with the name of your virtual environment in parentheses.

(myvenv)$

We can now install Django into our virtual environment

(myvenv)$ pip install Django~=3.0

After running that command look in myvenv/lib/python3.8/site-packages and you will see that the latest incarnation of Django version 3 has been installed. And it's safe within your virtual environment untouched by anything outside that "bubble".

You can also run the pip list command in the Terminal...

(myvenv)$ pip list
Package    Version
---------- -------
asgiref    3.2.10 
Django     3.1    
pip        19.2.3 
pytz       2020.1 
setuptools 41.2.0 
sqlparse   0.3.1

In the example shown here, I have installed Django 3.1 and there are some other default packages already installed.

Any other packages that you need for your program should be installed the same way - pip install... into the active virtual environment.

And now for the cherry on the top: requirements.txt. This is a simple text file that keeps track of the various packages that you have installed into the virtual environment. When your program is complete, requirements.txt will contain a blueprint of the specific versions of all of the packages that your program needs in order to run. You can therefore run your program in a virtual environment on another machine by passing that virtual environment a copy of requirements.txt to use as a recipe to concoct the precise mix of packages required. More on that later.

So how do you create the requirements.txt file?

There is another pip command: pip freeze. Running that in the Terminal will list all third-party packages and version numbers.

(myvenv)$ pip freeze
asgiref==3.2.10
Django==3.1
pytz==2020.1
sqlparse==0.3.1

All you need to do now is add a suffix to that same command to instruct it to write the list to file instead of to screen...

(myvenv)$ pip freeze > requirements.txt

You now have a file called requirements.txt that contains precisely the same list as was printed to screen by the pip freeze command without the suffix.

IMPORTANT When you run that command you need to make sure you are in the project root directory - i.e. my_project in this example - because requirements.txt will be created in whatever directory the pip freeze command was run in.

So there you have it. All of the packages that your program needs, safe within their own bubble which has a list of contents on the outside in the form of requirements.txt. Every time you install a new package to use in your program, run the command pip freeze > requirements.txt and your "contents list" is updated.

Take your new requirements.txt file for a test drive

You can really get a feel for how useful requirements.txt is by creating a new virtual environment in a new diectory - say my_other_project - by following the instructions above. You can give the virtual environment the same name - myvenv - if you like; that's up to you.

Then, before installing anything, copy the requirements.txt file that we created above in my_project into your my_other_project directory. It needs to sit in that root directory, alongside myvenv (assuming you chose the same virtual environment name).

Then, with your Terminal in the my_other_project directory, and the virtual environment activated, run...

(myvenv)$ pip install -r requirements.txt

Wait for the magic to happen, then run pip freeze...

(myvenv)$ pip freeze
asgiref==3.2.10
Django==3.1
pytz==2020.1
sqlparse==0.3.1

And you get exactly the same output as in the other project. The environment has been precisely recreated.

Magic eh?

When you have finished working on your project, use the command deactivate in the Terminal to ... well ... deactivate the virtual environment

(myvenv)$ deactivate
$

Conclusion

After reading this, I hope that you now have a better understanding of:

virtual environments in general;
the reason they are a good idea;
and how to set one up for your next Python project.

Image credit: Photo by Lanju Fotografie on Unsplash