32
\$\begingroup\$

The scenario

You live in a country that is having a presidential election. Each voter gets one vote, and therefore there is a firmly-entrenched two-party system. (Third parties exist, but get hardly any votes).

The latest opinion poll shows the race in a dead heat:

  • 49%: Alberto Arbusto
  • 49%: Jorge Sangre
  • 2%: various minor candidates

The program requirements

You have been hired by the government to write part of the vote counting software. You will be given, on standard input, an unordered list of one precinct’s votes, one per line, like this:

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

and, after it has read all the votes, outputs a summary of how many votes each candidate got, sorted in descending order by number of votes, like this:

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

The underhanded part

You're a partisan hack who wants to steal the election for one of the two main candidates (you can choose which one). So, your program must deliberately print incorrect vote counts, with a systematic bias towards your favorite candidate.

Of course, you must do this is such a way that a person looking at your code or its output would likely not recognize the incorrect behavior.

\$\endgroup\$
12
  • 2
    \$\begingroup\$ How about let the person running the program choose who he/she wants to bias to? This 1: makes the challenge less broad (a good thing), 2: makes the answers more interesting (IMO) \$\endgroup\$
    – Justin
    Jun 20, 2014 at 4:52
  • 1
    \$\begingroup\$ ...you can choose which one... Can I choose the one whose name is the first? \$\endgroup\$
    – user80551
    Jun 20, 2014 at 5:24
  • 2
    \$\begingroup\$ By "biased" you mean that the candidate we prefer must be elected, or thar the program will simply output and higher number of votes for him than the one actually contained in the input file? \$\endgroup\$
    – user25169
    Jun 20, 2014 at 9:06
  • 3
    \$\begingroup\$ It might be difficult to justify a long program in Bash, given that a non-underhanded program to count votes in this format would literally just be sort|uniq -c... \$\endgroup\$
    – user16402
    Jun 20, 2014 at 9:40
  • 1
    \$\begingroup\$ @Alessandro: It simply needs to output a higher number of votes for him (and/or a lower number of votes for his opponent) than what's actually in the input. The election is assumed to be close enough that a small error could swing it. \$\endgroup\$
    – dan04
    Jun 20, 2014 at 13:59

8 Answers 8

34
\$\begingroup\$

Scala

Long live 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 will almost always come out slightly ahead of Jorge Sangre, provided enough votes are cast (~10,000). There's no need to tamper with the votes themselves.

There's a race condition. And by putting Alberto Arbusto earlier in the list, we increase his chances of winning the race.

Side note: This code is loosely based on a "custom" connection pool that I encountered on a project. It took us weeks to figure out why the application was perpetually out of connections.

\$\endgroup\$
1
  • 14
    \$\begingroup\$ I like this one because of the plausible deniability it gives. \$\endgroup\$
    – dan04
    Jun 21, 2014 at 1:21
16
\$\begingroup\$

Ruby

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 will get a substantial boost in his vote count (for example, 492 votes will be reported as 754). Alberto's votes will be reported accurately.

As you might guess, it's not who counts the votes but who formats the votes. I've tried to obscure it (PrettyString.new isn't a real thing and never gets called), but formatter is actually the name string. If the second letter of the name is 'o', the vote count will be printed out in octal instead of decimal.

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

Bash

(Does this meet the specification?)

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

As always, this takes extra precautions to ensure valid output.

uniq -c prefixes each line with the number of times it occurs. This basically does all the work.

Just in case uniq -c does something wrong, we now sort its output by the names of candidates in reverse order, then run it through uniq -f1 (don't print duplicate lines, ignoring the first field [the number of votes]) to remove any duplicate candidates. Finally we use sort -gr to sort in "General Numeric" and "Reverse" order (descending order by number of votes).

uniq -c counts consecutive occurences, not occurences over the whole file. The winner will be the candidate with the most consecutive votes.

\$\endgroup\$
2
  • 16
    \$\begingroup\$ How does this bias any particular candidate. You've simply changed the winning condition of the election. (this would be chaos if this how elections were actually decided :). You'd get giant internet groups organizing to vote sequentially) \$\endgroup\$
    – Cruncher
    Jun 20, 2014 at 15:43
  • 1
    \$\begingroup\$ @Cruncher in the comments on the question, the asker says that it's fine to pick the first name in the file somehow, so this is probably fine as well \$\endgroup\$
    – user16402
    Jun 20, 2014 at 15:52
8
\$\begingroup\$

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

The first candidate in the text file will always win!

It will make Alberto Arbusto the winner!

The candidates' names are ordered alphabetically in the dictionary, but the votes are ordered by number.

\$\endgroup\$
9
  • \$\begingroup\$ So will this just hand the election to the first candidate alphabetically, or can it be manipulated to prefer any candidate we like? \$\endgroup\$
    – James_pic
    Jun 20, 2014 at 12:42
  • \$\begingroup\$ It doesn't sort the candidates alphabetically. It only sorts the votes. You can manipulate any candidate to win. Just make sure he is the first one in the the text file. \$\endgroup\$
    – mai
    Jun 20, 2014 at 12:48
  • \$\begingroup\$ But IIUC SortedDictionary will sort the candidates alphabetically. \$\endgroup\$
    – James_pic
    Jun 20, 2014 at 12:53
  • \$\begingroup\$ Oh, I see. There might be a mistake here. Let me test it again. \$\endgroup\$
    – mai
    Jun 20, 2014 at 12:53
  • 1
    \$\begingroup\$ @James_pic: The hash table of the Dictionary<TK,TV> class, as implemented, stores indices into a backing array of actual items. A Dictionary<TK,TV> from which no items are ever deleted will enumerate elements in the order they were added; such behavior is not specified, but it's been in place sufficiently long I would not expect MS to ever change it. \$\endgroup\$
    – supercat
    Jun 20, 2014 at 17:08
7
\$\begingroup\$

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

Favors Jorge Sangre.

In testing with randomly generated vote files, even when Alberto Arbusto receives up to 1.4% more of the actual votes (49.7% vs 48.3% for Jorge Sangre), my man Jorge Sangre usually wins the count.

Reading the data in fixed-size blocks often splits a line across two blocks. The fragment of the line at the end of the first block doesn't get counted because it doesn't have a newline character. The fragment in the second block does generate a vote, but it doesn't match any of the candidate's names so the 'candidate' variable doesn't get updated. This has the effect of transferring a vote from the candidate whose name was split to the candidate who received the previous vote. A longer name is more likely to be split across blocks, so Alberto Arbusto ends up being a vote "donor" more often than Jorge Sangre does.

\$\endgroup\$
5
\$\begingroup\$

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

The vote counts will favour candidates closer to the end of the list.

In Python, mutable default arguments are created and bound to the function at definition. So the votes will be maintained between function calls and carried over for subsequent candidates. The number of votes will be counted twice for the second candidate, three times for the third, and so on.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Except for the fact that the total vote count is no longer consistent with the input data, this one had me. \$\endgroup\$
    – Zaid
    Jun 21, 2014 at 4:20
0
\$\begingroup\$

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

This counts my buddy Alberto twice every time.

"Oh - tr? Well, it's just necessary because computers aren't very good with capital letters - better if they're all lowercase.... Yeah, I know, computers are crazy."

OUTPUT

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

Here's another version that gives Juan Perez's vote to 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

OUTPUT

Alberto Arbusto: 6
Jorge Sangre: 6
Others: 1
\$\endgroup\$
0
\$\begingroup\$

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

The last person in the candidates list will always win.

\$\endgroup\$

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