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.

Results - July 19, 2014

The current King of the Hill is Mercenary by user Fabigler! Keep submitting entries and knock him off of his throne!

Click here to view the Scoreboard.

Programs submitted on or before July 19, 2014 were included. All other submissions will be included in future trials. New results should be posted around August 9, so that gives you plenty of time.


Illustration drawn by brother Illustrated by Chris Rainbolt, my brother and a fresh graduate from Savannah College of Art and Design

Introduction

The angels and demons are fighting and, as usual, using earth as their battleground. Humans are stuck in the middle and are being forced to take sides. An unknown neutral force rewards those who consistently fight for the losing side.

The Game

Each trial, you will be pseudorandomly paired and then shuffled with between 20 and 30 other submissions. Each trial will consist of 1000 rounds. Each round, you will be passed an input and be expected to produce output. Your output will be recorded and scored. This process will be repeated 1000 times.

Input

You will receive a single argument that represents the past votes of each player. Rounds are delimited by comma. A 0 represents a player who sided with Evil that round. A 1 represents a player who sided with Good. Within a trial, the players will always be in the same order. Your own vote will be included, but not explicitly identified. For example:

101,100,100

In this example, three rounds have been completed and three players are competing. Player one always sided with Good. Player two always sided with Evil. Player three swapped from Good in round 1 to Evil in rounds 2 and 3. One of those players was you.

Output

Java Submissions

  • Return the string good if you want to side with Good.
  • Return the string evil if you want to side with Evil.

Non-Java Submissions

  • Output the string good to stdout if you want to side with Good.
  • Output the string evil to stdout if you want to side with Evil.

If your program outputs or returns anything else, throws an exception, does not compile, or takes longer than one second to output anything on this exact machine, then it will be disqualified.

Scoring

Scores will be posted in a Google docs spreadsheet for easy viewing as soon as I can compile all the current entries. Don't worry - I will keep running trials for as long as you guys keep submitting programs!

  • You receive 3 points for siding with the majority during a round.
  • You receive n - 1 points for siding with the minority during a round, where n is the number of consecutive times you have sided with the minority.

Your score will be the median of 5 trials. Each trial consists of 1000 rounds.

Deliverables

Non-Java Submissions

You must submit a unique title, a program, and a Windows command line string that will run your program. Remember that an argument may be appended to that string. For example:

  • python Angel.py
    • Note that this one has no args. This is round one! Be prepared for this.
  • python Angel.py 11011,00101,11101,11111,00001,11001,11001

Java Submissions

You must submit a unique title and a Java class that extends the abstract Human class written below.

public abstract class Human {
    public abstract String takeSides(String history) throws Exception;
}

Testing

If you want to test your own submission, follow the instructions here.

Additional Notes

You may submit as many different submissions as you want. Submissions that appear to be colluding will be disqualified. The author of this challenge will be the only judge on that matter.

A new instance of your program or Java class will be created every time it is called upon. You may persist information by writing to a file. You may not modify the structure or behavior of anything except your own class.

Players will be shuffled before the trial starts. Demon and Angel will participate in every trial. If the number of players is even, Petyr Baelish will also join. Demon fights for Evil, Angel for Good, and Petyr Baelish chooses a pseudorandom side.

share|improve this question
2  
Comments purged, as they were obsolete and at request of OP. Please notify me of any comments that need to be undeleted. –  Doorknob Jul 16 at 11:28
7  
Woah, OP changes his username. Ok, so when will the result be displayed? –  justhalf Jul 18 at 6:52
5  
@Rainbolt This must be one freakin' hell of a job, running this challenge! The reason for this amount of attention is the simplicity of the protocol and the rules, making it accessible while also allowing simple, working entries. TL;DR: Your challenge is too good! :D –  tomsmeding Jul 19 at 18:54
3  
@dgel I'll post the raw data, upper, lower, averages, and maybe a line chart so we can see who did better as the competition dragged on. –  Rainbolt Jul 21 at 12:03
4  
One of the pods ended up with 10 entries that voted the same way every single time. Consequently, two users ended up with perfect or "one round short of perfect" scores of around 450,000. The same entries scored around 1900 in other trials. The average score is close to 2000. Because of the extreme imbalance in results, I decided that a more meaningful number would be a median. I edited the challenge so that after 5 trials, the winner will be the submission with the highest median. If anyone thinks that moving from mean to median is unfair or otherwise a poor choice, please comment. –  Rainbolt Jul 21 at 18:57

91 Answers 91

Hipster, Ruby

if ARGV.length == 0
    puts ["good", "evil"].sample
else
    last_round = ARGV[0].split(',').last
    n_players = last_round.length
    puts last_round.count('1') > n_players/2 ? "evil" : "good"
end

Simply goes with last round's minority, just because everything else is mainstream.

Run like

ruby hipster.rb
share|improve this answer
    
Does that work if is given no input? Remember, no argument on the first round. –  isaacg Jul 8 at 21:08
1  
@isaacg fixed. :) –  Martin Büttner Jul 8 at 21:13
1  
Isn't it supposed to output "good" or "evil" instead of "0" or "1"? –  David Conrad Jul 8 at 21:21
1  
@Manu -.- ... thanks –  Martin Büttner Jul 9 at 8:41
13  
@DatEpicCoderGuyWhoPrograms Stop suggesting edits everywhere. They're entirely valid, since syntax highlighting is nice and useful, but it's slightly annoying. –  tomsmeding Jul 9 at 20:57

Petyr Baelish

You never know whose side Petyr Baelish is on.

package Humans;

/**
 * Always keep your foes confused. If they are never certain who you are or 
 * what you want, they cannot know what you are like to do next.
 * @author Rusher
 */
public class PetyrBaelish extends Human {

    /**
     * Randomly take the side of good or evil.
     * @param history The past votes of every player
     * @return A String "good" or "evil
     */
    public String takeSides(String history) {
        return Math.random() < 0.5 ? "good" : "evil";
    }
}

This entry will only be included if the number of players is even. This ensures that there will always be a majority.

share|improve this answer
25  
On Petyr Baelish's side, obviously. –  Cthulhu Jul 9 at 7:25
2  
@Kevin It consistently beats most of the bots. It usually scores 27ish. –  cjfaure Jul 9 at 20:17
2  
@Kevin This entry was submitted by the author of the challenge. It wasn't meant to do well. It exists to make sure that there will always be a majority, because with an even number of players, there could be a tie. –  Rainbolt Jul 9 at 20:17
4  
Why oh God why has this one got the most votes? It's just not fair. –  tomsmeding Jul 9 at 20:27
3  
@tomsmeding No. It's a quote from Game of Thrones lol. –  Rainbolt Jul 9 at 20:55

C++, The Meta Scientist

This one does essentially the same as The Scientist, but doesn't operate on rounds as a whole but on the individual players. It tries to map a wave (or a constant function) to each player separately and predicts their move in the next round. From the resulted round prediction, The Meta Scientist chooses whichever side looks like having a majority.

#include <iostream>
#include <utility>
#include <cstdlib>
#include <cstring>
#if 0
#define DBG(st) {st}
#else
#define DBG(st)
#endif

#define WINDOW (200)

using namespace std;

int main(int argc,char **argv){
    if(argc==1){
        cout<<(rand()%2?"good":"evil")<<endl;
        return 0;
    }
    DBG(cerr<<"WINDOW="<<WINDOW<<endl;)
    int nump,numr;
    nump=strchr(argv[1],',')-argv[1];
    numr=(strlen(argv[1])+1)/(nump+1);
    int period,r,p;
    int score,*scores=new int[WINDOW];
    int max; //some score will always get above 0, because if some score<0, the inverted wave will be >0.
    int phase,phasemax;
    int predicted=0; //The predicted number of goods for the next round
    int fromround=numr-WINDOW;
    if(fromround<0)fromround=0;
    pair<int,int> maxat; //period, phase
    DBG(cerr<<"Players:"<<endl;)
    for(p=0;p<nump;p++){
        DBG(cerr<<" p"<<p<<": ";)
        for(r=fromround;r<numr;r++)if(argv[1][r*(nump+1)+p]!=argv[1][p])break;
        if(r==numr){
            DBG(cerr<<"All equal! prediction="<<argv[1][p]<<endl;)
            predicted+=argv[1][(numr-1)*(nump+1)+p]-'0';
            continue;
        }
        max=0;
        maxat={-1,-1};
        for(period=1;period<=WINDOW;period++){
            scores[period-1]=0;
            phasemax=-1;
            for(phase=0;phase<2*period;phase++){
                score=0;
                for(r=fromround;r<numr;r++){
                    if(argv[1][r*(nump+1)+p]-'0'==1-(r+phase)%(2*period)/period)score++;
                    else score--;
                }
                if(score>scores[period-1]){
                    scores[period-1]=score;
                    phasemax=phase;
                }
            }
            if(scores[period-1]>max){
                max=scores[period-1];
                maxat.first=period;
                maxat.second=phasemax;
            }
            DBG(cerr<<scores[period-1]<<" ";)
        }
        DBG(cerr<<"(max="<<max<<" at {"<<maxat.first<<","<<maxat.second<<"})"<<endl;)
        DBG(cerr<<"     prediction: 1-("<<numr<<"+"<<maxat.second<<")%(2*"<<maxat.first<<")/"<<maxat.first<<"="<<(1-(numr+maxat.second)%(2*maxat.first)/maxat.first)<<endl;)
        predicted+=(1-(numr+maxat.second)%(2*maxat.first)/maxat.first);
    }
    DBG(cerr<<"Predicted outcome: "<<predicted<<" good + "<<(nump-predicted)<<" evil"<<endl;)
    if(predicted>nump/2)cout<<"evil"<<endl; //pick minority
    else cout<<"good"<<endl;
    delete[] scores;
    return 0;
}

If you want to turn on debug statements, change the line reading #if 0 to #if 1.

Compile with g++ -O3 -std=c++0x -o MetaScientist MetaScientist.cpp (you don't need warnings, so no -Wall) and run with MetaScientist.exe (possibly including the argument of course). If you ask really nicely I can provide you with a Windows executable.

EDIT: Apparently, the previous version ran out of time around 600 rounds into the game. This shouldn't do that. Its time consumption is controlled by the #define WINDOW (...) line, more is slower but looks further back.

share|improve this answer
2  
I humbly suggest you try picking the losing side. If you can consistently guess correctly, you'll get more than 3 points per round. –  Kevin Jul 9 at 20:18
1  
@Kevin That's true, but I figured that it might guess the wrong side pretty quickly, and you need to correctly guess the losing side more than seven times in a row to get an improvement over always getting the majority right. I might change it though. –  tomsmeding Jul 9 at 20:23
1  
@Kevin Also, I'd first like to see how these do (Scientist and Meta Scientist) when Rusher gets us a scoreboard this weekend, as he indicated in the comments to the OP. Rusher, sorry, but I'm too lazy to compile all the stuff myself... :) –  tomsmeding Jul 9 at 20:28
3  
No worries! It probably isn't safe to run these anyway. Just let me screw up my machine with code written by 50 strangers on the Internet. –  Rainbolt Jul 9 at 20:39
1  
@Kevin But that's so MANY! I can, indeed, but I don't like it. I'll see how these fare. –  tomsmeding Jul 9 at 20:43

Angel

The purest player of all.

Program

print "good"

Command

python Angel.py
share|improve this answer
18  
Python is a good language. It seems only natural that the Angel should use it. –  jpmc26 Jul 10 at 1:24
11  
May I remind people that a Python is a Snake. A Serpent. –  Mr Lister Jul 15 at 7:52
1  
@MrLister May I remind you that Lucifer was a great Angel before God cast him out of heaven? –  Zibbobz Jul 18 at 18:36
    
@Zibbobz Yeah... shame really, that they fell out. They could have achieved so much together. –  Mr Lister Jul 18 at 20:03

Artemis Fowl

package Humans;

public class ArtemisFowl extends Human {
    public final String takeSides(String history) {
        int good = 0, evil = 0;
        for(int i = 0; i < history.length(); i++)   {
            switch(history.charAt(i))   {
                case '0': evil++; break;
                case '1': good++; break;
            }
        }
        if(good % 5 == 0){
           return "good";
        } else if (evil % 5 == 0){
           return "evil";
        } else {
           if(good > evil){
              return "good";
           } else if(evil > good){
              return "evil";
           } else {
              return Math.random() >= 0.5 ? "good" : "evil";
           }
        }
    }
}

In Book 7, The Atlantis Complex, Artemis Fowl contracted a psychological disease (called Atlantis complex) that forced him to do everything in multiples of 5 (speaking, actions, etc). When he couldn't do it in some multiple of 5, he panicked. I do basically that: see if good or evil (intentional bias) is divisible by 5, if neither is, then I panic & see which was greater & run with that or panic even further & randomly choose.

share|improve this answer
4  
When I read Artemis Fowl in Junior High, only two books existed. It's nice to see that there are now seven, and that Disney is making it into a movie. –  Rainbolt Jul 9 at 1:11
1  
There's actually 8 books. –  Kyle Kanos Jul 9 at 1:12
6  
The more the merrier (unless you are reading The Wheel of Time) –  Rainbolt Jul 9 at 1:13
1  
And you forgot break; in your switch. –  johnchen902 Jul 9 at 12:33
1  
@johnchen902,@Manu: I am not very experienced in java (I use Fortran90+ & only see java here), hence my errors. I'll fix them when I get into the office in an hour. –  Kyle Kanos Jul 9 at 12:37

Disparnumerophobic

Odd numbers are terrifying.

package Humans;

public class Disparnumerophobic extends Human {
    public final String takeSides(String history) {
        int good = 0, evil = 0;
        for(int i = 0; i < history.length(); i++)   {
            switch(history.charAt(i))   {
                case '0': evil++; break;
                case '1': good++;
            }
        }
        if(good%2 == 1 && evil%2 == 0)  return "evil";
        if(evil%2 == 1 && good%2 == 0)  return "good";
        // well shit.... 
        return Math.random() >= 0.5 ? "good" : "evil";
    }
}
share|improve this answer
17  
Comment made me laugh/snort. –  phyrfox Jul 9 at 3:50

Linus, Ruby

Seeks to confound analysts by always breaking the pattern.

num_rounds = ARGV[0].to_s.count(',')
LINUS_SEQ = 0xcb13b2d3734ecb4dc8cb134b232c4d3b2dcd3b2d3734ec4d2c8cb134b234dcd3b2d3734ec4d2c8cb134b23734ecb4dcd3b2c4d232c4d2c8cb13b2d3734ecb4dcb232c4d2c8cb13b2d3734ecb4dc8cb134b232c4d3b2dcd3b2d3734ec4d2c8cb134b234dcd3b2d3734ec4d2c8cb134b23734ecb4dcd3b2c4d2c8cb134b2
puts %w[good evil][LINUS_SEQ[num_rounds]]

Save as linus.rb and run with ruby linus.rb

share|improve this answer

C++, The Scientist

This one tries to, with the history of what the majority chose per round in wave (majority() gives the majority's choice on a round), fit a wave to the data, of wavelength 2*period and phase phase. Thus, given 0,1,1,1,0,1,0,1,1,1,0,0,0,1,0 it selects period=3, phase=5 (maxat=={3,5}): its scores become 9 3 11 5 5 3 5 7 9 7 7 7 7 7 7. It loops over all possible periods and if, for that period, the score is higher than for the current maximum, it stores {period,phase} for which that occurred.

It then extrapolates the found wave to the next round and takes the predicted majority.

#include <iostream>
#include <utility>
#include <cstdlib>
#include <cstring>
#if 0
#define DBG(st) {st}
#else
#define DBG(st)
#endif

#define WINDOW (700)

using namespace std;

int majority(const char *r){
    int p=0,a=0,b=0;
    while(true){
        if(r[p]=='1')a++;
        else if(r[p]=='0')b++;
        else break;
        p++;
    }
    return a>b;
}

int main(int argc,char **argv){
    if(argc==1){
        cout<<(rand()%2?"good":"evil")<<endl;
        return 0;
    }
    DBG(cerr<<"WINDOW="<<WINDOW<<endl;)
    int nump,numr;
    nump=strchr(argv[1],',')-argv[1];
    numr=(strlen(argv[1])+1)/(nump+1);
    int fromround=numr-30;
    if(fromround<0)fromround=0;
    int period,r;
    int *wave=new int[WINDOW];
    bool allequal=true;
    DBG(cerr<<"wave: ";)
    for(r=fromround;r<numr;r++){
        wave[r-fromround]=majority(argv[1]+r*(nump+1));
        if(wave[r-fromround]!=wave[0])allequal=false;
        DBG(cerr<<wave[r]<<" ";)
    }
    DBG(cerr<<endl;)
    if(allequal){
        DBG(cerr<<"All equal!"<<endl;)
        if(wave[numr-1]==1)cout<<"evil"<<endl; //choose for minority
        else cout<<"good"<<endl;
        return 0;
    }
    int score,*scores=new int[WINDOW];
    int max=0; //some score will always get above 0, because if some score<0, the inverted wave will be >0.
    int phase,phasemax;
    pair<int,int> maxat(-1,-1); //period, phase
    DBG(cerr<<"scores: ";)
    for(period=1;period<=WINDOW;period++){
        scores[period-1]=0;
        phasemax=-1;
        for(phase=0;phase<2*period;phase++){
            score=0;
            for(r=fromround;r<numr;r++){
                if(wave[r]==1-(r+phase)%(2*period)/period)score++;
                else score--;
            }
            if(score>scores[period-1]){
                scores[period-1]=score;
                phasemax=phase;
            }
        }
        if(scores[period-1]>max){
            max=scores[period-1];
            maxat.first=period;
            maxat.second=phasemax;
        }
        DBG(cerr<<scores[period-1]<<" ";)
    }
    DBG(cerr<<"(max="<<max<<" at {"<<maxat.first<<","<<maxat.second<<"})"<<endl;)
    DBG(cerr<<" max: ("<<numr<<"+"<<maxat.second<<")%(2*"<<maxat.first<<")/"<<maxat.first<<"=="<<((numr+maxat.second)%(2*maxat.first)/maxat.first)<<endl;)
    if(1-(numr+maxat.second)%(2*maxat.first)/maxat.first==1)cout<<"evil"<<endl; //choose for minority
    else cout<<"good"<<endl;
    delete[] wave;
    delete[] scores;
    return 0;
}

Compile with g++ -O3 -std=c++0x -o Scientist Scientist.cpp (you don't need warnings, so no -Wall) and run with Scientist.exe (possibly including the argument of course). If you ask really nicely I can provide you with a Windows executable.

Oh, and don't dare messing with the input format. It'll do strange things otherwise.

EDIT: Apparently, the previous version ran out of time around 600 rounds into the game. This shouldn't do that. Its time consumption is controlled by the #define WINDOW (...) line, more is slower but looks further back.

share|improve this answer
8  
Downloading executables written by sixty+ strangers on the Internet seems like a bad idea. –  Rainbolt Jul 14 at 22:02
    
@Rusher I totally agree. If you do want problems, that's step one in the "for dummies" guide. My offer stands though :) –  tomsmeding Jul 15 at 6:14
2  
Got this one to compile (and compete) fine. –  Rainbolt Jul 19 at 7:47

The BackPacker

Determinates a player that has chosen the matching minority the most yet and chooses his last vote.

package Humans;

public class BackPacker extends Human {
    // toggles weather the BackPacker thinks majority is better vs. minority is better
    private static final boolean goWithMajority = false;

    @Override
    public final String takeSides(String history)  {
        if (history == null || history.equals(""))
            return "evil";
        String[] roundVotes = history.split(",");
        int players = roundVotes[0].length();
        int[] winningPlayers = new int[players];
        for (String nextRound : roundVotes) {
            boolean didGoodWin = didGoodWin(nextRound, players);
            for (int player = 0; player < nextRound.length(); player++) {
                boolean playerVotedGood = nextRound.charAt(player) == '1';
                winningPlayers[player] += didPlayerWin(didGoodWin, playerVotedGood);
            }
        }
        int bestScore = -1;
        for (int nextPlayer : winningPlayers)
            if (bestScore < nextPlayer)
                bestScore = nextPlayer;
        int bestPlayer = 0;
        for (int ii = 0; ii < players; ii++) {
            if (winningPlayers[ii] == bestScore) {
                bestPlayer = ii;
                break;
            }
        }
        if (roundVotes[roundVotes.length - 1].charAt(bestPlayer) == '1')
            return "good";
        return "evil";
    }

    private int didPlayerWin(boolean didGoodWin, boolean playerVotedGood) {
        if(goWithMajority) {
            return ((didGoodWin && playerVotedGood) || (!didGoodWin && !playerVotedGood)) ? 1 : 0;
        } else {
            return ((!didGoodWin && playerVotedGood) || (didGoodWin && !playerVotedGood)) ? 1 : 0;
        }
    }

    private boolean didGoodWin(String round, int players) {
        int good = 0;
        for (char next : round.toCharArray())
            good += next == '1' ? 1 : 0;
        return (good * 2) > players;
    }
}

The CrowdFollower

Determinates a player that has chosen the matching majority the most yet and chooses his last vote.

package Humans;

public class CrowdFollower extends Human {
    // toggles weather the FrontPacker thinks majority is better vs. minority is better
    private static final boolean goWithMajority = true;

    @Override
    public final String takeSides(String history)  {
        if (history == null || history.equals(""))
            return "evil";
        String[] roundVotes = history.split(",");
        int players = roundVotes[0].length();
        int[] winningPlayers = new int[players];
        for (String nextRound : roundVotes) {
            boolean didGoodWin = didGoodWin(nextRound, players);
            for (int player = 0; player < nextRound.length(); player++) {
                boolean playerVotedGood = nextRound.charAt(player) == '1';
                winningPlayers[player] += didPlayerWin(didGoodWin, playerVotedGood);
            }
        }
        int bestScore = -1;
        for (int nextPlayer : winningPlayers)
            if (bestScore < nextPlayer)
                bestScore = nextPlayer;
        int bestPlayer = 0;
        for (int ii = 0; ii < players; ii++) {
            if (winningPlayers[ii] == bestScore) {
                bestPlayer = ii;
                break;
            }
        }
        if (roundVotes[roundVotes.length - 1].charAt(bestPlayer) == '1')
            return "good";
        return "evil";
    }

    private int didPlayerWin(boolean didGoodWin, boolean playerVotedGood) {
        if(goWithMajority) {
            return ((didGoodWin && playerVotedGood) || (!didGoodWin && !playerVotedGood)) ? 1 : 0;
        } else playerVotedGood                return ((!didGoodWin && good) || (didGoodWin && !playerVotedGood)) ? 1 : 0;
        }
    }

    private boolean didGoodWin(String round, int players) {
        int good = 0;
        for (char next : round.toCharArray())
            good += next == '1' ? 1 : 0;
        return (good * 2) > players;
    }
}
share|improve this answer
    
Very clean program! –  Rainbolt Jul 10 at 13:21
    
Whoops, I think I may have copied your program in a different language. –  PyRulez Jul 14 at 0:55
    
@Rusher I updated the code and would like to add this as two entries, one with goWithMajority = true and one where its false. Is that okay, or do I need to add a second BackPacker for this? –  Angelo Neuschitzer Jul 17 at 9:30
    
@AngeloNeuschitzer I edited this post. This way, I won't forget to add both submissions. I suggest you change the really uncreative name I gave it, and maybe add a description to both if you want. –  Rainbolt Jul 17 at 13:03
1  
@Rainbolt I like your FrontPacker better, actually. Lol'd. –  tomsmeding Jul 19 at 18:57

Fortune Teller

This is still work in progress. I haven't tested it yet. I just wanted to see if the OP thinks it breaks the rules or not.

The idea is to simulate the next round by executing all other participants a few times to get a probability of the outcome and act accordingly.

package Humans;

import java.io.File;
import java.io.IOException;
import java.io.UnsupportedEncodingException;
import java.net.JarURLConnection;
import java.net.URL;
import java.net.URLConnection;
import java.net.URLDecoder;
import java.util.ArrayList;
import java.util.Enumeration;
import java.util.jar.JarEntry;
import java.util.jar.JarFile;
import sun.net.www.protocol.file.FileURLConnection;

public class FortuneTeller extends Human {

/**
 * Code from http://stackoverflow.com/a/22462785 Private helper method
 *
 * @param directory The directory to start with
 * @param pckgname The package name to search for. Will be needed for
 * getting the Class object.
 * @param classes if a file isn't loaded but still is in the directory
 * @throws ClassNotFoundException
 */
private static void checkDirectory(File directory, String pckgname,
        ArrayList<Class<?>> classes) throws ClassNotFoundException {
    File tmpDirectory;

    if (directory.exists() && directory.isDirectory()) {
        final String[] files = directory.list();

        for (final String file : files) {
            if (file.endsWith(".class")) {
                try {
                    classes.add(Class.forName(pckgname + '.'
                            + file.substring(0, file.length() - 6)));
                } catch (final NoClassDefFoundError e) {
                // do nothing. this class hasn't been found by the
                    // loader, and we don't care.
                }
            } else if ((tmpDirectory = new File(directory, file))
                    .isDirectory()) {
                checkDirectory(tmpDirectory, pckgname + "." + file, classes);
            }
        }
    }
}

/**
 * Private helper method.
 *
 * @param connection the connection to the jar
 * @param pckgname the package name to search for
 * @param classes the current ArrayList of all classes. This method will
 * simply add new classes.
 * @throws ClassNotFoundException if a file isn't loaded but still is in the
 * jar file
 * @throws IOException if it can't correctly read from the jar file.
 */
private static void checkJarFile(JarURLConnection connection,
        String pckgname, ArrayList<Class<?>> classes)
        throws ClassNotFoundException, IOException {
    final JarFile jarFile = connection.getJarFile();
    final Enumeration<JarEntry> entries = jarFile.entries();
    String name;

    for (JarEntry jarEntry = null; entries.hasMoreElements()
            && ((jarEntry = entries.nextElement()) != null);) {
        name = jarEntry.getName();

        if (name.contains(".class")) {
            name = name.substring(0, name.length() - 6).replace('/', '.');

            if (name.contains(pckgname)) {
                classes.add(Class.forName(name));
            }
        }
    }
}

/**
 * Attempts to list all the classes in the specified package as determined
 * by the context class loader
 *
 * @param pckgname the package name to search
 * @return a list of classes that exist within that package
 * @throws ClassNotFoundException if something went wrong
 */
private static ArrayList<Class<?>> getClassesForPackage(String pckgname)
        throws ClassNotFoundException {
    final ArrayList<Class<?>> classes = new ArrayList<Class<?>>();

    try {
        final ClassLoader cld = Thread.currentThread()
                .getContextClassLoader();

        if (cld == null) {
            throw new ClassNotFoundException("Can't get class loader.");
        }

        final Enumeration<URL> resources = cld.getResources(pckgname
                .replace('.', '/'));
        URLConnection connection;

        for (URL url = null; resources.hasMoreElements()
                && ((url = resources.nextElement()) != null);) {
            try {
                connection = url.openConnection();

                if (connection instanceof JarURLConnection) {
                    checkJarFile((JarURLConnection) connection, pckgname,
                            classes);
                } else if (connection instanceof FileURLConnection) {
                    try {
                        checkDirectory(
                                new File(URLDecoder.decode(url.getPath(),
                                                "UTF-8")), pckgname, classes);
                    } catch (final UnsupportedEncodingException ex) {
                        throw new ClassNotFoundException(
                                pckgname
                                + " does not appear to be a valid package (Unsupported encoding)",
                                ex);
                    }
                } else {
                    throw new ClassNotFoundException(pckgname + " ("
                            + url.getPath()
                            + ") does not appear to be a valid package");
                }
            } catch (final IOException ioex) {
                throw new ClassNotFoundException(
                        "IOException was thrown when trying to get all resources for "
                        + pckgname, ioex);
            }
        }
    } catch (final NullPointerException ex) {
        throw new ClassNotFoundException(
                pckgname
                + " does not appear to be a valid package (Null pointer exception)",
                ex);
    } catch (final IOException ioex) {
        throw new ClassNotFoundException(
                "IOException was thrown when trying to get all resources for "
                + pckgname, ioex);
    }

    return classes;
}

private static boolean isRecursiveCall = false;
private static ArrayList<Class<?>> classes;

static {
    if (classes == null) {
        try {
            classes = getClassesForPackage("Humans");
        } catch (ClassNotFoundException ex) {

        }
    }    
}

private String doThePetyrBaelish() {
    return Math.random() >= 0.5 ? "good" : "evil";
}

@Override
public String takeSides(String history) {
    if (isRecursiveCall) {
        return doThePetyrBaelish();
    }
    isRecursiveCall = true;

    int currentRoundGoodCount = 0;
    float probabilityOfGood = 0;
    int roundCount = 0;
    int voteCount = 0;



    do {
        for (int i = 0; i < classes.size(); i++) {
            try {
                if (classes.get(i).getName() == "Humans.FortuneTeller") {
                    continue;
                }

                Human human = (Human) classes.get(i).newInstance();
                String response = human.takeSides(history);
                switch (response) {
                    case "good":
                        currentRoundGoodCount++;
                        voteCount++;
                        break;
                    case "evil":
                        voteCount++;
                        break;
                    default:
                        break;
                }
            } catch (Exception e) {
            }
        }

        probabilityOfGood = (probabilityOfGood * roundCount
                + (float) currentRoundGoodCount / voteCount) / (roundCount + 1);

        roundCount++;
        currentRoundGoodCount = 0;
        voteCount = 0;

    } while (roundCount < 11);

    isRecursiveCall = false;
    if (probabilityOfGood > .7) {
        return "evil";
    }
    if (probabilityOfGood < .3) {
        return "good";
    }

    return doThePetyrBaelish();
}

}
share|improve this answer
    
If your bot runs all the other bots each turns before answering, won't it take more than 1s to answer? –  plannapus Jul 9 at 12:41
    
@plannapus I'm going to guess the assumption with this bot is that everyone else is going to err on the side of caution and avoid anything close 1 seconds worth of wait. I'm thinking it may be worthwhile submitting and entry that consists of a 0.9 second wait, before returning "good", just to mess with him. Actually, SBoss has beat me to it :D –  scragar Jul 9 at 12:44
    
Yahhh! Then I would have to blacklist that bot in my code. That would be frustrating... Also with different entries in different environments like Python or Perl the reprated loading of the interpreter might just be enough to bring this code above the time limit. –  Andris Jul 9 at 12:55
14  
If someone else does the same thing as this, you get an infinite loop. –  Brilliand Jul 9 at 17:10
2  
The submission timed out. I attached a profiler, and nearly half a second is spent calling some submissions. It at least works though, so congrats for that. –  Rainbolt Jul 14 at 0:57

The Beautiful Mind, Ruby

Makes its decision based on patterns of questionable significance in the bit representation of the last round

require 'prime'

if ARGV.length == 0
    puts ["good", "evil"].sample
else
    last_round = ARGV[0].split(',').last
    puts Prime.prime?(last_round.to_i(2)) ? "good" : "evil"
end

Run like

ruby beautiful-mind.rb
share|improve this answer

Piustitious, Lua

A superstitious program that believes in Signs and Wonders.

history = arg[1]

if history == nil then
    print("good")
else
    local EvilSigns, GoodSigns = 0,0
    local SoulSpace = ""

    for i in string.gmatch(history, "%d+") do
         SoulSpace = SoulSpace .. i 
    end

    if string.match(SoulSpace, "1010011010")  then -- THE NUBMER OF THE BEAST!
        local r = math.random(1000)
        if r <= 666 then print("evil") else print("good") end
    else
        for i in string.gmatch(SoulSpace, "10100") do -- "I'M COMING" - DEVIL
            EvilSigns = EvilSigns + 1
        end
        for i in string.gmatch(SoulSpace, "11010") do -- "ALL IS WELL" - GOD
            GoodSigns = GoodSigns + 1
        end

        if EvilSigns > GoodSigns then 
            print("evil")
        elseif GoodSigns > EvilSigns then
            print("good")
        elseif GoodSigns == EvilSigns then
            local r = math.random(1000)
            if r <= 666 then print("good") else print("evil") end
        end
    end
end

run it with:

lua Piustitious.lua

followed by the input.

share|improve this answer

Code Runner

So, to make things interesting, I created a script to automatically download the code from every posted answer, compile it if necessary, and then run all of the solutions according to the rules. This way, people can check how they are doing. Just save this script to run_all.py (requires BeautifulSoup) and then:

usage:
To get the latest code: 'python run_all.py get'
To run the submissions: 'python run_all.py run <optional num_runs>'

A few things:

  1. If you want to add support for more languages, or alternatively remove support for some, see def submission_type(lang).
  2. Extending the script should be fairly easy, even for languages that require compilation (see CPPSubmission). The language type is grabbed from the meta code tag < !-- language: lang-java -- >, so make sure to add it if you want your code to be run (Remove the extra spaces before and after the <>). UPDATE: There is now some extremely basic inference to try and detect the language if it is not defined.
  3. If your code fails to run at all, or fails to finish within the allotted time, it will be added to blacklist.text and will be removed from future trials automatically. If you fix your code, just remove your entry from the blacklist and re-run get,

Currently supported languages:

 submission_types =  {
    'lang-ruby': RubySubmission,
    'lang-python': PythonSubmission,
    'lang-py': PythonSubmission,
    'lang-java': JavaSubmission,
    'lang-Java': JavaSubmission,
    'lang-javascript': NodeSubmission,
    'lang-cpp': CPPSubmission,
    'lang-c': CSubmission,
    'lang-lua': LuaSubmission,
    'lang-r': RSubmission,
    'lang-fortran': FortranSubmission,
    'lang-bash': BashSubmission
}

Without further ado:

import urllib2
import hashlib
import os
import re
import subprocess
import shutil
import time
import multiprocessing
import tempfile
import sys
from bs4 import BeautifulSoup

__run_java__ = """
public class Run {
    public static void main(String[] args) {
        String input = "";
        Human h = new __REPLACE_ME__();
        if(args.length == 1)
            input = args[0];
        try {
            System.out.println(h.takeSides(input));
        }
        catch(Exception e) {
        }
    }
}
"""

__human_java__ = """
public abstract class Human {
    public abstract String takeSides(String history) throws Exception;
}
"""

class Submission():
    def __init__(self, name, code):
        self.name = name
        self.code = code

    def submissions_dir(self):
        return 'submission'

    def base_name(self):
        return 'run'

    def submission_path(self):
        return os.path.join(self.submissions_dir(), self.name)

    def extension(self):
        return ""

    def save_submission(self):
        self.save_code()

    def full_command(self, input):
        return []

    def full_path(self):
        file_name = "%s.%s" % (self.base_name(), self.extension())
        full_path = os.path.join(self.submission_path(), file_name)
        return full_path

    def save_code(self):    
        if not os.path.exists(self.submission_path()):
            os.makedirs(self.submission_path())

        with open(self.full_path(), 'w') as f:
            f.write(self.code)

    def write_err(self, err):
        with open(self.error_log(), 'w') as f:
            f.write(err)

    def error_log(self):
        return os.path.join(self.submission_path(), 'error.txt')

    def run_submission(self, input):
        command = self.full_command()
        if input is not None:
            command.append(input)
        try:
            output,err,exit_code = run(command,timeout=1)
            if len(err) > 0:
                self.write_err(err)
            return output
        except Exception as e:
            self.write_err(str(e))
            return ""

class CPPSubmission(Submission):
    def bin_path(self):
        return os.path.join(self.submission_path(), self.base_name())

    def save_submission(self):
        self.save_code()
        compile_cmd = ['g++', '-O3', '-std=c++0x', '-o', self.bin_path(), self.full_path()]
        errout = open(self.error_log(), 'w')
        subprocess.call(compile_cmd, stdout=errout, stderr=subprocess.STDOUT)

    def extension(self):
        return 'cpp'

    def full_command(self):
        return [self.bin_path()]

class CSubmission(Submission):
    def bin_path(self):
        return os.path.join(self.submission_path(), self.base_name())

    def save_submission(self):
        self.save_code()
        compile_cmd = ['gcc', '-o', self.bin_path(), self.full_path()]
        errout = open(self.error_log(), 'w')
        subprocess.call(compile_cmd, stdout=errout, stderr=subprocess.STDOUT)

    def extension(self):
        return 'c'

    def full_command(self):
        return [self.bin_path()]

class FortranSubmission(Submission):
    def bin_path(self):
        return os.path.join(self.submission_path(), self.base_name())

    def save_submission(self):
        self.save_code()
        compile_cmd = ['gfortran', '-fno-range-check', '-o', self.bin_path(), self.full_path()]
        errout = open(self.error_log(), 'w')
        subprocess.call(compile_cmd, stdout=errout, stderr=subprocess.STDOUT)

    def extension(self):
        return 'f90'

    def full_command(self):
        return [self.bin_path()]

class JavaSubmission(Submission):   
    def base_name(self):
        class_name = re.search(r'class (\w+) extends', self.code)
        file_name = class_name.group(1)
        return file_name

    def human_base_name(self):
        return 'Human'

    def run_base_name(self):
        return 'Run'

    def full_name(self, base_name):
        return '%s.%s' % (base_name, self.extension())

    def human_path(self):
        return os.path.join(self.submission_path(), self.full_name(self.human_base_name()))

    def run_path(self):
        return os.path.join(self.submission_path(), self.full_name(self.run_base_name()))

    def replace_in_file(self, file_name, str_orig, str_new):
        old_data = open(file_name).read()
        new_data = old_data.replace(str_orig, str_new)

        with open(file_name, 'w') as f:
            f.write(new_data)

    def write_code_to_file(self, code_str, file_name):
        with open(file_name, 'w') as f:
            f.write(code_str)

    def save_submission(self):
        self.save_code()
        self.write_code_to_file(__human_java__, self.human_path())
        self.write_code_to_file(__run_java__, self.run_path())

        self.replace_in_file(self.run_path(), '__REPLACE_ME__', self.base_name())
        self.replace_in_file(self.full_path(), 'package Humans;', '')

        compile_cmd = ['javac', '-cp', self.submission_path(), self.run_path()]
        errout = open(self.error_log(), 'w')
        subprocess.call(compile_cmd, stdout=errout, stderr=subprocess.STDOUT)

    def extension(self):
        return 'java'

    def full_command(self):
        return ['java', '-cp', self.submission_path(), self.run_base_name()]

class PythonSubmission(Submission):
    def full_command(self):
        return ['python', self.full_path()]

    def extension(self):
        return 'py'

class RubySubmission(Submission):
    def full_command(self):
        return ['ruby', self.full_path()]

    def extension(self):
        return 'rb'

class NodeSubmission(Submission):
    def full_command(self):
        return ['node', self.full_path()]

    def extension(self):
        return 'js'

class LuaSubmission(Submission):
    def full_command(self):
        return ['lua', self.full_path()]

    def extension(self):
        return 'lua'

class RSubmission(Submission):
    def full_command(self):
        return ['Rscript', self.full_path()]

    def extension(self):
        return 'R'

class BashSubmission(Submission):
    def full_command(self):
        return [self.full_path()]

    def extension(self):
        return '.sh'

class Scraper():
    def download_page(self, url, use_cache = True, force_cache_update = False):
        file_name = hashlib.sha1(url).hexdigest()

        if not os.path.exists('cache'):
            os.makedirs('cache')

        full_path = os.path.join('cache', file_name)
        file_exists = os.path.isfile(full_path)

        if use_cache and file_exists and not force_cache_update:
            html = open(full_path, 'r').read()
            return html

        opener = urllib2.build_opener()
        opener.addheaders = [('User-agent', 'Mozilla/5.0')]
        response = opener.open(url)
        html = response.read()

        if use_cache:
            f = open(full_path, 'w')
            f.write(html)
            f.close()

        return html

    def parse_post(self, post):
        name = post.find(text=lambda t: len(t.strip()) > 0)
        pre = post.find('pre')
        lang = pre.attrs['class'][0] if pre.has_attr('class') else None
        code = pre.find('code').text
        user = post.find(class_='user-details').find(text=True)
        return {'name':name,'lang':lang,'code':code,'user':user}

    def parse_posts(self, html):
        soup = BeautifulSoup(html)
        # Skip the first post
        posts = soup.find_all(class_ = 'answercell')
        return [self.parse_post(post) for post in posts]

    def get_submissions(self,  page = 1, force_cache_update = False):
        url = "http://codegolf.stackexchange.com/questions/33137/good-versus-evil?page=%i&tab=votes#tab-top" % page
        html = self.download_page(url, use_cache = True, force_cache_update = force_cache_update)
        submissions = self.parse_posts(html)
        return submissions

class Timeout(Exception):
    pass

def run(command, timeout=10):
    proc = subprocess.Popen(command, bufsize=0, stdout=subprocess.PIPE, stderr=subprocess.PIPE)
    poll_seconds = .250
    deadline = time.time()+timeout
    while time.time() < deadline and proc.poll() == None:
        time.sleep(poll_seconds)

    if proc.poll() == None:
        if float(sys.version[:3]) >= 2.6:
            proc.terminate()
        raise Timeout()

    stdout, stderr = proc.communicate()
    return stdout, stderr, proc.returncode


def guess_lang(code):
    if re.search(r'class .* extends Human', code):
        return 'lang-java'
    if re.search(r'import sys', code):
        return 'lang-python'
    if re.search(r'puts', code) and (re.search(r'ARGV', code) or re.search(r'\%w', code)):
        return 'lang-ruby'
    if re.search(r'console\.log', code):
        return 'lang-javascript'
    if re.search(r'program', code) and re.search(r'subroutine', code):
        return 'lang-fortran'
    if re.search(r'@echo off', code):
        return 'lang-bash'
    return None


def submission_type(lang, code):
    submission_types =  {
        'lang-ruby': RubySubmission,
        'lang-python': PythonSubmission,
        'lang-py': PythonSubmission,
        'lang-java': JavaSubmission,
        'lang-Java': JavaSubmission,
        'lang-javascript': NodeSubmission,
        'lang-cpp': CPPSubmission,
        'lang-c': CSubmission,
        'lang-lua': LuaSubmission,
        'lang-r': RSubmission,
        'lang-fortran': FortranSubmission,
        'lang-bash': BashSubmission
    }

    klass = submission_types.get(lang)

    if klass is None:
        lang = guess_lang(code)
        klass = submission_types.get(lang)

    return klass

def instantiate(submission):
    lang = submission['lang']
    code = submission['code']
    name = submission['name']

    klass = submission_type(lang, code)
    if klass is not None:
        instance = klass(name, code)
        return instance
    print "Entry %s invalid - lang not supported: %s" % (name, lang)
    return None

def get_all_instances(force_update):
    scraper = Scraper()

    print 'Scraping Submissions..'

    pages = [1,2,3]
    submissions_by_page = [scraper.get_submissions(page=i, force_cache_update=force_update) for i in pages]
    submissions = [item for sublist in submissions_by_page for item in sublist]

    # Get instances
    raw_instances = [instantiate(s) for s in submissions]
    instances = [i for i in raw_instances if i]

    print "Using %i/%i Submissions" % (len(instances), len(submissions))

    return instances

def save_submissions(instances):
    print 'Saving Submissions..'

    for instance in instances:
        instance.save_submission()

def init_game(save=True, force_update=False):
    instances = get_all_instances(force_update)
    if save:
        save_submissions(instances)
    return instances

def one_run(instances, input):
    valid = {
        'good': 1,
        'evil': 0
    }

    disqualified = []
    results = []

    for instance in instances:
        out = instance.run_submission(input)
        res = out.strip().lower()
        if res not in valid:
            disqualified.append(instance)
        else:
            results.append(valid[res])

    return (results, disqualified)

def get_winner(scores, instances):
    max_value = max(scores)
    max_index = scores.index(max_value)
    instance = instances[max_index]
    return (instance.name, max_value)

def update_scores(results, scores, minority_counts, minority_num):
    for i in range(len(results)):
        if results[i] == minority_num:
            minority_counts[i] += 1
            scores[i] += (minority_counts[i] - 1)
        else:
            minority_counts[i] = 0
            scores[i] += 3

def try_run_game(instances, num_runs = 1000, blacklist = None):
    current_input = None
    minority_str = None
    num_instances = len(instances)
    scores = [0] * num_instances
    minority_counts = [0] * num_instances

    print "Running with %i instances..." % num_instances

    for i in range(num_runs):
        print "Round: %i - Last minority was %s" % (i, minority_str)
        results, disqualified = one_run(instances, current_input)

        if len(disqualified) > 0:
            for instance in disqualified:
                print "Removing %s!" % instance.name
                instances.remove(instance)

                if blacklist is not None:
                    with open(blacklist, 'a') as f:
                        f.write("%s\n" % instance.name)

            return False

        latest_result = "".join(map(str,results))
        current_input = "%s,%s" % (current_input, latest_result)

        minority_num = 1 if results.count(1) < results.count(0) else 0
        minority_str = 'good' if minority_num == 1 else 'evil'

        update_scores(results, scores, minority_counts, minority_num)
        name, score = get_winner(scores, instances)
        print "%s is currently winning with a score of %i" % (name, score)

    print "The winner is %s with a score of %i!!!" % (name, score)
    return True

def find_instance_by_name(instances, name):
    for instance in instances:
        if instance.name == name:
            return instance
    return None

def maybe_add_or_remove_baelish(instances, baelish):
    num_instances = len(instances)

    if num_instances % 2 == 0:
        print 'There are %i instances.' % num_instances
        try:
            instances.remove(baelish)
            print 'Baelish Removed!'
        except:
            instances.append(baelish)
            print 'Baelish Added!'

def remove_blacklisted(blacklist, instances):
    blacklisted = []

    try:
        blacklisted = open(blacklist).readlines()
    except:
        return

    print 'Removing blacklisted entries...'

    for name in blacklisted:
        name = name.strip()
        instance = find_instance_by_name(instances, name)
        if instance is not None:
            print 'Removing %s' % name
            instances.remove(instance)

def run_game(instances, num_runs):
    blacklist = 'blacklist.txt'
    remove_blacklisted(blacklist, instances)

    baelish = find_instance_by_name(instances, 'Petyr Baelish') 
    maybe_add_or_remove_baelish(instances, baelish)

    while not try_run_game(instances, num_runs = num_runs, blacklist = blacklist):
        print "Restarting!"
        maybe_add_or_remove_baelish(instances, baelish)

    print "Done!"

if __name__ == '__main__':
    param = sys.argv[1] if len(sys.argv) >= 2 else None

    if param == 'get':
        instances = init_game(save=True, force_update=True)
    elif param == 'run':
        instances = init_game(save=False, force_update=False)
        num_runs = 50
        if len(sys.argv) == 3:
            num_runs = int(sys.argv[2])
        run_game(instances, num_runs)
    else:
        self_name = os.path.basename(__file__)
        print "usage:"
        print "To get the latest code: 'python %s get'" % self_name
        print "To run the submissions: 'python %s run <optional num_runs>'" % self_name
share|improve this answer
    
Why no Fortran language?? –  Kyle Kanos Jul 16 at 18:01
    
@KyleKanos - I added support for it, will update the code shortly. –  WhatAWorld Jul 16 at 18:17
    
Yay! I (sorta) worked hard on my Fortran submission & Rusher can't get it to work so I'd like someone to get it :) –  Kyle Kanos Jul 16 at 18:19
1  
@Rusher: I agree with PeterTaylor on this one: syntax highlighting as the only suggested edit should be rejected. Edits should be used for substantial corrections, not minor stuff. –  Kyle Kanos Jul 16 at 18:47
1  
You do deserve the rep for this, but since this isn't exactly an answer to the question (and could probably benefit from the community adding stuff for other languages) I think this should technically be a community wiki. –  Martin Büttner Jul 16 at 20:26

The Winchesters

Sam and Dean are good (most of the time).

package Humans;

public class TheWinchesters extends Human {

    @Override
    public String takeSides(String history) throws Exception {
        return Math.random() < 0.1 ? "evil" : "good";
    }

}
share|improve this answer
    
Are you sure 9:1 is the right ratio? Maybe we should do some data mining and get a more precise ratio? –  awashburn Jul 15 at 19:38
    
@awashburn I started watching Supernatural 2 months ago (now stuck in season 9) and 9:1 seems ok to me ;) –  Manu Jul 16 at 9:02

Statistician

public class Statistician extends Human{
    public final String takeSides(String history) { 
        int side = 0;
        String[] hist = history.split(",");
        for(int i=0;i<hist.length;i++){
            for(char c:hist[i].toCharArray()){
                side += c == '1' ? (i + 1) : -(i + 1);
            }
        }
        if(side == 0) side += Math.round(Math.random());
        return side > 0 ? "good" : "evil";
    }
}
share|improve this answer
5  
That second last line is so awesome –  cjfaure Jul 9 at 7:56
4  
@Undeserved Instead of Math.ceil(Math.random()-Math.random()) you can also do just Math.round(Math.random()). –  tomsmeding Jul 9 at 8:04

R, a somewhat Bayesian bot

Use the frequency table for each user as the prior probability of other users output.

args <- commandArgs(TRUE)
if(length(args)!=0){
    history <- do.call(rbind,strsplit(args,","))
    history <- do.call(rbind,strsplit(history,""))
    tabulated <- apply(history,2,function(x)table(factor(x,0:1)))
    result <- names(which.max(table(apply(tabulated, 2, function(x)sample(0:1,1, prob=x)))))
    if(result=="1"){cat("good")}else{cat("evil")}
}else{
    cat("good")
    }

Invoked using Rscript BayesianBot.R followed by the input.

Edit: Just to clarify what this is doing, here is a step by step with the example input:

> args
[1] "11011,00101,11101,11111,00001,11001,11001"
> history #Each player is a column, each round a row
     [,1] [,2] [,3] [,4] [,5]
[1,]    1    1    0    1    1
[2,]    0    0    1    0    1
[3,]    1    1    1    0    1
[4,]    1    1    1    1    1
[5,]    0    0    0    0    1
[6,]    1    1    0    0    1
[7,]    1    1    0    0    1

> tabulated #Tally of each player previous decisions.
  [,1] [,2] [,3] [,4] [,5]
0    2    2    4    5    0
1    5    5    3    2    7

Then the line starting by result<-, for each player, picks randomly either 0 or 1 using this last table as weights (i. e. for player 1 the probability of picking 0 is 2/7th, of picking 1 5/7th, etc.). It picks one outcome for each player/column and finally returns the number that ended being the most common.

share|improve this answer

HAL 9000

#!/usr/bin/env perl
print eval("evil")

Edit : maybe this is more suitable for HAL 9000, but be careful! It is very evil. I recommend cd to empty directory before running it.

#!/usr/bin/env perl
print eval {
    ($_) = grep { -f and !/$0$/ } glob('./*');
    unlink;
    evil
}

This removes one file from cwd for each invocation!

Not so obvious invocation:

In M$

D:\>copy con hal_9000.pl
#!/usr/bin/env perl
print eval("evil")
^Z
        1 file(s) copied.

D:>hal_9000.pl
evil

In *nix

[core1024@testing_pc ~]$ tee hal_9000.pl
#!/usr/bin/env perl
print eval("evil")
# Press C-D here
[core1024@testing_pc ~]$ chmod +x $_
[core1024@testing_pc ~]$ ./$_
evil[core1024@testing_pc ~]$
share|improve this answer
    
You need to provide a command that can be used to run your program. See the "Deliverables" section of the challenge for more information. –  Rainbolt Jul 8 at 20:58
    
@Rusher Done ;) –  core1024 Jul 8 at 21:12

Will of the Majority

import sys
import random

if len(sys.argv)==1:
    print(random.choice(['good','evil']))
else:
    rounds=sys.argv[1].split(',')
    last_round=rounds[-1]
    zeroes=last_round.count('0')
    ones=last_round.count('1')
    if ones>zeroes:
        print('good')
    elif zeroes>ones:
        print('evil')
    elif ones==zeroes:
        print(random.choice(['good','evil']))

Save it as WotM.py, run as python3 WotM.py followed by the input.

A simple program, just to see how it will do. Goes with whatever the majority said last time, or else random.

share|improve this answer
    
You need to provide a command that can be used to run your program. See the "Deliverables" section of the challenge for more information. –  Rainbolt Jul 8 at 20:58
    
Damn it, that makes mine a duplicate. :D Changed mine to minority. –  Martin Büttner Jul 8 at 21:01
    
@Rusher Added the command. That what you were looking for? –  isaacg Jul 8 at 21:05
    
@isaacg Perfect! –  Rainbolt Jul 8 at 21:12
1  
I computed the average ranking from the scores in the scoreboard, and this entry wins by that measure. –  Brilliand Jul 22 at 19:43

Later is Evil, JavaScript (node.js)

Measures the amount of time between executions. If the the time difference is greater than last time, it must be evil. Otherwise, good.

var fs = require('fs'),
currentTime = (new Date).getTime();

try {
    var data = fs.readFileSync('./laterisevil.txt', 'utf8');
} catch (e) { data = '0 0'; } // no file? no problem, let's start out evil at epoch

var parsed = data.match(/(\d+) (\d+)/),
lastTime = +parsed[1],
lastDifference = +parsed[2],
currentDifference = currentTime - lastTime;

fs.writeFileSync('./laterisevil.txt', currentTime + ' ' + currentDifference, 'utf8');
console.log(currentDifference > lastDifference? 'evil' : 'good');

Run with: node laterisevil.js

share|improve this answer

Pattern Finder, Python

Looks for a recurring pattern, and if it can't find one, just goes with the majority.

import sys

if len(sys.argv) == 1: 
    print('good')
    quit()

wins = ''.join(
    map(lambda s: str(int(s.count('1') > s.count('0'))),
        sys.argv[1].split(',')
    )
)

# look for a repeating pattern
accuracy = []

for n in range(1, len(wins)//2+1):
    predicted = wins[:n]*(len(wins)//n)
    actual    = wins[:len(predicted)]
    n_right = 0
    for p, a in zip(predicted, actual):
        n_right += (p == a)
    accuracy.append(n_right/len(predicted))

# if there's a good repeating pattern, use it
if accuracy:
    best = max(accuracy)
    if best > 0.8:
        n = accuracy.index(best)+1
        prediction = wins[:n][(len(wins))%n]
        # good chance of success by going with minority
        if prediction == '1':
            print('evil')
        else:
            print('good')
        quit()

# if there's no good pattern, just go with the majority
if wins.count('1') > wins.count('0'):
    print('good')
else:
    print('evil')

run with

python3 pattern_finder.py
share|improve this answer
1  
I love this code so much, when I run it, it always get 3000 pts, somehow. –  Realdeo Jul 10 at 8:08

The Turncoat

The Turncoat believes that because of the other combatants so far, the majority will alternate after each round between good and evil more often than it stays on the same side. Thus he begins the first round by arbitrarily siding with good, then alternates every round in an attempt to stay on the winning or losing team more often than not.

package Humans;

public class Turncoat extends Human {
    public final String takeSides(String history) {
        String[] hist = history.split(",");

        return (hist.length % 2) == 0 ? "good" : "evil";
    }
}

After writing this, I realized that due to the entries based on statistical analysis, momentum would cause the majority to switch sides less as more rounds have been completed. Hence, the the Lazy Turncoat.

The Lazy Turncoat

The Lazy Turncoat starts off like the Turncoat, but as rounds pass, he gets lazier and lazier to switch to the other side.

package Humans;

public class LazyTurncoat extends Human {
    public final String takeSides(String history) {
        int round = history.length() == 0 ? 0 : history.split(",").length;
        int momentum = 2 + ((round / 100) * 6);
        int choice = round % momentum;
        int between = momentum / 2;

        return choice < between ? "good" : "evil";
    }
}
share|improve this answer
2  
The Lazy Turncoat is great! –  Angelo Neuschitzer Jul 10 at 11:34
    
I'm including both if you don't mind. –  Rainbolt Jul 15 at 2:17
    
Go ahead. I'm curious to see how both of them will do, particularly vs the ones that compile voting statistics. –  jaybz Jul 21 at 6:24
    
@Rainbolt I just noticed a stupid bug with the Turncoat. No need to correct it though. It still works, just not entirely as intended, and even if it isn't too late to fix it, fixing it will just make it behave exactly like one of the newer entries anyway. Feel free to include/exclude if you want. –  jaybz Jul 22 at 9:03

Biographer, Ruby

rounds = ARGV[0].split(',') rescue []

if rounds.length < 10
  choice = 1
else
  outcome_history = ['x',*rounds.map{|r|['0','1'].max_by{|s|r.count s}.tr('01','ab')}]
  player_histories = rounds.map{|r|r.chars.to_a}.transpose.map{ |hist| outcome_history.zip(hist).join }
  predictions = player_histories.map do |history|
    (10).downto(0) do |i|
      i*=2
      lookbehind = history[-i,i]
      @identical_previous_behavior = history.scan(/(?<=#{lookbehind})[10]/)
      break if @identical_previous_behavior.any?
    end
    if @identical_previous_behavior.any?
      (@identical_previous_behavior.count('1')+1).fdiv(@identical_previous_behavior.size+2)
    else
      0.5
    end
  end
  simulations = (1..1000).map do
    votes = predictions.map{ |chance| rand < chance ? 1 : 0 }
    [0,1].max_by { |i| votes.count(i) }
  end
  choice = case simulations.count(1)/10
    when 0..15
      1
    when 16..50
      0
    when 51..84
      1
    when 85..100
      0
  end
end

puts %w[evil good][choice]

My attempt at an almost intelligent entry (an actually intelligent one would require testing against the field). Written in Ruby, so there's a chance this'll be too slow, but on my machine anyway this takes .11 seconds to calculate the last round when there are 40 random players, so I hope it'll work well enough.

save as biographer.rb, run as ruby biographer.rb

The idea is that for each player, it estimates their chances of picking "good" by looking at both their own choices for the last ten rounds, and the overall outcomes, and finding instances in the past where the identical circumstances (their votes + overall outcomes) occurred. It picks the longest lookbehind length, up to 10 rounds, such that there's any precedent, and uses that to create a frequency (adjusted according to Laplace's Law of Succession, so that we're never 100% confident about anyone).

It then runs some simulations and sees how often Good wins. If the simulations turned out mostly the same way, then it's probably going to do well predicting in general so it picks the predicted minority. If it's not confident, it picks the predicted majority.

share|improve this answer
1  
+1 for the lengthy explanation! –  Rainbolt Jul 10 at 21:24

Judas

Judas is a really good person. It's a pity he'll betray the good guys for a few pennies.

package Humans;

public class Judas extends Human {

    private static final String MONEY = ".*?0100110101101111011011100110010101111001.*?";

    public String takeSides(String history) {
       return history != null && history.replace(",","").matches(MONEY) ? "evil" : "good";
    }
}
share|improve this answer
1  
This only ever votes evil if there are enough participants, you may want to remove the , out of history, even more so as Rusher is going to split up the game in groups. –  Angelo Neuschitzer Jul 14 at 7:52
    
I didn't know he was going to split up the game in groups. I actually waited for this question to have enough submissions before posting my answer because of the string size. Thanks for letting me know. –  William Barbosa Jul 14 at 10:47
    
If you know how to pass a 60000 character argument to a process in Windows, let me know. Otherwise, sorry for messing up your entry, and thank you for fixing it! I didn't anticipate receiving so many submissions. –  Rainbolt Jul 14 at 21:51

Alan Shearer

Repeats whatever the person he's sitting next to has just said. If the person turns out to be wrong, he moves on to the next person and repeats what they say instead.

package Humans;

/**
 * Alan Shearer copies someone whilst they're right; if they get predict
 * wrongly then he moves to the next person and copies whatever they say.
 *
 * @author Algy
 * @url http://codegolf.stackexchange.com/questions/33137/good-versus-evil
 */
public class AlanShearer extends Human {

    private char calculateWinner(String round) {
        int good = 0, evil = 0;

        for (int i = 0, L = round.length(); i < L; i++) {
            if (round.charAt(i) == '1') {
                good++;
            } else {
                evil++;
            }
        }

        return (good >= evil) ? '1' : '0';
    }

    /**
     * Take the side of good or evil.
     * @param history The past votes of every player
     * @return A String "good" or "evil
     */
    public String takeSides(String history) {
        String[] parts = history.split(",");
        String lastRound = parts[parts.length() - 1];

        if (parts.length() == 0 || lastRound.length() == 0) {
            return "good";
        } else {
            if (parts.length() == 1) {
                return lastRound.charAt(0) == '1' ? "good" : "evil";
            } else {
                int personToCopy = 0;

                for (int i = 0, L = parts.length(); i < L; i++) {
                    if (parts[i].charAt(personToCopy) != calculateWinner(parts[i])) {
                        personToCopy++;

                        if (personToCopy >= L) {
                            personToCopy = 0;
                        }
                    }
                }
            }

            return lastRound.charAt(personToCopy) == '1' ? "good" : "evil";
        }
    }
}
share|improve this answer
    
You reference a variable called lastRound before you even declare it. Also, you added parentheses to all of your String.length but it isn't a function. Can you get your submission to a point where it will compile? –  Rainbolt Jul 15 at 2:24
    
@Rusher - done :) –  Algy Taylor Jul 15 at 14:25
    
@Algy: lastRound.length is still accessed (in the first if) before lastRound is declared (in that if's else). Please try to compile (and maybe run) your code before submitting it here. –  Paŭlo Ebermann Jul 15 at 18:50
    
@PaŭloEbermann - apologies, I'm not in an environment where I can run it - amendment made, though –  Algy Taylor Jul 16 at 10:11
    
Now you're referencing a variable called "personToCopy" when it's out of scope. I just moved it inside of the else block so it would compile, but I don't know if that's what you wanted. –  Rainbolt Jul 19 at 6:56

Swiss

Always sustains neutrality. Doomed to never win.

package Humans;

/**
 * Never choosing a side, sustaining neutrality
 * @author Fabian
 */
public class Swiss extends Human {   
    public String takeSides(String history) {
        return "neutral" // wtf, how boring is that?
    }
}
share|improve this answer
    
I didn't write this! –  Rainbolt Jul 9 at 19:22
    
That's the irony. Neutrality never wins –  fabigler Jul 9 at 19:23
2  
@Rusher ah I got it now :D –  fabigler Jul 9 at 19:26
    
It doesn't even compile – there is a missing semicolon. –  Paŭlo Ebermann Jul 22 at 19:37

The Fallacious Gambler (Python)

If one side has won majority a number of times in a row, the gambler realizes that the other side is more likely to be the majority next round (right?) and this influence his vote. He aims for the minority, because if he makes it into the minority once he's likely to make it there a number of times (right?) and get a lot of points.

import sys
import random

def whoWon(round):
    return "good" if round.count("1") > round.count("0") else "evil"

if len(sys.argv) == 1:
    print random.choice(["good", "evil"])
else:
    history = sys.argv[1]
    rounds = history.split(",")
    lastWin = whoWon(rounds[-1])
    streakLength = 1
    while streakLength < len(rounds) and whoWon(rounds[-streakLength]) == lastWin:
        streakLength += 1
    lastLoss = ["good", "evil"]
    lastLoss.remove(lastWin)
    lastLoss = lastLoss[0] 
    print lastWin if random.randint(0, streakLength) > 1 else lastLoss  

Usage

For the first round:

python gambler.py

and afterward:

python gambler.py 101,100,001 etc.
share|improve this answer
4  
I like how you seem sure about your code, right? :P –  TopinFrassi Jul 14 at 23:25

Cellular Automaton

This uses conventional rules for Conway's Game of Life to pick a side. First, a 2D grid is created from the previous votes. Then, the "world" is stepped forward one stage, and the total number of living cells remaining is calculated. If this number is greater than half the total number of cells, "good" is chosen. Otherwise, "evil" is chosen.

Please forgive any mistakes, this was smashed out during my lunch hour. ;)

package Humans;

public class CellularAutomaton extends Human {

    private static final String GOOD_TEXT = "good";

    private static final String EVIL_TEXT = "evil";

    private int numRows;

    private int numColumns;

    private int[][] world;

    @Override
    public String takeSides(String history) {
        String side = GOOD_TEXT;

        if (history.isEmpty()) {
            side = Math.random() <= 0.5 ? GOOD_TEXT : EVIL_TEXT;
        }

        else {
            String[] prevVotes = history.split(",");

            numRows = prevVotes.length;

            numColumns = prevVotes[0].length();

            world = new int[numRows][numColumns];

            for (int i = 0; i < numColumns; i++) {
                for (int j = 0; j < numRows; j++) {
                    world[j][i] =
                        Integer.parseInt(Character.toString(prevVotes[j].charAt(i)));
                }
            }

            int totalAlive = 0;
            int total = numRows * numColumns;
            for (int i = 0; i < numColumns; i++) {
                for (int j = 0; j < numRows; j++) {
                    totalAlive += getAlive(world, i, j);
                }
            }
            if (totalAlive < total / 2) {
                side = EVIL_TEXT;
            }
        }

        return side;
    }

    private int getAlive(int[][] world, int i, int j) {
        int livingNeighbors = 0;

        if (i - 1 >= 0) {
            if (j - 1 >= 0) {
                livingNeighbors += world[j - 1][i - 1];
            }
            livingNeighbors += world[j][i - 1];
            if (j + 1 < numRows) {
                livingNeighbors += world[j + 1][i - 1];
            }
        }
        if (j - 1 >= 0) {
            livingNeighbors += world[j - 1][i];
        }
        if (j + 1 < numRows) {
            livingNeighbors += world[j + 1][i];
        }
        if (i + 1 < numColumns) {
            if (j - 1 >= 0) {
                livingNeighbors += world[j - 1][i + 1];
            }
            livingNeighbors += world[j][i + 1];
            if (j + 1 < numRows) {
                livingNeighbors += world[j + 1][i + 1];
            }
        }

        return livingNeighbors > 1 && livingNeighbors < 4 ? 1 : 0;
    }
}
share|improve this answer
    
I removed the print line from the code for testing.. Java entries only need to return good or evil, not print it. –  Rainbolt Jul 19 at 7:02

The Ridge Professor

I hope using libraries is allowed, don't feel like doing this without one =)

The basic idea is to train a ridge regression classifier for each participant on the last rounds, using the 30 results before each round as features. Originally included the last round of results for all players to predict the outcome for each player as well, but that was cutting it rather close for time when the number of participants gets larger (say, 50 or so).

#include <iostream>
#include <string>
#include <algorithm>
#include "Eigen/Dense"

using Eigen::MatrixXf;
using Eigen::VectorXf;
using Eigen::IOFormat;
using std::max;

void regress(MatrixXf &feats, VectorXf &classes, VectorXf &out, float alpha = 1) {
    MatrixXf featstrans = feats.transpose();
    MatrixXf AtA = featstrans * feats;

    out = (AtA + (MatrixXf::Identity(feats.cols(), feats.cols()) * alpha)).inverse() * featstrans * classes;
}

float classify(VectorXf &weights, VectorXf &feats) {
    return weights.transpose() * feats;
}

size_t predict(MatrixXf &train_data, VectorXf &labels, VectorXf &testitem) {
    VectorXf weights;
    regress(train_data, labels, weights);
    return (classify(weights, testitem) > 0 ? 1 : 0);
}

static const int N = 30;
static const int M = 10;
// use up to N previous rounds worth of data to predict next round
// train on all previous rounds available
size_t predict(MatrixXf &data, size_t prev_iters, size_t n_participants) {
    MatrixXf newdata(data.rows(), data.cols() + max(N, M));
    newdata << MatrixXf::Zero(data.rows(), max(N, M)), data;

    size_t n_samples = std::min(500ul, prev_iters);
    if (n_samples > (8 * max(N, M))) {
        n_samples -= max(N,M);
    }
    size_t oldest_sample = prev_iters - n_samples;
    MatrixXf train_data(n_samples, N + M + 1);
    VectorXf testitem(N + M + 1);
    VectorXf labels(n_samples);
    VectorXf averages = newdata.colwise().mean();
    size_t n_expected_good = 0;
    for (size_t i = 0; i < n_participants; ++i) {
        for (size_t iter = oldest_sample; iter < prev_iters; ++iter) {
            train_data.row(iter - oldest_sample) << newdata.row(i).segment<N>(iter + max(N, M) - N)
                                  , averages.segment<M>(iter + max(N, M) - M).transpose()
                                  , 1; 
        }
        testitem.transpose() << newdata.row(i).segment<N>(prev_iters + max(N, M) - N)
                  , averages.segment<M>(prev_iters + max(N, M) - M).transpose()
                  , 1;
        labels = data.row(i).segment(oldest_sample, n_samples);
        n_expected_good += predict(train_data, labels, testitem);
    }
    return n_expected_good;
}


void fill(MatrixXf &data, std::string &params) {
    size_t pos = 0, end = params.size();
    size_t i = 0, j = 0;
    while (pos < end) {
        switch (params[pos]) {
            case ',':
                i = 0;
                ++j;
                break;
            case '1':
                data(i,j) = 1;
                ++i;
                break;
            case '0':
                data(i,j) = -1;
                ++i;
                break;
            default:
                std::cerr << "Error in input string, unexpected " << params[pos] << " found." << std::endl;
                std::exit(1);
                break;
        }
        ++pos;
    }
}

int main(int argc, char **argv) {
    using namespace std;

    if (argc == 1) {
        cout << "evil" << endl;
        std::exit(0);
    }

    string params(argv[1]);
    size_t n_prev_iters = count(params.begin(), params.end(), ',') + 1;
    size_t n_participants = find(params.begin(), params.end(), ',') - params.begin();

    MatrixXf data(n_participants, n_prev_iters);
    fill(data, params);

    size_t n_expected_good = predict(data, n_prev_iters, n_participants);

    if (n_expected_good > n_participants/2) {
        cout << "evil" << endl;
    } else {
        cout << "good" << endl;
    }
}

To Compile

Save the source code in a file called ridge_professor.cc, download the Eigen library and unzip the Eigen folder found inside into the same folder as the source file. Compile with g++ -I. -O3 -ffast-math -o ridge_professor ridge_professor.cc.

To Run

call ridge_professor.exe and supply argument as needed.

Question

Since I can't comment anywhere yet, I'll ask here: doesn't the argument size limit on windows make it impossible to call the resulting binaries with the entire history at a few hundred turns? I thought you can't have more than ~9000 characters in the argument...

share|improve this answer
    
Thank you for drawing my attention to this. I'll figure out some way to make it work if it doesn't already work fine in Java. If Java can't do it, research tells me that C++ can, and I'll take the opportunity to relearn C++. I'll be back shortly with test results. –  Rainbolt Jul 11 at 19:04
    
As it turns out, Java is not subject the the limitations of the command prompt. It appears that only commands larger than 32k cause a problem. Here is my proof (I wrote it myself): docs.google.com/document/d/… . Again, I really appreciate you bringing this up before trials start tomorrow. –  Rainbolt Jul 11 at 19:47
    
@Rusher There are already 57 bots and you plan on each run being composed of 1000 rounds. That would make your string 57k characters (therefore >32k), wouldn't it? –  plannapus Jul 12 at 9:03
1  
@Rusher I think it may be better to extend the timeline by another week and ask participants to change their programs to read stdin instead of using an argument string. Would be trivial for most programs to change –  dgel Jul 13 at 9:40
    
@dgel The timeline for the challenge is infinitely long, but I don't want to change the rules in a way that everyone has to rewrite their answer. I'm pretty sure that the rule I added last night will only screw over a single submission, and I plan on helping that person if he ever gets his program to a point where it compiles. –  Rainbolt Jul 13 at 15:51

Crowley

Because the Winchesters are much less interesting without this fellow. He obviously sides with evil...unless it is needed to take care of a bigger evil.

package Humans;

public class Crowley extends Human {
public String takeSides(String history) {
    int gd = 0, j=history.length(), comma=0, c=0, z=0;
    while(comma < 2 && j>0)   {
        j--;
        z++;
        if (history.charAt(j) == ',') {
            comma++;
            if(c> z/2) {gd++;}
            z=0;
            c=0;
        } else if (history.charAt(j)=='1') {
            c++;
        } else {
        }
    }
    if(gd == 0){
        return "good";
    } else {
        return "evil";
    }
}}

I look at the last two turns (0 commas so far and 1 comma so far) and if both of them let evil win, I vote good. Otherwise I vote evil.

share|improve this answer
    
Do I get this right? You look at the last turn and if less than 50% are "good" votes you side with "good" else with evil? (Out of curiosity: Do you prefer cryptic variable names or is it an accident?) –  Angelo Neuschitzer Jul 17 at 8:10
1  
@AngeloNeuschitzer I look at the last two turns (0 commas so far and 1 comma so far) and if both of them let evil win, I vote good. Otherwise I vote evil. I prefer variable names that are short to type if the code is short enough the purpose of the code will not get confused. I'm not a professional programmer and this was the first time I've programmed in java or something someone else saw the code for in 6.5 years. I wrote this to refresh my memory.(TLDR they aren't cryptic to me and I'm the only one I usually code for.) –  kaine Jul 17 at 20:45
    
For clarity... Crowley started out as a human so it was intentional he starts good...Did not expect him to stay good for all rounds though... damn –  kaine Jul 25 at 19:45

C++, Bookkeeper

This one tries to do some smart pattern-matching. First of all, it does random moves while logging its moves in the file Bookkeeper.txt. When it has successfully determined which of the players he is, he saves that in the file instead, and afterwards does smart things.

These smart things are trying to pattern match the last WINDOW moves of each player, excluding itself. Near the top, WINDOW is defined to be 20. The pattern can be at most WINDOW/2 and at most (number of rounds)/2 long and must fill the entire WINDOW without faults. If it finds a pattern for a player, it predicts for that player what its next move will probably be; if it can't find a pattern, it assumes the player will repeat its last move.

Near the bottom of the file, it looks at the number of "goods" in the prediction and checks whether it can make sure it chooses a minority. If it can, it does; if it cannot (numgood==nump/2), it goes random.

#include <iostream>
#include <fstream>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <sys/time.h>
#if 0
#define DBG(st) {st}
#else
#define DBG(st)
#endif

#define WINDOW (20)

#define GETARGV1(rnd,plr) (argv[1][(rnd)*(nump+1)+(plr)])
#define MIN(a,b) ((a)<(b)?(a):(b))
#define FILENAME "Bookkeeper.txt"
#define MARK_IDENT "identification"
#define MARK_PLAYING "playing"

using namespace std;

int main(int argc,char **argv){
    struct timeval tv;
    gettimeofday(&tv,NULL);
    srand(1e6*tv.tv_sec+tv.tv_usec);
    int choice,nump,numr,i,rnd;
    if(argc==1){
        ofstream out(FILENAME);
        choice=rand()%2;
        cout<<(choice?"good":"evil")<<endl;
        out<<MARK_IDENT "\n"<<choice<<endl;
        out.close();
        return 0;
    }
    for(nump=0;argv[1][nump]=='1'||argv[1][nump]=='0';nump++);
    numr=(strlen(argv[1])+1)/(nump+1);
    ifstream in(FILENAME);
    string line;
    getline(in,line);
    if(line==MARK_IDENT){
        bool *ruledout=new bool[nump]();
        rnd=0;
        while(true){
            getline(in,line);
            if(!in.good()||line.size()==0)break;
            choice=line[0]-'0';
            for(i=0;i<nump;i++){
                if(GETARGV1(rnd,i)-'0'!=choice)ruledout[i]=true;
            }
            DBG(
                cerr<<"After round "<<rnd<<" (choice "<<choice<<"): ruledout=";
                for(i=0;i<nump;i++)cerr<<ruledout[i];
                cerr<<endl;
            )
            rnd++;
        }
        in.close();
        choice=-1;
        for(i=0;i<nump;i++){
            if(!ruledout[i]){
                if(choice==-1)choice=i;
                else break;
            }
        }
        delete[] ruledout;
        if(i==nump){
            ofstream out(FILENAME);
            out<<MARK_PLAYING<<'\n'<<choice<<endl;
            out.close();
            choice=rand()%2;
            cout<<(choice?"good":"evil")<<endl;
        } else {
            ofstream out(FILENAME,ofstream::out|ofstream::app);
            choice=rand()%2;
            cout<<(choice?"good":"evil")<<endl;
            out<<choice<<endl;
            out.close();
        }
    } else if(line==MARK_PLAYING){
        int iam,p,patternlen,patternloop,numgood;
        bool fail;
        getline(in,line);
        in.close();
        iam=0;
        for(i=0;i<(int)line.size();i++)iam=10*iam+line[i]-'0';
        patternlen=MIN(WINDOW/2,numr/2);
        numgood=0;
        bool *pattern=new bool[patternlen];
        bool *predicted=new bool[nump];
        for(p=0;p<nump;p++){
            if(iam==p)continue; //we don't do ourselves
            for(i=0;i<patternlen;i++){
                pattern[i]=GETARGV1(numr-1-i,p)-'0';
            }
            patternloop=1;
            fail=true;
            while(patternloop<=patternlen){
                fail=false;
                for(i=patternloop;i<WINDOW&&i<numr;i++){
                    if(GETARGV1(numr-1-i,p)-'0'!=pattern[i%patternloop]){
                        fail=true;
                        break;
                    }
                }
                if(!fail)break;
                patternloop++;
            }
            if(!fail){
                predicted[p]=pattern[patternloop-1];
            } else {
                predicted[p]=pattern[0]; //could not find a pattern, so just take the last one
            }
            numgood+=predicted[p];
            DBG(cerr<<"p"<<p<<": fail="<<fail<<" patternlen="<<patternlen<<" patternloop="<<patternloop<<" predicted["<<p<<"]="<<predicted[p]<<endl;)
        }
        delete[] predicted;
        delete[] pattern;
        //now we go for the minority.
        //if more than half of the other players will choose good, we can choose evil to be part of the minority:
        if(numgood>nump/2)cout<<"evil"<<endl;
        //if exactly half of the other players choose good, we get the majority by defenition, which sucks:
        if(numgood==nump/2)cout<<(rand()%2?"good":"evil")<<endl;
        //if less than half of the other players will choose evil, we can choose good to be part of the minority:
        if(numgood<nump/2)cout<<"good"<<endl;
    }
    return 0;
}

Compile with g++ -O3 -std=c++0x -o Bookkeeper Bookkeeper.cpp (you don't need warnings, so no -Wall) and run with Bookkeeper.exe (possibly including the argument of course). If you ask really nicely I can provide you with a Windows executable.

share|improve this answer
2  
+1 for figuring out which are your own votes. –  Andris Jul 16 at 6:43
    
I downloaded mingw 4.5.2, executed the command in your answer, and got Bookkeeper.cpp: In function 'int main(int, char**)': Bookkeeper.cpp:25:35: error: 'srand' was not declared in this scope Bookkeeper.cpp:29:21: error: 'rand' was not declared in this scope Bookkeeper.cpp:70:25: error: 'rand' was not declared in this scope Bookkeeper.cpp:74:25: error: 'rand' was not declared in this scope Bookkeeper.cpp:122:40: error: 'rand' was not declared in this scope –  Rainbolt Jul 19 at 7:45
    
@Rainbolt Sorry, you have to add the line #include <cstdlib> before everything. That'll work. — I edited the post. –  tomsmeding Jul 19 at 7:47
2  
I don't get it. I ran this entry three times in a row and it threw an exception on round 2. So I went to command line to see what the error actually was, and it ran fine. I went back to Java. It runs fine. I am puzzled now. –  Rainbolt Jul 19 at 7:57
    
@Rainbolt Cool! I am curious as to the results –  tomsmeding Jul 19 at 7:59

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.