Antimatroid, The

Getting a Development Network Started

I’ve been in the process of revamping my home network and have been spending time thinking about how I’d like to set up my development environment for my personal projects that I might try and sell one day. Most of the work I do is C#, ASP.NET, PHP, Java, Haskell,… the list goes on, so I’ve been thinking about what kind of solution will allow me to build against different OSes and platforms. The following is a rundown of this thought process and the considerations and decisions made in bringing up my network.

Anytime I do any planning there are a handful of main points that I try to keep focused on:

Cost – How much money I’m interested in putting into a project?
Time – Total time investment to bring up the hardware and software.
Quality – Am I after a quick solution or one that will have long lasting use?
Portability – How easy would it be to move the system to another platform.
Extensiblity – How easy it is to add on new entitites.

I know I want to keep the project under 1000 USD- this cost includes hardware, operating system licenses, software licenses, utility costs over the lifetime of the solution and opportunity costs etc. Time wise, I want something that could take an hour a day to get setup, working and tweaked to perfection over the course of a week. I want something that is going to be flexible enough to be useful five years down the road, but is also capable of doing what I want today, thus I want a solution that doesn’t look like it was thrown together with duct tape but also doesn’t look like I spent years planning it out. It is important for me to be able to port my solution to new hardware quickly and effortlessly as well as add on new elements as needed. This is especially important if my environment crashes as a result of hardware failure or software malice.

There are a variety of ecosystems that I’m used to working with. the following table summerizes the residents of each:

Ecosystem	Type of Work	Runtimes	IDE	Databases	Web Server
.net	Websites, Web Services, Clients, Services	.net Framework 4.0, Mono 2.6	Visual Studio 2008 Express	SQL Server 2008 Express	Internet Information Services 7.0
Java	Clients	JVE 1.6	Eclipse Galileo	MySQL Community Server 5.1	Apache 2.2
Haskell	Clients	NA	vim, yi, Leksah	MySQL Community Server 5.1	Apache 2.2

These ecosystems also have corresponding environments for dealing with source control, build automation, bug tracking and project tracking. Given the ecosystems I’m interested in, I’ve decided on Subversion, Hudson, Mantis and twiki to manage all of my projects’ artifacts.

Having reviewed what a lot of other shops have done, there are a couple common elements that most development networks incorporate:

repo- Source repository and OS specific Database(s).
dev- IDEs and frameworks for the development of OS specific applications. (per developer machine, often dual booting)
web- OS specific web servers hosting platform specific websites.
build- Dedicated build machines for producing assemblies for specific platforms and OSes.

Given these elements, the languages, platforms and operating systems that I’m interested in, I’ve settled on an ideal network that looks like the following:

Important to notice the use of virtualization here. Being able to store a series of ISOs for each of the element groups on a NAS makes it easy to bring up new instances and make backups, thus statisfying my time and portability criteria. As well as satisfying my cost criteria as it is cheaper to purchase a beefy box running several virtual machines than it is to purchase several physical machines. At the time of writing (2009-12), most quad core machines run for about 1000 USD and, and most (consumer) NASes cost about 100-300 USD. Now, I could load up the server up with 1TB storage for an additional 100 USD. Of course, this means I have a single point of failure- which in a home environment may not be a huge deal. In terms of money these two are the main consumers at the hardware level. Everything else already exists on the network.

Lets take a look at the estimated costs:

Item	Quantity	Amount (USD)	Extended Amount (USD)
Dell Studio XPS 8000	1	1100.00	1100.00
1TB Western Digital MyBook	1	120.00	120.00
Windows XP Professional Licenses	4	100.00	400.00
			1620.00

That total amount is a little more that initially desired. It is possible to collapse vm-windows-dev and time-thief down to one machine, and then collapse vm-windows-repo, vm-windows-web and vm-windows-build down to a single machine resulting in a cost savings of 300.00 USD from reduced operating system license costs. If the NAS is removed from the picture, that brings us down to 1200.00 which is about as close as I’m going to get to my inital target of 1000 USD. Not sure if this is the final setup that I will end up going with, per usual, I’ll update this post with any new developments.

Written by lewellen

2010-02-01 at 8:00 am

Posted in Uncategorized

Tagged with Build Automation, Development Environment, Development Network, Projects

Multi-agent ordering

leave a comment »

Given a set of agents $A = \{ a_{0}, a_{1}, \dotsc, a_{n} \}$ and a set of entities $V = \{ v_{0}, v_{1}, \dotsc, v_{m} \}$ , agents independently provide preferences $I_a \colon V^{2} \to \{ -1, 0, +1\}$ between different pairs of entities for a subset $S_{a}$ of the possible $E = V^{2}$ pairs. From these preferences, we wish to form a poset that contains the entities in order of least preferred to most preferred.

An agent may prefer an individual pair $e_{i,j}$ in the following ways: $-1$ , the agent prefers $v_{j}$ to $v_{i}$ ; $0$ , the agent is indifferent; $+1$ , the agent prefers $v_{i}$ to $v_{j}$ . Let $G_{a} = (V, S_{a})$ be the undirected graph that represents the preferences of an individual agent.

To form a consensus we are interested in $G= \sum_{a \in A} G_{a}$ . Let the adjacency matrix $M$ represent $G$ . In doing so, we may define $M$ in the following way: $M_{i,j} = \sum_{a \in A} I_a (e_{i,j})$ . It should be evident that $M_{i,i} = 0$ and $M_{i,j} = -M_{j,i}$ . We wish to simplify $M$ by turning it into a directed graph whereby all negative entries are removed. We shall define $N_{i,j} = \max{(0, M_{i,j})}$ to be this directed graph.

Let $deg_{j}^{in} = \sum_{i = 0}^{m} N_{i, j}$ be the sum of weights into vertex $v_{j}$ , $deg_{i}^{out} = \sum_{j = 0}^{m} N_{i,j}$ be the sum of weights out of vertex $v_{i}$ and $\delta_i = (deg_{i}^{in}, deg_{i}^{out})$ be the set of tuples for each vertex in $V$ . Thus, let $\delta$ along with the relation: increasing first element, then by decreasing second element be the poset $P$ of entities order from least preferred to most preferred.

Consider the following example: on a merchant’s website, customers $A = \{a,b,c,d,e,f\}$ independently provide comparisons between products that the merchant sells. The merchant wishes to know his customers’ preferences about his products $V = \{1,2,3,4,5,6\}$ .

Customers have provided the following set of preferences:

multi_agent_preferences

The consensus graph is produced from these preferences, followed by the directed graph until $\delta = \begin{pmatrix} (1,4) & (4,3) & (2,0) & (1,4) & (0,2) & (4,0) \end{pmatrix}$ is computed, which, when used to form $P$ , will yield $P = \{6,2,3,1,4,5\}$ . The merchant can infer from this analysis that customers least preferred product is 6, and most preferred product is 5.

Now, this model assumes that the agents are being truthful in their preferences. It is conceivable that a consortium of agents could force an entity to become the least or most preferred entity by providing false preferences. This premise presents two questions: how do we identity fallacious behavior, and two: how do we prevent it. The answer to the later of these two questions is simple: we add an additional term $\tau_a \in [0,1]$ when constructing $M_{i,j} = \sum_{a \in A} (1 - \tau_a) I_a (e_{i,j})$ where $0$ indicates that the agent provides factual preferences and $1$ indicates non factual preferences. The prior of these two questions is more involved and ties into calculating $\tau_a$ .

Lets consider two plausible hypotheses: a single agent tells the truth $\phi_{a}$ or he does not tell the truth about a single comparison $e$ . An agent is telling the truth about a single comparison if his preference $I_{a}(e)$ is identical to the majority preference $\sum_{a \in A} I_{a}(e)$ . An agent is not telling the truth if his preference is not identical to the majority preference. Let $\phi_{a}(e) = 1$ when $I_{a}(e)\sum_{\alpha \in A} I_{\alpha}(e) < 0$ , $0$ otherwise formalize this membership. Thus, we may define $\displaystyle \tau_{a} = \frac{\sum_{e \in S_{a}} \phi_{a}(e)}{ \lvert S_{a} \rvert }$ as the probability that a’s comparisons are majority comparisons.

This formalization assumes that there is an objective comparison and naturally, this formalization would not hold for subjective comparisons.

Consider the following example: seven robots are asked to order a collection of five blocks from smallest to largest and the result is an incorrectly ordered list. We wish to identify the defective robot(s), remove their preferences and reproduce the corrected list. The following table summarizes each robot’s preferences starting from the top left to right then down to the bottom left to right.

Going through the process above we arrive at an order of $\{0, 1, 3, 2, 4\}$ which is incorrect, thus we look at what our values are for this first iteration: $\tau_{a}^{(0)} = \begin{pmatrix}0 & 0.25 & 0 & 0 & 0 & 0.\overline{1} & 0\end{pmatrix}$ . Robots $a_{1}, a_{5}$ are more likely than their piers to deviate from the established majority. So, applying these values, we continue to perform this process iteratively until we arrive at $\{0,1,2,3,4\}$ using values of $\tau_{a}^{(2)} = \begin{pmatrix}0 & 0.41\overline{6} & 0 & 0 & 0 & 0.\overline{2} & 0 \end{pmatrix}$ . This process can be visualized the iterations of $N$ below. Edge weights represent the consensus. Thicker lines for the majority, thinner for the minority.

While not previously alluded to, it is possible that it may take several iterations to achieve a correct ordering. Which raises a couple questions: under what conditions will the correct ordering exist, how many iterations will it take to reach the correct ordering and are the number of iterations finite. The last one is left to the reader.

As a thought experiment, it is evident that there has to be at least $m - 1$ preferences for a correct ordering to be produced. Starting at any one vertex, there exists a path to every other vertex, otherwise a consensus cannot be achieved because $G$ could be decomposed into a set of disjoint subgraphs and no ordering is possible.

If there is an objective order $P^{\star}$ , it is still possible to arrive at a separate order $P^{\prime}$ that is produced after successive iterations if the majority preferences are all incorrect with respect to $P^{\star}$ . Thus, we cannot guarantee that the process will converge. If the preferences are correct with respect to $P^{\star}$ , then convergence will be achieved as the weight of dissenting agent’s preferences tends towards zero.

Written by lewellen

2010-01-01 at 8:00 am

Posted in Uncategorized

Tagged with Algorithms, Graph Theory, Order Theory

The next decade of the Internet

leave a comment »

This post marks the return of The Antimatroid after a four month hiatus. I will be resuming my monthly publication format. Next month’s post will be on multi-agent consensus forming followed by infectious diseases modeling.

Last month, specifically- October 29, 2009, marked the 40th year of the Internet- which got me thinking a bit about the direction the Internet is heading in and how people will ultimately utilize the Internet in the future. Part of this thought exercise is thinking what devices people will use to connect to the Internet, what they will do once connected and what type of networks their data will travel over. Naturally, thinking about what information those devices are capable of collecting, presenting, processing; what people will share, interact and consume while connected; and finally the technology behind the network, who owns the network and how it is regulated. The other half of this exercise, is looking at the trajectory that history has provided us for extrapolation.

According to Gartner, there were 41.0 million smartphones sold worldwide in the second quarter of 2009. At present, there ought to be roughly a billion smartphones worldwide, each of these phones is connected to some kind of network capable of accessing the Internet. Most of these phones have built-in cameras, voice recorders, GPS and accelerometers. Just about any other sensor could be added to these phones. Imagine each one sending up that sensor data to The Cloud- GPS information coupled with images could allow for image recognition to be performed real-time to tell the user about what they are looking at, weather sensors could be added to capture accurate weather information to provide more accurate weather models. Another aspect to consider- each smartphone has processing power of 500Mhz to 1Ghz. That is a lot of potential processing power left untapped, on the order of an exahertz. Telecoms could lease out this processing power to whomever and make a bundle if the margin is right.

With all this information that can come up from smartphones as well as traditional machinery, the Internet becomes much more real-time and much more focused. To make sense of this information, there will continue to be a need for efficient and effective searching- Google isn’t going anywhere- but it will have to become more specialized providing location aware searching, e.g., being able to walk into a bookstore and having instructions on how to find a copy of an original print favorite of yours down to the bookcase and row. Aggregation sites that understand how to filter down the data and present it in a meaningful and insightful way will be necessary to make sense of all the data. Sites that present media from multiple sites, multiple social networks and results from multiple search engines will gain value. The ability to take in multiple data streams in a standardized way is important- a common interface for real-time data.

Data, obviously, isn’t just text, it is audio, pictures and video. We saw how streaming media was a boom in the late 90s for music. The emergence of VoIP as an effective replacement for telephone lines- both residential and commercial- has seen adoption in leaps and bounds. News organizations have adopted the net in varying degrees allowing for much faster distribution of news as it happens. The remaining media is television. YouTube, Hulu, Netflix have seen the commercial benefits of bringing streaming video to the world. Traditional media outlets are streaming their programs online – Fox, CBS, ABC, NBC etc all have fantastic options available for free. The trend here being that we can bring all of our traditional media onto a single delivery system: news, documents, images, audio, video – all the media we’ve come to adopt over time – can be delivered to you on a single pipe.

People will continue to share information, but the focus will be on better management of their networks, their social circles to be more precise- both virtual and physical. Networks like Facebook and LinkedIn do a decent job now of connecting people with one another, but fail to adequately manage which information is dispersed amongst the associates in our networks. The focus on managing, marketing and protecting our identities and personas will become more prominent; publishing, sharing and distributing information that we find, produce and rehash will become easier.

Of course this is a very North American view of the Internet. It is estimated that 25% of the world’s population is connected to the internet according to Internet World Stats. Of that quarter, Asia represents roughly 42.6% of all internet users followed by Europe at 24.1% and North America at 14.6%. Among all Internet users, 27.6% speak English, 22.2% Chinese and 7.9% Spanish. Unsurprisingly, the corresponding number of web pages by those languages are not proportionate to their language base. English website constitute 68.4% of all pages followed by Japanese at 5.9% and German at 5.8% according to ClickZ. When you get down to it, the Internet contains a lot of information, but most likely in a language that the user doesn’t speak, unless they happen to know English. I believe that we will continue to see English as the dominate language of the web until new standards come in to place that allow for better support of the Unicode character encoding at each part of the Internet technology stack. At which time, I would expect to see page share by language to be proportionate to world language shares. I would not expect to see an increase in the number of Middle East and African users given the more pressing matters of each region- as of now each represents less than 4% of internet users. Naturally, as language shares normalize, automated translation will become increasingly important as great ideas are not limited to just one language.

As I draw to a close, I’d like to mention one more area of interest: regulation. I believe that this area will become more contentious as the number of individuals on the Internet from minority nations increases in the coming decade. It should seem reasonable that anyone, anywhere has the right to access, produce and discuss the lawful content of their choice without obstruction from a foreign body. Problem being, what is lawful content? We should all be able to recognize that there exist ideas that should be allowed to spread freely, even when we do not agree with those ideas and that that information should be spread freely unobstructed by any entity.

The second aspect to this problem of regulation is how people will be charged to access the Internet. Internet Service Providers should not charge customers to access certain sites, doing so is a form of censorship as well as a form of control a companies primary resource: users. ISPs could have the ability to reduce a website’s user traffic by charging those users money to access that site and thus reducing the number of users that might go to a website and thus reducing the profitability of that website. Likewise, if an ISP did not want users to visit a particular website, they could drop all packet requests to that website or return that the site does not exist. practices such as these are why it is important for different nations to adopt the policy of Network Neutrality. As the Internet reaches its next phase of development it will become increasingly important that the foundations that made it so popular are not disregarded in favor of those motivated by political or corporate ideologies.

The Internet has proven to be the truest of democratic forms, a wildly successful bazaar, a comprehensive library and ultimately a platform that enables people from every background to access, distribute and discuss information. I suspect that we will see the Internet become real time, it will be able to provide us with location aware content, be on the smallest and largest of gadgets from our cellphones to computers. We will access all of our information from the Internet: music, radio, television and news. It will become easier to manage our social networks and personal data. The shift from English to local languages will begin to build momentum as Unicode support becomes more widely adopted. There will be potential for underrepresented regions to start having a presence on the Internet. Last but not least, it will start to see an increased trend towards less censorship and more regulation towards keeping it an open platform.

Written by lewellen

2009-12-01 at 8:00 am

Posted in Uncategorized

Tagged with Network Neutrality, Opinion, Smartphones, Worldwide Internet Languages

Busy month

leave a comment »

Between a busy month at work and juggling the duties associated with buying a home, I’ve haven’t had the time to write anything up for the month of July. I do have some interesting stuff in the works for August and following months. Until then, I’m sure you’ll find something worth reading in the archive.

Written by lewellen

2009-07-01 at 12:00 am

Posted in Uncategorized

Sudoku Solver in Haskell

leave a comment »

This month will be a bit of short article since I haven’t had a whole lot of time on my hands lately. Haskell is a wonderful little language that has begun to pick up a bit of moment in the past year that I’ve been playing with on-and-off now for several years. Since I don’t post enough on Haskell, I figured I’d post my bare-bones Haskell Sudoku Solver.

import Data.List
import Data.Maybe

toRowColumn :: Int -> (Int, Int)
toRowColumn index = (r, c)
	where	r = div index 9
		c = mod index 9

toIndex :: (Int, Int) -> Int
toIndex (r, c) = r * 9 + c

toRegion :: (Int, Int) -> Int
toRegion (r, c) = (div r 3) * 3 + (div c 3)

columnIndicies :: Int -> [Int]
columnIndicies c = [c, c + 9..80]

regionIndicies :: Int -> [Int]
regionIndicies g = [toIndex(r + x, c + y) |
		x <- [0..2],
		y  [Int]
rowIndicies r = [9 * r..9 * (r + 1) - 1]

values :: [Int] -> [Int] -> [Int]
values board indicies = filter (>0) (map (board!!) indicies)

possibleValues :: [Int] -> (Int, Int) -> [Int]
possibleValues board rowColumn =
	foldl () [1..9] (
	  map (values board) (
	    map (f -> (fst f . snd f) rowColumn) (
	      zip [rowIndicies, columnIndicies, regionIndicies] [fst, snd, toRegion]
	    )
	  )
	)

validBoard :: [Int] -> Bool
validBoard board = (length board == 81) && (and $ map (==0) l)
	where	l = map length s
		s = map ([1..9]) v
		v = [values board (xIndicies x) |
			x <- [0..8],
			xIndicies  Bool
solvedBoard board = and $ map (>0) board

hasUnassigned :: [Int] -> Bool
hasUnassigned board = isJust $ elemIndex 0 board

assignFirstUnassigned :: [Int] -> Int -> [Int]
assignFirstUnassigned (b:bs) value
	| b == 0 = value : bs
	| otherwise = b : (assignFirstUnassigned bs value)

possibleBoards :: [Int] -> [Int] -> [[Int]]
possibleBoards board possibleAssignments = map (assignFirstUnassigned board) possibleAssignments

solve :: [Int] -> [[Int]]
solve board
	| not (validBoard board) = [[]]
	| solvedBoard board = [board]
	| not (hasUnassigned board) = [[]]
	| otherwise = concated
	where	concated = concat mapped
		mapped = map solve filtered
		filtered = filter (not . null) possibleSolved
		possibleSolved = possibleBoards board possibleAssignments
		possibleAssignments = possibleValues board unassignedRowColumn
		unassignedRowColumn = toRowColumn unassignedIndex
		unassignedIndex = fromJust $ elemIndex 0 board

demo :: [Int]
demo = [2,0,0,0,8,0,3,0,0,
       0,6,0,0,7,0,0,8,4,
       0,3,0,5,0,0,2,0,9,
       0,0,0,1,0,5,4,0,8,
       0,0,0,0,0,0,0,0,0,
       4,0,2,7,0,6,0,0,0,
       3,0,1,0,0,7,0,4,0,
       7,2,0,0,4,0,0,6,0,
       0,0,4,0,1,0,0,0,3]

Written by lewellen

2009-06-01 at 12:00 am

Posted in Uncategorized

Tagged with Haskell, Sudoku

Sudoku Solver in C# using Lambda Expressions

leave a comment »

Seems that everywhere you look someone has a Sudoku Solver that they want to showcase, well, I’m no different so I figured I’d post my take on the subject. Microsoft has introduced/included/borrowed a number of functional programming features into the latest version of C# (3.0) that have made it easier for developers to write better, cleaner code. One of those features continues the trend of improving anonymous methods, which extend delegates which extend interfaces now known as Lambda expressions. E.g., the following are all the same for the expression $\lambda x . x * x$ :

Func<int, int> square = (x) => x * x;

Func<int, int> square = new Func<int, int>(delegate(int x) { return x * x; });

public interface Func<T, R> {
    R Evaluate(T x);
}

public class Square : Func<int, int> {
    public int Evaluate(int x) {
        return x*x;
    }
}

...

Func<int,int> square = new Square();

Given that level of expressive power, I thought I would approach this implementation using as many lambda expressions as possible to see how concise and easy to follow an implementation I could create.

To start off, the solver will assume that the board will be passed in as a 81 character array containing digits 0-9. Zero shall represent an unassigned cell.

The core loop is pretty simple: Start with the initial board on a stack, in a loop take the first board off the stack and check if it is valid. A board is said to be valid if for every row, column and region each structure contains one and only one instance of the digits 1-9. If the board is not valid, no further work should be done.

Next we need to check if the board is solved. If it is not, then we need to explore the possible boards that can be derived from that board. To do so, we will need to find the first possible cell that is unassigned and push on to the the stack a derived board using the possible values that can be assigned to the identified cell.

Once the loop finally exits, print out the solved board.

using System;
using System.Collections.Generic;

namespace Sudoku {
    public class Program {
        static public void Main(string[] args) {
            string input = "200080300060070084030500209000105408000000000402706000301007040720040060004010003";
            Board inputBoard = null;
            try {
                inputBoard = new Board(input);
            } catch (InvalidInputException iie) {
                Console.WriteLine(iie.InvalidInput);
                return;
            }

            Stack boards = new Stack();
            boards.Push(inputBoard);
            Board board = null;
            do {
                board = boards.Pop();
                if (!board.Valid)
                    continue;
                if (!board.Solved)
                    board.FirstAvailable((r, c) =>
                        board.PossibleValuesAt(r, c, (v) =>
                            boards.Push(board.DeriveUsing(r, c, v))
                        )
                    );
            } while (boards.Count > 0 && !board.Solved);
            Console.WriteLine(board);
        }
    }
}

I’m going to start with the private member methods since they form the basic grammar that I will use to implement the public member methods and properties.

The first thing you’ll notice is the private class Structure; it is a simple pair class that contains two member properties for accessing a function that iterates over all possible structures and a function that iterates over all the cells in a specific structure.

The private constructor instantiates a private member array containing the function pointers that enumerate over Rows, Column and Regions.

assertStructure method which iterates over every instance of a structure in the table, and verifies that one and only one instance of the digits 1-9 exist in that structure instance.

indexInStructure iterates over all of the indices of a structure- in this case, 0-8.

using System;
using System.Text;

namespace Sudoku {
    public partial class Board {
        private class Struct {
            public Action<Action<int>> In { get; set; }
            public Action<int, Action<int>> ForValues { get; set; }
            public Struct(Action<Action<int>> _in, Action<int, Action<int>> forValues) {
                In = _in; ForValues = forValues;
            }
        }

        private Struct[] structures;

        private Board(int[] board) {
            this.board = board;
            structures = new Struct[] {
                new Struct(Rows, ValuesInRow), new Struct(Columns, ValuesInColumn),
                new Struct(Regions, ValuesInRegion)
            };
        }

        private bool assertStructure(Action<Action<int>> structure, Action<int, Action<int>>
            valuesInStructure) {
            bool asserted = true;
            structure((x) => {
                int[] used = new int[10];
                valuesInStructure(x, (y) => used[y]++);
                used[0] = 0;
                asserted &= forAllValues((v) => v < 2, used);
            });
            return asserted;
        }

        private void indexInStructure(Action<int> actOnIndex) {
            indexInStructure((n) => true, actOnIndex);
        }

        private void indexInStructure(Predicate<int> p, Action<int> actOnIndex) {
            indexFromToWhere(0, 9, p, actOnIndex, false);
        }

The forAllValues method is simply a way of writing the predicate $(\forall x) Px$ applied to members of the universe of discourse (the array that was passed in).

indexFromToWhere is a simple wrapper around a common for loop with filtering and the option to break after the first object to pass through the filter is found.

        private bool forAllValues(Predicate f, T[] A) {
            bool held = true;
            for (int n = 0; n < A.Length && held; n++)
                held &= f(A[n]);
            return held;
        }

        private void indexFromToWhere(int min, int max, Predicate<int> p, Action<int> actOnIndex,
            bool breakAfterFirst) {
            for (int n = min; n < max; n++)
                if (p(n)) {
                    actOnIndex(n);
                    if (breakAfterFirst)
                        break;
                }
        }

The following methods are all related to working with the board representation. I choose to implement the board as an integer array. The at method maps a logical row and column to a row order array value within board. Each of the different indexInBoard methods allows for iterating over the indices of the board.

        private int[] board;

        private int at(int row, int col) {
            return row * 9 + col;
        }

        private void indexInBoard(Action<int> actOnIndex) {
            indexInBoard((n) => true, actOnIndex);
        }

        private void indexInBoard(Predicate<int> p, Action<int> actOnIndex) {
            indexInBoard(p, actOnIndex, false);
        }

        private void indexInBoard(Predicate<int> p, Action<int> actOnIndex, bool breakAfterFirst) {
            indexFromToWhere(0, board.Length, p, actOnIndex, breakAfterFirst);
        }
    }
}

The first set of public member methods and properties we can look at are for managing the state of the board. The board is only Solved if each index is assigned. The board is only Valid if every structure in the board is asserted to be true. The constructor checks the input to make sure it is valid, delegates the some work to the private constructor and loads the input string in to the integer array.

using System;
using System.Text;

namespace Sudoku {
    public partial class Board {
        public bool Solved {
            get {
                return forAllValues((x) => x > 0, board);
            }
        }
        public bool Valid {
            get {
                return forAllValues((s) => assertStructure(s.In, s.ForValues), structures);
            }
        }

        public Board(string input) : this (new int[81]) {
            if (string.IsNullOrEmpty(input))
                throw new InvalidInputException(InvalidInput.Empty);
            if (input.Length != 81)
                throw new InvalidInputException(InvalidInput.Length);
            for (int n = 0; n  board[n] = input[n] - '0');
        }

        override public string ToString() {
            StringBuilder S = new StringBuilder(board.Length);
            indexInBoard((n) => S.Append((char)('0' + board[n])));
            return S.ToString();
        }

Next, we need a way to operate on each of the structures in the board. Each row from top to bottom, each column from left to right and each region from top left to bottom right (zig-zag) will be assigned an index from 0-8 respectively.

        public void Columns(Action<int> actOnColumn) {
            indexInStructure(actOnColumn);
        }

        public void Regions(Action<int> actOnRegion) {
            indexInStructure(actOnRegion);
        }

        public void Rows(Action<int> actOnRow) {
            indexInStructure(actOnRow);
        }

It is easy to then iterate the cells in a given structure. The values in a column are simply a trip down the Rows and we only want to act when the value is defined. The values in a row are just as easy by traveling across the Columns and acting when the value is defined. Iterating over the values in the region is a little more involved, but nonetheless just as easy to follow- map the region to the appropriate reference row and column and then iterate over the 3×3 grid and act only when the value is defined.

        public void ValuesInColumn(int column, Action<int> actOnValue) {
            Rows((r) => {
                int value = board[at(r, column)];
                if (value > 0)
                    actOnValue(value);
            });
        }

        public void ValuesInRegion(int region, Action<int> actOnValue) {
            int row = (region / 3) * 3;
            int column = (region % 3) * 3;
            int value = 0;
            for (int r = 0; r < 3; r++)
                for (int c = 0; c  0)
                        actOnValue(value);
                }
        }

        public void ValuesInRow(int row, Action<int> actOnValue) {
            Columns((c) => {
                int value = board[at(row, c)];
                if (value > 0)
                    actOnValue(value);
            });
        }

Finally, we have the interesting methods used in the main loop. DeriveUsing will copy the board into a cloned integer array and then assign the derived at row and column with the value supplied. The newly derived board is then returned.

FirstAvailable iterates over all the indices of the board until it finds an unassigned value and then it acts upon the reference row and column.

PossibleValuesAt goes and collects a list of possible values by first collecting the values used in the row, column and region that the reference row and column reside within, then each value not found is acted upon.

        public Board DeriveUsing(int row, int colum, int withValue) {
            int[] derived = new int[81];
            indexInBoard((n) => derived[n] = board[n]);
            derived[at(row, colum)] = withValue;
            return new Board(derived);
        }

        public void FirstAvailable(Action<int, int> actOnRowAndColumn) {
            indexInBoard((n) =>
                board[n] == 0, (n) => actOnRowAndColumn(n / 9, n % 9), true);
        }

        public void PossibleValuesAt(int row, int column, Action<int> actOnPossibleValue) {
            bool[] used = new bool[10];
            ValuesInRow(row, (x) => used[x] = true);
            ValuesInColumn(column, (x) => used[x] = true);
            ValuesInRegion((row / 3) * 3 + (column / 3), (x) => used[x] = true);
            indexFromToWhere(1, used.Length, (n) => !used[n], actOnPossibleValue, false);
        }
    }
}

Having approached this implementation as I did, I found some interesting bugs that I hadn’t come across before and I figure I’ll close with one that caught me off guard. I had spent an hour writing all my code and figured I’d run it to see what kind of output I got. To my surprise I got an immediate StackOverflowExeception. So I spent and an additional 10 minutes debugging and found the following offending code. Take a look at it and see if you can see what’s wrong with it before reading on.

public void act(Func<int,int> assign){
    act((n) => board[n] = assign(n));
}

public void act(Action<int> actOn) {
    for(int n = 0; n < board.Length; n++)
      actOn(n);
}

After a minute I had my ah-ha moment (as I’m sure have as well) and remembered that the assignment operator returns the value of the assignment so the compiler was turning (n) => board[n] = assign(n), into Func<int, int> instead of Action<int> as I had hoped. To fix the bug, I had to do the following to get the compiler to pick the statement up as Action<int>.

public void act(Func<int,int> assign) {
    for(int n = 0; n < board.Length; n++)
        act((n) => { board[n] = assign(n); });
}

Having made the change, I tested my input string and out printed the solution immediately. I decided against writing similar function overloading in the final implementation to prevent any unintended bugs.

Written by lewellen

2009-05-01 at 12:00 am

Posted in Uncategorized

Tagged with C# 3.0, Lambda Expressions, Sudoku

Integer Factorization by Dynamic Programming with Number Theoretic Applications

with 5 comments

Having been a participant of a number of mathematical programming competitions over the years, I’ve had to find a number of efficient ways of implementing many common Number Theoretic Functions. In this write up, I’m going to go over a method I’ve found useful for easily factoring numbers using a sieving method, go over some the implementation of a few number theory functions along with time complexity analysis of each. The cornerstone to many of these implementations relies on the ability to quickly factor integers and find primes.

One of the most popular methods of for finding primes is the Sieve of Eratosthenes. The algorithm starts by populating a table with every positive integer from 2 to a ceiling value. Then find the first integer not yet crossed off, in the case 2, and eliminate every multiple of 2 from the table then return to 2 and find the next positive integer not yet crossed off and repeat the procedure until the end of the table is reached. The method is fine and all, but a lot of really great information is lost in that computation. Here is a sample implementation:

bool[] isPrime = new bool[400];
for (uint n = 2; n < isPrime.Length; n++)
    isPrime[n] = true;
for (uint n = 2; n < isPrime.Length; n++)
    if (isPrime[n])
        for (uint m = 2, c = 0; (c = m * n) < isPrime.Length; m++)
            isPrime[c] = false;

On the other hand, say we approach sieve a little differently. Create an empty table as large as the ceiling value. Start at 2 and for every multiple of 2, create a record that has two parts: 2 and half of the multiple. Return to 2 and find the next integer in the table that has yet to be recorded, in this case 3. For every multiple of 3, create a record that has two parts: 3 and third of the multiple (only if the multiple was not previously recorded. E.g., 6 because 2 previously recorded the record). Return to 3 and find the next integer in the table that has yet to be recorded so on and so forth until every integer in the table has been recorded.

The following graphic demonstrates this process for a ceiling values of 25. If we wish to factor 16, we go to 16’s record (2, 8), follow to 8’s record (2,4), again follow 4’s record (2, 2) and finally 2’s record (2, λ). Thus the prime factorization of 16 is 2, 2, 2, 2.

It should be apparent that this algorithm is a simple dynamic programming solution that yields two major results:

We have factored every positive integer up to a ceiling value.
We have found every positive prime integer up to a ceiling value.

And one major draw back

Uses a lot of memory as a trade off for speed.

Let’s get into the C# implementation. To start off, we need a record class that’ll store the information about the first prime that divides an entry and the composite to jump to if the record corresponds to a composite.

public class Record {
    public uint Prime {get; set;}
    public uint? JumpTo {get; set;}
}

We’ll have a class called NumberTheory and assume that it has the following structure. If you want, you could make this a Singleton class but I felt it was unnecessary for the scope of this write up.

public class NumberTheory {
    private Record[] table;

    ...
}

It makes sense to put the core algorithm in the constructor and then have member methods for each of the functions we’d like to have. It should be assumed that for the lifetime of the class that the largest value ever called on the methods will be N otherwise an exception should be thrown by the methods (omitted here for brevity).

public NumberTheory(uint N){
    uint c = 0;
    table = new Record[N+1];
    for(uint n = 2; n < table.Length; n++) {
        if(table[n] != null)
            continue;
        table[n] = new Record() { Prime = n };
        for(uint m = 2; (c = n * m) < table.Length; m++)
            if(table[c] == null)
                table[c] = new Record() { JumpTo = m, Prime = n };
    }
}

The time complexity of the implementation can be derived using some analysis and by having some knowledge of certain identities. Starting from 2 there are N – 2 numbers to check of which 1/2 will be visited by the interior loop, starting from 3 there are N – 3 numbers to check of which 1/3 will be visited visited by the interior loop, so on and so forth leading to the following summation:
$\displaystyle T(n) = \sum_{p \le n} \left( \frac{1}{p}(n - p) \right)$
$\displaystyle T(n) = \sum_{p \le n} \left( \frac{n}{p} - 1 \right)$

If we separate the summation into the harmonic series of primes (HSP) and prime counting function (aggregate 1 for every prime less than n) we get:
$\displaystyle T(n) = n \sum_{p \le n} \left( \frac{1}{p} \right) - \pi(n)$

Asymptotically, the HSP tends towards $\ln \ln n$ and $\pi(n)$ towards $\frac{n}{\ln n}$ .
$\displaystyle T(n) = n \left( \ln \ln n \right) - \pi(n)$
$\displaystyle T(n) = n \left( \ln \ln n \right) - \frac{n}{\ln n}$
$\displaystyle T(n) = n \frac{ \ln n \cdot \ln \ln(n) - 1}{\ln n}$

Giving us our final asymptotic time complexity of $O(n \ln \ln n)$ .

The first member method we’ll implement is a trivial check to see if a given number is prime by checking the table’s Record’s JumpTo property for null.

public bool IsPrime(uint N){
    return !table[N].JumpTo.HasValue;
}

The time complexity here is a simple $O(1)$ .

From IsPrime, we can easily implement a function that will get every single prime up to a given value by iterating over the table.

public void PrimesLessThan(uint value, Action<uint> actOnPrime) {
    for(int n = 2; n < value; n++)
	if(IsPrime(n))
		actOnPrime(n);
}

We can get the prime counting function $\pi(n)$ but utilizing the PrimeLessThan function.

public uint CountPrimes(uint n) {
	uint count = 0;
	PrimesLessThan(n, (p) => {count++;});
	return count;
}

Here the time complexity is the same as PrimesLessThan: $O(n)$ .

We can get the prime factorization of a composite easily. To do so, we simply iterate over the records until we reach a Record with no JumpTo value.

public void PrimeFactorsOf(uint composite, Action actOnFactor) {
    Record temp = table[composite];
    while(temp != null) {
        actOnFactor(temp.Prime);
        if(temp.JumpTo.HasValue)
            temp = table[temp.JumpTo.Value];
        else
            temp = null;
    }
}

The time complexity of this implementation relies on the the prime omega function $\Omega(n)$ which is the number of prime factors (not necessarily distinct) of n. The function tends to $O( \ln \ln n)$ .

From PrimeFactorsOf, we can also easily implement Euler’s Totient Function $\phi(n)$ - the function tells us how many positive integers less than n are coprime to n. It is defined as:
$\displaystyle \phi(n) = n \prod_{p|n} \left( 1 - \frac{1}{p} \right)$
Which essentially states that if you multiply all of the repeated prime factors of n together by all of the non-repeat prime factors – 1 of n together, you will have the result of $\phi(n)$ .

public uint EulerTotient(uint n){
    uint phi = 1, last = 0;
    PrimeFactorsOf(n, (p) => {
        if(p != last) {
            phi *= p - 1;
            last = p;
        } else {
            phi *= p;
        }
    });
    return phi;
}

A similar function known as the Dedekind $\psi(n)$ Function defined as
$\displaystyle \psi(n) = n \prod_{p|n} \left ( 1 + \frac{1}{p} \right )$
can be implemented in a similar way as $\phi(n)$ :

public uint DedekindPsi(uint n){
    uint phi = 1, last = 0;
    PrimeFactorsOf(n, (p) => {
        if(p != last) {
            phi *= p + 1;
            last = p;
        } else {
            phi *= p;
        }
    });
    return phi;
}

The Von Mangoldt Function $\Lambda(n)$ is another interesting function, unfortunately I haven’t had a chance to use it, but it is trivial to implement so I will include it here for completeness. It is defined as
$\displaystyle \Lambda (n) = \begin{cases} \ln{p} & \text {if n = prime to some positive integer power} \\ 0 & \text{otherwise} \end{cases}$

public double VonMangoldt(uint n){
    uint P = 0;
    PrimeFactorsOf(n, (p) => {
        if(P == 0) {
            P = p;
        } else if (P != p) {
            P = 1;
        }
    });
    return Math.Log(P);
}

The Möbius Function $\mu(n)$ is a handy little function for determining if a number is square free or not (among many more interesting things). It is defined as:
$\displaystyle \mu(n) = \begin{cases} 0 & \text{if n has one or more replicated factors} \\ 1 & \text{if n = 1} \\ (-1)^{k} & \text{if n is a product of k distinct primes} \end{cases}$

public int MoebiusFunction(uint N){
    if(N == 1)
        return 1;
    bool distinct = true;
    uint last = 0, k = 0;
    PrimeFactorsOf(N, (p) => {
        if(p == last) {
            distinct = false;
        } else {
            k++;
            last = p;
        }
    });

    if(distinct)
        return ((k & 1) == 0) ? 1 : -1;
    return 0;
}

Since EulerTotient, DedekindPsi, VonMangoldt and Moebius each use PrimeFactorsOf without any additional lifting, their time complexities are the same as PrimeFactorsOf – $O(\ln \ln n)$ .

The last function I’ll implement is the Mertens Function $M(n)$ which is simply defined as $\displaystyle M(n) = \sum_{k = 1}^{n} \mu(k)$ :

public int Mertens(uint n){
    int m = 0;
    for(uint k = 1; k <= n; k++)
        m += MoebiusFunction(k);
    return m;
}

The implementation’s time complexity is simply $O(n \ln \ln n)$ .

Written by lewellen

2009-04-01 at 12:00 am

Posted in Uncategorized

Tagged with C# 2.0, Dynamic Programming, Integer Factorization, Number Theory

Generalized Interpreter Framework in C#

leave a comment »

Introduction

Like most Computer Science graduates, I had taken a Programming Languages course during college in which we built a compiler and studied the consequences of our design decisions. I had also taken a course in symbolic logic- particularly, looking at the sentential and predicate logic. Lately, I had been thinking about these two courses and thought it would be interesting to write an interpreter that would take in a sentence valid under sentential logic and output the resulting truth table.

After looking at what I had built, it became apparent that I could generalize my solution into a flexible framework where I could easily create a new interpreter for a desired (albeit simple) formal grammar and produce the desired outputs that other applications could then use for whatever purpose. The following is an overview of this framework and an example implementation for generating truth tables for sentences valid under sentential logic.

Framework

Specification

An Interpreter takes a string and produces an object hierarchy that a client can perform functions upon. The Interpreter does so by following the rules of a grammar that the string is assumed (although not garaunteed) to be valid under. The Interpreter will only be valid for context-free-grammars (CFG). A CFG consists of Terminals and Nonterminals. A Terminal is a character or sequence of characters that terminate a definition. A Nonterminal is a rule that defines the relationships between other Nonterminals and Terminals.

Design

interpreter_components

Interpreter designs differs from traditional compiler design, in that only the so-called front-end is implemented. There are three principal components involved in this process: Tokenizer, Parser and Semantic Analyzer.

A Tokenizer takes a string of characters and returns a collection of Tokens, where each Token is a tuple containing the accepted substring and meta data describing what the substring represents. Tokens are identified by looking for Terminals in the input string.

The Parser then builds (formally) a concrete syntax tree (informally a syntax tree) following the rules defined by the grammar. This is done by looking for Nonterminals in the collection of Tokens.

Finally, the Semantic Analyzer builds (formally) an abstract syntax tree (informally a semantic tree) by ignoring the syntax in the parse tree and constructing the appropriate tree for performing functions upon.

In the event of an exception, the Interpreter will write the details of the exception to a text writer (e.g., Console.Error) provided by the client of the Interpreter.

Exceptions are to be thrown under the following conditions:

The input string is null or empty, or none of the Terminals are able to accept a character in the input string.
None of the Nonterminals are able to accept a set of tokens, or the number of tokens is deficient for the Nonterminals to identify a match.

Implementation

abstract public class Tokenizer<T> {
    protected TerminalList<T> Terminals { get; private set; }

    public Tokenizer() {
        Terminals = new TerminalList<T>();
        loadTerminals();
    }

    public TokenList<T> Tokenize(string input) {
        if (string.IsNullOrEmpty(input))
            throw new UnexpectedEndOfInputException();

        TokenList<T> tokens = new TokenList<T>();
        Token<T> candiate;

        for (int n = 0; n < input.Length; n++) {
            if (char.IsWhiteSpace(input[n]))
                continue;

            if (!terminalExists(input, n, out candiate))
                throw new UnexpectedInputException(n);

            tokens.Add(candiate);
            n += candiate.Lexeme.Length - 1;
        }

        return tokens;
    }

    private bool terminalExists(string input, int n, out Token<T> candiate) {
        candiate = null;
        foreach (Terminal<T> terminal in Terminals)
            if (terminal.Exists(input, n, out candiate))
                return true;
        return false;
    }

    abstract protected void loadTerminals();
}

abstract public class Parser<T, P> {
    protected NonterminalList<T, P> Nonterminals { get; private set; }
    protected T[] FirstExpectedTokens { get; private set; }

    public Parser() {
        Nonterminals = new NonterminalList<T, P>();
        loadNonterminals();

        FirstExpectedTokens = new T[Nonterminals.Count];
        for (int n = 0; n < Nonterminals.Count; n++)
            FirstExpectedTokens[n] = Nonterminals[n].FirstExpectedToken;
    }

    public P Parse(TokenList<T> tokens) {
        return Parse(tokens, 0, tokens.Count - 1);
    }

    public P Parse(TokenList<T> tokens, int n, int m) {
        P parsedSentence;
        foreach (Nonterminal<T, P> nonterminal in Nonterminals)
            if (nonterminal.Exists(tokens, n, m, out parsedSentence))
                return parsedSentence;

        throw new UnexpectedTokenException<T>(tokens[n], FirstExpectedTokens);
    }

    abstract protected void loadNonterminals();
}

abstract public class SemanticAnalyzer<P, S> {
    abstract public S Analyze(P sentence);
}

abstract public class Interpreter<T, P, S> {
    private TextWriter externalLogger;

    abstract protected Tokenizer<T> Tokenizer { get; }
    abstract protected Parser<T, P> Parser { get; }
    abstract protected SemanticAnalyzer<P, S> SemanticAnalyzer { get; }

    public Interpreter(TextWriter externalLogger) {
        this.externalLogger = externalLogger;
    }

    public bool Interpret(string candidateSentence, out S sentence, out TokenList<T> tokens) {
        sentence = default(S);
        tokens = null;

        try {
            tokens = Tokenizer.Tokenize(candidateSentence);
            sentence = SemanticAnalyzer.Analyze(Parser.Parse(tokens));

            return true;
        } catch (UnexpectedInputException uie) {
            logger(uie.Message);
            logger("'{0}'", candidateSentence);
            logger(" {0}^", string.Empty.PadLeft(uie.AtIndex, '.'));

        } catch (UnexpectedEndOfInputException ueie) {
            logger(ueie.Message);
            logger("'{0}'", candidateSentence);
            logger(" {0}^", string.Empty.PadLeft(candidateSentence.Length, '.'));

        } catch (UnexpectedTokenException<T> pe) {
            logger(pe.Message);
            logger("'{0}'", candidateSentence);
            logger(" {0}^", string.Empty.PadLeft(pe.Unexpected.StartsAtIndex, '.'));
        }

        return false;
    }

    private void logger(string format, params object[] values) {
        externalLogger.WriteLine(format, values);
    }
}

Example

Specification

SL Backus-Naur Form (BNF)
sentence	::=	sentence_letter
	\|	~ sentence
	\|	( sentence connective sentence )

sentence_letter	::=	letter
sentence_letter	\|	letter number

connective	::=	v
	\|	^
	\|	->
	\|	<->

letter	::=	a
	\|	…
	\|	z
	\|	A
	\|	…
	\|	Z

number	::=	number digit
number	\|	digit

digit	::=	0
	\|	…
	\|	9

Sentential Logic (SL) is a simple formal system that consists of two semantic elements: primitive types called Sentence Letters that may either be true or false, and expressions built upon Sentence Letters called Sentences. A Sentence Letter is any character a-z (lower or upper) followed by an optional number. Sentences are defined in terms of other sentences, the simplest is a plain Sentence Letter. Any negated ¬ sentence is also a sentence. Any two sentences connected by a conjunction ∧, disjunction ∨, material conditional → or material biconditional ↔ and enclosed by parentheses () is also a sentence under SL. No other arrangement of symbols constitutes a sentence under SL.

Connectives and negation Truth Tables
	¬	∧	T	F	∨	T	F	→	T	F	↔	T	F
T	F		T	F		T	T		T	F		T	F
F	T		F	F		T	F		T	T		F	T

A truth table has a column for each of the sentence letter that show up in a sentence and a column for the sentence. Each row is one Cartesian coordinate in the space $\{T, F \}^{n}$ where n is the number of the number sentence letters. By convention, one lists the rows in order all sentence letters being true, to the last row where all sentence letters are false.

Implementation

TerminalSyntax and TerminalSentenceLetter are subclasses of Terminal and implement the logic for determining if a certain syntax or sentence letter exists in an input string. TerminalSyntax takes in the TokenType and string to find in the input as configuration options. If one felt inclined, one could have implemented a TerminalRegularExpression class instead of two separate classes but I felt it was unnecessary.

public class SLTokenizer : Tokenizer<TokenType> {
    protected override void loadTerminals() {
        Terminals.AddRange(new Terminal<TokenType>[] {
            new TerminalSyntax(TokenType.Conjunction, "^"),
            new TerminalSyntax(TokenType.Disjunction, "v"),
            new TerminalSyntax(TokenType.LeftParen, "("),
            new TerminalSyntax(TokenType.MaterialBiconditional, "<->"),
            new TerminalSyntax(TokenType.MaterialConditional, "->"),
            new TerminalSyntax(TokenType.Negation, "~"),
            new TerminalSyntax(TokenType.RightParen, ")"),
            new TerminalSentenceLetter()
        });
    }
}

The three Nonterminal types for Connectives, Negation and Letters are subclasses of Nonterminal and implement the logic for determining if a collection of tokens matches the rules associated with each Nonterminal type.

public class SLParser : Parser<TokenType, ParsedSentence> {
    protected override void loadNonterminals() {
        Nonterminals.AddRange(new Nonterminal<TokenType, ParsedSentence>[] {
            new NonterminalSentenceConnective(this),
            new NonterminalSentenceNegation(this),
            new NonterminalSentenceLetter()
        });
    }
}

Nothing particularly exciting here, simply mapping the parsed sentences to actual sentences that will be used by the client code. Sentence implementations have the logic for evaluating themselves.

public class SLSemanticAnalyzer : SemanticAnalyzer<ParsedSentence, Sentence> {
    public override Sentence Analyze(ParsedSentence sentence) {
        ParsedSentenceLetter letter = sentence as ParsedSentenceLetter;
        if (letter != null)
            return new SentenceLetter(letter);

        ParsedSentenceUnary negation = sentence as ParsedSentenceUnary;
        if (negation != null)
            return new SentenceUnaryNegation(negation, Analyze(negation.Sentence));

        ParsedSentenceBinary connective = sentence as ParsedSentenceBinary;
        if (connective != null) {
            switch (connective.Operation.TokenType) {
                case TokenType.Conjunction:
                    return new SentenceBinaryConjunction(connective, Analyze(connective.Left), Analyze(connective.Right));
                case TokenType.Disjunction:
                    return new SentenceBinaryDisjunction(connective, Analyze(connective.Left), Analyze(connective.Right));
                case TokenType.MaterialBiconditional:
                    return new SentenceBinaryMaterialBiconditional(connective, Analyze(connective.Left), Analyze(connective.Right));
                case TokenType.MaterialConditional:
                    return new SentenceBinaryMaterialConditional(connective, Analyze(connective.Left), Analyze(connective.Right));
            }
        }

        throw new NotImplementedException();
    }
}

Nothing extra to implement in the SLInterpreter to add other than the constructor and properties.

public class SLInterpreter : Interpreter<TokenType, ParsedSentence, Sentence> {
    public SLInterpreter(TextWriter externalLogger) : base(externalLogger) { 

    }

    override protected Tokenizer<TokenType> Tokenizer {
        get { return new SLTokenizer(); }
    }

    override protected Parser<TokenType, ParsedSentence> Parser {
        get { return new SLParser(); }
    }

    override protected SemanticAnalyzer<ParsedSentence, Sentence> SemanticAnalyzer {
        get { return new SLSemanticAnalyzer(); }
    }
}

Once all of the Interpreter code has been completed, it becomes trivial to go and implement the truth table.

private void table(string input) {
    SLInterpreter interpreter = new SLInterpreter(Console.Out);
    TokenList<TokenType> tokens;
    Sentence sentence;

    if (!interpreter.Interpret(input, out sentence, out tokens))
        return;

    List<Variable> variables = tokens
       .Where((x) => x.TokenType == TokenType.Letter)
       .Select((x) => x.Lexeme)
       .Distinct()
       .Select((x) => new Variable(x))
       .ToList();

    foreach (Variable variable in variables)
        Console.Write("{0} ", variable.Identifier);
    Console.WriteLine("| {0}", input);

    for (int n = (1 << variables.Count) - 1; n >= 0; n--) {
        int N = n;
        for (int m = variables.Count - 1; m >= 0; m--) {
            variables[m].Value = (N & 1) == 1;
            N >>= 1;
        }

        IDictionary<Token<TokenType>, bool> tableRow = new Dictionary<Token<TokenType>, bool>();
        sentence.Evaluate(variables, tableRow);

        int offset = 2;
        foreach (Variable variable in variables) {
            Console.Write("{0} ", variable.Value ? "T" : "F");
            offset += 1 + variable.Identifier.Length;
        }

        Console.Write("| ");
        foreach (Token<TokenType> token in tableRow.Keys) {
            Console.CursorLeft = token.StartsAtIndex + offset;
            Console.Write(tableRow[token] ? "T" : "F");
        } Console.WriteLine();
    }
}

Written by lewellen

2009-03-01 at 12:00 am

Posted in Uncategorized

Tagged with C# 2.0, Interpreter Design, Sentential Logic

Ouroboros: reinventing Nibbles

leave a comment »

Introduction

I talked about some classic arcade games in a previous post that I had worked on over the years and mentioned that I’d get around to posting some implementation details of one of them. A few months later here we are and the following is an overview of the implementation details of Ouroboros- my revisioning of the classic arcade game Nibbles that I enjoyed playing and learning about back in my QBasic days.

This write-up will go over the activities associated with the software development process from specification to implementation. Before I get into the details, here’s a game play of what is that I’ll be explaining how to make:

Specification

The goal of the game is to collect rewards. Each time a reward is collected, the user’s score is increased. The snake is constantly moving in the direction last requested by the user. The user can direct the snake to move either left, up, right or down. To make the game more challenging, the snake will grow whenever the snake consumes a reward. The game then ends once the snake spans the entire board or the snake collides with itself. When the snake “hits” a wall, its position wraps around the board. When either of the terminating conditions is meet the user is asked if he or she wishes to play again.

Requirements

The user may control the direction the snake may move by using the keyboard. The following keys are valid: {←, ↑, →, ↓} and {a, w, d, s} to the directions {left, up, right and down}.

The game is to be displayed to the user as as command line interface (CLI), 2D graphical user interface (2DGUI) using WinForms and a 3D GUI (3DGUI) using Windows Presentation Foundation. The CLI and 2DGUI shall appear as boards that the snake and reward appear on. The 3DGUI shall appear as a torus that the snake and reward appear on.

The game may not appear to be slower as the length of the snake increases.

Design

The Board

The board is a simple coordinate system with a fixed side length $B$ . Each $\vec{x} \subset { \{ 0, 1, \ldots B - 1 \} }^{2}$ coordinate may be occupied by at most one snake segment. For each view, a mapping $f : M \to V$ from the model space, $M$ , to the view space, $V$ , is necessary to achieve the required behavior.

snake_space1

For the CLI view, let $f(\vec{x}) = \vec{x}$ since every coordinate maps one-to-one with a cursor position on the console.

The 2DGUI view requires a scaling factor, $c > 1$ , otherwise the board would appear to be too small to play- unless for example, upon a cellphone LCD. Let $f(\vec{x}) = c\vec{x}$ .

The 3DGUI view requires an initial mapping from a $\vec{x} = (x,y)$ coordinate to a $\vec{y} = (\vartheta, \varphi)$ system. This is accomplished by $g(\vec{x}) = \frac{2\pi}{B}\vec{x}$ where $B$ is the length of the edge of the board. A torus is defined in terms of an interior radius, $R$ , and the swept radius, $r$ . Thus a torus is defined as the following:

$\displaystyle (f \circ g)(\vec{x}) = \begin{pmatrix}(R + r cos(\varphi))cos(\vartheta)\\(R + r cos(\varphi))cos(\vartheta)\\r sin(\varphi)\end{pmatrix}$

The Snake

The snake is conceptually a sequence of segments that I choose to represent as a singly-linked list where each node contains a pointer to the next segment and the segment’s position. The following illustrates a snake of length five:

snake_model

To achieve movement, the position of the head segment is passed to the next segment, and the next segment on to its next segment so on and so forth until the tail is reached.

Each time the snake moves, its $x^{(k)}$ coordinate will be calculated as $x_{n+1}^{(k)} = x_{n}^{(k)} + dx_{\text{dir}}^{(k)} \pmod{B}$ .

Scoring should be done in such a way that rewards become more valuable as time continues. Since the initial length of the snake is 1, a snake of length $N$ will have collected $N - 1$ rewards. Thus, let $S(N) = \sum_{n = 0}^{N}{100 (1 - e^{\frac{-(N - 1)}{10}})}$ represent the scoring function. Where 100 is maximum score for a reward, -1/10 is the decay factor.

Once a snake has consumed a reward, a new node is added to the tail with a location identical to the tail location.

To determine if a the snake is on top of a reward, each segment’s position will be compared to the reward’s position. If a segment and reward are identical then the snake is on top of the reward. If no match is found, then the snake is not on top of the reward. This process can be done in linear time. Constant time, if you choose to generate rewards that are not on top of snake.

When drawing the game it is useful to observe that the only thing that ever changes between time step is the the head and tail of the snake. Thus, it is prudent to only draw the current head position and erase the previous tail position. This will produce a length independent drawing method so that the game does not appear to be slower as the snake gets larger.

Implementations may be written using recursion, but beware that with larger board sizes that you run the risk of a stack overflow on systems that don’t give you much memory to work with. Using a cursor to search the singly-linked list may be more appropriate when using larger board sizes.

Implementation

I decided to go with a Model-View-Controller (MVC) pattern since I’d like to be able to view the CLI, 2DGUI and 3DGUI all at once. Below is a complete UML class diagram of all the MVC components that I choose to implement.

The following is the core engine of the game; it perform each of the core tasks of performing logic, drawing the board, getting user input and maintaining time.

public class Program {
    [STAThread]
    static public void Main(string[] args) {
        List views = new List(new IGameView[] {
            new CLIGameView(),
            new GUI2DGameView(),
            new GUI3DGameView()
        });
        IGameController controller = new CLIGameController();

        int boardSize = 32;
        double maxScore = double.MinValue;

        views.ForEach((view) => view.initialize(boardSize));

        do {
            SnakeDirection desiredDirection = SnakeDirection.Up;
            SnakePoint reward = SnakePoint.Random(boardSize);
            SnakeSegment snake = new SnakeSegment(SnakePoint.Random(boardSize));

            views.ForEach((view) => view.drawBoard());

            do {
                if (controller.InputAvailable) {
                    SnakeDirection possible = controller.getDirection();
                    if (possible != SnakeDirection.Nop)
                        desiredDirection = possible;
                }

                if (snake.isOnTopOf(reward)) {
                    snake.grow();

                    if (snake.Length != boardSize * boardSize) {
                        do {
                            reward = SnakePoint.Random(boardSize);
                        } while (snake.isOnTopOf(reward));
                    }

                    maxScore = Math.Max(maxScore, snake.Score);

                    views.ForEach((view) => view.drawScore(snake.Score, maxScore));
                }

                SnakePoint oldTail = snake.Tail.Location;

                snake.move(desiredDirection, boardSize);

                views.ForEach((view) => view.drawSnake(snake, oldTail));
                views.ForEach((view) => view.drawReward(reward));

                System.Threading.Thread.Sleep(1000 / 15);
            } while (!snake.selfCollision());

            views.ForEach((view) => view.drawGameOver());
            views.ForEach((view) => view.drawPlayAgain());

        } while (controller.playAgain());

        views.ForEach((view) => view.deinitialize());
        views.Clear();
    }
}

public class GUI3DGameView : IGameView {
    private int boardSize;
    private Form canvas;
    private ScoreLabel score;
    private TorusScene scene;

    public int BoardSize {
        get { return boardSize; }
    }

    public GUI3DGameView() {
        canvas = new Form();
        canvas.BackColor = System.Drawing.Color.FromArgb(0x33,0x33,0x33);
        canvas.FormBorderStyle = FormBorderStyle.FixedToolWindow;
        canvas.MaximizeBox = false;
        canvas.MinimizeBox = false;
        canvas.SizeGripStyle = SizeGripStyle.Hide;
        canvas.Text = "GUI3DGameView";
        canvas.ClientSize = new Size(384, 384);

        ElementHost host = new ElementHost();
        host.Child = scene = new TorusScene();
        host.Dock = DockStyle.Fill;
        canvas.Controls.Add(host);

        score = new ScoreLabel();
        score.Dock = DockStyle.Bottom;

        canvas.Controls.Add(score);
    }

    public void initialize(int boardSize) {
        this.boardSize = boardSize;

        if (!canvas.Visible)
            canvas.Show();
    }

    public void deinitialize() {
        canvas.Dispose();
    }

    public void drawBoard() {
        score.reset();
        scene.removeSnake();
    }

    public void drawGameOver() {

    }

    public void drawPlayAgain() {

    }

    public void drawReward(SnakePoint reward) {
        scene.moveReward(reward.x, reward.y);
    }

    public void drawScore(double current, double max) {
        score.setScore(current, max);
    }

    public void drawSnake(SnakeSegment head, SnakePoint oldTail) {
        scene.addSegment(head.Location.x, head.Location.y, head.Length);
    }
}

using System;
using System.Collections.Generic;
using System.Windows.Controls;
using System.Windows.Media;
using System.Windows.Media.Media3D;

namespace Snake.View.GUI3D {
    public class TorusScene : Viewport3D {
        private Queue<ModelVisual3D> patches;
        private ModelVisual3D reward;

        public TorusScene() {
            Camera = new PerspectiveCamera(new Point3D(10, 10, 10), new Vector3D(-10, -10, -10), new Vector3D(0, 1, 0), 60);

            AmbientLight aLight = new AmbientLight(Color.FromRgb(0x33,0x33,0x33));
            ModelVisual3D aLightHost = new ModelVisual3D();
            aLightHost.Content = aLight;
            Children.Add(aLightHost);

            DirectionalLight light = new DirectionalLight(Colors.Orange, new Vector3D(0, -10, 0));
            ModelVisual3D lightHost = new ModelVisual3D();
            lightHost.Content = light;
            Children.Add(lightHost);

            DirectionalLight rearLight = new DirectionalLight(Colors.LightBlue, new Vector3D(0, 10, 0));
            ModelVisual3D rearLightHost = new ModelVisual3D();
            rearLightHost.Content = rearLight;
            Children.Add(rearLightHost);

            Model3DGroup torus = new Model3DGroup();
            double N = 16.0;
            double dTheta = Math.PI / N, dPhi = Math.PI / N;
            double R = 5.0, r = 2.0;

            Color surface = SnakeColors.MGround;

            for (double theta = 0.0; theta <= 2.0 * Math.PI; theta += dTheta) {
                for (double phi = 0.0; phi <= 2.0 * Math.PI; phi += dPhi) {
                    Point3D[] S = square(dTheta, dPhi, R, r, theta, phi);
                    torus.Children.Add(triangle(S[0], S[1], S[3], surface));
                    torus.Children.Add(triangle(S[3], S[2], S[0], surface));
                }
            }

            ModelVisual3D model = new ModelVisual3D();
            model.Content = torus;
            Children.Add(model);

            patches = new Queue<ModelVisual3D>();
        }

        public void addSegment(double u, double v, int max) {
            ModelVisual3D snake = addSphere(u, v, 0.5, SnakeColors.MHead);

            if (patches.Count != 0 && patches.Count == max)
                Children.Remove(patches.Dequeue());
            patches.Enqueue(snake);

            Point3D[] S = square(Math.PI / 16.0, Math.PI / 16.0, 5.0, 2.5, u / 16.0 * Math.PI, v / 16.0 * Math.PI);
            double r = 30.0 / Math.Sqrt(3.0) / Math.Sqrt(S[0].X * S[0].X + S[0].Y * S[0].Y + S[0].Z * S[0].Z);
            Camera.SetValue(PerspectiveCamera.PositionProperty, new Point3D(r * S[0].X, r * S[0].Y, r * S[0].Z));
            Camera.SetValue(PerspectiveCamera.LookDirectionProperty, new Vector3D(-r * S[0].X, -r * S[0].Y, -r * S[0].Z));
        }

        public void moveReward(double u, double v) {
            if (reward != null) {
                Children.Remove(reward);
                reward = null;
            }

            reward = addSphere(u, v, 0.25, SnakeColors.MReward);
        }

        public void removeSnake() {
            while (patches.Count != 0)
                Children.Remove(patches.Dequeue());
        }

        private ModelVisual3D addSphere(double u, double v, double r, Color color) {
            Model3DGroup sphere = new Model3DGroup();
            Point3D center = parameterized(5.0, 2.0 + r, u / 16.0 * Math.PI, v / 16.0 * Math.PI);
            Vector3D vec = new Vector3D(center.X, center.Y, center.Z);

            double dTheta, dPhi;
            dTheta = dPhi = Math.PI / 3.0;

            for (double theta = 0.0; theta <= 2.0 * Math.PI; theta += dTheta) {
                for (double phi = 0.0; phi <= 2.0 * Math.PI; phi += dPhi) {
                    Point3D[] S = square(dTheta, dPhi, 0, r, theta, phi);
                    for (int n = 0; n < S.Length; n++)
                        S[n] = Point3D.Add(S[n], vec);

                    sphere.Children.Add(triangle(S[0], S[1], S[3], color));
                    sphere.Children.Add(triangle(S[3], S[2], S[0], color));
                }
            }

            ModelVisual3D model = new ModelVisual3D();
            model.Content = sphere;
            Children.Add(model);

            return model;
        }

        private Point3D parameterized(double R, double r, double theta, double phi) {
            return new Point3D(
                (R + r * Math.Cos(phi)) * Math.Cos(theta),
                r * Math.Sin(phi),
                (R + r * Math.Cos(phi)) * Math.Sin(theta)
            );
        }

        private Point3D[] square(double dTheta, double dPhi, double R, double r, double theta, double phi) {
            return new Point3D[] {
                parameterized(R, r, theta, phi),
                parameterized(R, r, theta, phi + dPhi),
                parameterized(R, r, theta + dTheta, phi),
                parameterized(R, r, theta + dTheta, phi + dPhi)
            };
        }

        private Model3DGroup triangle(Point3D a, Point3D b, Point3D c, Color color) {
            MeshGeometry3D mesh = new MeshGeometry3D();
            mesh.Positions.Add(a);
            mesh.Positions.Add(b);
            mesh.Positions.Add(c);
            mesh.TriangleIndices.Add(0);
            mesh.TriangleIndices.Add(1);
            mesh.TriangleIndices.Add(2);

            Material material = new DiffuseMaterial(new SolidColorBrush(color));
            GeometryModel3D model = new GeometryModel3D(mesh, material);
            Model3DGroup group = new Model3DGroup();
            group.Children.Add(model);
            return group;
        }
    }
}

Written by lewellen

2009-02-01 at 12:00 am

Posted in Uncategorized

Tagged with .Net 3.5, C# 3.0, Game Programming, Nibbles, WPF

Embedded Streaming Radio Project

with one comment

It’s been a while since I posted anything here, partly a function of a lack of interest, time and viewership. Part of my new years resolution was to try and post something around here maybe once a month. So, I figure I’d post on a hardware project that I’ve been tinkering around with the past couple months. It took me a while to gather this info so hopefully it will save others time looking to build a similar project.

I enjoy listening to the SHOUTcast streaming radio service using Winamp but after awhile I really want to be able to just listen to the stations on my shelf stereo system rather than on my laptop. Thus a pretty simple little idea:

Build a device that has a SHOUTcast complaint client that I can configure to point to a local shoutcast sever running on my laptop so that I can stream my mp3 collection or listen to any streaming station through my stereo shelf system.

Given that simple problem statement, I started thinking about how I would go about getting everything set up:

stereo_network

With all of that in mind, I have enough for an initial laundry list of requirements for the hardware component:

RCA out to connect to my stereo system
Built-in 1000/100/10 Gigabit Ethernet or 802.11b/g wireless to access the radio streams
http server running on port 80/8080 so that I could remotely configure it all
Maybe include a LCD for kicks or a touch screen for album art/misc content

Now there are couple paths to go down from here: the first was to run with the project thinking that I could go out and purchase all the hardware components described above- assemble them, write a simple http server and do some low level assembly. Second option is to go out and see what available open source options are out there and try to purchase a pre-built embedded system. The last option was to search the market for a similar product.

The first option sounds like a lot of fun, but doesn’t seem very feasible from a time stand point. Third option does offer a perfect solution through Logitech’s Squeezebox Classic which is great from a time stand point but not so great from a satisfaction standpoint so that leads one to option number two.

So the hunt was on to find the perfect combo of pre-existing components and figuring out how to get them all to play nicely. First thing I went looking for was to see if there were any open source SHOUTcast clients out there. Turns out there is a really great project out there called the SnackAmp Music Player that does everything that I’d like to do. In fact, it comes along with a great remote control feature targeted exactly at the kind of scenario I’m trying to build.

Next step was to look at what platforms SnackAmp would run on. Being an open source project they have builds available for standard i386 Linux distributions and of course Microsoft Windows. Not being a person particular about operating systems I decided that I would go with Linux since it’s free and since there are a number of minimalistic distributions out there.

Finally, I needed to decide on a piece of hardware that would meet my needs. I want something compact that I can place next to my stereo that is low power and quiet- something a little smaller than a DSL modem or smaller than standard CD wallet. Looking around it seems that VIA is the key player in the mini-itx market which the form factor of most of the boards I was looking at. mini-itx.com and mini-box.com have a number of solutions but few of their offerings had the 802.11b/g that I was looking for. I’m not 100% decided on what I would like to purchase from either site, but the average cost appears to be around 250-300 USD for a board, memory and enclosure.

Surmising all the above, I think I’d like to go with the following technology stack:

Stereo System	SnackAmp	Firefox	SHOUTcast Server	NAS
	ttylinux	Windows XP SP2
	mini itx	Laptop
	802.11b/g LAN

Total cost would be in the 250-300 USD range -add on an additional 100-300 USD for a cheap NAS- since the hardware is the only thing that I need to get. Now, I mentioned previously that Logitech offers an almost identical device for 300 USD (at the time of this post). So the question arises, which one is the better buy?

The commercial solution has been tested and it works with multiple services and seems to have a pretty large community built around it- but then again there’s nothing to learn other than how to use it. On the other hand, a custom built solution can be repurposed to fit future use cases that I have yet to think up so it may offer in the long run a great utility compared to its competition.

Short answer is that I have yet to decide on which option is right since I’m still looking around to see what’s out there. (If you know of additional products post them in the comments). If I move forward with any of this I’ll be sure to post details as they come along.

Written by lewellen

2009-01-01 at 12:52 pm

Posted in Uncategorized

Tagged with Internet Radio, Project

Antimatroid, The

Getting a Development Network Started

Multi-agent ordering

The next decade of the Internet

Busy month

Sudoku Solver in Haskell

Sudoku Solver in C# using Lambda Expressions

Integer Factorization by Dynamic Programming with Number Theoretic Applications

Generalized Interpreter Framework in C#

Introduction

Framework

Specification

Design

Implementation

Example

Specification

Implementation

Ouroboros: reinventing Nibbles

Introduction

Specification

Requirements

Design

The Board

The Snake

Implementation

Embedded Streaming Radio Project

Pages

Tags

Archives

Aesthetics

Computer Science

Mathematics

Security

Meta