title: Coin Tossing Time Travelers

text:
# Question
Title: Coin Tossing Time Travelers
In the future when Time Travel (abbreviated as TT) will be common, coin tossing will become a serious mind-sport. To prepare for the future we create a competition for programs where time traveling will be really happening from the viewpoints of the entries.

The competition is a round-robin style King of the Hill consisting of coin tossing matches between Java classes.

## Rules of the coin tossing match

* There are two players and 100 rounds.
* In every round a coin is tossed and based on the result one of the players scores 1 point. Each player has 50% chance to score a point.
* After the tossing both players have a chance to control the time by pulling levers.
* If you pull a **blue lever (revert stopper)** no TT is possible to the round the lever was used or any earlier round anymore. TT's attempting to go to these rounds will have no effect.
* If you pull a **red lever (reverter)** you try to revert the time back to a former round. If succeeded the **opponent's memory will be reverted** to its memory before the chosen round and the **coin toss results starting from the chosen round will also be deleted**. The only possible sign for your opponent about the TT will be the number of its unused levers which will not be reverted back.
* Each player has 5 blue and 20 red unused levers at the start of the match. These levers are not affected by TT's.
* If no TT happens at the end of a 100th round the game ends and the player with the higher score wins.

## Details

* Rounds have a 1-based indexing (form 1 to 100).
* Before round `x` you are provided the number of available blue and red levers, the coin toss results until turn `x` (inclusive) and the memory of your (last) `x-1`th round.
* Pulling a blue lever in round `x` stops any TT's that have a destination at round `x` or before (it blocks a TT if it happens on that same exact round too).
* Reverting to round `x` means that the next round will be round `x`.
* If both players choose to revert at the end of a round the time is reverted to the earlier destination which is not blocked. The player(s) who tried to revert to this time will keep their memory.

## Technical details

* You should write a Java class implementing the provided Bot interface.
* Add your bot to the project.
* Add an instance of your Bot to the `Bot` in the file `Controller.java`.
* Your class should **not keep information between calls**. (In most cases having only `final` variables outside of functions satisfies this requirement.)
* You can give information to the controller in the `memory` field of your returned `Action` object. This will be given back to you in the next turn if no TT happened. If a TT happens, you will receive the corresponding earlier memory of yours.
* You can use the `totalScore()` method of the `Game` class to get the score of a history string.

## Protocol

* At every turn your `takeTurn(...)` method is called with 5 arguments:

+ the number of unused blue levers
    + the number of unused red levers
    + the coin tossing history, a string consisting of 1's and 0's marking your wins and losses in the previous rounds. The first character corresponds to the first coin tossing. (In the first round the length of the string will be `1`.)
    + a string, your stored memory from the previous round
    + the 1-based index of this round
* At every turn your method returns an `Action` object containing

+ an integer in the `move` field describing your action:

    - `0` for no action
        - `-1` to pull a blue lever and block TT's going through this round
        - a positive integer `x`, not larger than the current round, to pull a red lever and try to revert back to round `x`
        - Invalid integers are treated as `0`.
    + a string containing your memory from this round which you want to preserve. Note that **storing memory is not a crucial part of the challenge**. You can make good entries without storing any useful data in the string. At the first round the string will be an empty string.
* Your method should take no more time than 10 ms per round on average in a match.
* Regularly failing the time-limit results in disqualification.

## Scoring

* Winning a match earns 2 points and a draw earns 1 point for both players. Loss earns no points.
* A bot's score will be the total number of points it collected.
* The number of matches played between each pair of contestants will depend on the number of entries and their speed.

Two simple example bots are posted as answers.

The controller and the first couple Bots are available here.

Test results with bots submitted until November 3.:

Total Scores:

```
Oldschool: 3163
Random: 5871
RegretBot: 5269
Nostalgia: 8601
Little Ten: 8772
Analyzer: 17746
NoRegretsBot: 5833
Oracle: 15539
Deja Vu: 5491
Bad Loser: 13715

```

<sup>(The controller is based on the Cat catcher challenge's controller. Thanks for @flawr providing it as a base for this one.)</sup>

Bonus: a nice 6-minute film based on a similar concept.

# Answer
> 11 votes
# Analyzer

This analyzes the past to make the best predictions for the future.

**EDIT:** Avoids blue levered times. Uses blue levers effectively. Uses red levers more effectively. Added scariness for Halloween season.

**EDIT:** Fixed off by 1 error.

**EDIT:** Improved `computeWinningProbability` function. Now uses red levers and blue lever more aggressively.

```
//Boo!
package bots;

import main.Action;
import main.Game;

import java.util.*;
import java.util.stream.Collectors;

/**
 * Created 10/24/15
 *
 * @author TheNumberOne
 */
public class Analyzer implements Bot{

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

    @Override
    public Action takeTurn(int blue_levers, int red_levers, String history,
                           String memory, int roundNumber) {
        /*System.out.println(Game.totalScore(history) + " : " + history);
        try {
            Thread.sleep(100);
        } catch (InterruptedException e) {
        }*/
        int roundsLeft = 100 - roundNumber;
        int myScore = (Game.totalScore(history) + roundNumber) / 2; //My number of wins.
        int enemyScore = roundNumber - myScore;                     //Enemy's number of wins.
        Map<Integer, Double> bestRounds = new HashMap<>();
        int timeLimit = 0;

        Scanner scanner = new Scanner(memory);
        if (scanner.hasNext()){     //No memory, first turn.
            boolean triedTimeTravel = scanner.nextBoolean();
            if (triedTimeTravel){
                int time = scanner.nextInt();
                if (roundNumber > time) {     //Failed.
                    timeLimit = time;
                }
            }
            timeLimit = Math.max(timeLimit, scanner.nextInt());
            int size = scanner.nextInt();
            for (int i = 0; i < size; i++) {
                bestRounds.put(scanner.nextInt(), scanner.nextDouble());
            }
        } else {
            bestRounds.put(1, 0.5);
        }

        clean(bestRounds, roundNumber, timeLimit);
        double winningProb = computeWinningProbability(myScore, enemyScore, roundsLeft);
        String newMemory = computeMemory(bestRounds, roundNumber, winningProb);

        if (winningProb >= new double[]{1.5, .75, .7, .65, .6, .55}[blue_levers]){ //Ensure success ... slowly.
            return getAction(-1, newMemory, timeLimit, roundNumber);
        }

        int bestRound = bestRound(bestRounds);
        double bestRoundProb = bestRounds.get(bestRound);

        if ((winningProb <= bestRoundProb - .05 || winningProb < .5 && bestRoundProb > winningProb) && red_levers > 0){
            return getAction(bestRound, newMemory, timeLimit, roundNumber);  //Let's find the best past.
        } else {
            return getAction(0, newMemory, timeLimit, roundNumber); //Let's wait it out :)
        }
    }

    //Should be combined with computeMemory.
    private static Action getAction(int actionNum, String newMemory, int timeLimit, int roundNumber){
        if (actionNum == -1){
            timeLimit = Math.max(timeLimit, roundNumber);
            newMemory = "false " + timeLimit + " " + newMemory;
            return new Action(actionNum, newMemory);
        }
        if (actionNum == 0){
            return new Action(actionNum, "false " + timeLimit + " " + newMemory);
        }
        if (actionNum > 0){
            return new Action(actionNum, "true " + actionNum + " " + timeLimit + " " + newMemory);
        }
        return null;
    }

    private static int bestRound(Map<Integer, Double> bestRounds) {
        int best = 0;           //If no previous rounds ... just go forward a round.
        double bestScore = -1;
        for (Map.Entry<Integer, Double> entry : bestRounds.entrySet()){
            if (entry.getValue() > bestScore){
                best = entry.getKey();
                bestScore = entry.getValue();
            }
        }
        return best;
    }

    private static String computeMemory(Map<Integer, Double> map, int roundNumber, double winningProb) {
        StringBuilder builder = new StringBuilder();
        builder.append(map.size() + 1).append(" ");
        for (Map.Entry<Integer, Double> entry : map.entrySet()){
            builder.append(entry.getKey()).append(" ").append(entry.getValue()).append(" ");
        }
        builder.append(roundNumber + 1).append(" ").append(winningProb);
        return builder.toString();
    }

    private static void clean(Map<Integer, Double> data, int round, int timeLimit) {
        data
                .entrySet()
                .stream()
                .filter(entry -> entry.getKey() > round || entry.getKey() <= timeLimit)
                .map(Map.Entry::getKey)
                .collect(Collectors.toList()).forEach(data::remove);
    }

    private static double computeWinningProbability(int myScore, int enemyScore, int roundsLeft){ //Too complex for IntelliJ
        int height = myScore - enemyScore;
        double total = 0.0;
        for (int i = Math.max(height - roundsLeft, 2); i <= height + roundsLeft; i += 2){
            total += prob(roundsLeft, height, i);
        }
        total += prob(roundsLeft, height, 0) / 2;
        return total;
    }

    private static double prob(int roundsLeft, int height, int i){
        double prob = 1;
        int up = i - height + (roundsLeft - Math.abs(i - height))/2;
        int down = roundsLeft - up;
        int r = roundsLeft;
        int p = roundsLeft;
        while (up > 1 || down > 1 || r > 1 || p > 0){  //Weird algorithm to avoid loss of precision.
            //Computes roundsLeft!/(2**roundsLeft*up!*down!)

            if ((prob >= 1.0 || r <= 1) && (up > 1 || down > 1 || p > 1)){
                if (p > 0){
                    p--;
                    prob /= 2;
                    continue;
                } else if (up > 1){
                    prob /= up--;
                    continue;
                } else if (down > 1){
                    prob /= down--;
                    continue;
                } else {
                    break;
                }
            }
            if (r > 1) {
                prob *= r--;
                continue;
            }
            break;
        }
        return prob;
    }

}

```

## Score (since Nov 2):

```
Total Scores:
Oldschool: 3096
Random: 5756
RegretBot: 5362
Nostalgia: 8843
Little Ten: 8929
Analyzer: 17764
NoRegretsBot: 5621
Oracle: 15528
Deja Vu: 5281
Bad Loser: 13820

```

# Answer
> 4 votes
# Oracle

I shamelessly copied some code from Analyzer (for parsing the memory). This submission tries to pull a blue lever early and then slowly builds up his lead. I think the performance of this bot makes up for the ugly code :)

```
package bots;

import java.util.*;
import java.util.Map.Entry;
import main.*;

public class Oracle implements Bot {

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

    @Override
    public Action takeTurn(int blue_levers, int red_levers, String history, String memory, int roundNumber) {
        int roundsLeft = 100 - roundNumber;
        Map<Integer, Integer> rounds = new HashMap<>();
        int myScore = (Game.totalScore(history) + roundNumber) / 2;
        int difference = myScore*2 - roundNumber;
        int highestBlockedRound = -1;
        int bestScore = 0;
        boolean hasUsedBlueLever = false;

        Scanner scanner = new Scanner(memory);
        if (scanner.hasNext()) {
            //timeTravel toRound highestBlockedRound hasUsedBlueLever bestScore rounds round1 percent1 round2 percent2 round3 percent3...
            boolean triedTravel = scanner.nextBoolean();
            int time = scanner.nextInt();
            if (triedTravel){
                if (roundNumber > time) {
                    highestBlockedRound = time;
                }
            }
            highestBlockedRound = Math.max(highestBlockedRound, scanner.nextInt());

            hasUsedBlueLever = scanner.nextBoolean();
            bestScore = scanner.nextInt();

            int size = scanner.nextInt();
            for (int i = 0; i < size && i < roundNumber; i++) {
                int number = scanner.nextInt();
                int diff = scanner.nextInt();
                if (number < roundNumber) {
                    rounds.put(number, diff);
                }
            }
        }
        rounds.put(roundNumber, difference);
        final int blockedRound = highestBlockedRound;

        int roundToRevert = 0;
        if (rounds.size() > 2) {
            Optional<Entry<Integer, Integer>> bestRound = rounds.entrySet()
                    .stream()
                    .filter(x -> x.getKey() >= blockedRound && x.getKey() <= roundNumber)
                    .sorted(Comparator
                        .comparingInt((Entry<Integer, Integer> x) -> x.getValue()*-1)
                        .thenComparingInt(x -> x.getKey()))
                    .findFirst();
            if (bestRound.isPresent()) {
                roundToRevert = bestRound.get().getKey();
            }
        }

        if (roundsLeft + Game.totalScore(history) <= 0 && red_levers > 0) {
            roundToRevert = highestBlockedRound+1;
        } else if (blue_levers > 0 && roundToRevert == roundNumber && ((hasUsedBlueLever && difference >= bestScore*1.5) || (!hasUsedBlueLever && difference > 1))) {
            roundToRevert = -1;
            hasUsedBlueLever = true;
            bestScore = difference;
            highestBlockedRound = roundNumber;
        } else if (red_levers > 0 && roundToRevert > 0 && rounds.get(roundToRevert) > difference+2) {
            roundToRevert += 1;
        } else {
            roundToRevert = 0;
        }

        StringBuilder sb = new StringBuilder();
        sb.append(roundToRevert > 0).append(' ');
        sb.append(roundToRevert).append(' ');
        sb.append(highestBlockedRound).append(' ');
        sb.append(hasUsedBlueLever).append(' ');
        sb.append(bestScore).append(' ');
        sb.append(rounds.size()).append(' ');
        rounds.entrySet().stream().forEach((entry) -> {
            sb.append(entry.getKey()).append(' ').append(entry.getValue()).append(' ');
        });
        String mem = sb.toString().trim();
        scanner.close();
        return new Action(roundToRevert, mem);
    }
}

```

# Answer
> 3 votes
## RegretBot

At the end of ~~our life~~ the match, we regret our past failures, and attempt to go back and fix them.

```
package bots;

import main.Action;
import main.Game;

public final class RegretBot implements Bot {

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

    @Override
    public Action takeTurn(int blue_levers, int red_levers, String history, String memory, int roundNumber) {
        int actionNum = 0;
        if(roundNumber == 100) {
            // if it's the end of the game and we're losing, go back
            //  in time to the first loss, in hopes of doing better
            if(Game.totalScore(history)<=0 && red_levers > 0) {
                actionNum = history.indexOf("0")+1;
            }
            // if we're winning at the end, pull a blue lever if we can,
            //  to prevent our opponent from undoing our victory
            else if(blue_levers > 0) {
                actionNum = -1;
            }
        }
        // we don't need no stinkin' memory!
        return new Action(actionNum, null);
    }

}

```

# Answer
> 3 votes
# Nostalgia

```
package bots;

import main.Action;
import main.Game;

public class Nostalgia implements Bot {

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

    @Override
    public Action takeTurn(int blue_levers, int red_levers, String history,
            String memory, int roundNumber) {

        int current_score = Game.totalScore(history);

        // wait until the end to use blue levers
        if (current_score > 0 && blue_levers >= (100 - roundNumber)) {
            return new Action(-1, memory);
        }

        // become increasingly likely to go back as the gap between the good old days
        // and the horrible present increases
        if (current_score < 0 && red_levers > 0) {
            //identify the best time to travel back to
            int best_score = -100;
            int good_old_days = 1;
            int past_score = 0;

            int unreachable_past = 0;
            if(memory != "") {
              unreachable_past = Integer.parseInt(memory, 10);
            }

            for(int i = unreachable_past; i<roundNumber ; i++) {
              if(history.charAt(i) == '1') {
                past_score += 1;
                if(past_score > best_score) {
                  best_score = past_score;
                  good_old_days = i + 1;
                }
              }
              else {
                past_score -= 1;
              }
            }
            if(roundNumber >= 95 || Math.random() < (best_score - current_score) / 100.0) {
              return new Action(good_old_days, Integer.toString(good_old_days));
            }
        }

        // if neither action was needed do nothing
        return new Action(0, memory);
    }
}

```

Not tested, just a quick stab at trying to make a bot that's difficult to block (because it decides when to pull the red lever mostly randomly) but that makes decent decisions.

Edit: I missed this rule:

> If you pull a blue lever (revert stopper) no TT is possible through that round anymore

That seems like a good reason to use memory -- if you remember trying to TT to a given round, you may have failed, so you shouldn't try to TT to that round again. Edited my bot to try to avoid this.

# Answer
> 2 votes
# Little Ten

Little Ten does a lot of multiplying and dividing by 10, using numbers that are multiples of 10, and going back to rounds that are multiples of 10.

```
package bots;

import main.Action;
import main.Game;

public class LittleTen implements Bot {

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

    @Override
    public Action takeTurn(int blue_levers, int red_levers, String history, String memory, int roundNumber) {
        int score = Game.totalScore(history);
        char c = history.charAt(history.length() - 1);
        if (memory.isEmpty())
            memory = "1";

        if (roundNumber == 100) {
            if (score >= 0)
                // We're tied or ahead by the end of the match. Prevent time
                // travel if we can; otherwise whatever happens happens.
                return new Action(blue_levers > 0 ? -1 : 0, memory);
            else {
                // Travel to earlier rounds the farther behind we are if we can
                // (of course using 10 as a reference)
                if (red_levers > 0) {
                    int i = Integer.parseInt(memory);
                    int round = score <= -10 ? i : 100 - ((100 - i) / (11 + (score <= -10 ? -10 : score)));
                    return new Action(round, memory);
                }
            }
        }
        else if (score >= 7 + roundNumber / 20 && blue_levers > 0) {
            // We're ahead; we don't want to lose our lead, especially if the
            // match is close to ending. But we don't want to use up our blue
            // levers too quickly.
            int choice = (int) (Math.random() * 100),
                bound = (roundNumber / 10 + 1) * 5 - ((6 - blue_levers) * 5 - 2);
            if (choice < bound) {
                memory = String.valueOf(roundNumber);
                return new Action(-1, memory);
            }
        }
        else if (score <= -3) {
            // Possibly use a red lever if we're falling too far behind
            if (red_levers > 0) {
                int choice = (int) (Math.random() * 100),
                    bound = score <= -11 ? 90 : 10 * (-3 - score + 1);
                if (choice < bound) {
                    // Check the first round that is the lower multiple of ten
                    // and decide if we've been successful up to that point; if
                    // so, travel back to that round, otherwise go back 10 more
                    int round = roundNumber / 10 * 10;
                    if (round < 10)
                        return new Action(1, memory);
                    String seq = history.substring(0, round-1);
                    int minRound = Integer.parseInt(memory);
                    while (Game.totalScore(seq) <= 0 && round > 10 && round > minRound) {
                        round -= 10;
                        seq = history.substring(0, round-1);
                    }
                    if (round == 0)
                        round = 1;
                    return new Action(round, memory);
                }
            }
        }
        return new Action(0, memory);
    }
}

```

Edit: Changed the mechanics a little now that the explanation of what happens when a blue lever is pulled is clearer. Also did a bit of rebalancing.

# Answer
> 1 votes
# Random

Random's strategy is the following:

* **block** with a 10% chance if in the lead and has blue levers left
* **travel back** one turn (replaying the last round) with 10% chance if behind in score and has red levers left

```
package bots;

import main.Action;
import main.Game;

public class RandomBot implements Bot {

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

    @Override
    public Action takeTurn(int blue_levers, int red_levers, String history,
            String memory, int roundNumber) {

        // if in the lead and has blocks left, blocks with a 10% chance
        if (Game.totalScore(history) > 0 && blue_levers > 0
                && Math.random() > 0.9) {
            return new Action(-1, null);
        }

        // if behind and has travels left, travel back the current step to
        // replay it with a 10% chance
        if (Game.totalScore(history) < 0 && red_levers > 0
                && Math.random() > 0.9) {
            return new Action(roundNumber, null);
        }

        // if neither action were needed do nothing
        return new Action(0, null);
    }
}

```

# Answer
> 1 votes
# NoRegretsBot

```
package bots;

import main.Action;
import main.Game;

public final class NoRegretsBot implements Bot {

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

    @Override
    public Action takeTurn(int blue_levers, int red_levers, String history, String memory, int roundNumber) {
        // every 20 turns, pull a blue lever to lock in the past
        // hopefully this will thwart some of those pesky time-travelers
        return new Action(roundNumber%20==0?-1:0, null);
    }

}

```

# Answer
> 1 votes
# Bad Loser

This bot uses no memory and is surprisingly good (but it doesn't beat Analyzer or Oracle).

```
package main;

import bots.Bot;

/**
 * Created 11/2/15
 *
 * @author TheNumberOne
 */
public class BadLoser implements Bot{
    @Override
    public String getName() {
        return "Bad Loser";
    }

    @Override
    public Action takeTurn(int blue_levers, int red_levers, String history, String memory, int roundNumber) {
        if (history.contains("00") && red_levers > 0){       //Subtract a zero for better performance against
            return new Action(history.indexOf("00") + 1, "");// Analyzer and Nostalgia, and worse performance
                                                             // against everything else.
        }
        int wins = 0;
        for (char c : history.toCharArray()){
            wins += c - '0';
        }
        if (wins >= new int[]{101, 51, 40, 30, 20, 10}[blue_levers]){
            return new Action(-1, "");
        }
        return new Action(0, "");
    }
}

```

# Answer
> 0 votes
# Oldschool

This bot never does any action as Oldschool doesn't believe in time traveling.

```
package bots;

import main.Action;

public class OldschoolBot implements Bot {

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

    @Override
    public Action takeTurn(int blue_levers, int red_levers, String history,
            String memory, int roundNumber) {
        // never tries to block or travel at all
        return new Action(0, null);
    }
}

```

# Answer
> 0 votes
## Deja Vu Bot

This bot tries to track when it pulls the blue to avoid red pulls into that region. Will only pull red levers when significantly behind in the score.

```
package bots;

import main.*;

public class Dejavu implements Bot
{
    @Override
    public String getName()
    {
        return "Deja Vu";
    }

@Override
public Action takeTurn(int blue_levers, int red_levers, String history,
                       String memory, int roundNumber) {

    if(roundNumber == 1)
    {
        memory = "-1";
    }
    int[] blevers = getBlueLevers(memory);
    char[] hist = history.toCharArray();
    int ms = 0;
    int ts = 0;
    int rl = -1;
    boolean bl = false;
    boolean url = false;

    for(int i = 0; i < hist.length; i++)
    {
        switch(hist[i])
        {
            case '1':
            ms++;
            break;
            case '0':
            ts++;
            break;
        }
    }

    if(ts - ms >= 10)
    {
        for(rl = hist.length - 1; ts - ms <= 5 && rl >= 0; rl--)
        {
            switch(hist[rl])
            {
                case '1':
                ms--;
                break;
                case '0':
                ts--;
                break;
            }
        }
        url = true;
    }

    if(ms - ts >= 7)
    {
        bl = true;
        url = false;
        memory += "," + roundNumber;
    }

    for(int i = 0; i < blevers.length; i++)
    {
        if(rl <= blevers[i])
        {
            rl = blevers[i] + 1;
        }
    }

    if(url)
    {
        return new Action(rl, memory);
    }
    else if(bl)
    {
        return new Action(-1, memory);
    }
    else
    {
        return new Action(0, memory);
    }
}

private int[] getBlueLevers(String s)
{
    String[] b = s.split(",");

    int[] bl = new int[b.length];
    for(int i = 0; i < b.length; i++)
    {
        bl[i] = Integer.parseInt(b[i]);
    }

    return bl;
}

}

```

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


title: Fit the factors in the field

text:
# Question
Title: Fit the factors in the field
Given a positive integer below 1000, display all possible rectangles with that area.

# Task

Let's say the input is 20. We can make a rectangle 20×1, 10×2, or 5×4, so this is a valid output:

```
********************

**********
**********

*****
*****
*****
*****

```

Note that each possible rectangle appears exactly once.

The rectangles may appear in any order, orientation or position, but no two rectangles may overlap or touch, even at the corners. The following is also valid:

```
********************

            ****
**********  ****
**********  ****
            ****
            ****

```

# Scoring

The bounding-box area (BBA) of an output is the area of the minimum rectangle enclosing all of the rectangles. In the first example output, the size is 20×9, so the BBA is 180. In the second example output, the size is 20×7, so the BBA is just 140.

Find the BBA of the output when the the input is 60, 111, 230, 400, and 480, and add them up. Multiply this sum by the size of your code in bytes. The result is your score; lowest score wins.

# Rules

* The program (or function) must produce valid output for any positive integer below 1000.
* The output must contain just asterisks (`*`), spaces (), and newlines.
* There can be any amount of space between the rectangles, but this counts towards the BBA.
* Leading or trailing lines or columns, if they have just spaces, do not count towards the BBA.

# Answer
# Ruby, 228 bytes * 21895 =4992060

```
->n{a=(0..n*2).map{$b=' '*n}
g=0
m=n*2
(n**0.5).to_i.downto(1){|i|n%i<1&&(m=[m,n+h=n/i].min
g+=h+1
g<m+2?(a[g-h-1,1]=(1..h).map{?**i+$b}):(x=(m-h..m).map{|j|r=a[j].rindex(?*);r ?r:0}.max
(m-h+1..m).each{|j|a[j][x+2]=?**i}))}
a}

```

Several changes from ungolfed code. Biggest one is change of meaning of variable `m` from the height of the squarest rectangle, to the height of the squarest rectangle plus `n`.

Trivially, `*40` has been changed to `*n` which means a lot of unnecessary whitespace at the right for large `n`; and `-2` is changed to `0` which means rectangles plotted across the bottom always miss the first two columns (this results in poorer packing for numbers whose only factorization is `(n/2)*2`)

**Explanation**

I finally found time to get back to this.

For a given `n` the smallest field must have enough space for both the longest rectangle `1*n` and the squarest rectangle `x*y`. It should be apparent that the best layout can be achieved if both rectangles have their long sides oriented in the same direction.

Ignoring the requirement for whitespace between the rectangles, we find that the total area is either `(n+y)*x = (n+n/x)*x` or `n*(x+1)`. Either way, this evaluates to `n*x + n`. Including the whitespace, we have to include an extra `x` if we place the rectangles end to end, or `n` if we place the rectangles side by side. The former is therefore preferable.

This gives the following lowerbounds `(n+y+1)*x` for the field area:

```
n     area
60    71*6=426
111  149*3=447
230  254*10=2540
400  421*20=8240
480  505*20=10100

```

This suggests the following algorithm:

```
Find the value (n+y+1) which shall be the field height
Iterate from the squarest rectangle to the longest one
  While there is space in the field height, draw each rectangle, one below the other, lined up on the left border.
  When there is no more space in the field height, draw the remaining rectangles, one beside the other, along the bottom border, taking care not to overlap any of the rectangles above.
  (Expand the field rightwards in the rare cases where this is necessary.)

```

It is actually possible to get all the rectangles for the required test cases within the above mentioned lower bounds, with the exception of 60, which gives the following 71\*8=568 output. This can be improved slightly to 60\*9=540 by moving the two thinnest rectangles right one square and then up, but the saving is minimal, so it's probably not worth any extra code.

```
10
12
15
20
30
60
******
******
******
******
******
******
******
******
******
******

*****  *
*****  *
*****  *
*****  *
*****  *
*****  *
*****  *
*****  *
*****  *
*****  *
*****  *
*****  *
       *
****   *
****   *
****   *
****   *
****   *
****   *
****   *
****   *
****   *
****   *
****   *
****   *
****   *
****   *
****   *
       *
***    *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
    ** *
    ** *
    ** *
    ** *
    ** *
    ** *
    ** *
    ** *
    ** *
    ** *
    ** *

```

This gives a total area of 21895.

**Ungolfed code**

```
f=->n{
  a=(0..n*2).map{' '*40}                                      #Fill an array with strings of 40 spaces
  g=0                                                         #Total height of all rectangles
  m=n                                                         #Height of squarest rectangle (first guess is n)
  (n**0.5).to_i.downto(1){|i|n%i<1&&(puts n/i                 #iterate through widths. Valid ones have n%i=0. Puts outputs heights for debugging.
    m=[m,h=n/i].min                                           #Calculate height of rectangle. On first calculation, m will be set to height of squarest rectangle.
    g+=h+1                                                    #Increment g
    g<n+m+2?                                                  #if the rectangle will fit beneath the last one, against the left margin
      (a[g-h-1,1]=(1..h).map{'*'*i+' '*40})                      #fill the region of the array with stars
    :                                                         #else
      (x=(n+m-h..n+m).map{|j|r=a[j].rindex('* ');r ?r:-2}.max    #find the first clear column
      (n+m-h+1..n+m).each{|j|a[j][x+2]='*'*i}                    #and plot the rectangle along the bottom margin
    )
  )}
a}                                                            #return the array

puts f[gets.to_i]

```
> 3 votes

# Answer
# CJam, 90385 * 31 bytes = 2801935

```
q~:FmQ,:){F\%!},{F\/F'**/N*NN}/

```

Test it here. Use this script to calculate the BBAs.

This is just the naive solution to get things started.
> 2 votes

# Answer
# Ruby, 56 bytes

90385\*56=5061560 assuming output the same as Martin's (I believe it is.)

```
->n{1.upto(n){|i|i*i<=n&&n%i==0&&puts([?**(n/i)]*i,'')}}

```

---

Here's another useful function, in a useful test program

```
f=->n{1.upto(n){|i|i*i<=n&&n%i==0&&print(n/i,"*",i,"\n")};puts}

f[60];f[111];f[230];f[400];f[480]

```

Which gives the following output, for reference:

```
60*1
30*2
20*3
15*4
12*5
10*6

111*1
37*3

230*1
115*2
46*5
23*10

400*1
200*2
100*4
80*5
50*8
40*10
25*16
20*20

480*1
240*2
160*3
120*4
96*5
80*6
60*8
48*10
40*12
32*15
30*16
24*20

```
> 1 votes

---
Tags: code-challenge, ascii-art
---


title: Convert Valve KV into JSON

text:
# Question
Title: Convert Valve KV into JSON
Valve's KV file format is as follows (in pseudo-EBNF):

```
<pair> ::= <text> <value>
<value> ::= <text> | <block>
<text> ::= "\"" <char>* "\""
<block> ::= "{" <pair>* "}"

```

The parsing starts on `<pair>` state. Whitespace is allowed anywhere, but is only required between two consecutive `<text>` tokens (`"a""b"` is invalid, but `"a" "b"` is valid, and so is `"a"{}`).

And since I'm lazy, `<char>` is any character, except `"`, unless preceded by `\`.

You can also see KV as JSON without commas and colons, and with only strings and objects as possible types.

Your task is to write a program or function that converts a input string (stdin, file or argument) in KV to a output string in JSON. You can output anywhere (stdout, file or return value), as long as it's a valid json string.

It isn't necessary to preserve whitespace in the output, as long as quoted text doesn't change.

Standard loopholes apply, of course.

## Bonus

You get a **-20** byte bonus if the output is pretty-printed, regardless of input. Pretty printed means indenting each level of blocks with 4 spaces, separating colons from values by 1 space and have one pair per line. Closing braces should stand on their own line.

## Test cases

Input:

```
"foo" {
    "bar" "baz"
    "oof" {
        "rab" "zab"
    }
}

```

Output:

```
{
    "foo": {
        "bar": "baz",
        "oof": {
            "rab": "zab"
        }
    }
}

```

Input:

```
"obj" {
    "emptyo" {}
    "troll" "}{"
}

```

Output:

```
{
    "obj": {
        "emptyo": {},
        "troll": "}{"
    }
}

```

Input:

```
"newline" "
"

```

Output:

```
{
    "newline": "\n"
}

```

Input:

```
"key
with_newline" {
    "\"escaped\"quotes" "escaped_end\""
}

```

Output:

```
{
    "key\nwith_newline": {
        "\"escaped\"quotes": "escaped_end\""
    }
}

```

# Answer
# CJam, ~~57~~ 54 bytes

```
{[~]2/{`_'{#{1>W<"\u%04x"fe%s`}{~J}?}f%':f*',*{}s\*}:J

```

This is a named function that pops a VDF string from the stack and pushes a JSON string in return.

CJam has no JSON built-ins, so the bonus won't be worth it. Since conditionally escaping some characters would be a pain for the same reason, I decided to escape *everything*.

The result isn't pretty, but it's valid JSON. Try it online in the CJam interpreter.
> 1 votes

---
Tags: code-golf, json
---


title: A flat guessing game

text:
# Question
Title: A flat guessing game
There is a game I like to play. It happens on a grid of finite size (but it's wrapped, like a sphere). On that grid, a random (integer-only) point is selected. Then, I, the user, am prompted for a coordinate input. If my input matches the random point exactly, I am told that I have won. Otherwise, I am told the point-wise distance between my input and the random point. For example, if I guessed `(2,2)` and the random point was at `(4,3)`, then the distance would be `sqrt[(3-2)^2 + (4-2)^2] = sqrt[5]`.

The game continues until the player arrives at the correct location of the point.

---

**Objective** Create a functional version of the game described above. You must create a full program to do so. Here's what your program should do:

1. Request two inputs: the height and the width of the board. The origin is at the top-left of the board. These inputs will not exceed `1024`.
2. Select a random point on that board; this will be the point to be guessed.
3. Accept input simulating a turn. The input will be either a space-separated pair of integers or two separate integer inputs. In response to this input, the program will do one of two things:
1. If the input matches the random point selected, output a message signalling the user's victory. I would suggest "You won!".
    2. Otherwise, output the distance between the user's input point and the random point. In either case, you must increment the turn counter.
4. Once the user has achieved victory, display the number of turns the user took. The program then exits.

## Bonuses

Bonuses are applied in the order that they appear in this list

* -150 bytes if your program takes an input integer `D` that describes the dimension in which the game takes place. E.g., if `D = 3`, then you create a random point of `3` integers, take `3` integer inputs, and output the distance between those points.
* -50% (or +50% if `score < 0`)if you provide a graphical representation of the board (ASCII or Picture) that shows where the user has previously guessed on the grid of given dimensions and the turn counter. (If you go for the first bonus, then this bonus only applies to the `2D` and `1D` modes. If you add a 3D graphical output, you get an additional -50%.)
* -60 bytes if you can provide a gamemode (selected by an input in the beginning; that is, when given `0`, perform the regular gamemode; when given `1`, perform this gamemode) in which the point moves 1 unit in a random orthogonal direction per turn

# More on wrapping

Wrapping occurs only when, in the third bonus, the moving point moves across any of the boundaries; in this case, the moving point is warped to the respective point, like so:

```
...              ...
..R (move right) R..
...              ...

```

This wrapping behaviour does not effect the user's guess, asides from the fact that point has changed direction.

---

# Leaderboard

The Stack Snippet at the bottom of this post generates the catalogue from the answers a) as a list of shortest solution per language and b) as an overall leaderboard.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

```
# Language Name, N bytes

```

where `N` is the size of your submission. If you improve your score, you *can* keep old scores in the headline, by striking them through. For instance:

```
# Ruby, <s>104</s> <s>101</s> 96 bytes

```

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the *last* number in the header:

```
# Perl, 43 + 2 (-p flag) = 45 bytes

```

You can also make the language name a link which will then show up in the snippet:

```
# [><>](http://esolangs.org/wiki/Fish), 121 bytes

```

```
<style>body{text-align:left!important}#answer-list{padding:10px;width:290px;float:left}#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}</style><script src=https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js></script><link rel=stylesheet type=text/css href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"><div id=language-list><h2>Shortest Solution by Language</h2><table class=language-list><thead><tr><td>Language<td>User<td>Score<tbody id=languages></table></div><div id=answer-list><h2>Leaderboard</h2><table class=answer-list><thead><tr><td><td>Author<td>Language<td>Size<tbody id=answers></table></div><table style=display:none><tbody id=answer-template><tr><td>{{PLACE}}<td>{{NAME}}<td>{{LANGUAGE}}<td>{{SIZE}}<td><a href={{LINK}}>Link</a></table><table style=display:none><tbody id=language-template><tr><td>{{LANGUAGE}}<td>{{NAME}}<td>{{SIZE}}<td><a href={{LINK}}>Link</a></table><script>function answersUrl(e){return"//api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"//api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var a=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(a="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var r=a.match(SCORE_REG);r?e.push({user:getAuthorName(s),size:+r[2],language:r[1],link:s.share_link}):console.log(a)}),e.sort(function(e,s){var a=e.size,r=s.size;return a-r});var s={},a=1,r=null,n=1;e.forEach(function(e){e.size!=r&&(n=a),r=e.size,++a;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;o=jQuery("<a>"+o+"</a>").text(),s[o]=s[o]||{lang:e.language,lang_raw:o,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang_raw>s.lang_raw?1:e.lang_raw<s.lang_raw?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var QUESTION_ID=62598,ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",OVERRIDE_USER=8478,answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?([-\d]+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;</script>
```

# Answer
> 8 votes
# CJam, ~~-113~~ ~~-139~~ ~~-152~~ ~~-157~~ -159 bytes

```
l~]:B:mr{_ea:i~mr0a*W2mr#+*.+B:,.=_[l~].-:mh_p}g],(

```

The program is **51 bytes** long and qualifies for the **-150 bytes** and **-60 bytes** bonuses.

The game mode and number of dimensions are read as a command-line argument, the size in each dimension from STDIN. Since the victory message is arbitrary, the program will print `0.0` (distance to goal) to indicate that the game is over.

### Test runs

```
$ cjam game.cjam 0 3; echo
2 2 2
1 1 1
1.4142135623730951
1 1 0
1.7320508075688774
1 0 1
1.0
0 0 1
0.0
4
$ cjam game.cjam 1 3; echo
2 2 2
0 0 0
1.0
0 0 0
0.0
2

```

### How it works

```
l~]       e# Read a line from STDIN, evaluate it and collect the result.
:B        e# Save the resulting array in B. The result is [B1 ... Bd],
          e# where Bk is the board size in dimension k.
:mr       e# Pseudo-randomly select a non-negative integer below Bk,
          e# for each k between 1 and d.
{         e# Do:
  _       e#   Copy the item on the stack. The original becomes a dummy value
          e#   that will be used to count the number of turns.
  ea      e#   Push the array of command-line arguments.
  :i~     e#   Cast each to integer and dump them on the stack.
          e#   This pushes m (game mode) and d (number of dimensions).
  mr      e#   Pseudo-randomly select a non-negative integer below d.
  0a*     e#   Push an array of that many zeroes.
  W2mr#   e#   Elevate -1 to 0 or 1 (selected pseudo-randomly).
  +       e#   Append the result (1 or -1) to the array of zeroes.
  *       e#   Repeat the array m times.
  .+      e#   Perform vectorized addition to move the point.
  B:,.=   e#   Take the k-th coordinate modulo Bk.
  _[l~]   e#   Push a copy and an evaluated line from STDIN.
  .-:mh   e#   Compute their Euclidean distance.
  _p      e#   Print a copy.
}g        e# While the distance is non-zero, repeat the loop.
],(       e# Get the size of the stack and subtract 1.
          e# This pushes the number of turns.

```

# Answer
> 7 votes
# Pyth, 91 (-150 -60) = -119

```
VvwaYOvw;JY#IqQ1=dOlY XYd@S[0 @Jd +@Yd?O2_1 1)1)=T[)VYaT^-Nvw2)=ZhZ=b@sT2Iqb0Bb;p"Won in "Z

```

Old solution: (54-150=-96)

```
JYVQaYOvw;#=J[)VYaJ^-Nvw2)=ZhZ=b@sJ2Iqb0Bb;p"Won in "Z

```

All input takes place on a new line.

* First integer represents the game mode (**either `1` or `0`**)
* ~~First~~ Second integer `D` represents the dimensions of play.
* Next `D` inputs represent the field size
* Every `D` inputs from this point on are guesses

Sample play (hints do not appear in the actual program):

```
  #Hint: Gamemode (1 or 0)
1
  #Hint: Dimensions
3
  #Hint: X-size
4
  #Hint: Y-size
4
  #Hint: Z-size
4
  #Hint: Guesses
  #Hint:[3, 2, 1]
3
2
2
1.0
  #Hint:[3, 2, 1]
3
2
1
1.0
  #Hint:[2, 2, 1]
2
2
1
1.0
  #Hint:[3, 2, 1]
3
2
1
Won in 4

```

# Answer
> 3 votes
## Python 2, 210 - 150 = 60

```
from random import*
q,r,o=map,raw_input,int
a=q(randrange,q(o,r().split(' ')))
m=q(o,r().split(' '))
t=1
while m!=a:print sum([(c-d)**2for c,d in zip(m,a)])**.5;m=q(o,r().split(' '));t+=1
print'You won in %d'%t

```

First challenge only so far. Try it online

# Answer
> 3 votes
## Pip, ~~43~~ 42 bytes - 150 = -108

Takes the board dimensions as command-line arguments (with D implied from the number of args). Takes guesses as space-separated numbers on stdin.

```
YRR_MgWd:++i&RT$+(y-(q^s))**2Pd"Won in ".i

```

This code takes heavy advantage of Pip's array-programming features. The array of cmdline args is stored in `g`. We generate the point to be guessed by mapping the randrange operator `RR` over `g`, and yank the resulting list into the `y` variable. Then comes the main while loop, where the condition is as follows:

```
d:++i&RT$+(y-(q^s))**2

  ++i&                  Increment i, the guess counter; the result is always > 0, so the
                          short-circuiting & operator evaluates the next expression:
              q         Read a line from stdin
               ^s       Split on spaces
           y-(   )      Subtract from our chosen point itemwise
          (       )**2  Square, itemwise
        $+              Fold on +, summing the list of squares
      RT                Square root
d:                      Assign this distance to d

```

If the distance was nonzero, the inside of the loop prints it. If it was zero, we've hit the target point; the loop halts, and the program outputs the win message and number of turns.

Example run:

```
C:\Users\dlosc> pip.py -f guessing.pip 10 5 6 4
5 2 3 2
3.1622776601683795
6 2 3 2
4.123105625617661
3 2 3 2
1.4142135623730951
3 1 3 2
2.23606797749979
3 2 2 2
1.7320508075688772
2 2 3 2
1
2 2 3 1
1.4142135623730951
2 3 3 2
Won in 8

```

# Answer
> 2 votes
## R, 134 - 150 = -16 bytes

```
function(...){G=sapply(list(...),sample,1)
C=0
repeat{g=scan()
C=C+1
if(any(G!=g))cat(sqrt(sum((G-g)^2)))else{cat("Won in",C);break}}}

```

# Answer
> 2 votes
## Haskell, 240 - 150 = 90

```
import System.Random
r x=randomRIO(0,x-1)
m=map read.words
g=getLine
main=do g;(fmap m g::IO[Int])>>=mapM r>>=b 1
b c v=do i<-fmap(sqrt.fromIntegral.sum.map(^2).zipWith(-)v.m)g;if i==0 then putStrLn$"Won in "++show c else do print i;b(c+1)v

```

# Answer
> 1 votes
# Dyalog APL, ~~77~~ 71 - 210 = -139

```
S F M
P←?S
{P←S|P+(?D)⌽D↑M×¯1 1[?2]
C+←1
P≢G←⎕:0⊣⎕←.5*⍨+/2*⍨P-G
C}⍣≢C←0

```

Ok:

Note that this runs in index origin 0 (`⎕IO←0`) which is default in many APLs.
Takes boolean mode as right argument (`M`), and dimension sizes as left argument (`S`).
Number of dimensions is `D`, which must be set (e.g. `D←3`) before calling, as per OP).
`P←?S` goal gets random point in range 1 though each of the dimension bounds
`{``}⍣≢C←0` repeat the function until the result is different from `C`, which initially gets `0`
`?2` random number 0 or 1
`¯1 1[``]` index from list of two numbers
multiply by mode; makes `0` if mode is `0`
`D↑` pad with `0`s to match number of dimensions
`(?D)⌽` rotate list randomly (0 through number of dimensions-1)
`P+` adjust current goal
`S|` world-size modulus
`P←` save new goal point
`C+←1` increment counter
`P≢G←⎕:` input guess, and if it is different from goal point then...
`P-G` distances in each dimension
`2*⍨` squared
`+/` sum them
`.5*⍨` square-root
`⎕←` print that
`0⊣` return 0 (i.e identical to initial value, so repeat)
`C` ... else, return the number of guesses (which, being different from 0, stops the looping and returns the last value)

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


# Question
Title: Who has the most stars in The Nineteenth Byte?
Note: this challenge involves downloading and sifting through HTML webpages. If your language cannot handle this you might not want to participate in this challenge.

# Introduction

There are always discussions over in The Nineteenth Byte Chat about who leads the starboard. So, lets help everyone out and count the total amount of stars per user in the chat.

# Challenge

Given an positive integer `N` which is greater than zero, calculate the leader(s) of the starboard of the last `N` starred messages in the chat. These messages can be viewed here. Hint: each page has 50 starred messages. Output will be a list of the top 5 users *by amount of starred messages*. A bonus of **-15%** off your byte count will be granted if you can display the usernames of those users, but no penalty will be given if you simply display the user id numbers. **Please note that there is profanity in some of the starred messages. If you are sensitive to this type of language, view the page with caution.**

Examples (Image is current starboard as of writing this challenge):

* (RED) Input: `5` Output (With bonus): `[Geobits Sp3000 PhiNotPi Seadrus]`
* (BLUE) Input: `10` Output (Without bonus): `[51024 17335 24697 116494 129255]`
* (GREEN) Input: `14` Output (Without bonus): `[51024 116494 141697 17335 24697]`

**Extra stuff:**

Ties in the top 5 will be sorted by lowest to highest *user id* number. If there is less than five users, just output the leaderboard with *empty slots* at the end. Input and output can be in any format. Output does not need to be capitalized. If input is greater than `50`, you must still count the messages on page 2, page 3, etc. You may assume that input will always be under `2^31`, and will also not be so large that it 1) is larger than the amount of starred messages that there is and 2) will not crash the program (by making arrays to big, running out of memory, etc.).

This is , shortest code in bytes wins!

---

## Leaderboards

Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

```
## Language Name, N bytes

```

where `N` is the size of your submission. If you improve your score, you *can* keep old scores in the headline, by striking them through. For instance:

```
## Ruby, <s>104</s> <s>101</s> 96 bytes

```

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the *last* number in the header:

```
## Perl, 43 + 2 (-p flag) = 45 bytes

```

You can also make the language name a link which will then show up in the leaderboard snippet:

```
## [><>](http://esolangs.org/wiki/Fish), 121 bytes

```

---

```
var QUESTION_ID=62182,OVERRIDE_USER=36670;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"http://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
```

```
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>
```

# Answer
* I' m so sorry for being slow but reading starred messages while coding was so hilarious and dilatory, this could have kept my mood up for a month.

---

* **Edit:** Yes, I found it, the tie and duplicate ids issues are both fixed up harmonically. The trick is that the old code sorts the user-ids by descending number of stars, so I twisted some lines of my program in a way that it sorts users according to 99-n°\_stars; since 99 is way bigger than the top hit star-cap (hopefully - I assumed), sorting the result by increasing number of stars kills both birds with one stone, descending stars with ascendant user-ids.

---

## BrownRecluse, ~~without bonus = 536~~ with bonus = 551-15% = 468 b

```
U=New(URL);P=New(Parser);L=New(Stack);t=New(Stack);v='http://chat.stackexchange.com/rooms/info/240/the-nineteenth-byte?tab=stars&page=';j=input();a=0;for i=1to j\50+1do begin U.Location=v+i;U.get;P.Parse(U.Data);x=New(RegEx);x.Data=U.Data;x.Mask='users/(\d*)/(\S*)".*?"times">(\d*?)<';while(x.Match)and(a<j)do begin L.Push(Format('%3d%9s%s',[99-x.Value[3],x.Value[1],x.Value[2]]));a=a+1;end;end;L.sort;i=0;for each L as y do if(not y.empty)and(not t.find(y.right(y.Length-12)))and(i<5)then begin y.delete(1,12);i=i+1;t.push(y);end;output(t.join(' '));

```

## Input

```
60

```

## Output

```
mego rainbolt alex-a lembik v

```

## Input

```
90

```

## Output

```
aditsu mego rainbolt alex-a lembik

```

## NOTES

* This program (including bonus) doesnt support unicode characters - I'm sorry Vɪʜᴀɴ!
* This program works based on the standard feature that each page contains almost 50 starred messages by default.
* See clearly that 60 and 90 messages are contained within the first two pages, whilst the outputs differ.
* This is the download page of this programming language in case it is not in your possession
* In case needed, this is the bonusless program of **485 b**

```
U=New(URL);P=New(Parser);L=New(Stack);t=New(Stack);v='http://chat.stackexchange.com/rooms/info/240/the-nineteenth-byte?tab=stars&page=';j=input();a=0;for i=1to j\50+1do begin U.Location=v+i;U.get;P.Parse(U.Data);x=New(RegEx);x.Data=U.Data;x.Mask='users/(\d*)/(\S*)".*?"times">(\d*?)<';while(x.Match)and(a<j)do begin L.Push(Format('%3d%9s',[99-x.Value[3],x.Value[1]]));a=a+1;end;end;L.sort;i=0;for each L as y do if(not y.empty)and(not t.find(y.right(y.Length-3)))and(i<5)then begin y.delete(1,3);i=i+1;t.push(y);end;output(t.join(' '));

```

***Input***

```
60

```

***Output***

```
169713    107051    141888     94625    116494

```

***Input***

```
90

```

***Output***

```
50454    169713    107051    141888     94625

```

> If there was incoherence between results my code isn't taking the blame!
> 11 votes

---
Tags: code-golf, parsing, internet
---