title: Turn a string inside out

text:
# Question
Title: Turn a string inside out
A balanced string is a string of parentheses `()` so that every parenthesis is can be matched with another one. More rigorously they are the strings spanned by this grammar:

```
S → (S)S | ε

```

We can turn a string "inside out" by:

* Switching all occurrences of `(` and `)` with each other
* Moving characters from the front of the string to the back until the string is balanced again.

---

Lets do an example.

We start with the balanced string:

```
(()(())())

```

We then switch the parens to make

```
))())(()((

```

Then move characters from the front of the string to the back of the string until the string is balanced.

```
))())(()((
)())(()(()
())(()(())
))(()(())(
)(()(())()
(()(())())

```

Thats our result!

---

Note that some strings can be turned inside out in multiple ways, for example the string

```
(()())

```

When turned inside out can be either:

```
()(())

```

or

```
(())()

```

However every string has at least one solution.

# Task

Write a program to take a balanced string as input and output that string turned inside out. In cases where there may be multiple valid outputs you need only output one of them. You may use a different brace type (`<>`,`[]` or `{}`) if you so wish.

This is a competition so you should aim to minimize your size of your source code, as measured by bytes.

## Test Cases

```
(()())     -> ()(()), (())()
(()(())()) -> (()(())())
((())())() -> (()(()()))

```

# Answer
> 9 votes
# Haskell, ~~124~~ ~~120~~ ~~119~~ ~~117~~ ~~113~~ ~~110~~ ~~109~~ ~~106~~ ~~105~~ ~~104~~ ~~101~~ 98 bytes

*4 bytes saved thanks to bartavelle!*

*3 bytes saved thanks to Zgarb*

*1 byte saved thanks to Peter Taylor*

Here's a solution I worked out in Haskell. Its ~~ok right now~~ pretty good thanks to some help I received, but I'm looking to make this shorter, so feedback/suggestions are appreciated.

```
until(!0)g.map d
_!1=1<0
('(':a)!x=a!(x-1)
(_:a)!x=a!(x+1)
_!_=1>0
g(a:b)=b++[a]
d '('=')'
d _='('

```

Try it online!

## Explanation

This program defines 4 functions, the first `(!)` determines if a string is balanced. Its defined as follows:

```
_!1=1<0
('(':a)!x=a!(x-1)
(_:a)!x=a!(x+1)
_!_=1>0

```

This check assumes that the input has an equal number of open and close parens thanks to a suggestion from Peter Taylor.

The next `g` will rotate the string once.

```
g(a:b)=b++[a]

```

Then we have `d` which simply takes a paren and mirrors it

```
d '('=')'
d _='('

```

Finally we have the function we are concerned with. Here we use a pointfree representation of `until(!0)g` composed with `map d`, which maps `d` to the input and applies `g` until the result is balanced. This is the exact process described in the question.

```
until(!0)g.map d

```

# Answer
> 7 votes
# SOGL V0.12, ~~12~~ 11 bytes

```
↔]»:l{Ƨ()øŗ

```

Try it Here!

Explanation:

```
↔            mirror characters
 ]           do ... while the top of stack is truthy
  »            put the last letter at the start
   :           duplicate it
    l{         length times do
      Ƨ()        push "()"
         ø       push ""
          ŗ      replace ["()" with ""]
             if the string left on stack is empty (aka all matched parentheses could be removed), then stop the while loop

```

Note: `l{` could be replaced with  for 10 bytes, but, sadly, it isn't implemented.

# Answer
> 5 votes
## CJam (20 chars)

```
q1f^0X${~_}%_:e>#)m<

```

Online demo

or for the same char count

```
q1f^_,,{0W$@<~}$W=m<

```

Online demo

### Dissection

The two versions have a common header and footer

```
q1f^    e# Read input and toggle least significant bit of each character
        e# This effectively swaps ( and )

m<      e# Stack: swapped_string index
        e# Rotates the string to the left index characters

```

Then the bit in the middle obviously calculates how far it's necessary to rotate. Both of them use evaluation and rely on `(` being the CJam decrement operator and `)` being the increment operator.

```
0X$     e# Push 0 and a copy of the swapped string
{~_}%   e# Map: evaluate one character and duplicate top of stack
        e# The result is an array of the negated nesting depth after each character
_:e>    e# Copy that array and find its maximum value
#       e# Find the first index at which that value occurs
)       e# Increment

```

vs

```
_,,     e# Create array [0 1 ... len(swapped_string)-1]
{       e# Sort with mapping function:
  0W$@  e#   Rearrange stack to 0 swapped_string index
  <~    e#   Take first index chars of swapped_string and evaluate
}$      e# The result is an array of indices sorted by the negated nesting depth
W=      e# Take the last one

```

# Answer
> 3 votes
# JavaScript (ES6), ~~111~~ 105 bytes

(Saved 2 bytes thanks to @CraigAyre, 2 bytes thanks to @PeterTaylor, 2 bytes thanks to @Shaggy.)

```
s=>(r=[...s].map(c=>'()'[c<')'|0])).some(_=>r.push(r.shift(i=0))&&!r.some(c=>(i+=c<')'||-1)<0))&&r.join``

```

**Ungolfed:**

```
s=>(
  r=[...s].map(c=>'()'[c<')'|0]),  //switch "(" and ")"
  r.some(_=>(
    r.push(r.shift(i=0)),          //move last element to beginning of array, initialize i
    !r.some(c=>(i+=c<')'||-1)<0)   //check if balanced (i should never be less than 0)
  )),
  r.join``
)

```

**Test cases:**

```
let f=

s=>(r=[...s].map(c=>'()'[c<')'|0])).some(_=>r.push(r.shift(i=0))&&!r.some(c=>(i+=c<')'||-1)<0))&&r.join``

console.log(f('(()())'));      // ()(())
console.log(f('(()(())())'));  // (()(())())
console.log(f('((())())()'));  // (()(()()))
```

# Answer
> 3 votes
# Retina, ~~46~~ 38 bytes

```
T`()`)(
(.*?)(((\()|(?<-4>\)))+)$
$2$1

```

Try it online! Link includes test cases. Edit: Saved 8 bytes with help from @MartinEnder. The first stage simply transposes the parentheses, while the second stage looks for longest suffix that's a valid balanced prefix, which apparently is a sufficient condition for the rotation to be fully balanced. The balancing is detected using balancing groups. The construct `((\()|(?<-4>\)))+` matches any number of `(`s plus any number of `)`s as long as we have already (`<-4>`) seen as many `(`s. Since we're only looking for a valid prefix we don't have to match the remaining `)`s.

# Answer
> 2 votes
# Mathematica, 78 bytes

```
""<>{"(",")"}[[2ToCharacterCode@#-81//.x_/;Min@Accumulate@x<0:>RotateLeft@x]]&

```

# Answer
> 2 votes
# PHP, ~~110~~ 108 bytes

```
for($s=$argn;;$p?die(strtr($s,"()",")(")):$s=substr($s,1).$s[$i=0])for($p=1;$p&&$c=$s[$i++];)$p-=$c<")"?:-1;

```

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

**breakdown**

```
for($s=$argn;               # import input
    ;                       # infinite loop
    $p?die(strtr($s,"()",")(")) # 2. if balanced: invert, print and exit
    :$s=substr($s,1).$s[$i=0]   #    else: rotate string, reset $i to 0
)                               # 1. test balance:
    for($p=1;                   # init $p to 1
        $p&&$c=$s[$i++];)       # loop through string while $p is >0
        $p-=$c<")"?:-1;             # increment $p for ")", decrement else

```

# Answer
> 2 votes
# Python 3, ~~112~~ ~~103~~ 101 bytes

*-2 bytes thanks to @Mr.Xcoder*

```
k=y=input().translate(' '*40+')(')
while k:
 k=y=y[1:]+y[0]
 for _ in y:k=k.replace('()','')
print(y)

```

Try it online!

# Answer
> 2 votes
# Octave, 62 bytes

```
@(s)")("(x=hankel(s,shift(s,1))-39)(all(cumsum(2*x'-3)>=0)',:)

```

Try it online!

A function that takes the string as input and prints all results.

**Explanation:**

```
           hankel(a,shift(a,1))                                % generate a matrix of n*n where n= length(s) and its rows contain incresing circulraly shifted s
         x=...                 -39                             % convert matrix of "(" and ")" to a mtrix of 1 and 2
    ")("(x                        )                            % switch the parens
                                               2*x'-3          % convert [1 2] to [-1 1]
                                        cumsum(      )         % cumulative sum along the rows
                                    all(              >=0)'    % if all >=0
                                   (                       ,:) % extract the desired rows

```

# Answer
> 1 votes
# APL (Dyalog Unicode), ~~35~~ 30 bytes

*Golfed a new approach thanks to @Adám*

```
1⌽⍣{2::0⋄1∊⍎⍕1,¨⍺}')('['()'⍳⎕]

```

Try it online!

Golfing is in progress.

### Explanation

```
'()'⍳⎕              Find the index of each character of the input in the string '()'
                    (this is 1-indexed, so an input of '(())()' would give 1 1 2 2 1 2)
')('[...]           Find the index of the vector in the string ')('
                    This essentially swaps ')'s with '('s and vice versa
⍣                   On this new string, do:
 1⌽                   rotate it one to the left
                    Until this results in 1:
 1,¨⍺                 Concatenate each element of the argument with a 1
                      This inserts 1 one before each parenthesis
 ⍕                    Stringify it
 ⍎                    And evaluate it, if the parentheses are balanced, this produces no errors
 1∊                   Check if 1 belongs to evaluated value
                      If the parentheses were not matches during ⍎, this causes a syntax error
 2::0                 This catches a syntax error and returns 0
                      Essentially this code checks if the brackets are balanced or not

```

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

```
f=(s,t=s,u=t.replace(')(',''))=>u?t==u?f(s.slice(1)+s[0]):f(s,u):s.replace(/./g,c=>c<')'?')':'(')

```

Works by recursively rotating the input string until its transpose is balanced, then transposing it.

# Answer
> 0 votes
# Python 2, 99 bytes

```
r=[0];S=''
for c in input():b=c>'(';r+=[r[-1]+2*b-1];S+=')('[b]
n=r.index(min(r))
print S[n:]+S[:n]

```

Try it online!

## In function form for easy test cases:

## Python 2, 108 bytes

```
def f(s):
 r=[0];S=''
 for c in s:b=c>'(';r+=[r[-1]+2*b-1];S+=')('[b]
 n=r.index(min(r))
 return S[n:]+S[:n]

```

Try it online!

This uses a slightly different approach - instead of recursively rotating the string, if we think of the parens as incrementing and decrementing some balance counter, then a balanced string must never have a total sum of increments - decrements that is less than 0.

So we take

```
(()(())())

```

invert the parens:

```
))())(()((

```

and convert it to a list of sums of increments/decrements:

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

```

-3 is the minimum at index 4 (zero based); so we want to shift by that index+1. This guarantees that the cumulative increment/decrement will never be less than 0; and will sum to 0.

# Answer
> 0 votes
## Clojure, 118 bytes

```
#(loop[s(map{\(\)\)\(}%)](let[s(conj(vec(rest s))(first s))](if(some neg?(reductions +(map{\( 1\) -1}s)))(recur s)s)))

```

Returns a sequence of characters, so I'd call it like this:

```
(apply str (f "(()(())())"))
; "(()(())())"

```

First flips brackets, then loops as long as the cumulative sum of bracket count goes negative at some point of the sequence.

# Answer
> 0 votes
# brainfuck, 82 bytes

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

```

Try it online!

### Explanation

With each character read, a counter is modified as follows:

* The counter starts at 0.
* After each `)`, the counter increases by 1.
* After each `(`, the counter decreases by 1, unless the counter was 0, in which case the counter is unchanged.

Each prefix is a valid suffix of a balanced string (after inversion) if and only if this counter is 0. This code uses the longest such prefix to form the output.

```
,[                   Take input and start main loop
                     The cell one space right is the output cell (0 at this point),
                     and two spaces right is a copy of the previous counter value
  ++                 Add 2 to input
  [->->++<<]         Negate into output cell, and add twice to counter
  -[--->+>-<<]       Add 85 to output cell, and subtract 85 from counter
  >-->+              Subtract 2 from output cell and add 1 to counter
                     The output cell now has (81-input), and the counter has been increased by (2*input-80)
  [-[-<<+>>>>+<<]]   If the counter is nonzero, decrement and copy
,]
+[<<]                Go to the last position at which the counter is zero
>>>                  Go to following output character
[.[-]>>]             Output from here to end, clearing everything on the way
                     (Only the first one needs to be cleared, but this way takes fewer bytes)
<[<<]                Return to the same zero
<[<<]>>              Go to beginning of string
[.>>]                Output remaining characters

```

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


title: n * k = dd0d00d where d = ...?

text:
# Question
Title: n * k = dd0d00d where d = ...?
Given a positive integer ***n ≤ 500***:

* Find the *smallest* positive integer ***k*** such that all digits in the decimal representation of ***n\*k*** are either ***0*** or ***d***, with ***1 ≤ d ≤ 9***.
* Print or return ***d*** in less than 30 seconds (read more about that in the *Clarifications and rules* section).

## Easy examples

Here are the first 30 values of ***d***.

```
+----+-------+---------+---+    +----+-------+---------+---+
|  n |     k |   n * k | d |    |  n |     k |   n * k | d |
+----+-------+---------+---+    +----+-------+---------+---+
|  1 |     1 |       1 | 1 |    | 16 |     5 |      80 | 8 |
|  2 |     1 |       2 | 2 |    | 17 |   653 |   11101 | 1 |
|  3 |     1 |       3 | 3 |    | 18 |     5 |      90 | 9 |
|  4 |     1 |       4 | 4 |    | 19 |   579 |   11001 | 1 |
|  5 |     1 |       5 | 5 |    | 20 |     1 |      20 | 2 |
|  6 |     1 |       6 | 6 |    | 21 |    37 |     777 | 7 |
|  7 |     1 |       7 | 7 |    | 22 |     1 |      22 | 2 |
|  8 |     1 |       8 | 8 |    | 23 |  4787 |  110101 | 1 |
|  9 |     1 |       9 | 9 |    | 24 |    25 |     600 | 6 |
| 10 |     1 |      10 | 1 |    | 25 |     2 |      50 | 5 |
| 11 |     1 |      11 | 1 |    | 26 |    77 |    2002 | 2 |
| 12 |     5 |      60 | 6 |    | 27 |    37 |     999 | 9 |
| 13 |    77 |    1001 | 1 |    | 28 |    25 |     700 | 7 |
| 14 |     5 |      70 | 7 |    | 29 | 37969 | 1101101 | 1 |
| 15 |     2 |      30 | 3 |    | 30 |     1 |      30 | 3 |
+----+-------+---------+---+    +----+-------+---------+---+

```

## Not-so-easy examples

One particularity of this challenge is that some values are much harder to find than others -- at least with a purely brute-force approach. Below are some examples of ***n*** that lead to a high value of ***k***.

```
+-----+------------+---------------+---+    +-----+------------+---------------+---+
|   n |          k |         n * k | d |    |   n |          k |         n * k | d |
+-----+------------+---------------+---+    +-----+------------+---------------+---+
|  81 |   12345679 |     999999999 | 9 |    | 324 |   13717421 |    4444444404 | 4 |
| 157 |   64338223 |   10101101011 | 1 |    | 353 |   28615017 |   10101101001 | 1 |
| 162 |   13717421 |    2222222202 | 2 |    | 391 |  281613811 |  110111000101 | 1 |
| 229 |   43668559 |   10000100011 | 1 |    | 405 |   13717421 |    5555555505 | 5 |
| 243 |   13717421 |    3333333303 | 3 |    | 439 |   22781549 |   10001100011 | 1 |
| 283 |   35371417 |   10010111011 | 1 |    | 458 |   43668559 |   20000200022 | 2 |
| 299 |   33478599 |   10010101101 | 1 |    | 471 |   64338223 |   30303303033 | 3 |
| 307 |   32576873 |   10001100011 | 1 |    | 486 |   13717421 |    6666666606 | 6 |
| 314 |   64338223 |   20202202022 | 2 |    | 491 |  203871711 |  100101010101 | 1 |
| 317 | 3154574483 | 1000000111111 | 1 |    | 499 |   22244489 |   11100000011 | 1 |
+-----+------------+---------------+---+    +-----+------------+---------------+---+

```

## Clarifications and rules

* ***n\*k*** will always contain at least one digit ***d***, but it may contain no zero at all.
* This is , so the shortest code in bytes wins. However, your program or function must be able to return the result for any ***1 ≤ n ≤ 500*** in *less than 30 seconds* on middle-range hardware.
* Keep in mind that some values are harder to find than others. A program that would try to brute-force the value of ***k*** is unlikely to comply with the time-limit constraint (a good test case is ***n = 317***). There are significantly faster methods to find ***d***.

## Reference table

All values of ***d*** for ***1 ≤ n ≤ 500*** are listed below.

```
n       | d
--------+--------------------------------------------------
001-025 | 1 2 3 4 5 6 7 8 9 1 1 6 1 7 3 8 1 9 1 2 7 2 1 6 5
026-050 | 2 9 7 1 3 1 8 3 2 7 9 1 2 3 4 1 6 1 4 9 2 1 6 7 5
051-075 | 3 4 1 9 5 7 1 2 1 6 1 2 9 8 5 6 1 4 3 7 1 9 1 2 3
076-100 | 4 7 6 1 8 9 2 1 4 5 2 3 8 1 9 1 4 3 2 5 6 1 7 9 1
101-125 | 1 6 1 8 7 2 1 9 1 1 1 7 1 2 5 4 9 2 7 6 1 2 3 4 5
126-150 | 6 1 8 3 1 1 6 7 2 9 8 1 6 1 7 1 2 1 9 5 2 7 4 1 3
151-175 | 1 8 9 7 5 4 1 2 1 8 7 2 1 4 3 2 1 8 1 1 3 4 1 6 7
176-200 | 8 3 2 1 9 1 2 1 8 5 6 1 4 9 1 1 6 1 2 3 7 1 9 1 2
201-225 | 3 2 7 4 5 2 9 8 1 7 1 4 1 2 5 9 7 2 3 2 1 2 1 7 9
226-250 | 2 1 4 1 1 3 8 1 6 5 4 3 7 1 6 1 2 3 4 7 6 1 8 3 5
251-275 | 1 6 1 2 3 8 1 6 7 2 9 2 1 6 5 7 3 4 1 9 1 8 3 2 5
276-300 | 6 1 2 9 7 1 2 1 4 5 2 7 9 1 1 3 4 1 7 5 8 9 2 1 3
301-325 | 7 2 3 8 5 6 1 4 3 1 1 8 1 2 9 4 1 2 1 8 1 7 1 4 5
326-350 | 2 1 8 7 3 1 4 3 2 5 8 1 2 3 2 1 6 1 8 3 2 1 4 1 7
351-375 | 9 8 1 6 5 4 7 2 1 9 1 2 3 4 5 2 1 8 9 1 7 6 1 2 3
376-400 | 8 1 9 1 2 3 2 1 6 7 2 9 4 1 3 1 7 1 2 5 9 1 2 7 4
401-425 | 1 6 1 4 5 2 1 8 1 1 3 4 7 9 5 8 1 2 1 6 1 2 3 8 5
426-450 | 2 7 4 3 1 1 9 1 7 3 4 1 6 1 4 3 2 1 4 5 2 3 7 1 9
451-475 | 1 4 3 2 5 8 1 2 9 2 1 6 1 8 3 2 1 6 7 1 3 8 1 6 5
476-500 | 7 3 2 1 6 1 2 3 4 5 6 1 8 3 7 1 6 1 2 9 8 7 6 1 5

```

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

```
²B€Ḍ9×þF%Þ¹ḢQS

```

Quadratic runtime (under 25 seconds on TIO).

Try it online!

### Alternate version, 15 bytes

```
2ȷB€Ḍ9×þF%Þ¹ḢQS

```

Constant runtime (approx. 1 second on TIO).

Try it online!

### How it works

```
²B€Ḍ9×þF%Þ¹ḢQS  Main link. Argument: n

²               Take the square of n.
                This bound is high enough for all integers up to 500.
                In fact, The highest value we need is 1387 for input 471, so
                2000 (2ȷ) is also enough (and a lot faster).

 B€             Binary; convert 1, ..., 4159 to base 2.
   Ḍ            Undecimal; convert each digit array from base 10 to integer.
                This generates the array A of all positive integers up to n²
                whose decimal representations consist entirely of 1's and 0's.
    9×þ         9 multiply table; for each x in A, yield [x, 2x, ..., 8x, 9x].
       F        Flatten; concatenate the resulting arrays, yielding the vector
                V. Note that V contains all numbers that match the regex ^d[0d]*$
                in base 10, in ascending order.
          ¹     Identity; yield n.
        %Þ      Sort the entries for V by their remainders modulo n. This places
                multiples of n at the beginning. The sorting algorithm in stable,
                so the first element of sorted V is the smallest multiple of n.
           Ḣ    Head; extract the first element.
            Q   Unique; deduplicate its digits in base 10. This yields [d, 0].
             S  Take the sum, yielding d.

```

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

```
n=>{for(p=1;;p=k)for(d=0;d++<9;)for(k=p;k<p+p;k++)if(k.toString(2)*d%n<1)return d;}

```

Now returns `6` for `n=252`! I tried a recursive approach but it's also 83 bytes and crashes out for me for the harder numbers:

```
f=(n,p=1,d=1,k=p)=>k<p+p?k.toString(2)*d%n<1?d:f(n,p,d,k+1):d>8?f(n,p+p):f(n,p,d+1)

```

# Answer
> 4 votes
# Mathematica, ~~103~~ ~~100~~ 97 bytes

```
#&@@IntegerDigits[Sort[Join@@Table[Cases[FromDigits/@{0,i}~Tuples~13/#,_Integer],{i,9}]][[10]]#]&

```

*finds 317 in 0.39 sec*

Try it online copy/paste the code, add \[317\] at the end and press shift+enter to run

*-3 bytes from @JungHwan Min<br>-3 bytes from @Keyu Gan*

# Answer
> 2 votes
# Jelly, 21 bytes

```
9Rṭ€0ṗ€⁴ẎḌḍ@Ðf⁸ṢDFḟ0Ḣ

```

A monadic link returning the number OR a full program printing it.

A limited-range brute-forcer which takes less than 20 seconds for any **1 ≤ n ≤ 500** (less than 3 seconds for a 1 byte code cost - replace  with `13`).

**Try it online!**

### How?

```
9Rṭ€0ṗ€⁴ẎḌḍ@Ðf⁸ṢDFḟ0Ḣ - Link: number, n
9R                    - range of 9 = [1,2,3,4,5,6,7,8,9]
  ṭ€0                 - tack €ach to 0 -> [[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[0,9]]
       ⁴              - literal 16
     ṗ€               - Cartesian product for €ach
        Ẏ             - tighten (flatten by 1 level)
         Ḍ            - covert from decimal list to number (vectorises)
              ⁸       - chain's left argument (n)
            Ðf        - filter keep items for which this yields a truthy value:
          ḍ@          -   divisible? with swapped @rguments
               Ṣ      - sort
                D     - convert to decimal list (vectorises)
                 F    - flatten into a single list
                  ḟ0  - filter out zeros
                    Ḣ - head (get the first value)

```

# Answer
> 2 votes
# Python 2/3, ~~129~~ ~~128~~ 127 bytes

```
from itertools import*
lambda n:next(d for p in count()for d in range(1,10)for k in range(2**p,2*2**p)if d*int(bin(k)[2:])%n<1)

```

-1 byte: `count(0)``count()`
-1 byte: `==0``<1` since it can't be negative

# Answer
> 2 votes
# PHP, 87 bytes

```
for(;++$i<5e3;)for($n=10;$d=--$n*decbin($i);)($y&&$d>$y)|$d%$argn?:$x=$n.!$y=$d;echo$x;

```

Try it online!

# PHP, 89 bytes

```
for(;++$i<5e3;)for($n=10;$d=--$n*decbin($i);)$d%$argn?:$r[$d]=$n;krsort($r);echo end($r);

```

Try it online!

---
Tags: code-golf, arithmetic
---


title: Golf the Lucas Lehmer Primality Test

text:
# Question
Title: Golf the Lucas Lehmer Primality Test
your task is to write a program that uses the Lucas-Lehmer primality test to check whether an input number is prime or not. This prime number candidate has the form `2<sup>p</sup>-1` with p being prime. (Mersenne prime number)

## The Lucas-Lehmer-test

The n-th Mersenne number is prime if it is a divisor of the (n-1)-th Lucas-Lehmer number (LLN). You can calculate the LLN, similiar to the Fibonacci numbers, based on a recursive algorithm:

```
L<n> = (L<n-1>)^2 - 2

```

The LLN for 2 is 14. So, for p=3, LLN\<3-1\>=14

## Evaluation

* You have to submit a function that takes p as input (Remember: `2^p-1`)
* The shortest solution will win.
* Your solution has to use the Lucas-Lehmer test
* The code must be executable.
* Output: boolean value or 1=prime/0=not prime

## Tests:

```
p --> 2^p-1  --> LLN<n-1> --> ?
3 --> 7      --> 14  --> prime
5 --> 31     --> 37634 > prime (1214*31)

```

Good Luck

# Answer
> 1 votes
# 05AB1E, 11 bytes

```
o<4IÍFnÍ}sÖ

```

Try it online!

**Explanation**

```
o<            # push 2^p-1
  4           # push 4
   IÍF        # p-2 times do:
      nÍ      # square and subtract 2
        }     # end loop
         sÖ   # LLN(n) % Mp == 0

```

If we didn't need boolean value output we could save a byte with `4IÍFnÍIo<%` which returns **0** for prime and non-zero otherwise.

# Answer
> 4 votes
# Python 2, 51 bytes

```
p=input()
s=4
exec's=(s*s-2)%(2**p-1);'*(p-2)
s>0>x

```

Try it online!

Output is via exit code

# Answer
> 3 votes
# Haskell, ~~47 43~~ 41 bytes

Thanks @Kittsil for saving me 2 bytes!

```
f n=iterate(\v->mod(v^2-2)$2^n-1)4!!n-2<1

```

Try it online!

# Answer
> 3 votes
## Mathematica 44 Bytes

```
(s@3=14;s@n_:=Mod[s[n-1]^2-2,2^#-1];s@#==0)&

```

Test:

```
{#, %[#]} & /@ Prime[Range[2, 20]]

```

Too bad we can't use `MersennePrimeExponentQ` (22 bytes) since it doesn't appear to always use the LLT.

# Answer
> 2 votes
# Python 3, 61 bytes

```
l=lambda x:4*(x<3)or l(x-1)**2-2
f=lambda p:not l(p)%(2**p-1)

```

Try it online!

I'd like to note that the Lucas-Lehmer test only applies to ~~odd primes~~ Mersenne numbers of the form 2*p*-1 where *p* is an odd prime. This program uses a recursive function for the Lucas-Lehmer numbers, and then a function that just tests if the *n*-th LLN is divisible by M*n*.

# Answer
> 2 votes
# PHP, 58 bytes

```
for($s=4;++$i+1<$argn;)$s=($s**2-2)%(2**$argn-1);echo+!$s;

```

Try it online!

# Answer
> 1 votes
## APL, 28 bytes

```
{0=(¯1+2*⍵)|(¯2+×⍨)⍣(⍵-2)⊢4}

```

Explanation:

```
                         ⊢4    ⍝ to the number 4,
                   ⍣(⍵-2)      ⍝ apply this function ⍵-2 times,
            (¯2+×⍨)            ⍝ N*N - 2
   (¯1+2*⍵)|                   ⍝ modulo 2^⍵ - 1
 0=                            ⍝ is the result 0?

```

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


# Question
Title: Given a string and integer n, split the string at n characters, and print as follows:
Given a string and integer n, split the string at n character, and print as follows: Ex)

`laptop 3` should print `lap top`

`laptop 2` should print `la pt op` (see how it splits the string at every 2nd char)

Special cases:

`laptop 0` should print `laptop` (since we split at every 0th char, thus none)

`laptop 9` should print `laptop` (since length of laptop \< 9, so no splitting)

`bob 2` should print `bo b` (we split at the `o` (2nd char), but then there aren't enough characters after, so we just leave as is\`

You may assume n \>= 0

# Answer
# Japt, 7 bytes

```
òVªLl)¸

```

Test it online!

### Explanation

```
            Implicit: U, V = inputs
UòV   )     Split U into slices of length V.
   ªLl      If V is 0, instead use 100! (roughly 9.3326e+157).
       ¸    Join with spaces.
            Implicit: output result of last expression

```

9.3326e+157 is far larger than JavaScript's max string size of 9.0072e+15, so this will work for any input.
> 2 votes

# Answer
# JavaScript, ~~54~~ 47 bytes

```
s=>n=>n?eval(`s.match(/.{1,${n}}/g)`).join` `:s

```

```
f=
s=>n=>n?eval(`s.match(/.{1,${n}}/g)`).join` `:s

console.log(
    f('laptop')(0),
    f('laptop')(1),
    f('laptop')(2),
    f('laptop')(3),
    f('laptop')(4)
)
```
> 2 votes

# Answer
# PHP, 48 bytes

```
[,$s,$n]=$argv;echo$n?chunk_split($s,$n," "):$s;

```

Run with `-r`.
> 1 votes

# Answer
# Jelly,  ~~7~~  5 bytes

```
sW⁹?K

```

A full program printing the result (or a dyadic link returning a list of characters).

**Try it online!**

### How?

```
sW⁹?K - Main link: list of characters, a; number, n
   ?  - if:
  ⁹   -       chain's right argument = n (0 is not truthy, positive integers are)
s     - then: split a into chunks of length n (overflow kept like the challenge requires)
 W    - else: wrap a in a list
    K - join with spaces (the wrapped list becomes depth 1 again with no spaces)
      - implicit print

```
> 1 votes

# Answer
# CJam, 11 bytes

```
q~:X{X/S*}&

```

**Try it online!**

### How it works

```
q~           e# Read all input and evaluate. Pushes the string and the number n
  :X         e# Store n in variable X
    {    }&  e# If top of the stack (number n) is nonzero, run this block
     X       e# Push N again
      /      e# Split into pieces that long. Last piece may be shorter
       S     e# Push space
        *    e# Join using spaces
             e# Implicitly display

```
> 0 votes

# Answer
## Haskell, 33 bytes

```
import Data.List
s!n=chunksOf n s

```
> 0 votes

# Answer
# Python 2, ~~76~~ ~~67~~ 56 bytes

*-13 bytes thanks to ETHproductions and notjagan.*

```
lambda s,n:n and[s[i:i+n]for i in range(0,len(s),n)]or s

```

Try it online!

## Regex solution, 56 bytes

```
lambda s,n:re.findall('.{1,%i}'%n or len(s),s)
import re

```

Try it online!
> 0 votes

# Answer
# Mathematica, 114 bytes

```
d=StringRiffle;If[#2>(s=StringLength@#)||#2==0,#,k=d@StringPartition[#,#2];If[#2<=s/2,k,d[{k,StringDrop[#,#2]}]]]&

```
> 0 votes

# Answer
# QBIC, 27 bytes

```
_L;|~:|\b=a][1,a,b|?_sA,c,b

```

## Explanation

```
_L;|        set a as the length of A$ (input from cmd line)
~:|         IF b (input num from cmd line) is anything but 0 THEN (empty)
\b=a        ELSE (b==0) set b to the full length of A$
]           END IF
[1,a,b|     FOR c = 1; c <= LEN(A$); c = c + b
?_sA,c,b    PRINT a substring of A$, starting at c, running for b chars.
            NEXT is auto-added at EOF

```
> 0 votes

---
Tags: code-golf, string, source-layout
---


title: Write an ASP/Prolog/SAT flow solver

text:
# Question
Title: Write an ASP/Prolog/SAT flow solver
Flow Free is an addictive android game where you have to connect pairs of elements together via non-overlapping snakes and fill the entire grid. For a description, see here:

https://play.google.com/store/apps/details?id=com.bigduckgames.flow&hl=en

I have an ASP (answer set programming) solution which is only a couple rules and I don't think it's possible to phrase the same solution nearly as concisely as a SAT instance, but I'd be interested in being proven wrong.

Any language is fine, but I doubt it can be done concisely without running some sort of solver which is why I labeled it ASP/Prolog/SAT

Winner is fewest characters.

You may assume the problem is defined using the predicates:

```
v(V). % A vertex

a(V,W). % V and W are adjacent

c(C). % A color

s(V,C). % V is an endpoint of color C

```

Furthermore, the input satisfies

```
a(W,V) :- a(V,W) % Adjacencies are bidirectional

2{s(V,C) : v(V)}2 :- c(C). % Every color has exactly two endpoints

```

The solution predicate will be of the form

```
e(V,W,C).

```

Saying there's an edge between V and W of color C.

Edges must be bidirectional (of the same color). Each vertex must have edges to and from it of exactly one color. Endpoints have exactly one edge, all other vertices have exactly two edges. There are no loops, every snake must be traceable back to two endpoints.

Here's a sample input to test it on (5x5 Level 2 in the Regular Pack):

```
v(v11; v12; v13; v14; v15).
v(v21; v22; v23; v24; v25).
v(v31; v32; v33; v34; v35).
v(v41; v42; v43; v44; v45).
v(v51; v52; v53; v54; v55).

a(v11, v12).
a(v12, v13).
a(v13, v14).
a(v14, v15).
a(v12, v11).
a(v13, v12).
a(v14, v13).
a(v15, v14).
a(v11, v21).
a(v12, v22).
a(v13, v23).
a(v14, v24).
a(v15, v25).

a(v21, v22).
a(v22, v23).
a(v23, v24).
a(v24, v25).
a(v22, v21).
a(v23, v22).
a(v24, v23).
a(v25, v24).
a(v21, v31).
a(v22, v32).
a(v23, v33).
a(v24, v34).
a(v25, v35).
a(v21, v11).
a(v22, v12).
a(v23, v13).
a(v24, v14).
a(v25, v15).

a(v31, v32).
a(v32, v33).
a(v33, v34).
a(v34, v35).
a(v32, v31).
a(v33, v32).
a(v34, v33).
a(v35, v34).
a(v31, v41).
a(v32, v42).
a(v33, v43).
a(v34, v44).
a(v35, v45).
a(v31, v21).
a(v32, v22).
a(v33, v23).
a(v34, v24).
a(v35, v25).

a(v41, v42).
a(v42, v43).
a(v43, v44).
a(v44, v45).
a(v42, v41).
a(v43, v42).
a(v44, v43).
a(v45, v44).
a(v41, v51).
a(v42, v52).
a(v43, v53).
a(v44, v54).
a(v45, v55).
a(v41, v31).
a(v42, v32).
a(v43, v33).
a(v44, v34).
a(v45, v35).

a(v51, v52).
a(v52, v53).
a(v53, v54).
a(v54, v55).
a(v52, v51).
a(v53, v52).
a(v54, v53).
a(v55, v54).
a(v51, v41).
a(v52, v42).
a(v53, v43).
a(v54, v44).
a(v55, v45).

s(v11, yellow).
s(v45, yellow).
s(v41, blue).
s(v55, blue).
s(v51, red).
s(v43, red).
s(v42, green).
s(v33, green).

c(red; green; blue; yellow).

```

And to test the output

```
shouldbe(v33,v32,green).
shouldbe(v42,v32,green).
shouldbe(v43,v53,red).
shouldbe(v51,v52,red).
shouldbe(v55,v54,blue).
shouldbe(v41,v31,blue).
shouldbe(v45,v35,yellow).
shouldbe(v11,v12,yellow).
shouldbe(v12,v11,yellow).
shouldbe(v35,v45,yellow).
shouldbe(v31,v41,blue).
shouldbe(v54,v55,blue).
shouldbe(v52,v51,red).
shouldbe(v53,v43,red).
shouldbe(v32,v42,green).
shouldbe(v32,v33,green).
shouldbe(v53,v52,red).
shouldbe(v52,v53,red).
shouldbe(v54,v44,blue).
shouldbe(v31,v21,blue).
shouldbe(v35,v25,yellow).
shouldbe(v12,v13,yellow).
shouldbe(v13,v12,yellow).
shouldbe(v25,v35,yellow).
shouldbe(v21,v31,blue).
shouldbe(v44,v54,blue).
shouldbe(v44,v34,blue).
shouldbe(v21,v22,blue).
shouldbe(v25,v15,yellow).
shouldbe(v13,v14,yellow).
shouldbe(v14,v13,yellow).
shouldbe(v15,v25,yellow).
shouldbe(v22,v21,blue).
shouldbe(v34,v44,blue).
shouldbe(v34,v24,blue).
shouldbe(v22,v23,blue).
shouldbe(v15,v14,yellow).
shouldbe(v14,v15,yellow).
shouldbe(v23,v22,blue).
shouldbe(v24,v34,blue).
shouldbe(v24,v23,blue).
shouldbe(v23,v24,blue).

:-not e(V,W,C),shouldbe(V,W,C).
:-e(V,W,C),not shouldbe(V,W,C).

```

Also Level 21 5x5 should be the first puzzle with more than 1 solution (specifically, there are 9 solutions, not 40) To set up level 21, set the last few lines of the input to

```
s(v55, yellow).
s(v44, yellow).
s(v15, blue).
s(v45, blue).
s(v51, red).
s(v53, red).
s(v22, green).
s(v14, green).
s(v23, orange).
s(v43, orange).

c(red; green; blue; yellow; orange).

```

# Answer
> 4 votes
## ASP (clingo), 180 bytes

```
{e(V,W,C):a(V,W),c(C)}.r(V):-s(V,_).r(V):-r(W),e(W,V,_).o(V):-r(V),{e(V,W,_):v(W);s(V,_)}=2.:-e(V,_,C),e(V,_,D),C!=D.:-e(V,W,C),not e(W,V,C).:-v(V),not o(V).:-s(V,C),e(V,_,D),C!=D.

```

I am new to ASP, so I was excited to find this task, even if it is somewhat old. It was nice to see there were places for variations and an opportunity for golfing which was leading to the limits of my understanding (I hope it is still correct, it seems to be).

Here is a commented version:

```
% Select some edges e(V,W,C) s.t. V and W are adjacent and C is a color.
{e(V,W,C):a(V,W),c(C)}.

% Auxilary predicates:

% A vertex is reachable from an endpoint if
% it is an endpoint ...
r(V):-s(V,_).
% ... or it has an edge to it from a reachable vertex.
r(V):-r(W),e(W,V,_).

% A vertex is okay if it is reachable and either
% is an endpoint with one edge or is not an endpoint and has two edges.
% This is golfed to: the set of edges from V and endpoints V has
% cardinality 2.
o(V):-r(V),{e(V,W,_):v(W);s(V,_)}=2.

% Constraints:  We do not want ...

% edges from the same vertex with different colors:
:-e(V,_,C),e(V,_,D),C!=D.

% edges without their inverses:
:-e(V,W,C),not e(W,V,C).

% vertices that are not okay:
:-v(V),not o(V).

% edges from endpoints with the wrong color
:-s(V,C),e(V,_,D),C!=D.

% We're only interested in the e predicate:
#show e/3.

```

I don't know about different ASP solvers, but I used clingo, which in debian is contained in the gringo package.

If you have a problem in a file `prob` and my code in a file `solve`, call `clingo 0 prob solve`. For each solution, you will get the list of colored edges it uses (and all the other predicates if you use the golfed version which lacks the `#show` line). If you only want the number of solutions, add the option `-q`. If you only want to know if there is at least one solution, call without `0`.

---
Tags: code-golf
---


title: Make a string into a triangle

text:
# Question
Title: Make a string into a triangle
# Challenge

Given a string, make it into a triangle as shown below:

### Input

```
Hello, world!

```

### Output

```
H
He
Hel
Hell
Hello
Hello,
Hello,
Hello, w
Hello, wo
Hello, wor
Hello, worl
Hello, world
Hello, world!

```

The first line contains the first character of the string. The following lines contain one more character on each line, until the full length of the original string is reached.

If you receive a one character string, just output it.

You will never receive an empty string.

## Rules

* Standard loopholes apply, as usual
* This is , shortest solution wins.

# Answer
# Jelly, 3 bytes

```
;\Y

```

Try it online!
> 4 votes

# Answer
# brainfuck, 23 bytes

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

```

Try it online!
> 2 votes

# Answer
# Python, 33 bytes

```
f=lambda s:s and f(s[:-1])+s+'\n'

```

Try it online!
> 2 votes

# Answer
# J, 2 bytes

```
[\

```

Tailor made for J. This is just a scan `\` using the identity function `[`.

Try it online! -- Note the extra space in the output on line 1 is just a quirk of TIO in this case. It does not appear when run in jconsole.
> 2 votes

# Answer
# Haskell, 28 bytes

```
g[]=[]
g a=(g.init)a++'\n':a

```

Try it online!

Pretty straight forward. The base case is the empty string and each other case is a recursive call to `init` to the string with a newline and the input added to the end.

Here are my three attempts at a non-recursive solution all of which are exactly the same length.

```
g a=concat['\n':take x a|(x,_)<-zip[1..]a]
g a=concat['\n':take(fst x)a|x<-zip[1..]a]
g a=concat['\n':take x a|x<-[1..length a]]

```

And here's one that I found that is shorter than all of them

```
g a=do(x,_)<-zip[1..]a;'\n':take x a

```

I also came up with this very strange solution I quite like (its longer than the others though):

```
g a=zip[1..](a>>[a])>>=('\n':).uncurry take

```

Try it online!
> 2 votes

# Answer
# , 5 bytes

```
òÄ$xh

```

Try it online!
> 0 votes

# Answer
# Python 2, 49 bytes

```
lambda s:'\n'.join(s[:i]for i in range(len(s)+1))

```

Try it online!

Meanwhile, I'm like, how is this is impossible right now in my language?!
> 0 votes

# Answer
# Python 2, 34 bytes

```
s=''
for c in input():s+=c;print s

```

Try it online!
> 0 votes

# Answer
# C (gcc), 57 bytes

```
i;f(char*s){for(i=0;i<strlen(s);puts(""))write(1,s,++i);}

```

Try it online!
> 0 votes

# Answer
# Ruby, 31 + 1 = 32 bytes

Uses `-n` flag.

```
a=''
$_.each_char{|i|puts a<<i}

```

Try it online!
> 0 votes

# Answer
# Ruby, 35 bytes

```
->s{a='';s.each_char{|c|puts a<<c}}

```
> 0 votes

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


title: Maximum number of distinct substrings

text:
# Question
Title: Maximum number of distinct substrings
# Description

Given a length `n`, and an alphabet size `k>0`, your program must determine the number of strings with those parameters which have a maximal number of unique substrings. In the case of `k=2`, this generates OEIS A134457.

# Example

For example, `2210` has the substrings , `2`, `22`, `221`, `2210`, `2`, `21`, `210`, `1`, `10`, and `0`, for a total of 11. However, `2` appears twice, so it only has 10 unique substrings.

This is as many as possible for a length 4 string containing 3 different symbols, but it ties with 35 other strings for a total of 36 tieing strings including `0012`, `2101`, and `0121`. Therefore, for `n=4` and `k=3`, your program should output 36.

# Test Cases

```
n    k    output

0    5    1
1    3    3
5    1    1
9    2    40
2    3    6
5    5    120

```

# Answer
# Jelly, 9 bytes

```
ṗµẆQLµ€ML

```

Try it online!

Input in reversed order. Brute force.
> 2 votes

# Answer
# Pyth, 12 bytes

```
l.Ml{.:Z)^UE

```

Try it online.

Pure brute force.

### Explanation

* Implicit: append `Q` to the program.
* Implicit: read and evaluate a line of input (`n`) in `Q`.
* `E`: read and evaluate a line of input (`k`).
* `U`: get a range `[0, ..., k-1]`.
* `^`: get all `n`-length strings of `[0, ..., k-1]`.
* `.M`: find the ones that give a maximum for function `f(Z)`:
    + `.:Z`: find the substrings of `Z`
    + `{`: remove duplicates
    + `l`: get the number of unique substrings
* `l`: get the number of such strings
> 3 votes

# Answer
# Mathematica, 96 bytes

```
Last[Last/@Tally[Length@Union@Flatten[Table[Partition[#,i,1],{i,s}],1]&/@Tuples[Range@#2,s=#]]]&

```
> 2 votes

# Answer
## Haskell, 82 bytes

```
import Data.Lists
l=length
n#k=l$argmaxes(l.nub.powerslice)$mapM id$[1..k]<$[1..n]

```

Usage example: `9 # 2` -\> `40`.

How it works:

```
       [1..k]<$[1..n]  --  make a list of n copies of the list [1..k]
      mapM id          --  make a list of all combinations thereof, where
                       --  the 1st element is from the f1st list, 2nd from 2nd etc
  argmaxes             --  find all elements which give the maximum value for function:
     l.nub.powerslice  --    length of the list of unique sublists
l                      --  take the length of this list

```
> 2 votes

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


title: The sum of consecutive odd numbers

text:
# Question
Title: The sum of consecutive odd numbers
Although related challenges have been asked, this one is different to warrant its own question.

---

# Challenge

Given a positive integer, return the longest sequence of consecutive positive odd integers whose sum is the given integer. If no such sequence exists, you may report an error in whatever way makes sense for your language, including returning a falsy value or throwing an exception.

# Test Cases

```
  1 -> [1]
  2 -> []
  3 -> [3]
  4 -> [1, 3]
  5 -> [5]
  6 -> []
  9 -> [1, 3, 5] (note that [9] is not a valid answer)
 15 -> [3, 5, 7]
104 -> [23, 25, 27, 29] (note that [51, 53] is not a valid answer)

```

# Scoring

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

# Answer
> 11 votes
# Haskell, ~~67~~ ~~65~~ ~~63~~ ~~62~~ 58 bytes

Saved 4 bytes thanks to Julian Wolf

```
f x=[[2*n+1,2*n+3..2*m]|n<-[0..x],m<-[n..x],m^2-n^2==x]!!0

```

Try it online!

I check if the number can be expressed as he difference of two squares: `m^2-n^2`. I can then construct the list of consecutive odd numbers: `[2n+1,2n+3...2m-1]`. Note that because the minimum `n` is chosen, the longest list will be output

# Answer
> 9 votes
# Jelly,  ~~11~~  10 bytes

-1 byte thanks to Dennis (use the implicit range building of  \- replace `Rm2Ẇ` with `ẆḤ’`)

```
ẆḤ’S_¥Ðḟ⁸Ṫ

```

A monadic link returning a list of the summands if possible, or `0` if not.

**Try it online!**

### How?

```
ẆḤ’S_¥Ðḟ⁸Ṫ - Link: number, n
Ẇ          - all sublists (implicit range of input) note: ordered by increasing length
           -                i.e. [[1], [2], [3], ..., [1,2], [2,3], ..., [1,2,3], ...]]
 Ḥ         - double              [[2], [4], [6], ..., [2,4], [4,6], ..., [2,4,6], ...]]
  ’        - decrement           [[1], [3], [5], ..., [1,3], [3,5], ..., [1,2,5], ...]]
        ⁸  - link's left argument, n
      Ðḟ   - filter out items for which the following yields a truthy value:
     ¥     -   last two links as a dyad:
   S       -     sum
    _      -     subtract the right from the left = sum - n
         Ṫ - tail (last and hence longest such run)

```

# Answer
> 9 votes
# Python 2, ~~66~~ 62 bytes

```
f=lambda n,k=0,*r:n-sum(r)and f(n,k+1,*range(k%n|1,k/n,2))or r

```

Exits with a *RuntimeError* (maximum recursion depth exceeded) if there's no solution.

Try it online!

# Answer
> 8 votes
## JavaScript (ES7), ~~87~~ ~~86~~ ~~85~~ 81 bytes

Returns a comma-delimited list of integers, or `0` if no solution exists.

```
n=>(g=(s,k,x=n+s)=>(x**.5|0)**2-x?k>n?0:g(s+k,k+2):(n-=k)?k+','+g(-n,k+2):k)(0,1)

```

### How?

We first look for the smallest perfect square ***s*** such that ***x = n + s*** is another perfect square.

If ***s*** exists, ***n*** is the difference ***x - s*** of 2 perfect squares, which can be written as the difference of 2 sequences of consecutive odd numbers. We then build the resulting list.

Example:

For ***n = 104***:

We find ***s = 11² = 121*** which satisfies ***x = n + s = 225 = 15²***

Then:

***15² = 1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 + 17 + 19 + 21 + 23 + 25 + 27 + 29***
***11² = 1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 + 17 + 19 + 21***
***104 = 15² - 11² = 23 + 25 + 27 + 29***

```
let f =

n=>(g=(s,k,x=n+s)=>(x**.5|0)**2-x?k>n?0:g(s+k,k+2):(n-=k)?k+','+g(-n,k+2):k)(0,1)

console.log(f(1))   // -> 1
console.log(f(2))   // -> 0
console.log(f(3))   // -> 3
console.log(f(4))   // -> 1,3
console.log(f(5))   // -> 5
console.log(f(6))   // -> 0
console.log(f(9))   // -> 1,3,5
console.log(f(15))  // -> 3,5,7
console.log(f(104)) // -> 23,25,27,29
```

# Answer
> 7 votes
# 05AB1E, ~~9~~ 8 bytes

-1 byte thanks to Emigna

```
ÅÉŒʒOQ}н

```

Explanation:

```
ÅÉ           Generate a list of odd numbers up to, and including, the input
  Œ          Substrings
   ʒ         Only keep values
    O          where the sum
     Q         equals the input
       }     End
             For 9, the result would look like this:
             [[1, 3, 5], [9]]
        н    Get the first value

```

On invalid input, outputs nothing.

Try it online!

# Answer
> 6 votes
# Haskell, ~~61~~ 60 bytes

*Thanks to @maple\_shaft for shaving off 1 byte*

```
f n=[k|r<-[1,3..],s<-[r,r+2..n],k<-[[r,r+2..s]],sum k==n]!!0

```

Try it online!

Uses the fact that the longest run will always be the run that starts with the lowest number.

I wanted to do something with arithmetic in stead of brute-forcing `k`, but `fromInteger` seems to kill it.

# Answer
> 4 votes
# Python, 67 bytes

```
f=lambda n,R=[1]:n-sum(R)and f(n,[R+[R[-1]+2],R[1:]][sum(R)>n])or R

```

Try it online!

I copied my answer from the previous consecutive sum challenge and changed the `+1` to `+2`. Who knew that golfed code could be so modular?

An oddly straightforward strategy: search for the interval `R` with the desired sum.

* If the sum is too small, shift the right endpoint of the interval up 2 by appending the next number 2 above it.
* If the sum is too large, shift up the left endpoint by removing the smallest element
* If the sum is correct, output `R`.

Since the bottom end of the interval only increases, longer intervals are found before shorter ones. If no possible interval can be found, terminates with IndexError.

# Answer
> 4 votes
# JavaScript (ES6), ~~65~~ 64 bytes

```
f=(a,i=1)=>a>i?(c=f(a-i,i+=2))[0]==i?[i-2,...c]:f(a,i):a<i?0:[i]

```

Returns an array if there's a solution, or 0 for no solution.

This is a highly inefficient yet *golfy* solution to the problem.

It searches for the first solution using `a-i` and `i=1`, even if it doesn't work up the recursive stack. If that solution doesn't begin with `i+2`, then we recursively search for the first solution using `a` and `i+2`.

**Ungolfed**

```
f=(a,i=1)=>
  a > i ?
    (c = f(a - i, i += 2))[0] == i ?
      [i-2, ...c] :
      f(a, i) :
  a < i ?
    0 :
    [i]

```

**Test cases:**

```
f=(a,i=1)=>a>i?(c=f(a-i,i+=2))[0]==i?[i-2,...c]:f(a,i):a<i?0:[i]

console.log(JSON.stringify(f(1)));   //[1]
console.log(JSON.stringify(f(3)));   //[3]
console.log(JSON.stringify(f(4)));   //[1, 3]
console.log(JSON.stringify(f(5)));   //[5]
console.log(JSON.stringify(f(6)));   //[0]
console.log(JSON.stringify(f(9)));   //[1, 3, 5]
console.log(JSON.stringify(f(15)));  //[3, 5, 7]
console.log(JSON.stringify(f(104))); //[23, 25, 27, 29]
```

For an idea of how inefficient this is, the solution to `f(104)` requires 69,535 recursive calls. The stack is never more than 51 levels deep, so no problem with stack overflow.

The solution to `f(200)` requires 8.6 *million* recursive calls, with a stack 99 levels deep. (Its solution is `[11,13,15,17,19,21,23,25,27,29]`.)

Here's a visual representation of the program running:

```
r=0;
output=o=>setTimeout(_=>O.textContent += o + '\n', r++ * 20);

f=(a,i=1,s='',o = s + 'a=' + a + '; i=' + i + ';')=>
(
  output(o),
  a > i ?
    (c = f(a - i, i += 2, s + '  '))[0] == i ? (
      output(o + ' a > i; [i-2, ...c] = [' + [i-2, ...c] + '];'),
      [i-2, ...c]
    ) : (
      output(o + ' a > i; c=[' + c + ']; ' + 'c[0]+2 != i ... dead end\n' + s + 'trying a, i+2:'),
      f(a, i, s)
    ) :
  a < i ? (
    output(o + ' a < i ... dead end'),
    0
  ) : (
    output(o + ' a == i;'),
    [i]
  )
)

f(21);  //[5, 7, 9]
```

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

# Answer
> 3 votes
# Python 3, 190 81 Bytes

```
`def c(q,l,i):
    if sum(l)0:
        l.append(i)
        return c(q,l,i+2)
    elif sum(l)>q:
        l.pop(0)
        return c(q,l,i)
    else:
        print(l)
c(q,[1],1)`
```

```
c=lambda q,l=[1]:c(q,l+[l[-1]+2])if(sum(l)<q)*l else c(q,l[1:])if sum(l)>q else l

```

Thanks to @ovs and @musicman523

# Answer
> 3 votes
# Python 2.7, 109 108 97 bytes

11 bytes down, Thanks to Erik the Outgolfer.

This is my first code golf!

```
def f(N):
 for n in range(N):
    x=(n*n+N)**.5-n
    if x%1==0:return[2*(k+n)+1for k in range(int(x))]

```

## How it works

I used the well known identity that `1 + 3 + 5 + ... + (2n - 1) = n²`

Take the case of `15`

```
15 = 3 + 5 + 7 = (1 + 2) + (3 + 2) + (5 + 2) = (1 + 3 + 5) + 3×2 = 3² + 3×2

```

In general, if there are *x* terms starting from `2n + 1`, like

```
(2n + 1) + (2n + 3) + (2n + 5) ... (2n + (2x-1))

```

It is equal to `2nx + x²`

If `N` is the input integer, the problem reduces to finding maximum `x` such that

```
x² + 2nx - N = 0

```

It is a quadratic equation with solution

```
x = sqrt(n² + N) - n

```

The longest sequence is one with largest `x`. The program iterates `n` from `0` to `N` and when it find that `x` is an integer, it creates a list of `(2n + 1) + (2n + 3) + (2n + 5) ... (2n + (2x-1))` and returns it.

# Answer
> 2 votes
# QBIC, 47 bytes

```
{_Cg=q┘q=q+2~g>:|_Xp\?g,[q,a,2|?b,┘g=g+b~g=a|_X

```

This tries to count all the odd numbers from one until its sum is `n`. If it passes `n`, reset the loop, increase 1 to 3 and try again. Quit, printing 0, if at the start of the loop our number `> n`.

## Explanation

```
{       Do infinitely
_C      Clear the screen (we basically print every run of odd numbers, but clear out everything that doesn't sum up to n)
g=q     Set g to the first num of this cycle (q starts as 1 in QBIC)
┘       (Syntatcic linebreak)
q=q+2   Raise q to the next odd number, this sets up both the next outer loop as well as a coming FOR loop
~g>:|   If we start out with a number > n (read as 'a' from the cmd line)
_Xp     THEN quit, printing 0 (the value of the number var 'p')
\       ELSE
[q,a,2| FOR b = q, b <= n, b+=2
?b,┘    PRINT b followed by a tab
g=g+b   Add 'b' to running total 'g'
~g=a|   and if that lands us on 'n'
_X      QUIT (printing nothing: everything is already printed)

```

# Answer
> 1 votes
# Python 2, ~~91~~ 90 bytes

*-1 byte thanks to @CMcAvoy*

```
lambda n,r=range:[r(i,j+1,2)for i in r(1,n+1,2)for j in r(i,n+1,2)if(i+j)*(2+j-i)==4*n][0]

```

Try it online!

# Answer
> 1 votes
# PHP, 73 bytes

no solution is a infinite loop

```
for($e=-1;$s-$i=$argn;)$s+=$s<$i?$n[]=$e+=2:-array_shift($n);print_r($n);

```

Try it online!

# PHP, 83 bytes

prints nothing for no solution

every input mod 4 == 2 has no solution

```
for($e=-1;($i=$argn)%4-2&&$s-$i;)$s+=$s<$i?$n[]=$e+=2:-array_shift($n);print_r($n);

```

Try it online!

# Answer
> 1 votes
# , 90 bytes

```
f=function(x,y=1)'if'(length(w<-which(cumsum(r<-y:x*2-1)==x)),r[1:w],'if'(y>x,0,f(x,y+1)))

```

Try it online!

Uses a recursive function that test sequence cumulative sum of y:x converted to an odd number sequence. y is incremented on each recursion until it exceeds x. The first sequence which sums to the target will be returned.

# Answer
> 1 votes
# Python 2, 89 bytes

```
lambda n,r=range:[v for v in[r(1,n+1,2)[i:j]for i in r(n)for j in r(n+1)]if sum(v)==n][0]

```

An unnamed function taking a positive integer, `n`, and returning the result if it exists and raising an `IndexError` otherwise.

**Try it online!**

Creates a list of all the relevant odd numbers with `r(1,n+1,2)` which is `range(start=1, stop=n+1, step=2)`; creates all the relevant sub-slices (plus some empty ones) by slicing that from `i` inclusive to `j` exclusive with `[i:j]` across `i` in **\[0,n)** using `r(n)` and `j` in **\[0,n\]** using `r(n+1)` (the empty ones when `i>=j` or `i` is out of bounds); filters for those with the correct sum with `if sum(v)==n`; returns the first (and hence longest) such slice using `[0]`.

# Answer
> 1 votes
# Pyth, 11 bytes

```
efqsTQ.:%2S

```

Try it here.

# Answer
> 0 votes
# Python 2, ~~122~~ ~~121~~ ~~119~~ 115 bytes

*-1 byte thanks to musicman523. -4 bytes thanks to Step Hen. haha*

```
def f(n,R=range):r=R(1,n,2);print[i for w in R(1,len(r)+1)for i in[r[j:j+w]for j in R(len(r)-w+1)]if sum(i)==n][-1]

```

Try it online!

# Answer
> 0 votes
# Python 3, 93 bytes

```
lambda n,r=range:[[*r(s,e+1,2)]for s in r(1,n+1,2)for e in r(s,n+1,2)if(s+e)*(2+e-s)==4*n][0]

```

Try it online!

Only thing special I did was noting that `(s+e)*(2+e-s)==4*n` is equivalent to `sum(range(s,e+1,2))==n`, and though they're the same size when `r=range`, the former can be placed closer to the `if` statement.

# Answer
> 0 votes
# Python 3, 185 bytes

```
def f(s):
  d={k:v for k,v in{a:(1-a+((a-1)**2+4*s)**(.5))/2 for a in range(1,s,2)}.items()if int(v)==v};m=max(d.keys(), key=(lambda k: d[k]));return list(range(int(m),int(m+2*d[m]),2))

```

Try it online!

---

As for how this works, I tried to go for a bit more elegant solution than a simple brute force search. I rearranged the formula for the sum of an arithmetic sequence and applied the quadratic formula to get the expression `(1-a+((a-1)**2+4*s)**(.5))/2`, which appears in the code. What the expression calculates is, given a desired sum `s` and a first term for of arithmetic sequence `a`, the length of the sequence. These lengths are stored in a dictionary as values to the first terms as keys.

Next, all non-integer values are removed from the dictionary, as those represent invalid sequences. From there, the largest value is identified with `max(d.keys(), key=(lambda k: d[k]))` and the sequence of odd numbers at that position and at that length is made with `list(range(int(m),int(m+2*d[m]),2))`.

---

I'm looking for help golfing this if you see anything. I was more interested in seeing how well I could do with a non-trivial algorithm; my answer is nearly twice as long as the best Python solution.

# Answer
> 0 votes
# Mathematica, 56 bytes

```
Last@Cases[Subsequences@Table[n,{n,1,#,2}],x_/;Tr@x==#]&

```

`Function` with first argument `#`. `Table[n,{n,1,#,2}]` computes the list of positive odd numbers less than or equal to `#`. `Subsequences` returns all subsequences of that list ordered by increasing length. We then take the `Cases` which match `x_/;Tr@x==#`, that is, sequences `x` such that their sum `Tr@x` is equal to the input `#`. We then take the `Last` such sequence.

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

```
n=>(g=s=>s?s>0?g(s-(u+=2)):g(s+l,l+=2):u-l?l+' '+g(s,l+=2):u)(n-1,l=u=1)

```

Returns a space-separated string of odd numbers or throws on invalid input. 84 byte version that returns an (empty when appropriate) array:

```
n=>n%4-2?(g=s=>s?s>0?g(s-(u+=2)):g(s+l,l+=2):u-l?[l,...g(s,l+=2)]:[u])(n-1,l=u=1):[]

```

Explanation: Loosely based on @Cabbie407's awk solution to Sums of Consecutive Integers except I was able to save some bytes by using recursion.

# Answer
> 0 votes
# PHP, 78 bytes

```
for($b=-1;$s-$argn;)for($n=[$s=$x=$b+=2];$s<$argn;)$s+=$n[]=$x+=2;print_r($n);

```

infinite loop if no solution. insert `?$b>$argn+2?$n=[]:1:0` after `$s-$argn` to print empty array instead.

Run with `-nR` or try it online.

# Answer
> 0 votes
# Excel VBA, 139 Bytes

`Sub`routine that takes input `n` of expected type integer and reports the longest sequence of consecutive odd numbers to cell `[A1]`

```
Sub a(n)
For i=1To n Step 2
s=0
For j=i To n Step 2
s=s+j
If s=n Then:For k=i To j-1 Step 2:r=r &k &"+":Next:[A1]=r &j:End
Next j,i
End Sub

```

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

```
(i)=>{int s,j,b=1,e=3;for(;;){var o="";s=0;for(j=b;j<e;j+=2){s+=j;o+=j+" ";}if(s==i)return o;s=s<i?e+=2:b+=2;if(b==e)return"";}};

```

Outputs numbers in a string, space delimited (any other character would just require changing the `" "`). Input with no solution returns an empty string (though if running forever without error is a valid way to indicate no solution then 17 bytes could be saved by removing `if(b==e)return"";`).

Algorithm is:

1. Start with \[1\]
2. If the sum is equal to the target, return the list
3. If the sum is less than the target, add the next odd number
4. If the sum is greater than the target, remove the first item
5. If the list is empty, return it
6. Repeat from 2

# Answer
> 0 votes
## C++, 157 -\> 147 Bytes

---

**-10 Bytes thanks to DJMcMayhem**

will return 0 if there's no answer, 1 otherwise

the last line it prints is the answer

```
int f(int n){for(int i=1;;i+=2){int v=0;for(int k=i;;k+=2){v+=k;std::cout<<k<<" ";if(v==n)return 1;if(v>n)break;}if(i>n)return 0;std::cout<<"\n";}}

```

ungolfed:

```
int f(int n)
{
    for (int i = 1;; i += 2)
    {
        int v = 0;
        for (int k = i;; k += 2)
        {
            v += k;
            std::cout << k << " ";
            if (v == n)
                return 1;
            if (v > n)
                break;

        }
        if (i > n)
            return 0;
        std::cout << "\n";
    }
}

```

this is my first code golf ^^

# Answer
> 0 votes
# Kotlin, 152 bytes

```
fun f(a:Double){var n=Math.sqrt(a).toInt()+1;var x=0;while(n-->0){if(((a/n)-n)%2==0.0){x=((a/n)-n).toInt()+1;while(n-->0){println(x.toString());x+=2}}}}

```

Try it online (Wait 4-5 seconds, compiler is slow)

Ungolfed

```
fun f(a: Double){
    var n=Math.sqrt(a).toInt()+1;
    var x=0;

    while(n-->0){
        if(((a/n)-n)%2==0.0){
            x=((a/n)-n).toInt()+1;

            while(n-->0){
                println(x.toString());
                x+=2;
            }

        }
    }
}

```

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


title: A game of atomic proportions

text:
# Question
Title: A game of atomic proportions
Your task make a bot that plays Atomas, with the highest score.

## How the game works:

The gameboard starts with a ring of 6 "atoms", with numbers ranging from `1` to `3`. You can "play" an atom between two atoms, or on another atom, depending on the atom itself.

You can either have a normal atom, or a special atom.

### The normal atom:

You can play a normal atom between any two available atoms on the board.

You start off with atoms in the range `1 to 3`, but the range increases by 1 once every 40 moves (so after 40 moves, the range becomes `2 to 4`).

If there are atoms on the board that are lower than the range, it has a `1 / no. of atoms of that number on the board` chance of spawning.

Let's say you have a `2` to play, and the board looks like this:

```
   1 1 2 1

```

Let's place the `2` to the right of the `1`.

The board now becomes:

```
   1 1 2 1 2

```

**Note: the board wraps around, so the `1` on the far left is actually next to the `2` on the far right. This will be important later.**

There are 4 types of "special" atoms, and they are:

### The `+` atom:

This atom is played between two atoms. It has a 1 in 5 chance of spawning.

If the atoms on both sides of the `+` atom are the same, fusion occurs. Here's how it works:

```
The two atoms fuse together to create an atom one higher.
(So, two 3 atoms fuse together to form one 4 atom.)
While the atoms on both sides of the fused atom are equal:
    If the atoms on the side >= the fused atom:
        The new fused atom = the old fused atom's value + 2.
    If the atoms on the side < the fused atom:
        The new fused atom = the old fused atom's value + 1.

```

Example:

```
   1 1 3 2 2 3  (the 1 on the left-hand side "wraps back"
                 to the 3 on the right-hand side)

Let's use the + on the two 2's in the middle.

-> 1 1 3 3 3    (the two 2's fused together to make a 3)
-> 1 1 5        (the two 3's fused with the 3, and because 3 >= 3,
                 the new fused atom = 3 + 2 = 5)
-> 6            (the two 1's fused with the 5, since the board wraps,
                 and because 1 < 5, the new fused atom = 5 + 1 = 6)

Because the atoms on the sides of the 6 don't exist, fusion stops,
and the board is now [6].

```

If the atoms on both sides of the `+` atom are different, then the `+` stays on the board.

Example:

```
   1 3 2 3 1 1

Let's use the + on the 2 and 3 in the middle.

-> 1 3 2 + 3 1 1 (2 != 3, so the + stays on the board)

```

### The `-` atom:

This atom is played on another atom. It has a 1 in 10 chance of spawning.

The `-` atom removes an atom from the board, and gives you a choice to either:

* play the removed atom next round, or
* turn it into a + atom to play next round.

Example:

```
   1 3 2 3 1 1

Let's use the - on the left-hand 2.

-> 1 3 3 1 1    (the 2 is now removed from the board)

Let's turn it into a +, and place it in between the 3's.

-> 1 4 1 1      (the two 3's fused together to make a 4)
-> 5 1          (the two 1's fused with the 4, and because 1 < 4,
                 the new fused atom = 4 + 1 = 5)

```

### The black `+` atom (`B`):

This atom is played between 2 atoms. It has a 1 in 80 chance of spawning, and only spawns once your score \> 750.

This atom is basically the same as the `+` atom, except that it fuses any two atoms together, even `+`'s. From then on, it follows the `+` rule (it only fuses atoms together if the atoms on both sides of the fused atom are equal).

The fused atom as a result of the black `+` is equal to:

* the higher number atom in the fusion + 3
* `4` if the two fused atoms are `+`'s

Example:

```
   1 3 2 1 3 1

Let's use the black + on the 2 and 1 in the middle.

-> 1 3 5 3 1    (the 2 and 1 fused together to make a 2 + 3 = 5)
-> 1 6 1        (+ rule)
-> 7            (+ rule)

```

Another example:

```
   2 + + 2

Let's use the black + on the two +'s.

-> 2 4 2        (the two +'s fused together to make a 4)
-> 5            (+ rule)

```

### The clone atom (`C`):

This atom is played on another atom. It has a 1 in 60 chance of spawning, and only spawns once your score \> 1500.

The clone atom allows you to choose an atom, and play it next round.

Example:

```
   1 1 2 1

Let's use the clone on the 2, and place it to the right of the 1.

-> 1 1 2 1 2

```

Here is my build of the game, in Python 2:

```
import random
import subprocess

logs='atoms.log'
atom_range = [1, 3]
board = []
score = 0
move_number = 0
carry_over = " "
previous_moves = []

specials = ["+", "-", "B", "C"]

def plus_process(user_input):
    global board, score, previous_moves, matches
    previous_moves = []
    matches = 0

    def score_calc(atom):
        global score, matches
        if matches == 0:
            score += int(round((1.5 * atom) + 1.25, 0))
        else:
            if atom < final_atom:
                outer = final_atom - 1
            else:
                outer = atom
            score += ((-final_atom + outer + 3) * matches) - final_atom + (3 * outer) + 3
        matches += 1

    if len(board) < 1 or user_input == "":
        board.append("+")
        return None
    board_start = board[:int(user_input) + 1]
    board_end = board[int(user_input) + 1:]
    final_atom = 0
    while len(board_start) > 0 and len(board_end) > 0:
        if board_start[-1] == board_end[0] and board_end[0] != "+":
            if final_atom == 0:
                final_atom = board_end[0] + 1
            elif board_end[0] >= final_atom:
                final_atom += 2
            else:
                final_atom += 1
            score_calc(board_end[0])
            board_start = board_start[:-1]
            board_end = board_end[1:]
        else:
            break
    if len(board_start) == 0:
        while len(board_end) > 1:
            if board_end[0] == board_end[-1] and board_end[0] != "+":
                if final_atom == 0:
                    final_atom = board_end[0]
                elif board_end[0] >= final_atom:
                    final_atom += 2
                else:
                    final_atom += 1
                score_calc(board_end[0])
                board_end = board_end[1:-1]
            else:
                break
    if len(board_end) == 0:
        while len(board_start) > 1:
            if board_start[0] == board_start[-1] and board_start[0] != "+":
                if board_start[0] >= final_atom:
                    final_atom += 2
                else:
                    final_atom += 1
                score_calc(board_start[0])
                board_start = board_start[1:-1]
            else:
                break
    if matches == 0:
        board = board_start + ["+"] + board_end
    else:
        board = board_start + [final_atom] + board_end
        for a in range(len(board) - 1):
            if board[a] == "+":
                if board[(a + 1) % len(board)] == board[a - 1]:
                    board = board[:a - 1] + board[a:]
                    plus_process(a)
                    break

def minus_process(user_input, minus_check):
    global carry_over, board
    carry_atom = board[int(user_input)]
    if user_input == len(board) - 1:
        board = board[:-1]
    else:
        board = board[:int(user_input)] + board[int(user_input) + 1:]
    if minus_check == "y":
        carry_over = "+"
    elif minus_check == "n":
        carry_over = str(carry_atom)

def black_plus_process(user_input):
    global board
    if board[int(user_input)] == "+":
        if board[int(user_input) + 1] == "+":
            inter_atom = 4
        else:
            inter_atom = board[int(user_input) + 1] + 2
    else:
        if board[int(user_input)] + 1 == "+":
            inter_atom = board[int(user_input)] + 2
        else:
            inter_list = [board[int(user_input)], board[int(user_input) + 1]]
            inter_atom = (inter_list.sort())[1] + 2
    board = board[int(user_input) - 1:] + [inter_atom] * 2 + board[int(user_input) + 1:]
    plus_process(int(user_input) - 1)

def clone_process(user_input):
    global carry_over
    carry_over = str(board[int(user_input)])

def regular_process(atom,user_input):
    global board
    if user_input == "":
        board.append(random.randint(atom_range[0], atom_range[1]))
    else:
        board = board[:int(user_input) + 1] + [int(atom)] + board[int(user_input) + 1:]

def gen_specials():
    special = random.randint(1, 240)
    if special <= 48:
        return "+"
    elif special <= 60 and len(board) > 0:
        return "-"
    elif special <= 64 and len(board) > 0 and score >= 750:
        return "B"
    elif special <= 67 and len(board) > 0 and score >= 1500:
        return "C"
    else:
        small_atoms = []
        for atom in board:
            if atom not in specials and atom < atom_range[0]:
                small_atoms.append(atom)
        small_atom_check = random.randint(1, len(board))
        if small_atom_check <= len(small_atoms):
            return str(small_atoms[small_atom_check - 1])
        else:
            return str(random.randint(atom_range[0], atom_range[1]))

def specials_call(atom, user_input):
    specials_dict = {
        "+": plus_process,
        "-": minus_process,
        "B": black_plus_process,
        "C": clone_process
    }
    if atom in specials_dict.keys():
        if atom == "-":
            minus_process(user_input[0], user_input[1])
        else:
            specials_dict[atom](user_input[0])
    else:
        regular_process(atom,user_input[0])

def init():
    global board, score, move_number, carry_over, previous_moves
    board = []
    score = 0

    for _ in range(6):
        board.append(random.randint(1, 3))

    while len(board) <= 18:
        move_number += 1
        if move_number % 40 == 0:
            atom_range[0] += 1
            atom_range[1] += 1
        if carry_over != " ":
            special_atom = carry_over
            carry_over = " "
        elif len(previous_moves) >= 5:
            special_atom = "+"
        else:
            special_atom = gen_specials()
        previous_moves.append(special_atom)
        bot_command = "python yourBot.py"
        bot = subprocess.Popen(bot_command.split(),
                               stdout = subprocess.PIPE,
                               stdin = subprocess.PIPE)
        to_send="/".join([
            # str(score),
            # str(move_number),
            str(special_atom),
            " ".join([str(x) for x in board])
        ])
        bot.stdin.write(to_send)
        with open(logs, 'a') as f:f.write(to_send+'\n')
        bot.stdin.close()
        all_user_input = bot.stdout.readline().strip("\n").split(" ")
        specials_call(special_atom, all_user_input)

    print("Game over! Your score is " + str(score))

if __name__ == "__main__":
    for a in range(20):
        with open(logs, 'a') as f:f.write('round '+str(a)+'-'*50+'\n')
        init()

```

## How the bot thing works:

### Input

* Your bot will get 2 inputs: the atom that is currently in play, and the state of the board.
* The atom will be like so:
    + `+` for a `+` atom
    + `-` for a `-` atom
    + `B` for a Black `+` atom
    + `C` for a Clone atom
    + `{atom}` for a normal atom
* The state of the board will be like so:
    + `atom 0 atom 1 atom 2... atom n`, with the atoms separated by spaces (`atom n` wraps back to `atom 1`, to simulate a "ring" gameboard)
* These two will be separated by a `/`.

Example inputs:

```
1/1 2 2 3   (the atom in play is 1, and the board is [1 2 2 3])
+/1         (the atom in play is +, and the board is [1] on its own)

```

### Output

* You will output a string, depending on what the atom in play is.

+ If the atom is meant to be played between two atoms:

    - Output the gap you want to play the atom in. The gaps are like in between each atom, like so:

        ```
        atom 0, GAP 0, atom 1, GAP 1, atom 2, GAP 2... atom n, GAP N

        ```

        (`gap n` indicates you want to place the atom between `atom 1` and atom `n`) So output `2` if you want to play the atom on `gap 2`.
    + If the atom is meant to be played on an atom:
        - Output the atom you want to play it on, so `2` if you want to play the atom on `atom 2`.
    + If the atom is a `-`:
        - Output the atom you want to play it on, followed by a space, followed by a `y/n` choice of turning the atom into a `+` later, so `2, "y"` if you want to play the atom on `atom 2`, and you want to turn it into a `+`. **Note: this requires 2 inputs, instead of 1.**

Example outputs:

```
(Atom in play is a +)
2   (you want to play the + in gap 2 - between atom 2 and 3)
(Atom in play is a -)
3 y  (you want to play the - on atom 3, and you want to change it to a +)
2 n  (you want to play the - on atom 2, and you don't want to change it)

```
* To make the bot work, you have to go to the `Popen` bit (at around the end of the code), and replace it with whatever makes your program run as a Pythonic list (so if your program is `derp.java`, replace `["python", "bot.py"]` with `["java", "derp.java"]`).

## Answer-specific Specs:

* Place the entire code of your bot into the answer. If it doesn't fit, it doesn't count.
* Each user is allowed to have more than 1 bot, however, they should all be in separate answer posts.
* Also, give your bot a name.

## Scoring:

* The bot with the highest score wins.
    + Your bot will be tested for 20 games, and the final score is the average of the 20 games.
* The tie-breaker will be the time of the upload of the answer.
* So your answer will be formatted like this:

```
{language}, {bot name}
Score: {score}

```

Good luck!

# Answer
> 1 votes
## Python, draftBot, Score = 889

```
import random
def h(b):
    s=0
    for x in b:
        try:
            s+=int(x)
        except:
            s+=0
    return s
def d(i):g=i.split("/");a=g[0];b=g[1].split(" ");return(a,b)
def p(a,_,j):
    v=[]
    for x in _:
        try:
            v.append(int(x))
        except:
            v.append(0)
    try:
        v=v[:j+1]+[int(a)]+v[j+1:]
    except:
        v=v[:j+1]+[a]+v[j+1:]
    r1=[[]];b=[x for x in v];m=range(len(b)+1)
    for k in m:
        for i in m:
            for j in range(i):
                c = b[j:i + 1]
                if len(c)%2==0 and c==c[::-1] and 0 not in c:r1.append(c)
        b.insert(0, b.pop())
    q1=max(r1,key=len)
    r2=[[]];b=[x for x in v];m=range(len(b)+1)
    for k in m:
        for i in m:
            for j in range(i):
                c = b[j:i + 1]
                if len(c)>2 and len(c)%2==1 and c==c[::-1] and "+" in c and 0 not in c:r2.append(c)
        b.insert(0, b.pop())
    q2=max(r2,key=h)
    with open('f.log', 'a') as f:f.write('pal '+str(_)+' : '+str(q1)+' : '+str(q2)+'\n')
    if q2!=[]:return 100+h(q2)
    else:return len(q1)
i=raw_input()
(a,b)=d(i)
if a in ['C','B']:print('0')
elif a=='-':print("0 y" if random.randint(0, 1) == 1 else "0 n")
else:q,j=max((p(a,b,j),j)for j in range(len(b)));print(str(j))

```

I found that the controller:

* crashes when score exceeds 1500;
* does not properly merge atoms in same cases.

# Answer
> 0 votes
## Python, RandomBot, Score = 7.95

Nothing too fancy, just a random bot.

```
import random

game_input = raw_input().split("/")
current_atom = game_input[0]
board = game_input[1].split(" ")

if current_atom != "-":
    print(random.randint(0, len(board) - 1))
else:
    random_choice = " y" if random.randint(0, 1) == 1 else " n"
    print(str(random.randint(0, len(board) - 1)) + random_choice)

```

# Answer
> 0 votes
## Python, BadPlayer, Score = 21.45

```
import random

try:
    raw_input
except:
    raw_input = input

game_input = raw_input().split("/")
current_atom = game_input[0]
board = game_input[1].split(" ")

def get_chain(board, base):
    chain = []
    board = board[:]
    try:
        while board[base] == board[base + 1]:
            chain = [board[base]] + chain + [board[base + 1]]
            del board[base]
            del board[base]
            base -= 1
    except IndexError:
        pass
    return chain

def biggest_chain(board):
    chains = []
    base = 0
    i = 0
    while i < len(board) - 1:
        chains.append([i, get_chain(board, i)])
        i += 1
    return sorted(chains, key=lambda x: len(x[1]) / 2)[-1]

def not_in_chain():
    a, b = biggest_chain(board)
    if len(b) == 0:
        print(random.randint(0, len(board) - 1))
    elif random.randint(0, 1) == 0:
        print(random.randint(a + len(b)/2, len(board) - 1))
    else:
        try:
            print(random.randint(0, a - len(b)/2 - 1))
        except:
            print(random.randint(a + len(b)/2, len(board) - 1))

if current_atom in "+B":
    a, b = biggest_chain(board)
    if len(b) == 0:
        print(0)
    else:
        print(a)
elif current_atom == "C":
    not_in_chain()
elif current_atom == "-":
    a, b = biggest_chain(board)
    if len(b) == 0:
        print(str(random.randint(0, len(board) - 1)) + " n")
    elif random.randint(0, 1) == 0:
        print(str(random.randint(a + len(b)/2, len(board) - 1)) + " n")
    else:
        try:
            print(str(random.randint(0, a - len(b)/2 - 1)) + " n")
        except:
            print(str(random.randint(0, len(board) - 1)) + " n")
else:
    not_in_chain()

```

Just a very bad bot that often make the controller crash

---
Tags: code-challenge, game
---


title: Am I a Sophie Germain prime?

text:
# Question
Title: Am I a Sophie Germain prime?
A Sophie Germain Prime is a prime number **P** such that **2P+1** is prime as well. Given a *prime number* as input, your task is to determine whether it is a Sophie Germain Prime.

Standard Input/Output rules and Default Loopholes apply. This is a , so standard rules for this tag apply (returning two distinct and *consistent* values for each case, e.g: `True`/`False`).

---

# Test Cases

### Truthy (Sophie Germain primes)

These are the first few of them (OEIS A005384):

```
2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113

```

### Falsy

```
7, 13, 17, 31, 37, 43, 47

```

---

Please note that answers with explanations are encouraged!

It's , hence the shortest code in bytes in every language wins!

# Answer
> 7 votes
# x86-64 Machine Code, 24 bytes

```
01 FF FF C7 6A 01 59 89 F8 FF C1 99 F7 F9 85 D2 75 F5 39 F9 0F 94 C0 C3

```

The above code defines a function that takes a single parameter (the input value, known to be a prime) in `EDI` (following the System V AMD64 calling convention used on Gnu/Unix), and returns a Boolean result in `AL` (`1` if the input is a Sophie Germain prime, `0` otherwise).

The implementation is very similar to the solution to this challenge, since all we really have to do is determine whether a number is prime using as little code as possible, which means an inefficient iterative loop.

Basically, we take the input and immediately transform it into `2 × input + 1`. Then, starting with a counter set to 2, we loop through and check to see if the counter is a factor. The counter is incremented each time through the loop. As soon as a factor is found, the loop ends and that factor is compared against `2 × input + 1`. If the factor is equal to the test value, then that means we didn't find any smaller factors, and therefore the number must be prime. And since we have thus confirmed that `2 × input + 1` is prime, this means that `input` must be a Sophie Germain prime.

**Ungolfed assembly language mnemonics:**

```
IsSophieGermainPrime:
   add   edi, edi            ; input *= 2
   inc   edi                 ; input += 1
   push  1
   pop   rcx                 ; counter = 1

.CheckDivisibility:
   inc   ecx                 ; increment counter
   mov   eax, edi            ; EAX = input (needs to be in EAX for IDIV; will be clobbered)
   cdq                       ; sign-extend EAX into EDX:EAX
   idiv  ecx                 ; EDX:EAX / counter
   test  edx, edx            ; check the remainder to see if divided evenly
   jnz   .CheckDivisibility  ; keep looping if not divisible by this one

   cmp   ecx, edi            ; compare counter to input
   sete  al                  ; set true if first found factor is itself;
   ret                       ;          otherwise, set false

```

# Answer
> 6 votes
# Python,  ~~46 43 41~~  40 bytes

-1 byte using code suggested elsewhere by Erik the Outgolfer (`2*n+1` may be calculated as `n-~n` \- that is, `2*n+1=n-(-1-n)`)

```
f=lambda n,p=3:p>n or(n-~n)%p*f(n,p+2)>0

```

A recursive function.

Returns `True` if the prime number input, `n`, is a Sophie Germain prime and `False` if not.

**Try it online!**

Works by multiplying the remainders of the division of the candidate number `n-~n` (which is equal to `2*n+1`) after dividing by `p`, while `p` is less than `n`, starting at `p=3` and incrementing by `2` at each iteration. This is sufficient since `n` is greater that the square root of `2*n+1` (`n-~n`) for `n` greater than `2`. Also, since `2` is a Sophie Germain prime we can start testing with `p=3` and add `2` at each iteration rather than `1`. If the original `n` was greater than `2` the product of the resulting remainders is returned, so if the candidate has any factors the resulting `0` forces the result to be `0` too. The final `>0` forces all the positive products to return `True` and the `0`s to return `False` (to fulfil the "distinct and consistent" requirement).

Also beats:

...the 41 byte Python 3 (with sympy):

```
import sympy
lambda n:sympy.isprime(n-~n)

```

...and the 42 byte Python 2 full program **Try It**:

```
n=2*input()+1
p=3
while n%p:p+=2
print p<n

```

# Answer
> 6 votes
# Python 2, 39 bytes

```
f=lambda n,k=3:n%k^k/2>0<f(n,k+2)or k>n

```

Try it online!

### Alternate versions

```
f=lambda n,k=3:n%k^1>0<f(n-1,k+2)or k>n

```

```
f=lambda n,k=3:~-n%k>0<f(n-1,k+2)or k>n

```

```
f=lambda n,k=3:n%k!=1==f(n-1,k+2)or k>n

```

# Answer
> 4 votes
# MATL, 4 bytes

```
EQZp

```

Prints 1 for a Sophie Germain prime and 0 otherwise.

Try it at MATL Online

**Explanation**

```
        % Implicitly grab input as a number
E       % Multiply by 2
Q       % Add one
Zp      % Check if this is a prime number
        % Implicitly display the result

```

# Answer
> 4 votes
# Mathematica , 13 bytes

```
PrimeQ[2#+1]&

```

# Answer
> 4 votes
# Pyth, 4 bytes

*Almost an anagram for Pyth.*

```
P_hy

```

Try it online!

Other semi-anagrams: `Pt_y`, `P_tyh`.

**How?**

```
   y   # Double
  h    # Increment
 _     # Negate
P      # Prime?

```

P for positive argument factorizes; to test primality one should provide the negation of the number tested.

# Answer
> 4 votes
# CJam, 7 bytes

```
{2*)mp}

```

Try it online!

# Answer
> 3 votes
# 05AB1E, 3 bytes

```
x>p

```

Prints `1` if the *prime number* input is a Sophie Germain prime, and `0` if it is not (prints `1` if double the input plus one is prime).

**Try it online!**

### How?

```
x>p - implicit input: number n
x   - pop n then push n, 2*n
 >  - pop 2*n then push 2*n+1
  p - pop 2*n+1 then push is prime? (2*n+1) {True:1; False:0}
    - implicit print of top of stack

```

# Answer
> 3 votes
# Python 2, ~~47~~ ~~43~~ 42 bytes

*-4 bytes thanks to Leaky Nun. -1 byte thanks to Erik the Outgolfer.*

```
lambda n:all((n-~n)%i for i in range(2,n))

```

Try it online!

# Answer
> 3 votes
# Brachylog, 5 bytes

```
×₂+₁ṗ

```

Try it online!

# Answer
> 2 votes
# Jelly, 4 bytes

```
Ḥ‘ÆP

```

A monadic link returning `1` if the *prime number* input is a Sophie Germain prime, and `0` if it is not (yields `1` if double the input plus one is prime, `0` otherwise).

**Try it online!**

### How?

```
Ḥ‘ÆP - Link: number n
Ḥ    - double n
 ‘   - increment
  ÆP - is prime?

```

# Answer
> 2 votes
# Neim, 3 bytes

```
ᚫ>

```

Try it online!

-1 thanks to Okx.

# Answer
> 2 votes
# C, 43 bytes

```
i;f(x){for(x=x*2+1,i=1;x%++i;);return x>i;}

```

Returns `0` if `x` is a Sophie Germain prime, `1` otherwise.

Try it online!

# C (gcc), 38 bytes

```
i;f(x){for(x=x*2+1,i=1;x%++i;);x=x>i;}

```

Try it online!

# Answer
> 2 votes
# PHP, 39 bytes

prints 1 for true and nothing for false

```
for($d=$n=$argn*2+1;$n%--$d;);echo$d<2;

```

Try it online!

# Answer
> 2 votes
# Julia 0.6, 20 bytes

```
x->∉(0,(x-~x)%3:x)

```

# Answer
> 1 votes
# Clojure, 60 bytes

```
#((fn[n](some(fn[a](=(mod n a)0))(range 2 n)))(+(* 2 %)1))

```

Try it online!

This is an anonymous function - to use the function, do this:

```
(#(...) {number}) ; This will output a value

```

Returns `False` if prime is a Sophie Germain prime, `True` otherwise.

# Answer
> 1 votes
# Japt, 5 bytes

```
*2Ä j

```

Test it online! Probably won't get shorter than this...

An alternative solution which might be shorter in other languages:

```
¤Ä n2 j

```

Test it online! `¤` converts the input to binary, `Ä` appends a 1, and `n2` converts back from base 2 (Japt doesn't have a built-in for converting from binary).

# Answer
> 1 votes
# Python 2, 55 bytes:

```
lambda n:len(filter(lambda p:(2*n+1)%p,range(2,n)))>n-3

```

# Python 2, 48 bytes, different logic:

```
lambda n:all(map(lambda p:(2*n+1)%p,range(2,n)))

```

# Answer
> 1 votes
# braingasm, ~~8~~ 5 bytes

```
;*+q:

```

Works like this:

```
;          Input a number
 *+        Double and increase it
   q:      Print 1 or 0 depending on wether the current number is prime

```

edit: don't need prime check on input

# Answer
> 1 votes
# Pari/GP, 17 bytes

```
p->isprime(2*p+1)

```

Try it online!

# Answer
> 1 votes
# Julia 0.4, ~~17~~ 16 bytes

*1 byte saved thanks to @Tanj*

```
x->isprime(x-~x)

```

`isprime` was deprecated in Julia 0.5.

# Answer
> 1 votes
# QBIC, 7 bytes

```
?µ:*2+1

```

## Explanation

```
?        PRINT
 µ       the result of the prime-test (-1 for true. 0 for false)
  :*2+1  with the input times 2 plus 1 as argument

```

# Answer
> 1 votes
# MATLAB / Octave, 18 bytes

```
@(x)isprime(2*x+1)

```

Anonymous function.

Try it online!

# Answer
> 1 votes
## Ruby 2.3.1, 44 bytes

```
lambda{|p|(2...2*p+1).all?{|r|(2*p+1)%r!=0}}

```

Try it online!

# Answer
> 1 votes
# C (gcc), 46 bytes

```
f(x,i){for(i=2;i<x;)(x-~x)%i++?:(x=i=0);x=!x;}

```

Try it online!

Returns `0` if SG prime, `1` otherwise.

# Answer
> 1 votes
# Excel VBA, 59 Bytes

Anonymous VBE immediate window function that takes input from cell `[A1]` to and outputs to the vbe immediate window

Must be run in a clean module *or* the value of `j` must be reset to `0` before use

```
n=[2*A1-1]:For i=2To n-1:j=IIf(n/i=Int(n/i),i,j):Next:?j<>0

```

# Answer
> 0 votes
# ,,,, 5 bytes

```
2×1+p

```

Unlike other golflangs, ,,, doesn't have builtins for incrementing and doubling because I thought I'd rather use those bytes for other things. :P

## Explanation

Take input 23 for example.

```
2×1+p

       implicit input                      [23]
2      push 2                              [23, 2]
 ×     pop 23 and 2 and push 23 * 2        [46]
  1    push 1                              [46, 1]
   +   pop 46 and 1 and push 46 + 1        [47]
    p  pop 47 and push whether it is prime [1]
       implicit output                     []

```

# Answer
> 0 votes
# cQuents, 9 bytes

```
#|2A+1?pz

```

Had to fix an interpreter bug to get this working, so no TIO link.

### Explanation

```
#|2A+1      The last item in the input, which will become n, equals the first item
            in the input times two, plus one.
      ?     Mode: query. Returns true if n is in the sequence, and false otherwise.
       pz   Sequence: each item is the next prime after the previous item.

```

---
Tags: code-golf, number, number-theory, decision-problem, primes
---


title: Peaceable coexisting armies

text:
# Question
Title: Peaceable coexisting armies
In the game of chess, there is piece called the queen that may attack any other piece that is on the same row, column or diagonal. In chess there are typically two sides, black and white, with each piece belonging to one of the teams. Pieces may not attack pieces belong to the same team.

Your goal is to find out the largest peaceable coexisting armies for a square board. That is the largest number of black and white queens that can fit on the board such that no two queens can attack each other and the number of black queens is equal to the number of white queens.

You will receive as input the side length of a square board, and should output the number of size of the largest peaceable coexisting armies that can fit on that board.

This is so standard rules for the tag apply.

OEIS A250000

These test cases encompass all known answers. Your solution should be a generalized answer that, given enough computing power and time, can compute the solution for any input value.

```
1: 0
2: 0
3: 1
4: 2
5: 4
6: 5
7: 7
8: 9
9: 12
10: 14
11: 17
12: 21
13: 24

```

# Answer
# C, 476 bytes, DFS iterating white queens, O(2n2)

```
#define R return
#define Z(q)for(j=q;j<I;j++)
#define Q(q)memset(q,0,4*J);
#define U(q)S(w[k]/I q j,w[k]%I+j)
int*c,*w,*Y,j,k,r,I,J,m;T(i,j){R i*I+j;}S(x,y){x>=0&&x<I&&y>=0&&y<I?Y[T(x,y)]=1:0;}g(l){int i;if(l==m){Q(Y)for(k=m;k--;){Z(0)Y[T(w[k]/I,j)]=Y[T(j,w[k]%I)]=1;Z(-I)U(+),U(-);}for(r=k=J;k--;)r-=Y[k];R r>=m;}for(i=!l?0:w[l-1]+1;i<J;i++){if(!c[i]){c[i]=1;w[l]=i;if(g(l+1))R 1;c[i]=0;}}R 0;}f(s){I=s;J=I*I;int C[J],W[J],y[J];c=C;w=W;Y=y;for(m=1;;m++){Q(c)if(!g(0))R m-1;}}

```

## 518 bytes, DFS with pruning, O(2n)

```
#define R return
#define Z(q)for(j=q;j<I;j++)
#define Q(q)memset(q,0,4*J);
#define V(Q)t=Q;if(!Y[t]){G-=Y[t]=1;b[B++]=t;}
#define F(q)if(S(x q j,y+j)){V((x q j)*I+y+j)}
int*c,*w,*Y,j,k,r,I,J,m;S(x,y){R x>=0&&x<I&&y>=0&&y<I;}D(l,H){int i,b[J],B,t,x,y,G;if(l==m)R 1;for(i=!l?0:w[l-1]+1;i<J;i++){if(!c[i]){c[i]=1;w[l]=i;x=i/I;y=i%I;G=H;Z(B=0){V(x*I+j)V(j*I+y)}Z(-I){F(+)F(-)}if(G>=m&&D(l+1,G))R 1;for(j=B;j--;)Y[b[j]]=0;c[i]=0;}}R 0;}f(s){I=s;J=I*I;int C[J],W[J],y[J];c=C;w=W;Y=y;for(m=1;;m++){Q(c)Q(Y)if(!D(0,J))R m-1;}}

```

## 577 bytes, DFS iterating white and black queens, O(?)

```
#define R return
#define U(V,r,q)S(V,r[i]/I q j,r[i]%I+j)
#define W(q)for(j=q;j<I;j++)
#define Z(r,q,t,v)for(i=0;i<r;i++){t[q[i]]=1;W(0)v[T(q[i]/I,j)]=v[T(j,q[i]%I)]=1;W(-I)U(v,q,+),U(v,q,-);};
#define P(K,L,M)memcpy(v,K,4*J);for(i=0;i<J;i++)if(!v[i]){L[M++]=i;if(g(E,N,!C))R 1;M--;};
int*w,*b,m,I,J;T(i,j){R i*I+j;}Q(int*q){memset(q,0,4*J);}S(V,x,y)int*V;{x>=0&&x<I&&y>=0&&y<I?V[T(x,y)]=1:0;}g(E,N,C){int i,j,v[J],X[J],Y[J];if(E==m&&N==m)R 1;Q(X);Q(Y);Z(E,w,X,Y)Z(N,b,Y,X)if(C){P(Y,b,N)}else{P(X,w,E)}R 0;}f(q){I=q,J=I*I;int W[J],B[J];w=W,b=B;for(m=1;;m++)if(!g(0,0,0))R m-1;}

```

Basically, the code iterates over possibilities of white queen and check whether black queen could be placed then.

Speed reference table (in seconds):

```
+---+----------------------+---------------------+-----------------+--------+
| n |      DFS w & b       |        DFS w        |  DFS w/ pruning | Clingo |
+---+----------------------+---------------------+-----------------+--------+
| 3 |                 0.00 |                0.00 |            0.00 |   0.01 |
| 4 |                 0.00 |                0.00 |            0.00 |   0.02 |
| 5 |                 0.47 |                0.16 |            0.00 |   0.04 |
| 6 |                20.62 |                1.14 |            0.00 |   0.60 |
| 7 |              1125.07 |              397.88 |            0.63 |  18.14 |
| 8 |                      |                     |            1.28 | 979.35 |
| 9 |                      |                     |           23.13 |        |
+---+----------------------+---------------------+-----------------+--------+

```
> 9 votes

# Answer
# Clingo, 90 bytes

```
{q(1..n,1..n)}.a(X+(-I;0;I),Y+(0;I)):-q(X,Y),I=-n..n.:~K={q(X,Y)},{a(1..n,1..n)}n*n-K.[-K]

```

### Demo

```
$ clingo peaceable.lp -cn=6
clingo version 5.1.0
Reading from peaceable.lp
Solving...
Answer: 1

Optimization: 0
Answer: 2
q(6,1) a(7,1) a(7,2) a(8,1) a(8,3) a(9,1) a(9,4) a(10,1) a(10,5) a(11,1) a(11,6) a(12,1) a(6,1) a(6,2) a(6,3) a(6,4) a(6,5) a(6,6) a(5,1) a(5,2) a(4,1) a(4,3) a(3,1) a(3,4) a(2,1) a(2,5) a(1,1) a(1,6) a(0,1) a(7,0) a(8,-1) a(9,-2) a(10,-3) a(11,-4) a(12,-5) a(6,-4) a(6,-3) a(6,-2) a(6,-1) a(6,0) a(5,0) a(4,-1) a(0,7) a(1,-4) a(2,-3) a(3,-2) a(6,-5) a(6,7) a(0,-5) a(12,7)
Optimization: -1
Answer: 3
q(1,6) q(6,1) a(7,1) a(7,2) a(7,6) a(8,1) a(8,3) a(9,1) a(9,4) a(10,1) a(10,5) a(11,1) a(11,6) a(12,1) a(6,1) a(6,2) a(6,3) a(6,4) a(6,5) a(6,6) a(5,1) a(5,2) a(5,6) a(4,1) a(4,3) a(4,6) a(3,1) a(3,4) a(3,6) a(2,1) a(2,5) a(2,6) a(1,1) a(1,2) a(1,3) a(1,4) a(1,5) a(1,6) a(0,1) a(0,5) a(0,6) a(-1,4) a(-1,6) a(-2,3) a(-2,6) a(-3,2) a(-3,6) a(-4,1) a(-4,6) a(-5,6) a(7,0) a(8,-1) a(9,-2) a(10,-3) a(11,-4) a(12,-5) a(6,-4) a(6,-3) a(6,-2) a(6,-1) a(6,0) a(5,0) a(4,-1) a(0,7) a(1,7) a(2,7) a(-1,8) a(1,8) a(3,8) a(-2,9) a(1,9) a(-3,10) a(1,10) a(-4,11) a(1,11) a(-5,12) a(1,-4) a(1,0) a(2,-3) a(3,-2) a(6,-5) a(6,7) a(4,9) a(5,10) a(6,11) a(1,12) a(-5,0) a(0,-5) a(7,12) a(12,7)
Optimization: -2
Answer: 4
q(1,6) q(6,1) q(6,6) a(7,1) a(7,2) a(7,5) a(7,6) a(8,1) a(8,3) a(8,4) a(8,6) a(9,1) a(9,3) a(9,4) a(9,6) a(10,1) a(10,2) a(10,5) a(10,6) a(11,1) a(11,6) a(12,1) a(12,6) a(6,1) a(6,2) a(6,3) a(6,4) a(6,5) a(6,6) a(5,1) a(5,2) a(5,5) a(5,6) a(4,1) a(4,3) a(4,4) a(4,6) a(3,1) a(3,3) a(3,4) a(3,6) a(2,1) a(2,2) a(2,5) a(2,6) a(1,1) a(1,2) a(1,3) a(1,4) a(1,5) a(1,6) a(0,1) a(0,5) a(0,6) a(-1,4) a(-1,6) a(-2,3) a(-2,6) a(-3,2) a(-3,6) a(-4,1) a(-4,6) a(-5,6) a(7,0) a(8,-1) a(9,-2) a(10,-3) a(11,-4) a(12,-5) a(12,0) a(6,-4) a(6,-3) a(6,-2) a(6,-1) a(6,0) a(5,0) a(4,-1) a(0,7) a(1,7) a(2,7) a(5,7) a(-1,8) a(1,8) a(3,8) a(4,8) a(-2,9) a(1,9) a(3,9) a(-3,10) a(1,10) a(2,10) a(-4,11) a(1,11) a(-5,12) a(0,12) a(1,-4) a(1,0) a(2,-3) a(3,-2) a(6,-5) a(6,7) a(6,8) a(4,9) a(6,9) a(5,10) a(6,10) a(6,11) a(1,12) a(6,12) a(-5,0) a(0,-5) a(0,0) a(7,7) a(8,8) a(9,9) a(10,10) a(11,11) a(7,12) a(12,7) a(12,12)
Optimization: -3
Answer: 5
q(1,1) q(1,6) q(6,1) q(6,6) a(7,1) a(7,2) a(7,5) a(7,6) a(8,1) a(8,3) a(8,4) a(8,6) a(9,1) a(9,3) a(9,4) a(9,6) a(10,1) a(10,2) a(10,5) a(10,6) a(11,1) a(11,6) a(12,1) a(12,6) a(6,1) a(6,2) a(6,3) a(6,4) a(6,5) a(6,6) a(5,1) a(5,2) a(5,5) a(5,6) a(4,1) a(4,3) a(4,4) a(4,6) a(3,1) a(3,3) a(3,4) a(3,6) a(2,1) a(2,2) a(2,5) a(2,6) a(1,1) a(1,2) a(1,3) a(1,4) a(1,5) a(1,6) a(0,1) a(0,2) a(0,5) a(0,6) a(-1,1) a(-1,3) a(-1,4) a(-1,6) a(-2,1) a(-2,3) a(-2,4) a(-2,6) a(-3,1) a(-3,2) a(-3,5) a(-3,6) a(-4,1) a(-4,6) a(-5,1) a(-5,6) a(7,-5) a(7,0) a(8,-1) a(9,-2) a(10,-3) a(11,-4) a(12,-5) a(12,0) a(6,-4) a(6,-3) a(6,-2) a(6,-1) a(6,0) a(5,-3) a(5,0) a(4,-2) a(4,-1) a(3,-1) a(2,0) a(0,7) a(1,7) a(2,7) a(5,7) a(-1,8) a(1,8) a(3,8) a(4,8) a(-2,9) a(1,9) a(3,9) a(-3,10) a(1,10) a(2,10) a(-4,11) a(1,11) a(-5,7) a(-5,12) a(0,12) a(1,-5) a(1,-4) a(1,-3) a(1,-2) a(1,-1) a(1,0) a(2,-3) a(3,-2) a(6,-5) a(6,7) a(6,8) a(4,9) a(6,9) a(5,10) a(6,10) a(6,11) a(1,12) a(6,12) a(-5,-5) a(-5,0) a(-4,-4) a(-3,-3) a(-2,-2) a(-1,-1) a(0,-5) a(0,0) a(7,7) a(8,8) a(9,9) a(10,10) a(11,11) a(7,12) a(12,7) a(12,12)
Optimization: -4
Answer: 6
q(1,2) q(1,3) q(2,2) q(2,3) q(2,6) a(7,1) a(7,2) a(7,3) a(7,6) a(8,2) a(8,3) a(8,6) a(6,2) a(6,3) a(6,6) a(5,2) a(5,3) a(5,5) a(5,6) a(4,1) a(4,2) a(4,3) a(4,4) a(4,5) a(4,6) a(3,1) a(3,2) a(3,3) a(3,4) a(3,5) a(3,6) a(2,1) a(2,2) a(2,3) a(2,4) a(2,5) a(2,6) a(1,1) a(1,2) a(1,3) a(1,4) a(1,5) a(1,6) a(0,1) a(0,2) a(0,3) a(0,4) a(0,5) a(0,6) a(-1,1) a(-1,2) a(-1,3) a(-1,4) a(-1,5) a(-1,6) a(-2,2) a(-2,3) a(-2,5) a(-2,6) a(-3,1) a(-3,2) a(-3,3) a(-3,6) a(-4,2) a(-4,3) a(-4,6) a(-5,2) a(-5,3) a(7,-4) a(7,-3) a(7,-2) a(8,-4) a(8,-3) a(8,0) a(6,-3) a(6,-2) a(6,-1) a(5,-2) a(5,-1) a(5,0) a(4,-1) a(4,0) a(3,0) a(2,0) a(1,7) a(2,7) a(3,7) a(5,7) a(0,8) a(1,8) a(2,8) a(4,8) a(-2,7) a(-1,9) a(1,9) a(2,9) a(-3,7) a(-3,8) a(-2,10) a(2,10) a(-4,7) a(-4,8) a(-4,9) a(-3,11) a(-5,8) a(-5,9) a(-4,12) a(1,-4) a(1,-3) a(1,-2) a(1,-1) a(1,0) a(2,-4) a(2,-3) a(2,-2) a(2,-1) a(6,7) a(6,8) a(5,9) a(6,10) a(2,11) a(2,12) a(-5,-4) a(-5,-3) a(-4,-4) a(-4,-3) a(-4,-2) a(-4,0) a(-3,-3) a(-3,-2) a(-3,-1) a(-2,-2) a(-2,-1) a(-2,0) a(-1,-1) a(-1,0) a(0,0) a(7,7) a(7,8) a(8,8) a(7,9) a(8,9) a(7,11) a(8,12)
Optimization: -5
OPTIMUM FOUND

Models       : 6
  Optimum    : yes
Optimization : -5
Calls        : 1
Time         : 0.733s (Solving: 0.71s 1st Model: 0.00s Unsat: 0.71s)
CPU Time     : 0.730s

```
> 3 votes

# Answer
# Python 2 | 325 284 217 bytes

Try it online!

```
from itertools import*
N=input()
r=range(N*N)
for n in r:
 g=r
 for s in combinations(g,n):
    for p in s:g=filter(lambda q:all([abs(q%N-p%N)!=abs(q/N-p/N),q%N!=p%N,q/N!=p/N]),g)
    if len(g)>=n:break
    g=r
 else:exit(n-1)

```

**Edit:** Replaced tuples with integers in g and other trivial edits.

**Edit2:** Bytes down to 217 thanks to musicman523 and CalculatorFeline!

## How it works

The program iterates over all possible positions of `n` queens and filters out non-peaceful points in `g` caused due to position of the queens. If the remaining points is greater than `n` then it means that it is possible to for `n` queen armies to stay peacefully. If for the next value of `n`, no peaceful situation is found, then the program exits with exit code : `n-1`, which is the answer. **In short, it is brute force**

The program can be made faster by changing the last two lines to

```
for n in range(N**2):
    if not z(n,N):print n-1;break

```
> 3 votes

# Answer
## Haskell, ~~169 156 153~~ 152 bytes

```
k!(a:b)=k!b++[a:c|c<-(k-1)!b]
k!x=[x|k==0]
q&l|p<-q![[x,y,x-y,x+y]|x<-l,y<-l]=or[all and$zipWith(/=)<$>b<*>w|b<-p,w<-p]
g n=last$filter(&[1..n])[0..n*n]

```

Defines a function `g`, may be further golfable. Try it online! On TIO, when compiled with `-O2`, this takes about 36 seconds for **n = 4** and times out on **n = 5**. The time complexity should be **O(n24n2)**.

## Explanation

We iterate over the possible values for the number of queens (**q**). For each **q**, we generate all pairs of size-**q** subsets of **\[1..n\]2**, one set of black queens (**b**) and one of white queens (**w**). Then, each element of **b** is checked against each element of **w** to see if they share a row, column, diagonal or anti-diagonal. This also takes care of two pieces sharing the same coordinate. The greatest value of **q** that admits a peaceable configuration is the final value.

The first two lines of the program define the function `!`, which computes the length-`k` subsequences of a list `x`. The implementation is by a basic recursion: either choose the first element to be in the set or not and recurse to the tail, decrementing `k` if necessary. Then the empty list or reached, check that `k==0`.

```
k!(a:b)=       -- ! on integer k and list with head a and tail b is
 k!b++         -- the concatenation of k!b and
 [a:c|         -- the list of lists a:c where
  c<-(k-1)!b]  -- c is drawn from (k-1)!b.
k!x=           -- If x doesn't have the form a:b (which means that it's empty),
 [x|           -- the result is a list containing x
  k==0]        -- but only if k==0.

```

The second auxiliary function `&` takes a number `q` (number of queens on either side) and a list `l` (the x-coordinates of the board, also used as the y-coordinates), and returns a Boolean value indicating if a peaceable configuration exists. We first compute `p`, the list of length-`q` subsequences of the list of values `[x,y,x-y,x+y]`, where `x` and `y` range over `l`. They represent the row, column, diagonal and anti-diagonal of a square `(x,y)` on the board.

```
q&l               -- & on inputs q and l:
 |p<-             -- define p as
  q!              -- the q-subsequences of
  [[x,y,x-y,x+y]  -- the list of these 4-lists
   |x<-l,y<-l]    -- where x and y are drawn independently from l.

```

Next we have the result of `q&l`. We draw two subsequences `b` and `w` from `p`, pair the 4-lists of them together in all possible ways, and check that they always differ in all 4 coordinates. If some choices of `b` and `w` result in a truthy result, we return `True`.

```
=or            -- Does the following list contain a True:
 [all and$     -- every list contains only truthy values
  zipWith(/=)  -- if we zip with inequality
  <$>b<*>w     -- all elements of b and w in all possible ways,
 |b<-p,w<-p]   -- where b and w are drawn independently from p.

```

The last line is the main function. Given `n`, it simply finds the largest possible value of `q` for which `q&[1..n]` is true.

```
g n=              -- g on input n is
 last$            -- the last of
 filter(&[1..n])  -- those values q for which q&[1..n] is true
 [0..n*n]         -- in this list.

```
> 2 votes

---
Tags: code-golf, chess
---