Permainan pelat nomor Spanyol

26

Pertanyaan ini didasarkan pada pertanyaan yang saya ajukan dalam bahasa Spanyol . Ya, saya meminta algoritma dalam Bahasa Spanyol. :)

Di Spanyol, plat nomor saat ini memiliki pola ini:

1234 XYZ

di mana XYZ adalah tiga konsonan yang diambil dari set konsonan Spanyol penuh (kecuali 'Ñ', saya pikir).

Terkadang, saat bepergian dengan istri saya, kami biasa bermain game. Ketika kita melihat plat nomor, kita mengambil tiga konsonan dan mencoba untuk membentuk sebuah kata yang mengandung ketiga konsonan itu, muncul dalam urutan yang sama seperti pada plat nomor. Contoh (dalam bahasa Spanyol):

BCD
    BoCaDo (valid)
    CaBezaDa (not valid)
FTL
    FaTaL (valid)
    FLeTar (not valid)
FTR
    FleTaR (valid, wins)
    caFeTeRa (valid, loses)

Pemenangnya adalah orang yang menggunakan jumlah karakter paling sedikit, seperti yang Anda lihat pada contoh terakhir.

Tantangan

Tulis program atau fungsi terpendek yang menerima daftar kata dan satu set tiga konsonan dan temukan kata terpendek dalam daftar yang berisi tiga konsonan dalam urutan yang sama. Untuk tujuan permainan ini, kasus tidak masalah.

  • Input untuk daftar kata (parameter pertama) akan menjadi array dari stringjenis bahasa Anda . Parameter kedua (tiga konsonan) akan menjadi yang lain string. Jika lebih baik untuk bahasa Anda, pertimbangkan stringdengan tiga konsonan item terakhir dari seluruh daftar parameter. Output akan menjadi yang lain string.
  • Kata-kata dalam daftar kata tidak akan ditemukan atau kata-kata yang tak terbatas, kata-kata yang akan muncul dalam kamus standar apa pun. Jika Anda membutuhkan batas, anggap tidak ada kata dalam daftar kata yang akan lebih panjang dari 50 karakter.
  • Jika ada beberapa kata dengan panjang yang sama yang bisa menjadi jawaban yang valid, Anda dapat mengembalikan salah satu dari mereka. Pastikan Anda mengembalikan hanya satu kata, atau string kosong jika tidak ada kata yang cocok dengan pola tiga konsonan.
  • Anda dapat mengulangi konsonan dalam grup, jadi input yang valid untuk ketiga konsonan adalah keduanya FLRdan GGG.
  • Konsonan Spanyol persis sama dengan bahasa Inggris, dengan penambahan "Ñ". Vokal sama dengan adition dari vokal yang ditekankan: "áéíóúü". Tidak akan ada tanda lain seperti "-" atau "'".
  • Anda dapat mengira bahwa kasusnya akan selalu sama dalam daftar kata dan tiga konsonan.

Jika Anda ingin menguji algoritme Anda dengan koleksi nyata kata-kata Spanyol, Anda dapat mengunduh file (15,9 MB) dari Dropbox dengan lebih dari satu juta kata.

Uji kasus

Input: 'psr', {'hola' 'repasar' 'pasarais' 'de' 'caída' 'pequeñísimo' 'agüeros'}
Output: 'repasar'

Input: 'dsd', {'dedos' 'deseado' 'desde' 'sedado'}
Output: 'desde'

Input: 'hst', {'hastío' 'chest'}
Output: 'chest'

Ini adalah , jadi semoga program terpendek yang membantu saya untuk selalu mengalahkan kemenangan istri saya! :)

Charlie
sumber
Berapa lama kata-kata dalam daftar kata dijamin?
Neil
2
Dalam plat nomor aktual, huruf Q juga tidak diizinkan; dan W , meskipun bukan huruf Spanyol yang tepat
Luis Mendo
2
Bolehkah kita mengasumsikan kata-kata dalam daftar dan tiga huruf akan semuanya dalam satu kasus?
Jonathan Allan
1
@LuisMendo W telah menjadi huruf Spanyol sejak 1969 .
walen
1
@walen Itu sebabnya saya berkata "benar" :-) Itu ada dalam bahasa Spanyol, tetapi terasa asing
Luis Mendo

Jawaban:

7

05AB1E , 10 8 byte

Disimpan 2 byte berkat Leo

ʒæså}éR`

Cobalah online!

Penjelasan

ʒ         # filter list, keep only members for which the following is true
  så      # input is in the
 æ        # powerset of the current word
    }     # end filter
     é    # sort by length
      R   # reverse
       `  # push separately (shortest on top)

Saya akan digunakan headpada akhirnya menghemat satu byte tetapi itu akan menampilkan daftar kosong jika tidak ada kecocokan.

Emigna
sumber
3
3ù #keep only those of length 3mengapa kamu membutuhkan ini?
Leo
1
@ Leo: Saya tidak, itu konyol saya. Terima kasih :)
Emigna
6

MATL , 30 29 byte

xtog!s2$S"1G!'.*'Yc!@gwXXn?@.

Cobalah online!

Penjelasan

x         % Implicitly take first input (string with three letters). Delete.
          % Gets copied into clipboard G, level 1
t         % Implicitly take second input (cell array of strings defining the
          % words). Duplicate
o         % Convert to numeric array of code points. This gives a matrix where
          % each string is on a row, right-padded with zeros
g         % Convert to logical: nonzeros become 1
!s        % Sum of each row. This gives the length of each word
2$S       % Two-input sort: this sorts the array of strings according to their
          % lengths in increasing order
"         % For each word in the sorted array
  1G      %   Push first input, say 'xyz'
  !       %   Transpose into a column vector of chars
  '.*'Yc  %   Concatenate this string on each row
  !       %   Transpose. This gives a char array which, when linearized in
          %   column-major order, corresponds to 'x.*y.*z.*'
  @g      %   Push corrent word
  w       %   Swap
  XX      %   Regexp matching. Gives a cell array with substrings that match
          %   the pattern 'x.*y.*z.*'
  n       %   Number of matchings
  ?       %   If non-zero
    @     %     Push cell array with current word, to be displayed as output
    .     %     Break loop
          %   Implicit end (if)
          % Implicit end (for)
          % Implicitly display stack
Luis Mendo
sumber
6

PHP , 111 byte

$y=array_map(str_split,preg_grep("#".chunk_split($_GET[1],1,".*")."#",$_GET[0]));sort($y);echo join($y[0]??[]);

Cobalah online!

Jörg Hülsermann
sumber
2
Plat nomor harus berupa string, bukan array. Tetapi Anda tidak membutuhkan pengubahnya.
Titus
@Titus diperbaiki !!
Jörg Hülsermann
You can suppose the case will always be the same in both the word list and the three consonants.- tidak perlu untuk pengubah regex. Apakah Anda mencoba wordwrapbukan join(str_split())?
Titus
@Titus ide bagus
Jörg Hülsermann
5

Jelly ,  12 11  10 byte

ŒPċðÐfLÞḣ1

Program lengkap yang menerima daftar daftar huruf kecil (kata-kata) dan daftar huruf kecil (huruf) dan mencetak kata pertama dari kata terpendek yang berisi sub-urutan sama dengan huruf (atau tidak sama sekali jika tidak ada ).

Cobalah online!

Bagaimana?

ŒPċðÐfLÞḣ1 - Main link: words; characters
   ðÐf     - filter keep words for which this is truthy:
ŒP         -   the power-set (all sub-sequences of the word in question)
  ċ        -   count (how many times the list of characters appears)
           - ...note 0 is falsey while 1, 2, 3, ... are truthy
       Þ   - sort by:
      L    -  length
        ḣ1 - head to index 1 (would use Ḣ but it yields 0 for empty lists)
           - implicit print (smashes together the list of lists (of length 1))
Jonathan Allan
sumber
1
Jika saya memahami penjelasan Anda dengan benar, ini akan menolak kata seperti "borracho" untuk urutan konsonan "brc", karena "brc" bukan merupakan substring dari "brrc"
Leo
@ Leo ah, ya tangkapan bagus saya pikir itu akan gagal ...
Jonathan Allan
@ Leo - yah sudah diperbaiki (centang "ada di" untuk seluruh set daya setiap kata) tetapi mungkin tidak sepenuhnya golf ...
Jonathan Allan
5

Pyth - 22 21 19 12 11 byte

h+f/yTQlDEk

-1 Terima kasih kepada Maltysen.

Mengambil 2 baris sebagai input. 1 adalah string 3 huruf (huruf kecil), dan 2 adalah daftar kata huruf kecil.

Coba di sini

Penjelasan:

h+f/yTQlDEk
       lDE   # Sort word list by length
  f          # Filter elements T of the word list...
    yT       # by taking the powerset...
   /  Q      # and checking whether the 3-letter string Q is an element of that.
 +        k  # Add empty string to the list (in case no results found)
h            # And take the first result (the shortest)

Solusi lama 19 byte:

h+olNf/-T"aeiou"QEk                       
Maria
sumber
@ JonathanAllan: Diperbaiki! Terima kasih telah menunjukkannya.
Maria
1
@ JonathanAllan: Sepertinya dia mengedit pertanyaan untuk mengklarifikasi bahwa itu harus mengembalikan string kosong dalam kasus itu. Saya telah mengedit jawaban saya sesuai dengan itu.
Maria
1
Kami memiliki operator meta sort-by di D, sehingga Anda dapat mengganti olN dengan lD
Maltysen
5

Brachylog v2, 11 byte

tlᵒ∋.&h⊆.∨Ẹ

Cobalah online!

Pengiriman fungsi. (TIO link memiliki argumen baris perintah untuk menjalankan fungsi seolah-olah itu adalah program lengkap.)

Penjelasan

Hanya terjemahan langsung dari spesifikasi lagi ...

tlᵒ∋.&h⊆.∨Ẹ
t            The last element of {standard input}
   ∋.        contains the return value as an element
     &       and
      h      the first element of {standard input}
       ⊆.    is a subsequence of the return value
         ∨   alternate behaviour if no solution is found:
          Ẹ  return empty string
  ᵒ          tiebreak override: favour answers that have a low
 l           length

Anda benar-benar hampir dapat menjawab dengan h⊆.&t∋- menukar urutan evaluasi berarti bahwa Brachylog akan memilih jawaban tersingkat secara default (seperti kendala pertama yang dilihatnya , yang memiliki "terpendek" yang agak nyaman sebagai tiebreak default) - tetapi dalam kasus itu, Brachylog's algoritma evaluasi sayangnya akan masuk ke loop tak terbatas jika jawabannya tidak benar-benar ditemukan. Jadi hampir setengah dari jawaban itu didedikasikan untuk menangani kasus tidak ada jawaban yang tepat. Bahkan kemudian, lᵒtiebreak menimpa (yang secara teknis semacam, memanfaatkantiebreak default dari elemen yang disukai lebih dekat pada awal daftar) hanya dua byte; tiga lainnya berasal dari kebutuhan untuk mengeluarkan string kosong khusus ketika output tidak ditemukan, yang bertentangan dengan nilai sentinel "no solusi" default Brachylog (karena final .akan tersirat jika kita tidak harus mengikutinya dengan ).

Menariknya, ada fitur yang sebelumnya diterapkan di Brachylog yang akan menyelamatkan satu byte di sini. Pada satu titik, Anda bisa mengekstrak elemen dari argumen masukan menggunakan ?₁, ?₂, dll sintaks; yang akan memungkinkan Anda untuk mengatur ulang program tlᵒ∋.⊇?₁∨Ẹ, yang hanya 10 byte. Sayangnya, implementasi yang digunakan tidak benar-benar berfungsi (dan menyebabkan banyak program yang rusak), sehingga dikembalikan. Anda dapat menganggap program sebagai "konseptual" sepanjang 10 byte.

ais523
sumber
4

Haskell 129 125 74 byte

import Data.List
l#w=sortOn length[p|p<-w,isInfixOf l$filter(`elem`l)p]!!0

KREDIT ke @nimi

Davide Spataro
sumber
1
Anda dapat mengganti yang paling kanan mapdan yang filterdengan daftar pemahaman. Karena Anda sudah memiliki Data.Listruang lingkup, Anda dapat menggunakan sortOn lengthdan memilih kepala untuk menemukan elemen dengan panjang minimal. Akhirnya, buatlah yfungsi infiks. Semua ini membuat fdan kberlebihan:l#w=sortOn length[p|p<-w,isInfixOf l$filter(`elem`l)p]!!0 .
nimi
kamu benar! Saya baru saja mulai bermain golf! Terima kasih!
Davide Spataro
1
Satu lagi: jika Anda mengalihkan impor Data.Lists, Anda dapat menggunakanargmin bukannya sortOndan menyimpan !!0: l#w=argmin length[...]. Data.Listsmemiliki banyak fungsi yang bagus
nimi
3

Perl, 53 byte

48 byte kode + 5 untuk -paF.

$"=".*";($_)=sort{$a=~y///c-length$b}grep/@F/,<>

Ini mengambil keuntungan dari fakta bahwa daftar diinterpolasi ke m//operator yang memanfaatkan $"variabel yang mengubah masukan string awal dari psrke p.*s.*ryang kemudian dicocokkan untuk setiap kata tambahan dan diurutkan pada length.

Cobalah online!

Dom Hastings
sumber
Jika saya memasukkan "adsd" ke daftar Anda, program Anda gagal menemukannya. Karakter pertama yang ditemukan tidak perlu menjadi yang pertama dalam kata.
Charlie
@CarlosAlejo Input membutuhkan baris baru, berfungsi dengan baik kemudian: Coba online! . Itu memang membuat saya lengah, karena <<<operator menambahkan itu untuk saya di baris perintah!
Dom Hastings
3

JavaScript (ES6), 77 75 72 byte

Membawa 3 konsonan c dan daftar kata ldalam sintaks currying (c)(l). Kedua input diharapkan dalam kasus yang sama.

c=>l=>l.map(w=>x=!w.match([...c].join`.*`)||!x[w.length]&&x?x:w,x='')&&x

Uji kasus

Arnauld
sumber
c=>l=>l.sort((a,b)=>a[b.length]&&1).find(w=>w.match(c.split``.join`.*`))untuk 72, saya pikir
LarsW
@ LarsW Memang, terima kasih! Namun saya telah memilih pendekatan lain untuk mematuhi aturan baru: atau string kosong jika tidak ada kata yang cocok dengan pola tiga konsonan .
Arnauld
3

R, 101 byte

Pertama kali bermain golf! Saya yakin ini bisa dipadatkan

Mengambil string x dan vektor karakter y dari input yang mungkin

w=pryr::f((b=y[sapply(gsub(paste('[^',x,']'),'',y),function(l)regexpr(x,l))>0])[which.min(nchar(b))])

Cobalah online!

Sunting: Versi saya 135, terima kasih Scrooble untuk -34!

Pun intended
sumber
1
Selamat datang di PPCG! Ini terlihat seperti cuplikan di mana input dalam variabel hardcoded. Jawaban harus berupa program lengkap atau fungsi yang dapat dipanggil. Anda dapat melihat ini (atau jawaban R lainnya) untuk kemungkinan metode I / O.
Martin Ender
2

Retina , 58 byte

O#$^`¶.+
$.&
s`^((.)(.)(.).*¶(?-s:(.*\2.*\3.*\4.*)))?.*
$5

Cobalah online! Mengambil tiga konsonan pada satu baris dan kemudian daftar kata pada semua baris berikutnya. Penjelasan: Omengurutkan daftar ¶.+tidak termasuk baris pertama secara #numerik $dikunci oleh $.&panjang. Pertandingan kemudian dicari untuk garis yang menyertakan tiga konsonan secara berurutan. Jika garis yang sesuai ada dari yang terakhir, yaitu terpendek, garis tersebut menjadi output, jika tidak maka output kosong. Untuk ?-s:sementara menonaktifkan efek s`sehingga hanya satu baris yang cocok.

Neil
sumber
1
Saya tidak bisa memutuskan apakah itu tiga pusar atau tiga payudara.
Charlie
@CarlosAlejo Apakah Anda memikirkan Eccentrica Gallumbits?
Neil
Saya sedang memikirkan alien dari Total Recall, tetapi Eccentrica juga bisa menjadi pilihan ... :)
Charlie
2
@CarlosAlejo Rupanya Mary adalah penghormatan untuk Eccentrica Gallumbits.
Neil
1

Pip , 17 byte

@:qJ`.*`N_FI#_SKg

Mengambil daftar kata sebagai argumen baris perintah, dan konsonan dari stdin. Cobalah online!

Penjelasan

                   g is list of cmdline args (implicit)
              SKg  Sort g using this key function:
            #_      Length of each item (puts shortest words first)
          FI       Filter on this function:
  q                 Line of input
   J`.*`            joined on regex .* (turns "psr" into `p.*s.*r`)
        N_          Count regex matches in item (keeps only words that match)
@:                 Get first element of result (using : meta-operator to lower precedence)
                   If the list is empty, this will give nil, which results in empty output
DLosc
sumber
1

Java 8, 132 126 byte

s->a->{String r="";for(String x:a)r=(x.length()<r.length()|r.isEmpty())&x.matches(r.format(".*%s.*%s.*%s.*",s))?x:r;return r;}

-6 byte terima kasih kepada @Nevay .

Penjelasan:

Cobalah online.

s->a->{              // Method with two String-array parameters and String return-type
  String r="";       //  Result-String, starting empty
  for(String x:a)    //  Loop over the words
    r=(x.length()<r.length()
                     //   If a word is smaller than the current `r`,
      |r.isEmpty())  //   or `r` is still empty
      &x.matches(r.format(".*%s.*%s.*%s.*",s))?
                     //   And if the word is valid
       x             //    Change `r` to the current word
      :              //   Else:
       r;            //    Leave `r` the same
  return r;}         //  Return the result
Kevin Cruijssen
sumber
1
126 byte:s->a->{String r="";for(String x:a)r=(x.length()<r.length()|r.isEmpty())&x.matches(r.format(".*%s.*%s.*%s.*",s))?x:r;return r;}
Nevay
0

Python, 77 byte

import re
lambda s,a:min([x for x in a if re.search('.*'.join(s),x)],key=len)

Cobalah online!

Uriel
sumber
0

MATL , 28 27 26 byte

x"l1G@g3XNXm/@gn*v]&X<2Gw)

Cobalah online!

x- Secara implisit mengambil input pertama (string dengan tiga huruf) dan menghapusnya. Mendapat disalin ke clipboard G, level 1 secara otomatis (bagian ini terinspirasi oleh jawaban @Luis Mendo ).

" - Secara implisit mengambil input kedua (array kata-kata sel), beralih melalui itu.

l - Dorong 1 untuk digunakan nanti

1G - Tekan input pertama (katakan 'psr')

@g - Dorong kata saat ini sebagai array

3XN- nchoosek- Dapatkan semua kombinasi 3 huruf dari kata

Xm- Lihat apakah kode plat 'psr' adalah salah satu dari kombinasi ini. Mengembalikan 0 untuk false dan 1 untuk true.

/- Membagi 1 (yang kami dorong sebelumnya) dengan hasil ini. Mengubah 0s menjadi Infs

@gn - Dapatkan panjang kata saat ini

*- Kalikan panjangnya dengan hasil pembagian. Mengembalikan panjang seperti ketika kata berisi 3 karakter, jika tidak kembaliInf

v - menggabungkan hasil ini secara vertikal menjadi satu larik

] - tutup lingkaran

&X< - dapatkan indeks dari nilai minimum dari array itu yaitu indeks di mana kata yang mengandung huruf dan dengan panjang minimum ditemukan

2G - Tekan kembali input kedua

w - Bawa indeks min kembali ke atas tumpukan

) - Indeks ke dalam array kata dengan indeks min, mengembalikan kata yang valid dengan panjang minimum

(Output tersirat.)


Lebih tua:

x"@g1Gy3XNXm1w/wn*v]&X<2Gw)

x"@g1Gy3XNXm1w/wn*v]2Gw2$S1)
sundar - Pasang kembali Monica
sumber