Wonderment

31 08 2007

I wonder which is more complex. A collection of interacting brains or the universe. I also wonder which allows whom.

Advertisements




rndm thuts on cmunictin

24 08 2007

The other day I was thinking about hours and hotels before stumbling upon a brilliant discovery. Grammar Nazis are Champions of Inconsistency.

The rules of syntax of natural languages are filled with exceptions and inconsistencies due to their organic manner of growth. Thus, anyone who champions the grammar of a natural language such as English must necessarily be a Champion of Inconsistency.

For example, H is not a vowel. But no one ever says a hour, its an hour. But you say a hotel. Cause an hotel sounds weird. []

This is why I prefer to have language serve me and not be its servant. The ultimate purpose of language is to allow communication between two objects capable of processing and acting on it, so long as it does this then it suffices. Natural Language carries thoughts from the human mind to the external, so it will always be imperfect. It may only suffice. Hence it seems silly to get annoyed when ppl – kids looking to display identity/membership – arbitrarily drp vwls and cnsnants from wrds. These people may use language as they see fit, it is merely an imperfect human tool.

If they are incomprehensible to me I say simply, I am sorry but I do not speak that language. I can only assume that their urgency to communicate outside their native group is minimal.





Eating NP-completely at Mcdonalds

21 08 2007

Ever since I was a child I have always been aware of and appreciated the difficulty involved in solving NP-complete problems. While the other children were out at their tables eating their food, I would stand often, trying to decide just what choices would allow me to get the most value for my money. It was a treat you see, so we didnt get to do it all the time. I used to take a long time making decisions, over analyzing decision paths whose relevance might be deemed questionable. I still do this actually, much to the amusement (and often frustrated bemusement of my friends). As an example, one of my favourite eat out treats was going to McDonalds. I realized that rather than buying unfilling happy meals I could do better by buying a number of individual sandwiches and fries separately for a similar price.

I still like to go to mcdonalds and still take time (counted in minutes) trying to optimize my cost-value ratio. Having recently gotten an Acer n310, the solution was simple. Use the knapsack algorithim to decide how to pack as much McDonalds for the price I wish to pay into my stomach while also cutting time and ensuring that I am actually making a good choice. So I did that.

The program was written on .NET 2.0, in F# and it runs on both my PocketPC and on my PC. I built the F# dll and then slapped a GUI on it using Visual C# for both versions.

At the moment the menu is hard-coded in and so are the costs and value function. The program works well enough. It validated some of my choices (3 hamburgers and 1 fillet, 1 small fries was fair for a £5 limit) while showing that with other choices by varying a single item I could have gotten more value for a bit less. The code is not very long, the knapsack contents function and .net interfaces are given below:

let rec bag_contents cost_i (best_items_per_cost : int array) =     

    match cost_i with
        | _ when cost_i <= 0 -> []
        | cost_current -> cost.[0] <- cost_current
                          let next_item = cost_current - cost.[best_items_per_cost.[cost_current]]               
                          best_items_per_cost.[cost_current]::(bag_contents next_item  best_items_per_cost)

//....
//Exposed using:
let rec mkString xs = 
    match xs with
        | [] -> ""
        | x :: xs ->  if x > 0 then assoc_list.[x-1] + " | " + (mkString xs) else " | " + (mkString xs)

type Knap = class
     new () = {}
     member this.Packed_Bag cost_size_preffered = mkString (best_bag cost_size_preffered size_menu)
end

Some things I wish to do is allow feeding of textfiles of items and cost/value functions (merely tables). As well I would like to do suggestions and variety. At the moment for example it tells me that Fries,Fries,Fries,Fries is good for £3.56. This is to be expected given the nature of the algorithm. But something like, for Np (where N is an integer) more or less you might try this combination or getting this or that item. So it’d also take a range |k| when making suggestions.

Defining value is tricky as well but that cant be helped.

knap.jpgknapm.jpg

Numeric updown in .NET compact doesnt support decimals.





More Haskell and Some Nemerle

16 04 2007

Ive recently had to complete a paper so I have not been able to do too much programming. However, even in the few days that I have used it Haskell has allowed me to write extremely short yet expressive programs, whose equivalence I would not know how to write so simply in C++ or C#. The programs are pretty simple. In one, I have a function which takes a list of numbers and a function and builds a modulo table using the function which I have defined prior.

Basically it makes a modulo table for Zn = [0.. (n-1)].

aMod :: Int -> Int -> Int -> Int

aMod a b m = (a + b) `mod` m
mMod a b m = (a * b) `mod` m

modulo_table a f =
	let k = length a in
	[((f i 1 k), (f 1 j k), (f (f i 1 k) (f 1 j k) k) )  | i <- a, j <- a]

I know the above is not efficient since it applies f at least twice more than it needs to. If anyone knows how it can be improved please tell. However it was done as such to make it easier to check from the Hugs output thing. In a real program I’d simply make a list [f i j k | i <- a, j <- a ] and format it accordingly. But I havent gotten to monads yet :)

modulo_table2 [0..3] aMod
[0,1,2,3,1,2,3,0,2,3,0,1,3,0,1,2]

modulo_table [0..11] mMod
[(0,0,0),(0,1,0),(0,2,0),(0,3,0),(0,4,0),(0,5,0),(0,6,0),(0,7,0),(0,8,0),(0,9,0),(0,10,0),(0,11,0),(1,0,0),(1,1,1),(1,2,2),(1,3,3),(1,4,4),(1,5,5),(1,6,6),(1,7,7),(1,8,8),
(1,9,9),(1,10,10),(1,11,11),(2,0,0),(2,1,2),(2,2,4),(2,3,6),(2,4,8),(2,5,10),(2,6,0),(2,7,2),(2,8,4),(2,9,6),(2,10,8),(2,11,10),(3,0,0),(3,1,3),(3,2,6),(3,3,9),(3,4,0),
(3,5,3),(3,6,6),(3,7,9),(3,8,0),(3,9,3),(3,10,6),(3,11,9),(4,0,0),(4,1,4),(4,2,8),(4,3,0),(4,4,4),(4,5,8),(4,6,0),(4,7,4),(4,8,8),(4,9,0),(4,10,4),(4,11,8),(5,0,0),(5,1,5),
(5,2,10),(5,3,3),(5,4,8),(5,5,1),(5,6,6),(5,7,11),(5,8,4),(5,9,9),(5,10,2),(5,11,7),(6,0,0),(6,1,6),(6,2,0),(6,3,6),(6,4,0),(6,5,6),(6,6,0),(6,7,6),(6,8,0),(6,9,6),(6,10,0),
(6,11,6),(7,0,0),(7,1,7),(7,2,2),(7,3,9),(7,4,4),(7,5,11),(7,6,6),(7,7,1),(7,8,8),(7,9,3),(7,10,10),(7,11,5),(8,0,0),(8,1,8),(8,2,4),(8,3,0),(8,4,8),(8,5,4),(8,6,0),(8,7,8),
(8,8,4),(8,9,0),(8,10,8),(8,11,4),(9,0,0),(9,1,9),(9,2,6),(9,3,3),(9,4,0),(9,5,9),(9,6,6),(9,7,3),(9,8,0),(9,9,9),(9,10,6),(9,11,3),(10,0,0),(10,1,10),(10,2,8),(10,3,6),
(10,4,4),(10,5,2),(10,6,0),(10,7,10),(10,8,8),(10,9,6),(10,10,4),(10,11,2),(11,0,0),(11,1,11),(11,2,10),(11,3,9),(11,4,8),(11,5,7),(11,6,6),(11,7,5),(11,8,4),
(11,9,3),(11,10,2),(11,11,1)]

——————-
The next program I wrote is one which allows one to compose permutation groups and can build cayley tables for said permutation groups. I do not see it being difficult to extend to be more general but then Cayley’s Theorem would have that doing that may not even be necessary. hehe. Basically it takes a map described as a tuple (which is basically what a function is in the mathematical sense) and follows the the pairs to create a composition.

{-The task of the algorithim is to go through each tuple in the list and for each tuple try to match the given variable.
The matched tuples opposite pair is returned and matched to some iteration -}

sec list2 a = head [b | (n,b) <- list2, n == a]

o :: [(Int,Int)] -> [(Int,Int)]-> [(Int,Int)]
o list1 list2 = let n = length list1 in [ (a, (sec list1 (sec list2 a)) ) | a <- [1..n]]

//////////////

Hugs> a
[(1,2),(2,3),(3,1)]
Hugs> a `o` e `o` r `o` b
(1,3),(2,2),(3,1)]

This example works on the symmetry group of a triangle.

e,a,b,r,s,t::[(Int,Int)]

l = [(e,'e'),
(a,'a'),
(b,'b'),
(r,'r'),
(s,'s'),
(t,'t')]

e = [(1,1),(2,2),(3,3)]
a = [(1,2),(2,3),(3,1)]
b = [(1,3),(2,1),(3,2)]

r = [(1,1),(2,3),(3,2)]
s = [(1,3),(2,2),(3,1)]
t = [(1,2),(2,1),(3,3)]

(&) j k  = [ b | (n,b) <- l, n == (j `o` k)]

cayley_table = [  ( b, d, a&c    )  | (a,b) <- l, (c,d) <- l]

cayley_table
[('e','e',"e"),('e','a',"a"),('e','b',"b"),('e','r',"r"),('e','s',"s"),('e','t',"t"),
('a','e',"a"),('a','a',"b"),('a','b',"e"),('a','r',"t"),('a','s',"r"),('a','t',"s"),
('b','e',"b"),('b','a',"e"),('b','b',"a"),('b','r',"s"),('b','s',"t"),('b','t',"r"),
('r','e',"r"),('r','a',"s"),('r','b',"t"),('r','r',"e"),('r','s',"a"),('r','t',"b"),
('s','e',"s"),('s','a',"t"),('s','b',"r"),('s','r',"b"),('s','s',"e"),('s','t',"a"),
('t','e',"t"),('t','a',"r"),('t','b',"s"),('t','r',"a"),('t','s',"b"),('t','t',"e")]

The cayley table is based around assigning pairing a letter to a group element. Then the operator (&) basically matches the element of a predefined list to the composition of the given elements.

#pragma indent
using System;
using System.Console;
using Nemerle.Utility;
using Nemerle.Collections;

module Program

aMod (a :int, b : int, m : int) : int
	(a + b) % m

mMod (a:int, b:int, m : int) : int
	(a * b) % m

modulo_table2 (a : list[int], f : (int * int* int)-> int)  : list[int]
	def k = List.Length(a)
	$[f(i, j , k)  | i in a, j in a]

//this feels me with unhappiness. if anyone knows how pattern matching on tuples works in nemerle please let me know.
sec(list2 : list[(int * int)], a : int): int
	def tup = List.Head(List.Filter(list2, fun(x) { if(x[0]==a)true else false}  ) )//  Head $[v[1] | v in list2, v[0] == a]
	tup[1]

public static @<.> (list1 : list[(int * int)], list2 : list[(int * int)]) : list[(int * int)]
	def n = List.Length(list1);
	$[ ( /**/ a, sec(list1, sec(list2, a) ) /**/) | a in [1..n]]

Main() : void

	def m = Int32.Parse(ReadLine()) - 1
	def z = modulo_table2($[0..m], aMod)

	def e = [(1,1),(2,2),(3,3)]
	def a = [(1,2),(2,3),(3,1)]
	def b = [(1,3),(2,1),(3,2)]

	def r = [(1,1),(2,3),(3,2)]
	def s = [(1,3),(2,2),(3,1)]
	def t = [(1,2),(2,1),(3,3)]

	def l = [(e,'e'),(a,'a'),(b,'b'),(r,'r'),(s,'s'),(t,'t')]

	mutable n = 0;
	def chk (j , k)
	$[ x[1] | x in l, x[0] == j <.> k]

	def cayley_table = $[  ( b, d, chk(a,c)   )  | (a,b) in l, (c,d) in l]

	mutable n = 0;

	foreach(a in z)
		Write($"$a ")
		if(n < m) n++
		else
			n=0
			WriteLine("")

ReadLine()

12
0 1 2 3 4 5 6 7 8 9 10 11
1 2 3 4 5 6 7 8 9 10 11 0
2 3 4 5 6 7 8 9 10 11 0 1
3 4 5 6 7 8 9 10 11 0 1 2
4 5 6 7 8 9 10 11 0 1 2 3
5 6 7 8 9 10 11 0 1 2 3 4
6 7 8 9 10 11 0 1 2 3 4 5
7 8 9 10 11 0 1 2 3 4 5 6
8 9 10 11 0 1 2 3 4 5 6 7
9 10 11 0 1 2 3 4 5 6 7 8
10 11 0 1 2 3 4 5 6 7 8 9
11 0 1 2 3 4 5 6 7 8 9 10




Haskell

12 04 2007

I have been trying to write programs in OCaml, with the keyword here being trying. What little I managed to learn has faded quite quickly due to my disuse of the knowledge. So far I have been programming by “instinct”:

randoms snips:

let addm a b m = (a + b) mod m
let mm a b m = (a * b) mod m

let eq a b m = let g = a - b in if (g mod m) == 0 then true else false;;

let f n = let rec g a b n l = if n + 1 == List.length l then l else g (a + b) a n ( a ::l) in g 0 1 n []

let rec general_sorder_reccurence b a p q n l = if n + 1 == List.length l then l else general_sorder_reccurence (p*a + q*b) a p q n (a::l)

let sqf n = List.map (fun x -> x * x) (f n)
let sumf n = List.fold_left (+) 0 (sqf n)

let fgen_l n = let rec gen_l n l = if List.length l == n then l else gen_l n ((sumf (List.length l)) :: l) in gen_l n []

Coding by ear is no fun so I decided I need to read a book on functional programming as I do not really have time to learn by experimentation. So I picked up a book on Functional programming taught with Haskell.

So far I must say I quite like this language and do not find it esoteric at all (perhaps it is because I never got too steeped in imperative programming or because I meet with the cousins of many of the notions of the language daily). Although I feel the Ocaml syntax (especially its pattern matching stuff) can be quite elegant, Haskell is alot more natural.

List comprehension and lazy evaluation are also really useful tools. (Nemerle has both of these too). I have only just begun and shall be reporting in with more substantial learnings as time passes.





Hiatus

8 04 2007

I have been busy trying to get into a comfortable schedule with life and so had to go on a forced blogging hiatus. I am now back on path and should be able to blog regularly henceforth.





Graphs

20 09 2006

I originally began my project in C# but quickly hit its abstraction ceiling. Well, I did not actually hit it but thinking forward to what I wanted to do, I realized that I need the best abstractions that the CLI could provide. Good as C# is, it is still too similar to C++ and Java.Whenever someone says .NET, people instantly think C#, which for people who enjoy exploring the outer edges of .NET (or more appropriately, the CLI) can be quite feather ruffling. With respect to programming, my project was began for three reasons: to rekindle my interest in programming, learn about .NET and the language independence it claims and to test its CLI claims. It has lived up to and beyond claims made in this area. Indeed Rebooted was suprised that I was able to get all the languages working cross platform – it was due to no special skill of mine but the incredible ease that which the CLI allows all those who obey its rules to interoperate. The languages need not know about each other so long as they speak the common tongue. Now, it is not completely trivial – there is still a need to design what classes you plan to expose outwards carefully, especially with respect to types (or enter typing hell – super nested generic classes), so they can be consumed without being choked on. Nonetheless the process is smooth and I have yet to feel the need to beat my computer with a bat while working on this project.

As stated in an earlier post and will be gone over in further detail in a future post, I have switched to Nemerle as the main vehicle for my engine for reasons due to its incredible macro system (lisp level, quotations, exposed compiler api), OOP and ease of code organization, rich type system (perhaps overly so…despite .net) and is functional (despite .net). The last part is what I want to focus on in this post.

People wonder if you can write a game in a functional language. I say yes but not in the strict sense. I take the same stance of functional programming as the makers of OCaml where (loosely quoting) they state that functional programming is not so much about immutability and lack of state but rather a program that is more or less a composition of black box like functions that though they may contain some mutability internally, on the whole, the behaviour of the program is essentially functional.

Nonetheless it does not do to obsess over a paradigm at the expense of sensibility. Some problems are more tractible taken from an imperative stance while others are from a functional. That is why functional languages that mix this well allow for ease of concept -> code as smoothly as possible. What Nemerle does is mix the concepts OOP quite seamlessly with functional programming. This has the added advantage of not only allowing the abstractions of the functional paradigm but also the organizational benefits of OOP. However this post will not show much Nemerle syntax (due to its rich type code of Nemerle the stuff I will show required alot of upcasts and type constraints and other stuff with the IL code not as good as F# version and so it made alot more sense to keep it in F#).

By abstracting away, you reduce the number of steps that take you from concept idea to concrete code, allowing less mistakes and efficient implentation. It makes alot of sense to write an RPG in a functional language.

In fact it does not make sense to write an RPG in a language like C++. RPGs contain alot of concepts (quests, game-player interactions, conversations, magic, skills, vocations/jobs/class, pathfinding, …) that are best represented with recursion, recursive data types and deconstructed with pattern matching.

I recently faced this when I decided to approach conversation in the game. Even C# did not have the appropriate constructs to do this most succintly. At first I thought to represent the conversations as trees but felt that they were not the most appropriate data structure. Thinking further, I realized that conversations are nothing more than directed graphs such that each node or vertex is either of type R (responses) or S (statements). Where for each R there is only one edge and each S has an edge to unique Rs (since if it does not then the S was not well formed). Each S has an edge to atleast one R node even if R is the empty node. By directed graph I mean a set (V,E) of vertices and edges with directed meaning that the edges are arrows:

conv_graph.jpg

I can think of no uses of the tools of graph theory with NPC conversing but if the need ever arises I will be sure to post on it. Nonetheless I set out to represent this concept in code. I realized that a graph could be treated as a list of vertices where each vertex is paired with a list of edges it points to. Hacking concepts out on the interactive top level of Ocaml i was able to come up with the following code:

let ins v g = (v , []) :: g

let edges_to a b g =
  let rec edg a b g g2 =
     match g with
        l :: g -> if fst l = a then ((a, b :: snd l) :: g2) @ g
                  else edg a b g (l::g2)
        | _ -> g
   in edg a b g []

let g1 = ins "Hello" []
let g2 = ins "bye" g1
edges_to "Hello" "bye" g2
;; 

The code is far shorter than the equivalent C# or C++ version would be. As well, by using the top level of OCaml I was able to accelerate my brainstorming and be assured that not only will I not have syntax errors when rewriting for the game, that it would work with no logical errors. As I stated earlier this did not translate well to Nemerle so I decide to do it in F#. However, to get it to communicate with other languages I had to rebrand it with .NET compliant classes.

The relevant F# code:

type 'a graph = ('a * 'a list) list 

let ins v g = (v , []) :: g

let rec edg a b g g2 =
     match g with
        l :: g -> if fst l = a then ((a, b :: snd l) :: g2) @ g
                  else edg a b g (l::g2)
        | _ -> g 

type 'a Graph = class
	new (a) = {graph_object = ins a [] }
	val mutable graph_object: 'a graph

member this.Insert_Edge (vertex_a, vertex_b) = 
		this.graph_object <- edg vertex_a vertex_b this.graph_object []
	member this.Insert (v)  = 
		this.graph_object <- (v , []) :: this.graph_object
	member this.List_Edges_To (v) = 
		List.to_array (List.assoc v this.graph_object)
end

Examples of usage:

dbg.PNG
The next post will not just be a test but will build converation around this and making accessing and listing much easier to the end user/me.