Archive

Posts Tagged ‘heuristic’

How I learned to type the Neo2 keyboard layout: a review after the first 1.5 years

December 27, 2016 Leave a comment

neo-iconA couple of years back, I was asking myself: should I switch my keyboard layout to a more effective one? If yes, which new layout should I learn? For obvious reasons I searched for reports of people that did such a switch before. And this is why I try to give such a report myself now, after typing Neo2 for about 1.5 years – which seems to be a good point for summarizing my success story with Neo2 so far.

But first: some details about my typing characteristics before I learned typing the Neo2 layout. I…

  • …was “successfully” using the German QWERTZ keyboard layout for something like 12 years with a 10-finger-system.
  • …was typing with somewhere around 450 characters per minute for normal text.
    …did software development for a living and especially disliked the access to special characters my back-then keyboard layout.
  • …didn’t like the idea of using an ineffective keyboard layout in general. The layout I was using back then was a) not optimized for today’s hardware and b) I used it all day as it is the number 1 tool used in my profession, so investing in improvements should really pay off on the long run.

Overview of alternative keyboard layouts

There are (and were back in the day) many alternatives to the layout I used. For some examples, see e.g.:

I looked a bit into heuristically optimized keyboard layouts. Some of them use the same higher layers as Neo2 and just have layer 1 and 2 rearranged heuristically, such as the bone layout (German: http://wiki.neo-layout.org/wiki/Bone). Why didn’t I chose such a layout? Those had/still have less support, as they are not used so widely. This brings additional effort when configuring/using different PCs/hardware.

Additionally, for something so important for me and my daily business I preferred to use something already proven to work well, and would therefore bring less problems with it.

Why use Neo2 instead of other alternatives?

Neo was designed back in 2004 and was optimized for the German language. Due to German being very similar to English from key frequency point of view the “being optimized to German” did not make a big difference to me (and still does not make any, you can rest assured that it’s very comfortable to type English with it). Neo2 has a very good heatmap (optimized for key position and typing interleaving with left/right keys:

keyboard_heatmap_for_german_neo

Though there are arrangements that are a little more effective and further optimized (e.g. heuristically),  when it comes to key frequencies, having such a heatmap still is an amazing thing.

To me, even more important was that access to special characters is solved very cleverly with Neo2. There are 6 layers in total:

  • Layer 1+2 are lower and upper case characters – those are the ones you are probably used to on your keyboard. The “modifier” keys are the Shift keys.
  • Layer 3 are special characters (right below your fingers, e.g. in the home row!). The “modifier” keys are the CapsLock button on the left side and the “#” key on the right side.
  • Layer 4 are other special characters and special keys
  • Layer 5+6 are Greek letters.

The special characters on layer 3 make accessing special characters for programming very easy. And layer 4 is something that is easily underestimated: it features:

  • Keys to control cursor position like up/down/left/right, page up/down, delete left/right, home/end, escape, tab, enter, etc. – all under your left hand.
  • All numbers in the form of a keypad – all under your right hand.

From this point of view, Neo2 is more effective for programmers than e.g. Dvorak, Colemak, or similar keyboard layouts (still, those are pretty cool too). But besides the Neo2 layout having a lively community and already being proven to working well, this was the main reason for learning Neo2 instead of any other layout.

Learning and switching to Neo2

How not to do it

Maybe 3 years before I already had tried Neo2 – for very short time. Back then I set my goal similar to “I want to type in Neo!”, printed a Neo2 layout onto an A4 sheet of paper, switched my keyboard layout to Neo2 and just started typing it. In short: it did no work out. I had to search for every key using the printout, and of course got frustrated over the extremely low speed of typing (which was to be expected) very fast – and quit within hours.

How to do it

After the first try, the goal of switching keyboard layout remained. I wanted to use a more effective keyboard layout/Neo2 someday, as it would just be so much more effective for my everyday usage. The second time (maybe 2 years after the first try) I was better prepared to really perform a switch:

  1. I used KTouch with Neo2 to train single keys – one after another (the KTouch “beginner mode”). I did this is my free time, at work I continued to use my QWERTZ layout. Further, I made sure that I typed all keys with the correct fingers (I had had a slight mash-up with the QWERTZ layout before).
  2. In KTouch I used standard settings, which are minimum 180 chars per minute and 98% accuracy to pass each lesson and unlock the next one. This ensures you don’t try to learn¬† too much at once, which was the problem with my first try.
  3. Using KTouch I trained about 1/3 of the Neo2 lessons provided. Those were all about introducing and training new character keys. It was no problem to write with my QWERTZ layout at work at the time (switching was smooth).
  4. After finishing about 1/3 of the Neo2-lessons provided with KTouch (within 1.5 months as far as I remember), I did the “all in” thing: I switched all my layouts to Neo2 and typed all texts with it. This included my keyboard at work as well as e.g. my on-screen keyboard on my mobile phone. Of course it was very slow at the beginning again (first few days), but now I learned very fast. After about 2 to 3 weeks of typing, my speed was OK, while I was still learning at a fast rate without requiring any extra training time. This was when typing the old QWERTZ layout became more difficult for me.
  5. Since then I’ve just continued to write Neo2. Once in a while I did some more lessons in KTouch – but these were just for training and comparing typing speeds. But overall, using a typing trainer like KTouch definitely was the “enabler” of learning a new keyboard layout for me.

Progress report after the first 1.5 years

I started learning Neo2 around end of February 2015. Within about 1.5 months (after successfully completing about 1/3 of the lessons in KTouch) I made the “all in” move and switched all my layouts to Neo2. My progress since then:

  • Mid of April (~2 months): about 190 chars/min, 95.5% accuracy in the 1000 English words test from KTouch Neo2.
  • End of April: feeling more comfortable every day.
  • Mid of May (~3 months): about 250 chars/min, 95.5% accuracy in the German/English words test from KTouch Neo2.
  • Mid of June (~4 months): 286 char/min, 98.5% accuracy (09:02 in the “repeat many words test” in KTouch Neo2).
  • End of September (~7.5 months): 286 char/min, 96.3% accuracy (21:13 in the 1000 most frequently used English words test in KTouch Neo2) and 289 char/min, 97.2% accuracy (08:57 in the “repeat many words test” in KTouch Neo2).
  • Beginning of February (~1 year): 337 char/min, 96.8% accuracy (6:50 in the KTouch Neo2 train comma lesson).
  • Mid of February 2016 (~1 year): 330 char/min, 97.2% accuracy (18:20 in the 1000 most frequently used English words test in KTouch Neo2) and 311 char/min, 96.4% accuracy (8:20 in the KTouch Neo2 “repeat many words test”).
  • April 2016 ~1 year 2 months: 318 chars/min with 97.2 accuracy with the KTouch Neo2 congratulation text for finishing Neo2 training. Programming: 241char/min with 96.5% accuracy in KTouch Neo2 shell text (special characters, numbers, …). This pretty much is what I wanted in the beginning – it made me writing code on my keyboard more effectively. Additionally: have the feeling that I need to think less about how I do things, and more about what I want do to. Specially the position keys under left hand at level 4 (move cursor up/down/left/right, page up/down, delete left right, home/end) have proven extremely effective – much more than I initially thought – to quickly move the cursor around when programming.
  • July 2016 ~1 years 5 moths: 333 chars/min with 98.0% accuracy (18:09 in the 1000 most frequently used English words test in KTouch Neo2).

This is an example of how your progress for learning Neo2 in KTouch could look like:

  • Left: progress for one single lesson: usually, you will always increase in speed and accuracy when repeating the same lesson (which is why you are able to learn a new keyboard layout relatively fast if you take it seriously).
  • Right: progress for different/all lessons: usually, you increase in speed and accuracy for a specific lesson, and when you move on to the next lesson your speed and accuracy will be lower for it at the beginning – which is because you are just learning completely new things there. I can scroll far to the left in this view – and it’s a good feeling to see speed and accuracy continuously increasing over time there ūüėČ

 

 

 

 

The final (and frequently asked) questions

Is my typing speed still increasing? Yes, definitely. Was it worth the effort? Would I do it again? Yes, definitely, to both. Though, at the moment I’m still a bit slower in typing regular texts than I was before, programming is definitely faster already. Typing feels less cumbersome: especially complex combinations of symbols/characters are easier to type, and I don’t need to move my right hand anymore for reaching e.g. arrow keys, delete/insert, or similar. Besides making a large number small tasks a little faster (which sums up to a lot in the end), this also just feels more satisfactory.

So, bottom line: in my opinion, especially when your job involves something like programming, learning Neo2 really pays off in the end.

Magic number board puzzle solver in Python

December 2, 2014 Leave a comment

The magic number board puzzle is yet another equation puzzle (similar to the first equation puzzle or Jodici) – but has a notable larger solution space.

Magic number board

A magic number board example

The magic number board is a quadratic board, consisting of 5×5 = 25 fields, which are organized as 5 horizontal rows and 5 vertical columns. Each field should contain a number in the range [5,29], which each number being used exactly once in the board. Each row, column and both diagonals should sum to 85 exactly. Some numbers are already given at start – the task is to fill in all remaining fields while sticking to the rules.

Solving the magic number board puzzle

We’re going to refer to rows/fields/diagonals as “groups” from now (e.g. if a fact or rule is true for all groups it’s true for all rows, columns and diagonals). The magic number puzzle contains 12 such groups, consequently we have 12 equations in total, and – given 8 of the 25 fields being filled at the start – 17 variables to fill in. Without additional rules, this would allow for multiple solutions. The additional rule of using each number once in the board reduces the amount of valid solutions to one, if the puzzle is designed correctly.

The solution space is notably larger than with the equation puzzle or Jodici. Given 8 initially filled fields we have 17 yet empty fields, for which we have 17! solutions (3.5*10^14 solutions or ~48bit entropy). Pure brute force would of course find the solution, but would require an arguable amount of time to do so with typical PCs or Laptops. Therefore, we are speeding up the process by using best first search and – more important – incorporating the following optimizations.

Successor generation (branching factor reduction)

When adding a number to the board, we don’t need to generate all successors (e.g. place every possible number in every still empty field). We know that we can still reach all possible solutions in our search tree, if we just fill in all possible numbers to a single field (generating multiple successors having this field filled, but all other previously empty field still being empty). Doing so causes us to skip different orders of filling numbers to fields (e.g. first filling 1 to field A, then 2 to field B, or first filling 2 to field B, then 1 to field A – which would result in the same state). Consequently, this reduces the branching factor and therefore the runtime. Given this optimization idea, the question is: how to determine the one field we’re going to fill numbers into? Which his brings us to:

Order of fields to be filled (heuristic search direction)

A human player would try to fill numbers to those groups that already contain many numbers. Why? Because usually, there are least possibilities of numbers to be filled into these groups (which again causes a lower branching factor, therefore less complexity to deal with for the human player). Hence, we always fill a field in the group with the least fields still empty (excluding completely filled groups of course). An example of using such an order: imagine we have a group which already contains 4 numbers. There is (at max) one possibility for the fifth number, as the five numbers have to sum to 85. A human player would immediately fill in that number – a behaviour we should also strive for in our approach.

Validity check – detecting dead ends early (branch cutting)

The third thought is about evaluating if a board is already invalid, which correlates to branch cutting in search. As we fill numbers into the board it’s very important to find out as soon as possible, if the board cannot yield a valid solution any more (therefore all possible successors can be excluded from search, which cuts parts of search tree, and which saves us lots of resources).¬† An example for such using such checks for groups containing 4 numbers: with the the fifth number all numbers of that group have to sum to 85. In case the number required to be filled into the field yet empty for the sum to be 85 is already used elsewhere, the current board cannot yield a valid solution any more – therefore the board can be excluded from search. We don’t only check groups already containing 4 numbers, but also groups containing 3 numbers. For these groups we try to fill in all permutations of numbers still available and check, if with at least one combination the group sums to 85. If this is the case, the group is counted as valid. If no combination allows for a sum of 85, the board is already invalid and we exclude it from search. Note: using permutations of numbers still available, conceptually it would be possible to check for groups with any amount of already filled in numbers (e.g. 2, 1 or even empty groups). The drawback is that the amount of permutations that need to be checked increases exponentially with the amount of fields of the group still being empty. Consequently, the gain of recognizing invalid boards earlier is easily eaten up by the additional complexity of generating and checking permutations.

Python implementation

# Magic number square solver implementation. The magic number square is a 5x5 number board in which each field must contain a nr [5,25]. Some numbers are given at the start, all others have to be found. In the end, each nr must be used once and all rows, columns and both diagonals have to sum to 85. 
# Rainhard Findling
# 2014/11
# 
# Core concepts:
# 
# Branch cutting: we look at each generated board: for each row (incl. row, col, diagonal) the remaining numbers must contain at least one permutation with which the row sums up exactly to 85, otherwise the board can only create invalid solutions and is skipped in future search.
# 
# Heuristic (search direction): we prefer boards which are more filled over boards not so filled. We futher prefer rows with more filled cells over rows with less filled cells. In fact, we use a monotinic metric: 1 row with N filled cells is always worth more than [MAX] rows which have N-1 cell filled less. Therefore, we always try to fill the row with already has the most filled cells (except of completely filled rows). 
# 
# Successor generation: of a board only those successors get created that fill a number to the row with most already filled cells (excluding completely filled rows). This is intuitive, but it seems it would not be necessary as we do heuristic sorting whcih would prefer "more filled" boards always. But it's also required for another reason: it is important in combination with branch cutting (it's one solution to the problem that would emerge otherwise). For a board with a row where only 1 cell is not filled yet, that cell could remain unfilled (even if we have a heuristic that would enforce this cell to be filled next) - simply because filling the cell makes the row valid, but there are no valid successors of the resulting board possible anymore. This would lead to the irrational behavior of trying this cell and discarding all successors, then trying the other candidates from the list which still have this one cell free, therefore leaving this cell free (for getting a still high bonus for having one nearly filled row) and trying to fill cells elsewhere. The approach of only filling the row with already highest filling status - except completely filled rows - ensures that there are no states that allow for "leaving out because resulting successors are invalid" scenarios.
# 
import itertools
import copy
import numpy

global_sum = 85
global_nrs_range = range(5, 30)
global_branchcutting_min_amount_of_filled_cells_to_perform_permutation_check = 3
global_heuristics_row_fill_stat_hist_weights = [12**x for x in range(6)] # why? because with 5*5 we have 12 rows to validate in total. therefore, if we want to favor boards that have more filled or nearly filled rows, our base b for hist**b has to be 12 for the metric order to be monotone. why 6 weights if we have 5*5? because we weight the '0-fills' too.
_ = '__' # placeholder for empty fields

class Cell():
    """representation of a cells in the gameboard."""
    def __init__(self, nr=_):
        self.nr = nr
        #if(self.nr != _):
            #self.available_nrs = []
        #else:
            #self.available_nrs = global_nrs_range

    def __str__(self):
        return '%2s' % str(self.nr)

    def str_verbose(self):
        """str with more information about this cell than __str__."""
        return self.__str__() + ' (' + ','.join([ str(x) for x in self.available_nrs]) + ')'

    def __repr__(self):
        return self.__str__()
    
    def __deepcopy(self, memo):
        return Cell(self.nr)

class Board():
    """Representation of a gameboard holding all numbers + helper infos for solving it."""
    def __init__(self, gameboard, parent, available_nrs=None):
        self.gameboard = gameboard
        self.parent = parent
        if(available_nrs != None):
            self.available_nrs = available_nrs
        else:
            self.available_nrs = self.generate_available_nrs_from_gameboard()

    def generate_available_nrs_from_gameboard(self):
        """derive still available numbers from gameboard."""
        return [x for x in global_nrs_range if not x in map(lambda x:x.nr, self.all_cells_as_vector())]
        
    def all_cells_as_vector(self):
        return reduce(lambda x,y:x+y, self.gameboard)
    
    def __str__(self):
        return self.str_gameboard(self.gameboard)
    
    def str_gameboard(self, gameboard):
        """string representation of a gameboard = board."""
        s = '\n================\n'
        for row in gameboard:
            s += '|' + ' '.join([x.__str__() for x in row]) + '|\n'
        s += '================\n'
        return s
    
    def __repr__(self):
        return self.__str__()
    
    def __deepcopy__(self, memo):
        # we do not/cannot deepcopy parent!
        return Board(copy.deepcopy(self.gameboard), self.parent, copy.deepcopy(self.available_nrs))
    
    def __eq__(self, other):
        if other == None:
            return False
        for self_row, other_row in zip(self.gameboard, other.gameboard):
            for self_cell, other_cell in zip(self_row, other_row):
                if not self_cell.nr == other_cell.nr:
                    return False                
        return True
          
    def __cmp__(self, other):
        # __cmp__ should return a negative integer if self < other, zero if self == other, and positive if self > other
        if self.heuristic() < other.heuristic():
            return -1
        if self.heuristic() == other.heuristic():
            return 0
        else:
            return 1
    
    def copy_transposed(self):
        """get a transposed copy of the gameboard: rows become columns, columns become rows."""
        return [[row[nr] for row in self.gameboard] for nr in range(len(self.gameboard))]
    
    def diagonal_topleft_bottomright(self):
        """get the topleft to bottomright diagonal 'row'"""
        return [self.gameboard[nr][nr] for nr in range(len(self.gameboard))]
    
    def diagonal_topright_bottomleft(self):
        """get the topright to bottomleft diagonal 'row'"""
        return [self.gameboard[len(self.gameboard)-nr-1][nr] for nr in range(len(self.gameboard))]
    
    def get_all_groups(self):
        """returns all groups (rows, cols, diagonals) that have to fulfill certain criteria."""
        return self.gameboard + self.copy_transposed() + [self.diagonal_topleft_bottomright()] + [self.diagonal_topright_bottomleft()]
    
    def is_valid(self):
        """checks if this gameboard is valid / can still be solved in a valid way."""
        for row in self.get_all_groups():
            free = len(filter(lambda cell:cell.nr == _, row))
            #print 'free', free
            if(len(self.gameboard) - free < global_branchcutting_min_amount_of_filled_cells_to_perform_permutation_check):
                # too many unfilled cells, we don't check if permutations can still make this row valid
                #print 'skipping row with', str(free), 'free cells during checks'
                continue
            if(free == 0):
                # is already filled. sanity check: is it's filled in valid way?
                if(reduce(lambda x,y:x+y.nr, row, 0) != global_sum):
                    return False
                    #raise Exception('Completely filled row does not sum to ' + str(global_sum) + ': ' + str(row))
                continue
            cur_sum = reduce(lambda x,y:x + (y.nr if y.nr != _ else 0), row, 0) # sum of nrs currently in this row
            # check that from nrs still available it's still possible to get this row to the target sum
            sum_remainder = global_sum - cur_sum
            # does any combination of available nrs still fulfill this criteria?
            permutations = itertools.permutations(self.available_nrs, free)
            if not any([sum(x) == sum_remainder for x in permutations]):
                return False
            
        return True
    
    def is_filled(self):
        """checks if all fields are filled. valid + filled therefore means solved."""
        for row in self.gameboard:
            for cell in row:
                if cell.nr == _:
                    return False
        return True
    
    def generate_successors(self):
        """generate all possible successor states of this board."""
        successors = []
        counts = [len(filter(lambda cell:cell.nr != _, row)) for row in self.get_all_groups()]
        row_nr = counts.index(max(filter(lambda x:x<len(self.gameboard),set(counts))))
        #for row_nr in range(len(self.gameboard)):
        row = self.get_all_groups()[row_nr]
        for cell_nr in range(len(row)):
            cell = row[cell_nr]
            if cell.nr == _:
                # this cell can be set as next step
                for nr in self.available_nrs:
                    # generate clone
                    suc = copy.deepcopy(self)
                    # modify to show new state
                    suc.available_nrs.remove(nr)
                    suc.get_all_groups()[row_nr][cell_nr].nr = nr
                    suc.parent = self
                    if suc.is_valid():
                        successors.append(suc)
        return successors
        
    def fill_stat_hist(self):
        """histogram of how row fill states: how much rows exist with have 0, 1, 2 etc. filled cells."""
        counts = [len(filter(lambda cell:cell.nr != _, row)) for row in self.get_all_groups()]
        #fill_stat_hist = [len(list(group)) for key,group in itertools.groupby(counts)]
        fill_stat_hist = [len(filter(lambda x:x==i, counts)) for i in range(len(self.gameboard)+1)]
        return fill_stat_hist

    def fill_stat_hist_weighted(self):
        """the same hist weighted by how much we think it's worth to have more of 'such' row fill states."""
        return map(lambda x:x[0]*x[1], zip(self.fill_stat_hist(), global_heuristics_row_fill_stat_hist_weights))
        
    def heuristic(self):
        """heuristic of how good this field is. bigger means better."""
        return sum(self.fill_stat_hist_weighted())
            
    def path(self):
        """evolution chain from beginning to this state - for getting detailled insight."""
        return [self] if self.parent == None else self.parent.path() + [self]

def generate_board(board):
    return Board([[Cell(x) for x in row] for row in board], None)

# generate board
b = generate_board([    [ _, _, _, _,15],
                        [ _, _,25,17, _], 
                        [ _,26, _, 5, _], 
                        [ _,18, _, _,11], 
                        [ _, _,21, _, _]])
print b

# best first search
nodes = [b]
closed = []
solutions = []
while(len(nodes) > 0):
    # sort: bigger heuristic = best = last in list
    nodes.sort()
    node = nodes.pop()
    closed.append(node)
#    print 'current board:', node
    #print 'nodes remaining in list:', len(nodes)
    #print 'fill_stat_hist:', str(node.fill_stat_hist())
    #print 'fill_stat_hist weighted:', str(node.fill_stat_hist_weighted())
#    print 'solutions:', len(solutions)
    # produce some kiddies
    successors = node.generate_successors()
    suc_finished = filter(lambda suc:suc.is_filled(), successors)
    if(len(suc_finished) > 0):
        #print 'solution(s):', map(lambda x:x.path(), suc_finished)
        solutions += suc_finished
        print 'solutions:', len(solutions)
        #break
    suc_unfinished = filter(lambda suc:not suc.is_filled(), successors)
    suc_to_add = filter(lambda suc:not suc in nodes and not suc in closed, suc_unfinished)
    nodes += suc_to_add
    
print map(lambda x:x.path(), solutions)
print 'found solutions:', len(solutions)
print 'finished.'

When running the solver on the magic number board example from above, we get presented the single possible, valid solution (along with the steps it took to get there, which are not shown here for layouting reasons ):

================
|__ __ __ __ 15|
|__ __ 25 17 __|
|__ 26 __  5 __|
|__ 18 __ __ 11|
|__ __ 21 __ __|
================

solutions: 1
[[
================
|__ __ __ __ 15|
|__ __ 25 17 __|
|__ 26 __  5 __|
|__ 18 __ __ 11|
|__ __ 21 __ __|
================
,
[...]
,
================
|28 24  6 12 15|
|13  7 25 17 23|
| 8 26 19  5 27|
|20 18 14 22 11|
|16 10 21 29  9|
================
]]
found solutions: 1
finished.