# Question
Title: Determine Beckett Grading Service (BGS) Final Grade
## Introduction:

Beckett Grading Service (aka BGS), is a company which encapusulates and grades Trading Card Game (TCG) cards (i.e. sport cards, Magic The Gathering, Pokémon, Yu-Gi-Oh, etc. etc.). The TCG cards that come in for grading will be checked on four categories (which we will later refer to as subgrades): centering, corners, edges, and surface. These subgrades will be in the range \\$\[1, 10\]\\$ in increments of \\$0.5\\$. Based on these four subgrades, the graded card is also given a final grade (in the same range). This final grade isn't just an average however. To quote the BGS FAQ page (minor note when reading: the *grading level/point* they're talking about is a step of 0.5):

> **Here is how we do it!**
> The overall numerical grade is not a simple average of the four report card grades. Beckett Grading Services uses an algorithm which determines the final grade using the 4 sub grades on the front label of the card holder. The lowest overall grade is the first category to observe because it is the most obvious defect, and the lowest grade is the most heavily weighted in determining the overall grade.
>
> **Example :**
> Centering = 9.5; Corners = 9.5; Edges = 9; Surface = 8
> Final grade = 8.5
>
> The reason that this card received an 8.5 is that even though the Surface grade was an 8 (the lowest grade overall), the 9.5 grades on Centering and Corners were strong enough to bring it up a full point to reach the 8.5 level.
>
> **Another example :**
> Centering = 9.5; Corners = 9.5; Edges = 8.5; Surface = 9
> Final grade = 9
>
> Upon first glance, it may appear that this card should've received a grade different than a 9. The most this card could receive was .5 (or one-half grade) above the lowest sub-grade. The Edges were the lowest in this case, hence, the card received the overall 9 grade. Even though Centering and Corners received grades of 9.5, a key point to remember is that the minimum requirement to receive a grade of Gem Mint is to have at least three grades of 9.5 and the fourth to be no less than a 9.
>
> Also, please note that the final grade rarely, if ever, exceeds two levels above the lowest of the four characteristic grades. For example, if a card has characteristic grades of Centering 10, Corners 6, Edges 10 and Surface 10, the final grade will be a "7" (of which is exactly two grading levels above the lowest characteristic grade).

Although the algorithm they use to determine the final grade has never been revealed, someone was able to come up with a set of rules as algorithm for determining the final grade based on the four subgrades by looking at as many example graded cards as possible (source):

In pseudo-code:

```
Sort subgrades in decreasing order

var fourth = fourth number in this order # so the lowest subgrade
var third = third number in this order   # so the second to last subgrade - could be equal
                                         #  to the lowest of course)
var first = first number in this order   # so the highest subgrade
var diff = third - fourth                # difference between these two lowest subgrades
var finalGrade                           # our final grade we're calculating

If diff == 0:
  finalGrade = fourth
Else:
  If fourth is Edges OR fourth is Surface:
    If diff < 1:
      finalGrade = fourth + 0.5
    Else:
      If (diff == 1 AND fourth + 1 >= 9.5)
         OR (first - fourth == 1.5 AND first != 10):
        finalGrade = fourth + 0.5
      Else:
        finalGrade = fourth + 1.0
  Else-if fourth is Centering:
    If diff < 2:
      finalGrade = fourth + 0.5
    Else-if diff < 4:
      finalGrade = fourth + 1.0
    Else:
      finalGrade = fourth + 1.5
  Else(-if fourth is Corners):
    If diff < 3:
      finalGrade = fourth + 0.5
    Else:
      finalGrade = fourth + 1

```

Some examples:

* 9.5 8.5 7.5 9.5 = 8.5: `fourth` number is Edges (7.5); `diff` is 1.0. So the final grade becomes `fourth + 1.0`.
* 10 10 10 8.5 = 9.5: `fourth` number is Surface (8.5); `diff` is 1.5. So the final grade becomes `fourth + 1.0` (with a different if-else path than the one above)
* 9.5 9.5 9 8 = 8.5: `fourth` number is Surface (8); `diff` is 1.0; `first` number is 9.5. So the final grade becomes `fourth + 0.5`.
* 5.5 8.5 9 7 = 6: `fourth` number is Centering (5.5); `diff` is 1.5. So the final grade is `fourth + 0.5`.
* 5 7 9 9.5 = 6: `fourth` number is Centering (5); `diff` is 2. So the final grade is `fourth + 1`.
* 4.5 9 9.5 9 = 6: `fourth` number is Centering (4); `diff` is 4.5. So the final grade is `fourth + 1.5`.
* 9 6.5 9 9.5 = 7: `fourth` is Corners (6.5); `diff` is 2.5. So the final grade is `fourth + 0.5`.

In summary: Corners is punished hardest, Centering next, Surface/Edges the least. How much the overall grade is better than the worst subgrade depends on which subgrade is the worst, and also depends on how much the other three subgrades are better than the worst subgrade, measured by `diff`.

Here an ungolfed reference implementation of the described algorithm in Java. (It can also be used to generate more random test cases; see the bottom section of the output.)

## Challenge:

Given the four subgrades as input, output the final grade based on the algorithm above.

## Challenge rules:

* Input may be in any reasonable format. Can be four separated inputs. A sorted list. Etc. Make sure to state the order of the subgrades centering, corners, edges, surface you've used. Inputs can be as decimal numbers, strings, or other reasonable input-types.
    + If your language doesn't have a numeric type that allows decimal values, or if you choose to, you are allowed to take all inputs multiplied by 10 as integers (as long as it's consistent). I.e. instead of `4.5 8 9.5 6.5` you could also take the input as `45 80 95 65`. In which case the output is of course similar. *Make sure to mention in your answer if you're using integers which are multiplied by 10!*
* Output may be returned by a function in any reasonable type, output to STDOUT/STDERR/Exit Code, etc.
* Of course you don't have to follow the algorithm exactly as described above. As long as it gives the correct result for any of the 130321 possible test cases, it's fine to implement it in any way you'd like. If you think hard-coding all possible test cases is shorter in your language of choice, by all means go for it.

## General rules:

* This is , so shortest answer in bytes wins.
Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
* Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
* Default Loopholes are forbidden.
* If possible, please add a link with a test for your code (i.e. TIO).
* Also, adding an explanation for your answer is highly recommended.

## Test cases:

```
Centering  Corners  Edges  Surface  =  Final grade
10         10       10     10       =  10
10         10       10     9.5      =  10
10         10       9.5    10       =  10
10         9.5      10     10       =  10
9.5        10       10     10       =  10
10         9.5      9.5    9        =  9.5
8.5        9        10     9.5      =  9
8          8        8.5    8.5      =  8
9.5        8.5      9.5    9.5      =  9
5.5        7.5      7.5    7        =  6
9.5        8.5      8.5    9        =  8.5
8          8.5      9      9        =  8.5
9.5        4.5      4.5    2.5      =  3.5
9.5        6        6.5    6        =  6
9.5        7        7      8        =  7
9.5        9.5      9.5    8.5      =  9
7.5        8.5      9      8        =  8
9          8        7      8.5      =  8
10         9.5      9.5    8        =  9
10         9        9.5    9        =  9
10         8        9      9        =  8.5
9.5        8.5      7.5    9.5      =  8.5
9.5        8.5      8.5    6.5      =  7.5
10         10       10     8.5      =  9.5
9.5        9.5      9      8        =  8.5
5.5        8.5      9      7        =  6
5          7        9      9.5      =  6
4.5        9        9.5    9        =  6
9          6.5      9      9.5      =  7
1          1        1      1        =  1
1          10       10     10       =  2.5
10         1        10     10       =  2

```

# Answer
> 4 votes
# Charcoal, ~~73~~ 71 bytes

```
≦⊗θ≔⌊θη≔⁻⌊Φθ⁻κ⌕θηηζＩ⊘⁺η∧ζ⎇⌕θη∨⎇⊖⌕θη∨›²ζ∨∧⁼²ζ‹¹⁶η∧⁼³⁻⌈θη›²⁰⌈θ›⁶ζ²⊕⌊⟦²÷ζ⁴

```

Try it online! Link is to verbose version of code. Takes input as an array of 4 values \[Centring, Corners, Edges, Surface\]. Explanation:

```
≦⊗θ

```

Double all the values so we're dealing in grade points rather than grades.

```
≔⌊θη

```

Find the worst grade.

```
≔⁻⌊Φθ⁻κ⌕θηηζ

```

Find the worst of the other grades, i.e. the second worst, and subtract the worst grade.

```
Ｉ⊘

```

Halve the final value and cast to string for display.

```
⁺η

```

Add the bonus to the minimum grade.

```
∧ζ

```

No bonus if the worst two grades are the same.

```
⎇⌕θη

```

Check whether the worst grade was for Centring.

```
∨⎇⊖⌕θη∨›²ζ∨∧⁼²ζ‹¹⁶η∧⁼³⁻⌈θη›²⁰⌈θ›⁶ζ²

```

If not then check whether only one bonus point should be awarded otherwise award two bonus points. (If the worst grade was for Corners then add a bonus point if the difference was less than 6 grade points or 2 if it was 6 or more. The calculation for Edges and Surface is longer but still only adds one or two bonus points.)

```
⊕⌊⟦²÷ζ⁴

```

If the worst grade was for Centring then add a bonus point for every 4 grade points between the worst two grades up to 2, plus a further bonus point.

# Answer
> 4 votes
# Perl 5 (`-ap`), ~~157~~ 154 bytes

minor improvements `!$d?0:...` inverted to `$d?...:0`, `>=9.5` changed to `>9.4` and `!=10` to `<10`

```
($w,$x,$y,$z)=sort{$b<=>$a}@F;$d=$y-$z;$_=$z+=$d?$z==$F[2]|$z==$F[3]?$d<1?.5:$d==1&$z+1>9.4|$w-$z==1.5&$w<10?.5:1:$z==$F[0]?$d<2?.5:$d<4?1:1.5:$d<3?.5:1:0

```

TIO

first answer was

```
($w,$x,$y,$z)=sort{$b<=>$a}@F;$d=$y-$z;$_=$z+=!$d?0:$z==$F[2]|$z==$F[3]?$d<1?.5:$d==1&$z+1>=9.5|$w-$z==1.5&$w!=10?.5:1:$z==$F[0]?$d<2?.5:$d<4?1:1.5:$d<3?.5:1

```

straight forward, ungolfed

```
!$d?0
:$z==$F[2]|$z==$F[3]?
    $d<1?.5
    :$d==1&$z+1>=9.5|$w-$z==1.5&$w!=10?.5
    :1
:$z==$F[0]?
    $d<2?.5
    :$d<4?1
    :1.5
:$d<3?.5
:1

```

TIO

# Answer
> 3 votes
# JavaScript (V8), ~~160 159 154~~ 151 bytes

```
s=>{[C,O,E,S]=[...s];[a,b,c,d]=s.sort((a,b)=>b-a);e=c-d;return(e?d==E|d==S?e<1?.5:(e==1&d>8.4)|(a-d==1.5&a<10)?.5:1:d-C?e<3?.5:1:e<2?.5:e<4?1:1.5:0)+d}

```

Try it online!

## A bit ungolfed:

```
function calculateScore(score) {
  [center,corner,edge,surface] = [...score]; // makes a copy because sort is in-place
  [first,second,third,fourth] = score.sort((a,b)=>b-a); // standard sort is alphabetically, this will sort by value
  diff = third - fourth;
  return fourth + (// Every final score is fourth + something else
    diff != 0
      ? fourth == edge || fourth == surface
        ? diff < 1
          ? 0.5
          : (diff == 1 && fourth >= 8.5) || (first-fourth == 1.5 && a < 10)
            ? 0.5
            : 1
      : fourth != corner
        ? diff < 3
          ? 0.5
          : 1
        : diff < 2
          ? 0.5
          : diff < 4
            ? 1
            : 1.5
      : 0 // diff == 0
  );
}

```
* -1: `>=8.5` -\> `>8.4`
* -5 thanks to @Kevin Cruijssen
* -3 for ES6 copying with `[...s]`

# Answer
> 3 votes
# JavaScript (ES6),  ~~115 ... 105~~  102 bytes

Takes input as an array.

```
a=>([w,d,,b]=([C,c]=a).sort((a,b)=>a-b),(d-=w)?(w-C?w-c?d<1|(w>8?d:b-w-.5)==1:d<3:d<4?d<2:3)||2:0)/2+w

```

Try it online!

or compare all results with those of the ungolfed reference implementation

### Commented

```
a => (                      // a[] = [ centering, corners, edges, surface ]
  [ w,                      // w = worst grade (4th grade)
    d,                      // d = 3rd grade
    ,                       // the 2nd grade is ignored
    b                       // b = best grade (1st grade)
  ] =                       //
    ([C, c] = a)            // before sorting, save C = centering and c = corners
    .sort((a, b) => a - b), // sort the grades from lowest to highest
  (d -= w) ?                // d = 3rd grade - worst grade; if it's not 0:
    ( w - C ?               //   if the worst grade is not for centering:
        w - c ?             //     if the worst grade is not for corners:
          d < 1 |           //       yield 1 if d < 1 OR
          ( w > 8 ?         //       either
              d             //         d (if w > 8)
            :               //       or
              b - w - .5    //         b - w - 0.5 (if w <= 8)
          ) == 1            //       is equal to 1
        :                   //     else (worst grade = corners):
          d < 3             //       yield 1 if d < 3
      :                     //   else (worst grade = centering):
        d < 4 ?             //     if d < 4:
          d < 2             //       yield 1 if d < 2
        :                   //     else:
          3                 //       yield 3
    ) || 2                  //   if the above result is 0, yield 2 as the default value
  :                         // else (d = 0):
    0                       //   yield 0
) / 2 + w                   // half the above result and add it to w

```

# Answer
> 3 votes
# Python 3, 132 bytes

```
def f(a):c,C,*_=a;w,x,y,z=sorted(a);d=x-w;return(x>w)*[[2-(d<1or d==1<w-7or z-w==1.5>z-8.5),3-(d<2)-(d<4)][w==c],-~(d>=3)][w==C]/2+w

```

Try it online!

# Answer
> 1 votes
# C# (Visual C# Interactive Compiler), 164 bytes

```
(a,b,c,d)=>{int[]e={a,b,c,d};Array.Sort(e);int f=e[0],h=e[1]-f,i=e[3];return(h<1?0:f==c|f==d?h<9?5:h<11&f>84|i-f==15&i<96?5:10:f==a?h<20?5:h<40?10:15:h<30?5:10)+f;}

```

Try it online!

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


# Question
Title: Generate a random point outside a given rectangle within a map
# Introduction

Given this visualization of a playing field:

```
(0,0)
+----------------------+(map_width, 0)
|           A          |
|-----+-----------+----|
|  D  |     W     | B  |
|-----+-----------+----|
|           C          |
+----------------------+(map_width, map_height)
(0, map_height)

```

The entire map the game is played on is the rectangle with the corner coordinates (0,0) and (map\_width, map\_height). The points eligible for spawning enemies is the Union $$S = \bigcup (A, B, C, D) $$

# The Challenge

Write code that returns a random point(x, y) that is guaranteed to be inside S. Your code cannot introduce any additional bias, meaning that the probability of each coordinate is uniformly distributed given the assumption that your choice of generating randomness (e.g. function|library|dev/urandom) is unbiased.

Shortest solutions in bytes win!

# Input

You will be given a total of 6 positive integer input variables in order: `map_width, map_height, W_top_left_x, W_top_left_y, W_width, W_height`. You can assume that the (calculated) surface area of all regions(A,B,C,D,W) is each \>10, so there are no empty spaces/regions.

Example Input: `1000, 1000, 100, 100, 600, 400`

The input has to contain the 6 values described above but it can be passed as fewer numbers of arguments and in any order. For instance passing `(map_width, map_height)` as python tuple is allowed. What is not allowed of course are calculated parameters like the bottom right point of the W.

# Output

2 randomly generated integers (x, y) where

$$(0 \leq x \lt \text{map\_width}) \land (0 \leq y \lt \text{map\_height}) \land\[\neg (\text{W\_top\_left\_x} \leq x \lt \text{W\_top\_left\_x} + \text{view\_width})\lor \neg (\text{W\_top\_left\_y} \leq y \lt \text{W\_top\_left\_y} + \text{view\_height})\]$$

holds.

# Examples

```
Input                                    Output(valid random samples)

1000 1000 100 100 600 400                10 10
1000 1000 100 100 600 400                800 550
1000 1000 100 100 600 400                800 10
1000 1000 100 100 600 400                10 550

```

For details and limitations for input/output please refer to the default input/output rules

# Answer
# Python 2, ~~114~~ ~~106~~ ~~102~~ 101 bytes

```
lambda w,h,X,Y,W,H:choice([(i%w,i/w)for i in range(w*h)if(W>i%w-X>-1<i/w-Y<H)<1])
from random import*

```

Try it online!
> 7 votes

# Answer
# , ~~89~~ 73 bytes

```
function(w,h,K,D,`*`=sample){while(all((o<-c(0:w*1,0:h*1))<=K+D&o>K))0
o}

```

Try it online!

Takes input as `width,height,c(X,Y),c(W,H)`.

Samples from \\$\[0,w\]\times\[0,h\]\\$ uniformly until it finds a point outside the inner rectangle.
> 4 votes

# Answer
# 05AB1E, ~~23~~ ~~21~~ ~~20~~ ~~18~~ 17 bytes

```
L`â<ʒ²³+‹y²@«P≠}Ω

```

Input is in the format `[map_width, map_height], [W_top_left_x, W_top_left_y], [W_width, W_height]`.

Thanks to *@Grimy* for -1 byte, and also for making me realize I introduced a bug after my latest edit.

Try it online, output 10 possible outputs at the same time or verify all possible coordinates. (Minor note: I've decreased the example input by a factor 10, because the filter and random choice builtin arer pretty slow for big lists.)

**Explanation:**

The inputs `map_width, map_height, [W_top_left_x, W_top_left_y], [W_width, W_height]` are referred to as `[Wm, Hm], [x, y], [w, h]` below:

```
L          # Convert the values of the first (implicit) input to an inner list in
           # the range [1, n]: [[1,2,3,...,Wm],[1,2,3,....,Hm]]
 `         # Push both inner lists separated to the stack
  â        # Get the cartesian product of both lists, creating each possible pair
   <       # Decrease each pair by 1 to make it 0-based
           # (We now have: [[0,0],[0,1],[0,2],...,[Wm,Hm-2],[Wm,Hm-1],[Wm,Hm]])
    ʒ      # Filter this list of coordinates [Xr, Yr] by:
     ²³+   #  Add the next two inputs together: [x+w, y+h]
        ‹  #  Check for both that they're lower than the coordinate: [Xr<x+w, Yr<y+h]
     y     #  Push the coordinate again: [Xr, Yr]
      ²    #  Push the second input again: [x, y]
       @   #  Check for both that the coordinate is larger than or equal to this given
           #  input: [Xr>=x, Yr>=y] (the w,h in the input are ignored)
     «     #  Merge it with the checks we did earlier: [Xr<x+w, Yr<y+h, Xr>=x, Yr>=y]
      P≠   #  And check if any of the four is falsey (by taking the product and !=1,
           #  or alternatively `ß_`: minimum == 0)
    }Ω     # After the filter: pick a random coordinate
           # (which is output implicitly as result)

```
> 4 votes

# Answer
# PowerShell, ~~85~~ 73 bytes

-12 bytes thanks to mazzy

```
param($a,$b,$x,$y,$w,$h)$a,$b|%{0..--$x+($x+$w+2)..$_|random
$x,$w=$y,$h}

```

Try it online!

Nice simple answer which cobbles together an array made of the range of values for each dimension and then picks one randomly for `x` and `y`. Manages to reuse most of the code by first processing `x`, then overwriting `$x` with `$y` and running it again.
> 4 votes

# Answer
# C# (Visual C# Interactive Compiler), 110 bytes

```
(a,b,c,d,e,f)=>{int g=c,h=d;for(var z=new Random();g>=c&g<e+c|h>=d&h<f+d;h=z.Next(b))g=z.Next(a);return(g,h);}

```

Try it online!
> 3 votes

# Answer
# Julia, ~~76~~ ~~71~~ 67 bytes

```
f(w,h,a,b,c,d)=rand(setdiff((0:w-1)'.=>0:h-1,(a:a+c-1)'.=>b:b+d-1))

```

Try it online!
> 2 votes

# Answer
# Jelly, 11 bytes

```
p/’$€+2¦ḟ/X

```

Try it online!

A dyadic link that takes two arguments, `[map_width, map_height], [W_width, W_height]` and `W_left, W_top` and returns a randomly selected point meeting the requirements.

## Explanation

```
   $€       | For each of member of the left argument, do the following as a monad:
p/          | - Reduce using Cartesian product (will generate [1,1],[1,2],... up to the width and height of each of the rectangles)
  ’         | - Decrease by 1 (because we want zero-indexing)
     +2¦    | Add the right argument to the second element of the resulting list
        ḟ/  | Reduce by filtering members of the second list from the first
          X | Select a random element

```
> 2 votes

# Answer
# Wolfram Language (Mathematica), ~~84~~ ~~68~~ 60 bytes

```
RandomChoice[g=Join@@List~Array~##&;#~g~0~Complement~g@##2]&

```

Try it online!

Take inputs as `{map_width, map_height}, {W_width, W_height}, {W_top_left_x, W_top_left_y}`.
> 2 votes

# Answer
# Java (OpenJDK 8), 100 bytes

```
W->H->r->{int x=0,y=0;for(;r.contains(x+=W*Math.random(),y+=H*Math.random());x=y=0);return x+","+y;}

```

Try it online!

Uses `java.awt.Rectangle` as holder of some of the parameters. Naturally, those use `int` fields, and not `float` or `double`.
> 1 votes

# Answer
# Python 2, 100 bytes

Input should be in the form of `((map_width, W_top_left_x, W_width),(map_height, W_top_left_y, W_height))`

Output is given in the form: `[[x],[y]]`

```
lambda C:[c(s(r(i[0]))-s(r(i[1],i[1]+i[2])),1)for i in C]
from random import*;c=sample;r=range;s=set

```

Try it online!

Random outputs obtained from the example input:

```
[[72], [940]]
[[45], [591]]
[[59], [795]]
[[860], [856]]
[[830], [770]]
[[829], [790]]
[[995], [922]]
[[23], [943]]
[[761], [874]]
[[816], [923]]

```
> 1 votes

# Answer
# Charcoal, ~~55~~ 43 bytes

```
ＮθＮηＦＥ²Ｎ⊞υ⟦ιＮ⟧Ｉ‽ΦＥ×θη⟦﹪ιθ÷ιθ⟧⊙υ∨‹§ιμ§λ⁰¬‹§ιμΣλ

```

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

```
ＮθＮη

```

Input the map size. (If they were last, I could input the height inline for a 1-byte saving.)

```
ＦＥ²Ｎ⊞υ⟦ιＮ⟧

```

Input the inner rectangle. (If I could input in the order `left, width, top, height` then I could use `Ｆ²⊞υＥ²Ｎ` for a 3-byte saving.)

```
Ｅ×θη⟦﹪ιθ÷ιθ⟧

```

Generate a list of all co-ordinates in the field.

```
Φ...⊙υ∨‹§ιμ§λ⁰¬‹§ιμΣλ

```

Filter out entries where both co-ordinates lie inside the rectangle.

```
Ｉ‽...

```

Print a random element of those that are left.
> 0 votes

# Answer
# Perl 5 `-ap`, 84 bytes

```
sub c{($c=0|rand((pop)+($l=pop)-"@_"))<$l?$c:$c+"@_"-$l}say c@F[4,2,0];$_=c@F[5,3,1]

```

Try it online!
> 0 votes

# Answer
# , ~~54~~ ~~47~~ ~~45~~ 39 bytes

```
(0?@{[)^:((-1&{)~(<*/@,0<:[)2{[)^:_{~&1

```

Try it online!

Take input as a 3 x 2 grid like:

```
grid_height  grid_width
inner_top    inner_left
inner_height inner_width

```
* Pick a random point on the entire grid: `0?@{[`
* Shift it left and down by the upper-left point of the interior rectangle: `(-1&{)~`
* Return to step 1 if the chosen spot is within `(<*/@,0<:[)` the similarly shifted interior rectangle `2{[`. Otherwise return the original, unshifted random point.
* Seed the whole process with a point we know is invalid, namely the upper left point of the interior rectangle, defined by elements 2 and 3 of the input list: `{~&1`

# Another approach, 45 bytes

```
{.#:i.@{.(?@#{])@-.&,([:<@;&i./{:){1&{|.i.@{.

```

Try it online!

This one is conceptually simpler, and doesn't bother with looping. Instead, we construct a matrix of all the numbers 0 to (w x h), shift it by the inner starting point, grab just the points in the (0, 0) to (inner w, innner h) subgrid, remove them from the overall grid after flattening both, pick one at random from the remainder, and convert the integer back into a point using divmod `<.@% , |~`
> 0 votes

# Answer
# Scala, 172 bytes

Randomness? Gotcha.

```
(a:Int,b:Int,c:Int,d:Int,e:Int,f:Int)=>{var r=new scala.util.Random
var z=(0,0)
do{z=(r.nextInt(a),r.nextInt(b))}while((c to e+c contains z._1)|(d to e+d contains z._2))
z}

```

A fun implementation I could think of.
**How it works**: Generate a random pair in the map. If it is in the inner rectangle, try again.
Try it online!
> 0 votes

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


title: Bridge the Gaps

text:
# Question
Title: Bridge the Gaps
Given a black and white image with a white background and a set of black dots, paint a set of white pixels red, such that there is a path between each pair of black pixels.

### Details

* A path is a set of connected pixels (8-neighbourhood connectivity). Black pixels can be used as part of the paths. The goal is trying to minimize the set of red pixels under the above conditions, and outputting a corresponding image.
* You don't *have to* find the optimal solution.
* A trivial and at the same time worst solution is just painting all the white pixels red.
* Example (Pixels are enlarged for visibility):

## Details

* Given a pixel image (in any suitable format) return another image with the dots connected as specified above, as well as a integer indicating how many red pixel were used.
* The Score is the product of (1+the number of red pixels) for each of the 14 testcases.
* The goal is having the lowest score.

## Testcases

The 14 testcases are shown below. A python program to verify the connectedness of the outputs can be found here.

## Meta

Thanks to @Veskah, @Fatalize, @wizzwizz4 and @trichoplax for the various suggestions.

# Answer
> 8 votes
# Python, 2.62 * 10^40

This algorithm just floodfills (BFS) the plane starting from the black parts of the image, where for each new pixel we record what black part it was flooded from. As soon as we have two neighbouring pixels with different black parts as ancestors, we basically merge these two black parts by joining them through the ancestors of the two neighbours we just found. In theory this could be implemented in `O(#pixels)`, but to keep the amount of code at an acceptable level this implementation is slightly worse.

### Output

```
import numpy as np
from scipy import ndimage
import imageio
from collections import deque

# path to your image
for k in range(1, 15):
    fname=str(k).zfill(2) +'.png'
    print("processing ", fname)

    # load image
    img = imageio.imread("./images/"+fname, pilmode="RGB")
    print(img.shape)

    # determine non_white part
    white = np.logical_and(np.logical_and(img[:,:,0] == 255, img[:,:,1] == 255), img[:,:,2] == 255)
    non_white = np.logical_not(white)

    # find connected components of non-white part
    neighbourhood = np.ones((3,3))
    labeled, nr_objects = ndimage.label(non_white, neighbourhood)

    # print result
    print("number of separate objects is {}".format(nr_objects))

    # start flood filling algorithm
    ind = np.nonzero(labeled)
    front = deque(zip(ind[0],ind[1]))

    membership = np.copy(labeled)
    is_merge_point = np.zeros_like(labeled) > 0
    parent = np.zeros((2,) + labeled.shape) #find ancestor of each pixel
    is_seed = labeled > 0
    size_i, size_j = labeled.shape
    # flood from every seed
    while front: #while we have unexplored pixels
        point = front.popleft()
        # check neighbours:
        for (di,dj) in [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]:
            current = membership[point[0], point[1]]
            new_i, new_j = point[0]+di, point[1]+dj
            if 0 <= new_i < size_i and 0 <= new_j < size_j:
                value = membership[new_i, new_j]
                if value == 0:
                    membership[new_i, new_j] = current
                    front.append((new_i, new_j))
                    parent[:, new_i, new_j] = point
                elif value != current: #MERGE!
                    is_merge_point[point[0], point[1]] = True
                    is_merge_point[new_i, new_j] = True
                    membership[np.logical_or(membership == value, membership == current)] = min(value, current)

    # trace back from every merger
    ind = np.nonzero(is_merge_point)
    merge_points = deque(zip(ind[0].astype(np.int),ind[1].astype(np.int)))
    for point in merge_points:
        next_p = point
        while not is_seed[next_p[0], next_p[1]]:
            is_merge_point[next_p[0], next_p[1]] = True
            next_p = parent[:, next_p[0], next_p[1]].astype(np.int)

    # add red points:
    img_backup = np.copy(img)
    img[:,:,0][is_merge_point] = 255 * img_backup[:,:,0]
    img[:,:,1][is_merge_point] = 0   * img_backup[:,:,1]
    img[:,:,2][is_merge_point] = 0   * img_backup[:,:,2]

    #compute number of new points
    n_red_points = (img[:,:,0] != img[:,:,1]).sum()
    print("#red points:", n_red_points)

    # plot: each component should have separate color
    imageio.imwrite("./out_images/"+fname, np.array(img))

```

### Score

```
(1+183)*(1+142)*(1+244)*(1+42)*(1+1382)*(1+2)*(1+104)*(1+7936)*(1+26)*(1+38562)*(1+42956)*(1+6939)*(1+8882)*(1+9916)
= 26208700066468930789809050445560539404000
= 2.62 * 10^40

```

# Answer
> 7 votes
# C, score 2.397x10^38

Man this took way too long to do, most likely due to my choice of language. I got the algorithm working fairly early, but ran into a lot of problems with memory allocation (couldn't recursively free stuff due to stack overflows, leak sizes were huge).

Still! It beats the other entry on every test case, and ~~might even be optimal~~ gets pretty close or exactly optimal solutions a lot of the time.

Anyway, here's the code:

```
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <string.h>

#define WHITE 'W'
#define BLACK 'B'
#define RED   'R'

typedef struct image {
    int w, h;
    char* buf;
} image;

typedef struct point {
    int x, y;
    struct point *next;
    struct point *parent;
} point;

typedef struct shape {
    point* first_point;
    point* last_point;

    struct shape* next_shape;
} shape;

typedef struct storage {
    point* points;
    size_t points_size;
    size_t points_index;

    shape* shapes;
    size_t shapes_size;
    size_t shapes_index;
} storage;

char getpx(image* img, int x, int y) {
    if (0>x || x>=img->w || 0>y || y>=img->h) {
        return WHITE;
    } else {
        return img->buf[y*img->w+x];
    }
}

storage* create_storage(int w, int h) {
    storage* ps = (storage*)malloc(sizeof(storage));

    ps->points_size = 8*w*h;
    ps->points = (point*)calloc(ps->points_size, sizeof(point));
    ps->points_index = 0;

    ps->shapes_size = 2*w*h;
    ps->shapes = (shape*)calloc(ps->shapes_size, sizeof(shape));
    ps->shapes_index = 0;

    return ps;
}

void free_storage(storage* ps) {
    if (ps != NULL) {
        if (ps->points != NULL) {
            free(ps->points);
            ps->points = NULL;
        }
        if (ps->shapes != NULL) {
            free(ps->shapes);
            ps->shapes = NULL;
        }
        free(ps);
    }
}

point* alloc_point(storage* ps) {
    if (ps->points_index == ps->points_size) {
        printf("WHOAH THERE BUDDY SLOW DOWN\n");
        /*// double the size of the buffer
        point* new_buffer = (point*)malloc(ps->points_size*2*sizeof(point));
        // need to change all existing pointers to point to new buffer
        long long int pointer_offset = (long long int)new_buffer - (long long int)ps->points;
        for (size_t i=0; i<ps->points_index; i++) {
            new_buffer[i] = ps->points[i];
            if (new_buffer[i].next != NULL) {
                new_buffer[i].next += pointer_offset;
            }
            if (new_buffer[i].parent != NULL) {
                new_buffer[i].parent += pointer_offset;
            }
        }

        for(size_t i=0; i<ps->shapes_index; i++) {
            if (ps->shapes[i].first_point != NULL) {
                ps->shapes[i].first_point += pointer_offset;
            }
            if (ps->shapes[i].last_point != NULL) {
                ps->shapes[i].last_point += pointer_offset;
            }
        }

        free(ps->points);
        ps->points = new_buffer;
        ps->points_size = ps->points_size * 2;*/
    }
    point* out = &(ps->points[ps->points_index]);
    ps->points_index += 1;
    return out;
}

shape* alloc_shape(storage* ps) {
    /*if (ps->shapes_index == ps->shapes_size) {
        // double the size of the buffer
        shape* new_buffer = (shape*)malloc(ps->shapes_size*2*sizeof(shape));
        long long int pointer_offset = (long long int)new_buffer - (long long int)ps->shapes;
        for (size_t i=0; i<ps->shapes_index; i++) {
            new_buffer[i] = ps->shapes[i];
            if (new_buffer[i].next_shape != NULL) {
                new_buffer[i].next_shape += pointer_offset;
            }
        }
        free(ps->shapes);
        ps->shapes = new_buffer;
        ps->shapes_size = ps->shapes_size * 2;
    }*/
    shape* out = &(ps->shapes[ps->shapes_index]);
    ps->shapes_index += 1;
    return out;
}

shape floodfill_shape(image* img, storage* ps, int x, int y, char* buf) {
    // not using point allocator for exploration stack b/c that will overflow it

    point* stack = (point*)malloc(sizeof(point));
    stack->x = x;
    stack->y = y;
    stack->next = NULL;
    stack->parent = NULL;

    point* explored = NULL;
    point* first_explored;
    point* next_explored;

    while (stack != NULL) {
        int sx = stack->x;
        int sy = stack->y;
        point* prev_head = stack;
        stack = stack->next;
        free(prev_head);

        buf[sx+sy*img->w] = 1; // mark as explored

        // add point to shape
        next_explored = alloc_point(ps);
        next_explored->x = sx;
        next_explored->y = sy;
        next_explored->next = NULL;
        next_explored->parent = NULL;

        if (explored != NULL) {
            explored->next = next_explored;
        } else {
            first_explored = next_explored;
        }
        explored = next_explored;

        for (int dy=-1; dy<2; dy++) {
        for (int dx=-1; dx<2; dx++) {
            if (dy != 0 || dx != 0) {
                int nx = sx+dx;
                int ny = sy+dy;
                if (getpx(img, nx, ny) == WHITE || buf[nx+ny*img->w]) {
                    // skip adding point to fringe
                } else {
                    // push point to top of stack
                    point* new_point = (point*)malloc(sizeof(point));
                    new_point->x = nx;
                    new_point->y = ny;
                    new_point->next = stack;
                    new_point->parent = NULL;

                    stack = new_point;
                }
            }
        }
        }
    }

    /*if (getpx(img, x, y) == WHITE || buf[x+y*img->w]) {
        return (shape){NULL, NULL, NULL};
    } else {
        buf[x+y*img->w] = 1;

        shape e  = floodfill_shape(img, ps, x+1, y,   buf);
        shape ne = floodfill_shape(img, ps, x+1, y+1, buf);
        shape n  = floodfill_shape(img, ps, x,   y+1, buf);
        shape nw = floodfill_shape(img, ps, x-1, y+1, buf);
        shape w  = floodfill_shape(img, ps, x-1, y,   buf);
        shape sw = floodfill_shape(img, ps, x-1, y-1, buf);
        shape s  = floodfill_shape(img, ps, x,   y-1, buf);
        shape se = floodfill_shape(img, ps, x+1, y-1, buf);

        point *p = alloc_point(ps);
        p->x = x;
        p->y = y;
        p->next = NULL;
        p->parent = NULL;

        shape o = (shape){p, p, NULL};
        if (e.first_point != NULL) {
            o.last_point->next = e.first_point;
            o.last_point = e.last_point;
        }
        if (ne.first_point != NULL) {
            o.last_point->next = ne.first_point;
            o.last_point = ne.last_point;
        }
        if (n.first_point != NULL) {
            o.last_point->next = n.first_point;
            o.last_point = n.last_point;
        }
        if (nw.first_point != NULL) {
            o.last_point->next = nw.first_point;
            o.last_point = nw.last_point;
        }
        if (w.first_point != NULL) {
            o.last_point->next = w.first_point;
            o.last_point = w.last_point;
        }
        if (sw.first_point != NULL) {
            o.last_point->next = sw.first_point;
            o.last_point = sw.last_point;
        }
        if (s.first_point != NULL) {
            o.last_point->next = s.first_point;
            o.last_point = s.last_point;
        }
        if (se.first_point != NULL) {
            o.last_point->next = se.first_point;
            o.last_point = se.last_point;
        }

        return o;
    }*/

    shape out = {first_explored, explored, NULL};

    return out;
}

shape* create_shapes(image* img, storage* ps) {
    char* added_buffer = (char*)calloc(img->w*img->h, sizeof(char));
    shape* first_shape = NULL;
    shape* last_shape = NULL;
    int num_shapes = 0;
    for (int y=0; y<img->h; y++) {
        for (int x=0; x<img->w; x++) {
            if (getpx(img, x, y) != WHITE && !(added_buffer[x+y*img->w])) {
                shape* alloced_shape = alloc_shape(ps);
                *alloced_shape = floodfill_shape(img, ps, x, y, added_buffer);

                if (first_shape == NULL) {
                    first_shape = alloced_shape;
                    last_shape = alloced_shape;
                } else if (last_shape != NULL) {
                    last_shape->next_shape = alloced_shape;
                    last_shape = alloced_shape;
                }

                num_shapes++;
            }
        }
    }

    free(added_buffer);

    return first_shape;
}

void populate_buf(image* img, shape* s, char* buf) {
    point* p = s->first_point;

    while (p != NULL) {
        buf[p->x+p->y*img->w] = 1;
        p = p->next;
    }
}

bool expand_frontier(image* img, storage* ps, shape* prev_frontier, shape* next_frontier, char* buf) {
    point* p = prev_frontier->first_point;
    point* n = NULL;

    bool found = false;

    size_t starting_points_index = ps->points_index;

    while (p != NULL) {
        for (int dy=-1; dy<2; dy++) {
        for (int dx=-1; dx<2; dx++) {
            if (dy != 0 || dx != 0) {
                int nx = p->x+dx;
                int ny = p->y+dy;
                if ((0<=nx && nx<img->w && 0<=ny && ny<img->h) // in bounds
                        && !buf[nx+ny*img->w]) {               // not searched yet
                    buf[nx+ny*img->w] = 1;
                    if (getpx(img, nx, ny) != WHITE) {
                        // found a new shape!
                        ps->points_index = starting_points_index;
                        n = alloc_point(ps);
                        n->x = nx;
                        n->y = ny;
                        n->next = NULL;
                        n->parent = p;
                        found = true;
                        goto __expand_frontier_fullbreak;
                    } else {
                        // need to search more
                        point* f = alloc_point(ps);
                        f->x = nx;
                        f->y = ny;
                        f->next = n;
                        f->parent = p;
                        n = f;
                    }
                }
            }
        }}

        p = p->next;
    }
__expand_frontier_fullbreak:
    p = NULL;
    point* last_n = n;
    while (last_n->next != NULL) {
        last_n = last_n->next;
    }

    next_frontier->first_point = n;
    next_frontier->last_point = last_n;

    return found;
}

void color_from_frontier(image* img, point* frontier_point) {
    point* p = frontier_point->parent;

    while (p->parent != NULL) { // if everything else is right,
                                // a frontier point should come in a chain of at least 3
                                // (f point (B) -> point to color (W) -> point in shape (B) -> NULL)
        img->buf[p->x+p->y*img->w] = RED;
        p = p->parent;
    }
}

int main(int argc, char** argv) {
    if (argc < 3) {
        printf("Error: first argument must be filename to load, second argument filename to save to.\n");
        return 1;
    }

    char* fname = argv[1];
    FILE* fp = fopen(fname, "r");

    if (fp == NULL) {
        printf("Error opening file \"%s\"\n", fname);
        return 1;
    }

    int w, h;
    w = 0;
    h = 0;
    fscanf(fp, "%d %d\n", &w, &h);

    if (w==0 || h==0) {
        printf("Error: invalid width/height specified\n");
        return 1;
    }

    char* buf = (char*)malloc(sizeof(char)*w*h+1);
    fgets(buf, w*h+1, fp);
    fclose(fp);

    image img = (image){w, h, buf};

    int nshapes = 0;
    storage* ps = create_storage(w, h);

    while (nshapes != 1) {
        // main loop, do processing step until one shape left
        ps->points_index = 0;
        ps->shapes_index = 0;

        shape* head = create_shapes(&img, ps);
        nshapes = 0;
        shape* pt = head;
        while (pt != NULL) {
            pt = pt->next_shape;
            nshapes++;
        }
        if (nshapes % 1024 == 0) {
            printf("shapes left: %d\n", nshapes);
        }
        if (nshapes == 1) {
            goto __main_task_complete;
        }

        shape* frontier = alloc_shape(ps);
        // making a copy so we can safely free later
        point* p = head->first_point;
        point* ffp = NULL;
        point* flp = NULL;
        while (p != NULL) {
            if (ffp == NULL) {
                ffp = alloc_point(ps);
                ffp->x = p->x;
                ffp->y = p->y;
                ffp->next = NULL;
                ffp->parent = NULL;
                flp = ffp;
            } else {
                point* fnp = alloc_point(ps);
                fnp->x = p->x;
                fnp->y = p->y;
                fnp->next = NULL;
                fnp->parent = NULL;

                flp->next = fnp;
                flp = fnp;
            }

            p = p->next;
        }
        frontier->first_point = ffp;
        frontier->last_point = flp;
        frontier->next_shape = NULL;

        char* visited_buf = (char*)calloc(img.w*img.h+1, sizeof(char));
        populate_buf(&img, frontier, visited_buf);

        shape* new_frontier = alloc_shape(ps);
        new_frontier->first_point = NULL;
        new_frontier->last_point = NULL;
        new_frontier->next_shape = NULL;

        while (!expand_frontier(&img, ps, frontier, new_frontier, visited_buf)) {
            frontier->first_point = new_frontier->first_point;
            frontier->last_point = new_frontier->last_point;
            new_frontier->next_shape = frontier;
        }

        free(visited_buf);
        color_from_frontier(&img, new_frontier->first_point);
__main_task_complete:
        img = img;
    }

    free_storage(ps);

    char* outfname = argv[2];
    fp = fopen(outfname, "w");

    if (fp == NULL) {
        printf("Error opening file \"%s\"\n", outfname);
        return 1;
    }

    fprintf(fp, "%d %d\n", img.w, img.h);
    fprintf(fp, "%s", img.buf);

    free(img.buf);

    fclose(fp);

    return 0;
}

```

Tested on: Arch Linux, GCC 9.1.0, `-O3`

This code takes input/output in a custom file I call "cppm" (because it's like a condensed version of the classic PPM format). A python script to convert to/from it is below:

```
from PIL import Image

BLACK='B'
WHITE='W'
RED  ='R'

def image_to_cppm(infname, outfname):
    outfile = open(outfname, 'w')
    im = Image.open(infname)

    w, h = im.width, im.height
    outfile.write(f"{w} {h}\n")
    for y in range(h):
        for x in range(w):
            r, g, b, *_ = im.getpixel((x, y))
            if r==0 and g==0 and b==0:
                outfile.write(BLACK)
            elif g==0 and b==0:
                outfile.write(RED)
            else:
                outfile.write(WHITE)
    outfile.write("\n")
    outfile.close()
    im.close()

def cppm_to_image(infname, outfname):
    infile = open(infname, 'r')

    w, h = infile.readline().split(" ")
    w, h = int(w), int(h)

    im = Image.new('RGB', (w, h), color=(255, 255, 255))

    for y in range(h):
        for x in range(w):
            c = infile.read(1)
            if c==BLACK:
                im.putpixel((x,y), (0, 0, 0))
            elif c==RED:
                im.putpixel((x,y), (255, 0, 0))

    infile.close()
    im.save(outfname)
    im.close()

if __name__ == "__main__":
    import sys
    if len(sys.argv) < 3:
        print("Error: must provide 2 files to convert, first is from, second is to")

    infname = sys.argv[1]
    outfname = sys.argv[2]

    if not infname.endswith("cppm") and outfname.endswith("cppm"):
        image_to_cppm(infname, outfname)
    elif infname.endswith("cppm") and not outfname.endswith("cppm"):
        cppm_to_image(infname, outfname)
    else:
        print("didn't do anything, exactly one file must end with .cppm")

```

## Algorithm explanation

How this algorithm works is that it starts by finding all the connected shapes in the image, including red pixels. It then takes the first one and expands its frontier one pixel at a time until it encounters another shape. It then colors all the pixels from the touching to the original shape (using the linkedlist it made along the way to keep track). Finally, it repeats the process, finding all the new shapes created, until there is only one shape left.

## Image gallery

Testcase 1, 183 pixels  Testcase 2, 140 pixels  Testcase 3, 244 pixels  Testcase 4, 42 pixels  Testcase 5, 622 pixels  Testcase 6, 1 pixel  Testcase 7, 104 pixels  Testcase 8, 2286 pixels  Testcase 9, 22 pixels  Testcase 10, 31581 pixels  Testcase 11, 21421 pixels  Testcase 12, 5465 pixels  Testcase 13, 4679 pixels  Testcase 14, 7362 pixels

# Answer
> 5 votes
# Python 3: ~~1.7x10^42~~ 1.5x10^41

Using `Pillow`, `numpy` and `scipy`.

Images are assumed to be in an `images` folder located in the same directory as the script.

**Disclaimer**: It takes a long time to process all the images.

## Code

```
import sys
import os

from PIL import Image
import numpy as np
import scipy.ndimage

def obtain_groups(image, threshold, structuring_el):
    """
    Obtain isles of unconnected pixels via a threshold on the R channel
    """
    image_logical = (image[:, :, 1] < threshold).astype(np.int)
    return scipy.ndimage.measurements.label(image_logical, structure=structuring_el)

def swap_colors(image, original_color, new_color):
    """
    Swap all the pixels of a specific color by another color
    """
    r1, g1, b1 = original_color  # RGB value to be replaced
    r2, g2, b2 = new_color  # New RGB value
    red, green, blue = image[:, :, 0], image[:, :, 1], image[:, :, 2]
    mask = (red == r1) & (green == g1) & (blue == b1)
    image[:, :, :3][mask] = [r2, g2, b2]
    return image

def main(image_path=None):
    images = os.listdir("images")
    f = open("results.txt", "w")

    if image_path is not None:
        images = [image_path]

    for image_name in images:
        im = Image.open("images/"+image_name).convert("RGBA")
        image = np.array(im)

        image = swap_colors(image, (255, 255, 255), (255, 0, 0))

        # create structuring element to determine unconnected groups of pixels in image
        s = scipy.ndimage.morphology.generate_binary_structure(2, 2)

        for i in np.ndindex(image.shape[:2]):
            # skip black pixels
            if sum(image[i[0], i[1]]) == 255:
                continue
            image[i[0], i[1]] = [255, 255, 255, 255]
            # label the different groups, considering diagonal connections as valid
            groups, num_groups = obtain_groups(image, 255, s)
            if num_groups != 1:
                image[i[0], i[1]] = [255, 0, 0, 255]
            # Show percentage
            print((i[1] + i[0]*im.size[0])/(im.size[0]*im.size[1]))

        # Number of red pixels
        red_p = 0
        for i in np.ndindex(image.shape[:2]):
            j = (im.size[1] - i[0] - 1, im.size[0] - i[1] - 1)
            # skip black and white pixels
            if sum(image[j[0], j[1]]) == 255 or sum(image[j[0], j[1]]) == 255*4:
                continue
            image[j[0], j[1]] = [255, 255, 255, 255]
            # label the different groups, considering diagonal connections as valid
            groups, num_groups = obtain_groups(image, 255, s)
            if num_groups != 1:
                image[j[0], j[1]] = [255, 0, 0, 255]
            # Show percentage
            print((j[1] + j[0]*im.size[0])/(im.size[0]*im.size[1]))
            red_p += (sum(image[j[0], j[1]]) == 255*2)

        print(red_p)
        f.write("r_"+image_name+": "+str(red_p)+"\n")

        im = Image.fromarray(image)
        im.show()
        im.save("r_"+image_name)
    f.close()

if __name__ == "__main__":
    if len(sys.argv) == 2:
        main(sys.argv[1])
    else:
        main()

```

## Explanation

Trivial solution. We begin by changing the color of all the white pixels in an image to red. By doing this, it is guaranteed that all the elements (any isle of black pixels) are connected.

Then, we iterate over all the pixels in the image starting from the top left corner and moving right and down. For every red pixel we find we change its color to white. If after this change of color there is still only one element (an element being now any isle of black and red pixels), we leave the pixel white and move on to the next pixel. However, if after the color change from red to white the number of elements is bigger than one, we leave the pixel red and move on to the next pixel.

**Update**

As it can be seen (and expected) the connections obtained by only using this method show a regular pattern and in some cases, such as in the 6th and 11th images, there are unnecessary red pixels.

This extra red pixels can be easily removed by iterating again over the image and performing the same operations as explained above but from the bottom right corner to the top left corner. This second pass is much faster since the amount of red pixels that have to be checked.

## Results

The images which are modified after the second pass are listed twice to show the differences.

Number of red pixels: 18825

Number of red pixels: 334

Number of red pixels: 1352

Number of red pixels: 20214

Number of red pixels: 47268

Number of red pixels: ~~63~~ 27

Number of red pixels: 17889

Number of red pixels: 259

Number of red pixels: 6746

Number of red pixels: 586

Number of red pixels: ~~9~~ 1

Number of red pixels: 126

Number of red pixels: 212

Number of red pixels: 683

Score computation:

(1+6746) * (1+126) * (1+259) * (1+17889) * (1+334) * (1+586) * (1+18825) * (1+9) * (1+683) * (1+1352) * (1+20214) * (1+212) * (1+63) * (1+47268) = 1778700054505858720992088713763655500800000 ~ 1.7x10^42

Updated score computation after adding second pass:

(1+ 18825) * (1+ 1352) * (1+ 20214) * (1+ 47268) * (1+ 27) * (1+ 17889) * (1+ 6746) * (1+ 586) * (1+ 1) * (1+ 126) * (1+ 212) * (1+ 334) * (1+259) * (1+683) = 155636254769262638086807762454319856320000 ~ 1.5x10^41

---
Tags: code-challenge, graphical-output, path-finding, test-battery, algorithm
---


title: Composing fill in the blanks

text:
# Question
Title: Composing fill in the blanks
Let us say that we have a particular set of functions on strings. These functions are kind of like fill in the blanks or madlibs, except that they only take one input and use that to fill in all of their blanks. For example we might have a function that looks like

```
I went to the ____ store and bought ____ today.

```

If we applied this function to the string `cheese` the result would be:

```
I went to the cheese store and bought cheese today.

```

We can represent these functions as a non-empty list of strings, where the blanks are simply the gaps in between strings. For example our function above would be:

```
["I went to the ", " store and bought ", " today."]

```

With this representation there is only one representation for every function of this sort and only one function for each representation.

A really neat thing is that the set of such functions is closed under composition. That is to say composition of two of our functions is always another one of these functions. For example if I compose our function above with

```
["blue ", ""]

```

(the function that prepends `blue` to the input) We get the function:

```
["I went to the blue ", " store and bought blue ", " today."]

```

These can get a little more complex though. For example if we compose the first function with

```
["big ", " and ", ""]

```

The result is

```
["I went to the big ", " and ", " store and bought big ", "and", " today."]

```

## Task

Your task is to take two functions as described as non-empty lists of strings and output their composition as a non-empty list of strings.

For the purpose of this challenge a list can be any ordered container that permits duplicates and a string may be a native string type, a list of characters or a list of integers.

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

## Test cases

```
["","xy"] ["ab",""] -> ["ab","xy"]
["x","y","z"] ["a","b"] -> ["xa","bya","bz"]
["xy"] ["ab"] -> ["xy"]
["","",""] ["a",""] -> ["a","a",""]
["x",""] ["","",""] -> ["x","",""]
["x","y","z"] ["a","b","c"] -> ["xa","b","cya","b","cz"]
["x","x","x"] ["a"] -> ["xaxax"]
["w","x","y","z"] ["ab","cd","e"] -> ["wab","cd","exab","cd","eyab","cd","ez"]

```

# Answer
> 11 votes
# Jelly, 6 bytes

```
j0j@ṣ0

```

A dyadic Link accepting the *first* function representation on the *right* and the *second* function representation on the *left* which yields the resulting function representation. Each function representation is a list of lists of characters (Jelly has no other strings).

**Try it online!** (the full-program arguments are given in Python notation; strings become lists. The footer shows a Python representation of the Link's output.)

Here is a test-suite which reformats the Link's output like the inputs.

### How?

Takes advantage of Jelly's mixed type lists to allow the entire domain of representations (any list of lists of characters) by using the integer zero as a place-holder:

```
j0j@ṣ0 - Link: b, a        e.g.    b = [['a','b'],['c','d'],['e']]
       -                   ...and  a = [['w'],['x'],['y'],['z']]
                             (i.e. test-case ["w","x","y","z"] ["ab","cd","e"])
j0     - join b with zeros         ['a','b',0,'c','d',0,'e']
  j@   - join a with that          ['w','a','b',0,'c','d',0,'e','x','a','b',0,'c','d',0,'e','y','a','b',0,'c','d',0,'e','z']
    ṣ0 - split at zeros            [['w','a','b'],['c','d'],['e','x','a','b'],['c','d'],['e','y','a','b'],['c','d'],['e','z']
                             (i.e.: ["wab","cd","exab","cd","eyab","cd","ez"])

```

---

If we needed to deal with any of Jelly's mixed lists (including those of any depth or shape) we could use this eight byter: `j,©⁹jœṣ®` which uses the paired arguments as the place-holder.

# Answer
> 5 votes
# Python 3.8 (pre-release),  ~~60~~  58 bytes

```
lambda a,b:(v:='&'.join(a+b)+'$').join(b).join(a).split(v)

```

An unnamed function accepting two lists of strings, `a` and `b`, which returns a list of strings.

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

### How?

First forms a separator string, `v`, which cannot be found inside `a` or `b`. Then forms a string by joining up the strings in `b` with copies of `v`. Then forms a string by joining up the strings in `a` with copies of that. Finally splits that string at instances of `v` to give a list of strings.

While ensuring `v` is not in `a` or `b` we must also ensure that `v` wont make us split early in the case where all the strings in `a` and `b` are equal. To do so we form `v` by joining all the strings in both lists with instances of a string (here `'&'`) and add an extra, different character (here `'$'`). Note that doing either in isolation is not enough as all strings in the inputs could equal the chosen character.

# Answer
> 5 votes
# Haskell, 78 bytes

```
(a:b:r)#t@(x:s)|s>[]=(a++x):init s++((last s++b):r)#t|z<-a++x++b=(z:r)#t
x#_=x

```

Try it online!

# Answer
> 2 votes
# 05AB1E, ~~4~~ ~~15~~ ~~19~~ ~~9~~ 11 bytes

```
«TýR©ý¹sý®¡

```

Unlike the Jelly answer, 05AB1E's string `"0"`, integer `0`, and float `0.0` are all (somewhat) equal, so I can't split/join by an integer. This is why we had the +15 bytes as workarounds, although I've golfed it back to 9 bytes now. Thanks to *@JonathanAllan* for finding 2 bugs.

Try it online or verify all test cases.

**Explanation:**

```
«            # Merge the two (implicit) input-lists together
 Tý          # Then using a "10" delimiter join all strings together
   R         # Reverse this string
    ©        # Store this string in variable `®` (without popping)
     ý       # Use this string as delimiter to join the second (implicit) input-list
      ¹sý    # Then join the first input-list by this entire string
         ®¡  # And split it back on variable `®` so it's the expected list of strings
             # (after which this result is output implicitly)

```

# Answer
> 2 votes
# Japt, 8 bytes

Adapts Jonathan's approach.

```
qVqN²)qN

```

Try it

```
qVqN²)qN     :Implicit input of arrays U & V (N=[U,V])
q            :Join U with
 Vq          :  V joined with
   N²        :    Push 2 to N (modifying the original), which gets coerced to a string
             >     e.g., N=[["a","b"],["c","d"]] -> N=[["a","b"],["c","d"],2] -> "a,b,c,d,2"
     )       :End join
      qN     :Split on the modified N, which, again, gets coerced to a string
             > e.g., N=[["a","b"],["c","d"],2] -> "a,b,c,d,2"

```

# Answer
> 2 votes
# Wolfram Language (Mathematica), ~~62~~ 61 bytes

```
""<>#&/@Flatten[#~(R=Riffle)~I/.I->#2~R~I]~SequenceSplit~{I}&

```

Try it online!

-1 thanks to Roman

---

Though it's not a valid output, this returns a function that actually does the job.. (34 bytes)

```
(g=a""<>a~Riffle~#&)[#]@*g[#2]&

```

Try it online!

# Answer
> 1 votes
# , ~~44~~ ~~43~~ ~~42~~ 29 bytes

```
_<;._1@,(;@}:@,@,.(,_&,)&.>/)

```

Try it online!

*-13 bytes thanks to miles!*

This approach uses integers and is due to miles.

# original approach with strings

```
g=.[:}.@,,.
f=.(<@0<@;;._1@,];@g<"0@[)<@0<@g]

```

Try it online!

*Note: I've adjusted -3 off the TIO to account for `f=.`*

Uses Jonathan Allen's method, adapted for J.

This was surprisingly difficult to golf, since J doesn't have a built in "join" method, and I'd be curious to see if it can be improved significantly.

`g` is helper verb that gives us "join"

# Answer
> 1 votes
# Haskell, 62 bytes

```
[a]#(c:d)=(a++c):d
(a:b)#c=a:b#c
[a]%b=[a]
(a:b)%c=[a]#c#(b%c)

```

Try it online!

Here is my Haskell answer. It works on any type of list.

# Answer
> 0 votes
# Perl 5 (`-lp`), 20 bytes

As @JonathanAllan commented, this is a full-program using, for IO, a tab as a list separator and a newline to separate the two lists.

```
chop($n=<>);s/  /$n/g

```

TIO

the tab and newline were chosen because more convenient to check test cases, otherwise could be changed to non-printable characters `\1` and `\2`.

(`-02l012p`)

```
chop($n=<>);s//$n/g

```

TIO

How it works,

* `-02` : to set input record separator to `\2`
* `-l` : to remove input separator from default argument `$_` and to add output record separator to default output
* `-012` : to set output record separator to `\012` (`\n`) so that output is easier to check
* `-p` : to print default argument
* `$n=<>;` : to read next record and to assign to `$n`
* `chop$n;` : to remove separator from `$n`
* `s/\x1/$n/g` : to replace all occurences of `\1` with `$n`

# Answer
> 0 votes
# JavaScript (Node.js), ~~85~~ 79 bytes

```
([a,...b],[c,...d])=>b.map(e=>r.push(r.pop(r.push(r.pop()+c,...d))+e),r=[a])&&r

```

Try it online!

# Answer
> 0 votes
# JavaScript, 37 bytes

Also adapts Jonathan's approach.

```
a=>b=>a.join(b.join(a+=b+0)).split(a)

```

Try it online

# Answer
> 0 votes
# JavaScript (ES6),  ~~62~~  59 bytes

*Saved 3 bytes thanks to @Shaggy*

This is a fixed version of Luis' answer (now deleted) to support all characters.

```
a=>b=>a.map(e=escape).join(b.map(e)).split`,`.map(unescape)

```

Try it online!

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


title: Radioactive Bit Checking

text:
# Question
Title: Radioactive Bit Checking
Note: This is the version of my previous challenge Pristine Bit Checking. This should be *much* more difficult than that one.

Write a program/function that takes two integers in the range \\$0\\$ to \\$255\\$ inclusive, and returns whether the binary forms of the numbers are exactly one bit different.

For example, \\$1\\$ and \\$0\\$ have binary forms `00000001` and `00000000`, which are one bit apart. Similarly, \\$152\\$ and \\$24\\$ are `010011000` and `000011000`, so they return true.

***However***, your code must be **radiation-hardened**, such that if any one bit in your program is flipped, it should still work correctly. For example, if your program was the single byte `a` (`01100001`), then all the 8 possible modified programs:

```
á ! A q i e c `

```

must still work correctly. Make sure you are modifying by *bytes* (e.g. the `á` up there is actually representing the byte \\$225\\$, not the actual two byte character `á`).

### Test cases:

With Truthy meaning they *are* different by one bit.

```
0,1     => Truthy
1,0     => Truthy
152,24  => Truthy
10,10   => Falsey
10,11   => Truthy
11,12   => Falsey
255,0   => Falsey

```

## Rules:

* Provide a testing framework that can verify that your program is properly radiation-hardened, since there will be a lot of possible programs (number of bytes\*8), or else a complete proof of validity.
    + *Please* make sure to double-check your program is valid before you post it.
* Output can to be either truthy/falsey (either way around is fine), or else as one distinct value for truthy and the rest as falsey

Here is a helper program that can be used to produce all the variations of an inputted program.

# Answer
> 7 votes
# HTML + JavaScript, 210 bytes

```
<script>[d,b]=location.search.match(/[\d]([\d]*)?/g);1/b/d&&document.write([i=b^d][i--&i]+'<!-'+'-')</script></script>0<script>[d,b]=location.search.match(/\d+/g);document.body.innerHTML=[i=b^d][i&i-1]</script>

```

Open page with search parameters `index.html?a=1&b=2`.

## Validation (Python + Selenium + Firefox)

```
# -*- coding: utf-8 -*-
from selenium import webdriver
import os
source = "<script>[d,b]=location.search.match(/[\d]([\d]*)?/g);1/b/d&&document.write([i=b^d][i--&i]+'<!-'+'-')</script></script>0<script>[d,b]=location.search.match(/\d+/g);document.body.innerHTML=[i=b^d][i&i-1]</script>"
filename = os.path.abspath("temp1.html")

browser = webdriver.Firefox()

def test(html, input_values, expected):
    with open(filename, "w", encoding="latin-1") as html_file:
        html_file.write(html)
    [a, b] = input_values
    browser.get("file:///" + filename + "?a=" + str(a) + "&b=" + str(b))
    text = browser.find_element_by_tag_name("body").text
    if text == "true" and expected == True: return True
    if text == "false" and expected == False: return True
    if text == "undefined" and expected == False: return True
    try:
        if int(text) != 0 and expected == True: return True
        if int(text) == 0 and expected == False: return True
    except: pass
    print(html, input_values, expected, text)

testcases = [
    [[1, 1], False],
    [[1, 2], False],
    [[1, 3], True],
]

fullTestcases = [
    [[0, 1], True],
    [[1, 0], True],
    [[152, 24], True],
    [[10, 10], False],
    [[10, 11], True],
    [[11, 12], False],
    [[255, 0], False],
]

def runAllTestcases(html, testcases):
    for testcase in testcases:
        test(html, *testcase)

runAllTestcases(source, fullTestcases)

for pos in range(len(source)):
    for flip in range(8):
        flip_char = chr(ord(source[pos]) ^ (2 ** flip))
        flip_source = source[0:pos] + flip_char + source[pos+1:]
        runAllTestcases(flip_source, testcases)
    print(pos, "/", len(source))

browser.quit()

```

Usage:

* make sure you have `python3` and `firefox` installed.
* save this python code to your locale.
* `pip install selenium`
* download firefox web driver and put it in the same folder of this python source.
* execute this validator and wait it finish.

## How

If the modification is on the first time of script. The script will throw some errors (syntax error, undefined variable, etc.). And the second time of script will run correctly and overwrite the output.

If the modification is not on the first time of script. The script output

## Learn some (useless) HTML knowledge

* document.write insert HTML to current position. You should not output unbalanced HTML in usual. When unbalanced HTML is printed. It inserted as is. And following HTML are re-parsed. You may even insert something like \<!-- to open a comment.
* When trying to parse \<head\>, if HTML parser got anything should not be existed here, the \<head\> tag is closed immediately and a \<body\> is created.
* When the tag is created, document.body is accessible.
* \<script\> tag is closed by \</script\>. Anything between them are script. Script may not be valid, and that doesn't matter (doesn't break HTML).
* Exception in previous \<script\> tag does not prevent the following 's execution.

---
Tags: code-golf, decision-problem, radiation-hardening
---


title: Pristine Bit Checking

text:
# Question
Title: Pristine Bit Checking
Write a program/function that takes two integers in the range \\$0\\$ to \\$255\\$ inclusive, and returns whether the binary forms of the numbers are exactly one bit different.

For example, \\$1\\$ and \\$0\\$ have binary forms `00000001` and `00000000`, which are one bit apart. Similarly, \\$152\\$ and \\$24\\$ are `010011000` and `000011000`, so they return true.

***However***, your code must be **pristine**, such that if any one bit in your program is flipped, it should throw an error. For example, if your program was the single byte `a` (`01100001`), then all the 8 possible modified programs:

```
á ! A q i e c `

```

must throw an error. Make sure you are modifying by *bytes* (e.g. the `á` up there is actually representing the byte \\$225\\$, not the actual two byte character `á`).

### Test cases:

```
0,1     => Truthy
1,0     => Truthy
152,24  => Truthy
10,10   => Falsey
10,11   => Truthy
11,12   => Falsey
255,0   => Falsey

```

## Rules:

* Provide a testing framework that can verify that your program is properly pristine, since there will be a lot of possible programs (number of bytes\*8), or else a complete proof of pristineness.
    + *Please* make sure your program is valid before you post it.
* Output needs to be either truthy/falsey (either way around is fine), or else two distinct non-error values
* Errors can be runtime, compiler, interpreter etc.

# Answer
# Python 2, 35 bytes

```
lambda a,b:(a^b)&-(a^b)in[a^b or[]]

```

Try it online!

Uses the power-of-two check `n&-n==n`, eliminating the `n==0` false positive.

For reference, these are the pairs of one-char binary operators that are one bit apart, making them hard to use:

```
+ /
- /
* +
% -
< |
< >

```

Fortunately, `&` and `^` are not among these.

Also note that `==` can become `<=`, and `+` can become the comment character `#`.

---

# Python 2, 41 bytes

```
lambda a,b:bin(a^b).count(`+True`)is+True

```

Try it online!

Taking TFeld's `lambda a,b:bin(a^b).count('1')==1` and making it pristine by changing the 1's to `+True` and `==` to `is`. Thanks to Jo King for 1 byte.
> 16 votes

# Answer
# Python 2, ~~72~~ ~~67~~ 50 bytes

```
lambda a,b:sum(map(int,'{:b}'.format(a^b)))is+True

```

Try it online!

<sub>-5 bytes, thanks to Jo King</sub>

---

Returns `True`/`False` for for truthy/falsey.

The program is basically the same as `lambda a,b:bin(a^b).count('1')==1`, but without numbers and other chars which work when bit-flipped.

Works by making sure that almost everything is a named function (which are all quite pristine)

The pristine test at the end flips a single bit (for every bit), and tries the function on an input. If that works (correct or not), that variation is printed. No printed programs = pristine function.
> 9 votes

# Answer
# Java 8, ~~68~~ ~~61~~ ~~56~~ 45 bytes

```
a->b->(a.bitCount(a^b)+"").equals(-~(a^a)+"")

```

-11 bytes thanks to *@EmbodimentOfIgnorance*, replacing constant `java.awt.Font.BOLD` with `-~(a^a)`.

Try it online.

**Explanation:**

The shortest base function would be:

```
a->b->a.bitCount(a^b)==1

```

Try it online.

This is modified so there isn't a digit, `=`, nor one of the `+/*` operands in it for numeric calculations (so the `+` for String-concatenation is fine):

The `+""` and `.equals` are to compare by `String.equals(String)` instead of `int==int`.
NOTE: `Integer.equals(int)` could be used here, but would be more bytes, since both the `.bitCount` and `java.awt.Font.BOLD` are primitive `int` instead of `Integer`-objects, so an additional `new Integer(...)` would be required to transform one of the two to an `Integer`-object, before we could use the `.equals`.
> 8 votes

# Answer
# C (gcc), 56 bytes

```
d(a,b){return(sizeof((char)d))^__builtin_popcount(a^b);}

```

Try it online!

Returns `0` if the pair differ by 1, non-zero otherwise. Slightly unusual for C, unless you consider it returning `EXIT_SUCCESS` if the pair differ by 1, any other value otherwise.

Uses `sizeof((char)d))` to produce the constant `1` in a pristine way while also forcing the function name to be pristine.

It then XORs that 1 with the popcount of the XOR of the arguments. Luckily the `^` symbol is easy to keep pristine, as is the very long identifier `__builtin_popcount`.

Meanwhile, here is the script used to test the solution:

```
#!/bin/bash

SOURCE_FILE=$1
FOOT_FILE=$2
TMP_SRC=temp.c

LENGTH="$(wc -c <"$SOURCE_FILE")"
BITS=$((LENGTH*8))

cat "$SOURCE_FILE" >"$TMP_SRC"
cat "$FOOT_FILE" >>"$TMP_SRC"
if gcc -w $TMP_SRC -o t.out >/dev/null 2>&1; then
    if ./t.out; then
        echo "Candidate solution..."
    else
        echo "Doesn't even work normally..."
        exit
    fi
else
    echo "Doesn't even compile..."
    exit
fi

for i in $(seq 1 $BITS); do
    ./flipbit "$i" <"$SOURCE_FILE" >"$TMP_SRC"
    cat "$FOOT_FILE" >>"$TMP_SRC"
    if gcc -w $TMP_SRC -o t.out >/dev/null 2>&1; then
        echo "Testing flipped bit $i:"
        cat "$TMP_SRC"

        ./t.out >/dev/null 2>&1
        STATUS=$?
        if [ "$STATUS" -eq 0 ]; then
            echo "It works!"
            exit
        elif [ "$STATUS" -eq 1 ]; then
            echo "It doesn't work..."
            exit
        else
            echo "It crashes"
        fi
    fi
done

```

Which uses the `./flipbit` tool I wrote whose source is simply:

```
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[]) {
    int bittoflip = atoi(argv[1]) - 1;
    int ch;

    while ((ch = fgetc(stdin)) != EOF) {
        if (bittoflip < 8 && bittoflip >= 0) {
            putchar(ch ^ (1 << bittoflip));
        } else {
            putchar(ch);
        }

        bittoflip -= 8;
    }

    return 0;
}

```

The tricky bits were:

* Whitespace: All whitespace (including newlines) have pristine twins that will work similarly
* Comparison: `=` doesn't work well, since it can be a comparison in every case it could appear. Similarly `-` doesn't work well. Thus `^` is used to assert equality with 1.
* Variable names: f would clash with b, so had to use d as the function name instead.
> 7 votes

# Answer
# , ~~38~~ 37 bytes

-1 byte thanks to Nick Kennedy.

```
dpois(log2(bitwXor(scan(),scan())),T)

```

Try it online! (Thanks to Giuseppe for setting up the TIO properly.)

Proof that it is pristine (using Nick Kennedy's checker).

Outputs 0 for falsey, and a positive value for truthy, which I understand is acceptable since R will interpret these as False and True.

Explanation: `bitwXor(a,b)` gives (as an integer) the bitwise XOR between `a` and `b`. To check whether it is a power of 2, check whether its log in base 2 is an integer. The function `dpois` gives the probability density function of the Poisson distribution: its value is 0 for non-integer values, and something positive for non-negative integers. The `T` is there because `dpois` requires a second argument (any positive real works, and `T` is interpreted as 1).

If we insist on outputting to distinct values, the following version outputs FALSE or TRUE in 42 bytes (thanks to Giuseppe for -8 bytes):

```
dpois(log2(bitwXor(scan(),scan())),T)%in%F

```

and is also pristine. Try it online!
> 7 votes

# Answer
# , 83 bytes

```
t(identical(sum(.<-as.double(intToBits(Reduce(bitwXor,scan())))),sum(T^el(.[-T]))))

```

Try it online!

Proof that this is pristine

Working around the fact that `as.integer`, `as.double` etc. are only a bit away from `is.integer`, `is.double` etc. was the hardest bit. In the end, using `sum(T^el(.[-T])` as a way of both generating a one and checking that `as.double` has returned a \>1 length vector was the best I could do. The wrapping `t` is to handle the fact that otherwise `identical` can become `ide~tical`.
> 6 votes

# Answer
# Julia 0.7, 20 bytes

```
(a,b)->ispow2(a⊻b)

```

Try it online!

Here is a pristine validator that tries running each modified anonymous function against some input, and neither passes successfully. Note that the code has a multi-byte unicode character, and some possible outputs from bit flipping are not even included, as those produce invalid UTF-8 strings.
> 5 votes

# Answer
# C# (Visual C# Interactive Compiler), 37 bytes

```
a=>b=>a!=b&((a^b)&-(a^b)).Equals(a^b)

```

The `a=>b=>` part cannot be changed, or else the function is invalid.

In `a!=b`, the `=` cannot be changed since `int` cannot be converted to `bool`.

Try it online!
> 5 votes

# Answer
# C# (Visual C# Interactive Compiler), ~~128~~ ~~101~~ ~~77~~ ~~70~~ ~~61~~ 74 bytes

*-27 bytes thanks to Ascii-Only*

```
a=>b=>{var d=Math.Log(a^b,(int)Math.E);return d.Equals((int)Math.Abs(d));}

```

Try it online!

You have to be quite creative to get numbers in C# without using literals. Only uses ^ operator. Variables a,b are all more than 1 bit away from each other and everything else is a keyword/name.
> 4 votes

# Answer
# JavaScript (ES6 in strict mode), 61 bytes

```
(y,z,e)=>eval(`(y${(e='^=z)*!(y&~-y)')!='^=z)*!(y&~-y)'||e}`)

```

Try it online! or Make sure that all modified programs are wrong
> 3 votes

# Answer
# Groovy, ~~47~~ 36 bytes

```
a,b->a.bitCount(a^b).equals(-~(a^a))

```

Try it online!

Adapted version of Kevin Cruijssen's Java answer.
> 2 votes

# Answer
# MATLAB, 37 bytes

```
@(c,e)eq(nnz(de2bi(bitxor(c,e))),eye)

```

Sorry, no TIO link, because I can't get the test suite to work under Octave. Thanks @ExpiredData for some helpful comments.

Test suite:

```
program = '@(c,e)eq(nnz(de2bi(bitxor(c,e))),eye)';
number_of_characters = nnz(program);
success = [];
for character_counter = 0 : number_of_characters
    for bit_no = 1:8
        prog_temp = program;
        if(character_counter > 0)
            prog_temp(character_counter) = bitxor(double(prog_temp(character_counter)),2^(bit_no-1));
        elseif(bit_no<8) % Test the unmodified program once
            continue
        end
        try
            eval(prog_temp);
            eval('ans(2,3)');
            disp(prog_temp)
            success(end+1)=1;
        catch
            success(end+1)=0;
        end
    end
end
assert(nnz(success)==1)

```
> 1 votes

# Answer
# Perl 6, ~~77~~ 43 bytes

*Thanks to Jo King for -33 bytes.*

```
{elems(i)eq(sum [+^](@_).polymod(+@_ xx*))}

```

This is equivalent to

```
{1 eq(sum [+^](@_).polymod(2 xx*))}

```

`1` was rewritten as `elems([""])`. `2` was rewritten as `sum(elems([""]),elems([""]))`; `elems(["",""])` might seem to work but `elems([""-""])` is also valid and seems to hang the tester.

Try it online!
> 1 votes

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

```
b=>d=>[i=d^b][i--&i]

```

Try it online!

validator by Arnauld, modified (not use strict)
> 1 votes

---
Tags: code-golf, decision-problem, restricted-source, pristine-programming
---


title: Black and white shirt 2

text:
# Question
Title: Black and white shirt 2
This is a more complicated version of this puzzle. The premise is the same but a few rules differ in a few key places, making for a more complex problem.

Assume I have some number of black shirts and some number of white shirts, both at least 1. Both colors of shirt have a non-zero durability. All shirts of a given color start with the same durability.

Every day, I pick out a clean shirt to wear, and it becomes dirty. Once I run out of all clean black shirts or all clean white shirts, I wash all my dirty shirts of both colors and start over. Clean shirts do not get washed. Whenever a shirt gets washed, its durability goes down by one. Immediately after washing, if the durability of a shirt reaches 0, it must be thrown out.

When picking which shirt to wear of a particular color, I specify whether I choose a shirt with highest (h) or lowest (l) remaining durability.

# Challenge:

Take in an arbitrarily long sequence of four indicators (eg. bh bh bl wl bl wh wl bh...) representing my choice of shirt to wear on that day. Continue execution until either my last black shirt or my last white shirt is thrown out. Once this occurs, stop consuming input and print out the remaining shirts’ durabilities.

## Inputs:

Number of black shirts, number of white shirts, durability of black shirts, durability of white shirts, and a sequence of shirt selections of arbitrary length at least long enough for one color of shirt to run out (can be considered infinitely long). The selection can be represented by a character pair (eg. bh, bl, wh, wl), or a single character (eg. b, B, w, W). Your choice, as long as there are four distinct inputs of 1 or 2 characters.

## Output:

Status of each remaining shirt, sorted by durability. All shirts will be of one color.

## Test cases:

The following test cases represent the amount of input the program should need to process before halting. The input is arbitrarily long otherwise.

```
1 1 1 1 bh
1

1 3 1 10 wh bh
10 10 9

1 5 2 10 wh wh bh wl wl wl bh
10 10 9 8 8

2 5 1 10 bh wh wh wl bl
10 10 9 9 9

1 5 6 5 wl wh bl wl wh bl wl wh bl wl wl bl wl wl wl bl wl wl wl wl bl
4 3 2 1

1 1 1 10 bl wh wh wh wh wh wh wh wh wh wh wh wh
10
#note the processing would stop occurring after the first bl and everything else should be ignored.

```

# General rules:

* This is , so shortest answer in bytes wins.
* Default I/O rules apply

# Answer
> 1 votes
# Perl 5, 254 bytes

```
sub f{@s=map[$_>$_[0]||0,$_>$_[0]?$_[3]:$_[2],1],1..$_[0]+$_[1];while(join('',map$$_[0],@s)=~/01|10/){($c,$p)=&{$_[4]};(@w=sort{$p*($$b[1]<=>$$a[1])}grep$$_[2]&&$$_[0]eq$c,@s)[0][2]=0;@s=grep$$_[2]||++$$_[2]&&--$$_[1],@s if@w<2}sort{$b<=>$a}map$$_[1],@s}

```

Try it online!

Ungolfed but same – with tests:

```
use Test::More tests=>6;
sub fu {
  my($countb,$countw,$durb,$durw,$get_todays)=@_;            #get 5 inputs
  my @s=( (map{{col=>'b',dur=>$durb,clean=>1}}1..$countb),   #init shirts array
          (map{{col=>'w',dur=>$durw,clean=>1}}1..$countw) );
  while(join('',map$$_{col},@s)=~/bw|wb/){                   #while still both colors left
    my($col,$p) = &$get_todays;                              #todays color and preference
    my @w = grep $$_{clean} && $$_{col} eq $col, @s;         #@w=wearable shirts
    my $shirt = (sort{$p*($$b{dur}<=>$$a{dur})}@w)[0];       #pick todays shirt w/most|least durability left
    $$shirt{clean}=0;                                        #dirty in the evening
    map{$$_{clean}=1;$$_{dur}--}grep!$$_{clean},@s if @w==1; #wash if there was only one this morning
    @s=grep$$_{dur}>0,@s;                                    #toss out worn outs
  }
  return sort{$b<=>$a}map$$_{dur},@s
}
my @test=(
'1 1 1 1 bh',                                                             '1',
'1 3 1 10 wh bh',                                                         '10 10 9',
'1 5 2 10 wh wh bh wl wl wl bh',                                          '10 10 9 8 8',
'2 5 1 10 bh wh wh wl bl',                                                '10 10 9 9 9',
'1 5 6 5 wl wh bl wl wh bl wl wh bl wl wl bl wl wl wl bl wl wl wl wl bl', '4 3 2 1',
'1 1 1 10 bl wh wh wh wh wh wh wh wh wh wh wh wh',                        '10'  #should see sequence not empty
);
while(@test){
  my($countb,$countw,$durb,$durw,@col)=split' ',shift@test;
  my @expected                        =split' ',shift@test;
  my $msg='';
  my $feederu=sub{ (shift(@col)//do{@expected='!',$msg='sequence ran out!'})
                   =~/(.)(.)/;($1,{h=>1,l=>-1}->{$2}) };
  my $feeder=sub{ (shift(@col)//do{@expected='!',$msg='sequence ran out!'})
                   =~/(.)(.)/;($1 eq 'w'||0,{h=>1,l=>-1}->{$2}) };
  my @got=fu($countb,$countw,$durb,$durw,$feederu);
 #my @got=f($countb,$countw,$durb,$durw,$feeder);
  $msg='sequense not empty' if @col;
  is(join(" ",@got),
     join(" ",@expected), $msg);
}

```

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


title: Help me sub-divide a time signature

text:
# Question
Title: Help me sub-divide a time signature
This challenge is based on a video in which Andrew Huang discusses unusual time signatures...

https://www.youtube.com/watch?v=JQk-1IXRfew

In it, he advises that you can understand time signatures by dividing them into 3's and 2's. So you count to a small number a few times, instead of counting to a large number.

Here's the pattern he builds which repeats after 19 steps:

* 5 groups of 3
* 2 groups of 2

This is how it looks:

```
#..#..#..#..#..#.#.

```

Actually, as you'd play each beat alternatively, the accented beats move from left to right, because there's an odd number of steps. So now this pattern is:

```
R..L..R..L..R..L.L.
L..R..L..R..L..R.R.

```

If we reduce this to an algorithm, it can be described like this.

## Step 1: where are the accents

* From your number of steps, start by taking groups of 3 from the start until there's 4 or fewer steps remaining.

E.g. for a pattern 8 steps long.

8 steps - take three, 5 steps remaining

```
#..

```

5 steps - take 3, 2 steps remaining

```
#..#..

```

Once we're down to 4 steps or fewer, there's 3 possibilities.

* 4 steps - 2 groups of 2
* 3 steps - 1 group of 3
* 2 steps - 1 group of 2

So from our above example:

```
#..#..#.

```

## Step 2: Which hand are the accents on

Let's assume that each individual step will be played on alternate hands, starting with the right.

So for 8 steps, the (underlying) pattern will go

```
rlrlrlrl

```

The pattern we output will only tell use which hand the accents are on. With the above example:

```
R..L..R.

```

That's fine, it's repeatable.

**but**

If it's an odd number, you've got the same hand for both the first and last steps, and you can't keep alternating when you repeat the pattern. Instead, the second pattern will be on the other hand. Here's the pattern on an 11 step pattern.

```
R..L..R..L.
L..R..L..R.

```

To clarify, if the pattern length is *odd*, we need to see the repeated, alternated pattern. If the length is *even*, we only need to see it once.

Hopefully that's clear enough:

---

# The Rules

* It's code golf, go for the shortest code.
* Your code will accept one pattern, a positive integer higher than 1.
* It will output some text describing a pattern diagram, as described above.
* Any language you like.
* Please include a link to an online interpreter.

# Test cases

2

```
R.

```

3

```
R..
L..

```

4

```
R.R.

```

7

```
R..L.L.
L..R.R.

```

9

```
R..L..R..
L..R..L..

```

10

```
R..L..R.R.

```

19

```
R..L..R..L..R..L.L.
L..R..L..R..L..R.R.

```

22

```
R..L..R..L..R..L..R.R.

```

# Answer
> 3 votes
# Retina 0.8.2, 66 bytes

```
.+
$*
1
RL
^(.+)RL\1$
$1R¶L$1
^(.+)\1$
$1
(.)(..?)(?!.\b)
$1$.2$*.

```

Try it online! Link includes test cases. Explanation:

```
.+
$*

```

Convert the input to unary.

```
1
RL

```

Alternate between hands.

```
^(.+)RL\1$
$1R¶L$1

```

If there are an odd number of beats then divide the output in the middle.

```
^(.+)\1$
$1

```

But if there are an even number of beats then just use one copy.

```
(.)(..?)(?!.\b)
$1$.2$*.

```

Try to match groups of three beats, but without leaving a lone beat at the end, and replace the offbeats with `.`s.

# Answer
> 3 votes
# Jelly, 25 bytes

```
Ṗ;’m3Ṭ»¬€ḤÐe,N$ṫḂṚị“LR.”Y

```

A monadic Link accepting an integer greater than one which yields a list of characters.

**Try it online!**

### How?

```
Ṗ;’m3Ṭ»¬€ḤÐe,N$ṫḂṚị“LR.”Y - Link: integer (>1), N     e.g. 13
Ṗ                         - popped range (N)               [1,2,3,4,5,6,7,8,9,10,11,12]
  ’                       - decrement (N)                  12
 ;                        - concatenate                    [1,2,3,4,5,6,7,8,9,10,11,12,12]
    3                     - literal three
   m                      - modulo slice                   [1,    4,    7,    10,      12]
     Ṭ                    - un-truth                       [1,0,0,1,0,0,1,0,0, 1, 0 ,1]
                          -                                     ...12th entry is a 1 ^
        €                 - for each of [1..N]:
       ¬                  -   logical NOT                  [0,0,0,0,0,0,0,0,0, 0, 0, 0, 0]
      »                   - maximum                        [1,0,0,1,0,0,1,0,0, 1, 0 ,1, 0]
          Ðe              - for entries at even indices:
         Ḥ                -   double                       [1,0,0,2,0,0,1,0,0, 2, 0, 2, 0]
              $           - last two links as a monad:
             N            -   negate                       [-1,0,0,-2,0,0,-1,0,0,-2,0,-2,0]
            ,             -   pair                         [[1,0,0,2,...],[-1,0,0,-2,...]]
                Ḃ         - modulo 2 (N)                   1
               ṫ          - tail from index                [[1,0,0,2,...],[-1,0,0,-2,...]]
                          -    ...Jelly indexing is 1-based & modular
                          -       so 0 would have resulted in [[-1,0,0,-2,...]]
                 Ṛ        - reverse                        [[-1,0,0,-2,...],[1,0,0,2,...]]
                          -    ...which for a list of length 1 is a no-op
                   “LR.”  - literal list of characters     ['L', 'R', '.']
                  ị       - index into (1-based & modular) ["R..L..R..L.L.","L..R..L..R.R."]
                        Y - join with newlines             "R..L..R..L.L.\nL..R..L..R.R."
                          -    ...which is just the entry for a list of length 1

```

# Answer
> 2 votes
# 05AB1E (legacy), ~~47~~ ~~43~~ ~~42~~ ~~41~~ 40 bytes

```
„RL×2äIÈ.£εÐ3äн€3sg3%i2TSǝR}£εćsg'.×«]J»

```

Not too happy with it..

Switched to the legacy version to save a byte (the legacy version replaces the values when using , whereas the new version leaves them in the list: Try `€3` in the legacy or try `€3` in the new version).
-1 byte thanks to *@Grimy*.

Try it online or verify all test cases.

**Explanation:**

```
„RL×          # Repeat "RL" the (implicit) input-integer amount of times
    2ä        # Divide it into 2 equal halves
      IÈ      # Check if the input-integer is even (1 if truthy; 0 if falsey)
        .£    # And remove that many items
              # Some examples of what we now have:
              #  7 → ["RLRLRLR","LRLRLRL"]
              #  9 → ["RLRLRLRLR","LRLRLRLRL"]
              #  10 → ["RLRLRLRLRL"]
ε             # Map each string in this list to:
 Ð            #  Triplicate the string
  3ä          #  Divide the string into 3 equal parts
    н         #  And only leave the first one
     €3       #  And convert each value to a 3
              #  (basically a golf from my previous ceil(length/3) amount of 3s list)
 sg           #  Swap to take the string again, and get its length
   3%i     }  #  If this length modulo-3 is exactly 1:
      2TSǝ    #   Replace the first two items (at indices 0 and 1) with 2s
          R   #   And reverse it: [3,3,3,...,2,2]
 £            #  Split the string according to this list
              #  Some examples again:
              #   ["RLRLRLR","LRLRLRL"] → [["RLR","LR","LR"],["LRL","RL","RL"]]
              #   ["RLRLRLRLR","LRLRLRLRL"] → [["RLR","LRL","RLR"],["LRL","RLR","LRL"]]
              #   ["RLRLRLRLRL"] → [["RLR","LRLR","RL","RL"]
 ε            #  Then map each inner substring to:
  ć           #   Extract head; pop and push remainder and head
   sg         #   Swap to get the remainder, and get it's length (either 1 or 2)
     '.×     '#   Create a string with that many "."
        «     #   And merge it to the extracted head
]             # After both the inner and outer map:
 J            # Join each inner list together to a single string
  »           # And then join the strings by newlines
              # (after which the result is output implicitly)

```

# Answer
> 1 votes
# JavaScript (ES6),  ~~84 81 78~~  75 bytes

```
f=(n,x,N)=>n?'RL.'[!--n|N%3%(3-!~-n)?2:N&1^x]+f(n,x,-~N):N&!x?`
`+f(N,1):''

```

Try it online!

### Commented

```
f = (               // f is a recursive function taking:
  n,                //   n = input
  x,                //   x = flag set to 1 if we're processing the 2nd row
  N                 //   N = counter incremented each time n is decremented
) =>                //
  n ?               // if n is not 0:
    'RL.'[          //   output the next character:
      !--n |        //     decrement n; if this is the last character
      N % 3 %       //     or N mod 3 is either
      (3 - !~-n) ?  //     odd if n = 1 or not equal to 0 otherwise:
        2           //       output '.'
      :             //     else:
        N & 1 ^ x   //       output either 'L' or 'R' depending on N and x
    ] +             //   end of character output
    f(n, x, -~N)    //   append the result of a recursive call with N+1
  :                 // else:
    N & !x ?        //   if x = 0 and N is odd:
      `\n` +        //     append a linefeed
      f(N, 1)       //     and restart with x = 1
    :               //   else:
      ''            //     stop recursion

```

# Answer
> 1 votes
# Julia 1.0, ~~83~~ ~~80~~ 75 bytes

```
n->(f(r,s,h='R'-6s)=r∈0:2:4 ? "$h."^(r>>1) : "$h.."*f(r-3,1-s)).(n,0:n%2)

```

Try it online!

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

```
Éƒ¶IÅœRΣP}θRv„LR¼¾èyG¼'.J

```

*-1 byte thanks to Kevin Cruijssen*

Try it online!

Explanation:

A signature subdivision can be seen as an integer partition. For example, `#..#.#.` is the partition `[3, 2, 2]` of 7.

A remarkable property of the subdivisions specified by this challenge is that they maximize product. For example, 3\*2\*2 = 12, and no other partition of 7 has a product \> 12 (only `[3, 4]` ties it). This can be proved true in the general case.

```
Éƒ                  # loop (input%2) + 1 times

¶                   # newline
 IÅœ                # integer partitions of the input
    R               # reverse, so that [2, 2, 3, ..., 3] comes after [3, ..., 3, 4]
     ΣP}            # sort by product (stable sort)
        θ           # take the last element
         R          # reverse it, so that the 2s are at the end

v                   # for each integer y in the partition
 „LR                # literal string "LR"
    ¼¾è             # increment counter_variable, then use it to index into "LR"
       yG           # loop y-1 times
         ¼          # increment counter_variable
          '.        # literal "."
            J       # join all the strings in the stack

```

---
Tags: code-golf, algorithm
---