FindHoles.js

tCategories = {
    "C": "b,d,dz,g,ġ,gh,h,j,k,k',kh,l,m,n,p,p',q,q',r,s,ş,t,t',ts,ts',tş,tş',v,z".split(","),
    "V": "a,ạ,e,i,o,u".split(",")
}

///////////////////////////////////////////////////////////

// the entire lexicon of Old Mtsqrveli compressed into one, space-delimited line
var sWords = "abi abmiot'i ạbts ạbtsila adele adhava adkhlo ạdrelva adumi ạdzproqar ạdzprova aes aghdgeva aghleva aghsmsglema aghsmsgleva ạgoli ạjalva aje akhali akhola ạlạ alt'kạreşva alt'kạreşvo alt'kạrva amarteva andebsva ani anitşmenra antiova ap api apjeva apts ạr arav aravola aravtsmegduli ard ardaba ardzġvoş ạrgạ ạrgạli arhaz arin arioa ạrjạl ạrkos ạrkots'ạli ạrlo ạrt artova artsmdo aruli ạsb ạşqạm ạstuli atoni ạtşạ atuliş ạvạlos avli avt azkhrane azkhrava ạztạr azva ba baġrạj bagrat bạntsava bạri barqa başvke batomi bdov bdzerala bdzeraldagoma bdztots begeomima begeva bel beştova bgera bgeti bghi bghloni bghola bikhi bkhievo bkhliva bkhvseba braşi braşoli brba brdebsva brdzola brebsva brivgha brivghebiva brivghi brmava brts'eva brts'q'inavs brve brveli brvjema brvmotmelova btmirdzma btmire btsqalavs btşroşin btşrova Budạpasetis bul bvareti bvlino bvlinoba bzeleunamva bzeleva bziniva bzq'e bzvo bzvoma da- dạ dados dag- dagoş te daidebişin daidebiva daisi dameti Damotsa damşalva daova daqtsva dari darkht'iva darmiot'i darupts'srt'ma dasaniva daşkham daşlieva datskeliva dats'kiva dạtşnoma datşrema datşreva dbrebesva dbres debi dede dereva dgareva dghiş dgileva dgova di- didanatşeni diemşili digagemajemi digagemi dighlobi dimt'eli dimtsetsvatş'rebi dimtştemtani diobani dirteli disakvi diteri dkha dkhliva dmelo dmova dno doda dona donapreliva dor druva duguli dvagerts dviş dvişnen dzala dzamova dzan dzebuli dzge dzghạnd dzgherba ghvenili dzghva dzgoni dzidi dzilva dzkhuli dzmoba dznebula dzneva dzol dzora dzrebva dzto dzuzegi -eb- edza eger ehit ehitne ek'- ek'dimt'elimpova ekhneva ek'şnola ek'ter ek'vse eld elt eltaba ema emo emşi ena ereva erguli eri eromema ert erta ertjeva ervde ervdempova ervdene eskats eşva et etseva et've euni ev eva evjevo ġa- gabrtsema gabrtseva gadkheva gadkhunamila gạdz gạdzotni gagemajema gagemajeva gageva gaisreva ġajarva ġajeva gạla ġạmạ gamari gamoja ġams gana gạnạd gạndza ġanieva gankhetliva gạntsva ġaraq'ava garega gariva gaşaula gaşvnelo ġatavsova gatsva ġaverts'eva ba jạpreght'ova ġavetşova gavola ġavraq'ava gavs gbeli gdmebova gdmo ġdseva gduliva gdza gdzabola ġdzạmi ġdzạmi ninạ gdzra gdzrola geli gelmiot'i gemits ġena gera gerts ġevli gh- ghabsva ghadiava ghak'avs ghạli ghạlima ghani ghar ghde gherian gherianebsva ghevma ghirsebi ghis ghloba ghme- ghmedaidebiva ghmotebiva ghnova ghobduli gholuri ghq'arova ghrạlova ghreba ghrnova ghrto ghtiova ghtşmelova ghtsova ghturva ghumeli ghur ghvạr ghvạrjeva ghveni ghvenidgareva ghvi giạri ginva girgi giurt ġkheta ġkhro ġkhruba ġletiva ġmavi gmbrava gmehova ġmer ġmihiova ġmio ġmotşva ġmtş'ạlva gmur ġmztava gni gnva goneva gordikhruva gordva ġori gorna ġort'q'va ġova ġovar ġovrebsva grge gro grojeva ġtsareva gtvava guliva ġundza ġuşur guza gva ġvạdo gvalova gvạmde ġvạr gvdelo ġver ġvivta ġvivtaba ġvlo ġvoni gvqi ġvrepts ġvsotar ġvsova ġzar gznev ha hae- haedgova haenihova hạlova hara hạreva hatar hatskhva hạz helez hergova hiova hiova adkhat hiova otvlid histạva hizd ho hod hornva idva igan iganaşmine igt ikạlto ikhre ikhruva ik'meva ik'ura ilava ilomi imsviva ina ioda iodaghema ipra iprala iq'os ir teo iravs irula iruli iş- isari işbrdzova işdaşliva işdgova işdruva işeşin iseskatsva işkạd işk'edulebiva işk'elkrva iskerdva işkerdva işk'vanvo işmġnova işmikhulva işoktsiva işomiva işpgholamdova işqova işsidva istavnebiva isteli işuliva işvitsva itar it'ev iti itroq'noşvo itşi itşk'vanva ivdor ivela ivelebiva ivkhe ivkheghloba ivs iz izjeva izrail izula jai jana jạpreght'ova jạpruba jạpruts'ạli jạpruts'ạlidavqar jaqtsva jạroş jartsva jasti jatşve jạvre jazi jega jegoli qmirạ jemei jiarva jiomavạn jiova jirusạlemi jmil jmora jmur jneoni jneva joha johaeldi joli jolmiot'i jom jora jrdzo jrta jruts'nil jruts'nilne juri jurişin juva jvar jvari aborul Jvari magrulvis jveba jvei jvini jvloha k'ar Kạrdzimekhrạ kạrdzkạ kari karkar kạrkiva k'aşk'i katova k'ats k'edula k'edulebiva kedz kedzukhi k'elkrva ker k'erava kerd k'erk'eti kersam kertş kertşdago kh khada khalosani khalosanine khari khari rdzema kharine kharsva khdzar khemo khest'i khest'ila khev khlat'va khmurdavi khmuri khmuridavs khna khntso kholo khorti khrạt'homa Khrista khristabzvo Khristabzvosam khrova khubi khusli khvits'i khvp'i kird k'marva k'marvo k'miva kneva kobula kolke kordva k'ova kroni kuna kundema kundeva k'up'va kurd kurdova kurdovo kurdovoba kurke kurmtsava kurmtso k'vanva kve k'verkhi kvro ladz lạjvro lạjvroma lakebiva lana lanaba lari larijeva laşegava lạsrva latşari lat'var lavs lebtşima lege leva lva mạdạgoma mạdạgova madav mạdztrạl magos magrulva mạjatva makhlomạrna mạlte mạmitsakvosam mamshi mạmtsva mana maraji maraji ut'q'mevo mạrạs mardavs mark'e marq'mevo marşva martsve maşkola maşkoli mạştova mat'ova matş mạts mdadạ mdahir mdareva mde mdigmats'ạli mdigva mdkart mdme mdmejeva mdnova mdtghaz mdveri mdzo meda medbrebesva megduva megholi mekhrạ melaeli meli melistavnebiva meoma meomela meova mepe mera meşiva met'a meteva metsikhvo mevari mevt mġạlova mghera mghoni mghrạt mghrạtikhubima mghva mgnedza mġnoba mġnojeva mgreli mġrvtso mgurva mi- mielba mielsạ mikhebuliva mikhula mino minola mioba miot'i mirmeva mirmevo misạ mit'ebeva mits'an mk'a mkare mk'eva mkhare mkhedveli mkherdova mkhlimpova mkhline mkhliti mkhrava mkhreduli mkna mkral mkrebalva mkreġoma mkreġova mk'tş'espova mkvasi mkvat mk'vdebiva mnişeva mo- modonebiva mogankhetliva moġmtş'ạlva moma momo moqdzeva mormi moti motmelova motş'ilimpova mots'orilebiva moul movtsalebiva mparevs mparveli mparveva mp'ivs mplobsva mp'ts'eva mqareva mqarevo mqeho mq'isiera mq'opi mqşama mqşava mq't'ivs mq'ts'e mq'tşeva mqva mq'var mq'vili mqvlet'i mrkhi mrtelova mrzva msar mşimuni msneva msopli msqi mşvạt mşvildi msvili msvili ninạ mta mtaki mtani mtanine mt'ạreva mt'eli mt'evs mtiane mtkhvevaşi mtkhvevaşine mt'k'inevuli mt'k'oni mtliani mt'o mtokvi mtosma mtosva mtosvi mtosvine mt'ruli mts- mtş'abs mtsali mts'ali mts'alimpova mtsare mtsaz mtsbtmirdzmidamşal mtsdadid mtsdats'ki mtşema mtşemaġvivtaba mtşemdo mtsetsvatş'reba mtşeva mtşevo mtşevoba mtsġataviso mtshorn mtsimsveba mtsjiar mtşkura mtsne mtşo mtşola mtşolasako mtşolasam mtşoskhivi mtsqrạ mtsqrveli mtssakhedzmidamşal mtşteva mtstş'eno mtveli mtvrali mtvralimpova mtvrghtsova munga muq'o mzeli mzkhal nạbi nạbi- nais nakhri nạkhvạr nạkola naova naq'ar nari naşi nats natsdago natshatar natsi mdmela ndmirni -ndz- ndzelạ neiva nevt nid nieva nihova nilova nilovo nimdzi nimkhli nimskhet'i ninạ nino nitş nitşmot nkghri nkhriadhava norma norva notghe notghetsạ nt'miş ntsiro ntşoma nuriva oba od odz- okha okhli okhro okhroli oktsi ol oliş oljeva olma olmats'ạli onzva orav ori orma ornạli ort' ortghi ortşva orul osi oskeva oşp oşpi otni otnima otnimats kh ts'ạlimats otni-ts'ạli otsa otşsebiva otşsi otvli ova ovda ovs ozan pạgha p'aghtova pạkor p'ani pạnt'ova par p'arak'eva p'ari p'arine p'erlova p'io p'irev p'itil pleda plei pogạ p'oki p'okordva pona prekova preliva prq'ts'eva prta prtebava p'tşt'oni p'tşt'va p'uli pvreva qạ- -ş qạmşi qar qarsạli qạrtoş qdzeva q'dzt'eva qema qemdva qetsma meomi qetsva q'ipts'la q'iq'ova qitsda q'jrma q'jroni qmạ qmadi qmạjeva qmar Qmarola qmartur qmel qmetava qmha qmhats'ạli qmhats'ạlima qmirạ q'mtla q'mtlebiva qmtoma qmtova q'mtş'ova -qn- qoşva q'ov qova qrhạ qrma qrtnạ qrva q'smi q'smiot'i q'sveli qşvo qtşe q'tsmina q'tsvoni q'uha q'uhotni quntsi q'uq'uli quri quridavs qvar q'vdiadiva qvela rạbtş'i rad radoli rae raq'ava rạtşomi rbneva rdev rdgala rdveba rdzema rdzeva rdznioni rdznioni adkhanen rdzniva retskhva rgava rghebdạ rghemeva rghova rghuno rieli rip'al risula risva rkhab rkhe rkhilva rkhneva rk'ida rkmena rkova rmgadi rmip'ova rmnebiva rmni Roma rqopva rsạ rtela rt'q'va rts'a rtşeva rtspeva rtspeva khvp'is ruk'an runi rupts'i rupts'srt'va rus ruti ruvạli rve rvno rzeva rzli rzqạrebiva sadova sadzoba saere sakali sakhe sakhedzma sakhejeva saktsla sakvo sakvosam sạmạla şạmdola samepo şạmi samiha samihane samqạre samsverkhi samt'o saniva sanja sạnqe sạpliva sapteli sạrep'i sarev sark'ala sạrmo sartola sartva şạrva sasmeli sạtkelos satkhva satş'a satşari sats'i sats'osumi sauli sạvsli şedzlova şeġạma şeġạva şema şen- şenbege şenetşi şenghrna şenomdo şenova şenrdze şentsmeho serm şevseba sidva şini- şiniş sipi sisk'i sist'ula sitsneva şiv skhivi slduva şme- şmeġmihiova şmets'q'ariva şmit'i şmiva şnola şnova so şoba sohaş soşmiot'i soşvi spasva sqamts sqtsne sqtsnebeva srt'va şude sudgileva sula şuli sumeva suo sup'i suruva sust'ili svamps svan şvar şvei şveni şvenidavs şvenimats arghebdi svġo şvili şvimz şvir svkhulidavs şvnelo svre svreba şvtse şvtsemormebiva svtsheli svtsheva svumi şvuri t'ạd t'ạdloba t'ạdola tadzrvo tadzrvola tadzrvosamema tadzrvuli tagi takht'i t'ani taq'vani tarebs tarebsjeva tatevs tats'e tatsebs tatuli t'ava tạvạd tạvạdipra tavisola tavsoli tavsova tbiliva tbiri tbleva tbrtstova t'dzre t'ebva teghirna tegir t'ekhvmiva tel- telapledatsva telervdema telervdeva telhova teo teove tera terjvạl t'erva tesmek'i teti t'etri t'ets'i tets'ma tevze tghandi tghas tgheskatsva tghorva tkhevadi tkhit'ova tkhmeva tkhsi t'k'mali t'k'nola t'k'nova tkoni t'k'şuli tkva tma tmelova t'meri t'mşạva tmşeva t'mverkhova t'na tnạli tojol tolova t'om t'ots'e t'q'ineba t'qts've t'q'upebivo t'q'va tra treti trha tronuva tsala tsalaotniş tsalebiva ts'ạli -ts'ạli ts'ạli mdmeghe ts'ạlima ts'ani tsạq'ova tş'areva ts'ari tş'ạto tşdequli ts'eba tşelạ tşem tşemi tşemiokhliva tsemova tşeno tşenoba tş'enova tş'epleva tş'epva tşetşri ts'eva tşgvra tşida tş'ili tşin tşişi ts'iti ts'itijveba ts'itijveba oruli ts'ivri ts'ivrişin ts'k'apva tş'keli ts'keromiş tskhae tskhaltova tşkhenova tşkhenuli tşkhieva tşkhrdebuli tskhri ts'khrik'ạ tskhurova ts'kiva ts'k'mena tsk'ugha ts'mado tsmehova tş'mevti tşmi ts'mikheva tşmiot'i Ts'mirisam tş'mlira ts'mrde tşneva tş'nimi ts'odeba ts'ogli ts'ok'ni tş'oqtş ts'ori ts'orila ts'orilebiva tsovanet'i tşovar tsoveba ts'pens ts'p'ni ts'q'arima ts'q'ariva ts'q'eba ts'q'rveva ts'q'uli tşra ts'rdari tşrdilova ts'relevro tsrolaghloba tsrova tş'smeva ts't'keva tst'o ts'ubari ts'ubarine tşutşi tsva tsvan tsvanebola tsvanebsva tşvar tş'vera ts'vina tşvino tsvlo tsvlohatar tsvo tsvoba ts'vroba tur t'ut'i t'var t'vas'i t'vasliva tvaşt' tvazkạrkiva tvazkạrkivo t'vet'gheva tvi tvilisi t'vilova tvira t'vis tvmiot'i t'vrạlo t'vrjma t'vrjva tvro u ubi- udrạlo udvar uġạr ughara uhar ukhi uk'neli uli umerva un- una undiaghleli unpari unt'meri up'alidavs uptşmova uqtsva uq'vkhots ur urbnisi ure urjul uroş urt urvni uşvalova ut'q'meva utskeli utşnov utşnovsumi uts'q'oda uvdova uvis uvisdgooni uvli uvlimomas uvmes uvmetsova v- vagdal vagdaljeva vaghras vali vama vamba vạnt'ma vạr vardza varkan vats vatş'ar vdạ vdareva vdzkeva venova verts' verts'eva vet'eli vetşova videts vin vitsva vkart vk'ava vk'meva vne vqa vrk'eli vrskhebiva vşeli vsgeva vsrt'ma vsrt'oni vsrt'va vsulebiva vtghaz vulebiva vulebivo vuli zạd zạdulebiva zạduli zagola zagova Zan zanidavs zar zarmk'vdebiva zeghe zeghva zeli zema zepuri zepurjevo zeva zi ziani zirmi zoriba zrme zrmeli rkhab zughali zuli zuni zurtva zuti zvel zveli zvisva";
var tWords = sWords.split(" ");

// returns a dictionary sorted by value in descending order
// (otherwise by default dictionaries are unordered, but will display by keys in alphabetical order)
// (from StackOverflow)
function sort_object(obj) {
    items = Object.keys(obj).map(function(key) {
        return [key, obj[key]];
    });
    items.sort(function(first, second) {
        return second[1] - first[1];
    });
    sorted_obj={}
    items.forEach(function(v) {
        use_key = v[0]
        use_value = v[1]
        sorted_obj[use_key] = use_value
    })
    return(sorted_obj)
}

// returns the number of matches in the lexicon of each segment that matches sPattern
function Stats(sPattern) {
    let tCombos = expandCategories(sPattern); // get all combinations that fit the pattern
                                              // e.g. if sPattern = "tV", then this returns
                                              // ["ta","tạ","te","ti","to","tu"]
    let tOut = {};
    for (let i = 0; i < tCombos.length; i++) {
        tOut[tCombos[i]] = 0;
    }
    // sort the combinations by descending length*, then smoosh into a regex
    // (* since some of the consonants are digraphs, e.g. "gh", and regexes match the first thing they can,
    //    if we don't force it to try to match longer combinations first, it would never match e.g. "agh" -
    //    that would always be counted as a match for "ag".)
    let re = new RegExp(tCombos.sort(function(a,b) { return b.length - a.length }).join("|"), "g");
    while (result = re.exec(sWords)) {
        tOut[result[0]] = tOut[result[0]] + 1;
    }
    return tOut;
}

// the same as above, except sorted by value in descending order
function OStats(sPattern) {
    let tOStats = sort_object(Stats(sPattern));
    let str = '{\n' + Object.getOwnPropertyNames(tOStats).map(key => `  ${key}: ${tOStats[key]}`).join('\n') + '\n}';
    console.log(str);
}

// given some pattern ABC, find combinations of ABC that don't appear in the lexicon, even though AB and BC individually do
function FindHoles(sPattern) {

    let tPattern = Stats(sPattern); // results for search on "ABC"
    let tTop = Stats(sPattern.substring(0,2)); // results for search on "AB"
    let tBottom = Stats(sPattern.substring(1)); // results for search on "BC"

    let tOut = [];

    for (let sKey in tPattern) { // for each "ABC" we tallied up the results for,
        let sTop = sKey.substring(0,2); // the corresponding "AB"
        let sBottom = sKey.substring(1); // the corresponding "BC"

        // if "AB" occurs, and "BC" occurs, but "ABC" doesn't
        if ( (tTop[sTop] < 2) && (tBottom[sBottom] < 2) && (tPattern[sKey] > 2) ) {
            // I'm not really sure what a good metric would be for deciding if a combination "occurs" or not
            tOut.push(sKey);
        }

    }

    return tOut;

}

FindHoles("VCC");

////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////

// Everything after this point exists to power the function expandCategories, which is used in Stats
// which basically determines all possible permutations of an input pattern, e.g. "VCC", that contains a reference to a category like C or V
// if it looks way more complicated than it needs to be, that's because it is
// it's directly taken and repurposed from a sound engine I wrote where it's meant to deal with much much more complicated input patterns
// like (C)[P('),B2,r]aC(:) or whatever, not just VCC
// so it's quite overkill for this particular use case, but there was no use

function join(array) {
  return Array.isArray(array) ? array.join('') : array;
}

function categoryValueToString(array = []) {
  return `[${array.toString()}]`;
}

function multiply(twoDArray1, twoDArray2) {
  if (twoDArray1.length === 0 && twoDArray2.length === 0) {
    return [];
  }
  else if (twoDArray1.length === 0) {
    return twoDArray2;
  }
  else if (twoDArray2.length === 0) {
    return twoDArray1;
  }
  const product = [];
  for (let i = 0; i < twoDArray1.length; i++) {
    for (let j = 0; j < twoDArray2.length; j++) {
      product.push([...twoDArray1[i], twoDArray2[j]]);
    }
  }
  return product;
}

function expandMultiCharacterCategory(inputString) {
  const multiCharCategories = Object.keys(tCategories).filter((key) => key.length > 1).sort((category1, category2) => category2.length - category1.length);
  let output = inputString;
  for (let category of multiCharCategories) {
    const expandedCategoryString = categoryValueToString(tCategories[category]);
    while (output.includes(category)) {
      output = output.replace(category, expandedCategoryString);
    }
  }
  return output;
}

function hasSquareBrackets(inputString) {
  for (let i = 0, ch = inputString.charAt(0); i < inputString.length; i++, ch = inputString.charAt(i)) {
    if (ch === '[') {
      return true;
    }
  }
  return false;
}

function expandSquareBrackets(inputString) {
  if (!hasSquareBrackets(inputString)) {
    return inputString;
  }
  let output = [[]];
  for (let i = 0, ch = inputString.charAt(0), squareBrackets = 0, j = 0; i < inputString.length; i++, ch = inputString.charAt(i)) {
    if (ch === '[') {
      squareBrackets++;
      if (squareBrackets === 1) {
        output.push([]);
        j++;
        continue;
      }
    }
    else if (ch === ']') {
      squareBrackets--;
      if (squareBrackets === 0) {
        output.push([]);
        j++;
        continue;
      }
    }

    if (ch !== ' ') {
      output[j].push(ch);
    }
  }
  output = output
    .map(join)
    .filter((string) => string !== '')
    .map(split)
    .reverse()
    .reduceRight(multiply)
    .map(join);
    return output;
}

function split(inputString) {
  let output = [];
  for (
    let i = 0, j = 0, ch = inputString.charAt(0), squareBrackets = 0;
    j <= inputString.length;
    j++, ch = inputString.charAt(j)
  ) {
    if (ch === '[') {
      squareBrackets++;
    }
    else if (ch === ']') {
      squareBrackets--;
    }


    if (squareBrackets === 0 && (ch === ',' || j === inputString.length)) {
      output.push(inputString.slice(i, j));
      i = j + 1;
    }
  }
  return output;
}

function stringHasCategories(inputString) {
  for (const key of Object.keys(tCategories)) {
    if (inputString.includes(key)) {
      return true;
    }
  }
  return false;
}

function expandCategories(inputString) {
  if (!stringHasCategories(inputString)) {
    return inputString;
  }
  let output = [[]];
  for (let i = 0, ch = inputString.charAt(0); i < inputString.length; i++, ch = inputString.charAt(i)) {
    if (tCategories[ch]) {
      output = multiply(output, tCategories[ch]);
    }
    else {
      output.forEach((op) => op.push(ch));
    }
  }
  output.forEach((op, i) => { output[i] = op.join(''); });
  return output;
}