Month: May 2020

Maquereaux et départements

Cette semaine, l’énigme “classique” de FiveThirtyEight (qu’on peut retrouver ici) demande de trouver des mots n’ayant aucune lettre en commun avec un et seul état américain. Par exemple, “mackerel” (le maquereau) a des lettres en commun avec tous les états sauf l’Ohio.

Ce problème peut s’adapter au cas français : quels sont les mots n’ayant aucune lettre en commun avec un et un seul département français ?

En reprenant la liste de mots utilisés pour notre article sur Motus et sur “Des Chiffres et des Lettres”, qui sont de 10 lettres au maximum (selon les règles des jeux), on trouve plus de 15 000 mots qui répondent à notre définition ! L’un d’entre eux est d’ailleurs “MAQUEREAUX”, qui partage (au moins) une lettre en commun avec tous les départements, sauf le Lot.

C’est d’ailleurs ce département qui est le plus souvent à l’origine de la présence des mots dans la liste ; c’est assez logique, car il ne contient ni A, ni E, ni I (lettres qui sont très présentes dans les autres départements), et ne contient que trois lettres.

En utilisant le dictionnaire Lexique, on peut chercher parmi des mots de plus de 10 lettres ceux qui répondent à notre définition. Le mot le plus long répondant à la définition est alors MULTIDIMENSIONNELLE, avec 19 lettres, grâce au département du Var.

Il est possible d’aller plus loin, si l’on accepte de compter tous les caractères des mots et non uniquement les lettres. Dans ce cas, avec 22 signes, le mot répondant à la définition est SUIVEZ-MOI-JEUNE-HOMME (oui, ce mot existe ; non, aucun lien avec les autres maquereaux) car il n’a aucune lettre en commun avec le Gard.

Comment trouver ces mots : description de l’algorithme

Le programme permettant de trouver les mots satisfaisant à la condition demandée (aucune lettre en commun avec un et un seul département) se décompose en plusieurs étapes.

Tout d’abord, on construit des matrices (des tableaux) dont chaque colonne est une lettre de l’alphabet et chaque ligne correspond à, soit un mot du dictionnaire, soit un département. Au croisement d’une ligne et d’une colonne se trouve une indicatrice TRUE/FALSE (qu’on recodera 1/0 après) indiquant si oui ou non la lettre se trouve dans le mot concerné. Pour cela, on utilise la fonction str_detect du package stringR.

sapply(LETTERS,FUN=str_detect,string="AIN")
A     B     C     D     E     F     G     H     I     J     K     L     M     N     O     P 
TRUE FALSE FALSE FALSE FALSE FALSE FALSE FALSE TRUE FALSE FALSE FALSE FALSE TRUE FALSE FALSE 
Q     R     S     T     U     V     W     X     Y     Z 
FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE

On a ainsi construit un tableau pour le dictionnaire tableau_dico et un tableau pour les départements tableau_dep. La commande suivante va calculer pour chaque mot du dictionnaire le nombre de département ne partageant aucune lettre en commun.

f <- function(x,ajout) {
  return(max(x + ajout))
}

sum(apply(tableau_dep,MARGIN = 1,f,ajout=tableau_dico[mot,]) == 1))

En décomposant un peu le code :

  • la fonction f construite ici prend deux vecteurs x et ajout et calcule le maximum de la somme des deux vecteurs ;
  • ici, ces deux vecteurs sont la ligne de tableau_dico associée au mot choisi et une ligne de tableau_dep, soit des vecteurs de 0 et 1 suivant si les lettres appartiennent aux mots considérés ;
  • f peut ici renvoyer 1 ou 2 : s’il renvoie 1, cela veut dire qu’il n’y a aucune lettre en commun, sinon, la valeur associée à cette lettre serait de 2, car somme de 1 et 1 dans chacun de deux vecteurs, et donc f calculerait un maximum de 2 ;
  • on applique cette fonction à l’ensemble des départements dans tableau_dep (apply avec le choix de margin=1 pour indiquer que l’on travaille sur les lignes) ;
  • on compte alors le nombre de départements pour lesquels cette sortie est 1.

Une fois qu’on a appliqué cette commande à l’ensemble des mots du dictionnaire, on peut enfin isoler les “maquereaux” en filtrant sur ceux pour lesquels le nombre de départements n’ayant aucune lettre en commun est exactement de 1.

Image : Atlantic mackerels (Petar Milošević)

Rolling some dices

Today, a quick post trying to provide an answer to this week Riddle Classic on FiveThirtyEight :

The fifth edition of Dungeons & Dragons introduced a system of “advantage and disadvantage.” When you roll a die “with advantage,” you roll the die twice and keep the higher result. Rolling “with disadvantage” is similar, except you keep the lower result instead. The rules further specify that when a player rolls with both advantage and disadvantage, they cancel out, and the player rolls a single die. Yawn!

There are two other, more mathematically interesting ways that advantage and disadvantage could be combined. First, you could have “advantage of disadvantage,” meaning you roll twice with disadvantage and then keep the higher result. Or, you could have “disadvantage of advantage,” meaning you roll twice with advantage and then keep the lower result. With a fair 20-sided die, which situation produces the highest expected roll: advantage of disadvantage, disadvantage of advantage or rolling a single die?

Extra Credit: Instead of maximizing your expected roll, suppose you need to roll N or better with your 20-sided die. For each value of N, is it better to use advantage of disadvantage, disadvantage of advantage or rolling a single die?

This problem is quite similar to some issues we’ve already tackled on this website, such as Tennis vs Badminton, or archery points (FR), or even how Eurovision rules impacts french rankings (FR). In order to answer we’re going to use simulations with R. The main set of functions needed is described here:

dice <- function() {return(sample(1:20,1))}

advantage <- function() {
  a <- dice()
  b <- dice()
  return(max(a,b))
} 

disadvantage <- function() {
  a <- dice()
  b <- dice()
  return(min(a,b))
} 

disadvantage_of_advantage <- function() {
   a <- advantage()
   b <- advantage()
   return(min(a,b))
 }

advantage_of_disadvantage <- function() {
   a <- disadvantage()
   b <- disadvantage()
   return(max(a,b))
 }

Then, we just need to simulate a fair amount (say, n = 10 000 or 100 000) of every dice rolling method. The first question to answer is: how to get the best rolls on average? The following graph answers it nicely, showing that the “disadvantage of advantage” method leads to better results than just rolling a dice, and even better ones than “advantage of disadvantage”.

Will this method be efficient for the other problem, which is maximising our chances to roll a value higher than a set threshold (resulting in harming the dragon, for instance, instead of failing miserably in our attempt)? The answer is yes… but only for lower values of the threshold!

As shown by the graph, as long as the threshold is 14 or higher (and killing a dragon might be that hard!), it’s better to just roll a dice. Why? That’s because our advantage and disadvantage modifiers tend to concentrate the distributions of values obtained: getting a 20 on “disadvantage of advantage” means that you need to get a 20 on both previous rollings with advantage, meaning that you need at least one 20 during each one ; this is extremly unlikely!

Eurovision 2020 – « prédictions »

L’Eurovision 2020, comme bon nombre d’événements culturels et sportifs, n’aura pas lieu cette année, pour cause de pandémie. Les chansons proposées par les pays participants ont néanmoins été mises en ligne : on peut les retrouver ici.

Même si cela n’a aucun intérêt (personne ne gagnera un concours qui n’aura pas lieu), il est donc possible de mettre en oeuvre notre modèle de prédictions (comme les années précédentes, en 2018 et 2019) utilisant les données associées à chaque vidéo sur Youtube : nombre de vues, “likes” – pouces vers le haut, “dislikes” – pouces vers le bas.

Le modèle utilise les données (Youtube et résultats lors du concours) pour les années précédentes et prédit ensuite le score qu’obtiendrait chaque pays. L’idée est que le nombre de personnes regardant un clip en ligne (et leurs réactions, via les boutons dédiés de Youtube) est un bon moyen de prédire le succès d’une chanson à l’Eurovision ; c’est évidemment très limité et ce pour de nombreuses raisons : existence d’un double vote (public et jury), différences entre les clips et la prestation en live, etc.

Passons donc aux « résultats » : our twelve points go to… la Russie !

En effet, comme en 2018 avec Israël, leur vidéo est un outlier (une observation avec des caractéristiques très différentes des autres) qui récolte plus de 85 millions de vues largement supérieur aux autres ; il s’agit de la chanson “Uno”, que vous pouvez (et je vous y encourage) écouter ci-après :

Sans surprise, ce sont donc eux qui sont les favoris pour notre modèle ! Le reste du top 5 (avec beaucoup moins d’écarts et donc de certitude) se compose de l’Arménie, l’Azerbaïdjan, l’Ukraine et la Bulgarie.

On peut comparer ces résultats (à défaut de ne jamais pouvoir savoir si le modèle aurait eu raison !) avec ceux des bookmakers (voir ici), évidemment gelés depuis l’annonce de l’annulation du concours. Ils ne plaçaient pas la Russie en premier, mais dans les cinq favoris néanmoins.