Preparation: Crossword Creator in Python

I finally have found a programming problem again that kept me occupied for more than a day simply because I could not do it. But let’s start from the beginning. I wrote a “Search the Words”-Game recently (like this one here) and it worked pretty well actually. There were some limitations to it, but it gave me a good result 9 times out of 10 (I may even post the code for it).

I then figured: “Hey actually, the code I used in this program, I can easily adapt to write a CrossWord Creator!” I have tried this and I unfortunately got nowhere 😦 The main problem here is, that I used a fairly brute force approach in my “Search the Words”-script. In a crossword, there are many more constraints which leads to many, many dead ends. Thus either, the code does not yield a satisfactory result or it takes up all memory for a very long… and in the end does not yield a satisfactory result 😉 The problem here was twofold. My code was not optimized for speed (many unnecessary loops) and in most cases it was leading towards a dead end.

With this in mind, I looked a little bit into constraint logic programming, the branch that deals with these problems. Actually, crosswords are some of the more widely used constraint logic problems (alongside Sudoku and probably other Puzzles). I found a Python implementation by Bryan Helmig, as well, but I wanted to do it myself, so I only read through his approach and not his code.

I will now for myself, outline the approach I will try and possible implementations. If you, the reader, have anything to add, please feel free to chime in. Every constructive input is welcome. The only thing you need to remember is, that this is a hobby of mine and I have never ever formally studied computing science or software engineering, therefore sentence like “Just use xyz algorithm to implement concept abc…” do unfortunately not help me in the slightest 😉

So here is my analysis. The problem can be easily broken down into several steps.

  1. Order the list of words to be used in a useful way
  2. Place the words in a grid according to specific rules
  3. Check the quality of the crossword (if it yielded a useful result)
  4. Remember the result and repeat the first 3 steps X times to yield the best possible result.

This is a very general approach, but I will try to move within these confines and sum up my thoughts on each. How to optimise each section and get a meaningful result.

General Definition of Constraints

Before I even discuss the steps, it is first important to assess the constraints that we have for this problem. To this end, I will use the crosswords, that are common in German newspapers. I know there are international differences, but these are the ones I grew up with so I will use those.

  1. Except the first word, each successive word must be placed with one or more letter overlaps with another word already placed on the grid.
  2. Apart from at the overlaps, letters are not allowed to be in parallel cells of the grid (unless they are part of the same word).
  3. A word placement may not be longer than the boundaries of the grid.
  4. The two words of an overlap must be at right angles to each other, e.g. the words ‘creator’ and ‘random’ may not both be horizontal, otherwise you will see a grid with something like this CREATORANDOM

These are the constraints that I can think of and that I have to work with. Now onto the discussion of each point.

1. Order the list of words

This step is rather easy. I will actually follow Bryan Helmig’s assumption here that the longer the word, the harder it will be to place it. Therefore, putting the words in a list ordered by length of word could be an option and then placing it accordingly. If a word cannot be placed on the grid, because there is no good overlap, we skip it and try the next. Then we revisit the same word again.

It can also be envisioned to place the words in a dictionary, with the keys being the length of the words and the values a list with all words of each length. If this would give more comprehensive code or a faster lookup will have to be tested. In this case, it is foreseeable that we can have more variation, simply by being able to choose at random from a list of words of equal length. Something that may not be as easy when working with an order list.

2. Place the words in the grid according to specific rules

This algorithm will be the most crucial part and the one that will need most optimising. I need to subdivide this section into two parts.

  1. The search for a suitable space
  2. The actual placement of the word

The search for a suitable place

I have been pondering about this step for quite some time. Before, I was just brute-forcing it by going through the list of letters already placed and finding a match with a letter in the word to be placed. Unfortunately, this would always lead to the same options tested first and thus can lead into the same dead end over and over again. Additionally, you would always start at the beginning and go through all the letters. Again and again. That is not very efficient and will lead to long waiting times in calculations.

I came up with an idea that I will try for this approach. When placing a word, I will save the coordinates of each letter in a grid in a hash (python dictionary), so that it will look something like this at some point:


letter_coords = {
'a': [(1,0), (3,6)],
't': [(9,0), (1,4), (5,7)],
...
}

This format will avoid that we have to go through all letters in the grid again and again and again. When we want to place a word, we just look for the letters in the word and check the coordinates given from this dictionary. The speed advantage will most likely allow us, to go through all possible positions, to find the “best” position to place the word (what the best is, we need to discuss in the next section).

Addendum:

An addition to this format is to also note down in which direction they still free to (left to right or top to bottom). Secondly, once both direction are used up for a letter, it can be removed from the list.

The actual placement of the word

I have just discussed how to find in a quick manner possible positions of overlap. The actual placement of the word requires also a little thinking. In a random placement, you can imagine that it will be easy at first, but towards the end, you will run out of suitable options very quickly. Therefore, I need to think of a smart way of placing the words.

The first thought that came to my mind is to give a score for each placement according to several factors. Here are my current thoughts:

  • Start at 1
  • multiply with 0 (to get 0) when an undesirable situation is found
    • letter is parallel to a letter not belonging to the same word
    • word is too long
  • If score is ever 0, discard and go to next
  • depending on how much “space” (free cells) around the letters add a score
    • One free cell on either side +1
    • two on one side, one on the other + 2 etc.
    • +X for each additional overlap
  • Choose the word with the highest score, if more than one, choose at random.

Based on this, I should get a reasonably good placement of the word and generally good variability based on the first two major steps.

3. Check the ‘quality’ of the crossword

Here, I will try to recycle an idea from before. I will try to assign a score to each crossword. The best factor here would be overlaps. Another one would be how many of the words were placed. That is right. Maybe there is a word that just cannot be placed. So rather than aborting the entire mission, give the crossword with all the words that were possible to be placed. The more words in, the better, of course. The score needs to be carefully designed, however, so that there is no chance that fewer words with more overlaps is worth more than all words placed with minimum overlaps.

4. Repeat and choose the “best” crossword

This step is self-explanatory. Based on the score of the previous step, you choose after x repeats, the best crossword.

So, based on the above waffling, I will try to write this crossword generator script. If I manage it and it looks good, I will share the code on here. If you have any additions or improvements. Feel free to mention them here, as well :).

Advertisements

Create a simple game menu with pygame pt. 3 – Recognising the keyboard

Please note that I used python 2.7 for this tutorial. If you are using python3.x, this code may not work. There have been many changes that do not allow backwards compatibility. If you run into problems, these websites could be useful: http://docs.python.org/3/whatsnew/3.0.html ; http://www.python.org/dev/peps/pep-3113/ ; https://wiki.python.org/moin/Python2orPython3

Hello and welcome back for the third part of my little mini tutorial series where I first teach myself how to write a game menu with pygame and then live to tell the tale in little articles such as this one 😛 . Last time we looked at the mouse and how to recognise when the cursor hovers over one of our menu items. We then implemented an effect that showed us what the cursor is currently recognising.

If you are just interested in the full code after this tutorial, then follow this link.

This time round, we shall do such a navigation also for the keyboard. Again, like last time, I took the time to compartmentalise some code into methods to make it all more readable, such as the introduction of a MenuItem method called is_mouse_selection() or GameMenu‘s set_mouse_selection() method. In both cases, the code did not change, all we did was tidy up a little.

Here’s the code and try to find the sections in the code that you have so far that correspond to these snippets.

In MenuItem:

    def is_mouse_selection(self, (posx, posy)):
        if (posx >= self.pos_x and posx <= self.pos_x + self.width) and \
            (posy >= self.pos_y and posy <= self.pos_y + self.height):
                return True
        return False

In GameMenu:

    def set_mouse_selection(self, item, mpos):
        """Marks the MenuItem the mouse cursor hovers on."""
        if item.is_mouse_selection(mpos):
            item.set_font_color(RED)
            item.set_italic(True)
        else:
            item.set_font_color(WHITE)
            item.set_italic(False)

But let’s delve into this section properly. One of the first things, I thought about was trying to solve the riddle of what to do when the mouse cursor hovers over one menu item, while the user tries to navigate with the keyboard. Obviously, he doesn’t want to constantly return to the mouse selection. Thus, we need to recognise that a keyboard key was used and when that is the case we make sure the mouse stops working and disappears from sight.
So first, we make sure that the keyboard keys are recognised by adding the following line to the event loop.

                if event.type == pygame.KEYDOWN:

Let’s first make the mouse cursor disappear on usage of the keyboard. For this purpose we shall introduce a new variable to the GameMenu init, self.mouse_is_visible and place it in the if clause above, and then create a method that regularly checks if the mouse should be visible or not.

    def set_mouse_visibility(self):
        if self.mouse_is_visible:
            pygame.mouse.set_visible(True)
        else:
            pygame.mouse.set_visible(False)

Then call this method inside the mainloop after the pygame.event loop but before self.screen.fill(self.bg_color). Obviously the reason for that is that all graphical operations should come last, but we still want to call this method after modifications made to the variable self.mouse_is_visible.

To prevent the mouse highlighting to interfere with the keyboard, we now only need to do one more thing. We need to use our previously defined variable in order to let the code only run self.set_mouse_selection() if the cursor is visible. Therefore we modify our pre-existing code like so:

            for item in self.items:
                if self.mouse_is_visible:
                    self.set_mouse_selection(item, mpos)
                self.screen.blit(item.label, item.position)

This is all nice and well, the moment we touch a keyboard, our cursor will disappear. It is, however, not much use, if we can’t get it back. I figured, it is best to get it back, when we move the mouse. To recognise this, pygame provides a nice little function called pygame.mouse.get_rel() that gives the relative change of the mouse coordinates since the last check. In this case, we’re not interested in that, only that it “has” moved, not by how much. Therefore, a nice little check just before the call to self.set_mouse_visibility() in the mainloop, will do that trick.

            if pygame.mouse.get_rel() != (0, 0):
                self.mouse_is_visible = True

Ok, now, we press the key on the keyboard and the mouse disappears and once we move the mouse again, it re-appears. Great! Now all that is left for us to do, is get the navigation with the keyboard’s up and down arrow buttons working.
For this purpose, we need to play around with the index of GameMenu‘s self.items index. We’ll now create a new attribute in the GameMenu.__init__, called self.cur_item and set it to None. You will see in a second why None and not 0, for example.

Re-visit now our pygame event loop, in particular the section that recognises the keyboard input and add a call to a new method to it.

                if event.type == pygame.KEYDOWN:
                    self.mouse_is_visible = False
                    self.set_keyboard_selection(event.key)

We shall now use this method to define our keyboard navigation. It is a couple of lines of code, but it is pretty easy. Check out the code, which is a method of the GameMenu class, obviously.

    def set_keyboard_selection(self, key):
        """
        Marks the MenuItem chosen via up and down keys.
        """
        for item in self.items:
            # Return all to neutral
            item.set_italic(False)
            item.set_font_color(WHITE)

        if self.cur_item is None:
            self.cur_item = 0
        else:
            # Find the chosen item
            if key == pygame.K_UP and \
                    self.cur_item > 0:
                self.cur_item -= 1
            elif key == pygame.K_UP and \
                    self.cur_item == 0:
                self.cur_item = len(self.items) - 1
            elif key == pygame.K_DOWN and \
                    self.cur_item < len(self.items) - 1:
                self.cur_item += 1
            elif key == pygame.K_DOWN and \
                    self.cur_item == len(self.items) - 1:
                self.cur_item = 0

        self.items[self.cur_item].set_italic(True)
        self.items[self.cur_item].set_font_color(RED)

Bear with me on this one and I shall go through each section with you.

        if self.cur_item is None:
            self.cur_item = 0

This one is the easy part. Remember, I said, I would explain why I chose None? If self.cur_item is None, I know that we switched from mouse to keyboard. As a consequence, I will start at index 0 and everything is peachy. No confusing mark-up. Once I use the mouse again, I will put self.cur_item back to None, just to have reliable behaviour. It’s not rocket science or particularly clever even, it just helps me keep track.

        else:
            # Find the chosen item
            if key == pygame.K_UP and \
                    self.cur_item > 0:
                self.cur_item -= 1
            elif key == pygame.K_UP and \
                    self.cur_item == 0:
                self.cur_item = len(self.items) - 1
            elif key == pygame.K_DOWN and \
                    self.cur_item < len(self.items) - 1:
                self.cur_item += 1
            elif key == pygame.K_DOWN and \
                    self.cur_item == len(self.items) - 1:
                self.cur_item = 0

This is the largest section, but it really is very easy. Let me write it out in words what happens here:

  • If item not top item in the list and UP is pressed, move selection up one item
  • If item is top item in the list and UP is pressed, select the last item on the list.
  • If item not bottom item in the list and DOWN is pressed, move selection down one item
  • If item is bottom item in the list and DOWN is pressed, select the first item on the list.

Simple, huh?

        self.items[self.cur_item].set_italic(True)
        self.items[self.cur_item].set_font_color(RED)

You have seen something similar before with the mouse selection and again it is to highlight your selection accordingly.

Finally, I have kept the first lines of code for last. That is, because I actually wrote them last ;).

        for item in self.items:
            # Return all to neutral
            item.set_italic(False)
            item.set_font_color(WHITE)

As the comment mentions, here, we are just returning all items to neutral, so that we can mark up the new selection. Nothing much to it, really.

And this is it. We have now a Game Menu in which we can navigate without much problem using either mouse or keyboard. Cool, huh? Next time, we will connect them up to functions that “may” trigger the next step in the game or such as in our case simple print functions. We have managed to do the hard part, the last part is easy in comparison.

I hope you enjoyed it. Till next time! 🙂

————————————————
Here’s the full code after this tutorial

#!/usr/bin/python

import pygame

pygame.init()

WHITE = (255, 255, 255)
RED = (255, 0, 0)
BLACK = (0, 0, 0)

class MenuItem(pygame.font.Font):
    def __init__(self, text, font=None, font_size=30,
                 font_color=WHITE, (pos_x, pos_y)=(0, 0)):
        pygame.font.Font.__init__(self, font, font_size)
        self.text = text
        self.font_size = font_size
        self.font_color = font_color
        self.label = self.render(self.text, 1, self.font_color)
        self.width = self.label.get_rect().width
        self.height = self.label.get_rect().height
        self.dimensions = (self.width, self.height)
        self.pos_x = pos_x
        self.pos_y = pos_y
        self.position = pos_x, pos_y
        self.is_selected = False

    def set_position(self, x, y):
        self.position = (x, y)
        self.pos_x = x
        self.pos_y = y

    def set_font_color(self, rgb_tuple):
        self.font_color = rgb_tuple
        self.label = self.render(self.text, 1, self.font_color)

    def is_mouse_selection(self, (posx, posy)):
        if (posx >= self.pos_x and posx <= self.pos_x + self.width) and \
            (posy >= self.pos_y and posy <= self.pos_y + self.height):
                return True
        return False


class GameMenu():
    def __init__(self, screen, items, bg_color=BLACK, font=None, font_size=30,
                    font_color=WHITE):
        self.screen = screen
        self.scr_width = self.screen.get_rect().width
        self.scr_height = self.screen.get_rect().height

        self.bg_color = bg_color
        self.clock = pygame.time.Clock()

        self.items = []
        for index, item in enumerate(items):
            menu_item = MenuItem(item, font, font_size, font_color)#, '/home/nebelhom/.fonts/SHOWG.TTF')

            # t_h: total height of text block
            t_h = len(items) * menu_item.height
            pos_x = (self.scr_width / 2) - (menu_item.width / 2)
            # This line includes a bug fix by Ariel (Thanks!)
            # Please check the comments section of pt. 2 for an explanation
            pos_y = (self.scr_height / 2) – (t_h / 2) + ((index*2) + index * menu_item.height)

            menu_item.set_position(pos_x, pos_y)
            self.items.append(menu_item)

        self.mouse_is_visible = True
        self.cur_item = None

    def set_mouse_visibility(self):
        if self.mouse_is_visible:
            pygame.mouse.set_visible(True)
        else:
            pygame.mouse.set_visible(False)

    def set_item_selection(self, key):
        """
        Marks the MenuItem chosen via up and down keys.
        """
        for item in self.items:
            # Return all to neutral
            item.set_italic(False)
            item.set_font_color(WHITE)

        if self.cur_item is None:
            self.cur_item = 0
        else:
            # Find the chosen item
            if key == pygame.K_UP and \
                    self.cur_item > 0:
                self.cur_item -= 1
            elif key == pygame.K_UP and \
                    self.cur_item == 0:
                self.cur_item = len(self.items) - 1
            elif key == pygame.K_DOWN and \
                    self.cur_item < len(self.items) - 1:
                self.cur_item += 1
            elif key == pygame.K_DOWN and \
                    self.cur_item == len(self.items) - 1:
                self.cur_item = 0

        self.items[self.cur_item].set_italic(True)
        self.items[self.cur_item].set_font_color(RED)

    def set_mouse_selection(self, item, mpos):
        """Marks the MenuItem the mouse cursor hovers on."""
        if item.is_mouse_selection(mpos):
            item.set_font_color(RED)
            item.set_italic(True)
        else:
            item.set_font_color(WHITE)
            item.set_italic(False)


    def run(self):
        mainloop = True
        while mainloop:
            # Limit frame speed to 50 FPS
            self.clock.tick(50)

            for event in pygame.event.get():
                if event.type == pygame.QUIT:
                    mainloop = False
                if event.type == pygame.KEYDOWN:
                    self.mouse_is_visible = False
                    self.set_item_selection(event.key)

            if pygame.mouse.get_rel() != (0, 0):
                self.mouse_is_visible = True
                self.cur_item = None

            self.set_mouse_visibility()

            # Redraw the background
            self.screen.fill(self.bg_color)

            for item in self.items:
                if self.mouse_is_visible:
                    mpos = pygame.mouse.get_pos()
                    self.set_mouse_selection(item, mpos)
                self.screen.blit(item.label, item.position)

            pygame.display.flip()


if __name__ == "__main__":
    # Creating the screen
    screen = pygame.display.set_mode((640, 480), 0, 32)

    menu_items = ('Start', 'Setting', 'Quit')

    pygame.display.set_caption('Game Menu')
    gm = GameMenu(screen, menu_items)
    gm.run()

Using Gstreamer with Python2.6 in Windows XP – Pt. 1 Introduction and Installation

(Original post from 31.10.2011)

The three reasons why I feel it useful to compile my experiences with GStreamer under Windows XP, although I am not a good programmer, are as follows.

  1. There isn’t much information on how to effectively install GStreamer bindings with Python2.6 and I ran into some wonderfully confusing problems
  2. All the examples I found, were written for Linux. This caused me some problems for example in terms of knowing which “sink” to use (we’ll get to that I am sure) as they are very different from Linux to Windows
  3. The majority of examples use “pygtk” as the library to make the GUI. While I have nothing against Pygtk, I am used to wxpython in particular, and I would like to have examples without any GUI in general. Kind of a minimal example.

I will try and link to tutorials and information as I go along and quote their code, just in case, the site gets taken down sometime or something like that. The reason, I want to use GStreamer is because I want to write an audio tool for my roleplaying group that can play several audio files at the same time (mp3, ogg or wav) while being cross platform (Windows and Linux, but mostly Windows). As mentioned, the examples in Linux were plenty, Windows less so. I wrote one of those before, so all the functionality around it is already present, but the library didn’t quite cut it for me. There were irresolvable issues with it.

Installation
Let’s start with the installation, which has been quite the charmer for me. NOTE: This for an installation of Gstreamer with bindings to Python2.6.

I tried it with cygwin, as well, because I had so many problems with the “standard” way, but that just led to even more frustration. Mostly because I do not know how to use cygwin properly, I am sure.

Anyhow, go to the following website:

http://code.google.com/p/ossbuild/

and download and install “GStreamer-WinBuilds-GPL-x86.msi” & “GStreamer-WinBuilds-SDK-GPL-x86.msi”

Good, now comes the part that took me the best part of two days to figure out. The SDK installation does not install the bindings directly into your Python installation. I had to do that manually.
I went to:

..\OSSBuild\GStreamer\v0.10.6\sdk\bindings\python\v2.6\lib\site-packages

In your Gstreamer installation and copied and pasted the contents into the following folder in my Python2.6 installation

..\Python26\Lib\site-packages

If you would start an interpreter now, you could import pygst no problem, BUT (there is always a but) not the module “gst”. This was rather vexing. I finally, after about two days of feeling like an idiot, looked at the contents I copied and pasted. There you find a folder named “gst-0.10” and inside that folder was a folder called “gst”. By moving that folder directly into site-packages, I was finally able to import gst in my python interpreter.

There you go, you can now use Gstreamer together with Python2.6.

Python: Unzipping the zip

(Original post from 25. March 2012)

I just came across a great little feature of python that I thought I might want to share with my non-existent fan base (and with myself).

While writing on my eternal project of a good role-playing music player, I came across a situation where I had to handle lists of tuples with two values. Often times, I found myself need to pass a list of just one part of that tuple to a function or some such thing and I was hunting high and low for a way to do it until a thought struck me.

One way to make these lists in python is to “zip” two lists together. Is there a way to “unzip”, i.e. the reverse of zip, such a list? turns out there is, but to me it is a bit a weird.

Here is an example:

>>> li = [(1, "one"), (2, "two"), (3, "three"), (4, "four")]
>>> zip(*li)
[(1, 2, 3, 4), ('one', 'two', 'three', 'four')]

As you can see, the two original lists are re-established. As long as the tuples have the same length, you can do this with as many items in a tuple as you want. I found this very useful and I found myself over using it a little bit.

First post!

Ah yes! The daunting first post of a blog. I created this blog in order to better arrange my blogging life. I already have another blog, but noticed that the posts regarding programming do not fit the general topic of the blog any more. As such, I will migrate all my programming-related posts from there over to this lovely blog, to have it all in one place. I chose wordpress.com, because their syntax highlighting is easy to use and integrated. Exactly what I need.

It also means that, of course, the frequency of new entries will be reduced across the board, but I am not in this game for quantity. I do it out of enjoyment and if I just don’t feel that at the time, well tough. No blog entry 😉 Expect a rather high rate of publishing at the beginning (because of copy and paste). I will mark the old posts at the top with their real first publishing date for chronological reasons.

Apart from that, all I can say is: “Let’s hope this is useful and you enjoy reading it.”