Golf String's format() inverse

Question

Invert the Format method.

The Format method of the String class (or equivallent, such as sprintf) is available in most languages. It basically takes a "Format" string which may contain placeholders with some extra formatting, and zero or more values to be inserted instead of those placeholders.

Your task is to implement the inverse function in your language of choice.

API

Method name should be either format1 or deformat.

Input: 1st parameter will be the "Format" string, just like in the original format method. 2nd parameter will be the parsed string (see examples below). No other parameters are needed nor allowed.

Output: an array (or your language-of-choice's equivalent) of values that were extracted correspondingly with the placeholders in the format.

The placeholders are {0}, {1}, {2}, etc.

In case of bad format you may throw an error, or return whatever you like.

In case of invalid input, you may throw an error, or return whatever you like. Invalid input is such that cannot be generated by String.Format using same format string, for example: '{0}{0}', 'AAB'.

Examples

deformat('{0} {1}', 'hello world') => ['hello', 'world']
deformat('http{0}://', 'https://') => ['s']
deformat('http{0}://', 'http://') => [''] // array of one item which is an empty string
deformat('{0}{1}{0}', 'ABBA') => ['A', 'BB']

Ambiguity

In case of ambiguity you may return any suitable answer. For example:

deformat('{0} {1}', 'Edsger W. Dijkstra')
// both ['Edsger', 'W. Dijkstra'] and ['Edsger W.', 'Dijkstra'] are applicable.

Some More Rules

• To make it easier, there's no need to actually support formatting. You can forget all about leading zeros, decimal point or rounding issues. Just generate the values as strings.
• To make it non-trivial, Regular Expressions are not allowed.
• You don't need to take care of curly braces in input (i.e. 2nd input parameter will not contain any {s or }s).

Winning

This is code-golf! (should be read as "This is Sparta!") the correct function having shortest length wins. Standard loopholes are forbidden.

Answer 1

Haskell, 220 characters

import Data.Map;f""""=[empty]
f('{':b)d=[insert k m b|(k,('}':a))<-lex b,(m,c)<-[splitAt n d|n<-[0..length d]],b<-f a c,notMember k b||b!k==m]
f(x:b)(y:d)|x==y=f b d;f _ _=[];format1 x y=elems$mapKeys((0+).read)$f x y!!0

Breaks if you use multiple representations for the same pattern ({1} vs {01}) - doesn't enforce their equality, discarding matches for all but one representation instead.

19 characters can be saved by omiting mapKeys((0+).read)$ if proper ordering of matches above 10 patterns doesn't matter, or if padding to the same length may be required, or if string ordering of patterns is acceptable. In any case, if a pattern is omitted from the first argument, it is omitted from the result as well.

Removing !!0 from the end makes format1 return the list of all solutions, rather than just the first one.

before golfing:

import Data.Map
import Control.Monad

cuts :: [a] -> [([a],[a])]
cuts a=[splitAt n a | n <- [0..length a]]

f :: String -> String -> [Map String String]
-- empty format + empty parsed = one interpretation with no binding
f "" "" = [empty]
-- template-start format + some matched = branch search
f ('{':xs) ys = do
    let [(key, '}':xr)] = lex xs
    (match, yr) <- cuts ys
    b <- f xr yr
    guard $ notMember key b || b!key == match
    return $ insert key match b
-- non-empty format + matching parsed = exact match
f (x:xs) (y:ys) | x == y = f xs ys
-- anything else = no interpretation
f _ _ = []

deformat :: String -> String -> [String]
deformat x y = elems $ mapKeys ((0+).read) $ head $ f x y

Answer 2

Ruby, 312 characters

class String
def-@
self[0,1].tap{self[0,1]=''}end
end
def format1 f,s,r=[]
loop{if'{'==c=-f
n,f=f.split('}',2)
[*1..s.length,0].each{|i|next if'{'!=f[0]&&s[i]!=f[0]
if u=format1((g=f.gsub("{#{n}}",q=s[0,i])).dup,s[i..-1],r.dup)
r,s,f=u,s[i..-1],g
r[n.to_i]=q
break
end}else
c!=-s&&return
end
""==c&&break}
r
end

5 characters could be saved by preferring zero-length matches, making the ABBA solution ['', 'ABBA'], rather than the question's preferred solution. I chose to interpret the examples as an implied part of the specification.

Answer 3

Python, 208 chars, albeit incomplete.

def format1(i,o):
 i+=" ";o+=" ";x=y=0;s=[]
 while x<len(i):
  if i[x]=="{":
   try:y+=len(s[int(i[x+1])])
   except:
    s+=[""]
    while o[y]!=i[x+3]:s[int(i[x+1])]+=o[y];y+=1
   x+=3
  x+=1;y+=1
 return s

The function sweeps both strings simultaneously, until it finds a opening brace in the input string, signifying a placeholder.

Then, it assumes the placeholder has already been expanded, and tries to advance the index of the output string past it by looking in the list of values found so far.

If it hasn't been expanded, it adds a new entry to the list of values, and starts adding in characters from the output string until it reaches the character after the placeholder in the input string.

When it gets to the end of the input string, it returns the values found so far.

---

It works well for simple inputs, but it has a number of issues:

• It requires a known delimiter after each placeholder in the input, so it doesn't work with placeholders right next to each other i.e. "{0}{1}". This is why I needed to append a space char to both strings.

• It assumes the first instances of each placeholder are in order e.g. "{0}{1}{1}{0}{2}".

• It only works for the first 10 placeholders as it assumes they are all 3 chars long.

• It doesn't handle ambiguous cases at all :(

Answer 4

C++11 code, 386 characters

#include <string>
#include <map>
using namespace std;using _=map<int,string>;using X=const char;_ format1(X*p,X*s,_ k=_()){_ r;while(*p!='{'){if(!*p||!*s){return*p==*s?k:r;}if(*p++!=*s++)return r;}int v=0;while(*++p!='}'){v=v*10+(*p-48);}p++;if(k.find(v)!=k.end()){return format1((k[v]+p).c_str(),s,k);}while((r=format1(p,s,k)).empty()){k[v]+=*s++;if(!*s){return*p==*s?k:r;}}return r;}

The format1 function have 2 strings as input (const char*) and returns an hashmap with keys integer (the pattern) and value is the identified string. If nothing is found or any error, an empty hashmap is returned.

Usage:

for (auto v : format1("{1} {2}", "one two")){
    cout << v.first << "=" << v.second << endl;
}

Output:

1=one
2=two

Example 2:

auto v = format1("{1} {2}", "one two");
cout << v[1] << " and " << v[2] << endl;

Output:

one and two

The patterns are in decimal representation, inputs bigger than MAXINT will overflow but it still works.

Even though there are smaller solutions in other programming languages, this is the smallest C++ - yet! :)

This is the code before golfing:

#include <string>
#include <map>
using namespace std;

using res = map<int,string>;

res format1(const char* p, const char* s, res k=res()){
    res r; // intermediate result, empty until the end
    // match until first '{'
    while (*p != '{'){
        if (!*p || !*s){
            // exit case
            return ((*p == *s) ? k : r); // == 0
        }
        if (*p++ != *s++)
               return r;
    }

    // *p == '{'
    int v = 0;
    while(*++p != '}'){
        v = v*10 + (*p - '0');
    }
    p++; // advance past '}'

    // match back-references
    if (k.find(v) != k.end()){
       return format1((k[v]+p).c_str(), s, k);
    }

    // recursive search
    while ( (r=format1(p, s, k)).empty() ){
        k[v] += *s++;
        if (!*s){
            return *p == *s ? k : r;
        }
    }
    return r;
}