O Stack Exchange detecta automaticamente a votação em série (quando um usuário faz um voto positivo ou negativo em muitas das postagens de outro usuário) e o inverte. Neste desafio, você implementará um detector "voto em série" muito, muito simples.

Entrada

A entrada é uma sequência que representa uma lista de votos. Cada grupo de dois caracteres representa um voto - o primeiro é o eleitor e o segundo é o usuário que está sendo votado. Por exemplo, a seguinte entrada

ababbccd

pode ser analisado como ab ab bc cde representa avotar bduas vezes, bvotar cuma vez e cvotar duma vez.

A entrada será composta apenas por letras minúsculas e será sempre igual> 0. Você também não pode votar em si mesmo (portanto, não aaou hh).

Resultado

Para os propósitos deste desafio, a votação em série é definida como qualquer usuário que esteja votando em outro usuário três ou mais vezes.

A saída é quantos votos devem ser revertidos para cada usuário (ou seja, quantos votos em cada usuário foram revertidos, não quantos votos que eles deram foram revertidos), no formato [user][votes][user2][votes2].... Por exemplo, uma entrada de abababab( avotação bquatro vezes) deve ser gerada b4(quatro votos foram revertidos de apara b).

A saída pode estar na ordem que você desejar, mas tanto a entrada quanto a saída devem ser cadeias simples, conforme descrito acima.

Casos de teste

In                            Out
---------------------------------------------------------------------------
abababcbcbcbcbbababa          b7a3
edfdgdhdfgfgfgih              g3
jkkjjkkjjkkjljljljmlmlnmnmnm  j6k3m3
opqrstuv                      <none>
vwvwwvwv                      <none>
xyxyxyxyxyxyxyzyzyzyxzxzxz    y10z3
nanananananananabatman        a8
banana                        <none>

Pitão, 22 bytes

pM_srSsfttTtMM.gkcz2 8

Experimente on-line: Demonstration or Test Suite

Explicação:

pM_srSsfttTtMM.gkcz2 8
                 cz2     chop the input into pairs
              .gk        group these pairs by their value
           tMM           discard the first char in each pair in each group
       fttT              discard all groups, that contain less than three pairs
      s                  concatenate all groups to get a list of chars
     S                   sort all chars
    r                8   run-length-encoding
   s                     concatenate all (count,char) pairs 
  _                      reverse the order
pM                       print each element without separator

Exemplo:

input:   ededgdhdfgfgfgihed
chop:    ['ed', 'ed', 'gd', 'hd', 'fg', 'fg', 'fg', 'ih', 'ed']
group:   [['ed', 'ed', 'ed'], ['fg', 'fg', 'fg'], ['gd'], ['hd'], ['ih']]
discard: [['d', 'd', 'd'], ['g', 'g', 'g'], ['d'], ['d'], ['h']]
discard: [['d', 'd', 'd'], ['g', 'g', 'g']]
concat.: ['d', 'd', 'd', 'g', 'g', 'g']
sort:    ['d', 'd', 'd', 'g', 'g', 'g']
rle:     [[3, 'd'], [3, 'g']]
concat.: [3, 'd', 3, 'g']
reverse: ['g', 3, 'd', 3]
print:   g3d3

Ilegível , 1830 1796 1791 1771 1762 1745 1736 1727 1626 1606 1577 bytes

A saída está em ordem alfabética inversa ( zpara a), mas de acordo com suas regras que parecem ser permitidas.

'"" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "'" "'" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "'" "'" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" ""'""' "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" " '""' "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" " "" '""' "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" """ "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "'" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" '""' "" "" "" '"" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" ""'" "'" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" '""' "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" " "" '""' "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" """ "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" " '"" "'" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" '""' "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "'""' "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "'" "'" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" '""' "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" " """ '""' "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" '""' "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" '"" "" "" "'" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" """" "" '""' "" '"" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" '""' "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "'""' "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "'" "'" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" '"" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" """ '"" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" " "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "'" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" ""'"" "'" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" " "'" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" """ '""' "" "" "'" "" "" "" "" "" "" """" '""' "" "" "'" "" "" "" "" "" "" ""

Explicação

Primeiro, para ter uma impressão do que o ilegível pode fazer, aqui está sua operação básica:

• Você tem uma fita infinita de células inteiras de tamanho arbitrário
• Você não tem um ponteiro de memória como no Brainfuck; em vez disso, você desrefere as células pela localização na fita. Isso significa que você pode "ler o valor # 4" ou "ler o valor # (ler o valor # 4)" (desreferência dupla).
• Você pode apenas ler ou gravar células de memória (não diretamente incrementadas / diminuídas como no Brainfuck).
• Você pode aumentar / diminuir os valores dentro de uma expressão. Assim, para incrementar uma célula de memória que você tem que ler , incremento , gravação , ou diferentemente colocar: write(x, inc(read(x))).
• Existem loops while e condicionais ternários que podem apenas verificar zero vs. diferente de zero.

Este programa usa a fita da seguinte maneira. Os nomes das variáveis ​​serão usados ​​no pseudocódigo posteriormente abaixo. Além disso, isso documenta a primeira versão (que era de 1830 bytes); veja as edições na parte inferior do que mudou desde então.

• Célula 0: variávelq
• A célula 1: variáveis a, p,ch
• Célula 2: variáveis hash,v
• Célula 3: variáveis b,r
• Célula 4: variáveis aa,l
• Célula 5: permanece 0 para marcar o "final" da sequência de dígitos decimais
• Células 6–95: armazena a sequência de dígitos decimais ao contrário
• Células 96–121: armazena o número de votos a serem deduzidos dos usuários a(96) a z(121) (o código ASCII da letra menos um).
• Células 4657-7380: lembre-se de quais combinações de eleitor / eleitor foram encontradas quantas vezes. Essas células têm apenas 4 valores possíveis: 0= ainda não visto, -1= visto uma vez, -2= visto duas vezes, -3= visto qualquer número de vezes mais que 2.

O algoritmo essencialmente procede da seguinte maneira:

• Continue lendo pares de caracteres ae b. Calcule o valor do hash (a-2)*(a-1)+b-1, que é exclusivo para cada combinação de letras a – z.
• Verifique a célula de memória com esse valor de hash ( *hash). Se for -3, o usuário já está qualificado para a remoção de votos, então aumente *(b-1). Caso contrário, diminua *hash. Se for agora -3 , o usuário acabou de se qualificar para a remoção de votos após três ocorrências, então aumente *(b-1)em 3.
• Depois disso, repasse os caracteres na ordem inversa ( zpara a) e produza os que precisam de dedução de votos. Isso requer divisão inteira manual por 10 para converter o número em dígitos decimais.

Com tudo isso esclarecido, é assim que o programa se parece com pseudocódigo:

// Read pairs of characters
while (a = read) + 1 {
    b = read

    // Calculate hash = (a-1)*(a-2)/2 + b-1
    // This also sets a = b-1
    hash = 0
    while --a {
        aa = a
        while --aa {
            ++hash
        }
    }
    while --b {
        ++a
        ++hash
    }

    // If this combination has just been seen for the third time,
    // increment *a by 3; if more than third time, increment *a by 1
    *a = (*hash + 3) ? ((--*hash) + 3 ? *a : (*a+3)) : (*a+1)
}

// Loop through the characters z to a
l = 27
while --l {                     // l loops from 26 to 1 (not 0)
    (v = *(ch = l + 95)) ? {    // 'a' is ASCII 97, but cell 96
        print (ch+1)            // print the votee

        // Now we need to turn the number v into decimal.
        // p points to where we are storing decimal digits.
        p = 5

        while v {
            // Integer division by 10 (q=quotient, r=remainder)
            r = (q = 0)
            while v {
                --v
                (++r - 10) ? 1 : {
                    r = 0
                    ++q
                }
            }
            // Store digit ASCII character
            *(++p) = r + 48     // 48 = '0'
            v = q
        }

        // Now output all the digit ASCII characters in reverse order
        while *p {
            print *(--p + 1)
        }

    } : 1
}

Edit 1, 1830 → 1796: Percebi que posso reutilizar o valor de retorno de um loop while em um só lugar.

Edit 2, 1796 → 1791: Acontece que o programa é um pouco menor se, em vez de usar as células 6–95, eu armazenar os dígitos decimais nas células com números negativos (–1 em diante). Como um bônus adicional, o programa não está mais limitado a 10 votos!

Edit 3, 1791 → 1771: Em vez de atribuir o resultado de *(ch = l + 95)a v, agora o atribuo a ele qe depois movo a atribuição v = qpara a condição while, levando o código para 1777 bytes. Em seguida, troque o local de qe vna fita, porque qagora é 1 mais comum que v.

Edit 4, 1771 → 1762: Duh. Inicializar hashpara 1 em vez de 0 é 9 bytes mais curto. O código hash agora é mais 1, o que não importa.

Edit 5, 1762 → 1745: Se eu inicializar qe rpara 1 em vez de 0, tenho que espalhar alguns -1s em alguns lugares para torná-lo correto e tudo parece cancelar - exceto que o while v { --v; [...] }loop agora precisa executar uma iteração a menos, o que posso fazer dizendo while --v { [...] }, que é 26 caracteres menor.

Edit 6, 1745 → 1736: Em vez de { r = 1; ++q }, podemos escrever q = *((r = 1)+1)+1. Isso se baseia no fato de qestar no slot variável nº 2. Se estivesse no slot 1, isso seria ainda mais curto, mas o programa inteiro seria mais longo no geral.

Edit 7, 1745 → 1727: Reverse Edit 6 e, em vez disso, conseguiu salvar salvando o loop while mais interno na expressão que calcula o código ASCII do dígito, que também termina em 1736 bytes ... mas salvou uma instrução de decremento (9 bytes ) alterando ((++r) - 11) ? r :para (r - 10) ? ++r :.

Edit 8, 1727 → 1626: Retrabalhou o cálculo de hash. Agora ele usa um loop while a menos. Agora, as localizações das células estão com seus códigos ASCII reais (não são mais 1 desativadas). Reorganizou as variáveis ​​para diferentes locais na fita porque agora elas ocorrem com diferentes frequências.

Edite 9, 1626 → 1606: Inlining mais louco. O corpo do primeiro loop while agora se parece com isso:

// b = next char
*(b = (hash = read)) = {

    // hash = b + (a-1)*(a-2)/2
    while (a2 = --a) {
        while --a2 {
            ++hash
        }
    }

    // If this combination has just been seen for the third time,
    // increment *b by 3; if more than third time, increment *b by 1
    (*hash + 3) ? ((--*hash) + 3 ? *b : (*b+3)) : (*b+1)
}

e a atribuição de variáveis ​​agora mudou quase completamente.

Editar 10, 1606 → 1577: Eu observei que ae a2são ambos decrementado a 0 enquanto em laços, de modo que se podia emparelhar pcom qualquer um daqueles, mas não com ch, não seria necessário para inicializar pa 0(que custa 29 bytes). Acontece que eu posso fazer isso trocando pe r. As mais recentes atribuições de variáveis ​​(e sua frequência de ocorrência no código) são agora:

0 = v (3)                    (total  3)
1 = hash (6), r (5), ch (2)  (total 13)
2 = b (4), q (5)             (total  9)
3 = a (3), p (5)             (total  8)
4 = a2 (3), l (4)            (total  7)

CJam, 23 bytes

Festa de longa duração!

q2/$e`{3a>},e~Wf=$e`Wf%

ou

qW%2/$e`{3a>},e~:ce`Wf%

Execute todos os casos de teste

Explicação

q2/   e# Read input and split into pairs.
$e`   e# Sort and run-length encode - this tallies the pairs.
{     e# Filter the tallies...
  3a> e#   Keep only those which start with a 3 or greater.
},    e# Now we need to group the remaining pairs.
e~    e# Run-length decode the remaining pairs.
Wf=   e# Select the second character from each pair (the one being voted on).
$e`   e# Tally the characters by sorting and RLE'ing again.
Wf%   e# Reverse each pair, because CJam's RLE has the number first and the character last.

A outra versão começa revertendo os pares, o que economiza dois bytes em outro lugar: a) selecionar o primeiro caractere em cada string é apenas em :cvez de Wf=selecionar o segundo. b) Não precisamos ordenar novamente antes do segundo RLE, porque os pares já foram classificados principalmente pelo caractere restante.

Bash, 95 94 85 81 bytes

fold -2|sort|uniq -c|awk '$1>2{c[substr($2,2)]+=$1}END{for(x in c)printf x c[x]}'

Uma solução elegante e longa, mas longa, para começar ...

Graças à User112638726 para salvar um byte com sed, DigitalTrauma para salvar 9 com fold, e Rainer P. para salvar 4 mais com awk's substr!

Para ver como funciona, vamos pegar a entrada abababcbcbcbcbbababa.

• Depois fold -2(enrole a linha com uma largura de 2), temos

  ab
  ab
  cb
  cb
  cb
  cb
  ba
  ba
  ba
  

• Depois sort | uniq -c( -cé um sinalizador muito bacana para uniqgerar a contagem de quantas vezes cada linha aparece na entrada), obtemos

        3 ab
        3 ba
        4 cb
  

• Agora vamos examinar o awkcomando final :

  • $1>2: Somente produza material se o registro 1 (também conhecido como número de votos idênticos) for maior que 2 (ou seja, ≥ 3). Em outras palavras, ignore qualquer linha que comece com um número ≤ 2.

  • {c[substr($2,2)]+=$1}: Se o número for maior que 2, adicione esse número à ctabela de hash, usando o segundo caractere do registro 2 (também conhecido como voto-ee) como chave. (Não precisamos inicializar tudo para zero; awkfaz isso por nós.)

  • END{...}: Isso significa apenas "depois de processar o arquivo inteiro, eis o que fazer a seguir".

  • for(x in c)printf x c[x]: Bastante auto-explicativo. Imprima todas as chaves e seu valor correspondente.

JavaScript, 114 113 110

f=s=>eval('o={},s.replace(/../g,m=>s.search(`^((..)*${m}){3}`)?0:o[c=m[1]]=~~o[c]+1);r="";for(v in o)r+=v+o[v]');

Casos de teste:

f=s=>eval('o={},s.replace(/../g,m=>s.search(`^((..)*${m}){3}`)?0:o[c=m[1]]=~~o[c]+1);r="";for(v in o)r+=v+o[v]');
document.body.innerHTML = [["abababcbcbcbcbbababa","b7a3"],
["edfdgdhdfgfgfgih","g3"],
["jkkjjkkjjkkjljljljmlmlnmnmnm","j6k3m3"],
["opqrstuv",""],
["vwvwwvwv",""],
["xyxyxyxyxyxyxyxyzyzyzyxzxzxz","y11z3"],
["nanananananananabatman","a8"],
["banana",""]].every(v=>(f(v[0])=="" && v[1]=="") || [...new Set(f(v[0]).match(/../g))].every(p=>new Set(v[1].match(/../g)).has(p)))

Em um nível alto, esse código preenche um objeto com pares de valores-chave que mapeiam os destinatários do voto para o número de votos, como { b:7, a:3 }e os une a uma sequência em um forloop. O código está em uma evalexpressão para permitir o uso de foruma função de seta sem precisar gastar bytes em { }e ;return r.

( Adota o user81655 para salvar três bytes!)

Explicação do evalcódigo:

o={},                             // object to hold name/vote mapping
s.replace(/../g,                  // for each pair of chars in input
  m=>s.search(`^((..)*${m}){3}`)  // see if pair appears 3 times
                                  //   (0 if true, -1 if not)
     ?0                           // if not, do nothing
     :o[c=m[1]]=~~o[c]+1          // if yes, increment the property named after
                                  //   the second character in the pair
);
r="";                       // return string
for(v in o)r+=v+o[v]        // populate string with characters and vote totals

Haskell, 103 bytes

import Data.Lists
f s|c<-chunksOf 2 s,b<-[e!!1|e<-c,countElem e c>2]=nub b>>= \q->q:show(countElem q b)

Exemplo de uso: f "jkkjjkkjjkkjljljljmlmlnmnmnm"->"k3j6m3"

Como funciona:

c<-chunksOf 2 s                      -- split the input into lists of 2 elements
b<-[e!!1|e<-c,countElem e c>2]       -- for every element e of that list take the 2nd
                                     -- char if there are more than 2 copies of e
nub b>>= \q->q:show(countElem q b)   -- take every uniq element thereof and append
                                     -- the number how often it appears 

JavaScript (ES6), 195 174 169 167 158 bytes

s=v=>eval("a={},b={},e='';(v.match(/../g)).forEach(c=>{a[c]=(a[c]||0)+1});for(var k in a){d=k[1];a[k]>2&&(b[d]=(b[d]||0)+a[k])};for(var k in b){e+=k+b[k]};e")

Teste

s=v=>eval("a={},b={},e='';(v.match(/../g)).forEach(c=>{a[c]=(a[c]||0)+1});for(var k in a){d=k[1];a[k]>2&&(b[d]=(b[d]||0)+a[k])};for(var k in b){e+=k+b[k]};e")

<input type="text" id="input" value="abababcbcbcbcbbababa" />
<button onclick="result.textContent=s(input.value)">Go</button>
<pre id="result"></pre>

Mathematica, 110 100 99 bytes

g=Cases[Tr@#,#2,All]&;""<>g[g[BlockMap[$,Characters@#,2],i_*_/;i>2]/.$->Last,i_*x_:>x<>ToString@i]&

Perl, 86 84 83 bytes

s/../$h{$&}++/eg;@l=%l=map{/./;$h{$_}>2?($',${$'}+=$h{$_}):()}keys%h;$"="";$_="@l"

São 82 bytes mais 1 para o -pargumento da linha de comando:

$ echo xyxyxyxyxyxyxyxyzyzyzyxzxzxz | perl -p 86.pl
y11z3

s/../$h{$&}++/eg;     # construct hash %h with pair counts

@l = %l = map         # assign to array via hash to filter dupes
{                     
  /./;                # match the first character

  $h{$_}>2?           # filter on 3 or more identical votes
  (                   # return a 2 element list (k/v pair for %l):
    $',               # $POSTMATCH: the 2nd character (votee)
    ${$'} += $h{$_}   # increment votee total votes, value is new total
  )
  :()
}
keys %h;              # iterate the unique pairs

$" = "";              # set $LIST_SEPARATOR to empty string
$_ = "@l"             # implicit join using $";  $_ gets printed with -p

• update 84 Salve 2 bytes, incorporando o grep
• atualização 83 Economize 1 byte usando vars temporários globais em ${$'}vez de $g{$'}. Infelizmente, $$'não funciona.

Pure Bash, 151

Mais do que eu esperava, mas aqui está.

declare -A a n
for((;v<${#1};v+=2));{((a[${1:v:2}]++));}
for u in ${!a[@]};{((a[$u]>2))&&((n[${u:1}]+=a[$u]));}
for u in ${!n[@]};{ printf $u${n[$u]};}

Usa a indexação de matriz associativa para fazer a contagem necessária. Requer bash versão 4.0 ou superior.

PHP 247 caracteres

(ai)

$f='';for($i=0;$i<strlen($s);$i=$i+2){$a[]=$s[$i].$s[$i+1];}$r=[];for($i=0;$i<count($a);$i++){$t=array_count_values($a);$c=$t[$a[$i]];if($c>=3){$r[$a[$i][1]][$a[$i][0]]=$c;}}for($i=0;$i<count($r);$i++){$f.=key($r).array_sum(current($r));next($r);}

Explicado

// Test Case
$s = 'nanananananananabatman';

// Final result here
$f = '';

// Seperate strings into array in 2 character chunks
for ($i = 0; $i < strlen($s); $i = $i + 2)
{
    $a[] = $s[$i] . $s[$i + 1];
}

// Make an array of data
// The first level of array has voted on user as key
// Inside of that array is a dictionary with the voter user as the key, and the number of votes as the value
$r = [];
for ($i = 0; $i < count($a); $i++)
{
    $t = array_count_values($a);
    $c = $t[$a[$i]];
    if ($c >= 3)
    {
        $r[$a[$i][1]][$a[$i][0]] = $c;
    }
}

// Combine votes from different users to the same user into the final result string
for ($i = 0; $i < count($r); $i++)
{
    $f .= key($r) . array_sum(current($r));
    next($r);
}

echo $f;

Fez isso sem espreitar outras respostas. Este é o código de golfe mais difícil que eu já enfrentei. Congratulo-me com todas as otimizações.

R, 221 bytes

código

f=function(s){t=strsplit(gsub("(.{2})","\\1 ", s)," ")[[1]];z=table(t)[table(t)>2];n=substr(names(z),2,2);x=data.frame(y=z,t=n);a=aggregate(x$y,by=list(x$t),sum);for(i in nrow(a):1)cat(as.character(a[i,1]),a[i,2],sep="")}

destroçado

f <- function(s){
  l <- gsub("(.{2})", "\\1 ", s)
  t <- strsplit(l," ")[[1]]
  z <- table(t)[table(t)>2]
  n <- substr(names(z),2,2)
  x <- data.frame(y=z,t=n)
  a <- aggregate(x$y, by=list(x$t),sum)
  for(i in nrow(a):1){
    cat(as.character(a[i,1]),a[i,2],sep="")
  }
}

Há muito espaço para melhorias aqui.