Category: Programming

Untangle, Planarity.

I’ve been writing some code (in Java) to solve this fun puzzle.  I’ve played the puzzle for many years – it’s part of the excellent and free Simon Tatham’s Portable Puzzle Collection which has been available on many platforms for ages and has recently been ported to Android too.  Untangle was inspired by Planarity, written by John Tantalo.

My first effort modelled the puzzle as a physical system.  The links between points are elastic bands, where the attractive force is proportional to the cube of their length.  The points have an electric charge which produces a repulsive force between all points in line with Coulomb’s inverse square law.  The whole thing is submerged in a viscous fluid so that things don’t move too fast.

Untangle17

It solves many puzzles just using those rules but sometimes, especially with puzzles with a large number of vertices, it gets stuck in ‘a knot’ or takes too long to stabilize.  Also, if it happens to ‘choose’ an outer face with a large number of vertices, then some inner vertices can be pushed out by the repulsive force so that they cross the ‘perimeter line’.

I’m now working on a faster and guaranteed-to-work algorithm – though it may not be as interesting to watch in action.  Stay tuned for an update…

ATmega328P-PU 12MHz bootloader

It took me an embarrassingly long time to get a 328 with a 12MHz crystal working so that it would allow a normal (serial / FTDI) upload from the Arduino IDE.

There are a few older guides around but I didn’t find one that used the newer optiboot bootloader.

If you don’t want to compile the bootloader yourself, you can download the compiled optiboot_at328mega_12.hex file from this link (right-click and and Save (link) as…) just copy it to your optiboot folder before editing your “boards.txt” file as described below.

If you want to compile the hex file yourself here’s how:

Edit the Makefile in your optiboot folder. On my (Windows 7 64bit) machine using Arduino 1.0.5-r2 this folder was C:\Program Files (x86)\Arduino\hardware\arduino\bootloaders\optiboot

Add this section. I put it in after the existing atmega328 sections and before the Sanguino section  (note that the -W1, … shouldn’t be on a separate line – it’s a continuation of the LDSECTIONS line, but this blogging software seems to want to wrap it onto a new line):

atmega328_12: TARGET = atmega328
atmega328_12: MCU_TARGET = atmega328p
atmega328_12: CFLAGS += '-DLED_START_FLASHES=3' '-DBAUD_RATE=115200'
atmega328_12: AVR_FREQ = 12000000L
atmega328_12: LDSECTIONS  = -Wl,--section-start=.text=0x7e00 -Wl,--section-start=.version=0x7ffe
atmega328_12: $(PROGRAM)_atmega328_12.hex
atmega328_12: $(PROGRAM)_atmega328_12.lst

atmega328_12_isp: atmega328
atmega328_12_isp: TARGET = atmega328
atmega328_12_isp: MCU_TARGET = atmega328p
# 512 byte boot, SPIEN
atmega328_12_isp: HFUSE = DE
# Low power xtal (12MHz) 16KCK/14CK+65ms
atmega328_12_isp: LFUSE = FF
# 2.7V brownout
atmega328_12_isp: EFUSE = 05
atmega328_12_isp: isp

This is just a copy of the atmega328. section with:

  • the name changed from atmega328. to atmega328_12.
  • the f_cpu parameter changed from 16000000L to 12000000L
  • the two (PROGRAM) lines changed so that the .hex and .lst filenames also have the “_12” addition
  • the comment about the 16MHz crystal frequency changed to 12MHz

Run a command shell as administrator and navigate to the optiboot folder.  Enter the following command to compile the new 12MHz optiboot bootloader:

omake atmega328_12

Now edit your boards.txt file.  On my machine this was located at C:\Program Files (x86)\Arduino\hardware\arduino  Add this new section at the end – again this is just a copy of the ‘uno’ section with the few obvious edits for frequency and bootloader file.

##############################################################

atmega328bb12.name=ATmega328 12MHz crystal
atmega328bb12.upload.protocol=arduino
atmega328bb12.upload.maximum_size=32256
atmega328bb12.upload.speed=115200
atmega328bb12.bootloader.low_fuses=0xff
atmega328bb12.bootloader.high_fuses=0xde
atmega328bb12.bootloader.extended_fuses=0x05
atmega328bb12.bootloader.path=optiboot
atmega328bb12.bootloader.file=optiboot_atmega328_12.hex
atmega328bb12.bootloader.unlock_bits=0x3F
atmega328bb12.bootloader.lock_bits=0x0F
atmega328bb12.build.mcu=atmega328p
atmega328bb12.build.f_cpu=12000000L
atmega328bb12.build.core=arduino
atmega328bb12.build.variant=standard

Now launch Arduino, select “ATmega328 12MHz crystal” as your board and “Burn Bootloader” from the Tools menu.

That’s it, and you should be up and running with the normal hardware serial port working correctly with the ‘Serial’ commands and serial uploading from the Arduino IDE also working correctly.  I’ve seen comments that not all of the timing functions (microsecond delays etc.) work accurately when using a 12MHz crystal and the standard Arduino libraries.  I’ve not investigated that yet; and so far I’ve not tried using software serial with a 12MHz crystal – that also may require some tweaking…

 

 

Controlling the Raspberry Pi camera from C

I wanted to be able to stop and start the camera driven by events instead of just calling raspivid to record for a preset time.

My code is really just a simple wrapper around raspivid using the SIGUSR1 option to stop the video under program control rather than after a preset time.

The example main() function starts the video, sleeps for five seconds and then stops it.  For demo purposes I included the options for black and white inverted video.  To record with the normal raspivid defaults you just call startVideo with an empty options string:

startVideo(“filename.h264”, “”);

Obviously you can put any of the normal raspivid options in the string – but you should avoid -t, -n, -o, and -s as the code fills those in for you.  If you want to enable preview/monitoring then make the obvious change to remove the -n (no preview) option.

Save code as, say, video.c and compile with gcc -o video video.c

#include <signal.h>
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static pid_t pid = 0;

void startVideo(char *filename, char *options) {
    if ((pid = fork()) == 0) {
        char **cmd;

        // count tokens in options string
        int count = 0;
        char *copy;
        copy = strdup(options);
        if (strtok(copy, " \t") != NULL) {
            count = 1;
            while (strtok(NULL, " \t") != NULL)
                count++;
        }

        cmd = malloc((count + 8) * sizeof(char **));
        free(copy);

        // if any tokens in options, 
        // copy them to cmd starting at positon[1]
        if (count) {
            int i;
            copy = strdup(options);
            cmd[1] = strtok(copy, " \t");
            for (i = 2; i <= count; i++)
                cmd[i] = strtok(NULL, " \t");
        }

        // add default options
        cmd[0] = "raspivid"; // executable name
        cmd[count + 1] = "-n"; // no preview
        cmd[count + 2] = "-t"; // default time (overridden by -s)
                               // but needed for clean exit
        cmd[count + 3] = "10"; // 10 millisecond (minimum) time for -t
        cmd[count + 4] = "-s"; // enable USR1 signal to stop recording
        cmd[count + 5] = "-o"; // output file specifer
        cmd[count + 6] = filename;
        cmd[count + 7] = (char *)0; // terminator
        execv("/usr/bin/raspivid", cmd);
    }
}

void stopVideo(void) {
    if (pid) {
        kill(pid, 10); // seems to stop with two signals separated
                       // by 1 second if started with -t 10 parameter
        sleep(1);
        kill(pid, 10);
    }
}

int main(int argc, char **argv) {
    printf("Recording video for 5 secs...");
    // example options give an upside-down black and white video
    startVideo("temp.h264", "-cfx 128:128 -rot 180"); 
    fflush(stdout);
    sleep(5);
    stopVideo();
    printf("\nVideo stopped - exiting in 2 secs.\n");
    sleep(2);
    return 0;
}

Flash Rubik Cube Simulator

Snapshot of Flash Rubik Cube Simulator

Above is a snapshot image.  Here’s the real thing.

It works for any size of cube from 2 x 2 x 2 up to 11 x 11 x 11.  Actually, 11 is an arbitrary limit – the same code would work for any size of cube.  Use the little + and – buttons up in the top left hand corner to select the size of the cube.

Turning a face or slicing a layer is pretty intuitive – just click somewhere on the cube, hold down the mouse button and drag.

Turning the whole cube around is the same but you have to double-click, hold the mouse button down on the second click and then drag.

There’s a bug in the turning of the whole cube which causes the orientation to jump occasionally.  I think I can fix it by using quaternions to do the whole-cube rotation, but with the demise of Flash I’m thinking this would be a good project to migrate to HTML5 – and then I could patch in the quaternion stuff at the same time.

You can also use the keyboard to turn layers (there’s a sort of agreed way of doing this among speed-cubers, and the simulation mostly uses the agreed keys),

The Minimum Attack Problem

Place five queens on a chess board so that every square on the board is attacked.  It’s an old and famous problem; there are lots of solutions and it’s pretty easy to find one.  Try it for yourself and see!

Now try using just three queens and two rooks.  Not so easy this time; the solution is unique if you ignore trivial rotations and reflections of the whole board.  What about other attacking forces? Four queens and two pawns maybe?

The image above is a snapshot of my solver.  Click here to go to the solver itself. I wrote it over ten years ago when Java applets were flavor of the month.  Most modern computers and tablets don’t have Java available by default and most tablets won’t let you install Java at all; you can still install Java as a free plug-in in most PC browsers though.