Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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!

share|improve this question

15 Answers 15

up vote 8 down vote accepted

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.

share|improve this answer
    
Apologies for missing the time limit on this one and accepting your answer 11 days late. I've since stopped using time limits on challenges. Cheers! –  Rainbolt Mar 26 at 14:05
    
Since the first element is guaranteed to be the last after sorting, ~]$.,(2/= should work as well. –  Dennis May 16 at 17:54

APL (21)

∪v/⍨c=⌈/c←+/∘.=⍨v←1↓⎕
share|improve this answer

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.

share|improve this answer

Mathematica (19)

g=Commonest@Rest@#&

Input as follows:

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

Output:

{1}
share|improve this answer

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
share|improve this answer
    
Can't you do list(raw_input())[2::2] instead of raw_input().split() –  user80551 Mar 12 at 17:57
    
@user80551 Actually, I cannot use that. What if the number of worlds was 42? –  Quincunx Mar 12 at 18:00
    
Stop using 42 when 10 would have sufficed, that's enough for now I think :) –  user80551 Mar 12 at 18:01
    
@user80551 "that's enough for now I think". Do you mean that I should just do your method, or that I use 42 too much? –  Quincunx Mar 12 at 18:04
    
I think that everyone on PCG.SE is using 42 too much since codegolf.stackexchange.com/questions/21835/… –  user80551 Mar 12 at 18:05

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.

share|improve this answer
3  
The compiler you linked to on GitHub was modified two hours ago. This challenge is months old. The community here usually only accepts answers for which a compiler existed before the challenge was posted. I guess it doesn't really matter here, because it doesn't look like you tailored your language specifically to this challenge. –  Rainbolt Jul 3 at 13:46
    
@Rusher I've only just completed my language, about a week ago, well after this challenge was posted. In addition, I'm still revising things almost every day. I'll of course understand if it won't get accepted for anything, but I didn't feel like that should stop me from posting. –  isaacg Jul 3 at 17:54
1  
Oh of course you can post. I didn't downvote your post or anything (and I just noticed you explained your code in a way that I can understand it, so I upvoted as well). I just didn't want you to be surprised in the event that you somehow get it down to 8 characters and don't get accepted answer. –  Rainbolt Jul 3 at 17:59
    
@Rusher Oh, I see. Thanks for the clarification. –  isaacg Jul 3 at 18:01

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
share|improve this answer

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
share|improve this answer

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)
share|improve this answer

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)
share|improve this answer

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);}}}
share|improve this answer
1  
Haha I bet you were cringing while writing out Write, ReadLine, GroupBy, OrderBy, etc. All my charz down teh drainz! Pretty good for the language chosen. –  Rainbolt May 16 at 15:28

JavaScript (60)

a=prompt().split(" ").slice(1).sort();alert(a[a.length/2-1])
share|improve this answer
    
Doesn't work if a.length & 1 –  Florent Mar 13 at 12:36

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
share|improve this answer
    
@Rusher The first program's output is valid according to your description, because it clearly indicates which world is the world to destroy ;-) –  Quincunx Mar 12 at 19:09

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
share|improve this answer

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];
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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