title: Halt with 50% non-Halting

text:
# Question
Title: Halt with 50% non-Halting
Create a program that halts **exactly** 50% of the time. Be original. Highest voted answer wins. By **exactly** I mean that on *each* run there is a 50% chance of it halting.

# Answer
> 45 votes
### Perl

```
fork || do {sleep(1) while(1)}

```

Each time you run this program, it halts and doesn't halt.

# Answer
> 20 votes
## Python

```
import random
p=.3078458
while random.random()>=p:p/=2

```

Each time around the loop it breaks with exponentially decreasing probability. The chance of never breaking is the product \\$(1-p)(1-\frac{p}{2})(1-\frac{p}{4})...\\$ which is \\$\frac{1}{2}\\$. (Obligatory comment about floating point not being exact.)

# Answer
> 12 votes
# JavaScript

Alternatives halting and not halting. (halts on first run, doesn't halt on second, ...)

```
var h = localStorage.halt;
while (h) localStorage.halt = false;
localStorage.halt = true;

```

# Answer
> 10 votes
# Geometry Dash 2.2 Editor Glitch - 2 objects

**Explanation:**

The random trigger randomly toggles (disables) Group ID 1 or 2 with a 50% chance.

The purple pad is on reverse mode (meaning that if the cube touches it, the cube moves backward, which goes to the left forever and ever.).

Since the purple pad has Group ID 2, it has a 50% chance of being disabled, which means that the cube can pass through it to the end of the level, which will halt.

**How to reproduce this:**

Purple pad is on reverse mode and has Group ID 1.

Inside the random trigger.

# Answer
> 7 votes
# C

```
#include <unistd.h>
main() { while (getpid()&2); }

```

# Answer
> 7 votes
# Random Brainfuck, 5 bytes

```
?[--]

```

Try it online!

Random BF extends BF's set of primitives with the `?`, which generates a random byte and stores it in the current cell. That is, it generates an integer from 0-255. Given that there are an equal amount of odds and evens in that range, there is a 50% chance that the current cell is set to an even number after the first step.

The `[--]` endlessly decrements the current cell by two, as long as the current cell is not zero. Therefore, all even numbers will terminate. On the other hand, since parity is invariant mod 256, all odd numbers will loop forever, never quite reaching zero.

# Answer
> 7 votes
# Lost, 2 bytes

```
%@

```

Try it online!

Although this is apparently a popcon, I figure the language itself is adequately interesting!

Lost is a fairly standard toroidal 2D language, with the caveat that the instruction pointer's initial position and direction are completely random. Additionally, in order to make it possible to write deterministic programs, there's a piece of global state called the *safety* which doesn't allow the program to halt by reaching `@` until it's been turned off by `%`. So, this program has three cases:

* 50% of the time, the IP starts moving left or right. It eventually reaches both instructions, and the program halts.
* 25% of the time, the IP starts moving up or down on `%`. The safety is turned off, but it never reaches `@`, so the program does not halt.
* 25% of the time, the IP starts moving up or down on `@`. The safety is never turned off, so the program does not halt.

# Answer
> 6 votes
# INTERCAL, 59 bytes

```
DO %50 (1) NEXT
DO COME FROM COMING FROM
(1) PLEASE GIVE UP

```

Try it online!

`COME FROM COMING FROM` makes an endless loop, but there is a 50% chance to skip to the end of the program.

# Answer
> 5 votes
# Ruby

```
n = 2*rand(1...49)+1; divisors = (1...100).select{|x|n % x == 0}.count until divisors == 2
print n

```

There are exactly 24 odd primes between 0..100, the largest being 97. This algorithm chooses a random odd number within the range and repeats until it finds a prime:

This particular implementation has two bugs:

* an exclusive range is used, meaning that 99 is never tested, meaning there are only 48 possible values for `n`, of which 24 are primes.
* while `n` was meant to be redrawn at each iteration, only the primality testing is executed in the loop. If at first it doesn't succeed, it will try again - but with the same number.

# Answer
> 5 votes
# \>\<\>, 3 bytes

```
x;v

```

Try it online!

I... don't actually know \>\<\>, but this should work on the same principle as the existing answers, just by "rerolling" vertical travel and looping if it goes left rather than down.

# Answer
> 4 votes
# BASH

```
#!/bin/bash
set -e
sed -i 's/true\;/false\;/' $0
while false; do echo -n ''; done;
sed -i 's/false\;/true\;/' $0

```

Just a fun self-modifying script.

Note: the empty quoted string on `echo -n ''` are just for clarity. They can be removed without loss of functionality.

# Answer
> 4 votes
## GolfScript

```
2rand{.}do

```

I know this isn't a challenge, but I golfed it anyway. :)

---

Alternatively, here's a GolfScript implementation of Keith Randall's solution:

```
2{2*.rand}do

```

In theory, this will have an exactly 1/4 + 1/8 + 1/16 + ... = 1/2 probability of halting. In practice, though, it will always eventually run out of memory and halt, because the denominator keeps getting longer and longer.

# Answer
> 4 votes
I felt like golfing this one:

### Befunge - 5 chars

```
?><
@

```

(I'm not sure whether this actually works as I don't have a befunge compiler on me)

# Answer
> 4 votes
# Poetic, 113 bytes

```
sometimes i,i think i get a choice
if its a thing i know i do affect,i bet i do win
i`m sorry if it breaks
o-h no

```

Try it online!

# Answer
> 3 votes
Somewhat obfuscated solution:

# Haskell

```
import Control.Monad
import Control.Monad.Random         -- package MonadRandom
import Control.Monad.Trans.Maybe
import Data.Numbers.Primes          -- package primes

-- | Continue the computation with a given probability.
contWithProb :: (MonadRandom m, MonadPlus m) => Double -> m ()
contWithProb x = getRandomR (0, 1) >>= guard . (<= x)

loop :: MonadRandom m => MaybeT m ()
loop = contWithProb (pi^2/12) >> mapM_ (contWithProb . f) primes
  where
    f p = 1 - (fromIntegral p)^^(-2)

main = evalRandIO . runMaybeT $ loop

```

# Python

The same solution expressed in Python:

```
import itertools as it
import random as rnd
from math import pi

# An infinite prime number generator
# Copied from http://stackoverflow.com/a/3796442/1333025
def primes():
    D = {  }
    yield 2
    for q in it.islice(it.count(3), 0, None, 2):
        p = D.pop(q, None)
        if p is None:
            D[q*q] = q
            yield q
        else:
            # old code here:
            # x = p + q
            # while x in D or not (x&1):
            #     x += p
            # changed into:
            x = q + 2*p
            while x in D:
                x += 2*p
            D[x] = p

def contWithProb(p):
    if rnd.random() >= p:
        raise Exception()

if __name__ == "__main__":
    rnd.seed()
    contWithProb(pi**2 / 12)
    for p in primes():
        contWithProb(1 - p**(-2))

```

## Explanation

> This solution makes use of the fact that the infinite product \\$\Pi(1-p^{-2})\\$ converges to \\$\frac{6}{\pi^2}\\$. This is because \\$\zeta(2)=\Pi(\frac{1}{1-p^{-2}})\\$ converges to \\$\frac{\pi^2}{6}\\$.

# Answer
> 3 votes
# \>\<\>, 4 bytes

```
x;
>

```

Try it online!

# Answer
> 3 votes
# Pyt, 3 bytes

```
ɹ`ł

```

Try it online!

```
ɹ          get a random bit (0 or 1 with equal probability)
 `ł        loop while top of stack is truthy (1 is truthy; 0 is not)

```

# Answer
> 2 votes
# C

```
int main() {
    char i;
    while(i&1);
}

```

# Answer
> 2 votes
# \>\<\>, 5 bytes and a beautiful 2x2 square

```
x;
><

```

`x` sends the instruction pointer in a random direction; If it sends left or right the IP will hit `;` and terminate. If it goes up or down the IP will get stuck in the infinite `><` loop, being sent back and forth between the two.

# Answer
> 2 votes
**Scala**

```
object HaltOrNot extends App {
  val x = scala.util.Random.nextLong
  while (((scala.util.Random.nextLong & 0xFFFFFFFFFFFFFFFEL) ^ x) != 0) {}
}

```

If x is odd positive or even negative, this program will *never* halt. If x is even positive or odd negative, this program will definitely halt... someday... after thousands of years... (e.g., if your machine can test 100 Mio loops per second it will terminate after 2924 years in expectation)

# Answer
> 1 votes
## TI-Basic

```
:Lbl 1:If round(rand):Pause:Goto 1

```

# Answer
> 1 votes
## Python, 48

```
import random
a=random.randrange(2)
while a:pass

```

# Answer
> 1 votes
# Perl

```
BEGIN {
    # Do the following block 50% of time.
    if (int rand 2) {
        # Create a function that doubles values.
        *double = sub {
            2 * shift;
        };
    }
}
double / 3 while 1; # Calculates double divided using /

```

Not code golf, so I could avoid unreadable code (because what it does is more important). It randomly declares a function during compilation phase. If it gets declared, `double` gets regular expression as an argument. If it doesn't get declared, `double` is a bareword, and Perl divides it by `3` endlessly. This abuses Perl's bareword parsing, in order to get parser parse the same code two different ways.

# Answer
> 1 votes
# Java

```
import java.util.Random;

class Halt50 {
    public static void main(String[] args){
        if(new Random().nextInt(2)==0)for(;;);
    }
}

```

# Answer
> 1 votes
# Java

```
import java.io.*;

public class HaltNoHalt {
    public static void main(String[] args) throws Exception {
        RandomAccessFile f = new RandomAccessFile("HaltNoHalt.java", "rw");
        f.seek(372);
        int b = f.read();
        f.seek(372);
        f.write(b ^ 1);
        Runtime.getRuntime().exec("javac HaltNoHalt.java");

        while ((args.length & 1) == 1);
    }
}

```

This self-modifies the code to toggle the `== 1` to `== 0` and back, every time it's run. Save the code with newlines only or the offset will be wrong.

The `args.length` is just to prevent compiler optimizations.

# Answer
> 1 votes
# JavaScript (Node.js), 24 bytes

It was incorrect, but somehow correcting it removed 2 bytes, thanks Roman Czyborra for pointing out it was incorrect

And another -2 because I forgot how to JS

```
if(Date.now()%2)for(;;);

```

`Date.now()` returns the amount of milliseconds since the Unix time epoch, which has a 50% chance to be even at the moment of running the program.

# Answer
> 1 votes
# Alice, 5 bytes

```
2U$v@

```

Try it online!

```
2          Pushes the number 2 on the stack
 U         Pops 2, pushes a random number in the range [0,2) on the stack
  $        Pops the random number, if 0 skip the next instruction
   v       Now moves vertically forever
    @      Halt

```

# Answer
> 1 votes
# Fortran (GFortran), 19 bytes

```
1 if(i>0)goto 1
end

```

Try it online!. Since the lazy programmer did not initialise `i`, it is a random 32 bit integer, populated from whatever bits were floating around in that memory space before.

# Answer
> 1 votes
**Javascript**

JS has these Object URL things, which are generated when you create a file. The hex is all meaningless nonsense, but not in this case! Therefore, something like this works:

```
var blob = URL.createObjectURL(new Blob([""]))
// The blob looks something like "blob:null/01234567-1234-1234-1234-0123456789ab" and is hex, which can be exploited, really, any character works!
while (TextEncoder && new TextEncoder().encode(blob)[10] > 56) {
// Forever!
}

```

# Answer
> 1 votes
## Python, 19 bytes

```
while id(1)>>17&1:1

```

**Run online**

This gets the address of the constant `1` in memory, and gets the 17th bit from the right. It then loops forever if the bit is `1`.

I can't use a later bit to save a byte, because those bits seem to be constant between runs. The last bits are always `0011110000`.

Some debug code:

```
print(bin(id(1)))
print(bin(id(1)>>17))
print(id(1)>>17&1)

```

# Answer
> 0 votes
**Exactly** 50% of the time?

# OBJ-C

```
- (void)applicationDidFinishLaunching:(NSNotification*)aNotification {
    BOOL haltedLastRun = [(NSNumber*)[[NSUserDefaults standardUserDefaults] objectForKey:@"halted"] boolValue];
    if (!haltedLastRun) {
        [[NSUserDefaults standardUserDefaults] setObject:[NSNumber numberWithBool:YES] forKey:@"halted"];
        [[NSApplication sharedApplication] terminate:nil];
    }
}

```

# Answer
> 0 votes
# Haskell

Runs for two intervals, each one 1 second long (chosen because 1 second is the SI unit for time). Halts inside 50% of the intervals. So 50% of the running seconds it will not halt, the other 50% it will. Works in GHC only.

```
import Control.Concurrent (threadDelay)
main = threadDelay 1990000

```

# Answer
> 0 votes
## Shell Script

this script will clobber .md5sum files in the current and child directories.

```
#!/bin/sh
echo *.md5sum|xargs -n1|head -n1|xargs test -e && exec rm *.md5sum
while ! find . -name '*.md5sum' -print0 |xargs -0r grep 00000000000000
do {
    find . -type f -print|sed -e 's!^\(.*\)$!md5sum "\1" > "\1".md5sum!e'
}
done

```

# Answer
> 0 votes
## GTB

```
[@r;p;]

```

I know this isn't code-golf but I decided to golf it anyway.

# Answer
> 0 votes
# C++

```
#include <fstream>
main () {
    int c;
    std::fstream fs;
    fs.open ("myfile.txt", std::fstream::in);
    fs>>c;
    fs.close ();
    fs.open ("myfile.txt", std::fstream::out);
    fs<<c+1;
    fs.close ();
    while (c%2);
    return 0;
}

```

Each run will halt iff the run before didn't.

# Answer
> 0 votes
## Windows Command Script

This script will append code to itself which ultimately alternates 'x' on each run.

```
call :last
if %x%==1 (
    echo>>%0 set x=0
    exit /b 0
) else (
    echo>>%0 set x=1
)
:nohalt
goto :nohalt
:last
set x=1
[newline here]

```

# Answer
> 0 votes
# Math++

```
_($rand*2)+2>$
2>$
1

```

# Answer
> 0 votes
# Python 2, 54 bytes

```
import time;H=[time.time()%2]
for h in H:H+=[h]*int(h)

```

Try it online!

Halting behaviour is dependent on current time.

# Answer
> 0 votes
# Pxem, filename: 7 bytes + content: 0 bytes = 7 bytes, depends on implementation.

* Filename (escaped): `\002.r.w.a`
* Content: empty.

## How it works

* `\002.r`: pushes one of 0 or 1.
* `.w ... .a`: `while empty || pop!=0; do ... ;done`

Try it online!

# Answer
> 0 votes
# Thue, 19 bytes

```
0::=00
10::=
::=
10

```

Try it online!

TIO's Thue interpreter doesn't seem to be working correctly.

# Answer
> 0 votes
# Thunno, \\$ 6 \log\_{256}(96) \approx \\$ 4.94 bytes

```
2RZw?[

```

Attempt This Online!

#### Explanation

```
2R      # range(2): push [0, 1]
  Zw    # Random element of ↑
    ?   # If ↑ == 1:
     [  #  Loop forever
        # (Else, exit)

```

# Answer
> 0 votes
# C (GCC)

```
unsigned long long i,j,k;
r;

main()
{
    srand(time(0));

    i=k=1;
    while (k) {
        k = 0;
        for (j = 1; j <= i; ++j) {
            do {
                r = rand() % 4;
            } while (r == 3);

            k += !!r;
        }
        ++i;
    }
}

```

Try It Online!

It loops while `k` isn't 0. `k` is only 0 at the end of the loop if `i` number of calls to `rand()` are all divisible by 3. The chance of that equals

$$ \frac {1} {3^i} $$

and the sum of all inverse natural powers of 3 equals 0.5. Of course, `i` doesn't go from 1 to infinity, but from 1 to `ULLONG_MAX`. When `i` reaches `ULLONG_MAX`, the `for` loop will loop infinitely as `j` will always be less than or equal to `i` (assuming `ULL_MAX + 1` is 0).

Since `i` doesn't quite loop from 1 to infinity, the code will loop *slightly* less than 50 % of the time, more specifically

$$ 50 \\% - \frac {1} {3^{U+1} - 3^{U}} $$

where U is `ULLONG_MAX`.

---
Tags: popularity-contest, random
---


title: Print all pandigital numbers

text:
# Question
Title: Print all pandigital numbers
Given a base as input, output all pan-digital numbers. A number is pan-digital if it includes every digit in that base at least once, possibly multiple times. Every number is considered to contain an infinite number of leading 0s.

rules apply. Given a base, you may either:

* Given an index, output the n-th pan-digital number in that base
* Output all pan-digital numbers up to a given index, or
* Output all pan-digital numbers in that base in ascending order.

You may also submit a function that outputs a generator or infinite list.

## Test cases

```
2 -> 1, 2, 3, 4, 5, 6... (all natural numbers)
3 -> 5, 7, 11, 14, 15, 16, 17, 19...
4 -> 27, 30, 39, 45...
...
10 -> 123456789, 123456798...

```

# Answer
# x86-64 machine code, 28 bytes

```
31 C0 FF C0 50 31 C9 99 F7 FE 0F AB D1 01 C2 75 F6 58 FF C1 0F A3 F1 19 D7 73 E7 C3

```

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes a 0-index in EDI and the base in ESI, and returns a number in EAX.

In assembly:

```
f:  xor eax, eax    # Set EAX to 0. EAX will hold the number being tested.
ol: inc eax         # Increase EAX by 1.
    push rax        # Save the value of RAX (containing EAX) onto the stack.
    xor ecx, ecx    # Set ECX to 0.
il: cdq             # Set EDX to 0 by sign-extending EAX.
    idiv esi        # Divide EDX:EAX by ESI (the specified base).
                    # The quotient goes in EAX and the remainder goes in EDX.
    bts ecx, edx    # Set the bit in ECX at position EDX (a digit) to 1.
    add edx, eax    # Add EAX to EDX.
    jnz il          # Jump back if the result of the addition is nonzero.
            # This loop will exit when the quotient and remainder are both zero.
            # This performs one more iteration after EAX first becomes zero,
            # thereby processing one leading zero and ending with EAX=0, EDX=0.
    pop rax         # Restore the value of RAX (containing EAX) from the stack.
    inc ecx         # Add 1 to ECX.
    bt ecx, esi     # Set CF to the bit in ECX at position ESI (the base).
            # If all digits are present, ECX was (2^base)-1 and became 2^base,
            # and then CF=1. Otherwise, ECX is lower, and CF=0.
    sbb edi, edx    # Subtract EDX+CF from EDI (thus -1 when EAX is pandigital).
    jnc ol          # Jump back, to repeat, except when it goes from 0 to -1.
    ret             # Return.

```
> 9 votes

# Answer
# Python, ~~74~~ 71 bytes

*-3 thanks to pan*

```
def f(b,i=1):b-len({i//b**k%b for k in range(i+1)})or print(i);f(b,i+1)

```

Attempt This Online!
> 8 votes

# Answer
# 05AB1E, ~~11~~ ~~9~~ 8 bytes

```
∞ʒ*IвÙgQ

```

-2 bytes thanks to *@TheThonnu* (`¾šêIL<Q` to `0šÙgQ`).
-1 byte thanks to *@alephalpha* (`Iв0š` to `*Iв`).

Given \\$n\\$, outputs the infinite sequence.

Try it online.

**Explanation:**

```
∞         # Push an infinite positive list: [1,2,3,...]
 ʒ        # Filter it by:
  *       #  Multiply the current integer to the (implicit) input-integer
   Iв     #  Convert it to base-input as list
     Ù    #  Uniquify this list
      g   #  Pop and push its length
       Q  #  Check if it's equal to the (implicit) input-integer
          # (after which the filtered infinite list is output implicitly)

```

Multiplying the integer by the input results in an additional trailing `0` in the base-converted list (thanks *@alephalpha*).
> 7 votes

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

Longer than EzioMercer's answer but works in theory1 for any base, rather than up to \\$36\\$.

Expects `(base)(n)` where both arguments are BigInts. Returns the \\$n\\$-th term of the sequence, 1-indexed.

```
b=>g=(k,q=x=1n,o=1n)=>q?g(k,q/b,o|1n<<q%b):k&&-~g(k-=-~o>>b,++x)

```

Try it online!

*1: In practice, it's ironically worse because of the recursion.*

### Without recursion, 70 bytes

*-1 thanks to @l4m2*

Backport of the C port.

```
b=>k=>{for(q=x=o=1n;k;q=q/b||(k-=-~o>>b,x+=o=1n))o|=1n<<q%b;return~-x}

```

Try it online!

---

# C (gcc), 66 bytes

*-1 thanks to @ceilingcat*
*-1 thanks to @c--*

A port of the JS version, but obviously without the benefit of BigInts.

```
o,q,x;f(b,k){for(q=x=0;k;q=q/b?:(k-=-~o>>b,x+=o=1))o|=1<<q%b;--x;}

```

Try it online!
> 7 votes

# Answer
# Vyxal, ~~11~~ ~~10~~ 9 bytes

```
⁰τꜝ⁰ɽ⊍¬)ȯ

```

Try it Online!

Prints the first n pandigital numbers. Takes n then base.

*-1 thanks to @mathcat*

*-1 thanks to @AndrovT*

## Explained (old)

```
⁰τUs⁰ɽ~↔⁼)ȯ
         )ȯ  # First n numbers where:
⁰τ           #   that number in base input
  Us         #   uniquified sorted
    ⁰ɽ ↔     #   with digits from the range [1, input) kept
      ~ ⁼    #   equals that range

```
> 5 votes

# Answer
# JavaScript (V8), 59 bytes

```
b=>{for(i=0;++i;)new Set(i.toString(b)+0).size<b||print(i)}

```

Try it online!

## UPD 62 -\> 60

Thanks to Kevin Cruijssen for the tip to reduce bytes count

## UPD 60 -\> 59

Thanks to Arnauld for the tip to reduce bytes count

# JavaScript (Node.js), 113 bytes

This code works for any base, rather than up to 36 and without a recursion

Expects one argument - `b (base)` as `BigInt`

```
b=>{for(n=0n;a=[],p=0n,k=++n;new Set(a).size<b||console.log(n)){while(k/b**p++);while(p--)k-=(a[p]=k/b**p)*b**p}}

```

Try it online!
> 4 votes

# Answer
# Jelly, 7 bytes

```
1bŻĠṫʋ#

```

A dyadic Link that accepts the base on the left and the number of pan-digital numbers to find on the right and yields a list.

**Try it online!**

### How?

```
1bŻĠṫʋ# - Link: integer, B; integer, N
1       - set the left argument to one (k=1)
      # - increment (k), yielding the first (N) for which:
     ʋ  -   last four links as a dyad - f(k, B):   e.g. k=23, B=3
 b      -     convert (k) to base (B)                   [2,1,2]
  Ż     -     prefix with a zero                        [0,2,1,2]
   Ġ    -     group indices by their values -           [[1],[3],[2,4]]
    ṫ   -     tail (that) from index (B) -                      [[2,4]]
        -       (the empty list is falsey, other lists are truthy)

```
> 4 votes

# Answer
# PARI/GP, 46 bytes

```
n->for(i=1,oo,#Set(digits(i*n,n))<n||print(i))

```

Attempt This Online!

Saved some bytes by multiplying `n` instead of prepending `0`.
> 3 votes

# Answer
# Wolfram Language (Mathematica), 47 bytes

```
If[DigitCount[n#,#]~FreeQ~0,Echo@n]~Do~{n,∞}&

```

Try it online! (press "play" to stop running)

prints sequence to infinity

-4 bytes from @alephalpha
> 3 votes

# Answer
# Gaia, ~~9~~ 8 bytes

```
⟨×Bul=⟩#

```

Try it online!

Takes `n`, then `b`; returns the first `n` pandigital numbers in base `b`. Uses the same trick as this answer to add a zero.

Explanation of older answer below:

```
⟨       ⟩#   # find the first n positive integers with a truthy result of:
 B          # convert to base b (implicitly pushed)
  0+        # add 0 to the list
    u       # uniquify
     l=     # is the length equal to the base (implicitly pushed again)
```
> 3 votes

# Answer
# Pip, ~~29 24 23~~ 20 bytes

```
W1{I#UQy*aTDa=aPyUy}

```

Attempt This Online!

*-1 thanks to @KevinCruijssen and @alephalpha*
*-3 thanks to @DLosc*

#### Explanation

```
W1{I#UQy*aTDa=aPyUy}  # Implicit input on command line
                      # y is automatically initialised to 0
                      # (in a numerical context)
W1{                }  # while True:
   I                  #  if
    #                 #   the length of
       y*a            #   y * input
          TDa         #   in base input
     UQ               #   uniquified
             =        #   equals
              a       #   the input
               Py     #  then print y
                 Uy   #  increment y

```

Old:

```
Y1W1{ISNUQyTDaPE0=,a{Py}Yy+1}  # Implicit input on command line
Y1                             # Set y to 1
  W1{                       }  # while True:
     I                         #  if
          yTDa                 #   y in base input
              PE0              #   with a 0 prepended,
      SNUQ                     #   sorted and uniquified
                 =             #   equals
                  ,a           #   range(0, input)
                    {  }       #  then
                     Py        #   print y
                        Yy+1   #  y = y + 1

```
> 2 votes

# Answer
# Java 8, ~~98~~ ~~97~~ ~~96~~ 94 bytes

Given a base \\$b\\$, it'll output the infinite sequence separated by newlines (pretty similar to *@EzioMercer*'s JavaScript answer):

```
b->{for(int i=0;;)if(b.toString(++i*b,b).chars().distinct().count()==b)System.out.println(i);}

```

Try it online.

Original answer **(~~98~~ ~~97~~ 95 bytes)**: Given two inputs \\$b\\$ and \\$n\\$, outputs the \\$n^{th}\\$ term in base-\\$b\\$.

```
b->n->{int r=0,i,t;for(;n>0;)n-=b.toString(++r*b,b).chars().distinct().count()<b?0:1;return r;}

```

Try it online.

**Explanation:**

```
b->n->{                // Method with two integer parameters and integer return-type
  int r=0;             //  Result-integer, starting at 0
  for(;n>0;)           //  Loop as long as input `n` is not 0 yet:
    n-=                //   Decrease `n` by:
       b.toString(++r  //    Increase the result-integer by 1 first with `++r`
                  *b   //    Multiply the new `r` by base `b`
                       //    (this is to get an additional trailing 0)
                  ,b)  //    Convert `r*b` to base-`b`,
        .chars()       //    Convert it to an IntStream of codepoint integers
        .distinct()    //    Uniquify this IntStream
        .count()       //    Get how many items are left
       <b?             //    If this is smaller than base `b`:
          0            //     Leave `n` the same by decreasing with 0
         :             //    Else (the count is equal to `b` instead):
          1;           //     Decrease `n` by 1
  return r;}           //  After the loop, return the result-integer

```

Minor note: `.distinct().count()` is 4 bytes shorter than Java 16+'s `.boxed().toSet().size()`.
> 2 votes

# Answer
# K (ngn/k), 16 bytes

```
{&x=#'?'+0,x\!y}

```

Try it online!

Takes the base as `x` and `y` as the zero-based index to generate all "pandigital" numbers up to.

* `x\!y` convert `0..y` to base `x`
* `+0,` prepend a `0`, then transpose to ensure all results contain a leading `0`
* `#'?'` count the number of distinct digits in each value
* `&x=` return indices where all digits are present
> 2 votes

# Answer
# Julia 1.0, 49 bytes

```
>(b,n=1)=1:b-1⊆digits(n;base=b)&&@show(n),b>n+1

```

Try it online!

prints the sequence indefinitely. Uses the beautiful  (same as the function `issubset`)
> 2 votes

# Answer
# Charcoal, 22 bytes

```
ＮθＮηＷη«→≧⁻¬⁻…¹θ↨ⅈθη»Ｉⅈ

```

Try it online! Link is to verbose version of code. Takes `b` and `n` as input and outputs the `n`th pandigital number in base `b`. Explanation:

```
ＮθＮη

```

Input `b` and `n` as integers.

```
Ｗη«

```

Repeat until `n` is zero.

Move right one position. This uses the current column index as the next trial pandigital integer.

```
≧⁻¬⁻…¹θ↨ⅈθη

```

If the set difference between the range from `1` to `b` and the base conversion of the trial integer is empty then decrement `n`.

```
»Ｉⅈ

```

Output the final pandigital integer.

26 bytes to output the first `n` pandigital integers:

```
ＮθＮηＷ‹Ｌυη«→Ｆ¬⁻…¹θ↨ⅈθ⊞υⅈ»Ｉυ

```

Try it online! Link is to verbose version of code. Explanation: Pushes the pandigital numbers to the predefined empty list as they are found and outputs the final list once `n` pandigital numbers have been found.
> 1 votes

# Answer
# Japt, 14 bytes

0-indexed

```
o1
@eUfXìNÎ}iV

```

Try it

```
o1\n@eUfXìNÎ}iV     :Implicit input of integers U=base & V=index
o1                  :Range [1,U)
  \n                :Reassign to U
    @               :Function taking an integer X as argument
     e              :  Test U for equality with
      Uf            :    U filtered by elements of
        Xì          :      X converted to digit array in base
          N         :        Array of all inputs
           Î        :        First element (i.e., original U)
            }       :End function
             iV     :Get the Vth integer that returns true

```
> 1 votes

# Answer
# Pyth, 11 bytes

```
.f!-tUQjZQE

```

Try it online!

Prints the first n pandigital numbers, take input as base then n.

### Explanation

```
               # implicitly assign Q = eval(input())
          E    # E = eval(input())  (second input)
.f        E    # print the first E numbers which satisfy lambda Z
       jZQ     # convert Z to base Q as a list of digits
    tUQ        # [1, 2,..., Q-1]
   -           # remove all digits in our number from the list of all digits
  !            # not (will be true for empty list)

```
> 1 votes

# Answer
# C (clang), 65 bytes

```
j,k;f(*i,b,n){for(*i=j=0;n;j=!j?*i+=k=1:j%b==k?n-=++k/b,*i:j/b);}

```

Try it online!
> 1 votes

# Answer
# Python, ~~93~~ ~~90~~ ~~87~~ 82 bytes

*-3 from @The Thonnu
-3 from @c--
-5 from @user85795*

```
def f(b,i=1,j=1,*s):i and f(b,i//b,j,i%b,0,*s);b>len({*s})or print(j);f(b,j+1,j+1)

```

Attempt This Online! Infinitely prints out values.
> 1 votes

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


title: Find Sub-matrix with matched cell 1

text:
# Question
Title: Find Sub-matrix with matched cell 1
You are given a matrix of size m x n where each cell can contain either 1 or 0. You need to find the largest square submatrix that contains only 1's. The output should be the area of the largest square submatrix.

For example, given the following matrix:

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

```

The largest square submatrix that contains only 1's is:

```
1 1 1
1 1 1
1 1 1

```

So the output should be 9 since the area of the square is 3x3 = 9.

The time complexity of your algorithm should be O(mn).

# Answer
> 7 votes
# Python NumPy, 148 bytes

```
lambda X,o=1:[B:=c(c(pad(X,1),0),1),[o:=o+(B[i,j]+B[i-o,j-o]-B[i,j-o]-B[i-o,j]==o*o)for i,j in argwhere(X)+1]]and~-o*~-o
from numpy import*
c=cumsum

```

Attempt This Online!

Should be linear in the size N (total number of elements) of the input.

### How?

Computes first the 2d partial sums B of the input. After this one off O(N) (space and time) investment we can count the number of ones in any grid rectangle in constant time using the four corners of the rectangle: B(top left)+B(bottom right)-B(top right)-B(bottom left).

We can now find the maximum in linear time by traversing the input a single time top left to bottom right. We only check for squares that have their bottom right corner at the current position. If the current point is bottom right of a new maximum square we know that the current maximum must be one less because we have already visited the top left neighbour of the current point. Therefore we need at each point only check a single square, the loop body is constant time and the loop is linear.

# Answer
> 5 votes
# MATL, ~~21~~ 19 bytes

```
lYa`9I&ZItz}x@UGaa*

```

*2 bytes saved thanks to @lmendo*

The complexity of the erosion operation is O(mn), but unfortunately with this approach, we perform erosion as many as max(m, n) times.

Try it at MATL Online

**Explanation**

```
        % Implicitly grab input as a multi-dimensional array
lYa     % Pad with a row of zeros on the top and bottom to ensure erosion works
`       % do...while loop
  9I&ZI % Perform image erosion with a 3 x 3 neighborhood
  t     % Duplicate the output
  z     % Check if there are any 1's left in the eroded result, if so, repeat
}       % End loop
x       % Delete the last element on the stack (the eroded matrix of all 0's)
@       % Get the index of the last loop iteration and
U       % Square it to get the size of the largest contiguous square of 1's
Gaa     % Check if there are any 1's in the input
*       % Multiply with the result (to account for a matrix of all 0's)
        % Implicitly display the result

```

# Answer
> 5 votes
# , 78 76 75 bytes

```
[:>./@,@;($<@,:&2@#:i.@#@,)({:*1+<./@}:)@,;.0`(0<@{1+[)`]}&.>/@,&|.0<@,0&,.

```

Try it online!

\\$\mathcal{O}(mn)\\$ using a standard dynamic programming table.

The only challenge was how to translate this essentially procedural algorithm into an array paradigm:

* First add a top-left border of zeros:

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

```
* Next generate the coordinates for what would be the nested loop in a procedural language -- that is, we traverse from left to right, top to bottom. We also add `2 2` to each, since we'll be cutting out 2x2 squares later. For example, the first element represents the 2x2 square whose top-left coordinate is `0 0`:

```
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│0 0│0 1│0 2│0 3│0 4│1 0│1 1│1 2│1 3│1 4│2 0│2 1│2 2│2 3│2 4│3 0│3 1│3 2│3 3│3 4│
│2 2│2 2│2 2│2 2│2 2│2 2│2 2│2 2│2 2│2 2│2 2│2 2│2 2│2 2│2 2│2 2│2 2│2 2│2 2│2 2│
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘

```
* Now we reverse the above list and use it in a single reduction of the input from the previous step. In each step of the reduction, we slice out a two by two square. For example in the first step of the reduction we take the top-left square:

```
0 0
0 1

```
* The reduction logic is simple. Call the value of the lower-right cell `lr`. We update `lr` as follows: `lr * (1 + min(all values except lr))`.
* Return the max value of the completed dynamic programming table.

# Answer
> 3 votes
# Charcoal, ~~88~~ ~~80~~ 46 bytes

```
≔Ｅθ⁰θＷＳ«≔⮌θη≔⟦⁰⟧θＦι⊞θ×Ｉκ⊕⌊⟦↨υ⁰⊟η↨η⁰⟧⊞υ⌈θ»ＩＸ⌈υ²

```

Try it online! Link to verbose version of code. Takes input as a list of newline-terminated bit strings. Explanation: Now a port of @Jonah's J solution.

```
≔Ｅθ⁰θ

```

Start with a row of zeros.

```
ＷＳ«

```

Loop over each input row.

```
≔⮌θη

```

Reverse the previous row totals to make them easier to process.

```
≔⟦⁰⟧θ

```

Start collecting a new row with a zero column.

```
Ｆι

```

For each cell...

```
⊞θ×Ｉκ⊕⌊⟦↨υ⁰⊟η↨η⁰⟧

```

... multiply its value with the incremented minimum of the cells above and to the left. The cell above is obtained by popping the reversed previous row, the cell to the above left is obtained as the base `0` of the popped reversed previous row and the cell to the left is obtained as the base `0` of the new row.

```
⊞υ⌈θ

```

Collect the maximum square found in this row.

```
»ＩＸ⌈υ²

```

Output the largest found square from all rows.

# Answer
> 2 votes
# Wolfram Language (Mathematica), 109 bytes

```
Catch[Do[If[AnyTrue[Erosion[ArrayPad[#,1],BoxMatrix[All,n]],#==1&,2],Throw[n]],{n,Min@Dimensions@#,1,-1}]]^2&

```

Try it online!

# Answer
> 2 votes
# Vyxal, 20 bytes

```
ɖλZɖλ÷nfṪg›*";vt;fG²

```

Try it Online!

Based on *@Jonah's* J answer.

For each 2x2 square

```
a b
c d

```

it replaces `d` with `d*(min(a,b,c)+1)` in sequence going from left to right, top to bottom. Then it takes maximum and squares it.

```
ɖλ                   # scan by:
  Z                  #   zip
   ɖλ                #   scan by:  receives [a,c], [b,d]
     ÷               #     push each to stack
      n              #     push the function argument [[a,c],[b,d]]
       f             #     flatten
        Ṫ            #     remove tail  [a,c,b]
         g           #     minimum
          ›          #     increment
           *         #     multiply
            "        #     pair [b, new d]
             ;       #   end scan
              vt     #   get the tail of each
                ;    # end scan
                 f   # flatten
                  G  # maximum
                   ² # square

```

# Answer
> 1 votes
# C, C++ : ~~231~~ ~~227~~ 196 bytes

-4 bytes thanks to EzioMercer

-31 bytes thanks to ceilingcat

```
int f(int t[],int x,int y){int z=1,j=y,i,v,w,m,k,b;for(;j--;)for(i=x;i--;)if(t[i*y+j]){v=k=1;w=0;for(m=x-i<y-j?x-i:y-j;k++<m;w=v?k:w)for(b=k*k;b--;)v=t[y*(i+b%k)+j+b/k]?v:0;z=w>z?w:z;}return z*z;}

```

TIO Link thanks The Thonnu for pointing it out

Test code :

```
int t[5][4] = {
    {1,1,1,1},
    {0,0,1,0},
    {1,1,1,0},
    {1,1,1,1},
    {1,1,1,0}
};

int main() {
    printf("r=%d\n", f((int*)t,5,4));
    return 0;
}

```

# Answer
> 0 votes
# JavaScript, 186 bytes

I know that the complexity should be `O(mn)` but here the complexity is `O((mn)^2)` :)

```
m=>eval('for(x=b=0;x<(r=m.length);++x)for(y=0;y<(c=m[0].length);++y)if(m[x][y]){for(o=s=1;o&&s<(c>r?r:c);++s)for(t=s+1;t--;)if(!m[x+s]?.[y+t]||!m[x+t][y+s]){o=0;--s;break}b=s>b?s:b}b*b')

```

Try it:

```
f=m=>eval('for(x=b=0;x<(r=m.length);++x)for(y=0;y<(c=m[0].length);++y)if(m[x][y]){for(o=s=1;o&&s<(c>r?r:c);++s)for(t=s+1;t--;)if(!m[x+s]?.[y+t]||!m[x+t][y+s]){o=0;--s;break}b=s>b?s:b}b*b')

;[
    [
        [1, 0, 1, 1, 1],
        [1, 0, 1, 1, 1],
        [1, 1, 1, 1, 1],
        [1, 0, 0, 1, 0],
    ],
    [
        [1, 0, 1, 0, 1],
        [1, 0, 1, 1, 1],
        [1, 1, 1, 1, 1],
        [1, 0, 0, 1, 0],
    ],
    [
        [1, 0, 1, 1, 1],
        [1, 0, 1, 0, 1],
        [1, 1, 1, 1, 1],
        [1, 0, 0, 1, 0],
    ],
    [
        [1]
    ],
    [
        [0]
    ]
].map(m => console.log(f(m)))
```

# JavaScript, 200 bytes

Here the complexity is much less than `O((mn)^2)` because if the algorithm find the biggest possible square it will stop

```
m=>eval('a=(c=m[0].length)>(r=m.length)?r:c;for(x=b=0;b!=a&&x<r;++x)for(y=0;b!=a&&y<c;++y)if(m[x][y]){for(o=s=1;o&&s<a;++s)for(t=s+1;t--;)if(!m[x+s]?.[y+t]||!m[x+t][y+s]){o=0;--s;break}b=s>b?s:b}b*b')

```

Try it:

```
f=m=>eval('a=(c=m[0].length)>(r=m.length)?r:c;for(x=b=0;b!=a&&x<r;++x)for(y=0;b!=a&&y<c;++y)if(m[x][y]){for(o=s=1;o&&s<a;++s)for(t=s+1;t--;)if(!m[x+s]?.[y+t]||!m[x+t][y+s]){o=0;--s;break}b=s>b?s:b}b*b')

;[
    [
        [1, 0, 1, 1, 1],
        [1, 0, 1, 1, 1],
        [1, 1, 1, 1, 1],
        [1, 0, 0, 1, 0],
    ],
    [
        [1, 0, 1, 0, 1],
        [1, 0, 1, 1, 1],
        [1, 1, 1, 1, 1],
        [1, 0, 0, 1, 0],
    ],
    [
        [1, 0, 1, 1, 1],
        [1, 0, 1, 0, 1],
        [1, 1, 1, 1, 1],
        [1, 0, 0, 1, 0],
    ],
    [
        [1]
    ],
    [
        [0]
    ]
].map(m => console.log(f(m)))
```

## Explanation

I will not explain each line of code because it is a lot and boring

Here is illustration of algorithm:

When I meet the 1 in matrix (blue) I start checking the right and bottom edges of this cell (red cells) if all red cells are 1 then I start check the right and bottom edges of red cells (green cells) and so on until where I won't meet 0 or meet the matrix edge

# Answer
> 0 votes
# Excel, 142 bytes

```
=LET(b,SEQUENCE(ROWS(a)),c,TRANSPOSE(b),MAX(MMULT(N(COUNTIF(OFFSET(INDIRECT(TOCOL(CELL("address",OFFSET(a,b-1,c-1)))),,,c,c),"<>1")=0),b^0))^2)

```

Input ***a*** is a *worksheet range* comprising the matrix. The above should preferably be placed in a worksheet different to that containing the matrix so as to avoid potential circular references.

Complexity is unfortunately \\$\mathcal{O}(m^3)\\$.

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


title: Translate to plorcly borglar

text:
# Question
Title: Translate to plorcly borglar
plorcly borglar is a "mod" created by jan Misali for the constructed language toki pona that makes words sound funny.

It involves substituting the 14 toki pona letters for funnier versions plus 2 extra rules. The substitutions are:

| toki pona letter | plorcly borglar letter |
| --- | --- |
| m | bl |
| n | gl |
| p | b |
| t | pl |
| k | cl |
| s | scr |
| w | spw |
| l | scl |
| j | shl |
| i | ee |
| u | oo |
| e | o |
| o | or |
| a | ar |

The two extra rules are:

* When an "n" in a toki pona is followed by a consonant or ends a word it is replaced with "ng" instead of "gl", so *nasin* becomes *glarscreeng* not **glarscreegl*
* When an *i* is the final letter of a word containing another vowel it becomes "y" instead of "ee", so *poki* becomes *borcly* not **borclee*, but *ni* becomes *glee* not *gly*.

<sup>*(The vowels here are "a", "e", "i", "o" and "u", "y" does not exist in toki pona at all)*</sup>

And that's it.

The challenge here is to take a sequence of space separated words that are valid in toki pona's phonotactics and convert it to plorcly borglar. If you know what that means you can get going, this is so the goal is to minimize the size of your source code as measured in bytes. Otherwise I will explain it.

Toki pona has 14 letters / phonemes, 9 consonants "m", "n", "p", "t", "k", "s", "w", "l", and "j" and 5 vowels "a", "e", "i", "o", "u". All words are built out of these characters (No upper case), but not every sequence of these characters is a valid word.

That's probably all you *need* to complete this challenge. But there are more rules that might be helpful for optimizing.

Words in toki pona consist of syllables. A syllable in toki pona is consists of a consonant, then a vowel, then an optional "n". The first syllable in a word can skip the initial consonant. For example "olin" is a valid syllable consisting of "o" + "lin". Additionally "nn" and "nm" are not legal sequences so you can't end a syllable in "n" if the next one starts with "n" or "m".

Finally the following syllables are illegal:

* *ti(n)*
* *ji(n)*
* *wu(n)*
* *wo(n)*

So they will not appear in input words.

## Test cases

```
toki pona -> plorcly borglar
nasin -> glarscreeng
poki -> borcly
ni -> glee
mi olin e sina -> blee orscleeng o screeglar
soweli lawa li ike tawa mi -> scrorspwoscly sclarspwar sclee eeclo plarspwar blee
lon sike lon ma la jan lili li tomo -> sclorng screeclo sclorng blar sclar shlarng scleescly sclee plorblor
sinpin -> screengbeeng
tenpo -> plongbor
linja -> scleengshlar

```

# Answer
> 7 votes
# Vyxal, ~~73~~ ~~68~~ ~~66~~ ~~63~~ ~~62~~ 60 bytes

```
‛ngkvvẊ÷V⌈ƛṪAa[ṫ‛iy*J;C«ƛẋ8›ŀ+λ¢Żƛvτ"Ŀ¨z`B†⁋ɽ†g<¹⌊}+.+«⌈$İṠṄ

```

Try it Online! or verify all test cases.

*-3 bytes* by emanresu A

*-3 bytes* by slightly modifying emanresu A's 64 byte solution

*-1 byte* by adapting mod 17 indexing from *@Arnauld's* JavaScript answer

*-2 bytes* by emanresu A

Start by handling the `n` special case by replacing every occurrence of `n` where special rules don't apply with `g`.

```
‛ng       # push the string "ng"
   kv     # push all vowels "aeiou"
     vẊ   # vectorize cartesian product [["na", "ne", ... ], [ga, ge, ...]]
       ÷  # push each to stack
        V # replace

```

Process each word individually, optionally replacing a `i` at the end with `y`.

```
⌈              # split on spaces
 ƛ             # map:
  Ṫ            #   remove last item
   A           #   is vowel?
    a[         #   if any is true:
      ṫ        #     tail extract
       ‛iy     #     push "ib"
          *    #     ring translate
           J   #     concatenate
            ;  # end map

```

Now comes the main part where most of the replacements happen.

```
C             # convert to a list of char codes
 «...«        # push the string "spw gl y ee shl cl scl bl ng or b  ar scr pl oo o"
      ⌈       # split on spaces
       $      # swap top two items on the stack
        İ     # index into (Vyxal indexing wraps around)
         Ṡ    # vectorizing sum
          Ṅ   # join by spaces

```

# Answer
> 4 votes
# Lexurgy, 134 bytes

```
a:
i=>y/{a,e,i,o,u} []* _ $
n=>ng/_ {m,n,p,t,k,s,w,l,j,$}
{m,n,p,t,k,s,w,l,j,u,e,o,a,i}=>{bl,gl,b,pl,cl,scr,spw,scl,shl,oo,o,or,ar,ee}

```

# Answer
> 4 votes
# Retina 0.8.2, 103 bytes

```
a
ar
o
or
e
o
u
oo
s
scr
l
scl
j
shl
p
b
w
spw
k
cl
t
pl
n([aio])
gl$1
n
ng
m
bl
([aio]\w*)i\b
$1y
i
ee

```

Try it online! Link includes test cases. Explanation: Mainly just a series of replacements. The primary ordering is that no replacement string contains letters yet to be translated. Additionally the rules that depend on vowels come after `e` and `u` are translated but before `i` is translated to reduce the number of relevant vowels to check.

# Answer
> 2 votes
# JavaScript, 260 bytes

```
s=>s.replace(/[^ ]*/g,w=>[...w].map((l,i,a)=>a.some((l,i)=>i!=(v={i:'ee',u:'oo',e:'o',o:'or',a:'ar'},b=a.length-1)&&v[l])&&l=='i'&&i==b?'y':((c={m:'bl',n:'gl',p:'b',t:'pl',k:'cl',s:'scr',w:'spw',l:'scl',j:'shl'})[a[i+1]]||i==b)&&l=='n'?'ng':c[l]||v[l]).join``) // 260

// Without map and join
s=>s.replace(/[^ ]*/g,w=>w.replace(/./g,(l,i)=>[...w].some((l,i)=>i!=(v={i:'ee',u:'oo',e:'o',o:'or',a:'ar'},b=w.length-1)&&v[l])&&l=='i'&&i==b?'y':((c={m:'bl',n:'gl',p:'b',t:'pl',k:'cl',s:'scr',w:'spw',l:'scl',j:'shl'})[w[i+1]]||i==b)&&l=='n'?'ng':c[l]||v[l])) // 260

```

Try it:

```
f=s=>s.replace(/[^ ]*/g,w=>[...w].map((l,i,a)=>a.some((l,i)=>i!=(v={i:'ee',u:'oo',e:'o',o:'or',a:'ar'},b=a.length-1)&&v[l])&&l=='i'&&i==b?'y':((c={m:'bl',n:'gl',p:'b',t:'pl',k:'cl',s:'scr',w:'spw',l:'scl',j:'shl'})[a[i+1]]||i==b)&&l=='n'?'ng':c[l]||v[l]).join``)

;[
  ['o', 'or'],
  ['toki pona', 'plorcly borglar'],
  ['nasin', 'glarscreeng'],
  ['poki', 'borcly'],
  ['ni', 'glee'],
  ['tonki', 'plorngcly'],
  ['mi olin e sina', 'blee orscleeng o screeglar'],
  ['soweli lawa li ike tawa mi', 'scrorspwoscly sclarspwar sclee eeclo plarspwar blee'],
  ['lon sike lon ma la jan lili li tomo', 'sclorng screeclo sclorng blar sclar shlarng scleescly sclee plorblor'],
  ['sinpin', 'screengbeeng'],
  ['linja', 'scleengshlar'],
].map(s=>console.log(f(s[0]), f(s[0])===s[1]));
```

# Answer
> 2 votes
# 05AB1E, 86 bytes

```
ð¡ε.•3₁‹uŒœÈĆ•S.•1и<Uº•2ô«.•3r"Δü¾n₂¸}#rö₆!õé¯à1#ryÂ‚H¦±x¦7ke•#.:Âć'eQs¦žMÃĀ*i¨¨'y«]ðý

```

Try it online or verify all test cases.

**Explanation:**

*General explanation:*

1. Split on spaces, and map over the toki pona words.
2. Do the following replacements (in order): a→ar; o→or; e→o; u→oo; s→scr; l→scl; j→shl; p→b; w→spw; k→cl; t→pl; m→bl; na→gla; no→glo; ni→gli; i→ee.
3. Replace a trailing 'ee' with 'y' if there are three or more vowels.
4. Join the plorcly borglar words back with space delimiter, and output the result.

*Code explanation:*

```
ð¡                    # Split the (implicit) input-list on spaces
                      # (note: cannot be builtin `#`, since it fails for inputs without spaces)
  ε                   # Map over each toki pona word:
   .•3₁‹uŒœÈĆ•        #  Push compressed string "aoeusljpwktmi"
     S                #  Convert it to a list of characters
      .•1и<Uº•        #  Push compressed string "nanonin"
        2ô            #  Split it into parts of size 2: ["na","no","ni","n"]
          «           #  Merge the two lists together
   .•3r"Δü¾n₂¸}#rö₆!õé¯à1#ryÂ‚H¦±x¦7ke•
                     "#  Push compressed string "ar or o oo scr scl shl b spw cl pl bl ee gla gli glo ng"
     #                #  Split it on spaces
   .:                 #  Do all replacement one by one in the current toki pona word
   Âć'eQs¦žMÃĀ*i¨¨'y« #  Handle special case trailing 'i':
   Â                  #   Bifurcate the current word; short for Duplicate & Reverse copy
    ć                 #   Extract head; pop and push remainder-string and first char
     'eQ             '#   Check if this character is an "e"
    s                 #   Swap so the remainder-string is at the top
     ¦                #   Remove the first character
      žMÃ             #   Only keep all vowels
         Ā            #   Check whether what remains is NOT an empty string
          *i          #   If both are truthy:
            ¨¨        #    Remove the trailing "ee"
              'y«    '#    And append an "y" instead
  ]                   # Close both the if-statement and map
   ðý                 # Join the plorcly borglar words back together with space delimiter
                      # (after which the result is output implicitly)

```

See this 05AB1E tip of mine (section *How to compress strings not part of the dictionary?*) to understand why `.•3₁‹uŒœÈĆ•` is `"aoeusljpwktmi"`; `.•1и<Uº•` is `"nanonin"`; and `.•3r"Δü¾n₂¸}#rö₆!õé¯à1#ryÂ‚H¦±x¦7ke•` is `"ar or o oo scr scl shl b spw cl pl bl ee gla gli glo ng"`.

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

```
s=>s[R='replace'](/\S/g,c=>'spw///ee/shl/cl/scl/bl/gl/or/b//ar/scr/pl/oo/o'.split`/`[Buffer(c)[0]%17])[R](/gl(?![aeo])/g,'ng')[R](/(?<=[aeo]\S*)ee\b/g,'y')

```

Try it online!

## How?

### Step 1: main character substitution

Because the input string is guaranteed to be valid toki pona, we only need to support the 14 toki pona letters. Taking their ASCII code modulo 17 is slightly more efficient than just subtracting 97.

| character | ASCII code | mod 17 | replaced with |
| --- | --- | --- | --- |
| 'a' | 97 | 12 | 'ar' |
| 'e' | 101 | 16 | 'o' |
| 'i' | 105 | 3 | 'ee' |
| 'j' | 106 | 4 | 'shl' |
| 'k' | 107 | 5 | 'cl' |
| 'l' | 108 | 6 | 'scl' |
| 'm' | 109 | 7 | 'bl' |
| 'n' | 110 | 8 | 'gl' |
| 'o' | 111 | 9 | 'or' |
| 'p' | 112 | 10 | 'b' |
| 's' | 115 | 13 | 'scr' |
| 't' | 116 | 14 | 'pl' |
| 'u' | 117 | 15 | 'oo' |
| 'w' | 119 | 0 | 'spw' |

It is worth noting that translated vowels can be detected with just `[aeo]` because `i`'s and `u`'s are removed entirely. We use this property for the two other steps.

### Step 2: applying the *n→ng* rule

We look for ...

```
 .--------> the substitution of 'n'
 |     .--> not followed by the substitution of a vowel
 |  ___|___
/gl(?![aeo])/g

```

... and replace each match with `ng`.

### Step 3: applying the *ee→y* rule

We look for ...

```
       .-----------> the substitution of a vowel
       |   .-------> optionally followed by non-space characters
       |   |  .----> followed by 'ee'
       |   |  | .--> followed by a space or end-of-line
      _|_ _|_ | |
/(?<=[aeo]\S*)ee\b/g

```

... and replace each match with `y`.

# Answer
> 1 votes
# Charcoal, 90 bytes

```
≔aeiouηＦη≔⪫⪪θ⁺nι⁺gιθ⪫ＥＥ⪪θ ⎇∨⌕⮌ιi›²ΣＥη№ιλι⁺…ι⊖Ｌιy⭆ι§⪪”&⌊↶k⊗3ＮＨ₂uXNＳuï^Ｔζ ﹪﹪⮌≔↙Ｖs⟧；ＶDw”d⌕βλ

```

Try it online! Link is to verbose version of code. Takes input as a newline-terminated string. Explanation:

```
≔aeiouη

```

Get the vowels separately as this saves a byte.

```
Ｆη≔⪫⪪θ⁺nι⁺gιθ

```

Loop over the vowels and change `n`s preceding a vowel to `g`s.

```
⪫ＥＥ⪪θ ...

```

With the input split into words,...

```
⎇∨⌕⮌ιi›²ΣＥη№ιλι⁺…ι⊖Ｌιy

```

... if the word ends in an `i` and contains at least `2` vowels, then replace that `i` with a `y`, and...

```
⭆ι§⪪”...”d⌕βλ

```

... replace each letter in the word with a string from a look-up table, wrapping around after `p` to save space in the table.

The best I could do as an expression was 93 bytes:

```
⪫ＥＥ⪪Ｓ ⎇∨⌕⮌ιi›²ΣＥaeiou№ιλι⁺…ι⊖Ｌιy⭆ι∨§⪪”&⌊∨<↨…¶№Pφ↔↖℅³⁰²¹↑|êＧ~3ψ⌊↓EÞ´”d⌕βλ§⪪nggl²№aeiouy§⁺ι ⊕μ

```

Try it online! Link is to verbose version of code. Takes input as a newline-terminated string. Explanation:

```
⪫ＥＥ⪪Ｓ

```

With the input split into words...

```
⎇∨⌕⮌ιi›²ΣＥaeiou№ιλι⁺…ι⊖Ｌιy

```

... if the word ends in an `i` and contains at least `2` vowels, then replace that `i` with a `y`, ...

```
⭆ι∨§⪪”...”d⌕βλ

```

... replace each letter except `n` in the word with a string from a look-up table (wrapping around after `p` to save space in the table), ...

```
§⪪nggl²№aeiouy§⁺ι ⊕μ

```

... but replace `n` with either `ng` or `gl` depending on whether it is followed by a vowel.

# Answer
> 1 votes
# Haskell \+ hgl, 152 bytes

```
v=cx<<zW(fpM<χ)
k=v"mnptkswlj"$Wr"bl gl b pl cl scr spw scl shl"
f=fo[pY$k,v"iuoae"$Wr"ee oo or ar o",pY'$"ng"<$χn,k<>pM"y"χi++pY f]

```

```
he<gc(mY$f++p_S)

```

Attempt This Online!

This is an approach using hgl's parser library, there may very well be a shorter way to write this using the regular library functions, but I wanted to put this part of the library to the test, since it needs improvement.

## Reflections

This does about how I would expect it to. However there are some holes here to be filled.

* I don't know why this keeps coming up without me fixing it: I need a function to take a parser and grab the first complete parse.
* There should be some way to split a string into substrings of a certain size. This would allow me to make `Wr"ee oo or ar o"` into `Wx2"eeoooraro"` and `Wr"bl gl pl cl scr spw scl shl b"` into `Fk"l"<"bgpc"++Wx3"scrspwsclshlb"`.
* A constant string enumerating the vowels would save bytes here, however with the above optimization, it would no longer be useful.
* There should be shortcuts for `fpM<χ` and `fpM<ʃ`, plus the bajillion variants that I could make of them.
* There should probably be a shortcut for `ʃ" "`. `p_S` works well enough in this case, but it could cost me later down the line.
* `isP` should have an infix.
* A function which combines `(<>)` an `pY` could probably be useful, since it's not uncommon to use them in tandem. If done right it could save a few bytes here.
* There should be a version of `isP` which runs both the parsers instead of dropping the separators.
* I have not implemented any sort of string compression algorithm. This would obviously be useful.

I pushed a version with some of these improvements which in total takes of 27 bytes:

### 128 bytes

```
v=cx<<zWx
k=v"mntkswljp"$Fk"l"<"bgpc"<>Wx3"scrspwsclshlb"
f=k?<>v"iuoae"(Wx2"eeoooraro")<>?hhn"ng"<>(k<>hhi"y"++pY f)

```

```
gk$f>|+p_S

```

# Answer
> 0 votes
# Python, 248 bytes

```
import re
def f(s,S=re.sub,r=''):
 for w in S('gl(?![aeo])','ng',S('\S',lambda c:'spw///ee/shl/cl/scl/bl/gl/or/b//ar/scr/pl/oo/o'.split('/')[ord(c[0])%17],s)).split():r+=('ee'==w[-2:]and sum(map(w.count,'aeiou'))>2)and w[:-2]+'y 'or w+' '
 return r

```

Attempt This Online!

Based off Arnauld's JS answer.

---
Tags: code-golf, string, parsing, natural-language
---


title: Ragged list pattern matching

text:
# Question
Title: Ragged list pattern matching
Given a pattern and a ragged list of positive integers, your task is to decide whether the pattern matches the ragged list.

The pattern is also represented by a ragged list. But in addition to positive integers, it may contain a wildcard value.

Here is the rule for matching:

* A positive integer matches the same positive integer.
* The wildcard matches anything: either a positive integer, or a ragged list.
* A ragged list matches a ragged list if they have the same length, and each pair of items at the same position matches.

For example, if we write the wildcard as `0`, then the pattern `[0, [4, [5], 0]]` matches the ragged list `[[1, 2, [3]], [4, [5], [6, [7]]]]`: here the first `0` matches `[1, 2, [3]]`, while the second `0` matches `[6, [7]]`.

Note that the wildcard cannot match a subsequence of more than 1 items in a ragged list.

You may choose any fixed value as the wildcard, as long as it is consistent.

This is , so the shortest code in bytes wins.

This is . You may use your language's convention for truthy/falsy, or use two distinct, fixed values to represent true or false.

## Testcases

Here I use `0` to represent the wildcard. The input here are given in the order `pattern, ragged list`.

Thanks @pxeger, @pajonk, @DLosc, @Deadcode for providing some interesting testcases.

### Truthy

```
[], []
[0], [1]
[1, 0], [1, [2, 3]]
[1, 0], [1, [[2, 3]]]
[1, [2, 0], 4], [1, [2, 3], 4]
[0, [4, [5], 0]], [[1, 2, [3]], [4, [5], [6, [7]]]]

```

### Falsy

```
[1], []
[0], []
[[]], []
[[]], [3]
[[4]], [4]
[0], [1, 2]
[1, 0], [1]
[0], [[1], [2]]
[1, 0, [2, 3]], [1, [2, 3]]
[1, [0, 2], 4], [1, [2, 3], 4]
[[0], [4, [5], 0]], [[1, 2, [3]], [4, [5], [6, [7]]]]

```

# Answer
> 12 votes
# Elixir, 1 byte

```
=

```

Yes, Elixir's equality/pattern match operator functions exactly as requested when input is provided as plain code with wildcards indicated by underscore`_`. The output is by presence/absence of error (passed = match, error = no match, see the Test Suite

Since validity of this way of taking input has been questioned in comments, here is also the conventional function doing the same, with all the boilerplate counted in code...

# Elixir, 28 bytes

```
&Code.eval_string&1<>"="<>&2

```

Try it online!

# Answer
> 6 votes
# Haskell, 44 bytes

```
W#_=1
p#a|p==a=1
L(h:p)#L(f:r)|h#f>0=L p#L r
```

Attempt This Online!

More readable:

```
W # _ = True
p # a
 | p == a
 = True
L (h:p) # L (f:r)
 | h # f
 = L p # L r

```

Uses a custom sum type for ragged list, where `W` represents a wildcard:

```
data Ragged = W | N Int | L [Ragged]
 deriving Eq

```

As I understand it, I don't have to include that type definition in my score?

Maybe `deriving Eq` is not allowed, in which case it can be manually instantiated for only 1 byte more:

## Haskell, 45 bytes

```
W==_=1>0;N p==N a=p==a;L p==L a=p==a;_==_=1<0
```

Attempt This Online!

Although now I'm not sure if I have to include the instance declaration in my score.

More readable:

```
W == _     = True
N p == N a = p==a
L p == L a = p==a
_ == _     = False

```

# Answer
> 6 votes
# tinylisp, ~~71~~ ~~81~~ ~~70~~ 79 bytes

Being a language whose syntax is entirely made of ragged lists, you'd expect tinylisp to be good at parsing them, and it indeed doesn't do that bad of a job at it.

```
(d F(q((A B)(i(a(e A 0)(e A B))0(i(a(e()B)(e(v B)B))1(a(F(h A)(h B))(F(t A)(t B

```

Takes two lists as arguments, and outputs falsy (zero) if they match, or truthy (positive int) if they don't.

Edit +10 bytes: @DLosc pointed out that my code actually failed for some cases containing an empty list as an element.

Edit -11 bytes: @DLosc suggested `(e(v A)A)` for the troublesome conditional, and indeed it does work, and saves a byte off my original size.

Edit +9 bytes: Two more fixes for problems pointed out by alephalpha and DLosc, changing `(e(v A)A)` to `(e(v B)B)` and adding a test if `B` is nil to the second if, I think this actually works perfectly now

Try it online!

# Answer
> 4 votes
# Python 2, 34 bytes

```
f=lambda p,a:a+a!=p+p>0<map(f,p,a)
```

Attempt This Online!

Outputs via presence or absence of an error. If there's no error, the pattern matches. If there is an error, the pattern doesn't match.

~~-16~~ -13 bytes thanks to @loopy walt

# Answer
> 4 votes
# , ~~111~~ ~~110~~ ~~104~~ 82 bytes

*Edit: -22 bytes thanks to @Giuseppe.*

```
f=\(p,l,`+`=is.list,`-`=length)`if`(+p,+l&-p==-l&&all(mapply(f,p,l)),!p|!+l&&p==l)
```

Attempt This Online!

Straightforward recursion.

# Answer
> 3 votes
# Retina, ~~65~~ ~~63~~ ~~57~~ 56 bytes

```
~(L$`^.+
\n$&$
_
(\d+|<((?<_><)|(?<-_>>)|\d|,)+(?(_)^)>)

```

Try it online! Takes two newline-separated `<>`-wrapped lists but link is to test suite that deletes spaces, splits on semicolons and converts other types of brackets for convenience. Uses `_` to represent the wild card. Edit: Saved ~~6~~ 7 bytes thanks to @Deadcode pointing out that I don't need to use `[]`-wrapped lists or support spaces. Explanation:

```
~(`

```

Evaluate the result of the transformations below on the original input. Since they result in a single line, this makes Retina attempt to match the input against the result.

```
L$`^.+
\n$&$

```

Take only the first line of the input and wrap it in `\n` and `$` so that it will match against the second line of the input.

```
_
(\d+|<((?<_><)|(?<-_>>)|\d|,)+(?(_)^)>)

```

Replace each `_` with a match against either a non-negative integer or a list, using a .NET balancing group to ensure that the list is properly balanced. A named capturing group `?<_>` is used here because .NET allows capturing groups to be reused in this way and it's golfier than calculating the capturing group number.

# Answer
> 2 votes
# Charcoal, 56 bytes

```
¹≔⟦Ａ⟧θＦθ«≔§ι⁰η≔§ι¹ζ¿⁼⁺ηυη¿∧⁼⁺ζυζ⁼ＬηＬζＦＬη⊞θＥι§λκ⎚¿∧η¬⁼ηζ⎚

```

Try it online! Link is to verbose version of code. Takes input as a pair of two ragged lists with `0` indicating a wildcard and outputs a Charcoal boolean, i.e. `-` for matching, nothing for mismatching. Explanation:

```
¹

```

Start by assuming that the lists match.

```
≔⟦Ａ⟧θＦθ«

```

Start a breadth-first search of the lists.

```
≔§ι⁰η≔§ι¹ζ

```

Extract the corresponding sublists that are being searched.

```
¿⁼⁺ηυη

```

If the pattern list element is a sublist, ...

```
¿∧⁼⁺ζυζ⁼ＬηＬζ

```

... then if the list element under test is a sublist of the same length, then...

```
ＦＬη

```

... for each pair of elements of the sublists...

```
⊞θＥι§λκ

```

... push the corresponding pair to the search list.

If the element under test wasn't a sublist of the same length then clear the canvas.

```
¿∧η¬⁼ηζ⎚

```

Otherwise, when the pattern element isn't a sublist, then if it is truthy but not equal to the element under test then clear the canvas.

Support for zeros by using empty strings as wildcard is possible at a cost of 2 bytes:

```
¹≔⟦Ａ⟧θＦθ«≔§ι⁰η≔§ι¹ζ¿⁼⁺ηυη¿∧⁼⁺ζυζ⁼ＬηＬζＦＬη⊞θＥι§λκ⎚¿∧⁺ηω¬⁼ηζ⎚

```

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

# Answer
> 2 votes
# Jelly, 13 bytes

```
ßȯŒḊ?"ḣL{
ç⁹⁼

```

A dyadic Link that accepts the pattern (with `0` as the wildcard) on the left and the potential match on the right and yields `1` for a match or `0` for no match.

**Try it online!**

### How?

```
ßȯŒḊ?"ḣL{ - Helper Link: pattern P; potential A
     "    - P zip A applying:
    ?     -   if...
  ŒḊ      -   ...condition: depth (of element of P)
ß         -   ...then: call this Helper Link (with element of P and element of A)
 ȯ        -   ...else: (element of P) logical OR (element of A)
       L{ - get length of P
      ḣ   - head (the zip result) to index (length of P)

ç⁹⁼ - Link: pattern P; potential A
ç⁹  - P Helper Link A
  ⁼ - equals A?

```

# Answer
> 2 votes
# Ruby, 57 bytes

```
f=->t,a{a!=t&&t&&t.zip(a).map{|r|[f][t.size^a.size][*r]}}

```

Try it online!

Uses `nil` as filler. (`false` will also work)

Ports @pxeger's Python answer.

# Answer
> 2 votes
# Regex (Perl / PCRE), ~~63~~ ~~60~~ ~~56~~ 53 bytes

```
((_?)(\2.)?(?=.*
(\4?(?(?=\2)\3|(\d+,?|{(?5)*})))))+

```

Try it online! (Perl)
Try it on regex101 (PCRE)

The wildcard is `_` and the delimiter between the pattern and the ragged list is a newline.

This regex works by going through the pattern one character at a time; any character other than `_` must be matched with the identical character in the pattern, and `_` is matched with any positive integer or ragged list. This is done while cumulatively building up a backreference of the full ragged list, as each piece of it is matched.

Due to the optimization of requiring the input to be well-formed, only the ragged lists matched with `_` need to be checked for matched brackets. The regex uses `{` and `}` (curly braces) as its brackets to avoid having to `\`-escape them. Similarly, spaces must not be present in the input.

#### Explanation

`(` ... `)+`
Match what is inside any nonzero number of times.

`(_?)(\2.)?`
Consume the current pattern character. If it is `_`, set `\2` to contain it. Otherwise, set `\2` to be empty and `\3` to contain the character. Note that the latter can also happen if the character is `_`, but this cannot lead to a subsequent match, because `_` cannot be in the input ragged list.

`(?=.*`
... `)`
Process the input ragged list in a lookahead, so that outside this lookahead, the input pattern can still be processed picking up where it left off. The `.*` skips over what remains of the input pattern, and the newline skips over the newline delimiter.

`(\4?(?(?=\2)\3|(\d+,?|{(?5)*})))`
Validate that the appropriate section of the input ragged list matches the current character of the input pattern, capturing the entire portion of it matched so far (starting from its beginning) in `\4`.

`\4?`
If this is the first character being processed, `\4` will be unset, and this will consume zero characters of the input ragged list. Otherwise, this can either match with what `\4` has been set to, or match an empty string. Since the regex is designed only to work on well-formed input, it will in practice always match `\4` (the portion of the input ragged list already matched) when it is set, skipping to the appropriate part of the input ragged list to match against the corresponding current input pattern character. The unoptimized version of this would be `(?(4)\4)` or `\4?+`.

`(?(?=\2)` ... `|` ... `)`
If `\2` matches (without consuming it), match against the first part, otherwise match against the second part. `\2` will contain `_` if that (a wildcard) is the current pattern character, otherwise it will be empty. Since well-formed input can never contain `_` in the input ragged list, `\2` will only match if the current pattern character is *not* a wildcard.

`\3`
Match against the current non-wildcard character.

`(\d+,?|{(?5)*})`
Match any single positive integer or ragged list. Balancing of opening and closing braces is done here using recursion; `(?5)` recursively calls the entire expression above. Since the input is assumed to be well-formed, we can get away with the optimization of not enforcing that there is an integer directly before and after every comma.

Once the entire input pattern has been processed, the newline delimiter is skipped, enforcing that the entire input pattern has been matched against. There is no need to anchor at the beginning or end of the input string, because as long as the input is well-formed (with balanced braces), there is no way that the entire input pattern can be matched without also matching the entire input ragged list.

# Regex (.NET), 71 bytes

```
(?<=(.)+);(?<-1>\1|(?<=(?=\1)_.*)(\d+|<((<)|(?<-4>>)|\d|,)+(?(4)^)>))+$

```

Try it online!

The wildcard is `_` and the delimiter between the pattern and the ragged list is `;`. The brackets are `<` and `>`.

This regex works by capturing the input pattern character by character in reverse, pushing it onto the Balanced Group stack of Group 1. Then the input ragged list is tested against this by popping the stack in a loop, and for each popped character, matching directly against it if possible, and otherwise, checking if the popped character is `_`, and if it is, matching against any ragged list with balanced brackets.

#### Explanation

`(?<=(.)+);`
Push the input pattern onto the Group 1 stack, one character at a time in reverse order, then skip to the input ragged list.

`(?<-1>` ... `)+$`
Pop the Group 1 stack in a loop, executing the following for each popped character, and then assert that the end of the string (and thus the end of the input ragged list) has been reached.

`\1|(?<=(?=\1)_.*)(\d+|<((<)|(?<-4>>)|\d|,)+>)`
What to execute for each character popped from the Group 1 stack.

`\1`
If the character matches, consume it. This can never happen if the character is `_`, because a well-formed input ragged list can't contain that.

`|`
Otherwise, execute the following.

`(?<=(?=\1)_.*)`
Assert that the pattern character is `_`.

`(\d+|<((<)|(?<-4>>)|\d|,)+(?(4)^)>)`
Match either a single positive integer, or a ragged list with balanced brackets.

`(<)` \- push an opening bracket onto the Group 4 stack
`(?<-4>>)` \- pop an entry from the Group 4 stack, and match a closing bracket
`\d|,` \- match a numeral or comma
`(?(4)^)` \- assert that the Group 4 stack is empty (literally, assert that if the Group 4 stack is not empty, we're at the beginning of the input string)

# Answer
> 1 votes
# Python3, 114 bytes:

```
T=type
f=lambda x,y:len(x)==len(y)and all(a==0 or(T(a)==T(b)and(f(a,b)if list==T(a)else a==b))for a,b in zip(x,y))

```

Try it online!

# Answer
> 1 votes
# Wolfram Language (Mathematica), 6 bytes

```
MatchQ

```

Try it online!

Built-in. Uses `_` as a wildcard. Input `[list, pattern]` or `[pattern][list]`.

---

Non-built-in:

### Wolfram Language (Mathematica), 33 bytes

```
##=!=0&&Or@@#0@@@Check[{##},]&

```

Try it online!

Uses `0` as a wildcard. Input in any order. Returns `False` if they match, or `Null` otherwise.

### Wolfram Language (Mathematica), 23 bytes

```
##=!=0&&#0@@@({##})&

```

Try it online!

Uses `0` as a wildcard. Input in any order. Returns by error presence/absence.

# Answer
> 1 votes
# Factor \+ `match`, 7 bytes

```
(match)

```

Try it online!

# Answer
> 1 votes
# Pip `-x`, 25 bytes

```
aN[0b]|$&0*g&a#=b&$&fMZab

```

Takes the pattern and the list as command-line arguments in Pip list syntax, using `0` as the wildcard value. Outputs `1` for truthy, empty string or `0` for falsey. Attempt This Online! Or, verify all test cases.

### Explanation

This is a recursive full program. The `-x` flag evaluates the program's arguments, which allows us to take lists as inputs.

```
aN[0b]|$&0*g&a#=b&$&fMZab
                          ; a is 1st arg (pattern); b is 2nd arg (list)
                          ; g is list of both args; f is main function
  [0b]                    ; List containing 0 and b
aN                        ; Is a in that list? (I.e. is a 0 or does a equal b?)
      |                   ; If that result is truthy, return it; if not:
         0*g              ; 0 times g (applies to ints, maps over lists)
       $&                 ; Fold on AND (truthy iff both elements are truthy):
                          ; - If a or b is an int (and we know they're not equal
                          ;   because we already checked), we get a falsey result
                          ; - If a or b is an empty list (and we know they're not
                          ;   both empty because we already checked), that's falsey
                          ; - Otherwise, both are nonempty lists and we get truthy
            &             ; If that result is falsey, return it; if not:
             a#=b         ; Are a and b the same length?
                 &        ; If that result is falsey, return it; if not:
                    f     ; Apply the main function recursively
                     MZab ; to corresponding items from a and b
                  $&      ; Fold on AND (truthy iff all elements are truthy)

```

---
Tags: code-golf, decision-problem, ragged-list, pattern-matching
---


# Question
Title: Output a Latin square with a program which is a Latin square
A Latin square of order n is text which is arranged as a square of n lines by n columns, contains n different characters, and each character appears once in each line and column. For example, here is a Latin square of order 9:

```
Code gOlf
ode gOlfC
de gOlfCo
e gOlfCod
 gOlfCode
gOlfCode
OlfCode g
lfCode gO
fCode gOl

```

Make a program which outputs a Latin square of order n (like in this other challenge), but the program must also be a Latin square of order n. The output must be different (i.e. not a quine) - use different symbols and/or in different order.

Some notes on formatting:

1. Output to stdout or return a string which could be printed to stdout directly (i.e. it should contain newline bytes).
2. Leading and trailing spaces are allowed only if the square doesn't otherwise contain spaces.
3. Leading and trailing newlines are allowed.
4. Tab and other control characters are allowed only if your system can print them without disturbing the square shape.
5. Usual Code Golf - your score is the number of bytes in your program, so a score should normally be n²+n-1 or n²+n.
6. Include your program's output in your answer, if you think it looks pretty.

---

As noted by tsh, n = 1 is uninteresting, so let's add a restriction n \> 1.

# Answer
> 15 votes
# C89 (using implicit `int`), 811 bytes (\\$ n = 28 \\$)

```
ps0,f;to(char/*1+){2-u9]y=}[
+,}2=s09f-(put1;*/oy[]){char
u[9012]={f};/*c-as)rt(,op+hy
th,+p-;])0r}a92{s1([fc*/oy=u
;for(ps0/*t]9y=u,h1-}2[c{a)+
o1ayc{-}[]f+th,r)(u*/=29;ps0
-=1;u[ps0/*2)fa+hrc,9o}(]ty{
}c2)y9rtp;,[so+h-0fu{a(1*/]=
92-ps0+/*h1t;)o}{=yc(ru,a][f
s]+9a)1(}r-,[upy;f0=c{oht*/2
);for(/*1p9{]0[s2-}+a,=yhuct
]{(h[,ay+sp-}r)0ucto1*/f=29;
f-=1;oy[29/*ps(,t{+0)}]arcuh
au[=of,h;+{sc}y9(t2)p0r*/-1]
=oy[0])puts/*c;(92r1+-h}f{,a
29cf]a[{,u0rh-stp*/(oy+=1);}
/*r{th};-)=u,]920+pfy1a[so(c
,+s/h*{2]a;1=[0py9-trfc)u}o(
{t]u+c2)s1yo-,/[r}a9=hp0(;f*
1(*c{/u+a2])o=}f[,9shty;-0rp
y0t-/r(f={a9+1uoc][h*p;s},2)
*)ha9}fcy,u({+r=o[]p;/0-21ts
(/{]2yc-o}+hfpta=u*;s91r)[0,
cy)t*=91r[2f0a-]};h/,s{u+(po
[au*}+=rh(cy2{f)/o,]0;tp9s-1
0}/s,1hatyoc(;]*fp={u)-2[r+9
rp;()u*,co[=y2h/1as}]+ft09{-
hrp}-tou9=)01({c]y;a2[s+,f*/

```

Try it online

This is a function called `to` which prints the following output:

```
]\[ZYXWVUTSRQPONMLKJIHGFEDCB
\[ZYXWVUTSRQPONMLKJIHGFEDCB]
[ZYXWVUTSRQPONMLKJIHGFEDCB]\
ZYXWVUTSRQPONMLKJIHGFEDCB]\[
YXWVUTSRQPONMLKJIHGFEDCB]\[Z
XWVUTSRQPONMLKJIHGFEDCB]\[ZY
WVUTSRQPONMLKJIHGFEDCB]\[ZYX
VUTSRQPONMLKJIHGFEDCB]\[ZYXW
UTSRQPONMLKJIHGFEDCB]\[ZYXWV
TSRQPONMLKJIHGFEDCB]\[ZYXWVU
SRQPONMLKJIHGFEDCB]\[ZYXWVUT
RQPONMLKJIHGFEDCB]\[ZYXWVUTS
QPONMLKJIHGFEDCB]\[ZYXWVUTSR
PONMLKJIHGFEDCB]\[ZYXWVUTSRQ
ONMLKJIHGFEDCB]\[ZYXWVUTSRQP
NMLKJIHGFEDCB]\[ZYXWVUTSRQPO
MLKJIHGFEDCB]\[ZYXWVUTSRQPON
LKJIHGFEDCB]\[ZYXWVUTSRQPONM
KJIHGFEDCB]\[ZYXWVUTSRQPONML
JIHGFEDCB]\[ZYXWVUTSRQPONMLK
IHGFEDCB]\[ZYXWVUTSRQPONMLKJ
HGFEDCB]\[ZYXWVUTSRQPONMLKJI
GFEDCB]\[ZYXWVUTSRQPONMLKJIH
FEDCB]\[ZYXWVUTSRQPONMLKJIHG
EDCB]\[ZYXWVUTSRQPONMLKJIHGF
DCB]\[ZYXWVUTSRQPONMLKJIHGFE
CB]\[ZYXWVUTSRQPONMLKJIHGFED
B]\[ZYXWVUTSRQPONMLKJIHGFEDC

```

I started with code like this:

```
i;
to()
{
    char u[100] = {0};
    char *s = u;
    // Fill the string with some printable bytes
    for (i = 29; i -= 1; u[i] = 94 - i)
        ;
    for (i = 29; i -= 1; )
    {
        puts(s += 1); // print the string
        s[29 - 1] = s[0]; // rotate the string
    }
}

```

I arranged it as a sequence of strings which all have unique characters, padded with spaces in such a way that I could replace spaces with comments later. Then I tweaked the code repeatedly, until all columns also contained unique characters. This was not easy!

The result was this:

```
ps0,f;to(char
                  oy[]){char
u[9012]={f};
                        oy=u
;for(ps0
                     =29;ps0
-=1;u[ps0
                          ]=
92-ps0+
                           2
);for(
                       f=29;
f-=1;oy[29
                         -1]
=oy[0])puts
                   (oy+=1);}

```

I had to use multi-character variable names to make all the string fragments have different lengths. I tried to use a minimal subset of characters, but ultimately I failed to satisfy all constraints and added an extra character `y`. So it seems possible to golf this further (if you want to do this — good luck, I'm out!)

Then, I made a script which completes any partially filled rectangle to a Latin square, randomizing characters inside the comments and doing backtracking.

# Answer
> 12 votes
# APL (Dyalog Unicode), 109 bytes

Full program that prints to stdout.

```
(↑⍋⌽¨⊂) ⎕D
↑⍋⌽¨⊂) ⎕D(
⍋⌽¨⊂) ⎕D(↑
⌽¨⊂) ⎕D(↑⍋
¨⊂) ⎕D(↑⍋⌽
⊂) ⎕D(↑⍋⌽¨
) ⎕D(↑⍋⌽¨⊂
 ⎕D(↑⍋⌽¨⊂)
⎕D(↑⍋⌽¨⊂)
D(↑⍋⌽¨⊂) ⎕

```

Try it online!

`⎕D` the digits `0` through `9`

`(``)` apply the following tacit function:

on the entire argument:

`⌽¨` rotate each of the following amounts:

the grade (the permutation that would sort the argument, i.e. the indices 1 through 10)

mix the list of strings into a character matrix

The first rotation ends up having unbalanced parentheses and therefore quits with an error, causing no further output on stdout.

# Answer
> 10 votes
# Thunno, 11 bytes (\\$ n = 3 \\$)

```
drz
rzd
zdr

```

Attempt This Online!

Reads its own source code and reverses it. (I can't see anything in the question which disallows this.)

#### Output

```
rdz
dzr
zrd

```

#### Explanation

Only the last line matters:

```
zd   # Read source code and push to stack
  r  # Reverse so the output is different
     # Implicit output

```

# Answer
> 8 votes
# , 239 bytes (n=15)

```
choue=:i.+|~/15
i=:15.|+/~choue
=echo|.u:i+/~51
51|i.+/~=:eouhc
15/.|~+:eui=coh
+.5|:1=cu/~iheo
|ih~/o51+c.:e=u
o|ie15~/c.hu+:=
~+15cuoh|e/.=i:
huec+/1o~5=|:.i
u/~=hci|o1:e5+.
/~.:=eu51hoci|+
:o+/~ihe5=u1.c|
.cu+i:e=ho15|/~
e:=ouhc.i|5+1~/

```

Try it online!

---

## Explanation

```
choue=:i.+|~/15

```
* `|~/` is a no-op on 15: it inserts `|~` between the items, but there's only one item.
* `+` is complex conjugation, which is also a no-op on 15.
* `i.` makes a list of the first 15 nonnegative integers.
* That list is assigned to `choue`.

```
i=:15.|+/~choue

```
* `+/~` makes an addition table of the integers in `choue`.
* `15.` `|` reduces it modulo 15; the full stop is used as a decimal point.
* The result is assigned to `i`.

```
=echo|.u:i+/~51

```
* `+/~` here ends up being the same as plain addition, adding 51 to each item of `i`.
* `u:` converts numbers to characters.
* `|.` reverses the result. (Something had to be put here to separate `echo` from `u:`.)
* `echo` outputs the table of characters.
* `=` doesn't matter because it is applied after the `echo`.

```
51|i.+/~=:eouhc

```
* This line is a syntax error, ending execution.

# Answer
> 5 votes
# Jelly, 29 bytes

```
Rṙ`Y5
ṙ`Y5R
`Y5Rṙ
Y5Rṙ`
5Rṙ`Y

```

Try it online!

All lines but the last are ignored.

```
5R       [1 .. 5]
  ṙ      rotated left
   `     each of [1 .. 5] times.
    Y    Join on newlines.

```

# Answer
> 4 votes
# 05AB1E, 55 bytes (\\$ n = 7 \\$)

```
0oā._»2
oā._»20
ā._»20o
._»20oā
_»20oā.
»20oā._
20oā._»

```

Try it online!

#### Output

```
0485761
4857610
8576104
5761048
7610485
6104857
1048576

```

#### Explanation

We can ignore everything but the last line.

```
20       # Push 20
  o      # Push 2 ** 20 (1048576)
   ā     # Push [1..7]
    ._   # Rotate 1048576 that many times
      »  # Join by newlines
         # Implicit output

```

# Answer
> 3 votes
# Vyxal `j`, 41 bytes (\\$ n = 6 \\$)

```
∪:żvǓk
:żvǓk∪
żvǓk∪:
vǓk∪:ż
Ǔk∪:żv
k∪:żvǓ

```

Try it Online!

#### Output

```
eiouya
iouyae
ouyaei
uyaeio
yaeiou
aeiouy

```

#### Explanation

Only the last line matters, so everything else can be ignored.

```
k∪      # Push "aeiouy"
  :ż    # Duplicate and push [1..6]
    vǓ  # Rotate the string that many places
        # Implicit output, joined by newlines

```

---
Tags: code-golf, restricted-source, printable-ascii
---


title: Mixed fractions without delimiters

text:
# Question
Title: Mixed fractions without delimiters
Help! I printed a bunch of rational numbers with no spaces or other delimiters other than the `/` in the fractions. There is, however, good news! All the numbers are positive. There are no improper fractions, every numerator is less than its denominator and any integers are represented directly, not as fractions. Any non-integers greater than 1 are represented as an integer followed by a fraction. Every fraction is reduced to lowest terms, no numerator and denominator have any common factors other than 1.

Using this information, and given a string that I've printed, I need you to tell me what the original numbers could have been. If there are multiple possibilities, I want to know all of them.

## Examples

given as `input` =\> `output`.

`1` =\> `1`

`1/2` =\> `1/2`

`12/3` =\> `1`,`2/3` and `1 2/3` (or, equivalently, `5/3`)

`2/34` =\> `2/3`,`4` (cannot be `2/34` because 2 and 34 share a factor of 2)

`12/35` =\> `12/35` and `1 2/35` and `1`,`2/35` and `1`,`2/3`,`5`

`12/345/678/9` =\> `1`,`2/3`,`4`,`5/6`,`7`,`8/9` and `5/3`,`29/6`,`71/9` and `5/3`,`45/67`,`8/9` and ...

## Rules

You can assume there is at least one valid way to delimit the input.

Your results can contain improper or mixed fractions, you can represent 5/3 as `5/3` or `1 2/3`. You can use any kind of delimiters, as long as each type of delimiter (start and end of a list, between numbers, between integer and fraction in a mixed fraction, between numerator and denominator in a fraction) is unique and consistent. You can take input from stdin, or function parameters, or command line options. You can print your results, or return them from a function, or even just leave them in a variable.

# Answer
# Haskell, 480 bytes

```
c""=[]
c('/':x)=c x
c x|(f,b)<-span(/='/')x=f:c b
i x[]=[[x]]
i x(y:z)=(x:y):z
s[x]=[[[x]]]
s(x:y)=[p|s<-s y,p<-[i x s,[x]:s]]
m[[b],[c]]=[[b++'/':c]]
m[[a,b],[c]]=[[a++'+':b++'/':c],[a,b++'/':c]]
m([b]:((c:d:e):f))=map((b++'/':c):)$m$(d:e):f
m([a,b]:((c:d:e):f))=[p++s|s<-m((d:e):f),p<-m[[a,b],[c]]]
m((x:y):z)=map(x:)$m$y:z
l=length
o i=[o|s<-sequence$map s$c$i,and[n<d&&gcd n d==1|i<-[1..l s-1],
 let[n,d]=read<$>[last$s!!pred i,s!!i!!0]],
 and[l(s!!i)>1|i<-[1..l s-2]],o<-m s]

```

Try it online!

# Haskell, 650 bytes

```
chunks""=[]
chunks('/':xs)=chunks xs
chunks xs|(front,back)<-span(/='/')xs=front:chunks back

insert x[]=[[x]]
insert x(y:ys)=(x:y):ys

splits[x]=[[[x]]]
splits(x:xs)=[p|s<-splits xs,p<-[insert x s,[x]:s]]

merges[[b],[c]]=[[b++'/':c]]
merges[[a,b],[c]]=[[a++'+':b++'/':c],[a,b++'/':c]]
merges([b]:((c:d:e):f))=[(b++'/':c):s|s<-merges$(d:e):f]
merges([a,b]:((c:d:e):f))=[p++s|
 s<-merges((d:e):f),p<-merges[[a,b],[c]]]
merges((x:xs):ys)=map(x:)$merges$xs:ys

origins input=[m|s<-sequence$map splits$chunks$input,
 and[length(s!!i)>1|i<-[1..length s-2]],
 and[n<d&&gcd n d==1|i<-[1..length s-1],
 let[n,d]=read<$>[last$s!!pred i,s!!i!!0]],m<-merges s]

```

Try it online!
> 3 votes

# Answer
# JavaScript (V8), ~~188~~  185 bytes

```
f=([c,...x],y='')=>c?f(x,y+c)-f(x,y+[,c])-f(x,y+' '+c):y.split`,`.some(e=>e.replace(/(?:[1-9]\d* ?)??(?:([1-9]\d*)\/([1-9]\d*))?$/,g=(_,a,b)=>+a>=b|!_?1:a?g(1,b%a,a):b-1||''))||print(y)

```

Try it online!
> 3 votes

---
Tags: code-golf
---


title: Source Code Byte Frequency

text:
# Question
Title: Source Code Byte Frequency
# Source Code Byte Frequency

---

Write a program that get a single byte character as an input and prints the frequency of that byte in the program's source code as an output.

**Examples:**

Assuming my program is: `ab#cd%b` then the output of the program should be (each line is a separate execution):

```
input         output
-----         ------
  a           0.1428571428571429
  b           28.57%
  #           14.2857143%
  c           1/7
  B           0

```

---

### Rules:

* The format of the proportion does not need to be consistent across all inputs, e.g. a fraction for one, decimal for another, percent for a third, plain zero for non-existent byte, etc...
* If a proportion is represented as decimal, the result must be accurate to at least 4 decimal places.
* Source code should be at least 1 byte long.

---

### Scoring:

This is - the shortest code (≥1) wins.

---

(It would also be fun to get the shortest code in every language, so don't hesitate to post multiple entries)

# Answer
> 34 votes
# JavaScript (ES6), 40 bytes

All used characters appear exactly twice. Therefore, this returns either `0` or 2/40 = `0.05`.

```
F=_=>(F+'+./02>cdeilnsu').includes(_)/20

```

Try it online!

# Answer
> 33 votes
# Retina 0.8.2, 1 byte

```
1

```

Try it online! Link includes... test cases? But there's not much to test really. The program counts the number of `1`s in the input, so if the input is `1`, then this is 100% of the program's code, and the program outputs `1` accordingly, otherwise the input character is not in the program's code, and therefore the output is `0`.

# Answer
> 12 votes
# Python 2, <sup>~~52~~</sup> 50 bytes

```
s="print`'s=;exec s'+s`.count(input())/50.";exec s

```

Try it online!

---

# Python 3.8 (pre-release), 53 bytes

```
exec(s:="print(('exec(s:=%r)'%s).count(input())/53)")

```

Try it online!

---

# Python 3, 55 bytes

```
s="print(('s=%r;exec(s)'%s).count(input())/55)";exec(s)

```

Try it online!

# Answer
> 9 votes
# Japt, 2 bytes

```
èè

```

Try it

## Explanation

Counts number of times `è` occurs in the input. So outputs 1 if input is `è` otherwise 0

# Answer
> 9 votes
# Unary, ~~~9.84e57~~ ... ~~~3.58e42~~ 59,599,717,533,291,089,242,285,960,261,852 (~5.96e31) bytes thanks to Jo King!

```
[encoded data, 62797 characters]...why in the world have you scrolled this far? It's Unary - it's just going to be zeroes forever...

```

Outputs `1` if the input is `0`, `0` otherwise.

---

## brainf\*** code (35 bytes)

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

```

Try it online!

# Answer
> 8 votes
# Actually, 5 bytes

```
5○Qc/

```

Try it online!

## Explanation

```
 ○    Push the byte of input
  Qc  Count how many times it's in the source code
5   / And divide by five

```

# Answer
> 7 votes
# JavaScript (Node.js),  ~~61~~  34 bytes

-16 bytes thanks to *MatthewJensen*

-11 bytes thanks to *Arnauld*

```
f=c=>--('f='+f).split(c).length/34

```

Try it online!

# Answer
> 7 votes
# APL (Dyalog Unicode), inspecting its own source code, 20 bytes

```
 f←{(+/÷≢)⍵=,⎕CR'f'}

```

Try it online!

Note the leading space in the code. When a function is defined in APL, the interpreter converts the source code to its own whitespace formatting (strips most spaces but inserts some at certain places, including the start of each line). The system functions that retrieve the source code (e.g. `⎕CR` and `⎕NR`) give the converted representation.

`f←` part cannot be removed from the score because the source inspection depends on itself being defined as `f`.

```
⎕CR'f'  ⍝ Get the char matrix representation of function f
,       ⍝ Convert the 1-row matrix to a vector
⍵=      ⍝ Compare each char of above with the input char
(+/÷≢)  ⍝ Compute the average

```

---

# APL (Dyalog Unicode), quine-like, 26 bytes

```
(+/÷≢)⍞=13⍴'''(+/÷≢)⍞=13⍴'

```

Try it online!

There is no escape sequence in APL's string literal. Instead, one single quote is represented by two single quotes, so the literal `'''(+/÷≢)⍞=13⍴'` gives the string `'(+/÷≢)⍞=13⍴`.

```
'...'   ⍝ Start with the string literal
13⍴     ⍝ Cycle-take first 13 chars, adding `'` at the start to the end
⍞=      ⍝ Compare with single-char input from stdin
(+/÷≢)  ⍝ Compute the average

```

# Answer
> 6 votes
# 05AB1E, ~~26~~ 23 bytes

-3 bytes by using the shortest standard quine in 05AB1E.

```
0"D34çýI¢23/"D34çýI¢23/

```

Try it online!

## Explanation

```
0                       Push a 0 for double quote insertion later.
 "D34çýI¢23/"           Push the quine string.
             D          Duplicate the quine string.
              34çý      Insert a double quote between rach item on the stack.
                  I¢    Count how many times the input appeaes
                    23/ And divide by 23.

```

# Answer
> 6 votes
# Ruby `-nl`, <sup>~~56...38~~</sup> 36 bytes (without reading own source code)

```
p~%r,[+-2\[-\]p~%r+2?./8:],?1.0/18:0

```

Try it online!

Each of the 18 distinct characters in the code appears twice. The input is tested against a comma-delimited regexp. The outer `[]` is a character class containing literal characters plus two character ranges: `+-2` is equivalent to the literal characters `+,-./012` and `\[-\]` is equivalent to the literal characters `[\]`. The code prints `0.05555555555555555` (decimal expansion of `1.0/18`) if the regexp matches the input character; `0` is printed otherwise.

---

# Ruby `-nl`, 27 bytes (reads own source code)

```
p (IO.read($0).count$_)/27r

```

Try it online!

Reads its own source and counts occurrences of the input. Output is a rational number.

---

# Ruby `-nl` \+ coreutils, 24 bytes (reads own source code)

```
p`cat #$0`.count($_)/24r

```

Try it online!

Same as above but uses `cat` (from coreutils) to read the source.

# Answer
> 5 votes
# , ~~77~~ 75 bytes

*Edit: -2 bytes thanks to Giuseppe*

```
f <-function(c)sum(c==unlist(strsplit(capture.output(dump("f","")),"")))/75

```

Try it online!

Uses R `dump(,"")` function to output own source code\*, capturing output (normally to the console) using `capture.output()`. Then finds the number of matches to the function argument `c`, divided by the source code length (75 bytes).

\*Note that the TIO interface gives slightly differently-formatted output from the `dump()` function to running directly in R, so counts of whitespace characters are inaccurate in TIO (but correct in R).

---

# (without reading own source code), 106 bytes

```
'->p;sum(gregexpr(scan(,""),sQuote(p),f=T)[[1]]>0)/53'->p;sum(gregexpr(scan(,""),sQuote(p),f=T)[[1]]>0)/53

```

Try it online!

~~Same~~ Similar approach to above, but including quoted string instead of reading the source code itself.

# Answer
> 5 votes
# Io, 126 bytes

```
method(h,"mmmeeettthhhooodd((((,,,,aaaaassssMuubl  pppn34L))))iif==102/6"asMutable append(34)asList map(o,if(o==h,1,0))sum/62)

```

Try it online!

# Answer
> 5 votes
# PHP, ~~63~~ 60 bytes

```
fn($a)=>strstr('ffnn($a)==>>str\\\',,??11//220::',$a)?1/20:0

```

Try it online!

Much better solution than the first version, each char is present 3 times so if it is found, results in 3/63.

EDIT: saved 3 bytes by re-using `n` as var name (I had the luck that the total count still saved the repetition of all numbers for the calculus)

EDIT2: fixed the problem that `n` wasn't counted for not being in the string, manages to keep it 60 by removing `"` and introducing `\` (thanks to Dom Hastings)

EDIT3: fixed the problem with `0` wasn't counted because it was at the end (thanks to Dominic van Essen)

# Answer
> 5 votes
# C (gcc), ~~225~~ ~~221~~ ~~217~~ ~~203~~ 197 bytes

-28 bytes ceilingcat

```
char*t,r;main(i,s){for(i=getchar(asprintf(&t,s="char*t,r;main(i,s){for(i=getchar(asprintf(&t,s=%c%s%1$c,34,s));*t;r+=*t++==i);printf(%1$c%%d/197%1$c,r);}",34,s));*t;r+=*t++==i);printf("%d/197",r);}

```

Try it online!

# Answer
> 5 votes
# MATL, 14 bytes

```
39'39m7/h'hm7/

```

Try it online!

Each byte is present exactly twice in the source code. Therefore each byte has a frequency of either 1/7 or 0.

```
39       % Push code-point for '
'39m7/h' % Push literal char array
h        % Horizontally concatenate. Automatically converts to char array.
m        % Ismember: is input in this char array?
7/       % Divide by seven

```

# Answer
> 5 votes
## x86 machine code (MS-DOS .COM format), ~~53~~ ~~49~~ 44 bytes

Edit: Saved 4 bytes by eliminating a redundant CALL/RET and 5 bytes by outputting via `INT 29H`.

Input is taken from the command line: no input will search for `NUL` (hex 00H). Result is in the form "00/00" (i.e. "03/44" for an input of ")").

The counting part is really easy since this is a COM program: I scan for the target byte starting at DS:100H until I hit the end of the program code. To print the result and total counts, I use `AAM` to convert the numbers into unpacked BCD (which will always be less than 99) and then print the digits after flipping them so that they're displayed in the correct order.

Hex dump:

```
A0 82 00 B9 2C 00 33 D2 BF 00 01 F2 AE E3 03 42 EB F9 8B C2 E8 07 00 B0 2F CD 29 B8 2C 00 D4 0A 05 30 30 86 E0 CD 29 86 E0 CD 29 C3

```

TASM source for generated code:

```
IDEAL

MODEL   TINY
CODESEG
ORG 100H

PSIZE   EQU PEND-MAIN
PLEN    EQU PSIZE+1     ; Loop needs to be one larger so we can break on CX=0

MAIN:
    MOV     AL,[0082H]  ; Get search value from the command line
    MOV     CX,PLEN
    XOR     DX,DX
    MOV     DI,100H     ; Start search from the beginning of the program
CLOOP:
    REPNZ   SCASB       ; Search for value
    JCXZ    CDONE       ; Exit when at end of string
    INC     DX
    JMP     CLOOP
CDONE:
    MOV     AX,DX
    CALL    DISPNUM
    MOV     AL,'/'
    INT     29H
    MOV     AX,PSIZE
    ; Fallthrough to print last number and exit

DISPNUM:
    AAM                 ; Convert value to unpacked BCD (AH:AL)
    ADD     AX,3030H
    XCHG    AH,AL
    INT     29H
    XCHG    AH,AL
    INT     29H
    RET

PEND:

END MAIN
ENDS

```

# Answer
> 4 votes
# Python 3, 46 bytes

```
print(open(__file__).read().count(input())/46)

```

Try it online!

Straightforward enough, reads its own source code, counts how many times the input character appears, and returns that divided by 46 (the length of the code). You can also do it in 42 bytes with

```
lambda c:open(__file__).read().count(c)/42

```

but it's a little weird as this isn't a complete program (and since `__file__` will give the whole program, if you try to add a `f=` header, the frequencies get messed up).

# Answer
> 4 votes
# Pyth, 14 bytes

```
c/+N"c/+NQ7"Q7

```

Try it online!

## Explanation

```
c/+N"c/+NQ7"Q7
    "c/+NQ7"    # String literal
  +N            # Prepend '"'
 /          Q   # Count occurrences of the input in that string
c            7  # Divide by 7

```

# Answer
> 4 votes
# Google Sheets, 51

Input is in B1.

```
=LEN(REGEXREPLACE(FORMULATEXT(A1),"[^"&B1&"]",))/51

```

For once, we can't use the auto-close trick because the calculation would be wrong.

# Answer
> 3 votes
# Bash, 30 bytes

```
echo `tr -dc "$1"<$0|wc -c`/30

```

Try it online!

# Answer
> 3 votes
# \>\<\>, 24 bytes

```
'3d*0${:}=+40l4)?.+6*,n;

```

Assumes input on the stack.

1. Reads the code as a string literal, except for the leading `'`
2. `3d*` pushes the character code of `'`, and a counter `0` is also added.
3. Main loop `${:}=+`, increment the counter if the topmost value is equal.
4. `40l4)?.` Exit main loop if all values are read, if not jump back
5. `+6*,n;` print the result of floating point division

# Answer
> 3 votes
# Lenguage, 49,673,539,524 bytes

This code contains `49673539524` null bytes, and can actually fit into the universe (and even on a reasonably sized hard drive \[or even a flash drive!\]), which is saying a lot for Lenguage! Outputs digits as characters;  (with  replaced with an actual Start of Heading character, ASCII `1`) for `1` and infinite null bytes (ASCII `0`) for `0`; `␀␀␀␀␀...` (with  replaced with an actual null character) repeated forever. Converted to codepoints, it's pretty much `00000...` forever, or just `0`. Try brainf\*** online!*

```
,[>+[-.+]]+.  # full program
,             # set cell 0 to code point of input
 [       ]    # while cell 0 is nonzero...
  >+          # set cell 1 to 1
    [   ]     # while cell 1 is nonzero...
     -        # set cell 1 to 0
      .       # output character with code point in cell 1
       +      # set cell 1 to 1
          +   # set cell 0 to 1
           .  # output character with code point in cell 1

```

Well this ain't winning. The only reason I submitted this in the first place was because the method used is extremely simple. The code is translated using the method shown in my other Lenguage answer into the brainf\*** program `,[>+[-.+]]+.`.

<sub>\*The reason the TIO link outputs 1 for empty input is because empty input can simulate input of a null byte in brainf\***, as the current cell is set to `0` if there is no input to take.</sub>

<sub>Side note: I had ended up golfing over \\$7.7×10^{40}\\$ bytes from the Lenguage program (34 from the brainf\*** program) since my original version. My first attempt was `-[----->+<]>-->,[<<++[------<+>]<+++.>>-[.]]<.`, my second attempt was `-[----->+<]>-->,[<---.++[.]]<.`, I realized I don't need to output the decimal point (these programs prepended decimal points), and my third attempt was `-[----->+<]>-->,[<-[.]]<.`, until I realized I could golf this down a **ton** by outputting as characters.</sub>

# Answer
> 2 votes
# Japt, 18 bytes

```
øQ¬c"øQ¬cq¹/9"q¹/9

```

Try it

# Answer
> 2 votes
# C (clang), ~~159~~ ~~108~~ 90 bytes

```
x,s;main(c,v)char**v;{for(c=open(__FILE__,0);read(c,&x,1);s+=x==*v[1]);printf("%d/90",s);}

```

Try it online!

-51, thanks to ceilingcat (and also without the four-character-filename limitation)

-18, thanks to ceilingcat!

# Answer
> 2 votes
# Wolfram Language (Mathematica), 46 bytes

```
StringCount[ToString[#0, InputForm], #1]/46 &

```

Try it online! Pure function. Takes a single-character string as input and returns a rational number as output. Note the trailing space, which is necessary for the `InputForm` string to match the function.

# Answer
> 2 votes
# Lua, 98 bytes

```
s="s,i,p=s..'s=;load(s)(...)',-1,0while p do i,p=i+1,s:find(...,p+1,1)end print(i/98)"load(s)(...)

```

Try it online!

Ported Python answer to Lua.

The problem with Lua string functions is that you can't accept user input for anything but `string.find` with truthy fourth argument. Anyone trying to golf this should test all magic characters `^$()%.[]*+-?` as possible inputs.

Alternatively,

# Lua, 84 bytes (reads own source)

```
s,i,p=io.open(arg[0]):read(),-1,0while p do i,p=i+1,s:find(...,p+1,1)end print(i/84)

```

Try it online!

This also assumes that `arg[0]` can be used as path to program, which most likely is so.

# Answer
> 1 votes
# JavaScript (V8), 48 bytes

```
function f(c){return--(f+'').split(c).length/48}

```

Try it online!

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

```
f=open(__file__).read();print(f.count(input())/len(f))

```

Try it online!

`__file__` contains the path to the file the program is in. So f opens the file where it is and grabs the contents of it. `print(f.count(input())/len(f))`

This counts the occurrences of the character provided and divides it by the total number of characters.

# Answer
> 1 votes
# Thunno, \\$ 18 \log\_{256}(96) \approx \\$ 14.82 bytes

```
34C"34C+sc9/"+sc9/

```

Attempt This Online!

Based off @Mukundan314's Pyth answer.

## Thunno, \\$ 6 \log\_{256}(96) \approx \\$ 4.94 bytes

```
zdsc6/

```

Attempt This Online!

Probably cheating but I'll put it here anyway.

#### Explanations

```
34C                 # Push chr(34), the double quote
   "34C+sc9/"+      # Prepend it to the string "34C+sc9/"
              sc    # Swap and count the number of times the input is in the string
                9/  # Divide by 9 (Half the length of the program)

```

```
zd      # Push the source code
  sc    # Swap and count the number of times the input is in the string
    6/  # Divide by 6 (The length of the program)

```

---
Tags: code-golf, self-referential
---