Implementing the toolbox, the playing field and reconsiderations.

Greetings readers.
I implemented the playing field and the toolbox. Both went fairly smooth, because they are simple adapters of the constrained mapping and the multiset.
However, while implementing these classes and especially the tests for them, I noticed a fair amount of duplication. Both the toolbox-tests and the playingfield tests contain a lot of tests which check “Is a small plus bomb combined with a small plus bomb really a big plus bomb? Is a small plus bomb with a small diagonal bomb really an O-bomb? …”. While I implemented tests for the actual gamestate, this duplication of a responsibility became glaringly obvious, because now I had that large clump of tests in the same file. Two times.
Thus, I sat bad and asked myself: Where does this come from? How can I remove this duplication?
The duplication results from the following facts:

• The toolbox has a method combine(bombtype, bombtype) which tries to remove a bomb of each type and puts a bomb of the combined type into the toolbox (or it raises an exception, because the bombs cannot be combined). I implemented this method, because while I played this game, I usually combined several bombs in the toolbox before actually placing them on the field.
• The playing field contains the functionality that placing a bomb on an existing bomb combines the bombs if possible (if it is impossible, it raises an exception, of course). This is necessary, because some problems require you to place a bomb on an existing bomb, combining them, in order to solve the problem.

Given this duplication, the question is: Can I remove it? And as you might suspect already, yes I can. Ask yourself: Do I need the combination in the toolbox? Do I need the combination in the playing field? The answers: Yes, I do need to combination functionality in the playing field, because, as I said, some puzzles require you to place a bomb on an existing bomb, combining them in order to solve the puzzle. Thus, we can assume: placing two bombs on the same field in the playing area combines them. However, if we can combine bombs by placing them on the same location on the playing field, we do not need to be able to combine them in the toolbox! It is actually quite clear, now that I pondered about it for a bit: put(l, combine(b1, b2)) == put(l, b1); put(l, b2). Thus, I can remove all combining functionality from the toolbox and keep it in the playing field.

This is nice, because it reduces the complexity in the solver. Before this thoughts, I figured I need to consider two types of moves: combining bombs in the toolbox and placing bombs on the playing field. This was simplified! Now I just have to consider the move of placing bombs on the playing field, because this includes combining bombs! This was a very successful evening.

Thanks for reading and see you next time,

Tetha.

Implementing the constrained mapping

Greetings readers,
more implementation fun, but at first, a little resignation on my part. Building these posts like the multiset is a lot of work and in fact, far less inspiring than I hoped to. If someone really wants step-by-step-logs back, let me now, otherwise, I will rather stay at a higher level.
While implementing the constrained mapping, I noticed I was hardcoding a strong assumption about my keys: The are indexable and every index needs to fulfill a certain predicate. Is this the case all the time? Of course not. Why should it?
Thus, I changed my design so the mapping contains a simple predicate which must be fulfilled by all keys. Second, I will implement a component-by-component-predicate which uses a list of sub-predicates to validate a vector. Given that, I still need a simple check if a value is in range, but that’s no problem.
Testing this limited mapping is a charm, because you can make the predicate always return True or return False, depending if you are interested in failures due to the predicate or not. For example, when checking the classical m.get(m.set(k, v), k) == v, you can set the predicate to constant true and everything is golden. If you want to check if predicate failure is handled properly, you set the predicate to constant false and testing for predicate checking is a charm.

Greetings, and thanks for reading,
Tetha.

Reorganizing code

Hello readers,
its time to push the development of our bombchain solver further. At first, if you did take a look at the folder with the multiset-code, the diagrams and such, you might have seen that everything was in a single folder. When I started to implement the constrained mapping, I figured: This will not scale. The result will consist of something like 20 classes and due to my habit of putting classes into their own file, I would end up with 20 files for classes. Add in 20 more files for tests and a bunch of files for the diagrams and their exported form and you will end up with a folder with 50 used files in it, plus even some swap files, git files, problem files and even more. I might describe it slightly differently: It would be a mess. Thus, I went to think about this for a bit and came to the following:
There will be toplevel folders diagrams, code and test. /diagrams contains the diagrams created on the way, /code contains the code created and /test contains the testcases for the code. /diagrams will be flat. /code will contain a subdirectory for each processing stage and each data exchange format (that is, /code/parser, /code/gamestate, /code/solver, /code/result and /code/output). These folder will probably be flat and just contain the necessary classes. The main script for the solver will go into /code and / will contain a single python script to run all tests (this needs to be in / or it requires a bit of path-hackery to find the code to test ). /test finally will mirror /code, just that every module and every package in /test must provide an attribute “tests” with all tests of the sub-elements collected. This creates nice concise packages and a nice dependencies

I won’t add the git repository to this post just yet. I will rather write a second post just now, because I already implemented the constrained mapping, but I wanted to separate these two concerns into two blog posts.

Greetings and thanks for reading,
Tetha

Implementing the Multiset

Greetings readers,

lets implement that multiset. As you might recall, the multiset is used to implement the toolbox of my bombchain solver. It has the methods to add, remove elements, a test for containment and a method to clone the entire set.

The rules a multiset follows are pretty easy:

• If you insert an element more often than you remove it then the element is in the multiset
• if you insert an element as often as you remove it then the element is not in the multiset
• if you insert an element less often than you insert it then you need to decide what is supposed to happen. I consider this an error.

Given this, it is easy to define the following tests:

class MultisetTest(unittest.TestCase):
    def setUp(self):
        self._subject = multiset.Multiset()

    def testContainment(self):
        self.assertFalse(5 in self._subject)

    def testInsertionContainment(self):
        self._subject.add(5)
        self.assertTrue(5 in self._subject)

    def testInsertionDeletionContains(self):
        self._subject.add(5)
        self._subject.remove(5)
        self.assertFalse(5 in self._subject)

    def testEmptyRemoval(self):
        self.assertRaises(multiset.MissingElement, self._subject.remove, 5)

    def testMultiInsertionDeletionContains(self):
        self._subject.add(5)
        self._subject.add(5)
        self._subject.remove(5)
        self.assertTrue(5 in self._subject)

class CloneTests(unittest.TestCase):
    def setUp(self):
        self._subject = multiset.Multiset()
        self._subject.add(10)
        self._clone = self._subject.clone()

    def testCloneInsertion(self):
        self._clone.add(5)
        self.assertFalse(5 in self._subject)

    def testCloneDeletion(self):
        self._clone.remove(10)
        self.assertTrue(10 in self._subject)

As you can see, I implemented the checks for adding and removing more / the same time / less for just a single insertion, but this will be sufficient, because those tests are no specification, but more a validation of the code I will produce. Second, there might be a bit of duplication left between InsertionDeletion and MultiInsertionDeletion. In both cases, an element is added in the beginning to the set. However, I decided that extracting a fixture for these two tests that adds a single element to the set is more confusing and the duplication is not that bad, because it shows the intent of the tests quite clearly.

Given this, I started to create the module multiset and the class in it.

I began with the MultiInsertionDeletion test, because I figured that this tests would use the most meat of the class and building the simplest code that might work for this test would be the least wasteful step. Given this, I created this code:

class Multiset:
    def __init__(self):
        self._elements = collections.defaultdict(int)

    def add(self, element):
        self._elements[element] += 1

    def __contains__(self, element):
        return self._elements[element] > 0

    def remove(self, element):
        self._elements[element] -= 1

(Beforehand: I am stripping comments from the code I present in the blog in order to save some space) As you can see, I used pythons defaultdict there. This instance will init uninitialized values in the set with 0 if you access them. Given this, it should be clear how I intend to implement the multiset: I have a mapping from key to amount, with amount being some positive integer. As I run the test, it works as expected (and, oh wonder, the InsertionDeletion-test works, too. ) Happy about that, I tackled the test with the unbalanced removes. In order to do this, I defined the required exception at first:

class MissingElement(Exception):
    def __init__(self, missing_element):
        Exception.__init__(self, "Element  is missing" % missing_element)
        self.missing_element = missing_element

As you can see, a meaningful error message is generated and every data in the error message is available as attributes, so this is a helpful exception. I also did not include the Error-suffix, because I think “except MissingElement, e” reads far nicer than “except MissingElementError, e”. Given this, I could modify the method remove in order to throw this exception when appropiate:

    def remove(self, element):
        if self._elements[element] == 0:
            raise MissingElement(element)
        else:
            self._elements[element] -= 1</pre>

Given this, I had everything working except for the clone-tests. Well, so I sat down and implemented the simplest code possible. It resulted in this:

def clone(self):
    result = Multiset()
    for k, v in self._elements.iteritems():
        for i in range(0, v):
            result.add(k)
    return result

The first thing one might recognize is the potential inefficiency. This is a dilemma, currently, because I do not want to access the semi-private attribute _elements of the resulting object, even though it belongs to the same class. I figured: For this bombchain-solver, there would be at most 10 bombs in the toolbox (because it has 10 fields only) and thus, copying this would be quick enough. If it is too slow eventually, I can implement a more efficient method addMany. A slight tripping moment might be the behaviour of iteration over a defaultdict. A defaultdict iterates over all keys that have been accessed somewhen in the past. This is a bit unobvious, but it is what I need, so I will add a little comment and keep it that way.

Given all of this, we have finished implementing the multiset.

The current git database can be found unter this link: current git repository (Yes, I am still looking for a nicer hoster. That one is annoying).
Thanks for reading, and see you next time,
Tetha.

A few design thoughts

Greetings readers,

today, I will post some design thoughts. I simply felt like drawing some UML-diagrams and think about them for a bit. At first, an activity diagram that closely resembles a level 1 dataflow diagram:

I drew this diagram with dia, because I did not decide to use UML beforehand. I rather wanted to have some diagrams, searched around and ended up with UML-diagrams, because the other diagrams did not express what I wanted.

But back to this diagram. Of course, we can ask ourself about the value of the diagram. I mean, it just shows three bubbles with “Parse problem”, “Solve Problem” and “Output Solution” in them. We knew that earlier, didn’t we? Sure, I sort of knew this earlier, but now, it is written down. The program will accept a single problem (on stdin, as a good little unix program), solve this problem and output the solution (on stdout). Multiple problems can be kept in separate files in a folder and piped into the program using some bash-magic.

This diagram tells us even more: We have three sequential modules and these modules need to exchange data. That is, we need to define a data exchange format between the parser and the solver and a data exchange format between the solver and the result-printer. I am unsure how complex the output-module will be (it might be just a function “print result”), but I certainly do not want to output statistical data or the solution in my solver, because that would result in a mess. Furthermore, I can imagine the need for different output modules. I think it would be a good thing to have — for example — a module which just prints “Problem solved in XX seconds” and a second output modile which prints “Problem solved. Solution found” (opposed to “No solution found in both cases”).

Third, I think it is a good idea to implement the parser and the result printer (or at least, one result printer) before implementing a solver, because once we have a tested parser and a tested printer, we can forget every detail about them. They work. Now we can think about the more complicated solver. The solver can be mocked up as a module that just says “Cannot solve this problem”.

Thus, this very simple diagram taught us a good roadmap how to implement this solver:

• Implement the exchange data structures
• Implement the parser
• Implement a simple result dumper
• Implement a solver

Since I am a bit eager to start cutting some code, I will continue to plan the exchange structures. At first, the (currently) simple result structure:

A class diagram for the result datastructures.

I basically figured the minimum information I need to have a very basic output. The questions I needed to answer are:

• Did I solve the problem?
• What is the solution, if there was one?

These are the two methods in the interface. The interface is then implemented in two state-classes in order to remove some conditionals. It is always nice to remove conditionals if you can without too much trouble.

Of course, I cannot claim to say: This is the finite result structure and it will never ever change. I am pretty sure it will change, because I think I will want to track the time the solver needs, for example. This will require a bit of redesign, but that is no real problem. This is not waterfall.

Third, there is the more complicated exchange structure between the parser and the solver:

A class diagram of the gamestate

Here, I figured again about the basic operations I need in the parser and a solver. The parser needs to add bombs to the toolbox and place bombs on the field. The solver is a backtracking solver, so it needs to be able to preserver the input state and manipulate copies of the input state, it needs to get information about the toolbox and the playing field, it needs to place bombs, it needs to know, if the playing field is in a finished state and it needs to be able to combine bombs. These are the methods in the class gamestate. Since the class gamestate should have a single responsibility, I added two more classes to represent the toolbox and the playing field. I am not too sure if the gamestate decides if it is final or if the playing field decides if it is final. I think however, I will move this into the playing field, because the logic if a field is final does not depend on the toolbox.

A second decision was the addition of the classes Multiset and LimitedMapping. I implemented such classes such as the multiset and the mapping, limited to a certain set of coordinates, pretty often. Granted, only around three times, but on the other hand… THREE TIMES. Thus, I decided to extract the essence out of the classes and have some very abstract (and simple) classes to use here. The first is the multiset and it is very straightforward. Imagine a set that can contain an element more than once and you have a multiset. The second. the limited mapping is a bit more tricky, but it captures the essence of representing all coordinate based levels. It maps coordinates given as indexable objects of keys to values and has a predicate-function for each dimension (every valid index on the coordinate vectors) that must hold. So, if you have a level with cartesian coordinates (x, y) and the x-coordinate goes from 0 to 100 and the y-coordinate goes from 0 to 50, then you have the first predicate function lamda x: 0 <= x <= 100 and the second predicate function lambda y: 0 <= x <= 50. If a coordinate does not fulfill ALL predicates, errors must be raised.

So, this is growing a pretty large post already and I have the thoughts I had written down… Thus: See you next time, readers.

Greetings, Tetha.

Initial Considerations

Greetings, Readers.

Welcome back to the development of a bombchain solver. In the last entry, I introduced you to my idea of a “Let’s develop” and the game Bombchain. In this entry, I will clarify a few things how I currently develop things and the general strategy for the solver I will use.

So, at first, how to develop such things? I for myself cannot claim superiority of my way — I cannot even claim that my way works somehow, but I think thats ok, because it works pretty well for me. I won’t go test driven design crazy or try to analyze things to death until I have a diagram for all ten lines of code. I consider myself somewhere in the middle of that. I tend to plan a reasonable amount until I know the general strategy of the program and a very high level architecture of things. Once I have that, I like to implement things test first, because testing first does make things easier.

So, having that out of the way, we need to consider what strategy to use in this bombchain solver. For such solvers, there are two major ways one can go: by brute force, and by logic.

The logic way generally means: Find deduction rules and apply them until the puzzle is solved or you cannot apply rules anymore. For example, consider Sudokus. In a sudoku, you can formulate the pattern: “Consider a field. If all numbers except a single number occur in the same row, box and column as the considered field, then the considered field must contain the missing number.” Given enough of these rules, it is possible to solve a large amount of sudokus. However, for example solving a Sudoku is an NP-hard problem, so the existance of infinitely many sudokus that cannot be solved with efficient patterns is very probable.

Second, there is the way of brute force. Basically it means: try every possibility at every choice and check if the puzzle is still correct. Once all choices are made and the puzzle is correct, the puzzle is solved. This algorithm is cabable of solving many, many problems, it is just comparably slow. However, for some problems, no faster solution is known. Some Sudokus are such problems, for example.

I for myself dislike the backtracking approach, because it feels cheap. Of course, it is interesting and to a certain degree challenging to make such a backtracking solver fast enough to solve things in less than a day, but it is still kind of cheap. The art of finding new patterns and new approaches to solve things efficiently is much more interesting in comparision. Thus, I will try not to use backtracking, but I am not too sure if that is possible.

This leads me to the misery I stumbled upon when planning this solver and these essays. I basically wanted to build patterns, a nice framework for these patterns and end up with like 10 patterns and say “look, these 10 patterns can solve the 40 levels (minus the bonus levels) of the first bombchain without a problem”. But then, my destructive mind struck again.

Consider this problem:

Given a small x bomb in the toolbox, it is straightforward to derive whre it goes: lower row, middle column. In order to derive that, you could calculate the fields where the small x bomb must be placed in order to make the other bombs explode and intersect these sets of coordinates. In this case, that would give us exactly one coordinate, the lower row, middle column. So far, so good. but what about:

Consider having 2 small plus bombs in your inventory. Now you have a lot of plans that are all equal in this context:

• Place one bomb left, place one right, ignite any
• place one bomb right, place one left, ignite any
• combine the two bombs in your inventory, place the result left and ignite it
• combine the two bombs in your inventory,place the result right and ignite it
• combine one bomb from the inventory with the right bomb on the field, place the other bomb from the inventory next to the left bomb, ignite the large bomb
• combine one bomb from the inventory with the left bomb on the field, place the other bomb from the inventory next to the right bomb, ignite the large bomb.

The problem now is: All of these solutions to this trivial solution requires a lookahead of around 3 – 4 (place this here, place that there and finally ignite this)

A Bombchain Solver: Introduction

Greetings Reader,

I decided to implement a solver for the game “Bombchain”. There are several reasons for this. The most important is that I really like Let’s Plays. a Let’s Play is if someone plays a game, records his playing in some way and displays them on the internet. The most popular choices of media and commentary are screenshots and text and video with subtitles or audio commentary. For example, take a look at www.lparchive.org and for example, view a few Videos of Deceased Crabs excellent playthrough of La Mulana. I for myself will display the code I produce in text form together with considerations and commentary in text form. Also, the sourcecode will be made available as a zipped git archive.

Enough of the introduction, what is Bombchain? Bombchain is a fun flash puzzle game. You can take a look at it yourself at Freegamesnews. The main screen looks like this:

You can see the main playing field on the right side (marked green), the logo of the game on the upper left side and the toolbox on the left side (marked red). On the playing field you see 8 bombs placed and in the toolbox there are two more bombs. The goal is to arrange the bombs from the toolbox in a way so you need to ignite a single bomb only in order to create a chain reaction that destroys all bombs on the playing field.  The bombs ignite other fields in a bomb-specific pattern.

I will now list the bombs, how I call them and their explosion pattern.

Name	Bomb	Explosion Pattern
Small X
Small Plus
Small O
Big X
Big Plus
Omega

If you wonder where the difference between the large plus bomb and the large x bomb is, look at the game. They are red or green, but flash into yellow and back to green or red and black. Also, it is necessary to note that the field the bomb was on is ignited too. It will be important to remember this in order to prevent infinite recursions during simulating the field.

As I mentioned, you are able to place bombs on the field, this is fairly straightforward. If a bomb of a certain type is in the toolbox, you select a field to place to bomb on and after that, the bomb is not in the toolbox anymore, but the bomb is on the field. The field may be empty or it may contain a combineable bomb. More on combining the bombs now:

Bombs can be combined according to certain rules:

• Two small X bombs turn into a large X bomb.
• Two small Plus bombs turn into a large Plus bomb.
• A small X bomb and a small Plus bomb turn into an O bomb.
• A large X-bomb and a large Plus bomb turn into an omega bomb.
• An O bomb and an O bomb turn into an omega bomb.

Also, it is necessary to mention that I am only concerned about the actual puzzle levels of bomb chain. Bomb chain also contains bomnus levels where you need to cover a certain area with as little bombs as possible. I won’t try to solve these levels here.

So, this is bombchain. I hope to see you next time, readers, when I post some technical considerations.

Thanks for reading, Tetha.