Получить результат ближайшей последовательности из массива и заданного шаблона с помощью PHP

Question

Я пытаюсь получить год и месяц из букв в установленной последовательности. Я знаю, что последовательность основана на следующих буквах:

$letters = array('B','C','D','F','G','H','J','K','L','M','N','P','R','S','T','V','W','X','Y','Z');

Она начинается с 0000BBB, а когда достигает 9999, становится BB C, BBD et c. Поэтому мне не нужны числа в этом случае и только буквы, так как у меня есть список последней зарегистрированной последовательности за год и месяц, например:

$plates = array(
            array('2018','KHF','KHX','KJV','KKN','KLM','KML','KNK','KPD','KPR','KPT','----','----'),
            array('2017','JWN','JXF','JYB','JYT','JZP','KBM','KCH','KCV','KDK','KFB','KFV','KGN'),
            array('2016','JLN','JMF','JMY','JNR','JPK','JRG','JRZ','JSL','JTB','JTR','JVH','JVZ'),
            array('2015','JCK','JCY','JDR','JFG','JFW','JGP','JHJ','JHT','JJH','JJW','JKK','JKZ'),
            array('2014','HVN','HVZ','HWM','HXB','HXN','HYD','HTY','HZB','HZL','HZZ','JBL','JBY'),
            array('2013','HNT','HPC','HPN','HPY','HRK','HRX','HSK','HSR','HSZ','HTK','HTV','HVF'),
            array('2012','HJC','HJM','HKB','HKL','HKX','HLK','HLW','HMD','HML','HMT','HNC','HNK'),
            array('2011','HBP','HCB','HCR','HDC','HDR','HFF','HFT','HGC','HGM','HGX','HHH','HHT'),
            array('2010','GTC','GTS','GVM','GWC','GWV','GXP','GYD','GYM','GYX','GZJ','GZT','HBG'),
            array('2009','GKS','GLC','GLP','GMC','GMN','GNF','GNY','GPJ','GPW','GRM','GSC','GSR'),
            array('2008','FZR','GBN','GCK','GDH','GFC','GFY','GGV','GHG','GHT','GJJ','GJV','GKH'),
            array('2007','FKY','FLV','FNB','FNZ','FRC','FSJ','FTP','FVJ','FWC','FXB','FXY','FYY'),
            array('2006','DVW','DWT','DXZ','DYY','FBC','FCJ','FDP','FFK','FGF','FHD','FJD','FKC'),
            array('2005','DFZ','DGX','DHZ','DKB','DLD','DMJ','DNP','DPK','DRG','DSC','DTB','DVB'),
            array('2004','CRV','CSS','CTT','CVR','CWR','CXT','CYY','CZP','DBJ','DCH','DDG','DFF'),
            array('2003','CDV','CFM','CGJ','CHF','CJC','CKB','CLD','CLV','CMM','CNK','CPF','CRC'),
            array('2002','BSL','BTF','BTZ','BVW','BWT','BXP','BYP','BZF','BZV','CBP','CCH','CDC'),
            array('2001','BFJ','BGF','BHG','BJC','BKB','BLC','BMF','BMW','BNL','BPG','BRB','BRT'),
            array('2000','---','---','---','---','---','---','---','---','BBJ','BCD','BCY','BDR')
        );

Это означает, что индекс массива 0 - это год и от От 1 до 12 будет месяц. Я пытаюсь найти совпадение, но затем понимаю, что не могу найти точное значение и мне нужно искать ближайшее значение на основе букв.

Я был бы очень признателен, если бы кто-нибудь мог направить меня в правильном направлении, что бы будет лучшим методом для этого.

Это пока тест, но он просто вернет точное совпадение, мне пришлось бы искать любые возможные буквы, такие как KHW как пример, который должен соответствовать как ближайшее значение к KHX

foreach ($plates as $key => $val) {                        
            $search = array_search('KHX', $plates[$key]);            
            if($search){
                echo $search."\n";
                echo $plates[$key][0];
                break;
            }
        }        

Answer 1

Приведенный ниже код ни в коем случае не оптимизирован, это скорее концепция того, как вы можете решить свою проблему.

//Flatten out array (one dimension without years and ----)
$flatten = array();
foreach($plates as $platevalues) {
    foreach($platevalues as $pv) {        
        if ($pv != '---' && $pv != '----' && intval($pv) == 0) {
            //Create a string only if valid letters included in the $letters-array
            //This string is then added to the new array that is flattened out
            $pv2 = '';
            for($i=0;$i<strlen($pv);$i++) {
                $letter = substr($pv,$i,1);
                if (in_array($letter, $letters) !== false) {
                    $pv2 .= $letter;
                }
            }
            $flatten[] = $pv2;
        }
    }
}

//Do the search
$search = 'GWN';
$search_result = '';

//Create a new search string based on first found in flattened
//plates array (first G, then GW, then GWN)
for($i=0;$i<strlen($search);$i++) {
    foreach($flatten as $key=>$f) {
        if (substr($search,0,$i+1) == substr($f,0,$i+1)) {
            $search_result .= substr($search,$i,1);
            break;
        }
    }
}
/*
$search_result is: GW
*/

//Create a new array where all items that begins with GW are included
$result = [];
foreach($flatten as $key=>$item) {
    if (substr($search_result,0,strlen($search_result)) == 
    substr($item,0,strlen($search_result))) {
        $result[] = $item;   
    }
}
/*
$result =

array (size=2)
    0 => string 'GWC' (length=3)
    1 => string 'GWV' (length=3)
*/

//Create an array with total ASCII-value for each item 
//in the $result array above
$result_o = [];
foreach($result as $item) {
    $o = 0;
    for($i=0;$i<strlen($item);$i++) {
        $o += ord(substr($item,$i,1));
    }
   $result_o[]= $o;
}
/* 
$result_o = 

array (size=2)
    0 => int 225
    1 => int 244        
*/


//Get the total ASCII-value for the original search string
$search_o = 0;
for($i=0;$i<strlen($search);$i++) {
    $search_o += ord(substr($search,$i,1));
}
/*
$search_ o = 236
*/


//Find closest value in the $result_o (ASCII) - array compared (225,244)
//to the original $search_o ASCII value above (236)
$closest = 0;
$use_key = 0;
foreach($result_o as $key=>$item) {
    if ($closest == 0 || abs($search_o - $closest) > abs($item - $search_o)) {
        $closest = $item;
        $use_key = $key;
    }
}

/* 
$closest = 244 (it's closer to 236 than 225 is)
$use_key = 1
*/

Чтобы получить результат, вы:

/*
$result =

array (size=2)
    0 => string 'GWC' (length=3)
    1 => string 'GWV' (length=3)
*/

//This should print out GWV
echo 'result=' . $result[$use_key];

Answer 2

Вы можете решить это с помощью O (log n) с помощью двоичного поиска. Но в более простом решении вы можете решить это с помощью O (n). Вы можете рассчитать разницу между каждым словом с помощью приведенного ниже алгоритма. ‍‍

<?php

function strToInt($str)
{
    $result = 0;
    for ($i = 0; $i < strlen($str); $i++) {
        $result = $result * 100 + ord($str[$i]);
    }

    return $result;
}

function find($searchStr)
{
    $plates = [
        ['2018','KHF','KHX','KJV','KKN','KLM','KML','KNK','KPD','KPR','KPT','----','----'],
        ['2017','JWN','JXF','JYB','JYT','JZP','KBM','KCH','KCV','KDK','KFB','KFV','KGN'],
        ['2016','JLN','JMF','JMY','JNR','JPK','JRG','JRZ','JSL','JTB','JTR','JVH','JVZ'],
        ['2015','JCK','JCY','JDR','JFG','JFW','JGP','JHJ','JHT','JJH','JJW','JKK','JKZ'],
        ['2014','HVN','HVZ','HWM','HXB','HXN','HYD','HTY','HZB','HZL','HZZ','JBL','JBY'],
        ['2013','HNT','HPC','HPN','HPY','HRK','HRX','HSK','HSR','HSZ','HTK','HTV','HVF'],
        ['2012','HJC','HJM','HKB','HKL','HKX','HLK','HLW','HMD','HML','HMT','HNC','HNK'],
        ['2011','HBP','HCB','HCR','HDC','HDR','HFF','HFT','HGC','HGM','HGX','HHH','HHT'],
        ['2010','GTC','GTS','GVM','GWC','GWV','GXP','GYD','GYM','GYX','GZJ','GZT','HBG'],
        ['2009','GKS','GLC','GLP','GMC','GMN','GNF','GNY','GPJ','GPW','GRM','GSC','GSR'],
        ['2008','FZR','GBN','GCK','GDH','GFC','GFY','GGV','GHG','GHT','GJJ','GJV','GKH'],
        ['2007','FKY','FLV','FNB','FNZ','FRC','FSJ','FTP','FVJ','FWC','FXB','FXY','FYY'],
        ['2006','DVW','DWT','DXZ','DYY','FBC','FCJ','FDP','FFK','FGF','FHD','FJD','FKC'],
        ['2005','DFZ','DGX','DHZ','DKB','DLD','DMJ','DNP','DPK','DRG','DSC','DTB','DVB'],
        ['2004','CRV','CSS','CTT','CVR','CWR','CXT','CYY','CZP','DBJ','DCH','DDG','DFF'],
        ['2003','CDV','CFM','CGJ','CHF','CJC','CKB','CLD','CLV','CMM','CNK','CPF','CRC'],
        ['2002','BSL','BTF','BTZ','BVW','BWT','BXP','BYP','BZF','BZV','CBP','CCH','CDC'],
        ['2001','BFJ','BGF','BHG','BJC','BKB','BLC','BMF','BMW','BNL','BPG','BRB','BRT'],
        ['2000','---','---','---','---','---','---','---','---','BBJ','BCD','BCY','BDR']
    ];

    $minYear = null;
    $minKey = null;
    $minDiff = strToInt('ZZZ');
    $searchInt = strToInt($searchStr);

    for ($i = 0; $i < count($plates); $i++) {
        for ($j = 1; $j < 13; $j++) {
            if(abs($searchInt - strToInt($plates[$i][$j])) < $minDiff) {
                $minDiff = abs($searchInt - strToInt($plates[$i][$j]));
                $minYear = $plates[$i][0];
                $minKey = $plates[$i][$j];
            }
        }
    }

    return [$minYear, $minKey];
}


print_r(find('KHW'));