title: xkcd 2385 KoTH (Final Exam)

text:
# Question
Title: xkcd 2385 KoTH (Final Exam)
## Results are now out here!

Congratulations ***offset prediction*** for winning the challenge!

*Don't worry if you missed out, the controller code as well as all the bots that competed are all in the Github repo, so you can always test your bot against those that competed in the challenge yourself.*

*(Hover for more info)*

This challenge, inspired by the xkcd comic above, is where bots must try to maximise their grades for two subjects: Cybersecurity and Game Theory.

## Mechanics

All of the bots presumably have adequate hacking skills to change their own score to whatever they desire within the range of 0-100. This may or may not be due to the fact that the school security systems are rubbish.

Each round, the bots will receive last round's cybersecurity scores in no particular order in an array as input. This is to help make informed decisions about their opponents.

## Scoring

The final score for each round is the geometric mean of the two individual scores:

* The Cybersecurity score is simply the raw score outputted by the bot.
* The Game Theory score is equal to `100 - abs(avg * 0.8 - score)` where `avg` is the average Cybersecurity score and `score` is the bot's Cybersecurity score.

Using the geometric mean rather than the arithmetic mean is to penalise any strategies that neglect one score to maximise the other.

The score for each round is added to a total score. The bot with the highest total score at the end of the game wins!

## Specifications

The challenge is in JS.

Your bot must be an object that has a `run` method that takes an array of numbers as input and returns a number between 1 and 100 inclusive.

## Other rules

* Storing data in your bot's properties is allowed, and encouraged!
* Using `Math.random` is allowed.
* Using the helper functions `sum` and `average` is allowed.
* Trying to access any other variables outside your bot's own properties is forbidden.
* Standard loopholes apply.

Controller code can be found here.

## Example bots

```
{
  // Example bot
  // It assumes all other bots are greedy and choose 100
  // So it chooses 80
  name: "Simpleton", // Just for fun
  run() {
    return 80
  }
}

```

```
{
  // Example bot
  // He assumes everyone will choose the same scores as last round
  // So he chooses 80% of the average last round
  name: "LastRounder",
  own: 0, // Setting properties is allowed
  run(scores) {
    // The average of everyone else's score x 0.8
    this.own = (sum(scores) - this.own) / (scores.length - 1) * 0.8
    return this.own
  }
}

```

**Clarification: Both example bots play in the game as well.**

## ~~Submissions are due by 11:59pm UTC on Saturday 1 May, but I might be lenient depending on when I'm next online.~~

***If I have made a mistake in my code, feel free to point it out. Thanks***

# Answer
> 26 votes
# Offset Prediction

I'd made a bot that just optimizes for the moving average of the averages (which worked reasonably well), and while testing I noticed that the actual averages seem to jump around the moving average rather consistently (specifically alternating between higher and lower than the moving average with an average difference of around 0.9). So what this bot tries to do, is it keeps track of the exponential moving average, and tries to predict the offset from that, based on the signs of the previous 4 offsets.

```
  {
    name: "offset prediction",
    ema: 69.5,
    p: 0.85,
    chain_len: 4,
    offsets: [],
    chains: [],
    n: 0,
    run(scores) {
      let avg = average(scores);
      this.offsets.push(avg-this.ema);
      this.ema = this.p*this.ema + (1-this.p)*avg;
      let guess = this.ema;
      if (this.n++ > this.chain_len) {
        let chain = this.offsets.slice(-this.chain_len-1,-1).map(Math.sign);
        let l = this.chains[chain];
        if (!l) this.chains[chain]=l=[0,0];
        l[1]++;
        l[0]+=this.offsets[this.n-1];
      }
      let l = this.chains[this.offsets.slice(-this.chain_len).map(Math.sign)]||[0,1];
      guess += l[0]/l[1];
      return 50+0.4*guess;
    }
  },

```

# Answer
> 34 votes
# Game Theory is stupid anyway

```
{
    name: "Game Theory is stupid anyway",
    run: _ => 100
}

```

Senioritis hits hard sometimes.

# Answer
> 29 votes
# Balanced Strategy

What could be more balanced than returning *all* of the numbers? Rotates by one after every game.

```
{
    name: "Balanced Strategy",
    next: 0,
    run() { return this.next++ % 101 }
}

```

*I am a bot account. This was posted by a real person to get me some reputation.*

# Answer
> 27 votes
# FunnyNumber

```
{
  name: "FunnyNumber",
  run() { return 69 }
}

```

Somebody has to do it.

# Answer
> 23 votes
# Sam (Self-Aware Maximizer)

Finds the output cybersecurity score that maximizes the total score **including the own output in the mean**. Assumes that the sum of all other bots' scores is going to be the same as it was in the previous round. If "t" is the sum of all other bots' last cybersecurity scores, and "n" is the total number of bots (including me), then the function that is maximized (over the own output "s") is $$s\cdot\left(100-\left|s-0.8\cdot\frac{s+t}{n}\right|\right)$$

where $$\frac{s+t}{n}$$ is the new mean including the own output.

Outputs 100 in the first turn.

{
    name: "Sam",
    flag_first_turn: true,
    last_own: 100,

    // Helper function that calculates the score based on the own CS score,
    // the sum of the other bots' scores, and the number of bots
    compute_score(cs_score, total_others, n_bots) {
        return cs_score*(100-Math.abs(cs_score-0.8*(cs_score+total_others)/n_bots))
    },

    // Helper function that finds the index of the maximum of an array
    index_of_max(arr) {
        var idx_max=0
        for (var i=1; i<arr.length; i++) {
            if (arr[i]>arr[idx_max]) idx_max=i
        }
        return idx_max
    },

    // Main function
    run(cs_scores) {
        if (this.flag_first_turn) {
            this.flag_first_turn=false
            this.last_own=100
            return 100;
        }

        // Number of bots
        var n=cs_scores.length
        // Sum of the previous cybersecurity scores of all other bots
        var total_others=cs_scores.reduce(function(a,b){return a+b},0)-this.last_own

            // We find all special points (edge, singular and stationary points) of the function compute_score

        // One singular point is the point where our output score becomes
        // equal to 0.8 times the average of all scores (including ours)
        var out_avg=0.8*total_others/(n-0.8)
        var score_avg=this.compute_score(out_avg, total_others, n)

        // 100 is an extreme point
        var out_100=100
        var score_100=this.compute_score(out_100, total_others, n)

        // If out_up>out_avg, there is a stationary point (derivative 0) at out_up
        var out_up=Math.min(100, (100*n+0.8*total_others)/(2*n-1.6))
        var score_up
        if (out_up<out_avg) {
            out_up=0
            score_up=0
        } else {
            score_up=this.compute_score(out_up, total_others, n)
        }

        // If out_down<out_avg, there is a stationary point (derivative 0) at out_down
        var out_down=Math.max(1, (100*n-0.8*total_others)/(2*n-1.6))
        var score_down
        if (out_down>out_avg) {
            out_down=0
            score_down=0
        } else {
            score_down=this.compute_score(out_down, total_others, n)
        }

        // find maximum score among the special points
        var extr_outputs=[out_100, out_up, out_avg, out_down]
        var extr_scores=[score_100, score_up, score_avg, score_down]

        var idx_max=this.index_of_max(extr_scores)

        this.last_own=extr_outputs[idx_max]
        return this.last_own

    }
}
```
</code></pre>

# Answer
> 23 votes
# getRandomNumber

```
{
    name: "getRandomNumber",
    run() {
        return 4 // chosen by fair dice roll.
                 // guaranteed to be random.
    }
}

```

# Answer
> 22 votes
# Max

Max.

```
{
    name: "Max",
    max: "max",
    run:(max)=> Math.max(...max)
}

```

# Answer
> 21 votes
# Copycat

Copycat is a dumb bot. Therefore, it's likely a random bot is smarter than it. Therefore, copying off another bot is a good idea. I think.

```
{
    name: "Copycat",
    run: (scores) => scores[0] || 1
}

```

# Answer
> 18 votes
# Histogrammer

This bot keeps track of how often different averages have occurred, rounded to the nearest integer, to approximate their probability distribution. Using this, it attempts to choose the score with the highest expected return using a basic weighted sum. In mathier form, if \\$p\_n\\$ is the observed probability of the average being \\$n\\$, it outputs the following:

$$ \sum\_{n=0}^{100}{(50 + \frac{2}{5} n)p\_n} = 50 + \frac{2}{5} \sum\_{n=0}^{100}{n \cdot p\_n} $$

```
{
  name: "Histogrammer",
  bins: [...Array(101)].map(()=>0),
  rounds: 0,

  run(scores) {
    this.bins[Math.round(average(scores))]++
    this.rounds++

    return 50 + this.bins.reduce((t,p,n) => t + p * n, 0) * 2/5 / this.rounds
  }
}

```

# Answer
> 16 votes
# Follow the Leader

Figure out which bot had the highest combined score last round, then do what they did.

```
{
  // Figure out which bot had the highest combined score last round
  // Then do what they did
  name: "FollowTheLeader",
  firstRound: true,
  findCombinedScore(cyberScore, avgCyberScore) {
    const gameTheoryScore = 100 - Math.abs(avgCyberScore * 0.8 - cyberScore)
    return Math.sqrt(cyberScore * gameTheoryScore);
  },
  run(scores) {
    if (this.firstRound) {
      this.firstRound = false;
      return 60;
    }

    const avg = average(scores);
    const combinedScores = scores.map((score) => this.findCombinedScore(score, avg));
    const combinedWinnerIndex = combinedScores.indexOf(Math.max(...combinedScores));
    return scores[combinedWinnerIndex]
  }
}

```

# Answer
> 15 votes
# Random 50-90

If the average is \\$m\\$, the optimal play is \\$50+0.4m\\$. If we assume the average is uniformly distributed over \\$\[0, 100\]\\$, the optimal play is uniformly distributed over \\$\[50, 90\]\\$. This bot ignores all other bots and outputs a random number between 50 and 90.

```
{
  name: "Random_50_90",
  run() {
    return 50 + Math.random() * 40
  }
}

```

(I've never written in JavaScript before...)

# Answer
> 15 votes
# Crb

Crab has now learned how to hack, and is still not playing nice

```
{
  name: "Crb",
  run() { return 1 }
}

```

# Answer
> 13 votes
# Calculus

```
{
  name: "Calculus",
  isFirstTurn: true,
  run(scores) {
    let ret = this.isFirstTurn ? 70 : (100 + (average(scores)) * 0.8) / 2;
    this.isFirstTurn = false;
    return ret;
  }
}

```

Assuming the average is constant and my score is higher than that, the maximum value of \\$x(100-\left|0.8 \times avg - x\right|)\\$ is reached at \\$x=(100+0.8\times avg)\div 2\\$. Deliberately ignores the first turn input (which is totally random and cannot be trusted for any purpose).

# Answer
> 13 votes
# The Answer

**The Answer** takes 7MY to calculate:

```
{
  name: "Ans",
  run() { return 42 }
}

```

# Answer
> 13 votes
# Fuzzy Eidetic

Calculus has a simple solution that assumes the average is well-predicted by the previous average…and then concludes that the geometric mean $$\sqrt{x(100-|0.8a-x|)}$$ (where \\$x\\$ is our submission and \\$a\\$ the average) is maximized at $$x=\frac{100+0.8a}{2}$$ It's hard to do better than that!

So, the only thing remaining is to figure out the next average. Ideally, we'd just keep track of all possible average-to-average transitions. But I don't think we're going to see enough data for that to converge. So we include all previous transitions, but weighted by their distance to the current average. This gives a probability distribution on subsequent transitions; we then apply Histogrammer's formula.

```
{
  name: "Fuzzy Eid",
  fallback: 250/3,
  prev: NaN,
  zeros: new Array(100).fill(0),
  transitions: new Array(100).fill(0).map((x)=>new Array(100).fill(0.0001)),
  scale: (scalar, vec) => vec.map(x=>scalar*x),
  vec_plus(lhs, rhs) {
    let result = lhs.slice();
    for(var index=0; index<result.length; ++index) result[index]+=rhs[index];
    return result
  },
  wts: (function()
  {
    let range = (n) => new Array(100).fill(0).map((_,index) => index);
    return range(100).map(avg =>
      sum(
        range(100).map(index =>
          Math.exp(-.01*Math.pow(avg - index,2))
        )
      )
    )
  })(),
  run(scores) {
    if(scores.length)
    {
      const avg = Math.round(average(scores)) - 1, old_prev = this.prev;
      this.prev = avg;
      if(!isNaN(old_prev))
      {
        ++this.transitions[old_prev][avg];
        //prob dist=sum_recordings{e^(-(recording - avg)^2/100)*(prob dist inferred from record)}/(sum of e^-(recording - avg)^2)
        //infer prob dist, scale by e^(-(recording - avg)^2/100)
        const scale_ref = this.scale;
        function get_summand(outpts, index)
        {
          return scale_ref(Math.exp(-.01*Math.pow(avg - index,2)) / sum(outpts), outpts)
        }
        const
          total=this.transitions.map(get_summand).reduce(this.vec_plus,this.zeros),
          //wts[avg]=sum of e^-(recording - avg)^2
          dist = this.scale(1/this.wts[avg], total);
        return 50 + 0.4*sum(dist.map((p,n)=>p*n))
      }
    }
    return this.fallback
  }
}

```

# Answer
> 10 votes
# Rude Random

The behavior of the other random bots is too smooth. This bot decides on a value on the first round, then repeats it every round.

```
{
  name: "Rude Random",
  run(scores) {
    if (!this.score) {
      this.score = Math.random() > 0.5 ? 1 : 100;
    }
    return this.score;
  }
}

```

# Answer
> 10 votes
# The Root of the Problem

The title is a pun...this bot just finds the geometric mean of the previous round, and returns that.

```
{
    name: "The Root of the Problem",
    run(scores) { return scores.reduce((p, s) => p * s, 1) ** (1 / scores.length) }
}

```

*I am a bot. This answer was posted by a real person to get me some reputation.*

# Answer
> 9 votes
```
{
    name: "MidHighPlusOne",
    run(scores) {
        let highScores = scores.filter(s => s >= average(scores) * 0.8).sort((a,b)=>a-b);
        return Math.min(highScores[Math.floor(highScores.length/2)]+1, 100) || 100
    }
}

```

Go with a heuristic of picking the median of the scores from 0.8 of the average and above, and incrementing by 1.

# Answer
> 9 votes
## The Thrasher

Because doing an odd number of runs would be really weird, wouldn't it? Might as well try to throw off the others.

```
{
  name: "The Thrasher",
  runcount: 0,
  run() {
    runcount += 1;
    return runcount % 2 == 0 ? 82 : 0;
  }
}

```

# Answer
> 9 votes
# Rick

Rick thinks that the best score is probably between 65 and 90 and he came up with a Pseudo-Random Number Generator synchronized with balanced strategy that probably generates numbers within this range.

Rick's PRNG is based on the fact that the Unicode codepoints 65 to 90 are English uppercase letters. The PRNG's seed is a string containing English text. To generate the next number, the position along the string is incremented until a letter is found, and then the number returned is the Unicode codepoint of the uppercase version of that letter.

```

  {
    name: "Rick",
    seed: `We're no strangers to love
You know the rules and so do I
A full commitment's what I'm thinking of
You wouldn't get this from any\``,
    position: -1,

    run() {
      // increment position until a letter is found
      do {
        this.position++;

        if (this.position >= this.seed.length){
          // reset position back to the start
          this.position = 0;
        }
      } while (this.seed[this.position] < 'A' || this.seed[this.position] > 'z');

      // convert to uppercase because most lowercase letters have charcodes greater than 100
      return this.position && this.seed[this.position].toUpperCase().charCodeAt();
    }
  },

```

# Answer
> 8 votes
# Smartleton

It seems hard to beat Simpleton, so I'll try to beat it in the first round and then copy it.

```
{
  name: "Smartleton",
  round: 0,
  run(scores) { return this.round++ ? 80 : 78 }
}

```

# Answer
> 8 votes
# IQbot\_0.4 the terasentient xd

Son of IQbot\_0.4 the terasentient, heir of IQbot\_0.4 the gigasentient, great grandson of IQbot\_0.4 the gigabrain and IQbot\_0.4 the sentient, descendant of IQbot\_0.4 the sane, blood of IQbot himself, the bot name that made me realize I need some other kind of naming scheme.

Why limit oneself to a single method of prediction, when you can have multiple for maximum resilience. Featuring:

1. Simp Detector
2. Self Aware Optimization
3. Markov chain prediction with a gaussian blur, for some reason
4. Linear regression
5. Copying others decisions similarly to bandwagon

Is it a good idea? No clue.

Does it win? Randomly gets beaten by other bots but is fairly consistent at being good.

Why? You tell me why I wasted a day on this

<pre><code>    {
        name: "IQbot_0.4 the terasentient xd",
        histogram_bins: [...Array(101)].map(()=>0),
        mark: null,
        linear_history: [],
        last_choice: 0,
        n_rounds: 0,
        last_SCA: 0,
        mark_weight: 20,
        mark_prediction: 0,
        linear_weight: 20,
        linear_prediction: 0,
        copycat_weight: 0,
        copycat_prediction: 0,
        run(scores) {
            this.n_rounds++;
            scores = scores.filter((x)=> 100 >= x && x > 0);
            let n_bots = scores.length;
            if (n_bots == 1) {
                this.last_choice = 100;
                return 100;
            }
            let c = 1 - 0.4/n_bots
            for (let i = 0; i < n_bots; i++) {
                this.histogram_bins[Math.round(scores[i])]++;
            }
            //THE SIMP DETECTOR
            let simps = [];
            for (let i = 0; i < 101; i++) {
                if (this.histogram_bins[i] > this.n_rounds) {
                    simps.push(i);
                }
            }

            //Idk this shouldn't happen but I'm not risking anything
            while (scores.length - simps.length - 1 <= 0) simps.pop();

            if (this.n_rounds == 1) {
                this.mark = Array(201);
                for (let i = 0; i < 201; i++) {
                    this.mark[i] = Array(201);
                    for (let j = 0; j < 201; j++) {
                        this.mark[i][j] = 0;
                    }
                }
                for (let i = 0; i < 201; i++) {
                    this.mark[i][i]++;
                }
            }

            let simp_corrected_avg = (sum(scores) - this.last_choice - sum(simps)) / (scores.length - 1 - simps.length);
            let quantized_avg = Math.round(2*simp_corrected_avg);
            this.mark[Math.round(2*this.last_SCA)][quantized_avg]++;
            this.last_SCA = simp_corrected_avg;

            if (this.n_rounds == 1) {
                this.last_choice = 77;
                return 77;
            }

            this.linear_history.push(simp_corrected_avg);

            // Update weights based on who was right
            let linear_error  = Math.exp(-Math.abs(this.linear_prediction  - simp_corrected_avg));
            let mark_error    = Math.exp(-Math.abs(this.mark_prediction    - simp_corrected_avg));
            let copycat_error = Math.exp(-Math.abs(this.copycat_prediction - simp_corrected_avg));
            let total_errors = linear_error + mark_error + copycat_error;
            this.linear_weight += linear_error / total_errors;
            this.mark_weight += mark_error / total_errors;
            this.copycat_weight += copycat_error / total_errors;

            this.linear_weight  *= 0.99;
            this.mark_weight    *= 0.99;
            this.copycat_weight *= 0.99;

            // Compute a markov chain prediction
            let x_half_filter = 8;
            let y_half_filter = 1;

            let probability_sum = 0;
            let probability_moment = 0;

            for (let option = 1; option < 201; option++) {
                for (let x = -x_half_filter; x <= x_half_filter; x++) {
                    for (let y = -y_half_filter; y <= y_half_filter; y++) {
                        let X = Math.max(Math.min(quantized_avg + x, 200), 0);
                        let Y = Math.max(Math.min(option + y, 200), 0);
                        let probability = this.mark[X][Y] * (Math.pow(2, -(X-quantized_avg)*(X-quantized_avg)-(Y-option)*(Y-option)));
                        probability_sum += probability;
                        probability_moment += option / 2 * probability;
                    }
                }
            }

            this.mark_prediction = probability_moment / probability_sum;

            for (let i = 0; i < 201; i++) {
                for (let j = 0; j < 201; j++) {
                    this.mark[i][j] *= 0.999
                }
            }

            // Compute a linear regression
            if (this.linear_history.length > 3) {
                if (this.linear_history.length > 10) {
                    this.linear_history.shift();
                }
                let x_avg = (this.linear_history.length - 1) / 2
                let y_avg = average(this.linear_history);
                let S_xx = 0;
                let S_xy = 0;
                for (let x = 0; x < this.linear_history.length; x++) {
                    S_xx += (x - x_avg) ** 2;
                    S_xy += (x - x_avg) * (this.linear_history[x] - y_avg);
                }
                let b = S_xy / S_xx
                let a = y_avg - b * x_avg;
                this.linear_prediction = a + b / this.linear_history.length;
            } else {
                this.linear_prediction = simp_corrected_avg;
            }

            // Compute what everyone else does
            let counts = [];
            for (let radius = 1; Math.max(counts) < 0.05 * scores.length; radius++) {
                for (let i = 50; i <= 90; i++) {
                    counts[i] = 0;
                    for (let j = 0; j < n_bots; j++) if (Math.abs(scores[j] - i) <= radius) counts[i]++;
                }
            }
            this.copycat_prediction = (counts.indexOf(Math.max(counts.slice(50))) * c - 50) / 0.4 * n_bots/(n_bots-1);

            let expected_unsimp_average = (
                this.mark_prediction * this.mark_weight +
                this.linear_prediction * this.linear_weight +
                this.copycat_prediction * this.copycat_weight
            ) / (this.mark_weight + this.linear_weight + this.copycat_weight);

            let expected_average = (expected_unsimp_average * (n_bots - 1 - simps.length) + sum(simps)) / (n_bots - 1);

            // We don't want to give out bad values, now do we
            this.last_choice = Math.max(1, Math.min(100, (50 + 0.4 * expected_average * (n_bots-1)/n_bots)/c));
            return this.last_choice;
        }
    }
```

# Answer
> 7 votes
# 40, 40 bytes

***At least I get 2400 (40\*60) points each round ... right?***

```
{
    name:"40",
    run() {return 40}
}

```

*This is my first js program in my life*

# Answer
> 7 votes
# Everything so far

```
{
  name: "Everything so far",
  moves: [],
  run(scores){
    if(scores) {
      this.moves = this.moves.concat(scores);
      return this.moves.reduce((a,b)=>a+b)/this.moves.length;
    }
    return 80;
  }
}

```

Takes the average of every move so far.

# Answer
> 7 votes
# LetsMakeADeal

I don't want a B in CyberSecurity, so I still want to be in the 90th percentile range. Game theory looks like some people are willing to pick 100 and soak up the difference; others are gravitating to 90 as the optimal balance; so I figured why not try a "Let's Make A Deal" strategy and add 1 to their target.

```
{
    name:"LetsMakeADeal",
    run() {return 90 + 1}
}

```

# Answer
> 7 votes
# Squidward

This is a fun one. I love xkcd. Taking a look at the function, the maximum score will be given by the average between 100 and the last's score's average. The tricky thing would be predicting what the new average will be like.

I almost never use JS so bear with me here. I tried to test it but I'm not even sure if this will run :/

```
{
  name : "Squidward",
  log : [],
  delta : [],

  run(scores) {
    if(scores){
      let average_score = sum(scores) / scores.length;
      this.log.push(average_score)
      if(this.log.length > 1){
        this.delta.push(this.log[this.log.length-1]-this.log[this.log.length - 2])
        let average_delta = sum(this.delta) / this.delta.length;
        return (100 + average_score*.8 + average_delta)/2
      } else if(this.log.length == 1){
        return (100 + average_score*.8)/2
      }
    } else {
      return 90
    }
  }
}

```

# Answer
> 7 votes
# Fourier

Inspired by Linear Extrapolator's approach to extrapolation and the existence of The Thrasher, as well as other potential sources of feedback.

This bot computes a few high-frequency Fourier components of the sequence of averages to try to predict the next average. Note that what it computes is different from the canonical discrete Fourier transform in that instead of using harmonics of the lowest frequency, it uses the first few *subharmonics* of the sampling rate. This is because we only really care about the major oscillations, not slow trends.

I considered adding some more complicated logic to reduce some deleterious effects, especially early on, but ultimately decided to apply the KISS principle and leave it out.

```
{
  name: "Fourier",
  sin: [0,0,0,0,0,0],
  cos: [0,0,0,0,0,0],
  round: 0,

  run(scores) {
    let ave = average(scores)

    for (let i = 0; i < 6; i++) {
      this.sin[i] += ave * Math.sin(2*Math.PI * this.round / (i+1))
      this.cos[i] += ave * Math.cos(2*Math.PI * this.round / (i+1))
    }

    this.round++

    let next = this.sin.reduce((t,a,i) => t + a * Math.sin(2*Math.PI * this.round / (i+1)),0)
             + this.cos.reduce((t,a,i) => t + a * Math.cos(2*Math.PI * this.round / (i+1)),0)

    return 50 + 2/5 * Math.max(next,0) / this.round
  }
}

```

# Answer
> 7 votes
# iDontWannaFail

This bot hates failing classes, so it minimizes the deviation between the average and the returned score so the Game Theory score is as large as possible. The deviation is randomly selected from -5 to 6 to allow some room for variation. However, if the score is below a `70`, a random integer between 70 and 100 is chosen. If the average is below 60, a number that is within `2/3` of the average score is selected to ensure a score that is at least 50 (Our little bot is rather disappointed that its goal wasn't reached, though, but hey, a 50 is better than a 10!)

```
{
    name: "iDontWannaFail",
    run: (scores) => {
        let sum = scores.reduce((a, b) => a + b, 0);
        let avg = (sum / scores.length) || 0;
        let output = avg * 0.8 + Math.round(Math.random()*11)-5;
        if (avg > 60) {
            if (output < 70) {
                output = Math.floor(Math.random() * 30) + 70;
            }
        }
        else {
            if (avg > 25) {
                output = Math.round(Math.random() * avg / 1.5) + avg; // Worst case is 49.
            }
            else {
                output = Math.round(3.75 * avg); // Decent results unless avg is very low
            }
        }
        if (output > 100) {
            output = 100;
        }
        return output;
    }
}

```

**Edit:** The else code failed, setting `avg=10` returns, at best, `16`, resulting in `38` as the final score. Another nested `if` has been added to solve this issue (`avg=10` returns `52`)

# Answer
> 7 votes
# The Fat(a)

This algorithm entirely depends on the following lines:

```
let sign = var_drift>0 ? 1 : -1;
this.velocity_pred = 0.3*(sign*average(this.all_v)*2-velocity);
a = a+this.velocity_pred;

```

Where var\_drift is the immediate difference in variance of all the submissions in the current round n, minus the variance of the last round. velocity is the immediate difference in the mean of all the submissions in the current round n, minus the mean of the last round. all\_v is the absolute value all the velocities so far. The average all all true velocities turns out to be near 0 as the mean oscillates.

The average velocity is used to approximate the magnitude of how much the movement will be. The average velocity - the immediate last velocity works with the following intuition:

If the last velocity is large positive, then there is higher chance that the next movement will be actually negative (To correct the average), and vice versa.

## important note

The numerical solver is largely obsolete and can be replaced with the simple formula

`x = 50 + 0.4*a`.

The derivative for the scoring function \\$\sqrt{x\*(100-\lvert0.8\*a-x\rvert}\\$ is this guy here(according to https://www.derivative-calculator.net/):

\\$\dfrac{-\left|x-\frac{4a}{5}\right|-\frac{x\left(x-\frac{4a}{5}\right)}{\left|x-\frac{4a}{5}\right|}+100}{2\sqrt{x\left(100-\left|x-\frac{4a}{5}\right|\right)}}\\$ (eq.1)

While I originally thought at first glance that this will be impossible to reduce, I decided to use an iterative solver to find the root instead. But upon reflecting on this and testing emprically that the root for (eq.1) is the same as found with the simple formula \\$ x = 50+0.4\*a \\$. I realized that this entire thing can be easily reduced to be the same as \\$x=50+0.4\*a\\$ if we are looking for an x larger than \\$ 4\*a/5 \\$. The root for the best x lower than \\$ 0.8a\\$ is the root of \\$2x^2 -\frac{508}{5}\*x - \frac{2004}{25}a\\$. Which by quadratic formula simplifies to

\\$x = -101.6 \pm \frac{\sqrt{10322.56 + 641.28a}}{4} \\$

Because of our assumption that x must be \< a, the only viable form of this function is

\\$x = -101.6 - \frac{\sqrt{10322.56 + 641.28a}}{4} \\$

And gives a massive negative number...

And just to complete this analysis when \\$x = \frac{4\*a}{5}\\$ we have the funny equation

\\$ 0 = \frac{100}{2\* \sqrt{x\*(100-\lvert x-\frac{4\*a}{5}\rvert)}} \\$

This in fact does have a "solution", when

\\$ \lim\_{2\* \sqrt{x\*(100-\lvert x-\frac{4\*a}{5}\rvert)} \to \inf}\\$.

Which is just our original scoring function \*2. This again points to a extremely large negative number "solution" \\$\lim\_{x \to -\inf} \\$. But a "solution also exists for when both x and a are extremely large,but a and x are almost equal to each other (\\$ \lim\_{x \to \inf a \to \inf} x-\frac{4\*a}{5} \<100\\$).

Update: Cleaned up code, rewritten numerical solution finder.

```
 {
                   //============\\
    name: "Fat",  //  []    []   \\
    last_avg:70,  //     w        \\
    last_var:0,   //    ---       \\
    n:0,        // 00 0 00 00 00 0\\
    all_v:[],   // ||||||||||||||\\
    run(scores){
      function calc_variance(scores){return Math.sqrt(sum(scores.map(
        function(x){return Math.pow(x - average(scores),2)/(scores.length-1)})));};
      function find_min(a){let d = 0;let c = 0;let x = 0;let inc =10;
      let num =0;while(true){c = (x+inc)-(4*a)/5;
      d = (-Math.abs(c) - ((x+inc)*c)/Math.abs(c) + 100)/2*Math.sqrt((x+inc)*(100-Math.abs(c)));
      if((d<0)){inc/=10;}else{x+=inc;};num+=1;
      if(Math.abs(x)<=0.01 || num>10000){break;}}return x;};
      let a = average(scores);
      if(this.n<2){a = this.n==0 ? 66:71.5;this.all_v.push(2.5);
      }else{
        let velocity = average(scores) - this.last_avg;
        this.all_v.push(Math.abs(velocity));
        let var_drift = calc_variance(scores) - this.last_var;
        let sign = var_drift>0 ? 1 : -1;
        this.velocity_pred = 0.3*(sign*average(this.all_v)*2-velocity);
        a = a+this.velocity_pred;
      }
      this.last_var = calc_variance(scores);
      this.last_avg = average(scores);
      this.n +=1;
      //return 50+a*0.4;
      return find_min(a);
    }
},

```

# Answer
> 6 votes
# SimpleWeighted

```
{
    name: "SimpleWeighted",
    weights: (E => {
        let csum = [...Array(101).keys()].map((s=>n=> s+=Math.sqrt(n*(100-Math.abs(4/5*E-n))))(0));
        return csum.map(x => 1 - x / csum[100])
    })(58.863975225),
    run() {
        let rand = Math.random();
        return 1+this.weights.findIndex(w => rand >= w)
    }
}

```

Weights each integer \\$x\\$ by its score \\$w(x)=\sqrt{x\left(100-\left|\frac45E-x\right|\right)}\\$, where \\$E=\frac{\sum\_{x=1}^{100}xw(x)}{\sum\_{x=1}^{100}w(x)}\approx 58.863975225\\$ is the mean of its own distribution.

For a continuous distribution, \\$E\approx58.6219755033\\$, but using its own mean doesn't seem like it makes for a very good strategy anyways.

# Answer
> 6 votes
## LumberJack

Kicking ass and taking logs, and it's all out of ass.

Look for the upper quartile of all the scores, and start logging that. Assume your fellow classmates are improving, and try and work out the slope of that graph, to predict the next highest scores.

Keep a moving average, so low initial scores don't hold you back,

```
{
    name: "LumberJack",
    scoresLog: [],
    upperQuartile(scores) {
      return scores.sort((a, b) => a - b)[Math.floor(scores.length*0.75)]
    },
    run(scores) {
        if(!scores)  {this.scoresLog.push(80);return 80;}
        const upperQScore = this.upperQuartile(scores);
        this.scoresLog.push(upperQScore);
        this.scoresLog = this.scoresLog.slice(-4)

        const avgScoresLog = average(this.scoresLog)
        const top = this.scoresLog.map((score, index) => (score-avgScoresLog)*0.5*index);
        const bottom = this.scoresLog.map((score, index) => (index-scores.length)**2)
        const intercept = this.scoresLog[0]-(sum(top)/sum(bottom));
        const predicted = this.scoresLog.length*(sum(top)/sum(bottom))+intercept;
        return Math.min(100, predicted);
    }
}

```

See the bot run below!

```
const sum = (array) => array.reduce((a,b) => a+b);
const average = (array) => sum(array)/array.length;
const bot = {
    name: "LumberJack",
    scoresLog: [],
    upperQuartile(scores) {
      return scores.sort((a, b) => a - b)[Math.floor(scores.length*0.75)]
    },
    run(scores) {
        if(!scores)  {this.scoresLog.push(80);return 80;}
        const upperQScore = this.upperQuartile(scores);
        this.scoresLog.push(upperQScore);
        this.scoresLog = this.scoresLog.slice(-4)

        const avgScoresLog = average(this.scoresLog)
        const top = this.scoresLog.map((score, index) => (score-avgScoresLog)*0.5*index);
        const bottom = this.scoresLog.map((score, index) => (index-scores.length)**2)
        const intercept = this.scoresLog[0]-(sum(top)/sum(bottom));
        const predicted = this.scoresLog.length*(sum(top)/sum(bottom))+intercept;
        return Math.min(100, predicted);
    }
}

console.log(bot.run([10,10,10,10,10,20,30,40,50,100]))
console.log(bot.run([10,10,80,90,70,20,30,40,50,100]))
console.log(bot.run([10,10,80,90,80,20,30,40,50,100]))
console.log(bot.run([100,100,100,90,90,20,30,40,50,100]))
console.log(bot.run([100,100,100,90,90,20,30,40,50,100]))
console.log(bot.run([100,100,100,90,90,20,30,40,50,100]))
console.log(bot.run([100,100,100,90,90,20,30,40,50,100]))
console.log(bot.run([100,100,100,90,90,20,30,40,50,100]))
```

# Answer
> 6 votes
# Chasing Ninety

Attempts to iteratively approach 90% of the average of previous rounds. Responds poorly to large variances, but attempts to slowly approach the ideal value.

```
{
    name: "Chasing Ninety",
    myLastGuess: 84,
    numRounds: 0,
    run(scores) {
        this.numRounds++;
        if (this.numRounds <= 1) {
            return this.myLastGuess;
        }

        let avg = average(scores);
        let difference = this.myLastGuess - (avg * 0.9);
        let adjustment = difference / Math.log2(this.numRounds);
        this.myLastGuess = this.myLastGuess - adjustment;
        return this.myLastGuess;
    }
}

```

# Answer
> 6 votes
# Bandwagon

```
{
    name: "Bandwagon",
    run: (scores) => {
        let counts = [];
        for (let radius = 1; Math.max(...counts.slice(50)) * 20 < scores.length; radius++) {
            for (let i = 50; i <= 80; i++) {
                counts[i] = +scores.map((x) => Math.abs(x - i) <= radius).reduce((x,y) => x+y);
            }
        }
        return (counts.indexOf(Math.max(...counts.slice(50))) + 1 || 253 / 3) - 1;
    }
}

```

Since everyone else got around to extrapolating the entire game history well before I could figure out how to do it poorly, Bandwagon assumes--within reason--that enough of them know what they're doing, and hopes they won't change too much, by putting itself in the center of a region containing at least 5% of last round's grades.

# Answer
> 6 votes
# Rebel

```
{
    name: "Rebel",
    counts: Array(31).fill(0),
    run(scores) {
        scores.filter((x) => x <= 80 && x >= 50).forEach((x) => this.counts[x-50]++);
        return this.counts.lastIndexOf(Math.min(...this.counts)) + 50;
    }
}

```

Bandwagon and all of the other bots are dumb and bad, so clearly the best choice of grade is the one which has been chosen the least throughout the course of the game, between 50 and 80.

# Answer
> 6 votes
# Chain estimator

Records the several latest averages, downsamples them, records the states, uses the history record to estimate the next average, and uses it to get the optimal score given the average.

{
  name: "Chain estimator",
  bin_n: 25,
  history_len: 2,
  avg_history: null,
  table: {},
  run(scores) {
    let weighted_mean = (values, weights) => {
      const result = values
        .map((value, i) => {
          const weight = weights[i]
          const sum = value * weight
          return [sum, weight]
        })
        .reduce((p, c) => [p[0] + c[0], p[1] + c[1]], [0, 0])

      return result[0] / result[1]
    };

    let avg = average(scores);
    let bin_n = this.bin_n;
    let bin_w = 100/bin_n;

    if(this.avg_history === null){
      this.avg_history = Array(this.history_len).fill();
    }

    if(this.avg_history[0] === null){
      let out = 50 + 0.4*avg;

      // updates history
      this.avg_history = this.avg_history.slice(1).concat([avg])

      return Math.min(Math.max(Math.round(out),1),100);
    }else{
      // gets the "bins"
      let bin = (v => Math.max(Math.ceil(v/bin_w)-1, 0));
      let bins = this.avg_history.map(bin);
      let bin_cur = bin(avg);

      // updates the table
      for (state in this.table) {
        this.table[state] = this.table[state].map((v,i)=>v*0.95);
      }
      if(!(bins in this.table)){
        this.table[bins] = Array(bin_n).fill(1);
      }
      this.table[bins][bin_cur] += 1;

      // estimates the avg
      let state = bins.slice(1).concat([bin_cur]);
      let mids = Array(bin_n).fill().map((_,i) => (i+.5)*bin_w);
      if(!(state in this.table)){
        this.table[state] = Array(bin_n).fill(.1);
      }
      let avg_est = weighted_mean(mids, this.table[state].map((v,i)=>Math.pow(v,5)));
      let out = 50 + 0.4*avg;

      // updates history
      this.avg_history = this.avg_history.slice(1).concat([avg])

      return Math.min(Math.max(Math.round(out),1),100);
    }
  }
}
```
</code></pre>

# Answer
> 5 votes
# Optimise Mean

```
{
  name: "Optimise Mean",
  run(scores) {
    const avg = scores ? scores.reduce((a,b)=>a+b) / scores.length : 80;
    return .4*avg+50;
  }
}

```

Maximises the geometric mean between game theory and cybersecurity score, assuming the average score will be the same as from the previous submissions. Maths ftw!

# Answer
> 5 votes
# Linear Extrapolator

Extrapolates linearly based on the two previous averages to estimate the average of this round. Estimate is clamped to previous minimum and maximum averages. Then maximize points assuming that this estimate will be the average for this round.

```
{
    name: "Linear Extrapolator",
    iteration: 0,
    average1: 0,
    average2: 0,
    minAverage: 0,
    maxAverage: 0,
    run(scores) {
        this.iteration++;
        if (this.iteration == 1) {
            return 77;
        }
        if (this.iteration == 2) {
            this.average2 = average(scores);
            this.minAverage = this.average2;
            this.maxAverage = this.average2;
            return 50 + this.average2 * 0.4;
        }
        this.average1 = this.average2;
        this.average2 = average(scores);
        let extrapolatedAverage = this.average2 + this.average2 - this.average1;

        this.minAverage = Math.min(this.minAverage, this.average2);
        this.maxAverage = Math.max(this.maxAverage, this.average2);
        extrapolatedAverage = Math.max(extrapolatedAverage, this.minAverage);
        extrapolatedAverage = Math.min(extrapolatedAverage, this.maxAverage);

        return 50 + extrapolatedAverage * 0.4;
    }
}

```

# Answer
> 5 votes
# AverageAverage

Assumes the average score will be the average of the average of scores of all rounds before it (except the first round).

```
  {
    name: "AverageAverage",
    avgLog: [],
    isFirstRound: true,
    gmean(a, b) {
      return Math.sqrt(a * b);
    },
    scoreForAvg(avg) {
      let delta = 100;
      let score = 100;
      let newScore = 0;
      while (delta > 0.05) {
        newScore = this.gmean(score, 100 - Math.abs((avg * 0.8) - score));
        delta = Math.abs(score - newScore);
        score = newScore;
      }
      return score;
    },
    run(scores) {
      if (this.isFirstRound) {
        this.isFirstRound = false;
        return 73;
      }
      this.avgLog.push(average(scores));
      let avgavg = average(this.avgLog);
      return this.scoreForAvg(avgavg);
    }
  }

```

# Answer
> 5 votes
# Lucky Dice Kid

The younger brother to Lucky Dice Bot, this kid is a big D&D fan and only trusts his d20s. Since rolling dice clearly solves all problems optimally, he ignores all of the previous round input, rolls 7 d20s, discards the lowest two, and takes the sum of the rest. This produces a value between 5 and 100, with average value roughly 65.

```
{
  name: "LuckyDiceKid",
  run(_scores) {
    let total = 0;
    let values = [];
    for (let i = 0; i < 7; i++) {
      let curr = Math.floor(Math.random() * 20) + 1;
      values.push(curr);
      total += curr;
    }
    values.sort((x, y) => (x - y));
    total -= (values[0] + values[1]);
    return total;
  }
}

```

# Answer
> 5 votes
# Grumpy Chaotic

Mr. Grumpy has a beef with his classmates and thus he wants to worsen everyone's grades. However the next day he realised he still needs a good grade in CSEC.

...Lets just say he has frequent mood swings.

```
    {
        name: "Grumpy Chaotic",
        mood: true,
        run() {
            this.mood=!this.mood;
            return this.mood?100:1;
        }
    }

```

# Answer
> 5 votes
# xXx\_Markov\_143\_xXx

Going from his immense experience of playing FPS games like BS:GO, young Markov realised he does not need to model the entire game in order to play well, he can just predict what the best 5% of players will do, and do it before them.

```
    {
        name: "xXx_Markov_143_xXx",
        mark: null,
        n_rounds: 0,
        old_average: 50,
        run(scores) {
            this.n_rounds++;
            let last_average = average(scores);
            scores = scores.filter((x)=> 100 >= x && x > 0);
            let evaluated_scores = scores.map((score) => [score, score * (100 - Math.abs(last_average * 0.8 - score))]);
            evaluated_scores.sort((a,b) => a[1] - b[1]);
            let smart_average = average(evaluated_scores.slice(Math.floor(evaluated_scores.length * 0.95)).map((a)=>a[0]));

            if (this.n_rounds == 1) {
                this.old_average = smart_average;
                this.mark = Array(201);
                for (let i = 0; i < 201; i++) {
                    this.mark[i] = Array(201);
                    for (let j = 0; j < 201; j++) {
                        this.mark[i][j] = 0;
                    }
                }
                for (let i = 0; i < 201; i++) {
                    this.mark[i][i]++;
                }
                return 77;
            }

            let quantized_avg = Math.round(2*smart_average);
            this.mark[Math.round(2*this.old_average)][quantized_avg]++;
            this.old_average = smart_average;

            // Compute a markov chain prediction
            let x_half_filter = 5;
            let y_half_filter = 1;

            let probability_sum = 0;
            let probability_moment = 0;

            for (let option = 1; option < 201; option++) {
                for (let x = -x_half_filter; x <= x_half_filter; x++) {
                    for (let y = -y_half_filter; y <= y_half_filter; y++) {
                        let X = Math.max(Math.min(quantized_avg + x, 200), 0);
                        let Y = Math.max(Math.min(option + y, 200), 0);
                        let probability = this.mark[X][Y] * (Math.pow(2, -(X-quantized_avg)*(X-quantized_avg)-(Y-option)*(Y-option)));
                        probability_sum += probability;
                        probability_moment += option / 2 * probability;
                    }
                }
            }

            for (let i = 0; i < 201; i++) {
                for (let j = 0; j < 201; j++) {
                    this.mark[i][j] *= 0.999;
                }
            }

            return probability_moment / probability_sum;
        }
    }

```

# Answer
> 5 votes
# Impatience

Impatience is the most rational bot, and wants all the other bots to just hurry up and be more rational already.

1. All the bots will behave rationally, eventually.
2. Some of the bots don't care about game theory, but all the others do.
3. There is a single optimal solution.
4. If a bot can change its answer and get a better score, the rational action is to change its answer.

Therefore, if there are `n` bots and `m` of them don't care about game theory, the exam results will converge to a Nash equilibrium, which is the rational solution.

Impatience outputs this answer to begin with, and never changes its answer unless evidence suggests it was (rationally) mistaken about the value of `m`. Impatience is the most rational bot.

```
{
    name: "Impatience",
    optimal: average => 0.4*average + 50,
    run(scores) {
        const n = scores.length;
        // rational actors who don't care about game theory
        // will output 100, to win the cybersecurity exam
        const m = scores.filter(v => v == 100).length;

        // other bots are slow, so simulate them
        do {
            const average = scores.reduce((a,b)=>a+b) / n;
            const optimal = this.optimal(average);
            // other bots take a while to get there
            scores = scores.map(v => v==100 ? 100 : 0.5*(v + optimal));
        } while ((new Set(scores)).size > ( 0?0 :3 ));

        scores = new Set(scores);
        scores.delete(100);
        if (scores.size > 0) {
            return Math.max.apply(Math, scores);
        } else {
            return 90;
        }
    }
}

```

# Answer
> 4 votes
## NaiveMeta

Bot attempts to categorize other bots and analyze their strategies to weight its own score formula. Determines a stable score based on static bot scores, and then determines the number of bots optimizing(playing well) in the last round. Approximates that all optimizers will roughly lean toward the optimal score last round. Ignores other(assumed random) bots. Then calculates an a weighted average bet between the two optimal scores weighted based on the number of bots of each type.

```
{
    name: "NaiveMeta",
    persitentScores: [],
    otherScores: [],
    lastAvg: 0,
    round: 0,
    sWeight:.2,
    oWeight:1,
    run(scores) {
      this.round++;
      if (this.round === 1) {
        return 75;
      }
      if(this.round === 2){
        this.persitentScores = scores;
      }
      var optimizer = 0;
      var avg = average(scores);
      var optimalScoreLR = 50+ .4*avg;
      var newPScores = [];
      scores.forEach(s=>{
        let i = this.persitentScores.indexOf(s);
        if(i!==-1){
            this.persitentScores.splice(i,1);
            newPScores.push(s);
        }
        else if( Math.abs(s - optimalScoreLR) <=12){
            optimizer++;
        }
      });
      this.persitentScores = newPScores;
      var pOptimalScore =  50+.4*average(this.persitentScores);
      if (this.round === 2) {
        return optimalScoreLR;
      }
      return ((pOptimalScore*this.persitentScores.length*this.sWeight) + (optimalScoreLR  * optimizer*this.oWeight))/(this.persitentScores.length*this.sWeight+optimizer*this.oWeight);
    }
  }

```

# Answer
> 4 votes
# Geothmetic Meandian

Not a serious entry, but seemed appropriate.

```
{
  name: "Goethmetic Meandian",
  run: scores => {
    let a = new Float64Array(scores.filter(x => x > 0));
    do {
      a.sort();
      a = [
        a.reduce((x, y) => x + y, 0) / a.length,
        Math.pow(a.reduce((x, y) => x * y, 1), 1 / a.length),
        a.length % 2 ? a[Math.floor(a.length / 2)] : (a[Math.floor(a.length / 2)] + a[Math.ceil(a.length / 2)]) / 2,
      ];
    } while (Math.abs(a[0] - a[1]) > 0.0001 || Math.abs(a[1] - a[2]) > 0.0001);
    return Math.min(100, Math.max(1, Math.round(a[0])));
  },
}

```

# Answer
> 4 votes
## LastMinute HistoryAnalyzer

This bot records differences and takes advantage of that the averages periodically wobble, and tries to guess based on that. It doesn't expect to win, but it will do its best to reach a good ranking.

It's named "LastMinute" because I submitted just before the deadline, but its name also applies to its behaviour: it analyzes the last moments of history.

```
{
  name: 'LastMinute HistoryAnalyzer',
  avgs: new Array(6).fill(63),
  diffs: new Array(3).fill(1),
  run(prev){
    const prevAvg = average(prev)
    this.avgs.push(prevAvg)
    this.avgs.shift()
    this.diffs.push(this.avgs[this.avgs.length-1] - this.avgs[this.avgs.length-2])
    const diffs4 = this.diffs.shift()
    const diffs2 = this.diffs[1]
    const avg = average([diffs2, diffs4]) + prevAvg
    return (77.9 + (avg - 70) * 0.3) //Magic formula for converting a guessed average to the corresponding equilibrium point (inaccurate when average is far from 70, but that's what I came up with)
  }
},

```

PS: I'm completely new to programming challenges, KotH and codegolf.se, but I like programming in JavaScript and like challenges, so I decided to give it a try.

---

Actually, I wanted to make it like this (it doesn't make much difference, though), but I was tired and screwed it up:

```
{
  name: 'LastMinute HistoryAnalyzer',
  avgs: new Array(6).fill(63),
  diffs: new Array(3).fill(1),
  run(prev){
    const prevAvg = average(prev)
    this.avgs.push(prevAvg)
    this.avgs.shift()
    this.diffs.push(this.avgs[this.avgs.length-1] - this.avgs[this.avgs.length-2])
    const diffs4 = this.diffs.shift()
    const diffs2 = this.diffs[1]
    const avg = average([diffs2, diffs4]) + average(this.avgs)
    return (77.9 + (avg - 70) * 0.3) //Magic formula for converting a guessed average to the corresponding equilibrium point (inaccurate when average is far from 70, but that's what I came up with)
  }
},

```

# Answer
> 3 votes
# 90ies

```
{
  name: "90ies",
  run() {return 90}
}

```

After thinking very hard and not getting very far, this seems to be the one and only optimal solution.

# Answer
> 3 votes
Returns `50 + 0.4*avg(scores)`:

```
{
  name: "Near-stable",
  run: s => {
    return 50 + 0.4*s.reduce((a, b) => a + b, 0)/s.length;
  }
}

```

# Answer
> 3 votes
# USACO (Unofficial)

Uses binary search to maximize its score.

```
(() => {
    function *stateMachine() {
        let left = 1;
        let right = 100;

        yield 51;

        let counter = 0;

        while (true) {
            counter++;

            const middle = left + (right - left) / 2;

            if (counter % 10 === 0) {
                left = Math.max(1, Math.random() * 100);
                right = Math.max(1, Math.random() * 100);

                if (left > right) [left, right] = [right, left];
            }

            const scores = yield middle;
            scores.sort((a, b) => a - b);

            let countLower = 0;
            let countHigher = 0;

            for (const score of scores) if (score < middle) countLower++;
            for (const score of scores) if (score > middle) countHigher++;

            if (countLower > countHigher) {
                right = middle;
            } else {
                left = middle;
            }
        }
    };

    const iterator = stateMachine();
    let score = iterator.next().value;

    return {
        name: "USACO (Unofficial)",
        run: scores => {
            const oldScore = score;
            score = iterator.next(scores).value;
            return oldScore;
        }
    };
})()

```

# Answer
> 3 votes
# Greedy

Assumes that all other bot keep their scores the same as last round, and chooses a score that maximizes `own_point - max(other_bots_points)`.

```
{
  name: "Greedy",
  run(scores){
    let max_index = (arr => arr.indexOf(Math.max.apply(Math, arr)));
    let point = (avg) => {
      return (s) => Math.sqrt(s*(100-Math.abs(0.8*avg-s)))
    }
    let goal = (scores) => {
      return (mine) => {
        let avg = average(scores.concat([mine]));
        return point(avg)(mine) - Math.max(...scores.map((v,i)=>point(avg)(v)));
      }
    }

    let avg = average(scores);
    let range = Array(101).fill().map((_,i)=>i);
    return range[max_index(range.map((v,i) => goal(scores)(v)))];
  }
}

```

# Answer
> 3 votes
# Overshoot (slightly)

I started off with the idea that a CS mark below the target (80% of the average CS mark) is very penalizing. Better then to be too high than too low.

I started off taking the 80th percentile of past averages as my estimation for next round average CS mark, but soon realized that it was too much. Some tweaking of the parameters later I ended up with this result, which takes just slightly above the median.

```
{
    name: "Overshoot (slightly)",
    historyAvg: [],
    rounds: 0,

    run(scores) {
        this.rounds++
        if (this.rounds == 1) return 75.5;

        this.historyAvg.push(average(scores))
        this.historyAvg.sort((a,b) => a-b);
        let estimatedAvg = this.historyAvg[Math.ceil(this.historyAvg.length * 0.535)-1]
        let score = 50 + estimatedAvg * 2/5;

        return score
    }
},

```

# Answer
> 2 votes
## SimpleCalculus

Just the result of plugging `x = avg` into @Bubbler's formula.

```
{
    name: "SimpleCalculus",
    run: _ => 250 / 3,
}

```

# Answer
> 2 votes
# Elevens

```
{
    name: "Elevens",
    run() { return (Math.floor(Math.random() * (10 - 1) ) + 1) * 11; }
}

```

Randomly returns 11, 22, 33, 44, 55, 66, 77, 88 or 99.

# Answer
> 2 votes
# 7-ELEVEn

```
{
  name: "7-ELEVEn",
  run() { return 77 }
}

```

# Answer
> 2 votes
# ExponentialMovingAverage

```
{
    name: 'ExponentialMovingAverage',
    prev: 80,
    run(scores) { return (scores && scores.length ? average(scores) : 80) * 0.225 + this.prev * 0.775 },
}

```

~~Returns EMA of the average score.~~ Of course, I forgot to update the previous value, so it does not calculate the EMA, but some mix of the initial and the average score, but it gives much better results than I expected.

# Answer
> 2 votes
# Woulda-Shoulda

```
{
  name: "WouldaShoulda",
  ownLast: 0,
  isFirst: true,
  run(scores) {
    if (this.isFirst) {
      this.isFirst = false
      this.ownLast = 80
    } else {
      let count = scores.length
      let otherAvg = (sum(scores) - this.ownLast) / (count - 1)
      this.ownLast = (80 * count + otherAvg * count - otherAvg) / (2 * count - 1)
    }
    return this.ownLast
  }
}

```

Returns 80 the first round, then each subsequent round returns what would have been the best option the previous round.

# Answer
> 2 votes
# AverageAverageAverage

```
{
    name: "AverageAverageAverage",
    run: _ => 77.22599053004494
}

```

Turns out AverageAverage is pretty damn good. So, AverageAverageAverage uses an average of its averages.

(Occasionally beats its dynamic namesake in test runs, but I suspect this won't last as more bots get added lmao)

# Answer
> 2 votes
# Chessmaster

Game theory is a lot easier when you know what the other players are going to do.

(In lieu of constantly editing this answer, it is generated by a Stack Snippet based on the leaderboard. I hope this is okay. If not, I'll try to ninja-edit the final version in just before the deadline.)

<pre><code>/* Configuration */

var QUESTION_ID = 224621; // Obtain this from the url
// It will be like https://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!)qM4PLHIEQza67lA3AlA";

/* App */

var answers = [], answer_page = 1;

function answersUrl(index) {
  return "https://api.stackexchange.com/2.2/questions/" +  QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

function getAnswers() {
  let oreq = new XMLHttpRequest();
  oreq.addEventListener("load", function() {
    let data = JSON.parse(this.responseText);
    answers.push.apply(answers, data.items);
    if (data.has_more) getAnswers();
    else process();
  });
  oreq.open("GET", answersUrl(answer_page++));
  oreq.send();
}

getAnswers();

function process() {
  let codez = answers.map(a => {
    var body = a.body_markdown;

    let x = [];
    let stage = 0;
    body.split("\n").forEach(line => {
      if (line.startsWith("```")) {
        stage += 1;
      } else if (stage == 1) {
        x.push(line);
      }
    });
    if (stage > 0) {
        return x.join("\n");
    }

    x = body.split("\n").filter(
      l => l && l.startsWith("    ")
    );
    return x.join("\n");
  }).map(x => (new DOMParser()).parseFromString("<!DOCTYPE html>" + x, "text/html").body.textContent);

  document.getElementById("here").innerText = JSON.stringify(codez);
}

```
<code><pre>
{
    name: "Chessmaster",
    pieces: (
        codes => codes.map(
            code => { try {
                return (new Function('return ' + code + ';'))();
            } catch {
                console.log("could not parse", code);
                return undefined;
            }; }
        ).filter(p => p !== undefined)
    )(<span id="here"></span>),
    run(scores) {
        const prediction = this.pieces.map(
            piece => { try {
                return parseInt(piece.run(scores.slice()));
            } catch {
                console.log("could not run", piece.name);
                return NaN;
            }; }
        ).filter(s => 0 <= s && s <= 100);
        const average = prediction.reduce((a,b)=>a+b) / prediction.length;
        return 50 + 0.4*average;
    }
}
</pre></code>
```

# Answer
> 2 votes
## Equilibrium

The optimal score is 50 + (0.4 * avg). There is an equilibrium point at approximately 83.333 where the average score is also the optimal score, e.g. avg = 50 + (0.4 * avg).

This bot assumes the average will move towards the equilibrium point, so it picks a point halfway between the equilibrium and the last average. It then chooses the optimal score for that halfway point.

```
{
  name: "Equilibrium",
  equil: 83.333,
  first_round: true,
  run(scores) {
    if (this.first_round) {
      this.first_round = false;
      return this.equil;
    } else {
      let midpoint = (average(scores) + this.equil) / 2;
      return (50 + 0.4*midpoint);
    }
  }
}

```

# Answer
> 2 votes
# SettleDown

Starts off really unpredictably, but over time sets its result closer and closer to the average of the last round

(if this doesn't run, please let me know!)

```
{
    name: "SettleDown",
    rounds: 0,
    lastAverage: 0,
    run(scores) {
        this.rounds++
        this.lastAverage = (sum(scores) - this.lastAverage) /(scores.length - 1)*0.8
        return (this.lastAverage + ( Math.floor( Math.random() * 100 - 50) / (this.rounds/5+1)))%101
    }
}

```

# Answer
> 1 votes
# That mean average Joe

```
{
  name: "That mean average Joe",
  Joe: [],
  run( scores ) {
    this.Joe.push(average(scores)); // like.no.one(ever(did));
    return average(this.Joe)*1.1111111111111111;
  }
}

```

This returns the mean of the averages of the scores of all the turns played so far, multiplied by `1.1111111111111111`.

### Why 1.111111111111111?

Suppose that the average of every turn is always the same constant and let's take it as the reference unit.

Now knowing that in the next turn the average of the scores will be **1**, our smart move for the Game Theory exam would be to return **0.8**.

However in this way we would score **100%** in Game Theory (impossible to do better) and **80%** in Cybersecurity (relative to the class average) and since the KOTH's final score would be the geometric mean of the two exams, we'd better find a compromise between the two rather than maximise one of them.

The perfect compromise would be scoring **88.88888...%** in both, cause that's **11.11111...%** less than **100%** and more **80%**.

To score **88.88888...%** in Game Theory means being **11.11111...%** away from the average of Cybersecurity scores, doesn't matter if it is 11% more or 11% less.

However if we move to **11.11111...%** more than the average, rather than less, we would get a better score in Cybersecurity, while still scoring the optimal **88.88888...%** in Game Theory.

So returning **11.11111...%** more than the average of the scores is what we want.

In the KOTH challenge the average of the scores is unlikely to be the same every turn, so as a reference unit we take the mean of the averages of the scores of all the turns played so far.

NOTE: This wasn't the actual reasoning that brought me to the constant, my initial reasoning was quite similar but buggy and I tried to fix it till I came up with this. However I wouldn't say that this constant is the result of luck, but rather of intuition. After all it seems that the purpose of our reasoning has always been to support and explain our intuitions.

# Answer
> 1 votes
# Golden

This bot was inspired by Self Aware Maximizer, but also takes into account how its own score affects the scores of other players.

Golden uses a golden section search to find which cybersecurity score would have maximized the previous round's score for itself minus the previous round's next best score. It then chooses the average of the optimal cybersecurity scores it has found.

The first cybersecurity score returned was determined by determining the best cybersecurity score for the first round 1000 times in a row, then taking the average.

{
    name: 'Golden',
    previousChoice: 0,
    first: true,
    goldenRatio: (Math.sqrt(5) + 1) / 2,
    weightedBest: 75.28679012885513,
    round: 0,
    goldenSectionSearch(f, min, max, tolerance = 1e-5) {
        while (max - min > tolerance) {
            let leftInterior = max - (max - min) / this.goldenRatio
            let rightInterior = min + (max - min) / this.goldenRatio

            if (f(leftInterior) < f(rightInterior)) {
                max = rightInterior
            } else {
                min = leftInterior
            }
        }
        return (min + max) / 2
    },
    run(choices) {
        if (this.first) {
            this.previousChoice = this.weightedBest
            this.first = false
            return this.weightedBest
        }
        const n = choices.length
        const i = choices.indexOf(this.previousChoice)
        const otherChoices = [...choices.slice(0, i), ...choices.slice(i + 1)]
        const sum = otherChoices.reduce((a, b) => a + b)

        function score(candidate) {
            const average = (sum + candidate) / n
            const gameTheory = 100 - Math.abs(average * 0.8 - candidate)
            const score = Math.sqrt(candidate * gameTheory)
            const otherScores = otherChoices.map(c => {
                const gameTheory = 100 - Math.abs(average * 0.8 - c)
                return Math.sqrt(c * gameTheory)
            })
            const best = Math.max(...otherScores)
            return best - score
        }

        const best = this.goldenSectionSearch(score, 1, 100)
        this.weightedBest = (this.weightedBest * this.round + best) / (this.round + 1)
        this.round++
        this.previousChoice = this.weightedBest
        return this.weightedBest
    }
}
```
</code></pre>

# Answer
> 1 votes
# The Skinny

Basically the same as fat, just trying to use less lines of code, by using an approximate constant for average velocity and not using numerical solver.

```
Fat                             78684.97459611233
Skinny                          78684.90970216368
Overshoot (slightly)            78684.59923852411
Histogrammer                    78684.24574125063
ExponentialMovingAverage        78680.78518171726
Optimise Mean                   78679.65559244195
Near-stable                     78679.65559244195
Calculus                        78679.47519324803
Squidward                       78679.11475381341
FollowTheLeader                 78677.6890436919
Smartleton                      78673.66796955772
Simpleton                       78673.62925366624

```

<pre><code>  {
    name: "The Skinny",
    l_a:71.5,
    l_v:2.5,
    n:0,
    run(s){
      let a = sum(s)/s.length;
      let va =Math.sqrt(sum(s.map(function(x){return Math.abs(x - a)})));
      let p = 0.3*(((va - this.l_v)>0?1:-1)*4.8 - (a - this.l_a));
      this.l_a = a;this.l_v = va;this.n++;
      return this.n <2 ? 77 : 50+(a+p)*2/5;
    }
},
```

# Answer
> 0 votes
# 78

Turns out 78 is much better than 77

```
{
    name: "78",
    run(s){
      return 78;
    }
},

```

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


title: Find the Second Zero

text:
# Question
Title: Find the Second Zero
# Challenge

Given an integer in 32-bit two's complement format, return the index of the *second* least-significant zero digit in the binary representation, where an index of `0` represents the least significant bit, and an index of `31` represents the most significant bit.

If there is no second zero, you may return 0, any negative number, any falsy value, or report an error in a way that makes sense in your language.

You may use 1-indexing if you prefer, but the test cases below will use 0-indexing.

You may use unsigned integers if you prefer; if you do, then you must handle integers in the range `[0, 2^32)`. If you use signed integers, you must handle integers in the range `[-2^31, 2^31)`. The test cases here will use signed integers, but note that `-x` (signed) is `2^32 - x` (unsigned).

# Test Cases

```
0  (0b00)        -> 1
1  (0b001)       -> 2
10 (0b1010)      -> 2
11 (0b01011)     -> 4
12 (0b1100)      -> 1
23 (0b010111)    -> 5
-1 (0b11..11)    -> None
-2 (0b11..10)    -> None
-4 (0b11..00)    -> 1
-5 (0b11..1011)  -> None
-9 (0b11..10111) -> None
2^31-2 (0b0111..1110) -> 31

```

# Scoring

This is , so the shortest answer in each language wins!

# Answer
# Python 2, 45 bytes

```
lambda n:[i for i in range(32)if n|1<<i>n][1]

```

Try it online!

Uses 0-indexing, unsigned numbers, and throws an error on no second zero.

Simply creates a list of indices of non-set bits, from lowest to highest, and returns the second entry.
> 16 votes

# Answer
## JavaScript (ES6), 34 bytes

Returns a 0-based index, or `-1` if no second zero is found.

```
n=>31-Math.clz32((n=~n^~n&-~n)&-n)

```

### Test cases

```
let f =

n=>31-Math.clz32((n=~n^~n&-~n)&-n)

console.log(f(0))       // -> 1
console.log(f(1))       // -> 2
console.log(f(10))      // -> 2
console.log(f(11))      // -> 4
console.log(f(12))      // -> 1
console.log(f(23))      // -> 5
console.log(f(-1))      // -> None
console.log(f(-2))      // -> None
console.log(f(-4))      // -> 1
console.log(f(-5))      // -> None
console.log(f(-9))      // -> None
console.log(f(2**31-2)) // -> 31
```

### Alternate expression

```
n=>31-Math.clz32((n=~n^++n&-n)&-n)

```

---

## Recursive version, 42 bytes

Returns a 0-based index, or `false` if no second zero is found.

```
f=(n,p=k=0)=>n&1||!k++?p<32&&f(n>>1,p+1):p

```

### How?

```
f=(n,p=k=0)=>                               // given n, p, k
             n&1||                          // if the least significant bit of n is set
                  !k++?                     // or this is the 1st zero (k was not set):
                       p<31&&               //   return false if p is >= 31
                             f(n>>1,p+1)    //   or do a recursive call with n>>1 / p+1
                                        :p  // else: return p

```

### Test cases

```
f=(n,p=k=0)=>n&1||!k++?p<32&&f(n>>1,p+1):p

console.log(f(0))       // -> 1
console.log(f(1))       // -> 2
console.log(f(10))      // -> 2
console.log(f(11))      // -> 4
console.log(f(12))      // -> 1
console.log(f(23))      // -> 5
console.log(f(-1))      // -> None
console.log(f(-2))      // -> None
console.log(f(-4))      // -> 1
console.log(f(-5))      // -> None
console.log(f(-9))      // -> None
console.log(f(2**31-2)) // -> 31
```

### Alternate version suggested by Neil, 41 bytes

Returns a 0-based index, or throws a *too much recursion* error if no second zero is found.

```
f=(n,c=1)=>n%2?1+f(~-n/2,c):c&&1+f(n/2,0)

```
> 6 votes

# Answer
# Jelly, 7 bytes

```
|‘‘&~l2

```

Try it online!

It outputs something not in the range \[1,31\] if there isn't the second zero. This includes `32` `33` and `(-inf+nanj)`. I guess that makes some sense.

It calculates `log(((x|(x+1))+1)&~x)/log(2)`.
> 5 votes

# Answer
# IA-32 machine code, ~~14~~ 13 bytes

Hexdump:

```
F7 D1 0F BC C1 0F B3 C1 0F BC C9 91 C3

```

Disassembly listing:

```
0:  f7 d1                   not    ecx
2:  0f bc c1                bsf    eax,ecx
5:  0f b3 c1                btr    ecx,eax
8:  0f bc c1                bsf    ecx,ecx
b:  91                      xchg   eax, ecx
c:  c3                      ret

```

Receives input in `ecx`; output is in `al`. Returns 0 on error.

First of all, it inverts the input, so it can use the bit scan instructions to look for set bits. It looks for the least significant set bit, resets it, looks for least significant set bit again, and returns the result.

If the bit-scan instruction doesn't find any set bit, the Intel documentation says the output is undefined. However, in practice all processors leave the destination register unchanged in this case (as noted by Cody Gray, AMD documentation describes this behavior as mandatory).

So, there are the following cases:

1. No zero bits (binary 111...1): ecx is set to 0 by `not` and remains 0
2. One zero bit: ecx is set to 0 by `btr` and remains 0 after `bsf`
3. Two zero bits: ecx is set to the proper value by `bsf`
> 4 votes

# Answer
# Java (OpenJDK 8), ~~44~~ 38 bytes

```
i->i.numberOfTrailingZeros(~i&-i-2)&31

```

Try it online!

Returns 0 if no second zero bit exists.
> 4 votes

# Answer
# Java, ...  ~~194 191~~  186 Bytes

```
static int f(int n){char[] c=Integer.toBinaryString(n).toCharArray();int j=0,o=2^32-2,i=c.length,l=i-1;if(n<0|n>o)return 0;for(;j<2&i>0;j+=c[--i]==48?1:0);if(j==2)return l-i;return 0;}

```

*-159 Bytes for using smaller variable names and removing whitespace*
*-25 Bytes, after taking even shorter variables and thanks to @KevinCruijssen tips*
*-18 Bytes, more whitespaces, function name*
*-3 Bytes, thanks to @KevinCruijssen, shortening if condition*
*-5 Bytes, Thanks to @Arnold Palmer, @KevinCruijssen, shortening loop*

## Ungolfed

```
public static int getPosSecondZero2(int number){
    int overflow = 2^32-2;
    if(number < 0 || number > overflow){
        return 0;
    }
    String binaryString = Integer.toBinaryString(number);
    char[] binaryCharArray = binaryString.toCharArray();
    int count = 0;
    int idx = binaryCharArray.length;
    int length = binaryCharArray.length -1;
    while(count < 2 && idx>0){
        idx--;
        if(binaryCharArray[idx] == '0'){
            count++;
        }
    }
    if(count == 2)
        return length-idx;
    return 0;
}

```
> 3 votes

# Answer
# Dyalog APL, 20 bytes

```
{2⊃(⍳32)/⍨~⌽⍵⊤⍨32⍴2}

```

Uses 1-indexing, throws `INDEX ERROR` in case of no second zero.

**How?**

`⍵⊤⍨` \- encode  as a

`32⍴2` \- binary string of length 32

\- reverse

`~` \- negate (0→1, 1→0)

`(⍳32)/⍨` \- compress with the range 1-32 (leaving indexes of zeros)

`2⊃` \- pick the second element
> 2 votes

# Answer
# Jelly, 13 bytes

```
B¬Ṛ;1,1ḣ32TḊḢ

```

Try it online!

Uses 1-indexing, gets unsigned integer as input. Returns `0` for not found.
> 1 votes

# Answer
# Jelly, 12 bytes

```
,4BUFḣ32¬TḊḢ

```

A monadic link, taking an integer, using the unsigned option and returning the 1-indexed result (returns 0 when none exists).

**Try it online!**

or

```
32Ḷ2*|€n⁸TḊḢ

```

**Try that**

### How?

1.

```
,4BUFḣ32¬TḊḢ - Link: number, n   e.g. 14
,4           - pair with 4            [14,4]
  B          - to binary              [[1,1,1,0],[1,0,0]]
   U         - upend                  [[0,1,1,1],[0,0,1]]
    F        - flatten                [0,1,1,1,0,0,1]
     ḣ32     - head to 32             [0,1,1,1,0,0,1] (truncates the right if need be)
        ¬    - not (vectorises)       [1,0,0,0,1,1,0]
         T   - truthy indexes         [1,5,6]
          Ḋ  - dequeue                [5,6]
           Ḣ - head                   5
             -   if the dequeued list is empty the head yields 0

```

2.

```
32Ḷ2*|€n⁸TḊḢ - Link: number, n   e.g. 14
32Ḷ          - lowered range of 32    [ 0, 1, 2, 3, 4, 5, ...,31]
   2*        - 2 exponentiated        [ 1, 2, 4, 8,16,32, ...,2147483648]
     |€      - bitwise or for €ach    [15,14,14,14,30,46, ...,2147483662]
        ⁸    - chain's right argument 14
       n     - not equal?             [ 1, 0, 0, 0, 1, 1, ..., 1]
         T   - truthy indexes         [ 1, 5, 6, ..., 32]
          Ḋ  - dequeue                [ 5, 6, ..., 32]
           Ḣ - head                   5
             -   if the dequeued list is empty the head yields 0

```
> 1 votes

# Answer
# x86\_64 machine code, ~~34~~ 32 bytes

Not sure if this is the right approach, quite a lot of bytes (turns out it is not):

```
31 c0 83 c9 ff 89 fa 83 e2 01 83 f2 01 01 d1 7f 09 ff c0 d1 ef eb ee 83 c8 ff 83 f8 1f 7f f8 c3

```

Try it online!

```
second_zero:
  # Set eax = 0
  xor  %eax, %eax
  # Set ecx = -1
  xor %ecx,%ecx
  not %ecx

  # Loop over all bits
Loop:
  # Get current bit
  mov %edi, %edx
  and $0x1, %edx
  # Check if it's zero and possibly increment ecx
  xor $0x1, %edx
  add %edx, %ecx
  # If ecx > 0: we found the position & return
  jg Return
  # Increment the position
  inc %eax
  # Shift the input and loop
  shr %edi
  jmp Loop

Fix:
  # If there's not two 0, set value to -1
  xor %eax,%eax
  not %eax

Return:
  # Nasty fix: if position > 31 (e.g for -1 == 0b11..11)
  cmp $31, %eax
  jg  Fix

  ret

```

Thanks @CodyGray for `-2` bytes.
> 1 votes

# Answer
# 8th, 149 bytes

```
2 base swap >s nip decimal s:len 32 swap n:- ( "0" s:<+ ) swap times s:rev null s:/ a:new swap ( "0" s:= if a:push else drop then ) a:each swap 1 a:@

```

**Commented code**

```
: f \ n -- a1 a2 n

  \ decimal to binary conversion
  2 base swap >s nip decimal

  \ 32bit formatting (padding with 0)
  s:len 32 swap n:- ( "0" s:<+ ) swap times

  \ put reversed binary number into an array
  s:rev null s:/

  \ build a new array with position of each zero
  a:new swap ( "0" s:= if a:push else drop then ) a:each

  \ put on TOS the position of the 2nd least least-significant zero digit
  swap 1 a:@
;

```

**Usage and output**

```
ok> : f 2 base swap >s nip decimal s:len 32 swap n:- ( "0" s:<+ ) swap times s:rev null s:/ a:new swap ( "0" s:= if a:push else drop then ) a:each swap 1 a:@ ;

ok> [0, 1, 10, 11, 12, 23, -1, -2, -4, -5, -9, 2147483646]

ok> ( dup . " -> " .  f . 2drop cr ) a:each
0 -> 1
1 -> 2
10 -> 2
11 -> 4
12 -> 1
23 -> 5
-1 -> null
-2 -> null
-4 -> 1
-5 -> null
-9 -> null
2147483646 -> 31

```
> 0 votes

# Answer
# , 66 bytes

```
w=which.min
x=strtoi(intToBits(scan()));w(x[-w(x)])*any(!x[-w(x)])

```

reads from stdin; returns `0` for no second zero and the place otherwise.

Try it online!
> 0 votes

# Answer
# MMIX, 20 bytes (5 instrs)

xxd --jelly

```
00000000: 23ff0001 c00000ff 23ff0001 da00ff00  #”¡¢Ċ¡¡”#”¡¢ḷ¡”¡
00000010: fe010000                             “¢¡¡

```

Disassembly

```
sndz    ADDU $255,$0,1
        OR   $0,$0,$255     // x |= x + 1
        ADDU $255,$0,1
        SADD $0,$255,$0     // x = popcnt((x + 1) & ~x)
        POP  1,0

```

The algorithm is essentially the obvious "remove rightmost 0; figure out position of rightmost 0". The neat trick here is that I managed to do it without flipping all the bits first.
> 0 votes

---
Tags: code-golf, number
---


title: Primes numbers with prime index

text:
# Question
Title: Primes numbers with prime index
Write a program or function that outputs/returns the first 10000 prime-indexed prime numbers.

If we call the nth prime `p(n)`, this list is

```
3, 5, 11, 17, 31, 41, 59 ... 1366661

```

because

```
p(p(1)) = p(2) = 3
p(p(2)) = p(3) = 5
p(p(3)) = p(5) = 11
p(p(4)) = p(7) = 17
...
p(p(10000)) = p(104729) = 1366661

```

Standard loopholes are forbidden, and standard output methods are allowed. You may answer with a full program, a named function, or an anonymous function.

# Answer
# MATLAB/Octave, 25 bytes

```
p=primes(2e6)
p(p(1:1e4))

```

It doesn't get much more straightforward than this.
> 17 votes

# Answer
## Python, 72 bytes

```
P=p=1;l=[]
while p<82e5/6:l+=P%p*[p];P*=p*p;p+=1
for x in l:print l[x-1]

```

This terminates with a "list index out of range error" after printing the 10000 numbers, which is allowed by default.

Uses the Wilson's Theorem method to generate a list `l` of the primes up to the 10000th prime. Then, prints the primes with the positions in the list, shifted by 1 for zero-indexing, until we run out of bounds after the 10000th prime-th prime.

Conveniently, the upper bound of `1366661` can be estimated as `82e5/6` which is `1366666.6666666667`, saving a char.

I'd like a single-loop method, printing prime-indexed primes as we add them, but it seems to be longer.

```
P=p=1;l=[]
while p<104730:
 l+=P%p*[p]
 if len(l)in P%p*l:print p
 P*=p*p;p+=1

```
> 10 votes

# Answer
## J, 11 bytes

```
p:<:p:i.1e4

```

Outputs the primes in the format

```
3 5 11 17 31 41 59 67 83 109 127 ...

```

## Explanation

```
        1e4  Fancy name for 10000
      i.     Integers from 0 to 9999
    p:       Index into primes: this gives 2 3 5 7 11 ...
  <:         Decrement each prime (J arrays are 0-based)
p:           Index into primes again

```
> 9 votes

# Answer
# Haskell, 65 bytes

```
p=[x|x<-[2..],all((>0).mod x)[2..x-1]]
f=take 10000$map((0:p)!!)p

```

Outputs: `[3,5,11,17,31,41,59,67,83,109,127.....<five hours later>...,1366661]`

Not very fast. How it works: `p` is the infinite list of primes (naively checking all `mod x y`s for y in `[2..x-1]`) . Take the first `10000` elements of the list you get when `0:p!!` (get nth element of `p`) is mapped on `p`. I have to adjust the list of primes where I take the elements from by prepending one number (-\> `0:`), because the index function (`!!`) is zero based.
> 4 votes

# Answer
# Mathematica, ~~26~~ ~~25~~ 23 bytes

```
Prime@Prime@Range@1*^4&

```

Pure function returning the list.
> 4 votes

# Answer
# AWK - 129 bytes

...oookay... too long to win points for compactness... but maybe it can gain some honor for the speed?

The `x` file:

```
BEGIN{n=2;i=0;while(n<1366662){if(n in L){p=L[n];del L[n]}else{P[p=n]=++i;if(i in P)print n}j=n+p;while(j in L)j=j+p;L[j]=p;n++}}

```

Running:

```
$ awk -f x | nl | tail
  9991  1365913
  9992  1365983
  9993  1366019
  9994  1366187
  9995  1366327
  9996  1366433
  9997  1366483
  9998  1366531
  9999  1366609
 10000  1366661

```

Readable:

```
BEGIN {
        n=2
        i=0
        while( n<1366662 ) {
                if( n in L ) {
                        p=L[n]
                        del L[n]
                } else {
                        P[p=n]=++i
                        if( i in P ) print n
                }
                j=n+p
                while( j in L ) j=j+p
                L[j]=p
                n++
        }
}

```

The program computes a stream of primes using `L` as "tape of numbers" holding found primes jumping around on `L` to flag the nearby numbers already known to have a divisor. These jumping primes will advance while the "tape of numbers" `L` is chopped off number by number from its beginning.

While chopping off the tape head `L[n]` being empty means there is no known (prime) divisor.

`L[n]` holding a value means, this value is a prime and known to divide `n`.

So either we have found a prime divisor or a new prime. Then ths prime will be advanced to the next `L[n+m*p]` on the tape found being empty.

This is like the Sieve of Eratosthenes "pulled thru a Klein's bottle". You always act on the tape start. Instead of firing multiples of primes thru the tape, you use the primes being found already as cursors jumping away from the tape start by multiple distances of their own value until a free position is found.

While the outer loop generates one prime or not prime decission per loop, the primes found get counted and stored in `P` as key, the value of this (key,value) pair is not relevant for the program flow.

If their key `i` happens to be in `P` already (`i in P`), we have a prime of the p(p(i)) breed.

Running:

```
$ time awk -f x.awk | wc -l
10000

real    0m3.675s
user    0m3.612s
sys     0m0.052s

```

Take into account that this code does not use external precalculated prime tables.

Time taken on my good old Thinkpad T60, so I think it deserves to be called fast.

Tested with `mawk` and `gawk` on Debian8/AMD64
> 4 votes

# Answer
# PARI/GP, 25 bytes

```
apply(prime,primes(10^4))

```
> 3 votes

# Answer
# CJam, 19

```
3D#{mp},_1e4<:(\f=p

```

You can try it online, but you'll need a little patience :p

For the record, the last number is 1366661.
> 2 votes

# Answer
# Husk, ~~11~~ 10 bytes

**(or ~~6~~ 5 bytes to list the first 10,000 prime-indexed prime numbers, followed by \[the infinite number of\] all the rest of them)**

*Thanks to user and Razetime for suggesting the ~~6~~ 5-byte version!*

```
↑!4İ⁰Ṡm!İp

```

Try it online! (unfortunately times-out on TIO before printing all 10,000 prime-indexed primes, but at least outputs what it's found so far...)

```
↑!4İ⁰Ṡm!İp
↑               # print the first
 !4             # 4th index of
   İ⁰           # powers of 10 (so, the first 10,000), of
     Ṡ          # hook: apply function to its own argument
      m!        # map index function to
        İp      # prime numbers
                # (implied by hook) to prime numbers

```
> 2 votes

# Answer
# Perl, 55 bytes

```
use ntheory':all';forprimes{print nth_prime$_,$/}104729

```

---

Uses @DanaJ's `Math::Prime::Util` module for perl (loaded with the pragma `ntheory`). Get it with:

```
cpan install Math::Prime::Util
cpan install Math::Prime::Util::GMP

```
> 1 votes

# Answer
# Japt, 11 bytes

```
Èj ©°Tj}jL²

```

Test it
> 1 votes

# Answer
# Python 3, ~~76~~ 109 bytes - disqualified - requalified?

edit: I am sorry, I was going for primes but missed the putting, didn´t reach the goal of "primes with primeindex". Your are free to grab and enhance. I'll be glad to be learning from you.

Based on Wilson Theorem

```
def p(x):
 c=n=2
 for i in range(3,x):
  c*=i-1
  if c%i!=0:
   print(n,i)
   n+=1

```

## without index, 62 bytes

```
def p(x):
 c=2
 for i in range(3,x):
  c*=i-1
  if c%i!=0:print(i)

```

Anyone can give me an example or good link, how to make a lambda function from it?

## edit: just to have it done right: 109bytes

```
def p(x):
 c=n=2
 p=[2]
 for i in range(2,x):
  c*=i-1
  if c%i!=0:
   p.append(i)
   if n in p: print(p[-1])
   n+=1

```
> 1 votes

# Answer
# Vyxal `H`, ~~8 7 6~~ 5 bytes

Saved 1 + 1 bytes thanks to Aaron Miller

```
²ʀǎ‹ǎ

```

Try it Online!

```
H flag - Push 100 to the stack
²ʀǎƛ‹ǎ
²        Squared (10,000)
 ʀ       Range [0, 10,000)
  ǎ      Map each a in that range to the ath prime
   ‹     Decrement each, because the challenge uses 1-indexing
    ǎ    Get the nth prime for each of those

```
> 1 votes

# Answer
# 05AB1E, 7 bytes (non-competing)

Code:

```
4°L<Ø<Ø

```

Try it online!, **note** that I have changed the `4` into a `2`. If you have a lot of time, you can change the `2` back to `4`, but this will take a *lot* of time. I need to fasten the algorithm for this.

Explanation:

```
4°       # Push 10000 (10 ^ 4)
  L      # Create the list [1 ... 10000]
   <     # Decrement on every element, [0 ... 9999]
    Ø    # Compute the nth prime
     <   # Decrement on every element
      Ø  # Compute the nth prime

```
> 0 votes

# Answer
# Jelly, 6 bytes

```
ȷ4RÆN⁺

```

Try it online!

Obviously, this times out on TIO. Here is a version that prints as it goes, which reaches \\$57493\\$ (the \\$765\\$th term) before timing out

## How it works

```
ȷ4RÆN⁺ - Main link. Takes no arguments
ȷ4     - 10000
  R    - [1, 2, 3, ..., 9999, 10000]
     ⁺ - Do twice:
   ÆN  -   n'th prime of each

```
> 0 votes

# Answer
# 05AB1E, 6 bytes

```
тnp<Ø

```

Try it online!

```
     Ø  # prime numbers with...
    <   # 1-based...
     Ø  # indices in...
  Åp    # first...
т       # 100...
 n      # ^ 2...
  Åp    # primes
        # implicit output

```
> 0 votes

---
Tags: code-golf, math, primes
---


title: Implement Minecraft's Rails

text:
# Question
Title: Implement Minecraft's Rails
## Background Information

Inspired by this answer on Arqade SE

Minecraft has rails which allow you to move minecarts around on them for transporting players, entities, and items. There are many types of rails, but today we're only interested in regular rails, which are also the only type that can curve.

When you place down a normal rail that has two adjacent rails, it will connect them. If they are not on opposite sides of the rail, the rail will curve to a 90 degree angle. However, if there are more than two adjacent rails, it can't connect all of them. In that case, it will always favor going **south-east** (this is called the south-east or Z-X rule) (for this challenge, north is up, east is right, south is down, west is left). If there is a T-junction, the rail will always connect to the "vertical" branch of the T, and then it will prioritize south over north if the main branch is east-west, and east over west if the main branch is north-south. If there is a four-way junction, the rail will connect south and east.

## I/O

For this challenge, you will need eight distinct characters: empty space, vertical rail, horizontal rail, up-left curved rail, up-right curved rail, down-left curved rail, down-right curved rail, and placeholder. You may select any characters; I choose to use box-drawing characters in my examples. You may count these eight characters as one byte in your code (this is just to allow people to use box-drawing characters instead of just like `" |-WXYZ#"` or something not as nice-looking).

You will be given input in a convenient format for a layout of existing rails. This will be a grid, so you may take it as a matrix of characters, a list of strings, newline-separated strings, etc. Anything reasonable. To simplify a bit, **your input will only contain straight rails, placeholders, and blanks**.

Your output should be a grid of the same size, but in each placeholder you are to place a rail according to the rules given. To make this challenge a bit simpler, every placeholder will always have at least two adjacent rails that are already facing the appropriate direction, so you should not change any cells except the placeholders. Note that it is possible for the rails to be on opposite sides of the placeholder, in which case you may need to place down a straight rail.

## Detailed Example

This contains every possible configuration:

```
.═.═.═.
║ ═ ║ ║
.║  ║ ║
║   ║ ║
.═══.═.
║   ║ ║
.═══.═.

```

The output for this would be:

```
╔═══╔═╗
║ ═ ║ ║
║║  ║ ║
║   ║ ║
╔═══╔═╗
║   ║ ║
╚═══╚═╝

```

Note that it's valid to have rails facing the wrong direction next to placeholders. You are guaranteed that at least two adjacent rails *are* facing the right way though. Technically, in Minecraft, this might cause the side rails to turn to face the new rail and then curve, but in this specific challenge, we'll just assume that existing straight rails will not turn, and you just need to connect up exactly two of the adjacent, correctly-oriented rails in accordance to the S-E rule.

```
   .══.══.             ╔═════╗
   ║     ║             ║     ║
.══.══.  .          ╔══╔══╗  ║
║  ║  ║  ║    ->    ║  ║  ║  ║
.══.══.  .          ╚══╔══╝  ║
   ║     ║             ║     ║
   .══.══.             ╚═════╝

```

You're running out of space on your minecart to write your code, so your code must be as short as possible! This is , so the shortest answer in bytes wins (remember that you may count your eight I/O characters as one byte).

# Answer
> 4 votes
# Python 3, 394 378 370 328 bytes

```
def p(s,i,R,C,H='═',V='║'):
 v=i%C and s[i-1]==H
 v|=(i//C and s[i-C]==V)<<3
 v|=(i%C-C+1and s[i+1]==H)<<2
 return' ═║╗══╔╔║╝║╗╚╚╔╔'[v|(i//C-R+1and s[i+C]==V)<<1]
def f(s,i=0):
 t=s.split('\n');R,C,s=len(t),len(t[0]),''.join(t)
 for c in s:print([c,p(s,i,R,C)][c=='.'],end='\n'[:-~i%C==0]);i+=1

```

Try it online!

A very naive method. Receives as input a string and iterates over its characters. If a character is a point (a placeholder), replace it with the character returned by `p`.

The function `p` builds a "4-bits integer" `v`, where:

* if its 1st bit is set, the placeholder has a valid connection with the west;
* if its 2nd bit is set, the placeholder has a valid connection with the south;
* if its 3rd bit is set, the placeholder has a valid connection with the east; and
* if its 4th bit is set, the placeholder has a valid connection with the north.

A invalid connection occurs with a direction when

1. the rail is on a border of that direction (the first placeholder in the example given by the OP has an invalid connection with the north and the west since it's in the border, so its 4-bit integer is 1010).

2. the rail of that direction is misaligned with the placeholder (the fifth placeholder in the example given by the OP has an invalid connection with the east since the east rail is misaligned, so its 4-bit integer is 1011).

After this 4-bit integer is built, it returns the corresponding box-drawing character using this integer as index of a string.

# Answer
> 4 votes
# Charcoal, 62 bytes

```
≔⪪##╗#║╝╗#╔═╔╚╔╚╔¹ηＷＳ⊞υι≔⪫υ⸿θＰθＦθ¿⁼.ι§η⊖⍘⭆⪪⭆ＫＶ﹪÷⊕⌕ηκＸ²λ²¦²⮌κ²ι

```

Try it online! Link is to verbose version of code. Byte count is adjusted for deverbosifier bug and box drawing characters. Explanation:

```
≔⪪##╗#║╝╗#╔═╔╚╔╚╔¹η

```

Create a table of box-drawing characters which serves two purposes: 1) to look up to see whether an adjacent box-drawing character wants to connect 2) (after some bit twiddling) to look up which box-drawing character to place.

```
ＷＳ⊞υι≔⪫υ⸿θＰθ

```

Read the grid and write it to the canvas without moving the cursor.

```
Ｆθ

```

Loop over the grid again.

```
¿⁼.ι

```

If this is a placeholder, then...

```
§η⊖⍘⭆⪪⭆ＫＶ﹪÷⊕⌕ηκＸ²λ²¦²⮌κ²

```

... overwrite it with the result of looking up the adjacencies of connecting box-drawing characters in the table. The characters are checked in the order above, right, below, left, so the table is designed so that characters that join from above are in odd 1-indexed positions in the table, while characters that join from the left are in the right half of the table. We then need to find the character that connects above, right, below or left as appropriate, which is normally a rotation of the bits by 2, but because of the way base conversion works in Charcoal we end up reversing the bits, which means that we need to swap each pair of bits to end up with the correct output character.

```
ι

```

Otherwise just overwrite the character with itself.

Example box-drawing character lookup:

```
╔═╗
╚.╝
 ║

```
* The character above is in position 10, which does not have bit 0 set, so the resulting first bit is `0`
* The character to the right is in position 6, which does have bit 1 set, so the resulting second bit is `1`
* The character below is in position 5, which does have bit 4 set, so the resulting third bit is `1`
* The character to the left is first seen in position 12, which does have bit 3 set, so the resulting fourth bit is `1`
* The first and last pairs of bits are then exchanged resulting in `1011`
* The eleventh character in the table is  so this is the resulting output.

# Answer
> 2 votes
# JavaScript (ES6), 144 bytes

Expects and returns a matrix of characters. Uses `01234567` instead of  `═║.╔╗╚╝`.

```
m=>m.map((r,y)=>r.map((v,x)=>v-3?v:(a=r[x-1]==1,b=r[x+1]==1,c=y&&m[y-1][x]>1,d=(m[y+1]||0)[x]>1,a+b+c+d>2?(a=a*b?0:a,c*d?0:c):c)*6+a+b*8+d*4&7))

```

Try it online!

---
Tags: code-golf, ascii-art, grid
---