title: Mad Libs number sequences

text:
# Question
Title: Mad Libs number sequences
My robot for generating Mad Libs-style challenges has gone rogue! To defeat it, I need you to write code that can solve all the challenges it can crank out.

Your input is three selections for the blanks A, B, C, each from (1,2,3), specifying the sequence challenge to solve, and the number \\$n\\$ that's the input to the challenge.

**Challenges**

Given a positive integer \\$n\\$, output (A) \________

> **A:**
> (1) the \\$n\\$'th
> (2) whether \\$n\\$ is a
> (3) the smallest number above \\$n\\$ that's a

positive (B) \_______

> **B:**
> (1) Fibonacci number
> (2) triangular number
> (3) multiple of 3

whose base-10 representation (C) \_______

> **C:**
> (1) starts and ends with the same digit.
> (2) is in sorted order.
> (3) doesn't have any 1's.

**Example**

Given selections `(A, B, C) = (3, 1, 1)` and `n=13`, the challenge is "Given a positive integer \\$n\\$, output (A3) the smallest number above \\$n\\$ that's a positive (B1) Fibonacci number whose base-10 representation (C1) starts and ends with the same digit." With input `n=13`, the Fibonacci numbers bigger than \\$13\\$ start out as \\$21, 34, 55, 89, ...\\$, and the first one starting and ending with the same digit is is 55. So you should output 55.

**Details**

* You may take the fill-in-the-blank selections one-indexed (1, 2, 3) or zero-indexed (0, 1, 2).
* Note that we're restricting the sequences to positive values, so none of them contain zero. They start as
    + Fibonacci: \\$1, 1, 2, 3, ...\\$
    + Triangular: \\$1, 3, 6, 10, ...\\$
    + Multiple of 3: \\$3, 6, 9, 12, ...\\$
* For choice A1, outputting the \\$n\\$'th element, \\$n\\$ is one-indexed. So, the `n=1` Fibonacci number is 1, the `n=2` Fibonacci number is also 1, `n=3` gives 2, and so on.
* For deciding whether n is in the sequence (A2), you may use any two consistent outputs -style.
* You may assume that each sequence has an infinite number of terms meeting each condition C, and not worry about what happens with machine overflows and the like.
* For C2, digits in sorted order can have "ties", such as `377`.

**Test cases**

Here are all outputs for every combination with `n=10`, as `(A,B,C), n: result`. For these, we use one-indexed selections, and for A2 we use `1/0` for `True/False`

```
(1, 1, 1), 10: 165580141
(1, 1, 2), 10: 89
(1, 1, 3), 10: 987
(1, 2, 1), 10: 1431
(1, 2, 2), 10: 78
(1, 2, 3), 10: 276
(1, 3, 1), 10: 222
(1, 3, 2), 10: 36
(1, 3, 3), 10: 42
(2, 1, 1), 10: 0
(2, 1, 2), 10: 0
(2, 1, 3), 10: 0
(2, 2, 1), 10: 0
(2, 2, 2), 10: 0
(2, 2, 3), 10: 0
(2, 3, 1), 10: 0
(2, 3, 2), 10: 0
(2, 3, 3), 10: 0
(3, 1, 1), 10: 55
(3, 1, 2), 10: 13
(3, 1, 3), 10: 34
(3, 2, 1), 10: 55
(3, 2, 2), 10: 15
(3, 2, 3), 10: 28
(3, 3, 1), 10: 33
(3, 3, 2), 10: 12
(3, 3, 3), 10: 24

```

The first 10 outputs, `n=1` to `n=10`, for each challenge combination are:

```
(1, 1, 1): 1, 1, 2, 3, 5, 8, 55, 17711, 63245986, 165580141,
(1, 1, 2): 1, 1, 2, 3, 5, 8, 13, 34, 55, 89,
(1, 1, 3): 2, 3, 5, 8, 34, 55, 89, 233, 377, 987,
(1, 2, 1): 1, 3, 6, 55, 66, 171, 595, 666, 1081, 1431,
(1, 2, 2): 1, 3, 6, 15, 28, 36, 45, 55, 66, 78,
(1, 2, 3): 3, 6, 28, 36, 45, 55, 66, 78, 253, 276,
(1, 3, 1): 3, 6, 9, 33, 66, 99, 111, 141, 171, 222,
(1, 3, 2): 3, 6, 9, 12, 15, 18, 24, 27, 33, 36,
(1, 3, 3): 3, 6, 9, 24, 27, 30, 33, 36, 39, 42,
(2, 1, 1): 1, 1, 1, 0, 1, 0, 0, 1, 0, 0,
(2, 1, 2): 1, 1, 1, 0, 1, 0, 0, 1, 0, 0,
(2, 1, 3): 0, 1, 1, 0, 1, 0, 0, 1, 0, 0,
(2, 2, 1): 1, 0, 1, 0, 0, 1, 0, 0, 0, 0,
(2, 2, 2): 1, 0, 1, 0, 0, 1, 0, 0, 0, 0,
(2, 2, 3): 0, 0, 1, 0, 0, 1, 0, 0, 0, 0,
(2, 3, 1): 0, 0, 1, 0, 0, 1, 0, 0, 1, 0,
(2, 3, 2): 0, 0, 1, 0, 0, 1, 0, 0, 1, 0,
(2, 3, 3): 0, 0, 1, 0, 0, 1, 0, 0, 1, 0,
(3, 1, 1): 2, 3, 5, 5, 8, 8, 8, 55, 55, 55,
(3, 1, 2): 2, 3, 5, 5, 8, 8, 8, 13, 13, 13,
(3, 1, 3): 2, 3, 5, 5, 8, 8, 8, 34, 34, 34,
(3, 2, 1): 3, 3, 6, 6, 6, 55, 55, 55, 55, 55,
(3, 2, 2): 3, 3, 6, 6, 6, 15, 15, 15, 15, 15,
(3, 2, 3): 3, 3, 6, 6, 6, 28, 28, 28, 28, 28,
(3, 3, 1): 3, 3, 6, 6, 6, 9, 9, 9, 33, 33,
(3, 3, 2): 3, 3, 6, 6, 6, 9, 9, 9, 12, 12,
(3, 3, 3): 3, 3, 6, 6, 6, 9, 9, 9, 24, 24,

```

# Answer
# JavaScript (ES6),  ~~158 ... 145~~  144 bytes

Takes input as `(a,b,c,n)`, with \\$a\\$, \\$b\\$ and \\$c\\$ 0-indexed.

```
(a,b,c,n)=>(g=x=>[(d=[...x+''],i+=C=![d[0]-x%10,d+''>d.sort(),/1/.test(x)][c])>n,x>=n,x>n&C][a]?a-1?x:C&x==n:g([y,x+y,x+3][b],y+=b||x))(i=0,y=1)

```

Try it online!

### Commented

```
(a, b, c, n) => (              // given the challenge parameters ...
  g = x =>                     // g is a recursive function taking the current value x
    [                          // this is the array for A
      (                        //   a = 0:
        d = [...x + ''],       //     d[] = array of digits in x
        i += C =               //     increment i if C is true
          ![                   //     set C if the condition is false:
            d[0] - x % 10,     //       c = 0: the 1st and the last digits are not equal
            d + '' > d.sort(), //       c = 1: the digits are not in sorted order
            /1/.test(x)        //       c = 2: there's a '1' in x
          ][c]                 //     pick the relevant condition for C
      ) > n,                   //     exit if i is greater than n
      x >= n,                  //   a = 1: exit if x is greater than or equal to n
      x > n & C                //   a = 2: exit if x is greater than n and C is true
    ][a]                       // pick the relevant condition for A
    ?                          // if we're done:
      a - 1 ? x                //   if a is not equal to 1, return x
            : C & x == n       //   otherwise, test whether C is true and x is equal to n
    :                          // else:
      g(                       //   do a recursive call:
        [                      //     update x:
          y,                   //       b = 0: x = y (Fibonacci)
          x + y,               //       b = 1: x += y (triangular numbers)
          x + 3                //       b = 2: x += 3 (multiples of 3)
        ][b],                  //     pick the relevant update for B
        y += b || x            //     if b = 0, add x to y (for Fibonacci)
                               //     otherwise, add b to y (we actually just need to
                               //     add 1 for triangular numbers; for multiples of 3,
                               //     y is ignored anyway)
      )                        //   end of recursive call
)(i = 0, y = 1)                // initial call to g with x = i = 0 and y = 1

```
> 4 votes

# Answer
# Python 3, <sup>~~426~~ \\$\cdots\\$ ~~204~~</sup> 181 bytes

Saved 9 bytes thanks to RGS!!!

```
def f(a,b,c,n):
 j=i=l=x=0;y=1
 while(i<n,l<n,l<=n)[a]:
  j+=1;x,y=y,x+y;p=(x,j*-~j//2,3*j)[b];s=str(p)
  if(s[0]==s[-1],[*s]==sorted(s),not'1'in s)[c]:l=p;i+=1
 return(l,l==n)[a%2]

```

Try it online!

\\$(a,b,c)\\$ are zero-indexed and *...whether \\$n\\$ is a...* returns `True`/`False`.
> 3 votes

# Answer
# Wolfram Language (Mathematica), 245 bytes

**Input {a,b,c,n}**
True/False for A(2)

```
(d=#4;a=#;c=#3;n={#&@@(i=IntegerDigits)@#==#~Mod~10&,OrderedQ@i@#&,i@#~FreeQ~1&};{t=v=1;While[v<=d,While[!n[[c]][#@t++]];v++];#[t-1],!FreeQ[#[w=Range[3d]],d]&&n[[c]]@d,#&@@Select[Select[#@w,#>d&],n[[c]]]}[[a]]&[{Fibonacci,#(#+1)/2&,3#&}[[#2]]])&

```

Try it online!

Here are all test cases for n=1 to 10
> 2 votes

# Answer
# , 199 bytes

```
f=function(A,B,C,n){u=c(sum(1:B),1+2*(B>2))
while(sum(v<-grepl(c("^(.)(.*\\1)?$","^1*2*3*4*5*6*7*8*9*$","^[^1]*$")[C],u))<n+2)u=c(u[1]+c(u[2],sum(u^0)+1,3)[B],u)
w=u[v]
c(w[3],n%in%w,min(w[w>n]))[A]}

```

Try it online!

Conditions C1-C3 are checked via regex.

In all cases, it computes the first `n+2` terms verifying the condition; this is always enough. They are stored in reverse in `w`. Then:

* for A1, take `w[3]`
* for A2, check whether `n` appears in `w`
* for A3, take the min of the elements of `w` which are greater than `n`.

Details of the regexes:

* C1: `^(.)(.*\\1)?$`: get first digit with `^(.)`, then find either the end of the number (correspond to a 1-digit number) or any sequence followed by the same digit again
* C2: `^1*2*3*4*5*6*7*8*9*$`: any number of 1s, then any number of 2s, then... then any number of 9s
* C3: `^[^1]*$` only digits which are not 1

`w` is built as the elements of sequence `u` verifying the regex, where `u` is the Fibonacci/Triangular/multiples of 3 sequence, built iteratively by adding the appropriate increment at each step.
> 1 votes

# Answer
# Jelly, 58 bytes

```
ị"“ÆḞ“+1c2“×3”,“.ịEƊ“ṢƑ“ċ1¬$”,“ṖṪ“e@“>Ƈ”ż“¶1ÇD“Ɗ⁸+1¤#Ç”FvḢ

```

Try it online!

A dyadic link taking the choices in the order `B, C, A` as the left argument and `n` as the right argument. Builds a program from component parts and then executes it. The presence of two ones at the start of the Fibonacci sequence added an extra four characters!

## Explanation

```
ị"          | Index into the following list of strings, zipped with the first argument (so the first choice picks from the first list of strings, the second from the second and the third from the third):

```

### First set of choices

```
“ÆḞ         | - Fibonacci sequence
“+1c2       | - Triangular numbers
“×3”,       | - Multiply by 3

```

### Second set of choices

```
“.ịEƊ       | - Extract last and first terms and check if equal
“ṢƑ         | - Check whether invariant when sorted
“ċ1¬$”,     | - Count 1s and then logical not

```

### Third set of choices

```
“ṖṪ         | - Remove last then take last remaining
“e@         | - Exists (with arguments reversed)
“>Ƈ”        | - Keep those greater than

```

### Fixed bits of generated program

```
ż           | Zip with strings representing the following
“¶1ÇD       | - Newline, then 1 followed by call of previous link followed by D convert to decimal digits
“Ɗ⁸+1¤#Ç”   | - Last three as a monad called to find n+1 matching terms

```

### Code to execute the generated program

```
F           | Flatten
 v          | Call as Jelly code using n as argument
  Ḣ         | Head (needed when A is 3)

```

### Example generated code for `[1,1,1]`:

```
ÆḞ
1ÇD.ịEƊƊ⁸+1¤#ÇṖṪ

```
> 1 votes

# Answer
# Python 3, ~~182~~ 173 bytes

```
def f(a,b,c,n):
 u=i=l=0;v=b&2|1
 while(i<n,l<n,l<=n)[a]:
  u,v=v,[u+v,2*v-u+1,v+3][b];s=str(u)
  if(s[0]==s[-1],[*s]==sorted(s),not'1'in s)[c]:l=u;i+=1
 return(l,l==n)[a%2]

```

Try it online!

The skeleton was borrowed from Noodle9's Python answer, but I'm building the sequence of values in a different way.

Thanks to @xnor for saving me 9 bytes.
> 1 votes

# Answer
# Python 2, 162 bytes

Inputs A, B, C are 0-indexed.

```
a,b,c,n=input();
i=0;x=k=1
while[n,i<n,i<=n][a]|1-x:i,k=[k,k+i,i+3][b],k+(b or i);s=`i`;x=[s[0]==s[-1],sorted(s)==list(s),not'1'in s][c];n-=x>a
print[i,i==n][a%2]

```

Try it online!
> 1 votes

# Answer
# 05AB1E, ~~49~~ 44 bytes

```
∞3*∞Åf∞ηO)³èʒ1å≠y¬Å¿yD{Q)Iè}D¹²i<èë²<i.ië›Ïн

```

Input is 1-based in the order \\$n,A,B,C\\$, and for A2 it'll output \\$0\\$/\\$1\\$ for truthy/falsey respectively.

-5 bytes thanks to *@Grimmy*.

Try it online or verify all test cases.

**Explanation:**

```
∞           # Push an infinite list of positive integers: [1,2,3,...]
 3*         # Multiply each by 3
∞           # Push an infinite list of positive integers again
 Åf         # Get the (0-based) n'th Fibonacci of each
∞           # Push an infinite list of positive integers again
 η          # Get all prefixes
  O         # And sum each prefix
   )        # Wrap all infinite lists into a list
    ³è      # And index the third input (B) into it (0-based and with wraparound)
ʒ           # Filter this list by:
 1å         #  Check if the current value contains a 1
   ≠        #  And invert the boolean
 y          #  Push the current value again
  ¬         #  Push its head (without popping)
   Å¿       #  And check if the value ends with this head
 y          #  Push the current value again
  D{        #  Create a copy, and sort its digits
    Q       #  Check if both are equal
     )      #  Wrap all three checks into a list
      Iè    #  And index the next fourth input (C) into it (0-based and with wraparound)
}D          # After the filter: duplicate the resulting filtered infinite list
  ¹         # Push the first input (n)
   ²i       # If the second input (A) is exactly 1:
     <      #  Decrease `n` by 1 to make it 0-based
      è     #  And use it to index into the filtered infinite list
    ë²<i    # Else-if the second input (A) is 2:
        .i  #  Check if input `n` is in the filtered infinite list
    ë       # Else (second input (A) is 3):
     ›      #  Check for each value whether `n` is larger than it
      Ï     #  Only keep the values at the truthy indices
            #  (hence the duplicate after the filter)
       н    #  And only keep its first value
            # (after which the result is output implicitly)

```
> 1 votes

# Answer
# Bash \+ GNU utilities, 277 bytes

```
b=(d*5*d4+dvd*-r4-dvd*-* 8*1+dvd*- d3/3*-)
c=('^(.)(.*\1)?$' ^`seq -s* 9`*$ -v\ 1)
f()(egrep -q ${c[$3]}<<<$5&&dc<<<"$5 ${b[$2]}d/p"||echo 1)
case $1 in
0)for((n=1;k<$4;n++,k+=!`f $* $n`+($n$2$3<102))){ :;};$[--n];;1)n=`f $* $4`;;2)for((n=$4+1;`f $* $n`;n++)){ :;}
esac
echo $n

```

Try it online!

Input is passed in the arguments, in the order A B C n. The values A, B, and C are 0-based.

Output is on stdout. For A=1, the output is 0 for truthy and 1 for falsey.

There is lots of spurious output on stderr, which is allowed under standard golfing rules, but if you want to try it out yourself, I recommend a command like:

`madlibs 0 2 1 5 2>/dev/null`

so that your output doesn't have stderr output included in it.

---

The TIO link shows all 27 combinations of A, B, and C, and all values of n from 1 to 6. (TIO times out if I use larger values for n, but I've tested more on my own computer.)

By the way, this script requires GNU utilities. In particular, it won't work on OS X (and probably other BSD systems), because `seq` is different there.

---

Some comments on the code:

`b` is an array of three dc scripts for testing whether a number is a Fibonacci number, a triangular number, or a multiple of 3, respectively. (Each dc script outputs 0 for true and 1 for false.)

`c` is an array of three regexes which match an input which starts and ends with the same digit, or is in sorted order, or doesn't have any 1s, respectively. The regex for being in sorted order is computed using `seq`, not given explicitly, because the code is shorter that way.

`f` is a function that tests to see if input $5 satisfies the requirements with B=$2 and C=$3. It prints 0 for true, and 1 for false. (This works by calling the appropriate dc script from `b` and matching against the appropriate regex from `c`.)

The case statement computes the desired answer by calling `f` as needed to test whether the appropriate numbers have the required properties.
> 1 votes

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


title: Japanese Encoding Conversion

text:
# Question
Title: Japanese Encoding Conversion
### Background

In JIS X 0208 a 94 by 94 map (kuten (区点)) is defined to encode Chinese characters (kanji), phonetic moras (kana) and other symbols. Along with this standard there are 3 different encodings that maintain 1-1 correspondences with the map, namely JIS, Shift\_JIS and EUC. These encodings take 2 bytes for each character in the kuten map. The mappings are different that random characters may occur (mojibake) if the wrong encoding is used.

### Conversion Algorithm

In the formulae below, kuten is an ordered pair of numbers \\$(区,点)\\$ where \\$1\le 区,点\le94\\$, and \\$(a,b)\\$ is an ordered pair of bytes where \\$0\le a,b\le 255\\$. The conversions between kuten and the 3 encodings are as follows:

$$\text{JIS}: (a,b)=(32+区,32+点)$$

$$\text{Shift\_JIS}: (a,b)=\begin{cases} \left(128+\left\lceil\frac{区}{2}\right\rceil+64\left\lfloor\frac{区}{63}\right\rfloor,63+点+\left\lfloor\frac{点}{64}\right\rfloor\right)&\text{if }区\text{ is odd}\\ \left(128+\left\lceil\frac{区}{2}\right\rceil+64\left\lfloor\frac{区}{63}\right\rfloor,158+点\right)&\text{if }区\text{ is even} \end{cases}$$

$$\text{EUC}: (a,b)=(160+区,160+点)$$

### Challenge

Write a program or function that, given a byte pair, the source encoding and the destination encoding, converts the byte pair from the source encoding to the destination encoding and outputs the result. You may assume that the input byte pair represents a valid codepoint in the source encoding.

The input and output formats are flexible and are accepted if reasonable. For example, you may receive or output the byte pair as a list, as two numbers or as a number, either in decimal or hexadecimal; you may also assign a number to each of the possible encodings and use them as the input format of the encodings.

### Sample IO

The format used in the samples is `SrcCodePoint, SrcEncoding, DstEncoding -> DstCodePoint`. Decimal is used here but hexadecimal is also acceptable. The Unicode character and its assigned kuten are for explanation.

```
(227, 129), Shift_JIS, EUC -> (229, 225) (Kuten: 69-65; U+7E3A 縺)
(101, 98), JIS, Shift_JIS  -> (227, 130) (Kuten: 69-66; U+7E67 繧)
(229, 227), EUC, JIS       -> (101, 99)  (Kuten: 69-67; U+7E5D 繝)
(137, 126), Shift_JIS, JIS -> (49, 95)   (Kuten: 17-63; U+5186 円)
(177, 224), EUC, Shift_JIS -> (137, 128) (Kuten: 17-64; U+5712 園)
(49, 97), JIS, EUC         -> (177, 225) (Kuten: 17-65; U+5830 堰)

```

See here (in Japanese) for the full table.

### Winning condition

This is a code-golf challenge, so the shortest valid submission for each language wins. Standard loopholes are forbidden by default.

# Answer
# Ruby, ~~140~~ 116 bytes

Takes code point as an array, and encodings are `JIS`, `Shift_JIS`, and `EUC-JP`, respectively.

Ruby supports converting between EUC-JP and SHIFT\_JIS, so we math JIS encoding into EUC, perform the appropriate conversion, then math back the JIS encoding if that's the destination encoding.

-34 bytes by getting permission to take EUC input as EUC-JP.

```
->c,s,d{(c.map!{|e|e+=128};s="EUCJP")if s=~r=/^J/
c.pack('c*').encode(d[r]?"EUCJP":d,s).bytes.map{|e|e-=d[r]?128:0}}

```

Try it online!

**Explanation**

```
->c,s,d{                                            # Function that takes 3 parameters
        (                           )if s=~r=/^J/   # If s is JIS: (starts with J)
                                                    #  (also store this regex for later)
         c.map!{|e|e+=128};                         # Add 128 to each codepoint
                           s="EUCJP"                # Change s to EUC-JP locale
  c.pack('c*')                                      # Pack codepoints into bytestring
    .encode(                                        # Encode the bytestring as follows:
                                                    #  Destination encoding is:
      d[r]?"EUCJP":d,                               #   If d is JIS, use EUC-JP instead
      s                                             #  Source encoding
    )
    .bytes                                          # Convert to bytes
    .map{|e|e-=d[r]?128:0}                          # If d is JIS, subtract 128
}

```

### Pure Math Version, ~~164~~ 162 bytes

Takes code points separately, and the encodings are integers: `0=JIS, 1=SHIFT_JIS, 2=EUC`.

-2 bytes from Jonathan Allen.

```
->a,b,s,d,e=160{k,t=[[a-32,b-32],[a*2-1+b/158-(2+a/222)*128,b-63-b/128-b/158*94],[a-e,b-e]][s]
[[k+32,t+32],[128+k/2+k%2+k/63*64,158+t+t/64-k%2*95],[k+e,t+e]][d]}

```

Try it online!
> 2 votes

# Answer
# 05AB1E, ~~37~~ 34 bytes

```
93ÝãDžy+∞x64&+₃+Ƶ₁L64K30+â)33+Iè`‡

```

Try it online! or validate all test cases.

First input is `[source encoding, destination encoding]`, with 0 representing JIS, 1 for EUC, and 2 for ShiftJIS.

Second input it `[byte pair]`.
> 2 votes

# Answer
# JavaScript (Node.js), 172 bytes

```
(a,b,x,y)=>eval('for(c=d=t=0;c-a|b-d;[c,d]=x(p,q))y(p=++t>>8,q=t&255)')
S=(k,t)=>[128+k/2+k%2/2+64*(k>62),(k%2?63+(t>63):158)+t]
J=(k,t)=>[32+k,32+t]
E=(k,t)=>[160+k,160+t]

```

Try it online!

Invoke as `f(227, 129, S, E)` where `S=Shift_JIS, E=EUC, J=JIS`.
> 1 votes

# Answer
# Jelly, 62 bytes

*Tired & ill so probably very beatable!*

```
⁹:64;95⁸ị+63+
‘&64+HƲḞ+Ø⁷,ç
94,þ`“¡ ɦ‘+€ç/€€€1¦
Ḣị¢⁼€€ŒṪṪ⁸;œị¢

```

A dyadic Link accepting `[SrcEncoding, DstEncoding]` on the left and `SrcCodePoint` on the right which yields `DstCodePoint`.

Where `SrcEncoding` and `DstEncoding` are:

```
Shift_JIS  1
      JIS  2
      EUC  3

```

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

# Answer
# Clojure, ~~51~~ 50 bytes

```
#(for[b(.getBytes(String. %2%)%3)](bit-and b 255))

```

Try it online!

Anonymous function taking three arguments: source encoding, input pair as a Java byte array, and destination encoding.

This relies on JVM's built-in conversion functionality. As other answers are doing, I took the liberty to modify the expected encoding strings to match the format recognized by the JVM:

* JIS -\> JIS0208 (Simply "JIS" is also listed in Java docs, but somehow doesn't work)
* Shift\_JIS remains as is
* EUC -\> EUC-JP
> 1 votes

# Answer
# Haskell, ~~185~~ ~~179~~ 153 bytes

```
x?(a,b)=[(a+32,b+32),(128+div a 2+rem a 2+64*div a 63,b+63+[95,div b 64]!!rem a 2),(a+160,b+160)]!!x
(x!y)i=y?head[(a,b)|a<-[1..],b<-[1..255],i==x?(a,b)]

```

Try it online!

Takes Encodings as 0=JIS, 1=Shift\_JIS, 2=EUC. Probably still a lot of room for improvement.
> 0 votes

---
Tags: code-golf, encoding
---


title: The Snail in the Well

text:
# Question
Title: The Snail in the Well
# Background

There's a common riddle that goes something like this:

> A snail is at the bottom of a 30 foot well. Every day the snail is able to climb up 3 feet. At night when they sleep, they slide back down 2 feet. How many days does it take for the snail to get out of the well?

The intuitive answer is

> 30 days, because the snail climbs at 1 foot per day for 30 days to reach the top,

but actually the answer is

> 28 days, because once the snail is 27 feet in the air (after 27 days), they will simply climb the remaining 3 feet to the top on the 28th day.

# Challenge

This challenge generalizes this riddle. Given three positive integers as input, representing the total height, the climb height, and the fall height, return the number of days it will take to climb out of the well.

If the snail cannot climb out of the well, you may return 0, return a falsy value, or throw an exception. You may also write code that will halt if and only if a solution exists.

If you wish, you may take the fall height as a negative integer.

# Test Cases

```
(30,  3,  2) -> 28
(84, 17, 15) -> 35
(79, 15,  9) -> 12
(29, 17,  4) -> 2
(13, 18,  8) -> 1
( 5,  5, 10) -> 1
( 7,  7,  7) -> 1
(69,  3,  8) -> None
(81, 14, 14) -> None

```

# Scoring

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

# Answer
> 22 votes
# Gray Snail, 1206 bytes for numeric I/O, 149 bytes for unary I/O

For fun. Composition of first program:

* 451 bytes, converting number into dots
* 121 bytes, core function (a separated version is written below)
* 634 bytes, converting dots into number

Take numeric input and output. Input is `A`, `B`, `C` respectively. Compared to other (near) `O(1)` answer, the code has a complexity of `O(n)`. But for large number, it may eat up your memory first.

Hang if no solution is found.

```
INPUT p
POP Z r .!
f
POP Z o .
q
POP Z p [p]
GOTO [Z]
0
POP Z n .
GOTO w
1
POP Z n ..
GOTO w
2
POP Z n ...
GOTO w
3
POP Z n ....
GOTO w
4
POP Z n .....
GOTO w
5
POP Z n ......
GOTO w
6
POP Z n .......
GOTO w
7
POP Z n ........
GOTO w
8
POP Z n .........
GOTO w
9
POP Z n ..........
GOTO w
w
POP Z o .[o][o][o][o][o][o][o][o][o][o][n]
GOTO [r] [p]
GOTO q
!
POP Z A .[o]
INPUT p
POP Z r .@
GOTO f
@
POP Z B .[o]
INPUT p
POP Z r .#
GOTO f
#
POP Z C .[o]
POP H N .[B]
U
POP Z A [A]
POP Z B [B]
GOTO D [A]
GOTO $ [B]
GOTO U
$
POP Z A .[A][C]
POP Z H ..[H]
POP Z B .[N]
GOTO U
D
POP Z r .
POP Z M .
POP Z N ...........
POP Z z .[N]
POP Z V .[H]
+
GOTO l[V] [H]
POP Z H [H]
POP Z z [z]
GOTO ( [z]
GOTO +
(
GOTO ) [H]
POP Z z .[N]
POP Z M ..[M]
POP Z V .[H]
GOTO +
)
POP Z r .0[r]
POP Z M ..[M]
POP Z H .[M]
POP Z M .
POP Z V .[H]
POP Z z .[N]
GOTO +
l
POP Z r .0[r]
GOTO -
l.
POP Z r .1[r]
GOTO -
l..
POP Z r .2[r]
GOTO -
l...
POP Z r .3[r]
GOTO -
l....
POP Z r .4[r]
GOTO -
l.....
POP Z r .5[r]
GOTO -
l......
POP Z r .6[r]
GOTO -
l.......
POP Z r .7[r]
GOTO -
l........
POP Z r .8[r]
GOTO -
l.........
POP Z r .9[r]
GOTO -
-
GOTO / [M]
POP Z H .[M]
POP Z M .
POP Z V .[H]
POP Z z .[N]
GOTO +
/
OUTPUT [r]

```

`f` is a (maybe) recursive function to convert integers into dots. Argument is saved in `[p]` and output in `[o]`.

`U` is a function testing `S1>=S2`, storing parameter in `B, A` while saving `A-B` into `A`.

Code starting from `D` is a stub converting dots into numbers.

The underlying principle is the same with my C answer (ripping off falsy output for impossible solutions).

## Standalone version, 149 ~~156~~ ~~157~~ ~~167~~ ~~170~~ ~~230~~ bytes, only support unary I/O

Input needs to be dots, e.g. `..........` for `10`.

```
INPUT A
INPUT B
INPUT C
POP N H .
GOTO U
$
POP N A .[A][C]
POP Z H ..[H]
U
POP Z A [A]
POP Z N ..[N]
GOTO D [A]
GOTO $ .[B] [N]
GOTO U
D
OUTPUT .[H]

```

`U` calculates `A=A-B`, and jumps to `D` when `A<=0`. Otherwise `$` assigns `A+C` to `A` and call `U`.

Hang if no solution is found.

**Tricks:** abuse the "compiler"'s ability to interpret empty string. You can rip off conditions in `GOTO` statement to make unconditioned jumps and the same trick works for `POP`.

**Remark:** I may golf it more by 3 bytes but by doing so, mine and WheatWizard's answer would have the exact same logic. The result is probably the shortest GraySnail solution and I'm trying to prove it.

# Answer
> 20 votes
> **Note:** the byte count is being questioned by Martin Ender in the comments. It seems there is no clear consensus about what to do with named, recursive lambda expressions in C# answers. So I have asked a question in Meta about it.

# C# (.NET Core), 32 31 bytes

```
f=(a,b,c)=>a>b?1+f(a-b+c,b,c):1

```

Try it online!

A recursive approach. If the snail cannot escape, it ends with the following message: `Process is terminating due to StackOverflowException.`

* 1 byte saved thanks to LiefdeWen!

# Answer
> 15 votes
# GRAY SNAIL, ~~219~~ ~~206~~ ~~169~~ ~~167~~ ~~159~~ ~~156~~ 146 bytes (unary IO)

```
INPUT a
INPUT u
INPUT d
POP U c
GOTO 1
3
POP f a [a][d]
POP U c ..[c]
1
GOTO 2 [a]
GOTO 3 [U] [u]
POP f U ..[U]
POP f a [a]
GOTO 1
2
OUTPUT [c].

```

I think I can golf this down a bit.

# Answer
> 12 votes
## JavaScript (ES6), ~~31~~ ~~28~~ 27 bytes

*Saved a few bytes thanks to @Arnauld*

I hadn't realized we could fail with an exception. Pretty sure this is optimal:

```
u=>d=>g=h=>h>u?1+g(h-u+d):1

```

Assign to a variable with e.g. `f=`, then call like `f(climb)(fall)(height)`. Throws `InternalError: too much recursion` if the climb is impossible.

---

## JavaScript (ES6), 38 bytes

```
f=(h,u,d=0)=>h>u?u>0?1+f(h-u,u-d):+f:1

```

A recursive function that returns the number of days, or `NaN` for never.

### Test cases

```
let f=(h,u,d=0)=>h>u?u>0?1+f(h-u,u-d):+f:1;

[
  [30,  3,  2],
  [84, 17, 15],
  [79, 15,  9],
  [29, 17,  4],
  [13, 18,  8],
  [ 5,  5, 10],
  [ 7,  7,  7],
  [69,  3,  8],
  [81, 14, 14]
].map(x => console.log(x + '', '->', f.apply(null, x)))
```

# Answer
> 10 votes
# Excel, ~~51~~ 46 bytes

-1 byte thanks to @Scarabee.

-4 because INT(x) = FLOOR(x,1)

```
=IF(B1<A1,IF(C1<B1,-INT((B1-A1)/(B1-C1)-1)),1)

```

Input taken from Cells A1, B1 and C1 respectively. Returns `FALSE` for invalid scenarios.

# Answer
> 8 votes
# C (gcc), 39 ~~43~~ ~~44~~ ~~46~~ ~~47~~ ~~58~~ ~~60~~ bytes

Only on 32-bit GCC and all optimizaitons turned off.

```
f(a,b,c){a=a>b?b>c?1+f(a-b+c,b,c):0:1;}

```

Return 0 when solution is impossible. A modified version of original recursive solution.

Inspired by @Jonah J solution and @CarlosAlejo C# solution.

*I'll update the expanded version later (after I finish my Grey Snail answer).*

# Answer
> 7 votes
# Java (OpenJDK 8), 35 bytes

```
(a,b,c)->b<a?c<b?(a+~c)/(b-c)+1:0:1

```

Try it online!

Math wins!

### Credits

# Answer
> 5 votes
# Python 2, 37 bytes

```
f=lambda x,y,z:x-y<1or 1+f(x-y+z,y,z)

```

Try it online!

Finally got my recursive version below my standard calculation (I was passing a count to my function instead of adding one before calling it).

# Python 2, 43 ~~46~~ bytes

```
#43 bytes
lambda x,y,z:y/x>0 or[1-(x-y)/(z-y),0][z/y]
#46 bytes
lambda x,y,z:y/x and 1or[1-(x-y)/(z-y),0][z/y]

```

Try it online!

Shaved 3 bytes by trading "\__ and 1" for "\__\>0".

Using boolean trickery, essentially executes:

```
if floor(y/x) > 0:
    return True # == 1
elif floor(z/y) == 1:
    return 0
elif floor(z/y) == 0:
    return 1-floor((x-y)/(z-y))
    # Python 2 implicitly treats integer division as floor division
    # equivalent: 1 + math.ceil((y-x)/(z-y))
    # because: -floor(-x) == ceil(x)

```

# Answer
> 4 votes
## Perl 5, 37 bytes

**35 bytes code +2 for `-pa`.**

```
$i-=$F[2]while++$\,($i+=$F[1])<$_}{

```

Try it online!

# Answer
> 4 votes
# Haskell, ~~30~~ ~~29~~ 27 bytes

```
(b!c)a=1+sum[b!c$a+c-b|a>b]

```

Try it online!

Shorter than the existing Haskell answer. Perhaps someone else can beat me.

This uses a recursive approach to solving the problem. Each recursion is essentially a day of movement for the snail. If the distance left to the end is less than the distance still required we end our recursion.

# Answer
> 4 votes
# R, 43 bytes

Borrowing from other answers:

```
g=function(a,b,c)`if`(b<a,1+g(a-b+c,b,c),1)

```

Gives error if no solution.

# Answer
> 3 votes
# J, 25 bytes

First a nice solution, which is a cheat, since it assumes that "anything other than a positive integer result" equals "None":

```
>.>:%/2-/\

```

## explanation

* `2-/\` use windows of length 2 across our 3 item input, placing a minus sign between each one, which for the input `30 3 2`, eg, returns `27 1`
* `%/` put a division symbol between each element of the list, in our case the list has only two items, so it means "divide 27 by 1"
* `>:` increment by 1
* `>.` take the ceiling

## official solution

Here is the official solution that converts negatives and infinity to 0, which part i was not able to find a satisfyingly terse solution for:

```
0:`[@.(>&0*<&_)>.>:%/2-/\

```

TIO

# Answer
> 3 votes
# PHP\>=7.1, 60 bytes

prints 0 for no escape

```
[,$h,$u,$d]=$argv;echo$h>$u?$u>$d?ceil(($h-$d)/($u-$d)):0:1;

```

PHP Sandbox Online

# PHP\>=7.1, 67 bytes

prints nothing for no escape

```
for([,$h,$u,$d]=$argv;($u>$d?:$h<=$u)&&0<$h+$t*$d-$u*++$t;);echo$t;

```

PHP Sandbox Online

# Answer
> 3 votes
# PowerShell, ~~95~~ 94 bytes

```
$g=$args[0]
$c=$args[1]
$f=$args[2]
$p=0
$d=0
1..$g|%{$d+=1;$p+=$c;if($p-ge$g){$d;exit}$p-=$f}

```

Try it online!

# Answer
> 2 votes
# Ruby, ~~49~~ 47 bytes

```
->h,a,b{h-a<1?1:(1.0*(h-a)/[a-b,0].max+1).ceil}

```

Throws exception if snail can't climb out

Try it online!

# Answer
> 2 votes
# Mathematica, ~~47~~ ~~40~~ 39 bytes

```
If[#==#2,1,⌈(#-#3)/(#2-#3)⌉~Max~0]&

```

*-7 bytes from @KeyuGan*

# Answer
> 2 votes
# Python v2 & v3, 44 Bytes

```
f=lambda x,y,z:1+f(x-(y-z),y,z)if x>y else 1

```

*^Infinite recursion (error) for None case.*

# Answer
> 2 votes
# QBIC, ~~31~~ 23 bytes

Just noticed the requirements changed. This version doesn't check if the snail will ever reach the top of the well.

```
≈:-:>0|q=q+1┘a=a-b+:]?q

```

The explanation below, for the original version that does check if a solution exists, covers all relevant parts of this code too.

---

Original, 31 byte answer:

```
~:>:|≈:-a>0|q=q+1┘c=c-a+b]?q\?0

```

## Explanation

```
~           IF
 :          cmd line arg 'a'  (the increment of our snail)
  >         is greater than
   :        cmd line arg 'b'  (the decrement, or daily drop)
    |       THEN
≈           WHILE
 :          cmd line arg 'c'  (the height of the well)
  -a        minus the increment (we count down the hieght-to-go)
    >0|     is greater than 0 (ie while we haven't reached the top yet)
q=q+1       Add a day to q (day counter, starts at 1)
┘           (syntactic linebreak)
c=c-a+b     Do the raise-and-drop on the height-to-go
]           WEND
?q          PRINT q (the number of days)
\?0         ELSE (incrementer <= decrementer) print 0 (no solution)

```

Try it online! (OK, not really: this is a translation of QBIC to QBasic code run in repl.it 's (somewhat lacking) QBasic enviroment)

# Answer
> 2 votes
## Batch, 66 bytes

```
@set/an=%4+1,a=%1-%2+%3
@if %1 gtr %2 %0 %a% %2 %3 %n%
@echo %n%

```

The second last test case printed nothing, and the last test case actually crashed `CMD.EXE`...

# Answer
> 2 votes
# 05AB1E, 19 bytes

```
0[¼²+D¹<›i¾q}³-D1‹#

```

Explanation:

```
0                   Initialise stack with 0
 [                  while(true)
  ¼                   increment the counter variable
   ²+                 add the second input to the top of the stack
     D¹<›i            if it is greater than or equal to the first input
          ¾             push the counter variable
           q            terminate the program
             }        end if
              ³-      subtract the third input from the top of the stack
                D     duplicate top of stack
                 1‹   if it is less than 1
                   #  break the loop

```

For invalid values, this may return any value less than 1. However, in 05AB1E, only 1 is truthy so this meets the requirement that the output for an invalid value should be falsy.

Try it online!

# Answer
> 2 votes
# 05AB1E, 12 bytes

```
.×ηO<²›1k2÷>

```

Try it online!

Prints `0` if impossible.

Input format:

```
[climb, -fall]
height

```

# Answer
> 2 votes
# PHP, 60 bytes

```
[,$h,$v,$d]=$argv;echo$h>$v?$v>$d?ceil(($h-$d)/($v-$d)):N:1;

```

prints `N` for `None`. Run with `-r`.

# Answer
> 2 votes
# Japt, 12 bytes

```
@UµV-W §W}aÄ

```

Test it online!

Outputs `undefined` for never, after possibly freezing your browser for a while, so please be careful.

I'm not convinced this is optimal. `oWV-W l` works on all but the last three cases...

# Answer
> 2 votes
# Excel VBA, 47 Bytes

Anonymous VBE immediate window function that takes input in from the range `[A1:C1]` from the `ActiveSheet` object outputs to the VBE immediate window

This primarily Excel formula based solution appears to be smaller than any purely VBA solution that I can come up with :(

```
?[If(B1>C1,-Int((B1-A1)/(B1-C1)-1),Int(A1=B1))]

```

# Answer
> 2 votes
# HP-15C Programmable Calculator, 26 Bytes

The three numbers are loaded into the stack in order before running the program. The fall height is entered as a negative number. If the snail cannot climb out of the well, the result is either a negative number or error #0 (zero divide error).

Op codes in hex:

```
C5 C1 B4 C5 FB 74 1A C4 FA B4 C5 FD C1 C1 A3 70 C6 F0 B4 FA EB F1 FA B2 0A F1

```

Instruction meanings:

```
x↔y
ENTER
g R⬆
x↔y
−
g TEST x≤0
GTO A
R⬇
+
g R⬆
x↔y
÷
ENTER
ENTER
f FRAC
TEST x≠0
EEX
0
g R⬆
+
g INT
1
+
g RTN
f LBL A
1

```

You can try the program with this HP-15C simulator.

# Answer
> 2 votes
# Common Lisp, 49 bytes

```
(defun f(a b c)(if(> a b)(1+(f(+(- a b)c)b c))1))

```

Try it online!

Recursive function, stack overflow if no solution found.

# Answer
> 1 votes
# Jelly, 10 bytes

```
ẋ;\m2S€<i0

```

Try it online!

# Answer
> 1 votes
**Haskell, 47 ~~55~~ bytes (48 if tuple required)**

```
f d c s|d<=c=1|c<s= -1|d>c||c<s=1+(f(d-c+s)c s)

```

tuple variation

```
f(d,c,s)|d<=c=1|c<s= -1|d>c||c<s=1+(f(d-c+s)c s)

```

Explanation

```
f d c s       function that does all the heavy lifting =)
              d - depth
              c - climb per day
              s - slide per night

 |d<=c=1             recursion terminator. 1 day of climbing
 |c<s= -1            possibility check. top can't be reached
 |otherwise=1+(f(d-c+s)c s)  1 day plus the rest of the distance

```

# Answer
> 1 votes
# Python 3, 41 Bytes

```
f=lambda a,b,c:int(b>=a)or 1+f(a-b+c,b,c)

```

Error for Never

Outgolf @veganaiZe

# Answer
> 1 votes
# Google Sheets, 43 Bytes

Worksheet cell function that takes input from cells `A1:C1` and outputs to the calling cell

```
=if(B1>C1,-int((B1-A1)/(B1-C1)-1),int(A1=B1

```

# Excel, 45 Bytes

Same as above, but formatted for MS Excel

```
=If(B1>C1,-Int((B1-A1)/(B1-C1)-1),Int(A1=B1))

```

# Answer
> 1 votes
# APL (Dyalog), 13 bytes

```
(⌈+÷⊢)/0⌈2-/⊢

```

Try it online!

---

Errors on division by zero if the snail cannot climb out of the well.

# Answer
> 1 votes
# C# (.NET Core), 37 bytes

```
(h,c,f)=>h>c?f<c?1+(h-f-1)/(c-f):0:1;

```

Non-recursive lambda. Uses formula found here. Could be shortened by 6 bytes if "any negative result" is a valid way to return failure; currently returns 0 instead.

# Answer
> 1 votes
# Jelly, 8 bytes

```
ẋ+\<i0HĊ

```

Try it online!

**How it Works**

```
ẋ+\<i0HĊ - main link. The inputs are a list and an int, e.g. 3,-2 and 30
ẋ          - repeat the first input a number of times equal to the second input
               e.g. 3,-2,3,-2,3,-2,3,-2,...3,-2 (60 elements total)
 +\        - cumulative sum, e.g. 3,1,4,2,5,3,6,4,7,5,8,...32,30
   <       - less than (the second element)
    i0     - get the index of the first 0
      HĊ   - halve and round up

```

# Answer
> 1 votes
# bash, 39 bytes

```
echo $((d=$2-$3,d>0?$1/d-$3/d:$2/$1%2))

```

Try it online!

# Answer
> 1 votes
# Kotlin, 70 bytes

```
fun s(h:Int,c:Int,f:Int):Int=if(h>c)if(c>f)1+s(h-c+f,c,f)else 0 else 1

```

Try it online!

# Answer
> 1 votes
# @yBASIC, 45 bytes

```
@__
_=_+_%-_#__=__+!.GOTO(@_)+"_"*(_>_%)@_?__

```

The language has no support for input so you have to set variables \_, \_%, and \_# to the well depth, fall distance, and climb distance, respectively. (Is this allowed?)

Try it online! (Experimental)

# Answer
> 1 votes
# GolfScript, 30 bytes

```
:c-.{(c@-.{/))}{;1<}if}{;;1}if

```

The code in the header is purely to make the input easier - it just swaps around the order into another valid inpu format, just for ease of copying examples.

I thought this was going to be an 8-bte solution! And it is... kinda. Turns out we need two catches here, and each of them add a ton to make sure GS doesn't error out. Oh well. It works :)

Try it online!

# Answer
> 1 votes
# PowerShell, ~~60~~ 59 bytes

<sup>-1 byte thanks to mazzy</sup>

```
param($g,$c,$f)for(){++$d;if(($p+=$c)-ge$g){$d;exit}$p-=$f}

```

Try it online!

An optimization of root's answer. If you like this, upvote his.

This runs forever on tests that are impossible. It also `exit`s the script altogether on return so the test script is a bit sillier than normal.

# Answer
> 1 votes
# PowerShell, 50 bytes

```
for($g,$c,$f=$args;($p+=$c)-lt$g;++$d){$p-=$f}1+$d

```

Try it online!

# Answer
> 0 votes
# R, 50 bytes

```
f=function(x,y,z)`if`(y>z,ceiling((x-z)/(y-z)),0)

```

Similar logic to others, let down by ceiling and function being such long words..

Usage:

```
> f(30,3,2)
[1] 28

> f(30,3,20)
[1] 0

```

# Answer
> 0 votes
## Clojure - ~~80~~ 70 bytes

```
(defn snail[x y z](cond(>= y x)1(> y z)(Math/ceil(/(- x z)(- y z))):else false))

```

Ungolfed version:

```
(defn snail [x y z]
  (cond
    (>= y x) 1
    (> y z)  (Math/ceil (/ (- x z) (- y z)))
    :else    false))

```

---

As a (shorter) anonymous function:

```
#(cond(<= %2 %1)1(> %2 %3)(Math/ceil(/(- %1 %3)(- %2 %3))):else false)

```

My original thinking (without checking, naturally) was that the `%` chars in the substitution markers would outweigh the benefit of getting rid of `defn snail [x y z]`. Apparently NOT! :-)

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

```
D,f,@@@,¿@>,@$_+abRbUp${f}1+,1¿

```

Try it online!

First ever use of the ternary expression! Raises an `Exception` on invalid inputs

## How it works

```
D,f,@@@,		; Declare a triadic function
			; Example arguments: 		[30 3 2]. Labelled [A B C] here
	¿		; If...
		@>	; 	A > B
	,		; Then...
		@	; 	Reverse;	STACK = [2 3 30]
		$_	; 	Swap subtract;	STACK = [2 27]
		+	; 	Add;		STACK = [29]
		abRbU	; 	Reversed args;	STACK = [29 2 3 30]
		p$	; 	Pop and swap;	STACK = [29 3 2]
		{f}	; 	Call 'f';	STACK = [27]
		1+	; 	Add 1;		STACK = [28]
	,		; Else...
	1		; 	Push 1;
	¿		; Endif
			;			Returns  28

```

Try it online!

# Answer
> 0 votes
# Python 3, 36 bytes

```
f=lambda h,a,b:h and-~f(h>>a<<b,a,b)

```

Try it online!

I/O format is questionable, but I think the idea is interesting enough for it to be posted.

**Input**:

* `h`: If the depth of the well is `d`, `h` is an integer whose binary representation has `d` digits (ignoring leading zeros). For example, if `d = 4`, `h` can be `0b1111`.
* `a`: The climb distance
* `b`: The fall distance, (positive integer).

**Output**: Number of days for the snail to climb out of the well. If it's impossible to climb out, runs forever.

## Explanation

`h>>a<<b` will have the number of binary digits equals to the remaining height after one day. If the snail reaches the top during the day, then `h>>a` is `0`, thus `h>>a<<b` is still 0.

The function is a recursive function that returns 0 if `h==0`, else recurs on `h = h>>a<<b`. The golfed code use the fact that `-~x == 1+x` to save 1 space.

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


# Question
Title: (RGS 5/5) Computing the set of all set partitions with fixed sizes
# Task

Given a set of `n` unique elements and a multiset `l` of positive numbers that add up to `n`, find all the ways of partitioning those unique elements into disjoint sets with sizes given by the elements of `l`.

(A multiset is a set that allows repeated elements)

The point here is that we are taking everything in the output as sets, so order doesn't matter in any place.

This may be simpler to understand if you check some test cases below.

# Input

The multiset `l` of positive integers that add up to `n`. Note that the elements in `l` may appear repeatedly. This might be given as

* a list `l = [1, 1, 2, 2, 3]`
* arguments to a function `f(1, 1, 2, 2, 3)`
* or any other sensible way of representing a multiset

You may assume the representation of `l` is ordered.

You may also take a list/set/collection of `n` distinct integers, or you may generate it depending on the sum of the elements in `l`. If you generate it, you may use *any* `n` distinct integers for the set to be partitioned but your remaining code should work for any set of `n` integers. The set you use must be specified in your answer. Suggestions include:

* a range starting in `0`: `[0, 1, ..., n-1]`
* a range starting in `1`: `[1, 2, ..., n]`

# Output

The different ways in which your collection can be split in sets with the given sizes. Your output should be unambiguous.

# Reference implementation

You can find a vanilla python reference implementation here or you can try it online.

# Test cases

I am using the set `0, ..., n-1` when the list adds up to `n`. In the TIO link, that list is given explicitly to my function.

After the `->`, each line represents one possible way of splitting the set.

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

[3] -> [
    [[0, 1, 2]]
]

[1, 2] -> [
    [[0], [1, 2]]
    [[1], [0, 2]]
    [[2], [0, 1]]
]

[2, 2] -> [
    [[0, 1], [2, 3]]
    [[0, 2], [1, 3]]
    [[0, 3], [1, 2]]
]

[1, 1, 2] -> [
    [[0], [1], [2, 3]]
    [[0], [2], [1, 3]]
    [[0], [3], [1, 2]]
    [[1], [2], [0, 3]]
    [[1], [3], [0, 2]]
    [[2], [3], [0, 1]]
]

[1, 2, 2] -> [
    [[0], [1, 2], [3, 4]]
    [[0], [1, 3], [2, 4]]
    [[0], [1, 4], [2, 3]]
    [[1], [0, 2], [3, 4]]
    [[1], [0, 3], [2, 4]]
    [[1], [0, 4], [2, 3]]
    [[2], [0, 1], [3, 4]]
    [[2], [0, 3], [1, 4]]
    [[2], [0, 4], [1, 3]]
    [[3], [0, 1], [2, 4]]
    [[3], [0, 2], [1, 4]]
    [[3], [0, 4], [1, 2]]
    [[4], [0, 1], [2, 3]]
    [[4], [0, 2], [1, 3]]
    [[4], [0, 3], [1, 2]]
]

[2, 2, 2] -> [
    [[0, 1], [2, 3], [4, 5]]
    [[0, 1], [2, 4], [3, 5]]
    [[0, 1], [2, 5], [3, 4]]
    [[0, 2], [1, 3], [4, 5]]
    [[0, 2], [1, 4], [3, 5]]
    [[0, 2], [1, 5], [3, 4]]
    [[0, 3], [1, 2], [4, 5]]
    [[0, 3], [1, 4], [2, 5]]
    [[0, 3], [1, 5], [2, 4]]
    [[0, 4], [1, 2], [3, 5]]
    [[0, 4], [1, 3], [2, 5]]
    [[0, 4], [1, 5], [2, 3]]
    [[0, 5], [1, 2], [3, 4]]
    [[0, 5], [1, 3], [2, 4]]
    [[0, 5], [1, 4], [2, 3]]
]

[1, 2, 3] -> [
    [[0], [1, 2], [3, 4, 5]]
    [[0], [1, 3], [2, 4, 5]]
    [[0], [1, 4], [2, 3, 5]]
    [[0], [1, 5], [2, 3, 4]]
    [[0], [2, 3], [1, 4, 5]]
    [[0], [2, 4], [1, 3, 5]]
    [[0], [2, 5], [1, 3, 4]]
    [[0], [3, 4], [1, 2, 5]]
    [[0], [3, 5], [1, 2, 4]]
    [[0], [4, 5], [1, 2, 3]]
    [[1], [0, 2], [3, 4, 5]]
    [[1], [0, 3], [2, 4, 5]]
    [[1], [0, 4], [2, 3, 5]]
    [[1], [0, 5], [2, 3, 4]]
    [[1], [2, 3], [0, 4, 5]]
    [[1], [2, 4], [0, 3, 5]]
    [[1], [2, 5], [0, 3, 4]]
    [[1], [3, 4], [0, 2, 5]]
    [[1], [3, 5], [0, 2, 4]]
    [[1], [4, 5], [0, 2, 3]]
    [[2], [0, 1], [3, 4, 5]]
    [[2], [0, 3], [1, 4, 5]]
    [[2], [0, 4], [1, 3, 5]]
    [[2], [0, 5], [1, 3, 4]]
    [[2], [1, 3], [0, 4, 5]]
    [[2], [1, 4], [0, 3, 5]]
    [[2], [1, 5], [0, 3, 4]]
    [[2], [3, 4], [0, 1, 5]]
    [[2], [3, 5], [0, 1, 4]]
    [[2], [4, 5], [0, 1, 3]]
    [[3], [0, 1], [2, 4, 5]]
    [[3], [0, 2], [1, 4, 5]]
    [[3], [0, 4], [1, 2, 5]]
    [[3], [0, 5], [1, 2, 4]]
    [[3], [1, 2], [0, 4, 5]]
    [[3], [1, 4], [0, 2, 5]]
    [[3], [1, 5], [0, 2, 4]]
    [[3], [2, 4], [0, 1, 5]]
    [[3], [2, 5], [0, 1, 4]]
    [[3], [4, 5], [0, 1, 2]]
    [[4], [0, 1], [2, 3, 5]]
    [[4], [0, 2], [1, 3, 5]]
    [[4], [0, 3], [1, 2, 5]]
    [[4], [0, 5], [1, 2, 3]]
    [[4], [1, 2], [0, 3, 5]]
    [[4], [1, 3], [0, 2, 5]]
    [[4], [1, 5], [0, 2, 3]]
    [[4], [2, 3], [0, 1, 5]]
    [[4], [2, 5], [0, 1, 3]]
    [[4], [3, 5], [0, 1, 2]]
    [[5], [0, 1], [2, 3, 4]]
    [[5], [0, 2], [1, 3, 4]]
    [[5], [0, 3], [1, 2, 4]]
    [[5], [0, 4], [1, 2, 3]]
    [[5], [1, 2], [0, 3, 4]]
    [[5], [1, 3], [0, 2, 4]]
    [[5], [1, 4], [0, 2, 3]]
    [[5], [2, 3], [0, 1, 4]]
    [[5], [2, 4], [0, 1, 3]]
    [[5], [3, 4], [0, 1, 2]]
]

[1, 1, 4] -> [
    [[0], [1], [2, 3, 4, 5]]
    [[0], [2], [1, 3, 4, 5]]
    [[0], [3], [1, 2, 4, 5]]
    [[0], [4], [1, 2, 3, 5]]
    [[0], [5], [1, 2, 3, 4]]
    [[1], [2], [0, 3, 4, 5]]
    [[1], [3], [0, 2, 4, 5]]
    [[1], [4], [0, 2, 3, 5]]
    [[1], [5], [0, 2, 3, 4]]
    [[2], [3], [0, 1, 4, 5]]
    [[2], [4], [0, 1, 3, 5]]
    [[2], [5], [0, 1, 3, 4]]
    [[3], [4], [0, 1, 2, 5]]
    [[3], [5], [0, 1, 2, 4]]
    [[4], [5], [0, 1, 2, 3]]
]

```

---

This is the fifth and **final** challenge of the RGS Golfing Showdown. If you want to participate in the competition, you have 96 hours to submit your eligible answers. Remember there is still 300 reputation in prizes! (See 6 of the rules)

Also, as per section 4 of the rules in the linked meta post, the "restricted languages" for this third challenge are *only* Sledgehammer,  and Mathematica so submissions in these languages are not eligible for the final prize. But *they can still be posted!!*

## Final prize

If you want to be considered for the final prize, at the end of your answer to this challenge please add a link to the eligible submissions you want to be considered for your final score, as well as the scores those answers got! This way it will be slightly easier for me to keep track of everything. Thanks!

This is still a regular challenge, so enjoy!

# Answer
> 5 votes
# 05AB1E, 9 bytes

```
œεI£€{{}ê

```

Try it online!

```
œ           # permutations of the [0, ..., n-1] input
 ε     }    # for each permutation:
  I£        #  cut it in parts of lengths given by the second input
    €{      #  sort each part
      {     #  sort the list of parts
        ê   # sort and uniquify the list of lists of parts

```

# Answer
> 5 votes
# Python 3, ~~123~~ ~~118~~ ~~114~~ 112 bytes

Input: set `s` representing a list of `n` unique elements, and an iterable `l` representing the multiset.

Output: a set of all partitions, where each partition is a tuple of tuples of elements (aka output is a set of tuples of tuples).

```
lambda s,l:{(*sorted(p),)for p in product(*(combinations(s,i)for i in l))if{*sum(p,p)}>s}
from itertools import*

```

Try it online!

## Approach

**Step 1**: For each element `i` of the multiset `l`, we find all combinations of `i` elements of `s`. We then find the Cartesian products of them. This is the list of candidate partitions.
For example: for `l = [1,2], s = ABC`, we first find all combinations

* of 1 element: `A, B, C`
* of 2 elements: `AB, AC, BC`

The candidate partitions are the Cartesian product of the above list of combinations:

```
[A,AB]
[A,AC]
[A,BC]
[B,AB]
[B,AC]
[B,BC]
[C,AB]
[C,AC]
[C,BC]

```

**Step 2**: Filter out the invalid partitions (partitions that do not add up to `s`).
For the above example, only the following partitions are kept:

```
[A,BC]
[B,AC]
[C,AB]

```

## Code breakdown

```
lambda s,l:
{
  (*sorted(p),)                     # convert partition to a sorted tuple (of tuples)
  for p in product(                 # for each candidate partition
    *(combinations(s,i)for i in l)
  )
  if{*sum(p,p)}>s                   # keep only if partition add up to s
}                              # put everything in a set to filter out duplicates

```

Each partition is stored as a sorted tuple of sorted tuple. This ensure no duplicate in the final result.

`{*sum(p,p)}>s` checks if a candidate partition is valid (aka contains all element in `s`). This work by putting all elements in the partition and some extra elements into a set, then check if the set is a superset of `s`.

For example: for `s={0,1,2,3}` and valid partition `p=((0,1),(2,3))`:
`sum(p,p)` evaluates to `((0,1),(2,3),0,1,2,3)`, which when converted into set is a superset of `s`.

For `s={0,1,2,3}` and invalid partition `p=((0,1),(1,2))`:
`sum(p,p)` evaluates to `((0,1),(1,2),0,1,2)`, which when converted into set becomes `{0,1,2,(0,1),(1,2)}`, not a superset of `s`.

# Answer
> 4 votes
# JavaScript (ES6),  ~~158 156~~  141 bytes

Takes input as `(a)(r)`, where \\$a\\$ is the representation of the input set \\$l\\$ as an ordered array, and \\$r\\$ is the range \\$\[1,2,...,n\]\\$.

Prints the results.

```
a=>r=>(F=(k,m,o=[],p,s=[],n=a[k])=>n?s[n-1]?F(++k,m,[...o,s],a[k]-n?0:s[0]):r.map(i=>i<p|m>>i&1||F(k,m|1<<i,o,i,[...s,i])):console.log(o))(0)

```

Try it online!

### Commented

```
a =>                      // a[] = ordered representation of the input set
r => (                    // r[] = range [1, 2, ..., n]
  F = (                   // F is a recursive function taking:
    k,                    //   k = index of the current entry in a[]
    m,                    //   m = bitmask of values already assigned in the output
    o = [],               //   o[] = output
    p,                    //   p = either 0 or a previous value (as a lower bound)
    s = [],               //   s[] = array representing the current set
    n = a[k]              //   n = k-th entry in a[]
  ) =>                    //
    n ?                   // if n is defined:
      s[n - 1] ?          //   if the current set is not full:
        F(                //     do a recursive call:
          ++k,            //       increment k
          m,              //       pass m unchanged
          [...o, s],      //       append s[] to o[]
          a[k] - n ? 0    //       set p to 0 if the next set has a different size
                   : s[0] //       or to s[0] if it has the same size
        )                 //     end of recursive call
      :                   //   else:
        r.map(i =>        //     for each value i in the range r[]:
          i < p |         //       abort if i is less than p
          m >> i & 1 ||   //       or the i-th bit is already set in m
          F(              //       otherwise, do a recursive call:
            k,            //         pass k unchanged
            m | 1 << i,   //         set the i-th bit in m
            o,            //         pass o unchanged
            i,            //         set p to i
            [...s, i]     //         append i to s[]
          )               //       end of recursive call
        )                 //     end of map()
    :                     // else:
      console.log(o)      //   leaf node: print o[]
)(0)                      // initial call to F with k = 0

```

---

### Previous answers

* RGS 1/5 \- JavaScript, 37 bytes
* RGS 2/5 \- CP-1610 machine code, 28 bytes (or 27.5)
* RGS 3/5 \- JavaScript, 79 bytes
* RGS 4/5 \- JavaScript, 206 bytes

Total score: **491 bytes**

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

Uses the range \[1,2,...,n\]

```
Union[Sort/@(Sort/@#~TakeList~a&/@Permutations@Range@Tr[a=#])]&

```

Try it online!

# Answer
> 3 votes
# Jelly, ~~16~~ ~~15~~ 13 bytes

```
Œ!ṁ€R}Ṣ€Ṣ¥€ṢQ

```

-2 bytes thanks to *@NickKennedy* by golfing the loose link to an inline one with `}`.

Try it online.

**Explanation:**

```
Œ!ṁ€R}Ṣ€Ṣ¥€ṢQ  # Main link taking two list arguments
               # i.e. left=[0,1,2,3,4]; right=[1,2,2]
Œ!             #  Get all permutations of the (implicit) left argument
               #   i.e. [0,1,2,3,4] → [[0,1,2,3,4],[0,1,2,4,3],...,[4,3,2,1,0]]
     }         #  Turn a monad into a dyad by using the right argument:
    R          #   Create a range of each inner integers
               #    i.e. [1,2,2] → [1,[1,2],[1,2]]
  ṁ€           #   And mold each permutation based on that
               #    i.e. [3,0,2,4,1] and [1,[1,2],[1,2]] → [3,[0,2],[4,1]]
          €    #  Map,
         ¥     #  using the previous two links as dyad:
      Ṣ€       #   Sort each inner-most list
               #    → [[0,[1,2],[3,4]],[0,[1,2],[3,4]],...,[4,[2,3],[0,1]]]
        Ṣ      #   Then sort each inner list
               #    → [[0,[1,2],[3,4]],[0,[1,2],[3,4]],...,[[0,1],[2,3],4]]
           Ṣ   #  And after the map, sort the outer list
               #   → [[0,[1,2],[3,4]],[0,[1,2],[3,4]],...,[[0,4],[1,3],2]]
            Q  #  And uniquify it
               #   → [[0,[1,2],[3,4]],[0,[1,3],[2,4]],...,[[0,4],[1,3],2]]
               #  (after which the result is output implicitly)

```

---

**Original ~~16~~ 15 bytes answer:**

```
⁹R⁸ṁ
Œ!çṢ€Ṣɗ€ṢQ

```

First (semi-complex) Jelly answer, so can definitely be golfed.. I probably can't find the builtins I'm looking for, since I have the feeling there should be a builtin for `⁹R⁸ṁ` similar as 05AB1E's `£`.
Port of the approach used by *@Grimmy* in his 05AB1E answer.

Try it online.

**Explanation:**

```
⁹R⁸ṁ        # Define a link taking two list arguments
            # i.e. left=[1,2,2]; right=[3,0,2,4,1]
⁹           #  Use the left argument
 R          #  And create a range of each inner integers
            #   i.e. [1,2,2] → [1,[1,2],[1,2]]
  ⁸         #  Then take the right argument
   ṁ        #  And mold it based on the earlier list
            #   i.e. [3,0,2,4,1] and [1,[1,2],[1,2]] → [3,[0,2],[4,1]]

Œ!çṢ€Ṣɗ€ṢQ  # Main link taking two list arguments
            # i.e. left=[0,1,2,3,4]; right=[1,2,2]
Œ!          #  Get all permutations of the (implicit) left argument
            #   i.e. [0,1,2,3,4] → [[0,1,2,3,4],[0,1,2,4,3],...,[4,3,2,1,0]]
       €    #  Map,
      ɗ     #  using the previous three links as dyad:
  ç         #   Apply the link we defined above,
            #   which uses this main-link's right as left argument for the helper-link
            #    → [[0,[1,2],[3,4]],[0,[1,2],[4,3]],...,[4,[3,2],[1,0]]]
   Ṣ€       #   Sort each inner-most list
            #    → [[0,[1,2],[3,4]],[0,[1,2],[3,4]],...,[4,[2,3],[0,1]]]
     Ṣ      #   Then sort each inner list
            #    → [[0,[1,2],[3,4]],[0,[1,2],[3,4]],...,[[0,1],[2,3],4]]
        Ṣ   #  And after the map, sort the outer list
            #   → [[0,[1,2],[3,4]],[0,[1,2],[3,4]],...,[[0,4],[1,3],2]]
         Q  #  And uniquify it
            #   → [[0,[1,2],[3,4]],[0,[1,3],[2,4]],...,[[0,4],[1,3],2]]
            #  (after which the result is output implicitly)

```

---

And not that it matters, but my other *RGS Golfing Showdown* answers are:

Total score: **466 bytes**

# Answer
> 3 votes
# Jelly, 12 bytes

```
œcŒpFQƑ$ƇṢ€Q

```

Try it online!

A dyadic link taking the list of \\$n\\$ integers as the left argument and the list of set lengths as the right. Returns a list of lists.

Thanks to @KevinCruijssen for pointing out an omission in my original answer.

## Previous RGS submissions:

1. Jelly 12 bytes
2. BBC BASIC V 92 bytes
3. Jelly 37 bytes
4. R 128 bytes
5. Jelly 12 bytes (this post)

**Total: 281 bytes**

# Answer
> 3 votes
# Jelly, 12 bytes

```
œcŒpṢ€FQƑ$ƇQ

```

**Try it online!**

---

**Overal RGS admissible competition entries:**

RGS 1/5 - Jelly, 7
RGS 2/5 - Husk, 22
RGS 3/5 - Jelly, 36
RGS 4/5 - MATL, 26 *
This: 12

**Total = 103 bytes**

<sub>* Might be 25, but I haven't proven that the 25 would never yield multiple results</sub>

# Answer
> 2 votes
# 05AB1E, ~~18~~ 17 bytes

```
œ€.œ€`€€{ʒ€gQ}€{Ù

```

Try it online!, or verify some test cases

---

### Explanation

```
                                     - Takes input of the numbers [1..N]
œ                                    - Permutations of this list
 €.œ                                 - Partitions of each of these permutations
    €`                               - Flatten these 1 level
      €€{                            - Sort the lists in each list in each partition
        ʒ                            - Filter the partitions
          €g                         - Where the size of the sub partitions...
            Q}                       - Equal to the second input (l)
              €{Ù                    - Sort and uniquify these
                                     - Output implicitly

```

---

### Submissions for consideration

(4/5) Sledgehammer 6 bytes

(3/5) 05AB1E 38 bytes

(2/5) C# 76 bytes

(1/5) 05AB1E 6 bytes

# Total = 143

# Answer
> 2 votes
# Japt `-Q`, 13 bytes

```
á £V®Xj0Z ñ
â

```

Try it

**Submissions**

(1/5) Japt, 9 bytes

(2/5) CJam, 23 bytes

(3/5) Japt, 40 or 41 bytes (I don't know which one to use, I'm not sure if the 40 byte one is valid)

(4/5) Magma, 34 bytes

**Total Score: 120 (or maybe 119)**

# Answer
> 1 votes
# , 47 bytes

```
[:~.~:@I.(/:(#,])&.>)@(<@/:~;.1)"1[:(!A.&i.])+/

```

Try it online!

I entirely missed the Portuguese one, so I'm out of the final prize anyway.

And J is not so good for handling non-rectangular arrays.

### How it works

```
[:~.~:@I.(/:(#,])&.>)@(<@/:~;.1)"1[:(!A.&i.])+/

[:(!A.&i.])+/    NB. all permutations of 0..n-1
           +/    NB. sum of l, i.e. the value of n
  (   &i.])      NB. array of 0..n-1
   !  &i.        NB. array of 0..n!-1
    A.           NB. (0..n!-1)-th permutations of 0..n-1

~:@I.    NB. cut vector (1 2 3 -> 1 1 0 1 0 0)
   I.    NB. for each number k at index i, k copies of i
         NB. e.g. 1 2 3 -> 0 1 1 2 2 2
~:@      NB. nub sieve; does each item appear for the first time?

(/:(#,])&.>)@(<@/:~;.1)"1    NB. cut, sort each item, and sort each row
                       "1    NB. on each row...
             (     ;.1)    NB. cut to the lengths of l
                           NB. e.g. 1 1 0 (f;.1) 0 1 2 -> (f 0)(f 1 2)
              <@/:~        NB. sort each item and enclose
(          )@     NB. then...
 /:               NB. sort the row by...
   (   )&.>       NB. the result applied to each item x...
    #,]           NB. the length of x, followed by x itself
                  NB. that is, sort by lengths then content

[:~.    NB. finally, remove duplicate rows to get the answer

```

# Answer
> 1 votes
# Husk, 14 bytes

```
u→SġÖȯLuΣmOΠMṖ

```

**Try it online!**

...I feel like the `→SġÖȯLuΣ` (last-entry-of hook group-by sort-by compose length deduplicate concatenated) should be `XȯLuΣ` where `X` is "maximals-by-predicate", saving 3 bytes, but I can't seem to find such a high-level-function. Maybe I'm being blind?

# Answer
> 1 votes
# GAP, ~~145 127~~ 105 bytes

```
f:={l,c}->(i->Orbit(SymmetricGroup(c),Set(l,n->Set([1..n],k->NextIterator(i))),OnSetsSets))(Iterator(c));

```

Try it online!

This is absurdly long, but I like computing the answer as an orbit of a group action. I have mixed feelings about creating the first element using an `Iterator`...

# Answer
> 1 votes
# Charcoal, 95 bytes

```
⊞υＥ⊕⌈θＥ№θι⟦⟧Ｆη«≔υζ≔⟦⟧υＦζＦＬκＦ∨⊕⌕§κλ⟦⟧№θλ¿‹Ｌ§§κλμλ⊞υＥκ⎇⁻ξλνＥν⎇⁻ρμπ⁺π⟦ι⟧»≔⟦⟧ζＦυ«≔⟦⟧εＦιＦκ⊞ελ⊞ζε»⪫ζ¶

```

Try it online! Link is to verbose version of code. I don't often get to use the `r` variable; I think this might be only the second time ever. Takes the set counts and unique entries as arguments. Explanation:

```
⊞υＥ⊕⌈θＥ№θι⟦⟧

```

Make a list of lists of sets (also actually lists), where each element of that list will have a number of sets equal to the count of occurrences of that index in the input set counts, and push that list to the predefined empty list, which is now technically a list of lists of lists of lists.

```
Ｆη«

```

Loop over the unique entries.

```
≔υζ≔⟦⟧υ

```

Move the list of lists of lists of sets into a temporary variable so that it can be cleared to accumulate the results of this pass.

```
Ｆζ

```

Loop over each list of lists of sets from the previous pass.

```
ＦＬκ

```

Loop over each possible set count.

```
Ｆ∨⊕⌕§κλ⟦⟧№θλ

```

Loop over each set, but if there is more than one empty set then stop at the first.

```
¿‹Ｌ§§κλμλ

```

Ignore this set if it's full.

```
⊞υＥκ⎇⁻ξλνＥν⎇⁻ρμπ⁺π⟦ι⟧

```

Construct a new list of lists of sets by replacing the one at the current set count with a new list of sets constructed by replacing the current set by union with the current unique entry. This is done to ensure that the new lists are all clones.

```
»≔⟦⟧ζＦυ«≔⟦⟧εＦιＦκ⊞ελ⊞ζε»

```

Flatten each list of lists of sets in the resulting list into a list of sets.

```
⪫ζ¶

```

Output the list of lists of sets in a human-readable manner. (This only costs 1 byte, so I think it's fair.)

### Submission history:

(1/5) Charcoal, 19 bytes (Retina 0.8.2, 68 bytes)

(2/5) Charcoal, 31 bytes (Retina, 74 bytes)

(3/5) vi, 48 bytes (Charcoal, 50 bytes; Batch, 265 bytes)

(4/5) Charcoal, 41 bytes

(5/5) Charcoal, 95 bytes

Total score: 234 bytes

Total Charcoal score: 236 bytes

Wooden Spoon score: 543 bytes

# Answer
> 1 votes
# (with partitions library), 86 bytes

```
function(l,n)lapply(partitions::listParts(n),function(x)if(all(lengths(x)==l))show(x))

```

Try it online at RDRR!

Assumes that `l` is sorted in decreasing order. Will print a lot of fluff after the answer, so I advise to call `invisible(f(l, n))` rather than `f(l, n)`.

The function `listParts` lists all the partitions of `1:n`; they are then filtered to keep only those whose lengths match the values of `l`.

Previous submissions, all in R (not that R is a competitive language!):

1. 38 bytes
2. 73 bytes (also SPL, 398 bytes)
3. 111 bytes
4. 68 bytes

**Total: 376 bytes**

# Answer
> 1 votes
# Pyth, 20 bytes

```
{SMfqQlMTSMMs./M.pUs

```

Try it online!

### Explanation

```
{SMfqQlMTSMMs./M.pUsQ # full program (Q=input, last one is implicit)
                  UsQ # range(sum(Q))
                .p    # get all permutations
            s./M      # for each permutation, get all partitions, concatenate to one list
         SMM          # sort each list in each partition
   f                  # keep only the partitions T where
    qQ                # Q ==
      lMT             #      map each list in a partition T to its length
 SM                   # now sort the filtered partitions
{                     # and deduplicate

```

---
Tags: code-golf, combinatorics, set-partitions
---


title: Circle intersection area

text:
# Question
Title: Circle intersection area
# Description :

Given `x` and `y` positions of two circles along with their `radii`, output the area of intersection of the two circle.

---

# Input :

You will be given following input :

```
array 1 = x and y positions of circle a
array 2 = x and y positions of circle b
radius  = radii of the two congruent circles

```

## Input method :

```
([12 , 20] , [20 , 18] , 12)     ---> two array and number
([12 , 20 , 20 , 18] , 12)       ---> array and a number
(12 , 20 , 20 , 18 , 12)         ---> all five numbers
('12 20' , '20 18' , 12)         ---> 2 strings and a number
('12 20 20 18' , 12)             ---> string and a number
('12 20 20 18 12')               ---> one string

```

---

# Output :

* A non-negative integer (no decimal) equal to area of intersection of two circles.
* A string equal to the above mentioned integer.

### Note :

* Output must be \>= 0, since area can't be negative.
* In case of decimal round down to nearest integer

---

# Examples :

```
([0, 0], [7, 0], 5)                   ---> 14

([0, 0], [0, 10], 10)                 ---> 122

([5, 6], [5, 6], 3)                   ---> 28

([-5, 0], [5, 0], 3)                  ---> 0

([10, 20], [-5, -15], 20)             ---> 15

([-7, 13], [-25, -5], 17)             ---> 132

([-12, 20], [43, -49], 23)            ---> 0

```

---

# Winning criteria :

This is so shortest code in bytes for each language wins.

---

# Suggestions :

* Provide a TIO link so it can be tested.
* Provide an explanation so others can understand your code

These are only suggestions and are not mandatory.

# Answer
> 5 votes
# JavaScript (ES6), 72 bytes

*Alternate formula suggested by @ceilingcat*

Takes input as 5 distinct parameters **(x0, y0, x1, y1, r)**.

```
with(Math)f=(x,y,X,Y,r)=>-(sin(d=2*acos(hypot(x-X,y-Y)/r/2))-d)*r*r*2>>1

```

Try it online!

---

# JavaScript (ES7), ~~81~~ ~~80~~ 77 bytes

*Saved 3 bytes thanks to @Neil*

Takes input as 5 distinct parameters **(x0, y0, x1, y1, r)**.

```
(x,y,X,Y,r,d=Math.hypot(x-X,y-Y))=>(r*=2)*r*Math.acos(d/r)-d*(r*r-d*d)**.5>>1

```

Try it online!

### How?

This is based on a generic formula from MathWorld for non-congruent circles:

```
A = r².arccos((d² + r² - R²) / 2dr) +
    R².arccos((d² + R² - r²) / 2dR) -
    sqrt((-d + r + R)(d + r - R)(d -r + R)(d + r + R)) / 2

```

where **d** is the distance between the two centers and **r** and **R** are the radii.

With **R = r**, this is simplified to:

```
A = 2r².arccos(d / 2r) + d.sqrt((2r - d) * (2r + d)) / 2

```

And with **r' = 2r**:

```
A = (r'².arccos(d / r') + d.sqrt(r'² - d²)) / 2

```

*Note*: If **d** is greater than **2r**, `Math.acos()` will return `NaN`, which is coerced to **0** when the right-shift is applied. This is the expected result, because **d \> 2r** means that there's no intersection at all.

# Answer
> 3 votes
# Mathematica ~~66 57~~ 51 bytes

```
Floor@Area@RegionIntersection[#~Disk~#3,#2~Disk~#3]&

```

A `Disk[{x,y},r]`refers to the region circumscribed by the circle centered at `{x,y}` with a radius of `r`.

`RegionIntersection[a,b]` returns the intersection of regions `a`, `b`. `Area` takes the area. `IntegerPart` rounds down to the nearest integer.

# Answer
> 3 votes
# Jelly,  ~~27 25 24~~  22 bytes

```
×,²I½
÷ÆA×²}_çHḞ
ạ/çḤ}

```

A full program accepting a list of the two centres as complex co-ordinates and the radius which prints the result (as a dyadic link it returns a list of length 1).

**Try it online!**

To take the two co-ordinates as pairs add `Uḅı` to the main link, like this.

### How?

```
×,²I½ - Link 1, get [√(s²d² - s⁴)]: separation of centres, s; diameter, d
 ,    - pair = [s, d]
×     - multiply (vectorises) = [s², sd]
  ²   - square (vectorises) = [s⁴, s²d²]
   I  - incremental differences = [s²d² - s⁴]
    ½ - square root (vectorises) = [√(s²d² - s⁴)]

÷ÆA×²}_çHḞ - Link 2, get intersection area: separation of centres, s; diameter, d
÷          - divide = s/d
 ÆA        - arccos = acos(s/d)
    ²}     - square right = d²
   ×       - multiply = acos(s/d)d²
       ç   - call last Link (1) as a dyad (f(s,d)) = [√(s²d² - s⁴)]
      _    - subtract (vectorises) = [acos(s/d)d² - √(s²d² - s⁴)]
        H  - halve (vectorises) = [(acos(s/d)d² - √(s²d² - s⁴))/2]
         Ḟ - floor = [⌊(acos(s/d)d² - √(s²d² - s⁴))/2⌋]
           -  ...Note: Jelly's Ḟ takes the real part of a complex input so when
           -           the circles are non-overlapping the result is 0 as required

ạ/çḤ} - Main link: centres, a pair of complex numbers, c; radius, r
 /    - reduce c by:
ạ     -   absolute difference = separation of centres, s
      -   ...Note: Jelly's ạ finds the Euclidean distance when inputs are complex
      -            i.e. the norm of the difference
   Ḥ} - double right = 2r = diameter, d
  ç   - call last Link (2) as a dyad (f(s,d))
      - implicit print

```

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

```
Floor@Area@RegionIntersection[#~Disk~#3,Disk@##2]&

```

Try it online!

# Answer
> 2 votes
# C (gcc), ~~83 79 71~~ 66 bytes

```
f(a,b,c,d,e){float g=cacos(hypot(a-c,b-d)/e/2)*2;e*=(g-sin(g))*e;}

```

Try it online!

# Answer
> 2 votes
# Python 3, 106 chars with centers given as lists

```
from numpy import*
def f(a,b,r):d=min(1,hypot(*subtract(b,a))/2/r);return(arccos(d)-d*(1-d*d)**.5)*r*r//.5

```

# 100 chars with center coords separately

```
from math import*
def f(a,b,A,B,r):d=min(1,hypot(A-a,B-b)/2/r);return(acos(d)-d*(1-d*d)**.5)*r*r//.5

```

# Answer
> 1 votes
# Haskell, 83 bytes

```
(k!l)m n r|d<-sqrt$(k-m)^2+(l-n)^2=floor$2*r^2*acos(d/2/r)-d/2*sqrt(4*r*r-d*d)::Int

```

Just the formula, really. Type has to be declared as `Int` for NaN to map to 0 with `floor`.

Try it online!

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

```
with(Math)f=(a,b,c,d,r)=>(-sin(x=2*acos(hypot(a-c,b-d)/2/r))+x)*r*r|0

```

Try it online!

Short not sure if it can be golfed any further. Any suggestions are welcome

# Answer
> 0 votes
# Perl 6, 56 bytes

```
{{1>$_&&{$_-.sin}(2*.acos)}(abs($^p-$^q)/2/$^r)*$r²+|0}

```

Try it online!

Takes circle coordinates as complex numbers.

# Answer
> 0 votes
# Excel, 119 bytes

```
=INT(IFERROR(2*E1^2*ACOS(((C1-A1)^2+(D1-B1)^2)^.5/2/E1)-((4*E1^2-((C1-A1)^2+(D1-B1)^2))*((C1-A1)^2+(D1-B1)^2))^.5/2,0))

```

Input taken as 5 separate variables:

```
x-coordinate    y-coordinate    x-coordinate    y-coordinate    radius
     A1              B1             C1                D1          E1

```

# Answer
> 0 votes
# Python 2, 109 bytes

```
from math import*
a,b,x,y,r=input()
d,R=hypot(x-a,y-b),2*r
print int(d<R and R*r*acos(d/R)-d*sqrt(R*R-d*d)/2)

```

Try it online!

Pretty straightforward. Get the distance between circles, and use `R=2r` as a substituite in the equation. `d<R and` to short-circuit if circles don't overlap.

# Answer
> 0 votes
# Pyth, 63 bytes

```
J@+^-hhQh@Q1 2^-ehQe@Q1 2 2K*2eQs&<JK-**KeQ.tcJK4c*J@-*KK*JJ2 2

```

**Test suite**

Takes input as a triple consisting of two doubles and a number.

# Answer
> 0 votes
# T-SQL, 122 bytes

```
SELECT FLOOR(Geometry::Parse('POINT'+a).STBuffer(r).STIntersection(
             Geometry::Parse('POINT'+b).STBuffer(r)).STArea())FROM t

```

(line break for readability only).

Uses MS SQL's support of spatial geometry.

Per our IO standards, SQL can take input from a pre-existing table **t** with `int` field **r** and `varchar` fields **a** and **b** containing coordinates in the format `(x y)`.

My statement parses the coordinates as `POINT` geometry objects expanded by the radius using the function `STBuffer()`, then taking the `STIntersection()` followed by the `STArea()`.

If I am allowed to input the *actual* geometry objects in the table instead, then my code becomes almost trivial (48 bytes):

```
SELECT FLOOR(a.STIntersection(b).STArea())FROM t

```

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


title: An unknowably odd function

text:
# Question
Title: An unknowably odd function
This challenge initially appeared in this challenge as a an extra brain teaser. I am posting it with permission from the original author so that we can have a formal competition.

---

Your task here will be to implement a function1 that forms a permutation on the positive integers. This means that each positive integer should be the output of calling the function with exactly one positive integer.

In the earlier challenge we calculated the odd probability for such sequences. We defined it as so:

If we have a function \\$f\\$ the probability of a number being odd will be defined as the limit of ratio odd members of the set to the size of the set \\$f\\{1\dots n\\}\\$ as \\$n\\$ tends towards infinity.

$$\lim\_{n\rightarrow \infty}\dfrac{\left|\\{x : x \in \\{1\dots n\\}, \mathrm{odd}(f(x))\\}\right|}{n}$$

Your task is to write a function with no defined odd probability. That is a function \\$f\\$ for which the above limit does not converge.

---

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

---

1: Here function will mean program or function. It is just a piece of code that takes input and produces output.

# Answer
> 13 votes
# JavaScript (ES7),  ~~33~~  29 bytes

This is A307485: one odd, two even, four odd, eight even, etc.

```
n=>n-~n-(4<<Math.log2(n))/3|0

```

Try it online!

For \\$n\in\mathbb{N}^\*\\$, this is equivalent to:

$$a(n)=2n+1-\left\lceil\frac{2^{\lfloor log\_2 n\rfloor+2}}{3}\right\rceil$$

It produces the sequence:

```
1
2 4
3 5 7 9
6 8 10 12 14 16 18 20
...

```

The ratio of odd values is 'bouncing' ad infinitum between \\$1/3\\$ and \\$2/3\\$, more and more slowly:

# Answer
> 9 votes
# sed -E, ~~20~~ 17 bytes

```
s/\B(.)(.*)/\2\1/

```

Try it online!

*Saved 3 bytes as per user41805's suggestion.*

This takes the input number and moves the 2nd digit (from the left) to the end of the number (the one's place).

The numbers from 1 to 10*n* are just rearranged, so the proportion of odd numbers for inputs up to 10*n* is 0.5.

All the numbers from 10*n*+1 to 10*n*+10*n*-1-1 map to even numbers, so the proportion of odd numbers for inputs up to 10*n*+10*n*-1 is $$\frac{10^n/2+1}{10^n+10^{n-1}}=\frac{5+10^{-(n-1)}}{11},$$ which approaches 5/11 as *n* approaches infinity.

# Answer
> 8 votes
# MATL, ~~18~~ ~~17~~ 16 bytes

```
:"vtn@W:2e+!h]G)

```

**Try it online!**

This produces the following permutation of the positive integers:

```
1 2 3 5 4 6 7 9 11 13 8 10 12 14 15 17 19 21 23 25 27 29 16 18 20 22 24 26 28 30 ...

```

The pattern is easier to see if the sequence is arranged as follows (read top to down, then left to right):

```
1
2
3   5
4   6
7   9 11 13
8  10 12 14
15 17 19 21 23 25 27 29
16 18 20 22 24 26 28 30
...

```

It's clear that the cumulative proportion of odd values has limit superior `2/3` and limit inferior `1/2`. Or see the proportion graphically at **MATL Online!**

### Explanation

The code produces a longer sequence than needed (with length exponential in the input number), and then outputs the term specified by the input.

```
:       % Implicit input, n. Push range [1 2 ... n]
"       % For each k in [1 2 ... n]
  v     %   Concatenate stack vertically. This is only useful in the first
        %   iteration, to produce the empty array [], which will later be
        %   extended with terms of the sequence
  tn    %   Duplicate sequence so far. Push its number of elements, say m
  @W:   %   Push range [1 2 3 ... 2^k]
  2e    %   Arrange as a two-row matrix in column-major order. Gives
        %   [1 3 5 ... 2^k-1;
        %    2 4 6 ... 2^k]
  +     %   Add, element-wise. Gives
        %   [m+1 m+3 m+5 ... m+2^k-1;
        %    m+2 m+4 m+6 ... m+2^k]
  !h    %   Transpose, then concatenate into a row vector. This extends the
        %   sequence. The transpose is needed so that, when concatenating,
        %   the terms are included in the correct order
]       % End
G)      % Take the n-th entry. Implicit display

```

# Answer
> 6 votes
# APL (Dyalog Extended), ~~8~~ 4 bytes

```
⌽1⌽⍞

```

Try it online!

Based on xnor's idea to keep the first digit and reverse the rest. A full program that takes the input from STDIN as a string, rotates left once (`1⌽`), reverses (), and prints to STDOUT.

---

# APL (Dyalog Extended), 8 bytes

```
⊥1,1⌽1↓⊤

```

Try it online!

Generates a sequence that is very similar to Luis Mendo's MATL answer:

```
1
2
3
4 6
5 7
8 10 12 14
9 11 13 15
16 18 20 22 24 26 28 30
17 19 21 23 25 27 29 31
...

```

### How it works

```
⊥1,1⌽1↓⊤
       ⊤  ⍝ Convert to binary digits
     1↓   ⍝ Remove the leading 1
   1⌽     ⍝ Rotate left once; move 2nd bit to last
 1,       ⍝ Add back the leading 1
⊥         ⍝ Convert binary digits to integer

```

# Answer
> 3 votes
# Haskell, 18 bytes

```
f(h:t)=h:reverse t

```

Try it online!

Based on Mitchell Spector's idea. Leaves the first digit in place and reverses the rest. Input and output are as strings.

# Answer
> 3 votes
# Retina, ~~6~~ 5 bytes

```
,V1,`

```

Try it online! Link includes test cases shamelessly stolen from @xnor. Uses the same suffix reversal algorithm inspired by @MitchellSpector's `sed` answer. Edit: Saved 1 byte thanks to @FryAmTheEggman. Explanation:

```
V`

```

Reverse the matched characters (defaults to matching each line).

```
,

```

Reverse all matches

```
1,

```

Exclude the first character of each match from being reversed. (`^0` also works.)

# Answer
> 2 votes
# Python, 22 bytes

```
lambda s:s[0]+s[:0:-1]

```

Try it online!

Based on Mitchell Spector's idea. Leaves the first digit in place and reverses the rest. Input and output are as strings.

# Answer
> 1 votes
# Pure Bash, 27 bytes

```
echo ${1:0:1}${1:2}${1:1:1}

```

Try it online!

This uses the same method as my sed answer.

# Answer
> 1 votes
# Retina, ~~18~~ 17 bytes

```
(.)(.)(.*)
$1$3$2

```

Try it online!

This is a port of my sed answer (moving the second digit to the far right). I've never programmed in Retina before, so I took a quick look at the language documentation and put this together. I assume that it can be made much shorter using more advanced features of Retina.

Also, if there's any error in the Retina code, please let me know. It does appear to work :) .

# Answer
> 0 votes
# Charcoal, 7 bytes

```
§θ⁰⮌✂θ¹

```

Try it online! Link is to verbose version of code. This is the Charcoal port of the 6-byte Retina 1 answer that I alluded to in my comments to @MitchellSpector's `sed` answer, and then presumably independently discovered by @xnor. I/O as strings (which Charcoal defaults to anyway). Explanation:

```
§θ⁰

```

Print the first character of the input number.

```
⮌✂θ¹

```

Print the remaining characters of the input number, but reversed.

---
Tags: code-golf, sequence, open-ended-function
---


title: Is this a Boggle pad?

text:
# Question
Title: Is this a Boggle pad?
Given a list of case-insensitive ASCII letter strings ("words"), output whether the entire list can be found on some four-by-four configuration ("board") of letter squares, in which no square can be used more than once in a word, and in which words are formed by moving from any square to any adjacent square including diagonally.

You do not need to worry that the combination of squares that would allow for the list actually appears in a Boggle game. The words need not be actual words in any language. You should assume that if Q appears on the board, it's on a square of its own (unlike in actual Boggle).

Standard loopholes are banned, standard I/O rules apply, and you're golfing.

---

In the examples below, a slash signifies a newline.

## Truthy examples

* auuuuooiiaaoiee, euiaaiueeuua, ooouuueee, eueueuoaoa — All are on the board auii/euoa/ueoa/euio
* swiop, byteba, ceropl, qoiz, aeis, lqoep — All are on the board abcb/rety/poiw/lqzs

## Falsy examples

* swiop, byteba, ceropl, qoiz, aeis, lqoep, wybez — There are fifteen distinct letters (*abceilopqrstwyz*) and a single word has two *b*s, so that's the sixteenth square. Thus there's only one *e*. But the *e* has nine distinct letters (*abcioprtz*) adjacent to it, which is impossible.
* hskcbnzvgfa, lajdnzvfhgs, kajfbmxvshd, ldgckvbsanx — There are sixteen distinct letters (*abcdfghjklmnsvxz*). Of those, *s* is adjacent to all of *abghkv*, *v* is adjacent to all of *bfgksxz*, *b* is adjacent to all of *cfmnsv*, *a* is adjacent to all of *fjklns*, and *f* is adjacent to all of *abghjv*. But on an actual board only four squares are adjacent to more than five squares apiece.

# Answer
# Python 3, 215 bytes

```
def f(w):b=product(*[set("".join(w))]*16);return any(all(any(all(x-y in[1,-1,4,-4]for x,y in zip(q,q[1:]))for q in product(*[[x for x in range(16)if k[x]==c]for c in a]))for a in w)for k in b)
from itertools import*

```

Try it online!

This is never going to finish, so I can't really debug it or prove it works. I will try to find constant optimizations / test with reduced test cases, but if you spot a reason it would definitely fail, I will take it down / fix it.
> 1 votes

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


# Question
Title: How many balloons do I need in each corner?
You have a square board with a bunch of items laid out on it in one of a \\$3 \times 3\\$ grid of cells and you want to lift it up using balloons, but you can only attach balloons to the corners of the board. Your task is to determine the minimum number of balloons in each corner to make sure the board won't tip over in flight, but can still lift all its contents.

## "Physics" Model

* Each balloon can lift 0.25kg (these are very strong balloons)
* The board itself weighs 1kg, so you would need 1 balloon in each corner to lift an empty board
* Items in each corner cell only exert force on their respective corners (i.e. 4 balloons are needed in the corresponding corner per kg)
* Items on each edge cell split their force evenly between their neighboring corners (i.e. 2 balloons on each of the two corresponding corners per kg)
* Items in the center cell split their force evenly across all corners (i.e. 1 balloon is needed in each corner per kg)

## Example Test Cases

### 1

```
Input:
0 0 0
0 0 0
0 0 0

Output:
1 1
1 1

```

### 2

```
Input:
1 2 1
2 4 2
1 2 1

Output:
17 17
17 17

```

### 3

```
Input:
5 0 0
0 0 2
0 1 0

Output:
21 5
 3 7

```

### 4

```
Input:
12  9 35
 1 32  2
 4  6 18

Output:
101 195
 63 121

```

### 5

```
Input:
9999 9999 9999
9999 9999 9999
9999 9999 9999

Output:
89992 89992
89992 89992

```

### 6

```
Input:
9999    2 9001
   0 9999 9999
9999  999 9999

Output:
50000 66006
51994 71992

```

## Rules and Assumptions

* You may assume each cell is filled with a whole number between \\$0\\$ and \\$9999\\$ kg weight worth of items
* Use any convenient format for I/O
* Shortest code wins!

# Answer
> 9 votes
# Jelly, 14 bytes

```
3Ḷ×þ`ZU$Ƭ×µ§§‘

```

Try it online!

Takes input as a 3x3 matrix and outputs a list going clockwise starting from the bottom-right.

# Explanation

```
3Ḷ×þ`ZU$Ƭ×µ§§‘     Main Link
3Ḷ                 [0, 1, 2]
  ×þ`              outer product by multiplication with itself ([0, 0, 0], [0, 1, 2], [0, 2, 4])
        Ƭ          (include the original, plus) rotate clockwise until results are no longer unique (4 results total)
     ZU$           zip and upend (clockwise rotation)
         ×         vectorized multiply with original (gets the workload distributions to each balloon)
           §§      sum results for each balloon (vectorized-sum rows in the matrix; sum the results)
              ‘    increment

```

# Answer
> 8 votes
# Python 2, ~~58~~ ~~57~~ 56 bytes

```
lambda c,*b:[b[~i]*4-~c+b[i]*2+b[i-2]*2for i in 0,2,4,6]

```

Try it online!

**Input**: 9 numbers, representing the board in the following orders:

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

```

**Output**: list of length 4, representing the balloons as follow:

```
1 0
2 3

```

## Explanation

`lambda c,*b:` separates the 9 numbers into the center `c` and a list of length 8 representing the corner and edge values:

```
5 0 7
2 _ 6
3 4 1

```

The reason for this is because length 8 works nicely with negative index, as shown as follow:

```
                Indices    |  Indices mod 8
Edge 1 (i)     0  2  4  6  |  0  2  4  6
Edge 2 (i-2)  -2  0  2  4  |  6  0  2  4
Corner (~i)   -1 -3 -5 -7  |  7  5  3  1

```

*-1 byte thanks to @xnor!*

# Answer
> 5 votes
# 05AB1E, ~~26~~ ~~25~~ ~~17~~ 14 bytes

```
2ÝÂ‚Dδδ*€€*OO>

```

-8 bytes by porting *@HyperNeutrino*'s Jelly answer, so make sure to upvote him!!
-3 bytes thanks to *@Grimmy*.

I/O are both integer-matrices. The output-matrix is mirrored diagonally (i.e. if the input-matrix would be `[[a,b,c],[d,e,f],[g,h,i]]` the output-matrix would result in `[[I,G],[C,A]]`).

Try it online or verify all test cases.

**Explanation:**

```
2Ý       # Push list [0,1,2]
  Â      # Bifurcate it (short for Duplicate & Reverse copy)
   ‚     # Pair those two together: [[0,1,2],[2,1,0]]
    D    # Duplicate it
     δ   # Apply double-vectorized:
      δ  #  Inner apply double-vectorized:
       * #   Multiply:
         #    [[[[0,0,0],[0,1,2],[0,2,4]],
         #      [[0,0,0],[2,1,0],[4,2,0]]],
         #     [[[0,2,4],[0,1,2],[0,0,0]],
         #      [[4,2,0],[2,1,0],[0,0,0]]]]
€        # Map over each inner pair of matrices:
 €       #  Map over each matrix in this pair:
  *      #   Multiply each by the (implicit) input-matrix at the same indices
O        # Sum each row of the inner-most matrices
 O       # Sum those row-sums together as well
  >      # And increase each by 1 for the board itself
         # (after which the result is output implicitly)

```

# Answer
> 5 votes
# , ~~76~~ ~~64~~ 50 bytes

-12 bytes thanks to Giuseppe!

-8 bytes with outer product `%*%`

-6 bytes by changing the order of the output

```
scan()%*%matrix(c(y<-2:0%o%c(2:0,0:2),rev(y)),9)+1

```

Try it online!

Takes input as 9 integers, top to bottom and left to right. Output is in order (NW, SW, NE, SE).

Performs the matrix multiplication of the input vector with the matrix

```
4   0   0   0
2   0   2   0
0   0   4   0
2   2   0   0
1   1   1   1
0   0   2   2
0   4   0   0
0   2   0   2
0   0   0   4

```

which is constructed by inputting the values of the first two columns, and then combining with those columns in reverse.

# Answer
> 5 votes
# Python 3, <sup>~~86~~ ~~78~~</sup> 77 bytes

Saved 8 bytes thanks to xnor!!!
Saved a byte thanks to S.S. Anne!!!

```
lambda b:[[4*b[i][j]+2*b[1][j]+2*b[i][1]-~b[1][1]for j in(0,2)]for i in(0,2)]

```

Try it online!

Uses a list of lists for both input (\\$3\times3\\$) and output (\\$2\times2\\$).

# Answer
> 5 votes
# Python 2, ~~69~~ ~~63~~ ~~59~~ ~~58~~ 57 bytes

```
lambda l:[2*(2*l[i]+l[i%2]+l[i/2])-~l[8]for i in 4,5,6,7]

```

Try it online!

The input is in this order:

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

```

and output is

```
0 2
1 3

```

-1 thanks to @SurculoseSputum

I kept this solution because I started thinking about shuffling indices with it:

### Python 3.8 (pre-release), ~~82~~ ~~81~~ 80 bytes

```
def f(l):*l,d=l;return[(l:=l[2:]+l[:2])and-~d+2*(l[1]+l[7]+2*l[0])for _ in'0'*4]

```

Try it online!

Thanks HyperNeutrino, SSAnne and Surculose Sputum for -1 each!

# Answer
> 3 votes
# JavaScript (ES6),  ~~63~~  57 bytes

Takes input as a flat array of 9 integers. Outputs a flat array of 4 integers.

```
a=>[0,2,6,8].map(i=>a[i]*4+2*(a[3+i%6]+a[i>2?7:1])-~a[4])

```

Try it online!

### How?

Below is the matrix of the item indices:

$$\pmatrix{ 0&\color{red}1&2\\ \color{blue}3&4&\color{blue}5\\ 6&\color{red}7&8}$$

We iterate on the indices of the corners \\$i\in\\{0,2,6,8\\}\\$.

The index of the left or right edge (\\$\color{blue}3\\$ or \\$\color{blue}5\\$) is given by:

$$H\_i=3+(i\bmod6)$$

The index of the top or bottom edge (\\$\color{red}1\\$ or \\$\color{red}7\\$) is given by:

$$V\_i=\cases{ 1&\text{if $i\le2$}\\ 7&\text{if $i\>2$} }$$

# Answer
> 3 votes
# , 47 bytes

```
x=scan();4*x[1:4]+2*x[5:8]+2*x[c(6:8,5)]+x[9]+1

```

Try it online!

Input is a vector in the order

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

```

And output

```
1 2
4 3

```

# Answer
> 2 votes
# Charcoal, 27 bytes

```
Ｆ⁴«≔Ｅ³Ｅ⮌θ§μκθ⟦Ｉ⊕ΣＥθ×λΣＥκ×νμ

```

Try it online! Link is to verbose version of code. Outputs the four corners in order top right, top left, bottom left, bottom right as compared to the test case format. Explanation:

```
Ｆ⁴«

```

Process each corner in turn.

```
≔Ｅ³Ｅ⮌θ§μκθ

```

Rotate the board.

```
⟦Ｉ⊕ΣＥθ×λΣＥκ×νμ

```

Multiply each row and column by its coordinate, then sum the results, and increment the final total.

# Answer
> 2 votes
# Python 3, ~~90~~ 86 bytes

```
lambda a,b,c,d,e,f,g,h,i:(4*a+2*b+2*d-~e,2*b+2*f+4*c-~e,2*d+4*g+2*h-~e,2*f+2*h+4*i-~e)

```

Try it online!

Thanks @xnor for the -4.

# Answer
> 2 votes
# APL (Dyalog Extended), 16 bytes

```
1+{⍉⊥2↑⍉↑⍵⍮⌽⍵}⍣2

```

Try it online!

An anonymous function that takes a 3x3 matrix and returns a 2x2 matrix.

### How it works

```
1+{⍉⊥2↑⍉↑⍵⍮⌽⍵}⍣2  ⍝ Input: 3x3 matrix of numbers
  {     ↑⍵⍮⌽⍵}    ⍝ Join the input with its horizontal reverse,
                  ⍝ adding a leading length-2 axis
   ⍉   ⍉          ⍝ For each row (last axis),
     2↑           ⍝ Take the first two numbers x, y and
    ⊥             ⍝ Apply base-2, i.e. evaluate (2×x)+y
                  ⍝ (equivalent to dot product with [2 1 0])
              ⍣2  ⍝ Repeat the above twice
1+                ⍝ Increment element-wise

```

# Answer
> 2 votes
# Excel (as CSV), 92 bytes

```
,,,=1+A1*4+(B1+A2)*2+B2,=1+C1*4+(B1+C2)*2+B2
,,,=1+A3*4+(B3+A2)*2+B2,=1+C3*4+(B3+C2)*2+B2
,,

```

To use: Input between `,`'s, save as CSV, open in Excel.

Eg:

```
12,9,35,=1+A1*4+(B1+A2)*2+B2,=1+C1*4+(B1+C2)*2+B2
1,32,2,=1+A3*4+(B3+A2)*2+B2,=1+C3*4+(B3+C2)*2+B2
4,6,18

```

# Answer
> 2 votes
# GolfScript, 73 bytes

```
:a;0{..2/2*:x;2%2*:y;).2%!a...x=y=4*\x=1=2*+\1=y=2*+\1=1=+)`" "+\n*+\}4*;

```

Just here to submit something. Cool question! stack-based languages are NOT the solution. Fuck this shit, lmfao.

Could probably golf with better modulo shit, but I've stopped caring lol

Try the really "golf-inputted" one, awkward for input

Same program, weird header and footer to format OP's input into the one above, easier to use and test. Plus, look at that identically-formatted output. Gorgeous, ainnit?

# Answer
> 1 votes
# Perl 5 `-MList::Util=sum -MPOSIX -a`, 76 bytes

```
map$_*=++$i==5||$i%2*2+2,@F;map{say ceil.25+sum@F[$_,$_+1,$_+3,$_+4]}0,1,3,4

```

Try it online!

### Input:

If the grid is denoted as:

```
a b c
d e f
g h i

```

Then the input is space separated:

```
a b c d e f g h i

```

### Output:

Output is line separated:

```
balloons attached at a
balloons attached at c
balloons attached at g
balloons attached at i

```

# Answer
> 1 votes
# Haskell, ~~67~~ 66 bytes

```
f a b c d e f g h i=[2*v+e+1|v<-[2*a+b+d,b+2*c+f,d+2*g+h,f+h+2*i]]

```

Try it online!

Inspired by my Python answer.

# Answer
> 1 votes
# Jelly, ~~21~~ 19 bytes

```
3,1p`ạ€3Rp`¤P€€×³§‘

```

Try it online!

# How?

Notice that we can create the weight matrices for each corner by finding the absolute difference to the opposite corners.

For example, for the first balloon, the weight matrix is

```
4 2 0
2 1 0
0 0 0

```

This can be found by, for each coordinate, find the absolute difference to the corner (3, 3), and product. For example, (1, 1) has an absolute difference (2, 2) and product 4.

```
3,1p`ạ€3Rp`¤P€€×³§‘    Main link
3,1                      Get 3,1 pair
   p`                    cartesian product with itself, gives the 3 corner coordinates
       3Rp`¤             Get all the coordinates
     ạ€                  get the absolute differences for each corner coordinate
            P€€          product each subsublist
               ×³        vectorize multiply with the input
                 §‘      sum each sublist and increment

```

# Answer
> 1 votes
# Jelly, 14 bytes

```
ŒJḂ§2*ṁ×⁸+Ɲ⁺€‘

```

A monadic Link accepting a list of lists of integers which yields a list of list of integers:
`[[top-left, top-right], [bottom-left, bottom-right]]`

**Try it online!**

### How?

```
ŒJḂ§2*ṁ×⁸+Ɲ⁺€‘ - Link: list of lists of integers, T    e.g. [[ 3, 9, 5],[ 1, 3, 2],[ 4, 6, 1]]
ŒJ             - multidimensional indices (T)               [[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]]
  Ḃ            - least significant bit (vectorises)         [[1,1],[1,0],[1,1],[0,1],[0,0],[0,1],[1,1],[1,0],[1,1]]
   §           - sums                                       [2,1,2,1,0,1,2,1,2]
    2          - literal two                                2
     *         - exponentiate                               [4,2,4,2,1,2,4,2,4]
      ṁ        - mould like (T)                             [[ 4, 2, 4],[ 2, 1, 2],[ 4, 2, 4]]
        ⁸      - chain's left argument, T                   [[ 3, 9, 5],[ 1, 3, 2],[ 4, 6, 1]]
       ×       - multiply (vectorises)                      [[12,18,20],[ 2, 3, 4],[16,12, 4]]
          Ɲ    - for neighbours:
         +     -   add (vectorises)                         [[14,21,24],[18,15, 8]]
            €  - for each:
           ⁺   -   repeat last link                         [[35,45],[33,23]]
               - (...i.e +Ɲ for each)
             ‘ - increment (vectorises)                     [[36,46],[34,24]]

```

# Answer
> 0 votes
# brainfuck, 138 bytes

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

```

Try it online!, just for the byte count.

Try it here, by pasting this input: `\12\9\35\1\32\2\4\6\18` and hitting the "view memory" button to compare it with the expected output `101 195 063 121`.

# Answer
> 0 votes
# Pyth, 24 bytes

```
mh+eQ+ys<.<ecPQ4d2yy@Qd4

```

Try it online!

I/O format: List `[0, 1, 2, 3, 4, 5, 6, 7, 8]` (input) and `[0, 1, 2, 3]` (output) with positions

```
Input: 0 5 1     Output: 0 1
 = Q   4 8 6             3 2
       3 7 2

```

### Explanation

```
m                      4   # map [0, 1, 2, 3] to (current number = d)
 h                         # 1 +
  +eQ                      # Q[-1] + 1 +
      ys                   #   2 * sum of
           ec  4           #     chop       into pieces of length 4, take last element
             PQ            #          Q[:-1]                 -> [4,5,6,7]
         .<     d          #     rotate left by d
        <        2         #     first two elements -> [4,5], [5,6], [6,7] or [7,4]
     +                     # +
                  yy       #   4 *
                    @Qd    #       Q[d]

```

# Answer
> 0 votes
# PHP, 101 bytes

A rather inelegant solution. Just multiples corners by 4, sides by 2 and adds 1 to the center than adds up each corner. Some form of matrix multiplication may be possible with `array_map()`.

```
parse_str($argv[1]);$e++;echo$a*4+$b*2+$d*2+$e,$c*4+$b*2+$f*2+$e,$g*4+$d*2+$h*2+$e,$i*4+$f*2+$h*2+$e;

```

Try it online!

It takes input as a string in a html query format e.g. `a=9999&b=3&c=9001&d=0&e=9998&f=9999&g=9999&h=999&i=9999`

+7 bytes if the output can't be an unseparated list, by making it into an array and using `print_r()`

# PHP, 108 bytes

```
parse_str($argv[1]);$e++;print_r([$a*4+$b*2+$d*2+$e,$c*4+$b*2+$f*2+$e,$g*4+$d*2+$h*2+$e,$i*4+$f*2+$h*2+$e]);

```

Try it online!

---
Tags: code-golf, grid
---