Forem: VojtechP

Tower of Hanoi

VojtechP — Sun, 01 Mar 2020 09:08:34 +0000

Yesterday I wanted to try code some challenge. I chose the Tower of Hanoi.

Rules

Tee goal is to move discs from left tower to right tower with those rules:

Only one disc can be moved at the time
Each move moves the upper disc to another tower
Disc can't be put on a smaller disc

Tower data structure

Because in every move you must take a top disc and put it as a top disc on another tower, the tower is stack.

class Tower {
  constructor(stack, level) {
    this._stack = stack || new Array();
    this._level = level || 0;
  }

  push(value) {
    const { length } = this._stack;

    if (length && value > this._stack[length - 1]) {
      throw new TypeError(
        `Could not put bigger disk(${value}) on smaller(${
          this._stack[length - 1]
        })`
      );
    }

    this._stack.push(value);
  }

  pop() {
    if (this.isEmpty()) {
      throw new TypeError("Tower is empty");
    }

    return this._stack.pop();
  }

  isEmpty() {
    return this.getSize() <= 0;
  }

  getSize() {
    return this._stack.length - this._level;
  }

  getUpperTower() {
    return new Tower(this._stack, this._level + 1);
  }

  toArray() {
    return [...this._stack];
  }
}

Explanation

this._stack is an array that works as an inner stack.
this._level is level where tower starts.

In the algorithm, I will need to create sub towers without lower levels that share stack but start at different levels.

In the push method, I test if I am not putting a smaller disc on a bigger one and in the pop method I could not pop from an empty tower.

Methods isEmpty and getSize reflects the level where the tower starts.

Method getUpperTower returns the same tower that starts at a higher level.

And the last method toArray return stack as array from bottom to top for printing tower to console.

Solution

For the solution, I created a class TowerOfHanoi that creates the source tower with discs from n to 1 and two empty towers.

Method _print prints tower. Method solve is used to solve this puzzle.

Method _solve is a place where I will explain and implement a solution.

class TowerOfHanoi {
  constructor(size) {
    this._destinationTower = new Tower();
    this._sourceTower = new Tower();
    this._temporaryTower = new Tower();

    this._printLength = String(size).length;

    for (let i = size; i > 0; i--) {
      this._sourceTower.push(i);
    }
  }

  _print() {
    const destinationArray = this._destinationTower.toArray();
    const sourceArray = this._sourceTower.toArray();
    const temporaryArray = this._temporaryTower.toArray();
    const arrays = [sourceArray, temporaryArray, destinationArray];
    const maxHeight = Math.max(
      ...[destinationArray.length, sourceArray.length, temporaryArray.length]
    );

    console.log("");

    for (let i = maxHeight - 1; i >= 0; i--) {
      const row = arrays
        .map(array => String(array[i] || "").padStart(this._printLength, " "))
        .join(" | ");

      console.log(`| ${row} |`);
    }

    console.log("_".repeat(3 * this._printLength + 10));
  }

  _solve({ destinationTower, sourceTower, temporaryTower }) {}

  solve() {
    this._print();

    this._solve({
      destinationTower: this._destinationTower,
      sourceTower: this._sourceTower,
      temporaryTower: this._temporaryTower
    });
  }
}

Base case

If the source tower contains only 1 disc, the solution is moving this disc to the destination tower and the puzzle is solved.

_solve({ destinationTower, sourceTower, temporaryTower }) {
  if (sourceTower.getSize() == 1) {
    destinationTower.push(sourceTower.pop());

    this._print();

    return;
  }
}

This works for size == 1.

Move upper discs

If all upper discs are move to the temporary tower then is possible to move the biggest disc to the destination tower.

Moving the upper disc to the temporary tower is the same as solving this puzzle for moving the source tower containing discs without the lowest disc to temporary disc.

The new source tower is the upper tower of the actual source tower that starts one level higher. The destination and temporary tower are exchanged.

_solve({ destinationTower, sourceTower, temporaryTower }) {
  if (sourceTower.getSize() == 1) {
    destinationTower.push(sourceTower.pop());

    this._print();

    return;
  }

  this._solve({
    destinationTower: temporaryTower,
    sourceTower: sourceTower.getUpperTower(),
    temporaryTower: destinationTower
  });

  destinationTower.push(sourceTower.pop());

  this._print();
}

This works for sizes 1 and 2.

Last step

After these steps, the source tower is empty, the temporary tower contains discs from n-1 to 1 and the destination tower contains n.

It looks like an original puzzle, but the source and the temporary towers are swapped. Because the destination tower contains only the biggest disc it is possible to ignore this disc and solve it as an original puzzle for n-1.

_solve({ destinationTower, sourceTower, temporaryTower }) {
  if (sourceTower.getSize() == 1) {
    destinationTower.push(sourceTower.pop());

    this._print();

    return;
  }

  this._solve({
    destinationTower: temporaryTower,
    sourceTower: sourceTower.getUpperTower(),
    temporaryTower: destinationTower
  });

  destinationTower.push(sourceTower.pop());

  this._print();

  this._solve({
    destinationTower: destinationTower.getUpperTower(),
    sourceTower: temporaryTower,
    temporaryTower: sourceTower
  });
}

Hot reloaded Apollo server: Dockerization

VojtechP — Tue, 25 Feb 2020 15:36:05 +0000

Photo by Dimitry Kooijmans on Unsplash

This is my second post and the second part of a hot reload demonstration.

Production docker image

dockerfile

FROM node:12-alpine

WORKDIR /app

RUN npm install -g webpack webpack-cli

COPY ./package*.json ./
RUN npm install

COPY ./src ./src
COPY ./webpack.*.js ./

RUN npm run build

EXPOSE 8080

CMD [ "npm", "start" ]

Build image:docker build . -t apollo-server-hot-reload-example
and run container: docker run -p 8080:8080 apollo-server-hot-reload-example

Development webpack config

For running a server I will need a webpack plugin start-server-webpack-plugin. But because there is a bug in the latest version I will use version 3.0.0-rc3.

Restart on every rebuild #30

antonyisoardi posted on Oct 04, 2018

Not so sure if anyone else has experienced this, BUT!... I've noticed that the server is only being restarted on every second rebuild.

Rebuilds are successful every time, however in order for me to get the server restarted I have to make a second change.

View on GitHub

npm i -D start-server-webpack-plugin@3.0.0-rc3

webpack.development.js

const path = require("path");

const cleanWebpackPlugin = require("clean-webpack-plugin");
const merge = require("webpack-merge");
const nodeExternals = require("webpack-node-externals");
const StartServerPlugin = require("start-server-webpack-plugin");
const webpack = require("webpack");

const common = require("./webpack.common");

module.exports = merge.smart(common, {
  devtool: "inline-source-map",
  entry: ["webpack/hot/poll?1000", path.join(__dirname, "src/index.js")],
  externals: [
    nodeExternals({
      whitelist: ["webpack/hot/poll?1000"]
    })
  ],
  mode: "development",
  plugins: [
    new StartServerPlugin({
      name: "server.js",
      nodeArgs: ["--inspect"],
      signal: true
    }),
    new cleanWebpackPlugin.CleanWebpackPlugin(),
    new webpack.HotModuleReplacementPlugin()
  ],
  watch: true
});

Next, I will add a script to build dev version: "build:dev": "webpack --config webpack.development.js"

Development docker image

The difference between production and development docker image is in command. The development image needs volume to share the source with host machine.

dev/dockerfile

FROM apollo-server-hot-reload-example

# dev volume
VOLUME /app

CMD [ "npm", "run", "build:dev" ]

Because there are changes that influence production image I must rebuild it again.
docker build . -t apollo-server-hot-reload-example
And finally, I can build development image.
docker build dev -t apollo-server-hot-reload-example-dev

Run development docker container

After I run this command:

docker run -p 8080:8080 -v *absolute_path_to_project*:/app apollo-server-hot-reload-example-dev

where *absolute_path_to_project* is the absolute path to project request return same string like in production mode. After code change, webpack rebuilds code and restarts server.

VojtechP / apollo-server-hot-reload-example

apollo-server-hot-reload-example

Example repo for hot reaload Apollo server in docker container used for dev.to posts part1 and part 2

View on GitHub

Hot reloaded Apollo server: Introduction

VojtechP — Mon, 24 Feb 2020 17:58:05 +0000

Photo by Dan Wayman on Unsplash

This is my first post on dev.to. For some time I wanted to build Apollo server with hot reload. Many attempts failed, but I recently found webpack plugin that helped me. In this short series, I will demonstrate that.

Init and clear package.json

npm init

After that, I cleaned up package.json and added .gitignore.

Install dependencies and create demo app

npm i apollo-server graphql

src/resolvers/index.js

export default {
  Query: {
    testMessage() {
      return "Hello World!";
    }
  }
};

src/typeDefs/index.js

import { gql } from "apollo-server";

export default gql`
  type Query {
    testMessage: String!
  }
`;

src/index.js

import { ApolloServer } from "apollo-server";

import resolvers from "./resolvers";
import typeDefs from "./typeDefs";

const server = new ApolloServer({ resolvers, typeDefs });

server.listen(process.env.GRAPHQL_PORT || 8080).then(({ url }) => {
  console.log(`Server ready at ${url}`);
});

if (module.hot) {
  module.hot.accept();
  module.hot.dispose(() => {
    console.log("Module disposed");
  });
}

Production webpack config

Install dev dependencies:
npm i -D npm i -D webpack webpack-cli clean-webpack-plugin webpack-merge webpack-node-externals

webpack.common.js

const path = require("path");

module.exports = {
  output: {
    filename: "server.js",
    path: path.resolve(__dirname, "dist")
  },
  resolve: {
    extensions: [".js"]
  },
  target: "node"
};

webpack.production.js

const path = require("path");

const cleanWebpackPlugin = require("clean-webpack-plugin");
const merge = require("webpack-merge");
const nodeExternals = require("webpack-node-externals");

const common = require("./webpack.common");

module.exports = merge.smart(common, {
  devtool: "source-map",
  entry: [path.join(__dirname, "src/index.js")],
  externals: [nodeExternals({})],
  mode: "production",
  plugins: [new cleanWebpackPlugin.CleanWebpackPlugin()]
});

And finally add this script to package.json

"build": "webpack --config webpack.production.js",
"start": "node dist/server.js"

Test run

Next step is build app:
npm run build
and test run:
npm start

After that, you can open your browser at http://localhost:8080/ and try out this query:

query {
  testMessage
}

Next part

In the next part, I will dockerize app.

VojtechP / apollo-server-hot-reload-example

apollo-server-hot-reload-example

Example repo for hot reaload Apollo server in docker container used for dev.to posts part1 and part 2

View on GitHub