• Name: bsoup
  Location: JP - Japan
  
  
• Name: Shinichiro Hamaji
  Location: JP - Japan

To build:

    make

To use:

    ./hamaji < a_nonogram_file

Try:

    ./try.sh

If you have perl installed you should be able to reproduce dragon.nono like:

    perl c2nono.pl hamaji.c | ./hamaji

Judges’ remarks:

This program solves Nonograms which is also known as “Paint by Numbers”.

This entry roars as the Year of the Dragon: A year considered by some to be good luck. Well it was certainly true that the IOCCC was lucky to get such a fine submission!

The source code is a solution to a Paint by Numbers puzzle when you paint by C. Try your hand at solving a few of the other .nono files and then compare your solution with this program!

NOTE: NONOGRAM (r) is a registered Trademark and is used with permission. See https://nonogram.com for more information.

Author’s remarks:

The format of the input files are as same as this site: https://web.archive.org/web/20130218055139/http://codegolf.com/paint-by-numbers.

For example, for a simple problem which shows a glider of Conway’s Game of Life:

       1
       .
      112

    1  X
    1   X
    3 XXX

the input should be

    1
    1
    3
    -
    1
    1.1
    2

The width and the height of an input puzzle should be less than or equal to 60.

When this solver finds the problem has no solution, it prints “invalid”. This means the problem is indeed broken. For example, this happens for an input like

    2
    -
    2

When this solver cannot find a solution, it prints “failed”. This failure can happen when the problem has more than one solution or the solver cannot solve the input problem. Here is an example input of the former:

    1
    1
    -
    1
    1

There are two solutions:

      11

    1 X
    1  X

and

      11

    1  X
    1 X

Detail

Solving Nonogram is NP-complete, so we cannot make a solver which solves all puzzles. However, we can write a solver which solves most problems solvable by humans. There are a bunch of ways to write such programs. The two most obvious approaches are:

1. Check all possible solutions with backtracking.
2. Implement all techniques which humans use.

The former, brute-force approach is easy to implement. However, it works only for smaller problems (width and height should be at most 30 or so). Similarly, using generic probabilistic metaheuristics such as simulated annealing doesn’t work for big problems.

See: http://ccl.northwestern.edu/netlogo/models/community/Nonogram.

By its definition, the latter method works for all human-solvable problems. The issue of the latter approach is this kind of program tends to be lengthy. This approach still requires some recursions. The most difficult problems which are considered human-solvable may require some “guesses”. For these kinds of problems, we need to assume a cell is a space or a box, go ahead some steps with simple methods and mark the tried cell as a box (or a space if we assumed the tried cell is a box) if a contradiction is found.

My program uses an approach like “Set based solver” introduced in https://wiki.haskell.org/Nonogram#Set_based_solver. This should be equivalent to the combinations of simple methods (no advanced reasoning with guess). My solver also runs a non-recursive guess for each undetermined cells. So, my program should be able to solve most human-solvable problems (assuming humans cannot execute deeper recursions).

Obfuscation

First of all, as you see, my program looks like a nonogram puzzle which results in a dragon. This puzzle is dragon.nono in this directory. Note that whitespaces in character literals, a string literal, and around the last comment are considered as a boxed cell.

My program is based on bit operations for speed. Many values are stored using negative logic (0 means on and 1 means off) to utilize the initial value of global variables. Thus, it might be difficult to figure out how it works.

My program is decently shortened, because the size of source code is limited by IOCCC’s rule (2048 non-whitespace characters) and a lot of characters are just wasted for numbers around the picture.

The three requirements (dragon, speed, and size) naturally ended up with the well obfuscated code.

Portability

This program uses two C99 features. One line comments and long long. GCC’s -ansi -pedantic check should pass:

    cc -ansi -pedantic -std=c99 hamaji.c

I checked my program with gcc-4.6.2 on linux, llvm-gcc-4.2 on Mac, and clang-3.0 on Mac.

Note that the behavior of scanf(3) differs on linux and mac, but this program supports both semantics.

This program should not depend on sizeof(int), sizeof(void*), ASCII, memory layout, undefined evaluation order (e.g., a[i++]=i), etc. This program won’t work if the size of long long literal is less than 8. By grepping the source code of gcc

    grep LONG_LONG_TYPE_SIZE gcc/config/*/*

I found long long may be 32bit integers only on AVR.

A few more things

This code is considered as a new year’s postcard in Japan. We chose the dragon because 2012 is the year of dragon.

The second author wrote the picture, and the first author did everything else.

The dragon.nono, samurai.nono, and penguin.nono were written by the second author. The soccer.nono was from a wikipedia entry. This file is important because it requires some guesses. The random.nono file was randomly generated. The codegolf.nono and face.nono were taken from https://web.archive.org/web/20130218055139/http://codegolf.com/paint-by-numbers.

You can reproduce dragon.nono from hamaji.c using c2nono.pl:

    perl c2nono.pl hamaji.c | ./hamaji

Primary files

• hamaji.c - entry source code
• Makefile - entry Makefile
• hamaji.orig.c - original source code
• c2nono.pl - perl script to reproduce dragon.nono
• codegolf.nono - nonogram input data
• conway-game-of-life.nono - nonogram input data
• dragon.nono - nonogram input data
• face.nono - nonogram input data
• multi-solutions.nono - nonogram input data
• no-solution.nono - nonogram input data
• penguin.nono - nonogram input data
• plus.nono - nonogram input data
• random.nono - nonogram input data
• samurai.nono - nonogram input data
• smiley.nono - nonogram input data
• soccer.nono - nonogram input data
• try.sh - script to try entry

Secondary files

• 2011_hamaji.tar.bz2 - download entry tarball
• README.md - markdown source for this web page
• .entry.json - entry summary and manifest in JSON
• .gitignore - list of files that should not be committed under git
• .path - directory path from top level directory
• index.html - this web page

Jump to: top