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

Пост для тренування мізків. Дозволяється використовувати будь-яку мову. Дозволяється висловлювати свою думку на рахунок чужого коду (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 F#, F# example, F# slice, F# small tasks, python

56 Responses

Subscribe to comments with RSS.

Якщо без рекурсії то ітерацією:
```
>>> 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
Мне сразу подумалось такое:
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

Відповідь
- Вставив в пост, лишнє урізав.
  
  danbst
  
  Листопад 9, 2011 at 18:37
  
  Відповідь
Ось мій варіант (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
  
  Відповідь
  - спробуй тег <pre>
    bunyk
    
    Листопад 12, 2011 at 18:52
    
    Відповідь
  - Вніс у пост, дякую
    
    danbst
    
    Листопад 14, 2011 at 23:20
    
    Відповідь
Вирішив продовжити гарну тенденцію постійного скорочення сніпета:
```
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

#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

Відповідь

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
ВНЕЗАПНО http://www.0chan.ru/c/res/210620.html

jtimv

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

Відповідь
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
Мій сішний варіант:

#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 0×100

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
    
    Відповідь
Додав у пост рішення на K3.2 (інтерпретатор kona)

danbst

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

Відповідь
Ще одне потворне рішення на Хаскелі (діти, не робіть цього вдома!)
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
Й так, я зрозумів, що С-шний код навіть перевірити не зможу. Дуже шкода усіх, хто старався

danbst

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

Відповідь

Напишіть відгук Cancel reply

Enter your comment here...

Fill in your details below or click an icon to log in:

Email (обов`язково) (Address never made public)

Ім`я (обов`язково)

Сайт

You are commenting using your WordPress.com account. ( Log Out / Змінити )

You are commenting using your Twitter account. ( Log Out / Змінити )

You are commenting using your Facebook account. ( Log Out / Змінити )

Скасувати

Connecting to %s

	intracer on Хороше і погане
	intracer on Хороше і погане
	danbst on Хороше і погане
	ulidtko on Хороше і погане
	ulidtko on Хороше і погане
	danbst on Хороше і погане

UProLa