Задачка на С не на 5 минут

 
0
 
C++
ava
MGami | 02.10.2013, 13:24
Добрый день! Друг прислал ссылку с задачей на языке С. Показалось - очень простая. На деле - совсем нет.
Условия  тут: http://hola.org/jobs_ru.html 
Дорешал до:


int str_cpy(char **out_str, const char *arg)
{
        char *str = malloc(strlen(arg) + 1);

        if (str) {
                strcpy(str, arg);

                free(*out_str);

                /* update the result */
                *out_str = str;
        }
        else {
                /* error handling */
                return -1;
        }

        return 0;
}

int str_cat(char **out_str, const char *arg)
{
        size_t out_len = strlen(*out_str);
        char *str = realloc(*out_str, out_len + strlen(arg) + 1);

        if (str) {
                strcpy(str + out_len, arg);

                /* update the result */
                *out_str = str;
        }
        else {
                /* error handling */
                return -1;
        }

        return 0;
}
и застрял. Прошу помощи. Если решиам - приз отдам, не в призу уже дело:))) Или сами попробуйте...
Comments (14)
ava
feodorv | 02.10.2013, 13:05 #
Какой-то развод  smile Понятие об идеале у всех разное... Так пойдёт:

char *str_cpy( char **pdst, const char *src)
{
  char *s = *pdst;
  *pdst = strdup( src );
  if( s != NULL ) str_free( &s );
  return *pdst;
}

или нужно "эффективнее":

char *str_cpy( char **pdst, const char *src)
{
  if( *pdst != NULL && strlen(*pdst) >= strlen(src) )
    strcpy( *pdst, src);
  else
  {
    if( s != NULL ) str_free( &s );
    *pdst = strdup( src );
  }
}
ava
volatile | 02.10.2013, 16:43 #
Цитата
На этот проект выделено 25 000 долларов. В Израиле около 60 человек уже получили вознаграждение


60 x $500 = $30,000

Походу, у них перерасход бюджета уже.  smile 

И кстати, почему только в израиле? Что, в других странах не нашлось программистов способных решить столь сложную задачу?
ava
baldina | 02.10.2013, 21:29 #
они пишут, что решившие не с первого раза по 250 получают, так что с арифметикой в порядке.
но денег осталось мало, спешите  smile 
ava
bsa | 02.10.2013, 22:01 #
MGamifeodorv, у вас лишние ресурсы тратятся на измерение длины строки. strcpy работает медленней memcpy. А длина строки все равно вычисляется. Более того, можно использовать realloc для выделения памяти.
ava
volatile | 02.10.2013, 23:28 #
Цитата (bsa @  2.10.2013,  22:01 findReferencedText)
 memcpy

меммув лучше заюзать, там накладываются строки у них.
ava
bsa | 03.10.2013, 00:11 #
volatile, memmove лучше не использовать. Так как это уже неоптимально - лишняя буферизация.
ava
volatile | 03.10.2013, 08:24 #
Цитата (bsa @  3.10.2013,  00:11 findReferencedText)
volatile, memmove лучше не использовать.

В варианте предложенным feodorv, нет разговора, лучше или хуже.
Мы там просто обязаны использовать memmove, потому-что у них в примере есть такой вызов:
    str_cpy(&s, s+5);
здесь memcpy (как впрочем и strcpy) поведет себя неопределенным образом.

Цитата (bsa @  3.10.2013,  00:11 findReferencedText)
Так как это уже неоптимально - лишняя буферизация. 

нет никокой лишней буферизации, мы уже это обсуждали с вами.
ava
MGami | 03.10.2013, 09:41 #
Вот тут прикольные размышления на эту тему и, кстати, о том, кто уже получил бабки:)))

http://habrahabr.ru/post/193308/
ava
akizelokro | 03.10.2013, 15:24 #
Я вообще не уверен в порядке вычисления в строках, инициализируемых в параметрах (но я не особо лихой программист, если по чесноку).
Я что-то всегда считал, что подобная конструкция

func(char ** dest, "Hola Hola");


может в разных компиляторах исполняться либо как


char * temp = "Hola Hola";
func(dest, temp);


либо как


char * temp;
func(dest, temp);
temp = "Hola Hola";


added later:
Отсюда я бы начал с того, что сигнатура функций должна быть другой
ava
volatile | 03.10.2013, 15:55 #
Цитата (akizelokro @  3.10.2013,  15:24 findReferencedText)
Я что-то всегда считал, что подобная конструкция 

func(char ** dest, "Hola Hola");

К слову, подобная конструкция вообще не скомпилируеца, но не будем придирацца
вы видимо имели ввиду вызов функции:

func(dest, "Hola Hola");

Здесь порядок будет именно таким:
const char * temp = "Hola Hola";
func(dest, temp);

А то что вы слышали звон про неопределенность порядка вычисления аргуметнов функций, то не от туда он.
Неопредееленность здесь в том что неизвестно, что вычислится первым
dest или temp

ava
akizelokro | 03.10.2013, 16:01 #
Цитата (volatile @  3.10.2013,  15:55 findReferencedText)
А то что вы слышали звон про неопределенность порядка вычисления аргуметнов функций, то не от туда он.

Неопредееленность здесь в том что неизвестно, что вычислитс


Спасибо большое!
ava
bsa | 09.10.2013, 23:22 #
Я бы сделал как-то так:
/* Copyright (C) Hola 2012, 2013
*
* Welcome to TheCodeIL.com Challenge!
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>

void str_cpy(char **dst, const char *src)
{
    size_t size = strlen(src) + 1; //do not forget of '\0'
    char *ret = (char*)malloc(size);
    memcpy(ret, src, size);
    if (*dst)
       str_free(dst);
    *dst = ret;
}

void str_cat(char **dst, const char *src)
{
   if (*dst) {
      size_t src_size = strlen(src) + 1;
      size_t dst_size = strlen(*dst);
      *dst = (char*)realloc(*dst, src_size + dst_size);
      memcpy(*dst + dst_size, src, src_size);
   } else
      str_cpy(dst, src);
}

int main(int argc, char *argv[])
{
    char *s = NULL;
    str_cpy(&s, "Hola Hola");
    str_cpy(&s, s+5);
    str_cat(&s, " World");
    str_printf(&s, "%s!", s);
    puts(s); /* result: "Hola World!" */
    str_free(&s);
    return 0;
}
ava
feodorv | 12.10.2013, 11:40 #
Цитата (volatile @  3.10.2013,  09:24 findReferencedText)
Мы там просто обязаны использовать memmove

Ну да, однозначно memmove.
Я просто хотел понять, что "идеальнее" с точки зрения hola.org: использовать старую память, если в неё влезает строка (а единственный доступный способ - сравнить длины строк), или лучше каждый раз перезаказывать память smile Есть некоторый намёк на то, что всё не просто:
Цитата
эффективная реализация функций str_cpy и str_cat умещается в 7 строк кода на функцию

Куда там 7 строк для str_cpy, если делаем банальный strdup.


Цитата (bsa @  10.10.2013,  00:22 findReferencedText)
В str_cpy нельзя использовать realloc, так как он сделает неверным указатель src. 

Можно проверять перекрытие строк smile Но опять-таки, входит это в понятие "идеальности" или нет...


Цитата (bsa @  10.10.2013,  00:22 findReferencedText)
    if (*dst)
     str_free(*dst);

Мне почему-то кажется, что str_free проверит аргумент на NULL. И таки str_free(dst)...
ava
bsa | 14.10.2013, 09:53 #
feodorv, проверку перекрытия строк без своего аллокатора не напишешь.
А вот у меня нет уверенности, что str_free делает проверку.
Please register or login to write.
Firm of day
Вы также можете добавить свою фирму в каталог IT-фирм, и публиковать статьи, новости, вакансии и другую информацию от имени фирмы.
Подробнее
Contributors
advanced
Submit