## Comparison of Wang tiling solvers

12 décembre 2018 | Catégories: sage, slabbe spkg, math | View Comments

During the last year, I have written a Python module to deal with Wang tiles containing about 4K lines of code including doctests and documentation.

It can be installed like this:

sage -pip install slabbe

It can be used like this:

sage: from slabbe import WangTileSet sage: tiles = [(2,4,2,1), (2,2,2,0), (1,1,3,1), (1,2,3,2), (3,1,3,3), ....: (0,1,3,1), (0,0,0,1), (3,1,0,2), (0,2,1,2), (1,2,1,4), (3,3,1,2)] sage: T0 = WangTileSet([map(str,t) for t in tiles]) sage: T0.tikz(ncolumns=11).pdf()

The module on wang tiles contains a class `WangTileSolver` which contains
three reductions of the Wang tiling problem the first using MILP solvers,
the second using SAT solvers and the third using Knuth's dancing links.

Here is one example of a tiling found using the dancing links reduction:

sage: %time tiling = T0.solver(10,10).solve(solver='dancing_links') CPU times: user 36 ms, sys: 12 ms, total: 48 ms Wall time: 65.5 ms sage: tiling.tikz().pdf()

All these reductions now allow me to compare the efficiency of various types of solvers restricted to the Wang tiling type of problems. Here is the list of solvers that I often use.

Solver | Description |
---|---|

'Gurobi' |
MILP solver |

'GLPK' |
MILP solver |

'PPL' |
MILP solver |

'LP' |
a SAT solver using a reduction to LP |

'cryptominisat' |
SAT solver |

'picosat' |
SAT solver |

'glucose' |
SAT solver |

'dancing_links' |
Knuth's algorihm |

In this recent work on the substitutive structure of Jeandel-Rao tilings, I introduced various Wang tile sets \(T_i\) for \(i\in\{0,1,\dots,12\}\). In this blog post, we will concentrate on the 11 Wang tile set \(T_0\) introduced by Jeandel and Rao as well as \(T_2\) containing 20 tiles and \(T_3\) containing 24 tiles.

**Tiling a n x n square**

The most natural question to ask is to find valid Wang tilings of \(n\times n\) square with given Wang tiles. Below is the time spent by each mentionned solvers to find a valid tiling of a \(n\times n\) square in less than 10 seconds for each of the three wang tile sets \(T_0\), \(T_2\) and \(T_3\).

We remark that MILP solvers are slower. Dancing links can solve 20x20 squares with Jeandel Rao tiles \(T_0\) and SAT solvers are performing very well with Glucose being the best as it can find a 55x55 tiling with Jeandel-Rao tiles \(T_0\) in less than 10 seconds.

**Finding all dominoes allowing a surrounding of given radius**

One thing that is often needed in my research is to enumerate all horizontal and vertical dominoes that allow a given surrounding radius. This is a difficult question in general as deciding if a given tile set admits a tiling of the infinite plane is undecidable. But in some cases, the information we get from the dominoes admitting a surrounding of radius 1, 2, 3 or 4 is enough to conclude that the tiling can be desubstituted for instance. This is why we need to answer this question as fast as possible.

Below is the comparison in the time taken by each solver to compute all vertical and horizontal dominoes allowing a surrounding of radius 1, 2 and 3 (in less than 1000 seconds for each execution).

What is surprising at first is that the solvers that performed well in the first \(n\times n\) square experience are not the best in the second experiment computing valid dominoes. Dancing links and the MILP solver Gurobi are now the best algorithms to compute all dominoes. They are followed by picosat and cryptominisat and then glucose.

**The source code of the above comparisons**

The source code of the above comparison can be found in this Jupyter notebook. Note that it depends on the use of Glucose as a Sage optional package (#26361) and on the most recent development version of slabbe optional Sage Package.

## Wooden laser-cut Jeandel-Rao tiles

07 septembre 2018 | Catégories: sage, slabbe spkg, math | View Comments

I have been working on Jeandel-Rao tiles lately.

Before the conference Model Sets and Aperiodic Order held in Durham UK (Sep 3-7 2018), I thought it would be a good idea to bring some real tiles at the conference. So I first decided of some conventions to represent the above tiles as topologically closed disk basically using the representation of integers in base 1:

With these shapes, I created a 33 x 19 patch. With 3cm on each side, the patch takes 99cm x 57cm just within the capacity of the laser cut machine (1m x 60 cm):

With the help of David Renault from LaBRI, we went at Coh@bit, the FabLab of Bordeaux University and we laser cut two 3mm thick plywood for a total of 1282 Wang tiles. This is the result:

One may recreate the 33 x 19 tiling as follows (note that I am using
Cartesian-like coordinates, so the first list `data[0]` actually is the first
column from bottom to top):

sage: data = [[10, 4, 6, 1, 3, 3, 7, 0, 9, 7, 2, 6, 1, 3, 8, 7, 0, 9, 7], ....: [4, 5, 6, 1, 8, 10, 4, 0, 9, 3, 8, 7, 0, 9, 7, 5, 0, 9, 3], ....: [3, 7, 6, 1, 7, 2, 5, 0, 9, 8, 7, 5, 0, 9, 3, 7, 0, 9, 10], ....: [10, 4, 6, 1, 3, 8, 7, 0, 9, 7, 5, 6, 1, 8, 10, 4, 0, 9, 3], ....: [2, 5, 6, 1, 8, 7, 5, 0, 9, 3, 7, 6, 1, 7, 2, 5, 0, 9, 8], ....: [8, 7, 6, 1, 7, 5, 6, 1, 8, 10, 4, 6, 1, 3, 8, 7, 0, 9, 7], ....: [7, 5, 6, 1, 3, 7, 6, 1, 7, 2, 5, 6, 1, 8, 7, 5, 0, 9, 3], ....: [3, 7, 6, 1, 10, 4, 6, 1, 3, 8, 7, 6, 1, 7, 5, 6, 1, 8, 10], ....: [10, 4, 6, 1, 3, 3, 7, 0, 9, 7, 5, 6, 1, 3, 7, 6, 1, 7, 2], ....: [2, 5, 6, 1, 8, 10, 4, 0, 9, 3, 7, 6, 1, 10, 4, 6, 1, 3, 8], ....: [8, 7, 6, 1, 7, 5, 5, 0, 9, 10, 4, 6, 1, 3, 3, 7, 0, 9, 7], ....: [7, 5, 6, 1, 3, 7, 6, 1, 10, 4, 5, 6, 1, 8, 10, 4, 0, 9, 3], ....: [3, 7, 6, 1, 10, 4, 6, 1, 3, 3, 7, 6, 1, 7, 2, 5, 0, 9, 8], ....: [10, 4, 6, 1, 3, 3, 7, 0, 9, 10, 4, 6, 1, 3, 8, 7, 0, 9, 7], ....: [4, 5, 6, 1, 8, 10, 4, 0, 9, 3, 3, 7, 0, 9, 7, 5, 0, 9, 3], ....: [3, 7, 6, 1, 7, 2, 5, 0, 9, 8, 10, 4, 0, 9, 3, 7, 0, 9, 10], ....: [10, 4, 6, 1, 3, 8, 7, 0, 9, 7, 5, 5, 0, 9, 10, 4, 0, 9, 3], ....: [2, 5, 6, 1, 8, 7, 5, 0, 9, 3, 7, 6, 1, 10, 4, 5, 0, 9, 8], ....: [8, 7, 6, 1, 7, 5, 6, 1, 8, 10, 4, 6, 1, 3, 3, 7, 0, 9, 7], ....: [7, 5, 6, 1, 3, 7, 6, 1, 7, 2, 5, 6, 1, 8, 10, 4, 0, 9, 3], ....: [3, 7, 6, 1, 10, 4, 6, 1, 3, 8, 7, 6, 1, 7, 2, 5, 0, 9, 8], ....: [10, 4, 6, 1, 3, 3, 7, 0, 9, 7, 2, 6, 1, 3, 8, 7, 0, 9, 7], ....: [4, 5, 6, 1, 8, 10, 4, 0, 9, 3, 8, 7, 0, 9, 7, 5, 0, 9, 3], ....: [3, 7, 6, 1, 7, 2, 5, 0, 9, 8, 7, 5, 0, 9, 3, 7, 0, 9, 10], ....: [10, 4, 6, 1, 3, 8, 7, 0, 9, 7, 5, 6, 1, 8, 10, 4, 0, 9, 3], ....: [3, 3, 7, 0, 9, 7, 5, 0, 9, 3, 7, 6, 1, 7, 2, 5, 0, 9, 8], ....: [8, 10, 4, 0, 9, 3, 7, 0, 9, 10, 4, 6, 1, 3, 8, 7, 0, 9, 7], ....: [7, 5, 5, 0, 9, 10, 4, 0, 9, 3, 3, 7, 0, 9, 7, 5, 0, 9, 3], ....: [3, 7, 6, 1, 10, 4, 5, 0, 9, 8, 10, 4, 0, 9, 3, 7, 0, 9, 10], ....: [10, 4, 6, 1, 3, 3, 7, 0, 9, 7, 5, 5, 0, 9, 10, 4, 0, 9, 3], ....: [2, 5, 6, 1, 8, 10, 4, 0, 9, 3, 7, 6, 1, 10, 4, 5, 0, 9, 8], ....: [8, 7, 6, 1, 7, 5, 5, 0, 9, 10, 4, 6, 1, 3, 3, 7, 0, 9, 7], ....: [7, 5, 6, 1, 3, 7, 6, 1, 10, 4, 5, 6, 1, 8, 10, 4, 0, 9, 3]]

The above patch have been chosen among 1000 other randomly generated as the closest to the asymptotic frequencies of the tiles in Jeandel-Rao tilings (or at least in the minimal subshift that I describe in the preprint):

sage: from collections import Counter sage: c = Counter(flatten(data)) sage: tile_count = [c[i] for i in range(11)]

The asymptotic frequencies:

sage: phi = golden_ratio.n() sage: Linv = [2*phi + 6, 2*phi + 6, 18*phi + 10, 2*phi + 6, 8*phi + 2, ....: 5*phi + 4, 2*phi + 6, 12/5*phi + 14/5, 8*phi + 2, ....: 2*phi + 6, 8*phi + 2] sage: perfect_proportions = vector([1/a for a in Linv])

Comparison of the number of tiles of each type with the expected frequency:

sage: header_row = ['tile id', 'Asymptotic frequency', 'Expected nb of copies', ....: 'Nb copies in the 33x19 patch'] sage: columns = [range(11), perfect_proportions, vector(perfect_proportions)*33*19, tile_count] sage: table(columns=columns, header_row=header_row) tile id Asymptotic frequency Expected nb of copies Nb copies in the 33x19 patch +---------+----------------------+-----------------------+------------------------------+ 0 0.108271182329550 67.8860313206280 67 1 0.108271182329550 67.8860313206280 65 2 0.0255593590340479 16.0257181143480 16 3 0.108271182329550 67.8860313206280 71 4 0.0669152706817991 41.9558747174880 42 5 0.0827118232955023 51.8603132062800 51 6 0.108271182329550 67.8860313206280 65 7 0.149627093977301 93.8161879237680 95 8 0.0669152706817991 41.9558747174880 44 9 0.108271182329550 67.8860313206280 67 10 0.0669152706817991 41.9558747174880 44

I brought the \(33\times19=641\) tiles at the conference and offered to the first 7 persons to find a \(7\times 7\) tiling the opportunity to keep the 49 tiles they used. 49 is a good number since the frequency of the lowest tile (with id 2) is about 2% which allows to have at least one copy of each tile in a subset of 49 tiles allowing a solution.

A natural question to ask is how many such \(7\times 7\) tilings does there
exist? With ticket #25125 that was merged in Sage 8.3 this Spring, it is
possible to enumerate and count solutions in parallel with Knuth dancing links
algorithm. After the installation of the Sage Optional package slabbe (`sage
-pip install slabbe`), one may compute that there are 152244 solutions.

sage: from slabbe import WangTileSet sage: tiles = [(2,4,2,1), (2,2,2,0), (1,1,3,1), (1,2,3,2), (3,1,3,3), ....: (0,1,3,1), (0,0,0,1), (3,1,0,2), (0,2,1,2), (1,2,1,4), (3,3,1,2)] sage: T0 = WangTileSet(tiles) sage: T0_solver = T0.solver(7,7) sage: %time T0_solver.number_of_solutions(ncpus=8) CPU times: user 16 ms, sys: 82.3 ms, total: 98.3 ms Wall time: 388 ms 152244

One may also get the list of all solutions and print one of them:

sage: %time L = T0_solver.all_solutions(); print(len(L)) 152244 CPU times: user 6.46 s, sys: 344 ms, total: 6.8 s Wall time: 6.82 s sage: L[0] A wang tiling of a 7 x 7 rectangle sage: L[0].table() # warning: the output is in Cartesian-like coordinates [[1, 8, 10, 4, 5, 0, 9], [1, 7, 2, 5, 6, 1, 8], [1, 3, 8, 7, 6, 1, 7], [0, 9, 7, 5, 6, 1, 3], [0, 9, 3, 7, 6, 1, 8], [1, 8, 10, 4, 6, 1, 7], [1, 7, 2, 2, 6, 1, 3]]

This is the number of distinct sets of 49 tiles which admits a 7x7 solution:

sage: from collections import Counter sage: def count_tiles(tiling): ....: C = Counter(flatten(tiling.table())) ....: return tuple(C.get(a,0) for a in range(11)) sage: Lfreq = map(count_tiles, L) sage: Lfreq_count = Counter(Lfreq) sage: len(Lfreq_count) 83258

Number of other solutions with the same set of 49 tiles:

sage: Counter(Lfreq_count.values()) Counter({1: 49076, 2: 19849, 3: 6313, 4: 3664, 6: 1410, 5: 1341, 7: 705, 8: 293, 9: 159, 14: 116, 10: 104, 12: 97, 18: 44, 11: 26, 15: 24, 13: 10, 17: 8, 22: 6, 32: 6, 16: 3, 28: 2, 19: 1, 21: 1})

How the number of \(k\times k\)-solutions grows for k from 0 to 9:

sage: [T0.solver(k,k).number_of_solutions() for k in range(10)] [0, 11, 85, 444, 1723, 9172, 50638, 152244, 262019, 1641695]

Unfortunately, most of those \(k\times k\)-solutions are not extendable to a tiling of the whole plane. Indeed the number of \(k\times k\) patches in the language of the minimal aperiodic subshift that I am able to describe and which is a proper subset of Jeandel-Rao tilings seems, according to some heuristic, to be something like:

[1, 11, 49, 108, 184, 268, 367, 483]

I do not share my (ugly) code for this computation yet, as I will rather share clean code soon when times come. So among the 152244 about only 483 (0.32%) of them are prolongable into a uniformly recurrent tiling of the plane.

## slabbe-0.2.spkg released

30 novembre 2015 | Catégories: sage, slabbe spkg | View Comments

These is a summary of the functionalities present in slabbe-0.2.spkg optional
Sage package. It works on version 6.8 of Sage but will work best with sage-6.10
(it is using the new code for `cartesian_product` merged the the betas of
sage-6.10). It contains 7 new modules:

finite_word.pylanguage.pylyapunov.pymatrix_cocycle.pymult_cont_frac.pyxranking_scale.pytikz_picture.py

**Cheat Sheets**

The best way to have a quick look at what can be computed with the optional
Sage package `slabbe-0.2.spkg` is to look at the 3-dimensional Continued
Fraction Algorithms Cheat Sheets available on the arXiv since today. It
gathers a handful of informations on different 3-dimensional Continued Fraction
Algorithms including well-known and old ones (Poincaré, Brun, Selmer, Fully
Subtractive) and new ones (Arnoux-Rauzy-Poincaré, Reverse, Cassaigne).

**Installation**

sage -i http://www.slabbe.org/Sage/slabbe-0.2.spkg # on sage 6.8 sage -p http://www.slabbe.org/Sage/slabbe-0.2.spkg # on sage 6.9 or beyond

**Examples**

Computing the orbit of Brun algorithm on some input in \(\mathbb{R}^3_+\) including dual coordinates:

sage: from slabbe.mult_cont_frac import Brun sage: algo = Brun() sage: algo.cone_orbit_list((100, 87, 15), 4) [(13.0, 87.0, 15.0, 1.0, 2.0, 1.0, 321), (13.0, 72.0, 15.0, 1.0, 2.0, 3.0, 132), (13.0, 57.0, 15.0, 1.0, 2.0, 5.0, 132), (13.0, 42.0, 15.0, 1.0, 2.0, 7.0, 132)]

Computing the invariant measure:

sage: fig = algo.invariant_measure_wireframe_plot(n_iterations=10^6, ndivs=30) sage: fig.savefig('a.png')

Drawing the cylinders:

sage: cocycle = algo.matrix_cocycle() sage: t = cocycle.tikz_n_cylinders(3, scale=3) sage: t.png()

Computing the Lyapunov exponents of the 3-dimensional Brun algorithm:

sage: from slabbe.lyapunov import lyapunov_table sage: lyapunov_table(algo, n_orbits=30, n_iterations=10^7) 30 succesful orbits min mean max std +-----------------------+---------+---------+---------+---------+ $\theta_1$ 0.3026 0.3045 0.3051 0.00046 $\theta_2$ -0.1125 -0.1122 -0.1115 0.00020 $1-\theta_2/\theta_1$ 1.3680 1.3684 1.3689 0.00024

**Dealing with tikzpictures**

Since I create lots of tikzpictures in my code and also because I was unhappy
at how the `view` command of Sage handles them (a tikzpicture is not a math
expression to put inside dollar signs), I decided to create a class for
tikzpictures. I think this module could be useful in Sage so I will propose
its inclusion soon.

I am using the standalone document class which allows some configurations like the border:

sage: from slabbe import TikzPicture sage: g = graphs.PetersenGraph() sage: s = latex(g) sage: t = TikzPicture(s, standalone_configs=["border=4mm"], packages=['tkz-graph'])

The `repr` method does not print all of the string since it is often very
long. Though it shows how many lines are not printed:

sage: t \documentclass[tikz]{standalone} \standaloneconfig{border=4mm} \usepackage{tkz-graph} \begin{document} \begin{tikzpicture} % \useasboundingbox (0,0) rectangle (5.0cm,5.0cm); % \definecolor{cv0}{rgb}{0.0,0.0,0.0} ... ... 68 lines not printed (3748 characters in total) ... ... \Edge[lw=0.1cm,style={color=cv6v8,},](v6)(v8) \Edge[lw=0.1cm,style={color=cv6v9,},](v6)(v9) \Edge[lw=0.1cm,style={color=cv7v9,},](v7)(v9) % \end{tikzpicture} \end{document}

There is a method to generates a pdf and another for generating a png. Both
opens the file in a viewer by default unless `view=False`:

sage: pathtofile = t.png(density=60, view=False) sage: pathtofile = t.pdf()

Compare this with the output of `view(s, tightpage=True)` which does not
allow to control the border and also creates a second empty page on some
operating system (osx, only one page on ubuntu):

sage: view(s, tightpage=True)

One can also provide the filename where to save the file in which case the file is not open in a viewer:

sage: _ = t.pdf('petersen_graph.pdf')

Another example with polyhedron code taken from this Sage thematic tutorial Draw polytopes in LateX using TikZ:

sage: V = [[1,0,1],[1,0,0],[1,1,0],[0,0,-1],[0,1,0],[-1,0,0],[0,1,1],[0,0,1],[0,-1,0]] sage: P = Polyhedron(vertices=V).polar() sage: s = P.projection().tikz([674,108,-731],112) sage: t = TikzPicture(s) sage: t \documentclass[tikz]{standalone} \begin{document} \begin{tikzpicture}% [x={(0.249656cm, -0.577639cm)}, y={(0.777700cm, -0.358578cm)}, z={(-0.576936cm, -0.733318cm)}, scale=2.000000, ... ... 80 lines not printed (4889 characters in total) ... ... \node[vertex] at (1.00000, 1.00000, -1.00000) {}; \node[vertex] at (1.00000, 1.00000, 1.00000) {}; %% %% \end{tikzpicture} \end{document} sage: _ = t.pdf()

## slabbe-0.1.spkg released

27 août 2014 | Catégories: sage, slabbe spkg | View Comments

These is a summary of the functionalities present in slabbe-0.1 optional Sage package. It depends on version 6.3 of Sage because it uses RecursivelyEnumeratedSet code that was merged in 6.3. It contains modules on digital geometry, combinatorics on words and more.

Install the optional spkg (depends on sage-6.3):

sage -i http://www.liafa.univ-paris-diderot.fr/~labbe/Sage/slabbe-0.1.spkg

In each of the example below, you first have to import the module once and for all:

sage: from slabbe import *

To construct the image below, make sure to use tikz package so that `view` is
able to compile tikz code when called:

sage: latex.add_to_preamble("\\usepackage{tikz}") sage: latex.extra_preamble() '\\usepackage{tikz}'

# Draw the part of a discrete plane

sage: p = DiscretePlane([1,pi,7], 1+pi+7, mu=0) sage: d = DiscreteTube([-5,5],[-5,5]) sage: I = p & d sage: I Intersection of the following objects: Set of points x in ZZ^3 satisfying: 0 <= (1, pi, 7) . x + 0 < pi + 8 DiscreteTube: Preimage of [-5, 5] x [-5, 5] by a 2 by 3 matrix sage: clip = d.clip() sage: tikz = I.tikz(clip=clip) sage: view(tikz, tightpage=True)

# Draw the part of a discrete line

sage: L = DiscreteLine([-2,3], 5) sage: b = DiscreteBox([0,10], [0,10]) sage: I = L & b sage: I Intersection of the following objects: Set of points x in ZZ^2 satisfying: 0 <= (-2, 3) . x + 0 < 5 [0, 10] x [0, 10] sage: I.plot()

# Double square tiles

This module was developped for the article on the combinatorial properties of double square tiles written with Ariane Garon and Alexandre Blondin Massé [BGL2012]. The original version of the code was written with Alexandre.

sage: D = DoubleSquare((34,21,34,21)) sage: D Double Square Tile w0 = 3032321232303010303230301012101030 w4 = 1210103010121232121012123230323212 w1 = 323030103032321232303 w5 = 101212321210103010121 w2 = 2321210121232303232123230301030323 w6 = 0103032303010121010301012123212101 w3 = 212323032321210121232 w7 = 030101210103032303010 (|w0|, |w1|, |w2|, |w3|) = (34, 21, 34, 21) (d0, d1, d2, d3) = (42, 68, 42, 68) (n0, n1, n2, n3) = (0, 0, 0, 0) sage: D.plot()

sage: D.extend(0).extend(1).plot()

We have shown that using two invertible operations (called SWAP and TRIM), every double square tiles can be reduced to the unit square:

sage: D.plot_reduction()

The reduction operations are:

sage: D.reduction() ['SWAP_1', 'TRIM_1', 'TRIM_3', 'SWAP_1', 'TRIM_1', 'TRIM_3', 'TRIM_0', 'TRIM_2']

The result of the reduction is the unit square:

sage: unit_square = D.apply(D.reduction()) sage: unit_square Double Square Tile w0 = w4 = w1 = 3 w5 = 1 w2 = w6 = w3 = 2 w7 = 0 (|w0|, |w1|, |w2|, |w3|) = (0, 1, 0, 1) (d0, d1, d2, d3) = (2, 0, 2, 0) (n0, n1, n2, n3) = (0, NaN, 0, NaN) sage: unit_square.plot()

Since SWAP and TRIM are invertible operations, we can recover every double square from the unit square:

sage: E = unit_square.extend(2).extend(0).extend(3).extend(1).swap(1).extend(3).extend(1).swap(1) sage: D == E True

# Christoffel graphs

This module was developped for the article on a d-dimensional extension of Christoffel Words written with Christophe Reutenauer [LR2014].

sage: G = ChristoffelGraph((6,10,15)) sage: G Christoffel set of edges for normal vector v=(6, 10, 15) sage: tikz = G.tikz_kernel() sage: view(tikz, tightpage=True)

# Bispecial extension types

This module was developped for the article on the factor complexity of infinite sequences genereated by substitutions written with Valérie Berthé [BL2014].

The extension type of an ordinary bispecial factor:

sage: L = [(1,3), (2,3), (3,1), (3,2), (3,3)] sage: E = ExtensionType1to1(L, alphabet=(1,2,3)) sage: E E(w) 1 2 3 1 X 2 X 3 X X X m(w)=0, ordinary sage: E.is_ordinaire() True

Creation of a strong-weak pair of bispecial words from a neutral
**not ordinaire** word:

sage: p23 = WordMorphism({1:[1,2,3],2:[2,3],3:[3]}) sage: e = ExtensionType1to1([(1,2),(2,3),(3,1),(3,2),(3,3)], [1,2,3]) sage: e E(w) 1 2 3 1 X 2 X 3 X X X m(w)=0, not ord. sage: A,B = e.apply(p23) sage: A E(3w) 1 2 3 1 2 X X 3 X X X m(w)=1, not ord. sage: B E(23w) 1 2 3 1 X 2 3 X m(w)=-1, not ord.

# Fast Kolakoski word

This module was written for fun. It uses cython implementation inspired from the 10 lines of C code written by Dominique Bernardi and shared during Sage Days 28 in Orsay, France, in January 2011.

sage: K = KolakoskiWord() sage: K word: 1221121221221121122121121221121121221221... sage: %time K[10^5] CPU times: user 1.56 ms, sys: 7 µs, total: 1.57 ms Wall time: 1.57 ms 1 sage: %time K[10^6] CPU times: user 15.8 ms, sys: 30 µs, total: 15.8 ms Wall time: 15.9 ms 2 sage: %time K[10^8] CPU times: user 1.58 s, sys: 2.28 ms, total: 1.58 s Wall time: 1.59 s 1 sage: %time K[10^9] CPU times: user 15.8 s, sys: 12.4 ms, total: 15.9 s Wall time: 15.9 s 1

This is much faster than the Python implementation available in Sage:

sage: K = words.KolakoskiWord() sage: %time K[10^5] CPU times: user 779 ms, sys: 25.9 ms, total: 805 ms Wall time: 802 ms 1

# References

[BGL2012] | A. Blondin Massé, A. Garon, S. Labbé, Combinatorial properties
of double square tiles, Theoretical Computer Science 502 (2013) 98-117.
doi:10.1016/j.tcs.2012.10.040 |

[LR2014] | Labbé, Sébastien, and Christophe Reutenauer. A d-dimensional Extension of Christoffel Words. arXiv:1404.4021 (April 15, 2014). |

[BL2014] | V. Berthé, S. Labbé, Factor Complexity of S-adic sequences generated by the Arnoux-Rauzy-Poincaré Algorithm. arXiv:1404.4189 (April, 2014). |

## Releasing slabbe, my own Sage package

27 août 2014 | Catégories: sage, slabbe spkg | View Comments

Since two years I wrote thousands of line of private code for my own research. Each module having between 500 and 2000 lines of code. The code which is the more clean corresponds to code written in conjunction with research articles. People who know me know that I systematically put docstrings and doctests in my code to facilitate reuse of the code by myself, but also in the idea of sharing it and eventually making it public.

I did not made that code into Sage because it was not mature enough. Also, when I tried to make a complete module go into Sage (see #13069 and #13346), then the monstrous never evolving #12224 became a dependency of the first and the second was unofficially reviewed asking me to split it into smaller chunks to make the review process easier. I never did it because I spent already too much time on it (making a module 100% doctested takes time). Also, the module was corresponding to a published article and I wanted to leave it just like that.

**Getting new modules into Sage is hard**

In general, the introduction of a complete new module into Sage is hard especially for beginners. Here are two examples I feel responsible for: #10519 is 4 years old and counting, the author has a new work and responsabilities; in #12996, the author was decouraged by the amount of work given by the reviewers. There is a lot of things a beginner has to consider to obtain a positive review. And even for a more advanced developper, other difficulties arise. Indeed, a module introduces a lot of new functions and it may also introduce a lot of new bugs... and Sage developpers are sometimes reluctant to give it a positive review. And if it finally gets a positive review, it is not available easily to normal users of Sage until the next release of Sage.

**Releasing my own Sage package**

Still I felt the need around me to make my code public. But how? There are people (a few of course but I know there are) who are interested in reproducing computations and images done in my articles. This is why I came to the idea of releasing my own Sage package containing my public research code. This way both developpers and colleagues that are user of Sage but not developpers will be able to install and use my code. This will make people more aware if there is something useful in a module for them. And if one day, somebody tells me: "this should be in Sage", then I will be able to say : "I agree! Do you want to review it?".

**Old style Sage package** vs **New sytle git Sage package**

Then I had to chose between the old and the new style for Sage packages. I did not like the new style, because

- I wanted the history of my package to be independant of the history of Sage,
- I wanted it to be as easy to install as
sage -i slabbe,- I wanted it to work on any recent enough version of Sage,
- I wanted to be able to release a new version, give it to a colleague who could install it right away without changing its own Sage (i.e., updating the checksums).

Therefore, I choose the old style. I based my work on other optional Sage packages, namely the SageManifolds spkg and the ore_algebra spkg.

**Content of the initial version**

The initial version of the slabbe Sage package has modules concerning four
topics: *Digital geometry*, *Combinatorics on words*, *Combinatorics* and
*Python class inheritance*.

For installation or for release notes of the initial version of the spkg, consult the slabbe spkg section of the Sage page of this website.