title: Am I a Secondary Taxicab?

text:
# Question
Title: Am I a Secondary Taxicab?
# Background

Ramanujan's number, \\$1729\\$, is called a taxi-cab number due to the (possibly apocryphal) tale of Hardy boarding a cab to visit Ramanujan in hospital having this number, which seemed bland to him.

It's since known as the most famous of a class of integers known as "taxicab numbers" which are expressible as the sum of two \\$n\\$th powers (of positive integers) in two (or sometimes \\$k\\$) different ways.

\\$1729\\$ is the smallest natural number expressible as the sum of 2 cubes in 2 different ways, making it the first \\$3,2\\$ taxicab number (\\$n,k\\$ being general).

# Challenge

Given a number, decide whether it is a \\$3,2\\$ 'secondary taxicab number' - meaning it fulfils the same constraint as \\$1729\\$ (2 unique sums of cubes), but does not have to be the smallest such integer of the \\$3,2\\$ class (that being 1729, of course).

### Example cases

$$1729 = 10^3 + 9^3 = 12^3 + 1^3 \\ 4104 = 15^3 + 9^3 = 16^3 + 2^3 \\ 13832 = 2^3 + 24^3 = 18^3 + 20^3$$

As well as \\$20683, 32832, 39312...\\$

# Scoring

This is , so the shortest answer in each language wins.

---

Rough Matlab code to find other cases by brute force:

```
for k = 1729:20000
    C = sum(round(mod(real((k-[1:ceil(k^(1/3))].^3).^(1/3)),1)*10000)/10000==1);
    if C > 1
        D = (mod(C,2)==0)*C/2 + (mod(C,2)==1)*((C+1)/2);
        disp([num2str(k),' has ',num2str(D),' solns'])
    end
end

```

# Answer
> 4 votes
# 05AB1E, 9 bytes

### Code (very slow)

```
L3mãOQO3›

```

### Code (much faster), 12 bytes

```
tL3mDδ+˜QO3›

```

Uses the **05AB1E** encoding. Try it online!

### Explanation

```
t                # Square root (not necessary but added for speed)
 L               # Create a list [1 .. sqrt(input)]
  3m             # Raise to the power of 3
    D            # Duplicate
     δ+          # 2 dimensional addition
       ˜         # Deep-flatten the entire list
        Q        # Check which are equal to the input
         O       # Sum up to get the number of equalities
          3›     # Checks whether there are 4 or more equalities. In order for a number
                   to be a secondary taxicab number, there are at least two distinct
                   ways to get to that number and 4 ways when you also take reversed
                   arguments in account.

```

# Answer
> 6 votes
# Jelly, 9 bytes

Credits to Erik the Outgolfer.

```
Œċ*3S€ċ>1

```

Try it online!

This is too slow that it won't even work for `1729` online.

## Much faster, 12 bytes

Credits to Dennis.

```
R*3fRŒċS€ċ>1

```

Try it online!

# Answer
> 5 votes
# Mathematica, 35 bytes

```
Count[#^3+#2^3&~Array~{#,#},#,2]>2&

```

Pure function taking a positive integer and returning `True` or `False`.

`#^3+#2^3&~Array~{#,#}` tabulates all sums of cubes of two integers between 1 and the input. (This would be much faster with a sensible bound on the integers to be cubed, like the cube root of the input; but that would take precious bytes. As it is, the code takes about 30 seconds on the input `13832` and scales at least quadratically in the input.) `Count[...,#,2]` counts how many times the input appears in this list at nest-level 2; if this number is greater than `2`, then the input is a semi-taxicab number (greater than 2, rather than greater than 1, since a^3+b^3 and b^3+a^3 are being counted separately).

# Answer
> 4 votes
# Mathematica, ~~38~~ 37 bytes

```
Tr[1^PowersRepresentations[#,2,3]]>1&

```

*-1 byte thanks to @GregMartin*

As always, there is a Mathematica builtin to everything.

# Answer
> 3 votes
# APL (dzaima/APL), 15 bytes

```
{4≤⍵⍧∘.+⍨3*⍨⍳⍵}

```

Try it online!

Same method as all the other answers. Only works till 4104 due to brute forcing.

more than 20 bytes golfed off with dzaima's help at the APL orchard.

The output appears with a ⊂ next to it, which has been patched in the latest version of the interpreter.

## Explanation

```
{4≤⍵⍧∘.+⍨3*⍨⍳⍵} ⍵ → input
         3*⍨⍳⍵  range 1 to n, cubed
     ∘.+⍨       dot product, addition with itself
   ⍵⍧           number of times ⍵ appears in the sums
 4≤             is 4 less than or equal to that?

```

# Answer
> 2 votes
# Mathematica, 48 bytes

```
Length@Solve[x^3+y^3-#==0<x<y,{x,y},Integers]>1&

```

**input**

> \[4104\]

**output**

> True

# Answer
> 2 votes
## JavaScript (ES7), 63 bytes

A relatively fast recursive function which eventually returns a boolean.

```
f=(n,k,r=0,x=n-k**3)=>x<0?r>3:f(n,-~k,r+=(x**(1/3)+.5|0)**3==x)

```

### Demo

```
f=(n,k,r=0,x=n-k**3)=>x<0?r>3:f(n,-~k,r+=(x**(1/3)+.5|0)**3==x)

console.log([...Array(40000).keys()].filter(n => f(n)))
```

# Answer
> 1 votes
# MATL (16 15 bytes) (13 12 ideally)

```
.4^:3^2XN!sG=sq

```

Try it online!

## Explanation:

Based on the Jelly solution of 'Leaky Nun', just converted to MATL, probably redundant in some parts and can be improved:

```
.4^  % rough cube root of input, as maximum potential integer N.
:3^   % create array of all cubes from 1^3 up to N^3.
2XN   % do nchoosek on cube array, creating all possible pairs (k=2) to add.
!s    % transpose array and add all pairs to find sums.
G=    % find all pairs that equal the original input.
sq   % if there is more than one solution, then pass the test.

```

Note: falsy outputs include 0 and -1, while truthy output is 1. Thanks to Luis Mendo for saving an extra byte here replacing "s1\>" with "sq".

## Ideally (13 12 bytes):

```
:3^2XN!sG=sq

```

...is enough, but for larger numbers this crashes on tio.run's page.

# Answer
> 1 votes
## Python, 71 bytes

Try it online

```
lambda x:len([i for i in range(x)for j in range(i,x)if i**3+j**3==x])>1

```

# Answer
> 0 votes
# Ruby, 52 bytes

```
->n{r=*1..n;r.product(r).count{|i,j|i**3+j**3==n}>1}

```

Try it online!

Since this version creates a massive n2 sized array, it fails on all true testcases higher than `1729`, here is a modified version that has a smaller array size of about n2/3, which successfully checks at least up to 31392.

Try it online! (modified)

# Answer
> 0 votes
# PHP, 76 bytes

```
for(;$i++<$argn**(1/3);)for($n=1;$n<$i;)$n++**3+$i**3!=$argn?:$c++;echo$c>1;

```

Try it online!

Search till 400000 Try it online!

# Answer
> 0 votes
# Perl 5 `-pa`, 49 bytes

```
$_=1<grep{//;grep$'**3+$_**3=="@F",$_.."@F"}1..$_

```

Try it online!

# Answer
> 0 votes
# Add++, 32 bytes

```
D,g,@,3^AR3€Ω^$€+
L,R€gb+A€=b+2=

```

Try it online!

The Footer in the TIO link is simply a faster version (`b+` \\$\to\\$ `BFB]`)

## How it works

```
D,g,@,		; Define a helper function, g
		; It takes an int;	STACK = [5]
	3^	; Cube;			STACK = [125]
	AR	; Argument range;	STACK = [125 [1 2 3 4 5]]
	3€Ω^	; Cube each;		STACK = [125 [1 8 27 64 125]]
	$€+	; Add the cube to each;	STACK = [[126 133 152 189 250]]

L,		; Define the main function
		; Takes an int;		STACK = [1729]
	R	; Range;		STACK = [[1 2 3 ... 1728 1729]]
	€g	; Run g over each;	STACK = [[[2] [9 16] ... ]]
	b+	; Concatenate;		STACK = [[2 9 16 ...]]
	A€=b+	; Count argument;	STACK = [2]
	2=	; Equals 2?		STACK = [1]

```

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


# Question
Title: Differences of MaxMin Divisor Pairs (DMDP)
# Let's talk about divisors...

Leaving out perfect squares (for a moment), all positive integers can be expressed as the **product** of 2 of their divisors. Quick example for `126`: Here are all the divisors of `126`

As you can see all the divisors can be paired. Here are what we will call the **Divisor Pairs**:
`[1, 126], [2, 63], [3, 42], [6, 21], [7, 18], [9, 14]`

For this challenge we will need only the **last pair of this list** (which is the **center pair** of the picture):
`[9,14]`.We will call this pair the **MaxMin Divisor Pair**.
The **Difference of MaxMin Divisor Pair** **(DMDP)** is the difference of the two elements of the pair which is `[9,14]=5`
One more example for `544`. The divisors are:

> \[1, 2, 4, 8, 16, **17, 32**, 34, 68, 136, 272, 544\]

and **DMDP(544)=15** because `32-17=15`

What about the **perfect squares**? All perfect squares have **DMDP=0**
Let's take for example `64` with divisors

> {1, 2, 4, **8**, 16, 32, 64}

As you can see in this case the **MaxMin Divisor Pair** is `[8,8]` which has `DMDP=0`
we are almost done..

# The Challenge

Given an integer `n>0`, output **how many integers less than or equal to** `10000`, **have DMDP less than** `n`

# Test Cases

***input -\> output***

```
1->100 (those are all the perfect squares)
5->492
13->1201
369->6175
777->7264
2000->8478
5000->9440
9000->9888
10000->10000
20000->10000

```

This is .Shortest answer in bytes **wins**.

# Answer
> 5 votes
## JavaScript (ES7), 60 bytes

```
f=(n,i=1e4,j=i**.5|0)=>i?i%j?f(n,i,j-1):(i/j-j<n)+f(n,i-1):0

```

Probably exceeds your recursion limit, so you might prefer the iterative version for 70 bytes:

```
n=>[...Array(1e4)].map(g=(j=++i**.5|0)=>i%j?g(j-1):k+=i/j-j<n,i=k=0)|k

```

# Answer
> 5 votes
# Java 8, ~~151~~ ~~111~~ ~~110~~ ~~101~~ 98 bytes

```
n->{int r=0,x=10000,i;for(;x-->0;r-=i-n>>-1)for(i=x;i-->1&&(x<i*i|x%i>0||(i=x/i-i)>i););return r;}

```

-10 bytes thanks to *@Nevay*.
-3 bytes thanks to *@ceilingcat*.

**Explanation:**

Try it here.

```
n->{                  // Method with integer as parameter and return-type
  int r=0,            //  Result-integer, starting at 0
      x=10000,        //  Index-integer `x` for the outer loop, starting at 10,000
      i;              //  Index-integer `i` for the inner loop, uninitialized
  for(;x-->0;         //  Loop `x` in the range (10000, 0]:
      r-=i-n>>-1)     //   If the MaxMin-Divisor Pair's difference is lower than the input,
                      //    add 1 to the result (after every iteration)
    for(i=x;i-->1     //   Inner loop `i` in the range (`x`, 1]:
        &&(x<i*i      //    If the current square of `i` is smaller than or equals to `x`,
           |x%i>0     //    and the current `x` is divisible by `i`:
           ||(i=x/i-i)//     Calculate the MaxMin-Division difference
             >i););   //     And stop the inner loop
  return r;}          //  After the loops, return the result

```

# Answer
> 4 votes
# Jelly, 13 bytes

1 byte thanks to Jonathan Allan.

```
ȷ4RÆDạU$Ṃ€<⁸S

```

Try it online!

# Answer
> 2 votes
# , 73 ~~77~~ bytes

Thanks to @Guiseppe for the 4 bytes

```
sum(sapply(1:1e4,function(x)min(abs((w=which(x%%1:x<1))-rev(w))))<scan())

```

Try it online!

Have lost the vectorize function to calculate the DMDP and is now using a sapply over the function. The truthies for items which are less than the input are summed for the result.

# Answer
> 2 votes
# Mathematica, 64 bytes

```
Count[Divisors~Array~1*^4,a_/;#+a[[i=⌈Tr[1^a]/2⌉]]>a[[-i]]]&

```

Try it on Wolfram Sandbox

## Usage

```
f = Count[Divisors~Array~1*^4,a_/;#+a[[i=⌈Tr[1^a]/2⌉]]>a[[-i]]]&

```

```
f[1]

```

> ```
> 100
>
> ```

```
f /@ {1, 5, 13, 369, 777, 2000, 5000, 9000, 10000, 20000}

```

> ```
> {100, 492, 1201, 6175, 7264, 8478, 9440, 9888, 10000, 10000}
>
> ```

## Explanation

```
Divisors~Array~1*^4

```

Generate the lists of divisors, from `1` to `10000`. (the lists of divisors are sorted automatically)

```
Count[ ..., a_/; ... ]

```

Count the occurrences of elements `a`, such that...

```
#+a[[i=⌈Tr[1^a]/2⌉]]>a[[-i]]]

```

`(input) + (left one of the middle element(s)) > (right one of the middle element(s))`  If there is only one middle element, left = right.

# Answer
> 2 votes
# 05AB1E, ~~19~~ ~~18~~ ~~17~~ ~~16~~ ~~15~~ 12 bytes

```
4°ƒNÑÂα{нI‹O

```

Try it online!

**Explanation**

```
4°ƒ            # for N in [0 ... 10**4] do:
   NÑ          # push divisors of N
     Â         # bifurcate
      α        # element-wise absolute difference
       {       # sort
        н      # pop the head (smallest difference)
         I‹    # is it smaller than the input?
           O   # sum the stack

```

# Answer
> 1 votes
# MATL, 20 bytes

```
1e4:"@Z\2Y"dJ2/)G<vs

```

The code times out in TIO. Here's an example run with the offline compiler:

```
>> matl 1e4:"@Z\2Y"dJ2/)G<vs
> 13
1201

```

# Answer
> 1 votes
# , 91 bytes

```
function(n)sum(sapply(1:1e4,function(x,d=(1:x)[x%%1:x<1])diff(d[median(seq(d))+.5*0:1]))<n)

```

Takes a different (worse) approach to computing the DMDP than MickyT's solution by using array indexing and `diff` to compute it. Alas.

Try it online!

# Answer
> 1 votes
# Mathematica, 78 bytes

```
(s=#;Tr[1^Select[Table[#2-#&@@Quantile[Divisors@i,{.5,.51}],{i,10^4}],#<s&]])&

```

# Answer
> 1 votes
# Mathematica, ~~119~~ 115 bytes

```
(n=#;Tr[1^Select[Last@#-First@#&/@(Take[Divisors@#,Round[{-.1,.1}+(1+Length@Divisors@#)/2]]&/@Range@10000),#<n&]])&

```

I *finally* got this thing working and I've been trying for the past half an hour. .\_.

## Example run

# Answer
> 1 votes
# Husk, 19 bytes

```
#ȯV<⁰Sz≠↔§f`¦ḣḣ□100

```

No TIO link, since it times out. This version uses 100 in place of 10000 and finishes in a couple of seconds.

## Explanation

Husk has no divisors built-in or support for scientific notation yet.

```
#ȯV<⁰Sz≠↔§f`¦ḣḣ□100  Input is n (accessed with ⁰).
               □100  Square of 100: 10000
              ḣ      Inclusive range from 1.
#                    Count number of elements for which
 ȯ                   this composition of 3 functions gives truthy result:
                       Argument k, say k = 12.
         §f`¦ḣ         Divisors of k:
             ḣ           Range: [1,2,3,..,12]
         §f              Filter by
           `¦            divides k: [1,2,3,4,6,12]
     Sz≠↔              Absolute differences of divisor pairs:
        ↔                Reverse: [12,6,4,3,2,1]
     Sz                  Zip with divisor list
       ≠                 using absolute difference: [11,4,1,1,4,11]
  V<⁰                  Is any of these less than n?

```

# Answer
> 1 votes
# Japt, ~~25~~ ~~19~~ 17 bytes

```
L²õÈâ ®aX/ZÃd<UÃè

```

Test it

---

## Explanation

Implicit input of integer `U`.

```
L²õ

```

Generate an array of integers (`õ`) from 1 to 100 (`L`) squared.

```
Èâ          Ã

```

Pass each through a function (where `X` is the current element) that generates an array of the divisors (`â`) of `X`.

```
®    Ã

```

Map over that array of divisors, where `Z` is the current element.

```
aX/Z

```

Get the absolute difference (`a`) of `Z` and `X` divided by `Z`.

```
d<U

```

Are any of the elements (`d`) in the resulting array less than `U`?

```
è

```

Count the truthy elements and implicitly output the result.

# Answer
> 1 votes
# Ruby, 62 bytes

```
->n{(1..1e4).count{|x|(1..x).any?{|i|1>x%i&&x/i<=i&&i-x/i<n}}}

```

Try it online.

# Answer
> 1 votes
# TI-BASIC, 46 bytes

Note that TI-BASIC is a tokenized language. Also, the E in line 2 is a small capital E, found by pressing 2ND+, .

```
Input A
DelVar DFor(B,1,E4
For(C,1,√(B
If not(fPart(B/C
B/C-C<A
End
D+Ans→D
End

```

Result will be in D, and Ans immediately after program execution. If it is to be displayed, adding two more bytes (newline and `Ans`) would suffice.

# Answer
> 0 votes
# Python 2, 134 bytes

```
lambda i:len(filter(lambda n:n<i,[reduce(lambda x,y:y-x,[[x,n/x]for x in range(1,int(n**.5+1))if n%x<1][-1])for n in range(1,10001)]))

```

Try it online!

Eugh... need to do *much* better.

# Answer
> 0 votes
# Python 2, 83 bytes

A bit on the slow side, uses 5 seconds per test case

```
lambda x:sum(x>min(abs(y/t-t)for t in range(1,y+1)if y%t<1)for y in range(1,10001))

```

Try it online!

# Answer
> 0 votes
# PHP, 94+1 bytes

```
for(;$n++<1e4;$c+=$d<$argn)if(($i=$n**.5)>~~$i){while($n%++$i);for($d=1;$n%--$i;)$d++;}echo$c;

```

Run as pipe with `-nR` or try it online.

# Answer
> 0 votes
# VB.NET (.NET 4.5) ~~116~~ 115 bytes

```
Function A(n)
For i=1To 10^4
Dim s As Byte=Math.Sqrt(i)
While i Mod s>0
s-=1
End While
A-=i/s-s<n
Next
End Function

```

---

Explanation:

A function that takes `n` as a parameter, and returns the result.

Starts at the square root, and looks for the nearest integer that evenly divides (will be the smaller of the `MaxMin Divisor Pair`). Then gets the larger of the pair (`i/s`), finds the difference, and compares against the input.

---

Golfing strategies used:

* `Dim` is expensive, so the fewer variables I declare the better.
* I start searching at the square root, but only want to look at integers. By declaring `s` as an integral type, it casts to the floor for me.
* VB uses `^` as exponent. So while `10000` is 5 characters, `10^4` is only 4.
* VB creates an automatic variable with the same name and type as the function definition (in my case A). At the end of the function, if there is no `return`, the value of the function variable will be returned instead. So I save characters by not declaring a separate variable and not using a return statement.
* VB has very forgiving typing/casting. `i` is assumed `Integer` because I assigned a integer literal. `A` is assumed `Object` but as soon as I add an integer, it behaves like an `Integer`.
* Rather than `if` checking the that the difference is satisfactory, add it directly to the result by casting the boolean to an integer. However, VB uses `-1` for `True`, so subtract to get the correct sign.
* Technically, we want `Mod` to not be `0`. Taking the modulus of a negative number in VB.NET will give a negative result. But, everything is positive so I can save a byte by turning `<>` into `>`.
* The largest number to check is 10000. The square root of that is 100. So I only need a `Byte` to store that, saving bytes in the declaration by using a shorter named type.

Try it online!

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

```
x=>{int o=0,i=1;for(;i<=10000;i++)for(int j=1;j<=i;j++)if(i%j<1&Math.Abs(j-i/j)<x){o++;break;}return o;}

```

Try it online!

# Answer
> 0 votes
# Wolfram Language (Mathematica), 52 bytes

```
Boole@Array[AtomQ@√(4a+#^2)&,#,0,Or]~Sum~{a,1*^4}&

```

Try it online!

Slow.

---
Tags: code-golf, division
---


# Question
Title: Divisor sum from prime-power factorisation
The task is to compute the divisor sum of a number given its prime factorisation.

### Input

Two arrays (or something equivalent) of length *n*, one containing the prime factor and the other containing the corresponding exponent.

### Output

The sum of all divisors (including the number itself).

### Example

The number 240 has 2, 3, and 5 as prime factors with 4, 1, and 1 as the respective exponents. The expected output would then be 744.

```
Input: [2,3,5] [4,1,1]
Output: 744

```

### Scoring

Shortest code in bytes wins!

If your solution's run time complexity is O(sum of exponents) rather than O(product of exponents), your score may be multiplied by 0.8.

---

There was a similar question posted here, but it wasn't a challenge. I think the problem is interesting enought to be golfed.

The winner will be choosen this weekend

# Answer
> 3 votes
# Pyth, 13 bytes * 0.8 = 10.4

```
*Fms^LhdhedCQ

```

Demonstration.

This answer works somewhat differently from those above. In order to calculate the sum of the factors of the prime powers of the number, instead of using an arithmetic formula, the factors are explictly constructed and summed.

For instance, on the \[prime, exponent\] pair `[2, 4]`, we map `2 ^ x` over `0, 1, 2, 3, 4`, giving `[1, 2, 4, 8, 16]`, which is then summed to 31.

The results are then multiplied together and printed.

If exponentiation is implemented properly, or if there is intermediate result caching, this will be `O(sum of exponents)`.

# Answer
> 9 votes
# CJam, 15 bytes * 0.8 = 12

```
q~.{_@)#(\(/}:*

```

Try it online. The input order is exponent list first, then list of primes *(-3 bytes thanks to @Dennis)*.

For each prime-exponent pair `(p, e)` find

```
(p^(e+1) - 1)/(p - 1)

```

then find the product of all of these. E.g. for 240 this would be

```
(1 + 2 + 4 + 8 + 16)(1 + 3)(1 + 5) = 31 * 4 * 6 = 744

```

Depending on how exponentiation is implemented, this can be better than `O(sum of exponents)`.

# Answer
> 6 votes
# APL, ~~18~~ 13 bytes * 0.8 = 10.4

```
×/(1-⊣×*)÷1-⊣

```

This creates a dyadic function train that takes the array of factors on the left and the exponents on the right.

```
×/             ⍝ Vector product of
  (1-⊣×*)      ⍝ each factor^(exponent+1)-1
         ÷1-⊣  ⍝ divided by factor-1

```

Try it online. Note that this is the same approach as Sp3000's awesomely clever CJam answer.

Saved 5 bytes thanks to Dennis!

# Answer
> 2 votes
# TI-BASIC, 17 bytes * 0.8 = 13.6

Also uses Sp3000's method, though I found it independently. Takes one list from Input and one from the homescreen.

```
Input E
prod(AnsAns^∟E-1)/prod(Ans-1

```

Using prod( twice is smaller because it lets us use the open parenthesis for free. Note that this answer does not support empty arrays, because there are no empty arrays in TI-BASIC.

# Answer
> 2 votes
# C++, 111 80 77 bytes * 0.8 = 61.6

```
int g(int*p,int*e,int n){return n?g(p+1,e+1,n-1)*(pow(*p,*e-1)-1)/(*p-1):1;}

```

This computes (p^(e+1)-1)/(p-1) and recursively multiplies all factors. Found that out myself a year ago.

Thank you for helping, totally forgot about c++ style boolean usage.

# Answer
> 2 votes
## Haskell, 38 * 0.8 = 30.4

```
product$zipWith(\p e->(p*p^e-1)/(p-1))

```

Usage:

```
product$zipWith(\p e->(p*p^e-1)/(p-1)) [2,3,5] [4,1,1]
744.0

```

The anonymous function takes `(p,e)` to the divisor-sum for `p^e` via geometric series sum. Zipping together the two lists with this as the joining and taking the product gives the result.

I wasn't able to find anything shorter that the arithmetic expression

```
(p*p^e-1)/(p-1)
sum$map(p^)[0..e]

```

Maybe there's a way to get rid of the `(\p e->_)`.

Infix function definition gives the same length (38):

```
p%e=(p*p^e-1)/(p-1)
product$zipWith(%)

```

# Answer
> 2 votes
## Matlab, 53

```
function t=f(x,y)
s=1:prod(x.^y);t=s*~mod(s(end),s)';

```

Example:

```
>> f([2 3 5], [4 1 1])
ans =
   744

```

# Answer
> 1 votes
# Python 2,156

```
from itertools import*
from operator import*
i=input()
print sum(reduce(mul,[a**b for a,b in zip(i[0],p)])for p in product(*map(range,[x+1 for x in i[1]])))

```

# Input

```
[[2,3,5],[4,1,1]]

```

# Output

```
744

```

# Explanation

This program receive list of 2 lists: factors and exponents.

```
i=input() # Receive list of 2 lists: i[0] for factors i[1] for exponents

```

Then its create list of all possible combinations of the exponent list.

```
[x+1 for x in i[1]] # [4,1,1]->[5,2,2] (to include last element)
map(range,[x+1 for x in i[1]]) # [[0, 1, 2, 3, 4], [0, 1], [0, 1]]
product(*map(range,[x+1 for x in i[1]])) # [(0, 0, 0), (0, 0, 1), ..., (4, 1, 1)]

```

and zip it with the factors:

```
zip(i[0],p) for p in product(*map(range,[x+1 for x in i[1]])) # [[(2, 0), (3, 0), (5, 0)], ..., [(2, 4), (3, 1), (5, 1)]]

```

Calculate the factors to the power of exponents:

```
 [a**b for a,b in zip(i[0],p)]for p in product(*map(range,[x+1 for x in i[1]])) # [[1, 1, 1], ..., [16, 3, 5]]

```

and multiply each list (this gives us all the divisors):

```
reduce(mul,[a**b for a,b in zip(i[0],p)])for p in product(*map(range,[x+1 for x in i[1]])) # [1, 5, 3, 15, ..., 240]

```

Finally, sum all the lists and print:

```
print sum(reduce(mul,[a**b for a,b in zip(i[0],p)])for p in product(*map(range,[x+1 for x in i[1]]))) # 744

```

# Answer
> 1 votes
# Python 3, 134 120 117

Input: two comma-separated arrays separated by comma.

Example:

```
(2,3,7,11),(4,2,3,2)
21439600

```

```
from functools import*
a=eval(input())
print(reduce(int.__mul__,(sum(x**j for j in range(y+1))for x,y in zip(*a)),1))

```

With NumPy can be reduced to 100 bytes:

```
import numpy
a=eval(input())
print(numpy.product([sum(x**j for j in range(y+1))for x,y in zip(*a)]))

```

# Answer
> 1 votes
# Jelly

~~This answer is non-competing, since the challenge predates the creation of Jelly.~~

## 5 bytes (no bonus)

```
*PÆDS

```

Try it online!

### How it works

```
*PÆDS    Main link. Left input: p (prime factors). Right input: e (exponents).

*        Elevate the prime factors to the corresponding exponents.
 P       Take the product of all powers.
  ÆD     Find all divisors of the product.
    S    Compute the sum of the divisors.

```

## 7 bytes (5.6 bytes after bonus)

```
*‘}’:’{P

```

### How it works

```
×*’:’{P  Main link. Left input: p (prime factors). Right input: e (exponents).

 *       Elevate the prime factors to the corresponding exponents.
         This yields p ** e.
×        Multiply the prime factors with the corresponding powers.
         This yields p ** (e + 1).
  ’      Decrement the resulting products.
         This yields p ** (e + 1) - 1.
    ’{   Decrement the prime factors.
         This yields p - 1.
   :     Divide the left result by the right one.
         This yields (p ** (e + 1) - 1) / (p - 1).
      P  Take the product of all quotients.

```

Try it online!

# Answer
> 1 votes
# APL, 12 bytes * 0.8 = 9.6

```
×/1++/¨⎕*⍳¨⎕

```

This reads two lists from the keyboard, exponents first, i.e.:

```
      ×/1++/¨⎕*⍳¨⎕
⎕:
      4 1 1
⎕:
      2 3 5
744

```

Explanation:

* : read a list from the keyboard (the exponents)
* `⍳¨`: for each number in the list, generate a list `[1..n]`.
* `⎕*`: read another list from the keyboard (the primes), and raise each prime to each of the exponents in the corresponding lists
* `+/¨`: sum each list
* `1+`: add one to each result, to compensate for the missing `x^0` in each of the lists
* `×/`: take the product of the results

# Answer
> 1 votes
# Racket (Scheme), 65 * 0.8 = 52 bytes

Same arithmetic as everyone else

```
(λ(x y)(foldl(λ(m n o)(*(/(-(expt m(+ n 1))1)(- m 1))o))1 x y))

```

Explanation:

```
(λ (x y)    ;defines anonymous function with two inputs
    (foldl    ;recursively applies the following function to all elements of the lists given to an argument given (foldl function argument lists lists lists...)
        (λ (m n o) (* (/ (- (expt m (+ n 1)) 1) (- m 1)) o))    ;an anonymous function representing the same arithmetic used in the CJam answer, then multiplying it with our incrementor
        1 x y))    ;the incrementor argument is 1, and the input lists are the ones provided into the original function

```

# Answer
> 1 votes
# Jelly, 4 bytes

```
*PÆs

```

Try it online!

## How it works

```
*PÆs - Main link. Takes bases B on the left and exponents E on the right
*    - Raise each base to each exponent
 P   - Take the product
  Æs - Take the divisor sum

```

# Answer
> 0 votes
# Python 2, 80 Bytes * 0.8 = 64

This assumes the input comes in one after another. Follows the same formula as outlined in Sp3000's CJam answer.

```
print(reduce(float.__mul__,[~-(x**-~y)/~-x for x,y in zip(input(),input())],1))

```

If this isn't allowed, then I'll use this as a solution, which gets a score of 84 bytes * 0.8 = 67.2. Input should be separated by a comma, i.e. `[2,3,5],[4,1,1]`.

```
k=input()
print(reduce(float.__mul__,[~-(x**-~y)/~-x for x,y in zip(k[0],k[1])],1))

```

---

Psst. Hey! This is a possible solution in Symbolic, something I'm working on: `Ƥ(П([~-(x**-~y)/~-xϝx,yϊʐ(Ί,Ί)],1))`

# Answer
> 0 votes
# Perl 5, 96 bytes

Obviously this is nonwinning, but I decided to write it for fun.

It's a subroutine:

```
{($b,$e)=@_;$s=1;map$s*=$b->[$_]**$e->[$_],0..@$b-1;$_=1x$s;for$j(1..$s){$i+=$j*/^(.{$j})*$/}$i}

```

See it in action thus:

```
perl -e'print sub{...}->([2,3,5],[4,1,1])'

```

How it works:

* `($b,$e)=@_` reads the input arrayrefs `$b` (bases) and `$e` (exponents).
* `$s=1` initializes the product.
* `map$s*=$b->[$_]**$e->[$_],0..@$b-1` multiplies `$s` by successive base-exponent powers. Now `$s` is the composite number.
* `$_=1x$s` sets `$_` equal to a string of ones, `$s` long. `$i` is initialized at 0.
* `for$j(1..$s){$i+=$j*/^(.{$j})*$/}` tries, for every number `$j` between 1 and `$s`, to break `$_` up as `$j` characters repeated any number of times. If it can, then `$j` divides `$s`, and `/^(.{$j})*$/` is 1 (otherwise it's 0), and `$i` is augmented by `$j`. Thus, we add to `$i` the number of partitions in a equal-sized partition of `$_`. As Omar E. Pol points out, `$i` is the number we're seeking.
* `$i` at the end returns `$i`.

# Answer
> 0 votes
# Mathematica, 40 bytes

```
Total[Outer@@{*}~Join~(#^0~Range~#2),3]&

```

Without using any of the inbuilts that deal with divisors, to differentiate from the other mathematica solution in the thread.

Input is (using example) `[{2, 3, 5}, {4, 1, 1}]`

# Answer
> 0 votes
# J, 14 bytes * 0.8 = 11.2

```
[:*/(^>:)%&<:[

```

## Usage

```
   f =: [:*/(^>:)%&<:[
   2 3 5 f 4 1 1
744

```

---
Tags: code-golf, math, primes
---


title: Finding duplicate balls in a basket?

text:
# Question
Title: Finding duplicate balls in a basket?
A basket is full with \\$n\\$ colored balls. For each color except one, there are at least 2 balls with that color. Find the color which only has one ball. in \\$O(n)\\$ space complexity.

What if each ball is repeated exactly twice?

You can consider the input to be an array or a list or any container of colors as strings with a maximum length of 100

This is so the shortest code in bytes wins.

# Answer
> 10 votes
# Python - 17 chars

Solely as an expression:

```
min(B,key=B.count)

```

Full, standalone program with input and output, **34 chars**:

```
B=input()
print min(B,key=B.count)

```

edit: What gnibbler said.

# Answer
> 6 votes
# K, 17 15

```
&1=#:'=" "\:0:0

```

Takes input from stdin as a space separated list

```
k)&1=#:'=" "\:0:0
red red green blue blue
"green"

```

# Answer
> 5 votes
## J, 31 24 20 characters

```
{.(~./:#/.~);:1!:1[1

```

A lot prettier than the previous attempt. Takes input from keyboard.

Makes an assumption that wasn't necessary in the previous version - that there is exactly one colour with one ball. If there are 2 colours with one ball you'll get the first that appears in the list, if there are no colours with only one ball you'll get the colour with the least balls.

Example:

```
   {.(~./:#/.~);:1!:1[1
green green red blue blue
┌───┐
│red│
└───┘

```

# Answer
> 3 votes
# SQL - 44

### Find Unique Color

```
SELECT C FROM B GROUP BY C HAVING COUNT(C)=1

```

### Find Duplicate Colors

```
SELECT C FROM B GROUP BY C HAVING COUNT(C)>1

```

# Answer
> 2 votes
### Python 2.7, 44 chars

Using the same sort of format as Keith Randall's answer of a function that takes an array and returns the element/colour that only occurs once.

```
R=lambda B:[a for a in B if B.count(a)<2][0]

```

Alternatively, if I need to read in colours from the command line and output the colour that is unique (which takes 60 chars):

```
B=raw_input().split();print[a for a in B if B.count(a)<2][0]

```

# Answer
> 2 votes
# Clojure - 44

```
#(some(fn[[c n]](if(= n 1)c))(frequencies%))

```

That's a lambda function. Example:

```
(#(some(fn[[c n]](if(= n 1)c))(frequencies%))
  [:red :red :red :blue :green :blue :yellow :yellow])
=> :green

```

# Answer
> 1 votes
# GolfScript, 23

After a tremendous amount of help from w0lf, here's the source code.

```
' '/:x.&{x{1$=},,1=\;},

```

**DEMO**

---

## 28 characters with the error checking

`?` is displayed if there is not one unique color. For the sake of keeping the number of characters down to a minimum, the question mark was used (this of course can be changed to something more meaningful).
```
' '/:x.&{x{1$=},,1=\;},'?'or

```

**DEMO**

---

### Commentary

```
' '/:x        # split up each element and assign it to 'x'
.&            # copy the last element in the stack and do a "setwise and"
{x            # start filtration process and invoke 'x'
{1$=}         # checks for an equality comparison
,,            # find the count of each unique character
1=            # compare value to '1'
\;            # leave only value that has count of '1' on the stack
},            # close filtration process and print element on stack
'?'or         # OPTIONAL: is printed if no element with a count of '1' is found

```

# Answer
> 1 votes
# Mathematica 23

`n` contains the list.

```
Cases[Tally@n,{x_,1}:>x]

```

# Answer
> 1 votes
# 05AB1E, 2 bytes

```
.m

```

Try it online!

.m is a builtin function which return the least frequent element in a list.

If you are not allowed to use a builtin to solve the challenge, then it's ~~4~~ 2 bytes:

-2 thanks to @caird coinheringaahing

```
ʒ¢

```

Try it online!

# Answer
> 0 votes
## Python 2.7, 67 chars

```
from collections import*
R=lambda B:Counter(B).most_common()[-1][0]

```

# Answer
> 0 votes
# R - 18 chars

```
which(table(x)==1)

```

# Answer
> 0 votes
## APL (14)

```
B/⍨1=+/B∘.≡B←⎕

```

Takes input from the keyboard in the form of an APL list, so you need to put quotes around the colors `'like' 'this'`. (Or use numbers.)

```
      B/⍨1=+/B∘.≡B←⎕
⎕:
      'green' 'green' 'red' 'blue' 'blue'
 red

```

As a function (that takes a list, also 14 characters):

```
{⍵/⍨1=+/⍵∘.≡⍵}

```

# Answer
> 0 votes
## Groovy - 22 chars

```
it.min{a->it.count(a)}

```

Attribution and test case:

```
lone={it.min{a->it.count(a)}}

l = ['red','green', 'red', 'blue', 'green']

assert lone(l) == 'blue'
assert lone(l) != 'red'

```

---
Tags: code-golf, array, restricted-memory
---


title: Love Tester Code Golf

text:
# Question
Title: Love Tester Code Golf
Create program that counts the total number of letters common to two names, and finds the product of their lengths, to function as a "love tester."

Conditions: you may not get a 1:1 answer (being 3 out of 3, etc.) output.

## Input

Two names from STDIN or closest alternative.

## Output

Compute `x` as the total number of letters in common between the two names, ignoring case. Compute `y` as the product of the lengths of the names. Then the output, to STDOUT or closest alternative, is

```
Name1 and Name2 have x out of y chances of love.

```

## Examples

Input:

```
Wesley
Polly

```

Output:

```
Wesley and Polly have 2 out of 30 chances of love.

```

Wesley and Polly have 2 letters in common, `y` and `l`, and the product of their lengths is 6 * 5 = 30.

Input:

```
Bill
Jill

```

Output:

```
Bill and Jill have 3 out of 16 chances of love.

```

## Bonuses

* Subtract 30 bytes for using simplified fractions, i.e. `x out of y` is in fully reduced form.

## Scoring

This is answers will be scored in bytes with fewer bytes being better.

# Answer
> 3 votes
# Pyth, 40 bytes

```
jd[z"and"Jw"have"/K-lzl.-rz0rJ0i=J*lzlJK"out of"/JiJK"chances of love.

```

The code is **70 bytes** long and qualifies for the **-30 bytes** bonus.

Try it online.

```
  [                        Begin an array and fill it with the following:
   z                         The first line of input.
   "and"                     That string.
   Jw                        The second line of input, saved in J.
   "have"                    That string.
           rz0rJ0              Convert both lines to lowercase.
         .-                    Remove the characters form the second string
                               from the first, counting multiplicities.
        l                      Get the length.
     -lz                       Subtract it from the length of the first line.
    K                          Save in K.
                  =J*lzlJ      Save the lines' lengths' product in J.
                 i       K     Compute the GCD of J and K.
   /                         The quotient of K and the GCD.
   "out of"                  That string.
   /JiJK                     The quotient of J and the GCD of J and K.
   "chances of love.         That string.
jd                         Join the elements, separated by spaces.

```

# Answer
> 3 votes
# CJam, 55 bytes

```
ll]_~@_{'~,\elfe=}/.e<:+\:,:*]_2>~{_@\%}h;f/"and
have
out of
chances of love."N/.{}S*

```

The code is **85 bytes** long and qualifies for the **-30 bytes** bonus.

Try it online in the CJam interpreter.

### How it works

```
ll]      e# Read two lines and wrap them in an array.
_~       e# Copy the array and dump the lines on the stack.
@_       e# Rotate the array on top and push a copy.
{        e# For each line of the copy.
  '~,    e#   Push the array of all ASCII charcters up to '}'.
  \el    e#   Convert the line to lowercase.
  fe=    e#   Count the occurrences of each character in the line.
}/       e#
.e<      e# Vectorized minimum of the occurrences.
:+       e# Add to find the number of shared charaters.
\:,      e# Compute the length of each line.
:*       e# Push the product.
]_       e# Wrap the stack in an array and push a copy.
2>~      e# Discard the lines of the copy and dump the calculated integers.
{_@\%h}; e# Compute their GCD, using the Euclidean algorithm.
f/       e# Divide each element of the array by the GCD.
         e# This also splits the names, which won't affect printing.

"and
have
out of
chances of love."

N/       e# Split the above string at linefeeds.
.{}      e# Vectorized no-op. Interleaves the arrays.
S*       e# Join the results elements, separated by spaces.

```

# Answer
> 3 votes
# Dyalog APL, ~~94~~ 91-30= 61 bytes

Usually APL golfing results in code that is more compact – but not more complex – than normal, but in this case I save chars in ugly ways:

```
{1↓(∊' ',¨⍵,⍪'and' 'have'),' love.',⍨∊((⊢÷∨/)(≢⊃∩/32|⎕ucs¨⍵),×/≢¨⍵),⍪'out of' 'chances of'}

```

`,⍪'out of' 'chances of'` create a 2×2 table of numbers (left) and texts (right)
`×/≢¨⍵` product of lengths
`32|⎕UCS¨⍵` harmonize upper- and lowercase UCS values
`≢⊃∩/` tally the intersection of the two sets
`⊢÷∨/` divide the tally and the product with their GCD
`,' love.',⍨∊` make it into a simple list and append *love.*
`⍵,⍪'and' 'have'` create a 2×2 table of names (left) and texts (right)
`∊' ',¨` prepend a space to each table cell and then make into simple list
`1↓` drop the initial superfluous space

Thanks to ngn for -3 bytes.

# Answer
> 2 votes
# Javascript ES6, 123 bytes

```
(a,b)=>a+` and ${b} have ${[...a].map(x=>eval(`/${x}/i.test(b)&&c++`),c=0),c} out of ${a.length*b.length} chances of love.`

```

So much for "love"... I could really do with less bytes.

Run the code snippet in Firefox.

```
x=(a,b)=>a+` and ${b} have ${[...a].map(x=>eval(`/${x}/i.test(b)&&c++`),c=0),c} out of ${a.length*b.length} chances of love.`
```

```
<input id="a" value="Bill"><input id="b" value="Jill"><button onclick="o.innerHTML=x(a.value,b.value)">Calculate!</button>
<div id="o"></div>
```

# Answer
> 2 votes
# Julia, 129 bytes

The code is 159 bytes but it qualifies for the -30 bonus.

```
A,B=map(chomp,readlines())
a,b=map(lowercase,[A,B])
L=length
r=Rational(L(a∩b),L(a)L(b))
print("$A and $B have $(r.num) out of $(r.den) chances of love.")

```

This could probably be made shorter by *not* going for the bonus, but I wanted to show off Julia's rational number type. :)

Ungolfed:

```
# Read two names from STDIN on separate lines
A, B = map(chomp, readlines())

# Construct their lowercase equivalents
a, b = map(lowercase, [A, B])

# Construct a rational number where the numerator is the
# length of the intersection of a and b and the denominator
# is the product of the lengths
r = Rational(length(a ∩ b), length(a) * length(b))

# Tell us about the love
print("$A and $B have $(r.num) out of $(r.den) chances of love.")

```

The `Rational()` function constructs an object of type `Rational` which has fields `num` and `den`, corresponding to the numerator and denominator respectively. The benefit of using this type here is that Julia does the reduction for us; we don't have to worry about reducing the fraction ourselves.

# Answer
> 2 votes
# Stax, 42 - 30 = 12 bytes

```
±à>mª≈◄ΣÇyⁿ`à>²CΔ7ù«▀╦X╠;7╣ⁿ¡♣ë╩■B§F»é▲Y∩«

```

Run and debug it

Fractions are great to have.

# Answer
> 1 votes
# Dyalog APL, 84-30= 54 bytes

`∊' and ' ' have' 'out of' 'chances of love.',¨⍨⊢,{+/⌊⌿+⌿↑1↑¨⍨-32|⍉⎕ucs↑⍵}(,÷∨)(×/≢¨)`

This is a train, inspired by Adám's answer.

`×/≢¨` product of the lengths

`{+/⌊⌿+⌿↑1↑¨⍨-32|⍉⎕ucs↑⍵}` chances of love

`(,÷v)` the concatenation divided by the GCD; between the above two expressions, this reduces the fraction

`⊢,` prepend the names

`,¨⍨` shuffles the strings on the left with the values on the right

flatten

---

"Chances of love" computation in detail: `{+/⌊⌿+⌿↑1↑¨⍨-32|⍉⎕ucs↑⍵}
 ↑⍵ arrange the names in a 2×N matrix, pad with spaces
 ⎕ucs take ascii codes
 ⍉ transpose the matrix as N×2
 32| modulo 32 to case-fold
 1↑¨⍨- for each X create a vector 0 0...0 1 of length X
 ↑ arrange into a 3d array, pad with 0s
 +⌿ 1st axis sum, obtain freqs per letter and per name
 ⌊⌿ 1st axis min, obt. nr of common occurrences per letter
 +/ sum`

test, test2

# Answer
> 1 votes
# 05AB1E, 44-30 = 14 bytes

```
ÃÙgD¹g²g*DŠ¿U)X/`s¹²“ÿ€ƒ ÿ€¡ ÿ€Ä€‚ ÿÒï€‚„Î.“

```

Try it online!

# Answer
> 0 votes
# Python 2.7, 161 bytes

```
import string;r=raw_input;a,b=r(),r();print'%s and %s have %i out of %i chances of love'%(a,b,sum(map(lambda c:c in a and c in b,string.letters)),len(a)*len(b))

```

Test it here : http://ideone.com/jeoVgV

And here is a version that simplifies the fraction :

```
import string,fractions;r=raw_input;a,b=r(),r();F=fractions.Fraction(sum(map(lambda c:c in a and c in b,string.letters)),len(a)*len(b))
print'%s and %s have %i out of %i chances of love'%(a,b,F.numerator,F.denominator)

```

Unfortunately this one's score is 219-30=189...

# Answer
> 0 votes
# Java 8, 192 bytes

```
BiFunction y=(a,b)->a+" and "+b+" have "+(""+a).chars().filter(c->(""+b).toUpperCase().indexOf(c>'Z'?c-32:c)>=0).count()+" out of "+(""+a).length()*(""+b).length()+" chances of love.";

```

Ex:

```
System.out.println(y.apply("Bill","Jill"));
System.out.println(y.apply("Wesley","Polly"));

```

# Answer
> 0 votes
# Ruby, 153 bytes

Longer than I expected. I don't know if the 30 bytes bonus applies for this.

```
d=[];2.times{d<<gets.chop<<$_.downcase.chars<<$_.length-1};$><<"#{d[0]} and #{d[3]} have #{d[2]-(d[1]-d[4]).length} out of #{d[2]*d[5]} chances of love."

```

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


title: De-Parenthesizing a String

text:
# Question
Title: De-Parenthesizing a String
Given a properly-parenthesized string as input, output a list of all nonempty substrings within matching parentheses (or outside of all parentheses), with nested parentheses removed. Each substring should be the sequence of characters in exactly the same matching parentheses. Substrings should be listed in order of depth, and substrings of the same depth should be listed in the order they occur in the string. Assume the input is always correctly parenthesized.

You may assume that the input contains only lower-case ASCII letters and parentheses.

Your answer should be a function that, when given a string, returns a list of strings.

## **Examples:**

```
                   'a(b)c(d)e' -> ['ace', 'b', 'd']
                   'a(b(c)d)e' -> ['ae', 'bd', 'c']
                  'a((((b))))' -> ['a', 'b']
                        'a()b' -> ['ab']
                            '' -> []
                           'a' -> ['a']
          '(((a(b)c(d)e)f)g)h' -> ['h', 'g', 'f', 'ace', 'b', 'd']
'ab(c(((d)ef()g)h()(i)j)kl)()' -> ['ab', 'ckl', 'hj', 'efg', 'i', 'd']

```

Fewest bytes wins.

# Answer
> 11 votes
# JavaScript ES6, 91 ~~93 104 133 148~~

**Edit2** 2 bytes saved thx user81655

**Edit** Using more strings and less arrays

Test running the snippet below in an EcmaScript 6 compliant browser

```
f=s=>[...s].map(c=>l+=c<')'||-(o[l]=(o[l]||'')+c,c<'a'),o=[],l=0)&&(o+'').match(/\w+/g)||[]

// Less golfed

u=s=>{
  o=[]; l=0;
  [...s].map(c=>{
    if (c>'(') // letters or close bracket
      o[l]=(o[l]||'')+c, // add letter or close bracket to current level string
      l-=c<'a' // if close bracket, decrement level
    else
      ++l // open bracket, increment level
  })
  o = o+'' // collapse array to comma separated string
  return o.match(/\w+/g)||[] // fetch non empty strings into an array
}

// TEST
console.log=x=>O.innerHTML+=x+'\n'

;[ 'a(b)c(d)e'                    // ['ace', 'b', 'd']
 , 'a(b(c)d)e'                    // ['ae', 'bd', 'c']
 , 'a((((b))))'                   // ['a', 'b']
 , 'a()b'                         // ['ab']
 , ''                             // []
 , 'a'                            // ['a']
 , '(((a(b)c(d)e)f)g)h'           // ['h', 'g', 'f', 'ace', 'b', 'd']
 , 'ab(c(((d)ef()g)h()(i)j)kl)()' // ['ab', 'ckl', 'hj', 'efg', 'i', 'd']
].forEach(t=>console.log(t +" -> " + f(t)))
```

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

# Answer
> 8 votes
# Julia, ~~117~~ ~~86~~ 83 bytes

```
v->(while v!=(v=replace(v,r"(\(((?>\w|(?1))*)\))(.*)",s"\g<3> \g<2>"))end;split(v))

```

It's a regex solution.

Ungolfed:

```
function f(v)
  w=""
  while v!=w
    w=v
    v=replace(v,r"(\(((?>\w|(?1))*)\))(.*)",s"\g<3> \g<2>"))
  end
  split(v)
end

```

`r"(\(((?>\w|(?1))*)\))(.*)"` is a recursive (`(?1)` recurses group 1) regex that will match the first outermost balanced parentheses (that don't contain unbalanced/reversed parentheses), with the second group containing everything inside the parentheses (not including the parentheses themselves) and the third group containing everything after the parentheses (until the end of the string).

`replace(v,r"...",s"\g<3> \g<2>")` will then move the second group to the end of the string (after a space, to act as a delimiter), with the relevant parentheses removed. By iterating until v==w, it is ensured that the replace is repeated until there are no parentheses left. Because matches are moved to the end, and then the next match goes for the first parenthesis, the result will be the string broken down in order of depth.

Then `split` returns all of the non-whitespace components of the string in the form of an array of strings (that have no whitespace).

Note that `w=""` is used in the ungolfed code to make sure that the while loop runs at least once (except if the input string is empty, of course), and is not needed in the golfed form.

Thanks to Martin Büttner for assistance with saving 3 bytes.

# Answer
> 6 votes
# Python, 147 bytes

```
def f(s):
 d=0;r=[['']for c in s]
 for c in s:
  if c=='(':d+=1;r[d]+=['']
  elif c==')':d-=1
  else:r[d][-1]+=c
 return[i for i in sum(r,[])if i]

```

Unit tests:

```
assert f('a(b)c(d)e') == ['ace', 'b', 'd']
assert f('a(b(c)d)e') == ['ae', 'bd', 'c']
assert f('a((((b))))') == ['a', 'b']
assert f('a()b') == ['ab']
assert f('') == []
assert f('a') == ['a']
assert f('(((a(b)c(d)e)f)g)h') == ['h', 'g', 'f', 'ace', 'b', 'd']
assert f('ab(c(((d)ef()g)h()(i)j)kl)()') == ['ab', 'ckl', 'hj', 'efg', 'i', 'd']

```

I like this puzzle; it's very cute!

# Answer
> 5 votes
# Pyth, 32 bytes

```
fTscR)uX0.<GJ-FqLH`()@[Hdk)Jzmkz

```

Test suite

Loosely based off of @Quuxplusone's approach. Builds up space separated lists of the characters at each depth, then splits them and filters out the empty groups. The working list is rotated to keep the current depth's list in front at all times.

# Answer
> 4 votes
## Retina, ~~44~~ 41 bytes

```
+`\(((\w|(\()|(?<-3>.))*).(.*)
$4 $1
S_`

```

Run with the `-s` flag. Notice the space at the end of the last line.

I came up with this solution independently of Glen O but it turns out to be identical. The idea is to match the first pair of parentheses, remove it, and insert its contents at the end of the output (repeatedly). Due to .NET's lack of recursion in regex, I had to use balancing groups which is four bytes longer.

If you don't understand the first regex, let me refer you to my SO answer about balancing groups. Since the input is guaranteed to be correctly parentheses, we can save two bytes by matching `)` with `.` instead of `\)`. Then we simply match the rest of the string with `(.*)`. `$4 $1` first writes back said rest of the string (omitting both the parentheses and their content), and then the content of the parentheses after a space. The `+`` tells Retina to repeat this step until the string stops changing (which only happens once all parentheses have been removed).

Empty parentheses will result in two consecutive spaces, so finally we split the entire string on spaces (`S`` activates split mode and the regex is a single space). The `_` option tells Retina to omit empty parts of the split, so we don't include the empty results in the output.

# Answer
> 3 votes
## Common Lisp, 160

```
(lambda(x)(labels((g(l)(cons(#1=format()"~(~{~A~}~)"(#2=remove-if'listp l))(mapcan #'g(#2#'atom l)))))(remove""(g(read-from-string(#1#()"(~A)"x))):test'equal))))

```

This could be four bytes less if the case conversion wasn't necessary. The idea is to add left and right parenthesis to each side of the input string, treat it as a list, write the top level elements of the list to a string, and then process the sublists the same way.

# Answer
> 2 votes
## Haskell, ~~114~~ ~~112~~ 111 bytes

```
')'%(h:i:t)=("":i):t++[h]
'('%l=last l:init l
c%((h:i):t)=((c:h):i):t
g x=[a|a<-id=<<foldr(%)(x>>[[""]])x,a>""]

```

Usage example: `g "ab(c(((d)ef()g)h()(i)j)kl)()"` -\> `["ab","ckl","hj","efg","i","d"]`.

I'm going backward through the input string. The intermediate data structure is a list of list of strings. The outer list is per level and the inner list is per group within a level, e.g. `[["ab"],["ckl"],["hj"],["efg","i"],["d"]]` (note: the real list has a lot of empty strings in-between). It all starts with a number of empty strings equal to the length of the input - more than enough, but empty lists are filtered out anyway. The outer lists either rotates on `(`/`)` or adds the character to the front element. `)` also starts a new group.

Edit: @Zgarb has found a byte to save.

# Answer
> 2 votes
# Sed, 90 bytes

```
:
s/^(\w*)\((.*)\n?(.*)/\1\n\3_\2/M
s/(\n\w*_)(\w*)\)(.*)/\3\1\2/M
t
s/[_\n]+/,/g
s/,$//

```

Uses extended regexes (`-r` flag), accounted for by +1 byte. Also, this uses a GNU Extension (the `M` flag on the `s` command).

**Sample Usage:**

```
$ echo 'ab(c(((d)ef()g)h()(i)j)kl)()' | sed -r -f deparenthesize.sed
ab,ckl,hj,efg,i,d

```

**Explanation:** Since sed does not support stuff like recursive regexes, manual work is required. The expression is split up into multiple lines, each representing a level of nesting depth. The individual expressions on the same depth (and hence on the same line) are separated by an `_`. The script works through the input string one bracket at a time. The remaining input is always kept on the end of the line that corresponds to the current nesting level.

# Answer
> 1 votes
# 05AB1E, ~~23~~ ~~21~~ ~~17~~ 16 bytes

Thanks to @ovs for -2

Thanks to @ovs for additional -4

```
ΣžuSQÆ®+©}'(¡')м

```

Try it online!

The program contains empty strings in the output, which should be ignored. In case that's not allowed it's +3 for `ʒgĀ`.

# Answer
> 0 votes
# Python, 161 bytes

Here's what I came up with, a one-line functional python solution:

```
p=lambda s:filter(None,sum([''.join([s[i]for i in range(len(s))if s[:i+1].count('(')-s[:i+1].count(')')==d and s[i]!=')']).split('(')for d in range(len(s))],[]))

```

This challenge was inspired by https://github.com/samcoppini/Definition-book, which outputs a long string with word defined in parentheticals. I wanted to write code that would give me each sentence, with parenthesis removed. The functional solution is too slow to be effective on long strings, but imperative solutions (like @Quuxplusone's solution) are much faster.

# Answer
> 0 votes
# APL (Dyalog Unicode), 56 bytes

```
{a←⍬⋄(×≢¨a)/a←a,⊂'\([^()]*\)'⎕R{''⊣a,←⊂⍵.Match~'()'}⍣≡⍵}

```

Try it online!

A dfn which uses repeated regex replacement, and returns a list of strings (unordered).

---
Tags: code-golf, string, parsing, balanced-string
---


title: Taxi me some numbers

text:
# Question
Title: Taxi me some numbers
Taxicab Numbers or OEIS A011541 are the least numbers that are able to be represented as \\$n\\$ different sums of two positive cubed integers, for successive \\$n\\$.

You'll need to print out the \\$n\\$th taxicab number. This should work for any \\$n\\$ in theory.

However, as only 6 taxicab numbers have been discovered so far, there won't be an \\$n\\$ above 6. The numbers are \\$2, 1729, 87539319, 6963472309248, 48988659276962496\\$ and \\$24153319581254312065344\\$.

You're not allowed to hard code these variables, because your program must work for any arbitrary \\$n\\$ in theory.

# Answer
> 5 votes
## Haskell, 60 bytes

```
f n=[k|k<-[0..],n<=sum[1|x<-[1..k],y<-[1..x],x^3+y^3==k]]!!0

```

Pretty straightforward. Counts how many ways a number `k` can be written as a sum of two cubes. Filters for `k`'s such that this number is at least `n`, and takes the first one.

An equal-length method with `until`:

```
f n=until(\k->n<=sum[1|x<-[1..k],y<-[1..x],x^3+y^3==k])(+1)0

```

# Answer
> 13 votes
# Taxi, 4758 bytes

What better language to calculate taxicab numbers than one that simulates taxicabs?
This is a joke. There are so many better languages. What happened to the last two days of my life?

```
Go to Post Office:w 1 l 1 r 1 l.Pickup a passenger going to The Babelfishery.Go to The Babelfishery:s 1 l 1 r.Pickup a passenger going to Cyclone.Go to Cyclone:n 1 l 1 l 2 r.Pickup a passenger going to Bird's Bench.Pickup a passenger going to Cyclone.Go to Zoom Zoom:n.Go to Cyclone:w.Pickup a passenger going to Rob's Rest.Pickup a passenger going to Cyclone.Go to Bird's Bench:n 1 r 2 r 1 l.Go to Rob's Rest:n.Go to Cyclone:s 1 l 1 l 2 l.[a]Pickup a passenger going to Firemouth Grill.Pickup a passenger going to The Underground.Go to Zoom Zoom:n.Go to Firemouth Grill:w 3 l 2 l 1 r.Go to The Underground:e 1 l.Switch to plan "b" if no one is waiting.Pickup a passenger going to Cyclone.Go to Cyclone:n 3 l 2 l.Switch to plan "a".[b]Go to Firemouth Grill:s 1 r.[c]Pickup a passenger going to Cyclone.Go to Cyclone:w 1 l 1 r 2 r.Pickup a passenger going to Cyclone.Go to Zoom Zoom:n.Go to Cyclone:w.Pickup a passenger going to Multiplication Station.Pickup a passenger going to Multiplication Station.Pickup a passenger going to Multiplication Station.Go to Multiplication Station:s 1 l 2 r 4 l.Pickup a passenger going to Trunkers.Go to Trunkers:s 1 r 2 l.Go to Firemouth Grill:e 1 l 1 r.Switch to plan "e" if no one is waiting.Switch to plan "c".[e]Go to Trunkers:w 1 l 1 r.Pickup a passenger going to Cyclone.Go to Cyclone:w 2 r.Pickup a passenger going to Sunny Skies Park.Go to Sunny Skies Park:n 1 r.[f]Go to Trunkers:s 1 l.Switch to plan "g" if no one is waiting.Pickup a passenger going to Sunny Skies Park.Go to Cyclone:w 2 r.Pickup a passenger going to Cyclone.Go to Zoom Zoom:n.Go to Cyclone:w.Go to Sunny Skies Park:n 1 r.Switch to plan "f".[g]Go to Cyclone:w 2 r.Switch to plan "h" if no one is waiting.Pickup a passenger going to Firemouth Grill.Go to Zoom Zoom:n.Go to Firemouth Grill:w 3 l 2 l 1 r.Go to Trunkers:w 1 l 1 r.Switch to plan "g".[h]Go to Sunny Skies Park:n 1 r.Switch to plan "i" if no one is waiting.Pickup a passenger going to Cyclone.Go to Firemouth Grill:s 1 l 1 l 1 r.Pickup a passenger going to Addition Alley.Go to Cyclone:w 1 l 1 r 2 r.Pickup a passenger going to Addition Alley.Pickup a passenger going to Trunkers.Go to Zoom Zoom:n.Go to Trunkers:w 3 l.Go to Addition Alley:w 2 r 2 r 1 r.Pickup a passenger going to Narrow Path Park.Go to Narrow Path Park:n 1 r 1 l 1 r.Go to Cyclone:w 1 l 1 r 2 l.Switch to plan "h".[i]Go to Trunkers:s 1 l.Pickup a passenger going to Knots Landing.Go to Knots Landing:e 1 r 2 l 5 r.Go to Trunkers:w 1 l 3 r 1 l.Switch to plan "j" if no one is waiting.Go to Firemouth Grill:e 1 l 1 r.Switch to plan "e".[j]0 is waiting at Starchild Numerology.Go to Starchild Numerology:w 1 l 2 l.Pickup a passenger going to Addition Alley.[k]Go to Rob's Rest:w 1 r 2 l 1 r.Pickup a passenger going to Cyclone.Go to Cyclone:s 1 l 1 l 2 l.Pickup a passenger going to Rob's Rest.Pickup a passenger going to Equal's Corner.Go to Zoom Zoom:n.Go to Rob's Rest:w 2 l 2 r 1 r.Go to Narrow Path Park:s 1 l 1 l 1 r 1 r 2 l 5 l.Switch to plan "o" if no one is waiting.Pickup a passenger going to Equal's Corner.Go to Equal's Corner:w 1 l 1 r 2 l 1 l.Switch to plan "l" if no one is waiting.Pickup a passenger going to Knots Landing.1 is waiting at Starchild Numerology.Switch to plan "m".[l]0 is waiting at Starchild Numerology.[m]Go to Starchild Numerology:n 1 r.Pickup a passenger going to Addition Alley.Go to Addition Alley:w 1 r 3 r 1 r 1 r.Pickup a passenger going to Addition Alley.Go to Knots Landing:n 1 r 2 r 1 l.Go to Starchild Numerology:w 1 l 3 r 1 l 1 l 2 l.Switch to plan "k".[o]0 is waiting at Starchild Numerology.Go to Starchild Numerology:w 1 l 1 r 2 l 1 l 3 l.Pickup a passenger going to Equal's Corner.Go to Equal's Corner:w 1 l.Go to Addition Alley:n 4 r 1 r 1 r.Pickup a passenger going to Equal's Corner.Go to Bird's Bench:n 1 l 1 l 1 l 2 r 1 l.Pickup a passenger going to Cyclone.Go to Cyclone:n 1 r 1 l 2 l.Pickup a passenger going to Bird's Bench.Pickup a passenger going to Equal's Corner.Go to Bird's Bench:n 1 r 2 r 1 l.Go to Equal's Corner:n 1 r 1 r.Switch to plan "p" if no one is waiting.Go to Starchild Numerology:n 1 r.Go to Rob's Rest:w 1 r 2 l 1 r.Pickup a passenger going to The Babelfishery.Go to The Babelfishery:s 1 l 1 l 1 r 1 r 1 r.Pickup a passenger going to Post Office.Go to Post Office:n 1 l 1 r.Switch to plan "z".[p]1 is waiting at Starchild Numerology.Go to Starchild Numerology:n 1 r.Pickup a passenger going to Addition Alley.Go to Rob's Rest:w 1 r 2 l 1 r.Pickup a passenger going to Addition Alley.Go to Addition Alley:s 1 l 1 l 2 r 1 r 1 r.Pickup a passenger going to Cyclone.Go to Cyclone:n 1 l 1 l.Pickup a passenger going to Rob's Rest.Pickup a passenger going to Cyclone.Go to Rob's Rest:n 1 r 2 r 1 r.Go to Cyclone:s 1 l 1 l 2 l.Switch to plan "a".[z]

```

Try it online!
Try it online but with comments and line breaks!
Note: TIO can handle an input of `1` but `2` and above cause a timeout issue. I wrote a little snippet to print the value being checked every iteration and it only got up to `137` before it timed out. If someone who knows what they're doing could run it through an interpreter (the homepage links to a C++ version) to verify higher values, I'd appreciate it. It may take a very long time to run.

Ungolfed with comments:

```
[ FIND THE NTH TAXI CAB NUMBER ]
[ https://en.wikipedia.org/wiki/Taxicab_number ]
[ Inspired by https://codegolf.stackexchange.com/q/73827/38183 ]

[ A taxi cab number T(n) is the smallest number that can be made from the sum  ]
[ of two positive cubes in n different ways. For example, T(1) = 2 because     ]
[ 2 = 1^3 + 1^3. That is the only way to make 2 by summing positive cubes. No  ]
[ solution exists for 1 so 2 is T(1). T(2) = 1729 = 1^3 + 12^3 = 9^3 + 10^3.   ]
[ This program takes n as input and finds T(n). The (bad) psuedocode is:       ]
[                                                                              ]
[    S = STDIN;  // Use Bird's Bench                                           ]
[    T = STDIN;  // Use Rob's Rest. Saves bytes and T(n) > n is always true.   ]
[    while (true) {                                                            ]
[       // Fill an array (Firemouth Grill) with the numbers 1 through T        ]
[       // This will make it much easier to compute the cubes because a taxi   ]
[       // can only carry three passengers at a time.                          ]
[       for (i = T; i > 0; i--) { A.push(i) }                                  ]
[       // Fill an array (Trunkers) with the cubes of all integers 1 through T ]
[       for (i = T; i > 0; i--) { B.push(i ^ 3) }                              ]
[       // Fill an array (Sunny Skies Park) with each possible sum of cubes    ]
[       while (B(0) != null) {                                                 ]
[          // Make copies of the next value to add to each remaining value     ]
[          C.push(B(0));                                                       ]
[          while (B(0) != null) {                                              ]
[             C.push(C(0));                                                    ]
[             D.push(B(0));                                                    ]
[             B.shift();                                                       ]
[          }                                                                   ]
[          // Store each possible sum with this cube                           ]
[          while (C(0) != null) {                                              ]
[             E.push(C(0) + D(0));                                             ]
[             B.push(D(0));                                                    ]
[             C.shift;                                                         ]
[             D.shift;                                                         ]
[          }                                                                   ]
[       }                                                                      ]
[       // Check each possible sum to see if it equals T                       ]
[       N = 0;                                                                 ]
[       while (D(0) != null) {                                                 ]
[          if (D(0) = T) { N++ }                                               ]
[          D.shift();                                                          ]
[       }                                                                      ]
[       // If we found the desired number of sums, ouput and break             ]
[       // Otherwise, go to the next T and keep going                          ]
[       if (N = S) {                                                           ]
[          print(T);                                                           ]
[          break;                                                              ]
[       } else {                                                               ]
[          T++;                                                                ]
[       }                                                                      ]
[    }                                                                         ]
[                                                                              ]

[ S = STDIN;  // Use Bird's Bench                                         ]
[ T = STDIN;  // Use Rob's Rest. Saves bytes and T(n) > n is always true. ]
Go to Post Office: west 1st left 1st right 1st left.
Pickup a passenger going to The Babelfishery.
Go to The Babelfishery: south 1st left 1st right.
Pickup a passenger going to Cyclone.
Go to Cyclone: north 1st left 1st left 2nd right.
Pickup a passenger going to Bird's Bench.
Pickup a passenger going to Cyclone.
Go to Zoom Zoom: north.
Go to Cyclone: west.
Pickup a passenger going to Rob's Rest.
Pickup a passenger going to Cyclone.
Go to Bird's Bench: north 1st right 2nd right 1st left.
Go to Rob's Rest: north.

[ // Fill an array (Firemouth Grill) with the numbers 1 through T      ]
[ // This will make it much easier to compute the cubes because a taxi ]
[ //  can only carry three passengers at a time.                       ]
[ for (i = T; i > 0; i--) { A.push(i) }                                ]
Go to Cyclone: south 1st left 1st left 2nd left.
[a]
Pickup a passenger going to Firemouth Grill.
Pickup a passenger going to The Underground.
Go to Zoom Zoom: north.
Go to Firemouth Grill: west 3rd left 2nd left 1st right.
Go to The Underground: east 1st left.
Switch to plan "b" if no one is waiting.
Pickup a passenger going to Cyclone.
Go to Cyclone: north 3rd left 2nd left.
Switch to plan "a".

[b]
[ // Fill an array (Trunkers) with the cubes of all integers 1 through T ]
[ for (i = T; i > 0; i--) { B.push(i ^ 3); }                             ]
Go to Firemouth Grill: south 1st right.
[c]
Pickup a passenger going to Cyclone.
Go to Cyclone: west 1st left 1st right 2nd right.
Pickup a passenger going to Cyclone.
Go to Zoom Zoom: north.
Go to Cyclone: west.
Pickup a passenger going to Multiplication Station.
Pickup a passenger going to Multiplication Station.
Pickup a passenger going to Multiplication Station.
Go to Multiplication Station: south 1st left 2nd right 4th left.
Pickup a passenger going to Trunkers.
Go to Trunkers: south 1st right 2nd left.
Go to Firemouth Grill: east 1st left 1st right.
Switch to plan "e" if no one is waiting.
Switch to plan "c".

[e]
[ // Fill an array with each possible sum of cubes                ]
[ while (B(0) != null) {                                          ]
[ // Make copies of the next value to add to each remaining value ]
[ C.push(B(0));                                                   ]
[ while (B(0) != null) {                                          ]
[    C.push(C(0));                                                ]
[    D.push(B(0));                                                ]
[    B.shift();                                                   ]
[ }                                                               ]
[ Setup Cyclone with a copy of the first value ]
Go to Trunkers: west 1st left 1st right.
Pickup a passenger going to Cyclone.
Go to Cyclone: west 2nd right.
Pickup a passenger going to Sunny Skies Park.
Go to Sunny Skies Park: north 1st right.

[f]
[ Move any remaining values to Sunny Skies Park, duplicating Cyclone each time ]
Go to Trunkers: south 1st left.
Switch to plan "g" if no one is waiting.
Pickup a passenger going to Sunny Skies Park.
Go to Cyclone: west 2nd right.
Pickup a passenger going to Cyclone.
Go to Zoom Zoom: north.
Go to Cyclone: west.
Go to Sunny Skies Park: north 1st right.
Switch to plan "f".

[g]
[ // Store each possible sum with this cube ]
[ while (C(0) != null) {                    ]
[    E.push(C(0) + D(0));                   ]
[    B.push(D(0));                          ]
[    C.shift;                               ]
[    D.shift;                               ]
[ }                                         ]
[ Move everything at Cyclone to Firemouth Grill ]
Go to Cyclone: west 2nd right.
Switch to plan "h" if no one is waiting.
Pickup a passenger going to Firemouth Grill.
Go to Zoom Zoom: north.
Go to Firemouth Grill: west 3rd left 2nd left 1st right.
Go to Trunkers: west 1st left 1st right.
Switch to plan "g".

[h]
[ Copy Sunny Skies Park to Trunkers and add it to Firemouth Grill ]
Go to Sunny Skies Park: north 1st right.
Switch to plan "i" if no one is waiting.
Pickup a passenger going to Cyclone.
Go to Firemouth Grill: south 1st left 1st left 1st right.
Pickup a passenger going to Addition Alley.
Go to Cyclone: west 1st left 1st right 2nd right.
Pickup a passenger going to Addition Alley.
Pickup a passenger going to Trunkers.
Go to Zoom Zoom: north.
Go to Trunkers: west 3rd left.
Go to Addition Alley: west 2nd right 2nd right 1st right.
Pickup a passenger going to Narrow Path Park.
Go to Narrow Path Park: north 1st right 1st left 1st right.
Go to Cyclone: west 1st left 1st right 2nd left.
Switch to plan "h".

[i]
[ } // End of 'while (B(0) != null)' up near plan "e" ]
Go to Trunkers: south 1st left.
Pickup a passenger going to Knots Landing.
Go to Knots Landing: east 1st right 2nd left 5th right.
Go to Trunkers: west 1st left 3rd right 1st left.
Switch to plan "j" if no one is waiting.
Go to Firemouth Grill: east 1st left 1st right.
Switch to plan "e".

[j]
[ // Check each possible sum to see if it equals T ]
[ N = 0;                                           ]
[ while (D(0) != null) {                           ]
[    if (D(0) = T) { N++; }                        ]
[    D.shift();                                    ]
[ }                                                ]
[ Set N = 0 ]
0 is waiting at Starchild Numerology.
Go to Starchild Numerology: west 1st left 2nd left.
Pickup a passenger going to Addition Alley.

[k]
[ Pickup T ]
Go to Rob's Rest: west 1st right 2nd left 1st right.
Pickup a passenger going to Cyclone.
Go to Cyclone: south 1st left 1st left 2nd left.
Pickup a passenger going to Rob's Rest.
Pickup a passenger going to Equal's Corner.
Go to Zoom Zoom: north.
Go to Rob's Rest: west 2nd left 2nd right 1st right.
Go to Narrow Path Park: south 1st left 1st left 1st right 1st right 2nd left 5th left.
Switch to plan "o" if no one is waiting.

[ Check the next value against T ]
Pickup a passenger going to Equal's Corner.
Go to Equal's Corner: west 1st left 1st right 2nd left 1st left.
Switch to plan "l" if no one is waiting.

[ It's a match so N = N + 1 ]
Pickup a passenger going to Knots Landing.
1 is waiting at Starchild Numerology.
Switch to plan "m".

[l]
[ It's not a match so N = N + 0 ]
0 is waiting at Starchild Numerology.

[m]
Go to Starchild Numerology: north 1st right.
Pickup a passenger going to Addition Alley.
Go to Addition Alley: west 1st right 3rd right 1st right 1st right.
Pickup a passenger going to Addition Alley.
Go to Knots Landing: north 1st right 2nd right 1st left.
Go to Starchild Numerology: west 1st left 3rd right 1st left 1st left 2nd left.
Switch to plan "k".

[o]
[ // If we found the desired number of sums, ouput and break ]
[ // Otherwise, go to the next T and keep going              ]
[ if (N = S) {                                               ]
[    print(T);                                               ]
[    break;                                                  ]
[ } else {                                                   ]
[    T++;                                                    ]
[ }                                                          ]
[ T is still going to Equal's Corner so just get rid of it ]
0 is waiting at Starchild Numerology.
Go to Starchild Numerology: west 1st left 1st right 2nd left 1st left 3rd left.
Pickup a passenger going to Equal's Corner.
Go to Equal's Corner: west 1st left.

[ N is still going to Addition Alley so redirect it to Equal's Corner ]
Go to Addition Alley: north 4th right 1st right 1st right.
Pickup a passenger going to Equal's Corner.

[ Compare N = S ]
Go to Bird's Bench: north 1st left 1st left 1st left 2nd right 1st left.
Pickup a passenger going to Cyclone.
Go to Cyclone: north 1st right 1st left 2nd left.
Pickup a passenger going to Bird's Bench.
Pickup a passenger going to Equal's Corner.
Go to Bird's Bench: north 1st right 2nd right 1st left.
Go to Equal's Corner: north 1st right 1st right.
Switch to plan "p" if no one is waiting.

[ It's a match! The value we want is T, waiting at Rob's Rest. ]
[Go to Rob's Rest:n 3 l 1 r.]
Go to Starchild Numerology: north 1st right.
Go to Rob's Rest: west 1st right 2nd left 1st right.
Pickup a passenger going to The Babelfishery.
Go to The Babelfishery: south 1st left 1st left 1st right 1st right 1st right.
Pickup a passenger going to Post Office.
Go to Post Office: north 1st left 1st right.
Switch to plan "z".

[p]
[ It's not a match. T = T + 1 and start over. ]
1 is waiting at Starchild Numerology.
Go to Starchild Numerology: north 1st right.
Pickup a passenger going to Addition Alley.
Go to Rob's Rest: west 1st right 2nd left 1st right.
Pickup a passenger going to Addition Alley.
Go to Addition Alley: south 1st left 1st left 2nd right 1st right 1st right.
Pickup a passenger going to Cyclone.
Go to Cyclone: north 1st left 1st left.
Pickup a passenger going to Rob's Rest.
Pickup a passenger going to Cyclone.
Go to Rob's Rest: north 1st right 2nd right 1st right.
Go to Cyclone: south 1st left 1st left 2nd left.
Switch to plan "a".

[z]
[ Terminate program with 10 less bytes than going back to the Taxi Garage ]

```

# Answer
> 2 votes
# Jelly, 11 bytes

```
Œċ*3§ċ⁸=ð1#

```

Try it online!

This is *ridiculously* slow, timing out for \\$n \> 1\\$

## How it works

```
Œċ*3§ċ⁸=ð1# - Main link. Takes n on the left
        ð   - Group the previous links into a dyad f(k, n):
Œċ          -   All pairs from [1, 2, ..., k]
  *3        -   Cube each
    §       -   Sum of each
     ċ⁸     -   Count occurrences of k
       =    -   Does that equal n?
         1# - Find the first k, starting with n, which returns true under f(k, n)
              Starting with k = n is fine, as k > n for all n

```

# Answer
> 2 votes
# 05AB1E, 15 bytes

```
∞εL3mãOÙN>¢}Ik>

```

Try it online!

The program timeouts for \\$n\>1\\$ , but the algorithm works.

# Answer
> 1 votes
## ARM Thumb-2, ~~52~~ 48 bytes for theoretical algorithm, 50 bytes for overflow safe version until n == 3

This one is hilariously inefficient, and only works for n == 3 if we assume infinite integers.

Raw machine code:

```
b570 2101 0004 000a fb02 f502 4355 0013
fb03 f603 fb06 5603 428e d101 3c01 d005
3b01 d8f5 3a01 d1ef 3101 e7eb 0008 bd70

```

Assembly:

```
        .text
        .arch armv6t2
        .thumb
        .globl taxi
        .thumb_func
taxi:
        @ Nickname some registers for clarity
        n .req r0
        candidate .req r1
        i .req r2
        j .req r3
        matches_left .req r4
        i_cubed .req r5
        j_cubed_sum .req r6

        push    {r4-r6, lr}
        @ Start with a candidate of 1 (even though it's impossible)
        movs    candidate, #1
.Lcandidate_loop:
        @ reset match counter
        movs    matches_left, n
        @ start checking cubes
        @ Behold! The world's most inefficient loop!
        @ Takes 1.8 seconds for n = 2 on actual hardware. And remember, this is O(n^3). XD
        @ It also is very vulnerable to integer overflow and returns the incorrect
        @ result for n == 3. However, with sufficiently large integers, it would
        @ theoretically work fine.
        @ for (i = candidate; i != 0; --i)
        movs    i, candidate
.Li_loop:
        @ i_cubed = i * i * i
        mul     i_cubed, i, i                        @ wide insn
        muls    i_cubed, i
        @ for (j = i; --j;)
        movs    j, i
.Lj_loop:
        @ j_cubed_sum = j * j * j + i_cubed
        mul     j_cubed_sum, j, j                    @ wide insn
        mla     j_cubed_sum, j_cubed_sum, j, i_cubed @ wide insn
        @ Compare to the candidate
        cmp     j_cubed_sum, candidate
        bne     .Lno_match
.Lmatch:
        @ If it is the same, decrement matches_left
        subs    matches_left, #1
        @ Exit if we found all of the matches
        bne     .Lexit
.Lno_match:
        @ Decrement j and loop while non-zero.
        subs    j, #1
        bhi     .Lj_loop
.Lnext_i:
        @ Decrement i, and loop if it is not zero
        subs    i, #1
        bne     .Li_loop
.Lnext_candidate:
        @ Next candidate.
        adds    candidate, #1
        b       .Lcandidate_loop
.Lexit:
        movs    r0, candidate
        pop     {r4-r6, pc}

```

## Explanation

C function signature:

```
uint32_t taxi(uint32_t n);

```

Has a wonderful O(n^3) complexity combined with billions of redundant iterations thanks to it looping backwards, but it works for n == 1 and n == 2 in reasonable time on hardware. It doesn't properly calculate n == 3 because of integer overflow.

It is a very naïve triple nested loop that is **incredibly** inefficient.

Goes through every candidate, then tests every `i` for `i <= candidate`, then tests every `j` for `j <= i`, each going backwards. It calculates cubes live, and is **horrendously** redundant and inefficient....but it is small and that is what counts.

Equivalent C:

```
uint32_t taxi(uint32_t n)
{
    for (uint32_t candidate = 1; ; candidate++) {
        uint32_t matches_left = n;
        for (uint32_t i = candidate; i != 0; --i) {
            uint32_t i_cubed = i * i * i;
            for (uint32_t j = i; j != 0; --j) {
                uint32_t j_cubed_sum = j * j * j + i_cubed;
                if (j_cubed_sum == candidate) {
                    --matches_left;
                    if (matches_left == 0) {
                        return candidate;
                    }
               }
          }
    }
}

```

## Overflow-safe version

Here is a much faster one (but still slow) at 50 bytes which does not overflow before `n == 3`:

```
b570 2101 0004 2201 fb02 f502 4355 0013
fb03 f603 fb06 5603 428e d101 3c01 d006
3b01 d8f5 3201 428d d3ee 3101 e7ea 0008
bd70

```

```
        .text
        .arch armv6t2
        .thumb
        .globl taxi_safe
        .thumb_func
taxi_safe:
        @ Nickname some registers for clarity
        n .req r0
        candidate .req r1
        i .req r2
        j .req r3
        matches_left .req r4
        i_cubed .req r5
        j_cubed_sum .req r6

        push    {r4-r6, lr}
        @ Start with a candidate of 1 (even though it's impossible)
        movs    candidate, #1
.Lcandidate_loop:
        @ reset match counter
        movs    matches_left, n
        @ start checking cubes
        @ This version loops forwards from 1 and short circuits logically.
        @ It can correctly calculate n == 3.
        @ for (i = 1; i * i * i < candidate; i++) but the check is after the loop
        movs    i, #1
.Li_loop:
        @ i_cubed = i * i * i
        mul     i_cubed, i, i                        @ wide insn
        muls    i_cubed, i
        @ for (j = i; --j;)
        movs    j, i
.Lj_loop:
        @ j_cubed_sum = j * j * j + i_cubed
        mul     j_cubed_sum, j, j                    @ wide insn
        mla     j_cubed_sum, j_cubed_sum, j, i_cubed @ wide insn
        @ Compare to the candidate
        cmp     j_cubed_sum, candidate
        bne     .Lno_match
.Lmatch:
        @ If it is the same, decrement matches_left
        subs    matches_left, #1
        @ Exit if we found all of the matches
        bne     .Lexit
.Lno_match:
        @ Decrement j and loop while non-zero.
        subs    j, #1
        bhi     .Lj_loop
.Lnext_i:
        @ Increment i, and loop if i_cubed is less than candidate.
        adds    i, #1
        cmp     i_cubed, candidate
        blo     .Li_loop
.Lnext_candidate:
        @ Next candidate.
        adds    candidate, #1
        b       .Lcandidate_loop
.Lexit:
        movs    r0, candidate
        pop     {r4-r6, pc}

```

This one is significantly faster, and does not overflow before n == 3.

Instead of looping `i` backwards from `candidate`, we loop forwards from `1`, and also short circuit when `i * i * i >= candidate`, although we do run the inner loop with this condition first so it is still very redundant.

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


# Question
Title: Generate the set of prepend-append permutations in lexicographically sorted order
Define a *prepend-append sequence* of length `n` to be a permutation of the numbers `1, 2, ..., n` that can be generated by the following procedure:

* Start with the number `1`.
* For each number from `2` to `n`, place this number to the beginning or end of the sequence (either *prepend* or *append* it, hence the name of the sequence).

For example, this is a valid way to generate a prepend-append sequence of length 4:

```
1
21     [beginning]
213    [end]
2134   [end]

```

Your task is to build a program or function that will take a number `n` from `3` to `30` as input, and print or return all prepend-append sequences of length `n` in lexicographical order (if you're outputting strings and not lists, numbers above 9 will be represented as letters `a-u`, to preserve string length). For example, this is that order for `n = 4`:

```
1234  [RRR]
2134  [LRR]
3124  [RLR]
3214  [LLR]
4123  [RRL]
4213  [LRL]
4312  [RLL]
4321  [LLL]

```

In general, there are 2n-1 prepend-append permutations of length `n`.

You may not use any built-in sorting functions in your language in your code. The shortest program to do this in any language wins.

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

```
]]l~{)f+_1fm>|}/p

```

**Code expansion**:

```
]]                   "Put [[]] onto stack. What we will do with this array of array is";
                     "that in each iteration below, we will first append the next";
                     "number to all present arrays, then copy all the arrays and";
                     "move the last element to first in the copy";
  l~                 "Read input number. Lets call it N";
    {         }/     "Run this code block N times ranging from 0 to N - 1";
     )f+             "Since the number on stack starts from 0, add 1 to it and append";
                     "it to all arrays in the array of array beginning with [[]]";
        _1fm>        "Copy the array of array and move last element from all arrays";
                     "to their beginning";
             |       "Take set union of the two arrays, thus joining them and eliminating";
                     "duplicates. Since we started with and empty array and started adding";
                     "numbers from 1 instead of 2, [1] would have appeared twice if we had";
                     "simply done a concat";
                p    "Print the array of arrays";

```

**How it works**:

This is a debug version of the code:

```
]]l~ed{)edf+ed_ed1fm>ed|ed}/edp

```

Let's see how it works for input `3`:

```
[[[]] 3]                                 "]]l~"            "Empty array of array and input";
[[[]] 1]                                 "{)"              "First iteration, increment 0";
[[[1]]]                                  "{)f+"            "Append it to all sub arrays";
[[[1]] [[1]]]                            "{)f+_"           "Copy the final array of array";
[[[1]] [[1]]]                            "{)f+_1fm>"       "shift last element of each";
                                                           "sub array to the beginning";
[[[1]]]                                  "{)f+_1fm>|}"     "Take set based union";
[[[1]] 2]                                "{)"              "2nd iteration. Repeat";
[[[1 2]]]                                "{)f+"
[[[1 2]] [[1 2]]]                        "{)f+_";
[[[1 2]] [[2 1]]]                        "{)f+_1fm>";
[[[1 2] [2 1]]]                          "{)f+_1fm>|}";
[[[1 2] [2 1]] 3]                        "{)";
[[[1 2 3] [2 1 3]]]                      "{)f+"
[[[1 2 3] [2 1 3]] [[1 2 3] [2 1 3]]]    "{)f+_";
[[[1 2 3] [2 1 3]] [[3 1 2] [3 2 1]]]    "{)f+_1fm>";
[[[1 2 3] [2 1 3] [3 1 2] [3 2 1]]]      "{)f+_1fm>|}";
[[[1 2 3] [2 1 3] [3 1 2] [3 2 1]]]      "{)f+_1fm>|}/";

```

Try it online here
> 10 votes

# Answer
# Haskell, 47 bytes

```
f 1=[[1]]
f n=(\x->map(++[n])x++map(n:)x)$f$n-1

```
> 6 votes

# Answer
# Python 2, 68

```
f=lambda n:[[1]]*(n<2)or[x*b+[n]+x*-b for b in[1,-1]for x in f(n-1)]

```

Outputs a list of lists of numbers.

A recursive solution. For `n==1`, output `[[1]]`. Otherwise, add `n` to the start or end of all `(n-1)`-permutations. Prepending makes the permutation lexicographically later than appending, so the permutations remain sorted.

The "Boolean" `b` encodes whether to put `[n]` at the start or end. Actually, we move the rest of the list `x` in the expression `x*b+[n]+x*-b`. Putting `b` as `-1` or `1` lets use flip by negating, since a list multiplied by `-1` is the empty list.
> 5 votes

# Answer
# Pyth, 19

```
usCm,+dH+HdGr2hQ]]1

```

Try it online here

This is a full program that takes input from stdin.

This works in a similar way to xnor's solution, but generates the values a bit out of order, so they must be reordered. What happens at each level is that each previous list of values has the new value added to the end and to the beginning and these are each wrapped in a 2-tuple which are wrapped together in a list. For example, the first step does this:

```
[[1]]
[([1,2], [2,1])]

```

Then, this list of tuples is zipped (and then summed to remove the outermost list). In the first case this just gives the unwrapped value from above, as there is only one value in the list.

Steps showing 2-\>3:

```
([1,2], [2,1])
[([1,2,3],[3,1,2]),([2,1,3],[3,2,1])]
([1,2,3],[2,1,3],[3,1,2],[3,2,1])

```
> 4 votes

# Answer
# Mathematica, ~~57~~ ~~54~~ 49 bytes

```
f@1={{1}};f@n_:=#@n/@f[n-1]&/@Append~Join~Prepend

```

Example:

```
f[4]

```

> {{1, 2, 3, 4}, {2, 1, 3, 4}, {3, 1, 2, 4}, {3, 2, 1, 4}, {4, 1, 2, 3}, {4, 2, 1, 3}, {4, 3, 1, 2}, {4, 3, 2, 1}}
> 2 votes

# Answer
# J, 26 bytes

```
   0|:<:((,,.,~)1+#)@[&0,.@1:

   (0|:<:((,,.,~)1+#)@[&0,.@1:) 3
1 2 3
2 1 3
3 1 2
3 2 1

```

1-byte improvement thanks to FUZxxl.
> 2 votes

# Answer
# Pyth, ~~34~~ ~~33~~ ~~31~~ 29

Basically a translation of xnor's Python answer. I'm still not great with Pyth, so improvement suggestions are welcome.

Defines a function `y` to return a list of lists of integers.

```
L?]]1<b2smm++*kdb*k_dy-b1,1_1

```

**Update:** Saved 2 bytes thanks to FryAmTheEggman.

Explanation:

```
L                                  define a function y with argument b that returns
 ?*]]1<b2                          [[1]] if b < 2 else
         s                         sum(
          m                        map(lambda d:
           m                       map(lambda k:
            ++*kdb*k_d             k*d + [b] + k*-d
                      y-b1         , y(b - 1))
                          ,1_1)    , (1, -1))

```
> 1 votes

# Answer
# JavaScript (ES6) 73 ~~80~~

JavaScript implementation of @Optimizer's nice solution.

Recursive (73):

```
R=(n,i=1,r=[[1]])=>++i>n?r:r.map(e=>r.push([i,...e])+e.push(i))&&R(n,i,r)

```

Iterative (74):

```
F=n=>(i=>{for(r=[[1]];++i<=n;)r.map(e=>r.push([i,...e])+e.push(i))})(1)||r

```

**Test** In Firefox/FireBug console

```
R(4)

```

> \[\[1, 2, 3, 4\], \[2, 1, 3, 4\], \[3, 1, 2, 4\], \[3, 2, 1, 4\], \[4, 1, 2, 3\], \[4, 2, 1, 3\], \[4, 3, 1, 2\], \[4, 3, 2, 1\]\]
> 1 votes

# Answer
# Pure Bash, 103

Longer than I'd hoped:

```
a=1..1
for i in {2..9} {a..u};{
((++c<$1))||break
a={${a// /,}}
a=`eval echo $a$i $i$a`
}
echo ${a%%.*}

```
> 1 votes

# Answer
My Java solution:

```
public static void main(String[] args) {
    listPrependAppend(4);
}

private static void listPrependAppend(int n) {
    int total = (int) Math.pow(2, n - 1);
    int ps;
    boolean append;
    String sequence;
    String pattern;

    for (int num = 0; num < total; num++) {
        sequence = "";
        pattern = "";
        append = false;
        ps = num;
        for (int pos = 1; pos < n + 1; pos++) {
            sequence = append ? (pos + sequence) : (sequence + pos);
            append = (ps & 0x01) == 0x01;
            ps = ps >> 1;
            if (pos < n) {
                pattern += append ? "L" : "R";
            }
        }
        System.out.format("%s\t[%s]%n", sequence, pattern);
    }
}

```
> 0 votes

# Answer
# Jelly, 9 bytes

```
Œ!IṠIAƑƲƇ

```

Try it online!

## How it works

```
Œ!IṠIAƑƲƇ - Main link. Takes an integer n on the left
Œ!        - Permutations of [1,2,...,n]
       ƲƇ - Keep those permutations for which the following is true:
  I       -   Forward increments
   Ṡ      -   Signs
    I     -   Forward increments
     AƑ   -   All non-negative?

```

To see why this works, take four permutations for \\$n = 4\\$:

* `[2,1,3,4]` which is a prepend-append permutation
* `[3,2,1,4]` which is a prepend-append permutation
* `[3,1,4,2]` which is not
* `[1,2,4,3]` which is not

Let's work through each of the 4 commands (`I`, , `I` and ) to see the difference. Each command is applied sequentially to the result of the previous one:

| Command | `[2,1,3,4]` | `[3,2,1,4]` | `[3,1,4,2]` | `[1,2,4,3]` |
| --- | --- | --- | --- | --- |
| `I` | `[-1,2,1]` | `[-1,-1,3]` | `[-2,3,-2]` | `[1,2,-1]` |
|  | `[-1,1,1]` | `[-1,-1,1]` | `[-1,1,-1]` | `[1,1,-1]` |
| `I` | `[2,0]` | `[0,2]` | `[2,-2]` | `[0,-2]` |
|  | `1` | `1` | `0` | `0` |

It turns out that always `IṠI` yields an array consisting of `2`, `0` or `-2`, and that if a permutation does not contain `-2` after `IṠI` is applied, the permutation is a prepend-append permutation.
> 0 votes

---
Tags: code-golf, combinatorics
---


# Question
Title: Eye test - How many squares are in this picture?
## The picture:

Sick of the same old grid where the answer is simply a square pyramidal number?

Accept the challenge and write a program that given a positive integer \\$n\\$ counts how many squares are in the \\$n^{\text{th}}\\$ iteration of the Harter-Heighway dragon!

* The sequence of squares of size **1** is A003230
* Your code must count all the squares of any size (the first of size **2** show up in \\$7^{\text{th}}\\$ iteration)
* This is

Here's the beginning of the resulting sequence:

```
0, 0, 0, 1, 4, 11, 30, 78, 205, 546, 1455, 4062, 11192, 31889, 88487, 254594

```

And my un-golfed reference program in Mathematica.

# Answer
# Charcoal, 96 bytes

```
Ｆ…¹Ｘ²Ｎ«Ｆ¬⁼ＫＫ#⊞υ⟦ⅉⅈ⟧##¿＆ι⊗＆ι±ι↷↶»↷≔⁰ζＦυ«Ｊ⊟ι⊟ι≔¹ηＷ⬤ur⁼№ＫＤ⊗η✳λ#⊗η≦⊕ηＦη¿κ«↗↗≧⁺⬤dl⁼№ＫＤ⊗κ✳λ#⊗κζ»»⎚Ｉζ

```

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

```
Ｆ…¹Ｘ²Ｎ«

```

Loop over all the turns of the nᵗʰ iteration of the dragon.

```
Ｆ¬⁼ＫＫ#⊞υ⟦ⅉⅈ⟧

```

If we haven't visited this cell yet then record its position.

```
##

```

Print a segment of the dragon.

```
¿＆ι⊗＆ι±ι↷↶

```

Rotate appropriately for the next segment.

```
»↷

```

At the end of the dragon, rotate back to horizontal. (`Clear()` doesn't do this; maybe it should?)

```
≔⁰ζ

```

Start counting squares.

```
Ｆυ«Ｊ⊟ι⊟ι

```

Loop over and jump to each visited cell.

```
≔¹η

```

Start searching for squares.

```
Ｗ⬤ur⁼№ＫＤ⊗η✳λ#⊗η≦⊕η

```

While there are enough `#`s in both the upwards and rightwards directions increase the size of square being searched for.

```
Ｆη¿κ«

```

Check all sizes of squares from 1 to the largest potential size found.

```
↗↗≧⁺⬤dl⁼№ＫＤ⊗κ✳λ#⊗κζ

```

Move diagonally up and right two cells, then check downwards and leftwards for the other two sides of the square of this size and keep a running total of squares found.

```
»»⎚Ｉζ

```

Once all potential squares have been checked clear the canvas and output the final number found.
> 8 votes

# Answer
# JavaScript (ES6),  ~~272 ... 244~~  239 bytes

This is quite slow for \\$n\>6\\$ but was verified locally up to \\$n=8\\$.

```
k=>(b=[],k=1<<k,g=d=>k--?g(d+(g[b.push(n++,n++),x+=--d%2,y+=--d%2,[x-!d,y-(d>0)]]|=d&1||2,n&-n&n/2?1:3)&3):b.map(y=>b.map(x=>b.map(w=>o+=(h=d=>d--?g[[X=x-n/2+d,Y=y-n/2]]&g[[X,Y+w]]&2&&g[[X-=d,Y+=d]]&g[[X+w,Y]]&h(d):1)(++w))))|o)(n=x=y=o=0)

```

Try it online!

## Commented

### Step 1

We first build the grid.

```
k => (                             // k = input
  b = [],                          // initialize b[] to an empty array
  k = 1 << k,                      // turn k into 2 ** k
  g = d =>                         // g is a recursive function taking a direction d
    k-- ?                          //   decrement k; if it was not equal to 0:
      g(                           //     do a recursive call:
        d + (                      //       using the updated direction
          g[                       //
            b.push(n++, n++),      //       append n and n + 1 to b[]
            x += --d % 2,          //       add dx to x
            y += --d % 2,          //       add dy to y
            [x - !d, y - (d > 0)]  //       use either [x, y], [x-1, y] or [x, y-1]
          ] |=                     //       as a key to identify the cell
            d & 1                  //       that is updated with either a horizontal
            || 2,                  //       or a vertical border (using the two least
                                   //       significant bits as flags)
          n & -n & n / 2 ?         //       determine whether it's a left or right turn
            1                      //       and add either 1 or 3 to d
          :                        //
            3                      //
        ) & 3                      //       force d into [0 .. 3]
      )                            //     end of recursive call
    :                              //   else:
      ...                          //     stop the recursion and process step #2
)(n = x = y = o = 0)               // initial call to g

```

### Step 2

The array `b[]` is now filled with `[0, 1, ..., 2k-1]` and the underlying object of `g` describes the horizontal and vertical borders that are set for each cell in the grid.

```
b.map(y =>                         // for y = 0 to y = 2k-1:
  b.map(x =>                       //   for x = 0 to x = 2k-1:
    b.map(w =>                     //     for w = 0 to w = 2k-1:
      o +=                         //       update the output counter o:
        ( h = d =>                 //         h is a function taking a distance d
          d-- ?                    //           decrement d; if it was not equal to 0:
            g[[ X = x - n / 2 + d, //             test the vertical border at
                Y = y - n / 2      //             (x - n/2 + d, y - n/2)
            ]] &                   //
            g[[ X,                 //             test the vertical border at
                Y + w              //             (x - n/2 + d, y - n/2 + w)
            ]] & 2                 //
            &&                     //
            g[[ X -= d,            //             test the horizontal border at
                Y += d             //             (x - n/2, y - n/2 + d)
            ]] &                   //
            g[[ X + w,             //             test the horizontal border at
                Y                  //             (x - n/2 + w, y - n/2 + d)
            ]] &                   //
            h(d)                   //             and do a recursive call
          :                        //           else:
            1                      //             stop the recursion
        )(++w)                     //         increment w; initial call to h with d = w
    )                              //     end of map()
  )                                //   end of map()
) | o                              // end of map(); return o

```
> 5 votes

---
Tags: code-golf, math, counting, fractal
---