My Fizz Buzz solutions…

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…

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

Atinlay Aresquares…

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.

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

A couple of cool solar powered FPV planes…

Just a pointer to a cool project which appeared on Hackaday: a solar powered FPV plane that can fly forever (or at least until the sun goes down). Pretty spiffy!

The comments show a link to this solar powered plane developed at ETH:

It was in the air for 81.5 hours, and had a continuous flight distance of 2316km. It’s a slow flyer: average speed is just under 18mph. At the end, you can see that the wind conditions had deteriorated seriously. Pretty nifty.

A story from SIGGRAPH past…

I’ve been meaning to write down this story for a while, because it represents a time when I was booed away from a microphone by a crowd of two thousand people, and I always think that stories like this are fun.

Back in 1996, I attended SIGGRAPH in New Orleans. I remember flying out early and arriving somewhere around 7:00AM and being unable to check into my hotel room, so I went down to the French Quarter and had beignets and coffee. It was a wonderful city for one of my favorite activities: eating. Pixar alumnus and foodie Steve Upstill had given out a list of restaurants in New Orleans for me to try, and I don’t think I had a bad meal the entire week. From gumbo to po’boy sandwiches, it was all amazing and delicious.

But back to the conference..

There was a panel that I attended called “Graphics PCs will Put Workstation Graphics in the Smithstonian”. The panelists were:

  • Sam Uselton, from MRJ, Inc. served as organizer.
  • Michael Cox, from S3
  • Jay Tayborg, from Microsoft
  • Michael Deering, from Sun Microsystems
  • Kurt Akeley, from SGI

It was an interesting discussion, with the first two taking the the side of PCs, and the second two, standing up for the workstations. I had been working in scientific visualization at Princeton, and had then been at Pixar for about five years. My own opinions were that economies of scale would eventually destroy the workstation market. I had worked with high end SGI products, as well as workstations such as Stellar/Ardent/Stardent but had also been tracking the developments in the game world, and to me the writing on the wall was clear.

I remember approaching the microphone and asking a question like “Given what we’ve seen with Moore’s law and the increase in capabilities in microcomputers, and the increasing availability of operating systems like Linux and BSD-based systems,isn’t it reasonable to conclude that the same kind of thing will happen in the graphics market?”

I recall that Akeley and Deering tried to answer with something along the lines of “only workstations have the fast buses/high performance memory subsystems/careful and accurate rasterization that is necessary to do real graphics. I didn’t find that answer particularly helpful and tried to ask a followup and…

Was enthusiastically booed away from the microphone. It was really impressive, to have a couple of thousand people heckle you at once.

But in the end… I think that history points out that I was more or less correct. By no means did I contribute to this trend, but I did recognize it at the time, in a way that the majority of professionals at SIGGRAPH largely did not.

1995 was the apex for SGI, with a market cap of over 7 billion dollars. Ten years later, it was delisted from the NYSE because its stock price had fallen to below one dollar, with a market cap of just $120 million dollars. It was effectively bankrupt in 2006.

Sun would take a different path, riding the dot.com bubble up with its server hardware into the year 2000, and then riding it down to destruction. It never really became a big player in graphics.

Meanwhile, nVidia was formed in 1993 by Huang, Malachowsky and Priem (from AMD, Sun Micro and Sun Micro, respectively). In 1999 they released their Geforce board, which brought hardware with a full transform and light pipeline to the consumer market. They would absorb many other players, and became the destination for a lot of talent who had previously been at SGI. It currently has a market cap of about $18.6 billion dollars.

Mind you, nVidia didn’t pursue a strategy driven entirely by consumer products, and Sun and SGI failed not just because of their graphics strategy. But I do think that I what I said was mostly right, and it didn’t take forever for my prediction to come true.

Another press account of the session.

The summary page from the 1996 SIGGRAPH proceedings

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.

New experiment… Life beyond Comcast…

Today, I finally lost my freaking mind with respect to Comcast.

First of all, some background. I’ve have been a Comcast customer since 1999 when I moved into my house. For the most part, the service itself has been reasonably reliable and effective. I don’t have a lot of technical quibbles with them.

But their customer service makes me absolutely insane.

I am currently paying $269 a month (yeah, I know, right?) for a combination of Internet, TV, and phone (which I didn’t even want, but which was part of some “package” deal that was supposed to save me lots of money, that somehow never really materialized). I have mostly been ignoring it, but I finally decided that if I am paying nearly $3000 a year on television and Internet, I should review my priorities to reduce my bill since I pay for a lot of premium services that I probably don’t really need.

And here is where my irritation begins.

Because if you want to do that, you can’t do it online. In fact, other than determining that someone, somewhere signed me up for some package which has the label “HD XF Premier Bundle” and a somewhat mysterious “Additional Outlet Fee” for $39.00, it has no indication about what Internet speed limits can be be achieved, what channels are included or not included, and most importantly there is no way to actually determine what my options are. In fact, to make any changes to your service, that means talking to a service representative.

And here is where my absolute rage begins.

I hate losing my temper with people. I really do. I like to be easy going and polite. If someone is trying to help me, I try to help them help me. But Comcast service representatives are not there to help you. They are there to sell their package deals, which seem carefully constructed to be as opaque as humanly possible and to extract the maximum amount of money from you that they possibly can.

It’s infuriating, and today my fuse was admittedly short.

To be fair, I probably wasn’t fair. I wanted to a) review each of the charges on my bill and b) decide in each case whether the charge was appropriate, and what my options might be to change it. But the Comcast service representative literally could not do that. She insisted on trying to tell me that there was some other package, with some other price that she could sign me up for that would achieve some other price that was much cheaper. When I said that sounded better, she asked me whether I wanted to sign up for a “commitment” or not, and started explaining that if I signed up for a commitment, then I could not change my service for two years. And I am supposed to decide all of this without an actual itemization of the terms and conditions or even the services that were provided.

And I lost my freaking mind. Expletives were emitted. I was not a gentlemen. And then something that has never happened before, happened.

I had a customer service representative hang up on me.

So, I’m going to do something truly crazy: I’m ditching Comcast. Sonic.net has become available in my neighborhood, and they have more sensible packages available with Direct TV. I imagine that the service that I am going to get is a bit less speedy than Comcast, but I literally don’t care. I literally don’t care if Direct TV is better or worse than Comcast or even cheaper. I just no longer want to be a Comcast customer, and since it appears I don’t have to, I am not going to.

Voting with my feet. I’ll let you all know how it goes.

Quadcopter Survey with my DJI Phantom 2/GoPro

I hadn’t been flying my DJI Phantom 2 since last year (before I herniated two disks in my neck) but I’ve been meaning to take it out and get it in the the air. This week, two different things happened which provided some incentives to get it in the air, for reasons which weren’t entirely frivolous:

  • My new next door neighbor mentioned that there was debris in the drainage ditches up on the hill that drain from his yard to my yard. I thought that it had been cleaned out, so I wanted to be sure, but frankly, hiking up there when the ground is wet is asking for a new herniated disk.
  • I had a small roof leak which caused a call to my roofers to come out and have a peek. They mentioned that I had a fair number of busted tiles on my roof (annoying, perhaps broken by our contractors during last years remodel?).

I hadn’t flown in a while, so I decided that rather than flying over my house, I’d begin by just getting the view of the drainage ditches. I got the copter charged up again, reviewed my checklists, and took it out into the backyard.

Oddly, I heard a familiar droning: one of my neighbors had a quadcopter up doing a high pass over the neighborhood. By the time I was ready though, it had sailed back off to the south. I got it up in the air and tried to get my coordination back. It was a beautiful day for flying.

Here’s a nice high view to the north east from my house, fairly high up.

vlcsnap-2016-01-24-16h43m07s108

But that wasn’t what I was after: I aimed the GoPro down and flew fairly low over my hill to get these pictures. This is the view of the lower of the two drainage ditches. It’s got a little silt in it, but is pretty clear. It might be worthwhile to do a concrete patch of the seam. You can also see a fair number of gopher holes up on the hill.

vlcsnap-2016-01-24-16h42m37s703

The other ditch is at the top of the hill. It actually gets a lot less water, so the silt settles out pretty well up there, and I’ve got some grass growing it. It could definitely use some work to clear it.

vlcsnap-2016-01-24-16h42m21s229

Very nice! Perhaps next weekend I’ll do a flight over the house and see if I can identify broken roof tiles. I’m pretty glad I didn’t have to hike up there to check it out. Kind of wish I had an FPV setup. Perhaps I’ll get that going in the not-too-distant future.