title: Three triangular numbers

text:
# Question
Title: Three triangular numbers
### Description

There have been quite a few other challenges concerning these numbers before, and I hope this one is not among them.

The *n* th triangular number equals the sum of all natural numbers up to *n*, simple stuff. There are a wikipedia page and an entry at OEIS, for those who wish to inform themselves further.

Now, Gauss found out that every natural number may be expressed as a sum of three triangular numbers (these include `0`), and it is fine to have one number more than once, e.g. `0 + 1 + 1 = 2`.

### Challenge

Your task is to write a program or function, given a natural number (including `0`), prints three triangular numbers that sum up to the argument. You may print the numbers separeted by spaces, as an array, or by another method you like. However, it is **forbidden** to use any builtin functions to directly get an array, a range or any other form of collection containing a list of triangular numbers (for instance a single atom that yields the range).

### Test cases

```
9 -> 6 + 3 + 0 or 3 + 3 + 3
12 -> 6 + 6 + 0 or 6 + 3 + 3 or 10 + 1 + 1
13 -> 6 + 6 + 1
1 -> 1 + 0 + 0
0 -> 0 + 0 + 0

```

Note: If there is more than one possible combination, you may print any or all, but you must print any combination only once, eliminating all combinations that are a result of rearranging other combinations. I'd really appreciate a try-it link and an explanation, I really love to see how you solve the problem ;)

This is , so standard loopholes apply. May the shortest answer in bytes win!

# Answer
# 05AB1E, 10 bytes

Code:

```
ÝηO3ãʒOQ}¬

```

Explanation:

```
Ý             # Compute the range [0 .. input]
 η            # Get the prefixes
  O           # Sum each prefix to get the triangle numbers
   3ã         # Cartesian repeat 3 times
     ʒ  }     # Keep elements that
      OQ      #   have the same sum as the input
         ¬    # Retrieve the first element

```

Uses the **05AB1E** encoding. Try it online!
> 8 votes

# Answer
# Python 2, 99 bytes

```
from random import*
n=input()
while 1:b=sample([a*-~a/2for a in range(n+1)]*3,3);n-sum(b)or exit(b)

```

Try it online!

I'm pretty amazed this is shorter than `itertools` or a triple list comprehension! It (eventually) spits out a random answer every time you run it.

Two 102s:

```
n=input();r=[a*-~a/2for a in range(n+1)];print[(a,b,c)for a in r for b in r for c in r if a+b+c==n][0]
def f(n):r=[a*-~a/2for a in range(n+1)];return[(a,b,c)for a in r for b in r for c in r if a+b+c==n][0]

```

itertools looks to be 106:

```
from itertools import*;lambda n:[x for x in product([a*-~a/2for a in range(n+1)],repeat=3)if sum(x)==n][0]

```
> 7 votes

# Answer
# Jelly, 12 bytes

```
0r+\œċ3S=¥Ðf

```

Try it online!

## How it works

```
0r+\œċ3S=¥Ðf   input: n
0r             [0 1 ... n]
  +\           cumsum
    œċ3        combinations of 3 elements, with repetition
          Ðf   filter on
       S          sum
        =         equals n

```
> 3 votes

# Answer
# Brachylog, 13 bytes

```
⟦⟦ᵐ+ᵐj₃⊇Ṫ.+?∧

```

Try it online!

## How it works

```
⟦⟦ᵐ+ᵐj₃⊇Ṫ.+?∧  input: n
⟦              [0 1 ... n]
 ⟦ᵐ            [[0] [0 1] [0 1 2] ... [0 1 ... n]]
   +ᵐ          [0 1 3 ... n(n+1)/2]
     j₃        [0 1 3 ... n(n+1)/2 0 1 3 ... n(n+1)/2 0 1 3 ... n(n+1)/2]
       ⊇       is a superset of
        Ṫ      a list of three elements
         .     which is the output
          +?   which sums up to be the input

```
> 3 votes

# Answer
# MATL, 18 bytes

```
Q:qYs3Z^t!sG=fX<Y)

```

This outputs the first result in lexicographical order.

Try it at **MATL Online!**

### Explanation

```
Q     % Implicitly input n. Add 1
:     % Range (inclusive, 1-based): gives [1 2 ... n+1]
q     % Subtract 1 (element-wise): gives [0 1 ... n]
Ys    % Cumulative sum
3Z^   % Cartesian power with exponent 3. Gives a matrix where each row is a
      % Cartesian tuple
t     % Duplicate
!s    % Sum of each row
G=    % Does each entry equal the input?
f     % Find indices that satisfy that condition
X<    % Minimum
Y)    % Use as row index into the Cartesian power matrix. Implicitly display

```
> 2 votes

# Answer
# Retina, ~~63~~ 59 bytes

```
.+
$*
^((^1|1\2)*)((1(?(4)\4))*)((1(?(6)\6))*)$
$.1 $.3 $.5

```

Try it online! Link includes test cases. `(1(?(1)\1))*` is a generalised triangular number matcher, but for the first triangular number we can save a few bytes by using `^` for the initial match.
> 2 votes

# Answer
## Haskell, ~~66~~ 59 bytes

Thanks for allowing to output all solutions, that was fascinating distraction! I was so happy to not need to extract one solution and be able to just give them all that I didn't notice the cost that comes from avoiding permuted solutions. @Lynn's remark explained that to me and let me save 7 bytes.

```
f n|l<-scanl(+)0[1..n]=[(a,b,c)|c<-l,b<-l,a<-l,a+b+c==n]!!0

```

This binds more than enough triangular numbers to `l` and checks all combinations.
> 2 votes

# Answer
# Python 3, 119 bytes

```
lambda n:[l for l in combinations_with_replacement([(t**2+t)/2for t in range(n)],3)if sum(l)==n]
from itertools import*

```

Try it online!

**Thanks to @WheatWizard for saving 12 bytes!**
> 1 votes

# Answer
# PHP, 351 bytes

```
$r=[];function f($a=[],$c=0){global$argn,$t,$r;if($c<3){$n=$argn-array_sum($a);$z=array_filter($t,$f=function($v)use($n,$c){return$v>=$n/(3-$c)&&$v<=$n;});foreach($z as$v){$u=array_merge($a,[$v]);if(($w=$n-$v)<1){if(!$w){$u=array_pad($u,3,0);sort($u);if(!in_array($u,$r)){$r[]=$u;}}}else f($u,$c+1);}}}for($t=[0];$argn>$t[]=$e+=++$i;);f();print_r($r);

```

Try it online!
> 1 votes

# Answer
# Mathematica, 63 bytes

```
(t=#;#&@@Select[Table[i(i+1)/2,{i,0,t}]~Tuples~{3},Tr@#==t&])&

```
> 1 votes

# Answer
# C/C++ - 197 bytes

```
#include<stdio.h>
#define f(i,l,u) for(int i=l;i<=u;i++)
int t(int n){return n>1?n+t(n-1):n;}
int c(int n){f(a,0,n)f(b,a,n)f(c,b,n)if(t(a)+t(b)+t(c)==n)return printf("%d %d %d\n",t(a),t(b),t(c));}

```

Blow by blow:

```
#include<stdio.h>

```

Needed for printf. Could be elided for certain versions of C

```
#define f(i,l,u) for(int i=l;i<=u;i++)

```

Space saving for loop.

```
int t(int n){return n>1?n+t(n-1):n;}

```

Recursive triangle evaluator.

```
int c(int n){f(a,0,n)f(b,a,n)f(c,b,n)if(t(a)+t(b)+t(c)==n)return printf("%d %d %d\n",t(a),t(b),t(c));}

```

This guy does the heavy lifting. Three nested for loops iterate a, b, c from 0 to n, note that b and c each iterate from the previous value up to n. It's not strictly necessary to trim iteration like that since the `return` coming in a minute solves the "duplicate" problem.

At the inner level, if the sum of the three triangle numbers `==` the desired value, print the triangles and return.

You can legally remove the `return` keyword and convert the return type of c to void to save a few more bytes and print all possible solutions. It is for this reason that iterations are limited, if all loops ran from `0` to `n` it would cause duplicates.
> 1 votes

# Answer
# CJam, 26 bytes

```
{_),[{\_@+}*]3m*_{:+}%@#=}

```

Port of my MATL answer. This is an anonymous block that expects the input on the stack and replaces it by the output array.

**Try it online!**
> 0 votes

# Answer
# , 66 bytes

```
n=scan();b=expand.grid(rep(list(cumsum(0:n)),3));b[rowSums(b)==n,]

```

Brute force algorithm; reads `n` from stdin and returns a dataframe where each row is a combination of 3 triangular numbers that add up to `n`. If necessary, I can return only the first row for +4 bytes.

Try it online!
> 0 votes

# Answer
# Java 8, 164 bytes

```
n->{int t[]=new int[n+1],i=0,j=0;for(;i<=n;)if(Math.sqrt(8*i+++1)%1==0)t[j++]=i-1;for(int a:t)for(int b:t)for(int c:t)if(a+b+c==n)return new int[]{c,b,a};return t;}

```

**Explanation:**

Try it here.

```
n->{                     // Method with int parameter and int-array return-type
  int t[]=new int[n+1],  //  Create an int-array to store triangular numbers
      i=0,j=0;           //  Two index-integers
  for(;i<=n;)            //  Loop (1) from 0 to `n` (inclusive)
    if(Math.sqrt(8*i+++1)%1==0)
                         //   If `i` is a triangular number
      t[j++]=i-1;        //    Add it to array `t`
                         //  End of for-loop (1) (implicit / single-line body)
  for(int a:t)           //  Loop (2) over the triangular numbers
    for(int b:t)         //   Inner loop (3) over the triangular numbers
      for(int c:t)       //    Inner loop (4) over the triangular numbers
        if(a+b+c==n)     //     If the three triangular numbers sum equal the input
          return new int[]{c,b,a};
                         //      Return these three triangular numbers as int-array
                         //    End of loop (4) (implicit / single-line body)
                         //   End of loop (3) (implicit / single-line body)
                         //  End of loop (2) (implicit / single-line body)
  return t;              //  Return `t` if no sum is found (Java methods always need a
                         //  return-type, and `t` is shorter than `null`;
                         //  since we can assume the test cases will always have an answer,
                         //  this part can be interpret as dead code)
}                        // End of method

```
> 0 votes

# Answer
# JavaScript, 108 bytes

```
r=[],i=a=b=0
while(a<=x)r.push(a=i++*i/2)
for(a=0;a<3;){
b=r[i]
if(b<=x){
x-=b
a++
console.log(b)}
else i--}

```

### Explanation

`x` represents the input

`while(a<=x)r.push(a=i++*i/2)` Creates an array of all triangular numbers up to x

The `for` loop prints the highest triangular number less than `x`, then subtracts that number from `x`, for three iterations. (basically a greedy algorithm)
> 0 votes

# Answer
# Pyth, 19 bytes

I am *so* out of practise with Pyth, it's untrue :/

```
hfqQsT.C*3+0msSdSQ3

```

Try it out here.

```
hfqQsT.C*3+0msSdSQ3  Implicit: Q=input()

                SQ   Range 1-n
            m        Map the above over d:
              Sd       Range 1-d
             s         Sum the above
                     Yields [1,3,6,10,...]
          +0         Prepend 0 to the above
        *3           Triplicate the above
      .C          3  All combinations of 3 of the above
 f                   Filter the above over T:
    sT                 Where sum of T
  qQ                   Is equal to input
h                    Take the first element of that list

```
> 0 votes

# Answer
# Ruby ~~61~~ ~~57~~ 55 bytes

Inspired by Lynn's Python answer. It generates random triplets until the desired sum is achieved:

```
->n{x=Array.new 3{(0..rand(n+1)).sum}until x&.sum==n;x}

```

It requires Ruby 2.4. In Ruby 2.3 and older, it's a syntax error, and `Range#sum` isn't defined. This longer version (64 bytes) is needed for Ruby 2.3:

```
->n{x=Array.new(3){(a=rand(n+1))*-~a/2}until x&.inject(:+)==n;x}

```

Here's a small test:

```
f=->n{x=Array.new 3{(0..rand(n+1)).sum}until x&.sum==n;x}
# => #<Proc:0x000000018aa5d8@(pry):6 (lambda)>
f[0]
# => [0, 0, 0]
f[13]
# => [0, 3, 10]
f[5]
# => [3, 1, 1]
f[27]
# => [21, 3, 3]
f[27]
# => [0, 21, 6]
f[300]
# => [3, 21, 276]

```

Try it online with Ruby 2.3!
> 0 votes

# Answer
# Javascript (ES6), 108 bytes - fixed

Takes an integer as an input, outputs an array `[a, b, c]` containing a sorted list of triangle numbers `a + b + c = x`, where `a` is the largest triangle number less than or equal to the input, and `b` is the largest triangle number less than or equal to the input minus `a`.

```
x=>{t=[0],t.f=t.forEach,i=j=k=0;for(;j<x;t[i]=j+=i++);t.f(a=>t.f(b=>t.f(c=>a+b+c==x?k=[a,b,c]:0)));return k}

```

## Explanation

```
x=>{
    t=[0],                               // initialize an array of triangle numbers
    t.f=t.forEach,                       // copy forEach method into t.f,
                                         // saves a net of 4 bytes
    i=j=k=0;
    for(;j<x;t[i]=j+=i++);               // populate t with all triangle numbers that
                                         // we could possibly need
    t.f(                                 // loop over all t
        a=>t.f(                          // loop over all t
            b=>t.f(                      // loop over all t
                c=>a+b+c==x?k=[a,b,c]:0  // if a+b+c = x, set k = [a,b,c], else noop
                                         // using a ternary here saves 1 byte vs
                                         // if statement
                                         // iterating over t like this will find all
                                         // permutations of [a,b,c] that match, but
                                         // we will only return the last one found,
                                         // which happens to be sorted in descending order
            )
        )
    );
    return k
}

```

```
const F = x=>{t=[0],t.f=t.forEach,i=j=k=0;for(;j<x;t[i]=j+=i++);t.f(a=>t.f(b=>t.f(c=>a+b+c==x?k=[a,b,c]:0)));return k};

$('#output').hide();
$('#run').click(() => {
  const x = parseInt($('#input').val(), 10);
  if (x >= 0) {
    $('#input').val(x);
    const values = F(x);
    $('#values').text(values.join(', '));
    $('#output').show();
  }
  else {
    $('#output').hide();
    alert('You must enter a positive integer');
  }
});
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
Enter a value: <input type="text" id="input" />
<br />
<button id="run">Get triangle numbers</button>
<br />
<span id="output">Triangle numbers are: <span id="values"></span></span>
```
> 0 votes

# Answer
# , 36 bytes

```
((2!1+$@]#:0({I.@,)=)]+/+/~)2!1+i.,]

```

Try it online!
> 0 votes

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


title: Product of digit runs

text:
# Question
Title: Product of digit runs
We seem to quite like digit runs lately, so here's a fairly simple challenge.

Given a positive integer, split it into it's digit runs, and return the product.

For example:

`11122333` would become `111, 22, 333`, the product of which is `813186`

Input may be taken as an integer, string, or list/array of digits/characters. Your entry must work for any number within it's representable range. I have tested this for 32-bit integers (2^32-1 max value) and the largest possible result I have found is `1099999989` from `1199999999`, which is also within the 32-bit integer range. I have yet to find a number who's output is larger than the input.

For the purposes of this challenge, runs of length 1 are not counted.

If there is only 1 run, return the run. If there are no runs, do anything (undefined behaviour)

Standard I/O rules apply, output can be given as an integer or string.

## Testcases

```
11122333 -> 813186
1112333 -> 36963
1122855098 -> 13310
98776543 -> 77
1000000 -> 0
123456789 -> undefined
1 -> undefined
99445662 -> 287496
1199999999 -> 1099999989
999999999 -> 999999999

```

## Scoring

This is so fewest bytes **in each language** wins!

# Answer
# Haskell, ~~63~~ 55 bytes

Since no one has done Haskell yet here's my take on it. Takes a string as input (of course).

```
import Data.List
f s=product[read x|x@(_:_:_)<-group s]

```

Try it online!

This code almost looks as if it is not golfed, but I cannot find anyway to make it shorter.
> 6 votes

# Answer
# Japt, ~~10~~ 8 bytes

Takes input as a string, outputs an integer or `1` for "undefined".

```
ò¦ fa_Ã×

```

Test it

* 2 bytes saved thanks to ETH
> 5 votes

# Answer
# 05AB1E, ~~6~~ 5 bytes

-1 byte thanks to Erik the Outgolfer

```
γ9ÝKP

```

Try it online!

If we don't need to ignore runs of length one, 2 bytes:

```
γP

```

Try it online!
> 4 votes

# Answer
# JavaScript (ES6), ~~46~~ ~~45~~ ~~38~~ 35 bytes

Takes input as a string, outputs an integer or throws an error for "undefined".

```
s=>eval(s.match(/(.)\1+/g).join`*`)

```
* 7 bytes saved thanks to Herman.
* 3 bytes saved thanks to Craig.

---

## Try it

```
o.innerText=(f=
s=>eval(s.match(/(.)\1+/g).join`*`)
)(i.value="11122333");oninput=_=>o.innerText=f(i.value)
```

```
<input id=i><pre id=o>
```
> 3 votes

# Answer
# Jelly, 7 bytes

```
ŒgḊÐfḌP

```

Try it online!

-1 thanks to Leaky Nun.
> 2 votes

# Answer
# Perl 5, 25 bytes

24 bytes + `-p` flag.

```
s/(.)\1+/$.*=$&/eg;$_=$.

```

Try it online!

Quite straight forward: `(.)\1+` matches the runs of more than one digit, and `$.*=$&` uses `$.` as accumulator for the multiplications (because its initial value is 1 and not 0). Finally, `$_` is set to `$.` and implicitly printed thanks to `-p` flag.
> 2 votes

# Answer
# Perl 6, 21 bytes

```
{[*] .comb(/(.)$0+/)}

```

Test it

This returns `1` if there is no *“digit runs”* as that is the base case for multiplication.

The only change to allow one digit runs is to replace `$0+` with `$0*` in the regular expression.

## Expanded:

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

  [*]        # reduce the following using &infix:<*>

    .comb(   # pull out substrings that match the following
             # (implicit method call on ｢$_｣)

      /
        (.)  # any digit (character)
        $0+  # at least one more of that digit
      /
    )
}

```
> 2 votes

# Answer
# Python 2, ~~95~~ 79 bytes

-2 thanks to @LeakyNum

```
l='0'
p=1
for c in input()+' ':a=c in l;p*=int(l)**(len(l)>1>a);l=l*a+c
print p

```

Try it online!
> 1 votes

# Answer
# Retina, 47 bytes

```
(.)\1+
$*_
T`d
{`(?<=^(_+) _*)_
$1
}`^_+ _
_
_

```

This is slow on the larger test cases.

Try it online!

### Explanation

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

```

First, replace each run of 2 or more of the same digit with that many `_`s, followed by a space for separation.

```
T`d

```

Then remove all remaining digits.

```
{`(?<=^(_+) _*)_
$1
}`^_+ _
_

```

Next, run these two stages in a loop. The first replaces every `_` in the second run with the entire first run, effectively multiplying them. The second stage deletes the first run.

```
_

```

Finally, output the number `_`s.
> 1 votes

# Answer
# C (gcc), ~~93~~ 89 bytes

There must be some more golfing to be done here...

```
z,r;f(char*d){for(z=0;r=*d++;z=r/10?z?z*r:r:z)for(r-=48;r%10==*d-48;r=r*10+*d++-48);d=z;}

```

Try it online!
> 1 votes

# Answer
# Mathematica, 61 bytes

```
Times@@FromDigits/@Select[Split@IntegerDigits@#,Length@#>1&]&

```
> 1 votes

# Answer
# Python 2, 69 bytes

```
lambda n:eval('*'.join(zip(*re.findall(r'((.)\2+)',n))[0]))
import re

```

Try it online!
> 1 votes

# Answer
# PHP, 62 bytes

prints 1 if no run is found

```
preg_match_all('#(.)\1+#',$argn,$t);echo array_product($t[0]);

```

Try it online!
> 0 votes

# Answer
# Ruby, 41 bytes

```
p eval gets.scan(/(.)\1+/).map(&:join)*?*

```

Takes input from stdin, scans it for runs of length \> 1, joins them on `"*"`, evaluates and prints.
> 0 votes

# Answer
# CJam, 18 Bytes

```
qe`{0=1>},{:*i}%:*

```

Try it Online

```
q           e# read string - '1112333'
e`          e# convert string to RLE - [[3,'1'],[1,'2'],[3,'3']]
{0=1>},     e# filter out runs of length one - [[3,'1'],[3,'3']]
{:*i}%      e# convert sub-arrays to runs - [111,333]
:*          e# multiply array elements - 36963

```
> 0 votes

# Answer
# Factor, 151 bytes

```
[ { } { } ] dip
[ 48 - 2dup swap in? [ suffix ] [ [ suffix ] dip 1array ] if ] each
suffix rest [ 0 swap [ swap 10 * + ] each ] map product

```

Getting a better grip on this language! Still don't think I'm using enough combinators...
> 0 votes

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


title: Display a Lemniscate (∞)

text:
# Question
Title: Display a Lemniscate (∞)
The infinity symbol is also called a lemniscate. Your program must draw a lemniscate with text via standard out (formatted with newline feeds) or graphically.

The infinity symbol (by my standards) must be continuous (that is, every non-whitespace character must be touching two other non-whitespace characters diagonally or orthogonally). It must also have two and no more than two gaps of enclosed whitespace (connectivity for whitespace is only orthogonal). Thus, the following output fails:

```
   ooo   ooo
 o    o o    o
o      o      o
 o    o o    o
   ooo   ooo

```

A correct version the above example might be

```
  oooo   oooo
 o    o o    o
o      o      o
 o    o o    o
  oooo   oooo

```

or

```
  ooo   ooo
 o   o o   o
o     o     o
 o   o o   o
  ooo   ooo

```

The size of the ∞ is unimportant. The orientation of the ∞ is unimportant. Symmetry is also unimportant. Graphical displays are accepted as well. Appropriate newline feeds are required in the output.

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

# Answer
> 12 votes
# Desmos, 22 bytes

```
r=\sqrt{\sin 2\theta }

```

Try it here! Desmos is a graphing tool. This plots the polar equation:

which draws a lemniscate shape.

# Answer
> 7 votes
# J, 8 bytes

```
3 5$' o'

```

Like Conor's, prints:

```
 o o
o o o
 o o

```

`$` is J's shape operator, so we are creating a 3 x 5 grid, using the fill chacters  `o`. When fill runs out, `$` repeats them cyclically by default.

Try it online!

# Answer
> 6 votes
# Mathematica, 4 bytes

```
∞&

```

I think this answer covers all the criteria

# Mathematica, 17 bytes

```
Graphics@Text@∞

```

@ovs's opinion is that the right answer is...

# Mathematica, 2 bytes

```
8&

```

and I agree!

# Answer
> 3 votes
# Mathematica - 49 bytes

```
ParametricPlot[{ReIm[Sin[t+I Sin[t]]]},{t,0,2Pi}]

```

Result:

# Answer
> 2 votes
# ///, 13 bytes

```
/z/ o o
/zozz

```

Try it online! Outputs:

```
 o o
o o o
 o o

```

I think this is the smallest valid "lemniscate" allowed by the rules.

# Answer
> 2 votes
# Python 2, ~~21~~ 19 bytes

```
print"o o\nooo\n"*3

```

Try it online!

This prints:

```
o o
ooo
o o
ooo
o o
ooo

```

It may not look like a lemnescate but it has two enclosed spaces (marked with `x`)

```
o o
ooo
oxo
ooo
oxo
ooo

```

And every `o` is connected to at least two other `o`s. Thus despite not looking anything like what it is supposed to this fulfills the bare-minimum requirements.

# Answer
> 1 votes
# Jelly,  ~~8~~  7 bytes

```
8RKḊs5Y

```

As a full program prints:

```
 2 3
4 5 6
 7 8

```

Which seems to adhere to the specification.

**Try it online!**

### How?

```
8RKḊs5Y - Main link: no arguments
8R      - range of 8 -> [1,2,3,4,5,6,7,8]
  K     - join with spaces -> [1,' ',2,' ',3,' ',4,' ',5,' ',6,' ',7,' ',8]
   Ḋ    - dequeue -> [' ',2,' ',3,' ',4,' ',5,' ',6,' ',7,' ',8]
    s5  - split into chunks of length 5 -> [[' ',2,' ',3,' '],[4,' ',5,' ',6],[' ',7,' ',8]]
      Y - join with newlines -> [' ',2,' ',3,' ',`\n`,4,' ',5,' ',6,'\n',' ',7,' ',8]
        - implicit print

```

# Answer
> 1 votes
# Charcoal, 7 bytes (ASCII-art version)

```
ＧＨX²o‖Ｂ

```

Try it online!

The first part (`ＧＨX²o`) prints a hollow polygon of size 2 in the `X` direction using the `o` char as border, that results in this:

```
 o
o o
 o

```

Then I only have to reflect the canvas horizontally (skipping the middle column), to get this:

```
 o o
o o o
 o o

```

Link to the verbose version.

# Answer
> 1 votes
# Charcoal, 9 bytes

```
o↘ooo‖Ｂ¬←

```

Draws the actual last example. 10-byte version that takes a size parameter as input:

```
Ｇ→↘↘Ｎo‖Ｂ¬←

```

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

# Answer
> 0 votes
**C , 55 bytes**

```
i;f(){while(i++<18)putchar(i%6?(i/6+i)%2?32:'o':'\n');}

```

outputs

---
Tags: code-golf, ascii-art
---


title: Solve a game of flood

text:
# Question
Title: Solve a game of flood
This challenge was inspired by the game Flood.

# Challenge

Given a grid of colors, determine the optimal list of moves to take to convert the whole grid to the same color.

First of all, let us say that a pixel is in the "top left chunk" if and only if it is either the top left pixel or it shares an edge with a pixel of the same color in the top left chunk. Then, a move is defined as changing the color of all pixels in the top left chunk to a specific color.

If you change the color of the top left chunk to match the color of one of the pixels adjacent to the top left chunk, then that pixel joins the top left chunk.

The input will be given as a matrix of positive integers with each integer representing a distinct color. A move is defined by the color to which you change the top left chunk; thus, a move is represented as an integer,

The output should be a list of integers representing which moves to take to convert the entire grid to one color in as few moves as possible. If multiple methods are possible, outputting all of them or any one of them is allowed.

# Example

Let's take this as an example:

```
123
132
223

```

In this case, both `[2, 3, 2]` and `[3, 2, 3]` work. We observe the following for `[2, 3, 2]`:

```
123    223    333    222
132 -> 232 -> 332 -> 222
223    223    333    222

```

and the following for `[3, 2, 3]`:

```
123    323    223    333
132 -> 332 -> 222 -> 333
223    223    223    333

```

# Test Cases

```
123
132 -> 2 3 2 OR 3 2 3
223

111
111 -> []
111

123
231 -> 2 3 1 2
312

123
312 -> 2 1 3 1 2 OR 2 1 3 2 1 OR 2 3 2 1 3 OR 2 3 2 3 1 OR 3 1 2 1 3 OR 3 1 2 3 1 OR 3 2 3 1 2 OR 3 2 3 2 1 (Thanks @JonathanAllan)
231

```

# Rules

* This is so the shortest valid submission is determined as the winner, tiebreak by earlier submission winning
* The input and output can be in any reasonable format for matrices and lists
* The input is not necessarily square but is necessarily rectangular
* Your program must be able to handle at least 128 x 128
* Your program must be able to handle at least 16384 colors
* You may also take the number of distinct colors as an input

Please correct my test cases if they are wrong. Thanks!

# Note:

I believe that this is different enough from Create A Flood AI to warrant its own post because the winning criteria are very different; that one mainly asks to find a small number of steps to solve all of the test cases; this one requires one of the shortest solutions and is a code-golf. However, if you disagree, please close-vote as duplicate and then the community can decide.

# Answer
> 2 votes
## CJam (77 bytes)

```
{Ma+a{():B;:A:|{A((:C;0\+a\+_e_,2*{[0C]f/[0_]f*z}*{0Der}%BD+a+a+}fDAe_(-}g;B}

```

Online demo. This is an anonymous block (function) which takes the input as a 2D array and provides the output as a 1D array.

---
Tags: code-golf
---


# Question
Title: How many partitions contain only perfect squares?
Given a non-negative integer or a list of digits, determine in how many ways can the number be formed by concatenating square numbers, which may have leading zeroes.

# Examples

```
input -> output # explanation
164 -> 2 # [16, 4], [1, 64]
101 -> 2 # [1, 01], [1, 0, 1]
100 -> 3 # [100], [1, 00], [1, 0, 0]
1 -> 1 # [1]
0 -> 1 # [0]
164900 -> 9 # [1, 64, 9, 0, 0], [1, 64, 9, 00], [1, 64, 900], [16, 4, 900], [16, 4, 9, 0, 0], [16, 4, 9, 00], [16, 49, 0, 0], [16, 49, 00], [16, 4900]

```

# Rules

* Standard Loopholes Apply
* This is so the shortest answer in bytes wins

# Answer
# Jelly, 8 bytes

```
ŒṖḌÆ²Ạ€S

```

A monadic link taking a list of digits and returning a non-negative integer.

**Try it online!** or see the test suite.

### How?

```
ŒṖḌÆ²Ạ€S - Link: list of digits              e.g. [4,0,0,4]
ŒṖ       - all partitions                         [[4,0,0,4],[4,0,[0,4]],[4,[0,0],4],[4,[0,0,4]],[[4,0],0,4],[[4,0],[0,4]],[[4,0,0],4],[4,0,0,4]]
  Ḍ      - convert from decimal list (vectorises) [[4,0,0,4],[4,0,   4 ],[4,    0,4],[4,      4],[   40,0,4],[   40,    4],[    400,4],     4004]
   Æ²    - is square? (vectorises)                [[1,1,1,1],[1,1,   1 ],[1,    1,1],[1,      1],[    0,1,1],[    0,    1],[      1,1],        0]
     Ạ€  - all truthy? for €ach                   [        1,          1,          1,          1           0,            0,          1,        0]
       S - sum                                    5

```
> 7 votes

# Answer
# Haskell, 135 bytes

```
s x=any((x==).(^2))[0..x]
c(a:b:x)=a*10+b:x
c x=x
h[x]=1>0
h x=(s.head)x
f x@(_:_:_)|y<-until h c x=f(tail y)+f(c y)
f x=sum[1|any s x]

```

Try it online!

Probably not well golfed yet but this is a surprisingly difficult problem
> 7 votes

# Answer
## Haskell, 88 bytes

```
f x=sum[0.5|y<-mapM(\c->[[c],c:" "])x,all((`elem`map(^2)[0..read x]).read).words$id=<<y]

```

Defines a function `f` that takes a string and returns a float. Very slow. Try it online!

## Explanation

I'm using my Haskell tip for computing all partitions of a string with `mapM` and `words`. The snippet `mapM(\c->[[c],c:" "])x` replaces every character `'c'` of a string `x` with either the one-element string `"c"` or the two-element string `"c "`, and returns the list of all possible combinations. If I take one of the results, `y`, concatenate it and call `words` on the result, it will be split at the spaces inserted by `mapM`. In this way I obtain all partitions of `x` into contiguous substrings. Then I just count those results where each partition element is a perfect square (by finding it in the list `[0,1,4,9,..,x^2]`). A caveat is that each partition is counted twice, with and without a trailing space, so I take the sum of `0.5`s instead of `1`s; this is why the result type is a float.

```
f x=                       -- Define f x as
 sum[0.5|                  -- the sum of 0.5 for
  y<-                      -- every y drawn from
  mapM(\c->[[c],c:" "])x,  -- this list (explained above)
                           -- (y is a list of one- and two-element strings)
  all(...)                 -- such that every element of
                 id=<<y]   -- concatenated y
          .words$          -- split at spaces satisfies this:
                           -- (the element is a string)
   (...).read              -- if we convert it to integer
    `elem`                 -- it is an element of
    map(^2)                -- the squares of
    [0..read x]            -- the numbers in this list.

```
> 6 votes

# Answer
# Pyth, 16 bytes

```
lf!f!sI@sjkY2T./

```

Test suite.
> 4 votes

# Answer
# Python 3, ~~148~~ ~~139~~ ~~135~~ 134 bytes

10 bytes thanks to Arnold Palmer.

```
def f(a):
 s=[a[:1]]
 for i in a[1:]:s=sum([[x+[i],x[:-1]+[x[-1]*10+i]]for x in s],[])
 return sum({n**.5%1for n in x}=={0}for x in s)

```

Try it online!
> 4 votes

# Answer
# Python 2, ~~173~~ 163 bytes

```
lambda s:len([l for l in[''.join(sum(zip(s,[','*(n>>i&1)for i in range(len(s))]+['']),())).split(',')for n in range(2**~-len(s))]if {int(x)**.5%1for x in l}=={0}])

```

Try it online!

Edit: Saved 10 bytes due to ArnoldPalmer
> 2 votes

# Answer
# Mathematica, 141 bytes

```
Count[FreeQ[IntegerQ/@Sqrt[FromDigits/@#],1<0]&/@(FoldPairList[TakeDrop,s,#]&/@Flatten[Permutations/@IntegerPartitions[Length[s=#]],1]),1>0]&

```

**input** (a list of digits)

> \[{1,6,4}\]
> 2 votes

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


title: Help! I forgot my password!

text:
# Question
Title: Help! I forgot my password!
Help! I just logged into Stack Exchange, but I forgot what my password is! I need a way to work it out before I log off.

Luckily, I'm an excellent hacker. Not only was I able to find my password's hash, but I also found Stack Exchange's hashing algorithm! It takes the ASCII value of each digit multiplied by that digit's place, then sums all those values together. For example:

```
"135" -> 1*49 + 2*51 + 3*53 = 310

```

I remember that my password is 3 digits long, and that each character is a number between 0 and 5 inclusive (such that it will match the regex: `^[0-5]{3}$`), but that's still too many possibilities to guess. I need a program that can convert a hash back into potential passwords, but despite being an expert hacker, I can't code to save my life! I was able to write these tests out by hand though:

```
input -> output
288   -> 000                      // lowest possible hash
290   -> 200, 010
298   -> 022, 050, 103, 131, 212, 240, 321, 402, 430, 511
318   -> 555                      // highest possible hash

```

Can one of you write a program for me that will take in a hash and print all the possible passwords I could have used?

The input will always be able to produce at least one valid password. Any output format is allowed, as long as the strings can be clearly identified. I'm also not concerned about leading zeroes, so if a potential password is `001`, I'll also accept `01` or `1`.

Please help me from being locked out of Stack Exchange!

### Scoring

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

# Answer
# 05AB1E, 9 bytes

```
5Ý3ãʒÇƶOQ

```

Try it online!

Returns list of lists of digits.
> 10 votes

# Answer
# , ~~113~~ 108 bytes

```
f(int h){int i=47,j,k;while(++i<54)for(j=47;++j<54)for(k=47;++k<54;)if(h==i+j+j+k*3)printf("%c%c%c",i,j,k);}

```

It is unique to see what is meant for output, the output is of the format: 200010

All passwords are written as 3-digits without delimiter.
> 9 votes

# Answer
# Jelly, 16 bytes

```
Ṿ€Oæ.J
6Ḷṗ3Ç⁼¥Ðf

```

A monadic link returning a list of lists of digits.

**Try it online!**

### How?

```
Ṿ€Oæ.J - Link 1, hash: list of integers (the digits of a password)
Ṿ€     - unevaluate €ach (giving a list of characters)
  O    - cast to ordinals (Ṿ€O could actually be replaced with +48 too)
     J - range of length (i.e. [1,2,3] in all use-cases)
   æ.  - dot product

6Ḷṗ3Ç⁼¥Ðf - Main link: number, n
6Ḷ        - lowered range of 6 = [0,1,2,3,4,5]
  ṗ3      - Cartesian power with 3 = [[0,0,0],[0,0,1],...,[5,5,5]] (all passwords)
       Ðf - filter keep if:
      ¥   -   last two links as a dyad (right implicitly n):
    Ç     -     call last link (1) as a monad
     ⁼    -     equals right?

```
> 8 votes

# Answer
# Python 2, ~~126~~ 75 bytes

-2 thanks to @ArnoldPalmer

```
lambda h:[(P/36,P%36/6,P%6)for P in range(216)if P/36+P%36/6*2+P%6*3==h&31]

```

Try it online!
> 5 votes

# Answer
# MATL, 20 bytes

```
'0':'5'3Z^t3:*!si=Y)

```

Try it online!

### Explanation

```
'0':'5'   % Push inclusive range from '0' to '5', that is, '012345'
3Z^       % Cartesian power with exponent 3. Each Cartesian tuple is a row
t         % Duplicate
3:        % Push [1 2 3]
*         % Multiply element-wise with broadcast
!s        % Sum of each row
i         % Input number
=         % Logical mask of values that equal the input
Y)        % Use as logical index into the rows of the matrix. Implicit display

```
> 4 votes

# Answer
# Python 2, 81 bytes

```
lambda h:[(a,b,c)for a in r for b in r for c in r if a+2*b+3*c+288==h]
r=range(6)

```

Try it online!
> 3 votes

# Answer
## Haskell, ~~71~~ ~~70~~ ~~64~~ 61 bytes

```
l=[0..5]
f p=[show=<<[a,b,c]|a<-l,b<-l,c<-l,p-288==a+2*b+3*c]

```

Try it online!
> 3 votes

# Answer
# CJam, ~~26~~ 25 bytes

*-1 byte thanks to Challenger5*

```
{:H;6Zm*{s:i3,:).*:+H=},}

```

Anonymous block expecting the hash on the stack (as an integer) and leaves the result on the stack (as a list of strings).

Try it online!

### Explanation

```
:H;    e# Store the hash in H.
6Zm*   e# 3rd Cartesian power of [0 1 2 3 4 5].
{      e# For each tuple in the power:
 s     e#  Stringify the tuple.
 :i    e#  Get the code point of each digit.
 3,:)  e#  Push [1 2 3].
 .*    e#  Element-wise multiplication of the two lists.
 :+    e#  Sum the result.
 H=    e#  Check if it's equal to the hash.
},     e# Filter the tuples to only ones for which this block gave a truthy result.

```
> 2 votes

# Answer
# C# (.NET Core),133 131 125 123 bytes

```
n=>{int i,j,k;for(i=48;i<54;++i)for(j=48;j<54;++j)for(k=48;k<54;++k)if(i+j*2+k*3==n)Console.Write($"{i%48}{j%48}{k%48},");}

```

Try it online!
> 2 votes

# Answer
## JavaScript (Firefox 30-57), 72 bytes

```
n=>[for(i of s="012345")for(j of s)for(k of s)if(n-i-j*2-k*3==288)i+j+k]

```
> 2 votes

# Answer
# Charcoal, 33 bytes

```
Ｆ⁶Ｆ⁶Ｆ⁶¿⁼⁺℅Ｉι⁺×℅Ｉκ²×℅Ｉλ³Ｉθ«ＩιＩκＩλ⸿

```

Try it online!

A similar approach to other answers: loop thrice from 0 to 5, calculate the hash and print the state of the iteration variables if it coincides with the input hash.

Link to the verbose version.
> 2 votes

# Answer
# Java, 162 Bytes

```
static void f(int n){for(int i=48;i<54;i++){for(int j=48;j<54;j++){for(int k=48;k<54;k++){if(i+j*2+k*3==n)System.out.println((char)i+""+(char)j+""+(char)k);}}}}

```
> 2 votes

# Answer
# , ~~67~~ ~~62~~ 61 bytes

*-5 bytes thanks to Jarko Dubbeldam*

```
b=t(t(expand.grid(rep(list(0:5),3))));b[b%*%1:3==scan()-288,]

```

Try it online!

reads the number from `stdin`; returns a matrix where the rows are the characters.

It generates all possible trios of digits in a matrix format (`b`), computes the matrix product `b * [1,2,3]`, takes the rows of `b` which match (subtracting `288` from the input which is `1*48+2*28+3*48`) and returns them.
> 1 votes

# Answer
# Pyth, 18 bytes

```
fqQs*VS3CMT^jkU6 3

```
> 1 votes

# Answer
# QBIC, 40 bytes

```
[0,5|[0,5|[0,5|~a+b+b+c+c+c+288=:\?a,b,c

```

## Explanation

```
[0,5|                Make a FOR loop run through the possible digits for pos 1, called a
[0,5|                Loop for #2, b
[0,5|                Loop for #3, c
                     Calculate the hash by taking a once, b twice and c thrice,
                     and raising all to their ASCII codepoints
 a+b+b+c+c+c+288
~               =:   IF thta is euqal to the given hash (read from cmd line)
\?a,b,c              THEN print the digits
                     (the IF and the FOR loops are auto-closed by QBIC)

```
> 1 votes

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


title: {Curly Numbers};

text:
# Question
Title: {Curly Numbers};
In the esoteric programming language Curly, programs consist solely of curly braces `{}` and semicolons `;`. Despite this humble toolset, Curly has literals that can represent any nonnegative integer. The format is a little hard for the uninitiated to read, though, so let's write some code to do the conversion for us.

## Format of numbers

Curly numbers are structured according to the following rules:

1. Adding a semicolon adds one to the number.
2. A number enclosed in curly braces is multiplied by four.
3. Curly-brace groups may be nested but not concatenated. Braces must match properly.
4. Semicolons outside a set of curly braces must come afterward, not before.
5. To avoid ambiguity in parsing, a number must always start with a curly brace.

Some examples:

```
{;;}     2*4 = 8
{{;};};  (1*4+1)*4+1 = 21
{};;;    0*4+3 = 3

```

(Note that rule 5 means the numbers 0 to 3 must start with an empty pair of curly braces.)

And some invalid examples:

```
{{;}{;;}}  Curly brace groups side-by-side, not nested
{;}}       Unmatched brace
{;{;}}     Semicolon before curly-brace group
;;;        Number does not start with curly brace

```

Here's a BNF grammar for Curly numbers:

```
<number> ::= "{" <inner> "}" <semis>
<inner>  ::= <semis>
           | <number>
<semis>  ::= ";" <semis>
           | ""

```

Numbers like `{;;;;}` (more than 3 semicolons in a row) or `{{};}` (unnecessary empty brace groups) are called *improper* Curly numbers. They obey the above grammar and can be evaluated in the usual way, but they are also capable of shorter representations (for the above examples, `{{;}}` and `{;}` respectively).

## The challenge

Write a program or function that inputs/receives a string. If the string is a nonnegative decimal integer, output/return the *proper* (i.e. shortest possible) Curly representation for that integer. If the string is a Curly number, output/return its decimal representation.

**Input** can be received via STDIN, command-line argument, or function parameter. It *must* be a string; that is, you may not write a function that accepts strings for Curly numbers but integers for decimal numbers.

**Output** can be printed to STDOUT or returned from the function. A function *may* return an integer when appropriate, or it may return strings in all situations.

Your program does not have to handle bad input (Curly numbers that break the formatting rules, floating point numbers, negative integers, random text), and it is **not** required to handle improper Curly numbers (but see below). Input will consist only of printable ASCII characters.

## Scoring

The shortest code in bytes wins. If your program can do **both** of the following:

1. correctly handle improper Curly numbers, and
2. when given a Curly number, ignore any extra characters that aren't `{};`

then subtract 10% from your score. (Integer input will never have extraneous characters, even for the bonus.)

## Test cases

```
Input       Output
{;;}        8
{{;};};     21
{};;;       3
{{{{;}}};}  260
{}          0
4           {;}
17          {{;}};
1           {};
0           {}
96          {{{;};;}}

```

For the bonus:

```
{};;;;;     5
{{;;;;};;}  72
c{u;r;l}y;! 9
42{;} ;;;;  8

```

Note: Curly is not yet implemented. But if this question does well, I may develop it further.

# Answer
> 16 votes
# Pyth, ~~35~~ 32 bytes - 10% = 28.8

```
.x.U+jb`HZ*R\;.[Z2jsz4i/R\;cz\}4

```

Try it online: Demonstration or Test Suite

edit: As it turned out, I accidentally can also handle improper Curly Numbers. Wasn't planned at all. ;-)

### Explanation:

There are two expressions in the code. The first one converts a number into a Curly Number, and the second one converts a Curly Number into a regular number. `.x` handles, which expression gets printed. It will try to print the first expression. If there are any non-digits in the input, the first expression fails (via Exception). `.x` catches the Exception and prints the second one.

```
.U+jb`HZ*R\;.[Z2jsz4   # number to Curly Number
                 sz    read the input and converts it to an int
                j  4   convert to base 4
            .[Z2       pad zeros on the left, until length is >= 2
        *R\;           convert each digit to ";"s
                       lets call this list of ";"s Y
.U                     reduce this list, start with b=Y[0],
                       Z iterates over Y[1], Y[2], ...,
                       update b in each step with:
   jb`H                   put b into curly brackets
  +    Z                  and append Z

i/R\;cz\}4             # Curly Number to regular number
     cz\}              split the input by "}"
 /R\;                  count the ";"s in each string
i        4             convert this list from base 4 to base 10

```

# Answer
> 12 votes
# CJam, ~~51~~ ~~47~~ ~~44~~ 41 bytes

```
r_'{-_@={i4bYUe[';f*{{}s@*\+}*}{'}/:,4b}?

```

Try it online: sample run | test suite

### How it works

```
r        e# Read a token from STDIN.
_'{-     e# Remove all left curly brackets from a copy of the token.
_@       e# Copy the modified token and rotate the original on top of it.
=        e# Check for equality.
{        e# If the strings were equal:
  i4b    e#   Convert to integer, then to base 4.
  YUe[   e#   Left-pad the resulting array with zeroes to a length of 2.
  ';f*   e#   Replace each digit with that many semicolons.
  {      e#   For each string of semicolons but the first:
    {}s  e#     Push the string "{}".
    @    e#     Rotate the first string or the result of the previous
         e#     iteration on top of the stack.
    *    e#     Join, i.e., surround the string with curly brackets.
    \+   e#     Append the current string of semicolons to the result.
  }*     e#
}{       e# Else:
  '}/    e#   Split the modified input at right curly brackets.
  :,     e#   Replace each run of 0 to 3 semicolons by its length.
  4b     e#   Convert from base 4 to integer.
}?       e#

```

# Answer
> 7 votes
# Python 2, 167 bytes - 10% = 150.3

```
d=lambda x:("{"+d(x//4)+"}"if x>3 else"")+";"*(x%4)
c=lambda n:"{}"*(int(n)<4)+d(int(n))if n.isdigit()else reduce(lambda x,y:x*4+y,[x.count(";")for x in n.split("}")])

```

In this implementation, `c` is the function that satisfies the requirements. It returns a string if given an nonnegative integer as input, or an integer if given a curly number as input.

# Answer
> 6 votes
# Python 266 bytes - 10% = ~~1268.1~~ ~~326.7~~ 239.4 bytes

Boy am I not a code golfer yet =/, but that 10% helped *me* out a *lot* when my score was still over 1000!

I have a fully fleshed out (and verbose) version of this code here. It will recognize the validity of curly numbers, and provide a looped interface to enter numbers for testing.

(Comments just for clarification)

See this code in action

```
def c(t):                           # curly to int function
 v=0                                #  int value of input
 for a in t:                        #  for each character of input
  if a==';':v+=1                    #   if you find a ';', add one to total
  if a=='}':v*=4                    #   if you find a '}', multiply total by 4
 print v                            #  print value
def i(t):                           # int to curly function
 v=int(t);f,b="{}"if v<4 else"",""  #  get integer value. initialize front (f) and back (b) strings
 while 1:                           #  loop until stopped
  r,v=v%4,int(v/4)                  #   get remainder of v/4 and int value of v/4
  if r>0:b=';'*r+b                  #   if remainder exists, prepend that many ';' to back string
  if v>0:f=f+'{';b='}'+b            #   if remaining value > 4, append '{' to front and prepend '}' to back
  if v<4:b=';'*v+b;break            #   if remaining value < 4, prepend that many ';' to back string and break
 print f+b                          #  print result
t=raw_input()                       # get raw input
try:int(t);i(t)                     # use try block to determine which function to call
except:c(t)                         #

```

Thanks to Erik Konstantopoulos for a major byte reduction! You could say... he really took a... byte... out of my code... \*self five\*

# Answer
> 4 votes
# CJam, ~~87 bytes~~ 80.1 score (89 bytes - 10% bonus)

Update version that qualifies for the bonus while growing by 2 bytes:

```
l_'{#){VX@{";{}"#)" _@+\ 4* 4/"S/=~}/;}{i_4<{"{}"\';*}{{4md\_{F'{\+'}+}{;L}?\';*+}:F~}?}?

```

Try it online

First time I used recursion in CJam! The whole thing may look kind of lengthy, but the two completely separate conversions add up.

I used a completely separate case for converting numbers smaller than 4 to Curly. It's probably possible to avoid that, but folding the special case handling into the recursive function wouldn't be entirely trivial. And adding the extra `{}` as a post-processing step didn't really look any better, even though I should try again if it might be slightly shorter.

# Answer
> 3 votes
# C#, 173 - 10% = 155.7 ~~171.0, 177.3~~

This does no validation and only looks for `;` and `}` characters. It assumes all `{` characters come before any `;` characters. The hardest thing I found was to not insert a `{}` in the middle of a Curly number.

Line breaks and indents for clarity:

```
string C(string a,int b=0){
    int n;
    if(int.TryParse(a,out n))
        a=(n>=b?"{"+C(""+n/4,4)+"}":"")+";;;".Remove(n%4);
    else
        foreach(int c in a)
            a=""+(c==59?++n:c==125?n*=4:n);
    return a;
}

```

# Answer
> 2 votes
# Java 326 bytes - 10% = 294 bytes

It is complete program written in java,

```
public class a{static String c(long a,int v){if(a==0)return v==0?"{}":"";String x="";for(int i=0;i<a%4;i++)x+=";";return "{"+c(a/4,v+1)+"}"+x;}public static void main(String[]c){try{System.out.println(c(Long.parseLong(c[0]),0));}catch(Exception e){System.out.println(c[0].chars().reduce(0,(a,b)->b==';'?a+1:b=='}'?a*4:a));}}}

```

I'm sure it can be much shorter but i cant have much time now to optimize it

# Answer
> 2 votes
# GNU sed, 330 326 - 10% = 293.4

(I added one for the use of `-r` before claiming the bonus 10%; I hope that's correct)

```
/;/{
s/[^};]//g
:c
s/(;*)\}/\1\1\1\1/
tc
:d
/;/{
s/;;;;;/v/g
s/vv/x/g
/[;v]/!s/\b/0/2
s/;;/b/g
s/bb/4/
s/b;/3/
s/v;/6/
s/vb/7/
s/v3/8/
s/v4/9/
y/;bvx/125;/
td
}
n
}
:u
s/\b9/;8/
s/\b8/;7/
s/\b7/;6/
s/\b6/;5/
s/\b5/;4/
s/\b4/;3/
s/\b3/;2/
s/\b2/;1/
s/\b1/;0/
s/\b0//
/[^;]/s/;/&&&&&&&&&&/g
tu
:v
s/;;;;/v/g
s/v+/{&}/
y/v/;/
tv

```

The full version shows that most of the above is conversion between decimal and unary:

```
#!/bin/sed -rf

/;/{

# Delete non-Curly characters
s/[^};]//g

# Curly to unary
:c
s/(;*)\}/\1\1\1\1/
tc

# unary to decimal
:d
/;/{
s/;;;;;/v/g
s/vv/x/g
/[;v]/!s/\b/0/2
s/;;/b/g
s/bb/4/
s/b;/3/
s/v;/6/
s/vb/7/
s/v3/8/
s/v4/9/
y/;bvx/125;/
td
}

# done
n

}

# Decimal to unary
:u
s/\b9/;8/
s/\b8/;7/
s/\b7/;6/
s/\b6/;5/
s/\b5/;4/
s/\b4/;3/
s/\b3/;2/
s/\b2/;1/
s/\b1/;0/
s/\b0//
/[^;]/s/;/&&&&&&&&&&/g
tu

# Unary to Curly
:v
s/;;;;/v/g
s/v+/{&}/
y/v/;/
tv

```

# Answer
> 2 votes
# Perl, 183 177

This might not be the shortest Perl answer, but I think it's interesting enough to post (input in `$_`, output as return value):

`sub f{if(/}/){s/[{}]/00/g;oct'0b'.s/00(;+)/sprintf'%02b',length$1/ger}else{$_=sprintf'%064b',$_;s/../oct"0b$&"/ge;s/^0+(?!$)//;$_='{'x length.$_;s/\d/'}'.';'x$&/ge;s/\Q{{}/{/r}}`

We observe that Curly is simply quaternary (base-4) notation. We're slightly hampered by Perl's lack of native support for quaternary, but luckily, each quaternit is two bits in binary, and we can read and write binary. So we have the following:

1. Curly to decimal: convert each Curly digit to 2 binary digits, concatenate and convert to decimal
2. Decimal to Curly: print the number in binary (forcing an even number of digits), then convert each bit-pair to Curly.

### Expanded version

```
sub f
{
    if (/}/) {
        s/[{}]/00/g;     # digits are now 00 00; 00;; 00;;;
                         # and opening braces become harmless leading zeros
        s/00(;+)/sprintf'%02b',length $1/ge;
                         # convert semicolons to binary, leaving zeros alone
        oct "0b$_"       # now to decimal
    } else {
        $_=sprintf'%064b',$_;   # decimal to binary
        s/../oct"0b$&"/ge;      # bit-pair to quaternit
        s/^0+(?!$)//;           #/remove leading zeros
        $_='{'x length.$_;      # prefix enough opening braces
        s/\d/'}'.';'x$&/ge;     #/digit to semicolons
        s/{{}/{/r               # first empty brace, unless $_ <= {};;;
    }
}

```

# Answer
> 1 votes
# Perl 5, 154 (~~185~~ 170 Bytes - 10% + 1 Penalty)

```
$e=$/;if($_=~/{/){s/[^{};]//g;s/;/+1/g;s/{/+4*(/g;s/}/+0)/g;$b=eval}else{$r=$_;$b=$r<4?"{}":"";while($r>0){if($r%4>0){$r--;$e=";$e"}else{$b.="{";$e="}$e";$r/=4}}}$_=$b.$e

```

Regex & eval resolve the curlies.
The generation of the curlies is done differently.

### Test

Test file contains also the bonus cases

```
$ cat curlytestcases.txt
{}
{};
{};;
{};;;
{;;}
{{;};};
{{{{;}}};}
0
1
2
3
4
17
96
{};;;;;
42{;} ;;;;
c{u;r;l}y;!
{{;;;;};;}

$ cat curlytestcases.txt |perl -p curlies.pl
0
1
2
3
8
21
260
{}
{};
{};;
{};;;
{;}
{{;}};
{{{;};;}}
5
8
9
72

```

# Answer
> 1 votes
# JavaScript (ES6), 95 (105-10%)

```
f=(n,r='{}')=>-1-n?(n>3?'{'+f(n>>2,'')+'}':r)+';'.repeat(n&3):n.replace(/[;}]/g,c=>c>';'?n*=4:++n,n=0)&&n

```

Test running the snippet below

```
f=(n,r='{}')=>-1-n?(n>3?'{'+f(n>>2,'')+'}':r)+';'.repeat(n&3)
:n.replace(/[;}]/g,c=>c>';'?n*=4:++n,n=0)&&n

// Test
function out(x) { O.innerHTML=x+'\n'+O.innerHTML; }

function go() { out(I.value + ' --> ' + f(I.value)) }

;[
  ['{;;}', 8]
, ['{{;};};', 21 ]
, ['{};;;', 3 ]
, ['{{{{;}}};}', 260 ]
, ['{}', 0 ]
, [ 4, '{;}' ]
, [ 17, '{{;}};' ]
, [ 1,'{};' ]
, [ 0, '{}' ]
, [ 96, '{{{;};;}}' ]
, ['{};;;;;', 5 ]
, ['{{;;;;};;}' , 72 ]
, ['c{u;r;l}y;!', 9 ]
, ['42{;} ;;;;', 8 ]
].forEach(t => {
  r=f(t[0])
  k=t[1]
  out('Test ' +(r==k?'OK':'Fail')+'\nInput:  '+t[0]+'\nResult: '+r+'\nCheck:  '+k+'\n')
})
```

```
Custom test <input id=I><button onclick='go()'>-></button>
<pre id=O></pre>
```

# Answer
> 1 votes
# Ruby, ~~126.9~~ 129.6 (144 - 10%)

Uses recursion to convert decimal into curly form. Removing the check for ignoring characters outside of `/[;{}]/` increases the score by `0.4` at the moment.

```
f=->s{s=~/^\d+$/?(n=s.to_i
"{#{n<1?'':f[(n/4).to_s].gsub('{}','')}}#{?;*(n%4)}"):eval(s.tr("^{;}","").gsub(/./){|c|c<?A?"+1":c>?|?")*4":"+(0"})}

```

# Answer
> 1 votes
# Retina, ~~69~~ 64 bytes

```
+`{(;*)}
$1$1$1$1
^\d+|^(;*)
$*;$.1
+`(;+)\1\1\1
{$1}
^;|^$
{}$&

```

Try Test Suite

---

# Explanation

```
+`{(;*)}
$1$1$1$1

```

Decompose the innermost braces to just `;`s. Loop until no more braces.

```
^\d+|^(;*)
$*;$.1

```

Convert between decimal and unary `;`

```
+`(;+)\1\1\1
{$1}

```

Find the longest run of `;` that is a multiple of 4 and nest into braces, loop until no more runs of 4+ exist.

```
^;|^$
{}$&

```

If the resulting curly number begins with `;` or is empty string, add `{}` in front.

# Answer
> 1 votes
# Python 2, 157 bytes -10% = 141.3

```
lambda n:'{}'*(int(n)<4)+g(int(n))if n.isdigit()else sum((v==';')*4**n.count('}',i)for i,v in enumerate(n))
g=lambda n:'{%s}'%g(n/4)+';'*(n%4)if n>3else';'*n

```

Try it online!

A more golfed Python 2 answer that handles the bonus cases. Didn't want to necro dead posts with this as a comment, so here it is.

It works from the inside in on curly numbers, adding 4^(the number of end curly brackets left in the string) to the sum for each semicolon found. If the string is a number, then it recursively creates the curly number in the same way as the grammar provided.

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


title: Is it a turtle prime?

text:
# Question
Title: Is it a turtle prime?
As we all know, it's turtles all the way down. But is it primes all the way down too?

A number is considered a "turtle-prime" if it satisfies the following conditions:

```
1) It is prime.
2) It is possible to remove a single digit leaving a prime number.
3) Step 2 can be repeated until left with a single digit prime.

```

For example, `239` is a "turtle-prime", as it can be reduced to `23` then either `2` or `3`, both of which are prime. It also can be reduced to `29` then `2`. `151` is not a turtle prime, as it reduces to `15` (not prime), `51` (not prime), or `11`. `11` is prime, but can only reduce to `1`, which is not.

Given a positive integer, determine if it is a "turtle-prime". Your output can be in any form so long as it gives the same output for any truthy or falsey value.

Test cases:

```
input -> output
1     -> false
2     -> true
17    -> true
19    -> false
239   -> true
389   -> false

```

# Scoring

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

# Answer
> 6 votes
# Jelly, 16 bytes

```
DŒPḊṖLÐṀḌß€¬Ȧ<ÆP

```

Try it online!

### How it works

```
DŒPḊṖLÐṀḌß€¬Ȧ<ÆP  Main link. Argument: n

D                 Decimal; convert n to base 10.
 ŒP               Powerset; get all sub-arrays of n's decimal digits.
   Ḋ              Dequeue; remove the first sub-array (empty array).
    Ṗ             Pop; remove the last sub-array (all of n's digits).
     LÐṀ          Maximal by length; keep those of the remaining subarrays that
                  have maximal length. This keep exactly those sub-arrays that have
                  one (and only one) digit removed. If n < 10, this yields an empty
                  array. Without Ḋ, it would yield [[]] instead.
        Ḍ         Undecimal; turn the generated digit arrays into integers.
         ß€       Recursively map the main link over the generated integers.
           ¬      Negate; map 1 to 0 and 0 to 1.
            Ȧ     Any and all; yield 0 if the array is empty (n < 10) or any of the
                  recursive calls returned 1 (mapped to 0). If all calls returned
                  0, this will yield 1.
              ÆP  Test n for primality, yielding 1 for primes, 0 otherwise.
             <    Test if the result to the left is less than the result to the
                  right. This is possible only if the left result is 0 (n < 10 or
                  removing a digit results in a turtle prime) and the right result
                  is 1 (n itself is prime).

```

# Answer
> 7 votes
# Haskell, ~~104~~ ~~102~~ ~~99~~ ~~98~~ ~~97~~ ~~95~~ 91 bytes

```
p x=product[2..x-1]^2`mod`x>0
f[]=1>0
f x|y<-zip[0..]x=or[f[snd b|b<-y,b/=a]|a<-y,p$read x]

```

Try it online!

## Explanation

First we set up a primality test

```
p x=product[2..x-1]^2`mod`x>0

```

This uses Wilson's Theorem to determine the primality of an input.

We then declare a base case, which will assert that the empty string is truthy.

```
f[]=1>0

```

Now we define the actual function

```
f x|y<-zip[0..]x=or[f[snd b|b<-y,b/=a]|a<-y,p$read x]

```

We use a pattern guard to bind `zip[0..]x` to `y`, because we need to use it twice later. We then assert the answer is

```
or[f[snd b|b<-y,b/=a]|a<-y,p$read x]

```

`[[snd b|b<-y,b/=a]|a<-y]` is all of the numbers that are a digit removed from our input. So we are asserting that at least one of these numbers is truthy for `f`. In order to ensure that composite numbers are falsy we add in `prime$read x`. If the number is not prime the list will become empty and the `any` of a empty list is false.

# Answer
> 6 votes
# R, ~~124~~ ~~122~~ ~~120~~ ~~113~~ ~~95~~ ~~93~~ ~~106~~ 105 bytes

```
 g=pryr::f(`if`(gmp::isprime(sum(x*10^((l<-sum(x|1)-1):0))),any(!l,sapply(0:l+1,function(z)g(x[-z]))),!1))

```

Which evaluates to the function:

```
function (x)
if (gmp::isprime(sum(x * 10^((l <- sum(x | 1) - 1):0)))) any(!l,
    sapply(0:l + 1, function(z) g(x[-z]))) else !1

```

Recursive solution. Takes input as a list of digits.

Has 2 logical statements:

1. Is `x` prime when concatenated?
2. Is any of the following `TRUE`:

1. Is the length of `x` nonzero? This is our final terminating condition.
    2. Is `f` `TRUE` for any subset of `x`?

The first statement ensures we keep working with primes only. The second does the actual recursion.

Saved two bytes thanks to @Giuseppe.

I had to revert some of my golfs because of a bug, where I was testing with a previous function definition by accident.

# R, 98 bytes, non-competing

Like I mentioned in the comments, I made a package. Since the challenge predates that, this is non-competing, but I wanted to showcase it a bit. It's not much so far, but we'll get there.

```
g=pryr::f(`if`(gmp::isprime(RG::C(x)),any(!(l<-sum(x|1)-1),sapply(0:l+1,function(z)g(x[-z]))),!1))

```

`C()` is the first function in the package, and takes care of concatenating digits into a numeric.

# Answer
> 5 votes
# Jelly, 19 bytes

```
DJḟÐ€`ịDḌḟ0ß€¬Ȧ¬aÆP

```

Try it online!

## How it works

```
DJḟÐ€`ịDḌḟ0ß€¬Ȧ¬aÆP                input:239

D                    decimal         [2,3,9]
 J                   range@length    [1,2,3]
  ḟÐ€`               filter out each [[2,3],[1,3],[1,2]]
      ịD             index&decimal   [[3,9],[2,9],[2,3]]
        Ḍ            undecimal       [39,29,23]
         ḟ0          filter out 0    [39,29,23]
           ß€        this@each       [1,1,1]
             ¬       logical not     [0,0,0]
              Ȧ      any and all     0
               ¬     logical not     1
                aÆP  and&is_prime    1

```

Recursion without base case ftw.

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

```
DµœcL’$Ḍµ€FÆPÐf
×⁵WÇÐĿFṪ<8

```

A monadic link taking and returning integers (`1` for turtle `0` otherwise).

**Try it online!**

### How?

```
DµœcL’$Ḍµ€FÆPÐf  Link 1: primes by digit removal: list of numbers  e.g. [19790]
D                cast to decimal list (vectorises)                      [[1,9,7,9,0]]
 µ      µ€       monadic chain for €ach:
      $            last two links as a monad:
    L                length                                             5
     ’               decrement                                          4
  œc             combinations without replacement                       [[1,9,7,9],[1,9,7,0],[1,9,9,0],[1,7,9,0],[9,7,9,0]]
       Ḍ         cast from decimal list (vectorises)                    [1979,1970,1990,1790,9790]
          F      flatten (from a list of lists form the for €ach to a single list)
             Ðf  filter keep if:
           ÆP      is prime?

×⁵WÇÐĿFṪ<8  Main Link: number, n             e.g. 1979
 ⁵          literal 10
×           multiply                              19790
              (this is so the first number is tested as prime too)
  W         wrap in a list                        [19790]
    ÐĿ      loop, collecting results (including the input×10) while change still occurs:
   Ç          call the last (1) link as a monad   [[19790],[1979],[197,199,179],[19,17,97,19,19,17,19,79],[7,7,7,7],[]]
      F     flatten                               [19790,1979,197,199,179,19,17,97,19,19,17,19,79,7,7,7,7]
       Ṫ    tail                                  7
        <8  less than 8?                          1
              (if a single digit prime was reached this will be 1
               otherwise it will be 0
               e.g. an input of 4 yields 40 at the end which is not <8)

```

# Answer
> 2 votes
# Python 2, ~~132~~ ~~124~~ 119 bytes

-8 Thanks to @WheatWizard

-5 Thanks to @LeakyNun

```
p=lambda i:i>1and all(i%v for v in range(2,i))
f=lambda n:n<'0'or any(f(n[:i]+n[i+1:])for i in range(len(n)))*p(int(n))

```

Try it online!

Can't think of anything to hone it down without some builtin prime checker. Takes the number as a string (I assumed this given the OP allowed a list of digits, but if not then +14 bytes for another lambda), and recursively computes each "turtled" number's turtleness.

# Answer
> 2 votes
# Ruby, ~~72~~ 57+8 = ~~80~~ 65 bytes

Uses the `-rprime` flag. -15 bytes from histocrat!

```
f=->n{n==''||n.to_i.prime?&!n.scan(/./){f[$`+$']&&break}}

```

Try it online!

# Answer
> 2 votes
# Java, 220 bytes

Try it online!

Golfed:

```
boolean t(String n){int l=n.length();if(f(x->{for(int i=2;i<x;)if(x%i++==0)return 1<0;return x>1;},new Integer(n)))if(l<2)return 1>0;else for(int i=0;i<l;)if(t(n.substring(0,i)+n.substring(++i,l)))return 1>0;return 1<0;}

```

Ungolfed:

```
  boolean t(String n) {
    int l = n.length();
    if (f(x -> {
      for (int i = 2; i < x;) {
        if (x % i++ == 0) {
          return 1 < 0;
        }
      }
      return x > 1;
    } , new Integer(n))) {
      if (l < 2) {
        return 1 > 0;
      }
      else {
        for (int i = 0; i < l;) {
          if (t(n.substring(0, i) + n.substring(++i, l))) {
            return 1 > 0;
          }
        }
      }
    }
    return 1 < 0;
  }

```

# Answer
> 1 votes
# 05AB1E, ~~28~~ 27 bytes

Iterative solution.

```
¸[D0èg2‹#εæ¨D€gZQÏDpÏ}˜]p1å

```

Try it online!

**Explanation**

```
¸                              # wrap input in a list
 [                             # start a loop
  D0èg2‹#                      # if the length of the first element is less than 2, break
         ε                     # apply to each element in the list
          æ                    # compute powerset
           ¨                   # remove last element (the full number)
            D€gZQÏ             # keep only the elements whose length is the max length
                  DpÏ          # keep only primes
                     }         # end apply
                      ˜        # flatten list
                       ]       # end loop
                        p1å    # is any element in the resulting list prime

```

# Answer
> 1 votes
# C#, 355 bytes

```
namespace System{using B=Numerics.BigInteger;class A{static void Main(){Console.WriteLine(D(Console.ReadLine()));}static bool P(B x){if(x<2)return 1<0;B r=1;for(int i=1;i<=x-1;i++)r*=i;return(r+1)%x==0;}static bool D(string x){if(x.Length==0)return 1>0;bool b;if(b=P(B.Parse(x))){var n=1<0;for(int i=0;i<x.Length;i++)n|=D(x.Remove(i,1));b&=n;}return b;}}}

```

Try it online!

My first code golf, so I hope I did it alright. I couldn't think of a way to make it even smaller (other than using int instead of BigInteger, but I did it so it would work for all provided test cases). Anyway, here's the same properly formatted:

```
namespace System
{
    using B = Numerics.BigInteger;
    class A
    {
        static void Main()
        {
            Console.WriteLine(D(Console.ReadLine()));
        }

        static bool P(B x)
        {
            if (x < 2)
                return 1<0;
            B r = 1;
            for (int i = 1; i <= x - 1; i++)
                r *= i;
            return (r + 1) % x == 0;
        }

        static bool D(string x)
        {
            if (x.Length == 0)
                return 1>0;
            bool b;
            if (b = P(B.Parse(x)))
            {
                var n = 1<0;
                for (int i = 0; i < x.Length; i++)
                    n |= D(x.Remove(i, 1));
                b &= n;
            }
            return b;
        }
    }
}

```

# Answer
> 0 votes
# Perl 6, 65 bytes

```
my&f={.is-prime&&(10>$_||?grep {f +[~] .list},m:ex/^(.*).(.*)$/)}

```

Try it online!

# Answer
> 0 votes
# PHP, 164 bytes

```
function t($n){for($i=1;++$i<$n;)if($n%$i<1)return 0;if($n<10)return $n>1;foreach($r=str_split($n)as$k=>$v){$q=$r;array_splice($q,$k,1);$z|=t(join($q));}return $z;}

```

Try it online!

Starts off by testing the number for primality, then loops through the digits as an array, popping each one out and joining the rest back together and feeding them recursively through the function again. Each link downwards does a logical OR with the lower paths, only returning `true` if there exists at least one path of all primes.

# Answer
> 0 votes
# Javascript 167 bytes

```
n=>{a=[];for(i=1;i++<=n;)a.every(x=>i%x)?a.push(i):0;b=k=>(s=''+k,a.indexOf(k)>-1&&(k<10||[...s].some((x,i)=>(r=[...s],r.splice(i,1),b(~~(r.join('')))))));return b(n)}

```

## Explanation

```
n=>{
    a=[];                             // create array to store primes in
    for(i=1;i++<=n;)                  // iterate from 2 to n
        a.every(x=>i%x)?a.push(i):0;  // if i % x is truthy for all x in a,
                                      // then i is prime
    b=k=>(                            // function to test is k is turtle prime
        s=''+k,                       // convert k to a string
        a.indexOf(k)>-1 && (          // if k is prime and
            k<10 ||                   // k is a single digit or
            [...s].some((x,i)=>(      // iterate over the digits of k
                                      // and check to see if, by removing each
                                      // any of the resulting numbers is turtle prime
                                      // ... is spread operator
                                      // [...s] converts string s to an array of characters
                r=[...s],             // convert s to an array again,
                                      // importantly, this cannot be the same array
                                      // we created above, as we need to
                r.splice(i,1),        // splice out the ith element of the array
                b(~~(r.join('')))     // join the array to a string, convert to int,
                                      // and check if this number is turtle prime
                                      // ~ is bitwise negate, implicitly converts to int first before negating
                                      // ~~ negates the negation, getting us the int
            ))
        )
    );
    return b(n)
}

```

```
F=n=>{a=[];for(i=1;i++<=n;)a.every(x=>i%x)?a.push(i):0;b=k=>(s=''+k,a.indexOf(k)>-1&&(k<10||[...s].some((x,i)=>(r=[...s],r.splice(i,1),b(~~(r.join('')))))));return b(n)}

$('#input').on('keyup', () => $('#output').text(F(parseInt($('#input').val(), 10))))
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<input type="text" id="input" />
<span id="output"></span>
```

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


# Question
Title: Most common elements of a list in Python
<sup>*This is a tips question for golfing in Python, which is on topic for main.*</sup>

I'm looking for the shortest way to get all of the most common elements of a list in Python, in the shortest way possible. Here's what I've tried, assuming the list is in a variable called `l`:

```
from statistics import*
mode(l)

```

This throws an error if there are multiple modes.

```
max(l,key=l.count)

```

This only returns 1 item, I need to get *all* the elements of greatest count.

```
from collections import*
Counter(l).most_common()

```

This returns a list of tuples of `(element, count)`, sorted by count. From this I could pull all the elements whose corresponding count is equal to the first, but I don't see a way to golf this much better than:

```
from collections import*
c=Counter(l).most_common()
[s for s,i in c if i==c[0][1]]

```

I am sure there is a shorter way!

Also, if it can be done without variable assignment or multiple uses of `l`, I can keep the rest of the code as a lambda expression to save more bytes.

Edit: Per @Uriel's suggestion, we can do:

```
{s for s in l if l.count(s)==l.count(max(l,key=l.count))}

```

And I can alias `list.count` for a few bytes:

```
c=l.count;{s for s in l if c(s)==c(max(l,key=c))}

```

@Uriel pointed out that we can get a couple more bytes with `map`:

```
c=l.count;{s for s in l if c(s)==max(map(c,l))}

```

# Answer
> 5 votes
How about this one?

```
c=l.count;{x for x in l if c(x)==max(map(c,l))}

```

Enclose in `[*...]` to get a list.

---
Tags: code-golf, tips, python
---


# Question
Title: Who was the biggest "Weekend Update" host during that time period?
These are the hosts of the "Weekend Update" news segment on *Saturday Night Live*, with the years they hosted and their initials:

```
Chevy Chase         1975-1976  CC
Jane Curtain        1976-1980  JC
Dan Aykroyd         1977-1978  DA
Bill Murray         1978-1980  BM
Charles Rocket      1980-1981  CR
Gail Matthius       1981       GM
Brian Doyle-Murray  1981-1982  BD
Mary Gros           1981-1982  MG
Christine Ebersole  1982       CE
Brad Hall           1982-1984  BH
Christopher Guest   1984-1985  CG
Dennis Miller       1985-1991  DM
Kevin Nealon        1991-1994  KN
Norm MacDonald      1994-1997  NM
Colin Quinn         1998-2000  CQ
Jimmy Fallon        2000-2004  JF
Tina Fey            2000-2006  TF
Amy Poehler         2004-2008  AP
Seth Meyers         2006-2014  SM
Cecily Strong       2013-2014  CS
*Colin Jost         2014-pres  CJ
*Michael Che        2014-pres  MC

*At the time of this writing, present is 2017.

```

I got most of the years this website, but later ones I got from Wikipedia.

The task is simple. Given a range of years, output the initials of the person who was host during the most years in that time period. If there is a tie, output the initials of all the hosts that tied. Note that sometimes "Weekend Update" only has 1 host and sometimes it has 2.

For example, if the input is `1984-1985`, output `CG` because he was the only person to host during both of those years.

# Specifics

* Input is flexible, but it will always consist of a start year and a later end year. Also you don't need to include the first two digits of the year: `95-05` is fine for `1995-2005`.
* Assume all ranges are inclusive: `1982-1984` means `1982,1983,1984`.
* For input, the earliest start year is `1975` and the latest end year is `2017`

# Examples

* `1983-1987` =\> `DM` (he hosted '85,'86,'87\`)
* `1999-2001` =\> `CQ JF TF` \[`CQJFTF` also ok\] (all hosted during two of those years)
* `1975-2017` =\> `SM` (has 9 years!)
* `1990-2000` =\> `KN NM` (both have 4 years)
* `2013-2015` =\> `SM CS CJ MC` (all have 2 years)

# Answer
> 2 votes
# Python 2, 291 bytes

```
def f(b,e):
 s=''.join('A AB BC BCD BD BDE EFGH GHJ J JK KL L L L L L LM M M MN N N N O O OPQ PQ PQ PQ PQR QR QRS RS RS S S S S ST STUV UV UV UV'.split()[b-1975:e-1974]);C=s.count;return''.join({'CJDBCGBMCBCDKNCJTASCCMCCAMRMDGEHGMNMQFFPMSJC'[ord(h)-65::22]for h in s if C(h)==max(map(C,s))})

```

Try it online!

# Answer
> 1 votes
# Python 2, 325 bytes

```
def f(x,y):a=sum([s.split(',')for s in('CC CC,JC JC,DA JC,DA,BM JC,BM JC,BM,CR CR,GM,BD,BD BD,MG,CE,BH BH BH,CG CG,'+'DM '*6+'DM,KN KN KN KN,'+'NM '*4+'CQ CQ CQ,'+'JF,TF '*4+'JF,TF,AP TF,AP TF,AP,SM AP,SM AP,'+'SM '*5+'SM,CS SM,CS,'+'CJ,MC '*4).split()[x-1975:y-1974]],[]);c=a.count;print{s for s in a if c(s)==max(map(c,a))}

```

Try it online!

### 284 bytes, but more boring:

```
def f(x,y):a=sum([s.split(',')for s in'eJx1z9sJwzAUBNFWtoBpwlrZCgrX+NV/LVEiHBxMYDjs79qyqVY1eeiS4j1O8SZvlCDllppR8Eh66BMuciGHbvGcdcYc+ua1R504Jv2RYdFF9tDV3/DexZVov26+ACfwONE='.decode('base64').decode('zip').split()[x-1975:y-1974]],[]);c=a.count;print{s for s in a if c(s)==max(map(c,a))}

```

Try it online!

# Answer
> 1 votes
## JavaScript (ES6), ~~201~~ ~~200~~ 199 bytes

Takes the year range in currying syntax `(a)(b)`. Returns a string made of concatenated initials.

```
a=>b=>"MCCJCSSMAPTFJFCQNMKNDMCGBHCEMGBDGMCRBMDAJCCC".match(/../g).reduce((o,c,n)=>(s=(a<(x-='0017240243612010012111'[n])?x:a)-(b<(y=+'3318464233612011012141'[n]+x)?b:y))>m?o:s<m?(m=s,c):c+o,m=x=2014)

```

### Test cases

```
let f =

a=>b=>"MCCJCSSMAPTFJFCQNMKNDMCGBHCEMGBDGMCRBMDAJCCC".match(/../g).reduce((o,c,n)=>(s=(a<(x-='0017240243612010012111'[n])?x:a)-(b<(y=+'3318464233612011012141'[n]+x)?b:y))>m?o:s<m?(m=s,c):c+o,m=x=2014)

console.log(f(1983)(1987)) // => DM
console.log(f(1999)(2001)) // => CQ JF TF
console.log(f(1975)(2017)) // => SM
console.log(f(1990)(2000)) // => KN NM
console.log(f(2013)(2015)) // => SM CS CJ MC
```

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


title: Smallest chess game compression

text:
# Question
Title: Smallest chess game compression
# Inspiration:

Heavily inspired by Smallest chess board compression I decided to make a similar but distinctly different competition.

# tl;dr

Take the file Chess\_Games.txt and compress it as much as you can so that you can expand it to the original file.

# Objective:

Write an algorithm to encode and decode an entire chess database from start position to end

The encoding must be able to determine for all of the games all the positions:

* The location all the pieces
* Whose turn it is
* Whether the player can castle on each side.
* Whether the player can perform an en-passant, and if so, which of their pawns?
* The previous position

Additionally:

* Each game should also include who won and how it ended (forfeit, draw, checkmate, stalemate, etc...)

# Input/Output:

There should be 2 algorithms Compress/Expand which satisfy the following properties:

* Compress takes in a file of games via a sequence of moves via chess notation and output compressed file
* Expand does the opposite, taking in a compressed file and outputting the original file with all the games in the same order
* Correctness: Expand(Compress(file)) = file for all properly formed files

Any game that is not well formed or violates the rules of chess is considered bad. All bad games may be skipped.

It must be able to parse sen notation. Look at chessgames.com and https://database.lichess.org/ for some examples.

I have compiled a file of the first 10000 games from "May 2017" in Chess\_Games.txt

The file should look like the following:

```
e4 d5 exd5 Nf6 d3 Qxd5 Nc3 Qf5 Be2 Bd7 g4 Qe6 g5 Nd5 Ne4 Bc6 Bg4 Qe5 f4 Qd4 Nf3 Qb6 Qe2 e6 Be3 Qa6 O-O Nd7 c4 Ne7 f5 Bxe4 dxe4 exf5 exf5 O-O-O f6 gxf6 gxf6 Nc6 Nd4 Nxd4 Bxd4 Bc5 Bxc5 Rhg8 Be7 Rde8 b4 Qxf6 Bxf6 Rxe2 h3 h5 Kh1 hxg4 Rg1 Nxf6 Rae1 Rxe1 Rxe1 gxh3 Kh2 Ng4+ Kxh3 Nf2+ Kh2 Ng4+ Kg3 f5 Kf4 Nh6 Re7 Rg4+ Ke5 Kd8 Kf6 Ng8+ Kf7 Nxe7 Kf8 f4 c5 f3 c6 f2 cxb7 Nc6 b8=Q+ Nxb8 Kf7 Kd7 0-1
d3 e6 e3 d5 Nf3 Nf6 Be2 Be7 O-O O-O Nc3 Nbd7 Ne1 c5 f3 e5 e4 d4 Nb1 b6 f4 exf4 Rxf4 Qc7 Rf3 Bd6 g3 Ng4 Rf1 Ndf6 Bxg4 Bxg4 Qd2 Rae8 Qf2 Re5 Bf4 Rh5 Bxd6 Qxd6 Nf3 c4 e5 Rxe5 Nxe5 Qxe5 Nd2 cxd3 cxd3 Be2 Rfe1 Qe3 Qxe3 dxe3 Ne4 Bxd3 Nxf6+ gxf6 Rxe3 Bg6 Rae1 Kg7 h4 h5 R1e2 Bf5 Rg2 Bg4 Re4 Kg6 Rge2 f5 Re5 f6 Re6 Rg8 Re7 Rg7 Re8 1-0
d4 d5 e4 dxe4 c4 Nf6 Qc2 Bf5 Nc3 Qxd4 Be3 Qe5 Nge2 e6 Ng3 Bb4 a3 Bxc3+ bxc3 Nc6 Be2 Na5 O-O Nxc4 Bd4 Qb5 Nxf5 exf5 Bxf6 gxf6 Rab1 Nxa3 Qa2 Qxb1 Rxb1 Nxb1 Qxb1 O-O-O Qb3 b6 Ba6+ Kb8 Qb5 Rhe8 Qc6 1-0
e3 c5 d3 d5 Nf3 Nc6 Be2 Nf6 O-O g6 h3 Bg7 Re1 O-O Nbd2 Re8 Nf1 e5 c3 b6 N3h2 Bb7 Qc2 Qc7 b3 Rac8 Bb2 a5 Rac1 a4 Qb1 axb3 axb3 Ba6 d4 Bxe2 Rxe2 exd4 cxd4 Qb8 dxc5 d4 Ree1 dxe3 Rxe3 Nd5 Rxe8+ Rxe8 Bxg7 Kxg7 Re1 Rxe1 Qxe1 bxc5 Qd1 Nd4 Ne3 Nf4 Neg4 Qxb3 Qe1 Qd5 Ne3 Qe6 Qf1 c4 Nhg4 Nde2+ Kh2 c3 g3 c2 gxf4 c1=Q Qxc1 Nxc1 Ng2 Qe4 Kg3 Nd3 f3 Qe2 Nh4 h5 Nh2 Qe1+ Kg2 Nf2 Nf5+ gxf5 Kg3 Qg1+ Kh4 Nxh3 Kxh5 1-0
e4 d5 exd5 Qxd5 Nc3 Qd8 d4 Bf5 Nf3 e6 Nh4 Bg6 Nxg6 hxg6 Be3 Bd6 Bc4 a6 Qf3 c6 O-O-O Nd7 Ne4 Qc7 Nxd6+ Qxd6 Bf4 Qb4 Bb3 Ngf6 Rhe1 O-O-O Bg3 a5 Qf4 Qb6 Re3 Rh5 Bc4 Rf5 Qd6 Ne8 Qa3 Qa7 Red3 b5 Bxb5 cxb5 Rc3+ Kb7 Qe7 b4 Rc5 Rxc5 dxc5 Qxc5 Qxd8 Ndf6 Qb8+ Ka6 Rd8 Qa7 Rxe8 Nxe8 Qxe8 Qc5 Qa8+ Kb5 Qb8+ Ka4 b3+ Ka3 Qf4 Qc3 Qe5 1-0
e4 d5 exd5 Qxd5 Nf3 Qd8 Nc3 e6 Bc4 Nf6 Bb3 Be7 a3 a6 O-O O-O h3 b6 d3 Bb7 Bg5 Nbd7 Ne4 h6 Bh4 Nxe4 Bxe7 Qxe7 dxe4 Bxe4 Re1 Bb7 Ba2 Nf6 b4 Rfd8 Qc1 Qd6 c4 Qc6 Qc2 Rd7 Rac1 Rad8 c5 bxc5 Qxc5 Qb5 Qxb5 axb5 Ne5 Rd2 Bb3 Rb2 Bd1 Rdd2 Re2 Rxe2 Bxe2 Rxe2 Nf3 Ra2 Rxc7 Bd5 Rc8+ Kh7 Ne5 Rxa3 Rf8 Ra1+ Kh2 h5 Rxf7 Kh6 Rf8 Kg5 g3 Kf5 Nd7 Ra2 Nxf6 gxf6 Rg8 Rxf2+ Kg1 Rg2+ Kf1 Rh2 g4+ hxg4 hxg4+ Ke5 Re8 Rh1+ Kf2 Rh2+ Kg3 Rg2+ Kh4 Rf2 Kg3 Rf4 g5 Re4 gxf6 Kxf6 Rf8+ Ke5 Rh8 Re3+ Kf2 Re4 Rh5+ Kd4 Rh6 Rf4+ Kg3 Re4 Rh8 Re3+ 0-1
...

```

# Scoring:

In order to make things objective, the winner is the algorithm that can compress the files at https://database.lichess.org/ as small as possible. The target database is the "May 2017". The winner is whoever has the smallest file that expands properly.

The file to use is Chess\_Games.txt which is the first 10000 games from the "May 2017" database at https://database.lichess.org/ with all of the header information removed. This file will be the benchmark to use. It should be 2,789,897 bytes with a SHA-256 hash of `56b6d2fffc7644bcd126becd03d859a3cf6880fa01a47fa08d4d6a823a4866bc` (Pastebin might remove the last newline after game 10000)

# Naive Solution:

Using generic compression algorithms:

* zip: 647,772 bytes (76.841%)
* 7z: 652,813 bytes (76.661%)
* bz2: 722,158 bytes (74.182%)
* xz: 784,980 bytes (71.936%)
* rar: 853,482 bytes (69.487%)
* gz: 923,474 bytes (66.985%)

# Answer
# Python, score = 418581 bytes

This uses a bijective variant of asymmetric numeral systems. Because it’s bijective, you can not only compress any valid list of chess games into a file and expand it back to the same list—you can also **expand any file** into a valid list of chess games and compress it back to the same file! Perfect for hiding your porn collection.

Requires python-chess. Run with `python script.py compress` or `python script.py expand`, both of which will read from standard input and write to standard output.

```
import chess
import sys

RESULTS = ['1-0\n', '1/2-1/2\n', '0-1\n', '*\n']
BITS = 24

def get_moves(board):
    if board.is_insufficient_material() or not board.legal_moves:
        return [board.result() + '\n']
    else:
        return RESULTS + sorted(
            board.legal_moves,
            key=lambda move: (move.from_square, move.to_square, move.promotion))

def read_bijective():
    buf = bytearray(getattr(sys.stdin, 'buffer', sys.stdin).read())
    carry = 0
    for i in range(len(buf)):
        carry += buf[i] + 1
        buf[i] = carry & 0xff
        carry >>= 8
    if carry:
        buf.append(carry)
    return buf

def write_bijective(buf):
    carry = 0
    for i in range(len(buf)):
        carry += buf[i] - 1
        buf[i] = carry & 0xff
        carry >>= 8
    while carry:
        carry = (carry << 8) + buf.pop() + 1
    getattr(sys.stdout, 'buffer', sys.stdout).write(buf)

def add_carry(buf, carry):
    for i in range(len(buf)):
        if carry == 0:
            break
        carry += buf[i]
        buf[i] = carry & 0xff
        carry >>= 8
    return carry

def do_compress():
    board = chess.Board()
    state = 0
    buf = bytearray()

    games = []
    for sans in sys.stdin:
        game = []
        for san in sans.split(' '):
            move = san if san in RESULTS else board.parse_san(san)
            moves = get_moves(board)
            game.append((len(moves), moves.index(move)))
            if move in RESULTS:
                board.reset()
            else:
                board.push(move)
        games.append(game)

    for game in reversed(games):
        for (n, i) in reversed(game):
            q = ((1 << BITS) - 1 - i) // n + 1
            while state >= q << 8:
                buf.append(state & 0xff)
                state >>= 8
            hi, j = divmod(state, q)
            lo = n * j + i
            state = hi << BITS | lo
        state += add_carry(buf, 1)

    while state:
        buf.append(state & 0xff)
        state >>= 8
    write_bijective(buf)

def do_expand():
    board = chess.Board()
    state = 0
    buf = read_bijective()

    while True:
        while buf and state < 1 << BITS:
            state = state << 8 | buf.pop()
        if state == 0:
            break
        state += add_carry(buf, -1)

        while True:
            moves = get_moves(board)
            while buf and state < 1 << BITS:
                state = state << 8 | buf.pop()
            n = len(moves)
            hi, lo = divmod(state, 1 << BITS)
            j, i = divmod(lo, n)
            q = ((1 << BITS) - 1 - i) // n + 1
            state = j + q * hi
            move = moves[i]
            if move in RESULTS:
                sys.stdout.write(move)
                board.reset()
                break
            else:
                sys.stdout.write(board.san(move).rstrip('+#') + ' ')
                board.push(move)

if __name__ == '__main__':
    {'compress': do_compress, 'expand': do_expand}[sys.argv[1]]()

```
> 5 votes

# Answer
# Python, score = 426508 bytes

### Compression Function: ( m+1 ) ⋅ log2 ( b+1 )

**m** is number of moves and **b** is branching factor

# Attempt 1:

I answered the question at Smallest chess board compression so I'm trying to fix it up to post here.

Naively I thought that I can encode each move in 12 bits, 4 triplets of the form (start x, start y, end x, end y) where each is 3 bits.

We would assume the starting position and move pieces from there with white going first. The board is arranged such that ( 0 , 0 ) is white's lower left corner.

For example the game:

```
  e4    e5
 Nf3    f6
Nxe5  fxe5
...    ...

```

Would be encoded as:

```
100001 100010 100110 100100
110000 101010 101110 101101
101010 100100 101101 100100
...

```

This leads to an encoding of 12 *m* bits where *m* is the number of moves made.

# Attempt 2:

I realized that each move in the previous attempt encodes many illegal moves. So I decided to only encode legal moves. We enumerate possible moves as follows, number each square such that ( 0 , 0 ) → 0 , ( 1 , 0 ) → 1 , ( x , y ) → x \+ 8 y . Iterate through the tiles and check if a piece is there and if it can move. If so add the positions it can go to to a list. Choose the list index that is the move you want to make. Add that number to the running total of moves weighted by 1 plus the number of possible moves.

Example as above: From the starting position the first piece that can move is the knight on square 1, it can move to square 16 or 18, so add those to the list `[(1,16),(1,18)]`. Next is the knight on square 6, add it's moves. Overall we get:

`[(1,16),(1,18),(6,21),(6,23),(8,16),(8,24),(9,17),(9,25),(10,18),(10,26),(11,19),(11,27),(12,20),(12,28),(13,21),(13,29),(14,22),(14,30),(15,23),(15,31)]`

Since we want the move ( 12 , 28 ) , we encode this as 13 in base 20 since there are 20 possible moves.

So now we get the game number g0 = 13

Next we do the same for black except we number the tiles in reverse (to make it easier, not required) to get the list of moves:

`[(1,16),(1,18),(6,21),(6,23),(8,16),(8,24),(9,17),(9,25),(10,18),(10,26),(11,19),(11,27),(12,20),(12,28),(13,21),(13,29),(14,22),(14,30),(15,23),(15,31)]`

Since we want the move ( 11 , 27 ) , we encode this as 11 in base 20 since there are 20 possible moves.

So now we get the game number g1 = ( 11 ⋅ 20 ) \+ 13 = 233

Next we get the following list of moves for white:

`[(1,16),(1,18),(3,12),(3,21),(3,30),(3,39),(4,12),(5,12),(5,19),(5,26),(5,33),(5,40),(6,12),(6,21),(6,23),(8,16),(8,24),(9,17),(9,25),(10,18),(10,26),(11,19),(11,27)(13,21),(13,29),(14,22),(14,30),(15,23),(15,31)]`

Since we want the move ( 6 , 21 ) , we encode this as 13 in base 29 since there are 29 possible moves.

So now we get the game number g2 = ( ( 13 ⋅ 20 ) \+ 11 ) 20 \+ 13 = 5433

Next we get the following list of moves for black: `[(1,11),(1,16),(1,18),(2,11),(2,20),(2,29),(2,38),(2,47),(3,11),(4,11),(4,18),(4,25),(4,32),(6,21),(6,23),(8,16),(8,24),(9,17),(9,25),(10,18),(10,26),(12,20),(12,28),(13,21),(13,29),(14,22),(14,30),(15,23),(15,31)]`

Since we want the move ( 10 , 18 ) , we encode this as 19 in base 29 since there are 29 possible moves.

So now we get the game number g3 = ( ( ( 19 ⋅ 29 \+ 13 ) 20 ) \+ 11 ) 20 \+ 13 = 225833

And continue this process for all the remaining moves. You can think of *g* as the function g ( x , y , z ) = x y \+ z . Thus g0 = g ( 1 , 1 , 13 ) , g1 = g ( g ( 1 , 1 , 11 ) , 20 , 13 ) , g2 = g ( g ( g ( 1 , 1 , 13 ) , 20 , 11 ) , 20 , 13 ) , g3 = g ( g ( g ( g ( 1 , 1 , 19 ) , 29 , 13 ) , 20 , 11 ) , 20 , 13 )

To decode a game number *g*0, we start at the initial position and enumerate all possible moves. Then we compute *g*1 = *g*0 // *l*, *m*0 = *g*0 % *l*, where *l* is the number of possible moves, '//' is the integer division operator and '%' is the modulus operator. It should hold that *g*0 = *g*1 \+ *m*0. Next we make the move *m*0 and repeat.

From the example above if *g*0 = 225833 then *g*1 = 225833 // 20 = 11291 and *m*0 = 225833 % 20= 13. Next *g*2 = 11291 // 20 = 564 and *m*1 = 11291 % 20 = 11. Then *g*3 = 11291 // 20 = 564 and *m*2 = 11291 % 20 = 11. Therefore *g*4 = 564 // 29 = 19 and\_m\_3 = 564 % 29 = 13. Finally *g*5= 19 // 29 = 0 and *m*4 = 19 % 29 = 19.

# So how many bits are used to encode a game this way?

For simplicity, let's say there are always 35 moves each turn (https://en.wikipedia.org/wiki/Branching\_factor) and for the worst case scenario we always pick the biggest one, 34. The number we will get is 34 ⋅ 35m \+ 34 ⋅ 35m-1 \+ 34 ⋅ 35m-2 \+ ⋯ \+ 34 ⋅ 35 \+ 34 = 35m+1 − 1 where \_m is the number of moves. To encode 35m+1 − 1 we need about log2 ( 35m+1 ) bits which is about ( m \+ 1 ) ⋅ log2 ( 35 ) = 5.129 ⋅ ( m \+ 1 )

On average *m* = 80 (40 moves per player) so this would take 416 bits to encode. If we were recording many games we would need a universal encoding since we don't know how many bits each number will need

Worst case when *m* = 11741 so this would take 60229 bits to encode.

# Additional Notes:

Note that *g* = 0 denotes a valid game, the one where the piece on the lowest square moves to the lowest square it can.

If you want to refer to a specific position in the game you may need to encode the index. This can be added either manually e.g concatenate the index to the game, or add an additional "end" move as the last possible move each turn. This can now account for players conceding, or 2 in a row to denote the players agreed to a draw. This is only necessary if the game did not end in a checkmate or stalemate based on the position, in this case it is implied. In this case it brings the number of bits needed on average to 419 and in the worst case 60706.

A way to handle forks in a what-if scenario is to encode the game up to the fork and then encode each branch starting at the forked position instead of the initial position.

# Implementation:

Take a look at my github repo for the code: https://github.com/edggy/ChessCompress
> 3 votes

---
Tags: code-challenge, chess, compression
---


# Question
Title: Setup the tribal totem for the requested weather
There is a Sioux village. It has a totem:

```
             __
         ___|  |___
   \/    \        /    \/
   /\     ``|  |``     /\
  /^^\      |  |      /^^\
 / /\ \     |  |     / /\ \
''''''''''''''''''''''''''''

```

The totem lets the Sioux mastering the weather for helping in their different tasks. Help the villagers properly decorating the totem for invoking the adequate weather. The totem has several parts:

```
             __
         ___|AA|___
   \/    \BBBBBBBB/    \/
   /\     ``|CC|``     /\
  /^^\      |DD|      /^^\
 / /\ \  13 |EE| 42  / /\ \
''''''''''''''''''''''''''''

```
* `A` is for *sun* `()` or *clouds* `ww`
* `B` is for *rain* `""""""""` or *snow* `::::::::`
* `C` is for *thunderstorm* `zz`
* `D` is for *wind* `~~`
* `E` is for *fog* `==`

But that's not all. The totem needs weather dancers. The more elements are invoked, the higher the number of required dancers is. If there is one element invoked, a dancer is needed. Two elements, two dancers. Beyond four elements, there will always be at most four dancers. If there is no element invoked, no dancers are needed. The totem needs to rest.

The weather dancers must appear in the order `1234`. For instance if there are two dancers, the slots `1` and `2` must be occupied. Moreover, each dancer performs a different figure:

* `1` is `T`
* `2` is `Y`
* `3` is `K`
* `4` is `X`

Now, the villagers will express their weather wishes. They will pronounce a sentence containing the weather element(s) they would like to have. Setup the totem and the dancers for fulfilling their wishes.

**Challenge**

Write a program which takes a string as input, matches the elements in the sentence (*sun*, *rain*, …), and outputs the full village with the totem properly set and its dancers. Your program does not have to check the correctness of the input string (e.g. it won't contain both *sun* and *clouds*). It must matches **words** (in the literal sense):

* The input string `X says: "I like the wind, it blows the worries away"` matches *wind*, because the comma is not part of the word
* The input string `Y says: "I hope the weather won't get too windy"` does not match *wind*, because *windy* and *wind* are two different words

The word(s) to match are guaranteed to be in the quoted part of the input string (the first part designating who is talking will never contain a word that could be matched).

**Examples**

```
The squaw says: "I want sun and wind for drying the clothes"
             __
         ___|()|___
   \/    \        /    \/
   /\     ``|  |``     /\
  /^^\      |~~|      /^^\
 / /\ \  T  |  |  Y  / /\ \
''''''''''''''''''''''''''''

```

```
The warrior thinks: "A good thunderstorm will afraid the invaders. Or a snow storm. Or an impenetrable fog. Or an oppressive sun."
             __
         ___|()|___
   \/    \::::::::/    \/
   /\     ``|zz|``     /\
  /^^\      |  |      /^^\
 / /\ \  TK |==| XY  / /\ \
''''''''''''''''''''''''''''

```

```
The papoose shouts: "I WANNA GO OUTSIDE PLAY UNDER THE SUN!"
             __
         ___|()|___
   \/    \        /    \/
   /\     ``|  |``     /\
  /^^\      |  |      /^^\
 / /\ \  T  |  |     / /\ \
''''''''''''''''''''''''''''

```

```
The wise grandma whispers: "The totem is an illusion"
             __
         ___|  |___
   \/    \        /    \/
   /\     ``|  |``     /\
  /^^\      |  |      /^^\
 / /\ \     |  |     / /\ \
''''''''''''''''''''''''''''

```

```
The shaman confides: "I perform my magic hidden in the fog, under the rain or at least under heavy clouds"
             __
         ___|ww|___
   \/    \""""""""/    \/
   /\     ``|  |``     /\
  /^^\      |  |      /^^\
 / /\ \  TK |==|  Y  / /\ \
''''''''''''''''''''''''''''

```

```
The village chief claims: "The meat of bison is better preserved in the snow, or dried under a burning sun. My Pa' used to say that heavy wind and a thunderstorm could help too, but I have no clue how. And despite everyone contradicting me, I am persuaded a good fog will do as well"
             __
         ___|()|___
   \/    \::::::::/    \/
   /\     ``|zz|``     /\
  /^^\      |~~|      /^^\
 / /\ \  TK |==| XY  / /\ \
''''''''''''''''''''''''''''

```

This is so the shortest answer in bytes win. Explanations are encouraged.

# Answer
> 2 votes
# Python, <sub>~~527~~ ~~524~~ ~~508~~ ~~504~~ ~~481~~ ~~474~~ ~~462~~</sub> 461 bytes

```
from re import*
a=r"""!!! __
!! ___|AA|___
   \/!\BBBBBBBB/!\/
   /\! ``|CC|``! /\
  /^^\!  |DD|!  /^^\
 / /\ \  02 |EE| 31  / /\ \
""";s={'sun':'A2()','clouds':'A2w','rain':'B2"','snow':'B2:','thunderstorm':'C2z','wind':'D2~','fog':'E2='};i=0
for y in[w for w in split('\W+',input().lower())if w in s]:i+=1;z=s[y];w=int(z[1]);a=sub(z[0]*w,(z[2:]*w)[:w],a)
for y in range(min(i,4)):a=sub(str(y),'TYKX'[y],a)
print(sub('!',' '*4,sub('[ABCDE0123]',' ',a))+"'"*28)

```

Try it online!

# Answer
> 2 votes
# Python 3, ~~473~~ ~~464~~ 460 bytes

```
import re
x=re.split('\W+',input().lower())
L='sun clouds rain snow thunderstorm wind fog'.split()
q=sum(map(x.count,L))
print(r'''!    __
!___|#|___
" \/"  \$/" \/
" /\"   ``|%%|``"  /\
  /^^\""  |&&|"" /^^\
 / /\ \  13 |''| 42 / /\ \
'''.translate({33:' '*9,34:' '*2,35:' (w )w'[(L[0]in x)+2*(L[1]in x)::3],36:' ":'[(L[2]in x)+2*(L[3]in x)]*8,37:' z'[L[4]in x],38:' ~'[L[5]in x],39:' ='[L[6]in x],49:' T'[q>0],50:' Y'[q>1],51:' K'[q>2],52:' X'[q>3]})+"'"*28)

```

Try it online!

-9 bytes
-4 bytes thanks to ovs

# Answer
> 1 votes
# JavaScript (ES6), 417 bytes

```
(s,i=x=>s.toLowerCase()[q](/\W+/).includes(x[0]),g=x=>y=>i(x)?y[0]:(j--,"  "),j=4,t="||   \\/|   /\\|  /^^\\| / /\\ \\"[q="split"]`|`.map(x=>x[p="padEnd"](9)))=>`    __    n___|${i`sun`?"()":g`clouds``ww`}|___n${"\\"[p](9,i`rain`?'"':g`snow``:`)}/n \`\`|${g`thunderstorm``zz`}|\`\` n   |${g`wind``~~`}|   n02 |${g`fog``==`}| 31`.replace(/\d/g,m=>m>j?" ":"TYKX"[m])[q]`n`.map((v,k)=>t[k]+v+t[k]).join`
`+`
`[p](28,"'")

```

The idea here was to generate the totem pole first, then add the mirrored tikis on both sides of it.

Includes two helper functions: `i`, which checks if a string is one of the words in the input; and `g`, which does `i` and returns the given string or `" "`. `g` also counts how many elements are missing to be used for the dancers at the bottom.

## Test Snippet

```
let f=
(s,i=x=>s.toLowerCase()[q](/\W+/).includes(x[0]),g=x=>y=>i(x)?y[0]:(j--,"  "),j=4,t="||   \\/|   /\\|  /^^\\| / /\\ \\"[q="split"]`|`.map(x=>x[p="padEnd"](9)))=>`    __    n___|${i`sun`?"()":g`clouds``ww`}|___n${"\\"[p](9,i`rain`?'"':g`snow``:`)}/n \`\`|${g`thunderstorm``zz`}|\`\` n   |${g`wind``~~`}|   n02 |${g`fog``==`}| 31`.replace(/\d/g,m=>m>j?" ":"TYKX"[m])[q]`n`.map((v,k)=>t[k]+v+t[k]).join`
`+`
`[p](28,"'")

let tests = [`The squaw says: "I want sun and wind for drying the clothes"`,`The warrior thinks: "A good thunderstorm will afraid the invaders. Or a snow storm. Or an impenetrable fog. Or an oppressive sun."`,`The papoose shouts: "I WANNA GO OUTSIDE PLAY UNDER THE SUN!"`,`The wise grandma whispers: "The totem is an illusion"`,`The shaman confides: "I perform my magic hidden in the fog, under the rain or at least under heavy clouds"`,`The village chief claims: "The meat of bison is better preserved in the snow, or dried under a burning sun. My Pa' used to say that heavy wind and a thunderstorm could help too, but I have no clue how. And despite everyone contradicting me, I am persuaded a good fog will do as well"`];I.innerHTML+=tests.map(t=>"<option>"+t).join``
```

```
<select id=I oninput="O.innerHTML=(idx=I.selectedIndex)?(t=tests[idx-1])+'\n\n'+f(t):''" style="width:90vw"><option>---Tests---</select>
<pre id=O></pre>
```

---
Tags: code-golf, ascii-art
---