I have already owned the original Gamebuino – now named Classic – but I have not skipped the opportunity to upgrade my experience with the new Gamebuino Meta sporting more memory and a color screen!

Here is the box after opening.

 

And the contents of the deluxe package, including a real wood sticker! There is also a pouch (not shown).

 

Here is a closeup of the screen including pixel art created by my kid using the recommended palette.

 

The programming environment is practically the same as for Gamebuino Classic, only with a new board, driver and library. Very quickly I managed to patch together an app that displays a background and a large animated moving sprite – the pony above:

I’m in love with the speed and the color screen. I see so many opportunities. Stay tuned for updates!

Advertisements

In the previous post (size-efficient maze generation) I showed how to write a simple and short, if suboptimal, program generating a maze. Now here’s how to put it to work and create a simple game for BBC micro:bit.

Micro:bit game

Micro maze

The game incorporates:

  • random selection of maze “branching factor”
  • 20×20 maze generation,
  • random placement of the target,
  • controlling the player dot by tilting the device,
  • on completion, display of the time used to solve the maze

The design of the game has been heavily influenced by the limitations of the micro:bit platform. The game does not include any sound effect, since the device has no built-in speaker (though you can add one). The 5×5 screen is extremely limited, at least every pixel has 10 lightness levels, so the walls can be distinguished from the player dot.

Yet what caused me the most headaches was the memory size limit both for the program itself and for the runtime. It turned out that it is extremely easy to add a few lines to a correctly working Micropython program, create a .hex file, download it to micro:bit, only to realize that it would not work. The device would display nothing and the all the info I found on the web was that probably the device ran out of memory while compiling Micropython to byte code. Even if the program run, it might still stop due to a MemoryException when allocating the memory required for the maze.

For example, I could have easily doubled the size of the maze while using the same amount of memory by storing 2 locations (cells) per byte, not one. Sadly, this made the program longer and more complicated, so it never “compiled” successfully. As it is, I keep the maze as one large bytearray where each byte corresponds to one cell. I encode the type of the cell in the lowest 2 bits of a byte. Support of “branching factor” requires that during the generation I know what was the original direction from which a maze location was originally entered. This takes 2 bits more – only for generation. This leaves 4 bits per byte unused.

On other Micropython implementations I used const keyword which saved memory. It seems to be unsupported on the Micropython version on http://python.microbit.org. I noticed that replacing Python “constant” variables by constants did reduce memory usage, however at the cost of reduced readability. I kept the number of named “constant” variables to minimum. I have also kept the Game class even though I felt that replacing it via some global variables would save runtime memory. That would be a bad programming example though.

Now about the game itself. After the start or reset, a number 0-9 is randomly selected and displayed. This is the “branching factor” where 0 has many branches and 9 has more long corridors. The maze is generated for a few seconds while this number is being shown. After it’s completed, the player position is shown as a bright pixels, walls are medium-light pixels, corridors are dark, the target is flashing. If A button is pressed, the minimap is displayed, with just the player (steady dot) and the target (blinking dot). Tilting the device will move the player in the direction of the tilt as long as it does not run into a wall.

And here’s me actually finding the target – yes, the whole search did take 300 seconds including the hidden part.

How to play?

  • copy the code below.
  • paste it into the editor on Python micro:bit website
  • name the program in a window to the right
  • press Download
  • save the .hex file to a directory of your choice
  • connect your micro:bit to your computer
  • drag and drop the .hex file from your computer to micro:bit
  • the code will be flashed
  • the game will start, display a number and after a short while you will be able to play

Enjoy!


# -*- coding: utf-8 -*-

import microbit as m
from random import randrange as rr

WH = 20
SH = 5

def clamp(a, b, c):
    return max(min(c, b), a)

class Game:
    def __init__(self):
        self.world = bytearray(WH * WH)
        self.player = [ 1, 1 ]
        self.pos = [0, 0]

    def getworld(self, x, y):
        return self.world[x + y * WH]

    def setworld(self, x, y, s):
        self.world[x + y * WH] = s

    def world2screen(self, p):
        return [ p[0] - self.pos[0], p[1] - self.pos[1] ]

    def screen2world(self, p):
        return [ p[0] + self.pos[0], p[1] + self.pos[1] ]

    def getscreen(self, x, y):
        p = self.screen2world((x, y))
        if p == self.player:
            return 4
        else:
            return self.getworld(p[0], p[1])

    def trymove1axis(self, p, d, axis):
        q = [ p[0], p[1] ]
        q[axis] += d
        if q[axis] < 0 or q[axis] >= WH:
            return False, p
        if self.getworld(q[0], q[1]) != 0:
            return False, q
        return True, q

    def updatepos(self):
        self.pos[0] = clamp(0, self.player[0] - SH // 2, WH - SH)
        self.pos[1] = clamp(0, self.player[1] - SH // 2, WH - SH)

    def moveplayer(self, dxy, ax):
        for i in range(2):
            if dxy[ax] != 0:
                r, q = self.trymove1axis(self.player, dxy[ax], ax)
                if r:
                    self.player = q
                    self.updatepos()
                    return True
            ax = 1 - ax
        return False        

XX = "2101"
YY = "1210"

CACTGOAL = 3
CAVAIL = 2
CWALL = 1
CEMPTY = 0

def mazesearchactive(g, k):
    for x in range(1, WH - 1):
        for y in range(1, WH - 1):
            if g.getworld(x, y) & 0x03 == CACTGOAL:
                if k == 0:
                    return x, y,
                k -= 1
    return None, None

def mazeupd(g, x, y, active, d):
    p = g.getworld(x, y)
    if p & 0x03 == CACTGOAL:
        g.setworld(x, y, CWALL)
        active -= 1
    elif p == CAVAIL:
        g.setworld(x, y, CACTGOAL + (d << 2))         active += 1          return active      def maze(g, prob_max, prob_t):     active = 0     for x in range(WH):         for y in range(WH):             if x == 0 or y == 0 or x == WH - 1 or y == WH - 1:                 g.setworld(x, y, CWALL)             else:                 g.setworld(x, y, CAVAIL)                      g.setworld(1, 1, CACTGOAL)     active += 1          nx, ny = -1, -1          while active > 0:

        if nx == -1:
            x, y = mazesearchactive(g, rr(active))
        else:
            x, y = nx, ny
            nx, ny = -1, -1

        lastd = g.getworld(x, y) >> 2

        g.setworld(x, y, CEMPTY)
        active -= 1

        for d in range(4):
            nactive = mazeupd(g, x + int(XX[d]) - 1, y + int(YY[d]) - 1, active, d)
            if lastd == d and nactive > active and rr(prob_max) < prob_t:
                nx, ny = x + int(XX[d]) - 1, y + int(YY[d]) - 1
            active = nactive

    g.setworld(x, y, CACTGOAL)
    return x, y

h = rr(10)
m.display.show(str(h))
g = Game()
gx, gy = maze(g, 10, h)

f = 0    

while True:

    if m.button_a.is_pressed():
        m.display.clear()
        m.display.set_pixel(g.player[0] * SH // WH, g.player[1] * SH // WH, 9)
        m.display.set_pixel(gx * SH // WH, gy * SH // WH, 8 * (f % 2))
    else:

        for y in range(SH):
            for x in range(SH):
                v = g.getscreen(x, y)
                if v == CACTGOAL and f % 2 == 1:
                    v = 0
                m.display.set_pixel(x, y, v * 2)

        if abs(g.player[0] - gx) + abs(g.player[1] - gy) <= 1:             break         dx = m.accelerometer.get_x()         dy = m.accelerometer.get_y()         ax = int(abs(dy) > abs(dx))
        dx = clamp(-1, dx // 200, 1)
        dy = clamp(-1, dy // 200, 1)
        if dx != 0 or dy != 0:
            g.moveplayer((dx, dy), ax)

    m.sleep(200)
    f += 1

while True:
    m.sleep(500)
    m.display.scroll("{}s".format(f // 5))

The task for today’s exercise is to build a maze and keep the size of the source code as well as memory under some limits. There is an array “world” of size WW times WH and it needs to be converted into a maze, where some cells are passable and some are walls. The outer rows and columns must become walls and the maze needs to be “perfect” – no loops and all passable cells are reachable. Let’s assume that the start is always in position (1,1) and there is one special cell being the goal.

labexample

In the above example the white square in the left upper corner, (1, 1) is the starting point and (22, 44) in is the light grey goal. Dark grey squares are walls and black cells are passable. Walls surround the maze as required. Some cells that are not empty are not reachable however (very dark grey). As long as there are few such cells a maze is good enough even if not perfect.

Generating a maze is generally not a challenging task. The assumption for today is that we are running the maze generation on a device with limited memory for both the code and the variables. Namely, we can store several bits of information in each maze cell, above that we can only use several simple variables. How does it affect our approach to maze generation algorithm?

These restrictions mean that using recursion or stack based algorithms directly is out of question. One of the possible approaches would be to use a method similar to BFS (Breadth First Search) or DFW (Depth First Search) where the next square to be visited would be randomly selected from the queue or the stack, respectively. The data structure would require some additional memory for storing “active” square coordinates, which does not match our requirements.

The idea is that we can trade time for memory size and simply mark the active squares in the same memory that we are using for storing the maze itself. Randomly selecting the next active cell to be processed requires:

  • keeping track of the count of all active cells, e.g. active
  • select randomly the index k from 0 to active-1 (the next cell to be processed)
  • search through all the possible squares, stopping the search on kth active cell

If there are N cells, this makes the algorithm complexity to be N^2. For example a 5×5 maze with 25 cells would require at worst 25×25 = 625 operations in the worst case. So this method can be used only for rather small mazes, but we are limited by the memory anyway.

This approach leads to mazes with high branching i.e. there are many shorter corridors. If longer straight corridors are desirable, we can incorporate such a feature by storing the direction of the travel in each active cell and adding a probability P that this direction will be continued next time the cell is processed.

Here is an example of the algorithm execution for the simpler version without directionality.

In the example below:

  • W: wall
  • ?: available unprocessed cell
  • A: active cell
  • : empty cell

The initial state; walls surround the available cells.

+---+---+---+---+--
|Y/X| 0 | 1 | 2 |
+---+---+---+---+--
| 0 | W | W | W | W
+---+---+---+---+--
| 1 | W | ? | ? | ?
+---+---+---+---+--
| 2 | W | ? | ? | ?
+---+---+---+---+--
|   | W | ? | ? |

Cell (1, 1) is made active and the active counter is set to 1.

+---+---+---+---+--
|Y/X| 0 | 1 | 2 |
+---+---+---+---+--
| 0 | W | W | W | W
+---+---+---+---+--
| 1 | W | A | ? | ?
+---+---+---+---+--
| 2 | W | ? | ? | ?
+---+---+---+---+--
|   | W | ? | ? |

The index of the active cell to be processed is randomly selected, however there is only 1 at the moment. The algorithm scans the whole table and finds the active cell. The current active cell changes state to empty and squares up, down, right and left are examined. Walls up and left are not changed. Available cells to the right and down become active. Active cell count is updated (2).

+---+---+---+---+--
|Y/X| 0 | 1 | 2 |
+---+---+---+---+--
| 0 | W | W | W | W
+---+---+---+---+--
| 1 | W |   | A | ?
+---+---+---+---+--
| 2 | W | A | ? | ?
+---+---+---+---+--
|   | W | ? | ? |

In the next step the index of the active cell to be processed is randomly selected; for example 2nd: (1, 2). Table is scanned to find that cell. The current active cell changes state to empty and squares up, down, right and left are examined. Wall to the left and empty square up are not changed. Available cells right and down become active. Active cell count is updated (3).

+---+---+---+---+--
|Y/X| 0 | 1 | 2 |
+---+---+---+---+--
| 0 | W | W | W | W
+---+---+---+---+--
| 1 | W |   | A | ?
+---+---+---+---+--
| 2 | W |   | A | ?
+---+---+---+---+--
|   | W | A | ? |

Next cell is randomly selected and found by scanning, e.g. (2, 1). The current active cell changes state to empty and squares up, down, right and left are examined. Neighboring walls and empty squares are unchanged. Available cells to the right becomes active. Neighboring active cell becomes a wall, since it would otherwise link two different empty squares and we do not want loops. Active cell count is updated – it is reduced to 2.

+---+---+---+---+--
|Y/X| 0 | 1 | 2 |
+---+---+---+---+--
| 0 | W | W | W | W
+---+---+---+---+--
| 1 | W |   |   | A
+---+---+---+---+--
| 2 | W |   | W | ?
+---+---+---+---+--
|   | W | A | ? |

This short example showed how this algorithm is able to build paths and walls with minimal additional storage.

Here is the actual Python code, extended with the feature of longer straight corridors.

Values to be stored in the maze cell. Available (unprocessed) and active (on the currently processed list) cells codes can be reused. MASK and SHIFT are used for encoding the codes (lower two bits) and travel direction (higher two bits).

MASK = 0x03
SHIFT = 2

CEMPTY = 0
CAVAIL = 1
CWALL = 2
CACT = 3
CGOAL = 3

Size efficient mapping of the numerical direction code 0…3 to x and y deltas. Deltas are -1, 0 or 1, so it’s necessary to add 1 for encoding and subtract 1 for decoding. For example if the direction d is 1, XX[1] is “1”, 1 – 1 == 0; YY[1] is “2”, 2 -1 == 1; thus the direction vector is (0, 1) i.e. down.

XX = "2101"
YY = "1210"

This is the function that scans the “world” searching for the kth active cell. The variable g is the “world” object that exposes getworld(x, y) and setworld(x, y, state) member functions. This function returns the coordinates of the kth active cell.


def mazesearchactive(g, k):
    for x in range(1, g.WW - 1):
        for y in range(1, g.WH - 1):
            if g.getworld(x, y) & MASK == CACT:
                if k == 0:
                    return x, y,
                k -= 1
    return None, None

Maze update function. g is the “world” object as above, x and y are the coordinates of the cell being updated, active and avail are counts of the active and available cells respectively. Strictly speaking available cells do not need to be counted, unless we want to implement checking if any cells were left unprocessed. So this code can be still simplified if the the target architecture requires it. d is direction (0…3), the index to XX and YY strings.


def mazeupd(g, x, y, active, avail, d):
    p = g.getworld(x, y)
    if p & MASK == CACT:
        g.setworld(x, y, CWALL)
        active -= 1
    elif p == CAVAIL:
        g.setworld(x, y, CACT + (d << SHIFT))
        active += 1
        avail -= 1

    return active, avail

Finally, the maze generating function. g is the “world” object, while prob_t / prob_max is the probability that the direction of the corridor will be extended. The higher this probability, the more straight corridors. Specifying this as a ratio avoids floating point numbers that might not be available on the destination platform. The last square to be emptied is marked as the goal. This tends to be distant from the origin, however if the probability of straight corridors is higher, the last square may turn out to be close and the maze will be easy to solve.


def maze(g, prob_max, prob_t):
    avail = 0
    active = 0
    for x in range(g.WW):
        for y in range(g.WH):
            if x == 0 or y == 0 or x == g.WW - 1 or y == g.WH - 1:
                g.setworld(x, y, CWALL)
            else:
                g.setworld(x, y, CAVAIL)
                avail += 1

    g.setworld(1, 1, CACT)
    active += 1
    avail -= 1

    nx, ny = -1, -1

    while active > 0:

        if nx == -1:
            x, y = mazesearchactive(g, rr(active))
        else:
            x, y = nx, ny
            nx, ny = -1, -1

        lastd = g.getworld(x, y) >> SHIFT

        g.setworld(x, y, CEMPTY)
        active -= 1

        for d in range(4):
            nactive, avail = mazeupd(g, x + int(XX[d]) - 1, y + int(YY[d]) - 1, active, avail, d)
            if lastd == d and nactive > active and rr(prob_max) <span 				data-mce-type="bookmark" 				id="mce_SELREST_start" 				data-mce-style="overflow:hidden;line-height:0" 				style="overflow:hidden;line-height:0" 			></span>< prob_t:
                nx, ny = x + int(XX[d]) - 1, y + int(YY[d]) - 1
            active = nactive

    g.setworld(x, y, CGOAL)
    return x, y

This code was used in a Micropython application and should be easily portable to embedded Lua or C/C++.

And here are mazes generated with various likelihoods of direction reusing. Low values have higher branching, higher tend to have straight long corridors.

0%

lab0

10%

lab10

20%

lab30

30%

lab30

40%

lab40

50%

lab50

60%

lab60

70%

lab70

80%

lab80

90%

lab90

I happen to own two of BBC micro:bit devices. Micro:bit is a small computer with two buttons, 5×5 array of LEDs, some sensors (compass, accelerator), USB port and Bluetooth Low Energy radio capability. Naturally with two micro:bits I wanted to find a fun use for the radio. Here it is – a “Hide and Seek” application written in Micropython.

The basic idea is as follows: when you press a button on a device it becomes the active one, sets the max radio power and sends a message to the other (passive) one.

IMG_4470

Freshly started devices show question marks

If there is no response, the other device is either out of range, or is turned off and the active device shows an X sign.

When the message reaches the passive device, it shows a “target” icon and sends the acknowledgement message back at full power. This is to make sure the active one gets the response. Upon successful read of the acknowledgement, the initiating device reduces the power by one step and sends the message again.

This process can have two outcomes:

  • the acknowledging response is received every time, even for the lowest power setting, which means that the passive device is nearby; in that case a happy face is shown on the active device
  • for some power setting N the response is not received, while there is a response to query sent with power N+1; N + 1 is an estimate of the distance between the devices and is shown on the active device screen as a number between 1 and 7

In both cases the search is stopped. I called this a “single” mode and assigned this to button A on micro:bit.

IMG_4495

After pressing the A button on the pink device, it displays a smiley and the left one – target icon

This approach worked, however constant pressing A button was irritating. I added a continuos mode (auto mode) turned on and off by pressing B. In this mode the device constantly repeats the whole search procedure while displaying the latest result. This proved to be a much more convenient arrangement.

Of course the power needed to communicate is only an approximation of the distance and depends on more things, e.g objects in the way and some random conditions. Therefore the approximate distance can vary a lot between measurements, making for a display that jumps unreliably between high and low values. To overcome this problem I added a simple smoothing filter that averages the measurements in the auto mode.

IMG_4500

Pink micro:bit is put into auto mode and the other device is taken away: approximate distance of 2 is displayed here.

Finally I tested this solution on some little test subjects who actually did like this new game. I hid a micro:bit somewhere and they tried to locate it using the distance information on shown on the other device. Then we switched places and it was my role to search for the micro:bit hidden by the little ones. It was fun.

And here is the source code. You can generate a .hex file here: micro:bit Python editor by pasting the code and clicking Download. Then simply drag the .hex file to the micro:bit connected via USB. Then do the same for the other micro:bit, the code is the same for active and passive devices and you can exchange the roles, although it is recommended that only one is active at a time.

# created by Tomasz Kwiatkowski
import radio
from microbit import *

TIMEOUT = 100
PWRMAX = 7
SLEEP = 100

pwr = PWRMAX
MODE_NONE = 0
MODE_SINGLE = 1
MODE_AUTO = 2

mode = MODE_NONE

sent = -1

radio.on()

display.show("?")

# class to store and display the smoothed power needed to communicate
class Filter:
    def __init__(self):
        self.scale = 100
        self.ratio = 80 # state is 80% old value and 20% new value
        self.acc = (PWRMAX + 1) * self.scale
    def update(self, p):
        self.acc =  ( self.ratio * self.acc +
                      self.scale * p * (self.scale - self.ratio)) // self.scale
        smooth_pwr = self.acc // self.scale
        if smooth_pwr == 0:
            display.show(Image.HAPPY) # close
        elif smooth_pwr >= PWRMAX:
            display.show(Image.NO) # no response
        else:
            display.show(str(smooth_pwr)) # radio power for which comms possible

smooth = Filter()

while True:

    if mode != MODE_NONE:
        t = running_time()
        if sent == -1:
            # set power, send message
            radio.config(power = pwr)
            radio.send("S" + str(pwr))
            sent = t
        else:
            dt = t - sent
            if dt > TIMEOUT:
                # response not received
                if mode == MODE_SINGLE:
                    mode = MODE_NONE
                    if pwr == PWRMAX:
                        display.show(Image.NO)
                    else:
                        display.show(str(pwr + 1))
                else:
                    sent = -1
                    smooth.update(pwr + 1)

                sleep(SLEEP)

                pwr = PWRMAX

        if mode == MODE_AUTO:
            # turn off auto mode on B pressed
            if button_b.was_pressed():
                mode = MODE_NONE
            # blink a pixel in auto mode
            display.set_pixel(0, 0, (t // SLEEP) % 10)

    else: # MODE_NONE
        if button_a.was_pressed():
            mode = MODE_SINGLE
            pwr = PWRMAX
            sent = -1
        elif button_b.was_pressed():
            mode = MODE_AUTO
            pwr = PWRMAX
            sent = -1
            smooth = Filter()

    # process incoming transmissions
    incoming = radio.receive()
    if incoming:
        if incoming[0] == 'S':
            radio.config(power = PWRMAX)
            radio.send("R" + incoming[1])
            if mode == MODE_NONE:
                # only show when in passive mode
                display.show(Image.TARGET)
        elif incoming[0] == 'R' and mode >= 1 and incoming[1] == str(pwr):

            if pwr == 0:
                # received response with low power, other radio is nearby
                if mode == MODE_SINGLE:
                    # in single mode stop the search
                    mode = MODE_NONE
                    display.show(Image.HAPPY)
                else:
                    # in auto mode continue to search
                    smooth.update(pwr)
                    pwr = PWRMAX
                    sent = -1

                sleep(SLEEP)
            else:
                if mode == MODE_SINGLE:
                    # temporarily display power while searching
                    display.show(str(pwr))
                # got response, reduce power and try again
                pwr -= 1
                sent = -1

If you are a fan of football (a.k.a. soccer), you surely know that the draw for the World Cup in Russia is going to take place on December 1st, 2017.

Teams from 5 continental football federations, namely:

  • North America – CONCACAF,
  • South America – CONMEBOL,
  • Europe – UEFA,
  • Africa – CAF,
  • Asia – AFC (which includes Australia)

are split into 4 pots:

POT 1 POT 2 POT 3 POT 3
Russia Spain Denmark Serbia
Germany Peru Iceland Nigeria
Brazil Switzerland Costa Rica Australia
Portugal England Sweden Japan
Argentina Colombia Tunisia Morocco
Belgium Mexico Egypt Panama
Poland Uruguay Senegal Korea Republic
France Croatia Iran Saudi Arabia

According to FIFA: no teams from the same confederation, with the exception of UEFA, which could have up to two teams in the same group, will be drawn into the same group.

It’s worth noting that if we take any team, the probability of other teams being drawn into the same group depends on:

  • confederations to which all four teams belong
  • the order of pots in which the groups are drawn

So you can get different probabilities for group set up if you do the draw in pot 1, 2, 3, 4 order and in pot 4, 3, 2, 1 order for example. I do not know which order FIFA uses on December 1st, I’m assuming here pot 1 .. pot 4 since Russia is assigned group 1 already, so it makes sense to fill the rest of the groups with pot 1 teams.

Also, the draw done by sequential choosing a team randomly does not assign the same probability to each possible team arrangement. It is because during the draw the rules may force some team to be assigned to a particular group. Other choices may result in an invalid arrangement. I did enumerate all valid confederation arrangements and got slightly different results than the simulation.

For the simulation I wrote a short Python program that simulated the draw with all the rules validated. I computed the probabilities by running the draw simulation a hundred thousand times.

Here’s how you would use these tables.

Assume you want to check probabilities for Serbia, which is from Europe and is in pot 4. Find the “Potential groups for a team from Europe in pot 4” table. It turns out that the most probable arrangement for Serbia (28.5%) is to face an European team from pot 1, South American team from pot 2 and and an African team from pot 3. So Poland, Peru, Tunisia or Germany, Colombia, Senegal etc. are just as probable opponents for Serbia. On the other hand teams from South America from pot 1, North America from pot 2 and Asia from pot 3 have only 2% chance to be drawn into Serbia’s group – indeed there are only 2 such groups possible, with Brazil/Argentina,  Mexico, Iran.

I hope you will find it interesting in the last few days before the draw!

Potential groups for a team from Europe in pot 1 Probability
Europe Europe Africa Asia 18.62%
Europe South America Europe Asia 13.47%
Europe South America Europe Africa 9.42%
Europe South America Africa Asia 7.15%
Europe Europe Asia Africa 5.58%
Europe Europe North America Asia 5.13%
Europe Europe Africa North America 4.90%
Europe South America Africa Europe 4.76%
Europe South America Europe North America 3.58%
Europe Europe North America Africa 3.49%
Europe North America Europe Asia 3.30%
Europe Europe Asia North America 2.26%
Europe North America Europe Africa 2.25%
Europe South America North America Asia 2.14%
Europe South America Asia Africa 2.11%
Europe North America Africa Asia 2.08%
Europe South America Africa North America 1.85%
Europe South America Asia Europe 1.72%
Europe South America North America Europe 1.52%
Europe South America North America Africa 1.51%
Europe North America Africa Europe 1.27%
Europe South America Asia North America 0.76%
Europe North America Asia Africa 0.65%
Europe North America Asia Europe 0.47%
Potential groups for a team from Europe in pot 2 Probability
Europe Europe Africa Asia 27.94%
South America Europe Europe Asia 10.51%
Europe Europe Asia Africa 8.37%
Europe Europe North America Asia 7.69%
Europe Europe Africa North America 7.34%
South America Europe Europe Africa 7.25%
South America Europe Africa Asia 5.97%
Europe Europe North America Africa 5.23%
South America Europe Africa Europe 3.89%
Europe Europe Asia North America 3.39%
South America Europe Europe North America 2.73%
South America Europe North America Asia 1.80%
South America Europe Asia Africa 1.70%
South America Europe Africa North America 1.58%
South America Europe Asia Europe 1.40%
South America Europe North America Africa 1.26%
South America Europe North America Europe 1.25%
South America Europe Asia North America 0.68%
Potential groups for a team from Europe in pot 3 Probability
Europe South America Europe Asia 26.95%
Europe South America Europe Africa 18.84%
South America Europe Europe Asia 14.01%
South America Europe Europe Africa 9.67%
Europe South America Europe North America 7.15%
Europe North America Europe Asia 6.60%
Europe North America Europe Africa 4.50%
South America Europe Europe North America 3.64%
South America North America Europe Asia 3.58%
South America North America Europe Africa 2.54%
South America North America Europe Europe 2.52%
Potential groups for a team from Europe in pot 4 Probability
Europe South America Africa Europe 28.55%
South America Europe Africa Europe 15.57%
Europe South America Asia Europe 10.34%
Europe South America North America Europe 9.14%
Europe North America Africa Europe 7.62%
South America North America Europe Europe 7.56%
South America North America Africa Europe 5.71%
South America Europe Asia Europe 5.60%
South America Europe North America Europe 4.98%
Europe North America Asia Europe 2.84%
South America North America Asia Europe 2.08%
Potential groups for a team from South America in pot 1 Probability
South America Europe Europe Asia 21.02%
South America Europe Europe Africa 14.51%
South America Europe Africa Asia 11.94%
South America Europe Africa Europe 7.78%
South America Europe Europe North America 5.45%
South America North America Europe Asia 5.37%
South America North America Europe Africa 3.81%
South America North America Europe Europe 3.78%
South America Europe North America Asia 3.61%
South America Europe Asia Africa 3.41%
South America Europe Africa North America 3.16%
South America North America Africa Europe 2.86%
South America Europe Asia Europe 2.80%
South America Europe North America Africa 2.53%
South America Europe North America Europe 2.49%
South America North America Africa Asia 2.35%
South America Europe Asia North America 1.37%
South America North America Asia Europe 1.04%
South America North America Asia Africa 0.72%
Potential groups for a team from South America in pot 2 Probability
Europe South America Europe Asia 26.95%
Europe South America Europe Africa 18.84%
Europe South America Africa Asia 14.31%
Europe South America Africa Europe 9.52%
Europe South America Europe North America 7.15%
Europe South America North America Asia 4.28%
Europe South America Asia Africa 4.22%
Europe South America Africa North America 3.70%
Europe South America Asia Europe 3.45%
Europe South America North America Europe 3.05%
Europe South America North America Africa 3.02%
Europe South America Asia North America 1.51%
Potential groups for a team from North America in pot 2 Probability
Europe North America Europe Asia 19.80%
Europe North America Europe Africa 13.49%
Europe North America Africa Asia 12.50%
South America North America Europe Asia 10.75%
Europe North America Africa Europe 7.62%
South America North America Europe Africa 7.62%
South America North America Europe Europe 7.56%
South America North America Africa Europe 5.71%
South America North America Africa Asia 4.71%
Europe North America Asia Africa 3.87%
Europe North America Asia Europe 2.84%
South America North America Asia Europe 2.08%
South America North America Asia Africa 1.44%
Potential groups for a team from North America in pot 3 Probability
Europe Europe North America Asia 30.77%
Europe Europe North America Africa 20.93%
Europe South America North America Asia 12.83%
Europe South America North America Europe 9.14%
Europe South America North America Africa 9.07%
South America Europe North America Asia 7.22%
South America Europe North America Africa 5.06%
South America Europe North America Europe 4.98%
Potential groups for a team from North America in pot 4 Probability
Europe Europe Africa North America 29.37%
Europe South America Europe North America 21.45%
Europe Europe Asia North America 13.58%
Europe South America Africa North America 11.11%
South America Europe Europe North America 10.90%
South America Europe Africa North America 6.32%
Europe South America Asia North America 4.54%
South America Europe Asia North America 2.73%
Potential groups for a team from Africa in pot 3 Probability
Europe Europe Africa Asia 37.25%
Europe South America Africa Asia 14.31%
Europe Europe Africa North America 9.79%
Europe South America Africa Europe 9.52%
South America Europe Africa Asia 7.96%
South America Europe Africa Europe 5.19%
Europe North America Africa Asia 4.17%
Europe South America Africa North America 3.70%
Europe North America Africa Europe 2.54%
South America Europe Africa North America 2.11%
South America North America Africa Europe 1.90%
South America North America Africa Asia 1.57%
Potential groups for a team from Africa in pot 4 Probability
Europe South America Europe Africa 28.27%
Europe Europe Asia Africa 16.74%
South America Europe Europe Africa 14.51%
Europe Europe North America Africa 10.46%
Europe North America Europe Africa 6.74%
Europe South America Asia Africa 6.33%
Europe South America North America Africa 4.54%
South America North America Europe Africa 3.81%
South America Europe Asia Africa 3.41%
South America Europe North America Africa 2.53%
Europe North America Asia Africa 1.94%
South America North America Asia Africa 0.72%
Potential groups for a team from Asia in pot 3 Probability
Europe Europe Asia Africa 33.48%
Europe Europe Asia North America 13.58%
Europe South America Asia Africa 12.67%
Europe South America Asia Europe 10.34%
South America Europe Asia Africa 6.82%
South America Europe Asia Europe 5.60%
Europe South America Asia North America 4.54%
Europe North America Asia Africa 3.87%
Europe North America Asia Europe 2.84%
South America Europe Asia North America 2.73%
South America North America Asia Europe 2.08%
South America North America Asia Africa 1.44%
Potential groups for a team from Asia in pot 4 Probability
Europe Europe Africa Asia 27.94%
Europe South America Europe Asia 20.21%
Europe South America Africa Asia 10.73%
South America Europe Europe Asia 10.51%
Europe Europe North America Asia 7.69%
South America Europe Africa Asia 5.97%
Europe North America Europe Asia 4.95%
Europe South America North America Asia 3.21%
Europe North America Africa Asia 3.13%
South America North America Europe Asia 2.69%
South America Europe North America Asia 1.80%
South America North America Africa Asia 1.18%

I learned about New Merology while reading Professor Stewart’s Cabinet of Mathematical Curiosities. The original idea was created by Lee Sallows and I found the original paper here. The updated version is here. I think that either Ian Stewart or Lee Sallows have explained this better than I can, here’s just a short introduction.

So called gematria deals with assigning distinct values to letters thus giving each word a numerical value. Let’s call a number name perfect if the sum of the letter values equals the number. For example (in English):

O + N + E = 1

T + W + O = 2

This is impossible to attain with the typical letter value assignment A=1, B=2, C=3 etc. To overcome this problem Lee Sallows invented New Merology which says that the letter value can be zero or negative, or not necessarily a whole number- although in this case we deal with integers only. Letter values must be still distinct. Lee Sallows starts his exploration of the possible values with O=-2, N=2 and E=1. Then O+N+E equals 1 and if W=-3 and T=7 it necessarily follows that T+W+O=2, making both ONE and TWO perfect numbers. In his paper he finally arrives at the most perfect possible solutions for English and French. This is reportedly verified by a Pascal program.

I have originally written a Python program to generate the Perfect Number Names solutions for Polish and English. It tried to arrive at the dependencies between letters e.g. (in Polish)

D + Z + I + E + S + I + Ę + Ć = 10

D + Z + I + E + W + I + Ę + Ć = 9

(after subtracting both sides)

S – W = 1

so S=W+1, which can lead to further discovered dependencies. But the remaining part of the program was still brute force and made it quite slow. And I was thinking that there must be some better way to solve this since it was just a list of simultaneous Diophantine equations with additional constraints (distinct letter values). I abandoned this puzzle temporarily but kept it in the back on my mind.

Z3

And now Z3Prover enters the stage. It can be used for many things and may be an overkill in this particular case. Still it is very simple to use –  it allows me to provide the equations and constraints and practically instantly receive the information if these are satisfiable or not. Moreover the positive result is accompanied with a model, in this case the mapping of letters to their values!

So here are the inputs:

  1. Equations e.g. Z+E+R+O=0, O+N+E=1 etc. up to MAX_NUM
  2. Distinctness constraints: A!=B, A!=C… B!=C etc. for all A…Z
  3. Minimum: abs(A) <= MIN_VAL for all letters A…Z

The algorithm

Initially I start with only inputs 1 & 2: the list of equations including numerals up to MAX_NUM (usually less than 20) and the distinctness constraints. If these are not satisfiable, I reduce MAX_NUM until I find the list of the numerals that is satisfiable under the constraints. (Bisection would be an improvement here).

Once I establish the largest satisfiable list of perfect number names i.e. know the MAX_NUM, another search is made, this time using all inputs 1 & 2 & 3 and going upward if current MIN_VAL condition makes the constraints unsatisfiable. (MIN_VAL  is the smallest maximum absolute value of all used letters). This search must end since a solution existed in the previous algorithm step. The obvious improvement is again to use the bisection instead of the linear search and is left as an exercise for the reader.

This results in the longest possible list of perfect number names and the smallest maximum absolute value of all letters.

Language competition

Which language among Dutch, English, French, German, Italian, Polish, Portuguese and Spanish has the longest list of perfect number names? Make your guess. The output of my program is provided below with the answer.

Note: I’m treating letters with diacritics/accents as distinct from the base letters which makes sense for Polish. In Lee Sallows’ solution for French he did not distinguish between E in DEUX and É in ZÉRO, I do, even though all the character mapping makes the program harder to follow.

****************************************
DE numerals from 0 up to 16 absolute value within 12
a=11 b=-4 c=-9 d=8 e=10 f=-1 h=5 i=-12 l=2 n=3 ö=7 r=-3 s=0 t=1 u=-7 ü=4 v=9 w=12 z=-8

   n   u   l   l   =   0
  +3  -7  +2  +2   =   0

   e   i   n   s   =   1
 +10 -12  +3  +0   =   1

   z   w   e   i   =   2
  -8 +12 +10 -12   =   2

   d   r   e   i   =   3
  +8  -3 +10 -12   =   3

   v   i   e   r   =   4
  +9 -12 +10  -3   =   4

   f   ü   n   f   =   5
  -1  +4  +3  -1   =   5

   s   e   c   h   s   =   6
  +0 +10  -9  +5  +0   =   6

   s   i   e   b   e   n   =   7
  +0 -12 +10  -4 +10  +3   =   7

   a   c   h   t   =   8
 +11  -9  +5  +1   =   8

   n   e   u   n   =   9
  +3 +10  -7  +3   =   9

   z   e   h   n   =  10
  -8 +10  +5  +3   =  10

   e   l   f   =  11
 +10  +2  -1   =  11

   z   w   ö   l   f   =  12
  -8 +12  +7  +2  -1   =  12

   d   r   e   i   z   e   h   n   =  13
  +8  -3 +10 -12  -8 +10  +5  +3   =  13

   v   i   e   r   z   e   h   n   =  14
  +9 -12 +10  -3  -8 +10  +5  +3   =  14

   f   ü   n   f   z   e   h   n   =  15
  -1  +4  +3  -1  -8 +10  +5  +3   =  15

   s   e   c   h   z   e   h   n   =  16
  +0 +10  -9  +5  -8 +10  +5  +3   =  16

****************************************
NL numerals from 0 up to 13 absolute value within 12
a=4 c=-11 d=-10 e=3 é=1 f=2 g=5 h=7 i=0 j=12 l=6 n=-1 r=10 s=-8 t=8 u=-5 v=-9 w=-12 z=11

   n   u   l   =   0
  -1  -5  +6   =   0

   é   é   n   =   1
  +1  +1  -1   =   1

   t   w   e   e   =   2
  +8 -12  +3  +3   =   2

   d   i   r   e   =   3
 -10  +0 +10  +3   =   3

   v   i   e   r   =   4
  -9  +0  +3 +10   =   4

   v   i   j   f   =   5
  -9  +0 +12  +2   =   5

   z   e   s   =   6
 +11  +3  -8   =   6

   z   e   v   e   n   =   7
 +11  +3  -9  +3  -1   =   7

   a   c   h   t   =   8
  +4 -11  +7  +8   =   8

   n   e   g   e   n   =   9
  -1  +3  +5  +3  -1   =   9

   t   i   e   n   =  10
  +8  +0  +3  -1   =  10

   e   l   f   =  11
  +3  +6  +2   =  11

   t   w   a   a   l   f   =  12
  +8 -12  +4  +4  +6  +2   =  12

   d   e   r   t   i   e   n   =  13
 -10  +3 +10  +8  +0  +3  -1   =  13

****************************************
PT numerals from 0 up to 11 absolute value within 20
a=-11 c=9 d=-4 e=-6 ê=3 i=-10 m=-3 n=-8 o=5 q=17 r=-19 s=11 t=8 u=4 v=18 z=20

   z   e   r   o   =   0
 +20  -6 -19  +5   =   0

   u   m   =   1
  +4  -3   =   1

   d   o   i   s   =   2
  -4  +5 -10 +11   =   2

   t   r   ê   s   =   3
  +8 -19  +3 +11   =   3

   q   u   a   t   r   o   =   4
 +17  +4 -11  +8 -19  +5   =   4

   c   i   n   c   o   =   5
  +9 -10  -8  +9  +5   =   5

   s   e   i   s   =   6
 +11  -6 -10 +11   =   6

   s   e   t   e   =   7
 +11  -6  +8  -6   =   7

   o   i   t   o   =   8
  +5 -10  +8  +5   =   8

   n   o   v   e   =   9
  -8  +5 +18  -6   =   9

   d   e   z   =  10
  -4  -6 +20   =  10

   o   n   z   e   =  11
  +5  -8 +20  -6   =  11

****************************************
FR numerals from 0 up to 13 absolute value within 15
a=15 c=-9 d=14 e=6 é=5 f=2 h=13 i=8 n=7 o=-5 p=-2 q=-1 r=-3 s=10 t=-7 u=-6 x=-12 z=3

   z   é   r   o   =   0
  +3  +5  -3  -5   =   0

   u   n   =   1
  -6  +7   =   1

   d   e   u   x   =   2
 +14  +6  -6 -12   =   2

   t   r   o   i   s   =   3
  -7  -3  -5  +8 +10   =   3

   q   u   a   t   r   e   =   4
  -1  -6 +15  -7  -3  +6   =   4

   c   i   n   q   =   5
  -9  +8  +7  -1   =   5

   s   i   x   =   6
 +10  +8 -12   =   6

   s   e   p   t   =   7
 +10  +6  -2  -7   =   7

   h   u   i   t   =   8
 +13  -6  +8  -7   =   8

   n   e   u   f   =   9
  +7  +6  -6  +2   =   9

   d   i   x   =  10
 +14  +8 -12   =  10

   o   n   z   e   =  11
  -5  +7  +3  +6   =  11

   d   o   u   z   e   =  12
 +14  -5  -6  +3  +6   =  12

   t   r   e   i   z   e   =  13
  -7  -3  +6  +8  +3  +6   =  13

****************************************
PL numerals from 0 up to 13 absolute value within 10
a=7 c=-4 ć=1 d=-8 e=5 ę=-10 i=8 j=-1 m=-7 n=0 o=-2 p=6 r=-5 s=4 ś=-6 t=9 w=3 y=-3 z=2

   z   e   r   o   =   0
  +2  +5  -5  -2   =   0

   j   e   d   e   n   =   1
  -1  +5  -8  +5  +0   =   1

   d   w   a   =   2
  -8  +3  +7   =   2

   t   r   z   y   =   3
  +9  -5  +2  -3   =   3

   c   z   t   e   r   y   =   4
  -4  +2  +9  +5  -5  -3   =   4

   p   i   ę   ć   =   5
  +6  +8 -10  +1   =   5

   s   z   e   ś   ć   =   6
  +4  +2  +5  -6  +1   =   6

   s   i   e   d   e   m   =   7
  +4  +8  +5  -8  +5  -7   =   7

   o   s   i   e   m   =   8
  -2  +4  +8  +5  -7   =   8

   d   z   i   e   w   i   ę   ć   =   9
  -8  +2  +8  +5  +3  +8 -10  +1   =   9

   d   z   i   e   s   i   ę   ć   =  10
  -8  +2  +8  +5  +4  +8 -10  +1   =  10

   j   e   d   e   n   a   ś   c   i   e   =  11
  -1  +5  -8  +5  +0  +7  -6  -4  +8  +5   =  11

   d   w   a   n   a   ś   c   i   e   =  12
  -8  +3  +7  +0  +7  -6  -4  +8  +5   =  12

   t   r   z   y   n   a   ś   c   i   e   =  13
  +9  -5  +2  -3  +0  +7  -6  -4  +8  +5   =  13

****************************************
ES numerals from 0 up to 11 absolute value within 20
a=-9 c=20 d=4 e=7 h=10 i=-19 n=-5 o=-11 r=-16 s=9 t=3 u=17 v=-17 z=18

   c   e   r   o   =   0
 +20  +7 -16 -11   =   0

   u   n   o   =   1
 +17  -5 -11   =   1

   d   o   s   =   2
  +4 -11  +9   =   2

   t   r   e   s   =   3
  +3 -16  +7  +9   =   3

   c   u   a   t   r   o   =   4
 +20 +17  -9  +3 -16 -11   =   4

   c   i   n   c   o   =   5
 +20 -19  -5 +20 -11   =   5

   s   e   i   s   =   6
  +9  +7 -19  +9   =   6

   s   i   e   t   e   =   7
  +9 -19  +7  +3  +7   =   7

   o   c   h   o   =   8
 -11 +20 +10 -11   =   8

   n   u   e   v   e   =   9
  -5 +17  +7 -17  +7   =   9

   d   i   e   z   =  10
  +4 -19  +7 +18   =  10

   o   n   c   e   =  11
 -11  -5 +20  +7   =  11

****************************************
IT numerals from 0 up to 10 absolute value within 10
a=0 c=-8 d=-7 e=5 i=10 n=-4 o=1 q=-2 r=-5 s=-9 t=3 u=4 v=7 z=-1

   z   e   r   o   =   0
  -1  +5  -5  +1   =   0

   u   n   o   =   1
  +4  -4  +1   =   1

   d   u   e   =   2
  -7  +4  +5   =   2

   t   r   e   =   3
  +3  -5  +5   =   3

   q   u   a   t   t   r   o   =   4
  -2  +4  +0  +3  +3  -5  +1   =   4

   c   i   n   q   u   e   =   5
  -8 +10  -4  -2  +4  +5   =   5

   s   e   i   =   6
  -9  +5 +10   =   6

   s   e   t   t   e   =   7
  -9  +5  +3  +3  +5   =   7

   o   t   t   o   =   8
  +1  +3  +3  +1   =   8

   n   o   v   e   =   9
  -4  +1  +7  +5   =   9

   d   i   e   c   i   =  10
  -7 +10  +5  -8 +10   =  10

****************************************
EN numerals from 0 up to 12 absolute value within 10
e=-2 f=-6 g=0 h=-7 i=7 l=9 n=2 o=1 r=4 s=3 t=10 u=5 v=6 w=-9 x=-4 z=-3

   z   e   r   o   =   0
  -3  -2  +4  +1   =   0

   o   n   e   =   1
  +1  +2  -2   =   1

   t   w   o   =   2
 +10  -9  +1   =   2

   t   h   r   e   e   =   3
 +10  -7  +4  -2  -2   =   3

   f   o   u   r   =   4
  -6  +1  +5  +4   =   4

   f   i   v   e   =   5
  -6  +7  +6  -2   =   5

   s   i   x   =   6
  +3  +7  -4   =   6

   s   e   v   e   n   =   7
  +3  -2  +6  -2  +2   =   7

   e   i   g   h   t   =   8
  -2  +7  +0  -7 +10   =   8

   n   i   n   e   =   9
  +2  +7  +2  -2   =   9

   t   e   n   =  10
 +10  -2  +2   =  10

   e   l   e   v   e   n   =  11
  -2  +9  -2  +6  -2  +2   =  11

   t   w   e   l   v   e   =  12
 +10  -9  -2  +9  +6  -2   =  12

As you see German won with perfect number names possible for 0…16.

Python code

 

# -*- coding: UTF-8 -*-
# Copyright 2016 TKK
from z3 import sat, Int, Solver

NUMERALS = {
  "PL" : "zero,jeden,dwa,trzy,cztery,pięć,sześć,siedem,osiem,dziewięć,dziesięć,jedenaście,dwanaście,trzynaście,czternaście".split(','),
  "DE" : "null,eins,zwei,drei,vier,fünf,sechs,sieben,acht,neun,zehn,elf,zwölf,dreizehn,vierzehn,fünfzehn,sechzehn,siebzehn".split(','),
  "FR" : "zéro,un,deux,trois,quatre,cinq,six,sept,huit,neuf,dix,onze,douze,treize,quatorze,quinze,seize".split(','),
  "IT" : "zero,uno,due,tre,quattro,cinque,sei,sette,otto,nove,dieci,unidici,dodici,tredici,quattordici,quindici,sedici".split(','),
  "ES" : "cero,uno,dos,tres,cuatro,cinco,seis,siete,ocho,nueve,diez,once,doce,trece,catorce,quince,dieciséis,diecisete".split(','),
  "PT" : "zero,um,dois,três,quatro,cinco,seis,sete,oito,nove,dez,onze,doze,treze,quatorze,quinze,dezesseis".split(','),
  "NL" : "nul,één,twee,dire,vier,vijf,zes,zeven,acht,negen,tien,elf,twaalf,dertien,veertien,vijftien".split(','),
  "EN" : "zero,one,two,three,four,five,six,seven,eight,nine,ten,eleven,twelve,thirteen,fourteen".split(',')
}

CHARMAP = { 'ć': 'c_', 'ę': 'e_', 'ś': 's_', 'ö': 'o_', 'ü': 'u_', 'é': 'e_acute', 'ê': 'e_circ' }

def find_num(numerals, limit, charmap):
  letters = sorted(set(charmap.get(x, x) for x in "".join(numerals)))

  my_sym = {}
  for l in letters:
    my_sym[l] = Int(l)

  s = Solver()
  for i, w in enumerate(numerals):
    s.add(sum([ my_sym[charmap.get(c, c)] for c in w ]) == i)

  for i, let in enumerate(letters):
    if limit is not None:
      s.add(my_sym[let] >= -limit)
      s.add(my_sym[let] <= limit)

    for let2 in letters[i + 1:]:
      s.add(my_sym[let] != my_sym[let2] )

  chk = s.check()
  model = None
  if chk == sat:
    model = s.model()
  return chk, model

def find_longest_existing(numerals, charmap): 
  for lennum in range(len(numerals), 0, -1):
    ret, model = find_num(numerals[:lennum], None, charmap)
    if ret == sat:
      return lennum
  return 0

def find_best_assignment(numerals, charmap):
  for m in range(5, 100):
    ret, model = find_num(numerals, m, charmap)
    if ret == sat:
      return m, model
  return None, None

def pretty_print_solution(lang, range_max, abs_max, model, charmap):
    rev_charmap = dict(zip(charmap.values(), charmap.keys()))
    print("*" * 40)
    print(lang, "numerals from 0 up to", range_max - 1, "absolute value within", abs_max)
    #print(NUMERALS[lang][:v])
    sp = sorted((str(k), model[k].as_long()) for k in model)
    sval = dict(sp)
    print(" ".join(["{}={}".format(rev_charmap.get(p[0], p[0]), p[1]) for p in sp ]))
    print()
    
    for i, word in enumerate(NUMERALS[lang][:range_max]):
        let, num, nsum = "", "", 0
        for ch in word:
            let += "{: >4}".format(ch)
            chval = sval[CHARMAP.get(ch, ch)]
            num += "{: >+4}".format(chval)
            nsum += chval

        let += "   ={: >4}".format(i)
        num += "   ={: >4}".format(nsum)
        print(let)
        print(num)
        print()    

def main():
  for lang in NUMERALS:
    v = find_longest_existing(NUMERALS[lang], CHARMAP)
    
    ret, model = find_best_assignment(NUMERALS[lang][:v], CHARMAP)
    if ret and model:
        pretty_print_solution(lang, v, ret, model, CHARMAP)    
   
if __name__ == "__main__":
  main()

This is related to the previous post. I have started developing drop-in replacement for atoi() and atol(). The new functions maintain the compatibility with the library functions and yet are faster on the platforms and compilers I tested. The sign of a number and whitespace are handled as atoi() would, with the caveat that whitespace is hardcoded to match atoi() behavior when LCC_ALL=C. See the source code and performance charts.