Debugging my Anet A8 hot bed…

As in most things, whether you achieve success has a lot to do with what connections you have. And this is true of my somewhat unreliable Anet A8 3D printer more than most.

My printer had been down for a month while I worked on getting a new hot end installed properly. It wasn’t so much that it was difficult, but that it simply took time to get the new parts, find an appropriate crimping tool for the thermistor, and install the new head. Mind you, reassembling the MK8 seems to be more difficult than you would think, but I am getting better at it.

I have been thinking of doing a hot end replacement to a new Bowden extruder, so I thought that while the iron was hot (so to speak) I would print the necessary brackets so I would have them on hand when I felt like that kind of tinkering. I got the stepper motor bracket printed, and was printing the necessary bracket to mount on the X-axis when I had the print fail because of a THERMAL RUNAWAY error message. A bit of debugging revealed that there was a problem not with the hot end, but with the heated bed. In particular, it seemed like it was unable to come to temperature. The controller basically jammed the current on full blast, but it seemed to stabilize at around 38 degrees Celsius instead of the desired 50 degrees.

That was where I left it a week ago.

Finally today I decided to disassemble the hot bed and see what the issue is. My suspicion was that as with the hot end, a thermistor had failed (or perhaps just become dislodged) and was no longer reading properly. I thought I’d remove the hot bed so I could examine the underside so I could see if there was any obvious problem. To remove the hot bed, you pull the four leveling bolts at the four corners, and disconnect the connector.

Looking on the underside, you can see the connector has six pins. There are two positive, two negative and two pins which go to the thermistor. You can order replacements fairly easily, for $13-$20.

But back to my broken hot bed.

Like 99% of all problems, it was pretty obvious once I looked. Here is a picture of this connector:

It may not be obvious in this picture, but the left most pin (wired to positive) is pretty oxidized and gray. Looking at the corresponding socket on the plug, it also appears oxidized and gray.

Normally, the resistance of the hot bed is supposed to be around 1.2 ohms. At 12V, that means that the bed should draw 10 amps and therefore about 120w. But if the connector adds just one more ohm of resistance, it basically halves the available power, and the bed may not heat very effectively. That’s what I’m thinking of doing.

Apparently these connectors do fail fairly often because they aren’t really rated for as much current as is passing through them, and they also aren’t really designed for a connection which flexes. I think what I’m going to do is remove the connector entirely and solder the wires directly to the pins. I’ll probably have to wait until this weekend.

3DPrint Wiki on replacing the Hot Bed connector

I might also take the time to do the MOSFET upgrade that people recommend for additional safety.

pinMode v. digitalWrite: what’s with this use (abuse?) of internal pullups?

This post is the kind of round about post you get first thing in the morning.   I’ll get to the title question at the end.

This morning, I was interested in doing a tiny bit of tinkering. I had found one of these 4 digit 7 segment LED displays while digging around for something else. You can get these modules for about $2.50 from banggood, and potentially for as little as a buck on eBay.

A little over a week ago, I was tinkering with a WeMOS D1 Mini board that I had acquired, and decided to port my Plan-13 library to it. Long (long long) time readers may remember some years ago that I wrote this code to predict the position of satellites, first in Python, but then ported it to C and had it running on the Arduino as part of my ANGST (Arduino ‘n Gameduino Satellite Tracker) project. But that project had a number of shortcomings:

  • It was fairly complicated, and required a number of additional add-ons to work.  I used the Gameduino to generate graphics, had an external RTC and EEPROM to store orbital data, and used an optical shaft encoder to move around.  Yes, it was attractive and fun, but not cost effective.
  • It had no easy way to update orbital elements.  You had to connect it to a PC and reprogram it with new orbital elements each time you needed an update.

But these WeMOS boards are built around the ESP8266 modules, which have a number of advantages:

  • They are based around an 80Mhz 32 bit processor, instead of a 16Mhz 8 bit processor.
  • They have 4Mbytes of flash memory.  You can easily configure some small part of that to serve as a miniature file system, ample to store orbital elements without any additional hardware.
  • They are cheap: around $5.
  • And most intriguingly: they have WiFi. 

So, I worked on the spiritual descendent of ANGST.   Using the platformio system I moved a copy of my Plan13 library to a new project, and started tinkering.   As of now, the project:

  • Wakes up and connects to my local WiFi network
  • Establishes a connection to an NTP server, so I can get the time
  • Connects to Celestrak and downloads the latest orbital elements for the ISS
  • Predicts the next three passes from my home location
  • And then enters a loop, predicting the sub-satellite latitude and longitude, its location relative to some major world cities, and if it is above the horizon, then the azimuth and altitude of the satellite.

Here is the current data as I write this:

But the one thing it did not have until this morning was an external display.  Hence, the TM1637, and a little tinkering.

Time is in GMT, but eventually I will also have it have the option of using local time (it is more convenient to use GMT for the satellite computations.)

To get this to work, I could have dusted off the work to drive the similar TM1640 based displays that I used in another project, but I thought that I’d use a standard library instead.   The platformio system has a pretty nifty library manager, so I searched for a library, found one (cool!) and it claimed compatibility with the ESP8266.  Neat.

So I read some of the example code, patched it to output the time in the main loop(), and tried it.

It didn’t work.

I double-checked connections.

It didn’t work.

I tried their example.

It didn’t work.  The displays remained dark.

Grumble.  I opened up the code and tried to see what was going on.   It didn’t take me too long to figure out what was going on:

Here is a link to the code, and a screen grab of the offending lines:

Link to the source on github

It’s not exactly my first rodeo, so I was immediately suspicious when I saw that the initializer set the mode for the two pins to INPUT, rather than OUTPUT, but then immediately wrote to them.  That doesn’t seem right, does it?

Well, this isn’t even my second rodeo.  I know that Arduino’s ATMega328 processor has internal pull up resistors, and I’ve seen odd code which used pinMode to swap back and forth between high and low, not using pinMode.

But the ESP8266 (thought I) doesn’t have internal pull ups.   I’m pretty sure that’s true, but I never got to verify it, because all of a sudden, with no change whatsoever, my program started working.

hate it when that happens. 

It’s been that kind of a week.

But it made me think about how this works.  Here is my guess, and I’d appreciate corrections.

During initialization, it sets pinMode to INPUT, and writes a LOW value to the data pin.   Even though we’ve written a LOW, the pin is pulled HIGH by the action of the (external) pull up resistor.

When the driver wishes to shift the output pin to LOW, it uses pinMode() to shift the type for the pin to OUTPUT.   When it wants it to be high, it sets pinMode() to INPUT.

I find this odd in a couple of ways:

  • It is not any shorter or more efficient than using digitalWrite.
  • It is certainly no clearer.

Is there something I’m missing about why you would code this stuff this way?

Of course, I wouldn’t have dug into this code at all had I not had a mysterious (and fleeting) failure at the beginning, so I am not sure how it really matters.

Addendum:  While I was typing this, the ISS did a 65 degree elevation pass which was captured thusly.  I only then noticed that it was producing duplicate messages for each five second message.  Must have goofed when I installed the code to blink the clock’s “colon” segments.  I’ll get it sorted later.

 

Musing about a 2 dimensional delta robot…

First of all, if anyone is still swinging by this blog, yes, I’m still alive. While I haven’t exactly been prolific in my leisure activities, they haven’t stopped entirely. I worked on some simple embedded development for the hackaday.io 1K code challenge, which you can see on my hackaday.io page, and which hopefully I’ll write up here. I’ve got some additional projects in mind, so perhaps with a little extra effort on my part I’ll be getting back to more regular entries.

One of the things that has been kicking around in my head is to “make something that moves.” In particular, I’ve long been interested in gadgets like plotters, 3d printers, laser cutters and CNC machines. A few months ago on a whim, I ordered a CNC shield and Arduino so that I could begin to think about maybe creating a project which drives some steppers around to trace some pattern. I doubt that I possess the skills or know-how to do a good job of making a real CNC machine, but I kind of liked the idea of making a plotter. I started to work on the basic mechanical design of a simple 2D gantry. But frankly, I began to balk at the idea. You need two different sets of parallel ways, which seemed large and cumbersome, and each axis is different.

At the Maker Faire I had observed some simpler setups which generally go under the name of “Drawbots”. You can see an excellent write-up here on the “Death To Sharpie” page. I liked the idea a lot: it uses two steppers and the setups for each are symmetric. Each one winds and unwinds a chain, and the pen is suspended at the intersection of the two chains. In this incarnation, the pen doesn’t even have a separate control: it is simply drug around the poster board, leaving a trail wherever it goes. Pretty cool! I must admit though, I thought his software setup (laptop + Raspberry Pi + Arduino?) was a little complicated, and I’d probably enjoy working on the control software anyway.

But I was discussing this with my constant lunchtime companion Tom, discussing catenary curves and the like, and he basically said “why don’t you just use solid arms, making a 2D analog of the 3D delta robots you see in 3D printers?”

An awesome idea! One of the cool things about constructing a delta robot is that it consists of three essentially identical pillars. Yes, the three pillars all move slightly differently, but that is really a software issue, not a hardware one. A few moments of thought and I realized that you could make a pretty spiffy 2D version, and the math would actually be pretty easy.

So, in between tasks, I worked out the necessary quadratic equations, and created this gif that will demonstrate how the motion works.

The work space is the unit-size gray square at the bottom. It is bracketed by two rails, each of length two. Each has a carriage which runs along its side, and pins one end of a fixed arm (again, of unit length) which are held together in the center by a pin, which is where the pen will be. As you drive the red and green carriages back and forth, the intersection moves back and forth. It isn’t hard to see that the pen can reach any location in the unit square at the bottom.

It isn’t quite as compact as the typical drawbot, but I can’t help but think there are some serious mechanical advantages to setting up a bot this way. It should not be very hard to create an interpreter that could run on the Arduino that would take a small subset of G code and some basic scaling and rate information, and drive a pair of steppers to create this kind of a robot. I’ve never written code exactly like this before. It should be fun.

Stay tuned.

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

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…

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.

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

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…

Code for generating a random Latin square…

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 ;
}

KenKen puzzle solver…

Lately, my lunch hours have been spent working on the NYT Crossword with my lunch companion Tom. While I find that the Thursday crosswords are often beyond my ability to do in the allotted time, between the two of us, more often than not we manage to plow through them. Slowly over time, we’ve begun to solve them slightly quicker, so I’ve branched out to doing the KenKen puzzles.

For those of you who haven’t seen these before, you can learn about them on their official website here. The 4×4 ones are usually pretty easy, but the last couple days have done some 6×6 puzzles have been shockingly hard. So much so, that today I got to this state on today’s puzzle:

IMG_1128

Yes, I was using pen. And I made a mistake, although I can’t see what I was thinking when I did. And because I made a mistake, I couldn’t spot it, and I was hung up. The “4” in first column was wrong. I knew it could not be a 6 or 1, or a 3, or a 4, but for some reason I thought that the final column couldn’t be 4 and 3, but..

Never mind, it doesn’t matter what the mistake was.

By the end up twenty minutes I was annoyed, knew I had made a mistake, but decided to give into the urge to write a program to solve it. How long could it take?

Well, the answer was about 27 minutes.

This program doesn’t have any interface or flexibility, everything is hard coded. Basically it uses backtracking and fills in each square in order from bottom left to top right, and as the top most, right most square of each outlined area is finished, it checks to make sure that the sums/differences/whatever for the filled in region sum to the right values. I didn’t know how I was going to encode those constraints, so I just ended up writing a function that computes the proper constraint. This is not really the right way to do it: it’s error prone and requires recompilation of the code to change the puzzle. But it does work fairly well, once you type the expressions in correctly.

Once I got those straightened out, it blats out the solution in less than 1 millisecond on my desktop.

+---+---+---+---+---+---+
| 6 | 1 | 5 | 2 | 4 | 3 |
+---+---+---+---+---+---+
| 2 | 6 | 1 | 3 | 5 | 4 |
+---+---+---+---+---+---+
| 1 | 4 | 6 | 5 | 3 | 2 |
+---+---+---+---+---+---+
| 3 | 2 | 4 | 6 | 1 | 5 |
+---+---+---+---+---+---+
| 5 | 3 | 2 | 4 | 6 | 1 |
+---+---+---+---+---+---+
| 4 | 5 | 3 | 1 | 2 | 6 |
+---+---+---+---+---+---+

1 solutions found

It points out that the 4 should have been a 2 (IDIOT!) and then it all works out.

The code is 178 lines long, but is not particularly pretty/short/adaptable. Some day, I’ll have to tidy it up and make a better version.

But in case people find this stuff interesting, here it is. Remember: 27 minutes to write.

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

/*
 * kenken.c
 *
 * A program inspired by a particular tough 6x6 puzzle that appeared
 * on Thursday, May 11, 2016, which Tom Duff and I could not appear to
 * get the answer to during our lunch hour.  I thought that it was possible
 * that I could write a program to solve the puzzle in less than an hour.
 *
 * Hence, this code.
 *
 */

int total = 0 ;

#define DIM     (6)

typedef struct t_puzzle_state {
    int sq[DIM][DIM] ;
    int r[DIM] ;            // bitflag for values left in rows...
    int c[DIM] ;            // bitflag for values available in columns
} PuzzleState ;


void
PrintPuzzleState(PuzzleState *p)
{
    int i, j ;

    printf("+") ;
    for(j=0; j<DIM; j++)
        printf("---+") ;
    printf("\n") ;

    for (i=0; i<DIM; i++) {
        printf("|") ;
        for (j=0; j<DIM; j++) {

            if (p->sq[DIM-1-i][j])
                printf(" %1d |", p->sq[DIM-1-i][j]) ;
            else
                printf("   |") ;
        }
        printf("\n+") ;
        for(j=0; j<DIM; j++)
            printf("---+") ;
        printf("\n") ;
    }
    printf("\n") ;
}

void
InitializePuzzleState(PuzzleState *p)
{
    int i, j ;

    memset((void *) p, 0, sizeof(*p)) ;

    for (i=0; i<DIM; i++) {
        for (j=1; j<=DIM; j++) {
            p->r[i] |= (1<<j) ;
            p->c[i] |= (1<<j) ;
        }
    }
}

void
HardcodePuzzleState(PuzzleState *p, int r, int c, int val)
{
    p->sq[r] = val ;
    p->r[r] &= ~(1<<val) ;
    p->c &= ~(1<<val) ;
}

#define SQUARE(i, j)    ((i)*DIM+(j))
#define ABS(x)          ((x)<0?(-(x)):(x))

int
ConstraintSatisfied(PuzzleState *p, int i, int j)
{
    switch (SQUARE(i,j)) {
    case SQUARE(0,1):
        return ABS(p->sq[0][0] - p->sq[0][1]) == 1 ;
    case SQUARE(0,2):
        return p->sq[0][2] == 3 ;
    case SQUARE(1, 3):
        return (p->sq[0][3]+p->sq[1][3]) == 5 ;
    case SQUARE(1, 4):
        return (p->sq[0][4] * p->sq[0][5] * p->sq[1][4]) == 72 ;
    case SQUARE(2, 2):
        if (p->sq[2][2] == 2 * p->sq[1][2])
            return 1 ;
        if (p->sq[1][2] == 2 * p->sq[2][2])
            return 1 ;
        return 0 ;
    case SQUARE(2, 4):
        return ABS(p->sq[2][4] - p->sq[2][3]) == 5 ;
    case SQUARE(3, 1):
        if (p->sq[3][1] == 2 * p->sq[2][1])
           return 1 ;
        if (p->sq[2][1] == 2 * p->sq[3][1])
           return 1 ;
        return 0 ;
    case SQUARE(3, 5):
        return (p->sq[3][5]+p->sq[2][5]+p->sq[1][5]) == 8 ;
    case SQUARE(4, 2):
        return ABS(p->sq[4][2] - p->sq[4][1]) == 5 ;
    case SQUARE(4, 3):
        return p->sq[4][3] == 3 ;
    case SQUARE(4, 4):
        return (p->sq[4][4]+p->sq[3][2]+p->sq[3][3]+p->sq[3][4]) == 19 ;
    case SQUARE(5, 1):
        return (p->sq[4][0]*p->sq[5][0]*p->sq[5][1]) == 12 ;
    case SQUARE(5, 4):
        return (p->sq[5][2]+p->sq[5][3]+p->sq[5][4]) == 11 ;
    case SQUARE(5, 5):
        return (p->sq[5][5]+p->sq[4][5]) == 7 ;
    default:
        return 1 ;
    }

    return 1 ;
}

void
SolvePuzzleState(PuzzleState *p, int i, int j)
{
    int v ;

    if (i >= DIM) {
        PrintPuzzleState(p) ;
        total ++ ;
        return ;
    }
        
    int pval = p->r[i] & p->c[j] ;

    for (v=1; v<=DIM; v++) {
        if ((pval & (1<<v)) == 0)
            continue ;
        // Try to place v in sq[i][j] ;
        p->sq[i][j] = v ;

        if (ConstraintSatisfied(p, i, j)) {
            p->r[i] &= ~(1<<v) ;
            p->c[j] &= ~(1<<v) ;

            int ni, nj ;
            nj = j + 1 ;
            if (nj < DIM) {
                ni = i ;
            } else {
                ni = i + 1 ;
                nj = 0 ;
            }

            SolvePuzzleState(p, ni, nj) ;

            p->r[i] |= (1<<v) ;
            p->c[j] |= (1<<v) ;
        } 
    }
    p->sq[i][j] = 0 ;
}

main()
{
    PuzzleState p ;
    InitializePuzzleState(&p) ;
    // HardcodePuzzleState(&p, 0, 2, 3) ;
    // HardcodePuzzleState(&p, 4, 3, 3) ;

    SolvePuzzleState(&p, 0, 0) ;
    fprintf(stderr, "%d solutions found\n", total) ;
}

Solving the N queens problem, again…

Backtracking is a better technique, obviously. The version from earlier today was actually not very clever, and took half an hour to find the 73,712 solutions to the 13×13 checkerboard. This version is less code (just 91 lines, compared to 107 for yesterdays) and finds all the 13×13 solutions in just 2.5 seconds (a speed up of around 720x).

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

#define MAX_N   (15)

int board[MAX_N] ;
int total = 0 ;

void
print(int board[MAX_N], int n)
{
    int i, j ;

    printf("+") ;
    for (i=0; i<n; i++) {
        printf("-") ;
        if (i < n-1)
            printf("+") ;
    }
    printf("+\n") ;

    for (i=0; i<n; i++) {
        printf("|") ;
        for (j=0; j<n; j++) {
            if (j == board[i])
                printf("O") ;
            else
                printf(" ") ;
            if (j < n-1)
                printf("|") ;
        }
        printf("?\n") ;
        if (i < n-1) {
            printf("+") ;
            for (j=0; j<n; j++) {
                printf("-") ;   
                if (j < n-1) 
                    printf("+") ;       
            }
            printf("+\n") ;
        }
    }

    printf("+") ;
    for (i=0; i<n; i++) {
        printf("-") ;
        if (i < n-1)
            printf("+") ;
    }
    printf("+\n\n") ;
}

#define abs(n) ((n)<(0)?(-(n)):(n))


void
place(int r, int n)
{
    int i, j ;
    if (r == n) {
        // We filled in all rows...
        total++ ;
        print(board, n) ;
    } else {
        for (i=0; i<n; i++) {
           board[r] = i ;
           for (j = 0; j<r; j++) {
                if (board[j] == board[r])
                    goto skipit ;
                if (abs(board[j]-board[r]) == abs(j-r))
                    goto skipit ;
           }
           place(r+1, n) ;
skipit:
           continue ;
        }
    }
}

int
main(int argc, char *argv[])
{
    int n = atoi(argv[1]) ;
    place(0, n) ;
    if (total == 0)
        fprintf(stderr, "There are no solutions for the %dx%d board..\n", n, n) ;
    else
        fprintf(stderr, "There is %d solution%s for the %dx%d board.\n", 
                total, total > 1 ? "s" : "", n, n) ;
    return 0 ;
}

Fun.

Solving the N Queens Problem…

A question on Quora set me thinking about solving the N Queens problem, which is to list all ways that N queens can be positioned on an NxN checkerboard such that no queen can attack the other. I seemed to have misplaced my implementation of this that I did in Python, so I decided to do one in C while watching Agents of Shield. The code in general shows the lack of attention, but it does work. It can find all 92 solutions for the 8×8 checkerboard in under one second, but slows down rapidly after that, taking nearly half an hour to find all 73,712 solutions for the 13×13 board.

This program isn’t completely unclever (in fact, I think it is too clever in a way) but it should be properly described as a brute force search, since it generates all N! ways of positioning N queens in different rows, and tests them for diagonals. Thus, it’s runtime is O(N!), which isn’t great. It doesn’t even do backtracking, which would undoubtedly help a great deal.

One good page I found googling this morning is this one by Jeff Somer. His program is much more clever than mine. My estimate is that my program would take well over 100,000 years to count all the positions for a 21×21 board, Jeff’s does it in about a week.

Another cool page is this one, which introduces the idea of “super-queens”, which also capture with the same moves as a knight. Only one unique solution for N=10 exists, which is pretty cool. For higher N, more solutions become possible.

Code is archived here.

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

#define MAX_N   (15)

int board[MAX_N] ;
int total = 0 ;

void
print(int board[MAX_N], int n)
{
    int i, j ;

    printf("+") ;
    for (i=0; i<n; i++) {
        printf("-") ;
        if (i < n-1)
            printf("+") ;
    }
    printf("+\n") ;

    for (i=0; i<n; i++) {
        printf("|") ;
        for (j=0; j<n; j++) {
            if (j == board[i])
                printf("O") ;
            else
                printf(" ") ;
            if (j < n-1)
                printf("|") ;
        }
        printf("?\n") ;
        if (i < n-1) {
            printf("+") ;
            for (j=0; j<n; j++) {
                printf("-") ;   
                if (j < n-1) 
                    printf("+") ;       
            }
            printf("+\n") ;
        }
    }

    printf("+") ;
    for (i=0; i<n; i++) {
        printf("-") ;
        if (i < n-1)
            printf("+") ;
    }
    printf("+\n\n") ;
}

#define abs(n) ((n)<(0)?(-(n)):(n))

void
check(int board[MAX_N], int n)
{
    int col[MAX_N] ;
    int i, j ;

    for (i=n-1; i>=0; i--) {
        col[i] = board[i] ;
        for (j=i+1; j<n; j++) {
            if (col[i] <= col[j]) 
                col[j]++ ;
        }
    }

    // now, check for diagonals.. 
    for (i=0; i<n; i++)
        for (j=i+1; j<n; j++)
            if (abs(col[i]-col[j]) == abs(j-i))
                return ;

    // we have a winner...
    total++ ;
    print(col, n) ;
}

void
place(int i, int n)
{
    if (i == n) {
        // check board 
        check(board, n) ;
    } else {
        int which ;
        for (which=0; which < n-i; which++) {
            board[i] = which ;
            // recurse...
            place(i+1, n) ;
        }
    }
}

int
main(int argc, char *argv[])
{
    int n = atoi(argv[1]) ;
    place(0, n) ;
    if (total == 0)
        fprintf(stderr, "There are no solutions for the %dx%d board..\n", n, n) ;
    else
        fprintf(stderr, "There is %d solution%s for the %dx%d board.\n", 
                total, total > 1 ? "s" : "", n, n) ;
    return 0 ;
}

Streaming to twitch.tv with ffmpeg…

I was trying to figure out how to screencast to twitch.tv using ffmpeg. A couple of hours of tinkering resulted in the following command line which does a bunch of stuff.

  • It captures the X desktop at 15 fps and 1920×1080 resolution.
  • It grabs frames from my webcam (a Logitech Pro 9000) at 320×240 resolution.
  • It then combines the two into a 1024×576 image, with the video overlayed at the top right and a banner at the bottom that displays a couple of lines of text.
  • It then ships it to the twitch.tv server.  If you grab this code, you need to add your own streaming URL for your own channel.
#!/bin/bash

/home/markv/bin/ffmpeg 	\
	-y -thread_queue_size 64 -f x11grab -s 1920x1080 -framerate 15 -i :0.0+0,0 \
	-thread_queue_size 64 -f v4l2 -input_format mjpeg -framerate 5 -video_size 320x240 -i /dev/video0 \
	-filter_complex \
	"[0:v] scale=1024:576, setpts=PTS-STARTPTS  [bg]; \
	 [1:v] setpts=PTS-STARTPTS [fg]; \
	 color=0x336699cc:1024x64, drawtext=textfile=twitch.txt:fontfile=/usr/share/fonts/truetype/dejavu/DejaVuSansMono-Bold.ttf:x=10:y=16:fontsize=16:fontcolor=white [bottom] ; \
	 [bg][fg] overlay=W-w-16:16 [out2]; \
	 [out2][bottom] overlay=0:H-64, format=yuv420p [out]" \
	-map "[out]" \
	-vsync 1 \
	-c:v libx264 -b:v 500k -maxrate 500k -bufsize 1000k -framerate 15 -g 30 -crf 30 -preset fast -pix_fmt yuv420p -tune zerolatency \
	-f flv rtmp://live.twitch.tv/app/live_XXXXXXXX_XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

A few additional notes:

  • The default DNS server for my ISP don’t serve DNS requests for the live.twitch.tv server.   I fixed this by adding the Google DNS servers to my router (8.8.8.8 and 8.8.4.4).
  • The script appears to work pretty well, but sometimes has difficulty starting up.  And, when the script crashes, the remote clients don’t time out for a considerable time.
  • I haven’t tested this extensively.

Buyer beware, but I hope it is useful.

 

Recommendations for tech to create a virtual hacker space?

Most of my hacking occurs in a vacuum: where I sit in my living room or in my home office and toil away silently on projects which occasionally get documented here, but which all too often are just my way of passing the time. On the way to work, I was asking myself what I could do to boost my own excitement about these projects, and provide some incentive to do more, and on a more regular basis.

So, I had an idea which is almost certainly not new: the idea of a virtual hackerspace.

For years, I used to donate my Friday evenings to the Chabot Amateur Telescope Makers workshop. I’d go down and spend three or four hours showing up, seeing who needed help on a telescope project, or I’d bring my own and work on that. I want to create a more generic “workshop network”, where people can meet regularly for a kind of hackerspace parallel play using video conferencing technology.

In some sense, it’s just an extension of Google Hangouts. The idea would be that each participant would have a webcam/microphone setup, and at the appointed time, we could all just open our cameras and mics, say “hi” to one another and then go about our business, potentially sharing our projects or asking questions of the group at large. I’ve mostly used Hangouts for simple one-to-one conversations, and have little experience with larger groups, and didn’t really find any obvious links about how to manage larger groups. Does anyone have any recommendations on how to setup such a network? I am not really interested in creating a “show”, but really more of a set of spaces which encourage mutual collaboration and interest.

I’m willing to entertain other technologies as well, if people have better suggestions.

And, if you would be interested in joining in this kind of “network”, drop me a note here or on twitter (@brainwagon). I’ll try to do an update of what I learn.

More on Caxton Foster’s Blue Architecture…

Okay, it’s been a long time since I wrote anything here. Not really a lot dramatic going on in life, I just have been spending my free time writing for Quora rather than my own blog. But I still am nerding out from time to time. Last night I dusted off an old project of mine and carried it a bit further…

I had written a short post before about a simulator I wrote for Caxton Foster’s “Blue” computer architecture described in his book Computer Architecture. I have the third edition published in 1985. The “Blue” architecture is ridiculously simple: only sixteen instructions, 4096 words of memory, and only one addressing mode. If you click back to my previous post, you’ll see a complete behavioral simulator for it, written in less than an hour.

Somehow this came back up, and I was suddenly intrigued by the idea of trying to write a simple program for it, just to test my ideas about how awful such a machine would be. Ultimately, my goal is to write a simple program that can compute the value of pi to around 100 decimal places. Such a program seems doable, but it’s not a complete cakewalk. But to achieve this, I thought it might be fun to write a simple assembler.

So, I shook the cobwebs that have covered the bits of my brain that understood yacc/lex/bison/flex and wrote a simple assembler for the architecture. It totals only about 250 lines of code, but can handle symbolic labels and all the instructions. It took me about two hours of wall clock time, with my attention split between programming and watching the latest episode of Grimm.

I doubt the assembler is of any real interest, but eventually I’ll get the code onto github.

I then sat down this morning, and wrote this simple program to take the signed value at the memory location VALUE and print it as a signed decimal number. It prints the sign then five digits, with leading zeros if necessary. I didn’t bother to comment
the code, but here it is…

PRINTVALUE:
	LDA VALUE
	JMA NEG
	LDA PLUS
	OUT
POS:
	LDA S0
	STA TMP0
	SRJ DODIGIT
	LDA S1
	STA TMP0
	SRJ DODIGIT
	LDA S2
	STA TMP0
	SRJ DODIGIT
	LDA S3
	STA TMP0
	SRJ DODIGIT
	LDA S4
	STA TMP0
	SRJ DODIGIT
	HLT

DODIGIT:
	IOR JMPBIT
	STA RETURN
	LDA ZERO
	STA DIGIT
LOOP:	LDA VALUE
	ADD TMP0
	JMA DONE
	STA VALUE
	LDA DIGIT
	ADD ONE
	STA DIGIT
	JMP LOOP
DONE:
	LDA DIGIT
	ADD FE
	OUT
RETURN:
	JMP 0

NEG:
	LDA MINUS
	OUT
	LDA VALUE
	XOR ONES
	ADD ONE
	STA VALUE
	JMP POS

VALUE:	.WORD 12323
TMP0:	.WORD 0
DIGIT:	.WORD 0
S0:	.WORD -10000
S1:	.WORD -1000
S2:	.WORD -100
S3:	.WORD -10
S4:	.WORD -1
ZERO:	.WORD 0
ONE:	.WORD 1
ONES:	.WORD $FFFF
JMPBIT:	.WORD $A000
MINUS:	.STRING "-"
PLUS:	.STRING "+"
FE:	.WORD 48

The assembler spits out a series of 16 bit words which can be loaded into my
simulator…

0x602B, 0x9024, 0x6038, 0xC000, 0x602E, 0x702C, 0x8014, 0x602F, 
0x702C, 0x8014, 0x6030, 0x702C, 0x8014, 0x6031, 0x702C, 0x8014, 
0x6032, 0x702C, 0x8014, 0x0000, 0x4036, 0x7023, 0x6033, 0x702D, 
0x602B, 0x102C, 0x9020, 0x702B, 0x602D, 0x1034, 0x702D, 0xA018, 
0x602D, 0x1039, 0xC000, 0xA000, 0x6037, 0xC000, 0x602B, 0x2035, 
0x1034, 0x702B, 0xA004, 0x3023, 0x0000, 0x0000, 0xD8F0, 0xFC18, 
0xFF9C, 0xFFF6, 0xFFFF, 0x0000, 0x0001, 0xFFFF, 0xA000, 0x002D, 
0x002B, 0x0030, 

The data above gets simply compiled into my simulator and runs.

Screen Shot 2016-03-26 at 10.57.16 AM

Okay, so what’s fun to note about this?

There is only a single register, the accumulator. You spend a LOT of time loading things, modifying the value, and storing them back into main memory. There is no “immediate mode”, so you have to create memory locations to store common values like “1” and “0”. DODIGIT is a subroutine, which is called by the SRJ instruction. SRJ puts the PC into the accumulator, and then jumps to the specified address. To “return”, you OR in the bits to the accumulator to form a JMP instruction, and then store that at the end of your subroutine. There is no call stack. Although not demonstrated particularly here, the processor does not implement indexing or indirection. There is also no real condition registers such as CARRY or OVERFLOW, so implementing multi-precision arithmetic might be a challenge.

Foster’s book also details additions to this architecture, eventually becoming INDIGO, an architecture which is rather similar to a PDP-8.

Sure, if you are going to really learn computer archtictures, Patterson and Hennessy is probably a better path, but there is something like of pleasing in this archaic trip down memory lane. My pi computing program will percolate in my brain for a bit, and will find implementation on some other evening.

Addendum: Hackaday recently posted about Al Williams’ FPGA implementation of an architecture which is based upon Foster’s Blue machine. I believe he made a number of changes that make it more practical, but it might be worth looking at. He wrote a monitor, which seems to use opcodes which aren’t compatible with mine.

Addendum2: Pondering it some more throughout the day, it seems difficult to implement my idea of a pi computing program for this virtual machine. All of the algorithms that I can think of require 32 bit numbers, and the Blue architecture simply lacks the capabilities needed to implement it. It also is pretty weak on conditional statements: the only condition that you can branch on is the sign bit of the accumulator.