Stack Exchange detecta automáticamente el voto en serie (cuando un usuario vota a favor o en contra de muchas de las publicaciones de otro usuario) y lo revierte. En este desafío, implementará un detector de "voto en serie" muy, muy simple.

Entrada

La entrada es una cadena que representa una lista de votos. Cada grupo de dos personajes representa un voto: el primero es el votante y el segundo es el usuario que se vota. Por ejemplo, la siguiente entrada

ababbccd

se puede analizar como ab ab bc cdy representa avotar bdos veces, bvotar cuna vez y cvotar duna vez.

La entrada consistirá solo en letras minúsculas, y siempre será una longitud par> 0. Tampoco puedes votar por ti mismo (así que no aao hh).

Salida

Para los propósitos de este desafío, la votación en serie se define como cualquier usuario dado que vota sobre cualquier otro usuario tres o más veces.

El resultado es cuántos votos se deben invertir para cada usuario (es decir, cuántos votos se invirtieron en cada usuario, no cuántos votos se han invertido), en el formato [user][votes][user2][votes2].... Por ejemplo, una entrada de abababab( avotar bcuatro veces) debería producirse b4(se han invertido cuatro votos de aa b).

La salida puede estar en el orden que desee, pero tanto la entrada como la salida deben ser cadenas simples como se describió anteriormente.

Casos de prueba

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

Pyth, 22 bytes

pM_srSsfttTtMM.gkcz2 8

Pruébelo en línea: Demostración o conjunto de pruebas

Explicación:

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

Ejemplo:

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

Ilegible , 1830 1796 1791 1771 1762 1745 1736 1727 1626 1606 1577 bytes

La salida está en orden alfabético inverso ( za a) pero de acuerdo con sus reglas, eso parece ser permisible.

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

Explicación

Primero, para tener una idea de lo que Unreadable puede hacer, aquí está su operación básica:

• Tienes una cinta infinita de celdas enteras de tamaño arbitrario
• Usted no tiene un puntero de memoria como en Brainfuck; en su lugar, desreferencia las celdas por su ubicación en la cinta. Esto significa que puede "leer el valor n. ° 4" o "leer el valor n. ° (leer el valor n. ° 4)" (doble desreferencia).
• Solo puede leer o escribir celdas de memoria (no aumentar / disminuir directamente como en Brainfuck).
• Puede aumentar / disminuir valores dentro de una expresión. Por lo tanto, para incrementar una celda de memoria que tiene que leer , de la subasta , escritura , o diferente puesto: write(x, inc(read(x))).
• Hay bucles while y condicionales ternarios que solo pueden verificar cero frente a no cero.

Este programa usa la cinta de la siguiente manera. Los nombres de las variables se usarán en el pseudocódigo más adelante. Además, esto documenta la primera versión (que tenía 1830 bytes); vea las ediciones en la parte inferior para ver qué ha cambiado desde entonces.

• Celda 0: variableq
• Cell 1: las variables a, p,ch
• Celda 2: variables hash,v
• Celda 3: variables b,r
• Celda 4: variables aa,l
• Celda 5: sigue siendo 0 para marcar el "final" de la cadena de dígitos decimales
• Celdas 6–95: almacena la cadena de dígitos decimales hacia atrás
• Celdas 96–121: almacene el número de votos que se deducirán de los usuarios a(96) a z(121) (el código ASCII de la carta menos uno).
• Celdas 4657–7380: recuerde qué combinaciones de votante / votante se han encontrado cuántas veces. Estas celdas tienen solo 4 valores posibles: 0= aún no visto, -1= visto una vez, -2= visto dos veces, -3= visto cualquier número de veces más de 2.

El algoritmo esencialmente procede de la siguiente manera:

• Sigue leyendo pares de caracteres ay b. Calcule el valor hash (a-2)*(a-1)+b-1, que es único para cada combinación de letras a – z.
• Verifique la celda de memoria en ese valor hash ( *hash). Si es así -3, el usuario ya es elegible para la eliminación de votos, así que incremente *(b-1). De lo contrario, decremento *hash. Si es ahora -3 , el usuario acaba de ser elegible para la eliminación de votos después de tres ocurrencias, así que incremente *(b-1)en 3.
• Después de esto, revise los caracteres en orden inverso ( za a) y muestre los que necesitan votos deducidos. Esto requiere la división de enteros manual por 10 para traducir el número a dígitos decimales.

Con todo eso aclarado, así es como se ve el programa como 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
}

Edición 1, 1830 → 1796: Me di cuenta de que puedo reutilizar el valor de retorno de un ciclo while en un solo lugar.

Edición 2, 1796 → 1791: Resulta que el programa es un poco más pequeño si, en lugar de usar las celdas 6–95, guardo los dígitos decimales en las celdas con números negativos (–1 en adelante). ¡Como un bono adicional, el programa ya no se limita a 10⁹⁰ votos!

Edición 3, 1791 → 1771: en lugar de asignar el resultado de *(ch = l + 95)to v, ahora lo asigno a qy luego muevo la asignación v = qa la condición while, llevando el código a 1777 bytes. Luego intercambie la ubicación de qy ven la cinta porque qahora es 1 más común que v.

Edición 4, 1771 → 1762: Duh. Inicializar hasha 1 en lugar de 0 es 9 bytes más corto. El código hash ahora es 1 más, lo que no importa.

Edición 5, 1762 → 1745: si inicializo qy ren 1 en lugar de 0, tengo que esparcir algunos -1s en lugares para hacerlo bien, y todo parece cancelarse, excepto que el while v { --v; [...] }ciclo ahora necesita ejecutar una iteración menos, lo que puedo hacer diciendo while --v { [...] }, que es 26 caracteres más corto.

Edición 6, 1745 → 1736: en lugar de { r = 1; ++q }, podemos escribir q = *((r = 1)+1)+1. Esto se basa en el hecho de que qestá en la ranura variable # 2. Si estuviera en la ranura # 1, esto sería aún más corto, pero entonces todo el programa sería más largo en general.

Edición 7, 1745 → 1727: se revirtió la Edición 6 y, en su lugar, se logró guardar al incluir el bucle while más interno en la expresión que calcula el código ASCII de dígitos, que también termina en 1736 bytes ... pero luego guardó una instrucción de disminución (9 bytes ) cambiando ((++r) - 11) ? r :a (r - 10) ? ++r :.

Edición 8, 1727 → 1626: Se modificó el cálculo del hash. Ahora usa un bucle while menos. Las ubicaciones de las celdas ahora están en sus códigos ASCII reales (ya no están apagados en 1). Reorganizar las variables a diferentes ubicaciones en la cinta porque ahora se producen con diferente frecuencia.

Edición 9, 1626 → 1606: más loco en línea. El cuerpo del primer bucle while ahora se ve así:

// 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)
}

y la asignación variable ahora ha cambiado casi por completo.

Editar 10, 1606 → 1577: He observado que ay a2son ambos decrementa a 0 en los bucles while, por lo que si podría emparejarse pcon cualquiera de ellos, pero no con ch, no necesitaría para inicializar pa 0(que cuesta 29 bytes). Resulta que puedo hacer eso intercambiando py r. Las nuevas asignaciones de variables (y su frecuencia de aparición en el código) son ahora:

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

¡Fiesta de corrida!

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

o

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

Ejecute todos los casos de prueba

Explicación

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.

La otra versión comienza invirtiendo los pares, lo que ahorra dos bytes en otro lugar: a) seleccionar el primer carácter en cada cadena es solo en :clugar de Wf=seleccionar el segundo. b) No necesitamos ordenar nuevamente antes del segundo RLE, porque los pares ya estaban ordenados principalmente por el carácter 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]}'

Una primera solución elegante pero larga para comenzar ...

¡Gracias a User112638726 por guardar un byte con sed, DigitalTrauma por guardar 9 con fold, y Rainer P. por guardar 4 más con awk's substr!

Para ver cómo funciona, tomemos la entrada abababcbcbcbcbbababa.

• Después fold -2(ajuste la línea a un ancho de 2), tenemos

  ab
  ab
  cb
  cb
  cb
  cb
  ba
  ba
  ba
  

• Después sort | uniq -c( -ces un indicador muy ingenioso uniqque genera el recuento de cuántas veces aparece cada línea en la entrada), obtenemos

        3 ab
        3 ba
        4 cb
  

• Ahora examinemos el awkcomando final :

  • $1>2: Solo genera material si el registro 1 (también conocido como el número de votos idénticos) es mayor que 2 (es decir, ≥ 3). En otras palabras, ignore cualquier línea que comience con un número ≤ 2.

  • {c[substr($2,2)]+=$1}: Si el número es mayor que 2, agregue ese número a la ctabla hash, utilizando el segundo carácter del registro 2 (también conocido como vote-ee) como clave. (No tenemos que inicializar todo a cero; lo awkhace por nosotros).

  • END{...}: Esto solo significa "después de procesar todo el archivo, esto es lo que debe hacer a continuación".

  • for(x in c)printf x c[x]: Bastante autoexplicativo. Imprima cada clave y su valor correspondiente.

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 prueba:

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)))

En un nivel alto, este código llena un objeto con pares clave-valor que asignan los destinatarios del voto al número de votos, como { b:7, a:3 }y luego los une en una cadena en un forbucle. El código está en una evalexpresión para permitir el uso fordentro de una función de flecha sin necesidad de gastar bytes en { }y ;return r.

(¡Apoyos para user81655 para guardar tres bytes!)

Explicación del 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)

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

Cómo 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")

Prueba

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"

Eso es 82 bytes más 1 para el -pargumento de la línea de comandos:

$ 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

• actualización 84 Ahorre 2 bytes alineando el grep
• actualización 83 Ahorre 1 byte utilizando vars temporales globales en ${$'}lugar de $g{$'}. Lamentablemente, $$'no funciona.

Pure Bash, 151

Más de lo que esperaba, pero aquí 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]};}

Utiliza la indexación de matriz asociativa para hacer el recuento necesario. Requiere bash versión 4.0 o superior.

PHP 247 caracteres

(Ay)

$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;

Hice esto sin mirar otras respuestas. Este es el código de golf más difícil que he abordado hasta ahora. Agradezco todas las optimizaciones.

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="")}

sin golf

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="")
  }
}

Aquí hay mucho margen de mejora.