Thursday, May 25, 2017

Nice Code Blocks in Blogger

This post is mostly for my own use, but I figure some others might like it, too.  You may have noticed that I have some nice code blocks in some of my posts.  I may start with something like:

function(args)
{
    if ( maybe ) do_something();
}

(I set the font to offset the above code using the font-selector make it stand out a bit.)

How to I get those nice looking blocks?

To start, I use a site to format the blocks:

http://hilite.me/

That generates HTML that I can paste into my post.  When editing, normally you're in "compose" mode, but near the top left, you can hit "HTML" to get into the raw code of the page.  I just paste the results from the web page.  Make sure you don't put it in the middle of a <div></div> pair.  I often put a lone line of text where I want to paste into the page to make it easy to find.  Something like this:

==========PASTE_CODE_BLOCK_HERE==========

So doing that, now I have this:

function(args)
{
    if ( maybe ) do_something();
}

After that, I hit "preview."  There I'll see that with a white background, I see lots of off-white text on white.  Not good.  (This is because my normal page style is light text on dark, and the highlighter page assumes you have dark text on light and doesn't override it.)  At the top of the HTML block I paste in, there are some HTML style options separated by semicolons.  I need to add in, "color:black;" to correct the color issue:

function(args)
{
    if ( maybe ) do_something();
}

That's nice, but I don't like that it highlights spaces.  This is a simple matter of removing the "<span ...> </span>" tags around the spaces.  But wait, there's a reason those are there: it's based on where I'm pasting from.  If I'm pasting from a web page with formatting, some of that is getting picked up by the highlighter.  As a general rule, never paste into Blogger from a web page or formatted document--it will mess up all sorts of things.  I have to make sure I'm posting raw ASCII text if I want a nice clean block of code.  So going back to the original code, pasting it first into a text editor, and then into the highlighter, and editing the default text color:

function(args)
{
    if ( maybe ) do_something();
}

So there's just one change, but to be sure I remember it and to make it easy, I'll save a one-line command line for fixing things.  I toss in stripping out stray blank lines.  Since I want to buffer all the input before printing the output, I'll pipe the output to a tail command.  I then add a final comment line and a blank line to keep things easier to follow when editing the page:

sed -e 's/border: *solid gray/&;color:black/' |
    grep -v '^$' |
    tail -n 10000 ; \
    echo '<!-- END HTML generated using hilite.me -->'; \
    echo ''

One simple hint: You're free to leave blank lines in the HTML version of the page outside of the block generated by the web page.  This may make it simpler to find and update the blocks as needed, but Blogger sometimes removes them.  In any case, they're harmless.

Another thing to watch for is that the Blogger composer sometimes gets confused as to the line breaks around code blocks.  Always check the preview--there are often line breaks where the composer doesn't show them between your text and the code block.

For this post I used the "colorful" style.  I think I'll use "emacs" in most of my posts. Somehow that color scheme looks natural to me.

Thursday, May 4, 2017

Digital Rights Management (DRM) and Star Wars

Many of my friends have heard me complain (OK, rant) about DRM.  DRM officially stands for "digital rights management," but I prefer "digital restrictions management."  The most common use of DRM is for video like Blu Ray discs and Netflix.  DRM software enforces the restrictions imposed by the seller.  You only get to use the media in the way they intended, no matter how much money you spent to buy it.  You don't fully own that disc you just bought.  Want to skip the previews?  Sorry.  Want to skip the copyright notice?  No way.

Of course, DRM doesn't stop the professional copiers.  People in various countries will take one legal disc and press duplicates that are completely identical, bypassing all the copy protections.  DRM value: zero.  Semi-professional pirates find various ways of bypassing the protection, including ripping from the HDMI output with hacks to remove the copy protection there, and then they share the videos online.  DRM value: none.  Regular owners who want to copy the movie to their iPad to watch in the car can't.  Yes, some discs offer alternatives that may or may not work offline.  DRM value: consumers annoyed.

But let's look at the worst impact of DRM ever:  Star Wars.

In particular, have you ever wondered why Princess Leia had to send the Death Star plans with R2D2 instead of transmitting them to another ship?  Or why they never made copies and sent them with multiple courriers?  Clearly the plans were encumbered with the nastiest DRM ever invented.  Want to copy them?  No way.  Want to transmit them without destroying the original?  Nope, not allowed.  Want to analyze them to find a design flaw allowing you to destroy the Death Star using small fighters too small to be considered a serious threat?  No problem, but only if you watch the Imperial Secret Documents crawl first.

So remember, DRM isn't just about stopping those nasty consumers from watching movies they've legitimately purchased on multiple devices.  DRM is also about preserving the Empire.  Support DRM to help destroy the last vestiges of the Republic.

Happy Star Wars Day.  May the Fourth be with you.

Wednesday, July 6, 2016

Writing Telnet in Bash

Every so often, I find that I need to script some network connection.  For interactive jobs, the standard answer is to use 'telnet' with 'expect' to achieve this.  Unfortunately, expect is often a major pain to work with.  The obvious modern solution would be to use Python, but I haven't learned that yet.  What I do know is Bash, and wouldn't it be cool to do this entirely in Bash?  So to prove that this works, I decided to write a simple telnet client entirely in Bash.  If I can write telnet in Bash, I can extend it to manage the connection to do pretty much anything I want.

To make this work, I need to use the Bash network extensions.  Built into Bash is a virtual file system for creating network sockets: /dev/tcp/host/port.  Just open the file with the appropriate protocol/host/port, and you're good to go.  Be aware that while this was added in Bash 2.04, it's a compile-time option, and the version of Bash included with some distributions might not support this.

So obviously, I was able to get this to work, or I wouldn't be writing this.  Here's the script:


#!/bin/bash
#
# A Bash-only telnet client
#
# Options:
#   $1  host name
#   $2  port (default 23)
#

read_write_one_char()
{
    IFS=$'\n' # tell read to treat all non-newline characters the same
    while true; do
        read -r -n 1 -t 0.01 C
        STATUS=$?
        if [ ${STATUS} != 0 ]; then
            if [ ${STATUS} -gt 128 ]; then # Read returns 142 on timeout
                return 0 # Normal exit
            fi
            return 1 # EOF or other problem
        fi
        if [ -z "${C}" ]; then
            echo ""
        else
            echo -n "${C}"
        fi
    done
}

do_io()
{
    while true; do
        read_write_one_char 0<&3 || break
        read_write_one_char 1>&3 || break
    done
}

PORT="$2"
if [ -z "$PORT" ]; then
    PORT=23
fi
exec 3<>/dev/tcp/$1/${PORT}
do_io
exec 3>&-
exec 3<&-
So how does this work?

The last four lines have three uses of 'exec'.  The syntax of the 'exec' command is rather counterintuitive--it's essentially overloading the command with something that doesn't exec a new binary.  It's opening a socket for read and write to file descriptor 3, and then closing it when the work is done.  Note that while you open the socket for read and write with a single call, you have to close read and write separately.

The real work is in the function read_write_one_char().  This function uses the Bash built-in command 'read' to read one byte from stdin and copy it to stdout.  Here we run into some significant limitations in Bash for handling I/O.  I would like to be able to do a binary read into a string, the write it out, which is essentially what I'm doing.  Unfortunately, Bash tries really hard to be working with words separated by whitespace, not binary data.  The internal variable 'IFS' defines what it considers to be whitespace, so I have to override that to be just newline (using a Bash syntax for specifying non-ASCII constants).

The read command returns a non-zero status if it times out that is greater than 128 (142 in my testing, but I wouldn't rely on that).  If it returns any other non-zero status, the script assumes it's an end-of-file indication.

When echoing the character that was read out, we are again bitten by the shell's insistence on working with words and whitespace, so the script has to undo that by treating an empty read as having read whitespace (which is only a newline, having overridden IFS as mentioned above).

The read has a timeout of a hundredth of a second so that the same thread can switch between reading the console and the network.  It's within a loop, however, so that if a burst of characters comes in, it will read until it times out before switching to the other input.

That's it.

The script works rather nicely for simple tasks.  It could easily be extended to handle some things like \r\n sequences and things like that.  Extending it to read more than one character at a time would improve performance.  More importantly, it could easily save text read from the network for matching against patterns just like 'expect' does.

One thing that is particularly cool about this script is that it's all pure Bash.  Every command that it uses is built-in.  There is not a single subprocess being forked.  Just echo, read, test ([), and true.

Tuesday, February 16, 2016

Linux with LIRC Remote Controls

On May 11, 2000, I ordered our first DVR.  It was  a ReplayTV 2020, capable of recording 20 hours of TV on its 20GB hard drive.  We had previously used a VCR for recording several shows, but the DVR experience was so much better that we never even got around to watching some shows that we had previously recorded on VHS.  Five years later, we replaced the ReplayTV with MythTV.  I've refreshed the hardware, but the database has carried over, reporting that our first recording was on February 20, 2004 (and episode of CSI).

I could go on and on about how wonderful MythTV is, though I wouldn't recommend it unless you like to tinker with all sorts of Linux oddities to keep everything working just right.  One of those oddities is dealing with a remote control.  While you can use a wireless keyboard (which we do), it's often much nicer to use a standard universal remote.  Which brings us to the point of this post.

To receive IR signals, you need an IR receiver.  Today there are several USB-based solutions, including a programmable FLIRC device that remembers IR signals and converts them into the keystrokes of your choice.  While I would probably get one of those if I were starting fresh today, I have an old PVR-250 card that included an IR receiver.  I keep the card for digitizing VHS tapes, and take advantage of the IR receiver.

All was good, until my remote control suddenly died.  I tried new batteries.  No luck.  And of course the remote is no longer being made, as even something as standard as a universal remote has to be changed every few years, so I ended up ordering a new universal remote.

Programming a universal remote for use with MythTV should be fairly simple.  It doesn't really matter what codes the remote sends, as long as the computer can receive them, and as long as each button sends a different key.  Making this a little trickier, the receiver I have only parses the RC-5 protocol used by Philips.  So I set the remote to a code set for a Philips TV that sent signals on most of the buttons.  I managed to find another universal remote, and I programmed it to a different Philips code set, then used the learning mode on the new remote to program the remaining buttons so that each button sent a different signal.

To program the Linux side, there are three places to set up codes.  The kernel has a mapping of codes to key codes in the input layer.  LIRC has a mapping in /etc/lirc/lircd.conf, and applications have a mapping in ~/.lircrc.

Fortunately, the lircd.conf mapping can be ignored once it's set up, as the key code to symbol mapping is standard regardless of the remote.  While you still need the file, its purpose was to do the mapping now in the input layer for older drivers that didn't use that layer.

The ~/.lircrc file is where the real magic of using LIRC comes in.  If the remote worked like a keyboard, then all applications would see the same key for each button.  But with LIRC, you can set up different actions for a given button for each  program.  For example, you can tell MythTV that the PLAY button has the action of 'P' on the keyboard, while for Xine the same PLAY button has the action of the space bar.

The tricky part is setting up the initial mapping from remote codes to key symbols in the kernel.  For this, there's the input-utils package.  First, the 'lsinput' command told me that my remote was input 4.  Knowing this, I used 'input-events 4' to watch the raw scan codes for each button on the remote.  I found that a few were duplicates, so I had to use the learning mode to learn different codes for those buttons.

Then it should have been a simple matter of using 'input-kbd' to program a new set of mappings.  This program takes a mapping from scan codes to keyboard codes (which LIRC then passes on to the programs).  I had a file that mapped the codes for my previous remote, and even the remote from before that (which we went back to using briefly, despite some buttons not working on it).  I was able to add the codes for the new remote.  But that's when things fell apart.

Somehow, after sending the new mapping file to the kernel using input-kbd, displaying the active map would show that some buttons reverted back to a previous value.  I was absolutely convinced that I was doing everything correctly, so I was going to report this as a kernel bug.  In preparing to send the report, I ran input-kbd under strace so that I could cite the exact ioctls that were misbehaving, and much to my surprise, I saw that input-kbd was sending my mapping, followed by a bunch of old mappings.

So it was time to look at the source for input-kbd.

Since I use Gentoo Linux, I had the source already downloaded.  Looking at the source, and knowing the behavior I was seeing, the bug was fairly obvious.  The program was written assuming that anyone submitting a new mapping would want to remap all the same codes as the old map, so it read the old map, then overwrote it with the new map, but when sending the map back to the kernel, used the size of the original map.

So I wrote a patch to fix that bug.  I also took the time to allow comments in the input file (saving my init script having to strip them out with sed and grep before loading them).  Again, as a Gentoo user, I was able to put the patches in /etc/portage/patches/sys-apps/input-utils/, and now the patches are automatically applied whenever I install the package.

But being a responsible person, I also looked for a place to report the bug back to the developer.  The project is on Git Hub, but there is no issue tracker there or anywhere else that I could find.  So I resorted to emailing the developer, hoping that the published address was still valid.  I'm pleased to report that the patches got through and were immediately applied (with a few tweaks).  I've sent one more iteration of improvements, but hopefully when input-utils-1.2 is released, this bug will be gone.

So having done all that, I decided to take the remote apart and see what was wrong with it.  I pried it apart with a screwdriver.  It's just one circuit board with a single chip.  I couldn't see any indication of cracked solder or anything like that, so I put it back together.  I put the batteries back in, and...

The old remote works just fine.

Well, I learned a bit about how the mapping of remotes works in Linux, and I rather like the new remote.  In any case, I'll have something to switch to when the old one dies again.

Thursday, December 10, 2015

Portable Inline Assembly

This is a fun little tidbit.  Assembly language is, obviously, not portable.  If you use inline assembly code in a C program, you won't expect it to run on multiple processors without special handling for each one.  Well, there's an exception to that.

First, the trivial exception:

__asm__("");

That's valid code (assuming the gcc compiler, as I will throughout this discussion).  But it doesn't do anything, so it's rather pointless.  The magic comes in when you specify the input and output parameters.  For output, I'll specify two registers, assigned to the variables 'a' and 'b'.  For input, I'll use the same registers.  The syntax GCC uses is that zero is the first output register, and so-forth.  Note that you specify the output first.

__asm__("" \
 :"=r"(a), "=r"(b) \
 :"0"(b),"1"(a) );

Now this does something!  We've told it that the input is two registers with the values from variables 'b' and 'a', and the output is the same two registers which are variables 'a' and 'b'.  Notice the order.  We've swapped two variables.  No intermediary storage.  No fancy xors.  No actual code.  What we've done is tell the compiler to swap it's notion of where 'a' and 'b' are stored (with both being registers).

We can make this into a fancy macro:

#define SWAP_ASM(_a,_b) __asm__("" \
    :"=r"(_a), "=r"(_b) \
    :"0"(_b),"1"(_a) );

And demonstrate that it works:

#include <stdio.h>

#define SWAP_ASM(_a,_b) __asm__("" \
    :"=r"(_a), "=r"(_b) \
    :"0"(_b),"1"(_a) );

int main(int argc,char *argv[])
{
   int a='a', b='b';
   (void)argc;(void)argv; // no "unused" warning
   SWAP_ASM(a,b);
   printf("a contains '%c'\n"
          "b contains '%c'\n",a,b);
   return 0;
}

Now admittedly, this isn't very useful.  If the variables aren't in registers, the compiler has to generate load and store instructions before and after the swap.  Using inline assembly can mess up optimization (probably more so in older releases), so using a variable to do a swap with all your code being in C is likely a better choice.  Still, a neat little hack.

Thursday, December 3, 2015

Scripting ssh passwords

One of the most powerful communications tools available is ssh.  Pretty much the only version on Linux is OpenSSH, and most of the versions I've come across on other platforms are derived from it.  I assume you know that, and I assume you also know that the best way to use it is with pre-shared keys so that you don't have to worry about passwords.  Unfortunately, that isn't always an option.

Recently I was working on a script that needed to use ssh to connect to an embedded system.  There are no keys on the remote system, so you have to use a password.  You can look the password up in a database.  Asking the user to do that and type it in manually would be a pain, and in this case, would add no security.

Openssh does everything it can to make scripting passwords difficult, which is only reasonable from a security standpoint.  But for anyone who has been around Unix systems for a while knows, there's a program called "expect" that solves the problem.  Expect allocates a pseudo TTY device, spawns a target program, and controls it through the TTY.  It can watch for prompts and issue responses, and it can eventually return control to the parent TTY, allowing a user to interact manually.

So I set up a script using expect to enter the password for ssh, and all was good.  I invited everyone else in my department to use the same script.  Most people loved it.  Then I started getting complaints.  It seems that while I would expect expect to be installed everywhere, that expectation was flawed.  I could ask everyone to install expect (and I did), but it seems that everyone is managing their own Linux systems, and many developers don't really know much about doing so.

I needed a better solution.

I found a better solution.

Ssh has a feature where it can run a GUI program to ask for a password.  That is exactly where we'll get our scripted password inserted.  This requires two things:  Set the environment variable SSH_ASKPASS to an executable that will write the password to stdout, and have the ssh process not be connected to a tty.

The first part is easy.  Just create a script that echos the password:

   echo echo $PW > /tmp/pw.$$
   chmod 700 /tmp/pw.$$

The second part is a little more tricky.  Also, it means that we can't interact with ssh once it connects.  Well, maybe we could with some additional trickery, but fortunately, my use of ssh didn't require interacting with it once the connection was established--I was just forwarding ports.  The obvious solution of redirecting stdin from /dev/null doesn't work, and neither does outright closing stdin.  The tty is part of a process state independent of the file descriptors, so we have to actually detach it.  What we want here is a program called 'setsid.'  This is part of the util-linux package, and it seems to be on every system I've been able to find, including the ones that didn't have expect.

Now there's one problem with setsid.  It immediately runs the program in the background.  I wanted to check the exit status of ssh to verify that everything was good.  I thought I was in luck, seeing that there's an option to do just this:  --wait.  Then I found that most of the other developers have older systems from before this option was added (in 2013, apparently).  This required creating another temporary script and a temporary results file, with the parent script waiting in a loop for it to finish.  So in /tmp/dossh.$$, I put the ssh command, followed by saving of the status ($?) in /tmp/dossh.$$.result.  And to keep everything clean, the last line of the script removes the script itself from /tmp.

So the parent script runs 'setsid /tmp/dossh.$$' then sits in a loop:
   while ! [ -f /tmp/dossh.$$.result]; do sleep .1; done
Then the parent script can grab the result, remove the remaining temporary files, and make use of the ssh tunnel. No manual password entry required.

No expect required!  (And that's a good thing.  Expect is a pain to use, in large part due to TCL being a painful language, but also due to issues where subtle changes in software versions can break everything, such as if a prompt changes slightly.)

Everything works exactly as the user would expect it to.

Wednesday, November 25, 2015

Solving a Puzzle

Earlier this year, I was given a puzzle as a gift.  It's a simple frame with Tetris-like blocks of different shapes, and the object is to get all nine blocks into the frame.  Making it more difficult, there will be leftover empty squares throughout the puzzle.  I played around with it for a while, and it wasn't too difficult to get to within one square of completing it, but I was probably nowhere close to actually solving it.

Being a programmer, I decided it would be more fun to program my computer to solve the puzzle.  I spent a couple of hours on it, and came up with a nice result.  I'll share the result below, along with some observations about the program and the puzzle.

First, here's a link to the puzzle:  http://www.palmettopuzzleworks.net/
You can buy it directly through Etsy for $20.


Before I delve into my program, let me start by suggesting that this might make a great programming assignment.  It's a very well-defined problem, but with a number of subtleties to watch out for.

So let me show you my solution.  My intuition was that this would be a computationally complex problem, and it looked like a good fit regardless, so my language of choice was C.

The first thing to do is define the data structures.  I've found that in the vast majority of problems, the data structures drive the code.  If you have the wrong data structures, you'll never get a good solution, but with the right data structures, the code mostly flows into place.

As you can see in the picture, the board is an 11x11 grid with some spaces filled in.  That makes the board an easy two-dimensional array.  The largest piece fits in a 4x5 grid, so I created a three-dimensional array for the pieces initialized to a 1 for the spots that are filled and a 0 for the squares not occupied.  Thinking ahead, I'm going to have to rotate each piece, so I need to use a square for each piece, not just a rectangle, so each piece is a 5x5 grid.


int grid[11][11];
int pieces[9][5][5] =
{
   // first four pieces are "big" and take four rows
   { { 0,1,1,0,0 },
     { 0,1,1,1,0 },
     { 1,1,1,1,1 },
     { 0,1,0,0,0 },
     { 0,0,0,0,0 } },
   { { 1,1,1,0,0 },
     { 0,1,1,1,0 },
     { 1,1,1,0,0 },
     { 0,1,0,0,0 },
     { 0,0,0,0,0 } },
   { { 0,1,0,0,0 },
     { 0,1,1,1,0 },
     { 0,1,1,1,1 },
     { 1,1,1,1,0 },
     { 0,0,0,0,0 } },
   { { 0,1,0,0,0 },
     { 1,1,1,1,0 },
     { 0,1,1,1,1 },
     { 0,1,0,1,0 },
     { 0,0,0,0,0 } },
   // remaining five pieces take three rows
   { { 0,1,1,1,0 },
     { 1,1,1,0,0 },
     { 1,1,1,0,0 },
     { 0,0,0,0,0 },
     { 0,0,0,0,0 } },
   { { 1,1,1,1,0 },
     { 1,1,1,0,0 },
     { 1,0,1,0,0 },
     { 0,0,0,0,0 },
     { 0,0,0,0,0 } },
   { { 1,1,1,0,0 },
     { 1,1,1,1,0 },
     { 1,0,1,0,0 },
     { 0,0,0,0,0 },
     { 0,0,0,0,0 } },
   { { 0,1,1,1,0 },
     { 1,1,1,0,0 },
     { 1,0,1,0,0 },
     { 0,0,0,0,0 },
     { 0,0,0,0,0 } },
   { { 1,1,0,0,0 },
     { 1,1,1,1,0 },
     { 0,1,1,0,0 },
     { 0,0,0,0,0 },
     { 0,0,0,0,0 } }
};

Initializing the grid is pretty simple: a zero represents an open space, a number indicates a piece (1 through 9), and another constant represents the border (10).  Because the border is more filled than open, the code fills the borders, then opens up the spaces where a piece can intrude.


#define BORDER 10

void init_border(void)
{
   // Set grid to zero
   memset(grid,0,sizeof(grid));
   // Border defaults to blocked
   for(int i=0;i<11;++i)
   {
      grid[0][i] = grid[i][0] = grid[10][i] = grid[i][10] = BORDER;
   }
   // Clear spots
   grid[0][2] = grid[0][4] = grid[0][8] = 0;
   grid[10][1] = grid[10][4] = grid[10][6] = grid[10][8] = 0;
   grid[3][0] = grid[5][0] = grid[8][0] = 0;
   grid[1][10] = grid[5][10] = grid[7][10] = grid[9][10] = 0;
}

Now here we come to the key trick to make the whole thing work.  I have to try each piece in four different rotations.  If I rotate the pieces on the fly, the program will be spending most of its time doing rotations.  That's not a good idea for something that is already likely to be quite computationally intensive.  So why not save the work and just do it once?  This raises one subtlety to the problem: The pieces all fit in a 5x5 grid, but have at least one row or column empty.  The solving code will want to assume that the top row and left column are non-empty, so each rotation has to also shift to make that happen.  With that explained, there's nothing particularly fancy about the code, though I'll admit that on the first run, it mangled the pieces by doing some reflections as well as rotations.


int all_pieces[9][4][5][5];

void init_rotations(void)
{
   for (int piece=0; piece<9; ++piece)
   {
      for (int rotation=0; rotation<4; ++rotation )
      {
         if ( rotation == 0 )
         {
            for ( int r=0;r<5;++r )
            {
               for ( int c=0;c<5;++c )
               {
                  all_pieces[piece][rotation][r][c] = pieces[piece][r][c];
               }
            }
         }
         else
         {
            for ( int r=0;r<5;++r )
            {
               for ( int c=0;c<5;++c )
               {
                  all_pieces[piece][rotation][4-c][r] = all_pieces[piece][rotation-1][r][c];
               }
            }
         }
      }
   }
   // Now shift rotations to all be in the upper-left (no all-zero rows or all-zero columns
   for (int piece=0; piece<9; ++piece)
   {
      for (int rotation=1; rotation<4; ++rotation )
      {
         for ( int i=0; i<5; ++i )
         {
            if ( all_pieces[piece][rotation][0][i] ) goto next; // Something in the first row
         }
         for ( int r=0;r<4;++r )
         {
            for ( int c=0;c<5;++c )
            {
               all_pieces[piece][rotation][r][c] = all_pieces[piece][rotation][r+1][c];
            }
         }
         for ( int c=0;c<5;++c )
         {
            all_pieces[piece][rotation][4][c] = 0;
         }
         --rotation; continue;
      next: ;
      }
   }
   for (int piece=0; piece<9; ++piece)
   {
      for (int rotation=1; rotation<4; ++rotation )
      {
         for ( int i=0; i<5; ++i )
         {
            if ( all_pieces[piece][rotation][i][0] ) goto next2; // Something in the first column
         }
         for ( int r=0;r<5;++r )
         {
            for ( int c=0;c<4;++c )
            {
               all_pieces[piece][rotation][r][c] = all_pieces[piece][rotation][r][c+1];
            }
         }
         for ( int r=0;r<5;++r )
         {
            all_pieces[piece][rotation][r][4] = 0;
         }
         --rotation; continue;
      next2: ;
      }
   }
}

Before writing the code to try all the combinations and find the solution, I need to be able to display the board.  I also need to be able to display the pieces to check that I've coded and rotated them correctly.  This is a place where spending a few minutes extra to have nice readable output can save a lot of time in understanding the results.  Using a graphics toolkit or generating HTML would be overkill for this problem.  Simple printing to the console would be fine, but tossing in some ANSI color codes to make the pieces easier to visualize would be well worth the effort.  Fortunately, I have a handy set of ANSI color code defines:


#define _CN "\033[m"          // Reset to default color and attributes
#define _CRED "\033[1;31m"    // Set text to bold red
#define _Cred "\033[31m"      // Set text to red
#define _C_red "\033[4;31m"   // Set text to underlined and red
#define _C_RED "\033[4;1;31m" // Set text to underline and bold red
#define _Bred "\033[41m"      // Set background to red
#define _CGRN "\033[1;32m"
#define _Cgrn "\033[32m"
#define _C_grn "\033[4;32m"
#define _C_GRN "\033[4;1;32m"
#define _Bgrn "\033[42m"
#define _CYEL "\033[1;33m"
#define _Cyel "\033[33m"
#define _C_yel "\033[4;33m"
#define _C_YEL "\033[4;1;33m"
#define _Byel "\033[43m"
#define _CBLU "\033[1;34m"
#define _Cblu "\033[34m"
#define _C_blu "\033[4;34m"
#define _C_BLU "\033[4;1;34m"
#define _Bblu "\033[44m"
#define _CMAG "\033[1;35m"
#define _Cmag "\033[35m"
#define _C_mag "\033[4;35m"
#define _C_MAG "\033[4;1;35m"
#define _Bmag "\033[45m"
#define _CCYN "\033[1;36m"
#define _Ccyn "\033[36m"
#define _C_cyn "\033[4;36m"
#define _C_CYN "\033[4;1;36m"
#define _Bcyn "\033[46m"
#define _CWHT "\033[1;37m"
#define _Cwht "\033[37m"
#define _C_wht "\033[4;37m"
#define _C_WHT "\033[4;1;37m"
#define _Bwht "\033[47m"
#define _CBLK "\033[1;30m"
#define _Cblk "\033[30m"
#define _C_blk "\033[4;30m"
#define _C_BLK "\033[4;1;30m"
#define _Bblk "\033[40m"
/*
 * ANSI attribute strings
 */
#define _A_BOLD "\033[1m"         // Leave color and underline-status as-is, set BOLD
#define _A_UNDER "\033[4m"        // Leave color and bold-status as-is, set UNDERLINE
#define _A_BOLD_UNDER "\033[1;4m" // Just an optimized version of _A_BOLD _A_UNDER

So using those defines to display the grid and the pieces is fairly straightforward.  You'll notice that I take advantage of C's string concatenation--any two strings separated only by whitespace are treated as a single string.


void display_grid(void)
{
   printf(_Bblk"             "_CN"\n");
   for (int row=0;row<11;++row)
   {
      printf(_Bblk" "_CN);
      for (int col=0;col<11;++col)
      {
         char c;
         c = grid[row][col] + '0';
         switch(grid[row][col]) {
            case 0: c=' '; printf(_Bwht); break;
            case 1:
               printf(_Bcyn); break;
            case 2:
            case 3:
               printf(_Bblu); break;
            case 4:
            case 5:
               printf(_Bmag); break;
            case 6:
            case 7:
               printf(_Byel); break;
            case 8:
               printf(_Bred); break;
            case 9:
               printf(_Bgrn); break;
            case BORDER: c=' '; printf(_Bblk); break;
         }
         printf("%c"_CN,c);
      }
      printf(_Bblk" "_CN"\n");
   }
   printf(_Bblk"             "_CN"\n");
   printf("\n");
}

void display_pieces(void)
{
   for (int piece=0;piece<9;++piece)
   {
      printf("Piece %d rotations\n",piece+1);
      for (int row=0;row<5;++row)
      {
         for (int rotation=0;rotation<4;++rotation)
         {
            for (int col=0;col<5;++col)
            {
               char c;
               c = all_pieces[piece][rotation][row][col] ? '1' + piece : ' ';
              
               switch(all_pieces[piece][rotation][row][col] * (piece+1)) {
                  case 0: c=' '; printf(_Bwht); break;
                  case 1:
                     printf(_Bcyn); break;
                  case 2:
                  case 3:
                     printf(_Bblu); break;
                  case 4:
                  case 5:
                     printf(_Bmag); break;
                  case 6:
                  case 7:
                     printf(_Byel); break;
                  case 8:
                     printf(_Bred); break;
                  case 9:
                     printf(_Bgrn); break;
                  default:
                     printf("invalid"); break;
               }
               printf("%c"_CN,c);
            }
            printf("      ");
         }
         printf("\n");
      }
   }
}

With the above code, I have all that is needed to display the pre-rotated pieces (which proved vital for debugging mangled rotations) and the game board with any pieces placed in it.  Starting out, it looks like:

Piece 1 rotations
 11          1           1        1         
 111        11        11111      1111       
11111      111         111        111       
 1         1111         11        11        
             1                    1         
Piece 2 rotations
222         2           2         2 2       
 222       222         222       2222       
222        2222       222         222       
 2         2 2         222         2        
                                            
Piece 3 rotations
 3           3         3333      3          
 333        333       3333       3333       
 3333       333        333       333        
3333       3333          3       333        
              3                   3         
Piece 4 rotations
 4           4         4 4         4        
4444        444       4444       4444       
 4444       44         4444       44        
 4 4       4444          4       444        
            4                     4         
Piece 5 rotations
 555       5           555       55         
555        555         555       555        
555        555        555        555        
            55                     5        
                                            
Piece 6 rotations
6666       6           6 6       666        
666        666         666        66        
6 6        66         6666       666        
           666                     6        
                                            
Piece 7 rotations
777         7          7 7       777        
7777       777        7777        77        
7 7        77          777       777        
           777                    7         
                                            
Piece 8 rotations
 888       8           8 8       88         
888        888         888        88        
8 8        88         888        888        
            88                     8        
                                            
Piece 9 rotations
99          9          99         99        
9999        99        9999       999        
 99        999          99       99         
           99                     9         
                                            
Empty board
             
             
             
             
             
             
             
             
             
             
             
             
             

So the the code to actually go through the placements feels anticlimactic at this point.  It simply marches through the puzzle, trying every possible combination in much the way I would do if I were doing an exhaustive search by hand.  Here's the complete program:


/*
 * Find the solution or solutions to The Infuriater
 *
 * By Preston Crow
 *
 * gcc -std=c99 -W -Wall puzzle.c -o puzzle -O3 && puzzle
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define _CN "\033[m"          // Reset to default color and attributes
#define _CRED "\033[1;31m"    // Set text to bold red
#define _Cred "\033[31m"      // Set text to red
#define _C_red "\033[4;31m"   // Set text to underlined and red
#define _C_RED "\033[4;1;31m" // Set text to underline and bold red
#define _Bred "\033[41m"      // Set background to red
#define _CGRN "\033[1;32m"
#define _Cgrn "\033[32m"
#define _C_grn "\033[4;32m"
#define _C_GRN "\033[4;1;32m"
#define _Bgrn "\033[42m"
#define _CYEL "\033[1;33m"
#define _Cyel "\033[33m"
#define _C_yel "\033[4;33m"
#define _C_YEL "\033[4;1;33m"
#define _Byel "\033[43m"
#define _CBLU "\033[1;34m"
#define _Cblu "\033[34m"
#define _C_blu "\033[4;34m"
#define _C_BLU "\033[4;1;34m"
#define _Bblu "\033[44m"
#define _CMAG "\033[1;35m"
#define _Cmag "\033[35m"
#define _C_mag "\033[4;35m"
#define _C_MAG "\033[4;1;35m"
#define _Bmag "\033[45m"
#define _CCYN "\033[1;36m"
#define _Ccyn "\033[36m"
#define _C_cyn "\033[4;36m"
#define _C_CYN "\033[4;1;36m"
#define _Bcyn "\033[46m"
#define _CWHT "\033[1;37m"
#define _Cwht "\033[37m"
#define _C_wht "\033[4;37m"
#define _C_WHT "\033[4;1;37m"
#define _Bwht "\033[47m"
#define _CBLK "\033[1;30m"
#define _Cblk "\033[30m"
#define _C_blk "\033[4;30m"
#define _C_BLK "\033[4;1;30m"
#define _Bblk "\033[40m"
/*
 * ANSI attribute strings
 */
#define _A_BOLD "\033[1m"         // Leave color and underline-status as-is, set BOLD
#define _A_UNDER "\033[4m"        // Leave color and bold-status as-is, set UNDERLINE
#define _A_BOLD_UNDER "\033[1;4m" // Just an optimized version of _A_BOLD _A_UNDER

int grid[11][11];
int pieces[9][5][5] =
{
   // first four pieces are "big" and take four rows
   { { 0,1,1,0,0 },
     { 0,1,1,1,0 },
     { 1,1,1,1,1 },
     { 0,1,0,0,0 },
     { 0,0,0,0,0 } },
   { { 1,1,1,0,0 },
     { 0,1,1,1,0 },
     { 1,1,1,0,0 },
     { 0,1,0,0,0 },
     { 0,0,0,0,0 } },
   { { 0,1,0,0,0 },
     { 0,1,1,1,0 },
     { 0,1,1,1,1 },
     { 1,1,1,1,0 },
     { 0,0,0,0,0 } },
   { { 0,1,0,0,0 },
     { 1,1,1,1,0 },
     { 0,1,1,1,1 },
     { 0,1,0,1,0 },
     { 0,0,0,0,0 } },
   // remaining five pieces take three rows
   { { 0,1,1,1,0 },
     { 1,1,1,0,0 },
     { 1,1,1,0,0 },
     { 0,0,0,0,0 },
     { 0,0,0,0,0 } },
   { { 1,1,1,1,0 },
     { 1,1,1,0,0 },
     { 1,0,1,0,0 },
     { 0,0,0,0,0 },
     { 0,0,0,0,0 } },
   { { 1,1,1,0,0 },
     { 1,1,1,1,0 },
     { 1,0,1,0,0 },
     { 0,0,0,0,0 },
     { 0,0,0,0,0 } },
   { { 0,1,1,1,0 },
     { 1,1,1,0,0 },
     { 1,0,1,0,0 },
     { 0,0,0,0,0 },
     { 0,0,0,0,0 } },
   { { 1,1,0,0,0 },
     { 1,1,1,1,0 },
     #if 0
     { 0,1,1,0,0 },
     #else
     { 1,1,1,0,0 },
     #endif
     { 0,0,0,0,0 },
     { 0,0,0,0,0 } }
};

int all_pieces[9][4][5][5];

int place[9][3]; // rotation,row,col for the piece

#define BORDER 10

void init_border(void)
{
   // Set grid to zero
   memset(grid,0,sizeof(grid));
   // Border defaults to blocked
   for(int i=0;i<11;++i)
   {
      grid[0][i] = grid[i][0] = grid[10][i] = grid[i][10] = BORDER;
   }
   // Clear spots
   grid[0][2] = grid[0][4] = grid[0][8] = 0;
   grid[10][1] = grid[10][4] = grid[10][6] = grid[10][8] = 0;
   grid[3][0] = grid[5][0] = grid[8][0] = 0;
   grid[1][10] = grid[5][10] = grid[7][10] = grid[9][10] = 0;
}

void init_rotations(void)
{
   for (int piece=0; piece<9; ++piece)
   {
      for (int rotation=0; rotation<4; ++rotation )
      {
         if ( rotation == 0 )
         {
            for ( int r=0;r<5;++r )
            {
               for ( int c=0;c<5;++c )
               {
                  all_pieces[piece][rotation][r][c] = pieces[piece][r][c];
               }
            }
         }
         else
         {
            for ( int r=0;r<5;++r )
            {
               for ( int c=0;c<5;++c )
               {
                  all_pieces[piece][rotation][4-c][r] = all_pieces[piece][rotation-1][r][c];
               }
            }
         }
      }
   }
   // Now shift rotations to all be in the upper-left (no all-zero rows or all-zero columns
   for (int piece=0; piece<9; ++piece)
   {
      for (int rotation=1; rotation<4; ++rotation )
      {
         for ( int i=0; i<5; ++i )
         {
            if ( all_pieces[piece][rotation][0][i] ) goto next; // Something in the first row
         }
         for ( int r=0;r<4;++r )
         {
            for ( int c=0;c<5;++c )
            {
               all_pieces[piece][rotation][r][c] = all_pieces[piece][rotation][r+1][c];
            }
         }
         for ( int c=0;c<5;++c )
         {
            all_pieces[piece][rotation][4][c] = 0;
         }
         --rotation; continue;
      next: ;
      }
   }
   for (int piece=0; piece<9; ++piece)
   {
      for (int rotation=1; rotation<4; ++rotation )
      {
         for ( int i=0; i<5; ++i )
         {
            if ( all_pieces[piece][rotation][i][0] ) goto next2; // Something in the first column
         }
         for ( int r=0;r<5;++r )
         {
            for ( int c=0;c<4;++c )
            {
               all_pieces[piece][rotation][r][c] = all_pieces[piece][rotation][r][c+1];
            }
         }
         for ( int r=0;r<5;++r )
         {
            all_pieces[piece][rotation][r][4] = 0;
         }
         --rotation; continue;
      next2: ;
      }
   }
}

void display_grid(void)
{
   printf(_Bblk"             "_CN"\n");
   for (int row=0;row<11;++row)
   {
      printf(_Bblk" "_CN);
      for (int col=0;col<11;++col)
      {
         char c;
         c = grid[row][col] + '0';
         switch(grid[row][col]) {
            case 0: c=' '; printf(_Bwht); break;
            case 1:
               printf(_Bcyn); break;
            case 2:
            case 3:
               printf(_Bblu); break;
            case 4:
            case 5:
               printf(_Bmag); break;
            case 6:
            case 7:
               printf(_Byel); break;
            case 8:
               printf(_Bred); break;
            case 9:
               printf(_Bgrn); break;
            case BORDER: c=' '; printf(_Bblk); break;
         }
         printf("%c"_CN,c);
      }
      printf(_Bblk" "_CN"\n");
   }
   printf(_Bblk"             "_CN"\n");
   printf("\n");
}

void display_pieces(void)
{
   for (int piece=0;piece<9;++piece)
   {
      printf("Piece %d rotations\n",piece+1);
      for (int row=0;row<5;++row)
      {
         for (int rotation=0;rotation<4;++rotation)
         {
            for (int col=0;col<5;++col)
            {
               char c;
               c = all_pieces[piece][rotation][row][col] ? '1' + piece : ' ';
              
               switch(all_pieces[piece][rotation][row][col] * (piece+1)) {
                  case 0: c=' '; printf(_Bwht); break;
                  case 1:
                     printf(_Bcyn); break;
                  case 2:
                  case 3:
                     printf(_Bblu); break;
                  case 4:
                  case 5:
                     printf(_Bmag); break;
                  case 6:
                  case 7:
                     printf(_Byel); break;
                  case 8:
                     printf(_Bred); break;
                  case 9:
                     printf(_Bgrn); break;
                  default:
                     printf("invalid"); break;
               }
               printf("%c"_CN,c);
            }
            printf("      ");
         }
         printf("\n");
      }
   }
}

void remove_piece(int piece)
{
   for (int row=0;row<11;++row)
   {
      for (int col=0;col<11;++col)
      {
         if ( grid[row][col] == piece+1 )
         {
            grid[row][col] = 0;
         }
      }
   }
}

int place_piece_here(int piece,int rotation,int row,int col)
{
   for ( int r=0; r<5; ++r )
   {
      for ( int c=0; c<5; ++c )
      {
         if ( all_pieces[piece][rotation][r][c] )
         {
            if ( r+row >= 11 || c+col >=11 ) return 0; // Off the grid
            if ( grid[r+row][c+col] ) return 0; // Spot full
         }
      }
   }
   // Yes, it goes here; put it in the grid
   for ( int r=0; r<5; ++r )
   {
      for ( int c=0; c<5; ++c )
      {
         if ( all_pieces[piece][rotation][r][c] )
         {
            grid[r+row][c+col] = piece+1;
         }
      }
   }
   return 1;
}

// Place a piece if possible; return true if placed
int place_piece(int piece)
{
   for ( int rotation=place[piece][0]; rotation<4; ++rotation,place[piece][1]=0,place[piece][2]=0 )
   {
      for ( int row=place[piece][1]; row<9; ++row,place[piece][2]=0 )
      {
         for ( int col=place[piece][2]; col<9; ++col )
         {
            if ( place_piece_here(piece,rotation,row,col) )
            {
               place[piece][0]=rotation;
               place[piece][1]=row;
               place[piece][2]=col;
               return 1;
            }
         }
      }
   }
   return 0;
}

int main(int argc,char *argv[])
{
   (void)argc;(void)argv;
   init_border();
   init_rotations();
   display_pieces();
   printf("Empty board\n");
   display_grid();

   int solutions=0;
   for (int i=0; i<9; ++i )
   {
      if ( place_piece(i) )
      {
         if ( i == 8 )
         {
            ++solutions;
            printf("Solution %d found:\n",solutions);
            display_grid();
            remove_piece(i);
         }
         else
         {
            if ( i >=7 && 0 ) // debug
            {
               printf("Placed %d pieces:\n",i+1);
               display_grid();
            }
            if ( i != 8 )
            {
               for ( int j=0;j<3; ++j)
                  place[i+1][j]=0;
            }
            continue;
         }
      }
      if ( i == 0 )
      {
         if ( !solutions )
         {
            printf("Failed to solve puzzle\n");
         }
         break;
      }
//printf("Can't place piece %d; remove piece %d\n",i+1,i);
      // Advance the previous piece
      --i;
      remove_piece(i);
//      printf("piece %d was at rot,row,col %d,%d,%d\n",i+1,place[i][0],place[i][1],place[i][2]);
      ++place[i][2];
      // Go back one more as the loop will increment
      --i;
//      printf("piece %d was at rot,row,col %d,%d,%d\n",i+1,place[i][0],place[i][1],place[i][2]);
   }
   //display_grid();
   return 0;
}

Now much to my surprise, once I had debugged it, it ran quite fast.  I had guessed that it might run for hours before finding the solution, but it ran to completion in under a minute.  The biggest surprise was that it found not one, but eight solutions!  I shared my results with the creator of the puzzle.  He said he had also used a computer to verify that there was only one solution, but apparently his program had a bug.  He has made a slight change to the puzzle, so if you buy it now, it will have one unique solution.

In case you're interested in buying and playing with the puzzle yourself, I won't spoil it by posting the solution here.  It's simple enough to run the program if you want to see them.

And a note on copyright: While I hold the copyright on all my posts, including the above code, in my opinion, the ANSI color code defines are simple and obvious enough that they can hardly be considered copyrightable, so feel free to use them.