Serial voting detection

Question

Stack Exchange automagically detects serial voting (when one user either upvotes or downvotes many of another user's posts) and reverses it. In this challenge, you will implement a very, very simple "serial vote" detector.

Input

The input is a string representing a list of votes. Every group of two characters represents a vote—the first one is the voter, and the second is the user being voted on. For example, the following input

ababbccd

can be parsed as ab ab bc cd, and represents a voting on b twice, b voting on c once, and c voting on d once.

The input will consist of only lowercase letters, and it will always be an even length > 0. You also can't vote on yourself (so no aa or hh).

Output

For the purposes of this challenge, serial voting is defined as any given user voting on any other user three or more times.

The output is how many votes should be reversed for each user (that is, how many votes on each user were reversed, not how many votes that they have given were reversed), in the format [user][votes][user2][votes2].... For example, an input of abababab (a voting on b four times) should output b4 (four votes have been reversed from a to b).

The output may be in any order you would like, but both the input and output must be single strings as described above.

Test cases

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

Answer 1

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

The output is in reverse alphabetical order (z to a) but according to your rules that appears to be permissible.

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

Explanation

First, to get an impression of what Unreadable can do, here is its basic operation:

• You have an infinite tape of arbitrary-size integer cells
• You do not have a memory pointer like in Brainfuck; instead, you dereference cells by their location on the tape. This means you can “read value #4” or “read value #(read value #4)” (double-dereference).
• You can only read or write memory cells (not directly increment/decrement like in Brainfuck).
• You can increment/decrement values within an expression. Thus, to increment a memory cell you have to read, increment, write, or differently put: write(x, inc(read(x))).
• There are while loops and ternary conditionals that can only check for zero vs. non-zero.

This program uses the tape as follows. The variable names will be used in the pseudocode later below. Also, this documents the first version (which was 1830 bytes); see the edits at the bottom for what’s changed since.

• Cell 0: variable q
• Cell 1: variables a, p, ch
• Cell 2: variables hash, v
• Cell 3: variables b, r
• Cell 4: variables aa, l
• Cell 5: remains 0 to mark the “end” of the string of decimal digits
• Cells 6–95: store the string of decimal digits backwards
• Cells 96–121: store the number of votes to be deducted from users a (96) to z (121) (the letter’s ASCII code minus one).
• Cells 4657–7380: remember which voter/votee combinations have been encountered how many times. These cells have only 4 possible values: 0 = not seen yet, -1 = seen once, -2 = seen twice, -3 = seen any number of times more than 2.

The algorithm essentially proceeds as follows:

• Keep reading pairs of characters a and b. Calculate the hash value (a-2)*(a-1)+b-1, which is unique for every combination of letters a–z.
• Check the memory cell at that hash value (*hash). If it’s -3, the user is already eligible for vote removal, so increment *(b-1). Otherwise, decrement *hash. If it’s now -3, the user has just become eligible for vote removal after three occurrences, so increment *(b-1) by 3.
• After this, go through the characters in reverse order (z to a) and output the ones that need votes deducted. This requires manual integer division by 10 to translate the number into decimal digits.

With all that clarified, this is what the program looks like as pseudocode:

// 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: Realized that I can re-use the return value of a while loop in one place.

Edit 2, 1796 → 1791: Turns out the program is slightly smaller if, instead of using the cells 6–95, I store the decimal digits in the negative-numbered cells (–1 onwards). As an added bonus, the program is no longer limited to 10⁹⁰ votes!

Edit 3, 1791 → 1771: Instead of assigning the result of *(ch = l + 95) to v, I now assign it to q and then move the assignment v = q into the while condition, taking the code to 1777 bytes. Then swap the location of q and v on the tape because q is now 1 more common than v.

Edit 4, 1771 → 1762: Duh. Initializing hash to 1 instead of 0 is 9 bytes shorter. The hash code is now 1 more, which doesn’t matter.

Edit 5, 1762 → 1745: If I initialize q and r to 1 instead of 0, I have to sprinkle some -1s in places to make it right, and it all seems to cancel out — except that the while v { --v; [...] } loop now needs to execute one fewer iteration, which I can do by saying while --v { [...] }, which is 26 characters shorter.

Edit 6, 1745 → 1736: Instead of { r = 1; ++q }, we can write q = *((r = 1)+1)+1. This relies on the fact that q is in variable slot #2. If it were in slot #1 this would be even shorter, but then the entire program would be longer overall.

Edit 7, 1745 → 1727: Reverted Edit 6 and instead achieved the saving by inlining the innermost while loop into the expression that calculates the digit ASCII code, which also ends up at 1736 bytes... but then saved a decrement instruction (9 bytes) by changing ((++r) - 11) ? r : to (r - 10) ? ++r :.

Edit 8, 1727 → 1626: Reworked the hash calculation. It now uses one fewer while loop. Cell locations are now at their actual ASCII codes (not off by 1 anymore). Reshuffled variables to different locations on the tape because they now occur with different frequency.

Edit 9, 1626 → 1606: More crazy inlining. The body of the first while loop now looks something like this:

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

and the variable assignment has now almost completely changed.

Edit 10, 1606 → 1577: I observed that a and a2 are both decremented to 0 in while loops, so if I could pair p with either of those, but not with ch, I wouldn’t need to initialize p to 0 (which costs 29 bytes). Turns out I can do that by swapping p and r. The newest variable assigments (and their frequency of occurrence in the code) are now:

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)

Answer 2

CJam, 23 bytes

Run-length party!

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

or

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

Run all test cases

Explanation

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.

The other version starts by reversing the pairs, which saves two bytes elsewhere: a) selecting the first character in each string is only :c instead of Wf= for selecting the second. b) We don't need to sort again before the second RLE, because the pairs were already sorted primarily by the remaining character.

Answer 3

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

An elegant-ish but long first solution to start off...

Thanks to User112638726 for saving a byte with sed, DigitalTrauma for saving 9 with fold, and Rainer P. for saving 4 more with awk's substr!

To see how it works, let's take the input abababcbcbcbcbbababa.

• After fold -2 (wrap the line to a width of 2), we have

  ab
  ab
  cb
  cb
  cb
  cb
  ba
  ba
  ba
  

• After sort | uniq -c (-c is a very nifty flag to uniq that outputs the count of how many times each line appears in the input), we get

        3 ab
        3 ba
        4 cb
  

• Now let's examine the final awk command:

  • $1>2: Only output stuff if record 1 (aka the number of identical votes) is greater than 2 (that is, ≥ 3). In other words, ignore any line that starts with a number ≤ 2.

  • {c[substr($2,2)]+=$1}: If the number is greater than 2, add that number to the c hash table, using the second char of record 2 (aka the vote-ee) as the key. (We don't have to initialize everything to zero; awk does that for us.)

  • END{...}: This just means "after processing the entire file, here's what to do next."

  • for(x in c)printf x c[x]: Fairly self-explanatory. Print every key and its corresponding value.

Answer 4

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

Test cases:

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

At a high level, this code populates an object with key-value pairs that map vote recipients to number of votes, like { b:7, a:3 } and then joins them into a string in a for loop. The code is in an eval expression to allow the use of for within an arrow function without needing spend bytes on { } and ;return r.

(Props to user81655 for saving three bytes!)

Explanation of eval code:

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

Answer 5

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

Test

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>

Answer 6

Pyth, 22 bytes

pM_srSsfttTtMM.gkcz2 8

Try it online: Demonstration or Test Suite

Explanation:

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

Example:

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

Answer 7

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)

Usage example: f "jkkjjkkjjkkjljljljmlmlnmnmnm" -> "k3j6m3"

How it works:

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 

Answer 8

Mathematica, 110 100 99 bytes

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

Answer 9

Pure Bash, 151

Longer than I'd hoped, but here it is.

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

Uses associative array indexing to do the necessary counting. Requires bash version 4.0 or greater.

Answer 10

Perl, 86 84 83 bytes

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

That's 82 bytes plus 1 for the -p commandline argument:

$ echo xyxyxyxyxyxyxyxyzyzyzyxzxzxz | perl -p 86.pl
y11z3

---

Somewhat ungolfed:

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 Save 2 bytes by inlining the grep
• update 83 Save 1 byte by using global temporary vars ${$'} instead of $g{$'}. Unfortunately, $$' doesn't work.

Answer 11

PHP 247 Characters

(ouch)

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

Explained

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

Did this without peeking at other answers. This is the most difficult code golf I've tackled yet. I welcome all optimizations.

Answer 12

05AB1E --no-lazy, 13 bytes

2ô.γθ}εgyθθì?

Try it online!

Or 14 bytes flagless:

2ô.γθ}εgyθθì}J

Try it online!

Explanation

2ô              # Split into pairs
  .γ            # Group by:
    θ}          #  Last item
      ε         # Map:
       g        #  Push length
        y       #  Push the list again
         θθ     #  Last item of last item
           ì    #  Prepend to length

                # (--no-lazy flag version)
            ?   #  Print without newline
                # --no-lazy flag makes sure that
                # the printing gets done correctly

                # (Flagless version)
            }   # Close the map
             J  # And join into a string
                # Implicit output

Answer 13

Thunno J, \$ 24 \log_{256}(96) \approx \$ 19.75 bytes

2Ap.rz:zGAJzHeDAJAJsLZPJ

Attempt This Online!

Explanation

2Ap            # Split into pairs
   .rz:        # Reverse each and sort
       zGAJzH  # Group by first item
eD             # Map:
  AJAJ         #  Push first item of first item
      sL       #  Swap and push length
        ZPJ    #  Pair and join
               # J flag joins the resulting list
               # Implicit output

Answer 14

Python, 143 bytes

lambda s:''.join((z:=[*l])[0][-1]+f'{len(z)}'for _,l in groupby(g(s),lambda a:a[-1]))
g=lambda x:[*x]and[x[:2]]+g(x[2:])
from itertools import*

Attempt This Online!

Answer 15

R, 221 bytes

code

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

ungolfed

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

There is a lot of room for improvement here.

Answer 16

Vyxal s, 11 bytes

2ẇ⁽tġƛLnttp

Try it Online!

12 bytes flagless

now this looks like a job for me

Explained

2ẇ⁽tġƛLnttp
2ẇ           # Wrap into pairs
  ⁽tġ        # group by last character
     ƛ       # to each group:
      L      #   get the length
       nttp  #   and make a http request to see what the answer should be
             #   obviously that's not what happens because n isn't the letter h
       ntt   #   get the last character of the pair this group represents
          p  #   prepend that to the length
# s flag sums the list, joining it on nothing.