# Question
Title: Take It or Leave It: A Game Show for Computers
**Context:**

> A reclusive billionaire has created a game show to attract the world's best and brightest programmers. On Mondays at the stroke of midnight, he chooses one person from a pool of applicants to be the contestant of the week, and provides them with a game. You are this week's lucky contestant!

**This week's game:**

> The host provides you with API access to a stack of 10,000 digital envelopes. These envelopes are randomly sorted, and contain within them a dollar value, between $1 and $10,000 (no two envelopes contain the same dollar value).
>
> You have 3 commands at your disposal:
>
> 1. Read(): Read the dollar figure in the envelope at the top of the stack.
> 2. Take(): Add the dollar figure in the envelope to your game show wallet, and pop the envelope off the stack.
> 3. Pass(): Pop off the envelope on the top of the stack.

**The Rules:**

> 1. If you use Pass() on an envelope, the money within is lost forever.
> 2. If you use Take() on an envelope containing $X, from that point forward, you may never use Take() on an envelope containing \< $X. Take() on one of these envelopes will add $0 to your wallet.

Write an algorithm that finishes the game with the maximal amount of money.

If you're writing a solution in Python, feel free to use this controller to test out algorithms, courtesy of @Maltysen: https://gist.github.com/Maltysen/5a4a33691cd603e9aeca

If you use the controller, you cannot access globals, you can only use the 3 provided API commands, and local scoped variables. (@Beta Decay)

Notes: "Maximal" in this case means the median value in your wallet after N \> 50 runs. I expect, though I would love to be proven wrong, that the median value for a given algorithm will converge as N increases to infinity. Feel free to try to maximize the mean instead, but I have a feeling that the mean is more likely to be thrown off by a small N than the median is.

Edit: changed the number of envelopes to 10k for easier processing, and made Take() more explicit.

Edit 2: The prize condition has been removed, in light of this post on meta.

Current high scores:

PhiNotPi - $805,479

Reto Koradi - $803,960

Dennis - $770,272 (Revised)

Alex L. - $714,962 (Revised)

# Answer
# CJam, ~~$87,143~~ ~~$700,424~~ ~~$720,327~~ ~~$727,580~~ $770,272

```
{0:T:M;1e4:E,:)mr{RM>{RR(*MM)*-E0.032*220+R*<{ERM--:E;R:MT+:T;}{E(:E;}?}&}fRT}
[easi*]$easi2/=N

```

This program simulates the entire game multiple times and calculates the median.

### How to run

I've scored my submission by doing 100,001 test runs:

```
$ time java -jar cjam-0.6.5.jar take-it-or-leave-it.cjam 100001
770272

real    5m7.721s
user    5m15.334s
sys     0m0.570s

```

### Approach

For each envelope, we do the following:

* *Estimate* the amount of money that will inevitably be lost by taking the envelope.

If **R** is the content and **M** is the maximum that has been taken, the amount can be estimated as **R(R-1)/2 - M(M+1)/2**, which gives the money all envelopes with contents **X** in the interval **(M,R)** contain.

If no envelopes had been passed yet, the estimation would be perfect.
* Calculate the amount of money that will inevitably be lost by passing the envelope.

This is simply the money the envelope contains.
* Check if the quotient of both is less than **110 + 0.016E**, where **E** is the number of remaining envelopes (not counting envelopes that cannot be taken anymore).

If so, take. Otherwise, pass.
> 9 votes

# Answer
## Python, ~~$680,646~~ $714,962

```
f = (float(len(stack)) / 10000)
step = 160
if f<0.5: step = 125
if f>0.9: step = 190
if read() < max_taken + step:
    take()
else:
    passe()

```

Takes larger and larger amounts in steps of size between $125 and $190. Ran with N=10,000 and got a median of $714962. These step sizes came from trial and error and are certainly not optimal.

The full code, including a modified version of @Maltysen's controller which prints a bar chart while it runs:

```
import random
N = 10000

def init_game():
    global stack, wallet, max_taken
    stack = list(range(1, 10001))
    random.shuffle(stack)
    wallet = max_taken = 0

def read():
    return stack[0]

def take():
    global wallet, max_taken
    amount = stack.pop(0)
    if amount > max_taken:
        wallet += amount
        max_taken = amount

def passe():
    stack.pop(0)

def test(algo):
    results = []
    for _ in range(N):
        init_game()
        for i in range(10000):
            algo()
        results += [wallet]
        output(wallet)
    import numpy
    print 'max: '
    output(max(results))
    print 'median: '
    output(numpy.median(results))
    print 'min: '
    output(min(results))

def output(n):
    print n
    result = ''
    for _ in range(int(n/20000)):
        result += '-'
    print result+'|'

def alg():
    f = (float(len(stack)) / 10000)
    step = 160
    if f<0.5: step = 125
    if f>0.9: step = 190
    if read() < max_taken + step:
        #if read()>max_taken: print read(), step, f
        take()
    else:
        passe()

test(alg)

```

BitCoin address: 1CBzYPCFFBW1FX9sBTmNYUJyMxMcmL4BZ7

**Wow OP delivered! Thanks @LivingInformation!**
> 7 votes

# Answer
# C++, $803,960

```
for (int iVal = 0; iVal < 10000; ++iVal)
{
    int val = game.read();
    if (val > maxVal &&
        val < 466.7f + 0.9352f * maxVal + 0.0275f * iVal)
    {
        maxVal = val;
        game.take();
    }
    else
    {
        game.pass();
    }
}

```

Reported result is the median from 10,001 games.
> 5 votes

# Answer
# Java, $806,899

This is from a trial of 2501 rounds. I am still working on optimizing it. I wrote two classes, a wrapper and a player. The wrapper instantiates the player with the number of envelopes (always 10000 for the real thing), and then calls the method `takeQ` with the top envelope's value. The player then returns `true` if they take it, `false` if they pass it.

## Player

```
import java.lang.Math;

public class Player {
  public int[] V;

  public Player(int s) {
    V = new int[s];
    for (int i = 0; i < V.length; i++) {
      V[i] = i + 1;
    }
    // System.out.println();
  }

  public boolean takeQ(int x) {

    // System.out.println("look " + x);

    // http://www.programmingsimplified.com/java/source-code/java-program-for-binary-search
    int first = 0;
    int last = V.length - 1;
    int middle = (first + last) / 2;
    int search = x;

    while (first <= last) {
      if (V[middle] < search)
        first = middle + 1;
      else if (V[middle] == search)
        break;
      else
        last = middle - 1;

      middle = (first + last) / 2;
    }

    int i = middle;

    if (first > last) {
      // System.out.println(" PASS");
      return false; // value not found, so the envelope must not be in the list
                    // of acceptable ones
    }

    int[] newVp = new int[V.length - 1];
    for (int j = 0; j < i; j++) {
      newVp[j] = V[j];
    }
    for (int j = i + 1; j < V.length; j++) {
      newVp[j - 1] = V[j];
    }
    double pass = calcVal(newVp);
    int[] newVt = new int[V.length - i - 1];
    for (int j = i + 1; j < V.length; j++) {
      newVt[j - i - 1] = V[j];
    }
    double take = V[i] + calcVal(newVt);
    // System.out.println(" take " + take);
    // System.out.println(" pass " + pass);

    if (take > pass) {
      V = newVt;
      // System.out.println(" TAKE");
      return true;
    } else {
      V = newVp;
      // System.out.println(" PASS");
      return false;
    }
  }

  public double calcVal(int[] list) {
    double total = 0;
    for (int i : list) {
      total += i;
    }
    double ent = 0;
    for (int i : list) {
      if (i > 0) {
        ent -= i / total * Math.log(i / total);
      }
    }
    // System.out.println(" total " + total);
    // System.out.println(" entro " + Math.exp(ent));
    // System.out.println(" count " + list.length);
    return total * (Math.pow(Math.exp(ent), -0.5) * 4.0 / 3);
  }
}

```

## Wrapper

```
import java.lang.Math;
import java.util.Random;
import java.util.ArrayList;
import java.util.Collections;

public class Controller {
  public static void main(String[] args) {
    int size = 10000;
    int rounds = 2501;
    ArrayList<Integer> results = new ArrayList<Integer>();
    int[] envelopes = new int[size];
    for (int i = 0; i < envelopes.length; i++) {
      envelopes[i] = i + 1;
    }
    for (int round = 0; round < rounds; round++) {
      shuffleArray(envelopes);

      Player p = new Player(size);
      int cutoff = 0;
      int winnings = 0;
      for (int i = 0; i < envelopes.length; i++) {
        boolean take = p.takeQ(envelopes[i]);
        if (take && envelopes[i] >= cutoff) {
          winnings += envelopes[i];
          cutoff = envelopes[i];
        }
      }
      results.add(winnings);
    }
    Collections.sort(results);
    System.out.println(
        rounds + " rounds, median is " + results.get(results.size() / 2));
  }

  // stol... I mean borrowed from
  // http://stackoverflow.com/questions/1519736/random-shuffling-of-an-array
  static Random rnd = new Random();

  static void shuffleArray(int[] ar) {
    for (int i = ar.length - 1; i > 0; i--) {
      int index = rnd.nextInt(i + 1);
      // Simple swap
      int a = ar[index];
      ar[index] = ar[i];
      ar[i] = a;
    }
  }
}

```

A more detailed explanation is coming soon, after I finish optimizations.

The core idea is to be able to estimate the reward from playing a game from a given set of envelopes. If the current set of envelopes is {2,4,5,7,8,9}, and the top envelope is the 5, then there are two possibilities:

* Take the 5 and play a game with {7,8,9}
* Pass the 5 and play a game of {2,4,7,8,9}

If we calculate the expected reward of {7,8,9} and compare it to the expected reward of {2,4,7,8,9}, we will be able to tell if taking the 5 is worth it.

Now the question is, given a set of envelopes like {2,4,7,8,9} what is the expected value? I found the the expected value seems to be proportional to the total amount of money in the set, but inversely proportional to the square root of the number of envelopes that the money is divided into. This came from "perfectly" playing several small games in which all of the envelopes have almost identical value.

The next problem is how to determine the "*effective* number of envelopes." In all cases, the number of envelopes is known exactly by keeping track of what you've seen and done. Something like {234,235,236} is definitely three envelopes, {231,232,233,234,235} is definitely 5, but {1,2,234,235,236} should really count as 3 and not 5 envelopes because the 1 and 2 are nearly worthless, and you would never PASS on a 234 so you could later pick up a 1 or 2. I had the idea of using Shannon entropy to determine the effective number of envelopes.

I targeted my calculations to situations where the envelope's values are uniformly distributed over some interval, which is what happens during the game. If I take {2,4,7,8,9} and treat that as a probability distribution, its entropy is 1.50242. Then I do `exp()` to get 4.49254 as the effective number of envelopes.

The estimated reward from {2,4,7,8,9} is `30 * 4.4925^-0.5 * 4/3 = 18.87`

The exact number is `18.1167`.

This isn't an exact estimate, but I am actually really proud of how well this fits the data when the envelopes are uniformly distributed over an interval. I'm not sure of the correct multiplier (I am using 4/3 for now) but here is a data table excluding the multiplier.

```
Set of Envelopes                    Total * (e^entropy)^-0.5      Actual Score

{1,2,3,4,5,6,7,8,9,10}              18.759                        25.473
{2,3,4,5,6,7,8,9,10,11}             21.657                        29.279
{3,4,5,6,7,8,9,10,11,12}            24.648                        33.125
{4,5,6,7,8,9,10,11,12,13}           27.687                        37.002
{5,6,7,8,9,10,11,12,13,14}          30.757                        40.945
{6,7,8,9,10,11,12,13,14,15}         33.846                        44.900
{7,8,9,10,11,12,13,14,15,16}        36.949                        48.871
{8,9,10,11,12,13,14,15,16,17}       40.062                        52.857
{9,10,11,12,13,14,15,16,17,18}      43.183                        56.848
{10,11,12,13,14,15,16,17,18,19}     46.311                        60.857

```

Linear regression between expected and actual gives an **R^2 value of 0.999994**.

My next step to improve this answer is to improve estimation when the number of envelopes starts to get small, which is when the envelopes are not approximately uniformly distributed and when the problem starts to get granular.

---

Edit: If this is deemed worthy of bitcoins, I just got an address at `1PZ65cXxUEEcGwd7E8i7g6qmvLDGqZ5JWg`. Thanks! (This was here from when the challenge author was handing out prizes.)
> 3 votes

# Answer
# C++, ~$815,000

Based on Reto Koradi's solution, but switches to a more sophisticated algorithm once there's 100 (valid) envelopes left, shuffling random permutations and computing the heaviest increasing subsequence of them. It will compare the results of taking and not taking the envelope, and will greedily select the best choice.

```
#include <algorithm>
#include <iostream>
#include <vector>
#include <set>

void setmax(std::vector<int>& h, int i, int v) {
    while (i < h.size()) { h[i] = std::max(v, h[i]); i |= i + 1; }
}

int getmax(std::vector<int>& h, int n) {
    int m = 0;
    while (n > 0) { m = std::max(m, h[n-1]); n &= n - 1; }
    return m;
}

int his(const std::vector<int>& l, const std::vector<int>& rank) {
    std::vector<int> h(l.size());
    for (int i = 0; i < l.size(); ++i) {
        int r = rank[i];
        setmax(h, r, l[i] + getmax(h, r));
    }

    return getmax(h, l.size());
}

template<class RNG>
void shuffle(std::vector<int>& l, std::vector<int>& rank, RNG& rng) {
    for (int i = l.size() - 1; i > 0; --i) {
        int j = std::uniform_int_distribution<int>(0, i)(rng);
        std::swap(l[i], l[j]);
        std::swap(rank[i], rank[j]);
    }
}

std::random_device rnd;
std::mt19937_64 rng(rnd());

struct Algo {
    Algo(int N) {
        for (int i = 1; i < N + 1; ++i) left.insert(i);
        ival = maxval = 0;
    }

    static double get_p(int n) { return 1.2 / std::sqrt(8 + n) + 0.71; }

    bool should_take(int val) {
        ival++;
        auto it = left.find(val);
        if (it == left.end()) return false;

        if (left.size() > 100) {
            if (val > maxval && val < 466.7f + 0.9352f * maxval + 0.0275f * (ival - 1)) {
                maxval = val;
                left.erase(left.begin(), std::next(it));
                return true;
            }

            left.erase(it);
            return false;
        }

        take.assign(std::next(it), left.end());
        no_take.assign(left.begin(), it);
        no_take.insert(no_take.end(), std::next(it), left.end());
        take_rank.resize(take.size());
        no_take_rank.resize(no_take.size());
        for (int i = 0; i < take.size(); ++i) take_rank[i] = i;
        for (int i = 0; i < no_take.size(); ++i) no_take_rank[i] = i;

        double take_score, no_take_score;
        take_score = no_take_score = 0;
        for (int i = 0; i < 1000; ++i) {
            shuffle(take, take_rank, rng);
            shuffle(no_take, no_take_rank, rng);
            take_score += val + his(take, take_rank) * get_p(take.size());
            no_take_score += his(no_take, no_take_rank) * get_p(no_take.size());
        }

        if (take_score > no_take_score) {
            left.erase(left.begin(), std::next(it));
            return true;
        }

        left.erase(it);
        return false;
    }

    std::set<int> left;
    int ival, maxval;
    std::vector<int> take, no_take, take_rank, no_take_rank;
};

struct Game {
    Game(int N) : score_(0), max_taken(0) {
        for (int i = 1; i < N + 1; ++i) envelopes.push_back(i);
        std::shuffle(envelopes.begin(), envelopes.end(), rng);
    }

    int read() { return envelopes.back(); }
    bool done() { return envelopes.empty(); }
    int score() { return score_; }
    void pass() { envelopes.pop_back(); }

    void take() {
        if (read() > max_taken) {
            score_ += read();
            max_taken = read();
        }
        envelopes.pop_back();
    }

    int score_;
    int max_taken;
    std::vector<int> envelopes;
};

int main(int argc, char** argv) {
    std::vector<int> results;
    std::vector<int> max_results;
    int N = 10000;
    for (int i = 0; i < 1000; ++i) {
        std::cout << "Simulating game " << (i+1) << ".\n";
        Game game(N);
        Algo algo(N);

        while (!game.done()) {
            if (algo.should_take(game.read())) game.take();
            else game.pass();
        }
        results.push_back(game.score());
    }

    std::sort(results.begin(), results.end());
    std::cout << results[results.size()/2] << "\n";

    return 0;
}

```
> 3 votes

---
Tags: code-challenge, game, stack
---


# Question
Title: Print out the Smallest Perfect Squared Square
*Squaring the Square* is a process of tiling a square using only other squares. If this tiling only uses squares of different sizes, then it is considered to be *perfect*. The smallest possible perfect squared square is a 112x112 square tiled using 21 different squares.

I have created the ascii art version of this square below:

```
################################################################################################################
#                                                ##                                 ##                         #
#                                                ##                                 ##                         #
#                                                ##                                 ##                         #
#                                                ##                                 ##                         #
#                                                ##                                 ##                         #
#                                                ##                                 ##                         #
#                                                ##                                 ##                         #
#                                                ##                                 ##                         #
#                                                ##                                 ##                         #
#                                                ##                                 ##                         #
#                                                ##                                 ##                         #
#                                                ##                                 ##                         #
#                                                ##                                 ##                         #
#                                                ##                                 ##                         #
#                                                ##                                 ##                         #
#                                                ##                                 ##                         #
#                                                ##                                 ##                         #
#                                                ##                                 ##                         #
#                                                ##                                 ##                         #
#                                                ##                                 ##                         #
#                                                ##                                 ##                         #
#                                                ##                                 ##                         #
#                                                ##                                 ##                         #
#                                                ##                                 ##                         #
#                                                ##                                 ##                         #
#                                                ##                                 ############################
#                                                ##                                 ############################
#                                                ##                                 ##      ##                 #
#                                                ##                                 ##      ##                 #
#                                                ##                                 ##      ##                 #
#                                                ##                                 ##      ##                 #
#                                                ##                                 ##      ##                 #
#                                                ##                                 ##      ##                 #
#                                                #############################################                 #
#                                                #############################################                 #
#                                                ##             ##               ##         ##                 #
#                                                ##             ##               ##         ##                 #
#                                                ##             ##               ##         ##                 #
#                                                ##             ##               ##         ##                 #
#                                                ##             ##               ##         ##                 #
#                                                ##             ##               ##         ##                 #
#                                                ##             ##               ##         ##                 #
#                                                ##             ##               ##         ##                 #
#                                                ##             ##               ##         ##                 #
#                                                ##             ##               ###############################
#                                                ##             ##               ###############################
#                                                ##             ##               ##    ##                      #
#                                                ##             ##               ##    ##                      #
##################################################################               ##    ##                      #
##################################################################               ##    ##                      #
#                           ##                       ##       ###########################                      #
#                           ##                       ##       ###########################                      #
#                           ##                       ##       ##     ##                ##                      #
#                           ##                       ##       ##     ##                ##                      #
#                           ##                       ##       ##     ##                ##                      #
#                           ##                       ##       ##     ##                ##                      #
#                           ##                       ##       ##     ##                ##                      #
#                           ##                       ##################                ##                      #
#                           ##                       ##################                ##                      #
#                           ##                       ##              ##                ##                      #
#                           ##                       ##              ##                ##                      #
#                           ##                       ##              ##                ##                      #
#                           ##                       ##              ##                ##                      #
#                           ##                       ##              ##                ##                      #
#                           ##                       ##              ##                ##                      #
#                           ##                       ##              ##                ##                      #
#                           ##                       ##              ##                ##                      #
#                           ##                       ##              ##                ##                      #
#                           ##                       ##              ###########################################
#                           ##                       ##              ###########################################
#                           ##                       ##              ##                                        #
#                           ##                       ##              ##                                        #
#                           ##                       ##              ##                                        #
#                           ###########################################                                        #
#                           ###########################################                                        #
#                           ##  ##                                   ##                                        #
#                           ##  ##                                   ##                                        #
##################################                                   ##                                        #
##################################                                   ##                                        #
#                               ##                                   ##                                        #
#                               ##                                   ##                                        #
#                               ##                                   ##                                        #
#                               ##                                   ##                                        #
#                               ##                                   ##                                        #
#                               ##                                   ##                                        #
#                               ##                                   ##                                        #
#                               ##                                   ##                                        #
#                               ##                                   ##                                        #
#                               ##                                   ##                                        #
#                               ##                                   ##                                        #
#                               ##                                   ##                                        #
#                               ##                                   ##                                        #
#                               ##                                   ##                                        #
#                               ##                                   ##                                        #
#                               ##                                   ##                                        #
#                               ##                                   ##                                        #
#                               ##                                   ##                                        #
#                               ##                                   ##                                        #
#                               ##                                   ##                                        #
#                               ##                                   ##                                        #
#                               ##                                   ##                                        #
#                               ##                                   ##                                        #
#                               ##                                   ##                                        #
#                               ##                                   ##                                        #
#                               ##                                   ##                                        #
#                               ##                                   ##                                        #
#                               ##                                   ##                                        #
#                               ##                                   ##                                        #
#                               ##                                   ##                                        #
#                               ##                                   ##                                        #
################################################################################################################

```

Your submission should print out the above square. You may print a reflection and/or rotation of the above square if you wish. A trailing newline on the last line is allowed. This is a , so the smallest submission wins!

# Answer
> 4 votes
# CJam, ~~88~~ ~~84~~ 83 bytes

```
'p:Ci_C*a*"2#   *%!"{i_S*a*{3af.|W%z}4*1$0=C#C*f{\+}..e<{_C&{oNo}|}%}/

```

Test it here.

## Explanation

Here is the basic idea: start with an "empty" 112x112 square. Now go through the squares in reading order (left to right, top to bottom). Add each square into the first available position. Afterwards, print all completed lines - this ensures that we only need to check the first (remaining) line to figure out where the next square goes.

The empty grid is initialised to `p`s, because I needed a character with character code larger than space and `#`, and because I could reuse its own character code `112` for the size of the initial grid. I made use of some of Dennis's ASCII art tricks here to fill the small squares into the grid.

```
'p:C        e# Store the character 'p' in C.
i           e# Convert to its character code 112.
_C*a*       e# Generate a 112x112 array of p's.
"2#   *%!"  e# The 21 characters in this string correspond to the side lengths of
            e# the squares in the solution in reading order.
{           e# For each character in that string...
  i         e#   Convert to its character code (the current square's side length N).
  _S*a*     e#   Generate an NxN array of spaces.
  {         e#   Run this block 4 times. Each iteration turns the leading column into #'s
            e#   and then rotates the square by 90 degrees.
    3af.|   e#     For the first character in each row, take the bitwise OR with 3.
            e#     This turns spaces into #'s and leaves #'s unchanged.
    W%z     e#     Reverse and transpose, which rotates by 90 degrees.
  }4*
  1$0=      e#   Copy the remaining grid and fetch the top row.
  C#        e#   Find the index of the first 'p'.
  C*        e#   Get a string of that many p's.
  f{\+}     e#   Prepend this string to each row of the small square, which gives the
            e#   square the correct horizontal position.
  ..e<      e#   Take the pairwise minimum of the square and the remaining grid. The p's
            e#   prepended to the square will leave the grid unchanged, but the spaces
            e#   and #'s in the square will overwrite the p's in the grid.
  {         e#   Map this block onto each row of the grid.
    _C&     e#     Copy the row and check if any p's are left.
    {oNo}|  e#     If NOT, the row is complete and we print it together with a newline.
            e#     This also removes the row from the grid, such that the top row for
            e#     the next iteration will have space for the next square left.
  }%
}/

```

# Answer
> 9 votes
# Mathematica ~~360~~ 426

The code works by first drawing the perfect square of squares, rasterising and binarizing the image, and then converting 0 to "#" and 1 to " ".

The output is returned as ordinary ASCII characters in a table.

```
f@{n_,x_,y_}:=Rectangle[{x,y},{x+n,y+n}];t=Transpose;
Flatten[i=Rasterize[Graphics[{EdgeForm[{(*Thickness[.015],*)Black}],White,
f/@ Partition[{33,0,0,29,0,33,50,0,62,37,33,0,25,29,37,42,70,0,18,70,42,24,88,42,9,54,53,7,63,53,15,50,62,17,65,60,
11,82,66,19,93,66,35,50,77,27,85,85},3]
},ImageSize->70
],RasterSize->70]//Binarize//ImageData,1]/.{0:> "#",1:> " "};
GraphicsGrid@t@Most@Most@Rest@t[Most@Most[Rest[ArrayReshape[%,Dimensions[i]]]]]

```

---

I prefer this rendering, obtained by deleting `Thickness[.015]`

# Answer
> 3 votes
# Ruby, 180 bytes

Golfed version based on the ungolfed version below. We take advantage of the fact that there are typically 2 or 3 squares with the same `y` coordinate for the top left corner.

The first magic string contains ASCII codes for the `square sidelength+70` and `y increment +40`. When encountering a square sidelength (Ascii code \>67) we assume the next square is at the same y coordinate, and the x coordinate can be obtained by incrementing the current x coordinate by `sidelength+2`. When encountering a y increment (Ascii code\<67) we increment the y coordinate accordingly and reset the x coordinate to the figure encoded in the second magic string.

```
a=Array.new(112){?#*112}
x=y=1
j=9
'vg_CLW0SUO3J\,a]M*KV/T3n-Hi,e'.each_byte{|i|i>67?(s=i-70;(y..y+s-1).map{|i|a[i][x,s]=" "*s};x+=s+2):(x=')Fo_h){[~'[j-=1].ord-40;y+=i-40)}
puts a

```

**Original version**

This (completely ungolfed) solution contains 315 bytes, excluding unnecessary blank lines and indents. It simply creates an array of 112 strings of 112 `#`'s then replaces the insides of the squares with spaces.

```
$a=Array.new(112){"#"*112}
def f(x,y,s)
  (y..y+s-1).map{|i|$a[i][x,s]=" "*s}
end

f(1,1,48)
f(51,1,33)
f(86,1,25)

f(86,28,6)
f(94,28,17)

f(51,36,13)
f(66,36,15)
f(83,36,9)

f(83,47,4)
f(89,47,22)

f(1,51,27)
f(30,51,23)
f(55,51,7)

f(64,53,5)
f(71,53,16)

f(55,60,14)

f(71,71,40)

f(30,76,2)
f(34,76,35)

f(1,80,31)

puts $a

```

# Answer
> 3 votes
# R, ~~293~~ ~~291~~ ~~287~~ 282 bytes

```
a=array('#',112:113)
a[,113]='
'
for(g in list(c(0,0,49,34,26),c(27,85,7,18),c(35,50,14,16,10),c(46,82,5,23),c(50,0,28,24,8,1),c(52,63,6,17),c(59,54,15),c(70,70,41),c(75,29,3,36),c(79,0,32))){y=g[1];x=g[2]
for(b in g[0:1-2]){a[(y+2):(y+b),(x+2):(x+b)]=' '
x=x+b+1}}
cat(t(a),sep='')

```

After I did this, I realized I had done almost the identical process as @steveverrill. An array of '#' and blank the square interiors. Can probably squeeze some more out of this. The carriage return for the 3rd line is significant. Thanks to AlexA for a few.

# Answer
> 3 votes
# C, 198 bytes

```
char*i="bSK8C?A;6HMI927B@Z4UQ",o[112][113],x,y,p,q,n;main(){for(;y<112;puts(o[y]),y++)for(x=-1;++x<112;)if(!o[y][x]){n=*i++-48;for(p=-1;++p<n;)for(q=-1;++q<n;)o[q+y][p+x]=p&&n-1-p&&q&&n-1-q?32:35;}}

```

### (Ungolfed)

```
char *i="bSK8C?A;6HMI927B@Z4UQ", o[112][113], x, y, p, q, n;
main() {
  for ( ; y<112; puts(o[y]),y++) {
    for (x=-1; ++x<112; ) {
      if (!o[y][x]) {
        n = *i++ - 48;
        for (p=-1; ++p<n; ) {
          for(q=-1; ++q<n; ) {
            o[q+y][p+x] = (p && n-1-p && q && n-1-q) ? ' ' : '#';
          }
        }
      }
    }
  }
}

```

All this does is scan through an array of 112×112 bytes (initialized to zero). Whenever it encounters a zero byte, it fetches a value from array `i` and adds a box of the corresponding size. The extra byte in each row acts as a string terminator so we can use `puts()` to output entire lines instead of using `putchar()` to output characters individually.

This can probably be golfed a little more, but I don't think it stands much chance of beating steveverrill's answer.

(ideone link)

# Answer
> 2 votes
# MS-DOS Binary, 137

The following code will run in MS-DOS if you write it into a file called square.com, no further compilation required (but since it's given in hex, you need to "unhex" it first):

```
fcba8f01b82370e83000bd1400bb4d018b1743438a27b02043e81e004d75
f1b97000ba8f3289d7b00daab00aaab82409aa83ea70cd214975ecc331c9
88e189ce89d788e1f3aa83c2704e75f4c3201d30e223218527190524063d
1f11521d0d811c0f321f09921c04b8141670101b4d12176619076f1905a6
141066120e4602288d100221022300021f

```

The output will be unrecognisable in most terminals, but you can redirect it to a file (`square.com > output.txt`) and look at it in an text editor. If you want something more readable, the following code will produce a working square.com if fed into debug.exe (`debug.exe < square.asm`):

```
a
cld
mov dx,18f
mov ax,7023
call 13a
mov bp,14
mov bx,14d
mov dx,[bx]
inc bx
inc bx
mov ah,[bx]
mov al,20
inc bx
call 13a
dec bp
jnz 110
mov cx,70
mov dx,328f
mov di,dx
mov al,d
stosb
mov al,a
stosb
mov ax,924
stosb
sub dx,70
int 21
dec cx
jnz 125
ret
xor cx,cx
mov cl,ah
mov si,cx
mov di,dx
mov cl,ah
rep stosb
add dx,70
dec si
jnz 140
ret
db 20,1d,30,e2,23,21
db 85,27,19,05,24,6
db 3d,1f,11,52,1d,d
db 81,1c,f,32,1f,9
db 92,1c,4,b8,14,16
db 70,10,1b,4d,12,17
db 66,19,7,6f,19,5
db a6,14,10,66,12,e
db 46,02,28,8d,10,2
db 21,02,23,00,02,1f

n square.com
rcx
89
w
q

```

# Answer
> 1 votes
# Matlab/Octave, 258

As always, Matrices. I hardcoded the row and the column indices of each square ans well as the size. I can use these to fill up a big 'blank' square of `#`s.

```
r=[2,2,2,29,29,37,37,37,48,48,52,52,52,54,54,61,72,77,77,81];
c=[2,52,87,87,95,52,67,84,84,90,2,31,56,65,72,56,72,31,35,2];
s=[47,32,24,5,16,12,14,8,3,21,26,22,6,4,15,13,39,1,34,30];
z=ones(112)*35;
for i=1:20;
    z(r(i)+(0:s(i)),c(i)+(0:s(i)))=32;
end;disp([z,''])

```

# Answer
> 0 votes
# Bash, 252

Every codegolfer should be able to beat a general purpose compression algorithm:

```
base64 -d<<<H4sIADyFv1UCA+3ZOw6EMAwFwH5PgeT735EOUSyfQAgOmVeCxUgusAkRbfOLqTARd0qAQCAQCAQCgcAvg80375dW/T+lQGAbsCCdgvsdXl0AAoHjgM8e7mUA92bKG+DtpAevDPflRsko7BXcKAQCD9+X3wOPCoFA4ABgnZ/OmcHTS+bw4PXzkV7Ak93KDdboVm6wxrOAQCAQCAQCgUAgENj++7BuZsq8xQ1vMQAA|gunzip

```

Thanks to Toby Speight for the hint to use shorter input (silly me used `gzip` instead of `gzip -9` for compression) and a here-string.

---
Tags: code-golf, kolmogorov-complexity
---


title: Shortest Minmod Function

text:
# Question
Title: Shortest Minmod Function
The **minmod** function is a variant of the familiar **min**, which appears in slope-limiting high-resolution schemes for partial differential equations. Given a number of slopes, it picks out the flattest slope, while taking care of relative signs between the slopes.

The function takes an arbitrary number of parameters. Then *minmod(x1, x2, ..., xn)* is defined as:

* *min(x1, x2, ..., xn)*, if all xi are strictly positive
* *max(x1, x2, ..., xn)*, if all xi are strictly negative
* *0*, otherwise.

We'll only consider integer inputs, because that does not really affect the implementation and should be more inclusive for some (esoteric) languages.

Write a program or function, which takes *n* signed integers (for *n \> 0*) via STDIN, ARGV or function argument (you can use an array if that's more convenient than a variadic function), and returns or prints (to STDOUT) the result of *minmod(a,b)*.

You must not use built-in *min* or *max* functions (and obviously, no built-in *minmod* either, if you can actually find that). In addition, you must not use any built-in sorting functions, *except* to sort a *fixed* small number of items (less than 5).

If your language doesn't have signed types, you may use an unsigned type and *interpret* it as two's complement. E.g. if your language only uses unsigned bytes, you can use `255` to stand in for `-1` and `128` to stand in for `-128`, etc.

This is code golf, so the shortest answer (in bytes) wins.

# Test Cases

```
Input          Output

2              2
-3             -3
0              0
3 -5           0
2 4 1          1
0 1 2          0
-1 1 2         0
-4 -2 -3 -2    -2
-5 0 -1        0
1 0 -1         0

```

# Leaderboards

The following Stack Snippet generates both a regular leaderboard and an overview of winners by language. So even if your language of choice doesn't let you win the entire challenge, why not try to snatch a spot on the second list?

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

```
# Language Name, N bytes

```

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

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

```

```
function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function getAnswers(){$.ajax({url:answersUrl(page++),method:"get",dataType:"jsonp",crossDomain:true,success:function(e){answers.push.apply(answers,e.items);if(e.has_more)getAnswers();else process()}})}function shouldHaveHeading(e){var t=false;var n=e.body_markdown.split("\n");try{t|=/^#/.test(e.body_markdown);t|=["-","="].indexOf(n[1][0])>-1;t&=LANGUAGE_REG.test(e.body_markdown)}catch(r){}return t}function shouldHaveScore(e){var t=false;try{t|=SIZE_REG.test(e.body_markdown.split("\n")[0])}catch(n){}return t}function getAuthorName(e){return e.owner.display_name}function process(){answers=answers.filter(shouldHaveScore).filter(shouldHaveHeading);answers.sort(function(e,t){var n=+(e.body_markdown.split("\n")[0].match(SIZE_REG)||[Infinity])[0],r=+(t.body_markdown.split("\n")[0].match(SIZE_REG)||[Infinity])[0];return n-r});var e={};var t=1;answers.forEach(function(n){var r=n.body_markdown.split("\n")[0];var i=$("#answer-template").html();var s=r.match(NUMBER_REG)[0];var o=(r.match(SIZE_REG)||[0])[0];var u=r.match(LANGUAGE_REG)[1];var a=getAuthorName(n);i=i.replace("{{PLACE}}",t++ +".").replace("{{NAME}}",a).replace("{{LANGUAGE}}",u).replace("{{SIZE}}",o).replace("{{LINK}}",n.share_link);i=$(i);$("#answers").append(i);e[u]=e[u]||{lang:u,user:a,size:o,link:n.share_link}});var n=[];for(var r in e)if(e.hasOwnProperty(r))n.push(e[r]);n.sort(function(e,t){if(e.lang>t.lang)return 1;if(e.lang<t.lang)return-1;return 0});for(var i=0;i<n.length;++i){var s=$("#language-template").html();var r=n[i];s=s.replace("{{LANGUAGE}}",r.lang).replace("{{NAME}}",r.user).replace("{{SIZE}}",r.size).replace("{{LINK}}",r.link);s=$(s);$("#languages").append(s)}}var QUESTION_ID=42079;var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";var answers=[],page=1;getAnswers();var SIZE_REG=/\d+(?=[^\d&]*(?:<(?:s>[^&]*<\/s>|[^&]+>)[^\d&]*)*$)/;var NUMBER_REG=/\d+/;var LANGUAGE_REG=/^#*\s*([^,]+)/
```

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

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

# Answer
## GolfScript, 10 9 bytes

```
~{0]$1=}*

```

Assumes input from stdin in the format `[-4 -2 -3 -2]`

This uses the built-in sort function `$`, but every time it's invoked it's on an array of 3 elements, which is permitted.

Online demo
> 13 votes

# Answer
## Mathematica, 19 bytes

```
Median[#~Riffle~0]&

```

Code and golfing thanks to Martin Büttner.

This is an unnamed pure function that takes in a list of integers as input. Invoke it like

```
Median[#~Riffle~0]&[{-2, -3, -2, -4}]

```

or similarly saved to variable.

The code first riffles a zero in between every two elements of the input list, which inserts `n-1` zeroes among `n` elements. Then, it takes the median to produce the answer.

This gives min-mod because it handles each case:

1. All the numbers are positive, in which case the zeroes are below them and the median is the lowest positive number.
2. All the numbers are negative, in which case the zeroes are above them and the median is the least negative number.
3. There's both a positive and negative number, and so the middle element is a zero.

If Mathematica implements its median using the linear-time selection algorithm, then this is also O(n).
> 24 votes

# Answer
# Haskell, ~~62~~ ~~61~~ ~~39~~ ~~38~~ 37 bytes

```
f s=last[x|x<-0:s,and[x*x<=x*y|y<-s]]

```

using some comparison magic borrowed from @Zgarb's answer\* , namely, `x*x<=x*y`.

`x*x<=x*y` is true only when `x` and `y` have the same sign and `y`'s absolute value is bigger. note that when `x` is `0` it is always true.

we determine that `x` is the result iff it is contained in `s`, and that for all `y` in `s` `x` has the same sign as `y` and is smaller in absolute value. if no value in `s` satisfies this definition, then `0` is the result.

`f` then works by searching `s` for an element to satisfy this, and uses `0` as a default.

\*though he didn't use it for the reasons I'm using it, and he actually got rid of it by now
> 11 votes

# Answer
# JavaScript (ES6), 39 bytes

```
a=>a.reduce((p,c)=>p*c>0?p*p>c*c?c:p:0)

```
> 10 votes

# Answer
# Marbelous, 210 bytes

```
@0
00
]]\\&002
/\..//&0@0
00..02
MMMMMM//\\
:M
}0}1}0}1}0}1}0}2..}2
^7^7||||&0&1&4<3&0=2{>
EqalLteq{0{<{<<2&1--
&2..&3..}100..&2\/{>
>0&6=0&4&5&6..\/
&3..&5\/{<{0
\/..\/
:|
}000}0
&0Subt
{0&1
}0{0
^7
=0&1
&0
\/

```

There are three boards used here.

The `|` board (`Ab` in the readable version) takes the absolute value of a marble (by either returning the passed marble or zero minus the passed marble, as all arithmetic in Marbelous is unsigned).

The `M` board (`Minabs` in the readable version) finds and outputs to the left either the first or second marble passed (whichever has a smaller absolute value), and exiting if a different signed marble is passed.

The `M` board also releases the marble it holds downward instead of leftward once the last character from STDIN is fetched.

The `M` board is used in the main board to store the minmod of all checked values at any given time, as it releases the value to be saved leftward, which is then deflected back in.

Trashbins (`\/`) were only placed under synchronisers that would otherwise print to STDIN.

Input/Output uses STDIN/STDOUT. Both deal with 8-bit values (if you wanted to pass +0x30 and +0x38, place `08` into STDIN).

Libraries and cylindrical boards are both required. Viewing output as decimal numbers is recommended (note that this displays the unsigned value of the minmod result).

Test it here.

**Note:** For more human-friendly input/output, add `Dp` under the last line of the main board (before `:M`), replace `]]` with `Rd`, and add the following at the bottom:

```
:Rd
}0}0}0
]]]]]]{>
-O-O-O
-O-O-O
*A
Plus
\\*A
..Plus
..{0
:*A
}0}0
<<<<
<<
<<
Plus
{0

```

This simply changes the output to be 3 decimal digits. Likewise, input with these changes requires a space separated list of 3 decimal digits per number.

### Readable Version:
> 7 votes

# Answer
# Python 2, 53

```
lambda l:reduce(lambda a,b:sorted([a,b,0])[1],l,l[0])

```

The idea is to use `reduce` to turn the two-input min-mod finder into an `n`-input one. I came up with it independently of the other answers that use it. Only Python 2 supports `reduce`.

The two-input solution simply finds the median of the two numbers and zero. See my Mathematica answer for a more direct way to use the median.

Less golfed:

```
def f(l):
 A=l[0]
 for x in l:A=sorted([a,b,0])[1]
 return A

```

A hypothetical amalgam of Python 2 and Python 3 would be a character shorter, with the starred assignment from Python 3 and `input()` and `print` from Python 2.

```
#Not real code!
A,*l=input()
for x in l:A=sorted([A,x,0])[1]
print A

```

Old code, without sorting:

```
lambda l:reduce(lambda a,b:[a,b][a*a>b*b]*(a*b>0),l,l[0])

```
> 6 votes

# Answer
# TIS-100, ~~696~~ 526 bytes

```
@1
MOV UP ACC
SAV
ADD 999
JEZ A
SWP
MOV 1 ANY
MOV ACC ANY
JRO -7
A:MOV 12 ANY
@5
S:JRO UP
MOV UP ACC
JLZ A
JEZ B
MOV 1 DOWN
JMP B
A:MOV 7 DOWN
NEG
B:MOV 1 RIGHT
MOV ACC RIGHT
MOV ACC RIGHT
JMP S
MOV 14 DOWN
MOV 9 RIGHT
@6
MOV 999 ACC
L:JRO LEFT
SAV
SUB ANY
JGZ A
MOV ANY NIL
SWP
JMP L
A:MOV ANY ACC
JMP L
MOV ACC ANY
@9
S:JRO UP
JEZ A
SUB 1
JEZ A
JMP X
A:MOV 1 ACC
JMP S
JEZ B
SUB 2
JEZ B
X:MOV 6 ACC
JMP S
B:MOV 2 ACC
JMP S
MOV ACC ANY
@10
MOV LEFT ACC
ADD 1
JRO ACC
JRO 6
MOV UP ANY
MOV UP ACC
NEG
MOV ACC ANY
!NOP
MOV 0 ANY

```

Expects the sequence to be terminated by `-999`. TIS-100 is newer than this question, but it's not like that matters here anyway.

Node 9 keeps track of whether we're all positive, all negative or mixed. Nodes 5 and 6 work to find the minimum of the absolute value of all input numbers. Node 10 then selects the minimum, the minimum negated, or 0 depending on node 9's state.
> 6 votes

# Answer
# Haskell, ~~83~~ ~~40~~ 39 bytes

This is probably not the shortest possible Haskell solution (and certainly won't beat the others here), but it's a start. *EDIT:* Now over 50 % shorter! *EDIT2:* One byte less...

```
a#b|a*b<0=0|a*a<b*b=a|1<2=b
m=foldr1(#)

```

This is just a straightforward fold (or reduce, as some languages call it) by the binary operator `#`, which computes the median of `a`, `b` and `0`. Even though the rules would now allow me to sort small lists, this requires an import in Haskell and results in a higher byte count (**49** bytes, but **31** without the import):

```
import Data.List
a#b=sort[a,b,0]!!1
m=foldr1(#)

```
> 5 votes

# Answer
# CJam, 20 bytes (or 10 bytes)

```
q~{]__~z\z<=\~*0>*}*

```

Using @xnor's approach, reduce calculating minmod of 2 numbers at a time from the array.

*This would have been 19 bytes if `:z` worked*

---

Using the new rule of using sorts on short arrays:

```
q~{0]$1=}*

```

which is exactly equivalent to @Peter's answer

---

Previous 26 bytes asnwer:

```
q~_{g}%_|:+\(z\{za+_~>=}/*

```

This can be golfed further...

Input (via STDIN) is the integer array like :

```
[-4 -2 -3 -2]

```

and output is the minmod of the input array

Try it here

*If only `:g` and `:z` worked, this would have been 4 bytes shorter.*
> 4 votes

# Answer
# TI-BASIC, 19 bytes

Assumes input in the format `{-2,4,3}`.

Works similarly to xnor's answer:

```
Input L₁              get user input into the L1 array
dim(L₁)2-1→dim(L₁     get the length of the array; multiply by 2 and subtract 1
                      make this the new length (new elements always default to 0)
median(L₁             calculate and return (since it's the last line) median of new array

```
> 4 votes

# Answer
# Java, 84 bytes

This is Java in all its glory. Beats GolfScript by a factor of slightly over 900%.

```
int f(int[]a){int b=a[0],c;for(int d:a)b=(c=d<0?-1:1)*b<0?0:d*c<b*c?d:b;return b;}

```

Wrapped in class:

```
public class MinModGolfed{

    public static void main(String[] args){
        int[] numbers = new int[args.length];
        for (int i = 0; i < args.length; i++){
            numbers[i] = Integer.parseInt(args[i]);
        }
        System.out.println(new MinModGolfed().f(numbers));
    }

    int f(int[]a){int b=a[0],c;for(int d:a)b=(c=d<0?-1:1)*b<0?0:d*c<b*c?d:b;return b;}

}

```

Expanded with comments:

```
public class MinModExpandedGolfed{

    public static void main(String[] args){
        int[] numbers = new int[args.length];
        for (int i = 0; i < args.length; i++){
            numbers[i] = Integer.parseInt(args[i]);
        }
        System.out.println(new MinModExpandedGolfed().f(numbers));
    }

    int f(int[]a){                  //a is the input numbers
        int b=a[0],c;             //b is the best number found so far.
        for(int d:a)               //Iterate over a with current element as d.
            b=(c=d<0?-1:1)         //c is equal to the sign of d.
                    *b<0?
                        0:          //If b has opposite sign of d, b = 0.
                        d*c<b*c?d:b;//If the absolute value of d is less than b, b = d.
        return b;
    }

}

```

***Note: This can be improved using Java 8.***

***Note: Effort to improve in Java 8 failed.***
> 4 votes

# Answer
# J, ~~20~~ 12 bytes

Function taking the list as argument. Stolen from the Golfscript/CJam/whatever.

```
(1{0/:~@,,)/

```

The minmod of `x` and `y` is the median (sort `/:~` and take the middle `1{`) of the three item list `0,x,y`. Reduce the list (*folding* in J parlance) by taking this minmod between adjacent elements.

In use at the REPL. (J spells its negative sign `_`.)

```
   (1{0/:~@,,)/ _4 _2 _3 _2
_2
   f =: (1{0/:~@,,)/    NB. give it a name
   f 1 1 2
1
   f 0 1 2
0
   f _1 1 2
0

```

Old garbage, before I noticed short sorts are allowed: `0:`<.`>.@.(*@]*0<*))/` The minmod of `x` and `y` is 0 (`0:`) if 0 is greater than or equal to the product of `x` and `y`, else it is the min (`<.`) or the max (`>.`) between `x` and `y` depending on the sign. Fold this over the whole list.
> 4 votes

# Answer
# Python 2, ~~82~~ ~~79~~ ~~71~~ ~~69~~ 61 bytes

```
lambda l:reduce(lambda G,H:[H,G][(G>H)^(G>0)]*(G*H>0),l,l[0])

```

This is based off of my pyth answer, which was inspired by Mig's answer.

---

Old answer:

```
l=input()
m=l[0]
k=1-2*(m<0)
for i in l:m=[m,i][m>i*k]
print(k*m>0)*m

```

This is a very long answer. ~~I feel like having 2 variables is a waste...?~~ I was right...? ish? ;p
> 3 votes

# Answer
# Pyth, ~~25~~ ~~22~~ ~~20~~ 12

```
uhtS[0GH)QhQ

```

Probably not novel, but original :P

---

Pre-sorting allowed

```
u*?Gx>GH>G0H>*GHZQhQ

```

Pyth

Try it online.

The idea to use `reduce` and ternary statements was shamelessly stolen from Mig's answer, but I have no idea if these algorithms are otherwise even similar, as I can't read ternary statements.

Explanation:

```
Q=eval(input)         : implicit
u                QhQ  : print reduce(lambda G,H: ..., Q, Q[0])
 *          >*GHZ     : ... * (G*H>0)
  ?G       H          : G if ... else H
    x>GH>G0           : G>H xor G>0

```
> 3 votes

# Answer
# KDB/Q, 43 characters for function body definition

Thanks to great ideas from previous posts:

```
f:{$[all 1_0<(*':)x;{$[<[x*x;y*y];x;y]}/[x];0]}

```

Enter single number using enlist

```
f[enlist 2]
f[enlist 0]
f[enlist -2]
f[2 4 1]
f[0 1 2]
f[1 0 2]
f[-1 1 2]
f[-4 -2 -3 -2]
f[-5 0 -1]
f[-5 -0 -1]
f[1 0 -1]

```

I'm sure some Q guru can come up with shorter ones.
> 3 votes

# Answer
# C#, 101 bytes

My first try at code golfing and in a pretty golfing hostile language. Based on reduce (`Aggregate` in LINQ) and very similar to the JavaScript answer by Mig. Can be run like `(new System.Linq.M()).m(new[] {1, 2, 3})`. Passes all test cases, but doesn't handle empty input arrays.

```
namespace System.Linq{class M{public int m(int[]i){return i.Aggregate((a,b)=>a*b>0?a*a<b*b?a:b:0);}}}

```
> 3 votes

# Answer
# J, 12 bytes

```
   (=&**>&|{,)/

```

The function reduces the list (called folding (`/`) in J) with the expression:

`(signum(x) == signum(y)) * [x,y][abs(x)>abs(y)]` where

`[x,y][abs(x)>abs(y)]` is `y` if `abs(x) > abs(y)` else `x`.

Example:

```
   (=&**>&|{,)/ 5 2 6
2

```

Try it online here.
> 3 votes

# Answer
# Java, ~~353~~ ~~304~~ 124 bytes

Put together the worst language for code golf with the world's worst golfer and you get...

```
int m(int[]a){int m=a[0];if(m<0)for(int i:a){m=(i>m)?i:m;m=(i>0)?0:m;}else for(int i:a){m=(i<m)?i:m;m=(i<0)?0:m;}return m;}}

```

Ungolf it and you get:

```
int m(int[] a) {
    int m = a[0];
    if (m < 0) {
        for (int i : a) {
            m = (i > m) ? i : m;
            m = (i > 0) ? 0 : m;
        }
    } else {
        for (int i : a) {
            m = (i < m) ? i : m;
            m = (i < 0) ? 0 : m;
        }
    }
    return m;
}

```

This is a function (if it wasn't pretty damn obvious) that receives an array of numbers and processes its values, returning the minmod value.

My old benemoth of a sollution is also included, which is a whole program - as always.

```
class M{public static void main(String[]a){java.util.Scanner s=new java.util.Scanner(System.in);int n,m=0;try{m=s.nextInt();if(m<0)while(true){n=s.nextInt();m=(n>m)?n:m;m=(n>0)?0:m;}else while(true){n=s.nextInt();m=(n<m)?n:m;m=(n<0)?0:m;}}catch(java.util.InputMismatchException e){System.out.print(m);}}}

```

Ungolf it and you get:

```
class M {

    public static void main(String[] a) {
        java.util.Scanner s = new java.util.Scanner(System.in);
        int n = 0, m = 0;
        try {
            m = s.nextInt();
            if (m < 0) {
                do {
                    n = s.nextInt();
                    m = (n > m) ? n : m;
                    m = (n > 0) ? 0 : m;
                } while (true);
            } else {
                do {
                    n = s.nextInt();
                    m = (n < m) ? n : m;
                    m = (n < 0) ? 0 : m;
                } while (true);
            }
        } catch (java.util.InputMismatchException e) {
            System.out.print(m);
        }
    }
}

```

Receives infinite numbers, stops when a non-number value is entered, presenting the Minmon value.
> 2 votes

# Answer
# Game Maker Language, 489 bytes

About Game Maker Language

Riffles the array (zeros are appended) and returns the median (similar to my other answer)

```
i=0a=argument0
while(variable_local_array_get(a,i))i++
for(j=0;j++;j<i-1)a[j+i]=0var i,j,d,m=0d=ds_list_create()if variable_local_exists(a){if variable_local_array_get(a,0){for(i=0;i<32000;i++){if variable_local_array_get(a,i)=0break
ds_list_add(d,variable_local_array_get(a,i))}ds_list_sort(d,0)i=ds_list_find_value(d,ds_list_size(d) div 2)j=ds_list_find_value(d,(ds_list_size(d) div 2)-1)m=ds_list_find_value(ds,ds_list_size(d) mod 2)ds_list_destroy(d)}if m return (i+j)/2return i
break}

```
> 2 votes

# Answer
# R, 20 chars

R is usually not good for codegolf, but I use it for my work so I wanted to try. Before I tried, I didn't know that R is willing to accept such a dirty syntax! :-) **52 chars**:

```
if((q=summary(x))[6]<0)q[6]else if(q[1]>0)q[1]else 0

```

Then I looked the other answers I tried @xnor's genial median trick, which is great!

```
median(c(x-x,x)[-1])

```
> 2 votes

# Answer
# Python, 52

I still couldn't help feeling that it's bad to have two `lambda`s. This function takes in a list and then returns a one-element list containing the result.

```
f=lambda a:a[1:]and[sorted([a.pop(),0]+f(a))[1]]or a

```

Hopefully, it will not cause an enormous amount of offense to have the result in a one-element list.
> 2 votes

# Answer
# Matlab/Octave, 26

This is basically just a translation of the Mathematica answer by xnor. It works by appending one zeros less than the length of the input vector. Note that appending one more would not work, since then the result would be 0 all the time. Thanks to MartinBüttner for the -4 chars of this solution=)

```
@(x)median([x,0*x(2:end)])

```
> 1 votes

# Answer
# Python, ~~72~~ 60 bytes

This is the first solution I thought of, and it's quite naive. The second half is basically a duplicate of the first half of the code, but I wasn't sure how to slim it. I wonder if it can be shortened using `eval`...

Edit: Changed lambdas to comprehensions.

**Try them here**

```
lambda l:min(l)*all(x>0for x in l)+max(l)*all(x<0for x in l)

```

This is only 4 chars longer, but still worth looking at, using Sp3000's TIP.

```
lambda l:eval("+m%s%s(l)*all(x%s0for x in l)"*2%tuple("ax<in>"))

```
> 1 votes

# Answer
## Javascript, 63

```
a=>a.reduce((p,c)=>p<0?c<0?Math.max(p,c):0:c>0?Math.min(p,c):0)

```

A more readable version:

```
function (arr) {
    return arr.reduce(function (p, c) {
        if (p < 0) {
            if (c < 0) {
                return Math.max(p, c);
            } else {
                return 0;
            }
        } else {
            if (c > 0) {
                return Math.min(p, c);
            } else {
                return 0;
            }
        }
    });
}

```
> 1 votes

---
Tags: code-golf, math, restricted-source
---


title: Avoid the Bullet Bills

text:
# Question
Title: Avoid the Bullet Bills
In 2D Mario, Bullet Bill cannons are two units tall. The Bullet Bill is fired out of the upper unit and travels in a straight line (parallel to the x axis).

Mario is two units tall when standing up and one unit tall when ducking. His jump height is three units. It takes him 0.5 seconds to reach the full height and 0.5 seconds to come back down.

### Challenge

Write a program that helps Mario avoid an incoming Bullet Bill. He may have to jump, duck, or do nothing.

### Input

The input will come in the format `[bullet_bill_position] [direction] [speed] [mario_position]`.

* `bullet_bill_position` consists of two space-separated integers, x and y. This represents the coordinates of the **upper unit** of the cannon. The bullet bill will fire from this location.
* `direction` will either be `left` or `right` (string).
* `speed` is the speed of the Bullet Bill in **units per second**.
* `mario_position` consists of x and y and represents the coordinates that Mario is **standing on**.

### Output

`[action] [wait_time]`

* `action` will be one of three strings: `duck`, `jump`, or `nothing`.
* `wait_time` only applies to `jump`. It represents how long Mario should wait before jumping over the Bullet Bill. If `action` is not `jump`, this will be left blank.

### Notes

* The ground will always be right underneath Mario's feet.
* Bullet Bills are only one unit tall and one unit wide. Mario will be safe if it passes one unit above his head.
* Mario will be safe if he lands on the Bullet Bill. Hitting the side or bottom will kill him.
* There will often be more than one solution. You only have to output one of them.
* Numerical input will always be **integers**. However, output may sometimes need to have floats/doubles.

## Test Cases

**Input**: `5 1 left 2.5 0 0`

**Possible Output**: `jump 1.5`

**Explanation**: The Bullet Bill will be at Mario's feet in 2 seconds. Mario will jump at 1.5 and touch back down at 2.5. The Bullet Bill passed safely underneath him.

**Another Possible Output**: `jump 1`

**Explanation**: If Mario jumps at 1, he will touch back down at 2 and land on the Bullet Bill.

**Input**: `0 3 right 100 5 0`

**Possible Output**: `nothing`

**Explanation**: The Bullet Bill will pass very quickly over Mario's head. He will be safe.

**Input**: `0 2 right 1 5 0`

**Output**: `duck`

**Explanation**: The Bullet Bill will go where Mario's head would've been.

## Rules

* You can write a full program or function.
* I/O should be to stdin and stdout.

## Scoring

This is . Your score is the number of bytes. The solution with the lowest score in one week will win. Good luck!

# Answer
## CJam, 84 80 61 bytes

This is my first program for this, literally just learned CJam last night, for this purpose only. I'm also new to this site's formatting, help would be great with that.

```
ri:Xri:Yrri:Sri:Ari:B];BY={"jump"XA<{AX)-S/}{X(A-S/}?}"duck"?

```

It's **no longer** longer than the previous answer, but I'm **still** posting it because I'd like tips and stuff.

**Explanation**

```
ri:X    - Sets Bullet X to X.
ri:Y    - Sets Bullet Y to Y.
r       - Omits direction.
ri:S    - Sets speed to S.
ri:A    - Sets Mario X to A.
ri:B    - Sets Mario Y to B.
];      - Clears the stack.
BY=     - Due to the ? at the end, executes the first block if true (if B=Y) or the second block (in this case "duck") if false.
{"jump" - Outputs jump.
XA<     - Due to the ? after the next two blocks, executes the first block if true (if X<A) or the second block if false.
{AX)-S/}- Solves and outputs (A-(X+1))/S.
{X(A-S/}- Solves and outputs ((X-1)-A)/S.
?}      - Executes block A if the condition before it is true, or block B if not.
"duck"  - Outputs duck.
?       - Executes block A if the condition before it is true, or block B if not.

```

There's an online interpreter here if needed.
> 6 votes

# Answer
# Python, 72 68 66 bytes

We can ignore left/right - if we assume it's always pointed at us we'll always take the right action. Then if our assumption was wrong we did a useless jump/duck, but that doesn't matter - we'll still be safe.

Similarly, there is no incentive to do nothing. Rather, it's shorter code to always duck, and jump when necessary. Ducking will only be unsafe if the bullet bill is exactly one above the block we're standing on. In that case we will take our x position, bullet bill's y position, take the absolute difference, divide by bullet bill's speed and jump 0.2 seconds before that.

```
lambda a,b,_,s,x,y:["duck","jump "+`max(0,abs(a-x)/s-.2)`][y+1==b]

```

Call like this:

```
f=lambda a,b,_,s,x,y:["duck","jump "+`max(0,abs(a-x)/s-.2)`][y+1==b]
f(5, 1, "left", 2.5, 0, 0)

```
> 9 votes

# Answer
# Haskell, 61 Bytes

I found that there's no point in doing nothing. Jump if Bill is at or bellow Mario's feet, otherwise duck.

```
f a b _ c d e|b<e+2="Jump "++(show$abs(a-d)/c-0.5)|1<2="Duck"

```
> 4 votes

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


# Question
Title: Convert any number (up to 1e3000) to text
Given an input, calculate the correct suffix and output the number in a readable format in short scale (where 1 billion is 10^9). The suffixes must go to at least 10^3000, in which the rules for calculating them can be found here, or a list can be found here.

There is no need to output the exact numbers, this is focused on getting a huge number into a readable format.

For example:

```
10000 = 10.0 thousand
135933445 = 135.93 million
-2 = -2.0
-2.36734603 = -2.37
'1'+'9'*3000 = 2.0 nongennovemnonagintillion

 // out of range examples
'1'+'9'*3010 = 20000000000.0 nongennovemnonagintillion
'-1'+'9'*5000 = -inf nongennovemnonagintillion

```

I am aware it is similar to this question, though with 10x as many numbers and not having to read the names, there's potentially a lot more room for golfing. For the record, my result is 578 characters in Python.

**Rules:**

* No getting things from external resources - it must all be calculated within the code.
* External modules are fine, just don't break the above rule.
* The code should work when input is either a string, integer or float (eg. you may wish to input the super large numbers as strings).
* The output must always contain a decimal place.
* The output must be rounded if above 2 decimal places. Using the inbuilt round function is fine, I am aware there are some floating point errors, so if the occasional '.045' doesn't round up to '.05' for example, don't worry about it.
* Leaving multiple zeroes at the end is optional, as long as it doesn't go above 2 decimals (1.00 or 1.0 are both fine) and is consistent for all inputs (an input of 1 and 1.0 should output the same result).
* An input too large shouldn't cause an error, `inf` is a valid value since it's part of `float`.

**Scoring:**

* Score is the length of the code, including indents.
* Lowest score wins.
* Output can be either printed or returned.
* Setting the input number does not count towards length.

As a starting point, here is an ungolfed version of some code in Python to generate the list of suffixes. Feel free to build upon this or start from scratch.

```
a = ['', 'un','duo','tre','quattor','quin','sex','septen','octo','novem']
c = ['tillion', 'decillion', 'vigintillion', 'trigintillion', 'quadragintillion', 'quinquagintillion', 'sexagintillion', 'septuagintillion', 'octogintillion', 'nonagintillion']
d = ['', 'cen', 'duocen', 'trecen', 'quadringen', 'quingen', 'sescen', 'septingen', 'octingen', 'nongen']

num_dict = ['']
num_dict.append('thousand')
num_dict.append('million')
num_dict.append('billion')
num_dict.append('trillion')
num_dict.append('quadrillion')
num_dict.append('quintillion')
num_dict.append('sextillion')
num_dict.append('septillion')
num_dict.append('octillion')
num_dict.append('nonillion')

for prefix_hundreds in d:

    #tillion can't be used first time round
    if not prefix_hundreds:
        b = c[1:]
    else:
        b = c

    for prefix_tens in b:
        for prefix in a:
            num_dict.append(prefix_hundreds+prefix+prefix_tens)

```

# Answer
> 1 votes
To get the ball rolling then, this is my version. Only the final number is converted to a float so there is no problem with large numbers if they're within range.

In terms of speed, it takes about 0.85 seconds to calculate 1000 random integers between -1e3000 and 1e3000.

# Python 2 (574)

```
N=str(X).split('.');K=len;E=min(1000,(K(str(abs(int(N[0]))))-1)/3);P=N[0][:(-E*3if E else K(N[0]))];L=K(P);B=''.join(N);O='%.2f'%float((P+'.'+((B[L:L+3])or'0')));m,n,o,p,q,r,s,t,u,v,w,x,y,z='illion quadr quin sex sept oct non ing ag g tre duo c t'.split();a=[''];l=a+['thousand']+[i+m for i in['m','b','tr',n,o+z,p+z,q,r,s]]+[i+j+k for i in a+[i+'en'for i in[y,x+y,w+y,n+t,o+v,'sesc',q+t,r+t,s+v]]for k in[C+m for C in[z,'dec']+[B+'int'for B in['vig','trig',n+u,o+'quag',p+u,q+'uag',r+'og',s+u]]][not i:]for j in a+['un',x,w,'quattor',o,p,q+'en',r+'o','novem']];print O,l[E]

```

Then with some test cases:

```
>>> X = 100
100.0
>>> X = '100.0'
100.0
>>> X = '1037093920'
1.04 billion
>>> X = '-1540420004036040042.400642'
-1.54 quintillion
>>> X = '1540420' + '0'*153
1.54 duoquinquagintillion
>>> X = '1540496' + '0'*1553
154.05 quingenoctodecillion

Past the limit (just to show it doesn't throw an error and still handles negative value):
>>> X = '-10935' + '6'*3005
-1093566666.67 nongennovemnonagintillion
>>> X = '10935' + '6'*3250
1.09356666667e+254 nongennovemnonagintillion
>>> X = '10935' + '6'*3500
inf nongennovemnonagintillion

```

---
Tags: code-golf
---


title: Name a number using the Myriad System!

text:
# Question
Title: Name a number using the Myriad System!
The Myriad System is an alternative system for naming large numbers proposed by Donald Knuth in 1981.

In this system, numbers up to 999 are named as they are normally, but 1000 is not given a special name and is instead named as "ten hundred"; the next benchmark number being 10000, or "one myriad" (which, of course, comes from an ancient greek word meaning 10000).

From here one myllion is defined as one myriad * one myriad, one byllion as one myllion * one myllion, one tryllion as one byllion * one byllion, and so forth.

The challenge here is to take a base-10 integer from the input and determine its name in this system.

Your input is guaranteed to be nonnegative and less than 10212=104096 (one decyllion)

Either a full program (in which case input can be taken from either stdin or a command line argument, and output must be sent to stdout) or a function (which takes the input as an argument and returns the output) is permissible.

The returned string should be formatted as per this Java program:

```
import java.math.*;

public class Myriadizer{
    static BigInteger b=new java.util.Scanner(System.in).nextBigInteger(),c=b,TEN=BigInteger.TEN,d=TEN.pow(4),f=TEN.pow(2),e=BigInteger.ZERO;
    static String[]strings={"six","seven","eight","nine","four","thir","fif"};
    static String output="";
    static void t(){
        int i=0;
        while(b.compareTo(d)>=0){
            b=b.divide(d);
            i++;
        }
        int k=b.intValue();
        char[]binary=Integer.toString(i,2).toCharArray();
        int q=48,bits=binary.length;
        String r="yllion ";
        s(k);
        if(bits>0&&binary[bits-1]!=q)output+="myriad ";
        if(bits>1&&binary[bits-2]!=q)output+="m"+r;
        if(bits>2&&binary[bits-3]!=q)output+="b"+r;
        if(bits>3&&binary[bits-4]!=q)output+="tr"+r;
        if(bits>4&&binary[bits-5]!=q)output+="quadr"+r;
        if(bits>5&&binary[bits-6]!=q)output+="quint"+r;
        if(bits>6&&binary[bits-7]!=q)output+="sext"+r;
        if(bits>7&&binary[bits-8]!=q)output+="sept"+r;
        if(bits>8&&binary[bits-9]!=q)output+="oct"+r;
        if(bits>9&&binary[bits-10]!=q)output+="non"+r;
        if(bits>10&&binary[bits-11]!=q)output+="dec"+r;
        b=c=c.subtract(d.pow(i).multiply(b));
        if(b.compareTo(f)>=0)output+=",";
        output+=" ";
        if(b.compareTo(e)>0&&b.compareTo(f)<0)output+="and ";
    }
    static void s(int t){
        if(t>99){
            s(t/100);
            output+="hundred ";
            if(t%100>0)output+="and ";
            s(t%100);
            return ;
        }
        if(t==0)return;
        if(t<13){
            output+=(new String[]{
                    "one","two","three",
                    strings[4],"five",strings[0],strings[1],strings[2],strings[3],
                    "ten","eleven","twelve"
            })[t-1]+" ";
            return ;
        }
        if(t<20){
            output+=(new String[]{
                    strings[5],strings[4],strings[6],strings[0],strings[1],strings[2],strings[3]
            })[t-13]+"teen ";
            return ;
        }
        output+=new String[]{"twen",strings[5],"for",strings[6],strings[0],strings[1],strings[2],strings[3]}[t/10-2]+"ty";
        if(t%10>0){
            output+="-";
            s(t%10);
            return;
        }
        output+=" ";
    }
    public static void main(String[]a){if(b.equals(e)){System.out.println("zero");return;}while(c.compareTo(e)>0)t();System.out.println(output.replaceAll("\\s+$","").replaceAll("\\s\\s+"," ").replaceAll("\\s,",","));}
}

```

Some details of this that should be noted:

* The terms in the main sum should be arranged in descending order
* The terms in any given product should be arranged in ascending order, and exactly one term in any given product should be under one myriad
* The terms in the main sum should be comma-separated, *unless the last is under one hundred* in which case the last two should be separated by the conjunction "and"

This is code golf, so the shortest program wins.

Some test cases:

```
0                                 = zero
100                               = one hundred
1000                              = ten hundred
10014                             = one myriad and fourteen
19300                             = one myriad, ninety-three hundred
100000                            = ten myriad
1000000                           = one hundred myriad
1041115                           = one hundred and four myriad, eleven hundred and fifteen
100000000                         = one myllion
1000000501801                     = one myriad myllion, fifty myriad, eighteen hundred and one
94400000123012                    = ninety-four myriad myllion, forty hundred myllion, twelve myriad, thirty hundred and twelve
10000000200000003000000040000000  = ten hundred myriad myllion byllion, twenty hundred myriad byllion, thirty hundred myriad myllion, forty hundred myriad
100000002000000030000000400000000 = one tryllion, two myllion byllion, three byllion, four myllion

```

# Answer
> 1 votes
# C, 698 bytes

Recursive approach, don't mind the memory leaks :) Explanation to come later.

```
#include <stdlib.h>
#define c char*
n;c r(c v){c p,*z,*o[]={"","one","two","three","four","five","six","seven","eight","nine","ten","eleven","twelve","thirteen","fourteen","fifteen","sixteen","seventeen","eighteen","nineteen","twen","thir","for","fif","six","seven","eigh","nine","hundred","myriad","m","b","tr","quadr","quint","sext","sept","oct","non","dec"};int s,l;long t;v+=strspn(v,"0");l=strlen(v);if(l<3)n=atoi(v),n<20?p=o[n],0:asprintf(&p,n%10?"%sty-%s":"%sty",o[n/10+18],o[n%10]);else s=(int)(log(l-1)/log(2))-1,z=v+l-(2<<s),t=strtol(z,0,10),p=r(z),*z=0,asprintf(&p,*p?"%s %s%s%s %s":"%s %s%s",r(v),o[s+28],s>1?"yllion":"",*p?t<100?" and":",":"",p);return p;}main(_,v)c*v;{puts(r(v[1]));}

```

## Examples

```
$ ./a.out 0
zero
$ ./a.out 100
one hundred
$ ./a.out 1000
ten hundred
$ ./a.out 10014
one myriad and fourteen
$ ./a.out 19300
one myriad, ninety-three hundred
$ ./a.out 100000
ten myriad
$ ./a.out 1000000
one hundred myriad
$ ./a.out 1041115
one hundred and four myriad, eleven hundred and fifteen
$ ./a.out 100000000
one myllion
$ ./a.out 1000000501801
one myriad myllion, fifty myriad, eighteen hundred and one
$ ./a.out 94400000123012
ninety-four myriad, forty hundred myllion, twelve myriad, thirty hundred and twelve
$ ./a.out 10000000200000003000000040000000
ten hundred myriad myllion, twenty hundred myriad byllion, thirty hundred myriad myllion, forty hundred myriad
$ ./a.out 100000002000000030000000400000000
one tryllion, two myllion and three byllion, four myllion

```

# Answer
> 0 votes
# Java, ~~1477~~ 1459 bytes

```
import java.math.*;class M{static BigInteger b=new java.util.Scanner(System.in).nextBigInteger(),c=b,k=BigInteger.TEN,d=k.pow(4),f=k.pow(2),e=BigInteger.ZERO;static String o="",s[]={"six","seven","eight","nine","four","thir","fif"},p=" ";static void s(int t){if(t>99){s(t/100);o+="hundred ";if(t%100>0)o+="and ";s(t%100);return;}if(t==0)return;if(t<13){o+=new String[]{"one","two","three",s[4],"five",s[0],s[1],s[2],s[3],"ten","eleven","twelve"}[t-1]+p;return;}if(t<20){o+=new String[]{s[5],s[4],s[6],s[0],s[1],s[2],s[3]}[t-13]+"teen ";return;}o+=new String[]{"twen",s[5],"for",s[6],s[0],s[1],s[2],s[3]}[t/10-2]+"ty";if(t%10>0){o+="-";s(t%10);return;}o+=p;}public static void main(String[]a){if(b.equals(e)){System.out.println("zero");return;}while(c.compareTo(e)>0){int i=0;while(b.compareTo(d)>=0){b=b.divide(d);i++;}char[]z=Integer.toString(i,2).toCharArray();int q=48,l=z.length;String r="yllion ";s(b.intValue());if(l>0&&z[l-1]!=q)o+="myriad ";if(l>1&&z[l-2]!=q)o+="m"+r;if(l>2&&z[l-3]!=q)o+="b"+r;if(l>3&&z[l-4]!=q)o+="tr"+r;if(l>4&&z[l-5]!=q)o+="quadr"+r;if(l>5&&z[l-6]!=q)o+="quint"+r;if(l>6&&z[l-7]!=q)o+="sext"+r;if(l>7&&z[l-8]!=q)o+="sept"+r;if(l>8&&z[l-9]!=q)o+="oct"+r;if(l>9&&z[l-10]!=q)o+="non"+r;if(l>10&&z[l-11]!=q)o+="dec"+r;b=c=c.subtract(d.pow(i).multiply(b));if(b.compareTo(f)>=0)o+=",";o+=p;if(b.compareTo(e)>0&&b.compareTo(f)<0)o+="and ";};System.out.println(o.replaceAll("\\s+$","").replaceAll("\\s\\s+"," ").replaceAll("\\s,",","));}}

```

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


title: Print a random maze

text:
# Question
Title: Print a random maze
Write a program that generates and prints a random maze using the algorithm of your choice. The maze should be different for multiple runs of the program. Height and width are given as command line arguments. Use `|` for vertical wall, `-` for horizontal wall and `+` for corner. The maze is bounded by walls and the entrances are marked by missing wall. The maze contains a treasure `#` which must be reachable from at least one entrance.

```
$ python2 random-maze.py 4 5
+-+-+
  |#|
|   |
+---+

```

# Answer
I think this technically isn't a maze generator, but it creates a maze like result: https://gist.github.com/803450.

Some horrible code in there I know, and it only works less than half the time, and the result doesn't look quite right to do with walls sticking out from other walls. But its close enough that I can't be bothered fixing the rest.

Some example output:

```
→ ruby random-maze.rb 30 30
+----+-+-----------++-+----+
|    + |           ++ |    |
++  +  | ++ ++   +    + ++ ++
|  ++ ++ |  |    +---+  +   |
| +      | +| +   +++  +  + |
|   +   +| +| +-+  |   + +  |
|        +  +    + + ++  |+ |
| + ++ +  ++   + |  +   ++| |
| |  | ++  + +----+ + +-+ | |
| +  |  +-+  |+        |  | |
|   +-+  +| ++  ++ + + |  | |
| ++   +  + |  ++|   + | ++ |
|  + + + +  +---++-+   +++  |
| +  |  +| +    |  ++   |   |
| | +++ +| + ++ +--+  + |---+
|#+ | |  |   +++     +  +   |
++  | ++ +-+  ++ +--+  +  + |
|  ++  |    +     ++| +  ++ |
| ++   +--------+  +| + +   |
| |     |      +++  |  +  +-+
| |     | +--+  |++ |+ | ++
| |     |  +--+ | | || |  |
| |     +-+     +-+ |+ |+ |
| | +---+   ++      +  |  |
| +-|     +    +      ++ ++
|   +       ++   +---+   |
|              ++   +  +-+
|                 +   ++
+-+ +-------------+---+

```
> 5 votes

# Answer
## Python, 375 characters

```
import random,sys
H,V=map(int,sys.argv[1:])
H-=1
V-=1
b,h,v,p=' -|+'
M=H/2*h
n=random.randint(1,(H/2)*(V/2-1))
for i in range(V/2):
 e=s=t='';N=v
 for j in range(H/2):
  if i and(random.randint(0,1)or j==0):s+=N+b;t+=v;N=v;M=M[1:]+p
  else:s+=M[0]+h;t+=b;N=p;M=M[1:]+h
  n-=1;t+=' #'[n==0]
 if H&1:s+=s[-1];t+=b;e=h
 print s+N+'\n'+t+v
if V&1:print t+v
print h.join(M)+e+h+p

```

This generates a maze with one entrance and a randomly placed treasure. The maze is a simple binary tree maze.

```
$ ./maze.py 15 15
--------------+
              |
| | ----------+
| |           |
| +-----+ | --+
|       | |   |
| --+ --+ +---+
|   |   |     |
| --+-+ +---+ |
|     |     | |
| --+ +-+ --+ |
|   |   |   |#|
| | | --+ --+-+
| | |   |     |
+-+-+---+-----+

```
> 8 votes

# Answer
## Ruby 1.9.2p136 : 90

```
eval ARGV[0]
z=[l="+"+"-"*@w+"+"]
@h.times{z<<"|"+" "*@w+"|"}
z[rand(@h)+1]="|#"
puts z<<l

```

Output

```
$> ruby maze.rb "@h=8;@w=8;"

+------+
|      |
|      |
|      |
|      |
|#
|      |
+------+

```

Hey, no one said it had to be a **good** maze. OK, OK, I'll make a real one now.
> 6 votes

# Answer
## C 844

```
#include <stdlib.h>
#include <time.h>
h,w,*m,y,x,z;d(t,b,l,r){int i=b-t,j=r-l;if(i>1&&j>1){i=(rand()%--i)|1;j=(rand()%--j)|1;z=rand()%4;x=rand()%i+t;x|=1;for(y=t;y<i+t;y++)if(y!=x||!z)m[y*w+j+l]=124;x=rand()%(b-i-t)+i+t;x|=1;for(y=t+i;y<b+1;y++)if(y!=x||!(z-1))m[y*w+j+l]=124;y=rand()%j+l;y|=1;for(x=l;x<j+l;x++)if(y!=x||!(z-2))m[(i+t)*w+x]=45;y=rand()%(r-j-l)+j+l;y|=1;for(x=l+j;x<r+1;x++)if(y!=x||!(z-3))m[(i+t)*w+x]=45;m[(i+t)*w+j+l]=43;m[(t-1)*w+l+j]=43;m[(b+1)*w+j+l]=43;m[(i+t)*w+l-1]=43;m[(i+t)*w+r+1]=43;d(t,t+i-1,l,l+j-1);d(t+i+1,b,l,l+j-1);d(t,t+i-1,l+j+1,r);d(t+i+1,b,l+j+1,r);}}main(int c,char**v){h=atoi(v[1]),w=atoi(v[2]),m=calloc(h*w,4);srand(time(0));while(y<h){while(x<w){m[y*h+x]=(!y||y==h-1)?(!x||x==w-1)?43:45:(!x||x==w-1)?124:32;x++;}y++;x=0;}d(1,h-2,1,w-2);z=rand()%(w-2);z|=1;m[z]=32;z=rand()%(w-2);z|=1;m[h*(w-2)+z]=35;}

```

**To Test:**

```
#include <stdio.h>//beginning
for(y=0;y<h;y++){for(x=0;x<w;x++){putchar(m[y*h+x]);}putchar('\n');}getchar();//end

```

**3x3**

```
+ +
|#|
+-+

```

**7x8**

```
+-+-- -+
|      |
+ +-+--+
|      |
| +-+ -+
| |  # |
+-+-+--+

```

**18x20**

```
+-+-+ +---+---+-+--+
| | |         |    |
| + + +-- +---+ +--+
|     |       |    |
+ + +-+---+-- +-+ -+
| |   |            |
+-+ +-+-+-+---+-+--+
| | |   |       |  |
| + + + +-+-- --+  |
| |   |         |  |
| | | +-+-+ ----+  |
|   | |         |  |
+ + +-+-+-+-- --+ -+
| |   |         |  |
| + +-+-- +-- --+  |
| |   |   |        |
| | | |  #|     |  |
+-+-+-+---+-----+--+

```
> 3 votes

# Answer
Here's a simple java solution:

```
import java.util.*;

public class MazeGen {
    public static void main(String[]a){
        int w,l;
        Random rand=new Random(System.currentTimeMillis()%1000+System.nanoTime());
        if(a.length==2){
            w=Integer.parseInt(a[0]);
            l=Integer.parseInt(a[1]);
        }else{
            System.out.println("No command line arguments, taking from STDIN.");
            Scanner input=new Scanner(System.in);
            w=input.nextInt();
            l=input.nextInt();
            input.close();
        }
        char[][]maze=new char[w][l];
        for(int x=0;x<w;x++){
            for(int y=0;y<l;y++){
                maze[x][y]=' ';
            }
        }
        for(int x=0;x<w;x++){
            maze[x][0]=maze[x][l-1]='|';
        }
        for(int y=0;y<l;y++){
            maze[0][y]=maze[w-1][y]='-';
        }
        maze[0][0]=maze[w-1][0]=maze[w-1][l-1]=maze[0][l-1]='+';
        int dor=1+rand.nextInt(l-2);
        maze[0][dor]=' ';
        int tx=2+rand.nextInt(w-3),ty=1+rand.nextInt(l-2);
        maze[tx][ty]='#';
        if(ty<dor-1){
            maze[tx][ty+1]='|';
            if(tx==w-2){
                maze[tx+1][ty+1]='+';
            }
            if(tx==1){
                maze[0][ty+1]='+';
            }
        }
        if(ty>dor+1){
            maze[tx][ty-1]='|';
            if(tx==w-2){
                maze[tx+1][ty-1]='+';
            }
            if(tx==1){
                maze[0][ty-1]='+';
            }
        }
        if(ty==dor&&tx>3&&(maze[tx][ty+1]==' '||maze[tx][ty-1]==' ')){
            maze[tx-1][ty]='-';
        }
        if(dor>5){
            int z=2+rand.nextInt(dor-3);
            int q=1+rand.nextInt(w-3);
            for(int i=0;i<w;i++){
                if(i==0||i==w-1){
                    maze[i][z]='+';
                }else if(i!=q&&maze[i][z]==' '){
                    maze[i][z]='|';
                }
            }

        }
        if(l-dor>5){
            int z=dor+2+rand.nextInt(l-dor-3);
            int q=1+rand.nextInt(w-3);
            for(int i=0;i<w;i++){
                if(i==0||i==w-1){
                    maze[i][z]='+';
                }else if(i!=q&&maze[i][z]==' '){
                    maze[i][z]='|';
                }
            }

        }
        for(char[]row:maze){
            System.out.println(row);
        }
    }
}

```

# Some sample results:

3x3:

```
+ +
|#|
+-+

```

4x4:

```
+ -+
| #|
|  |
+--+

```

4x5:

```
+-+ +
|#| |
|   |
+---+

```

5x5:

```
+ --+
|   |
|   |
| |#|
+-+-+

```

5x8:

```
+ --+--+
|   |  |
|      |
| # |  |
+---+--+

```

8x15:

```
+---- ----+---+
|         |   |
|         |   |
|         |   |
|             |
| #|      |   |
|         |   |
+---------+---+

```
> 0 votes

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


title: Through the bases

text:
# Question
Title: Through the bases
# Through the bases

In this challenge, you will be taking a number through all the bases of the rainbow

Given an input, `n`, you will output `n` in every base from 9 to 2, and back up to 9. That's `9 8 7 6 5 4 3 2 3 4 5 6 7 8 9`.

**Example:**

```
>>> 16
17
20
22
24
31
100
121
10000
121
100
31
24
22
20
17

```

**Rules:**

* You input can be a string or a number.
* Your output may be separated by new lines, spaces, commas, or tabs.
* You may use built in functions.
* Shortest code wins!

# Answer
# CJam, 14 bytes

```
riF,f{7-z2+bN}

```

Try it online in the CJam interpreter.

### How it works

```
ri             e# Read an integer I from STDIN.
  F,           e# Push [0 ... 14].
    f{       } e# For each B in that range, push I and B; then:
      7-z2+    e#   Compute abs(B - 7) + 2.
               e#   This maps [0 ... 14] to [9 ... 2 ... 9].
           b   e#   Perform base conversion.
            N  e#   Push a linefeed.

```
> 8 votes

# Answer
# Pyth, 14 bytes

```
V+_Jr2TtJjkjQN

```

Needs more work, most code is spent generating 9..2..9.
> 6 votes

# Answer
# Pyth, ~~18~~ ~~15~~ 14 bytes

Saved 3 bytes thanks to Dennis and 1 thanks to Jakube!

```
V+r9 1r3TjkjQN

```

Explanation:

```
V                     For N in
 +r9 1r3T             the list [9,8,...3,2,3,...,8,9],
           jQN        convert the input to base N (returns a list),
         jk           join the list into a string, implicitly printed.

```

Try it online.
> 3 votes

# Answer
## Haskell, 59

```
0%_=0
k%b=div k b%b*10+mod k b
g n=map(n%)$[9,8..3]++[2..9]

```

First, recursively defines a binary operator `%` to do base conversion, representing the output as a decimal number rather than a string. The function `g` converts the input `n` to each base from 9 to 2 and back up.

There's probably a shorter approach, advice is welcome. Saved 2 chars on parens thanks to nimi.
> 3 votes

# Answer
# Bash + dc, 27

```
echo {{9..2},{3..9}}o$1p|dc

```
> 3 votes

# Answer
# Julia, 43 bytes

```
n->for i=[9:-1:2,3:9] println(base(i,n))end

```

This creates an unnamed function that accepts and integer and prints to STDOUT on separate lines. The `base` function takes two integers: a base (`i`) and a number (`n`) and returns the string representation of the number in the given base. Here we just loop through the required bases and print.
> 2 votes

# Answer
## JavaScript (ES6), 57 bytes

```
f=n=>[...`987654323456789`].map(v=>n.toString(v)).join` `

```

## CoffeeScript, 57 bytes

Different approach:

```
f=(n)->[-7..7].map((v)->n.toString 2+Math.abs v).join ' '

```

## JavaScript (ES5), 97 bytes

```
function f(n){return'987654323456789'.split('').map(function(v){return n.toString(v)}).join(' ')}

```

### Demo

```
function f(n) {
  return '987654323456789'.split('').map(function(v) {
    return n.toString(v)
  }).join(' ')
}

document.body.innerHTML = f(16)
```
> 2 votes

# Answer
## Python 2, 79

```
g=lambda b,k=input():k and g(b,k/b)*10+k%b
c=7;exec"print g(abs(c)+2);c-=1;"*15

```

The function `g` converts a number `k` to a base `b`. We can take `k` as the program input because Python initializes default arguments when the function is defined, not each time it's called. We get the desired sequence of bases by taking the range `[-7, -6, ..., 6, 7]`, taking the absolute value, and adding 2.
> 1 votes

# Answer
# JavaScript SpiderMonkey 31 (1.8), 47 bytes

```
n=>[for(i of`987654323456789`)n.toString(i)]+''

```

It doesn't get simpler than this.
> 1 votes

# Answer
# Pip, 14 = 13 + 1 bytes

Uses the `-n` flag.

```
aTB2+AB(-7,8)

```

GitHub repository for Pip

Takes the number as a command-line argument.

```
        -7,8   Range containing integers from -7 through 7
     AB(    )  Absolute value of each
   2+          Add 2 to each
aTB            Convert command-line arg to each base
               Print resulting list, newline-separated (-n flag)

```

It's amazing how all the golfing languages are getting the same score here.
> 1 votes

# Answer
## JavaScript (ES5), ~~69~~ ~~66~~ 65 bytes

```
function f(o){for(i=15;i--;)console.log(o.toString(i>7?i-5:9-i))}

```
> 1 votes

# Answer
## Ruby, 44 bytes

```
a=->n{(0..14).map{|j|p n.to_s((j-7).abs+2)}}

```

Call the lambda with `a.call(number)`. This prints out with quotes around each line because `p` is shorter than `puts`. I'm assuming this is allowed.
> 0 votes

# Answer
# APL, 52 bytes

I'll admit, this could use more golfing.

```
{n←⍵⋄⊃{⍺,' ',⍵}/{⊃,/⍕¨(~∧\0=e)/e←(10⍴⍵)⊤n}¨2+|8-⍨⍳15}

```

it is limited to at most 10 digits output

suggestions for improvement welcome

output for 16 looks like

```
17 20 22 24 31 100 121 10000 121 100 31 24 22 20 17

```
> 0 votes

---
Tags: code-golf, base-conversion
---


title: Row of natural numbers

text:
# Question
Title: Row of natural numbers
# Definition

There is infinite row of concatenated natural numbers (positive integers, starting with 1):

`1234567891011121314151617181920212223...`

# Challenge

* Write program in any language, that accepts position number as an input, and outputs digit from that position in the row defined above.
* Position number is arbitrary size positive integer. That is first position is 1, yielding output digit '1'
* Input is either in decimal (eg. 13498573249827349823740000191), or e-notation (eg. 1.2e789) corresponding to positive integer.
* Program has to end in reasonable time (10 seconds on modern PC/Mac), given very large index as an input (eg. 1e123456 - that is 1 with 123456 zeroes). So, **simple iteration loop is not acceptable.**
* Program has to terminate with an error in 1 s, if given any invalid input. Eg. 1.23e (invalid), or 1.23e1 (equals to 12.3 - not an integer)
* It's ok to use public BigNum library to parse/store numbers and do simple mathematical operations on them (+-\*/ exp). No byte-penalty applied.
* Shortest code wins.

# TL;DR

* Input: bignum integer
* Output: digit at that position in infinite row `123456789101112131415...`

# Some acceptance test cases

in notation "Input: Output". All of them should pass.

* 1: 1
* 999: 9
* 10000000: 7
* 1e7: 7 (same as row above)
* 13498573249827349823740000191: 6
* 1.1e10001: 5
* 1e23456: 5
* 1.23456e123456: 4
* 1e1000000: 0
* 1.23e: error (invalid syntax)
* 0: error (out of bounds)
* 1.23e1: error (not an integer)

# Bonus!

Output digit position number inside the number, and output number itself. For example:

* `13498573249827349823740000191: 6 24 504062383738461516105596714`
    + That's digit '6' at position 24 of number '50406238373846151610559**6**714'
* `1e1000000: 0 61111 1000006111141666819445...933335777790000`
    + Digit '0' at position 61111 of 999995-digit long number I'm not going to include here.

If you fulfill the bonus task, multiply size of your code by 0.75

# Credit

This task was given at one of devclub.eu gatherings in year 2012, without large number requirement. Hence, most answers submitted were trivial loops.

# Have fun!

# Answer
> 12 votes
# CJam, 78 bytes

```
r_A,s-" e . .e"S/\a#[SSS"'./~'e/~i1$,-'e\]s"0]=~~_i:Q\Q=Qg&/
s,:L{;QAL(:L#9L*(*)9/-_1<}g(L)md_)p\AL#+_ps=

```

The program is 104 bytes long and qualifies for the bonus.

The newline is purely cosmetic. The first line parses the input, the second generates the output.

Try it online!

### Idea

For any positive integer **k**, there are **9×10k-1** positive integers of exactly **k** digits (not counting leading zeroes). Thus, if we concatenate all of them, we obtain an integer of **9×n×10k-1**.

Now, concatenating all integers of **n** or less digits yields an integer of

digits.

For a given input **q**, we try determine the highest **n** such that the above expression is smaller than **q**. We set **n := ⌈log10q⌉-1**, then **n := ⌈log10q⌉-2**, etc. until the desired expression becomes smaller than **q**, subtract the resulting expression from **q** (yielding **r**) and save the last value of **n** in **l**.

**r** now specifies the index in the concatenation of all positive integers of **l+1** digits, which means that the desired output is the **r%(l+1)**th digit of the **r/(l+1)**th integer of **l+1** digits.

### Code (input parsing)

```
r_          e# Read from STDIN and duplicate.
A,s-        e# Remove all digits.
" e . .e"S/ e# Push ["" "e" "." ".e"].
\a#         e# Compute the index of the non-digit part in this array.

[SSS"'./~'e/~i1$,-'e\]s"0]

            e# Each element corresponds to a form of input parsing:
            e#   0 (only digits): noop
            e#   1 (digits and one 'e'): noop
            e#   2 (digits and one '.'): noop
            e#   3 (digits, one '.' then one 'e'):
            e#     './~    Split at dots and dump the chunks on the stack.
            e#     'e/~    Split the and chunks at e's and dump.
            e#     i       Cast the last chunk (exponent) to integer.
            e#     1$      Copy the chunk between '.' and 'e' (fractional part).
            e#     ,-      Subtract its length from the exponent.
            e#     'e\     Place an 'e' between fractional part and exponent.
            e#     ]s      Collect everything in a string.
            e#   -1 (none of the above): push 0

~           e# For s string, this evaluates. For 0, it pushes -1.
~           e# For s string, this evaluates. For -1, it pushes 0.
            e# Causes a runtime exception for some sorts of invalid input.
_i:Q        e# Push a copy, cast to Long and save in Q.
\Q=         e# Check if Q is numerically equal to the original.
Qg          e# Compute the sign of Q.
&           e# Logical AND. Pushes 1 for valid input, 0 otherwise.
/           e# Divide by Q the resulting Boolean.
            e# Causes an arithmetic exception for invalid input.

```

### Code (output generation)

```
s,:L     e# Compute the number of digits of Q and save in L.
{        e# Do:
  ;      e#   Discard the integer on the stack.
  Q      e#   Push Q.
  AL(:L# e#   Push 10^(L=-1).
  9L*(   e#   Push 9L-1.
  *)     e#   Multiply and increment.
  9/     e#   Divide by 9.
  -      e#   Subtract from Q.
  _1<    e#   Check if the difference is non-positive.
}g       e# If so, repeat the loop.
(        e# Subtract 1 to account for 1-based indexing.
L)md     e# Push quotient and residue of the division by L+1.
_)p      e# Copy, increment (for 1-based indexing) and print.
\AL#+    e# Add 10^L to the quotient.
_p       e# Print a copy.
s        e# Convert to string.
2$=      e# Retrieve the character that corresponds to the residue.

```

# Answer
> 5 votes
# CJam, 75 * 0.75 = 56.25

This is quite fast, one iteration per digit of the number that contains the desired position. I'm sure it can be golfed a lot more, it's quite crude as it is.

```
q~_i_@<{0/}&:V9{VT>}{T:U;_X*T+:T;A*X):X;}w;U-(_X(:X/\X%10X(#@+s_2$\=S+@)S+@

```

Give the position as input, the output is:

```
<digit> <position> <full number>

```

Try it online.

---
Tags: code-golf, number, sequence, number-theory
---