Bash-Style Curly Brace Expansion

a_description.md

Bash-Style Curly Brace Expansion

Expands the curly-brace notation as supported by Bash.

expand "ab{c,d}e"
  => [ "abce", "abde" ]

expand "ab{c,d}e{1,2}"
  => [ "abce1", "abce2", "abde1", "abde2" ]

expand "ab{c,d{1,2}}e"
  => [ "abce", "abd1e", "abd2e" ]

This was a rudimentary attempt to see what could be written in < 20 minutes (for an interview-length question). There are certainly faster and more elegant solutions.

I've also added three additional solutions:

• A Ruby verion using regular expressions provided by @jakswa
• A recursive accumulator method in Ruby provided by @betawaffle
• The same recursive accumulator method in Erlang using tail recursion, also provided by @betawaffle

b_elliott_expand.rb

def expand(string, expansions = [])
  pos = string.index('{')
  expansions << string and return if pos.nil?

  open_count = 1
  alternations = []
  alt_i = pos+1

  start_str = string[0..(pos-1)]
  end_str = nil
  pos = pos + 1

  while i = string.index(/[{},]/, pos)
    case string[i]
    when '{'
      open_count += 1
    when '}'
      open_count -= 1
      if open_count == 0
        alternations << string[alt_i..(i-1)]
        end_str = string[(i+1)..-1]
        break
      end
    when ','
      if open_count == 1
        alternations << string[alt_i..(i-1)]
        alt_i = i+1
      end
    end

    pos = i+1
  end

  raise "invalid matching" unless open_count == 0

  alternations.each do |alt|
    expand(start_str + alt + end_str, expansions)
  end

  expansions.sort
end

b_elliott_expand2.rb

def expand2(string, expansions = [])

  state = :starting
  start_str = ""
  end_str = ""
  alternations = []
  open_count = 0

  string.each_char do |c|
    case state
    when :starting
      if c == '{'
        open_count += 1
        alternations << ""
        state = :matching
      else
        start_str += c
      end
    when :matching
      if c == '{'
        open_count += 1
      elsif c == '}'
        open_count -= 1
        if open_count == 0
          state = :ending
        end
      elsif c == ','
        alternations << ""
      else
        alternations[alternations.length-1] += c
      end
    when :ending
      end_str += c
    end
  end

  raise "invalid matching" unless open_count == 0

  alternations.each do |alt|
    expand(start_str + alt + end_str, expansions)
  end

  expansions.sort
end

c_jake_expand.rb

def expand(s)
  result = ['']; 
  r = /([{,])([^{},]*){([^{}]+)}([^{},]*)([,}])/
  s.sub!(r) { $1 << $3.split(',').map {|i| $2<<i<<$4 }.join(",") << $5 } while s.match r #or 'while $3', I think
  s.scan(/([^{}]*){([^{}]+)}([^{}]+$)?/) {|a,b,e| 
    result = result.product(b.split(',').map {|c|  a.to_s + c + e.to_s}).collect {|x,y| x + y}
  }
  result
end

d_andy_expand.erl

expand(Bin) ->
    expand_1(Bin, [<<>>], []).

append(C, Prefixes) ->
    lists:map(fun (Prefix) ->
                      <<Prefix/binary, C>>
              end, Prefixes).

expand_1(Bin, Prefixes, Acc) ->
    expand_1(Bin, Prefixes, Prefixes, Acc).

expand_1(<<C, Rest/binary>>, Pre0, Cur0, Acc0) ->
    case expand_2(C, Pre0, Cur0, Acc0) of
        {Pre1, Acc1} ->
            expand_1(Rest, Pre1, Acc1);
        {Pre1, Cur1, Acc1} ->
            expand_1(Rest, Pre1, Cur1, Acc1)
    end;
expand_1(<<>>, _, Cur, Acc) ->
    lists:reverse(Cur, Acc).

expand_2(C, Pre, Cur, Acc) ->
    case C of
        $} -> {Cur ++ Acc, []};
        ${ -> {Cur, Cur, Acc};
        $, -> {Pre, Pre, Cur ++ Acc};
        _  -> {Pre, append(C, Cur), Acc}
    end.

d_andy_expand.rb

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

Note: d_andy_expand yields weird output when a } is missing

d_andy_expand("foo{a,b")  # => foob

Note: c_jake_expand provide empty output when there isn't any brace

c_jake_expand("{foobar") # => foobar
c_jake_expand("foobar") # => ""