# Question
Title: The cyclic sequence of even digits, with odds in between
Consider the following sequence:

```
1, 0, 1, 2, 4, 1, 6, 8, 0, 1, 2, 4, 6, 8, 1, 0, 2, 4, 6, 8, 1, 0, 2, 4, 6, 8, 0, 1, ...

```

The even digits start from **0** and are grouped into runs of increasing length. They are arranged cyclically, meaning that they are sorted in ascending order until **8** is reached, and then cycled back from **0**. **1** separates the runs of even digits, and it also starts the sequence. Let's visualize how this sequence is formed:

```
                 1, 0, 1, 2, 4, 1, 6, 8, 0, 1, 2, 4, 6, 8, 1, 0, 2, 4, 6, 8, 1,  ...

                    -     ----     -------     ----------     -------------
run length:         1      2          3            4                5            ...
position of 1:   X     X        X           X              X                 X   ...
even sequence:      0,    2, 4,    6, 8, 0,    2, 4, 6, 8,    0, 2, 4, 6, 8      ...

```

---

Acceptable Input and Output methods:

* Receive an integer **N** as input and output the **N**th term of this sequence.
* Receive an integer **N** as input and output the first **N** terms of this sequence.
* Print the sequence indefinitely.

You can choose either 0 or 1-indexing for the first two methods.

You can compete in any programming language, while using the standard input and output methods. Standard loopholes are forbidden. This is , so the shortest code in each language wins.

# Answer
# Haskell, ~~50~~ 46 bytes

```
1#cycle[0,2..8]
n#r=1:take n r++(n+1)#drop n r

```

Try it online!

`1#cycle[0,2..8]` returns the sequence as infinite list.

*-4 bytes thanks to Ørjan Johansen!*
> 8 votes

# Answer
## Husk, ~~12~~ ~~11~~ 10 bytes

```
ṁ:1CN¢mDŀ5

```

Try it online!

Prints the sequence indefinitely.

Alternatively:

```
J1CΘN¢mDŀ5

```

Try it online!

### Explanation

```
        ŀ5   Start from [0, 1, 2, 3, 4]
      mD     Double each value to get [0, 2, 4, 6, 8]
     ¢       Repeat this list indefinitely, [0, 2, 4, 6, 8, 0, 2, ...]
   CN        Cut it into chunks of increasing lengths,
             [[0], [2, 4], [6, 8, 0], ...]
ṁ:1          Prepend 1 to each sublist and concate the resulting lists.

```

For the alternative solution:

```
     ¢mDŀ5   Again, get [0, 2, 4, 6, 8, 0, 2, ...].
  CΘN        This time we prepend a zero to the natural numbers, which
             prepends an empty list to the resulting chunks.
J1           Join all the sublists with 1.

```

We could also do `...ΘCN...`, because `Θ` does "prepend default element", which prepends a zero for lists of integers and an empty list for lists of lists.
> 7 votes

# Answer
# Jelly, 10 bytes

```
5ḶḤṁR€1pFḣ

```

Returns the first **n** items of the sequence.

Try it online!

### How it works

```
5ḶḤṁR€1pFḣ  Main libk. Argument: n

5           Set the return value to 5.
 Ḷ          Unlength; yield [0, 1, 2, 3, 4].
  Ḥ         Unhalve; yield [0, 2, 4, 6, 8].
    R€      Range each; yield [[1], [1, 2], [1, 2, 3], ..., [1, ..., n]].
   ṁ        Mold; in the result to the left, replace [1] with [0], [1, 2] with
            [2, 4], [1, 2, 3] with [6, 8, 0], and so forth.
      1p    Take the Cartesian product of [1] and the result.
        F   Flatten the result.
         ḣ  Head; take the first n items of the result.

```
> 7 votes

# Answer
# Python 3, 52 bytes

```
def f(n):t=(8*n+1)**.5+1;return 0==t%1or(n-t//2)%5*2

```

Takes a 1-based index and returns *True* or an integral *float*.

Try it online!
> 4 votes

# Answer
# APL (Dyalog Unicode), ~~52~~ ~~59~~ 56 bytes

```
r←c k
r←~n←0
:For j :In ⍳k
n+←j-1
r,←1,⍨j⍴n⌽0,2×⍳4
:End
r←k⍴r

```

Try it online!

This is a tradfn (**trad**itional **f**unctio**n**) taking one argument `k` and returning the first `k` items of the sequence.

Thanks to @GalenIvanov for pointing out an error in the function. Thanks to @Adám for 3 bytes.

### How it works:

```
r←c k             ⍝ The function c takes the argument k and results in r
r n←1 0           ⍝ Initializing the variables r and n, and setting them to 1 and 0, respectively.
:For j :In ⍳k     ⍝ For loop. ⍳k yields [1, 2, 3, ..., k], and j is the control variable.
n+←j-1            ⍝ Accumulates j-1 into n, so it follows the progression (0, 1, 3, 6, 10, 15...)
r,←1,⍨j⍴n⌽0,2×⍳4  ⍝ This line is explained below.
:End              ⍝ Ends the loop
r←k⍴r             ⍝ return the first k items of r.
                  ⍝ ⍴ actually reshapes the vector r to the shape of k;
                  ⍝ since k is a scalar, ⍴ reshapes r to a vector with k items.
            2×⍳4  ⍝ APL is 1-indexed by default, so this yields the vector 2 4 6 8
          0,      ⍝ Prepend a 0 to it. We now have 0 2 4 6 8
        n⌽        ⍝ Rotate the vector n times to the left.
      j⍴          ⍝ Reshape it to have j items, which cycles the vector.
   1,⍨            ⍝ Append a 1, then
r,←               ⍝ Append everything to r.

```

Below are a `Dfn`(**d**irect **f**unctio**n**) and a tacit function that also solve the challenge, both kindly provided by @Adám.

* Dfn: `{⍵⍴1,∊1,⍨¨j⍴¨(+\¯1+j←⍳⍵)⌽¨⊂0,2×⍳4}` Try it online!
* Tacit: `⊢⍴1,∘∊1,⍨¨⍳⍴¨(⊂0,2×⍳4)⌽⍨¨(+\¯1+⍳)` Try it online!
> 2 votes

# Answer
# Python 2, 51 bytes

```
k=n=0
while 1:print 1;k+=1;exec'print n%10;n+=2;'*k

```

Prints the whole sequence.

Try it online!
> 2 votes

# Answer
# APL, 25 bytes

Returns nth term.

```
1,(⌽n↑⌽(+/⍳n←⎕)⍴0,2×⍳4),1

```

Explanation

```
n←⎕     Prompts for screen input of integer
+/⍳      Creates a vector of integers of 1 to n and sums
⍴0,2×⍳4  Creates a vector by replicating 0 2 4 6 8 to the length of sum
⌽n↑⌽   Rotates the vector, selects first n elements and rotates result
        (selects last n elements}
1,...,1 Concatenates 1s in front and behind result

```
> 2 votes

# Answer
# JavaScript (ES6), ~~62~~ ~~54~~ 52 bytes

Returns the **N**th term of the sequence, 0-indexed.

```
n=>(g=e=>n--?g(e+=k++<l?2:k=!++l):k<l?e%10:1)(k=l=0)

```

### Demo

```
let f =

n=>(g=e=>n--?g(e+=k++<l?2:k=!++l):k<l?e%10:1)(k=l=0)

for(n = 0; n < 30; n++) {
  console.log('a(' + n + ') = ' + f(n))
}
```
> 1 votes

# Answer
# C (gcc), 84 bytes

```
i;j;f(){for(i=1;;i++){printf("%d ",1);for(j=0;j<i;)printf("%d ",(2*j+++i*i-i)%10);}}

```

Try it online!

A function (`f()`) that prints the sequence infinitely, separated by spaces.

`i` is the length of the current even-run.

`j` is the index in the current even-run

`(2*j+++i*i-i)%10` gives the correct even number, given i and j (and increments j), equivalent to ((j+Tr(i))%5)\*2, where Tr(x) is the xth triangular number (which is the number of even numbers that have been printed before the current even run;
> 1 votes

# Answer
# Java 8, 96 bytes

```
v->{for(int i=0,j=-2,k;;i++,System.out.println(1))for(k=0;k++<i;System.out.println(j%=10))j+=2;}

```

Prints indefinitely, each number on a new line.

**Explanation:**

Try it here.

```
v->{                               // Method with empty unused parameter and no return-type
  for(int i=0,                     //  Index integer, starting at 1
          j=-2,                    //  Even index integer, starting at -2
          k;                       //  Inner index integer
      ;                            //  Loop (1) indefinitely
                                   //    After every iteration:
       i++,                        //     Increase index `i` by 1
       System.out.println(1))      //     And print a 1
    for(k=0;                       //   Reset index `k` to 0
        k++<i;                     //   Inner loop (2) from 0 to `i`
                                   //     After every iteration:
       System.out.println(j%=10))  //      Set `j` to `j` modulo-10, and print it
      j+=2;                        //    Increase `j` by 2
                                   //   End of inner loop (2) (implicit / single-line body)
                                   //  End of loop (1) (implicit / single-line body)
}                                  // End of method

```
> 1 votes

# Answer
## Batch, 85 bytes

```
@set/an=%2+1,t=n*-~n/2
@if %t% lss %1 %0 %1 %n%
@cmd/cset/a(%1-n)%%5*2*!!(t-=%1)+!t

```

Outputs the Nth term of the sequence. Works by calculating the next triangular number.
> 1 votes

# Answer
# , 46 42 40 bytes

-6 bytes thanks to cole

```
{.({.[:;[:#:&.>2^i.);@(1,&.><;.1)10|2*i.

```

Outputs the first N terms of this sequence.

How it works:

`10|[:+:i.` \- generates a list of length N of 0 2 4 6 8 0 2 4... It simply takes mod 10 of the doubled items of a list of integers starting at 0.

`[:;[:#:&.>2^i.` \- generates a bit mask for cutting the above list.

(1 means start): 1 1 0 1 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 ... It finds 2 to the power of the consecutive non-negative integers, converts them into binary, flattens the list and takes only the first N items, so that the length of the both lists is the same.

`;@(1,&.><;.1)` \- splits (cuts) the list of the even digits into sublistsaccording to the map of ones and zeroes, appends the sublist to 1 and finally flattens the resulting list

`]{.` \- takes only the first N items, getting rid of the additional numbers in the list due to the added 1s.

Try it online!
> 1 votes

# Answer
# Perl 5, 44 bytes

```
do{say 1;map{say(($r+=2)%10)}0..$i++}while 1

```

Try it online!

Infinite output
> 1 votes

# Answer
# Common Lisp, 74 bytes

```
(do((b 1(1+ b))(k -2))(())(print 1)(dotimes(m b)(print(mod(incf k 2)10))))

```

Try it online!

Prints the sequence indefinitely.
> 1 votes

# Answer
# Perl 5, 35 bytes

```
{say$i--?$r++%5*2:($i=++$j)>0;redo}

```

try it online
> 1 votes

# Answer
# Jelly, 17 bytes

```
9Ḷm2ẋ⁸ṁJR$$j1 1;ḣ

```

Try it online!
> 0 votes

# Answer
# Proton, 55 bytes

```
i=0 j=-2while1{for k:0..i print(j=(j+2)%10)print(1)i++}

```

Try it online!

Prints the sequence indefinitely
> 0 votes

# Answer
# Java (OpenJDK 8), 107 bytes

```
i->{String b="";for(int l=i,r=0,z=0;i>0;b+=l-i--==r?(l=i)<1+r++*0?"1":"1":"02468".charAt(z++%5));return b;}

```

Try it online!
> 0 votes

# Answer
# Mathematica, 68 bytes

Returns the Nth term

```
Insert[Join@@Table[{0,2,4,6,8},#^2],1,Array[{(2-#+#^2)/2}&,#]][[#]]&

```

Try it online!
> 0 votes

# Answer
## Wolfram Language (Mathematica), 61 bytes

```
Flatten[TakeList[2Mod[r=0~Range~#,5],UpTo/@r]~Riffle~1][[#]]&

```

Try it online!
> 0 votes

# Answer
# JavaScript, 45 bytes

1 indexed:

```
f=(x,t=0,p=0)=>p<x?f(x-1,t+1,p+t):x-p?x%5*2:1

```

0 indexed:

```
g=(x,p=0)=>p<x?g(x-1,p?++t+p:t=1):x-p?x%5*2:1

```

```
    f=(x,t=0,p=0)=>p<x?f(x-1,t+1,p+t):x-p?x%5*2:1

g=(x,p=0)=>p<x?g(x-1,p?++t+p:t=1):x-p?x%5*2:1

a.value=[...Array(100)].map((_,i)=>f(i+1))
b.value=[...Array(100)].map((_,i)=>g(i))
```

```
<output id=a></output>
<output id=b></output>
```
> 0 votes

# Answer
# Ruby, ~~48~~ 46 bytes

```
a=b=c=0;loop{a>b&&(p 2*b%10;b+=1)||a+=c+=p(1)}

```

Try it online!

Print the sequence indefinitely
> 0 votes

# Answer
# bash, 42 bytes

```
for((;;)){ echo $[i--?r++%5*2:(i=++j)>0];}

```

or 34 if valid

```
echo $[i--?r++%5*2:(i=++j)>0];. $0

```

try it online
> 0 votes

# Answer
# Pip, 15 bytes

```
W P1L UiP2*Uv%t

```

Prints indefinitely. Try it here! Or, here's a 16-byte equivalent in Pip Classic: Try it online!

### Explanation

```
W                While this expression is truthy--
  P1             print 1 (evaluates to 1, which is truthy)
                 --loop:
      Ui          Increment i (initially 0)
    L             and loop that many times:
           Uv      Increment v (initially -1)
         2*        Multiply by 2
             %t    Mod 10
        P          Print

```
> 0 votes

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


title: Restricted Polyglot

text:
# Question
Title: Restricted Polyglot
Polyglots are programs that are valid in multiple programming languages simultaneously. Most such polyglots are written in such a way that certain constructs of one language are interpreted as comments of another language (e.g. `#define` in C being interpreted as a comment in several scripting languages).

I am curious to see if it is possible to make a non-trivial polyglot which contains no comments, but also immediately changes when you remove any non-whitespace character, I therefore challenge you to come up with such a program.

The concrete rules are as follows:

1. (Output). Your program must produce some output on the console under each of your languages. That is, your program is not permitted to simply exit without printing anything.
2. (Variance). As a relaxation of the standard polyglot definition, the program's output may vary between languages.
3. (Errors). Your program must not produce any errors (broadly defined) under any of your languages. For most languages, this is defined as returning a non-zero exit code from the compiler and/or interpreter.
4. (Restriction). The removal of any single non-whitespace character from your code should cause your program to change its behaviour under *every* one of your languages. The program may "change" by becoming invalid for that language, or by changing the output that is produced.
5. This is a *code challenge*. Winner is the program which is valid in the most programming languages. Ties will be broken in favor of shorter program length.

The restriction rule doesn't apply to the removal of several characters. That is, it is fine if removing several characters simultaneously results in no change for one of your languages.

Observe that the restriction rule implies that you cannot use Whitespace as one of your languages, as removing any non-whitespace character won't change the behaviour of the Whitespace program.

Here's a simple example of a program that fulfills all the above restrictions, for the languages Python 2 and Python 3:

```
print("Hello World!")

```

Removing any character in `print` will cause both languages to throw a `NameError`; removing any bracket or quote will throw a `SyntaxError`, and removing any of the string characters will change the output in both languages. (Note that `print("hello", "world")` is a more subtle, but still valid program under the above rules).

This example is a bit lame because Python 2 and Python 3 are very similar, so I won't accept any other solutions that only use different versions of the same language (especially Python 2 and Python 3).

# Answer
> 13 votes
# Bash + GolfScript + CJam

```
"echo" []
{ cat<&3;} \
3<""<("echo" 'p'~)

```

### Output

Bash:

```
[]
p~

```

GolfScript:

```
"echo"
echo{ cat<&3;}0

```

CJam:

```
echo{ cat<&3;}-1echop

```

There is a `\x7f` in the end of output of CJam.

# Answer
> 9 votes
# Bash + Befunge

```
"echo" $,$,"ol":,,,@

```

prints 'hello' in befunge.

# Answer
> 7 votes
# GolfScript + PHP + CJam + Mathematica + bc + Pyth + /// \+ TI-Basic + R + Octave + Matlab + Scilab + Numeric Topline \+ ?Fueue \+ huh?

```
10

```

In Golscript, PHP, CJam, Mathematica, bc, Pyth, ///, and TI-Basic, it outputs `10`.

In R, it outputs `[1] 10`

In Octave, it outputs `ans = 10`

In Matlab and Scilab, it outputs `ans = 10`.

In Numeric Topline, it outputs `0`.

If I understand Fueue properly, it outputs a newline, then acts as a cat program.

In huh?, it outputs

```
What?
?

```

# Answer
> 7 votes
# bc, GolfScript, Homespring, huh, Octave, Scilab (0 bytes)

Guaranteed to comply with rule 4. Not a winner, but would do well in the tie break.

### Output

bc

```
Copyright 1991-1994, 1997, 1998, 2000, 2004, 2006 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'.

```

GolfScript

```

```

Homespring

```
In Homespring, the null program is not a quine.

```

huh

```
?

```

Octave

```
GNU Octave, version 3.6.4
Copyright (C) 2013 John W. Eaton and others.
This is free software; see the source code for copying conditions.
There is ABSOLUTELY NO WARRANTY; not even for MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  For details, type `warranty'.

Octave was configured for "x86_64-redhat-linux-gnu".

Additional information about Octave is available at http://www.octave.org.

Please contribute if you find this software useful.
For more information, visit http://www.octave.org/get-involved.html

Read http://www.octave.org/bugs.html to learn how to submit bug reports.

For information about changes from previous versions, type `news'.

```

Scilab

```
Startup execution:
  loading initial environment

-->

```

# Answer
> 3 votes
> Seems like this answer is not fully correct.
> I partially fixed it, and going to improve the other part in a few days.

# C++ & Javascript

## The idea is:

```
void eval(bool="main=function(){alert('Hi from Javascript!')};puts=function(){};int=0");
int
main()
{
puts("Hi from C++!");
}

```

C++: http://codepad.org/SK2wbIDL
Javascript: Just copy code to the browser console

## And a set of fixes to make it satisfy

> (Restriction). The removal of any single non-whitespace character from your code should cause your program to change its behaviour under every one of your languages. The program may "change" by becoming invalid for that language, or by changing the output that is produced.

### From Javascript side:

Changing `int`, `main` or `puts` will crash with reading of undeclared variable. But `bool` and `Hi from C++!` can be safely changes. Let's fix it:

```
puts=function(){}

```

```
puts=function(s){s=='Hi from C++!'?bool:nope}

```

If strings are equal, it checks existance of `bool`, otherwice it crashes with undeclared `nope`.

Now, there are 2 trailing semicolons that can be removed. The first is fixed esyly - just remove newline before `int`:

```
void eval(bool="main=function(){alert('Hi from Javascript!')};puts=function(){};int=0");int

```

The second is before `}`, so I need some constriction, valid in both languages and not requiring semicolon at the end in C++ or forsing a semicolon in js. Fine:

```
while(0);

```

It's impossible to omit semicolon in js as `while` needs the body.

So the program at the moment is:

```
void eval(bool="main=function(){alert('Hi from Javascript!')};puts=function(s){s=='Hi from C++!'?bool:nope};int=0");int
main()
{
puts("Hi from C++!");while(0);
}

```

### From C++ side:

There are 2 problems: `eval` can have any name and all js code can be changed.

*I'll try to fix them in a few days.*

# Answer
> 2 votes
# CJam + Golfscript

Okay, this is somewhat boring, but it's a start.

```
1,

```

Prints "0" in both languages. Removal of the `1` causes an error, removing the `,` prints "1" instead.

The same can be done with `1)` or `1(`. There are many alternatives.

(Yes, I know this isn't code-golf)

# Answer
> 2 votes
# C and C++

```
#include <stdio.h>
int main() { puts("Hello!"); return 0; }

```

C and C++ are different languages that are almost compatible with each other - contrary to what you might hear C++ is not a superset of C. Look at http://en.wikipedia.org/wiki/Compatibility\_of\_C\_and\_C%2B%2B for some differences. The example above is not idiomatic C++ but it does work and produces the same output in both C and C++.

# Answer
> 2 votes
## JavaScipt, Lua, R and Python 3 - 24 bytes

May work on some other languages, I'll test latter.

```
alert=print;alert(1)

```

JavaScript was tested on Firefox's console and the other languages here, here and here

# Answer
> 1 votes
## Perl + Ruby + Python

I think in PHP this would need a semicolon if you are running with `-R`.

```
print "Hello World!"

```

# Answer
> 1 votes
# Bash + sh + zsh + ksh, 4 bytes:

```
echo

```

Really simple and satisfies every rule:

1. Outputs a newline in each of the languages.
2. Output currently does *not* vary in any way between the languages.
3. Does not produce an error in any of the languages...
4. ...*except* when any of the characters are removed/changed.

# Answer
> 0 votes
# Bash + sh + zsh + ksh + Windows Batch, 4 bytes:

```
echo

```

Really simple and satisfies every rule:

Outputs a newline which doesn't vary in each of the languages (but Windows Batch, which outputs `ECHO is on`, on the language you use), doesn't error, except when any letter is removed or changed.

# Answer
> 0 votes
# Every single flavor of HQ9+, 1 byte

```
9

```

Including but not limited to HQ9+, FishQ9+, BrainfishQ9+, CHIQRSX9+, Unified HQ9+, H9+, HQ9++,HQ9+-, FHQ9+-, HQ9F+, HQ9+B, HQ9+~, HQ9+2D, HI9+, and probably some more that I've missed.

---
Tags: restricted-source, polyglot, rosetta-stone, comment
---


title: A Suitable Mission

text:
# Question
Title: A Suitable Mission
Summer Klerance, a senior in college, is what her teachers refer to as GBL\*. Students in her probability class have been assigned individual problems to work on and turn in as part of their final grade. Summer, as usual, procrastinated much too long, and, having finally looked at her problem, realizes it is considerably more advanced than those covered in her course and has several parts as well. An average programmer, Summer decides to take a Monte Carlo gamble with her grade. Her prof. said that answers could be rounded to the nearest integer, and she doesn't have to show her work. Surely if she lets her program run long enough, her results will be close enough to the exact results one would get "the right way" using probability theory alone.

**Challenge**

You (playing alone) are dealt consecutive 13-card hands. *Every* hand is from a full, shuffled deck. After a certain number of deals, you will have held all 52 cards in the deck at least once. The same can be said for several other goals involving complete suits.

Using your favorite random-number tools, help Summer by writing a program that simulates one million 13-card deals and outputs the **average** number of deals needed for you to have seen (held) each of these **seven goals**:

```
1 (Any) one complete suit
2 One given complete suit
3 (Any) two complete suits
4 Two given suits
5 (Any) three complete suits
6 Three given complete suits
7 The complete deck (all four suits)

```

Each goal number (1-7) must be followed by the **average** number of hands needed (rounded to one decimal, which Summer can then round to the nearest integer and turn in) and (just for inquisitive golfers) add the minimum and maximum number of hands needed to reach that goal during the simulation. Provide output from *three runs* of your program. *The challenge is to generate all the averages. The min. and max. are (required) curiosities and will obviously vary run to run.*

**Test Runs**

Input: None

Sample Output: Three separate million-deal runs for the average, minimum, and maximum number of hands needed to reach each of the seven goals.

```
1 [7.7, 2, 20 ]       1 [7.7, 3, 18]        1 [7.7, 2, 20 ]
2 [11.6, 3, 50]       2 [11.7, 3, 54]       2 [11.6, 3, 63]
3 [10.0, 4, 25]       3 [10.0, 4, 23]       3 [10.0, 4, 24]
4 [14.0, 5, 61]       4 [14.0, 4, 57]       4 [14.0, 4, 53]
5 [12.4, 6, 30]       5 [12.4, 6, 32]       5 [12.4, 6, 34]
6 [15.4, 6, 51]       6 [15.4, 6, 53]       6 [15.4, 6, 51]
7 [16.4, 7, 48]       7 [16.4, 7, 62]       7 [16.4, 7, 59]

```

**Rules:**

1. *Every* hand must be dealt from a *full, shuffed deck* of 52 standard French playing cards.
2. Results for each goal must be based on one million hands or deals. You can collect all the results in a single million-deal run, or program as many million-deal runs as you like. However, each of the seven goals should reflect the result of one million deals.
3. Averages for the number of hands should be *rounded to one decimal*.
4. Output should be formatted roughly as above: each goal number (1-7) followed by its results (avg., min., and max. number of hands). **Provide output for three runs of your program (side by side or consecutively), which will serve as a check of the accuracy/consistency of the averages (column 1) only (columns 2 and 3 are required, but will obviously vary run to run).**
5. Shortest program in bytes wins.

---

**Note**: FYI, I believe the *exact* calculation (via formula) for the average number of hands needed to see the complete deck (goal # 7) works out to ≈ **16.4121741798**

---

\*Good but lazy

# Answer
> 4 votes
# JavaScript (V8),  ~~251~~  247 bytes

A full program that prints 7 tuples `(avg, min, max)`.

```
[1,21845,279,30583,6015,32639,32767].map(b=>{for(M=k=t=c=0,m=n=1e6;c++||(x=[j=0]),n--;){for(d=[],i=14;--i;){while(d[v=Math.random()*52|0]);j|=((d[v]=x[v&3]|=1<<v/4)>8190)<<v%4}b>>j&1||(t+=c,M=c>M?c:M,m=c<m?c:m,k+=.1,c=0)}print(~~(t/k+.5)/10,m,M)})

```

Try it online!

### Example output

```
1   7.7  2 19   7.7  2 18   7.7  3 18
2   11.6 3 52   11.6 3 58   11.6 3 49
3   10.0 4 24   10.0 4 23   10.0 4 29
4   14.0 4 51   14.0 5 59   14.0 4 55
5   12.4 6 32   12.4 5 33   12.4 6 33
6   15.4 6 54   15.4 6 52   15.4 6 60
7   16.4 7 56   16.4 7 54   16.4 7 54

```

# Answer
> 3 votes
# Jelly, ~~80~~ 61 bytes

```
%4‘ċⱮ4=13¹ḣƭS<
8⁸€;Q¥€52Ẋḣ13¤ẋç¥"JH$Ʋȷ6Ð¡Ẉ€¬ZT€IµÆmær1;Ṃ;Ṁ)ṖĖ

```

Try it online!

A pair of links that is run as a nilad and returns a list with a member for each goal. Each goal is represented as `[goal number, [mean deals, min deals, max deals]]`. The TIO link only does 10,000 deals per trial since that’s the most that can be done within the 60 second limit. The `ȷ6` above is the number of deals for each trial in something like scientific notation (`ȷ6` means \\$10^6\\$), so for TIO I’ve used `ȷ4` instead.

Full explanation to follow.

# Answer
> 2 votes
# Ruby, 196 bytes

```
7.times{|g|c=r=[]
1.upto(1e6){$.+=1
c|=[*1..52].sample 13
d=(0..3).map{|i|c.count{|j|j%4==i}}
(r<<$.;*c,$.=0)if[d.max(m=g/2+1),d[0,m]][g%2].sum/m>12}
p g+1,[r.sum.fdiv(r.size).round(1),*r.minmax]}

```

Try it online! The number of deals on TIO is set to `1e5` instead of `1e6` to avoid timing out.

Sample output for three local runs with `1e6` deals (side by side for ease of reading and to save space):

```
1              1              1
[7.7, 2, 20]   [7.7, 2, 18]   [7.7, 2, 19]
2              2              2
[11.7, 2, 52]  [11.6, 3, 45]  [11.6, 3, 60]
3              3              3
[10.0, 4, 24]  [10.0, 4, 26]  [10.0, 4, 23]
4              4              4
[14.0, 4, 57]  [14.0, 5, 51]  [14.0, 5, 51]
5              5              5
[12.4, 6, 31]  [12.4, 6, 34]  [12.4, 6, 32]
6              6              6
[15.4, 6, 62]  [15.4, 6, 57]  [15.4, 6, 53]
7              7              7
[16.4, 7, 51]  [16.4, 7, 53]  [16.4, 7, 48]

```

### Explanation

As the deals progress, a count is kept of the number of cards seen from each suit. This count is stored in the 4-element array `d` in the code.

Goals 1, 3, 5, and 7 are achieved when all 13 cards from any \\$m=1, 2, 3, 4\\$ suits, respectively, have been seen, or in other words when the sum of the \\$m\\$ greatest elements of `d` equals \\$13m\\$.

Goals 2, 4, and 6 are equivalent to choosing a particular ordering of suits and seeing all 13 cards from the first \\$m=1,2,3\\$ suits, respectively. In these cases, the goal is achieved when the sum of the first \\$m\\$ elements of `d` equals \\$13m\\$.

```
7.times{|g|    # for each goal
  c=r=[]       # initialise
  1.upto(1e6){ # 1 million times
    $.+=1      # count deals towards current goal
    c|=[*1..52].sample 13 # randomly select 13 cards and keep track of history (set union)
    d=(0..3).map{|i|c.count{|j|j%4==i}} # count cards seen from each suit
    (r<<$.;*c,$.=0)if[d.max(m=g/2+1),d[0,m]][g%2].sum/m>12 # if goal is achieved, store deal counter then reset counter and history
  }
  p g+1,[r.sum.fdiv(r.size).round(1),*r.minmax] # formatted output
}

```

# Answer
> 2 votes
# Charcoal, 136 bytes

```
≔Ｅ⁷⟦⟧ε≔Ｅε⁰ζ≔⮌ζηＦ×φφ«≔⟦⟧θＦ¹³⊞θ‽⁻Ｅ⁵²λθ≧｜ΣＸ²θη≦⊕ζ≔Ｅη↨⁻⊖Ｘ²¦⁵³κ⁸¹⁹²δＦ⁷Ｆ⎇﹪κ²⁼¹Σ…§δκ⊘⁺³κ›⊗№§δκ⁰κ«⊞§εκ§ζκ§≔ζκ⁰§≔ηκ⁰»»Ｅε⪫⟦⊕κ⟦∕÷⁺×χΣι⊘ＬιＬιχ⌊ι⌈ι⟧⟧

```

Try it online! Link is to verbose version of code. Note: TIO link limited to 10,000 iterations as 1,000,000 is too slow. Explanation:

```
≔Ｅ⁷⟦⟧ε≔Ｅε⁰ζ≔⮌ζη

```

Start with an array of 7 empty lists of counts needed to reach the goal, a list of counts tracking the next goal, and a list of cards seen so far for each goal.

```
Ｆ×φφ«

```

Loop 1,000,000 times.

```
≔⟦⟧θＦ¹³⊞θ‽⁻Ｅ⁵²λθ

```

Deal 13 different cards at random.

```
≧｜ΣＸ²θη

```

Convert the cards into a bitmask and mark them as having been seen for each goal.

```
≦⊕ζ

```

Increment the count for each goal.

```
≔Ｅη↨⁻⊖Ｘ²¦⁵³κ⁸¹⁹²δ

```

For each goal, find all the suits for which all of the cards have now been seen.

```
Ｆ⁷Ｆ⎇﹪κ²⁼¹Σ…§δκ⊘⁺³κ›⊗№§δκ⁰κ

```

For each goal, check whether it has been satisfied: goals 2, 4 and 6 require specific suits to have been seen while the other goals only require a count of seen suits.

```
«⊞§εκ§ζκ§≔ζκ⁰§≔ηκ⁰»»

```

If the goal has been satisfied then save the count and restart that goal.

```
Ｅε⪫⟦⊕κ⟦∕÷⁺×χΣι⊘ＬιＬιχ⌊ι⌈ι⟧⟧

```

Format the averages as desired. Sample outputs (from TIO):

```
1 [7.7, 3, 16]  [7.8, 3, 16]  [7.7, 3, 14]
2 [11.7, 4, 35] [11.6, 4, 32] [11.7, 3, 33]
3 [10.0, 5, 21] [10.0, 5, 20] [10.0, 5, 19]
4 [13.9, 6, 39] [14.1, 6, 34] [14.0, 7, 33]
5 [12.4, 7, 27] [12.5, 7, 23] [12.5, 7, 24]
6 [15.7, 8, 39] [15.6, 7, 37] [15.4, 7, 39]
7 [16.5, 8, 39] [16.5, 9, 38] [16.5, 8, 37]

```

# Answer
> 1 votes
# Python 2 (PyPy), 244 bytes

```
from random import*
R=range
for g in R(1,8):
 j=s=0;r=[]
 for _ in R(10**6):
	for c in sample(R(52),13):s|=1<<c
	S=[s>>13*i&8191>8190for i in R(4)];j+=1.;g%2>0>S.sort()
	if all(S[g/-2:]):r+=j,;j=s=0
 print g,round(sum(r)/len(r),1),min(r),max(r)

```

Try it online!

Results of three runs:

```
1  7.7 2 19    1  7.7 3 18    1  7.7 3 18
2 11.6 3 50    2 11.6 3 49    2 11.6 3 45
3 10.0 4 24    3 10.0 4 24    3 10.0 4 24
4 14.0 4 46    4 14.0 4 47    4 14.0 5 58
5 12.4 5 33    5 12.4 6 30    5 12.4 6 32
6 15.4 5 52    6 15.4 5 51    6 15.4 6 54
7 16.4 7 53    7 16.4 7 54    7 16.4 7 51

```

By replacing the inner for loop by `exec`, we can trade in 10 bytes for a bit of memory usage1:

```
from random import*
R=range
for g in R(1,8):j=s=0;r=[];exec'for c in sample(R(52),13):s|=1<<c\nS=[s>>13*i&8191>8190for i in R(4)];j+=1.;g%2>0>S.sort()\nif all(S[g/-2:]):r+=j,;j=s=0\n'*10**6;print g,round(sum(r)/len(r),1),min(r),max(r)

```

Don't try it online!

1 After changing `10**6` to `10**5` this finished while using 4 GB of RAM. 10\*4 = 40?

# Answer
> 1 votes
# Perl 5 (List::Util), ~~195~~ 231 bytes

```
for$g(map'^('.($_%2?'':'(.{13})*').'1{13}){'.($_/2^0).'}',2..8){my@n;for(1..1e6){$n=0;$s=0 x52;while($s!~$g){$h=1x13;substr$h,rand 1+length$h,0,0for 1..39;$s|=$h;$n++}push@n,$n}printf++$i." %.1f %d %d\n",sum(@n)/@n,min(@n),max(@n)}

```

Try it online!

A million times gave the following output from the three runs which took more than 14 minutes each:

```
1 7.7 2 20     |  1 7.7 2 22     |  1 7.7 2 22
2 11.6 2 61    |  2 11.6 2 69    |  2 11.6 2 58
3 10.0 4 26    |  3 10.0 4 28    |  3 10.0 4 28
4 14.0 4 59    |  4 14.0 4 58    |  4 14.0 4 61
5 12.4 5 36    |  5 12.4 5 40    |  5 12.4 5 36
6 15.4 5 62    |  6 15.4 5 56    |  6 15.4 6 60
7 16.4 6 65    |  7 16.4 6 61    |  7 16.4 6 60

```

# Answer
> 0 votes
# PHP, 364, 348, 343, 342, 338, 330

```
for(;$r<23;){if(7==$l=$r++%8)continue;for($d=$x=$c=$s=$g=0,$m=2e6;$d++<1e6;){foreach(array_rand(range(0,51),13)as$a)$u[$a]=$a%4;$t=array_count_values($u);~$l&1&&rsort($t);for($h=-1;$h++<$o=$l>>1;)if(($t[$h]??0)<13)break;$c++;if($h>$o){$s+=$c;$m=min($m,$c);$x=max($x,$c);$g++;$c=0;$u=[];}}$f=round($s/$g,1);echo++$l.":$f,$m,$x\n";}

```

Try it online!

Outputs three consecutive sets of seven goals

-4 bytes thanks to @Djin Tonic for the idea to shuffle cards differently!

Original naive implementation ungolfed:

```
for($run=1;$run<=3;$run++){
  $row=1;
  for($suit_match_count=0;$suit_match_count<=3;$suit_match_count++){//number of given suits to match (-1)
    for($match_type_switch=0;$match_type_switch<=1;$match_type_switch++){//switch between 'any' and 'given'
      if($suit_match_count==3 && $match_type_switch==1) {//last two cases are the same so skip
        continue;
      }
      $goal_count=0;
      $goal_deals_sum=0;
      $goal_deal_count=0;
      $running=[];
      $min_deals=1000001;//outside of range
      $max_deals=0;
      for($deal_count=0;$deal_count<1000000;$deal_count++){//million deals
        $deal=[];
        for(;count($deal)<13;){//one deal
          $card=rand(1,52);
          $deal[$card]=1;
          $running[$card]=$card%4;
        }

        $suit_count = array_count_values($running);//check for complete suits

        if($match_type_switch==0){
          rsort($suit_count);
        }

        for($check_suit_match=0;$check_suit_match<=$suit_match_count;$check_suit_match++){
          if (($suit_count[$check_suit_match]??0)!=13) {
            break;
          }
        }
        $goal_deal_count++;
        if($check_suit_match==($suit_match_count+1)){//we have our desired number of matched suits
          $goal_count++;
          $goal_deals_sum+=$goal_deal_count;

          if($goal_deal_count<$min_deals){
            $min_deals=$goal_deal_count;
          }
          if($goal_deal_count>$max_deals){
            $max_deals=$goal_deal_count;
          }
          $goal_deal_count=0;
          $running=[];
        }
      }
      echo "$row [".(intval(10*$goal_deals_sum/$goal_count)/10).",$min_deals,$max_deals]\n";

      $row++;
    }
  }
  echo "\n\n";
}

```

---
Tags: code-golf, probability-theory, simulation
---


# Question
Title: King of the Hill: Nose Poker - An ogre game for ogres
## Links

Here's the official score table:

```
<script src="https://ajfaraday.github.io/nose_poker/ogres.js"></script><script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/3.3.1/jquery.min.js"></script><table> <thead> <tr> <th>Ogre</th> <th>Hand</th><th>NP</th> <th>Reason</th> </tr></thead> <tbody id="clients"> </tbody></table><script type='text/javascript'>
ogres.forEach( function(data_row){var row=$('<tr>'); var cell=$('<td>'); cell.html(data_row.name); row.append(cell); cell=$('<td>'); cell.html(data_row.hand); row.append(cell); cell=$('<td>'); cell.html(data_row.np); row.append(cell);row.append(cell);cell=$('<td>'); cell.html(data_row.reason); row.append(cell); $('tbody#clients').append(row);});</script>
```

Nose Poker is an ogre game played by a group of ogres. Each ogre brings a large nose and a small club.

On each hand, all the ogres will declare how many times they will poke their nose with the club.

Each time, the lowest bid(s) will be knocked out of the game, then the remaining ogres will poke their nose with the club their declared number of times.

Any ogre who has run out of nose will also be knocked out of the game.

## The Challenge

Write the JavaScript code to play Nose Poker. You'll write a client class which plays the role of an ogre and makes the decision how to bid on each hand.

Your ogre starts the game with 500 nose points (np), and there is no way to recover np during the game. Each turn you will call `controller.declare(pokes)` and either fall out of the competition if you declare the lowest number of pokes, or your troll will lose the declared amount of np.

The goal is to stay in the game as long as you can.

There are three ways to be knocked out of the game:

* **Failed to bid** If something goes wrong and you don't make a bit, or bid zero or less, you're out.
* **Cowardice!** Your ogre chickened out and bid lower than everyone else.
* **Has no nose** Your ogre ran out of np and therefore has no nose. How does it smell? Like it's out of the game.

## The Controller

Your client class will be passed a `controller` object which acts as it's interface to the game.

Here are the four functions it provides:

**np()**: The current amount of nose points that your ogre has.

```
this.controller.np();
// 450

```

**hand\_number()** The number of the current hand the game is on.

```
this.controller.hand_number();
// 2

```

**scores()** An array of the amount of np each currently active ogre has.

```
this.controller.scores();
// [450, 250, 20]

```

Note: This is intentionally sorted in descending order of np so it is not possible to see how other ogres have been bidding.

**declare(pokes)** Here's the important one. Declare how many times your ogre will poke itself in the nose with a club.

```
this.controller.declare(10);

```

## Getting the app

You're going to need node and npm, sorry.

* `git clone https://github.com/AJFaraday/nose_poker.git`
* `cd nose_poker`
* `npm install`

## Writing a Client

Here's the template for your client class, add it to a js file in `src/clients/working`

```
module.exports = class {

  constructor(controller) {
    this.controller = controller;
  }

  play_hand() {
  }

};

```

You can then modify the `play_hand()` function, remember it must call `this.controller.declare(pokes)`. (You can also be knocked out of the game for failing to do this).

When you're happy with it, run `./get_answers.sh` from the nose\_poker root directory. This will add your client to `/src/clients.js` (and also get the current set of clients from the Stack Exchange question). You only need to do this once.

After the first time you can run games to see the result of modifying your code by calling `node script/play_game.js`.

## Submitting your Client

To add your client to the competition, answer this question.

* Name your ogre by including a title (h1, by starting the line with '#' or underlining it with '=' symbols)
    + The name should only contain alpha characters and underscores, no spaces please.
* Put the code in a code block.
* Please include a brief description of your ogre's strategy, and any other information you'd like to include.

The app will then periodically pick up answers, run the game, and update the score table in this question.

## Forbidden stuff

In order to be accepted into the competition, your code must export a valid class which accepts a controller, has a `play_hand()` function, and will call `this.controller.declare(pokes)` at some point in that function. If it does not, the official instance will not import it.

The importer will also ignore any answers which use these terms:

* `game` \- Please do not try to interact with the game directly
* `Math.random` \- Let's keep this deterministic, so the result is definitive.
* `setTimeout`, `setInterval` \- These lead to runtime oddities.
* `eval`, `import` \- Just don't!

## Default bots

| Default Bot | Behaviour |
| --- | --- |
| go\_home | Always bid 1 |
| go\_big | Bids 90% of np |
| half\_way | Bids 50% of np |

# Answer
# Sinus-oidal

```
module.exports = class {
    constructor(controller) {
        this.controller = controller;
    }

    play_hand() {
        var turn = this.controller.hand_number();
        var multiply = Math.sin(turn * Math.PI / 4);

        this.controller.declare(Math.floor(2 ** (multiply + 1)));
    }
};

```

Get it?
> 8 votes

# Answer
# super\_smart\_bot

```
module.exports = class {
    constructor(controller) {
        this.controller = controller;
    }
    try_certain_win()
    {
        //we need to have more points than everyone else combined, plus 1 per player (though this bound is probably too weak)
        //bid as many points as the lowest-NP player has, plus 1
        let tcost = 0;
        let mcost = 999;
        let skipped = false;
        let other_scores = this.controller.scores().filter(a => skipped ? true : (a == this.controller.np() ? (skipped = true)*0 : true));
        for(let c of other_scores)
        {
            tcost += c + 1;
            if(c + 1 < mcost) mcost = c + 1;
        }
        if(this.controller.np() <= tcost)
            return false;
        this.controller.declare(mcost);
        return true;
    }
    min_safe_bid()
    {
        let skipped = false;
        let other_scores = this.controller.scores().filter(a => skipped ? true : (a == this.controller.np() ? (skipped = true)*0 : true));
        let res = Math.min(...other_scores) + 1;
        return res;
    }
    play_hand() {
        if(this.controller.hand_number() == 1)
        {
            this.controller.declare(2);
            return;
        }
        let scores = this.controller.scores();
        if(scores.length == 2) //optimal because this is the last round
        {
            this.controller.declare(this.controller.np() - 1);
            return;
        }
        if(this.try_certain_win()) return;
        let bid = this.controller.np() / this.controller.scores().length;
        bid = Math.min(bid, this.min_safe_bid());
        this.controller.declare(bid);
    }
};

```
> 7 votes

# Answer
# Smart Median

```
module.exports = class {

  constructor(controller) {
    this.controller = controller;
  }

    play_hand() {
    // Beat the simple bots
    if(this.controller.hand_number() <= 5) {
        this.bid(this.controller.hand_number() + 1);
        return;
    }
    var scores = this.other_scores();
    var bid = Math.floor(this.median(scores) / scores.length) + 1; // Add 1 to win once there's only 1 opponent left
    this.bid(bid);
    }

  other_scores() {
    var scores = this.controller.scores();
    var myIndex = scores.indexOf(this.controller.np());
    scores.splice(myIndex, 1);
    return scores;
  }

  median(scores) {
    var half = Math.floor(scores.length / 2);
    return scores[half];
  }

    bid(value) {
        // Never bid more than the weakest player has
        var weak = Math.min(...this.controller.scores());
        // Never bid more than I have
    var me = this.controller.np();
    var final_bid = Math.min(value, weak + 1, me);
    this.controller.declare(final_bid);
    }

};
```

Chooses a bid based on the median score divided by the number of opponents remaining. The idea is that the more opponents there are, the more likely one is to bid low, so I am safer to bid lower as well. I also threw in some smart bidding features, like not bidding more than a guaranteed pass, to not lose too many points. I imagine this strategy will burn through too many points in the midgame to win, but I do think it'll place near the top.
> 6 votes

# Answer
# Half-life

```
module.exports = class {
    constructor(controller) {
        this.controller = controller;
    }

    play_hand() {
        var np = this.controller.np()
        var bid = np < 10 ? np - 1 : Math.floor(np / 2);
        this.controller.declare(bid);
    }
};

```

Takes the number of nose points it has and bids half each time. However, if it has less than 10 np left, it goes all in. This is to hopefully defeat `half_way`.
> 5 votes

# Answer
# Dumb Ogre

```
module.exports = class {
    constructor(controller) {
        this.controller = controller;
    }

    play_hand() {
        this.controller.declare(2);
    }
};

```

To be fair, ogres aren't known to be particularly smart.

A trivial bot to get the ball rolling :p
> 4 votes

# Answer
# Adaptive Bot

```

module.exports = class {

    constructor(controller) {
        this.controller = controller;
    }

    play_hand()
    {
        if (this.controller.hand_number() == 1) {
            this.lastScores = this.controller.scores();
            this.controller.declare(2);
            return;
        }

        var scores = this.controller.scores();
        var finalBid = 100;
        for (var i = 0; i < scores.Length; i++) {
            for (var j = 0; j < this.lastScores.Length; j++) {
                if (this.lastScores[j] - scores[i] < finalBid) {
                    finalBid = this.lastScores[j] - scores[i];
                }
            }
        }

        this.lastScores = scores;

        this.controller.declare(finalBid + 1);
    }
};

```

Starts in the first round by bidding 2, to not get kicked out immediately (due to Go\_Home bot).

Then, assuming the bots stay in the same order, find out what everyone bid by finding the smallest difference between the previous turn and the current one.

As all bots I have seen so far reduce their bid monotonically, finding the lowest bid that survived and adding 1 will ensure that you survive next round.

EDIT: I dont have access to real coding tools right now, so I cant upload it/fix bugs. But I hope I made the strategy clear, so if anyone wants to copy this into a working bot, feel free to do so :)

EDIT2: The bots was completely busted and only bid 101 each turn :O Now it should work properly, so please update it again :D
> 4 votes

# Answer
# Exponential Ogre

```
module.exports = class {
    constructor(controller) {
        this.controller = controller;
    }

    play_hand() {
        let bid = 1 << this.controller.hand_number();
        this.controller.declare(bid);
    }
};

```

Starting at 2, the ogre doubles its bid every round. Quite similar to Reverse Pinocchio, but I got the idea independently.
> 4 votes

# Answer
# Oldgre

Oldgre has perfected his strategy over many years.

*Whippersnappgres!*

```
module.exports = class {

  constructor(controller) {
    this.controller = controller;
  }

  play_hand() {
    const x = this.controller.hand_number();
    this.controller.declare(
      -     0.000006858186 * x ** 11
      -     0.000199732658 * x ** 10
      +     0.024797517263 * x ** 9
      -     0.737278798843 * x ** 8
      +    11.416562524617 * x ** 7
      -   107.788528491826 * x ** 6
      +   656.517974108233 * x ** 5
      -  2615.799102867764 * x ** 4
      +  6707.381768918599 * x ** 3
      - 10515.725107130049 * x ** 2
      +  8997.738815265786 * x ** 1
      -  3130.528128281523 * x ** 0
    );
  }

};

```

This is largely a proof of concept and, for the sake of the competition, I won't keep updating it.
> 4 votes

# Answer
# Simple Optimization Thing

```
module.exports = class {
    constructor(controller) {
        this.controller = controller;
    }

    play_hand() {
        var count = this.controller.scores().length;
        var min = Math.min(...this.controller.scores());

        this.controller.declare(min / count);
    }
};

```

Not sure if this strategy will work at all :p
> 3 votes

# Answer
# Quicksort Ogre

```
module.exports = class {
    constructor(controller) {
        this.controller = controller;
    }

    play_hand() {
        var turns = this.controller.hand_number();

        this.controller.declare(Math.round(turns * Math.log(turns)) + 4);
    }
};

```

Ogres don't understand time complexity, but they do understand being poked on the nose \\$n\log n\\$ times. Small constant offset to prevent being immediately eliminated.

Probably my last somewhat trivial bot, I just want to see how something between the linear and exponential strategies would do (and quadratic was a bit too boring :p).
> 3 votes

# Answer
# Troll Adaptive

Exactly the same as Adaptive by @Nurator, except increases it's bid the second round to eliminate the original Adaptive:

```
module.exports = class {

    constructor(controller) {
        this.controller = controller;
    }

    play_hand()
    {
        if (this.controller.hand_number() == 1) {
            this.lastScores = this.controller.scores();
            this.controller.declare(2);
            return;
        }
        else if (this.controller.hand_number() == 2) {
            this.lastScores = this.controller.scores();
            /* Adaptive will bid 3 since 2 is the lowest number. Thus, bidding 4 will eliminate Adaptive */
            this.controller.declare(4);
            return;
        }

        var scores = this.controller.scores();
        var finalBid = 75;
        for (var i = 0; i < scores.Length; i++) {
            for (var j = 0; j < this.lastScores.Length; j++) {
                if (this.lastScores[j] - this.scores[i] < finalBid) {
                    finalBid = this.lastScores[j] - this.scores[i];
                }
            }
        }

        this.lastScores = scores;

        this.controller.declare(finalBid + 1);
    }
};

```

Can easily be defeated by increasing your bid in the third round instead, and the bot after can be easily defeated in the fourth round etc.
> 2 votes

# Answer
# Knockout

```
module.exports = class {

    constructor(controller) {
      this.controller = controller;
    }

    play_hand() {
      let hand = this.controller.hand_number()
      if(hand == 12){
           this.controller.declare(2);
           return;
      }
      if(this.controller.scores.length == 2){
        this.controller.declare(this.controller.np() - 1)
        return;
      }
      this.controller.declare(500 / (this.controller.scores().length + hand + 2) + 20 * (hand > 7) + 5 * (hand > 9) + 5 * (hand > 9))
    }

  };

```

~~A very simple strategy with some small tweaks that allow it to win!~~ Has been complicated a bit.

Basically tries to spend roughly the same amount each turn by going 500 / original number of bots. Of course, it's impossible to calculate the original number of bots, so it counts the current amount + the hand number.

Has several tricks, including going all-in at the end, and playing 2 on round 12 because oldgre will always play 1.

I'm not sure what's up with the snippet, but it *is* winning locally:
> 2 votes

# Answer
# Super dumb bot

According to the instructions as I understand them, my own bot's score is returned somewhere in scores(); if this is not the case, comment out the lines starting with the line `if (score == sscore)` and continuing to the `else`.

```
module.exports = class {
    constructor(controller) {
        this.controller = controller;
    }

    play_hand() {
        if(this.controller.hand_number() == 1)
        {
            // Go Home Bot makes everybody else need to do this nonsense on the first turn rather than really try.
            this.controller.declare(2);
            return;
        }
        if(this.controller.hand_number() == 2)
        {
            // Get rid of the other not-really-competing bot.
            this.controller.declare(3);
            return;
        }
        var myscore = this.controller.np();
        var sscore = myscore;
        var scores = this.controller.scores();
        var ctr = 0;
        for (var i = 0; i < scores.length; i++) {
            var score = scores[i];
            if (score != 0)
                if (score == sscore)
                    sscore = 0;
                else
                    ctr+=1;
        }
        var value = (ctr < 2) ? 0
             : Math.floor(myscore / ctr);
        this.controller.declare(value);
    }
};

```

Either I know the optimal strategy off the top of my head or I don't. I put no effort into finding out whether or not I am right. The long loop just determines how many other bots are in the game. If the specifications had been written tighter it could be replaced by `var ctr = scores.length - 1;`
> 2 votes

# Answer
# Incremental ogre

```
module.exports = class {

  constructor(controller) {
    this.controller = controller;
  }

  play_hand() {
    var bid = this.controller.hand_number() * 10
    this.controller.declare(bid);
  }

};

```

Bids 10 more each round.
> 1 votes

---
Tags: king-of-the-hill, javascript
---


title: What degree is this palindrome?

text:
# Question
Title: What degree is this palindrome?
Your task is to determine the palindromic degree of a given non-empty string.

To do this, loop until one of the following conditions are met:

* The string is not a palindrome.
* You encounter a string that has already been encountered.

And do the following:

* If it is a palindrome, add one to the degree.
* Depalindromize.

For example, if I had the string `babababab`, the calculation would go:

```
babababab     1
babab         2
bab           3
ba

```

For the string `zzzzz`, it would go:

```
zzzzz         1
zzz           2
zz            3
z             4
z

```

### Test cases

```
abc 0
cenea 0
pappap 2
aa 2
aba 1
aaa 3
cccc 3
zzzzz 4

```

Explanation:

```
abc : 0
cenea : 0
pappap -> pap -> pa : 2
aa -> a -> a : 2
aba -> ab : 1
aaa -> aa -> a -> a: 3
cccc -> cc -> c -> c: 3
zzzzz -> zzz -> zz -> z -> z : 4

```

Remember, this is , so the code with the fewest bytes wins.

# Answer
## Perl, 53 bytes

52 bytes of code + 1 byte for `-p`.

```
$\++while s/^((.+).?)(??{reverse$2})$/$1/||s/^.$//}{

```

To run it :

```
perl -pE '$\++while s/^((.+).?)(??{reverse$2})$/$1/||s/^.$//}{' <<< "zzzzz"

```
> 3 votes

# Answer
# Jelly, ~~11~~ 9 bytes

```
ŒHḢ$ƬUƑƤS

```

Try it online!

-2 bytes thanks to Unrelated String!

## How it works

```
ŒHḢ$ƬUƑƤS - Main link. Takes a string S on the left
   $Ƭ     - Until reaching a previously encountered string:
ŒH        -   Split into halves
  Ḣ       -   Take the first one
       Ƥ  - Over each prefix:
     U    -   Reverse each string in the prefix
      Ƒ   -   Does that equal the prefix?
        S - Sum

```
> 3 votes

# Answer
# JavaScript (ES6), 85 bytes

```
f=s=>s[1]?(t=s.slice(0,l=-~s.length/2))==[...s.slice(-l)].reverse().join``?1+f(t):0:1

```
> 2 votes

# Answer
# Haskell, 58 bytes

```
p[a]=1
p a|reverse a==a=1+p(take(div(1+length a)2)a)
p _=0

```
> 2 votes

# Answer
# 05AB1E, 14 bytes

```
[ÐÂÊ#¼g#2ä¬])\

```

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

# Answer
# Scala, 56 bytes

```
s=>if(s.reverse==s&&s.size>1)1+h(s.take(s.size/2))else 2

```

requires an assignmentt to a variable with type declaration:

`val f:(String=>Int)=...`
> 1 votes

# Answer
# Pyth - 21 bytes

The case of palindromes never running out really cost me, will look for a better way.

```
.xxK.uhc2NQ)hf!_ITKlK

```

Test Suite.
> 0 votes

# Answer
# Python 2, ~~94~~ ~~87~~ 77 bytes

The recursive approach... this currently assumes that empty & single letter strings get a score of 1.

```
def P(x,c=0):a=len(x);return c+(a<2)if(x[::-1]!=x)+(a<2)else P(x[:-~a/2],-~c)

```

**Try it online!**
> 0 votes

# Answer
# Java 7,147 bytes

```
int c(String s,int t){int l=s.length();return l<2?t+1:s.equals(new StringBuilder(s).reverse().toString())?c(s.substring(0,l%2>0?l/2+1:l/2),++t):t;}

```
> 0 votes

# Answer
# Pyth, 17 bytes

```
a!_IQl.u?_IJhc2NJ

```

Test suite

The previous Pyth answer uses an older version of the language and a significantly different approach.

##### Explanation:

```
a!_IQl.u?_IJhc2NJ   | Full program
a!_IQl.u?_IJhc2NJNQ | with implicit variables filled
--------------------+-------------------------------------------------------------------------------------------------------------------------
      .u          Q | Repeat the following until a repeated value is found, collecting the intermediate results, with N starting as Q (input):
           Jhc2N    |  J = the first half of N (longer half is necessary)
        ?_I     JN  |  if J is invariant over reversal (i.e. is a palindrome), N = J, else N = N
     l              | take the length of the resulting list
a                   | subtract
 !_IQ               |  0 if Q is a palindrome, 1 otherwise

```
> 0 votes

# Answer
# Python 3, 53 bytes

```
f=lambda x:2>>len(x)or-~f(x[len(x)//2:])*(x==x[::-1])

```

Try it online!

## How it works:

* `2>>len(x)` will give us `1` if `len(x)==1` and `0` if `len(x)>1` (we don't have to treat the case where `x` is the empty string)
* if the previous gives `0` then we recurse with `x[len(x)//2:]` which is the second part of our palindrome (including the center), `-~` we add `1` and multiply by `(x==x[::-1])` to return `0` if it is not a palidrome
> 0 votes

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


# Question
Title: Blinking Lighthouses – Founder's Day Upgrade
To celebrate the island's next Founder's Day, colored filters (fuchsia, chartreuse, and aquamarine\*) have been installed in every lighthouse. All lighthouses begin operation with their fuchsia filter, and they are all on the same color cycle: FCA, FCA, ... Each lighthouse changes its color filter *after every ON blink,* whether long or short. In addition, each starts the cycle anew with fuchsia each time its code begins.

Other than the addition of color, lighthouse operation is identical to that in the original challenge, **Blinking Lighthouses**.

**Challenge:** Input is identical to the original challenge: the codes for each of n lighthouses in the form of strings of (only) L's and S's.

Output now consists of *four* lines, one line per color, plus a "totals" line. The top line has the total times that 0...n fuchsia lights were simultaneously on; the second line chartreuse; and the third line aquamarine. Thus the third number in the second line is the total seconds that exactly two chartreuse lights were simultaneously on *regardless of what other colors were on during those seconds*. The fourth line has the totals for 0...n lights simultaneously on regardless of color (this line is identical to the output of the original challenge).

***Unfortunately***, Chief of Lighthouse Operations Marie Lumenix has reported a glitch during filter testing. For some reason, if *all* lighthouses have simultaneously blinked aquamarine at the same time for a *total* of 5 seconds after the start of operation (the last item in line 3 of output), the electronic color filter system *immediately* fails and all lighthouses continue their schedules for the rest of the hour blinking white. This glitch will not affect the last, "totals", line of output, but may affect the first three rows, *which each total the number of seconds only for the period that filters were working*.\**

**Rules** The rules are otherwise the same as in the original challenge. Shortest code in bytes wins.

*Just for clarification*: the first number in the last row is the total seconds that all lighthouses were off regardless of color. The last row should sum to 3600 sec as in the original challenge, or 1 hr of lighthouse operation. The sums for each row, 1 to 3, should match, whether or not they each total 3600. *These three rows stop counting after a glitch.*

**Test Cases for the broken system**

```
(Input -> Output)

['SLS', 'SLL', 'SSS', 'LSL'] ->

[1178, 360, 90, 40, 5]
[998, 470, 165, 40, 0]
[1178, 165, 270, 55, 5]
[1125, 890, 652, 590, 343]

['SLS', 'LLS', 'SSSL'] ->

[2121, 1158, 288, 33]
[2155, 1219, 226, 0]
[2957, 579, 64, 0]
[1254, 1125, 577, 644]

(The color schedules, in seconds, for the 3 lighthouses in test case #2 case are:

F-CCC-A-------  [repeat]
FFF-CCC-A------- [repeat]
F-CCC-A-FFF------- [repeat]

each lighthouse begins the FCA color cycle anew each time its code repeats.)

['SSSLLLSSS', 'LLSSSLLSSLS', 'LSLSLL', 'SSLLL', 'SLLSSSL'] ->

[1334, 1115, 548, 223, 57, 8]
[1560, 1047, 463, 163, 44, 8]
[1591, 950, 525, 184, 30, 5]
[484, 653, 657, 553, 553, 700]

```

---

\*The colors of Lighthouse Island's flag, chosen by a referendum held at Aloisius' Tavern and Gift Shop.
\**Marie feels absolutely terrible about this and promises to get things shipshape by Founder's Day.

# Answer
# , 129 bytes

```
<@(0,#\)(<:@(#/.~@,+/))&>[:(<@(+/),~]<@({.&.|:"2)~[:{:5{.!._[:>:@I.*/@{:)1 2 3=/(3600$(6$0),~&;[:(*&.>1 2 3$~$)19<@#:@|14+3&u:)&>

```

Try it online!
> 4 votes

# Answer
# 05AB1E, 52 bytes

Based on my answer to the previous challenge.

```
ε€C9%Å10.ý˜7Å0«Dη_O3%>*60n∍}øÐ3QP.¥5‹Ï3LδQøs<dªεOZÝ¢

```

Try it online!

```
ε€C9%Å10.ý˜7Å0«        60n∍}   # see my previous answer
               Dη              # push all prefixes of the signal
                 _O            # count the number of 0's (how often the signal was off)
                   3%>         # modulo 3, add 1
                      *        # multiply each value in the signal list (0 or 1) with this
                               # this replaces all 1's with the correct color: (1=F, 2=C, 3=A)

øÐ                             # tranpose the list (n × 3600 -> 3600 × n) and push the result three times
  3QP                          # on the first copy, check for each second if all lighthouses are aquamarine
     .¥                        # take the sums of prefixes of this list,
                               # this keeps track of how many times all lighthouses were aquamarine so far
       5‹                      # for each second: is this value less than 5?
         Ï                     # take the lighthouse for all seconds where this was true
          3L                   # push the range [1, 2, 3]
            δQø                # for each of those numbers (colors) compare the lighthouse colors to it
               s<dª            # append a boolean matrix of activations in any color (>0)
                   ε           # for each of those 4 boolean matrices:
                    O          # sum each row / second
                     ZÝ        # get the range [0 .. maximum]
                       ¢       # and count all these values

```

The first half of this can be used to visualize the color pattern: Try it online!
> 4 votes

# Answer
# Jelly, 55 bytes

```
ŻI»0Ä’%3‘×
Ø0œịŻṖÄ<5a
O%9ÄṬ;Øỵ¬Ñṁ⁽½c)Zċþ3Sṭ$=þ@LŻ$ṪṭÇƊ§

```

Try it online!

A full program taking a list of strings and printing a list of lists of integers.

The first part (converting from Ss and Ls to the sequence dir each lighthouse was derived from @JonathanAllan’s answer to the previous challenge.

## Explanation

Convert a list of 0s and 1s to a list of 0s, 1s, 2s and 3s

```
Ż          | Prepend 0
 I         | Increments
  »0       | Max of 0 and this (i.e. replace -1 with 0)
    Ä      | Cumulative sum
     ’     | Add 1
      %3   | Mod 3
        ‘  | Subtract 1
         × | Times the input

```

Replace all of the values in the lists of F, C and A with 0 once the last list of the list list provided as the argument. Argument referred to as x.

```
Ø0œị       | x[0][0]
    Ż      | Prepend 0
     Ṗ     | Remove last item
      Ä    | Cumulative sum
       <5  | Less than 5
         a | Logical and with x (vectorises)

```

```
              )                     | For each lighthouse list:
O                                   | - Convert each character to UTF8 codepoints
 %9                                 | - Mod 9
   Ä                                | - Cumulative sum
    Ṭ                               | - Untruthy
     ;Øỵ                            | - Append "aeiouy"
        ¬                           | - Logical not
         Ñ                          | - Call helper link 1
          ṁ⁽½c                      | - Mould to 3600
               Z                    | Transpose
                ċþ3                 | Outer function using count and the numbers [1,2,3]
                     $              | Following as a monad:
                   S                | - Sum (because of vectorisation, will add the F, C and A values together)
                    ṭ               | - Tag onto the end of the F,C,A list
                      =þ@LŻ$        | Outer function using equals (with arguments reversed) and using [0,1,..,n] as the right argument
                               Ɗ    | Following as a monad:
                            Ṫ       | - Tail
                             ṭ      | - Tag onto:
                              Ç     |   - Result of calling helper link 2 on the remaining lists
                                §   | Sum of innermost lists

```
> 4 votes

# Answer
# Python 2, ~~203~~ 200 bytes

```
E=enumerate
l=input()
t=eval(`[[0]*-~len(l)]*4`)
for i in range(3600):
 for y,q in E(t):q[sum(y==((sum([~ord(w)%5*[j%3]+[3]for j,w in E(c)],[])+[3]*6)*450)[i]for c in l)^0-y/3]+=y*y|5>t[2][-1]
print t

```

Try it online!

Building the pattern with strings instead of lists of digits comes out at the same length and is a bit faster: Try it online!
> 2 votes

# Answer
# Jelly, 51 bytes

```
Ẓ&/Ä<5S‘x3ɓBSZḊḣ"
O%9Ṭ€;Øỵ¬a"“µ¦¤‘ṁ$+⁴Fṁ⁽½c)ÇċⱮ€LŻ$

```

A monadic Link that accepts the list of patterns and yields the list of lists of counts.

**Try it online!**

### How?

```
Ẓ&/Ä<5S‘x3ɓBSZḊḣ" - Link 1: list of lists of colours at each second, L
                            where F=25, C=21, A=19, and off=16
Ẓ                 - is prime? (i.e. is Aquamarine?)
  /               - reduce using:
 &                -   bitwise AND -> 1 if all Aquamarine else 0
   Ä              - cumulative sums
    <5            - less than five?
      S           - sum
       ‘          - increment -> second, s, when filtering breaks (or 3601)
        x3        - repeat (that) three times -> [s,s,s]
          ɓ       - new dyadic chain, f(L, [s,s,s]):
           B      -   convert (L) to binary i.e. each number -> [1, F?, C?, A?, on?]
            S     -   sum columns
             Z    -   transpose
              Ḋ   -   dequeue (discard the leading-bit result)
                " -   (that) zip ([s,s,s]) with:
               ḣ  -     head to index  (this leaves the fourth list intact)

O%9Ṭ€;Øỵ¬a"“µ¦¤‘ṁ$+⁴Fṁ⁽½c)ÇċⱮ€LŻ$ - Main Link: list of patterns
                         )        - for each pattern:
O%9Ṭ€                             -   convert 'S' to [0,1] and 'L' t [0,0,0,1]
     ;Øỵ                          -   concatenate "aeiouy"
        ¬                         -   logical NOT -> unflattend on/off seconds, U
                 $                -   last two links as a monad, f(pattern):
           “µ¦¤‘                  -     [9,5,3]
                ṁ                 -     mould like (patten) - e.g. 'SLSS' -> [9,5,3,9]
          "                       -   (U) zip (that) with:
         a                        -     logical AND -> 1s become 9 (F), 5 (C), or 3 (A)
                  +⁴              -   add 16 -> 25 (F), 21 (C), 19 (A), or 16 (off)
                    F             -   flatten
                     ṁ⁽½c         -   mould like [1..3600]
                          Ç       - call last Link (Link 1) as a monad, f(that)
                                $ - last two links as a monad, f(patterns):
                              L   -   length
                               Ż  -   zero-range -> [0..length(patterns)]
                           ċⱮ€    - for each map with count occurrences

```
> 2 votes

# Answer
# Python 3, ~~282~~ ~~276~~ 241 bytes

I managed to get the byte count under 300, I'm quite happy with that :).

**Edit:**
*-6 bytes thanks to @ovs:* rewritten ternary `if ... else`.
*-10 bytes:* `m.append` replaced by `+=[]`, and including the `x+=`. `range(4)` replaced by a list of 4 elemensts.
*-15 bytes:* shortened the creation of list `m` of translated codes: `m` built with list comprehension, string built with `join`.
*-10 bytes:* the creation of translated list `m` is moved directly into the loop of counter. Used 2 variables to unpack the `zip`.

```
def f(h):
 t=[[0]*-~len(h)for i in[0]*4]
 for i in range(3600):
  for n in'0123'[3*(t[2][-1]>4):]:t[int(n)][[c[i]for c in[(''.join(q*(p>'L'or 3)+'3'for p,q in zip(w,'012'*len(w)))+'3'*6)*450 for w in h]].count(n)]+=1
 print(t[:3],t[3][::-1])

```

Try it online!

---

***Original code explanation** (at least I tried to explain)*

* `def f(h):`
Function definition, takes as input the list with the lighthouses' codes.
* `m,t=[],[[0]*-~len(h)for i in range(4)]`
Initialize the empty list `m` that will contain the translated codes.
Initialize the list of counters: 4 lists (1 for each color and 1 for the total), each with n+1 lighthouses elements.
* `for w in h:`
Loop on the code of each lighthouse to translate into color codes.
* `x=''`
Initialize empty string for the translated code.
* `for q in zip(w,'012'*len(w)):x+=q[1]*(1if q[0]>'L'else 3)+'3'`
Translate the `'SL'` sequences into color codes and the corresponding duration.
`zip(w,'012'*len(w))` zips the the `'SL'` code with the corresponding repeated color sequence ('0'=F, '1'=C, '2'=A).
For each `'S'`, `'L'`: replace with the color code (repeated for the seconds of short or long duration) and the off separation period ('3'=OFF); `x += lenght of color + 1s off`
* `x+='3'*6;m.append(x*450)`
Add the long off period (6s since 1s is already present) and extend the translated sequence for at least 1h.
* `for i in range(3600):`
Loop for 1h: for each second...
* `for n in'0123'[3*(t[2][-1]>4):]:t[int(n)][[c[i]for c in m].count(n)]+=1`
For each color and for the off (`in '0123'`)...
`'0123'[3*(t[2][-1]>4):]` count only the off periods (indexed last item of the string) if we get 5s of color A on all lighthouses at the same time.
`[c[i]for c in m]` status of each lighthouse at second *i*.
`count(n)` gives how many lighthouses have that status `n`; the count corresponds to the index in the list of the corresponding status; and increment the counter.
To summarize: `t[index of color][index of how many are ON] += 1`
* `print(t[:3],t[3][::-1])`
Print the counter for the colors and the total ON period: this list must be reversed since in the previous step we counted the OFF periods.
> 2 votes

---
Tags: code-golf, string, array, arithmetic
---


title: To find islands of 1 and 0 in matrix

text:
# Question
Title: To find islands of 1 and 0 in matrix
Given a two dimensional matrix of 0 and 1s. Find the number of island for 1s and 0s where neighbours are only in the horizontal and vertical.

```
Given input:

1 1 1 0
1 1 1 0

output = 1 1
Number of 1s island = 1

xxx-
xxx-

Number of 0s island = 1

---x
---x

------------------------------

Given input:

0 0 0 0
1 1 1 1
0 0 0 0
1 1 1 1

output = 2 2
Number of 1s island = 2

----
xxxx  <-- an island of 1s
----
xxxx  <-- another island of 1s

Number of 0s island = 2

xxxx  <-- an island
----
xxxx  <-- another island
----

------------------------------

Given input:

1 0 0
0 0 0
0 0 1
output = 2 1
Number for 1's island = 2:

x--  <-- an island of 1s
---
--x  <-- an island of 1s

Number of 0's island = 1:

-xx  \
xxx   > 1 big island of 0s
xx-  /

------------------------------

Given input:

1 1 0
1 0 0
output = 1 1
Number for 1's island =1 and number of 0's island = 1

------------------------------

Given input:

1 1
1 1
output = 1 0
Number for 1's island =1 and number of 0's island = 0

```

# Answer
# , 57 bytes

```
,&([:(0#@-.~~.@,)](*@[*[:>./((,-)#:i.3)|.!.0])^:_ i.@$)-.

```

Try it online!

This is one of those where the idea is incredibly simple (and I think fun), but executing it had some mechanical lengthiness which masks the simplicity... eg, shifting the original matrix in all directions with 0 fill is the verbose `((,-)#:i.3) |.!.0`.

It's likely this mechanical lengthiness can be golfed further, and I may try tomorrow evening, but I'll post the crux of it now.

Say our input is:

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

```

We start with a matrix of unique integers the same size:

```
 0  1  2  3
 4  5  6  7
 8  9 10 11
12 13 14 15

```

Then for each cell we find the max of all its neighbors, and multiply by the input mask:

```
 0  0  0  0
 8  9 10 11
 0  0  0  0
13 14 15 15

```

We iterate this process until the matrix stops changing:

```
 0  0  0  0
11 11 11 11
 0  0  0  0
15 15 15 15

```

And then count the number of unique, non-zero elements. That tells us the number of 1-islands.

We apply the same process to "1 minus the input" to get the number of 0-islands.
> 18 votes

# Answer
# APL (Dyalog Unicode), ~~29~~ 28 bytesSBCS

-1 thanks to @Adám

```
{≢∪∨.∧⍨⍣≡2>+/↑|∘.-⍨⍸⍵}¨⊂,~∘⊂

```

Try it online!

`⊂,~∘⊂` the matrix and its negation

`{`  for each of them do

`⍸⍵` list of pairs of coords of 1s

`+/↑|∘.-⍨` matrix of manhattan distances

`2>` neighbour matrix

`∨.∧⍨⍣≡` transitive closure

`≢∪` number of unique rows
> 17 votes

# Answer
# MATL, ~~14~~ 12 bytes

```
,G@-K&1ZIugs

```

Try it online! Or verify all test cases.

### Explanation

```
,        % Do twice
  G      %   Push input
  @      %   Push iteration index: first 0, then 1
  -      %   Subtract. This converts 0 and 1 into -1 and 0 in the second iteration
  K      %   Push 4
  &1ZI   %   Label connected components of matrix using 4-connectedness. Zeros in the
         %   matrix are background. This replaces the nonzeros by 1, 2, 3, ..., where
         %   each number defines a connected component
  u      %   Unique values. This gives [0; 1; 2; ..., L], where L is the number of
         %   connected components.
  g      %   Convert nonzeros to 1
  s      %   Sum. This gives L, to be output
         % End (implicit).
         % Display stack (implicit)

```
> 8 votes

# Answer
# JavaScript (ES7),  ~~138 ... 107~~  106 bytes

Returns an array `[ones, zeros]`.

```
f=(m,X,Y,V=.5,c=[0,0])=>m.map((r,y)=>r.map((v,x)=>V-v|(x-X)**2+(y-Y)**2>1||f(m,x,y,v,r[c[v^1]++,x]=2)))&&c

```

Try it online!

### How?

We use a recursive function. During the initial call, we look for \\$0\\$'s and \\$1\\$'s. Whenever we find such a starting point, we increment the corresponding island counter (\\$c\[0\]\\$ or \\$c\[1\]\\$) and enter the recursive phase to flood-fill the area of similar adjacent cells with \\$2\\$'s.

To save bytes, the exact same code is used for both the root iteration and the recursive iterations, but it behaves a bit differently.

During the first iteration:

* We start with \\$V=0.5\\$ so that \\$V-v\\$ is rounded to \\$0\\$ for both \\$v=0\\$ and \\$v=1\\$, thanks to the bitwise OR.
* \\$X\\$ and \\$Y\\$ are undefined and the computed quadrance \\$(x-X)^2+(y-Y)^2\\$ evaluates to *NaN*. It forces the inequality test to fail, no matter the value of \\$(x,y)\\$.

During the recursive iterations:

* The parameter \\$c\\$ is set to an integer (\\$2\\$) instead of an array. Because numbers are objects in JS, the expression `c[v ^ 1]++` is valid if \\$c\\$ is a number -- although it has no effect at all. It means that we can execute this statement unconditionally, without knowing if we're currently looking for starting points or flood-filling.

### Commented

```
f = (                 // f is a recursive function taking:
  m,                  //   m[]  = input binary matrix
  X, Y,               //   X, Y = coordinates of the previous cell, initially undefined
  V = .5,             //   V    = value of the previous cell, initially set to 0.5
                      //          so that the integer part of V - v is 0 for v = 0 or 1
  c = [0, 0]          //   c[]  = array of counters of 1's and 0's islands
) =>                  //          (or an integer when called recursively)
  m.map((r, y) =>     // for each row r[] at position y in m[]:
    r.map((v, x) =>   //   for each value v at position x in r[]:
      V - v |         //     abort if |V - v| ≥ 1
      (x - X) ** 2 +  //     or X and Y are defined and the quadrance between
      (y - Y) ** 2    //     (X, Y) and (x, y)
      > 1 ||          //     is greater than 1
      f(              //     otherwise, do a recursive call to f:
        m,            //       leave m[] unchanged
        x, y,         //       pass the new coordinates
        v,            //       pass the new reference value
        r[c[v ^ 1]++, //       increment c[v ^ 1] (ineffective if c is an integer)
          x           //       and set the current cell ...
        ] = 2         //       ... to 2
      )               //     end of recursive call
    )                 //   end of inner map()
  ) && c              // end of outer map(); return c

```
> 7 votes

# Answer
# Wolfram Language (Mathematica), ~~64~~ 62 bytes

```
Max@MorphologicalComponents[#,CornerNeighbors->1<0]&/@{#,1-#}&

```

Try it online!

Thanks to attinat: we can write `1<0` instead of `False` and save two bytes.

un-golfed version:

```
F[M_] := {Max[MorphologicalComponents[M,   CornerNeighbors -> False]],
          Max[MorphologicalComponents[1-M, CornerNeighbors -> False]]}

```

There is, of course, a *Mathematica* builtin `MorphologicalComponents` that takes an array (or an image) and returns the same with the pixels of each morphologically connected island replaced by the island index. Taking the `Max` of this result gives the number of islands (the background zeros are left at zero, and the island index starts at 1). We need to do this separately for the array (giving the number of 1-islands) and one minus the array (giving the number of 0-islands). To make sure diagonal neighbors don't count as neighbors, the option `CornerNeighbors->False` needs to be given.
> 7 votes

# Answer
# K (ngn/k), ~~60 55 51 50~~ 46 bytes

```
{#?{|/'x*\:x}/2>+/x*x:x-\:'x:(0,#*x)\&,/x}'~:\

```

Try it online!

`~:\` a pair of the input and its negation (literally: negate iterate-converge)

`{` `}'` for each

`,/x` flatten the arg

`&` where are the 1s? - list of indices

`(0,#*x)\` divmod width(input) to get two separate lists for ys and xs

`x-\:'x:` per-axis distances ∆x and ∆y

`x*x:` square them

`+/` add ∆x² and ∆y²

`2>` neighbour matrix

`{|/'x*\:x}/` transitive closure

`#?` count unique rows
> 6 votes

# Answer
# Python 3, 144 127 bytes

This solution uses `cv2`'s awesome image processing power. Despite cv's less awesome, super long and readable method names, it beats both other Python answers!

### Golfed:

```
import cv2,numpy as n
f=lambda b:n.amax(cv2.connectedComponents(b*255,0,4)[1])
def g(a):b=n.array(a,n.uint8);print(f(1-b),f(b))

```

### Expanded:

```
import cv2
import numpy as np

# Finds the number of connected 1 regions
def get_components(binary_map):
    _, labels = cv2.connectedComponents(binary_map*255, connectivity=4) # default connectivity is 8
    # labels is a 2d array of the binary map but with 0, 1, 2, etc. marking the connected regions
    components = np.amax(labels)
    return components

# Takes a 2d array of 0s and 1s and returns the number of connected regions
def solve(array):
    binary_map = np.array(input_map, dtype=np.uint8)
    black_regions = get_components(1 - binary_map) # 0s
    white_regions = get_components(binary_map) # 1s
    return (black_regions, white_regions)

```
> 6 votes

# Answer
# , ~~46 44~~ 43 bytes

-1 byte thanks to @miles

```
,&#&~.&([:+./ .*~^:_:2>1#.[:|@-"1/~4$.$.)-.

```

Try it online!

tests and the `,&` `-.` wrapper stolen from @jonah's answer

`,&` `-.` for the input and its negation do:

`4$.$.` (y,x) coordinates of the 1s as an n×2 matrix

`1#.[:|@-"1/~` manhattan distances: abs(∆x)+abs(∆y)

`2>` neighbour matrix

`[:+./ .*~^:_:` transitive closure

`#&~.&(` `)` number of unique rows
> 5 votes

# Answer
# Jelly, 20 bytes

```
,CŒṪ€µạþ`§Ịæ*LṠQL«L)

```

Try it online!

Adapted from my Jelly answer to caird's shape grouping challenge. Unfortunately, handling empty lists had multiple consequences that made me use `§` instead of complex numbers and add `«L`. The outer structure was shamelessly stolen from caird's answer.

```
,CŒṪ€µạþ`§Ịæ*LṠQL«L)    Main link. Input = binary matrix
,CŒṪ€                   Classify coords of zeros and ones (Ġ doesn't work)
     µ             )    Operate on each list...
      ạþ`§Ị             Proximity matrix; m[i][j]==1 if two points are adjacent
           æ*L          m^(length of input list)
              ṠQL       Sign (convert positives to 1) and count unique rows
                 «L     Handle empty list to make it 0

```
> 5 votes

# Answer
# Retina 0.8.2, 155 bytes

```
s`1(.*)
;$1a
}+`(?<=(.)*)(1|;)(.*¶(?<-1>.)*(?(1)$))?(?!\2)[1;]
;$3;
s`0(.*)
:$1b
}+`(?<=(.)*)(0|:)(.*¶(?<-1>.)*(?(1)$))?(?!\2)[0:]
:$3:
\W+(a*)(b*)
$.1 $.2

```

Try it online! Link includes test case. Explanation:

```
s`1(.*)
;$1a

```

If there's a `1`, change it to `;` and append an `a` to the end of the input so that it's out of the way.

```
}+`(?<=(.)*)(1|;)(.*¶(?<-1>.)*(?(1)$))?(?!\2)[1;]
;$3;

```

Flood fill any more adjacent `1`s with `;`s.

```
}

```

Repeat until all of the islands of `1`s have been turned into `;`s.

```
s`0(.*)
:$1b

```

If there's a `0`, change it to `:` and append a `b` to the end of the input so that it's out of the way.

```
+`(?<=(.)*)(0|:)(.*¶(?<-1>.)*(?(1)$))?(?!\2)[0:]
:$3:

```

Flood fill any more adjacent `0`s with `:`s.

```
}

```

Repeat until all of the islands of `0`s have been turned into `:`s.

```
\W+(a*)(b*)
$.1 $.2

```

Separately count the numbers of islands of `1`s and `0`s.
> 3 votes

# Answer
# Jelly, ~~44~~ 42 bytes

```
ŒJfⱮ+€¥Ø.,UŻ¤œịḢ¥Ƈ⁹œịƇ€ɗⱮ,¬$fƇⱮ`ẎQ$€QƊÐL€Ẉ

```

Try it online!

A monadic link accepting a list of lists of integers as its argument and returning a list of the number of 1 and 0 islands in that order.

Thanks to @JonathanAllan for pointing out a bug in my code when there were islands that were diagonally adjoined.

## Explanation (needs updating)

### Step 1

Generate list of all matrix indices each with the indices of its neighbour to the right (unless on the right side) and down (unless at the bottom)

```
ŒJ            | Multi-dimensional indices (e.g. [1,1],[1,2],[1,3],[2,1],[2,2],[2,3])
      ¥       | Following as as a dyad:
  fⱮ          | - Filter the indices by each of:
    +€      ¤ |   - The indices added to the following
       Ø.     |     - 0,1
         ,U   |     - Paired with itself reversed [0,1],[1,0]
           Ż  |     - Prepended with zero 0,[0,1],[1,0]

```

### Step 2

Split these indices by whether there was 1 or 0 in input. Returns one list of indices with neighbours for 1s and another for 0s.

```
  Ƈþ   | Filter each member of the output of stage 1 using the following criteria:
œị   $ | - Corresponding value for the multi-dimensional indices in each of the following as a monad:
   ,¬  |   - The input paired with its inverse

```

### Step 3

Merge lists with members in common and output counts

```
           ƲÐL€  | For each of the outputs from stage 2, do the following as a monad and repeat until no changes
¹Ƈ               | - Filter out empty lists (only needed on first pass through but included here to save a byte)
  fƇⱮ`           | - Take each list of indices and filter the list of indices for those containing a match for any of them
        $€       | - For each resulting list of lists:
      Ẏ          |   - Tighten (concatenate top level of lists)
       Q         |   - Uniquify
          Q      | - Uniquify
               Ẉ | Finally output the lengths of the final lists

```
> 3 votes

# Answer
# Haskell, ~~228~~ ~~227~~ ~~225~~ 224 bytes

```
import Data.List
z=zipWith
a!b=div(max(a*a)(a*b))a
l x=z(!)(z(!)x(0:x))$tail x++[0]
s=(\x->length.($x).filter<$>[(>0),(<0)]).nub.(>>=id).(until=<<((==)=<<))((.)>>=id$transpose.map l).z(\i->z(\j x->2^i*j*(2*x-1))[1,3..])[1..]

```

Try it online!

Explanation:

The idea for this solution is as follows: Initialise the matrix with unique values in each cell, positive for `1` and negative for `0`. Then repeatedly compare each cell with its neighbours and, if the neighbour has the same sign but a number with a larger absolute value, replace the cell's number wit the neighbour's number. Once this hits a fixed point, count the number of distinct positive numbers for the number of `1` regions and the distinct negative numbers for the number of `0` regions.

In code:

```
s=(\x->length.($x).filter<$>[(>0),(<0)]).nub.(>>=id).(until=<<((==)=<<))((.)>>=id$transpose.map l).z(\i->z(\j x->2^i*j*(2*x-1))[1,3..])[1..]

```

can be separated into the preprocessing (assigning numbers to cells), the iteration, and the postprocessing (counting cells)

## Preprocessing

The preprocessing part is the function

```
z(\i->z(\j x->2^i*j*(2*x-1))[1,3..])[1..]

```

Which uses `z` as abbreviation for `zipWith` to shave off a few bytes. What we do here is zip the two dimensional array with integer indices at the rows and odd integer indices at the columns. We do this since we can build a unique integer from a pair of integers `(i,j)` using the formula `(2^i)*(2j+1)`. If we generate only odd integers for `j`, we can skip calculating the `2*j+1`, saving three bytes.

With the unique number, we now only have to multiply in a sign based on the value in the matrix, which is obtained as `2*x-1`

## Iteration

The iteration is done by

```
(until=<<((==)=<<))((.)>>=id$transpose.map l)

```

Since the input is in the form of a list of lists, we perform the neighbour comparison on each row, transpose the matrix, perform the comparison on each row again (which due to the transpose is what was the columns before) and transpose again. The code that accomplishes one of these steps is

`((.)>>=id$transpose.map l)`

where `l` is the comparison function (detailed below) and `transpose.map l` performs one half of the comparison and transposition steps. `(.)>>=id` performs its argument twice, being the pointfree form of `\f -> f.f` and by one byte shorter in this case due to operator precedence rules.

`l` is defined in the row above as `l x=z(!)(z(!)x(0:x))$tail x++[0]`. This code performs a comparison operator `(!)` (see below) on every cell with first its left neighbour, and then with its right neighbour, by zipping the list `x` with the right shifted list `0:x` and the left shifted list `tail x++[0]` in turn. We use zeroes to pad the shifted lists, since they can never occur in the preprocessed matrix.

`a!b` is defined in the row above this as `a!b=div(max(a*a)(a*b))a`. What we want to do here is the following case distinction:

* If `sgn(a) = -sgn(b)`, we have two opposing areas in the matrix and do not wish to unify them, so `a` stays unchanged
* If `sgn(b) = 0`, we have the corner case where `b` is padding and therefore `a` stays unchanged
* If `sgn(a) = sgn(b)`, we wish to unify the two areas and take the one with the bigger absolute value (for convenience's sake).

Note that `sgn(a)` can never be `0`. We accomplish this with the formula given. If the signs of `a` and `b` differ, `a*b` is less or equal to zero, while `a*a` is always greater than zero, so we pick it as the maximum and divide with `a` to get back `a`. Otherwise, `max(a*a)(a*b)` is `abs(a)*max(abs(a),(abs(b))`, and by dividing this by `a`, we get `sgn(a)*max(abs(a),abs(b))`, which is the number with the larger absolute value.

To iterate the function `((.)>>=id$transpose.map l)` until it reached a fixed point, we use `(until=<<((==)=<<))`, which is taken from this stackoverflow answer.

## Postprocessing

For postprocessing, we use the part

```
(\x->length.($x).filter<$>[(>0),(<0)]).nub.(>>=id)

```

which is just a collection of steps.

`(>>=id)` squashes the list of lists into a single list, `nub` gets rid of doubles, `(\x->length.($x).filter<$>[(>0),(<0)])` partitions the list into a pair of lists, one for positive and one for negative numbers, and calculates their lengths.
> 3 votes

# Answer
# Jelly, 23 bytes

```
,CµŒṪŒ!ŒṖ€ẎạƝ€§€ỊȦƲƇẈṂ)

```

Try it online!

Somewhat of a brute force approach, times out if there are more than \\$7\\$ \\$0\\$s or \\$7\\$ \\$1\\$s

## How it works

```
,CµŒṪŒ!ŒṖ€ẎạƝ€§€ỊȦƲƇẈṂ) - Main link. Takes a matrix B on the left
 C                      - Complement of each element
,                       - Pair; [B, 1-B]
  µ                   ) - Over each matrix M:
   ŒṪ                   -   Get the [x, y] coords of each element of 1 in M
     Œ!                 -   All permutations
         €              -   Over each permutation:
       ŒṖ               -     Get all partitions
          Ẏ             -   Tighten into a list of partitions
                  ƲƇ    -   Keep the partitions P for which the following is true:
             €          -     Over each partition:
            Ɲ           -       Over each overlapping pair:
           ạ            -         Absolute differences
               €        -     Over each difference:
              §         -       Get the sums
                Ị       -     Insignificant; Equal to 1 or 0
                 Ȧ      -     There are no zeros anywhere here?
                     Ẉ  -   Lengths of each
                      Ṃ -   Minimum

```
> 3 votes

# Answer
# Java 10, ~~359~~ ~~355~~ ~~281~~ ~~280~~ ~~261~~ ~~246~~ ~~240~~ 236 bytes

```
int[][]M;m->{int c[]={0,0},j=m[0].length,i=m.length*j,t;for(M=m;i-->0;c[~t&1]+=t<2?f(t,i/j,i%j):0)t=M[i/j][i%j];return c;}int f(int v,int x,int y){try{if(M[x][y]==v){M[x][y]|=2;f(v,x,y-f(v,x-f(v,x,y+f(v,x+1,y)),y));}}finally{return 1;}}

```

-74 bytes thanks to *@NahuelFouilleul*.
-10 bytes thanks to *@ceilingcat*.

Try it online.

**Explanation:**

```
int[][]M;              // Integer-matrix on class-level, uninitialized

m->{                   // Method with integer-matrix parameter and integer-array return-type
  int c[]={0,0}        //  Counters for the islands of 1s/0s, starting both at 0
      j=m[0].length,   //  Amount of columns
      i=m.length*j,    //  Index of the cells
      t;               //  Temp-value to decrease the byte-count
  for(M=m;             //  Set the class-level matrix to the input-matrix
      i-->0            //  Loop over the rows
      ;                //    After every iteration:
       c[~t&1]+=       //     Increase the corresponding counter by:
        t<2?           //      If the cell's value `t` is 0 or 1:
         f(t,i/j,i%j)  //       Call the recursive flood-fill method with value `t`
                       //       And increase the counter by 1
        :              //      Else:
         0;            //       Keep the counter the same by increasing by 0
    t=M[i/j][i%j];     //     Set `t` to the value of the current cell
  return c;}           //  After the nested loops: return the counters-array as result

// Recursive method with value and cell-coordinate as parameters,
// This method will flood-fill the matrix, where 0 becomes 2 and 1 becomes 3
int f(int v,int x,int y){
  try{if(M[x][y]==v){  //   If the cell contains the given value:
    M[x][y]|=2;        //    Fill the cell with 0→2 or 1→3 depending on the value
       f(v,x+1,y)      //    Do a recursive call downwards
      f(v,x,y+...)     //    Do a recursive call towards the right
     f(v,x-...,y)      //    Do a recursive call upwards
    f(v,x,y-...);}     //    Do a recursive call towards the left
                       //    (method `f` always result in 1, so we use it to our advantage to
                       //     save bytes here by nesting, instead of having four loose calls)
  }finally{return 1;}} //  Ignore any ArrayIndexOutOfBoundsExceptions with a finally-return,
                       //  which is shorter than manual checks
                       //  And return 1 to increase the counter

```
> 2 votes

# Answer
# Python 3, 167 bytes

```
def f(m):
 n=[0,0];i=-2
 for r in m:
  j=0;i+=1
  for c in r:n[c^1]+=1-((i>=0)*(m[i][j]==c)*(1+({*r[:j]}=={c})*({*m[i][:j]}=={c^1}))or(j>0)*(r[j-1]==c));j+=1
 print(n)

```

Try it online!

---

# Python 2, 168 bytes

```
def f(m):
 n=[0,0];i=-2
 for r in m:
	j=0;i+=1
	for c in r:n[c^1]+=1-((i>=0)*(m[i][j]==c)*(1+(set(r[:j])=={c})*(set(m[i][:j])=={c^1}))or(j>0)*(r[j-1]==c));j+=1
 print n

```

Try it online!

-2 bytes thanks to Kevin Cruijssen

+2 bytes formatting fix

# Explanation

A counter is kept for 0s and 1s. For each entry in the matrix, the following actions are performed:

* Incrase counter for current value by 1
* If the same value exists directly above or to the left, decrease by 1

This results in a false positive for left-aligned cases like

```
0 0 1
1 1 1

```

or

```
0 1
1 1

```

If such a situation arises, the counter is decreased by 1.

Return value is `[#1, #0]`
> 2 votes

# Answer
# Perl 5 (`-0777p`), 110 bytes

May be improved, uses a regex to replace `1` with `3`, then `0` with `2`.

```
/
/;$m="(.{@-})?";sub f{($a,$b,$c)=@_;1while s/$b$m\K$a|$a(?=$m$b)/$b/s||s/$a/$b/&&++$c;$c}$_=f(1,3).$".f(0,2)

```

TIO
> 1 votes

# Answer
# T-SQL 2008, 178 bytes

Input is a table variable.

> x and y are the coordinates
>
> v is the values 0 and 1(could also handle other numeric values)

The test data used in this example:

```
100
000
001

```

```
DECLARE @ table(x int, y int, v int)

INSERT @ values
(1,1,1),(1,2,0),(1,3,0),
(2,1,0),(2,2,0),(2,3,0),
(3,1,0),(3,2,0),(3,3,1)
SELECT*,y-x*99r INTO # FROM @
WHILE @@rowcount>0UPDATE #
SET r=b.r
FROM #,# b
WHERE abs(#.x-b.x)+abs(#.y-b.y)=1and #.v=b.v and #.r>b.r
SELECT v,count(distinct r)FROM #
GROUP BY v

```

**Try it online**
> 1 votes

# Answer
# , ~~194~~ 172 bytes

```
function(m,u=!1:2){for(i in 1:2){w=which(m==i-1,T)
N=1:nrow(w)
A=!!N
for(s in N){u[i]=u[i]+A[s]
while(any(s)){A[s]=F
s=c(N[as.matrix(dist(w))[s[1],]==1&A],s[-1])}}}
rev(u)}

```

Try it online!

Perform a depth-first search starting in each cell of the matrix that is equal to 1 (or zero).

* -2 bytes thanks to @Giuseppe
> 1 votes

---
Tags: code-golf, binary-matrix
---