Форум: Форум PHPФорум ApacheФорум Регулярные ВыраженияФорум MySQLHTML+CSS+JavaScriptФорум FlashРазное
Новые темы: 0000000
PHP на примерах (2 издание). Авторы: Кузнецов М.В., Симдянов И.В. Объектно-ориентированное программирование на PHP. Авторы: Кузнецов М.В., Симдянов И.В. MySQL 5. В подлиннике. Авторы: Кузнецов М.В., Симдянов И.В. C++. Мастер-класс в задачах и примерах. Авторы: Кузнецов М.В., Симдянов И.В. PHP 5/6. В подлиннике. Авторы: Кузнецов М.В., Симдянов И.В.
ВСЕ НАШИ КНИГИ
Консультационный центр SoftTime

Выбрать другой форум

 

Здравствуйте, Посетитель!

вид форума:
Линейный форум Структурный форум

тема: Ответ 001 на задачу N 22
 
 автор: SoftTime   (15.06.2007 в 20:44)   письмо автору
 
 

Ответ 001 на задачу N 22.
С условиями задачи можно ознакомится по ссылке.
<?php
// Решение задачи № 22 | Eugene77 | Передача данных через узкий канал связи

// Для успешного сравнения кодированных строк надо расположить кодировочные символы
// в порядке возрастания.
// Это можно было бы сделать изначально и самому Трианону, тогда получилась бы более
// скоростная версия программы. Но как условие даётся не отсортированная строка, следовательно
// будем сортировать её при каждом вызове кодировщика функцией  bubble.
// функция  bubble  просто меняет местами любых двух соседей, если они стоят не по порядку.
// И так до тех пор, пока не останется кого менять.

function bubble($abc){
for(
$unsorted=true$unsorted; ){
    
$unsorted=false;
    for(
$i=0$i<84$i++) {
        if(
$abc[$i]> $abc[$i+1]) {
            
$tmp $abc[$i];
            
$abc[$i] = $abc[$i+1];
            
$abc[$i+1] = $tmp;
            
$unsorted true;
        }
    }
}
return 
$abc;
}


// Функция user_encode во внешнем цикле разбивает входную строку на четвёрки байтов
// В первом вложенном цикле проверяет не короче ли остаток строки четырёх байтов и,
// если надо, уменьшает значение параметра $k до реальной длины остатка.
// Во втором цикле преобразует четвёрку байтов (квартет) в целое число
// В третьем вложенном цикле "while" приходится выравнивать содержимое неполных четвёрок к началу четвёрки быйтов
// Эта дань прихоти заказчика желающего сравнивать закодированные строки (сравнение строк начинается с первых байтов)
// В четвёртом цикле пора, наконец, привести число к 85-ричной системе исчислеия. (52200625 === 85*85*85*85)
// Число необходимых байт возрастает при этом на один  ($pentet)
// Можно было бы сделать короче и изящнее, но условие сраниваемости строк накладывает жёсткие рамки на алгоритм.

function user_encode($data$abc) {
$abc=bubble($abc);
for(
$resalt ""$i=0$kvartet=substr($data$i4);  $i+=4){
    for(
$k=4$kvartet == substr($data$i$k-1); $k--);
    for(
$bin_kvartet=0$j=0$j<$k$j++) $bin_kvartet=($bin_kvartet<<8)+ord($kvartet[$j]);
    while(
$j++ < 4$bin_kvartet=($bin_kvartet<<8)+ord($abc[84]);
    for(
$pentet ""$j=0$d=52200625$remnant $bin_kvartet$j<=$k$j++){
        
$remnant2 $remnant%$d;
        
$index = ($remnant-$remnant2)/$d;
        
$pentet .= $abc[$index];
        
$remnant $remnant2;
        
$d /= 85;
     }
    
$resalt .= $pentet;
}
return 
$resalt;
}

// Функция user_decode состоит из четырёх циклов в теле основного цикла,
// разбивающего входной поток на пятёрки байтов.
// В начале проверяется, действительно ли это пятёрка, и корректируется параметром $k, если надо
// Задача второго цикла - получить из пятёрки байтов входного потока целое число
// Для этого достаточно лишь просуммировать байты с соответствующими их положению весами.
// Третий цикл "while", опять же, выравнивающий. Возник лишь из-за условия сравниваемости кодированных строк, не более.
// Четвёртый цикл выделяет отдельные байты из целого числа и преобразует их в буквы.

function user_decode($text$abc){
$abc=bubble($abc);

for(
$resalt ""$i=0$pentet=substr($text$i5);  $i+=5){
    for(
$k=5$pentet == substr($text$i$k-1); $k--);
    for(
$bin_kvartet=0$j=0$j<$k$j++){
        
$pos strpos($abc$pentet[$j]);
        
$bin_kvartet $bin_kvartet*85+$pos;
    }
    while(
$j++<5$bin_kvartet *= 85;
    for(
$kvartet ""$j=24$j>=8*(5-$k); $j -= 8){
        
$digit $bin_kvartet>>$j;
        
$bin_kvartet -= $digit<<$j;
        
$kvartet .= chr($digit);
}
$resalt .= $kvartet;
}
return 
$resalt;
}
?>


http://www.softtime.ru/info/task.php?id_article=111

   
 
 автор: Trianon   (22.06.2007 в 14:23)   письмо автору
 
   для: SoftTime   (15.06.2007 в 20:44)
 

Просто очень обидно. Аж до слез.
Скрипт выглядит конфеткой, оформлен изумительно,
я даже выкинул bubble, перенеся его в тестовую обложку,
чтобы честно сравнить быстородействие.
Но увы. Тест рушится на первой нетривиальной проверке.
Код строки из одной буквы 'я' не декодируется обратно. 64 очка. :(

И еще, после того, как я всё же запустил тест быстродействия,
меня закидало нотайсами. Пришлось вставить error_reporting(E_ALL-E_NOTICE);
По собственнной инициативе я этого не делаю никогда.

Штрафных баллов : 64
Проверка на длинном тестовом наборе: 65792 байт
Тестовый набор данных декодирован с ошибкой:
Размер копии: 33625
В копии не совпадают с оригиналом 33268 байт

   
 
 автор: cheops   (23.06.2007 в 10:20)   письмо автору
 
   для: Trianon   (22.06.2007 в 14:23)
 

Это получается, что 64 самый лучший результат и приз достаётся Eugene77?

   
 
 автор: Trianon   (23.06.2007 в 13:40)   письмо автору
 
   для: cheops   (23.06.2007 в 10:20)
 

Игорь. Так дело не пойдет.
Кто у нас спонсор?
Кто у нас председатель жюри?
Кого будут случ чего на мыло отправлять?
Ой... чего-то я не то пишу...

Я написал свою оценку.
Составил тестовые скрипты.
Прогнал тесты.
Которые случайно (а если вглядеться - очень даже определенно) показали разные результаты.
И показал (плохим правда примером - времени было всего часа два - придумать лучше не успел) что задача решаема. Свое решение я ни в коем разе в список претендентов не толкаю.
Подводить итоги - Вам.
Вы можете учесть оценки тестов и мои коментарии.
Вы можете засчитать свой вариант (и очень желательно чтоб Вы все же озвучили его ), Можете объявить раунд сорванным.
Можете сменить судейский состав. :)
Но решение принимать - Вам.
Ну если никак - попросите Максима...
В любом случае, решать судьбу приза прав у меня нет.

   
 
 автор: cheops   (23.06.2007 в 14:00)   письмо автору
 
   для: Trianon   (23.06.2007 в 13:40)
 

Задача достаточно сложная и ваше мнение, как автора было бы тут очень важно. Мне кажется, приз вручать нужно, даже если задача выполнена не на все 100%. В качестве критерия лучше выбирать штрафные баллы, так как признак формальный и был заранее озвучен. Поэтому признаку победителем будет Eugene77 - если возражений нет, да будет так :)))

PS Вообще летом задачи наверное нужно попроще давать, что типа постраничной навигации на наименьшее количество строк - многие разработчики на юга откачёвывают, а те кто остаётся стараются больше отдыхать, запсать сил и витаминов на зиму. А то получается сами задачу ставите - сами и решаете - такой жанр лучше в виде статьи сразу оформлять :)))

   
 
 автор: Trianon   (23.06.2007 в 21:33)   письмо автору
 
   для: cheops   (23.06.2007 в 14:00)
 

>Поэтому признаку победителем будет Eugene77 - если возражений нет, да будет так :)))

возражений нет.

Решение подкупило своей лаконичностью, на самом деле - самое близкое к сути алгоритма.

Судите сами - если и я и Вы и тестер-скрипт высказались одинаково, о чем еще думать?

64 - признак того, что все облажались на краевых эффектах...
Ну так что... поправят - и уйдет этот шестой бит.

Останется сухой остаток.

   
 
 автор: Eugene77   (24.06.2007 в 19:48)   письмо автору
 
   для: Trianon   (23.06.2007 в 21:33)
 

Дорогой Трианон, извините, что я вас так огорчил! Я прямо растерялся, не знаю, что мне сейчас делать.
Я упустил из виду, что первый бит у числа в PHP всегда – знаковый. Из-за него и возникает мой баг.
Чтобы вы могли убедиться в этом, прилагаю копию программы, в которой алгоритм не изменён ни на йоту, а лишь использована библиотека GMP, в которой таких чисто PHP-шных проблем нет.


function user_encode($data, $abc) {
for($resalt = "", $i=0; $kvartet=substr($data, $i, 4);  $i+=4){
    for($k=4; $kvartet == substr($data, $i, $k-1); $k--);
    for($bin_kvartet=gmp_init(0), $j=0; $j<$k; $j++) $bin_kvartet=gmp_add(gmp_mul($bin_kvartet,256),ord($kvartet[$j]));
    while($j++ < 4) $bin_kvartet=gmp_add(gmp_mul($bin_kvartet,256),ord($abc[84]));
    for($pentet = "", $j=0, $d=52200625, $remnant = $bin_kvartet; $j<=$k; $j++, $d /= 85){
        $remnant2 = gmp_div_r($remnant,$d);
        $index = gmp_div(gmp_sub($remnant,$remnant2), $d);
        $pentet .= $abc[gmp_intval ($index)];
        $remnant = $remnant2;
    }
    $resalt .= $pentet;
}
return $resalt;
}


function user_decode($text, $abc){
for($resalt = "", $i=0; $pentet=substr($text, $i, 5);  $i+=5){
    for($k=5; $pentet == substr($text, $i, $k-1); $k--);
    for($bin_kvartet=gmp_init(0), $j=0; $j<$k; $j++){
        $pos = strpos($abc, $pentet[$j]);
        $bin_kvartet = gmp_add(gmp_mul($bin_kvartet,85),$pos);
    }
    while($j++<5) $bin_kvartet = gmp_mul($bin_kvartet,85);
    for($kvartet = "", $j=24; $j>=8*(5-$k); $j -= 8){
        $digit = gmp_div($bin_kvartet,gmp_pow(2,$j));
        $bin_kvartet = gmp_sub($bin_kvartet,gmp_mul($digit,gmp_pow(2,$j)));
        $kvartet .= chr(gmp_intval($digit));
}
$resalt .= $kvartet;
}
return $resalt;
}

Залатывать эту дырку без использования GMP не хочется, так как
1. получается сложный некрасивый код, который потом тяжело будет переносить на микроконтроллер. А так получается наиболее простой для переноса на любой язык вариант.
2. В мануале я прочитал, что количество байтов в intedger зависит от операционной системы. Так что без GMP получается не совсем универсальная версия.
3. Из GMP я не использую никаких особенных функций: обычное сложение, умножение, деление – так что это условию задачи противоречит лишь формально, а для жизненной ситуации с виртуальным заказчиком подходит идеально. Кроме может быть, степенной функции, но убрать её – дело пяти минут.
4. GMP позволяет, если хотите, ещё более сократить код и приспособить его к «интересам» микроконтроллера так как содержит функцию целочисленного деления (раз уж вопрос скорости важен для заказчика).

Вот и слегка «причёсанный» вариант скрипта:

function user_encode($data, $abc) {
for($resalt = "", $i=0; $kvartet=substr($data, $i, 4);  $i+=4){
    for($k=4; $kvartet == substr($data, $i, $k-1); $k--);
    for($bin_kvartet=gmp_init(0), $j=0; $j<$k; $j++) $bin_kvartet=gmp_add(gmp_mul($bin_kvartet,256),ord($kvartet[$j]));
    while($j++ < 4) $bin_kvartet=gmp_add(gmp_mul($bin_kvartet,256),ord($abc[84]));
    for($pentet = "", $j=0, $d=52200625, $remnant = $bin_kvartet; $j<=$k; $j++, $d /= 85){
        $index = gmp_div_q($remnant, $d);
        $remnant = gmp_div_r($remnant,$d);
        $pentet .= $abc[gmp_intval ($index)];
    }
    $resalt .= $pentet;
}
return $resalt;
}

function user_decode($text, $abc){
for($resalt = "", $i=0; $pentet=substr($text, $i, 5);  $i+=5){
    for($k=5; $pentet == substr($text, $i, $k-1); $k--);
    for($bin_kvartet=gmp_init(0), $j=0; $j<$k; $j++){
        $pos = strpos($abc, $pentet[$j]);
        $bin_kvartet = gmp_add(gmp_mul($bin_kvartet,85),$pos);
    }
    while($j++<5) $bin_kvartet = gmp_mul($bin_kvartet,85);
    for($kvartet = "", $j=16777216 , $t=1; $t<$k; $j /= 256, $t++){
        $digit = gmp_div($bin_kvartet,(int)$j);
        $bin_kvartet = gmp_sub($bin_kvartet,gmp_mul($digit,$j));
        $kvartet .= chr(gmp_intval($digit));
    }
$resalt .= $kvartet;
}
return $resalt;
}


При таком положении дел у меня теряется желание ещё что-то высасывать из пальца заумное, если и так, очевидно, «все овцы целы и все волки сыты».

Надеюсь приведённые скрипты хоть чуть-чуть загладят рану, нанесённую вашему эстетическому восприятию первым моим сочинением!

Большое спасибо!

   
 
 автор: Eugene77   (24.06.2007 в 21:34)   письмо автору
 
   для: cheops   (23.06.2007 в 14:00)
 

Ура! Ура! Ура! Ура! Ура!

Ура! Ура! Ура! Ура! Ура!

Ура! Ура! Ура! Ура! Ура!

Мне дали приззззззззз!!!!!!!!!!!!!


Не подскажете,

как теперь его получить?


Может лучше новую тему завести?!

ПОЛУЧЕНИЕ ПРИЗОВ НА SOFTTIME

а то эта слишком уже длинная.

   
 
 автор: cheops   (25.06.2007 в 01:15)   письмо автору
 
   для: Eugene77   (24.06.2007 в 21:34)
 

Сообщите пожалуйста имя для домена третьего уровня вида имя_домен.st-host.ru, который хотите получить в управление или домен второго уровня, если он у вас имеется. Как только сообщите, мы заведём вам аккаунт и вышлем параметры доступа вам по почте - e-mail, который вы указывали при регистрации у вас рабочий?

   
 
 автор: Eugene77   (25.06.2007 в 08:56)   письмо автору
 
   для: cheops   (25.06.2007 в 01:15)
 

Хорошо!
Но только вот я уезжаю на лето, не успею сейчас все эти вопросы решить.
Да и сайт мой пока на локалхосте трепыхается - мягко говоря не совсем готов к публикации.
Как мне лучше сейчас поступить?
Это завистит от того какие у вас порядки.

Имя домена, например, зависит от того, можно ли мне сразу сделать несколько поддоменов:
underdomen1.superdomen.st-host.ru, underdomen2.superdomen.st-host.ru, underdomen3.superdomen.st-host.ru, и можно ли будет мне потом добавлять эти поддомены. Будет ли добавка поддоменов бесплатна? Всего поддоменов вряд-ли будет более 5.

e-mail перед отправкой лучше проверить. Отошлите просто пробное письмо, пожалуйста!

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

Сколько вы даёте баз?

Ещё хотя бы вкратце - сценарий перезда? Мне его перекачивать при помощи far ? Или как лучше?

Ну, и наконец, куда мне постучаться, когда я вернусь после лета?

   
 
 автор: cheops   (25.06.2007 в 10:45)   письмо автору
 
   для: Eugene77   (25.06.2007 в 08:56)
 

Хм... давайте тогда подождём до тех пор, пока вам не будет удобно (просто хост-команда включит счётчик в момент создания аккаунта и через месяц выключит, поэтому лучше инициировать хостинг, когда он вам реально понадобится). Как только вам будет удобно подымите эту тему или пришлите мне письмо на igor [at] sottime.ru с ссылкой на эту тему с вашего почтового ящика.

   
 
 автор: Eugene77   (25.06.2007 в 21:43)   письмо автору
 
   для: cheops   (25.06.2007 в 10:45)
 

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

   
 
 автор: cheops   (26.06.2007 в 11:03)   письмо автору
 
   для: Eugene77   (25.06.2007 в 08:56)
 

>underdomen1.superdomen.st-host.ru, underdomen2.superdomen.st-host.ru, underdomen3.
superdomen.st-host.ru,
>и можно ли будет мне потом добавлять эти поддомены. Будет ли добавка поддоменов
>бесплатна? Всего поддоменов вряд-ли будет более 5.
>Сколько вы даёте баз?
Вы будете иметь 100 Мб диского пространства и исходя из этого бесплатно вам предоставляется до 10 поддоменов третьего уровня и 2 базы данных (на каждые 50 Мб предоставляется 1 база данных и 5 доменов третьего уровня). Обычно их можно создавать самостоятельно из панели администрирования, но это в случае, если привязка идёт к домену второго уровня, тут вероятно придётся создавать их по заявке (так как домен сразу второго уровня). Все дополнительные домены и базы данных сверх бесплатных оплачиваются.

>Ещё не ясно с какого момента начинается отсчёт месяца. С момента получения мной
>параметров доступа или с момента как сайт настроен и заработал. Я разумеется, приведу в
>рабочее состояние сайт на локалхосте, но при переезде-то возникнут нюансы.
Месяц отсчитывается с момента получения вами параметров доступа.

>Ещё хотя бы вкратце - сценарий перезда? Мне его перекачивать при помощи far ? Или как
>лучше?
Да, вам будет предоставлены параметры FTP-доступа и вы можете воспользоваться одним из FTP-клиентов для переноса файлов (например, FAR).

>Ну, и наконец, куда мне постучаться, когда я вернусь после лета?
Пишите мне на igor [at] softtime.ru

   
 
 автор: Eugene77   (26.06.2007 в 20:49)   письмо автору
 
   для: cheops   (26.06.2007 в 11:03)
 

Прекрасные условия! Для меня этого всего пока вполне достаточно. "Нигде не жмёт!"
Если проще создавать домены третьего уровня, а не четвёртого, то так тому и быть. Меня это тоже не стеснит, в чём-то даже лучше. Главное конкретные детали прояснились!

Меня ещё один вопрос интересует, уже не по хостингу.
Что стало с 21-й задачей? Ведь очень уж интересные темы в ней затронуты!
Я разбираясь в них, даже написал свою верию решения, добиваясь максимально прозрачного состояния скрипта. Кто-нибудь из вас - опытных - можете посмотреть?
Советы мне дать?
Спасибо вам за заботу!

   
 
 автор: cheops   (26.06.2007 в 21:22)   письмо автору
 
   для: Eugene77   (26.06.2007 в 20:49)
 

Мы пришли к выводу, что с 21 задачей никто не справился (весь упор шёл на безопасную вставку данных в СУБД), поэтому Trianon выложил свой вариант ответа http://www.softtime.ru/forum/read.php?id_forum=7&id_theme=38424, а приз решили никому не вручать.

   
 
 автор: Eugene77   (27.06.2007 в 09:43)   письмо автору
 
   для: cheops   (26.06.2007 в 21:22)
 

>Мы пришли к выводу, что с 21 задачей никто не справился (весь упор шёл на безопасную вставку данных в СУБД), поэтому Trianon выложил свой вариант ответа http://www.softtime.ru/forum/read.php?id_forum=7&id_theme=38424, а приз решили никому не вручать.

Приз - это, конечно здорово, но не самое главное.
Для меня в данном случае важнее понять все ли уроки я усвоил правильно из тех, которые подразумевала задача.

Можете её посмотреть вы или Трианон, если он увидит этот мой пост?

Мне важно услышать ваши оценки, особенно указания на слабые места скрипта.

Если с 22-й задачей просто выявилась моя невнимательность, то в 21 вполне может выявиться, что я не знаю чего-то существенного.

   
 
 автор: cheops   (27.06.2007 в 10:27)   письмо автору
 
   для: Eugene77   (27.06.2007 в 09:43)
 

Вообще в конце обычно заводится тема - где все задачи обсуждаются, только для 22 что-то такой темы не завели. Все детали, на которые нужно было обратить внимание в задаче 21 Trianon и я описали в теме http://www.softtime.ru/forum/read.php?id_forum=7&id_theme=38452 - именно к ней следует обращаться, чтобы оценить что не так и насколько.

   
 
 автор: Eugene77   (27.06.2007 в 15:01)   письмо автору
 
   для: cheops   (27.06.2007 в 10:27)
 

Жаль, что вы не хотите посмотреть мой скрипт!
Наверно вам надоело уже разбирать наши каракули... да и зачем, если довольно правильный ответ уже опубликован.

Обсуждение я читал, спасибо что напомнили.

Но мне казалось, что там надо было ещё коснуться и кодировок, точнее количества байт в различных кодировках, раз уж предлагалось считать буквы.

Ну, замнём на этом тему.

Спасибо на том. И так вся эта история с задачами мне очень помогла!

   
 
 автор: cheops   (27.06.2007 в 16:21)   письмо автору
 
   для: Eugene77   (27.06.2007 в 15:01)
 

>Но мне казалось, что там надо было ещё коснуться и кодировок, точнее количества байт в
>различных кодировках, раз уж предлагалось считать буквы.
Да есть такое дело, функция LENGTH() - возвращает количество байт в строке, для того, чтобы получить количество символов (в том числе и для двухбайтовых кодировок), правильнее использовать функцию CHAR_LENGTH(). Здесь не совсем корректно это обсуждать, так как вы не привели свой файл config.inc.php - не известно, как вы настраиваете кодировку соединения. Поэтому по умолчанию действует презумция невиновности :) - вы использовали однобайтовую кодировку и с проблемой удвоения не столкнулись, следовательно с ней не столкнётся и пользователь скрипта.

PS Вопросы, посвящённые предыдущей задаче, лучше обсуждать в темах, посвящённых предыдущей задаче. Другие посетители, которые будут решать задачу позже, возможно тоже заинтересуются всеми аспектами задачи и им тоже интересно почитать обсуждение, а так они будут вынуждены искать это обсуждение по всему форуму.

   
 
 автор: Eugene77   (27.06.2007 в 22:33)   письмо автору
 
   для: cheops   (27.06.2007 в 16:21)
 

>Да есть такое дело, функция LENGTH() - возвращает количество байт в строке, для того, чтобы >получить количество символов (в том числе и для двухбайтовых кодировок), правильнее >использовать функцию CHAR_LENGTH().

Разве есть такие функции в PHP?
Я знаю пока только strlen(). Где прочитать?

>Здесь не совсем корректно это обсуждать, так как вы не привели свой файл config.inc.php - не >известно, как вы настраиваете кодировку соединения. Поэтому по умолчанию действует >презумция невиновности :) - вы использовали однобайтовую кодировку и с проблемой >удвоения не столкнулись, следовательно с ней не столкнётся и пользователь скрипта.
>

А магические кавычки тоже по умолчанию выключенными считать? :-)


>PS Вопросы, посвящённые предыдущей задаче, лучше обсуждать в темах, посвящённых предыдущей задаче. Другие посетители, которые будут решать задачу позже, возможно тоже заинтересуются всеми аспектами задачи и им тоже интересно почитать обсуждение, а так они будут вынуждены искать это обсуждение по всему форуму.

То есть мне создать новую тему: Решение задачи 21 № 7, внести туда своё решение, и там продолжим? Правильно я понял?

   
 
 автор: cheops   (28.06.2007 в 00:26)   письмо автору
 
   для: Eugene77   (27.06.2007 в 22:33)
 

>Разве есть такие функции в PHP?
>Я знаю пока только strlen(). Где прочитать?
А разве вы PHP-функцию использовали? Вы воспользовались MySQL-функцией :)))
<?php
  $sql 
"SELECT *, LENGTH(guestname) as len FROM guests WHERE id = ".intval($id);
?>

   
 
 автор: Eugene77   (28.06.2007 в 09:34)   письмо автору
 
   для: cheops   (28.06.2007 в 00:26)
 

Ага! Понятно! Вы меня с кем-то другим перепутали.
Вот почему мне наш диалог таким странным показался!

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

Может он и не очень разумный, тогда в чём? Подскажите!
Я положу сейчас свой вариант решения в виде отдельной темы.
Конечно, я не претендую на полноправие своего решения, в нём присутствуют элементы прямо подцепленные из других ответов, но не всё там чужое. Надеюсь, кто-нибудь протестирует моё решение и даст совет.

   
 
 автор: Eugene77   (12.08.2007 в 20:11)   письмо автору
 
   для: Eugene77   (24.06.2007 в 21:34)
 

Привет всем!
Я, наконец, вернулся домой. Наверно упустил много интересного!
Буду навёрстывать.
Как жаль, что Трианон опубликовал своё решение прежде меня, но вот и мой вариант, на скорую руку залатанный. Признаться, латал скрепя сердцем – вся красота потерялась. Стало всё ужасно запутанно. Хотя после месяца проведенного в палатке, когда даже сотового телефона не было рядом, - это пустяки – у любого получится такую задачку решить.
В принципе идея простая – если не хватает места в четырёх байтах, то добавляем ещё два вспомогательных интеджера. Излишки – кидаем туда. Но всё это оборачивается кучей условных операторов, так что, конечно, мне до Трианоновой ясности мысли далеко, даже после такого славного проветривания мозгов, какое мне досталось.



// Функция user_encode во внешнем цикле разбивает входную строку на четвёрки байтов
// В первом вложенном цикле проверяет не короче ли остаток строки четырёх байтов и,
// если надо, уменьшает значение параметра $k до реальной длины остатка.
// Во втором цикле преобразует четвёрку байтов (квартет) в целое число
// В третьем вложенном цикле "while" приходится выравнивать содержимое неполных четвёрок к началу четвёрки быйтов
// Эта дань прихоти заказчика желающего сравнивать закодированные строки (сравнение строк начинается с первых байтов)
// В четвёртом цикле пора, наконец, привести число к 85-ричной системе исчислеия. (52200625 === 85*85*85*85)
// Число необходимых байт возрастает при этом на один ($pentet)
// Можно было бы сделать короче и изящнее, но условие сраниваемости строк накладывает жёсткие рамки на алгоритм.



f
unction user_encode($data, $abc) {
$patch = (127<<24)+(255<<16)+(255<<8)+255;
$abc=bubble($abc);
 for($resalt = "", $i=0; ($kvartet=substr($data, $i, 4)) != NULL;  $i+=4){
        for($k=4; $kvartet[$k-1] == NULL; $k--);
echo"k=    ".$k.'</br>';
        for($bin_kvartet=ord($kvartet[0]), $j=0; $j<$k; $j++) {
            if(($bin_kvartet=($bin_kvartet<<8))>= 0){
                if($patch-$bin_kvartet >= ord($kvartet[$j])){$bin_kvartet+=ord($kvartet[$j]); $add=0; $addrem = 0;}
                else {$bin_kvartet=$bin_kvartet-$patch+ord($kvartet[$j]); $add=$patch; $addrem = 0;}
                }
            else{
                 $bin_kvartet=($bin_kvartet ^ (128<<24));
                 $bin_kvartet += ord($kvartet[$j]);
                 $add=$patch; $addrem = 1;
                 }
        }
        while($j++ < 4)  {
            if(($bin_kvartet=($bin_kvartet<<8))>= 0){
                if($patch-$bin_kvartet >= ord($abc[84])){$bin_kvartet+=ord($abc[84]); $add=0; $extr = 0;}
                else {$bin_kvartet=$bin_kvartet-$patch+ord($abc[84]); $add=$patch; $extr = 41;}
                }
            else{
                 $bin_kvartet=($bin_kvartet ^ (128<<24));
                 $bin_kvartet += ord($abc[84]);
                 $add=$patch; $extr = 41; $addrem = 1;
                 }
        }
echo "encode summ  ".gmp_strval(gmp_add(gmp_add($bin_kvartet,$add),$addrem))."</br>";
        $d=52200625;
        $index = 0;
        if($add>0) $index++;
        for(; ($bin_kvartet - $index*$d + $add + $addrem) >= 0; $index++) $remnant = $bin_kvartet - $index*$d + $add + $addrem;

           $d /= 85;
           $pentet = $abc[--$index];

        for($j=1; $j<=$k; $d /= 85, $j++){
            $remnant2 = $remnant%$d;
            $index = ($remnant-$remnant2)/$d;
           if($index > 84) $index /= 85;
            $remnant = $remnant2;
            $pentet .= $abc[$index];
         }


    $resalt .= $pentet;
 }
return $resalt;
}

// Функция user_decode состоит из четырёх циклов в теле основного цикла,
// разбивающего входной поток на пятёрки байтов.
// В начале проверяется, действительно ли это пятёрка, и корректируется параметром $k, если надо
// Задача второго цикла - получить из пятёрки байтов входного потока целое число
// Для этого достаточно лишь просуммировать байты с соответствующими их положению весами.
// Третий цикл "while", опять же, выравнивающий. Возник лишь из-за условия сравниваемости кодированных строк, не более.
// Четвёртый цикл выделяет отдельные байты из целого числа и преобразует их в буквы.

function user_decode($text, $abc){
$abc=bubble($abc);
$patch = (127<<24)+(255<<16)+(255<<8)+255;

for($resalt = "", $i=0; $pentet=substr($text, $i, 5);  $i+=5){
    for($k=5; $pentet == substr($text, $i, $k-1); $k--);
    for($bin_kvartet=0, $j=0; $j<4; $j++){
        if($j < $k) $pos = strpos($abc, $pentet[$j]);
        else  $pos = 0;
        $bin_kvartet = $bin_kvartet*85+$pos;
    }

    if(4 < $k) $pos = strpos($abc, $pentet[4]);
    else  $pos = 0;
    $remnant = ($patch-$pos)%85;
    if(($patch-$remnant)/85 >= $bin_kvartet) { // Первый бит будет нулём (маленькое число)
            $bin_kvartet = $bin_kvartet*85+$pos;
        for($kvartet = "", $j=24; $j>=8*(5-$k); $j -= 8){
            $digit = $bin_kvartet>>$j;
            $bin_kvartet -= $digit<<$j;
            $kvartet .= chr($digit);
        }
    }
    else{  // Первый бит хочет стать единичкой. Надо решать проблему этого знакового бита
        $remnant = $patch%85;
        $quotient = ($patch-$remnant)/85;
        $bin_kvartet = ($bin_kvartet-$quotient)*85-43+$pos;
        $digit = ($bin_kvartet>>24)+128;
        $kvartet = chr($digit);
        $bin_kvartet -= (($digit-128)<<24);

        for($j=16; $j>=8*(5-$k); $j -= 8){
            $digit = $bin_kvartet>>$j;
            $bin_kvartet -= $digit<<$j;
            $kvartet .= chr($digit);
        }
     }
$resalt .= $kvartet;
}
return $resalt;
}

function user_decode_gmp($text, $abc){
$abc=bubble($abc);

for($resalt = "", $i=0; $pentet=substr($text, $i, 5);  $i+=5){
    for($k=5; $pentet == substr($text, $i, $k-1); $k--);
    for($bin_kvartet=gmp_init(0), $j=0; $j<$k; $j++){
        $pos = strpos($abc, $pentet[$j]);
        $bin_kvartet = gmp_add(gmp_mul($bin_kvartet,85),$pos);
    }
    while($j++<5) $bin_kvartet = gmp_mul($bin_kvartet,85);
    for($kvartet = "", $j=16777216 , $t=1; $t<$k; $j /= 256, $t++){
        $digit = gmp_div($bin_kvartet,(int)$j);
        $bin_kvartet = gmp_sub($bin_kvartet,gmp_mul($digit,$j));
        $kvartet .= chr(gmp_intval($digit));
    }
$resalt .= $kvartet;
}
return $resalt;
}


Кстати, попутно нашёл ошибочку и в своей функции кодирования посредством gmp библиотеки. Её следует переделать до вот такого состояния:


function user_gmp_encode($data, $abc) {
$abc=bubble($abc);
for($resalt = "", $i=0; ($kvartet=substr($data, $i, 4)) != NULL;  $i+=4){
    for($k=4; $kvartet[$k-1] == NULL; $k--);
    for($bin_kvartet=gmp_init(0), $j=0; $j<$k; $j++) $bin_kvartet=gmp_add(gmp_mul($bin_kvartet,256),ord($kvartet[$j]));
    while($j++ < 4) $bin_kvartet=gmp_add(gmp_mul($bin_kvartet,256),ord($abc[84]));
 echo"gmp_bin_kvartet = ".gmp_strval($bin_kvartet)."</br>";
    for($pentet = "", $j=0, $d=52200625, $remnant = $bin_kvartet; $j<=$k; $j++, $d /= 85){
        $index = gmp_div_q($remnant, $d);
        $remnant = gmp_div_r($remnant,$d);
        $pentet .= $abc[gmp_intval ($index)];
    }
    $resalt .= $pentet;
}
return $resalt;
}


Ну и, с нетерпением жду следующую задачку!

Возможно ли придумать задачу, касающуюся темы защиты от ftp троянов?

   
 
 автор: Unkind   (12.08.2007 в 22:13)   письмо автору
 
   для: Eugene77   (12.08.2007 в 20:11)
 

Возможно ли придумать задачу, касающуюся темы защиты от ftp троянов?
Я думаю придумать возможно всегда. Но вот такая тема как защита от троянов, ворующих FTP-пароли для PHP-форума не подходит.
Да и вообще для обычной задачи не подойдет. Нужно иметь ну уж хотя бы базу хешей исполняемых файлов или библиотек, содержащих троян.

   
 
 автор: sim5   (12.08.2007 в 22:46)   письмо автору
 
   для: Eugene77   (12.08.2007 в 20:11)
 

Задача была интересная, но в ее начале упоминался и микроконтроллер. Бедный микроконтроллер - придеться ему изрядно попотеть :)

   
 
 автор: Trianon   (13.08.2007 в 11:27)   письмо автору
 
   для: Eugene77   (12.08.2007 в 20:11)
 

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

А идеальный ответ вакантен.
Его так никто и не прислал.
В том числе и я.

   
 
 автор: Eugene77   (13.08.2007 в 18:49)   письмо автору
 
   для: Trianon   (13.08.2007 в 11:27)
 

>
>А идеальный ответ вакантен.
>Его так никто и не прислал.
>В том числе и я.

Нравится мне ваша загадочность...
Хоть и похоже немного на детский сад, но я купился...
Может ещё подумаю...
Жаль, времени маловато: тема-то немного в сторонке лежит от моих задач...
А то вообще-то и самому хочется по-человечески код переписать.

Тестировать-то будете?
Интересно было бы узнать реальную разницу в скорости под юниксом всех трёх действующих вариантов. Стоило ли копья ломать?!

   
 
 автор: Trianon   (20.08.2007 в 07:08)   письмо автору
 
   для: Eugene77   (13.08.2007 в 18:49)
 

>Нравится мне ваша загадочность...
>Хоть и похоже немного на детский сад, но я купился...
какие загадки?
пока что единственный опубликованный вариант, который не лажает на тестах, основан на трюке с переменной системой счисления (основание дрожит между 84 и 85). Для микроконтроллерной реализации ответного интерфейса - это роскошь на грани (а то и за гранью) фола.


>Может ещё подумаю...
>Жаль, времени маловато: тема-то немного в сторонке лежит от моих задач...
>А то вообще-то и самому хочется по-человечески код переписать.
>
>Тестировать-то будете?
Тестирующие скрипты опубликованы. Какая разница, кто запустит?

>Интересно было бы узнать реальную разницу в скорости под юниксом всех трёх действующих вариантов. Стоило ли копья ломать?!

Однозначно - из-за скорости - нет.

   
 
 автор: Eugene77   (20.08.2007 в 21:56)   письмо автору
 
   для: Trianon   (20.08.2007 в 07:08)
 

>пока что единственный опубликованный вариант, который не лажает на тестах, основан на трюке с переменной системой счисления (основание дрожит между 84 и 85). Для микроконтроллерной реализации ответного интерфейса - это роскошь на грани (а то и за гранью) фола.
>
Это мне непонятно. Что вы сказали? Вы говорите про мой вариант программы или про свой?
Вы тестировали мой вариант?
Что значит "дрожжит"
>
>Тестирующие скрипты опубликованы. Какая разница, кто запустит?
>
Ну я например проглядел у себя ошибку уже два раза. Хорошо бы протестировать мой скрипт
серьёзненько!

А вообще у меня наклёвывабтся некие идеи иного подхода к решению. Недавно, например
прочитал про pack(). Кажется ей можно многое упростить, но хорошо бы где-то добыть примеров её использования, а то я не совсем понял детали использования из мануала.
Незнаю ещё допустите ли вы её к использованию.
Да и пока времени маловато.
>>Интересно было бы узнать реальную разницу в скорости под юниксом всех трёх действующих вариантов. Стоило ли копья ломать?!
>
>Однозначно - из-за скорости - нет.

   
Rambler's Top100
вверх

Rambler's Top100 Яндекс.Метрика Яндекс цитирования