Topologie ASCII pt 1: Puis-je compter sur vous?

28

J'ai un problème grave. J'ai des fichiers texte où je garde mes numéros très importants - tous les plus importants! Et deux et trois ..

Ces nombres étaient si importants que je ne pouvais pas les confier à ces nouveaux systèmes de nombres décimaux ou binaires. J'ai gardé chaque numéro codé en unaire, comme suit:

            +--+
            |  |
+---+  +----+  |
|   |  |       |
+---+  +-------+
   ~/two.txt

Simple et fiable: deux boucles ASCII pour le numéro 2. Malheureusement, ces choses ont tendance à s'emmêler au fil du temps et maintenant j'ai du mal à déterminer le nombre de boucles dans chaque fichier. Voici quelques exemples que j'ai élaborés à la main:

Une:

   +---+
   |   |
+--+   |
|      |
+--+   |
   |   |
   |   |
   |   |
+--+   +--+
|         |
+---------+

Trois:

+---------+
| +-----+ |
| | +-+ | |
| | | | | |
| | +-+ | |
| +-----+ |
+---------+

Quatre:

  +--------------+
  |  +--+  +--+  |
  |  |  |  |  |  |
+-|-----|-----|----+
| |  |  |  |  |  | |
| +--+  +--+  +--+ |
+------------------+

              +------------+
              |            |
        +-----+  +-----+   |
        |        |     |   |
  +-----|-----------+  |   |
  |     |  +--+  |  |  |   |
  +-+   +--|--|--+  +---------+
    |      |  +-+      |   |  |
    +------+    |      |   |  |
                +-------+  |  |
                       ||  |  |
                       |+-----+
                       |   |
                       +---+

Cinq:

+--------+  +--------+  +--------+
|        |  |        |  |        |
|     +--|-----+  +--|-----+     |
|     |  |  |  |  |  |  |  |     |
+-----|--+  +-----|--+  +--------+
      |        |  |        |
      +--------+  +--------+

Pouvez-vous m'aider à compter mes boucles?

Voici les règles:

  • Comme je stocke tout dans unaire codé ASCII, l'efficacité de l'espace est très importante pour moi. Par conséquent, c'est le golf de code. Le plus petit programme en octets gagne.
  • Les boucles sont dessinées avec les caractères +, -, |. Chaque coin de la boucle est dessiné sans ambiguïté: exactement l'un des caractères au-dessus et en dessous du + sera |, et exactement un à droite ou à gauche sera -. Deux marques + ne sont jamais adjacentes.
  • Les brins peuvent passer les uns sur les autres. Lorsque les brins se croisent, vous pourrez voir le brin "sous" immédiatement des deux côtés du brin "au-dessus".
  • Votre programme doit prendre une représentation sous forme de chaîne de la boucle (à partir de stdin ou en tant que paramètre de fonction) et produire un nombre (soit à stdout, soit comme valeur de retour).
  • Les longueurs de ligne peuvent ne pas être uniformes dans le dessin de la boucle et il peut y avoir des espaces de fin sur chaque ligne.
  • Vous pouvez supposer qu'il y a au moins une boucle dans l'entrée.

Je compte sur vous!

Matt Noonan
la source
L'un des côtés d'un «sous-volet» peut-il être un +?
feersum
@feersum: Non, les deux bords attachés au + seront toujours visibles.
Matt Noonan
1
@Martin: J'ai bien peur que non. Mon espace de stockage est vraiment très cher, donc je ne peux pas ménager tous ces espaces supplémentaires.
Matt Noonan
Je pense que vous devriez ajouter ceci ( pastebin ) comme cas de test, sauf si je manque quelque chose et que ce n'est pas une entrée valide. Il y a 6 boucles; Je ne l'ai testé qu'en ligne avec la solution SnakeEx et il en produit 12.
blutorange
1
Vous devriez peut-être explicitement interdire ou autoriser les boucles qui se croisent (par exemple pastebin.com/5RLZuULG ) Actuellement, elles sont détectées par la solution ruby, mais pas par la solution SnakeEx.
blutorange

Réponses:

19

SnakeEx - 98 octets avec Javascript, 44 sans

Cela ressemblait à un bon problème pour essayer ma langue du Défi Quinzaine sur:

m:({e<>PE}\-[|\-]*<T>\+|[|\-]*<T>)+`\+
e:\+

Le meilleur endroit pour l'essayer est mon interprète en ligne .

SnakeEx fait correspondre les motifs dans le texte en utilisant des "serpents" qui se déplacent autour des expressions rationnelles correspondant au texte. Le code se lit un peu comme une expression régulière, sauf:

  • L' <T>instruction. C'est une commande de direction qui dérive le serpent à gauche et à droite de sa direction actuelle.
  • {e<>PE}est comme un appel de sous-programme. Celui qui engendre un serpent dont la définition va ede l'avant (<> ) et avec des paramètres P(ferroutage - le serpent reproducteur suit le nouveau serpent) et E(exclusif - ne correspond à rien de ce qui a déjà été apparié). Cette vérification exclusive est la seule chose qui empêche le serpent de boucler indéfiniment.
  • Le préfixe ` à la fin indique que ce qui suit ne doit être mis en correspondance que s'il a déjà été mis en correspondance, ce que nous pouvons utiliser pour forcer la boucle à se fermer.

Parce que SnakeEx est comme regex et ne produit pas techniquement les résultats comme souhaité par lui-même, je suppose que nous devons l'envelopper dans du Javascript appelant l'interpréteur:

function e(s){return snakeEx.run('m:({e<>PE}\\-[|\\-]*<T>\\+|[|\\-]*<T>)+`\\+\ne:\\+',s,1).length}

Edit : corrigé pour fonctionner avec les cas de test supplémentaires de blutorange

BMac
la source
1
+1 J'aime vraiment ça, peut-être parce que je peux l'essayer en ligne et mettre les boucles en surbrillance. Mais vous voudrez peut-être vérifier ces deux cas de test: 1 , 2
blutorange
@blutorange Bonne prise. J'ai ajouté un correctif légèrement hacky pour les boucles auto-croisées. Je devrai penser un peu plus au cas de test 1.
BMac
C'est le plus facile à réparer, il suffit de le remplacer [^ ]par [|\-];)
blutorange
Hah, il m'a fallu beaucoup de temps pour comprendre pourquoi c'était le cas. Bon appel.
BMac
C'est génial!
Ingo Bürk
10

C # - 338 388 433 octets

Enregistré un tas d'octets en passant à un tableau à 1 dimension.

using C=System.Console;using System.Linq;class P{static void Main(){var D=C.In.ReadToEnd().Split('\n');int z,w=D.Max(m=>m.Length)+1,d,c=0;var E=D.SelectMany(l=>l.PadRight(w)).ToList();for(z=E.Count;z-->1;)if(E[z-1]==43)for(d=1,c++;E[z+=d%2<1?w*d-w:d-2]>32;)if(E[z]<44){E[z]=' ';d=d%2>0?z<w||E[z-w]<99?2:0:E[z+1]!=45?1:3;}C.WriteLine(c);}}

D'abord, il lit dans l'entrée, et le rend agréable et rectangulaire, avec une bordure "" afin que nous n'ayons pas à faire de vérification des limites sur l'horizontale (moins cher pour faire la vérification sur la verticale que pour mettre la ligne supplémentaire) . Ensuite, il regarde à travers le rectangle, donc il frappe toujours un coin inférieur droit. Quand il frappe l'un de ces derniers, il se dirige vers le haut, suivant tous les + qu'il rencontre, et les efface au fur et à mesure (avec un espace). Il cesse de suivre lorsqu'il rencontre un espace. Testé sur les cinq exemples donnés.

using C=System.Console;
using System.Linq;

class P
{
    static void Main()
    {
        // read in
        var D=C.In.ReadToEnd().Split('\n');

        int z, // z is position in E
        w=D.Max(m=>m.Length)+1, // w is width
        d, // d is direction of travel (1 == horizontal?, 2 == down/right?)
        c=0; // c is loop count

        // make all the lines the same length
        var E=D.SelectMany(l=>l.PadRight(w)).ToList(); // say no to horizontal bounds checking

        // consume +s
        for(z=E.Count;z-->1;)
            if(E[z-1]==43) // right-most lower-most +
                for(d=1,c++; // go left, increment counter
                    E[z+=d%2<1?w*d-w:d-2]>32 // move z, then check we havn't hit a space (when we do, z is basiclly z - 1)
                    ;)
                    if(E[z]<44) // +
                    {
                        E[z]=' '; // toodles

                        d=
                            d%2>0? // currently horizontal, must go vertical
                                z<w||E[z-w]<99?2 // can't go up, must go down
                                :0 // can go up, go up
                            : // currently vertical, must go horizontal
                                E[z+1]!=45?1 // can't go right, must go left
                                :3 // can go right, go right
                            ;
                    }

        // output result
        C.WriteLine(c);
    }
}
VisualMelon
la source
Sensationnel. C'est impressionnant: o
Metoniem
6

Slip , 51 41 + 2 = 43 octets

$a(`+`-[^ +]*`+(<|>)`|[^ +]*`+#(<|>))+?$A

(Maintenant mis à jour pour fonctionner avec le cas de test de @ blutorange à un coût majeur)

Puisque @BMac a utilisé SnakeEx pour ce défi, j'ai pensé essayer d'utiliser ma soumission de langage de correspondance de motifs 2D , Slip. Mais parce que Slip n'avait pas les fonctionnalités nécessaires pour résoudre ce problème, je les ai ajoutées au cours des derniers jours. En d'autres termes, cette soumission n'est pas admissible à gagner .

Courez avec le ndrapeau pour le nombre de matchs, par exemple

py -3 slip.py regex.txt input.txt n

Essayez-le en ligne .


Explication

En raison de la pléthore de nouvelles fonctionnalités dans cette soumission, c'est une bonne occasion de les présenter.

$a                Set custom anchor at current position
(
  `+`-            Match '+-'
  [^ +]*          Match any number of '|' or '-'
  `+              Match a '+'
  (<|>)           Either turn left or turn right
  `|              Match a '|'
  [^ +]*          Match any number of '|' or '-'
  `+              Match a '+'
  #               Prevent next match from moving the match pointer (doubling up on '+')
  (<|>)           Either turn left or turn right
)
+?                Do the above at least once, matching lazily
$A                Make sure we're back where we started

Slip essaie de faire correspondre à partir de chaque position et ne renvoie que des correspondances uniques. Notez que nous utilisons [^ +]- alors que l'utilisation [-|]sauverait théoriquement deux octets, non échappé -au début / fin des classes de caractères n'est pas encore implémenté dans Slip.

Sp3000
la source
1
@blutorange a threeégalement des +s qui ne sont pas un -, un |et 2 espaces, donc je suppose que ce n'est pas une erreur
Sp3000
5

Rubis 295

F=->i{l=i.lines
g={}
l.size.times{|y|i.size.times{|x|l[y][x]==?+&&g[[y,x]]=[[y,x]]}}
c=->a,b{w=g[b]+g[a];w.map{|x|g[x]=w}}
k=g.keys
k.product(k).map{|n,o|
r,p=n
s,q=o
((r==s&&p<q&&l[r][p...q]=~/^\+-[|-]*$/)||(p==q&&r<s&&l[r...s].map{|l|l[p]||c}.join=~/^\+\|[|-]*$/))&&c[n,o]}
g.values.uniq.size}

Essayez en ligne: http://ideone.com/kIKELi (j'ai ajouté un #to_aappel sur la première ligne, car ideone.com utilise Ruby 1.9.3, qui ne supporte pas #sizepour Enumerables Dans Ruby 2.1.5+ le code fonctionne OK. . )

L'approche est la suivante:

  • faire une liste de tous les + signes dans l'entrée et considérer chacun d'eux comme une forme distincte
  • trouver des lignes horizontales et verticales qui relient deux + signes et combiner leurs formes en une seule
  • à la fin, le nombre de formes distinctes correspond au résultat

Voici une version plus lisible:

def ascii_topology_count(input)
  lines = input.lines
  max_length = lines.map(&:size).max

  # hash in which the keys are corners ("+"s), represented by their [y, x] coords
  # and the values are arrays of corners, representing all corners in that group
  corner_groups = {}

  lines.size.times { |y|
    max_length.times { |x|
      if lines[y][x] == ?+
        corner_groups[[y, x]] = [[y, x]]
      end
    }
  }

  # function that combines the groups of two different corners
  # into only one group
  combine_groups =-> c1, c2 {
    g1 = corner_groups[c1]
    g2 = corner_groups[c2]

    g2 += g1
    corner_groups[c1] = g2
    g2.map{|x| corner_groups[x] = g2}
  }

  corner_groups.keys.product(corner_groups.keys).map{|c1, c2|
    y1,x1=c1
    y2,x2=c2
    if y1 == y2 && x1 < x2
      # test horizontal edge
      t = lines[y1][x1...x2]
      if t =~ /^\+-[|-]*$/
        # p "#{c1}, #{c2}, [H] #{t}"
        combine_groups[c1, c2]

      end
    end

    if x1 == x2 && y1 < y2
      # test vertical edge
      t=lines[y1...y2].map{|l|l[x1]||' '}.join

      if t =~ /^\+\|[|-]*$/
        # p "#{c1}, #{c2}, [V] #{t}"
        combine_groups[c1, c2]
      end
    end
  }

  corner_groups.values.uniq.count
end
Cristian Lupascu
la source
5

JavaScript (ES6) 190 197 202 215 235 289 570

Modifier un tableau à une dimension au lieu de 2 dimensions, taille de ligne maximale 999 caractères (mais peut être plus gratuit, par exemple 1e5 au lieu de 999)

Modifier l' extrait de code animé ajouté, voir ci-dessous

F=s=>[...s.replace(/.+/g,r=>r+Array(e-r.length),e=999)]
  .map((c,x,z,d=1,f='-',g='|')=>{
    if(c=='+')
      for(++n;z[x+=d]!='+'||([f,g,e,d]=[g,f,d,z[x-e]==g?-e:z[x+e]==g&&e],d);)
        z[x]=z[x]==g&&g
  },n=0)|n

Ungolfed premier essai

f=s=>
{
  cnt=0
  s = (1+s+1).split(/[1\n]/)

  for(;x=-1, y=s.findIndex(r=>~(x=r.indexOf('+-'))), x>=0;++cnt)
  {
    //console.log(y+' '+x+' '+s.join('\n'))
    dx = 1
    for(;dx;)
    {
      a=s[y-1],b=s[y+1],
      r=[...s[y]]
      for(r[x]=' ';(c=r[x+=dx])!='+';)
      {
        if (c=='-')
          if((a[x]||b[x])=='|')r[x]='|';
          else r[x]=' ';
      }  

      if(a[x]=='|')dy=-1;
      else if(b[x]=='|')dy=1;
      else dy=0
      r[x]=' '
      s[y]=r.join('')
      if (dy) {
        for(;y+=dy,r=[...s[y]],(c=r[x])!='+'&c!=' ';)
        {
          if (c=='|') 
            if((r[x-1]||r[x+1])=='-')r[x]='-';
            else r[x]=' ';
          s[y]=r.join('')
        }  
        if(r[x-1]=='-')dx=-1;
        else if(r[x+1]=='-')dx=1;
        else dx=0;
      }
    }  
  }
  return cnt
}

Extrait animé

Tester dans la console Firefox / FireBug

F('\
  +--------------+\n\
  |  +--+  +--+  |\n\
  |  |  |  |  |  |\n\
+-|-----|-----|----+\n\
| |  |  |  |  |  | |\n\
| +--+  +--+  +--+ |\n\
+------------------+\n\
\n\
              +------------+\n\
              |            |\n\
        +-----+  +-----+   |\n\
        |        |     |   |\n\
  +-----|-----------+  |   |\n\
  |     |  +--+  |  |  |   |\n\
  +-+   +--|--|--+  +---------+\n\
    |      |  +-+      |   |  |\n\
    +------+    |      |   |  |\n\
                +-------+  |  |\n\
                       ||  |  |\n\
                       |+-----+\n\
                       |   |\n\
                       +---+')

4

F('\
+--------+  +--------+  +--------+\n\
|        |  |        |  |        |\n\
|     +--|-----+  +--|-----+     |\n\
|     |  |  |  |  |  |  |  |     |\n\
+-----|--+  +-----|--+  +--------+\n\
      |        |  |        |\n\
      +--------+  +--------+')

5

edc65
la source
Vous économiseriez sûrement quelques octets en doublant la version golfée? Vous pouvez également créer une fonction anonyme (je pense que cela est dans les règles de codegolf)
theonlygusti
@theonlygusti la version golfée est comptée comme une seule ligne (aucune nouvelle ligne et aucun espace d'indentation ne sont comptés) .Avec une fonction anonyme, j'économise 2 octets, une économie négligeable ...
edc65
4

Rubis, 178 187 199 212 212

Meilleure version rubis, crée une fonction F. Maintenant avec des avertissements d'interprètes toujours plus délicieux.

b=->n{Q[I]=?~
d=Q[I+n]==(n>1??|:?-)?1:-1
loop{I+=d*n
b[n>1?1:N]if Q[I]==?+
Q[I]<?~?4:break}}
F=->s{N=s.size;Q=s+?\n
Q.gsub!(/^.*$/){$&.ljust N-1}
(0..N).find{!(I=Q=~/\+/)||b[1]}}

Testez-le en ligne: ideone

Fondamentalement, la fonction bdémarre à n'importe quel moment +, passe récursivement dans la boucle et définit tout +sur u. Ainsi, une boucle est supprimée à chaque bappel. La fonction Fessaie simplement la fréquence à laquelle nous devons appeler bjusqu'à ce qu'il ne reste plus de boucles.

blutorange
la source
2

Python 2 - 390

Prend une chaîne avec des sauts de ligne de stdin. C'est une méthode assez simple pour jouer au golf un peu, mais je ne suis certainement pas autant que cela pourrait être compte tenu de sa durée.

s=raw_input().split('\n');L=len
def R(x,y):
 b=p,q=x,y;u=v=f=0
 while b!=(p,q)or not f:
    p+=u;q+=v;f=u+v;c=s[q][p]
    if'+'==c:u,v=[(i,j)for i,j in{(-1,0),(1,0),(0,-1),(0,1)}-{(-u,-v)}if 0<=q+j<L(s)and 0<=p+i<L(s[q+j])and s[q+j][p+i]in['-+','|+'][j]][0];s[q]=s[q][:p]+' '+s[q][p+1:]
    if c+s[q+v][p+u]in'-|-':p+=u;q+=v
print L([R(x,y)for y in range(L(s))for x in range(L(s[y]))if'+'==s[y][x]])
KSab
la source
1

Python 2 - 346 octets

Implémenté comme une fonction cqui prend les données du fichier en entrée et renvoie le nombre de boucles.

Premièrement, la fonction décompose les données en un mappage des emplacements des éléments de boucle avec le type d'élément à cet emplacement (par exemple {(0,0): '+'}). Ensuite, il utilise deux fonctions internes mutuellement récursives. Le premier supprime un segment de boucle du mappage et décide des emplacements à vérifier pour le segment suivant. Le second vérifie le type d'élément de boucle dans les emplacements sélectionnés et, s'il est compatible avec ce qui est attendu, appelle le premier pour supprimer la section nouvellement trouvée.

e=enumerate
def c(d):
 D={(i,j):k for i,l in e(d.split('\n'))for j,k in e(l)if k in'+-|'}
 def f(r,c,R,C,t):
  if D.get((r,c),t)!=t:g(r,c)
  elif D.get((R,C),t)!=t:g(R,C)
 def g(r,c):
  t=D.pop((r,c))
  if t!='|':f(r,c-1,r,c-2,'|');f(r,c+1,r,c+2,'|')
  if t!='-':f(r-1,c,r-2,c,'-');f(r+1,c,r+2,c,'-')
 n=0
 while D:g(*D.keys()[0]);n+=1
 return n
Mac
la source