title: You are the Weakest Link, Goodbye

text:
# Question
Title: You are the Weakest Link, Goodbye
This challenge is based off of the game show, Weakest Link. For those unfamiliar with the show, **the crux of this challenge deals with who you vote off**:

* If the other players are smarter than you, then you have less of a chance of getting the pot.
* If the other players are dumber than you, then you have less of a pot to get.

At the start of each round, the *Pot* starts out with $0. A group of 9 players is formed, and each player is given a unique *Smartness* from 1 to 9.

At the start of each turn, `Pot += Smartness` for each player still in the round. Then, players vote on the player they wish to remove. The player with the most votes is removed. In case of a tie, the smarter player is kept.

When there are only 2 players are left in the round, they face off in a battle of wits. The chance of the player winning is `Smartness/(Smartness+OpponentSmartness)`. The winning player then receives the entire pot.

The player who has received the most money at the end of the game wins.

# Input / Output

Each turn, you will receive the current list of opponents. You will have access to your smartness and **all players' entire voting history** for the round via functions in the Player class.

As output, you must return a single integer, representing the player you wish to vote for (representing their smartness). Voting for yourself *is* allowed (but not recommended).

Rounds of 9 will repeat until all players have played at least ~~1000~~10000 rounds, and all players have played in the same number of rounds.

You can find the controller here: https://github.com/nathanmerrill/WeakestLink

To create a player, you need to extend the Player class, and add your player to the PlayerFactory class. Your class must follow the following rules:

1. Communication or interference with any other player (include your other players of the same type) is strictly prohibited.
2. Reflection and static variables (except for constants) are not allowed.
3. If you want to use randomness, I have provided a `getRandom()` function in the Player class. Use it, so simulations can be deterministic.

I have provided many functions in the Player class for easy access to data. You can find them online on Github. Your player will be instantiated each new round. "Dumb/suicidal" players are allowed (but not players with the same strategy).

# Scores

```
377195  WeakestLink.Players.PrudentSniper
362413  WeakestLink.Players.Sniper
353082  WeakestLink.Players.VengefulSniper
347574  WeakestLink.Players.AntiExtremist
298006  WeakestLink.Players.BobPlayer
273867  WeakestLink.Players.MedianPlayer
247881  WeakestLink.Players.TheCult
240425  WeakestLink.Players.Leech
235480  WeakestLink.Players.SniperAide
223128  WeakestLink.Players.Guard
220760  WeakestLink.Players.Anarchist
216839  WeakestLink.Players.RevengePlayer
215099  WeakestLink.Players.IndependentVoter
213883  WeakestLink.Players.SniperKiller
210653  WeakestLink.Players.MaxPlayer
210262  WeakestLink.Players.Bandwagon
209956  WeakestLink.Players.MeanPlayer
208799  WeakestLink.Players.Coward
207686  WeakestLink.Players.Spy
204335  WeakestLink.Players.Hero
203957  WeakestLink.Players.MiddleMan
198535  WeakestLink.Players.MinPlayer
197589  WeakestLink.Players.FixatedPlayer
197478  WeakestLink.Players.HighOrLowNotSelf
181484  WeakestLink.Players.RandomPlayer
165160  WeakestLink.Players.BridgeBurner

```

# Answer
## Sniper

The general idea is to keep around one of the *stupid players* (i.e. ones we are more likely to beat in the face-off) to snipe for the points. After that we try to remove the other low-value players to raise the pot. But when we get to the intelligent players we opt to remove for the most dangerous ones in case our *stupid player* gets removed. That way if we don't have someone to snipe we should get someone we at least stand a chance against. Also, since we always vote with either a min or max player, I expect we are fairly effective in getting our way.

```
package WeakestLink.Players;
import java.util.Collections;
import java.util.Iterator;
import java.util.Set;
public class Sniper extends Player {
    @Override
    public int vote(Set<Integer> currentOpponents) {
        int smrt = getSmartness();

        //count number of players smarter/stupider than me
        Iterator<Integer> opps = currentOpponents.iterator();
        int cnt_smrt=0, cnt_stpd=0, opp_smrt, min_stpd=10, max_smrt=0;

        while(opps.hasNext()){
            opp_smrt = opps.next().intValue();
            if(opp_smrt > smrt){
                cnt_smrt++;
                if(opp_smrt > max_smrt) max_smrt = opp_smrt;
            }
            else if(opp_smrt < smrt){
                cnt_stpd++;
                if(opp_smrt < min_stpd) min_stpd = opp_smrt;
            }
        }

        //remove low-value, then dangerous players
        if(cnt_stpd>1)
            return min_stpd;
        else
            return max_smrt;
    }
}

```
> 22 votes

# Answer
## TheCult

The cult players have a mildly esoteric voting scheme by which they attempt to identify each other and vote as a group, using only the voting record. Since each member of the cult knows how to vote, anyone who votes differently is revealed as a non-member and eventually targeted for elimination.

**The voting scheme at a glance:**

* on the first turn vote for weakest contestant, working in concert with min & sniper helps the cult gain power
* on subsequent turns vote off known non-members until only the cult remains (we vote off the lowest-value non-member to rack up points as long as we think we are in control).
* when only members remain, vote off low-value members for points (indeed sacrificing yourself for the good of the cult).

**The Code:**

```
package WeakestLink.Players;
import WeakestLink.Game.Vote;
import java.util.Iterator;
import java.util.Set;
public class TheCult extends Player {
    private int cult_vote;
    private boolean[] isMember = null;
    @Override
    public int vote(Set<Integer> currentOpponents) {
        //on first turn, vote the code
        if(isMember == null){
            isMember = new boolean[10];
            for(int i=10; --i!=0;) isMember[i]=true; //runs 9-1
            return cult_vote = 1;
        }
        //on all other turn, assess who is not voting with the cult
        Vote opp_vote;
        int cult_cnt=0;
        Iterator<Vote> votes = getRecentVotes().iterator();
        while(votes.hasNext()){
            opp_vote = votes.next();
            if(opp_vote.getVoted() != cult_vote)
                isMember[opp_vote.getVoter()] = false;
            else
                cult_cnt++;
        }
        //find weakest and stongest non-members, and weakest members
        Iterator<Integer> opps = currentOpponents.iterator();
        int opp_smrt, min_mem=10, min_non=10, max_non=0;
        while(opps.hasNext()){
            opp_smrt = opps.next().intValue();
            if(isMember[opp_smrt]){
                if(opp_smrt < min_mem) min_mem = opp_smrt;
            }else{
                if(opp_smrt < min_non) min_non = opp_smrt;
                if(opp_smrt > max_non) max_non = opp_smrt;
            }
        }
        if(cult_cnt>2 && min_non!=10) cult_vote = min_non;
        else if(max_non!=0)           cult_vote = max_non;
        else                          cult_vote = min_mem;
        return cult_vote;
    }
}

```

**Final Thoughts:**

The cult now switch's to voting for the most dangerous players when there are only two or fewer cult-members remaining for the face-off. I tested it several times with `cult_cnt>1` and `cult_cnt>2` conditions and the later wins more often.

Still, this is a precaution and the cult really isn't designed to work as lone player, so as the number of new players increase the cult should still lose eventually.
> 12 votes

# Answer
# PrudentSniper

Sniper, but with two special-case behaviors. One is that if there are three bots left, and PrudentSniper is the smartest, it will vote for the middle bot instead of the least smart. This allows it to win a few more showdowns. The other behavior is that if the smartest bot is gunning for it (voted for it or the analogous bot last time) and the least smart isn't, it will vote for the smartest in self defense.

```
package WeakestLink.Players;
import WeakestLink.Game.Vote;
import java.util.Collections;
import java.util.Iterator;
import java.util.Set;
public class PrudentSniper extends Player {
    @Override
    public int vote(Set<Integer> currentOpponents) {
        int smrt = getSmartness();

        //count number of players smarter/stupider than me, find max/min
        Iterator<Integer> opps = currentOpponents.iterator();
        int cnt_smrt=0, cnt_stpd=0, opp_smrt, min_stpd=10, max_smrt=0;

        while(opps.hasNext()){
            opp_smrt = opps.next().intValue();
            if(opp_smrt > max_smrt) max_smrt = opp_smrt;
            if(opp_smrt < min_stpd) min_stpd = opp_smrt;
            if(opp_smrt > smrt){
                cnt_smrt++;
            }
            else if(opp_smrt < smrt){
                cnt_stpd++;
            }
        }

        //identify enemies
        Iterator<Vote> votes = getRecentVotes().iterator();
        boolean[] voted_for_me = new boolean[9];

        while(votes.hasNext()) {
          Vote opp_vote = votes.next();
          voted_for_me[opp_vote.getVoter()] = (opp_vote.getVoted() == getSmartness() ||
                                              (opp_vote.getVoted() < getSmartness() && cnt_stpd < 1) ||
                                              (opp_vote.getVoted() > getSmartness() && cnt_smrt < 1));
        }

        if (currentOpponents.size() < 3 || cnt_stpd < 2 || (voted_for_me[max_smrt] && !voted_for_me[min_stpd] && cnt_smrt > 0) )
          return max_smrt;
        else
          return min_stpd;
    }
}

```
> 12 votes

# Answer
# BridgeBurner

Not somewhere where I can test this right now, and this came out feeling like really ugly/dumb code, but it *should* work.

This bot just wants to be hated. It votes for whoever has voted against it the *least*. In the event of a tie, it picks whoever has gone the longest without voting for it. In the event of another tie, it picks the smartest of those (presumably because they will make the worst enemy). It will not vote for itself, because no one will really hate it when it's not around.

```
package WeakestLink.Players;

import WeakestLink.Game.Vote;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class BridgeBurner extends Player{
    @Override
    public int vote(Set<Integer> currentOpponents) {
        List<Integer> votes_against = Stream.generate(() -> 0).limit(9).collect(Collectors.toList());
        List<Integer> last_voted_against = Stream.generate(() -> 0).limit(9).collect(Collectors.toList());
        Iterator<Vote> votes_against_me = getVotesForSelf().iterator();

        for (int c = 0; c < 9; c++){
            if (!currentOpponents.contains(c)){
                votes_against.set(c,-1);
                last_voted_against.set(c,-1);
            }
        }

        while(votes_against_me.hasNext()){
            Vote vote = votes_against_me.next();

            int voter = vote.getVoter();
            int round = vote.getRound();

            if (currentOpponents.contains(voter)){
                votes_against.set(voter, votes_against.get(voter)+1);
                last_voted_against.set(voter, Math.max(round, last_voted_against.get(voter)));
            } else {
                votes_against.set(voter, -1);
                last_voted_against.set(voter, -1);
            }
        }

        int min_tally = Collections.max(votes_against);
        for (int c = 0; c < 9; c++){
            int current_tally = votes_against.get(c);
            if (current_tally != -1 && current_tally < min_tally){
                min_tally = current_tally;
            }
        }

        if (Collections.frequency(votes_against, min_tally) == 1){
            return votes_against.indexOf(min_tally);
        } else {
            List<Integer> temp_last_against = new ArrayList<>();
            for (int c = 0; c < 9; c++){
                if (votes_against.get(c) == min_tally){
                    temp_last_against.add(last_voted_against.get(c));
                }
            }
            return last_voted_against.lastIndexOf(Collections.min(temp_last_against));
        }
    }
}

```
> 7 votes

# Answer
# RevengePlayer

This bot will vote for whoever voted for him the most times, tiebreaker being the smartest player. The theory is that a player that voted for you in the past will likely vote for you again.

```
package WeakestLink.Players;
import java.util.Collections;
import java.util.Set;
import java.util.Iterator;
import WeakestLink.Game.Vote;
public class RevengePlayer extends Player{

    @Override
    public int vote(Set<Integer> opponents) {
        int[] A;
        A = new int[10];
        for(int i = 1;i < 10;i++)
            A[i] = opponents.contains(i)? i+1 : 0;
        Set<Vote> H = getVotingHistory();
        Iterator<Vote> I = H.iterator();
        while(I.hasNext()){
            Vote v = I.next();
            if(v.getVoted() == getSmartness())
                A[v.getVoter()] += A[v.getVoter()] != 0?10:0;
        }
        int maxI = 0;
        for(int i = 1;i < 10;i++)
            if(A[i] > A[maxI])
                maxI = i;
        return maxI;
    }
}

```
> 6 votes

# Answer
# Bandwagon

Follows the crowd in voting, unless he's the one being targeted.

```
package WeakestLink.Players;

import WeakestLink.Game.Vote;
import java.util.Map;
import java.util.Set;

/**
 * Votes for the currently most voted bot in the game. Or the lowest one.
 */
public class Bandwagon
        extends Player {

    @Override
    public int vote(Set<Integer> currentOpponents) {
        int self = getSmartness(), vote = -1;
        java.util.Map<Integer, Integer> votes = new java.util.TreeMap<>();
        getVotingHistory().stream().map((Vote v)-> v.getVoted()).filter((Integer i)-> !i.equals(self)).forEach((Integer tgt)-> {
            if(!votes.containsKey(tgt)) {
                votes.put(tgt, 1);
            } else {
                votes.put(tgt, votes.get(tgt) + 1);
            }
        });

        do {
            if(votes.entrySet().isEmpty()) {
                vote = currentOpponents.stream().filter((Integer i)-> !i.equals(self)).sorted().findFirst().get();
            } else {
                if(votes.containsKey(vote)) {
                    votes.remove(vote);
                    vote = -1;
                }

                for(Map.Entry<Integer, Integer> vv: votes.entrySet()) {
                    Integer key = vv.getKey();
                    Integer value = vv.getValue();

                    if((vote == -1) || (value > votes.get(vote))) {
                        vote = key;
                    }
                }
            }
        } while(!currentOpponents.contains(vote));

        return vote;
    }
}

```

I'm guessing this one will just make snipers stronger by following them, but also avoids being targeted by the cult and sniper-aides in a slightly effective manner. It may as well be a meatshield for sniper killers or aid them if there's more of them. (Need to test with the latest updates).

Using java 8 features because the game needs that to run anyway.
> 6 votes

# Answer
# MeanPlayer

Vote neither the stupidest nor the smartest players, and he's carrying a gun (sneaked it past security)

```
public class MeanPlayer extends Player{

    @Override
    public int vote(Set<Integer> currentOpponents) {
        int mid = currentOpponents.size() / 2;
        Object[] sortedOpponents = currentOpponents.toArray();
        Arrays.sort(sortedOpponents);
        return (int) sortedOpponents[mid];
    }
}

```
> 5 votes

# Answer
# AntiExtremist

This extreme socialist believes that all people should be of equal smartness. He tries to kill those who are much smarter or dumber than he is. He considers both but he favors dumb in general. He favors dumb people in the beginning and smart in the end, but it's weighted based on how extreme those people are.

```
package WeakestLink.Players;
import java.util.Arrays;
import java.util.Set;

public class AntiExtremist extends Player {

    Object[] currentPlayers;

    @Override
    public int vote(Set<Integer> currentOpponents) {

        currentPlayers = (Object[]) currentOpponents.toArray();
        Arrays.sort(currentPlayers);

        int smartness = getSmartness();
        int turns = getTurnNumber();

        //// Lets get an idea of who's smart and who's dumb ////

        int smarter = 0, dumber = 0;

        int max_smart = 0, min_smart = 10;

        currentOpponents.toArray();

        for (int i = 0; i < currentPlayers.length; i++) {
            int osmart = (int)currentPlayers[i];

            if (osmart == smartness)
                continue;

            if (osmart > smartness) {
                smarter++;

                if (osmart > max_smart)
                    max_smart = osmart;
            }
            else if (osmart < smartness) {
                dumber++;

                if (osmart < min_smart)
                    min_smart = osmart;
            }

        }

        // int total = smarter+dumber;

        double smarter_ratio = smarter > 0 ? (max_smart-smartness)/4.5 : 0;
        double dumber_ratio = dumber > 0 ? (smartness-min_smart)/3.0 : 0;//Favor dumber

        smarter_ratio*=.25+(turns/9.0*.75);
        dumber_ratio*=1-(turns/8.0*.75);

        return smarter_ratio > dumber_ratio ? max_smart : min_smart;

    }

}

```

**NOTE:** According to Linus this will vote the same as sniper the vast majority of the time (525602:1228).
> 5 votes

# Answer
# MedianPlayer

This player attempt to be the meanest (well, medianness) one left.

It votes to eliminate the smartest and dumbest opponents (with a slight bias towards voting off the smartest), depending on if there are more or less smarter/dumber than themself.

```
package WeakestLink.Players;
import java.util.Collections;
import java.util.Iterator;
import java.util.Set;
public class MedianPlayer extends Player {
  @Override
  public int vote(Set<Integer> currentOpponents) {
    int smrt = getSmartness();

    //count number of players smarter/stupider than me
    Iterator<Integer> opps = currentOpponents.iterator();
    int cnt_smrt=0, cnt_stpd=0, min_stpd=10, max_smrt=0;

    while(opps.hasNext()){
      int opp_smrt = opps.next().intValue();
      if(opp_smrt > smrt){
        cnt_smrt++;
        if(opp_smrt > max_smrt)
          max_smrt = opp_smrt;
      } else if(opp_smrt < smrt){
        cnt_stpd++;
        if(opp_smrt < min_stpd)
          min_stpd = opp_smrt;
      }
    }

    // the middle must hold
    if(cnt_stpd>cnt_smrt)
      return min_stpd;
    else
      return max_smrt;
  }
}

```

framework blatantly stolen from @Linus above.
> 4 votes

# Answer
# Coward

```
package WeakestLink.Players;
import WeakestLink.Game.Vote;
import java.util.Collections;
import java.util.Iterator;
import java.util.Set;
public class Coward extends Player {
  @Override
  public int vote(Set<Integer> currentOpponents) {

    boolean[] currentOpponent = new boolean[10];

    Iterator<Integer> opps = currentOpponents.iterator();
    while(opps.hasNext()){
      currentOpponent[opps.next().intValue()] = true;
    }

    int[] voteCounts = new int[9];
    for(int i=0; i<9; i++) {
        voteCounts[i] = 0;
    }

    Iterator<Vote> votes = getRecentVotes().iterator();

    while(votes.hasNext()){
      Vote opp_vote = votes.next();
      if(currentOpponent[opp_vote.getVoter()])
        voteCounts[opp_vote.getVoted()] += 1;
      else
        voteCounts[opp_vote.getVoter()] += 100;
    }

    int previous_weakest = -1;
    int max_votes_gotten = 0;
    for(int i=0;i<9;i++){
      if (voteCounts[i] > max_votes_gotten) {
        max_votes_gotten = voteCounts[i];
        previous_weakest = i;
      }
    }
    int min_closeness = 10;
    int to_vote = -1;
    int opp;
    int closeness;
    opps = currentOpponents.iterator();
    while(opps.hasNext()){
      opp = opps.next();
      closeness = Math.abs(opp - previous_weakest);
      if(closeness <= min_closeness) {
        to_vote = opp;
        min_closeness = closeness;
      }
    }

    return to_vote;

  }
}

```

Just doesn't want to get voted off, so votes for the opponent most similar to the player that got voted off last round in order to maximize the chance of being on the winning team.

Doesn't do particularly well right now, but might as well throw it in the mix.
> 4 votes

# Answer
# Hero

Votes off those who pick on the weak ... or annoy him.

```
package WeakestLink.Players;

import WeakestLink.Game.Game;
import WeakestLink.Game.Vote;

import java.util.*;

/**
 * Created by thenumberone on 12/2/15.
 * @author thenumberone
 */
public class Hero extends Player{

    @Override
    public int vote(Set<Integer> currentOpponents) {
        int me = getSmartness();
        Set<Vote> history = getVotingHistory();
        history.removeIf(vote -> !currentOpponents.contains(vote.getVoter()) || vote.getVoter() == me);
        int[] evilnessLevel = new int[Game.NUMBER_PLAYERS_PER_ROUND];
        for (Vote vote : history){
            evilnessLevel[vote.getVoter()] += vote.getVoted() == me ? 1_000_000 : Game.NUMBER_PLAYERS_PER_ROUND - vote.getVoted();
        }
        int mostEvilOpponent = -1;
        for (int opponent : currentOpponents){
            if (mostEvilOpponent == -1 || evilnessLevel[opponent] > evilnessLevel[mostEvilOpponent]){
                mostEvilOpponent = opponent;
            }
        }
        return mostEvilOpponent;
    }
}

```
> 4 votes

# Answer
# FixatedPlayer

Picks a random target, then votes for them until they're gone. Won't vote for himself though.

```
package WeakestLink.Players;

import WeakestLink.Game.Vote;

import java.util.*;

public class FixatedPlayer extends Player{
    @Override
    public int vote(Set<Integer> currentOpponents) {
        int self = getSmartness();
        Vote previous_vote = getLastVote();
        if (previous_vote == null || !currentOpponents.contains(previous_vote.getVoted())){
            return (int) currentOpponents.toArray()[getRandom().nextInt(currentOpponents.size())];
        }
        else {
            return previous_vote.getVoted();
        }
    }
}

```
> 4 votes

# Answer
## Bob

Bob is just the average guy that thinks he is smarter then he really is. Cannot win the *sniper* family but get top 5 in my simulations most of the time.

```
package WeakestLink.Players;

import java.util.Collections;
import java.util.Set;

import WeakestLink.Game.Vote;

public class BobPlayer extends Player {

    @Override
    public int vote(Set<Integer> currentOpponents) {
        int smartness;

        // Bob sometimes thinks he is smarter than he really is
        if (getRandom().nextInt(10) == 0) {
            smartness = 10;
        } else {
            smartness = getSmartness();
        }

        // If there is still some competition
        if (currentOpponents.size() > 3) {
            // And Bob is the dumbest
            if (smartness < Collections.min(currentOpponents)) {
                // Go for the smartest one
                return Collections.max(currentOpponents);
                // But if he is the smartest
            } else if (smartness > Collections.max(currentOpponents)) {
                // Go for the weak link
                return Collections.min(currentOpponents);
            } else {
                // Else revenge!
                for (Vote v : getRecentVotes()) {
                    if (v.getVoted() == smartness && currentOpponents.contains(v.getVoter())) {
                        return v.getVoter();
                    }
                }
            }
            return Collections.min(currentOpponents);
        } else {
            //If there are few opponents just revenge!
            for (Vote v : getRecentVotes()) {
                if (v.getVoted() == smartness && currentOpponents.contains(v.getVoter())) {
                    return v.getVoter();
                }
            }
            return Collections.max(currentOpponents);
        }
    }

}

```
> 4 votes

# Answer
# Spy

Spy is reserved. He doesn't like to gun for the smartest people. Likewise, he doesn't like picking on ~~quartata~~ defenseless idiots. So, he likes to eliminate those closest to him in smartness.

```
package WeakestLink.Players;

import java.util.Iterator;
import java.util.Set;

public class Spy extends Player{
  @Override
  public int vote(Set<Integer> currentOpponents) {
    int selfIntel = getSmartness();
    int closestIntel = 100; // default
    // get closest player
    Iterator<Integer> enemies = currentOpponents.iterator();
    while(enemies.hasNext()){
      int enemyIntel = enemies.next().intValue();
      if(Math.abs(enemyIntel - selfIntel) < closestIntel) closestIntel = enemyIntel;
    }
    return closestIntel;
  }
}

```

You've just been backstabbed, *mes amis*. He doesn't care if he wins. He just like the sound of the knife in your back as he votes you off successfully.
> 4 votes

# Answer
# Statistics

This is not an entry to the contest. This is merely a way to get useful statistics of a game. These statistics print off the percentage likelihood that a particular player will be voted off in a round.

To do this add the following lines to `Round.java` so that the top of the file looks like this:

```
package WeakestLink.Game;

import WeakestLink.Players.Player;

import java.util.*;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Round {

    private static int[][] statistics = new int[Game.NUMBER_PLAYERS_PER_ROUND - 2][Game.NUMBER_PLAYERS_PER_ROUND + 1];
    private static int[] counts = new int[Game.NUMBER_PLAYERS_PER_ROUND - 2];

    static {
        Runtime.getRuntime().addShutdownHook(new Thread(() -> {
            for (int i = 0; i < Game.NUMBER_PLAYERS_PER_ROUND - 2; i++){
                System.out.println();
                System.out.println("For " + (i+1) + "th round:");
                for (int j = 1; j <= Game.NUMBER_PLAYERS_PER_ROUND; j++){
                    System.out.println(String.format("%f%% voted for %d", 100.0*statistics[i][j]/counts[i], j));
                }
            }
        }));
    }

...

```

Then modify the vote method to look like this:

```
private Vote vote(Player player){
    player.setVotingHistory(new HashSet<>(votes));
    player.setTurnNumber(currentTurn);
    player.setPot(pot);
    Set<Integer> players = currentPlayers.stream()
            .filter(p -> p != player)
            .map(playerToSmartness::get)
            .collect(Collectors.toSet());
    int vote = player.vote(players);
    if (!currentPlayers.contains(smartnessToPlayer.get(vote))){
        throw new RuntimeException(player.getClass().getSimpleName()+" voted off non-existent player");
    }
    Vote v = new Vote(playerToSmartness.get(player), vote, currentTurn);
    counts[v.getRound()]++;
    statistics[v.getRound()][v.getVoted()]++;
    return v;
}

```

Example Output:

```
For 1th round:
55.554756% voted for 1
4.279166% voted for 2
1.355189% voted for 3
1.778786% voted for 4
3.592771% voted for 5
3.952368% voted for 6
1.779186% voted for 7
6.427149% voted for 8
21.280630% voted for 9

For 2th round:
2.889877% voted for 1
34.080927% voted for 2
6.826895% voted for 3
4.990010% voted for 4
5.914753% voted for 5
4.985510% voted for 6
3.302524% voted for 7
11.304360% voted for 8
25.705144% voted for 9

For 3th round:
2.152783% voted for 1
13.005153% voted for 2
21.399772% voted for 3
7.122286% voted for 4
6.122008% voted for 5
6.761774% voted for 6
11.687049% voted for 7
19.607500% voted for 8
12.141674% voted for 9

For 4th round:
2.122183% voted for 1
10.105719% voted for 2
11.917105% voted for 3
17.547460% voted for 4
8.626131% voted for 5
12.079103% voted for 6
18.819449% voted for 7
11.065111% voted for 8
7.717738% voted for 9

For 5th round:
1.689826% voted for 1
7.364821% voted for 2
9.681763% voted for 3
11.704946% voted for 4
20.336237% voted for 5
20.691914% voted for 6
13.062855% voted for 7
9.332565% voted for 8
6.135071% voted for 9

For 6th round:
1.456188% voted for 1
6.726546% voted for 2
10.154619% voted for 3
16.355569% voted for 4
22.985816% voted for 5
17.777558% voted for 6
11.580207% voted for 7
7.757938% voted for 8
5.205558% voted for 9

For 7th round:
1.037992% voted for 1
6.514748% voted for 2
15.437876% voted for 3
22.151823% voted for 4
17.015864% voted for 5
14.029088% voted for 6
11.907505% voted for 7
7.957136% voted for 8
3.947968% voted for 9

```
> 4 votes

# Answer
# MaxPlayer

A know-it-all. Prefers to remove anybody with high-intelligence (who can therefore challenge his unmatched intellect)

```
public class MaxPlayer extends Player{

    @Override
    public int vote(Set<Integer> currentOpponents) {
        return Collections.max(currentOpponents);
    }
}

```
> 3 votes

# Answer
# Guard

Votes off those that pick on the strong ... or those that annoy him.

```
package WeakestLink.Players;

import WeakestLink.Game.Game;
import WeakestLink.Game.Vote;

import java.util.Set;

/**
 * Created by thenumberone on 12/2/15.
 * @author thenumberone
 */
public class Guard extends Player{

    @Override
    public int vote(Set<Integer> currentOpponents) {
        int me = getSmartness();
        Set<Vote> history = getVotingHistory();
        history.removeIf(vote -> !currentOpponents.contains(vote.getVoter()) || vote.getVoter() == me);
        int[] evilnessLevel = new int[Game.NUMBER_PLAYERS_PER_ROUND];
        for (Vote vote : history){
            evilnessLevel[vote.getVoter()] += vote.getVoted() == me ? 1_000_000 : vote.getVoted();
        }
        int mostEvilOpponent = -1;
        for (int opponent : currentOpponents){
            if (mostEvilOpponent == -1 || evilnessLevel[opponent] > evilnessLevel[mostEvilOpponent]){
                mostEvilOpponent = opponent;
            }
        }
        return mostEvilOpponent;
    }
}

```
> 3 votes

# Answer
# Leech

Relies on other bots to vote the smartest and dumbest guys off.. sort of.

He is satisfied with turning up somewhere in the middle and eventually splitting the pot with the winner (since he is actually a really decent ~~guy~~ bot).

```
package WeakestLink.Players;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Set;

public class Leech extends Player {
    /**
     * Copyrighted (not really, use this however you want friends) by Sweerpotato :~)!
     */
    @Override
    public int vote(Set<Integer> currentOpponents) {
        int mySmartness = getSmartness();

        ArrayList<Integer> opponentSmartness = new ArrayList<Integer>();
        opponentSmartness.addAll(currentOpponents);
        opponentSmartness.add(mySmartness);
        Collections.sort(opponentSmartness);

        if(mySmartness > 4 && mySmartness > Collections.min(opponentSmartness)) {
            //There's somebody dumber than me, vote that dude off
            return opponentSmartness.get(opponentSmartness.indexOf(mySmartness) - 1);
        }
        else {
            //Vote off the smartest guy, so we have a better chance to win
            if(mySmartness == Collections.max(opponentSmartness)) {
                //Apparently, we're the smartest guy
                return opponentSmartness.get(opponentSmartness.indexOf(mySmartness) - 1);
            }
            else {
                return Collections.max(opponentSmartness);
            }
        }
    }
}

```
> 3 votes

# Answer
# SniperKiller

Another answer shamelessly stolen from Linus's code. This one in will kill all snipers, not protect them. If it knows that no snipers are left it will act like a sniper itself.

```
package WeakestLink.Players;
import WeakestLink.Game.Vote;
import java.util.Collections;
import java.util.Iterator;
import java.util.Set;

public class SniperKiller extends Player {
    boolean[] sniperish;
    int[] sniperwouldvote;

    @Override
    public int vote(Set<Integer> currentOpponents) {
        int smrt = getSmartness();
        currentOpponents.add(smrt);
        if(sniperish==null){
            sniperish = new boolean[10];
            sniperwouldvote = new int[10];
            for(int i=10;--i!=0;){
                sniperish[i] = true;
                sniperwouldvote[i] = 1;
            }
            sniperish[smrt]=false; //knows we are not the sniper
            return 1;
        }
        //figure out who isn't a sniper
        Vote opp_vote;
        int opp_smrt;
        Iterator<Vote> votes = getRecentVotes().iterator();
        while(votes.hasNext()){
            opp_vote = votes.next();
            opp_smrt = opp_vote.getVoter();
            if(opp_vote.getVoted() != sniperwouldvote[opp_smrt])
                sniperish[opp_smrt] = false;
        }
        //figure out how snipers would vote this round
        Iterator<Integer> opps = currentOpponents.iterator();
        int cnt_opp=0, min_opp=10, max_opp=0;
        int[] snpr_votes = new int[10];
        while(opps.hasNext()){
            opp_smrt = opps.next().intValue();
            if(smrt == opp_smrt) continue;
            sniperwouldvote[opp_smrt] = hypothetically(opp_smrt, currentOpponents);
            cnt_opp++;
            if(sniperish[opp_smrt]){
                snpr_votes[sniperwouldvote[opp_smrt]]++;
            }
            if(opp_smrt<min_opp) min_opp=opp_smrt;
            if(opp_smrt>max_opp) max_opp=opp_smrt;
        }
        for(int i = 1;i<10;i++){//hit the weakest sniper.
            if(sniperish[i] && currentOpponents.contains(i))
                return i;
        }
        return hypothetically(smrt, currentOpponents);
    }

    private int hypothetically(int smrt, Set<Integer> currentOpponents) {
        Iterator<Integer> opps = currentOpponents.iterator();
        int cnt_smrt=0, cnt_stpd=0, opp_smrt, min_stpd=10, max_smrt=0;
        while(opps.hasNext()){
            opp_smrt = opps.next().intValue();
            if(opp_smrt > smrt){
                cnt_smrt++;
                if(opp_smrt > max_smrt) max_smrt = opp_smrt;
            }
            else if(opp_smrt < smrt){
                cnt_stpd++;
                if(opp_smrt < min_stpd) min_stpd = opp_smrt;
            }
        }
        if(cnt_stpd>1) return min_stpd;
        return max_smrt;
    }
}

```
> 3 votes

# Answer
# RandomPlayer

```
public class RandomPlayer extends Player{

    @Override
    public int vote(Set<Integer> currentOpponents) {
        return (int) currentOpponents.toArray()[getRandom().nextInt(currentOpponents.size())];
    }
}

```
> 2 votes

# Answer
# MinPlayer

An Elitist. Prefers to remove anybody with low intelligence.

```
public class MinPlayer extends Player {

    @Override
    public int vote(Set<Integer> currentOpponents) {
        return Collections.min(currentOpponents);
    }
}

```
> 2 votes

# Answer
# ApproximatePosition

This bot is trying to shooting approximately around the missing smartness values, assuming that the group will continue with the same pattern, meaning it will target the same type of target. It always vote for the smartest of two player when there's a choice.

Long time I didn't use Java, and currently at work so... Can't test it, hope it's not too buggy, be gentle please :).

By the way, it uses awt.Point only because I'm too lazy to implement a tuple n\_n.

```
package WeakestLink.Players;
import WeakestLink.Game.Vote;

import java.util.*;
import java.awt.Point;

public class ApproximatePosition extends Player
{

    @Override
    public int vote(Set<Integer> currentOpponent)
    {
        List<Integer> present = new ArrayList<>(currentOpponent);
        List<Integer> emptyPosition = new ArrayList<Integer>();
        Collections.sort(present);

        //If it is the first round, vote for the smartest buddy
        if(present.size()==8)
            return present.get(present.size()-1);

        int lastCheck=present.get(0);
        if(lastCheck>0)
            for(int i=0;i<lastCheck;i++)
                if(i!=getSmartness()&&!emptyPosition.contains(i))
                    emptyPosition.add(i);
        for(int i=1;i<present.size();i++)
        {
            if(present.get(i)-lastCheck>1)
                for (int j=lastCheck+1;j<present.get(i);j++)
                    if(j!=getSmartness()&&!emptyPosition.contains(j))
                        emptyPosition.add(j);
            lastCheck=present.get(i);
        }
        //untill there's at least 3 excluded members, we continue with this behaviour
        if(emptyPosition.size()<=2)
        {
            if(emptyPosition.isEmpty()) return present.get(present.size()-1);
            return decide(emptyPosition.get(0),present.get(present.size()-1),present.get(0),present);
        }

        Point maxRangeOfBlank=new Point(present.get(present.size()-1),present.get(present.size()-1));
        for (int i=0;i<emptyPosition.size()-1;i++)
            if(emptyPosition.get(i+1)-emptyPosition.get(i)==1)
            {
                int size=0;
                while(i+size+1<emptyPosition.size() && emptyPosition.get(i+size+1)-emptyPosition.get(i+size)==1)
                    size++;
                if(size>=sizeOfRange(maxRangeOfBlank))
                    maxRangeOfBlank=new Point(emptyPosition.get(i),emptyPosition.get(size));
                i+=size;
            }

        return decide(maxRangeOfBlank,present.get(present.size()-1),present.get(0),present);
    }

    private int decide(int blankSeat, int smartest,int dumbest,List<Integer> present)
    {
        return decide(new Point(blankSeat,blankSeat),smartest,dumbest,present);
    }

    private int decide(Point rangeBlankSeat, int smartest,int dumbest,List<Integer> present)
    {
        int target= smartest;
        if (rangeBlankSeat.getY()==smartest||((int)rangeBlankSeat.getY()+1)==getSmartness()){
            if ((rangeBlankSeat.getX()==dumbest||(int)rangeBlankSeat.getX()-1==getSmartness())){
                target= smartest; //should not happen
            } else {
                target= (int) rangeBlankSeat.getX()-1; //Vote for dumber than the missing
            }
        } else {
            target= (int) rangeBlankSeat.getY() +1; //Vote for smarter than the missing, default comportment
        }
        if(present.contains(target))
            return target;
        return smartest;
    }
    //Return the number of consecutive values between X and Y (included)
    private int sizeOfRange(Point range)
    {
        return (int)(range.getY()-range.getX())+1;
    }

}

```
> 2 votes

# Answer
## SniperAide

Before the addition of PrudentSniper I wrote a bot to help Sniper beat AntiExtremist and other *frauds* (I use the word with love). The bot, SniperAide, looks for players who vote like snipers and votes as it thinks they would when there is a consensuses. If all players look like snipers he votes for the max, protecting lower Snipers (who would also switch to the max at this point), even if it is himself.

**The Code**:

```
package WeakestLink.Players;
import WeakestLink.Game.Vote;
import java.util.Collections;
import java.util.Iterator;
import java.util.Set;

public class SniperAide extends Player {
    boolean[] sniperish;
    int[] sniperwouldvote;

    @Override
    public int vote(Set<Integer> currentOpponents) {
        int smrt = getSmartness();
        if(sniperish==null){
            sniperish = new boolean[10];
            sniperwouldvote = new int[10];
            for(int i=10;--i!=0;){
                sniperish[i] = true;
                sniperwouldvote[i] = 1;
            }
            sniperish[smrt]=false; //knows we are not the sniper
            return 1;
        }
        //figure out who might isn't a sniper
        Vote opp_vote;
        int opp_smrt;
        Iterator<Vote> votes = getRecentVotes().iterator();
        while(votes.hasNext()){
            opp_vote = votes.next();
            opp_smrt = opp_vote.getVoter();
            if(opp_vote.getVoted() != sniperwouldvote[opp_smrt])
                sniperish[opp_smrt] = false;
        }
        //include ourself in the simulation of other snipers.
        currentOpponents.add(smrt);
        //figure out how snipers would vote this round
        Iterator<Integer> opps = currentOpponents.iterator();
        int cnt_snpr=0, cnt_opp=0, min_opp=10, max_opp=0;
        int[] snpr_votes = new int[10];
        while(opps.hasNext()){
            opp_smrt = opps.next().intValue();
            if(smrt == opp_smrt) continue;
            sniperwouldvote[opp_smrt] = hypothetically(opp_smrt, currentOpponents);
            cnt_opp++;
            if(sniperish[opp_smrt]){
                cnt_snpr++;
                snpr_votes[sniperwouldvote[opp_smrt]]++;
            }
            if(opp_smrt<min_opp) min_opp=opp_smrt;
            if(opp_smrt>max_opp) max_opp=opp_smrt;
        }
        //figure out how to vote in sniper's intrest when not identified
        if(cnt_snpr == cnt_opp)
            return max_opp;
        if(cnt_snpr == 0)
            return hypothetically(smrt, currentOpponents);
        //if multiple hypothetical snipers only vote how they agree
        int onlyvote = -1;
        for(int i=10; --i!=0;){
            if(onlyvote>0 && snpr_votes[i]!=0) onlyvote=-2;
            if(onlyvote==-1 && snpr_votes[i]!=0) onlyvote=i;
        }
        if(onlyvote>0) return onlyvote;
        return max_opp;
    }

    private int hypothetically(int smrt, Set<Integer> currentOpponents) {
        Iterator<Integer> opps = currentOpponents.iterator();
        int cnt_smrt=0, cnt_stpd=0, opp_smrt, min_stpd=10, max_smrt=0;
        while(opps.hasNext()){
            opp_smrt = opps.next().intValue();
            if(opp_smrt > smrt){
                cnt_smrt++;
                if(opp_smrt > max_smrt) max_smrt = opp_smrt;
            }
            else if(opp_smrt < smrt){
                cnt_stpd++;
                if(opp_smrt < min_stpd) min_stpd = opp_smrt;
            }
        }
        if(cnt_stpd>1) return min_stpd;
        return max_smrt;
    }
}

```

He currently is not much help against PrudentSniper.
> 2 votes

# Answer
## HighOrLowNotSelf

Removes randomly lowest or highest intelligence player (but not self).

```
public class HighOrLowNotSelf extends Player{
    @Override
    public int vote(Set<Integer> ops) {
        int b=Math.round(Math.random()*1);
        int p;
        if(b==1) p=Collections.max(ops) else p=Collections.min(ops);
        if(p==getSmartness()) {
            return vote(ops);
        }
        return p;
    }
}

```
> 2 votes

# Answer
# VengefulSniper

This started as something I *thought* was original called `StupidBuffering` (a name I hated to give up), then ended up being just a PrudentSniper who didn't care if he was being targeted. This also seemed to be the only reason he couldn't beat PrudentSniper, so I tweaked things around a bit to make that his focus.

Now, this is basically a sniper, but if the smartest or dumbest bot targets him, he will target whichever one got the most votes last round. If they both got the same number of votes and both targeted him, he goes back to normal sniper-y behavior. In my tests, this actual beats PrudentSniper on occasion.

```
package WeakestLink.Players;

import java.util.*;

import WeakestLink.Game.Vote;

public class VengefulSniper extends Player{
    @Override
    public int vote(Set<Integer> currentOpponents) {
        int me = getSmartness();
        int smartOpp = Collections.max(currentOpponents);
        int dumbOpp = Collections.min(currentOpponents);
        int votesAgainstSmart=0, votesAgainstDumb=0;
        Boolean targetedBySmart = false, targetedByDumb = false;

        Set<Vote> votesForMe = getRecentVotes();
        Iterator<Vote> votes = votesForMe.iterator();
        while(votes.hasNext()){
            Vote vote = votes.next();
            int voter = vote.getVoter();
            int voted = vote.getVoted();

            if(voted == me){
                if(voter == smartOpp){
                    targetedBySmart = true;
                }
                if(voter == dumbOpp){
                    targetedByDumb = true;
                }
            } else if (voted == smartOpp){
                votesAgainstSmart++;
            } else if (voted == dumbOpp){
                votesAgainstDumb++;
            }
        }

        // If being targeted by smartest or dumbest, take them out
        // Try to go with the rest of the crowd if they both targeted me
        if(targetedBySmart ^ targetedByDumb){
            return targetedBySmart ? smartOpp : dumbOpp;
        } else if (targetedBySmart && targetedByDumb){
            if (votesAgainstSmart > votesAgainstDumb){
                return smartOpp;
            } else if (votesAgainstDumb > votesAgainstSmart){
                return dumbOpp;
            }
        }

        Iterator<Integer> opps = currentOpponents.iterator();
        int cnt_stpd=0;
        while(opps.hasNext()){
            int opp_smrt = opps.next().intValue();
            if(opp_smrt < me){
                cnt_stpd++;
            }
        }

        if (cnt_stpd < 2 || (currentOpponents.size() < 4)){ //buffer is small, protect myself
            return smartOpp;
        } else {
            return dumbOpp;
        }
    }
}

```
> 2 votes

# Answer
# MiddleMan

The MiddleMan trys his best to maximize profits while keeping a wary eye that he's not cut from the game. He keeps around lesser contestants to improve his chance of making it to the next round (and to leave an easy finish). He will vote off someone smarter than him only if there are more smarter contestants than there are lesser contestants. Whichever of the two groups, he always votes for the lowest of the group to keep the pot climbing.

```
package WeakestLink.Players;
import java.util.Collections;
import java.util.Iterator;
import java.util.Set;
public class MiddleMan extends Player {
    @Override
    public int vote(Set<Integer> currentOpponents) {
        int smrt = getSmartness();

        //count number of players smarter/stupider than me
        Iterator<Integer> opps = currentOpponents.iterator();
        int cnt_smrt=0, cnt_stpd=0, opp_smrt, min_stpd=9, min_smrt=9;

        while(opps.hasNext()){
            opp_smrt = opps.next().intValue();
            if(opp_smrt > smrt){
                cnt_smrt++;
                if(opp_smrt < min_smrt) min_smrt = opp_smrt;
            }
            else if(opp_smrt < smrt){
                cnt_stpd++;
                if(opp_smrt < min_stpd) min_stpd = opp_smrt;
            }
        }

        //Keep myself in the middle of the pack, favoring the point earners
        if(cnt_stpd>cnt_smrt)
            return min_stpd;
        else
            return min_smrt;
    }
}

```

P.S. hope it compiles, I'm not a Java guy.

Had this scheme in mind before reading the other entries. Then I was surprised how close (but critically different) Sniper was so I went ahead and used that as a jumping off point since I don't know Java syntax. Thanks @Linus
> 2 votes

# Answer
# IndependentVoter

This bot knows that the general population is always wrong! So it votes for whoever is getting the least votes.

Code is nearly Identical to SolarAaron's "Bandwagon", but the end logic is flipped.

```
package WeakestLink.Players;

import WeakestLink.Game.Vote;
import java.util.Map;
import java.util.Set;

/**
 * Votes for the currently lest voted bot in the game.
 * Or the lowest one.
 */
public class IndependentVoter
        extends Player {

    @Override
    public int vote(Set<Integer> currentOpponents) {
        int self = getSmartness(), vote = -1;
        java.util.Map<Integer, Integer> votes = new java.util.TreeMap<>();
        getVotingHistory().stream().map((Vote v)-> v.getVoted()).filter((Integer i)-> !i.equals(self)).forEach((Integer tgt)-> {
            if(!votes.containsKey(tgt)) {
                votes.put(tgt, 1);
            } else {
                votes.put(tgt, votes.get(tgt) + 1);
            }
        });

        do {
            if(votes.entrySet().isEmpty()) {
                vote = currentOpponents.stream().filter((Integer i)-> !i.equals(self)).sorted().findFirst().get();
            } else {
                if(votes.containsKey(vote)) {
                    votes.remove(vote);
                    vote = -1;
                }

                for(Map.Entry<Integer, Integer> vv: votes.entrySet()) {
                    Integer key = vv.getKey();
                    Integer value = vv.getValue();

                    if((vote == -1) || (value < votes.get(vote))) {
                        vote = key;
                    }
                }
            }
        } while(!currentOpponents.contains(vote));

        return vote;
    }
}

```
> 2 votes

# Answer
# Anarchist

The anarchist doesn't like regimes.
The anarchist will try to kill the current president.
If the anarchist is president, he decides to abuse his power and kill useless peagents. Unless he was targeted by one of his inferiors, for they should burn instead.

```
package WeakestLink.Players;

import WeakestLink.Game.Vote;

import java.util.LinkedList;
import java.util.Set;

public class Anarchist extends Player {

    LinkedList<Integer> opponents;

    @Override
    public int vote(Set<Integer> currentOpponents) {
        opponents = new LinkedList();
        opponents.addAll(currentOpponents);
        opponents.sort(Integer::compare);

        int me = getSmartness();

        if (getPresident() != me) {
            return getPresident();
        } else {
            // treason ?
            Vote voteForMe = getRecentVotes().stream().filter(v -> v.getVoted() == me).findAny().orElse(null);
            if (voteForMe == null) {
                // No treason ! Hurray. Kill the peagants.
                return getPeagant();
            } else {
                // TREASON!
                return opponents.get(opponents.indexOf(voteForMe.getVoter()));
            }
        }
    }

    private int getPresident() {
        return opponents.getLast();
    }

    private int getPeagant() {
        return opponents.getFirst();
    }

}

```
> 1 votes

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


# Question
Title: Can you win with two more moves at Three Men's Morris?
# Bounties

*No. 1 (**awarded**)*

> I'll throw in 50 rep for the first valid answer

*No. 2 (**awarded**)*

> I'll throw in another 100 rep for the shortest valid answer.

*No. 3 (**open for submissions**)*

> I'll throw in 200 rep for the first one with a significant shorter valid answer. Significant being at most 45% of currently shortest answer (*564 bytes x 0.45* = **max 254 bytes**).

---

## The Game

You remember the classic game "Nine Men's Morris" or simply "**Mill**"? There's a variation called Three Men's Morris which is a bit like a mutable tic-tac-toe.

## Rules

This is the blank board of the game:

```
   a   b   c
1 [ ]–[ ]–[ ]
   | \ | / |
2 [ ]–[ ]–[ ]
   | / | \ |
3 [ ]–[ ]–[ ]

```

`[ ]` is a field and `|–/\` represent routes between those fields.

The game is played by two players `1` and `2` who each place 3 tokens on the board. This actually happened already and we are in the game. The game is won if one player can form a `mill` which is a vertical or horizontal row of the player's 3 tokens.

Tokens can be moved on the board along the connecting lines, according to this rule:

> To any adjacent empty position (i.e. from an edge position to the center, or from the center to an edge position, or from an edge position to an adjacent edge position

A player must make a move unless there's no adjacent empty position, in which case the move is skipped.

## The Challenge

You're player `1` and your move is next. Write a program or a function, that determines whether:

* you can force a win with 2 or less moves (**definite win**)
* you can win with 2 or less moves, if your opponent makes a mistake (**possible win**)
* you cannot win with 2 or less moves, because you'll need more moves or because forced moves lead your opponent to win (**impossible to win**)

## Requirements

* Even though you definitely win when you bore your opponent to death, your program must finish in finite time.
* You can write a program or a function.

## Input

The players are represented by `1` and `2`. `0` defines a free field. You can take input as a matrix or an array.

**Definite**

```
A         B         C         D
2 1 0  |  2 1 0  |  1 0 1  |  1 2 2
2 1 2  |  0 1 0  |  1 0 2  |  2 1 O
0 0 1  |  2 2 1  |  0 2 2  |  O O 1

A: [2,1,0,2,1,2,0,0,1]
B: [2,1,0,0,1,0,2,2,1]
C: [1,0,1,1,0,2,0,2,2]
D: [1,2,2,2,1,0,0,0,1]

```

**Possible**

```
A         B         C
1 0 1  |  1 0 1  |  1 2 2
1 2 2  |  1 2 0  |  0 0 1
2 0 0  |  2 0 2  |  2 1 0

A: [1,0,1,1,2,2,2,0,0]
B: [1,0,1,1,2,0,2,0,2]
C: [1,2,2,0,0,1,2,1,0]

```

**Impossible**

```
A         B
1 0 0  |  1 2 0
1 2 2  |  2 1 0
2 0 1  |  1 2 0

A: [1,0,0,1,2,2,2,0,1]
B: [1,2,0,2,1,0,1,2,0]

```

## Output

Your program should output/return a smiley:

* Definite win: `:)`
* Possible win: `:|`
* Impossible to win: `:(`

## Examples

*Definite win in two moves:*

```
[2][1][ ] 1. [2][1][ ]
[2][1][2] -> [2][1][2]
[ ][ ][1]    [ ][1][ ]

[2][1][ ] 1. [2][1][ ]    [ ][1][ ] 2. [ ][ ][1]
[ ][1][ ] -> [ ][ ][1] -> [2][ ][1] -> [2][ ][1]
[2][2][1]    [2][2][1]    [2][2][1]    [2][2][1]

[1][ ][1] 1. [ ][1][1]    [ ][1][1] 2. [1][1][1]
[1][ ][2] -> [1][ ][2] -> [1][ ][2] -> [ ][ ][2]
[ ][2][2]    [ ][2][2]    [2][ ][2]    [2][ ][2]

```

*Possible win in two moves:*

```
[1][ ][1] 1. [ ][1][1]    [ ][1][1] 2. [1][1][1]
[1][2][ ] -> [1][2][ ] -> [1][2][2] -> [ ][2][2]
[2][ ][2]    [2][ ][2]    [2][ ][ ]    [2][ ][ ]

[1][ ][1] 1. [ ][1][1]    [ ][1][1] 2. [1][1][1]
[1][2][ ] -> [1][2][ ] -> [1][2][2] -> [ ][2][2]
[2][ ][2]    [2][ ][2]    [2][ ][ ]    [2][ ][ ]

[1][2][2] 1. [ ][2][2]    [2][ ][2] 2. [1][2][2]
[ ][ ][1] -> [1][ ][1] -> [1][ ][1] -> [1][1][1]
[2][1][ ]    [2][1][ ]    [2][1][ ]    [2][ ][ ]

```

*Impossible to win in two moves:*

```
[1][ ][ ]
[1][2][2]
[2][ ][1]

```

## Bonus

In case a definite win is possible and your program outputs the moves of one way to success as well like `a1:a2` (1 move) or `a1:a2,a3:b2` (2 moves), you can withdraw **30%** of your byte count.

---

This is code golf – so shortest answer in bytes wins. Standard loopholes are disallowed.

---

Thanks to Peter Taylor who fixed some flaws and improved wording in the Sandbox.

# Answer
> 1 votes
# Haskell, ~~580~~ ~~564~~ 441 bytes

This is how far I can golf it for now. Not sure if the other languages can beat it.

Call `m` on a list of lists like `[[2,1,0],[2,1,2],[0,0,1]]` (Definite A).

```
import Data.Array
r=[0..2]
p?f=[(x,y)|x<-r,y<-r,f!y!x==p]
p%f=all(==x)xs||all(==y)ys where(x:xs,y:ys)=unzip$p?f
s p x y f=f//[(y,f!y//[(x,p)])]
p#f=[s 0 x y$s p u v f|a@(x,y)<-p?f,b@(u,v)<-0?f,((x-u)*(y-v)==0&&abs(x+y-u-v)==1)||elem(1,1)[a,b]]
p&f|p#f>[]=p#f|0<1=[f]
e=any
i a p f=e(a$e(p%))(map(map(p&))(map((3-p)&)$p&f))||e(p%)(p&f)
l=listArray(0,2)
f(True,_)=":)"
f(False,True)=":|"
f _=":("
m=putStrLn.f.(\f->(i all 1 f,i e 1 f)).l.map l

```

Test code:

```
da = [[2,1,0],[2,1,2],[0,0,1]]
db = [[2,1,0],[0,1,0],[2,2,1]]
dc = [[1,0,1],[1,0,2],[0,2,2]]
dd = [[1,2,2],[2,1,0],[0,0,1]]
pa = [[1,0,1],[1,2,2],[2,0,0]]
pb = [[1,0,1],[1,2,0],[2,0,2]]
pc = [[1,2,2],[0,0,1],[2,1,0]]
ia = [[1,0,0],[1,2,2],[2,0,1]]
ib = [[1,2,0],[2,1,0],[1,2,0]]
al = [da,db,dc,dd,pa,pb,pc,ia,ib]

```

`mapM_ m al` returns:

```
:)
:)
:)
:)
:|
:|
:|
:(
:(

```

# Answer
> 5 votes
# C# - ~~739~~ 663 bytes

Complete program, reads input from argv, and appears to work. Run it like

```
ThreeMill 1 2 1 1 2 0 0 0 2

```

If this method of input is unacceptable, I'll be glad to change it (never like using argv).

```
using System;using System.Linq;class P{static void Main(string[]A){var I=new[]{0,3,6,1,4,7,2,5,8};Func<string[],string>J=S=>S[0]+S[1]+S[2]+" "+S[3]+S[4]+S[5]+" "+S[6]+S[7]+S[8]+" ";Func<string[],string,int>W=(B,p)=>(J(B)+J(I.Select(i=>B[i]).ToArray())).Contains(p+p+p)?1:0;Func<string[],string,string[][]>V=(B,p)=>I.SelectMany(a=>I.Where(b=>a!=b&B[a]==p&B[b]=="0"&(a==4|b==4|a-b==3|b-a==3|((a-b==1|b-a==1)&a/3==b/3))).Select(b=>{var N=(string[])B.Clone();N[b]=p;N[a]="0";return N;})).DefaultIfEmpty(B).ToArray();int h,G;Console.WriteLine(":"+"(|))"[V(A,"1").Max(z=>((h=0)<(G=V(z,"2").Sum(j=>V(j,"1").Max(q=>W(q,"1")-W(q,"2"))+h++*0))?1:0)+(h>G?W(z,"1")*2:2))]);}}

```

I was disinclined to post this yesterday, because I've not been able to golf it down much (not had all that much time, and I might be out of practice), but since there hasn't been a response yet, I'll post it anyway, I certainly don't expect the bounty, I'd rather it went to someone who's put a bit more effort into theirs before posting!

*Edit:* replaced all the bools with ints, which meant I could make better use of Linq, and managed to collapse both foreach loops, giving big savings. I am slightly amazed that the `h` counter works... ++ is such a subtle utility.

The program is very simple, it just explores every possible set of moves (stores board state in a string\[\]). It iterates over all of our possible moves (the boards that result thereof), and counts the number of responses by our opponent that we can successful beat (`G`) (i.e. those that we win, and he doesn't). It also counts the number of possible responses (`h`). If we can win any, then it's a possible, and we add 1 to the sum, if we can win them all, it's a definite, and we add 2 to the sum. The maximum some is therefore our best possible outcome, and we index into the string "(|))" to return the appropriate face. Note that we need the extra ")" because the sum can be 2 or 3 if it's a definite (it's possible that we don't appear to be able to beat any responses having already won on the first go, so the possible check is a tad misleading).

The program checks for a victory by producing a string from the board, that is space-separated rows and columns, and just looks for a string of 3 of the player's character in this string (e.g. "201 201 021 220 002 111 " is a win for us)

```
using System;
using System.Linq; // all important

class P
{
    static void Main(string[]A) // transform to int?
    {
        var I=new[]{0,3,6,1,4,7,2,5,8}; // vertical indexes
        Func<string[],string>J=S=>S[0]+S[1]+S[2]+" "+S[3]+S[4]+S[5]+" "+S[6]+S[7]+S[8]+" "; // joins the strings up, so that there is a space separating each group of three (including at end)
        Func<string[],string,int>W=(B,p)=>(J(B)+J(I.Select(i=>B[i]).ToArray())).Contains(p+p+p)?1:0; // checks if a particular player wins
        Func<string[],string,string[][]>V=(B,p)=>I.SelectMany(a=>I // for each imagineable move
            .Where(b=>a!=b&B[a]==p&B[b]=="0"&(a==4|b==4|a-b==3|b-a==3|((a-b==1|b-a==1)&a/3==b/3))) // where it's legal
            .Select(b=>{var N=(string[])B.Clone();N[b]=p;N[a]="0";return N;}) // select the resulting board
        ).DefaultIfEmpty(B) // allow not-moving
        .ToArray();

        int h, // h stores the number of responses the opponent has to each move
        G; // G stores the number of responses by the opponent we can beat

        Console.WriteLine(":"+"(|))"[ // we index into this to decide which smiley
            V(A,"1").Max(z=>
                    ((h=0)<(G=V(z,"2").Sum(j=>V(j,"1").Max(q=>W(q,"1")-W(q,"2"))+h++*0))?1:0) // if there is atleast 1 reponse by the opponent we can beat, we can possibly win
                    +(h>G?W(z,"1")*2:2) // if there are moves which we can't win, then if we have already won (one-move), else, we can definitely win
                   ) // sum is therefore 0 if impossible, 1 if possible, >2 (no more than 3) if definite
            ]);

    }
}

```

Here is my test script:

```
ThreeMill 2 1 0 2 1 2 0 0 1
ThreeMill 2 1 0 0 1 0 2 2 1
ThreeMill 1 0 1 1 0 2 0 2 2
ThreeMill 1 2 2 2 1 0 0 0 1

ThreeMill 1 0 1 1 2 2 2 0 0
ThreeMill 1 0 1 1 2 0 2 0 2
ThreeMill 1 2 2 0 0 1 2 1 0

ThreeMill 1 0 0 1 2 2 2 0 1
ThreeMill 1 2 1 1 2 0 0 0 2
ThreeMill 1 0 1 2 0 2 1 0 2

```

Which outputs

```
:)
:)
:)
:)
:|
:|
:|
:(
:|
:)

```

# Answer
> 1 votes
# PowerShell ~~576~~ 550 bytes

I shall not be so easily deterred - if I can't get C# below 631 bytes, I'll have to use a different language instead! I'm hoping that Leif Willerts will knock 5 bytes off his answer, because I've decided I'm not overly fond of PowerShell, maybe I just need to look at it objectively in terms in byte counts...

This is a script, you run it by `. .\mill.ps1 "201102021"`. It's pretty well a copy of my C# answer, only in a language I've little experience with. I've not made too much of an effort to golf this, because it took so bloomin' long to get working in the first instance, and is reasonably compact already.

*Edit: couldn't just leave those `[Math]::Floor` calls in there*

```
param($U);$I=0,3,6,1,4,7,2,5,8;function J($S){($S[0..2]+" "+$S[3..5]+" "+$S[6..8]-join"").Contains($p*3)}function W($D,$p){(J $D)-or(J $D[$I])}function V($Q,$C){$I|%{$a=$_;$I|?{$a-ne$_-and$Q[$a]-eq$c-and$Q[$_]-eq"0"-and($a-eq4-or$_-eq4-or$a-$_-eq3-or$_-$a-eq3-or(($a-$_-eq1-or$_-$a-eq1)-and$a/3-$a%3/3-eq$_/3-$_%3/3))}|%{$b=$Q[0..8];$b[$_]=$c;$b[$a]=0;$b-join''}}|%{$n=1}{$n=0;$_}{if($n){$Q}}}$e=$f=0;V $U "1"|%{$h=0;$x=$_;V $x "2"|%{$k=0;(V $_ "1"|%{if((W $_ "1")-and!(W $_ "2")){$k=$e=1}});$h+=1-$k};if($h-eq0-or(W $x "1")){$f=2}};":"+"(|))"[$e+$f]

```

If you a description of how it works... the C# answer is for you, but hopefully the comments make it clear enough. The semicolons may not match perfectly with the single-line command, I'm not sure yet where they are needed and aren't, and didn't copy them back when I put the whole thing on one line.

```
param($U); # take input as argument

$I=0,3,6,1,4,7,2,5,8; # cols

function J($S){ # checks if this is a winning string
($S[0..2]+" "+$S[3..5]+" "+$S[6..8]-join"").Contains($p*3)}

function W($D,$p){ # checks if this is a winning board
(J $D)-or(J $D[$I])} # $D[$I] reorganises into columns

function V($Q,$C){ # yields all valid moves from position $Q for player $C
$I|%{$a=$_;$I| # for each possible move
?{$a-ne$_-and$Q[$a]-eq$c-and$Q[$_]-eq"0"-and($a-eq4-or$_-eq4-or$a-$_-eq3-or$_-$a-eq3-or(($a-$_-eq1-or$_-$a-eq1)-and$a/3-$a%3/3-eq$_/3-$_%3/3))}| # where legal
%{$b=$Q[0..8];$b[$_]=$c;$b[$a]=0;$b-join''}}| # make the move (copy $Q to an array, modify, join into a string)
%{$n=1}{$n=0;$_}{if($n){$Q}}} # if empty, return $Q - I am confident this can be achieved with commas, and [0], and maybe a +, but I don't want to think about it

$e=$f=0; # possible, definite

V $U "1"|%{ # for all our possible moves
$h=0;$x=$_; # $k is whether we win all of these
  V $x "2"| # for all opponent's responses
  %{$k=0;(V $_ "1"| # for all our responses
  %{if((W $_ "1")-and!(W $_ "2")){$k=$e=1}});$h+=1-$k}; # if we can win and he can't, then things are looking good, set $e to 1 (possible win)

  if($h-eq0-or(W $x "1")){$f=2} # if we win every move, or we have already won, it's a definite
};

":"+"(|))"[$e+$f] # smile, it's all over

```

Test script (PowerShell):

```
. .\mill.ps1 "210212001"
. .\mill.ps1 "210010221"
. .\mill.ps1 "101102022"
. .\mill.ps1 "122210001"

. .\mill.ps1 "101122200"
. .\mill.ps1 "101120202"
. .\mill.ps1 "122001210"

. .\mill.ps1 "100122201"
. .\mill.ps1 "121120002"
. .\mill.ps1 "101202102"

. .\mill.ps1 "100122201"
. .\mill.ps1 "120210120"

```

Output thereof:

```
:)
:)
:)
:)
:|
:|
:|
:(
:|
:)
:(
:(

```

# Answer
> 1 votes
# Python 3, ~~566~~ 557 bytes

I'll have to see if I can golf it down further, or if I can get the 30% bonus, but after much procrastination, here is my answer.

```
def t(g,x=1,r=0,z=0):
 m=[[1,3,4],[0,2,4],[2,4,5],[0,4,6],[0,1,2,3,5,6,7,8],[2,4,8],[3,4,7],[4,6,8],[4,5,7]];a=[[0,1,2],[3,4,5],[6,7,8],[0,3,6],[1,4,7],[2,5,8],[0,4,8],[2,4,6]];z=z or[[],[],[],[]];s=0
 if r>3:return z
 for i in a:
  if g[i[0]]==g[i[1]]==g[i[2]]>0:s=g[i[0]];break
 z[r]+=s,
 for q in range(9):
  i=g[q]
  if i==x:
   for p in m[q]:
    if g[p]<1:n=g[:];n[q],n[p]=n[p],n[q];z=t(n,3-x,r+1,z)
 if r:return z
 else:
  w=l=0
  for j in range(4):w=w or 1in z[j];l=l or 2in z[j]
  if l<1and w:return":)"
  elif w<1and l:return":("
  else:return":|"

```

Ungolfed:

```
def three_mens_morris(grid, player=1, rec=0, w_l=0, p=0):
    moves = [[1,3,4],[0,2,4],[2,4,5],[0,4,6],[0,1,2,3,5,6,7,8],[2,4,8],[3,4,7],[4,6,8],[4,5,7]]
    w_l = w_l or [[],[],[],[]]
    if rec == 4: return w_l
    result = check_grid(grid)
    w_l[rec].append(result)
    for sq_1 in range(len(grid)):
        piece = grid[sq_1]
        if piece == player:
            for sq_2 in moves[sq_1]:
                if grid[sq_2] == 0:
                    new_grid = grid.copy()
                    new_grid[sq_1],new_grid[sq_2]=new_grid[sq_2],new_grid[sq_1]
                    w_l = three_mens_morris(new_grid,3-player,rec+1,w_l)
    if p: print(w_l)
    if rec:
        return w_l
    else:
        win = loss = 0
        for i in range(4):
            if 1 in w_l[i]:
                win = 1
            elif 2 in w_l[i]:
                loss = 1
        if p:print(win,loss)
        if loss==0 and win:
            return ":)"
        elif loss and win==0:
            return ":("
        else:
            return ":|"

def check_grid(grid):
    rows = [[0,1,2],[3,4,5],[6,7,8],[0,3,6],[1,4,7],[2,5,8],[0,4,8],[2,4,6]]
    for i in rows:
        if grid[i[0]]==grid[i[1]]==grid[i[2]] and grid[i[0]]:
            return grid[i[0]]
    return 0

```

---
Tags: code-golf, game, board-game
---


title: Connect-n time!

text:
# Question
Title: Connect-n time!
https://en.wikipedia.org/wiki/Connect\_Four

Does anyone remember the 2 player game connect 4? For those who don't it was a 6x7 board that stands vertical on a surface. The goal of connect 4 is to, well connect 4! The connection is counted if it is horizontal, diagonal, or vertical. You place your pieces on the board by inserting a piece at the top of a column where it falls to the bottom of that column. Our rules change 3 things in connect 4.

* **Change #1** Winning is defined as the player with the most points. You get points by connecting 4 like in the rules - more on that later.
* **Change #2** You have 3 players each round.
* **Change #3** The board size is 9x9.

### Scoring:

Score is based on how many you get in a row. If you have a 4 in a row group you get 1 point. If you have a 5 in a row group you get 2 points, 6 in a row 3 and so on.

### Examples:

Note `o` and `x` are replaced with `#` and `~` respectively, for better contrast

Example of empty board: (all examples are 2 player standard size board)

```
   a b c d e f g
6 | | | | | | | |
5 | | | | | | | |
4 | | | | | | | |
3 | | | | | | | |
2 | | | | | | | |
1 |_|_|_|_|_|_|_|

```

If we drop a piece in coll `d`, it will land in location`1d`.

```
   a b c d e f g
6 | | | | | | | |
5 | | | | | | | |
4 | | | | | | | |
3 | | | | | | | |
2 | | | | | | | |
1 |_|_|_|#|_|_|_|

```

If we now drop a piece in coll `d` again, it will land in location `2d`. Here are examples of 4 in a row positions:

```
   a b c d e f g
6 | | | | | | | |
5 | | | | | | | |
4 | | | |~| | | |
3 | | |~|#| | | |
2 | |~|#|~| |#| |
1 |~|#|~|#|_|#|_|

```

In this case `x` gets 1 point diagonally (`1a 2b 3c 4d`).

```
  a b c d e f g
6 | | | | | | | |
5 | | | | | | | |
4 | | | |#| | | |
3 | | | |#| | | |
2 | | | |#| | | |
1 |_|~|_|#|~|_|~|

```

In this case, `o` gets 1 point vertically (`1d 2d 3d 4d`).

```
   a b c d e f g
6 | | | | | | | |
5 | | | | | | | |
4 | | | | | | | |
3 | | | | | | | |
2 | | |#|#|#|#| |
1 |_|_|~|~|~|~|~|

```

In this case `o` gets 2 points horizontally (`1c 1d 1e 1f 1g`) and `x` gets 1 point horizontally (`2c 2d 2e 2f`).

```
   a b c d e f g
6 | | |#| | | | |
5 | | |#| | | | |
4 | | |#| | | | |
3 | | |#| | |~| |
2 |~| |#| | |#|~|
1 |~|_|#|~| |~|~|

```

This time `x` gets 3 points for a 6 in a row (`1c 2c 3c 4c 5c 6c`).

### Input / Output

You will have access to the board via a 2d array. Each location will be represented with an `int` representing a player id. You will also have your player id passed to your function. You make your move by returning which coll you want to drop your piece into. Each round 3 players will be chosen to play. At the end of the game, all players will have played an even amount of games.

For the moment 100k rounds will be run (note this takes a *long* time, you may want to reduce it for fast turnaround testing). Overall the winner is the player with the most wins.

The controller can be found here: https://github.com/JJ-Atkinson/Connect-n/tree/master.

### Writing a bot:

To write a bot you must extend the `Player` class. `Player` is abstract and has one method to implement, `int makeMove(void)`. In `makeMove` you will decide which coll you would like to drop your piece into. If you chose an invalid coll (e.g. coll does not exist, coll is filled already), **your turn will be skipped**. In the `Player` class you have many useful helper methods. A listing of the most important ones follows:

* `boolean ensureValidMove(int coll)`: Return true *if* the coll is on the board *and* the coll is not filled yet.
* `int[] getBoardSize()`: Return a int array where `[0]` is the number of columns, and `[1]` is the number of rows.
* `int[][] getBoard()`: Return a copy of the board. You should access it like this: `[coll number][row number from bottom]`.
* To find the rest, look at the `Player` class.
* `EMPTY_CELL`: The value of an empty cell

Since this will be multi-threaded, I have also included a `random` function if you need it.

### Debugging your bot:

I have included some things in the controller to make it simpler to debug a bot. The first one is `Runner#SHOW_STATISTICS`. If this is enabled, you will see a printout of player groups played, including a count of bot wins. Example:

```
OnePlayBot, PackingBot, BuggyBot,
OnePlayBot -> 6
PackingBot -> 5
BuggyBot -> 3
Draw -> 1

```

You can also make a custom game with the `connectn.game.CustomGame` class, you can see the scores and winner of each round. You can even add yourself to the mix with `UserBot`.

### Adding your bot:

To add your bot to the lineup, go to the `PlayerFactory` static block and add the following line:

```
playerCreator.put(MyBot.class, MyBot::new);

```

### Other things to note:

* The simulations are multi-threaded. If you want to turn that off, go to `Runner#runGames()` and comment this line (`.parallel()`).
* To change the number of games, set `Runner#MINIMUM_NUMBER_OF_GAMES` to your liking.

### Added later:

* Communication among bots is disallowed.

Related: Play Connect 4!

================================

## Scoreboard: (100 000 games)

```
MaxGayne -> 22662
RowBot -> 17884
OnePlayBot -> 10354
JealousBot -> 10140
Progressive -> 7965
Draw -> 7553
StraightForwardBot -> 7542
RandomBot -> 6700
PackingBot -> 5317
BasicBlockBot -> 1282
BuggyBot -> 1114
FairDiceRoll -> 853
Steve -> 634

```

================================

# Answer
> 11 votes
# MaxGayne

This bot assigns a score to each position, based mainly on the length of connected parts. It looks 3 moves deep inspecting 3 best looking moves at each stage, and chooses the one with the maximum expected score.

```
package connectn.players;

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

public class MaxGayne extends Player {
    private static final int PLAYERS = 3;

    private static class Result {
        protected final int[] score;
        protected int lastCol;

        public Result(int[] score, int lastCol) {
            super();
            this.score = score;
            this.lastCol = lastCol;
        }

        public Result() {
            this(new int[PLAYERS], -1);
        }

        public Result(Result other) {
            this(new int[PLAYERS], other.lastCol);
            System.arraycopy(other.score, 0, this.score, 0, PLAYERS);
        }

        public int getRelativeScore(int player) {
            int max = Integer.MIN_VALUE;
            for (int i = 0; i < PLAYERS; ++ i) {
                if (i != player && score[i] > max) {
                    max = score[i];
                }
            }
            return score[player] - max;
        }
    }

    private static class Board extends Result {
        private final int cols;
        private final int rows;
        private final int[] data;
        private final int[] used;

        public Board(int cols, int rows) {
            super();
            this.cols = cols;
            this.rows = rows;
            this.data = new int[cols * rows];
            Arrays.fill(this.data, -1);
            this.used = new int[cols];
        }

        public Board(Board other) {
            super(other);
            this.cols = other.cols;
            this.rows = other.rows;
            this.data = new int[cols * rows];
            System.arraycopy(other.data, 0, this.data, 0, this.data.length);
            this.used = new int[cols];
            System.arraycopy(other.used, 0, this.used, 0, this.used.length);
        }

        private void updatePartScore(int player, int length, int open, int factor) {
            switch (length) {
                case 1:
                    score[player] += factor * open;
                    break;
                case 2:
                    score[player] += factor * (100 + open * 10);
                    break;
                case 3:
                    score[player] += factor * (10_000 + open * 1_000);
                    break;
                default:
                    score[player] += factor * ((length - 3) * 1_000_000 + open * 100_000);
                    break;
            }
        }

        private void updateLineScore(int col, int row, int colOff, int rowOff, int length, int factor) {
            int open = 0;
            int player = -1;
            int partLength = 0;
            for (int i = 0; i < length; ++ i) {
                int newPlayer = data[(col + i * colOff) * rows + row + i * rowOff];
                if (newPlayer < 0) {
                    if (player < 0) {
                        if (i == 0) {
                            open = 1;
                        }
                    } else {
                        updatePartScore(player, partLength, open + 1, factor);
                        open = 1;
                        player = newPlayer;
                        partLength = 0;
                    }
                } else {
                    if (newPlayer == player) {
                        ++ partLength;
                    } else {
                        if (player >= 0) {
                            updatePartScore(player, partLength, open, factor);
                            open = 0;
                        }
                        player = newPlayer;
                        partLength = 1;
                    }
                }
            }
            if (player >= 0) {
                updatePartScore(player, partLength, open, factor);
            }
        }

        private void updateIntersectionScore(int col, int row, int factor) {
            updateLineScore(col, 0, 0, 1, rows, factor);
            updateLineScore(0, row, 1, 0, cols, factor);
            if (row > col) {
                updateLineScore(0, row - col, 1, 1, Math.min(rows - row, cols), factor);
            } else {
                updateLineScore(col - row, 0, 1, 1, Math.min(cols - col, rows), factor);
            }
            if (row > cols - col - 1) {
                updateLineScore(cols - 1, row - (cols - col - 1), -1, 1, Math.min(rows - row, cols), factor);
            } else {
                updateLineScore(col + row, 0, -1, 1, Math.min(col + 1, rows), factor);
            }
        }

        private void updatePiece(int player, int col, int row) {
            updateIntersectionScore(col, row, -1);
            data[col * rows + row] = player;
            ++ used[col];
            lastCol = col;
            updateIntersectionScore(col, row, 1);
        }

        public Board updatePiece(int player, int col) {
            int row = used[col];
            if (row >= rows) {
                return null;
            } else {
                Board result = new Board(this);
                result.updatePiece(player, col, row);
                return result;
            }
        }

        private void updateBoard(int[][] board) {
            for (int col = 0; col < cols; ++ col) {
                for (int row = 0; row < rows; ++ row) {
                    int oldPlayer = data[col * rows + row];
                    int newPlayer = board[col][row] - 1;
                    if (newPlayer < 0) {
                        if (oldPlayer < 0) {
                            break;
                        } else {
                            throw new RuntimeException("[" + col + ", " + row + "] == "  + oldPlayer + " >= 0");
                        }
                    } else {
                        if (oldPlayer < 0) {
                            updatePiece(newPlayer, col, row);
                        } else if (newPlayer != oldPlayer) {
                            throw new RuntimeException("[" + col + ", " + row + "] == "  + oldPlayer + " >= " + newPlayer);
                        }
                    }
                }
            }
        }

        private Result bestMove(int depth, int player) {
            List<Board> boards = new ArrayList<>();
            for (int col = 0; col < cols; ++ col) {
                Board board = updatePiece(player, col);
                if (board != null) {
                    boards.add(board);
                }
            }
            if (boards.isEmpty()) {
                return null;
            }
            Collections.sort(boards, (o1, o2) -> Integer.compare(o2.getRelativeScore(player), o1.getRelativeScore(player)));
            if (depth <= 1) {
                return new Result(boards.get(0).score, boards.get(0).lastCol);
            }
            List<Result> results = new ArrayList<>();
            for (int i = 0; i < 3 && i < boards.size(); ++ i) {
                Board board = boards.get(i);
                Result result = board.bestMove(depth - 1, (player + 1) % PLAYERS);
                if (result == null) {
                    results.add(new Result(board.score, board.lastCol));
                } else {
                    results.add(new Result(result.score, board.lastCol));
                }
            }
            Collections.sort(results, (o1, o2) -> Integer.compare(o2.getRelativeScore(player), o1.getRelativeScore(player)));
            return results.get(0);
        }
    }

    private Board board = null;

    @Override
    public int makeMove() {
        if (board == null) {
            int[][] data = getBoard();
            board = new Board(data.length, data[0].length);
            board.updateBoard(data);
        } else {
            board.updateBoard(getBoard());
        }

        Result result = board.bestMove(3, getID() - 1);
        return result == null ? -1 : result.lastCol;
    }
}

```

# Answer
> 6 votes
# RowBot

Looks in all directions and determines the optimal column. Tries to connect his pieces, while not letting his opponents do the same.

```
package connectn.players;

import connectn.game.Game;
import java.util.ArrayList;
import java.util.List;

public class RowBot extends Player {

    @Override
    public int makeMove() {
        int[][] board = getBoard();
        int best = -1;
        int bestScore = -10;
        for (int col = 0; col < board.length; col++) {
            if (ensureValidMove(col)) {
                int score = score(board, col, false);
                score -= score(board, col, true);
                if (score > bestScore) {
                    bestScore = score;
                    best = col;
                }
            }
        }
        return best;
    }

    private int score(int[][] board, int col, boolean simulateMode) {
        int me = getID();
        int row = getLowestEmptyRow(board, col);
        List<Score> scores = new ArrayList<>();
        if (!simulateMode) {
            scores.add(getScoreVertical(board, col, row));
        } else {
            row += 1;
        }
        scores.addAll(getScoreHorizontal(board, col, row));
        scores.addAll(getScoreDiagonal(board, col, row));
        int score = 0;
        for (Score s : scores) {
            if (s.player == me) {
                score += s.points > 2 ? 100 : s.points * 5;
            } else if (s.player != Game.EMPTY_CELL) {
                score += s.points > 2 ? 50 : 0;
            } else {
                score += 1;
            }
        }
        return score;
    }

    private Score getScoreVertical(int[][] board, int col, int row) {
        return getScore(board, col, row, 0, -1);
    }

    private List<Score> getScoreHorizontal(int[][] board, int col, int row) {
        List<Score> scores = new ArrayList<>();

        Score left = getScore(board, col, row, -1, 0);
        Score right = getScore(board, col, row, 1, 0);
        if (left.player == right.player) {
            left.points += right.points;
            scores.add(left);
        } else {
            scores.add(left);
            scores.add(right);
        }
        return scores;
    }

    private List<Score> getScoreDiagonal(int[][] board, int col, int row) {
        List<Score> scores = new ArrayList<>();

        Score leftB = getScore(board, col, row, -1, -1);
        Score rightU = getScore(board, col, row, 1, 1);
        Score leftBottomToRightUp = leftB;
        if (leftB.player == rightU.player) {
            leftBottomToRightUp.points += rightU.points;
        } else if (leftB.points < rightU.points || leftB.player == Game.EMPTY_CELL) {
            leftBottomToRightUp = rightU;
        }

        Score leftU = getScore(board, col, row, -1, 1);
        Score rightB = getScore(board, col, row, 1, -1);
        Score rightBottomToLeftUp = leftU;
        if (leftU.player == rightB.player) {
            rightBottomToLeftUp.points += rightB.points;
        } else if (leftU.points < rightB.points || leftU.player == Game.EMPTY_CELL) {
            rightBottomToLeftUp = rightB;
        }

        if (leftBottomToRightUp.player == rightBottomToLeftUp.player) {
            leftBottomToRightUp.points += rightBottomToLeftUp.points;
            scores.add(leftBottomToRightUp);
        } else {
            scores.add(leftBottomToRightUp);
            scores.add(rightBottomToLeftUp);
        }
        return scores;
    }

    private Score getScore(int[][] board, int initCol, int initRow, int colOffset, int rowOffset) {
        Score score = new Score();
        outerLoop: for (int c = initCol + colOffset;; c += colOffset) {
            for (int r = initRow + rowOffset;; r += rowOffset) {
                if (outside(c, r) || board[c][r] == Game.EMPTY_CELL) {
                    break outerLoop;
                }
                if (score.player == Game.EMPTY_CELL) {
                    score.player = board[c][r];
                }

                if (score.player == board[c][r]) {
                    score.points++;
                } else {
                    break outerLoop;
                }

                if (rowOffset == 0) {
                    break;
                }
            }
            if (colOffset == 0) {
                break;
            }
        }
        return score;
    }

    private boolean outside(int col, int row) {
        return !boardContains(col, row);
    }

    private int getLowestEmptyRow(int[][] board, int col) {
        int[] rows = board[col];
        for (int row = 0; row < rows.length; row++) {
            if (rows[row] == Game.EMPTY_CELL){
                return row;
            }
        }
        return -1;
    }

    private class Score {
        private int player = Game.EMPTY_CELL;
        private int points = 0;
    }
}

```

# Answer
> 5 votes
# OnePlayBot

This bot has only one play - place its piece in the leftmost cell that is valid. Oddly enough it does pretty good ;)

```
static class OnePlayBot extends Player {
    @Override
    int makeMove() {
        int attemptedMove = 0;

        for (int i = 0; i < getBoardSize()[0]; i++)
            if (ensureValidMove(i)) {
                attemptedMove = i;
                break;
            }

        return attemptedMove;
    }
}

```

# Answer
> 3 votes
# BasicBlockBot

A simple (and naive) block bot. He doesn't know you can make a 4 in a row horizontally *or* diagonally!

```
static class BasicBlockBot extends Player {
    @Override
    int makeMove() {
        List<Integer> inARows = detectInARows();
        double chanceOfBlock = 0.5;

        if (inARows.isEmpty())
            chanceOfBlock = 0;

        if (random() < chanceOfBlock) {
            return inARows.get((int)Math.round(random() * (inARows.size() - 1)));
        } else {
            return (int)Math.round(random() * getBoardSize()[0]);
        }
    }

    /**
     * Very limited - just detects vertical in a rows
     *
     * @return A list of colls that have 4 in a row vertical
     */
    private List<Integer> detectInARows() {
        List<Integer> ret = new ArrayList<>();
        int[][] board = getBoard();

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                int currId = board[i][j];
                if (currId != -1 && is4InARowVertical(i, j, board)) {
                    ret.add(i);
                }
            }
        }

        return ret;
    }

    private boolean is4InARowVertical(int coll, int row, int[][] board) {
        int id = board[coll][row];

        for (int i = 0; i < 4; i++) {
            int y = row + i;
            if (!boardContains(coll,y) || board[coll][y] != id)
                return false;
        }
        return true;
    }

}

```

# Answer
> 3 votes
# RandomBot

Just put a piece anywhere that is valid.

```
static class RandomBot extends Player {
    @Override
    int makeMove() {
        int attemptedMove = (int)Math.round(random() * getBoardSize()[0]);
        while (!ensureValidMove(attemptedMove))
            attemptedMove = (int)Math.round(random() * getBoardSize()[0]);

        return attemptedMove;
    }
}

```

# Answer
> 3 votes
# Progressive

Progressive is... progressive. He likes looking at *everything*, and some! (I'm not sure of the methodology of this. It worked against a friend, once.) And, for some reason, it works decently.

```
static class Progressive extends Player{
    @Override
    int makeMove(){
        int move = 0;
        boolean statusBroken = false;
        for(int n=getBoardSize()[0];n>2;n-=2){
            for(int i=0;i<getBoardSize()[0];i+=n){
                if(ensureValidMove(i)){
                    move = i;
                    statusBroken = true;
                    break;
                }
                if(statusBroken) break;
            }
        }
        return move;
    }
}

```

# Answer
> 3 votes
# StraightForwardBot

Similar to the OnePlayBot but takes into account the last move and plays the next column over that is valid.

```
static class StraightForwardBot extends Player {
    private int lastMove = 0;

    @Override
    int makeMove() {
        for (int i = lastMove + 1; i < getBoardSize()[0]; i++) {
            if (ensureValidMove(i)) {
                lastMove = i;
                return i;
            }
        }
        for (int i = 0; i < lastMove; i++) {
            if (ensureValidMove(i)) {
                lastMove = i;
                return i;
            }
        }
        return 0;
    }
}

```

# Answer
> 3 votes
## JealousBot

This bot hates the other player. And he doesn't like that he drops pieces on the board. So he tries to be the last one who have drop a piece in a column.

```
public class JealousBot extends Player {

    @Override
    public int makeMove() {
        int move = 0;
        boolean madeMove = false;
        int[] boardSize = getBoardSize();
        int id = getID();
        int[][] board = getBoard();

        if(getTurn()!=0) {
            for(int col = 0; col<boardSize[0]; col++) {
                for(int row = 0; row<boardSize[1]; row++) {
                    if(ensureValidMove(col)) {
                        if(board[col][row]!=EMPTY_CELL && board[col][row]!=id) {
                            move = col;
                            madeMove = true;
                            break;
                        }
                    }
                }
                if(madeMove) break;
            }

            if(!madeMove) {
                int temp = (int)Math.round(random()*boardSize[0]);
                while(madeMove!=true) {
                    temp = (int)Math.round(random()*boardSize[0]);
                    if(ensureValidMove(temp)) {
                        madeMove = true;
                    }
                }
                move = temp;
            }
        } else {
            move = (int)Math.round(random()*boardSize[0]);
        }

        return move;
    }
}

```

It's my first time on CodeGolf, so I hope this answer will be good enough. I couldn't test it yet, so please excuse me if there are any mistakes.

**EDIT** : Added a line to break the second `for`.

**EDIT 2** : Figured out why the `while` was infinite. It is now complete and can be used!

# Answer
> 3 votes
# FairDiceRoll

Always returns 4.

```
static class FairDiceRoll extends Player {
    private int lastMove = 0;
    @Override
    int makeMove() {
        return 4;
    }
}

```

# Answer
> 2 votes
# BuggyBot

A sample bot for you to beat (FYI: it's not hard ;)

```
static class BuggyBot extends Player {
    @Override
    int makeMove() {
        return getBoardSize()[1] - 1;
    }
}

```

# Answer
> 2 votes
# PackingBot

This bot isn't aiming for points directly. He tries to pack a maximum of tokens until the board is filled. He understood that simply going up again and again is stupid, so he will randomly put tokens around his "domain".

He should be able to get some points in all directions, but will not be the best !

(Not tested)

```
package connectn.players;

static class PackingBot extends Player
{
    @Override
    int makeMove()
    {
        int move = 0;
        int[] sizes = getBoardSize();
        if(getTurn()==0)
            return sizes[0]/2+sizes[0]%2;

        int[][] board = getBoard();
        int[] flatBoard =new int[sizes[0]];
        //Creating a flat mapping of my tokens
        for(int i=0;i<sizes[0];i++)
            for (int j=0;j<sizes[1];j++)
                if(board[i][j]!=getID())
                    flatBoard[i]++;

        int max=0;
        int range=0;
        for(int i=0;i<flatBoard.length;i++)
        {
            if(flatBoard[i]!=0)
                range++;
            if(flatBoard[i]>flatBoard[max])
                max=i;
        }

        int sens = (Math.random()>0.5)?1:-1;
        move=((int)(Math.random()*(range+1)*sens))+max;

        while(!ensureValidMove(move))
        {
            move=(move+1*sens)%sizes[0];
            if(move<0)
                move=sizes[0]-1;
        }
        return move;
    }

}

```

# Answer
> 2 votes
# Steve

```
package connectn.players;

import java.util.Random;
import java.util.concurrent.ThreadLocalRandom;

import connectn.game.Game;

public class Steve extends Player {
    @Override
    public int makeMove() {
        Random r=ThreadLocalRandom.current();
        int attemptedMove = 0;
        int[][]board=getBoard();
        int ec=Game.EMPTY_CELL;
        for(int c=0;c<board.length;c++){
            int j=board[c].length-1;
            for(;j>=0;j--){
                if(board[c][j]!=ec)break;
            }

            if(j>2+r.nextInt(3)&&r.nextDouble()<0.8)return c;
        }
        int k=-2+board.length/2+r.nextInt(5);
        if(ensureValidMove(k))return k;
        for (int i = 0; i < getBoardSize()[0]; i++)
            if (ensureValidMove(i)) {
                attemptedMove = i;
                break;
            }

        return attemptedMove;
    }
}

```

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


title: Counting icons for Innovation splays

text:
# Question
Title: Counting icons for Innovation splays
Innovation is a card game where players battle through the ages, from prehistory to modern times, in an attempt to earn achievements faster than their opponents.

Each card in Innovation is unique, and provides a player with a number of icons. If we treat each card as a 2x3 grid, then three of the four slots on the left and bottom edges will always been taken up by icons (the symbols in black hexagons are not counted).

The game has 6 types of icons (castles, crowns, leaves, lightbulbs, factories and clocks), which we will represent arbitrarily using the chars `012345`. Using `#` to represent the black hexagon, we can use four chars to represent the icons on each card. For example, the cards above are

```
0.. #.. 3.. 1..  -> 03#0 #331 355# 144#
3#0 331 55# 44#

```

Now, in Innovation, cards in the play area are grouped into piles\* which are splayed in one of four ways. For each example we'll use the cards above, assuming the leftmost card, `03#0`, is at the top of the pile.

**No splay:** only the top card is visible

```
0..
3#0

```

**Splay left**: the top card is fully visible, as well as the right third of all cards below

```
0..|.|.|.|
3#0|1|#|#|

```

**Splay right**: the top card is fully visible, as well as the left third of all cards below

```
1|3|#|0..
4|5|3|3#0

```

**Splay up**: the top card is fully visible, as well as the bottom half of all cards below.

```
0..
3#0
---
331
---
55#
---
44#

```

### The challenge

Input will be a single space-separated string consisting of two parts:

* A splay direction, which is one of `!<>^`, representing no splay, splay left, splay right or splay up respectively.
* A non-empty list of cards, each of which is 4 characters long and consisting of the chars `012345#`. The leftmost card is at the top of the pile, and each card contains exactly one `#`.

Answers may be functions, full programs or equivalent. You may choose whether the splay direction is first or last, i.e. choose one of the two formats below:

```
> 03#0 #331 355# 144#
03#0 #331 355# 144# >

```

Output will be a list of six numbers representing the count for each icon, e.g. for the example cards above:

```
! 03#0 #331 355# 144#  ->  2 0 0 1 0 0
< 03#0 #331 355# 144#  ->  2 1 0 1 0 0
> 03#0 #331 355# 144#  ->  2 1 0 3 1 1
^ 03#0 #331 355# 144#  ->  2 1 0 3 2 2

```

For instance, the no splay case had two `0` icons and one `3` icon showing, giving the first line. Note that we don't count `#`s, since the black hexagons aren't icons.

You may choose any reasonable and non-ambiguous way of representing the list, e.g. delimiter-separated or using your language's natural list representation.

### Test cases

```
! 113#  ->  0 2 0 1 0 0
< 113#  ->  0 2 0 1 0 0
> 113#  ->  0 2 0 1 0 0
^ 113#  ->  0 2 0 1 0 0
! 000# 12#2  ->  3 0 0 0 0 0
< 000# 12#2  ->  3 0 1 0 0 0
> 000# 12#2  ->  3 1 1 0 0 0
^ 000# 12#2  ->  3 0 2 0 0 0
! 000# 111# 222#  ->  3 0 0 0 0 0
< 000# 111# 222#  ->  3 0 0 0 0 0
> 000# 111# 222#  ->  3 2 2 0 0 0
^ 000# 111# 222#  ->  3 2 2 0 0 0
! 335# #101 21#2 333# 2#20 3#33 4#54 #133 3#33 32#2  ->  0 0 0 2 0 1
< 335# #101 21#2 333# 2#20 3#33 4#54 #133 3#33 32#2  ->  1 1 2 5 1 1
> 335# #101 21#2 333# 2#20 3#33 4#54 #133 3#33 32#2  ->  0 3 3 7 1 1
^ 335# #101 21#2 333# 2#20 3#33 4#54 #133 3#33 32#2  ->  2 4 4 10 1 2

```

Note that something like `!` is invalid input, since the list is guaranteed to be non-empty.

---

<sup>* For the purposes of this challenge, we're ignoring pile colours.</sup>

# Answer
> 5 votes
## CJam, ~~44~~ ~~37~~ 36 bytes

*Thanks to Sp3000 for reminding me that I'm overcomplicating things and saving 7 bytes.*

```
rci7%"3>0<2<1>"2/=6,slS%{W$~+}*fe=p;

```

Test it here.

### Explanation

Some observations:

* We always want to count the entire first card.
* All splays will result in either a prefix or a suffix of the icons removed. `!` removes all of them (which is either a prefix or a suffix of four characters), `<` removes the first three characters, `>` removes the last two characters, `^` removes the first character.

So all we need is a short way to map the splay mode to the correct truncation:

```
rci   e# Read the splay mode and convert to its character code.
7%    e# Take modulo 7. This maps "<!>^" to [4 5 6 3], respectively. Modulo 4 those are
      e# are all distinct (namely [0 1 2 3], respectively).
"3>0<2<1>"
      e# Push this string.
2/    e# Split it into chunks of 2, ["3>" "0<" "2<" "1>"]. Each chunk is CJam code which
      e# performs one of the truncations.
=     e# Select the correct snippet. This works, because array indexing is cyclic in CJam.
6,s   e# Push the string "012345".
lS%   e# Read the remainder of the input and split into space-separated tokens.
{     e# Now we're abusing the fold operation to apply our snippet to every card except
      e# the first, while also combining them all back into a single string.
  W%  e#   Copy the bottom of the stack (the truncation snippet).
  ~   e#   Evaluate it.
  +   e#   Append it the string we're building.
}*
fe=   e# For each character in "012345", count the occurrences in our new string.
p     e# Pretty-print the array.
;     e# Discard the truncation snippet which was still at the bottom of the stack.

```

We can notice that the truncation snippets actually have a lot of structure. Each splay mode maps to one number in `[0 1 2 3]` (specifically, in order `"!^><"`), and two of them have `>` and two have `<`. I was hoping to find two hashes which magically produce these parts separately, as that would save a bunch of bytes, but so far I wasn't able to find anything. I can map `"!^><"` to numbers of alternating parity with `31%` (to select the correct character from `"<>"`), but I haven't found anything which neatly maps them `[0 1 2 3]` in that order. (Except the naive solution of `"!^><"#` which unfortunately doesn't save any bytes.)

Also note that it's actually a bit more flexible. `!` can also be implemented as `n>` for any `n > 3` (discarding everything as a prefix). Unfortunately, I haven't been able to find any simple function for such a map either.

# Answer
> 0 votes
# Pyth, ~~39~~ ~~36~~ ~~33~~ 31 bytes

```
Jtczdm/s+hJm@yk%*%Chz33T19tJ`d6

```

Try it online. Test suite.

### Explanation

* `Jtczd`: split input by spaces, remove the first part, and save the rest to `J`.
* `m``6`: repeat the following for numbers 0 to 5.
    + `m``tJ`: repeat the following for all cards except for the first one.
        - `Chz`: get the code point of the first character in the input.
        - `%*%``33T19`: map the code points of `!<>^` (33, 60, 62, 94) to the numbers 0, 4, 5, 14. The exact calculation performed is `cp % 33 * 10 % 19`.
        - `yk`: get the powerset of the current card. This is a list of all subsequences of the card.
        - `@`: get the item of the powerset corresponding to the index calculated before.
    + `+hJ`: append the first card to the result.
    + `s`: concatenate the processed cards together.
    + `/```d`: count the occurrences of the current number in the result.

---
Tags: code-golf, counting, card-games
---