title: Friendly Incenters

text:
# Question
Title: Friendly Incenters
The incenter of a triangle is the intersection of the triangle's angle bisectors. This is somewhat complicated, but the coordinate formula for incenter is pretty simple (reference). The specifics of the formula do not matter much for this challenge.

The formula requires lengths of sides, so it can be very messy for most triangles with integer coordinates because lengths of sides tend to be square roots. For example, the incenter of the triangle with vertices `(0,1)`, `(2,3)`, and `(1,5)` is `((2√2+2√17)/(2√2+√5+√17),(10√2+√5+3√17)/(2√2+√5+√17))` (yuck).

A triangle with integer coordinates can have an incenter with rational coordinates in only two cases:

1. the side lengths of the triangle are all integers
2. the side lengths of the triangle are `a√d`, `b√d`, and `c√d` for integers `a`, `b`, `c`, and `d` (equivalent for `d=1`).

(Meeting at least one of these two conditions is necessary to having a rational incenter, and the former is sufficient. I am not sure if the second case is sufficient)

# Challenge

Given a triangle OAB, it meets the "friendly incenter" condition if all of the following are true:

1. points `A` and `B` have nonnegative integer coordinates,
2. If `O` is the origin, the distances `OA`, `OB`, and `AB` are either:
    * all integers or
    * integers multiplied by the square root of the same integer (`a√d`, `b√d`, and `c√d` as described in the intro).
3. The triangle is not degenerate (it has positive area, i.e. the three vertices are not collinear)

Based on wording from the tag, your program may

* Given some index n, return the n-th entry of the sequence.
* Given some index n, return all entries up to the n-th one in the sequence.
* Without taking any index, return an (infinite) lazy list or generator that represents the whole sequence.

But what is the sequence? Since it would be too arbitrary to impose an ordering on a set of triangles, the sequence is the infinite set of all triangles that meet the "friendly incenter" condition. You may order these triangles however you wish, for example:

* in increasing order of the sum of coordinates
* in increasing order of distance from the origin

This sequence must include every "friendly incenter" triangle once and once only. To be specific:

* Every triangle must have finite index in the sequence
* Two triangles are the same if one can be reflected over the line `y=x` to reach the other, or the points `A` and `B` are the same but swapped.

For example, the triangle with vertices `(0,0)`, `(32, 24)`, and `(27, 36)` must be included at some point in the sequence. If this is included as `A(32,24) B(27,36)`, then the following triangles cannot be included because they duplicate that included triangle:

* `A(24,32) B(36,27)`
* `A(27,36) B(32,24)`
* `A(36,27) B(24,32)`

# Example Output:

If a program opts to output the first `n` triangles and is given `n=10`, it may output:

```
(0,0),(0,4),(3,4)
(0,0),(3,0),(3,4)
(0,0),(3,0),(0,4)
(0,0),(4,3),(0,6)
(0,0),(4,4),(1,7)
(0,0),(7,1),(1,7)
(0,0),(1,7),(8,8)
(0,0),(0,8),(6,8)
(0,0),(6,0),(6,8)
(0,0),(3,4),(0,8)

```

Of course, the output format is flexible. For example, the `(0,0)` coordinates may be excluded, or you may output complex numbers (Gaussian Integers) instead of coordinate pairs.

# Answer
# JavaScript (V8),  ~~232~~  229 bytes

Prints the results as \\$X\_A,Y\_A,X\_B,Y\_B\\$.

```
n=>{for(o=[0,1,2,k=3];n;)for(z=++k**4;o[A=[x,y,X,Y]=o.map(i=>~~(z/k**i)%k)]|o[[y,x,Y,X]]|o[[X,Y,x,y]]|o[[Y,X,y,x]]|Y*x==X*y|(g=d=>!d||[p,q=X*X+Y*Y,p+q-2*(x*X+y*Y)].some(v=>(v/d)**.5%1)*g(d-1))(p=x*x+y*y)?--z:o[print(A),A]=--n;);}

```

Try it online!

### Commented

```
n => {                      // n = input
  for(                      // outer loop:
    o = [0, 1, 2, k = 3];   //   o = [0, 1, 2, 3], re-used as an object to store
                            //       the coordinates that were already tried
                            //   k = counter
    n;                      //   loop until n = 0
  ) for(                    //   inner loop:
    z = ++k ** 4;           //     increment k; start with z = k ** 4
    o[  A = [x, y, X, Y] =  //     build the next tuple A = [x, y, X, Y]
          o.map(i =>        //     we try all tuples such that:
            ~~(z / k ** i)  //       0 ≤ x < k, 0 ≤ y < k, 0 ≤ X < k, 0 ≤ Y < k
            % k             //
          )                 //
    ] |                     //     if [x, y, X, Y] was already tried
    o[[y, x, Y, X]] |       //     or [y, x, Y, X] was already tried
    o[[X, Y, x, y]] |       //     or [X, Y, x, y] was already tried
    o[[Y, X, y, x]] |       //     or [Y, X, y, x] was already tried
    Y * x == X * y |        //     or (0, 0), (x, y) and (X, Y) are co-linear
    ( g = d =>              //     or g returns a truthy value:
      !d ||                 //       stop if d = 0
      [                     //       compute the squared distances:
        p,                  //         OA² = p = x² + y² (computed below)
        q = X * X + Y * Y,  //         OB² = q = X² + Y²
        p + q - 2 *         //         AB² = (X - x)² + (Y - y)² = p + q - 2(xX + yY)
        (x * X + y * Y)     //
      ].some(v =>           //       test whether there's any v in the above list
        (v / d) ** .5 % 1   //         such that sqrt(v / d) is not an integer
      ) * g(d - 1)          //       and that this holds for d - 1
    )(p = x * x + y * y) ?  //     initial call to g with d = p; if truthy:
      --z                   //       decrement z
    :                       //     else:
      o[print(A), A] = --n; //       print A, set o[A] and decrement n
  );                        //
}                           //

```
> 7 votes

# Answer
# 05AB1E, 54 bytes

```
∞<€Ðæ4ùÙεœÙ}€`2δôʒnOy`αnOª¬Lδ/tøεεDïQ}P}ày`R*Ë≠*}4ô€н

```

Outputs the infinite sequence of \\$\[\[x\_A,y\_A\],\[x\_B,y\_B\]\]\\$, although in a different order than the challenge description.

Try it online. (Extremely slow, so will only output the first five triangles before timing out after 60 seconds on TIO.)

**Explanation:**

```
∞<             # Push an infinite list non-negative list: [0,1,2,3,4,...]
  €Ð           # Repeat each item three times: [0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,...]
    æ          # Take the powerset of this infinite list
     4ù        # And only keep sublists of length 4:
               #  [[0,0,0,1],[0,0,0,1],[0,0,1,1],[0,0,1,1],[0,0,1,1],...]
       Ù       # Uniquify this list of sublists:
               #  [[0,0,0,1],[0,0,1,1],[0,1,1,1],[0,0,0,2],[0,0,1,2],...]
        ε      # Map each sublist to:
         œ     #  Get all permutations of the current list
          Ù    #  And uniquify it
        }€`    # After the map: flatten it one level down:
               #  [[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1],[1,1,0,0],...]
            δ  # Map over each sublist again
           2 ô #  And split it into parts of size 2
               #   [[[1,0],[0,0]],[[0,1],[0,0]],[[0,0],[1,0]],[[0,0],[0,1]],...]

```

We now have an infinite list of triangles in all four permutations of the \\$A\\$ and \\$B\\$ coordinates (try `∞<€Ðæ4ùÙεœÙ}€`2δô` loose).
Minor pet peeve: If the cartesian product builtin would have sorted in the same order as the powerset for infinite lists instead of `[[[0,0],[0,0]], [[0,0],[0,1]], [[0,0],[0,2]], [[0,0],[0,3]], ...]`, this entire first part could have been `∞<ãÙãÙ` instead.. :/

Now we keep all valid triangles:

```
ʒ              # Filter this list of triangles [[a,b],[c,d]] by:
 n             #  Square all inner values: [[a²,b²],[c²,d²]]
  O            #  Sum each inner list: [a²+b²,c²+d²]
   y           #  Push the original triangle [[a,b],[c,d]] again
    `          #  Pop and push both values separated to the stack
     α         #  Take the absolute difference between the coordinates: [|a-c|,|b-d|]
      n        #  Square the inner values: [|a-c|²,|b-d|²]
       O       #  Sum it: |a-c|²+|b-d|²
        ª      #  And append it to the earlier list: [a²+b²,c²+d²,|a-c|²+|b-d|²]
               #  (let's call this list [OA²,OB²,AB²] for now)
 ¬             #  Push the first item OA² (without popping the list)
  L            #  Pop and push a list in the range [1,OA²]
   δ/          #  Divide the values in both lists double-vectorized:
               #   [[OA²/1,OB²/1,AB²/1],
               #    [OA²/2,OB²/2,AB²/2],
               #    ...,
               #    [OA²/OA²,OB²/OA²,AB²/OA²]]
     t         #  Take the square root of each inner value:
               #   [[sqrt(OA²/1),sqrt(OB²/1),sqrt(AB²/1)],
               #    [sqrt(OA²/2),sqrt(OB²/2),sqrt(AB²/2)],
               #    ...,
               #    [sqrt(OA²/OA²),sqrt(OB²/OA²),sqrt(AB²/OA²)]]
      ø        #  Zip/transpose; swapping rows/columns:
               #   [[sqrt(OA²/1),sqrt(OA²/2),...,sqrt(OA²/OA²)],
               #    [sqrt(OB²/1),sqrt(OB²/2),...,sqrt(OB²/OA²)],
               #    [sqrt(AB²/1),sqrt(AB²/2),...,sqrt(AB²/OA²)]]
       ε       #  Map each inner list to:
        ε      #   Map each number to:
         D     #    Duplicate the number
          ï    #    Cast the copy to an integer
           Q   #    And check if it's still the same as before the cast
               #    (which means this number is an integer)
        }P     #   After inner map: check if all are truthy (by taking the product)
       }à      #  After the outer map: check if any are truthy (by taking the maximum)
 y             #  Push the original triangle [[a,b],[c,d]] again
  `            #  Pop and push both values separated to the stack
   R           #  Reverse the second list ([c,d] to [d,c])
    *          #  Multiply the coordinates: [a*d,b*c]
     Ë≠        #  Check that both are NOT the same: a*d != b*c
 *             #  Check if both checks were truthy

```

And since we've included all four permutations of the triangle coordinates in the infinite list, we fix this after the filter:

```
}4ô            # After the filter: split the infinite lists into parts of size 4
               # (which are all four the same triangles, but in different permutations)
   €н          # And only leave a single triangle of each quartet (the first)
               # (after which the infinite list is output implicitly as result)

```
> 5 votes

# Answer
# Husk, 42 bytes

```
foË(fεṁC2gpṁ□)S:Fz-foV≠Fz/fo§=←▲S+m↔m½π4ΘN

```

Try it online!

This is an infinite list of point pairs `[[xA,yA],[xB,yB]]`. For some reason TIO refuses to print an initial segment before running out of time, so the link cuts it after 8 elements (the 9th would take too long).

# Explanation

First we generate all point pairs.

```
m½π4ΘN
     N Infinite list of positive integers: [1,2,3..]
    Θ  Prepend zero: [0,1,2,3..]
  π4   Cartesian 4th power: [[0,0,0,0],[0,0,0,1],[1,0,0,0]..]
m½     Split each in half: [[[0,0],[0,0]],[[0,0],[0,1]],[[1,0],[0,0]]..]

```

Next we discard duplicates. This is done by creating the list of equivalent point pairs and checking that the current one is the lexicographic maximum.

```
fo§=←▲S+m↔
fo          Filter by condition:
        m↔    Reverse each: [[yA,xA],[yB,xB]]
      S+      Concatenate with the current point pair: [[xA,yA],[xB,yB],[yA,xA],[yB,xB]]
     ▲        The maximum of this list of 4 points
    ←         and its first element [xA,yA]
  §=          are equal.

```

Then we remove degenerate triangles by dividing B element-wise by A and checking that the results are distinct. Husk handles division so that this works out:

* Dividing by a nonzero integer gives a rational number by default.
* Dividing a positive number by zero gives infinity.
* Dividing a negative number by zero gives negative infinity.
* Dividing zero by zero gives a special value "Any", which is equal to every finite number, but not equal to the infinities.

```
foV≠Fz/
fo       Filter by condition:
    F      Fold by
     z/    element-wise division: [xB/xA,yB/yA]
  V≠       This list contains an unequal pair.

```

Finally, we verify the friendly incenter condition. This is done by computing the squares of the three sides, dividing out square factors and checking that the results are equal.

```
foË(...)S:Fz-
fo             Filter by condition:
          F      Fold by
           z-    element-wise subtraction
        S:       and prepend to the point pair: [[xB-xA,yB-yA],[xA,yA],[xB,yB]]
  Ë(...)         The results of ... are equal for these three points.

fεṁC2gpṁ□  Compute (a value corresponding to) d from a point (x,y) of magnitude n√d
       ṁ   Map and sum
        □  square: x²+y²
      p    Prime factors, say [2,2,2,2,2,3,5,5]
     g     Group equal adjacent elements: [[2,2,2,2,2],[3],[5,5]]
  ṁ        Map and concatenate
   C2      splitting into chunks of length 2: [[2,2],[2,2],[2],[3],[5,5]]
fε         Keep singletons: [[2],[3]]

```
> 4 votes

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


title: Build the smallest number

text:
# Question
Title: Build the smallest number
Given a non-empty list of digits 0 though 9, output the smallest number that can be produced by an expression formed by reordering these digits and introducing exponentiation signs `^`, with adjacent digits getting concatenated as multi-digit numbers. Exponentiation is evaluated as right-associative.

For example, `[4, 2, 3, 3]` could become `2^34^3` which evaluates as `2^(34^3)`, but simply writing `2334` is smallest here. You can assume that any array containing a 0 gives a minimum of zero (a special case), or that it's achievable by an expression like `0^rest`, or like `00` for just zeroes.

The input list can be taken as any ordered sequence, but not as an unordered (multi)set.

Test cases:

```
[2,3] => 8 (2^3)
[3,3] => 27 (3^3)
[4,3] => 34 (34)
[1,2,3] => 1 (1^2^3)
[2,2,2] => 16 (2^2^2)
[2,3,2] => 81 (2^3^2)
[3,0] => 0 (Special, or maybe 0^3)
[0,1,0] => 0 (Special, or maybe 0^10)

```

Shortest code in each language wins. I'll accept an answer just to give the +15 rep without any specific accepting standard.

# Answer
# 05AB1E, ~~12~~ 11 bytes

```
œε.œJ€.«m}ß

```

Try it online or verify all test cases or try it online with added debug-lines.

**Explanation:**

```
œ            # Get all permutations of the (implicit) input-list
 ε           # Map each permutation to:
  .œ         #  Get all its partitions
    J        #  Join each inner-most list together
     €       #  For each inner list:
      .«     #   Right-reduce it by:
        m    #    Taking the power
         }ß  # After the map: pop and push the flattened minimum
             # (after which it is output implicitly as result)

```
> 2 votes

# Answer
# Japt `-g`, 12 bytes

```
á Ër!p mDìÃn

```

Try it
> 1 votes

# Answer
# Jelly, 10 bytes

```
Œ!*@/€;ḌƊṂ

```

A monadic link accepting a list of digits yields an integer.

**Try it online!**

### How?

Checks digital and power-wise evaluations of all permutations even though we only *need* to check forward-sorted-digital, forward-sorted-power-wise, and reverse-sorted-power-wise (and only for `[3,2,2]`), because it's far terser.

Note that there is no need to check any mixture of digital and power-wise evaluations (they can never be strictly smaller than one of the three previously mentioned evaluations)

```
Œ!*@/€;ḌƊṂ - Link: list, L
Œ!         - all permutations (of L) -> P
        Ɗ  - last three links as a monad:
     €     -   for each (p in P):
    /      -     reduce with:
   @       -       using swapped arguments:
  *        -         exponentiation
       Ḍ   -   un-decimal (vectorises across P)
      ;    -   concatenate (these two lists of numbers)
         Ṃ - minimum

```
> 1 votes

# Answer
# Io, 77 bytes

Based on xnor's observation in the comment section. -12 bytes thanks to Arnauld's idea.

```
method(x,y :=x sort;if(y==list(2,2,3),81,y join()asNumber min(y reduce(**))))

```

Try it online!

## Explanation

```
method(x,           // Anonymous method with param x
    y := x sort     // Assign y to sorted x
    if(y == list(2,2,3), // Edge case treatment
        81,              // (It's a kinda weird case that goes right to left)
        ,y join()asNumber// Join the sorted digit-list into a single number.
        min(                // Minimum with:
            y reduce(**)))) // the sorted list reduced by the power function.

```
> 0 votes

# Answer
# JavaScript (ES7),  ~~65~~  62 bytes

*Fixed thanks to @xnor and @l4m2*
*Saved 3 bytes thanks to @l4m2*

```
a=>Math.min(x=a.sort().join``,a[0]&&eval(x-223?a.join`**`:81))

```

Try it online!

### How?

The general case is to look for the minimum of the concatenation of the digits in ascending order and an exponent chain, also in ascending order.

But as noticed by @xnor, there are a few special cases:

* if the list contains a \\$0\\$, the result is always \\$0\\$
* for `[3,2,2]`, the minimum value is \\$3^{2^2}=81\\$
> 0 votes

# Answer
# perl -alp, 83 bytes

```
%_=(22,4,23,8,24,16,33,27,222,16,223,81);$_=join"",sort@F;$_=/0/||/1/?$&:$_{$_}||$_

```

Try it online!

Reads a list of white space separated numbers from `STDIN`, writes the answer to `STDOUT`. If the input contains a `0`, output `0`, else, if the input contains a `1`, output a `1`. Else, if it's one of 6 special cases, output the corresponding value. Otherwise, output the sorted input.
> 0 votes

---
Tags: code-golf, number, expression-building
---


# Question
Title: Find the date that is n days from January 1st 1984
This challenge is a relatively simple concept that I'm surprised has not been done yet. You will be given only an integer as an input. Your task is to find the date that is this number of days from January 1st, 1984. This challenge is uniquely for the Gregorian calendar (which is standard almost everywhere).

# One restriction

The twist on this challenge is that you should not use a built-in function that deals with the date and time - because then this challenge would be trivial for a few languages. Your program must do this calculation entirely on its own - keep in mind leap years exist and have special rules:

* every year that is a multiple of four is a leap year
* the exception to the above rule is any year that is a multiple of 100 but not a multiple of 400

# Output format

You must output the year, month, and day of the month in any order you want so long as the number for the year and day of the month are not conjoined. You can use any character (not numeric or alphabetical), or none, as a separator. The **name of the month must be given as a word instead of a number.** Examples for this format are shown in the test cases.

# Input

You will be given an integer as an input. You can assume this integer will be smaller in magnitude than 700000 - this means **negative integers are also accepted**.

# Test cases

**input | accepted output (which is relatively flexible)**

`13318` | `June 18 2020`

`2` | `JanUaRy03(1984)`

`656979` | `3782september29`

`-30` | `DECEMBER 02 1983`

`-589001` | `00371may15` (leading zeroes may be used)

`0` | `1984 1 january`

# Scoring

This is . Shortest code wins!

# Answer
# 05AB1E, ~~111~~ ~~106~~ 103 bytes

```
•3zb•2ôI5°7*+F©`т‰0Kθ4ÖUD2Qi\28X+ë<7%É31α}‹i®ć>šë®1¾ǝDÅsD12‹i>1ǝë<sθ>ª]εNi”……‚æ‡‰…ä†ï€¿…Ë…ê†Ä…æ…Ì…Í”#sè

```

Output as a triplet `[day, "Month", year]`.

Try it online. (Sort of, since it times out for any input above \\$\geq-650000\\$..)

### Explanation:

Since 05AB1E doesn't have any date builtins, I've calculated things manually before. I've used the code of going to the next day from this answer of mine, which in turns also uses the leap year calculation of this answer of mine.

Since this challenge also asks to go back in time, I would need to implement something to go to a previous day as well for negative inputs, which would cost a lot of bytes. Instead, since the challenge input is limited to the range \\$\[-700000,700000\]\\$, I used that to my advantage and start going upwards in days from date June 21st, 0067 onward, which is 700,000 days before January 1st, 1984.

In pseudo-code, I therefore do the following steps:

```
1   Date currentDate = [21,06,0067]
2   Loop input + 700000 amount of times:
3*   currentDate += 1;  # Set currentDate to the next date in line
4   Convert month-integer to month-string and output the result

```

Where step 3 is divided into substeps:

```
a   Integer isLeapYear = ...;
b   Integer daysInCurrentMonth = currentDate.month == 2 ?
c                                 28 + isLeapYear
d                                :
e                                 31 - (currentDate.month - 1) % 7 % 2;
f   If(currentDate.day < daysInCurrentMonth):
g     nextDate.day += 1;
h   Else:
i     nextDate.day = 1;
j     If(currentDate.month < 12):
k       nextDate.month += 1;
l     Else:
m       nextDate.month = 1;
n       nextDate.year += 1;

```

**Transforming that into code:**

1) `Date currentDate = [21,06,0067]` is done like this:

```
•3zb•     # Push compressed integer 210667
     2ô   # Split it into parts of size 2: [21,06,67]
...
©         #  Store the current date in variable `®` (without popping)

```

2) `Loop input + 700000 amount of times:` is done like this:

```
I         # Push the input-integer
 5°       # Push 10 to the power 5: 100000
   7*     # Multiply that by 7: 700000
     +    # Add it to the input-integer
      F   # Loop that many times:

```

3a) `Integer isLeapYear = ...;` is done like this:

```
`         # Pop and push the day, month, and year separated to the stack
 т‰       # Take the divmod of 100
   0K     # Remove all 0s
     θ    # Pop and leave its last value
      4Ö  # And check if it's divisible by 4 (1 if it's a leap year; 0 if not)
        U # Pop and store this in variable `X`

```

3b) `currentDate.month == 2 ?` and 3c) `28 + isLeapYear`:

```
D         # Duplicate the month that is still on the stack
 2Qi      # If it's equal to 2 (thus February):
    \     #  Discard the duplicated month from the stack
     28X+ #  And add 28 and `X` (the isLeapYear check) together

```

3d) `:` and 3e) `31 - (currentDate.month - 1) % 7 % 2;`:

```
ë         # Else:
 <        #  Month - 1
  7%      #  Modulo-7
    É     #  Is odd (short for modulo-2)
     31α  #  Absolute difference with 31
}         # Close the if-else statement

```

3f) `If(currentDate.day < daysInCurrentMonth):`:

```
‹         # Check if the day that is still on the stack is smaller than this value
 i        # If it is:

```

3g) `nextDate.day += 1;`:

```
®         #  Push the entire date from variable `®` again
 ć        #  Extract its head (the days); pop and push [month,year] and day separated
  >       #  Day + 1
   š      #  Prepend it back in front of the list

```

3h) `Else:` and 3i) `nextDate.day = 1;`:

```
ë         # Else:
 ®        #  Push the entire date from variable `®` again
  1       #  Push a 1
   ¾      #  Push index 0
    ǝ     #  Insert the 1 at index 0 (to replace the day) in the list `®`

```

3j) `If(currentDate.month < 12):`:

```
D         # Duplicate it
 Ås       # Pop and push the middle item (the month)
   D12‹   # Check if the month is below 12:
       i  # And if it is:

```

3k) `nextDate.month += 1;`:

```
>         # Month + 1
 1        # Push index 1
  ǝ       # Insert the month + 1 at index 1 (to replace the month) in the list `®`

```

3l) `Else:`, 3m) `nextDate.month = 1;` and 3n) `nextDate.year += 1;`:

```
ë         # Else:
 <        #  Decrease the month by 1 to 11
  s       #  Swap so list `®` is at the top of the stack again
   θ      #  Pop and push its last item (the year)
    >     #  Year + 1
     ª    #  Convert the 11 to list [1,1] and append the year + 1

```

4) And finally we convert the month-integer to month-string in the resulting date, and output the result:

```
]         # Close both if-else statements and the infinite loop
 ε        # Map the resulting date to:
  Ni      #  If the (0-based) index is 1 (thus the month)
    ”……‚æ‡‰…ä†ï€¿…Ë…ê†Ä…æ…Ì…Í”
          #   Push the dictionary string of months ("December January ... November"
     #    #   Split it on spaces to a list of strings
      s   #   Swap so the month is at the top of the stack
       è  #   And index it into the list (0-based and with wraparound,
          #   which is why "december" is the first item)
          # (after which the resulting date is output implicitly)

```

See this 05AB1E tip of mine (sections *How to use the dictionary?* and *How to compress large integers?*) to understand why `•3zb•` is `210667` and `”……‚æ‡‰…ä†ï€¿…Ë…ê†Ä…æ…Ì…Í”` is `"December January February March April May June July August September October November"`.
> 7 votes

# Answer
# Perl 5, 333 bytes

```
eval'sub f{my(N,Y,B,C)=@_;X=sub{B=~/4|6|9|11/?30:B!=2?31:Y%400?Y%100?Y%4?28:29:28:29};if(!C){B--;C=&X}if(C>&X){B++;C=1}if(!B){B=12;Y--}if(B>12){B=1;Y++}@_==1?f(N,1984,1,1):N<0?f(N+1,Y,B,C-1):N>0?f(N-1,Y,B,C+1):Y.[qw(January February Mars April May June July August September October November December)]->[B-1].C}'=~s,[NXYBC],\$$&,gr;

```

Try it online!

Ungolfified:

```
sub f {
  my($n,$y,$m,$d) = @_;
  my $M = sub{$m=~/4|6|9|11/?30:$m!=2?31:$y%400?$y%100?$y%4?28:29:28:29};
  if( $d==0  ){ $m--; $d=&$M }
  if( $d>&$M ){ $m++; $d=1 }
  if( $m==0  ){ $m=12; $y-- }
  if( $m==13 ){ $m=1; $y++ }
  @_==1 ? f($n,1984,1,1)
 :$n<0  ? f($n+1,$y,$m,$d-1)
 :$n>0  ? f($n-1,$y,$m,$d+1)
 :        "$y-".[qw(January February Mars April May June July August September
                    October November December)]->[$m-1]."-$d"
}

```

Test:

```
use Test::More tests=>6;
my @tests = (
    [13318,    '2020-June-18'],
    [2,        '1984-January-3'],
    [656979,   '3782-September-30'],     #was 29
    [-30,      '1983-December-2'],
    [-589001,  '371-May-16'],            #was 15
    [0,        '1984-January-1'] );
for(@tests){
    my($n,$expect) = @$_;
    my $got = f($n);
    is($got, $expect, sprintf"   n=%-12d $expect",$n);
}

```

Output:

```
ok 1 -    n=13318        2020-June-18
ok 2 -    n=2            1984-January-3
ok 3 -    n=656979       3782-September-30
ok 4 -    n=-30          1983-December-2
ok 5 -    n=-589001      371-May-16
ok 6 -    n=0            1984-January-1

```
> 3 votes

# Answer
# T-SQL, ~~333~~ 311 bytes

Added some line feeds to avoid scrolling

```
DECLARE @ int=0WHILE~@i<724671SELECT
@+=iif(d=iif(m=2,28-sign(1/~(y%4)*y%25+1/~(y%16)),
31+~m%9%2),iif(m=12,320,51-d),1),@i-=1FROM(SELECT
@/50%18m,@%50d,@/900y)x
PRINT concat(@/900,choose(@/50%18,'january','february',
'march','april','may','june','july','august',
'september','october','november','december'),@%50)

```

**Try it online**
> 3 votes

# Answer
## JavaScript (Node.js), ~~330~~ 300 bytes

```
a=>{for(n=a<(d=m=0),y=1984,a*=n?-1:1;a-->0;){s="3"+((y%400)?((y%100)?((y%4)?(0):1):0):1)+"3232332323";v=27+(+s[m]);if(n&&!d--){m=m?(m-1):11;m==11&&y--;d=v}if(!n&&d++==v){d=0;m=m^11?(m+1):0;!m&&y++;}};return y+['January','February','March','April','May','June','July','August','September','October','November','December'][m]+(d+1)}

```

Try it online!

**String improvement (and removed parentheses):**

```
a=>{for(n=a<(d=m=0),y=1984,a*=n?-1:1;a-->0;){v=27+(+("3"+(y%400?(y%100?(y%4?0:1):0):1)+3232332323)[m]);if(n&&!d--){m=m?m-1:11;m==11&&y--;d=v}if(!n&&d++==v){d=0;m=m^11?m+1:0;!m&&y++;}}return y+"January February March April May June July August September October November December".split(" ")[m]+(d+1)}

```

Try it online!

Tests:

```
console.log(f(13318))
console.log(f(2))
console.log(f(656979))
console.log(f(-30))
console.log(f(-589001))
console.log(f(0))

```

Results:

```
2020June18
1984January3
3782September30
1983December2
371May16
1984January1

```

Ungolfified:

```
a=>{
    for(n=a<(d=m=0),y=1984,a*=n?-1:1;a-->0;){
        v=27+(+("3"+(y%400?(y%100?(y%4?0:1):0):1)+3232332323)[m]);
        if(n&&!d--){
            m=m?m-1:11;
            m==11&&y--;
            d=v
        }
        if(!n&&d++==v){
            d=0;
            m=m^11?m+1:0;
            !m&&y++;
        }
    }
return y+"January February March April May June July August September October November December".split(" ")[m]+(d+1)
}

```
> 1 votes

---
Tags: code-golf, date
---


# Question
Title: LeetCode 552: Student Attendance Record II
I'm posting my code for a LeetCode problem copied here. If you have time and would like to golf for a short solution, please do so.

### Requirement

* It has to only pass the LeetCode's Online Judge, if the language would be available.
* If the language is not available, simply we should possibly keep the `class Solution` as well as the function name.

### Languages and Version Notes

Available languages are:

* C++ clang 9 Uses the C++17 standard.
* Java 13.0.1
* Python 2.7.12
* Python3 3.8
* C gcc 8.2
* C# 8.0
* JavaScript 14.3.0
* Ruby 2.4.5
* Bash 4.3.30
* Swift 5.0.1
* Go 1.13
* Scala 2.13
* Kotlin 1.3.10
* Rust 1.40.0
* PHP 7.2

Thank you!

## Problem

> Given a positive integer n, return the number of all possible attendance records with length n, which will be regarded as rewardable. The answer may be very large, return it after mod 10 ^ 9 + 7.
>
> A student attendance record is a string that only contains the following three characters:
>
> * 'A' : Absent.
> * 'L' : Late.
> * 'P' : Present.
>
> A record is regarded as rewardable if it doesn't contain more than one 'A' (absent) or more than two continuous 'L' (late).
>
> ### Example 1:
>
> * Input: n = 2
> * Output: 8
>
> ### Explanation:
>
> There are 8 records with length 2 will be regarded as rewardable:
>
> * "PP" , "AP", "PA", "LP", "PL", "AL", "LA", "LL"
> * Only "AA" won't be regarded as rewardable owing to more than one absent times.
> * Note: The value of n won't exceed 100,000.

### Accepted Code

```
class Solution:
    def checkRecord(self, n):
        MOD = 1000000007
        a = b = d = 1
        c = e = f = 0
        for _ in range(n - 1):
            a, b, c, d, e, f = (a + b + c) % MOD, a, b, (a + b + c + d + e + f) % MOD, d, e

        return (a + b + c + d + e + f) % MOD

```

### Accepted Golf Attempt in Python 3 - 185 bytes - I

```
class Solution:
    def checkRecord(self,n):
        M=1000000007;a=b=d=1;c=e=f=0
        for _ in range(n-1):a,b,c,d,e,f=(a+b+c)%M,a,b,(a+b+c+d+e+f)%M,d,e
        return(a+b+c+d+e+f)%M

```

### Accepted Golf Attempt in Python 3 - 185 bytes - II

```
class Solution:
    def checkRecord(self,n):
        M=int(1e9+7);a=b=d=1;c=e=f=0
        for _ in range(n-1):a,b,c,d,e,f=(a+b+c)%M,a,b,(a+b+c+d+e+f)%M,d,e
        return(a+b+c+d+e+f)%M

```

### Reference

In LeetCode's answer template, there is a class usually named `Solution` with one or more `public` functions which we are not allowed to rename.

# Answer
Tips:

1. The first argument `self` can be renamed to something shorter.
2. Use `while n:n-=1` to loop `n` times
3. (Python 2 specific) You can use a single tab for the second level of indentation, instead of 2 spaces.
4. For this problem, it's sufficiently fast to just mod `b` every loop, instead of having to mod both `a` and `d`.
5. The part `a,b,c,d,e,f=...` can be broken into `a,b,c=...;d,e,f=...`, which allows reusing the updated value `a=a+b+c`
6. `c,e,f` can be initialized to `10**9+7` instead of `0` (found by @xnor).

# Python 2, ~~136 134 131 127~~ 125 bytes

```
class Solution:
 def checkRecord(_,n):
	a=b=d=1;c=e=f=M=10**9+7
	while n:n-=1;a,b,c=a+b+c,a%M,b;d,e,f=a+d+e+f,d,e
	return d%M

```

Try it online!
> 5 votes

# Answer
1. You don't need more than one space per level of indentation.
2. Observe that you have `(a+b+c+d+e+f)` used twice. This code duplication can be avoided by running the loop one more time and using `d` of the extra iteration
3. `[0]*n` is 3 bytes shorter than `range(n)`
4. It's not necessary to modulo by 1000000007 each time; you can remove it from the loop and only do it at the end (This takes about 1 second for `n=100000` on TIO, which appears to be too slow). After this, `M` will only be used once, so you can inline it into the one place it was used

---

# Python 3, 136 bytes

```
class Solution:
 def checkRecord(self,n):
  a=b=d=1;c=e=f=0
  for _ in [0]*n:a,b,c,d,e,f=a+b+c,a,b,a+b+c+d+e+f,d,e
  return d%int(1e9+7)

```

Try it online!

---

Or, if the last tip is too slow:

# Python 3, 148 bytes

```
class Solution:
 def checkRecord(self,n):
  M=int(1e9+7);a=b=d=1;c=e=f=0
  for _ in [0]*n:a,b,c,d,e,f=(a+b+c)%M,a,b,(a+b+c+d+e+f)%M,d,e
  return d%M

```

Try it online!
> 4 votes

# Answer
# C (gcc), 121 bytes

```
checkRecord(n){long a=1,b=1,d=1,c=0,e=0,f=0,x,y,m=7+1e9;for(;n--;d=y%m)x=a+b+c,y=x+d+e+f,f=e,e=d,c=b,b=a,a=x%m;return d;}

```

Try it online!

Slightly golfed less

```
checkRecord(n){
  long a=1,b=1,d=1,c=0,e=0,f=0,x,y,m=7+1e9;
  for(;n--;d=y%m)
    x=a+b+c,
    y=x+d+e+f,
    f=e,
    e=d,
    c=b,
    b=a,
    a=x%m;
  return d;
}

```
> 3 votes

# Answer
# Python 2, ~~127~~ ~~126~~ 119 bytes

```
class Solution:
 def checkRecord(s,n):
    a=[1,0,0]
    while~n:n-=1;a=[sum(a[:3])]+a;b=a[3]=sum(a[1:7])%(10**9+7)
    return b

```

Try it online! Somewhat slower than @SurculoseSputum's answer. Edit: Saved 1 byte thanks to @KevinCruijssen. Saved a further 7 bytes thanks to @xnor.

Out of interest, I also wrote a 34-byte solution in Charcoal:

```
≔Ｅ⁶¬ιηＦＮＵＭη⎇﹪λ³§η⊖λΣ…η⁺³λＩ﹪Ση⁺⁷Ｘφ³

```

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

```
≔Ｅ⁶¬ιη

```

Create an array of six elements where only the first element is `1` and the others are all `0`.

```
ＦＮ

```

Loop over the given number of times.

```
ＵＭη

```

Modify the array in-place according to the result of the mapping (the mapping is calculated first, then the array modified).

```
⎇﹪λ³

```

For positions 1, 2, 4 and 5:

```
§η⊖λ

```

Take the previous element of the previous array.

```
Σ…η⁺³λ

```

Otherwise take the sum of the array so far plus the next three elements.

This results in `h = [sum(h[0:3]), h[0], h[1], sum(h), h[3], h[4]]`.

```
Ｉ﹪Ση⁺⁷Ｘφ³

```

Take the final sum and reduce modulo `7+1000**3`.
> 3 votes

# Answer
# Java, 137 bytes

```
long checkRecord(int n){long a=1,b=1,c=0,d=1,e=0,f=0,x,y,m=7+(int)1e9;for(;n-->0;y=x+d+e+f,f=e,e=d,c=b,b=a,a=x%m,d=y%m)x=a+b+c;return d;}

```

Figured I'd add a Java answer, since it was missing. It's a straightforward port of *@ceilingcat*'s C answer, since I couldn't find anything shorter.

Try it online.

---

# 05AB1E, ~~24~~ 23 bytes

```
6LΘIFÐÁr3£‚O30Sǝ}O9°7+%

```

Try it online.

**Explanation:**

```
6L                # Push the list [1,2,3,4,5,6]
  Θ               # Check == 1 for each (1 if truthy; 0 if falsey): [1,0,0,0,0,0]
   IF             # Loop the input amount of times:
     Ð            #  Triplicate the list at the top of the stack
      Á           #  Rotate the top list once towards the right: [f,a,b,c,d,e]
       r          #  Reverse the stack so this rotated list is at the bottom
        3£        #  Pop and push the first three items of the top list: [a,b,c]
          ‚       #  Pair it with the full list: [[a,b,c,d,e,f],[a,b,c]]
           O      #  Sum both inner lists: [a+b+c+d+e+f,a+b+c]
            30S   #  Push [3,0]
               ǝ  #  Insert the a+b+c+d+e+f and a+b+c at indices 3 and 0 respectively in
                  #  the rotated list: [a+b+c,a,b,a+b+c+d+e+f,d,e]
    }O            # After the loop, sum the resulting list
      9°          # Push 10 to the power 9: 1000000000
        7+        # Add 7: 1000000007
          %       # Modulo
                  # (after which the result is output implicitly)

```
> 1 votes

# Answer
# x86\_64 machine language for Linux, 83 bytes

```
0x00:  55                push rbp
0x01:  45 31 C0          xor  r8d, r8d
0x04:  31 C9             xor  ecx, ecx
0x06:  53                push rbx
0x07:  6A 01             push 1
0x09:  41 5A             pop  r10
0x0b:  31 DB             xor  ebx, ebx         ; a=b=d=0
0x0d:  4D 89 D1          mov  r9, r10
0x10:  4D 89 D3          mov  r11, r10         ; c=e=f=1
0x13:  BE 07 CA 9A 3B    mov  esi, 0x3b9aca07  ; m=1000000007
0x18:  4B 8D 04 0B       lea  rax, [r11 + r9]
0x1c:  48 01 C8          add  rax, rcx         ; x=a+b+c
0x1f:  48 99             cqo
0x21:  49 8D 0C 02       lea  rcx, [r10 + rax]
0x25:  48 F7 FE          idiv rsi              ; x%=m
0x28:  4C 01 C1          add  rcx, r8
0x2b:  48 01 D9          add  rcx, rbx         ; y=x+d+e+f
0x2e:  4C 89 C3          mov  rbx, r8          ; f=e
0x31:  48 89 C8          mov  rax, rcx         ; e=d
0x34:  4C 89 C9          mov  rcx, r9          ; c=b
0x37:  48 89 D5          mov  rbp, rdx         ; b=a
0x3a:  48 99             cqo
0x3c:  48 F7 FE          idiv rsi              ; y%=m
0x3f:  4D 89 D0          mov  r8, r10
0x42:  4D 89 D9          mov  r9, r11
0x45:  49 89 D2          mov  r10, rdx         ; d=y
0x48:  49 89 EB          mov  r11, rbp         ; a=x
0x4b:  FF CF             dec  edi
0x4d:  75 C9             jne  0x18             ; if( --n ) goto 0x18
0x4f:  92                xchg eax, edx
0x50:  5B                pop  rbx
0x51:  5D                pop  rbp
0x52:  C3                ret                   ; return d

```

To Try it online!, call the following c code as if it were a function (you may also be able to paste it into one or more 'interview preparation websites' and run it as if it were a c program)

```
(*checkRecord)()=L"\xc0314555\x6a53c931\x315a4101\xd1894ddb\xbed3894d\x3b9aca07\x0b048d4b\x48c80148\x0c8d4999\xfef74802\x48c1014c\x894cd901\xc88948c3\x48c9894c\x9948d589\x4dfef748\x894dd089\xd28949d9\xffeb8949\x92c975cf\xc35d5b";

```
> 1 votes

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


title: Split pythagorean triples into two sets

text:
# Question
Title: Split pythagorean triples into two sets
# Task

Write a program/function that when given a positive integer \\$n\\$ splits the numbers from \\$1\\$ to \\$n\\$ into two sets, so that no integers \\$a, b, c\\$, satisfying \\$a^2 + b^2 = c^2\\$ are all in the same set. For example, if \\$3\\$ and \\$4\\$ are in the first set, then \\$5\\$ must be in the second set since \\$3^2+4^2=5^2\\$.

Acceptable Output Formats:

* One of the sets
* Both the sets
* An array of length \\$n\\$ where the \\$i\\$-th element (counting from 1) is one of two different symbols (e.g. 0 and 1, a and b, etc.) which represent which set \\$i\\$ belongs to.The reverse of this is also fine

# Constraints

You can expect \\$n\\$ to be less than \\$7825\\$. This is because \\$7824\\$ is proven to be the largest number to have solution (which also implies that all numbers less than 7825 have a solution).

# Scoring

This is so shortest bytes wins.

# Sample Testcases

```
3 -> {1}
3 -> {}
5 -> {1, 2, 3}
5 -> {1, 2, 3}, {4, 5}
5 -> [0, 0, 0, 1, 1]
5 -> [1, 1, 0, 0, 1]
10 -> {1, 3, 6}
10 -> {1, 2, 3, 4, 6, 9}
41 -> {5, 6, 9, 15, 16, 20, 24, 35}

```

A checker to verify your output can be found here

---

*Inspired by The Problem with 7825 - Numberphile*

# Answer
> 7 votes
# , 37 bytes

Brute forces through the possible sets, outputs the bit mask.

```
((-&.#.+./@,)[(e.~+/~)/.*:@#\)^:_@#&1

```

Try it online! (Also outputs list as numbers for easier comparison.)

### How it works

```
((-&.#.+./@,)[(e.~+/~)/.*:@#\)^:_@#&1
                                  #&1 convert to list of N 1's
(                            )^:_     do until list does not change
                        *:@#\         right: convert to 1,4,9…,N^2
             [                        left: the bit mask
                      /.              partition left based on right, for each set:
                  +/~                 make M*M addition table
               e.~                    any element of that in the same set?
       +./@,                          OR all answers: 1 on conflict, 0 if finished
  -&.#.                               list: from base 2, subtract that^, to base 2

```

# Answer
> 6 votes
# Wolfram Language (Mathematica), ~~132~~ 116 bytes

```
{1}.SatisfiabilityInstances[And@@(And[Or@@#,Nand@@#]&/@Map[x,Select[#~Tuples~3,{1,1,-1}.#^2==0&],{2}]),x/@#]&@*Range

```

Try it online!

This uses Mathematica's SAT solver to label the integers 1 through the input as `True` and `False`.

* This is composed with `Range`, so what feeds into the main function is a list of the integers from 1 to the input.
* `Select[#~Tuples~3,{1,1,-1}.#^2==0&]` generates all the Pythagorean triples (multiple times actually, but that's okay).
* `And[Or@@#,Nand@@#]&` is true if at least one, but not all, of the elements of its input is true.
* `{1}.SatisfiabilityInstances[...,x/@#]` uses the SAT solver. Since `SatisfiabilityInstances` returns a list containing one solution, we use `{1}.` to get its first element.

# Answer
> 6 votes
# Jelly, 18 bytes

```
œc3²SHeƊ$Ƈ
ÇŒpÇÞḢQ

```

**Try it online!** (too inefficient for \\$n\>25\\$ on TIO).

### How?

Strategy: Find all Pythagorean triples using \\$\[1,n\]\\$ then find a way to pick 1 element from each of them such that the resulting set contains no Pythagorean triples. That way we have a set which both contains no Pythagorean triple and blocks the other set from having any.

```
œc3²SHeƊ$Ƈ - Link 1, find all Pythagorean triples: list of integers OR number
œc3        - all combination of length 3 (given n uses [1..n])
         Ƈ - keep those for which:
        $  -   last two links as a monad:
   ²       -     square each of them
       Ɗ   -     last three links as a monad:
    S      -       sum (of the three squares)
     H     -       halved
      e    -       exists in (the squares)?

ÇŒpÇÞḢQ - Main Link: n
Ç       - call Link 1 as a monad -> all Pythagorean triples using [1,n]
 Œp     - Cartesian product -> all ways to pick one from each
    Þ   - sort those by:
   Ç    -   call Link 1 as a monad (empty lists are less than non-empty ones)
     Ḣ  - head
      Q - deduplicate (if n < 7825 this is a valid answer)

```

# Answer
> 5 votes
# JavaScript (ES6),  ~~118~~  117 bytes

Much slower for -1 byte.

```
f=(n,a=[],b=a)=>n?f(n-1,[n,...a],b)||f(n-1,a,[n,...b]):[a,b][E='every'](o=>o[E](x=>o[E](y=>o[E](k=>k*k-x*x+y*y))))&&b

```

Try it online!

---

# JavaScript (ES6),  ~~122 119~~  118 bytes

Returns one of the sets as an array.

```
f=(n,a=[],b=a)=>[a,b][S='some'](o=>o[S](x=>o[S](y=>o[S](k=>k*k==x*x+y*y))))?0:n?f(n-1,[n,...a],b)||f(n-1,a,[n,...b]):b

```

Try it online!

Solution found locally for \\$n=41\\$:

```
[ 5, 6, 9, 15, 16, 20, 24, 35 ]

```

# Answer
> 4 votes
# 05AB1E, 14 bytes

Port of the 17 byte Jelly answer. (`Læ3ùʒDnO;tå}€н` is the same length)

```
Læ3ùʒnRćsOQ}€н

```

Try it online!

## Explanation

```
L              Length range
 æ             Powerset
  3ù           Pick truples (length-3 tuples)
    ʒ          Filter:
     n             Square all items
      R            Reverse the list
       ć           Head-extract (head on top)
        s          Swap
         O         Sum the remaining list
          Q}       Equal?
            €н Take head of each

```

# Answer
> 3 votes
# Jelly, ~~30~~ 26 bytes

```
œ|/L=³
Œc§œ&
ŒP²ÇẸƊÐḟŒcÑƇḢ

```

Try it online!

## How?

This does a more brute-force approach, filtering subsets of `[1..n]` based on whether they contain any Pythagorean triples. Then, it finds two triple-less subsets that have all `n` elements between them

```
œ|/L=³         # Test if a pair of sets unions to [1..n]
œ|/              # Set intersection
   L             # Is the length
    =³           # equal to n?

Œc§œ&          # Does a pair exist that sums to another?
Œc               # Compute all pairs of squares
  §              # Sum each
   œ&            # Set intersection with the set of squares (nonempty & truthy if a pair of squares sum to another square)

ŒP²ÇẸƊÐḟŒcÑƇḢ  # Main link
ŒP               # All subsets of 1..n
     ƊÐḟ         # Remove those where:
  ²                # of the squares,
   ÇẸ              # a pair of the squares exists that sum to another square
        Œc       # All pairs of these triple-less subsets
          ÑƇ     # Filter the pairs by whether they union to [1..n]
            Ḣ    # Head; get the first one

```

# Answer
> 2 votes
# Wolfram Language (Mathematica), 1664 bytes

works for all n (1 to 7824) instantly

```
IntegerDigits[Uncompress@"1:eJwllsmRHDkMRXWVGfIAKwGYoKtMGAfG/5veT0V0dHVlkiDwN/av//7/87t+/vjhPfem6tm+K6+yqFft5e/e9fXzeH6W62050307NdsTzYtIe/mMApOd/mJY5G/Yn9FdxidPe95uu/lGRNu2+U2n1c6zypfbWza7m80S99pKerF625V9oeNuzW1ywnt92jfZUcXbV94eHrael5Evyo1vHazcy3LPpOa7fXNlmW6d0xF0QXvLBHP+ikf2mKuDBp+1v94BBtvQlEDVdrdRfES8pIPsR1mmfAOUUXdeN2f8DvZzxNFc64c5VWJjPGie0rHls/TaOo4TmoGXtwx4Ry/rHzwDEtbwMwYbMDW2xhkvg18BoPva04zBJqAwisL+AbcLa34OLdSBUGpa1VlDJp3G2wqtA+zTgmz4sTh7YxCVN1RCFYy7x3z5ivIghVhm/s3vBxM6F1S0KJO5k8GpRiuMbRCaRT1eF1NoRSGflb7OUYgJJSYNOoRzyIDMLEaCQgAxNFWsRkq5zPxGDYZLewakSRvgCRNrcJ92EFzis1FSIhnoZ8pYZ3HeA4TJfUwq+RiyB478gA7UA7QgUxl05yvcKDHgOonYOcLfciywwgKLC+ICNSWqFNaLYFEzQ6ANmsEBJ96ZhnEwE5prPX06RBYD20FJPVk6EyrYfOoK3dnniG+kCBBbCY1Ra/FGBfDtMzB/vEItgKMRAYiHqDREkghhA5KiC6jFTp8nGAycUCi+dg6B4ZdSGxMVXb8bGWLYOgQDzFe0fG3wztNPk/edjBV6v5m1uOgvMKCxOwBWtr5OoAYuFmUyTAkdkiNoytgrx32iBDDEjzsfsdQJltIFFnaAQztkUigpUtSiG+Y98Jz56Ejgv0eXhBAiwhtKBVYjqpJdqB8KHPQN60QCRj+gnFWejUKLrUQAuHIcwmUh/sQAYIqxlBAGcHCF2S+pCdPsY/hHMAZKEVBCn9AUeyB0wEcZZClbIEmXLkyZ5YMM5dSobQkJQbjyQoYAE4J05LbAcwpAlJQu8VIKW4M4PsccBJFi4TxOPiyRKUJMcc7LIO1JVgWiwpHoIWA4oTj0Ri2yAqsiQZS6Cm9QIXpLtwCGIU0lb3TzkcyM0iEvsA5mHPLi5OPH/SBx4zj6IeMfwxnC/HQ68ouCiGBS42nw6ErC/eIaJYEQoHIWgIFRSo7QA2ZomqcKfSEKyDdKcsUXPXAlYNf40HqfbCBMzgKVc5pFvs6nxodtJ9xV9+kOITFIVFAfdYMAWrfQY03joC+08pt2kZgpz584m4EWhA4x/I0WHNjo7xBP4ifFGfgf3VIIueRHe0jyaL+rkQhEk6xGhpXi8LlBu4YBYYyAnaAHw1MeBRUXMLoAfK5S3IfisZWE+7jYKN4EGG2SlkBlKICHzEOaLxFKWuMImiBA0bLMAi3IBR/wUNnByvhCD1uTcsJLN04oGBu9SaKGlJFAKs24krEs9NKZ7h0oxTkMTAYUyjn91xAKWMCFv8CZyock+EGWMjCutNANrdZOqY0Z0T66Yr2oJswJ+FBaKHORK8sOAbUuruSWkR5gRbZoLuYPer7CORkDULwUjQgHD++RLKBOR0p3EkvGh0VG4pbCOyt+QBs99V9DtuSl",2][[;;#]]&

```

Try it online!

# Answer
> 2 votes
# , ~~99~~ 95 bytes

```
n=scan():1
f=function(j)outer(a<-n[j]^2,a,`+`)%in%a
while(any(f(i<-sample(!0:1,n,T)),f(!i)))0
i

```

Try it online!

Outputs a vector of `TRUE` and `FALSE` representing in reverse order which set each integer belongs to. (The footer of the TIO transforms this into a list of integers in the first set.)

Works by random sampling: repeatedly draw a random subset of `1:n` until neither the subset nor its complement contain any Pythagorean triples (checked by the function `f`).

It will finish in finite time for any input \<7825, but will in expectation take a very long time for largeish `n`. TIO starts timing out around `n=90`.

# Answer
> 1 votes
# Charcoal, 74 bytes

```
ＮθＦθＦιＦκＦ⁼Ｘ⊕ι²ΣＸ⊕⟦κλ⟧²⊞υ⊕⟦ικλ⟧≔⁰ηＷ¬ⅉ«≔Ｅυ§κ÷ηＸ³λζ≦⊕η≔Ｘζ²ε¿¬⊙ε⊙ε№ε⁺κμＩ⁻Ｅθ⊕κζ

```

Try it online! Well, for `n<50`, otherwise it gets too slow. Link is to verbose version of code. Based on @JonathanAllen's answer. Explanation:

```
Ｎθ

```

Input `n`.

```
ＦθＦιＦκ

```

Loop through all potential Pythagorean triples.

```
Ｆ⁼Ｘ⊕ι²ΣＸ⊕⟦κλ⟧²

```

If this is indeed a triple,

```
⊞υ⊕⟦ικλ⟧

```

then push it to the empty list.

```
≔⁰η

```

Start iterating through the ways of picking one element of each triple.

```
Ｗ¬ⅉ«

```

Repeat until output has been generated.

```
≔Ｅυ§κ÷ηＸ³λζ

```

Pick one element from each triple.

```
≦⊕η

```

Increment the loop counter.

```
≔Ｘζ²ε

```

Square the elements.

```
¿¬⊙ε⊙ε№ε⁺κμ

```

Check for Pythagorean triples.

```
Ｉ⁻Ｅθ⊕κζ

```

If none, then output one of the sets.

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


title: Is this stack of CNN layers valid?

text:
# Question
Title: Is this stack of CNN layers valid?
## Background

This challenge is about Convolutional neural networks, and its two main building blocks, namely Convolutional layer and Pooling layer.

For simplicity, we ignore the "depth" of the images and intermediate tensors, and just look at the width and height.

### Convolutional layer

A convolutional layer works like a kernel in image processing. It is defined by kernel width and height, and kernel mode (min, mid, or max). A *min kernel* extracts values at positions where the entire kernel overlaps with the original image. For a *mid kernel*, the center of the kernel is placed over each pixel of the image; for a *max kernel*, all positions where any pixel overlaps with the kernel is considered.

One pixel per positioning of the kernel is produced, resulting in a 2D array which can be smaller than (min), equal to (mid), or larger than (max) the input image.

```
Kernel (C is the center)
###
#C#
###

Image
*****
*****
*****
*****
*****

Min kernel convolution (results in 3x3)
###**     **###
#C#**     **#C#
###** ... **###
*****     *****
*****     *****
 ...       ...
*****     *****
*****     *****
###** ... **###
#C#**     **#C#
###**     **###

Mid kernel convolution (results in 5x5)
###           ###
#C#***     ***#C#
###***     ***###
 ***** ... *****
 *****     *****
 *****     *****
  ...       ...
 *****     *****
 *****     *****
 ***** ... *****
###***     ***###
#C#***     ***#C#
###           ###

Max kernel convolution (results in 7x7)

###             ###
#C#             #C#
###****     ****###
  *****     *****
  ***** ... *****
  *****     *****
  *****     *****
   ...       ...
  *****     *****
  *****     *****
  ***** ... *****
  *****     *****
###****     ****###
#C#             #C#
###             ###

```

If the input image has `IR` rows and `IC` columns, and the kernel has `KR` rows and `KC` columns, the output dimensions are defined as follows:

* Min kernel: `IR - KR + 1` rows, `IC - KC + 1` columns; invalid if the resulting rows or columns are zero or negative
* Mid kernel: `IR` rows, `IC` columns; error if either `KR` or `KC` is even
* Max kernel: `IR + KR - 1` rows, `IC + KC - 1` columns

### Pooling layer

A pooling layer is defined by window width and height, and the horizontal and vertical stride size (how many units to move at once in either direction). See the following illustration:

```
3x3 window, 2x2 stride pooling on a 7x7 image
###**** **###** ****###
###**** **###** ****###
###**** **###** ****###
******* ******* *******
******* ******* *******
******* ******* *******
******* ******* *******

******* ******* *******
******* ******* *******
###**** **###** ****###
###**** **###** ****###
###**** **###** ****###
******* ******* *******
******* ******* *******

******* ******* *******
******* ******* *******
******* ******* *******
******* ******* *******
###**** **###** ****###
###**** **###** ****###
###**** **###** ****###

```

If the input image has `IR` rows and `IC` columns, and the pooling layer has the window of `WR`/`WC` rows/columns and `SH`/`SV` horizontal/vertical stride, the output dimensions are defined as follows:

* Rows: `(IR - WR)/SV + 1`, error if `(IR - WR) % SV != 0` or `WR < SV`
* Cols: `(IC - WC)/SH + 1`, error if `(IC - WC) % SH != 0` or `WC < SV`

### Stacking multiple layers

The convolutional and pooling layers can be stacked in any arbitrary way, so that the output of the previous layer becomes the input of the next layer. The dimensions of the input image to the entire stack is provided, and the dimensions of each intermediate image should be calculated sequentially. A stack of layers is valid if no error occurs at any layer. The final output size does not matter, as long as it can be calculated without error.

The following stack is valid:

```
Input image 25x25
1. Min Convolution 3x3         => Intermediate image 23x23
2. Pooling 3x3 with stride 2x2 => Intermediate image 11x11
3. Max Convolution 3x3         => Intermediate image 13x13
4. Max Convolution 4x4         => Intermediate image 16x16
5. Pooling 2x2 with stride 2x2 => Intermediate image 8x8
6. Min Convolution 5x5         => Intermediate image 4x4
7. Pooling 4x4 with stride 3x3 => Output image 1x1

```

Taking any contiguous subsequence of the stack, starting with the respective (intermediate) image as the input, is also valid. (e.g. steps 2, 3, 4, 5 with input image `23x23`)

Any of the following modifications to the 7-layer stack above will result in an invalid stack:

* Replace step 2 with stride `4x4` or `2x4`: stride is larger than window in at least one dimension
* Replace step 3 with `mid` convolution: image size becomes too small at step 7
* Replace step 4 with `mid` convolution: mid convolution with even kernel dimension is an error
* Replace step 6 with kernel size `9x5` or larger: kernel does not fit in the image (`IR-KR+1` is zero or negative, which is an error)

## Challenge

Given the input dimensions and the description of a stack of convolutional/pooling layers, determine if it is a valid configuration, i.e. not an error.

The description of the stack can be taken in reasonable ways to represent

* a list (sequence) of two kinds of layers
* for a convolutional layer, the kernel size (width/height; two numbers) and mode (min/mid/max)
* for a pooling layer, the window size (width/height) and stride (horizontal/vertical; four numbers in total)

All numbers (kernel size, window size, stride) are guaranteed to be positive integers.

You may output truthy/falsy by following your language's convention or selecting two distinct values for true/false respectively.

Standard rules apply. The shortest code in bytes wins.

# Answer
# Python 3.8 (pre-release), ~~138~~ ~~134~~ 118 bytes

```
lambda s,l:[s:=[(r:=(I-(m:=M-(M>1))*k)/S+m+0%(k%2+m**2))+(r%1+(S>k)and E)for I,k,S,*_ in zip(s,*L,(1,1))]for M,L in l]

```

Try it online!

Anonymous function that throws an error only if the given layers are in error. Takes a list of layers, where each layer is either:

* `[mode, [KR,KC]]` where mode is `-1`,`0`,or`-1` corresponding to a max,mid, or min convolutional layer, or
* `[2, [WR, WC], [SR, SC]]` where the 2 indicates a pooling layer

I could save a few bytes if `(1,1)` could be added as a third element of convolutional layers, but I feel that's redundant information with the `mode` already differing it from pooling layers.

### Commented

```
f=\
lambda s,l:\
 [
  s:=[             # set s (size) to:
   (
    r:=                # an optimized calculation of the new size (r) along width (i=0) or height (i=1)
                         # (need to set this to r because s is not updated until finishing this element)
                         # [IR - KR + 1, IR, IR + KR - 1, (IR - WR)/SV + 1]
                         # <--> (IR - m * KR)/(SV or 1) + m where m is -1 for max, 0 for mid, 1 for min, and 1 for pool
    (I-                    # (IR-
     (m:=M-(M>1))          #  m  # (need to convert pool(M=2) to 1, leave -1,0,1 unchanged) # maybe something with `M&2` might shorten
     *k)/                  # * KR)/
    S                      # SV
    +m                     # + m
    +0%(               # error if k is even and m==0 (mid):
    k%2+m**2             # This sum gives 0 iff k is even and m==0
    )                    # 0 mod the sum throws ZeroDivisionError if the sum is 0
   )                     # otherwise it is equal to 0 and does not affect the sum
   +(
     r%1+(S>k)         # True if r is not an integer or the stride size is greater than the window size
    and E              # throw NameError (E is not defined) if the above is true
   )                   # otherwise, False equals 0 in sums, so this does not affect the sum
   for I,k,S,*_ in zip(s,*L,(1,1))       # repeat for rows and columns
                                         # The (1,1) provides the default value of S
  ]
  for M,L in l  # repeat for each layer
 ]

```

### Named function + traditional for-loop approach for the same bytecount:

```
def f(s,l):
 for M,L in l:s=[(r:=(I-(m:=M-(M>1))*k)/S+m+0%(k%2+m**2))+(r%1+(S>k)and E)for I,k,S,*_ in zip(s,*L,(1,1))]

```

### Ungolfed

```
def f(size, layers):
    while layers:
        [mode, *layer] = layers.pop(0)

        if mode < 2:
            # convolutional, mostly eq to pooling with S=(1,1)
            layer += [(1,1)]

        kernel, stride = layer

        m = 1 if mode > 1 else mode
        for i in 0,1:
            size[i] = (size[i] - m*kernel[i])/stride[i] + m
            # check for fractions
            if size[i] % 1:
                return False
            # can't have even kernel dimension on a mid window
            if m==0 and kernel[i]%2==0:
                return False
            # stride can't be larger than kernel
            if stride[i] > kernel[i]:
                return False
    return True

```
> 5 votes

# Answer
# 05AB1E, 45 bytes

```
sεÐgiĀ«]vyн³Dp-Nè©*-yθ/®+ÐïÊyнÈ®_*y`‹«à~i0q]1

```

Inspired by *@fireflame241*'s ungolfed Python answer, so make sure to upvote him!

Three loose inputs:

1. The window dimensions `[w,h]`
2. List of layers, where `[[r,c]]` is a convolutional layer and `[[r,c],[r,c]]` is a pooling layer.
3. List of kernel modes, where `-1` is max; `0` is mid; `1` is min; and `2` is a pooling layer.

Try it online. (No test suite due to the `q`, but I've manually checked the four falsey examples.)

**Explanation:**

```
s                   # Swap to get the first two (implicit) inputs onto the stack,
                    # with the second input at the top
 ε                  # Map over each layer:
  Ð                 #  Triplicate the layer
   gi               #  If it's length is 1 (thus a convolutional layer):
     Ā              #   Truthify both integers, so we have a pair of 1s: [1,1]
      «             #   Merge it to the layer
 ]                  # Close the if-statement and map
  v                 # Loop over each layer `y`, consisting of two pairs [kernel,stride]:
   yн               #  Get the first pair (the kernel)
     ³              #  Push the third input-list of modes
      Dp-           #  Transform the 2s into 1s (by checking for prime, and subtracting)
         Nè         #  Get the mode at the current loop-index
           ©        #  Store it in variable `®` (without popping)
            *       #  Multiply this mode to the kernel-pair
             -      #  Subtract each from the dimensions-pair
              yθ    #  Get the last pair (the stride)
                /   #  Divide the dimension-pair by the stride-pair
                 ®+ #  And add the modified mode `®` to each
   Ð                #  Triplicate the modified dimensions-pair
    ï               #  Cast the values in the top copy to integers
     Ê              #  Check if the top two pairs are NOT equal
                    #  (1 if the dimension-pair contains decimal values; 0 if integers)
    yн              #  Push the kernel again
      È             #  Check for both values if they're even (1 if even; 0 if odd)
       ®_           #  Check if `®` is 0 (1 if 0; 0 if not)
         *          #  Multiply the checks
    y`              #  Push the kernel-pair and stride-pair separated to the stack
      ‹             #  Check if [kernel-row < stride-row, kernel-column < stride-column]
    «               #  Merge the pairs of checks together
     à              #  Check of any are truthy of this quartet by taking the maximum
    ~               #  Check if either is truthy by taking the bitwise-OR
     i              #  If this is truthy:
      0             #   Push a 0
       q            #   And stop the program
                    #   (after which this 0 is output implicitly as result)
 ]                  # Close the if-statement and loop
  1                 # And push a 1
                    # (which will be output implicitly if we didn't encountered the `q`)

```
> 2 votes

# Answer
# , 84 bytes

Takes in a list of layers; `mode x y` for convolution, with `_1 0 1` for `min mid max`, and a 2x2 matrix `wx wy ,: sx sy` for pooling, and `x y` for the initial image. Returns 0 if it is a valid description, 1 otherwise.

```
_ e.&>(1(+_*[><.)@+(-{.)%(]*>:)/@])`((+_*1>])@+}.(]-~*+_*(2|[)+:|@]){.)@.(]3=#)~&.>/

```

Try it online!

### How it works

```
(…)`(…)@.(]3=#)~&.>/

```

We fold the list from the right (where initially the `25 25` stands), and based on the left length (3 for convolution, 2 for pooling), we choose from two functions. Whenever we encounter an error, we set to row or column dimension to infinity. For convolution with example `_1 3 3` (min 3x3):

```
((+_*1>])@+}.(]-~*+_*(2|[)+:|@]){.)
           }.(                 ){.  split into 3 3 and _1 as arguments
                            |@]     mode != 0?
                      2|[           3 3 even?
                          +:        not-or, so 1 iff mode = 0 and dimension even
                   _*               if this^ returns 1, convert it to infinity
                 *+                 add to this dim * mode (_3 _3)
              ]-~                   subtract the mode (_2 _2)
           +                        add to the image dimension (23 23)
  (+_*1>])                          if the dimensions are less than 1, add infinity

```

For pooling, with for example `3 3,:2 2` on the left side, `23 23` on the right side:

```
(1(+_*[><.)@+(-{.)%(]*>:)/@])
                   (]*>:)/@]  multiple stride with (window greater/equal stride?)
             (-{.)%           (image - window)% mstride, is infinity iff mstride is 0
 1          +                 add one
  (+_*[><.)                   add infinity if flooring a dimensions changes it

```

An the end, after applying each layer:

```
_ e.&>       unbox and check if at least one dimension is infinity

```
> 2 votes

---
Tags: code-golf, decision-problem, neural-networks
---


title: Make Zero From First 'n' Numbers

text:
# Question
Title: Make Zero From First 'n' Numbers
# Challenge

The challenge is to write a code that takes a positive integer 'n' as an input and displays all the possible ways in which the numbers from 1 - n can be written, with either positive or negative sign in between, such that their sum is equal to zero. Please remember that you may only use addition or subtraction.

For example, if the input is 3, then there are 2 ways to make the sum 0:

```
 1+2-3=0
-1-2+3=0

```

Note that, the numbers are in order, starting from 1 till n (which is 3 in this case). As it is evident from the example, the sign of the first number can also be negative, so be careful.

Now, 3 was pretty much simple. Let us list all the ways when we consider the number 7.

```
 1+2-3+4-5-6+7=0
 1+2-3-4+5+6-7=0
 1-2+3+4-5+6-7=0
 1-2-3-4-5+6+7=0
-1+2+3+4+5-6-7=0
-1+2-3-4+5-6+7=0
-1-2+3+4-5-6+7=0
-1-2+3-4+5+6-7=0

```

So here, we have got a total of 8 possible ways.

---

# Input And Output

As stated before, the **input would be a positive integer**. Your output should contain all the possible ways in which the numbers give a sum of zero. **In case there is no possible way** to do the same, **you can output anything** you like.

Also, **you can print the output in any format you like**. **But, it should be understandable**. For example, you may print it as in the above example. Or, you may just print the signs of the numbers in order. Otherwise, you can also print '0's and '1's in order, where '0' would display negative sign and '1' would display positive sign (or vice versa).

For example, you can represent 1+2-3=0 using:

```
1+2-3=0
1+2-3
[1,2,-3]
++-
110
001

```

However, I would recommend using any of the first three formats for simplicity. You can assume all the inputs to be valid.

---

# Examples

```
7 ->

 1+2-3+4-5-6+7=0
 1+2-3-4+5+6-7=0
 1-2+3+4-5+6-7=0
 1-2-3-4-5+6+7=0
-1+2+3+4+5-6-7=0
-1+2-3-4+5-6+7=0
-1-2+3+4-5-6+7=0
-1-2+3-4+5+6-7=0

4 ->

 1-2-3+4=0
-1+2+3-4=0

2 -> -

8 ->

 1+2+3+4-5-6-7+8=0
 1+2+3-4+5-6+7-8=0
 1+2-3+4+5+6-7-8=0
 1+2-3-4-5-6+7+8=0
 1-2+3-4-5+6-7+8=0
 1-2-3+4+5-6-7+8=0
 1-2-3+4-5+6+7-8=0
-1+2+3-4+5-6-7+8=0
-1+2+3-4-5+6+7-8=0
-1+2-3+4+5-6+7-8=0
-1-2+3+4+5+6-7-8=0
-1-2+3-4-5-6+7+8=0
-1-2-3+4-5+6-7+8=0
-1-2-3-4+5+6+7-8=0

```

---

# Scoring

This is , so the shortest code wins!

# Answer
# Haskell, 42 bytes

```
f n=[l|l<-mapM(\i->[i,-i])[1..n],0==sum l]

```

Try it online!
> 8 votes

# Answer
# Jelly, 9 bytes

```
1,-ṗ×RSÐḟ

```

Try it online!

# Exp

```
1,-ṗ×RSÐḟ  Main link. Input = **n**. Assume n=2.
1,-        Literal list [1, -1].
   ṗ       Cartesian power **n**. Get [[1, 1], [1, -1], [-1, 1], [-1, -1]]
    ×R     Multiply (each list) by **R**ange 1..n.
       Ðḟ  ilter out lists with truthy (nonzero)
      S      **S**um.

```

---

# Jelly, 9 bytes

Jonathan Allan's suggestion, output a list of signs.

```
1,-ṗæ.ÐḟR

```

Try it online!
> 7 votes

# Answer
# Python 2, 62 bytes

```
f=lambda n,*l:f(n-1,n,*l)+f(n-1,-n,*l)if n else[l]*(sum(l)==0)

```

Try it online!

*Mr. Xcoder saved 4 bytes with a nifty use of starred arguments.*
> 5 votes

# Answer
# Perl, ~~37~~ 36 bytes

```
perl -E 'map eval||say,glob join"{+,-}",0..<>' <<< 7

```
> 4 votes

# Answer
# 05AB1E, 11 bytes

```
®X‚¹ãʒ¹L*O_

```

Try it online!

The output format for e.g. input `3` is:

```
[[-1, -1, 1], [1, 1, -1]]

```

That is, `-1-2+3, 1+2-3`.
> 3 votes

# Answer
# Python 3, 105 bytes

```
lambda n:[k for k in product(*[(1,-1)]*n)if sum(-~n*s for n,s in enumerate(k))==0]
from itertools import*

```

Try it online!
> 2 votes

# Answer
# Wolfram Language (Mathematica), 36 bytes

```
Pick[p={1,-1}~Tuples~#,p.Range@#,0]&

```

Try it online!
> 2 votes

# Answer
# Husk, 10 bytes

```
fo¬ΣΠmSe_ḣ

```

Try it online!

## Explanation

Not too complicated.

```
fo¬ΣΠmSe_ḣ  Implicit input, say n=4
         ḣ  Range: [1,2,3,4]
     m      Map over the range:
      Se     pair element with
        _    its negation.
            Result: [[1,-1],[2,-2],[3,-3],[4,-4]]
    Π       Cartesian product: [[1,2,3,4],[1,2,3,-4],..,[-1,-2,-3,-4]]
f           Keep those
   Σ        whose sum
 o¬         is falsy (equals 0): [[-1,2,3,-4],[1,-2,-3,4]]

```
> 2 votes

# Answer
# JavaScript (V8),  ~~69 61~~  58 bytes

*Saved 8 bytes thanks to @Neil*
*Saved 3 bytes thanks to @l4m2*

Prints all solutions.

```
f=(n,o='')=>n?f(n-1,o+'+'+n)&f(n-1,o+-n):eval(o)||print(o)

```

Try it online!
> 2 votes

# Answer
# Swift, 116 bytes

```
func f(n:Int){var r=[[Int]()]
for i in 1...n{r=r.flatMap{[$0+[i],$0+[-i]]}}
print(r.filter{$0.reduce(0){$0+$1}==0})}

```

Try it online!

## Explanation

```
func f(n:Int){
  var r=[[Int]()]                         // Initialize r with [[]]
                                          // (list with one empty list)
  for i in 1...n{                         // For i from 1 to n:
    r=r.flatMap{[$0+[i],$0+[-i]]}         //   Replace every list in r with the list
  }                                       //   prepended with i and prepended with -i
  print(r.filter{$0.reduce(0){$0+$1}==0}) // Print all lists in r that sums to 0
}

```
> 1 votes

# Answer
# Python 3 + numpy, ~~104~~ 103 bytes

```
import itertools as I,numpy as P
lambda N:[r for r in I.product(*[[-1,1]]*N)if sum(P.arange(N)*r+r)==0]

```

Output is \[-1, 1\] corresponding to the sign.
> 1 votes

# Answer
# Python 2, 91 bytes

```
lambda x:[s for s in[[~j*[1,-1][i>>j&1]for j in range(x)]for i in range(2**x)]if sum(s)==0]

```

Try it online!

Returns a list of satisfying lists (e.g., f(3)=\[\[-1,-2,3\], \[1,2,-3\]\])
> 1 votes

# Answer
# APL (Dyalog), 38 bytes

```
{k/⍨0=+/¨k←((,o∘.,⊢)⍣(⍵-1)⊢o←¯1 1)×⊂⍳⍵}

```

Try it online!
> 1 votes

# Answer
# C (gcc), ~~171~~ 161 bytes

```
k,s;f(S,n,j)int*S;{if(s=j--)S[j]=~0,f(S,n,j),S[j]=1,f(S,n,j);else{for(k=n;k;)s+=k--*S[k];if(!s)for(puts("");k<n;)printf("%d",S[k++]+1);}}F(n){int S[n];f(S,n,n);}

```

Try it online!
> 1 votes

# Answer
# Pyth, 13 bytes

```
f!sT.nM*F_BMS

```

**Try it here!**
> 1 votes

# Answer
# Clean, 79 bytes

```
import StdEnv
$n=[k\\k<-foldr(\i l=[[p:s]\\s<-l,p<-[~i,i]])[[]][1..n]|sum k==0]

```

Try it online!
> 1 votes

# Answer
# Retina, 73 bytes

```
.+
*
_
=_$`
+0`=
-$%"+
(-(_)+|\+(_)+)+
$&=$#2=$#3=
G`(=.+)\1=
=.*

_+
$.&

```

Try it online! Explanation:

```
.+
*

```

Convert the input to unary.

```
_
=_$`

```

Convert the number to a list of `=`-prefixed numbers.

```
+0`=
-$%"+

```

Replace each `=` in turn with both `-` and `+`, duplicating the number of lines each time.

```
(-(_)+|\+(_)+)+
$&=$#2=$#3=

```

Separately count the number of `_`s after `-`s and `+`s. This sums the negative and positive numbers.

```
G`(=.+)\1=

```

Keep only those lines where the `-`s and `+`s cancel out.

```
=.*

```

Delete the counts.

```
_+
$.&

```

Convert to decimal.
> 1 votes

# Answer
# C (gcc), ~~101~~ ~~100~~ 83 bytes

Represents addition as 0 and subtraction as 1, but that ultimately that does not matter since for any valid sequence, the complement of the sequence will also result in zero. Returns the permutations by appending them as 32-bit ints to a caller-provided buffer.

```
i,j,s;f(n,p)int*p;{for(i=1<<n;--i;s||(*p++=i))for(j=s=0;j<n;)s+=i>>j++&1?j:-j;n=p;}

```

Try it online!

# Explanation

```
i,j,s; // iterators i and j, sum s.
f(n,p)int*p; // declare function
{
  for ( i=1<<n; --i; // iterate over all permutations of n bits (except all-0)
      s||(*p++=i)) // if the permutation summed to 0, append it to the buffer
   for(j=s=0;j<n;)
     s+= i>>j++&1 // Determine the value of the jth bit
       ?j:-j; // 1=>+(j+1), 0=>-(j+1)
  n=p; // return the pointer to the end of the appended values
}

```
> 1 votes

# Answer
# , 35 30 bytes

-5 bytes thanks to FrownyFrog!

```
>:@i.(]#~0=1#.*"1)_1^2#:@i.@^]

```

Try it online!

## Original:

# , 35 bytes

```
[:(#~0=+/"1)>:@i.*"1(_1^[:#:@i.2^])

```

## How it works

I multiply the list 1..n with all possible lists of coefficients 1 / -1 and find the ones that add up to zero.

```
                    (             ) - the list of coefficients
                             i.     - list 0 to
                               2^]  - 2 to the power of the input
                     _1^[:          - -1 to the power of
                          #:@       - each binary digit of each number in 0..n-1 to
                 *"1                - each row multiplied by
            >:@i.                   - list 1..n
  (#~      )                        - copy those rows
     0=+/"1                         - that add up to 0
[:                                  - compose

```

Try it online!

As an alternative I tried an explicit verb, using the approach of cartesian product of +/-:

# , 37 bytes

```
3 :'(#~0=+/"1)(-y)]\;{(<"1@,.-)1+i.y'

```

`{(<"1@,.-)` finds the cartesian products for example:

```
{(<"1@,.-) 1 2 3
┌───────┬────────┐
│1 2 3  │1 2 _3  │
├───────┼────────┤
│1 _2 3 │1 _2 _3 │
└───────┴────────┘

┌───────┬────────┐
│_1 2 3 │_1 2 _3 │
├───────┼────────┤
│_1 _2 3│_1 _2 _3│
└───────┴────────┘

```

Too bad that it boxes the result, so I spent some bytes to unbox the values

Try it online!
> 0 votes

# Answer
# Perl 6, 43 bytes

```
{grep *.sum==0,[X] (1..$_ X*1,-1).rotor(2)}

```

Try it
Returns a sequence of lists

## Expanded:

```
{  # bare block lambda with implicit parameter ｢$_｣

  grep              # only return the ones
    *.sum == 0,     # that sum to zero

    [X]             # reduce with cross meta operator

      (
          1 .. $_   # Range from 1 to the input

        X*          # cross multiplied by

          1, -1

      ).rotor(2)    # take 2 at a time (positive and negative)
}

```

`1..$_ X* 1,-1``(1, -1, 2, -2)`
`(…).rotor(2)``((1, -1), (2, -2))`
`[X] …``((1, 2), (1, -2), (-1, 2), (-1, -2))`
> 0 votes

# Answer
Not the best but I tried :)

# C (Linux GCC)

## Entire program: 282 characters

```
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int n,x,i,s;int main(int c,char**z){n=atoi(z[1]);int a[n];for(x=0;x<n;x++)a[x]=x+1;for(i=0;i<pow(2, n)-1;i++){s=0;for(x=0;x<n;x++){printf("%c%d",i>>x&0x01?'-':'+',a[x]);s+=(i>>x&0x01?-1:1)*a[x];}printf(s!=0?"\r":"=%d \n",s);}}

```

## Just as function: 196 characters

```
void z(int n){int a[n],x,i,s;for(x=0;x<n;x++)a[x]=x+1;for(i=0;i<pow(2,n)-1;i++){s=0;for(x=0;x<n;x++){printf("%c%d",i>>x&0x01?'-':'+',a[x]);s+=(i>>x&0x01?-1:1)*a[x];}printf(s!=0?"\r":"=%d \n",s);}}

```

### Results

* n = 4:

```
+1-2-3+4=0
-1+2+3-4=0

```
* n = 7:

```
+1-2-3-4-5+6+7=0
-1+2-3-4+5-6+7=0
-1-2+3+4-5-6+7=0
+1+2-3+4-5-6+7=0
-1-2+3-4+5+6-7=0
+1+2-3-4+5+6-7=0
+1-2+3+4-5+6-7=0
-1+2+3+4+5-6-7=0

```

## Abstract Printing & Just Function: 172 characters

You could shrink the print statements down much more by simply outputting only the +/-'s which are represented by 1/-1 and abstractly representing the entire sum thing, but I still don't think it would beat the other C answers anyway.

That version is:

```
void z(int n){int a[n],x,i,j,s;for(x=0;x<n;x++)a[x]=x+1;for(i=0;i<pow(2,n)-1;i++){s=0;for(x=0;x<n;x++){j=i>>x&0x01?-1:1;printf("%d ",j);s+=j*a[x];}printf(s!=0?"\r":"\n");}}

```

## Results

* n = 4:

```
1 -1 -1 1
-1 1 1 -1

```
* n = 7:

```
1 -1 -1 -1 -1 1 1
-1 1 -1 -1 1 -1 1
-1 -1 1 1 -1 -1 1
1 1 -1 1 -1 -1 1
-1 -1 1 -1 1 1 -1 1
1 1 -1 -1 1 1 -1
1 -1 1 1 -1 1 -1 1
-1 1 1 1 1 -1 -1 -1

```
> 0 votes

# Answer
# T-SQL, 152 bytes

Input is a *varchar(max)*

Output format is *+1+2-3*

```
WITH C as(SELECT @*1d,@+null o,0f
UNION ALL
SELECT~-d,concat(char(44+s),d,o),f+s*d
FROM C,(values(-1),(1))x(s)WHERE d>0)SELECT
o FROM C WHERE f=0and d=0

```

**Try it online**
> 0 votes

# Answer
# , ~~82~~ 69 bytes

```
s=t(expand.grid(rep(list(c(-1,1)),n<-scan())))*1:n;t(s[,!colSums(s)])

```

Try it online!

*Edit: -13 bytes by using built-in `expand.grid` function to automatically create matrix of all combinations of `+1` and `-1`.*

Selects rows of matrix of 1:n in all combinations of positive & negative which sum to zero.

Commented version:

```
s=t(                    # transpose matrix of:
mapply(rep,             # apply the function 'rep'
    list(c(-1,1)),      # to the values (-1, 1)
    each=2^(0:(n-1)),   # repeating each by an increasing power-of-2
    length=2^n)         # and making the output length always 2^n
)                       # so: this generates a matrix of all the
                        # combinations of -1 and 1

t(                      # now transpose the matrix s
s[,                     # taking only the columns with a
   !colSums(s*1:n)]     # zero sum of multiplying the values
)                       # by the sequence 1:n

```

**Previous (but sadly ~~longer~~ *much* longer) recursive strategy: 118 bytes**

```
f=function(n,l=NULL,t=0)`if`(n>1,c(f(n-1,c(0,l),t-n),f(n-1,c(1,l),t+n)),`if`(t==n,list(c(0,l)),if(t==-n)list(c(1,l))))

```

Try it online!

Outputs `1` for `+` and `0` for `-` (or the other way around).

Commented version:

```
f=function(n,l=NULL,t=0){               # n = counts down to 1 recursively
                                        # l = list of signs so far
                                        # t = total so far
    if(n==1){                           # if n is 1...
        if(t-n==0){                     # ...then if t-n makes zero...
            return(list(c("-",l))) }    # add a '-' to the list of signs & return it
        else if(t+n==0){                # ...or, if t+n makes zero...
            return(list(c("+",l))) }    # add a '+' to the list of signs & return it
        else {                          # ...otherwise we can't make zero...
            return(NULL) }              # so return NULL
    } else {                            # if n is greater than 1
        return(c(                       # return the result of calling this function
            f(n-1,c("-",l),t-n),        # using n-1, after applying either a '-'
            f(n-1,c("+",l),t+n)         # or a '+' and updating the total so far
        ))
    }
}

```
> 0 votes

---
Tags: code-golf, number, number-theory, integer, expression-building
---


# Question
Title: Count from 1 to 100... in Roman Numerals
**Write a program that count from 1 to 100 in Roman Numerals** and print these numbers by standard output. Each one of the numbers must be separated by spaces.

You cannot use any built in function to transform to roman numerals nor external application or library to do so.

The desired result is

```
I II III IV V VI VII VIII IX X XI XII XIII XIV XV XVI XVII XVIII XIX XX XXI XXII XXIII XXIV XXV XXVI XXVII XXVIII XXIX XXX XXXI XXXII XXXIII XXXIV XXXV XXXVI XXXVII XXXVIII XXXIX XL XLI XLII XLIII XLIV XLV XLVI XLVII XLVIII XLIX L LI LII LIII LIV LV LVI LVII LVIII LIX LX LXI LXII LXIII LXIV LXV LXVI LXVII LXVIII LXIX LXX LXXI LXXII LXXIII LXXIV LXXV LXXVI LXXVII LXXVIII LXXIX LXXX LXXXI LXXXII LXXXIII LXXXIV LXXXV LXXXVI LXXXVII LXXXVIII LXXXIX XC XCI XCII XCIII XCIV XCV XCVI XCVII XCVIII XCIX C

```

As it is a code golf challenge, **shortest code wins**.

# Answer
## Perl 69 bytes

```
s;.;y/XVI60-9/CLXVIX/dfor$a[$_].="32e$&"%72726;gefor 1..100;print"@a"

```

Works by way of magic formula. The expression `"32e$&"%72726` transforms each digit in the following manner:
*0⇒32, 1⇒320, 2⇒3200, 3⇒32000, 4⇒29096, 5⇒56, 6⇒560, 7⇒5600, 8⇒56000, 9⇒50918*

After applying the translation `y/016/IXV/`, we have this instead:
*0⇒32, 1⇒32**I**, 2⇒32**II**, 3⇒32**III**, 4⇒29**I**9**V**, 5⇒5**V**, 6⇒5**VI**, 7⇒5**VII**, 8⇒5**VIII**, 9⇒5**I**9**X**8*

The rest of the digits (`2-57-9`) are removed. Note that this could be improved by one byte by using a formula which translates `012` instead of `016`, simplifying `/XVI60-9/` to `/XVI0-9/`. I wasn't able to find one, but maybe you'll have better luck.

Once one digit has been transformed in this manner, the process repeats for the next digit, appending the result, and translating the previous `XVI`s to `CLX` at the same time the translation for the new digit occurs.

**Update**
Exhaustive search didn't reveal anything shorter. I did, however, find an alternative 69 byte solution:

```
s;.;y/XVI0-9/CLXIXV/dfor$a[$_].="57e$&"%474976;gefor 1..100;print"@a"

```

This one uses a `0-2` substitution for `IXV`, but has a modulo that's one digit longer.

---

## Update: ~~66~~ 65 bytes

This version is notably different, so I should probably say a few words about it. The formula it uses is actually one byte longer!

Unable to shorten the formula any more than it is, I decided to golf down what I had. It wasn't long until I remembered my old friend `$\`. When a `print` statment is issued, `$\` is automatically appended to the end of the output. I was able to get rid of the awkward `$a[$_]` construction for a two byte improvement:

```
s;.;y/XVI60-9/CLXVIX/dfor$\.="32e$&"%72726;ge,$\=!print$"for 1..100

```

Much better, but that `$\=!print$"` still looked a bit verbose. I then remembered an alternative, equal length formula I had found which didn't contain the number `3` in any of its digit transforms. So, it should be possible to use `$\=2+print` instead, and substitute the resulting `3` with a space:

```
s;.;y/XVI0-9/CLXIIX V/dfor$\.="8e$&"%61535;ge,$\=2+print for 1..100

```

Also 67 bytes, due to the necessary whitespace between `print` and `for`.

> **Edit**: This can be improved by one byte, by moving the `print` to the front:
>
> ```
> $\=2+print!s;.;y/XVI0-9/CLXIIX V/dfor$\.="8e$&"%61535;gefor 1..100
>
> ```
>
> Because the substitution needs to evaluate completely before the `print`, the assignment to `$\` will still occur last. Removing the whitespace between `ge` and `for` will issue a deprecation warning, but is otherwise valid.

But, if there were a formula which didn't use a `1` anywhere, `$\=2+print` becomes `$\=print` for another two bytes worth of savings. Even if it were one byte longer, it'd still be an improvement.

As it turns out, such a formula does exist, but it is one byte longer than the original, resulting in a final score of **65 bytes**:

```
$\=print!s;.;y/XVI60-9/CLXXI V/dfor$\.="37e$&"%97366;gefor 1..100

```

---

## Methodology

The question was asked how one might go about finding such a formula. In general, finding a magic formula to generalize any set of data is matter of probability. That is, you want to choose a form which is as likely as possible to produce something similar to the desired result.

Examing the first few roman numerals:

```
0:
1: I
2: II
3: III
4: IV
5: V
6: VI
7: VII
8: VIII
9: IX

```

there is some regularity to be seen. Specifically, from *0-3* and then again from *5-8*, each successive term increases in length by one numeral. If we wanted to create a mapping from digits to numerals, we would want to have an expression that *also* increases in length by one digit for each successive term. A logical choice is *k • 10d* where *d* is the corresponding digit, and *k* is any integer constant.

This works for *0-3*, but *4* needs to break the pattern. What we can do here is tack on a modulo:
*k • 10d % m*, where *m* is somewhere between *k • 103* and *k • 104*. This will leave the range *0-3* untouched, and modify *4* such that it won't contain four `I`s. If we additionally constrain our search algorithm such that the modular residue of *5*, let's call it *j*, is less than *m / 1000*, this will ensure that we also have regularity from *5-8* as well. The result is something like this:

```
0: k
1: k0
2: k00
3: k000
4: ????
5: j
6: j0
7: j00
8: j000
9: ????

```

As you can see, if we replace `0` with `I`, *0-3* and *5-8* are all guaranteed to be mapped correctly! The values for *4* and *9* need to be brute forced though. Specifically, *4* needs to contain one `0` and one `j` (in that order), and *9* needs to contain one `0`, followed by one other digit that doesn't appear anywhere else. Certainly, there are a number of other formulae, which by some fluke of a coincidence might produce the desired result. Some of them may even be shorter. But I don't think there are any which are as likely to succeed as this one.

I also experimented with multiple replacements for `I` and/or `V` with some success. But alas, nothing shorter than what I already had. Here is a list of the shortest solutions I found (the number of solutions 1-2 bytes heavier are too many to list):

```
y/XVI60-9/CLXVIX/dfor$\.="32e$&"%72726
y/XVI0-9/CLXIXV/dfor$\.="57e$&"%474976
y/XVI0-9/CLXIVXI/dfor$\.="49e$&"%87971

y/XVI0-9/CLXIIXIV/dfor$\.="7e$&"%10606  #
y/XVI0-9/CLXIIXIV/dfor$\.="7e$&"%15909  # These are all essentially the same
y/XVI0-9/CLXIIXIV/dfor$\.="7e$&"%31818  #

y/XVI0-9/CLXIIX V/dfor$\.="8e$&"%61535  # Doesn't contain 3 anywhere

y/XVI60-9/CLXXI V/dfor$\.="37e$&"%97366 # Doesn't contain 1 anywhere

```
> 77 votes

# Answer
# HTML + JavaScript + CSS (137)

HTML (9)

```
<ol></ol>

```

JavaScript (101)

```
for(i=1;i<=100;i++){document.getElementsByTagName('ol')[0].appendChild(document.createElement('li'))}

```

CSS (27)

```
ol{list-style:upper-roman}

```

Output

...

Demo on JSBin
> 15 votes

# Answer
# Python 116

better golfed code of scleaver's answer:

```
r=lambda a,b,c:('',a,2*a,3*a,a+b,b,b+a,b+a+a,b+3*a,a+c);print' '.join(i+j for i in r(*'XLC')for j in r(*'IVX'))+' C'

```
> 10 votes

# Answer
# Python, 139

```
print' '.join(' '.join(i+j for  j in ' _I_II_III_IV_V_VI_VII_VIII_IX'.split('_'))for i in ' _X_XX_XXX_XL_L_LX_LXX_LXXX_XC'.split('_'))+' C'

```
> 8 votes

# Answer
## C, 177 160 147 chars

There are shorter solutions, but none in C, so here's my try.

New solution, completely different from my previous one:

```
char*c;
f(n){
    printf("%.*s",n%5>3?2:n%5+n/5,c+=n%5>3?n%4*4:2-n/5);
}
main(i){
        for(;i<100;putchar(32))
                c="XLXXXC",f(i/10),
                c="IVIIIX",f(i++%10);
        puts("C");
}

```

## Previous solution (160 chars):

Logic:
1. `f` prints a number from 1 to 10. `c` is the digits used, which can be `IVX` or `XLC`. Called once for the tens once for the ones.
2. If `n%5==0` \- print nothing or `c[n/5]` which is `I` or `V` (or `L` or `C`).
3. If `n%4==4` \- `4` or `9` \- print `I` (or `X`), by `n+1`.
4. If `n>4` \- print `5` (i.e. `V` or `L`) then `n-5`.
5. If `n<4` \- print `I` then `n-1` (i.e. `n` times `I`).

```
char*c;
p(c){putchar(c);}
f(n){
        n%5?
                n%5>3?
                        f(1),f(n+1):
                        n>4?
                                f(5),f(n-5):
                                f(n-1,p(*c)):
                n&&p(c[n/5]);
}
main(i){
        for(;++i<101;p(32))
                c="XLC",f(i/10),
                c="IVX",f(i%10);
        p(10);
}

```
> 6 votes

# Answer
# Mathematica 159 150 142

```
c = {100, 90, 50, 40, 10, 9, 5, 4, 1};
Table["" <> Flatten[ConstantArray @@@ Thread@{StringSplit@"C XC L XL X IX V IV I",
  FoldList[Mod, k, Most@c]~Quotient~c}], {k, 100}]

```

---

**Built-in solution**: `IntegerString`, 38 chars

```
IntegerString[k, "Roman"]~Table~{k, 100}

```
> 5 votes

# Answer
## JavaScript, 123

Inspired by a longer version I came across in a Polish newsgroup (at least, Chrome thought it was Polish).

```
for(i=100,a=[];n=i--;a[i]=r)
  for(r=y='',x=5;n;y++,x^=7)
    for(m=n%x,n=n/x^0;m--;)
      r='IVXLC'[m>2?y+n-(n&=-2)+(m=1):+y]+r;
alert(a)

```
> 5 votes

# Answer
# Q (~~81~~ 80)

2nd cut:

```
1_,/'[($)``X`XX`XXX`XL`L`LX`LXX`LXXX`XC cross``I`II`III`IV`V`VI`VII`VIII`IX],"C"

```

1st cut:

```
1_,/'[$:[``X`XX`XXX`XL`L`LX`LXX`LXXX`XC cross``I`II`III`IV`V`VI`VII`VIII`IX]],"C"

```
> 5 votes

# Answer
## Python, 168

```
r=lambda n,l,v:(r(n,l[1:],v[1:])if n<v[0]else l[0]+r(n-v[0],l,v))if n else''
for i in range(1,101):print r(i,'C XC L XL X IX V IV I'.split(),[100,90,50,40,10,9,5,4,1]),

```

**Explanation**

Using these values, take the largest value not greater than n and subtract it from n. Repeat until n is 0.

```
'C'  = 100
'XC' = 90
'L'  = 50
'XL' = 40
'X'  = 10
'IX' = 9
'V'  = 5
'IV' = 4
'I'  = 1

```
> 4 votes

# Answer
## Ruby 1.9, 140 132

```
r=" "
100.times{r+=?I
0while[[?I*4,"IV"],["VIV","IX"],[?X*4,"XL"],["LXL","XC"],[/(.)((?!\1)[^I])\1/,'\2']].any?{|q|r.sub! *q}
$><<r}

```

This literally counts from 1 to 100 in Roman numerals. Starts with a blank string, then loops through appending "I" and then repeatedly applying a series of substitution rules, effectively adding 1.

Edit: Added version number, since `?I` only works in 1.9, and used @Howard's changes to trim some characters.
> 4 votes

# Answer
## Ruby 112 chars

```
101.times{|n|r=' ';[100,90,50,40,10,9,5,4,1].zip(%w(C XC L XL X IX V IV I)){|(k,v)|a,n=n.divmod k;r<<v*a};$><<r}

```

Basically using the `to_roman` method explained here, but using a zipped array for brevity.
> 4 votes

# Answer
**perl 205**

```
@r = split //, "IVXLC";
@n = (1, 5, 10, 50, 100);

for $num (1..100) {
  for($i=@r-1; $i>=0; $i--) {
    $d = int($num / $n[$i]);
    next if not $d;
    $_ .= $r[$i] x $d;
    $num -= $d * $n[$i];
  }
  $_ .= " ";
}
s/LXXXX/XC/g;
s/XXXX/XL/g;
s/VIIII/IX/g;
s/IIII/IV/g;
print;

```

Golfed:

```
@r=split//,"IVXLC";@n=(1,5,10,50,100);for$num(1..100){for($i=@r-1;$i>=0;$i--){$d=int($num/$n[$i]);next if!$d;$_.=$r[$i]x$d;$num-=$d*$n[$i];}$_.=" ";}s/LXXXX/XC/g;s/XXXX/XL/g;s/VIIII/IX/g;s/IIII/IV/g;print;

```
> 2 votes

# Answer
**MUMPS 184**

```
S V(100)="C",V(90)="XC",V(50)="L",V(40)="XL",V(10)="X",V(9)="IX",V(5)="V",V(4)="IV",V(1)="I" F I=1:1:100 S S=I,N="" F  Q:'S  S N=$O(V(N),-1) I S&(S'<N ) S S=S-N W V(N) S N="" w:'S " "

```

Same algorithm as @cardboard\_box, from whom I've taken the explanation verbatim -

**Explanation**

Using these values, take the largest value not greater than n and subtract it from n. Repeat until n is 0.

```
'C'  = 100
'XC' = 90
'L'  = 50
'XL' = 40
'X'  = 10
'IX' = 9
'V'  = 5
'IV' = 4
'I'  = 1

```
> 2 votes

# Answer
# , 85 bytes

```
R=.romans
for(r in 1:100){while(r>0){cat(names(R[I<-R<=r][1]))
r=r-R[I][1]}
cat(" ")}

```

Try it online!

Uses the random `utils` package variable `.romans` to get the *values* of the roman numerals, but does the conversion by itself; the builtin approach would be 20 bytes: `cat(as.roman(1:100))`
> 2 votes

# Answer
# APL (Dyalog Unicode), 61 bytes

```
∊{'IVXLC'[∊5 3 1+{(⍺=0)↓⍺↑⍨⊃¯2,⍨⍵~0}⌿0 5⊤1+⍵⊤⍨3⍴10],' '}¨⍳100

```

Try it online!

(I know there's already an APL answer, but wanted to re-solve it anyway)

Adapted and golfed from Nikolay Nikolov's piece of code that supports up to M at the bottom of this page.

### How it works

```
∊{'IVXLC'[∊5 3 1+{(⍺=0)↓⍺↑⍨⊃¯2,⍨⍵~0}⌿0 5⊤1+⍵⊤⍨3⍴10],' '}¨⍳100
∊{'IVXLC'[...],' '}¨⍳100  ⍝ Less interesting part
                    ⍳100  ⍝ 1-based range; 1 to 100 inclusive
 {        ...     }¨      ⍝ Compute a representation for each number
  'IVXLC'[   ],' '        ⍝ Index into the string and pad with a space
∊                         ⍝ Concatenate the strings

∊5 3 1+{(⍺=0)↓⍺↑⍨⊃¯2,⍨⍵~0}⌿0 5⊤1+⍵⊤⍨3⍴10  ⍝ Interesting part
                                 ⍵⊤⍨3⍴10  ⍝ Last 3 decimal digits of ⍵
                           0 5⊤1+  ⍝ Divmod of each digit +1 by 5
       {                 }⌿  ⍝ Compute the partial roman representation:
⍝  Digit  0  1   2     3       4
⍝  Div    0  0   0     0       1
⍝  Mod    1  2   3     4       0
⍝  Result [] [0] [0 0] [0 0 0] [0 1]
⍝  Digit  5   6     7       8         9
⍝  Div    1   1     1       1         2
⍝  Mod    1   2     3       4         0
⍝  Result [1] [1 0] [1 0 0] [1 0 0 0] [0 2]
                 ⊃¯2,⍨⍵~0  ⍝ ¯2 if mod is 0, keep mod otherwise
              ⍺↑⍨          ⍝ Overtake div with the above
                           ⍝ (¯2: add 0 to the left; other: add (mod-1) 0s to the right)
        (⍺=0)↓             ⍝ Drop one if div is 0
 5 3 1+  ⍝ Offset each nested array to point to correct roman unit
∊        ⍝ Flatten

```

---

OP said "You cannot use any built in function to transform to roman numerals" but didn't say about a built-in that does arithmetic over roman numerals, so this one could be technically valid:

# APL (Dyalog Unicode), 29 bytes

```
⎕CY'dfns'
∊,∘' '¨{⍳⍵}roman'C'

```

Try it online!

This one leverages the library operator `roman` that does various arithmetic over roman numerals (that is, the input is also a roman numeral). So this basically computes the 1-based range `{⍳⍵}` over `roman` numerals with the input value `'C'` (100), appends a space to each string `,∘' '¨` and flattens them .
> 2 votes

# Answer
## APL 128

I tried an indexing solution in APL:

```
r←⍬
i←1
l:r←r,' ',('   CXI LV CX'[,⍉((1+(4 4 2 2⊤0 16 20 22 24 32 36 38 39 28)[;1+(3⍴10)⊤i])×3)-4 3⍴2 1 0])~' '
→(100≥i←i+1)/l
r

```

It can be 4 bytes shorter in index origin 0 instead of 1 but the real space hog is the generation of the index matrix via:

```
4 4 2 2⊤0 16 20 22 24 32 36 38 39 28

```

So far I have not been able to generate the indices on the fly!
> 1 votes

# Answer
# LaTeX (138)

```
\documentclass{minimal}
\usepackage{forloop}
\begin{document}
\newcounter{i}
\forloop{i}{1}{\value{i} < 101}{\roman{i}\par}
\end{document}

```
> 1 votes

# Answer
# Python, 125

```
' '.join(i+j for i in['']+'X XX XXX XL L LX LXX LXXX XC C'.split()for j in['']+'I II III IV V VI VII VIII IX'.split())[1:-38]

```
> 1 votes

# Answer
# PHP, ~~38~~ 37 bytes

`<ol type=I><?=str_repeat("<li>",100);`

-1 byte thanks to @manatwork

Same idea as Patrick's answer, but in a more compact language. Beats Mathematica!

Try it Online!
> 1 votes

# Answer
**VBA (Excel), 245 bytes**

created Function for Repetition and Replace - **91 bytes**

`Function s(a,b):s=String(a,b):End Function
Function b(x,y,z):b=Replace(x,y,z):End Function`

using immediate window (**154 bytes**)

`p="I":for x=1to 100:?b(b(b(b(b(b(b(b(s(x,p),s(100,p),"C"),s(90,p),"XC"),s(50,p),"L"),s(40,p),"XL"),s(10,p),"X"),s(9,p),"IX"),s(5,p),"V"),s(4,p),"IV"):next`
> 1 votes

# Answer
# Java (OpenJDK 8), 152 bytes

```
a->{String[] t=",X,XX,XXX,XL,L,LX,LXX,LXXX,XC,,I,II,III,IV,V,VI,VII,VIII,IX".split(",");for(int i=1;i<100;i++){a+=t[i/10]+t[i%10+10]+" ";}return a+"C";}

```

Try it online!

**Explanation:**

```
String[] t=",X,XX,XXX,XL,L,LX,LXX,LXXX,XC,,I,II,III,IV,V,VI,VII,VIII,IX".split(",");
//Create an array of numerals, first half represents tens place, second half represents ones place
    for(int i=1;i<100;i++){
//Loop 99 times
        a+=t[i/10]+t[i%10+10]+" ";
//Add tens place and ones place to the string
    }return a+"C";
//Add numeral for 100 and return the string

```
> 0 votes

# Answer
# TeX, 354 bytes

```
\let~\let~\d\def~\a\advance~\b\divide~\x\expandafter~\f\ifnum{~~\newcount~\n~\i~\j~\k~\u~\v}~~\or\d\p#1{\ifcase#1C~2~L~5~X~2~V~5~I\fi}\d\q#1{\p{#1~}}\d\r{\j0
\v100\d\m{\d\w{\f\n<\v\else\p\j\a\n-\v\x\w\fi}\w\f\n>0\k\j\u\v\d\g{\a\k2\b\u\q\k}\g\f\q\k=2\g\fi\a\n\u\f\n<\v\a\n-\u\a\j2\b\v\q\j\else\p\k\fi\x\m\fi}\m}\i1\d\c{
\f\i<101 \n\i\r\a\i1 \x\c\fi}\c\bye

```

Some explanation: TeX provides a built-in command `\romannumeral` for converting numbers to Roman numerals. As the question doesn't allow to use built-in functions, the above code is a golfed version of the same algorithm Knuth's original TeX compiler uses for `\romannumeral` (see *TeX: The Program*, § 69, `print_roman_int`) re-implemented in TeX.

As he wants to leave the joy of puzzling out how this code works to the reader, Knuth refuses to give an explanation of this part of the code. So I'll follow suit and just give an ungolfed and slightly modified version, which is closer to the original than the above code:

```
\newcount\n
\newcount\j
\newcount\k
\newcount\u
\newcount\v

\def\chrnum#1{\ifcase#1m\or 2\or d\or 5\or c\or 2\or l\or 5\or x\or 2\or v\or 5\or i\fi}
\def\chrnumM#1{\chrnum{#1\or}}

\def\roman#1{%
    \n=#1\relax
    \j=0\relax
    \v=1000\relax
    \def\mainloop{%
        \def\while{%
            \ifnum\n<\v
            \else
                \chrnum\j
                \advance\n -\v
                \expandafter\while
            \fi
        }\while
        \ifnum\n>0\relax
            \k=\j \advance\k 2\relax
            \u=\v \divide\u \chrnumM\k
            \ifnum\chrnumM\k=2\relax
                \advance\k 2\relax
                \divide\u \chrnumM\k
            \fi
            \advance\n \u
            \ifnum\n<\v
                \advance\n -\u
                \advance\j 2\relax
                \divide\v \chrnumM\j
            \else
                \chrnum\k
            \fi
            \expandafter\mainloop
        \fi
    }\mainloop
}

\newcount\i \i=1
\def\countloop{%
    \ifnum\i<100\relax
        \roman\i\
        \advance\i 1
        \expandafter\countloop
    \fi
}\countloop
\bye

```
> 0 votes

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