51
\$\begingroup\$

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>
\$\endgroup\$
  • 16
    \$\begingroup\$ +1 for nanananananananabatman test case. \$\endgroup\$ – nine Dec 16 '15 at 11:23

12 Answers 12

6
\$\begingroup\$

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
\$\endgroup\$
34
\$\begingroup\$

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)
\$\endgroup\$
22
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ FWIW the Q in your second answer should be q for non-test-wrapper purposes. \$\endgroup\$ – Peter Taylor Dec 15 '15 at 21:39
  • \$\begingroup\$ @PeterTaylor I do that all the time -.- \$\endgroup\$ – Martin Ender Dec 15 '15 at 21:40
  • \$\begingroup\$ I know it's a minor detail, but converting the 3 to a list for the comparison is a nice trick. I solved it just for my own entertainment, and lost a byte there because I used 0=2>. Otherwise I ended up with almost the same as your first solution, except for using ::\ instead of Wf% for the last step. \$\endgroup\$ – Reto Koradi Dec 17 '15 at 18:20
10
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ & is equivelant to \0 in sed \$\endgroup\$ – User112638726 Dec 15 '15 at 14:54
  • \$\begingroup\$ @User112638726 Didn't know that, thanks \$\endgroup\$ – Doorknob Dec 15 '15 at 14:57
  • \$\begingroup\$ Reduced it a bit sed -r 's/.(.)/\1\n/g'|awk '{a[$1]++}END{for(i in a)printf (a[i]>2)?i a[i]:y} \$\endgroup\$ – User112638726 Dec 15 '15 at 15:14
  • \$\begingroup\$ @User112638726 That fails for the input bacada, for example. \$\endgroup\$ – Doorknob Dec 15 '15 at 15:16
  • \$\begingroup\$ Oh yeah my bad! \$\endgroup\$ – User112638726 Dec 15 '15 at 15:16
8
\$\begingroup\$

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
\$\endgroup\$
6
\$\begingroup\$

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 
\$\endgroup\$
6
\$\begingroup\$

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>

\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to PPCG :) We have some tips for golfing in JS here and here. I don't know JS myself well enough to really help, but happy golfing :) \$\endgroup\$ – FryAmTheEggman Dec 15 '15 at 16:40
  • 1
    \$\begingroup\$ For one thing, you can remove the vars. Who cares about polluting the global scope in code golf? ;) \$\endgroup\$ – Doorknob Dec 15 '15 at 18:59
  • \$\begingroup\$ Also, /(\w{2})/g can just be /../g -- we already know the input is only letters, and repeating one (or two) characters is shorter than {2}. If you're interested, you can have a look at (and comment questions on) my JavaScript answer to this challenge. Welcome to PGCC! \$\endgroup\$ – apsillers Dec 15 '15 at 19:08
4
\$\begingroup\$

Mathematica, 110 100 99 bytes

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

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.
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.