title: How many fingers does bad pianist need?

text:
# Question
Title: How many fingers does bad pianist need?
# Challenge

## Premise

Bob is a novice pianist who can only play sequences of single notes. In addition, he does quite an interesting thing: for every note after the first, if it's higher than the previous note was, he uses the finger directly to the right of the previous finger used; if lower, to the left; if the same pitch, well, the same finger.

Let's take Auld Lang Syne as an example, and arbitrarily suppose, only for the sake of this example, that Bob uses the very right side of his right hand.

```
Pitch: Should < auld = ac- = quain- < tance > be > for- < got
Digit: mid      ring   ring  ring     pinky   ring mid    ring

```

Alice wants to convince him of the stupidity of his playing...

## Task

Input: a sequence of \\$n\\$ MIDI note numbers (which are integers between 0 and 127 inclusive), where \\$2\leq n\leq10000\\$.

Output: the number of fingers required to finish the melody with the playing style outlined in 'Premise'.

Please note that the answer may be more than 5.

No consideration of the starting finger is needed. Assume that the choice is optimal for playable melodies and has nothing (else) to do with the number of fingers required.

### Example 1

Input: `0 0 0 0`

Output: `1`

### Example 2

Input: `43 48 48 48 52 50 48 50`

Output: `3`

### Example 3

Input: `86 88 84 81 83 79 74 76 72 69 71 67 62 64 60 57 59 57 56 55`

Output: `9`

### Example 4

Input: `82 79 78 76 78 76 74 73 70 67 66 64 66 64 62 61`

Output: `12`

# Remarks

# Answer
# Perl 6, 27 bytes

```
{+minmax [\+] @_ Z<=>0,|@_}

```

Try it online!

### Explanation

`@_ Z<=>0,|@_` uses the zip metaoperator (`Z`) with the compare operator (`<=>`) to zip the list with itself offset by 1 and return the result of the comparison., e.g. `[43, 48, 48, 48, 52, 50, 48, 50]` -\> `(More More Same Same More Less Less More)`

`[\+]` Reduces the list by summing over it (More = 1, Same = 0, Less = -1), however the `\` does a 'triangular reduction' which produces a list of each calculation instead of the end result, e.g. `(More More Same Same More Less Less More)` -\> `(More 2 2 2 3 2 1 2)`

`minmax` returns the range of smallest..largest, effectively removing duplicates. `(More 2 2 2 3 2 1 2)` -\> `Order::More..3`

`+` just returns the length of this range (list), which is the result
> 13 votes

# Answer
# 05AB1E, 8 bytes

```
¥.±ŒOÄZ>

```

Try it online!

---

## Explanation

```
¥              - Get the differences
 .±            - Get the signs of these (so if they go up or down)
   ŒO          - Sum the sublists of these
     ÄZ        - And find the biggest absolute change
       >       - Add one (since we need a finger to play the first note)

```
> 9 votes

# Answer
# Python 3.8, ~~64 63~~ 57 bytes

*-6 bytes thanks to @xnor's abuse of walrus!*

```
lambda l,t=0,a=0:len({(t:=t+(a<b)-(a>(a:=b)))for b in l})

```

Try it online!

A function that takes input `l` as a list of integers, and returns the number of fingers needed.

**How**:

`t` keeps track of the current finger (represented by an integer). For each 2 consecutive notes `a, b`, the finger is increased by `-1`, `0`, or `1` depending on whether `a>b`, `a==b` or `a<b`:

```
t:=t+(a<b)-(a>b)

```

All values of `t` are then gathered into a set, whose size is the number of unique fingers.
> 9 votes

# Answer
# , ~~45~~ 42 bytes

```
`?`=diff;1+?range(0,cumsum(sign(?scan())))

```

Try it online!

Thanks to JDL for -3 bytes.
> 6 votes

# Answer
# FRACTRAN 29 fractions (244 bytes)

```
7*61/2^129*59 3*61/2*59 47/59 59/61 2*53/7*47 31/47 47/53 7*37/2^129*31
17/31 31/37 67/2^128*17 5*19/2*3*17 5*11*23/2*13*17 5*11*23/2*17 13*23/3*11*17
13*23/3*17 41/17 17/19 29/3*23 41/23 23/29 3*43/5*41 3*43/2*41 47/41
41/43 2/67 1/3 2/13 2/11

```

Input: \\$59\cdot 2^n\\$, where \\$n\\$ is the MIDI list (terminated in the sentinel 128) in base-129. That is, if the list is \\$\\{n\_0, n\_1, n\_2, \dots, n\_m\\}\\$, then \\$n=n\_0 + 129n\_1 + 129^2n\_2 + \cdots + 129^{m}n\_m + 129^{m+1}\cdot 128\\$.

Output: \\$2^k\\$, where \\$k\\$ is the number of necessary fingers.

---

To try this online, the interpreter at https://pimlu.github.io/fractran/ is able to evaluate the program relatively quickly, and it takes the program in the following syntax:

```
7*61%2^129*59
3*61%2*59
47%59
59%61
2*53%7*47
31%47
47%53
7*37%2^129*31
17%31
31%37
67%2^128*17
5*19%2*3*17
5*11*23%2*13*17
5*11*23%2*17
13*23%3*11*17
13*23%3*17
41%17
17%19
29%3*23
41%23
23%29
3*43%5*41
3*43%2*41
47%41
41%43
2%67
1%3
2%13
2%11

```

For the four examples, the program accepts this syntax for the input:

```
[59, 1], [2, 35446128768]
[59, 1], [2, 9845790461648320003]
[59, 1], [2, 209150948383325817811492382511176427430698872]
[59, 1], [2, 755543512556056338685630134436248304]

```

These are prime factorizations, saving having to multiply out the gigantic exponentials.

## How does it work?

In FRACTRAN, there is a state, which is initially set to the input value. The state is multiplied by each fraction one at a time, and if any results in a whole number, that number replaces the state and the program returns to the beginning of the list. If no fractions apply in this way, then the state is output and the program halts.

This is a terse way of describing a register machine. By prime factorizing everything, a fraction like 75/7 = 3\*5^2/7 means "if register seven is at least 1, then decrement it and add 1 to register three and 2 to register five."

Each prime in the program can be given a descriptive name, like 3 is 'a' and 59 is 'line1'. The rest don't particularly matter, since I'll give a disassembled version of the program, and you could figure out the rest of the assignments if you really wanted. Each line is like a chemical reaction; for example, the first line means "if line1 \>= 1 and a \>= 129, then decrement line1 by 1, decrement a by 129, increment line1r by 1, and increment adiv1 by 1."

```
0. line1 + 129 a -> line1r + adiv
1. line1 + a -> line1r + b
2. line1 -> line3
3. line1r -> line1
4. line3 + adiv -> line3r + a
5. line3 -> line4
6. line3r -> line3
7. line4 + 129 a -> line4r + adiv
8. line4 -> line5
9. line4r -> line4
10. line5 + 128 a -> line8
11. line5 + a + b -> line5r + c
12. line5 + a + MAX -> line6 + c + MIN
13. line5 + a -> line6 + c + MIN
14. line5 + b + MIN -> line6 + MAX
15. line5 + b -> line6 + MAX
16. line5 -> line7
17. line5r -> line5
18. line6 + b -> line6r
19. line6 -> line7
20. line6r -> line6
21. line7 + c -> line7r + b
22. line7 + a -> line7r + b
23. line7 -> line3
24. line7r -> line7
25. line8 -> a
26. b -> 0
27. MAX -> a
28. MIN -> a

```

So, here's an analysis. At the beginning, the input is `line1 + n a`. This means, the first relevant part of the program is

```
0. line1 + 129 a -> line1r + adiv
1. line1 + a -> line1r + b
2. line1 -> line3
3. line1r -> line1

```

which reduces the a register mod 129, putting the quotient in adiv and the remainder into b, which serves as a register to hold the previous MIDI note, which in this case is the very first one. Once this is done, it continues onto

```
4. line3 + adiv -> line3r + a
5. line3 -> line4
6. line3r -> line3

```

which moves adiv back into the a register, and for the main loop the a register starts with the remaining part of the MIDI list. Then,

```
7. line4 + 129 a -> line4r + adiv
8. line4 -> line5
9. line4r -> line4

```

The MIDI list is reduced mod 129, putting the rest of the list into adiv, leaving the MIDI note in the a register. This continues on to the the core calculation loop.

```
10. line5 + 128 a -> line8
11. line5 + a + b -> line5r + c
12. line5 + a + MAX -> line6 + c + MIN
13. line5 + a -> line6 + c + MIN
14. line5 + b + MIN -> line6 + MAX
15. line5 + b -> line6 + MAX
16. line5 -> line7
17. line5r -> line5

```

Reaction 10 detects if the sentinel 128 has occured, in which case it goes to line8 (the cleanup routine). Otherwise, we begin the comparison of a with b, to see which is larger. There are two registers MAX and MIN, representing the maximum and minimum relative finger numbers relative to note b so far. If a is greater than b, then we need to decrement MAX and increment MIN; if MAX is zero, then we don't decrement it, since this has the effect of widening the necessary number of fingers. Similarly, if b is greater than a, we need to decrement MIN (if nonzero) and increment MAX.

The comparison works by decrementing both a and b until one of them is zero. We will need the a register later on, to store it back into b, so whenever we decrement a, we increment a temporary variable c. Reaction 11 decrements a and b if they are both nonzero. Past this point, we know either b=0 or a=0. Reactions 12 and 13 are for the b=0 case, implementing the decrement-MAX-if-nonzero operation, and reactions 14 and 15 are for a=0. Reaction 16 is when a and be were equal.

If a and b were unequal in some way, then b is zeroed out with the following block

```
18. line6 + b -> line6r
19. line6 -> line7
20. line6r -> line6

```

And, along with the a=b case, this continues on to

```
21. line7 + c -> line7r + b
22. line7 + a -> line7r + b
23. line7 -> line3
24. line7r -> line7

```

which stores a+c into b, clearing a and c in the process. This has the effect of copying the original value of a at the start of the main loop into b. From here, we return to line3 to set up the main loop.

At the very end, once the sentinel is detected, the following block is run.

```
25. line8 -> a
26. b -> 0
27. MAX -> a
28. MIN -> a

```

Since the sentinel detection subtracts 128 from a, we know a is zero when entering this block. Then, the value of 1 + MAX + MIN is stored into a, and the value of b is cleared out. Once done, no other reactions apply, and the program terminates with the number of necessary fingers in the a register.
> 6 votes

# Answer
# JavaScript (ES6),  ~~55 53~~  52 bytes

```
a=>a.map(o=v=>o[i+=-(a>v)|a<(a=v)]=n+=!o[i],i=n=0)|n

```

Try it online!

### Commented

```
a =>                // a[] = input array of notes, re-used to store
  a.map(            //       the previous finger index
    o =             // o = object used to store the fingers
    v =>            // for each note v in a[]:
    o[              //   update o[i]:
      i +=          //     update i:
        -(a > v) |  //       decrement i if the previous value is greater than v
        a < (a = v) //       increment i if it's lower than v; and update a to v
    ] =             //       (if a = v or a is non-numeric, i is left unchanged)
      n += !o[i],   //     mark this finger as used and increment n if it was
                    //     not already used
    i = n = 0       //   start with i = n = 0
  ) | n             // end of map(); return n

```
> 2 votes

# Answer
# Perl 5 `-MList::Util=uniq -pa`, 35 bytes

```
$_=uniq map{$c+=$_<=>$p;$p=$_;$c}@F

```

Try it online!
> 2 votes

# Answer
# Io, ~~107~~ 105 bytes

-2 bytes after using "push" instead of "append".

```
method(x,(r :=x slice(0,-1)map(i,v,(v-x at(i+1))compare(0)))map(i,v,r slice(0,i+1)sum)push(0)unique size)

```

Try it online!
> 2 votes

# Answer
# Wolfram Language (Mathematica), ~~53~~ 46 bytes

```
Tr[1^{0}~Union~Accumulate@Sign@Differences@#]&

```

Try it online!

Thanks to @J42161217 for pointing out that `Tr[1^list]` is a 1-character-shorter alternative to `Length@list`.
> 2 votes

# Answer
# Retina, 76 bytes

```
\d+
*_:$&*
+`_=_
=
=_
<
_=
>
[_:=]

Lw$`(.)(?>(\1)|(?<-2>.))*
_$#2*
O^`
1G`

```

Try it online! Link includes test suite. Takes input as a `=`-separated list of integers (I could have used space or `,` but `=` was prettier) but the test suite adapts the space-separated test cases to work with the code. Explanation:

```
\d+
*_:$&*

```

Convert each integer to unary in duplicate.

```
+`_=_
=

```

Subtract pairs of adjacent integers.

```
=_
<
_=
>

```

Note whether adjacent integers were ascending or descending.

```
[_:=]

```

Delete everything else.

```
Lw$`(.)(?>(\1)|(?<-2>.))*
_$#2*

```

Find runs of notes. Runs can be interrupted by a reverse run as long as the run does not return to its starting finger; this is achieved via the .NET regexp balancing group construct `(?<-2>.)`. The run always starts with an ascending or descending pair which requires two fingers; since one finger is added at the end to handle the degenerate case where only one note is played, only one finger is added here, resulting in the number of additional fingers required for this run. The `w` modifier allows all valid runs to be collected.

```
O^`

```

Sort the longest number of fingers to the start.

```
1G`

```

Consider only the longest number of fingers. (I would count the longest fingers using `\G.?` but that doesn't work for some reason.)

```

```

Convert back to decimal and add one for the starting finger.
> 1 votes

# Answer
# , ~~36~~ 18 bytes

Bubbler managed to shave off a full 50% off my program with a few nice tricks and some deft handling of trains.

```
0#@=@(,+/\)2*@-/\]

```

Try it online!

The dyadic verb `*@-/\` takes a prefix size and a list, then computes the sign of the difference of the list (from inserting `-` between elements of the list). In this case, it is used as `2 *@-/\ ]`, which is a fork that takes a list and gives a list of the signs of differences between adjacent elements. (This is an idiom I hoped would exist but couldn't come up with myself.)

Letting `d` denote this result, the rest of the train is `0 #@=@(, +/\) d`, which is equivalent to `# = (0 , +/\ d)`. First, `+/\ d` computes the sum of each prefix of `d`, which like in the previous answer gives a relative finger numbering of all notes of the song. But, since the differences only give relative differences, the fingering of the first note is not present, so zero is prefixed to the list with the `,` dyad.

For some reason I thought I had to take one more than the difference of the maximum and minimum values of this array to count the number of necessary fingers, despite the fact all I had to do was count the number of distinct elements, which would be `# ~.` of the array. However, J has a one-character shorter idiom for this. The `=` monad gives an array with one row per unique element (the rows indicating where that element appears), and the `#` monad counts the number of rows, hence the number of necessary fingers.

---

The original 36-byte solution:

```
1:+(>./-<./)@(0&,)@(+/\)@(}.(*@-)}:)

```

Try it online!

This is a monadic verb that takes a list of numbers.

`*@-` takes the sign of the difference of two numbers. Since `}.` and `}:` cut off the head and tail of a list, the fork `}. (*@-) }:` constructs a list of signs of differences between consecutive elements of the given list.

This is composed with `+/\`, which takes the sums of the prefixes of the list, giving relative finger numbers through the song. This is prefixed with 0 using `0&,` since the song starts with some finger.

This is composed with `>./ - <./`, which takes the difference of the maximum and the minimum of these relative finger numbers, and then the `1:+` fixes a fencepost error: we start counting fingers from 1.
> 1 votes

# Answer
# Husk, 11 bytes

```
→▲mamΣQm±Ẋ-

```

Port of *@ExpiredData*'s 05AB1E answer, so make sure to upvote him!

Try it online.

**Explanation:**

```
         Ẋ   # For each overlapping pair of the (implicit) argument:
          -  #  Subtract them from one another
       m     # Then map over each forward difference:
        ±    #  And take its signum (-1 if <0; 0 if 0; 1 if >0)
      Q      # Get all sublists of those
    m        # Map over each sublist:
     Σ       #  And take its sum
  m          # Map over each sum:
   a         #  And take its absolute value
 ▲           # Then take the maximum of this list
→            # Increase it by 1
             # (after which it is output implicitly as result)

```
> 1 votes

# Answer
# \[C#\], 86 bytes

```
s.Aggregate(0,(i,y)=>{var t=z>y?++i:z<y?--i:i;h[i]=1;z=y;return t;});return h.Count();

```

Try It online!

My goal was to do this using the Linq Aggregate function, but surely not the best way.
> 1 votes

# Answer
# PHP, ~~66~~ 59 bytes

```
for(;$b=$argv[++$i];$a=$b)$f[$n+=$b<=>$a]=1;echo count($f);

```

Try it online!

Pretty straightforward: uses a index counter `$n` which is incremented each time a superior note is to play and decremented when a lower note, with the PHP comparison operator `<=>`. Then an array is set to the value `1` at this index. At the end count the array.

EDIT: saved 7 bytes removing the test on `$i`, we actually don't care if the starting value for `$n` is `0` or `1`
> 1 votes

# Answer
# T-SQL, 125 bytes

Input is taken from table `T` (according to the Code Golf rules for SQL): column `P` represents position and column `V` represents the value.

```
SELECT MAX(S)-MIN(S)+1FROM(SELECT*,SUM(ISNULL(X,0))OVER(ORDER BY P)S FROM(SELECT*,SIGN(V-LAG(V)OVER(ORDER BY P))X FROM T)A)B

```

DB Fiddle
> 1 votes

# Answer
# Japt, 8 bytes

Port of Expired Data's solution.

```
äÎãx rÔÄ

```

Try it
> 0 votes

# Answer
# Stax, 11 bytes

```
£→▓J←εm@φ┤»

```

Run and debug it

Unpacked, ungolfed, and commented, it looks like this.

```
                                    input:[43 48 48 48 52 50 48 50]
:-      get pairwise differences    main:[5, 0, 0, 4, -2, -2, 2]
Z+      prepend a 0                 main:[0, 5, 0, 0, 4, -2, -2, 2]
{:+m    map: numeric sign           main:[0, 1, 0, 0, 1, -1, -1, 1]
:+      prefix sums                 main:[0, 1, 1, 1, 2, 1, 0, 1]
:s^     max - min + 1               main:3

```

Run this one
> 0 votes

---
Tags: code-golf, array
---


title: Russian Roulette, varying chances

text:
# Question
Title: Russian Roulette, varying chances
# Russian roulette

It's Russian roulette! The rules are simple. Shoot a revolver with `n` slots for bullets and one round inside at your head and you *might not die*! This Question is different from other Russian roulette questions because it takes input to change the chance of exiting with an error.

## Task:

Make a program that takes integer `n` (you can assume that 10\<=n\<=128) as input and **outputs nothing.**

> but how do I tell if I'm dead?

The program generates a random number x in the range 0 - n inclusive. If x=0 the revolver fires and the program exits with an error (you die). Otherwise the program exits normally.

If your language needs it, the range can be 1-n inclusive.

Standard loopholes forbidden, etc. Upvote answers in *fun* languages! What I'd really like to see is an answer in a language that doesn't have normal randomness (eg. in Befunge where `?` sends you in a random direction instead of giving a random number).

# Answer
# Charcoal, 5 bytes

```
≔‽‽Ｎθ

```

Try it online! Link is to verbose version of code. Explanation: The  function reads the input number. The  generates a random number between `0` and its argument. However, this errors if the argument is zero. This happens if the inner  randomised a `0`, i.e. 1 in `n` times. The `≔θ` simply serves to make the program do nothing if it was successful.
> 1 votes

# Answer
# APL (Dyalog Unicode), 3 bytes

Full program. Exits with code 11 or 0. Requires `⎕IO←0`.

```
÷?⎕

```

Try it online!

prompt for `n`

`?` generate random integer in range `0``n-1`

`÷` reciprocal (errors if argument is 0)
> 9 votes

# Answer
# JavaScript (V8), 18 bytes

Community consensus is that time can count as a source of randomness. This function will simply take the time in milliseconds modulo the inputted value. If `0`, the function tries to return `a`, which does not exist.

```
n=>Date.now()%n||a

```

Try it online!
> 4 votes

# Answer
# Pyth, 3 bytes

```
JlO

```

Try it online!

`O` \- generate a random integer in the range `0` \- `n-1`

`l` \- log base 2 of that integer. Throws a `math domain error` if `0` was generated

`J` \- assign the value to a variable so that we suppress all output
> 3 votes

# Answer
# Rust + time crate, 38 bytes

```
|n:u8|1/(time::Time::now().second()%n)

```

Defines a closure that takes an unsigned 8-bit integer as input and returns an integer or panics with "attempt to divide by zero".

try it online.

Our rules about using the time as randomness state the following (emphasis mine):

> \[...\] if you have to select one random value per script execution, current **seconds**/milliseconds should be sufficient.
> 1 votes

# Answer
# Python, <sup>~~57~~</sup> 43 bytes

Saved 14 bytes synchronously with thanks to Surculose Sputum!!!

```
lambda n:1/randint(0,n)
from random import*

```

Try it online!
> 0 votes

# Answer
# Python 2, 26 bytes

`id(0)%129%-~n` gives a random number from 0 to n inclusive. It returns an error if it equals 0, because of `ZeroDivisionError`.

```
lambda n:1/(id(0)%129%-~n)

```

Try it online!
> 0 votes

# Answer
# Python 2, 23 bytes

```
1/(id(0)%129%-~input())

```

which is a merging of dingledooper's answer with my original one (below). Try it online!

# Python 2, 40 bytes

```
from random import*
1/randint(0,input())

```

Try it online! Full program.
> 0 votes

# Answer
# Ruby, 14 bytes

```
->n{1./rand~n}

```

Try it online!

Exits with `ZeroDivisionError` when `rand~n` returns 0. It's helpful that `rand` takes the absolute value of its argument.
> 0 votes

# Answer
# `j`, 2 bytes

```
g(

```

## Explanation

```
    Implicit input
g   Randrange 1 to input
 (  Decrement the number by 1

Flag:j (Evaluates the J command at the end of the program)

The J command, given a number operand, reciprocals the number.

It throws a 0-division error when the operand is 0.

```
> 0 votes

# Answer
# MATLAB, 32 bytes

```
@(n)eval('if(randi(n)==n)a;end')

```

`randi(n)` outputs random integer from \[1,2,3...n\] list

`a` is undefined, so when it is called, program errors out
> 0 votes

# Answer
# Python3, 66 bytes

```
0/0 if __import__("random").randint(0,int(input()))==1 else exit()

```
> 0 votes

# Answer
# 05AB1E, 5 bytes

```
Ý<Ω¬F

```

Try it online!
> 0 votes

# Answer
# T-SQL, 24 bytes

```
DECLARE @ INT=10

SET @/=floor(rand()*-~@)

```

**Try it online**
> 0 votes

# Answer
# Java (JDK), 22 bytes

```
n->n/=n*=Math.random()

```

Try it online!
> 0 votes

---
Tags: code-golf, random, game, error-message
---


title: Get me out of here

text:
# Question
Title: Get me out of here
## Challenge

Given a grid size, obstacles' positions, player position and target position your task is to find a path for the player to get to the target and avoid the obstacles at the same time (if necessary).

---

## Input

* **N**: Grid size `N x N`
* **P**: Player's position `[playerposx, playerposy]`
* **T**: Target's position `[targetposx, targetposy]`
* **O**: Obstacles' positions `[[x1, y1], [x2, y2],...,[xn, yn]]`

---

## Output

**Path**: A path player can use to reach target `[[x1, y1], [x2, y2],...,[xn, yn]]`

---

## Rules

1. The point `[0,0]` is on the top-left corner of the grid.
2. Player's position will always be on the left side of the grid.
3. Target's position will always be on the right side of the grid.
4. The grid will always have at least one obstacle.
5. You can assume that no obstacle overlaps player or target position.
6. You don't necessarily need to find the min path.
7. The player can only move left, right, top and bottom not diagonally.
8. You can take the input in any convenient way.
9. You can assume that a path for the player to get to target will always exist.
10. Obviously, for each input multiple valid paths exist, choose one.
11. Assume `N > 2` so the grid will be at least `3 x 3`.

---

## Examples

Input: `9`, `[6, 0]`, `[3, 8]`, `[[0, 5], [2, 2], [6, 4], [8, 2], [8, 7]]`
Possible Output: `[[6, 0], [6, 1], [6, 2], [6, 3], [5, 3], [5, 4], [5, 5], [5, 6], [5, 7], [5, 8], [4, 8], [3, 8]]`

Input: `6`, `[1, 0]`, `[3, 5]`, `[[1, 2], [2, 5], [5, 1]]`
Possible Output: `[[1, 0], [1, 1], [2, 1], [2, 2], [2, 3], [2, 4], [3, 4], [3, 5]]`

---

**Note**

Notice that `X` is for rows and `Y` for cols. Don't confuse them with the coordinates in an image.

**Edit**

As @digEmAll pointed out, due to rules `#2` and `#3`, `playerY = 0` and `targetY = N-1`. So, if you want you can take as input only `playerX` and and `targetX` (if that makes your code shorter).

# Answer
# JavaScript (ES6), 135 bytes

Takes input as `(width, [target_x, target_y], obstacles)(source_x, source_y)`, where *obstacles* is an array of strings in `"X,Y"` format.

Returns an array of strings in `"X,Y"` format.

```
(n,t,o)=>g=(x,y,p=[],P=[...p,v=x+','+y])=>v==t?P:~x&~y&&x<n&y<n&[...o,...p].indexOf(v)<0&&[0,-1,0,1].some((d,i)=>r=g(x+d,y-~-i%2,P))&&r

```

Try it online!

### Commented

```
(n, t, o) =>              // n = width of maze, t[] = target coordinates, o[] = obstacles
  g = (                   // g() = recursive search function taking:
    x, y,                 //   (x, y) = current coordinates of the player
    p = [],               //   p[] = path (a list of visited coordinates, initially empty)
    P = [                 //   P[] = new path made of:
      ...p,               //     all previous entries in p
      v = x + ',' + y     //     the current coordinates coerced to a string v = "x,y"
    ]                     //
  ) =>                    //
    v == t ?              // if v is equal to the target coordinates:
      P                   //   stop recursion and return P
    :                     // else:
      ~x & ~y             //   if neither x nor y is equal to -1
      && x < n & y < n    //   and both x and y are less than n
      & [...o, ...p]      //   and neither the list of obstacles nor the path
        .indexOf(v) < 0   //   contains a position equal to the current one:
      && [0, -1, 0, 1]    //     iterate on all 4 possible directions
        .some((d, i) =>   //     for each of them:
          r = g(          //       do a recursive call with:
            x + d,        //         the updated x
            y - ~-i % 2,  //         the updated y
            P             //         the new path
          )               //       end of recursive call
        ) && r            //     if a solution was found, return it

```
> 5 votes

# Answer
# , 227 bytes

```
function(N,P,G,O){M=diag(N+2)*0
M[O+2]=1
b=c(1,N+2)
M[row(M)%in%b|col(M)%in%b]=1
H=function(V,L){if(all(V==G+2))stop(cat(L))
M[t(V)]=2
M<<-M
for(i in 0:3){C=V+(-1)^(i%/%2)*(0:1+i)%%2
if(!M[t(C)])H(C,c(L,C-2))}}
try(H(P+2,P),T)}

```

Try it online!

Not really short, and definitely not giving the shortest path (e.g. check the first example).
It basically performs a recursive depth-first search and stops as soon as the target has been reached, printing the path.

Thanks to JayCe for the improvement in output formatting
> 5 votes

# Answer
# Python 2, ~~151~~ 149 bytes

```
N,s,e,o=input()
P=[[s]]
for p in P:x,y=k=p[-1];k==e>exit(p);P+=[p+[[x+a,y+b]]for a,b in((0,1),(0,-1),(1,0),(-1,0))if([x+a,y+b]in o)==0<=x+a<N>y+b>-1]

```

Try it online!
> 4 votes

# Answer
# Haskell, ~~133~~ ~~131~~ 130 bytes

* -1 byte thanks to BWO

```
(n!p)o=head.(>>=filter(elem p)).iterate(\q->[u:v|v@([x,y]:_)<-q,u<-[id,map(+1)]<*>[[x-1,y],[x,y-1]],all(/=u)o,x`div`n+y`div`n==0])

```

Try it online! (with a few testcases)

A function `!` taking as input

* `n :: Int` size of the grid
* `p :: [Int]` player's position as a list `[xp, yp]`
* `o :: [[Int]]` obstacles position as a list `[[x1, y1], [x2, y2], ...]`
* `t :: [[[Int]]]` (implicit) target's position as a list `[[[xt, yt]]]` (triple list just for convenience)

and returning a valid path as a list `[[xp, yp], [x1, y1], ..., [xt, yt]]`.

As a bonus, it finds (one of) the shortest path(s) and it works for any player's and target's position. On the other hand, it's *very* inefficient (but the examples provided run in a reasonable amount of time).

## Explanation

```
(n ! p) o =                                                         -- function !, taking n, p, o and t (implicit by point-free style) as input
    head .                                                          -- take the first element of
    (>>= filter (elem p)) .                                         -- for each list, take only paths containing p and concatenate the results
    iterate (                                                       -- iterate the following function (on t) and collect the results in a list
        \q ->                                                       -- the function that takes a list of paths q...
            [u : v |                                                -- ... and returns the list of paths (u : v) such that:
                v@([x, y] : _) <- q,                                -- * v is an element of q (i.e. a path); also let [x, y] be the first cell of v
                u <- [id, map (+ 1)] <*> [[x - 1,y], [x, y - 1]],   -- * u is one of the neighbouring cells of [x, y]
                all (/= u) o,                                       -- * u is not an obstacle
                x `div` n + y `div` n == 0                          -- * [x, y] is inside the grid
            ]
    )

```

This function performs a recursive BFS via `iterate`, starting from the target and reaching the player's starting position. Paths of length \\$k\\$ are obtained by prepending appropriate cells to valid paths of length \\$k-1\\$, starting with the only valid path of length 1, that is the path `[[xt, yt]]`.

The apparently obscure expression `[id, map (+ 1)] <*> [[x - 1,y], [x, y - 1]]` is just a "golfy" (-1 byte) version of `[[x + 1, y], [x, y + 1], [x - 1, y], [x, y - 1]]`.
> 3 votes

# Answer
# APL (Dyalog Unicode), ~~79~~ 75 bytes

```
{⍺←0j¯1⋄n p t o←⍵⋄p=t:p⋄p,(-∘p∇⊣@1∘⍵)⊃s/⍨{~∨/¯1n∊9 11○⍵}¨s←o~⍨p+⍺×0j1*3⌽⍳4}

```

Try it online!

-4 bytes by refactoring `c` thanks to @Adám.

---

# APL (Dyalog Unicode), 79 bytes

```
{⍺←0j¯1⋄n p t o←⍵⋄p=t:p⋄c←⊃s/⍨{~∨/¯1 n∊9 11○⍵}¨s←o~⍨p+⍺×0j1*3⌽⍳4⋄p,(c-p)∇c@1⊢⍵}

```

Try it online!

Takes a 4-element array `N P T O` as input, where `N` is an integer and the coordinates are represented as complex numbers.

Interprets a complex number `x + yi` (`XjY` in APL's notation) as the position `(x, y)`, where `(0, 0)` is at the bottom left of the board and `x` and `y` directions are right and upwards respectively. Uses the right-hand-touching algorithm in this view, which works because both the start and the target are adjacent to the outer wall (and the minimal path is not required). The path may have multiple copies of the same coordinates when it encounters a dead end. To ensure that the player is touching the right-hand wall at start, the direction is initialized to the downwards direction `-i`.

### Ungolfed with comments

```
f←{
  ⍺←0j¯1
  d←⍺                ⍝ direction, default down
  n p t o←⍵          ⍝ decompose the inputs
  p=t:p              ⍝ player = target: reached the goal
  turn←0j1*¯1 0 1 2  ⍝ turns to try out, right turn first
  steps←o~⍨p+d×turn  ⍝ possible steps from current position
  chosen←⊃steps/⍨{~∨/¯1 n∊9 11○⍵}¨steps  ⍝ the free spot with highest precedence
  d2←chosen-p        ⍝ keep track of the previous step
  p,d2∇n chosen t o  ⍝ move one step and recurse
}

```
> 2 votes

# Answer
# Retina 0.8.2, 229 bytes

```
.
$&$&
@@
s@
##
.#
{`(\w.)\.
$1l
\.(.\w)
r$1
(?<=(.)*)\.(?=.*¶(?<-1>.)*(?(1)$)\w)
d
}`\.(?=(.)*)(?<=\w(?(1)$)(?<-1>.)*¶.*)
u
+T`.`#`.(?=(.)*)(?<=d#(?(1)$)(?<-1>.)*¶.*)|(?<=(.)*.).(?=.*¶(?<-2>.)*(?(2)$)u#)|(?<=#r).|.(?=l#)
.(.)
$1

```

Try it online! Not sure whether the I/O format qualifies. Explanation:

```
.
$&$&

```

Duplicate each cell. The left copy is used as a temporary working area.

```
@@
s@

```

Mark the start of the maze as visited.

```
##
.#

```

Mark the end of the maze as being empty.

```
{`(\w.)\.
$1l
\.(.\w)
r$1
(?<=(.)*)\.(?=.*¶(?<-1>.)*(?(1)$)\w)
d
}`\.(?=(.)*)(?<=\w(?(1)$)(?<-1>.)*¶.*)
u

```

While available working cells exist, point them to adjacent previously visited cells.

```
+T`.`#`.(?=(.)*)(?<=d#(?(1)$)(?<-1>.)*¶.*)|(?<=(.)*.).(?=.*¶(?<-2>.)*(?(2)$)u#)|(?<=#r).|.(?=l#)

```

Trace the path from the exit to the start using the working cells as a guide.

```
.(.)
$1

```

Delete the working cells.
> 1 votes

# Answer
## JavaScript, 450 bytes

Takes input as `(n, {playerx, playery}, {targetx, targety}, [{obstaclex, obstacley}])`. Returns an array of `{hopx, hopy}`.

```
j=o=>JSON.stringify(o);l=a=>a.length;c=(a,o)=>{let i=l(a);while(i>0){i--;if(j(a[i])==j(o)){return 1;}}return 0;}h=(p,t,o)=>{if(p.y<t.y&&!c(o,{x:p.x,y:p.y+1})){return{x:p.x,y:p.y+1};}if(p.y>t.y&&!c(o,{x:p.x,y:p.y-1})){return{x:p.x,y:p.y-1};}if(p.x<t.x&&!c(o,{x:p.x+1,y:p.y})){return{x:p.x+1,y:p.y};}if(p.x>t.x&&!c(o,{x:p.x-1,y:p.y})){return{x:p.x-1,y:p.y};}return t;}w=(n,p,t,o)=>{let r=[];r.push(p);while(j(p)!==j(t)){p=h(p,t,o);r.push(p);}return r;}

```

Here is an unobfuscated version on my mess:

```
// defining some Array's function for proper comparaisons
json = (object) => { return JSON.stringify(object) };
length = (array) => { return array.length; }
contains = (array, object) => {
    let i = length(array);
    while (i > 0) {
    i--;
        if (json(array[i]) == json(object)) { return true; }
    }
    return false;
}
//return next found hop
getNextHop = (player, target, obstacles) => {
    //uggly serie of conditions
    //check where do we have to go and if there is an obstacle there
    if(player.y<target.y && !contains(obstacles, [x:player.x, y:player.y+1])) { return [x:player.x, y:player.y+1]; }
    if(player.y>target.y && !contains(obstacles, [x:player.x, y:player.y-1])) { return [x:player.x, y:player.y-1]; }
    if(player.x<target.x && !contains(obstacles, [x:player.x+1, y:player.y])) { return [x:player.x+1, y:player.y]; }
    if(player.x>target.x && !contains(obstacles, [x:player.x-1, y:player.y])) { return [x:player.x-1, y:player.y]; }
    return target;
}
//return found path
getPath = (gridsize, player, target, obstacles) => {
    let path = [];
    path.push(player);
    //while player is not on target
    while(json(player)!=json(target)) {
        player = getNextHop(player, target, obstacles); //gridsize is never used as player and target are in the grid boundaries
        path.push(player);
    }
    return path;
}

```
> 1 votes

---
Tags: code-golf, grid, path-finding
---


# Question
Title: The first digit of a to the power of b (approximately)
Inspired by This answer to a Puzzling question

**Background - exponentiation by squaring**
*If you don't want to read the background, or don't understand it, there's a worked example in Java, linked at the bottom of the post.*

\\$a^{2^{x+1}} = a^{2^{x}} * a^{2^{x}}\\$

Therefore to find \\$a^b\\$ (where \\$a\\$ and \\$b\\$ are base-10 numbers), you can use the following steps:

(using the example: \\$a^b = 3^{2020} = 6.0944502154628860109199404161593e+963\\$)

1. Convert \\$b\\$ to binary (\\$2020\\$ -\> \\$11111100100\\$)
2. For each \\$1\\$ in the binary (\\$n\\$), calculate \\$a^n\\$, by starting at \\$a^1\\$ and repeatedly squaring to get \\$a^2\\$, \\$a^4\\$, etc... and keeping only those numbers we need (\\$3^1 = 3\\$, \\$3^2 = 9\\$, squared gives \\$3^4 = 81\\$, squared gives \\$3^8 = 6561\\$, squared gives \\$3^{16} = 43046721\\$, squared gives \\$3^{32} = 1853020188851841\\$, etc. We just keep those numbers where the binary mask is a 1.)
3. Multiply all the kept answers from step 2 where the binary mask is a \\$1\\$ (\\$81\*1853020188851841\*...\\$).
4. The first non-zero digit is therefore \\$6\\$.

The problem with this method though, even though it is easier for humans than calculating such a large exponent straight-off, is that you still have to square some pretty large numbers.

***In Theory, though, we can approximate!***

According to the link at the start of the question, you can approximate by just considering the first \\$n\\$ digits (rounded) at each stage in step 2 above - with larger \\$n\\$ giving a lower margin of error.

**For example**, if \\$n=4\\$, then you get\* \\$3^2=9,^2=81,^2=6561,^2\approx4305,^2\approx1853,^2\approx3434,^2\approx1179,^2\approx1390,^2\approx1932,^2\approx3733\\$.

note that the numbers here have been rounded<sup>*</sup>, rather than just truncated - e.g. 6561 * 6561 = 43046721 - which has been rounded to 430**5** rather than 430**4**.

Keeping \\$3733,1932,1390,1179,3434,1853,81\\$ from the bitmask we can then do \\$3733\*1932\*1390\*1179\*3434\*1853\*81= 6091923575465178358320\\$, so the first digit is \\$6\\$, as we would expect.

This is not only easier in our heads, but it gives us the same first digit! Much simpler!

However, if we only consider the first \\$3\\$ digits when we double, instead of the first \\$4\\$, we get \\$353\*188\*137\*117\*342\*185\*81 = 5451573062187720\\$, which gives us a first digit of \\$5\\$ instead of \\$6\\$ \- that's why it's only approximately accurate!

---

**The Challenge** is to find the first digit of \\$a^b\\$, where only the first \\$n\\$ digits, rounded, are considered each time we square. You don't have to use exponentiation by squaring in your program, if you can get the correct answers by another method.

**Inputs**

Three positive Integers (greater than \\$0\\$), up to an arbitrary maximum (your program should work in theory for all possible Integers) - the base \\$a\\$, the exponent \\$b\\$ and the approximation length \\$n\\$

**Output**

a single digit or character in the range \[1..9\]

**Some Worked Examples**

`3,2020,3` -\> `5` (see worked example in background above)
`3,2020,4` -\> `6` (see worked example in background above)

`2,20,1` -\> \\$20\_{10} = 10100\_2. 2^1=2,^2=4,^2=16\approx2,^2=4,^2=16\approx2\\$ which gives \\$2^{16}\*2^4\approx2\*2\\$ = `4`
`2,20,2` -\> \\$2^1=2,^2=4,^2=16,^2=256\approx26,^2=676\approx68\\$ which gives \\$68\*16 = 1088\\$, first digit `1`
`2,20,3` -\> \\$2^1=2,^2=4,^2=16,^2=256,^2=65536\approx655\\$ which gives \\$655\*16 = 10480\\$, first digit `1`
`2,20,4` -\> \\$6554\*16 = 104864\\$, first digit `1`
`2,20,5 or above` -\> \\$65536\*16 = 1048576\\$, first digit `1`

`15,127,5` -\> `15,225,50625,25629...,65685...,43145...,18615...` -\> `231009687490539279462890625` -\> `2`

**The same Examples formatted for easy copying, plus some additional ones**

```
a,b,n,outputs result
3,2020,3 outputs 5
3,2020,4 outputs 6
3,2020,5 outputs 6
2,20,1 outputs 4
2,20,2 outputs 1
2,20,3 outputs 1
2,20,4 outputs 1
2,20,5 outputs 1
2,20,6 outputs 1
2,11111,4 outputs 5
4,1234,3 outputs 8
5,54,2 outputs 6
6,464,3 outputs 1
7,2202,4 outputs 8
8,1666,5 outputs 3
9,46389,6 outputs 2
10,1234,7 outputs 1
11,5555,8 outputs 8
12,142,14 outputs 1

```

Sample implementation on TIO

This is , usual rules and restrictions apply, lowest bytes wins.

---

**EDIT**

\*to clarify what I mean by rounding, any number less than \\$x.5\\$ should round down to \\$x\\$. Any number greater than \\$x.5\\$ should round up to \\$x+1\\$. The boundary (\\$x.5\\$) can go either way, depending on your language.

# Answer
> 5 votes
# Python 2, 88 bytes

```
a,b,n=input()
s=1
while b:a=int(`a`[:n])+(`a`[n:]>"5");s*=a**(b%2);a*=a;b/=2
print`s`[0]

```

Try it online! or Check all test cases!

Reads 3 integers from `STDIN`, and print out the first digit approximation.

**Rounding**: `x.5` is always rounded down. This causes the test case `(5, 54, 2)` to gives the wrong result.

**Explanation**:

This part is the regular exponentiation by squaring:

```
while b:s*=a**(b%2);a*=a;b/=2

```

This is the rounding part:

```
a=int(`a`[:n])+(`a`[n:]>"5")

```

which takes the first `n` digits of `a`, and adds an extra 1 if the remaining part is more than `5`.

# Answer
> 2 votes
# JavaScript (Node.js), 100 bytes

Takes input as `(b)(n)(a)`, where \\$a\\$ and \\$b\\$ are BigInts.

```
b=>n=>g=(a,k=p=1n)=>k>b?(p+g)[0]:g((BigInt((a*a+'0'.repeat(n)).slice(0,n+1))+5n)/10n,k+k,b&k?p*=a:0)

```

Try it online!

---

# JavaScript (ES6),  ~~92~~  87 bytes

*Improved the upper bound of \\$n\\$ thanks to @Neil*

Without BigInts. Works for \\$n\le 10\\$.

```
b=>n=>g=(a,k=p=1)=>k>b?(p+g)[0]:g((+(a*a).toPrecision(n)+'').slice(0,n),k+k,b&k?p*=a:0)

```

Try it online!

### How?

At each iteration:

* We compute \\$a^2\\$ with \\$n\\$ significant digits thanks to the `.toPrecision()` method. This gives a string, which may be in scientific notation.

Example for \\$a=1023\\$:

```
  (1046529).toPrecision(4) ~> "1.047e+6"

```
* we coerce this result to a number and immediately back to a string:

```
  +(1046529).toPrecision(4)+'' ~> "1047000"

```
* we keep the \\$n\\$ first characters to get the new value of \\$a\\$:

```
  (+(1046529).toPrecision(4)+'').slice(0,4) ~> "1047"

```

The highest value of \\$n\\$ that can be supported is \\$10\\$ because:

$$(10^{10}-1)^2=99999999980000000000$$

which is already greater than `Number.MAX_SAFE_INTEGER`, but sill coerced to its standard decimal representation `"99999999980000000000"`.

For \\$n\>10\\$, the result is always stringified in scientific notation (e.g. `9.9999999998e+21`) and the algorithm doesn't work anymore.

# Answer
> 2 votes
# Charcoal, 45 bytes

```
ＮθＮηＮζＦ⮌↨η²«Ｆι⊞υθ≧×θθ¿›ＬＩθζ≔÷⁺⁵Ｉ…Ｉθ⊕ζχθ»§ＩΠυ⁰

```

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

```
ＮθＮηＮζ

```

Input `a`, `b` and `n`.

```
Ｆ⮌↨η²«

```

Loop over the bits of `b` from LSB to MSB.

```
Ｆι⊞υθ

```

If the current bit of `b` is set then push `a` to the empty list.

```
≧×θθ

```

Square `a`.

```
¿›ＬＩθζ

```

If `a` has more than `n` digits...

```
≔÷⁺⁵Ｉ…Ｉθ⊕ζχθ

```

... then take the first `n+1` digits, add `5`, and drop the last digit, thus rounding the power of `a` to `n` digits.

```
»§ＩΠυ⁰

```

Print the first digit of the product of the desired powers of `a`.

# Answer
> 1 votes
# Python 3.8 (pre-release), 131 bytes

```
lambda a,b,n:(m:=a)and str(math.prod((m:=round(m/10**(len(str(m))-n)))**int((m:=m**2)and c)for c in f"{b:b}"[::-1]))[0]
import math

```

Try it online! **How it works:**

```
lambda a,B,n:                      # function taking the three arguments as input
             (m:=a)and             # initialize the base for repeated squaring and
                       str(...)[0] # return the first digit of the string representing the final number

# Inside str():
math.prod(                           ) # the product of (new in 3.8)
          ... for c in f"{B:b}"[::-1]  # something we compute for each character in the reversed binary representation of the input B

# Use repeated := to modify the base we keep squaring
# Inside math.prod(... for c in f"{B:b}"[::-1])
(m:=                            )                      # modify m
    round(m/10**(len(str(m))-n))                       # by rounding it to the first n digits
                                       (m:=m**2)and    # finally we square m again (without effecting anything else)
                                 **int(             c) # and only include this number in the product if the binary digit is 1

```

My `(5, 54, 2)` test case gives a different result; I suspect it is because of how Python rounds `62.5` vs how the reference implementation rounds `62.5`. Python rounds it down to `62`, but if I force Python to round up I get the reference solution of `6`.

# Answer
> 1 votes
# 05AB1E (legacy), 20 bytes

```
b©vDnDg°I°÷/ò})®RÏPн

```

Uses the legacy version of 05AB1E, because division-by-zero errors will result in the initial integer, whereas the new 05AB1E version would make it 0 instead.

Input-order as \\$b,a,n\\$.
Just like both Python answers, the test case `54,5,2` will result in `4` instead of `6`, because of different rounding than the Java reference implementation.

Try it online or verify all test cases.

**Explanation:**

```
b              # Convert the (implicit) input-integer `b` to a binary string
 ©             # Store it in variable `®` (without popping)
  v            # Pop and loop its length amount of times:
   D           #  Duplicate the top value
               #  (which is the implicit input-integer `a` in the first iteration)
    n          #  Square it
     Dg        #  Take its length without popping (by duplicating first)
       °       #  Take 10 to the power that length
        I°     #  Take 10 to the power input-integer `n` as well
          ÷    #  Integer-divide 10^length by 10^n
           /   #  Divide the current square by this
               #  (the value remains the same for division-by-zero errors in the legacy
               #   version, which will happen if the amount of digits in the squared
               #   value is smaller than `n`)
            ò  #  And bankers-round that decimal to the nearest integer
  })           # After the loop: wrap all values on the stack into a list
    ®R         # Push the binary-string from `®` and reverse it
      Ï        # Only leave the values in the list at the 1-bits
       P       # Take the product of those remaining values
        н      # And pop and push its first digit
               # (after which it is output implicitly as result)

```

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


title: Generate *all* coprime tuples

text:
# Question
Title: Generate *all* coprime tuples
Given integers `k` and `n`, generate a sequence of `n` unique *k-tuples* of pairwise coprime integers. *Every* such tuple must occur once eventually, that is, for any existing k-tuple of pairwise coprime integers, some `n` will eventually generate it.

The output may be printed or evaluated in any list/tuple-like form.

### Definitions

* Two numbers `a` and `b` are **coprime** if `gcd(a, b) = 1`, i.e. they share no common divisor other than 1.
* A tuple of `k` numbers `(a1, a2, ..., ak)` is **pairwise coprime** if every pair of numbers in the tuple is coprime.

### Examples

```
 k =  1, n =  5 -> [[1],[2],[3],[4],[5]]
 k =  2, n =  7 -> [[2,1],[3,1],[3,2],[4,1],[4,3],[5,1],[5,2]]
 k =  3, n = 10 -> [[3,2,1],[4,3,1],[5,2,1],[5,3,1],[5,3,2],[5,4,1],[5,4,3],[6,5,1],[7,2,1],[7,3,1]]
 k =  4, n =  2 -> [[5,3,2,1],[5,4,3,1]]
 k =  5, n =  0 -> []

```

### Notes

* Standard code golf rules, shortest code wins.
* `k` is assumed to be positive, and `n` non-negative.
* The numbers within each tuple must be positive, distinct, and may appear in any order.
* Uniqueness is up to ordering: e.g. `(1,2,3)` is the same as `(1,3,2)`.
* Good luck and have fun!

# Answer
# 05AB1E, 13 bytes

I think it has been 389 days since I last posted something here haha. There is definitely some golfing potential left in this program.

### Code

Uses the **05AB1E**-encoding.

```
∞æ¹ùʒPy.¿Q}²£

```

**Try it online!**

### Explanation

It is worth noting that for two numbers \\$n, m \in \mathbb{Z}^+\\$ that:

$$ \tag{1} \label{1} \gcd(n, m) \cdot \text{lcm}(n, m) = n \cdot m $$

This means that for two numbers \\$n, m \in \mathbb{Z}^+\\$ where the \\$\gcd(n, m) = 1\\$, we can conclude that the \\$\text{lcm}(n, m) = n \cdot m\\$.

Furthermore, the \\$\gcd\\$ function is a multiplicative function, which means that if \\$n\_1\\$ and \\$n\_2\\$ are relatively prime, then:

$$ \gcd(n\_1 \cdot n\_2, m) = \gcd(n\_1, m) \cdot \gcd(n\_2, m) $$

From this, we obtain the fact that:

$$ \tag{2} \label{2} \gcd(a, bc) = 1 \iff \gcd(a, b) = 1 \wedge \gcd(a, c) = 1 $$

Let us denote a \\$k\\$-tuple of positive integers as \\$S = \\{x\_1, x\_2, \dots, x\_k\\}\\$. A set \\$S\\$ is pairwise coprime, if and only if:

$$ \tag{3} \label{3} \forall a, b \in S \wedge a \not = b \rightarrow \gcd(a, b) = 1 $$

Using Equations \\$\eqref{1}, \eqref{2}\\$ and \\$\eqref{3}\\$, we can conclude that a set \\$S = \\{x\_1, x\_2, \dots, x\_k\\}\\$ is pairwise coprime, if and only if:

$$ \text{lcm}(x\_1, x\_2, \dots, x\_k) = \prod\_{x \in S} x $$

### Code Explanation

```
∞æ¹ùʒPy.¿Q}²£

∞æ              # Powerset of the infinite list [1, ..., ∞].
  ¹ù            # Keep only lists of length *k*.
    ʒ     }     # Filter. Keep lists where the
     P          #   product of the list
         Q      #   is equal to
      y.¿       #   the least common multiple of the list
           ²£   # Retrieve the first *n* elements.

```
> 8 votes

# Answer
# Husk, 9 bytes

```
↑fËoε⌋`ṖN

```

Try it online!

## Explanation

A straightforward solution, not the most exciting.

```
↑fËoε⌋`ṖN  Implicit inputs, say k=3, n=2.
        N  Natural numbers: [1,2,3,4,..
      `Ṗ   All k-element subsets: [[1,2,3],[2,3,4],[1,3,4],..
           ` flips the arguments of Ṗ since it expects the number first.
 f         Keep those that satisfy this:
  Ë          All pairs x,y (not necessarily adjacent) satisfy this:
     ⌋         their gcd
   oε          is at most 1.
           Result is all pairwise coprime subsets: [[1,2,3],[1,3,4],..
↑          Take the first n: [[1,2,3],[1,3,4]]

```
> 6 votes

# Answer
# Wolfram Language (Mathematica), 106 bytes

```
(s=Range[#2#];If[#==1,List/@s,SortBy[Select[s~(S=Subsets)~{#},Union[GCD@@@#~S~{2}]=={1}&],Last][[;;#2]]])&

```

Try it online!
> 3 votes

# Answer
# Jelly, 16 bytes

```
‘×ÆNœcŒcg/€$ÐṂḣ⁸

```

A dyadic Link accepting `n` on the left and `k` on the right.

**Try it online!**

There must be a better way than this inefficient monstrosity! It'll time out for quite small inputs since it inspects all k-tuples of the natural numbers up to the `(n+1)*k`-th prime! (The `+1` is only needed to handle `n=0`.)
> 3 votes

# Answer
# Python 3, 153 bytes

```
lambda n,k,R=range:[[*t,r]for r in R(n+k+2)for t in combinations(R(1,r),k-1)if all(sum(x%i<1for x in[*t,r])<2for i in R(2,r))][:n]
from itertools import*

```

Try it online!

A function that takes `n, k` as arguments and returns out the list of `n` co-prime k-tuples.

The tuple are generated with increasing maximum, so it's guaranteed that every co-prime tuple will eventually be printed as `n` increases.
> 2 votes

# Answer
# JavaScript (ES6), 143 bytes

Takes input as `(k)(n)`.

```
(k,x=0)=>F=n=>n?(g=a=>x>>i?x>>i++&1?a.some(x=>(C=(a,b)=>b?C(b,a%b):a>1)(x,i))?[]:g([...a,i]):g(a):b=a)(i=[],x++).length-k?F(n):[b,...F(n-1)]:[]

```

Try it online!

### Commented

```
( k,                        // outer function taking k
  x = 0                     // x = bit mask of integers to include in the tuple
) =>                        //
F = n =>                    // F = recursive function taking n
n ?                         // if n is not equal to 0:
  ( g = a =>                //   g is a recursive function taking a[]:
      x >> i ?              //     if x is greater than or equal to 2**i:
        x >> i++ & 1 ?      //       if the i-th bit is set in x:
          a.some(x =>       //         for each value x in a[]:
            ( C = (a, b) => //           C tests whether a and b are coprime:
              b ?           //             if b is not equal to 0:
                C(b, a % b) //               recursive call with (b, a mod b)
              :             //             else:
                a > 1       //               true if *not* coprime
            )(x, i)         //           initial call to C with (x, i)
          ) ?               //         end of some(); if truthy:
            []              //           abort by returning an empty array
          :                 //         else:
            g([...a, i])    //           append i to a[] and call g again
        :                   //       else:
          g(a)              //         just call g with a[] unchanged
      :                     //     else:
        b = a               //       done: return a[] and save it in b[]
  )(i = [], x++)            //   initial call to g with a = [], i = 0; increment x
  .length - k ?             //   if the length of the result is not equal to k:
    F(n)                    //     just call F with n unchanged
  :                         //   else:
    [b, ...F(n - 1)]        //     append b[] to the final result and decrement n
:                           // else:
  []                        //   stop recursion

```
> 2 votes

# Answer
# Charcoal, 58 bytes

```
ＮθＮη≔⁰ζ⊞υ⟦⟧Ｗ‹ＬΦυ⁼Ｌκθη«≦⊕ζＦΦυ⬤κ⬤…²ζ∨﹪μξ﹪ζξ⊞υ⁺⟦ζ⟧κ»Ｉ…Φυ⁼Ｌιθη

```

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

```
ＮθＮη

```

Input `k` and `n`.

```
≔⁰ζ⊞υ⟦⟧

```

Start the master list with a 0-tuple whose largest number is 0.

```
Ｗ‹ＬΦυ⁼Ｌκθη«

```

Repeat until we have at least `k` `n`-tuples.

```
≦⊕ζ

```

Increment the candidate number.

```
ＦΦυ⬤κ⬤…²ζ∨﹪μξ﹪ζξ

```

Filter out all of the existing tuples where at least one member has a common factor with the candidate.

```
⊞υ⁺⟦ζ⟧κ

```

Prepend the candidate to each remaining tuple and push all the resulting tuples back to the master list.

```
»Ｉ…Φυ⁼Ｌιθη

```

Print the first `n` `k`-tuples.
> 2 votes

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


# Question
Title: Inverse of Conway base 13 function in \$\mathbb{Q}\$
(The \\$\mathbb{Q}\\$ in the title means rational numbers.)

## Background

**Conway base 13 function** is an example of a strongly Darboux function, a function that takes every real number on any open interval \\$(a,b)\\$. In other words, for any given real numbers \\$a, b, y\\$, you can find a value \\$x\\$ between \\$a\\$ and \\$b\\$ such that \\$f(x) = y\\$.

The function is defined as follows:

1. Write the input value `x` in base 13 using thirteen symbols `0 .. 9, A, B, C`, without any trailing infinite stream of `C`s. (It is related to the fact `0.9999... = 1` in base 10, or `0.CCC... = 1` in base 13.)
2. Delete the sign and decimal point, if present.
3. Replace `A`s with `+`, `B`s with `-`, `C`s with `.`.
4. Check if some (possibly infinite) suffix of the sequence starts with a sign (`+` or `-`) and contains exactly one `.` and no extra signs. If such a suffix exists, interpret it as a decimal number; it is the value of \\$f(x)\\$. Otherwise, \\$f(x) = 0\\$.

Some examples:

* \\$f(123B45.A3C14159\dots \_{13}) = f(0.A3C14159\dots \_{13}) = 3.14159\dots \\$
* \\$f(B1C234 \_{13}) = -1.234\\$
* \\$f(1C234A567 \_{13}) = 0\\$

## Task

Given three rational numbers \\$a = \frac{a\_n}{a\_d}, b = \frac{b\_n}{b\_d}, y = \frac{y\_n}{y\_d}\\$ given as integer fractions, find a value of \\$x = \frac{x\_n}{x\_d}\\$ between \\$a\\$ and \\$b\\$ (exclusive) such that \\$f(x) = y\\$ (where \\$f\\$ is the Conway base 13 function). There are infinitely many values of \\$x\\$ that satisfy the condition for any input; just output one of them.

You can assume \\$a \< b\\$, \\$a\_d, b\_d, y\_d \> 0\\$, \\$y \ne 0\\$, and the fractions are given in the reduced form. Negative input numbers are represented using negative numerators. You don't need to reduce the output fraction.

Standard rules apply. The shortest code in bytes wins.

## Examples

### `a = 0/1, b = 1/1, y = 1/3`

Decimal representation of \\$y\\$ is \\$0.\overline{3}\\$ (where the overline is the notation for repeating decimal). To get this value, the minimal base-13 suffix of \\$x\\$ is \\$+.\overline{3}\\$ or \\$AC\overline{3}\\$. An example of such an \\$x\\$ would be \\$0.AC\overline{3}\_{13} = 569/676\\$. Proof by Wolfram|Alpha.

### `a = 2017/2197, b = 2018/2197, y = -1/5`

The minimal base-13 suffix of \\$x\\$ is \\$-.2 = BC2\_{13}\\$. But the value of `a` is exactly \\$0.BC2\_{13}\\$, so we can't use that. And the value of `b` is \\$0.BC3\_{13}\\$, so we're forced to begin with \\$0.BC2\\$. One possible value of \\$x\\$ is \\$0.BC2BC2\_{13} = 4433366 \\; / \\; 4826809\\$.

### `a = 123/10 = c.3b913b91..., b = 27011/2196 = c.3b93b9..., y = 987/1`

One possible answer is \\$x = c.3b92a987c\_{13} = 130435909031 \\; / \\; 10604499373\\$.

### `a = -3/2, b = -4/3, y = -1/7`

One possible answer is \\$x = -1.5bc\overline{142857}\_{13} = -28108919 \\; / \\; 19316024\\$.

# Answer
> 5 votes
# Python 2, ~~254 237 219 216~~ 207 bytes

*-3 bytes thanks to @KevinCruijssen !*

Can save 1 more byte by replacing `X=e**(A+B)` with `X=e**A**B`, but the result will be humongous, and the time taken to run will be very long.

```
e=13
a,A,b,B,y,Y=input()
X=e**(A+B)
x=a*X/A+2
r=abs(y)
s="AB"[y<0]+`r/Y`+"C"
R=[]
exec"R=[r]+R;r=r%Y*10;s+=`r/Y`;"*-~Y
n=~R.index(r)
T=e**-n-1
S=e**len(s)*T
print(int(s,e)*T+int(s[n:],e))*((x>0)*2-1)+x*S,X*S

```

Try it online! or Check all test cases!

A program that takes in 6 integers from `STDIN`, and prints out the numerator and denominator of the result.

### Big idea

* First, find a number \\$c\\$ such that \\$a \< c \< b\\$ and \\$c\\$ has finite base-13 representation. Note that \\$c\\$ should be "sufficiently far away" from \\$a\\$ and \\$b\\$. This will be the prefix of \\$x\\$.
For example: \\$a = 1.1...\_{13}, b = 1.3...\_{13}\\$ then \\$c = 1.2\_{13}\\$. We say that \\$c\\$ is sufficiently far away from \\$a\\$ and \\$b\\$, since we can add any suffix to \\$c\\$ and it is guaranteed to stay in the range \\$(a,b)\\$.
* Then find the suffix of \\$x\\$ by finding the base-10 representation of \\$y\\$, then replacing `+-.` with `ABC`. E.g with \\$y = 1/3\\$, the suffix is \\$+0.(3)=A0C(3)\\$
* Join the prefix and suffix together. E.g \\$x = 1.2A0C(3)\\$.

### Details

**Finding the prefix:**

The prefix has the form \\$x/X\\$, where \\$X\\$ is a power of 13.

Consider the integers \\$\Bigl \lfloor \frac{aX}{A} \Big \rfloor \\$ and \\$\Bigl \lfloor \frac{bX}{B} \Big \rfloor \\$ (where \\$X = 13^i\\$), which are the truncations of \\$a/A\\$ and \\$b/B\\$ to a certain base-13 precision. If there is an integer \\$x\\$ between those 2 numbers such that \\$x\\$ is at least 2 away from both numbers, then \\$x/X\\$ can be the prefix. This is because no matter what suffix is added, the value of \\$x/X\\$ won't change by more than \\$1/X\\$.

\\$X=13^{A+B}\\$ is guaranteed to be large enough to see a large gap between the truncation of \\$a/A\\$ and \\$b/B\\$.

This is the part that finds the prefix:

```
X=e**(A+B)
x=a*X/A+2

```

**Finding the suffix:**

First, the long division \\$y/Y\\$ is performed to find the decimal representation (with repeated digit). `r` is the current remainder, and `R` keeps track of the seen remainder after each digit division, in order to detect repeating decimals. \\$y/Y\\$ is calculated until \\$Y+1\\$ digits after the decimal point, which is sufficient to detect repeating groups of digits.

```
r=abs(y)
s="AB"[y<0]+`r/Y`+"C"
R=[]
exec"R=[r]+R;r=r%Y*10;s+=`r/Y`;"*-~Y

```

The suffix has the form \\$stttt... = s(t)\\$, where \\$s\\$ is the result of truncated \\$y/Y\\$ above, and \\$t\\$ is the repeating decimals found in \\$s\\$.

```
n=~R.index(r)
t = s[n:]

```

Thus, our result should have the form \\$\frac{x + 0.sttt...\_{13}}{X}\\$ (or \\$\frac{x - 0.sttt...\_{13}}{X}\\$ if \\$x\\$ is negative)

To convert `0.s(t)` in base 13 to fraction, the following formula is used: $$ 0.s(t) = 0.sttt... = \frac{s.(t)}{13^i} $$ $$ s.(t) = s.ttt... = s + \frac{t}{13^j-1} $$ where \\$i, j\\$ are the number of digits in \\$s, t\\$.

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

```
a=13;b=Floor;c=RealDigits@#~FromDigits~a&;(d=b[+##2/2,e=a^b@Log[a,#3-#2]/a])+If[d<0,-e,e]/a(If[#<0,11,10]+(c[f=b[g=Abs@#]]a+12+c[g-f])/a^IntegerLength@f/a)&

```

Try it online! Pure function. Takes the rational numbers \\$y\\$, \\$a\\$, and \\$b\\$ (in that order) as input and returns the rational number \\$x\\$ as output. The function directly uses rational arithmetic; I wrote another algorithm which manipulates the individual digits, but it took 192 bytes. I'm pretty sure that another few bytes can be squeezed out of this one, though, since the negative-number handling is somewhat sloppy. Also, here's an ungolfed version to clarify the logic:

```
Block[{y = #, a = #2, b = #3, conv = FromDigits[RealDigits[#], 13] &,
   pref, prefexp, ipart, sign},
  prefexp = 13^Floor[Log[13, b - a]]/13;
  pref = Floor[(a + b)/2, prefexp];
  ipart = Floor[Abs[y]];
  pref + If[pref < 0, -1, 1] prefexp/
     13 (If[y < 0, 11, 10] +
      13^-(IntegerLength[ipart] + 1) (13 conv[ipart] + 12 +
         conv[Abs[y] - ipart]))] &

```

---
Tags: code-golf, math, base-conversion
---


title: Break The Chain

text:
# Question
Title: Break The Chain
You are given an \\$ 25 \times 25 \\$ square lattice graph. You are to remove certain nodes from the graph as to *minimize* your score, based on the following scoring system:

Your score will be the \\$ \text{number of nodes removed} \\$ \\$ + \\$ the \\$ \text{size of the largest connected component} \\$. In the smaller \\$ 4 \times 4 \\$ example below, exactly \\$ 5 \\$ nodes have been crossed out (removed), and the size of the largest connected component is \\$ 4 \\$ (top and left components). Therefore the total score is \\$ 9 \\$.

## Notes

* You should give your score alongside a list of crossed out nodes
* If a program was written to solve this problem, please include it in your answer if possible
* Here is a program to check your score

This is , so the *minimum* score wins!

# Answer
> 13 votes
# 92+41=133

```
.......X.........X.......
........X.......X........
.......X.........X.......
......X.X.......X.X......
.....X...X.....X...X.....
....X.....X...X.....X....
...X.......X.X.......X...
X.X.........X.........X.X
.X.X.......X.X.......X.X.
....X.....X...X.....X....
.....X...X.....X...X.....
......X.X.......X.X......
.......X.........X.......
......X.X.......X.X......
.....X...X.....X...X.....
....X.....X...X.....X....
.X.X.......X.X.......X.X.
X.X.........X.........X.X
...X.......X.X.......X...
....X.....X...X.....X....
.....X...X.....X...X.....
......X.X.......X.X......
.......X.........X.......
........X.......X........
.......X.........X.......

```

Now with 13 regions, all of 41.

# Previous version 93+46=139

```
X...........X...........X
.X..........X..........X.
..X.........X.........X..
...X.......X.X.......X...
....X.....X...X.....X....
.....X...X.....X...X.....
......X.X.......X.X......
.......X.........X.......
......X.X.......X.X......
.....X...X.....X...X.....
....X.....X...X.....X....
...X.......X.X.......X...
XXX.........X.........XXX
...X.......X.X.......X...
....X.....X...X.....X....
.....X...X.....X...X.....
......X.X.......X.X......
.......X.........X.......
......X.X.......X.X......
.....X...X.....X...X.....
....X.....X...X.....X....
...X.......X.X.......X...
..X.........X.........X..
.X..........X..........X.
X...........X...........X

```

8 regions of 46, 4 regions of 41.

# Answer
> 9 votes
# Lower bound: 114

**Notation:** Add 25 points to each side of the grid to produce a 27-by-27 grid with corners missing. Call these additional 100 points \\$\mathcal{E}\\$. Let \\$\mathcal{X}\\$ denote the set of deleted points. Say the \\$i\\$th component has \\$c\_i\\$ points and is bounded by \\$x\_i\\$ members of \\$\mathcal{X}\\$ and by \\$e\_i\\$ members of \\$\mathcal{E}\\$.

**Constraints:** First, components that border \\$\mathcal{E}\\$ border disjoint subsets of \\$\mathcal{E}\\$, and so

$$\sum\_i e\_i \leq 100.$$

Next, consider the simple polygon with vertices/perimeter at the members of \\$\mathcal{X}\\$ and \\$\mathcal{E}\\$ that border the \\$i\\$th component. By Pick's theorem, the area of this polygon is

$$A\_i=c\_i + \frac{x\_i + e\_i}{2} - 1.$$

Meanwhile, the octagon with \\$\mathcal{E}\\$ as vertices/perimeter has area 674. As such,

$$\sum\_i c\_i + \sum\_i\Big( \frac{ x\_i + e\_i }{2} - 1 \Big) = \sum\_i A\_i \leq 674.$$

Furthermore, it is conjectured (!) that

$$\frac{ x\_i + e\_i }{2} - 1 \geq \frac{1}{2}\Big\lceil \sqrt{8c\_i-4}\Big\rceil.$$

**Optimization:** In our notation, we seek to minimize \\$|\mathcal{X}|+\max\_i c\_i\\$. It is convenient to write

$$|\mathcal{X}| = 625 - \sum\_i c\_i.$$

We may relax our optimization to only consider the above constraints:

$$\text{minimize} \quad 625 - \sum\_i c\_i + \max\_i c\_i$$ $$\text{subject to} \quad \sum\_i e\_i \leq 100, \quad \sum\_i c\_i + \sum\_i\Big( \frac{ x\_i + e\_i }{2} - 1 \Big) \leq 674, $$ $$\frac{ x\_i + e\_i }{2} - 1 \geq \frac{1}{2}\Big\lceil \sqrt{8c\_i-4}\Big\rceil, \quad x,c,e \geq 0.$$

The square root makes this optimization a pain, so we further relax to a sequence of linear programs. To accomplish this, we take

$$X\_k := \sum\_{i:c\_i=k} x\_i, \quad E\_k := \sum\_{i:c\_i=k} e\_i, \quad z\_k := |\\{i:c\_i = k\\}|, \quad C := \max\_i c\_i.$$

Then for each \\$C\in\\{1,\ldots,133\\}\\$, we solve the linear program

$$\text{minimize} \quad 625 - \sum\_k kz\_k + C$$ $$\text{subject to} \quad \sum\_k E\_k \leq 100, \quad \sum\_k kz\_k + \sum\_k\Big( \frac{ X\_k + E\_k }{2} - z\_k \Big) \leq 674, $$ $$\frac{ X\_k + E\_k }{2} - z\_k \geq \frac{1}{2}\Big\lceil \sqrt{8k-4}\Big\rceil\cdot z\_k, \quad X,E,z \geq 0.$$

Indeed, we only need to consider \\$C\leq 133\\$ thanks to the best known solution. Here's an implementation in MATLAB using CVX:

```
vals=[];
for C=1:133;
    [C min(vals)]
    w = ceil(sqrt(8*(1:C)-4))/2;
    cvx_begin quiet
        variable X(C)
        variable E(C)
        variable z(C)
        minimize( 625 - (1:C)*z + C )
        subject to
            sum(E) <= 100
            (1:C)*z + sum( (X+E)/2-z ) <= 674
            for ii=1:C
                (X(ii)+E(ii))/2-z(ii) >= w(ii)*z(ii)
            end
            X >= 0
            E >= 0
            z >= 0
        cvx_end
    vals(end+1)=cvx_optval;
end

```

The minimum value of 113.32 occurs when \\$C=41\\$. (Curiously, this is the size of the components in the best known solution.) Here's a plot of how the minimum varies with \\$C\\$:

# Answer
> 6 votes
## Score 80 + 61 = 141

```
........X...........X....
.......X.............X...
........X...........X....
.X.......X.........X.....
X.X.......X.......X......
...X.......X.....X.......
....X.......X...X........
.....X.....X.X.X.......X.
......X...X...X.......X.X
.......X.X.....X.....X...
........X.......X...X....
.......X.........X.X.....
......X...........X......
.....X.X.........X.......
....X...X.......X........
...X.....X.....X.X.......
X.X.......X...X...X......
.X.......X.X.X.....X.....
........X...X.......X....
.......X.....X.......X...
......X.......X.......X.X
.....X.........X.......X.
....X...........X........
...X.............X.......
....X...........X........

```

Found with the help of this program which tells you the number of `X`s and the size of each area of `.`s.

## Previous score 89 + 54 = 143

```
....X...............X....
.....X.............X.....
......X...........X......
.......X.........X.......
........X...X...X........
.........XXX.XXX.........
........X.......X........
.......X.........X.......
XXXXXXX...........XXXXXXX
.......X.........X.......
.......X.........X.......
........X.......X........
.........XXXXXXX.........
........X.......X........
.......X.........X.......
.......X.........X.......
XXXXXXX...........XXXXXXX
.......X.........X.......
........X.......X........
.........XXX.XXX.........
........X...X...X........
.......X.........X.......
......X...........X......
.....X.............X.....
....X...............X....

```

# Answer
> 5 votes
# C++, score 147

Adding simulated annealing has changed the results *very significantly*. They are now extremely worrying.

The code:

```
//#define _GLIBCXX_DEBUG
#include <x86intrin.h>
#include <iostream>
#include <streambuf>
#include <bitset>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>
#include <random>
#include <set>
#include <list>
#include <map>
#include <unordered_map>
#include <deque>
#include <stack>
#include <queue>
#include <string>
#include <iomanip>
#include <unordered_set>
#include <thread>

std::mt19937_64 mt;
int N = 25;
std::vector<char> cuts(N*N);
std::vector<char> marks;
int dfs(int at)
{
    char x = at % N, y = at / N;
    marks[at] = true;
    int sz = 1;
    static const char ddx[4] {1, -1, 0, 0};
    static const char ddy[4] {0, 0, 1, -1};
    for(int d = 0; d < 4; d++)
    {
        int dx = ddx[d], dy = ddy[d];
        int nx = x + dx, ny = y + dy;
        if(nx < 0 || ny < 0 || ny >= N || nx >= N) continue;
        if(marks[ny * N + nx]) continue;
        sz += dfs(ny * N + nx);
    }
    return sz;
}
bool connected(int at)
{
    char x = at % N, y = at / N;
    static const char ddx[4] {1, -1, 0, 0};
    static const char ddy[4] {0, 0, 1, -1};
    for(int d = 0; d < 4; d++)
    {
        int dx = ddx[d], dy = ddy[d];
        int nx = x + dx, ny = y + dy;
        if(nx < 0 || ny < 0 || ny >= N || nx >= N) continue;
        if(cuts[ny * N + nx]) return true;
    }
    return false;
}
int score()
{
    marks = cuts; //true -> pretend it's already cut
    int ans1 = 0, ans2 = 0;
    for(char el : cuts) ans2 += el == true;
    for(int i = 0; i < N*N; i++)
    {
        if(marks[i]) continue;
        ans1 = std::max(ans1, dfs(i));
    }
    return ans1 + ans2;
}
int main()//int64_t argc, char*argv[])
{
    int gs = 8;
    for(int y = 0; y < N; y++)
    for(int x = 0; x < N; x += gs)
        cuts[y*N+x] ^= true;
    for(int y = 0; y < N; y += gs)
    for(int x = 0; x < N; x++)
        cuts[y*N+x] ^= true;
    for(int x = 0; x < N; x++)
        cuts[x] ^= true,
        cuts[N*x] ^= true,
        cuts[N*(N-1)+x] ^= true,
        cuts[N*x+N-1] ^= true;
    //do random changes, minimizing score
    printf("%d\n", score());
    int its = 1e6;
    float temp = 1;
    for(int y = 0; y < N; y++)
    {
        for(int x = 0; x < N; x++) printf("%c", cuts[y*N+x] ? '#' : '.');
        printf("\n");
    }
    while(its --> 0)
    {
        if(its % 1000 == 0) printf("i: %d\n", its);
        temp -= 2e-6;
        int i = 0;
        do { i = mt() % (N*N); }
        while(!cuts[i] && !connected(i));
        //fun fact: do..while loops don't actually need braces
        int sb = score();
        cuts[i] ^= 1;
        int sa = score();
        int delta = sb - sa; //positive -> good
        //printf("%d\n", delta);
        if(delta <= 0 && (temp <= 0 || ldexpf(std::exp(delta / temp), 60) < mt()))
            cuts[i] ^= 1;
        else printf("%d\n", sa);
    }
    for(int y = 0; y < N; y++)
    {
        for(int x = 0; x < N; x++) printf("%c", cuts[y*N+x] ? '#' : '.');
        printf("\n");
    }
}

```

The output, with the starting condition being a 3x3 grid:

<pre><code>........#........#.......
.........#......#........
........#.......#........
.......#.......#.........
........#.......#........
........#........#.......
.......#........#........
.#....#.#......#.#...#.##
#.#.##...#...##...#.#.#..
...#......#.#....#.#.....
...........#.....#.......
..........#......#.......
.........#.......#.......
#......##........#.......
.#....#.......###........
..##.#.......#..#........
....#......##....#....#.#
.....#....#......#...#.#.
......#.##........###....
.......#.........#.......
.......#........#........
........#......#.........
.......#......#..........
.......#......#..........
.......#.....#...........
```
</code></pre>

# Answer
> 4 votes
# Score: ~~158 145~~ 141

*-4 thanks to @LevelRiverSt !*

```
.....X.............X.....
.....X.............X.....
......X...........X......
.......X.........X.......
........X.......X........
XX.......X.....X.......XX
..X.......X.X.X.......X..
...X.......X.X.......X...
....X.....X...X.....X....
.....X...X.....X...X.....
......X.X.......X.X......
.......X.........X.......
......X...........X......
.......X.........X.......
......X.X.......X.X......
.....X...X.....X...X.....
....X.....X...X.....X....
...X.......X.X.......X...
..X.......X.X.X.......X..
XX.......X.....X.......XX
........X.......X........
.......X.........X.......
......X...........X......
.....X.............X.....
.....X.............X.....

```

Try it online!

**Number of X**: 80
**Largest component**: 61

Divide the grid into 9 rougly equal areas of size ~60.

# Answer
> 3 votes
# 92 + 45 = 137

```
......X.........X........
.......X........X........
........X........X.......
.......X.X.......X.......
......X..X......X.X......
.....X....X....X...X.....
....X......X..X.....X...X
X..X.......X.X.......X.X.
.XX.........X.........X..
...X.......X.X.......X...
....X.....X...X.....X....
.....X...X.....X...X.....
......X.X.....X.X.X......
.......X.....X...X.......
......X.....X.....X......
.....X......X......X.....
....X......X........X....
....X.....X.X........XXX.
XXXX.X...X...X......X...X
......X.X.....X....X.....
.......X.......X..X......
.......X........XX.......
........X.......X........
........X.......X........
........X.......X........

```

Try it online!

I started with a program, then I took the best output and hand-modified it to get this. Next I'm going to try restricting the program to only place Xs on one color of squares - that seems like it might work better. The program is written in rust. The key idea was to seed the map with a Vornoi diagram before running a simplified simulating annealing:

```
use rand::prelude::*;

use std::collections::{HashMap, HashSet};

fn make_neighbors(point: (usize, usize), size: usize) -> Vec<(usize, usize)> {
    let (r, c) = point;
    let mut neighbors = vec![];
    if r > 0 {
        neighbors.push((r - 1, c));
    }
    if c > 0 {
        neighbors.push((r, c - 1));
    }
    if r < size - 1 {
        neighbors.push((r + 1, c));
    }
    if c < size - 1 {
        neighbors.push((r, c + 1));
    }
    neighbors
}

fn value_board(board: &Vec<Vec<bool>>) -> usize {
    let size = board.len();
    let mut color_counts = vec![];
    let mut removed_count = 0;
    let mut seen = HashSet::new();
    for r in 0..size {
        for c in 0..size {
            if board[r][c] {
                removed_count += 1;
            } else {
                let mut color_count = 0;
                let mut flood_stack = vec![(r, c)];
                while !flood_stack.is_empty() {
                    let point = flood_stack.pop().unwrap();
                    if !board[point.0][point.1] &&!seen.contains(&point) {
                        seen.insert(point);
                        color_count += 1;
                        let neighbors = make_neighbors(point, size);
                        flood_stack.extend(neighbors);
                    }
                }
                color_counts.push(color_count);
            }
        }
    }
    let max_color_count = color_counts.into_iter().max().unwrap_or(0);
    removed_count + max_color_count
}

// TODO: make removed, neighbor_removed into VecSets.
fn simulated_annealing(input_board: &Vec<Vec<bool>>, max_steps: usize) -> Vec<Vec<bool>> {
    let size = input_board.len();
    let mut coloring: HashMap<(usize, usize), usize> = HashMap::new();
    let mut max_color = 0;
    let mut color_counts = vec![];
    let mut removed: Vec<(usize, usize)> = vec![];
    let mut neighbor_removed: Vec<(usize, usize)> = vec![];
    let mut board = input_board.clone();
    for r in 0..size {
        for c in 0..size {
            if board[r][c] {
                removed.push((r, c));
                let neighbors = make_neighbors((r, c), size);
                for point in neighbors {
                    if !board[point.0][point.1] && !neighbor_removed.contains(&point) {
                        neighbor_removed.push(point);
                    }
                }
            } else {
                if !coloring.contains_key(&(r, c)) {
                    let color = max_color;
                    max_color += 1;
                    color_counts.push(0);
                    let mut flood_stack = vec![(r, c)];
                    while !flood_stack.is_empty() {
                        let point = flood_stack.pop().unwrap();
                        if !board[point.0][point.1] && !coloring.contains_key(&point) {
                            coloring.insert(point, color);
                            color_counts[color] += 1;
                            let neighbors = make_neighbors(point, size);
                            flood_stack.extend(neighbors);
                        }
                    }
                }
            }
        }
    }
    let mut rng = thread_rng();
    for step in 0..max_steps {
        //dbg!(&removed, &neighbor_removed, &coloring, &board);
        assert_eq!(removed.len() + coloring.len(), size.pow(2));
        if rng.gen::<f64>() < 0.5  && !removed.is_empty() {
            let index = rng.gen_range(0, removed.len());
            let &(r, c) = &removed[index];
            assert!(removed.contains(&(r, c)));
            assert!(!neighbor_removed.contains(&(r, c)));
            assert!(!coloring.contains_key(&(r, c)));
            assert!(board[r][c]);
            let neighbors = make_neighbors((r, c), size);
            let neighbor_colors: HashSet<usize> = neighbors
                .iter()
                .filter_map(|n| coloring.get(n))
                .cloned()
                .collect();
            // Remove if only 1 color.
            // This will always be a neutral or improving step
            // Never remove otherwise
            if neighbor_colors.len() <= 1 {
                board[r][c] = false;
                removed.swap_remove(index);
                let neighbors = make_neighbors((r, c), size);
                for neighbor in neighbors {
                    if board[neighbor.0][neighbor.1] {
                        neighbor_removed.push((r, c));
                        break;
                    }
                }
                let new_color = if neighbor_colors.len() == 1 {
                    neighbor_colors.into_iter().next().unwrap()
                } else {
                    let new_color = max_color;
                    max_color += 1;
                    color_counts.push(0);
                    new_color
                };
                coloring.insert((r, c), new_color);
                color_counts[new_color] += 1;
            }
        } else if !neighbor_removed.is_empty() {
            let index = rng.gen_range(0, neighbor_removed.len());
            let (r, c) = neighbor_removed[index];
            let my_color = *coloring.get(&(r, c)).unwrap();
            let is_max_color = color_counts.iter().enumerate().all(|(i, &color_count)| {
                i == my_color || color_count < color_counts[my_color]
            });
            // Flip if either is a max color, in which case it's free,
            // or temp is high enough and get lucky.
            let take_action = is_max_color || {
                step < max_steps / 2 && rng.gen::<f64>() < 0.1
            };
            if take_action {
                board[r][c] = true;
                neighbor_removed.swap_remove(index);
                removed.push((r, c));
                coloring.remove(&(r, c));
                color_counts[my_color] -= 1;
                let neighbors = make_neighbors((r, c), size);
                for neighbor in neighbors {
                    if !board[neighbor.0][neighbor.1] && !neighbor_removed.contains(&neighbor) {
                        neighbor_removed.push(neighbor)
                    }
                }
            }
        }
    }
    board
}
// Given starting points and a board size, make a vornoi diagram
fn vornoi(points: &Vec<(usize, usize)>, size: usize) -> Vec<Vec<bool>> {
    let mut time_board: Vec<Vec<Option<usize>>> = vec![vec![None; size]; size];
    let mut board = vec![vec![false; size]; size];
    for (i, point) in points.iter().enumerate() {
        time_board[point.0][point.1] = Some(i);
    }
    for _ in 0..size {
        let mut new_board = time_board.clone();
        for r in 0..size {
            for c in 0..size {
                if let Some(i) = time_board[r][c] {
                    let neighbors = make_neighbors((r, c), size);
                    for (nr, nc) in neighbors {
                        if let Some(j) = new_board[nr][nc] {
                            if i != j {
                                board[r][c] = true;
                            }
                        } else {
                            new_board[nr][nc] = Some(i);
                        }
                    }
                }
            }
        }
        time_board = new_board
    }
    board
}

fn random_vornoi(num_points: usize, size: usize) -> Vec<Vec<bool>> {
    let mut points = vec![];
    let mut rng = thread_rng();
    while points.len() < num_points {
        let r = rng.gen_range(0, size);
        let c = rng.gen_range(0, size);
        if !points.contains(&(r, c)) {
            points.push((r, c))
        }
    }
    vornoi(&points, size)
}
fn print_board(board: &Vec<Vec<bool>>) {
    let string_board = board
        .iter()
        .map(|row| {
            row.iter()
                .map(|&c| if c { 'X' } else { '.' })
                .collect::<String>()
        })
        .collect::<Vec<String>>()
        .join("\n");
    println!("{}", string_board);
}
fn main() {
    let size: usize = 25;
    let reps = 100;
    let steps = 30000000;
    let mut best_points = 0;
    let mut best_board = None;
    let mut best_value = size.pow(2);
    for num_points in 8..17 {
        let mut best_board_points = None;
        let mut best_value_points = size.pow(2);
        for _ in 0..reps {
            let board = random_vornoi(num_points, size);
            let better_board = simulated_annealing(&board, steps);
            let value = value_board(&better_board);
            if value < best_value {
                best_board = Some(better_board.clone());
                best_value = value;
                best_points = num_points;
            }
            if value < best_value_points {
                best_board_points = Some(better_board);
                best_value_points = value;
            }
        }
        println!("{} {}", num_points, best_value_points);
        print_board(&best_board_points.unwrap());
        println!();
    }
    println!("{} {}", best_points, best_value);
    print_board(&best_board.unwrap());
    println!();
}

```

To run the program, put the above file in `src/main.rs` and put `rand = "*"` in your Cargo.toml.

# Answer
> 1 votes
# Score: ~~314~~ 313

-1 thanks to @Level River St

```
.X.X.X.X.X.X.X.X.X.X.X.X.
X.X.X.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X.X.X.
X.X.X.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X.X.X.
X.X.X.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X.X.X.
X.X.X.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X.X.X.
X.X.X.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X.X.X.
X.X.X.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X.X.X.
X.X.X.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X.X.X.
X.X.X.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X.X.X.
X.X.X.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X.X.X.
X.X.X.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X.X.X.
X.X.X.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X.X.X.
X.X.X.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X.X.X.

```

The largest connected component is of size 1.

Verify the score here: Try it online!

---
Tags: code-challenge, graph-theory
---