title: Calculate 500 digits of pi

text:
# Question
Title: Calculate 500 digits of pi
Write a program to calculate the first 500 digits of pi, meeting the rules below:

* It must be less than 500 characters in length.
* It cannot include "pi", "math.pi" or similar pi constants, nor may it call a library function to calculate pi.
* It may not use the digits "3", "1" and "4" consecutively.
* It must execute in a reasonable time (under 1 minute) on a modern computer.

The shortest program wins.

# Answer
> 15 votes
## Golfscript - 29 chars

```
6666,-2%{2+.2/@*\/9)499?2*+}*

```

I will post analysis later

# Answer
> 9 votes
# Mathematica (34 chars): (without "cheating" with trig)

`N[2Integrate[[1-x^2]^.5,-1,1],500]`

So, to explain the magic here:
`Integrate[function, lower, upper]` gives you the area under the curve "function" from "lower" to "upper". In this case, that function is `[1-x^2]^.5`, which is a formula that describes the top half of a circle with radius 1. Because the circle has a radius of 1, it does not exist for values of x lower than -1 or higher than 1. Therefore, we are finding the area of half of a circle. When we multiply by 2, then we get the area inside of a circle of radius 1, which is equal to pi.

# Answer
> 8 votes
# Python (83 chars)

```
P=0
B=10**500
i=1666
while i:d=2*i+1;P=(P*i%B+(P*i/B+3*i)%d*B)/d;i-=1
print'3.%d'%P

```

# Answer
> 4 votes
## Python3 136

Uses Madhava's formula.

```
from decimal import *
D=Decimal
getcontext().prec=600
p=D(3).sqrt()*sum(D(2-k%2*4)/3**k/(2*k+1)for k in range(1100))
print(str(p)[:502])

```

## Python3 164

Uses this formula.

```
from decimal import *
D=Decimal
getcontext().prec=600
p=sum(D(1)/16**k*(D(4)/(8*k+1)-D(2)/(8*k+4)-D(1)/(8*k+5)-D(1)/(8*k+6))for k in range(411))
print(str(p)[:502])

```

# Answer
> 4 votes
# Husk, ~~28~~ ~~25~~ 24 bytes

```
i*!500İ⁰ΣG*2mṠ/o!İ1→ḣ□70

```

Try it online!

Calculates the value of pi as a rational number using the first 5000 terms of the infinite series `2 + 1/3*(2 + 2/5*(2 + 3/7*(2 + 4/9*(2 + ...))))`, and then extracts the first 500 digits.

The code to calculate the value of pi from a specified number of terms is only 13 bytes (`ΣG*2mṠ/o!İ1→ḣ`):

```
ΣG*2mṠ/o!İ1→ḣ
Σ                       # the sum of
 G*2                    # the cumulative product, starting at 2, of
    m                   # mapping the following function to all terms of
            ḣ           # series from 1 to ... (whatever number is specified)
     Ṡ/                 # divide by x
       o!  →            # element at index -1
         İ1             # of series of odd numbers

```

Unfortunately, we then need to waste 3 bytes specifying the number of terms to use:

```
□70                     # 70^2 = 4900

```

And then 8 more bytes converting the rational number (expressed as a fraction) into its digits in decimal form:

```
i*!500İ⁰
i                       # integer value of
 *                      # multiplying by
  !500                  # 500th element of
      İ⁰                # series of powers of 10

```

# Answer
> 4 votes
# Java 10, ~~208~~ ~~207~~ ~~206~~ ~~193~~ ~~176~~ 155 bytes

```
n->{var t=java.math.BigInteger.TEN.pow(499).shiftLeft(1);var p=t;for(int i=1656;i>0;)p=t.add(p.multiply(t.valueOf(i)).divide(t.valueOf(i-~i--)));return p;}

```

-14 bytes thanks to *@ceilingcat*.
-17 bytes thanks to *@jeJe*.
-21 bytes thanks to *@Neil* reverting the algorithm.

Try it online.

**Or as full program (203 bytes):**

```
interface M{static void main(String[]a){var t=java.math.BigInteger.TEN.pow(499).shiftLeft(1);var p=t;for(int i=1656;i>0;)p=t.add(p.multiply(t.valueOf(i)).divide(t.valueOf(i-~i--)));System.out.print(p);}}

```

Try it online.

# Answer
> 3 votes
## Mathematica (17 bytes)

```
N[ArcCos[-1],500]

```

Proof of validity.

# Answer
> 3 votes
## PARI/GP, 14

```
\p500
acos(-1)

```

You can avoid trig by replacing the second line with

```
gamma(.5)^2

```

or

```
(6*zeta(2))^.5

```

or

```
psi(3/4)-psi(1/4)

```

or

```
4*intnum(x=0,1,(1-x^2)^.5)

```

or

```
sumalt(k=2,(-1)^k/(2*k-3))*4

```

# Answer
> 2 votes
# Pyth, 21

```
u+/*GHhyHy^T500r^3T1Z

```

Uses this algorithm: `pi = 2 + 1/3*(2 + 2/5*(2 + 3/7*(2 + 4/9*(2 + ...))))` found in the comments of the Golfscript answer.

# Answer
> 2 votes
# Fortran, ~~154~~ 144 bytes

Mangled the rosetta code solution. Saved lots of bytes using implicit integers `i j k l m n`, `print` instead of `write`, and shuffling things around.

Try it online! <sub>~~154 bytes~~</sub>

```
integer::v(3350)=2;x=1E5;j=0;do n=1,101;do l=3350,1,-1
m=x*v(l)+i*l;i=m/(2*l-1);v(l)=m-i*(2*l-1);enddo
k=i/x;print'(I5.5)',j+k;j=i-k*x;enddo;end

```

# Answer
> 2 votes
# Raku, 44 bytes

```
(2.FatRat,{++$*$_/(2*++$+1)}...*)[^1658].sum

```

Try it online!

A search for a series that quickly converges to pi led to this Math StackExchange answer, which I implemented in Raku. The series consists of FatRats, which is Raku's unlimited-precision rational number type. A little calculation and trial and error showed that 1,658 terms are sufficient to obtain 500 decimal places of accuracy.

# Answer
> 1 votes
## bc -l (22 = 5 command line + 17 program)

```
scale=500
4*a(1)

```

# Answer
> 1 votes
# Mathematica - 50

```
½ = 1/2; 2/Times @@ FixedPointList[(½ + ½ #)^½~N~500 &, ½^½]

```

# Answer
> 1 votes
# Axiom, 80 bytes

```
digits(503);v:=1./sqrt(3);6*reduce(+,[(-1)^k*v^(2*k+1)/(2*k+1)for k in 0..2000])

```

for reference https://tuts4you.com/download.php?view.452; it would be an approssimation to 6\*arctg(1/sqrt(3))=%pi and it would use serie expansion for arctg

```
  3.1415926535 8979323846 2643383279 5028841971 6939937510 5820974944 592307816
  4 0628620899 8628034825 3421170679 8214808651 3282306647 0938446095 505822317
  2 5359408128 4811174502 8410270193 8521105559 6446229489 5493038196 442881097
  5 6659334461 2847564823 3786783165 2712019091 4564856692 3460348610 454326648
  2 1339360726 0249141273 7245870066 0631558817 4881520920 9628292540 917153643
  6 7892590360 0113305305 4882046652 1384146951 9415116094 3305727036 575959195
  3 0921861173 8193261179 3105118548 0744623799 6274956735 1885752724 891227938
  1 8301194913 01

```

# Answer
> 1 votes
# 05AB1E, 20 bytes

```
₄°·D.ΓN>*N·3+÷}O+₄;£

```

Port of my Java answer (with the `503` replaced with `1000` \- anything \\$\geq503\\$ is fine to output the first 500 digits accurately with this approach).

Try it online or verify it's equal to the first 500 digits of PI using the builtin `žs`.

**Explanation:**

```
₄°              # Push 10**1000
  ·             # Double it to 2e1000
   D            # Duplicate it
    .Γ          # Loop until the result no longer changes,
                # collecting all intermediate results
                # (excluding the initial value unfortunately)
      N>        #  Push the 0-based loop-index, and increase it by 1 to make it 1-based
        *       #  Multiply this 1-based index to the current value
         N·     #  Push the 0-based index again, and double it
           3+   #  Add 3 to it
             ÷  #  Integer-divide the (index+1)*value by this (2*index+3)
     }O         # After the cumulative fixed-point loop: sum all values in the list
       +        # Add the 2e1000 we've duplicated, which wasn't included in the list
        ₄;      # Push 1000, and halve it to 500
          £     # Leave the first 500 digits of what we've calculated
                # (after which it is output implicitly as result)

```

# Answer
> 1 votes
# APL (NARS2000), 20 bytes

```
{2+⍵×⍺÷1+⍨2×⍺}/⍳7e3x

```

I haven't been able to test this, but here's a version in Dyalog APL. The only difference between them is the suffix "x", which is used for rational numbers in NARS2000 but is not available in Dyalog (or other variants available online, as far as I know).

It's based on the `pi = 2 + 1/3*(2 + 2/5*(2 + 3/7*(2 + 4/9*(2 + ...))))` formula in the comments under the accepted Golfscript answer.

# Answer
> 1 votes
# Scala 3, ~~96~~ 84 bytes

A port of @Kevin Cruijssen's Java 10 answer in Scala.

Saved 12 bytes thanks to @ceilingcat

---

Golfed version. Attempt This Online!

```
_=>{val t=BigInt(10).pow(499)*2;var p=t;for i<- 1656 to 1 by-1 do p=t+p*i/(2*i+1);p}

```

Ungolfed version. Attempt This Online!

```
_ => {
  val t = BigInt(10).pow(499) << 1
  var p = t
  var i = 1656
  while (i > 0) {
    val temp = 2 * i + 1
    p = t + (p * BigInt(i) / temp)
    i -= 1
  }
  p
}

```

# Answer
> 0 votes
# APL(NARS), 213 chars

```
r2fs←{⎕ct←0⋄k←≢b←⍕⌊⍵×10x*a←⍺⋄k-←s←'¯'=↑b⋄c←{s:'¯'⋄''}⋄m←s↓b⋄0≥k-⍺:c,'0.',((⍺-k)⍴'0'),m⋄c,((k-⍺)↑m),'.',(k-⍺)↓m}

r←P w;i;d;e;k
r←i←0x⋄e←÷10x*w
k←1+8×i⋄d←(+/4 2 1 1÷k,-k+3..5)×÷16*i⋄→3×⍳e>∣d⋄r+←d⋄i+←1⋄→2

{⍵r2fs P⍵}500

```

111+13+15+59+2+13=213

`p r2fs w`, return a string of the rational number in w seen as float with p digits afther the point.

`P p`, would return a rational number enough to be traslated from `r2fs` to a float string with p digits of precision.

Test (the last digit is always not rounded)- output:

```
  3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066
  470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461284756482337
  867831652712019091456485669234603486104543266482133936072602491412737245870066063155881748815209209628292540917153
  643678925903600113305305488204665213841469519415116094330572703657595919530921861173819326117931051185480744623799
  6274956735188575272489122793818301194912

```

---
Tags: code-golf, restricted-source, pi, restricted-time
---


# Question
Title: Output all the different counts of points
Consider a 10 by 10 grid of points at integer coordinates. Given a coordinate (x, y) of one of the points in the grid and a radius r, some of the points in the grid will fall inside a circle of radius r that is centered at (x, y). You will count the number of such points.

# Input

An integer coordinate (x, y) in a 10 by 10 grid.

# Output

All the different counts for the number of points in the grid that are inside a circle centered at (x, y), for every possible radius r. Your output should not contain duplicate values but can be in any order.

You may not assume that r is an integer so there are an infinite number of possible radii but your output will nonetheless be of finite size. For example, the same count arises for all 0\<r\<1.

The numbers 1 and 100 will always be in your output no matter what (x, y) are.

If (x, y) is a corner, the output should be:

```
[1, 3, 4, 6, 8, 9, 11, 13, 15, 17, 19, 20, 22, 26, 28, 30, 31, 33, 35, 37, 39, 41, 43, 45, 48, 50, 52, 54, 56, 58, 62, 64, 65, 67, 69, 71, 73, 75, 79, 81, 83, 85, 86, 88, 90, 92, 94, 95, 97, 99, 100]

```

If (x, y) is on a side and not too close to a corner then the output should include 1, 4, 6, 9, 13, 15, 18, 22, 26.

If (x, y) is somewhere in the middle then your output should include 1, 5, 9, 13, 21, 25, 29. For example if it is (4, 3) the output should be \[1, 5, 9, 13, 21, 25, 29, 37, 45, 48, 54, 58, 64, 72, 76, 80, 82, 86, 87, 89, 91, 94, 96, 97, 99, 100\].

# Answer
# Vyxal 3, 12 bytes

```
₀ʀ2ẋᵗϩİ?ȧS†@

```

10x10 grid located in coordinates 0-9. Takes input as a complex number.

Try it Online!

**Explanation**

```
₀ʀ2ẋᵗϩİ?ȧS†@
  2ẋ          # 2nd cartesian power of
₀ʀ            # Range 0-9
    ᵗϩ        # Map through all coordinates and dump to stack
      İ?ȧ     # Absolute difference between input and coordinate
         S†   # Sort list and return length of consecutive groups
           @  # Cumulatively add all lengths

```

#### Original answer, 13 bytes

```
₀ʀ2ẋƛ?-²∑}S†@
  2ẋ            # 2nd cartesian power of
₀ʀ              # Range 0-9
    ƛ    }      # Map through all coordinates
     ?-²∑       # Squared euclidean distance between input and coordinate
          S†    # Sort list and return length of consecutive groups
            @   # Cumulatively add all lengths

```

Created with the help of Luminespire.
> 5 votes

# Answer
# Wolfram Language (Mathematica), 101 bytes

```
Union@Table[p=#;Length@Select[Join@@Array[{#,#2}&,{10,10},0],p~EuclideanDistance~#<r&],{r,1,20,.01}]&

```

Try it online!
> 3 votes

# Answer
# Jelly, 10 bytes

```
⁵p`Æịạ⁸ĠẈÄ

```

Try it online!

A monadic link taking a co-ordinate on a grid from 1..10 on both axes and expressed as a complex number. A list of integers is returned.

## Explanation

```
⁵p`        | Cartesian product of 1..10 with itself
   Æị      | Convert to complex
     ạ⁸    | Absolute difference with link argument
       Ġ   | Indices to group identical values (ordered by the values)
        Ẉ  | Group lengths
         Ä | Cumulative sum

```
> 3 votes

# Answer
# Wolfram Language (Mathematica), 57 bytes

```
i+=#2&@@@Tally@Sort@{Array[# #+#2#2&,10+{i=0,0},-#,##&]}&

```

Try it online!

```
                     Array[# #+#2#2&,10+{  0,0},-#,   ]     distance to each point
               Sort@{                              ##& }    ascending by distance
   #2&@@@Tally@                                             counts of each
i+=  &@@@                                i=                 cumulative

```
> 3 votes

# Answer
# APL(Dyalog Unicode), ~~32~~27 bytes SBCS

```
{⍸⌽≠{⍵[⍒⍵]},+.×⍨⍤-∘⍵¨⍳2⍴10}

```

Try it on APLgolf!

-5 bytes thanks to att.

A dfn which takes a vector on the right and outputs the list of possible counts.

## Old explanation

```
{+\{≢⍵}⌸{⍵[⍋⍵]},∘.(+.×⍨⍵-,)⍨⍳10}
                            ⍳10   # range 1-10
                ∘.(       )⍨      # For every pair of elements
                         ,        # pair into vector
                       ⍵-         # subtract from input vector
                   +.×⍨           # dot product with itself
               ,                  # matrix to list
        {⍵[⍋⍵]}                   # sort
   {≢⍵}⌸                          # frequencies of groups
 +\                               # cumulative sums

```

Created with the help of Luminespire.
> 2 votes

# Answer
# Desmos, 75 bytes

```
f(p)=[L[L<=i].countfori=L].unique
I=[0...9]
L=[distance(p,(a,b))fora=I,b=I]

```

Input as a point `(x,y)`, ranging between coordinates 0 to 9.

Try It On Desmos!

Try It On Desmos! - Prettified
> 2 votes

# Answer
# Scala, ~~156~~ 146 bytes

Use `Double scala.math.hypot(Double length, Double base)` to calculate the square root of the sum of squares of the 2 numbers.

Saved 10 bytes thanks to @ceilingcat

---

Golfed version. Try it online!

```
(x,y)=>{val p=for{i<-0 to 99}yield(i/10,i%10);p.foldLeft(Set(1,100)){(a,t)=>a+p.count{case(a,b)=>math.hypot(a-x,b-y)<=math.hypot(t._1-x,t._2-y)}}}

```

Ungolfed version. Try it online!

```
object Main {
  val gridSize = 10

  def main(args: Array[String]): Unit = {
    // Example usage:
    val countsForCorner = countPointsInCircleForAllRadii(0, 0)
    val countsForSide = countPointsInCircleForAllRadii(0, 5)
    val countsForMiddle = countPointsInCircleForAllRadii(5, 5)

    println(countsForCorner.toList.sorted.mkString("[", ", ", "]"))
    println(countsForSide.toList.sorted.mkString("[", ", ", "]"))
    println(countsForMiddle.toList.sorted.mkString("[", ", ", "]"))
  }

  def countPointsInCircleForAllRadii(x: Int, y: Int): Set[Int] = {
    val points = for {
      i <- 0 until gridSize
      j <- 0 until gridSize
    } yield (i, j)

    val counts = points.foldLeft(Set[Int]()) { (acc, point) =>
      val (px, py) = point
      val maxRadius = math.sqrt(math.pow(px - x, 2) + math.pow(py - y, 2))
      val count = points.count { case (cx, cy) =>
        math.sqrt(math.pow(cx - x, 2) + math.pow(cy - y, 2)) <= maxRadius
      }
      acc + count
    }

    // Ensure 1 and 100 are always included as per the specifications
    counts + 1 + 100
  }
}

```
> 2 votes

# Answer
# , 47 bytes

```
\(x)cumsum(table(abs(x-outer(0:9,0:9*1i,`+`))))

```

Attempt This Online!

A function taking a complex argument and returning a list of integers. Uses a zero-indexed grid from 0..9 on both axes.
> 2 votes

# Answer
# TI-BASIC, 73 bytes

```
abs(Ans-seq(10fPart(.1I)+int(.1I),I,0,99→L
SortA(ʟL
ΔList(augment(ʟL,{0
cumSum(1 or Ans)not(not(Ans→L
SortD(ʟL
seq(ʟL(I),I,1,sum(1 and ʟL

```

Takes input in `Ans` as a complex number with the x and y from 0 to 9.
> 2 votes

# Answer
# Charcoal, 37 bytes

```
ＮθＮηＦχＦχ⊞υ⁺Ｘ⁻θι²Ｘ⁻ηκ²Ｗυ«⟦ＩＬυ⟧≔⁻υ⟦⌈υ⟧υ

```

Try it online! Link is to verbose version of code. 0-indexed. Outputs the counts in descending order. Explanation:

```
ＮθＮη

```

Input the centre point.

```
ＦχＦχ

```

Loop over all of the points in the grid.

```
⊞υ⁺Ｘ⁻θι²Ｘ⁻ηκ²

```

Calculate the squared distance from the centre to that point.

```
Ｗυ«

```

Repeat until no more squared distances remain.

```
⟦ＩＬυ⟧

```

Output the current count of squared distances.

```
≔⁻υ⟦⌈υ⟧υ

```

Remove the highest squared distance(s).

Output in ascending order costs 2 bytes, but 2 bytes can be saved by using the newer version of Charcoal on ATO and taking input as a Gaussian integer:

```
Ｎθ≔ΣＥχＥχ↔⁻θ⁺ι×λＩ1jηＷ⁻ηυ⊞υ⌊ιＩＥυＬΦη¬›λι

```

Attempt This Online! Link is to verbose version of code. 0-indexed. Explanation:

```
Ｎθ

```

Input the centre point.

```
≔ΣＥχＥχ↔⁻θ⁺ι×λＩ1jη

```

Calculate the distances to all of the points in the grid.

```
Ｗ⁻ηυ⊞υ⌊ι

```

Sort and deduplicate the distances.

```
ＩＥυＬΦη¬›λι

```

For each unique distance, output the count of points not greater than that distance.
> 1 votes

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

```
x=>y=>[...w=Array(i=100)].map(t=>w[j=(--i%10)**2+(i/10|0)**2]=-~w[j])&&w.flatMap(t=>i+=t)

```

Try it online!

# JavaScript (Node.js), 104 bytes

```
x=>y=>[...[...Array(i=100)].map(e=t=>(--i%10)**2+(i/10|0)**2+1e7).sort(),0].flatMap((t,i)=>e-(e=t)?i:[])

```

Try it online!
> 1 votes

# Answer
# Perl 5 `-la`, ~~69~~ 66 bytes

```
map/.$/&++$a[("@F"-$`)**2+($F[1]-$&)**2],0..99;$_&&say$t+=$_ for@a

```

Try it online!

Grid is labeled 0-9 on both axes. Input of X and Y is on one line, space separated. Output is line separated.
> 1 votes

# Answer
# Rust, ~~322~~ ~~259~~ ~~254~~ 125 bytes

A port of my Scala answer in Rust.

Saved 68 bytes thanks to @ceilingcat

Saved 129 bytes thanks to @att

---

Golfed version. Attempt This Online!

```
|x,y|->HashSet<_>{let p=||(0..=99).map(|i|(|a,b|a*a+b*b)(i/10-x,i%10-y));p().map(|a|p().filter(|&b|b<=a).count()).collect()};

```

Ungolfed version. Attempt This Online!

```
use std::collections::HashSet;

const GRID_SIZE: i32 = 10;

fn main() {
    // Example usage:
    let counts_for_corner = count_points_in_circle_for_all_radii(0, 0);
    let mut sorted_counts_for_corner: Vec<_> = counts_for_corner.into_iter().collect();
    sorted_counts_for_corner.sort_unstable();
    println!("{:?}", sorted_counts_for_corner);

    let counts_for_side = count_points_in_circle_for_all_radii(0, 5);
    let mut sorted_counts_for_side: Vec<_> = counts_for_side.into_iter().collect();
    sorted_counts_for_side.sort_unstable();
    println!("{:?}", sorted_counts_for_side);

    let counts_for_middle = count_points_in_circle_for_all_radii(5, 5);
    let mut sorted_counts_for_middle: Vec<_> = counts_for_middle.into_iter().collect();
    sorted_counts_for_middle.sort_unstable();
    println!("{:?}", sorted_counts_for_middle);
}

fn count_points_in_circle_for_all_radii(x: i32, y: i32) -> HashSet<i32> {
    let points = (0..GRID_SIZE)
        .flat_map(|i| (0..GRID_SIZE).map(move |j| (i, j)))
        .collect::<Vec<_>>();

    let mut counts = HashSet::new();

    for point in &points {
        let (px, py) = *point;
        let max_radius = (((px - x).pow(2) + (py - y).pow(2)) as f64).sqrt();
        let count = points.iter().filter(|&&(cx, cy)| {
            (((cx - x).pow(2) + (cy - y).pow(2)) as f64).sqrt() <= max_radius
        }).count() as i32;

        counts.insert(count);
    }

    // Ensure 1 and 100 are always included as per the specifications
    counts.insert(1);
    counts.insert(100);

    counts
}

```
> 1 votes

---
Tags: code-golf
---


title: Coin sequence probability

text:
# Question
Title: Coin sequence probability
Given two strings containing only `0` and `1`, decide the probability that first appears earlier as a consecutive substring in an infinite random 0/1 stream.

You can assume that neither string is suffix of the other string, so `01, 1`, `00, 0` are invalid. (\*)

IO format flexible. Your answer should be precise given ideal floating point numbers, so sampling is likely not a good idea.

Shortest code wins.

# Note

* I'd like to see how much longer code without assumption `(*)`, allowing collision in a sequence but won't happen (due to fact that one string would appear earlier) or even just no extra rule(In which case `f(a,b)+f(b,a)!=1`). Therefore, you may also provide version(s) that do so, even if longer, if convenient.

# Test cases

```
0, 1 => 50%
00, 1 => 25%
10, 00 => 75%
0, 01 => 100%
011, 001 => 1/3
00, 110 => 1/2 (Example with different length input but result half)
000, 101 => 5/12 (Examples provided by Bubbler)
000, 011 => 2/5
111, 1001 => 4/7
111, 0011 => 5/12 (Suggested by Neil, longer string would likely come earlier)
(Following not required)
11, 1 => 0%
1, 11 => 100%
10, 10 => 100% (0% if you choose strict early)
01, 1 => 50%   (0%)
1, 01 => 100%  (50%)

```

# References

# Answer
> 8 votes
# Charcoal, ~~34~~ 32 bytes

```
≔⮌Ｅ²ＳθＩＥθΣ⊞ＯυΣＥθ×⊖⊗⁼κμ↨²Ｅι¬⌕λ✂ιξ

```

Try it online! Link is to verbose version of code. Outputs the ratio as a fraction but not necessarily in lowest terms. Technically works for all edge cases although two identical inputs outputs `0/0`. Explanation: For the Cartesian product of the two inputs with itself, calculates which suffixes of one are prefixes of the other, then interprets that in base `2`; this is negated when the strings are compared against each other. The final denominator is simply the sum of all four values; the numerator is the sum of two of them. Example for `111` and `0011`:

```
Suffixes of 111: 111 11 1
Are they prefixes of 111? 1 1 1 = 7
Are they prefixes of 0011? 0 0 0 = -0
Suffixes of 0011: 0011 011 11 1
Are they prefixes of 111? 0 0 1 1 = -3
Are they prefixes of 0011? 1 0 0 0 = 8
Numerator = 8 - 3 = 5
Denominator = 8 - 3 + 7 - 0 = 12

```

Note that the values `7` and `8` are also half the indices at which you would expect to find `111` and `0011` respectively, which leads to the paradox that although you would expect to see `0011` first, the expected position of `111` is before that of `0011`.

26 bytes by taking input in the form of a reversed list:

```
ＩＥθΣ⊞ＯυΣＥθ×⊖⊗⁼κμ↨²Ｅι¬⌕λ✂ιξ

```

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

```
  θ                         Input list
 Ｅ                          Map over elements
         θ                  Input list
        Ｅ                   Map over elements
              κ             Outer index
             ⁼              Equals
               μ            Inner index
            ⊗               Doubled
           ⊖                Decremented
          ×                 Times
                   ι        Outer string
                  Ｅ         Map over characters
                      λ     Inner string
                    ¬⌕      Begins with
                        ι   Outer string
                       ✂    Sliced from
                         ξ  Innermost index
                ↨           Convert from base
                 ²          Literal integer `2`
       Σ                    Take the sum
    ⊞Ｏυ                     Push to predefined empty list
   Σ                        Take the sum of that list
Ｉ                           Cast to string
                            Implicitly print

```

# Answer
> 2 votes
# Uiua 0.8.0, 35 bytes SBCS

```
+,∩(-:∩(°⋯⇌⊢⍉⊐≡⌕),:≡(□↘)⇡⧻♭..∩¤)⊙.,

```

Try on Uiua Pad!

Port of Neil's answer.

## Explanation

```
⊙., # duplicate inputs in reverse order
∩(  # on both pairs,
  ∩¤    # add an axis to both inputs
  ⇡⧻♭.. # dup the first twice and range the length
  ≡(□↘) # for each in the range,
        # drop that much from the front and box the result
  ,:    # dup top of stack to third
  ∩(    # on both pairs,
    ⊐≡⌕ # find suffixes in input
    ⊢⍉  # first column
    °⋯⇌ # reverse then un-bits, binary to number
  )
  -:    # subtract second from top
)
+,  # duplicate the second onto top then add

```

# Answer
> 1 votes
# Jelly, 16 bytes

```
¹ÐƤ€eþ€¹Ƥ€Ḅạ/€UÄ

```

Try it online!

A Jelly port of Neil’s Charcoal answer, so be sure to upvote that one too!

If odds are allowable as output, one byte can be saved (by omitting the `Ä`). If it’s allowable to reverse the order of the inputs, then a further byte can be saved (omit the last `U`).

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


title: The Caged Circles

text:
# Question
Title: The Caged Circles
This problem will have you analyzing circles drawn on the grid, with the gridlines drawn at integer values of \\$x\\$ and \\$y\\$.

Let \\$\varepsilon\\$ be a very small number (think, \\$\varepsilon = 0.0001\\$). If we paint a filled-in circle of radius \\$\varepsilon\\$ centered at the origin, it will require paint to be in \\$4\\$ boxes; painting a circle of radius \\$1 + \varepsilon\\$ will send the paintbrush to \\$12\\$ different boxes (second, red circle); painting a circle of radius \\$\sqrt 2 + \varepsilon\\$ will send the paintbrush to \\$16\\$ different boxes (third, green circle).

There's no way to draw a circle based at the origin that lives in exactly \\$13\\$ or \\$14\\$ or \\$15\\$ boxes, so the possible number of boxes that a circle can live in is given by `[4, 12, 16, ...]`.

# Rules

This challenge will give you a point \\$(x,y)\\$ on the plane consisting of two rational numbers \\$x\\$ and \\$y\\$. Your job is to output the first sixteen (or more!) terms of the sequence consisting of all numbers \\$b\\$ such that there is a way to draw a circle centered at \\$(x,y)\\$ that contains a part of exactly \\$b\\$ boxes.

Any reasonable input is allowed: you can take the center point as a pair of floats, a complex number, a list containing numerators and denominators in some order, etc.

This is a challenge, so the shortest code wins.

# Examples

In my example, the inputs are written as pairs of rational numbers. The first entry in the table is illustrated above.

```
[input]    | [output]
(x, y)     | sequence
-----------+----------------------------------------------------------------------
(0/1, 0/1) | 4, 12, 16, 24, 32, 36, 44, 52, 60, 68, 76, 80, 88, 104, 112, 120, ...
(5/1, 5/2) | 2,  6,  8, 12, 16, 20, 22, 26, 34, 38, 40, 44, 48,  52,  56,  60, ...
(1/3, 8/1) | 2,  4,  6,  8, 10, 12, 14, 18, 20, 22, 24, 26, 28,  30,  32,  34, ...
(1/2, 3/2) | 1,  5,  9, 13, 21, 25, 29, 37, 45, 49, 61, 69, 77,  81,  89,  97, ...
(1/3,-1/3) | 1,  3,  4,  6,  8,  9, 11, 13, 15, 17, 19, 21, 22,  24,  26,  29, ...
(1/9, 8/7) | 1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13,  14,  15,  16, ...

```

(If it helps, the first example is given by \\$4\\$ times A000592.)

# Answer
> 4 votes
# MATL, ~~51~~ 50 bytes

```
p-9:9*tJ*!+1ei1GP*1Gp\tFF5Mth3$v-!Z}J*!+u-|X<S&Y'Ys

```

The input consists of an array containing the denominators followed by an array containing the numerators. The output may contain more than 16 terms.

Try it online! Or verify all test cases (with output trimmed to 16 terms for convenience)

### Explanation

Let (*x*, *y*) be the input values modulo 1. The code checks the distance from the (*x*, *y*) to each square with lower left corner (*a*, *b*), where *a* and *b* are integers. To do that, 9 points of the square are tested: (*a*+*m*,*b*+*n*) with *m* = 0, *x*, 1 and *n* = 0, *y*, 1, and the minimum of the 9 distances is kept.

A grid of 19×19 squares with *a*, *b* = −9, −8, ..., 9 is generated. The distance from (*x*, *y*) to each square is computed as described in the preceding paragraph. The 361 distances are sorted and run-length encoded, and the cumulative sum of the run lengths is the desired output.

To keep floating-point issues as controlled as possible, instead of using the actual values for *x*, *y*, *a*, *b*, *m*, *n*, the code uses those values multiplied by the product of the two input denominators.

```
p       % Implicit input: array with the denominators. Product
-9:9    % Push [-9, -8, ... 9]
*       % Multiply, element-wise
tJ*     % Duplicate, multiply by j (imaginary unit) element-wise
!+      % Transpose, add with broadcast. This generates the 19×19 grid of
        % complex values
1e      % Linearize into a row vector
i       % Input: array with the numerators
1GP     % Push first input again. Flip it
*       % Multiply, element-wise
1Gp     % Push first input again. Product (*)
\       % Modulo, element-wise (**)
t       % Duplicate
FF      % Push [0 0]
5Mth    % Push (*) again. Duplicate, concatenate with itself horizontally
3$v     % Concatenate three elements vertically. Gives a 3×2 matrix
-       % Subtract (*) with broadcast
!       % Transpose. The result is a 2×3 matrix
Z}      % Split into two rows with 3 elements
J*      % Multiply by j (imaginary unit) element-wise
!+      % Transpose, add with broadcast. This gives a 3×3 matrix with the
        % 9 points to be considered in each square
u       % Unique. This gives a column vector with the (unique) values
-|      % Subtract with broadcast, absolute value. Gives a 9×361 matrix
X<      % Minimum of each column. This gives the 361 distances
S       % Sort
&Y'     % Run-length encoding, producing only the run lengths
Ys      % Cumulative sum. Implicit display

```

# Answer
> 7 votes
# PowerShell, 317 313 305 298 281 274 231 221 210 207 195 181 136 126 111 109 108 bytes

-an enormous 94 bytes thanks to mazzy!

I must say, I never expected to beat Charcoal in this challenge; and when I posted that 317 byte answer, I certainly never expected to get it all the way down to the low 100s. I'm hopeful I can shave those final 10 to get to sub-100, but this feels so very optimized!

Takes the x and y offsets (center of the circle) as inputs. Generates all points in the range `(-9..9,-9..9)`, then adds points for potential border intersections, which handles offset circles, and handles doubling point values on x,0 or 0,y coordinates when the circle is centered on the origin. Groups all of those points by their squared distance from the origin, then for each group outputs the sum of the group's count and the counts of all groups with distance smaller than that group. Multiplies all of the squared distances by 1e7 then casts to Integer to avoid issues with floating points.

Because it groups the distances, it does output more than the first 16 terms, but as the challenger stated that this is acceptable, the TIO link truncates the output to the first 16 terms to make it more clear which tests succeed.

```
$x,$y=$args|%{,(-9..9+($p=$_%1)|%{($t=$_-$p)*$t*1e7})}
$x|%{$n=$_;$y|%{[Int]($n+$_)}}|group|% c*|%{($s+=$_)}

```

Try it online!

# Ungolfed

At this point, the ungolfed solution is more a representation of the logic behind my solution than it is an ungolfed version of the solution - as the iterations have been made, I haven't been able to keep up with the changes on the ungolfed version. I am leaving it in here, despite the discrepancy, in hopes that it will inspires to answer in their language of choice (or port it to their language)

```

#Take the x-offset, y-offset, and starting radius as a parameter
#radius starts at 0, so that the first element will be the count of points on the origin of the circle
param($xOffset,$yOffset,$radius=0)
#set the x and y offsets to be in the range [0,1)
$xOffset=$xOffset % 1
$yOffset=$yOffset % 1
#do 16 times (for the required 16 elements)
1..16|%{
	#make an array of points
	$points = @()
	#set our limits to the edge of the bounding box of the circle
	#this will normally be within 1 of the actual circle, but offsets of .5
	#will increase the search space due to .NET's banker's rounding
	$upperSearchLimitX = [Int]($xOffset+$radius+1)
	$lowerSearchLimitX = -$upperSearchLimitX
	$upperSearchLimitY = [Int]($yOffset+$radius+1)
	$lowerSearchLimitY = -$upperSearchLimitY
	#generate x and y for every combination of values in those ranges
	$lowerSearchLimitX..$upperSearchLimitX | %{
		$x = $_
		$lowerSearchLimitY..$upperSearchLimitY | %{
			$y = $_
			#add the point to our list
			$points+=@{x=$x;y=$y}
			#If x is zero, also add a special point that represents a border intersection to the list
			#this will also make x,0 points count for two when the center is at 0,0
			if (!$x) {
				$points+=@{x=$x+$xOffset;y=$y}
			}
			#If y is zero, also add a special point that represents a border intersection to the list
			#this will also make 0,y points count for two when the center is at 0,0
			if (!$y) {
				$points+=@{x=$x;y=$y+$yOffset}
			}
		}
	}
	#add the center point to the list
	$points += @{x=$xOffset;y=$yOffset}
	#set the minimum point as the closest point to our current circle that's outside of the bounds of the circle
	$minimum =	$points|?{
				($_.distance=[Math]::Sqrt(($_.x-$xOffset)*($_.x-$xOffset)+($_.y-$yOffset)*($_.y-$yOffset))) -gt $radius
			}|sort distance -t 1
	#set our new radius to be that point's distance from the x offset
	$radius = $minimum.distance
	#count the number of points that lie inside (but not on the boundary of) this new circle, output implicitly
	@($points|?{$_.distance -lt $radius}).Count
}

```

Try it online!

I'm not the best at making images; if anyone can recommend a good tool for things like these, let me know. But here's a rough sketch of all the points that get checked along with the order we iterate to them in for x=3/8, y=1/4

# Answer
> 6 votes
# Charcoal, 117 bytes

```
ＮθＮηＮζＮε≧×εθ≧×ηζ≧×ηε≔⁰ηＷ‹Ｌυ¹⁶«≔⟦⟧δＦ…·±ηηＦ…·±ηηＦ¬›ΣＸ⟦κλ⟧²ηＦ…·÷⁺θκε±÷⁺θκ±εＦ…·÷⁺ζλε±÷⁺ζλ±εＦ¬№δ⟦νξ⟧⊞δ⟦νξ⟧Ｆ¬№υＬδ⊞υＬδ≦⊕η»Ｉυ

```

Try it online! Link is to verbose version of code. Takes input as numerator denominator numerator denominator. Explanation:

```
ＮθＮηＮζＮε

```

Input the co-ordinates.

```
≧×εθ≧×ηζ≧×ηε

```

Increase the scale of the grid so that the gridlines are drawn at intervals given by the product of the denominators.

```
≔⁰η

```

Start enumerating circles with radius \\$ \sqrt h + ε \\$.

```
Ｗ‹Ｌυ¹⁶«

```

Repeat until 16 box counts have been found.

```
≔⟦⟧δ

```

Start with an empty list of boxes.

```
Ｆ…·±ηηＦ…·±ηη

```

Search points with a distance of up to and including \\$ h \\$ both horizontally and vertically.

```
Ｆ¬›ΣＸ⟦κλ⟧²η

```

Skip points whose distance from the desired point is greater than \\$ h \\$.

```
Ｆ…·÷⁺θκε±÷⁺θκ±εＦ…·÷⁺ζλε±÷⁺ζλ±ε

```

Consider all boxes touching this point.

```
Ｆ¬№δ⟦νξ⟧⊞δ⟦νξ⟧

```

Add the box to the list of boxes if it's not already present.

```
Ｆ¬№υＬδ⊞υＬδ

```

Add the count of boxes to the list of box counts if it's not already present.

```
≦⊕η

```

Move on to the next radius.

```
»Ｉυ

```

Print all of the box counts found.

# Answer
> 2 votes
# Perl 5, 225 bytes

```
sub f{my($x,$y,@a,@r,%b,$n,$i)=(@_,map{[cos,sin],[-cos,sin],[cos,-sin],[-cos,-sin]}map$_/12.566,0..720);while(@r<16){$n+=2e-3;$b{int$x+$n*$$_[0]+1e4,int$y+$n*$$_[1]+1e4}++for@a;$b=keys%b;$i=0,push@r,$b if$b>$r[-1]&&$i++>1}@r}

```

Try it online!

All brawn and no brain, but the 5 given tests passes in about 11 seconds at link above. It's easy to find new tests that will fail. The function f starts at the given input (x,y) and circles around in ever wider circles counting boxes it falls into. To be (almost) sure it found all boxes it needs two rounds for a new number of boxes to be registered into the return array @r. This solution is bound to have floating point "rounding errors" and "over- or understepping" when the radius is increased. To solve this properly I'd try to sort the distances of the edges of the close by boxes, but I'm too lazy to even think about that now.

```
sub f{
  my($x,$y,@a,@r,%b,$n,$i)=
    ( @_, map {[cos,sin],[-cos,sin],
               [cos,-sin],[-cos,-sin]}
          map $_/12.566, 0..720 );     #12.566 ~ 4*π
  while(@r<16){                        #repeat until 16 elems found
    $n+=2e-3;                          #increase radius
    $b{ int$x+$n*$$_[0]+1e4,           #keys of dict b contains found boxes
        int$y+$n*$$_[1]+1e4 }++        #+1e4 to avoid rounding up for x<0 or y<0
      for @a;                          #for all angles tested
    $b=keys%b;                         #b = number of boxes so far
    $i=0, push@r,$b                    #register b in solution if
      if !@r || $b > $r[-1] && $i++ > 1#it's > last number and if it's
                                       #found at least twice
  }
  @r                                   #return the 16 counts found
}

```

# Answer
> 2 votes
## Javascript, 199 bytes

My first code golf in a long time!

I originally started with a brute force solution, but couldn't get the step sizes small enough to have it produce the correct answers in a timely manner. So here's a more elegant solution that iterates points in a similar fashion to Zaelin's answer.

```
(x,y)=>{b={0:1};g=w=>b[d=parseInt(w*1e7)]=1+(b[d]|0);for(u=x%1-9;++u<9;){g(u*u);for(v=y%1-9;++v<9;)g(u*u+v*v)||u+1<9||g(v*v)}s=0;return Object.keys(b).sort((a,b)=>a-b).map(v=>(s+=b[v])).slice(0,16)}

```

Try it online!

### Ungolfed

```
(x, y) => {
  b = { 0: 1 };             // initialize a map for the lengths
  g = (w) => {              // function g is used to add to the map
    d = parseInt(w * 1e7);  // avoid floating point rounding errors
    b[d] = 1 + (b[d] | 0);  // increment point with length d
  }
  for (u = (x % 1) - 9; ++u < 9; ) {    //loop over "u" coordinates
    g(u * u);                           // add horizontal line
    for (v = (y % 1) - 9; ++v < 9; )    // loop over "v" coords
      g(u * u + v * v);                 // add corner
      (u + 1 < 9) || g(v * v);          // add vertical line (but only once per above for loop)
  }
  s = 0;                        // sum of circles up to this point
  return Object.keys(b)
    .sort((a, b) => a - b)
    .map((v) => (s += b[v]))    // aggregate number of circles visited
    .slice(0, 16);        // first 16 terms only
};

```

It relies on the fact that every new vertical, horizontal and corner node found represents exactly one new grid square found. Note that the x=0 or y=0 cases do not have to be treated specially, it just means that we hit a node and a vertical/horizontal line at the same time, which represents the multiple new grid squares hit.

# Answer
> 2 votes
# Vyxal, 15 bytes

```
9:NṡvJΠ$v∆dsĠ@¦

```

Try it Online!

Mostly a port of Zaelin Goodwin's Powershell answer, go look at that if you want to understand why this works. Outputs more than the first 16 terms, although beyond that not all terms may be accurate.

```
   ṡ            # Range from
9               # 9 to
 :N             # -9
    vJ          # Append x and y to two copies of that
      Π         # Take the cartesian product
       $v∆d     # Distance between each point and the input
           s    # Sort
            Ġ@  # Take lengths of runs of identical items
              ¦ # Cumulative sum

```

---
Tags: code-golf, geometry, combinatorics, grid
---


# Question
Title: What's the character limit of this text field?
Someone I know has no coding experience, but has proposed an algorithm\* to determine the character limit of text fields they find online. They copy a string containing the numbers from 1 to 1,000 inclusive, not separated in any way, and they read the last few digits it displays.

For example, after pasting, they might see

`...5645745845`

From here, they can figure out the character limit.

They've got two problems with this approach. One, it's a little hard to determine where the discrete numbers are in the string. (The last whole number displayed here is `458`, and the final two digits would have been followed by `9` if the text field allowed one more character.)

Two, the math is a little tricky even when that character has been identified. It's easy with single digits. For instance, if the last whole number were `5`, the limit would be `5` characters. With double digits it's a little harder. If the last whole number were `13` followed by the `1` of `14`, the full field would display `123456789101112131` for a limit of `18` characters.

They've managed to get a script that copies the last 10 digits the text field displays, or as many as the field holds if the field can hold less than 10. They'd like to feed that into another script that returns the field's length limit.

Additional test cases:

```
'' -> 0
'1' -> 1
'12' -> 2
'7891011121' -> 16
'1191201211' -> 256
'5645745845' -> 1268

```

Here are some examples of invalid inputs, incidentally:

```
'0'
'121'
'1211'

```

---

* Possibly in jest :)

# Answer
> 6 votes
# Excel (ms365)

**1)** Recursion with `LAMBDA()`, **74 bytes**:

Formula in `B1`:

```
=LET(x,LAMBDA(y,n,s,IFERROR(FIND(A1,s),y(y,n+1,s&n))),x(x,1,""))+LEN(A1)-1

```

**Note**: Due to the limitations within Excel this may return an error above a certain amount of recursive lambda calls.

---

**2)** Concatenating with `ROW()`, **39 bytes**:

I did explicitly want to stay away from using a concatenated string from any arbitrary range of numbers for this challenge. If one is okay with this concept then try:

```
 =FIND(A1,CONCAT(ROW(1:8468)))+LEN(A1)-1

```

Here I found that concatenating `ROW(1:8468)` seems to be Excel's (or rather `CONCAT()`'s) limit.

---

**3)** Overcome Excel's limits using `PY()`, **87 bytes**:

To overcome these limits of function within Excel, we could use the new `PY()` function:

```
=PY(
    ''.join(map(str,range(1,int(xl("A1")+1)))).find(str(xl("A1")))++len(str(xl("A1")))
)

```

**Note**: Python is not my forté, so I'm sure this can be golfed down. However, more importantly. Since `PY()` is executed on an external server there is a high chance of this code error out due to a "time-limit".

# Answer
> 5 votes
# Vyxal, 50 bitsv2, 6.25 bytes

```
⌊ɾṅḟ?L+

```

Try it Online!

Bitstring:

```
11001011010011010000000111000101111000110100000010

```

Times out for very large inputs because it needs to generate a range between 1 and whatever number represented by the input.

## Explained

```
⌊ɾṅḟ?L+
⌊ɾ       # The range [1, input]
  ṅ      # Joined into a single string.
   ḟ     # Find the index of the input in that string
    ?L+  # And add the length of the input to that

```

Created with the help of Luminespire.

# Answer
> 5 votes
# JavaScript (Node.js), 43 bytes

```
x=>~(g=s=>~s.indexOf(x,1)||g(s+i++))(x,i=1)

```

Try it online!

Using range, fail `11` (expect 13, get 1)

# JavaScript (Node.js), 49 bytes

```
x=>~(g=s=>~s.search(x)||g(s+ ++i))(i='')+x.length

```

Try it online!

-4 from Arnauld

Not using the 10

# Answer
> 5 votes
# 05AB1E, 7 bytes

```
LJIkIg+

```

Times out for larger inputs. Add a leading  (push 1000) to speed it up.

Try it online or verify all test cases.

**Explanation:**

```
L        # Push a list in the range [1, (implicit) input-integer]
 J       # Join it together to a single string
  Ik     # Pop and push the (0-based) index of the input
    Ig+  # Add the length of the input
         # (after which the result is output implicitly)

```

# Answer
> 5 votes
# Ruby, ~~34~~ 30 bytes

```
->i{[*1..1e3]*''=~/(?<=#{i})/}

```

Try it online!

*Thanks to @Neil for saving 1 Byte by removing useless + in regexp*

Regexp /(?\<=#{i})+/ finds index next to input in the constructed string `[*1..1e3]*''` by using a look behind.

# Answer
> 4 votes
# Perl 5 (`-p`), 27 bytes

```
(join"",1..1e3)=~$_;$_="@+"

```

Try it online!

# Answer
> 4 votes
# Haskell, ~~65~~ 63 bytes

*-2 bytes thanks to @AZTECCO*

```
n%h|l<-length n,n==take l h=l
n%(_:h)=1+n%h
f=(%([1..]>>=show))

```

Try it online!

# Answer
> 3 votes
# Retina 0.8.2, 38 bytes

```
^
1001$*1¶
\G1
$.`
r`\B\1.*¶(.*)
$1
\B

```

Try it online! Link includes test cases. Explanation:

```
^
1001$*1¶
\G1
$.`

```

Create a string of all the numbers from `0` to `1000` concatenated.

```
r`\B\1.*¶(.*)
$1

```

Remove everything after the first copy of the input, but don't delete the leading `0`. The `r` reverses the direction of processing, so the `(.*)` is matched first and the `\B` last.

```
\B

```

Count the pairs of adjacent digits, which is the same as the length excluding the leading `0`.

Alternative 38-byte version that works for arbitrary numbers given enough memory and processing power but is slower for inputs of four or more digits.

```
^
$'$*111¶
\G1
$.`
r`\B\1.*¶(.*)
$1
\B

```

Try it online! Link includes test cases. Explanation:

```
^
$'$*111¶
\G1
$.`

```

Create a string of all the numbers from `0` to the input plus `1` concatenated. (This is needed for the edge case of an empty input.)

```
r`\B\1.*¶(.*)
$1

```

Remove everything after the first copy of the input, but don't delete the leading `0`.

```
\B

```

Take the length excluding the leading `0`.

# Answer
> 3 votes
# APL+WIN, ~~35~~ 33 bytes

Two bytes saved thanks to Tbw

Prompts for string of digits:

```
↑(¯1+⍴s)+((s←,⎕)⍷n)/⍳⍴n←⊃,/⍕¨⍳1E3

```

Try it online! Thanks to Dyalog Classic

# Answer
> 3 votes
# Pip, 10 bytes

Semi-port of lyxal's Vyxal answer

```
J1,a~:Xa$)

```

Attempt This Online!

```
J1,a~:Xa$)
J1,a        # Range from 1 to input as string
    ~:Xa    # Match input as regex in range
        $)  # Return last index of first match

```

Created with the help of Luminespire.

# Answer
> 3 votes
# Charcoal, 10 bytes

```
Ｉ⁺Ｌθ⌕⭆φ⊕ιθ

```

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

```
      φ     Predefined variable `1000`
     ⭆      Map over implicit range and join
        ι   Current value
       ⊕    Incremented
    ⌕       Find index of
         θ  Input string
 ⁺          Plus
   θ        Input string
  Ｌ         Length
Ｉ           Cast to string
            Implicitly print

```

# Answer
> 2 votes
# APL (Dyalog Classic), 22 bytes

```
≢-1-(⊃∘⍸⍷∘(⊃,/⍕¨⍳1E3))

```

Try it online!

```
≢-1-(⊃∘⍸⍷∘(⊃,/⍕¨⍳1E3))  # tacit function
     ⊃∘⍸⍷∘               # index of first subsequence equal to input in
                 1E3    # 1000
                ⍳       # range
              ⍕¨       # toString each
            ,/          # concat reduce
          ⊃,/⍕¨⍳1E3    # '12345678910...'
 -1-                    # minus 1 (because a-1-c = a-(1-c) = ¯1+a+c in APL)
≢                       # length of input (this is one character;
                     # the code block does not display it correctly)

```

Created with the help of Luminespire.

# Answer
> 2 votes
# Python 3, 55 bytes

```
lambda s:"".join(map(str,range(1,1001))).find(s)+len(s)

```

This is a rather simple solution, but it works.

# Answer
> 1 votes
# Japt, 9 bytes

```
+A³õ ¬
aN

```

Try it

# Answer
> 0 votes
# JavaScript (Node.js), 57 bytes

```
x=>[...Array(1000).keys()].join('').indexOf(x)-1+x.length

```

Attempt This Online!

Constructs `"0123456789..."`, then finds the input in it.

# Answer
> 0 votes
# Scala 3, 41 bytes

```
s=>(1 to 1000).mkString.indexOf(s)+s.size

```

Attempt This Online!

# Answer
> 0 votes
# Uiua, 30 bytes

```
(⊏0+⧻:⊚⌕:/$"__"+1⇡1e3.|0;)=0⧻.

```

Test suite

I felt like adding another answer

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


title: How long is this string, really?

text:
# Question
Title: How long is this string, really?
In most programming languages, the string `Hello, World!` can be represented as `"Hello, World!"`. But if you want to represent `"Hello, World!"` you need to escape the double quotes with backslashes for `"\"Hello, World!\""`, and to represent *that* you also need to escape the backslashes resulting in `"\"\\\"Hello, World!\\\"\""`.

Your challenge is to, given a printable ASCII string that's been escaped multiple times (such as `"\"\\\"Hello, World!\\\"\""`, find how many characters it is when fully unescaped. Specifically, you should remove a single pair of enclosing `"` and replace `\\` with `\` and `\"` with `"`, until there are no more enclosing `"` left.

You can assume that the string will be syntactically valid - At all stages, as long as the string starts and ends with `"`, all other backslashes and double quotes will be properly escaped, and only `"` and `\` will be escaped. The input string will not be `"` at any level of escaping. If the string starts and ends with `"`, the last `"` cannot be escaped, so e.g. `"abc\"` won't occur.

This is , shortest wins!

## Testcases

```
e -> 1
"hello" -> 5
"\"\\" -> 2
a""b"c -> 6
"c\d+e -> 6
"\"\\\"Hello, World!\\\"\"" -> 13
"c\\\"d\"" -> 5
"\"\"" -> 0
"r\"\"" -> 3
"\"hello\"+" -> 8
"\"\\\"\\\\\\\"\\\\\\\\\\\\\\\"Hello\\\\\\\\\\\\\\\"\\\\\\\"\\\"\"" -> 5
"\\\\\"" -> 3
[""] -> 4

```

# Answer
> 7 votes
# JavaScript (Node.js), 41 bytes

```
f=x=>/^".*"$/.test(x)?f(eval(x)):x.length

```

Try it online!

Trivial

# Answer
> 6 votes
# Retina 0.8.2, 47 bytes

```
+`(?=.*"$)(^"(?!$)|\\(.)|(?!^)"$)(?<=^".*)
$2
.

```

Try it online! Link includes test cases. Explanation:

```
(?=.*"$)

```

Ensure the string ends with a `"` before making any replacements.

```
(^"(?!$)|\\(.)|(?!^)"$)

```

Replace a leading `"`, an escaped character or a trailing `"`, but not a lone `"`.

```
(?<=^".*)

```

Ensure that the string starts with a `"` before making any replacements.

```
$2

```

Unescape the character.

```
+`

```

Repeat until the string can't be unquoted further.

```
.

```

Get the length of the final string.

If `"` is excluded as being an unsupported input, then ten bytes can be saved by removing `(?!$)` and `(?!^)`.

# Answer
> 6 votes
# Jelly, 11 bytes

```
ŒV.ị=”"ȦƲ¿L

```

Try It Online!

-2 bytes thanks to Jonathan Allan

## Explanation

```
ŒV.ị=”"ȦƲ¿L    Main Link
  ------Ʋ      Link Grouping (see below)
         ¿     While
  .ị               the first and last (index at 0.5)
       Ȧ           are all
    =”"            equal to "
ŒV             Evaluate (Python)
          L    Length

```

The footer runs all tests and prints `1` for any correct answers. `Ỵœṣ“ -> ”$€Ç=V}ɗ/€` means "split on newlines, split each string on substrings equal to `" -> "`, then for each pair, check that the result of the main link on the left side equals the right side evaluated (to convert to a number)".

For the link grouping, `Ʋ` combines four links into a monad, so you'd think we'd need to use `$` to capture the fifth, but since `”"Ȧ` would be an LCC (a chain that begins with a nilad and only has monads and dyad-nilad/nilad-dyad pairs after it, so a chain with a constant result), it doesn't count that as a link and therefore keeps going one extra time. This is an important tip when understanding the link combining quicks as **all** of them do this and it is easy to miscount or misunderstand the grouping because it may be taking more links than you expect.

`ŒV.ị⁼⁾""Ʋ¿L` would also work where instead of `=”"Ȧ` to check that all are equal to `"`, we just check that it's equal to `['"', '"']`. This also makes the grouping a bit simpler because we don't have any potential LCCs so it just takes four links.

# Answer
> 5 votes
# Excel ms365, 138 bytes

Assuming input in `A1`:

```
=LET(x,LAMBDA(f,s,IF(s<"",s,f(f,IFNA(SUBSTITUTE(SUBSTITUTE(MID(s,XMATCH("""*""",s,2)+1,LEN(s)-2),"\\","\"),"\""",""""),LEN(s))))),x(x,A1))

```

It's a recursive LAMBDA that will keep calling itself untill no more starting+leading double quotes.

---

# Google Spreadsheets, 107 bytes

Again, assuming input in `A1`, applying the same recursive logic with a few slight changes making use of the regex-functions:

```
=LET(x,LAMBDA(f,s,IF(REGEXMATCH(s,""".*"""),f(f,REGEXREPLACE(s,"^""|""$|\\(\\|"")","$1")),LEN(s))),x(x,A1))

```

# Answer
> 3 votes
# Charcoal, ~~34~~ 33 bytes

```
Ｗ¬∨⌕θ"⌕⮌Φθλ"≔⪫⁻⪪✂θ¹±¹¦¹\\¦\¦\θＩＬθ

```

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

```
Ｗ¬∨⌕θ"⌕⮌Φθλ"

```

Repeat while the string starts with `"` and ends with a different `"`...

```
≔⪫⁻⪪✂θ¹±¹¦¹\\¦\¦\θ

```

... remove those `"`s, split the string on `\\`, remove any remaining `\`s, then join the string on `\`, thus unquoting the string.

```
ＩＬθ

```

Output the length of the final string.

(Yes I could use eval to save 14 bytes but that's boring.)

If `"` is excluded as being an unsupported input, then two bytes can be saved by replacing `Φθλ` with `θ`.

# Answer
> 3 votes
# Python, ~~51~~ 52 bytes

```
f=lambda s:f(eval(s))if'"'==s[-1:]==s[:1]else len(s)

```

Not complicated, but it works well.

**Explanation:**

Define a function f that takes an argument s:

```
f=lambda s:

```

If the string begins and ends with `"`, return the value of the function with backslashes evaluated:

```
f(eval(s))if'"'==s[-1:]==s[:1]

```

Otherwise, output the length of the string:

```
len(s)

```

Try it online!

# Answer
> 3 votes
# Perl 5 `-pl`, 45 bytes

```
s/\\(\\|")/$1/g while s/^"(.*)"$/$1/;$_=y///c

```

Try it online!

# Perl 5 `-pl`, 54 bytes

Handles the `"\"foo\\\""` testcase I proposed in the comments. If that's not a valid test case, then the shorter version above will suffice.

```
s/\\(\\|")/$1/g while s/^"(.*[^\\])"$/$1/;say;$_=y///c

```

Try it online!

# Answer
> 3 votes
# Python 3, ~~91~~90 bytes

```
f=lambda s:f(s[1:-1].replace('\\"','"').replace(r'\\','\\'))if'"'==s[-1:]==s[0]else len(s)

```

because `eval` is evil :P, with inspiration from Jakav

Try it online!

# Answer
> 2 votes
# QBASIC, 302 bytes

```
Q$ = CHR$(34): LINE INPUT T$: DO WHILE LEFT$(T$, 1) + RIGHT$(T$, 1) = Q$ + Q$: U$ = MID$(T$, 2, LEN(T$) - 2): T$ = "": C$ = "": FOR J = 1 TO LEN(U$): C$ = C$ + MID$(U$, J, 1): B = -(C$ <> "\"): T$ = T$ + RIGHT$(C$, B * ((INSTR("\\" + Q$, C$) > 0) + 2)): C$ = LEFT$(C$, 1 - B): NEXT: LOOP: PRINT LEN(T$)

```

A bit of nostalgia...

**Explanation:**

```
'Set quote mark because QBASIC doesn't have string escaping
'then get string
Q$ = CHR$(34)
LINE INPUT T$
'Process the string while it starts and ends with quotes
DO WHILE LEFT$(T$, 1) + RIGHT$(T$, 1) = Q$ + Q$
    'Strip enclosing quotes, assign to a temporary variable,
    'prepare to rebuild the original string,
    'and prepare to track current character(s)
    U$ = MID$(T$, 2, LEN(T$) - 2)
    T$ = ""
    C$ = ""
    'Process string character by character.
    FOR J = 1 TO LEN(U$)
        'Add current character to current status
        C$ = C$ + MID$(U$, J, 1)
        'QBASIC boolean ops return -1 for true, 0 for false,
        'so set B to 0 if current character is an escape char, to 1 otherwise.
        B = -(C$ <> "\")
        'Add current character to string if not an escape char,
        'de-escaping if appropriate
        T$ = T$ + RIGHT$(C$, B * ((INSTR("\\" + Q$, C$) > 0) + 2))
       'Clear current character unless it's an escape char
        C$ = LEFT$(C$, 1 - B)
    NEXT
LOOP
PRINT LEN(T$)

```

# Answer
> 1 votes
# 05AB1E, 10 bytes

```
Δ¬'"Qi.E]g

```

Try it online or verify all test cases. (Note: in the single TIO, the input is wrapped within `"""`-quotes to always have a string input.)

**Explanation:**

```
Δ         # Loop until the result no longer changes:
 ¬        #  Push its first character (without popping the string)
  '"Qi   '#  If it's a double quote:
      .E  #   Evaluate the string as Elixir code
]         # Close both the if-statement and changes-loop
 g        # Pop and push the length of the reduced string
          # (which is output implicitly as result)

```

# Answer
> 1 votes
# Pyth, 20 bytes

```
L?&b&qhbNqebNyvblbyw

```

Try it online!

Same approach as Jakav's Python solution.

# Answer
> 1 votes
# Vyxal `l`, 70 bitsv2, 8.75 bytes

```
Sλh\"=ßE;Ẋ

```

Try it Online!

Bitstring:

```
0110001110110011010000001101101101100000011010011000101001000111010000

```

Port of 05ab1e except i had to add a "stringify" at the start for the final case

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


title: The worst spaghetti code

text:
# Question
Title: The worst spaghetti code
# Objective

Write a full program that works exactly like the flow chart below.

Each output, which is an integer, shall be through `stdout`, followed by a line feed.

Each input shall be a line of string fed through `stdin`, and shall be judged to a predicate you choose for branching. The same predicate must be used for all branches.

The predicate must be able to judge every possible input, and must not be always truthy nor always falsy. Possible choices of the predicate include:

* Truthy if the inputted string is nonempty
* Truthy if the inputted string consists of whitespaces
* Truthy if the inputted string can be parsed into an integer
* Truthy if the inputted string is exactly `Hello, world!`

# The flow chart

# Rule

Your submission need not to follow the definition above exactly, as long as the visible side-effects are the same. This rule is present to aid functional languages.

# Ungolfed solution

## Haskell

Truthy if the string is empty.

```
main :: IO ()
main = procedure1 where
    genProcedure :: Int -> IO () -> IO () -> IO ()
    genProcedure output branch1 branch2 = do
        print output
        str <- getLine
        if null str
            then branch1
            else branch2
    procedure1, procedure2, procedure3 :: IO ()
    procedure1 = genProcedure 1 procedure3 procedure2
    procedure2 = genProcedure 2 procedure1 procedure3
    procedure3 = genProcedure 3 procedure2 (pure ())

```

# Answer
# Jelly, ~~15~~ 13 bytes

```
‘Ṅ+%3ßḊo?ɗɠẸ¤

```

Try it online!

A full program that takes no arguments but reads from STDIN. The predicate function checks for a non-empty line. As required, the intermediate outputs are sent to STDOUT.

## Explanation

```
‘                | Increment by 1
 Ṅ               | Output to STDOUT with a trailing newline
         ɗɠẸ¤    | Following as a dyad with the right argument (y) as 1 if the next line from STDIN is non-empty and 0 if empty, and the link’s argument + 1 as the left argument
  +              |   x + y
   %3            |   Mod 3
     ßḊṪ?        |   If this or the input is truthy, call the link recursively; if falsy, remove the remaining value so we’re left with an empty list

```
> 4 votes

# Answer
# QBasic, 58 bytes

```
1?x+1
LINE INPUT s$
x=x+1+(s$>"")*(2+(x=0)*3)
IF x<3GOTO 1

```

Empty inputs are falsey; nonempty inputs are truthy. You can type the program in and run it at Archive.org.

Sadly, storing the program state in a variable `x` is much cheaper than doing actual control flow with gotos. A direct translation of the flowchart comes in at 95 bytes:

```
1?1
LINE INPUT s$
IF""<s$GOTO 3
2?2
LINE INPUT s$
IF""<s$GOTO 1
3?3
LINE INPUT s$
IF""<s$GOTO 2

```
> 11 votes

# Answer
# PARI/GP, 52 bytes

Strictly speaking, this is not a valid solution, because it can't handle some special inputs like `quit`. But this is the best I can do.

```
my(n=0);while(n<3,print(n++);iferr(input,e,n=n++%3))

```

Attempt This Online!

Valid PARI/GP expressions (e.g. `o_o`) are falsy. Other strings (e.g. `*_*`) are truthy.

PARI/GP doesn't have a way to read an arbitrary string from stdin. The function `input` always parses the input as a PARI/GP expression. So I use `iferr` to check if the input is valid.

I also need to declare `n` as a local variable, otherwise the user may input a string like `n=9` and change the value of `n`.

However, there's no way to stop the user from inputting something like `quit`, which will quit the program; or `input`, which prompts for another input; or `print("something")`, which prints something. It's just impossible to handle these cases.
> 5 votes

# Answer
# Charcoal, 22 bytes

```
≔³θＷθ«Ｉ⁻⁴θＤ⎚≔⎇Ｓ⊕﹪θ³⊖θθ

```

Try it online! Link is to verbose version of code. Uses nonempty as the predicate. Explanation:

```
≔³θ

```

Numbering the states in reverse to output values, we start in state `3`.

```
Ｗθ«

```

Repeat until state `0` (END) is reached.

```
Ｉ⁻⁴θＤ⎚

```

Generate the correct output value.

```
≔⎇Ｓ⊕﹪θ³⊖θθ

```

If the input is not empty, then go the the previous state (increment the internal value, but `3` becomes `1`), otherwise go to the next state (decrement the internal value).
> 4 votes

# Answer
# Javascript, 38 bytes

```
f=(n=1)=>(n+=!prompt(n)*4)-3&&f(n%3+1)
```

Empty string as true
> 3 votes

# Answer
# Vyxal 3, 19 bytes

```
1{:|Ọ"ᵈḄᵇ“f2Ẇ0pi?ȯi

```

Try it Online!

A single number is all you need

Truthy is defined as standard vyxal truth

## Explained

```
1{:|Ọ"ᵈḄᵇ“f2Ẇ0pi?ȯi
1                    # Start with 1 on the stack. This is the initial state
 {:|                 # While the top of the stack is truthy:
    Ọ                #   Print it without popping. This prints the current state
     "ᵈḄᵇ“           #   Push the number 233101 to the stack
          f2Ẇ        # Flatten it and divide it into chunks of size 2. This is the state map. The first number in a pair is the state to go to when false input. The second number is the true jump.
             0p      #   Prepend a 0 to indicate a halt state
               i     #   Retrieve the pair corresponding to the current state
                ?ȯi  #   And get the next state based on the truthiness of the input

```

Created with the help of Luminespire.
> 2 votes

# Answer
# brainfuck, 111 bytes

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

```

Try it online!

An empty string (followed by a line feed) is truthy, any other input is falsy.
> 1 votes

# Answer
# Perl, 123 bytes

```
I:print 1;$i=<STDIN>;chomp$i;goto K if$i;J:print 2;$i=<STDIN>;chomp$i;goto I if$i;K:print 3;$i=<STDIN>;chomp$i;goto J if$i;

```

Attempt This Online!

The predicate here is Perl truth.
> 1 votes

# Answer
# Rust, 136 bytes

```
fn main(){let mut c=1;while 4>c{print!("{c}
");let y=&mut "".into();std::io::stdin().read_line(y);c+=if "
"!=y{if c==1{c=4}-1}else{1}}}

```

Expanded (I also replaced newlines inside string literals by regular `\n`):

fn main(){
    let mut c=1;
    while 4>c {
        print!("{c}\n");
        let y=&mut "".into();
        std::io::stdin().read_line(y);
        c+=if "\n"!=y {
            if c==1 { c = 4 }
            -1

        } else {
            1
        }
    }
}
```
</code></pre>
> 1 votes

# Answer
# APL(NARS), 40 chars

```
P
⎕←1⋄→3×⍳''≡⍞
⎕←2⋄→1×⍳''≡⍞
⎕←3⋄→2×⍳''≡⍞

```

1+3\*12+3=40 Predicate would be here "True if the input line is empty"
> 1 votes

# Answer
# Python 3.8, 108 bytes

```
p=print
i=input
def a():p(1);c()if i()else b()
def b():p(2);a()if i()else c()
def c():
 p(3)
 if i():b()
a()

```

Try it online!

The predicate checking the input is truthy if the inputted string is nonempty.
> 1 votes

# Answer
# C (GNU Extension), 311 Bytes

```
#include <stdio.h>
#define G goto
int main(){int a,b,c,d,e,f,i;char*h="Hello, world!";void*j[3][2]={{&&x,&&y},{&&y,&&w},{&&z,&&x}};w:i=0;q:a=e=f=1;b=c=d=0;G L;o:if(c){puts(a+e+f?"1":"0");G*j[i][a||e||f];}a=a?b>47&&b<58:0;e=e?b==h[d-1]:0;f=f?b==32:0;L:b=getchar();d++;c=b==10;G o;z:return 0;y:i=2;G q;x:i=1;G q;}

```

This code (ab)uses the GNU extension Labels as Values and gotos.

Things seen as truthy:

* A sequence of digits (allows 0000000...)
* The exact string "Hello, world!"
* A sequence of space
* An empty string

---

## Explained

```
#include <stdio.h>

//to save space
#define G goto

int main() {
    //a stores if the input is an integer
    int a;
    //b stores the char we currently act upon
    int b;
    //c stores if the end of the current input line has been reached
    int c;
    //d counts the number of chars in the current input, used when testing for hello world
    int d;
    //e stores if the input is the hello world
    int e;
    //f stores if the input consists of space
    int f;
    //i stores the current state, goes from 0 to 2
    int i;
    //this is used for comparisons to find out if the input is hello world
    char *h = "Hello, world!";
    //this is a jump table, it is used to emulate something like a switch using gotos
    void *j[3][2] = {
        {&&x, &&y}, //these are where one can go from state 0 using what result
        {&&y, &&w}, //go from state 1
        {&&z, &&x}  //go from state 2
    };

    //the labels w x y z are the different states
    //w is state 0, the beginning
    //x is state 1
    //y is state 2
    //z is state 3, the end state

    //this is state 0
    w:
    i = 0;

    //this resets all the variables to their default values
    q:
    a = e = f = 1; //at the beginning of the line parsing, we assume all the things to be true as we later test if they are wrong
    b = c = d = 0;
    G L;

    //this are two things combined: the output in case the end of the line has been reached & the check for all the different things we consider truthy
    o:
    if(c){
        //this is the output, the shorthand if is true in case any of them are non zero
        puts(a + e + f ? "1" : "0");
        //this selects the next state to jump to, based on the current state i and the result, and does the goto
        G *j[i][a || e || f];
    }
    //the way these assignments work is that we only test if the condition still is true if it still is true. In case it ever is false we do not try to test again
    a = a ? b > 47 && b < 58 : 0; //this tests for digits, assumes ascii as digits are from 48 to 57
    e = e ? b == h[d-1] : 0; //this tests for hello world, in case the input looks like hello world but goes on with the exact (random) data as stored in the compiled file this can cause a buffer overrun!
    f = f ? b == 32 : 0; //this tests for space, assumes ascii where ' ' is 32

    //this gets the next character in the line
    L:
    b = getchar();
    d++;
    c = b == 10; //this tests for end of line by looking for '\n' which, assuming ascii, is 10
    G o;

    //this is state 3, the end
    z:
    return 0;

    //this is state 2
    y:
    i = 2;
    G q;

    //this is state 1
    x:
    i = 1;
    G q;
}

```
> 0 votes

---
Tags: code-golf, interactive
---


title: Test whether a sequence is bitonic

text:
# Question
Title: Test whether a sequence is bitonic
You know what a *mono*tonic sequence is: each element is bigger than its predecessor (monotonically rising) or as its successor (monotonically falling).

*Bi*tonic means you have two arms of the sequence, one monotonically rising, the other falling.

For example, `1,3,5,7,6,4,2` is bitonic (rising until 7, then falling until the end; `99,4,8,16` is as well (falling until 4, then rising until the end).

**The task is to test, whether a sequence is bitonic** (without being monotonic), with your code being as short as possible in your language of choice.

**Input**: A list of positive integer numbers without duplicates in a form that suits your language.

**Output**: Truthy/falsy

**Test data**:

```
True:
1,3,5,7,6,4,2
99,4,8,16
100000,10000,1000,100,10,1,11,111,1111,11111,111111
2,1,3,4,5,6

False:
1,2,3,4,5,6,7
7,6,5,4,3,2,1
1,4,7,6,2,3,5
99,88,66,77,55,44,33,22,11
1,9,2,8,3,7,4,6,5

```

# Answer
# Haskell + hgl, 10 bytes

```
eL2<gr<pac

```

*(Doesn't work on ato since ato is slightly out of date)*

## Explanation

* `pac` gets the contour of a list, i.e. the comparisons between consecutive elements
* `gr` group them into sections of equal elements.
* `eL2` check if there are exactly two groups

## Reflection

A couple of thoughts here

* I think there might be use in having a function which counts the number of groups. Although I don't think it would help this particular answer.
* `pWK` gets all partitions where each part satisfies a predicate. A version of this could be `ay eL2<pWK(lq<pac)`, which is much longer although there are a bunch of ways to improve this approach.
    + `lq<pac` determines if a list is monotonic, that is useful. We already have functions for the specific monotonicities, this would be a nice addtion.
    + Versions of a lot of the partitioning functions that are specific to partition into two parts would be useful, since that is the most basic non-trivial type of partition. A version of `pWK` which is specific to size 2 would change this from `ay eL2`, checking if there is something of size 2, to `ø`, checking if the result is null.
> 5 votes

# Answer
# Jelly, 6 bytes

```
IṠITL’

```

A monadic Link that accepts a list of different integers and yields `0` (falsey) if it is bitonic or a non-zero integer (truthy) if not.

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

### How?

The count of direction changes must be exactly one, so count them and subtract one to give `0` iff the input is bitonic.

```
IṠITL’ - Link: list, A       e.g. [5, 4, 3, 6, 7, 2]
I      - forward differences      [ -1,-1, 3, 1,-5]
 Ṡ     - signs                    [ -1,-1, 1, 1,-1]
  I    - forward differences      [   0, 2, 0,-2]
   T   - truthy indices           [      2,    4]
    L  - length                   2
     ’ - decrement                1 (truthy: not bitonic)

```
> 5 votes

# Answer
# , 31 bytes

```
\(x,`?`=diff)sum(!!?sign(?x))-1

```

Attempt This Online!

A function taking a vector of integers and returning falsy for bitonic and truthy for non-bitonic. Takes some inspiration from @JonathanAllan’s Jelly answer.
> 4 votes

# Answer
# APL (Dyalog Classic), ~~13~~ 11 bytes

-2 bytes thanks to att.

```
1=1⊥2≠/2>/⊢

```

Try it online!

```
1=1⊥2≠/2>/⊢
       2>/⊢  ⍝ compare successive terms with > (direction of deltas)
    2≠/      ⍝ compare successive terms with ≠ (changes in direction)
  1⊥         ⍝ sum (# of changes in direction)
1=           ⍝ equal to 1

```

Created with the help of Luminespire.
> 3 votes

# Answer
# Jelly, 7 bytes

```
IṠŒgL=2

```

Try it online!

## Explanation

```
I       | Increments
 Ṡ      | Signs
  Œg    | Group consecutive equal values
    L=2 | Length is equal to two?

```
> 3 votes

# Answer
# Google Sheets, 80 bytes

```
=regexmatch(join(,sort((D1:Y1<E1:1)+2*(D1:Y1>E1:1)*(E1:1>0))),"^(1+2+|2+1+)0*$")

```

Put the number sequence in cells `D1:Z1` and the formula in cell `A1`.

Simple Boolean arithmetic and string matching. Makes just one pass through the array. The `sort()` does not actually sort anything — its purpose is to enable array processing.

Expects that the last number is in or before column `Z`. If you need more columns, replace `:1` with `:Z1` (3 bytes) and insert columns before `Y` as necessary.
> 3 votes

# Answer
# Ruby, 36 bytes

```
->a,*l{l.chunk{|x|a<=>a=x}.count==2}

```

Try it online!

Probably the same idea as @JonathanAllan’s Jelly answer.
> 3 votes

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

This is implementation-dependent, as it assumes that the `sort()` algorithm compares the items by pairs from left to right, at least while \\$x\ge0\\$ (after which it no longer matters because we already know that the sequence is not bitonic anyway).

Returns \\$0\\$ or \\$1\\$.

```
a=>a.sort(s=(a,b)=>x-=s!=(s=a>b),x=2)|!x

```

Try it online!
> 3 votes

# Answer
# Perl 5 `-p`, 43 bytes

```
s/\d+ ?/$&>$'||B/ge;chop;$_=/^(B+1+|1+B+)$/

```

Try it online!
> 3 votes

# Answer
# Julia 1.0, 29 bytes

```
!L=sum((~=diff)(~L.>0).^2)==1

```

Try it online!

based on multiple other answers
> 3 votes

# Answer
# 05AB1E, 6 bytes

```
ü.SÔg<

```

Outputs an 05AB1E truthy/falsey value, so `1` if truthy and `0` or a positive integer if falsey.

Try it online or verify all test cases.

**Explanation:**

```
ü       # For each overlapping pair of the (implicit) input-list:
 .S     #  Compare them: 1 if a>b; 0 if a==b; -1 if a<b
   Ô    # Connected uniquify this list
    g   # Pop and push the length
     <  # Decrease it by 1
        # (after which the result is output implicitly)

```
> 2 votes

# Answer
# MathGolf, 7 bytes

```
│mσ│┘Σ┴

```

Try it online.

**Explanation:**

```
│        # Get the forward differences of the (implicit) input-list
 m       # Map over each integer:
  σ      #  Get its sign
   │     # Get the forward differences of this list again
    ┘    # Check for each that they're NOT equal to 0
     Σ   # Sum the amount of non-zero values together
      ┴  # Check whether this is equal to 1
         # (after which this is output implicitly as result)

```
> 2 votes

# Answer
# APL+WIN, 15 bytes

Prompts for input.

```
1=+/2=|2-/×2-/⎕

```

Try it online! Thanks to Dyalog Classic
> 2 votes

# Answer
# Raku, 29 bytes

```
($_ Z-.skip)>>.sign.squish==2

```

Attempt This Online!

Zip-subtract the sequence with itself-skipped, i.e., take the differences and further take the sign of those differences. Lastly "squish" the signs, which squeezes consecutive duplicates into one, i.e., uniq of UNIX; if we have 2 unique signs at the end, sequence is bitonic.
> 2 votes

# Answer
# Japt, 6 bytes

Outputs `0` for `true` or a non-zero integer for `false`.

```
äÎòÎÊÍ

```

Try it
> 2 votes

# Answer
# C (clang), 62 bytes

```
i;f(*l,z){i=*l=*l>l[1];return--z-1?f(l+1,z)+(i%2-*l&&++i):-1;}

```

Try it online!

Return false if bitonic , true otherwise
> 2 votes

# Answer
# Uiua, 14 bytes

```
=1/+≡/≠◫2≡/>◫2

```

Gets windows, compares, gets windows, counts changes in comparisons and checks if the number of changes is exactly 1.

Test pad
> 2 votes

# Answer
# Retina 0.8.2, 39 bytes

```
\d+
$*
(?<=(1+)),1\1
;
1

^,+;+$|^;+,+$

```

Try it online! Link includes test cases. Explanation: Port of @NickKennedy's Jelly answer.

```
\d+
$*

```

Convert the integers to unary.

```
(?<=(1+)),1\1
;

```

Replace the comma with a semicolon for all ascending pairs. (The lookbehind both allows the "matches" to overlap and being atomic finds the start of the unary value without needing a word boundary.)

```
1

```

Delete any remaining `1`s.

```
^,+;+$|^;+,+$

```

Check whether the sequence is bitonic.
> 1 votes

# Answer
# Charcoal, 23 bytes

```
≔ＥΦθκ›ι§θκθ⁼№θ§θ⁰⌕θ¬§θ⁰

```

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

```
≔ＥΦθκ›ι§θκθ

```

Create a list of `1`s and `0`s corresponding to whether the overlapping pairs of integers are ascending or descending.

```
⁼№θ§θ⁰⌕θ¬§θ⁰

```

Check that the count of occurrences of the first element is also the start of the second run of identical elements; if there is only one run then there is no start of the second run while if there are more than two runs then there are too many of the first element to fit before the second run.
> 1 votes

# Answer
# Clojure, 84 bytes

```
#(=(sort(mapcat set(partition-by +(for[i(map -(rest %)%)](Long/signum i)))))'(-1 1))

```

Annoyingly `partition-all` is a long function name, and the static function call `Long/signum` (which outputs -1, 0 or 1) cannot be directly composed with `-` using `comp`.

Try it online!
> 1 votes

# Answer
# APL(NARS), 12 chars

```
1=≢⍸∼2=/2</⎕

```

This above it seems ok for all test how to use it:

```
  1=≢⍸∼2=/2</⎕
⎕:
  1 9 2 8 3 7 4 6 5
0

```

test but the char "∼" in Tio is not the same char of the answer.

https://tio.run/##PY09DsIwDIX3nOWh4rT5qUQPgATiDJVQWSrBysIIZQCxcAFOwXlykfCSAFH89Gx/tvvDONse@3G/i@H@XK/C@VEruuWGTlSYLkOULlxf4fY@6a7Si4rdyHoclKCGgYNFA60G1bY0HmLpZZ4e5K9JGBBI@jmKfFU4pZF2Ntyad0D/Mjjm6ZJhXrMuud/k64ky5b73sIQdDEGSRMkWuCXoiTqOcdEH
> 1 votes

# Answer
# Desmos, 42 bytes

```
f(L)=d(d(L))^2.total-1
d(L)=sgn(L[2...]-L)

```

Try It On Desmos!

Try It On Desmos! - Prettified

Returns `0` if bitonic or a non-zero integer otherwise.
> 1 votes

# Answer
# Swift, 143 bytes

Minimal version:

```
func b(_ a:[Int])->Bool{var c=[Int]();for i in 0..<a.count-1{let s=(a[i+1]-a[i]).signum();if s != 0 && s != c.last{c+=[s]}};return c.count==2}

```

Verbose version:

```
func bitonic3(_ array: [Int]) -> Bool {
    let a = array
    var changes: [Int] = []
    var reducedChanges: [Int] = []

    for i in 0 ..< a.count - 1 {
        let sign = (a[i+1] - a[i]).signum()
        if sign != 0 {
            changes.append(sign)
        }
    }

    for i in 0 ..< changes.count {
        let value = changes[i]
        if reducedChanges.last != value {
            reducedChanges.append(value)
        }
    }

    if reducedChanges.count != 2 {
        return false
    }

    return true
}

```
> 1 votes

# Answer
# Nekomata \+ `-e`, 4 bytes

```
∆±ĉđ

```

Attempt This Online!

```
∆±ĉđ
∆       Delta; differences between consecutive elements
 ±      Sign
  ĉ     Split into chunks of identical elements
   đ    Unpair; check if length is 2

```
> 1 votes

---
Tags: code-golf, math, sequence, decision-problem
---


title: Where's the 0xBEEF?

text:
# Question
Title: Where's the 0xBEEF?
This challenge was inspired by this Wendy's commercial from 1984.

*Illustration by T S Rogers*

Your task is to find a hexadecimal 0xBEEF on a binary bun.

The 'beef' consists of the following pattern:

```
1 0 1 1  (0xB)
1 1 1 0  (0xE)
1 1 1 0  (0xE)
1 1 1 1  (0xF)

```

And the 'bun' consists of a 12x12 binary matrix, such as:

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

```

### Input

Your program or function will take the binary matrix as input. The matrix format is very flexible, but it must be clearly described in your answer.

For instance:

* a single binary string, with or without separators between the rows:

`"111001111110 110100100000..."`

or:

`"111001111110110100100000..."`
* an array of binary strings:

`["111001111110", "110100100000", ...]`
* an array of numbers (each number describing a row once converted back to binary and left-padded with zeros):

`[3710, 3360, ...]`

### Output

The coordinates `(X, Y)` of the 'beef', `(0, 0)` being the top left corner of the bun.

Alternatively, you may use 1-based coordinates (but not a mix of both formats, like 0-based for X and 1-based for Y).

For the above example, the expected answer is `(3, 4)` (0-based) or `(4, 5)` (1-based):

```
   00 01 02 03 04 05 06 07 08 09 10 11
00  1  1  1  0  0  1  1  1  1  1  1  0
01  1  1  0  1  0  0  1  0  0  0  0  0
02  0  1  0  0  0  1  1  1  1  1  0  1
03  1  0  0  1  0  0  1  0  0  1  0  0
04  1  0  0 [1  0  1  1] 0  0  1  1  1
05  1  1  1 [1  1  1  0] 0  0  0  1  0
06  1  1  0 [1  1  1  0] 0  0  0  0  1
07  1  0  0 [1  1  1  1] 0  0  0  0  1
08  1  0  0  1  1  1  0  1  1  1  1  1
09  1  1  1  1  1  0  0  1  1  1  1  1
10  1  0  0  0  0  1  0  1  0  1  1  1
11  1  1  0  0  1  1  0  0  0  0  1  1

```

Again, any reasonable format would work as long as it is specified in your answer. Please also mention if you're using 0-based or 1-based coordinates.

### Rules

* You can safely assume that there is always exactly one 'beef' on the bun. Your code is not required to support cases with more than one beef or no beef at all.
* The beef pattern will always appear as described. It will never be rotated or mirrored in any way.
* This is code-golf, so the shortest answer in bytes wins. Standard loopholes are forbidden.

### Test cases

In the following test cases, each row of the matrix is expressed as its decimal representation.

```
Input : [ 3710, 3360, 1149, 2340, 2407, 4034, 3521, 2529, 2527, 3999, 2135, 3267 ]
Output: [ 3, 4 ]

Input : [ 1222, 3107, 1508, 3997, 1906, 379, 2874, 2926, 1480, 1487, 3565, 633 ]
Output: [ 3, 7 ]

Input : [ 2796, 206, 148, 763, 429, 1274, 2170, 2495, 42, 1646, 363, 1145 ]
Output: [ 6, 4 ]

Input : [ 3486, 3502, 1882, 1886, 2003, 1442, 2383, 2808, 1416, 1923, 2613, 519 ]
Output: [ 1, 1 ]

Input : [ 3661, 2382, 2208, 1583, 1865, 3969, 2864, 3074, 475, 2382, 1838, 127 ]
Output: [ 8, 8 ]

Input : [ 361, 1275, 3304, 2878, 3733, 3833, 3971, 3405, 2886, 448, 3101, 22 ]
Output: [ 0, 3 ]

Input : [ 3674, 2852, 1571, 3582, 1402, 3331, 1741, 2678, 2076, 2685, 734, 261 ]
Output: [ 7, 7 ]

```

# Answer
# Jelly, ~~20~~ ~~17~~ 16 bytes

```
ṡ€4ḄZw€“¿ÇÇÐ‘ĖUṀ

```

Input is in form of a Boolean matrix, output is the 1-based index pair **(Y, X)**.

Try it online! or verify all test cases.

### How it works

```
ṡ€4ḄZw€“¿ÇÇÐ‘ĖUṀ  Main link. Argument: M (2D array of Booleans)

ṡ€4               Split each row into 9 chunks of length 4.
   Ḅ              Convert these chunks from base 2 to integer.
    Z             Zip/transpose. This places the columns of generated integers
                  into the rows of the matrix to comb through them.
       “¿ÇÇÐ‘     Push the array of code points (in Jelly's code page) of these
                  characters, i.e., 0xB, 0xE, 0xE, and 0xF.
     w€           Window-index each; in each row, find the index of the contiguous
                  subarray [0xB, 0xE, 0xE, 0xF] (0 if not found).
                  Since the matrix contains on one BEEF, this will yield an array
                  of zeroes, with a single non-zero Y at index X.
             Ė    Enumerate; prefix each integer with its index.
              U   Upend; reverse the pairs to brings the zeroes to the beginning.
               Ṁ  Take the maximum. This yields the only element with positive
                  first coordinate, i.e., the pair [Y, X].

```
> 30 votes

# Answer
## vim, ~~126~~ ~~80~~ ~~77~~ 76

```
/\v1011\_.{9}(1110\_.{9}){2}1111<cr>:exe'norm Go'.join(getpos('.'))<cr>xxdawhPXXd{

```

Expects input in the form

```
111001111110
110100100000
010001111101
100100100100
100101100111
111111000010
110111000001
100111100001
100111011111
111110011111
100001010111
110011000011

```

And outputs (with 1-based indices) as

```
4 5

```

```
/                      regex search for...
\v                     enable "very magic" mode (less escaping)
1011\_.{9}             find the first line ("B"), followed by 8 chars + 1 \n
(1110\_.{9}){2}        find the second and third lines ("EE")
1111<cr>               find the fourth line ("F")
:exe'norm Go'.         insert at the beginning of the file...
join(getpos('.'))<cr>  the current position of the cursor
xxdawhPXX              do some finagling to put the numbers in the right order
d{                     delete the input

```

Thanks to Jörg Hülsermann for indirectly saving 46 bytes by making me realize my regex was super dumb, and to DJMcMayhem for 3 more bytes.
> 42 votes

# Answer
## JavaScript (ES6), ~~63~~ ~~60~~ 56 bytes

```
s=>[(i=s.search(/1011.{9}(1110.{9}){2}1111/))%13,i/13|0]

```

Takes input as a 155-character space-delimited string of 12 12-digit binary strings, returns zero-indexed values. Edit: Saved 3 bytes thanks to @JörgHülsermann. Saved 4 bytes thanks to @ETHproductions.
> 22 votes

# Answer
# C, ~~146~~ ~~177~~ ~~173~~ 163 bytes

Thanks to Numberknot for fixing the code (shifting the lower three rows).

Saving 4 bytes by replacing `>>=1` with `/=2` in 4 places. Saving 10 more bytes by letting `x` and `y` be global and default `int` thanks to MD XF

```
#define T(i,n)(A[y+i]&15)==n
x,y;b(int A[12]){for(x=9;x--;){for(y=0;++y<9;A[y]/=2)if(T(0,11)&&T(1,14)&&T(2,14)&&T(3,15))return(x<<4)+y;A[9]/=2;A[10]/=2;A[11]/=2;}}

```

Ungolfed:

```
int b(int A[12]) {
 for (int x=8; x>=0; --x) {
  for (int y=0; y<9; ++y) {
   if ((A[y]&15)==11 && (A[y+1]&15)==14 && (A[y+2]&15)==14 && (A[y+3]&15)==15) {
    return (x<<4) + y;
   }
   A[y]/=2;
  }
  A[9]/=2; A[10]/=2; A[11]/=2;
 }
}

```

Returns x,y (0-based) in the high and low nibble of a byte.

Usage:

```
int temp=b(array_to_solve);
int x=temp>>4;
int y=temp&15;
printf("%d %d\n",x,y);

```
> 14 votes

# Answer
# MATL, ~~22~~ 21 bytes

```
Eq[ODDH]B~EqZ+16=&fhq

```

Input is a binary matrix, with `;` as row separator. Output is 1-based in reverse order: `Y X`.

Try it online! Or verify all test cases with decimal input format.

### Explanation

The pattern is detected using 2D convolution. For this,

* The matrix and the pattern need to be in bipolar form, that is, `1, -1` instead of `1, 0`. Since the pattern has size 4×4, its occurrence is detected by an entry equal to `16` in the convolution output.
* The convolution kernel needs to be defined as the sought pattern reversed in both dimensions.

Also, since the convolution introduces an offset in the detected indices, this needs to be corrected for in the output.

```
Eq      % Implicitly input binary matrix. Convert to bipolar form (0 becomes -1)
[ODDH]  % Push array [0 8 8 2]
B       % Convert to binary. Each number gives a row
~Eq     % Negate and convert to bipolar. Gives [1 1 1 1; 0 1 1 1; 0 1 1 1; 1 1 0 1]
        % This is the "BEEF" pattern reversed in the two dimensions. Reversal is
        % needed because a convolution will be used to detect that patter
Z+      % 2D convolution, keeping original size
16=&f   % Find row and column indices of 16 in the above matrix
h       % Concatenate horizontally
q       % Subtract 1. Implicitly display

```
> 10 votes

# Answer
# Mathematica, 62 bytes

```
BlockMap[Fold[#+##&,Join@@#]==48879&,#,{4,4},1]~Position~True&

```

Returns all positions of the BEEF matrix, 1-indexed. The input must be a matrix of binary digits. The x and y in the output are switched, though.
> 8 votes

# Answer
# PHP, 87 Bytes

binary string as input without separators, returns zero-indexed values.

```
preg_match("#1011(.{8}1110){2}.{8}1111#",$argv[1],$c,256);echo($s=$c[0][1])%12,$s/12^0;

```

array of numbers as input 128 Bytes

```
<?foreach($_GET[a]as$a)$b.=sprintf("%012b",$a);preg_match("#1011(.{8}1110){2}.{8}1111#",$b,$c,256);echo($s=$c[0][1])%12,$s/12^0;

```

14 Bytes saved by @Titus Thank You
> 7 votes

# Answer
## Slip, 28 bytes

27 bytes of code, +1 for `p` option.

```
(?|1011)(\(?|1110)){2}\1111

```

Requires input as a multiline rectangle of 1's and 0's without spaces. Try it here (with third testcase as input).

### Explanation

Slip is a language from the 2-D Pattern Matching challenge. Sp3000 could say a lot more about it than I can, but basically it's an extended form of regex with some directional commands that let you match in two dimensions. The above code uses the eponymous "slip" command `\`, which doesn't change the match pointer's direction but moves it sideways by one character. It also uses "stationary group" `(?|...)`, which matches something and then resets the pointer to its previous location.

The code breaks down as follows:

```
(?|1011)                     Match 1011; reset pointer to beginning of match
        (         ){2}       Do the following twice:
         \                     Slip (moves pointer down one row)
          (?|1110)             Match 1110; reset pointer to beginning of match
                      \1111  Slip and match 1111

```

This matches the `0xBEEF` square. The `p` option outputs the coordinates of the match, 0-indexed.
> 7 votes

# Answer
# Java 7,~~182~~ 177 bytes

I ported Karl Napf **C** answer to **JAVA** And Thanks to Karl Napf for saving 5 bytes by reminding me Bit magic.(Btw i came up with this idea too but @KarlNapf return part idea was yours not mine).Sorry if i displeased you.

(0-based)

```
int f(int[]a){int x=9,y,z=0;for(;x-->0;){for(y=0;y<9;a[y++]/=2) if((a[y]&15)==11&(a[y+1]&15)==14&(a[y+2]&15)==14&(a[y+3]&15)==15)z=(x<<4)+y;a[y]/=2;a[10]/=2;a[11]/=2;}return z;}

```

# Ungolfed

```
class Beef {

    public static void main(String[] args) {
        int x = f(new int[] { 1222, 3107, 1508, 3997, 1906, 379, 2874, 2926, 1480, 1487, 3565, 633 });
        System.out.println(x >> 4);
        System.out.println(x & 15);
    }

    static int f(int[] a) {
        int x = 9,
            y,
            z = 0;

        for (; x-- > 0; ) {
            for (y = 0; y < 9; a[y++] /= 2)
                if ((a[y] & 15) == 11
                  & (a[y + 1] & 15) == 14
                  & (a[y + 2] & 15) == 14
                  & (a[y + 3] & 15) == 15)
                    z = (x << 4) + y;

            a[y] /= 2;
            a[10] /= 2;
            a[11] /= 2;
        }
        return z;
    }

}

```
> 6 votes

# Answer
# Scala, 90 bytes

```
("1011.{8}(1110.{8}){2}1111".r.findAllMatchIn(_:String).next.start)andThen(i=>(i/12,i%12))

```

Explanation:

```
(
  "1011.{8}(1110.{8}){2}1111" //The regex we're using to find the beef
  .r                          //as a regex object
  .findAllMatchIn(_:String)   //find all the matches in the argument thats going to be passed here
  .next                       //get the first one
  .start                      //get its start index
)                             //this is a (String -> Int) function
andThen                       //
(i=>                          //with the found index
  (i/12,i%12)                 //convert it to 2d values
)

```

`(a -> b) andThen (b -> c)` results in a `(a -> c)` function, it's like the reverse of compose, but requires fewer type annotations in scala. In this case, it takes a string of the binary digits as input and returns a tuple of zero-based indices.
> 5 votes

# Answer
# Python 2, ~~98~~ ~~95~~ 92 bytes

```
lambda x:'%x'%(`[''.join('%x'%int(s[i:i+4],2)for s in x)for i in range(9)]`.find('beef')+15)

```

Input is a list of strings, output is the string **XY** (1-based indices).

Test it on Ideone.
> 5 votes

# Answer
# Perl 5 \+ `-n -M5.10.0`, 51 bytes

Uses 0-based indices. Expects input as a string of `1`s and `0`s and outputs space separated co-ordinates.

Thanks to @wullxz and @GabrielBenamy for helping me save 9 bytes, and to @Taemyr's comment on my Retina answer for pointing out an issue!

```
/1011.{9}(1110.{9}){2}1111/;say"@-"%13,$","@-"/13|0

```

Try it online!
> 5 votes

# Answer
## Retina, 47 bytes

I'd like to preface this with an apology. I think this is probably terrible and a bad example of how to use the language, but since I used a Regex for my Perl answer, I thought I'd try Retina. I'm not very good. :( The snippets on github helped me greatly though!

Thanks to @wullzx for his comment on my Perl answer for -3 bytes and to @Taemyr for pointing out an issue with my method!

Expects input as a space-separated binary string and outputs co-ordinates space separated.

```
(.{13})*(.)*1011(.{9}1110){2}.{9}1111.*
$#2 $#1

```

Try it online!

Verify all tests at once.
> 5 votes

# Answer
# J, ~~31~~ 29 bytes

```
[:($#:I.@,)48879=4 4#.@,;._3]

```

The input is formatted as a 2d array of binary values, and the output is the zero-based coordinates as an array `[y, x]`.

The flattening and base conversion to find the index is something I learned from this comment by Dennis.

## Usage

```
   f =: [:($#:I.@,)48879=4 4#.@,;._3]
   ] m =: _12 ]\ 1 1 1 0 0 1 1 1 1 1 1 0 1 1 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 1 1 1 1 1 0 1 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 1 0 1 1 0 1 1 1 0 0 0 0 0 1 1 0 0 1 1 1 1 0 0 0 0 1 1 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 0 0 1 0 1 0 1 1 1 1 1 0 0 1 1 0 0 0 0 1 1
1 1 1 0 0 1 1 1 1 1 1 0
1 1 0 1 0 0 1 0 0 0 0 0
0 1 0 0 0 1 1 1 1 1 0 1
1 0 0 1 0 0 1 0 0 1 0 0
1 0 0 1 0 1 1 0 0 1 1 1
1 1 1 1 1 1 0 0 0 0 1 0
1 1 0 1 1 1 0 0 0 0 0 1
1 0 0 1 1 1 1 0 0 0 0 1
1 0 0 1 1 1 0 1 1 1 1 1
1 1 1 1 1 0 0 1 1 1 1 1
1 0 0 0 0 1 0 1 0 1 1 1
1 1 0 0 1 1 0 0 0 0 1 1
   f m
4 3
   f (#:~2#~#) 3710 3360 1149 2340 2407 4034 3521 2529 2527 3999 2135 3267
4 3
   f (#:~2#~#) 1222 3107 1508 3997 1906 379 2874 2926 1480 1487 3565 633
7 3
   f (#:~2#~#) 2796 206 148 763 429 1274 2170 2495 42 1646 363 1145
4 6
   f (#:~2#~#) 3486 3502 1882 1886 2003 1442 2383 2808 1416 1923 2613 519
1 1
   f (#:~2#~#) 3661 2382 2208 1583 1865 3969 2864 3074 475 2382 1838 127
8 8
   f (#:~2#~#) 361 1275 3304 2878 3733 3833 3971 3405 2886 448 3101 22
3 0
   f (#:~2#~#) 3674 2852 1571 3582 1402 3331 1741 2678 2076 2685 734 261
7 7

```

## Explanation

```
[:($#:I.@,)48879=4 4#.@,;._3]  Input: 2d array M
                            ]  Identity. Get M
                 4 4    ;._3   For each 4x4 subarray of M
                       ,         Flatten it
                    #.@          Convert it to decimal from binary
           48879=              Test if equal to 48879 (decimal value of beef)
[:(       )                    Operate on the resulting array
         ,                       Flatten it
      I.@                        Find the indices where true
    #:                           Convert from decimal to radix based on
   $                               The shape of that array
                               Returns the result as coordinates [y, x]

```
> 5 votes

# Answer
# APL (Dyalog Extended), 13 bytes

```
⍸⎕⍷⍨~⊤0 8 0 6

```

Try it online!

We already have Zacharý's APL answer, but APL has improved a lot over the recent years, just enough to beat Jelly!

A full program that takes the binary matrix from stdin and prints the `(y,x)` to stdout.

### How it works

```
⍸⎕⍷⍨~⊤0 8 0 6
     ⊤0 8 0 6  ⍝ Binary representation (a number → column)
               ⍝ 0 1 0 0
               ⍝ 0 0 0 1
               ⍝ 0 0 0 1
               ⍝ 0 0 0 0
    ~  ⍝ Boolean negation
 ⎕⍷⍨   ⍝ Take input and mark 1 where the 2D pattern appears
⍸      ⍝ Extract the coordinates of all ones

```
> 3 votes

# Answer
# Ruby, 62 bytes

```
def f(a);a=~/1011(.{8}1110){2}.{8}1111/;$`.size.divmod(12);end

```

It expects a string of `0` and `1` and returns an array of Y and X, zero-based.

Try at ideone.
> 2 votes

# Answer
**Scala, 318 Bytes**

*This solution could be further improved... but I kept it readable and allowed for the input to be the multi-line spaced matrix.*

**Actual Solution if Array of binary String**

```
def has(s: String, t: String): Int = s.indexOf(t)
val beef = List("1011", "1110", "1110", "1111")
l.zipWithIndex.map{case(e,i)=>l.drop(i).take(4)}.map{_.zip(beef)}.map{_.collect{case e=>has(e._1,e._2)}}.zipWithIndex.filterNot{e => e._1.contains(-1) ||  e._1.distinct.length > 1}.map{e=>s"(${e._1.head},${e._2})"}.head

```

**Sample Working**

```
val bun =
"""1 1 1 0 0 1 1 1 1 1 1 0
1 1 0 1 0 0 1 0 0 0 0 0
0 1 0 0 0 1 1 1 1 1 0 1
1 0 0 1 0 0 1 0 0 1 0 0
1 0 0 1 0 1 1 0 0 1 1 1
1 1 1 1 1 1 0 0 0 0 1 0
1 1 0 1 1 1 0 0 0 0 0 1
1 0 0 1 1 1 1 0 0 0 0 1
1 0 0 1 1 1 0 1 1 1 1 1
1 1 1 1 1 0 0 1 1 1 1 1
1 0 0 0 0 1 0 1 0 1 1 1
1 1 0 0 1 1 0 0 0 0 1 1
""".replaceAll(" ","")
def has(s: String, t: String): Int = s.indexOf(t)
val beef = List("1011", "1110", "1110", "1111")
val l = bun.split("\n").toList
l.zipWithIndex.map{case(e,i)=>l.drop(i).take(4)}
.map{_.zip(beef)}
.map{_.collect{case e=>has(e._1,e._2)}}.zipWithIndex
.filterNot{e => e._1.contains(-1) ||  e._1.distinct.length > 1}
.map{e=>s"(${e._1.head},${e._2})"}.head

```
> 1 votes

# Answer
# Element, 130 bytes

```
_144'{)"1-+2:';}144'["1-+19:~?1+~?!2+~?3+~?12+~?13+~?14+~?15+~?!24+~?25+~?26+~?27+~?!36+~?37+~?38+~?39+~?16'[&][12%2:`\ `-+12/`]']

```

Try it online!

Takes input as one long string of 1s and 0s without any delimiters. Outputs like `3 4` (0-based indexing).

This works by placing the input data into an "array" (basically a dictionary with integer keys) and then, for each possible starting value, tests the bits at particular offsets (all 16 of them in a very laborious process).
> 1 votes

# Answer
**Python, 137 bytes** (according to Linux (thanks ElPedro))

```
def f(s,q=0):import re
 i=s.index(re.findall('1011.{8}1110.{8}1110.{8}1111',s)[q])+1
 x=i%12
 y=(i-x)/12
 if x>8:x,y=f(s,q+1)
 return x,y

```

Not exactly a competitive bytecount, but the algorithm is a bit interesting. Takes input as a string of binary values.
> 1 votes

# Answer
## Dyalog APL, ~~29~~ 27 bytes

Takes a 12x12 binary array as user input and returns the coordinates in reverse order, the indexes start at 1.

Thanks to @Adám for saving many bytes. -2 Bytes because I'm dumb and left everything in a function for no reason.

```
0~⍨∊{⍵×⍳⍴⍵}⎕⍷⍨~0 8 0 6⊤⍨4/2

```
> 1 votes

# Answer
# **F# - 260 bytes**

Full program, including the required EntryPoint designator (so count fewer if you wish I suppose).

Input: each row as separate string: "111001111110" "110100100000" "010001111101" "100100100100" "100101100111" "111111000010" "110111000001" "100111100001" "100111011111" "111110011111" "100001010111" "110011000011"

Code:

```
[<EntryPoint>]
let main a=
 let rec f r:int=
  let b=a.[r].IndexOf"1011"
  if(b>0)then if(a.[r+1].[b..b+3].Equals"1110"&&a.[r+2].[b..b+3].Equals"1110"&&a.[r+3].[b..b+3].Equals"1111")then r else f(r+1)
  else f(r+1)
 printfn"%d%d"(a.[f 0].IndexOf"1011")(f 0);0

```

Not the most elegant solution most likely, but i wanted to keep with strings, so this is how i did it. I almost got it to be a single line and smaller using pipes, but there is something with the double if block that was getting me that i couldn't resolve. So oh well!

I thought too about porting Karl's answer into F# as it's a good one, and may still do that for fun as another approach, but wanted to stick with this one to be different.
> 1 votes

# Answer
# , 111 bytes

```
function(a,b=63357%/%2^(0:15)%%2)
which(sapply(1:9,function(i)sapply(1:9,function(j)all(a[i+0:3,j+0:3]==b))),T)

```

Try it online!

Searches for identities of 4x4 matrix starting at all indices of 9x9 matrix (to avoid edge overlaps).
> 1 votes

# Answer
# 05AB1E, 17 bytes

```
2Fø€ü4}JJ˜Žùòbk9‰

```

Input as a matrix of bits. Output is 0-based, in the order \\$Y,X\\$.

Try it online or verify all test cases.

**Explanation:**

```
2Fø€ü4}     # Create transposed overlapping 4x4 blocks of the (implicit) input-matrix:
2F          #  Loop 2 times:
  ø         #   Zip/transpose; swapping rows/columns
   €        #   Map over each row:
    ü4      #    Create all overlapping quartets
 }          #  Close the loop
J           # Join each row of each matrix together
 J          # Join the rows of each matrix together
  ˜         # Flatten the list of strings
   Žùò      # Push compressed integer 63481
      b     # Convert it to binary: 1111011111111001
       k    # Get the index of this binary-string in the list
        9‰  # Divmod it by 9
            # (after which the result is output implicitly)

```

See this 05AB1E tip of mine (section *How to compress large integers?*) to understand why `Žùò` is `63481`.
> 1 votes

# Answer
# Uiua, 12 bytes

```
⊚⌕⋯13_7_7_15

```

Self explanatory. Converts the number array to bits, finds where it is. The input is a 12x12 bit matrix, the output is a 1x2 matrix where the X coordinate is the second element.

Test pad
> 1 votes

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