Serial voting detection 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                      &lt;none&gt;
vwvwwvwv                      &lt;none&gt;
xyxyxyxyxyxyxyzyzyzyxzxzxz    y10z3
nanananananananabatman        a8
banana                        &lt;none&gt;
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)