title: Formatting a Lisp-like Syntax

text:
# Question
Title: Formatting a Lisp-like Syntax
# Background

(Based on a true, heart-wrenching story)

In my time, I've played around with Lisp and similar languages often. I've written with them, ran them, interpreted them, designed them, and made machines write with them for me... And if there is one thing that bothers me, it's seeing Lisp that does not comply with my specific formatting style.

Unfortunately, some text editors (*cough* XCode *cough*) tend to strip my beautiful tabs and spaces whenever code is copied and pasted... Take this beautifully spaced Lisp-like syntax:

```
(A
    (B
        (C)
        (D))
    (E))

```

*(Where `ABCDE` are arbitrary functions)*

*SOME* text editors butcher this lovely code to the following end:

```
(A
(B
(C)
(D))
(E))

```

What a mess! That's not readable!

Help me out, here?

# The Challenge

Your goal in this challenge is to take a series of functions separated by newlines in a format described below and return a more beautiful arrangement that highlights readability and elegance.

# The Input

We define a function `F` of arity `N` arguments as a construct similar to the following:

```
(F (G1 ...) (G2 ...) (G3 ...) ... (GN ...))

```

where `G1, G2, ..., GN` are all functions in and of themselves. An arity `0` function `A` is simply `(A)`, while an arity `2` function `B` is of the form `(B (...) (...))`

Your code should take input as a series of functions with a single newline before every function's leading parenthesis (except for the first function). The example above is valid input.

You may assume:

* The parentheses are balanced.
* A function will never have to be indented more than 250 times.
* EVERY function is surrounded by parentheses: `()`
* A function's name will only contain printable ASCII characters.
* A function's name will never contain parentheses or spaces.
* There is an optional trailing newline on input.

# The Output

Your code should output the **same** set of functions, where the only changes made are the additions of spaces or tabs before the leading parentheses of functions. Output should comply with the following rules:

* The first function (and later top-level functions) given should have no preceding spaces
* An argument to a function's horizontal location is exactly one tab to the right of that function's horizontal location.
* A tab is implementation-defined, but must be at least 3 spaces.
* You may optionally print a maximum of two spaces after each line.

# Rules

# Examples

*Input:*

```
(A
(B
(C)
(D))
(E))

```

*Output:*

```
(A
    (B
        (C)
        (D))
    (E))

```

*Input:*

```
(!@#$%^&*
(asdfghjklm
(this_string_is_particularly_long
(...))
(123456789)))
(THIS_IS_TOP_LEVEL_AGAIN
(HERE'S_AN_ARGUMENT))

```

*Output:*

```
(!@#$%^&*
    (asdfghjklm
        (this_string_is_particularly_long
            (...))
        (123456789)))
(THIS_IS_TOP_LEVEL_AGAIN
    (HERE'S_AN_ARGUMENT))

```

*Input:*

```
(-:0
(*:0
(%:0
(Arg:6)
(Write:0
(Read:0
(Arg:30))
(Write:0
(Const:-6)
(Arg:10))))
(%:0
(Const:9)
(/:0
(Const:-13)
(%:0
(Arg:14)
(Arg:0)))))
(WriteArg:22
(-:0
(Const:45)
(?:0
(Arg:3)
(Arg:22)
(Arg:0)))))

```

*Output:*

```
(-:0
    (*:0
        (%:0
            (Arg:6)
            (Write:0
                (Read:0
                    (Arg:30))
                (Write:0
                    (Const:-6)
                    (Arg:10))))
        (%:0
            (Const:9)
            (/:0
                (Const:-13)
                (%:0
                    (Arg:14)
                    (Arg:0)))))
    (WriteArg:22
        (-:0
            (Const:45)
            (?:0
                (Arg:3)
                (Arg:22)
                (Arg:0)))))

```

# Answer
> 9 votes
# Pyth, 24 20 19 18 bytes

```
FN.z+*ZC9N~Z-1/N\)

```

Increments a counter for every line, counts total number of closing parentheses encountered so far, and subtracts it from the counter. Then we indent by `counter` tabs.

# Answer
> 9 votes
# Common Lisp - ~~486~~ 414 bytes (Rube Goldberg version)

```
(labels((p(x d)(or(when(listp x)(#2=princ #\()(p(car x)d)(incf d)(dolist(a(cdr x))(format t"~%~v{   ~}"d'(t))(p a d))(#2# #\)))(#2# x))))(let((i(make-string-input-stream(with-output-to-string(o)(#1=ignore-errors(do(b c)(())(if(member(setq c(read-char))'(#\( #\) #\  #\tab #\newline):test'char=)(progn(when b(prin1(coerce(reverse b)'string)o))(#2# c o)(setq b()))(push c b))))))))(#1#(do()(())(p(read i)0)(terpri)))))

```

# Approach

Instead of doing like everybody else and count parentheses by hand, let's invoke the Lisp reader and do it *The Right Way* :-)

* Read from input stream and write to a *temporary* output stream.
* While doing so, aggregate characters different from `(`, `)` or whitespace as strings.
* The intermediate output is used to build a string, which contains syntactically well-formed Common-Lisp forms: nested lists of strings.
* Using that string as an input stream, call the standard `read` function to build actual lists.
* Call `p` on each of those lists, which recursively write them to the standard output with the requested format. In particular, strings are printed unquoted.

As a consequence of this approach:

1. There are less restrictions on the input format: you can read arbitrarly formatted inputs, not just "one function per line" (ugh).
2. Also, if the input is not well-formed, an error will be signaled.
3. Finally, the pretty-printing function is well decoupled from parsing: you can easily switch to another way of pretty-printing S-expressions (and you should, if you value your vertical space).

# Example

Reading from a file, using this wrapper:

```
(with-open-file (*standard-input* #P"path/to/example/file")
    ...)

```

Here is the result:

```
(!@#$%^&*
    (asdfghjklm
        (this_string_is_particularly_long
            (...))
        (123456789)))
(THIS_IS_TOP_LEVEL_AGAIN
    (HERE'S_AN_ARGUMENT))
(-:0
    (*:0
        (%:0
            (Arg:6)
            (Write:0
                (Read:0
                    (Arg:30))
                (Write:0
                    (Const:-6)
                    (Arg:10))))
        (%:0
            (Const:9)
            (/:0
                (Const:-13)
                (%:0
                    (Arg:14)
                    (Arg:0)))))
    (WriteArg:22
        (-:0
            (Const:45)
            (?:0
                (Arg:3)
                (Arg:22)
                (Arg:0)))))

```

*(it seems that tabs are converted to spaces here)*

# Pretty-printed (golfed version)

Contrary to the safer original version we expect input to be valid.

```
(labels ((p (x d)
           (or
            (when (listp x)
              (princ #\()
              (p (car x) d)
              (incf d)
              (dolist (a (cdr x)) (format t "~%~v{  ~}" d '(t)) (p a d))
              (princ #\)))
            (princ x))))
  (let ((i
         (make-string-input-stream
          (with-output-to-string (o)
            (ignore-errors
             (do (b
                  c)
                 (nil)
               (if (member (setq c (read-char)) '(#\( #\) #\  #\tab #\newline)
                           :test 'char=)
                   (progn
                    (when b (prin1 (coerce (reverse b) 'string) o))
                    (princ c o)
                    (setq b nil))
                   (push c b))))))))
    (ignore-errors (do () (nil) (p (read i) 0) (terpri)))))

```

# Answer
> 7 votes
# Retina, ~~89~~ 83 bytes

```
s`.+
$0<tab>$0
s`(?<=<tab>.*).
<tab>
+ms`^((\()|(?<-2>\))|[^)])+^(?=\(.*^((?<-2><tab>)+))
$0$3
<tab>+$
<empty>

```

Where `<tab>` stands for an actual tab character (0x09) and `<empty>` stands for an empty line. After making those replacements, you can run the above code with the `-s` flag. However, I'm not counting that flag, because you could also just put each line in its own source file, in which case the 7 newlines would be replaced by 7 penalty bytes for the additional source files.

This is a full program, taking input on STDIN and printing the result to STDOUT.

## Explanation

Every pair of lines defines a regex substitution. The basic idea is to make use of .NET's balancing groups to count the current depth up to a given `(`, and then insert that many tabs before that `(`.

```
s`.+
$0<tab>$0

```

First, we prepare the input. We can't really write back a conditional number of tabs, if we can't find them somewhere in the input string to capture them. So we start by duplicating the entire input, separated by a tab. Note that the `s`` just activates the single-line (or "dot-all") modifier, which ensures that the `.` also matches newlines.

```
s`(?<=<tab>.*).
<tab>

```

Now we turn every character after that tab into a tab as well. This gives us a sufficient amount of tabs at the end of the string, without modifying the original string so far.

```
+ms`^((\()|(?<-2>\))|[^)])+^(?=\(.*^((?<-2><tab>)+))
$0$3

```

This is the meat of the solution. The `m` and `s` activate multi-line mode (so that `^` matches the beginnings of lines) and single-line mode. The `+` tells Retina to keep repeating this substitution until the output stops changing (in this case, that means until the pattern no longer matches the string).

The pattern itself matches a prefix of the input up to an unprocessed `(` (that is, a `(` that doesn't have any tabs before it, but should). At the same time it determines the depth of the prefix with balancing groups, such that the height of stack `2` will correspond to the current depth, and therefore to number of tabs we need to append. That is this part:

```
((\()|(?<-2>\))|[^)])+

```

It either matches a `(`, pushing it onto the `2` stack, or it matches a `)`, popping the last capturing from the `2` stack, or it matches something else and leaves the stack untouched. Since the parentheses are guaranteed to be balanced we don't need to worry about trying to pop from an empty stack.

After we've gone through the string like this and found an unprocessed `(` to stop at, the lookahead then skips ahead to the end of the string, and captures tabs into group `3` while popping from the `2` stack until its empty:

```
(?=\(.*^((?<-2><tab>)+))

```

By using a `+` in there, we ensure that the pattern only matches anything if at least one tab should be inserted into the match - this avoids an infinite loop when there are multiple root-level functions.

```
<tab>+$
<empty>

```

Lastly, we just get rid of those helper tabs at the end of the string to clean up the result.

# Answer
> 6 votes
# C: ~~95~~ 94 characters

It's not very golfed yet, and from the question I'm unsure whether tabs are acceptable, which is what I use here.

```
i,j;main(c){for(;putchar(c=getchar()),c+1;i+=c==40,i-=c==41)if(c==10)for(j=i;j--;putchar(9));}

```

Ungolfed:

```
i,j;
main(c){
  for(
    ;
    putchar(c=getchar()),
    c+1;
    i+=c==40,
    i-=c==41
  )
    if(c==10)
      for(
        j=i;
        j--;
        putchar(9)
      );
}

```

Edit: Made it so that it quits on EOF.

# Answer
> 5 votes
# Julia, ~~103~~ ~~99~~ ~~97~~ ~~94~~ 88 bytes

```
p->(i=j=0;for l=split(p,"\n") i+=1;println("\t"^abs(i-j-1)*l);j+=count(i->i=='\)',l)end)

```

This defines an unnamed function that accepts a string and prints the indented version. To call it, give it a name, e.g. `f=p->...`. Note that the input must be a valid Julia string, so dollar signs (`$`) must be escaped.

Ungolfed + explanation:

```
function f(p)
    # Set counters for the line number and the number of close parens
    i = j = 0

    # Loop over each line of the program
    for l in split(p, "\n")
        # Increment the line number
        i += 1

        # Print the program line with |i-j-1| tabs
        println("\t"^abs(i-j-1) * l)

        # Count the number of close parens on this line
        j += count(i -> i == '\)', l)
    end
end

```

Example, pretending each set of four spaces is a tab:

```
julia> f("(A
(B
(C)
(D))
(E))")

(A
    (B
        (C)
        (D))
    (E))

```

Any suggestions are more than welcome!

# Answer
> 4 votes
# Haskell, ~~83~~ 81

```
unlines.(scanl(\n s->drop(sum[1|')'<-s])$n++['\t'|'('<-s])"">>=zipWith(++)).lines

```

a very points free solution.

# Answer
> 3 votes
# Perl, 41

```
$_="\t"x($i-$j).$_;$i+=y/(/(/;$j+=y/)/)/

```

`40` characters `+1` for `-p`.

Run with:

```
cat input.txt | perl -pe'$_="\t"x($i-$j).$_;$i+=y/(/(/;$j+=y/)/)/'

```

# Answer
> 3 votes
# Python 2 - ~~88~~ 78 Bytes

Fairly straightforward (and not very short) solution:

```
l=0
for x in raw_input().split():g=x.count;d=l*'\t'+x;l+=g("(")-g(")");print d

```

# Answer
> 2 votes
# CJam, 20 bytes

```
r{_')e=NU)@-:U9c*r}h

```

Try it online in the CJam interpreter.

### How it works

```
r                    e# Read a whitespace-separated token R from STDIN.
{                 }h e# Do, while R is truthy:
  _')e=              e#   Push C, the number of right parentheses in R.
       NU            e#   Push a linefeed and U (initially 0).
         )@-         e#   Compute U + 1 - C.
            :U       e#   Save in U.
              9c*    e#   Push a string of U tabulators.
                 r   e#   Read a whitespace-separated token R from STDIN.

```

---
Tags: code-golf, string, whitespace, balanced-string, syntax
---


# Question
Title: Code Bots 3: Parallel Programming Antipatterns
**Welcome back!** I'm excited to present the 3rd CodeBots challenge. This one has been a long time in the making. This challenge will be split up in 3 sections: the short version, the long version, and additional details.

# The Short Version

Each competitor will write a 24-command program. These bots will move around the world and copy their code into other bots, while trying to prevent other bots to do the same. One of the possible commands is the no-op `Flag`. If a bot has more of your `Flag` than any other bot's `Flag`, you get a point. You win by having the most points.

All of the above was true for the past two challenges. This time around, bots will be able to run multiple lines of code at the same time.

# The Long Version

## The API

Every bot will have exactly 24 lines, where each line is in the following format:

```
$label command parameters //comments

```

Labels and comments are optional, and each command has a different number of parameters. Everything is case-insensitive.

### Parameters

Parameters are typed, and can be in the following formats:

1. A value from 0 to 23.
2. A variable: `A`, `B`, `C`, `D`
3. A value using addition: `A+3` or `2+C`
4. A line of code, which is designated using the `#` sign (`#4` would represent the 5th line, while `#C+2` would represent the line calculated by `C+2`).
5. You can use a `$label` instead of designating a line of code.
6. Your opponent's variable or line of code, designated by `*`. Your opponent is the bot in the square that you are facing. (`*B` represents your opponent's `B` value, while `*#9` represents your opponent's 10th line). If there is nobody in that square, the command is not executed.

### Commands

**Move V**

Moves the bot `North+(V*90 degrees clockwise)`. Movement does not change direction.

**Turn V**

Turns the bot `V*90 degrees` clockwise.

**Copy V W**

Copies whatever is in `V` into `W`. If `V` is a line number, then `W` has to be a line number. If `V` is a variable or value, then `W` must be a variable.

**Flag**

Does nothing.

**Start V**

Starts a new thread attached to the variable `V`. Immediately, and on each future turn, the thread will execute the command on line `V`.

If `V` is already attached to a thread, then this command is a no-op. If `V` is an opponent's variable, then the opponent will start a thread attached to that variable.

**Stop V**

Stops the thread attached to the variable `V` at the end of this turn.

**Lock V**

Prevent the line or variable `V` from being used in *any way* except by the thread that called `Lock`. A subsequent call to `Lock` by the same thread unlocks `V`. Locks cannot be called on opponent's variables or lines.

**If Cond V W**

This will test `Cond`. If the condition is true, then it will move the thread pointer to the line number `V`, otherwise to the line number `W`. That line will then be immediately executed.

Conditionals can be `X=Y`, `X<Y`, `!X`, or `?X`:

1. `X=Y` tests whether two lines are of the same type and from the same bot, or you test whether two values equal the same amount.
2. `X<Y` tests whether the value of `X` is less than `Y`.
3. `!X` tests whether the variable or line `X` is locked (returns true if locked)
4. `?X` tests whether a given variable has a thread attached to it

# Additional Details

## Multi-threaded interactions

Actions of the same type are executed at the same time. Actions are executed in the following order:

1. Lock. If several threads attempt to lock a variable, they will all fail. If a thread is unlocking a variable while another is attempting to lock it, the variable will remain unlocked.
2. Start. If several threads attempt to start a thread on a variable, it will count as a single start.
3. Copy. If two threads both copy to the same variable, the variable will end up as a random value. If they both copy to the same line, neither will work. If a thread copies to the same variable another thread is copying from, then the latter thread will copy a random value. If two threads are both copying from the same variable, they will both work fine.
4. If. All conditionals will be tested simultaneously, and then the thread variables will be updated after. Executing an `If` can cause an action with a higher priority to be added. Actions with higher priority will be executed before moving on past the `If`, while actions with a lower priority will execute after the `If`.
5. Move. Multiple moves on the same bot will move the bot the sum of all of the moves. If multiple bots would end up in the same spot, they will be returned to their starting spot.
6. Turn. Multiple turns on the same bot will sum.
7. Stop. Multiple stop commands on the same variable will count as a single stop.

## Other details

Your initial thread starts attached to the `D` variable

Recursing with an `If` (having an `If` statement pointed to itself) will cause your bot to do nothing

If a thread is stopped after locking, those locks will be unlocked

Actions to use a locked variable or line will do nothing.

If a bot is shorter than 24 lines, remaining lines will be filled with `Flag`

Performing a write on a variable that is also attached to a starting thread will actually have the thread start its execution on the new value as the thread starts the following turn.

Bots are placed in a toroidal world in the following pattern:

```
B...B...B...
..B...B...B.
B...B...B...

```

I have added several sample bots that are commented as a language reference.

The controller is located here. I've worked a long time on it, but it probably still has bugs. When the spec and the controller contradict, the spec is correct.

## Scoreboard

```
1. 771  LockedScannerBot
2. 297  CopyAndSelfFlag
3. 289  DoubleTapBot
4. 197  ThreadCutterBot
5. 191  TripleThread
6. 180  ThickShelled
7. 155  Attacker
8. 99   RandomMover
9. 90   BananaBot
10. 56  LockedStationaryDoubleTap

```

# Answer
> 3 votes
# Locked Scanner Bot

Scans the enemy as fast as possible and replaces the lines with flags.

```
    Lock D
    Copy $a A
    Start A
    Copy $b B
    Start B

$d  Lock $d0
    Lock $d1
$d0 Copy $flag *#C+1
$d1 If 1=1 $d0 $d0

$a  Lock A
    Lock $a0
    Lock $a1
    Lock $a2
$a0 Copy $flag *#C
$a1 Copy C+2 C
$a2 If !*#C $a1 $a0

$b  Lock B
    Lock $b0
    Lock $b1
    Lock $b2
$b0 Move C
$b1 Turn 1
$b2 If 1=1 $b0 $b0

$flag Flag

```

# Answer
> 3 votes
## DoubleTapBot

This bot has 3 threads : One for moving (A), The two others for flagging (B and D). B flag 1/2 turn, D flag 1/3 turn. So some turn, he will double flag the opponent :).

I assume that C will return to 0 if it exceed 23.

It shoudl be pretty safe if it have some turn to prepare itself (8 turn), as he will always keep at least 2 threads (A & B) running normally.

I can't try it at the moment, so I'll do the test when I'll be back Home :)

```
Lock D          //Thread D locks itself
Copy 6 A        //Thread A will start line 6
Start A
Copy 13 B       //Thread B will start line 13
Start B
Copy 20 D       //Moving Thread D to an other part of the program
Lock A          //Thread A locks itself and the line it will be using
Lock #10
Lock #11
Lock #12
Move C          //Move in a pseudo random direction
Turn 1      //always turn to the right
If 1=1 #10 #10  //return to Move C
Lock B          //Thread B locks itself and the line it will be using
Lock #13
Lock #14
Copy #18 *#C    //Copy a flag to the Cth line of the opponent
If 1=1 #16 #16  //jump back to the copy
Flag
Flag
Copy C+1 C      //Increment C
Copy #19 *#C+1  //Copy a flag to the Cth+1 line of the opponent
If 1=1 #20 #20  //jump back to the increment
Flag

```

# Answer
> 2 votes
# Locked Stationary Double Tap

Inspired by @Katenkyo's DoubleTapBot, this one gives up a couple of flags and any hope of movement in return for completely locking down its own threads so it can't ever be reprogrammed. It is, however, still succeptible to having enemy flags written to non-looping code areas.

```
Lock $flag              // lock the only flag line, super important!
Lock D                  // lock thread D
Copy 10 A
Start A                 // start thread A at $Astart
Copy 17 B
Start B                 // start thread B at $Bstart
Lock $D1                // lock thread D lines
Lock $D2                // thread D should be safe on turn 8
$D1 Turn C              // Spin in place, once every 2 turns
$D2 If 0=0 $D1 $D1      // thread D loop
$Astart Lock A          // thread A starts here, locks itself
Lock $A1                // lock thread A lines
Lock $A2
Lock $A3                // thread A should be safe on turn 7
$A1 Copy $flag *#C      // ATTACK! once every 3 turns
$A2 Copy C+1 C          // increment C, used for attacks and turning
$A3 If 0=0 $A1 $A1      // thread A loop
$Bstart Lock B          // thread B starts here, locks itself
Lock $B1                // lock thread B lines
Lock $B2                // thread B should be safe on turn 8
$B1 Copy $flag *#C+12   // ATTACK! once every 2 turns
$B2 If 0=0 $B1 $B1      // thread B loop
$flag Flag

```

# Answer
> 1 votes
# Attacker Bot

Copies flags into various locations

```
Copy A+1 A // Increment A
Move A //Move in the Ath direction
Turn A //Rotate A times
Copy #8 *#A //Copy my flag over
Copy 23 D //Loop back to the beginning.  (I use 23 here as threads auto-increment)

```

# Answer
> 1 votes
# Random Mover

Moves in a psuedorandom direction

```
Copy 5 C
Copy 8 B
Start C
Move A // If you can't catch me, you can't modify me
If 1=1 #3 #3 //Continue to execute the above line
Start B
Copy 4 A
If 1=1 #6 #6 //Continue to execute the above line
Flag
Copy 5 A
If 1=1 #9 #9 //Continue to execute the above line

```

# Answer
> 1 votes
# Thick Shelled

Locks his stuff as much as he can

```
Copy 5 B //Designating that the B thread will start on line 5
Start B //Starting the B thread
Lock C //Preventing C from being used
Copy A+1 A //The two threads are offset, meaning that the two threads shouldn't access this at the same time
Lock #A
Copy 2 B

```

# Answer
> 0 votes
# Triple Thread

This simple bot runs three threads all with the same code. Each thread attacks 1/3 turns, moves 1/6, turns 1/6, and does bookkeeping 1/3.

```
Move 0
Start A
Start B
$loop Copy #A+9 *#C
Move C
Copy #A+9 *#C
Turn C
Copy C+1 C
If 0=0 $loop $loop

```

# Answer
> 0 votes
# Banana Bot

Attempts to throw bananas in the enemies wheel before the enemy can do anything. Prone to being squished.

```
$d     If !*D $d1 $d0
$d0    Copy 24 *D
$d1    If !D $d2 $start
$d2    If !*B $d5 $d3
$d3    Copy 24 *B
$d4    Copy $d D

$start Lock D             //Banana's like to split.
       Copy $a A
       Start A
       Copy $b B
       Start B
       Lock $flag

$d5    Copy $start *C     //It's okay if enemy messes up our start.
       Copy $d d

$a     Lock A
$a1    Move C
       Turn 1
       Copy $a1 A

$b     Lock B
$b0    Copy C+1 C
       If !*#C $b0 $b1    //Banana's are good at slipping.
$b1    Copy $flag *#C
$b2    Copy $b0 B

$flag  Flag

```

# Answer
> 0 votes
# Copy and Self Flag

This bot runs three threads. The D thread moves until it runs into an enemy, then tries to copy a flag into them, then moves a random direction. The A thread copies its own flag over non-essential lines of the bot's code. The B thread is just a counter. The variable, flag, and lines of code used by each thread are fully locked in the first 15 turns, and the bot overwrites almost all of its startup code with its own flags. I don't think it's possible to convert this bot to another team's banner after turn 15 without a dedicated attack bot doing nothing but writing flags to it.

```
    Lock D              // Lock D thread
    Copy $AS A
    Start A             // Start A thread at $AS
    Start B             // B is just a counter
    Copy $DL D          // Jump to D thread startup code
$DC Start B             // Don't let B thread get stopped
$D0 If !*#B $D1 $D2
$D1 Copy $DF *#B
$D2 If !*#B+6 $D3 $DM
$D3 Copy $DF *#B
$DM Move B              // Move some direction after attacking
$DA Move 0              // Move north ...
    If ?*D $DC $DA      // until we hit a live target
$DF Flag                // Flag to copy
$DL Lock #B+3           // Lock the D thread's lines
    If B<12 $DL $DA     // jump to `Move 0` when D thread is safe
$AS Lock A
$AL Lock #B+20
    If B<4 $AL $AD
    Copy 23 B           // reset B so A doesn't overwrite its own code
$AF Flag
    Flag
$AD Copy $AF #B+1       // Copy a safe flag over every unused line of code
    If B<18 $AD $AF

```

# Answer
> 0 votes
# Thread Cutter Bot

```
   Lock D
   Lock $f
   Copy 16 C
$S If ?*D $1 $2
   Move 1
   Copy $S D
$f Flag
$1 Stop *D
$2 If ?*A $3 $4
$3 Stop *A
$4 If ?*B $5 $6
$5 Stop *B
$6 Copy $f *#C
   Copy C+1 C
   If *#C=#C $E $6
   Copy 2 D
$E Start *D

```

Stop all enemy threads before filling with your code.

---
Tags: king-of-the-hill
---


title: Implement a PCG

text:
# Question
Title: Implement a PCG
What better problem for PCG.SE than to implement PCG, A Better Random Number Generator? This new paper claims to present a fast, hard-to-predict, small, statistically optimal random number generator.

Its minimal C implementation is just about nine lines:

```
// *Really* minimal PCG32 code / (c) 2014 M.E. O'Neill / pcg-random.org
// Licensed under Apache License 2.0 (NO WARRANTY, etc. see website)

typedef struct { uint64_t state;  uint64_t inc; } pcg32_random_t;

uint32_t pcg32_random_r(pcg32_random_t* rng)
{
    uint64_t oldstate = rng->state;
    // Advance internal state
    rng->state = oldstate * 6364136223846793005ULL + (rng->inc|1);
    // Calculate output function (XSH RR), uses old state for max ILP
    uint32_t xorshifted = ((oldstate >> 18u) ^ oldstate) >> 27u;
    uint32_t rot = oldstate >> 59u;
    return (xorshifted >> rot) | (xorshifted << ((-rot) & 31));
}

```

(from: http://www.pcg-random.org/download.html)

The question is: can you do better?

# Rules

Write a program or define a function that implements PCG on 32-bit unsigned integers. This is fairly broad: you could print out an infinite sequence, define a `pcg32_random_r` function and corresponding struct, etc.

You must be able to seed your random number generator equivalently to the following C function:

```
// pcg32_srandom(initstate, initseq)
// pcg32_srandom_r(rng, initstate, initseq):
//     Seed the rng.  Specified in two parts, state initializer and a
//     sequence selection constant (a.k.a. stream id)

void pcg32_srandom_r(pcg32_random_t* rng, uint64_t initstate, uint64_t initseq)
{
    rng->state = 0U;
    rng->inc = (initseq << 1u) | 1u;
    pcg32_random_r(rng);
    rng->state += initstate;
    pcg32_random_r(rng);
}

```

(from: `pcg_basic.c:37`)

Calling the random number generator without seeding it first is undefined behaviour.

To easily check your submission, verify that, when seeded with `initstate = 42` and `initseq = 52`, the output is `2380307335`:

```
$ tail -n 8 pcg.c
int main()
{
    pcg32_random_t pcg;
    pcg32_srandom_r(&pcg, 42u, 52u);

    printf("%u\n", pcg32_random_r(&pcg));
    return 0;
}
$ gcc pcg.c
$ ./a.out
2380307335

```

# Scoring

Standard scoring. Measured in bytes. Lowest is best. In case of tie, earlier submission wins. Standard loopholes apply.

# Sample solution

Compiles under `gcc -W -Wall` cleanly (version 4.8.2).

Compare your submission to this to make sure you get the same sequence.

```
#include <stdlib.h>
#include <stdint.h>
#include <stdio.h>

typedef struct { uint64_t state;  uint64_t inc; } pcg32_random_t;

uint32_t pcg32_random_r(pcg32_random_t* rng)
{
    uint64_t oldstate = rng->state;
    // Advance internal state
    rng->state = oldstate * 6364136223846793005ULL + (rng->inc|1);
    // Calculate output function (XSH RR), uses old state for max ILP
    uint32_t xorshifted = ((oldstate >> 18u) ^ oldstate) >> 27u;
    uint32_t rot = oldstate >> 59u;
    return (xorshifted >> rot) | (xorshifted << ((-rot) & 31));
}

void pcg32_srandom_r(pcg32_random_t* rng, uint64_t initstate, uint64_t initseq)
{
    rng->state = 0U;
    rng->inc = (initseq << 1u) | 1u;
    pcg32_random_r(rng);
    rng->state += initstate;
    pcg32_random_r(rng);
}

int main()
{
    size_t i;
    pcg32_random_t pcg;
    pcg32_srandom_r(&pcg, 42u, 52u);

    for (i = 0; i < 16; i++)
    {
        printf("%u\n", pcg32_random_r(&pcg));
    }
    return 0;
}

```

Sequence:

```
2380307335
948027835
187788573
3952545547
2315139320
3279422313
2401519167
2248674523
3148099331
3383824018
2720691756
2668542805
2457340157
3945009091
1614694131
4292140870

```

# Answer
# CJam, ~~109~~ ~~107~~ ~~104~~ ~~98~~ 91 bytes

This uses some characters outside the ASCII range, but they are all within extended ASCII, so I'm counting each character as a byte (instead of counting as UTF-8).

```
{[2*0:A)|:B{AA"XQô-L-"256b*B1|+GG#%:A;__Im>^27m>_@59m>_@\m>@@~)31&m<|4G#%}:R~@A+:AR];}:S;

```

This is basically an exact port of the C code.

The seed function is a block stored in `S`, and the random function is a block stored in `R`. `S` expects `initstate` and `initseq` on the stack and seed the PRNG. `R` doesn't expect anything on the stack and leaves the next random number on it.

Since calling `R` before calling `S` is undefined behaviour, I'm actually defining `R` *within* `S`, so until you use the seed block, `R` is just an empty string and useless.

The `state` is stored in variable `A` and the `inc` is stored in `B`.

Explanation:

```
"The seed block S:";
[       "Remember start of an array. This is to clear the stack at the end.";
2*      "Multiply initseq by two, which is like a left-shift by one bit.";
0:A     "Store a 0 in A.";
)|:B    "Increment to get 1, bitwise or, store in B.";
{...}:R "Store this block in R. This is the random function.";
~       "Evaluate the block.";
@A+:A   "Pull up initstate, add to A and store in A.";
R       "Evaluate R again.";
];      "Wrap everything since [ in an array and discard it.";

"The random block R:";
AA            "Push two A's, one of them to remember oldstate.";
"XQô-L-"256b* "Push that string and interpret the character codes as base-256 digits.
               Then multiply A by this.";
B1|+          "Take bitwise or of 1 and inc, add to previous result.";
GG#%:A;       "Take modulo 16^16 (== 2^64). Store in A. Pop.";
__            "Make two copies of old state.";
Im>^          "Right-shift by 18, bitwise xor.";
27m>_         "Right-shift by 27. Duplicate.";
@59m>         "Pull up remaining oldstate. Right-shift by 59.";
_@\m>         "Duplicate, pull up xorshifted, swap order, right-shift.";
@@            "Pull up other pair of xorshifted and rot.";
~)            "Bitwise negation, increment. This is is like multiplying by -1.";
31&           "Bitwise and with 31. This is the reason I can actually use a negative value
               in the previous step.";
m<|           "Left-shift, bitwise or.";
4G#%          "Take modulo 4^16 (== 2^32).";

```

And here is the equivalent of the test harness in the OP:

```
42 52 S
{RN}16*

```

which prints the exact same numbers.

Test it here. Stack Exchange strips the two unprintable characters, so it won't work if you copy the above snippet. Copy the code from the character counter instead.
> 18 votes

# Answer
# C, 195

I figured someone ought to post a more compact C implementation, even if it stands no chance of winning. The third line contains two functions: `r()` (equivalent to `pcg32_random_r()`) and `s()` (equivalent to `pcg32_srandom_r()`). The last line is the `main()` function, which is excluded from the character count.

```
#define U unsigned
#define L long
U r(U L*g){U L o=*g;*g=o*0x5851F42D4C957F2D+(g[1]|1);U x=(o>>18^o)>>27;U t=o>>59;return x>>t|x<<(-t&31);}s(U L*g,U L i,U L q){*g++=0;*g--=q+q+1;r(g);*g+=i;r(g);}
main(){U i=16;U L g[2];s(g,42,52);for(;i;i--)printf("%u\n",r(g));}

```

Although the compiler will complain, this should work properly on a 64-bit machine. On a 32-bit machine you'll have to add another 5 bytes to change `#define L long` to `#define L long long` (like in this ideone demo).
> 12 votes

# Answer
# Julia, ~~218~~ ~~199~~ 191 bytes

Renaming data types plus a few other little tricks helped me to cut down the length by additional 19 bytes. Mainly by omitting two **::Int64** type assignments.

```
type R{T} s::T;c::T end
R(s,c)=new(s,c);u=uint32
a(t,q)=(r.s=0x0;r.c=2q|1;b(r);r.s+=t;b(r))
b(r)=(o=uint64(r.s);r.s=o*0x5851f42d4c957f2d+r.c;x=u((o>>>18$o)>>>27);p=u(o>>>59);x>>>p|(x<<-p&31))

```

Explanation of the names (with according names in the ungolfed version below):

```
# R     : function Rng
# a     : function pcg32srandomr
# b     : function pcg32randomr
# type R: type Rng
# r.s   : rng.state
# r.c   : rng.inc
# o     : oldstate
# x     : xorshifted
# t     : initstate
# q     : initseq
# p     : rot
# r     : rng
# u     : uint32

```

Initialize seed with state 42 and sequence 52. Due to the smaller program you need to state the data type explicitely during initialization now (saved 14 bytes of code or so). You can omit the explicit type assignment on 64-bit systems:

```
r=R(42,52) #on 64-bit systems or r=R(42::Int64,52::Int64) on 32 bit systems
a(r.s,r.c)

```

Produce first set of random numbers:

```
b(r)

```

Result:

```
julia> include("pcg32golfed.jl")
Checking sequence...
result round 1: 2380307335
target round 1: 2380307335   pass
result round 2: 948027835
target round 2: 948027835   pass
result round 3: 187788573
target round 3: 187788573   pass
             .
             .
             .

```

I was really surprised, that even my ungolfed Julia version below is so much smaller (543 bytes) than the sample solution in C (958 bytes).

## Ungolfed version, 543 bytes

```
type Rng{T}
    state::T
    inc::T
end

function Rng(state,inc)
    new(state,inc)
end

function pcg32srandomr(initstate::Int64,initseq::Int64)
    rng.state =uint32(0)
    rng.inc   =(initseq<<1|1)
    pcg32randomr(rng)
    rng.state+=initstate
    pcg32randomr(rng)
end

function pcg32randomr(rng)
    oldstate  =uint64(rng.state)
    rng.state =oldstate*uint64(6364136223846793005)+rng.inc
    xorshifted=uint32(((oldstate>>>18)$oldstate)>>>27)
    rot       =uint32(oldstate>>>59)
    (xorshifted>>>rot) | (xorshifted<<((-rot)&31))
end

```

You initialize the seed (initial state=42, initial sequence=52) with:

```
rng=Rng(42,52)
pcg32srandomr(rng.state,rng.inc)

```

Then you can create random numbers with:

```
pcg32randomr(rng)

```

Here is the result of a test script:

```
julia> include("pcg32test.jl")
Test PCG
Initialize seed...
Checking sequence...
result round 1: 2380307335
target round 1: 2380307335   pass
result round 2: 948027835
target round 2: 948027835   pass
result round 3: 187788573
target round 3: 187788573   pass
             .
             .
             .
result round 14: 3945009091
target round 14: 3945009091   pass
result round 15: 1614694131
target round 15: 1614694131   pass
result round 16: 4292140870
target round 16: 4292140870   pass

```

As I’m an abysmal programmer, it took me almost a day to get it working. The last time I tried coding something in C (actually C++) was almost 18 years ago, but a lot of google-fu finally helped me to create a working Julia version. I have to say, I have learned a lot during just a few days on codegolf. Now I can start to work on a Piet version. That’s gonna be a whole lot of work, but I **really, really** want a (good) random number generator for Piet ;)
> 6 votes

---
Tags: code-golf, random
---


title: Strategic Voting, The Game

text:
# Question
Title: Strategic Voting, The Game
One of the most common voting systems for single-winner elections is the plurality voting method. Simply put, the candidate with the most votes wins. Plurality voting, however, is mathematically unsound and is liable to create situations in which voters are driven to vote for the "lesser of two evils" as opposed to the candidate they truly prefer.

In this game, you will write program that takes advantage of the plurality voting system. It will cast a vote for one of three candidates in an election. Each candidate is associated with a certain payoff for yourself, and your goal is to maximize your expected payoff.

The payoffs are "uniformly" randomly distributed, change with each election, and add to 100. Candidate *A* could have payoff 40, Candidate *B* could have payoff 27, and Candidate *C* could have payoff 33. Each player has a different set of payoffs.

When it is your turn to vote, you will have incomplete information. Listed below is the information that you will have available to you. Since you don't know what other player's individual payoffs are, it will be your challenge to predict how they would vote given the current poll results.

* The partial results of the election so far
* The number of entrants (excluding yourself), who haven't voted yet
* Your personal payoffs for each of the candidates
* The total group payoffs for each of the candidates

After each player has been given a chance to vote, the candidate with the most votes wins in accordance with plurality voting. Each player then receives the number of points that corresponds the their payoff from that candidate. If there is a tie in votes, then the number of points assigned will be the average of the tied candidates.

## Tournament Structure

When first instantiated, the entrant will be told the number of elections held in the tournament. I will attempt to run an extremely large number of elections. Then, each election will be carried out one-by-one.

After the entrants are shuffled, each is given a turn to vote. They are given the limited information listed above and return a number signifying their vote. After each election is over, each bot is given the final poll results and their score increase from that election.

The victorious entrant will be the one with the highest total score after some large number of elections have been held. The controller also computes a "normalized" score for each contestant by comparing its score to the score distribution predicted for a randomly-voting bot.

## Submission Details

**Submissions will take the form of Java 8 classes.** Each entrant must implement the following interface:

```
public interface Player
{
    public String getName();
    public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs);
    public void receiveResults(int[] voteCounts, double result);
}

```
* **Your constructor should take a single `int` as a parameter,** which will represent the number of elections that will be held.
* The `getName()` method returns the name to be used on the leaderboard. This allows you to have nicely-formatted names, just don't go crazy.
* The `getVote(...)` method returns `0`, `1`, or `2` to signify which candidate will receive the vote.
* The `receiveResults(...)` method is mainly to enable the existence of more complex strategies that use historical data.
* You are allowed to create pretty much any other methods / instance variables you wish to record and process the information given to you.

## Tournament Cycle, Expanded

1. The entrants are each instantiated with `new entrantName(int numElections)`.
2. For each election:
    1. The controller randomly determines the payoffs for each player for this election. The code for this is given below. Then, it shuffles players and has them start voting.
    2. The entrant's method `public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs)` is invoked, and the entrant returns their vote of `0`, `1`, or `2` for the candidate of their choice.
    3. Entrants whose `getVote(...)` method doesn't return a valid vote will be assigned a random vote.
    4. After everyone has voted, the controller determines the election results by the plurality method.
    5. The entrants are informed of the final vote counts and their payoff by calling their method `public void receiveResults(int[] voteCounts, double result)`.
3. After all elections have been held, the winner is the one with the highest score.

## The Random Distribution of Payoffs

The *exact* distribution will have a significant effect on gameplay. I have chosen a distribution with a large standard deviation (about 23.9235) and which is capable of creating both very high and very low payoffs. I have checked that each of the three payoffs has an identical distribution.

```
public int[] createPlayerPayoffs()
{
    int cut1;
    int cut2;
    do{
        cut1 = rnd.nextInt(101);
        cut2 = rnd.nextInt(101);
    } while (cut1 + cut2 > 100);
    int rem = 100 - cut1 - cut2;
    int[] set = new int[]{cut1,cut2,rem};
    totalPayoffs[0] += set[0];
    totalPayoffs[1] += set[1];
    totalPayoffs[2] += set[2];
    return set;
}

```

## More Rules

Here are some more generalized rules.

* Your program must not run/modify/instantiate any parts of the controller or other entrants or their memories.
* Since your program stays "live" for the whole tournament, don't create any files.
* Don't interact with, help, or target any other entrant programs.
* You *may* submit multiple entrants, as long as they are reasonably different, and as long as you follow the above rules.
* I haven't specified an exact time limit, but I would greatly appreciate runtimes that are *significantly* less than a second per call. I want to be able to run as many elections as feasible.

## The Controller

**The controller can be found here.** The main program is `Tournament.java`. There are also two simple bots, which will be competing, titled `RandomBot` and `PersonalFavoriteBot`. I will post these two bots in an answer.

## Leaderboard

It looks like ExpectantBot is the current leader, followed by Monte Carlo and then StaBot.

```
Leaderboard - 20000000 elections:
   767007688.17 (  937.86) - ExpectantBot
   766602158.17 (  934.07) - Monte Carlo 47
   766230646.17 (  930.60) - StatBot
   766054547.17 (  928.95) - ExpectorBot
   764671254.17 (  916.02) - CircumspectBot
   763618945.67 (  906.19) - LockBot
   763410502.67 (  904.24) - PersonalFavoriteBot343
   762929675.17 (  899.75) - BasicBot
   761986681.67 (  890.93) - StrategicBot50
   760322001.17 (  875.37) - Priam
   760057860.67 (  872.90) - BestViableCandidate (2842200 from ratio, with 1422897 tie-breakers of 20000000 total runs)
   759631608.17 (  868.92) - Kelly's Favorite
   759336650.67 (  866.16) - Optimist
   758564904.67 (  858.95) - SometimesSecondBestBot
   754421221.17 (  820.22) - ABotDoNotForget
   753610971.17 (  812.65) - NoThirdPartyBot
   753019290.17 (  807.12) - NoClueBot
   736394317.17 (  651.73) - HateBot670
   711344874.67 (  417.60) - Follower
   705393669.17 (  361.97) - HipBot
   691422086.17 (  231.38) - CommunismBot0
   691382708.17 (  231.01) - SmashAttemptByEquality (on 20000000 elections)
   691301072.67 (  230.25) - RandomBot870
   636705213.67 ( -280.04) - ExtremistBot
The tournament took 34573.365419071 seconds, or 576.2227569845166 minutes.

```

Here are some older tournament, but none of the bots have changed in functionality since these runs.

```
Leaderboard - 10000000 elections:
   383350646.83 (  661.14) - ExpectantBot
   383263734.33 (  659.99) - LearnBot
   383261776.83 (  659.97) - Monte Carlo 48
   382984800.83 (  656.31) - ExpectorBot
   382530758.33 (  650.31) - CircumspectBot
   381950600.33 (  642.64) - PersonalFavoriteBot663
   381742600.33 (  639.89) - LockBot
   381336552.33 (  634.52) - BasicBot
   381078991.83 (  631.12) - StrategicBot232
   380048521.83 (  617.50) - Priam
   380022892.33 (  617.16) - BestViableCandidate (1418072 from ratio, with 708882 tie-breakers of 10000000 total runs)
   379788384.83 (  614.06) - Kelly's Favorite
   379656387.33 (  612.31) - Optimist
   379090198.33 (  604.83) - SometimesSecondBestBot
   377210328.33 (  579.98) - ABotDoNotForget
   376821747.83 (  574.84) - NoThirdPartyBot
   376496872.33 (  570.55) - NoClueBot
   368154977.33 (  460.28) - HateBot155
   355550516.33 (  293.67) - Follower
   352727498.83 (  256.36) - HipBot
   345702626.33 (  163.50) - RandomBot561
   345639854.33 (  162.67) - SmashAttemptByEquality (on 10000000 elections)
   345567936.33 (  161.72) - CommunismBot404
   318364543.33 ( -197.86) - ExtremistBot
The tournament took 15170.484259763 seconds, or 252.84140432938332 minutes.

```

I also ran a second 10m tournament, confirming ExpectantBot's lead.

```
Leaderboard - 10000000 elections:
   383388921.83 (  661.65) - ExpectantBot
   383175701.83 (  658.83) - Monte Carlo 46
   383164037.33 (  658.68) - LearnBot
   383162018.33 (  658.65) - ExpectorBot
   382292706.83 (  647.16) - CircumspectBot
   381960530.83 (  642.77) - LockBot
   381786899.33 (  640.47) - PersonalFavoriteBot644
   381278314.83 (  633.75) - BasicBot
   381030871.83 (  630.48) - StrategicBot372
   380220471.33 (  619.77) - BestViableCandidate (1419177 from ratio, with 711341 tie-breakers of 10000000 total runs)
   380089578.33 (  618.04) - Priam
   379714345.33 (  613.08) - Kelly's Favorite
   379548799.83 (  610.89) - Optimist
   379289709.83 (  607.46) - SometimesSecondBestBot
   377082526.83 (  578.29) - ABotDoNotForget
   376886555.33 (  575.70) - NoThirdPartyBot
   376473476.33 (  570.24) - NoClueBot
   368124262.83 (  459.88) - HateBot469
   355642629.83 (  294.89) - Follower
   352691241.83 (  255.88) - HipBot
   345806934.83 (  164.88) - CommunismBot152
   345717541.33 (  163.70) - SmashAttemptByEquality (on 10000000 elections)
   345687786.83 (  163.30) - RandomBot484
   318549040.83 ( -195.42) - ExtremistBot
The tournament took 17115.327209018 seconds, or 285.25545348363335 minutes.

```

# Answer
# NoThirdPartyBot

This bot tries to guess which candidate will be third, and votes the candidate he likes best of the two front runners.

```
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class NoThirdPartyBot implements Player {

    public NoThirdPartyBot(int e) {
    }

    @Override
    public String getName() {
        return "NoThirdPartyBot";
    }

    @Override
    public int getVote(int[] voteCounts, int votersRemaining, int[] payoffs,
            int[] totalPayoffs) {
        List<Integer> order = order(totalPayoffs);

        if (payoffs[order.get(0)] > payoffs[order.get(1)]) {
            return order.get(0);
        } else {
            return order.get(1);
        }
    }

    static List<Integer> order(int[] array) {
        List<Integer> indexes = Arrays.asList(0, 1, 2);
        Collections.sort(indexes, (i1, i2) -> array[i2] - array[i1]);
        return indexes;
    }

    @Override
    public void receiveResults(int[] voteCounts, double result) {
    }
}

```

# CircumspectBot

This bot votes for his favorite that hasn't been mathematically eliminated.

```
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class CircumspectBot implements Player {

    public CircumspectBot(int elections) {
    }

    @Override
    public String getName() {
        return "CircumspectBot";
    }

    @Override
    public int getVote(int[] voteCounts, int votersRemaining, int[] payoffs,
            int[] totalPayoffs) {
        List<Integer> indexes = new ArrayList<>();
        int topVote = Arrays.stream(voteCounts).max().getAsInt();
        for (int index = 0; index < 3; index++) {
            if (voteCounts[index] + votersRemaining + 1 >= topVote) {
                indexes.add(index);
            }
        }
        Collections.sort(indexes, (i1, i2) -> payoffs[i2] - payoffs[i1]);

        return indexes.get(0);
    }

    @Override
    public void receiveResults(int[] voteCounts, double result) {

    }

}

```
> 10 votes

# Answer
# ExpectantBot

This bot computes the expected value of each voting option assuming that all voters afterwards will vote randomly.

```
import java.util.Arrays;

public class ExpectantBot implements Player {

    public ExpectantBot(int elections) {
    }

    @Override
    public String getName() {
        return "ExpectantBot";
    }

    static double choose(int x, int y) {
        if (y < 0 || y > x) return 0;
        if (y > x/2) {
            // choose(n,k) == choose(n,n-k),
            // so this could save a little effort
            y = x - y;
        }

        double denominator = 1.0, numerator = 1.0;
        for (int i = 1; i <= y; i++) {
            denominator *= i;
            numerator *= (x + 1 - i);
        }
        return numerator / denominator;
    }

    double expectedPayout(int[] voteCounts, int[] payoffs, int votersRemaining) {
        double total = 0.0;
        for (int firstPartyVoters = 0; firstPartyVoters <= votersRemaining; firstPartyVoters++) {
            for (int secondPartyVoters = 0; secondPartyVoters <= votersRemaining - firstPartyVoters; secondPartyVoters++) {
                int thirdPartyVoters = votersRemaining - firstPartyVoters - secondPartyVoters;

                int [] newVoteCounts = voteCounts.clone();
                newVoteCounts[0] += firstPartyVoters;
                newVoteCounts[1] += secondPartyVoters;
                newVoteCounts[2] += thirdPartyVoters;
                int highest = Arrays.stream(newVoteCounts).max().getAsInt();
                int payoff = 0;
                int winCount = 0;
                for (int index = 0; index < 3; index++) {
                    if (newVoteCounts[index] == highest) {
                        payoff += payoffs[index];
                        winCount++;
                    }
                }
                double v = (double)payoff / (double) winCount;
                double value = choose(votersRemaining, firstPartyVoters)*choose(votersRemaining - firstPartyVoters, secondPartyVoters)*v*Math.pow(1/3.0, votersRemaining);
                total += value;
            }
        }
        return total;
    }

    @Override
    public int getVote(int[] voteCounts, int votersRemaining, int[] payoffs,
            int[] totalPayoffs) {

        int bestVote = 0;
        double bestScore = 0.0;
        for (int vote = 0; vote < 3; vote++) {
            voteCounts[vote]++;
            double score = expectedPayout(voteCounts, payoffs, votersRemaining);
            if (score > bestScore) {
                bestVote = vote;
                bestScore = score;
            }
            voteCounts[vote]--;
        }
        return bestVote;

    }

    @Override
    public void receiveResults(int[] voteCounts, double result) {
    }

}

```
> 10 votes

# Answer
# HipBot

HipBot doesn't care about payouts. Money is just a sedative that distracts from true art.

HipBot wants to vote for someone *real*, not just some corporate shill. He also wants to wear their campaign shirt after their (presumably) humiliating defeat, so he feels superior whenever the winner does something wrong.

Therefore, HipBot votes for the person with the lowest votes or, if there's a tie, whoever's got the better payout. Eating organic-only isn't free.

```
public class HipBot implements Player{

    public HipBot(int rounds){ /*Rounds are a social construct*/ }

    public String getName(){ return "HipBot"; }

    public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs){

        int coolest = 0;
        int lowest = 100000000;
        int gains = 0;

        for( int count = 0; count < voteCounts.length; count++ ){

            if( voteCounts[count] < lowest || (voteCounts[count] == lowest && payoffs[count] > gains) ){

                lowest = voteCounts[count];
                coolest = count;
                gains = payoffs[count];

            }

        }

        return coolest;

    }

    public void receiveResults(int[] voteCounts, double result){ /*The past is dead*/ }

}

```

HipBot is also untested, so let me know if there's anything going on.

EDIT: added in more competitive tiebreaking, pithy comments.
> 9 votes

# Answer
# PersonalFavoriteBot

This bot simply votes for the candidate with the highest personal payoff, ignoring everything else. One of the main points of this challenge is to demonstrate how this is not the optimal strategy.

```
import java.lang.Math;
import java.util.Random;
/**
 * This bot picks the candidate with the highest personal payoff, ignoring everyone else's actions.
 *
 * @author PhiNotPi
 * @version 5/27/15
 */
public class PersonalFavoriteBot implements Player
{
    Random rnd;
    String name;
    /**
     * Constructor for objects of class PersonalFavoriteBot
     */
    public PersonalFavoriteBot(int e)
    {
       rnd = new Random();
       name = "PersonalFavoriteBot" + rnd.nextInt(1000);
    }

    public String getName()
    {
        return name;
    }

    public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs)
    {
        //return rnd.nextInt(3);
        int maxloc = 0;
        for(int i = 1; i< 3; i++)
        {
            if(payoffs[i] > payoffs[maxloc])
            {
                maxloc = i;
            }
        }
        return maxloc;
    }

    public void receiveResults(int[] voteCounts, double result)
    {

    }
}

```

# RandomBot

This bot votes randomly. Regardless of the number of elections carried out (as long as it's reasonably high, like over 100), this contestant's normalized score fluctuates between -2 and 2.

```
import java.lang.Math;
import java.util.Random;
/**
 * This bot votes for a random candidate.
 *
 * @author PhiNotPi
 * @version 5/27/15
 */
public class RandomBot implements Player
{
    Random rnd;
    String name;
    /**
     * Constructor for objects of class RandomBot
     */
    public RandomBot(int e)
    {
       rnd = new Random();
       name = "RandomBot" + rnd.nextInt(1000);
    }

    public String getName()
    {
        return name;
    }

    public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs)
    {
        return rnd.nextInt(3);
    }

    public void receiveResults(int[] voteCounts, double result)
    {

    }
}

```
> 8 votes

# Answer
# Follower

Follower wants to fit in. It thinks the best way to accomplish that is by voting the same way as everyone else, or at least with the plurality so far. It'll break ties towards its own preference, to show a little independence. But not too much.

```
public class Follower implements Player
{
    public Follower(int e) { }

    public String getName()
    {
        return "Follower";
    }

    public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs)
    {
        int mostPopular = 0;
        int mostVotes = voteCounts[0];
        for (int i = 1; i < voteCounts.length; i++) {
            int votes = voteCounts[i];
            if (votes > mostVotes || (votes == mostVotes && payoffs[i] > payoffs[mostPopular])) {
                mostPopular = i;
                mostVotes = votes;
            }
        }
        return mostPopular;

    }

    public void receiveResults(int[] voteCounts, double result) { }
}

```

Note: I haven't tested this, so let me know if there are any errors.
> 7 votes

# Answer
# Best Viable Candidate

Pretty heavily revised version of my original submission. This one still eliminates any candidates that cannot win given the remaining votes to be cast, but then uses a strategy that tries to optimize the *relative payoff* rather than the absolute one. The first test is to take the ratio of my personal payoff to the overall payoff for each candidate, looking for the best value there. I then look for other ratios that are very close to the best and if there is one that has a lower overall payoff than the very best I pick that one instead. Hopefully this will tend to depress the payout of the other players while keeping mine reasonably high.

This bot does *almost* as well as the original on in my own testing, but not quite. We'll have to see how it does against the full field.

```
 /**
  * This bot picks the candidate with the highest relative payoff out of those
  * candidates who are not already mathematically eliminated.
  *
  * @author Ralph Marshall
  * @version 5/28/2015
  */

import java.util.List;
import java.util.ArrayList;

public class BestViableCandidate implements Player
{
    private static int NUM_CANDIDATES = 3;
    private int relativeCount = 0;
    private int relativeCountLowerTotal = 0;
    private int totalRuns;

    public BestViableCandidate(int r) {
        totalRuns = r;
    }

    public String getName() {
        return "BestViableCandidate (" + relativeCount + " from ratio, with " + relativeCountLowerTotal + " tie-breakers of " + totalRuns + " total runs)";
    }

    public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs) {

        int i, maxVoteSoFar = 0;

        // First we figure out the maximum possible number of votes each candidate would get
        // if every remaining bot voted for it
        int [] maxPossibleVotes = new int[NUM_CANDIDATES];
        for (i = 0; i < NUM_CANDIDATES; i++) {

            // The voters remaining does not include me, so we need to add one to it
            maxPossibleVotes[i] = voteCounts[i] + votersRemaining + 1;

            if (voteCounts[i] > maxVoteSoFar) {
                maxVoteSoFar = voteCounts[i];
            }
        }

        // Then we throw out anybody who cannot win even if they did get all remaining votes
        List<Integer> viableCandidates = new ArrayList<Integer>();
        for (i = 0; i < NUM_CANDIDATES; i++) {
            if (maxPossibleVotes[i] >= maxVoteSoFar) {
                viableCandidates.add(Integer.valueOf(i));
            }
        }

        // And of the remaining candidates we pick the one that has the personal highest payoff
        // relative to the payoff to the rest of the voters
        int maxCandidate = -1;
        double maxRelativePayoff = -1;
        int maxPayoff = -1;
        int minTotalPayoff = Integer.MAX_VALUE;

        int originalMaxCandidate = -1;
        double originalMaxPayoff = -1;

        double DELTA = 0.01;

        double tiebreakerCandidate = -1;

        for (Integer candidateIndex : viableCandidates) {
            double relativePayoff = (double) payoffs[candidateIndex] / (double) totalPayoffs[candidateIndex];
            if (maxRelativePayoff < 0 || relativePayoff - DELTA > maxRelativePayoff) {
                maxRelativePayoff = relativePayoff;
                maxCandidate = candidateIndex;

                maxPayoff = payoffs[candidateIndex];
                minTotalPayoff = totalPayoffs[candidateIndex];

            } else if (Math.abs(relativePayoff - maxRelativePayoff) < DELTA) {
                if (totalPayoffs[candidateIndex] < minTotalPayoff) {
                    tiebreakerCandidate = candidateIndex;

                    maxRelativePayoff = relativePayoff;
                    maxCandidate = candidateIndex;

                    maxPayoff = payoffs[candidateIndex];
                    minTotalPayoff = totalPayoffs[candidateIndex];

                }
            }

            if (payoffs[candidateIndex] > originalMaxPayoff) {
                originalMaxPayoff = payoffs[candidateIndex];
                originalMaxCandidate = candidateIndex;
            }
        }

        if (tiebreakerCandidate == maxCandidate) {
            relativeCountLowerTotal++;
        }

        if (originalMaxCandidate != maxCandidate) {
            /*                System.out.printf("%nSelecting candidate %d with relative payoff %f (%d/%d) instead of %d with relative payoff %f (%d/%d)%n",
                              maxCandidate, (double) payoffs[maxCandidate]/(double)totalPayoffs[maxCandidate], payoffs[maxCandidate], totalPayoffs[maxCandidate],
                              originalMaxCandidate, (double) payoffs[originalMaxCandidate]/(double)totalPayoffs[originalMaxCandidate], payoffs[originalMaxCandidate], totalPayoffs[originalMaxCandidate]);
            */
            relativeCount++;
        }

        return maxCandidate;
    }
}

```
> 4 votes

# Answer
# Monte Carlo

This simulates a large amount of random elections. It then chooses the choice that maximizes it's own profits.

```
import java.util.ArrayList;
import java.util.List;

public class MonteCarlo implements Player{

    private static long runs = 0;
    private static long elections = 0;

    public MonteCarlo(int e) {
        elections = e;
    }

    @Override
    public String getName() {
        return "Monte Carlo (difficulty " + (runs / elections) + ")";
    }

    @Override
    public int getVote(int[] voteCounts, int votersRemaining, int[] payoffs, int[] totalPayoffs) {
        elections++;
        double[] predictedPayoffs = new double[3];
        long startTime = System.nanoTime();
        while (System.nanoTime() - startTime <= 200_000){ //Let's give us 200 micro-seconds.
            runs++;
            int[] simulatedVoteCounts = voteCounts.clone();
            for (int j = 0; j < votersRemaining; j++){
                simulatedVoteCounts[((int) Math.floor(Math.random() * 3))]++;
            }
            for (int j = 0; j < 3; j++) {
                simulatedVoteCounts[j]++;
                List<Integer> winners = new ArrayList<>();
                winners.add(0);
                for (int k = 1; k < 3; k++) {
                    if (simulatedVoteCounts[k] > simulatedVoteCounts[winners.get(0)]) {
                        winners.clear();
                        winners.add(k);
                    } else if (simulatedVoteCounts[k] == simulatedVoteCounts[winners.get(0)]) {
                        winners.add(k);
                    }
                }
                for (int winner : winners) {
                    predictedPayoffs[j] += payoffs[winner] / winners.size();
                }
                simulatedVoteCounts[j]--;
            }
        }
        int best = 0;
        for (int i = 1; i < 3; i++){
            if (predictedPayoffs[i] > predictedPayoffs[best]){
                best = i;
            }
        }
        return best;
    }

    @Override
    public void receiveResults(int[] voteCounts, double result) {

    }
}

```
> 4 votes

# Answer
# StatBot

StatBot is based on ExpectantBot; however, instead of assuming that each vote is equally probable it collects stats on how people vote and uses that to estimate the probability.

```
import java.util.Arrays;

public class StatBot implements Player {

    static private int[][][] data = new int[3][3][3];
    private int[] voteCounts;

    StatBot(int unused) {

    }

    @Override
    public String getName() {
        return "StatBot";

    }

     static double choose(int x, int y) {
            if (y < 0 || y > x) return 0;
            if (y > x/2) {
                // choose(n,k) == choose(n,n-k),
                // so this could save a little effort
                y = x - y;
            }

            double denominator = 1.0, numerator = 1.0;
            for (int i = 1; i <= y; i++) {
                denominator *= i;
                numerator *= (x + 1 - i);
            }
            return numerator / denominator;
        }

    double expectedPayout(int[] voteCounts, int[] payoffs, int votersRemaining) {
        Integer[] indexes = {0, 1, 2};
        Arrays.sort(indexes, (i0, i1) -> voteCounts[i1] - voteCounts[i0]);
        int [] stats = data[indexes[0]][indexes[1]];
        int total_stats = Arrays.stream(stats).sum();
        double total = 0.0;
        for (int firstPartyVoters = 0; firstPartyVoters <= votersRemaining; firstPartyVoters++) {
            for (int secondPartyVoters = 0; secondPartyVoters <= votersRemaining - firstPartyVoters; secondPartyVoters++) {
                int thirdPartyVoters = votersRemaining - firstPartyVoters - secondPartyVoters;

                int [] newVoteCounts = voteCounts.clone();
                newVoteCounts[0] += firstPartyVoters;
                newVoteCounts[1] += secondPartyVoters;
                newVoteCounts[2] += thirdPartyVoters;
                int highest = 0;
                for (int h : newVoteCounts) {
                    if (h > highest) highest = h;
                }
                int payoff = 0;
                int winCount = 0;
                for (int index = 0; index < 3; index++) {
                    if (newVoteCounts[index] == highest) {
                        payoff += payoffs[index];
                        winCount++;
                    }
                }
                double v = (double)payoff / (double) winCount;
                double value = choose(votersRemaining, firstPartyVoters)*choose(votersRemaining - firstPartyVoters, secondPartyVoters)*v;
                value *= Math.pow((double)stats[0]/(double)total_stats, firstPartyVoters);
                value *= Math.pow((double)stats[1]/(double)total_stats, secondPartyVoters);
                value *= Math.pow((double)stats[2]/(double)total_stats, thirdPartyVoters);

                total += value;
            }
        }
        return total;
    }

    @Override
    public int getVote(int[] voteCounts, int votersRemaining, int[] payoffs,
            int[] totalPayoffs) {

        int bestVote = 0;
        double bestScore = 0.0;
        for (int vote = 0; vote < 3; vote++) {
            voteCounts[vote]++;
            double score = expectedPayout(voteCounts, payoffs, votersRemaining);
            if (score > bestScore) {
                bestVote = vote;
                bestScore = score;
            }
            voteCounts[vote]--;
        }
        voteCounts[bestVote]++;
        this.voteCounts = voteCounts;

        return bestVote;

    }

    @Override
    public void receiveResults(int[] endVoteCounts, double result) {
        Integer[] indexes = {0, 1, 2};
        Arrays.sort(indexes, (i0, i1) -> voteCounts[i1] - voteCounts[i0]);
        for(int i = 0; i < 3; i++){
            data[indexes[0]][indexes[1]][i] += endVoteCounts[i] - voteCounts[i];
        }
    }
}

```
> 4 votes

# Answer
# Optimist

The Optimist is very optimistic and assumes that half of the remaining voters will vote for the candidate that gives it the best payoff.

```
import java.lang.Integer;
import java.lang.String;
import java.util.Arrays;
import java.util.Comparator;

public class Optimist implements Player
{
    public Optimist(int _) { }
    public String getName() { return "Optimist"; }
    public int getVote(int[] curVotes, int rem, final int[] payoffs, int[] _)
    {
        Integer[] opt = new Integer[] { 0, 1, 2 };
        Arrays.sort(opt, new Comparator<Integer>() { public int compare(Integer i1, Integer i2) { return payoffs[i1] > payoffs[i2] ? -1 : payoffs[i1] == payoffs[i2] ? 0 : 1; } });
        int a = curVotes[opt[0]], b = curVotes[opt[1]], c = curVotes[opt[2]];
        double rest = (double)rem / 4;
        if (b <= a + rest && c <= a + rest)
            return opt[0];
        else if (c <= b)
            return opt[1];
        else
            return opt[0];
    }
    public void receiveResults(int[] _, double __) { }
}

```
> 3 votes

# Answer
# ABotDoNotForget

His goal is simple : determining the overall tendencies using the total payoffs and counting the number of time the lower/medium/higher ones won. He will then vote for the one that is most likely to win.

```
import java.util.ArrayList;

public class ABotDoNotForget implements Player
{
    private int nbElec;
    private int countElec=0;
    private int[] currPayoffs=new int[3];
    private int[] lmh=new int[3];
    private int[] wins=new int[3];

    public ABotDoNotForget(int nbElec)
    {
        this.nbElec=nbElec;
    }

    public String getName() {return "ABotDoNotForget";}

    public int getVote(int[] voteCounts,
                        int votersRemaining,
                        int[] payoffs,
                        int[] totalPayoffs)
    {
        countElec++;
        System.arraycopy(totalPayoffs, 0, currPayoffs, 0, totalPayoffs.length);

        if(countElec<=nbElec/20&&countElec<=20)
        {
            int best=0;
            for(int i=1;i<payoffs.length;i++)
                if(payoffs[i]>=payoffs[best])
                    best=i;
            return best;
        }

        for(int i =1;i<totalPayoffs.length;i++)
        {
            if(totalPayoffs[i]<totalPayoffs[i-1])
            {
                int tmp= totalPayoffs[i];
                totalPayoffs[i]=totalPayoffs[i-1];
                totalPayoffs[i-1]=tmp;
                if(i==2&&totalPayoffs[i-1]<totalPayoffs[i-2]){
                    tmp= totalPayoffs[i-1];
                    totalPayoffs[i-1]=totalPayoffs[i-2];
                    totalPayoffs[i-2]=tmp;
                }
            }
        }
        lmhDist(currPayoffs,totalPayoffs);
        int best=0;
        for(int i=1;i<wins.length;i++)
            if(wins[i]>=wins[best]){
                best=i;
            }
        int ownH=0;
        for(int i=1;i<payoffs.length;i++)
            if(payoffs[i]>=payoffs[ownH])
                ownH=i;
        int ownM=0;
        for(int i=1;i<payoffs.length;i++)
            if(payoffs[i]>=payoffs[ownM]&&i!=ownH)
                ownM=i;

        int persBest=(voteCounts[ownH]-voteCounts[ownM]+(votersRemaining/3)>=0
                &&voteCounts[ownH]-voteCounts[best]<(votersRemaining/3))?ownH:ownM;

        return persBest;

    }

    public void receiveResults(int[] voteCounts, double result)
    {
        int best=0,bestV=voteCounts[best];
        for(int i=1;i<voteCounts.length;i++)
            if(voteCounts[i]>=bestV){
                best=i;
                bestV=voteCounts[i];
            }
        wins[lmh[best]]++;

    }

    private void lmhDist(int[] a,int[] s)
    {
        ArrayList<Integer> al = new ArrayList<Integer>();
        al.add(a[0]);al.add(a[1]);al.add(a[2]);
        lmh[0]=al.indexOf(s[0]);
        lmh[1]=al.indexOf(s[1]);
        lmh[2]=al.indexOf(s[2]);

    }
}

```

### Edit :

Some change done in the decision algorythm, now takes into account his own best payoff. Should now be able to vote better when the current distribution was making him vote for his own Lower when others where voting for their Higher payoffs.
> 3 votes

# Answer
# Priam

Priam hates recursion. He estimates the probability of each remaining bot based on the total payoffs and then calculates the best way of maximising his payoff.

```
public class Priam implements Player {
    private static double[] smallFactorials = {1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800.,87178291200.,1307674368000.,20922789888000.,355687428096000.,6402373705728000.,121645100408832000.,2432902008176640000.};
    @Override
    public String getName() {
        return "Priam";
    }

    @Override
    public int getVote(int[] voteCounts, int votersRemaining, int[] payoffs,
            int[] totalPayoffs) {
        int totalPayoff = totalPayoffs[0] + totalPayoffs[1] + totalPayoffs[2];
        double p0 = ((double)totalPayoffs[0])/totalPayoff;
        double p1= ((double) totalPayoffs[1])/totalPayoff;
        double p2 = ((double)totalPayoffs[2])/totalPayoff;
        double[] expectedPayoffs = {0,0,0};
        for(int myChoice=0;myChoice<3;myChoice++)
        {
            for(int x0 = 0; x0 <= votersRemaining; x0++)
            {
                for(int x1 = 0; x1 <= (votersRemaining-x0); x1++)
                {
                    int x2 = votersRemaining - (x1 + x0);
                    double probability =
                            Math.pow(p0, x0)
                            * Math.pow(p1, x1)
                            * Math.pow(p2, x2)
                            * Choose(votersRemaining, x0)
                            * Choose(votersRemaining-x0, x1);
                    int votes0 = voteCounts[0];
                    int votes1 = voteCounts[1];
                    int votes2 = voteCounts[2];
                    if(myChoice == 0)
                    {
                        votes0++;
                    }
                    else if(myChoice==1)
                    {
                        votes1++;
                    }
                    else
                    {
                        votes2++;
                    }

                    votes0+=x0;
                    votes1+=x1;
                    votes2+=x2;
                    if(votes0>votes1 && votes0>votes2)
                    {
                        expectedPayoffs[myChoice]+=probability*payoffs[0];
                    }
                    else if(votes1>votes2)
                    {
                        expectedPayoffs[myChoice]+=probability*payoffs[1];
                    }
                    else
                    {
                        expectedPayoffs[myChoice]+=probability*payoffs[2];
                    }
                }
            }
        }
        if(expectedPayoffs[0]>expectedPayoffs[1] && expectedPayoffs[0]>expectedPayoffs[2])
        {
            return 0;
        }
        else if(expectedPayoffs[1]>expectedPayoffs[2])
        {
            return 1;
        }
        else
        {
            return 2;
        }
    }

    private long Choose(int source, int team) {
        return Factorial(source)/(Factorial(team)*Factorial(source-team));
    }

    private long Factorial(int n) {
        if(n<=20)
        {
            return (long)smallFactorials[n];
        }
        double d=(double)n;
        double part1 = Math.sqrt(2*Math.PI*d);
        double part2 = Math.pow(d/Math.E, d);
        return (long)Math.ceil(part1 * part2);
    }

    @Override
    public void receiveResults(int[] voteCounts, double result) {

    }
    public Priam(int i)
    {

    }
}

```

Much much faster than Odysseus as there is no recursion (runs in time O(n^2)) and can do one million elections in about 15 seconds.
> 3 votes

# Answer
# NoClueBot

NoClue does not actually know Java or math very well, so he has no idea if this weighting-ratio-thingy will help him win. But he's trying.

```
import java.lang.Math;
import java.util.*;
/**
 * Created by Admin on 5/27/2015.
 */
public class NoClueBot implements Player {

    public NoClueBot(int e) { }

    public String getName() {
        return "NoClueBot";
    }

    public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs) {
        double x = 0;
        int y = 0;
        for (int i=0; i<3; i++) {
            double t = (double) voteCounts[i] * ((double) payoffs[i]/(double) totalPayoffs[i]);
            if (x<t) {
                x = t;
                y = i;
            }
        }
        return y;
    }

    public void receiveResults(int[] voteCounts, double result) { }
}

```

---

# SomeClueBot

SomeClueBot has been decommissioned. ~~actually uses logic! used to use logic, which turned out to be inefficient, so instead he became mindful of the total payoff, not his own. uses logic again! But he doesn't do well with all these followers and optimists, and even people who don't care! :)~~

---

# SometimesSecondBestBot

Basically PersonalFavouriteBot, improved (in theory).

```
import java.lang.Math;
/**
 * Created by Admin on 5/27/2015.
 */
public class SometimesSecondBestBot implements Player {
    public SometimesSecondBestBot(int e) { }

    public String getName() {
        return "SometimesSecondBestBot";
    }

    public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs) {
        int m = 0;
        int n = 0;
        for(int i = 1; i< 3; i++) {
            if(payoffs[i] > payoffs[m]) { n = m; m = i; }
        }
        return (voteCounts[n]>voteCounts[m]&&totalPayoffs[n]>totalPayoffs[m])||(voteCounts[m]+votersRemaining<voteCounts[n])||voteCounts[m]+votersRemaining<voteCounts[Math.min(3-n-m, 2)] ? n : m;
    }

    public void receiveResults(int[] voteCounts, double result) { }
}

```
> 2 votes

# Answer
# The extremist

Always vote for the candidate with the lowest payoff

```
public class ExtremistBot implements Player
{
    public ExtremistBot(int e){}

    public void receiveResults(int[] voteCounts, double result){}

    public String getName(){
        return "ExtremistBot";
    }

    public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs)
    {
        int min = 0;
        for(int i = 1; i<payoffs.length; i++){
            if(payoffs[i] <payoffs[min]){
                min = i;
            }
        }
        return min;
    }
}

```
> 2 votes

# Answer
# SmashAttemptByEquality

The goal is to equalize all the candidats, then SMASH! all the other bots on the last round.
This is a destructive algorith that tries to bug out all the others, to claim the win.

```
public class SmashAttemptByEquality implements Player {
    static private int elections;

    public SmashAttemptByEquality(int e) {
        this.elections = e;
    }

    public String getName() {
        return "SmashAttemptByEquality (on " + String.valueOf(this.elections) + " elections)";
    }

    public int getVote(int[] voteCounts, int votersRemaining, int[] payoffs, int[] totalPayoffs) {

        //if there are no votes or it is a tie
        if(voteCounts.length == 0 || (voteCounts[0] == voteCounts[1] && voteCounts[1] == voteCounts[2]))
        {
            //let the system handle the (distributed?) randomness
            return 3;
        }

        //we want to win, so, lets not mess when there are no voters left
        if( votersRemaining > 0 )
        {
            //lets bring some equality!
            if( voteCounts[0] >= voteCounts[1] )
            {
                if(voteCounts[0] > voteCounts[2])
                {
                    return 2;
                }
                else
                {
                    return 0;
                }
            }
            else if( voteCounts[1] >= voteCounts[2] )
            {
                if(voteCounts[1] > voteCounts[0])
                {
                    return 0;
                }
                else
                {
                    return 1;
                }
            }
            else
            {
                return 0;
            }
        }
        else
        {
            //just play for the winner!
            if( voteCounts[0] >= voteCounts[1] )
            {
                if(voteCounts[0] > voteCounts[2])
                {
                    return 0;
                }
                else
                {
                    return 2;
                }
            }
            else if( voteCounts[1] >= voteCounts[2] )
            {
                if(voteCounts[1] > voteCounts[0])
                {
                    return 1;
                }
                else
                {
                    return 0;
                }
            }
            else
            {
                return 0;
            }
        }
    }

    public void receiveResults(int[] voteCounts, double result) { }
}

```

Notice that this is **untested**!
> 2 votes

# Answer
# **Basic Bot**

Basic Bot just votes for the candidates that isn't eliminated and has the largest maximum payoff from those candidates.

```
public class BasicBot implements Player {
    public BasicBot(int e) { }
    public String getName()
    {
        return "BasicBot";
    }
    public static int getMax(int[] inputArray){
    int maxValue = inputArray[0];
    for(int i=1;i < inputArray.length;i++){
      if(inputArray[i] > maxValue){
         maxValue = inputArray[i];
      }
    }
    return maxValue;
   }
    public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs)
    {
        // Check for Eliminated Candidates
        int eliminated0 = 0;
        int eliminated1 = 0;
        int eliminated2 = 0;
        if( ((voteCounts[0] + votersRemaining) < voteCounts[1]) || ((voteCounts[0] + votersRemaining) < voteCounts[2]))
        {
            eliminated0 = 1;
        }
        if( ((voteCounts[1] + votersRemaining) < voteCounts[0]) || ((voteCounts[1] + votersRemaining) < voteCounts[2]))
        {
            eliminated1 = 1;
        }
        if( ((voteCounts[2] + votersRemaining) < voteCounts[0]) || ((voteCounts[2] + votersRemaining) < voteCounts[1]))
        {
            eliminated2 = 1;
        }
        // Choose the Candidates that is not elimated with the largest payoff
        if ((payoffs[0] == getMax(payoffs)) && eliminated0 == 0)
            return 0
        else if ((payoffs[1] == getMax(payoffs)) && eliminated1 == 0)
            return 1
        else
            return 2

    }

    public void receiveResults(int[] voteCounts, double result)
    {
    }

}

```
> 2 votes

# Answer
## CommunismBot

CommunismBot thinks we should all just get along and pick the candidate who is best for everyone.

```
public class CommunismBot implements Player
{
    Random rnd;
    String name;
    public CommunismBot(int e) {
        rnd = new Random();
        name = "CommunismBot" + rnd.nextInt(1000);
    }

    public String getName()
    {
        return name;
    }

    public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs)
    {
        int maxloc = 0;
        for(int i = 1; i< 3; i++)
        {
            if(totalPayoffs[i] > totalPayoffs[maxloc])
            {
                maxloc = i;
            }
        }
        return maxloc;
    }

    public void receiveResults(int[] voteCounts, double result) { }
}

```

## Hatebot

Hatebot always picks the best candidate. Unless they're a dirty-stinking-party 1. Those guys are awful.

```
import java.util.Random;

public class HateBot implements Player
{
    Random rnd;
    String name;
    public HateBot(int e) {
        rnd = new Random();
        name = "HateBot" + rnd.nextInt(1000); }

    public String getName()
    {
        return name;
    }

    public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs)
    {
        if(payoffs[0]>payoffs[2])
            return 0;
        else
            return 2;
    }

    public void receiveResults(int[] voteCounts, double result) { }
}

```

## StrategicBot

StrategicBot votes for the best candidate provided that they're within one standard deviation of the next best candidate, given the number of voters remaining.

```
import java.util.Random;

public class StrategicBot implements Player
{
    Random rnd;
    String name;
    public StrategicBot(int e) {
        rnd = new Random();
        name = "StrategicBot" + rnd.nextInt(1000);

    }

    public String getName()
    {
        return name;
    }

    public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs)
    {
        double margin = 9.0*votersRemaining/9;
        int maxloc = 0;
        boolean noLead=false;
        for(int i = 1; i< 3; i++)
        {
            for(int j = 1; j < 3; j++)
            {
                if(payoffs[j] + margin > payoffs[i])
                    noLead=true;
            }
            if(payoffs[i] > payoffs[maxloc] && noLead)
            {
                maxloc = i;
            }
            noLead=false;
        }
        return maxloc;
    }

    public void receiveResults(int[] voteCounts, double result) { }
}

```
> 2 votes

# Answer
## Kelly's Favorite

I started with CircumspectBot, but not much is left. Makes a sort of boring guess at the probability distribution of the remaining votes, and then makes the choice that maximizes its own log-utility (Kelly Criterion). Not the speediest, but within the ball park of some of the others. Also, it's fairly competitive with the field (as it stood when I started working on this, and downloaded the other bots).

```
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.HashMap;

public class KellysFavorite implements Player {
    private ArrayList<Double> cache = new ArrayList<Double>();

    public KellysFavorite(int elections) {
        cache.add(0.0);
        double v = 0.0;
        for(int i=1; i<1000; i++) {
            v += Math.log(i);
            cache.add(v);
        }
    }

    @Override
    public String getName() {
        return "Kelly's Favorite";
    }

    private double factln(int n) {
        return cache.get(n);
    }

    private  double binll(int x, int n, double p)
    {
        double ll = 0.0;
        ll += ((double)x)*Math.log(p);
        ll += ((double)(n - x))*Math.log(1.0 - p);
        ll += factln(n) - factln(x) - factln(n-x);
        return ll;
    }

    public  double logAdd(double logX, double logY) {
        // 1. make X the max
        if (logY > logX) {
            double temp = logX;
            logX = logY;
            logY = temp;
        }
        // 2. now X is bigger
        if (logX == Double.NEGATIVE_INFINITY) {
            return logX;
        }
        // 3. how far "down" (think decibels) is logY from logX?
        //    if it's really small (20 orders of magnitude smaller), then ignore
        double negDiff = logY - logX;
        if (negDiff < -20) {
            return logX;
        }
        // 4. otherwise use some nice algebra to stay in the log domain
        //    (except for negDiff)
        return logX + java.lang.Math.log(1.0 + java.lang.Math.exp(negDiff));
    }

    @Override
    public int getVote(int[] voteCounts,
                       int votersRemaining,
                       int[] payoffs,
                       int[] totalPayoffs) {
        int totalviable = 0;
        boolean[] viable = { false, false, false };
        int topVote = Arrays.stream(voteCounts).max().getAsInt();
        for (int index = 0; index < 3; index++) {
            if (voteCounts[index] + votersRemaining + 1 >= topVote) {
                viable[index] = true;
                totalviable += 1;
            }
        }

        // if only one candidate remains viable, vote for them
        if(totalviable == 1) {
            for(int index = 0; index < 3; index++)
                if(viable[index])
                    return index;
        } else {
            double votelikelihoods[] = { 0.0, 0.0, 0.0 };
            double totalweight = 0.0;
            for(int index=0; index<3; index++) {
                if(!viable[index])
                    votelikelihoods[index] -= 10.0;
                else if(voteCounts[index] < topVote)
                    votelikelihoods[index] -= 0.1;

                totalweight += Math.exp(votelikelihoods[index]);
            }

            double probs[] = new double[3];
            for(int index=0; index<3; index++) {
                probs[index] = Math.exp(votelikelihoods[index]) / totalweight;
            }

            double[] utilities = {0,0,0};
            for(int mychoice=0; mychoice<3; mychoice++) {
                boolean seen[] = { false, false, false };
                double likelihoods[] = { Double.NEGATIVE_INFINITY,
                                         Double.NEGATIVE_INFINITY,
                                         Double.NEGATIVE_INFINITY };
                int[] localVoteCounts = { voteCounts[0] + (mychoice==0?1:0),
                                          voteCounts[1] + (mychoice==1?1:0),
                                          voteCounts[2] + (mychoice==2?1:0) };
                for(int iVotes=0; iVotes<=votersRemaining; iVotes++)
                    for(int jVotes=0; jVotes<=(votersRemaining-iVotes); jVotes++) {
                        int kVotes = votersRemaining - iVotes - jVotes;

                        int a = localVoteCounts[0] + iVotes;
                        int b = localVoteCounts[1] + jVotes;
                        int c = localVoteCounts[2] + kVotes;
                        int wincount = Math.max(a, Math.max(b, c));
                        int winners = 0;
                        if(a>=wincount) { winners += 1; }
                        if(b>=wincount) { winners += 1; }
                        if(c>=wincount) { winners += 1; }

                        double likelihood =
                            binll(iVotes, votersRemaining, probs[0])
                            + binll(jVotes, votersRemaining-iVotes, probs[1] / (probs[1] + probs[2]));

                        likelihood += Math.log(1.0/winners);

                        if(a>=wincount) {
                            if(seen[0])
                                likelihoods[0] = logAdd(likelihoods[0],
                                                        likelihood);
                            else
                                likelihoods[0] = likelihood;
                            seen[0] = true;
                        }
                        if(b>=wincount) {
                            if(seen[1])
                                likelihoods[1] = logAdd(likelihoods[1],
                                                        likelihood);
                            else
                                likelihoods[1] = likelihood;
                            seen[1] = true;
                        }
                        if(c>=wincount) {
                            if(seen[2])
                                likelihoods[2] = logAdd(likelihoods[2],
                                                        likelihood);
                            else
                                likelihoods[2] = likelihood;
                            seen[2] = true;
                        }

                    }

                for(int index=0; index<3; index++)
                    utilities[mychoice] += Math.exp(likelihoods[index]) * Math.log((double)payoffs[index]);
            }

            double maxutility = Math.max(utilities[0], Math.max(utilities[1], utilities[2]));
            int choice = 0;
            for(int index=0; index<3; index++)
                if(utilities[index]>=maxutility)
                    choice = index;
            return choice;
        }

        throw new InternalError();
    }

    @Override
    public void receiveResults(int[] voteCounts, double result) {

    }

}

```

Also available at https://gist.github.com/jkominek/dae0b3158dcd253e09e5 in case that's simpler.
> 2 votes

# Answer
# ExpectorBot

Tries to predict how all other Bots will vote by calculating average Payout for the others. Default votes for best payoff, but will vote for second best, if it has more expected votes than the best, a better than average payout for me and the worst-payout has a chance of winning this thing.

```
import java.util.Arrays;

public class ExpectorBot implements Player
{
    class Votee
    {
        int index;
        int payoff;
        float avgPayoff;
        float expectedVotes;
    }

    public ExpectorBot( final int e )
    {

    }

    @Override
    public String getName()
    {
        return "ExpectorBot";
    }

    @Override
    public int getVote( final int[] voteCounts, final int votersRemaining, final int[] payoffs, final int[] totalPayoffs )
    {
        final int otherVoters = Arrays.stream( voteCounts ).sum() + votersRemaining;
        final Votee[] v = createVotees( voteCounts, otherVoters, votersRemaining, payoffs, totalPayoffs );

        final Votee best = v[ 0 ]; // Most Payoff
        final Votee second = v[ 1 ];
        final Votee worst = v[ 2 ];

        int voteFor = best.index;

        if( ( second.expectedVotes >= best.expectedVotes + 1 ) // Second has more votes than Best even after I vote
                && ( second.payoff >= second.avgPayoff ) // Second payoff better than average for the others
                && ( worst.expectedVotes >= best.expectedVotes + 0.5f ) ) // Worst has a chance to win
        {
            voteFor = second.index;
        }

        return voteFor;
    }

    private Votee[] createVotees( final int[] voteCounts, final int otherVoters, final int votersRemaining, final int[] payoffs, final int[] totalPayoffs )
    {
        final Votee[] v = new Votee[ 3 ];

        for( int i = 0; i < 3; ++i )
        {
            v[ i ] = new Votee();
            v[ i ].index = i;
            v[ i ].payoff = payoffs[ i ];

            // This is the average payoff for other Players from this Votee
            v[ i ].avgPayoff = (float)( totalPayoffs[ i ] - payoffs[ i ] ) / otherVoters;

            // The expected number of Votes he will get if everyone votes for biggest payoff
            v[ i ].expectedVotes = voteCounts[ i ] + ( votersRemaining * v[ i ].avgPayoff / 100.0f );
        }

        Arrays.sort( v, ( o1, o2 ) -> o2.payoff - o1.payoff );

        return v;
    }

    @Override
    public void receiveResults( final int[] voteCounts, final double result )
    {

    }
}

```
> 2 votes

# Answer
## LockBot

Just a lonely philosopher, looking for his "e"...

```
//He thinks he's the father of democracy, but something's missing....
public class LockBot implements Player {

public LockBot(int i) {
    //One election, 10000000, what's the difference?
}

@Override
public String getName() {
    return "LockBot";
}

@Override
public int getVote(int[] voteCounts, int votersRemaining, int[] payoffs,
        int[] totalPayoffs) {

    double totalPlayers = voteCounts.length + votersRemaining;
    double totalPayoff = totalPlayers * 100;

    //adjust total payoffs to ignore my own
    for( int i = 0; i < totalPayoffs.length; i++){
        totalPayoffs[i] -= payoffs[i];
    }

    //Votes are probably proportional to payoffs
    //So lets just find the highest weight
    double[] expectedOutcome = new double[3];
    for(int i = 0; i< expectedOutcome.length; i++){
        expectedOutcome[i] = (totalPayoffs[i] / totalPayoff) * payoffs[i];
    }

    //Find the highest
    int choice = 0;
    if(expectedOutcome[1] > expectedOutcome[choice]){
        choice = 1;
    }
    if(expectedOutcome[2] > expectedOutcome[choice]){
        choice = 2;
    }

    return choice;
}

@Override
public void receiveResults(int[] voteCounts, double result) {
    // TODO Auto-generated method stub

}

}

```
> 1 votes

# Answer
# WinLose

If you win, I lose! That simple. So this bot votes for the one that he likes and everyone else dislikes.

```
public class WinLose implements Player
{
    public WinLose(int e) { }

    public String getName()
    {
        return "WinLose";
    }
    public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs)
    {
        int max = 0;
        for(int i = 1; i< 3; i++)
        {
            if(10*payoffs[i]-totalPayoffs[i] > 10*payoffs[max]-totalPayoffs[max])
            {
                max = i;
            }
        }
        return max;
    }

    public void receiveResults(int[] voteCounts, double result)
    {

    }
}

```
> 0 votes

---
Tags: king-of-the-hill, java
---