O matcher FizzBuzz-ish String

25

Digamos que você tenha uma string como esta:

abaabbbbbaabba

Conte o número de vezes que um caractere especificado aparece na sequência de entrada, mas apenas se o caractere aparecer apenas uma vez em uma linha . Por exemplo, se o personagem for a,

abaabbbbbaabba
^ x      x   ^

O total seria 2 (os aanão contariam porque o aaparece duas vezes seguidas).

Como isso está relacionado ao FizzBuzz?

Se o personagem aparecer 3 (ou múltiplos de 3) vezes seguidas ou 5 (ou múltiplos de 5) vezes seguidas, o contador será diminuído . Se for um múltiplo de 3 e 5 vezes, o contador ainda será incrementado. Lembre-se de que o contador também será incrementado se o personagem aparecer apenas uma vez em uma linha e será ignorado se o personagem aparecer outro número de vezes em uma linha (além das situações descritas acima).

Para recapitular, se a sequência a corresponder for a,

input            counter (explanation)

a                 1 (single occurence)
aaa               -1(multiple of 3)
aaaaa             -1(multiple of 5)  
aaaaaaaaaaaaaaa   1 (multiple of 15)
aa                0 (none of the above)

aba               2 (two single instances)
aaba              1 (one single occurence(+1) and one double occurence(ignored))
aaaba             0 (one single occurence(+1) and one triple (-1)
aaaaaa            -1 (six is a multiple of three)

Implementação de referência (ungolfed) em java:

import java.util.Scanner;
import java.util.regex.*;

public class StrMatcher {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in); //Scanner to get user input
        int total = 0;//Running total of matches

        System.out.println("Enter a string: ");
        String strBeingSearched = sc.nextLine(); //String that will be searched

        System.out.println("Enter string to match with: ");
        String strBeingMatched = sc.nextLine(); //Substring used for searching

        //Simple regex matcher
        Pattern pattern = Pattern.compile("(" + strBeingMatched + ")+");
        Matcher matcher = pattern.matcher(strBeingSearched);

        while(matcher.find()){  //While there are still matches

            int length = matcher.end() - matcher.start();
            int numberOfTimes = length/strBeingMatched.length();//Calculate how many times in a row the string is matched

            if((numberOfTimes == 1)||((numberOfTimes % 3 == 0) && (numberOfTimes % 5 == 0))){
                total++; //Increment counter if single match or divisible by 15
            } else if((numberOfTimes % 3 == 0)||(numberOfTimes % 5 == 0)) {
                total--; //Decrement counter if divisible by 3 or 5 (but not 15)
            }

            strBeingSearched = strBeingSearched.substring(matcher.end());
            matcher = pattern.matcher(strBeingSearched); //Replace string/matcher and repeat
        }

        System.out.println(total);
    }   
}
  • A sequência que será pesquisada pode ter qualquer comprimento, mas o padrão será apenas um caractere.
  • Nenhuma string terá caracteres especiais de regex.
  • Isso é ; o programa mais curto em bytes vence.
  • Sem brechas padrão.
Daniel M.
fonte
3
Seria útil se você pudesse fornecer mais alguns exemplos de teste. Especialmente aqueles em que a sequência tem mais de uma letra.
Reto Koradi 21/09/2015
Adicionei alguns casos - espero que ajude. Diga-me se eu precisar de mais casos - é a minha primeira vez no PPCG.
Daniel M.
Vou mudar os requisitos para que a sequência seja apenas um caractere, pois a implementação é praticamente a mesma, mas menos confusa.
Daniel M.
É como a pergunta 1 esparsa, mas com a adição do FizzBuzz
ev3commander

Respostas:

32

Função , 1840 bytes

Porra, essa linguagem é inviável.

Este programa espera que o primeiro caractere da entrada seja o caractere a ser pesquisado e o restante da entrada para criar a sequência a ser pesquisada. Isso significa que aaabaprocurará ana entrada aaba(e, portanto, na saída 1). Você pode separá-los com uma nova linha ou espaço ( a aaba), mas apenas porque a nova linha / espaço extra não faz diferença na saída.

Como sempre, você pode obter uma renderização mais agradável (sem o espaçamento entre linhas) se executar $('pre').css('line-height',1)no console do navegador.

      ┌───┐
      │╓─╖└─────────────┐
      └╢³╟┐    ┌─────┐ ┌┴┐╓─╖
┌─────┐╙─╜└────┤┌─╖ ┌┴╖│┌┘║¹║
│     ├───────┐└┤²╟─┤·╟┘│ ╙┬╜╔═══════╗
│    ┌┴╖╔═╗┌─╖├┐╘╤╝ ╘╤╝┌┘  └┬╢2097151║
│    │♭║║5╟┤%╟┘└─┴──┐│┌┘┌───┘╚═══════╝
│    ╘╤╝╚═╝╘╤╝╔═╗┌─╖│││┌┴┐┌────┐
│    ┌┴╖   ┌┘ ║3╟┤%╟┘││└┬┘│╔══╗└┐
│  ┌─┤·╟─┐ │  ╚═╝╘╤╝ │└┐  │║21╟┐│
│  │ ╘╤╝ ├─┘┌─────┘  └┐└┐ │╚══╝│└─┐
│ ┌┴╖┌┴╖┌┴╖┌┴╖┌─╖    ┌┴╖│ │┌─╖┌┴─╖│
│┌┤·╟┤?╟┤?╟┤?╟┤+╟────┤³║│ └┤²╟┤>>║└──┐
││╘╤╝╘╤╝╘╤╝╘╤╝╘╤╝    ╘╤╝│  ╘╤╝╘╤═╝╓─╖│
││ │ ┌┴╖┌┴╖┌┴╖┌┴╖╔═╗ ┌┴╖│  ┌┴╖ ├──╢²╟┤
││ └─┤·╟┤·╟┤?╟┤·╟╢1║┌┤·╟┘  │♯║┌┴╖ ╙─╜│
│└──┐╘╤╝╘╤╝╘╤╝╘╤╝╚═╝│╘╤╝   ╘╤╝│¹║┌───┘
└──┐│╔╧╗ └┬─┘ ┌┴╖   │┌┴─╖   │ ╘╤╝│
   ││║1║ ┌┴┐┌─┤?╟───┴┤>>╟┐ ┌┴╖┌┴╖│
   ││╚═╝ └┬┘│ ╘╤╝    ╘══╝│┌┤?╟┤=║│
   │└────┐│╔╧╗     ┌─────┘│╘╤╝╘╤╝│
╔═╗└────┐│├╢0║╔══╗┌┴╖┌─╖ ╔╧╗   └─┘
║ ║     │└┘╚═╝║21╟┤×╟┤♯╟┐║0║
╚╤╝     └──┐  ╚══╝╘═╝╘═╝│╚═╝
 │┌──┴────╖└────────────┘
 ││int→str║
 │╘══╤════╝
┌┴─╖┌┴╖┌─╖╔╗
│>>╟┤³╟┤¹╟╢║
╘═╤╝╘═╝╘═╝╚╝
╔═╧╗
║21║
╚══╝

(1840 bytes quando codificado como UTF-16.)

Explicação

  • ¹ retorna o primeiro caractere de uma sequência.
  • ²conta o número de ocorrências de um caractere no início de uma determinada sequência. Por exemplo, dado o caractere ae a string aaba, ele retorna 2. Para ae baa, ele retorna 0.
  • ³chama ²para obter o número de caracteres no início, examina se o número é divisível por 3 e 5 e se é igual a 1 e determina o incremento / decremento adequado. Ele também remove um caractere extra do início da string (por exemplo, dado que aaabbaele remove 3 + 1 = 4 caracteres, fornecendo ba). Em seguida, ele se chama recursivamente com a string mais curta e adiciona o resultado.
  • O programa principal chama ¹para remover o primeiro caractere da entrada e chama ³com esse caractere e o restante da string como argumentos separados.
Timwi
fonte
10
Eu nunca vou votar no Funciton.
orlp 21/09/2015
14

CJam, 40 36 35 32 30 bytes

0llcf=e`::*{(_g+Y13515Yb+=(+}/

Obrigado a @ MartinBüttner por jogar fora um byte!

Graças a @AndreaBiondo por jogar fora 2 bytes e abrir caminho para mais 3!

Experimente on-line no intérprete CJam .

Como funciona

0          e# Push a 0 (accumulator).
l          e# Read a line from STDIN.
lc         e# Read a second line and keep only the first character.
f=         e# Check each character from the first line for equality.
           e# This results in 1 for the specified character and 0 for others.
e`         e# Perform run-length encoding.
::*        e# Multiply each element by its number of repetitions.
{          e# For each remaining integer I:
  (_!      e#   Subtract 1, copy and push sign(I-1).
  +        e#   Add the results.
           e#     If I == 0, I-1 + sign(I-1) =  -1 + -1 = -2.
           e#     If I == 1, I-1 + sign(I-1) =   0 +  0 =  0.
           e#     If I >= 2, I-1 + sign(I-1) = I-1 +  1 =  I.
  Y        e#   Push 2.
  13515Yb  e#   Convert 13515 into the array of its binary digits.
  +        e#   Concatenate 2 and the array.
           e#   This pushes [2 1 1 0 1 0 0 1 1 0 0 1 0 1 1].
  =        e#   Retrieve the digit at (index I-1 + sign(I-1))%15.
           e#     If I == 0, this pushes 1.
           e#     Else, if I == 1, this pushes 2.
           e#     Else, if I%15 == 0, this pushes 2.
           e#     Else, if I%3==0 or I%5==0, this pushes 0.
           e#     Else, this pushes 1.
  (        e#   Decrement the result.
  +        e#   Add it to the accumulator.
}/         e#
Dennis
fonte
Você pode salvar outros 2 bytes com uma tabela de pesquisa codificada em base e indexação modular: llcf=e`::*0-{(_!\6563282Zb:(=}%1bé de 33 bytes.
Andrea Biondo
@AndreaBiondo Isso realmente salvou 3 bytes. Obrigado!
Dennis
7

C, 160 126 125 119 114 109 104 100 bytes

main(int q,char **z){int i=0,t=0,s=0,a=z[1][0],c;do{if((c=z[2][i])!=a){s+=(!!t)*((t==1)-!(t%3)-!(t%5)+3*!(t%15));t=0;}else{++t;}++i;}while(c);printf("%d\n",s);}

Provavelmente pode ser melhorado ... Isso recebe informações dos argumentos da linha de comando (o primeiro argumento é o padrão, o segundo é a string). Não suporta a pesquisa do padrão de caractere NULL (\ x00).

EDIT ** 126 125 119 114 109 104 100 bytes **: Depois de incorporar as sugestões de Dennis e algumas idéias adicionais (cláusula remove else, combinou o tempo em uma única instrução e usou subtração em vez de! =). Também removeu ponto e vírgula extra no loop for (que na verdade fazia parte da sugestão de Dennis). Encurtou ainda mais removendo as variáveis ​​'i' e 'a'.

t,s;main(c,z)char**z;{for(;c;t++)if((c=*z[2]++)-*z[1])s+=!!t*((t<2)-!(t%3)-!(t%5)+3*!(t%15)),t=-1;printf("%d",s);}

Removidos os operadores if e negation ('!') Abusando do operador ternário. As verificações de modularidade compactadas usando esse 'AND' bit a bit enganam um && duplo porque bitwise '&' têm um erro e colocando a comparação (t <2) dentro dos operadores ternários. Substituído !! t * (...) movendo !! t para o operador ternário, permitindo-me remover parênteses.

Cara, eu realmente quero colocá-lo abaixo da marca de 100 bytes: S

t,s;main(c,z)char**z;{for(;c;)(c=*z[2]++)-*z[1]?s+=t%15?t%3&&t%5?t<2:-1:!!t,t=0:t++;printf("%d",s);}

Soluções TENTATIVAS: Não tenho certeza se elas seriam consideradas válidas, mas posso reduzir para 93 caracteres se usar saída (s) em vez de printf ("% d", s). Mas a saída não seria visível, mas seria um código de retorno. Se a saída for realmente necessária, também posso reduzi-la para 98 bytes, mas seria necessário imprimir todos os valores intermediários de s antes da resposta final ...

Tob Ernack
fonte
3
Bem-vindo à programação de quebra-cabeças e código de golfe! Eu não testei completamente, mas i,t,s,a;main(c,z)char**z;{a=*z[1];while(c){if((c=z[2][i])!=a)s+=(!!t)*((t<2)-!(t%3)-!(t%5)+3*!(t%15)),t=0;else++t;++i;}printf("%d",s);}deve funcionar tão bem (e é 23 bytes mais curto).
Dennis
Ah, que bom transformar a cláusula if () {} em uma declaração!
Tobe Ernack
Um pouco mais bytes: Se você começar maincom for(a=*z[1];c;i++), você não precisa do {}redor do if ... else.
Dennis
4

Ruby, 111 103 96 bytes

->s,m{s.chars.chunk{|x|x}.reduce(0){|x,(c,g)|l=g.size
x+(c!=m ?0:l<2||l%15<1?1:l%3*l%5<1?-1:0)}}

Esse desafio foi feito para o Ruby's Enumerable#chunk, então eu tive que postar isso. :)

Teste on-line: http://ideone.com/pG4mAn

O código é bastante simples. Aqui está uma versão mais legível: http://ideone.com/ub3siA .

Cristian Lupascu
fonte
4

Python 3, 361, 300, 296, 263, 256, 237, 229, 188, 178 , 164 bytes.

Economizou 15 bytes graças ao vaultah do SOPython.
Economizou 9 bytes graças a Joe Kington do SOPython.
Economizou 11 bytes graças ao DSM do SOPython.

Esta é a minha primeira vez que envia uma resposta, por isso tenho certeza de que isso pode ser muito mais curto. Ele pega a cadeia de teste como a primeira resposta à entrada e o caractere de pesquisa como a segunda.

t=input()
m=input()
c=u=0
g=iter(t)
while g:
 r=next(g,0)
 if r==0:print(c);g=0
 while r==m:u+=1;r=next(g,0)
 if u:b=u%3<1;v=u%5<1;c+=((0,-1)[b|v],1)[u<2or b&v];u=0

Versão não destruída:

import sys
test = sys.argv[1]
match_char = sys.argv[2]
counter = char_counter = 0
char_generator = (c for c in test)
while char_generator:
    try:
        char = next(char_generator)
    except StopIteration:
        print(counter)
        break
    while char == match_char:
        char_counter += 1
        try:
            char = next(char_generator)
        except StopIteration:
            break
    if char_counter == 0:
        continue
    counter += 1 if char_counter == 1 or (char_counter % 3 == 0 and char_counter % 5 == 0) else -1 if char_counter % 3 == 0 or char_counter % 5 == 0 else 0
    char_counter = 0

Descobri que estava falhando em um dos casos de teste.

Morgan Thrapp
fonte
3

Haskell, 120 bytes

import Data.List
f c=sum.map(v.length).filter((==c).head).group
v 1=1
v n|n%3&&n%5=1|(n%3||n%5)=(-1)|0<1=0
x%y=x`mod`y<1

f faz o trabalho.

Leif Willerts
fonte
3

Java, 146 152 143 138 139 136 bytes

  1. Corrigido um erro.
  2. operações deslocadas, comutadas para operador bit a bit para as %3&%5verificações.
  3. i<2Comparação reduzida .
  4. Corrigido um erro (a %3&%5verificação não funciona como se pensava).
  5. Atalho de multiplicação usado como visto na resposta Ruby de @ w0lf .

Implementado como BiFunction<String, String, Integer>no Java 8, deixe-me saber se isso é necessário para ser um programa completo (ou se eu posso até soltar o java.util.regexprefixo do pacote abaixo).

A contagem de bytes acima não inclui a nova linha abaixo, que é simplesmente adicionada para fins de formatação neste site.

(a,b)->java.util.regex.Pattern.compile("[^"+b+"]").splitAsStream(a)
.mapToInt(v->v.length()).map(i->i<2?i:i%15<1?1:i%3*i%5<1?-1:0).sum();

Explicação aproximada:

  1. Aplique regex com padrão que não corresponde b, ou seja "[^"+b+"]".
  2. Obter comprimento de cada token (por exemplo "a" -> 1).
  3. Aplicar o mapeamento desejado para -1, 0e 1.
  4. sum() para obter resposta.
hjk
fonte
2

Javascript, 206 bytes

function f(n,e){var t=n.match(new RegExp(e,"g")).length,g=n.match(new RegExp(e+"{2,}","g"));return null!==g&&g.forEach(function(n){t-=n.length,n.length%15==0?t+=1:(n.length%3==0||n.length%5==0)&&(t-=1)}),t}

Expandido:

function funkyFizzb(n, c) {
    var score = n.match(new RegExp(c, "g")).length; 
    var repeatOccurence = n.match(new RegExp(c + "{2,}", "g"));

    if(repeatOccurence !== null) {
        repeatOccurence.forEach(function(v,i){
            // remove multiple occurrence counts
            score -= v.length;

            if(v.length % 15 == 0) {
                score += 1;
            }

            else if(v.length % 3 == 0 || v.length % 5 == 0) {
                score -= 1;
            }
        });
    }

    return score;
};

Explicação:

Estou usando regex para contar o total de vezes que um personagem aparece e subtraí-lo todas as vezes que apareceu em grupos. Finalmente, eu passo pelos grupos e faço o incremento / decremento do fizz buzz.

Passa nos casos de teste fornecidos na pergunta:

funkyFizzb("aaa", "a") => -1

e assim por diante

eu estou sério
fonte
Remova o new, useexec vez de matche alias length, e você deve ser bom.
Mama Fun rolo
2

Perl, 82 65 63 59 bytes

58 bytes + parâmetro de linha de comando de 1 byte

Não é particularmente curto, mas é um começo - continuará diminuindo.

$l=y///c,$i+=!($l>1&&$l%15)||-!($l%3*$l%5)for/$^I+/g;$_=$i

Supondo que -ipode ser usado para fornecer à cadeia de entrada um exemplo de uso é o seguinte:

echo "aaabaaa" | perl -pi"a" entry.pl
Jarmex
fonte
0

Pitão, 32 bytes

tão perto! Mais 2 bytes para amarrar a excelente entrada de Dennis no CJam

s.b?qYz?tN@+,0_1 1+}3PN}5PN1Zrw8

Teste on-line

Brian Tuck
fonte
0

gawk, 140

p=$2{b="[^"$1"]";for($0=2;$i-->0;){sub("^"b"*",_,p);p=substr(p,$++i=match(p,b))}for($i=length(p);$++j;)s+=$j%5?$j%3?$j<2:-1:$j%3?-1:1}$0=s""

Insira como "string de espaço de char", assim

echo "x axxbxcxdexxxfffghixxj" | awk 'p=$2{b="[^"$1"]";for($0=2;$i-->0;){sub("^"b"*",_,p);p=substr(p,$++i=match(p,b))}for($i=length(p);$++j;)s+=$j%5?$j%3?$j<2:-1:$j%3?-1:1}$0=s""'

Ungolfed

p=$2{
    #i=j=s=0                # make reusable
    b="[^"$1"]";           # pattern "not matching char"
    $0=2;                  # help starting the while loop
    while($i-->0){         # match didn't return -1; dec stack top
        sub("^"b"*",_,p);  # remove not matching chars at head of string
        $++i=match(p,b);   # push index of first occurence of not matching char
        p=substr(p,$i)     # remove matching chars from head of string
    };
    $i=length(p);          # get last value
    while($++j)            # sometimes last value on stack is 0
        s+=$j%5?$j%3?$j<2:-1:$j%3?-1:1

        # if $j%5!=0
        #   if $j%3!=0     (not divisible by 5 AND 3)
        #     s+=($j==1)   (single character)
        #   else           (divisible by 3 but not by 5)
        #     s-=1
        # else             (divisble by 5)
        #   if $j%3!=0
        #     s-=1         (divisible by 5 but not by 3)
        #   else
        #     s+=1         (divisible by 3 AND 5)

}$0=s"" # output
Cabbie407
fonte
0

Pitão, 27 bytes

sm|!JPdx,02+}3J}5JhMf}zTrw8

Suíte de teste

Insira o formulário, por exemplo:

a
aaaba

Explicação:

sm|!JPdx,02+}3J}5JhMf}zTrw8
                               z = input() (The match character)
                         w     input() (The string)
                        r 8    Run length encode
                    f}zT       Filter for the runs z is in.
                  hM           Take their lengths
 m|                            Map (d) to the logical or of
    Pd                         Find all prime factors of the current run length
   J                           Save them in J
  !                            Take the logical negation. This will be 1 if
                               d is 1, and 0 otherwise.
           +}3J                If d wasn't 1, add up 1 if 3 is in J
               }5J             and 1 if 5 is in J.
       x,02                    Then, take the index of the result in [0,2]
                               so 0 -> 0, 2 -> 1, 1 -> -1 (not found)
s                              Sum up the values for each run.
isaacg
fonte