21 Відповідь від Patron

  • Patron
  • Patron
  • Заблокований
  • Поза форумом
  • Дата реєстрації: 22.05.2012
  • Повідомлень: 412
    • Репутація: 147

Re: Фільтрація номерів за маскою (задача на 5+)

Replace написав:

Цифри - ок. В умові взагалі про це не було сказано. Можна і так використовувати.
А такі маски точно не мають ніякого застосування. =)

Я з масками аж тепер допетрав. Маска це як шаблон який вказує на послідовність цифр у номері. Різні букви у масці - різні цифри у номері, якщо повторюється буква у масці то шукаємо вже не яку небудь цифру у номері а ту яка перший раз співпала з буквою у масці?)) Тобто ми маємо тимчасово зберігати цифри з номера котрі співпали з буквами для подальшого використання.Так?

22 Відповідь від Replace

  • Replace
  • Replace Team
  • Поза форумом
  • Звідки: Київ
  • Дата реєстрації: 06.04.2012
  • Повідомлень: 2 895
    • Репутація: 2106

Re: Фільтрація номерів за маскою (задача на 5+)

Так, в приват кину приклад :)
Не завжди перше співпадання підходить.

Наприклад, aabb 096 5584433. Якщо приянити за aa = 55, то нічого не вийде, а для варіанту з 44 підійде.

Replace вебсайт

23 Відповідь від Patron

  • Patron
  • Patron
  • Заблокований
  • Поза форумом
  • Дата реєстрації: 22.05.2012
  • Повідомлень: 412
    • Репутація: 147

Re: Фільтрація номерів за маскою (задача на 5+)

function byMask($number, $pattern) {
            /* 
            *Початок поршуку по символьній масці 
            */
            if(strlen($pattern) > strlen($number)) {
                return false;
            } else if(strlen($pattern) == strlen($number)) {
                $shift = false;
            } else{
                $shift = strlen($pattern);
            }
            $symbols = str_split($pattern);
            $numbers = str_split($number);
            
            $i = 0;
            do {
                $stack = array();
                $slice = array();
                //Вирізаємо зріз з основного масиву
                foreach(str_split($number) as $key=>$val) {
                    if($key >= $i && $key < $i+$shift) {
                        $slice[] = $val;
                    }
                }
                $good = true;
                //Порівнюємо зріз із маскою
                for($k = 0; $k < count($slice); $k++){
                    if(array_key_exists($symbols[$k], $stack)){
                        if($stack[$symbols[$k]] == $slice[$k]) {
                            continue;
                        } else {
                            $good = false;
                        }
                    } else {
                      $stack[$symbols[$k]] = $slice[$k];    
                    }
                }
                if($good == true) {
                    return true;
                } else if($shift != false && $i+1+$shift < strlen($number)){
                  $i += 1; // переходимо на наступний зріз(slice)
                } else {
                    /*
                    *якщо ми тут то ми безуспішно пройшли останній зріз і $good != true
                    */
                    return false;
                }                
            } while ($i+1+$shift < strlen($number));
        }
    
        if(byMask("097999954321", "aa")) {
            // 99 тут
            echo "here";
        } else {
            echo "false";
        }
        echo "<br/>";
        if(byMask("097999954321", "abcde")) {
            // 54321 тут
            echo "here";
        } else {
            echo "false";
        }
        echo "<br/>";
        if(byMask("097999954321", "aaaa")) {
            // 9999 тут
            echo "here";
        } else {
            echo "false";
        }
        if(byMask("097990954321", "aaba")) {
            // 9909 тут
            echo "here";
        } else {
            echo "false";
        }

Ось мій варіант. Алгоритм схожий на твій.

Подякували: Replace1

24 Відповідь від funivan

  • funivan
  • funivan
  • Replace Team
  • Поза форумом
  • Звідки: Київ
  • Дата реєстрації: 24.09.2012
  • Повідомлень: 2 005
    • Репутація: 927

Re: Фільтрація номерів за маскою (задача на 5+)

А те що мається на увазі то в кожного своє)

Я згідний з вами, у багатьох випадках краще перепитувати тоді буде менше "у кожного своє" ;)

П.С. Всі хто читає гілки форуму з темою "Задача" давайте спочатку будемо задавати питання а потім кидати відповідь. Думаю це в часті запитання можна кидати ;)

Подякували: Patron, Replace2

funivan вебсайт

25 Відповідь від Patron

  • Patron
  • Patron
  • Заблокований
  • Поза форумом
  • Дата реєстрації: 22.05.2012
  • Повідомлень: 412
    • Репутація: 147

Re: Фільтрація номерів за маскою (задача на 5+)

Не завжди перше співпадання підходить.

поясни чому. В мене після першого співпадання повертає true.
п.с http://codepad.viper-7.com - виконати php онлайн.

26 Відповідь від Vo_Vik

  • Vo_Vik
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 01.10.2012
  • Повідомлень: 4 784
    • Репутація: 2493

Re: Фільтрація номерів за маскою (задача на 5+)

Нажаль зараз не маю як писати, але як би це робив я.
Реалізуємо фунцію для провірки номеру по цифровій масці.
Для буквеної маски генеруємо всіх можливі для неї комбінації цифрових масок.
тобто a=0,1,2,..9, b=...
Можемо добавити комбінації для зеркальних... aaa,aba, aaaa, abba, aabaa,ababa, abbba, abcba, aaaaaa, aabbaa, abaaba, abbbba, abccba, можна розширити до 7-ми символів в зеркалі.
Прогін варіантів масок через масив номерів.
Можлива оптимізація, якщо номер не містить цифру n, то не пробувати маски з цією цифрою.

Vo_Vik вебсайт

27 Відповідь від Replace

  • Replace
  • Replace Team
  • Поза форумом
  • Звідки: Київ
  • Дата реєстрації: 06.04.2012
  • Повідомлень: 2 895
    • Репутація: 2106

Re: Фільтрація номерів за маскою (задача на 5+)

Vo_Vik, нереально багато зайвих ітерацій

Patron написав:

Не завжди перше співпадання підходить.

поясни чому. В мене після першого співпадання повертає true.
п.с http://codepad.viper-7.com - виконати php онлайн.

У тебе номер інший. Там перше співпадання і підходить =)

Replace вебсайт

28 Відповідь від Vo_Vik

  • Vo_Vik
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 01.10.2012
  • Повідомлень: 4 784
    • Репутація: 2493

Re: Фільтрація номерів за маскою (задача на 5+)

Добре, буду дома, напишу. Добавлю таймер, то подивимось.

Vo_Vik вебсайт

29 Відповідь від funivan

  • funivan
  • funivan
  • Replace Team
  • Поза форумом
  • Звідки: Київ
  • Дата реєстрації: 24.09.2012
  • Повідомлень: 2 005
    • Репутація: 927

Re: Фільтрація номерів за маскою (задача на 5+)

Vo_Vik написав:

Добре, буду дома, напишу. Добавлю таймер, то подивимось.

Ти хочеш всі маски генерувати??? Уявляєш скільки ітерацій треба для генерування azza при тому що а може бути в межах 0 до 9

p.s. Глянь мій код у цій гілці вважаю його досить оптимізованим.

funivan вебсайт

30 Відповідь від Patron

  • Patron
  • Patron
  • Заблокований
  • Поза форумом
  • Дата реєстрації: 22.05.2012
  • Повідомлень: 412
    • Репутація: 147

Re: Фільтрація номерів за маскою (задача на 5+)

Тримайте хлопаки, майже без велосипедів)))

function byMask2($number, $pattern) {
  //Конвертуємо маску в регексп
  $stack = array();
  $regExp = "#";
  foreach(str_split($pattern) as $symbol){
     if(in_array($symbol, $stack)){
          $regExp .= '\\'.(array_search($symbol, $stack)+1);
      } else {
          $regExp .= '([0-9])';
          $stack[] = $symbol;
      }
  }
  $regExp .= "#";
   return preg_match($regExp, $number);
 }
    
 if(byMask2("22323", 'aabab')){
    echo "match";
 }
/* match */

перевірити цей код

Код не працює!

31 Відповідь від Vo_Vik Востаннє редагувалося Vo_Vik (02.10.2012 20:35:21)

  • Vo_Vik
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 01.10.2012
  • Повідомлень: 4 784
    • Репутація: 2493

Re: Фільтрація номерів за маскою (задача на 5+)

funivan написав:
Vo_Vik написав:

Добре, буду дома, напишу. Добавлю таймер, то подивимось.

Ти хочеш всі маски генерувати??? Уявляєш скільки ітерацій треба для генерування azza при тому що а може бути в межах 0 до 9

p.s. Глянь мій код у цій гілці вважаю його досить оптимізованим.

Рівно 90.
Але вони генеруються один раз, потім просто для кожного номеру підставляються.
це швидше ніж кожен раз для нового номеру підбирати всі комбінації.

Для 3-х різних літер буде 720 комбінацій, ...

Потім порівняння  по по цифровій масці досить швидка операція сама по собі, для бінарної маски це просте множення.

Vo_Vik вебсайт

32 Відповідь від funivan

  • funivan
  • funivan
  • Replace Team
  • Поза форумом
  • Звідки: Київ
  • Дата реєстрації: 24.09.2012
  • Повідомлень: 2 005
    • Репутація: 927

Re: Фільтрація номерів за маскою (задача на 5+)

Рівно 90.
Але вони генеруються один раз, потім просто для кожного номеру підставляються.
це швидше ніж кожен раз для нового номеру підбирати всі комбінації.

Для 3-х різних літер буде 720 комбінацій, ...

Буду сперечатись поки не переконаю бо впевнений що це довгий варіант. Навіть, навіть якщо ти згенеруєш декілька тисяч комбінацій наступним кроком буде перевірка.

Візьми 1н телефон порівняй з 10000 комбінаціями які ти згенеруєш і засічи час, пізніше спробуй мій метод і засічи час. ;) Про результати відпиши.

для прикладу даю маски

49bb
zqzq
a0a0
q9119q

funivan вебсайт

33 Відповідь від funivan

  • funivan
  • funivan
  • Replace Team
  • Поза форумом
  • Звідки: Київ
  • Дата реєстрації: 24.09.2012
  • Повідомлень: 2 005
    • Репутація: 927

Re: Фільтрація номерів за маскою (задача на 5+)

Patron написав:

Тримайте хлопаки, майже без велосипедів)))

 if(byMask2("22222", 'a3bab')){
    echo "match";
 }
 if(byMask2("22222", 'abab')){
    echo "match";
 }

Спробуй це. Так що код не гуд

Подякували: Patron1

funivan вебсайт

34 Відповідь від Vo_Vik

  • Vo_Vik
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 01.10.2012
  • Повідомлень: 4 784
    • Репутація: 2493

Re: Фільтрація номерів за маскою (задача на 5+)

Patron написав:

Тримайте хлопаки, майже без велосипедів)))

 if(byMask2("22323", 'aabab')){
    echo "match";
 }
/* match */

А для 122323 воно працює?

Vo_Vik вебсайт

35 Відповідь від funivan

  • funivan
  • funivan
  • Replace Team
  • Поза форумом
  • Звідки: Київ
  • Дата реєстрації: 24.09.2012
  • Повідомлень: 2 005
    • Репутація: 927

Re: Фільтрація номерів за маскою (задача на 5+)

А для 122323 воно працює?

Воно працює =)

А що там з твоїм брутфорсом))

funivan вебсайт

36 Відповідь від Vo_Vik

  • Vo_Vik
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 01.10.2012
  • Повідомлень: 4 784
    • Репутація: 2493

Re: Фільтрація номерів за маскою (задача на 5+)

funivan написав:

для прикладу даю маски

49bb
zqzq
a0a0
q9119q

ці маски не коректні, згідно умов задачі вони трансформуються в
49aa
abab
a0a0
a9aa9a

Vo_Vik вебсайт

37 Відповідь від Vo_Vik

  • Vo_Vik
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 01.10.2012
  • Повідомлень: 4 784
    • Репутація: 2493

Re: Фільтрація номерів за маскою (задача на 5+)

funivan написав:

А що там з твоїм брутфорсом))

Так я казав, що коли прийду з роботи... А то ще 2 робочі години) А потім година в дорозі.

Vo_Vik вебсайт

38 Відповідь від funivan Востаннє редагувалося funivan (02.10.2012 20:55:32)

  • funivan
  • funivan
  • Replace Team
  • Поза форумом
  • Звідки: Київ
  • Дата реєстрації: 24.09.2012
  • Повідомлень: 2 005
    • Репутація: 927

Re: Фільтрація номерів за маскою (задача на 5+)

Vo_Vik написав:

ці маски не коректні, згідно умов задачі вони трансформуються в
49aa
abab
a0a0
a9aa9a

Ну в умові маска це a-z 0-9 під цю умову попадають але нахай.
Давай тоді для маски підбери =) 

abcdefgh

funivan вебсайт

39 Відповідь від Patron

  • Patron
  • Patron
  • Заблокований
  • Поза форумом
  • Дата реєстрації: 22.05.2012
  • Повідомлень: 412
    • Репутація: 147

Re: Фільтрація номерів за маскою (задача на 5+)

Vo_Vik написав:
Patron написав:

Тримайте хлопаки, майже без велосипедів)))

 if(byMask2("22323", 'aabab')){
    echo "match";
 }
/* match */

А для 122323 воно працює?

Код не гуд) Треба щось придумати)

40 Відповідь від Vo_Vik

  • Vo_Vik
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 01.10.2012
  • Повідомлень: 4 784
    • Репутація: 2493

Re: Фільтрація номерів за маскою (задача на 5+)

Трохи величенький у мене код получився на швидку руку

▼Прихований текст
<?
include 'list.php';
$maxLenght = 8;
$support_symbols = array(' ','+','-');
$list = explode("\n",str_replace($support_symbols,'',$list));
echo '<form method="post">';
echo 'Please enter mask (will be cat to '.$maxLenght.' symbols):<input type="text" name="mask" value="'.(isset($_POST['mask'])?$_POST['mask']:'').'">';
echo '</form>';
if(isset($_POST['mask']) && $_POST['mask']){
    $_POST['mask']=substr($_POST['mask'],0,$maxLenght);
//check time
   $mtime = microtime();
   $mtime = explode(" ",$mtime);
   $mtime = $mtime[1] + $mtime[0];
   $starttime = $mtime;
//end check time
    $masks=getMasks($_POST['mask']);
//check time
   $mtime = microtime();
   $mtime = explode(" ",$mtime);
   $mtime = $mtime[1] + $mtime[0];
   $endtime = $mtime;
   $totaltime = ($endtime - $starttime);
   echo "Mask generation time =".$totaltime." seconds<br />";
//end check time
    $numbers = array();
    foreach($list as $number)
        foreach($masks as $mask)
            if (strstr($number,$mask)) $numbers[] = $number;
//check time
   $mtime = microtime();
   $mtime = explode(" ",$mtime);
   $mtime = $mtime[1] + $mtime[0];
   $endtime2 = $mtime;
   $totaltime = ($endtime2 - $endtime);
   echo "Mask comparation time =".$totaltime." seconds<br />";
//end check time
    echo "Total selected ".count($numbers)." numbers<br />";
    echo "Mask: ".$_POST['mask'];
    echo '<pre>'.print_r($numbers,true);
}
function getMasks($string) {
    $charMask=str_split($string);
    $listMasks= array();
    $uniqueChars = array_unique($charMask);
    return setMasks(array(), $uniqueChars, $string, array());
}
function setMasks($inputMasks, $uniqueChars, $string, $excludedNumbers) {
    if(!count($inputMasks)) {
        $inputMasks = array($string);
    }
    if(count($uniqueChars)){
        $charNumber = count($uniqueChars)-1;
        if(is_numeric($uniqueChars[$charNumber])) {
            unset($uniqueChars[$charNumber]);
            return setMasks($inputMasks, $uniqueChars, $string, $excludedNumbers);
        }
        else {
            $outputMasks = array();
            $letter = $uniqueChars[$charNumber];
            unset($uniqueChars[$charNumber]);
            for($i=0;$i<=9;$i++) {
                if(!in_array($i, $excludedNumbers)) {
                    $outputMasks = array_merge($outputMasks,
                        setMasks(
                            replaceChar($inputMasks, $letter, $i)
                                , $uniqueChars, $string, array_merge($excludedNumbers, array($i))));
                }
            }
            return $outputMasks;
        }
    }
    else {
        return $inputMasks;
    }
}

function replaceChar($inputMasks, $letter, $i) {
    foreach($inputMasks as $key=>$value)
        $inputMasks[$key] = str_replace($letter, $i, $value);
    return $inputMasks;
}
?>

Ось результати на локальному сервері:
Mask generation time =0.0101351737976 seconds
Mask comparation time =0.113929033279 seconds
Total selected 440 numbers
Mask: abb

Vo_Vik вебсайт