title: Does the code terminate?

text:
# Question
Title: Does the code terminate?
This is a code golf challenge I thought of with a mathematical bent. The challenge is to write the shortest code possible such that it is an open question whether or not the code terminates. An example of what I mean could be the following piece of python code, adapted from an anwser to this cs stackexchange question.

```
def is_perfect(n):
    return sum(i for i in range(1, n) if n % i == 0) == n

n = 3
while not is_perfect(n):
    n = n + 2

```

Mathematicians conjecture that there are no odd perfect numbers, but it has never been proven, so no one knows if this piece of code will ever terminate. Can you come up with other pieces of code (perhaps relying on other open problems like the Collatz conjecture, or the twin primes conjecture) that are shorter, but for which it is unknown whether or not they terminate?

Edit: Some people have brought up a good additional rule - The solutions to the question should be deterministic. Although it might be even more interesting if you could find shorter solutions using nondeterminism. In this case, the rule would be to find a snippet for which the probability of termination is unknown.

# Answer
# Jelly, 7 bytes

```
!‘Æ²µ4#

```

Try it online!

### Background

This will terminate once it finds a fourth solution to Brocard's problem, i.e. a solution **n! + 1 = m²** with **(n,m) ≠ (4, 5), (5, 11), (7, 71)** over the positive integers. The implementation doesn't use floating point arithmetic, so it will only terminate if it does find a fourth solution or if **n!** can no longer be represented in memory.

*Brocard's problem was first used in this answer by @xnor.*

### How it works

```
!‘Æ²µ4#  Main link. No arguments. Implicit argument: 0

    µ4#  Convert the links to the left into a monadic chain and call it with
         arguments k = 0, 1, 2, ... until 4 of them return 1.
!        Factorial; yield k!.
 ‘       Increment; yield k! + 1.
  Æ²     Squareness; return 1 if k! + 1 is a perfect square, 0 if not.

```
> 30 votes

# Answer
# Jelly, ~~11~~ 9 bytes

```
ÆẸ⁺‘ÆPµ6#

```

This will terminate once the sixth Fermat prime is found.

Try it online!

### How it works

```
ÆẸ⁺‘ÆPµ6#  Main link. No arguments. Implicit argument: 0

      µ6#  Convert the links to the left into a monadic chain and call it with
           arguments k = 0, 1, 2, ... until 6 of them return 1.
ÆẸ         Convert [k] to the integer with that prime exponent factorization, i.e.,
           into 2 ** k.
  ⁺        Repeat.
   ‘       Increment.
           We've now calculated 2 ** 2 ** k + 1.
    ÆP     Test the result for primality.

```
> 20 votes

# Answer
## Pyth, 10 bytes

```
fP_h^2^2T5

```

Uses the conjecture that all Fermat numbers `2^(2^n)+1` are composite for `n>4`.

```
f        5   Find the first number T>=5 for which
   h^2^2T    2^(2^T)+1
 P_          is prime

```
> 17 votes

# Answer
# MATL, 11 bytes

```
`@QEtZq&+=z

```

Terminates iff the Goldbach conjecture is false. That is, the program stops if it finds an even number greater than `2` that cannot be expressed as the sum of two primes.

```
`        % Do...while
  @      %   Push iteration index k. Gives 1, 2, 3, ...
  QE     %   Add 1 and multiply by 2. Gives 4, 6, 8, ...
  tZq    %   Duplicate. Push all primes up to current k
  &+     %   Matrix with all pairwise additions of those primes
  =z     %   Number of entries of that matrix that equal k. This is used as loop
         %   condition. That is, the loop continues if this number is nonzero
         % Implicit end

```
> 12 votes

# Answer
## Python, 36 bytes

```
k=n=1
while(n+1)**.5%1+7/k:k+=1;n*=k

```

Uses Brocard's problem:

> Is n!+1 a perfect square for any n≥8?

Computes successive factorials and checks whether they are squares and have `k>7`. Thanks to Dennis for 2 bytes!

This assumes Python continues to have accurate arithmetic for arbitrarily large numbers. In actual implementation, it terminates.
> 12 votes

# Answer
# Brachylog (v2), 3 bytes in Brachylog's encoding

```
⟦cṗ

```

Try it online! (will time out without doing anything visible, for obvious reasons)

Full program; if run with no input, searches for the first Smarandache prime, and outputs `true.` if and when it finds one. It's an open question as to whether any Smarandache primes exist. (Note that Brachylog's prime-testing algorithm, although it works in theory on arbitrarily large numbers, tends to run slowly on them; thus, if you're interested in finding Smarandache primes yourself, I recommend using a different language.)

## Explanation

```
⟦cṗ
⟦     Form an increasing range from 0 to {the smallest number with no assertion failure}
 c    Concatenate all the numbers that make up that range, in decimal
  ṗ   Assert that the result is prime

```

Brachylog operates on the decimal digits of a number whenever you try to treat it like a list, so "range" followed by "concatenate" is a very terse way to generate the sequence of Smarandache numbers (and then we filter that by primality; Brachylog's default full program behaviour will then force the first element of the resulting generator). The range has a leading zero, but fortunately, with this flow pattern, Brachylog removes the zero rather than failing.

Here's an example that finds the first Smarandache number that's equal to 6 (mod 11), as a demonstration of a similar program that terminates within 60 seconds rather than having unknown halting status:

```
⟦c{-₆~×₁₁&}

```

Try it online!

This would print `true.` as a full program, but I threw in the `Z` command line argument to actually print the number in question, giving a better demonstration that this general approach works.
> 12 votes

# Answer
# Perl, ~~50~~ ~~38~~ ~~36~~ ~~34~~ 33 bytes

```
$_=196;$_+=$%while($%=reverse)-$_

```

Explanation: 196 is a possible Lychrel number \- a number that does not form a palindrome by repeatedly adding its reverse to itself. The loop continues until $n is equal to its reverse, which is as yet unknown for initial value 196.

```
25 + 52 = 77

```

which is not valid.

```
96 + 69 = 165
165 + 561 = 726
726 + 627 = 1353
1353 + 3531 = 4884

```

so none of the numbers in this sequence are valid.

Edit: Golfed it down by using an until loop instead of a for loop (somehow). Also, I had fewer bytes than I thought (I should probably look at my bytecount more carefully in the future).

Edit: Replaced `$n` with `$_` to save 2 bytes for the implied argument in `reverse`. I *think* this is as golfed as this implementation is going to get.

Edit: I was wrong. Instead of using `until($%=reverse)==$_` I can go while the difference is nonzero (i.e. true): `while($%=reverse)-$_`.
> 11 votes

# Answer
# Python, ~~30~~ 28 bytes

```
n=2
while 2**~-n%n**3-1:n+=1

```

This program will halt if and only if there is an integer n bigger than 1 such that 2^(n-1)-1 is divisible by n^3. To my knowledge it is not known whether any number with this property exists (if a number satisfying this property is prime, it is called a Wieferich prime of order 3 to base 2, and it is open whether any such prime exists).
> 9 votes

# Answer
# 05AB1E, 8 bytes

Will terminate when the 6th Fermat prime is found.

```
5µNoo>p½

```

**Explanation**

```
5µ          # loop over increasing N (starting at 1) until counter reaches 5
  Noo       # 2^2^N
     >      # + 1
      p½    # if prime, increase counter

```
> 8 votes

# Answer
## Haskell, 47 bytes

```
[n|n<-[1..],2*n==sum[d|d<-[2..n],n`mod`d<1]]!!0

```

Searching the first quasiperfect number, which is a number `n` whose sum of divisors is `2*n+1`. Instead of adding 1, I exclude 1 from the list of divisors.
> 7 votes

# Answer
# Brain-Flak, ~~212~~ ~~208~~ 204 bytes

*This program uses a multiplication algorithm written by MegaTom and a non-square checker written by 1000000000*

Try It Online

```
(((()()()()){})){{}((({}()))<{(({})[()])}{}>[()]){({}<({}<>)({<({}[()])><>({})<>}{}<><{}>)>[()])}{}(({}())){(({}[()]<>)<>)(({({})({}[()])}{}[({})]<>)){{}{}({}<>)(<([()])>)}{}({}()){(((<{}{}<>{}>)))}{}}{}}

```

This program starts at 8 and tests each number to see if n!+1 is a square number. It exits when it finds one. This is known as Brocard's Problem and it is an open problem in mathematics.
> 6 votes

# Answer
# Python 2, 88 bytes

```
p=lambda n:all(n%x for x in range(2,n))
s=lambda n:0if p((10223*2**n)+1)else s(n+1)
s(0)

```

This code will terminate if 10223 is a Sierpiński number. 10223 is currently the smallest candidate that may or may not be a Sierpiński number, as of December 2013.

A Sierpiński number is a number `k` in which all numbers of the form `(k * 2^n) + 1` are composite.
> 5 votes

# Answer
# Actually, 16 bytes

```
1`;;pY)▒@D÷íu*`╓

```

Try it online!

This code terminates iff there is some composite number `n` such that `totient(n)` divides `n-1` (Lehmer's totient problem).

Explanation:

```
1`;;pY)▒@D÷íu*`╓
1`            `╓  first integer, starting with 0, where the following function leaves a truthy value on top of the stack:
    pY       *      composite (not prime) and
   ;  )▒            totient(n)
  ;     @D÷íu       is in the list of divisors of n-1

```
> 5 votes

# Answer
# Jelly, ~~9~~ 8 bytes

-1 byte thanks to @Dennis! (use exponentiation instead of multiplication to avoid `Æṣ(0)`)

```
*ḂÆṣ=µ2#

```

Will return a list of zero and the smallest odd perfect number, if any exist.

### How?

```
*ḂÆṣ=µ2# - Main link: no arguments
     µ   - monadic chain separation
      2# - count up from implicit `n=0` and return the first 2 truthy results of
 Ḃ       -     mod 2        -> n%2
*        -     exponentiate -> n**(n%2)  (1 when n is even, n when n is odd)
  Æṣ     -     sum of proper divisors of n**(n%2)
    =    -     equals n?    -> 1 if n is zero or both perfect and odd, else 0

```
> 5 votes

# Answer
# Pyth, 16 bytes

```
f!}1.u@,/G2h*3GG

```

Returns the first value for which the Collatz conjecture does not hold. As it is unknown whether the conjecture holds for all numbers, it is unknown whether this code will terminate.
> 4 votes

# Answer
# Haskell, 46 bytes

```
[n|m<-[1..],n<-[1..m],product[1..n]+1==m^2]!!3

```

Terminates if it finds the 4th solution to brocard's problem.
> 4 votes

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

```
p=lambda n,k=2:n<=k or n%k*p(n,k+1)
g=lambda n:[p(b)*p(n-b)for b in range(n)]and g(n+2)
g(4)

```

This code will terminate if the Goldbach conjecture does not hold for all even numbers (i.e. if all even numbers can be expressed as the sum of two primes). It has currently been tested for numbers up to 4\*10^18.

A huge amount of thanks to @Pietu1998 for shortening my code by a lot!

EDIT: Thanks to @JonathanAllan for shaving 6 bytes off my code!
> 3 votes

# Answer
# Python, 92 bytes

This isn't winning any code golf competitions, and it requires infinite memory and recursion depth, but this is an almost perfect opportunity to plug an interesting problem I asked on math stackexchange two years ago, that no Fibonacci number greater than 8 is the sum of two positive cubes. Funnily enough, it started as an code golf challenge idea, so I guess I've come full circle.

```
def f(i,j):
 r=range(i)
 for a in r:
  for b in r:
   if a**3+b**3==i:1/0
 f(j,i+j)
f(13,21)

```
> 3 votes

# Answer
# JavaScript (ES6), ~~104~~ 101 bytes

```
for(n=[6,9,p=1];!p;n=n.map((x,i)=>(q=n[n.length+~i],p|=x^q,c=q+x+c/10|0)%10).concat(c/10|0||[]))c=p=0

```

Uses the same method as the Perl answer: sets **n** to 196, then repeatedly adds **n** to its base 10 reverse until it's a palindrome in base 10. This would be shorter if JS supported arbitrary-precision numbers, but oh well.
> 2 votes

# Answer
# Python, 80 bytes

Terminates if the Collatz Conjecture is proven false. See this question.

```
n=2
while 1:
 L=[];x=n
 while~-n:1/(n not in L);L+=[n];n=(n/2,n*3+1)[n%2]
 n=x+1

```
> 2 votes

# Answer
# Jelly, 7 bytes

```
*+3Ẓµ4#

```

Try it online! (prints two elements, not 4, so that you can actually see it halt)

Prints the first four \\$n\\$ such that \\$n^n+3\\$ is prime. It is not known whether four+ numbers with this property exist. The first three are 2, 1036, and 2770.

## Explanation

```
*+3Ẓµ4#
     4#  Find the first four numbers with the following property:
    µ      (bracketing/grouping: place everything to the left inside the loop)
*          {The number} to the power of {itself}
 +3        plus 3
   Ẓ       is prime

```
> 2 votes

# Answer
# Pyth, 13 bytes

```
.u@,/G2h*5GG7

```

Like Steven H.'s answer, but saving a few bytes by using the 5n+1 problem instead

> Do the iterates of $$f(n)=\begin{cases}5n+1&\mbox{if }n\mbox{ is odd}\\\frac{n}{2}&\mbox{otherwise}\end{cases}$$ starting with 7, cycle?

While it seems unlikely, the answer is unknown!
> 2 votes

# Answer
# Vyxal, 8 bytes

```
λEE›æ;5ȯ

```

Try it Online!

Finds the fifth Fermat Prime.

```
λ    ;5ȯ # First 5 numbers where
 EE›     # 2^2^n + 1
   æ     # Is prime

```
> 2 votes

# Answer
# Python 2, 64 bytes

> A Lychrel number is a natural number that cannot form a palindrome through the iterative process of repeatedly reversing its digits and adding the resulting numbers.

No Lychrel numbers have been proven to exist in base ten. 196 is the smallest base ten Lychrel number candidate. It has been shown that if a palindrome exists (making 196 *not* a Lychrel number), it would have at least a billion (10^9) digits, because people have run the algorithm that long.

```
n=196
while 1:
    x=str(n);r=x[::-1]
    if x!=r:n=n+int(r)
    else:1/0

```
> 1 votes

# Answer
# R, 30 bytes, arguable whether it is deterministic

```
while(any(sample(2,654,T)>1))1

```

R's default random number generator has equidistribution in 653 consecutive dimensions but it is not known to in 654 dimensions. Thus there may or may not be a sequence of pseudorandom numbers that sample the lowest element from a given vector 654 times in a row (here the vector `1:2`).

Since R's RNG is periodic (albeit with very long period), I claim that this *is* deterministic since it will eventually loop round to the start. Your opinions may differ, of course.
> 1 votes

# Answer
# Pushy, 13 bytes

```
7$h&fh&r2e=?i

```

Try it online!

This program attempts to find a solution to Brocard's Problem \- it will keep running until it finds a \\$n \ge 8\\$ such that \\$ n! +1=m^2, m \in \mathbb{N} \\$
> 1 votes

# Answer
# Python 3, 101 bytes

I know it's longer than many others, but I spent a lot of time seeing how short I could golf this.

This attempts to disprove Euler's Sum of Powers Conjecture for `k=6` (there exists no positive integer solution to the Diophantine equation `A^6+B^6+C^6+D^6+E^6==F^6`), for which no counterexample has been found.

```
R=[1]
while 1:R+=[R[-1]+1];eval(("[1/("+"+%s**6"*5+"!=%%s**6)%s]"%("for %s in R "*6))%(*"ABCDEF"*2,))

```

**In Python 2 (104 bytes):**

```
R=[1]
while 1:R+=[R[-1]+1];eval(("[1/("+"+%s**6"*5+"!=%%s**6)%s]"%("for %s in R "*6))%tuple("ABCDEF"*2))

```

**Less golfed:**

```
x=2
while 1:
    R=range(1,x)
    [1/(A**6+B**6+C**6+D**6+E**6!=F**6)for F in R for E in R for D in R for C in R for B in R for A in R]
    x+=1

```

**Mathy version with no eval:**

```
R=range
x=2
while 1:
    for i in R(x**6):1/(sum(map(lambda x:x**6,[1+(i%x**-~j/x**j)for j in R(6)]))-i%x-1)
    x+=1

```

Alternate reference: Euler's Sum of Powers Conjecture - MathWorld
> 0 votes

# Answer
# Python, 68 bytes

```
n=2
while"".join(str((i+2)**n)[0]for i in range(8))!="23456789":n+=1

```

**Try it online**

Tries to answer one of Gelfand's Questions.

> 2. Will the row "23456789" ever appear for n\>1? None does for n\<=10^5. ...
> 0 votes

# Answer
# Clojure, 154 bytes

```
(loop[x 82001](if(= 0(reduce +(map{true 1 false 0}(for[y(range 3 6)](true?(for[z(str(range 2 y))](.indexOf z(Integer/toString x y))))))))x(recur(inc x))))

```

Checks if there's a number above 82,000 that only contains 0's and 1's for base 2 all the way to base 5. In other words, it checks if there's another number in this sequence.

In that special group, there are only 3 numbers: `0`, `1` and `82,000`. There are no more numbers that follow that rule that are less than approximately `3*10^19723`.
> 0 votes

# Answer
# Pyt, 14 bytes

```
27*²0`ŕĐ₫+Đ₽¬ł

```

Port of mbomb007's answer.
> 0 votes

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


title: Is this a half-sort?

text:
# Question
Title: Is this a half-sort?
The problem over here introduces an new type of strings: if you split the string into equal halfs and swap the pairs, it produces the same output as sorting the string. We call that a half-sort.

Given a purely ASCII string, check if the string is in a half-sort.

## An example of a half-sort string

The string `node` is a half-sort string, because if you sort by codepoints (note that the codepoints are in *decimal*, not *binary*):

```
n 110
o 111
d 100
e 101

```

That gets turned into:

```
d 100
e 101
n 110
o 111

```

You'll see that the `node` to `deno` conversion is exactly moving the right half to the left position.

## Specification

* For odd-length strings, splitting should make the first half longer.
* Sorting a string means sorting the string based on the codepoints of the characters.

## Reference program & test cases

Here is the reference program I made for checking my test cases.

```
node -> True
rum  -> True
aaa  -> True

deno -> False
rim  -> False

```

# Answer
> 1 votes
# Brachylog, 5 bytes

```
oḍ↔c?

```

Try it online!

Outputs through success or failure.

```
o        The input sorted
 ḍ       and split in half (with the *second* half longer if the length is odd),
  ↔      with those halves reversed
   c     and concatenated,
    ?    is the input.

```

# Answer
> 5 votes
# , ~~20~~ ~~18~~ ~~15~~ 14 bytes

*-1 thanks to Jonah.*

Goes the other way around: sorts the string ('node' -\> 'deno'), rotates it back ('deno' -\> 'node') and checks if this equals the input. Fits better J trains.

```
-:<.@-:@#|./:~

```

Try it online!

### How it works

```
-:<.@-:@#|./:~
           /:~  sort input
  <.@-:@#       length of input, halved and floored
         |.     rotate sorted input by that amount
-:              input equal to that?

```

# Answer
> 5 votes
# Python 3, ~~45~~ 42 bytes

*-3 bytes thanks to @dingledooper*

```
lambda s:sorted(s)==s+[s.pop(0)for c in s]

```

Try it online!

Takes input as a list of characters. Returns `True` if the list is half-sorted, `False` otherwise.

**How**

`[s.pop(0)for c in s]` gets the first half of the list. After this is evaluated, `s` only has the later half left.

Thus `s+[s.pop(0)for c in s]` is the list with the 2 halves swapped. Note that this works because Python evaluates anything inside square brackets first.

I then check if the swapped list is sorted, aka compare it with `sorted(s)`.

# Answer
> 4 votes
# Pyth, 8 bytes

```
qSzs_c2z

```

Try it online!

---

Luckily, Pyth offers most of what we need out of the box, so we just need to call the operations necessary.

```
 Sz       # Sort the input
     c2z  # Chop the input into two equal pieces (first longer if needed)
    _     # Reverse the chopped elements
   s      # Join them back together
q         # Check for equality

```

# Answer
> 4 votes
# perl -plF//, 49 bytes

```
push@F,splice@F,0,(@F+1)/2;$_="@F"eq"@{[sort@F]}"

```

Try it online!

Splits a line of input into characters, which are placed in `@F`. We remove the first half and tag it to the end. We then check whether the array is the same if we sort it -- if the result is the same, the string was a half sort, if not, it wasn't.

Outputs 1 for a half sort, the empty string when not.

# Answer
> 3 votes
# Jelly, 6 bytes

```
ŒHṚFṢƑ

```

A monadic Link accepting a list of characters which yields `1` (truthy) if a half-sort and `0` (falsey) otherwise.

**Try it online!**

### How?

Fairly straightforward in Jelly, pretty much just implements the challenge specification directly...

```
ŒHṚFṢƑ - Link: list of characters (full Unicode, but works with ASCII only too)
ŒH     - split it into two halves (first half 1-longer if odd in length)
  Ṛ    - reverse
   F   - flatten back to a list of characters
     Ƒ - is invariant under?:
    Ṣ  -   sort

```

# Answer
> 3 votes
# 05AB1E, 7 bytes

```
{I2äRJQ

```

Try it online or verify all test cases.

**Explanation:**

```
{        # Sort the characters in the (implicit) input
 I       # Push the input again
  2ä     # Split it into 2 equal-sized parts (first part will be longer for odd lengths)
    R    # Reverse this pair
     J   # Join them back together to a string
      Q  # And check if both strings are equal
         # (after which the result is output implicitly)

```

# Answer
> 3 votes
# Charcoal, 22 bytes

```
≔⪫⮌⪪θ⊘⊕Ｌθωθ¬⊙θ∧κ‹ι§θ⊖κ

```

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. `-` for true, nothing for false. Explanation:

```
≔⪫⮌⪪θ⊘⊕Ｌθωθ

```

Split the string into half, reverse, and join.

```
¬⊙θ∧κ‹ι§θ⊖κ

```

Check whether any characters are less than their predecessor.

# Answer
> 2 votes
# Python 3.8,  ~~68~~  46 bytes

```
lambda s:sorted(s)==s[(h:=-~len(s)//2):]+s[:h]

```

An unnamed function accepting a list of characters which yields `True` if a half-sort and `False` otherwise.

**Try it online!**

---

Turns out the straightforward way is terser!

Original 68 byter in Python 2:

```
lambda s:all(i==~-len(s)/2for i in range(len(s))if(s[1:]+s)[i]<s[i])

```

Try it online!

# Answer
> 2 votes
# Ruby, 33 bytes

```
->a{a.rotate(-~a.size/2)==a.sort}

```

Try it online!

Takes input as an array of characters (which feels like cheating). Simply rotates the array by half its length and checks whether this is equal to the sorted array.

# Answer
> 2 votes
# APL+WIN, ~~39~~ 36 bytes

Prompts for input of string:

```
(⍴s)=+/1,2≤/⎕av⍳(-⍴s)↑s,(⌈.5×⍴s)↑s←⎕

```

Try it online! Courtesy of Dyalog Classic

Explanation:

```
(⌈.5×⍴s)↑s take the front half of the string rounding up for odd number length

(-⍴s)↑s,prepend the original string and take trailing characters up to
the original length of string

⎕av⍳ get code points

(⍴s)=+/1,2≤/ check that successive code points are ascending, sum the
 result and compare to length of string; equal = 1 = true, not equal = 0 = false

```

# Answer
> 2 votes
# C (gcc), ~~82~~ 81 bytes

```
i;e;r;l;f(char*s){l=strlen(s);for(r=1,e=i=~-l/2;++i%l-e;)r&=s[-~i%l]/s[i%l];e=r;}

```

Try it online!

# Answer
> 2 votes
# Clojure, 48 bytes

```
#(=(sort %)(flatten(reverse(partition-all 2%))))

```

Try it online!

# Answer
> 2 votes
# Vyxal, 5 bytes

```
s½Ṙ∑=

```

Try it Online!

```
s     # Input Sorted
 ½    # Split into two halves
  Ṙ∑  # And concatenated reversed
    = # Equals original input?

```

---
Tags: code-golf, string, decision-problem, sorting
---


title: Is this a word?

text:
# Question
Title: Is this a word?
Toki pona is a minimalist constructed language, and thus it has minimalist phonotactics (rules describing what sounds make valid words).

Toki Pona has 8 consonant sounds `m`, `n`, `p`, `t`, `k`, `s`, `w`, `l` and `j` and 5 vowel sounds `a`, `e`, `i`, `o`, `u`. A single basic syllable in toki pona consists of any 1 consonant, any one vowel and optionally an `n`. So all of the following are valid:

```
pi
ko
wa
san
jen

```

There are four exceptions of sequences that are forbidden they are `ji, wu, wo, ti`.

With the basic syllables we can build words. A word is just a string of basic syllables with two special rules:

1. When we have an `n` followed by either `n` or `m` we drop the `n`. e.g. `jan` \+ `mo` is `jamo` not `janmo`
2. The initial syllable of a word can drop the initial consonant. e.g. `awen` and `pawen` are both legal and distinct words. This does allow for words consisting of just a vowel.

## Task

Your task is to take a non-empty string consisting of lowercase alphabetic characters (`a` through `z`) and determine if it makes a valid toki pona word.

When the input is a valid word you should output one value and when it is not you should output another distinct value.

This is so answers will be scored in bytes with the goal being to minimize the size of the source.

## Test cases

Accept:

```
awen
jan
e
monsuta
kepekin
ike
sinpin
pakala
tamako
jamo
pankulato
pawen
an
nene
nenen

```

Reject:

```
bimi
ponas
plani
womo
won
tin
wu
miji
sunmo
anna
sam
kain
op
p
n

```

# Answer
> 7 votes
# Retina 0.8.2, ~~48~~ 47 bytes

```
A`ji|nm|nn|ti|wu|wo
^((^|[j-npstw])[aeiou]n?)+$

```

Try it online! Link includes test cases. Edit: Saved 1 obvious byte thanks to @ovs. Explanation:

```
A`ji|nm|nn|ti|wu|wo

```

Delete invalid inputs.

```
^((^|[j-npstw])[aeiou]n?)+$

```

Match valid inputs that weren't invalidated above.

# Answer
> 4 votes
# Jelly,  ~~56~~  51 bytes

+1 to cater for strict IO (two distinct outputs rather than truthy vs falsey being allowed)

```
“jtklmnpsw”,ØẹŒpṖṖ¬3,8¦p”n;ƊṗⱮLẎF€⁾mnyw⁾nnƲÐḟḊ€;$e@

```

A (very inefficiant) monadic Link that yields `0` when the input string is not a Toki Pona word and `1` when it is.

(Don't) Try it online! (it's so inefficient it'll only complete for words of length three or less!)

...but here is a test-suite that has all tests except the four syllable `pankulato` that (a) limits to three base-syllables, rather than that of the number of characters in the input string and (b) only calls the word-generating code once for all (hence the `e@` has been moved out to the footer).

### How?

We construct a list containing ALL valid Toki Pona words constructed from at most `length(input)` syllables and check if the input is in there.

Yep that's soooo nasty, but without easy regex access I imagine it's the golfiest way.

```
“jtklmnpsw”,ØẹŒpṖṖ¬3,8¦p”n;Ɗṗ - (partial) Link: integer (from below!)
“jtklmnpsw”                   - "jtklmnpsw"
            Øẹ                - "aeiou"
           ,                  - pair
              Œp              - Catesian product
                ṖṖ            - pop off "wu" and "wo"
                   3,8¦       - apply to indices 3 & 8 ("ji" & "ti"):
                  ¬           -   logical NOT (replace these with [0,0] (integers)
                           Ɗ  - last three links as a monad:
                        ”n    -   'n'
                       p      -   Cartesian product (appends 'n' to each)
                          ;   -   concatenate
                            ṗ - Catiasian power (the integer)

...ⱮLẎF€⁾mnyw⁾nnƲÐḟḊ€;$e@ - (continued) Link: string, S
... L                     - length of S
...Ɱ                      - map across [1..length(S)] with:
...                       -   code above -> base-syllable combos of each length
     Ẏ                    - tighten
      F€                  - flatten each
                 Ðḟ       - filter discard those for which:
                Ʋ         -   last four links as a monad:
        ⁾mn               -     "mn"
           y              -     translate (convert ms to ns)
             ⁾nn          -     "nn"
            w             -     index of first occurrence (or zero)
                      $   - last two links as a monad:
                   Ḋ€     -   dequeue each
                     ;    -   concatenate
                        @ - with swapped arguments:
                       e  -   S exists in there?

```

# Answer
> 3 votes
# Perl 5 `-p`, 64 bytes

```
$_=!/[jt]i|wu|wo|nm|nn/&&/^([aeiou]n?)?([mnptkswlj][aeiou]n?)*$/

```

Try it online!

# Answer
> 2 votes
# Charcoal, ~~59~~ ~~58~~ 55 bytes

```
∧θ¬⊙⪪”&↧q1o⁺VＰα”²№θι≔aeiouηＦ⮌θ¿№ηι≔⁻”&↧ï⁸t∕p№t⟦”ηη¿⁻ιn⎚

```

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

```
∧θ¬⊙⪪”&↧q1o⁺VＰα”²№θι

```

Check that the word doesn't contain any of the illegal letter pairs contained in the compressed string.

```
≔aeiouη

```

Start by expecting the last character to be a vowel.

```
Ｆ⮌θ

```

Loop over the word in reverse.

```
¿№ηι

```

If we see an expected letter, ...

```
≔⁻”&↧ï⁸t∕p№t⟦”ηη

```

... then flip the set of expected letters by subtracting it from the string all the legal Toki Pona letters grouped into vowels and consonants.

```
¿⁻ιn

```

Otherwise, if the current letter is not an `n`, ...

... then erase any previous validity there might have been.

# Answer
> 2 votes
# TypeScript type system, 313 bytes

```
type v="a"|"e"|"i"|"o"|"u";type i<T>=T extends""?1:T extends`${Exclude<`${"m"|"n"|"p"|"t"|"k"|"s"|"w"|"l"|"j"}${v}`,"ji"|"wu"|"wo"|"ti">}${infer r}`?i<r>extends 1?1:r extends`n${infer e}`?e extends`${"n"|"m"}${any}`?0:i<e>:0:0;type o<T>=T extends`${v}${infer p}`?i<p>extends 1?1:p extends`n${infer r}`?i<r>:0:i<T>

```

This is written entirely with TypeScript types - the `o` type outputs 1 if the input parameter is a valid word and 0 if it is not. There's probably some room for further golfing.

# Answer
> 1 votes
# 05AB1E, 49 bytes

```
„nn„nm‚åà≠×ε.•2Ñ|qγù•žMâ¨¨D27SèKD'n««N>ãJ}˜D€¦«Iå

```

Port of *@JonathanAllan*'s Jelly answer, but even slower.. :/
Outputs `1`/`0` for accept/reject respectively.

Try it online.
As is it's too slow for a test suite, but by adding `2äн` between the `×` and `ε` (map over halve the input-length instead), we can verify all but the longest few truthy test cases and falsey test cases respectively, in separated test suites.

**Explanation:**

```
„nn„nm‚               # Push pair ["nn","nm"]
       åà≠            # Check that NEITHER is present in the (implicit) input
          ×           # 'Multiply' it by the (implicit) input-string
                      # (the input if truthy; "" if falsey)
ε                     # Map over the characters:
 .•2Ñ|qγù•            #  Push compressed string "jtklmnpsw"
          žM          #  Push builtin vowels "aeiou"
            â         #  Pop both, and create a list of all possible char-pairs
             ¨¨       #  Remove the last two ("wu" and "wo")
               D      #  Duplicate the list
                27S   #  Push pair [2,7]
                   è  #  Index those into the copy: ["ji","ti"]
                    K #  Remove those as well
 D                    #  Duplicate the list again
  'n«                '#  Append an "n" to each string
     «                #  Merge the two lists together
 N                    #  Push the 0-based map-index
  >                   #  Increase it by 1 to make it 1-based
   ã                  #  Cartesian product this index on the list of syllables
    J                 #  Join each inner list together to a string
}˜                    # After the map: flatten the list of lists
  D                   # Duplicate the list
   €¦                 # Remove the first consonant from each
     «                # Merge the two lists together
Iå                    # Check if the input-string is in this list
                      # (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 `.•2Ñ|qγù•` is `"jtklmnpsw"`.

# Answer
> 1 votes
# Pip, ~~56~~ ~~53~~ 47 bytes

*-3 bytes by porting Neil's Retina answer*

```
X<>"jiwuwotinnnm"NIa&a~=+:`^|[j-nptsw]`+XV.`n?`

```

Returns 1 for a valid word, 0 for an invalid word. Attempt This Online!

Verify all test cases

### Explanation

At its core, this solution works similarly to Neil's Retina answer:

* The input does not contain any of the illegal sequences `ji`, `wu`, `wo`, `ti`, `nn`, or `nm`; AND
* The input fully matches the regex `((^|[j-nptsw])[aeiou]n?)+`

First half:

```
X<>"jiwuwotinnnm"NIa
   "jiwuwotinnnm"     That string
 <>                   Grouped into pairs of characters
X                     Converted to a regex that matches any of those pairs
                 NI   Does not match in
                   a  The command-line argument

```

Second half:

```
a~=+:`^|[j-nptsw]`+XV.`n?`
     `^|[j-nptsw]`          That regex
                  +         Wrapped in a non-capturing group and followed by
                   XV       Built-in regex `[aeiou]`
                     .      Followed by
                      `n?`  That regex
   +:                       Apply the + quantifier to the above wrapped in n.c. group
a~=                         Command-line argument fully matches that regex

```

# Answer
> 1 votes
# Python 3, ~~97 88~~ 86 bytes

```
lambda x:re.sub("((?!ji|wu|wo|ti|.*n[nm])(^|[j-npstw])[aeiou]n?)*$","",x)>""
import re

```

Try it online!

return `False` for valid word, `True` for invalid

Thanks to @14m2 for -2 bytes

## How it works:

* at each syllable, we chek for `ji|wu|wo|ti` and prevent any capture if it is present. We also chek for the presence of either `nn` or `nm` further in the word.
* if it was absent, we capture the syllable (consonant + voyel (+ n))
* All the syllables captured are replaced by the empty string
* We then check if the result is greater than the empty string (falsey) or equal to the empty string (thruthy)

# Answer
> 1 votes
# Lexurgy, 195 bytes

Lexurgy is a tool made for conlangers for applying sound changes, so this is perfect for this challenge! ~~(and here I am bashing it into code golf)~~

Outputs the original word if it's valid Toki Pona, and an empty string otherwise.

Extremely slow version:

```
Class c {m,n,p,t,k,s,w,l,j}
Class v {a,e,i,o,u}
a:
{({j,t} i),(w {o,u}),({m,n} {m,n}),!@c&!@v}=>`
{(!n&@c @c),(@v @v)}=>` *
!@v&!n=>`/_ $
n=>`/$ _ $
c propagate:
[]=>`/{` _,_ `}
d:
`=>*

```

Much faster version, 199 bytes:

```
Class c {m,n,p,t,k,s,w,l,j}
Class v {a,e,i,o,u}
a:
{j,t} i=>`
w {o,u}=>`
{m,n} {m,n}=>`
!n&@c @c=>` *
@v @v=>` *
!@v&!n=>`/_ $
n=>`/$ _ $
!@c&!@v=>`
c propagate:
[]=>`/{` _,_ `}
d:
`=>*

```

Ungolfed:

```
Class cons {m,n,p,t,k,s,w,l,j}
Class vow {a,e,i,o,u}

remove-forbidden:
 {j,t} i => ` # ji, ti
 w {o,u} => ` # wo, wu
 {m,n} {m,n} => ` # mn, mm, etc
 !n&@cons @cons => ` * # no consecutive consonants
 @vow @vow => ` * # no consecutive vowels
 !@vow&!n => ` / _ $ # ending with a vowel or n
 n => ` / $ _ $ # nothing of length 1
Then:
 !@cons&!@vow => ` # convert any invalid character
Then propagate:
 [] => ` / {` _, _ `} # spread the invalid
Then:
 ` => * # delete the invalid

```

# Answer
> 0 votes
# C (gcc), 438 bytes

```
#define R return
int c(l){char a[]={'n','m','p','t','k','s','w','l','j'};for(int i=0;i<9;i++)if(l==a[i])R 1;R 0;}
int v(l){R l==97||l==101||l==105||l==111||l==117?1:0;}
int f(char* s){int i,a,b;for(i=0;*s!=0;s++,i++){a =*s;b=*(s+1);if(!(c(a)||v(a))||((a=='j'||a=='t')&&b=='i'||a=='w'&&(b=='u'||b=='o')||a=='n'&&(b=='n'||b=='m'))||(c(a)&&c(b)&&a!='n')||(v(a)&&v(b))) R 0;}if(i==1&&c(*(s-1))) R 0;if(*s==0&&v(*(s-2))&&*(s-1)!='n') R 0;R 1;}

```

Try it online!

Explanations :

#define R return
// function to detect a consonant
int c(l){char a[]={'n','m','p','t','k','s','w','l','j'};for(int i=0;i<9;i++)if(l==a[i])R 1;R 0;}
// function to detect a vowel
int v(l){R l==97||l==101||l==105||l==111||l==117?1:0;}

int f(char* s){int i,a,b;for(i=0;*s!=0;s++,i++)
{
    a =*s;b=*(s+1);
    if(!(c(a)||v(a))||      // detect if characters are allowed
    ((a=='j'||a=='t')&&b=='i'||a=='w'&&(b=='u'||b=='o')||a=='n'&&(b=='n'||b=='m'))|| // detect if sequences ji, wu, wo & ti are not used
    (c(a)&&c(b)&&a!='n')||  // detect if there are not 2 consecutives consonants
    (v(a)&&v(b)))           // detect if there are not 2 consecutives vowels
    R 0;
    if(i==1&&c(*(s-1))) R 0;    // detect if it a single letter word & a vowel
    if(*s==0&&v(*(s-2))&&*(s-1)!='n') R 0;  // test if the last character is not a consonant except 'n'
    R 1;
}
```

---
Tags: code-golf, decision-problem, natural-language
---


title: Is the room lit up?

text:
# Question
Title: Is the room lit up?
Imagine you have a grid where some squares are walls, some are empty, and some are lights that shine for arbitrary distances in the four cardinal directions until they meet walls:

```
####.####
##..L....
####.##.#
####.##L.
##......L

```

In the above grid, the lights cover all the tiles. But in some cases, they may not be:

```
###
.#L
###

```

Your challenge is, given a grid like the one above, determine whether all empty tiles are lit up. You may take input as a matrix of characters or integers, a list of lines, newline-separated lines (as above) with any three distinct characters, etc.

An input may contain none of a type of cell.

You may output truthy and falsy with any of the following:

* Values your language considers truthy or falsy (if applicable), or inverted
* One truthy value and everything else is falsy, or vice versa
* Two consistent values representing truthy and falsy

# Testcases (Given in above format)

Truthy:

```
L

L.
.L

L....
..#L.
....L
.L...

#

L...L...L

#####.###
#L...L...
##.####L.
#.L..####

```

Falsey:

```
.

.#

L#.

.#.
.L.
.#.

L...
L...
L.#.
L...

L.
..

```

# Answer
> 10 votes
# Vyxal, ~~29~~ ~~27~~ ~~25~~ 23 bytes

```
2(⌈ƛƛ:×c[¶1V];Ṅ;∩vṅ)∑¶↔

```

Split on wall, check if any spilt contain light, replace it with 1, transpose, do it again, check sum.

outputs empty string for false, dots otherwise.

-2 by @lyxal (pog)

-2 by @lyxal again (1 minute after first one)

-2 by ... yep still @lyxal

Try it Online!

translate the input

# Answer
> 6 votes
# JavaScript (ES6), 112 bytes

Expects a matrix with \\$0\\$ for walls, \\$3\\$ for lights and \\$4\\$ for empty squares. Returns *false* if the lights cover all the tiles, or *true* otherwise.

```
f=m=>m<(m=m.map((r,y)=>r.map((v,x)=>v&&[1,2,1,2].map((b,d)=>v|=(m[y+--d%2]||0)[x+~-d%2]&b)|v)))?f(m):/4/.test(m)

```

Try it online!

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

```
f=(a,n=4)=>n?f(a[0].map((_,x)=>a.map(c=>(t=c.at(~x))>1?p=t:t|p>>2,p=0)),n-1):!/0/.test(a)

```

Try it online!

Input matrix where 0 = empty, 2 = wall, 4 = light. Output true vs. false.

Rotate the matrix 90deg 4 times, fill empty cell if there is a light on its left side. Finally test if there are any empty cell left.

This function use ES2022 feature `Array#at` which requires a newer version of NodeJs than current TIO available. A Polyfill for `Array#at` is included in the header of TIO code. So it may be tested on it. You may execute it on a more recent version NodeJs without the header.

```
f=
  (a, // input matrix
  n=4 // rotate 4 times
)=>n?
f(
a[0].map((_,x)=>a.map(c=>(t=c.at(~x)) // rotate
/* t */>1?p=t:t|p>>2,p=0) // fill empty cell if there is a light left side
),n-1):
!/0/.test(a) // no empty cells left

```

---

# JavaScript (Node.js), 95 bytes

```
a=>w=>a.every((c,i)=>c|[-2,-1,1,2].some(s=>a.some(_=>t=a[j+=s%2?(j%w-~s)%-~w&&s:s*w/2],j=i)&t))

```

Try it online!

Input flatten matrix with 0 = empty, 1 = light, 2 = wall, and its width. Output true vs. false.

```
a=> // the matrix; 0 = empty, 1 = light, 2 = wall
w=> // width of matrix
a.every(   // if every cell is
  (c,i)=>c| // either cell is not empty
  // or cell is lighted
  [-2,-1,1,2] // four directions; up, left, right, down
  .some(s=>   // any direction that
    a.some(_=>  // repeat enough times (we use `a` only because it is long enough)
      t=a[ // repeat move until current cell is non empty
        j+=s%2? // -2, 2 are left / right, while -1, 1 are up / down
          (j%w-~s)%-~w&&s: // if we reached end of current row, stop move
          s*w/2 // move up or down (may out of bound but we don't care)
      ],
      j=i // starting from cell `i`
    )&t // if non-empty cell exists and the cell is light
  )
)

```

# Answer
> 4 votes
# JavaScript (ES6), 254 bytes

```
d=>!(f=i=>i?f(i-1,d=d.replace(/(?<=a|b)[ c]|[ c](?=a|b)/g,x=>"ab"[+
(x<"!")]),d=(t=s=>[...s.split`
`[0]].map((_,i)=>s.split`
`.map(x=>x[i]).join``).join`
`)(t(d).replace(/(?<=a|c)[ b]|[ b](?=a|c)/g,x=>"ac"[+(x<"!")]))):d)
(d.length+d[0].length).includes` `

```

Uses  for empty spaces, `a` for lights, and any non-alphabetical and non-space character for walls.

# Answer
> 4 votes
# C (gcc), <sup>~~274~~ \\$\cdots\\$ ~~195~~</sup> 191 bytes

```
#define F for(y=0,i=r*c;i--;
#define J(A,B,C,D)for(y=A c;--y+B&&~-m[C*c+D];)m[C*c+D]|=m[i]*2&4;
i;y;f(m,r,c)int*m;{F){J(-i%,c,i/c,-y)J(i%,1,i/c,y)J(-i/,r,-y,i%c)J(i/,1,y,i%c)}F)y|=!m[i];i=y;}

```

Try it online!

*Saved a whopping ~~45~~ \\$\cdots\\$ ~~55~~ 59 bytes and got below 200 thanks to ceilingcat!!!*

Inputs a pointer to an array of integers along with the room dimensions (since pointers in C carry no length info).
These integers represent a room with \\$0\\$ -\> `.`, \\$1\\$ -\> `#`, and \\$2\\$ -\> `L`.
Returns \\$0\\$ if the room is lit up or \\$1\\$ otherwise.

# Answer
> 3 votes
# Jelly, 19 bytes

```
,Z»×¥@\Ṛ$2¡€Z»¥/F’Ạ

```

Try It Online!

"Borrowing" the multiplication idea from Unrelated String (i.e. stealing lol). 0 for `#`, 1 for `.`, 2 for `L`.

# Answer
> 3 votes
# , 43 bytes

```
*-:g&.|:>.g=.**[:}:@;"1<@(#$2&e.);.2"1@,.&0

```

Try it online!

Based on okie's "split on walls and check if each section contains a light" idea.

# Answer
> 3 votes
# 05AB1E (legacy), 21 bytes

```
3xŸvTyT+:yT*y∞:ζí}SßĀ

```

Input as a list of lines, where `.L#` are `012` respectively.

Uses the legacy version of 05AB1E where the `ζ` and `:` builtin works on list of strings, which would have been `€SζJ` and required a map over the lines in the new 05AB1E (ending up 6 bytes longer).

Try it online or verify all test cases.

**Explanation:**

```
3          # Push a 3
 x         # Double it (without popping): 6
  Ÿ        # Pop both and push a list in this range: [3,4,5,6]
   v       # Loop over each of these digits `y`:
        :  #  Replace all:
    T      #   "10"
     yT+   #   with "1y", where `y` is the current digit
           #  (which use the implicit input-list in the first iteration)
         : #  Then infinitely replace all:
    yT*    #   "y0"
       y∞  #   with "yy", where the `y` are again the current digit
    ζí     #  Then rotate once clockwise:
    ζ      #   Zip/transpose; swapping rows/columns
     í     #   Reverse each row
   }       # After the loop, we want to check if any empty spots remain:
    S      # Convert the list of strings to a flattened list of characters
     ß     # Pop and push its minimum
      Ā    # Check if this is NOT 0
           # (after which the result is output implicitly)

```

# Answer
> 2 votes
# Jelly, ~~17~~ 16 bytes

```
»×¥@\Ṛ$⁺
Ç€»ÇF1e

```

Try it online!

*Fixed by borrowing back from hyper-neutrino lmao*

*-1 replacing the double transpose with a map by replacing the map with implicit vectorization*

Takes a matrix of 0 for `#`, 1 for `.`, and 2 for `L`.

```
»×¥@\Ṛ$⁺    Monadic helper link: light up all columns or a row
    \       Scan by
»  @        (vectorizing) max of right and
 ×¥         (vectorizing) product,
     Ṛ      then reverse.
      $⁺    Do it again.

Ç€»ÇF1e    Monadic main link: is there anything unlit?
Ç          Light up
 €         each row,
   Ç       light up the columns,
  »        and take the maximum at each position.
    F      Flatten the result.
     1e    Does it contain 1?

```

# Answer
> 2 votes
Brev, 159, no, 156 bytes:

```
(define (l row) (strse row "[g_]*L+[g_]*" (strse (m 0) "_" "g")))
(print (apply any (compose (strse? "_") l string) (map (o string->list l) (read-lines))))

```

Uses _ instead of . (shaves four bytes) and prints #f for lit up, #t for dark.

Update: remove a redundant partial applicator

# Answer
> 2 votes
# SnakeEx, 34 bytes

```
m:{d<>}{d<R>}{d<L>}{d<B>}
d:,+[#$]

```

Uses `,` instead of `.`; to take inputs formatted as in the question, replace `,` on the second line with `\.`. Outputs one or more matches (truthy) for a room that is not fully lit, no matches (falsey) for a room that is lit. Try it here!

### Explanation

Core idea: find a `,` which can't "see" an `L` in any of the four directions. If no such `,` exists, the room is fully lit; if such a `,` exists, it is not fully lit.

```
d:        Define a helper snake d to match
  ,+      1 or more commas
    [#$]  followed by a pound sign or the edge of the grid

m:                         Define the main snake m to match
  {d<>}                    d in the default direction (left-to-right)
       {d<R>}              and also in the direction 90 degrees clockwise (top-to-bottom)
             {d<L>}        and the direction 90 degrees counterclockwise (bottom-to-top)
                   {d<B>}  and the reverse direction (right-to-left)

```

# Answer
> 2 votes
## Txr Lisp, 109 bytes

```
(do let((l(op mapcar(op regsub #/[. ]*L[. ]*/(op regsub #/\./" ")))))(find #\.(cat-str[l(transpose[l @1])])))

```

## 103 bytes

```
(op find #\.(cat-str[#1=(op mapcar(op regsub #/[. ]*L[. ]*/(op regsub #/\./" ")))(transpose[#1# @1])]))

```

## 97 bytes

Drop `(cat-str X)`, use quasiliteral ``@x``.

```
(op find #\.`@[#1=(op mapcar(op regsub #/[. ]*L[. ]*/(op regsub #/\./" ")))(transpose[#1# @1])]`)

```

This is an expression that evaluate so to a function which operates on sequence of strings, those being the lines of the grid.

The function returns `#\.`, the dot character, to indicate that unlit areas remain. Otherwise it returns `nil`. A character is truthy, and `nil` is the only false value.

The logic is just regex. The `regsub` function matches regular expressions. If the replacement argument is a function, the matched text is passed to it and replaced with what the function returns. For the substitution we use another partially applied `regsub` which replaces dots with spaces.

So, in every string of dots or spaces that contains an `L`, we replace the dots with spaces, doing this in every string. Then we transpose the vector of strings and do it again.

Truthy example:

```
#####.###        #####.###        ####       ####
#L...L...  -->   #L   L      -->  #L#   -->  #L#
##.####L.        ##.####L         # .L       #  L
#.L..####        # L  ####        # #        # #
                                  # #        # #
                                  .L##        L##
                                  # ##       # ##
                                  # L#       # L#
                                  #  #       #  #

```

No dots remain, so everything is lit.

This main list-of-string processing action for replacing the `L`s is a function. In the 109 byte version, it bound to the lexical variable `l`, which we then refer to twice separated by a `transpose` call.

In the 103 byte version, we get rid of the local variable and just repeat the code in two places using the Lisp circle notation. `#1=OBJ` means "`OBJ`, also associated with label 1". And `#1#` then means "reproduce the object from label 1, `OBJ` here". With this we can make a piece of data (i.e. piece of source code, of code is data) appear in two or more places.

# Answer
> 1 votes
# Retina 0.8.2, ~~94~~ 91 bytes

```
(?!_+L|((?<=(.)*)_.*¶(?<-2>.)*(?(2)^))+L)_(?<!L_+|L((?<=(?<!.)(?(4)$)(?<-4>.)*.).*¶(.)*_)+)

```

Try it online! Takes input using `_` as a floor tile instead of `.` but header converts `.` to `_` for you for convenience. Outputs the number of unlit floor tiles, so a falsy value if the room is lit. Explanation:

```
(?!_+L|

```

Don't match a floor tile that is to the left of a light, or...

```
((?<=(.)*)_.*¶(?<-2>.)*(?(2)^))+L)

```

... that is above a light.

```
_

```

Match an unlit floor tile.

```
(?<!L_+|

```

Don't match a floor tile that is to the right of a light, or...

```
L((?<=(?<!.)(?(4)$)(?<-4>.)*.).*¶(.)*_)+)

```

... that is below a light.

.NET balancing groups are used to ensure that the light is in the same column as the tile.

# Answer
> 1 votes
# Charcoal, 47 bytes

```
ＷＳ⊞υιυＦＬυＦ⌕Ａ§υιLＦ⁴«ＪκιＭ✳⊗λＷ﹪℅ＫＫ³⁵✳⊗λ_»≔№ＫＡ.θ⎚¬θ

```

Try it online! Link is to verbose version of code. Takes input as a list of newline-terminated strings and outputs a Charcoal boolean, i.e. `-` if the room is fully lit, nothing if not. Explanation:

```
ＷＳ⊞υιυ

```

Input the map and print it to the canvas.

```
ＦＬυＦ⌕Ａ§υιLＦ⁴«

```

Loop over the lights in all directions.

```
ＪκιＭ✳⊗λ

```

Move to a tile adjacent to a light.

```
Ｗ﹪℅ＫＫ³⁵

```

While this tile is not wall, ...

```
✳⊗λ_

```

... mark it as lit and move to the next tile. (Note: If there are two lamps, they'll light each other, but the loop above checks the original lamps, so it doesn't matter that they get removed from the canvas.)

```
»≔№ＫＡ.θ

```

Count the number of remaining unlit tiles.

```
⎚¬θ

```

Clear the canvas and output the result.

# Answer
> 1 votes
# Python3, 205 bytes:

```
import re
m=lambda x:re.sub('(?:\.+)*L(?:\.+)*',lambda j:'L'*len(j.group()),x)
f=lambda x:all(all(n!=('.','.')for n in zip(m(i),j)if n!=('#','#'))for i,j in zip(x,[*zip(*[m(''.join(c))for c in zip(*x)])]))

```

Try it online!

# Answer
> 1 votes
# Perl 5, 103 bytes

```
sub{$_=pop;while(!$h{$_}++){s/(Ll*)\./$1l/;$r=@l=();map/\s/?$r=0:$l[$r++]=~s/^/$_/,/./gs;$_="@l"}!/\./}

```

Try it online!

# Answer
> 0 votes
# C (gcc), ~~146~~ 141 bytes

```
#define F(d)for(i=r*c;i--;F&=m[i])for(j=i;m[i]>3&1u*j<r*c&m[j]<8&&j/c!=i/c^d*d;j+=d)m[j]|=1;
i;j;F;f(m,r,c)int*m;{F(1)F(-1)F(c)F=1;F(-c)i=F;}

```

Try it online!

Thank ceilingcat for -3 bytes

Not quite sure what Noodle9 did, and not sure why I can't `F(1)(-1)...` here

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


title: Code Golf Birthday Cake

text:
# Question
Title: Code Golf Birthday Cake
Your task is to print this exact text:

```
     | | | | | |
    &***********&
    | Code Golf |
   | e---------f |
  | d___________l |
 | o-------------o |
| C_______________G |
 ###Dennis$Dennis###
#####################

```

# Rules

* Trailing or leading newline is allowed
* , so shortest code wins!

# Answer
> 5 votes
# Vyxal, 71 bytes

```
\|6*Ṅ`&`×6*+∞`¬꘍ »₆`:⌈Rvf÷4ɾd7+‛-_f4Ẏ*$++J‛ |Ḃ∇++÷`###%$`∞‛ṫ¹%\#21*WøĊ⁋

```

Try it Online!

```
=== Top bit ===
\|6*Ṅ`&`×6*+∞
\|6*          # Six |
    Ṅ         # Join by spaces
     `&`   +  # Append to an &
        ×6*   # six asterisks
            ∞ # Palindromise that

=========== Code Golf bit ===========
`¬꘍ »₆`:                              # Compressed string `Code Golf`, two copies
        ⌈R                            # Split on spaces and reverse each word
          vf÷                         # Make each a char list and push each
             4ɾ                       # 1...4
               d7+                    # Double + 7 -> 9, 11, 13, 15
                  ‛-_f4Ẏ              # Extend `-_` into length 4 and turn into char list
                        *             # Repeat characters by numbers
                         $++          # Join the `Code Golf` bit by those
                            J         # Append `Code Golf`
                             ‛ |Ḃ     # Push ` |` and `| `
                                 ∇++  # Prepend `| ` and append ` |` to each
                                    ÷ # Push each value to the stack.

=== Final bit ===
`###%$`               # Literal string `###%$`
       ∞              # Palindromised
        ‛ṫ¹%          # Format (replace % by) "Dennis"
            \#21*     # 21 #
                 WøĊ⁋ # Output the stack, centred and joined on newlines.

```

# Answer
> 2 votes
# Charcoal, 69 bytes

```
× |³⸿×*⁶&⸿Ｅ⁵⁺×§_-ι⁺⁵ι |Ｅ²×#⁺χι‖Ｏ←Ｍ±⁶±²…Dennis$¹³↗↖Golf←floG edo↙CedoC

```

Try it online! Link is to verbose version of code. Explanation: Outputs the right half of the cake body, reflects it, then adds in the lettering.

```
× |³⸿

```

Handle the candles.

```
×*⁶&⸿

```

Handle the icing.

```
Ｅ⁵⁺×§_-ι⁺⁵ι |

```

Draw the bulk of the cake.

```
Ｅ²×#⁺χι

```

Draw the base of the cake.

```
‖Ｏ←

```

Reflect to complete the cake body.

```
Ｍ±⁶±²…Dennis$¹³↗

```

Cyclically extend the string `Dennis$` to 13 characters and output it in the appropriate position.

```
↖Golf←floG edo↙CedoC

```

Add the two copies of `Code` and `Golf`.

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

```
_=>` 5|@@@@@
 4&*11&
 4| Code Golf@
 3| e-9f@
 @ d_11l@
@ o-13o@
| C_15G@
 #3Dennis$Dennis#3
#21`.replace(/@|.(\d+)/g,([c],n)=>c.repeat(n)||' |')

```

Try it online!

# Answer
> 1 votes
# Retina 0.8.2, 114 bytes

```

    6$*¦¶    &11$**&¶   ¦ Code Golf¦¶  ¦ e9$*-f¦¶ ¦ d11$*_l¦¶¦ o13$*-o¦¶| C15$*_G¦¶ ###D$D###¶21$*#
¦
 |
D
Dennis

```

Try it online! Explanation:

```

    6$*¦¶    &11$**&¶   ¦ Code Golf¦¶  ¦ e9$*-f¦¶ ¦ d11$*_l¦¶¦ o13$*-o¦¶| C15$*_G¦¶ ###D$D###¶21$*#

```

Insert most of the cake using run-length encoding.

```
¦
 |
D
Dennis

```

Make a couple of substitutions that save a few bytes. (In particular, the `¦` substitution allows me to write `6$*¦` to mean  `| | | | | |`.)

# Answer
> 0 votes
# Perl 5 \+ `-p0513`, 119 bytes

Pretty much just RLE, nothing too exciting.

```
s''4 6P
4 &11*&
3 P Code GolfP
  P e9-fP
 P d11_lP
P o13-oP
| C15_GP
 3#Dennis$Dennis3#
21#';s/\d+(.)/$1x$&/ge;s/P/ |/g

```

Try it online!

# Answer
> 0 votes
# 05AB1E, 77 bytes

```
„| 11∍'*11×'&.ø”|ƒËŠˆ |”©Âá4.£v'|y„-_NèN·9+×y®á2ä`‡««‚Ć}”¼´$”13∍…###.ø¬21×».c

```

Try it online.

**Explanation:**

```
„|               # Push string "| "
   11∍           # Extend it to size 11: "| | | | | |"
'*              '# Push character "*"
  11×            # Repeat it 11 times: "***********"
     '&.ø       '# Surround it with leading/trailing "&": "&***********&"
”|ƒËŠˆ |”        # Push dictionary string "| Code Golf |"
         ©       # Store it in variable `®` (without popping)
Â                # Bifurcate it (short for Duplicate & Reverse copy):
                 # "| floG edoC |"
 á               # Only leave the letters: "floGedoC"
  4.£            # Only leave the last 4 characters: "edoC"
     v           # Foreach `y` over these characters:
      '|        '#  Push character "|"
      y          #  Push character `y`
      „-_        #  Push string "-|"
         Nè      #  Index (0-based modular) the map-index into this string
           N·    #  Push double the map-index
             9+  #  Add 9
               × #  Repeat the character that many times
      y          #  Push the character again
       ®         #  Push "| Code Golf |" from variable `®`
        á        #  Only leave its letters: "CodeGolf"
         2ä      #  Split it into two equal-sized parts: ["Code","Gold"]
           `     #  Pop and push both separated to the stack
            ‡    #  Transliterate
      ««         #  Append the top three strings together
      ‚          #  Pair it with the "|"
       Ć         #  Enclose; append its own head (the "|")
     }           # Close the foreach
”¼´$”            # Push dictionary string "Dennis$"
     13∍         # Extend it to size 13: "Dennis$Dennis"
        …###.ø   # Surround it with leading/trailing "###":
                 # "###Dennis$Dennis###"
¬                # Push the first character (without popping): "#"
 21×             # Repeat it 21 times: "###################"
»                # Join each list on the stack by spaces,
                 # and then all strings on the stack by newlines
 .c              # Centralize it, adding leading spaces where necessary
                 # (after which the result is output implicitly)

```

See this 05AB1E tip of mine (section *How to use the dictionary?*) to understand why `”|ƒËŠˆ |”` is `"| Code Golf |"` and `”¼´$”` is `"Dennis$"`.

---
Tags: code-golf, kolmogorov-complexity
---


title: Compress and decompress

text:
# Question
Title: Compress and decompress
Your task is to make a bidirectional compressor. It takes a list of bytes as input and returns a list of bytes as output. It has the property than whenever it is iterated twice it returns the original input.

In other words, if `f` is your program as a function, then `f(f(x))=x` for all `x`.

Now, since this is a "compressor", it should actually try to compress it's input. Of course, it can't compress every input. It should however be able to compress your program's source code. That is, if `s` is your program's source code, then `len(f(s))<len(s)`.

To recap, your program acts as a function that takes a list of bytes as input and outputs a list of bytes as output. Let's call your program `f` and it's source code `s`. Your program must satisfy both:

* `f(f(x)) = x` for all `x`
* `len(f(s)) < len(s)`

Remember that the empty list is a list, and thus your code should be able to handle it.

Normal quine rules apply, so no introspection is allowed (opening the file that contains your source code, etc.).

Shortest code wins!

# Answer
# JavaScript (ES6), 26 bytes

*-1 thanks to @thejonymyster*

*-7 thanks to @Arnauld*

*-4 thanks to @l4m2*

```
x=>x.replace(/-2|1/,z=>~z)

```

Swaps the first instance of `-2` and `1`, saving 1 byte when the program compresses itself. Takes the list of bytes as input, as a string.

This is quite the community effort now :p
> 11 votes

# Answer
# , ~~102~~ 59 bytes

```
function(x)`if`(nchar(x)%%2,sub("#$","",x),sub("$","#",x))#

```

Try it online!

`f()` removes any trailing `#` comment character if there are an odd number of characters in the input (as in `myprog`), or adds one if there are an even number.

(Removing the first `f` would also work, and is 1-byte shorter, but it's less satisfying as the 'compressed' function is no longer a runnable compression function itself...)
> 5 votes

# Answer
# C (gcc), 49 bytes

```
A;f(char*s){s[-1]=65;A=s[A=*s==65]-59?s:s-1+A*2;}

```

Try it online!

Surculose Sputum's idea

# C (gcc), ~~55~~ ~~54~~ 52 bytes

```
A;f(char*s){A=*s-(s[-1]=65)?s-1:*++s-65?s:f(s+1)-2;}

```

Try it online!

Thank gastropner for -2 bytes

Requires `s[-1]` be writable
> 3 votes

# Answer
# Zsh, 35 bytes

```
printf %s ${1/(#m)(-3|2)/$[~MATCH]}
```

Attempt This Online!

Previous version independently discovered to l4m2's golf to Redwolf's answer, goddamn ninjas! (now just a lazy port :/)

Swaps the first instance of `-3` for `2` and vice versa.
> 2 votes

# Answer
# APL (Dyalog Unicode), 37 bytes

```
'¯2|1'⎕R{⍕83⎕Dr~11⎕Dr⍎⍵.Match}⍠'ML'1⊢

```

Try it online!

Same thing as everyone else here has done replaces ¯1 with 1 and vice versa

and it works this time for sure :D
> 2 votes

# Answer
# Retina 0.8.2, 18 bytes

```
1`-1|(2)
$#1$*-$.&

```

Try it online! Explanation: Port of @RedwolfPrograms' JavaScript answer.

```
1`

```

Only replace the first match.

```
-1|(2)

```

Match `-1` or `2`.

```
$#1$*-

```

Output `-` only if `2` was matched.

```
$.&

```

Output the length of the match.
> 1 votes

# Answer
# Haskell, 54 bytes

```
f('l':')':l)='!':l;f('!':l)="l)"++l;f(x:l)=x:f l;f_=[]

```

Try it Online!

Switches the first occurrence of `l)` and `!`.
> 1 votes

# Answer
# Python 3, 48 bytes

*Thanks @AnttiP for pointing out the error in a previous version.*

```
lambda s:['l'+s,s[1:],s][('l'+s[:2]).find('la')]

```

Try it online!

Takes in a string and compress/decompress it.

* If the input starts with `a`, prepends `l`
* If the input starts with `la`, then remove the first character `l`.
* Otherwise, returns the input unchanged

`('l'+s[:2]).find('la')` evaluates to 0, 1, -1 for each of the above case respectively. This is because by prepending `l` to the first 2 characters, we get `l??`. If we find `la` at the 0th index (`la?`), then the first character of input must be `a`. If we finds `la` at the 1st index (`lla`), then the input must starts with `la`.
> 1 votes

---
Tags: code-golf, compression, open-ended-function, self-referential
---


title: Sides of a polygon

text:
# Question
Title: Sides of a polygon
Given an ASCII-art shape made of the characters `/\|_`, your challenge is to return the number of sides it has.

A side is a straight line of one of those, for example:

```
\
 \
  \

 /
/

|
|
|
|

_____

```

Are all sides.

For example, this shape:

```
  ___
 /   \
/_____\

```

Has *four* sides. You can assume the input will be a single valid, closed shape - that is, things like this:

```
/
 _
/ \

 \
/

/_\
\_/
 _   _
/_\ /_\

```

Will *not* occur, and the shape will never touch itself, so this is invalid:

```
  /\/\
 / /\ \
/ /__\ \
|______|

```

## Testcases:

```
 /\
/__\ -> 3

 ________
/        \
|_________\  -> 5

___
|_| -> 4

/\/\/\/\/\
|________| -> 13

 _   _
| |_| |
|  _  | -> 12
|_| |_|

         /\
        /  \
   /\  /    \    /\
  /  \/      \  /  \
 /            \/    \
/____________________\ -> 7

   _
  / |
 _| |
/___/ -> 8

```

# Answer
> 7 votes
# , 49 bytes

*-1 thanks to Jonah*

This answer has 6 sides.

```
[:+/@,i.@4(1==-{&(0 1,1,.i:1)@[|.!.0=)"{'_/|\'&i.

```

Try it online!

* `'_/|\'&i.` Map walls to 0…4.
* `i.@4` For each possible wall …
* `|.!.0=` shift the corresponding bitmap …
* `{&(0 1,1,.i:1)@[` into the direction the wall points to.
* `1==-` Subtract this from the original bitmap and keep the 1s.
* `[:+/@,` Count the 1s.

Example for the `_`-lines in

```
____
|__|   original
 ____
 |__|  shifted by 1 into a direction _ points to

X....  spots where _ is in the original image,
.X...  but not in the shifted one.

```

Two Xs, thus two `_`-lines.

# Answer
> 3 votes
# Retina 0.8.2, 94 bytes

```
(?<=(.)*)(\|(?=.*¶(?<-1>.)*\|)|\\(?=.*¶(?<-1>.)*.\\)|/(?=.*¶(?<-1>.)*(?<-1>/)))(?(1)^)

_+|\S

```

Try it online! Link includes test suite that takes double-spaced test cases. Explanation:

```
(?<=(.)*)(\|(?=.*¶(?<-1>.)*\|)|\\(?=.*¶(?<-1>.)*.\\)|/(?=.*¶(?<-1>.)*(?<-1>/)))(?(1)^)

```

Match any of `|`, `\` or `/` with the corresponding symbol on the next line, but indented to line up with it and replace it with a space. (This is slightly golfier than using negative lookaheads.)

```
_+|\S

```

Count any remaining non-whitespace, except a run of `_` only counts as one side.

# Answer
> 2 votes
# Charcoal, 42 bytes

```
ＷＳ⊞υι≔⪫υ⸿θＰθＦθ⎇№⁺ ⊟ＫＤ²✳⊕｜⌕/|\ι⁴ιψι≔ＬＫＡθ⎚Ｉθ

```

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

```
ＷＳ⊞υι

```

Input the list of strings.

```
≔⪫υ⸿θ

```

Join them with carriage returns.

```
Ｐθ

```

Print the result to the canvas without moving the cursor.

```
Ｆθ

```

Loop over each character.

```
⎇№⁺ ⊟ＫＤ²✳⊕｜⌕/|\ι⁴ιψι

```

If the character is a space or equal to the adjacent character in the appropriate direction (E, SE, S or SW as appropriate), then erase it, otherwise reprint it.

```
≔ＬＫＡθ

```

Count the number of remaining characters on the canvas.

```
⎚Ｉθ

```

Clear the canvas and output the result.

# Answer
> 0 votes
# Python3, 598 bytes:

```
import re
def f(b,c,l,s=[]):
 k=0
 for u,v in{'/':[[-1,1],[1,-1]],'\\':[[1,1],[-1,-1]]}[l]:
  if(x:=c[0]+u)>=0 and(y:=c[1]+v)>=0 and(x,y)not in s:
   try:
    if b[x][y]==l:k=1;yield from f(b,(x,y),l,s+[(x,y)])
   except:1
 if k==0:yield tuple(sorted(s))
def g(b):
 b=[*filter(None,b.split('\n'))]
 e=enumerate;S=set;R=sum;L=len
 t=[((x,y),j) for x,a in e(b)for y,j in e(a)if j=='/'or j=='\\']
 n={m for i in t for m in f(b,i[0],i[-1],[i[0]])}
 return R(not any(S(i)&S(j)==S(i)and L(j)>L(i)for j in n)for i in n)+R(L(re.findall('_+',i))for i in b)+R(L(re.findall('\|+',''.join(i)))for i in zip(*b))

```

Very simple algorithm: find the number of diagonal edges (using `f`), and then the number of horizontal and vertical edges (using `re.findall`)

Try it online!

---
Tags: code-golf, string, ascii-art, grid, pattern-matching
---