#balisebooks – Foundation / Fondation – Isaac Asimov

Post original :
https://plus.google.com/106223694077555758612/posts/ivUf3P3dBm8

J’ai un problème avec Fondation. Je me considère fan d’Asimov, et j’ai jamais réussi à finir Fondation. C’est pire que ça : jusqu’à la semaine dernière, j’avais jamais fini le premier TOME de Fondation. Pas que j’avais pas essayé, j’ai dû commencé à le lire 4 ou 5 fois ces 12 dernières années.

Ça m’agace, parce que Fondation est souvent considéré comme LE cycle d’Asimov, voire de la science-fiction en général. Du coup, j’ai l’impression de louper un truc.

Fondation est l’histoire de la chute de l’Empire galactique et de la manière d’en atténuer les conséquences. Je pense que ce qui m’a le plus perturbée lors de mes premières tentatives est que les cinq parties du bouquin ont peu à voir les unes avec les autres, qu’elles sont séparées par une longue période de temps sans que ça ne soit explicite immédiatement, et qu’il n’y a presque pas de personnage commun entre les parties (un personnage dans une partie est parfois devenu limite un mythe dans la suivante). Pour moi, c’est source de confusion et d’agacement – ça m’énerve d’avoir un vague aperçu d’un personnage et *pouf* il disparaît dans la partie suivante. Bon, une fois qu’on a pigé la structure générale, ça va mieux.

J’ai aussi appris, en faisant un peu de méta-lecture, que Fondation avait été à l’origine publié comme nouvelles individuelles (en particulier dans Astounding). Je crois que j’aurais apprécié une note de l’éditeur sur ce point au début du livre.

Bon, j’ai fini le premier, qu’est-ce que j’en fais ? Je suis pas convaincue que je vais continuer. Je veux dire, objectivement, c’est bien, et je peux voir l’attrait de ce machin épique où on a l’impression de voir l’Histoire s’écrire. Mais je crois que… ben c’est pas ma came, quoi. J’ai toujours un peu l’impression de louper un truc, mais au moins j’ai fait ma paix avec ça. Il est pas impossible que ça finisse par m’énerver à l’avenir et que je me dise que le deuxième (ou le troisième, ou…) tome est différent et que je loupe effectivement quelque chose, mais on verra quand/si le problème se présente(ra) 🙂

#balisebooks – The Time-Traveling Fashionista / Une robe couleur du temps – Bianca Turetsky

(Tiens, j’avais oublié de traduire celui-ci hier. Le post original :
https://plus.google.com/106223694077555758612/posts/Xc36ULnW57y )

Bon, je crois que The Time-Traveling Fashonista (traduit en français sous le titre Une robe couleur du temps, c’est bien trouvé, d’ailleurs, enfin j’aime bien) est un exemple typique de « mon libraire a pas bien fait son boulot ». Je veux dire par là qu’il y a une petite section anglaise à la librairie en question, et que ladite section est divisée en quatre : littérature « générale », SF/Fantasy/Thrillers, non-fiction (ça se dit, ça en français ?) et littérature jeunesse. Ce livre était dans la partie littérature générale, et même mis en avant dans ladite section, mais la cible est clairement les 8-12 ans. Enfin bref, je l’avais, je l’ai lu 😉 (Et je serai plus prudente la prochaine fois que j’irai dans cette librairie).

C’est l’histoire de Louise, qui a 12 ans et une passion pour la mode « vintage » (*tousse*crédible*tousse*) et est invitée à une vente privée de mode vintage (*tousse*crédible*tousse*) (Bon, je plaisante sur le coup de la crédibilité. Je veux dire, le Club des 5, c’était pas des plus crédibles non plus. Mais c’était (c’est) bien quand même.) Louise essaye une robe, tombe dans les pommes, et se retrouve… sur le Titanic. Et, heu… c’est à peu près tout 🙂

Je dois admettre que c’était plutôt choupi et que les illustrations étaient jolies. Je ne suis pas sûre de ce que j’attendais en prenant ce bouquin, probablement pas un truc très profond, mais du fait que j’étais vraiment pas dans la cible, j’ai été un peu déçue. Probablement pas mal pour la cible considérée, cela dit.

#balisebooks – L’Affaire Jane Eyre – Jasper Fforde

Je viens de finir l’Affaire Jane Eyre, premier livre de la série des Thursday Next (qui est le nom de l’héroïne). L’histoire se déroule dans un univers parallèle où la guerre de Crimée est toujours en cours, où les gens voyagent en ballon dirigeable, où les dodos clonés sont des animaux de compagnie et où la littérature classique a une popularité énorme. Il existe même une division de la police (les SpecOps) qui s’occupe des crimes littéraires – manuscrits volés, contrefaçons et autres. Thursday fait partie de cette division et se retrouve à la poursuite d’Acheron Hades, qui commence par tuer un personnage mineur du Martin Chuzzlewit de Dickens et finit par kidnapper Jane Eyre du roman éponyme de Brontë.

J’ai beaucoup aimé. C’était suffisamment débile pour me faire rire, mais pas assez pour me faire perdre le fil de l’histoire. J’ai bien aimé l’univers et le groupe de personnages, et maintenant j’ai envie de relire Jane Eyre. Et de lire les Thursday Next suivants 🙂

#balisebooks – Outliers – Malcolm Gladwell

Post original :
https://plus.google.com/u/0/106223694077555758612/posts/iThAJA8pD7P

Je viens de finir Outliers, de Malcolm Gladwell (pas de traduction française à ma connaissance) et j’ai un avis assez ambigu sur l’ensemble. La thèse du bouquin est que le succès n’est pas une question de talent extraordinaire, mais d’un talent « suffisant » associé aux bonnes circonstances et à une quantité énorme de travail. Jusqu’ici, tout va bien; pourquoi pas.

Gladwell est très bon lorsqu’il s’agit de raconter des anecdotes, des histoires marrantes et assimilé. Il est drôle, engageant, ses exemples sont bien choisis et en général très intéressants (notons au passage que, à mon avis, What The Dog Saw est meilleur de ce point de vue).

Il est aussi très bon lorsqu’il s’agit de faire réfléchir son lecteur et de tenter de le faire regarder des histoires « classiques » au-delà de ce qui en est habituellement dit – il donne des informations supplémentaires et on finit par se demander ce qui, au final, est réellement pertinent (probablement tout, dans une certaine mesure).

Ce qui m’a par contre franchement agacée était le sentiment tenace de « oui, bon, tu essaies de me montrer des stats, mais tu essaierais pas de me pipoter, là, par hasard ? ». Je ne sais absolument pas si ses stats sont valides ou non. Mais, de la manière dont elles sont présentées dans le livre, elles tiennent plus de l’anecdotique et du sophisme du tireur d’élite texan (l’article anglais de la Wikipédia est plus complet… mais en anglais 😉 ). Encore une fois, je ne dis pas que les faits sont faux ; je dis juste qu’après avoir lu le livre, je ne sais pas s’ils sont vrais ou faux. Très agaçant.

Bref, au final, c’est un bouquin que j’ai apprécié (à cause des anecdotes rigolotes) mais qui m’a fondamentalement énervée sur le plan statistique/scientifique. Et je suis nulle en stats. Donc… ouais… mitigée.

Dominion

Bon, continuons dans les jeux qui commencent à avoir quelques années mais qu’on découvre seulement maintenant… (Vous plaignez pas, j’ai fait ma première partie de Catan ya pas quinze jours trois semaines (j’ai mis plus de temps que prévu à écrire ce billet)) – aujourd’hui, je cause de Dominion, édité à l’origine par Rio Grande Games et en France par Filosofia (et on en a une version en anglais).

Dominion se joue de deux à quatre joueurs et se joue avec des cartes ; dans la boîte de base il y a 500 cartes, divisées en plusieurs catégories. Les trois catégories « principales » sont les cartes d’action, les cartes de trésor (treasure) et les cartes de victoire (victory). Le but du jeu est d’obtenir, à la fin du jeu, un maximum de points de victoire. Les cartes d’action sont divisées en plusieurs catégories (suivant leur coût et les actions quelles permettent) ; les cartes de trésor et les cartes de victoire peuvent être de trois types différents, là encore, avec différentes valeurs et différents coûts.

C’est un jeu de « construction de deck » : tous les joueurs partent avec le même paquet de cartes et achètent des cartes à chaque tour pour constituer leur deck (paquet de cartes, donc). Un tour de joueur se compose de trois phases : une phase d’action (où le joueur peut… jouer des cartes action), une phase d’achat (où le joueur peut… acheter des cartes (je sais, fou) ) et une phase de nettoyage/rangement des cartes jouées (ou non).

Plus spécifiquement, à chaque tour, un joueur tire 5 cartes de son deck pour constituer une main. Cette main se compose de cartes « trésor » avec lesquelles il peut acheter des choses, de cartes « action » avec lesquelles il peut faire des choses, et de cartes « victory » avec lesquelles il ne peut rien faire (mais qui comptent pour le score final). Par défaut, un joueur a droit à une action et un achat. Les cartes action permettent entre autres d’augmenter le nombre d’actions possibles, de tirer de nouvelles cartes, d’augmenter le nombre d’achats possibles, et de bénéficier, pour un tour donné, d’argent supplémentaire. En pratique, le jeu marche avec des « combos » – des combinaisons de cartes qui se trouvent bien marcher ensemble. Par exemple, poser une carte Village donne deux actions supplémentaires ; poser une carte Smithy (forgeron) permet de tirer trois cartes ; le combo « village-smithy-village-smithy-et maintenant on commence les trucs vraiment intéressants (ou on a plein de pognon en main pour acheter des trucs chers) » s’est retrouvé assez souvent dans les parties qu’on a faites jusqu’à présent. Une fois toutes les opérations (actions et achats) effectuées, le joueur se défausse de ses cartes, y compris celles qui restent dans sa main. (Il remélange son deck lorsqu’il n’a plus de cartes à tirer).

Évidemment, l’astuce c’est que les cartes de victoire ne permettent rien. Du coup, si on achète trop de cartes de victoire dès le début, le deck se retrouve inutilisable – et en particulier ne permet plus d’acheter plus de cartes de victoire. Inversement, il faut quand même finir par acheter lesdites cartes de victoire, puisqu’elles déterminent à elles seules le gagnant du jeu.

Le jeu est intéressant à deux, probablement un peu plus à trois ou quatre, mais clairement très jouable à deux (le fait qu’il y ait finalement assez peu d’interactions entre les joueurs doit aider). Je suis pas sûre que la limite de quatre joueurs soit « dure » (i.e. si l’ajout d’un cinquième joueur détruit vraiment la balance du truc), mais on n’a pas essayé. Les tours sont très rapides et une partie dure de l’ordre d’une demi-heure. Il est aussi facile à « prendre en main » pour les nouveaux joueurs ; les explications peuvent être confuses (je crois que j’ai bien réussi, là) (à les rendre confuses, je veux dire), mais après deux ou trois tours de jeu ça roule tout seul.

Pour finir, notons que la boîte de base contient 25 types de cartes différents, et qu’une partie n’en utilise que 10 (soit des jeux pré-tirés, soit des jeux aléatoires). Soit, techniquement, plus de 3 millions de combinaisons différentes, mais certaines doivent être moins intéressantes que d’autres et beaucoup doivent se ressembler en pratique 😉 Il existe aussi de nombreuses extensions… mais bon, on va peut-être essayer de jouer avec toutes les cartes avant de regarder les extensions !

Annonce de service : RSS Google+

Ce post est purement informatif pour les gens qui aiment bien les RSS (moi), qui veulent voir les conneries (le plus souvent en anglais) que je raconte sur Google+ en public et qui ont quelque chose contre le fait que Google+ soit accessible essentiellement uniquement avec l’interface web de Google+ (et une API qui arrête pas de faire les pieds au mur, il paraît).

Je viens de mettre en place un flux RSS de mon G+ public chez un gens qui s’appelle gplusrss.com ; faites-en bon usage (ou pas). Ça marchera le temps que ça marchera avec la qualité de service que ça a, mais c’est censé marcher pour l’instant. Voilà.

Fin de l’annonce de service à caractère égocentrique.

Random insomniac thoughts about sudoku, CSPs and SAT

(Writing in English because for some reason (probably the fact that my courses on the subject are in English) my inner monologue is in English on this subject, so…)

This post will probably be fairly obscure to… err… I’d say anyone but me, but that would be kind of pretentious 😉 Let’s just say that if you haven’t heard the acronyms SAT or CSP before, you can probably skip this post, unless you’re very curious. If you have questions, remarks, don’t hesitate. I have no idea what I’m doing either.

Last night I did some Project Euler problems before going to bed, and I inadvertantly clicked on this one: Problem 96 – Devise an algorithm for solving Su Doku puzzles. And while I know that I shouldn’t go to bed with a problem I’m able to easily formulate in my head, I did anyway (because it was late), and an hour or two of mild insomnia followed, because I was thinking of said problem. Typical. Or, as I put it a while ago, « don’t derive and try to sleep ».

This is a collection of random thoughts on the subject; I obviously didn’t give it A LOT of thought, it’s more of a general interrogation post, because I think the exercise in itself isn’t bad. Also, I haven’t hit the litterature at all – so there’s a fair chance I’m only saying stuff that’s either trivial, stupid or wrong 😉

The problem of regular 9×9 sudoku, per se, is « easy ». Well, it’s not « easy » in that I’d probably need some hours of thought and a some hours of sweat implementing it, but I’m pretty confident I could get there, at least for a decent approximation of a decent algorithm. But anything I’m saying from now on doesn’t have anything to do with the question of solving a given 9×9 sudoku in a « reasonable » amount of time – I’m only interested in the « theoretical » problem.

What’s not obvious to me is the « best » way to model and solve the associated CSP or SAT instance. Again, for a « regular » sudoku, one could argue that the size of the problem is constant and that the « best » way to model and solve doesn’t matter much since it will also be constant. However, since I’m (originally) interested in solving the Project Euler question, the size of the constant actually matters to me – if it’s « gazillions », it’s not good enough for me. Moreover, the Sudoku problem for nxn problems is known to be NP-complete (haven’t read that paper yet, intend to). Also note that I’m not that interested in the decision problem (« is there a solution to this instance of sudoku ») but in finding an assignment that actually solves said puzzle.

There are two straightforward ways to model sudoku:

  • as a regular CSP problem, where each variable represents a cell and can take a value between 1 and n.
  • as a SAT problem where we define n boolean variables for each cell, each of which saying « does this cell take this value? »

A priori, both models have their merits; the CSP has the advantage of compactness and (human) readability, and the SAT has the advantage of being boolean (duh). Note that in any case, any nxn problem can be modelled in same way (by expressing the constraints of the grid, which is very regular), and the particular instance of the puzzle can be seen as an initial partial assignment on the problem (which will remove some constraints and some variables in some constraints). I’m not entirely clear on the number of constraints in both cases, I’d need some time with a pen and paper for that. Also, considering a SAT problem, the exact number of variables in a « reasonable » 3SAT reduction would need some work also. Probably not « hard » work, but « careful » work (and I’m not that good at careful 😉 ).

Now if I consider that I have a model, what are my options? (Again, this is a worst-case analysis – there’s a fair chance that most « real-world » puzzles won’t need that kind of machinery, but some instances ARE hard (the problem IS NP-complete). But by the way, what makes an « easy » sudoku puzzle, and is it possible to decide whether a given instance is easy or not? Anyway, for the general case, the three possibilities that I’m thinking of right now are randomized algorithms, so any runtime I’m talking about is expected runtime.

  • Apply PPSZ (beware, it bites) to the (3-)SAT problem. A bound on the runtime here would be 1.308^k, where k is the number of variables that I haven’t computed yet.
  • Use a PPZ-like approach on the CSP instance – consider a random permutation of the variables and treat them in order; pick, for each variable, a value uniformly at random in those that are not forbidden by the current partial assignment.
  • Use a « random downsampling » approach (for each cell, keep two values uniformly at random) and apply PPZ to the resulting instance.

Those two last approaches were part of an exercise in the latest SAT graded sheet I (tried to) solve(d), so I have some idea on how the analysis would go through in that case. It would still need some work, obviously (especially since the problem is slightly different).

Another question is, since the problem is very structured, can I use this structure to my advantage to make the algorithm faster, prove that the general algorithm is faster in this particular setting, or to get an easier analysis?

Still in the « random questions » – sudoku can be seen as the problem of « rainbow coloring » a n-regular hypergraph where each vertex is part of exactly 3 edges. How would previous algorithms behave on a more general case? (non n-regular and/or with an arbitrary number of edges per vertex). This kind of reflexion gives me the intuition that indeed, the structure of the problem can be used to get better algorithms and/or bounds. But I may obviously be wrong.

Last one, and then I’m leaving you 😉 – this is a more general question regarding SAT vs CSP. SAT domains and constraints and stuff can be represented in a hypercube where every possible assignment is a vertex and two vertices are connected iff there differ by exactly one coordinate. The hypercube model is a nice way to look at the SAT problem from a different perspective, and definitely has its uses. Is there any geometrical structure that would be useful in the same way (or in some way) for CSPs and variables whose domain is not reduced to 2 boolean values?