Scenariusz

Mieszkasz w kraju, w którym odbywają się wybory prezydenckie. Każdy głosujący otrzymuje jeden głos, dlatego istnieje mocno zakorzeniony system dwupartyjny. (Istnieją strony trzecie, ale nie mają prawie żadnych głosów).

Najnowsze badanie opinii pokazuje wyścig w martwym upale:

• 49%: Alberto Arbusto
• 49%: Jorge Sangre
• 2%: różni drobni kandydaci

Wymagania programu

Zostałeś zatrudniony przez rząd do napisania części oprogramowania do liczenia głosów. Otrzymasz, na standardowym wejściu, nieuporządkowaną listę głosów jednego okręgu, po jednym w wierszu, w następujący sposób:

Alberto Arbusto
Jorge Sangre
Jorge Sangre
Alberto Arbusto
Jorge Sangre
Alberto Arbusto
Alberto Arbusto
Jorge Sangre
Juan Perez
Jorge Sangre
Alberto Arbusto
Alberto Arbusto
…

i po przeczytaniu wszystkich głosów, wyświetla podsumowanie liczby głosów, jakie otrzymał każdy kandydat, posortowane w kolejności malejącej według liczby głosów, tak jak poniżej:

492 Jorge Sangre
484 Alberto Arbusto
 18 Juan Perez
  6 Mickey Mouse

Podstępna część

Jesteś partyzantem, który chce ukraść wybory dla jednego z dwóch głównych kandydatów (możesz wybrać, który z nich). Twój program musi więc celowo drukować nieprawidłowe liczby głosów, z systematycznym nastawieniem do twojego ulubionego kandydata.

Oczywiście musisz to zrobić w taki sposób, aby osoba oglądająca Twój kod lub jego dane wyjściowe prawdopodobnie nie rozpoznała nieprawidłowego zachowania.

Scala

Niech żyje Alberto Arbusto!

import scala.io.Source
import java.util.concurrent.atomic.LongAdder

object Votes extends App {
  val votes = Source.stdin.getLines.toIndexedSeq
  val registeredCandidates = Seq(
    "Alberto Arbusto",
    "Juan Perez",
    "Mickey Mouse",
    "Jorge Sangre"
  )

  val summaries = registeredCandidates map (Summary.apply(_, new LongAdder))

  var currentCandidate: String = _

  for (vote <- votes.par) {
    currentCandidate = vote
    summaries.find(s => s.candidate == currentCandidate).map(_.total.increment)
  }

  for (summary <- summaries.sortBy(-_.total.longValue)) {
    println(summary)
  }
}

case class Summary(candidate: String, total: LongAdder) {
  override def toString = s"${total.longValue} ${candidate}"
}

Alberto Arbusto prawie zawsze wyjdzie nieco przed Jorge Sangre, pod warunkiem oddania wystarczającej liczby głosów (~ 10.000). Nie ma potrzeby ingerowania w same głosy.

Jest warunek wyścigu. Umieszczając Alberto Arbusto wcześniej na liście, zwiększamy jego szanse na wygraną w wyścigu.

Uwaga dodatkowa: ten kod jest luźno oparty na „niestandardowej” puli połączeń napotkanej w projekcie. Zajęło nam tygodnie, aby dowiedzieć się, dlaczego aplikacja ciągle nie ma połączeń.

Rubin

vote_counts = $<.readlines.group_by{|s|s}.collect{ |name, votes| [votes.count, name] }

formatted_count_strings = vote_counts.map do |row,
  formatter = PrettyString.new|"%#{formatter[1][/[so]/]||'s'} %s"%
  [row,formatter]
end

sorted_count_strings = formatted_count_strings.sort_by(&:to_i).reverse

puts sorted_count_strings

Jorge Sangre uzyska znaczny wzrost liczby głosów (na przykład 492 głosy zostaną zgłoszone jako 754). Głosy Alberto zostaną dokładnie przedstawione.

Jak można się domyślić, to nie liczą się głosy, ale kto je formatuje. Próbowałem to ukryć ( PrettyString.newto nie jest prawdziwe i nigdy nie zostaje wywołane), ale formattertak naprawdę to ciąg nazwy. Jeśli drugą literą nazwy jest „o”, liczba głosów zostanie wydrukowana w postaci ósemkowej zamiast dziesiętnej.

Grzmotnąć

(Czy to odpowiada specyfikacji?)

uniq -c|sort -rk2,2|uniq -f1|sort -gr

Jak zawsze wymaga to dodatkowych środków ostrożności w celu zapewnienia prawidłowego wyniku.

uniq -cpoprzedza każdą linię liczbą wystąpień. To w zasadzie wykonuje całą pracę.

Na wypadek, gdyby uniq -ccoś poszło nie tak, sortujemy wyniki według nazw kandydatów w odwrotnej kolejności, a następnie uruchamiamy je uniq -f1(nie drukujemy duplikatów wierszy, ignorując pierwsze pole [liczba głosów]), aby usunąć duplikaty kandydatów. Na koniec używamy sort -grdo sortowania według „Ogólnej liczby” i „Odwrotnej” kolejności (malejącej według liczby głosów).

uniq -czlicza kolejne wystąpienia, a nie wystąpienia w całym pliku. Zwycięzcą zostanie kandydat z największą liczbą głosów.

DO#

using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;

class Program
{
    static void Main(string[] args)
    {
        var candidates = new SortedDictionary<string, int>();
        string candidate;
        using (var sr = new StreamReader("candidates.txt"))
        {
            while ((candidate = sr.ReadLine()) != null)
            {
                if (candidates.ContainsKey(candidate)) 
                    candidates[candidate]++;
                else 
                    candidates.Add(candidate, 1);
            }
        }

        // order by the votes
        var votes = candidates.OrderByDescending(k => k.Value).Select(x => x.Value);

        Console.WriteLine("Candidate | Votes"); 
        for (int i = 0; i < candidates.Count; i++)
        {   
            Console.WriteLine(candidates.ElementAt(i).Key + " " + votes.ElementAt(i));
        }

        Console.ReadKey();
    }
}

Pierwszy kandydat w pliku tekstowym zawsze wygrywa!

Dzięki temu Alberto Arbusto zwycięży!

Nazwy kandydatów są uporządkowane alfabetycznie w słowniku, ale głosy są uporządkowane według liczby.

do

#include <stdio.h>

#define NCANDIDATES 4
static const char * const cand_list[NCANDIDATES] = {
    "Alberto Arbusto",
    "Juan Perez",
    "Mickey Mouse",
    "Jorge Sangre"
};

#define BUFFER_SIZE 100

int
main(int argc, char **argv)
{
    int votes[NCANDIDATES];
    int candidate;
    size_t name_start;
    int i;
    int j;
    int place;
    int max;
    size_t bytes;
    char buffer[BUFFER_SIZE];

    /*
    Make sure input is read in text mode, so we don't have to
    worry about whether line endings are LF or CRLF.
    */
    freopen(NULL, "rt", stdin);

    /* Initialize vote tally. */
    for (candidate = 0; candidate < NCANDIDATES; candidate++) {
        votes[candidate] = 0;
    }

    /* Read and process vote file. */
    do {
        /* Read a block of data. */
        bytes = fread(buffer, 1, BUFFER_SIZE, stdin);

        /* Loop over the data, finding and counting the votes. */
        name_start = 0;
        for (i = 0; i < bytes; i++) {
            if (buffer[i] == '\n') {
                /* Found name. */
                buffer[i] = '\0'; // nul-terminate name so strcmp will work
                /* Look up candidate. */
                for (j = 0; j < NCANDIDATES; j++) {
                    if (strcmp(&buffer[name_start], cand_list[j]) == 0) {
                        candidate = j;
                        break;
                    }
                }
                /* Count vote. */
                ++votes[candidate];

                /* Next name starts at next character */
                name_start = i + 1;
            }
        }
    } while (bytes > 0);

    /* Output the candidates, in decreasing order of votes. */
    for (place = 0; place < NCANDIDATES; place++) {
        max = -1;
        for (j = 0; j < NCANDIDATES; j++) {
            if (votes[j] > max) {
                candidate = j;
                max = votes[j];
            }
        }
        printf("%8d %s\n", votes[candidate], cand_list[candidate]);
        votes[candidate] = -1; // Remove from consideration for next place.
    }

    return 0;
}

Sprzyja Jorge Sangre.

W testach z losowo generowanymi plikami głosowania, nawet gdy Alberto Arbusto otrzymuje do 1,4% więcej rzeczywistych głosów (49,7% vs 48,3% dla Jorge Sangre), mój człowiek Jorge Sangre zazwyczaj wygrywa.

Odczytywanie danych w blokach o stałym rozmiarze często dzieli linię na dwa bloki. Fragment linii na końcu pierwszego bloku nie jest liczony, ponieważ nie ma znaku nowej linii. Fragment w drugim bloku generuje głosowanie, ale nie pasuje do żadnej z nazw kandydata, więc zmienna „kandydat” nie jest aktualizowana. Skutkuje to przeniesieniem głosu z kandydata, którego nazwisko zostało podzielone, na kandydata, który otrzymał poprzedni głos. Dłuższe imię jest bardziej prawdopodobne, że zostanie podzielone na bloki, więc Alberto Arbusto jest częściej „dawcą” głosów niż Jorge Sangre.

Pyton

from collections import defaultdict

def count_votes(candidate, votes=defaultdict(int)):
    with open('votes.txt') as f:
        for line in f:
            votes[line.strip()] += 1

    return votes[candidate]

if __name__ == '__main__':
    candidates = [
        'Mickey Mouse',
        'Juan Perez',
        'Alberto Arbusto',
        'Jorge Sangre'
    ]

    results = {candidate: count_votes(candidate) for candidate in candidates}

    for candidate in sorted(results, key=results.get, reverse=True):
        print results[candidate], candidate

Liczenie głosów faworyzuje kandydatów bliżej końca listy.

W Pythonie, zmienne argumenty domyślne są tworzone i powiązane z funkcją w momencie definicji. Głosy będą zachowywane między wywołaniami funkcji i przenoszone na kolejnych kandydatów. Liczba głosów będzie liczona dwa razy dla drugiego kandydata, trzy razy dla trzeciego i tak dalej.

tr | sed | dc

tr ' [:upper:]' '\n[:lower:]' <votes |\
sed -e '1i0sa0ss0sp' -e \
    '/^[asp]/!d;s/\(.\).*/l\1 1+s\1/
    ${p;c[Alberto Arbusto: ]P lap[Jorge Sangre: ]P lsp[Juan Perez: ]P lpp
    }' | dc

To liczy mojego kumpla Alberto dwa razy za każdym razem.

„Och… tr? Cóż, jest to konieczne, ponieważ komputery nie są zbyt dobre w pisaniu wielkimi literami - lepiej, jeśli wszystkie są małe… Tak, wiem, komputery są szalone.”

WYDAJNOŚĆ

Alberto Arbusto: 12
Jorge Sangre: 5
Juan Perez: 1

Oto kolejna wersja, która daje głos Juana Pereza Jorge Sangre:

tr '[:upper:]' '[:lower:]' <votes |\
sed -e '1i0sj0sa1so' -e \
    's/\(.\).*/l\1 1+s\1/
    ${p;c[Alberto Arbusto: ]P lap[Jorge Sangre: ]P ljp[Others: ]P lop
    }' | dc

WYDAJNOŚĆ

Alberto Arbusto: 6
Jorge Sangre: 6
Others: 1

JavaScript

    function Election(noOfVoters) {
    candidates = ["Albert", "Jorge", "Tony", "Chip"];
    votes = [];

    for (i = 1; i <= noOfVoters; i++) {

        votes.push(prompt("1 - Albert, 2 - Jorge, 3 - Tony , 4 - Chip"))

    }
    votes.sort();
    WinningOrder = count(votes);

    var placement = [];

    for (x = 0; x < candidates.length; x++) {
        placement.push(x + " place with " + WinningOrder[x] + " votes is " + candidates[x] + "\n");
    }
    placement.reverse();
    alert(placement)
}


function count(arr) {
    var a = [],
        b = [],
        prev;

    arr.sort();
    for (var i = 0; i < arr.length; i++) {
        if (arr[i] !== prev) {
            a.push(arr[i]);
            b.push(1);
        } else {
            b[b.length - 1]++;
        }
        prev = arr[i];
    }

    b.sort();

    return b;
}

Ostatnia osoba na liście kandydatów zawsze wygrywa.