UProLa

Неокріпші думки

Розбити рядок прогаликами

with 56 comments

Пост для тренування мізків. Дозволяється використовувати будь-яку мову. Дозволяється висловлювати свою думку на рахунок чужого коду (code review). Дозволяєтсья пропонувати НЕоптимальні варіанти – типу “а ось так робити не варто!”.

Задача

Вказаний рядок розбити прогаликами на блоки по 4.
Приклад: “ХХХХХХХХХ” -> “XXXX XXXX X”
Застосування: номер банківської картки потрібно відобразити розбитим на блоки по 4 символи, для зручності.

Python

Моє рішення йде через рекурсію (щиро сподіваюсь, що python знає про tail call). Чи зможете Ви запропонувати інше рішення задачі?

def maskString(str):
    breakLine = lambda str: [str] \
                            if len(str) <= 4 \
                            else [str[:4]] + breakLine(str[4:])
    return " ".join(breakLine(str))

by bunyk

Ітерація по всім символам з додаванням прогаликів у потрібних місцях.

def spaced_blocks(s):
    g = (x+' ' if i % 4 == 3 else x for i, x in enumerate(s))
    return ''.join(g).strip()

by Александр Щапов

Використовуємо зручний Пайтонівський спосіб вирізання рядка (порівняй з кількістю символів для виклику методу substring у інших мовах).

def make_me_spaced(s):
    return ' '.join((s[x:x + 4] for x in range(0, len(s), 4)))

F#

Мій пайтонівський алгоритм, але записаний іншими словами і (sic!) без явної рекурсії.

let maskString =
    Seq.unfold(fun state -> match String.length state with
                            | 0 -> None
                            | x -> Some(state.Substring(0,min x 4),state.Substring(min x 4)))
    >> Seq.reduce (fun r s -> r + " " + s)

Clojure

by alexyakushev

Функціональний варіант не прокатив, тому був запропонований частково імперативний підхід.

(use '[clojure.string :only (join)])

(defn spaceString [t]
  (->> (for [c [(count t)] i (range 0 c 4)]
         (.substring t i (min (+ i 4) c)))
       (interpose " ") join))

Трошки поміркувавши, автор видав правильне, функціональне рішення.

(use '[clojure.string :only (join)])

(def spaceString
  (comp join flatten
        (partial interpose " ")
        (partial partition 4 4 nil)))

Common Lisp

by dmytrish

Через рекурсію. Не впевений, що тут застосовна хвостова оптимізація…

(defun spacify (s) 
  (if (> 5 (length s)) 
      s 
      (concatenate 'string (subseq s 0 4) " " (spacify (subseq s 4)))))

Haskell

by Winnie

donut – це так автор назвав функцію makeSpaced (для тих, хто не в курсі).

donut s = donut' (-1) s
  where donut' _ [] = []
        donut' 3 (x:sx) = ' ' : x : donut' 0 sx
        donut' i (x:sx) = x : donut' (i+1) sx

by Dmytro Sirenko

spacify s = unwords (map (take 4) (takeWhile (not.null) (iterate (drop 4) s)))

Regular Expressions

by Чувак, юзающий регекспы

Реально круте рішення!

/(....)(?!$)/
replace with
/$1 /

by bunyk

Зручніший варіант, пригодиться якщо будемо “маштабувати” код.

/(.{4})(?!$)/
replace with
/$1 /

K (kona implementation)

В спробі зробити коротше за регекспи рішення, отримав таку ось катавасію. У самого автора kona не вийшло зробити коротше, що означає – k не панацея.

{1_,/" ",/:(0 +\4+&_(-1+#x)%4)_ x}

Written by danbst

Листопад 8, 2011 at 20:52

Оприлюднено в Програмування

Tagged with , , , ,

Відповідей: 56

Subscribe to comments with RSS.

  1. Якщо без рекурсії то ітерацією:

    >>> def spaced_blocks(s):
    ...     g = (x+' ' if i % 4 == 3 else x for i, x in enumerate(s))
    ...     return ''.join(g)
    ... 
    >>> spaced_blocks('asdfasdfs;flasasdfadf')
    'asdf asdf s;fl asas dfad f'
    

    bunyk

    Листопад 8, 2011 at 22:17

    • Ок, тільки коли довжина вхідного рядка кратна 4, то твій алгоритм дає лишній прогалик в кінці рядка. Додав strip(), додав в пост.

      А взагалі, я навіть не знав, що генераторні вирази можна писати в круглих дужках! Дякую.

      danbst

      Листопад 8, 2011 at 23:11

      • Блін, я от протестував на довжині < 4, на довжині 0. І чого я на довжині 4 протестувати не додумався?

        І, власне генераторні вирази пишуться тільки в круглих дужках, бо в квадратних це вже не генератори а списки. Бляха, знов забув як перекладається list comprehensions, а ще хочу Пілігрима перекласти….

        Хочеться ще переписати максимально ефективно на C, але там треба ще рахувати скільки пам’яті треба виділити під новий рядок, а так впадло🙂 .

        bunyk

        Листопад 8, 2011 at 23:23

        • до-речі, рішення не зовсім коректне. strip() уріже усі невидимі символи у кінці рядка, а повинно просто вставити прогалики у потрібні місця, навіть якщо весь рядок з них складається.

          згоден, протупив я, але може ти знаєш варіант, як покращити ситуацію?

          danbst

          Листопад 14, 2011 at 22:25

  2. Мне сразу подумалось такое:

    In [13]: def make_me_spaced(s, step):
    ....: return ' '.join([s[x:x + step] for x in range(0, len(s) + 1, step)]).strip()
    ....:

    In [14]: make_me_spaced('1234564312345434', 4)
    Out[14]: '1234 5643 1234 5434'

    Александр Щапов

    Листопад 9, 2011 at 15:52

  3. Ось мій варіант (Haskell)

    donut s = donut’ (-1) s
    where donut’ _ [] = []
    donut’ 3 (x:sx) = ‘ ‘ : x : donut’ 0 sx
    donut’ i (x:sx) = x : donut’ (i+1) sx

    Winnie

    Листопад 12, 2011 at 18:12

    • *EqB> donut “123456789012345678901”
      “1234 5678 9012 3456 7890 1”
      *EqB> donut “12345678901234567890”
      “1234 5678 9012 3456 7890”
      прогалину в кінці враховано

      Winnie

      Листопад 12, 2011 at 18:13

    • собачий вордпрес зїв всі інденти

      donut s = donut’ (-1) s
      ..where donut’ _ [] = []
      …………donut’ 3 (x:sx) = ‘ ‘ : x : donut’ 0 sx
      …………donut’ i (x:sx) = x : donut’ (i+1) sx

      Winnie

      Листопад 12, 2011 at 18:21

  4. Вирішив продовжити гарну тенденцію постійного скорочення сніпета:

    def spaced_blocks(s):
        return re.sub('(.{4})', r'\1 ', s)
    

    bunyk

    Листопад 13, 2011 at 00:53

    • Правда тут є зовнішня залежність, але раз ми вже працюємо з рядками, то import re все одно доведеться рано чи пізно зробити🙂.

      bunyk

      Листопад 13, 2011 at 00:58

    • Ну, і ще дідівський метод:

      #include <stdio.h>
      #include <malloc.h>
      
      char * spaced_blocks(char *str, int len)
      {
      	int newlen = len + len / 4;
      	char *res = (char *) malloc(sizeof(char) * newlen);
      	int i;
      	int j=0;
      	for (i = 0; i < len; i++)
      	{
      		res[j] = str[i];
      		j++;
      		if(i % 4 == 3)
      		{
      			res[j] = ' ';
      			j++;
      		}
      	}
      	return res;
      }
      
      int main(void)
      {
      	char *str = "asdfasasdfafd";
      	printf("'%s'\n", spaced_blocks(str, 13));
          	return 0;
      }
      

      Хех. Писати на C після Python-на не так вже й важко як здається. Трохи незвично, але можливо. Крім того, коли знаєш що тут кожен байт в твоїх руках, це навіть мотивує.

      Треба буде якусь пітонівську бібліотечку написати, лиш не можу придумати яку мені треба було б…

      bunyk

      Листопад 13, 2011 at 01:19

      • Ах, тут ще бракує завершаючих нулів. Дивно що printf нічого на це не сказала. Там варто забрати параметр len, обчислити його вручну порахувавши кількість символів до нульового, і не забути виділити пам’ять для нульового символа в результаті, і додати його в кінець результату.

        Ну знав, що з першого разу правильні програми на C не виходять!

        bunyk

        Листопад 13, 2011 at 01:25

        • «вручну» — #include >string.h< і strlen()
          І виділяти пам’ять прямо всередині фунції тут трохи моветон. В ідеалі це функція — це автомат над потоком, яка видає результат у інший потік (див. мій варіант нижче, хоч він і не по-юніксовськи хачний, я намагався скоротити розмір коду).

          dmytrish

          Листопад 14, 2011 at 20:13

  5. #include 
    using namespace std;
    
    // k - step, must be > 0
    // s - source string, s.size() must be > 0
    string add_spaces(string s, int k) {
      int z=s.size();
      string r(z+(z-1)/k,' ');
      for(z=0;s[z];)
        r[z+z/k]=s[z++];
      return r;
    }
    
    int main() {
      string test = "";
      for (int i = 1; i < 12; ++i) {
        test += (char)'0' + (i%10);
        for (int j = 1; j < 5; ++j) {
          cout << test << " spaced by " << j << ": " << add_spaces(test, j) << "!" << endl;
        }
      }
      return 0;
    }
    
    

    ps. давно на сишке не писал

    jtimv

    Листопад 13, 2011 at 01:38

  6. Clojure

    (defn split [s]
      (->> s
           (partition 4)
           (interpose " ")
           flatten
           join))
    

    alexyakushev

    Листопад 13, 2011 at 02:26

    • Можна без аргументів, на одних higher-order:

      (def split
        (comp join flatten
              (partial interpose " ") (partial partition 4)))
      

      alexyakushev

      Листопад 13, 2011 at 02:38

      • Ouch!

        user=> (def split2 (comp join flatten (partial interpose " ") (partial partition 4)))
        #'user/split2
        user=> (split2 "xxxxyyyyz")
        "xxxx yyyy"
        user=> (split2 "xxxxyyyyzz")
        "xxxx yyyy"
        user=> (split2 "xxxxyyyyzzzz")
        "xxxx yyyy zzzz"
        

        А я вже майже вирішив, що Lisp це круто…

        danbst

        Листопад 14, 2011 at 19:57

        • Винен, треба було перевірити перед тим, як писати.

          В стандартній бібліотеці немає функції, яка б розбивала послідовності по принципу, вказаному в умові. Написати свій велосипед не складніше, ніж в ваших пайтонах:

          (defn split2 [t]
            (->> (for [c [(count t)] i (range 0 c 4)]
                   (.substring t i (min (+ i 4) c)))
                 (interpose " ") join))
          

          >> А я вже майже вирішив, що Lisp це круто…
          Твій когнітивний апарат мене вражає:)

          alexyakushev

          Листопад 14, 2011 at 20:57

        • Вніс рішення у пост. А на мій когнітивний апарат гнати не треба, не-не-не девід блейн.

          danbst

          Листопад 14, 2011 at 22:13

        • Ага! Я двічі лошара. Є можливість, просто треба уважніше документацію читати.
          Короче, міняй рішення на оце:

          (def split2
            (comp join flatten
                  (partial interpose " ")
                  (partial partition 4 4 nil)))
          

          alexyakushev

          Листопад 14, 2011 at 22:30

        • Додав. Тепер згоден – Lisp це круто. Хоча не стільки Lisp, скільки стандартна бібліотека Clojure

          danbst

          Листопад 14, 2011 at 23:22

        • Лісп це теж круто, просто його крутість в цій задачі не проявляється.
          А в даному випадку роль зіграв The Clojure Way (ну і бібліотека, написана відповідно до нього), яка стимулює працювати зі всім як з послідовностями і операціями над ними (замість рекурсії чи ітерації).

          alexyakushev

          Листопад 14, 2011 at 23:40

    • Найкоротше, що я зміг народити на Common Lisp:
      (defun spacify (s) (if (> 4 (length s)) s (concatenate ‘string (subseq s 0 4) ” ” (spacify (subseq s 4)))))
      цей падлючний subseq замість нормально проковтнути позицію, неприсутню в рядку, викидає condition, в результаті не уникнути перевірки на довжину, яка коле око.

      dmytrish

      Листопад 14, 2011 at 21:04

      • А по моєму, все правильно робить. На недопустимих аргументах краще викидати ексепшени, ніж провокувати subtle errors.
        Рішення коротке, але рекурсивне.

        alexyakushev

        Листопад 14, 2011 at 21:21

      • майже правильно. Залишає прогалик, коли довжина кратна 4. На жаль я погано знайомий з функціями ліспу, тому не зміг виправити ситуацію сам. Допоможете?

        danbst

        Листопад 14, 2011 at 22:22

        • Тут помилка не в Ліспі )
          (defun spacify (s) (if (> 5 (length s)) s (concatenate ‘string (subseq s 0 n) ” ” (spacify (subseq s)))))
          Хотів зробити варіант для будь-якого n (не тільки 4), але код би тоді ще трохи розпухнув, хай буде так.

          dmytrish

          Листопад 14, 2011 at 23:37

        • Як код вставляти тут?

          dmytrish

          Листопад 14, 2011 at 23:44

        • 2 варіанти – через тег <pre> або через BB-тег
          [ sourcecode language=”lisp” ]

          [ /sourcecode ]

          danbst

          Листопад 15, 2011 at 00:00

        • остаточний варіант:

          (defun spacify (s) (if (> 5 (length s)) s (concatenate 'string (subseq s 0 4) " " (spacify (subseq s 4)))))
          

          Повидаляйте хтось сліди моєї боротьби із Вордпресом)

          dmytrish

          Листопад 15, 2011 at 00:02

        • Ок, вніс в пост. До варіантів на С/C++ приступлю завтра, ймовірно…

          danbst

          Листопад 15, 2011 at 00:20

  7. jtimv

    Листопад 13, 2011 at 03:10

  8. s.replace(/(….)/g,”$1 “)

    Чувак, юзающий регекспы

    Листопад 13, 2011 at 13:38

    • Так оно будет практически в любом языке выглядеть. На Lua, например:
      f:gsub(“….”,”%1 “))
      Только оно оставляет пробел в конце, и его приходится убирать дополнительным тримом или сабстрингом. Что добавляет информационного мусора действие. Мое предыдущее решение лишено этого недостатка.

      alexyakushev

      Листопад 13, 2011 at 13:51

      • s.replace(/(….)(?!$)/g,”$1 “)

        Чувак, юзающий регекспы

        Листопад 13, 2011 at 13:57

        • +1
          Дорош, це не ти часом?

          P.S. Dan, включи оцінки в коментарях.

          bunyk

          Листопад 13, 2011 at 14:51

        • Магия, но ок.

          alexyakushev

          Листопад 13, 2011 at 15:45

        • я

          Чувак, юзающий регекспы

          Листопад 13, 2011 at 16:48

        • чувак, ти крут. Вніс до посту, разом з модифікованим варіантом Буника.

          danbst

          Листопад 15, 2011 at 00:00

        • >>>P.S. Dan, включи оцінки в коментарях.
          та ну, хай краще пости спамлять – буде графік відвідуваності рости =)

          danbst

          Листопад 15, 2011 at 00:23

  9. Мій сішний варіант:

    #include >stdio.h<

    void gap_after_fourcc(const char *in, char *out) {
    while (*out++ = *in++)
    if (!((long long)in % 4))
    *out++ = ‘ ‘;
    *out = ”;
    }

    #define BUF_SIZE 0x100

    int main(int argc, char **argv) {
    char buf[BUF_SIZE];
    char outbuf[BUF_SIZE];

    scanf(“%s”, buf);
    gap_after_fourcc(buf, outbuf);
    printf(“%s\n”, outbuf);
    }

    dmytrish

    Листопад 14, 2011 at 18:45

    • Тобто

      #include ;
      
      void gap_after_fourcc(const char *in, char *out) {
          while (*out++ = *in++)
              if (!((long long)in % 4))
                  *out++ = ' ';
          *out = '';
      }
      
      #define BUF_SIZE    0x100
      
      int main(int argc, char **argv) {
          char buf[BUF_SIZE];
          char outbuf[BUF_SIZE];
      
          scanf("%s", buf);
          gap_after_fourcc(buf, outbuf);
          printf("%s\n", outbuf);
      }
      

      dmytrish

      Листопад 14, 2011 at 18:46

      • Або, для повної unix-way-ності,

        #include <stdio.h>
        int main() {
            for (int c = -1, i = 0 ;;) {
                if (EOF == (c = getchar())) return 0;
                printf((i++ % 4) ? "%c" : "%c ", c);
            }
        }
        

        dmytrish

        Листопад 14, 2011 at 19:04

        • не катить, я не вказав у темі, але мав на увазі що потрібна саме чиста функція. Варіанти вище в стадії перевірки…

          danbst

          Листопад 14, 2011 at 22:29

        • Якщо потрібна чиста функція, то gap_after_fourcс() , можливо, і не чиста у функціональному розумінні, але таки функція. Щодо другого варіанту, то його після компіляції можна вважати елементом конвеєра баша (що таки не функція, згоден).

          dmytrish

          Листопад 14, 2011 at 23:54

      • *out = ‘\’ , малось на увазі

        dmytrish

        Листопад 14, 2011 at 23:49

      • *out = ‘\0’;

        dmytrish

        Листопад 14, 2011 at 23:50

  10. Додав у пост рішення на K3.2 (інтерпретатор kona)

    danbst

    Листопад 15, 2011 at 00:02

  11. Ще одне потворне рішення на Хаскелі (діти, не робіть цього вдома!)
    spaceBy n s = unwords(map (\ s -> take n s) (takeWhile (not.null) (iterate (\s -> drop n s) s)))
    І ще у мене стійке відчуття, що на функціях вищого порядку це можна зробити куди красивіше, але що є, то є)

    Dmytro Sirenko

    Листопад 28, 2011 at 22:15

    • Додав у пост, дякую.

      danbst

      Грудень 6, 2011 at 23:44

      • чорт, лямбди були непотрібні:
        spaceBy n s = unwords ( map (take 4) (takeWhile (not.null) (iterate (drop 4) s)))

        dmytrish

        Грудень 7, 2011 at 20:46

      • не потрібні, так не потрібні =) тепер добре видно, як на хаскелі можна писати лісп-стилем =)

        danbst

        Грудень 7, 2011 at 21:04

        • Підкол про лісп-стиль защітан))

          dmytrish

          Грудень 7, 2011 at 21:06

  12. Й так, я зрозумів, що С-шний код навіть перевірити не зможу. Дуже шкода усіх, хто старався😦

    danbst

    Грудень 6, 2011 at 23:47


Залишити відповідь

Заповніть поля нижче або авторизуйтесь клікнувши по іконці

Лого WordPress.com

Ви коментуєте, використовуючи свій обліковий запис WordPress.com. Log Out / Змінити )

Twitter picture

Ви коментуєте, використовуючи свій обліковий запис Twitter. Log Out / Змінити )

Facebook photo

Ви коментуєте, використовуючи свій обліковий запис Facebook. Log Out / Змінити )

Google+ photo

Ви коментуєте, використовуючи свій обліковий запис Google+. Log Out / Змінити )

З’єднання з %s

%d блогерам подобається це: