4

This is an attempt to write a new kind of question in which the answer needs to be found by writing an algorithm, rather than searching for it online, posted as discussed on meta. You can take it as a way to improve your programming skills while finding the answer to a curious question about our language.


The Spain license plates game

In Spain, current license plates have this pattern:

1234 XYZ

where XYZ are three consonants taken from the full set of Spanish consonants (except the 'Ñ', I think).

Sometimes, when traveling with my wife, we used to play a game. When we see a license plate, we take the three consonants and try to form a word that contains those three consonants, appearing in the same order as in the license plate. Examples:

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

The winner is the one who uses the least number of characters, as you can see in the last example.

OK, nice game, so what's the problem?

The problem is that not all the combination of consonants allow the game to have a solution, especially when the plate contains consonants such as 'W', 'X', 'Q' and so on.

So here's the question. I would like to find a subset of the Spanish consonants, such that you can take any three consonants (repetitions allowed) from that subset, and always be able to find a valid solution for the game. Example:

Subset: {B,C,D}

Possible permutations of these three letters, and some possible words
containing the letters in each permutation in the right order:

    BBB  BaoBaB
    BBC  BarBaCoa
    BBD  BaBaDa
    BCB  BiCarBonato
    BCC  BoCaCalle
    BCD  BoCaDo
    BDB  aBorDaBle
    BDC  aBDuCir
    BDD  BoveDaD
    CBB  CaBeceaBa
    CBC  CaBeCeaba
    CBD  CaBleaDo
    CCB  CabeCeaBa
    CCC  aparCaCoChes
    CCD  CaChaDa
    CDB  abraCaDaBra
    CDC  aComoDaCión
    CDD  aComoDaDo
    DBB  DoBlaBa
    DBC  DeBaCle
    DBD  DoBlaDo
    DCB  DeCasílaBo
    DCC  DeCadenCia
    DCD  DeCaDencia
    DDB  DegraDaBle
    DDC  DeDiCación
    DDD  DefenDeDor

Thus, {B,C,D} would be a valid answer, since every permutation of the members of the set (with repetitions allowed) has a solution for the game. But I am looking for the largest set that matches this criterion. What would that subset of consonants be?


Notes:

  1. I don't know if you can download a list of words from the RAE dictionary, so you can use any other Spanish list of words available, as long as it is reasonably complete (see below).
  2. Verb conjugations are valid words to be formed, as well as plurals.
  3. Note that I am not looking for the solutions to the game, as the game is to be played by humans. I am looking for the largest subset of consonants that allow the game to always be played and solved when taken any three consonants from them (repetitions allowed as seen in the example).

In other words, the challenge consists of finding the largest fair set of letters that the game can safely be played with, such that the players can never get stuck, where "stuck" means they are unable to propose a word for some permutation of letters taken from the alphabet (minus Ñ).


Lists of words:

  1. Public list of words with more than 80K entries (but does not contain plural forms or verb conjugations): https://github.com/javierarce/palabras/blob/master/listado-general.txt

  2. Dictionary used in LibreOffice and others: files es_ANY.dic and es_ANY.aff here. Entries are in the form [word]/[affixes], so you need to decode the way the affixes modify every word. If you want the whole word list generated by these two files, I have uploaded a file here (15.9MB, 1,256,499 words).


Posted the actual license plates game in PPCG! :)

  • 1
    Lista de palabras españolas: github.com/javierarce/palabras/blob/master/listado-general.txt No salen los verbos conjugados, pero en total aparecen más de 80 mil entradas. – fedorqui 'SO stop harming' Apr 27 '17 at 9:27
  • 2
    I think this would be best done on the programming puzzle SE. – user0721090601 Apr 27 '17 at 13:50
  • 1
    @guifa nonetheless, the problems there have all something in common: the final answer is always known, and what is important is the shortness of the code that provides the answer. I don't have the answer here, so I will not be able to validate whose code is the winner. – Charlie Apr 27 '17 at 14:04
  • 1
    Me han dado en la. Pata de palo. Escribiendo algoritmo ahora. Mismo – hlecuanda May 2 '17 at 8:25
  • 1
    Jaja 😂 es una alusión a tu mayor debilidad. Cuando alguien te golpea en tu "pata de palo" figuradamente tu única alternativa es caer en la tentación, como lo haría un hipotético corsario "mocho",* con el suelo, si le propinaras un golpe en su arbórea prótesis... (* alusión a un reciente te tema análogo) jaja – hlecuanda May 2 '17 at 8:34
4
+200

Para solucionar este problema, hay varios pasos que tenemos que hacer.

  1. Determinar todas las palabras en castellano. Esta lista es ENORME cuando se tiene en cuenta los verbos (más de 50 formas antes de contemplar las numerosas opciones de pronombres enclíticos sobre las seis formas imperativas que los admiten). Estamos hablando de algunos millones de palabras.
  2. Determinar (como máximo) !23^3! combinaciones de tres consonantes que pueden formar palabras en castellano según las instrucciones (máximo !23^3!)
  3. Determinar cuáles de grupos de 3 a 23 consonantes pueden ordenarse en subgrupos de tres (con repeticiones, así con 33 a 233 subgrupos cada uno) con tal de que cada de esos subgrupos se incluya en las combinaciones de paso 1.

El problema con que nos enfrentamos es que, teóricamente, habrá 750 cuatrillones de subgrupos en paso 3 que tenemos que verificar si están en las combinaciones de paso 2 (que a su vez tiene 12167 posibilidades).

Lo bueno es que tenemos algunas optimaciones que podemos hacer.

Primero, si cualquier letra no funciona en un grupo por sí sola (es decir, XXX), podemos descartar aquella letra por completo. (los sufijos hacen posible, teóricamente, ñoñiño de ñoño o zarzuelazo de zarzuela pero no usamos Ñ y no sé hasta que punto nuestro diccionario incluye sufijos). Ello nos reduce a 68588190, muchísimo más calculable.

De las combinaciones en triple, puedo afirmar lo siguiente (usando el regex A.*A.*A para pasar el archivo usando una letra en vez de A):

BBB: posible
CCC: posible
DDD: posible 
FFF: no posible
GGG: no posible 
HHH: posible (5 posibilidades)
JJJ: no posible
KKK: no posible
LLL: posible (1537 posibilidades)
MMM: posible (1593 posibilidades)
NNN: posible (22956 posibilidades)
PPP: posible (8 posibilidades)
QQQ: no posible
RRR: posible (17034 posibilidades)
SSS: posible (58264 posibilidades)
TTT: posible (2354 posibilidades)
VVV: posible (5 posibilidades)
WWW: no posible
XXX: no posible
YYY: no posible
ZZZ: no posible

Paso 1

Para este paso, he tomado dos archivos de LibreOffice (usan el formato Hunspell). Primero tenemos un diccionario que lleva el format [palabra]/[códigos]. Los códigos son de una letra en el caso del archivo español. Como ejemplo, tenemos la palabra hombre/S y la palabra mujer/S. El código S significa que podemos modificar las dos palabras según las reglas del mismo código contenidas en el archivo de afijos. Estas nos proporcionan las formas hombres y mujeres (así que tenemos hombre, hombres, mujer, mujeres). CarlosAlejo en los comentarios ya nos ha dado un archivo con todas las posibilidades.

Paso 2

La forma más rápida, por lo visto, es iterar por cada una de las millón y pico palabras, quitándoles cualquier letra no sea BCDHLMNPRSTV. De allí, determinamos todas las combinaciones de tres de las letras que queda (es decir, con bbcd tenemos bbc, bbd, bcd, bcd). Lo bueno es que con perl6 el método combinations nos mantiene el orden de las letras, necesario para el problema.

use v6;
my @consonants = ; # Ñ is not an option
my $file = open "es_ANY.txt";
my @dic = $file.lines;
close $file;
my %result;
for @dic -> $word {
  %result{.join('')}++ for $word.subst(/<-[bcdhlmnprstv]>/,'',:g).combinations(3);
}
say %result.keys.join(',');

El resultado de ello es sns,rtb,sph,nnp,mth,clp,tvb,npd,rnt,lll,rhl,tsr,npn,bpc,ssn,hmb,rrm,tvr,snt,dpl,tht,bdl,bsn,lst,bcr,cbr,tvc,lnp,lhc,pcl,llc,dst,srm,ttr,srl,rnp,sdp,hvr,rms,dnn,lvr,rll,prm,psc,lnd,npp,rrd,nrl,dhr,shd,ctm,dtv,rsm,brt,drc,ltc,hch,hhs,hsb,cph,lrv,srs,npb,mrp,nlp,sdl,crl,pcr,pcb,rdl,lpr,cdh,hnn,pls,bvv,hvm,vnt,dhb,lds,dnb,mnr,psd,mln,ndm,hrv,llv,ldb,trd,ptm,lpp,hrp,thn,nvs,dph,vhs,vcn,csn,ndd,vmm,pdb,ttb,mcd,hlh,lnb,lln,vcc,rbd,ldn,bvl,dcp,smh,bpr,hdd,vvs,cnr,hts,bnb,dlv,cpv,pcp,tch,hsl,rtn,cnp,rtr,bvb,src,tpm,svv,hrr,scd,dds,dnm,pss,pch,mnt,tcb,ttc,nvm,dvn,cnn,bns,stt,rsr,rmd,mhv,sct,npl,rht,bbn,ptl,hsv,pvv,rsn,ddm,hcc,hpt,nld,lsr,rsl,mct,mcb,dtc,bmt,rtm,slc,dvp,bct,bdh,vhd,cdc,pnr,pbb,pml,mtc,vlm,bbv,rsv,mpd,vtd,mmv,cnh,dhd,hbv,hnr,clt,rpb,cch,hld,ssp,mhn,tds,lsb,nms,nbt,mlc,stp,pcc,ntc,nsm,lvs,ddc,dbb,rrv,stb,lrm,tlb,mhp,tbn,cnt,tps,mrc,tpn,rlh,vvr,lvp,lph,tdm,ppb,phs,dtm,trn,vbb,hvl,crr,nrt,nmt,tmc,shr,phr,hmp,mtd,mcr,vld,lhh,mhd,snc,vcb,tnl,svd,drp,tdb,rct,cln,vcp,hph,pnp,rvs,brh,cpm,tsc,hpl,msv,rdh,rvr,rvl,htd,hhr,mvb,hrs,lnr,rlv,vrn,ndh,vlr,llp,cnl,rvc,tsd,ltb,phl,rtv,vcr,ptt,vmv,vcv,vdr,vdl,dht,lcb,pbt,msd,lbp,tpd,npv,dcb,dtl,vdn,dpr,mnc,tbc,bhc,cst,cdm,ltm,pnc,psn,nsd,tts,mvs,vnb,rnv,bvt,scl,hls,hnt,nbc,lls,cbc,rpc,lcr,trb,rpt,dth,drh,slr,bsr,svm,lch,vbc,bpb,mnd,bnd,lrn,ddn,phc,lrp,pvh,ttn,ncm,tdl,sbb,ptb,hpb,mht,dls,dbm,lbb,tpv,rnl,lcm,hvd,cmt,nsn,vpb,hpm,pct,lsh,lcp,prs,vmc,ccp,plh,rtl,ths,lnt,snr,rhn,pbc,hmr,vhh,btp,rmc,rtt,tph,lcn,cms,ldv,bds,mrb,sbt,spv,mvr,lvb,lcv,bvs,hnp,psb,nrp,tdp,bcb,tnm,cmd,mnn,rdd,hhh,lhv,bmc,crc,nrc,htr,htm,hcs,cvl,vlt,hvh,dvm,hsn,rvt,tvv,lth,bhs,vdt,tmn,ldr,dsl,cmr,tdt,vpc,sbh,mlm,tdr,btl,hct,pvr,ltp,tvs,cdv,sdv,rrr,spt,prp,pdc,mpl,dpd,dbh,csh,csv,mbv,vrh,nph,smn,btt,rcm,hht,vpt,vsh,rhv,nnl,cls,vnm,pbm,hps,nhr,mdb,ntl,lml,trm,vss,htt,mps,ctl,sdm,nts,dms,bdt,spd,clc,lhl,mmt,lrt,lpm,dlh,mvl,vrl,btv,bps,ssb,dpp,lmp,sbc,cvc,srp,hrd,mlr,cvt,svr,cvn,ncp,tsp,mvc,rnb,rvp,hsr,mnh,vhn,lvt,tcr,nrd,mnb,vdm,cbt,tpc,vbt,pmv,nvl,vvc,mbl,mnm,mvt,pnv,ppt,scn,rmn,vts,lbt,pdd,ddl,vsn,trc,ccr,ddb,bnn,plb,tvd,vnr,rcp,phm,bsb,dvl,ldm,cpt,brn,tlt,vmd,hlm,lpv,thb,nmv,svn,shh,mch,sbn,mvd,vmr,pdl,cdb,drv,bvm,hhd,mbr,ccc,dmh,ptp,,tln,mtm,vnh,lpl,nvr,mmp,rrb,vns,cps,ndl,nml,nbn,rbr,vds,csc,mtv,tdh,vnn,tbv,pvl,drn,bdv,rmp,prt,cml,tcl,rdb,pvs,rmh,bhv,tmp,lpc,hst,hcv,btr,lmm,ptc,tbp,hrh,thc,vbd,tnv,vmn,cbm,dlm,hsh,nvb,rnn,dvv,rpd,drm,prb,crb,rcr,mdc,dvs,dbt,lmt,btm,rbn,mrt,vmt,hbc,rlc,dpt,bsh,vpm,ntr,rbm,rlm,drr,mtr,lrh,pmh,cds,rth,nmn,ndp,vpn,sts,srv,dtr,prd,tml,bpt,vpr,npt,mhb,mns,vvv,bnp,bmd,dcc,hlr,srt,bnl,pnb,dbl,dhv,vvh,pbh,dvh,pdv,hpc,nns,pvp,tnd,nlb,dmb,chn,rbv,ndt,pdn,vbr,rst,prl,svp,nvh,nsl,hpn,clh,vrp,mdm,cdd,spr,lmr,mlp,stl,rhr,vsl,mrl,dcn,lhn,nbv,bsm,dmd,nvc,hdv,hhp,ssm,cbs,dmt,hcm,blp,svc,trs,brp,vnv,dnh,ppm,npc,hmc,cbh,tvp,nhp,tdd,vbn,nmr,mls,rcb,hrl,mss,tnn,nsb,hds,rnd,vrt,hhn,ssr,vnp,hdb,lmn,mtp,nmh,dsn,cdt,snd,mbt,sht,nbr,hvs,shp,phn,nds,mcn,bvr,cbd,hhm,vvp,spp,nhh,pbr,mdl,btb,rdm,mtt,vth,ctv,prc,dhl,bcv,dns,tbr,dmn,crt,ppl,tsv,thd,dsh,dcv,ppd,ntd,lrc,dsv,rlp,tcd,bdm,std,hmt,bvd,pmt,tls,bnr,vrm,psm,dcr,nlm,rdn,msh,csl,snp,dps,drt,vht,pth,ppr,tcn,blr,mbn,tvn,bcc,dnl,tmr,dhp,cbp,ndb,cmm,pcd,ddr,blb,vsm,pnt,mpr,rvh,blv,csb,nhd,nrb,chr,chp,lvc,htl,cnb,dnc,pcv,lnc,ddv,nbm,nlr,npr,hmm,tbm,bmn,dpb,tld,snn,bnc,rss,prh,trh,dbs,rvm,spc,lht,dnv,vlh,tdv,smp,msc,vdd,hhb,pph,slm,rln,hns,brl,nhs,tvt,sdn,rhd,cbn,mbd,dld,tnb,dcs,cll,hnh,lnn,mpn,nll,vpl,srb,sdr,mmc,slb,ccm,mcm,tpp,tnc,lsc,cvm,ppp,btd,bhm,pcn,nsp,vlp,nhl,nmp,pcm,plm,nvt,shm,dhc,tsh,vhl,mdv,lbh,msm,lss,bbm,rsc,dlc,vhr,slt,rbt,hmv,nhc,ntn,chc,sdh,phv,nrv,rrc,mll,slh,ppc,ssd,mtl,srd,pdt,rds,nrs,bcs,cbb,dpc,ctt,svl,htc,nrn,rdc,lbd,mpt,hsd,nvd,nbh,rns,lrb,drl,slv,tcc,mhs,sln,hbs,smr,bbl,nbs,ddd,nsr,bdp,vhm,dtt,ncs,tbb,pvt,bvn,tcs,tms,vtr,dbn,nmb,cvp,snl,brd,chb,vsd,pdh,shs,lvn,tlm,cpr,plv,bch,mvv,mdh,crm,lmv,hsm,mts,ccb,pld,tnp,rvb,sbl,dlb,nhn,dct,bll,hpp,scv,ltt,nvp,cvb,sll,ncc,bhp,pvb,pht,snv,mms,ltd,bhb,lnh,pmp,tnr,trr,scb,tll,rpm,hlt,nmd,bsc,tvl,nrh,mhc,ldt,dcm,pmm,dsb,pbv,pvn,nst,cts,dvr,clb,nct,htb,cmp,shc,ntb,rbh,rvn,pbn,tsb,pnh,thm,ccs,spn,pmc,vtt,pdp,srr,hdn,mbs,sbd,htn,cmc,bcm,stn,cmv,vln,sld,bbd,lvd,vlb,vll,vcl,mmr,bhd,brr,nnc,hlb,dvb,bhh,cnm,tss,dtp,bmb,vcs,bpm,nnh,mhl,bmr,trl,mpv,rcd,vtc,mpc,ctd,rts,vsb,bpd,ldh,crd,rml,mcl,sbp,pmd,lpb,mmh,svb,plp,bcd,vrr,nmc,dhh,mph,vhc,lsv,pnd,hhc,pmr,npm,hpv,tmh,pbl,lhs,msb,vps,vsp,stv,nnr,pnm,sbv,prn,rld,sbm,sst,nnb,lnl,vrs,nnn,hsp,lvh,psv,dtn,php,vsc,hbl,cdp,tcp,mrn,lbn,shv,hmh,ttp,rpp,ndc,csp,bcl,tpt,mbc,lpt,tmb,vmp,nsh,thp,clr,hbd,bcp,lmh,rmv,bnv,brc,vls,ptv,scs,sbs,hcb,hlp,vpv,dlp,dnd,rsd,tpr,dsm,hdm,rcc,rbb,scc,ldp,bpl,rpr,lsm,dmr,nhm,msn,bsp,smb,ssh,phd,sds,mtn,ssv,ccn,lms,ncn,dll,vdc,smv,pds,hln,dpv,nvv,brv,blt,lbm,lhd,vsr,lbv,lnm,rhm,lpn,stm,cct,mvn,lbr,lmb,cvh,pps,cpb,shb,dss,dtd,phb,rmr,mdt,rch,csr,nps,thh,dvt,tlc,bth,tnh,str,dlt,nln,nhv,nbp,rrs,rcs,lvm,hcn,htp,llb,spm,lhb,mhh,mld,btc,dnr,spb,lhm,nnv,hvt,bcn,nnd,plr,hhl,scp,srh,ltn,nrm,tns,clm,nhb,lct,nbl,bst,cpl,tmd,vdb,ccl,cvd,mtb,rph,llt,lhr,shl,lns,hpr,tpl,rbc,ctp,blh,hrm,nss,ncb,mdr,dch,chl,ndv,ltl,llr,hdl,mdn,ncr,mnv,hnv,drb,pvc,mml,rcn,nbd,nht,tlh,bbs,brb,nlt,pcs,tmm,mdp,mbm,sls,hvc,vlv,nnm,tnt,hcp,vvb,ctn,bsl,mdd,tth,hnd,vnd,ctb,rrt,dbr,sms,lbc,vtl,ssl,tsn,ptr,rsh,smt,cdr,bln,dmm,lcc,crh,ncv,dmp,smd,pln,vtp,msp,ttd,dts,ncd,csd,dnp,lsp,prv,msl,rmt,cdl,hll,spl,rdv,mvm,ntm,cvs,tbl,chd,ttl,pms,tdc,rlt,cnd,vms,tbh,ppn,ptd,hnl,rnc,bnt,rrl,dsd,dbd,sdc,dpm,rlr,css,hpd,hnc,ccd,dsc,vvd,ndn,bdd,rdt,dhn,rtd,vvm,hvb,sdb,mrv,lts,lmd,cpp,mmd,tdn,tcv,cmh,rbp,hbr,dln,rtp,cth,mlt,lcs,tmt,sps,hcd,lps,vrv,lld,dnt,cpn,hbt,hbh,mhr,sdd,rps,nsv,trp,tvm,tct,pst,hrt,lbs,bdn,sss,hcr,rpl,trv,rpv,rdp,scr,nlc,bbr,rhs,dpn,vdv,bmh,vch,bbb,bdr,cvv,vmb,tbs,scm,chh,nch,hdp,sdt,tst,mbb,rvd,vnl,mpb,tcm,vcd,tmv,rrh,hss,ltr,lrs,bls,tsm,lrd,mcv,hml,pts,mpm,pvd,hrn,rnm,ntv,brm,dhm,bpp,ldc,ldd,rpn,srn,vbs,vct,bpn,lcl,mnp,dbv,rbs,ncl,vrd,ttv,bht,hmn,tbt,vbl,smc,stc,blm,vcm,hrc,dmv,bvc,rmb,tlv,rls,dvd,rrn,svt,pdr,nvn,snh,sml,cdn,bhr,psr,rrp,mcs,mlv,rnh,bbc,dsr,rtc,mbh,nlv,pbd,dmc,vtb,mrm,pll,rlb,cld,crv,vlc,bmm,crn,csm,hdt,mnl,rnr,rhb,dlr,plc,smm,hms,cnv,htv,bsd,ddt,hcl,vsv,thr,prr,dcl,vdp,ddp,chv,mmn,bml,lnv,vrc,mmb,drs,cmn,cns,cvr,dtb,tpb,hdc,lmc,cbl,ntp,vvl,slp,trt,pnn,msr,crs,hnb,dcd,pmn,mrd,cpd,mhm,rdr,vtm,ppv,bnh,brs,pdm,mlb,snm,rbl,hbm,pns,vvn,snb,llm,lsn,ssc,sbr,hsc,vvt,ttm,nsc,lbl,vbm,tlr,rhp,shn,mcc,hrb,ltv,bsv,crp,nnt,ptn,bmp,clv,llh,dsp,psh,drd,lsd,lrr,svs,rhc,mrh,dml,phh,sth,ndr,psl,mcp,ttt,bld,bbh,vml,lpd,rcv,ddh,hvn,vnc,sch,hnm,dbc,bts,nmm,pmb,rsb,mmm,bhn,nrr,mrr,vpd,mst,vst,cnc,dhs,dvc,nbb,rcl,hbn,mds,psp,nlh,bhl,ctc,mpp,thl,hlc,lsl,nls,hmd,ccv,nth,mrs,lcd,cht,bbt,bms,cbv,bdc,chm,plt,vtn,ntt,lrl,bss,hdr,pvm,ldl,lvv,bbp,rvv,bdb,pnl,vtv,blc,rhh,btn,bnm,chs,rsp,hlv,rmm,tbd,vdh,ctr,tsl,lvl,cmb,vhb,pbs,svh,mlh,cpc,hbb,tlp,vrb

Estas son las 1701 combinaciones posibles. Que conste, solo hay 1728 (123) combinaciones dadas las consonantes. Es decir, hay gran probabilidad de tener 9-10 letras como resultado final.

Paso 3

Tenemos que formular las combinaciones de entre las letras que sabemos son válidas (por ejemplo, BCDH). Ende necesitamos las combinaciones de tres de esas letras (por ejemplo, BCD, BCH, BDH, CDH). Y de ahí necesitamos las combinaciones, con duplicados, de ellas (BBB, BBC, BBD, BCB, BCC, BCD…) que son 27. Tenemos que probar cada una de estas 27 combinaciones para ver si figuran en la lista que resultó de paso 2. Si cualquier no aparece, pues podemos descartar aquella combinación de letras al principio del proceso.

use v6;
my $former = ""; # insert the comma-delimited string from Paso 2
my %valid;
%valid{$_}++ for $former.split(",");
my @results;
my @consonants = ; # Ñ is not an option
for 3..@consonants.elems {
  SOLUTIONSET:
  for @consonants.combinations($^depth) {
    for $^solutionSet.combinations(3) {
      for ($^three.values,$^three.values,$^three.values).flat.combinations(3).unique {
        next SOLUTIONSET unless %valid{$^combination.join("")}:exists;
      }
    }
    @results.push($^solutionSet.join(""));
  }
}
say @results.join(",");

Después de ejecutar este script, tenemos la respuesta final:

bcd,bch,bcl,bcm,bcn,bcr,bcs,bct,bdl,bdm,bdn,bdr,bds,bdt,bhl,bhm,bhn,bhr,bhs,blm,bln,blr,bls,blt,bmn,bmr,bms,bmt,bnr,bns,bnt,brs,brt,bst,cdl,cdm,cdn,cdp,cdr,cds,cdt,cdv,chl,chm,chn,chp,chr,chs,clm,cln,clp,clr,cls,clt,clv,cmn,cmp,cmr,cms,cmt,cmv,cnp,cnr,cns,cnt,cnv,cpr,cps,cpt,crs,crt,crv,cst,csv,ctv,dlm,dln,dlp,dlr,dls,dlt,dlv,dmn,dmp,dmr,dms,dmt,dmv,dnp,dnr,dns,dnt,dnv,dpr,dps,dpt,drs,drt,drv,dst,dsv,dtv,hlm,hln,hlr,hls,hmn,hmp,hmr,hms,hnp,hnr,hns,hpr,hps,hrs,lmn,lmp,lmr,lms,lmt,lmv,lnp,lnr,lns,lnt,lnv,lpr,lps,lpt,lrs,lrt,lrv,lst,lsv,ltv,mnp,mnr,mns,mnt,mnv,mpr,mps,mpt,mrs,mrt,mrv,mst,msv,mtv,npr,nps,npt,nrs,nrt,nrv,nst,nsv,ntv,prs,prt,pst,rst,rsv,rtv,stv,bcdl,bcdm,bcdn,bcdr,bcds,bcdt,bchl,bchm,bchn,bchr,bchs,bclm,bcln,bclr,bcls,bclt,bcmn,bcmr,bcms,bcmt,bcnr,bcns,bcnt,bcrs,bcrt,bcst,bdlm,bdln,bdlr,bdls,bdlt,bdmn,bdmr,bdms,bdmt,bdnr,bdns,bdnt,bdrs,bdrt,bdst,bhlm,bhln,bhlr,bhls,bhmn,bhmr,bhms,bhnr,bhns,bhrs,blmn,blmr,blms,blmt,blnr,blns,blnt,blrs,blrt,blst,bmnr,bmns,bmnt,bmrs,bmrt,bmst,bnrs,bnrt,bnst,brst,cdlm,cdln,cdlp,cdlr,cdls,cdlt,cdlv,cdmn,cdmp,cdmr,cdms,cdmt,cdmv,cdnp,cdnr,cdns,cdnt,cdnv,cdpr,cdps,cdpt,cdrs,cdrt,cdrv,cdst,cdsv,cdtv,chlm,chln,chlr,chls,chmn,chmp,chmr,chms,chnp,chnr,chns,chpr,chps,chrs,clmn,clmp,clmr,clms,clmt,clmv,clnp,clnr,clns,clnt,clnv,clpr,clps,clpt,clrs,clrt,clrv,clst,clsv,cltv,cmnp,cmnr,cmns,cmnt,cmnv,cmpr,cmps,cmpt,cmrs,cmrt,cmrv,cmst,cmsv,cmtv,cnpr,cnps,cnpt,cnrs,cnrt,cnrv,cnst,cnsv,cntv,cprs,cprt,cpst,crst,crsv,crtv,cstv,dlmn,dlmp,dlmr,dlms,dlmt,dlmv,dlnp,dlnr,dlns,dlnt,dlnv,dlpr,dlps,dlpt,dlrs,dlrt,dlrv,dlst,dlsv,dltv,dmnp,dmnr,dmns,dmnt,dmnv,dmpr,dmps,dmpt,dmrs,dmrt,dmrv,dmst,dmsv,dmtv,dnpr,dnps,dnpt,dnrs,dnrt,dnrv,dnst,dnsv,dntv,dprs,dprt,dpst,drst,drsv,drtv,dstv,hlmn,hlmr,hlms,hlnr,hlns,hlrs,hmnp,hmnr,hmns,hmpr,hmps,hmrs,hnpr,hnps,hnrs,hprs,lmnp,lmnr,lmns,lmnt,lmnv,lmpr,lmps,lmpt,lmrs,lmrt,lmrv,lmst,lmsv,lmtv,lnpr,lnps,lnpt,lnrs,lnrt,lnrv,lnst,lnsv,lntv,lprs,lprt,lpst,lrst,lrsv,lrtv,lstv,mnpr,mnps,mnpt,mnrs,mnrt,mnrv,mnst,mnsv,mntv,mprs,mprt,mpst,mrst,mrsv,mrtv,mstv,nprs,nprt,npst,nrst,nrsv,nrtv,nstv,prst,rstv,bcdlm,bcdln,bcdlr,bcdls,bcdlt,bcdmn,bcdmr,bcdms,bcdmt,bcdnr,bcdns,bcdnt,bcdrs,bcdrt,bcdst,bchlm,bchln,bchlr,bchls,bchmn,bchmr,bchms,bchnr,bchns,bchrs,bclmn,bclmr,bclms,bclmt,bclnr,bclns,bclnt,bclrs,bclrt,bclst,bcmnr,bcmns,bcmnt,bcmrs,bcmrt,bcmst,bcnrs,bcnrt,bcnst,bcrst,bdlmn,bdlmr,bdlms,bdlmt,bdlnr,bdlns,bdlnt,bdlrs,bdlrt,bdlst,bdmnr,bdmns,bdmnt,bdmrs,bdmrt,bdmst,bdnrs,bdnrt,bdnst,bdrst,bhlmn,bhlmr,bhlms,bhlnr,bhlns,bhlrs,bhmnr,bhmns,bhmrs,bhnrs,blmnr,blmns,blmnt,blmrs,blmrt,blmst,blnrs,blnrt,blnst,blrst,bmnrs,bmnrt,bmnst,bmrst,bnrst,cdlmn,cdlmp,cdlmr,cdlms,cdlmt,cdlmv,cdlnp,cdlnr,cdlns,cdlnt,cdlnv,cdlpr,cdlps,cdlpt,cdlrs,cdlrt,cdlrv,cdlst,cdlsv,cdltv,cdmnp,cdmnr,cdmns,cdmnt,cdmnv,cdmpr,cdmps,cdmpt,cdmrs,cdmrt,cdmrv,cdmst,cdmsv,cdmtv,cdnpr,cdnps,cdnpt,cdnrs,cdnrt,cdnrv,cdnst,cdnsv,cdntv,cdprs,cdprt,cdpst,cdrst,cdrsv,cdrtv,cdstv,chlmn,chlmr,chlms,chlnr,chlns,chlrs,chmnp,chmnr,chmns,chmpr,chmps,chmrs,chnpr,chnps,chnrs,chprs,clmnp,clmnr,clmns,clmnt,clmnv,clmpr,clmps,clmpt,clmrs,clmrt,clmrv,clmst,clmsv,clmtv,clnpr,clnps,clnpt,clnrs,clnrt,clnrv,clnst,clnsv,clntv,clprs,clprt,clpst,clrst,clrsv,clrtv,clstv,cmnpr,cmnps,cmnpt,cmnrs,cmnrt,cmnrv,cmnst,cmnsv,cmntv,cmprs,cmprt,cmpst,cmrst,cmrsv,cmrtv,cmstv,cnprs,cnprt,cnpst,cnrst,cnrsv,cnrtv,cnstv,cprst,crstv,dlmnp,dlmnr,dlmns,dlmnt,dlmnv,dlmpr,dlmps,dlmpt,dlmrs,dlmrt,dlmrv,dlmst,dlmsv,dlmtv,dlnpr,dlnps,dlnpt,dlnrs,dlnrt,dlnrv,dlnst,dlnsv,dlntv,dlprs,dlprt,dlpst,dlrst,dlrsv,dlrtv,dlstv,dmnpr,dmnps,dmnpt,dmnrs,dmnrt,dmnrv,dmnst,dmnsv,dmntv,dmprs,dmprt,dmpst,dmrst,dmrsv,dmrtv,dmstv,dnprs,dnprt,dnpst,dnrst,dnrsv,dnrtv,dnstv,dprst,drstv,hlmnr,hlmns,hlmrs,hlnrs,hmnpr,hmnps,hmnrs,hmprs,hnprs,lmnpr,lmnps,lmnpt,lmnrs,lmnrt,lmnrv,lmnst,lmnsv,lmntv,lmprs,lmprt,lmpst,lmrst,lmrsv,lmrtv,lmstv,lnprs,lnprt,lnpst,lnrst,lnrsv,lnrtv,lnstv,lprst,lrstv,mnprs,mnprt,mnpst,mnrst,mnrsv,mnrtv,mnstv,mprst,mrstv,nprst,nrstv,bcdlmn,bcdlmr,bcdlms,bcdlmt,bcdlnr,bcdlns,bcdlnt,bcdlrs,bcdlrt,bcdlst,bcdmnr,bcdmns,bcdmnt,bcdmrs,bcdmrt,bcdmst,bcdnrs,bcdnrt,bcdnst,bcdrst,bchlmn,bchlmr,bchlms,bchlnr,bchlns,bchlrs,bchmnr,bchmns,bchmrs,bchnrs,bclmnr,bclmns,bclmnt,bclmrs,bclmrt,bclmst,bclnrs,bclnrt,bclnst,bclrst,bcmnrs,bcmnrt,bcmnst,bcmrst,bcnrst,bdlmnr,bdlmns,bdlmnt,bdlmrs,bdlmrt,bdlmst,bdlnrs,bdlnrt,bdlnst,bdlrst,bdmnrs,bdmnrt,bdmnst,bdmrst,bdnrst,bhlmnr,bhlmns,bhlmrs,bhlnrs,bhmnrs,blmnrs,blmnrt,blmnst,blmrst,blnrst,bmnrst,cdlmnp,cdlmnr,cdlmns,cdlmnt,cdlmnv,cdlmpr,cdlmps,cdlmpt,cdlmrs,cdlmrt,cdlmrv,cdlmst,cdlmsv,cdlmtv,cdlnpr,cdlnps,cdlnpt,cdlnrs,cdlnrt,cdlnrv,cdlnst,cdlnsv,cdlntv,cdlprs,cdlprt,cdlpst,cdlrst,cdlrsv,cdlrtv,cdlstv,cdmnpr,cdmnps,cdmnpt,cdmnrs,cdmnrt,cdmnrv,cdmnst,cdmnsv,cdmntv,cdmprs,cdmprt,cdmpst,cdmrst,cdmrsv,cdmrtv,cdmstv,cdnprs,cdnprt,cdnpst,cdnrst,cdnrsv,cdnrtv,cdnstv,cdprst,cdrstv,chlmnr,chlmns,chlmrs,chlnrs,chmnpr,chmnps,chmnrs,chmprs,chnprs,clmnpr,clmnps,clmnpt,clmnrs,clmnrt,clmnrv,clmnst,clmnsv,clmntv,clmprs,clmprt,clmpst,clmrst,clmrsv,clmrtv,clmstv,clnprs,clnprt,clnpst,clnrst,clnrsv,clnrtv,clnstv,clprst,clrstv,cmnprs,cmnprt,cmnpst,cmnrst,cmnrsv,cmnrtv,cmnstv,cmprst,cmrstv,cnprst,cnrstv,dlmnpr,dlmnps,dlmnpt,dlmnrs,dlmnrt,dlmnrv,dlmnst,dlmnsv,dlmntv,dlmprs,dlmprt,dlmpst,dlmrst,dlmrsv,dlmrtv,dlmstv,dlnprs,dlnprt,dlnpst,dlnrst,dlnrsv,dlnrtv,dlnstv,dlprst,dlrstv,dmnprs,dmnprt,dmnpst,dmnrst,dmnrsv,dmnrtv,dmnstv,dmprst,dmrstv,dnprst,dnrstv,hlmnrs,hmnprs,lmnprs,lmnprt,lmnpst,lmnrst,lmnrsv,lmnrtv,lmnstv,lmprst,lmrstv,lnprst,lnrstv,mnprst,mnrstv,bcdlmnr,bcdlmns,bcdlmnt,bcdlmrs,bcdlmrt,bcdlmst,bcdlnrs,bcdlnrt,bcdlnst,bcdlrst,bcdmnrs,bcdmnrt,bcdmnst,bcdmrst,bcdnrst,bchlmnr,bchlmns,bchlmrs,bchlnrs,bchmnrs,bclmnrs,bclmnrt,bclmnst,bclmrst,bclnrst,bcmnrst,bdlmnrs,bdlmnrt,bdlmnst,bdlmrst,bdlnrst,bdmnrst,bhlmnrs,blmnrst,cdlmnpr,cdlmnps,cdlmnpt,cdlmnrs,cdlmnrt,cdlmnrv,cdlmnst,cdlmnsv,cdlmntv,cdlmprs,cdlmprt,cdlmpst,cdlmrst,cdlmrsv,cdlmrtv,cdlmstv,cdlnprs,cdlnprt,cdlnpst,cdlnrst,cdlnrsv,cdlnrtv,cdlnstv,cdlprst,cdlrstv,cdmnprs,cdmnprt,cdmnpst,cdmnrst,cdmnrsv,cdmnrtv,cdmnstv,cdmprst,cdmrstv,cdnprst,cdnrstv,chlmnrs,chmnprs,clmnprs,clmnprt,clmnpst,clmnrst,clmnrsv,clmnrtv,clmnstv,clmprst,clmrstv,clnprst,clnrstv,cmnprst,cmnrstv,dlmnprs,dlmnprt,dlmnpst,dlmnrst,dlmnrsv,dlmnrtv,dlmnstv,dlmprst,dlmrstv,dlnprst,dlnrstv,dmnprst,dmnrstv,lmnprst,lmnrstv,bcdlmnrs,bcdlmnrt,bcdlmnst,bcdlmrst,bcdlnrst,bcdmnrst,bchlmnrs,bclmnrst,bdlmnrst,cdlmnprs,cdlmnprt,cdlmnpst,cdlmnrst,cdlmnrsv,cdlmnrtv,cdlmnstv,cdlmprst,cdlmrstv,cdlnprst,cdlnrstv,cdmnprst,cdmnrstv,clmnprst,clmnrstv,dlmnprst,dlmnrstv,bcdlmnrst,cdlmnprst,cdlmnrstv

Como se puede ver, el tamaño de las combinaciones va subiendo (porque empieza con grupos de tres, después de cuatro, etc). Al final de todo, hay tres grupos con NUEVE letras:

  • B C D L M N R S T
  • C D L M N P R S T
  • C D L M N R S T V

Para los interesados, con 9 letras, hay 9!/6!·33 combinaciones posibles (o 13608), cada una de las cuales puede formar una palabra según las reglas.

| improve this answer | |
  • Si tienes problemas con tu conjunto de palabras, puedes probar con la lista de palabras enlazada por fedorqui. Son muchas menos, y así al menos probarás el algoritmo. Si consigues que termine en un tiempo aceptable, puedes probar después con una lista más amplia. – Charlie May 4 '17 at 6:11
  • Although, I suppose first I should let it run for BBB/CCC/DDD/FFF/GGG etc. If any of those fail, I can simply remove them from consideration – user0721090601 May 4 '17 at 11:56
  • 1
    I like your idea of pruning the tree of possibilities in a smart way, at the beginning. – aparente001 May 5 '17 at 5:13
  • Tengo mi propio algoritmo desarrollado que me encuentra también un conjunto de 9 letras (creo que es justo el primero de los que tú indicas) cuando lo aplico sobre la lista completa de más de un millón de palabras. Sin embargo, si lo aplico sobre la lista de fedorqui de 80K términos, me encuentra un conjunto de 10 letras, lo cual me extraña dado que es un conjunto mucho más reducido. ¿Te pasa lo mismo? – Charlie May 5 '17 at 6:25
  • @CarlosAlejo todavía no lo he intentado, pero como mencioné, de nuestro conjunto reducido de consonantes había 1728 combinaciones posibles, de las cuales 1701 eran válidas. Obviamente, si hubiese 1728, la solución sería las 12 consonantes. De 1701 a 1728 no es mucho, y adicionando un par de palabras que coincidan con las combinaciones inválidas en mi prueba podría hacer la diferencia. Solo hace falta un sufijo o algo para hacer toda la diferencia (véase el ejemplo de zarzuelazo que no figura en nuestra lista y por tanto no tenemos constancia de ZZZ, pero vamos, es plenamente válida) – user0721090601 May 5 '17 at 14:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.