Форум PHP программистов > Потренируемся в задачках ;)

[ Поиск ] - [ Пользователи ] - [ Календарь ]

Полная Версия: Потренируемся в задачках ;)

Sylex

21.02.2009 - 22:42

Задача: вывести сокращенную последовательность чисел из данных, к примеру: заменить "1,2,3,4" на "1-4".

Входные и выходные параметры - строка.

Для проверки, как должно быть есть массив $aFloors:
ключи - пример исходных данных,
значение - то, что должно получиться...

Программа:

PHP

<style type="text/css">
.v TD {
font: 12px Arial;
padding: 2px 10px;
}
</style>
<table class="v">
<?php
$aFloors = array(
    '9,8,7,5,4,3,2,1' => '1-5,7-9',
    '7,6,5,8,4,3,2' => '2-8',
    '5,6,9,4,3,2' => '2-6,9',
    '1,9,7,5' => '1,5,7,9',
    '9,8,6,4,2,1' => '1,2,4,6,8,9',
    '9,8,6,4,7,2,1' => '1,2,4,6-9',
    '8' => '8',
    '2,7,8,9' => '2,7-9',
    '2,6,8,9' => '2,6,8,9'
);

foreach ($aFloors as $key => $val) {
    $res = GetFloors($key);
    echo <<<EOF
         <tr>
         <td>{$key}</td><td>{$val}</td><td>{$res}</td>
         </tr>
EOF;
}
echo '</table>';


function GetFloors($s)
{
    // ваше решение 
}
<

Мое решение уже готово, но ждемс других

Спустя 1 час, 11 минут, 56 секунд (21.02.2009 - 22:54) Viking написал(а):

пока ничего лучше не получилось

PHP

function GetFloors($s)
{
$ss = explode(",",$s);
sort($ss);
$ind=0;
$old = $res[$ind][] = array_shift($ss);

foreach($ss as $val) {
  if($old+1 != $val)
    $ind++;
  $res[$ind][] = $val;
  $old = $val;
}

foreach($res as $k=> $val)
  if(count($val)>2) $res[$k] = join("-",array(min($val),max($val)));
    else $res[$k] = join(",",$val);

return join(",",$res);
}

Спустя 3 минуты (21.02.2009 - 22:57) bret написал(а):

Не знаю, насколько изящен код, но тут вроде была фишка в том, чтобы ухватить алгоритм.

Кажется работает

PHP

function GetFloors($s)
{
    $arr = explode(",", $s);
    sort($arr);
    $new_arr = array();
    $i = $j = 0; // индексы массивов
    $found_fam = 0; // длина найденных соседних чисел (семьи)
    $prev = -1000000; // предыдущее число в массиве
    while($arr[$i])
    {
     settype($arr[$i], "int");
     if($i==0)
     {
      // начало у обоих массивов одинаковое
      $new_arr[$j] = $arr[$i];
      $prev = $arr[$i];
     }
     else
     {
      if($arr[$i]==($prev+1))
      {
       $found_fam++;
      }
      else
      {
       // обрыв семьи
       if($found_fam>1)
       {
        $found_fam = 0;
    $new_arr[$j] .= '-'.$prev;// семья велика -> объединить
       }
       else if($found_fam==1)
       {
        // семья мала -> разделить
        $found_fam = 0;
    $j++;
    $new_arr[$j] = $prev;
       }
       $j++;
       $new_arr[$j] = $arr[$i]; // начало новой семьи
      }
     }
     $prev = $arr[$i];
     $i++;
    }
    if($found_fam>1)
     $new_arr[$j] .= '-'.$prev;
    else if($found_fam==1)
     $new_arr[] = $prev;
    $rez = implode(",", $new_arr);
    return $rez;
}

Спустя 4 минуты, 42 секунды (21.02.2009 - 23:02) Viking написал(а):

PHP

function GetFloors($s)
{
$ss = explode(",",$s);
sort($ss);
$ind=0;
$old = $res[$ind][] = array_shift($ss);

foreach($ss as $val) {
  if($old+1 != $val)
    $ind++;
  $res[$ind][] = $val;
  $old = $val;
}
$res = array_map("callback",$res);

return join(",",$res);
}
function callback($val){
  if(count($val)>2) return join("-",array(min($val),max($val))); else return join(",",$val);
}

пожалуй всетаки так

Спустя 1 час, 45 минут, 48 секунд (22.02.2009 - 00:47) Viking написал(а):

во у меня как здорово получилось, без лишних циклов, вот тока алгоритм я сам не понял

PHP

function GetFloors($s)
{

$ss = explode(",",$s);
sort($ss);

$number = 1;

$res = $last = array_shift($ss);

while($val = array_shift($ss)) {

  if($last+1 == $val) {
    $number++;
  } elseif($number == 1) {
    $res.=",".$val;
  } elseif($number == 2) {
    $res.=",".$last.",".$val;
    $number=1;
  } else {
    $res.="-".$last.",".$val;
    $number=1;
  }
  $last = $val;
}

if($number == 2) 
  $res.=",".$last;
elseif($number!=1) 
  $res.="-".$last;

return $res;
}

а вообще, если вдуматься, логика тут есть...

Спустя 54 минуты, 5 секунд (22.02.2009 - 01:41) sergeiss написал(а):

Ну, и я свою лепту внесу всё-таки

Вполне даже изящно получилось

("Сам себя не похвалИшь, как оплеваный сидишь" (С)

)

PHP

function GetFloors( $s )
{
  $a=explode(',',$s);
  if( @count( $a ) == 0 or !@sort( $a ) ) return '';
  $ret=array();
  $start=$a[0];
  $end=$a[0];
  $max_key=max( array_keys( $a ));
  foreach( $a as $k => $val)
  {
    if( $k == 0 ) continue;
    $diff=$val-$end;
    if( $diff  > 1 ) // произошел скачок
    {
        switch( $end-$start )
        {
            case 0: $ret[]=$start; break;
            case 1: $ret[]=$start; $ret[]=$end; break;
            default: $ret[]="$start-$end"; 
        }
        if( $k == $max_key ) $ret[]=$val;
      $start=$val; $end=$val;
    }
    elseif( $k == $max_key ) // скачка не было, но до конца добрались
    {
        if( $val-$start == 1 )
            { $ret[]=$start; $ret[]=$val; }
        else 
            $ret[]="$start-$val";
    }
    else // перенос конца диапазона на следующее значение
      $end=$val;
          
  }
  return implode( ',', $ret);
}

Спустя 4 часа, 38 минут, 30 секунд (22.02.2009 - 06:20) kirik написал(а):

Sylex, хорошая зарядка для хвоста!

sergeiss, у тебя кажись с 8-кой траблы

Мой вариант:

Свернутый текст

PHP

function GetFloors($s)
{
    $tmp = array();
    $flag = 0;

    $array = explode(',', $s);
    sort($array, SORT_NUMERIC);

    while(list($key, $elm) = each($array))
    {
        if(!isset($tmp[$flag])) // Определяем первое число
        {
            $tmp[$flag] = $start = $elm;
        }
    
        if(isset($start) && in_array($start + 1, $array) && in_array($start + 2, $array)) // Ставим "-", если у нас есть хотя бы 2 последовательных числа
        {
            $tmp[$flag] .= '-';
            $continue = true;
            unset($start);
        }
        elseif(isset($continue) && !in_array($elm + 1, $array)) // Определяем конечное число последовательности, если такая была установлена
        {
            $tmp[$flag] .= $elm;
            $flag++;
            unset($continue);
        }
        elseif(!isset($continue)) // Опеределяем одиночное число
        {
            $tmp[$flag] = $elm;
            $flag++;
            unset($start);
        }
    }

    return implode(',', $tmp);
}

UPD
Вариант номер два:

Свернутый текст

PHP

function GetFloors($s)
{
    $flag = 0;
    $tmp = array();

    $array = explode(',', $s);

    for($i = min($array), $max = max($array); $i <= $max; $i++)
    {
        if(!isset($tmp[$flag]) && in_array($i, $array)) // Определяем первое число
        {
            $tmp[$flag] = $i;

            if(!in_array($i + 1, $array) || !in_array($i + 2, $array)) // Если это не последовательность - оставляем число одно
                $flag++;
            else
                $dlmtr = true;
        }
        else
        {
            if(isset($dlmtr)) // Если у нас последовательность - ставим "-"
            {
                $tmp[$flag] .= '-';
                unset($dlmtr);
            }
            
            if(isset($tmp[$flag]) && !in_array($i + 1, $array)) // Если это последнее число последовательности, прерываем последовательность (о как!)
            {
                $tmp[$flag] .= $i;
                $flag++;
            }
        }
    }

    return implode(',', $tmp);
}

Спустя 2 часа, 21 минута, 49 секунд (22.02.2009 - 08:42) Sylex написал(а):

Ну чтож, практически все справились, с чем вас и поздравляю!

Небольшие недочеты у bret (при нуле) и sergeiss (при одной цифре)

Мои варианты:
1.

PHP

function GetFloors($s)
{
    $m = explode(',', (string)$s);
    sort($m);
    $count = sizeof($m);
    $s = '';
    $i = 0;
    while($i<$count) {
        $z = $m[$i]; 
        $p_end = $i; 
        for($j=$i+1;$j<=$count;$j++) {
            $z++;
            if ( $j == $count || $m[$j] != $z ) {
                $p_end = $j-1;
                break;
            }
        }
        if ( $p_end-$i>1 ) {
            $s .= $m[$i] . '-' . $m[$p_end];
        } elseif ( $p_end - $i == 1 ) {
            $s .= $m[$i] . ',' . $m[$p_end];
        } else {
            $s .= $m[$p_end];
        }
        if ( $p_end+1 != $count ) $s .= ',';
        $i = $p_end + 1;
    }
    return $s;
}

PHP

function GetFloors($s)
{
    $m = explode(',', $s);
    sort($m);
    $count = sizeof($m);
    $s = $p = $m[0];
    $cur = 1;
    for ($i=1; $i<=$count;$i++) {
        $val = isset($m[$i]) ? $m[$i] : '';
        if ($p+1 == $val) {
            $cur++;
        } elseif ($cur == 1) {
            $s .= ',' . $val;
        } elseif ($cur == 2) {
            $s .= ',' . $p . ',' .$val;
            $cur = 1;
        } else {
            $s .= '-' . $p . ',' . $val;
            $cur = 1;
        }
        $p = $val;
    }
    return rtrim($s, ',');
}

Также считаю красивым решением Viking.

Еще варианты?

Спустя 4 минуты, 49 секунд (22.02.2009 - 08:47) Sylex написал(а):

Более интересные варианты получаются в обратной задаче.

Итак, пробуем "раскодировать строку", условия те же.

Программа:

PHP

<style type="text/css">
.v TD {
font: 12px Arial;
padding: 2px 10px;
}
</style>
<table class="v">
<?php
$aFloors = array(
    '1-5,7-9' => '1,2,3,4,5,7,8,9',
    '2-8' => '2,3,4,5,6,7,8',
    '2-6,9' => '2,3,4,5,6,9',
    '1,5,7,9' => '1,5,7,9',
    '1,2,4,6,8,9' => '1,2,4,6,8,9',
    '1,2,4,6-9' => '1,2,4,6,7,8,9',
    '8' => '8',
    '2,7-9' => '2,7,8,9',
    '2,6,8,9' => '2,6,8,9',
    '11,13,15,16,19-21' => '11,13,15,16,19,20,21',
    '0' => '0',
    '18' => '18',
);

foreach ($aFloors as $key => $val) {
    $res = GetFloors($key);
    echo <<<EOF
         <tr>
         <td>{$key}</td><td>{$val}</td><td>{$res}</td>
         </tr>
EOF;
}
echo '</table>';


function GetFloors($s)
{
    // ваше решение 
}

Спустя 1 час, 24 минуты, 19 секунд (22.02.2009 - 10:11) Viking написал(а):

ну дык это совсем просто
Задача №2

PHP

function GetFloors($s)
{
$array = explode(",",$s);
foreach($array as $val) {
   $tmp = explode("-",$val);
   for($i=$tmp[0];$i<=$tmp[count($tmp)-1];$i++)
      $res[] = $i;
}
return join(",",$res);
}

Спустя 22 минуты (22.02.2009 - 10:33) Viking написал(а):

или так

PHP

function GetFloors($s)
{
$array = explode(",",$s);
$res = array();
foreach($array as $val) {
   $tmp = explode("-",$val);
   $res = array_merge($res,range($tmp[0],$tmp[count($tmp)-1]));
}
return join(",",$res);
}

а есть функция, которая разворачивает в массив его подмассивы? я чего-то не нашел, если есть, то можно еще круче сделать

Спустя 31 минута, 12 секунд (22.02.2009 - 11:04) kirik написал(а):

Цитата (Sylex @ 22.02.2009 - 00:47)

Итак, пробуем "раскодировать строку", условия те же.

Мой вариант:

PHP

function GetFloors($s)
{
    $array = explode(',', $s);
    
    for($i = 0, $c = count($array); $i < $c; $i++)
    {
        $tmp = explode('-', $array[$i]);
        $result[] = isset($tmp[1]) ? implode(',', range($tmp[0], $tmp[1])) : $tmp[0];
    }

    return implode(',', $result);
}

UPD Или даже так:

PHP

function GetFloors($s)
{
    $array = explode(',', $s);

    while($elm = each($array))
    {
        $tmp = explode('-', $elm[1]);
        $result[] = implode(',', range(current($tmp), end($tmp)));
    }

    return implode(',', $result);
}

Спустя 3 часа, 56 минут, 18 секунд (22.02.2009 - 15:00) Sylex написал(а):

кто еще?

Спустя 17 минут, 35 секунд (22.02.2009 - 15:18) Alchemist написал(а):

Интересная задачка (это про оригинальную, обратная - слишком проста), но еще интереснее решения

Правда меня несколько огорчило, что все пошли по пути "универсального" решения. Просто чтобы не быть в толпе (читай - чтобы вы*бнуться

) предлагаю свой "адаптированый" вариант:

PHP

function GetFloors($line)
{
    $array = explode(',',$line);
    $tmp = array();
    $last = count($array)-1;
    $i = $t = 0;

    sort($array,SORT_NUMERIC);
    while($i <= $last){
        $t = nextRange($array,$i,$last,$last);
        $tmp[] = ($i < $t) ? $array[$i].'-'.$array[$t] : $array[$i];
        $i = ++$t;
    }
    return implode(',',$tmp);
}

function nextRange(&$array, $start, $end, $max)
{
    if ($start == $end)
        return $end;
    if ($array[$end] - $array[$start] > $end - $start)
        return nextRange($array, $start, $start + intval(($end - $start)/2), $end);
    return nextRange($array, $end, $end + intval(($max - $end)/2), $max);
}

Вариант работает тем лучше чем меньше есть непрерывных последовательностей. Так например если все числа входят в одну последовательность, то работа займет ровно одну итерацию, вне зависимости от кол-ва чисел.

ЗЫ: Sylex, у тебя в примере ошибка! Числа 1 и 2 образуют непрерывную последовательность, поэтому должны записываться 1-2, а не 1,2

Спустя 16 минут, 5 секунд (22.02.2009 - 15:34) Alchemist написал(а):

Подумал и решил таки написать обратную функцию тоже

PHP

function GetFloors($line)
{
    return preg_replace_callback('/([\d]+)-([\d]+)/is',
        create_function('$res','return implode(",",range($res[1], $res[2]));'),$line);
}

Спустя 4 минуты, 53 секунды (22.02.2009 - 15:39) Sylex написал(а):

Alchemist
я не ошибся, это мои условия :

Последовательность 1,2 = 1,2
Последовательность 4,5 = 4,5

Спустя 10 часов, 28 минут, 10 секунд (23.02.2009 - 02:07) sergeiss написал(а):

Нет, подождите секунду

У меня всё нормально считается.
Вот копия из решения, формат вывода - согласно первому посту темы (первая колонка - оригинальная последовательность, вторая - что должно получиться, третья - что получилось):

Цитата

9,8,7,5,4,3,2,1    1-5,7-9    1-5,7-9
7,6,5,8,4,3,2    2-8    2-8
5,6,9,4,3,2    2-6,9    2-6,9
1,9,7,5    1,5,7,9    1,5,7,9
9,8,6,4,2,1    1,2,4,6,8,9    1,2,4,6,8,9
9,8,6,4,7,2,1    1,2,4,6-9    1,2,4,6-9
8    8
2,7,8,9    2,7-9    2,7-9
2,6,8,9    2,6,8,9    2,6,8,9

Я не вижу никаких проблем с восьмеркой.

Спустя 3 часа, 31 минута, 52 секунды (23.02.2009 - 05:39) kirik написал(а):

Цитата (sergeiss @ 22.02.2009 - 18:07)

Я не вижу никаких проблем с восьмеркой.

У тебя ее просто нету

Цитата

8 8 ?

Спустя 5 часов, 24 минуты, 47 секунд (23.02.2009 - 11:04) sergeiss написал(а):

Во, блин... Точно нету... ^( А я куда-то не туда посмотрел....

Правда, это не "проблема восьмерки", а проблема одиночных значений. Ставлю вместо (одиночной) восьмерки любое число - результат одинаковый.

ОК, спасибо

Буду внимательнее при отладке

Спустя 1 месяц, 7 дней, 19 часов, 17 минут, 47 секунд (31.03.2009 - 05:22) Guest написал(а):

Здрасьте:) помогите! Самое важное знаю. Игру написала. Загвоздка в другом.... В вебмани. Вы люди уже вижу в этом поплававшие - подскажите что и как? Я зарегила номер, но в нашем городе нет таких аппаратов, которые бы переводили с вебмани на руки... как быть? Спасибо заранее;)

Спустя 16 часов, 50 минут, 53 секунды (31.03.2009 - 22:12) Guest написал(а):

Цитата

Неволнуйтесь! Аппаратов выдающее вебмани вообще нет!

Можно только вывести налом либо через банк либо через агентов. Можете найти их в поисковике: набирите вывод webmoney и ваш город напишите!

Спустя 18 минут, 41 секунда (31.03.2009 - 22:31) HardWoman написал(а):

Если не в Крупных городах - самое лучшее открыть счет в банке и перевести деньги с кошелька на счет и потом снять. Агенты берут просто космические проценты за вывод. Да и курс доллара у них значительно превосходит курс сбербанка.

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

Вы можете себе представить обычный банк, куда вы положили деньги, а у них с вашего счета их увели и предлагают вам обратиться в милицию? Советую выбрать другую платежную систему, например, рупей. Масса преимуществ.

Спустя 8 часов, 51 минута, 58 секунд (1.04.2009 - 07:23) Sylex написал(а):

Цитата (HardWoman @ 1.04.2009 - 01:31)

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

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

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

Быстрый ответ:

Здесь расположена полная версия этой страницы.