Recursive Reduce in JavaScript and Clojure

Another fun kata:

Given an array of arbitrarily nested objects, return a flat array with all the objects marked as “good”.

The definition above is quite generic, so I’ll provide examples to show exactly what I mean.

The array in JavaScript looks like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var items = [{
    id: 1,
    good: true
}, {
    id: 2,
    children: [{
        id: 3,
        good: true
    }, {
        id: 4,
        good: true
    }, {
        id: 5,
        children: [{
                id: 6,
                good: true
            }
            ...
        ]
    }, {
        id: 9,
        children: [...]
    }, ...]
}, ...]

We want the IDs of the good ones.

You might have noticed not all objects are “good”. Number 2 for example is not good. So the result in this case should be:

1
[1, 3, 4, 6]

The only thing to notice here is that you know it’s not good because it’s not marked as such. In other words, when some object is “bad”, there’s no good: false nor bad: true that tells you that.

So how do we solve this challenge?

Since there’s an arbitrary nesting depth, we can once again leverage the power and simplicity of recursion.

Solution in JavaScript

I’ve created the function goodOnes(items) that takes the input and returns what we expect. I’m also using Ramda.js, just because I wanted a clean functional solution and I didn’t want to mess around object mutation.

Here it is:

1
2
3
4
5
6
7
8
9
10
11
12
function goodOnes(items) {
    return R.reduce(theGoodOne, [], items);

    function theGoodOne(acc, item) {
        if (item.good) {
            return acc.concat(item.id);
        } else if (item.children && item.children.length > 0) {
            return R.reduce(theGoodOne, acc, item.children);
        }
        return acc;
    }
}

As a side note, you don’t really have to use Ramda.js. Array.prototype.reduce does the same, although in a less elegant way.

Explanation

What this function does is basically just collecting values. The starting point is an empty array, you can see that as the second argument in the first line. theGoodOne is another function (a closure, to be specific) that is implicitly taking two arguments: acc (the accumulator, the empty array) and item (the current item in the loop).

If the item is good, we return a new array with the item’s ID. Otherwise, we return the accumulator. However, if the item happens to have some children, we start over doing the same thing (i.e. looping over its children), also keeping track of the accumulator we already have this time. It might be still empty, but we don’t care yet. We just return it at the very end.

Now, you might have noticed a bug: what happens if the item is good, but also has children? … Yes, that item will be discarded! I did it on purpose by the way. When I made this function, the original array of items never had any good item with children. Only good items, or items with children. The algorithm is reflecting this, so it’s technically not a bug.

If you’re curious about what’s the original intent behind this function, it is to collect values from an infinitely nestable architecture of UI components. There are text components, number components, datepickers etc… those are all part of a category called fields. There are also wrappers, that could be for example a fieldset or a grid. Wrappers can contain fields, but also other wrappers.

So what if you have such data structure with so many components and all you need is just an array of fields? Simple, just reduce recursively on it! ;)

More in general, you can use the recursive reduce whenever you have a nested data structure (such as an array of arrays) and you want to get something out of it.

Solution in Clojure

This recursive solution follows the same logic as the JavaScript one, but somehow it feels superior. It could probably be rewritten in a more elegant way I guess, but I’m not very experienced with Clojure so here we go:

1
2
3
4
5
6
7
8
9
(defn good-one [acc item]
  (if (item :good)
    (conj acc (item :id))
    (if (seq (item :children))
      (reduce good-one acc (item :children))
      acc)))

(defn good-ones [collection]
  (reduce good-one [] collection))

Demo & Download

Everything is on GitHub if you want to fiddle around – just follow the instructions to get the demos up and running on your computer.

Blending together two lists in Elm and Swift

Here’s a fun kata:

Create a blend function that, given two lists of the same length, returns a new list with each element alternated. E.g.:

blend [1, 2, 3] [4, 5, 6]
=> [1, 4, 2, 5, 3, 6]

As with all challenges, it can be solved in many different ways. However this particular one is easily solvable with functional programming techniques such as recursion.

You can try implementing it on your own first or just look straight at the solutions below.

Solution in Elm

The one below is probably the most straightforward solution:

1
2
3
4
5
blend : List a -> List a -> List a
blend xs ys =
    case xs of
        x :: xs' -> x :: blend ys xs'
        _ -> []

Notice how I exchanged the arguments in the recursion call. That did the trick!

Let’s try it in the REPL – I added slashes so you can copy-paste the function:

1
2
3
4
5
6
7
8
9
10
11
$ elm-repl

> blend xs ys = \
    case xs of \
        x :: xs' -> x :: blend ys xs' \
        _ -> []

<function> : List a -> List a -> List a

> blend [0,0,0] [1,1,1]
[0,1,0,1,0,1] : List number

Solution in Swift

We can achieve the same in Swift by using an extension that splits up an Array into head and tail (credits to Chris Eidhof):

1
2
3
4
5
extension Array {
    var match : (head: T, tail: [T])? {
      return (count > 0) ? (self[0],Array(self[1..<count])) : nil
    }
}

And here’s the solution:

1
2
3
4
5
6
7
func blend(firstArray: Array<AnyObject>, secondArray: Array<AnyObject>) -> Array<AnyObject> {
    if let (head, tail) = firstArray.match {
        return [head] + blend(secondArray, secondArray: tail)
    } else {
        return []
    }
}

If you know of a better way, please let me know! Also feel free to leave a comment with any other alternative solution, even in other languages.

How to get the AST of an Elixir program

Getting the AST (Abstract Syntax Tree) representation of an Elixir source is pretty simple.

Let’s say we want to get the AST of this file:

lib/hello.ex
1
2
3
4
5
6
7
defmodule Hello do

  def hi(name) do
    IO.puts "Hello " <> name
  end

end

We can do it right away from iex:

1
2
3
4
5
6
7
8
9
10
11
12
13
$ iex
Erlang/OTP 18 [erts-7.0] [source] [64-bit] [smp:8:8] [async-threads:10] [kernel-poll:false]

Interactive Elixir (1.0.5) - press Ctrl+C to exit (type h() ENTER for help)
iex(1)> {:ok, ast} = Code.string_to_quoted(File.read!("lib/hello.ex"))
{:ok,
 {:defmodule, [line: 1],
  [{:__aliases__, [counter: 0, line: 1], [:Hello]},
   [do: {:def, [line: 3],
     [{:hi, [line: 3], [{:name, [line: 3], nil}]},
      [do: {{:., [line: 4],
         [{:__aliases__, [counter: 0, line: 4], [:IO]}, :puts]}, [line: 4],
        [{:<>, [line: 4], ["Hello ", {:name, [line: 4], nil}]}]}]]}]]}}

In our case, the ast variable will contain the full AST of the source code.

In case you want to get the AST of a single line, it’s even simpler:

1
2
3
4
5
6
7
8
9
10
iex(1)> name = "John"
"John"

iex(2)> IO.puts "Hello " <> name
Hello John
:ok

iex(3)> ast = quote do: IO.puts "Hello " <> name
{{:., [], [{:__aliases__, [alias: false], [:IO]}, :puts]}, [],
 [{:<>, [context: Elixir, import: Kernel], ["Hello ", {:name, [], Elixir}]}]}

For more context, I recommend reading the introduction to meta-programming in Elixir on Elixir’s official site.

In case you’re interested in parsing Elixir, Tokenizing and parsing in Elixir with yecc and leex by Andrea Leopardi is a very recommended reading.

Have fun with Elixir!

How To Get Environment Variables in the Browser

Preface: Why?

Environment variables are very useful for configuring your app depending on the environment, without having to hardcode any value in the source.

At my current company we are building a microservice infrastructure, where the frontend and the backend are completely decoupled applications. We also use Docker to manage these microservices and link them together. Turns out that storing the configuration in the environment—as opposed to storing it in the database or in the code itself—is quite valuable, as described also in the twelve-factor methodology.

Advantages:

  • Language and OS agnostic;
  • Easy to change between deploys without changing any code;
  • Impossible to accidentally check in source control.

How?

A web page doesn’t have access to OS variables, so you can’t normally use them.

The solution is pretty simple: you just need to generate a file that contains them.

For such a trivial task you could be tempted to use your language of choice, e.g. in JavaScript (Node.js) you have access to process.env.SOME_VAR. In Python you would probably do os.getenv('SOME_VAR') and in Ruby you’d use ENV['SOME_VAR']—but what about some old-school shell scripting? The script could be as simple as:

bin/env.sh
1
2
3
4
echo "env = {"
echo "  USER: '$USER',"
echo "  HOSTNAME: '$HOSTNAME'"
echo "}"

That, when executed, will become:

env.js
1
2
3
4
env = {
  USER: 'simone',
  HOSTNAME: 'ubuntu'
}

And the script to execute is:

1
$ ./bin/env.sh > env.js

Pretty straightforward, isn’t it?

Test it:

<!DOCTYPE html>
<html>
<head>
  ...
</head>
<body>
  <script src="env.js"></script>
  <script>
    console.log(env.USER +'@'+ env.HOSTNAME); // "[email protected]"
  </script>
</body>
</html>

One downside to this approach is that you have to “make a build” every time you change the variables. If you know any workarounds or better solutions, please let me know!

Source and download

Find the source code on GitHub. Download the zip file here.

Have fun!

Making a game from scratch in HTML5

“Pong is one of the earliest arcade video games; it is a tennis sports game featuring simple two-dimensional graphics.” - Wikipedia

Have you ever dreamed of building a game in JavaScript? I did, and I also managed to make my first one. Of course I also wrote some tips and gotchas to help you complete this nice challenge.

How to make Pong in HTML5 canvas

Pong, at it’s core, is an extremely simple game. That’s why it’s a good one to begin with if you have just started learning game design basics. Of course you could start with many other games, but if you are looking for something relatively simple to build, Pong really is one of the simplest games ever made.

AFAIK, there are at least two ways of doing it: I personally call them the “simple way” and the “hard way”. I did both, but first let’s explore the simple one.

Project structure

I aimed to make it as simple as possible, so I just created one HTML file that is referencing few JavaScript files. You may ask, why not a whole single file? Because it’s usually preferable to have many little files rather than one massive plate of spaghetti code. So here’s served the project’s structure:

1
2
3
4
5
6
7
8
index.html
canvas.js
game.js
keyboard.js
main.js
render.js
reset.js
update.js

index.html is our single entry point to the game.

canvas.js contains the code for initializing the canvas DOM object and the 2D context.

game.js contains the game objects. This file will be executed only once at the beginning, when the game loads.

keyboard.js has the keyboard bindings.

main.js is perhaps the most important file, because it contains the main game loop.

render.js does… the rendering. (you don’t say?)

reset.js is for resetting the game to the initial state, called every time a player wins.

update.js contains 90% of the game logic, and obviously is for updating the game state (before rendering).

The main loop

The main loop is at the core of our game. Maybe it’s hard to believe, but virtually every single videogame in the world lives and dies within a loop.

Implementing a game loop is a lot simpler than you think, but it’s not the focus of this tutorial. The resource I highly recommend for getting started is How to make a simple HTML5 Canvas game, by Matt Hackett. All my work is actually based on his tutorial. Read it, and you’ll get a basic understanding of the fundamentals of game development.

We want to focus on the game logic now, so for the time being let’s pretend our game loop looks like this:

1
2
3
4
while (true) {
  update(); // update game objects
  render(); // render game objects
}

Got it? :-)

Ball movement

How do we make the ball moving across the screen? In JavaScript, we can define objects with properties. The essential properties of our ball object are position and speed. The position represents the coordinates where the object is in the canvas space. Example:

1
2
3
4
5
6
var ball = {
  x: 0,
  y: 0,
  speedX: 0,
  speedY: 0
}

In order to make it move, we should change its position, and we can do it through the speed. This is the heart of our game:

1
2
3
4
5
if (isGameStarted) {
  // Ball movement
  ball.x += ball.speedX * modifier;
  ball.y += ball.speedY * modifier;
}

As you can imagine, isGameStarted is just a boolean flag. But what’s modifier? Well, it’s the delta time of our game loop. Put simply, the delta time is the time elapsed between a frame and another. This is very useful because we can use it to calculate how fast the ball should move. Without it, the game would just lag all the time.

Ball bounce

The game logic is mainly about the ball: it should be able to bounce away from the paddles. How can you implement that? It’s pretty simple - have a look at the code below.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
  // Ball is out of the left boundary
  if (ball.x <= 0) {
    // Player 2 wins!
    p2.score++;
    reset(); // reset the game to the initial state
  }

  // Ball is out of the right boundary
  if (ball.x >= canvas.width - ball.size) {
    // Player 1 wins!
    p1.score++;
    reset();
  }

  // Ball is colliding with the top
  if (ball.y <= 0) {
    ball.speedY = Math.abs(ball.speedY);
  }

  // Ball is colliding with the bottom
  if (ball.y + ball.size >= canvas.height) {
    ball.speedY = Math.abs(ball.speedY) * -1; // inverted
  }

Can you see what’s going on in the code? Basically, if the ball goes beyond the canvas’ left or right boundaries, all we do is increment the score and reset the game. If the ball touches the top or the bottom instead, we invert its speed on the Y axis. If you think about it, it’s all you need to make something reflect over a surface. So, in other words, if the speed is negative we make it positive, and viceversa.

Collision detection

What should happen when the ball touches one of the paddles? Fundamentally the same thing explained above: it should bounce away, reflecting on the paddle’s surface (and to do this we invert the Y speed). But how do we actually check if they are colliding?

The most common kind of collision detection is called AABB - Axis-Aligned Bounding Boxes. You can find plenty of resources around the Web explaining how this technique works, so I won’t talk about it (have a quick search for “AABB collision detection”, or just keep reading). As Linus Torvalds once said,

“Talk is cheap. Show me the code.”

Here we go:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
if (
  ball.x <= (p1.x + p1.width)
  && p1.x <= (ball.x + ball.size)
  && ball.y <= (p1.y + p1.height)
  && p1.y <= (ball.y + ball.size)
) {
  // Ball is colliding with the left paddle
  // Ensure the speed on the X axis is positive
  ball.speedX = Math.abs(ball.speedX);

  // Give the ball a bit of randomness by 
  // increasing/decreasing its speed on the Y axis
  ball.speedY = randomize();
}

The logic for the right paddle is exactly the same, but the speed on the X axis should be negative instead. In my case I also added a randomize() function, so the game will be more interesting - you don’t have to implement it this way, but a bit of randomness never hurts in gaming!

1
2
3
4
5
6
function randomize() {
  // Random float between 0 and 999.9
  var _rand = Math.random() * 1000;
  // positive or negative?
  return Math.random() > 0.5 ? _rand : _rand * -1;
}

Paddle movement

We move the paddles with the keyboard. Keyboard controls can be handled simply by keeping track of which key is currently being pressed (watch for the keydown event). We can use a simple JavaScript object for that (or an array if you prefer):

1
2
3
4
5
6
7
8
9
10
// Handle keyboard controls
var keysDown = {};

addEventListener("keydown", function (e) {
  keysDown[e.keyCode] = true;
}, false);

addEventListener("keyup", function (e) {
  delete keysDown[e.keyCode];
}, false);

The keyup and keydown events are the only two we need for handling the whole keyboard. So on keydown we add the key; on keyup we remove it. Simple.

Of course we are going to need JavaScript objects for the paddles as well. In my game I called them p1 and p2, which can be interpreted as players too.

Here’s the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// Update game objects
var update = function (modifier) {
  if (87 in keysDown) { // P1 holding up (key: w)
    p1.y -= p1.speed * modifier;
  }

  if (83 in keysDown) { // P1 holding down (key: s)
    p1.y += p1.speed * modifier;
  }

  if (38 in keysDown) { // P2 holding up (key: arrow up)
    p2.y -= p2.speed * modifier;
  }

  if (40 in keysDown) { // P2 holding down (key: arrow down)
    p2.y += p2.speed * modifier;
  }
}

Rendering the objects in the canvas

Here’s the render() function, in all its glory:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
var render = function () {

  ctx.fillStyle = "#0F0"; // green

  // P1
  ctx.fillRect(p1.x, p1.y, p1.width, p1.height);

  // P2
  ctx.fillRect(p2.x, p2.y, p2.width, p2.height);

  // ball
  ctx.fillRect(ball.x, ball.y, ball.size, ball.size);

  // Text options
  ctx.fillStyle = "rgb(250, 250, 250)";
  ctx.font = "18px Helvetica";
  ctx.textAlign = "left";
  ctx.textBaseline = "top";

  // P1 Score
  ctx.fillText(p1.score, 32, 32);

  // P2 Score
  ctx.fillText(p2.score, canvas.width - 32, 32);
};

It’s probably worth mentioning that you can use JSON.stringify() to debug your objects directly in the canvas, e.g.:

1
2
// Debugging the ball object
ctx.fillText("ball: " + JSON.stringify(ball), 0, 0);

However, I don’t recommend it. Just use whatever your browser is offering! If you are a web developer you surely know that there’s a built-in JavaScript console for debugging in your browser (if you don’t, search for developer tools).

Resetting the game

We need to reset the game every time a player scores. The logic is very simple, we just need to provide default values for our objects. Example below.

1
2
3
4
5
6
7
8
9
10
11
// Reset the game
var reset = function () {

  isGameStarted = false;

  ball.x = (canvas.width - ball.size) / 2;
  ball.y = (canvas.height - ball.size) / 2;

  ball.speedX = randomize(); // randomly start going left or right
  ball.speedY = 0;
}

This is the main logic of Pong. However, it’s not perfect, and it could be improved a lot in several ways… for example by implementing physics rules (or by using a physics engine, that has already done the job for us). We have just simulated the reflection of a ball on a surface, but it’s not realistic at all - let’s make it better.

The “hard way”

In a proper Pong game, you can usually control where the ball goes. It could have a steeper or shallower angle of reflection, based on where the ball landed. Should it land on one of the edges of the paddle, the collision should be inelastic. In case it lands exactly on the middle of the paddle, the collision should be totally elastic.

In order to implement physics rules in a game, you should have an understanding of basic vector math, trigonometry and - of course - physics. But don’t fear, you don’t have to know everything: just the basics. I personally didn’t know much about physics, but I learned it by reading about it.

Here are some useful resources on the Web:

Let’s explore together the potential of 2D vectors.

Using 2D Vectors

The main thing you’ll have to understand is how vectors are used in game development. As an example, let’s go back to our ball object and modify it to use vectors. It will look like this:

1
2
3
4
var ball = {
  position: new Vector({ x: 0 , y: 0 }),
  velocity: new Vector({ x: 0 , y: 0 })
}

Four values at the price of two attributes! And this is a lot better now, not only because we are using less attributes, but because we can use vector math. Believe me, vectors simplify your game a lot.

You may have noticed that I didn’t use speed, but I used velocity instead. The reason is that speed is a scalar quantity, while velocity is a vector quantity. Put simply, speed is an information that’s contained in velocity! You may want to read about it, albeit not directly related to programming.

A proper ball reflection

We can implement proper reflection (not a fake one) by using this JavaScript function:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var ball = {
  // the velocity vector
  velocity: new Vector(),

  /*
  * The formula:
  * 
  *  R = 2(V · N) * N - V
  *
  * V: velocity vector
  * N: a normalized vector of the plane surface (e.g. paddle or wall)
  * R: the reflected velocity vector
  */
  deflect: function (N) {
    var dot = this.velocity.dot(N);
    var v1 = N.multiplyScalar(2 * dot);
    this.velocity = v1.subSelf(this.velocity);
  }
}

This is how I’ve implemented it by using a vector library I found on the Web (find the source code on GitHub). Given a paddle’s normal, it will reflect any vector, but you have to make sure the paddle’s normal is a unit vector (in other words, it’s normalized).

Conclusion

I hope you enjoyed this article. Who’s following my blog since the beginning will probably remember my first blog post. It was more than 2 years ago, and at that time I was really excited by the idea to build a game with JavaScript. I finally did it, and it has been fun indeed! However, I learned a big lesson: although it was fun, it wasn’t really worth reinventing the wheel. So, if you got through all this tutorial, first of all congratulations! Secondly, consider using a game engine. Thirdly, maybe consider not using JavaScript… just use whatever you feel comfortable with. For instance, if you like the Ruby language (I do!) you could use Opal, a Ruby to JavaScript compiler.

Demo and source code

You can play the game here.

The full source code is on GitHub so you can clone it, fork it and even make your own from scratch, if you feel like it’s worth your time. If you are interested in the simple way, checkout the v1.0 release. The hard way is in the master branch.

As always, if you have any thoughts or questions, feel free to leave a comment below.

Have fun!