# Question
Title: Decide whether a given field of the board game 'Qwirkle' is valid (according to game rules)
The famous game of Qwirkle has simple but intricate rules (See part 2 of this question for a summary of the rules!)

1. The Challenge You are somehow (text input, function parameter, whatever) given a board of a Qwirkle game, like a snapshot from any current timeframe within a game. This board can be anything from completely empty to completely filled with tiles (max board size should be at least 32x32). Each tile can be one of six colors (red r, green g, blue b, orange o, purple p, yellow y) and one if six shapes (circle c, square s, flower f, zacks z, small star m, rhombus r). You can use any distinct letters as well! There are exactly three tiles of each shape-color combination in the whole set of tiles.

Simple rules are:

* each line (horizontal or vertical) of touching tiles must contain any distinct tile at most once and only tiles of different color and same shape OR tiles of different shape and same color!
* every tile has to touch ar least one neighboring tile! No single/islands of tiles!

Your task is to calculate wether the given board is in a valid state (see rules down below). That is, wether the given board does not break any of the rules. It can also be interpreted as 'a board that was created from a valid game, not breaking any of the game's rules'. The result is thus one of two possible values, either true or false, 1 or 0 or whatever you prefer.

The result can be anything from a text output, a returned boolean or other variable type or whatever you want. Just somehow publish the result (don't just keep it inside a variable)

2. The Game Rules In a possibly infinite 2d checked board, tiles get laid. On every field on the board can either be one or no tile.

There are 36 different types of stones, each 3 times, makes a total of 108 tiles. A board doesn't contain more than one set of tiles. (you only play with one sack. When it's empty, the game ends)

3. Special Things to Check

* It's important to note that a valid game evolves around one start position. This means, any tile on the field has to touch any other tile through other tiles. There can't be single tiles or islands of tiles disconnected from the main starter island. So, any tile has to touch at least one other tile.
* there are only 3 tiles of each color and shape in total. So there can't be, for example, 4 red square tiles or 4 green circles.
*

4. Example Image This is an example of a valid qwirkle field: I think all of your questions can be answered by studying this image:

5. Test Cases Note that test cases are going to be in an array (string with linebreaks or similar), for example: your program can take some other format (for example tabbed strings, semicolons as dividers or whatever! Doesn't have to accept any one! Just choose one specific format)

```
0,0,rs,rc,0,0
0,0,gs,gc,0,0

```

(this would be valid!)

In this case i specified the input as color first letter, shape second letter. So rs is red square, gc is green circle etc. Any other format is ok!

6. This is so shortest working code in bytes wins!

## Test cases (based from comments, commas separate columns, semicolons separate rows):

Truthy:

```
""
rc,gc,bc,oc,pc,yc;rs,gs,bs,os,ps,ys;rf,gf,bf,of,pf,yf;rz,gz,bz,oz,pz,yz;rm,gm,bm,om,pm,ym;rr,gr,br,or,pr,yr

```

Falsy:

```
rc,rs,rf,rz,rm,rr,rf
rc,rs,rf,yc

```

# Answer
# Haskell, 265 bytes

```
import Data.Maybe
import Data.List
i=isJust
(#)=map
a=all
h=head
j=fromJust
t([]:_)=[];t x=(h#x):t(tail#x)
v b=a(a(\z->any(a id)$t$(zipWith(==)$j$h z)#(j#z)))$map(filter(i.h).groupBy((.i).(==).i))b
f b=v b&&v(t b)&&(a((==1).length)$group$sort$concatMap catMaybes b)

```

Attempt This Online!
> 4 votes

# Answer
# 05AB1E, ~~71~~ 69 bytes

```
ø«ε0¡ε€Sø€ËàyD¢*]˜PI˜áD¢4‹PIa©˜ƶIgäΔ2Fø0δ.ø}2Fø€ü3}®*εεÅsyøÅs«à]˜0KËP

```

Input as a matrix of 2-char strings, with `0` as gaps. Outputs a 05AB1E truthy/falsey result, so `1` for truthy, or `0` or a positive integer for falsey.

Try it online or verify all test cases.

**Explanation:**

Step 1: Verify that each connected portion in a row or column is valid, where valid means they're either all the same shape and/or the same color, and in addition there aren't any duplicated pieces in a connected row/column.

```
ø           # Zip/transpose; swapping rows/columns of the (implicit) input-matrix
 «          # Merge this list of columns to the (implicit) input-list of rows
ε           # Map over each inner row/column:
 0¡         #  Split it on 0s (the gaps)
   ε        #  Map over each connected portion:
    €S      #   Split each 2-char string to a pair of characters
      ø     #   Zip/transpose; swapping rows/columns
       €Ë   #   Check for each inner list whether they're all the same
         à  #   Pop and get the maximum, to check if this is truthy for either
    y       #   Push the current connected portion again
     D      #   Duplicate it
      ¢     #   Pop both, and count how many times each piece occurs
    *       #   Multiply the earlier check to each count in the list
]           # Close the nested maps
 ˜          # Flatten the list of list of list of checks
  P         # Check if everything was truthy by taking the product

```

Try just this first step online or verify it for all test cases.

Step 2: Check that each individual piece does not occur more than 3 times:

```
I           # Push the input-matrix again
 ˜          # Flatten it
  á         # Remove all gaps by only keeping the letters
   D        # Duplicate it
    ¢       # Pop both, and count how many times each piece occurs
     4‹     # Check for each that it's smaller than 4
       P    # Check if everything was truthy by taking the product

```

Try just this second step online or verify it for all test cases.

Step 3: Flood-fill the matrix to check if everything is a single connected island (which I've done before in this answer and this answer of mine):

```
I           # Push the input-matrix yet again
 a          # Convert all pieces to 1s with the is_alphabetic builtin
  ©         # Store this matrix of 1s/0s in variable `®` (without popping)
   ˜        # Flatten it
    ƶ       # Multiply each value by its 1-based index
     Igä    # Mold it back to a matrix matching the input:
     I      #  Push the input
      g     #  Pop and push the length (the amount of rows)
       ä    #  Split the list into that many equal-sized parts
Δ           # Loop until the result no longer changes:
 2Fø0δ.ø}   #  Add a border of 0s around the matrix:
 2F     }   #   Loop 2 times:
   ø        #    Zip/transpose; swapping rows/columns
     δ      #    Map over each inner list:
    0 .ø    #     Surround it with both a leading and trailing 0
 2Fø€ü3}    #  Then split it into overlapping 3x3 blocks:
 2F         #   Loop 2 times again:
   ø        #    Zip/transpose; swapping rows/columns again
    €       #    Map over each inner list again:
     ü3     #     Split this list into overlapping triplets
 ®*         #  Multiply this matrix of 3x3 blocks and matrix `®` together,
            #  so all 3x3 blocks at the 0-positions will become a block of 0s
 εεÅsyøÅs«à #   Get the largest value from the horizontal/vertical cross of each
            #   3x3 block:
 εε         #    Nested map over each 3x3 block:
   Ås       #      Pop and push its middle row
     y      #      Push the 3x3 block again
      ø     #      Zip/transpose; swapping rows/columns
       Ås   #      Pop and push its middle row as well (the middle column)
         «  #      Merge the middle row and column together to a single list
          à #      Pop and push its maximum
]           # Close the nested maps and flood-fill loop
 ˜          # Flatten the resulting flood-filled matrix
  0K        # Remove all 0s (the gaps)
    Ë       # Check if all remaining values are the same, so we have a single island

```

Try just this third step online or verify it for all test cases.

Step 4: Combine all three checks of the previous steps, and output the result:

```
P           # Simply take the product of all three values on the stack
            # (which is output implicitly as result)

```
> 2 votes

# Answer
# , 90 87 85 78 74 bytes

```
((#@~."1@|:e.~1,#)@#~*/@,&,[:g+/@])(,:&(-/~)0j1&*)(g=.+./ .*^:_~)"2@e.i:@1

```

Try it online!

## argument encoding

We take the list positions (encoded as complex numbers) as the right arg, and the list of pieces as the left arg. For example, for the board:

```
rc,gc,bc
__,gs,__
__,gf,__

```

the left and right arguments would look like this (boxed for clarity):

```
┌──┬─────────────────┐
│rc│0 0j1 0j2 1j1 2j1│
│gc│                 │
│bc│                 │
│gs│                 │
│gf│                 │
└──┴─────────────────┘

```

## idea

The high-level idea is the interesting part, so I'll focus on that.

1. Find all horizontally connected pieces. To do this, we create an adjacency matrix of all the positions, where adjacency is defined by the distance between two elements being in the set `_1 0 1`:

```
      0    0j1  0j2  1j1  2j1
     +-----------------------
 0   |1    1    0    0    0
 0j1 |1    1    1    0    0
 0j2 |0    1    1    0    0
 1j1 |0    0    0    1    0
 2j1 |0    0    0    0    1

```

And then take the transitive closure of that matrix "or-multiplied" by itself until a fixed point. The result shows all the horizontal connections:

```
  1 1 1 0 0  <- 0 is connected to 0, 0j1, 0j2
  1 1 1 0 0  <- 0j1 is connected to 0, 0j1, 0j2
  1 1 1 0 0  <- 0j2 is connected to 0, 0j1, 0j2
  0 0 0 1 0  <- 1j1 is only connected to itself
  0 0 0 0 1  <- 2j1 is only connected to itself

```
2. Find all vertically connected pieces. To do this, we reuse the logic in step 1, by first multiplying every position by `0j1`, which has the effect of rotating the entire board 45 degress left. Now vertical connections will be horizontal ones. The resulting final matrix this time is:

```
 1 0 0 0 0
 0 1 0 1 1
 0 0 1 0 0
 0 1 0 1 1
 0 1 0 1 1

```
3. Next, we use the rows from the previous steps as masks to define the groups of pieces we need to validate:

```
 ┌──┬──┬──┬──┬──┐
 │rc│gc│bc│gc│gc│  <- Vertically connected pieces
 │  │gs│  │gs│gs│
 │  │gf│  │gf│gf│
 ├──┼──┼──┼──┼──┤
 │rc│rc│rc│gs│gf│  <- Horizontally connected pieces
 │gc│gc│gc│  │  │
 │bc│bc│bc│  │  │
 └──┴──┴──┴──┴──┘

```
4. For each group, we validate that one property is all the same, and that the other property is all different. This part should have been easier to golf but the best approach I came up with was `(#@~."1@|:e.~1,#)`. This takes the transpose of the input:

```
 ggg
 csf

```

and takes the length of the uniq of each row, giving: `1 3`. We then check if both `1` and "input length" are members of that list.
5. Finally, we check that all elements are connected. Here we use our adjacency matrix trick a third time, except now adjacency is defined as a horizontal or vertical connection:

```
 1 1 0 0 0
 1 1 1 1 0
 0 1 1 0 0
 0 1 0 1 1
 0 0 0 1 1

```

and we check that its transitive closure becomes the matrix consisting of all ones:

```
 1 1 1 1 1
 1 1 1 1 1
 1 1 1 1 1
 1 1 1 1 1
 1 1 1 1 1

```
> 2 votes

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


title: Generate the DH series

text:
# Question
Title: Generate the DH series
I see from this SMBC comic that Zach Weinersmith is offering a generous 14 points to anybody who can find a way of generating the following series:

```
0, 1, 4, -13, -133, 52, 53, -155

```

Now, we all know that there are infinite ways of generating any given numeric series, so Zach is clearly just giving those points away. But what's the *shortest* code that will do it?

I'll be particularly impressed if anyone can beat 25 bytes, particularly in a non-golfing language, since that's what it takes to write the following reference implementation in Python:

```
0,1,4,-13,-133,52,53,-155

```

The output can be in whichever format works best for you:

1. a program that spits out plaintext representation of signed decimal numbers
2. an expression that evaluates to a static sequence of numeric objects with these values (as in my Python example)
3. an expression for `f(n)` that returns the `n`th value of the sequence. You can choose a zero-based or one-based convention for `n` as you wish and need not worry what the expression produces subsequent to the known elements. (By "expression" here, I mean let's not count the characters in the function prototype itself, and let's say you can assume `n` is pre-initialized.)

Longer sequences (including infinite sequences) are permitted provided the first 8 elements match Weinersmith's DH Series above. The ninth and subsequent elements, if present, can be anything at all.

# Answer
> 5 votes
# Jelly, 12 bytes

```
“ĊĊḊḢṬ3gƈ¢‘I

```

Try it online!

### Explanation

```
“ĊĊḊḢṬ3gƈ¢‘      String representing code points
           I     Consecutive increments

```

# Answer
> 4 votes
# PHP, 75 Bytes

0-Indexing prints a underscore separeted string till the n th value

```
<?=+$e;for(;$i++<$argn;)echo _,$e+=[185,1,7-4*$e-log($e)^0,-17,-120][$i%5];

```

Try it online!

## Expanded

```
<?=+$e; #Output zero 0 th value
for(;$i++<$argn;) # loop till reach input n
  echo _,$e+=[185,1,7-4*$e-log($e)^0,-17,-120][$i%5];
# Output and assign the next value in sequence

```

## Steps depending on mod 5 start with 1

1: plus 1

2: plus 7 minus 4 times last value minus natural logarithm of last value cast to int

3: minus 17

4: minus 120

0: plus 185

Natural logarithm

## PHP, 33 Bytes

prints a string representation

```
<?="[0,1,4,-13,-133,52,53,-155]";

```

Try it online!

# Answer
> 2 votes
# 05AB1E, 20 bytes

```
•3—ι]½ý.¢Σ”•6¡4'-:.¥

```

Try it online!

**Uses:** 16364176412061856164208

**Replace the 6's with commas (split on 6):** `['1', '3', '417', '4120', '185', '1', '4208']`

**Replace 4's with negative symbol:** `['1', '3', '-17', '-120', '185', '1', '-208']`

**Undelta.**

---

Simpler approach (turned out worse): `•5Û€ïÛ†!eŽΓ•8BR7¡6'-:`

# Answer
> 1 votes
# Jelly, 17 Bytes

```
153B-*“¡¢¥Æ⁵45ɓ‘×

```

Try it online!

**Explanation:**

```
153B-*

```

decode the signs from the binary digits of 153

```
“¡¢¥Æ⁵45ɓ‘

```

the magnitudes of the numbers represented as a code-page index list

```
×

```

elementwise multiplication

# Answer
> 1 votes
# Python 3, 37 bytes

```
for i in 'ÝÞáÐXđĒB':print(ord(i)-221)

```

# Answer
> 1 votes
# 05AB1E, 14 bytes

```
"ÈÉÌ»Cüý-"ÇƵ%-

```

Try it online!

**Explanation**

```
"ÈÉÌ»Cüý-"      # push this string
          Ç     # convert to code points
           Ƶ%-  # subtract 200 from each

```

### Previous 15 bytes solution

```
•∍ÉΣ-ú—("o•3ô¬-

```

Try it online!

**Explanation**

```
•∍ÉΣ-ú—("o•       # push the number 1551561591420222072080
           3ô     # split into pieces of 3
             ¬-   # subtract the first element from all elements

```

# Answer
> 1 votes
# Neim, 11 + 1 (`-n`) = 12 bytes

```
0γ4π./

```

Try here

Note: might not work in the future. For reference, this works for commit db32a5e.

Explanation:

```
0γ4π./ Push 0
 γ          Push 1
  4         Push 4
   π        Push 13
           Negate
           Push 133
           Negate
       .    Push 52
        /   Push 53
           Push 155
           Negate

```

# Answer
> 0 votes
## Mathematica, 79 bytes

```
s={-22,-83,408,-489,-25};i=2;While[i!=-1,t=Join[{i},Accumulate[s]+i];i--;s=t];s

```

Try it online!

in order to run on mathics the original code needs 2 more bytes

# Answer
> 0 votes
# \>\<\>, 26 bytes

```
'!ñð7¯À½¼'80g-nao90.

```

Standard unicode solution, same as the other answers. Sad I couldn't get to 25.

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


title: Number to letters

text:
# Question
Title: Number to letters
### Your task

Given a numerical string or integer \\$\ge 0\\$ (which may have leading zeros), convert it to letters using the below rules.

### Rules

Loop through the digits:

* If the digit is `0` or `1`, combine it with the next digit and output that letter of the alphabet (0-indexed).
* If the digit is `2`, combine with the next digit ONLY IF the next digit is between `0` and `5` (inclusive). Otherwise, output `c` (2nd letter of the alphabet, 0-indexed).
* If the digit is `3` or more, output that letter of the alphabet (0-indexed).

### Example

Our input is the number `12321`.

We loop through the digits:

* `1`: this is less than 2, so we keep this and wait for the next digit.
* `2`: combine with the previous digit, `1`, to get `12`. Index into the lowercase alphabet (0-indexed) to get `m`
* `3`: this is more than 2, so we output the 3rd letter of the alphabet (0-indexed), `d`
* `2`: this is 2, so we check the next digit. It is less than 6, so we wait.
* `1`: combine with the previous digit, `2`, to get `21`. Index into the lowercase alphabet (0-indexed) to get `v`

Our output is `mdv`.

### Test cases

#### Random

```
Input   Output
132918  ncjs
79411   hjel
695132  gjfnc
800125  iamf
530987  fdjih
144848  oeiei
93185   jdsf
922846  jwieg
187076  shhg
647325  gehdz

```

#### Edge-cases

```
Input  Output
0      a
1      b
25     z
26     cg
000    aa
123    md
0123   bx
1230   mda
12310  mdk
12345  mdef
00012  abc

```

Feel free to create your own test cases in this TIO of some ungolfed Python code.

### Clarifications

* Everything must be 0-indexed
* You cannot ignore leading 0s (see the 5th and 6th edge-cases)
* If the last digit is 0, 1, or 2, and it has not already been used by the previous digit, output "a", "b", or "c" respectively (see edge-cases)
* This is , so shortest answer in bytes wins.

# Answer
> 2 votes
# Nibbles, ~~17~~ 16.5 bytes (33 nibbles)

```
``;$$$:+`r<;?\`<`:"26"$$@"a"_>$@

```

```
``;                                 # launch recursive function:
   $                                # starting with input list of digits,
    $                               # stopping when argument is empty
     $                              #   and then returning the empty argument,
                                    # otherwise:
                `:"26"$             #   make a list of "26" and the argument string,
              `<                    #   sort this list of strings,
             \                      #   reverse it,
            ?          $            #   get the index of the argument in this,
           ;                        #   and save this as the number of elements
                                    #   to take from the argument (1 or 2);
          <                         #   now, take that many elements
        `r                          #   read this as an integer,
       +                "a"         #   add this to "a",
      :                             #   and append onto this
                           _        #   a recursive call with argument:
                            >$      #     drop the saved number of elements
                              @     #     from the current argument

```

See some more test & edge cases

# Answer
> 9 votes
# JavaScript (Node.js), 49 bytes

```
//                           we match all patterns consisting of either:
//              +----------> a '2' followed by '0' to '5', or
//              |      +---> any digit optionally preceded by '0' or '1'
//             _|__   _|__
//            /    \ /    \
s=>s.replace(/2[0-5]|[01]?./g,n=>Buffer([+n+97]))
//                               \_____________/
//                                      |
// and replace each of them with a <----+
// letter in lower case

```

Try it online!

# Answer
> 7 votes
# Python 3.8 (pre-release), 58 bytes

```
f=lambda s:s and chr(97+int(s[:(I:=1+(s<"26"))]))+f(s[I:])

```

Try it online!

This is based on the observation that we can simply compare the entire leftover string to "26" to decide whether to consume one or two characters.

# Answer
> 5 votes
# \>\<\> (Fish), 83 bytes

```
>i:0(?;'0'-:2(?v:2=?v'a'+o
^ o+'a'+-'0'i*a<
+'a'~$o'c'v?(6:-'0'i<.01o
1o+'a'+*a$<.0

```

Link

Top row is basic reading lines and exiting at the end. Red part at the end is the single digit case.

Middle row is the 0 or 1 case.

Bottom row 2 rows are the 2 case. Top branch is C, bottom is 2 digit number.

# Answer
> 5 votes
# Retina 0.8.2, 32 bytes

```
2[0-5]|[01]?.
$*#a
+T`##l`_l`#\w

```

Try it online! Link includes test cases. Explanation:

```
2[0-5]|[01]?.

```

Use @Arnauld's regex to identify the numbers from `0` to `25` inclusive.

```
$*#a

```

Replace each number with a string of that many `#`s followed by an `a`.

```
+T`##l`_l`#\w

```

Repeatedly cycle letters though the alphabet, decreasing the number of preceding `#`s each time, until there are no `#`s left.

# Answer
> 3 votes
# 05AB1E, 17 bytes

```
.œʒ€g3‹y₂‹«P}θAsè

```

Output as a list of characters.

Try it online or verify all test cases.

**Explanation:**

```
.œ                # Get all possible partitions of the (implicit) input
  ʒ         }     # Filter this list by:
   €       P      #  All parts in a partition
    g             #  Should have a length
     3‹           #  Less than 3
       y  «       #  And in addition should also all be
        ₂‹        #  Less than 26
            }θ    # After the filter: leave the last valid partition
              Asè # Index each inner index into the lowercase alphabet
                  # (after which this character-list is output implicitly as result)

```

# Answer
> 3 votes
# Ruby, 49 bytes

```
->s{eval ['""',*s.scan(/2[0-5]|[01]?./)]*"<<97+"}

```

Try it online!

# Answer
> 3 votes
# Excel (ms365), 169 bytes

```
=DROP(REDUCE(VSTACK(A1,""),SEQUENCE(LEN(A1)),LAMBDA(a,b,IFERROR(LET(x,LEFT(TAKE(a,1),2),y,IF(--x>25,LEFT(x),x),CHOOSE({1,2},RIGHT(a,LEN(a)-LEN(y)),a&CHAR(y+97))),a))),1)

```

The idea here is to use `REDUCE()` to iterate n-times (length of input) over this input and while doing so keep a shadow-record in the element next to given input with the alphabetic output while we check all numbers in order from left to right.

I do have a feeling this could be shortened though.

# Answer
> 3 votes
# K (ngn/k), ~~42~~ 38 bytes

-4 bytes thanks to @coltim

Uses loopy walt's recursive approach. There is probably some clever way to rewrite it using a fold.

It takes the length 2 prefix and compare it with 26 to decide if we convert 1 or 2 characters. After the conversion, it appends a recursive call on the remaining string.

```
{$[x;(`c$97+.n$x),o(n:1+26>.2$x)_x;x]}

```

Try it online!

# Answer
> 2 votes
# Jelly, 20 bytes

```
ŒṖẈṀ’ỊƲƇV<26Ạ$ƇṪ‘ịØa

```

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

# Answer
> 2 votes
# Charcoal, 24 bytes

```
Ｗθ«≔⊕‹θ26ι§β✂θ⁰ι≔✂θιＬθ¹θ

```

Try it online! Link is to verbose version of code. Explanation: Port of @loopywalt's Python solution.

```
Ｗθ«

```

Loop until the input is empty.

```
≔⊕‹θ26ι

```

Determine how many digits to extract.

```
§β✂θ⁰ι

```

Output the appropriate letter.

```
≔✂θιＬθ¹θ

```

Slice off those digits.

# Answer
> 2 votes
# C (clang), ~~85~~ 75 bytes

* -7 thanks to jdt
* -3 thanks to ceilingcat

Takes strings to preserve leading zeroes.

```
f(*o,*s,u){for(;u=*s++;)*o++=97+((u-=48)>2|u==2&*s>53|!*s?u:u*10+*s++-48);}

```

Try it online!

# Answer
> 2 votes
# C (clang), 64++ bytes

```
u;f(*o,*s){for(;u=*s++;)*o++=*s<54<u-49|!*s?49+u:u*10-431+*s++;}

```

Try it online!

If the output not being null-terminated is a problem, it's 1 extra byte to write to `stdout`:

```
u;f(*s){for(;u=*s++;)putchar(*s<54<u-49|!*s?49+u:u*10-431+*s++);}

```

Try it online!

# Answer
> 1 votes
# sclin, 32 bytes

```
"2[0-5]|[01]?."\; /#
"&":97+ c>S

```

Try it here! Port of @Arnauld's answer.

For testing purposes:

```
["132918""79411""695132""800125""530987""144848""93185""922846""187076""647325""0""1""25""26""123""0123""1230""12310""12345"] \>S map ; n>< n>o
"2[0-5]|[01]?."\; /#
"&":97+ c>S

```

# Answer
> 1 votes
# jq -Rr, 43 bytes

```
[scan("2[0-5]|[01]?.")|tonumber+97]|implode

```

Try it online!

# Answer
> 1 votes
# \>\<\>, ~~54~~  50 bytes

```
ic%:a)?v}
<v+*a  ~!
^>"a"+o>:2(}:2=}$:@6({*{+l2)*?

```

Try it online!

**Explanation**

`ic%:a)?v}`
Get all the input, mod each by **12** to get numbers and reorder it in the input order.

```
v
~
>

```

Then discard the end-of-input-byte.

If we call the top of the stack **x** and the 2nd top value of the stack **y** then:

`:2(}:2=}$:@6({*{+l2)*?`
**If (x \< 2 or (x == 2 and y \< 6)) and len(stack) \> 1**

`<v+*a ~!`
**Then x = x * 10 + y**

`"a"+o`
Print **x + 97** as a character.

# Answer
> 0 votes
# Python 3, ~~73~~ 71 bytes

```
lambda s:re.sub('2[0-5]|[01]?.',lambda c:chr(97+int(c[0])),s)
import re

```

Try it online!

Uses Arnauld's Regex expression.

# Python 3, 117 bytes

```
f=lambda n:n and(chr(97+int(n[:2]))+f(n[2:])if n[0]in'01'or n[0]=='2'and int(n[1])<6 else chr(97+int(n[0]))+f(n[1:]))

```

Try it online!

Recursive `lambda` function.

# Python 3, 135 bytes

```
def f(n):
 if n=='':return''
 d=n[0]
 if d in'01'or d=='2'and int(n[1])<6:a,b=n[:2],n[2:]
 else:a,b=d,n[1:]
 return chr(97+int(a))+f(b)

```

Try it online!

Recursive `def` function.

# Python 3, 212 bytes

```
def f(n,i=0,o='',c=lambda s:chr(97+int(s))):
 while i<len(n)-1:
  d=n[i]
  if d in'01':i+=1;o+=c(d+n[i])
  elif d=='2'and int(n[i+1])<6:i+=1;o+=c(d+n[i])
  else:o+=c(n[i])
  i+=1
 if i<len(n):o+=c(n[i])
 return o

```

Try it online!

Iterative `def` function.

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


# Question
Title: Find the nth Fibonacci number, where n is the mth Fibonacci number
# Introduction

If \\$\newcommand{\fib}{\operatorname{fib}}\fib(x)\\$ calculates the \\$x\\$th Fibonacci number, write a program that calculates \\$\fib(\fib(m))\\$ for any integer value of \\$m \ge 0\\$. (Of course, there will be practical limits based on the language, so lesser limits are acceptable. Also, it's okay to stop at \\$m = 20\\$, even if the language could in theory go higher.) Any means of calculation is acceptable.

# Challenge

Write a program or function, in as few bytes of code as possible, that for any given positive integer input, will return the same output as function `fibfib` in the following Python code:

```
fibs = [0, 1]

def fib(n):
    global fibs

    while len(fibs) <= n:
        fibs.append(fibs[-2]+fibs[-1])

    return fibs[n]

def fibfib(m):
    return fib(fib(m))

```

You do not have to use the same or a similar algorithm; the output just has to be the same.

# Example Input and Output

```
 0 -> 0
 1 -> 1
 2 -> 1
 3 -> 1
 4 -> 2
 5 -> 5
 6 -> 21
 7 -> 233
 8 -> 10946
 9 -> 5702887
10 -> 139583862445
15 -> 13582369791278266616906284494806735565776939502107183075612628409034209452901850178519363189834336113240870247715060398192490855
20 -> 2830748520089123910580483858371416635589039799264931055963184212634445020086079018041637872120622252063982557328706301303459005111074859708668835997235057986597464525071725304602188798550944801990636013252519592180544890697621702379736904364145383451567271794092434265575963952516814495552014866287925066146604111746132286427763366099070823701231960999082778900856942652714739992501100624268073848195130408142624493359360017288779100735632304697378993693601576392424237031046648841616256886280121701706041023472245110441454188767462151965881127445811201967515874877064214870561018342898886680723603512804423957958661604532164717074727811144463005730472495671982841383477589971334265380252551609901742339991267411205654591146919041221288459213564361584328551168311392854559188581406483969133373117149966787609216717601649280479945969390094007181209247350716203986286873969768059929898595956248809100121519588414840640974326745249183644870057788434433435314212588079846111647264757978488638496210002264248634494476470705896925955356647479826248519714590277208989687591332543300366441720682100553882572881423068040871240744529364994753285394698197549150941495409903556240249341963248712546706577092214891027691024216800435621574526763843189067614401328524418593207300356448205458231691845937301841732387286035331483808072488070914824903717258177064241497963997917653711488021270540044947468023613343312104170163349890

```

# Answer
> 9 votes
# Jelly, ~~4~~ 3 bytes

```
ÆḞ⁺
```

Attempt This Online!

```
ÆḞ⁺
  ⁺ # Twice:
ÆḞ  # Nth fibonacci

```

*-1 byte thanks to Unrelated String*

# 05AB1E, 4 bytes

```
ÅfÅf

```

Try it online!

```
ÅfÅf
Åf   # Nth fibonacci
  Åf # Nth fibonacci

```

# flax, 4 bytes

```
;f;f

```

```
;f;f
  ;f # Nth fibonacci
;f   # Nth fibonacci

```

Try it online!

# Actually, 2 bytes

```
FF

```

Try it online!

```
FF
F  # Nth fibonacci
 F # Nth fibonacci

```

# Answer
> 6 votes
# Factor \+ `benchmark.fib3`, 37 bytes

```
[ [ 0 ] [ 1 - fib 1 - fib ] if-zero ]

```

Try it online!

## Huh?

Factor comes with a suite of benchmarks. One of these is to implement the fibonacci function in seven different ways. *Naturally*, `fib` is the shortest one of these; it has an off-by-one error, it doesn't handle 0 correctly, and it's very slow because it uses the naive recursive algorithm.

Regardless of these problems, fixing them is still shorter than rolling our own. If we were to do so, however, it would only cost 3 more bytes:

# Factor \+ `combinators.extras`, 40 bytes

```
[ [ 0 1 rot [ tuck + ] times . ] twice ]

```

Try it online!

# Answer
> 5 votes
# Wolfram Language (Mathematica), 20 bytes

```
Nest[Fibonacci,#,2]&

```

Try it online!

Slightly shorter than the naive `Fibonacci@Fibonacci@#&`.

# Answer
> 5 votes
# , 50 bytes

```
function(n,s=5^.5,`?`=round)?((r=s/2+.5)^?r^n/s)/s

```

Try it online!

Adapted from J.Doe's answer to the Fibonacci function or sequence.
Based on the closed-form formula for the fibonacci sequence, applied to itself.
The chance to assign the function (`round`) and variable (`s/2+.5`) that will be re-used means that we can re-perform the closed-form calculation on itself for less bytes than a 'trivial' adaption of simply appending a 'do it twice' function `;g=function(n)f(f(n))` (even in  ≥4.1 where defining a new function can be much golfier using `\` instead of `function` \*).

---

Note that a shorter  solution to the older challenge is user5957401's answer, which can be further golfed-down to ~~25~~ 23 bytes\**: `repeat show(F<-T+(T=F))`. However, as a full program, this is less easy to 'do it twice'.
If we re-arrange it into function form (`function(n){while(n<-n-1)T=F+(F=T);T}`), we can exploit the fact that the answer is already assigned to a variable to conditionally return this, or run the function again on this, for ~~60~~ 58 bytes: `f=function(n,m=T){while(n<-n-1)T=F+(F=T);`if`(m,f(T,0),T)}`.
This is again shorter than simply appending a 'do it twice' function, but longer than the closed-form approach above (although appending a 'do it twice' function wins in  ≥4.1 \*).

Finally, plannapus's answer (golfed-down by Robert S.) used the classic recursive approach. When adapted to run twice this is only one byte longer than the modified shortest fibonacci answer, with 59 bytes: `f=function(n)`if`(n<3,1,f(n-1)+f(n-2));g=function(n)f(f(n))`.
Boringly, though, this one *is* just the 'trivial' adaptation of appending `;g=function(n)f(f(n))`.

**Thanks to pajonk for pointing out the golfing differences when using  ≥4.1*
\***23-byte fibonacci function inspired by Giuseppe's answer here*

# Answer
> 5 votes
# , ~~49~~ 45 bytes\* \*(you can actually score like 14 but that's *boring*)

*-4 bytes thanks to ovs!* (also thanks for this for 33 bytes, which uses newer J features!)

```
1{,@f=:{&(2 2 2$#:151x)`(-&2+/ .*&f<:)@.(>&1)

```

Try it online! Uses the matrix method mentioned on the OEIS page.

## Explanation

*This applies to the less golfed version, but fundamentally remains the same. I will continue to explain the less golfed version as it is more intuitive what is going on.*

```
f=:{&(2 2 2$#:151x)`(-&2(+/ .*)&f<:)@.(>&1)
1{,@f

```

First, we define a helping verb `f` which recursively computes the matrix. `f` consists of two part: seed generation and recursion calculation. If the input is greater than 1 (`>&1`), then (`@.`) we calculate recursion; otherwise, we call the seed function. As I think it looks nicer by replacing the current `f` with the recursive verb `$:`, I shall explain that version, though they remain functionally equivalent.

```
f=:{&(2 2 2$#:151x)`(-&2(+/ .*)&$:<:)@.(>&1)
   <-----seed-----> <---recursion--->
   <-----seed----->                     if not(input > 1):
   {&(            )                       index the input into the following array
            #:151x                          get the bits of 151 (1 0 0 1 0 1 1 1)
      2 2 2$                                and create a 2x2x2 array
                                          the result is 1 0,:0 1 for 0, and 0 1,:1 1 for 1
                    <---recursion--->   if input > 1:
                    (-&2          <:)     compute input-2 and input-1
                        (     )&$:        call this verb on each, then
                         +/ .*            perform matrix multiplication

```

Since, however, `f` computes a matrix, and we are only interested in one member of that matrix, our actual verb is the last line `1{,@f`, which simply takes the top-right element of the matrix.

# * , 14 bytes

```
(+/@:!&i.-)^:2

```

Try it online!

Of course, the first highlighted method is *much* longer than taking the trivial approach of modifying the existing shortest Fibonacci in J thanks to @miles and applying it twice. While this approach is about ~30x slower than the first, it's the length which matters. Nonetheless, I consider it trivial, which is why it is not the most-featured solution in my answer.

# Answer
> 4 votes
# Haskell, 24 bytes

The single-Fibonacci part was borrowed from R. Martinho Fernandes.

```
map(f!!)f
f=0:scanl(+)1f

```

Try it online!

# Answer
> 4 votes
# JavaScript (Node.js), 115 bytes

```
f=n=>n<4?n+3n>>2n:(f(--n)**2n-(u=-1n)**(F=y=>y<2?y:F(--y)+F(--y))(n-=2n)*f(--n)*f(n+=3n)-u**F(--n)*f(--n)**2n)/f(n)
```

Attempt This Online! (includes benchmark)

Way longer than Radvylf's, but is way, way, faster. ATO for Radvylf's with benchmark, which times out.

Formula found at this paper.

# Python, 131 bytes

```
f=lambda n:n>3and(f(n-1)**2-(-1)**F(n-3)*f(n-4)*f(n-1)-(-1)**F(n-2)*f(n-3)**2)//f(n-3)or n+3>>2
F=lambda y:y>1and F(y-1)+F(y-2)or y
```

Attempt This Online!

Same concept.

# Answer
> 4 votes
# Python NumPy, 66 bytes

```
lambda n:ptp(x**ptp(x**n))
from numpy import*
x=mat("1 1;1 0","O")
```

Attempt This Online!

While this isn't really competitive (the `numpy import` is just too expensive, as is setting up the auxiliary matrix) I thought this is interesting. Perhaps it can be ported to one of the other matrix languages.

How?

The standard recurrence `a,b <---| a+b,a` can be conveniently expressed by the matrix \\$ M = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \\$. Doing n iterations then is as easy as taking the n-th power: $$ M^n = \begin{pmatrix} F\_{n+1} & F\_n \\ F\_n & F\_{n-1} \end{pmatrix} $$

Thus we could simply do `(x**(x**n)[0,1])[0,1]`. We save a few bytes using `ptp` instead which in turn uses that `F_n = F_n+1 - F_n-1`. (Note that this incorrectly returns 1 for input `0` because `F_-1` breaks the pattern `F_n <= F_n+1`, so ptp does not pick the right elements in that case.).

# Answer
> 3 votes
# Vyxal, 5 bytes

```
2(‹∆f

```

Try it Online!

## How?

```
2(‹∆f
2(    # Execute twice:
  ‹   # Decrement to make this 0-indexed
   ∆f # Nth fibonacci number

```

# Answer
> 3 votes
# SageMath, 28 bytes

```
lambda n,f=fibonacci:f(f(n))

```

Try it online!

# Answer
> 3 votes
# Husk, 4 bytes

```
‼!İf

```

Try it online!

```
‼     # twice = apply function twice:
 !    #   index = value at index (of input) of
  İ   #   infinite sequence of
   f  #   fiboncci numbers

```

# Answer
> 3 votes
# MathGolf, 2 bytes

```
ff

```

Try it online!

```
ff
f  # Nth fibonacci
 f # Nth fibonacci

```

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

```
#@*#&@Fibonacci

```

Try it online!

```
      Fibonacci     fib
#@*#&@                fib ∘ fib (composition)

```

# Answer
> 2 votes
# JavaScript (Node.js), 35 bytes

```
x=>(f=y=>y<2?y:f(--y)+f(--y))(f(x))

```

Simple recursive solution (now intended for use with bigints, thanks to Steffan for pointing out that's necessary).

# Answer
> 2 votes
# Python, 47 bytes

```
from sympy import*
lambda n,g=fibonacci:g(g(n))
```

Attempt This Online!

Without builtin:

# Python, 52 bytes

```
lambda n:g(g(n))
g=lambda y:y>1and g(y-1)+g(y-2)or y
```

Attempt This Online!

# Ruby, 39 bytes

```
->n{(g=->y{y>1?g[y-1]+g[y-2]:y})[g[n]]}
```

Attempt This Online!

# Answer
> 2 votes
# C (gcc) with `-lgmp` and `-m32`, ~~266~~ ~~265~~ ~~259~~ 241 bytes

* -1 thanks to ceilingcat
* -6 thanks to MackTuesday

As no native type supports `f(f(20))`, I used GMP for the math. Uses iteration to compute the Fibonacci sequence.

```
#import<gmp.h>
#define q mpz_set
f(i,r){mpz_t k,l,s,t;for(mpz_inits(k,l,s,t,0);mpz_cmp(k,i)<1;mpz_add_ui(k,k,1))mpz_cmp_ui(k,1)>0?mpz_add(l,s,t),q(s,t),q(t,l):q(mpz_get_ui(k)?t:s,k);q(r,t);}g(i,r){mpz_t a;mpz_init_set_ui(a,i);f(a,r);f(r,r);}

```

Unfortunately, TIO doesn't have the 32-bit version of GMP installed so it's 259 bytes in 64-bit mode:

```
#import<gmp.h>
#define q mpz_set
f(i,r)mpz_t i,r;{mpz_t k,l,s,t;for(mpz_inits(k,l,s,t,0);mpz_cmp(k,i)<1;mpz_add_ui(k,k,1))mpz_cmp_ui(k,1)>0?mpz_add(l,s,t),q(s,t),q(t,l):q(mpz_get_ui(k)?t:s,k);q(r,t);}g(i,r)mpz_t r;{mpz_t a;mpz_init_set_ui(a,i);f(a,r);f(r,r);}

```

Try it online!

Ungolfed (without GMP, assuming `int` is big enough):

```
int f(int i) {
  int j[2]={0}, k=0, l;

  for(; k<i+1; k++)
    if(k<2) j[k]=k;
    else {
      l=j[0]+j[1];
      j[0]=j[1];
      j[1]=l;
    }

  return j[1];
}

int g(int i) { return f(f(i)); }

```

# Answer
> 2 votes
## Batch, 123 bytes

```
@set/af=h=0,g=i=1
@for /l %%a in (1,1,%1)do @set/aj=h+i,h=i,i=j
@for /l %%a in (1,1,%h%)do @set/ah=f+g,f=g,g=h
@echo %f%

```

Explanation: Regular Batch variable expansion with `%` happens before the line is parsed, so the `%h%` has to be on a separate line to the code that sets `h`, but `set/a` is a special case and can access the current value of variables so works fine inside a loop.

# Answer
> 2 votes
# Desmos, ~~49~~ 45 bytes

```
pp-p~1
f(n)=(p^n-(1-p)^n)/5^{.5}
g(n)=f(f(n))

```

Just applies Binet's Formula twice. Did not include the last two test cases as the output is too large for Desmos to handle.

Try It On Desmos!

Try It On Desmos! - Prettified

# Answer
> 2 votes
# Octave, 32 bytes

```
@(n,m=[1 1;1 0])(m^(m^n)(2))(2);

```

Try it online!

Port of my Python answer.

# Answer
> 1 votes
# Retina 0.8.2, 42 bytes

```
.+
$*
+`11(1*)
1$1,$1
,

+`11(1*)
1$1,$1
1

```

Try it online! Note: Very slow, so will probably time out on TIO for inputs more than `8`. Explanation: Based on my Retina 0.8.2 answer to Fibonacci function or sequence.

```
.+
$*

```

Convert to unary.

```
+`11(1*)
1$1,$1

```

Recursively replace `n` with `n-1` and `n-2`, until each unary integer has been replaced down to `1` and `0`.

```
,

```

Sum the `1`s in unary, resulting in the Fibonacci of the input.

```
+`11(1*)
1$1,$1

```

Calculate the Fibonacci of the Fibonacci.

```
1

```

Sum and convert to decimal.

# Answer
> 1 votes
# Retina, 41 bytes

```
2{K`0,1
"$-1"+`\d+,(\d+)
$1,$.(*_$1*
,.+

```

Try it online! Link includes test cases. Explanation:

```
2{

```

Repeat the whole program twice.

```
K`0,1

```

Replace the input with the two integers `0` and `1`.

```
"$-1"+`

```

Repeat the number of times given by the stage before the previous stage. On the first iteration this is the input, while on the second it is the result of the first loop.

```
\d+,(\d+)
$1,$.(*_$1*

```

Replace the first integer with the second and the second with their sum.

```
,.+

```

Delete the second integer.

# Answer
> 1 votes
# Charcoal, 27 bytes

```
ＮθＦ²«≔Ｅ²κυＦθ≔⟦⌈υΣυ⟧υ≔⌊υθ»Ｉθ

```

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

```
Ｎθ

```

Input `n`.

```
Ｆ²«

```

Repeat twice.

```
≔Ｅ²κυ

```

Start with the two integers `0` and `1`.

```
Ｆθ

```

Repeat `n` times.

```
≔⟦⌈υΣυ⟧υ

```

Replace the first integer with the second and the second with their sum.

```
≔⌊υθ

```

Save the first integer for the next pass or the result.

```
»Ｉθ

```

Output the result.

Although the above code calculates the result quickly enough for inputs of `n` up to about `20`, here is a 42-byte version which is fast even for large values of `n`:

```
≔⮌Ｅ²Ｅ³¬⁼ιλυＦＮ⊞υＥ³ΣＥ²ΠＥ…⮌υ²§ξ⁺ν⊘⁺λπＩ§§υ±²¦¹

```

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

```
≔⮌Ｅ²Ｅ³¬⁼ιλυ

```

Start with \\$ ((F\_{F\_0-1}, F\_{F\_0}, F\_{F\_0+1}), (F\_{F\_1-1}, F\_{F\_1}, F\_{F\_1+1})) \\$ which is `[[1, 0, 1], [0, 1, 1]]`.

```
ＦＮ

```

Repeat `n` times.

```
⊞υＥ³ΣＥ²ΠＥ…⮌υ²§ξ⁺ν⊘⁺λπ

```

Calculate \\$ (F\_{F\_{i+2}-1}, F\_{F\_{i+2}}, F\_{F\_{i+2}+1}) \\$ from the previous terms. There are a number of ways of doing this e.g. \\$ F\_{F\_{i+2}-1} = F\_{F\_i-1}F\_{F\_{i+1}-1} + F\_{F\_i}F\_{F\_{i+1}} \\$.

```
Ｉ§§υ±²¦¹

```

Output the middle term of the penultimate result which is \\$ F\_{F\_n} \\$ as desired.

# Answer
> 1 votes
# Japt, 5 bytes

```
MgMgU

```

Try it here

# Answer
> 0 votes
# Raku, 27 bytes

```
[o] {(0,1,*+*...*)[$_]}xx 2

```

Try it online!

* `0, 1, *+* ... *` is the lazy, infinite Fibonacci sequence.
* `[$_]` looks up a number in the sequence by its index.
* `{ ... }` wraps the lookup in an anonymous function.
* `xx 2` replicates that function twice, producing a list of two elements.
* `[o]` reduces that list with function composition.

# Answer
> 0 votes
# \>\<\>, 38 bytes

```
2>01@@:}@{?vrn;
:v? (1}-1:{<+@
-\{~~$1

```

Try it online!

# Answer
> 0 votes
# J-uby, 13 bytes

```
(:++[0,1])**2

```

Attempt This Online!

## Explanation

This is the standard J-uby Fibonacci function, `:+ + [0,1]` (start an array with `[0,1]` and apply `:+` (sum) to its last two items \\$n\\$ times), iterated on twice, i.e. `F**2`.

# Answer
> 0 votes
# Excel, 66 bytes

```
=LET(q,SQRT(5),f,ROUND((.5+q/2)^ROW(A:A)/q,),INDEX(f,INDEX(f,A1)))

```

Note: Excel will add a leading zero to `.5` to make it `0.5` when the formula is entered.

The main portion of this is generating the Fibonacci sequence (or at least the first 1,474 terms (after that Excel can't handle numbers that large (which also limits to input to values ≤ 16))). That's what this part does:

```
q,SQRT(5),f,ROUND((0.5+q/2)^ROW(A:A)/q,)

```

After that, we use `INDEX(f,INDEX(f,n))` as the equivalent to `fib(fib(n))`.

---
Tags: code-golf, sequence, integer, fibonacci
---


title: Make me some curry

text:
# Question
Title: Make me some curry
Having a function *f* that takes arguments *x1*, *x2*, …, *xn*

– ie. *f : X1 × X2 × … × Xn → Y*

currying redefines *f* as a function taking a single argument *a1* which maps to yet another function. This technique is useful for partial application, for example with a curried `pow` function we could write `exp = pow(e)`.

### Example

Assuming we have the following function *f* taking three arguments (*f : X1 × X2 × X3 → Y*):

```
def f(a,b,c):
  return a + b * c

```

Currying this function leaves us with *f\_curry: X1 → (X2 → (X3 → Y))*, if we would now call that function twice with `f_curry(1)(2)` we would get a function (`h`) equivalent to the following returned:

```
def h(c):
   return 1 + 2 * c

```

The curried function `f` could be written like this (Python 3):

```
def f_curry(a):
  def g_curry(b):
    def h(c):
      return a + b * c
    return h
  return g_curry

```

Try it online!

## Challenge

Your challenge will be to curry a function as described above, here are the rules:

* Input will be a blackbox function which takes at least 2 arguments
* The input function will always have a fixed number of arguments (unlike `printf` or similar, note: you need to support functions with any number of arguments ≥2)
* If your language uses curried functions by default (eg. Haskell), you may expect the input function to be defined over *N*-tuples, instead of a "higher-order function"
* You may take the number of arguments as input
* Output will be the input's curried equivalent*
* You may assume that the output function will only ever be:
    + called with less or equal to the number of arguments that the input function takes
    + called with arguments of the right type

---

* This would mean for an input `f` with `N` arguments and an output `h` that for all valid arguments `a1,…,aN` it holds that `f(a1,a2,…,aN) == h(a1)(a2)…(aN)`.

# Answer
## JavaScript (ES6), 35 bytes

```
f=g=>g.length<2?g:a=>f(g.bind(f,a))

```
> 12 votes

# Answer
# Idris, 204 bytes

```
import Data.HVect
C:(a:Vect n Type)->(HVect a->Type)->Type
C[]T=T[]
C(h::t)T=(x:h)->C t(T .(x::))
c:{a:Vect n Type}->{T:HVect a->Type}->((b:HVect a)->T b)->C a T
c{a=[]}f=f[]
c{a=h::t}f=\v=>c(\u=>f(v::u))

```

Try it online!

Sounds like a job for dependent types! Well, maybe.

---

**C** is a currying type function. Given a vector of types **a = \[t1, t2, … tn\]** and a type function **T : HVect a → Type**, it returns a new type:

> **(x1 : t1) → (x2 : t2) → … → (T \[x1, x2, … xn\])**

Here, **HVect** is the heterogeneous vector type from the Idris Prelude — the type of *n*-tuples whose elements are of *n* different types.

**c** is a function that takes **a** and **T** as implicit arguments, and then converts an *uncurried* function `f` of type **((b : HVect a) → T b)** into a *curried* one of type **C a T**.

(**C** simply describes what we wish to do; **c** actually does it. But we can't get away with not defining **C**, as Idris demands that every top-level definition have a type signature.)

---

The TIO link gives a usage example. If we define a function on 3-tuples **(Nat, Nat, String)** as follows:

```
uncurried : HVect [Nat, Nat, String] -> String
uncurried [a, b, c] = show (a*a + b*b) ++ c

```

then **`uncurried [3, 4, "th"]`** yields the same result as **`c uncurried 3 4 "th"`**. Idris infers the arguments `a=[Nat, Nat, String]` and `T=const String` for us, I believe.

I based this code on this gist by timjb.
> 12 votes

# Answer
# Python 3, ~~54~~ 53 bytes

```
c=lambda n,f,*x:lambda y:(f,c)[n>1](*1%n*(n-1,f)+x,y)

```

Try it online!
> 7 votes

# Answer
# , 96 bytes

```
y=function(f,n=length(formals(f)),p=list())function(x,u=c(p,x))`if`(n<2,do.call(f,u),y(f,n-1,u))

```

Try it online!

---

Previous version (97 bytes)

-1 byte thanks to @JayCE
> 7 votes

# Answer
# Coconut, 54 bytes

```
def c(f,*a):
 try:return f(*a)
 except:return c$(f,*a)

```

Try it online!

---

# Coconut, 40 bytes

Port of Erik's Python answer.

```
def c(f,n,*a)=n and c$(f,n-1,*a)or f(*a)

```

Try it online!
> 5 votes

# Answer
# C++~~17~~ 20, ~~214~~ ~~200~~ ~~189~~ 184 bytes

```
#include<regex>
template<class R,class A,class...B>auto c(std::function<R(A,B...)>f){if constexpr(sizeof...(B))return[=](A a){return c<R,B...>({std::bind_front(f,a)});};else return f;}

```

Try it on Wandbox (TIO doesn't support gcc 9+ which is needed for std::bind\_front)

This is a template function that takes an std::function of any arity/type and returns a curried lambda expression. Uses constexpr if FTW. If any template gurus have any idea how to eliminate or reduce the need for std::function let me know.

Edit: replaced inner lambda with std::bind\_front.
Edit: replaced include with shorter \<regex\>

Ungolfed version:

```
#include <functional>

template <class R, class A, class... B>
auto curry(std::function<R(A, B...)> f) {
    if constexpr(sizeof...(B) > 0) {
        return [=](A a) {
            return curry(std::function<R(B...)>{std::bind_front(f, a)});
        };
    } else {
        return f;
    }
}

```
> 5 votes

# Answer
# Python 2, 60 bytes

```
c=lambda f,n,l=[]:lambda a:n-1and c(f,n-1,l+[a])or f(*l+[a])

```

Try it online!

The footer is a tester which uses STDIN in the following way per line:

1. The function itself
2. The number of the function's arguments, ≥2
3. A list of the arguments (`[a,b,...]`)

Note that, while a list of the arguments is given as input in the tester, in reality, the curried equivalent gets prepended to the list and the list is reduced by function call.

A similar 55-byte version has been kindly provided by ovs:

```
c=lambda f,n,*l:lambda a:n-1and c(f,n-1,*l,a)or f(*l,a)

```

Try it online!
> 4 votes

# Answer
# Attache, 5 bytes

```
Curry

```

Try it online!

Simple built in, largely uninteresting. But, here's a version from scratch:

## Attache, 35 bytes

```
{If[#__2<#_,Fold[`&:,$'__],_@@__2]}

```

Explanation:

```
{If[#__2<#_,Fold[`&:,$'__],_@@__2]}
{                                 }    lambda
 If[       ,              ,      ]     if
    #__2                                 the number of parameters after the first
        <#_                              is less than the arity of the first
            Fold[   ,    ]             then fold:
                 `&:                     right-function bonding
                     $                     over this function
                      '__                  paired with the rest of the parameters
                          ,            otherwise:
                           _@@           call the first parameter
                              __2        with the rest of them

```
> 4 votes

# Answer
# Rust, 73 69 bytes

```
macro_rules!c{($f:tt$(($n:tt:$a:ty))*)=>{$(move|$n:$a|)*$f($($n),*)}}

```

Try it online!

Rust is statically typed and because of this taking in a function with an unknown number of arguments is not allowed. Fortunately, macros have no such restrictions. This macro takes in a function of the form `name(arg1:type1)(arg2:type2)...(argN:typeN)`. and outputs a function that outputs an appropriately long chain of `impl FnOnce`s that ends with the desired function call. I shaved a few bytes by changing the input form to something more natural with the question. Ungolfed version:

```
macro_rules! c{       //declare a macro named c
  (                   //match on
    $f:tt             //A token tree (should be an ident, but this is codegolf)
    $(                //followed by zero or more sequences of
      ($n:tt : $a:ty) //a token tree (again, should be ident) colon type in parentheses
    )*                //end repetition
  )=>{                //replace with
    $(move|$n:$a|)*   //FnOnce closure heads for every matched name:type
    $f(               //call initially matched function
      $($n),*         //with a comma separated list of closure argument names
    )                 //end call
  }                   //end rule
}                     //end macro

```
> 4 votes

# Answer
# Cauliflower, 84 bytes

```
(:= c(\($f$n(@a))(if$n(\($a)(call c(cat(list$f(-$n 1))@a(list$a))))else(call$f@a))))

```

Try it online!
> 3 votes

# Answer
# Java 8, 19 + 126 = 145 bytes

This is a curried (hah) lambda taking a function and an argument count and returning the curried function.

```
import java.util.*;

```

```
f->p->new C(){List a=new Stack();public Object f(Object r)throws Throwable{a.add(r);return a.size()<p?this:f.f(a.toArray());}}

```

Try It Online

## Submission type

The submission defines appropriate functional interfaces for the input and output functions. The definitions of the interfaces aren't included in the byte count because they only provide type information and don't contribute any code to the solution. (In fact, both of them are general enough that they could well have been included in the set of functional interfaces in the standard library.) For more details see the TIO.

## Usage

Because the submission returns a function (instance of `C`), the output may be invoked directly (with `f`), but subsequent intermediate return values must be cast to an appropriate type before being invoked. Consult the TIO for a usage example.

Note that in Java functions (i.e. methods) are not first-class objects. Thus the syntax used in the output bullet of the challenge description is meaningless in Java. Rather than `f(a1, a2, a3)` we have `f.f(a1, a2, a3)`, and rather than `f(a1)(a2)(a3)` we have `f.f(a1).f(a2).f(a3)` (modulo typecasting).

## Limitations

When an intermediate result is applied (an argument added), the result is actually a mutated copy of the original result. This violates the spirit of currying, but meets the specific requirement stated in the challenge.

The form of input functions is limited by the decision to use functional interfaces, since a fully general functional interface has to use variadics or otherwise pack function parameters, and as a result the implementors of the interface must do so as well rather than listing parameters in the standard fashion. Technically this might disqualify the solution, since it is possible to support fully general non-variadic multi-parameter input functions by invoking them using reflection. My solution using this strategy (taking a `java.lang.reflect.Method` instead of an instance of a functional interface thanks to @user) is a bit longer, so I stick with this one.

## Ungolfed

```
f -> p -> new C() {
    List a = new Stack();
    public Object f(Object r) throws Throwable {
        a.add(r);
        return a.size() < p ? this : f.f(a.toArray());
    }
}

```

## Acknowledgments

* -211 bytes thanks to ideas from KrystosTheOverlord
> 3 votes

# Answer
# Python 2, 78 bytes

```
c=lambda f,*a:f.func_code.co_argcount>len(a)and(lambda x:c(f,*a+(x,)))or f(*a)

```

Try it online!
> 2 votes

# Answer
# Perl 6, ~~42~~ 40 bytes

```
my&c={.count>1??{c(.assuming($^a))}!!$_}

```

Try it online!

-2 bytes thanks to Brad Gilbert b2gills.
> 2 votes

# Answer
# Haskell, ~~211~~ ~~209~~ ~~189~~ 163 bytes

Flags:

```
-XMultiParamTypeClasses
-XFlexibleInstances

```

Actual code (119 bytes):

```
class C a b c where c::(a->b)->c
instance C()b b where c f=f()
instance C a b c=>C(d,a)b(d->c)where c a b=c(\d->a(b,d))

```

Try it online!

The input type of the function to be curried is a nested tuple in a cons-like structure. The uncurried version of a function that adds 3 numbers together would look something like this, where it ends in an empty tuple.

```
myAdd :: (Int, (Int, (Int, ()) ) ) -> Int
myAdd (a, (b, (c, _))) = a + b + c

```

It works from the bottom up. There's an instance to curry a function of type `() -> r` that just applies the empty tuple to the function. Then there's another instance of `C` that can curry a function of type `(a,b)->c` if there is already an instance of `C` for `b -> c`.

Here's an `uncurr` function to accompany the currying function:

```
class Uncurry a b c d where
  uncurr :: (a->b)->c->d

instance Uncurry a r (a,()) r where
  uncurr f (a,()) = f a

instance Uncurry a b c d => Uncurry e (a->b) (e,c) d where
  uncurr f (e,c) =(uncurr(f e) c)

```

Try it online!
> 2 votes

# Answer
# Wolfram Language (Mathematica), 5 bytes

Good ol' Mathematica built-ins

```
Curry

```

Takes 2 arguments, the function and the number of arguments.

Try it online!
> 2 votes

# Answer
# Julia 1.0, 40 bytes

```
f>n=n<2 ? f : ((x...)->y->f(x...,y))>n-1

```

Try it online!
> 2 votes

# Answer
# APL (Dyalog Classic), ~~58~~ 57 bytes

```
∇r←(a f g)x
:If a[1]=≢a
r←g 1↓a,x
:Else
r←(a,x)f g
:End
∇

```

Try it online!

Calling syntax (with curried function `g`, arguments `x1` through `x3`, and number of arguments `n`):

`((n x1 f g) x2) x3`

Requires `⎕IO←1`
> 1 votes

# Answer
# Julia 0.6, 48 bytes

```
c=(f,n,a=[])->n>1?x->c(f,n-1,[a;x]):x->f(a...,x)

```

Try it online!

Port of @EricTheOutgolfer's Python answer.
> 1 votes

# Answer
# Dotty, ~~345~~ ... ~~221~~ 186 bytes

```
def>[F,T,X](f:F)(using? :F TupledFunction T,e:T=>X)=e(?tupled f)
given[A]as((EmptyTuple=>A)=>A)=_(Tuple())
given[A<:Tuple,B,C,D](using t:(A=>B)=>C)as((D*:A=>B)=>D=>C)=f=>h=>t(c=>f(h*:c))

```

Try it in Scastie

**This will not work in Scala 3.0 as `TupledFunction` will be removed.** However, it may be added back later.

This one doesn't do any unsafe casting or other trickery.

`>` is the method to call. The type parameters `F`, `T`, and `X` represent the type of the input function, the type of the input function if it took a single tuple instead of multiple arguments, and the type of the resulting curried function, respectively. The first parameter, `f`, is the function to be curried. There are also two implicit parameters, `?` and `e`. `?` is a `TupledFunction` object that can convert between `F` and `T`, i.e., tuple and untuple a function. It is provided in the standard library automatically, and makes it easier for `e` to do its work.

`e` operates on the tupled form of `f`. There's a base implicit function that takes an a function `EmptyTuple=>A` and returns an `A` by just passing an empty tuple to that function. Another `given` builds on top of that by deconstructing `f` into `D *: A => B` (`D` is the type of the first parameter of `f`, `A` is the type of the rest of the parameters as a tuple, and `B` is the type of `f`'s result). It uses another implicit function of type `(A => B) => C`, where `C` is the curried version of `A => B`. This second case returns a function taking a `D` and then applying `t` to a new function where the `D` from before is cons-ed to an `A` before applying `f` to it.

## Dotty, 144 bytes

```
def a[T](x:Any)=x.asInstanceOf[T]
def c[T,R](f:T=>R,n:Int):Any=>Any=h=>a(n match{case 1=>f(a(Tuple1(h)))case _=>c(t=>f(a(h*:a[Tuple](t))),n-1)})

```

Try it in Scastie

Requires function to be tupled beforehand.
> 1 votes

# Answer
**Java 8... Using lambda insanity, 152 bytes**

Ok so I know that there is already a java 8 answer, but I wanted to use one using almost entirely lambdas without the use of java's Function\<\> class.

Here is the functional interface for the lambda expressions

```
interface K{Object f(int...x);}

```

And here is the actual expression

```
a->a.length==2?(K)c->a[0]+a[1]*c[0]:a.length==3?a[0]+a[1]*a[2]:(K)b->(b.length == 1)?(K)c->a[0]+b[0]*c[0]:a[0]+b[0]*b[1];

```

Yeah, so I know this looks really crazy, but the latter is mainly just using ternary operators to distinguish different number of arguments to what needs to be returned.

Given the submitted function

```
K function = a->a.length==2?(K)c->a[0]+a[1]*c[0]:a.length==3?a[0]+a[1]*a[2]:(K)b->(b.length == 1)?(K)c->a[0]+b[0]*c[0]:a[0]+b[0]*b[1];

```

`function(a, b, c)` is `function.f(a, b, c)`, `function(a)(b)(c)` is `((K)((K)function.f(a)).f(b)).f(c)`

Basically any situation that results in a curried result, the answer must be cast to `(K)` so then it can have a function called on it, otherwise the result is an integer. You can even do the following! `(function(a))(a,b)` which would be `((K)function.f(a)).f(b,c)` etc...

This probably took me way too long, and we already have a java 8 answer, but I feel like it is still an interesting way to go about it.
> 1 votes

# Answer
**Lispy, 169 bytes**

```
(define f(lambda A(begin(define G(lambda(X)(if(>=(length X)C)(proc:apply(head A)X)(lambda Args(G(concat X Args))))))(define C(length(lambda:args(head A))))(G(tail A)))))

```

Implements the generic abritrary ES5 currying algorithm on Rosetta Code.

Ungolfed and test:

```
(begin
;; f is a lambda that captures all arguments
(define f (lambda Arguments (begin            ;; function extraCurry(f) {
    (define F (head Arguments))
    (define A (tail Arguments))
    (define _curry (lambda (XS)               ;; function _curry(xs) {
        (if (>= (length XS) intArgs)          ;; xs.length >= intArgs ?
            (proc:apply F XS)                 ;;   f.apply(null, xs)
            (lambda Args                      ;; : function() {
                (_curry (concat XS Args)))    ;; return _curry(xs.concat([].slice.apply(arguments)))
        )
    ))
    (define intArgs (length (lambda:args F))) ;; intArgs = f.length
    (_curry A)                                ;; return _curry([].slice.call(arguments, 1))
)))

(define product3 (lambda (a b c) (* a b c)))

;; [14, 28, 42, 56, 70, 84, 98, 112, 126, 140]
(print (map [1 2 3 4 5 6 7 8 9 10] (((f product3) 7) 2))))

```

Try online link coming soon.
> 1 votes

# Answer
# Factor, 6 bytes

```
ncurry

```

Try it online!

Builtin.

A non-trivial implementation might be:

```
[ [ curry ] times ]

```

Currying is a pretty uncomplicated affair in a concatenative language. :)
> 1 votes

# Answer
# Ruby, 12 bytes

Ruby has a built-in method `curry` which can be called on a lambda that gives the desired behavior. The below code returns a lambda that calls `curry` on its argument.

```
proc &:curry

```

Attempt This Online!
> 1 votes

---
Tags: code-golf, functional-programming
---


title: Generate some rough numbers

text:
# Question
Title: Generate some rough numbers
# Background

A number `n` can be described as `B`-rough if all of the prime factors of `n` strictly exceed `B`.

# The Challenge

Given two positive integers `B` and `k`, output the first `k` `B`-rough numbers.

# Examples

Let `f(B, k)` be a function which returns the set containing the first `k` `B`-rough numbers.

```
> f(1, 10)
1, 2, 3, 4, 5, 6, 7, 8, 9, 10

> f(2, 5)
1, 3, 5, 7, 9

> f(10, 14)
1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59

```

# Answer
> 5 votes
# Python 3, ~~80~~, 75 bytes

```
lambda B,k:[i for i in range(1,-~B*k)if all(i%j for j in range(2,B+1))][:k]

```

Try it online!

Thanks to *shooqie* for saving 5 bytes.

This assumes that the k'th B-rough number will never exceed \\$B * k\\$, which I don't know how to prove, but seems like a fairly safe assumption (and I can't find any counterexamples).

Alternate solution:

# Python 2, 78 bytes

```
B,k=input()
i=1
while k:
 if all(i%j for j in range(2,B+1)):print i;k-=1
 i+=1

```

Try it online!

This solution does *not* make the above solution. And is much more efficient.

# Answer
> 5 votes
# Haskell, ~~53~~ 44 bytes

```
b%k=take k[n|n<-[1..],all((>0).mod n)[2..b]]

```

Try it online!

*Thanks to H.PWiz for -9 bytes!*

```
b%k=                       -- given inputs b and k
 take k                    -- take the first k elements from
  [n|n<-[1..]              -- the infinite list of all n > 0
   ,all            [2..b]] -- where all numbers from 2 to b (inclusive)
      ((>0).mod n)         -- do not divide n.

```

# Answer
> 3 votes
# Perl 6, ~~35~~ 32 bytes

*-3 bytes thanks to nwellnof!*

```
{grep(*%all(2..$^b),1..*)[^$^k]}

```

Try it online!

An anonymous code block that takes two integers and returns a list of integers.

### Explanation

```
{                              }  # Anonymous code block
 grep(             ,1..*)        # Filter from the positive integers
      *              # Is the number
       %             # Not divisible by
        all(      )  # All of the numbers
            2..$^b   # From 2 to b
                         [^$^k]   # And take the first k numbers

```

# Answer
> 3 votes
# Jelly, 7 bytes

```
1Æf>Ạɗ#

```

Try it online!

# Answer
> 3 votes
# Husk, ~~9~~ 8 bytes

```
↑foΛ>⁰pN

```

Try it online!

Takes \\$B\\$ as first and \\$ k \\$ as second input.

```
↑         -- take the first k elements
       N  -- from the natural numbers
 f        -- filtered by
  o   p   -- the prime factors
   Λ>⁰    -- are all larger than the first input

```

# Answer
> 2 votes
# Jelly, 10 bytes

```
1µg³!¤Ịµ⁴#

```

Try it online!

### How it works

```
1µg³!¤Ịµ⁴#    Dyadic main link. Left = B, right = k
       µ⁴#    Take first k numbers satisfying...
  g             GCD with
   ³!¤          B factorial
      Ị         is insignificant (abs(x) <= 1)?
1µ            ... starting from 1.

```

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

Takes input as `(b)(k)`.

```
b=>k=>(o=[],n=1,g=d=>(d<2?o.push(n)==k:n%d&&g(d-1))||g(b,n++))(b)&&o

```

Try it online!

### Commented

```
b => k => (             // input = b and k
  o = [],               // o[] = output array
  n = 1,                // n = value to test
  g = d => (            // g = recursive function, taking the divisor d
    d < 2 ?             // if d = 1:
      o.push(n) == k    //   push n into o[] and test whether o[] contains k elements
    :                   // else:
      n % d && g(d - 1) //   if d is not a divisor of n, do a recursive call with d - 1
    ) ||                // if the final result of g() is falsy,
    g(b, n++)           // do a recursive call with d = b and n + 1
)(b)                    // initial call to g() with d = b
&& o                    // return o[]

```

# Answer
> 2 votes
# Charcoal, 33 bytes

```
ＮθＮη≔⁰ζＷ‹Ｌυη«≦⊕ζ¿¬Φθ∧κ¬﹪ζ⊕κ⊞υζ»Ｉυ

```

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

```
ＮθＮη

```

Input `B` and `k`.

```
≔⁰ζ

```

Set `z` to 0.

```
Ｗ‹Ｌυη«

```

Repeat until we have `k` values.

```
≦⊕ζ

```

Increment `z`.

```
¿¬Φθ∧κ¬﹪ζ⊕κ

```

Divide `z` by all the numbers from `2` to `B` and see if any remainder is zero.

```
⊞υζ»

```

If not then push `z` to the predefined empty list.

```
Ｉυ

```

Cast the list to string and implicitly output it.

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

```
b=>g=(k,i=1,j=b)=>k?j>1?i%j?g(k,i,j-1):g(k,i+1):[i,...g(k-1,i+1)]:[]

```

Try it online!

# Answer
> 1 votes
# APL(NARS), 52 chars, 104 bytes

```
r←a f w;i
r←,i←1⋄→3
i+←1⋄→3×⍳∨/a≥πi⋄r←r,i
→2×⍳w>↑⍴r

```

Above it seems the rows after 'r←a f w;i' have names 1 2 3;test:

```
  o←⎕fmt
  o 1 h 2
┌2───┐
│ 1 2│
└~───┘
  o 1 h 1
┌1─┐
│ 1│
└~─┘
  o 10 h 14
┌14───────────────────────────────────────┐
│ 1 11 13 17 19 23 29 31 37 41 43 47 53 59│
└~────────────────────────────────────────┘

```

# Answer
> 1 votes
# 05AB1E, 9 bytes

```
∞ʒÒ¹›P}²£

```

Try it online or verify all test cases.

**Explanation:**

```
∞          # Infinite list starting at 1: [1,...]
 ʒ    }    # Filter it by:
  Ò        #  Get all prime factors of the current number
   ¹›      #  Check for each if they are larger than the first input
     P     #  And check if it's truthy for all of them
       ²£  # Leave only the leading amount of items equal to the second input

```

# Answer
> 0 votes
# Ruby, 56 bytes

```
->b,k{(1..).lazy.reject{|n|
(2..b).any?{n%_1<1}}.take k}

```

Attempt This Online!

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


# Question
Title: Calculate Pi unto a point using the Nilakantha series
Your task: given a nonzero positive number `i`, calculate pi using the Nilakantha series unto `i` terms.

The Nilakantha series is as follows:

$$\text 3 + \frac{4}{2 \times 3 \times 4} - \frac{4}{4 \times 5\times 6}+\frac{4}{6 \times 7 \times 8} - ...$$

3 is the first term, `4/2*3*4` is the second, `-4/4*5*6` is the third, and so on.

Notice that for the nth term:

* $$\text S\_1 = 3$$
* $$\text S\_n = \frac{4 \times (-1)^n}{2n \times (2n-1) \times (2n-2)}$$
* The approximation of pi by summing up these terms is $$\text S\_1 +\text S\_2\text + … +\text S\_n$$

Test cases:

```
In = Out

1 = 3
2 = 3.16666666667
3 = 3.13333333333
4 = 3.1452381

```

Notice the pattern of the numbers approximating towards pi.

Floating point issues are OK.

This is so shortest answer wins!

**EDIT**: by default this is 1-indexed, but if you want 0-indexed no problem, just mention it. And even infinitely printing the approximations with no input is Okay.

**EDIT 2**: Why some activity here?

# Answer
# Jelly, 13 bytes

```
RḤrƝP€4÷Ṛḅ-+3

```

A monadic Link that accepts a positive integer and yields the approximation (up to the floating point accuracy).

**Try it online!**

### How?

```
RḤrƝP€4÷Ṛḅ-+3 - Link: positive integer, n  e.g. 4
R             - range                           [1,2,3,4]
 Ḥ            - double                          [2,4,6,8]
   Ɲ          - for neighbours:
  r           -   inclusive range               [[2,3,4],[4,5,6],[6,7,8]]
    P€        - product of each                 [24,120,336]
      4÷      - four divided by those           [1/6,1/30,1/84]
        Ṛ     - reverse                         [1/84,1/30,1/6]
         ḅ-   - convert from base -1            sum([1/84,-1/30,1/6])=0.14523809523809522
           +3 - add three                       3.14523809523809522

```
> 6 votes

# Answer
# Python 3.8 (pre-release), 38 bytes (@xnor)

```
f=lambda n,i=.5:i//n/n or 2/i-f(n,i+1)

```

Try it online!

### Python 3.8 (pre-release), 40 bytes (@xnor)

```
f=lambda n,i=1:i//2//n/n or 4/i-f(n,i+2)

```

Try it online!

### Python, 45 bytes

```
f=lambda n,s=1:4/(2*s-1)-(s//n/s or f(n,s+1))

```

Attempt This Online!

1-based. n has to be positive.

### Python, 50 bytes

```
f=lambda n,s=0:n and f(n-1,4/(n+n-1)-s-0**s/n)or s

```

Attempt This Online!

This uses \\$\frac 4 {2x(2x+1)(2x+2)} =\frac 1 x + \frac 1 {x+1} - \frac 4 {2x+1} \\$ and that inside the full sum the first two terms cancel.

1-based. Can handle 0.

# Python 3.8 (pre-release), 45 bytes (@xnor)

```
f=lambda n:0**n*3or(-1)**n/n/(n-~n)/~n+f(n-1)

```

Try it online!

### Python, 50 bytes

```
f=lambda n:0**n*3or 1/(n|1)/(~n-n)/(n%-2^n)+f(n-1)

```

Attempt This Online!

0-based.
> 11 votes

# Answer
# JavaScript (ES6), 32 bytes

This version is based on @loopy-walt's answer, golfed by @xnor.

```
f=(n,i=.5)=>i<n?2/i-f(n,i+1):1/n

```

Try it online!

---

# JavaScript (ES6), 39 bytes

```
f=n=>--n?f(n)+(4-n%2*8)/(n+=n)/++n/~n:3

```

Try it online!

### Commented

```
f = n =>          // f is a recursive function taking the input n
--n ?             // decrement n; if it's not 0:
  f(n) +          //   do a recursive call and add:
  (4 - n % 2 * 8) //     -4 if n is odd, +4 otherwise
  / (n += n)      //     divided by 2n
  / ++n           //     divided by 2n + 1
  / ~n            //     divided by -(2n + 2)
:                 // else:
  3               //   end of recursion: return the integer part

```
> 6 votes

# Answer
# Factor \+ `koszul math.unicode`, <sup> ~~68~~ </sup> 64 bytes

```
[ ""3 rot [0,b) [ -1^ 4 reach Π / * + [ 2 v+n ] dip ] each ]

```

Attempt This Online!

0-indexed. Note the string literal has the control characters 2, 3, and 4 embedded, making it equivalent to the sequence `{ 2 3 4 }`. You can see these characters on ATO.

```
              ! 3
""            ! 3 { 2 3 4 }
3             ! 3 { 2 3 4 } 3
rot           ! { 2 3 4 } 3 3
[0,b)         ! { 2 3 4 } 3 { 0 1 2 }
[ ... ] each     <<for each element in { 0 1 2 }...>>
                 <<first iteration>>
              ! { 2 3 4 } 3 0
-1^           ! { 2 3 4 } 3 1
4             ! { 2 3 4 } 3 1 4
reach         ! { 2 3 4 } 3 1 4 { 2 3 4 }
Π             ! { 2 3 4 } 3 1 4 24
/             ! { 2 3 4 } 3 1 1/6
*             ! { 2 3 4 } 3 1/6
+             ! { 2 3 4 } 3+1/6
[ 2 v+n ] dip ! { 4 5 6 } 3+1/6
                 <<second iteration>>
              ! { 4 5 6 } 3+1/6 1
                 <<and so on>>

```
> 5 votes

# Answer
# 05AB1E, ~~20~~ 16 bytes

```
3λè®Nm4*N·2Ý-P/+

```

Outputs the 1-based \\$n^{th}\\$ value (by starting with \\$a(0)=3\\$ and where \\$a(1)\\$ is calculated as \\$3\\$ as well).

Try it online or verify the infinite sequence.

**Explanation:**

```
 λ         # Start a recursive environment,
  è        # to calculate a(input)
           # (which is output implicitly afterwards)
3          # Start with a(0)=3
           # Where every following a(n) is calculated by:
           #  (implicitly push the previous term a(n-1))
   ®Nm     #  Push (-1) to the power n
      4*   #  Multiply it by 4
   N·      #  Push 2n
     2Ý    #  Push list [0,1,2]
       -   #  Subtract each from the 2n: [2n,2n-1,2n-2]
        P  #  Take the product of this triplet: 2n*(2n-1)*(2n-2)
   /       #  Divide the earlier 4*(-1)**n by this (2n*(2n-1)*(2n-2))
    +      #  Add it to the previous term a(n-1)

```
> 3 votes

# Answer
# Vyxal , 19 bytes

```
ƛune4*nd:‹:‹**/;∑3+

```

flag to print rationals in their decimal form

**Explanation:**

```
ƛune4*nd:‹:‹**/;∑3+
ƛ              ;      Map lambda through inclusive range 1 to input
 une                  Push -1 to the power n
    4*                Multiply by 4 and push that
      nd:             Multiply n by 2 and duplicate
         ‹:           Decrement and duplicate
           ‹**        Decrement and push product of denominator
              /       Divide 4*(-1)**n by 2n*(2n-1)*(2n-2)
                ∑3+   Sum list and add 3

```

Try it Online!
> 3 votes

# Answer
# , 51 bytes

```
\(k,n=2:k*2)`if`(k>1,3+sum(4*1i^n/n/(n-1)/(n-2)),3)

```

Attempt This Online!

Uses the fact that \\$(-1)^n=i^{2n}\\$.

---

### , 51 bytes

```
\(k,n=2:k)`if`(k>1,3+sum((-1)^n/n/(2*n-1)/(n-1)),3)

```

Attempt This Online!

Uses the formula but with simplifying the fraction to \\$\frac{(-1)^n}{n(2n-1)(n-1)}\\$.
> 3 votes

# Answer
# \>\<\>, 36 bytes

Prints the infinite sequence

```
23:nao$:1+$:2%8*4$-$2*:1-:1-**,{+10.

```

Try it online!

# \>\<\>, 41 bytes

Generates the **nth** term

```
3$v ;n~<
1->:2(?v::2%8*4$-$2*:1-:1-**,{+}

```

Try it online!
> 3 votes

# Answer
# C (gcc), <sup>~~80~~ \\$\cdots\\$ ~~71~~</sup> 70 bytes

```
i;float s,m;float f(n){for(m=4,s=i=3;i++<2*n;s-=m/i/~-i/(i++-2))m=-m;}

```

Try it online!

*Saved ~~5~~ 6 bytes thanks to Kevin Cruijssen!!!*
*Saved 4 bytes thanks to Arnauld!!!*
> 2 votes

# Answer
# Desmos, 36 bytes

```
f(x)=3+∑_{n=2}^x(-1)^n/n(2nn-3n+1)

```

Try it on Desmos!

Near direct copy of the definition, simplified and rearranged only a little bit. 1 indexed.

Breakdown:

```
f(x)=3+∑_{n=2}^x(-1)^n/n(2nn-3n+1)  full function

f(x)=                               function definition (not sure if required)
     3+                             3 plus
       ∑                            The sum from
        _{n=2}                        n=2
              ^x                      to n=x
                                      (note that this defaults to 0 if x is less than 2)
                                    of
                (-1)^n                -1 when n is odd, 1 if n is even
                      /               divided by
                       n(2nn-3n+1)    2n^3-3n^2+n

```
> 2 votes

# Answer
# Vyxal `ḋr`, 14 bytes

```
Ḣƛd2ʀεΠ4/;uβ3+

```

Try it Online!

```
Ḣ              # range(2, n)
 ƛ       ;     # map...
     ε         # Difference of...
  d            # 2x
   2ʀ          # [0, 1, 2]
      Π        # Take the product
       4/      # 4 / that
          uβ   # Convert from base -1 (alternate signs)
            3+ # Add 3

```
> 2 votes

# Answer
# Python 3, 49 bytes

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

```

Try it online!

-5 bytes thanks to Mukundan314
> 1 votes

# Answer
# Wolfram Language (Mathematica), ~~36~~ 35 bytes

```
3.-Sum[(-1)^n/(2n^3+3n^2+n),{n,#}]&

```

Try it online!

Alternatively, and more interestingly, we can express the partial sums in terms of a Lerch transcendent: 36 bytes

```
Pi+(-1)^#(1/#-2LerchPhi[-1,1,#+.5])&

```

Try it online!
> 1 votes

# Answer
# x86 32-bit machine code, ~~37~~ 33 bytes

```
D9 E8 D8 C0 D8 C0 D9 E8 F9 D9 E8 D8 F1 D9 E8 DE C2 D8 F1 D8 C0 F5 72 F5 DE E2 E2 ED DD D8 D9 E1 C3

```

Try it online!

Following the `fastcall` calling convention, this takes a number `i` in ECX and returns the sum of the first `i` terms on the FPU register stack.

In assembly:

```
f:  fld1
    fadd st(0), st(0)
    fadd st(0), st(0)   # Example execution for 2nd iteration
    fld1                # FPU register stack (left is bottom):
    stc                 # -3   2   (before)
r:  fld1                # -3   2   1
    fdiv st(0), st(1)   # -3   2   1/2
ir: fld1                # -3   2   1/2   1
    faddp st(2), st(0)  # -3   3   1/2
    fdiv st(0), st(1)   # -3   3   1/(2*3)
    fadd st(0), st(0)   # -3   3   2/(2*3)
    cmc                 #[Repeat the 4 instructions above, using an inner loop:
    jc ir               # -3   3   2/(2*3)   1
                        # -3   4   2/(2*3)
                        # -3   4   2/(2*3*4)
                        # -3   4   4/(2*3*4)
    fsubrp st(2), st(0) # 3+4/(2*3*4)   4
    loop r
    fstp st(0)
    fabs
    ret

```

Each iteration of the outer loop computes one term \\$\frac4{2n(2n+1)(2n+2)}\\$ and combines it in using the reverse-subtract instruction; as in my answer to a related problem, this handles the alternating signs, but leaves the result with the wrong sign for even `i`, which is corrected for by taking the absolute value at the end (because all the correct results are positive).

The first iteration, if left the same as later iterations, would contain a division by 0. This is prevented by setting CF to 1 at the beginning, so that the inner loop executes once instead of twice during the first iteration, and it computes \\$\frac2{1\cdot2}\\$ instead.
> 1 votes

# Answer
# Raku, 36 bytes

```
[\+] 3,{-4*($*=-1)/[*] ^3+2*++$}...*

```

Try it online!

This is an expression for the infinite sequence of partial sums. 3 is the first term of the sequence, and the curly braces enclose a generating expression for the subsequent terms.

* The dividend is `-4 * ($ *= -1)`. The `$` here is an anonymous state variable. The `*= -1` causes it to alternate between -1 and 1. (The first time the expression is evaluated, it's undefined, but since it's being multiplied, it defaults to the multiplicative identity element 1.) Multiplying that by -4 produces the sequence of dividends 4, -4, 4, -4, ....
* The divisor is `[*] ^3 + 2 * ++$`. `$` here is another anonymous state variable which the preincrement operator `++` causes to take on the values 1, 2, 3, ..., as it's evaluated for each term of the sequence. Multiplying that by 2 produces 2, 4, 6, .... Those even numbers are added to the range `^3`, which means the integers from 0 to 2, producing a sequence of ranges `2, 3, 4`, `4, 5, 6`, `6, 7, 8`, .... Then `[*]` multiplies those numbers together.

`[\+]` produces the sequence of partial sums of the terms.
> 1 votes

# Answer
# Fig, \\$18\log\_{256}(96)\approx\\$ 14.816 bytes

```
+3S\n2@Nere+r3hax4

```

Try it online!

Port of Vyxal. Beats both that and osabie, 1.8 bytes longer than Jelly. 0-indexed.

```
+3S\n2@Nere+r3hax4
               ax  # Range [1, n]
              h    # Double
            r3     # [0, 1, 2]
          e+       # Add ^ to every element of ^^
        er         # Product of each element
      @N           # Negate
    n2             # Every other element
   \             4 # Four divided by ^
  S                # Sum
+3                 # Add 3

```
> 1 votes

# Answer
# Charcoal, ~~22~~ 21 bytes

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

```
   Ｎ                     Input `n` as a number
  Ｅ                      Map over implicit range
     ι                   Current value
    ⎇                    If nonzero then
          ι              Current value
         ﹪               Modulo
           ²             Literal integer `2`
        ⊗                Doubled
       ⊖                 Decremented
      ∕                  Divided by
              ι         Current value
             ×          Multiplied by
                ι       Current value
               ⊕        Incremented
            ×           Multiplied by
                   ι    Current value
                  ⊗     Doubled
                 ⊕      Incremented
                     ³   Otherwise literal integer `3`
 Σ                       Take the sum
Ｉ                        Cast to string
                       Implicitly print

```

Edit: Saved 1 byte by adpating @pajonk's simplification.
> 0 votes

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


title: Self-contained powers

text:
# Question
Title: Self-contained powers
Given integer `n`, output the smallest exponent `e` greater than 1 such that `n^e` contains `n` as a substring.

For example, for `25`, the answer should be `2`, as `25 ^ 2 = 625`, which contains `25` as a substring, but the answer for `13` should be `10`, as `13 ^ 10 = 137858491849`, so `10` is the lowest exponent for which the result contains `13` as a substring.

# Rules

* Standard I/O rules
* Standard loopholes apply
* Shortest code in bytes wins
* `n` will always be an integer greater than `0`

# Test Cases

```
1 => 2   (1 ^ 2 = 1)
2 => 5   (2 ^ 5 = 32)
3 => 5   (3 ^ 5 = 243)
4 => 3   (4 ^ 3 = 64)
5 => 2   (5 ^ 2 = 25)
6 => 2   (6 ^ 2 = 36)
7 => 5   (7 ^ 5 = 16807)
8 => 5   (8 ^ 5 = 32768)
9 => 3   (9 ^ 3 = 729)
10 => 2  (10 ^ 2 = 100)
11 => 11 (11 ^ 11 = 285311670611)
12 => 14 (12 ^ 14 = 1283918464548864)
13 => 10 (13 ^ 10 = 137858491849)
14 => 8  (14 ^ 8 = 1475789056)
15 => 26 (15 ^ 26 = 3787675244106352329254150390625)
16 => 6  (16 ^ 6 = 16777216)
17 => 17 (17 ^ 17 = 827240261886336764177)
18 => 5  (18 ^ 5 = 1889568)
19 => 11 (19 ^ 11 = 116490258898219)
20 => 5  (20 ^ 5 = 3200000)
25 => 2  (25 ^ 2 = 625)
30 => 5  (30 ^ 5 = 24300000)
35 => 10 (35 ^ 10 = 2758547353515625)
40 => 3  (40 ^ 3 = 64000)
45 => 5  (45 ^ 5 = 184528125)
50 => 2  (50 ^ 2 = 2500)
55 => 11 (55 ^ 11 = 13931233916552734375)
60 => 2  (60 ^ 2 = 3600)
65 => 17 (65 ^ 17 = 6599743590836592050933837890625)
70 => 5  (70 ^ 5 = 1680700000)
75 => 3  (75 ^ 3 = 421875)
80 => 5  (80 ^ 5 = 3276800000)
85 => 22 (85 ^ 22 = 2800376120856162211833149645328521728515625)
90 => 3  (90 ^ 3 = 729000)
95 => 13 (95 ^ 13 = 51334208327950511474609375)
100 => 2 (100 ^ 2 = 10000)

```

Python script to generate the first 1000 answers

# Answer
> 4 votes
# Perl 6, 31 bytes

```
{$^a;first {$a**$_~~/$a/},2..*}

```

Try it online!

# Answer
> 4 votes
# , ~~69~~ 44 bytes

```
function(n,i=2){while(!grepl(n,n^i))i=i+1;i}

```

Anonymous function. Works on large `i` when `n` is converted to BigZ (see TIO). Thanks for teaching me something Giuseppe and digEmAll!

Try it online!

# Answer
> 3 votes
# JavaScript (ES6 / Node.js),  ~~41~~  40 bytes

*Saved 1 byte thanks to @Shaggy*

Takes input as a *Number* (works for \\$n\<15\\$) or a *BigInt* literal.

```
n=>(g=x=>`${x*=n}`.match(n)?2:-~g(x))(n)

```

Try it online!

# Answer
> 3 votes
# APL (Dyalog Unicode), ~~25~~ ~~23~~ 17 bytes

*-2 bytes thanks to @Erik the Outgolfer*

*-6 bytes thanks to @ngn*

*thanks to @H.PWiz for making the code not require a custom `⎕pp` (print precision)*

```
⊢⍟×⍣(∨/(⍕÷)⍷0⍕⊣)⍨

```

Try it online!

```
⊢⍟×⍣(∨/(⍕÷)⍷0⍕⊣)⍨
  ×⍣(          )⍨ generates a geometric progression by repeatedly multiplying the argument
                   by its original value
     ∨/(⍕÷)⍷0⍕⊣   the progression stops when this function, applied between the new and the
                   last old member, returns true
         ÷        the original argument (ratio between two consecutive members)
        ⍕         formatted as a string
           ⍷      occurrences within...
            0⍕    ...the formatted (with 0 digits after the decimal point)...
              ⊣   ...new member
     ∨/           are there any?
⊢⍟                use logarithm to determine what power of ⍵ we reached

```

# Answer
> 3 votes
# Pyth, 9 bytes

```
f}`Q`^QT2

```

Try it online!

# Answer
> 3 votes
# Python 2, ~~42~~ 41 bytes

<sup>-1 byte thanks to Ørjan Johansen (returning `y` directely)</sup>

```
f=lambda x,y=2:y*(`x`in`x**y`)or f(x,y+1)

```

Try it online!

## Explanation/Ungolfed

Recursive function trying from \\$2,3\dots\\$ until we succeed:

```
# Start recursion with y=2
def f(x,y=2):
    # If we succeed, we arrived at the desired y
    if `x` in `x**y`:
        return y
    # Else we try with next y
    else:
        return f(x, y+1)

```

Try it online!

# Answer
> 2 votes
# 05AB1E, 7 bytes

```
∞>.Δm¹å

```

Try it online!

Explanation:

```
∞>.Δm¹å  //full program
∞        //push infinite list, stack = [1,2,3...]
 >       //increment, stack is now [2,3,4...]
  .Δ     //find the first item N that satisfies the following
     ¹   //input
      å  //is in
    m    //(implicit) input **  N

```

# Answer
> 2 votes
# Brachylog, 8 bytes

```
;.^s?∧ℕ₂

```

Try it online!

### Explanation

```
;.^         Input ^ Output…
   s?       …contains the Input as a substring…
     ∧      …and…
      ℕ₂    …the Output is in [2,+∞)

```

# Answer
> 2 votes
**SAS, ~~71~~ 66 bytes**

Edit: Removed `;run;` at the end, since it's implied by the end of inputs.

```
data a;input n;e=1;do until(find(cat(n**e),cat(n)));e+1;end;cards;

```

Input data is entered after the `cards;` statement, like so:

```
data a;input n;e=1;do until(find(cat(n**e),cat(n)));e+1;end;cards;
1
2
3
4
5
6
7
8
9
10
11
12
13
14

```

Generates a dataset `a` containing the input `n` and the output `e`.

# Answer
> 1 votes
# Jelly, 7 bytes

```
2ẇ*¥@1#

```

Try it online!

# Answer
> 1 votes
# Clean, 99 bytes

```
import StdEnv,Text,Data.Integer
$n=hd[p\\p<-[fromInt 2..]|indexOf(""<+n)(""<+prod(repeatn p n))>=0]

```

Try it online!

If it doesn't need to work for giant huge numbers, then

# Clean, 64 bytes

```
import StdEnv,Text
$n=hd[p\\p<-[2..]|indexOf(""<+n)(""<+n^p)>=0]

```

Try it online!

# Answer
> 1 votes
# Java (OpenJDK 8), 84 bytes

Takes input as a String representing the number and outputs an int.

Most of the bytes come from the verbosity of the `BigDecimal` being needed to process the large numbers.

```
n->{int i=1;while(!(new java.math.BigDecimal(n).pow(++i)+"").contains(n));return i;}

```

Try it online!

---

**How it works**

This is fairly simple but I'll include the explanation for posterity;

```
n->{                                    // Lamdba taking a String and returning an int
    int i=1;                            // Initialises the count
    while(!                             // Loops and increments until
        (new java.math.BigDecimal(n)    // Creates a new BigDecimal from the input n
            .pow(++i)+"")               // Raises it to the power of the current count
            .contains(n)                // If that contains the input, end the loop
    );
    return i;                           // Return the count
}

```

# Answer
> 1 votes
# PARI/GP 49 bytes

```
f(n)=e=1;until(#strsplit(Str(n^e++),Str(n))>1,);e

```

Try it online!

# Answer
> 0 votes
# JavaScript (Node.js), 45 bytes

*Test cases taken from @Arnauld's answer*

```
a=>eval("for(i=1n;!(''+a**++i).match(a););i")

```

Try it online!

# Answer
> 0 votes
# Ruby, 37 bytes

```
->n,i=2{i+=1until/#{n}/=~"#{n**i}";i}

```

Try it online!

# Answer
> 0 votes
# Japt, 10 bytes

```
@pX søU}a2

```

Try it

# Answer
> 0 votes
# Python 3, ~~63~~ 58 bytes

```
def f(n,e=2):
	while str(n)not in str(n**e):e+=1
	return e

```

Try it online!

Python2 would probably be shorter, but I like using 3. Coming up wiht a lambda is difficult, but I'm trying a few things.

# Answer
> 0 votes
# Charcoal, 19 bytes

```
Ｗ∨‹Ｌυ²¬№ＩΠυθ⊞υＩθＩＬυ

```

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

```
Ｗ∨‹Ｌυ²¬№ＩΠυθ⊞

```

Repeat until the the list length is at least 2 and its product contains the input...

```
⊞υＩθ

```

... cast the input to integer and push it to the list.

```
ＩＬυ

```

Cast the length of the list to string and implicitly print it.

# Answer
> 0 votes
# C# (.NET Core), 104 89 bytes

```
a=>{int i=2;while(!(System.Numerics.BigInteger.Pow(a,i)+"").Contains(a+""))i++;return i;}

```

Try it online!

*-1 byte: changed for loop to while (thanks to Skidsdev)*
*-14 bytes: abused C#'s weird string handling to remove* `ToString()` *calls*

Need to use C#'s BigInteger library, as the standard numeric C# types (int, double, long, ulong, etc.) fail for some larger numbers (including 12, 15, and 17).

Ungolfed:

```
a => {
    int i = 2;                                          // initialize i

    while( !(System.Numerics.BigInteger.Pow(a,i) + "")  // n = a^i, convert to string
                                .Contains(a + ""))      // if n doesn't contain a
        i++;                                                // increment i

    return i;
}

```

# Answer
> 0 votes
# MathGolf, 10 bytes

```
ôkï⌠#k╧▼ï⌠

```

Try it online!

## Explanation

This feels extremely wasteful, having to read the input explicitly twice, having to increment the loop counter twice.

```
ô            start block of length 6
 k           read integer from input
  ï          index of current loop, or length of last loop
   ⌠         increment twice
    #        pop a, b : push(a**b)
     k       read integer from input
      ╧      pop a, b, a.contains(b)
       ▼     do while false with pop
        ï    index of current loop, or length of last loop
         ⌠   increment twice

```

# Answer
> 0 votes
# Ruby, 41 bytes

```
f=->n,a=n{(a*=n).to_s=~/#{n}/?2:1+f[n,a]}

```

Try it online!

# Answer
> 0 votes
# Python 2, 47 bytes

```
i,e=input(),2
while`i`not in`i**e`:e+=1
print e

```

Try it online!

Inspired by @Gigaflop's solution.

# Answer
> 0 votes
# Tcl, 69 ~~81~~ bytes

```
proc S n {incr i
while {![regexp $n [expr $n**[incr i]]]} {}
puts $i}

```

Try it online!

# Answer
> 0 votes
PowerShell(V3+), 67 bytes

```
function f{param($n)$i=1;do{}until([math]::pow($n,++$i)-match$n)$i}

```

# Answer
> 0 votes
# Common Lisp, 78 bytes

```
(lambda(n)(do((e 2(1+ e)))((search(format()"~d"n)(format()"~d"(expt n e)))e)))

```

Try it online!

# Answer
> 0 votes
# , 26 bytes

```
2>:@]^:(0=[+/@E.&":^)^:_~]

```

Try it online!

NOTE: I've changed the final `]` to `x:` in the TIO, to make the tests pass for larger integers.

# Answer
> 0 votes
# Oracle SQL, 68 bytes

```
select max(level)+1 from dual,t connect by instr(power(x,level),x)=0

```

There is an assumption that source number is stored in a table `t(x)`, e.g.

```
with t as (select 95 x from dual)

```

Test in SQL\*Plus

```
SQL> with t as (select 95 x from dual)
  2  select max(level)+1 from dual,t connect by instr(power(x,level),x)=0
  3  /

MAX(LEVEL)+1
------------
          13

```

# Answer
> 0 votes
# Ruby, 35 bytes

```
->n{(2..).find{"#{n**_1}"[n.to_s]}}

```

Attempt This Online!

# Answer
> 0 votes
# Burlesque, 19 bytes

```
J2R@?^jbxq~[_+fi2.+

```

Try it online!

```
J    # Duplicate input
2R@  # Range (2..)
?^   # (in^2, in^3, ...)
j    # Put input to head of stack
bx   # Box
q~[  # Quoted contains
_+   # Push together (contains input)
fi   # Find the index which contains input
2.+  # Add 2 (0-indexed and 1 dropped)

```

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


title: Shortest path between two directories

text:
# Question
Title: Shortest path between two directories
The challenge is to write a program which will find the shortest (least number of characters) command which will navigate to a target directory, given a starting directory, assuming a standard linux file system.

Take the following file system as an example, starting from `~`:

```
.
├── target
└── test
    └── starting

```

If the user is in `~/test/starting` and wants to navigate to `~/target`, the shortest command is `cd ~/target`.

However, if the user is in `~/test/starting` and wants to navigate to `~/test`, the shortest command is `cd ..`

If the user wants to navigate to `~`, the shortest command is `cd ~`.

If the user wants to navigate to `/etc`, the shortest command is `cd /etc`.

**INPUT**

The input is two strings; the starting directory and the target directory. For example: `/etc/kernel` and `/opt`. The method and order these are input is up to you. (eg: array, list, arguments, input, etc)

**OUTPUT**

Print or return the shortest command which navigates to the target directory.

**SCORING**

Standard code golf rules.

**Some example test cases**

Input format is `starting` `target`

> Input: `~/a/b/c` `~/a/z`
>
> Output: `cd ~/a/z`

> Input: `~/apple/banana/carrot` `~/apple/banana/z`
>
> Output: `cd ../z`

> Input: `~/apple/banana/carrot` `/test`
>
> Output: `cd /test`

> Input: `/a/b` `/a/b/c`
>
> Output: `cd c`

> Input: `/a/b` `/a/b`
>
> Output: `cd .`

**CLARIFICATIONS**

* `~` is equivalent to `/home/golfer`
* Assume that inputs are already minimal. For example, you would not get `/home/golfer/a` as an input, and would instead get `~/a`
* The only aliases you need to worry about are `/` and `~`
* Shortest path from `~` to `/home` is `..`
* @loopywalt has pointed out that `cd` with no argument will navigate to `~`. This behaviour will be ignored, so please assume that an argument must always be specified.

# Answer
> 6 votes
# 05AB1E, ~~60~~ 56 bytes

```
Ëi'.ë'~’/€¨/’:'/©δ¡ζ.γË}¦˜2ôøðδK`®ýsg…../×ì®Ü}Iθ)éн…cd ì

```

-4 bytes thanks to *@JonathanAllan*

Inputs as a pair.

Try it online or verify all test cases.

**Explanation:**

```
Ëi              # If both paths in the (implicit) input-pair are the same:
  '.           '#  Push "."
 ë              # Else:
  '~      :    '#  In the strings of the (implicit) input-pair, replace all "~"
    ’/€¨/’      #  with dictionary string "/home/"
  '/©          '#  Push "/", and save it in variable `®` (without popping)
     δ          #  Map over the pair, with "/" as argument:
      ¡         #   Split the paths in the strings by this "/"
  ζ.γË}¦˜2ôøðδK #  Remove the matching path-prefixes:
  ζ             #   Zip/transpose; swapping rows/columns,
                #   using a " " as filler-character if the paths are of unequal length
   .γ }         #   Then group the pairs by:
     Ë          #    Check if the two values in the pair are the same
      }¦        #   After the group-by: remove the first group
        ˜       #   Flatten it to a single list
         2ô     #   Split it back into pairs
           ø    #   Zip/transpose these pairs back
             δ  #   Map over each inner list:
            ð K #    Remove all spaces
  `             #  Pop and push both lists separated to the stack
   ®ý           #  Join the second list with "/" delimiter
   s            #  Swap so the first list is at the top of the stack
    g           #  Pop and push its length
     …../×      #  Pop this length, and repeat string "../" that many times
   ì            #  Prepend it in front of the other string
    ®Ü          #  And trim a potentially trailing "/"
 }              # Close the if-else statement
  Iθ            # Push the second string of the input-pair
)               # Wrap all values on the stack into a list
 é              # Sort it by length
  н             # Pop and leave just the first/shortest one
   …cd ì        # Prepend "cd " in front of it
                # (after which the result is output implicitly)

```

See this 05AB1E tip of mine (section *How to use the dictionary?*) to understand why `’/€¨/’` is `"/home/"`.

# Answer
> 5 votes
# JavaScript (Node.js), 101 bytes

Expects `[ current_dir, target_dir ]`.

```
a=>'cd '+((s=require('path').relative(...a.map(s=>(q=s).replace(/~/,'/home/@')))||".")[q.length]?q:s)

```

Try it online!

---

# JavaScript (Node.js), 66 bytes

Expects `(current_dir)(target_dir)`.

Assumes a \*nix system where `~` redirects to `/home/some_user`. On TIO, `~` is `/home/runner/~`. So this may fail because of that.

```
a=>b=>'cd '+((s=require('path').relative(a,b)||".")[b.length]?b:s)

```

Try it online!

# Answer
> 5 votes
# Python 3, 81 bytes

```
lambda p:'cd '+min(relpath(*map(expanduser,p)),p[0],key=len)
from os.path import*

```

Try it online!

This utilizes the `os.path.relpath` function to get a relative path. The shortest path command is either the relative path or the absolute path, whichever is shorter, so the code just checks which using `min`. `expanduser` is used to expand the `~` directory to the user's home directory, which doesn't have to be `home/golfer` to meet the requirements. This is necessary to handle cases with `~` in the path name.

# Answer
> 1 votes
# Retina 0.8.2, 99 bytes

```
$
¶$%`
¶
/¶
m`^~(?=/.*¶)
/home/golfer
^(.*/)(.*¶)\1
$2
\G.*?/
../
1`¶

/¶
¶
O#$`
$.&
1G`
^$
.
^
cd

```

Try it online! Takes input on separate lines but link is to test suite that splits on space for convenience. Explanation:

```
$
¶$%`

```

Duplicate the last (to) line.

```
¶
/¶

```

Append `/` to the first two (original from and to) lines.

```
m`^~(?=/.*¶)
/home/golfer

```

Expand any leading `~` on the first two lines.

```
^(.*/)(.*¶)\1
$2

```

Remove any common prefix (ending in `/`) on the first two lines.

```
\G.*?/
../

```

Change any remaining "from" directories to `..`.

```
1`¶

```

Join those `..`s with the remaining "to" directories.

```
/¶
¶

```

Remove the trailing `/`.

```
O#$`
$.&

```

Sort numerically by length.

```
1G`

```

Take the first i.e. shortest string.

```
^$
.

```

If it's the empty string then replace it with `.`.

```
^
cd

```

Prefix `cd`  to the string.

# Answer
> 1 votes
# C# (Visual C# Interactive Compiler), 66 bytes

```
(a,b,c)=>"cd "+((c=Path.GetRelativePath(a,b)).Length<b.Length?c:b)

```

Try it online!

# Answer
> 0 votes
# Python, 87 bytes

```
lambda t,s:"cd "+[t,r:=relpath(t:=expanduser(t),s)][len(r)<len(t)];from os.path import*

```

Attempt This Online!

Expects `target, start`.

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