title: Numbers of purity

text:
# Question
Title: Numbers of purity
Today we'll look at a sequence \\$a\\$, related to the Collatz function \\$f\\$:

$$f = \begin{cases} n/2 & \text{if } n \equiv 0 \text{ (mod }2) \\ 3n+1 & \text{if } n \equiv 1 \text{ (mod }2) \\ \end{cases}$$

We call a sequence of the form \\$z, f(z), f(f(z)), …\\$ a *Collatz sequence*.

The first number in *our* sequence, \\$a(1)\\$, is \\$0\\$. Under repeated application of \\$f\\$, it falls into a cycle \\$0\to0\to0\to\\:\cdots\\$

The smallest number we haven't seen yet is 1, making \\$a(2)=1\\$. Under repeated application of \\$f\\$, it falls into a cycle \\$1\to4\to2\to1\to\cdots\\$

Now we have seen the number \\$2\\$ in the cycle above, so the next smallest number is \\$a(3) = 3\\$, falling into the cycle \\$3\to10\to5\to16\to8\to4\to2\to1\to4\to\cdots\\$

In all above cycles we've seen \\$4\\$ and \\$5\\$ already, so the next number is \\$a(4) = 6\\$.

By now you should get the idea. \\$a(n)\\$ is the smallest number that was not part of any Collatz sequences for all \\$a(1), ..., a(n-1)\\$

Write a program or function that, given an positive integer \\$n\\$, returns \\$a(n)\\$. Shortest code in bytes wins.

---

Testcases:

```
1  -> 0
2  -> 1
3  -> 3
4  -> 6
5  -> 7
6  -> 9
7  -> 12
8  -> 15
9  -> 18
10 -> 19
50 -> 114

```

(This is OEIS sequence A061641.)

# Answer
> 5 votes
# Jelly, ~~20~~ 19 bytes

```
ḟ@JḢ×3‘$HḂ?ÐĿ;Ṛ
Ç¡Ṫ

```

Try it online! or verify all test cases.

### How it works

```
Ç¡Ṫ              Main link. No explicit arguments. Default argument: 0
 ¡               Read an integer n from STDIN and do the following n times.
Ç                  Call the helper link.
  Ṫ              Tail; extract the last element of the resulting array.

ḟ@JḢ×3‘$HḂ?ÐĿ;Ṛ  Helper link. Argument: A (array)

  J              Yield all 1-based indices of A, i.e., [1, ..., len(A)]. Since 0
                 belongs to A, there is at least one index that does belong to A.
ḟ@               Filter-false swapped; remove all indices that belong to A.
   Ḣ             Head; extract the first index (i) that hasn't been removed.
           ÐĿ    Call the quicklink to the left on i, then until the results are no
                 longer unique. Collect all unique results in an array.
         Ḃ?      If the last bit of the return value (r) is 1:
       $           Apply the monadic 3-link chain to the left to r.
    ×3‘              Yield 3r + 1.
        H        Else, halve r.
              Ṛ  Yield A, reversed.
             ;   Concatenate the results array with reversed A.

```

After **n** iterations, the value of **a(n + 1)** will be at the beginning of the array. Since we concatenate the new array with a reversed copy of the old one, this means that **a(n)** will be at the end.

# Answer
> 9 votes
## Haskell, ~~93~~ 92 bytes

```
c x|x<2=[[0,2]!!x]|odd x=x:c(3*x+1)|1<2=x:c(div x 2)
([y|y<-[-1..],all(/=y)$c=<<[0..y-1]]!!)

```

Usage example: `([y|y<-[-1..],all(/=y)$c=<<[0..y-1]]!!) 10` -\> `19`.

`c x` is the Collatz cycle for `x` with a little bit of cheating for `x == 1`. The main functions loops through all integers and keeps those that are not in `c x` for `x` in `[0..y-1]`. Pretty much a direct implementation of the definition. As Haskell index operator `!!` is 0-based, I start at `-1` to prepend a (otherwise useless) number to get the index fixed.

# Answer
> 4 votes
# MATL, ~~46~~ 40 bytes

```
Oiq:"tX>Q:yX-X<`t0)to?3*Q}2/]h5M1>]Pv]0)

```

**Try it online!**

### Explanation

The code has an outer `for` loop that generates `n` Collatz sequences, one in each iteration. Each sequence is generated by an inner `do...while` loop that computes new values and stores them in a *sequence vector* until a `1` or `0` is obtained. When we are done with the sequence, the vector is reversed and concatenated to a *global vector* that contains the values from all previous sequences. This vector may contain repeated values. The reversing of the sequence vector ensures that at the end of the outer loop the desired result (the starting value of the last sequence) will be at the end of the global vector.

**Pseudo-code**:

```
1  Initiallization
2  Generate n sequences (for loop):
3    Compute initial value for the k-th sequence
4    Generate the k-th sequence (do...while loop)
5      Starting from latest value so far, apply the Collatz algorithm to get next value
6      Update sequence with new value
7      Check if we are done. If so, exit loop. We have the k-th sequence
8    Update vector of seen values
9  We now have the n sequences. Get final result

```

**Commented code**:

```
O           % Push 0                                                          1
iq:         % Input n. Generate [1 2 ... n-1]                                 ·
"           % For loop: repeat n-1 times. Let k denote each iteration         2
  t         %   Duplicate vector of all seen values                           · 3
  X>Q       %   Take maximum, add 1                                           · ·
  :         %   Range from 1 to that: these are potential initial values      · ·
  y         %   Duplicate vector of all seen values                           · ·
  X-X<      %   Set difference, minimum: first value not seen                 · ·
  `         %   Do...while: this generates the k-th Collatz sequence          · 4
    t0)     %     Duplicate, push last value of the sequence so far           · · 5
    to      %     Duplicate, parity: 1 if odd, 0 if even                      · · ·
    ?       %     If odd                                                      · · ·
      3*Q   %       Times 3, plus 1                                           · · ·
    }       %     Else                                                        · · ·
      2/    %       Half                                                      · · ·
    ]       %     End if                                                      · · ·
    h       %     Concatenate new value of the sequence                       · · 6
    5M      %     Push the new value again                                    · · 7
    1>      %     Does it exceed 1? This is the loop condition                · · ·
  ]         %   End do...while. The loops ends when we have reached 0 or 1    · ·
  P         %   Reverse the k-th Collatz sequence                             · 8
  v         %   Concatenate with vector of previously seen values             · ·
]           % End for                                                         ·
0)          % Take last value. Implicitly display.                            9

```

# Answer
> 3 votes
# Python 2, ~~97~~ 96 bytes

```
r,=s={-1}
exec'n=r=min({r+1,r+2,r+3}-s)\nwhile{n}-s:s|={n};n=(n/2,3*n+1)[n%2]\n'*input()
print r

```

Takes advantage of the fact that all multiples of **3** are pure. Test it on Ideone.

### How it works

On the first line, `r,=s={-1}` sets **s = {-1}** (set) and **r = -1**.

Next we read an integer from STDIN, repeat a certain string that many times, then execute it. This is equivalent to the following Python code.

```
for _ in range(input())
    n=r=min({r+1,r+2,r+3}-s)
    while{n}-s:
        s|={n}
        n=(n/2,3*n+1)[n%2]

```

In each iteration, we start by finding the smallest member of **{r+1, r+2, r+3}** that does not belong to **s**. In the first iteration, this initializes **r** as **0**.

In all subsequent runs, **s** may (and will) contain some of **r+1**, **r+2** and **r+3**, but never all of them, since all multiples of **3** are pure. To verify this statement, observe that no multiple **m** of **3** is of the form **3k + 1**. That leaves **2m** as the only possible pre-image, which is also a multiple of **3**. Thus, **m** cannot appear in the Collatz sequence of any number that is less than **m**, and is therefore pure.

After identifying **r** and initializing **n**, we apply the Collatz function with `n=(n/2,3*n+1)[n%2]`, adding each intermediate value of **n** to the set **s** with `s|={n}`. Once we encounter a number **n** that is already in **s**, `{n}-s` will yield an empty set, and the iteration stops.

The last value of **r** is the desired element of the sequence.

# Answer
> 3 votes
# Brachylog, ~~70~~ ~~67~~ ~~65~~ ~~63~~ 62 bytes

```
,[]:?:1ih.
,0<=X=,?'eXg{t{:2/.*?|:3*+.}gB,(?.sB;?:Bc:2&.)}:?c.

```

Try it online!

# Answer
> 1 votes
# Pyth, 32 bytes

```
VtQ=+Y.u?%N2h*3N/N2Z)=Zf!}TYhZ)Z

```

Test suite.

# Answer
> 1 votes
# Java, 148 bytes

```
int a(int n){if(n<2)return 0;int f=a(n-1),b,i,c;do{f++;for(b=1,i=1;i<n;i++)for(c=i==2?4:a(i);c>1;c=c%2>0?c*3+1:c/2)b=c==f?0:b;}while(b<1);return f;}

```

Ideone it! (Warning: exponential complexity due to zero optimization.)

Converting it from a `do...while` loop to a `for` loop would be golfier, but I am having trouble doing so.

Golfing advice is welcome as usual.

# Answer
> 1 votes
## Perl6, 96

```
my @s;my $a=0;map {while ($a=@s[$a]=$a%2??3*$a+1!!$a/2)>1 {};while @s[++$a] {}},2..slurp;$a.say;

```

Based on the Perl 5 answer. A bit longer since Perl6 syntax is less forgiving than Perl5 syntax, but I'll settle with this for now.

# Answer
> 0 votes
# PHP, ~~233~~ 124 bytes

```
<?$n=$argv[1];for($c=[];$n--;){for($v=0;in_array($v,$c);)$v++;for(;$n&&!in_array($v,$c);$v=$v&1?3*$v+1:$v/2)$c[]=$v;}echo$v;

```

+4 for function:

```
function a($n){for($c=[];$n--;){for($v=0;in_array($v,$c);)$v++;for(;$n&&!in_array($v,$c);$v=$v&1?3*$v+1:$v/2)$c[]=$v;}return$v;}

```

# Answer
> 0 votes
# Perl 5 - 74 bytes

```
map{0 while 1<($a=$c[$a]=$a%2?$a*3+1:$a/2);0 while$c[++$a]}2..<>;print$a+0

```

This is a pretty straightforward solution. It repeatedly applies the Collatz function to the variable `$a` and stores in the array `@c` that the value has been seen, then after reaching 0 or 1 it increments `$a` until it's a number that hasn't been seen yet. This is repeated a number of times equal to the input minus 2, and finally the value of `$a` is outputted.

# Answer
> 0 votes
# Mathematica, 134 bytes

```
f=If[EvenQ@#,#/2,3#+1]&;a@n_:=(b={i=c=0};While[i++<n-1,c=First[Range@Max[#+1]~Complement~#&@b];b=b~Union~NestWhileList[f,c,f@#>c&]];c)

```

Easier-to-read format:

```
f = If[EvenQ@#, #/2, 3#+1] &;                        Collatz function
a@n_ := (                                            defines a(n)
  b = {i = c = 0};                                   initializations
                                                       b is the growing sequence
                                                       of cycles already completed
  While[i++ < n - 1,                                 computes a(n) recursively
    c = First[Range@Max[# + 1]~Complement~# & @b];   smallest number not in b
    b = b~Union~NestWhileList[f, c, f@# > c &]       apply f to c repeatedly
                                                       until the answer is smaller
                                                       than c, then add this new
                                                       cycle to b
    ]
  ; c)                                                 output final value of c

```

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


title: Text animation format Code Golf

text:
# Question
Title: Text animation format Code Golf
Working with old files from DOS, I found an ancient text animation format, that specify how much time each frame must be shown in the screen. It's very simple:

> F1W5F2W3

This example above indicates that Frame 1 must be shown for 5 units of time, and frame 2 for 3 units more. Now I want to convert it to:

> 1, 1, 1, 1, 1, 2, 2, 2

In the converted example below, frame 1 is repeated 5 times, and frame 2 three times.

**Rules:** The only allowed letters are *F* and *W* (and the lowercase counterparts, *f* and *w*). Numbers can go up to 255. Total input String with no more than 255 chars.

Other examples:

> Input: F10W3F11W3F10W3F12W3
>
> Output: 10, 10, 10, 11, 11, 11, 10, 10, 10, 12, 12, 12
>
> Input: f1w0f2w10
>
> Output: 2, 2, 2, 2, 2, 2, 2, 2, 2, 2

**Short code wins.**

**Edited - Accepted formats:** Any answer containing the output and ignoring spaces. Ex: 1, 1, 2, 2 or \[1,1,2,2\] or (1,1,2,2). But NOT 1 1 2 2 or \[1; 1; 2; 2\] or \[1 1 2 2\].

# Answer
> 2 votes
# Pyth, 13 bytes

```
smMcr7Xrz0Gd2

```

Test suite

This program uses one of my favorite tricks, `mM`, which maps the map function over a list. It is also uses a relic of Pyth's distant past, the `r7` function, which splits a string on whitespace and evaluates the contents, which just so happens to be absolutely perfect for this challenge. Here's how it works, and each intermediate state:

```
smMcr7Xrz0Gd2     f1W5F2w3

        z        "f1W5F2w3"       Implicit: z is the input.
       r 0       "f1w5f2w3"       Lowercase
      X   Gd     " 1 5 2 3"       Replace all lowercase letters (G) with spaces (d)
    r7           [1, 5, 2, 3]     Split on whitespace, eval each string.
   c        2    [[1, 5], [2, 3]] Split into groups of length 2
 mM                               Apply the map function to each pair
                 [[1, 1, 1, 1, 1], [2, 2, 2]]
s                                 Flatten
                 [1, 1, 1, 1, 1, 2, 2, 2]

```

# Answer
> 15 votes
## Python 3, 57 bytes

```
lambda s:eval(s.upper().translate({70:'+[',87:']*'})[1:])

```

Turns a string like

```
f1w0f2w10

```

into a expression like

```
[1]*0+[2]*10

```

that it evaluated as code. This is done by turning the string uppercase, turning each `f` into `+[` and each `w` into `]*`, and removing the initial `+`. Thanks to Dennis for saving 7 bytes in Python 3 by using translate with a dictionary.

# Answer
> 4 votes
# , 25 bytes

```
Óá¨ä«©á¨ä«©/²a±,
D@"hD

```

Try it online!

Here is a hexdump of the answer, which is encoded in latin1:

```
0000000: d3e1 a8e4 aba9 e1a8 e4ab a92f b261 b12c  .........../.a.,
0000010: 2016 1b0a 4440 2268 44                    ...D@"hD

```

Explanation:

`<C-v>` is byte `0x16` and `<esc>` is byte `0x1B`. Since they are both unprintable, I am using this notation to refer to them.

```
Óá¨ä«©á¨ä«©/²a±, <C-v><esc>

```

This is a compressed regex, that basically transforms the input into V code. Here's what the buffer looks like after running this regex:

```
3a10, <esc>3a11, <esc>3a10, <esc>3a12, <esc>

```

Here's how that works:

```
3           "3 times:
 a    <esc> "Append the following text:
  10,       " '10, '

```

Running this in V (or its parent, vim) would create:

```
10, 10, 10,

```

And then a similar command repeats for each element of the input.

---

So, after running this regex, we've got valid V code that will create the desired output. Thankfully, V can easily self-interpret, as long as the code is in a buffer. So, we run the following:

```
D      "Delete this line into the unnamed register
 @"    "Run the text in the unnamed register as V code

```

This is exactly what we want, but now the output has a trailing `,`. So:

```
h      "Move one character to the left. Now we are on the second to last character
 D     "Delete until the end of the current line

```

# Answer
> 3 votes
# Pyth, 18 bytes

```
r_McvM:z"\d+"1 2 9

```

Try it online. Test suite.

# Answer
> 3 votes
# MATL, 22 bytes

```
t58<*cU2eZ}Y"&D32','XE

```

Try it online!

### Explanation

```
t        % Implicitly input string, say 'F10W2F1W3'. Duplicate
58<      % Array that contains 1 for numeric chars, 0 otherwise: [0 1 1 0 1 0 1 0 1]
*        % Multiply element-wise. Converts chars to numeric code
c        % Cast to char. Gives the original string with letters replaced by char 0
U        % Interprets as a numeric array. So the string ' 10 2 4 3' (where spaces are
         % actually char 0) gives the array [10 2 4 3]
2e       % Reshapes into a 2-column array in column-major order: [10 4; 2 3]
Z}       % Split into rows: [10 4], [2 3]
Y"       % Run-length decoding: [10 10 4 4 4]. Implicitly display
&D       % Get string representation, in the format '[10 10 4 4]'
32','XE  % Replace spaces by commas

```

# Answer
> 2 votes
# JavaScript ES6, 68 bytes

```
s=>s.replace(/F(\d+)W(\d+)/gi,(z,a,b)=>(f=n=>n&&f(n-1,alert(a)))(b))

```

Hopefully an alert box counts as a frame as I couldn't think of another way to count as a 'frame'.

Slightly modified version to try in-browser

```
t=function(s){s.replace(/F(\d+)W(\d+)/gi,function(z,a,b){(f=function(n){return n&&f(n-1,alert(a))})(b)})}

// Demo
document.getElementById('go').onclick=function(){
  document.getElementById('output').innerHTML = t(document.getElementById('input').value)
};
```

```
<div style="padding-left:5px;padding-right:5px;"><h2 style="font-family:sans-serif">Text Animation</h2><div><div  style="background-color:#EFEFEF;border-radius:4px;padding:10px;"><input placeholder="Input here..." style="resize:none;border:1px solid #DDD;" id="input"><button id='go'>Run!</button></div><br><div style="background-color:#EFEFEF;border-radius:4px;padding:10px;"><span style="font-family:sans-serif;">Output:</span><br><pre id="output" style="background-color:#DEDEDE;padding:1em;border-radius:2px;overflow-x:auto;"></pre></div></div></div>
```

# Answer
> 2 votes
# Perl, 28 bytes

27 bytes of code, plus 1 for the `p` flag in `perl -pe '…'`:

```
s|f(\d+)w(\d+)|"$1
"x$2|gie

```

Output for `F10W3F11W3F10W3F12W3`:

```
10
10
10
11
11
11
10
10
10
12
12
12

```

# Answer
> 2 votes
# Jelly, 18 (strict), 8 (relaxed) bytes

**Strict input (any upper or lower) & strict output form of a flat list**

```
Œl“wẋ”yṣ”fj“ð;ø”VḊ

```

How?

```
Œl“wẋ”yṣ”fj“ð;ø”VḊ - takes an input, example: F11w7f13W5F17w3f19W2
Œl                 - to lower case            f11w7f13w5f17w3f19w2
  “wẋ”             - make string "wẋ"
      y            - map "w":"ẋ"              f11ẋ7f13ẋ5f17ẋ3f19ẋ2
        ”f         - make string "f"
       s           - split on "f"             [,11ẋ7,13ẋ5,17ẋ3,19ẋ2]
           “ð;ø”   - make string "ð;ø"
          j        - join with "ð;ø"s         ð;ø11ẋ7ð;ø13ẋ5ð;ø17ẋ3ð;ø19ẋ2
                V  - eval Jelly code...
each ẋ will repeat left right times, e.g. 17ẋ3 yields [17,17,17]
; will concatenate,
ð will treat the last chain as a dyadic link (the first will yield 0 as there is no link)
ø will treat the last chain as a niladic link
- so the example evaluates to:
[0, 11, 11, 11, 11, 11, 11, 11, 13, 13, 13, 13, 13, 17, 17, 17, 19, 19]
                 Ḋ - dequeue
[11, 11, 11, 11, 11, 11, 11, 13, 13, 13, 13, 13, 17, 17, 17, 19, 19]

```

Test it at **TryItOnline**

**Non-strict version: only lower input, returns smashed lists** \[a,a,...\]\[b,b,..\]\[...

```
“wẋfø”yv

```

How?

```
“wẋfø”yv - takes an input, example: f11w7f13w5f17w3f19w2
“wẋfø”   - make the string "wẋfø"
      y  - map "w":"ẋ";"f":"ø"      ø11ẋ7ø13ẋ5ø17ẋ3ø19ẋ2
       v - eval Jelly code left with input right (empty)
           this is a hack as V should work (I think)
           but by forcing no input the leading ø evaluates to nothing
evaluation is as above, but simply yields the ẋ lists in turn
- so the example evaluates to:
[11, 11, 11, 11, 11, 11, 11][13, 13, 13, 13, 13][17, 17, 17][19, 19]

```

Test it at **TryItOnline**

# Answer
> 2 votes
## Perl 6, 30 bytes

```
{m:g/\d+/.map:{|(+$^f xx$^w)}}

```

Anonymous function (aka: lambda) which uses a regex match to pull out all the numbers.

I then map over this list, pulling out 2 items at a time using self-declared positional variables `$^f` and `$^w`. Self-declared positional variables are assigned alphabetically, so `f` and `w` works nicely.

The regex match actually produces a list of `Match` objects, so I use the `+` prefix operator to coerce `f` to an `Int`.

The map creates a list of `f`, `w` times. This would normally create a List-of-Lists, so I use the `Slip` prefix operator `|`. A `Slip` is a `List` sub-type that flattens into an outer list, ie. It *slips* a list into the surrounding list, so in the end we get a flat list.

Usage example: `{m:g/\d+/.map:{|(+$^f xx $^w)}}('F1W5F2W3')` returns `(1, 1, 1, 1, 1, 2, 2, 2)`.

Here is the same function written as a full-blown named subroutine, with a more explicit definition.

```
sub f(Str $s) {
    ($s ~~ m:g/\d+/).map(-> $f, $w {
        slip( $f.Int xx $w )
    });
}

```

# Answer
> 2 votes
# 05AB1E, 16 bytes

```
l'f¡vy'w¡`FDïˆ}\

```

**Explanation**

```
                   # implicit input
l                  # convert to lower case: 'f1w5f2w3'
 'f¡               # split on "f": ['','1w5','2w3']
    v              # for each: ex '1w5'
     y'w¡          # split on "w": ['1','5']
         `         # flatten: '5','1'
          FDïˆ}    # N times do; duplicate, convert to int, push to global array: [1,1,1,1,1]
               \   # discard last copy
                   # implicitly print list at the end of the program

```

Try it online

# Answer
> 1 votes
# R, 78 bytes

```
m=strsplit(scan(,""),"[FWfw]")[[1]][-1];cat(rep(m[c(T,F)],m[c(F,T)]),sep=", ")

```

Credit for the `rep(m[c(T,F)],m[c(F,T)])` bit goes to @flodel. Usage:

```
> m=strsplit(scan(,""),"[FWfw]")[[1]][-1];cat(rep(m[c(T,F)],m[c(F,T)]),sep=", ")
1: F10W3F11W3F10W3F12W3
2:
Read 1 item
10, 10, 10, 11, 11, 11, 10, 10, 10, 12, 12, 12
> m=strsplit(scan(,""),"[FWfw]")[[1]][-1];cat(rep(m[c(T,F)],m[c(F,T)]),sep=", ")
1: f1w0f2w10
2:
Read 1 item
2, 2, 2, 2, 2, 2, 2, 2, 2, 2

```

# Answer
> 1 votes
# Pyth, 18 bytes

```
r9m_sMdcR\Wtcr1Q\F

```

If you don't need to allow for both upper and lower case, you can take out the `r1` for 16 bytes:

```
r9m_sMdcR\WtcQ\F

```

Try it online!

Explanation:

```
            c      split:
             r1Q    the uppercase of the input
                \F  on the letter "F"
           t       Remove the first result
                       The first "F" in the notation has nothing in front of it,
                       so this removes the empty string that prefaces everything
       cR\W        Split each of the results on "W"
  m_               Reverse each of the splits so that the "W" part is first (how many repetitions, then what is to be repeated)
    sMd            Cast everything within the splits to integers
r9                 Run length decode

```

# Answer
> 1 votes
## Perl, 32 bytes

**29 bytes code + 3 for `-n`.**

```
print"$1 "x$' while/(\d+)w/gi

```

### Usage

```
cat text-animation.pl
print"$1 "x$' while/(\d+)w/gi
perl -n text-animation.pl <<< 'F1W5F2W3'
1 1 1 1 1 2 2 2

```

## Perl, 29 bytes

**26 bytes code + 3 for `-n`.**

If no separator is required, this works:

```
print$1x$' while/(\d+)w/gi

```

# Answer
> 1 votes
## C#, ~~160~~ 155 bytes

```
s=>{var r="";int i=1,j;var t=s.Split('f','F');while(i<t.Length){var u=t[i++].Split('w','W');for(j=0;j++<int.Parse(u[1]);)r+=u[0]+",";}return r.Trim(',');};

```

# Answer
> 1 votes
# VBA, ~~162 bytes~~ 147 bytes

Okay, this is only for fun since it's kinda hard to beat esoteric programming languages but I don't care too much about winning the challenge. I do enjoy solving the challenge, though. Here is my *stab* for this challenge:

```
Function F(a):b=Split(Replace(a,"F","W"),"W"):For i=1To Ubound(b)/2:c="":For j=1To b(2*i):c=c & b(2*i-1) & ",":Next:d=d & c:Next:F=Left(d,Len(d)-1)

```

Ungolfed the code:

```
Function F(a)

b = Split(Replace(a, "F", "W"), "W")

    For i = 1 To UBound(b) / 2
        c = ""
        For j = 1 To b(2 * i)
            c = c & b(2 * i - 1) & ","
        Next
        d = d & c
    Next

F = Left(d, Len(d) - 1)

End Function

```

Explanation:

1. Substitute the letter **F** in the string input with **W** using VBA function Replace.
2. Split the string result with delimited letter **W** into a 1D array.
3. Looping through each element array where every odd element is replicated as many as its next element value (the nearest even element).
4. Concatenate each of looping output.
5. Truncate the output so that the trailing `,` is excluded.

---

Thanks Kevin Cruijssen for the advice.

# Answer
> 1 votes
## Haskell, 68 bytes

```
p""=[]
p(_:b)|[(c,_:d)]<-reads b,[(e,f)]<-reads d=(c+0<$[1..e])++p f

```

Usage example: `p "F1W5F2W3"` -\> `[1,1,1,1,1,2,2,2]`.

`reads` takes a string and reads something from the front of it and returns a singleton list with a pair of the something and the rest of the string. The type system knows from the usage `c+0` and `[1..e]` that the somethings must be numbers, so `reads` consumes all digits from the beginning of the string. The `_` in the patterns match the letters `F` and `W` that we don't need otherwise.

# Answer
> 1 votes
## Clojure, 86 bytes

```
(fn[a](mapcat #(repeat(read-string(last %))(first %))(partition 2 (re-seq #"\d+" a))))

```

Depending on requirements, I could also drop "cat" from "mapcat".

# Answer
> 0 votes
## PowerShell v2+, 67 bytes

```
($args[0]-replace'F','+,'-replace'W','*').trim('+')+'-join", "'|iex

```

Takes input `$args[0]` as a string, pumps it through two `-replace` statements to swap the `F` for a `+,` and the `W` for a `*`. Then `.trim`s the errant initial `+` before concatenating `-join` with a `,<space>`, and piping to `iex` to evaluate the resulting string into a new string. That's left on the pipeline, and output is implicit.

As an example, with input `F1W5F2W3`, after the `-replace`s, our string will be `+,1*5+,2*3`. After the `.trim`, it'll be `,1*5+,2*3`. That's concatenated with the `-join` statement, like `,1*5+,2*3-join", "`. The `iex` then evaluates that string by forming an array of `5` `1`s via the comma-operator, using array concatenation to add on an array of `3` `2`s, so we have an array like `(1,1,1,1,1,2,2,2)`, which is then fed into `-join` to put the comma-space between the elements.

Since `-replace` is by default case-insensitive, it handles lowercase as well.

### Test cases

```
PS C:\Tools\Scripts\golfing> .\text-animation-format.ps1 'F1W5F2W3'
1, 1, 1, 1, 1, 2, 2, 2

PS C:\Tools\Scripts\golfing> .\text-animation-format.ps1 'F10W3F11W3F10W3F12W3'
10, 10, 10, 11, 11, 11, 10, 10, 10, 12, 12, 12

PS C:\Tools\Scripts\golfing> .\text-animation-format.ps1 'f1w0f2w10'
2, 2, 2, 2, 2, 2, 2, 2, 2, 2

```

# Answer
> 0 votes
## Retina, 51 bytes

Might be able to be golfed further, I'm not super familiar with Retina.

```
i`F(\d+)W(\d+)
$1_$2$*n
(?<=(\d+).*?)n
$1,
\d+_|,$

```

The trailing linefeed is significant.

Try it online!

**Explanation:**

The code consists of three replacement stages.

```
i`F(\d+)W(\d+)
$1_$2$*n

```

This replaces each group of `FxWy` into `x_` followed by `n` repeated *y* times. For example, `F2W3` is replaced with `2_nnn`. `i`` makes the regex case insensitive.

```
(?<=(\d+).*?)n
$1,

```

This matches all the repeated `n`'s. and replaces each of them with the number closest before it, followed by a comma. Using our previous example of `F2W3`, `2_nnn` is replaced with `2_2,2,2,`.

```
\d+_|,$

```

This removes the final garbage left behind. It replaces the numbers directly followed by underscores, and the comma at the end of the line, with nothing. So `2_2,2,2,` becomes `2,2,2`, which is the desired output.

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


# Question
Title: Make a (somewhat) self-referential string
You want to make a string where the (**1-indexed**) character at index `n` is `n`. When `n` is less than 10, this is easy: `"123456789"`. When `n` is 12, for example, it becomes impossible, since numbers greater than 9 (in base 10) take up more than one character. We can compromise by dividing the string into two-character substrings: `"020406081012"`. Now the index of the end of each *substring* `n` is `n`.

This can be generalized for any `d`-digit number. Here's an explanation for the "0991021" part of the string for a three-digit number:

```
Index:     ... * 97  98  99*100 101 102*103 ...
               *           *           *
               *---+---+---*---+---+---*---+
Character: ... * 0 | 9 | 9 * 1 | 0 | 2 * 1 | ...
               *---+---+---*---+---+---*---+

```

If you haven't figured it out yet, you are to write a program/function that takes a string or integer and output its self-referential string as specified above. You can also output an array of single-digit numbers, chars, or single-character strings.

The given integer will always be positive and **divisible by its length** (e.g. 126 is divisible by 3; 4928 is divisible by 4). Your program should theoretically work for an arbitrarily large input, but you can assume it is smaller than your language's maximum integer and/or string length.

Some observations if you still don't get it: The length of the output will always be the input itself, and the numbers that appear in the output will be divisible by the number of digits in the input.

This is , so shortest answer in bytes wins.

## Test cases

```
1    => 1
9    => 123456789
10   => 0204060810
105  => 003006009012015018021024027030033036039042045048051054057060063066069072075078081084087090093096099102105
1004 => 00040008001200160020002400280032003600400044004800520056006000640068007200760080008400880092009601000104010801120116012001240128013201360140014401480152015601600164016801720176018001840188019201960200020402080212021602200224022802320236024002440248025202560260026402680272027602800284028802920296030003040308031203160320032403280332033603400344034803520356036003640368037203760380038403880392039604000404040804120416042004240428043204360440044404480452045604600464046804720476048004840488049204960500050405080512051605200524052805320536054005440548055205560560056405680572057605800584058805920596060006040608061206160620062406280632063606400644064806520656066006640668067206760680068406880692069607000704070807120716072007240728073207360740074407480752075607600764076807720776078007840788079207960800080408080812081608200824082808320836084008440848085208560860086408680872087608800884088808920896090009040908091209160920092409280932093609400944094809520956096009640968097209760980098409880992099610001004

```

# Answer
> 8 votes
# Jelly, 12 bytes

```
VRUmLDUz0ZFU

```

I/O is in form of digit arrays. Try it online! or verify all test cases.

### How it works

```
VRUmLDUz0ZFU  Main link. Argument: A (digit array)

V             Eval; turn the digits in A into an integer n.
 R            Range; yield [1, ..., n].
  U           Upend; reverse to yield [n, ..., 1].
    L         Yield the length (l) of A.
   m          Modular; keep every l-th integer in A.
     D        Decimal; convert each kept integer into the array of its digits.
      U       Upend; reverse the digits of each integer.
       z0     Zip/transpose with fill value 0.
         Z    Zip again.
              This right-pads all digit arrays with zeroes.
          F   Flatten the resulting 2D array.
           U  Upend/reverse it.

```

# Answer
> 12 votes
# C, 64 bytes

```
l,i;main(n){for(scanf("%d%n",&n,&l);i<n;)printf("%0*d",l,i+=l);}

```

Takes a single integer as input on stdin.

# Answer
> 9 votes
## JavaScript (ES6), 83 bytes

```
n=>[...Array(n/(l=`${n}`.length))].map((_,i)=>`${+`1e${l}`+l*++i}`.slice(1)).join``

```

Yes, that's a nested template string. 79 bytes in ES7:

```
n=>[...Array(n/(l=`${n}`.length))].map((_,i)=>`${10**l+l*++i}`.slice(1)).join``

```

# Answer
> 7 votes
# MATL, ~~15~~ 14 bytes

```
VntG3$:10YA!1e

```

**Try it online!**

```
V        % Implicitly input number, n. Convert to string
n        % Length of that string, s
t        % Duplicate s
G        % Push n again
3$:      % 3-input range (s,s,n): generates [s, 2*s, ... ] up to <=n
10YA     % Convert each number to base 10. This gives a 2D array of char, with each
         % number on a row, left-padded with zeros if needed
!1e      % Reshape into a string, reading in row-major order. Implicitly display

```

# Answer
> 6 votes
# 05AB1E, 15 bytes

Code:

```
LD¹gÖÏvy0¹g×0ñ?

```

Explanation:

```
L                # Get the array [1, ..., input].
 D               # Duplicate this array.
  ¹g             # Get the length of the first input.
    Ö            # Check if it's divisible by input length.
     Ï           # Keep those elements.
      vy         # For each...
         ¹g      # Get the length of the first input.
        0  ×     # String multiply that with "0".
            0ñ   # Merge with the number.
              ?  # Pop and print without a newline.

```

The merging is done like this:

From these:

```
000
 12

```

It results into this:

```
012

```

Uses the **CP-1252** encoding. Try it online!.

# Answer
> 6 votes
# Python 2, ~~78~~ ~~70~~ ~~68~~ ~~64~~ 63 bytes

Actually basing on the idea of Destructible Watermelon makes it even smaller (using `input` is even better)(filling the string backward saves 4 bytes)(no `()` at `while`):

```
n,s=input(),''
l=len(`n`)
while n:s=`n`.zfill(l)+s;n-=l
print s

```

Here is the old 70 byte approach (Saving 8 bytes by using backquotes instead of `str` and dropping the square brackets around generator thanks to Dennis):

```
def f(n):l=len(`n`);print"".join(`x`.zfill(l)for x in range(l,n+l,l))

```

# Answer
> 5 votes
# Python 2, 63 bytes

```
def f(n):l=len(`n`);print'%%0%dd'%l*(n/l)%tuple(range(l,n+1,l))

```

Test it on Ideone.

# Answer
> 4 votes
# JavaScript (ES6), 66

Recursive, input `n` as a string (not a number) and limiting the output string size to 2GB (that is above the string limit of most javascript engines)

```
f=(n,i=1e9,s='',l=n.length)=>s[n-1]?s:f(n,i+=l,s+(i+'').slice(-l))

```

**Test**

```
f=(n,i=1e9,s='',l=n.length)=>s[n-1]?s:f(n,i+=l,s+(i+'').slice(-l))

function test() {
  var v=I.value;
  Alert.textContent=v % v.length ?
    'Warning: input value is not divisible by its string length':'\n';
  Result.textContent=f(v);
}

test()
```

```
<input type=number id=I value=105 oninput='test()' max=500000>
<pre id=Alert></pre>
<pre id=Result></pre>
```

# Answer
> 4 votes
# R, ~~66~~ ~~64~~ 62 bytes

edit:

`x=nchar(n<-scan());paste0(str_pad(1:(n/x)*x,x,,0),collapse="")`

first golf attempt...

# Answer
> 3 votes
# 2sable, 13 bytes

Code:

```
g©÷F®N>*0®×0ñ

```

Uses the **CP-1252** encoding.

# Answer
> 3 votes
# Python ~~3~~ 2, ~~79~~ ~~74~~ ~~69~~ ~~65~~ ~~68~~ 67 bytes

Thanks Dennis!

```
def f(n):i=l=len(`n`);s='';exec n/l*"s+=`i`.zfill(l);i+=l;";print s

```

byte count increase from bad output method

# Answer
> 3 votes
# Bash, ~~31~~ 22 bytes

```
seq -ws '' ${#1}{,} $1

```

Test it on Ideone.

*Thanks to @izabera for golfing off 6 bytes!*

# Answer
> 3 votes
# Brachylog, ~~53~~ ~~45~~ ~~42~~ ~~37~~ 28 bytes

```
~~lB,?ybeN:B%0,N:ef:{,"0":"9"y:?m.}acAl:Br-:"0"rjb:Acw\~~
~~lB,?ybeN:B%0,10:B^:N+:ef:{,"0":"9"y:?m.}acbw\~~
~~lB,?ybeN:B%0,10:B^:N+:ef:{:16+:@Prm.}acbw\~~
~~lB,?ybeN:B%0,10:B^:N+:efbe:16+:@Prmw\~~
lB,?ybeN:B%0,10:B^:N+:efbew\

```

Try it online!

# Answer
> 3 votes
# Ruby, ~~52~~ 48 + `n` flag = 49 bytes

```
((l= ~/$/)..$_.to_i).step(l){|j|$><<"%0#{l}d"%j}

```

# Answer
> 2 votes
# Javascript - 76

```
n=>eval('c="";for(a=b=(""+n).length;a<=n;a+=b)c+=`${+`1e${b}`+a}`.slice(1)')

```

or **71** if allowing for string arguments:

```
n=>eval('c="";for(a=b=n.length;a<=n;a+=b)c+=`${+`1e${b}`+a}`.slice(1)')

```

Thanks to @user81655!

Ungolfed:

```
function x(n)
{
   c = "", a = b = (""+n).length;
   while(a<=n)
   {
       c=c+"0".repeat(b-(""+a).length)+a
       a+=b;
   }
   return c;
}

```

much place for improvement, but i'm tired right now

# Answer
> 2 votes
# zsh, 28 bytes

```
printf %0$#1d {$#1..$1..$#1}

```

# zsh + seq, ~~21~~20 bytes

This is pretty much the same answer as Dennis but in 20 bytes because zsh

```
seq -ws '' $#1{,} $1

```

# Answer
> 2 votes
# R, ~~149~~ ~~142~~ 138 bytes

```
x=rep(0,n);a=strtoi;b=nchar;for(i in 1:(n=scan()))if(!i%%b(a(n)))x[i:(i-b(a(i))+1)]=strsplit(paste(a(i)),"")[[1]][b(a(i)):1];cat(x,sep="")

```

Leaving `nchar` in the code gives a program with the same number of bytes than replacing it with `b`, but having random letters wandering around in the code makes it more... *mysterious*

**Ungolfed :**
Each `nchar(strtoi(something))` permits to compute the number of numerals in a given number.

```
n=scan()   #Takes the integer
x=rep(0,n) #Creates a vector of the length of this integer, full of zeros

for(i in 1:n)
    if(!i%%b(strtoi(n)))         #Divisibility check
        x[i:(i-nchar(as.integer(i))+1)]=strsplit(paste(a(i)),"")[[1]][nchar(as.integer(i)):1];
        #This part replace the zeros from a given position (the index that is divisible) by the numerals of this position, backward.

cat(x,sep="")

```

The `strsplit` function outputs a list of vectors containing the splitten elements. That's why you have to reach the `1`st element of the list, and then the `i`th element of the vector, writing `strsplit[[1]][i]`

# Answer
> 2 votes
# Haskell, 51 bytes

```
f n|k<-length$show n=[k,2*k..n]>>=tail.show.(+10^k)

```

# Answer
> 2 votes
## Perl, 40 bytes

**39 bytes code + 1 for `-n`.**

```
$}=y///c;printf"%0$}d",$i+=$}while$i<$_

```

### Usage

```
echo -n 9 | perl -ne '$}=y///c;printf"%0$}d",$i+=$}while$i<$_'
123456789
echo -n 10 | perl -ne '$}=y///c;printf"%0$}d",$i+=$}while$i<$_'
0204060810
echo -n 102 | perl -ne '$}=y///c;printf"%0$}d",$i+=$}while$i<$_'
003006009012015018021024027030033036039042045048051054057060063066069072075078081084087090093096099102
echo -n 1000 | perl -ne '$}=y///c;printf"%0$}d",$i+=$}while$i<$_'
0004000800120016002000240028003200360040004400480052005600600064006800720076008000840088009200960100010401080112011601200124012801320136014001440148015201560160016401680172017601800184018801920196020002040208021202160220022402280232023602400244024802520256026002640268027202760280028402880292029603000304030803120316032003240328033203360340034403480352035603600364036803720376038003840388039203960400040404080412041604200424042804320436044004440448045204560460046404680472047604800484048804920496050005040508051205160520052405280532053605400544054805520556056005640568057205760580058405880592059606000604060806120616062006240628063206360640064406480652065606600664066806720676068006840688069206960700070407080712071607200724072807320736074007440748075207560760076407680772077607800784078807920796080008040808081208160820082408280832083608400844084808520856086008640868087208760880088408880892089609000904090809120916092009240928093209360940094409480952095609600964096809720976098009840988099209961000

```

# Answer
> 2 votes
# k4, 27

```
{,/"0"^(-c)$$c*1+!_x%c:#$x}

```

Not really golfed at all, just a straight-forward implementation of the spec.

```
                        $ / string
                       #  / count
                     c:   / assign to c
                   x%     / divide x by
                  _       / floor
                 !        / range (0-based)
               1+         / convert to 1-based
             c*           / multiply by count
            $             / string
       (-c)               / negative count
           $              / pad (negative width -> right-aligned)
   "0"^                   / fill blanks with zeros
 ,/                       / raze (list of string -> string)

```

# Answer
> 1 votes
# SQF \- 164

Using the function-as-a-file format:

```
#define Q String""
l=(ceil log _this)+1;s='';for[{a=l},{a<=_this},{a=a+l}]do{c=([a]joinQ)splitQ;reverse c;c=(c+['0'])select[0,l];reverse c;s=format[s+'%1',c joinQ]}

```

Call as `INTEGER call NAME_OF_COMPILED_FUNCTION`

# Answer
> 1 votes
# PowerShell, 77 bytes

```
$x="$($args[0])";$l=$x.Length;-join(1..($x/$l)|%{"$($_*$l)".PadLeft($l,'0')})

```

Uses string interpolation to shorten string casts. The parts before the second semicolon shorten the names of reused things. Then, every integer up to the input - and only those that are multiples of the input's length - are padded to be as long as the input string and finally joined into one.

# Answer
> 1 votes
## Actually, 30 bytes

```
;╝R╛$l;)*@#"%0{}d"f╗`#╜%`MΣ╛@H

```

Try it online!

I'm not happy with the length of this code, but I'm not sure that it can be made much shorter (if at all).

Explanation:

```
;╝R╛$l;)*@#"%0{}d"f╗`#╜%`MΣ╛@H
;╝                              duplicate input, push a copy to reg1
  R                             range(1, input+1)
   ╛$l                          push input from reg1, stringify, length
      ;)                        duplicate and move copy to bottom of stack
        *                       multiply range by length of input
         @#                     swap range with length, make length a 1-element list
           "%0{}d"f             "%0{}d".format(length) (old-style Python format string for zero-padding integers to length of input)
                   ╗            save format string in reg0
                    `#╜%`M      for each value in range:
                     #            make it a 1-element list
                      ╜%          format using the format string
                          Σ     concatenate
                           ╛@H  take only the first (input) characters in the resulting string

```

# Answer
> 0 votes
## PHP, 83 78 bytes

```
<?$a=$argv[1];$i=$y=strlen($a);while($y<=$a){printf('%0'.$i.'d', $y);$y+=$i;}

```

Tips are more then welcome. Manage to golf it myself by one byte by changing it from a for loop to a while loop.

This code assumes that this is being execute from the command line and that $argv\[1\] is the int.

## Thanks to:

@AlexGittemeier His suggestion (see comments) golfed this by 5 bytes to 78 bytes.

# Answer
> 0 votes
# CJam, 19 bytes

```
q_,:V\i,%{V+sV0e[}/

```

Try it online. No one has posted in CJam yet, so this is the script I used for the test cases.

## Explanation

```
q_,:V  e# Store the length of the input as V
\i,    e# Push the range from 0 to the input
%      e# Keep only every V'th number in the array
{      e# Do this for each number:
  V+   e# Add V to get the right number of leading zeroes
  s    e# Convert to string for left padding
  V    e# Push V, the length to bring each string to, and...
  0    e# The character to add to the left
  e[   e# Left pad
}/

```

# Answer
> 0 votes
## Perl 6, ~~69~~ ~~59~~ 46 bytes

```
{my \a=.chars;(a,2*a...$_).fmt("%0"~a~"s","")}

```

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


title: My triangle needs more nodes

text:
# Question
Title: My triangle needs more nodes
Consider the standard equilateral triangle, with nodes labeled using barycentric coordinates:

We can turn this 3 node triangle into a 6 node triangle by adding a new line of 3 vertices (one more than was present on a side of the original 3 node triangle), remove any internal edges (but **not** internal nodes) and re-normalize the coordinates:

Repeating the process to go from a 6 node triangle to a 10 node triangle, add a line of 4 vertices (again, one more than was present on a side of the original 6 node triangle), remove any internal edges (but **not** internal nodes) and re-normalize the coordinates:

This process can be repeated indefinitely. The goal of this challenge is given an integer `N` representing how many times this process has been performed, output all the nodes for the associated triangle in barycentric coordinates.

# Input

Your program/function should take as input a single non-negative integer `N` representing how many times this process has been applied. Note that for `N=0`, you should output the original triangle with 3 nodes.

The input may come from any source (function parameter, stdio, etc.).

# Output

Your program/function should output all the nodes in normalized barycentric coordinates. The order of the nodes does not matter. A number can be specified as a fraction (fraction reduction not required) or a floating point number. You may also output "scaled" vectors to specify a node. For example, all 3 of the following outputs are equivalent and allowed:

```
0.5,0.5,0

1/2,2/4,0

[1,1,0]/2

```

If using floating point output, your output should be accurate to within 1%. The output may be to any sink desired (stdio, return value, return parameter, etc.). Note that even though the barycentric coordinates are uniquely determined by only 2 numbers per node, you should output all 3 numbers per node.

# Examples

Example cases are formatted as:

```
N
x0,y0,z0
x1,y1,z1
x2,y2,z2
...

```

where the first line is the input `N`, and all following lines form a node `x,y,z` which should be in the output exactly once. All numbers are given as approximate floating point numbers.

```
0
1,0,0
0,1,0
0,0,1

1
1,0,0
0,1,0
0,0,1
0.5,0,0.5
0.5,0.5,0
0,0.5,0.5

2
1,0,0
0,1,0
0,0,1
0.667,0,0.333
0.667,0.333,0
0.333,0,0.667
0.333,0.333,0.333
0.333,0.667,0
0,0.333,0.667
0,0.667,0.333

3
1,0,0
0.75,0,0.25
0.75,0.25,0
0.5,0,0.5
0.5,0.25,0.25
0.5,0.5,0
0.25,0,0.75
0.25,0.25,0.5
0.25,0.5,0.25
0.25,0.75,0
0,0,1
0,0.25,0.75
0,0.5,0.5
0,0.75,0.25
0,1,0

```

# Scoring

This is code golf; shortest code in bytes wins. Standard loopholes apply. You may use any built-ins desired.

# Answer
## CJam (22 bytes)

```
{):X),3m*{:+X=},Xdff/}

```

This is an anonymous block (function) which takes `N` on the stack and leaves an array of arrays of doubles on the stack. Online demo

### Dissection

```
{         e# Define a block
  ):X     e# Let X=N+1 be the number of segments per edge
  ),3m*   e# Generate all triplets of integers in [0, X] (inclusive)
  {:+X=}, e# Filter to those triplets which sum to X
  Xdff/   e# Normalise
}

```
> 7 votes

# Answer
# Haskell, 53 bytes

```
f n|m<-n+1=[map(/m)[x,y,m-x-y]|x<-[0..m],y<-[0..m-x]]

```
> 6 votes

# Answer
# Python 3, 87 bytes

This is actually supposed to be a comment to the solution by TheBikingViking but I don't have enough reputation for comments.

One can save a few bytes by only iterating over the variables `i,j` and using the fact that with the third one they add up to `n+1`.

```
def f(n):d=n+1;r=range(n+2);print([[i/d,j/d,(d-i-j)/d]for i in r for j in r if d>=i+j])

```
> 5 votes

# Answer
# 05AB1E, 10 bytes

```
ÌL<¤/3ãDOÏ

```

**Explanation**

```
ÌL<          # range(1,n+2)-1
   ¤/        # divide all by last element (n+1)
     3ã      # cartesian product repeat (generate all possible triples)
       DO    # make a copy and sum the triples
         Ï   # keep triples with sum 1

```

Try it online
> 4 votes

# Answer
## Mathematica,  ~~44~~  43 bytes

```
Select[Range[0,x=#+1]~Tuples~3/x,Tr@#==1&]&

```

This is an unnamed function taking a single integer argument. Output is a list of lists of exact (reduced) fractions.

Generates all 3-tuples of multiples of `1/(N+1)` between 0 and 1, inclusive, and then selects those whose sum is 1 (as required by barycentric coordinates).
> 3 votes

# Answer
# MATL, 17 bytes

```
2+:qGQ/3Z^t!s1=Y)

```

Try it online!

### Explanation

The approach is the same as in other answers:

1. Generate the array `[0, 1/(n+1), 2/(n+1), ..., 1]`, where `n` is the input;
2. Generate all 3-tuples with those values;
3. Keep only those whose sum is `1`.

More specifically:

```
2+     % Take input and add 2: produces n+2
:q     % Range [0 1 ... n+1]
GQ/    % Divide by n+1 element-wise: gives [0, 1/(n+1), 2/(n+1)..., 1]
3Z^    % Cartesian power with exponent 3. Gives (n+1)^3 × 3 array. Each row is a 3-tuple
t      % Duplicate
!s     % Sum of each row
1=     % Logical index of entries that equal 1
Y)     % Use that index to select rows of the 2D array of 3-tuples

```
> 3 votes

# Answer
## Jellyfish, ~~37~~ 33 bytes

*Thanks to Zgarb for saving 4 bytes.*

```
p
*%
# S
`
=E   S
`/
1+r#>>i
   3

```

Try it online!

Like my Mathematica and Peter's CJam answers, this generates a set of candidate tuples and then selects only those that sum to 1. I'm not entirely happy with the layout yet, and I wonder whether I can save some bytes with hooks or forks, but I'll have to look into that later.
> 1 votes

# Answer
# Perl 6: ~~50~~ 40 bytes

```
{grep *.sum==1,[X] (0,1/($_+1)...1)xx 3}

```

Returns a sequence of 3-element lists of (exact) rational numbers.

Explanation:

* `$_`
Implicitly declared parameter of the lambda.
* `0, 1/($_ + 1) ... 1`
Uses the sequence operator `...` to construct the arithmetic sequence that corresponds to the possible coordinate values.
* `[X] EXPR xx 3`
Takes the Cartesian product of three copies of EXPR, i.e. generates all possible 3-tuples.
* `grep *.sum == 1, EXPR`
Filter tuples with a sum of 1.
> 1 votes

# Answer
# Ruby, 62

I'd be surprised if this can't be improved on:

```
->x{0.step(1,i=1.0/(x+1)){|a|0.step(1-a,i){|b|p [a,b,1-a-b]}}}

```

Taking the advice latent in the puzzle, this calculates the second node options based on the first, and the third node by subtracting the first two.
> 1 votes

# Answer
# Brachylog, 24 bytes

```
+:1f
yg:2j:eaL+?/g:Lz:*a

```

Try it online!
> 1 votes

# Answer
## JavaScript (Firefox 30-57), ~~88~~ 81 bytes

```
n=>[for(x of a=[...Array(++n+1).keys()])for(y of a)if(x+y<=n)[x/n,y/n,(n-x-y)/n]]

```

Returns an array of arrays of floating-point numbers. Edit: Saved 7 bytes by computing the third coordinate directly. I tried eliminating the `if` by calculating the range of `y` directly but it cost an extra byte:

```
n=>[for(x of a=[...Array(++n+1).keys()])for(y of a.slice(x))[x/n,(y-x)/n,(n-y)/n]]

```
> 0 votes

# Answer
# Python 3, 106 bytes

```
def f(n):r=range(n+2);print([x for x in[[i/-~n,j/-~n,k/-~n]for i in r for j in r for k in r]if sum(x)==1])

```

A function they takes input via argument and prints a list of lists of floats to STDOUT.

Python is not good at Cartesian products...

**How it works**

```
def f(n):                         Function with input iteration number n
r=range(n+2)                      Define r as the range [0, n+1]
for i in r for j in r for k in r  Length 3 Cartesian product of r
[i/-~n,j/-~n,k/-~n]               Divide each element of each list in the product
                                  by n+1
[x for x in ... if sum(x)==1]     Filter by summation to 1
print(...)                           Print to STDOUT

```

Try it on Ideone
> 0 votes

# Answer
# Actually, 15 bytes

This uses an algorithm similar to the one in TheBikingViking's Python answer. Golfing suggestions welcome. Try it online!

```
u;ur♀/3@∙`Σ1=`░

```

**Ungolfed:**

```
u;                Increment implicit input and duplicate.
  ur              Range [0..n+1]
    ♀/            Divide everything in range by (input+1).
      3@∙         Take the Cartesian product of 3 copies of [range divided by input+1]
         `Σ1=`    Create function that takes a list checks if sum(list) == 1.
              ░   Push values of the Cartesian product where f returns a truthy value.

```
> 0 votes

# Answer
# Ruby, ~~77~~ 74 bytes

Another answer using the algorithm in TheBikingViking's Python answer. Golfing suggestions welcome.

```
->n{a=[*0.step(1,i=1.0/(n+1))];a.product(a,a).reject{|j|j.reduce(&:+)!=1}}

```

Another 74-byte algorithm based on Not that Charles's Ruby answer.

```
->x{y=x+1;z=1.0/y;[*0..y].map{|a|[*0..y-a].map{|b|p [a*z,b*z,(y-a-b)*z]}}}

```
> 0 votes

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


title: The Permutation Pigeon-hole Principle

text:
# Question
Title: The Permutation Pigeon-hole Principle
In the game of sudoku, many players like to "pencil in" possible numbers that can go in each square:

The above row can be represented as an array:

```
[[1,2,9], [6], [5], [7], [1,2,9], [1,2,9], [3], [1,2,4], [8]]

```

Now, notice that there is only 1 place where a `4` can go. This effectively lets us simplify the above list to:

```
[[1,2,9], [6], [5], [7], [1,2,9], [1,2,9], [3], [4], [8]]

```

**The goal of this challenge is to take a list of possible numbers in a permutation, and deduce which possibilities can be eliminated**.

As another example, lets say you have the following array of possibilities:

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

```

The last two places *must* be filled with 1 and 2. Therefore, we can remove those possibilities from the first two elements in the array:

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

```

As another example:

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

```

Its *impossible* to construct a permutation from the above possibilities, as there's only 1 location for both `1` and `3`, and you would want to return an empty array.

**You need to input a list of possibilities and output the remaining possibilities after the maximum number of possibilities have been eliminated.**

* If a particular array is impossible, you either need to return an empty array, or an array where one of the subarrays is empty.
* You may assume that the array will be well-formed, and have at least 1 element.
* Given an array of size `N`, you can assume the numbers in the subarray will always be in the range `[0:N)`, and that `N <= 10`
* You may not assume that every number from `0` to `N-1` will be present
* You may assume that numbers within a single subarray are unique.
* If a subarray contains only a single possibility, you can either represent the possibility in an array or by itself. `[[1],[2],[0]]`, `[1,2,0]`, `[[1,2],0,[1,2]]` are all valid.
* You may accept the array either in a reasonable string format or in list/array format.
* Subarrays can be in any order.
* Instead of dealing with ragged arrays, you can pad empty places with `-1`.

# Test cases

```
[[0]]                                         -> [[0]]
[[1],[0]]                                     -> [[1],[0]]
[[1],[1]]                                     -> []
[[1],[0,1]]                                   -> [[1],[0]]
[[0,1,2],[1,2],[1,2]]                         -> [[0],[1,2],[1,2]]
[[0,1],[1,2],[0,2]]                           -> [[0,1],[1,2],[0,2]]
[[2,1],[1,2],[1,2]]                           -> []
[[0,3],[2,1],[3,0],[3,2]]                     -> [[0,3],[1],[0,3],[2]]
[[0,1],[0,1],[2,3],[2,3,0]]                   -> [[0,1],[0,1],[2,3],[2,3]]
[[0,1],[0,3],[3,2],[0]]                       -> [[1],[3],[2],[0]]
[[3,5,2],[0,2,4],[4,0],[0,1,3,5],[2,1],[2,4]] -> [[3,5],[0,2,4],[4,0],[3,5],[1],[2,4]]
[[6,9,8,4],[4,5],[5,3,6],[3,8,6,1,4],[3,1,9,6],[3,7,0,2,4,5],[9,5,6,8],[6,5,8,1,3,7],[8],[8,0,6,2,5,6,3]] -> [[6,9,4],[4,5],[5,3,6],[3,6,1,4],[3,1,9,6],[0,2],[9,5,6],[7],[8],[0,2]]
[[3,5,0],[5,7],[5,1,2],[1,3,0],[5,3],[5,0],[5,3,7,8,0,6],[7,5,0,1,8],[1,0,8],[0,6]] -> []
[[9,0,2,3,7],[0,7,6,5],[6,9,4,7],[9,1,2,3,0,5],[2,8,5,7,4,6],[6,5,7,1],[5,9,4],[5,9,3,8,1],[5,0,6,4],[0,7,2,1,3,4,8]] -> [[9,0,2,3,7],[0,7,6,5],[6,9,4,7],[9,1,2,3,0,5],[2,8,5,7,4,6],[6,5,7,1],[5,9,4],[5,9,3,8,1],[5,0,6,4],[0,7,2,1,3,4,8]]
[[2,6,0],[0,4,3],[0,6,2],[0,7],[0,9,2,3,6,1,4],[1,7,2],[2,7,8],[8,6,7],[6,5,2,8,0],[5,8,1,4]] -> [[2,6,0],[3],[0,6,2],[0,7],[9],[1],[2,7,8],[8,6,7],[5],[4]]
[[8],[8,0,6,5,7,2,4,1],[8,6,9,3,5,0,7],[3,9,1,0],[9],[9,2,6],[2,8,3],[3,1,6,8,2],[6],[6,4,5,3,0,7]] -> [[8],[5,7,4],[5,7],[0],[9],[2],[3],[1],[6],[4,5,7]]
[[8,1,0],[5,8,7,6,2,0],[6,8,2],[2,4,0,9],[4,1,7,3,6,8],[8,1],[8,0,3],[0,8,2],[0,8,3],[1,8,0]] -> []

```

This is a so make your answers as short as possible!

# Answer
> 17 votes
# Brachylog, 21 bytes

```
:1fz:da|,[]
:2a#d
:Am

```

Try it online!

Try it online!

## Predicate 0 (main predicate)

```
:1fz:da|,[]
:1f            Find all solutions of Predicate 1 using Input as Input.
   z           Transpose
    :da        Deduplicate each.
       |,[]    If there is no solution, return [] instead.

```

## Predicate 1 (auxiliary predicate 1)

```
:2a#d
:2a     Each element of Output satisfies Predicate 2 with each element of Input as Input
   #d   Each element is different

```

## Predicate 2 (auxiliary predicate 2)

```
:Am     Output is member of Input

```

# Answer
> 8 votes
# Jelly, 10 bytes

```
Œp⁼Q$ÐfZQ€

```

Try it online!

```
Œp⁼Q$ÐfZQ€   Main chain, argument: z

Œp           Cartesian product
  ⁼Q$Ðf      Filter for those that remain unchanged when uniquified
       Z     Transpose
        Q€   Uniquify each subarray

```

# Answer
> 7 votes
# Pyth, 11 bytes

```
{MC{I#.nM*F

```

Try it online!

```
{MC{I#.nM*F
         *F  reduce by Cartesian product
             produces nested arrays
      .nM    flatten each
   {I#       filter for invariant under deduplication
  C          transpose
{M           deduplicate each

```

# Answer
> 6 votes
## Haskell, 100 bytes

```
import Data.List
p z=map nub$transpose$filter(and.(flip$zipWith elem)z)$permutations[0..length z-1]

```

# Answer
> 2 votes
# Actually, 27 bytes

```
Rd╗R`╜∙"♂i"£M╗`MX╜`;╔=`░┬♂╔

```

Try it online!

# Answer
> 2 votes
# Python 3, ~~101~~ 99 bytes

*Thanks to @TLW for -2 bytes*

```
from itertools import*
lambda x:list(map(set,zip(*[i for i in product(*x)if len(i)==len(set(i))])))

```

An anonymous function that takes input via argument of a list of lists and returns a list of sets.

**How it works**

```
from itertools import*        Import Python's library for iterator generation
lambda x                      Anonymous function with input possibilities x as a
                              list of lists
...for i in product(*x)...    For i in the Cartesian product of x, ie all candidate
                              arrangements:
[...if len(i)==len(set(i))]    Filter into list by non-duplicity (set removes
                               duplicates, so there are no duplicates if the length
                               of i is the same as the length of the set of
                               the elements of i)
zip(*...)                     Unpack and take the transpose, leaving the modified
                              possibilities with duplicates
map(set,...)                  Remove duplicates
:list(...)                    Return the modified possibilities as a list of sets

```

Try it on Ideone

# Answer
> 2 votes
# Mathematica, 46 bytes

```
Union/@Thread@Select[Tuples@#,DuplicateFreeQ]&

```

# Answer
> 0 votes
# PHP, ~~245~~ 231 bytes

~~131~~ 117 for the cartesian product function, 114 for the other stuff

```
function c($a){if ($a){if($u=array_pop($a))foreach(c($a)as$p)foreach($u as$v)yield $p+[count($p)=>$v];}else yield[];}
function p($a){foreach(c($a)as$i)if(max(array_count_values($i))<2)foreach($i as$k=>$v)$r[$k][$v]=$v;return$r?:[];}

```

I ran into memory issues on some of the test cases, with a recursive function for the cartesian product. Worked better with this generator class and `function c($a){$b=[];foreach($a as$i)$b[]=new \ArrayIterator($i);return new CartesianProductIterator($b);}`.
But my generator is shorter and does the same job.

The larger examples, however, result in an Internal Server Error (both with the iterator and the generator) after a while on my machine. Currently no time to check the server logs, unfortunately.

---
Tags: code-golf, permutations
---


title: Output source file name

text:
# Question
Title: Output source file name
Write a program that prints the name of its source file. REPL environments are not allowed for this challenge. Your code must work in any file that your language's interpreter will accept. Your answer must also be a full program, not just a function. The source code's file extension must be printed. Leading or trailing newline are both optional. This is a code golf, so shortest answer wins. The winner will be chosen on September 2nd, 2016.

# Answer
> 5 votes
# , 3 bytes

```
"zp

```

Try it online!

This actually *does* work in the online interpreter somehow. `¯\_(ツ)_/¯`

Explanation:

The 'z' register is predefined to the source file of the program, and `p` pastes from whatever register you tell it to. `P` would also work, and not cause any different output.

# Answer
> 2 votes
# Bash, 7

```
echo $0

```

So trivial, I have to type in this text to make the answer long enough.

# Answer
> 1 votes
# C, 23 bytes

```
main(){puts(__FILE__);}

```

Try it on Ideone

---
Tags: code-golf, file-system
---


title: Hook length product

text:
# Question
Title: Hook length product
A Young diagram is an arrangement of boxes in left-justified rows and top-justified columns. For each box, all the spaces above it and to its left are occupied.

```
XXXXX
XXX
XXX
X

```

The hook length of a box is the number of boxes to its right in its row, and below it in its column, also counting itself once. For example, the second box has a hook length of 6:

```
X****
X*X
X*X
X

```

Here are all the hook lengths:

```
86521
532
421
1

```

Your goal is compute the *product* of the hook lengths, here `8*6*5*2*1*5*3*2*4*2*1*1 = 115200`.

(Read about the hook length formula if you're interested in why this expression matters.)

**Input:** A collection of row-sizes as numbers like `[5,3,3,1]` or as a repeated unary symbol like `[[1,1,1,1,1], [1,1,1], [1,1,1], [1]]` or `"XXXXX XXX XXX X"`. You can expect the list to be sorted ascending or descending, as you wish. The list will be non-empty and only contain positive integers.

**Output:** The product of hook lengths, which is a positive integer. Don't worry about integer overflows or runtime.

Built-ins dealing specifically with Young diagrams or integer partitions are not allowed.

**Test cases:**

```
[1] 1
[2] 2
[1, 1] 2
[5] 120
[2, 1] 3
[5, 4, 3, 2, 1] 4465125
[5, 3, 3, 1] 115200
[10, 5] 798336000

```

# Answer
# CJam, ~~20~~ 19 bytes

```
{ee::+W%}_q~%z%:+:*

```

This takes in CJam style unary list in an ascending order. For example:

```
[[1] [1 1 1] [1 1 1] [1 1 1 1 1]]

```

gives

```
115200

```

**How it works**

This version is provided by Dennis and it uses the fact that a `Block ArrayList %` still works in CJam :D

```
{       }_             e# Put this block on stack and make a copy
          q~           e# Read the input and evaluate it to put the array of arrays on stack
            %          e# Use the copy of the block and map the array using that block
 ee                    e# Here we are mapping over each unary array in the input. ee converts
                       e# the array to [index value] pair.
   ::+                 e# Add up each index value pair. Now we have the horizontal half of
                       e# hook length for each row
      W%               e# Reverse the array to make sure the count is for blocks to the right
             z%        e# Transpose and do the same mapping for columns
               :+      e# Now we have all the hook lengths. Flatten the array
                 :*    e# Get the product of all hook lengths.

```

---

*This is the original 20 bytes version*

```
1q~:,Wf%z:ee{:+)*}f/

```

This takes in a CJam style list of row-sizes in an ascending order. For example:

```
[1 3 3 5]

```

gives

```
115200

```

**How it works**

If we look at it, hook length of each block in a Young block diagram is the sum of the index of that block in its row and column, counting backwards. i.e. Start the index in each row from right side and start the index in each column from bottom.

We take the input in ascending order of row-size in order to easily start the index from bottom in each column. First, we get the index per row and reverse it. Then we transpose. Since the original row order was reversed, taking index in this transposed diagram will directly give the bottom to top index.

**Code expansion**

```
1                       e# This serves as the initial term for product of hook lengths
 q~                     e# Read the input and eval it to put an array on stack
   :,                   e# For each row-size (N), get an array of [0..N-1]
     Wf%                e# Reverse each row so that each row becomes [N-1..0]
        z               e# Transpose for the calculation of blocks below each block
         :ee            e# Enumerate each row. Convert it into array of [index value] pairs
            {    }f/    e# Apply this mapping block to each cell of each row
             :+         e# Add the index value pair. Here, index is the blocks below the
                        e# block and value is the blocks to the right of it in the Young diag
               )        e# Increment the sum by 1 to account for the block itself
                *       e# Multiply it with the current holding product, starting with 1

```

Try it online here
> 13 votes

# Answer
# J, 24 bytes

```
*/@,@(1|@-+/\."1++/\)@:>

```

25 bytes (with explanation):

```
*/@,@(+/\."1|@<:@++/\)@:>

```

Takes input as list of ascending lists of unary digits similar to the example `[[1], [1,1,1], [1,1,1], [1,1,1,1,1]]`.

Usage:

```
   f=.*/@,@(+/\."1|@<:@++/\)@:>

   f 1;1 1 1;1 1 1;1 1 1 1 1
115200

```

Method

* Create a binary matrix from the input
* Compute the running differences in both dimensions.
* For each cell add the two results, subtract 1, take the absolute value (to map the originally zero cells to 1)
* Ravel the matrix and take the product of the numbers.

Intermediate results shown on the input `1 1 1 1 1;1 1 1;1 1 1;1 (5,3,3,1 in unary)` (*this is for a previous version with descending lengths but using the same method*):

```
   ]c=.1 1 1 1 1;1 1 1;1 1 1;1
┌─────────┬─────┬─────┬─┐
│1 1 1 1 1│1 1 1│1 1 1│1│
└─────────┴─────┴─────┴─┘

   (>)  c
1 1 1 1 1
1 1 1 0 0
1 1 1 0 0
1 0 0 0 0

   (+/\.@:>)  c
4 3 3 1 1
3 2 2 0 0
2 1 1 0 0
1 0 0 0 0

   (+/\."1@:>)  c
5 4 3 2 1
3 2 1 0 0
3 2 1 0 0
1 0 0 0 0

   ((+/\."1++/\.)@:>)  c
9 7 6 3 2
6 4 3 0 0
5 3 2 0 0
2 0 0 0 0

   ((+/\."1<:@++/\.)@:>)  c
8  6  5  2  1
5  3  2 _1 _1
4  2  1 _1 _1
1 _1 _1 _1 _1

   ((+/\."1|@<:@++/\.)@:>)  c
8 6 5 2 1
5 3 2 1 1
4 2 1 1 1
1 1 1 1 1

   (,@(+/\."1|@<:@++/\.)@:>)  c
8 6 5 2 1 5 3 2 1 1 4 2 1 1 1 1 1 1 1 1

   (*/@,@(+/\."1|@<:@++/\.)@:>)  c
115200

```

Same length explicit version:

```
3 :'*/,|<:(+/\."1++/\)>y'

```

Try it online here.
> 6 votes

# Answer
# Pyth - 21 bytes

I'm losing a lot of bytes in the vertical calculation. Gonna focus on golfing that.

```
*Fs.em+lf>Td>Qkt-bdbQ

```

Takes input like `[5, 3, 3, 1]`.

Try it here online.
> 4 votes

# Answer
# Pyth, 18 bytes

```
*Fsm.e+k-bdf>TdQeQ

```

Takes input in ascending order, like `[1, 3, 3, 5]`.

Demonstration.

---

**Alternate solution, 19 bytes**

```
*Fs.em+s>Rd<Qk-bdbQ

```
> 4 votes

# Answer
# Python 2, ~~89~~ 88 bytes

```
p=j=-1;d={}
for n in input():j+=1;i=0;exec"a=d[i]=d.get(i,j);p*=n-i+j-a;i+=1;"*n
print-p

```

*(Thanks to @xnor for one insane byte save by combining `p` and `j`)*

The `d.get` looks a little suspicious to me, but otherwise I'm relatively happy with this. I tried some other approaches, like recursion and zipping, but this is the only one I managed to get under 100.

Takes input from STDIN as a list in ascending order, e.g. `[1, 3, 3, 5]`.
> 3 votes

# Answer
# Haskell, 68 bytes

```
f[]=1
f g@(h:t)=(h+length t)*f[x-1|x<-g,x>1]
p[]=1
p g@(_:t)=f g*p t

```

Usage example: `p [5,4,3,2,1]` -\> `4465125`

`f` scans from left to right by multiplying the length of outmost hook with a recursive call to itself where each element of the input list is reduced by `1` (dropping it when reaching `0`). `p` scans from top to bottom by multiplying `f` of the whole list with `p` of the tail.
> 3 votes

# Answer
# Python, ~~95~~ 91 bytes

This is a Python implementation of nimi's Haskell answer. Golfing suggestions welcome.

```
f=lambda z:z==[]or(z[0]+len(z)-1)*f([i-1for i in z if~-i])
p=lambda z:z==[]or f(z)*p(z[1:])

```
> 2 votes

# Answer
# R, 174 bytes

So... This solution is quite long and could probably be more golfed. I'll think about it !

```
v=c();d=length;m=matrix(-1,l<-d(a<-scan()),M<-max(a));for(i in 1:l)m[i,(1:a[i])]=c(a[i]:1);for(j in 1:M)m[,j]=m[,j]+c((((p=d(which(m[,j]>0)))-1)):0,rep(0,(l-p)));abs(prod(m))

```

**Ungolfed :**

```
v=c()          #Empty vector
d=length       #Alias

m=matrix(-1,l<-d(a<-scan()),M<-max(a)) #Builds a matrix full of `-1`

for(i in 1:l)
    m[i,(1:a[i])]=c(a[i]:1) #Replaces each row of the matrix by `n` to 1, `n` being the
                            #corresponding input : each number is the number of non-empty
                            #cells at its left + itself

for(j in 1:M)
    m[,j]=m[,j]+c((((p=d(which(m[,j]>0)))-1)):0,rep(0,(l-p)))

    #This part calculates the number of "non-empty" (i.e. without `-1` in a column), -1,
    #because the count for the cell itself is already done.
    # Then, it creates a vector of those count, appending 0's at the end if necessary
    #(this avoids recycling)

abs(prod(m)) #Outputs the absolute value of the product (because of the `-1`'s)

```
> 2 votes

# Answer
# Python 2, ~~135~~ 128 bytes

This takes a Python type list from stdin:

```
r=input()
c=[-1]*r[0]
for a in r:
 for b in range(a):c[b]+=1
s=1
y=0
for a in r:
 for x in range(a):s*=a-x+c[x]-y
 y+=1
print s

```

This is a very canonical implementation, but I haven't come up with anything much smarter so far. I have a feeling that there will be much shorter solutions even with "real" programming languages.

We get the number of boxes in each row as input. This solution first counts the number of boxes in each column, which is stored in `c` (it's actually the count minus 1 to simplify its usage in the later calculation). Then it iterates over all boxes, and multiplies the hook lengths. The hook length itself is trivial to calculate once you have the count of boxes in each row and column.
> 1 votes

# Answer
# JavaScript (*ES6*) 69

A function taking an array of integers in *ascending* order.

Run the snippet to test (Firefox only)

```
F=x=>x.map(r=>{for(i=-1;++i<r;p[i]=-~p[i])t*=r-i+~~p[i]},p=[],t=1)&&t

// TEST
out=x=>O.innerHTML += x + '\n';

test=[
 {y:[1], h: 1}
,{y:[2], h: 2}
,{y:[1, 1], h: 2}
,{y:[5], h: 120}
,{y:[2, 1], h: 3}
,{y:[5, 4, 3, 2, 1], h: 4465125}
,{y:[5, 3, 3, 1], h: 115200}
,{y:[10, 5], h: 798336000}
]

test.forEach(t=>{
  t.y.reverse(); // put in ascending order
  r=F(t.y);
  out((r==t.h? 'Ok':'Fail')+' Y: ['+t.y+'] Result:'+r+' Check:'+t.h)
})
```

```
<pre id=O></pre>
```
> 1 votes

---
Tags: code-golf, math, combinatorics, integer-partitions
---


# Question
Title: How can I shorten this multiple assignment in Lua?
Is there any better way to golf this (other than removing newlines/indentation)?

```
function(a,b,...)
  local c=s(a,b)
  local d=c
  for i,v in ipairs{...} do d=d:push(v) end
  return c
end

```

I'm particularly bothered by the double `local` usage, but as Lua does not have multiple assignment, and I cannot use function parameters to declare the locals, I can't see a way to remove them.

*For those who care, this is the implementation of the `__call` metamethod in my quick hack of a linked-list ~class used in this answer.*

# Answer
As requested in the comments, here it is as an answer.

```
local c,d=s(a,b)  -- d is nil
d=c

```

This saves you one `local` declaration, should give you -5 bytes.
> 4 votes

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


title: Extendable Train Swapping Problem

text:
# Question
Title: Extendable Train Swapping Problem
# Extended Train Swapping Problem

### Part 1: Normal Train Swapping Problem

In the 1996 CCC (Canadian Computing Competition), the first Stage 2 problem was a Train Swapping Problem. You can visit the link here. Essentially, you have a bunch of numbered trains, and you want to find out how many train swaps you need to get them in order, and each train swap operation allows you to swap two adjacent trains. Since train carriages can run either way, nobody cares about the fact that the train carriages face the other way when swapped. This is pretty easy; all you need to do is:

> Find the number of steps to bubble-sort it; it's the most efficient sorting algorithm when you can only make adjacent element swaps

So, I made a harder one.

### Part 2: How this challenge works

Essentially, you can now swap more than just adjacent trains. With a longer rotating platform, you can swap the position of multiple trains. For example, with a rotating platform of length 4, you can swap both the inner and outer pairs at the same time, so `1 2 3 4` becomes `4 3 2 1`. Here are some examples for different rotating platform sizes:

```
Length 2:
1 2 3 4 5
  ---
1 3 2 4 5

Length 3:
1 2 3 4 5
  -----
1 4 3 2 5

Length 4:
1 2 3 4 5
-------
4 3 2 1 5

```

Essentially, you're just inverting a sublist of the entire train. To clarify, in each move, you can only swap *exactly* `N` trains.

### Part 3: Specifications

## Input

Your input must take in two things: the length of the rotating platform, and the order of the train carriages. You may also require the number of train carriages if you wish. The order of the train carriages is given by an ordered list of numbers (each number representing a train carriage), so you can read the input as space-separated integers, newline-separated integers, an array, etc.

## Output

You must output the optimal (minimum) number of swaps needed to get the carriages all into the order `1 2 3 ... N`. If there is no solution, output `-1`, `No solution`, or some other consistent message. You may not output to stderr.

## Scoring

This is a challenge, so scoring is in bytes. The solution with the lowest number of bytes as of September 1st, 2016 will be the accepted one.

## Examples

**Problem 1** **Input**

```
4
2
1 3 2 4

```

**Output**

```
1

```

**Explanation**
This is pretty trivial; with a rotating platform of length 2, it's the same as the normal train swapping problem. Swap the `2` and the `3`.

**Problem 2** **Input**

```
4
3
1 3 2 4

```

**Output**

```
No solution (or an equivalent consistent message).

```

**Problem 3** **Input**

```
9
3
1 4 5 6 3 8 7 2 9

```

**Output**

```
4

```

**Explanation**

```
1 4 5 6 3 8 7 2 9
          -----
1 4 5 6 3 2 7 8 9
      -----
1 4 5 2 3 6 7 8 9
    -----
1 4 3 2 5 6 7 8 9
  -----
1 2 3 4 5 6 7 8 9

```

Standard loopholes apply

Good luck!

**EDIT 1**: Made the input format more flexible. Thanks to @Mego!
**EDIT 2**: Clarified that a rotating platform of length 4 swaps both the inner *and* outer pairs. Thanks to @TimmyD!
**EDIT 3**: Clarified that you must make permutations of length `N` exactly, not at most. Thanks to @Zgarb!

# Answer
# Perl, 120 bytes

Includes +6 for `-Xapi` (`-` and space are counted too because both the `-i` and the `$'` in the code make it impossible to combine the options with `-e`)

Run with the input on STDIN and the platform length after the `-i` option, e.g.

```
perl -Xapi3 trains.pl <<< "1 4 5 6 3 8 7 2 9"

```

Prints `-2` if there is no solution

`trains.pl`:

```
1until$_=$n++*$z{pack"W*",@F}||-!grep!$z{$_}++&&/.{$^I}(??{!\$z{$`.reverse($&).$'}})$/s,keys%z,pack"W*",1..@F;$_--

```

if `N <= 9` then you can gain 5 more bytes:

```
1until$_=$n++*$z{join"",@F}||-!grep!$z{$_}++&&/.{$^I}(??{!\$z{$`.reverse($&).$'}})$/,keys%z,join"",1..@F;$_--

```
> 1 votes

---
Tags: code-golf, sorting, graph-theory, path-finding, permutations
---


title: Brainf*ck Loop Problem

text:
# Question
Title: Brainf*ck Loop Problem
I have a problem for a cyber club that asks you to print:

```
ZYXWVUTSRQPONMLKJIHGFEDCBA@?>=<;:9876543210/.-,+*)('&%$#"!

```

Using Brainf\**k in 29 bytes or less without using the ',' character.

I have a working code:

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

```

However my loop is too long, sending me 16 bytes over the limit.

Is there a more efficient way to set the second and third cell to 58 and 90 so I can run my second loop? Or is there a better way to do this all together that I am just not seeing?

# Answer
> 24 votes
## ~~27~~ 24 bytes

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

```

~~Spent a whole day basically writing up a brute forcer and watching the results come in. Now I can get back to doing some actual work...~~ Another day of brute forcing later...

Try it online!

The component `++[<++[++<]>>>+]` initialises the tape to

```
[130, 0, 0, 0, 91, 59, 0]
                       ^

```

which is just perfect for what we need!

# Answer
> 15 votes
# 30 bytes

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

```

Try it online!

*85* and *171* are fairly easy to generate in brainfuck (modular inverses of *3* and *-3*). *85* is pretty close to *90*, and *171* is pretty close to *177* (*59·3*), which is used here. With a bit of hackery, I'm able to produce *88* and *176* instead.

Still one byte short of the target, though.

**Other suggestions**

In general, it's shorter to iterate over a list, multiplying by a constant, rather than the other way. This is especially true for 3 or more values. For example, this:

```
++++++++++[>++++++>+++++++++<<-]

```

can be written as:

```
+>++++[+++++[>++++++++++<-]<]>

```

There were only two inner values, so it's not much of an improvement in this case. In fact, just refactoring is one byte shorter:

```
+++++[>++++++[>++>+++<<-]<-]>

```

Multiplying *30* by *2* and *3*, rather than *10* by *6* and *9*. With Martin Büttner's suggestion, this is already down to *38* bytes, without much change to the original:

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

```

# Answer
> 4 votes
# 34 bytes

Saved you 11 bytes, but still 5 bytes too long...

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

```

I've spent hours already, hopefully someone can improve on this.

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


title: Draw a random hexa-glyph

text:
# Question
Title: Draw a random hexa-glyph
The above image is called a hexa-glyph. Hexa-glyphs are some cool patterns I made up while doodling during my DiffEq class. Here's how you make one:

1. Consider the following set of points, shaped like a regular hexagram. The inner hexagon is what will contain the final glyph, while the outer 6 points form a star and are where we will start drawing our lines.

2. From the outer six points, randomly select a pair. For efficiency, there should be at least one other point between the two selected points (otherwise, it would have no effect on the final figure). Then, from each of the two points, cast a *ray* towards the other. This ray is *blocked* by previous lines.

3. Repeat this process until all 9 edges have been formed, as shown in the next few images.

4. Here is an example of rays being blocked. The ends of the ray segment are still visible, but the middle portion is occluded by the first two segments we drew.

5. These two rays are also "blocked," but this doesn't cause any visible difference because they are blocked by the same other line.

6. Fast-forwarding until all 9 lines are drawn. If you want a more detailed explanation of these skipped steps, I can expound.

7. Finally, remove the points of the star. To make it look prettier, the thick dots are also removed.

# The challenge

You challenge is to output a visual representation of a random hexa-glyph. This is code-golf, fewest bytes wins.

1. All possible hexa-glyphs should appear with some positive probability. Different hexa-glyphs are generated by changing the order in which the 9 edges are drawn.
2. Furthermore, all images output by your program must be valid hexa-glyphs. Certain patterns (like a complete outline of the inner hexagon) cannot possibly appear as a hexa-glyph, and so you program mustn't output these.
3. The output should be a graphical image (printed to screen or file).
4. The hexagon must be regular, but can appear in any orientation.
5. Reflections / rotations are *not* considered unique. (This might make requirement 1 easier to follow).

# Answer
> 17 votes
## Mathematica, ~~273~~ ~~268~~ ~~264~~ 242 bytes

```
c=CirclePoints;b@_=k=1>0;Graphics[Line/@Cases[Append[Join@@({c@6,{3^.5/2,-Pi/6}~c~6}),{0,0}][[b@#=!k;#]]&/@TakeWhile[#,t=k;(r=t;t=b@#;r)&]&/@Join@@RandomSample[{#,Reverse@#}&/@Partition[Range@12,3,2,1]~Join~Array[{2#,13,2#+6}&,3]],{_,__}]]

```

The  renders as a superscript `T` in Mathematica and is a postfix transpose operator.

Sorting out the bugs in this took forever... towards the end I hacked a few things together to make it work, so this is definitely suboptimal. I also wonder whether it might be better overall to implement the spec more literally via the lines across the outer hexagon and let Mathematica's geometry functions handle the intersections.

Note that this is a full program and if you want to run the code multiple times within a single REPL session you'll have to prefix it with `Clear[b]`.

Here are the results of 20 runs:

### Explanation

This solution doesn't make use of the outer star points at all. Instead it works directly with the points that are part of the hexaglyph and lines that cover three of them at a time.

Let's label the points:

`1` starts on a slightly weird corner but this is due to the (also somewhat weird) default behaviour of `CirclePoints`. Starting the hexagon from there turned out cheapest.

Now we want to find the relevant lines through three of those points which correspond to connected points of the outer star. The ones around the hexagon are of course just 3 adjacent points (modulo 12), starting from an odd number. The ones across the centre consist of an even number `n`, `13` and `n+6`.

Representations of these lines (in the form of lists of three points are generated by the following code):

```
Partition[Range@12,3,2,1]~Join~Array[{2#,13,2#+6}&,3]

```

The `Partition` generates the lines around the hexagon and the `Array` the lines through the centre. To process both beams, we map this function over the list of lines:

```
{#,Reverse@#}&

```

Now we shuffle these with `RandomSample` to process them in a random order. `Join @@` flattens the list of pairs so that we have a list of beams.

Short intermission: to keep track of which points are already blocked we use a lookup function `b`, which is initialised to `True` for all values by `b@_=k=1>0;`. When processing a beam we keep all points until the first point that has `b[n] == False` (*including* that one):

```
TakeWhile[#,t=k;(r=t;t=b@#;r)&]&

```

I feel like this is the most golfable part right now... the use of two temporary variables to play Mastermind seems really expensive. Anyway, the result of this gives us the points in a line we're allowed to draw. Now this function is mapped over each of those points:

```
Append[Join@@({c@6,{3^.5/2,-Pi/6}~c~6}),{0,0}][[b@#=!k;#]]&

```

The first part generates the list of all 13 points using the interleaved results of two calls to `CirclePoints` (with different radii for the edge centres and the corners of the hexagon). Note the `b@#=!k` which now sets the lookup table's value for the current point to `False` so that no further beam can pass through it. Finally, the value is used as an index into the list of coordinates to get the correct 2D point.

```
Cases[...,{_,__}]

```

This discards all single-element lists, because they would render as individual (and visible) points. Finally we render the result:

```
Graphics[Line/@...]

```

# Answer
> 8 votes
# Shoes (Ruby) Rev C 184 bytes

12 bytes saved by transferring responsibility for checking if a particular half-line should be drawn from the main program to the drawing method. The main program still has to check if the whole line is completely blocked, though.

```
Shoes.app{t=[]
d=->p,q{t[p]&&t[q]||line(p/6*8,p%6*14,q/6*8,q%6*14)}
%w{1I IW WM M5 5' '1 =A P. R,}.shuffle.map{|i|b=i.sum/2
c=b*2-a=i.ord
t[a]&&t[c]||(d[a,b]
d[b,c]
t[a]=t[b]=t[c]=1)}}

```

# Shoes (Ruby) ~~205~~ ... Rev B 196 bytes

Shoes is a ruby-based tool for building GUI's etc. It's the first time I've used it. mothereff.in/byte-counter counts my submission as 196 bytes, but for some reason Shoes counts it as 202.

Also, Ruby lets you do things like `t[a=i.ord]` but strangely, it seems not to work as expected with Shoes.

```
Shoes.app{t=[]
d=->p,q{line(p/6*8,p%6*14,q/6*8,q%6*14)}
%w{1I IW WM M5 5' '1 =A P. R,}.shuffle.map{|i|b=i.sum/2
c=b*2-a=i.ord
t[a]&&t[c]||(t[a]&&t[b]||d[a,b]
t[b]&&t[c]||d[b,c]
t[a]=t[b]=t[c]=1)}}

```

**Explanation**

I don't consider the parts of the line outside the hexagon. I only draw the part that needs to be drawn. The important thing is whether the lines cross the intersections (If we only draw the parts that need to be drawn, this means they begin / end at the intersections.)

The basic rule is that if both endpoints of a line have been visited, the line is blocked and should not be drawn. As the lines are drawn in two halves, we also have to check if the midpoint has been visited to see if each half should be drawn or not.

I keep track of which points have been visited in the array `t[]`. This ends up containing an entry for each physical coordinate on the grid below. There is no separate 13-element logical array. By the end, `t[]` may have 87 elements, though only up to 13 will contain useful data.

Internally, the coordinates of the endpoints of the lines are given by a single number z, where z%6 is the y coordinate and z/6 is the x coordinate. In this system the hexagon is flattened. When the lines are plotted, the x scale is multiplied by 8 and the y scale is multiplied by 14, which is a very close rational approximation to the correct ratio: 14/8=1.75 vs sqrt(3)=1.732.

The internal coordinate system is shown below, with a few sample outputs.

**Ungolfed**

```
Shoes.app{
  t=[]                                          #Empty array for status tracking
  d=->p,q{line(p/6*8,p%6*14,q/6*8,q%6*14)}      #Drawing method. Convert p and q into x,y pairs, scale and draw line.
  %w{1I IW WM M5 5' '1 =A P. R,}.shuffle.map{|i|#take an array of the coordinates of the endpoints of each line, shuffle, then for each line
    b=i.sum/2                                   #b = midpoint of line, convert ASCII sum to number (average of the two coordinates)
    a=i.ord                                     #a = first endpoint of line, convert ASCII to number (no need to write i[0].ord)
    c=b*2-a                                     #c = second endpoint of line (calculating is shorter than writing i[1].ord)
    t[a]&&t[c]||(                               #if both endpoints have already been visited, line is completely blocked, do nothing. ELSE
      t[a]&&t[b]||d[a,b]                        #if first endpoint and midpoint have not both been visited, draw first half of line
      t[b]&&t[c]||d[b,c]                        #if second endpoint and midpoint have not both been visited, draw second half of line
      t[a]=t[b]=t[c]=1                          #mark all three points of the line as visited
    )
  }
}

```

**More Sample outputs**

These were done with an older version of the program. The only difference is that the positioning of the hexaglyph in the window is now slightly different.

# Answer
> 3 votes
# Python, ~~604~~ ~~591~~ ~~574~~ ~~561~~ ~~538~~ ~~531~~ ~~536~~ ~~534~~ ~~528~~ ~~493~~ ~~483~~ ~~452~~ ~~431~~ ~~420~~ ~~419~~ ~~415~~ ~~388~~ ~~385~~ 384 bytes

I have adapted Level River St's idea of checking if a line will be blocked by checking if both endpoints of the line have already been visited before. This saves 27 bytes. Golfing suggestions welcome.

**Edit:** Bug fixing and golfing `g(p,q)` for 3 bytes. Golfed `L` for one byte.

```
from turtle import*
from random import*
R=range
G=goto
*L,=R(9)
shuffle(L)
a=[0]*13
ht()
T=12
c=[(j.imag,j.real)for j in(1j**(i/3)*T*.75**(i%2/2)for i in R(T))]+[(0,0)]
def g(p,q):pu();G(c[p]);a[p]*a[q]or pd();G(c[q])
for m in L:
 p=2*m;x,y,z=R(p,p+3)
 if m<6:
  if a[x]*a[z%T]<1:g(x,y);g(y,z%T);a[x]=a[y]=a[z%T]=1
 else:
  if a[p-11]*a[p-5]<1:g(p-11,T);g(p-5,T);a[p-11]=a[p-5]=a[T]=1

```

**Ungolfing:**

```
from turtle import*
from random import*

def draw_line(points, p_1, p_2):
    penup()
    goto(points[p_1])
    if not (a[p] and a[q]):
        pendown()
    goto(points[p_2])

def draw_glyph():
    ht()
    nine_lines = list(range(9))
    shuffle(nine_lines)
    size = 12
    center = [0,0]

    points = []
    for i in range(12):      # put in a point of a dodecagon
                             # if i is even, keep as hexagon point
                             # else, convert to hexagon midpoint
        d = 1j**(i/3) * 12   # dodecagon point
        if i%2:
            d *= .75**.5     # divide by sqrt(3/4) to get midpoint
        points += (d.imag, d.real)
    points.append(center)

    a = [0]*13
    for m in nine_lines:
        p = 2*m
        if m<6:
            x, y, z = p, p+1, p+2
            if not (a[x] and a[z%12]):
                draw_line(points, x, y)
                draw_line(points, y, z%12)
                a[x] = a[y] = a[z%12] = 1
        else:
            if not (a[p-11] and a[p-5]):
                draw_line(p-11, 12)
                draw_line(p-5, 12)
                a[p-11] = a[p-5] = a[12] = 1

```

The hexa-glyphs themselves are quite small as we use a 12-pixel hexagon as a base (for golfing reasons). Here are some example hexa-glyphs (apologies for the poor cropping):

---
Tags: code-golf, graphical-output, geometry, random
---


title: The Burnt Pancake Problem

text:
# Question
Title: The Burnt Pancake Problem
This challenge is related to Flipping Pancakes.

You may have heard of pancake sorting, where a stack of pancakes is sorted by size by inserting spatula into the stack and flipping all of the pancakes above the spatula, until the pancakes are sorted smallest to largest on the plate. The burnt pancake problem is slightly different. All pancakes now have one side that is burnt, and the burnt side of each pancake must face the plate once the sorting is completed.

For example, given the following stack (size of pancake on the left. `0` meaning burnt-side down and `1` meaning burnt-side up on the right):

```
1 0
3 1
2 1

```

You may flip the whole stack to get `20 30 11`, flip the top two to get `31 21 11` and flip the whole stack again to get `10 20 30`, a sorted stack of burnt pancakes. This sequence of moves, flip 3, flip 2, flip 3, could be represented as `3 2 3`.

**The Challenge**

* Given an array of pancakes sizes (not necessarily unique) and their orientations, output any valid burnt pancake sorting sequence, that is, a sequence of flips that leads to the stack of pancakes being sorted from smallest to largest with burnt sides down.
* Input and output may be any sane format with separators, but please specify which formats you use and state which end of your input format is the top of the stack (TOS).
* Flipping zero pancakes is allowed.
* Mixing separators in the input/output is allowed.

**Test cases**

For all of the following test cases, input is a list and output is a space-separated string, and TOS is on the left.

```
[[1, 0], [3, 1], [2, 1]]
"3 2 3"

[[5, 1], [3, 0], [4, 1], [2, 1], [1, 0]]
"5 3 4 1 3 2 1"

[[5, 1], [3, 0], [3, 0], [1, 1]]
"4 3 2 3"

```

As always, if anything is unclear or incorrect, please let me know in the comments. Good luck and good golfing!

# Answer
> 7 votes
# Python 2, 83

Input is expected to be the list of (size, orientation) tuples with the stack's top at the end. The output is a list of sizes to flip separated by various kinds of whitespace.

```
a=input()
while a:i=a.index(max(a));print len(a)-i,a[i][1],len(a),i;a=a[i+1:]+a[:i]

```

# Answer
> 3 votes
# Ruby, ~~101~~ ~~95~~ 93 bytes

Not very golfy, I just wanted to make a bogo-sort variant. It's an anonymous function that takes an array of arrays and prints random flips to stdout until the pancakes are sorted.

```
->a{(p r=-~rand(a.size)
a[0,r]=a[0,r].reverse.map{|x,b|[x,1-b]})while a!=a.sort||a.rassoc(1)}

```

You can for example assign it to `f` and say `f.call [[1, 0], [3, 1], [2, 1]]`

-5 bytes from @Jordan with the brilliant use of `rassoc`
-2 bytes from @Sherlock9

# Answer
> 3 votes
## CJam (37 bytes)

```
q~{__$W>#)_p/(W%\M*2,f.^+(1=p_,)pW%}h

```

Input is an array in CJam format on stdin; output is a newline-separated list of flip lengths on stdout. The top of stack is at index `0`; `0` indicates burnt side up, and `1` indicates burnt side down.

Online demo

### Dissection

The output is always `3n` flips long, where `n` is the number of pancakes. First we flip the largest remaining pancake to the top; then if it's burnt side down we flip that one pancake; and then we flip it to the bottom and repeat as though the stack of pancakes were one shorter.

```
q~         e# Parse input into array
{          e# Loop...
  __$W>#)  e#   Find 1-based index of largest element in array
  _p       e#   Dup and print
  /(       e#   Split into chunks that long, and pull off the first
  W%       e#   Reverse the first chunk. Note that we don't flip the burnt/unburnt bit
  \M*      e#   Merge the remaining chunks into a single array
  2,f.^    e#   Flip *their* burnt/unburnt bits
  +        e#   Concatenate, prepending the first chunk
  (1=p     e#   Pull off the first (largest) element and print its burnt/unburnt bit
  _,)p     e#   Print the number of remaining elements plus 1 (to account for the largest)
  W%       e#   Reverse. Note that the first chunk has now been flipped twice, which is
           e#   why we have left its burnt/unburnt bit alone
}h         e# ... until we get down to an empty array

```

---
Tags: code-golf, sequence, sorting, path-finding, stack
---