Generasi puzzle pencarian kata

13

Diberikan daftar string, temukan matriks kuadrat terkecil yang berisi masing-masing string awal. String dapat muncul secara horizontal, vertikal atau diagonal dan maju atau mundur seperti dalam pertanyaan ini Puzzle Pencarian Kata .

Kata-kata harus ditempatkan di kotak, dengan setidaknya satu kata di setiap arah (horizontal, vertikal dan diagonal). Kata-kata akan muncul hanya satu kali.

Jadi, inputnya hanyalah daftar kata-kata. Sebagai contoh: CAT, TRAIN, CUBE, BICYCLE. Salah satu solusi yang mungkin adalah:

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

Saya mengganti mengisi surat dengan tanda bintang hanya untuk kejelasan. Keluaran yang diinginkan harus mencakup surat pengisian acak.

Bermigrasi
sumber
Haruskah setiap kata ditemukan hanya dalam satu posisi (seperti pencarian kata pada umumnya)? Misalnya, huruf yang tersisa ACdi contoh Anda akan membuat yang lain CATjika itu T.
Geobits
Tidak jelas bagi saya apa yang sebenarnya Anda maksud dengan " Kata-kata harus ditempatkan secara acak ke segala arah ". Akankah jawaban memenuhi kriteria ini jika, setelah meletakkan kata-kata dengan deterministik, itu secara acak memilih salah satu dari delapan simetri alun-alun? Atau, di sisi lain, apakah output harus dipilih secara seragam dari semua kotak terkecil yang mungkin berisi kata-kata? Atau apakah garis yang ditarik di suatu tempat di antara yang ekstrem itu?
Peter Taylor
Ya, itu harus ditemukan hanya dalam satu posisi.
Migue
1
Tidak juga, tidak. Saya masih tidak jelas apa ruang dari mana jawaban harus sampel secara acak, atau berapa banyak fleksibilitas yang diperbolehkan dalam menimbang unsur-unsur ruang itu.
Peter Taylor
1
Sampai sekarang, pertanyaan memiliki input yang tidak dapat diselesaikan, tetapi tidak disebutkan bagaimana Anda seharusnya berurusan dengan itu. Misalnya set 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 Ztidak memiliki solusi.
orlp

Jawaban:

6

JavaScript (ES6), 595 628 680

Sunting Beberapa pembersihan dan penggabungan:
- fungsi P digabung di dalam fungsi R
- calc x dan z dalam .map yang sama
- ketika solusi ditemukan, atur x ke 0 untuk keluar dari loop luar
- definisi gabungan dan panggilan W

Edit2 lebih banyak bermain golf, isi acak disingkat, loop luar direvisi ... lihat riwayat untuk sesuatu yang lebih mudah dibaca

Berbeda dengan jawaban yang diterima, ini harus bekerja untuk sebagian besar input. Hanya hindari kata-kata satu huruf. Jika sebuah output ditemukan, itu optimal dan menggunakan semua 3 arah.

Kendala untuk menghindari pengulangan kata sangat sulit. Saya harus mencari kata berulang di setiap langkah menambahkan kata ke grid, dan pada setiap karakter isian acak.

Subfungsi utama:

  • P (w) benar jika kata palindrome. Kata palindrom akan ditemukan dua kali ketika memeriksa kata-kata yang diulang.

  • R (s) periksa kata yang berulang pada kisi s

  • Q (s) mengisi kisi-kisi dengan karakter acak - itu rekursif dan mundur jika kata berulang - dan bisa gagal.

  • W () rekursif, cobalah untuk mengisi kotak ukuran yang diberikan, jika memungkinkan.

Fungsi utama menggunakan W () untuk menemukan kisi keluaran, mencoba dari ukuran kata terpanjang dalam input hingga jumlah panjang semua kata.

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
}

Tidak digabungkan dan dijelaskan (tidak lengkap, maaf guys ini banyak pekerjaan)

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)
  }    
}

Uji di Firefox / konsol 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,  

tidak diisi

,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', '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'])

output tidak terisi - @nathan: sekarang Anda tidak dapat menambahkan A x lainnya tanpa pengulangan. Anda akan membutuhkan kisi yang lebih besar.

,A, ,C,
, ,A,F,
,D,E,B,
edc65
sumber
Pada test case terakhir Anda, bukankah mungkin dalam kisi 3x3?
Nathan Merrill
@NathanMerrill no. Lebih detail dalam teks jawaban
edc65
kode yang sama sekali tidak dapat dibaca :) tapi bagus itu adalah kelemahan dari byte / point "award" jangan menjadi kompiler manusia
firephil
1
@firephil mencoba menambahkan penjelasan, itu tidak mudah ...
edc65
1

C #

Berikut ini adalah implementasi sederhana dengan pekerjaan yang masih harus dilakukan. Ada sangat banyak kombinasi untuk mendapatkan ukuran terkecil. Jadi hanya menggunakan algoritma paling sederhana yang bisa dipikirkan.

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();
    }

}

Uji

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
sumber
ini berfungsi tetapi tidak optimal: contoh kata string = "CAT, DOG, HR, RUN, CMD";
firephil
Apakah Anda memeriksa apakah karakter isian acak menyebabkan pengulangan kata dalam kisi?
edc65
-1 Mencobanya. Tidak mengikuti spesifikasi at least one word in each direction (horizontal, vertical and diagonal). Menjalankan program pengujian, tanpa kata horisontal (3 vertikal, 1 diag)
edc65
3
Pertanyaan ini adalah kode-golf , jadi Anda harus memposting berapa byte dalam judul, dan mungkin mempersingkat banyak program Anda. Terima kasih.
mbomb007
@ edc65 Ia melakukan satu vertikal, satu diagonal dan yang lainnya horisontal. Seperti yang saya komentari untuk mendapatkan solusi sempurna akan membutuhkan sejumlah besar kombinasi untuk mengecek serta spesifikasi pertanyaan.
bacchusbeale