LINUX.ORG.RU

Яблоконь LOR Code Wars Championship: раскрытие фигурных скобок как в баше

 ,


0

5

Я вижу тут всем нравятся подобные темы в стиле @kompospec.

Задача: реализовать элегентное раскрытие фигурных скобок как в баше:

Условия:

  • есть некая функция expand, приниающая строку, раскрывающая фигурные скобки с вариантами, перечисленными через запятую, и возвращающая массив с результатами. Пример реализации:
def combine(a: list, b: list) -> list:
    rv = []
    for x in a:
        for y in b:
            rv.append(x + y)
    return rv


def append(lst: list[str], add: str) -> list[str]:
    return [x + add for x in lst]


def expand(s: str) -> list[str]:
    head, *parts = s.split("{")
    rv = [head]
    for part in parts:
        options, rest = part.split("}", 1)
        rv = append(combine(rv, options.split(",")), rest)
    return rv


assert expand("~/{.local/share,.config,.cache}/{foo,bar}-package") == ['~/.local/share/foo-package', '~/.local/share/bar-package', '~/.config/foo-package', '~/.config/bar-package', '~/.cache/foo-package', '~/.cache/bar-package']
  • Язык реализации может быть любой.
  • Желательно чтобы функция могла обрабатывать вложенные скобки. Можно так же добавить поддержку срезов типа {a..z} и предусмотреть экранирование символово {},.
  • Предпочтительнее декларативный стиль.

Дополнения:

Что за вложенные скобки? - А вот они:

~   
❯ echo /path/to/{foo,ba{r,z}}.txt
/path/to/foo.txt /path/to/bar.txt /path/to/baz.txt

Примеры решений

Рекурсивный вызов:

# Модифицированная версия отсюда https://algo.monster/liteproblems/1096
def parse_range(s: str) -> list[str | int]:
    range_parts = s.split("..", 1)
    is_num_range = all(x.isdigit() for x in range_parts)
    first, last = map((ord, int)[is_num_range], range_parts)
    # first, last = min(first, last), max(first, last)
    res = range(first, last + 1)
    return list(res if is_num_range else map(chr, res))


def expand(s: str) -> set[str]:
    rv = set()

    def dfs(exp: str) -> None:
        try:
            inner, after = exp.split("}", 1)
        except ValueError:
            rv.add(exp)
            return

        before, inner = inner.rsplit("{", 1)

        for item in parse_range(inner) if ".." in inner else inner.split(","):
            dfs(f"{before}{item}{after}")

    dfs(s)

    return rv

Недостаток: без set будут дублироваться элементы.

Функциональный стиль:

def expand str
  _, res, _ = str.each_char.reduce([[''], [''], []]) do |(pre, cur, acc), c|
    case c
    when '}'; [acc + cur, acc + cur, []]
    when '{'; [cur, cur, acc]
    when ','; [pre, pre, acc + cur]
    else    ; [pre, cur.map { |x| x + c }, acc]
    end
  end
  res
end

Недостаток: неправильно обрабатывает запятую на первом уровне вложенности.

★★

Последнее исправление: rtxtxtrx (всего исправлений: 5)
Ответ на: комментарий от ugoday

P.S. Основная сложность тут — придумать названия для неизменной части строки и той, что содержит перечисления в фигурных скобках. Нужна помощь, тут есть какая-то стандартная терминология?

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

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

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

Ну, не надо прибедняться. Это ж контекстнозависимый парсер. Вполне себе алгоритмическая штука. В ней духа CS ещё и поболе будет, нежели в очередном способе быстро-быстро перемножать матрицы.

ugoday ★★★★★
()

Решение на Raku. Строится полноценая грамматика и в ней учитывается всё, что я смог придумать: последовательности ({1..5}), экранирование (\{) и скобки и запятые на верхнем уровне.

sub merge($prefix, $braces, $suffix) {
  if ($braces) {
    return $braces.made X~ $suffix.made if $suffix;
    return $braces.made;
  };
  return $suffix.made.map: $prefix ~ * if $suffix;
  [ $prefix ];
};

sub range(Int:D $start, Int:D $end, Int $incr is copy = Int) {
  $incr = 1 if !$incr.defined || $incr == 0;
  $incr = -$incr if ($incr > 0) != ($end >= $start);
  $start, * + $incr ...^ ($incr > 0 ?? { $_ > $end } !! { $_ < $end });
};

grammar braces {
  token TOP {
    ^ <top-string> $
    { make $<top-string>.made }
  };

  token top-string {
    [ <braces> || <item> || (.) ] <top-string>?
    { make merge $<item> ?? $<item>.made !! $0, $<braces>, $<top-string> }
  };

  token braces {
    '{' ~ '}' [ <range> || <list> ]
    { make ($<range> // $<list>).made }
  };

  token range {
       <number> '..' <number> [ '..' <number> ]?
       { make range |$<number>.map: *.made }
    || (\w) '..' (\w) [ '..' <number> ]?
       {
         make range(
           $0.ord, $1.ord, $<number> ?? $<number>.made !! Int
         ).map: &chr
       }
  };

  token number {
    <[+-]>? \d+
    { make $/.Int }
  };

  token list {
    (<string>?)* % ','
    { make $0.flatmap: -> $m { $m<string> ?? $m<string>.made !! '' } }
  };

  token string {
    [ <braces> || <item> ] <string>?
    { make merge $<item> ?? $<item>.made !! '', $<braces>, $<string> }
  };

  token item {
    [ <-[{},\\]> || [ '\\' . ]]*
    [ '\\' $ ]?
    <?{ $/ ne '' }>
    {
      my $match = $/;
      my $item = ~$/;
      $item ~~ s:g[ '\\' (.) ] = $0;
      $match.make: $item;
    }
  };
};

sub expand(Str:D $string) {
  braces.parse($string).made;
};

sub test($string) {
  say $string;
  print "'$_' " for expand $string;
  print "\n\n";
};

test '0123';
test '{}';
test '{0,1}';
test '{0{1,2}3';
test '0{1,2{3,4},5}6';
test '0{,1,,2,}3}';
test 'a,b,{c,d},e,f';
test '{\{,\,,\}}\\';
test 'q{1..5}';
test '{a..f}e';
test 'a{b,c,{10..1..-4},{e..a}}';

Выдача:

[tmp] > raku lor.raku
0123
'0123'

{}
''

{0,1}
'0' '1'

{0{1,2}3
'{013' '{023'

0{1,2{3,4},5}6
'016' '0236' '0246' '056'

0{,1,,2,}3}
'03}' '013}' '03}' '023}' '03}'

a,b,{c,d},e,f
'a,b,c,e,f' 'a,b,d,e,f'

{\{,\,,\}}\
'{\' ',\' '}\'

q{1..5}
'q1' 'q2' 'q3' 'q4' 'q5'

{a..f}e
'ae' 'be' 'ce' 'de' 'ee' 'fe'

a{b,c,{10..1..-4},{e..a}}
'ab' 'ac' 'a10' 'a6' 'a2' 'ae' 'ad' 'ac' 'ab' 'aa'
Jini ★★
()