Simple tests using the WeMos D1 R2…

August 25, 2016 | ESP8266 | By: Mark VandeWettering

I didn’t have a ton of time to tinker when I got home, but I did play a tiny bit more with the WeMos D1 R2. I got it mounted on an old breadboard that I had previously used for Arduino experiments, and then tried reflashing it with new, fresh NodeMCU firmware that I built on the cloud. That did not result in success, but I’m willing to bet that was because of something stupid I did, although what precisely that may have been is still a mystery to me. But I then dusted off some old “clock” code that I wrote for the Arduino, and tried a quick port to the WeMos. Several of the libraries that I used on the Arduino (RTClib and TimerOne) were not supported on the ESP8266, so for the moment it’s not a real time clock: it just counts in seconds, and uses the Ticker library instead. But in the span of fifteen minutes that I eeked out just before bed, I got it working:

IMG_0036

Pardon the poor quality snapshot against all the clutter on my desk.

So far, I’m having fun with the WeMos. I will probably a sketch which uses the WiFi next, and perhaps the MQTT framework.

New WeMos D1 R2 boards have arrived…

August 24, 2016 | ESP8266 | By: Mark VandeWettering

wemosI just got a trio of WeMos D1 R2 boards from Banggood this morning. I haven’t had a chance to do anything with them yet, other than power one of them on and check it for basic function, but I thought I’d give a brief review.

For those of you who maybe haven’t been tracking the ESP8266 based boards, they are basically a small 32 bit processor which run at 80Mhz and include WiFi. What’s really astonishing is how cheap they are: simple ESP-01 boards are available for around $3. These super cheap boards don’t have a lot of expansion pins, and are a little bit of a hassle to program though, since you’ll need a FTDI or similar serial cable.

The WeMos D1 R2 takes one of these modules (the tin package to the right) and mounts it with all the necessary interface logic to interface to USB. When I plugged it into my linux box, the following messages showed up in the output to “dmesg”, indicating that it had connected it to the serial port ttyUSB0:

[48095.058498] usb 1-3.3: new full-speed USB device number 7 using ehci-pci
[48095.186475] usb 1-3.3: New USB device found, idVendor=1a86, idProduct=7523
[48095.186482] usb 1-3.3: New USB device strings: Mfr=0, Product=2, SerialNumber=0
[48095.186485] usb 1-3.3: Product: USB2.0-Serial
[48095.191571] ch341 1-3.3:1.0: ch341-uart converter detected
[48095.251692] usb 1-3.3: ch341-uart converter now attached to ttyUSB0

Then, I ran “sudo screen /dev/ttyUSB0” and connected to it. It was booted into a custom build of the “nodemcu” firmware, which runs the open source language “lua”. You can read the documentation and figure out how to access many of the peripherals and libraries.

The quality of the boards seems quite high. One thing to note is that while the pin layouts and physical form factor of the boards is identical to the Arduino, the ESP8266 board supports much fewer pins. There appears to only be a single analog input, and the labeling of the digital “D” pins are somewhat odd, and it appears that multiple pins may be connected to the same input. It also appears that there are a different set of labels on the bottom of the board, which is truly confusing.

I’ll dig in a bit more when I have some time and figure out what the deal is.

Here is the link to the Banggood page for them. I found a 15% off coupon code “BG15%OFF” using the Honey Chrome plugin, so the cost for three shipped was about $16.

A new theory of dorodango…

August 22, 2016 | Dorodango | By: Mark VandeWettering

Okay, I’ve done two, with nearly identical outcomes: a fine network of relatively shallow cracks in the “capsule”, the thin layer of fine particles which encapsulate the core. I’ve been rereading various accounts on how other people make dorodango, and have noticed a couple of differences which I think I am going to test.

I suspect now that I’m being too timid in my initial drying of the core. After forming the wet inner core, you then sprinkle on relatively fine, dry dust until it won’t hold any additional material. What I was doing was then cycling this in a plastic bag, essentially drying the core very slowly, while adding additional finer and finer material. Eventually, when I did dry out this fine material, it was relatively inflexible, and as the core shrank slightly, it tension cracks. I’m now wondering if the bulk of drying shouldn’t happen while the outer skin is still relatively coarse. So, my next ball will be worked relatively longer in its primitive stage, and will be allowed to dry overnight. One account says that if it cracks, it will likely do so in the first 30 minutes of this stage.

I think I am going to ditch the soil that I purloined from Golden Gate park as well. It has a lot of faintly greasy black silt embedded in it, which is quite slick and messy. My normal backyard dirt was easier to work. I may also buy a bag of fire clay just to see what I could do with a 50/50 clay sand mixture.

Dorodango cracks again…

August 21, 2016 | Dorodango | By: Mark VandeWettering

Sigh. My second attempt has also cracked, although it is beginning to look pretty shiny.

IMG_0028

Ordered some ESP8266 boards in an Arduino form factor…

August 20, 2016 | Arduino, Embedded, ESP8266, Hardware | By: Mark VandeWettering

r2_1The ESP8266 is an amazing little processor: cheap and capable and (most interestingly) WiFi enabled. I have some of the older “nodemcu” boards that I got for about $7 each, but there are newer alternatives that include up to 4M of flash memory, and a variety of interesting form factors.

I noticed that WeMos was producing these boards which nominally have the Arduino Uno form factor. With a 15% discount coupon from banggood.com, I got three of them on order for under $16. I’ll let you know how they work out. I’m normally not a fan of the classic Arduino shape, but I do have a number of 3d printed cases and bumpers that can be used, which makes them relatively easy to mount and wire up.

If you want to program the ESP8266, you might try using platformio, which makes it easy to use both the native SDK as well as a simpler Arduino based framework. It also supports a number of other embedded architectures, including the Arduino, but allows you to use your own editor and the like to build and organize your code. Worth looking at.

FFMPEG overlay needs “repeatlast” argument…

August 17, 2016 | Video | By: Mark VandeWettering

I use ffmpeg to add some information overlays to the videos that I often upload to YouTube. I’ve documented these before, but I had a problem that arose from time to time that I never figured out: occasionally my encodes would seemingly just go on forever, and never terminate. I discovered today that this was because the use of the “overlay” filter. It apparently keeps generating frames even after the main stream has terminated, which seems odd to me, but… whatever. If you add the repeatlast argument, you’ll get what you want.

Stashed here for reference later.

#!/bin/sh
ffmpeg -y -f concat -i files.txt -movflags +faststart -aspect 16:9 -crf 24 \
	-vf "scale=854:480, fade=in:0:30, hqdn3d [xxx] ; \
	     color=0x33669955:854x64 [yyy] ; \
	     [xxx] [yyy] overlay=0:416:repeatlast=0, \
	     drawtext=textfile=hdr:fontfile=/usr/share/fonts/truetype/ttf-dejavu/DejaVuSans-Bold.ttf:x=10:y=432:fontsize=16:fontcolor=white" \
	quad.mp4

No! My precious dorodango!

August 11, 2016 | Dorodango | By: Mark VandeWettering

IMG_1245Eek! I was getting a bit impatient with my dorodango, so I decided to leave it out in the open air when I went to work today so I could let it dry out a bit. I returned to it having dry cracks! Note to anyone attempting this: don’t be impatient. Let it dry out slowly.

On the other hand, it does still look pretty cool. I snapped this with my Canon Digital XT and did a bit of tweaking to enhance the contrast and the cracks, and frankly, it looks pretty good. I put it back in a bag and put it in the refrigerator to sit for a half hour. I’m thinking that maybe that will draw some residual water to the surface, and maybe a little more dust rubbing will polish it. I wouldn’t mind if there were some cool looking cracks in it, if the surface was smoothed out.

It’s all an experiment!

Addendum: The center of the worst crack appears to be where the dorodango was the least round. My guess is that as the tension of the drying dorodango would have been evenly distributed if it were perfectly spherical, but the defect caused the stress to bunch up and break through. It’s spent a couple of rounds in the fridge, and the smaller cracks are filling in nicely, the center of the cracking is the only part where you can feel the cracks. I’ll try a few more rounds in the fridge to see what happens.

Addendum2:

It’s beginning to take a polish, at least for a bit. A little work with some dry fine dust and a paper towel yielded this:
IMG_1246

Dorodango: Having (or rather making) a ball with just mud

August 9, 2016 | My Projects | By: Mark VandeWettering

File_000On Sunday, I started a new project which on the face of it, seems like an enormous waste of time, but if you’ve been reading my blog for any period of time, you know that wasting time is pretty much the bread and butter of my online presence, so here we go.

I’ve started work on a dorodango (????).

A dorodango is essentially a ball of mud, carefully formed into a sphere, and then covered with layers of dried dirt until it becomes a smooth, solid sphere, and then polished to a high shine.

I’m sure that some of your are blinking your eyes and wondering if I’ve gone stark raving mad. Wonder no further. It is kind of a lunatic thing to do. On the other hand, it’s also relaxing, and gives me time to think about interesting things, or just clear my mind and think of nothing at all. And, of course, the materials you need are quite literally just some dry dirt and a little water.

If you want to see some excellent examples, you can surf over to Bruce Gardner’s excellent dorodango.com website and have a peek. My example will no doubt be less beautiful, but still pretty interesting.

I began by going out to my back yard with a small shovel and a strainer I bought just for this purpose for $1 at the Dollar Tree. I went to the portion of my garden which doesn’t get regular watering, and where the ground is very dry, and scooped up a bunch of dirt, and ran it through the sieve to remove the large pieces of gravel and other organic matter, which I dumped into a cheap $1 food container. Once I had a layer a few inches thick of relatively fine material, I strained some more into a smaller container. When I felt that I had enough material to form the initial core, I added some water (probably too much) and worked it into a paste. I then formed a rough ball, squeezing out some of the (again, too much) water, and then forming it roughly into a ball, shaking it back and forth between my two hands until a relatively good sphere was formed.

I then held it over my container of dry dirt, and sprinkled the surface with this, adding some, and then brushing it off with the base of my thumb. At this stage, the core is still pretty easy to squish, and several times, cracks would form across the ball. I then added a little bit more of the dirt and wiped across the crack, and they would go away. For a half an hour, I fought the appearance of new cracks, and then they seem to stop. The surface became quite smooth, and the ball was no longer easy to compress out of shape, although I was handling it pretty gingerly. I kept adding dry dirt to it, and rubbing it gently off with the base of my thumb until the surface appeared quite dry, and dirt would no longer stick to it. Then, I put it in a ziplock bag and set it aside in my garage on top of a piece of foam so it wouldn’t create a dent. After a few hours, water will condense out on the bag and on the surface, and you extract the ball and add more fine dirt. I’m currently in the process of repeating this process until the core is completely dried out. Then, there will be more polishing to bring up the surface sheen.

Here’s a brief iPhone video I made of the ball in progress (apologies for the vertically oriented video). The texture of the ball is already quite smooth and leathery. I estimate it will take a few more days of intermittent work before I’ll begin to work on polishing it.

I’ll hopefully post a picture of the beautiful finished sphere in a week or so. If this sounded boring, consider that I did most of the work while sitting outside, watching hummingbirds and generally relaxing. I found it a great stress relief.

If you’d like to give it a try, check out these instructions on the Make Magazine website.

Hooded Oriole at my hummingbird feeder…

June 26, 2016 | My Projects, Photography | By: Mark VandeWettering

Last year, I bodged together a motion detecting camera to photograph hummingbirds at my hummingbird feeder. But it was always a temporary hack. We had some difficulty with the ants that discovered the feeder, and we discontinued the experiment.

I had a post that I could hang some feeders from, and decided to fill a planter with cement and embed the post so I could move it around and hose it down easily. It’s working pretty well: last weekend we finished it, and have already had to refill the feeder. I think I’ve identified at least three to four hummingbirds who are feeding there, although they seem quite territorial, and one of the larger ones often scares off the smaller ones.

But he doesn’t seem to bother this guy:

yellow

I’m not much of a bird watcher, but a little googling suggests to me that he’s a Hooded Oriole. They seem to like the sugar water from hummingbird feeders, and slurp up a fair amount of this stuff when they land. I’ve seen a female of the species as well, who is a bit paler and lacks the black markings surrounding the eye.

I’ll try to get the motion detecting camera up sometime in the next few weeks.

J1a system on a Lattice ICESTICK40

June 22, 2016 | FPGA | By: Mark VandeWettering

Long time readers of this blog might remember that I received a Gameduino board designed by James Bowman. I used it to construct ANGST, an Arduino and Gameduino satellite tracking project. James did all the heavy lifting: the Gameduino uses a Xilinx FPGA to implement an Arduino shield that can generate graphics and sounds. To do so, it actually implements a “soft processor”, a very simple CPU core designed to execute the Forth Programming Language. I enjoyed goofing around with it, but it’s been sitting in a box for quite a while.

A couple months ago, I remember hearing about an interesting project called Project IceStorm. One of the things that has kept me from tinkering with FPGAs is that the development environments are proprietary and big. Really big. Wrapping my head around them just didn’t seem like fun. But Project Icestorm tries to apply open source methodology to FPGA programming. They reverse engineered the bitstream used by a simple family of FPGAs made by Lattice Semiconductor. The result is a complete set of tools to code logic designs in Verilog, compile, place, route and download them to a Lattice FPGA board. What’s doubly cool is that James took the core of his J1a processor and adapted it for a very cheap Lattice IceStick development board. Compared to some other FPGA boards, the Lattice ICE40 chips are pretty limited, but the J1a is a pretty good fit, and now with Project IceStorm, you can compile and download directly to the board, and have a small Forth base system running without any extra hardware.

I went ahead an ordered one of the boards, and following the instructions on James’ website, I went ahead and built the code and successfully installed in on my $21 ICESTICK. Initially, I had some trouble running the LED blink test: three of the leds worked fine, but two wouldn’t seem to light. Eventually, I tried updating the “yosys” software and recompiling it, and after that, it worked as expected. I’ve never done any Verilog programming before, but having this setup seems to make it seem more tractable than it has before. I’m dusting off the largely unused Verilog books I have on my shelf, and am thinking of trying something simple like a digital clock as my first try. I suspect I’ll outgrow the ICESTICK pretty quickly, but until I do, I bet I am going to learn a lot.

James does a better job describing his system than I could, so here’s a link to his video and his page describing the system. Thanks to Ken Boak for also drawing my attention to this project.

James’ page on J1a SwapForth

My Fizz Buzz solutions…

May 26, 2016 | Programming Languages, Rants and Raves | By: Mark VandeWettering

Joel Grus blogged about a job interview where he was asked about the ridiculous Fizz Buzz question that apparently some companies use to weed out complete frauds from their job interview process. The task is to create a program which prints the numbers from 1 to 100, but where all numbers which are a multiple of three are replaced with “fizz”, all numbers which are multiples of five are replaced with “buzz” and all numbers which are multiples of both three and five are replaced by “fizzbuzz”.

Joel somewhat comically decided to use the TensorFlow framework and solve it with machine learning. Go read his post, it’s pretty comical. Well, if you are a programming geek, it will seem comical.

For the non programmers in my audience (are there some?) this is a trivial program to write. If a programmer can’t bust out a solution to this in a minute or two, they likely have no business calling themselves a programmer. Here’s my 30 second solution (I type moderately slow):

#include <stdio.h>

int 
main()
{
    int i ;
    for (i=1; i<=100; i++) {
        if (i % 15 == 0) {
            printf("fizzbuzz\n") ;
        } else if (i % 3 == 0) {
            printf("fizz\n") ;
        } else if (i % 5 == 0) {
            printf("buzz\n") ;
        } else {
            printf("%d\n", i) ;
        }
    }
    return 0 ;
}

No doubt there are some practitioners in the audience who think that this inefficient, because I compute multiple modulo operations per loop iteration. I’d probably argue that this is short and clear, and until profiling revealed it to be a performance problem, I wouldn’t change it. If people insisted that I do a single modulo per loop iteration, I’d probably replace it with something like:

#include <stdio.h>

int 
main()
{
    int i ;
    for (i=1; i<=100; i++) {
        switch (i % 15) {
        case 3:
        case 6:
        case 9:
        case 12:
            printf("fizz\n") ;
            break ;
        case 5:
        case 10:
            printf("buzz\n") ;
            break ;
        case 0:
            printf("fizzbuzz\n") ;
            break ;
        default:
            printf("%d\n", i) ;
            break ;
        }
    }
    return 0 ;
}

I’d submit that it is much less clear, but not too bad. I’d probably add a comment to explain the higher level idea.

If we are allowed two modulo calls per iteration, could do it this way:

int
main()
{
    int i ;
    for (i=1; i<=100; i++) {

        bool mul3 = (i % 3 == 0) ;
        bool mul5 = (i % 5 == 0) ;

        if (mul3 && mul5) {
            printf("fizzbuzz\n") ;
        } else if (mul3) {
            printf("fizz\n") ;
        } else if (mul5) {
            printf("buzz\n") ;
        } else {
            printf("%d\n", i) ;
        }
    }
    return 0 ;
}

I used boolean variables, which I think reads a little better, but you could obviously use integers.

What if you don’t want to any modulus calls? Well, you could use a state machine…

#include <stdio.h>

int 
main()
{
    int i = 1 ;
    int state = 1 ;

    while (i <= 100) {
        switch (state) {
        case 3:
        case 6:
        case 9:
        case 12:
            printf("fizz\n") ;
            break ;
        case 5:
        case 10:
            printf("buzz\n") ;
            break ;
        case 15:
            printf("fizzbuzz\n") ;
            state = 0 ;
            break ;
        default:
            printf("%d\n", i) ;
        }
        state ++ ;
        i++ ;
    }
    return 0 ;
}

I hope I never have an interview where this is the kind of question I get asked.

Shower (or should I say “cow-er”) Thought of the Day…

May 25, 2016 | My Projects | By: Mark VandeWettering

I just recently found out about the /r/showerthoughts subreddit, where people vote on pithy sayings. I thought this might be a fun thing to have to replace the aging and relatively static “fortune” file that I use. I used the Python “PRAW” library to fetch the top entry for the day, and then optionally pass it to the terrific “cowsay” program for formatting.

Here’s the tiny, nearly trivial code, whose code includes an example of the output of “./shower –cow”

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# a program for fetching texts from Reddit's /r/showerthoughts reddit.
#  _________________________________________
# / The guy who said “Look! Up in the sky!  \
# | It’s a bird!” in the Superman intro was |
# \ strangely excited to see a bird...      /
#  -----------------------------------------
# \   ^__^
#  \  (oo)\_______
#     (__)\       )\/\
#         ||----w |
#         ||     ||

# Written by Mark VandeWettering, no rights reserved.

import sys
import subprocess
import argparse
import textwrap
import praw

parser = argparse.ArgumentParser(description = 'Fetch shower thoughts from reddit.')
parser.add_argument('--cow', action='store_true',
                help='pipe output through cowsay')
parser.add_argument('--cowstyle', dest='cowstyle', nargs=1, default=['default'],
                help='style passed to cowsay')
args = parser.parse_args()

r = praw.Reddit('shower')
s = r.get_subreddit('showerthoughts')

submissions = s.get_top_from_day(limit = 1)


for submission in submissions:
        if args.cow:
            ps = subprocess.Popen(['cowsay', '-f', args.cowstyle[0]], shell=False, stdin=subprocess.PIPE)
            ps.stdin.write(submission.title.encode('utf-8'))
            ps.stdin.close()
            ps.wait()
        else:
            for l in textwrap.wrap(submission.title, 60):
                print ("\t%s" % l).encode('utf-8')

Some random pictures from the Maker Faire…

May 21, 2016 | My Projects | By: Mark VandeWettering

Code for generating a random Latin square…

May 17, 2016 | Games and Diversions, My Projects, Puzzles | By: Mark VandeWettering

The other day I mentioned that generating random Latin squares was a bit more complicated than I thought, and that an algorithm by Jacobson and Matthews was the way that people typically did it. I worked up this implementation based on a couple of different descriptions of the algorithm (the original paper was behind a paywall). The code below simply generates a random DIMxDIM Latin square using their algorithm. I haven’t done extensive testing, but it appears to mostly work. I did run a test where I generated one million 4×4 matrices, and found that it generated all 576 different matrices in approximately the same propertion, so it appears to at least be roughly operational. I’ll eventually merge the code with my nascent KenKen generator.

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

/*
 * rls.c
 *
 * A straightforward implementation of the algorithm by Jacobson and 
 * Matthews, _Generating uniformly distributed random Latin square_,
 * Journal of Combinatorial Design, 1996.
 *
 * I actually couldn't find the original paper, so this is an implementation
 * based upon other descriptions of the algorithm.
 *
 * Written by Mark VandeWettering.
 *
 */


#define DIM (6)

typedef struct t_incidence_cube {
    int s[DIM][DIM][DIM] ;
} IncidenceCube ;


void
InitIncidenceCube(IncidenceCube *c)
{
    int i, j, k ;

    /* First, zero the cube */
    for (i=0; i<DIM; i++)
        for (j=0; j<DIM; j++)
            for (k=0; k<DIM; k++)
                c->s[i][j][k] = 0 ;

    /* And then dump ones in the right place... */
    for (i=0; i<DIM; i++)
        for (j=0; j<DIM; j++)
            c->s[i][j][(i+j)%DIM] = 1 ;
}

void
PrintIncidenceCube(IncidenceCube *c)
{
    int i, j, k ;

    for (i=0; i<DIM; i++) {
        for (j=0; j<DIM; j++) {
            for (k=0; k<DIM; k++) {
                if (c->s[i][j][k]) {
                    printf("%2d ", k+1) ;
                    break ;
                }
            }
        }
        printf("\n") ;
    }
    printf("\n") ;
}

void
CompactPrintIncidenceCube(IncidenceCube *c)
{
    int i, j, k ;

    for (i=0; i<DIM; i++) {
        for (j=0; j<DIM; j++) {
            for (k=0; k<DIM; k++) {
                if (c->s[i][j][k]) {
                    printf("%01d", k+1) ;
                    break ;
                }
            }
        }
    }
    printf("\n") ;
}

void
ShuffleIncidenceCube(IncidenceCube *c)
{
    int i, j ;

    for (i=0; i<DIM*DIM*DIM; i++) {
        
        // Assume we have a "proper" matrix...
       
        // Pick a random zero from the incidence cube... 
        int rx, ry, rz ;
        do {
            rx = lrand48() % DIM ;
            ry = lrand48() % DIM ;
            rz = lrand48() % DIM ;
        } while (c->s[rx][ry][rz]) ;

        int ox, oy, oz ;

        for (j=0; j<DIM; j++) {
            if (c->s[j][ry][rz] == 1)
                ox = j ;
            if (c->s[rx][j][rz] == 1)
                oy = j ;
            if (c->s[rx][ry][j] == 1)
                oz = j ;
        }

        // do the +/- 1 move...  
        // These are all square with zeros in them...
        c->s[rx][ry][rz] ++ ;
        c->s[rx][oy][oz] ++ ;
        c->s[ox][ry][oz] ++ ;
        c->s[ox][oy][rz] ++ ;

        // These all have ones, except for maybe the last one...
        c->s[rx][ry][oz] -- ;
        c->s[rx][oy][rz] -- ;
        c->s[ox][ry][rz] -- ;
        c->s[ox][oy][oz] -- ;

        while (c->s[ox][oy][oz] < 0) {

            rx = ox ;
            ry = oy ;
            rz = oz ;

            // Pick one of the two 1's that are in conflict
            if (drand48() < 0.5) {
                for (j=0; j<DIM; j++) {
                    if (c->s[j][ry][rz] == 1) {
                        ox = j ;
                    }
                }
            } else {
                for (j=DIM-1; j>=0; j--)  {
                    if (c->s[j][ry][rz] == 1) {
                        ox = j ;
                    }
                }
            }

            if (drand48() < 0.5) {
                for (j=0; j<DIM; j++) {
                    if (c->s[rx][j][rz] == 1) {
                        oy = j ;
                    }
                }
            } else {
                for (j=DIM-1; j>=0; j--)  {
                    if (c->s[rx][j][rz] == 1) {
                        oy = j ;
                    }
                }
            }

            if (drand48() < 0.5) {
                for (j=0; j<DIM; j++) {
                    if (c->s[rx][ry][j] == 1) {
                        oz = j ;
                    }
                }
            } else {
                for (j=DIM-1; j>=0; j--)  {
                    if (c->s[rx][ry][j] == 1) {
                        oz = j ;
                    }
                }
            }
          
            // do the +/- 1 move...  
            // These are all square with zeros in them...
            c->s[rx][ry][rz] ++ ;
            c->s[rx][oy][oz] ++ ;
            c->s[ox][ry][oz] ++ ;
            c->s[ox][oy][rz] ++ ;

            // These all have ones, except for maybe the last one...
            c->s[rx][ry][oz] -- ;
            c->s[rx][oy][rz] -- ;
            c->s[ox][ry][rz] -- ;
            c->s[ox][oy][oz] -- ;
        }

    }
}

int
main()
{
    IncidenceCube c ;
    int i ;

    srand48(getpid()) ;
    InitIncidenceCube(&c) ;
    ShuffleIncidenceCube(&c) ;
    PrintIncidenceCube(&c) ;
    return 1 ;
}

Atinlay Aresquares…

May 16, 2016 | Games and Diversions, Puzzles | By: Mark VandeWettering

My last post dealt with a solver for KenKen puzzles. Once you have one of those, then the obvious thing to work on next (in your copious spare time) is a generator for KenKen puzzles. It didn’t seem too hard. You’d begin by generating a random Latin square, then divide it up into “cages”, assign an operator to them, and then see if that has a unique solution. If it doesn’t, well, try again.

But it turns out that each of these steps hides inner difficulties, as well as a certain amount of mathematical beauty. Tom and I were discussing the first bit (generating random Latin square) over lunch, and I thought I’d summarize some of our discussion.

First of all, consider the following “canonical” Latin square of order 4:

1 2 3 4
4 1 2 3
3 4 1 2 
2 3 4 1

It’s pretty easy to generate this Latin square, and it’s pretty easy to generate other Latin squares by swapping either rows or columns. But the question is, can I generate all other Latin squares from this one by doing row and column swap operations?

Tom assured me that the answer was no, which wasn’t at all apparent to me until he presented an interesting example, so I thought I would summarize some of the ideas here. My presentation will take a slightly different path than our discussion, but it ends in the same place.

Let’s consider each square to have a canonical form, where the first row and first column are in sorted order. It should be relatively obvious that you can place any matrix into this form by a series of row and column operations. For example, the matrix above can be placed in canonical form by swapping the second and fourth row.

1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3 

But let’s consider a different matrix in canonical form formed by swapping 1 and 3 in rows 2 and 4.

1 2 3 4
2 1 4 3
3 4 1 2 
4 3 2 1 

We can’t convert this matrix into the previous one by only swapping rows and columns. Thus, if we try to generate a random Latin square by just beginning with a canonical one, there are possible Latin squares which can never be generated by just swapping row and column operations. Too bad, since this is really easy to implement.

Another easy thing to implement would be to just generate all possible Latin squares, store them in a table, and select one at random. That doesn’t seem too bad, until you consider that there are 812,851,200 possible Latin Squares to consider. Sure, disks are big, but that seems excessive.

It turns out that the algorithm that most people seem to use is the from 1996 by Jacobson and Matthews, which is hard to find online as a full paper. It uses a similar idea, but instead of swapping full rows and columns, it applies a different operator that mutates a given Latin square, and in the limit produces a distribution which is the same as the random distribution. It’s a little tricky to understand, but I am going to try to have an implementation in Python later tonight.

Here’s a report that provides some details and the skeleton of an implementation in Java.