LINUX.ORG.RU

[C++][критика]Отругайте реализацию задачки

 ,


0

1

Началось с того, что смотрел вакансии на одном сайте. Увиденная задачка заинтересовала и заставила вспомнить былое. Вакансия, к слову, из ДС. Стало интересно, насколько мои высушенные мозги годятся для дела в нормальных конторах.

Есть последовательность идентификаторов, строящаяся по особым правилам: 1. Первый идентификатор последовательности имеет вид «A1». Второй - «A2», третий - «A3» и так далее.

За «A9» следующий - «B1». Следующий после «Z9» имеет вид «A1-A1», потом «A1-A2» и так далее.

После «A1-Z9» следующим идет «A2-A1».

2. Максимальная длина идентификатора - десять групп по два символа. 3. В идентификаторах никогда не должны присутствовать буквы «D», «F», «G», «J», «M», «Q», «V», и цифра «0».

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

Функция должна получать в качестве входного параметра строку с идентификатором из описанной последовательности, и генерировать на выходе строку, содержащую следующий идентификатор последовательности. Например, функция получает «A1-Z9» и возвращает «A2-A1».

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

main.cpp

#include <iostream>
#include <cstring>

#include "cmeganumber.h"

using namespace std;

int main(int argc, char** argv)
{
    CMegaNumber t;
    t = "C9-Z9-Z9-Z9-Z9-Z9-Z9-Z9-Z9-Z9";
    cout << "baseval = " << t.szvalue() << endl;
    cout << "newval = " << (++t).szvalue() << ", overflow = " << t.m_bOverflow << endl;
    return 0;
}
cmeganumber.h
#ifndef CMEGANUMBER_H_INCLUDED
#define CMEGANUMBER_H_INCLUDED

class CMegaNumber
{
    private:
        char m_lpszValue[30];
        bool m_bAssigned;
    public:
        bool m_bOverflow;
        CMegaNumber();
        CMegaNumber& operator=(const char * lpszValue);
        CMegaNumber& operator++();
        char * szvalue() { return m_lpszValue; };
};

#endif // CMEGANUMBER_H_INCLUDED
cmeganumber.cpp
#include <cstring>

#include "cmeganumber.h"

// CMegaNumber implementation
/* constructor
    */
CMegaNumber::CMegaNumber()
{
    m_bOverflow = false;
    m_bAssigned = false;
    memset(m_lpszValue, 0, 30);
}
/* assignment operator overload
    */
CMegaNumber& CMegaNumber::operator=(const char * lpszValue)
{
    if(30 <= strlen(lpszValue))
    {
        strcpy(m_lpszValue, "err-too-long");
        m_bAssigned = false;
        return *this;
    }
    strcpy(m_lpszValue, lpszValue);
    m_bAssigned = true;
    return *this;
}
/* pre-increment operator overload
    */
CMegaNumber& CMegaNumber::operator++()
{
    if(!m_bAssigned)
    {
        strcpy(m_lpszValue, "err-not-assigned");
        return *this;
    }
    bool bIncHigh = false;
    char * p = m_lpszValue + strlen(m_lpszValue) - 1;
    *p == '9' ? *p = '1', bIncHigh = true : (*p)++;
    p--;
    if(bIncHigh)
    while(p >= m_lpszValue && bIncHigh)
    {
        switch(((unsigned long)p - (unsigned long)m_lpszValue) % 3)
        {
            case 1:
            *p == '9' && bIncHigh ? *p = '1' : ((*p)++, bIncHigh = false);
            break;
            
            case 0:
            *p == 'Z' && bIncHigh ? *p = 'A' : ((*p)++, bIncHigh = false);
            while(*p == 'D' ||
                  *p == 'F' ||
                  *p == 'G' ||
                  *p == 'J' ||
                  *p == 'M' ||
                  *p == 'Q' ||
                  *p == 'V') (*p)++;
            break;
            
            case 2:;
        }
        p--;
    }
    m_bOverflow = bIncHigh;
    return *this;
}

★★

Ответ на: комментарий от amomymous

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

m1rag3 ★★
() автор топика

> char m_lpszValue[30];

bool m_bAssigned;

bool m_bOverflow;



Венгерская нотация. Убивать.

Следующий после «Z9» имеет вид «A1-A1»


Эм... Не увидел в коде места, где происходит удлинение цепочки после переполнения самого левого узла. Плохо смотрел?

geekless ★★
()
Ответ на: комментарий от geekless

> Эм... Не увидел в коде места, где происходит удлинение цепочки после переполнения самого левого узла. Плохо смотрел?

Мля... И куда только смотрел...

m1rag3 ★★
() автор топика
Ответ на: комментарий от geekless

> Венгерская нотация. Убивать.

Привычка))

m1rag3 ★★
() автор топика
Ответ на: комментарий от Deleted

Конкретно тут нужен указатель на байтовый тип, он же char.

m1rag3 ★★
() автор топика

Без itertools, чтобы не читерить.

IGNORE = set(["D", "F", "G", "J", "M", "Q", "V"])

def inc_letter(l):
    l = chr(ord(l) + 1)
    if l in IGNORE:
        return inc_letter(l)
    elif l > 'Z':
        return None

    return l

def inc_cell(cell):
    l, n = cell
    n = chr(ord(n) + 1)
    if n > '9':
        l = inc_letter(l)
        if not l:
            return None

        return l + '1'
    else:
        return l + n

def get_next_internal(seq):
    if not seq:
        return ['A1']

    head = seq[:-1]
    tail = seq[-1]

    tail = inc_cell(tail)
    if not tail:
        head = get_next_internal(head)
        tail = 'A1'

    return head + [tail]

def get_next(seq):
    result = get_next_internal(seq.split('-'))

    if len(result) > 10:
        return None

    return '-'.join(result)

if __name__ == '__main__':
    seq = 'A1'
    for i in range(100000):
        seq = get_next(seq)
        print seq
baverman ★★★
()
Ответ на: комментарий от baverman

[ansi-c] как-то так

#include <stdio.h>
#include <string.h>
#include <ctype.h>


static int is_valid(const char *p) {
    if (p == NULL || strlen(p) != strspn(p, "ABCEHIKLNOPRSTUWXYZ123456789-"))
        return 0;

    goto skip_minus;
    do {
        if (*p++ != '-')
            return 0;
    skip_minus:
        if (!isalpha(p[0]) || !isdigit(p[1]))
            return 0;
    } while (*(p += 2));

    return 1;
}

static int inc(char *p) {
    static const signed char inctab[26] = {
    /*  A B C d E f g H I j K L m N O P q R S T U v W X Y Z */
        1,1,2,0,3,0,0,1,2,0,1,2,0,1,1,2,0,1,1,1,2,0,1,1,1,-25
    };
    char *t;

    if (!is_valid(p))
        return -1;

    for (t = strchr(p, '\0') - 1; t > p && ++*t > '9'; t -= 2) {
        *t-- = '1';
        if ((*t += inctab[*t - 'A']) != 'A')
            break;
        if (t == p && strlen(p) < 32)
            strcat(p, "-A1");
    }

    return 0;
}

int main() {
    char str[33] = "Z9-Z8";

    puts(str);
    inc(str);
    puts(str);
    inc(str);
    puts(str);
    inc(str);
    puts(str);

    return 0;
}
arsi ★★★★★
()
Ответ на: комментарий от yoghurt

Теперь это пиписькомерка-тред.

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

baverman ★★★
()

тесты где тесты? библиотечный класс мля

trashymichael ★★★
()
Ответ на: комментарий от m1rag3

В первую очередь неприятно обилие безымянных констант, смысл которых неясен:

f(30 <= strlen(lpszValue))

Почему 30? Лучше ввести именованную константу с «говорящим» названием. Тогда и комментарии не обязательны.

*p == '9' ? *p = '1', bIncHigh = true : (*p)++;

Здесь операция «запятая», тернарный оператор, нету скобок. Такая комбинация любым style guide запрещена. Лучше был бы оператор if.

while(*p == 'D' || и т.д.

Лучше бы смотрелась функция, проверяющая символ на допустимость.

Ну и все в таком ключе.

amomymous ★★★
()

Еще один, не менее наглядный вариант:

import itertools

CELL_TO_ORD = {}
ORD_TO_CELL = {}
for i, cell in enumerate(itertools.product('ABCEHIKLNOPRSTUVWXYZ', '123456789')):
    cell = ''.join(cell)
    CELL_TO_ORD[cell] = i
    ORD_TO_CELL[i] = cell

def get_next_internal(seq):
    if not seq:
        return ['A1']

    head = seq[:-1]
    tail = seq[-1]

    try:
        tail = ORD_TO_CELL[CELL_TO_ORD[tail] + 1]
    except KeyError:
        head = get_next_internal(head)
        tail = 'A1'

    return head + [tail]

def get_next(seq):
    result = get_next_internal(seq.split('-'))

    if len(result) > 10:
        return None

    return '-'.join(result)

if __name__ == '__main__':
    seq = 'A1'
    for i in range(100000):
        seq = get_next(seq)
        print seq
baverman ★★★
()
Ответ на: комментарий от staseg

> //Пока самый красивый вариант у arsi

+1

m1rag3 ★★
() автор топика
Ответ на: комментарий от baverman

> По теме. ТС, твой код ужасен, потому что нечитабелен.

да нет, вполне читабелен - идея понятна, но конечно вариант arsi гораздо проще

aho
()
Ответ на: комментарий от Gorthauer

> Где здесь С++? Я вижу только монстра «си с классами»

нормальный код на С++( не случай ТС ) - как раз «си с классами» + STL

aho
()
Ответ на: комментарий от aho

Стоит ли для такой простой задачи наворачивать код из STL, когда даже на чистом C реализация элементарна. Только лишнее использование памяти и увеличение объема машинного кода.

m1rag3 ★★
() автор топика
Ответ на: комментарий от baverman

> годную для обучения обезьян

Ждём новость в толксах: обезьяна украла у baverman-а ноутбук, написала программу на питоне, а затем потроллила на ЛОРе.

geekless ★★
()

предложенная задача - в точности задача на системы счисления. впрочем сильно завуалированная :) Все что по идее надо сделать - перевести кривую человеко-читаемую форму во внутреннее представление (а-ля BCD «двоично-десятичная»), прибавить еденицу, скорректировать переносы и результат перевести обратно. А точнее породить класс реализующий операции с этой кривой системой счисления.

Максимальное число в разрядной сетке 20(кол-во буков в старшей части) * 9(кол-во цифирь в младшей) - 1 = 179. Итого одного байта внутреннего представления хватит и на разряд и на небольшие переносы. А лучше взять int чтобы в него точно помещались переносы сложения и умножения (179^2).

Всё прочее можно подсмотреть в реализациях BCD (наверняка школьники и студенты породили тыщи)

MKuznetsov ★★★★★
()
Ответ на: комментарий от MKuznetsov

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

m1rag3 ★★
() автор топика
Ответ на: комментарий от geekless

Права на программу тоже будут public domain? Нет пути!

baverman ★★★
()
Ответ на: комментарий от m1rag3

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

Получение следующего «большого идентификатора» сведётся к операции на стеке (чтобы начинать с младших разрядов) и получении следующего «маленького идентификатора» (можно по единожды сгенерённой таблице).

MKuznetsov ★★★★★
()
Ответ на: комментарий от MKuznetsov

> выйдет класс-паралитик

вышел

fixed :)

m1rag3 ★★
() автор топика
Ответ на: комментарий от baverman

Перенимаю эстафету

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

Для начала расширяем имеющиеся классы нужным нам функционалом:

Character extend [
    code [
        <category: 'convenience'>
        ^self asInteger
    ]

    isRevolved [
        <category: 'testing'>
       ^self = $A
    ]

    nextForChain [
        <category: 'stream protocol'>
        | range code ch | 
        range := ReadStream on: ($A code to: $Z code).
        range position: (1 + self code - $A code).
        [(code := range next)
             ifNotNil: [ch := code asCharacter.
                        ('DFGJMQV' includes: ch) ifFalse: [^ch]]
             ifNil: [range reset]
        ] repeat
    ]
]

Integer extend [
    isRevolved [
        <category: 'testing'>
       ^self = 1 
    ]

    nextForChain [
        <category: 'stream protocol'>
        | r |
        r := (self + 1) \\ 10.
        r = 0 ifTrue: [r := 1].
        ^r
    ]
]

Запись «мега-числа» в виде «A1-A1-A1» по сути представляет собой цепь из счётчиков-сегментов. Класс отдельного сегмента:

Object subclass: Segment [
    | char digit |

    Segment class >> parser [
        <category: 'parser factory'>
        ^#letter asParser, #digit asParser
            => [:nodes |
                self new letter: nodes first
                         digit: nodes second digitValue]
    ]

    Segment class >> from: aString [
        <category: 'instance creation'>
        ^self parser parse: aString
    ]

    letter: aChar digit: aDigit [
        <category: 'initialization'>
        char := aChar.
        digit := aDigit
    ]

    incr [
        <category: 'incrementing'>
        digit := digit nextForChain.
        digit isRevolved ifTrue: [char := char nextForChain]
    ]

    isRevolved [
        <category: 'testing'>
        ^char = $A and: [digit = 1]
    ]

    printOn: aStream [
        <category: 'printing'>
        aStream nextPut: char; nextPutAll: digit asString
    ]
]

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

Object subclass: Chain [
    | segments |

    Chain class >> parser [
        <category: 'parser factory'>
        ^(Segment parser, $- asParser => [:nodes | nodes first]) star, Segment parser
    ]

    Chain class >> from: aString [
        | r nodes |
        r := self new.
        nodes := self parser parse: aString.
        r segments addAll: nodes first; add: nodes second.
        ^r
    ]

    incr [
        <category: 'incrementing'>
        self segments reverseDo:
            [:each |
            each incr.
            each isRevolved ifFalse: [^self]].
        self segments first isRevolved ifTrue:
            [self segments addFirst: (Segment new letter: $A digit: 1)]
    ]

    segments [
        <category: 'accessing'>
        ^segments ifNil: [segments := OrderedCollection new]
    ]

    printOn: aStream [
        <category: 'printing'>
        self segments isEmpty
            ifTrue: [aStream nextPutAll: 'an empty Chain']
            ifFalse: [self segments first printOn: aStream.
                      self segments allButFirst do:
                          [:each | aStream nextPut: $-.
                                   each printOn: aStream]]
    ]
]

Объекты счётчика и цепи инициализируются из строк. Разбор производится посредством простющих комбинаторных парсеров (зависимость - PetitParser).

В REPL:

st> c := Chain from: 'C9-Z9-Z9-Z9-Z9-Z9-Z9-Z9-Z9-Z9'
C9-Z9-Z9-Z9-Z9-Z9-Z9-Z9-Z9-Z9
st> c incr
E1-A1-A1-A1-A1-A1-A1-A1-A1-A1
st>

Кажется, всё верно. Тестами лень покрывать, патчи принимаются :)

yoghurt ★★★★★
()
Ответ на: комментарий от MKuznetsov

или вообще вхреначить отдельный абстрактный класс(или даже шаблон) реализующий упорядочную последовательность «букв» (С1,Z9..) алфавита со своими «bool allowed(T&)», «im<T> &next(im<T>&)», «bool islast(im<T>&)» ; Потом производный класс - конретно заданный алфавит

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

вот он правильный путь OO в C++ (и не только)! Решение конкретной задачи в абстрактном виде и получение моря ненужного reusable кода. Программер припахан, тестеровщик матерится, процессоры греются, память кончается, библиотеки шаблонов пухнут и все щастливы - потому как полный ентерпрайс и вообще очень прогрессивно.

MKuznetsov ★★★★★
()
Ответ на: комментарий от MKuznetsov

>или вообще вхреначить отдельный абстрактный класс(или даже шаблон) реализующий упорядочную последовательность «букв» (С1,Z9..) алфавита со своими «bool allowed(T&)», «im<T> &next(im<T>&)», «bool islast(im<T>&)» ; Потом производный класс - конретно заданный алфавит

Да, это ещё круче

yoghurt ★★★★★
()
Ответ на: комментарий от yoghurt

...впрочем, если в моём варианте вместо наращивания стандартных классов вести два новых, кое-что упростить, а кое-что усложнить, примерно оно и получится :)

yoghurt ★★★★★
()

афтар, не надо писать на крестах, умоляю

делается 2 класса: один отвечает за цифру, другой — за всё число. неужели в условии задачи не было намёка на это?

anonymous
()
Ответ на: комментарий от geekless

а чем плоха венгерская нотаций?

// код пишу в vim, очень удобно когда одного взгляда на имя переменной становится что и зачем это

anonymous
()
Ответ на: комментарий от anonymous

> афтар, не надо писать на крестах, умоляю

Ну отчего же. Хороший язык. К тому же по заданию именно плюсы. Было бы странно на вакансию приплюснутого кодера отправлять код на каком-нибудь питоне.

делается 2 класса: один отвечает за цифру, другой — за всё число

Такая мысль тоже была, но все-таки остановился на «класс-паралитик с исключительно статическими членами»(ц) :)

m1rag3 ★★
() автор топика
Ответ на: комментарий от anonymous

> а чем плоха венгерская нотаций?

Самому не очень нравится, но, как уже сказал, привычка. Кстати, отсюда вопрос, как щас оформляют Ъ-интерпрайс код, не имеющий отношения к OSS (тут, я думаю, все согласно заветам дяди Столлмана).

m1rag3 ★★
() автор топика

memset(m_lpszValue, 0, 30); - минус за «30» ибо «magic numbers» [code=cpp] if(30 <= strlen(lpszValue)) { strcpy(m_lpszValue, «err-too-long»); m_bAssigned = false; return *this; } [/code] - опять «magic number» - тут нужно экзепшн бросать, или «false» возвращать, но никак не записывать НЕПОТРЕБЩИНУ в переменную-член класса из-за того что кто-то решит неправильно применить оператор =. Я считаю это грубой ошибкой. И опять таки даже для этого «err-to-long» нет своей зарезервированной константы.

Это то, что бросилось сразу в глаза. Ну а с точки зрения алгоритма - это простое сложение, тут вспоминается прямо таки машина Тьюринга, для которой такая задача - канонический пример :)

anonymous
()
Ответ на: комментарий от anonymous

> я имел в виду, что лично вам не надо

на си тоже, кстати

Нууу, скажете тоже...

m1rag3 ★★
() автор топика

Что бросилось в глаза:
- используйте список инициализации;
- венгерская системная ноттация - говно, используйте венгерскую для приложений (http://www.ugolnik.info/?p=1010);
- «магигические» числа зло (в вашем случае это размер массива m_lpszValue);
- для копирования строки строки используйте strncpy();
- если это c++, то почему бы не использовать vector и string?

andreyu ★★★★★
()
Ответ на: комментарий от geekless

> > char m_lpszValue[30];

> bool m_bAssigned;

> bool m_bOverflow;


Венгерская нотация. Убивать.



Это системная венгерская. Венгерская для приложений весьма достойная штука.

andreyu ★★★★★
()
Ответ на: комментарий от andreyu

Спасибо за дельный комментарий, со всем согласен кроме

- если это c++, то почему бы не использовать vector и string?

Уже высказался выше на эту тему:

Стоит ли для такой простой задачи наворачивать код из STL, когда даже на чистом C реализация элементарна. Только лишнее использование памяти и увеличение объема машинного кода.

m1rag3 ★★
() автор топика
Ответ на: комментарий от m1rag3

>Стоит ли для такой простой задачи наворачивать код из STL, когда даже на чистом C реализация элементарна. Только лишнее использование памяти и увеличение объема машинного кода.

Тут даже не в машкоде дело. В данном случае char[XX] хватает с головой, никакие плюшки из плюсовой строки попросту не нужны.

staseg ★★★★★
()
Ответ на: Перенимаю эстафету от yoghurt

эстафета

Ruby

class Chain
  class Pair
    Allowed_chars = %w{ a b c f h i k l n o p r s t u w x y z }
    Allowed_numbers = (1..9)

    def initialize(pair = nil)
      pair ||= Allowed_chars.min + Allowed_numbers.min.to_s

      pair = pair.split ''
      raise ArgumentError, 'wrong pair!' unless pair.size == 2 and
        Allowed_chars.include? pair[0] and Allowed_numbers.include? pair[1].to_i

      @pair = [ pair[0], pair[1].to_i ]
    end

    def next!
      if @pair[1] == Allowed_numbers.max then
        @pair[1] = Allowed_numbers.min
        loop do

          if @pair[0] == Allowed_chars.max then
            @pair[0] = Allowed_chars.min.dup
            raise RangeError
          else
            @pair[0].next!
            break if Allowed_chars.include? @pair[0]
          end

        end
      else
        @pair[1] += 1
      end
    end

    def to_s
      @pair[0].upcase + @pair[1].to_s
    end
  end


  def initialize(string = nil)
    @chain = Array.new
    from_s string if string
  end

  def from_s(string)
    @chain.clear

    string.downcase.split('-').reverse.each do |pair|
      @chain << Pair.new(pair)
    end
  end

  def next!
    raise ArgumentError, 'chain is empty!' if @chain.empty?

    current = 0
    begin
        @chain[current].next!
      rescue RangeError
        current += 1
        retry if current != @chain.size
        @chain << Pair.new
      end
  end

  def to_s
    @chain.reverse.join('-')
  end
end


chain = Chain.new('z9-a5')

2000.times do
  chain.next!
end

puts chain

do0dlez ★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.