Երեք պատահական խնդիր

Արտահայտության հապավում

Խնդիրը։ Տրված է ինչ-որ արտահայտություն, օրինակ, «Միացյալ ազգերի կազմակերպություն» և պահանջվում է սրանից ստանալ «ՄԱԿ» հապավումը։

Դպրոցականը կամ ուսանողը, հավանաբար, առաջին լուծումը կտանի այսպես. տողը դարձնել ցուցակ, հետո անցնել տողի վրայով ու հավաքել բոլոր այն տառերը, որոնց նախորդում են տառ չհանդիսացող այլ սիմվոլներ։ Հետո՝ հավաքած տառերը դարձնել մեծատառ ու միավորել մեկ տողի մեջ։

Տողից նիշերի ցուցակ ստացվում է coerce ֆունկցիայով.

(coerce "abcd" 'list)    ; => (#\a #\b #\c #\d)

Նույն coerce ֆունկցիայով նիշերի ցուցակից ստացվում է տող.

(coerce '(#\a #\b #\c #\d) 'string)    ; => "abcd"

Նիշերի ցուցակից բառերի առաջին տառերն ընտրող ֆունկցիան կարելի է գրել ռեկուրսիվ եղանակով։

(defun select-first-letters (sl)
    (if (endp sl)
        '()
        (if (and (not (alpha-char-p (car sl))) (alpha-char-p (cadr sl)))
            (cons (cadr sl) (select-first-letters (cddr sl)))
            (select-first-letters (cdr sl)))))

Դե իսկ հապավում կառուցող ֆունկցիան արդեն կարելի է կառուցել այսպես․

(defun acronym-of (s)
    (string-upcase (coerce (select-first-letters (coerce s 'list)) 'string)))

Բայց այս ֆունկցիան ճիշտ չի աշխատելու, որովհետև տողի առաջին տառը, որը պետք է լինի հապավման առաջին տառը, չի բավարարում select-first-letters ֆունկցիայի 4֊րդ տողում գրված պայմանին։ Այդ թերությունը շտկելու համար պետք է պարզապես տողը նիշերի ցուցակ դարձնելուց հետո դրա սկզբից կցել մի որևէ նիշ։ Այսինքն acronym-of ֆունկցիան սահմանել հետևյալ կերպ․

(defun acronym-of (s)
    (string-upcase (coerce (select-first-letters (cons #\Space (coerce s 'list)) 'string))))

Սրա հետևանքով select-first-letters ֆունկցիայի երկրերդ տողում գրված պայմանը կձևափոխվի․

(defun select-first-letters (sl)
    (if (or (endp sl) (endp (cdr sl)))
        '()
        (if (and (not (alpha-char-p (car sl))) (alpha-char-p (cadr sl)))
            (cons (cadr sl) (select-first-letters (cddr sl)))
            (select-first-letters (cdr sl)))))

* * *

Փորձառու ծրագրավորողն այսպիսի բան, իհարկե, չի գրի։ Նա միանգամից կնկատի, որ արտահայտության հապավումը կառուցելու համար բավական է մեծատառ դարձնել բառերի միայն առաջին տառերը, իսկ մնացածները թողնել փոքրատառ։ Հետո դեն գցել ամեն ինչ՝ բացի մեծատառերից։

(defun acronym (text)
    (remove-if-not #'upper-case-p (string-capitalize text)))

Սա Արդեն ֆունկցիոնալ լուծում է։ string-capitalize ֆունկցիան վերադարձնում է տողը՝ որում բառերի միայն առաջին տառերն են մեծատառ։ remove-if-not ֆունկցիան ֆիլտրող ֆունկցիա է. այն իր երկրորդ արգումենտում տրված հաջորդականությունից դեն է գցում իր առաջին արգումենտում տրված պրեդիկատին չբավարարող տարրերը։

* * *

Տիպիկ C-ական լուծումն էլ այսպիսին կլինի.

void acronym(const char *text, char *acr)
{
    *acr++ = toupper(*text++);
    while( *text != '\0' ) {
        if( isalpha(*text) && !isalpha(*(text-1)) )
            *acr++ = toupper(*text);
        ++text;
    }
    *acr = '\0';
}

 

Բառերի հեմինգյան հեռավորություն

Խնդիրը։ Երկու նույն երկորությունն ունեցող բառերի հեմինգյան հեռավորություն է կոչվում դրանց նույն դիրքերում տարբերվող տառերի քանակը։ Օրինակ, abc և abc բառերի հեմինգյան հեռավորությունը զրո է, իսկ abc և aec բառերի հեմինգյան հեռավորությունը մեկ է, և այլն։

Իտերատիվ լուծումը կարող է լինել loop մակրոսի օգտագործմամբ։ Երկու զուգահեռ հաշվիչներ անցնում են տողերի վրայով և համեմատում են նույն դիրքում գտնվող տառերը։ Եթե դրանք տարբեր են, ապա հաշվարկման արդյունքին գումարվում է մեկ։

(defun hamming-distance (so si)
    (loop for x across so
          for y across si
          when (char-not-equal x y)
          sum 1))

Ֆունկցիոնալ լուծման առաջին մոտարկումը կարող է լինել այսպես. map ֆունկցիայով տրված բառերից կառուցվում է մի ցուցակ, որի i-րդ դիրքում գրված է 0` եթե բառերի i-րդ դիրքերի տառերը հավասար են, և 1՝ հակառակ դեպքում։ Այնուհետև apply ֆունկցիայով + գործողությունը կիրառվում է այդ ցուցակի նկատմամբ՝ վերադարձնելով տարբերվող տառերի քանակը։

(defun hamming-distance (so si)
    (apply #'+ (map 'list #'(lambda (x y) (if (char-equal x y) 0 1))
           so si)))

Վերջնական ֆունկցիոնալ լուծումն ավելի լավն է. նույն map ֆունկցիայով ստեղծվում է char-not-equal ֆունկցիայի արդյունքների ցուցակ՝ կազմված t-երից և nil-երից։ Իսկ հետո count ֆունցիայով հաշվվում է t-երի քանակը, որն էլ հենց տրված բառերի հեմինգյան հեռավորությունն է։

(defun hamming-distance (so si)
    (count t (map 'list #'char-not-equal so si)))

* * *

C-ական իրականացումը պարզապես հաշվում է բառերի նույն դիրքում տարբերվող տառերի քանակը.

unsigned int hamming_distance(const char *so, const char *si)
{
    unsigned int dist = 0;
    while( *so != '\0' && *si != '\0' )
        if( *so++ != *si++ )
            ++dist;
            
    return dist;
}

 

Ենթացուցակի ստուգում

Խնդիրը։ Ստուգել, թե արդյոք s₀ ցուցակը s₁ ցուցակի ենթացուցակն է։ Օրինակ, [3, 4, 5] ցուցակը [1, 2, 3, 4, 5, 6] ցուցակի ենթացուցակ է։

Միանգամից «ֆունկցիոնալ» լուծումը. s₀-ն s₁-ի ենթացուցակ է, եթե կա՛մ s₀-ն համընկնում է s₁-ի սկիզբի հետ՝ նրա պրեֆիքսն է, կա՛մ s₀-ն s₁-ի պոչի ենթացուցակն է։

Common Lisp լեզվով գրառումը.

(defun is-sublist (so si)
    (or (is-prefix so si)
        (is-sublist so (cdr si))))

is-prefix ֆունկցիայի իրականացումն էլ շատ հետաքրքիր է.

(defun is-prefix (so si)
    (not (member nil (mapcar #'eq so si))))

mapcar ֆունկցիայով կառուցվում է երկու ցուցակների համապատասխան տարրերի՝ իրար հավասար լինելու (կամ չլինելու) ցուցակը։ member ֆունկցիայով այդ ցուցակում որոնվում է որևէ nil արժեք, իսկ not ֆունկցիայով էլ պահանջվում է, որ nil չլինի։

C լեզվով պրեֆիքսի և ենթացուցակի ստուգման ֆունկցիաները կունենան հետևյալ ոչ պակաս հետաքրքիր տեսքը.

Եթե, օրինակ, ցուցակի հանգույցը սահմանված է այսպես.

struct node {
    char data;
    struct node *next; 
};

ապա s ցուցակի՝ l ցուցակի պրեֆիքս լինելը կաստուգվի այսպես.

bool is_prefix(const struct node *s, const struct node *l)
{
    while( NULL != s && NULL != l && s->data == l->data ) {
        s = s->next;
        l = l->next;
    }
    
    return NULL == s;
}

իսկ s ցուցակի՝ l ցուցակի ենթացուցակ լինելն էլ այսպես.

bool is_sublist(const struct node *s, const struct node *l)
{
    if( NULL == s )
        return true;

    if( NULL == l )
        return false;

    return is_prefix(s, l) || is_sublist(s, l->next);
}