Format () de Golf String inverse

13

Inversez la méthode Format.

La Formatméthode de la classe String (ou équivalente, comme sprintf) est disponible dans la plupart des langues. Il prend essentiellement une chaîne "Format" qui peut contenir des espaces réservés avec une mise en forme supplémentaire, et zéro ou plusieurs valeurs à insérer à la place de ces espaces réservés.

Votre tâche consiste à implémenter la fonction inverse dans la langue de votre choix.

API

Le nom de la méthode doit être soit format1ou deformat.

Entrée : le 1er paramètre sera la chaîne "Format", comme dans la méthode de formatage d'origine. Le deuxième paramètre sera la chaîne analysée (voir les exemples ci-dessous). Aucun autre paramètre n'est nécessaire ni autorisé.

Production : un tableau (ou l'équivalent de la langue de votre choix) de valeurs qui ont été extraites de manière correspondante avec les espaces réservés au format.

Les espaces réservés sont {0}, {1}, {2}, etc.

En cas de mauvais format, vous pouvez lancer une erreur ou retourner ce que vous voulez.

En cas d'entrée non valide, vous pouvez renvoyer une erreur ou retourner ce que vous voulez. Entrée non valide est telle que ne peut pas être généré par String.Format en utilisant même chaîne de format, par exemple: '{0}{0}', 'AAB'.

Exemples

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']

Ambiguïté

En cas d'ambiguïté, vous pouvez renvoyer toute réponse appropriée. Par exemple:

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

Quelques règles supplémentaires

  • Pour le rendre plus facile, il n'est pas nécessaire de réellement prendre en charge le formatage. Vous pouvez tout oublier sur les zéros non significatifs, les points décimaux ou les problèmes d'arrondi. Générez simplement les valeurs sous forme de chaînes.
  • Pour le rendre non trivial, les expressions régulières ne sont pas autorisées .
  • Vous n'avez pas besoin de prendre soin des accolades en entrée (c'est-à-dire que le deuxième paramètre d'entrée ne contiendra aucun {s ou }s).

Gagnant

C'est du ! (doit être lu comme "C'est Sparte!") la fonction correcte ayant la longueur la plus courte l'emporte. Les failles standard sont interdites.

Jacob
la source
Dans l'exemple deformat('{0}{1}{0}', 'ABBA') => ['A', 'BB'], que se passerait-il si on nous donnait à la place deformat('{0}{1}{0}', 'AAAA')?
xnor
@xnor - que nous avons une ambiguïté, et chacun des éléments suivants serait une sortie valide: ['', 'AAAA'], ['A', 'AA'],['AA', '']
Jacob
Aurait-on pu alors sortir deformat('{0}{1}{0}', 'ABBA') => ['', 'ABBA']? Si c'est le cas, il existe une solution bon marché à moins que chaque chaîne n'apparaisse au moins deux fois.
2014
votre solution bon marché fonctionnera-t-elle également deformat('{0}_{1}_{0}', 'A_BB_A')?
Jacob
Oh, je vois, j'avais oublié les personnages réels dans les résultats. J'essaie toujours de comprendre à quel point c'est algorithmiquement difficile. Voyons si je peux inventer une instance vraiment perverse.
xnor

Réponses:

2

Haskell, 220 caractères

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

Arrête si vous utilisez plusieurs représentations pour le même motif ( {1}vs {01}) - n'impose pas leur égalité, en rejetant les correspondances pour toutes les représentations sauf une.

19 caractères peuvent être sauvegardés en omettant mapKeys((0+).read)$si l'ordre correct des correspondances au-dessus de 10 motifs n'a pas d'importance, ou si un remplissage à la même longueur peut être requis, ou si l'ordre des chaînes de motifs est acceptable. Dans tous les cas, si un motif est omis du premier argument, il est également omis du résultat.

La suppression !!0de la fin fait format1renvoyer la liste de toutes les solutions, plutôt que juste la première.

avant de jouer au golf:

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
John Dvorak
la source
qui est là (0+)? l'écriture n'est-elle pas seulement lue plus court?
fier haskeller
@proudhaskeller readvous laisse juste un type ambigu. Haskell ne sait pas quel type commandable pour lire les clés. +0force un nombre, à partir duquel Haskell est déjà en mesure de faire un choix arbitraire et opte pour des entiers.
John Dvorak
2

Ruby, 312 caractères

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 caractères pourraient être enregistrés en préférant des correspondances de longueur nulle, ce qui rend la ABBAsolution ['', 'ABBA'], plutôt que la solution préférée de la question. J'ai choisi d'interpréter les exemples comme une partie implicite de la spécification.

Nathan Baum
la source
1

Python, 208 caractères, quoique incomplet.

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

La fonction balaye les deux chaînes simultanément, jusqu'à ce qu'elle trouve une accolade ouvrante dans la chaîne d'entrée, ce qui signifie un espace réservé.

Ensuite, il suppose que l'espace réservé a déjà été développé et essaie de faire avancer l'index de la chaîne de sortie après lui en consultant la liste des valeurs trouvées jusqu'à présent.

S'il n'a pas été développé, il ajoute une nouvelle entrée à la liste de valeurs et commence à ajouter des caractères à partir de la chaîne de sortie jusqu'à ce qu'il atteigne le caractère après l'espace réservé dans la chaîne d'entrée.

Quand il arrive à la fin de la chaîne d'entrée, il renvoie les valeurs trouvées jusqu'à présent.


Cela fonctionne bien pour les entrées simples, mais il a un certain nombre de problèmes:

  • Il nécessite un délimiteur connu après chaque espace réservé dans l'entrée, il ne fonctionne donc pas avec les espaces réservés les uns à côté des autres, c'est-à-dire "{0} {1}". C'est pourquoi j'ai dû ajouter un caractère d'espace aux deux chaînes.

  • Il suppose que les premières instances de chaque espace réservé sont en ordre, par exemple "{ 0 } { 1 } {1} {0} { 2 }".

  • Il ne fonctionne que pour les 10 premiers espaces réservés car il suppose qu'ils sont tous de 3 caractères.

  • Il ne gère pas du tout les cas ambigus :(

Sam Hubbard
la source
1

Code C ++ 11, 386 caractères

#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;}

La fonction format1 a 2 chaînes en entrée (const char *) et renvoie une table de hachage avec des clés entières (le modèle) et la valeur est la chaîne identifiée. Si rien n'est trouvé ou une erreur, une table de hachage vide est renvoyée.

Usage:

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

Production:

1=one
2=two

Exemple 2:

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

Production:

one and two

Les motifs sont en représentation décimale, les entrées plus grandes que MAXINTdéborderont mais cela fonctionne toujours.

Même s'il existe des solutions plus petites dans d'autres langages de programmation, c'est le plus petit C ++ - pour le moment! :)

Voici le code avant de jouer au golf:

#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;
}
Ovidiu Andoniu
la source