Council Majority

Question

Introduction

You belong to a council which oversees the destruction of corrupted worlds. When the council assembles, a single vote is taken. The ballot lists all nominated worlds. One is ultimately destroyed each time the council meets.

Due to a bug in user12345's code, the council recently flooded and then sent pirate zombies to the wrong planet. We need a more reliable system for counting votes.

Problem

A vote is described by a series of integers on a single line. The first integer is m, and the worlds nominated for destruction are uniquely numbered from 1 to m. The remaining integers each represent the world each council member voted on.

Somehow, without any collusion, one world always receives more than half of the vote. This always occurs, regardless of how many worlds are present.

Given an input, write a program that outputs the world elected for destruction.

Example Input

Remember, the first 3 is the number of worlds, m. It is not a vote.

3 1 1 2 3 1 3 1 1 3

Example Output

The majority of the council voted for planet 1, so we output that.

1

Assumptions

• The exact number of votes is not given
• The number of votes is between 1 and 100 (inclusive)
• Each vote is between 1 and m (inclusive)
• Every vote contains a majority
• Input must be provided through stdin, read from a file, or accepted as a sole argument to the program

The answer with the fewest characters wins!

Answer 1

GolfScript (10 9 chars)

~]$.,(2/=

Explanation:

~]     # Parse input into array
$      # Sort; note that the extra element giving the number of worlds will end up last
.,(2/= # Take the middle element (not counting the last one)

Thanks to Dennis for 10->9.

Answer 2

APL (21)

∪v/⍨c=⌈/c←+/∘.=⍨v←1↓⎕

Answer 3

Python (50)

l=raw_input().split()[1:];print max(l,key=l.count)

This approach doesn't need sorting. It finds the element which appears the most times is list l, using the max function and different ordering function.

Answer 4

Mathematica (19)

g=Commonest@Rest@#&

Input as follows:

g[{3, 1, 1, 2, 3, 1, 3, 1, 1, 3}]

Output:

{1}

Answer 5

Python, 61 60

l=map(int,raw_input().split())[1:];print sorted(l)[len(l)/2]

22 characters are spent parsing the input with spaces; if I could do comma separated, my score would drop to 39.

Does the same thing as the other answers: drops the first element, then prints the element at halfway through the list when it is sorted.

Explanation:

          raw_input().split()                                # Get the line of input, split on spaces
  map(int,raw_input().split())                               # Convert list of strings into list of ints
  map(int,raw_input().split())[1:]                           # Drop the first element
l=map(int,raw_input().split())[1:];                          # Assign list to variable `l`
                                         sorted(l)           # Sort l in ascending order
                                         sorted(l)[len(l)/2] # Get the element halfway through the list.
                                   print sorted(l)[len(l)/2] # Print it
l=map(int,raw_input().split())[1:];print sorted(l)[len(l)/2] # Combine statements

Answer 6

Pyth 1.0.5, 10

JPwd;ocJNJ

Unlike almost every solution above, this code doesn't just take the middlemost element.

Explanation:

JPwd    J = input, split on spaces
;       Print last element of
ocJN    Order by count in J of N,
J       For N in J

---

Bonus solution:

Council Plurality, 11

If you want pluralities to be correctly judged as well, that's one more character:

JtPwd;ocJNJ

This judges correctly the only case where the above fails for pluralities: When the last planet has one less vote than the plurality winner, the 10 character code will mistakenly select the last planet, because it counts the statement of the number of worlds as a vote.

This code corrects that error by using the tail function, t, to ignore the first number.

Answer 7

J (33 characters)

33 characters in J: (>:@i.>./)@:(+/"1)@(>:@i.@{.=/}.)

Use it as:

(>:@i.>./)@:(+/"1)@(>:@i.@{.=/}.) 3 1 1 2 3 1 3 1 1 3

Answer 8

J - 18 char

({~<.@-:@#)@/:~@}.

Explained by explosion:

({~<.@-:@#)@/:~@}.  NB. find the majority vote!
                }.  NB. remove the head of the list
            /:~     NB. sort the list
(        #)         NB. take the length
   <.@-:            NB. halve it and round down
 {~                 NB. select from the beheaded list

Usage:

   ({~<.@-:@#)@/:~@}. 3 1 1 2 3 1 3 1 1 3
1
   ({~<.@-:@#)@/:~@}. 20 3 2 2 1 1 1 1 7 7 7 7 7 7 7 7 7
7

Answer 9

Groovy - 99 Chars

Using drop-sort-get-midway technique:

l=(System.in.text as List).findAll{!it.allWhitespace}.drop(1).sort()
println l.get((int)l.size()/2)

Ungolfed, somewhat:

list = System.in.text as List
s = list.findAll{ ! it.isAllWhitespace() }.drop(1).sort()
i = (int) s.size() / 2
println s.get(i)

Answer 10

Python (78):

I swear I didn't see Quincunx's answer before I posted this...

from collections import*;print Counter(raw_input().split()[0:]).most_common(1)

Answer 11

C# 133 chars

Because it's totally worth it to go into an old question and add an answer massively longer than any other. c# is tough to golf.

namespace System.Linq{class P{static void Main(){Console.Write(Console.ReadLine().GroupBy(x=>x).OrderBy(x=>x.Count()).Last().Key);}}}

Answer 12

Python, 88 83

from collections import*;print Counter(map(int,raw_input().split())).most_common(1)

This works even if one world gets only one more vote than another, because it uses modes.

The output for the example: [(1, 5)]. The first number is the world to destroy, and the second is the number of votes it got. This output is valid according to your rules:

write a program that outputs the world elected for destruction.

And you gave an Example output, not a Corresponding output.

But if I really need the single number, then this works for 6 more characters:

from collections import*;print Counter(map(eval,raw_input().split())).most_common(1)[0][0]

Explanation:

from collections import*                                                            # import everything from the `collections` module
                                               raw_input().split()                  # Get the line of input, split on spaces
                                       map(int,raw_input().split())                 # Convert the list of strings to a list of ints
                               Counter(map(int,raw_input().split()))                # Create a Counter object (from collections) to get the mode
                               Counter(map(int,raw_input().split())).most_common(1) # Get the most common element of the Counter object
                         print Counter(map(int,raw_input().split())).most_common(1) # Print it
from collections import*;print Counter(map(int,raw_input().split())).most_common(1) # Combined statements

Answer 13

J 21

(~.(#~(=>./))#/.~)@}.

Explanation from right to left:

1. }. drop first number
2. fork:
   1. #/.~: Count per unique element the number of occurences
   2. Hook:
      1. #~ copy from left
      2. (=>./) hook: where right is maximum of right
   3. ~. : take unique elements, in order

Examples

   (~.(#~(=>./))#/.~)@}. 3 1 1 2 3 1 3 1 1 3               
1
   (~.(#~(=>./))#/.~)@}. 10 1 2 1 7 1 2 2 7 7 7
7

Answer 14

PHP - 66

<?=!preg_filter(~‹fl—‹ö,~€û§€ñ‘‘¢¬€œ,$argv[1]).sort($a)?:$a[$i/2];

Without the special chars:

<?=!preg_filter("# .#e",'$a[$i++]=$0',$argv[1]).sort($a)?:$a[$i/2];

Answer 15

JavaScript (60)

a=prompt().split(" ").slice(1).sort();alert(a[a.length/2-1])