Es zählt nicht, wer wählt; es ist, wer die Stimmen zählt [geschlossen]

33

Das Szenario

Sie leben in einem Land, in dem Präsidentschaftswahlen stattfinden. Jeder Wähler erhält eine Stimme, und deshalb gibt es ein fest verankertes Zweiparteiensystem. (Dritte existieren, bekommen aber kaum Stimmen).

Die jüngste Meinungsumfrage zeigt das Rennen in einer toten Hitze:

  • 49%: Alberto Arbusto
  • 49%: Jorge Sangre
  • 2%: verschiedene minderjährige Kandidaten

Die Programmanforderungen

Sie wurden von der Regierung beauftragt, einen Teil der Stimmzählsoftware zu schreiben. Sie erhalten bei Standardeingabe eine ungeordnete Liste mit den Stimmen eines Bezirks, eine pro Zeile, wie folgt:

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

und, nachdem es alle Stimmen gelesen hat, gibt es eine Zusammenfassung der Stimmen, die jeder Kandidat erhalten hat, in absteigender Reihenfolge nach der Anzahl der Stimmen, wie folgt:

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

Der hinterhältige Teil

Sie sind ein Partisanen-Hacker, der die Wahl für einen der beiden Hauptkandidaten stehlen möchte (Sie können wählen, welcher). Daher muss Ihr Programm absichtlich falsche Stimmenzahlen ausgeben, mit einer systematischen Ausrichtung auf Ihren Lieblingskandidaten.

Natürlich müssen Sie dies so tun, dass eine Person, die sich Ihren Code oder dessen Ausgabe ansieht, das falsche Verhalten wahrscheinlich nicht erkennt.

dan04
quelle
2
Wie wäre es, wenn die Person, die das Programm ausführt, wählen würde, auf wen sie sich einlassen möchte? Diese 1 : macht die Herausforderung weniger breit (eine gute Sache), 2 : macht die Antworten interessanter (IMO)
Justin
1
...you can choose which one...Kann ich den auswählen, dessen Name der erste ist?
user80551
2
Mit "voreingenommen" meinen Sie, dass der Kandidat, den wir bevorzugen, gewählt werden muss, oder dass das Programm einfach eine höhere Anzahl von Stimmen für ihn ausgibt als die tatsächlich in der Eingabedatei enthaltene?
3
Es könnte schwierig sein, ein langes Programm in Bash zu rechtfertigen, da ein nicht-hinterhältiges Programm zum Zählen von Stimmen in diesem Format buchstäblich nur sort|uniq -c...
1
@Alessandro: Es muss einfach eine höhere Anzahl von Stimmen für ihn (und / oder eine niedrigere Anzahl von Stimmen für seinen Gegner) ausgeben als das, was tatsächlich in der Eingabe enthalten ist. Es wird davon ausgegangen, dass die Wahl eng genug ist, um von einem kleinen Fehler beeinflusst zu werden.
Dan04

Antworten:

32

Scala

Es lebe 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 wird fast immer etwas vor Jorge Sangre herauskommen, vorausgesetzt, es werden genügend Stimmen abgegeben (~ 10.000). Es besteht keine Notwendigkeit, die Stimmen selbst zu manipulieren.

Es gibt eine Rennbedingung. Und indem wir Alberto Arbusto früher auf die Liste setzen, erhöhen wir seine Chancen, das Rennen zu gewinnen.

Randnotiz: Dieser Code basiert lose auf einem "benutzerdefinierten" Verbindungspool, auf den ich in einem Projekt gestoßen bin. Wir haben Wochen gebraucht, um herauszufinden, warum die Anwendung immer keine Verbindungen mehr hatte.

James_pic
quelle
12
Ich mag dieses wegen der plausiblen Verleugnung, die es gibt.
Dan04
16

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 wird seine Stimmenzahl erheblich steigern (zum Beispiel werden 492 Stimmen als 754 gemeldet). Alberto Stimmen werden genau berichtet.

Wie Sie sich vorstellen können, zählt nicht derjenige, der die Stimmen zählt, sondern derjenige, der die Stimmen formatiert. Ich habe versucht, es zu verschleiern ( PrettyString.newist keine echte Sache und wird nie aufgerufen), aber es formatterist eigentlich die Namenszeichenfolge. Wenn der zweite Buchstabe des Namens "o" ist, wird die Anzahl der Stimmen in Oktal statt Dezimal gedruckt.

Histokrat
quelle
9

Bash

(Entspricht dies der Spezifikation?)

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

Wie immer sind zusätzliche Vorsichtsmaßnahmen erforderlich, um eine gültige Ausgabe sicherzustellen.

uniq -cstellt jeder Zeile die Häufigkeit des Auftretens voran. Dies erledigt im Grunde die ganze Arbeit.

Für den Fall, uniq -cdass etwas nicht in Ordnung ist, sortieren wir die Ausgabe in umgekehrter Reihenfolge nach den Namen der Kandidaten und führen sie dann durch uniq -f1(drucken Sie keine doppelten Zeilen aus und ignorieren Sie das erste Feld [die Anzahl der Stimmen]), um doppelte Kandidaten zu entfernen. Zuletzt sort -grsortieren wir in "General Numeric" und "Reverse" (absteigende Reihenfolge nach Anzahl der Stimmen).

uniq -czählt aufeinanderfolgende Vorkommen, nicht Vorkommen über die gesamte Datei. Der Gewinner ist der Kandidat mit den meisten aufeinanderfolgenden Stimmen.


quelle
16
Wie beeinflusst dies einen bestimmten Kandidaten? Sie haben einfach die Siegbedingung der Wahl geändert. (Das wäre ein Chaos, wenn die Wahlen tatsächlich so entschieden würden :). Sie würden riesige Internet-Gruppen veranlassen, sich zu organisieren, um nacheinander abzustimmen)
Cruncher
1
@Cruncher in den Kommentaren zu der Frage, sagt der Fragesteller, dass es in Ordnung ist, den Vornamen in der Datei zu wählen, also ist dies wahrscheinlich auch in Ordnung
9

C #

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

Der erste Kandidat in der Textdatei gewinnt immer!

Es wird Alberto Arbusto zum Gewinner machen!

Die Namen der Kandidaten sind im Wörterbuch alphabetisch geordnet, die Stimmen jedoch nach Nummern.

mai
quelle
Wird dies also die Wahl nur alphabetisch an den ersten Kandidaten übergeben, oder kann es manipuliert werden, um einen beliebigen Kandidaten zu bevorzugen, den wir mögen?
James_pic
Die Kandidaten werden nicht alphabetisch sortiert. Es werden nur die Stimmen sortiert. Sie können jeden Kandidaten manipulieren, um zu gewinnen. Stellen Sie einfach sicher, dass er der erste in der Textdatei ist.
mai
Aber IIUC SortedDictionary werden die Kandidaten in alphabetischer Reihenfolge sortieren.
James_pic
Oh, ich verstehe. Möglicherweise liegt hier ein Fehler vor. Lass es mich nochmal testen.
mai
1
@James_pic: In der Dictionary<TK,TV>implementierten Hash-Tabelle der Klasse werden Indizes in einem Backing-Array von tatsächlichen Elementen gespeichert . A, Dictionary<TK,TV> aus dem niemals Elemente gelöscht werden, listet die Elemente in der Reihenfolge auf, in der sie hinzugefügt wurden. Ein solches Verhalten ist nicht spezifiziert, aber es ist ausreichend lange vorhanden. Ich würde nicht erwarten, dass MS es jemals ändern wird.
Supercat
7

C

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

Begünstigt Jorge Sangre.

Beim Testen mit zufällig generierten Abstimmungsdateien gewinnt normalerweise mein Mann Jorge Sangre, auch wenn Alberto Arbusto bis zu 1,4% mehr der tatsächlichen Stimmen erhält (49,7% gegenüber 48,3% für Jorge Sangre).

Das Lesen der Daten in Blöcken mit fester Größe teilt eine Zeile häufig auf zwei Blöcke auf. Das Fragment der Zeile am Ende des ersten Blocks wird nicht gezählt, da es kein Zeilenumbruchzeichen enthält. Das Fragment im zweiten Block generiert zwar eine Abstimmung, stimmt jedoch nicht mit den Namen der Kandidaten überein, sodass die Variable "Kandidat" nicht aktualisiert wird. Dies hat zur Folge, dass eine Abstimmung von dem Kandidaten, dessen Name geteilt wurde, auf den Kandidaten übertragen wird, der die vorherige Abstimmung erhalten hat. Ein längerer Name wird mit größerer Wahrscheinlichkeit über mehrere Blöcke verteilt, so dass Alberto Arbusto häufiger als Jorge Sangre als Wahlspender eingestuft wird.

Gary Culp
quelle
5

Python

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

Die Stimmenzahl wird Kandidaten bevorzugen, die näher am Ende der Liste stehen.

In Python werden veränderbare Standardargumente erstellt und an die Funktion bei der Definition gebunden. So bleiben die Stimmen zwischen den Funktionsaufrufen erhalten und werden für nachfolgende Kandidaten übertragen. Die Anzahl der Stimmen wird für den zweiten Kandidaten zweimal gezählt, für den dritten dreimal und so weiter.

grc
quelle
2
Abgesehen von der Tatsache, dass die Gesamtzahl der Stimmen nicht mehr mit den Eingabedaten übereinstimmt, hatte ich diese.
Zaid
0

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

Mein Kumpel Alberto zählt das jedes Mal zweimal.

"Oh - tr? Nun, es ist nur notwendig, weil Computer nicht sehr gut mit Großbuchstaben umgehen können - besser, wenn sie alle in Kleinbuchstaben geschrieben sind ... Ja, ich weiß, Computer sind verrückt."

AUSGABE

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

Hier ist eine andere Version, die Juan Perezs Stimme für Jorge Sangre gibt:

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

AUSGABE

Alberto Arbusto: 6
Jorge Sangre: 6
Others: 1
mikeserv
quelle
0

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

Die letzte Person in der Kandidatenliste gewinnt immer.

Xevvii
quelle