Since Wordle took the world by storm, a large number of innovative clones have emerged, one which I was pointed to recently is Tuble, where the aim is to guess the correct Tube Station in as few attempts as possible.

Once the initial fun dies down, I’ve quite enjoyed looking at these games as analytical puzzles, and finding an algorithm to solve them.

The Problem

As you make guesses, the game returns two data points to help you refine the next guess. The colour of the blob tells you how many zones are between the guess and the answer, and the number is how many station stops it would take to get there.

The Tube map is pretty well known, especially for Londoners, and the game only includes the core tube (no DLR, no TFL Rail, and also no Crossrail). Turning the map into data is a graph problem, and the biggest hurdle is turning the picture above into a collection of node and edge data.

The solution

1. Get the station data into Python
2. Determine the possible answers given guess(es) made
3. Determine the next best guess

1. Getting the data into Python

A quick google pointed me to this blog post (thanks Mark Dunne!), Mark had already found this github repo (thanks Nicola!) which had pre-built csvs with the info needed to build a networkx graph representation of the tube.

connections = pd.read_csv('london.connections.csv')

#filter out DLR
connections=connections[connections['line']!=13] 
connections=connections[connections['line']!=5]

station1=connections["station1"]
station2=connections["station2"]
stationMasterList=list(set(pd.concat([station1, station2]).to_list()))

stations=stations[stations.index.isin(stationMasterList)]

This first step removes the DLR and ELL stations (which aren’t in the game)

Then I’ve shamelessly copy-pasted this code from Mark’s notebook

graph = nx.Graph()

for connection_id, connection in connections.iterrows():
    station1_name = stations.loc[connection['station1']]['name']
    station2_name = stations.loc[connection['station2']]['name']
    graph.add_edge(station1_name, station2_name, time = connection['time'])
    
#add the connection between Bank and Monument manually
graph.add_edge('Bank', 'Monument', time = 1)

I’ve now got a graph with all my stations (nodes) and lines (edges).

2. Determine the possible answers given a guess

I’m not sure if there’s a more efficient way to do this, but the first iteration is just a loop through all the stations in the graph, and adding them to a list if they meet the conditions of the last guess.

def getPossiblesList(startStation, maxDistance, zoneFlag): #zoneFlag takes values as: green=0, yellow=1, orange=2, red=3
    startZone=stations[stations["name"]==startStation]["zone"].item()
    returnList=[]
    for id, stat in stations['name'].iteritems():
        if len(nx.shortest_path(graph, startStation, stat))-1 == maxDistance:
            details = stations[stations["name"]==stat][["name", "zone", ]].to_records(index=False)
            name=details[0][0]
            zone=details[0][1]
            if zoneFlag==0:
                if startZone==zone:
                    returnList.append(name)
            if zoneFlag==1:
                if abs(zone-startZone)>=1 and abs(zone-startZone)<2:
                    returnList.append(name)
            if zoneFlag==2:
                if abs(zone-startZone)>=2 and abs(zone-startZone)<3:
                    returnList.append(name)
            if zoneFlag==3:
                if abs(zone-startZone)>=3:
                    returnList.append(name)
    return returnList

My first guess is 16 stops from the correct station, and 1 zone away (plus or minus), given that, here are the possible stations which meet the criteria

['Holloway Road', 'Bethnal Green', 'Finsbury Park', 'Chalk Farm', 'Kentish Town', 'Bermondsey']

This is probably something you could do in your head, and leaves a much reduced number of possible options

3. Determine the next best guess

It will almost always be best to guess one of the stations in the shortlist, but there may be a better guess which limits the possible options more

E.g. if the possible stations are Regent’s Park or Piccadilly Circus, a guess of Oxford Circus wouldn’t help atall. Green Park would be better as you’d know exactly which station was right based on the feedback

However, given there are only 2 options, it would be much more sensible to guess one of those options as you’ve got a 50% chance of ‘getting lucky’.

Gut feel is that there could be an edge case where guessing from the shortlist would risk you getting less information than a non-shortlist station, in which case you’d be gambling a possible win on the next turn, vs a definite win on a subsequent turn.

def tubleResult(startStation, endStation):
    path=len(nx.shortest_path(graph, startStation, endStation))-1 #minus one as both stations are included in the result
    startZone=stations[stations["name"]==startStation]["zone"].item()
    endZone=stations[stations["name"]==endStation]["zone"].item()

    if abs(endZone-startZone)<1.0:
        zoneFlag=0
    elif abs(endZone-startZone)>=1 and abs(endZone-startZone)<2:
        zoneFlag=1
    elif abs(endZone-startZone)>=2 and abs(endZone-startZone)<3:
        zoneFlag=2
    elif abs(endZone-startZone)>=3:
        zoneFlag=3
    return(path, zoneFlag) #zoneFlag takes values as: green=0, yellow=1, orange=2, red=3

This code returns the values which the game would give you if you guessed a ‘start station’ and the correct result was ‘end station’. Using this, I can compare the information I’d get from using different guesses and select the one with the least ambiguous outcome.

fullList=[] #a full list of the stations, for the case where there are no previous guesses
for id, stat in stations['name'].iteritems():
    fullList.append(stat)

guesslist=[]
guesslist.append(('Ealing Broadway', 16, 1)) #Station name, number of stops away, encoded colour of the tile

returnLists=[] #store all the possible answers, based on guesses
for guess in guesslist:
    returnLists.append(getPossiblesList(guess[0], guess[1], guess[2]))

remainderList=[] #this will store a unique/deduped list of stations
if len(returnLists)==0:
    remainderList=list(set(fullList)) #clumsy dedup
else:
    remainderList=list(set.intersection(*[set(list) for list in returnLists])) #funky bit of code which I hope gives me the intersection of all results
    print(remainderList)

In the absence of a proper UI, the user adds more lines to the ‘guessList’, and the code runs from that.

if len(remainderList)==1:
    print ("The answer is "+remainderList[0])
if len(remainderList)==2:
    print ("The answer is either "+remainderList[0] +" or "+remainderList[1])
else:
    #Remainder List Loop
    bestDiff=1000
    bestStation=""
    for guessStat in remainderList:
        outcomes=[]
        for remainderStat in remainderList:
            outcomes.append(tubleResult(guessStat, remainderStat))
        numOutcomes=len(outcomes)

        numUniqueOutcomes=len(set(outcomes))
        diff=numOutcomes-numUniqueOutcomes
        if diff<bestDiff:
            bestDiff=diff
            bestStation=guessStat

    #Full List Loop
    for guessStat in fullList:
        outcomes=[]
        for remainderStat in remainderList:
            outcomes.append(tubleResult(guessStat, remainderStat))
        numOutcomes=len(outcomes)

        numUniqueOutcomes=len(set(outcomes))
        diff=numOutcomes-numUniqueOutcomes
        if diff<bestDiff:
            bestDiff=diff
            bestStation=guessStat

    print('The best guess is ' +bestStation +" with a duplication of "+ str( bestDiff))

This block of code will return one of 3 outcomes, a single result, a pair, or the best guess. I loop the final step first through the remainder list, then through all stations. If no station gives more information than one on the remainder list, I’d rather pick from that list – just in case I get lucky!

The performance

It works!

Half hangman, half mastermind, Wordle is a fun new obsession for half of the internet. Fun as it is to try and remember 5 letter words, what if I got the computer to solve it?

The Problem

You get 6 guesses to find the word of the day. Each guess is assessed and you find out which letters you guessed correctly (i.e. appear in the word) and if any of those are in the right position in the word. It looks like this:

In this example, the first guess is pure chance.

There is one word each day.

The Solution

My first solution will run through 3 steps:
1. Read in a defined wordlist
2. Read in any previous guesses with the results
3. Strip out words from the wordlist based on the guesses
4. Generate a new guess

https://github.com/alexchatwin/wordleSolver

1. Getting a defined wordlist

I don’t think there’s any way to do this without starting with a list of possible words. without this we’re just guessing symbols, and part of the nature of the puzzle is the players knowledge of english words.

I’ve chosen to use https://www-cs-faculty.stanford.edu/~knuth/sgb-words.txt, but I gather the actual seedlist for the Wordle game is available in GitHub

2. Reading in previous guesses

Each guess generates information about the true word.

Grey – the letter is not in the word at all
Yellow – the letter is in the word, but not where the guess has put it
Green – the letter is in the word and is in the right place

There are some subtleties to the yellow and green options – in both cases there is the potential for a letter to appear twice, it’s easy as a novice player to incorrectly assume green means job-done for that letter. Equally yellow is as much about narrowing down valid letters as it is about restricting the possibilities for the square.

3. Strip out words based on the information from the guesses

I’m going to loop through all the remaining words on the wordlist and prune them in one of 3 ways:

1. Remove any word containing any number of grey letters
2. For yellow letters, remove words with that character in that position, and also words where that character isn’t in at least one other position
3. For green letters, remove any words without that letter in that position

By gradually sifting through the words, I end up with a smaller list of possible words which fulfil the ‘rules’ as they evolve.

4. Generate a new guess

I want to use some tactics with each guess, it’s not helpful to have the algorithm only change a single letter at a time, or I’ll run out of guesses. The game also requires each guess to be a real word.

‘Splittiness’

I’m going to use an approach similar to a decision tree for v1. I’ll start by working out how many words each letter appears in, and then what fraction of the total words that represents:

Here S & E are the ‘winners’ – they’re each present in almost half of the words in the list. This is useful because guessing a first word with them will allow me to split the wordlist most evenly and remove/include a large number of possible words, reducing my search space considerably.

For later versions, I want to look at the overlap between them, e.g. if most words containing S also contain E, it might be that the first guess is better to skip E, and try the next letter down.

The best starting word, the word which will give me the best split between words I should include and remove contains S,E,A,R,O

Anagramming

SEARO is, unfortunately not a word, so the next step is to try the different permutations of the letters until I get something which is (more-so, something which is a word on my wordlist – so it’s still a viable guess).

First guess is easy enough, a simple iteration through the permutations of the letters comes up with – AROSE. I can use all the letters in a viable word, but I need a strategy to ensure I don’t get stuck further down the line. Even one letter down, EAROI doesn’t yield a valid 5 letter English word.

My solution is to add another level to my anagram solver, My preference is to have the 5 most splitty letters, but I’d take 1,2,3,4,6 if they didn’t work, and 1,2,3,4,7 after that. I now have a way to ensure that I’ll be able to sweep the full range of available letters, hoping I’m stepping ever nearer the right answer.

Rinse and repeat

Putting AROSE into the puzzle gives me

And then I repeat the process, putting in the results and asking for the next best word to try, until the board looks like this:

There’s a tangible sense of the algorithm building on what it learns each round.. but also a tedious inevitability that it will reach a valid answer at the end.

I suppose part of the challenge of wordle is the need for a human to remember all the possible words and to make efficient choices. This bit of coding has helped me understand the puzzle at a lower level.

Update – 21/1/22

Wordle 216 6/6

⬜?⬜⬜⬜
⬜?⬜?⬜
???⬜⬜
⬜??⬜?
⬜????
?????

Today’s word was solved, but I learned 2 things:
1. My algorithm will happily guess double letters which it has no evidence exist in the word – I think this is sub-optimal
2. If you guess the same letter twice, and it’s in the word once, you’ll get two yellow blocks if they’re in the wrong places, but a green and a grey (not yellow) if one of them is correct

Updates to follow!

In Part 1 I put together a short python script to automate the stitching together of 16 pictures into a single composite. Now I want to take some of the effort out of selecting the 16 pictures, in order to speed up the process

Each month my wife and I choose 16 of the best pictures involving our son from the hundreds we’ve taken. These end up on our fridge in a 4×4 grid. Although we take a picture of the pictures on the fridge, it always looks a bit screwed up and it’s nice to have a good version stitched together on the computer.

How can I minimise the effort needed to recreate a physical collage from a photo?

The problem

The problem looks a bit like this:

As part of the selection, we have up to 100 printed out into actual photos, so we can isolate the image files for those, but the refinement to the final 16 is done by hand.

1. Read in the individual images, and a picture of the ‘raw’ composite from the fridge
2. Break the raw composite down into 16 tiles
3. Check each of the individual images against the tiles
4. Present the user with the original tile and an ordered list of the ‘candidate’ images which are the best match
5. Loop for all 16, then stitch the final image together

1. Read in the images

I’m going to use a combination of OpenCV and Pillow for my image processing, the first step will be in OpenCV so I’ll read the files in like that.

I’ve created some objects to hold the data around each image – my foray into C# a few years ago got me thinking in Objects, and although I’m not sure it’s Pythonic (dahling), it helps me order my thoughts, and write more debuggable code

class Composite:
    imageName: str
    rawImage: Image.Image
    pilOutputImage: Image.Image
    outputImageArr: list
    tiles: list
    candidates: list
    readyToProcess: bool
    done: bool
    imageXSize: int
    imageYSize: int
    date: datetime
    
    
    def __init__(self, _imageName, _rawImage, _imageX _imageYSize):
        self.imageName=_imageName
        self.rawImage=_rawImage
        self.tiles=[]
        self.candidates=[]
        self.outputImageArr=[]
        self.readyToProcess=False
        self.done=False
        self.imageX=_imageX        
        self.imageYSize=_imageYSize
        self.pilOutputImage = Image.new('RGB', (_imageX4, _imageYSize*4),(255,255,255))
        self.date=datetime.datetime.strptime(_imageName.split(".")[0],'%b%y')
        
        
    def incompleteTiles(self):
        return [t for t in self.tiles if t.done==False]

    def pilImage(self):
        return Image.fromarray(self.rawImage[:,:,::-1].astype('uint8'))
    
    def buildImg(self):
        for tile in self.outputImageArr:
            Image.Image.paste(self.pilOutputImage, tile.pilImage(), (self.imageXtile.xPos, self.imageYSize*tile.yPos))
            
    def addCompleteTile(self, tile):
        self.outputImageArr.append(tile)
        Image.Image.paste(self.pilOutputImage, tile.pilImage(), (self.imageXtile.xPos, self.imageYSize*tile.yPos))

This is an example of the ‘Composite’ object – there will be one of these for each of my Raw Composite files (the fridge images). This holds the rest of the information relating to the Tiles (the 16 sub images) and the Candidate images. It also has the logic to build the final output image.

class Tile:
    xPos: int 
    yPos: int
    rawImage: Image.Image
    candidates: list
    done: bool
    
    def __init__(self, _x, _y, _rawImage):
        self.xPos=_x
        self.yPos=_y
        self.rawImage=_rawImage
        self.candidates=[]
        self.done=False
    
    def pilImage(self):
        return Image.fromarray(self.rawImage[:,:,::-1].astype('uint8'))

This is a Tile. It knows what it looks like in a raw form, it’s position on the 4×4 grid, and the candidate images which could be it

class Img:
    imageName: str
    rawImage: Image.Image
    error: float
    exifDT: datetime
    
    def __init__(self, _imageName, _rawImage, _dt):
        self.imageName=_imageName
        self.rawImage=_rawImage
        self.exifDT = _dt
        
    def pilImage(self):
        return Image.fromarray(self.rawImage[:,:,::-1].astype('uint8'))

Finally this is an image, I use it to keep some of the important info relating to the image in a single place. It’s got the concept of ‘Error’ in there, which will come from the matching code – the lowest error is our best candidate

This is my rough data structure, now I need to populate it

def loadImages(dir, size, type):
    compositeDir="C:/Users/alexc/Source/Repos/picStitcher/photos/"+dir+"/"
    returnList=[]
    for image_file in os.listdir(compositeDir):
        image = cv2.imread(compositeDir+image_file)
        img = Image.open(compositeDir+image_file)
        try:
            dt=img.getexif()[36867]
            dt=datetime.strptime(dt, '%Y:%m:%d %H:%M:%S')
        except:
            dt=datetime(1900, 1, 1, 00, 00)
        if type=="Composite":
            outObj=Composite(image_file, cv2.resize(image, (size[0]*4, size[1]*4), interpolation = cv2.INTER_AREA), size[0], size[1])
        elif type=="Img":
            outObj=Img(image_file, cv2.resize(image, size, interpolation = cv2.INTER_AREA), dt )

        returnList.append(outObj)
  
    return returnList

This function loads raw images (in OpenCV format – a numpy array) and creates an appropriate object to hold them. Theres some extra data (like date, and image size) which is useful later on.

2. Breaking out the tiles

This is a bit of a fudge. Because the pictures taken from the fridge are imperfect, it’s difficult to cut out the exact image, but the hope is that the matching process will work ok with a rough target.

def detile(name, image, imageXSize, imageYSize):
    outArr=[]
    for x in range(0,4):
        for y in range(0,4):
            im=image[y*imageYSize:(y+1)*imageYSize,x*imageXSize:(x+1)*imageXSize]
            outObj=Tile(x, y, im)
            outArr.append(outObj)
    
    return outArr

So I just loop through a 4×4 grid, cut each image and make a new tile out of it. Once that’s done, it gets added to the Tiles list in the Composite object

3. Checking for matches

Let’s assume I have 100 candidate images for my 16 tiles. That’s 1,600 checks which need to be done, and that’s going to take some time. This seemed like a good excuse to have a play with Threading in python

I’ve tried threading before in C#, and it felt messy. I’ve never really had proper training, so I just google my way through it, and I wasn’t ready to handle the idea that information would be processed outside of the main thread of my program. It was really useful (e.g. for not having the UI lock-up when heavy processing was happening), but I didn’t properly understand the way I was supposed to handle communication between the threads, or how to ‘safely’ access common sources of info.

This time, things are a bit simpler (and I’ve been thinking about it for a few more years).

I need my threads to work on the checking algorithm

    def wrapper_func(tileQueue, rawImages):
        print("thread")
        while True:
            try:
                tile = tileQueue.get(False)
                for image in rawImages:
                    result = cv2.matchTemplate(tile.rawImage, image.rawImage, cv2.TM_SQDIFF_NORMED )
                    mn,mx,mnLoc,mxLoc = cv2.minMaxLoc(result)
                    output=Img(image.imageName,image.rawImage, 0)
                    output.error=mn
                    tile.candidates.append(output)
                tileQueue.task_done()
            except queue.Empty:
                pass

Here I have a queue of tiles, and my raw images. Each tile needs to be checked against all the images, but there’s no reason why they can’t be checked independently of each other. This ‘wrapper function’ – which still uses the function name from a StackOverflow answer I cribbed (this one, I think) – is run in 8 different threads, and checks each tile against all the raw images, appending a candidate to the tile each time.

I’m pretty sure this qualifies as thread-safe. The append operation just adds new stuff in, and I’m not reading from anywhere in the list.

    def check_matches(composite, rawImages):
        print("check_matches.. may take a while")
        tileQueue=queue.Queue()
        
        for tile in composite.tiles:
            tileQueue.put(tile)
        for _ in range(8):        
            threading.Thread(target=wrapper_func, args=(tileQueue, rawImages)).start()
        
        tileQueue.join() #wait until the whole queue is processed
        for tile in composite.tiles:
            tile.candidates.sort(key=lambda x:x.error)  #sort the candidates by error (the error of the match)
            
        composite.readyToProcess=True
        print(composite.imageName+" ready to process")

Stepping out a layer, this processes an entire composite. First splitting into a queue of tiles, then fire this into 8 threads. Once the queue is processed, sort the candidates, then set a ‘ready to process’ flag for the UI to respond to.

    def loop_composites(): 
        thread.join()
        print("looping composites")
        global readyState, rawComposites, rawImages
        for composite in rawComposites:
            print(composite.date)
            compMinDT = composite.date-timedelta(days=30)
            compMaxDT = composite.date+timedelta(days=30)
            rawImagesFiltered=[i for i in rawImages if (i.exifDT>=compMinDT and i.exifDT<=compMaxDT) or i.exifDT==datetime.datetime(1900, 1, 1, 00, 00)]
            matchThread = threading.Thread(target=check_matches, args=(composite, rawImagesFiltered))
            matchThread.start()
            matchThread.join()

This is the outer layer of the loop. I’ve added in some filtering logic which uses the exif data to say when the photo was taken. All fridge photos are from a 1 month period (aligned to the middle of the month), so I can use the composite date and check for a period either side. This should reduce the processing if I want to run many months at the same time.

4. The UI

I’ve decided that there’s no way this process will work without a human in the loop – the whole point is to have the correct image at the end!

I’m using Flask to serve a simple web front end which will present the user with the images, and allow them to choose the correct one

On the left you can see the original composite image – you can see that the overall images are a bit skewed, and there’s significant light distortion on the left hand of the image

In the middle is the 1st tile cut from the raw composite

Next is the first match candidate (it’s correct! yay!)

Then is a placeholder for the newly constructed image

5. Loop, complete, stitch and save

Clicking ‘correct’ adds the candidate to the output image array, and pastes the image into the right hand ‘progress’ image

And once all the tiles have a match, the image is saved

6. How did we do

The original reason for creating this program, other than the fun of making it, was to reduce the time it took to create the composites. Let’s consider two metrics:

1. How many images did I need to click through to get to the final composite
2. How many times did the program get the right image first time

With around 100 photos per month, I only needed to check 5-6 of them, and worst case I needed 40 clicks for each of the remaining photos. I think that’s pretty good.