title: Write a FAST word equation solver

text:
# Question
Title: Write a FAST word equation solver
This question is similar to Write a word equation solver by David Frank **but different in three important ways:** (1) David asked for just the first solution found, and I am asking for all the solutions. (2) I am asking to output the time required to solve the puzzle. And (3), it is a completely different undertaking to write a program designed to be fast compared with one designed to be short. A brute force method is probably best for code golf, but will not beat my ?amazing? time of 0.15 seconds. -I say "amazing" only to encourage other to try it out. I'm sure mine won't be the fastest.

(I'm going to copy a lot of the text from that question.)

**Introduction**

Consider the following example:

```
  CODE
+ GOLF
——————
 GREAT

```

This is an equation where each letter represents a decimal digit and the words represent natural numbers (similar letters represent similar digits and different letters represent different digits). The task is to match each letter with its digit value so that the equation is correct. **One of the four** solutions for the equation above is:

```
  9265
+ 1278
——————
 10543

```

**Your task**

Your task is to write a program or function to **find ALL of the answers** to such a word equation. Your program should output all the answers and the time it took to find them in seconds.

**Input**

The input will be something like this, two words added together to make a third word.

Example:

1. CODE+GOLF=GREAT
2. AA+BB=CC

Spaces are omitted and only letters between capital A and Z will be used (no special or small letters). This string can be read from the standard input, from a file, or as a function parameter.

**Output**

The output should look something like this. To take luck out of the competition, your program must list all the solutions.

```
time = XX.XXX seconds
(1) 9265+1278=10543
(2) 9275+1268=10543
(3) 9428+1437=10865
(4) 9438+1427=10865

```

**Rules**

1. **Similar letters represent similar digits and different letters represent different digits**
2. To make things easier, you can assume that numbers can or don't start with a leading zero, it's up to you. The four answers I got for the sample problem assume numbers do not start with leading zeros.
3. You can use any language and the standard library of the chosen language (no external libs)
4. You cannot connect to any resources on the internet (why would you anyways?)
5. So the goal here is speed, but of coarse that depends on what computer you use. In order to account for the different speed of different computers, you could run my example on your computer and then report how many times faster or slower yours is than my sample answer.
6. **Please explain how your code works.**

**Example in JavaScript**

http://goo.gl/TdQczX

# Answer
> 6 votes
# Python3, 0.03 seconds:

```
def f(a, b, r, c = {}, s = [], k = 0, l = [], A = [], B = []):
   if not a and not b:
      yield f"{''.join(map(str, A))}+{''.join(map(str, B))}={''.join(map(str, l))}"
      return
   for x in c.get(a[-1], range(10)):
      if a[-1] in c or x not in s:
         _c, _s = {**c, a[-1]:[x]}, s+[x]
         for y in _c.get(b[-1], range(10)):
             if b[-1] in _c or y not in _s:
                n_c, v = {**_c, b[-1]:[y]}, k+x+y
                n_s = _s+[y]
                if a[:-1] and b[:-1]:
                    _v, _k = v%10, v//10
                    if [_v] == n_c.get(r[-1], [_v])and (r[-1] in n_c or _v not in n_s):
                        yield from f(a[:-1], b[:-1], r[:-1], {**n_c, r[-1]:[_v]}, n_s+[_v], _k, [_v]+l, [x]+A, [y]+B)
                else:
                    if len(str(v)) == len(r):
                        F = 1
                        for J, K in zip(r[::-1], str(v)[::-1]):
                            if n_c.get(J, [int(K)]) == [int(K)] and (J in n_c or int(K) not in n_s):
                               n_c[J] = [int(K)]
                               n_s = n_s + [int(K)]
                            else:
                               F = 0
                               break
                        if F: yield from f(a[:-1], b[:-1], '', n_c, n_s, 0, [v]+l, [x]+A, [y]+B)

t = time.time()
result = [*f('CODE', 'GOLF', 'GREAT')]
print(time.time() - t)
print(result)

```

Try it online!

# Answer
> 4 votes
# C++, 10000× faster (~20 µs)

```
#include <stdio.h>
#include <time.h>
#include <algorithm>

// digits
typedef int digit_t;
const digit_t BASE = 10;
typedef unsigned digit_mask_t;
inline char format_digit(digit_t d) { return '0' + d; }

// letters
typedef int letter_t;
const letter_t ALPHABETSIZE = 26;
typedef unsigned letter_mask_t;
inline bool is_letter(char c) { return unsigned(c - 'A') < 26u; }
inline letter_t parse_letter(char c) { return letter_t(c - 'A'); }

// terms
typedef int term_t;
inline term_t term_abs(term_t x) { return x < 0 ? -x : x; }

bool parse_formula(const char* formula, term_t coeffs[ALPHABETSIZE], letter_mask_t* ppresent, letter_mask_t* pleading) {
    // Convert BA+BB=CCC into A + 21*B - 111*C = 0.
    letter_mask_t present = 0, leading = 0;
    const char* p = formula;
    term_t side = +1, place = +1;
    for (;;) {
        const char* r;
        for (r = p; is_letter(*r); ++r) {}
        if (p < r)
            leading |= letter_mask_t(1) << parse_letter(*p);
        for (const char* q = r; q != p; --q) {
            letter_t l = parse_letter(q[-1]);
            coeffs[l] += place;
            present |= letter_mask_t(1) << l;
            place *= BASE;
        }
        p = r;
        switch (*p++) {
            case 0:
                *ppresent = present; *pleading = leading; return true;
            case '+':
                place = +side; break;
            case '-':
                place = -side; break;
            case '=':
                if (side < 0)
                    return false;
                place = side = -1;
                break;
            default:
                return false;
        }
    }
}

struct Var {
    digit_t value;
    term_t coeff;
    digit_t minval;  // 0 or 1
    letter_t name;
};

class Solver {
    const char* formula;
    letter_t num_vars;
    Var vars[BASE];
    void solve2(Var*, digit_mask_t, term_t, term_t);
public:
    bool solve(const char* formula);
};

bool Solver::solve(const char* formula) {
    this->formula = formula;
    term_t coeffs[ALPHABETSIZE] = {0};
    letter_mask_t present, leading;
    if (!parse_formula(formula, coeffs, &present, &leading))
        return false;
    // sort the used letters by magnitude of their coefficient
    letter_t letters[BASE];
    letter_t num_vars = 0;
    for (letter_t i = 0; i < ALPHABETSIZE; ++i) {
        if (present & (letter_mask_t(1) << i)) {
            if (num_vars == BASE)
                return false;
            letters[num_vars++] = i;
        }
    }
    if (num_vars == 0)
        return false;
    this->num_vars = num_vars;
    std::sort(letters, letters + num_vars, [&](letter_t a, letter_t b) { return term_abs(coeffs[a]) < term_abs(coeffs[b]); });
    // initialize tables
    term_t bounds[2] = {0};
    for (letter_t i = 0; i < num_vars; ++i) {
        vars[i].name = letters[i];
        vars[i].minval = digit_t((leading >> letters[i]) & 1);
        term_t coeff = vars[i].coeff = coeffs[letters[i]];
        bounds[coeff > 0] += coeff * (BASE - 1);
    }
    // call the recursive solver
    solve2(vars + num_vars - 1, 0, bounds[0], bounds[1]);
    return true;
}

void Solver::solve2(Var* pos, digit_mask_t digits_used, term_t lower_bound, term_t upper_bound) {
    term_t coeff = pos->coeff;
    digit_t d = BASE - 1, e = pos->minval;
    // adjust bounds to reflect a digit equal to BASE-1, instead of anything in [0,BASE)
    if (coeff < 0)
        upper_bound += coeff * d;
    else
        lower_bound += coeff * d;
    do {
        if (lower_bound <= 0 && upper_bound >= 0 && !(digits_used & (digit_mask_t(1) << d))) {
            pos->value = d;
            if (pos == vars) {
                // print the solution
                char digit_chars[ALPHABETSIZE];
                for (letter_t i = 0; i < num_vars; ++i)
                    digit_chars[vars[i].name] = format_digit(vars[i].value);
                for (const char* p = formula; *p; ++p)
                    putchar(is_letter(*p) ? digit_chars[parse_letter(*p)] : *p);
                putchar('\n');
            } else {
                solve2(pos - 1, digits_used | (digit_mask_t(1) << d), lower_bound, upper_bound);
            }
        }
        lower_bound -= coeff;
        upper_bound -= coeff;
    } while (--d >= e);
}

int main(int argc, char **argv) {
    int code = 0;
    for (int i = 1; i < argc; ++i) {
        puts(argv[i]);
        clock_t t = clock();
        code |= !Solver().solve(argv[i]);
        t = clock() - t;
        printf("%f\n", double(t) / CLOCKS_PER_SEC);
    }
    return code;
}

```

Attempt This Online!

This is roughly 10,000 times faster than JeffSB's solver and 2,500 times faster than Ajax1234's solver on my machine on the problem `CODE+GOLF=GREAT`. The speed ratio varies widely with the problem. For `FIFTY+STATES=AMERICA`, the JeffSB/me ratio is 25,000, while for `CORRECTS+REJECTED=MATTRESS` it's about 25.

The algorithm is quite different. Neither JeffSB nor Ajax1234 explained theirs, but it appears they both do digitwise addition from right to left. This program converts a problem like `TO+GO=OUT` into a formula like \\$-98 O + 10 G - 10 U + 9 T = 0\\$, with the terms sorted by absolute value. For each term from left to right, for each possible value of that digit, it computes upper and lower bounds for the sum by assuming that every later digit is 0 or 9. If the bounds include 0 then it recurses.

Since it doesn't cost any time, this program supports a more general set of alphametics with arbitrarily many terms on both sides of the `=`, and subtraction as well as addition. It can very quickly solve problems like `NINETEEN+NINETEEN+TEN+TEN+TEN+TEN+NINE+NINE+NINE+NINE+NINE+ONE+ONE+ONE+...=THOUSAND` where there are 877 `ONE`s.

I tried computing slightly more sophisticated bounds, and rewriting the recursive function as an iterative one, but both changes only improved performance by 1-2%, and complicated the code, so I reverted them.

<sup>(Sources for example problems: Mike Keith, Michael Hartley)</sup>

# Answer
> 1 votes
# Python 3, \<5ms

```
def solver(eqn, soln_format = "eqn"):
    #get weights
    weight = -1
    weights = {}
    for char in reversed(eqn):
        if char=='=':
            weight=1
            continue
        if char=='+':
            if weight>0:
                weight=1
            else:
                weight=-1
            continue
        if char not in weights:
            weights[char] = 0
        weights[char]+= weight
        weight*=10

    assert len(weights) <= 10
    weights_sorted = list(weights.values()) + [0]*(10-len(weights.values()))
    weights_sorted.sort()

    _, order = zip(*sorted(zip(weights_sorted, range(10)), key=lambda x: abs(x[0]), reverse=True)) #abs sorted order
    order_list = [num - sum(i<num for i in order[:idx]) for idx, num in enumerate(order)] #because indexes change
    order_list = order_list[:len(weights.values())] #to ignore zeros
    order_list.reverse() #to pop and append like a stack

    for soln in backtrack(0, weights_sorted.copy(), order_list, list(reversed(range(10))), []):
        weights_copy = weights.copy()
        weight_soln_pair = [(weights_sorted[i],num) for i,num in zip(order, soln)]
        assert sum(i*j for i,j in weight_soln_pair) == 0, "Major error"
        final_soln = {}
        for weight_val, soln_val in weight_soln_pair:
            for char, weight in weights_copy.items():
                if weight == weight_val:
                    final_soln[char] = soln_val
                    del weights_copy[char]
                    break

        if soln_format == "eqn":
            #CONVERT TO EQN
            eqn_copy = eqn
            for k, v in final_soln.items():
                eqn_copy = eqn_copy.replace(k, str(v))
            yield eqn_copy
        elif soln_format == "dict":
            yield final_soln

def backtrack(val, weights, test_order, remaining, soln):
    #Check if end
    if len(test_order)==0:
        if val==0:
            yield soln
        return False
    #Check if possible
    if sum([i*j for i,j in zip(remaining, reversed(weights))]) + val < 0: #max
        return False
    if sum([i*j for i,j in zip(remaining, weights)]) + val > 0: #min
        return False
    #Backtrack for each digit
    order = test_order.pop()
    weight = weights.pop(order)
    for i, num in enumerate(remaining):
        del remaining[i]
        yield from backtrack(val+num*weight, weights, test_order, remaining, soln + [num])
        remaining.insert(i, num)
    weights.insert(order, weight)
    test_order.append(order)
    return False

```

does pretty much the same as benrg's answer, but in python and does not remove the solutions with leading zeros

```
%%timeit -n 1 -r 1
print([*solver('CODE+GOLF=GREAT')])

```

---

```
['9428+1437=10865', '9438+1427=10865', '9265+1278=10543', '9275+1268=10543', '8653+0671=09324', '8673+0651=09324', '8643+0672=09315', '8673+0642=09315', '8612+0635=09247', '8632+0615=09247', '7642+0651=08293', '7652+0641=08293', '6918+0934=07852', '6938+0914=07852', '6918+0925=07843', '6928+0915=07843', '5928+0943=06871', '5948+0923=06871', '3857+0862=04719', '3867+0852=04719', '3612+0685=04297', '3682+0615=04297', '2918+0956=03874', '2958+0916=03874', '2918+0947=03865', '2948+0917=03865', '2846+0851=03697', '2856+0841=03697']
4.63 ms ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)

```

notebook link

---
Tags: math, fastest-code, puzzle-solver
---


title: Find the area of a polygon

text:
# Question
Title: Find the area of a polygon
Given consecutive side lengths `s1, s2, s3... s_n` of an n-gon inscribed in a circle, find its area. You may assume that the polygon exists. In addition, the polygon will be convex and not self-intersecting, which is enough to guarantee uniqueness. Built-ins that specifically solve this challenge, as well as built-in functions that calculate the circumradius or circumcenter, are banned (this is different from a previous version of this challenge).

Input: The side lengths of the cyclic polygon; may be taken as parameters to a function, stdin, etc.

Output: The area of the polygon.

The answer should be accurate to 6 decimal places and must run within 20 seconds on a reasonable laptop.

This is code golf so shortest code wins!

Specific test cases:

```
[3, 4, 5] --> 6
[3, 4, 6] --> 5.332682251925386
[3, 4, 6, 7] --> 22.44994432064365
[5, 5, 5, 5] --> 25
[6, 6, 6, 6, 6] --> 61.93718642120281
[6.974973020933265, 2.2393294197257387, 5.158285083300981, 1.4845682771595603, 3.5957940796134173] --> 21.958390804292847
[7.353566082457831, 12.271766915518073, 8.453884922273897, 9.879017670784675, 9.493366404245332, 1.2050010402321778] --> 162.27641678140589

```

Test case generator:

```
function randPolygon(n) {
  var left = 2 * Math.PI;
  var angles = [];
  for (var i = 0; i < n - 1; ++i) {
    var r = Math.random() * left;
    angles.push(r);
    left -= r;
  }
  angles.push(left);
  var area = 0;
  var radius = 1 + Math.random() * 9;
  for (var i = 0; i < angles.length; ++i) area += radius * radius * Math.sin(angles[i]) / 2;
  var sideLens = angles.map(function(a) {
    return Math.sin(a / 2) * radius * 2;
  });

  document.querySelector("#radius").innerHTML = radius;
  document.querySelector("#angles").innerHTML = "[" + angles.join(", ") + "]";
  document.querySelector("#inp").innerHTML = "[" + sideLens.join(", ") + "]";
  document.querySelector("#out").innerHTML = area;

  draw(angles);
}

function draw(angles) {
  var canv = document.querySelector("#diagram"),
    ctx = canv.getContext("2d");
  var size = canv.width
  ctx.clearRect(0, 0, size, size);
  ctx.beginPath();
  ctx.arc(size / 2, size / 2, size / 2, 0, 2 * Math.PI, true);
  ctx.stroke();
  ctx.beginPath();
  ctx.moveTo(size, size / 2);
  var runningTotal = 0;
  for (var i = 0; i < angles.length; ++i) {
    runningTotal += angles[i];
    var x = Math.cos(runningTotal) * size / 2 + size / 2;
    var y = Math.sin(runningTotal) * size / 2 + size / 2;
    ctx.lineTo(x, y);
  }
  ctx.stroke();
}
document.querySelector("#gen").onclick = function() {
  randPolygon(parseInt(document.querySelector("#sideLens").value, 10));
}
```

```
<div id="hints">
  <p><strong>These are to help you; they are not part of the input or output.</strong>
  </p>
  Circumradius:
  <pre id="radius"></pre>
  Angles, in radians, of each sector (this are NOT the angles of the polygon):
  <pre id="angles"></pre>
</div>
<hr>
<div id="output">
  Input:
  <pre id="inp"></pre>
  Output:
  <pre id="out"></pre>
</div>
<hr>
<div id="draw">
  Diagram:
  <br />
  <canvas id="diagram" width="200" height="200" style="border:1px solid black"></canvas>
</div>

Number of side lengths:
<input type="number" id="sideLens" step="1" min="3" value="3" />
<br />
<button id="gen">Generate test case</button>
```

# Answer
# Python 2, ~~195~~ 191 bytes

```
from math import*
C=sorted(input());l,h=0,1/max(C)
while h-l>2e-16:m=(l+h)/2;a=[asin(c*m)for c in C[:-1]];f=pi-sum(a);l,h=[l,m,h][sin(f)/m>C[-1]:][:2]
print sum(sin(2*t)/l/l for t in a+[f])/8

```

Uses a binary search to find the inverse diameter, then calculates the area of each segment by the angle/radius.

It finds the radius by first summing all but the largest chord angle, and checking the remaining angle to the remaining chord. Those angles are then also used to compute the area of each segment. A segment's area can be negative, if it's angle is bigger than 180 degrees. We do a binary search over the inverse diameter so the domain is bounded and well-behaved.

Readable implementation:

```
def segment_angles(line_segments, invd):
    return [2*math.asin(c*invd) for c in line_segments]

def cyclic_ngon_area(line_segments):
    line_segments = list(sorted(line_segments))
    lo, hi = 0, 1/max(line_segments)
    while hi - lo > 2e-16:
        mid = (lo + hi) / 2
        angles = segment_angles(line_segments[:-1], mid)
        angles.append(2*math.pi - sum(angles))
        if math.sin(angles[-1]/2) / mid > line_segments[-1]:
            lo = mid
        else:
            hi = mid
    return sum([math.sin(a)/lo/lo/8 for a in angles])

```
> 5 votes

# Answer
# PARI/GP, 182 bytes

```
A(v)=n=#s=vecsort(v);g=1^s;h=sum(k=1,n-1,asin(s[k]/S=s[n]))<Pi/2;g[n]-=2*h;d=solve(D=S,S/(vecsum(s)/2/S-1),sum(k=1,n,g[k]*asin(s[k]/D))-Pi*!h);sum(k=1,n,g[k]*s[k]*sqrt(d^2-s[k]^2))/4

```

Using @alephalpha's hints that global variables can be used and his improved chained assignments, significantly shorter code is possible. Also an unnecessary factor 8 in calculation of Dmax was removed.

## Version with comments

```
AreaCyclicPolygon(VectorofSidelenghts) =
{
  my( s = vecsort(VectorofSidelenghts), \\ allows access to longest side
                                        \\ and loop over shorter sides
      n = #s,
      S = s[n],    \\ assignment postponed into loop in golfed code
      g = vector(n,i,1), \\ Auxiliary vector of ones
      d,
      h = sum ( k=1, n-1, asin(s[k]/S)) < Pi/2, \\ determine whether the triangle
                                                   \\ with longest side makes an angle > Pi.
      Dmax = S/sqrt(vecsum(s)/2/S - 1) \\ upper limit of diameter from asymptotic
                                             \\ expansion showing 1/sqrt(eps) dependency.
                                             \\ In "golfed" version sqrt can be ommitted
                                             \\ drastically overestimating Dmax; solve still works
    );
  g[n] -= 2*h; \\ factor = -1 for largest triangle
               \\ when the polygon only occupies less than half of the circle
  d = solve ( D=s[n], Dmax,
              sum (k=1, n, g[k]*asin(s[k]/D)) - Pi*!h); \\ solve sum of angles equation
                                                        \\ including special case of
                                                        \\ large angle for longest side
  sum (k=1, n, g[k]*s[k]*sqrt(d^2 - s[k]^2))/4  \\ return value: use solution for d in sum
                                                \\ of triangle areas, again with potentially
                                                \\ negative contribution of triangle
                                                \\ with longest side
};

```

## Examples

```
AreaCyclicPolygon([3,4,5])
 6.000000000000000000
AreaCyclicPolygon([3,4,6])
 5.3326822519253854377215978803358864040
AreaCyclicPolygon([0.25,0.25,0.499999])
 0.00012499968750010937502343751074219391159
AreaCyclicPolygon([5,5,5,5])
 25.000000000000000000000000000000000000
AreaCyclicPolygon([6,6,6,6,6])
 61.937186421202809219324431185989945578
AreaCyclicPolygon([1e6,1e6,2e6-1])
 999999375.00005468750292968783569307190

```

## Note on estimating the maximum diameter

Regardless of whether the diameter (or equivalently the radius) is calculated using bisection or with a function for solving a non-linear equation (like PARI's solve here), a bracketing interval is required for the solution value. Trivially, the diameter cannot be smaller than the longest side. However, since the polygon can degenerate when the sum of the shorter sides approaches the longest side, the diameter of the polygon can become arbitrarily large. In order to estimate this diameter, it is sufficient to use a triangle as a model. From the well-known Heron formula for the area A one gets the radius $$ r(a,b,c) = \frac{a b c}{\sqrt{(a+b-c) (a-b+c) (-a+b+c) (a+b+c)}} $$ If one assumes a model triangle \\$\left(\frac{1}{4},\frac{1}{4},\frac{1}{2}-\epsilon \right)\\$ normalized to an approximate perimeter of 1 with a scaled length deficit \\$\epsilon\\$ of the longest side, then r becomes $$ r = \frac{\frac{1}{2}-\epsilon }{16 \sqrt{\left(\frac{1}{2}-\epsilon \right)^2 (1-\epsilon ) \epsilon }} $$ Assuming \\$\epsilon\\$ to be small, r can be expanded r in a series $$ r = \frac{1}{16 \sqrt{\epsilon }}+\frac{\sqrt{\epsilon }}{32}+\frac{3 \epsilon ^{3/2}}{128}+O\left(\epsilon ^{5/2}\right) $$ The leading term contains the singularity \\$\frac{1}{\sqrt{\epsilon }}\\$, which must be taken into account when calculating the upper bound. It doesn't matter whether you use the circumference or the longest side to scale back.

Whether one computes \\$\epsilon\\$ as $$ \epsilon = \frac{a+b+c}{2 c}-1 = \frac{a+b-c}{2 c} $$ which is the **vecsum(s)/2/S - 1** in the program, or as $$ \epsilon = 1-\frac{2 c}{a+b+c} $$ makes no essential difference for small \\$\epsilon\\$.
> 5 votes

# Answer
# Octave, 89 bytes

```
r=sum(s=input(''));while sum(a=asin(s/2/r))<pi r*=1-1e-4;b=a;end;disp(sum(cos(b).*s/2*r))

```

## Explanation

The angle `a` spanned by a segment of length `s` is `2*asin(s/2/r)`, given a circumradius `r`. Its area is `cos(a)*s/2*r`.

### Algorithm

1. Set `r` to something too large, such as the perimeter.
2. If the cumulated angle is smaller than `2pi`, reduce `r` and repeat step 2.
3. Calculate the area.
> 0 votes

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


title: Make a super acrostic

text:
# Question
Title: Make a super acrostic
### Background

Celebrating the release of Dyalog APL 16.0, where the solution to this problem is `{⊢⌺(≢⍵)⊢⍵}`Explanation

### Task

Given a printable ASCII string **of odd length** *n*, make an *n* × *n* square with the string centered horizontally, duplicated to be centered vertically, and with acrostics of the same string in each row and column. Note that all but the centered strings will be cut off to keep the square's size *n* × *n*.

Explanation of your code will be much appreciated.

### Rules

1. You may have trailing whitespace and newlines (this includes the lower-right triangle)
2. You may return a list of strings

### Example using the string `ABXCD`:

* *n* is 5. First we draw the two centered strings, one horizontal and one vertical:

```
┌─────┐
│  A  │
│  B  │
│ABXCD│
│  C  │
│  D  │
└─────┘

```

(5 × 5 bounding box added for clarity)
* Then we place all the possible acrostics, horizontally and vertically:

```
       A
      AB
  ┌─────┐
  │  ABX│CD
  │ ABXC│D
  │ABXCD│
 A│BXCD │
AB│XCD  │
  └─────┘
   CD
   D

```
* Finally, we return only what is inside the bounding box:

```
  ABX
 ABXC
ABXCD
BXCD
XCD

```

### Test cases

`World`:

```
  Wor
 Worl
World
orld
rld

```

`mississippi`:

```
     missis
    mississ
   mississi
  mississip
 mississipp
mississippi
ississippi
ssissippi
sissippi
issippi
ssippi

```

`Pneumonoultramicroscopicsilicovolcanoconiosis`:

```
                      Pneumonoultramicroscopi
                     Pneumonoultramicroscopic
                    Pneumonoultramicroscopics
                   Pneumonoultramicroscopicsi
                  Pneumonoultramicroscopicsil
                 Pneumonoultramicroscopicsili
                Pneumonoultramicroscopicsilic
               Pneumonoultramicroscopicsilico
              Pneumonoultramicroscopicsilicov
             Pneumonoultramicroscopicsilicovo
            Pneumonoultramicroscopicsilicovol
           Pneumonoultramicroscopicsilicovolc
          Pneumonoultramicroscopicsilicovolca
         Pneumonoultramicroscopicsilicovolcan
        Pneumonoultramicroscopicsilicovolcano
       Pneumonoultramicroscopicsilicovolcanoc
      Pneumonoultramicroscopicsilicovolcanoco
     Pneumonoultramicroscopicsilicovolcanocon
    Pneumonoultramicroscopicsilicovolcanoconi
   Pneumonoultramicroscopicsilicovolcanoconio
  Pneumonoultramicroscopicsilicovolcanoconios
 Pneumonoultramicroscopicsilicovolcanoconiosi
Pneumonoultramicroscopicsilicovolcanoconiosis
neumonoultramicroscopicsilicovolcanoconiosis
eumonoultramicroscopicsilicovolcanoconiosis
umonoultramicroscopicsilicovolcanoconiosis
monoultramicroscopicsilicovolcanoconiosis
onoultramicroscopicsilicovolcanoconiosis
noultramicroscopicsilicovolcanoconiosis
oultramicroscopicsilicovolcanoconiosis
ultramicroscopicsilicovolcanoconiosis
ltramicroscopicsilicovolcanoconiosis
tramicroscopicsilicovolcanoconiosis
ramicroscopicsilicovolcanoconiosis
amicroscopicsilicovolcanoconiosis
microscopicsilicovolcanoconiosis
icroscopicsilicovolcanoconiosis
croscopicsilicovolcanoconiosis
roscopicsilicovolcanoconiosis
oscopicsilicovolcanoconiosis
scopicsilicovolcanoconiosis
copicsilicovolcanoconiosis
opicsilicovolcanoconiosis
picsilicovolcanoconiosis
icsilicovolcanoconiosis

```

### Acknowledgements

Thanks to dzaima, Leaky Nun, Mr. Xcoder for everything but the very idea of this challenge.

# Answer
# Python 2, 60 bytes

```
n=input();l=len(n)
for i in range(l):print(l/2*' '+n)[i:l+i]

```

Try it online!
> 10 votes

# Answer
# MATL, 8 bytes

```
nXyPGZ+c

```

**Try it online!**

### Explanation

```
n    % Implicit input. Number of elements
Xy   % Identity matrix of that size
P    % Flip vertically
G    % Push input again
Z+   % 2D convolution, maintaining size
c    % Convert to char (char 0 is displayed as space). Implicitly display

```
> 5 votes

# Answer
# Retina, ~~70~~ 59 bytes

```
.
$.'$* $_$.`$* ¶
(?=((....))+)(?<-1>.)+(.*?)(?<-2>.)+¶
$3¶

```

Try it online! Edit: Saved 11 bytes with some help from @MartinEnder. Explanation: The first stage repeats the input once for each character, padding it appropriately on each line to get the shear. The last stage then removes 25% from each side to produce the desired result.
> 4 votes

# Answer
# Java 8, ~~120~~ 103 bytes

```
s->{int l=s.length(),i=l/2;for(;i-->0;s=" "+s+" ");for(;++i<l;System.out.println(s.substring(i,l+i)));}

```

-17 bytes thanks to *@OlivierGrégoire*.

**Explanation:**

Try it here.

```
s->{                      // Method with String parameter and no return-type
  int l=s.length(),       //  Length of the input-String
      i=l/2;              //  Temp index-integer (starting at halve the length floored)
  for(;i-->0;             //  Loop (1) from `l/2` to 0 (exclusive)
    s=" "+s+" "           //   Add spaces before and after the input-String
  );                      //  End of loop (1)
                          //  (If the input was "World", it is now "  World  ")
  for(;++i<l;             //  Loop (2) from 0 to `l` (exclusive)
    System.out.println(   //   Print:
      s.substring(i,      //    Substring of the modified input from `i`
                    l+i)  //    to `l+i` (exclusive)
    )                     //   End of print
  );                      //  End of loop (2)
}                         // End of method

```
> 3 votes

# Answer
## Haskell, ~~64~~ 62 bytes

```
f s|l<-length s=take l$take l<$>scanr(:)""(([2,4..l]>>" ")++s)

```

Try it online! How it works:

```
l<-length s               -- let l be the length of the input string

      ([2,4..l]>>" ")     -- take l/2 spaces and
                     ++s  -- append s
    scanr(:)""            -- make a list of the inits of the above string, e.g.
                          -- "  world" -> ["  world"," world","world","orld"...]
  take l <$>              -- take the first l chars of each string
take l                    -- and the first l strings

```
> 3 votes

# Answer
## SWI Prolog, 234 bytes

```
h(_,0,_,_,[]).
h(T,N,S,L,[H|U]):-sub_string(T,S,L,_,H),M is N-1,A is S+1,h(T,M,A,L,U).
s(T,R):-string_length(T,L),findall('_',between(1,L,_),A),string_chars(B,A),
                   string_concat(B,T,C),string_concat(C,B,D),S is L-((L-1)/2),h(D,L,S,L,R).

```

Maybe try online here: http://swish.swi-prolog.org/p/hEKigfEl.pl

NB.

1. The last line is one long line, I added a linebreak and spaces here just to avoid horizontal scrollbar in this answer.
2. The question involves spaces for padding, but Swish online doesn't show them cleanly because of HTML rendering interactions, you have to view source in browser dev tools to check they are present (they are). I've changed the padding to be `_` here, as it demonstrates it working and doesn't affect the byte count.

Examples running in Swish:

Approach, basically the first thing I could make work at all, and doubtless a skilled Prolog user could shorten it a lot:

* Given a string of length L, the output will have L lines, and each line will be L characters long, so 'L' shows up a lot. Countdown from L to 0 for the number of lines, L for the substring length for each line.
* Create a padding string of L spaces (underscores) long, add it to both ends of the input string, because that's a simple length which is definitely going to be enough padding.
* Calculate a starting offset into this triple-length string and recurse, generating a substring each time, into a list of results.

Explained and commented code (might not run), read from `superacrostic()` down, then `helper()` main body, then `helper()` base case:

```
% helper function recursive base case,
% matches when counter is 0, other input has any values, and empty list 'output'.
helper(_,0,_,_,[]).

% helper function recursively generates substrings
% matching a padded input Text, a line Counter
% a substring starting Offset, a line Length,
% and an output list with a Head and a Tail
helper(Text, Counter, Offset, LineLength, [Head|Tail]):-

    sub_string(Text, Offset, LineLength, _, Head),    % The list Head matches
                                                      % a substring of Text starting
                                                      % from Offset, of LineLength chars
                                                      % and

    NextCounter is Counter-1,                         % decrement the Counter

    NextOffset is Offset+1,                           % increment the offset

    helper(Text, NextCounter, NextOffset, LineLength, Tail).  % Recurse for list Tail

% Result is a superacrostic for an input string Text, if
superacrostic(Text, Result):-
    string_length(Text, Length),                   % Length is length of input,
                                                   % Text = 'ABXCD', Length = 5
                                                   % and

    findall('_',between(1,Length,_),PaddingList),  % PaddingList is a list of padding
                                                   % chars Length items long,
                                                   % ['_', '_', '_', '_', '_']
                                                   % and

    string_chars(PaddingString, PaddingChars),     % PaddingString is the string from
                                                   % joining up that list of chars
                                                   % '_____'
                                                   % and

    string_concat(PaddingString, Text, Temp),      % Temp is Text input with a
                                                   % padding prefix
                                                   % Temp = '_____ABXCD'
                                                   % and

    string_concat(Temp, PaddingString, PaddedText), % PaddedText is Temp with
                                                    % a padded suffix
                                                    % Temp = '_____ABXCD_____'
                                                    % and

    S is Length - ((Length - 1) / 2),              % Starting offset S for the substring
                                                   % is just past the padding,
                                                   % then half the input length back
                                                   % '_____ABXCD_____'
                                                   %     |
                                                   % to start the first line,
                                                   % and

    helper(PaddedText, Length, S, Length, Result). % Result is the list generated from
                                                   % the helper function,

    % to recurse Length times for that many output rows, S starting offset,
    % Length linelength, and Result 'output'.

```
> 3 votes

# Answer
# 05AB1E, 11 bytes

```
g;úIvDIg£,À

```

Try it online!

**Explanation**

```
g;ú           # prepend len(input)/2 spaces to input
   Iv         # for each char of input do
     D        # duplicate current string
      Ig£     # take the first len(input) chars
         ,    # print
          À   # rotate the string to the left

```
> 2 votes

# Answer
## JavaScript (ES6), 75 bytes

```
f=(s,k=1,l=s.length)=>k>l?'':(' '.repeat(l)+s).substr(l/2+k,l)+`
`+f(s,k+1)

console.log(f("World"))
```
> 2 votes

# Answer
# APL (Dyalog Unicode), 10 chars = 22 bytes

```
{⊢⌺(≢⍵)⊢⍵}

```

Try it online!

`{``}` anonymous function where the argument is represented by

provide the covered area when

`⌺(``)` sliding a stencil of size

length of

the argument

on

the argument

The way this works is by letting each character form the middle of a string with the same length as the input, padding left or right as needed. Take e.g. `ABXCD`:

The string has five characters, so the stencil will have an "opening" that is five characters wide.

`┌──↓──┐` stencil opening with middle marker
`│ ABX│CD` let `A` be in the middle
`│ ABXC│D` then `B`
`│ABXCD|` etc.
`A|BXCD |`
`AB|XCD  |`
`└──↑──┘` final stencil position
> 2 votes

# Answer
# PHP, 98 bytes

```
for(;~($a=$argn)[$i++];)$i&1?$t.=substr($a,$i/2)."
":$t=($s.=" ").substr($a,0,-$i/2)."
$t";echo$t;

```

Try it online!
> 2 votes

# Answer
# , ~~14~~, 11 bytes

```
òlÙxHÄ$x>>ê

```

Try it online!

3 bytes saved thanks to @nmjmcman!

Hexdump:

```
00000000: f26c d978 48c4 2478 3e3e ea              .l.xH.$x>>.

```

Original approach (18 bytes):

```
ø..
Duu@"ñLÙxHÄ$x>

```

Explanation:

```
ò           " Recursively:
 l          "   Move one char to the right (this will break the loop if we move too far
  Ù         "   Duplicate this line down
   x        "   Delete the first character on this line
    H       "   Move to the first line
     Ä      "   Duplicate this line up
      $     "   Move to the end of this line
       x    "   And delete a character
        >>  "   Put one space at the beginning of this line
          ê "   And move to this column on the last line
            " (implicit) ò, end the loop.

```
> 2 votes

# Answer
# Japt, ~~19~~ ~~17~~ 14 bytes

*Saved 5 bytes thanks to @ETHproductions and @Shaggy*

```
¬£iSp½*Ul¹tYUl

```

Test it online! `-R` flag added to join with newlines (visibility purposes)

## Explanation

```
¬£iSp½*Ul¹tYUl
                U = Implicit input
¬               Split the input into an array of chars
 £              Map; At each char:
  i               Insert:
   S                Space " "
    p               repeated(
     ½*Ul           .5 * U.length times
         ¹          )
          t        Substring(
           Y         Index,
            Ul       U.length)

```
> 2 votes

# Answer
# PowerShell Core, 68 bytes

```
0..($L=($a="$args").Length-1)|%{-join(' '*($L/2)+$a)[($_..($_+$L))]}

```

Try it online!

### Ungolfed explanation

```
# Input string ABXCD
# -> indexes  0,1,2,3,4  string indexing and num of output lines.
# -> Pad with half-len of spaces __ABXCD.
# -> sliding window array of chars:
# __ABXCD
# |    |       0..4
#  |    |      1..5
#   |    |     2..6
#    |    |    3..7   (selecting indexes past the end returns $nulls, no error)
#     |    |   4..8

# joining those chars into a line

$Text = "$args"                            # script args array to string.
$L    = $Text.Length - 1                   # useful number

$Offsets = 0..$L                           # range array 0,1,2,3,.. to last offset

$Offsets | ForEach-Object {                # Offsets doubles as number of output lines

    $LinePadding = ' ' * ($L / 2)          # lead padding string __
    $PaddedText  = $LinePadding + $Text    # -> __ABXCD

    $Chars = $_..($_+$L)                   # windows 0..4, then 1..5, then 2..6, etc.
    $Line  = $PaddedText[$Chars]           #_,_,A,B,X then _,A,B,X,C then A,B,X,C,D etc.

    -join $Line                            # __ABX  then _ABXC then ABXCD etc.

}

```
> 2 votes

# Answer
# JavaScript (ES8), ~~66~~ ~~63~~ 62 bytes

Returns an array.

```
s=>[...s].map((_,x)=>s.padStart(l*1.5).substr(x,l),l=s.length)

```

---

## Try it

```
o.innerText=(f=
s=>[...s].map((_,x)=>s.padStart(l*1.5).substr(x,l),l=s.length)
)(i.value="Pneumonoultramicroscopicsilicovolcanoconiosis").join`\n`;oninput=_=>o.innerText=f(i.value).join`\n`
```

```
<input id=i><pre id=o>
```

---

## Explanation

```
s=>

```

Anonymous function taking the string as an argument via parameter `s`.

```
[...s]

```

Split the string to an array of individual characters.

```
l=s.length

```

Get the length of the string and assign it to variable `l`.

```
.map((_,x)=>                                        )

```

Map over the array, passing each element through a function, where `x` is the index of the current element.

```
s.padStart(l*1.5)

```

For each element, return the original string with spaces prepended until it's length is 1.5 times that of it's original length.

```
.substr(x,l)

```

Get the substring of length `l` beginning from the current element's index.
> 2 votes

# Answer
# Charcoal, 26 bytes

```
Ａ⁺¹÷Ｌθ²δＦδ⟦✂θι⁺ιδ⟧Ｆ∕θ²Ｃ¹±¹

```

Try it online! Link is to verbose version of code.
> 1 votes

# Answer
# Jelly, 11 bytes

```
LH⁶ẋ;ṫJḣ€LY

```

Try it online!

## How it works

```
LH⁶ẋ;ṫJḣ€LY   "ABXCD"
L             5
 H            2.5
  ⁶ẋ          "  "
    ;         "  ABXCD"
     ṫJ       ["  ABXCD"
               " ABXCD"
               "ABXCD"
               "BXCD"
               "XCD]
        ḣ€L   ["  ABX"
               " ABXC"
               "ABXCD"
               "BXCD"
               "XCD]
           Y  "  ABX
                ABXC
               ABXCD
               BXCD
               XCD"

```
> 1 votes

# Answer
# Haskell, ~~86~~ 70 bytes

This is (still) way too long, but thanks @bartavelle for reminding me that outputting a list of strings is acceptable too!

```
f s|m<-div(length s)2=take(2*m+1).(`drop`((*>)s" "++s))<$>[m+1..3*m+1]

```

Try it online!
> 1 votes

# Answer
# QBIC, 32 bytes

```
_L;|A=space$(a'\`2)+A[a|?_sA,b,a

```

Man, it's time for me to add `space$` to QBIC...

## Explanation

```
  ;             Read a cmd line parameter as A$
_L |            And take its length as 'a'
A=space$        Set A$ to a number of spaces
(a'\`2)           equal to its own length halved
+A                prepended to itself
[a|             FOR b= 1 to the length of A$
?_sA,b,a        Print a substring of our space-padded A$, starting at the b'th character, running for a chars

```

## Sample run

```
Command line: acknowledgement
       acknowle
      acknowled
     acknowledg
    acknowledge
   acknowledgem
  acknowledgeme
 acknowledgemen
acknowledgement
cknowledgement
knowledgement
nowledgement
owledgement
wledgement
ledgement
edgement

```
> 1 votes

# Answer
# Mathematica, 88 bytes

```
T=Table;Column@Reverse@T[T[" ",i]<>StringDrop[s=#,-i],{i,d=-⌊StringLength@s/2⌋,-d}]&

```
> 1 votes

# Answer
# Python 2, ~~76 74~~ 73 bytes

*-1 thanks to @FelipeNardiBatista*

Of course, not as short as the other Python answer, but it's worth trying a completely different method:

```
n=input();x=len(n)
for i in range(x):print((2*x-~i)*' '+n)[x+x/2:2*x+x/2]

```

Try it online! (with the 74 byte version)

This first generates the full String, and then slices it to fit the square.

---

# Explanation

```
n=input();                                                  - takes input and assigns it to a variable n
          x=len(n)                                          - assigns the length of the input to a variable x
for i in range(x):                                          - iterates on the range 0...x, with a variable i
                   print                                    - outputs the result
                         ((2*x-i-1)*' '+n)                  - creates the "diamond" string
                                          [x+x/2:2*x+x/2]   - crops the string to fit the box

```
> 1 votes

# Answer
# Excel VBA, 68 Bytes

### Golfed

Anonymous VBE immediate window function that takes input from cell `[A1]` and outputs to the VBE immediate window

```
l=[Len(A1)]:For i=Int(-l/2)+2To l/2+1:?Mid(Space(l-i)&[A1],l,l):Next

```

### Ungolfed

```
Sub C(ByVal s As String)
    Let l = Len(s)
    For i = Int(-l / 2) + 2 To l / 2 + 1 Step 1
        Debug.Print Mid(Space(l - i) & s, l, l)
    Next i
End Sub

```
> 1 votes

# Answer
# Python 3, 68 bytes

```
a=input()
c=len(a)
b=a.center(c*2)
for i in range(c):print(b[i:i+c])

```

Try it online!
> 1 votes

# Answer
# PowerShell, ~~133~~ 119 bytes

```
$a="$args";$L=$a.Length;$m=($L+1)/2;$s=" "*($m-1)+$a+" "*($m-1);for($h=0;$h-lt$L;$h++){$r="";0..$L|%{$r+=$s[$_+$h]};$r}

```

Try it online!

**Ungolfed**

```
$a="$args"
$L=$a.Length                        # the length of the input
$m=($L + 1) / 2                     # the midpoint of the input
$s=" " * ($m-1) + $a + " " * ($m-1) # create a string using the input and padded on both sides with spaces

for($h=0;$h -lt $L;$h++) {          # the height, matching the length of the input
    $r=""                           # init/reset the output string

    0..$L | % {                     # number range to represent each character in the string
        $r+=$s[$_+$h]               # append the output string with the next character
    }

    $r                              # write the output
}

```
> 1 votes

# Answer
# , 19 bytes

```
|.!.' '"{~2%~#\-#\.

```

Try it online!

## Explanation

```
|.!.' '"{~2%~#\-#\.  Input: string S
             #\      Length of each prefix of S, [1, 2, ..., len(S)]
                #\.  Length of each suffix of S, [len(s), ..., 2, 1]
               -     Subtract elementwise
          2%~        Divide by 2
                     We now have a range [(1-len(S))/2, ..., -1, 0, 1, ..., (len(S)-1)/2]
       "{~           Use each value to operate on S
|.!.' '                Perform a shift while replacing characters with ' '

```
> 1 votes

# Answer
# Perl 5, 53 + 1 (`-n`) = 54 bytes

```
$t=$"x(($\=y%%%c)/2).$_;say substr$t,$_,$\for 0..$\-1

```

Try it online!
> 1 votes

# Answer
# Ruby `-nl`, 44 bytes

```
puts (0...c= ~/$/).map{$_.center(c*2)[_1,c]}

```

Attempt This Online!
> 1 votes

# Answer
# Japt `-R`, 11 bytes

```
¬£îUûUÊÑ sY

```

Try it

```
¬£îUûUÊÑ sY     :Implicit input of string U
¬               :Split
 £              :Map each element at 0-based index Y
  î             :  Slice the following to the length of U
   Uû           :    Centre pad U with spaces to length
     UÊ         :      Length of U
       Ñ        :      Multiplied by 2
         sY     :    Slice from index Y
                :Implicit output joined with newlines

```
> 1 votes

# Answer
# C# (.NET Core), 101 bytes

```
(a)=>{int L=a.Length,l=L/2;for(;l-->0;)a=" "+a+" ";for(;++l<L;)Console.WriteLine(a.Substring(l,L));};

```

Basically @KevinCruijssen's answer. Saves 2 bytes because `string.Length` doesn't need () and another 2 bytes because the second argument of `string.Substring()` is length rather than end Index, but then loses 2 bytes because `Console.WriteLine()` is longer. I had a more naive implementation, but it was about twice as long so...
> 0 votes

# Answer
# jq, ~~41~~ 39 bytes

```
(length/2*" "+.)[./""|keys[]:][:length]

```

Try it online!
> 0 votes

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


title: Cardinal Code Challenge

text:
# Question
Title: Cardinal Code Challenge
## Task

You're in charge of making a compass, of sorts.

Imagine your source code as the compass "needle" where running at different orientations produces distinct output.

Supported source code orientations are North, East, South, and West.

## Example

Let's say you have source code:

```
ABCD
 J K
WXYZ

```

We'll consider this the North orientation, rotating 90 degrees clockwise points us to the East:

```
W A
XJB
Y C
ZKD

```

rotating again points South:

```
ZYXW
K J
DCBA

```

and finally, the last rotation to the West:

```
DKZ
C Y
BJX
A W

```

When ran, each of the above code examples should output a single, distinct printable ASCII character of your choosing.

## Notes

Your code shall take no input.

Empty spaces or new lines do not collapse/disappear when rotating.

Leading/trailing new lines are okay in output.

Answers may be whole programs or functions, thus output to STDOUT or return the function result.

Standard rules apply; shortest answer in bytes wins!

# Answer
> 23 votes
# Jelly, 2 bytes

```
*2

```

**Try it online!**

Note that the main entry for a Jelly program is its last link, where any newline character will split links), neither of the two-line programs actually access their top link.

The four full programs, all of which implicitly print their result, are:

North:

```
*2   -> (implicit) zero raised to the power of 2 = 0

```

East:

```
*
2    -> literal 2 = 2

```

South:

```
2*   -> two raised to the power of (implicit) 2 = 4

```

West:

```
2
*    -> (implicit) zero raised to the power of (implicit) zero = 1

```

# Answer
> 21 votes
# Japt, ~~3~~ 2 bytes

```
gy

```

Somehow, *somehow*, I found an extremely hacky 2-byte solution...

---

North outputs `0`:

```
gy

```

Since there's no implicit input, it defaults to `0`. `g` on a number returns the sign of the number regardless of its arguments (`"y"` in this case).

---

East outputs `2`:

```
g
y

```

In a multi-line program, the first line sets the input to its result. This is basically a no-op, since `g` on `0` is `0`. Then `y` returns the GCD of `0` and... since it's missing an argument, it defaults to `2` (thanks, @Oliver!). This gives `2` as the output.

---

South outputs `g`:

```
yg

```

`y`, as before, is GCD. Since **gcd(0, x)** is **x** for any value, `y` on `0` takes the liberty of just returning its argument. In this case, the argument is `"g"`, which is the result.

---

West outputs `1`:

```
y
g

```

`y` on 0, as before, returns `2`. This is then passed to `g`, which (as already discussed) is the sign function on numbers. Therefore, the result is `1`.

# Answer
> 10 votes
# Java (OpenJDK 8), ~~7309~~ ~~4421~~ 855 bytes

-2888 bytes thanks to Leaky Nun
-3566 bytes thanks to Wheat Wizard

```
//i/////////////////////////////////////////////////////////////
//n//////////////////////////////////////////////////////////////////
interface M{static void main(String[]a){System.out.println(0);}}/////
//e//}};)2(nltnirp.tuo.metsyS{)a][gnirtS(niam diov citats{M ecafretni
//r//////////////////////////////////////////////////////////////////
//f}/////////////////////////////////////////////////////////////////
//a}//
//c;//
//e)//
// 3//
//M(//
//{n//
//sl//
//tt//
//an//
//ti//
//ir//
//cp//
// .//
//vt//
//ou//
//io//
//d.//
// m//
//me//
//at//
//is//
//ny//
//(S//
//S{//
//t)//
//ra//
//i]//
//n[//
//gg//
//[n//
//]i//
//ar//
//)t//
//{S//
//S(//
//yn//
//si//
//ta//
//em//
//m //
//.d//
//oi//
//uo//
//tv//
//. //
//pc//
//ri//
//it//
//na//
//tt//
//ls//
//n{//
//(M//
//1 //
//)e//
//;c//
//}a//
//}f//
///r//
///e//
 //t//
 //n//
 //i//

```

Try it online!

Old version

Straightforward aproach with comments wrapping the code^2 square, this can be done in pretty much any language.
a (more readable) example in python

```
##p#####
# r  2 #
print 1#
# n  t #
# t  n #
#4 tnirp
# 3  r #
#####p##

```

# Answer
> 8 votes
# Brain-Flak, 33 bytes

```
##)(##))()()  ((
((  ))##    ()##

```

Try it online!

# Brain-Flak, 33 bytes

```
##)     ## #
(( ))#)())()
  # ( (

```

Try it online!

# Brain-Flak, 36 bytes

```
#)##     ## #
  (())#)())()
 #   ( (

```

Try it online!

# Brain-Flak, 38 bytes

```
######  (#
(()()())#))((
       #(  ##

```

Try it online!

# Brain-Flak, 41 bytes

```
##(#####(#
(()()())#
##))()((
####((#)#)#

```

Try it online!

# Answer
> 6 votes
# Alice, 17 bytes

```
1/ 3<
vPo</
5} @<

```

Outputs `1`. Try it online!

```
5v1
}P/
 o
@<3
</<

```

Outputs `x`. Try it online!

```
<@ }5
/<oPv
<3 /1

```

Outputs `5`. Try it online!

```
</<
3<@
 o
/P}
1v5

```

Outputs `3`. Try it online!

# Answer
> 5 votes
# 05AB1E, ~~5~~ 3 bytes

```
Y'X

```

North, East, South, West

# Answer
> 5 votes
# Befunge, ~~17~~ 13 bytes

I thought Befunge would be fun for a geometrical problem. There is a trivial 4x4 solution akin to others here (I need 3 commands) but I managed a bit better.

*Edit: forgot about newlines*

*Edit 2: realized I could create a cat*

*Edit 3: the cat is dead*

```
2v3
@.v
.
1@.

```

RIP kitty :\<

```
1.@ 2
^._.^
3 @.4

```

# Answer
> 5 votes
# Lost, 45 bytes

```
v////v1//v(((
\(((%>2@0>%(((\
  (((v//3v////v

```

Try it online!

To recap the gimmick of lost from the esolangs wiki:

> Lost is a 2-Dimensional language where the instruction pointer starts at a random location, moving in a random direction. Despite this, Lost is still capable of creating completely deterministic programs.

So at first glace, Lost is perhaps not the ideal language for this challenge because of its incredible fragility.

# Answer
> 4 votes
# C (gcc), 283 279 209 bytes

```
/////////)pm//
/////////;ua//
main(){//}ti//
puts("N"//sn//
);}///////((//
//////////")//
///"//////W{//
///E//////"///
//)"//////////
//((///////};)
//ns//"S"(stup
//it}//{)(niam
//au;/////////
//mp)/////////

```

Try it online!

Same old comment trick here, but at least, in C this doesn't get **huuuge** ;)

# Answer
> 4 votes
# Starry, 34 bytes

```
  zz
  +
   .
    +

```

Or with spaces shown as hyphens so you can see them:

```
--zz--
--+---
---.--
----+-
------

```

Try it online!

The commands in Starry are `+`, `.` and some other things, and what they do is determined by how many spaces there are before them: a `+` with *n* spaces pushes *n*−5 to the stack, and `.` with an even number of spaces prints it. The `z`s and newlines are ignored entirely.

There are 6 spaces before the first `+` so it pushes 6−5 = 1, and the `.` prints it.

And the rotations:

```
-----
-----
---+z
--.-z
-+---
-----

```

Try it online! This prints "8".

```
------
-+----
--.---
---+--
--zz--

```

Try it online! This prints "2".

```
-----
---+-
z-.--
z+---
-----
-----

```

Try it online! And this prints "3".

# Answer
> 4 votes
## Labyrinth, 9 bytes

```
!
2@2
 !)

```

Prints `0`. Try it online!

```
 2)
 @!
!2

```

Prints `3`. Try it online!

```
)!
2@2
  !

```

Prints `1`. Try it online!

```
 2!
!@
)2

```

Prints `2`. Try it online!

### Explanation

Each program starts at the first non-space in reading order (i.e. either the top left or top centre character), moving east. For the first program:

```
!   Print an implicit zero.
    The IP can't move east, so it moves south instead.
2   Push a 2.
    The IP can't keep going south, so it turns east instead.
@   Terminate the program.

```

For the second program:

```
2   Push a 2.
)   Increment it to 3.
    The IP can't keep going east, so it turns south instead.
!   Print the 3.
    The IP can't keep going south, so it turns west instead.
@   Terminate the program.

```

For the third program:

```
)   Increment an implicit zero to 1.
!   Print the 1.
    The IP can't keep going east, so it turns south instead.
@   Terminate the program.

```

For the fourth program:

```
2   Push a 2.
!   Print the 2.
    The IP can't keep going east, so it turns back around to move west.
2   Push another 2.
    The IP can't keep going west, so it turns south instead.
@   Terminate the program.

```

# Answer
> 4 votes
## Wumpus, 7 bytes

```
O@$
)))

```

Prints `0`. Try it online!

```
)O
)@
)$

```

Prints `1`. Try it online!

```
)))
$@O

```

Prints `3`. Try it online!

```
$)
@)
O)

```

Prints `2`. Try it online!

### Explanation

The first program is easy enough: `O` prints an implicit zero and `@` terminates the program.

Starting at the second program, we need to look at the triangular grid layout to understand the control flow:

```
)   Increment an implicit zero to 1.
O   Print the 1.
))  Two irrelevant increments.
@   Terminate the program.

```

For the third program:

```
))) Increment an implicit zero to 3.
O   Print the 3.
@   Terminate the program.

```

The fourth one is where it gets really funky. Dashed lines indicate cells that aren't executed because they are skipped by the `$`:

```
$   Skip the ).
$   Skip the @.
))  Increment an implicit zero to 2.
O   Print the 2.
))  Two irrelevant increments.
@   Terminate the program.

```

# Answer
> 3 votes
# PowerShell, ~~20~~ 11 bytes

```
#4#
1#3
#2#

```

Abuses comments (`#`) like crazy, and the fact that a single number placed onto the pipeline gets output as-is. The above prints `1`. Try it online!

From here, you can easily see that each rotation yields only one number that's on the "left" of the comments, and so there's only one number that will be output per rotation.

*Saved 9 bytes thanks to Wheat Wizard!*

# Answer
> 3 votes
# Cardinal, ~~20 17 12~~ 11 bytes

```
.$
Z%"
+$v

```

Try it online!

All this time and no-one answered in Cardinal? This first one outputs `0`.

### East

```
 +Z.
 $%$
 v"

```

Try it online!

Outputs `1`.

### South

```

v$+
"%Z
 $.

```

Try it online!

Outputs a space.

### West

```
 "v
$%$
.Z+

```

Try it online!

Outputs `v`.

# Answer
> 3 votes
# dc, 9 bytes

```
 1
2p3
 4

```

Try it online!

I think its obviousness is part of the charm.

# Answer
> 2 votes
## Batch, 90 bytes

```
 :: :::@:
:&s ohce@
:e   : c:
      :h:
:o     o:
:h:
:c :   w:
@echo n&:
:@::: ::

```

Batch doesn't really have a comment character. For whole-line comments, `:` works, as it introduces a label, but I still need something to terminate the `echo` command while being a no-op when reversed. `&:` seems to work, which is all I need here, but it really confuses Batch, erroring out if I don't put a `:` before the `@` on the next line, and also somehow forgetting to print a newline.

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

Outputs 0 for North, 1 for East, 2 for South, and 3 for West.

```
////  _//
////  =//
_=>0//>//
  ////1//
  // //
//3////
//>//2>=_
//=  ////
//_  ////

```

```
const source =
`////  _//
////  =//
_=>0//>//
  ////3//
  // //
//1////
//>//2>=_
//=  ////
//_  ////`;

function rotateTextCW(text) {
  const lines = text.split("\n");
  const maxLineLength = lines
    .map(line => line.length)
    .reduce((max, len) => Math.max(len, max), 0);
  const paddedLines = lines.map(line => line.padEnd(maxLineLength));
  const charGrid = paddedLines.map(line => line.split(""));
  const rotatedGrid = [...new Array(maxLineLength)]
    .map(v => new Array(charGrid.length));

  for (let i = 0; i < charGrid.length; i++) {
    for (let j = 0; j < charGrid[i].length; j++) {
      rotatedGrid[j][charGrid.length - i - 1] = charGrid[i][j];
    }
  }

  return rotatedGrid
    .map(chars => chars.join("").trimRight())
    .join("\n");
}

const orientations = ["North", "East", "South", "West"];
let rotatedSource = source;
let markup = "";

orientations.forEach(orientation => {
  const code = `<pre>${rotatedSource}</pre>`;
  const result = `<code>${eval(rotatedSource)()}</code>`;
  const row = `
    <td>${orientation}</td>
    <td>${code}</td>
    <td>${result}</td>`;
  markup += `<tr>${row}</tr>`;
  rotatedSource = rotateTextCW(rotatedSource);
});

document.querySelector("table tr:first-child")
  .parentNode
  .innerHTML += markup;
```

```
<link href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.7/css/bootstrap.min.css" rel="stylesheet" />
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<script src="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.7/js/bootstrap.min.js"></script>

<div class="container">
  <table class="table table-striped table-responsive">
    <tr>
      <th>Orientation</th>
      <th>Source</th>
      <th>Result</th>
    </tr>
  </table>
</div>
```

# Answer
> 2 votes
# MATLAB, ~~29 17 5~~ 11 bytes

Having realised that the question called for single ASCII characters not just a distinct output, here is a MATLAB approach which will do just that:

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

```

This will implicitly print 1, 2, 3, or 4 depending on the rotation.

# Answer
> 1 votes
# SOGL V0.12, 4 bytes

```
5H
I

```

Outputs `1`, Try it Here!

```
I5
 H

```

Outputs `H`, Try it Here!

```
 I
H5

```

Outputs `5`, Try it Here!

```
H
5I

```

Outputs `6`, Try it Here!

# Answer
> 1 votes
# MATL, 11 bytes

```
HxI
xFx
TxK

```

Try it online!

Let's get this started in MATL. The main challenge is that MATL just fails if a function requires input if the stack is empty. Perhaps something clever with modifiers like `X`, `Y`, `Z` and `&` could make for something shorter, but I couldn't find a suitable combination.

Explanation: all characters push a single integer on the stack, and `x` removes all of them but the last.

# Answer
> 1 votes
## Perl, 49 bytes

**48 bytes code + 1 for `-p`.**

Assumes empty input which TIO doesn't support, so a newline is added in its place and not used. Prints , , , .

```
# ####
#S= _$
#; W#
 $_=N#
#_ _#
#= $#
#E#
 ## #

```

Try it online!

# Answer
> 1 votes
# C (gcc), 120 bytes

I had hoped for more synergy between the variants.

```
//}=)f8 ///
// c{(7 ///
   ;rr; //}
        ;c=
78; /// r{)
f(r /// r(f
){r /// ;38
=c;
}// ;rr;
/// 9({c //
/// 6f)=}//

```

North

East

South

West

# Answer
> 1 votes
# MathGolf, 11 bytes

```
Þ2Þ
3 1
Þ0Þ

```

A bit boring, but since MathGolf implicitly outputs the entire stack joined together, I'm not sure if something shorter is possible here..

Default; rotated once clockwise; rotated two times clockwise; rotated three times clockwise.

**Explanation:**

* `0123`: These push the digit to the stack
* : This pushes a space character to the stack
* `Þ`: This empties the stack except for the top value

And in the end the entire stack joined together is output implicitly as result.

# Answer
> 1 votes
# brainfuck, 72 bytes

```
++
+++++++++++++++++++++++++++++++++.+++++++++++++++++++++++++++++++++
+

```

Try it online!
Try it rotated once!
Try it rotated twice!
Try it rotated thrice!

# Answer
> 1 votes
# JavaScript (Node.js), 69 bytes

```
 _=>0//
/*    *_
/      =
1      >
>      3
=      /
_*    */
 //2>=_

```

Try it online!

This approach should work for any language with C-style comments.

# Answer
> 0 votes
# MAWP, 5 bytes

## North: 3

```
2M:
2

```

Try it!

## East: 4

```
22
 M
 :

```

Try it!

## South: 2

```
  2
:M2

```

Try it!

## West: 1

```
:
M
22

```

Try it!

The existing 1 in the stack is very convenient here.

# Answer
> 0 votes
# Python 2, 71 bytes

```
##p#####
# r  2 #
print 1#
# n  t #
# t  n #
#4 tnirp
# 3  r #
#####p##

```

Try it online!

Big thanks to this answer!

Note I **did not** copy it directly, but actually had a program in mind and golfed it with this.

---
Tags: code-golf, source-layout
---


title: Parlett's movement notation

text:
# Question
Title: Parlett's movement notation
Some chess variants use interesting non-standard pieces. In order to concisely describe new pieces or to describe pieces without requiring everyone to memorize a bunch of non-standard names some new notation can be invented.

In this challenge we are going to look at Parlett's movement notation and convert it to nice at a glance diagrams.

A move description consists of two parts. First is the distance. Some pieces can move 1 unit, some pieces can move two, and some pieces can move however as far as they wish. The second part is the pattern, that expresses what basic units a move can use. When moving a piece selects a unit from it's pattern and then repeat that unit based on it's distance.

For example a bishop has any non-negative distance, and it's pattern is all the diagonal movements 1 square. So the bishop can move in any diagonal direction any amount (other than 0).

---

## Distances

* Any postive integer means exactly that distance. e.g. `1` means `1`.
* `n` means that the piece can move any non-negative distance

For this challenge you can assume that the integers will not exceed 9.

---

## Move patterns

There are 5 basic patterns that all other patterns can be composed of. They are the 8 squares surrounding the piece except since the system doesn't distinguish between left and right moves, these moves are grouped into pairs.

| Number | Description |
| --- | --- |
| 1 | Diagonal forward |
| 2 | Directly forward |
| 3 | Left or right |
| 4 | Diagonal backward |
| 5 | Directly backward |

Here's these described with a diagram:

```
1 2 1
3   3
4 5 4

```

We can then describe the symbols for patterns. in terms of which of these they allow:

| Symbol | Allowed patterns |
| --- | --- |
| `x` | 1 or 4 |
| `+` | 2, 3 or 5 |
| `*` | 1, 2, 3, 4 or 5 |
| `>` | 2 |
| `<` | 5 |
| `<>` | 2 or 5 |
| `=` | 3 |
| `>=` | 2 or 3 |
| `<=` | 5 or 3 |
| `x>` | 1 |
| `x<` | 4 |

---

These two parts are then concatenated to make a symbol. So for our bishop earlier its distance is `n` and its pattern is `x` so it's symbol is `nx`.

## Grouping

You can group multiple moves together into larger moves using two extra symbols.

* `.` represents *and then*. For the symbol `a.b` the piece must perform a valid `a` move and then a valid `b` move.
* `,` represents *or*. For the symbol `a,b` the piece can do a valid `a` move or a valid `b` move.

`.` has higher precedence and there is no option for parentheses. So `a.b,c` means "(`a` then `b`) or `c`", not "`a` then (`b` or `c`)".

As an example the knight from chess can be expressed with the rather complex compound symbol `2=.1<>,2<>.1=`, in plain(er) English "(2 moves to the side and 1 forward or back) or (2 moves forward or back and one to the side)".

## Task

In this challenge your program or function is going to take in a symbol as a string and draw an diagram of where it can move.

The diagram will show a 9x9 board with the piece placed in the center, (5,5), and will show all the places the piece can move in 1 turn with `X` and all the places it cannot with `.`. We will ignore the case where the piece does not move (whether it is described by the rules or not) and place a `O` at the original coordinates to indicate its place.

A piece may not move out of the board during the course of the move. For example `1>.1<` (one forward, then one backwards) requires the piece to move one forward while staying in the board.

Your output should be arranged into 9 space separated columns with 9 newline separated rows. You may have trailing whitespace on any lines or after the end of the output.

This is so the goal is to minimize the size of your source code as measured in bytes.

## Test cases

```
1+
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . X . . . .
. . . X O X . . .
. . . . X . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .

2x
. . . . . . . . .
. . . . . . . . .
. . X . . . X . .
. . . . . . . . .
. . . . O . . . .
. . . . . . . . .
. . X . . . X . .
. . . . . . . . .
. . . . . . . . .

2*
. . . . . . . . .
. . . . . . . . .
. . X . X . X . .
. . . . . . . . .
. . X . O . X . .
. . . . . . . . .
. . X . X . X . .
. . . . . . . . .
. . . . . . . . .

n+,1x
. . . . X . . . .
. . . . X . . . .
. . . . X . . . .
. . . X X X . . .
X X X X O X X X X
. . . X X X . . .
. . . . X . . . .
. . . . X . . . .
. . . . X . . . .

2=.1<>,2<>.1=
. . . . . . . . .
. . . . . . . . .
. . . X . X . . .
. . X . . . X . .
. . . . O . . . .
. . X . . . X . .
. . . X . X . . .
. . . . . . . . .
. . . . . . . . .

n=.1<>
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
X X X X X X X X X
. . . . O . . . .
X X X X X X X X X
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .

1x.1+
. . . . . . . . .
. . . . . . . . .
. . . X . X . . .
. . X . X . X . .
. . . X O X . . .
. . X . X . X . .
. . . X . X . . .
. . . . . . . . .
. . . . . . . . .

1+.1+
. . . . . . . . .
. . . . . . . . .
. . . . X . . . .
. . . X . X . . .
. . X . O . X . .
. . . X . X . . .
. . . . X . . . .
. . . . . . . . .
. . . . . . . . .

1+.3>=
. . . . X . . . .
. . . X . X . . .
. . . . X . . . .
. X . . . . . X .
X . X . O . X . X
. X . . . . . X .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .

3=.4=.5=
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
X . . . O . . . X
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .

n<>.nx<
. . . . X . . . .
. . . X X X . . .
. . X X X X X . .
. X X X X X X X .
X X X X O X X X X
X X X X X X X X X
X X X X X X X X X
X X X X X X X X X
X X X X X X X X X

4*.1*
. X . X . X . X .
X X . X X X . X X
. . . . . . . . .
X X . . . . . X X
. X . . O . . X .
X X . . . . . X X
. . . . . . . . .
X X . X X X . X X
. X . X . X . X .

```

---

As a final note, you may notice that this notation fails to capture a lot of information about pieces. Like how blocking works, castling or anything about how pawns move. The thing is that these symbols are not really all that useful in expressing most interesting stuff. But they do make for a bit of an interesting code-golf challenge.

# Answer
# JavaScript (V8), 305 bytes

Prints the ASCII art.

```
s=>s.split`,`.map(s=>(g=(x,y,[s,...a])=>(r=m[y])&&r[x]&&b.map((v,d)=>s?',x<,>,,=,,>=,,<,,<>,,<=,,+,,x>,x'.split`,`.indexOf(s.slice(1))>>v&d!=4&&b.map((_,n)=>n-s[0]||g(x+d%3*n-n,y+n*~-(d/3),a)):r[x]='X'))(4,4,s.split`.`),b=[...'4142.2030'],m=b.map(_=>[...b].fill`.`))|m.map(r=>print(r.join` `),m[4][4]='O')

```

Try it online!

### Encoding

Each symbol is encoded by its position into a lookup array, packed as the following comma-separated string:

```
',x<,>,,=,,>=,,<,,<>,,<=,,+,,x>,x'

```

The position is then interpreted as a 5-bit mask. Note that the symbol `*` is not stored at all, so its position is `-1` and all bits are set in that case.

```
 symbol | position | bitmask      bits:
--------+----------+---------
   x<   |     1    |  00001       4 3 2 1 0
   >    |     2    |  00010       | | | | |
   =    |     4    |  00100       | | | | +--> Diagonal backward
   >=   |     6    |  00110       | | | +----> Directly forward
   <    |     8    |  01000       | | +------> Left or right
   <>   |    10    |  01010       | +--------> Directly backward
   <=   |    12    |  01100       +----------> Diagonal forward
   +    |    14    |  01110
   x>   |    16    |  10000
   x    |    17    |  10001
   *    |    -1    |  11111
                      -----
                      43210

```

Given a symbol and a direction \\$d\in\[0..3,5..8\]\\$, we retrieve one of the bitmasks described above and get the character at position \\$d\\$ in the lookup string `"4142.2030"` to figure out which bit should be tested. If the bit is set, we are allowed to move in this direction.

The direction vector is \\$\big((d\bmod 3)-1,\lfloor d/3 \rfloor-1\big)\\$, leading to the following compass:

$$\begin{matrix}0&1&2\\3&&5\\6&7&8\end{matrix}$$
> 4 votes

# Answer
# Charcoal, 136 bytes

```
ＵＯ⁹.Ｆ⪪Ｓ,⊞υ⁺⮌⪪ι.⟦⁴¦⁴⟧Ｆυ«≔⊟ιθ≔⊟ιη≔⊟ιζＦ⌕Ａ⮌⍘§⦃x¹⁷⁰+⁸⁵*²⁵⁵>⁴<⁶⁴<>⁶⁸=¹⁷>=²¹<=⁶⁹x>χx<¹⁶⁰⦄Φζλ²1Ｆ…·Σζ∨Σζ⁹«ＪθηＭλ✳κ¿⬤⟦ⅉⅈ⟧⁼μ﹪μ⁹¿ι⊞υ⁺ι⟦ⅉⅈ⟧X»»Ｊ⁴¦⁴OＵＥ¹

```

Attempt This Online! Link is to verbose version of code. Explanation:

```
ＵＯ⁹.

```

Draw a 9×9 board.

```
Ｆ⪪Ｓ,⊞υ⁺⮌⪪ι.⟦⁴¦⁴⟧

```

Get the input string, split it on `,`s, split each piece on `.`s, and append two `4`s to each reversed list of instructions as being the starting coordinates.

```
Ｆυ«

```

Loop over the list of instruction and coordinate entries.

```
≔⊟ιθ≔⊟ιη≔⊟ιζ

```

Remove the coordinates and one instruction and assign them to their own variables.

```
Ｆ⌕Ａ⮌⍘§⦃x¹⁷⁰+⁸⁵*²⁵⁵>⁴<⁶⁴<>⁶⁸=¹⁷>=²¹<=⁶⁹x>χx<¹⁶⁰⦄Φζλ²1

```

Map the instruction into a binary number and loop over the positions of the `1` bits (counting back from the end) which represent the allowed directions.

```
Ｆ…·Σζ∨Σζ⁹«

```

Loop over the allowed distances. (This assumes that zero distance means any amount up to and including `9`. Larger explicit distances are supported, and the range for arbitrary distances could be increased to `1000` without changing the byte count.)

```
ＪθηＭλ✳κ

```

Move to the resulting position for the given direction and distance.

```
¿⬤⟦ⅉⅈ⟧⁼μ﹪μ⁹

```

If the current position is on the board, then...

```
¿ι⊞υ⁺ι⟦ⅉⅈ⟧X

```

... if there are more instructions to process then push them with the current position to the list of instructions, otherwise mark the current position with an `X`.

```
»»Ｊ⁴¦⁴O

```

Mark the initial position with an `O`.

```
ＵＥ¹

```

Space the board out horizontally.
> 2 votes

# Answer
# Java 10, ~~631~~ ~~608~~ ~~606~~ ~~597~~ ~~578~~ ~~504~~ ~~489~~ ~~475~~ 470 bytes

```
s->{int i=0,k,d,n,x,y,l,e[],f[];var m=new boolean[81];for(var p:s.split(",")){e=f=new int[81];e[40]=k=1;for(var P:p.split("\\.")){f=e.clone();k++;for(i=81;i-->0;)if(e[i]==k-1)for(n=P.charAt(0),d=9;d-->0;)for(l=n>99?0:n-49;d*n==440|("ǰ« )ņ©+  Ł ".charAt((P.chars().sum()-n)%42%15)-1>>d&1)>0&&l++<n%48;)if((y=i/9-d/3*l+l)>=0&y<9&(x=i%9-d%3*l+l)>=0&x<9)f[y*9+x]=k;e=f;}for(;++i<81;)m[i]|=e[i]==k;}for(;i-->0;)System.out.print((i==40?"O":m[i]?"X":".")+(i%9<1?"\n":""));}

```

-74 bytes, opening up another -22 bytes, thanks to *@Arnauld*
-5 bytes thanks to *@ceilingcat*

Try it online.

**Explanation:**

```
s->{                            // Method with String parameter and no return-type
  int i=0,                      //  Index-integer, starting at 0
      k,                        //  'and then'-iteration integer
      d,                        //  Direction-integer
      n,                        //  Step-size integer
      o,                        //  Operation-integer
      x,y,                      //  x,y-coordinates
      l,                        //  Inner loop integer (when the step-size is 'n')
      e[],f[];                  //  Temp integer-arrays
  var m=new boolean[81];        //  Result boolean-array, starting at 81x false
  for(var p:s.split(",")){      //  Split the input by "," and loop over the parts:
    e=f=new int[81];            //   Set `e` to an empty list
                                //   (and `f` as well to prevent uninitialized errors)
    e[40]=k=1;                  //   (Re)set `k` to 1
                                //   And also fill the center cell with 1
    for(var P:p.split("\\.")){  //   Inner loop over the parts split by ".":
      f=e.clone();              //     Set `f` to a copy of `e`
      k++;                      //     Increase `k` by 1
      for(i=81;i-->0;)          //     Loop over all the cells:
        if(e[i]==k-1)           //      If the cell contains the previous `k`:
          for(n=P.charAt(0),    //       Set `n` to the first character of `P`
              d=9;d-->0;)       //       Loop over the directions `d` in the range (9,0]:
            for(l=n>99?         //        If the step-size is 'n':
                   0            //         Set `l` to 0
                  :             //        Else:
                   n-49;        //         Set `l` to digit 'n' minus 1
                 d*n==440       //         If `n` = 'n' and the direction is 4,
                 |("ǰ« )ņ©+  Ł ".charAt((P.chars().sum()-n)%42%15)-1>>d&1)>0
                                //         or bitmask magic† to check whether the direction applies to operation:
                &&l++<n%48;)    //          If `n` != 'n': simply use `l` once
                                //          Else (`n` = 'n'): loop `l` in the range [0,14):
                                //          (any integer >= 8 would be fine here)
              if((y=i/9-d/3*l+l)//          Set `y` to `l` steps into direction `d`
                 >=0&y<9        //          And check if it's still in bounds
                 &(x=i%9-d%3*l+l)>=0&x<9)
                                //          Change and check bounds for `x` as well:
                f[y*9+x]=k;     //           Fill the `x,y`'th cell with value `k`
      e=f;}                     //     Set `f` as new `e` for the next iteration
    for(;++i<81;)               //   Loop over all the cells again:
      m[i]|=                    //    OR the boolean at cell `i` with:
            e[i]==k;            //     Check if the `i`'th cell of `e` contains value `k`
  }                             //  After we've looped over the entire input-String:
  for(i=81;i-->0;)              //   Loop one last time over all the cells:
    System.out.print(           //    Print:
      (i==40?                   //     If it's the center cell:
        "O"                     //      Print "O"
       :m[i]?                   //     Else-if the `i`'th cell of the boolean-matrix is true:
        "X"                     //      Print "X"
       :                        //     Else (it's false instead):
        ".")                    //      Print "."
      +(i%9<1?"\n":""));}       //     And print a newline every 9 cells

```

*†Explanation of the 'bitmask magic':*

| Operation | `P.chars().sum()`
`-n` | `%42` | `%15` | `"ǰ« )ņ©+ Ł "`
`.charAt(...)-1` | `>>d` for direction `d`
in range \\$\[0,8\]\\$ | `&1` |
| --- | --- | --- | --- | --- | --- | --- |
| x | 120 | 36 | 6 | 325 | 325,162,81,40,20,10,5,2,1 | 101
000
101 |
| + | 43 | 1 | 1 | 170 | 170,85,42,21,10,5,2,1,0 | 010
101
010 |
| * | 42 | 0 | 0 | 495 | 495,247,61,30,15,7,3,1 | 111
101
111 |
| \> | 62 | 20 | 5 | 2 | 2,1,0,0,0,0,0,0 | 010
000
000 |
| \< | 60 | 18 | 3 | 128 | 128,64,32,16,8,4,2,1,0 | 000
000
010 |
| \<\> | 122 | 38 | 8 | 130 | 130,65,32,16,8,4,2,1,0 | 010
000
010 |
| = | 61 | 19 | 4 | 40 | 40,20,10,5,2,1,0,0,0 | 000
101
000 |
| \>= | 123 | 39 | 9 | 42 | 42,21,10,5,2,1,0,0,0 | 010
101
000 |
| \<= | 121 | 37 | 7 | 168 | 168,84,42,21,10,5,2,1,0 | 000
101
010 |
| x\> | 180 | 14 | 14 | 5 | 5,2,1,0,0,0,0,0 | 101
000
000 |
| x\< | 182 | 12 | 12 | 320 | 320,160,80,40,20,10,5,2,1 | 000
000
101 |
> 1 votes

---
Tags: code-golf, chess
---


title: What is the area of this polygon?

text:
# Question
Title: What is the area of this polygon?
# Calculate the area of a polygon.

Inspired by this shoelace algorithm video.

## Task

Your job is to create a program or function that calculates the area of a polygon. Program or function is defined according the the default definition in meta.

## Input

You will receive the X and Y coordinates of each vertex of the polygon. You can take the input as a list of tuples (`[[x1, y1], [x2, y2], etc]`), a matrix, or a flat list (`[x1, y1, x2, y2, etc]`). Two lists containing `x` and `y` coordinates respectively are allowed as well. The vertices are numbered counterclockwise and the first vertex is the same as the last vertex provided, thus closing the polygon.

If you want you can take the input without the last vertex (so receive each coordinate just once).

You can assume that the edges of the polygons don't intersect. You can also assume that all vertices have integer coordinates.

## Output

The area of the polygon. All standard output methods are allowed. If your language does not allow for float division and the solution would not be an integer, you are allowed to return a fraction. The fraction does not necessarily have to be simplified, so returning `2/4` would be allowed.

## Winning criterium

Shortest code wins!

## Test cases

```
[[4,4],[0,1],[-2,5],[-6,0],[-1,-4],[5,-2],[4,4]]
55

```

```
[[1,1],[0,1],[1,0],[1,1]]
0.5
1/2

```

# Answer
> 13 votes
# Jelly,  ~~8~~  6 bytes

-1 byte thanks to Emigna (redundant , `ÆḊ` has a left-depth of 2)
-1 byte thanks to Emigna, again (halve, `H`, is floating point no need to `÷2`)

```
ṡ2ÆḊSH

```

A monadic link taking a list of pairs of coordinates in counter-clockwise fashion as per the examples (with the one repeat) and returning the area.

**Try it online!**

### How?

Applies the shoelace algorithm, just as described in the video (which I happened to also watch just the other day!)

```
ṡ2ÆḊSH - Link: list of [x,y] coordinate pairs anticlockwise & wrapped, p
ṡ2     - all overlapping slices of length 2
  ÆḊ   - determinant (vectorises)
    S  - sum
     H - halve

```

# Answer
> 30 votes
## Mathematica, 13 bytes

```
Area@*Polygon

```

# Answer
> 21 votes
# Octave, 9 bytes

```
@polyarea

```

Inputs are a vector with the *x* values and a vector with the *y* values. This works in MATLAB too.

Try it online!

# Answer
> 16 votes
# JavaScript (ES6),  ~~69 67 47~~  44 bytes

*Thanks to @Rick for noticing that we don't need the absolute value if the vertices are guaranteed to be sorted in counterclockwise order and for suggesting to take a flat list as input, saving 20 bytes!
Saved 3 more bytes thanks to @Shaggy*

Takes input as a flat list of vertices, including the last vertex.

```
f=([x,y,...a])=>a+a?x*a[1]/2-y*a[0]/2+f(a):0

```

Try it online!

### How?

This is based on the formula used in many other answers. For \\$n\\$ 0-indexed vertices:

$$area=\left|\frac{(x\_0y\_1-y\_0x\_1)+(x\_1y\_2-y\_1x\_2)+\ldots+(x\_{n-1}y\_0-y\_{n-1}x\_0)}{2}\right|$$

# Answer
> 7 votes
# Python 3, ~~72~~ 71 bytes

```
from numpy import*
g=lambda x,y:(dot(x[:-1],y[1:])-dot(x[1:],y[:-1]))/2

```

Takes two lists, as it was allowed in the comments

```
x = [x0,x1,x2, ...]
y = [y0,y1,y2, ...]

```

Try it online!

This is basically just the implementation of the shoelace-formula. May I get plus points for a golf that you actually would implement like that? :D

-1, there is no need for a space behind `x,y:`.

---

# Answer
> 7 votes
# R, ~~54~~ 52 bytes

```
pryr::f({for(i in 2:nrow(x))F=F+det(x[i-1:0,]);F/2})

```

Which evaluates to the function:

```
function (x)
{
    for (i in 2:nrow(x)) F = F + det(x[i - 1:0, ])
    F/2
}

```

Makes use of the predefined `F = FALSE = 0`. Implements the shoelace algorithm in the linked video :)

-2 bytes thanks to Giuseppe

# Answer
> 6 votes
# Mathics, 31 bytes

```
Total[Det/@Partition[#,2,1]/2]&

```

Try it online!

---

# Mathematica, 25 bytes

```
Tr@BlockMap[Det,#,2,1]/2&

```

# Answer
> 4 votes
# Factor, 35 bytes

```
[ dup pick [ rest v. ] 2bi@ - 2 / ]

```

Try it online!

Takes two arrays of x- and y-coordinates on the top of the stack, and returns the area as an integer or a rational.

Exploits the vector dot product `v.` which ignores excess elements on either side, so calculating one side of the shoelace is as simple as "remove the first element from the top array, and compute the dot product". And we can reuse it to evaluate the other side of the shoelace by simply swapping the two input arrays.

Honorable mention goes to the Apply combinator `2bi@`, which lets us simplify multi-application of the inner function.

```
Input:
{ 4 0 -2 -6 -1  5 4 }
{ 4 1  5  0 -4 -2 4 }
Remove the first element from top:
{ 4 0 -2 -6 -1 5 4 }
{ 1 5  0 -4 -2 4 }
Evaluate the dot product (sum of elementwise product, ignoring any excess element)

[                  ! Input: ( x y )
  dup pick         ! Copy stack items to form ( x y y x )
  [ rest v. ]      ! The function that evaluates one side of shoelace
  2bi@             ! Apply the above to ( x y ), then to ( y x )
  - 2 /            ! Subtract the two and halve
]

```

# Answer
> 3 votes
# JS (ES6), ~~98~~ ~~95~~ ~~94~~ ~~93~~ ~~88~~ ~~86~~ ~~82~~ ~~81~~ ~~77~~ 73 bytes

```
(X,Y)=>{for(i in X){a+=(X[i]+X[i-1])*(Y[i]-Y[i-1]);if(!+i)a=0}return a/2}

```

Takes input like `[x1, x2, x3], [y1, y2, y3]`, and skips the repeated coord pair.

-3 bytes thanks to @JarkoDubbeldam

-4 bytes thanks to @JarkoDubbeldam

-1 byte thanks to @ZacharyT

-4 bytes thanks to @ZacharyT

-4 bytes thanks to @Rick

# Answer
> 3 votes
# J, 12 bytes

Assuming the input is a list of 2 element lists (ie, a table)

```
-:+/-/ .*2[\

```
* `2[\` -- breaks it down into the shoelace Xs, ie, overlapping squares of 4 elms
* `-/ .*` -- the determinant of each
* `+/` -- sum it
* `-:` -- divide by 2

If we get the input as a single list, we need to first transform into a table, giving us 20 bytes:

```
-:+/-/ .*2[\ _2&(,\)

```

# Answer
> 3 votes
# MS-SQL, 66 bytes

```
SELECT geometry::STPolyFromText('POLYGON('+p+')',0).STArea()FROM g

```

MS SQL 2008 and higher support Open Geospatial Consortium (OGC)-standard spatial data/functions, which I'm taking advantage of here.

Input data is stored in field *p* of pre-existing table *g*, per our input standards.

Input is a text field with ordered pairs in the following format: `(4 4,0 1,-2 5,-6 0,-1 -4,5 -2,4 4)`

Now just for fun, if you allowed my *input* table to hold Open Geospatial Consortium-standard geometry objects (instead of just text data), then it becomes almost trivial:

```
--Create and populate input table, not counted in byte total
CREATE TABLE g (p geometry)
INSERT g VALUES (geometry::STPolyFromText('POLYGON((5 5, 10 5, 10 10, 5 5))', 0))

--23 bytes!
SELECT p.STArea()FROM g

```

# Answer
> 2 votes
# Haskell, 45 bytes

```
(a:b:c)?(d:e:f)=(a*e-d*b)/2+(b:c)?(e:f)
_?_=0

```

Try it online!

# Answer
> 2 votes
# APL (Dyalog Extended), 14 bytes

```
2÷⍨1⊥2-/⍤×∘⌽/⊢

```

Try it online!

Same formula as in Arnauld's answer.

Takes input as a list of points, sorted in counterclockwise order.

## Explanation

```
2÷⍨1⊥2-/⍤×∘⌽/⊢
             ⊢ take the input (list of pts)
     2      /  reduce overlapping pairs by the following function:
         ×       multiply the first
          ∘⌽     with the second reversed
      -/⍤        reduce the multipled pair by subraction
   1⊥          sum the resultant array (using decoding)
2÷⍨            halve it

```

# Answer
> 2 votes
# PARI/GP 61 bytes

```
c=concat;s(z,v=1)=c(z,z)[^#x*2]+c(z[^1],z)*v
s(x,-1)*s(y)~/4

```

assumes coordinates given by two vectors x=\[x1,...xn\], y=\[y1,...,yn\]

## Test cases

```
A(x,y)={my(c=concat,s(z,v=1)=c(z,z)[^#x*2]+c(z[^1],z)*v);s(x,-1)*s(y)~/4};
A([1, 0, 1, 1],[1, 1, 0, 1])
1/2
A([4,0,-2,-6,-1,5,4],[4,1,5,0,-4,-2,4])
55

```

# Answer
> 2 votes
# PHP, 76 75 73 bytes

Well, i probably shoot myself in the knee with PHP and his $ prefix for variable but i just wanna try the challenge with it anyway.

Header just remove error reporting for conviniance and format input as 2 array like it's allowed in post... i was just lazzy to retype it myself XD. (you can test both case by switching var in the for loop)

Edit: Figure out i can pass 2 arg to for() and save carac from while keyword with the same logic

Edit : Saved 2 bytes by reverse the iteration order and use juste `$i` for condition, saved `<0` (need to substract for 2nd option since result will be negative otherwise, but same bytes length)

```
for($i=count($x);$i;){$s-=$x[$j=$i--]*$y[$i]-$y[$j]*$x[$i];}$s=abs($s)/2;

```

Try it online!

# PHP, 67 66 64 bytes

Solution without the `abs()` who work on both given case but feel like cheat since can return negative values in some cases ^^'

```
for($i=count($x);$i;){$s-=($x[$j=$i--]*$y[$i]-$y[$j]*$x[$i])/2;}

```

Try it online!

# Answer
> 1 votes
# Perl 5 `-pa`, 62 bytes

```
map$\+=$F[$i]*($a[($i+1)%@a]-$a[$i++-1]),@a=eval<>}{$\=abs$\/2

```

Try it online!

Takes input as a list of X coordinates on the first line followed by a list of Y coordinates on the second.

# Answer
> 1 votes
# , ~~51~~ 46 bytes

*Edit: save 5 more bytes since no need to take `abs()` if points always encircle the polygon in counter-clockwise fashion*

```
pryr::f(sum(x*(1:0-.5)*x[2:1,c(2:ncol(x),1)]))

```

Try it online!

After 3 years, ~~1~~ 6 bytes shaved from the previously-best  solution!

# Answer
> 1 votes
# Python 3, 58 bytes

```
lambda x,y:sum(x[i-1]*(j-y[i-2])/2for i,j in enumerate(y))

```

Try it online!

Implementation of the shoelace algorithm.

# Answer
> 1 votes
# Excel, 97 bytes

```
=LET(a,A1#,x,ROW(a),y,{2,1},b,IF(x=ROWS(a),INDEX(a,1,y),INDEX(a,x+1,y)),SUM(MMULT(a*b,{1;-1}))/2)

```

LET and dynamic arrays were not Excel features in 2017.

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


title: The best base is 10... Let's reach it!

text:
# Question
Title: The best base is 10... Let's reach it!
### Input:

A positive integer **n** consisting of digits in the range **0-9**.

### Challenge:

If **d** is the highest digit in the integer, assume the base of the number is **d+1**. E.g. if the integer is **1256** then you shall assume it's in **base-7**, if it's **10110** then you shall assume it's **base-2** (binary), and if it's **159** then it's decimal.

Now, do the following until you either, 1: reach a **base-10** integer, *or* 2: reach a single digit integer.

1. Convert the integer from **base-(d+1)** to **base-10**
2. Find the base of this new integer (again, **base-(d+1)** where **d** is the highest digit in the new number)
3. Go to step **1**.

---

### Examples:

Assume the input is **n = 413574**. The highest digit **d=7**, so this is **base-8** (octal). Convert this to decimal and get **137084**. The highest digit **d=8**, so this is **base-9**. Convert this to decimal and get **83911**. The highest digit is **9**, so this is a decimal number and we stop. The output shall be **83911**.

Assume the input is **n = 13552**. The highest digit is **d=5**, so this is **base-6**. Convert this to decimal and get **2156**. The highest digit **d=6**, so this is **base-7**. Convert this to decimal and get **776**. The highest digit is **d=7**, so this is **base-8**. Convert this to decimal and get **510**. The highest digit is **d=5** so this is **base-6**. Convert this to decimal and get **186**. The highest digit is **8**, so this is **base-9**. Convert this to decimal and get **159**. The highest digit is **9**, so this is a decimal number and we stop. The output shall be **159**.

Assume the input is **n=17**. This will give us **15**, then **11**, then **3**, which we will output since it's a single digit.

---

### Test cases:

```
5
5

17
3

999
999

87654321  (base-9 -> 42374116 in decimal -> base-7 -> 90419978 in decimal)
9041998

41253  (5505 -> 1265 -> 488 -> 404 -> 104 -> 29)
29

```

---

**Notes:**

* Standard rules regarding I/O, loopholes etc. You may take the input as a string
* Explanations are encouraged
* You may use builtin base-conversion commands
    + Solutions that don't use the language's builtin base-conversion functions (if they exist) are welcome, even if they end up being much longer than the obvious approach using builtin functions.

---

Apparently, this is OEIS A091047.

# Answer
> 21 votes
## Mathematica, 56 bytes

```
#//.x_/;(b=Max[d=IntegerDigits@x]+1)<11:>d~FromDigits~b&

```

Try it online! (Using Mathics.)

I thought I'd check out what the sequence looks like:

And here is a plot of the number of steps it takes to find the result:

<sup>(Click for larger versions. See the revision history for plots only up to **n = 1000**.)</sup>

Looks like a very interesting mixture of large scale structure and fine scale chaos. I wonder what's up with the wider gaps around 30,000 and 60,000.

# Answer
> 10 votes
# Java 8, ~~172~~ ~~166~~ ~~163~~ ~~152~~ ~~151~~ ~~140~~ ~~138~~ ~~116~~ ~~114~~ 99 bytes

```
s->{for(Integer b=0;b<10&s.length()>1;s=""+b.valueOf(s,b=s.chars().max().getAsInt()-47));return s;}

```

Takes the input as a `String`.

-64 bytes thanks to *@OlivierGrégoire*. And here I thought my initial 172 wasn't too bad.. ;)

Try it here.

**Explanation:**

```
s->{                    // Method with String as parameter and return-type
  for(Integer b=0;b<10  //  Loop as long as the largest digit + 1 is not 10
      &s.length()>1;    //  and as long as `s` contains more than 1 digit
    s=""+               //   Replace `s` with the String representation of:
         b.valueOf(s,   //    `s` as a Base-`b` integer
          b=s.chars().max().getAsInt()-47)
                        //     where `b` is the largest digit in the String + 1
  );                    //  End of loop
  return s;             //  Return result-String
}                       // End of method

```

# Answer
> 8 votes
# Pyth, 9 bytes

```
ui`GhseS`

```

Test suite

Explanation:

```
ui`GhseS`
ui`GhseS`GQ    Implicit variable introduction
u         Q    Repeatedly apply the following function until the value repeats,
               starting with Q, the input.
        `G     Convert the working value to a string.
      eS       Take its maximum.
     s         Convert to an integer.
    h          Add one.
 i`G           Convert the working value to that base

```

# Answer
> 6 votes
# JavaScript (ES6), 63 57 54 53 bytes

```
f=a=>a>9&(b=Math.max(...a+""))<9?f(parseInt(a,b+1)):a

```

Saved 8 bytes thanks to Shaggy and Dom Hastings

```
f=a=>a>9&(b=Math.max(...a+""))<9?f(parseInt(a,b+1)):a;

console.log(f("413574"))
```

# Answer
> 5 votes
# Python 3, ~~91 78 76 75~~ 73 bytes

*@Emigna shaved off 5 bytes. @FelipeNardiBatista saved 1 byte. @RomanGräf saved 2 bytes*

```
i=input()
while'9'>max(i)and~-len(i):i=str(int(i,int(max(i))+1))
print(i)

```

Try it online!

---

## Explanation

```
i=input()                                  - takes input and assigns it to a variable i
while '9'>max(i)and~-len(i):               - repeatedly checks if the number is still base-9 or lower and has a length greater than 1
    i=str(...)                             - assigns i to the string representation of ...
          int(i,int(max(i))+1)             - converts the current number to the real base 10 and loops back again
print(i)                                   - prints the mutated i

```

# Answer
> 5 votes
# 05AB1E, ~~10~~ 5 bytes

5 bytes saved thanks to *Magic Octopus Urn*

```
F§Z>ö

```

As this grows slow very quickly for large input, I'm leaving the old much faster version here for testing. The algorithm is the same, only the number of iterations differ.

```
[©Z>öD®Q#§

```

Try it online!

**Explanation**

```
[             # start a loop
 ©            # store a copy of the current value in the register
  Z>          # get the maximum (digit) and increment
    ö         # convert the current value to base-10 from this base
     D        # duplicate
      ®Q#     # break loop if the new value is the same as the stored value
         §    # convert to string (to prevent Z from taking the maximum int on the stack)

```

# Answer
> 3 votes
# APL (Dyalog), ~~20~~ 16 bytes

Takes and returns a string

```
((⍕⊢⊥⍨1+⌈/)⍎¨)⍣≡

```

`(``)⍣≡` apply the following function until two consecutive terms are identical:

`⍎¨` execute each character (turns the string into a list of numbers)

`(``)` apply the following tacit function to that:

`⌈/` find the maximum of the argument

`1+` add one

`⊢⊥⍨` evaluate the argument in that base

format (stringify, in preparation for another application of the outer function)

Try it online!

# Answer
> 3 votes
# Ruby, ~~60~~ 56 bytes

```
->n{n=(s=n.to_s).to_i(s.bytes.max-47)while/9/!~s&&n>9;n}

```

Try it online!

# Answer
> 3 votes
# Mathematica, 52 bytes

```
FromDigits[s=IntegerDigits@#,Max@s+1]&~FixedPoint~#&

```

Pure function taking a nonnegative integer as input and returning a nonnegative integer. Uses the same core mechanic `FromDigits[s=IntegerDigits@#,Max@s+1]` as Jenny\_mathy's answer, but exploits `FixedPoint` to do the iteration.

# Answer
> 3 votes
# Perl 6, 49 bytes

```
{($_,{.Str.parse-base(1+.comb.max)}...*==*).tail}

```

Test it

## Expanded:

```
{
  (

    $_,                 # seed the sequence with the input

    {
      .Str
      .parse-base(      # parse in base:
        1 + .comb.max   # largest digit + 1
      )
    }

    ...                 # keep generating values until

    * == *              # two of them match (should only be in base 10)

  ).tail                # get the last value from the sequence
}

```

# Answer
> 2 votes
# Python 2, ~~60~~ ~~59~~ ~~56~~ 53 bytes

Saved 4 byte thanks to *Felipe Nardi Batista*
Saved 3 bytes thanks to *ovs*

```
f=lambda x,y=0:x*(x==y)or f(`int(x,int(max(x))+1)`,x)

```

Try it online!

Using a recursive lambda, comparing the result of the base conversion to the previous iteration.

# Answer
> 2 votes
# PHP, 71 bytes

```
for(;$b<10&9<$n=&$argn;)$n=intval("$n",$b=max(str_split($n))+1);echo$n;

```

Try it online!

# Answer
> 2 votes
# Pip, 17 bytes

```
Wa>9>YMXaaFB:1+ya

```

Takes input as a command-line argument. Try it online!

### Explanation

This was fun--I got to pull out the chaining comparison operators.

We want to loop until the number is a single digit OR contains a 9. Equivalently, we want to loop while the number is multiple digits AND does not contain a 9. Equivalently, loop while the number is greater than 9 AND the maximum digit is less than 9: `a>9>MXa`.

```
Wa>9>YMXaaFB:1+ya
                   a is 1st cmdline arg (implicit)
     YMXa          Yank a's maximum digit into the y variable
Wa>9>              While a is greater than 9 and 9 is greater than a's max digit:
         aFB:1+y    Convert a from base 1+y to decimal and assign back to a
                a  At the end of the program, print a

```

# Answer
> 2 votes
## C#, 257 244 243 244 233 222 bytes

```
using System.Linq;z=m=>{int b=int.Parse(m.OrderBy(s=>int.Parse(s+"")).Last()+""),n=0,p=0;if(b<9&m.Length>1){for(int i=m.Length-1;i>=0;i--)n+=int.Parse(m[i]+"")*(int)System.Math.Pow(b+1,p++);return z(n+"");}else return m;};

```

Well, C# always takes a lot of bytes but this is just ridiculous. None of the built-ins can handle an arbitrary base, so I had to calculate the conversion myself. Ungolfed:

```
using System.Linq;
z = m => {
int b = int.Parse(m.OrderBy(s => int.Parse(s + "")).Last()+""), n = 0, p = 0; //Get the max digit in the string
if (b < 9 & m.Length > 1) //if conditions not satisfied, process and recurse
{
    for (int i = m.Length - 1; i >= 0; i--)
        n += int.Parse(m[i] + "") * (int)System.Math.Pow(b+1, p++); //convert each base-b+1 representation to base-10
    return z(n + ""); //recurse
}
else return m; };

```

# Answer
> 1 votes
# Mathematica, 92 bytes

```
f[x_]:=FromDigits[s=IntegerDigits@x,d=Max@s+1];(z=f@#;While[d!=10&&Length@s>1,h=f@z;z=h];z)&

```

# Answer
> 1 votes
# Javascript (ES6) with 0 arrow function, 74 bytes

```
function f(a){a>9&&b=Math.max(...a)<9&&f(parseInt(a,b+1));alert(a)}f('11')

```

# Answer
> 1 votes
# K4, 19 bytes

**Solution:**

```
{(1+|/x)/:x:10\:x}/

```

**Examples:**

```
q)\
  {(1+|/x)/:x:10\:x}/413574
83911
  {(1+|/x)/:x:10\:x}/13552
159
  {(1+|/x)/:x:10\:x}/17
3
  {(1+|/x)/:x:10\:x}/41253
29

```

**Explanation:**

Use `/:` built-in to convert base.

```
{(1+|/x)/:x:10\:x}/ / the solution
{                }/ / converge lambda, repeat until same result returned
            10\:x   / convert input x to base 10 (.:'$x would do the same)
          x:        / store in variable x
 (     )/:          / convert to base given by the result of the brackets
    |/x             / max (|) over (/) input, ie return largest
  1+                / add 1 to this

```

# Answer
> 1 votes
# Kotlin, 97 bytes

```
fun String.f():String=if(length==1||contains("9"))this else "${toInt(map{it-'0'}.max()!!+1)}".f()

```

## Beautified

```
fun String.f(): String = if (length == 1 || contains("9")) this else "${toInt(map { it - '0' }.max()!! + 1)}".f()

```

## Test

```
fun String.f():String=if(length==1||contains("9"))this else "${toInt(map{it-'0'}.max()!!+1)}".f()
val tests = listOf(
        5 to 5,
        17 to 3,
        999 to 999,
        87654321 to 9041998,
        41253 to 29
)

fun main(args: Array<String>) {
    tests.forEach { (input, output) ->
        val answer = input.toString().f()
        if (answer != output.toString()) {
            throw AssertionError()
        }
    }
}

```

## TIO

TryItOnline

# Answer
> 1 votes
# Husk, 8 bytes

```
ωoṠBo→▲d

```

Try it online!

```
ωoṠBo→▲d
ω           # repeat until output no longer changes:
 oṠ         # apply function to value & function-of-value
       d    # value: digits of argument
   Bo→▲     # function of value:
   B        # interpret digits as base n, with n given by
    o→▲     # max digit +1

```

# Answer
> 0 votes
# Japt, 25 bytes

```
>9©(A=Uì rw)<9?ßUs nAÄ):U

```

Try it online!

# Answer
> 0 votes
# Jelly, 9 bytes

```
DḅṀ‘$$µÐL

```

Try it online!

# Answer
> 0 votes
# C, ~~159~~ 157 bytes

```
#include <stdlib.h>
char b[99];i=0;m=-1;c(n){do{m=-1;sprintf(b,"%d",n);i=0;while(b[i]){m=max(b[i]-48,m);i++;}n=strtol(b,0,++m);}while(b[1]&&m<10);return n;}

```

# Answer
> 0 votes
# Scala, 119 bytes

```
if(x.max==57|x.length==1)x else{val l=x.length-1
f((0 to l).map(k=>(((x(k)-48)*math.pow(x.max-47,l-k))) toInt).sum+"")}

```

Try it online!

# Scala, 119 bytes

```
if(x.max==57|x.length==1)x else f((0 to x.length-1).map(k=>(((x(k)-48)*math.pow(x.max-47,x.length-1-k))) toInt).sum+"")

```

Try it online!

Both methods work the same way, but in the first one I put `x.length-1` in a variable, and in the second one I don't.

# Answer
> 0 votes
# Japt, 12 bytes

```
_=ì)ìZrÔÄ}gN

```

Try it

# Answer
> 0 votes
# , 22 bytes

```
(#.~1+>./)@(,.&.":)^:_

```

Try it online!

# Answer
> 0 votes
# Vyxal, 6 bytes

```
fG›β)Ẋ

```

Try it Online!

Will be 5 bytes once a bug fix is made.

## Explained

```
fG›β)Ẋ
    )Ẋ # Until the result of applying the following does not change:
fG     #   Get the biggest digit of the current value - should just be G, but bugs
  ›β   #   and convert the current value from base (the biggest digit + 1) to base 10

```

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