Motivation​

There are many interesting use cases out there for GitHub Actions. One of the main use cases is to create custom continuous integration (CI) workflows that are hosted and executed in your GitHub repository. I should add that that it's FREE for public repositories, with some usage limits/policies :)

With that introduction out of the way, here I am going to walk through a slightly more complex workflow that I am using in the open-source project MarkBind - A tool for generating static websites from Markdown-like syntax. P.S I am an active dev there so feel free to show your support by giving it a star or using it to create course/documentation websites today!

Requirements​

The reason why I would like to explain the workflow in detail here is that I think some requirements are fairly typical and it could serve as an example of a common CI script. Of course, the main reference that I would recommend is the official documentation by GitHub Also, this goes without saying that what I presented here is not the only way to do things.

So, let's talk about what I want the workflow to do:

• Run tests
  • Run it whenever someone makes a PR against the master branch
  • Run it in all major OSes
    • To ensure that it ain't just working on my machine
  • Also run it when a PR is merged, or when someone commits directly to the master branch
    • Sometimes senior devs might directly commit a quick fix to the master branch and this should still trigger the tests
• Deploy developer guide
  • Run it whenever a PR is merged, or when someone commits directly to the master branch
    • This is similar to the test runs but it is only triggered when a PR is merged (not when it is created)
    • The rationale for updating the developer guide per PR merge is so that our developer guide is always up-to-date with the latest development of the project, which could be slightly ahead of the released version
• Deploy user guide
  • Run it whenever we release a new version
    • Some context: when we release a new version we will push a tag of the master branch to GitHub. Hint: this is how we are going to trigger this step

Code​

Now we know the what, let me share the how. First, here's a brief summary of what we need to know about workflows:

• A workflow can have multiple jobs that can run sequentially or in parallel (this is the default)
• Each job can have multiple steps that run sequentially.
• Both jobs and steps can be configured to run under certain conditions.

Test​

So to achieve just what we need for the test, we can do something like this:

name: CI
on:
  push:
    branches:
      - master
  pull_request:
    branches:
      - master
jobs:
  test:
    strategy:
      matrix:
        platform: [ubuntu-latest, macos-latest, windows-latest]
    runs-on: ${{ matrix.platform }}

    steps:
      - uses: actions/checkout@v2
      - uses: actions/setup-node@v2
        with:
          node-version: '12'
      - run: npm i -g npm@8.3.1
      - run: npm run setup
      - run: npm run test

Some explanations of the syntax used:

• on.push.branches says that the workflow is only triggered when pushing to master, which is what happens when a PR is merged
• on.pull_request says that the workflow will run when someone sends over a PR, which is nice to ensure that the changes don't break the build
• the use of strategy and matrix is pretty much boilerplate code that is used to specify that the job named test will run on all three OSes.
  • This will run the tests in Ubuntu, macOS, and Windows, in parallel. It will by default fail-fast to stop the other two test runs if one of them failed unexpectedly.

Dev Guide​

To achieve just what we need for the developer guide update, we can do something like the following:

name: CI
on:
  push:
    branches:
      - master
jobs:
  deploy-docs:
    # disabled on forks
    if: github.repository == 'MarkBind/markbind'
    runs-on: ubuntu-latest
    env:
      GITHUB_TOKEN: ${{ secrets.GH_TOKEN }}
	steps:
      - uses: actions/checkout@v2
      - uses: actions/setup-node@v2
        with:
          node-version: '12'
      - run: npm i -g npm@8.3.1
      - run: npm run setup
      - name: Deploy DG on any commit to master, to markbind.org/devdocs
        run: >-
          npm run build:web &&
          npm run build:dg &&
          npm run deploy:dg

Now we reach the fun part... how to include the above with the test job so that it only runs when all tests have passed?

Here's my approach:

# code for test job omitted
deploy-docs:
    needs: test
    # disabled on forks
    if: github.event_name == 'push' && github.repository == 'MarkBind/markbind'
    runs-on: ubuntu-latest
    env:
      GITHUB_TOKEN: ${{ secrets.GH_TOKEN }}
	steps:
      - uses: actions/checkout@v2
      - uses: actions/setup-node@v2
        with:
          node-version: '12'
      - run: npm i -g npm@8.3.1
      - run: npm run setup
      - name: Deploy DG on any commit to master, to markbind.org/devdocs
        run: >-
          npm run build:web &&
          npm run build:dg &&
          npm run deploy:dg

There is quite a bit of stuff here, so here's a summary:

• I have defined another job named deploy-docs
• I specified it to only run if the previous job test is done and successful by doing needs: test
• I added a check to ensure that this job, unlike the test, will not run for pending PRs.
  • if: github.event_name == 'push' && github.repository == 'MarkBind/markbind'
  • it first checks if it is a push event (and not PR)
  • it then checks if the repository is the root repository
    • this is added to ensure that forks of the repo do not execute this job because they have no permission/access to publish the developer/user guides.

The rest is just set up and deploy commands that you may ignore.

User Guide​

Lastly, let's deal with the user guide which only needs to run per release.

To achieve just what we need for the user guide update, we can do something like the following:

name: CI
on:
  push:
    branches:
      - master
    tags:
      - 'v[0-9]+.[0-9]+.[0-9]+'
jobs:
  deploy-docs:
    # disabled on forks
    if: github.repository == 'MarkBind/markbind'
    runs-on: ubuntu-latest
    env:
      GITHUB_TOKEN: ${{ secrets.GH_TOKEN }}
    steps:
      - uses: actions/checkout@v2
      - uses: actions/setup-node@v2
        with:
          node-version: '12'
      - run: npm i -g npm@8.3.1
      - run: npm run setup
      - name: Deploy UG on release, to markbind.org
        if: github.ref_type == 'tag'
        run: >-
          npm run build:ug &&
          npm run deploy:ug

To integrate it into the entire workflow, the following changes are required (full script at the end):

name: CI
on:
  push:
    branches:
      - master
    tags:
      - 'v[0-9]+.[0-9]+.[0-9]+'
  pull_request:
    branches:
      - master

	# some code in between
	 - name: Deploy UG on release, to markbind.org
        if: github.ref_type == 'tag'
        run: >-
          npm run build:ug &&
          npm run deploy:ug

• The addition of on.push.tags ensures that when a new tag on the master branch is pushed to GitHub, as part of making a new release, will trigger the workflow.
  • This runs the test job and the developer guide deployment step as well.
    • It could easily be turned off such that only the user guide step is run.
  • the v[0-9]+.[0-9]+.[0-9]+ is a glob pattern to match semantic versioning tags.
• The if: github.ref_type == 'tag' in the user guide step will ensure that if this is just a PR merge or a push event to master, the step will be skipped.
  • The details of the github object that I am accessing here is available here

Full Script​

Putting everything together:

name: CI
on:
  push:
    branches:
      - master
    tags:
      - 'v[0-9]+.[0-9]+.[0-9]+'
  pull_request:
    branches:
      - master
jobs:
  test:
    strategy:
      matrix:
        platform: [ubuntu-latest, macos-latest, windows-latest]
    runs-on: ${{ matrix.platform }}

    steps:
      - uses: actions/checkout@v2
      - uses: actions/setup-node@v2
        with:
          node-version: '12'
      - run: npm i -g npm@8.3.1
      - run: npm run setup
      - run: npm run test
  deploy-docs:
    needs: test
    # disabled on forks
    if: github.event_name == 'push' && github.repository == 'MarkBind/markbind'
    runs-on: ubuntu-latest
    env:
      GITHUB_TOKEN: ${{ secrets.GH_TOKEN }}

    steps:
      - uses: actions/checkout@v2
      - uses: actions/setup-node@v2
        with:
          node-version: '12'
      - run: npm i -g npm@8.3.1
      - run: npm run setup
      - name: Deploy DG on any commit to master, to markbind.org/devdocs
        run: >-
          npm run build:web &&
          npm run build:dg &&
          npm run deploy:dg
      - name: Deploy UG on release, to markbind.org
        if: github.ref_type == 'tag'
        run: >-
          npm run build:ug &&
          npm run deploy:ug

Conclusion​

Now that CI script is written and workflow is automated, robots can finally take my job.

NUS CS3240 Design Task 6: Apartment Hunting (Application)

You and your friends have come together to build an application that provides location rankings for people looking to rent an apartment/room both long-term or short-term. You are designated as the designer for the team and you are tasked to come up with screens, allowing people to find apartments based on their needs, and also liaise with the owners.

Solution

I decided to dedicate an entire website to host the design assets and the complete write-up of the design process. You can find it here:

https://tlylt.github.io/roofind/ (Build with MarkBind)

P.S. My proof attempt/rewrite based on the solution discussed, uploaded mainly for my own reference. (warning: possibly erroneous)

Claim: The problem of determining whether a graph is connected is evasive​

• evasive as in it requires n C 2 queries i.e checking all the edges
• Prove by making an adversary argument

1. Suppose M is an algorithm that makes m < (n C 2) queries to decide whether the graph is connected
2. The adversary responds to each query as follows:
   • suppose it receives the x th query for 1 <= x <= m
   • it considers the graph x defined by taking
     • all the responses before this query (those that have reply of 1 => those edges that exist)
     • all unqueried edges are set to 1 and hence considered as exist
     • the current queried edge is set to 0 and hence not included
   • if this graph is still connected without the current edge, then the adversary replies 0, else replies 1
     • it's like if the graph does not need the current edge to be fully connected, then return 0
3. After all m queries, there are
   • responses for previously queried edges, which can be 1 or 0
   • one unqueried edge that is unknown
4. The adversary makes two graphs using the above information:
   • G0: take all edges that are connected according to the responses + set the unqueried edge to 0 (ignore the unknown edge)
   • G1: take all edges that are connected according to the responses + set the unqueried edge to 1 (include the unknown edge)
5. M cannot distinguish between G0 and G1 because both are consistent with its queries.
6. The argument is that G0 is disconnected while G1 is connected, and hence since M can only decide whether the graph is connected or not, M must be wrong for one of the above inputs.
7. G1 is connected trivially because it is consistent with the adversary's response strategy.
   • If you set the unqueried edges to 1, then the graph must be connected (together with those edges that exist, i.e. previously answered 1)
8. G0 is disconnected by contradiction:
   • Suppose G0 is connected for purpose of contradiction
   • Then let (i, j) = the last unqueried pair of nodes be connected, i.e there is a path between i and j
   • Given the adversary strategy, it must replied 1 to all edges on this path, because they exist
   • let (i', j') be the edge on this path that was queried last. Then the adversary should have answered 0 as i and j will be set as connected since they are unqueried at that point.
   • So a contradiction arises and the assumption is incorrect.

Concrete Example​

• n = 3

• Since the algorithm is going to decide whether the graph is connected or not, the adversary simply takes the input that is not consistent with the algorithm.