title: Score a 1 player game of Carcassonne

text:
# Question
Title: Score a 1 player game of Carcassonne
Carcassonne is a tile-based game, where the objective is to construct Roads, Cities and Monasteries, in order to score points. The game works by players taking turns to draw and place tiles to construct a landscape, then claiming roads, cities and monasteries. An example landscape is:

There are \\$19\\$ distinct tiles (ignoring rotations), each of which contains at least one feature (Road, City or Monastery):

Also, notice that the landscape must be consistent. This means that roads must connect to other roads, city edges must connect to other city edges and fields must connect to fields. Therefore, these tiles are inconsistent:

In a normal game of Carcassonne, each feature in the landscape is claimed by a player, and contributes to their final score. However, in this version, we will change the rules slightly (primarily for people who already know the standard Carcassonne rules):

* There will only be \\$1\\$ player
* The player will automatically own every feature in the landscape
* There will be no "badge" score for cities
    + Notice that in some of the tiles in the pictures have badge symbols on them. In this challenge, we're ignoring them.

In a landscape, each feature is either complete or incomplete:

* A complete monastery is one where it's tile is surrounded by \\$8\\$ tiles. This landscape contains one complete monastery (in the center) and one incomplete monastery (Top center).
* A complete city is one fully enclosed by walls. This landscape has \\$2\\$ complete cities and \\$2\\$ incomplete cities.
* A complete road is one where both ends terminate at either a city, village or by forming a loop. This landscape has \\$2\\$ complete roads and \\$2\\$ incomplete roads.

A landscape is scored as follows:

* For every complete city, the player scores \\$2\\$ points for every tile containing that city. Therefore this city scores \\$4\\$ points, and this city scores \\$18\\$ points.
* For every complete road, the player scores \\$1\\$ point for every tile containing that road. Therefore this road scores \\$6\\$ points, and this road scores \\$2\\$.
* For every complete monastery, the player scores \\$9\\$ points, such as this monastery.
* For every incomplete city, the player scores \\$1\\$ point for every tile containing that city. This landscape contains two incomplete cities, one scoring \\$2\\$ and the other \\$5\\$.
* For every incomplete road, the player scores \\$1\\$ point for each tile containing that road. This landscape contains three incomplete roads, scoring \\$1\\$, \\$2\\$ and \\$3\\$ points.
* For every incomplete monastery, the player scores \\$1\\$ point for each tile that neighbours the monastery, plus \\$1\\$ for the monastery itself. This landscape contains \\$3\\$ monasteries, scoring \\$2\\$, \\$5\\$ and \\$7\\$.

Take this landscape:

This landscape contains \\$1\\$ complete city, \\$2\\$ incomplete cities, \\$4\\$ complete roads, \\$2\\$ incomplete roads and \\$1\\$ incomplete monastery which scores \\$4 + (3+3) + (3+2+6+2) + (4+2) + 4 = 33\\$ points.

---

To avoid this challenge being about image processing, we can translate each tile into a list containing \\$5\\$ values, according to this legend:

```
[North edge, East edge, South edge, West Edge, # of cities]

0: Field
1: Road
2: City

```

For instance, this tile can be described as `[2, 0, 1, 1, 1]`. Using this legend, we can describe each tile uniquely, and it's rotations are rotations of the first four elements. The entire grid can be described as a rectangular matrix, with a \\$20^\text{th}\\$ distinct value for an empty square. Translating the first landscape into this format, we get:

```
[
 [             [],              [], [1, 1, 0, 0, 0], [1, 1, 2, 1, 1], [0, 1, 0, 1, 0],              [],              []],
 [[1, 0, 1, 0, 0],              [], [0, 0, 0, 0, 0], [2, 0, 2, 0, 2],              [], [0, 2, 2, 2, 1], [0, 0, 0, 2, 1]],
 [[1, 1, 0, 1, 0], [0, 0, 1, 1, 0], [0, 0, 0, 0, 0], [2, 2, 0, 0, 1], [2, 2, 0, 2, 1], [2, 0, 0, 2, 1],              []]
]

```

using `[]` to represent an empty square. The complete list of tiles (ignoring rotations) in the same grid as the second image is

```
[1, 0, 1, 0, 0] [0, 0, 1, 1, 0] [2, 1, 1, 1, 1] [0, 1, 1, 1, 0] [2, 0, 0, 0, 1]
[2, 2, 0, 2, 1] [0, 0, 0, 0, 0] [2, 2, 2, 2, 1] [2, 2, 0, 0, 1] [2, 1, 1, 2, 1]
[2, 2, 0, 0, 2] [0, 0, 1, 0, 0] [2, 0, 1, 1, 1] [2, 1, 1, 0, 1] [0, 2, 0, 2, 1]
[1, 1, 1, 1, 0] [2, 1, 0, 1, 1] [2, 2, 1, 2, 1] [2, 0, 2, 0, 2]

```

Note that the only way to distinguish tiles with monasteries and villages is by the number of roads/cities on the tile, and that there is no specific indicator that a tile has a monastery/village aside from the roads.

---

Your task is to take a matrix of lists in the above format representing a landscape and to output the score the player would have if they claimed all the features, complete or incomplete, in the landscape. You may take input in any convenient method, may choose any three consistent values to represent Field, City and Road edges and may use any value to represent the empty squares that isn't already a tile. Output must be an integer represented in your language's most natural format. If you aren't sure about an I/O format, just ask.

In addition, the inputs will always have consistent landscapes, and will always have at least 1 tile. Finally, the tiles will not be constrained by the tile availability (like in the real game).

This is so the shortest code in bytes wins.

## Test cases

Each test case has the matrix followed by the score, with the score breakdown underneath with abbreviations.

```
[[[], [], [1, 1, 0, 0, 0], [1, 1, 2, 1, 1], [0, 1, 0, 1, 0], [], []], [[1, 0, 1, 0, 0], [], [0, 0, 0, 0, 0], [2, 0, 2, 0, 2], [], [0, 2, 2, 2, 1], [0, 0, 0, 2, 1]], [[1, 1, 0, 1, 0], [0, 0, 1, 1, 0], [0, 0, 0, 0, 0], [2, 2, 0, 0, 1], [2, 2, 0, 2, 1], [2, 0, 0, 2, 1], []]] -> 32
1 c. city (4), 1 i. city (6), 6 i. roads (10), 2 i. monasteries (12)

[[[0, 2, 2, 2, 1], [1, 0, 1, 2, 1], [0, 1, 1, 0, 0], [2, 2, 2, 1, 1]], [[2, 1, 1, 2, 1], [1, 0, 0, 1, 0], [1, 1, 1, 0, 0], [2, 2, 2, 1, 1]], [[1, 1, 1, 0, 0], [0, 2, 1, 1, 1], [1, 0, 1, 2, 1], [2, 1, 1, 0, 1]], [[1, 0, 0, 0, 0], [1, 1, 0, 0, 0], [1, 0, 0, 1, 0], [1, 0, 1, 0, 0]]] -> 33
1 c. city (4), 2 i. cities (6), 4 c. roads (13), 2 i. roads (6), 1 i. monastery (4)

[[[0, 1, 1, 0, 0], [2, 1, 0, 1, 1], [1, 2, 1, 1, 1], [0, 2, 0, 2, 1], [0, 1, 1, 2, 1]], [[], [], [1, 0, 2, 1, 1], [0, 1, 1, 0, 0], [1, 2, 1, 1, 1]], [[2, 1, 0, 1, 1], [1, 2, 1, 1, 0], [2, 1, 1, 2, 1], [], [1, 1, 0, 1, 0]], [[], [1, 0, 0, 1, 1], [1, 0, 1, 0, 0], [2, 2, 0, 0, 2], [0, 1, 1, 2, 1]]] -> 39
2 c. cities (12), 4 i. cities (5), 1 c. road (2), 12 i. roads (20)

[[[2, 1, 1, 0, 1]]] -> 2
1 i. city (1), 1 i. road (1)

[[[1, 2, 1, 1, 1], [0, 0, 0, 2, 1], [], [1, 1, 0, 1, 0], [2, 2, 2, 1, 1]], [[1, 0, 1, 0, 0], [], [2, 0, 2, 0, 2], [0, 0, 0, 0, 0], []], [[1, 1, 2, 2, 1], [0, 1, 0, 1, 0], [2, 0, 1, 1, 1], [], []], [[], [], [2, 2, 1, 2, 1], [], []]] -> 29
2 c. cities (8), 4 i. cities (4), 2 c. roads (8), 4 i. roads (4), 1 i. monastery (5)

[[[], [0, 0, 2, 0, 1], [], [], [0, 0, 2, 0, 1], [], [], []], [[], [2, 1, 1, 0, 1], [0, 1, 0, 1, 0], [0, 1, 0, 1, 0], [2, 0, 1, 1, 1], [], [], []], [[], [1, 0, 1, 0, 0], [0, 2, 2, 0, 1], [0, 2, 2, 2, 1], [1, 1, 2, 2, 1], [0, 0, 1, 1, 0], [], []], [[0, 1, 1, 0, 0], [1, 2, 2, 1, 1], [2, 0, 2, 2, 1], [2, 0, 2, 0, 1], [2, 2, 0, 0, 2], [1, 1, 2, 2, 1], [0, 1, 2, 1, 1], [0, 0, 1, 1, 0]], [[1, 1, 1, 0, 0], [2, 2, 2, 1, 1], [2, 2, 2, 2, 1], [2, 1, 2, 2, 1], [0, 0, 0, 1, 0], [2, 2, 0, 0, 1], [2, 1, 2, 2, 1], [1, 0, 1, 1, 0]], [[1, 0, 1, 0, 0], [2, 2, 0, 0, 1], [2, 0, 2, 2, 1], [2, 0, 2, 0, 1], [0, 0, 0, 0, 0], [0, 2, 2, 0, 1], [2, 1, 1, 2, 1], [1, 0, 0, 1, 0]], [[1, 1, 0, 0, 0], [0, 0, 1, 1, 0], [2, 2, 0, 0, 1], [2, 2, 0, 2, 1], [0, 2, 0, 2, 1], [2, 1, 1, 2, 1], [1, 0, 0, 1, 0], []], [[], [1, 1, 0, 0, 0], [0, 1, 0, 1, 0], [0, 1, 0, 1, 0], [0, 1, 0, 1, 0], [1, 0, 0, 1, 0], [], []]] -> 106
3 c. cities (54), 5 c. roads (34), 2 c. monasteries (18)

```

Note that in the largest city in the final example, the tile `[2, 2, 0, 0, 2]` has two sections of the city, but is only a single tile. Therefore, it only counts for 2 points, not 4.

If you have a copy of Carcassonne, I'd highly recommend building the test cases, if only to help visualise them

# Answer
# Charcoal, ~~306~~ 246 bytes

```
Ｅθ⭆ι⎇λ⊟λψ≔ΣＥθΣＥι∨⁼²№λ¹№λ¹ζＦＬθＦＬ§θι«Ｊκι¿›²Σ∨§§θικ²≧⁺⊕ＬΦＫＭ℅λζ»ＦＬθＦＬ§θι«Ｊκι¿⁼²ΣＫＫ«≔⌕§§θικ²δ≔δεＭ✳⁻χ⊗ε¿ΣＫＫ«Ｗ∨⁻ⅉι⁻ⅈκ«≧⁻ΣＫＫεＷ∨›²§§§θⅉⅈε¬Σ§ＫＶε≦⊕εＭ✳⁻χ⊗ε»¿¬⁼﹪⁺²ε⁴δ1»»»Ｗφ«≔⁰φＦＬθＦＬ§θκ«Ｊλκ≔ΣＫＫδ≔§§θκλη≔∧δΦ⌕Ａη²¬℅§ＫＶμε¿ε«≔¹φ¿‹Ｌεδ«§≔η⊟ε⁰≔¹δ1»ψ≧⁺δζ»»»≧⁺⊗ΣＥＫＡΣιζ⎚Ｉζ

```

Try it online! Link is to verbose version of code. Explanation:

```
Ｅθ⭆ι⎇λ⊟λψ

```

Start by printing the number of cities on each tile so that the tiles can be walked using canvas operations rather than array indexing. Just getting the number of cities via `AtIndex(AtIndex(AtIndex(q, i), k), 4)` normally takes 7 bytes, whereas it can be read from the canvas in only 6 via `JumpTo(k, i);` and then `Sum(Peek())` (although obviously we can only do that as a separate statement). We can also directly inspect adjacent cells using `PeekMoore()` and `PeekVonNeumann()` to see whether they are empty tiles (empty tiles will be a null byte or an empty string for out-of-range tiles, but both have an ordinal of 0). Furthermore, removing the city count data from the input array makes the code to deal with the features cleaner (i.e. shorter).

```
≔ΣＥθΣＥＥι№λ¹∨⁼²λλζ

```

Start off by counting the roads. Complete and incomplete roads both score their length, so the only special case here is that a tile with two roads only scores 1.

```
ＦＬθＦＬ§θι«Ｊκι¿›²Σ∨§§θικ²≧⁺⊕ＬΦＫＭ℅λζ»

```

Next, find the monasteries, whose tiles have with no features apart from an optional road. For each monastery, simply count one more than the number of adjacent tiles, since complete monasteries count 9 anyway.

```
ＦＬθＦＬ§θι«

```

We need to check whether tiles with two cities are connected. Loop over all of the tiles.

```
Ｊκι¿⁼²ΣＫＫ«

```

Is this a tile of two cities?

```
≔⌕§§θικ²δ≔δεＭ✳⁻χ⊗ε

```

Pick one of the city directions and move one step.

```
¿ΣＫＫ«

```

Is there city here?

```
Ｗ∨⁻ⅉι⁻ⅈκ«

```

Repeat until we get back to the original tile.

```
≧⁻ΣＫＫε

```

If this is a different tile of two cities, then immediately U-turn, otherwise turn left. This allows us to perform a left-following maze traversal.

```
Ｗ∨›²§§§θⅉⅈε¬Σ§ＫＶε≦⊕ε

```

Turn right until there is a connected city.

```
Ｍ✳⁻χ⊗ε

```

Move to the next city.

```
»¿¬⁼﹪⁺²ε⁴δ1»»»

```

If we did not arrive in the opposite direction to which we left, then the two cities on this tile are actually connected, so count them as a single city.

```
Ｗφ«≔⁰φ

```

Next, we need to find tiles with incomplete cities. Use a variable with a predefined non-zero value as a loop variable, but immediately set it to zero inside the loop.

```
ＦＬθＦＬ§θκ«

```

Loop over each tile.

```
Ｊλκ≔ΣＫＫδ≔§§θκλη≔∧δΦ⌕Ａη²¬℅§ＫＶμε

```

Check for adjacent tiles in the appropriate directions. We can assume that these tiles will be city tiles if they exist, but if they don't exist then this tile is part of an incomplete city.

```
¿ε«≔¹φ

```

If so, then note that we had an incomplete city for later.

```
¿‹Ｌεδ«

```

If this tile has two cities, but only one was found to be incomplete, then...

```
§≔η⊟ε⁰

```

... mark that direction as a field, and...

```
≔¹δ

```

... reduce the score for this tile to 1, and...

```
1

```

... reduce the number of remaining cities to 1.

```
»ψ

```

Otherwise delete the tile completely. This will cause any adjacent city tiles to be (re)evaluated for incompleteness.

```
≧⁺δζ»»»

```

Score the number of cities deleted.

```
≧⁺⊗ΣＥＫＡΣιζ

```

Score two for any remaining cities on the remaining tiles, as these must now be complete cities.

```
⎚Ｉζ

```

Clear the canvas and output the final score.
> 14 votes

---
Tags: code-golf, array, board-game
---


# Question
Title: Descending dungeons of positional systems
The sequence discussed in this challenge is a variant of the Descending Dungeons sequence family. Specifically, the sequence generation rules:

```
(A_b = A's base 10 representation read as a base b number, A = A_10)
A(0) = 10
A(n) = 10_(11_(12_(...(n+9)_(n+10))))

```

Your goal is to make a program which accepts a nonnegative integer `n` and returns A(n) of the descending dungeons sequence, using 0-indexing.

Base conversion built-ins are allowed.

Return the result itself in base 10.

Test cases: (`A = B` means `input A returns B`)

```
0 = 10
1 = 11
2 = 13
3 = 16
4 = 20
5 = 25
6 = 31
7 = 38
8 = 46
9 = 55
10 = 65
11 = 87
12 = 135
13 = 239
14 = 463
15 = 943
16 = 1967
17 = 4143
18 = 8751
19 = 18479
20 = 38959

```

Use OEIS A121263 for further test cases.

This is code golf, so the shortest program wins. Have fun.

Final sidenote: This sequence came to my attention through a recent Numberphile video discussing descending dungeon sequences.

# Answer
# 05AB1E, 6 bytes

```
ÝT+.«ö

```

Basically a golfed version of *@hi.*'s 05AB1E answer, which I suggested as a golf in the comments of his/her answer. Since I got no response, I figured I'd just post it myself instead.

Try it online or verify all test cases.

**Explanation:**

```
Ý       # Push a list in the range [0, (implicit) input-integer]
 T+     # Add 10 to each value in this list
   .«   # Right-reduce this list by:
     ö  #  Base-conversion
        # (after which the result is output implicitly)

```

You can replace the `.` with `Å` to see each step of the reduction (from right to left).
> 2 votes

# Answer
# Jelly, 9 bytes

```
Ż+⁵ṚDḅ¥@/

```

A monadic Link accepting a non-negative integer which yields a non-negative integer.

**Try it online!** Or see the test-suite.

### How?

```
Ż+⁵ṚDḅ¥@/                  e.g. 5
Ż         - zero-range          [0,1,2,3,4,5]
  ⁵       - ten                 10
 +        - add                 [10,11,12,13,14,15]
   Ṛ      - reverse             [15,14,13,12,11,10]
        / - reduce by:          f(f(f(f(f(15,14),13),12),11),10)
       @  -   using swapped arguments:         e.g. f(y=15,x=14)
      ɗ   -     last two links as a dyad
    D     -       decimal (x)                       [1,4]
     ḅ    -       convert (that) from base (y)      19
                           i.e. f(f(f(f(f(15,14),13),12),11),10)
                              = f(f(f(f(19,13),12),11),10)
                              = f(f(f(22,12),11),10)
                              = f(f(24,11),10)
                              = f(25,10)
                              = 25

```
> 7 votes

# Answer
# Python 3, ~~75~~ 72 bytes

```
f,g=lambda n:n and f(n-1)+n*g(n)or 10,lambda n:n and(n+9)//10*g(n-1)or 1

```

Try it online!

Explanation: On observing the terms, I came across this recursive relation

`f(n) = f(n-1) + n*g(n)` where `g(n)` is the product of first `n` terms of the sequence

`1^1, 1^2, ... 1^10, 2^1, 2^2, 2^3, ... 2^10, 3^1, 3^2, 3^3 ...`

---

# Python 3, ~~69~~ 65 bytes

```
f=lambda n:n<2and n+10or(f(n-1)-f(n-2))*n//~-n*((n+9)//10)+f(n-1)

```

Try it online!

Explanation: This is an even more recursive approach of the above solution, with the `g` function completely removed. However note that this one is highly inefficient.

`f(n) = f(n-1) + n*g(n)` implies `g(n-1) = (f(n-1) - f(n-2))/(n-1)`

---

*Special thanks to Jo King for -4 bytes.*
> 4 votes

# Answer
# JavaScript (ES6), 54 bytes

```
n=>(F=i=>(g=k=>i>n?k:k&&k%10+F(i)*g(k/10|0))(++i+9))``

```

Try it online!

### Commented

```
n => (                // n = input
  F = i => (          // F is a recursive function taking a counter i
    g = k =>          //   g is a recursive function taking a number k
                      //   and returning either k if i > n or k converted
                      //   from base F(i) to decimal otherwise
      i > n ?         //     if i is greater than n:
        k             //       just return k
      :               //     else:
        k &&          //       return 0 if k = 0
        k % 10 +      //       otherwise extract the last digit of k
        F(i) *        //       and add F(i) multiplied by the result of
        g(k / 10 | 0) //       a recursive call with floor(k / 10)
  )(++i + 9)          //   increment i; initial call to g with k = i + 9
)``                   // initial call to F with i zero'ish

```
> 2 votes

# Answer
# Python 3, ~~110~~ ~~107~~ ~~87~~ ~~85~~ 90 bytes

```
f=lambda n,b=10:f(n-1,sum((int(v)*b**i)for i,v in enumerate(str(10+n)[::-1])))if n+1else b

```

Try it online!

Uses recursion to compute the solution.
> 2 votes

# Answer
# Pyth, 12 bytes

```
.UijZTb}+TQT

```

Try it online!

## Explanation

```
.UijZTb}+TQT
       }+TQT  # inclusive range [10 + input, 10]
.U            # reduce left to right by: f(b, Z)
   jZT        #   list of Z  (e.g. 123 -> [1, 2, 3])
  i   b       #   convert that from base b

```
> 1 votes

# Answer
# Scala, ~~105~~...~~57~~ 50 bytes

```
n=>((10 to n+10):\10)((i,r)=>(0/:s"$i")(_*r+_-48))

```

Scastie

Well, this has been a fun problem.

Explanation:

```
n =>
    ((10 to n+10) //A range from 10 to n+10
      :\10) (     //Fold it right with the initial value of 10
      (i, r) =>      //r is the current base, i is the counter
        (0 /: s"$i") //Make i a string/iterable of chars, and fold it left with an initial value of 0
           (_*r + _-48) //Multiply the previous value by r and add the current value to that (-48 because it's a Char and not a proper Int)
      )

```
> 1 votes

# Answer
# Charcoal, 21 bytes

```
Ｎθ≔⁺θχηＦθ≔⍘Ｉ⁻⁺θ⁹ιηηＩη

```

Try it online! Link is to verbose version of code. Explanation:

```
Ｎθ

```

Input `n`.

```
≔⁺θχη

```

Start with `n+10`.

```
Ｆθ

```

Loop `n` times.

```
≔⍘Ｉ⁻⁺θ⁹ιηη

```

Cast the previous integer to string and interpret it using the current base.

```
Ｉη

```

Print the final value as a string.
> 1 votes

# Answer
# Retina 0.8.2, 88 bytes

```
.+
10$*@$&$*;
(?!@)
$.`
\d+$
$*#
{`#(?=#*\d*;(#+)$)
$1
(\d)(\d*;#+)$
$1$*#$2
}`#;#+$
#
#

```

Try it online! Link includes some test cases (code gets too slow for TIO with larger numbers). Explanation:

```
.+
10$*@$&$*;

```

Convert the input to `n` `;`s, and prepend with 10 `@`s.

```
(?!@)
$.`

```

Insert the decimal numbers `10..n+10` around the `;`s.

```
\d+$
$*#

```

Convert the last number to unary using `#`s.

```
{`
}`

```

Reduce right-to-left over the list of numbers and left-to-right over the digits of each number.

```
#(?=#*\d*;(#+)$)
$1

```

Multiply the partial result so far by the base.

```
(\d)(\d*;#+)$
$1$*#$2

```

Add the next digit of the number to convert.

```
#;#+$
#

```

Once the number has been converted, delete the previous base, so that this result can serve as the base for the next conversion.

```
#

```

Once all of the numbers have been converted, convert the result to decimal.
> 1 votes

# Answer
# Io, 101 bytes

```
method(x,Range 10 to(x+10)asList reverseReduce(i,j,j asString asList map(asNumber)reduce(x,y,x*i+y)))

```

Try it online!

## Explanation

```
method(x,                // Take an argument x
    Range 10 to(x+10)    // [10..x+10]
    asList               // Reduce doesn't work on ranges
    reverseReduce(i,j,   // Reverse the list. Reduce (arguments i & j):

                         //     tl;dr base conversion from j (base 10) to base i
        j asString       //     Convert to string,
        asList           //     Convert to list,   (splits string into individual chars)
        map(asNumber)    //     (Map) Convert to number.
        reduce(x,y,      //     Reduce the digit list by (arguments x & y):
            x*i+y)))     //          x*i+y

```
> 1 votes

# Answer
# , ~~71~~ 62 bytes

*Edits: +3 bytes to fix output for edge-case of n=0, but then -12 bytes by skipping calculation of number of digits each step and simply calculating over an excessively large number of digits)*

```
n=i=scan()+10;while((i=i-1)>10)n=sum(i%/%10^(m=i:0)%%10*n^m);n

```

Try it online!

Readable (un-golfed) version:

```
n=i=scan()+10               # get n and add 10; set i to same value as n
'%_%'=function(a,b)         # Define infix _ function
                            # (this is incorporated directly inline in golfed code):
    m=rev(0:log10(a))       #   m = exponents-of-ten for each digit of a
                            #   (in golfed code we use m=a:0 which is much shorter
                            #   but uselessly includes exponentially more digits,
                            #   which will all contribute zero to the final sum)
    sum(                    #   get sum of...
        a %/% 10^m %% 10    #   each base-10 digit of a...
        * b^m )             #   multiplied by corresponding exponent-of-b.
while((i=i-1)>10)           # Main loop from (n-1)..10:
    n = i %_% n             #   n = i _ n
n                           # Output n

```
> 1 votes

# Answer
# APL (Dyalog Unicode), ~~25~~ ~~21~~ 18 bytes

* *Saved 4 bytes thanks to @ovs*
* *Saved 3 bytes thanks to @Adám*

```
(⊢⊥10⊥⍣¯1⊣)/9+⍳⎕+1

```

Try it online!

Accepts input through STDIN.

```
(⊢⊥10⊥⍣¯1⊣)/9+⍳⎕+1
             9+⍳⎕+1  ⍝ Create a range from 10 to n+10
            /        ⍝ Then fold over it with the train on the left:
   10(⊥⍣¯1)          ⍝ Get the digits of (inverse of interpreting in base 10)
           ⊣         ⍝ A (the number on the left).
 ⊥                   ⍝ Interpret in base
⊢                    ⍝ b (the accumulated value on the right)

```
> 1 votes

# Answer
# Retina, 72 bytes

```
.+
*
L$`
0;$.($`10*
$
¶10
{+`\d+;(\d)(\d*¶(\d+))$
$.(*$3*_$1*);$2
;¶.+$

```

Try it online! Link includes test cases. Explanation:

```
.+
*

```

Convert the input to unary.

```
L$`
0;$.($`10*

```

For each integer in the range `[0..n]`, output `0;` followed by 10 more than the integer, in decimal. The decimal is the value to be converted to the appropriate base, and the `0;` represents the initial value of the conversion.

```
$
¶10

```

Append an extra base `10` to simplify the algorithm.

```
{

```

Reduce (right-to-left) over the list of numbers.

```
+`

```

Reduce (left-to-right) over the second last number.

```
\d+;(\d)(\d*¶(\d+))$
$.(*$3*_$1*);$2

```

Multiply the result so far (implicitly the first number in the match) by the base (`$3`) and add the next digit of the second last number (`$1`).

```
;¶.+$

```

Delete the base.
> 0 votes

# Answer
# Japt, 10 bytes

Port of Jonathan's Jelly solution.

```
AôU ÔrÏììX

```

Try it

```
AôU ÔrÏììX     :Implicit input of integer U
A              :10
 ôU            :Range [A,A+U]
    Ô          :Reverse
     r         :Reduce
      Ï        :X=current total (initially first element) Y=current element (initially the second)
       ì       :Convert Y to base-10 digit array
        ìX     :Convert from base-X digit array

```
> 0 votes

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


# Question
Title: How to golf evaluation of math expression in MySQL?
The challenge given to me is comparatively easy, and specific to MySQL *only*. I'm given a table `expressions` which have mathematical calculations done by a kid. Basically, I've to `select` all the right calculations!

The table have the following properties,

* `a` : an integer, *the left operand*.
* `b` : an integer, *the right operand*.
* `operation` : a char, any one operation from `'+'`, `'-'`, `'*'` and `'/'` (pure-div).
* `c` : an integer, the result given by *the kid*.

# Example

```
a  b  operation  c
------------------
2  3  +          5
4  2  /          3
6  1  *          9
8  5  -          3

```

As we can see, the second and third operations are wrongly calculated, so they need to be filtered out. Here is what I've done till now,

# MySQL, 88 chars

*Rule:* 88 chars is calculated by removing *all spaces* (`\s+`) from the given code. This is MySQL, so they simply take amount of chars (calculated here).

```
select * from expressions
where if(
    '+' = @o := operation,
    a + b,
    if(
        @o = '-',
        a - b,
        if(
            @o = '*',
            a * b,
            a / b
        )
    )
) = c

```

Try it on Rextester!

But, I'm sure that this can be golfed further, as many other submissions are of `73` chars, which is `15` bytes fewer than mine!

I think I need to change the idea of my solution, but I can't find anything which can evaluate expressions directly in MySQL. Any ideas?

# Rules

* The names, specific to table, included in the code isn't subject to change.
* `select` is considered to be the only method to output/result.
* For multiple statements, it should be wrapped inside `begin ... end`, as the whole code is the body of a function, defined as,
`CREATE PROCEDURE expressionsVerification()`

# Answer
> 8 votes
# Score 69

```
select * from expressions
where elt(ord(operation)/2-20,a*b,a+b,a-b,a/b)=c

```

Takes inspiration from Marmite Bomber's use of `elt`, but uses a magic formula. Indexes into the list via `ord(operation)2/-20`, which buckets the four character codes across 1 to 4 by abusing `elt`'s rounding behavior.

-1 thanks to Arnauld, who improved on the modulo reduction.

-1 thanks to Bubbler, who found a better non-modulo formula.

## Score 73

```
select * from expressions
where elt(instr('*/-+',operation),a*b,a/b,a-b,a+b)=c

```

This is my best guess as to the 73 you mention other people have gotten in the question.

# Answer
> 6 votes
# MySQL, ~~82~~ 74 bytes

```
select * from expressions
where
elt(locate(operation,'+-/*'),a+b,a-b,a/b,a*b)=c

```

output

```
a           b           operation c
----------- ----------- --------- -----------
2           3           +         5
8           5           -         3

```

Explanation

ELT() returns the Nth element of the list of strings (the expressions are evaluated and converted to strings)

LOCATE Return the position of the first occurrence of substring

# Answer
> 0 votes
# Score 32

Solution using a database view

```
select a,b,operation
from e
where c=r

```

Unfortunately a `select *` is not possible as the view contains an extra column with the correct result.

Requires a view creation in the database

```
create or replace view e as
select
  a,b,operation,c,
  elt(field(operation,'+','-','/','*'),a+b,a-b,a/b,a*b) r
from  expressions

```

---
Tags: code-golf, tips
---


title: Centerless Polygons

text:
# Question
Title: Centerless Polygons
A centered polygonal number is a positive integer given by the number of vertices when a point is surrounded by (increasingly larger) polygons with the same number of sides, as shown below. For example, \\$p\_5(3) = 1 + 5 + 10 + 15 = 31\\$ is a centered pentagonal number formed by taking a vertex and adding three layers of pentagons:

---

This question, however, concerns center*less* polygonal numbers. In particular, we want to know how many ways we can write \\$n\\$ as the difference of two \\$k\\$-gonal numbers with \\$k \geq 3\\$—that is, a centered polygon with the center removed.

For example, \\$35\\$ can be written as the difference of two \\$k\\$-gonal numbers in five ways:

* \\$p\_5(4) - p\_5(2) = 51 - 16\\$,
* \\$p\_5(7) - p\_5(6) = 141 - 106\\$,
* \\$p\_7(3) - p\_7(1) = 43 - 8\\$,
* \\$p\_7(5) - p\_7(4) = 106 - 71\\$, and
* \\$p\_{35}(1) - p\_{35}(0) = 36 - 1\\$,

the first four of which are illustrated below:

##

# The Challenge

This challenge will have you write a script that takes a positive integer `n` and outputs the number of ways to write \\$n\\$ as a center*less* polygonal number.

Since this is a challenge, the shortest code wins.

The sequence begins:

```
0, 0, 1, 1, 1, 2, 1, 2, 3, 2, 1, 5, 1, 2, 5, 3, 1, 6, 1, 5, 5, 2, 1, 8, 3, 2, 6, 5, 1, 10, 1, 4, 5, 2, 5, 12, 1, 2, 5, 8, 1, 10, 1, 5, 12, 2, 1, 11, 3, 6, 5, 5, 1, 12, 5, 8, 5, 2, 1, 19, 1, 2, 12, 5, 5, 10, 1, 5, 5, 10, 1, 18, 1, 2, 12, 5, 5, 10, 1, 11, 10, 2

```

This is now in the OEIS as A339010.

# Answer
> 3 votes
# Jelly, 10 bytes

```
:3ḍƇ⁸ÆDFḂS

```

A monadic Link accepting \\$n\\$ which yields the count.

**Try it online!** Or see the test-suite.

### How?

```
:3ḍƇ⁸ÆDFḂS - Link: n
 3         - three
:          - (n) integer divide (3) -> x
   Ƈ       - filter keep those v in [1..x] for which:
  ḍ        -   (v) divides:
    ⁸      -     chain's left argument, n
     ÆD    - divisors (of each)
       F   - flatten
        Ḃ  - least significant bit (of each)
         S - sum

```

# Answer
> 14 votes
# Haskell, 42 bytes

```
f n=sum[0^mod n q|a<-[3..n],q<-[a,3*a..n]]

```

Try it online!

**51 bytes**

```
f n=sum[1|a<-[3..n],b<-[1,3..n],c<-[1..n],a*b*c==n]

```

Try it online!

The output is the number of ways to factor \\$n=abc\\$ into three positive factors, where \\$a \geq 3\\$, \\$b\\$ is odd, and \\$c\\$ is unconstrained.

# Answer
> 8 votes
# 05AB1E, ~~17~~ ~~16~~ 10 bytes

```
3÷ÝsÑÃÑÉOO

```

Try it online! Edit: Saved 5 bytes thanks to @ovs. Explanation:

```
3÷L         Get a list from `0` to `n//3`.
   sÑÃ      Keep only factors of `n`.
      ÑÉO   Number of odd divisors of each factor.
         O  Output the sum.

```

# Answer
> 5 votes
# , 29 bytes

```
[:+/@,[=[+/\\.@(*1+i.)~"+3+i.

```

Try it online!

```
[:+/@,[=[+/\\.@(*1+i.)~"+3+i.
                           i. 0…N-1
                         3+   3…N+2
                       "+     for each y in 3…N+2:
        [      (*1+i.)~       y * 0…N, thus f.e. 5 10 15 20 … for p_5
           \\.@               take every possible sublist
         +/                   and sum it
      [=                      which sums are equal to N?
[:+/@,                        count the true bits

```

# Answer
> 3 votes
# JavaScript (ES6), 49 bytes

Uses the method described by @xnor.

```
f=(n,d=k=1)=>k<=n&&!(n/~++k%d)+f(n,d>n||k--&&d+2)

```

Try it online!

### Commented

```
f = (            // f is a recursive function taking:
  n,             //   n = input
  d = k = 1      //   d = odd divisor, k = other divisor
) =>             //
  k <= n &&      // stop if k is greater than n
  !(             // otherwise:
    n / ~++k     //   - increment k
    % d          //   - increment the final result if d is a divisor of n / (k + 1)
  ) +            //
  f(             // add the result of a recursive call:
    n,           //   - pass n unchanged
    d > n ||     //   - if d is greater than n, leave k unchanged and reset d to 1
    k-- && d + 2 //     otherwise, decrement k and add 2 to d
  )              // end of recursive call

```

# Answer
> 3 votes
# Wolfram Language (Mathematica), 39 bytes

```
Sum[Boole[(2i j-i)∣#],{i,3,#},{j,#}]&

```

Try it online!

*special thanks to @att for saving 20 bytes*

# Answer
> 2 votes
# Charcoal, 24 bytes

```
ＮθＦθＦθＦθ⊞υ×⁺³ι×⊕⊗κ⊕λＩ№υθ

```

Try it online! Link is to verbose version of code. Port of @xnor's answer. Explanation:

```
Ｎθ

```

Input `n`.

```
ＦθＦθＦθ

```

Create loops `i`, `k` and `l` ranging from `0` to `n`.

```
⊞υ×⁺³ι×⊕⊗κ⊕λ

```

Calculate `a*b*c` where `a=i+3`, `b=2k+1` and `c=l+1`.

```
Ｉ№υθ

```

Count how many times this equals `n`.

# Answer
> 2 votes
# Python 3, ~~84~~ 65 bytes

Saved a whopping 19 bytes thanks to ovs!!!

```
lambda n,R=range:sum(n%q<1for a in R(3,n+1)for q in R(a,n+1,2*a))

```

Try it online!

Uses xnor's method from his Haskell answer.

# Answer
> 1 votes
# Retina 0.8.2, 49 bytes

```
.+
$*
M!&`(.+)$(?<=^\1{3,})
m&`(.(..)*)$(?<=^\1+)

```

Try it online! Link includes test suite that checks all numbers from `1` to the input. Explanation:

```
.+
$*

```

Convert to unary.

```
M!&`(.+)$(?<=^\1{3,})

```

List (`!`) all (`&`) factors not greater than `n/3`.

```
m&`(.(..)*)$(?<=^\1+)

```

Count the number of odd factors of all the factors. (The `M` is implicit as this is the last stage.)

# Answer
> 1 votes
# C (gcc), <sup>~~79~~ ~~63~~</sup> 62 bytes

Saved a whopping 16 bytes thanks to ovs!!!
Saved a byte thanks to the man himself Arnauld!!!

```
a;q;s;f(n){for(s=0,q=a=3;n/q||n/(q=++a);)s+=n%(q-=2*a)<1;n=s;}

```

Try it online!

Uses xnor's method from his Haskell answer.

# Answer
> 1 votes
# Ruby, 76 bytes

```
->n{(1..n/3).select{|k|n%k==0}.sum{|o|(1..o).select{|i|o%i==0}.sum{|j|j%2}}}

```

Try it online!

Based on Neil's answers.

# Answer
> 1 votes
# Java 8, 73 bytes

```
n->{int r=0,a=2,t;for(;a++<n;)for(t=a;t<=n;t+=2*a)if(n%t<1)r++;return r;}

```

Port of *@Noodle9*'s Python 3 answer, which uses the same method as *@xnor*'s Haskell answer.

Try it online.

**Explanation:**

```
n->{               // Method with integer as both parameter and return-type
  int r=0,         //  Result-sum, starting at 0
      a=2,         //  Temp-integer `a`, starting at 2
      t;           //  Temp-integer `t`, uninitialized
  for(;a++<n;)     //  Loop `a` in the range [1, n]:
    for(t=a;t<=n;  //   Inner loop `t` in the range [a, n],
        t+=2*a)    //   in increments of 2a
      if(n%t<1)    //    If the input is evenly divisible by `t`:
        r++;       //     Increase the result-sum by 1
  return r;}       //  And after the loops, return the result-sum

```

# Answer
> 1 votes
# APL (Dyalog Unicode), ~~40~~ 33 bytes (SBCS)

*Saved 7 bytes thanks to @Bubbler!*

Port of Neil's 05AB1E answer.

```
{+/∊(⊢(|⍨<2|⊢)1+⍳)¨⍵(⊢∩∨)⍳1+⌊⍵÷3}

```

Try it online!

```
{+/∊(⊢(|⍨<2|⊢)1+⍳)¨⍵(⊢∩∨)⍳1+⌊⍵÷3}
                          ⍳1+⌊⍵÷3 ⍝ Range to n//3 + 1
                    ⍵(⊢∩∨)       ⍝ Keep divisors of n
                   ¨              ⍝ For each divisor
   ∊(⊢(|⍨<2|⊢)1+⍳)               ⍝ A train to find odd divisors of the divisor, not sure how it works exactly
               1+⍳)               ⍝ Make a range from 2 to the divisor+1
    (⊢                           ⍝ On this side, just give back the divisor
      (|⍨<2|⊢)                   ⍝ Checks that the element of the range divides the divisor and that it's odd
      (|⍨                        ⍝ The possible divisor mod its divisor
         <                       ⍝ Is less than
          2|⊢)                   ⍝ 2 mod the divisor's possible divisor
   ∊                             ⍝ Turn into vector so a single sum is needed
 +/                               ⍝ Sum that

```

# Answer
> 1 votes
# MathGolf, 12 bytes

```
3/╒÷mÉî*──¥Σ

```

Try it online.

**Explanation:**

```
3/           # Integer-divide the (implicit) input-integer by 3
  ╒          # Pop and push a list in the range [0, input//3]
   ÷         # Check for each that they evenly divide the (implicit) input
             # (1 if truthy; 0 if falsey)
    m        # Then map each boolean to,
     É       # using the following three characters as inner code-block:
      î*     #  Multiply the boolean by the 1-based map-index
        ─    #  Pop and push a list of its divisors
         ─   # Flatten this list of list of integers
          ¥  # Modulo-2 on each
           Σ # And sum those together
             # (after which the entire stack joined together is output implicitly)

```

---
Tags: code-golf, sequence, geometry, combinatorics
---


title: Encode an image inside of the source

text:
# Question
Title: Encode an image inside of the source
**The golf challenge is to encode and compress the following image inside a source file.**

To do this you need to write 3 functions: `red`, `green`, and `blue` which accept x/y coordinates of the image and return the corresponding R/G/B pixel value between 0-255.

Here is the C/C++ test code:

```
#include <stdio.h>
#include "your_file"
int main() {
  int x, y;
  for(y = 0; y < 32; ++y)
  for(x = 0; x < 32; ++x)
    printf("%i %i %i\n", red(x, y), blue(x, y), green(x, y));
}

```

And the output: http://pastebin.com/A770ckxL (you can use this to generate your image data)

**Rules & details:**

* This is a golf
* Only your code/file is golfed - the test code is separate
* The character set used is ASCII, however control characters in strings may only be used if escaped (like '\n' and '\r', etc)
* Everything must be contained inside the source - no file loading
* Your output must match the example output. This means loseless compression.

**Languages:**

The problem was written with C/C++ in mind, but I'm removing those restrictions. With that said, I'll still recommend using them.

# Answer
## C, 796 754 712 703 692 685 682 670 666 662 656 648 chars

Changelog:

* 754-\>712: Added `return` to the `#define`, replacing `if` with `?` statements (thanks @FUZxxl), removing `int` from the functions parameter list.
* 712-\>703: Shameless copy from bunnit again :) Moved the whole image creation into the `#define`
* 703-\>692: Merged `p[]` and `h[]`, some more `?:` improvements
* 692-\>685: Incrementing `b` so `i` isn't needed anymore. `m=b` instead of `m=11` and `n<2e3` instead of `i<356` \- these are close to undefined behaviour/memory corruption, but it seems I'm lucky :)
* 685-\>682: `k` is now (32,16,8,4,2,1,0) instead of (5,4,3,2,1,0). Gotcha, D C ;)
* 682-\>670: Split `p[]` and `h[]`, converted `h[]` to a `char*` \- awwww, there's a sleepy kitty in it `^<+_=>-`
* 670-\>666: `while` =\> `for`, `l=l*2+...` =\> `l+=l+...`
* 666-\>662: `m=m>9?...` =\> `c[n++]=m>9?...`
* 662-\>656: Reversed bit order in `b[]`, so we can map to 64-127 instead of 0-63 and don't need bit index `k` anymore. Thanks @Piotr Tarsa. Replaced `?:` (GCC extension) with `||`. Thanks @JamesB
* 656-\>648: Shameless copy from Shelwien :) (multi-character constants for `p[]`)

Image is converted to a Base64-like string (ASCII 37-100), using huffman coding to encode colors 0-9 using 3-6 bits and a special color 10 (pixel is same as previous one) using only 1 bit.

```
#define P (x,y){for(;n<2e3;j/=2){j>1||(j=*b+++27);l+=l+(j&1);for(m=0;m<11;m++)l-h[m]+32||(c[n++]=m>9?c[n-1]:m,l=0,m=b);}return 255&p[c[x+y*32]]
char*h="$^<+_=>-,* ",*b="F0(%A=A=%SE&?AEVF1E01IN8X&WA=%S+E+A-(,+IZZM&=%]U5;SK;cM84%WE*cAZ7dJT3R.H1I2@;a^/2DIK&=&>^X/2U*0%'0E+;VC<-0c>&YU'%],;]70R=.[1U4EZ:Y=6[0WU4%SQARE0=-XDcXd_WW*UAF&cFZJJ0EV*(a(P05S3IXA>51cH:S5SAE6+W%/[]7SF(153UM]4U()(53DA+J:]&5+5KX,L6>*4I,/UMBcML9WKLa9%UYIHKWW(9-*):(-ZW(9%T'N&9;C,C/Ea/Y7(JJ\\6CD9E,2%J*,ac]NIW8(M=VFac)/^)?IS-;W&45^%*N7>V,,C-4N35FMQaF,EaWX&*EJ4'";p[]={0,'R@+','aXL',7783255,'4k`',16354410,'NNv',5295994,4671418,9975021},c[1024],j,l,m,n;red P;}blue P>>16;}green P>>8;}

```

Copied two things from bunnit's answer, the `#define` and the whole image being decoded completely every time `red`/`green`/`blue` are called. There's some room for additional improvement, so expect some updates :) I'm not sure about code compliance, used GCC 4.6.1 to compile and test.

Compression-wise, I think arithmetic coding would help as the distribution is pretty skewed, but maybe code overhead would be too heavy in this case. LZW also should do a very good job. Colors are quite local, so adaptive coding might be an idea.

More readable 754 character version with some comments:

```
#define P 255&p[c[x+y*32]]
// Base64 coded image bitstream, ASCII 37-100
// Huffman codes: 100, 111110, 11100, 1011, 111111, 11101, 11110, 1101, 1100, 1010, 0
char b[]="FYU%3+3+%B&E;3&HF1&Y1.JWXE83+%B=&=3)U]=.PP*E+%,('?B>?D*Wa%8&MD3P7dNbARIV1.Q[?4L9Qc.>E+EKLX9Q(MY%5Y&=?HC_)YDKE0(5%,]?,7YR+I@1(a&PO0+G@Y8(a%B23R&Y+)XcDXd<88M(3FEDFPNNY&HMU4UZY'BA.X3K'1DVOB'B3&G=8%9@,7BFU1'A(*,a(U-U'Ac3=NO,E'='>X]^GKMa.]9(*SD*^/8>^4/%(0.V>88U/)M-OU)P8U/%b5JE/?C]C9&4907UNN`GCc/&]Q%NM]4D,J.8WU*+HF4D-9L-;.B)?8Ea'L%MJ7KH]]C)aJA'F*24F]&48XEM&Na5";
// Colors, order GBR (one char shorter than all the others)
p[]={0,5390379,6379596,7783255,3435360,16354410,5131894,5295994,4671418,9975021};
// Huffman codes for colors 0-10
h[]={4,62,28,11,63,29,30,13,12,10,0};
// Array for image data
c[1024];
i,j,k,l,m,n;
red(int x,int y){
  while(i<356){
    k--;
    if (k<0) {
      j=b[i++]-37;
      k=5;
    }
    l*=2;
    if (j&(1<<k)) l++;
    for(m=0;m<11;m++){
      if(l==h[m]){
        if (m>9) m=c[n-1];
        c[n++]=m;
        l=0;
        m=12;
      }
    }
  }
  return P;
}
blue(int x,int y){return P>>16;}
green(int x,int y){return P>>8;}

```
> 6 votes

# Answer
## Python (~~684~~ 592 characters)

```
red,blue,green=[lambda x,y,i=i:[15570996,2839104,7010700,5732035,6304875,0,12207943,8016079,7753294,5005656][int('eJxtkgGSxSAIQ6+kaLTe/2JLImj7Z9MZ6/gMIgjAzMbVWisGySRNm2ut5Hhx/2M0JMfHH5PWwo9x4mNO8pb6JkFM3hpqrR4+qY6eVK1mjlsFeSOBjPyCMy3348aXVRtq9X8czovMIwA5FeXKtGOcvfcf/lbvyW0n2BTOh122HiIH0g/uNrx47zupzMxuuTv808pZd3K7deJ/+PiH61AztmaNwPAsOnNGYovWIxswRill6vnAL4HgxDF17jFcjwRk/5b3Q1x1flLI9n64CIci8bmQe7NL8XoKliu+Jk/AR9rnjkwAYaDka8OXu/a+5NvvNzkcmqifL47H04kAz9M+9slKkDMGuOHi5PR7GZwv7MeApkz5JOSPHFVW3QTbzDJtzDIczkuWjeupLbckLyU5/gByftMg'.decode('base64').decode('zip')[32*y+x])]>>i&255 for i in 16,8,0]

```

Since this challenge is now open to all, why not! It's the familiar zlib -\> base64 encoding route, so I apologize for that. Hopefully an entry with some semblance of ingenuity will be shorter!

Here's a test snippet analogous to the original:

```
for y in range(32):
    for x in range(32):
        print red(x,y), blue(x,y), green(x,y)

```
> 4 votes

# Answer
**C++, 631 chars; C - 613**

A base-92 unary mtf coder, C++, 631 chars:

```
#define A(Z)int Z(int X,int Y){char*s="xdGe*V+KHSBBGM`'WcN^NAw[,;ZQ@bbZVjCyMww=71xK1)zn>]8b#3&PX>cyqy@6iL?68nF]k?bv/,Q`{i)n[2Df1zR}w0yIez+%^M)Diye{TC]dEY\\0,dU]s'0Z?+bo;7;$c~W;tvFl%2ruqWk$Rj0N[uP)fSjk?Tnpn_:7?`VbJ%r@7*MQDFCDo3)l#ln<kuRzzHTwCg&gYgSXtv\\m_Eb}zRK7JK<AZzOe}UX{Crk)SyBn;;gdDv=.j*O{^/q6)`lHm*YYrdM/O8dg{sKW#B3BLMiI8@-Zo-EsgE.R#viYL$-<EU*~u5pe$r:`b)^dgXOJtf4";int*v,B=92,R=1,C=0,w[]={0,16354410,4671418,'aXL',7783255,5295994,'R@+','4k`',9975021,'NNv'};for(X+=Y*32+1;X--;)for(v=w;;){for(Y=*v++;R<B*B*B;C=C%R*B+*s++-35)R*=B;if(R/=2,C>=R){for(C-=R;--v>w;*v=v[-1]);*v=Y;break;}}return 255&Y
A(red);}A(blue)>>16;}A(green)>>8;}

```

And the C version of above (613 chars):

```
#define A (X,Y){char*s="xdGe*V+KHSBBGM`'WcN^NAw[,;ZQ@bbZVjCyMww=71xK1)zn>]8b#3&PX>cyqy@6iL?68nF]k?bv/,Q`{i)n[2Df1zR}w0yIez+%^M)Diye{TC]dEY\\0,dU]s'0Z?+bo;7;$c~W;tvFl%2ruqWk$Rj0N[uP)fSjk?Tnpn_:7?`VbJ%r@7*MQDFCDo3)l#ln<kuRzzHTwCg&gYgSXtv\\m_Eb}zRK7JK<AZzOe}UX{Crk)SyBn;;gdDv=.j*O{^/q6)`lHm*YYrdM/O8dg{sKW#B3BLMiI8@-Zo-EsgE.R#viYL$-<EU*~u5pe$r:`b)^dgXOJtf4";int*v,B=92,R=1,C=0,w[]={0,16354410,4671418,'aXL',7783255,5295994,'R@+','4k`',9975021,'NNv'};for(X+=Y*32+1;X--;)for(v=w;;){for(Y=*v++;R<B*B*B;C=C%R*B+*s++-35)R*=B;if(R/=2,C>=R){for(C-=R;--v>w;*v=v[-1]);*v=Y;break;}}return 255&Y
red A;}blue A>>16;}green A>>8;}

```

Just to include an entry with base-95 data and arithmetic coding + adaptive statistical model.
schnaader's code uses ~438 chars for data, and mine only 318 (311 w/o masking).
But as expected, arithmetic coding is too complicated for a small sample like this.

(This is 844 chars)

```
char* q="q^<A\">7T~pUN1 adz824K$5a>C@kC8<;3DlnF!z8@nD|9D(OpBdE#C7{yDaz9s;{gF[Dxad'[oyg\\,j69MGuFcka?LClkYFh=:q\\\\W(*zhf:x)`O7ZWKLPJsP&wd?cEu9hj 6(lg0wt\\g[Wn:5l]}_NUmgs]-&Hs'IT[ Z2+oS^=lwO(FEYWgtx),)>kjJSIP#Y?&.tx-3xxuqgrI2/m~fw \\?~SV={EL2FVrDD=1/^<r*2{{mIukR:]Fy=Bl.'pLz?*2a? #=b>n]F~99Rt?6&*;%d7Uh3SpLjI)_abGG$t~m{N=ino@N:";
#define I int
#define F(N) for(i=0;i<N;i++)
#define Z C=(C%T)*B+(*q++)-32
enum{B=95,H=1024,T=B*B*B};I p[B],v[B+H],n=3,*m=&v[B],R=T*B,C,i,j,y,c,x,w;void D(I P){w=(R>>11)*P;(y=C>=w)?R-=w,C-=w:R=w;while(R<T)R*=B,Z;}struct u{u(){F(4)Z;F(B)p[i]=H,v[i]=0;F(H){v[0]=m[i-1];v[1]=m[i-32];j=i;F(n){I&P=p[i];D(P);if(y){P-=P>>4;c=v[i];goto t;}else P+=H+H-P>>4;}c<<=7;for(x=-255;x<0;x+=x+y)D(H);v[n++]=c=x;t:m[i=j]=c;}}}d;I red(I x,I y,I z=0){return m[y*32+x]>>z&255;}
#define blue(x,y) red(x,y,8)
#define green(x,y) red(x,y,16)

```

Tests (from earlier base-96 version):
http://codepad.org/qrwuV3Oy
http://ideone.com/ATngC

Somehow SO eats 7F codes, so I had to update it to base=95
> 4 votes

# Answer
## C++ - 1525 1004 964 chars

```
#define e (int x,int y){for(i=g=0;i<702;i=i+2)for(j=48;j<d[i];++j)c[g++]=d[i+1]-48;return 255&z[c[x+y*32]]
int i,g,j,z[]={0,7010700,12207943,5005656,5732035,8016079,2839104,6304875,15570996,7753294},c[1024];
char*d="3031;23322337261524453223310625132101214103453101233722172643310323342102521229492333210352112241036141014821042552621241014161016141024121022103210151015104526211034361034726510352625107441:530855425201511551045378554>55755312410242035201510528725212044451015411032:73135216561321012171017101725313581125152572531358122415257257110213310131231422022172025105110315322103210623815203110113053521053223817506920721013361322282530991062101213361322282520491049682224133614121028101510291029;812341023342835694810582018841018356978194810842835193329781019482410542835192310193668399428454319362928102829843845331019263028101330441014382035104369285338101810284536334910291018534820283546891019102943883536";
int red e>>16;}
int blue e>>8;}
int green e;}

```

Created an array z which stores all of the possible colours as a single integer.(r\<\<16 | g\<\<8 | b). Created an array d which stores {amount, value}, the value is the position in the array z, the amount is the number of consecutive pixels with that value.(i.e 3,0, means colout t\[0\] appears the next 3 pixels. The actual array of pixels(c) is then calculated every time red is called. The value in the array is then right shifted and ANDed as necessary to get the correct component.

I could probably save a few more characters(~50) by taking more patterns out of the array as defines.

**Edit 1** \- changed the d array for a char array with each value offset by 48, which means I can represent it as a string saving a load of commas.

**Edit 2** \- Took a larger portion of the functions out in the define statement.
> 3 votes

# Answer
# Javascript, ~~696~~ 694 chars

Thanks to schnaader for 696 -\> 694.

I figured a different encoding format, which essentially is Run-length encoding with a color lookup table. It works quite nice, because there are less than 16 colors and they apear less that 16 times in a row; so every pixel definition including length fits into one byte. I put the color in the high part of the byte and the count in the low part.

In the end, the base64 string turned out to be longer than I had expected (472 chars), but the decoding program is really short.

```
for(b=i=a=[];a&15||(a=atob("AxMrMyIzJxYlRDUiMwEmFSMBIUEBQzUBITMnEidGMwEjMyQBUhIi
SSkzIwFTEiFCAWNBAUEoASRVYhJCAUFhAWFBAUIhASIBIwFRAVEBVGISAUNjAUMnVgFTYlIBRxRaA1hF
UgJREVUBVHNYRV51VRNCAUICUwJRASV4UhICRFQBURQBI3oTUxJWFiMBIXEBcQFxUhNTGCEVJXVSE1MY
IhQldVIXARIzATEhEyQCInECUgEVARM1IgEjASaDUQITAREDNSUBNSKDcQWWAicBMWMxIoJSA5kBJgEh
MWMxIoJSApQBlIYiQjFjQSEBggFRAZIBkoshQwEyQ4JTloQBhQKBSAGBU5aHkYQBSIJTkTOShwGRhEIB
RYJTkTIBkWOGk0mCVDSRY5KCAYKSSINUMwGRYgOCATEDRAFBgwJTATSWgjWDAYEBglRjM5QBkgGBNYQC
glNkmAGRAZI0iFNjAQ==").charCodeAt(i++));b.push([0,16354410,4671418,6379596,77832
55,5295994,5390379,3435360,9975021,5131894][a-- >>4]));green=(red=function(c,d){
return b[32*d+c]>>this&255}).bind(16);blue=red.bind(8)

```

Note: I split up the code to have a little readability. It needs to be on one line to run.

Test code:

```
for(var y = 0; y < 32; ++y) {
    for(var x = 0; x < 32; ++x) {
        console.log(red(x, y), green(x, y), blue(x, y));
    }
}

```

I think the example result is actually the output of red, green, blue (not red, blue, green like in the original test code); it works for me like that anyway.
> 3 votes

# Answer
## C++, 1357 chars

```
int i,j,C[]={0,0,0,106,249,140,186,71,71,76,97,88,87,118,195,122,80,207,43,82,64,96,52,107,237,152,52,118,78,78},E[]={30,31,112,33,22,33,72,61,52,44,53,22,33,10,62,51,32,10,12,14,10,34,53,10,12,33,72,21,72,64,33,10,32,33,42,10,25,21,22,94,92,33,32,10,35,21,12,24,10,36,14,10,14,82,10,42,55,26,21,24,10,14,16,10,16,14,10,24,12,10,22,10,32,10,15,10,15,10,45,26,21,10,34,36,10,34,72,65,10,35,26,25,10,74,41,105,30,85,54,25,20,15,11,55,10,45,37,85,54,145,57,55,31,24,10,24,20,35,20,15,10,52,87,25,21,20,44,45,10,15,41,10,32,107,31,35,21,65,61,32,10,12,17,10,17,10,17,25,31,35,81,12,51,52,57,25,31,35,81,22,41,52,57,25,71,10,21,33,10,13,12,31,42,20,22,17,20,25,10,51,10,31,53,22,10,32,10,62,38,15,20,31,10,11,30,53,52,10,53,22,38,17,50,69,20,72,10,13,36,13,22,28,25,30,99,10,62,10,12,13,36,13,22,28,25,20,49,10,49,68,22,24,13,36,14,12,10,28,10,15,10,29,10,29,118,12,34,10,23,34,28,35,69,48,10,58,20,18,84,10,18,35,69,78,19,48,10,84,28,35,19,33,29,78,10,19,48,24,10,54,28,35,19,23,10,19,36,68,39,94,28,45,43,19,36,29,28,10,28,29,84,38,45,33,10,19,26,30,28,10,13,30,44,10,14,38,20,35,10,43,69,28,53,38,10,18,10,28,45,36,33,49,10,29,10,18,53,48,20,28,35,46,89,10,19,10,29,43,88,35,36,10};int*Q(int n){for(i=0;1;i++){for(j=0;j<E[i]/10;j++){if(!n)return&C[E[i]%10*3];n--;}}}
#define red(x,y) Q(x+32*y)[0]
#define blue(x,y) Q(x+32*y)[1]
#define green(x,y) Q(x+32*y)[2]

```

Deobfuscated a bit:

```
int C[]={0,0,0,106,249,140,186,71,71,76,97,88,87,118,195,122,80,207,43,82,64,96,52,107,237,152,52,118,78,78},
int E[]={30,31,112,33,22,33,72,61,52,44,53,22,33,10,62,51,32,10,12,14,10,34,53,10,12,33,72,21,72,64,33,10,32,33,42,10,25,21,22,94,92,33,32,10,35,21,12,24,10,36,14,10,14,82,10,42,55,26,21,24,10,14,16,10,16,14,10,24,12,10,22,10,32,10,15,10,15,10,45,26,21,10,34,36,10,34,72,65,10,35,26,25,10,74,41,105,30,85,54,25,20,15,11,55,10,45,37,85,54,145,57,55,31,24,10,24,20,35,20,15,10,52,87,25,21,20,44,45,10,15,41,10,32,107,31,35,21,65,61,32,10,12,17,10,17,10,17,25,31,35,81,12,51,52,57,25,31,35,81,22,41,52,57,25,71,10,21,33,10,13,12,31,42,20,22,17,20,25,10,51,10,31,53,22,10,32,10,62,38,15,20,31,10,11,30,53,52,10,53,22,38,17,50,69,20,72,10,13,36,13,22,28,25,30,99,10,62,10,12,13,36,13,22,28,25,20,49,10,49,68,22,24,13,36,14,12,10,28,10,15,10,29,10,29,118,12,34,10,23,34,28,35,69,48,10,58,20,18,84,10,18,35,69,78,19,48,10,84,28,35,19,33,29,78,10,19,48,24,10,54,28,35,19,23,10,19,36,68,39,94,28,45,43,19,36,29,28,10,28,29,84,38,45,33,10,19,26,30,28,10,13,30,44,10,14,38,20,35,10,43,69,28,53,38,10,18,10,28,45,36,33,49,10,29,10,18,53,48,20,28,35,46,89,10,19,10,29,43,88,35,36,10};
int*Q(int n){
  for(int i=0;1;i++){
    for(int j=0;j<E[i]/10;j++){
      if(!n)return&C[E[i]%10*3];
      n--;
    }
  }
}
#define red(x,y) Q(x+32*y)[0]
#define blue(x,y) Q(x+32*y)[1]
#define green(x,y) Q(x+32*y)[2]

```

`C` contains the RGB values for the ten distinct colors of the image. `E` contains the data for the picture, where each element `E[i]` encodes both a repeat count `E[i]/10` and a color index `E[i]%10`.
> 2 votes

# Answer
# C (gcc), ~~602~~ 584 bytes

-18 bytes thanks to ceilingcat.

```
X[1024],*i,r,w,*I;
#define u(d)(x,y){i=X;for(I=L"56s-8-8_TKCL-8!UJ7!#%!9L!#8_,_W8!78A!0,-us87!:,#/!;%!%i!AN1,/!%'!'%!/#!-!7!&!&!D1,!9;!9_X!:10!a@v&5lM0+&\"N!D<lMvNPN6/!/+:+&!Kn0,+CD!&@!7x(6:,XT7!#(!(!(06:h#JKP06:h-@KP0^!,8!$#6A+-(+0!J!6L-!7!U=&+6!\"5LK!L-=(I\\+_!$;$-305z!U!#$;$-30+H!H[-/$;%#!3!&!4!4y3#9!.93:\\G!Q+)k!):\\e*G!k3:*84e!*G/!M3:*.!*;[>u3DB*;43!34k=D8!*153!$5C!%=+:!B\\3L=!)!3D;8H!4!)LG+3:Ep!*!4Bo:;!";w=*I-33,*I++;)for(r=w/10+1;r--;*i++=L"\0\x6a8cf9\xba4747\x4c5861\x57c376\x7acf50\x2b4052\x606b34\xed3498\x764e4e"[w%10]>>d&255);x=X[y*32+x];}
red u(16)green u(8)blue u(0)

```

Try it online!
> 2 votes

# Answer
# Python 3 (589 characters)

```
import base64,zlib
red,blue,green=(lambda x,y,i=i:b'\xed\x984+R@j\xf9\x8cWv\xc3`4k\0\0\0\xbaGGzP\xcfvNNLaX'[zlib.decompress(base64.decodebytes(b'eJxtkgGSxSAIQxWN1vtfeEkEbf9sOmMdn0EEAZjZuFprxSCZpGlzrZUcL+5/jIbk+Phj0lr4MU58zEneUt8kiMlbQ63VwyfV0ZOq1cxxqyBvJJCRX3Cm5X7c+LJqQ63+j8N5kXkEIKeiXJl2jLP3/sPf6j257QSbwvmwy9ZD5ED6wd2GF+99J5WZ2S13h39aOetObrdO/A8f/3AdasbWrBEYnkVnzkhs0XpkA8YopUw9H/glEJw4ps49huuRgOzf8n6Iq85PCtneDxfhUCQ+F3JvdileT8FyxdfkCfhI+9yRCSAMlHxt+HLX3pd8+/0mh0MT9fPF8Xg6EeB52sc+WQlyxgA3XJycfi+D84X9GNCUKZ+E/JGjyqqbYJtZpo1ZhsN5ybJxPbXlluSlJMcf++8TIA=='))[32*y+x]*3+i]for i in(0,1,2))

```

Test code

```
for y in range(32):
    for x in range(32):
        print(red(x,y), blue(x,y), green(x,y))

```

Based on solution from Dillon Cower
> 1 votes

# Answer
# PHP (5.4) - 822

I've done this **deliberately not using** any of the **built-in compression functions**. This solution is not finished, I'm not sure if I've given up, I can see areas for improvement but I can't find the time/willpower to refactor the whole thing at the moment, so I'm posting what I have so far.

Newlines + comments to be removed for 822 bytes.

```
// Colour map
$c=[0,16354410,4671418,6379596,7783255,5295994,5390379,3435360,9975021,5131894];

// Optimised RLE map
$r=array_merge(array_diff(range(10,89),[27,40,47,56,59,60,63,66,67,70,73,75,76,77,79,80,83,86]),[92,94,99,105,107,112,118,145]);

// Image data (base 70)
$e="CDsF<Fd]WPX<F0^VE0240GX02Fd;d_F0EFN0?;<onFE0H;2>0I404h0NZ@;>0460640>20<0E05050Q@;0GI0Gd`0H@?0eMqCjY?:51Z0QJjYu[ZD>0>:H:50Wk?;:PQ05M0ErDH;`]E0270707?DHg2VW[?DHg<MW[?c0;F032DN:<7:?0V0DX<0E0^K5:D01CXW0X<K7Ub:d03I3<A?Cp0^023I3<A?:T0Ta<>3I420A050B0Bt2G0=GAHbS0\:8i08Hbf9S0iAH9FBf09S>0YAH9=09IaLoAQO9IBA0ABiKQF09@CA03CP04K:H0ObAXK080AQIFT0B08XS:AHRm090BOlHI0";

// Expand image data
for($i=0;$i<352;$i++){$b=$r[ord($e[$i])-48];$l=(int)($b/10);while($l--)$d[]=$c[$b%10];}

// Colour retrieval functions
function red($x,$y){global$d;return$d[$x+$y*32]&0xff;}
function green($x,$y){global$d;return$d[$x+$y*32]>>8;}
function blue($x,$y){global$d;return($d[$x+$y*32]>>8)&0xff;}

```

Test stub:

```
for ($y=0;$y<32;$y++) {
    for ($x=0;$x<32;$x++) {
        printf("%d %d %d\n", red($x, $y), blue($x, $y), green($x, $y));
    }
}

```

The compression of the image data itself is pretty good, but the functions to retrieve RGB values take up 1/4 of the code.

I'm using a custom base70 + run length encoding mechanism.

1. There are 10 unique colours
2. Colours have run lengths between 1 and 14 (12 used).
3. There are 120 possible combinations.
4. There are only 70 *unique* run/colour combinations actually used.

The encoded image data references the array index of an RLE, which in turn indexes the array of colours. I'm not sure how much overhead this adds or subtracts over directly referencing the colours.

Sine there are 10 colours (0 to 9), RLEs are stored as `run_length * 10 + colour_index`. Giving a range of encodings between 10 and 145 without experimenting with optimisations based on colour ordering. (i.e. I could make the range 19 to 140 by moving colours 0 to 5, 5 to 9, and 9 to 0 - but this may have other knock-on effects)

A previous answer states their encoded data is 472 bytes. My encoded image data is 352 bytes, but the intermediate RLE / colour map (which is not binary encoded) is a further 129 bytes, putting the total at 481. (as well as additional overhead for joining up the two). However I suspect my method might scale better for larger images.

**TODO:**

1. Investigate binary encoding of RLE map
2. Find a way of reducing the size of the functions. `global` is a bitch, but can't access character indexes on constants.
3. Experiment with colour index ordering to see if RLE map size can be reduced with longer sequential runs of numbers
4. Potential 64bit specific optimisations of colour map? (r0 \<\< 56 | r1 \<\< 48 | ...)?
5. Experiment with vertical RLE to see if it results in a more compact set of encodings.
6. Area encoding?
> 1 votes

# Answer
# Julia, 636 bytes

Zlib compression is not part of standard libraries, so I only used Base64 encoding

```
using Base64
red,blue,green=[(x,y,d=base64decode)->d("AAAAavmMukdHTGFYV3bDelDPK1JAYDRr7Zg0dk5O")[3vcat([fill(div(i,16),i%16) for i=d("AxMrMyIzJxYlRDUiMwEmFSMBIUEBQzUBITMnEidGMwEjMyQBUhIiSSkzIwFTEiFCAWNBAUEoASRVYhJCAUFhAWFBAUIhASIBIwFRAVEBVGISAUNjAUMnVgFTYlIBRxRaA1hFUgJREVUBVHNYRV51VRNCAUICUwJRASV4UhICRFQBURQBI3oTUxJWFiMBIXEBcQFxUhNTGCEVJXVSE1MYIhQldVIXARIzATEhEyQCInECUgEVARM1IgEjASaDUQITAREDNSUBNSKDcQWWAicBMWMxIoJSA5kBJgEhMWMxIoJSApQBlIYiQjFjQSEBggFRAZIBkoshQwEyQ4JTloQBhQKBSAGBU5aHkYQBSIJTkTOShwGRhEIBRYJTkTIBkWOGk0mCVDSRY5KCAYKSSINUMwGRYgOCATEDRAFBgwJTATSWgjWDAYEBglRjM5QBkgGBNYQCglNkmAGRAZI0iFNjAQ==")]...)[32y+x+1]+c] for c=1:3]

```

Try it online!

Un-golfed version:

`colors` contains the 10 unique colors

`color_enc` contains the color number (0-9) in base16 + the amount it should be repeated (1-14) in base 16

`color_dec` rebuilds the whole image with color numbers (0-9)

```
using Base64

colors = "AAAAavmMukdHTGFYV3bDelDPK1JAYDRr7Zg0dk5O"
color_enc = "AxMrMyIzJxYlRDUiMwEmFSMBIUEBQzUBITMnEidGMwEjMyQBUhIiSSkzIwFTEiFCAWNBAUEoASRVYhJCAUFhAWFBAUIhASIBIwFRAVEBVGISAUNjAUMnVgFTYlIBRxRaA1hFUgJREVUBVHNYRV51VRNCAUICUwJRASV4UhICRFQBURQBI3oTUxJWFiMBIXEBcQFxUhNTGCEVJXVSE1MYIhQldVIXARIzATEhEyQCInECUgEVARM1IgEjASaDUQITAREDNSUBNSKDcQWWAicBMWMxIoJSA5kBJgEhMWMxIoJSApQBlIYiQjFjQSEBggFRAZIBkoshQwEyQ4JTloQBhQKBSAGBU5aHkYQBSIJTkTOShwGRhEIBRYJTkTIBkWOGk0mCVDSRY5KCAYKSSINUMwGRYgOCATEDRAFBgwJTATSWgjWDAYEBglRjM5QBkgGBNYQCglNkmAGRAZI0iFNjAQ=="

color_dec = vcat([fill(i÷16, i%16) for i in base64decode(color_enc)]...)

red,blue,green=[(x,y)->base64decode(colors)[3*color_dec[32y+x+1]+c] for c in 1:3]

```

Try it online!

Test code:

```
for y in 0:31
    for x in 0:31
        println(red(x,y), " ", blue(x,y), " ", green(x,y))
    end
end

```
> 0 votes

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


title: Unfolding an integer

text:
# Question
Title: Unfolding an integer
Given the functions

```
L: (x, y) => (2x - y, y)
R: (x, y) => (x, 2y - x)

```

and a number `N` generate a minimal sequence of function applications which take the initial pair `(0, 1)` to a pair which contains `N` (i.e. either `(x, N)` or `(N, y)`).

Example: `N = 21`. The minimal sequence is of length 5, and one such sequence is

```
          (  0,  1)
1. L ---> ( -1,  1)
2. L ---> ( -3,  1)
3. R ---> ( -3,  5)
4. L ---> (-11,  5)
5. R ---> (-11, 21)

```

Write the shortest function or program you can which generates a minimal sequence in `O(lg N)` time and `O(1)` space. You may output / return a string in either application order (`LLRLR`) or composition order (`RLRLL`), but document which.

# Answer
### Ruby, 55 or 39 characters

```
f=->n{(n>0?n-1:-n).to_s(2).tr'01',n>1?'LR':n<0?'RL':''}

```

The function returns the function sequence in composition order.

Usage:

```
puts f[21]     # RLRLL
puts f[-6]     # LLR

```

*Edit:* If we allow recursion (which violates the O(1) memory constraint but such does any function since the return value itself is O(lg n)) we can shrink the code to 39 characters.

```
f=->n{n<n*n ?f[(n-1)/2+1]+'RL'[n%2]:''}

```
> 2 votes

# Answer
## Perl, 82 81 Characters (complete program)

```
$n=<>;@_=(R,L);if($n<0){$n=1-$n;$a--}while($n>1){print$_[$n%2+$a];$n+=$n%2;$n/=2}

```

It takes one number as input, and it outputs the sequence in application order.

Edit: Instead of redefining the array in the if statement, set a number to negative one and add it to the index when the array is referenced. It achieves the same effect.
> 2 votes

# Answer
# Jelly, 15 bytes

```
“”HĊß;ị⁾LR$ƲḂƑ?

```

Try it online!

This uses the same allowance in Howard's answer, in that we can use recursion, despite it violating the \\$O(1)\\$ memory requirement. If this isn't allowed, then the following 20 byte solution works instead:

```
ḶȯAṀ©Bị⁾LRUAƑ}¡$®aḟ0

```

Try it online!

Both output the composition order

## How they work

```
“”HĊß;ị⁾LR$ƲḂƑ? - Main link f(N). Takes N on the left
              ? - If statement:
             Ƒ  -   If: Invariant under:
            Ḃ   -     Bit; Yields 1 for 0/1, else 0
“”              -   Then: Return the empty string
           Ʋ    -   Else:
  H             -     N÷2
   Ċ            -     Ceiling
    ß           -     f(⌈N÷2⌉)
          $     -     Group the previous 2 links together as a monad g(N):
       ⁾LR      -       "LR"
      ị         -       Modular index N into "LR"
     ;          -     Append to f(⌈N÷2⌉)

```

The 20 byte version (+6 bytes to handle \\$N = 0, 1\\$):

```
ḶȯAṀ©Bị⁾LRUAƑ}¡$®aḟ0 - Main link. Takes N on the left
Ḷ                    - [0, 1, ..., N-1] for N > 0 else []
  A                  - abs(N)
 ȯ                   - Replace [] with abs(N)
   Ṁ                 - Max; N-1 if N > 0 else abs(N)
    ©                - Save this to the register R
     B               - Convert R to binary
               $     - Group the previous 2 links into a monad f(N):
       ⁾LR           -   "LR"
             }       -   To N:
            Ƒ        -     Invariant under:
           A         -       Absolute value; 1 if N ≥ 0 else 0
              ¡      -   Do the following that many times:
          U          -     Reverse "LR"
                         This yields "RL" if N ≥ 0 else "LR"
      ị              - For each bit in R, index into "RL" or "LR",
                       yielding a list of Rs and Ls, S
                ®    - Yield R
                 a   - Replace all but R = 0 with S
                  ḟ0 - Change R = 0 to []

```
> 0 votes

---
Tags: code-golf, sequence, restricted-complexity
---


title: Generate the Stöhr sequence

text:
# Question
Title: Generate the Stöhr sequence
I am learning Ruby and wrote my first nontrivial code to solve this problem.

The challenge is to generate the first *n* elements of the Stöhr sequence, *S*, which is defined as follows:

> S\[0\] = 1
>
> S\[n\] is the smallest number that cannot be expressed as the sum of two distinct previous elements in the sequence.

Thus the sequence begins with 1, 2, 4, 7, and 10. The next element is 13, because 11 (=1+10) and 12 (=2+10) are sums of previous elements, but 13 is not.

I am looking for the shortest code. My own, in Ruby, is 108 characters long, but maybe I'll wait to see what others come up with before posting it?

# Answer
# APL, 7

In APL you can choose if you want to work with index 0 or index 1. You do this by setting global variable ⎕IO←0

If we choose to work in index 0 we have:

```
+\3⌊1⌈⍳

```

Explanation:

```
⍳    creates a sequence 0...n   (0 1 2 3 4 5)
1⌈   takes whichever is bigger, number in sequence or 1 (1 1 2 3 4 5)
3⌊   takes whichever is lower, number in sequence or 3 (1 1 2 3 3 3)
+\   partial sums for the sequence (1 2 4 7 10 13)

```

Try it on tryapl.org
> 15 votes

# Answer
# Haskell - ~~11~~ 21

Lazy infinite sequence

```
1:2:[4,7..]

```

Function that returns just supplied number of members (sigh)

```
flip take$1:2:[4,7..]

```
> 9 votes

# Answer
# Python 2, ~~37~~ 35 bytes

```
lambda n:[1,2][:n]+range(4,n*3-4,3)

```

Making use of a pattern...
> 7 votes

# Answer
# CJam, 14 bytes

```
1l~{_p_3e<+}*;

```

Test it here.

Starts at 1. Then, *S\[n\] = S\[n-1\] + min(S\[n-1\], 3)*.

```
1l~{_p_3e<+}*;
1              "Push 1.";
 l~            "Read and evaluate input N.";
   {       }*  "Repeat this block N times.":
    _p         "Duplicate the last number and print it.";
      _3e<     "Duplicate it again, and take minimum with 3.";
          +    "Add to last number.";
             ; "Discard final number to prevent output.";

```

This generalises easily to *h*-Stöhr sequences if we replace *3* by *2h-1*.
> 6 votes

# Answer
Brainfuck, 13 chars

```
+.+.++.[+++.]

```

Or 30 chars if we want to limit it to n outputs:

```
,->+.<[->+.<[->++.<[->+++.<]]]

```
> 6 votes

# Answer
# Python, 136 bytes

```
def f(n):
 if n<1:return[1]
 x=f(n-1);y=set(x)|{a+b for a in x for b in x if a!=b};return x+[min([a for a in range(1,max(y)+2)if{a}-y])]

```

Straight from the definition. I'm not sure how much I can golf this — it's certainly a lot longer than I expected.
> 4 votes

# Answer
# J, 14 chars

This just hardcodes the `[1,2, 4+3*k (k=0..n-1) ]` sequence and takes the first `N`.

```
   ({.1,2,4+3*i.) 10
1 2 4 7 10 13 16 19 22 25

```

.

# J, 18 chars

This one uses a linear combination of `[0,1,2,3...]`, `[1,1,0,0...]` and `[0,1,1,1...]`. Should be shorter but can't seem to golf it.

```
   ((3&*+<&2-2**)@i.) 10
1 2 4 7 10 13 16 19 22 25

```
> 3 votes

# Answer
# Prelude, ~~32~~ 20

**Edit:** ...with twice the voices now!

```
?(1-)
4 +3
2  ^
1 !^

```

This assumes the Python interpreter with `NUMERIC_OUTPUT = True`. Like the Brainfuck submission this answer assumes that input is given in the form of a code point. This is partly to get more attention for this meta discussion (and partly, because I love Prelude). So if you want to print the first 32 numbers, say, you need to put a space on STDIN. Of course, this means there's an upper limit to the valid inputs, but this answer isn't winning anyway, so I think within the limitations of Prelude this is fine.

## Explanation

In Prelude, all lines are executed in parallel, which line having its own stack, initialised to an infinite amount of zeroes. There is only a single instruction pointer (pointing at columns), so if you enter a loop on one voice, all other voices will loop along with it.

In the following I've transpose the code, so that I can annotate lines instead of columns:

```
?421  Read a character into the first stack. Push 4, 2, 1 onto the other stacks, respectively.
      Generally, the fourth stack will hold the next number to be printed, the third stack the
      one after that, and the second stack the number two steps ahead.
(     Start a loop if the input wasn't 0.
1+ !  Push a 1 onto the first stack. Add the top elements in the second stack. On the first
      iteration this will be 0 and 4, so it does nothing. On all further iterations
      this will increment the last number by 3.
-3^^  Subtract one from the first stack. Push a 3 onto the second stack for the next iteration.
      Copy the last value from the second to the third, and the third to the fourth stack.
)     If the top of the first stack is not 0, jump back to the column after the (.

```
> 3 votes

# Answer
# JavaScript (ES6) 92

As a recursive function based upon the problem definition

```
S=(n,v=1,s=[],r=0)=>[for(a of s)for(b of s)r+=(a-b&&a+b==v)]|r||(s.push(v),--n)?S(n,v+1,s):s

```

Using the pattern 1,2, 1+3\*k : 58

```
S=(n)=>(i=>{for(t=1;n>r.push(t+=i);i+=(i<3));})(0,r=[])||r

```

Side note: finding the h-Stöhr sequence (verifying the sum of up to `h` numbers instead of just 2). The `R` function tries all possibile sums of up a given number of list elements.

```
S=(n,h=2,s=[],v=1,R=(t,v,l,i=0,r=t,w)=>{
  for(;r&&l&&v[i];i++)
    w=[...v],r=!R(t-w.splice(i,1),w,l-1)
  return!r;
})=>R(v,s,h)||(s.push(v),--n)?S(n,h,s,v+1):s

```

**Ungolfed** roughly equivalent (and ES5 compatible)

```
function S(n, v, s)
{
  var r=0,a,b
  v = v||1
  s = s||[]
  for(a of s)
    for(b of s)
    {
      if (a != b && a+b == v)
        r++;
    }
  if (r == 0)
  {
    s.push(v);
    --n;
  }
  if (n != 0)
     return S(n,v+1,s)
  else
     return s
}

```

**Test** In FireFox/FireBug console. Simple function:

```
S(20)

```

> \[1, 2, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 49, 52, 55\]

Advanced function:

```
S(10,5)

```

> \[1, 2, 4, 8, 16, 32, 63, 94, 125, 156\]
> 2 votes

# Answer
# \>\<\> (fish), 72 65 49 46 chars

```
1n1-:?!;' 'o2n1-v
v1&no' ':<4&;!?:<
>-:?!;&3+^

```

Input is supplied to interpreter:

```
>fish.py stohr.fish -v 10
1 2 4 7 10 13 16 19 22 25

```

My first \>\<\> program, suggestions appreciated.
> 2 votes

# Answer
# Perl6 22 / 30

I'm going to see if Perl6 can deduce the sequence for me.

To do that I used the REPL built into Perl6

```
$ perl6
> 1,2,4,7...*
Unable to deduce arithmetic or geometric sequence from 2,4,7 (or did you really mean '..'?)
> 1,2,4,7,10...*
1 2 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58 61 64 67 70 ...

```

Hmm, I see the pattern that Perl deduced. After 4 to get the next value you just add 3.

```
1,2,4,*+3...*

```

Which saves one character making the code to get an infinite list of the numbers in the Stöhr sequence 13 characters long.

This code only does something useful in the REPL since it prints the *gist* of the result for us. To get it to print otherwise you would have to explicitly tell Perl to print the results.

```
$ perl6 -e 'say 1,2,4,*+3...*'

```

( `* + 3` is simply a way to get a code reference which returns 3 added to it's only argument. Other ways to write it would be `{ $_ + 3 }`, or `-> $i { $i + 3 }`, or `{ $^i + 3 }` or `sub ($i){ $i + 3 }` )

---

The shortest way to create something Callable to generate the first *n* elements is to get a slice of the elements.

```
{(1,2,4,*+3...*)[^$_]} # 22

```

In void context that would generate the first `$_` values, then promptly throw them away.

In anything other than void context it creates an anonymous code block ( a basic subroutine without a name ) which takes one argument.

```
# store it in a scalar variable
my $sub = {(1,2,4,*+3...*)[^$_]};
say $sub.(5);
# 1 2 4 7 10

# use it immediately
say {(1,2,4,*+3...*)[^$_]}.(5);
# 1 2 4 7 10

# pretend it always had a name
my &Stöhr-first = {(1,2,4,*+3...*)[^$_]};
say Stöhr-first 5;

```

If you really think it has to have a name to qualify as a valid for this challenge you would probably do this:

```
sub s(\n){(1,2,4,*+3...*)[^n]} # 30

```

Though since `s` is also used for the substitution operator, to call this the parens are non-optional. ( You could have given it a different name I suppose )

```
say s(5);
# 1 2 4 7 10

```
> 2 votes

# Answer
# \>\<\>, 31 bytes

```
4i1nao:?!;2nao1-:?!;$:nao3+$d0.

```

Reads in a single char, uses its code point (e.g. space = 32) and prints the numbers one on each line.
> 2 votes

# Answer
I see there is already a MUCH better java answer but i spent a while on this and i'm going to post it. even if it sucks.

## Java 313 char (+4 to fit it on screen)

```
import java.util.*;public class S{public static void main(String[] a){
Set<Integer> S=new HashSet<Integer>();S.add(1);int i=1,k=0;
while(S.size()<=new Integer(a[0])){if(S.contains(i)){}else{k=0;for(int j:S){
for(int l:S){if(l!=j){if((j+l)==i)k=1;}}}if(k==0)S.add(i);}i++;}for(int x:S)
{System.out.println(x);}}}

```

always grateful to get any tips or pointers on how to improve
> 2 votes

# Answer
# Jelly, 6 bytes

```
Ż«3»1Ä

```

Try it online!

Exactly the same as the APL answer, uses the fact that the partial sums are \\$1, 1, 2, 3, 3, 3, ...\\$

Alternative 6 byters

## How it works

```
Ż«3»1Ä - Main link. Takes n on the left
Ż      - [0, 1, 2, ..., n]
 «3    - Min with 3; [0, 1, 2, 3, 3, 3, ...]
   »1  - Max with 1; [1, 1, 2, 3, 3, 3, ...]
     Ä - Cumulative sum

```

The alternatives all work by generating the partial sums, just in different methods
> 2 votes

# Answer
# Ruby - ~~108~~ 88

```
q=->n{*k=1;(m=k[-1];k<<([*m+1..2*m]-k.combination(2).map{|i,j|i+j})[0])while k.size<n;k}

```

This uses the definition of the sequence.

More readable version:

```
q=->n{
    *k=1
    (
        m = k[-1]
        k << ([*m+1..2*m] - k.combination(2).map{|i,j|i+j})[0]
    ) while k.size < n
    k
}

```

> print q\[10\]
>
> \[1, 2, 4, 7, 10, 13, 16, 19, 22, 25\]
> 1 votes

# Answer
## T-SQL 204

Assumes that the input is in a variable called @N. I can make a procedure if you want, but there really isn't a good way to get STD\_IN in T-SQL.

Also, yay for moral bonus!

```
DECLARE @Q INT=0,@B INT=2
DECLARE @ TABLE(A INT)WHILE @N>0
BEGIN
SET @N-=1
WHILE @B>1
BEGIN
SET @Q+=1
SELECT @B=COUNT(*)FROM @ C,@ B WHERE C.A+B.A=@Q
END
INSERT INTO @ VALUES(@Q)SET @B=2
END
SELECT*FROM @

```
> 1 votes

# Answer
# Mathematica, 27 bytes

Hmmm, still no Mathematica answer? Here are two:

```
NestList[#+3~Min~#&,1,#-1]&
Array[i=1/2;i+=3~Min~i&,#]&

```

both define an unnamed pure function which receives an integer and returns a list of integers. This is based on the same recurrence relation as my CJam submission. Note that the `Array`-based code starts from `1/2`, because the recurrence relation is always applied before the value is returned.
> 1 votes

# Answer
## Java, 46

```
n->IntStream.iterate(2,x->x==2?1:x+3).limit(n)

```
> 1 votes

# Answer
# Python - not even close (139)

Acting under the assumption that this weren't easily calculable as others have done, the shortest solution I've found is below:

```
from itertools import combinations as C
x,i,n=[],1,input()
while len(x)<=n:
 if i not in [sum(y) for y in C(x,2)]:x.append(i)
 i+=1
print n

```
> 1 votes

# Answer
# Clojure - 130118

```
(defn s[n](last(take n(iterate #(if(<(count %)3)(conj %(+ (apply + %)1))(conj %(+(last %)(second %)(first %))))[1]))))

```

Un-golfed version:

```
(defn stohr [n]
  (last
    (take n
      (iterate #(if (< (count %) 3)
                   (conj % (+ (apply + %) 1))
                   (conj % (+ (last %) (second %) (first %)))) [1]))))

```

Share and enjoy.
> 1 votes

# Answer
## STATA 51

```
di 1 2 _r(a)
loc b=3*$a-2
forv x=4(3)`b'{
di `x'
}

```
> 0 votes

# Answer
# TI-BASIC, 41 27 30 bytes

*For your calculator*

```
Input N:For(I,1,N:I:If I>2:(I-2)3+1:Disp Ans:End

```
> 0 votes

# Answer
# GML, 67 bytes

```
n=argument0;for(i=1;i<=n;i++){t=i;if i>2t=(i-2)*3+1show_message(t)}

```
> 0 votes

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


title: Rise, sequence, rise

text:
# Question
Title: Rise, sequence, rise
We have a strictly increasing sequence of non-negative integers, like:

```
12 11 10

```

Wait! This sequence isn't strictly increasing, is it? Well, the numbers are written in different bases. The least possible base is 2, the biggest is 10.

The task is to guess bases each number is written, so that:

* the sequence is strictly increasing,
* the sum of the bases is maximised.

For instance, the solution for the sample will be:

```
6 8 10

```

because under those bases the sequence becomes `8 9 10` decimal - a strictly increasing sequence, and we are not capable of finding bases for which the sequence remains strictly increasing and whose sum is bigger than `6+8+10` .

Due to the second limitation a solution `3 5 7` is not satisfactory: in spite of fact that the sequence becomes `5 6 7` under those bases - we need to maximise the bases sum, and `3+5+7 < 6+8+10`.

If under no bases `2<=b<=10` is it possible for the series to be strictly increasing, for instance:

```
102 10000 10

```

single

```
0

```

should be output.

The input sequence can be passed in the way it's most convenient for your solution (standard input / command line parameters / function arguments...).

# Answer
> 13 votes
# Pyth, ~~31~~ ~~30~~ 29 bytes

```
e+0f.x!sgM.:iVczdT2ZosN^STlcz

```

*1 byte thanks to @Jakube.*

Demonstration. Test Harness.

Input is given on STDIN, space separated. If newline separated input is allowed, I can shorten the program by 2 bytes.

Explanation:

```
e+0f.x!sgM.:iVczdT2ZosN^STlcz
                                  Implicit: z = input(), T = 10, Z = 0, d = ' '
                        ST        [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
                          lcz     len(z.split())
                       ^          All combinations w/replacement of that length.
                    osN           Order by increasing sum.
   f                              Filter on
              czd                 z.split(' ')
            iV   T                Vectorize the "Convert to base" operation over
                                  the integers as strings and the base sequence.
          .:      2               Take length 2 subsequences.
        gM                        Map the >= operation over them.
      !s                          Sum and logically negate.
    .x             Z              If that throws an error, returns 0 (e.g. reject)
 +0                               Prepend a 0, in case no sequences are found.
e                                 Take the end of the list.

```

Including `1` in the list of possible bases is safe because `i`, which uses Python's `int` builtin, doesn't allow `1` as a base, and therefore always throws an error, which is caught and filtered out.

# Answer
> 9 votes
# CJam, 43 bytes

```
0B,2>ea,m*{:+~}${ea::~_2$.b__Q|$=*@.b=}=p];

```

Reads command-line arguments and prints an array.

Try it online in the CJam interpreter.

### Examples

```
$ cjam rise.cjam 12 11 10
[6 8 10]
$ cjam rise.cjam 19 18 17
0

```

### How it works

```
0       e# Push a 0 (default return value).
B,2>    e# Push [0 ... 10] and remove the first two elements.
ea,     e# Push the number of command-line arguments (n).
m*      e# Cartesian power. Pushes all vectors of {2 ... 10}^n.
{:+~}$  e# Sort by the negated sums.
{       e# Find; for each vector V in {2 ... 10}^n:
  ea::~ e#   Evaluate each character of each command-line argument.
  _2$   e#   Copy the results and V.
  .b    e#   Vectorized base conversion (list to integer).
  __    e#   Push two copies.
  Q|$   e#   Deduplicate and sort the last copy.
  =     e#   Compare it to the first. Pushes 1/0 if equal/unequal.
  *     e#   Repeat the original result of .b that many times.
  @.b   e#   Vectorized base conversion (integer to list).
  =     e#   Compare the result to the modified command-line arguments.
        e#   Equality makes sure that the base was greater than all digits.
}=      e# If pushed 1, push V and break.
p       e# Print. Either prints the last V or 0 if none matched.
];      e# Clear the stack to avoid implicitly printing the 0 (if still present).

```

# Answer
> 6 votes
# Julia, ~~176~~ ~~156~~ ~~145~~ ~~118~~ ~~109~~ ~~99~~ 97 bytes

```
A->try p=NaN;flipud(map(i->(k=11;t=p;while t<=(p=parseint("$i",k-=1))end;k),flipud(A)))catch;0end

```

Ungolfed:

```
function anonfunc(i)
  # Start with k=11 so that it evaluates to 10 on first while iteration
  k=11
  # set t to the previous value of p
  # Note: p here gets held over between iterations within the map
  t=p
  # Iterate through, dropping k by 1 and evaluating the integer in
  # base k and stopping if the value drops below t
  # Note: "p=" expression inside conditional to ensure k-=1 is evaluated
  # at least once (to make NaN work as desired)
  while t<=(p=parseint("$i",k-=1))
  end
  # if it dropped below t, return the base, k to be the corresponding
  # element in the map
  return k
end

function f(A)
  # Using try/catch to return 0 if no acceptable base found
  try
    # This is a trick to make sure the comparison in the while loop
    # evaluates to false on the first use of it (last value in A)
    p=NaN
    # Apply anonfunc to each element of A, starting with the last element
    # and store the result in S
    S=map(anonfunc,flipud(A))
    # S is backwards, so flip it and return it
    return flipud(S)
  catch
    # Will throw to here if parseint fails with the base due to having
    # a digit not acceptable in the base
    return 0
  end
end

```

Used with a 1d array input. If the function is assigned to `c`, then you would call `c([12,11,10])` and it would output `[6,8,10]`.

Note: I had used `dec(i)` inside the parseint command, but because `i` is a single-character variable name, and I don't need to access a component, I used `"$i"` to get the same result.

# Answer
> 5 votes
# Julia, ~~259~~ ~~204~~ 183 bytes

Saved a bunch with help from Glen O.

```
A->(M(x)=maxabs(digits(x))+1:10;S=[];X={};for i=M(A[1]),j=M(A[2]),k=M(A[3]) s=map(parseint,map(dec,A),[i,j,k]);all(diff(s).>0)&&(S=[S,sum(s)];X=[X,{[i,j,k]}])end;X==[]?0:X[indmax(S)])

```

Ungolfed + explanation:

```
function f(A)
    # Define a function to obtain the smallest possible base range
    M(x) = (maxabs(digits(x)) + 1):10

    # Define container arrays for the sums and bases
    S = []
    X = {}

    # Loop over all possible bases for each of the elements
    for i = M(A[1]), j = M(A[2]), k = M(A[3])
        # Parse each element of the input as a string
        # in the given base
        s = map(parseint, map(dec, A), [i,j,k])

        # Push the sum and bases if s is rising
        if all(diff(s) .> 0)
            S = [S, sum(s)]
            X = [X, {[i,j,k]}]
        end
    end

    # If X is empty, return 0, otherwise return the bases
    isempty(X) ? 0 : X[indmax(S)]
end

```

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

```
{Afb:X,9,2f+m*{X\.b__$_&=*},{:+}$0\+W=}

```

This is an anonymous function which takes the input as an array of decimal integers on the stack and leaves the output as an array or the integer `0` on the stack. Online demo.

# Answer
> 2 votes
## Python 2 (147 bytes)

```
def x(s):
 q=int;c=10;o=q(s[-1])+1;l=[]
 for i in map(str,s)[::-1]:
    n=q(i,c)
    while o<=n:
        c-=1;n=q(i,c)
        if 3>c:return 0
    l=[c]+l;o=n
 return l

```

Call the function `x` with a list of the ints.

Example:

```
print x([12,11,10])

```

prints

```
[6, 8, 10]

```

# Answer
> 1 votes
# Jelly, 18 bytes

```
⁵ḊœċLḅI>0Pʋ@ƇDSÐṀḢ

```

Try it online!

## How it works

```
⁵ḊœċLḅI>0Pʋ@ƇDSÐṀḢ - Main link. Takes a sequence S on the left
⁵                  - 10
 Ḋ                 - Dequeue; [2, 3, 4, 5, 6, 7, 8, 9, 10]
    L              - Length of S
  œċ               - Combinations with replacement
             D     - Convert each in S to digits
          ʋ@       - Group the previous 4 links together into a dyad f(s, l):
     ḅ             -   Convert from base
      I            -   Forward differences
       >0          -   Greater than 0?
         P         -   True for all?
            Ƈ      - Filter the combinations over f(s, l) with the digits on the right
              SÐṀ  - Take those with a maximal sum
                 Ḣ - Take the first one or 0 if empty

```

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