DEV Community: Luke Garrigan

My favourite Kotlin features

Luke Garrigan — Sun, 08 Aug 2021 16:52:49 +0000

Last Saturday I sat down with a strong cup of coffee and got stuck into some Kotlin. I thoroughly enjoyed the process and likewise, thoroughly enjoyed the language. Its simplicity, elegance and to-the-pointedness make me envy those lucky devs that use it day-to-day.

Engineers whose job is to create tools for popular programming languages — and the best ones at that — would certainly know a thing or two about each language’s strengths and weaknesses. It was the perfect recipe, and the oven was set at the perfect temperature.

Coincedentally — and to my astonishment — Kotlin is celebrating its 10th anniversary. I still consider it the new kid on the block, even if 142,000 apps are using it with upwards of 380,000,000,000 downloads.

My knowledge of the language is embryonic, to say the least. I’ve roughly spent a total of 7 hours coding in Kotlin, that’s around 3 hours solving Katas on Codewars and around 4 hours creating very simple Android applications — details of which I’ll go into in my next blog. So, I am by no means an expert. Yet, I’ve still managed to compile 5 things that I love about the language.

Clean syntax

The language is clean. And by clean I mean not verbose. As a Java turned C# developer I can acknowledge that sometimes the code I write is verbose. Verbosity however, is sometimes needed for code clarity. Kotlin has managed to reduce verbosity whilst keeping clarity and — somehow — managed to improve code readability (In my opinion). Here’s a few examples of how they’ve achieved it:

Final made simple

In Java to create a final variable — that is, a variable that can only be initialised once — you’d have the following:

final int AGE = 5;

Whereas in Kotlin you have two different keywords to declare variables: val and var.

val age = 5

val being the final equivalent. Much like TypeScript’s const.

Also, you may have noticed that semi-colons are not required. Oh, and there are inferred types, which there are too in Java and C# now, but it’s worth pointing out.

No new keyword

This one caught me off guard. There I was, trying to create my first object in Kotlin:

val person = new Person() // unresolved reference new

The new keyword is so embedded in my hippocampus for object-oriented programming that I thought I’d made some syntactical error, which, of course, I had.

Let’s have some fun

Kotlin is fun, but to define a function all you need is fun.

fun doSomething() {
  // doing something
}

Such a trivial thing, but having a vital keyword only being 3 characters allows you to focus on what’s important.

Not so nullable types

Null references — known as the billion-dollar mistake — have plagued developers for half a century. I can’t imagine a single developer who has not been stung by this hornet. We’ve all attempted to access a member of a null object at some point. NullPointerException or NullReferenceException or Cannot read property of null, I’m sure one of these inflicts PTSD in some of you.

In Kotlin, references are not nullable by default. You have to explicitly make them nullable:

var name: String = "Luke" 
a = null // compilation error

If you want string to be nullable you’d have to use the nullable syntax:

var name: String? = "Luke" 
a = null // all good

So what happens if you want to access a property of name in this scenario? It’d just throw a null reference exception wouldn’t it? Nope:

var name: String? = "Luke";
name = null;
var nameLength = name.length; // Only safe (?.) or non-null asserted (!!.) calls are allowed on a nullable receiver of type String?

Instead, you get a compile-time error explaining what you need to do to access the member, brilliant.

Extension functions

Okay, this one may be a bit of a cop-out as I am predominantly a C# developer and have on numerous occasions, expressed my love for extension methods. Having the ability to write new functions for third-party code whose source is not easily editable is a game-changer.

fun main() {
    var x = 10.4;
    print(x.half());
}

fun Double.half(): Double {
    return this / 2;
}

I also prefer the implementation of extension functions in Kotlin to other languages, there’s less syntactic sugar, which is always a plus from me.

Convert to Kotlin

One of the best parts of Kotlin is its interoperability with Java, making it easy for Java devs to make the transition. JetBrains IDEs allow you to directly convert Java code to Kotlin, by the click of a button, amazing. This is not so much a feature of the language but rather a feature of the tooling.

I don’t believe there’s any tooling to convert Kotlin code to Java, but, why would you? Well, I’m sure somebody, somewhere has this requirement, but for me I’d stick to Kotlin.

Conclusion

Kotlin has met me well. Many decisions have been made with careful consideration from a team of talented individuals oozing knowledge in programming languages.

As mentioned earlier, I’m new to the language, but I like what I’m seeing. And I intend to see more of it.

I’m currently coding an android app to calculate running paces, which will be written about in my next blog if you’re interested.

Thank you for reading this blog, I hope you’ve enjoyed it! Please signup to my newsletter if you did.

A Completely FREE planning poker app 💸 – Speed up your planning process!

Luke Garrigan — Fri, 02 Jul 2021 08:00:16 +0000

Estimating is tough, and us developers are pretty sh*t at it.

There are many ways to go about estimating, using the Fibonacci sequence, the modified Fibonacci sequence, t-shirt sizing estimating, etc. My team tends to go for the Fibonnaci sequence to measure the complexity of tickets in order to story point.

There are some brilliant apps out there to help us with estimating but all of them are stuck behind a paywall in some way or another.

So I decided to create a planning poker app that is free. You can find the app at planfree.dev. It is completely open-source and the code can be found at github.com/LukeGarrigan/planfree.dev.

If you’re interested in the development process go ahead and check out the blog I wrote Coding a Planning Poker App.

How it works

When clicking “Start new game” it’ll create a room for you and your team.

All you need to do is click “Invite Players” and send them the link.

Once your team have joined the game, all that’s left to do is vote by clicking one of the Fibonacci estimation tiles at the bottom. If your team uses a different voting system such as the T-Shirt or Powers of 2 then don’t panic, there’s a Github Issue for that.

Once all players have voted it’ll count down from 3 and then reveal the cards:

Conclusion

I hope this app helps you and your team in planning. And please let me know either on Twitter or on the GitHub repo if you have any suggestions and/or feedback, I’ll gladly listen as I want this app to help as many teams as possible.

The Game of Life

Luke Garrigan — Sat, 19 Jun 2021 13:16:47 +0000

The Game of Life or cellular automaton was developed by John Horton Conway in 1970 with just some paper and a Go board. It takes place on a two-dimensional grid where each cell is in one of two states on (alive) or off (dead). The state of a cell is determined by its neighbours, and 4 simple rules determine whether the given state will live or die.

Rules

There are four rules that determine a cell’s fate.

Underpopulation: Any live cell that has less than two neighbours dies.
Overpopulation: Any live cell that has more than three neighbours dies.
Any cell with two or three neighbours survives.
Reproduction: Any dead cell with exactly three neighbours becomes a live cell.

These rules can be further simplified for implementation:

Any live cell with two or three neighbours survives
Any dead cell with three live neighbours becomes a live cell
Everything else is now a dead cell

Implementing

I’m going to be using p5.js to implement this, all the code can be found here.

The first step is to create a grid and randomly choose whether the cell is dead or alive:

let grid;
let columns;
let rows;
let size = 20;

function setup() {
  createCanvas(800, 600);
  columns = width / size;
  rows = height / size;
  grid = createGrid();

  for (let i = 0; i < columns; i++) {
    for (let j = 0; j < rows; j++) {
      grid[i][j] = floor(random(2));
    }
  }
}

function draw() {
  background(0);
  for (let i = 0; i < columns; i++) {
    for (let j = 0; j < rows; j++) {
      let x = i * size;
      let y = j * size;
      if (grid[i][j] == 1) {
        fill(0, 255, 255);
        stroke(0, 255, 255);
        rect(x, y, size, size);
      }
    }
  }
}

Which should give us something like the following, where the blue colour represents a live cell:

The next step is to create the next generation.

function createNewGeneration() {
  let nextGeneration = createGrid();
  for (let i = 0; i < columns; i++) {
    for (let j = 0; j < rows; j++) {
      let currentState = grid[i][j];
      let count = countNeighbours(i, j);
      if (currentState == 1 && count == 2 || count == 3) {
        nextGeneration[i][j] = 1;
      } else if (currentState == 0 && count == 3) {
        nextGeneration[i][j] = 1;
      } else {
        nextGeneration[i][j] = 0;
      }
    }
  }
  return nextGeneration;
}

function countNeighbours(x, y) {
  let sum = 0;
  for (let i = -1; i <= 1; i++) {
    for (let j = -1; j <= 1; j++) {
      let col = (x + i + columns) % columns;
      let row = (y + j + rows) % rows;
      sum += grid[col][row];
    }
  }
  sum -= grid[x][y];
  return sum;
}

Now all that's needed is to assign the new generation to the current grid: grid = createNewGeneration() in the draw function and we're good to go!

Let's make each cell a little smaller, thus increasing the population size: let size = 5

Conclusion

The Game of Life is a marvellous simulation. It demonstrates how just a few simple rules and structures can form very complex systems. There's far more to learn about the Game of Life, there's a whole lexicon of patterns that perform particular behaviours.

What is even more remarkable about the Game of Life is that it is Turing Complete. It is able to make any arbitrarily complex computation, meaning a computer can be built in the Game of Life that can run a simulation of the Game of Life, which of course, has been done.

What is BFS? (Breadth-first Search)

Luke Garrigan — Sat, 05 Jun 2021 20:05:33 +0000

Introduction

In computer science, a search algorithm is a series of steps that can be used to find the desired state or a path to a particular state. In most scenarios, there will be additional constraints that will need to be fulfilled such as the time taken to reach the desired state, memory availability, maximum number of moves.

A classic example in the AI literature of pathfinding problems are the sliding-tiles puzzles such as the 3 × 3 8-puzzle, the 4 × 4 15-puzzle and the 5 × 5 24-puzzle. The 8-puzzle consists of a 3 × 3 grid with eight numbered square tiles and one blank. The blank is used to slide other tiles that are horizontally or vertically adjacent into that position in an attempt to reach the goal state. The objective is to rearrange the tiles from some random configuration to a specified goal configuration. The number of possible solvable states for the 8-puzzle is 9!/2 = 181440 so can be solved by means of brute-force search. However for the 15-puzzle with 16!/2 ≈ 1.05×1013 and 24-puzzle with 25!/2 ≈ 7.76×1024 a more sophisticated informed search is required.

Uninformed Search

Uninformed or brute-force search is a general problem-solving technique that consists of systematically enumerating all the possible states for a given solution and checking to see whether that given state satisfies the problem’s statement. All that is required to execute a brute-force search is some legal operators, an initial state and an acknowledged goal state. Uninformed search generates the search tree without using any domain-specific knowledge.

Completeness and optimality

Often in search, the input may be an implicit representation of an infinite graph. Given these conditions, a search algorithm is characterised as being complete if it is guaranteed to find a goal state provided one exists. Breadth-first search is complete and when applied to infinite graphs it will eventually find the solution. Depth-first search is not complete and may get lost in parts of the graph that do not contain a goal state.

Breadth-First Search

Breadth-first search is one of the simplest algorithms for searching a graph, it expands the nodes in a tree in the order of their given distance from the root, so it expands all the neighbouring nodes before going to the next level of the tree. The algorithm doesn’t trawl to the deeper levels of the tree without first expanding the lower levels thus ensures the finding of the shortest path.

The space requirement of breadth-first search is its largest deficiency. The 8-tile has a search space of 9!/2 = 181,400 states with a maximum number of 31 moves to solve. In terms of practicality, with larger problem states such as the 15-tile puzzle, a breadth-first search will exhaust the available memory rather quickly with its 16!/2 = 10,461,394,944,000 solvable states and a maximum number of 80 moves.

The below image, taken from the blog BFS vs DFS is great way of visualising how the different algorithms expand a tree:

Implementation

To demonstrate breadth-first search I’ve implemented the sliding-tile puzzle, all the source code for the project can be found here.

Which also scales:

The algorithm

The algorithm is really simple, each state is just an array, so the goal state is [0, 1, 2, 3, 4, 5, 6, 7, 8]. To begin with each state gets added to a queue and a seen array. For a given state from the queue we add its neighbours to the queue which’ll eventually get evaluated too. The seen array is just to ensure we don’t add stuff to the queue that we’ve already seen – (There’s multiple ways to get to the same state). Each state is compared with the goal state, and if it’s the same then we return.

 solve(puzzle, goal) {
        let seen = [puzzle];
        let queue = [puzzle];
        while(queue.length > 0) {
            let current = queue.shift();

            if (this.isEqual(current, goal)) {
                return current;
            }

            for (let neighbour of Puzzle.getNeighbours(current)) {
                if (!this.isInSeen(seen, neighbour)) {
                    seen.push(neighbour);
                    queue.push(neighbour);
                } 
            }
        }
    }

Testing our algorithm

8 TILE

Let’s start with the 8 tile, and create a problem state that is 10 moves away from the goal state:

BFS solved the problem in 0.014s with the optimal number of moves (10). Only having to expand 1060 states.

Next I’m going to up the number of random moves from the goal state to 20:

Notice how this time it only took 16 moves even though I randomly walked 20 moves from the goal state, implying it found a better solution than the path the random walker took.

The number of states expanded rose sharply to 16000. You can see how this could get out of hand very quickly.

15 TILE

Let’s try the same experiments on the 15 tile problem. With the algorithm being ran in the browser, my assumption is that we’ll exceed the memory limit and likely crash the browser – worth a shot anyway.

10 random moves from the goal

9246 expanded states, not too bad.

20 random moves from the goal

Just as I had expected, it crashed the browser, and also crashed my website so I lost part of my blog!

Informed search

As mentioned previously in order to solve the 15 tile – and even difficult configurations of 8 tile – we’d need to utilise an informed search algorithm. Uninformed search often expands states that pursue a direction alternative to the goal path, which can lead to searches taking an extensive amount of time and/or space. Informed search attempts to minimise this by producing intelligent choices for each selected state. This implies the use of a heuristic function which evaluates the likelihood that a given node is on the solution path. A heuristic is a function that ranks possible moves at each branching step to decide which branch to follow.

The goal of a heuristic is to produce a fast estimation of the cost from the current state to the desired state, the closer the estimation is to the actual cost the more accurate the heuristic function. In the context of the sliding-tile puzzle, to find best move from a set configuration the heuristic function is executed on each of the child states, the child state with the smallest heuristic value is chosen.

My next blog will be solving the sliding-tile puzzle using informed search, particularly the A* algorithm.

Check out my previous blog What Is Simulated Annealing? – that was a really fun one.

What is Simulated Annealing?

Luke Garrigan — Sat, 22 May 2021 18:31:47 +0000

What Is Simulated Annealing?

Today I’ve been playing around with simulated annealing, which is just a probabilistic technique for approximating the global optimum. Don’t let that put you off, it sounds far more complicated than it really is.

The name of the algorithm is stolen from metallurgy. Annealing is a heat treatment that alters the physical and sometimes chemical properties of a material, it involves heating a metal and then slowly cooling at a specific rate.

I have put together a really simple example to help explain the purpose and application of such an algorithm.

Hill climbing

Let’s say our protagonist is a skier. Skiers – I assume – always want to get to the highest point of the mountain so they can ski as fast as possible. Let’s write a very simple algorithm that determines how the skier climbs the mountain.

findHighestPoint() {
    if (this.heightOfHillToRight() >= this.y) {
        this.x++;
    } else {
        this.x--;
    }
}

Seems simple enough. If the position to our right is the same height or higher let’s move to the right, otherwise let’s move to the left.

We’ve cracked it haven’t we? Our skier can find the top of every mountain?

Not quite:

Our skier has hit what we call the local maxima, where it thinks it’s at the highest point. In order for the skier to find the global maxima (Highest point) it’ll first need to go down before it goes up. This is where simulated annealing comes in.

The algorithm

Choose a neighbour
Calculate the cost of the neighbour
Compare the new cost with the old cost
1. if (newCost < oldCost): move to neighbour
2. if (newCost > oldCost): potentially move to neighbour
Repeat until a solution is found or we reach the maximum iterations

Let’s put this into plain English for our simple hill climbing example.

Choose a neighbour: This will simply be a position on the hill the skier can move to.

Calculate the cost of the neighbour: This is the height of the hill at that position, so for us the higher the better - meaning the cost goes up as the hill goes down.

Compare the new cost with the old cost: So if the new position is at a higher point on the mountain then we will move to that position. If the new position is not at a higher point on the mountain we will potentially move to that position (This is the important bit).

The temperature

The temperature is very important to the algorithm, it controls the probability of us choosing to go down the hill in the hope to go up at a later point.

The temperature will start at 1.0 and will be decreased each iteration by some constant, in my example I use 0.99.

The equation that we’re going to use to determine the acceptance probability, i.e the probability of us going down the hill is:

 const prob = Math.exp((this.score-newScore)/this.temp);

For a given neighbour, the probability will get smaller as the iterations tick by (Because the temperature decreases each iteration). Meaning the likelihood of us choosing to go down decreases.

simulatedAnnealing() {
    if (this.temp < this.minTemp) return;
    for (let neighbour of this.getNeighbours()) {
      if (neighbour.score > this.score) {
        this.x = neighbour.x;
      } else {
        const prob = Math.exp((this.score-neighbour.score)/this.temp);
        if (random() >= prob) {
          this.x = neighbour.x;
        }
      }
    }
    this.temp *= this.alpha;
}

Let’s put it to the test

Awesome, in this example you can see how the temperature decreased as it tried to go back down the hill towards the end but eventually decided against it!

Let’s try a more complicated example:

Conclusion

Well, I had a lot of fun implementing that, if you want to have a trawl through the code I wrote or mess with the algorithm yourself – go here and have a play!

I took a lot of inspiration for this blog from this post by Katrina Ellison
and got the hill climbing idea from this video by Erir Schirtzinger so credit to them!

How To Code Snake 🐍

Luke Garrigan — Sat, 15 May 2021 13:20:50 +0000

I wouldn't usually post a blog like this to dev as it's something I usually do for myself, game dev is fun and I get a lot of enjoyment out of it. If you enjoy this blog please let me know and maybe I'll post more here!

Nokia’s snake was launched in 1997 with the Nokia 6110, the catalyst for mobile gaming! The concept of the game snake, however, existed long before the 1997 version. In another blog, I talk about How to code Blockade (1976) which is essentially player vs player snake a good 21 years before!

In this blog, I’m going to go through the step-by-step process of coding the game Snake, as it is commonly prescribed to beginner programmers as the game to code. However, I wouldn’t personally recommend this game to beginner programmers as Snake certainly has some tough quirks you have to figure out. If you are a new programmer I’d recommend taking a look at Top 5 BEST games to code as a beginner! or, if you’ve never coded before at all then take a look at How To Code A Game As A Beginner.

Let’s get started coding snake!

So for this blog, I’m going to be using https://editor.p5js.org/ which uses the p5.js library which makes using the Canvas a more pleasant experience. All the code that I’m writing for this blog can be found here so feel free to use that as a reference if you get stuck.

Making a grid for the snake to live

If you study the game of snake you can kind of see that everything is placed within a hidden grid, let’s create our own grid – which will be removed at the end – so we can keep everything in place and make our lives easier.



const GRID_SIZE = 20;

function setup() {
   createCanvas(700, 700);
}

function draw() {
  background(155, 204, 153);

  for (let x = 0; x < width; x += width / GRID_SIZE) {
    for (let y = 0; y < height; y += height / GRID_SIZE) {
        stroke(255);
        strokeWeight(1);
        line(x, 0, x, height);
        line(0, y, width, y);
    }
  }
}

Which should give you something like this:

Now we can tinker with GRID_SIZE to fit our game to our liking at any stage. This is an important variable, the snake's position and the food's position will be based on this.

Creating the Snake

Let's create a new file called snake.js which'll contain a class for our snake. Don't forget to add the reference to your index.html so we can use it:



  <body>
    <script src="sketch.js"></script>
    <script src="snake.js"></script> // add this
  </body>

SNAKE.JS



class Snake {
  constructor() {
    this.body = [];
    this.body.push({x: width/2, y: height/2}); // the head of the snake
    this.dir = 1; // 1 = right, 2 = down, 3 = left, 4 = right
  }

  draw() {
    fill(0);
    for (let b of this.body) {
      rect(b.x, b.y, width / GRID_SIZE, height / GRID_SIZE)
    }
  }

  update() {
    if (this.dir == 1) {
      this.body[0].x += width / GRID_SIZE;  
    } else if (this.dir == 2) {
      this.body[0].y += height / GRID_SIZE;
    } else if (this.dir == 3) {
      this.body[0].x -= width / GRID_SIZE;
    } else if (this.dir == 4) {
      this.body[0].y -= height / GRID_SIZE;
    }
  }
}

So we've created a body for our snake which is an array that'll contain the x and y locations of the part of the body. We're also adding the head of the snake to the body in the constructor, so when we new up the Snake object.

I'm pre-empting the movement of the snake, I know it's going to be able to move either up down left or right, so if the dir value is set to 1 then we're going right, if it's set to 2 then we're going down, 3 then we're going left and 4 is up.

We've also got a draw method which simply draws the rectangles representing the body of the snake.

And finally, the update method which just moves the head of the snake in the direction we're moving. Note, I only move the head of the snake because if I were to move the whole snake in a given direction then it wouldn't look like a snake at all. We're going to need to come back to this method as we will need to update the rest of the body - when we have the rest of the body and not just the head.

SKETCH.JS

Back in sketch.js we need to create the snake object and call our update/draw methods. Also, we'll limit the framerate to 4 to give us that retro feel!



const GRID_SIZE = 20;

let snake;
function setup() {
  createCanvas(700, 700);
  snake = new Snake();
  frameRate(4);
}

function draw() {
  background(155, 204, 153);
  for (let x = 0; x < width; x += width / GRID_SIZE) {
    for (let y = 0; y < height; y += height / GRID_SIZE) {
        stroke(255);
        strokeWeight(1);
        line(x, 0, x, height);
        line(0, y, width, y);
    }
  }

  snake.update();
  snake.draw();
}

Then when you hit play you should have something like this:

Adding key pressed handlers

When we hit the arrow keys we want to change direction, add this function to your sketch.js



function keyPressed() {
  if (keyCode === 39 && snake.dir !== 3) {
    snake.dir = 1;
  } else if (keyCode === 40 && snake.dir !== 4) {
    snake.dir = 2;
  } else if (keyCode === 37 && snake.dir !== 1) {
    snake.dir = 3;
  } else if (keyCode === 38 && snake.dir !== 2) {
    snake.dir = 4;
  } 
}

So this is saying when we press right and we're not going left change direction to the right, when we press down and we're not going up, go down, etc.

Have a little play:

Adding food for the snake

When the snake eats food, it grows, let's feed it.

FOOD.JS

Create a new file food.js and remember to add the reference to this in your index.html.



class Food {
  constructor() {
    this.spawn();
  }

  spawn() {
    let randX = random(width);
    let randY = random(height);
    this.x = randX - randX % (width / GRID_SIZE);
    this.y = randY - randY % (height / GRID_SIZE)
  }

  draw() {
    fill(255, 100, 100);
    rect(this.x, this.y, width / GRID_SIZE, height / GRID_SIZE);
  }
}

So we're giving the food a random location in the grid, the code randX - randX % (width / GRID_SIZE); is just allowing us to align the food within a grid square.

We've added the food but not given our snake the means to eat it 😢 Let's give him a mouth.

In our main draw function in sketch.js



...
function draw() {
  background(155, 204, 153);
  for (let x = 0; x < width; x += width / GRID_SIZE) {
    for (let y = 0; y < height; y += height / GRID_SIZE) {
        stroke(255);
        strokeWeight(1);
        line(x, 0, x, height);
        line(0, y, width, y);
    }
  }

  snake.update();

  if (snake.hasEatenFood()) {   // add this code
    food.spawn();
  }

  snake.draw();
  food.draw();

}

We've not yet written the hasEatenFood method so let's add that in snake.js



...
hasEatenFood() {
    if (this.body[0].x == food.x && this.body[0].y == food.y) {
      return true;     
    }
  }

Awesome! Now our snake can eat and not get bigger, jealous? Let's add some code to make our snake grow.

SNAKE.JS

So there's a few things here we need to add, here's the whole finished file, I'll explain what's added below:



class Snake {
  constructor() {
    this.body = [];
    this.body.push({x: width/2, y: height/2}); // the head of the snake
    this.dir = 1; // 1 = right, 2 = down, 3 = left, 4 = right

    this.lastX = width/2;
    this.lastY = height/2;
  }

  draw() {
    fill(0);
    for (let b of this.body) {
      rect(b.x, b.y, width / GRID_SIZE, height / GRID_SIZE)
    }
  }

  update() {
    this.lastX = this.body[this.body.length-1].x;     // track the last X and Y  
    this.lastY = this.body[this.body.length-1].y;     // so we can put the new body there
    for (let i = this.body.length-1; i >= 1; i--) {
      this.body[i].x = this.body[i-1].x;
      this.body[i].y = this.body[i-1].y;
    }

    if (this.dir == 1) {
      this.body[0].x += width / GRID_SIZE;  
    } else if (this.dir == 2) {
      this.body[0].y += height / GRID_SIZE;
    } else if (this.dir == 3) {
      this.body[0].x -= width / GRID_SIZE;
    } else if (this.dir == 4) {
      this.body[0].y -= height / GRID_SIZE;
    }
  }

  grow() {
    this.body.push({x: this.lastX, y: this.lastY});
  }

  hasEatenFood() {
    if (this.body[0].x == food.x && this.body[0].y == food.y) {
      return true;     
    }
  }

}

We now track the lastX and the lastY of the snake so that when the snake eats that position is basically where the food goes, it effectively goes straight to its butt. I've also added code to update the whole body of the snake, so in the update method you'll see the code:



    for (let i = this.body.length-1; i >= 1; i--) {
      this.body[i].x = this.body[i-1].x;
      this.body[i].y = this.body[i-1].y;
    }

This is updating each body to be the x and y of the element before it, remember the head is at index 0.

And we've also added the grow() method which simply appends to the array with the new body.

Adding hit detection

We want to make sure that the snake doesn't bump into itself, and if it does then we need to restart the game.

I've added a new method hitDetection() that gets called in the update() of the snake class:



  hitDetection() {
    for (let i = 1; i < this.body.length; i++) {
      if (this.body[0].x == this.body[i].x && this.body[0].y == this.body[i].y) {
        this.spawn();
      }
    }
  }

So this simply checks to see if the head of the snake hits any other part of its body. I've also moved the constructor code into a spawn() method the same as the food class, here's all the code:



class Snake {
  constructor() {
    this.spawn();
  }

  // added this
  spawn() {
    this.body = [];
    this.body.push({x: width/2, y: height/2}); 
    this.dir = 1; 
    this.lastX = width/2;
    this.lastY = height/2;
  }

  draw() {
    fill(0);
    for (let b of this.body) {
      rect(b.x, b.y, width / GRID_SIZE, height / GRID_SIZE)
    }
  }

  update() {
    this.hitDetection();

    this.lastX = this.body[this.body.length-1].x;   
    this.lastY = this.body[this.body.length-1].y;     
    for (let i = this.body.length-1; i >= 1; i--) {
      this.body[i].x = this.body[i-1].x;
      this.body[i].y = this.body[i-1].y;
    }

    if (this.dir == 1) {
      this.body[0].x += width / GRID_SIZE;  
    } else if (this.dir == 2) {
      this.body[0].y += height / GRID_SIZE;
    } else if (this.dir == 3) {
      this.body[0].x -= width / GRID_SIZE;
    } else if (this.dir == 4) {
      this.body[0].y -= height / GRID_SIZE;
    }
  }

  // added this
  hitDetection() {
    for (let i = 1; i < this.body.length; i++) {
      if (this.body[0].x == this.body[i].x && this.body[0].y == this.body[i].y) {
        this.spawn();
      }
    }
  }

  grow() {
    this.body.push({x: this.lastX, y: this.lastY});
  }

  hasEatenFood() {
    if (this.body[0].x == food.x && this.body[0].y == food.y) {
      return true;     
    }
  }

}

Losing the grid

Next, let's remove the code we added for our grid, it was simply there to make sure everything was kept in line!

So your draw function in sketch.js should look like this:



function draw() {
  background(155, 204, 153);
  /**
  let x = 0; x < width; x += width / GRID_SIZE) {
  for (let y = 0; y < height; y += height / GRID_SIZE) {
      stroke(255);
      strokeWeight(1);
      line(x, 0, x, height);
      line(0, y, width, y);
    }
  }
  */
  snake.update();

  if (snake.hasEatenFood()) {
    food.spawn();
    snake.grow();
  }
  stroke(155, 204, 153); // add this
  snake.draw();
  food.draw();

}

What's next?

The most complicated parts of Snake are done, but there are still some things we need to tweak. The best way to learn is by doing, so I challenge you to continue on with the coding and see if you can complete the following tasks. Please let me know if you manage any/all of them, I'd really appreciate that!

When the snake hits the edge of the map the game should restart or the snake should come out the other side of the wall
Add a scoring system and display the number (Could just be the snakes body length)
Make sure the food doesn't spawn on the snake's body.
Start the snake off already with a body size of 5

Create Fake Data Easily Using JavaScript

Luke Garrigan — Thu, 13 May 2021 07:07:47 +0000

Ever need to populate a table or generate some data to see what your GUI looks like when it’s in use? Need to test the performance of your application under load? Have to do a demo but you don’t have any legitimate data to do the demo as it’s pre-release?

Usually in this scenario, a programmer has one of two options:

Manually input the data by hand
Code your own seeding application that does it all for you

Neither of these scenarios are ideal. Manually inputting data by hand can take time, a lot of time. Coding your own seeding application is not as easy as you’d think, you need to understand the process of generating random text, dummy images, random dates, names, emails, etc.

What is Faker.js

Introducing Faker.js a brilliant solution to help you generate data and seed your application. Faker.js can be used either in the browser, or using node.js. All the problems and quirks with generating random data – some listed above – have been thought of and solved in Faker, so we don’t need to spend any more time reinventing the wheel.

Generating User Data

The most common scenario I can think of – and was required at work just a couple weeks ago – is generating User data. Let’s create a dummy node app that has a GET/ users request that’ll return a list of generated users. For the sake of this blog I’ll leave out the complexities of pagination, I’ll just return an array of 100 users.

const express = require("express");
const app = express();
app.listen(3000, () => {
 console.log("Server running on port 3000");
});

app.get("/users", (req, res, next) => {
    res.json([
        {
            "name": "Douglas Adams",
            "email": "douglas@gmail.com",
            "postcode": "pe22 22a",
            "phoneNumber": "07428233312",
            "city": "London",
            "country": "England",
            "favouriteQuote": "The answer is 42"
        }
    ]);
});

So if we call the endpoint GET http://localhost:3000/users:

Response:

[
    {
        "name": "Douglas Adams",
        "email": "douglas@gmail.com",
        "postcode": "pe22 22a",
        "phoneNumber": "07428233312",
        "city": "London",
        "country": "England",
        "favouriteQuote": "The answer is 42"
    }
]

This is the basic format of the data we want to generate. Let’s make use of Faker to do this for us.

Faker is super simple, all you need to do is scan their README.md for a good understanding of how they’ve structured it. Basically, there’s a list of objects that you can reference and each of those objects have methods that you can call. For example, there’s an address which has methods such as:

zipCode()
zipCodeByState()
city()
cityPrefix()
citySuffix()
// and a load more

So to get a random zip code I’d simply need to make the following call:

faker.address.zipCode()

Let’s incorporate this into our code:

npm install faker

const express = require("express");
const faker = require('faker');
const app = express();
app.listen(3000, () => {
 console.log("Server running on port 3000");
});

app.get("/users", (req, res, next) => {
    res.json([
        {
            "name": faker.name.findName(),
            "email": faker.internet.email(),
            "postCode": faker.address.zipCode(),
            "city": faker.address.cityName(),
            "country": faker.address.country(),
            "phoneNumber": faker.phone.phoneNumber(),
            "favouriteQuote": faker.lorem.sentence()
        }
    ]);
});

So now when I make the request, the response it returns is:

[
    {
        "name": "Darnell Marquardt",
        "email": "Braden_Block@gmail.com",
        "postCode": "56653",
        "city": "Mount Vernon",
        "country": "Paraguay",
        "phoneNumber": "987-214-5854 x674",
        "favouriteQuote": "Harum veritatis est dolore amet nam debitis."
    }
]

And if I run it again I’ll get a different result:

[
    {
        "name": "Victoria Kerluke V",
        "email": "Valentin.Beahan@hotmail.com",
        "postCode": "15058",
        "city": "Kendall",
        "country": "Serbia",
        "phoneNumber": "751.325.8108 x50407",
        "favouriteQuote": "Deserunt rerum maiores."
    }
]

Next, let’s update the code so it actually returns an array of 100 users:

app.get("/users", (req, res, next) => {
    res.json(getUsers());
});

function getUsers() {
    let users = [];
    for (let i = 0; i < 100; i++) {
        users.push({
            "name": faker.name.findName(),
            "email": faker.internet.email(),
            "postCode": faker.address.zipCode(),
            "city": faker.address.cityName(),
            "country": faker.address.country(),
            "phoneNumber": faker.phone.phoneNumber(),
            "favouriteQuote": faker.lorem.sentence()
        })
    }
    return users;
}

Response:

[
    {
        "name": "Sandra Schaefer",
        "email": "Bethany12@yahoo.com",
        "postCode": "65665",
        "city": "Palm Harbor",
        "country": "Slovakia (Slovak Republic)",
        "phoneNumber": "379-607-0449",
        "favouriteQuote": "Qui consectetur repellendus commodi."
    },
    {
        "name": "Mark Veum",
        "email": "Jedediah.Beer26@yahoo.com",
        "postCode": "89859",
        "city": "Montebello",
        "country": "Myanmar",
        "phoneNumber": "779.494.2905 x0531",
        "favouriteQuote": "Corrupti assumenda enim alias suscipit maxime molestiae quis laboriosam."
    },
   // you get the idea..

Using a seed

Let's imagine a scenario. You're doing a demonstration of the new users page, you click to open up the page, a GET users request is made, random users are returned. You spend a little time on the page, people become accustomed to the names of the users in the table. Then you come off the page to change some config. You go back to the page, a GET users request is made and different random users are returned, "What happened to Sandra" someone asks.

The thing that I love most about Faker, is that you can use a randomness seed meaning you can get consistent results every time you make a call. This is something that you most likely wouldn't implement if you were creating your own random data, well at least, I wouldn't.

Let's use a seed in our request:

app.get("/users", (req, res, next) => {
    faker.seed(123);
    res.json(getUsers());
});

Now every time I make a request the same data gets returned:

Going to the users page for the first time:

[
    {
        "name": "Clara Keebler",
        "email": "Maryse_Lubowitz49@gmail.com",
        "postCode": "79465",
        "city": "Lancaster",
        "country": "Burundi",
        "phoneNumber": "536.734.2063",
        "favouriteQuote": "Id harum sit odio quia vitae provident."
    },
    {
        "name": "Kristin Nicolas",
        "email": "Roslyn_Kulas61@gmail.com",
        "postCode": "74363",
        "city": "Guaynabo",
        "country": "Czech Republic",
        "phoneNumber": "496-807-4041",
        "favouriteQuote": "Sequi molestiae beatae enim necessitatibus molestiae."
    },
   // etc

Coming back to the users page:

[
    {
        "name": "Clara Keebler",
        "email": "Maryse_Lubowitz49@gmail.com",
        "postCode": "79465",
        "city": "Lancaster",
        "country": "Burundi",
        "phoneNumber": "536.734.2063",
        "favouriteQuote": "Id harum sit odio quia vitae provident."
    },
    {
        "name": "Kristin Nicolas",
        "email": "Roslyn_Kulas61@gmail.com",
        "postCode": "74363",
        "city": "Guaynabo",
        "country": "Czech Republic",
        "phoneNumber": "496-807-4041",
        "favouriteQuote": "Sequi molestiae beatae enim necessitatibus molestiae."
    },
   // etc

Summary

Generating random data is something all programmers will have to do at some point. With Faker.js it's an easier ride. Simply npm install for a node app or add it to your frontend solution. Need some data but don't have a backend to supply the data yet, then use faker.js.

Fast prototyping without worrying about the backend

Luke Garrigan — Sun, 25 Apr 2021 19:06:40 +0000

This week I had a small project I wanted to prototype with an even smaller timescale, so I did the obvious thing, rather than actually getting on with it I did a google trying to find faster ways to prototype the project without having to implement the CRUD endpoints I'd need.

I came across crudcrud.com which did exactly what I was hoping for; it generates a unique API endpoint address for you so that you can append any REST resource to it. (I have no affiliation with crudcrud.com I just found the website very useful, enough to make me want to write about it).

So let's say - because there isn't enough already - we're going to create a note-taking app. But we've got this really cool frontend idea that we want to demo with some working data. In comes crudcrud.com.

Let's open the site and grab the URL it's provided us:

https://crudcrud.com/api/b431386d6a404a768024221e158b3b17

Next step, let's open Postman (Or whatever tool you use to test APIs). I want to create a /notes resource so I'm going to create POST a request to store a note.

POST

https://crudcrud.com/api/b431386d6a404a768024221e158b3b17/notes

{
    "name": "How to write a good blog?",
    "note": "Well, first you'd have to be a writer for codeheir.com",
    "author": "Codeheir"
}

Which gives you the response:

{
    "name": "How to write a good blog?",
    "note": "Well, first you'd have to be a writer for codeheir.com",
    "author": "Codeheir",
    "_id": "6085b55113120c03e81c9522"
}

Now, I can make use of the _id it returns to make a GET request to retrieve the entity, PUT to update the entity, and DELETE to delete the entity.

PUT

I've since updated the note that I wrote above, so I'd like to let the backend know about this to store it. Let's create a PUT request to do that. Now if I append the _id of the note to the URL and update the method to PUT.

https://crudcrud.com/api/b431386d6a404a768024221e158b3b17/notes/6085b55113120c03e81c9522

{
    "name": "How to write a good blog? 🚀",
    "note": "Well, first you'd have to be a writer for codeheir.com and use emojis whenever possible 🔥",
    "author": "Codeheir"
}

GET entity

Now I can perform a GET to view my newly updated note.

https://crudcrud.com/api/b431386d6a404a768024221e158b3b17/notes/6085b55113120c03e81c9522

And the response:

{
    "_id": "6085b55113120c03e81c9522",
    "name": "How to write a good blog? 🚀",
    "note": "Well, first you'd have to be a writer for codeheir.com and use emojis whenever possible 🔥",
    "author": "Codeheir"
}

GET resource

Now, for my UI I want to retrieve all of the notes so that I can display them. To do that we perform a GET on the resource itself.

https://crudcrud.com/api/b431386d6a404a768024221e158b3b17/notes

Which returns all of our notes:

[
    {
        "_id": "6085b55113120c03e81c9522",
        "name": "How to write a good blog? 🚀",
        "note": "Well, first you'd have to be a writer for codeheir.com and use emojis whenever possible 🔥",
        "author": "Codeheir"
    },
    {
        "_id": "6085b89413120c03e81c9525",
        "name": "Test blog",
        "note": "This is just a test blog, delete it later",
        "author": "Codeheir"
    }
]

DELETE

As you may have seen from the request above, I have a note that I don't really care for, I've even mentioned in the note that I'll delete it later, let's go ahead and do that by creating a DELETE request:

https://crudcrud.com/api/b431386d6a404a768024221e158b3b17/notes/6085b89413120c03e81c9525

Now when I perform the GET resource request I should no longer see the deleted entity:

https://crudcrud.com/api/b431386d6a404a768024221e158b3b17/notes

[
    {
        "_id": "6085b55113120c03e81c9522",
        "name": "How to write a good blog? 🚀",
        "note": "Well, first you'd have to be a writer for codeheir.com and use emojis whenever possible 🔥",
        "author": "Codeheir"
    }
]

And that's pretty much it, a really powerful website to create quick prototypes so you don't need to worry yourself about all the layers involved in getting a backend going.

Let me know if you have any other tips for creating quick prototypes, I'm all for speeding up the process!

Neural Network Learns to Drive

Luke Garrigan — Sat, 10 Apr 2021 18:49:43 +0000

This week I've been playing around with neural networks, or more specifically neuroevolution of augmenting topologies (NEAT) which is nowhere near as complicated as it sounds. I'll go over the ins and outs of NEAT in a future blog. For now, just know that NEAT is a matter of combining the strengths of a genetic algorithm and a neural network to form something quite powerful, as this blog will show!

Starting simple

As with anything I know nothing about, I like to try and implement it in the simplest way possible and then iterate and expand on the implementation. I did this in my previous blog where I developed a simple genetic algorithm for a game where the goal was for the protagonist to move up, and that's it. This week was no different.

Flappy bird

One of the simplest games I could think of to get the ball rolling is Flappy bird as the rules and actions are quite simple, the bird must go through the pipes, and the bird does that by choosing one of two actions: flap wings or don't flap wings.

Luckily, I coded my own flappy bird for a YouTube video I did a while back. I'll grab that and attempt an implementation of NEAT.

Generation 1

I spawn a population of 100 birds with a random neural network. The neural network takes as input the x/y of the bird and the x and y of the top pipe.

As you can see, the first generation only 1 bird makes it through the first set of pipes, this means that bird is more likely to pass on its genetic material.

Generation 20

By generation 20 the bird is getting through a few pipes now and seems to have developed an understanding of the game and its objective.

Generation 30

By generation 30 the bird has mastered the game and continues on indefinitely.

The bird likes to live on the edge though, look how close it gets to the top pipes!

Self-driving car

Okay, so now I've got a pretty good idea of the implementation let's bring this code into my car game. If you're interested in how the reward mechanism works I cover it in detail in this blog, but basically there are checkpoints, and if the car drives over a checkpoint their score increments.

Inputs

So I think the only inputs the neural network really needs are some sensors, similar - but more primitive - than the sensors your car might have. So I'm going to choose 3 points that'll represent the sensors. The value of each sensor will be either 0 or 1, where 0 represents on track and 1 represents you're about to die.

I do this by taking the pixels of the track and then determine the RGB of the pixel at the location of the sensor, and if that RGB is not the same colour as the track, then it's safe to assume that going that way is probably not a good idea, but can my neural network figure that out.

The green dots represent the sensors.

The code for determining whether a sensor is still on the road looks like the following:

    let infrontCollision = 0
    const index = 4 * (floor(this.s1.y) * width + floor(this.s1.x));
    if (pixels[index] != 110 && pixels[index+1] != 111 && pixels[index+2] != 114) {
      infrontCollision = 1;
    }

Generation 0

Let's create a population of 100 with a mutation rate of 5% and see how it fairs:

I must admit, when I first ran this I was blown away. To get this far using just a traditional genetic algorithm took way over 100 generations. It's as though the car knew its purpose from the get-go!

Generation 2

By generation 2 we already have cars that can complete a full circuit of the track! Which took over 250 generations in my previous blog, quite remarkable.

Can it race another track?

One of the drawbacks of using just a genetic algorithm was that it adapted to the environment it was in, each generation had to learn how to get around a corner and then pass on that genetic information so that its children could get around the corner and attempt the next. Here though, we're using live information and teaching the car to stay on the track, and hopefully any track - provided the grey is the same ðŸ˜

Exporting the model

The neural network is essentially the brains of the car, when a car is successful I can essentially export their brain and inject it into another car. In the example below, I inject the brain of a successful car from the other track onto this brand new track and it already knows what it's got to do!

Conclusion

Well, that concludes this week's hacking! If you enjoyed my writing please sign up for my newsletter! All the code written in this blog can be found here although I very likely will have edited it by the time this blog is live.

As mentioned in my previous blog thanks to Daniel Shiffman for the inspiration and great tutorials opening my eyes to this mysterious world!

Genetic Algorithms In JavaScript

Luke Garrigan — Sat, 03 Apr 2021 14:02:38 +0000

This week I've been having a play around with genetic algorithms and had a tonne of fun.

What are genetic algorithms?

Genetic algorithms are inspired by Charles Darwin's theory of evolution. The premise being the most successful individuals reproduce and pass on their genetic traits to their offspring, i.e. natural selection.

There are 5 steps to the algorithm:

Creating a new generation
Evaluating individuals
Selection
Reproduction
Mutation

And these steps are repeated continuously until you find your goal. These steps will be explained in more detail in the example below.

My first genetic algorithm

There's no better way to understand an algorithm than to write it yourself, so I did exactly that. My first genetic algorithm was made using JavaScript with the p5.js library.

The goal for the algorithm is very simple, go from one point to another, and the quicker you get there the better. So I'm going to spawn a circle, that has a random set of forces that get applied to it sequentially - this is its genes.



 createGenes() {
    let s = [];
    for (let j = 0; j < GENE_LENGTH; j++) {
       s[j] = p5.Vector.random2D();
    }
    return s;
  }

Now let's create a number of these individuals, this is our population:

Now, after a certain amount of time or if one of the individuals reach the target I'll need to select the most successful in the population in order to reproduce. To do this we need to calculate its fitness function. Fitness is a value that'll represent how successful an individual was, usually the value will be normalised - an individual with a 0.9 fitness is better than an individual with 0.3 fitness.

So to calculate the fitness for my example I need to determine how far away from the goal they are, the closer they are to the goal the higher the fitness:



 calcFitness(pos) {
    const distanceToGoal = dist(pos.x, pos.y, goal.x, goal.y);
    let normalised = distanceToGoal / height;
    this.fitness = 1 - normalised;
  }

The penultimate step is selection, selection is just a means of giving the successful individuals a higher chance of reproducing. To do this I'm going to stick the individuals into an array proportional to their fitness score. So an individual with a fitness of 0.9 will get put into the array 90 times and an individual with a fitness of 0.5 will get put in 50 times. The next generation will be randomly selected from this array, so each subsequent generation should - in theory - get stronger.




function naturalSelection() {
  matingPool = [];
  for (let pop of population) {
    let n = floor(pop.fitness() * 100); 
    for (let i = 0; i < n; i++) {
      matingPool.push(pop);
    }
  }
}

The last step is reproduction, so using that array we've just created we will find two random individuals and cross their genetic material to create a child.



function reproduce() {
  for (let i = 0; i < population.length; i++) {
    let mummyIndex = floor(random(matingPool.length));
    let daddyIndex = floor(random(matingPool.length));

    let mummy = matingPool[mummyIndex];
    let daddy = matingPool[daddyIndex];

    let child = mummy.crossover(daddy);
    child.mutate(mutationRate);
    population[i] = child;
  }
}

The term for the mixing of the genes is crossover which can be done in a number of ways, the approach I'm taking is simply combining the genes so that each element alternates between mummy gene and daddy gene:



[M,D,M,D,M,D,M,D,M,D,M,D]



 crossover(partner) {
    let child = new DNA();
    child.genes = [];
    for (let i = 0; i < this.genes.length; i++) {
      if (i % 2 ==0) {
        child.genes.push(this.genes[i]);
      } else {
        child.genes.push(partner.genes[i]);
      }
    }
    return child;
  }

Another example for crossover is to literally split the genes in half, so the first half of the child's genes are from daddy and the second half are from mummy.

You'll notice, in the code before the last snippet there's a line which calls a mutate function, this is the final step - the mutation step allows us to maintain genetic diversity much like biological mutation. The function takes a mutationRate which is some percentage (2% in my example).

So the code here is quite simple, I loop through every gene and if the random value is less than the mutationRate then I'll create a random vector.



 mutate(mutationRate) {
    for (let i = 0; i < this.genes.length; i++) {
      if (random(1) < mutationRate) {
         this.genes[i] = p5.Vector.random2D(); 
      }
    }
  }

Let's see it in action:

Generation 0

All movements are completely random and no individuals reach the goal.

Generation 20

All individuals seem to be heading in the correct direction - up. There's still quite a lot of random side-to-side movement though. But at least they reach the destination!

Generation 50

It's now reaching the goal with a bit of speed! So much room to improve though, I'll let it run for a while!

Generation 550

Now we're talking ⏩⏩⏩

Genetic algorithm racer

Getting a circle to fly up is really quite a simple problem, I wanted to up the ante a little and create a racing game where the car would have to find its way around the track. Note, all the code for the following Genetic Algorithm can be found here.

Okay, I should probably add some hit detection and some way to calculate their fitness. I'm going to start off really simple and assume that the longer the car is alive, the more successful it is.



 calcFitness(timeAlive) {    
    this.fitness = map(timeAlive, 0, 10000, 0, 1);
  }

Everything else is pretty much the same as the previous genetic algorithm, apart from, the individual's genetic code represents an angle to turn the car - they move at a constant speed, the only thing that changes is the steering.

Let's see them drive!

Generation 0

Generation 10

We've cleared the first corner (The green car represents the last most successful car, I add that to the gene pool each iteration so it doesn't get any worse!)

Generation 50

We've got around the second corner - nearly. Not many cars seem to be reaching near to the end, maybe the mutation rate is a little high at 3%.

Insufficient fitness function

The fitness function I'm using is pretty awful, if you take a look at the example below. The car that gets the furthest isn't considered the best because it didn't stay alive for the longest time. So my fitness function is essentially promoting poor driving!

The better fitness function

I'm sure that given enough time, my old fitness function might well complete the track after a few million generations, I lack the patience to see.

Checkpoints

I'm going to update the track so that it it has checkpoints, if a car passes the checkpoint it'll add to their score, their score is their fitness function. This method should hopefully prevent the previous issues.

The circles represent the checkpoints (They won't be visible)

I've also added some code to alter how the mutation works, so that it only mutates genes near to where the car's ancestors crashed. So basically I won't be losing any cars early on.



mutate(mutationRate) {

    for (let i = ancestorDiePoint-buffer; i < this.genes.length; i++) {

      if (random(1) < mutationRate) {

         this.genes[i] = random(-TURN_MAX, TURN_MAX);

      }

    }

  }

Generation 50:

By Generation 50 it looks as though the end is in sight!

Generation 250 🥳:

Finally

Yey, the car made it. I created a genetic algorithm that can drive itself around a track, that's great. But now, what if I want to export the genes for the car that reached the end and put it onto another track? It'd be useless. Why? Because the steering/dna is specific to this current track. If we want to create a general-purpose self-driving racing car that can be plonked onto any track then we're going to need something a little more than a genetic algorithm, we're going to need a Neural Network which I'm going to be covering in my next blog, next week!

This blog was largely inspired by Daniel Shiffman's YouTube course on genetic algorithms so big thanks to him!

Regex: From beginner to BEST on your team in one blog 👑

Luke Garrigan — Sun, 21 Mar 2021 12:19:43 +0000

Recently I've been doing quite a lot of work using Regex and to be honest, I was pretty shite at it. It's one of those things that has been on my to-learn for years, but I've never really got round to it, because - like most people - I google a regex problem and see how other people have solved it rather than doing it myself.

What is regex

So if you don't know what regex is, don't worry this blog should be suitable for devs at all levels! Regex is short for Regular Expression which is a sequence of characters that specifies a search pattern. We use it reasonably frequently in programming to search for patterns in strings either to pull the information out or to make changes to it.

Let's get started

In this blog I recommend you open up https://regexr.com/ which is an online tool to evaluate regex, allowing you to put in test strings to see if your regex is working. Follow along with me making sure to use your own test strings to really solidify your understanding.

Slashes

The first thing you'll see is the slashes, one at the start and one at the end, they simply indicate when a regex starts and when a regex ends.

Flags

After the end slash you may have noticed there is usually a letter at the end. These are called flags, there are 6 flags:

g - global search, meaning it'll match all occurrences, this is the most common and will be used for the rest of the blog
i - ignore case, meaning case-insensitive
m - multiline mode, which will make more sense when we cover the ^ and $ below.

u, y, s are the others but won't be covered in this blog as I I've never really seen them used so I wouldn't consider them a learning priority. If you are interested, you can learn more here.

Exact matching

To start off with let's begin with exact character matching, let's say we want to match on the word Panic, all we have to do is write the thing.

/Panic/g

Which is probably what you want most of the time, and if it is, you likely don't need regex. But, anything a little more involved will require quantifiers, which we'll get onto.

Quantifiers

The `+`

The plus character + means match one or more of the preceding token. So in our example below, match the letter l one or more times.

/l+/g

The `?`

The question mark ? is the optional symbol, it means anything that is before it is optional. So in our example, we are searching for i and f if it exists, but if f doesn't exist don't worry yourself, we'll take the i. So the optional-ness is just the first token that precedes the ?, which is f.

/if?/g

The `*`

The * is basically a combination of the + and the ?. It matches 0 or more of the preceding token. So it's optional and if there are multiple of the preceding token we'll take that too. So in our example, we will match on anything that has an e and zero or many ls.

/el*/g

The `.`

The dot matches any characters except line breaks. In the example below, we are looking for any character that has a space after it.

/. /g

The `\w`

So you might look at this and think oh god this is why regexes are so complicated, what's the bloody slash for? Well, if we just put in 'w' then it'd search for the 'w' letter as seen above, so this allows us to search just for a word's character. So any alphanumeric or underscore.

Our example matches on any word character then the letter s:

/\ws/g

The `\s`

The \s quantifier is very simple, it just matches on any whitespace character (tabs, spaces, line breaks):

/\s/g

The `\S`

Matches anything that isn't whitespace:

This is true for other quantifiers too, so when they're capitalised it means the opposite. So for \d that matches on digits there is \D that matches on anything that isn't a digit, and \W matches on anything that isn't a word character.

The `|`

The pipe means or, so search for this or that. So if you want to search for some literal text let's say "happy" but we also want to grab all the occurrences of the word "day" then we could just put those either side of a pipe and we'll match on both!

/happy|day/g

The `^`

This symbol denotes the start of the string, or, if the multiline tag is enabled then it denotes the start of the line.

Example without the multiline tag:

/^the/g

Notice how it doesn't grab the "the" before Galaxy as it is not at the start of the string, and also how it doesn't grab the "the" on the second line, because that's also not the start of the string. However, if we enable multiline:

/^the/gm

Then a match is made at the start of both lines.

The `$`

This denotes the end of the string, so with multiline it'd mean the end of the line, in the example below I'm not using multiline:

/Thursday$/g

Notice how it doesn't match on the other Thursday as that's not at the end of the string, if you got rid of the $ then it certainly would match!

Length matching

Specifying a length in regex is pretty easy, all you have to do is choose your desired token and then follow it with some curly braces and pop a number in it. Below means give us any word characters that are 8 in length:

/\w{8}/g

You can also specify a min and max range:

/\w{4,6}/g

So any word character that is at least 4 characters long and at most 6.

Character sets

Character sets allow you to plonk stuff in square brackets which basically says match on anything that is within these square brackets. So the following means match any lowercase vowels:

/[aeiou]/g

And this means match any vowels that are followed by the letter r:

/[aeiou]r/g

You can also add ranges in character sets, the following means match on any lowercase characters in the alphabet:

/[a-z]/g

We want to grab the capital letters too, let's add that range as well.

/[a-zA-Z]/g

Another really common range you might see in regexes is [0-9]

Groups

Putting parentheses around part of your regex allows you to group it. This basically means that you can apply a quantifier to the entire group rather than just the preceding token.
The following means to find words that contain "the" with an upper or lowercase t.

/(t|T)he/g

Or the following example, which is looking for the letter p twice in the group and then an e after, but then notice the question mark after the group which denotes the preceding token is optional, so everything within the group is optional. Meaning e is chosen in cases where there's no preceding pp.

/(pp)?e/g

Referencing Groups

In some scenarios, you may want to split your regex up into groups so that you can later reference them individually. Let's take the following example:

/(\d)\. (.+)/g

This regex, first of all, looks for a number which is our first group, then a . (notice we had to escape the . else it would match on any character as shown previously). The second group (.+) is looking for any character except line breaks 1 or more.

Using the replace tools on https://regexr.com/ you can easily reference your groups. To reference the first group type in $1:

And then to reference the second group type in $2

Non-capturing groups

Let's say you want to capture the name of the book but don't really care about the number. So when you reference the group by using $1 it'll just return you the name. To do this we can create non-capturing groups, so within your brackets you can just plonk a ?: at the start to say, I don't want to include this in the result.

/(?:\d)\. (.+)/g

It looks the same right? But not when outputting the groups:

Notice how $2 is now black and is treated as though you want to append $2 as a string on the end because it's not defined.

Lookaheads/ lookbehinds

Okay, so you've learned pretty much everything you'll need to know about regex in 95% of scenarios, let's learn about lookaheads and lookbehinds.

Positive Lookbehind `?<=`

Matches a group before an expression without including it in the result.
Carrying on from the previous example let's take the same input and use positive lookbehind to find all occurrences of the letter h that are preceded by the letter t.

/(?<=t)h/g

So positive lookbehind is great for looking for something that precedes a pattern but you don't really care about having that pattern in the result.

Negative Lookbehind `?<!`

Specifies a group that cannot match before the main expression, so this is basically the inverse of positive lookbehind. All we do is swap the = for a !
Let's do that for the example we used in positive lookbehind:

/(?<!t)h/g

So this finds all occurrences of the letter h that are not preceded by the letter t.

Positive Lookahead `?=`

Matches a group after an expression without including it in the result. So exactly the same as positive lookbehind but from the other end of the string.
In the example below I'm looking for any character that has an a following it:

/.(?=a)/g

Negative Lookahead

Is just the inverse of positive lookahead. Specifies a group that cannot match after the main expression.
So the following looks for any character that is not followed by the letter a:

/.(?!a)/g

Let's tackle a problem together

A real common regex problem is phone numbers. Copy the following text into RegExr.

L. Garrigan: 248-555-1234  
J. Bezos: 232 123 2312  
E. Musk: (313) 555-1234  
B. Gates: (810)555-1234

Goal: get the numbers for each person and output in the format xxx-xxx-xxxx

Let's pick the problem apart. Let's search for numbers that are in the correct format, so L.Garrigan's number is in the correct format, let's grab that.

/\d{3}-\d{3}-\d{4}/g

So we're looking for 3 digits followed by a - then another 3 digits followed by a - then 4 digits

Next let's try grab the phone number with spaces rather than dashes.

/\d{3}-?\s?\d{3}-?\s?\d{4}/g

So I've made the - optional and also added an optional space denoted by \s?

I'm pretty sure this can be improved though using character sets rather than two optionals:

/\d{3}[- ]\d{3}[- ]\d{4}/g

I decided to go for [- ] which means match either - or a space, I chose the space instead because \s also matches on tabs and line breaks which I don't need.
Let's go for the third row now with the first numbers wrapped in brackets:

/\(?\d{3}\)?[-\s]\d{3}[- ]\d{4}/g

I've just added an optional bracket ( at the start - notice it's escaped else it'd think we were creating a group and then an optional closing bracket )? after the first 3 digits.

Next, let's go for Gates, who helpfully decided to not put a space after his parenthesis.

/\(?\d{3}\)?[-\s]?\d{3}[- ]\d{4}/g

So I just make the first character set optional which allows us to grab those.

We need to group these so we can output all the information in the desired format. So I'm going to group the first 3 numbers, then the second 3, then the last 4.
So it is just a case of wrapping parenthesis around the digit captures:

/\(?(\d{3})\)?[-\s]?(\d{3})[- ](\d{4})/g

And then output should look like the following:

Wonderful, all in that lovely format we wanted.
Note there's so many edge cases here, I'd recommend checking out this article which covers the problem in more detail.

Tackle some problems!

The only real way to get decent at anything is by practicing, so to really solidify what you've learnt in this blog have a crack at some problems on here it's a really good website that'll take you through some regex problems dependent upon your ability. It takes into consideration the quantifiers you know and don't know and designs tests accordingly.

I hope you've enjoyed this blog, be sure to check out my personal blogging site at codeheir.com for some extra free content!

DEV Community: Luke Garrigan

My favourite Kotlin features

Clean syntax

Not so nullable types

Extension functions

Convert to Kotlin

Conclusion

A Completely FREE planning poker app 💸 – Speed up your planning process!

How it works

Conclusion

Top 5 books EVERY programmer MUST read! 📚

Top 5 books EVERY programmer MUST read!

5 – The Clean Coder

4 – The Complete Software Developer’s Career Guide

3 – Cracking the Coding Interview

2 – Head First Design Patterns

1 – Clean Code

Conclusion

The Game of Life

Rules

Implementing

Conclusion

What is BFS? (Breadth-first Search)

Introduction

Uninformed Search

Completeness and optimality

Breadth-First Search

Implementation

The algorithm

Testing our algorithm

8 TILE

15 TILE

Informed search

What is Simulated Annealing?

What Is Simulated Annealing?

Hill climbing

The algorithm

The temperature

Let’s put it to the test

Conclusion

How To Code Snake 🐍

Let’s get started coding snake!

Making a grid for the snake to live

Creating the Snake

SNAKE.JS

SKETCH.JS

Adding key pressed handlers

Adding food for the snake

FOOD.JS

SNAKE.JS

Adding hit detection

Losing the grid

What's next?

Create Fake Data Easily Using JavaScript

What is Faker.js

Generating User Data

Using a seed

Summary

Fast prototyping without worrying about the backend

POST

PUT

GET entity

GET resource

DELETE

Neural Network Learns to Drive

Starting simple

Flappy bird

Generation 1

Generation 20

Generation 30

Self-driving car

Inputs

Generation 0

Generation 2

Can it race another track?

Exporting the model

Conclusion

Genetic Algorithms In JavaScript

What are genetic algorithms?

My first genetic algorithm

The `+`

The `?`

The `*`

The `.`

The `\w`

The `\s`

The `\S`

The `|`

The `^`

The `$`

Positive Lookbehind `?<=`

Negative Lookbehind `?<!`

Positive Lookahead `?=`