Talk: Yin-Yang Puzzles are NP-complete

This repository contains slides for a talk given by Erik Demaine and Jayson Lynch about our CCCG 2021 paper "Yin-Yang Puzzles are NP-complete" by Erik Demaine, Jayson Lynch, Mikhail Rudoy, and Yushi Uno.

You can watch the video or read the paper for more details about the results.

Watch Video

View Slides

Technology: reveal.js + Pug + Stylus + CoffeeScript + SVG Tiler + SVG.js + KaTeX

This repository uses the reveal-pug-talk template to make slides by combining the following technology (all free and open source):

• reveal.js: a flexible HTML presentation framework, extendable by plugins and themes. Here we use:
  • Chalkboard: enables live drawing annotation on the slides (using pen or touch or mouse)
  • Merriweather font
• Pug: a concise indentation-based notation for HTML, which makes it easier to express reveal.js slides, and to mix together other languages. Here we use:
  • Stylus: a concise indentation-based notation for CSS (styling of HTML)
  • CoffeeScript: an indentation-based language that compiles to JavaScript
• SVG Tiler: a library for converting ASCII art into high-quality SVG graphics
• SVG.js: a library that makes it easy to interact with SVG drawings
• KaTeX: a library for translating LaTeX math into HTML
• Gulp: a tool that builds the Pug code into HTML

Structure

Here's an overview of the individual files and what they do:

• gulpfile.coffee: Definitions of build and watch rules that run Pug on index.pug.
• index.pug: Top-level Pug file that calls all other files. Defines the top-level structure of the document, but has no slides.
• slides.pug: Slides and specific animations are defined here.
• index.styl: Custom reveal.js styling and CSS layout tools.
• figures.coffee: code to convert ASCII art in slides.pug into SVG Tiler drawings (via class graph, for grid graphs) or interactive Yin-Yang puzzles (via class puzzle).
• yinyang.coffee: SVG.js-based code to make interactive Yin-Yang puzzles, copied from the Yin-Yang font.
• yinyang.styl: Styling for intearctive Yin-Yang puzzles, copied from the Yin-Yang font.
• TRVB_definition.svg: a figure illustrating vertex breaking in the TRVB problem.
• TRVB_input.svg: a sample instance of TRVB.
• TRVB_output.svg: a sample solution to TRVB.
• puzzle_cover.png: the cover of Puzzler issue #150.

Build Instructions

To build the slides HTML (index.html) from the source files:

1. Install NodeJS if you haven't already.

2. Clone the repository

3. Run the following:

   npm install
   npm run build

If you're live-editing the file and want index.html to continually build and update, use the following command:

npm run watch

To assemble just the needed files into a dist directory, use the following command:

npm run dist

To deploy these files to GitHub Pages, use the following command:

npm run deploy