Forem: Lars Wächter

Solving Peg Solitaire using Backtracking

Lars Wächter — Tue, 10 Jan 2023 01:43:24 +0000

This post was originally published on my blog.

A few days ago I saw a post on Reddit where someone asked what an algorithm for solving Peg Solitaire might look like. If you read the comments, you'll notice that backtracking is the most common answer given. I really liked the idea and was curious to solve this puzzle. So in this post we'll solve Peg Solitaire with the help of backtracking.

There's also an example repository on GitHub.

But first things first. What is Peg Solitaire? Peg Solitaire is a single player board game where the player has to move pegs (pins) and remove them on a board in order to win. The rules are simple: each turn you can pick one peg, jump over a neighboring one (horizontal or vertical) and remove the one you just jumped over. The game is won when there's 1 peg left in the center of the board and it's lost when you cannot jump anymore or the last peg is not in the center. You're not allowed to jump over multiple pegs or multiple empty cells.

An example Peg Solitaire board (source)

Implementation

For the implementation we'll use Kotlin, but of course you can use any other language. Before we can implement the algorithm, we have to write some game logic first. Let's start with the board representation.

val board: Array<IntArray> = arrayOf(
    intArrayOf(-1, -1, 1, 1, 1, -1, -1),
    intArrayOf(-1, -1, 1, 1, 1, -1, -1),
    intArrayOf(1, 1, 1, 1, 1, 1, 1),
    intArrayOf(1, 1, 1, 0, 1, 1, 1),
    intArrayOf(1, 1, 1, 1, 1, 1, 1),
    intArrayOf(-1, -1, 1, 1, 1, -1, -1),
    intArrayOf(-1, -1, 1, 1, 1, -1, -1),
)

The board is encoded as matrix (2D array) including the following values:

-1 => No cell (edge)
0 => Cell without pin (hole)
1 => Cell with pin

The printed board looks like this:

 ---------------
|     X X X     |
|     X X X     |
| X X X X X X X |          -1 => " "
| X X X o X X X |           0 => "o"
| X X X X X X X |           1 => "X"
|     X X X     |
|     X X X     |
 ---------------

How do we check if the player has won? As I just mentioned above, the game is won when the last pin is in the center of the board. The board center is at position board[3][3]. Quite simple:

fun hasWon(): Boolean = this.remainingPegs == 1 && board[3][3] == 1

Next, we create a class that represents a single move. It has two attributes: from and to. Both of them include a x and y coordinate that represents the position on our board. For example Move(Pair(2,3), Pair(2,5)) means that we want to move the pin at y=2|x=3 to y=2|x=5. The first value indicates the row (y) and the second one the column (x). In this case, the pin at y=2|x=4 gets removed. The method getPegToRemove() returns the position of the pin to remove.

class Move(val from: Pair<Int, Int>, val to: Pair<Int, Int>) {
    fun getPegToRemove(): Pair<Int, Int> = Pair((from.first + to.first) / 2, (from.second + to.second) / 2)

    override fun toString(): String {
        return "(${from.first}|${from.second}) => (${to.first}|${to.second})"
    }
}

Now that we have the representation of the game board and moves, we can write a method that returns us all possible moves for a given board position. Here, we again iterate over each cell with a pin and check for each direction (horizontal / vertical) if the direct adjacent cell is not empty (1) and that this one's neighbor is empty (0). Of course, we must take into account the edges of the game board.

fun getPossibleMoves(): List<Move> {
    val moves = mutableListOf<Move>()

    for ((rowIdx, row) in board.withIndex()) {
        for ((cellIdx, cell) in row.withIndex()) {
            if (cell != 1) continue

            val from = Pair(rowIdx, cellIdx)

            // Left => Right
            if (cellIdx <= 4 && row[cellIdx + 1] == 1 && row[cellIdx + 2] == 0)
                moves.add(Move(from, Pair(rowIdx, cellIdx + 2)))

            // Right => Left
            if (cellIdx >= 2 && row[cellIdx - 1] == 1 && row[cellIdx - 2] == 0)
                moves.add(Move(from, Pair(rowIdx, cellIdx - 2)))

            // Up => Down
            if (rowIdx <= 4 && board[rowIdx + 1][cellIdx] == 1 && board[rowIdx + 2][cellIdx] == 0)
                moves.add(Move(from, Pair(rowIdx + 2, cellIdx)))

            // Down => Up
            if (rowIdx >= 2 && board[rowIdx - 1][cellIdx] == 1 && board[rowIdx - 2][cellIdx] == 0)
                moves.add(Move(from, Pair(rowIdx - 2, cellIdx)))
        }
    }

    return moves
}

The next step is to implement a method for playing a given move:

fun move(move: Move): Solitaire {
    val newBoard = board.map { it.clone() }.toTypedArray()

    val toRemove = move.getPegToRemove()
    newBoard[move.from.first][move.from.second] = 0
    newBoard[toRemove.first][toRemove.second] = 0
    newBoard[move.to.first][move.to.second] = 1

    return Solitaire(newBoard, remainingPegs - 1)
}

This method accepts a Move and returns a new game instance including the new board and the number of remainingPegs - 1. Look how the board is updated using the from and to attributes of move. The variable toRemove contains the position of the pin we just jumped over and want to remove.

Last but not least the most important part: the backtracking algorithm. Here, we create a game tree using depth-first-search. Each node in our tree represents a board position. From the root node (starting position) on, we iterate over all possible moves and search recursively for the one that results in a win. If that move is found, we cancel the search, go back up the child nodes to the root node and return the move of each child node that lead to this winning move.

fun dfs(
    game: Solitaire = this,
): Pair<Move?, Boolean> {
    if (game.hasWon()) return Pair(null, true)

    // Read from memory
    val hash = game.board.contentDeepHashCode()
    if (memory.containsKey(hash))
        return memory[hash]!!

    val moves = game.getPossibleMoves()
    if (moves.isEmpty()) return Pair(null, false)

    // Play each move and call recursively. Pick first solution that was found.
    for (move in moves) {
        val newGame = game.move(move)
        val hasWon = dfs(newGame).second

        // Return move that lead to win & store in memory
        if (hasWon) {
            memory[hash] = Pair(move, true)
            return memory[hash]!!
        }
    }

    // Case when no solution was found.
    return Pair(moves[0], false)
}

The return value of this method is of type Pair<Move?, Boolean> containing the next move to play and a boolean whether the game is solvable or not. Moreover, when we have found a winning move, we'll store it in a memory to speed up subsequent searches in the game tree.

You should notice that the algorithm always returns the same solution. That's because we cancel the search as soon as the first solution was found. If you want to have more randomness, you have to continue the search at this point for more winning moves and pick a random one of them. You can also shuffle the list of possible moves. Watch out: both will make the algorithm much slower!

Performance

When simulating a complete game, you'll see that the algorithm solves the puzzle surprisingly fast. On my laptop (Huawei Matebook 14) a complete simulation runs in ~80ms. Without the memory it would take ~500ms, what is still very good.

var game = Solitaire()

val timeMS = measureTimeMillis {
    var counter = 0
    while (!game.hasWon()) {
        counter++
        val move: Pair<Move?, Boolean> = game.dfs()
        game = game.move(move.first!!)
    }
}

println("Done in $timeMS ms")

Nevertheless, you can still improve the performance by using symmetries for example. This article might be a help for you.

Check out the GitHub repo for an example usage and more code details.

Writing & organizing Node.js API Tests the right way

Lars Wächter — Tue, 22 Nov 2022 14:20:22 +0000

This post was originally published on my blog.

Testing the code you write is an important step in the process of software engineering. It ensures that your software works as expected and reduces the risk of shipping bugs and vulnerabilities to production. Automated tests in particular play an important role when it comes to testing frequently and consistently. Continous integration makes them even more powerful.

In this blog post I'll show you an architecture for testing Node.js REST APIs that use a database in the background. There are some things you should consider in this scenario that we'll talk about. You'll see how to separate and organize your application's components in a way that you can test them independently. Therefore, we'll use two different approaches. On the one hand we setup a test environment in which we run ours tests against a test database. On the other hand we mock the database layer using mock functions so that we can run them in an environment in which we have no access to a database.

We'll start by writing unit tests for testing single components of our application. In the next step we combine those components and test them using integration tests. Last but not least, we setup a CI/CD pipeline using GitHub actions and run the tests on each push that is made.

Note that this is not a guide on how testing in general works. There are thousands of articles about frameworks like Jest, Mocha, Supertest and so on.
This is more a guide on how to prepare your Node application and test environment in a way that you can write tests effortlessly and efficiently with or without a database connection. There's also an example repo on GitHub. You should definitely check it out.

Disclamer: I know there really is no right or wrong when it comes to the architecture. The following is my prefered one.

Let's start with some of the tools we'll use. You should know most of them:

Language: Typescript
Server: Express
Database: Postgres
Testing: Jest & Supertest & Chai
CI/CD: GitHub Actions
Containerization: Docker

One benefit of this architecture is that you can use it with other databases than Postgres too, like MySQL for example. In this architecture we don't use any kind of ORM. Moreover, you can replace Jest with Mocha if that is your desired testing framework.

Application Architecture

The architecture of our application looks roughly like this:

node-api
├── api
│   ├── components
│   │   ├── user
|   |   │   ├── tests               // Tests for each component
|   |   |   │   ├── http.spec.ts
|   |   |   │   ├── mock.spec.ts
|   |   │   |   └── repo.spec.ts
|   |   │   ├── controller.ts
|   |   │   ├── dto.ts
|   |   │   ├── repository.ts
|   |   │   └── routes.ts
│   └── server.ts
├── factories                       // Factories to setup tests
|   ├── helper.ts
|   ├── abs.factory.ts
|   ├── http.factory.ts
|   └── repo.factory.ts
└── app.ts

Note: The example repo contains some more code.

Each component consists of the following four files:

controller.ts: HTTP Handler
dto.ts: Data Transfer Object (more)
repository.ts: Database Layer
routes.ts: HTTP Routing

The tests directory includes the tests of the according component. If you want to read more about this architecture, checkout this article of mine.

Config

We'll start by creating an .env.test file that contains the secret environment variables for testing. The npm Postgres package uses them automatically when establishing a new database connection. All we have to do is to make sure that they are loaded using dotenv.

NODE_PORT=0
NODE_ENV=test

PGHOST=localhost
PGUSER=root
PGPASSWORD=mypassword
PGDATABASE=nodejs_test
PGPORT=5432

Setting NODE_PORT=0 lets Node choose the first randomly available port that it finds. This can be useful if you run multiple instances of a HTTP server during testing. You can also set a fixed value other than 0 here. Using PGDATABASE we provide the name of our test database.

Next, we setup Jest. The config in jest.config.js looks as follows:

module.exports = {
  preset: "ts-jest",
  testEnvironment: "node",
  roots: ["src"],
  setupFiles: ["<rootDir>/setup-jest.js"],
}

And setup-jest.js like this:

require("dotenv").config({
  path: ".env.test",
})

This snippet ensures that the appropriate environment variables are loaded from the provided .env file before running the tests.

Testing with database

Let's start with the assumption that we have a test database that we can use. This might be one in a GitHub Actions CI/CD pipeline for example. Later on I'll show you how to test your application without a database connection.

3 rules

At the beginning I said that there are some important things we want to consider that make life much easier when testing Node APIs:

Separate the database layer
Outsource the database connection initialization
Outsource the HTTP server initialization

What do I mean by that?

Separate the database layer

You should have your own layer, separated from your business logic, that takes care of the communication with the database. In the example Git repo you can find this layer in a component's repository.ts file. This allows us to easily mock a layer's methods when we have no database available for testing.

Moreover, it's easier to replace your database system with another one.

export class UserRepository {
  readAll(): Promise<IUser[]> {
    return new Promise((resolve, reject) => {
      client.query<IUser>("SELECT * FROM users", (err, res) => {
        if (err) {
          Logger.error(err.message)
          reject("Failed to fetch users!")
        } else resolve(res.rows)
      })
    })
  }

Outsource the database connection initialization

You should already know that when writing tests against a database, you do not run them against the production one. Instead, you setup a test database. Otherwise, you run the risk messing up your production data.

Most of the time, your application connects to the database in a startup script, like index.js. After the connection is established, you start the HTTP server. That's what we want to do in our test setup too. This way we can connect to the database and disconnect from it gracefully before and after each test case.

Outsource the HTTP server initialization

It's a good practice, whether you use a database or not, to start the HTTP server from inside your tests. Just as we do for the database connection, we create a new HTTP server before and stop it after each test case.

This might look as follows: (you'll see the concrete implementation later on)

describe("Component Test", () => {
  beforeEach(() => {
    // Connect to db pool && start Express Server
  });

  afterEach(() => {
    // Release db pool client && stop Express Server
  });

  afterAll(() => {
    // End db pool
  });

In particular the execution order is:

Connect to the database pool
Run the SQL seed (create tables)
Start the Express server
Run the tests
Shutdown the Express server & release db pool client
Repeat step 1 - 5 for each test case and close the pool at the end

Tests

Each component consists of two test files:

repo.spec.ts
http.spec.ts

Both of them make use of so called TestFactories which prepare the test setup. You'll see their implementation in the next chapter.

Note: If you have a look at the example Git repo, you'll see that there are two more: mock.spec.ts and dto.spec.ts. Former one is discussed later on. The latter is not covered in this article.

repo.spec.ts

A repository is an additional abstract layer that is responsible for interacting with the database like reading and inserting new data. That layer is what we test in here. Since a database is required in this case, a new pool client is created to connect to the database using the RepoTestFactory before each test case. And it is released, right after the test case is completed. At the end, when all test cases are finished, the pool connection is closed.

Example on GitHub

describe("User component (REPO)", () => {
  const factory: RepoTestFactory = new RepoTestFactory()
  const dummyUser: IUser = userFactory.build()
  const dummyUserDTO: UserDTO = userDTOFactory.build()

  // Connect to pool
  beforeEach(done => {
    factory.prepareEach(done)
  })

  // Release pool client
  afterEach(() => {
    factory.closeEach()
  })

  // End pool
  afterAll(done => {
    factory.closeAll(done)
  })

  test("create new user", async () => {
    const repo = new UserRepository()
    const user = await repo.create(dummyUserDTO)

    expect(user).to.be.an("object")
    expect(user.id).eq(1)
    expect(user.email).eq(dummyUser.email)
    expect(user.username).eq(dummyUser.username)

    const count = await factory.getTableRowCount("users")
    expect(count).eq(1)
  })
})

http.spec.ts

Here, we test the integration of the user component's routes, controller and repository. Before each test case, a new pool client is created just as we did above. In addition, a new Express server is started using the HttpTestFactory. At the end, both are closed again.

Example on GitHub

ddescribe("User component (HTTP)", () => {
  const factory: HttpTestFactory = new HttpTestFactory()
  const dummyUser: IUser = userFactory.build()
  const dummyUserDTO: UserDTO = userDTOFactory.build()

  // Connect to pool && start Express Server
  beforeEach(done => {
    factory.prepareEach(done)
  })

  // Release pool client && stop Express Server
  afterEach(done => {
    factory.closeEach(done)
  })

  // End pool
  afterAll(done => {
    factory.closeAll(done)
  })

  test("POST /users", async () => {
    const res = await factory.app
      .post("/users")
      .send(dummyUserDTO)
      .expect(201)
      .expect("Content-Type", /json/)

    const user: IUser = res.body
    expect(user).to.be.an("object")
    expect(user.id).eq(dummyUser.id)
    expect(user.email).eq(dummyUser.email)
    expect(user.username).eq(dummyUser.username)

    const count = await factory.getTableRowCount("users")
    expect(count).eq(1)
  })
})

Factories

The test factories are actually the heart of our tests. They are responsible for setting up and preparing the environment for each test case. That includes:

Droping & creating all db tables
Initializing the db connection
Initializing the HTTP server
Closing both of them again

There are four factories in total: AbsTestFactory, RepoTestFactory, HttpTestFactory and MockTestFactory. Each of them has its own Typescript class.

The last one is discussed in the chapter "Testing without database".

AbsTestFactory

The first one AbsTestFactory is an abstract base class that is implemented by the other three. It includes among others a method for connecting to the database pool and one for disconnecting from it.

export abstract class AbsTestFactory implements ITestFactory {
  public poolClient: PoolClient

  abstract prepareEach(cb: (err?: Error) => void): void
  abstract closeEach(cb: (err?: Error) => void): void

  public async getTableRowCount(name: string) {
    const { rows } = await this.poolClient.query(
      `SELECT COUNT(*) FROM ${this.poolClient.escapeIdentifier(name)};`
    )
    return rows.length ? +rows[0].count : 0
  }

  protected connectPool(cb: (err?: Error) => void) {
    pool
      .connect()
      .then(poolClient => {
        this.poolClient = poolClient
        this.poolClient.query(this.seed, cb)
      })
      .catch(cb)
  }

  protected releasePoolClient() {
    this.poolClient.release(true)
  }

  protected endPool(cb: (err?: Error) => void) {
    pool.end(cb)
  }

  private seed = readFileSync(
    join(__dirname, "../../db/scripts/create-tables.sql"),
    {
      encoding: "utf-8",
    }
  )
}

Using the create-tables.sql script, the factory drops and recreates all the tables after the connection is established:

DROP TABLE IF EXISTS users;

CREATE TABLE users (
    id SERIAL PRIMARY KEY,
    email VARCHAR(50) UNIQUE NOT NULL,
    username VARCHAR(30) UNIQUE NOT NULL,
    created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP
);

RepoTestFactory

The RepoTestFactory is used by each component's repository test (repo.spec.ts) that you just saw above. All it does is use the parent class AbsTestFactory to connect to the database.

export class RepoTestFactory extends AbsTestFactory {
  prepareEach(cb: (err?: Error) => void) {
    this.connectPool(cb)
  }

  closeEach() {
    this.releasePoolClient()
  }

  closeAll(cb: (err?: Error) => void) {
    this.endPool(cb)
  }
}

The methods prepareEach, closeEach and closeAll are called for each test case in the Jest beforeEach, afterEach and afterAll lifecycle.

HttpTestFactory

The last one HttpTestFactory is used by each component's HTTP test (http.spec.ts). Just like RepoTestFactory, it uses the parent class for the database connection. Furthermore, it initializes the Express server.

export class HttpTestFactory extends AbsTestFactory {
  private readonly server: Server = new Server()
  private readonly http: HttpServer = createServer(this.server.app)

  get app() {
    return supertest(this.server.app)
  }

  prepareEach(cb: (err?: Error) => void) {
    this.connectPool(err => {
      if (err) return cb(err)
      this.http.listen(process.env.NODE_PORT, cb)
    })
  }

  closeEach(cb: (err?: Error) => void) {
    this.http.close(err => {
      this.releasePoolClient()
      cb(err)
    })
  }

  closeAll(cb: (err?: Error) => void) {
    this.endPool(cb)
  }
}

Helpers

In helper.ts, there are two fishery objects which we can use to create dummy data during the tests.

export const userFactory = Factory.define<IUser>(({ sequence, onCreate }) => {
  onCreate(
    user =>
      new Promise((resolve, reject) => {
        pool.query<IUser>(
          "INSERT INTO users (email, username) VALUES($1, $2) RETURNING *",
          [user.email, user.username],
          (err, res) => {
            if (err) return reject(err)
            resolve(res.rows[0])
          }
        )
      })
  )

  return {
    id: sequence,
    email: "john@doe.com",
    username: "johndoe",
    created_at: new Date(),
  }
})

export const userDTOFactory = Factory.define<UserDTO>(
  () => new UserDTO("john@doe.com", "johndoe")
)

Usage:

// Returns new `IUser` instance
const dummyUser1 = userFactory.build()

// Returns new `IUser` instance & creates db entry
const dummyUser2 = await userFactory.create()

Rewind

Let's jump back to the repo.spec.ts and http.spec.ts test files from above. In both of them we used the factories' prepareEach method before each and its afterEach method after right each test case. The closeAll method is called at the very end of the test file. As you have just seen, depending on the type of factory, we establish the database connection and start the HTTP server if needed.

describe("Component Test", () => {
  beforeEach(done => {
    factory.prepareEach(done)
  })

  afterEach(() => {
    factory.closeEach()
  })

  afterAll(done => {
    factory.closeAll(done)
  })
})

One important thing you should keep in mind is that for each test case that uses the database, the factory drops all the tables and recreates them using the provided SQL script afterwards. This way we have a clean database with empty tables in each test case.

Testing without database

So far we have run our tests against a test database, but what if we have no access to a database? In this case, we need to mock our database layer implementation (repository.ts), which is quite easy if you have separated it from the business logic, as I recommended in rule #1.

With mocks, the layer does not depend on an external data source any more. Instead, we provide a custom implementation for the class and each of its methods. Be aware that this does not affect the behavior of our controller since it does not care about where the data comes from.

Example on GitHub

const dummyUser = userFactory.build()
const dummyUserDTO = userDTOFactory.build()

const mockReadAll = jest.fn().mockResolvedValue([dummyUser])

const mockReadByID = jest
  .fn()
  .mockResolvedValueOnce(dummyUser)
  .mockResolvedValueOnce(dummyUser)
  .mockResolvedValue(undefined)

const mockCreate = jest.fn().mockResolvedValue(dummyUser)

const mockReadByEmailOrUsername = jest
  .fn()
  .mockResolvedValueOnce(undefined)
  .mockResolvedValueOnce(dummyUser)

const mockDelete = jest.fn().mockResolvedValue(true)

jest.mock("../repository", () => ({
  UserRepository: jest.fn().mockImplementation(() => ({
    readAll: mockReadAll,
    readByID: mockReadByID,
    readByEmailOrUsername: mockReadByEmailOrUsername,
    create: mockCreate,
    delete: mockDelete,
  })),
}))

After mocking the database layer, we can write ours tests as usual. Using toHaveBeenCalledTimes() we make sure that our custom method implementation has been called.

describe("User component (MOCK)", () => {
  const factory: MockTestFactory = new MockTestFactory()

  // Start Express Server
  beforeEach(done => {
    factory.prepareEach(done)
  })

  // Stop Express Server
  afterEach(done => {
    factory.closeEach(done)
  })

  test("POST /users", async () => {
    const res = await factory.app
      .post("/users")
      .send(dummyUserDTO)
      .expect(201)
      .expect("Content-Type", /json/)

    const user: IUser = res.body
    cExpect(user).to.be.an("object")
    cExpect(user.id).eq(dummyUser.id)
    cExpect(user.email).eq(dummyUser.email)
    cExpect(user.username).eq(dummyUser.username)

    expect(mockCreate).toHaveBeenCalledTimes(1)
    expect(mockReadByEmailOrUsername).toHaveBeenCalledTimes(1)
  })
})

Note: cExpect is a named import from the "chai" package.

MockTestFactory

Just as we did in the other tests files, we use a test factory here as well. All the MockTestFactory does is run a new Express HTTP instance. It does not establish a database connection since we mock the database layer.

export class MockTestFactory extends AbsTestFactory {
  private readonly server: Server = new Server()
  private readonly http: HttpServer = createServer(this.server.app)

  get app() {
    return supertest(this.server.app)
  }

  prepareEach(cb: (err?: Error) => void) {
    this.http.listen(process.env.NODE_PORT, cb)
  }

  closeEach(cb: (err?: Error) => void) {
    this.http.close(cb)
  }
}

One drawback we have using this approach is that the layer (repository.ts) is not tested at all because we overwrite it. Nevertheless, we can still test the rest of our application, like the business logic for example. Great!

Running

Using the the commands below we can run the tests with or without a database. Depending on the scenario, the files we do not want to test are excluded from execution.

{
  "test:db": "jest --testPathIgnorePatterns mock.spec.ts",
  "test:mock": "jest --testPathIgnorePatterns \"(repo|http).spec.ts\""
}

GitHub Actions

The final step is to create a CI/CD pipeline using GitHub actions that runs our tests. The according yaml file is available here. There's also a very good tutorial published on GitHub. You can decide whether to run the tests against a test database or use the mocked data layer. I decided to go with the former.

When running the pipeline with a test database, we need to make sure that we set the correct environment variables for it. Here you can find a test run.

Last words

My last tip is to have a look at the example repository on GitHub and to read it carefully There are some more tests and code snippets that I did not cover in this article. Moreover, checkout the links below. Happy coding!

Further resources

Using MySQL in Node.js with TypeScript

Lars Wächter — Thu, 07 Jul 2022 18:27:27 +0000

This post was originally published on my blog.

For a long time I was using MySQL with TypeScript without knowing that you can make use of the diamond <> operator to get a typed result from a SQL query. That changed from today on and I want it to share with you. To do so, I'm using the mysql2 npm package to run SQL queries in Node.js.

First of all, let's create a simple MySQL table:

CREATE TABLE users (
  id INT AUTO_INCREMENT PRIMARY KEY,
  email VARCHAR(50) UNIQUE NOT NULL,
  password VARCHAR(255) NOT NULL,
  admin BOOLEAN NOT NULL DEFAULT 0,
  created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP
);

Easy as that.

Next, we have to define a type for the query results which is based on the table we just created in the previous step. Therefore, we define an interface and set the properties according to the table columns:

import { RowDataPacket } from "mysql2"

export interface IUser extends RowDataPacket {
  id?: number
  email: string
  password: string
  admin: boolean
  created_at: Date
}

Don't forget to extend the RowDataPacket type from the mysql npm package, otherwise you'll get an error in the next step.

Now, we can use this interface for our SQL queries. Let's create a wrapper class that includes basic CRUD operations:

import { OkPacket } from "mysql2"

import { connection } from "./db"

export class UserRepository {
  readAll(): Promise<IUser[]> {
    return new Promise((resolve, reject) => {
      connection.query<IUser[]>("SELECT * FROM users", (err, res) => {
        if (err) reject(err)
        else resolve(res)
      })
    })
  }

  readById(user_id: number): Promise<IUser | undefined> {
    return new Promise((resolve, reject) => {
      connection.query<IUser[]>(
        "SELECT * FROM users WHERE id = ?",
        [user_id],
        (err, res) => {
          if (err) reject(err)
          else resolve(res?.[0])
        }
      )
    })
  }

  create(user: IUser): Promise<IUser> {
    return new Promise((resolve, reject) => {
      connection.query<OkPacket>(
        "INSERT INTO users (email, password, admin) VALUES(?,?,?)",
        [user.email, user.password, user.admin],
        (err, res) => {
          if (err) reject(err)
          else
            this.readById(res.insertId)
              .then(user => resolve(user!))
              .catch(reject)
        }
      )
    })
  }

  update(user: IUser): Promise<IUser | undefined> {
    return new Promise((resolve, reject) => {
      connection.query<OkPacket>(
        "UPDATE users SET email = ?, password = ?, admin = ? WHERE id = ?",
        [user.email, user.password, user.admin, user.id],
        (err, res) => {
          if (err) reject(err)
          else
            this.readById(user.id!)
              .then(resolve)
              .catch(reject)
        }
      )
    })
  }

  remove(user_id: number): Promise<number> {
    return new Promise((resolve, reject) => {
      connection.query<OkPacket>(
        "DELETE FROM users WHERE id = ?",
        [user_id],
        (err, res) => {
          if (err) reject(err)
          else resolve(res.affectedRows)
        }
      )
    })
  }
}

When running connection.query() we use the diamond operator <> to specify the type for the query result, our interface. Using the new Promise((resolve, reject) => {/* ... */}) construct we return the result as Promise and not as callback.

Notice that the readById() method returns a single instance of IUser by using the optional chaining (?.) operator. The methods create() and update() return the user that was just created / updated by reading the res.insertId / user.id value. The method remove() returns the number of affected rows, which should be 1 if everything worked fine.

One benefit of using this technique is that IDEs and editors like VSC suggest the table colums of the query results via IntelliSense now when working with them. On the other hand, your have some overhead because you have to define the TypeScript interfaces according to your database tables. This might become much more complicated when using more complex queries.

An alternative might be to use an ORM like TypeORM for example.

Recognizing hand drawn Doodles using Deep Learning

Lars Wächter — Sun, 03 Apr 2022 12:19:27 +0000

This post was originally published on my blog.

In November 2016 Google released an online game called "Quick, Draw!" that asks the player to draw an image of a prescribed object and then uses a neural network to guess what the drawing represents.
All in all there are 345 different objects the neural network can recognize.

Luckily, Google released the dataset they trained their neural network with, which includes more than 50 million by the players hand drawn images. So you can use this dataset to train your own neural network. And that's exactly what this article is about: we'll build a convolutional neural network to recognize hand drawn images using the Quick, Draw! dataset. Furthermore, we'll build a simple web app that allows the user to draw images and predict them using the network model later on.

The complete code and the trained model are available at GitHub. You can find the webapp demo on Heroku.

Neural Network

What we'll do:

Generate, load & visualize the training data
Design the network
Train & export the model
Convert the model to TFLite

Setup

For developing the convolutional neural network we'll use the following dependencies as listed in requirements.txt:



tensorflow==2.6.2
numpy~=1.19.5
quickdraw==0.2.0
matplotlib==3.3.4
jupyter==1.0.0
pillow==8.4.0

Tip: create a new virtual environment for that.

Install the dependencies using the following command.



pip3 install -r requirements.txt

Let's have a look at the dataset before writing the actual code.

Dataset

You can find the complete dataset at Google Cloud Platform, which contains more than 50 million images of 345 different categories. A list of all included categories is avaiable here.

A single image is represented as follows in the Quick, Draw! dataset:



{
  "key_id":"5891796615823360",
  "word":"nose",
  "countrycode":"AE",
  "timestamp":"2017-03-01 20:41:36.70725 UTC",
  "recognized":true,
  "drawing":[[[129,128,129,129,130,130,131,132,132,133,133,133,133,...]]]
}

The following properties are important for us:

word (the image's category)
recognized (whether the drawing was recognized by Google's AI)
drawing (an array representing the vector drawing)

The actual image in "drawing" is a multi-dimensional array including the pixel coordinates of each single stroke:



[
  [  // First stroke
    [x0, x1, x2, x3, ...],
    [y0, y1, y2, y3, ...],
    [t0, t1, t2, t3, ...]
  ],
  [  // Second stroke
    [x0, x1, x2, x3, ...],
    [y0, y1, y2, y3, ...],
    [t0, t1, t2, t3, ...]
  ],
  ... // Additional strokes
]

Generation

In order to train the neural network we create our own slightly modified dataset from Google's one. For downloading and accessing the one from Google Cloud Platform we use a Python package called quickdraw.

The following steps are required to create our own dataset:

Load 1200 training images for each class from the cloud storage
Resize them to 28x28 pixels
Save them as PNG



image_size = (28, 28)

def generate_class_images(name, max_drawings, recognized):
    directory = Path("dataset/" + name)

    if not directory.exists():
        directory.mkdir(parents=True)

    images = QuickDrawDataGroup(name, max_drawings=max_drawings, recognized=recognized)
    for img in images.drawings:
        filename = directory.as_posix() + "/" + str(img.key_id) + ".png"
        img.get_image(stroke_width=3).resize(image_size).save(filename)

for label in QuickDrawData().drawing_names:
    generate_class_images(label, max_drawings=1200, recognized=True)

Setting recognized=True ensures that only images that have been recognized by Google's AI are loaded.

After the generation is finished there should be a directory structure that looks like the following.
Each class has its own subdirectory including 1200 images:



.
└── dataset
|   ├── aircraft carrier
|   │   ├── 4504134474530816.png
|   │   ├── 4506833509154816.png
|   │   ├── ...
|   ├── airplane
|   │   ├── 4508382553702400.png
|   │   ├── 4508818253807616.png
|   │   ├── ...
|   ├── ...

In total there should be 414.000 images (345 * 1200).

Loading

Now we can load the images using Keras image_dataset_from_directory function and split them into a training and validation set. The batch size is set to 32.



batch_size = 32

train_ds = image_dataset_from_directory(
    dataset_dir,
    validation_split=0.2,
    subset="training",
    seed=123,
    color_mode="grayscale",
    image_size=image_size,
    batch_size=batch_size
)

val_ds = image_dataset_from_directory(
    dataset_dir,
    validation_split=0.2,
    subset="validation",
    seed=123,
    color_mode="grayscale",
    image_size=image_size,
    batch_size=batch_size
)

Using a 80/20 split we end up having 331.200 training and 82.800 validation images.

Visualization

Next, let's visualize some random training images using matplotlib:



plt.figure(figsize=(8, 8))
for images, labels in train_ds.take(1):
    for i in range(9):
        ax = plt.subplot(3, 3, i + 1)
        data = images[i].numpy().astype("uint8")
        plt.imshow(data, cmap='gray', vmin=0, vmax=255)
        plt.title(train_ds.class_names[labels[i]])
        plt.axis("off")

What outputs:

Architecture

In the next step we design the convolutional neural network. Therefore, we make use of the following 7 Keras layers:

There are 345 classes in total. The input shape is (28, 28, 1) since all images have a size of 28x28 pixel and 1 color channel (grayscale).



n_classes = 345
input_shape = (28, 28, 1)

model = Sequential([
    Rescaling(1. / 255, input_shape=input_shape),
    BatchNormalization(),

    Conv2D(6, kernel_size=(3, 3), padding="same", activation="relu"),
    Conv2D(8, kernel_size=(3, 3), padding="same", activation="relu"),
    Conv2D(10, kernel_size=(3, 3), padding="same", activation="relu"),
    BatchNormalization(),
    MaxPooling2D(pool_size=(2, 2)),

    Flatten(),

    Dense(700, activation="relu"),
    BatchNormalization(),
    Dropout(0.2),

    Dense(500, activation="relu"),
    BatchNormalization(),
    Dropout(0.2),

    Dense(400, activation="relu"),
    Dropout(0.2),

    Dense(n_classes, activation="softmax")
])

Moreover, here's a summary of the model. In total the modal has 2,068,019 parameters. 2,065,597 of them are trainable.



Layer (type)                 Output Shape              Param #
=================================================================
rescaling (Rescaling)        (None, 28, 28, 1)         0
_________________________________________________________________
batch_normalization (BatchNo (None, 28, 28, 1)         4
_________________________________________________________________
conv2d (Conv2D)              (None, 28, 28, 6)         60
_________________________________________________________________
conv2d_1 (Conv2D)            (None, 28, 28, 8)         440
_________________________________________________________________
conv2d_2 (Conv2D)            (None, 28, 28, 10)        730
_________________________________________________________________
batch_normalization_1 (Batch (None, 28, 28, 10)        40
_________________________________________________________________
max_pooling2d (MaxPooling2D) (None, 14, 14, 10)        0
_________________________________________________________________
flatten (Flatten)            (None, 1960)              0
_________________________________________________________________
dense (Dense)                (None, 700)               1372700
_________________________________________________________________
batch_normalization_2 (Batch (None, 700)               2800
_________________________________________________________________
dropout (Dropout)            (None, 700)               0
_________________________________________________________________
dense_1 (Dense)              (None, 500)               350500
_________________________________________________________________
batch_normalization_3 (Batch (None, 500)               2000
_________________________________________________________________
dropout_1 (Dropout)          (None, 500)               0
_________________________________________________________________
dense_2 (Dense)              (None, 400)               200400
_________________________________________________________________
dropout_2 (Dropout)          (None, 400)               0
_________________________________________________________________
dense_3 (Dense)              (None, 345)               138345
=================================================================
Total params: 2,068,019
Trainable params: 2,065,597
Non-trainable params: 2,422

Training

We'll train the neural network for 14 epochs. At the end of the training the resulting Keras model is saved to the models directory. Additionally, TensorBoard
helps us to visualize the training process.



epochs = 14

logdir = os.path.join("logs", datetime.datetime.now().strftime("%Y%m%d-%H%M%S"))
tensorboard_callback = TensorBoard(logdir, histogram_freq=1)

model.fit(
    train_ds,
    validation_data=val_ds,
    epochs=epochs,
    verbose=1,
    callbacks=[tensorboard_callback]
)

model.save('./models/model_' + datetime.datetime.now().strftime("%Y%m%d-%H%M%S"))

After 14 epochs of training the network has a validation accuracy of 61.15%, what's not that bad for 345 categories. Especially because there a similarities between some. I'm sure there are still some things you can improve to get an even better score.

Export

Last but not least since the web application requires a TFLite model, we have to convert the Keras model as described here.



# Convert the model
converter = tf.lite.TFLiteConverter.from_saved_model("models/<Model>") # path to the SavedModel directory
tflite_model = converter.convert()

# Save the model.
with open('model.tflite', 'wb') as f:
  f.write(tflite_model)

Web-App

Next we'll create the web application which is a simple FastApi server that hosts a single static HTML page where the user can draw a canvas
and the predicted labels are output as a pie chart with their probabilities. The REST API includes a single POST endpoint which is used for transforming the canvas.

Make sure to checkout the live demo.

Setup

For developing the web application we’ll use the following dependencies as listed in requirements.txt:



fastapi==0.71.0
Pillow==9.0.0
starlette==0.17.1
uvicorn==0.16.0
gunicorn==20.1.0

Backend

The backend is required to resize the canvas to 28x28 pixel as our training images and to crop its content square and remove blank space.

Instead of using Python you can accomplish the same using Tensorflow's resizeBilinear function. However, I have had bad experiences with this function.
Using it causes a huge quality loss of the image with unwanted color effects. That's the reason why I'm using Pillow on the backend side.

The endpoint /transform expects an image's strokes and the bounding box for cropping it. Using these two parameters we call transform_img which draws the image using it strokes, resize it and crops it.
The resulting image is returned from the endpoint.



class ImageData(BaseModel):
    strokes: list
    box: list

app = FastAPI()

@app.post("/transform")
async def transform(image_data: ImageData):
    filepath = "./images/" + str(uuid4()) + ".png"
    img = transform_img(image_data.strokes, image_data.box)
    img.save(filepath)

    return FileResponse(filepath, background=BackgroundTask(remove, path=filepath))

app.mount("/", StaticFiles(directory="static", html=True), name="static")

def transform_img(strokes, box):
    # Calc cropped image size
    width = box[2] - box[0]
    height = box[3] - box[1]

    image = Image.new("RGB", (width, height), color=(255, 255, 255))
    image_draw = ImageDraw.Draw(image)

    for stroke in strokes:
        positions = []
        for i in range(0, len(stroke[0])):
            positions.append((stroke[0][i], stroke[1][i]))
        image_draw.line(positions, fill=(0, 0, 0), width=3)

    return image.resize(size=(28, 28))

The final image looks as follows:

It has a resolution of 28x28 pixel and it's cropped.

Frontend

Let's continue with the frontend part of our web application. Here, we'll need a drawing area which allows the user to draw a canvas.
p5.js is a great library for such a use case.

NOTE: I will not cover each line of code here, only the important ones.
As I mentioned above you can finde the complete code here.

Model & Labels

First of all, we load our previous trained TFLite model using tfjs:



const loadModel = async () => {
  console.log("Model loading...")

  model = await tflite.loadTFLiteModel("./models/model.tflite")
  model.predict(tf.zeros([1, 28, 28, 1])) // warmup

  console.log(`Model loaded! (${LABELS.length} classes)`)
}

LABELS is an array that contains all 345 image categories. For reasons of space I placed them in a separate file.
The order of the its elements is really important, don't change it! Otherwise your model will make wrong predictions.

Drawing

Setup p5.js as follows:



const WIDTH = 500
const HEIGHT = 500
const STROKE_WEIGHT = 3

function setup() {
  createCanvas(WIDTH, HEIGHT)
  strokeWeight(STROKE_WEIGHT)
  stroke("black")
  background("#FFFFFF")
}

Handling mouse movement and click inside the canvas:



function mouseDown() {
  clicked = true
  mousePosition = [mouseX, mouseY]
}

// Check whether mouse position is within canvas
function mouseMoved() {
  if (clicked && inRange(mouseX, 0, WIDTH) && inRange(mouseY, 0, HEIGHT)) {
    strokePixels[0].push(Math.floor(mouseX))
    strokePixels[1].push(Math.floor(mouseY))

    line(mouseX, mouseY, mousePosition[0], mousePosition[1])
    mousePosition = [mouseX, mouseY]
  }
}

function mouseReleased() {
  if (strokePixels[0].length) {
    imageStrokes.push(strokePixels)
    strokePixels = [[], []]
  }
  clicked = false
}

When the mouse is clicked and moved its x/y coordinates are collected in strokePixels.
So the array contains all x and y pixels of the current drawn stroke:



[
  [x1, x2, ..., xn],
  [y1, y2, ..., yn]
]

When the mouse is released, the "current stroke" is finished and added to the imageStrokes array which
contains all drawn strokes of the canvas. In fact it's an array of strokePixels:



[
  // First stroke
  [[x0, x1, x2, x3, ...], [y0, y1, y2, y3, ...]],

  // Second stroke
  [[x0, x1, x2, x3, ...], [y0, y1, y2, y3, ...]],
  ...
]

Preprocessing

Before predicting the label we have to preprocess the canvas using our /transform endpoint and Tensorflow.js. Therefore, we use the imageStrokes
array that contains all the canvas' strokes:



const preprocess = async cb => {
  const { min, max } = getBoundingBox()

  // Resize to 28x28 pixel & crop
  const imageBlob = await fetch("/transform", {
    method: "POST",
    headers: {
      "Content-Type": "application/json",
    },
    redirect: "follow",
    referrerPolicy: "no-referrer",
    body: JSON.stringify({
      strokes: imageStrokes,
      box: [min.x, min.y, max.x, max.y],
    }),
  }).then(response => response.blob())

  const img = new Image(28, 28)
  img.src = URL.createObjectURL(imageBlob)

  img.onload = () => {
    const tensor = tf.tidy(() =>
      tf.browser
        .fromPixels(img, 1)
        .toFloat()
        .expandDims(0)
    )
    cb(tensor)
  }
}

The function getBoundingBox calculates the minimum / maximum x and y coordinates of the drawing inside the canvas. Those values are used to crop the canvas on the backend side and remove the white background.

Prediction

When making predictions we use our model and the tensor returned from preprocess. Afterwards, we select the top 3 predictions and output their probabilities with a pie chart.



const predict = async () => {
  if (!imageStrokes.length) return
  if (!LABELS.length) throw new Error("No labels found!")

  preprocess(tensor => {
    const predictions = model.predict(tensor).dataSync()

    const top3 = Array.from(predictions)
      .map((p, i) => ({
        probability: p,
        className: LABELS[i],
        index: i,
      }))
      .sort((a, b) => b.probability - a.probability)
      .slice(0, 3)

    drawPie(top3)
    console.log(top3)
  })
}

That's it! You just created an application that recognizes hand drawn images using Deep Learning. Show the app to your friends and family. I'm sure they'll be quite impressed.

Why and How to learn Programming

Lars Wächter — Mon, 28 Feb 2022 21:27:07 +0000

This post was originally published on my blog.

Programming is one of the most demanded skills in today's world. And in future, it'll play an even bigger role since digitalization is in full swing. Software is an integral part of our lives and even children already learn how to create it at a young age. So why shouldn't you too? To outsiders, programming might look like some magic that only the smartest wizards on earth are capable of. But that's certainly not true. Learning it takes a lot of time, hard work and dedication. But in the end, everybody with the right attitude can learn it.

While learning programming, you can aim for many different skill levels. One might just want to get a brief overview, do it as a hobby or master it and find his profession in it. Nevertheless, there are many reasons why one should learn how to code and even more ways to accomplish it. In this article I'd like to show you my view of the things. Why you should start and how to go about it.

Why

So, here are my top 3 reasons why you should learn how to code right now.

Mind stretching

Bill Gates once said: "Learning to write programs stretches your mind, and helps you think better, creates a way of thinking about things that I think is helpful in all domains.". At least if you can trust images with wise quotes on them and call them a reliable source. Nevertheless, programming is a skill that teaches you a new way of thinking and problem solving. It improves your problem solving skills and enhances logical thinking. You learn abstraction, to focus on the important things. Even if you don't become an expert in programming, you'll profit from knowing the basics. Logical thinking and problem solving are key skills in almost every domain and required for many different kind of jobs.

Furthermore, there's also a lot of joy while writing software: solving a problem you were working on for days, fixing that nasty bug and seeing your compiler run successfully, presenting your final work to family, friends and co-workers, developing tools that make the world a better place. Simply letting the imagination run wild. And last but not least, being able to understand the memes on r/ProgrammerHumor of course.

Digital Transformation

How could one not be amazed by today's technology? For me, it's is as breathtaking as scary what technology is capable of and what we achieved with it in the last years. Just take a moment and think about it.

Digital transformation is changing the world dramatically fast. Almost every day your hear buzzwords like "Cloud Computing", "Artifical Intelligence", "Blockchain" or "Big Data" in the news.
There are autonomouse vehicles on the streets, some of which drive better than we humans do. Doctors diagnose diseases like cancer with the help of Machine Learning. Computers beat the best chess players with ease. Your Amazon, Netflix and YouTube recommendations know your preferences better than you do. Your habits are all tracked by companies like Meta (Facebook) and Alphabet (Google), whether on smartphones, wearables, voice assistants or any other technical device. You're online nearly every waking hour, feeding personal data to the algorithms of major tech companies so they can create a digital version of you. No wonder their power exceeds that of most states. It's ridiculous.

In today's world, data is the new oil, thanks to the rising number of Internet users, less expensive storage and the increasing CPU power as written in Moore's law. The digital transformation is inevitable and collecting data is already a given.

All this progress is primarily accomplished by software (and hardware) developed by us humans. Software / Hardware / ML engineers, data scientists, mathematicians, physicists and many more write the code that will run our future and provide the models to predict it. Having at least a small understanding of how this kind of software, models or algorithms in general work, is in my opinion one of the main reasons for learning programming. It's about building a digital awareness, knowing how your environment works and what technology is capable of nowadays.

Job Market

Mostly caused by the digital transformation, the worldwide job market is seeking for talented software engineers, and companies offer great benefits to attract new employees: flexible working hours, home office, high salaries and much more. Tech jobs can be found in almost all industries like: automotive, banking, environment, fashion, health, insurance and public sector.

Furthermore, your job is safe. It's very unlikely that you'll be replaced by someone else in future, be it another employee or an AI. Coding skills are in high demand but not very common, at least not yet. There are too few of us to meet the economy's needs. That is why it's not uncommon for companies to apply to the developers these days. You have the free choice.

Altough a high salary shouldn't be the only reasons for you to learn how to code. You wouldn't be happy. Have fun in what you do, especially in your job, because you spend most of your life doing it.

How

Now that we have discussed the reasons for learning to code, let's have a look at how to go about it. As I said at the beginning of this post, there are many ways to learn programming: university, school, bootcamps, online courses, self-taught. They all have their pros and cons. The following way is the one I would recommend to a beginner. Here we go.

What is programming?

First of all, take a moment and think about what programming is at its core, regardless of any programming language. What is it really about and what is a computer's purpose?

The concept of programming is largely the same for most of the languages out there, whether you're learning Python, C, Kotlin, Java or JavaScript: you write a set of instructions (code) that are read and executed sequentially by your machine. You, the instructor, tell the computer what to do and how to behave. Doing so, each written line of code has a certain purpose and effect, whether you're working on web / desktop apps, microcontrollers or anything else.

The pool of instructions you can choose from and how they are written depends on your programming language. Nevertheless, the key idea remains the same.

Source code, especially algorithms, can be visually represented using flowcharts, what makes it much easier for us humans to understand them in many cases. An algorithm is just a collection of instructions with the goal of accomplishing a specific task.

Let's have an example. The following algorithm, written in JavaScript, calculates the sum of all numbers from 1 to 10, which is 55, and then prints it.

let sum = 0
for (let i = 1; i <= 10; i = i + 1) {
  sum = sum + i
}
console.log(sum)

The according flowchart looks as follows:

As you can see, the program can be split into smaller parts that even a non-programmer can understand. In total, there are five instructions sum=0, i=1, sum=sum+i, i=i+1 and print sum to execute and one condition to check i<=10. This is obviously a fairly simple algorithm. Others can contain hundreds or even thousands of instructions, making them much more complicated.

You may have noticed that the flowchart and the algorithm it represents work independently of any programming language. You can take the chart and implement its sequence of commands in Python, C or any other language. That's the key idea that all languages have in common. Focus on getting used to this kind of workflow.

Now that you have an idea about what programming is, it's time to introduce you to Karel. He teaches you how to code by following your commands.

Karel The Robot

Since there are so many similarities between the languages, I don't recommend you to start with one of the common ones I just mentioned above, even though this might be the conventional way to go. You'd be better off sticking with Karel The Robot. Karel is an educational programming language developed by the American professor Richard E. Pattis, that teaches you the core concepts of imperative programming. It does so by allowing you to write instructions to control a robot's movement on a 2-dimensional map, mostly a maze. In fact, this is what programming is all about: writing clear and precise instructions to let the computer perform a certain action.

Using Karel, you don't have to learn complicated syntax first. Its command set is manageable and very easy to understand, even for a beginner, but the functionality is still similar to those of other languages. To quote Eric Roberts [p. 1]:

In sophisticated languages like Java, there are so many details that learning these
details often becomes the focus of the course. When that happens, the much more critical
issues of problem solving tend to get lost in the shuffle. By starting with Karel, you can
concentrate on solving problems from the very beginning. And because Karel encourages
imagination and creativity, you can have quite a lot of fun along the way.

Here's an example of Karel The Robot. The challenge: move forward to the right beeper (green diamond), pick it up, go back to the starting point and do the same thing for the other one. Step by step.

A solution might look as follows:

void defuseTwoBombs()
{
    defuseBomb();
    turnRight();
    defuseBomb();
    turnAround();
}

void defuseBomb()
{
    moveForwardWhileClear();
    pickBeeper();
    turnAround();
    moveForwardWhileClear();
}

void moveForwardWhileClear() {
    while(frontIsClear()) {
        moveForward();
    }
}

The robot moves forward as long as its front is clear (moveForwardWhileClear). It picks the beeper up (pickBeeper), turns 180° (turnAround) and goes back (moveForwardWhileClear). These are the instructions listed inside the function defuseBomb. Afterwards, the robot turns 90° to the right (turnRight) and does the exact same thing again (defuseBomb). Pretty cool.

Obviously, Karel teaches you only the rudimentary basics of programming and problem solving in general. Sooner or later you have to switch to a "real" and more popular programming language.

There are multiple versions of Karel The Robot out there. I would recommend to check out the one by GitHub user fredoverflow which is written in Java. This one includes multiple exercises the user has to solve, like the one from above (defuseTwoBombs). Alternatively, have a look at the web version developed by Stanford Assistant Professor Chris Piech which has some bugs unfortunately.

Pick a language

Now it's time to learn a "real" programming language. There are dozens of articles on the Internet about whether you should start with Python, JavaScript or language xyz. Don't waste your valuable time so much when making a decision. Pick one and stick with it. In the end, it's not that important which one you choose. The fastest one you can start with is JavaScript. Just press F12 in your browser to open the DevTools and start typing "Hello World" in it. It takes only one keypress. There are also great online editors you can make use of, altough I would rather recommend to use a local setup on your machine.

Learn the fundamentals

Start with the fundamentals and repeat them everyday: data types, variables, arithmetic, if-conditions, loops, functions and so on. Some of them should look familiar to you from Karel The Robot. Learn the syntax and semantic of your programming language. In the beginning, it's not about knowing every feature, method or API that it offers. Start easy, learn the basics and take it slow. Future knowledge will build on this.

Moreover, don't get stuck in tutorial hell and waste your time watching endless tutorials on YouTube, Udemy or whatsoever where everyone is coding but you. You have to write your own code to learn programming. Try and fail. Make mistakes. If you get stuck on a problem, take a break. I don't know how many times I was lying in bed, sitting in the train or at the dinner table and the solution just came out of nowhere to my mind. It's amazing how our brain can solve problems in the background without actively paying attention to them.

Most important: build a daily habit. Code every day, even if it's just for a short period of time like 10 or 15 minutes. Repetition is the key to success.

Learn the algorithms and data structures

Next, learn the algorithms and get used to what I call "computational" or logical thinking. This might be not easy. Take a problem, break it down into smaller ones and solve them step by step. Get used to a sequential workflow. Just as you did for Karel The Robot. Before writing the code, take a sheet of paper, make some sketches, draw a flowchart and try different approaches. When you're done, pick the next one and include solutions from problems you've solved before. Your first solution might not be the most efficient one. That's okay. Get your code working and improve it afterwards. But please don't copy solutions that you don't understand and take them for granted.

It's not about learning every algorithm out there for sorting an array, traversing a binary tree or finding the shortest path. Have a look at some existing algorithms and try to implement or even slightly modify them. Give LeetCode a try. It's a great website for doing coding challenges.

Moreover, get in touch with the most common data structures: Arrays, Lists, Queues, Stacks, Maps, HashTables, Trees. Try to use some of them when working on different problems. I could bet you will not use more than two or three of them in your future workday. Especially trees are rather uncommon.

In this step, you may also want to take a look at some concepts such as OOP or functional programming, depending on your language.

Get back to the roots

Get back to the roots. Code without using a heavyweight IDE like IntelliJ or Visual Studio. Get rid of tools like Linters and Prettiers which highlight your code smells and autoformat your code. Get rid of fancy frameworks and libs that act like magical black boxes. Get rid of build tools that take more time building the project than the coding itself. They are unnecessary ballast.

Don't get me wrong, all these tools are amazing and I highly encourage you to use them in your later career. But in the beginning, they just distract you from your main goal: learning programming. Add them to your repetoir later on after you've learnt the fundamentals.

Keep in mind that you don't need much to get started. What you really need is a simple text editor and a compiler / interpreter for your programming language of choice. Above all, you don't need a +1000€ MacBook with fancy stickers on it, beside you want to fit the clichés. If you want to learn programming by creating the next Crysis, you might need one too.

Teach others

In my opinion, sharing knowledge is one of the greatest things you can do with it. Schwarzenegger already said: "Help others and give something back". So share your expertise and new discoveries with others. Both, you and your learning partner, will highly benefit from it. Maybe start your own blog too?

The programming community is huge, take advantage of that and get into conversations. You can participate in discussions on platforms like DEV or Stackoverflow, join multiple subs on Reddit or attend local meetups in your area. In times of the Internet there are endless possibilities.

Learn the tools

Once you know the fundamentals and some advanced concepts, go ahead and get familiar with tools like: GIT, Linters, IDEAs, Maven / Gradle / Webpack. Be amazed by IntelliJ's autocompletion and it's code analyzing capacity. Learn some common used libraries and frameworks for your programming language, but please don't end up coding dozens of similar CRUD REST-APIs.

Include these tools into your daily workflow and start working on your first "bigger" project. Make it open source and share it on GitHub so other people can contribute and give feedback.

Land an internship

Finally, after you have learnt the basics, some advanced concepts and tools, go ahead and apply for a software engineering internship near your location and surrond yourself with people that are more experienced than you. Especially when you're a student. The hands-on experience you gain may be worth much more than any course you'll ever take.

With that being said gain as much experience as possible: get in touch with production code, work in an interdisciplinary team, join discussions and code reviews, deploy applications, drop the live database (joke). And one of the most important things: ask questions, lots of questions!

Landing and internship can be hard, I know. You might have to run through multiple assessment centers, coding interviews / challenges and so on. Don't be discouraged when you fail your first ones. Coding interviews are broken.

Last words

That's it. Sounds complicated? Yeah, it is. Don't let anyone tell you otherwise. It's no reason why you shouldn't start right now. Take your time, follow a plan and you'll make it. I promise. Go for it, you won't regret it.

Let me know if this article helped you or not.

Improving Minimax performance

Lars Wächter — Thu, 23 Dec 2021 12:51:58 +0000

This post was originally published on my blog.

The Minimax algorithm, also known as MinMax, is a popular algorithm for calculating the best possible move a player can player in a zero-sume game, like Tic-Tac-Toe or Chess. It makes use of an evaluation-function provided by the developer to analyze a given game board. During the execution Minimax builds a game tree that might become quite large. This causes a very long runtime for the algorithm.

In this article I'd like to introduce 10 methods to improve the performance of the Minimax algorithm and to optimize its runtime. Some of them have a bigger and some a smaller impact. In the future I'll try to add new methods. I won't go into more detail about how the algorithm works. It's just about optimizing it. Check out the link from above to learn how the algorithm actually works.

A quick overview of all techniques discussed in this article:

Alpha-Beta Pruning
Pre-sort moves
Bitboards
Transposition Tables
Board Symmetries
Reduce possible moves
Instant win
Improve .hasPlayerWon() function
Improve .evaluate() function
Decrease search depth

1. Alpha-Beta Pruning

One of the most widely-known improvements is Alpha-Beta-Pruning, also known as Alpha-Beta-Cut or Alpha-Beta-Search. This slightly modified version of Minimax can reduce the algorithm's runtime drastically. The key idea here is to reduce the number of nodes within the game tree by cutting them off. Therefore, two values α and β are passed along the tree. These values represent the worst-case-scenario for each player.

Have a look at the second row (3 6 3). Here, the α value is 6, which is the minimum score that MAX will reach after evaluating the first two nodes (3 6). When evaluating the third node MIN keeps in mind that MAX will at least achieve a score of 6. If MIN finds a value that is less than α, here 5, the other node 8 can be cut off. The reason: no matter what MIN chooses, MAX will choose the α value 6. And MIN will choose a value that is definitely <= 5.

Have a look at the link from above for a more detailed explanation.

2. Pre-sort moves

Try to pre-sort the list of possible moves starting with the best ones when using Alpha-Beta Pruning. In this case, there's a higher chance of cutting of nodes within the game tree since the algorithm starts with a high alpha or low beta value at the beginning of each level.

3. Bitboards

Bitboards are a way of representing the game board using bits. In this case, each single bit represents one position on the board. Moreover, both players have their own board.

An example bitboard for Tic-Tac-Toe:



const board = [
    0b000_000_000,  // Player 1 Board (X)
    0b000_000_000   // Player 2 Board (O)
]

One of the main advantages of bitboards is that they allow a lot of flexibility in evaluation. Using bitwise opertations like AND, OR, XOR and shifting you can check for winning conditions, play & validate moves or rotate the game board in a very short time. They are also useful for calculating the board hash, which is used for transposition tables.

Depending on the complexity of your game bitboards might make a remarkable difference in terms of performance. Check out this link to see a Connect Four implementation using bitboards.

4. Transposition Tables

Transposition tables are used to store the result of already analyzed boards. This prevents the algorithm from evaluating the same board multiple times and reading it from a memory, the transposition table, instead.

Usually, transposition tables are implemented as a HashMap where the key is the hashed board. You can either store the transposition table in-memory and build it during the Minimax execution or store it in a non-volatile memory, like a text file for example.

A transposition table might look as follows:



8063104835353205054 2 -8534.0 -1
3522504971336218492 1 1082.0 -1
9207316698546002515 5 2705.0 1

Each single row contains information about:

the board hash
the played move
the move's evaluated score
the move's player

In Minimax, you can search for the current board hash within the transposition table and return the according entry.



function minimax(storage, game) {
    // recursion anchor ...

    const storedMove = storage.get(game.calcBoardHash());
    if(storedMove) return storedMove;

    // evaluation ...
}

If not entry was found, the board must first be evaluated. At the end of Minimax you can push the evaluated move to the transposition table right before it's returned:



function minimax(storage, game) {
    const bestMove; // evaluation ...
    storage.set(game.calcBoardHash(), bestMove);
    return bestMove;
}

5. Board Symmetries

The key idea is that you apply a symmetrie to your current examined board and read its counterpart from the memory, if existing. This reduces the number of board evaluations immensely. Symmetries are very powerful especially in combination with bitboards.

Depending on your game there are different symmetries that you can make use of. For example:

Inverting the board
Rotating the board (and inverting) => Tic-Tac-Toe, Mill
Mirroring the board on the x/y axis (and inverting) => Connect Four, Chess

With Bitboards you can easily rotate and mirror the board using binary operations. Check out this GitHub Gist to see a Bitboard for Tic-Tac-Toe in Kotlin.

Inverting the board

Tic-Tac-Toe



1)          2)

X . .       O . .
X O O       O X X
. . .       . . .

In the first scenario, the best possible move for player X is to play position 7 (bottom left). The same applies to player O in the second case. If Minimax have already calculated the best possible move for board #1 and it's stored in a transposition table, you can invert the board in the case of board #2, which gives you board #1, and read the best possible move of board #1 from memory and apply it. Keep in mind that this only applies to player O for the second board.

Rotating the board

Tic-Tac-Toe



1)          2)

X . .       . X X
X O O       . O .
. . .       . O .

Again, the best move for player X is to play position 7 in the first scenario. The second board is the same as the first one, but rotated by 90° clockwise. This time if Minimax have already evaluated board #1, you can rotate board #2 by 90°, which gives you board #1, and again read the best possible move of board #1 from memory. In this case you have to slightly modify the move: since the board was rotated by 90° clockwise you have to rotate the move 90° counter clockwise. Repeat this procedure for 180° and 270°.

Moreover, you can combine this method with the inverted board from above.

Mirroring the board

Connect Four



1)                  2)

. . . . . . .       . . . . . . .
. . . . . . .       . . . . . . .
. . . . . . .       . . . . . . .
. X . . . . .       . . . . . X .
. X . O O . .       . . O O . X .
. X O X O . .       . . O X O X .

Here, the best move for player X is to play column 2 in the first scenario. The second board is the same as the first one, but mirrored on the center y-axis. This time, after the evaluation of board #1, you can mirror board #2, which gives you board #1, and apply its best move. Don't forget to to mirror the move as well.

Once more, you can combine this technique with the inverted board.

6. Reduce possible moves

Keep in mind that each single move causes a new child node that has to be evaluated recursively. Therefore, it's simple: a smaller number of possible moves for each board leads to less nodes and evaluations in your game tree. That means: remove unnecessary and irrelevant moves. For example, in Connect-Four, don't play any moves that will definitely not result in a row of 4 in future. Be careful not to remove any moves that could prevent your opponent from winning.

7. Instant win

Before evaluating all possible moves you can check whether any of them will result in an instant win for the current player. If that's the case you can directly return this move and you don't have to evaluate the other ones.



function minimax(game) {
    // recursion anchor ...

    for(const move of game.getPossibleMoves())
        if(game.doMove(move).hasPlayerWon(game.currentPlayer))
            return [1_000_000, move];

    // evaluation ...
}

Furthermore, make sure to return a high score since it's a win-move.

8. Improve .hasPlayerWon() function

The .hasPlayerWon() function checks whether a player has won. It's commonly used in the recursion anchor, when evaluating the game board. Here, we can optimize two things:

Don't check before a win is possible
Don't check both players



game.hasPlayerWon = function(player) {
    if(this.playedMoves < 5) return false;
    // check if the given player has won ...
}

For example, in Tic-Tac-Toe, at least 5 moves must have been played before a player can win. That's why we immediately return false when less than 5 moves were played.

Moreover, we only have to check whether one player has won, not both. The player who played the last move is the only one who could have won so we don't have to check the other one.



function minimax(nodeHeight, game) {
    // recursion anchor
    if (nodeHeight == 0 || game.isDraw() || game.hasPlayerWon(-game.currentPlayer))
        return [game.evaluate(), null];
    // ...
}

Here, when calling game.hasPlayerWon() we check whether the previous player (the one who played the last move) has won. If player A is stored as 1 and player B as -1 you can easily switch between them using a negate: -game.currentPlayer.

9. Improve .evaluate() function

The evaluation function is called dozen of times during the execution of Minimax. That means: improve this function and make it as fast as possible. Combine it with Bitboards and check for a player's win blazing fast.

Moreover, there's no need to dig into the depths of the game tree if your evaluation function returns a score that reflects the board quite well. Just a single descent within the game tree can lead to a much longer runtime.

Another tip: include the current node height in the evaluation score. Moves that are higher up in the game tree will have a better score this way and the algorithm will pick the one that leads the fastest to a win.



game.evaluate = function(nodeHeight) {

    const score; // calc score ...

    return score + nodeHeight;

}

function minimax(nodeHeight, game) {

    // recursion anchor

    if (nodeHeight == 0 || game.isDraw() || game.hasPlayerWon(-game.currentPlayer))

        return [game.evaluate(nodeHeight), null];

    // evaluation ...

}

Decrease search depth

The last option might be the most obvious one: decrease the maximum search depth of the algorithm.
Does your game tree really have to be that deep? Do you have to look 9 or 10 moves ahead? Isn't a lookahead of 5 enough? Depending on the game, I guess most human players cannot anticipate more than maybe 3 to 4 moves. As I already said above, each single tree level results in a much longer runtime. Think about it.

Further resources

Last but not least a list with some useful resources.

We blog: Minimax Improvements
Chessprogramming: Bitboards
Wikipedia: Transposition Tables

Check out my example projects as well:

Connect Four in Kotlin
TTT Bitboard in Kotlin
Minimax in Kotlin
Zobrist Hashing in Kotlin

How I structure my React projects

Lars Wächter — Tue, 31 Aug 2021 13:24:23 +0000

This post was originally published on my blog.

It's been quite a while since I wrote an article about how I structure my Node.js REST APIs. The article covered the approach of designing a well organized and maintainable folder structure for Node.js applications.

So today I don't want to talk about Node.js APIs, but about the architecture of React applications and answer the same question from the previous article a second time:

What should the folder structure look like?

And again: there’s no perfect or 100% correct answer to this question, but there are tons of other articles discussing this one on the internet too. This folder structure is also partly based on multiple of them.

One important thing to mention is that React does not really tell you how to organize your project, except the fact that you should avoid too much nesting and overthinking. To be exact they say: (Source)

React doesn’t have opinions on how you put files into folders. That said there are a few common approaches popular in the ecosystem you may want to consider.

Take a look at the linked source where you can read more about those common approaches. They won't be further discussed in this article.

The following structure and architecture is one that has proven maintainable and reliable for me. It might give you a help for designing your own project. Keep in mind that the following architecture is based on a application bootstrapped with create-react-app and written in JavaScript.

Directory: root

react-project
├── node_modules
├── public
├── src
├── package.json
└── package-lock.json

This structure is nothing special and shouldn’t be new to you. It’s actually a basic create-react-app setup. The interesting part here is the content of the src folder which this article is about.

So what do we have in here?

react-project
├── api
├── components
├── i18n
├── modules
├── pages
├── stores
├── tests
├── utils
├── index.js
├── main.js
└── style.css

As you can see the application is primarily split into eight directories. From here on, we'll go top-down through the directories and examine each one.

Let’s start with the api directory.

Directory: src/api

react-project
├── api
│   ├── services
│   │   ├── Job.js
│   │   ├── User.js
│   ├── auth.js
│   └── axios.js

The api directory contains all services that take care of the communication between the React application (frontend) and an API (backend). A single service provides multiple functions to retrieve data from or post data to an external service using the HTTP protocol.

auth.js provides functions for authentication and axios.js contains an axios instance including interceptors for the outgoing HTTP requests and incoming responses. Moreover, the process of refreshing JWTs is handled in here.

Directory: src/components

react-project
├── components
│   ├── Job
│   │   ├── Description.js
│   │   └── Preview.js
│   └── User
│   │   ├── Card.js
│   │   ├── Create.js
│   │   └── List.js

If you're already familiar with React you should know that it's mainly component based. The components are actually the heart of every React application. The whole application, at least the presentational view, is built of many small components.

So what is a component? Source

Components let you split the UI into independent, reusable pieces, and think about each piece in isolation.

Imagine you have a website like Twitter or Facebook. The large website is made of many smaller pieces (components) that can be Buttons, Inputs or Widgets for example. Those pieces are put together to build ever more complex and larger ones. Each component has its own lifecyle and state management, whereby you can share a component's state with other ones.

Components are reused multiple times within the application to save the developer from writing redundant code.

Don't repeat yourself (DRY)

Splitting the codebase into multiple components is not just a "React thing". It's a common pattern in software engineering to simplify the development process and the maintenance later on.

In React, a component is mostly a simple JavaScript function or a class. Usually, I create a new file for each single component. In some rare cases I group multiple of them (functions or classes) into a single file. Imagine a UserList.js component which renders multiple elements of UserListItem:

const UserList = ({ users }) => (
  <ul>
    {users.map(user => (
      <UserListItem key={user.userId} user={user} />
    ))}
  </ul>
)

const UserListItem = ({ user }) => <li>{user.name}</li>

Here, it makes sense to combine both into one file. Further, UserListItem is probably not even used by any other component than UserList.

Beside the components themselves, you can also add their stylesheets or tests to this directory.

Directory: src/i18n

react-project
├── i18n
│   ├── de.json
│   └── en.json

i18n stands for internationalization and takes care of the language support of the application. The including JSON files are basically objects containg fixed constants as keys and their associated translations as values.

Therefore, the keys should be equal for each language file. Only the values (translations) differ from each other. You can easily query those language files later on by writing your own custom hook or component.

Directory: src/modules

react-project
├── modules
│   ├── logger.js
│   └── session.js

This directory includes some global modules that might be used for logging or as wrapper for the browser's LocalStorage for example.

Directory: src/pages

react-project
├── pages
│   ├── Home
│   │   ├── components
│   │   │   ├── Dashboard.js
│   │   │   └── Welcome.js
│   │   └── index.js
│   ├── Login.js
│   └── Profile.js

The pages directory includes the react-router-dom paths accessed while navigating through the application. Here, we collect multiple components into a single larger one to display a complete page view.

A page might contain its own component directory which includes "local" components that are only used on this page. For complex pages with a deep component tree you might want to check out the React Context API which makes it much easier to pass props along the tree and to handle a global "page state".

Directory: src/stores

react-project
├── stores
│   ├── language.js
│   └── user.js

This directory includes all global React states that can be accessed from any component within the application. While Redux is probably the most popular solution for managing global state I prefer to use zustand. It's very easy to get started with and its API is really straightforward.

Directory: src/tests

react-project
├── tests
│   ├── language.test.js
│   └── utils.test.js

The tests directory includes tests that do not belong to certain components. This could be tests for the implementation of algorithms for example. Moreover, I validate and compare the keys of the language files I mentioned above to make sure I did not miss any translation for a given language.

Directory: src/utils

react-project
├── utils
│   ├── hooks
│   │   ├── useChat.js
│   │   ├── useOutsideAlerter.js
│   │   ├── useToast.js
│   ├── providers
│   │   ├── HomeContextProvider.js
│   │   ├── ToastContextProvider.js
│   ├── colors.js
│   ├── constants.js
│   ├── index.js

Here, we have a bunch of utilities like: custom hooks, context providers, constants and helper functions. Feel free to add more stuff here.

All together

Last but not least a complete overview of the project structure:

react-project
├── api
│   ├── services
│   │   ├── Job.js
│   │   ├── User.js
│   ├── auth.js
│   └── axios.js
├── components
│   ├── Job
│   │   ├── Description.js
│   │   └── Preview.js
│   └── User
│   │   ├── Card.js
│   │   ├── Create.js
│   │   └── List.js
├── i18n
│   ├── de.json
│   └── en.json
├── modules
│   ├── logger.js
│   └── session.js
├── pages
│   ├── Home
│   │   ├── components
│   │   │   ├── Dashboard.js
│   │   │   └── Welcome.js
│   │   └── index.js
│   ├── Login.js
│   └── Profile.js
├── stores
│   ├── language.js
│   └── user.js
├── tests
│   ├── language.test.js
│   └── utils.test.js
├── utils
│   ├── hooks
│   │   ├── useChat.js
│   │   ├── useOutsideAlerter.js
│   │   ├── useToast.js
│   ├── providers
│   │   ├── HomeContextProvider.js
│   │   ├── ToastContextProvider.js
│   ├── colors.js
│   ├── constants.js
│   ├── index.js
├── index.js
├── main.js
└── style.css

That’s it! I hope this is a little help for people who don't know how to structure their React application or didn’t know how to start. Feel free to give any suggestions.

Database seeding in Node.js

Lars Wächter — Sat, 21 Aug 2021 15:14:37 +0000

This post was originally published on my blog.

In this article I'd like to talk about database seeding using Node.js and MySQL: what it is and how to implement it. You'll notice that it's actually quite easy and straightforward. For this tutorial I chose MySQL as database system but this procedure should also work with any other one. In this case there might be some small modifications necessary regarding the SQL query execution.

Let's start with an explanation of database seeding. Source

Database seeding is the initial seeding of a database with data. Seeding a database is a process in which an initial set of data is provided to a database when it is being installed. It is especially useful when we want to populate the database with data we want to develop in future.

So our goal is to "feed" the database with dummy data on its initialization. This can be very helpful especially during the development process or for onboarding new employees that run the development environment (database) locally on their machine.

First of all we create a new SQL script that includes the queries for inserting the dummy data. This script will be later executed using Node.js.

The seeding script: ./db/seeding.sql

/* Insert admin account */
INSERT INTO user (email, firstname, lastname, password)
VALUES ('admin@email.com', 'John', 'Doe', ?);

This SQL command inserts a new data set into the user table. The ? is a placeholder that gets replaced with a variable, the initial password, when calling the script using Node.js. You can add more queries here of course.

Make sure that the database tables were created before running the script otherwise it'll fail. Most ORMs take care of that.

Next, we write the Node.js script, which is required to establish a database connection and execute the SQL snippet we just created.

The Node.js script: ./db/index.js

const mysql = require("mysql2")
const fs = require("fs")
const bcrypt = require("bcryptjs")

// Load .env variables
require("dotenv").config()

// Read SQL seed query
const seedQuery = fs.readFileSync("db/seed.sql", {
  encoding: "utf-8",
})

// Connect to database
const connection = mysql.createConnection({
  host: process.env.DB_HOST,
  user: process.env.DB_USERNAME,
  password: process.env.DB_PASSWORD,
  database: process.env.DB_NAME,
  multipleStatements: true, // IMPORTANT
})

connection.connect()

// Generate random password for initial admin user
const psw = Math.random()
  .toString(36)
  .substring(2)
const hash = bcrypt.hashSync(psw, 10)

console.log("Running SQL seed...")

// Run seed query
connection.query(seedQuery, [hash], err => {
  if (err) {
    throw err
  }

  console.log("SQL seed completed! Password for initial admin account: " + psw)
  connection.end()
})

What happens here?

Load the environment variables using dotenv
Read the SQL snippet
Connect to the database (MySQL)
Generate a random password (hashed)
Execute the SQL snippet

At the end the admin password is logged to the console if everything worked fine. Instead of using dotenv you can also use fs.readFileSync to load your database credentials from any other file.

If you're not using MySQL you simply have to modify the database connection setup. I'm sure there's a npm package for your database system that can handle this.

Last but not least let's extend the package.json scripts to simplify the execution of the Node script.

{
  "scripts": {
    // ...
    "seed": "node db/index.js"
    // ...
  }
}

Now you can run the database seeding with a single command from the terminal: npm run seed. That's it! You database is filled with dummy data and you can focus on the important stuff.

There's also a GitHub repository available including an example application that makes use of database seeding. Have a look.

Zobrist Hashing

Lars Wächter — Sun, 02 Aug 2020 20:14:23 +0000

This post was originally published on my blog.

Zobrist hashing, named for its inventor Albert Zobrist, is a technique to represent game board positions, like from chess or Go, as hash value. It's mainly used with transposition tables, a special kind of hash table that is indexed by a board position and used to avoid analyzing the same board position more than once.

What it's good for

In game theory there are algorithms like Minimax or AlphaBeta that are used to analyze board positions and find the best possible move in the given situation. This might be applied to games like chess, Go or tic-tac-toe.

These algorithms take a given starting position and simulate the further course of the game with all possible moves for each player. With the help of an evaluation method, that is prescribed by the developer, the algorithm can calculate a score in each game situation. Based on this score the algorithm knows how good or bad a position is or a move that has led to this position. Ideally, the outpout of such an algorithm is the best possible move with it's calculated score.

One problem is that it might take a very long time to calculate the best possible move, especially for games like chess. That's because game like chess has a huge game tree. A game tree is a directed graph whose nodes are positions in a game and whose edges are moves. Algorithms like Minimax builds such a graph and traverse it to find the best possible move.

With the help of transposition tables it's possible to speed up these algorithms. Transposition tables act like a cache that store already analyzed board positions. While building up a game tree you mostly come across the same board position more than once. Without a transposition table you have to re-analyze the board position each time. So once the algorithm evaluated a position it stores the result in the transposition table to avoid this behavior. The next time the algorithm comes across this position it can take the result from the transposition table.

All in all: Transposition tables are used within the algorithms to avoid analyze the same position multiple times.

Mostly, transposition tables are implemented as a HashMap where the key is a board position in string representation. So regarding to a board position it's possible to store some information about it, like the best move.

This is where the Zobrist hash comes up: Zobrist hashing is a way to represent a given board position as an (unique) hash value. This hash is used within the transposition table to map information, like the best move, to the board and make it accessible.

So the following paragraph describes how a Zobrist hash works and how it's calculated. Tic-tac-toe is taken as example game here. At the end of this post you'll find an implementation in Kotlin.

How it works

Zobrist hashing works with a bunch of xor operations of random generated numbers, called keys. We break this down into two parts:

Generating the keys
Calculating the hash

Generating the keys

First of all, we have to generate keys according to the following scheme:

For every available board cell and every possible game character in one of these cells, we generate a random number.

This might sound a little bit confusing but it's actually quite easy. Let's have a look at our example, tic-tac-toe:

In a tic-tac-toe board, there are 9 available cells. In each of one of these cells there can be placed 2 different game characters: X or O. So according to above's quote we have to generate 18 (9*2) random numbers.

cell  |   player 1 (X)  |   player 2 (O)
------------------------------------------
0     |      44532      |      72217
1     |      90195      |      10291
2     |      81410      |      65932
3     |      36721      |      91854
...

In practice, most of the time 64 bit numbers, e.g. of data type Long, are used as random numbers. This reduces the risk of collisions while calculating the hashes later on.

Calculating the hash

Now, after the keys were generated it's possible to calculate the Zobrist hash of a given board position:

Take the previously generated random number of each cell where a game character is placed in and combine them per xor operation.

Again, it's easier than it might sound. Let's have an example.

Before we begin with that a quick note: The cells of our tic-tac-toe game are ordered like this: from 0 to 8.

0 1 2 
3 4 5
6 7 8

Okay, now it's time for an example. Have a look at the following board position:

X . O
X . .
. . .

Player 1 (X) in cells: 0, 3
Player 2 (O) in cells: 2

The players played in the following cells:

Player 1: 0, 3
Player 2: 2

Finally, we can calculate the Zobrist hash for this position: We take the random numbers / keys for these cells from above and combine them per xor operation. The order of the operations does not matter:

    44532 (cell #0 player 1)
XOR 65932 (cell #2 player 2)
XOR 36721 (cell #3 player 1)
---------
  = 74505 (Zobrist hash)

We successfully calculated the Zobrist hash for the game position: 74505.

Now, this hash can be used to store the board position inside the transposition table. In this case, the calculated hash value is used as key.

Reusing the hash

A huge advantage of this procedure is that it's not necessary to calculate the hash completely new after a move was played: We can take the key of the cell where the new move is played and combine it with the already existing Zobrist hash.

Assuming we have the same position as above:

X . O
X . .
. . .

=> 74505 (Zobrist hash)

Now, player O plays his move in cell #1, even though it's a bad one:

X O O
X . .
. . .

Again we'd like to calculate the Zobrist hash for the newly created board position. We use the old hash 74505 and combine it again per xor operation with the key of the new played cell (#1):

    74505 (old Zobrist hash)
XOR 10291 (cell #1 player 2)
---------
  = 68410 (new Zobrist hash)

Reusing the old hash to calculate a new one after a move was played makes it very efficient for traversing a game tree.

Moreover, it's quite easy do undo a move: we use the newly created Zobrist hash and combine it with key of the cell we'd like to undo. Let's undo player's 2 last move in cell #1 from above.

    68410 (new Zobrist hash)
XOR 10291 (cell #1 player 2)
---------
  = 74505 (Zobrist hash after undo last move)


Resulting position:
X . O
X . .
. . .

The Zobrist hash, 74505, equals the one in the beginning, before the move of player 2 was played.

Last but not least an example implementation in Kotlin for tic-tac-toe:

This post was originally published on Medium.

Setting up a MySQL container in Docker

Lars Wächter — Sun, 05 Apr 2020 03:03:07 +0000

This post was originally published on my blog.

Docker is a term you might already have heard or read about in the tech scene since it’s a quite upcoming trend in the last couple of years. Docker is platform as a service (PaaS) mostly used by software developers to develop, deploy, and run applications. A big benefit of it is that you can ship and run your application (almost) anywhere without having any external software installed on your operating system that is needed for your app besides Docker.

So, what exactly is Docker? Source

Docker is a tool designed to make it easier to create, deploy, and run applications by using containers. Containers allow a developer to package up an application with all of the parts it needs, such as libraries and other dependencies, and deploy it as one package. By doing so, thanks to the container, the developer can rest assured that the application will run on any other Linux machine regardless of any customized settings that machine might have.

This means the application runs inside a container which is some kind of a special type of process that is isolated from other processes.

The following describes how to setup a Docker container that runs a MySQL database.

Installing Docker

The first step is to install Docker. On their website you can find an instruction how to install Docker on different operating systems.

Creating MySQL Docker container

First of all we have to pull the official MySQL Docker image from the registry. The image is executable package of software that includes everything needed to run the application (MySQL).

docker pull mysql

Next, we create a new container from the image we pulled before.

docker create --name mysql-test -e MYSQL_ROOT_PASSWORD=test mysql

This command creates a new Docker container called mysql-test and sets the MySQL root user password to test.

Run the following command to list all installed containers on your system.

docker ps -a

You should see the container we just created.

Running the container

Time to start the container. mysql-test is the container’s name we set when we created it. You can use the container’s id here as well.

docker start mysql-test

Let’s check if the container is running. This should print all running containers to the console.

docker ps

Now we can access the container via bash.

docker exec -it mysql-test bash

Last but not least we can start the mysql-client and run SQL commands. The root password is test which we set on the container’s creation.

mysql -u root -p

Instead of pulling, creating and starting the container in multiple steps, you can accomplish this with one command as well.

docker run --name mysql-test -e MYSQL_ROOT_PASSWORD=test -d mysql

That’s it! I hope you got a brief overview of Docker and containerization. Now it’s time to create and run your own containers.

The next step might be to run your developed application in it’s own container. You can find a bunch of tutorials on the Internet for that.

Increasing your productivity with Telegram and Node.js

Lars Wächter — Sun, 01 Mar 2020 14:49:32 +0000

This article was originally published on Medium.

Some time ago I searched for an easy way to establish a communication channel between a mobile device and a Node.js webserver. My goal was to exchange messages over this channel and receive information about the weather, public transportation and more.

For example I send the message /train and receive a response with realtime details about train departure times of preconfigured routes. So the Node.js server receives the incoming message, processes it and sends a response back to the client.

After doing some researches I finally came up with Telegram bots since they are very easy to setup and fit perfect to my needs. Besides sending text messages, you can also share data like images or audio recordings.

First of all, what exactly is a Telegram bot? Source

Bots are third-party applications that run inside Telegram. Users can interact with bots by sending them messages, commands and inline requests. You control your bots using HTTPS requests to our bot API.

So you simply send a message from your phone via Telegram and your webserver receives it over Telegram’s API.

Just to name some of the things you can use your own bot for. Whether just for you or for your friends as well:

Gathering weather information
Fetching arrival / departure times of public transportation
Receiving tweets, news, status updates
Sending automated messages
IoT

and so much more.

One big benefit of Telegram bots is that you don’t need a public server which is accessible over an IP-address from outside the network. In my case I use a Raspberry Pi to run the Node application for example.

Since the communication takes place over the Telegram API, there’s just an internet connection required.

For interacting with it you can use a runtime environment like Node.js as I did in the example app below or any other programming languages.

Here you can find an introduction about how to interact with the API.

As I mentioned above I recently created an example app for a Telegram bot server based on Node.js. Feel free to use it for your own bot and customize it according to your wishes or contribute to it.

Let me know what you use your bot for and share your experience!

larswaechter / telegram-bot-server

An extendable webserver for communication with the Telegram Bot API.

telegram-bot-server

An extendable webserver for communication with the Telegram Bot API.

Description

telegram-bot-server is a Node.js powered webserver with MongoDB integration for running your own Telegram Bot as well as a REST API. With the help of Telegram bots you can do quite a lot of useful things.

Just to give some examples:

Gathering weather information based on your location
Fetching arrival / departure times of public transportation
Sending automated messages
IoT

You can make your bot public for other users or just use it for private purposes.

This application provides one example bot command (ping) innately but you can easily integrate your own ones into the current system.

See the Commands section for more information.

Prerequisites

Node.js
MongoDB
Telegram Bot
Internet connection

Installation

First of all, create a new MongoDB database:

use telegram-api-server

Afterwards, copy the environment file and enter your secret information:

cp .env.example .env

Now…

View on GitHub

Unit Tests for Node.js APIs built with TS, Express.js and TypeORM

Lars Wächter — Wed, 08 Jan 2020 19:27:06 +0000

This post was originally published on my blog.

Some days ago I wrote an article about how I structure my Node.js REST APIs. However, I didn’t cover any test scenarios in there. So it’s time to catch up on this now.

We’re going to write an unit test for a single API component based on the project structure from my other article. The goal is to test the component by mocking a database and sending an HTTP request to its routes.

For writing tests I use the following node modules:

Mocha
Chai
Supertest

Project structure

This is the project structure I mentioned above. Of course, you can use any other as well.

nodejs-api-structure
└───src
   │
   └───config
   │
   └───api
   │   │
   │   └───components
   │   │   │
   │   │   └───user
   │   │       │   controller.ts
   │   │       │   model.ts
   │   │       │   routes.ts
   │   │       │   service.ts
   │   │       │   user.spec.ts
   │   │
   │   └───middleware
   │   │
   │   │   routes.ts
   │   │   server.ts
   │
   └───test
   │   │   factory.ts
   │
   │   index.ts

We'll focus on the following files:

factory.ts
user.spec.ts

Test Factory (factory.ts)

This file is some kind of a setup file for each single unit test. It takes care of the database connection and starts the Express.js server.

We use ‘sqljs’ as database type, so it’s not necessary to provide a real database like MySQL or any other.

The code should be self explanatory. The class acts like a container for the database connection and express server. It provides getter methods to make them accessible and a method to open / close the connections.

import 'reflect-metadata';
import 'source-map-support/register';
import 'module-alias/register';

// Set env to test
process.env.NODE_ENV = 'test';

// Set env variables from .env file
import { config } from 'dotenv';
config();

import { createConnection, ConnectionOptions, Connection } from 'typeorm';
import { createServer, Server as HttpServer } from 'http';

import express from 'express';
import supertest from 'supertest';

import { env } from '@config/globals';

import { Server } from '../api/server';

/**
 * TestFactory
 * - Loaded in each unit test
 * - Starts server and DB connection
 */

export class TestFactory {
    private _app: express.Application;
    private _connection: Connection;
    private _server: HttpServer;

    // DB connection options
    private options: ConnectionOptions = {
        type: 'sqljs',
        database: new Uint8Array(),
        location: 'database',
        logging: false,
        synchronize: true,
        entities: ['dist/api/components/**/model.js']
    };

    public get app(): supertest.SuperTest<supertest.Test> {
        return supertest(this._app);
    }

    public get connection(): Connection {
        return this._connection;
    }

    public get server(): HttpServer {
        return this._server;
    }

    /**
     * Connect to DB and start server
     */
    public async init(): Promise<void> {
        this._connection = await createConnection(this.options);
        this._app = new Server().app;
        this._server = createServer(this._app).listen(env.NODE_PORT);
    }

    /**
     * Close server and DB connection
     */
    public async close(): Promise<void> {
        this._server.close();
        this._connection.close();
    }
}

Component test (user.spec.ts)

This file covers the unit test for the API component. In there, we use different HTTP request methods like POST, PUT, GET and DELETE to test the component’s API endpoints.

First of all, we create a new instance of the TestFactory class and User model. The mockTestUser methods returns an instance of User including some dummy data. Moreover we create another instance testUserModified with some modified properties which will be used to test the PUT endpoints.

const factory: TestFactory = new TestFactory();
const testUser: User = User.mockTestUser();
const testUserModified: User = { ...testUser, firstname: 'testFirstnameModified', lastname: 'testLastnameModified' };

Now we define Mocha’s before and after methods. before is executed before the test starts and after is executed after the test has ended.

Inside them we call the factory’s init and close method which establish a new database connection and express server before the test starts and disconnects from it when he has ended.

before(async () => {
    await factory.init();
});

after(async () => {
    await factory.close();
});

One important thing to notice is when you have multiple unit tests, that each test establishes a new database connection and express server.

For making HTTP requests to the server I use Supertest and Chai for validating the server responses.

Here's the complete code for one component:

import 'module-alias/register';

import { assert } from 'chai';

import { User } from './model';
import { TestFactory } from '../../../../test/factory';

describe('Testing user component', () => {
    // Create instances
    const factory: TestFactory = new TestFactory();
    const testUser: User = User.mockTestUser();
    const testUserModified: User = { ...testUser, firstname: 'testFirstnameModified', lastname: 'testLastnameModified' };

    before(async () => {
        await factory.init();
    });

    after(async () => {
        await factory.close();
    });

    describe('POST /users', () => {
        it('responds with status 400', (done) => {
            factory.app
                .post('/api/v1/users')
                .send()
                .set('Accept', 'application/json')
                .expect('Content-Type', /json/)
                .expect(400, done);
        });

        it('responds with new user', (done) => {
            factory.app
                .post('/api/v1/users')
                .send({
                    user: testUser
                })
                .set('Accept', 'application/json')
                .expect('Content-Type', /json/)
                .expect(200)
                .end((err, res) => {
                    try {
                        if (err) throw err;

                        const { status } = res.body;
                        const user: User = res.body.data;

                        // Assert status
                        assert(status === res.status, 'status does not match');

                        // Assert user
                        assert.isObject(user, 'user should be an object');
                        assert(user.id === testUser.id, 'userID does not match');
                        assert(user.email === testUser.email, 'userEmail does not match');
                        assert(user.firstname === testUser.firstname, 'userFirstname does not match');
                        assert(user.lastname === testUser.lastname, 'userLastname does not match');

                        return done();
                    } catch (err) {
                        return done(err);
                    }
                });
        });
    });

    describe('PUT /users/1', () => {
        it('responds with updated user', (done) => {
            factory.app
                .put('/api/v1/users/1')
                .send({
                    user: testUserModified
                })
                .set('Accept', 'application/json')
                .expect('Content-Type', /json/)
                .end((err, res) => {
                    try {
                        if (err) throw err;

                        const { status } = res.body;
                        const user: User = res.body.data;

                        // Assert status
                        assert(status === res.status, 'status does not match');

                        // Assert user
                        assert.isObject(user, 'user should be an object');
                        assert(user.id === testUserModified.id, 'userID does not match');
                        assert(user.email === testUserModified.email, 'userEmail does not match');
                        assert(user.firstname === testUserModified.firstname, 'userFirstname does not match');
                        assert(user.lastname === testUserModified.lastname, 'userLastname does not match');

                        return done();
                    } catch (err) {
                        return done(err);
                    }
                });
        });
    });

    describe('GET /users', () => {
        it('responds with user array', (done) => {
            factory.app
                .get('/api/v1/users')
                .set('Accept', 'application/json')
                .expect('Content-Type', /json/)
                .expect(200)
                .end((err, res) => {
                    try {
                        if (err) throw err;

                        const { status } = res.body;
                        const users: User[] = res.body.data;

                        // Assert status
                        assert(status === res.status, 'status does not match');

                        // Assert users
                        assert.isArray(users, 'users should be an array');
                        assert(users[0].id === testUserModified.id, 'userID does not match');
                        assert(users[0].email === testUserModified.email, 'userEmail does not match');
                        assert(users[0].firstname === testUserModified.firstname, 'userFirstname does not match');
                        assert(users[0].lastname === testUserModified.lastname, 'userLastname does not match');

                        return done();
                    } catch (err) {
                        return done(err);
                    }
                });
        });
    });

    describe('GET /users/1', () => {
        it('responds with single user', (done) => {
            factory.app
                .get('/api/v1/users/1')
                .set('Accept', 'application/json')
                .expect('Content-Type', /json/)
                .expect(200)
                .end((err, res) => {
                    try {
                        if (err) throw err;

                        const { status } = res.body;
                        const user: User = res.body.data;

                        // Assert status
                        assert(status === res.status, 'status does not match');

                        // Assert user
                        assert.isObject(user, 'user should be an object');
                        assert(user.id === testUserModified.id, 'userID does not match');
                        assert(user.email === testUserModified.email, 'userEmail does not match');
                        assert(user.firstname === testUserModified.firstname, 'userFirstname does not match');
                        assert(user.lastname === testUserModified.lastname, 'userLastname does not match');

                        return done();
                    } catch (err) {
                        return done(err);
                    }
                });
        });
    });

    describe('DELETE /users/1', () => {
        it('responds with status 204', (done) => {
            factory.app
                .delete('/api/v1/users/1')
                .set('Accept', 'application/json')
                .expect(204, done);
        });

        it('responds with status 404', (done) => {
            factory.app
                .delete('/api/v1/users/1')
                .set('Accept', 'application/json')
                .expect(404, done);
        });
    });
});

That's it! I hope this is a little help for people who struggle with writing unit tests for REST APIs built with Express.js and TypeORM.

I'm currently working on a side project where some components cover unit test as I described here. Have a look! at the 'user' or 'task' component for example.