ford johnson no recursion

mgerqoirg.txt

-- input
mgerqoirg

------------------------------------
--> step 0 : create board with couples

----- board ----------
m..rq..r. -- unordered
g  eo  ig


--------------------------------------
--> step 1: order the board
--> recursion (difficult todo because we have to reuse this algorithm on couples of the board.

----- board ----------
m..qr..r. -- ordered part
g  oe  ig

-----------------------------------
--> step 2: add jacobstahl numbers to the board

----- board ----------
m..qr..r. -- ordered part
g  oe  ig -- unordered part
1  03  24 -- jacobstahl position

-- jacobstahl back index
30748  -- couple position

-------------------------------------------------
--> step 3: consume first jacobsthal back index (3)
--> we clean up the column 3 leaving it alone with the `q`
--> looking up the 3rd column we see that we have to insert `o` before column 3
--> with bisection on columns 0..2 we place g in the column 1
--> column 1 is free so we stop moving stuff


----- board ----------
mo.qr..r. -- ordered part
g   e  ig  -- unordered part
1   3  24  -- jacobstahl position

-- jacobstahl back index
.0748  -- couple position

-------------------------------------------------
--> step 4: consume next jacobsthal back index (0)
--> we clean up the column 0   leaving it alone with `m`
--> looking up the 0st column we see that we have to insert `g` before column 0
--> with bisection on columns .. we place `g` the column 0
--> so we have to move column with `o`
--> it has space on the right so we stop there

----- board ----------
gmoqr..r. -- ordered part
    e  ig  -- unordered part
    3  24  -- jacobstahl position

-- jacobstahl back index
..748  -- couple position

-------------------------------------------------
--> step 5: consume next jacobsthal back index (7)
--> we clean up the 7th column leaving the `r` alone
--> looking up the 7th column we see that we have to insert `i` before column 7
--> with bisection on columns 0..6 we place i in the column 1
--> so we have to move column with `o` , `q` , `m` and `r` and then stop because on the right of `r`
--> but moving the `r` requires us to update the jacobstahl back index pointed by `r`
--> (index 3) which value was 4 and now it becomes 5

----- board ----------
gimoqr.r. -- ordered part
     e  g   -- unordered part
     3  4  -- jacobstahl position

-- jacobstahl back index
...58  -- couple position


-------------------------------------------------
--> step 6: consume next jacobsthal back index (5)
--> we clean up the 5th column leaving the `r` alone
--> looking up the 5th column we see that we have to insert `e` before column 5
--> with bisection on columns 0..4 we place e in the column 0
--> so we have to move column with `g` , `i` , `m`, `o` and `r` and then stop because on the right of `r`

----- board ----------
egimoqrr. -- ordered part
        g   -- unordered part
        4  -- jacobstahl position

-- jacobstahl back index
....8  -- couple position

-------------------------------------------------
--> step 7: consume next jacobsthal back index (8)
--> we clean up the 8th column which has . placeholder so we leave it alone
--> looking up the 8th column we see that we have to insert `g` before column 8
--> with bisection on columns 0..7 we place g in the column 2
--> so we have to move column with `i`, `m`, `o` , `q` , `r` and `r` and then stop because on the right of `r`

----- board ----------
eggimoqrr -- ordered part
           -- unordered part
           -- jacobstahl position

-- jacobstahl back index
.....  -- couple position