Stack Exchange автоматически обнаруживает последовательное голосование (когда один пользователь повышает или понижает количество постов другого пользователя) и отменяет его. В этом задании вы реализуете очень, очень простой детектор «серийного голосования».

вход

Входные данные представляют собой строку, представляющую список голосов. Каждая группа из двух символов представляет собой голос - первый - это избиратель, а второй - пользователь, за которого проголосовали. Например, следующий вход

ababbccd

может быть проанализирован как ab ab bc cdи представляет aголосование bдважды, bголосование cодин раз и cголосование dодин раз.

Ввод будет состоять только из строчных букв и всегда будет иметь четную длину> 0. Вы также не можете голосовать за себя (так что нет aaили hh).

Выход

Для целей этой задачи последовательное голосование определяется как голосование любого данного пользователя за любого другого пользователя три или более раз.

Выходные данные показывают, сколько голосов должно быть отменено для каждого пользователя (то есть, сколько голосов за каждого пользователя было отменено, а не сколько голосов, которые они дали, было отменено) в формате [user][votes][user2][votes2].... Например, следует ввести abababab( aголосование bчетыре раза) b4(четыре голоса были отменены из aв b).

Вывод может быть в любом порядке, который вы хотите, но и вход, и выход должны быть однострочными, как описано выше.

Контрольные примеры

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

Pyth, 22 байта

pM_srSsfttTtMM.gkcz2 8

Попробуйте онлайн: демонстрация или тестовый набор

Объяснение:

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

Пример:

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

Не читается , 1830 1796 1791 1771 1762 1745 1736 1727 1626 1606 1577 байт

Вывод в обратном алфавитном порядке ( zдо a), но в соответствии с вашими правилами, что представляется допустимым.

«" „“ „„„“ „“ „“““ „„„“““ „“»«»«„“ „“ „“ „“ „“»«»«»«»" „“ „“» «„„““» «» «„“„“„“» «» «„„“ „“ „“ „“ „““» «» "" „“ „“ „„„“ „“ „“““ «„„““» «„„“ „„„“ „“ „“““ „„„“““ „““» «» «» «» «" „“ „“ „“»" „“«"»«»«"„“„“„„„“„“„“““„„„“““» "„“„„„“„“„“„“““„“„“„“ «"»«»«„“»«»«„„“„“„““»«»«„“»«»«»«»«"„“» «„“„“„“„“"» «» «„“» «» «„“„“„“"»„“„“„“«"„“» "„“„“„“„“„„„“““" „„““«» «» «» «„“„“„“„„„“„„„“„“„“„“““„“„“„“““„“„“„“» «» "" „“ «» «» «„„“ „“ „“ „„„“““ „““» «„„““» «" „“ „“ „“»" „“ „“ „“ „„„“““ «» «„“» «» «» «» «„„“ „“ „“ „„„“““ „““» «» «» «„„““» «„„““»»«„„““» «„„““» «„„““» «„„““» «„„““» «„„““» «„„““» «„„““» "» «» «„“» «» «„“» «» «„“» «» «„“» «» «„“» «» «" „“ „“ „„„“ „“ „“““»" «» «„“» «» «„„“ „“ „“ „““» «» «» «» «„“» «» «„“» «» «„„“ „““» «» "»«» «» «» «» «„„“ „“ „“ „““» «» «» «„„““» «» «„“» «» «» «» "" „“ „“ „“ «" „„„“““ „„„“““ „„„“““ „„„“““ „„„“““ „„„“““ „„„“““ "„„““ «» «„“» «» «„“» «» «„“» «» «„“» «» «„“» «» «„“» «» «„“» «» «„“» «»«"»«»«„“»«»«„“»«»«„“»«»«„“»«»«„“»«»«„“»«»«„“»«»"» «„„““» «„„““» «„„““» «„„““» «„„““» «„„““» «„„““» «„„““» "» «» «„“» «» «„“» «» «„“» «» «„“» «» «„“» «» «„“» «» «„“» «» «„“» «» '«» «„“» «» «„“» «» «„“» «» «„“» «» «„“» «» «„“» «» «„“» «» «» «» "» «» «„“» «» «„“"»«"„“„“„“» «„“"»„“«"„“„“„„„“„“„“„“““„“» «» «„“„“„“„“» «» «„„“ „“ „“ „„„“““ „““» «» «„„“ „“ „““» «» "„“«» «» «„“» «» «" „“ „„„“ „“ „“““ „“ „“ „„„“““»" „“ „„„“ „“ „“ „“““ «» «» «» «„“» «» "„“„„„“““„„„“““„„„“““„„„“““„„„“““" „„““ «» «„“» «» «„“» «» «„“» «» «„“» «» «„“» «» «„“» «» «„“» «» «„“» «»«"»«»«„“»«»«„“»«»«„“»«»«„“»«»«„“»«»«„“»«»«„“»«»"» «„„““» «" „“ „“ „„„“ „“ „“““ „“ „“ „“»" „“ „„„“ „“ „“ „“““ „“ „“ „“ «" „“ „“ „“»«»«"„“„“„“„“„„„“„“„“„“““„“„“„“» "„“„“„“«» «„“„“„“„“» «» «» «» «» «„“„“„“„“» «» «» «» «» «„“„“„“„“» «» «» «» «» «„“„“„“„“» «» «» «» «„„“ „„„“ „“ „“““ „““» «" „“ „“ „“»" «» «„„“ „““» «» «» «„„““» «» «„“» «» «» «» «„„““» «» "„“„“„“«" "» „“ «" „“ „“»«„“ „“ „“ „„„“““ "» „“ «"»«„“ „“ „“ "» „“ „“ „“ " «„„“ „“ „““» «„„““» «» «„“» «» «» «» «„„““» «" „“»«» «„“» «» «„„““» «» «» «» «„“» «» "„“»«» «„“» «» «„„““» «» «» «» «„“» «» "„“»

объяснение

Во-первых, чтобы получить представление о том, что может сделать Unreadable, вот его основная операция:

• У вас есть бесконечная лента целочисленных ячеек произвольного размера
• Вы не иметь указатель памяти , как в Brainfuck; вместо этого вы разыменовываете ячейки по их расположению на ленте. Это означает, что вы можете «прочитать значение # 4» или «прочитать значение # (прочитать значение # 4)» (двойное разыменование).
• Вы можете только читать или записывать ячейки памяти (а не напрямую увеличивать / уменьшать, как в Brainfuck).
• Вы можете увеличивать / уменьшать значения в выражении. Таким образом, чтобы увеличить ячейку памяти , вы должны прочитать , приращение , запись , или иначе говоря: write(x, inc(read(x))).
• Существуют циклы while и троичные условные выражения, которые могут проверять только ноль против ненулевого значения.

Эта программа использует ленту следующим образом. Имена переменных будут использованы в псевдокоде ниже. Кроме того, это документирует первую версию (которая была 1830 байтов); см. правки внизу, чтобы узнать, что изменилось с тех пор.

• Ячейка 0: переменнаяq
• Ячейка 1: переменные a, p,ch
• Ячейка 2: переменные hash,v
• Ячейка 3: переменные b,r
• Ячейка 4: переменные aa,l
• Ячейка 5: остается 0, чтобы отметить «конец» строки десятичных цифр
• Ячейки 6–95: сохранить строку десятичных цифр назад
• Ячейки 96–121: сохраняют количество голосов, которые будут удержаны пользователями a(96) - z(121) (код ASCII буквы минус один).
• Ячейки 4657–7380: запомните, какие комбинации избирателей и избирателей встречались сколько раз. Эти ячейки имеют только 4 возможных значения: 0= еще не видел, -1= видел один раз, -2= видел дважды, -3= видел любое количество раз больше, чем 2.

Алгоритм по существу работает следующим образом:

• Продолжайте читать пары символов aи b. Вычислите значение хеша (a-2)*(a-1)+b-1, которое уникально для каждой комбинации букв a – z.
• Проверьте ячейку памяти на это значение хеша ( *hash). Если это так -3, пользователь уже имеет право на удаление голосов, так что увеличивайте *(b-1). В противном случае, уменьшить *hash. Если это сейчас -3 , пользователь только что получил право на удаление голоса после трех вхождений, так что увеличивайте *(b-1)на 3.
• После этого пройдите через символы в обратном порядке ( zдо a) и выведите те, которые требуют вычтенных голосов. Это требует ручного целочисленного деления на 10, чтобы перевести число в десятичные цифры.

После того, как все прояснилось, программа выглядит как псевдокод:

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

Изменить 1, 1830 → 1796: понял, что я могу повторно использовать возвращаемое значение цикла while в одном месте.

Edit 2, 1796 → 1791: Оказывается, программа немного меньше, если вместо использования ячеек 6–95 я сохраню десятичные цифры в ячейках с отрицательным номером (–1 и далее). В качестве дополнительного бонуса программа больше не ограничена 10⁹⁰ голосами!

Редактировать 3, 1791 → 1771: вместо присвоения результата *(ch = l + 95)для vя теперь присваиваю его, qа затем перемещаю присвоение v = qв условие while, переводя код в 1777 байт. Затем поменяйте местами расположение qи vна ленте, потому что qтеперь это на 1 чаще, чем v.

Изменить 4, 1771 → 1762: Дух. Инициализация hashдо 1 вместо 0 на 9 байт короче. Хеш-код теперь на 1 больше, что не имеет значения.

Редактировать 5, 1762 → 1745: если я инициализирую qи равным r1 вместо 0, мне придется посыпать некоторые -1s местами, чтобы все было правильно, и все это, похоже, отменяется - за исключением того, что while v { --v; [...] }цикл теперь должен выполнить на одну меньшую итерацию, что я могу сделать, сказав while --v { [...] }, что на 26 символов короче.

Изменить 6, 1745 → 1736: Вместо этого { r = 1; ++q }мы можем написать q = *((r = 1)+1)+1. Это зависит от того, что qнаходится в переменной слот № 2. Если бы это было в слоте № 1, это было бы еще короче, но тогда вся программа была бы длиннее в целом.

Правка 7, 1745 → 1727: отменил правку 6 и вместо этого добился сохранения, вставив самый внутренний цикл while в выражение, которое вычисляет цифровой код ASCII, который также заканчивается 1736 байтами ... но затем сохранил инструкцию уменьшения (9 байтов). ), изменив ((++r) - 11) ? r :на (r - 10) ? ++r :.

Изменить 8, 1727 → 1626: переработан расчет хеша. Теперь он использует один цикл while. Местоположения ячеек теперь имеют свои действительные коды ASCII (больше не на 1). Перестановки переменных в разных местах на ленте, потому что они теперь происходят с различной частотой.

Изменить 9, 1626 → 1606: более сумасшедшее встраивание. Тело первого цикла while теперь выглядит примерно так:

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

и назначение переменных теперь почти полностью изменилось.

Edit 10, 1606 → 1577: Я заметил , что aи a2оба декрементируется 0 в то время как петли, так что, если я мог бы пару pни с одним из тех , кто, но не с ch, я не должен был бы инициализировать pдо 0(который стоит 29 байт). Оказывается, я могу сделать это путем обмена pи r. Новейшие назначения переменных (и их частота появления в коде) теперь:

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 байта

Вечеринка!

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

или же

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

Запустите все тестовые случаи

объяснение

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.

Другая версия начинается с обращения пар, что позволяет сохранить два байта в другом месте: а) выбор первого символа в каждой строке только :cвместо Wf=выбора второго. b) Нам не нужно снова сортировать перед вторым RLE, потому что пары уже отсортированы в основном по оставшемуся символу.

Баш, 95 94 85 81 байт

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

Элегантное, но длинное первое решение, чтобы начать ...

Благодаря User112638726 для сохранения байт с sed, DigitalTrauma для сохранения 9 с fold, и Райнер П. для сохранения 4 больше с awk«с substr!

Чтобы увидеть, как это работает, давайте посмотрим abababcbcbcbcbbababa.

• После fold -2(обернуть строку на ширину 2), мы имеем

  ab
  ab
  cb
  cb
  cb
  cb
  ba
  ba
  ba
  

• После того, как sort | uniq -c( -cочень изящный флаг uniq, показывающий, сколько раз каждая строка появляется на входе), мы получаем

        3 ab
        3 ba
        4 cb
  

• Теперь давайте рассмотрим последнюю awkкоманду:

  • $1>2: Выводить данные только в том случае, если запись 1 (то есть число идентичных голосов) больше 2 (то есть ≥ 3). Другими словами, игнорируйте любую строку, которая начинается с числа ≤ 2.

  • {c[substr($2,2)]+=$1}: Если число больше 2, добавьте это число в cхеш-таблицу, используя в качестве ключа второй символ записи 2 (он же голос-е). (Нам не нужно инициализировать все до нуля; это awkделается для нас.)

  • END{...}Это означает, что «после обработки всего файла, вот что делать дальше».

  • for(x in c)printf x c[x]: Довольно понятно Напечатайте каждый ключ и его соответствующее значение.

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

Тестовые случаи:

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

На высоком уровне этот код заполняет объект парами ключ-значение, которые сопоставляют получателей голосов с количеством голосов, например, { b:7, a:3 }и затем соединяют их в строку в forцикле. Код находится в evalвыражении, позволяющем использовать forфункцию внутри стрелки без необходимости тратить байты на { }и ;return r.

( Попросите пользователя 81655 для сохранения трех байтов!)

Объяснение evalкода:

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 байта

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)

Пример использования: f "jkkjjkkjjkkjljljljmlmlnmnmnm"->"k3j6m3"

Как это устроено:

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 байт

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

Контрольная работа

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 байт

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

Perl 86 84 83 байта

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

Это 82 байта плюс 1 для -pаргумента командной строки:

$ 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

• обновление 84 Сохранить 2 байта, вставив grep
• обновление 83 Сохранить 1 байт, используя глобальные временные переменные ${$'}вместо $g{$'}. К сожалению, $$'не работает.

Чистый Баш, 151

Дольше, чем я надеялся, но вот оно.

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

Использует ассоциативное индексирование массива для необходимого подсчета. Требуется bash версии 4.0 или выше.

247 символов PHP

(Ой)

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

Разъяснения

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

Сделал это, не заглядывая в другие ответы. Это самый сложный кодовый гольф, с которым я когда-либо сталкивался. Я приветствую все оптимизации.

R, 221 байт

код

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

Здесь есть много возможностей для улучшения.