title: That's BS! (card game)

text:
# Question
Title: That's BS! (card game)
BS is a card game where the object of the game is to lose all of your cards.

A game consists of four players and a 52-card deck. Each player is randomly dealt 13 cards. Normally, cards are labeled 2 - 10, Ace, Jack, Queen, King, but for simplicity, the cards will be labeled with a number from 0 - 12 inclusive. Although the number of cards in a player's hand is public information, only the player knows what specific cards are in his hand.

The game goes as follows: the first player places as many cards labeled *0* as he wants to in the discard pile (note that he is not required to play all of his cards labeled *0*, though usually it is in his best interest to do so). He must play at least one card. The second player plays as many cards as he wants to labeled *1*, the third player plays *2*, and so on. After 12, it resets to 0.

What happens if you don't have any of the cards that you are supposed to play? Remember, you must play at least one card -- in fact, you can play any cards you want! (Actually, even if you have the right card, you can lie and play a different card). However, someone can call you out and say, "BS!" If that someone is correct and you had lied, then you must take all the cards in the discard pile; as a reward, the player who called you out randomly places one of their cards in the discard pile. If the accuser is wrong, however, he must take all the cards in the discard pile. Note that you can't lie about the *number* of cards that you play.

More detailed info:

* At the beginning of the game, four random players are chosen to play. Since there will be at least 1000 games, each player will get a chance to play. The turn order is randomly decided at the beginning of the game
* If you return one correct card and one incorrect card, then it is considered lying (i.e. if you were supposed to give *2*s, and you gave one *2* and one *1*, then that's lying)
* If two or more players both say BS at the same time, then one is randomly chosen.
* Your score is the percent of games that you win.
* There is a maximum 1000 rounds, where one round is every player going once. Usually, someone wins before this. If no one wins, then it is counted towards the total number of games played, but no one wins.

Spec:

You should write a class which extends `Player`. It will look like:

```
package players;

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

import controller.*;

public class Player1 extends Player {

    @Override
    protected List<Card> requestCards(int card, Controller controller) {
        Card[] hand = getHand();
        List<Card> ret =  new ArrayList<Card>();
        for (Card c : hand) {
            if (c.getNumber() == card) {
                ret.add(c);
            }
        }
        if (ret.size() == 0) ret.add(hand[0]);
        return ret;
    }

    @Override
    protected boolean bs(Player player, int card, int numberOfCards, Controller controller) {
        return numberOfCards >= 3;
    }

    protected void update(Controller controller) {
      // This method gets called once at the end of every round
    }

    protected void initialize(Controller controller) {
      // This method gets called once at the beginning once all the cards are dealt
    }

    public String toString() {
        return "Player 1";
    }
}

```

The method `requestCards` is called when it is your turn. The argument `card` is the card number that you are supposed to provide. You return a list of cards that you want to put in the discard pile. The player above checks to see if he has any cards of the requested card type; if not, he simply plays his first card and hopes no one checks.

The method `bs` is called whenever someone else plays a card. The first argument is the player, the second - the card he was *supposed* to play, and the third - the number of that type of card that he claims that he has played. Return `true` if you want to call "BS." In the code above, the player only calls "BS" when the other player claims to have 3 or more cards of the requested type.

The last argument for both methods is `controller`, which is just the controller that controls the game. From the controller, you can get more public information, such as the number of cards in the discard pile or the list and turn order of the players.

The `toString` method is optional.

Conroller on GitHub: https://github.com/prakol16/bs

If you want to post a non-java solution, you can use the interface provided in https://github.com/LegionMammal978/bs (credits to LegionMammal978) and I'll try to integrate it.

Scoreboard so far:

```
class players.PlayerConMan: 2660/4446 = 59.82905982905983%
class players.CalculatingLiar: 2525/4426 = 57.049254405784005%
class players.PlayerTruthy: 1653/4497 = 36.75783855903936%
class players.Player4: 1446/4425 = 32.67796610169491%
class players.Player1: 536/4382 = 12.23185759926974%
class players.Player3: 493/4425 = 11.141242937853107%
class players.Player2: 370/4451 = 8.312738710402156%
class players.LiePlayer: 317/4432 = 7.152527075812275%
class players.Hoarder: 0/4516 = 0.0%

```

PlayerConMan is winning, but CalculatingLiar is in a close second. These scores seem consistent -- they are fairly the same every time.

# Answer
> 10 votes
# ConMan

ConMan watches every card that goes through his hand, calling BS when a play isn't possible due to where the cards are.

Plays truth when able, but lies intelligently using the last card if a victory were to happen.

I spent a long time tuning a technique to call BS when the probability was high that the opponent was lying, or when calling BS was beneficial (such as getting useful cards from the discard pile), but in practice, not calling BS at all netted me the most points.

```
package players;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import controller.*;
import java.text.DecimalFormat;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;

public class PlayerConMan extends Player {

    private enum Location {

        PLAYER_0,
        PLAYER_1,
        PLAYER_2,
        PLAYER_3,
        DISCARD,
        UNKNOWN
    };

    private class MyCard {

        private final int number;
        private Location location;
        private double confidence;
        protected Card card;

        public MyCard(int x) {
            this.number = x;
            location = Location.UNKNOWN;
            confidence = 1.0;
        }

        @Override
        public String toString() {
            if (confidence > 0.75) {
                return ""+number;
            } else if (confidence > 0.25) {
                return number+"*";
            } else {
                return number+"_";
            }
        }
    }

    private final ArrayList<ArrayList<MyCard>> theDeck = new ArrayList();
    private Location myLocation;
    private ArrayList<Player> players;
    private final ArrayList<MyCard> myHand = new ArrayList();
    private final HashMap<Location, Integer> sizes = new HashMap();
    private ArrayList<Integer> lies = new ArrayList();
    private ArrayList<Integer> truths = new ArrayList();

    // Constructor
    public PlayerConMan() {
        for (int i = 0; i < 13; ++i) {
            ArrayList<MyCard> set = new ArrayList();
            for (int j = 0; j < 4; ++j) {
                set.add(new MyCard(i));
            }
            theDeck.add(set);
        }
        sizes.put(Location.PLAYER_0, 13);
        sizes.put(Location.PLAYER_1, 13);
        sizes.put(Location.PLAYER_2, 13);
        sizes.put(Location.PLAYER_3, 13);
        sizes.put(Location.DISCARD, 13);
        sizes.put(Location.UNKNOWN, 39);
    }

    //Gets the MyCard for this card, updating a MyCard with the lowest confidence if not already created
    private MyCard getCard(Card c) {
        ArrayList<MyCard> set = theDeck.get(c.getNumber());
        MyCard unknown = null;
        double confidence = 1.0;
        for (MyCard m : set) {
            if (m.card == c) {
                return m;
            }
            if (m.card == null) {
                if (m.location == Location.UNKNOWN) {
                    unknown = m;
                    confidence = 0.0;
                } else if (m.confidence < confidence || unknown == null) {
                    unknown = m;
                    confidence = m.confidence;
                }
            }
        }
        unknown.card = c;
        return unknown;
    }

    //Returns the Location of a player
    private Location getLocation(Player p) {
        return Location.values()[players.indexOf(p)];
    }

    @Override
    protected void initialize(Controller controller) {
        super.initialize(controller);
        players = new ArrayList(controller.getPlayers());
        for (Player p : players) {
            if (p == this) {
                myLocation = getLocation(p);
            }
        }
        for (Location loc : Location.values()) {
            sizes.put(loc, 0);
        }
    }

    private ArrayList<Integer>[] getTruthesAndLies(Player player, int card, ArrayList<MyCard> myHand) {
            //Determine our next plays
            int offset = players.indexOf(player);
            int myOffset = players.indexOf(this);
            int nextCard = (card + (myOffset - offset + 4) % 4)%13;
            ArrayList<Integer> truths = new ArrayList();
            ArrayList<Integer> lies = new ArrayList();
            ArrayList<MyCard> cardsLeft = new ArrayList(myHand);
            while (!cardsLeft.isEmpty()) {
                boolean isLie = true;
                Iterator<MyCard> it = cardsLeft.iterator();
                while (it.hasNext()) {
                    MyCard m = it.next();
                    if (m.number == nextCard) {
                        it.remove();
                        isLie = false;
                    }
                }
                if (isLie) {
                    lies.add(nextCard);
                } else {
                    truths.add(nextCard);
                }
                nextCard = (nextCard + 4)%13;
            }

            return new ArrayList[]{truths, lies};
    }

    private void updateDeck(Player player, int card, int numberOfCards, Controller controller) {
        Location loc = getLocation(player);

        //Update from BS
        if (sizes.get(Location.DISCARD) + numberOfCards != controller.getDiscardPileSize()) {

            //Move all cards from DISCARD to the losing player
            //  Losing player defaults to player playing, in the rare case of a tie
            Location losingPlayer = loc;
            Location winningPlayer = null;
            for (Player p : players) {
                Location pLoc = getLocation(p);
                int size = p.handSize();
                if (pLoc == loc) size += numberOfCards;
                if (p.handSize() > sizes.get(pLoc)) {
                    losingPlayer = pLoc;
                } else if (size < sizes.get(pLoc)) {
                    winningPlayer = pLoc;
                }
            }

            if (winningPlayer == null) {
                debug(losingPlayer+" lost a BS");
            } else {
                debug(losingPlayer+" lied and "+winningPlayer+" lost a card");
            }

            //Move the cards from the discard to the player
            ArrayList<MyCard> winnersHand = new ArrayList();
            for (ArrayList<MyCard> set : theDeck) {
                for (MyCard m : set) {
                    if (m.location == Location.DISCARD) {
                        if (losingPlayer == myLocation) {
                            //If we lost, update the discard cards to unknown;
                            //  They'll be updated when we look at our hand
                            m.location = Location.UNKNOWN;
                            m.confidence = 1.0;
                        } else {
                            //Move to the losing player
                            m.location = losingPlayer;
                        }
                    } else if (m.location == myLocation && winningPlayer == myLocation) {
                        //Update our old cards to the discard pile, in case we won
                        m.location = Location.DISCARD;
                        m.confidence = 1.0;
                    } else if (m.location == winningPlayer) {
                        //Add the card to the winner's hand for later processing
                        winnersHand.add(m);
                    }
                }
            }

            //If someone else won, adjust the probabilities on their cards
            if (winningPlayer != myLocation && winningPlayer != null) {
                int winningSize = players.get(winningPlayer.ordinal()).handSize();
                if (winningPlayer == loc) winningSize += numberOfCards;
                for (MyCard m : winnersHand) {
                    m.confidence *= 1-(1/winningSize);
                }
            }

        }
        sizes.put(Location.DISCARD, controller.getDiscardPileSize());
        //Update player handSize
        for (Player p : players) {
            sizes.put(getLocation(p), p.handSize());
        }

        //Detect if my hand size has changed to speed processing
        if (myHand.size() != handSize()) {
            //Update values from my hand
            myHand.clear();
            for (Card c : getHand()) {
                MyCard m = getCard(c);
                m.location = myLocation;
                m.confidence = 1.0;
                myHand.add(m);
            }

            //Determine our next plays
            ArrayList<Integer> tl[] = getTruthesAndLies(player, card, myHand);
            truths = tl[0];
            lies = tl[1];
            debug("Truthes: "+truths);
            debug("Lies: "+lies);
        }
    }

    @Override
    protected List<Card> requestCards(int card, Controller controller) {
        updateDeck(this, card, 0, controller);

        ArrayList<Card> ret = new ArrayList();
        int pick = card;
        boolean all = true;
        if (truths.get(0) != card) {
            pick = truths.get(truths.size()-1);
            all = false;
        }

        for (MyCard m : myHand) {
            if (m.number == pick) {
                m.location = Location.DISCARD;
                ret.add(m.card);
                if (!all) break;
            }
        }

        sizes.put(Location.DISCARD, controller.getDiscardPileSize() + ret.size());
        sizes.put(myLocation, myHand.size() - ret.size());
        printTheDeck();

        return ret;
    }

    @Override
    protected boolean bs(Player player, int card, int numberOfCards, Controller controller) {
        updateDeck(player, card, numberOfCards, controller);
        Location loc = getLocation(player);

        //Get total number of unknown cards and total number of cards the player must have
        int handSize = player.handSize() + numberOfCards;
        ArrayList<MyCard> playerHand = new ArrayList();
        ArrayList<MyCard> discardPile = new ArrayList();
        double totalUnknown = 0;
        double playerUnknown = handSize;
        double cardsHeld = 0;
        double cardsNotHeld = 0;
        for (ArrayList<MyCard> set : theDeck) {
            for (MyCard m : set) {
                if (m.location == Location.UNKNOWN) {
                    totalUnknown++;
                } else if (m.location == loc) {
                    playerHand.add(m);
                    playerUnknown -= m.confidence;
                    totalUnknown += 1.0 - m.confidence;
                    if (m.number == card) {
                        cardsHeld += m.confidence;
                    }
                } else {
                    if (m.location == Location.DISCARD) {
                        discardPile.add(m);
                    }
                    totalUnknown += 1.0 - m.confidence;
                    if (m.number == card) {
                        cardsNotHeld += m.confidence;
                    }
                }
            }
        }

        boolean callBS = false;
        double prob;
        int possible = (int)Math.round(4-cardsNotHeld);
        int needed = (int)Math.round(numberOfCards - cardsHeld);
        if (needed > possible) {
            //Player can't possibly have the cards
            prob = 0.0;
            debug("impossible");
            callBS = true;
        } else if (needed <= 0) {
            //Player guaranteed to have the cards
            prob = 1.0;
            debug("guaranteed");
        } else {
            //The probability that player has needed or more of the possible cards
            double successes = 0;
            for (int i = (int)needed; i <= (int)possible; i++) {
                successes += choose(possible, i) * choose(totalUnknown-possible, playerUnknown-i);
            }
            double outcomes = choose(totalUnknown, playerUnknown);
            prob = successes / outcomes;
            if (Double.isNaN(prob)) {
                prob = 0;
                callBS = true;
            }
            debug("prob = "+new DecimalFormat("0.000").format(prob));
        }

        //Update which cards they may have put down
        //  Assume they put down as many as they could truthfully
        int cardsMoved = 0;
        Iterator<MyCard> it = playerHand.iterator();
        while (it.hasNext()) {
            MyCard m = it.next();
            if (m.number == card) {
                it.remove();
                m.location = Location.DISCARD;
                discardPile.add(m);
                cardsMoved++;
                if (cardsMoved >= numberOfCards) {
                    break;
                }
            }
        }

        //We can't account for all the cards they put down
        //  Adjust existing probabilities and move our lowest confidence cards to the discard
        if (cardsMoved < numberOfCards) {
            //  Reduce the confidence of all remaining cards, in case they lied
            //  Assumes they lie at random
            double cardsLeft = handSize-cardsMoved;
            double cardsNeeded = numberOfCards-cardsMoved;
            double probChosen = 1 * choose(cardsLeft-1, cardsNeeded-1) / choose(cardsLeft, cardsNeeded);
            if (Double.compare(cardsLeft, cardsNeeded) == 0) {
                //They're gonna win, call their bluff
                callBS = true;
                for (MyCard m : playerHand) {
                    m.location = Location.DISCARD;
                }
            } else {
                for (MyCard m : playerHand) {
                    m.confidence *= (1-probChosen) * (1-prob) + prob;
                }
            }

            //  Move any UNKNOWN cards they could have played, assuming they told the truth
            Collections.sort(theDeck.get(card), new Comparator<MyCard>() {
                @Override
                public int compare(MyCard o1, MyCard o2) {
                    double p1 = o1.confidence - (o1.location == Location.UNKNOWN ? 10 : 0);
                    double p2 = o2.confidence - (o2.location == Location.UNKNOWN ? 10 : 0);
                    return (int)Math.signum(p1-p2);
                }
            });
            for (MyCard m : theDeck.get(card)) {
                if (m.location == Location.UNKNOWN || m.confidence < prob) {
                    m.location = Location.DISCARD;
                    m.confidence = prob;
                    cardsMoved++;
                    discardPile.add(m);
                    if (cardsMoved >= numberOfCards) break;
                }
            }
        }

        //Get the confidence of the discardPile
        double discardPileConfidence = 1.0;
        for (MyCard m : discardPile) {
            discardPileConfidence *= m.confidence;
        }
        discardPileConfidence *= Math.pow(0.5, controller.getDiscardPileSize() - discardPile.size());

        //Call BS if the cards in the discard pile consists only of cards we need / will play
        if (discardPileConfidence > 0.5 && discardPile.size() == controller.getDiscardPileSize()) {
            double truthCount = 0;
            double lieCount = 0;
            double unknownCount = 0;
            for (MyCard m : discardPile) {
                if (truths.contains(m.number)) {
                    truthCount += m.confidence;
                    unknownCount += 1-m.confidence;
                } else if (lies.contains(m.number)) {
                    lieCount += m.confidence;
                    unknownCount += 1-m.confidence;
                } else {
                    unknownCount += 1;
                    break;
                }
            }
            if (lieCount > 0 && unknownCount < 1) {
                debug("Strategic BS");
                //callBS = true;
            }
        }

        //What's the worst that could happen?
        //Test the decks'
        ArrayList<MyCard> worstHand = new ArrayList<MyCard>(myHand);
        worstHand.addAll(discardPile);
        ArrayList<Integer> loseCase[] = getTruthesAndLies(player, card, worstHand);
        int winPlaysLeft = truths.size() + lies.size();
        int losePlaysLeft = loseCase[0].size() + loseCase[1].size();
        double randomPlaysLeft = Math.max(losePlaysLeft,7);
        double expectedPlaysLeft = losePlaysLeft * discardPileConfidence + randomPlaysLeft * (1-discardPileConfidence);
        double threshold = 0.0 - (expectedPlaysLeft - winPlaysLeft)/13.0;
        debug("winPlaysLeft = "+winPlaysLeft);
        debug("expectedPlaysLeft   = "+expectedPlaysLeft);
        debug("Threshold    = "+threshold);

        if(lies.isEmpty()) {
            threshold /= 2;
        }
        //callBS = callBS || prob < threshold;

        printTheDeck();
        return callBS;
    }

    static double logGamma(double x) {
        double tmp = (x - 0.5) * Math.log(x + 4.5) - (x + 4.5);
        double ser = 1.0 + 76.18009173 / (x + 0) - 86.50532033 / (x + 1)
                + 24.01409822 / (x + 2) - 1.231739516 / (x + 3)
                + 0.00120858003 / (x + 4) - 0.00000536382 / (x + 5);
        return tmp + Math.log(ser * Math.sqrt(2 * Math.PI));
    }

    static double gamma(double x) {
        return Math.exp(logGamma(x));
    }

    static double factorial(double x) {
        return x * gamma(x);
    }

    static double choose(double n, double k) {
        if (Double.compare(n, k) == 0 || Double.compare(k, 0) == 0) return 1.0;
        if (k < 0 || k > n) {
            return 0.0;
        }
        return factorial(n) / (factorial(n-k) * factorial(k));
    }

    public String toString() {
        return "ConMan";
    }

    public void printTheDeck() {
        HashMap<Location, ArrayList<MyCard>> map = new HashMap();
        for (Location loc : Location.values()) {
            map.put(loc, new ArrayList());
        }
        for (ArrayList<MyCard> set : theDeck) {
            for (MyCard m : set) {
                map.get(m.location).add(m);
            }
        }
        String ret = "";
        for (Player p : players) {
            ret += p.toString()+": "+map.get(getLocation(p))+"\n";
        }
        ret += "Discard pile: "+map.get(Location.DISCARD)+"\n";
        ret += "Unknown: ("+map.get(Location.UNKNOWN).size()+" cards)\n";
        debug(ret);
    }

    public void debug(Object s) {

    }
}

```

# Answer
> 4 votes
# Player 3131961357\_10

Picks a random player each game, and always calls BS on that player.

```
package players;

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

import controller.*;

public class Player3131961357_10 extends Player{
    private int[] ducks = new int[13];
    private Player target = null;
    private int cake = 0;

    @Override
    protected List<Card> requestCards(int bacon, Controller controller){
        Card[] hand = getHand();
        List<Card> ret = new ArrayList<Card>();
        List<Card> others = new ArrayList<Card>();
        for(Card c:hand){
            if(c.getNumber() == bacon){
                ret.add(c);
            }else{
                others.add(c);
            }
        }
        if(ret.size() == 0){
            ImperfectPlayer.moveRandom(others, ret);
        }
        if(others.size() > 0 && ret.size() < 3 && handSize() > ret.size() + 1){
            ImperfectPlayer.moveRandom(others, ret);
        }
        return ret;
    }

    private final int someoneLied = 0;
    @Override
    protected boolean bs(Player player, int bacon, int howMuchBacon, Controller controller){
        if(target == null){
            // Could not find my cake.
            // Someone must have taken it.
            // They are my target.
            List<Player> players = controller.getPlayers();
            do target = players.get((int)Math.floor(Math.random() * players.size()));
            while(target != this);
        }

        int count = 0;
        Card[] hand = getHand();
        for(Card c:hand){
            if(c.getNumber() == bacon)
                ++count;
        }
        if(cake >= controller.getDiscardPileSize()){
            ducks = new int[13];
            cake = someoneLied;
        }
        ducks[bacon] += howMuchBacon;
        cake += howMuchBacon;

        if(player.handSize() == 0) return true;
        return player.handSize() == 0
            || howMuchBacon + count > 4
            || ducks[bacon] > 5
            || player == target
            || Math.random() < 0.025; // why not?
    }

    public String toString(){
        return "Player 3131961357_10";
    }

    public static <T> void moveRandom(List<T> from, List<T> to){
        T a = from.remove((int)Math.floor(Math.random() * from.size()));
        to.add(a);
    }
}

```

# Answer
> 4 votes
# Truthy

Not quite finished, since I don't know how to tell the result of calling BS (if they took the pile, or someone else in case of tie, or I did).

At the moment, only call BS if I can prove it. Don't lie unless I have to. I need to improve the lying algorithm. I'm trying to make it as close as possible to how I play BS against other players (minus randomly putting extra cards underneath to play 5 or 6 without them knowing.)

```
package players;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import controller.*;

public class PlayerTruthy extends Player {

    private List<Card> played;
    private int discardPileSize;
    private HashMap<String,Integer> handSizes;
    private boolean initialized;
    //controller.getDiscardPileSize()

    // Constructor
    public PlayerTruthy() {
        played = new ArrayList<Card>();
        handSizes = new HashMap<String,Integer>();
        discardPileSize = 0;
        initialized = false;
    }

    // Initialize (do once)
    private void init(Controller controller) {
        for (Player p : controller.getPlayers()) {
            handSizes.put(p, 0);
        }
        initialized = true;
    }

    @Override
    protected List<Card> requestCards(int card, Controller controller) {
        if (!initialized) {
            init(controller);
        }
        List<Card> cards = getCards(card);
        if (cards.size() == 0) {
            cards = lieCards(card);
        }
        played.addAll(cards);
        return cards;
    }

    @Override
    protected boolean bs(Player player, int card, int numberOfCards, Controller controller) {
        if (!initialized) {
            init(controller);
        }
        List<Card> hand = Arrays.asList(getHand());
        int count = countCards(hand, card);
        return numberOfCards > 4-count;
    }

    public String toString() {
        return "Truthy";
    }

    private int countCards(List<Card> list, int card) {
        int count = 0;
        for (Card c : list) {
            if (c.getNumber() == card) {
                count++;
            }
        }
        return count;
    }

    private List<Card> getCards(int card) {
        List<Card> cards = new ArrayList<Card>();
        Card[] hand = getHand();
        for (Card c : hand) {
            if (c.getNumber() == card) {
                cards.add(c);
            }
        }
        return cards;
    }

    private List<Card> lieCards(int card) {
        List<Card> hand = Arrays.asList(getHand());
        List<Card> cards = new ArrayList<Card>();
        int limit = 1;
        int count = 0;
        int index = (card+9) % 13;
        while (cards.size() == 0) {
            count = countCards(hand, index);
            if (count <= limit) {
                cards = getCards(index);
            }
            if (limit >= 3) {
                cards.removeRange(1, cards.size());
            }
            if (index == card) {
                limit++;
            }
            index = (index+9) % 13;
        }
        return cards;
    }
}

```

# Answer
> 4 votes
# CalculatingLiar

This one tries to play truth. If he lies, he uses a card that he won't use in the near future. It also tries to win trough calling BS on other players, since the last card almost never fits.

```
package players;

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

import controller.Card;
import controller.Controller;
import controller.Player;

public class CalculatingLiar extends Player {
    private final List<Integer> knownCardsOnDeck = new ArrayList<>();
    private int lastDeckSize = 0;

    @Override
    protected List<Card> requestCards(int card, Controller controller) {
        Card[] hand = getHand();
        List<Card> ret =  new ArrayList<Card>();
        for (Card c : hand) {
            if (c.getNumber() == card) {
                ret.add(c);
            }
        }
        if (ret.size() == 0) {
            ret.add(calculateWorstCard(card));
        }

        update(controller);

        for (Card c : ret) {
            knownCardsOnDeck.add(c.getNumber());
        }
        lastDeckSize = controller.getDiscardPileSize() + ret.size();
        return ret;
    }

    @Override
    protected boolean bs(Player player, int card, int numberOfCards,
            Controller controller) {
        Card[] hand = getHand();
        int myCards = 0;
        for (Card c : hand) {
            if (c.getNumber() == card)
                myCards++;
        }
        update(controller);
        for (Integer number : knownCardsOnDeck) {
            if (number == card) {
                myCards++;
            }
        }

        return player.handSize() == 0
                || numberOfCards > 4
                || myCards + numberOfCards > 4
                || (player.handSize() < 5 && handSize() == 1);
    }

    @Override
    protected void initialize(Controller controller) {
        knownCardsOnDeck.clear();
        lastDeckSize = 0;
    }

    @Override
    protected void update(Controller controller) {
        if (lastDeckSize > controller.getDiscardPileSize()) {
            knownCardsOnDeck.clear();
            lastDeckSize = controller.getDiscardPileSize();
        } else {
            lastDeckSize = controller.getDiscardPileSize();
        }
    }

    private Card calculateWorstCard(int currentCard) {
        List<Integer> cardOrder = new ArrayList<>();

        int nextCard = currentCard;
        do {
            cardOrder.add(nextCard);
            nextCard = (nextCard + 4) % 13;
        } while (nextCard != currentCard);
        Collections.reverse(cardOrder);

        Card[] hand = getHand();
        for (Integer number : cardOrder) {
            for (Card card : hand) {
                if (card.getNumber() == number) {
                    return card;
                }
            }
        }
        //never happens
        return null;
    }

    @Override
    public String toString() {
        return "(-";
    }
}

```

# Answer
> 2 votes
# LiePlayer

Lays down at *least* 2 cards, even if that means stretching the truth.

```
package players;

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

import controller.*;

public class LiePlayer extends Player {

    @Override
    protected List<Card> requestCards(int card, Controller controller) {
        Card[] hand = getHand();
        List<Card> ret =  new ArrayList<Card>();
        for (Card c : hand) {
            if (c.getNumber() == card) {
                ret.add(c);
            }
        }
        int i=0;
        while(ret.size()<2 && i<cards.length){
            if(c.getNumber() != card){
               ret.add(hand[i])
            }
            i++;
        }
        return ret;
    }

    @Override
    protected boolean bs(Player player, int card, int numberOfCards, Controller controller) {
        Card[] hand = getHand();
        int myCards = 0;//How meny of that card do I have.
        for (Card c : hand) {
            if (c.getNumber() == card) {
                myCards += 1;
            }
        }
        return numberOfCards+myCards >= 4;
        //for that to work, he would have to have all the other cards of that number.
    }

    public String toString() {
        //Why would we admit to lying?
        return "Truthful Player";
    }
}

```

# Answer
> 2 votes
# Hoarder

```
package players;

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

import controller.*;

public class Hoarder extends Player{
    @Override
    protected List<Card> requestCards(int card, Controller controller) {
        Card[] hand = getHand();
        List<Card> ret =  new ArrayList<Card>();
    if( canWinHonestly(card) ) { //Hoarded enough cards that I won't have to bs ever again, time to win.
      for (Card c : hand) {
            if (c.getNumber() == card) {
                ret.add(c);
            }
        }
    }
    else { // Don't have the cards I'll need in the future. Play my entire hand. Either get more cards or instantly win.
      for (Card c : hand) {
                ret.add(c);
      }
    }
        return ret;
    }

    @Override
    protected boolean bs(Player player, int card, int numberOfCards, Controller controller) {
    //Don't call unless I have to, don't want to lose a random card
        return (player.handSize() <= numberOfCards);
    }

  @Override
    public String toString() {
        return "Hoarder";
    }

  private boolean canWinHonestly(int card) {
    Card[] hand = getHand();
    List<Integer> remainingCards = new ArrayList<Integer>();
    for (Card c : hand) {
      remainingCards.add(c.getNumber());
    }
    while( remainingCards.size() > 0 ) {
      if(remainingCards.contains(card)) {
        remainingCards.remove((Integer) card);
        card = (card + 4) % 13;
      }
      else {
        return false;
      }
    }
    return true;
  }

}

```

Very simple strategy, collects cards until it can go on an honesty streak and win. Wasn't able to test it, hopefully my Java isn't too rusty.

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


# Question
Title: Number of unique outputs by substituting variables
Given a set of formulas like this:

```
bacb
bcab
cbba
abbc

```

Give an algorithm that finds the number of unique results you can get when each variable is substituted for either "0" or "1" in every formula.

There are `(k!)^2` formulas, each with `2k-1` variables and `k^2` terms. Express your asymptotics in terms of `k`.

Fastest algorithm wins. In case of a tie the solution with lower asymptotic memory usage wins. If that's still a tie, first post wins.

---

For the example above the following results can be acquired by substituting the variables:

```
1110, 0110, 1001, 0100, 1000, 0000, 0010, 1101, 1111, 0001, 1011, 0111

```

So the correct answer is 12. Among others, `1010` can not be made using the above formulas.

I've made three more tests cases, with respective solutions of 230, 12076 and 1446672.

# Answer
# Mathematica, O(k^2(k!)^2) time

```
Length[Union@@(Fold[Flatten[{StringReplace[#,#2->"0"],StringReplace[#,#2->"1"]}]&,#,Union[Characters[#]]]&/@#)]&

```

Hopefully I calculated the time complexity correctly. Input is a list of formulas such as `{"bacb","bcab","cbba","abbc"}`. Runs in less than 30 seconds for every test case on my machine, but who cares about absolute times?

### Explanation:

* First off, the `&` at the end makes it a pure function, with `#` referring to the first argument, `#2` being the second argument, etc.
* `Length[*..*]` takes the length of the list contained inside it.
* `Union@@(*..*)` takes the contained list and supplies it as the arguments for `Union`, which returns a list of the unique elements in any of its arguments.
* `*..*&/@#` takes a pure function and maps it over the list of formulas, so that `{a,b,c}` becomes `{f[a],f[b],f[c]}`. Note that in nested pure functions, `#n` refers to its innermost arguments.
* `Fold[*..*&,#,*..*]` takes a accumulator function, starting value, and list, and returns `f[f[...[f[starting value,l_1],l_2],...],l_n]`.
* `Union[Characters[#]]` takes all the characters in the current formula and gets all the unique elements, giving us the variables.
* `Flatten[*..*]` flattens its argument, so that `{{{a},b},{{c,{d}}}}` becomes `{a,b,c,d}`.
* `{*..*,*..*}` is simply a way to combine the two results using the above `Flatten`.
* `StringReplace[#,#2->"0/1"]` takes the previous result and returns it with the current variable replaced with either `0` or `1`.
> 2 votes

---
Tags: combinatorics, fastest-algorithm
---


title: Wrap-Around Subsequences

text:
# Question
Title: Wrap-Around Subsequences
# Introduction

In this challenge, your task is to find generalized subsequences of strings. The subsequences are not necessarily contiguous, and they can also "wrap around" the string, going past its end and starting again from the beginning. You'll want to minimize the number of wraps, though.

More formally, let `u` and `v` be any two strings, and `k ≥ 0` an integer. We say that `u` is a *`k`-wrapping subsequence* of `v`, if there are distinct indices `i<sub>1</sub>, i<sub>2</sub>, ..., i<sub>len(u)</sub>` such that `u == v[i<sub>1</sub>] v[i<sub>2</sub>] ... v[i<sub>len(u)</sub>]`, and at most `k` of the indices `i<sub>j</sub>` satisfy `i<sub>j</sub> > i<sub>j+1</sub>`. This means that `u` can be found inside `v` by going from left to right, choosing some of its characters on the way, and wrapping around at most `k` times (equivalently, doing at most `k+1` sweeps across `v`). Note that no character can be chosen more than once, even after a wrap-around, and that `0`-wrapping subsequences are exactly the ordinary subsequences that we are all familiar with.

# The Task

Your inputs are two non-empty alphanumeric strings `u` and `v`, and your output is the smallest integer `k` such that `u` is a `k`-wrapping subsequence of `v`. If no such `k` exists, the output shall be `-1`.

# Example

Consider the inputs `u := xyzyxzzxyx` and `v := yxzzazzyxxxyz`. If we start looking for the characters of `u` in `v` in a greedy fashion, we will wrap around 3 times:

```
 yxzzazzyxxxyz
>─x─────y────z┐
┌─────────────┘
└y───────x────┐
┌─────────────┘
└──zz─────x─y─┐
┌─────────────┘
└──────────x──>

```

Thus the correct output is at most 3. Note how the left-most character `x` is selected once, and then ignored on the second sweep, since it cannot be re-used. However, there exists a shorter method with only 2 wrap-arounds:

```
 yxzzazzyxxxyz
>──────────xyz┐
┌─────────────┘
└yxzz────x────┐
┌─────────────┘
└───────y─x───>

```

It turns out that one wrap-around (that is, two sweeps) is not enough, so the correct output is `2`.

# Rules and Bonuses

You can write either a function or a full program, and you can also change the order of the inputs if needed. The lowest byte count wins, and standard loopholes are disallowed.

There is a **bonus of -10%** for computing all of the test cases in under 10 seconds total. I will test unclear cases on my machine; my reference implementation in Python takes about 0.6 seconds. I have a 7-year old laptop with 1.86 GHz dual core CPU, which you may want to take into account.

# Test Cases

```
"me" "moe" -> 0
"meet" "metro" -> -1
"ababa" "abaab" -> 1
"abaab" "baabaa" -> 1
"1c1C1C2B" "1111CCCcB2" -> 3
"reverse" "reserved" -> 2
"abcdefg" "gfedcba" -> 6
"xyzyxzzxyx" "yxzzazzyxxxyz" -> 2
"aasdffdaasdf" "asdfddasdfsdaafsds" -> 2

```

# Answer
# Pyth, 34 bytes

```
Mh+Smssm>.ukC,dtdfqGsm@HkT.PUHlG_1

```

This defines a function `g`, which takes two strings as parameter. Try it online: Pyth Compiler/Executor

This code is very inefficient. It has a time and memory complexity of `len(v)!/(len(v)-len(u))!`. It is not able to solve the longer test cases in under 10 seconds. (It also will crash very likely, since it will run out of memory.)

```
M                                    define g(G, H): return _
                          .PUHlG        all permutations of [0, 1, ..., len(H)-1] of length len(G)
                 fqGsm@HkT              filter the permutations which form the string G
    mssm>.ukC,dtd                       compute the number of wraps for each of the remaining permutations
  +S                            _1      sort the numbers and append -1
 h                                      return the first element

```
> 4 votes

# Answer
# Haskell, 160 * 0.9 = 144 bytes

```
a#(-1)=a
a#b=min a b
f y=w(y++" ")0$length y
w _ n _[]=n
w(c:d)n o g@(a:b)|n>o=(-1)|a==c=z#w y n z g|c==' '=w y(n+1)o g|1<2=w y n o g where z=w d n o b;y=d++[c]

```

Timing for all test cases (note: arguments are flipped):

```
*Main> map (uncurry f) [
             ("moe", "me"),
             ("metro", "meet"),
             ("abaab", "ababa"),
             ("baabaa", "abaab"),
             ("1111CCCcB2", "1c1C1C2B"),
             ("reserved", "reverse"),
             ("gfedcba", "abcdefg"),
             ("yxzzazzyxxxyz", "xyzyxzzxyx"),
             ("asdfddasdfsdaafsds", "aasdffdaasdf")]
[0,-1,1,1,3,2,6,2,2]
(0.08 secs, 25794240 bytes)

```

How it works (short version): simple brute force that takes the minimum of using a matching character and skipping it. I stop the search when either finished (returning the number of cycles) or when cycled more than the minimum so far (returning -1).

Saved a lot of bytes compared to my first version, mainly because I switched from a full program to a function.

With some comments and proper spacing golfed Haskell is quite readable:

```
-- a minimum function that ignores a -1 in the right argument to prevent
-- "not solvable" cases in parts of the recursive search to dominate low numbers
-- of solvable parts. If the case isn't solvabale at all, both arguments are
-- -1 and are carried on.
a # (-1) = a
a # b    = min a b

-- the main function f calls the worker funktion w with arguments
-- * the string to search in (STSI), appended by a space to detect cycles
-- * the number of cycles so far
-- * the minimum of cycles needed so far, starting with the length of STSI
-- * the string to search for (STSF) (partial applied away and therefore invisible)
f y = w (y++" ") 0 (length y)

-- the worker function
w _ n _ [] = n          -- base case: if STSF is empty the work is done and the
                        -- number of cycles is returned

w (c:d) n o g@(a:b)     -- "c" is first char of STSI, "d" the rest
                        -- "n" number of cycles, "o" minimum of cycles so far
                        -- "g" is the whole STSF, "a" the 1st char, "b" the rest
  | n>o    = (-1)             -- if current cycle is more than a previous result,
                              -- indicate failure
  | a==c   = z # w y n z g    -- if there's a character match, take the min of
                              -- using it and skipping it
  | c==' ' = w y (n+1) o g    -- cycle detected, repeat and adjust n
  | 1<2    = w y n o g        -- otherwise try next char in STSI

  where                 -- just some golfing: short names for common subexpressions
  z = w d n o b;        -- number of cycles if a matching char is used
  y = d ++ [c]          -- rotated STSI

```

For reference: old version, full program, 187 bytes

```
main=interact$show.f.lines
a#(-1)=a
a#b=min a b
f[x,y]=w x(y++" ")0 0
w[]_ n _=n
w g@(a:b)(c:d)n m|a==c=w b d n 1#y|c==' '&&m==1=w g(d++" ")(n+1)0|c==' '=(-1)|1<2=y where y=w g(d++[c])n m

```
> 4 votes

# Answer
# JavaScript (ES6) 174 (193 - 10%)

Recursive search, like the @nimi's answer, keeping the min of wraps. The solutions space is big (above all for the last example) but cutting the search at the min currently found keeps the time low. **Edit 1** Add a missing test case, shortened a bit **Edit 2** No need to pass param w around, it's fixed

```
K=(w,s,x)=>
  ~-(R=(r,l,p=0,q=1,z=w[p],i=0)=>
  {
    if(z&&!(q>x)){
      if(~(r+l).indexOf(z))
        for(t=l?R(l+r,'',p,q+1):x;x<t?0:x=t,i=~r.indexOf(z,-i);)
          t=R(r.slice(-i),l+r.slice(0,~i),p+1,q);
      q=x
    }
    return q
  })(s,'')

```

**Ungolfed**

```
K=(word, astring)=>
{
  var minWraps // undefined at first. All numeric comparison with undefined give false
  var R=(right, left, pos, wraps)=>
  {
    var cur = word[pos]
    var i,t;
    if (! cur) // when all chars of word are managed
      return wraps;
    if (wraps > minWraps) // over the minimum wrap count already found, stop search
      return wraps;
    if ( (right+left).indexOf(cur) < 0 ) // if the current char is not found in the remaining part of the string
      return minWraps; // return the current min, could still be undefined (that means 'no way')
    if ( left ) // if there is a left part, try a wrapping search with the current char
    {
      t = R(left+right, '', pos, wraps+1)
      if ( !(minWraps < t)) minWraps = t; // set current min if t is less than current min or current min is still undefined
    }
    // find all occurrences of current char in the remaining part
    // for each occurrence, start a recursive search for the next char
    for(i = 0; (i = right.indexOf(cur, i)) >= 0; i++)
    {
      var passed = right.slice(0,i) // the passed chars go in the left part
      var rest = right.slice(i+1)
      t = R(rest, left+passed, pos+1, wraps) // try next char in the remaining part, no wrap
      if ( !(minWraps < t)) minWraps = t; // set current min if t is less than current min or current min is still undefined
    }
    return minWraps
  }
  var result = R(astring, '', 0, 1) // start with right=string and left empty
  return ~-result; // decrement. convert undefined to -1
}

```

**Test** In Firefox/FireBug console

```
time=~new Date;
[['me','moe']
,['meet','metro']
,['ababa','abaab']
,['abaab','baabaa']
,['1c1C1C2B','1111CCCcB2']
,['reverse','reserved']
,['abcdefg','gfedcba']
,['xyzyxzzxyx','yxzzazzyxxxyz']
,['aasdffdaasdf','asdfddasdfsdaafsds']]
.forEach(s=>console.log(s,r=K(...s)))
time-=~new Date

```

*Output* (last line is the execution time in ms)

> \["me", "moe"\] 0
> \["meet", "metro"\] -1
> \["ababa", "abaab"\] 1
> \["abaab", "baabaa"\] 1
> \["1c1C1C2B", "1111CCCcB2"\] 3
> \["reverse", "reserved"\] 2
> \["abcdefg", "gfedcba"\] 6
> \["xyzyxzzxyx", "yxzzazzyxxxyz"\] 2
> \["aasdffdaasdf", "asdfddasdfsdaafsds"\] 2
> 116
> 2 votes

---
Tags: code-golf, string, subsequence
---


title: Out-of-Control Rounding Errors

text:
# Question
Title: Out-of-Control Rounding Errors
# Background

You have recently been hired by a small accounting firm. The world of accounting is somewhat foreign to you, so you're not sure whether you are following all the professional guidelines. In particular, you don't know when you should round all those numbers, and in which direction, so most of the time you just wing it and hope for the best.

# Input

Your input is a single string that represents a simple calculation. It contains some number of nonnegative integers delimited by the characters `+-*/`. The string reads from left to right, and the normal precedence rules are ignored, so `"23+1*3/4"` means "start with 23, add 1, multiply by 3, and divide by 4", the result being 18. The input will not contain numbers that start with `0` (except `0` itself), nor a division by zero.

# Output

At each stage of the calculation, you can either round the result up or down to the nearest integer, or keep it as it is. Finally, you round either up or down to obtain a integer result. Your output is the list of integers that may result from such a calculation, sorted and without duplicates.

# Rules

You can write either a full program or a function. The lowest byte count wins, and standard loopholes are disallowed.

# Test Cases

```
"42" -> [42]
"2+0+4-0" -> [6]
"23+1*3/4" -> [18]
"5/2" -> [2,3]
"5/2+7/3*6-1" -> [17,18,19,23]
"23/2/2*30-170/3" -> [-7,-6,-2,-1,0,1,3,4]
"1/3*2*2*2*2*2*2" -> [0,16,20,21,22,24,32,64]
"1/3*9" -> [0,3,9]

```

# Answer
> 4 votes
# J, 84 bytes

Starting from a 1 element list the function keeps all the possible intermediate numbers in the list by evaling the next expression and adding it's up and down rounded copies.

~~Will golf further and add explanation tomorrow.~~ Can't find obvious ways to golf it more.

```
f=.3 :'/:~~.<.>((,>.,<.)@".@(":@],''x'',;@[))&.>/|.(>@{.;_2<\}.);:y rplc''/'';''%'''

```

Passes all the tests.

Usage:

```
   f '1/3*2*2*2*2*2*2'
0 16 20 21 22 24 32 64
   f '1/3*9'
0 3 9

```

Try it here.

# Answer
> 3 votes
# Python 2, 220 characters

```
import re,sys,math as m,fractions as f
X=f.Fraction
M=map
F=['+']+re.split("(\D)",sys.argv[1])
r=[X(0)]
while F:U=[eval('f.'+`n`+F[0]+F[1])for n in r];r=M(X,U+M(m.floor,U)+M(m.ceil,U));F=F[2:]
print sorted(set(M(int,r)))

```

It keeps a list of all possible numbers and at each step, generates three numbers for every number in the list, even if there are duplicates. Thus the run-time complexity is exponential. However, it works instantly for these small examples. Dupes are removed at the end.

It uses `fractions.Fraction` to do exact division, avoiding floating point inexactitudes.

Add 5 characters (`r=map(X,g)` --\> `r=set(map(X,g))`) to dramatically increase performance.

# Answer
> 2 votes
## Python, ~~421~~ ~~370~~ 354 bytes

Sorry, please bear with me. I am really new to python (I was just looking for a language that supports fractiosn) and used all of the few tricks I knew for shortening the code but it is still a monster considering that there is a python solution of almost half the size. I learned a lot and thought I'd submit it anyway=)

New Version thanks to @kirbyfan64sos and @Zgarb

```
from fractions import*
from math import*
import re,operator as z
s=input()
N=re.split(r'[\*\/\-\+]',s)
O=re.split(r'[0-9]+',s)[1:-1]
d={'+':z.add,'-':z.sub,'*':z.mul,'/':z.truediv}
l=[int(N[0])]#list of inters up to now
for i in range(len(O)): #iterate over all operations
    n=set()
    for f in l:
        f=d[O[i]](f,Fraction(int(N[i+1])))
        n.update([floor(f),ceil(f),f])
    l=n
print(set(map(floor,n)))

```

Old Version

```
from fractions import Fraction as F
from math import floor,ceil
import re
s=input()
N=re.split(r'[\*\/\-\+]',s)   #Numbers
O=re.split(r'[0-9]+',s)[1:-1] #Operators
l=[int(N[0])]
for i in range(len(O)): #Iterate over all operators
    n=set()
    for f in l:           #Iterate over all possible numbers
        g=F(int(N[i+1]))
        o=O[i]
        if o=='/':
            f/=g
        elif o=='*':
            f*=g
        elif o=='-':
            f-=g
        else:
            f+=g
        n.add(floor(f))  #Add all possible numbers to a new set
        n.add(ceil(f))   # the 'set' structure prevents from having multiple copies
        n.add(f)         # which is a really nice feature
    l=n                #repeat
print(set([floor(k) for k in n])) #also remove the unrounded ones

```

# Answer
> 1 votes
# Mathematica, 134

```
Union@Flatten@{Floor@#,Ceiling@#}&@ToExpression@StringReplace[#,x:("+"|"-"|"*"|"/"~~NumberString):>"//{Floor@#,#,Ceiling@#}"~~x~~"&"]&

```

# Answer
> 0 votes
# MATLAB, 283 chars

```
function[u]=w(s)
s=[' ' strsplit(regexprep(s,'\D',' $& '))];s=reshape(s,[2,size(s,2)/2]);o=s(1,:);d=cellfun(@str2num,s(2,:));a=d(1);for n=2:size(o,2)switch o{n}case'+';a=a+d(n);case'-'a=a-d(n);case'/'a=a/d(n);case'*'a=a*d(n);end;a=[ceil(a);a;floor(a)];end;u=unique(a(mod(a,1)==0))end

```

Ungolfed:

```
function [u] = WingitRound(i)
    i=[' ' strsplit(regexprep(i,'\D',' $& '))];
    i=reshape(i,[2,size(i,2)/2]);

    o=i(1,:);
    n=cellfun(@str2num,i(2,:));

    a=n(1);

    for n=2:size(o,2)
        switch o{n}
            case '+'
                a = a + n(n);
            case '-'
                a = a - n(n);
            case '/'
                a = a / n(n);
            case '*'
                a = a * n(n);
        end
        a = [ceil(a);a;floor(a)];
    end

    u=unique(a(mod(a,1)==0)));
end

```

While writing this, I realized that there is an even shorter way of doing this, which I will add once I finish writing it.

# Answer
> 0 votes
## VBA, 347 bytes

```
Function OoCRE(inp As String)
ct = 0
i = 1
Do While i < Len(inp)
c = Mid(inp, i, 1)
If Not IsNumeric(c) Then
ct = ct + 1
If ct = 2 Then
inp = Round(Application.Evaluate(Left(inp, i - 1))) & Right(inp, Len(inp) - (i - 1))
i = InStr(1, inp, c)
ct = 1
End If
End If
OoCRE = Round(Application.Evaluate(inp))
i = i + 1
Loop
End Function

```

---
Tags: code-golf, arithmetic, parsing, rational-numbers
---


title: Output a list of all rational numbers

text:
# Question
Title: Output a list of all rational numbers
Out of all of mathematics, there will always be a few theorems that go beyond all common sense. One of these is the fact that there are different sizes of infinity. Another interesting fact is the idea that many infinities which seem to be of different size are actually of the same size. There are just as many even numbers as integers, as there are rational numbers.

The general concept of this question is to confront the bizarre reality of infinity. In this challenge, your program will output a list which will:

* At any specific moment of time, always have a whole number of entries
* Eventually contain (if left to run long enough) any specific (non-zero) rational number precisely once on the entire list
* Contain an unbounded number of empty slots (entries on the list that are needlessly set to 0)
* Have a proportion of empty slots that approaches a limit of 100%
* For every positive integer N, have an infinite number of places with N consecutive empty slots

## The Challenge

Your challenge is to write that shortest possible program that will output a special list with the following rules:

1. All entries with an index that is not a square number should be set to zero. So, the first entry will be nonzero, the second and third will be zero, the fourth will nonzero, etc.
2. All rational numbers will be in the form of an improper fraction (such as 4/5 or 144/13) that has been simplified. The exception is zeroes, which will be simply `0`.
3. All (positive and negative) rational numbers should eventually appear on the list if your program runs for long enough and with enough memory. For any particular rational number, the time required may be an arbitrarily large, but always finite, amount of time.
4. If run for an infinite amount of time, no non-zero rational number should ever appear twice.

Rule 3 does allow for some variation, as in there is an infinite number of different possible legal outputs.

Output will be a stream of lines. Each line will be of the general form of `5: 2/3` where the first number is the entry number, then followed by the rational number. Note that `1: 0` will always be the first line of output.

## Example snippet of output:

```
1: 1/1
2: 0
3: 0
4: 2/1
5: 0
6: 0
7: 0
8: 0
9: -2/1
10: 0
etc...

```

## Rules, Regulations, and Notes

This is code golf. Standard code golf rules apply. Also, due to the variation allowed in the output, you need to at least show why you believe that your list will contain all possible rational numbers exactly once, and that your solution is correct.

*EDIT: Since the primes numbers did distract from the challenge, I am changing it to square numbers. This accomplishes the same purpose, and also shortens the solutions.*

# Answer
> 6 votes
## Haskell, 184 characters

```
main=putStr.unlines$zip[1..](s>>=g)>>=h
s=(1,1):(s>>=f)
f(a,b)=[(a,a+b),(a+b,b)]
g x@(a,b)=[x,(-a,b)]
h(i,(a,b))=(i^2)%(u a++'/':u b):map(%"0")[i^2+1..i*(i+2)]
i%s=u i++": "++s
u=show

```

This does a breadth-first traversal of the Calkin-Wilf Tree, yielding all positive rational numbers in reduced form exactly once. It then alternates between positive and negative to cover all the non-zero rational numbers and pads with zeroes between the square entries.

**Output (excluding zero lines for brevity):**

```
1: 1/1
4: -1/1
9: 1/2
16: -1/2
25: 2/1
36: -2/1
49: 1/3
64: -1/3
81: 3/2
100: -3/2
...

```

# Answer
> 5 votes
## Sage, 103 113 128

Sage can list the rationals with ease! Formatting to fit the program requirements, as always, ruins everything.

```
for i,q in enumerate(QQ):
 for j in[(i-1)^2+1..i*i]:print'%d:'%j,[0,'%d/%d'%(q.numer(),q.denom())][j==i*i]

```

Sage enumerates `QQ` according to their *height*: the max absolute value of the numerator & denominator after GCD reduction.

# Answer
> 4 votes
## Python, 162

```
f=lambda n:f(n/2)if n%2 else f(n/2)+f(n/2-1)if n else 1
n=i=1
while 1:
 print'%d:'%i,
 if i-n*n:s=0
 else: n+=1;s='%d/%d'%((-1)**n*f(n/2-1),f(n/2))
 print s
 i+=1

```

This uses the recursion given in Recounting the Rationals by Calkin & Wilf.

# Answer
> 2 votes
# Haskell, 55 bytes

```
mapM_ print$join$iterate(>>=(\x->[x+1,1/(1+1/x)]))[1%1]

```

outputs

```
1 % 1
2 % 1
1 % 2
3 % 1
2 % 3
3 % 2
1 % 3
4 % 1
...

```

1%1 is the root of the Calkin-Wilf tree; the iterate adds both children of each node; the join collapses the levels into a single list.

120 chars if you add proper imports, 0, and negatives:

```
import Data.Ratio
import Control.Monad
main=mapM_ print$0:(join(iterate(>>=(\x->[x+1,1/(1+1/x)]))[1%1])>>=(\x->[-x,x]))

```

outputs

```
0 % 1
(-1) % 1
1 % 1
(-2) % 1
2 % 1
(-1) % 2
1 % 2
(-3) % 1
3 % 1
(-2) % 3
2 % 3
(-3) % 2
3 % 2
(-1) % 3
1 % 3
(-4) % 1
4 % 1
...

```

outputting empty slots? that's in poor taste:( you had me at "list of all positive rationals"

# Answer
> 1 votes
## PHP 105 bytes

*Note: This code must be saved as iso-8859-1 (ansi) in order to run correctly. Online interpretters which encode all input to utf8 by default (such as ideone) will generate the wrong output.*

```
<?for($f=µ;$i++<$j*$j||++$j%2||(--$$f?$$f--:$f^=C);)echo"$i: ",$i==$j*$j?$j%2?$x=++$ö.~Ð.++$µ:"-$x":0,~õ;

```

Using Georg Cantor's enumeration (slightly modified for +/- values).

If you're having problems getting the above code to run (likely due to an excessive amount of NOTICE messages), use this instead (107 bytes):

```
<?for($f=µ;$i++<$j*$j||++$j%2||(--$$f?$$f--:$f^=C);)echo"$i: ",$i==$j*$j?$j%2?$x=++$ö.'/'.++$µ:"-$x":0,'
';

```

# Answer
> 0 votes
# Octave, 168 bytes

```
a=b=p=1;do for i=(p-1)^2+1:p^2-1 printf("%d: 0\n",i)end
printf("%d: %d/%d\n",p^2,a,b)
a=-a;if a>0do if b==1 b=a+1;a=1;else a++;b--;end until 1==gcd(a,b)end
p++;until 0

```

The solution is not very sophisticated, it is just a simple diagonal traversal of the "carpet" of rational numbers, discarding all fractions that can be simplified. After a positive number `a/b`, it's opposite `-a/b` is always printed before the next one from sequence goes.

Since all positive simple fractions will be printed and the opposite signed fractions to those will be printed, and it's never possible to two different simple fractions to have the same value, each non-zero rational number will be printed exactly once.

Degolfed:

```
a=b=p=1
do
    for i=(p-1)^2+1:p^2-1
        printf("%d: 0\n",i)         # p=2,3,4: 1..3,5..8,10..15
    end
    printf("%d: %d/%d\n", p^2,a,b); # p=2,3,4: 4,9,16
    a=-a;
    if a>0                          # the rule is: after a/b, a>0 output -a/b
        do
            if b==1 b=a+1;a=1; else a++;b--; end
        until 1==gcd(a,b)
    end
    p++;
until 0

```

---
Tags: code-golf, math, rational-numbers
---


title: Memory is Expensive

text:
# Question
Title: Memory is Expensive
You are a robot. You are stranded in a small cage with weird humans wearing weird suits looking at you. Your solar panel is malfunctioning, and your energy is running out. On the wall there is a riddle, and if you answer correctly the humans will grant you access to an energy source (yay!). However your RAM unit is leaking power, and the more you use it, the more energy will be lost.

> For each byte you access, you spend 1 energy unit (a bit costs 1/8 energy).
>
> The program that uses the least energy wins.
>
> Arrays cost the sum of all their variables. Strings and other non-fixed-length variables/arrays are prohibited, as your bot will be unable to calculate how much energy it spent. (Recursion is prohibited too!)

The riddle is weird, it changes after a while, so your bot must not hardcode the answer.

The riddle is a mathematical challenge:

> We shall input you with 3 variables, and they are free, but you shall not change them.
>
> For these 3 inputs, `a`, `b` and `c`, thou shalt calculate an integer `p` equivalent to `floor(pi * 10^(c-1))`, then you shall calculate `x = a!/b!`. Then you shall add to `x` the integer `p`. If and only if `c` is greater than `x`, you shall yell `Pi!!!!`
>
> `a`, `b` and `c` are integers smaller than the number 13.

*Example:* for `a = 5`, `b = 4`, and `c = 3`, calculate `5!/4! + 314`. as `x = 5`, and `c = 3`, don't yell `Pi!!!!`

Once finished calculating, your bot should output the answer. The input can be either in form of calling a function or the user typing a number when prompted.

If 2 bots have the same energy spending, the shortest code wins.

Also, the energy cost is for the worst case (that's why I said `a`, `b` and `c` are smaller than 13). (Extra clarification: the language overheads don't count, unless you abuse them to store data.)

# Answer
> 3 votes
## AVR (274 bytes, 0 energy points)

With all those fancy high-level languages you're never really sure how much RAM you're accessing. The only way to be sure is to ~~nuke it from orbit~~ go down to the bytes. Fortunately I just happen to be teaching myself assembler at the moment.

This submission is a subroutine that uses the AVR-GCC calling convention. Fortunately it so happens that both the return value and the arguments fit in registers. The return value will be at most `12! + floor(pi * 10^11) = 0x49 41 e6 f2 4e` (five bytes) and each of the arguments is at most `12` (one byte each). Each size is rounded up to the nearest multiple of two, so we get a total size of `6 + 2 + 2 + 2 = 12` bytes. Starting at `R25`, the return value fits in `R20`-`R24`, and the arguments live in `R18`, `R16`, and `R14`.

Note that as per the rules ("... but you shall not change \[the inputs\].") I don't write to `R18`, `R16`, or `R14`. I also don't explicitly use the stack or access anything other than the registers, meaning only two bytes are ever read from RAM during the whole program: `RET` reads the return address from the stack. However, the rules state "language overheads don't count," so the total score is zero.

The only other oddity is that I don't have a `printf` function, so in order to "yell" I bit-bang a generic parallel interface on port D. (That's digital pins 0-6 if you run this on an Arduino UNO, with pin 7 being the clock.)

Here is the code itself. All the jumps are relative, so you can plop this anywhere in your program and have it work.

```
4e e4 56 ef 69 e5 75 e2 89 e4 90 e0
22 24 23 94 33 24 44 24 55 24 77 24
60 2e 63 94 20 17 10 f4 22 24 12 c0
26 15 80 f0 56 9c 50 2c 46 9c 40 2c
51 0c 36 9c 30 2c 41 0c 57 1c 26 9c
20 2c 31 0c 47 1c 57 1c 63 94 ee cf
57 14 01 f5 47 14 f1 f4 37 14 e1 f4
2e 14 d0 f4 10 e5 1b b9 10 68 1b b9
19 e6 1b b9 10 68 1b b9 11 e2 1b b9
10 68 1b b9 1f 77 1b b9 10 68 1b b9
1f 77 1b b9 10 68 1b b9 1f 77 1b b9
10 68 1b b9 00 00 7b b8 1c e0 61 2e
6e 18 c9 f1 13 e3 81 9f 80 2d 91 2d
71 9f 70 2d 81 0d 97 1d 61 9f 60 2d
71 0d 87 1d 97 1d 51 9f 50 2d 61 0d
77 1d 87 1d 97 1d 41 9f 40 2d 51 0d
67 1d 77 1d 87 1d 97 1d 45 0f 56 1f
67 1f 78 1f 89 1f 97 1d 46 0f 57 1f
68 1f 79 1f 87 1d 97 1d 48 0f 59 1f
67 1d 77 1d 87 1d 97 1d 45 2f 56 2f
67 2f 78 2f 89 2f 99 27 86 95 77 95
67 95 57 95 47 95 6a 94 39 f6 42 0d
53 1d 64 1d 75 1d 87 1d 08 95

```

Here is the breakdown, including a short header to demonstrate calling the function.

```
0x0000  1fef      ldi  r17, 0xFF  ; write 1111 1111
0x0002  1ab9      out  0x0a, r17  ; to port D direction register
0x0004  10e0      ldi  r17, 0x00  ; write 0000 0000
0x0006  1bb9      out  0x0b, r17  ; to port D output register
0x0008  25e0      ldi  r18, 0x05  ; set a to 5
0x000a  04e0      ldi  r16, 0x04  ; set b to 4
0x000c  13e0      ldi  r17, 0x03  ;
0x000e  e12e      mov  r14, r17   ; set c to 3 (can't ldi, r14 < r16)
0x0010  0e940a00  call 0x14       ; call our subroutine @ 0x0014
0x0014  4ee4      ldi  r20, 0x4E  ; initialize output
0x0016  56ef      ldi  r21, 0xF6  ; with maximum 'pi integer'
0x0018  69e5      ldi  r22, 0x59  ; Floor[Pi*10^11]
0x001a  75e2      ldi  r23, 0x25  ;  = 314 159 265 358 (12 digits)
0x001c  89e4      ldi  r24, 0x49  ;  = 0x 49 25 59 f6 4e
0x001e  90e0      ldi  r25, 0x00
0x0020  2224      eor  r2, r2     ; initialize x
0x0022  2394      inc  r2         ; to 1
0x0024  3324      eor  r3, r3     ; (eor clears a byte)
0x0026  4424      eor  r4, r4
0x0028  5524      eor  r5, r5
0x002a  7724      eor  r7, r7     ; r7 stays zero (handy)
0x002c  602e      mov  r6, r16    ; count = b
0x002e  6394      inc  r6         ; count++
0x0030  2017      cp   r18, r16   ; if a >= b
0x0032  10f4      brcc .+4        ; go to loop @ 0x0038
0x0034  2224      eor  r2, r2     ; otherwise x is zero
0x0036  12c0      rjmp .+36       ; go to end of loop @ 0x005c
0x0038  2615      cp   r18, r6    ; if a < count
0x003a  80f0      brcs .+32       ; go to end of loop @ 0x005c
0x003c  569c      mul  r5, r6     ; otherwise multiply high byte by count
0x003e  502c      mov  r5, r0     ; copy low byte of result (high byte = 0)
0x0040  469c      mul  r4, r6     ; multiply second byte by count
0x0042  402c      mov  r4, r0
0x0044  510c      add  r5, r1     ; carry
0x0046  369c      mul  r3, r6     ; multiply third byte
0x0048  302c      mov  r3, r0
0x004a  410c      add  r4, r1
0x004c  571c      adc  r5, r7
0x004e  269c      mul  r2, r6     ; multiply low byte
0x0050  202c      mov  r2, r0
0x0052  310c      add  r3, r1
0x0054  471c      adc  r4, r7
0x0056  571c      adc  r5, r7
0x0058  6394      inc  r6         ; count++
0x005a  eecf      rjmp .-36       ; return to start of loop @ 0x0038
0x005c  5714      cp   r5, r7     ; if any of the high bytes of x
0x005e  01f5      brne .+64       ; are nonzero
0x0060  4714      cp   r4, r7     ; then jump past 'yelling'
0x0062  f1f4      brne .+60       ; @ 0x00a0
0x0064  3714      cp   r3, r7
0x0066  e1f4      brne .+56
0x0068  2e14      cp   r2, r14    ; only the low byte is a comparison
0x006a  d0f4      brcc .+52       ; since c is only one byte long
0x006c  10e5      ldi  r17, 0x50  ; write 'P' to buffer
0x006e  1bb9      out  0x0b, r17  ; write to PORTD
0x0070  1068      ori  r17, 0x80  ; set clock bit (buffer |= 1000 0000)
0x0072  1bb9      out  0x0b, r17  ; PORTD
0x0074  19e6      ldi  r17, 0x69  ; 'i'
0x0076  1bb9      out  0x0b, r17  ; PORTD
0x0078  1068      ori  r17, 0x80  ; 1000 0000
0x007a  1bb9      out  0x0b, r17  ; PORTD
0x007c  11e2      ldi  r17, 0x21  ; '!'
0x007e  1bb9      out  0x0b, r17  ; PORTD
0x0080  1068      ori  r17, 0x80  ; 1000 0000
0x0082  1bb9      out  0x0b, r17  ; PORTD
0x0084  1f77      andi r17, 0x7F  ; clear clock bit (buffer &= 0111 1111)
0x0086  1bb9      out  0x0b, r17  ; PORTD
0x0088  1068      ori  r17, 0x80  ; 1000 0000
0x008a  1bb9      out  0x0b, r17  ; PORTD
0x008c  1f77      andi r17, 0x7F  ; 0111 1111
0x008e  1bb9      out  0x0b, r17  ; PORTD
0x0090  1068      ori  r17, 0x80  ; 1000 0000
0x0092  1bb9      out  0x0b, r17  ; PORTD
0x0094  1f77      andi r17, 0x7F  ; 0111 1111
0x0096  1bb9      out  0x0b, r17  ; PORTD
0x0098  1068      ori  r17, 0x80  ; 1000 0000
0x009a  1bb9      out  0x0b, r17  ; PORTD
0x009c  0000      nop             ; baud rate is 1/4 processor speed
0x009e  7bb8      out  0x0b, r7   ; PORTD
0x00a0  1ce0      ldi  r17, 0x0C  ; buffer = 12
0x00a2  612e      mov  r6, r17    ; count = buffer (# of places in p)
0x00a4  6e18      sub  r6, r14    ; count -= c (# of /= 10 we need)
0x00a6  c9f1      breq .+114      ; if count == 0 skip loop @ 0x011a
0x00a8  13e3      ldi  r17, 0x33  ; buffer = 51
0x00aa  819f      mul  r24, r17   ; following the same procedure as before
0x00ac  802d      mov  r24, r0    ; we multiply p by 51
0x00ae  912d      mov  r25, r1
0x00b0  719f      mul  r23, r17   ; since we can't divide by 10
0x00b2  702d      mov  r23, r0    ; we divide by 5
0x00b4  810d      add  r24, r1    ; by multiplying by
0x00b6  971d      adc  r25, r7    ; 0b0.00110011001100110011
0x00b8  619f      mul  r22, r17   ; equivalent to multiplying by
0x00ba  602d      mov  r22, r0    ; 0b110011 = 51
0x00bc  710d      add  r23, r1    ; then repeatedly adding to itself
0x00be  871d      adc  r24, r7    ; shifted right by one byte
0x00c0  971d      adc  r25, r7
0x00c2  519f      mul  r21, r17
0x00c4  502d      mov  r21, r0
0x00c6  610d      add  r22, r1
0x00c8  771d      adc  r23, r7
0x00ca  871d      adc  r24, r7
0x00cc  971d      adc  r25, r7
0x00ce  419f      mul  r20, r17
0x00d0  402d      mov  r20, r0
0x00d2  510d      add  r21, r1
0x00d4  671d      adc  r22, r7
0x00d6  771d      adc  r23, r7
0x00d8  871d      adc  r24, r7
0x00da  971d      adc  r25, r7
0x00dc  450f      add  r20, r21   ; add p to itself, shifted one byte
0x00de  561f      adc  r21, r22
0x00e0  671f      adc  r22, r23
0x00e2  781f      adc  r23, r24
0x00e4  891f      adc  r24, r25
0x00e6  971d      adc  r25, r7
0x00e8  460f      add  r20, r22   ; shifted two bytes
0x00ea  571f      adc  r21, r23
0x00ec  681f      adc  r22, r24
0x00ee  791f      adc  r23, r25
0x00f0  871d      adc  r24, r7
0x00f2  971d      adc  r25, r7
0x00f4  480f      add  r20, r24   ; shifted four bytes
0x00f6  591f      adc  r21, r25
0x00f8  671d      adc  r22, r7
0x00fa  771d      adc  r23, r7
0x00fc  871d      adc  r24, r7
0x00fe  971d      adc  r25, r7
0x0100  452f      mov  r20, r21   ; shift right one byte
0x0102  562f      mov  r21, r22
0x0104  672f      mov  r22, r23
0x0106  782f      mov  r23, r24
0x0108  892f      mov  r24, r25
0x010a  9927      eor  r25, r25   ; clear top byte
0x010c  8695      lsr  r24        ; finally divide by two
0x010e  7795      ror  r23        ; by shifting right one bit
0x0110  6795      ror  r22
0x0112  5795      ror  r21
0x0114  4795      ror  r20
0x0116  6a94      dec  r6         ; count--
0x0118  39f6      brne .-114      ; if count != 0, repeat @ 0x00a8
0x011a  420d      add  r20, r2    ; add x to p
0x011c  531d      adc  r21, r3
0x011e  641d      adc  r22, r4
0x0120  751d      adc  r23, r5
0x0122  871d      adc  r24, r7
0x0124  0895      ret             ; return

```

Note that the since the subroutine directly follows the main routine, the subroutine is actually executed twice. The second `RET` call then tries to read from an empty stack. I left this behavior in the minimal example, since it's not a problem if you go step-by-step through the AVR simulator, and I wanted to keep the byte count low.

## Mathematica (70 bytes, 6 energy points)

```
Function[{a,b,c},If[c>a!/b!,Print["Pi!!!!"]];a!/b!+Floor[Pi 10^(c-1)]]

```
* `a`, `b`, and `c` are 'free', and don't count towards the number of accesses.
* The string contains six characters, which count as six bytes.

# Answer
> 1 votes
# Javascript (155 bytes, 14+ accesses)

Alright, this isn't the most golfed answer.

Quoting this: "**Arrays cost the sum of all their variables**"... I have no idea how to interpret this, since an array is simply a set of values all aligned in the memory.

Also, there's no information about how to access functions or anything else.

But here is the code:

```
function(a,b,c){var m=[1,1,2,6,24,120,720],f=function(n){return m[n]=m[n]?m[n]:n*f(n-1)};return ((f(a)/f(b))+(+'3141592653589'.substr(0,c)))<c?'PI!!!':'';}

```

For the score (using a=5, b=4, and c=3):

1. Creates an array with the factorial until 7 already there (? accesses)
2. Creates a variable `f` with a function to access the array (? accesses)
3. Calculates the factorial of `a` (2 accesses)
4. Calculates the factorial of `b` (2 accesses)
5. Divides them (2 accesses)
6. Calculates the sum of the number "equivalent to PI" ~~(`Math.PI*Math.pow(10,c)>>0`)~~ now it is only 3 accesses since it fetches `c` characters from the string and converts to integer:
    * ~~Gets the value of PI (∞ accesses)~~
    * ~~Calculates the power of 10 to multiply by `Math.PI` (∞ accesses + 1)~~
    * ~~Sums it all together (2 accesses)~~
    * ~~Rounds it (1 access)~~
7. Compares with `c` (2 accesses)
8. Either returns an empty string (0 accesses) or `PI!!!!` (6 accesses).

~~Result: To be improved! The battery would die in no time! **DO NOT RUN THIS CODE ON YOUR ROBOT OR IT WILL EXPLODE**

I assume that the access to the `window` object is ∞ (infinite) due to the fact that it contains everything, including itself.~~

Conclusion: I'm missing some crucial information and explanation to calculate the final number of accesses. But shouldn't be too bad, right?

---

Why am I using `var`? Simple: if it is declared without `var`, it is effectively accessing the `window` object which is a ∞ (infinite) number of accesses and the battery wouldn't even last 1 nanosecond. We would have a very fast drain, probably followed by an explosion.

---

# Javascript (165 bytes, 31 bytes for the factorial array + 16 accesses):

This one should be easier to calculate

```
function(a,b,c){var m=[1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800];return ((m[a]/m[b])+(+'3141592653589'.substr(0,c)))<c?'PI!!!':'';}

```

It has a 31 bytes-long list with all the 13 factorial numbers required.
It was calculated with the following code:

```
var i=0,m=[1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800],k;for(k in m)i+=Math.ceil(m[k].toString(2).length/8);

```

This makes it faster (if time is critical) and cleaner both for humans and machines. With a **VERY** good branch-prediction, the number of accesses could be reduced to 7 accesses.

It works as the code above, except that it doesn't have to calculate the factorial.

---

# Javascript (3 bytes, self-destruction)

Yes, the smallest losing entry!

It drains your battery so fast it will explode!

It's simple, just run:

```
top

```

And you are set. `top` is a variable that will access to `window.top`, which is the same as `window`, which has recursion **EVERYWHERE**

---

# Javascript (31\*2+6+6 bytes (592 bits), 187\*2+42+38=494 bits ):

Same thing as before, but a lot easier to calculate the number of accesses:

```
function(a,b,c){var m=[1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800];return ((m[a]/m[b])+(''.substr.call(3141592653589,0,c)))<c?'PI!!!':'';}

```

Empty strings and `0` aren't being calculated. Why? They are **NOTHING** in the memory. They only have a datatype.

The aray is being accessed twice, so, I'm counting that the entire array must be scattered.

If not, then the number of accesses drops to **22 bytes (146 bits)**!!!

That is for the worst case!!!

# Answer
> 1 votes
Both of these are ports of @IsmaelMiguel's answer.

# K, 59 bytes, # of accesses is proportional to input size

```
f:{:[z>(l[x]%(l:*/1+!:)y)+0$z#"3141592653589";"PI!!!!";""]}

```

The number of accesses would be something like (assuming a, b, and c are free):

```
a*4+b*4+19

```

# C89, 172 bytes (DON'T LOOK! CAST AWAY!)

```
int l(int n){int r=1;while(n--)r*=r;return r;}char s[]="PI!!!!";char*f(int a,int b,int c) {char p[]="3141592653589";p[c-1]=0;if(l(a)/l(b)+strtol(p,0,0)>=c)s[0]=0;return s;}

```

Apparently we're not allowed to use recursion, so this increased by several characters. Darn it.

Again assuming a, b, and c are free, the # of accesses might be something like:

```
a*4*4+b*4*4+3*4+3*8+15 == a*16+b*16+51

```

Thanks to @mbomb007 for pointing out I accidentally forgot an exclamation mark in "PI!!!!".

# Answer
> 0 votes
### Java (4 Energy points, maybe)

Here's my solution. I am not entirely sure how to score it as I might be invalid.

Calculating `p` wasn't part of the output so I skipped it (the people holding the bot wouldn't know if it was calculated or not). Also, I'm not sure if this is counts for hardcoding and I don't have enough rep to comment to ask.

```
public class Bot {
    public void foo(final int a, final int b, final int c) {
        if (b > a) {
            return;
        }
        int x = a - b;
        if (x > 4) {
            return;
        } else if (x == 3 && c < 7) {
            return;
        } else if (x == 2 && c < 3) {
            return;
        } else if (c < 2) {
            return;
        }
        System.out.println("Pi!!!!");
    }
}

```

---
Tags: code-challenge, math, pi, factorial
---


title: Output a Face on a Numbered Cube

text:
# Question
Title: Output a Face on a Numbered Cube
Assign the numbers 0 through 7 to the 8 vertices of a cube in any way you want. Exactly one number must be assigned to each vertex.

For example, your vertices might be assigned like this:

```
  3-----1
 /|    /|
4-----2 |
| |   | |
| 5---|-0
|/    |/
6-----7

```

Write a program that takes in an integer from 0 to 5. Each of these 6 numbers is associated with exactly one face of your cube in any way you like. When one of these numbers is input, the 4 vertex numbers of the associated face must be printed to stdout in a 2×2 square of digits. The face is to be viewed straight on from outside the cube. All 4 face rotations are valid.

For example, if 0 is associated with the front face of the example cube above, then this would be a valid output for input `0`:

```
42
67

```

The face may be viewed at any 90° rotation, so these are also valid:

```
27
46
```

```
76
24
```

```
64
72
```

This output (and its rotations) are **not valid**, as they are viewed from the wrong side of the face:

```
24
76

```

The same idea applies to all other faces. e.g. if 1 is associated with the back face, then input `1` might produce output `13[newline]05` (and `31[newline]50` would be invalid).

So the real challenge is choosing your vertex numbers and rotations such that translating the input into its 4 vertex numbers is easy and short.

**The shortest code in bytes wins. Tiebreaker is earlier post.** (Handy byte counter.)

### Notes

* You may write a function instead of a program. It should take an integer from 0 to 5 and print or return the 2×2 digit grid string.
* Take input from stdin, command line, or function arg. You may assume input is valid.
* The output may optionally have a trailing newline.
* Be sure to tell us the vertex and face numbers you chose.

# Answer
> 17 votes
# CJam, ~~23~~ 16 bytes

There's probably an elegant mathematical solution to this problem. ~~But I have no clue how to find one, so super compressed hard coding it is!~~

I found one! Well, it's not a classically elegant mathematical solution as it uses bitwise operations, but it is entirely formulaic.

```
li_o1^_p_6|o3+6%

```

Try it online.

### Cube layout

```
  4-----7          4-----7          3-----2
 /|    /|         /  0  /|         /  3  /|
1-----0 |        1-----0 |        6-----5 |
| |   | |        |     |2|        |     |4|
| 5---|-2        |  1  | 2        |  5  | 7
|/    |/         |     |/         |     |/
6-----3          6-----3          1-----4

```

### Explanation

My old answer already laid out the cube such that each face can be described with its first (top-left) vertex number equal to the face number. But I wanted to be able to calculate more vertex numbers using the face number. At some point, I came up with the idea that got my foot in the door, to calculate the second (top-left) vertex number as the face number XOR 1. And after a while of trial and error, I managed to come up with the layout shown above and the formulas below that allow me to to calculate *every* vertex number for a face `n` quite succinctly:

* Top-left: `n`
* Top-right: `n^1`
* Bottom-left: `(n^1)|6`
* Bottom-right: `((n^1)+3)%6`

For reference, I'll reproduce the output for each face in the desired layout here:

```
Face:      0     1     2     3     4     5

Vertices:  01    10    23    32    45    54
           74    63    70    65    72    61

```

So the whole program just comes down to reading the input face number and producing these values in order, albeit with slightly different printing logic for different vertices. Note that, because every vertex after the first starts with a base of `n^1`, I only need to calculate that once, which compacts the logic even further.

---

*For posterity's sake, and because I think it was still a pretty good approach, here's my old answer.*

# CJam, 23 bytes

There's probably an elegant mathematical solution to this problem. But I have no clue how to find one, so super compressed hard coding it is!

```
"pÜ×ñè¨"487b8b3/ri_o=~p

```

Try it online.

### Cube layout

```
  0-----7          0-----7          3-----6
 /|    /|         /  0  /|         /  3  /|
1-----2 |        1-----2 |        4-----5 |
| |   | |        |     |2|        |     |5|
| 5---|-6        |  1  | 6        |  4  | 7
|/    |/         |     |/         |     |/
4-----3          4-----3          1-----0

```

### Explanation

The basic approach employed is to hard code the vertices for each face in as little space as possible. Similarly to Optimizer's base conversion solution, this treats the vertex list as an octal number packed as ASCII character data. But that's about where the similarities end to make way for further optimizations!

Here are the three key optimizations I made to the "naive" solution:

* Lay out the cube such that each face can be described with its face number as the first vertex number. Looking at my cube layout as presented above, one can see that the top-left vertex number of each face is equal to the face number. This allows me to encode six fewer vertices at the cost of having to print the input back, which turns out to save a byte.
* Pack the vertex data into a string for which each "character" has a maximum larger than 256. As this maximum increases past 256, the length of the string slowly decreases, but it becomes increasingly likely that any one "character" exceeds 256 and is thus no longer part of the 1-byte ASCII character set. So I wrote a program that tries encoding the vertex data in every base from 256 to 1000, with which I found about 10 bases that save one byte of character data compared to base 256. I chose 487, as that also has the nice property that the resulting string consists entirely of printable ASCII.
* Mixed with the first optimization, produce the output asymetrically. The usual approach in CJam would be to format the vertex data as a 2-element list of 2-element lists, insert a newline in the middle, and let the output be implicitly printed. But I instead print the first vertex (equal to the input face number) with an operator that doesn't add a newline, retrieve the 3-element list of the other vertices, grab the next vertex and print it with an operator that does add a newline, and let the other two vertices be implicitly printed. This saves a byte.

# Answer
> 14 votes
# C,69

```
f(c){int d=c++%2*2-1;printf("%d%d\n%d%d",(c-d)%6,c%6,c%2+6,(c+d)%6);}

```

**Ungolfed in test program**

```
f(c){
 int d=c++%2*2-1;
 printf("%d%d\n%d%d",(c-d)%6,c%6,c%2+6,(c+d)%6);
}

int n;
main(){
  scanf("%d",&n);
  f(n);
}

```

**Explanation**

My cube numbering, when unfolded, looks like this:

```
0---7
|   |
| 0 |
|   |
1---2---7
|   |   |
| 1 | 2 |
|   |   |
6---3---4---7
    |   |   |
    | 3 | 4 |
    |   |   |
    6---5---0
        |   |
        | 5 |
        |   |
        6---1

```

The top left corner has the same number as the face.

The bottom right corner has number `(n+2)%6`

For odd `n` the top right corner is `(n+1)%6` and the bottom left is `6`

For even `n` the top right corner is `7` and the bottom left is `(n+1)%6`

The program displays the odd numbers as shown and the even numbers rotated 180 degrees. This means that the top right corner is always `(n+1)%6` and the bottom left is always `(n+1)%2+6`. Inverting `n` and `n+2` is easier (it is done by setting `c=n+1` and using `d` to add or subtract `1` or `-1` as necessary.)

**Output**

```
$ ./a
0
21
70

$ ./a
1
12
63

$ ./a
2
43
72

$ ./a
3
34
65

$ ./a
4
05
74

$ ./a
5
50
61

```

# Answer
> 8 votes
# Element, 18

```
_4:2%6+``2+6%`-5+`

```

Unlike many more advanced golfing languages, Element does not have a compression operator, so the brevity of the solution is tied rather closely to the exact numbering scheme used. After some experimentation, I have created a new numbering scheme which allows the vertices to be computed using only simple arithmetic operations.

```
  1-----0          1-----0          2-----5
 /|    /|         /  4  /|         /  3  /|
4-----6 |        4-----6 |        3-----7 |
| |   | |        |     |0|        |     |5|
| 7---|-5        |  2  | 5        |  1  | 0
|/    |/         |     |/         |     |/
3-----2          3-----2          4-----1

```

The top-left corner is 6 if even and 7 if odd. The top-right corner is the face number itself. The bottom-left is the face number, plus 2, mod 6. The bottom-right is 5 minus the face number.

Here is an explanation of the code.

```
_4:2%6+``2+6%`-5+`
_4:                    take input and make several copies of it
   2%6+`               take face #, mod 2, add 6, and output
        `              output input, which already has the newline attached
         2+6%`         take face #, add 2, mod 6, and output
              -5+`     negate face #, add 5, and output

```

Here are the outputs for each of the faces:

```
0
60
25

1
71
34

2
62
43

3
73
52

4
64
01

5
75
10

```

# Answer
> 6 votes
# Octave, ~~108~~ ~~100~~ ~~68~~ 50 bytes

Of course ther is a way of doing it way more elegant than my previous approaches, plain hardcoding. I am amazed how Octave is way more suitable for codegolf than Matlab=)

```
f=@(n)['040201375767';'261345154623'](:,2*n+(1:2))

```

## Layout:

(Sorry, I forgot to add this.)

### Cube layout

```
  1-----5          1-----5          6-----7
 /|    /|         /  2  /|         /  5  /|
0-----4 |        0-----4 |        2-----3 |
| |   | |        |     |4|        |     |3|
| 3---|-7        |  0  | 7        |  1  | 5
|/    |/         |     |/         |     |/
2-----6          2-----6          0-----1

```

## Old Versions:

```
f=@(n)[0 4 0 2 0 1 3 7 5 7 6 7;2 6 1 3 4 5 1 5 4 6 2 3](:,2*n+(1:2))

```

Even older Versions:

This is really gonna make a 2x2x2 array and then choosing a 'slice'. We do a 3d matrix permutation and each time choose the top or bottom slice. (This one does not work in matlab because of the indexing of an expression rather than a matrix) I am sure there would be more direct ways of doing it that would be shorter.

```
f=@(n)squeeze(permute(reshape(0:7,2,2,2),circshift((1:3)',n))(n=fix(n/3)+1,circshift((1:2)',n-1),:))

f=@(n)squeeze(permute(reshape(0:7,2,2,2),circshift((1:3)',n))(floor(n/3)+1,circshift((1:2)',floor(n/3)),:))

```

# Answer
> 5 votes
# CJam, ~~31~~ 28 (or 26) bytes

```
8,2/W%_1m<]z[D75K46]2/+ri=N*

```

which can also be compressed using base conversion into a 26 bytes version.

Assumes the cube to be like:

```
  7-----1
 /|    /|
5-----3 |
| |   | |
| 6---|-0
|/    |/
4-----2

```

with faces like

```
  7-----1      .-----.      .-----.      .-----.
 /  4  /|     /  4  /|     /  4  /|     /  0  /|
5-----3 |    .-----. |    .-----. |    .-----. |
|     |2|    |     |1|    |     |0|    |     |5|
|  1  | 0    |  0  | .    |  3  | .    |  3  | .
|     |/     |     |/     |     |/     |     |/
4-----2      .-----.      .-----.      .-----.

```

Try it online here

# Answer
> 4 votes
# JavaScript (ES6), 53 ~~62~~

**Edit** Save 8 bytes using template strings, thx @NinjaBearMonkey. Beware, the newlines inside quotes are significant and cannot be collapsed.

Can't be clever in Javascript, it's too verbose.

```
f=n=>`01
23
45
67
01
31
5702
64`.substr(n-4?n*3:20,5)

```

*Output* `for(i=0;i<6;i++)console.log(f(i),i)`

> 01
> 23
> 0
>
> 23
> 45
> 1
>
> 45
> 67
> 2
>
> 67
> 01
> 3
>
> 02
> 64
> 4
>
> 31
> 57
> 5

See the snippet to veify the number associations (*that* was fun)

```
function P3D(x,y,z) {
    this.x = x;this.y = y;this.z = z;
    this.rotateX = angle => {
        var rad = angle * Math.PI / 180,
        cosa = Math.cos(rad),sina = Math.sin(rad),
        y = this.y * cosa - this.z * sina,
        z = this.y * sina + this.z * cosa
        return new P3D(this.x, y, z)
    }
    this.rotateY = angle => {
        var rad = angle * Math.PI / 180,
        cosa = Math.cos(rad), sina = Math.sin(rad),
        z = this.z * cosa - this.x * sina,
        x = this.z * sina + this.x * cosa
        return new P3D(x,this.y, z)
    }
    this.rotateZ = angle => {
        var rad = angle * Math.PI / 180,
        cosa = Math.cos(rad), sina = Math.sin(rad),
        x = this.x * cosa - this.y * sina,
        y = this.x * sina + this.y * cosa
        return new P3D(x, y, this.z)
    }
    this.project = (viewWidth, viewHeight, fov, viewDistance) => {
        var factor = fov / (viewDistance + this.z),
        x = this.x * factor + viewWidth / 2,
        y = this.y * factor + viewHeight / 2
        return new P3D(x, y, this.z)
    }
}

var vx = [
    new P3D(-1,1,-1),
    new P3D(1,1,-1),
    new P3D(-1,-1,-1),
    new P3D(1,-1,-1),
    new P3D(-1,-1,1),
    new P3D(1,-1,1),
    new P3D(-1,1,1),
    new P3D(1,1,1),
];
// Define the vx that compose each of the 6 faces. These numbers are
// indices to the vertex list defined above.

var faces = [[0,1,3,2],[2,3,5,4],[4,5,7,6],[6,7,1,0],[0,2,4,6],[1,3,5,7]]

faces.map((f,i)=>{
    var mx=vx[f[0]].x+vx[f[1]].x+vx[f[2]].x+vx[f[3]].x,
    my=vx[f[0]].y+vx[f[1]].y+vx[f[2]].y+vx[f[3]].y,
    mz=vx[f[0]].z+vx[f[1]].z+vx[f[2]].z+vx[f[3]].z
    vx[i+10]=new P3D(mx/4, my/4, mz/4)
    f[4]=i
    f[5]=i+10
})

var angle = 0;

var ctx = CV.getContext("2d");

setInterval(loop,33)

function loop() {
    ctx.fillStyle = "#fff"
    ctx.fillRect(0,0,400,200);
    ctx.font = "20px Arial"
    angle += 2

    var t = vx.map(v=>
        v
        .rotateX(angle).rotateY(-angle).rotateZ(-angle)
        .project(400,200,128,3)
    )

    ctx.strokeStyle = "#f00"
    t.forEach((v,i)=>i<8?ctx.strokeText(i,v.x,v.y):0)

    ctx.strokeStyle = "#428"
    ctx.beginPath()
    faces.forEach(f=>(
        ctx.moveTo(t[f[0]].x,t[f[0]].y),
        ctx.lineTo(t[f[1]].x,t[f[1]].y),
        ctx.lineTo(t[f[2]].x,t[f[2]].y),
        ctx.lineTo(t[f[3]].x,t[f[3]].y),
        ctx.lineTo(t[f[0]].x,t[f[0]].y),
        ctx.strokeText(f[4],t[f[5]].x,t[f[5]].y)
    ))
    ctx.closePath(),
    ctx.stroke()
}
```

```
<canvas id=CV width=400 height=200></canvas>
```

# Answer
> 4 votes
# Ruby Rev 1,  ~~40~~ 36

`->(c){print(c^1,c,"\n",6|c,(c+3)%6)}`

Thanks to @rcrmn for suggesting using a lambda to save 4 bytes. I wasn't sure about leaving it anonymous but it seems to have been discussed on meta here and decided this was OK.

Here it is as a 40-byte function, for comparison with my Rev 0 Ruby answer, also below (Original C answer is in a separate post.)

```
def f(c)print(c^1,c,"\n",6|c,(c+3)%6)end

```

Further inspiration from Runer112: This relies on a modification of the numbering scheme used in his latest (16 byte!) answer. A direct port of PhiNotPi's scheme would give the same score.

By shifting the numbering from Rev 0 round one step, and taking everything XOR 1, we get the following cube:

```
4---7
|   |
| 1 |
|   |
1---0---7
|   |   |
| 0 | 3 |
|   |   |
6---3---2---7
    |   |   |
    | 2 | 5 |
    |   |   |
    6---5---4
        |   |
        | 4 |
        |   |
        6---1

```

Output

```
0
10
63

1
01
74

2
32
65

3
23
70

4
54
61

5
45
72

```

# Ruby Rev 0, ~~56 52~~ 50

Saved 4 bytes by removing unnecesary `()%6`from `c-d` and another 2 (inspired by runer112) by `6+c%2 --> 6|c` .

Score is for the function, which is just the first line. I'm new to Ruby and I'm surprised I can't find a shorter way than 12 characters (11 plus newline) to get a user input number into n. As a result, doing a function instead of a program saves 1 byte.

```
def f(c)d=c%2*2-1;print((c+d)%6,c,"\n",c|6,c-d)end

n=gets.to_i
f(n)

```

This is a port of my C answer. In C, the `%` operator returns a negative value with a negative number. In Ruby it always returns a positive value, so there is no need to add 1 to `c`. As a result, it is advantageous to shift the numbering of the faces by 1 as below:

```
0---7
|   |
| 1 |
|   |
1---2---7
|   |   |
| 2 | 3 |
|   |   |
6---3---4---7
    |   |   |
    | 4 | 5 |
    |   |   |
    6---5---0
        |   |
        | 0 |
        |   |
        6---1

```

With the new face numbering, the program prints the evens as shown above and the odds rotated through 180 degrees:

```
1
21
70

2
12
63

3
43
72

4
34
65

5
05
74

0
50
61

```

# Answer
> 4 votes
## CJam (25 bytes)

```
"ñRXµ  roM~"(ib65b2/q~=N*

```

This contains a non-printable character and a tab (which will be mangled by the StackExchange software), so in xxd format:

```
0000000: 22f1 5258 1fb5 0972 6f4d 7e22 2869 6236  ".RX...roM~"(ib6
0000010: 3562 322f 717e 3d4e 2a                   5b2/q~=N*

```

Online demo

Cube:

```
  1-----0        Faces:
 /|    /|        10 46
4-----6 |        14 37
| |   | |        20 31
| 3---|-2        23 57
|/    |/         56 20
7-----5          57 64

```

This is pure hard-coding, with the cube vertices selected to maximise base compressibility. I decode to 2-digit numbers, so none of them can begin with 0. I don't want any to begin with 7 either, since that pushes the second base too high. Therefore 0 and 7 must be on a long diagonal. I want a 10 edge to go first to reduce the value I'm encoding. Other than that, there's a fair amount of flexibility without changing the byte count.

I'm slightly disappointed that having popped the first character from the magic string, it's necessary to cast it to an int before using it as a base for base conversion. Hopefully future versions of CJam will save that byte, although it will be too late to exploit that here.

# Answer
> 3 votes
# Pyth, 30

Thanks @Jakube for 2 bytes.

```
Jc2jkfx>Q2!.&T^2%Q3U8jb?_J%Q2J

```

Try it here.

Golfing advice from pyth experts will be graciously accepted. In particular I think the output section might have some improvements.

Port of the following python:...

# Python, 109

```
Q=input()
s=''.join(map(str,filter(lambda v:(Q<3)^(v&(1<<Q%3)>0),range(8))))
print s[1-Q%2::2],'\n',s[Q%2::2]

```

...which is a port of

# Pure Bash, 130

For the purposes of explanation:

```
for v in {0..7};{
if(($1/3));then((v&(1<<$1%3)))&&a+=$v
else((v&(1<<$1%3)))||a+=$v
fi
}
i=$[$1%2*2]
echo "${a:i:2+i}
${a:2-i:4-i}"

```

The cube vertices are numbered thus:

```
  4-----5
 /|    /|
0-----1 |
| |   | |
| 6---|-7
|/    |/
2-----3

```

And the faces are numbered thus:

```
Face  Vertices  Swap
   0  0,2,4,6
   1  0,1,4,5   x
   2  0,1,2,3
   3  1,3,5,7   x
   4  2,3,6,7
   5  4,5,6,7   x

```

The `Swap` column indicates the order of the vertices should be switched in the output.

The algorithm starts out with all vertices {0..7}. Vertices are eliminated according to bits set in the vertex numbers:

* For faces 0,1 and 2, vertices with bits 1,2 or 3 cleared respectively are kept
* For faces 3,4 and 5, vertices with bits 1,2 or 3 set respectively are kept

The "kept" vertices are appended to a string. The string is output chars 0,1 then 2,3 or vice versa, depending on whether the swap flag (face number mod 2) is set.

# Answer
> 1 votes
# J - 26 bytes

Function taking face number as argument and returning the grid of digits.

```
0{.@":"0@{0&(|:|.)&(i.3#2)

```

We are using the following cube:

```
  4-----5    Face numbers:
 /|    /|     0 - front
0-----1 |     1 - top
| |   | |     2 - left
| 6---|-7     3 - back
|/    |/      4 - bottom
2-----3       5 - right

```

Example (try it yourself at tryj.tk):

```
   0{.@":"0@{0&(|:|.)&(i.3#2) 3         NB. inline
76
54
   f =: 0{.@":"0@{0&(|:|.)&(i.3#2)      NB. named
   f each 0 1 2 3 4 5                   NB. all results
+--+--+--+--+--+--+
|01|40|64|76|37|13|
|23|51|20|54|26|57|
+--+--+--+--+--+--+

```

The bread and butter is `0&(|:|.)`. This is a verb that reverses and rotates the cube in such as way as to visit every face when iteratively applied, which is what we do using the input argument. The vertices of the cube are generated by `i.3#2`, so we use that as the starting point, and take the front face `0...{` when we're done.

Printing the digits as a string costs 8 chars: `{.@":"0@` If we were allowed to simply return an array, that's a saving of 8 whole characters. *\[commences fist-shaking and indiscernible griping\]*

# Answer
> 0 votes
# \>\<\> (Fish), 38 bytes

```
'/ =/2= 28"H5'a@i-!
noan~\;
~>:?!^1-@~

```

Every output is stored as two 2-digit rows. The rows are stored as charcodes in the string `'/ =/2= 28"H'` (except the row `10` which is appended after the string as `a`). The first character (`/ = 47`) is used to redirect the program flow on the second interaction.

The top `2*(53-n)` elements are discarded (where n is the charcode of the input number) and the next two codes are printed with a newline between.

Layout:

```
  3-----2
 /|    /|
4-----7 |
| |   | |
| 5---|-0
|/    |/
6-----1      0 1 2 3 4 5 sides are top front bottom back left right respectively.

```

---
Tags: code-golf, geometry
---