Category Archives: Programming

Another un-productive weekend

The Problem

Convert a 12-variable Boolean expression in disjunctive normal form (DNF) to conjunctive normal form (CNF) so that generating the truth table is NP-hard.  Resulting CNF expression will be used in a student assignment.

Convert DNF to CNF is itself an NP-hard problem. If it were easy, SAT would not be NP. But I need a way to computationally convert DNF to CNF.

Possible solution: Wolfram|Alpha

Wolfram|Alpha is certainly able to convert DNF to CNF. Initial testing shows it works quite well for many variables, but it has a 200-character input limit. DNF expression is much longer than that.

Paid for annual Wolfram|Alpha subscription, hoping that would raise the character limit. Unsuccessful.

Applied for and was granted Wolfram|Alpha API access to try to get around the 200-character input limit. Unsuccessful. API error message is non-existent; it just silently refuses to run the query.

Possible solution: Mathematica

Download trial version of Mathematica and install on Mac. Success! Mathematica is able to convert DNF to CNF quickly. Twelve variables isn’t very many, anyway.

But Mathematica costs $500 to buy — a lot of money for a one-off problem I need to solve a couple times a year.

Possible solution: Karnaugh Maps

Learned that DNF can be converted to DNF using Karnaugh Maps. Just minimize the “zero” cells instead of the usual “one” cells. Invert the inputs. The result is a DNF expression. Seems easy enough.

Research K-map solvers. Most free ones are educational tools designed to show students how K-maps are solved. Because of the limited screen real estate, most can use at most four or five variables — nowhere near the twelve I need.

Possible solution: Roll my own K-Map solver

Getting desperate here. Spend a few hours thinking about how to solve K-Maps using only a truth table, as it would be silly to implement the actual 2D grid in a computer program. Came up with Quine-McCluskey algorithm on my own, so there’s that I guess.

But the Quine-McCluskey algorithm is also NP-hard. The number of prime implicants for 12 variables is as high as 3^n/3, or 177,147, so I see this is going nowhere fast.

Possible solution: Find a Q-M solver

Googled around for a Quine-McCluskey solver, ideally in Python. Found one called QM, referenced from the Wikipedia article. Ran it on my DNF expression. Waited about an hour, but still no results. Gave up.

Also found an optimized version of QM, but I’m already onto the next Possible Solution…

Possible solution: Symbolic computation package

Google around for a symbolic computation package for Python. Found one called Sympy. Install. Run. Plug in my DNF expression. Wait about 30 minutes with the CPU running at 100%. Give up.

Possible solution: Logic Friday

Learned that although DNF-to-CNF is NP-hard, some fine folks at UC Berkeley have discovered a heuristic approach that gives non-optimal but good-enough-for-me solutions. Originally for developing PLA devices at IBM, Logic Friday is a Windows application that implements the Espresso Heuristic Logic Minimizer.

Fire up a Windows VM, download, install Logic Friday. Plug in my DNF and, huzzah!, out pops a CNF within moments!

But.. It’s Windows. And non-scriptable. I’d like to be able to generate the DNF and convert to CNF in an automated fashion on a Linux box.

Working solution: Espresso on Linux

The Espresso Wikipedia page references a working copy of Espresso updated for ANSI C. (Note: this link is to the tar.gz file itself.)

Downloaded, installed on Linux.

Spent about six hours combing through the docs to get it to convert DNF to CNF (what it calls Product of Sum form). But output is still in a DNF formula.

Hack at the source code to get it to print CNF when the -pos command line argument is specified.

Finally get something to work:

$ espresso -pos -oeqntott mydnf.esp
v13.0 = (d|!j|!l|!m) & (!a|!g|m) & (d|!k|l|m) & (c|!d|!e|!j|!l) & (c|d|i|k|m) & (b|!g|!j|m) & (!a|!i) & (!c|k|l|m) & (a|b|j|!m) & (!c|!e|!k|l|!m) & (!b|d|!e|!l|!m) & (a|c|!e|l) & (!b|j|!l|m) & (e|i|j|!k) & (!d|e|!k|l) & (!c|h) & (b|!d|i|k) & (!c|d|!i) & (!a|d|l) & (!b|!c|!l) & (!b|c|e|!j) & (c|e|k|!l) & (a|g) & (!c|e|!l|!m) & (!c|j|!k) & (d|h) & (e|j|l|!m) & (b|d|!g|!k) & (!a|!d|j) & (c|!d|!i) & (!a|!c) & (!b|c|!h|l) & (!d|g) & (!d|!e|k) & (d|!j|k) & (!i|!j) & (!e|g) & (h|!k) & (!f);

Total time spent on this problem: 12+ hours spread across several days. But in the end I got something that worked.

New Problem

Didn’t get any grading done.

Advertisements

Things that bug me about Python

Python, love it or hate it, is a bizarre mix of procedural, functional, and object-oriented syntax. There are lots of things to like about it, but also lots of things to dislike. Here are some of my peeves. I’m sure I’m not the only one.

Versions

What do Windows and Python have in common? Everyone uses the prior, obsolete version and whines about the new version. Python 3 has been out for what, five years now, and people still prefer Python 2.x for everything?

Is version 3.x the Vista of Python?

Sets

This is a set of three numbers: {1, 2, 3}
This is a set of three strings: {‘pizza’, ‘hot dog’, ‘soda’}
This is not the empty set: {}. No, that’s a dictionary. What you meant to write was set(), of course.

Speaking of dictionaries…
Use braces to define an empty dictionary:
>>> D = {}
Use square brackets to access it.
>>> D[‘foo’] = ‘bar’
>>> D[‘foo’]
‘bar’
But get the contents of the dictionary and see it using braces:
>>> D
{‘foo’: ‘bar’}
Sometimes you have to use a method with dictionaries:
>>> D.keys()
dict_keys([‘foo’])
And other times you must use a function:
>>> len(D)
1

The Perl monger in me dies a little bit when I see that.

Strings

Want to convert a string into a list of characters? Use the list function, which I guess is OK:
>>> list(‘hello’)
[‘h’, ‘e’, ‘l’, ‘l’, ‘o’]

Want to convert that list back into a string? Use the join method of a string object:
>>> ”.join([‘h’, ‘e’, ‘l’, ‘l’, ‘o’])
‘hello’

IDLE

Want to give your language the impression that it’s slow: make the primary user interface as glacial as possible. Why is IDLE scrolling sooooo slow?

How about porting a native GUI toolkit to Python so it doesn’t have to rely on Tck/Tk? I can’t tell you how much frustration me and my students have had because the Tk implementation was borked, or there was some weird interaction between Python and Tk. At least Python 3.3.3 for the Mac comes with Tk built in now, but it has bloated the download size tremendously.

But then again…

I’ve still chosen to use Python 3 in my discrete structures course. It has a rich set of datatypes (lists, sets, tuples), comprehensions, a REPL, is cross-platform, is a “cool” and “hip” language, and amazes Java programmers with its handling of large integers.

I just try not to show my students the dark underbelly parts of Python that drives me crazy.

Cheating, round 1

cheating

The assignment was to write a C function that trims the newline character off a string, if it is present. The function takes a string as an argument, trims it in place, and returns nothing.

Here’s what one student turned in:

void trim(char *s)
char *tr ( char *s )
{
  int i = 0;
  int j = strlen ( s ) - 1;
  int k = 0;

  while ( isspace ( s[i] ) && s[i] != '' )
    i++;

  while ( isspace ( s[j] ) && j >= 0 )
    j--;

  while ( i <= j )
    s[k++] = s[i++];

  s[k] = '';

  return s;
}

Announcement to all students: we teachers can use Google, too.

What the $heck?

Did you know the dollar sign ($) is a valid character in a Java variable name? Imagine my surprise when a student showed me the method he wrote. It’s supposed to calculate the amount of tip to leave at a restaurant table.

/**
 * Given the dollar amount of the bill, return 15% tip.
 */
public double tip(double $)
{
    return $ * 0.15;
}

I was so sure this was a bug in the IDE that I submitted a bug report. Then I read the Java spec on identifier names.

Computational Games, part 3

If you’ve been following along, you should have a working Java program that builds the entire game tree for the “1, 2, … 10” two-player game. We are now going to add some code to compute each node’s win/loss status.

(This is the third part of a series on computational games. Read part 1 and part 2 before tackling the code here.)

Start by refactoring the class to add a winLoss attribute. Its values will be W (win), L (loss), or ? (don’t know yet). Also modify the constructor and toString methods accordingly. The changes are highlighted in green.

public class OneTwoTen
{
    int player;
    int pile;
    OneTwoTen add1;
    OneTwoTen add2;
    char winLoss;

    public OneTwoTen(int player, int pile)
    {
        this.player = player;
        this.pile = pile;
        this.add1 = null;
        this.add2 = null;
        this.winLoss = '?';
    }

    public String toString()
    {
        return "(" + player + ", " + pile + ", " + winLoss + ")";
    }

All the other methods remain as they are.  Don’t you love nicely modularized code that “just works” when you make changes?

We can’t know whether a particular node is a win or a loss until we know what its children are. So we’ll do this from the bottom up as described in part 1 of this series.

The leaves are handled specially: they are automatically losses. (By the way, this is only true for games where the goal is to be first to finish. In other games, such as “Even or Odd,” the goal is to have an even number of tokens regardless of who took the last one. Therefore, the leaves are not strictly losses.)

For all other nodes, we call doWinLoss on the children, then figure out if there are any losses among them. If there are, we are a win. Otherwise, a loss.

public void doWinLoss()
{
    if (add1 == null && add2 == null) winLoss = 'L';
    else
    {
        if (add1 != null) add1.doWinLoss();
        if (add2 != null) add2.doWinLoss();

        if ( ((add1 != null) && (add1.winLoss == 'L'))  ||
             ((add2 != null) && (add2.winLoss == 'L')) )
             winLoss = 'W';
        else
             winLoss = 'L';
    }
}

That’s all there is to it! Run it like this:

OneTwoTen root = new OneTwoTen(1,0);
root.buildTree();
root.doWinLoss();
root.printTree();

You should see that the root (1,0) node is labeled with a W to indicate it is a winning position — the first player is guaranteed a way to win. All other nodes will be labeled according to the rules discussed in part 1.

Want to try this on your own? Modify the program to implement the Even or Odd game. Here are the rules:

  • Start with 15 tokens in the pile. Each player maintains their own piles, initially with zero tokens in them.
  • At each turn, a player can take one, two, or three tokens from the central pile and adds them to their pile.
  • The game is over when the central pile is empty.
  • The winner is the player with an even number in their pile, regardless of who took the last tokens or who has more.

Some key points to consider when writing the program:

  • Each node will have three children because you can take 1, 2, or 3.
  • The win/loss status of the leaves depend on who has an even number and are therefore not automatically losses.
  • The in-order traversal of the tree won’t be pretty. You might be better off with a pre-order traversal: display the node first, then call printTree on each of the children.

When you’re done, you’ll be able to answer the central questions: will the first player win or lose the game? What moves should each player make?

In later posts, we’ll tackle some harder problems:

  • “Loopy” games, in which a move may take you back to a state you’ve already seen. Checkers is a well-known example of a loopy game — once a piece is kinged, it can move back and forth on the board.
  • You may have noticed a lot of duplication among the nodes. A total of 232 states are in the tree, but there are only twenty-one distinct states. How can we avoid computing and storing the duplicates? This will help us deal with games that have a lot of states.

Along the way, you’ll learn some more advanced data structures, such as HashMaps, and Java techniques for using them effectively.

Computational Games, part 2

Let’s see about coding up the “1, 2, … 10” game so the computer can arrive at the same conclusion we did: that player 1 is going to win the game.

Read Computational Games, Part 1 for the background material.

Each node in the tree is represented with:

  • The player number (1 or 2)
  • The number of tokens remaining in the pile
  • Pointers to the child nodes

(By the way, the content of this blog is aimed at university/college freshman and sophomores. The code is straightforward with not a lot of fancy syntax until it’s needed.)

Let’s define a Java class to represent a OneTwoTen node. We’ll also provide a convenient constructor for setting the attribute values and a toString for displaying them.

public class OneTwoTen
{
    int player;
    int pile;
    OneTwoTen add1;
    OneTwoTen add2;

    public OneTwoTen(int player, int pile)
    {
        this.player = player;
        this.pile = pile;
        this.add1 = null;
        this.add2 = null;
    }

    public String toString()
    {
        return "(" + this.player + ", " + this.pile + ")";
    }
}

Here’s how to define a few nodes:

OneTwoTen n1 = new OneTwoTen(1, 0);    // The initial state
OneTwoTen n2 = new OneTwoTen(2, 10);   // One of the leaf nodes
OneTwoTen n3 = new OneTwoTen(1, 6);    // A mid-game node

(I use BlueJ for a lot of my coding. Its Code Pad feature lets me simply type in statements like the ones above. With BlueJ, I can quickly test code without laboriously defining a main method. If you’re not using BlueJ, you’ll need to put the statements into a main.)

We can inspect the nodes, again in the CodePad:

> n1.player
1 (int)
> n1.pile
0 (int)
> n2.player
2 (int)
> n2.pile
10 (int)
> n1.toString()
“(1, 0)” (String)
> n3.toString()
“(1, 6)” (String)

Next, define a method called spawn that creates a node’s children. For a node where the pile is 10, there’s nothing to do. If the pile is 9, only one child is created. In all other cases, both children are spawned.

The otherPlayer method is a helper. It simply returns the number of the other player.

public void spawn()
{
    if (pile == 10) return;   // Nothing to do for the leaves
    else if (pile == 9)
    {
        // Only one child here
        add1 = new OneTwoTen(otherPlayer(), pile + 1);
    }
    else
    {
        add1 = new OneTwoTen(otherPlayer(), pile + 1);
        add2 = new OneTwoTen(otherPlayer(), pile + 2);
    }
}

public int otherPlayer()
{
    if (player == 1) return 2;
    else return 1;
}

Try it out:

> OneTwoTen n1 = new OneTwoTen(1, 0);
> n1.spawn();
> n1.add1.toString()
“(2, 1)” (String)
> n1.add2.toString()
“(2, 2)” (String)

Looks good! To build the whole tree, we’ll spawn a node’s children, then call buildTree on each of the children, telling each one to build their own trees.

public void buildTree()
{
    spawn();
    if (add1 != null) add1.buildTree();
    if (add2 != null) add2.buildTree();
}

Did it work? Let’s see…

> OneTwoTen n1 = new OneTwoTen(1, 0);
> n1.buildTree();
> n1.add1.add1.toString()
“(1, 2)” (String)
> n1.add1.add2.toString()
“(1, 3)” (String)
> n1.add1.add1.add1.toString()
“(2, 3)” (String)
> n1.add1.add1.add2.toString()
“(2, 4)” (String)

Sure looks like it! It would be nice to see the whole tree, though. The next method below prints the tree, but it’s sideways. You’ll need to turn your head 90 degrees to the left to see it.

The first printTree method takes an integer argument that tells it how far to indent the node. It calls printTree on the take2 node (so it appears on the right side of the sideways tree), then prints itself, then calls printTree on the take1 node. This is called an in-order traversal.

The second no-argument method just calls the first one with an indent of 0.

public void printTree(int indent)
{        
    if (add2 != null) add2.printTree(indent + 1);

    for (int i = 0; i < indent; i++) System.out.print("   ");
    System.out.println(toString());

    if (add1 != null) add1.printTree(indent + 1);
}

public void printTree()
{
    printTree(0);
}

I’ll leave it to you to call printTree after building the tree and seeing the fruits of your (well, my) labor.

In the next post, I’ll show you how to assign the win-loss label to each node.