Génération de puzzle de recherche de mots

13

À partir d'une liste de chaînes, recherchez la plus petite matrice carrée qui contient chacune des chaînes initiales. Les chaînes peuvent apparaître horizontalement, verticalement ou en diagonale et en avant ou en arrière comme dans cette question Puzzle de recherche de mots .

Les mots doivent être placés dans le carré, avec au moins un mot dans chaque direction (horizontal, vertical et diagonal). Les mots ne doivent apparaître qu'une seule fois.

Ainsi, l'entrée n'est qu'une liste de mots. Par exemple: CAT, TRAIN, CUBE, BICYCLE. Une solution possible est:

B N * * * * *
* I * * C A T
* A C * * * *
* R * Y * * C
* T * * C * U
* * * * * L B
* * * * * * E

J'ai remplacé les lettres de remplissage par des astérisques juste pour plus de clarté. La sortie souhaitée doit inclure des lettres de remplissage aléatoires.

Migue
la source
Chaque mot doit-il être trouvé dans une seule position (comme les recherches de mots typiques)? Par exemple, la lettre laissée ACdans votre exemple en ferait une autre CATsi elle l'est T.
Geobits
Pour moi, ce que vous entendez exactement par "les mots doivent être placés au hasard dans toutes les directions " n'est pas clair . Une réponse répondrait-elle à ce critère si, après avoir défini les mots de façon déterministe, elle sélectionne au hasard l'une des huit symétries du carré? Ou, à l'autre extrême, la sortie doit-elle être sélectionnée uniformément parmi tous les plus petits carrés possibles qui contiennent les mots? Ou la ligne est-elle tracée quelque part entre ces extrêmes?
Peter Taylor
Oui, il ne devrait être trouvé que dans une seule position.
Migue
1
Non, pas vraiment. Je ne sais toujours pas quel est l'espace à partir duquel une réponse doit être échantillonnée au hasard, ni quelle flexibilité est autorisée dans la pondération des éléments de cet espace.
Peter Taylor
1
Pour l'instant, la question a des entrées qui ne peuvent pas être résolues, mais aucune mention n'est faite de la façon dont vous êtes censé y faire face. Par exemple, l'ensemble A B C D E F G H I J K L M N O P Q R S T U V W X Y Zn'a pas de solution.
orlp

Réponses:

6

JavaScript (ES6), 595 628 680

Modifier certains nettoyage et fusion:
- fonction P fusionnée à l'intérieur de la fonction R
- calc x et z dans le même .map
- lorsque la solution est trouvée, définissez x sur 0 pour quitter la boucle externe
- fusion définie et appel de W

Modifier2 plus de golf, remplissage aléatoire raccourci, boucle externe révisée ... voir l'historique pour quelque chose de plus lisible

Contrairement à la réponse acceptée, cela devrait fonctionner pour la plupart des entrées. Évitez simplement les mots d'une seule lettre. Si une sortie est trouvée, elle est optimale et utilise les 3 directions.

La contrainte d'éviter de répéter des mots est très difficile. J'ai dû chercher un mot répétitif à chaque étape en ajoutant un mot à la grille et à chaque caractère de remplissage aléatoire.

Sous-fonctions principales:

  • P (w) vrai si mot palindrome. Un mot palindrom sera trouvé deux fois lors de la vérification des mots répétés.

  • R (s) vérifier les mots qui se répètent sur la grille s

  • Q (s) remplit la grille s avec des caractères aléatoires - c'est récursif et retour arrière en cas de répétition de mot - et peut échouer.

  • W () récursif, essayez de remplir une grille de taille donnée, si possible.

La fonction principale utilise W () pour trouver une grille de sortie, en essayant de la taille du mot le plus long en entrée jusqu'à la somme de la longueur de tous les mots.

F=l=>{
  for(z=Math.max(...l.map(w=>(w=w.length,x+=w,w),x=0));
      ++z<=x;
      (W=(k,s,m,w=l[k])=>w?s.some((a,p)=>!!a&&
            D.some((d,j,_,r=[...s],q=p-d)=>
              [...w].every(c=>r[q+=d]==c?c:r[q]==1?r[q]=c:0)
              &&R(r)&&W(k+1,r,m|1<<(j/2))
            )
          )
        :m>12&&Q(s)&&(console.log(''+s),z=x) 
      )(0,[...Array(z*z-z)+99].map((c,i)=>i%z?1:'\n'))
    )
    D=[~z,-~z,1-z,z-1,z,-z,1,-1]
    ,R=u=>!l.some(w=>u.map((a,p)=>a==w[0]&&D.map(d=>n+=[...w].every(c=>u[q+=d]==c,q=p-d)),
      n=~([...w]+''==[...w].reverse()))&&n>0)
    ,Q=(u,p=u.indexOf(1),r=[...'ABCDEFGHIJHLMNOPQRSTUVWXYZ'])=>
      ~p?r.some((v,c)=>(r[u[p]=r[j=0|c+Math.random()*(26-c)],j]=v,R(u)&&Q(u)))||(u[p]=1):1
    //,Q=u=>u.map((c,i,u)=>u[i]=c!=1?c:' ') // uncomment to avoid random fill
}

Non golfé et expliqué (incomplet, désolé les gars c'est beaucoup de travail)

F=l=>
{
  var x, z, s, q, D, R, Q, W;
  // length of longest word in z
  z = Math.max( ... l.map(w => w.length))
  // sum of all words length in x
  x = 0;
  l.forEach(w => x += w.length);

  for(; ++z <= x; ) // test square size from z to x
  {
    // grid in s[], each row of len z + 1 newline as separator, plus leading and trailing newline
    // given z==offset between rows, total length of s is z*(z-1)+1
    // gridsize: 2, z:3, s.length: 7 
    // gridsize: 3, z:4, s.length: 13
    // ...
    // All empty, nonseparator cells, filled with 1, so
    // - valid cells have a truthy value (1 or string)
    // - invalid cells have falsy value ('\n' or undefined)
    s = Array(z*z-z+1).fill(1) 
    s = s.map((v,i) => i % z != 0 ? 1 : '\n');

    // offset for 8 directions 
    D = [z+1, -z-1, 1-z, z-1, z, -z, 1, -1]; // 4 diags, then 2 vertical, then 2 horizontal 

    // Function to check repeating words
    R = u => // return true if no repetition
      ! l.some( w => // for each word (exit early when true)
      {
          n = -1 -([...w]+''==[...w].reverse()); // counter starts at -1 or -2 if palindrome word
          u.forEach( (a, p) => // for each cell if grid 
          {
            if (a == [0]) // do check if cell == first letter of word, else next word
               D.forEach( d => // check all directions 
                 n += // word counter
                   [...w].every( c => // for each char in word, exit early if not equal
                     u[q += d] == c, // if word char == cell, continue to next cell using current offset
                     q = p-d  // starting position for cell
                   )
               ) // end for each direction
          } ) // end for each cell
          return n > 0 // if n>0 the word was found more than once
      } ) // end for each word

    // Recursive function to fill empty space with random chars
    // each call add a single char
    Q = 
    ( u, 
      p = u.indexOf(1), // position of first remaining empty cell 
      r = [...'ABCDEFGHIJHLMNOPQRSTUVWXYZ'] // char array to be random shuffled
    ) => {
      if (~p) // proceed if p >= 0
        return r.some((v,c)=>(r[u[p]=r[j=0|c+Math.random()*(26-c)],j]=v,R(u)&&Q(u)))||(u[p]=1)
      else 
        return 1; // when p < 0, no more empty cells, return 1 as true
    }
    // Main working function, recursive fill of grid          
    W = 
    ( k, // current word position in list
      s, // grid
      m, // bitmask with all directions used so far (8 H, 4V, 2 or 1 diag)
      w = l[k] // get current word
    ) => {
      var res = false
      if (w) { // if current word exists
        res = s.some((a,p)=>!!a&&
            D.some((d,j,_,r=[...s],q=p-d)=>
              [...w].every(c=>r[q+=d]==c?c:r[q]==1?r[q]=c:0)
              &&R(r)&&W(k+1,r,m|1<<(j/2))
            )
          )
      } 
      else 
      { // word list completed, check additional constraints
        if (m > 12 // m == 13, 14 or 15, means all directions used
            && Q(s) ) // try to fill with random, proceed if ok
        { // solution found !!
          console.log(''+s) // output grid
          z = x // z = x to stop outer loop
          res = x//return value non zero to stop recursion
        }
      }
      return res
    };
    W(0,s)
  }    
}

Test dans la console Firefox / FireBug

F ([«TRAIN», «CUBE», «BOX», «BICYCLE»])

,T,C,B,O,X,B,H,  
,H,R,U,H,L,I,H,  
,Y,A,A,B,E,C,B,  
,D,H,S,I,E,Y,I,  
,H,E,R,L,N,C,T,  
,G,S,T,Y,F,L,U,  
,H,U,Y,F,O,E,H,  

non-rempli

,T,C,B,O,X,B, ,
, ,R,U, , ,I, ,
, , ,A,B, ,C, ,
, , , ,I,E,Y, ,
, , , , ,N,C, ,
, , , , , ,L, ,
, , , , , ,E, ,

F (['TRAIN', 'ARTS', 'RAT', 'CUBE', 'BOX', 'BICYCLE', 'STORM', 'BRAIN', 'DEPTH', 'MOUTH', 'SLAB'])

,T,A,R,C,S,T,H,
,S,R,R,L,U,D,T,
,T,B,A,T,N,B,P,
,O,B,O,I,S,A,E,
,R,B,A,X,N,H,D,
,M,R,M,O,U,T,H,
,B,I,C,Y,C,L,E,

F ([«AA», «AB», «AC», «AD», «AE», «AF», «AG»])

,A,U,B,C,
,T,A,E,Z,
,C,D,O,F,
,Q,C,G,A,

F ([«AA», «AB», «AC», «AD», «AE», «AF»])

sortie non remplie - @nathan: maintenant vous ne pouvez pas ajouter un autre A x sans répétitions. Vous aurez besoin d'une plus grande grille.

,A, ,C,
, ,A,F,
,D,E,B,
edc65
la source
Sur votre dernier cas de test, n'est-ce pas possible dans une grille 3x3?
Nathan Merrill
@NathanMerrill no. Plus de détails dans le texte de la réponse
edc65
code totalement illisible :) mais sympa c'est l'inconvénient du "prix" octet / point ne soyez pas un compilateur humain
firephil
1
@firephil essaye d'ajouter une explication, ce n'est pas facile ...
edc65
1

C #

Voici une implémentation simple avec encore du travail à faire. Il existe de très nombreuses combinaisons pour obtenir la plus petite taille. Donc, juste utilisé l'algorithme le plus simple pourrait penser.

class Tile
{
    public char C;
    public int X, Y;
}

class Grid
{
    List<Tile> tiles;

    public Grid()
    {
        tiles = new List<Tile>();
    }
    public int MaxX()
    {
        return tiles.Max(x => x.X);
    }
    public int MaxY()
    {
        return tiles.Max(x => x.Y);
    }
    public void AddWords(List<string> list)
    {
        int n = list.Count;
        for (int i = 0; i < n; i++)
        {
            string s = list[i];
            if(i==0)
            {
                Vert(s, 0, 0);
            }
            else if(i==n-1)
            {
                int my = MaxY();
                Diag(s, 0, my+1);
            }
            else
            {
                Horiz(s, 0, i);
            }
        }

    }
    private void Vert(string s, int x, int y)
    {
        for (int i = 0; i < s.Length; i++)
        {
            Tile t = new Tile();
            t.C = s[i];
            t.X = x+i;
            t.Y = y;
            tiles.Add(t);
        }
    }
    private void Horiz(string s, int x, int y)
    {
        for (int i = 0; i < s.Length; i++)
        {
            Tile t = new Tile();
            t.C = s[i];
            t.X = x+i;
            t.Y = y;
            tiles.Add(t);
        }
    }
    private void Diag(string s, int x, int y)
    {
        for (int i = 0; i < s.Length; i++)
        {
            Tile t = new Tile();
            t.C = s[i];
            t.X = x++;
            t.Y = y++;
            tiles.Add(t);
        }
    }
    public void Print()
    {
        int mx = this.MaxX();
        int my = this.MaxY();
        int S = Math.Max(mx, my) + 1;
        char[,] grid = new char[S, S];
        Random r = new Random(DateTime.Now.Millisecond);
        //fill random chars
        for (int i = 0; i < S; i++)
        {
            for (int j = 0; j < S; j++)
            {
                grid[i, j] = (char)(r.Next() % 26 + 'A');
            }
        }
        //fill words
        tiles.ForEach(t => grid[t.X, t.Y] = t.C);
        //print
        for (int i = 0; i < S; i++)
        {
            for (int j = 0; j < S; j++)
            {
                Console.Write("{0} ", grid[i,j]);
            }
            Console.WriteLine();
        }
    }
}

class WordSearch
{
    public static void Generate(List<string>list)
    {
        list.Sort((x, y) =>
        { int s = 0; if (x.Length < y.Length)s = -1; else if (y.Length < x.Length)s = 1; return s; });
        list.Reverse();
        Grid g = new Grid();
        g.AddWords(list);
        g.Print();
    }

}

Tester

class Program
{
    static void Main(string[] args)
    {
        string words = "CAT, TRAIN, CUBE, BICYCLE";
        string comma=",";
        List<string> w = words.Split(comma.ToArray()).ToList();
        List<string> t = new List<string>();
        foreach(string s in w)
        {
           t.Add(s.Trim());
        }
        WordSearch.Generate(t);

        Console.ReadKey();
    }
}
bacchusbeale
la source
cela fonctionne mais ce n'est pas optimal: exemples de mots de chaîne = "CAT, DOG, HR, RUN, CMD";
firephil
Vérifiez-vous si les caractères de remplissage aléatoires provoquent la répétition d'un mot dans la grille?
edc65
-1 J'ai essayé. Ne suit pas les spécifications at least one word in each direction (horizontal, vertical and diagonal). Exécution du programme de test, pas de mot horizontal (3 verticaux, 1 diag)
edc65
3
Cette question est code-golf , vous devez donc poster combien d'octets dans le titre, et probablement raccourcir votre programme un tas. Merci.
mbomb007
@ edc65 Il fait une verticale, une diagonale et toutes les autres horizontales. Comme je l'ai dit pour obtenir une solution parfaite, il faudra un nombre énorme de combinaisons à vérifier ainsi que les spécifications de la question.
bacchusbeale