title: Simplified Piet Interpreter

text:
# Question
Title: Simplified Piet Interpreter
### Background

Piet is an esoteric stack-based programming language in which programs are images meant to resemble abstract paintings.

To keep the challenge from being unnecessarily complex, you will not have to consider most of the colors present in Piet, which determine what instructions are executed; instead, each type of instruction will be assigned a specific number or character (more in **Code Instructions**).

A codel is the basic unit of Piet code, and can be at any size. For the sake of this challenge, you can assume that a codel is a number/character.

A color block is a contiguous region of codels of the same color which is bounded by codels of other colors, or the edge of the program image. A color block can contain another color block within itself, which is counted as a separate color block from the surrounding one. Codels that share corners are not considered to be part of the same color block.

Piet uses a stack to store all data values, which are integers.

### Code Execution

A Piet program begins execution in the color block which contains the top left codel of the program. The interpreter contains a Direction Pointer (DP), which initially points to the right. The DP can point up, down, left or right. The interpreter also contains a Codel Chooser (CC), which is initially pointing left. The CC can either point left or right.

As the program is executed, the interpreter travels through the program under the following rules:

1. The interpreter finds the edge of the current color block which is furthest in the direction of the DP. (This edge may be disjoint if the block is of a complex shape.)
2. The interpreter finds the codel of the current color block on that edge which is furthest to the CC's direction of the DP's direction of travel. (Visualize this as standing on the program and walking in the direction of the DP; see table at below.)
3. The interpreter travels from that codel into the color block containing the codel immediately in the direction of the DP.

The program continues following these rules until the code terminates.

(CC table)

| DP | CC | Codel Chosen |
| --- | --- | --- |
| right | left | uppermost |
| right | right | lowermost |
| down | left | rightmost |
| down | right | leftmost |
| left | left | lowermost |
| left | right | uppermost |
| up | left | leftmost |
| up | right | rightmost |

### More Info on Color Blocks

Each non-black and non-white color block (white and black are special colors; more on that later) represents a number equal to the number of codels in that block. Though the interpreter may pass through a color block during execution, it does not necessarily do anything with the color block's stored value; there are specific instructions that deal with these values.

Black color blocks and edges of the program restrict program flow. If the Piet interpreter attempts to move into a black block or off an edge, it is stopped and the CC is toggled. The interpreter then attempts to move from its current block again. If it fails a second time, the DP is moved clockwise one step. These attempts are repeated, with the CC and DP being changed between alternate attempts. If after eight attempts the interpreter cannot leave its current color block, there is no way out and the program terminates.

White color blocks are essentially no-op's in which the interpreter passes unhindered. When the interpreter moves into a white block, it follows the following steps:

* The interpreter "slides" across the white block in a straight line.
* If it hits a restriction, the CC is toggled. Since this results in no difference in where the interpreter is trying to go, the DP is immediately stepped clockwise.
* The interpreter now begins sliding from its current white codel, in the new direction of the DP, until it either enters a colored block or encounters another restriction.
* Each time the interpreter hits a restriction while within the white block, it toggles the CC and steps the DP clockwise, then tries to slide again. This process repeats until the interpreter either enters a colored block (where execution then continues); or until the interpreter begins retracing its route. If it retraces its route entirely within a white block, there is no way out of the white block and execution should terminate.

In the actual Piet language, no instructions are executed upon exiting a white color block. In this regard, this challenge is different from Piet; namely, instructions **are executed upon exiting a white color block**.

### Code Instructions

As stated at the very beginning, to simplify the challenge, colors will not be used. Instead, each instruction will be mapped to a specific number/character of your choosing. When the interpreter enters a color block of a certain number/character, the corresponding instruction is executed. Any operations which cannot be performed (such as popping values when not enough are on the stack) are simply ignored, and processing continues with the next command. The corresponding instruction of the top left color block is not executed when initially running the program (though it will still have a value), but will run on any subsequent visits to the color block.

The instructions are as follows (these are just a subset of all the Piet instructions):

* **Push**: Pushes the value of the color block just exited onto the top of the stack.
* **Pop**: Deletes the value on the top of the stack
* **Add**: Pops the top two values off the stack and pushes the sum of those two numbers onto the stack
* **Subtract**: Pops the top two values off the stack and pushes the difference between the second topmost value and the top value of the stack
* **Multiply**: Pops the top two values off the stack and pushes the product of those two numbers onto the stack
* **Divide**: Pops the top two values off the stack and pushes the quotient between the second topmost value and the top value
* **Pointer**: Pops the top value off the stack and rotates the DP clockwise that many steps (anticlockwise if negative).
* **Switch**: Pops the top value off the stack and toggles the CC that many times (the absolute value of that many times if negative).

### Task

Choose 10 distinct numbers/characters which each represent one of the code instructions and the black and white codels, and clearly specify which 10 you chose in your answer.

Given a 2d rectangular grid, matrix, or a similar default I/O format consisting of the 10 different characters/numbers of your choosing representing a Piet program, output the final state of the stack after the input program has halted. Assume that all input programs will eventually halt.

The output can be in any reasonable or default output format, as long as it's clear what the state of the stack is. You can also output the stack with the "first" value representing the top of the stack, or the "last" value representing the top of the stack. For example, if the final state of the stack has `2` as the top value, `3` as the second topmost value, and `4` at the bottom of the stack, then both `[2,3,4]` and `[4,3,2]` are acceptable output formats. Make sure to include in your answer which output format you are using out of the two.

You can also optionally take in the dimensions of the Piet program.

### Worked Example

In this example, `0` is push, `1` is pop, `2` is add, `3` is subtract, `4` is multiply, `5` is divide, `6` is pointer, `7` is switch, `8` is white, `9` is black.

I will also use `>`, `<`, `^`, `v` to indicate where the interpreter is and what direction the DP is pointing.

Program:

```
111090908004
911088808944
911069912399

```

The program starts in the color block containing the top left codel, which is the 3 by 3 block of `1`'s. Remember that the initial instruction upon running the code is not ran, so `pop` (the instruction mapped to `1` in our example) is not ran. Also note that this color block has a value of 7, because it consists of 7 codels.

```
>11090908001
911088808911
911069912399

```

Initially, the DP is pointing right, so the interpreter goes to the right edge of the color block. The CC is pointing left, which means that the interpreter first tests the top-right edge for any restrictions.

```
11>090908001
911088808911
911069912399

```

There are none, so it travels to the right into the next color block, which is the block of `0`'s. `0` represents the push instruction, so 7 is pushed to the top of the stack. The stack is now `[7]`. At this point, the DP is pointing right, and the CC is pointing left, so it first tests the top-right edge for restrictions.

```
111>90908004
911088808944
911069912399

```

There is a black codel (`9`) restricting the program flow, so the CC is toggled and is now pointing to the right. The bottom right edge is now tested:

```
111090908004
911088808944
911>69912399

```

There are no restrictions here, so the interpreter travels to the code block to the right, which is the `6`. `6` is the pointer instruction, which rotates the DP clockwise 7 times (7 is on the top of the stack) and pops the 7 off the stack, leaving the stack empty. The DP was pointing right, so after 7 clockwise rotations, it points up.

```
111090908004
911088808944
9110^9912399

```

There are no restrictions in that direction, so the interpreter moves into the white code block.

```
111090908004
9110^8808944
911069912399

```

In white code blocks, the interpreter slides across white codels in a straight line until it hits a restriction, after which the DP is rotated clockwise, and the CC is toggled once. In this case, right after entering the white codel, there is a restriction in the upwards direction, so the DP is turned to the right, and the CC is toggled from right to left.

```
111090908004
9110>8808944
911069912399

```

There are no restrictions in this direction, so the interpreter slides across the remaining white codels until it reaches the block of `0`'s. `0` is the push instruction, so it pushes 3 to the top of the stack (because the white block that the interpreter just exited contains 3 codels). The stack is now `[3]`. The DP is pointing right and the CC is pointing left, so the interpreter checks the top-right edge first:

```
1110909>8004
911088808944
911069912399

```

There are no restrictions in this direction, so it travels into the white block.

```
11109090>004
911088808944
911069912399

```

The interpreter slides across the white block in a straight line until it enters the block of `0`'s. `0` is the push command, so 2 (the value of the white block that the interpreter just exited) is pushed onto the top of the stack. The stack is now `[2,3]`. The DP is pointing right and the CC is pointing left, so the top-right edge is checked:

```
1110909080>4
911088808944
911069912399

```

There are no restrictions in that direction, so it enters into the block of `4`'s. `4` is the multiply command, so it pops the top two values off the stack and pushes the product of the two popped values. The stack is `[2,3]`, so the `2` and `3` are popped off, and `2*3=6` is pushed onto the stack. The stack is now `[6]`.

The DP is pointing the the right and the CC is pointing to the left, so the top right edge is tested first:

```
11109090800>
911088808944
911069912399

```

There is a restriction in that direction (namely, the edge of the program), so the CC is toggled, making it point to the right. The bottom right edge is now tested:

```
111090908004
91108880894>
911069912399

```

There is also a restriction in that direction, so the DP is rotated clockwise once, making it point downwards. The CC is pointing to the right, so the bottom left edge is tested:

```
111090908004
9110888089v4
911069912399

```

There is also a restriction in that direction, so the CC is toggled, making it point to the left. The bottom right edge is now tested:

```
111090908004
91108880894v
911069912399

```

There is also a restriction in that direction, so the DP is rotated clockwise once, making it point to the left. The CC is pointing to the right, so the top left edge is tested:

```
111090908004
9110888089<4
911069912399

```

There is a restriction in that direction, so the CC is toggled, making it point to the left. This results in the same edge being chosen, which we already established to have a restriction. The DP is then rotated clockwise once, making it point upwards. The CC is pointing to the left, so the top leftmost edge is tested:

```
11109090800^
911088808944
911069912399

```

There's also a restriction in that direction, so the CC is toggled, making it point to the right. This results in the same edge being chosen, which is already known to have a restriction. At this point, 8 unsuccessful attempts have been made at getting out of this color block, so the interpreter concludes that there is no way out of this color block and terminates the program.

The final state of the stack is `[6]`.

### Test Cases

Uses the same character set as the worked example above.

```
111090908004
911088808944
911069912399
-> [6]

1199999999999999
9890888898889889
8880888000888808
8880889888988898
-> [3,9,7,9,7]

21234567000880
99999900000999
40330000000088
44988888888889
-> [-22]

```

This is , so shortest code in bytes wins!

---

Reference: official Piet specification

# Answer
# Python3, 1383 bytes:

```
lambda b:M(set(),b,0,2,[],(0,0))
T={0:(L:={0:max,2:min}),1:(K:={0:min,2:max}),2:K,3:L}
Q={0:(0,1),1:(1,0),2:(0,-1),3:(-1,0)}
I={0:lambda s,v,*a:[*a,[v]+s],1:lambda s,v,*a:[*a,s[1:]],2:lambda s,v,*a:[*a,[sum(s[:2])]+s[2:]],3:lambda s,v,*a:[*a,[s[1]-s[0]]+s[2:]],4:lambda s,v,*a:[*a,[s[0]*s[1]]+s[2:]],5:lambda s,v,*a:[*a,[s[1]/s[0]]+s[2:]],6:lambda s,v,DC,CC:[(s[0]+DC)%4,CC,s[1:]]if s else[DC,CC,s],7:lambda s,v,DC,CC:[DC,[0,2][abs(s[0])%2],s[1:]]}
def V(b,x,y):
 try:
  return 0 if b[x][y]==9 or x<0 or y<0 else 1
 except:return 0
def C(b,v,s):
 q,S,D,d=[s],[s],{s[0]:[s[1]]},{s[1]:[s[0]]}
 while q:
  x,y=q.pop(0)
  for n,m in Q.values():
   if(X:=x+n)>=0 and(Y:=y+m)>=0:
    try:
     if(X,Y)not in S and b[X][Y]==v:q+=[(X,Y)];S+=[(X,Y)];D[X]=D.get(X,[])+[Y];d[Y]=d.get(Y,[])+[X]
    except:1
 return S,D,d
def M(H,b,DC,CC,s,c,P=0,E=[]):
 if(_:=str([DC,CC,s,c,P,E,b[c[0]][c[1]]]))in H:return s
 H.add(_)
 x,*y=C(b,S:=b[c[0]][c[1]],c)
 if P==8:return s
 if S==8:X,Y=c
 else:
  if DC in[0,2]:X=T[DC][CC](y[1][(Y:=[max,min][DC==2](y[1]))])
  else:Y=T[DC][CC](y[0][(X:=[max,min][DC==3](y[0]))])
 if V(b,A:=X+Q[DC][0],B:=Y+Q[DC][1]):return M(H,b,*(I[b[A][B]](s,len(x),DC,CC)if b[A][B]in I and(s or b[A][B]<2)else[DC,CC,s]),(A,B),0,[])
 if S!=8:return M(H,b,(DC+1)%4 if P%2 else DC,[0,2][CC==0]if not P%2 else CC,s,(X,Y),P+1,[])
 return M(H,b,(DC+1)%4,[0,2][CC==0],s,(X,Y),0,E+[(X,Y)])

```

Try it online!
> 6 votes

---
Tags: code-golf, grid, interpreter, simulation
---


# Question
Title: Is this propositional formula an instance of an axiom?
Please help me automate my discrete mathematics homework. Given a valid propositional formula, check if it is an instance of one of Łukasiewicz's axioms. Here's how it works.

A *term* can be defined inductively as follows:

* Single lower-case letters of the Latin alphabet (`a`, `b`, `c`, etcetera) are terms.
* Given a term `ϕ`, `¬ϕ` is also a term.
* Given terms `ϕ` and `ψ`, `(ϕ→ψ)` is also a term.

A formula is itself a term, usually made up of smaller terms. An example of a formula is `(a→b)→¬(¬c→¬¬a)`.

Now, these are the three axioms. They are formula templates; some formulae are instances of an axiom. You make an instance by replacing all the variables (the Greek letters) with terms.

```
A: ϕ→(ψ→ϕ)
B: (ϕ→(ψ→χ))→((ϕ→ψ)→(ϕ→χ))
C: (¬ϕ→¬ψ)→(ψ→ϕ)

```

Same Greek letters have to be substituted with the same terms. Thus, one instance of the axiom A is `(b→¬c)→(c→(b→¬c))`. In this case `ϕ` has been substituted with `(b→¬c)`, and `ψ` with `c`. Key to solving problems or making proofs in propositional logic is recognising when formulae are instances of axioms.

Note that all these axioms have their outer parens stripped away, which is common to do on the highest level. The strict way to write these is `(ϕ→(ψ→ϕ))` `((ϕ→(ψ→χ))→((ϕ→ψ)→(ϕ→χ)))` `((¬ϕ→¬ψ)→(ψ→ϕ))`, with surrounding parens, but people usually leave those out when the meaning is clear so I'll leave it free how you choose to parse them.

The goal of the program is to take as input a **valid** formula in string or character array format, and output A, B or C (upper or lower case is fine) if it is an instance of the respective axiom, and do something else (output zero, output nothing, basically do anything except throwing an error) if it is not. The question is ; the shortest code wins!

### Test cases

```
input; output
(a→(a→a))→((a→a)→(a→a)); B
(a→(b→¬¬¬¬¬c))→((a→b)→(a→¬¬¬¬¬c)); B
(¬¬¬x→¬z)→(z→¬¬x); C
(¬(a→(b→¬c))→¬(c→c))→((c→c)→(a→(b→¬c))); C
(b→¬c)→(c→(b→¬c)); A
a→(b→c); 0

```

Alternatively, with surrounding parentheses:

```
input; output
((a→(a→a))→((a→a)→(a→a))); B
((a→(b→¬¬¬¬¬c))→((a→b)→(a→¬¬¬¬¬c))); B
((¬¬¬x→¬z)→(z→¬¬x)); C
((¬(a→(b→¬c))→¬(c→c))→((c→c)→(a→(b→¬c)))); C
((b→¬c)→(c→(b→¬c))); A
(a→(b→c)); 0

```

If you want to stick with printable ascii characters, you can use \> for → and ! for ¬:

```
input; output
(a>(a>a))>((a>a)>(a>a)); B
(a>(b>!!!!!c))>((a>b)>(a>!!!!!c)); B
(!!!x>!z)>(z>!!x); C
(!(a>(b>!c))>!(c>c))>((c>c)>(a>(b>!c))); C
(b>!c)>(c>(b>!c)); A
a>(b>c); 0

```

Alternatively, with surrounding parentheses:

```
input; output
((a>(a>a))>((a>a)>(a>a))); B
((a>(b>!!!!!c))>((a>b)>(a>!!!!!c))); B
((!!!x>!z)>(z>!!x)); C
((!(a>(b>!c))>!(c>c))>((c>c)>(a>(b>!c)))); C
((b>!c)>(c>(b>!c))); A
(a>(b>c)); 0

```

# Answer
# Pip, ~~99~~ 83 bytes

```
(AZ'^.("9>,9>\1
,9>,9>9  >,,\1>\2 >,\1>\3
,!9>!9 >,\2>\1"R9C+XX^n).` $`NaTRpk@?:1)

```

Attempt This Online!

### Explanation

A lightly compressed regex solution.

First, we're going to modify the input a bit:

```
aTRpk
a      Command-line argument
 TR    Transliterate
   p    from "()"
    k   to ", "

```

Using `,`  in place of `()` saves bytes on backslashes in the regexes.

Next, we're going to construct a list containing the following three regexes for axioms A, B, and C respectively:

```
^(.+)>,.+>\1 $
^            $  The full string must match
 (.+)           Match any run of characters (capture group 1)
     >,         →(
       .+       Match any run of characters
         >      →
          \1    Match group 1 again
            ␠   )

^,(.+)>,(.+)>(.+)  >,,\1>\2 >,\1>\3  $
^                                    $  The full string must match
 ,                                      (
  (.+)                                  Match any run of characters (capture group 1)
      >,                                →(
        (.+)                            Match any run of characters (capture group 2)
            >                           →
             (.+)                       Match any run of characters (capture group 3)
                 ␠␠>,,                  ))→((
                      \1                Match group 1 again
                        >               →
                         \2             Match group 2 again
                           ␠>,          )→(
                              \1        Match group 1 again
                                >       →
                                 \3     Match group 3 again
                                   ␠␠   ))

^,!(.+)>!(.+) >,\2>\1 $
^                     $  The full string must match
 ,!                      (¬
   (.+)                  Match any run of characters (capture group 1)
       >!                →¬
         (.+)            Match any run of characters (capture group 2)
             ␠>,         )→(
                \2       Match group 2 again
                  >      →
                   \1    Match group 1 again
                     ␠   )

```

We start with this string:

```
"9>,9>\1
,9>,9>9  >,,\1>\2 >,\1>\3
,!9>!9 >,\2>\1"

```

Then:

```
'^.("..."R9C+XX^n).` $`
    "..."                The above string
         R9              Replace each 9 with:
             XX            Regex `.`
            +              Apply + quantifier: `.+`
           C               Wrap in capture group: `(.+)`
               ^n        Split the resulting string on newlines
'^.                      Concatenate "^" to the front
                 .` $`   Concatenate ` $` to the end, coercing the result to a regex

```

Now we use the `N` operator to count the number of matches of each of these regexes in the transliterated input. The result will be a list of 0's and 1's: `[1 0 0]` if the first regex matched, `[0 1 0]` if the second matched, `[0 0 1]` if the third matched, or `[0 0 0]` if none matched.

Finally:

```
(AZ...@?:1)
   ...       That three-element list
      @?:    Find the index of the first occurrence of
         1   1
(AZ       )  Use that number to index into the uppercase alphabet
             If 1 is not found, returns nil, which results in no output

```
> 6 votes

# Answer
# Curry (PAKCS), 175 bytes

```
n s='!':s
s%t='(':s++'>':t++")"
p[a]|a>'`'=1
p(n s)=p s
p(s%t)=p s*p t
f(a++'>':b%a)|p a==p b="A"
f(a%(b%c)++'>':(a%b)%(a%c))|p a*p b==p c="B"
f(n a%n b++'>':b%a)|p a==p b="C"

```

Try it online!

Takes input in ASCII characters. Returns nothing if it is not an axiom.
> 7 votes

# Answer
# Python3, 450 bytes:

```
lambda t,y:next((b for a,b in t if all(c(a,p(y)[0],{}))),0)
T=type
def p(s,c=0):
 q,n=[],0
 while s and(c==0 or s[0]!=')'):
  n+=(S:=s[0])=='!'
  if S.isalpha():q+=[[n,S]];n=0
  if S=='(':t,s=p(s[1:],1);q+=[(n,t)];n=0
  s=s[1:]
 return q,s
def c(a,b,d):
 if T(a)!=T(b):return
 for x,y in zip(a,b):
  p,q=x;n,m=y
  if(t:=T(x))==list:yield all([d.get(q,m)==m,not p or p%2==n%2]);d[q]=m
  if t==tuple:yield all([T(y)==tuple,not p or p%2==n%2,*c(q,m,d)])

```

Try it online!
> 2 votes

# Answer
# Retina 0.8.2, 102 bytes

```
T`()`{}
{((.+)>{.+>\2}|(.+)>{(.+)>(.+)}}>{{\3>\4}>{\3>\5}|!(.+)>!(.+)}>{\7>\6)}$|.+
$#2$*A$#4$*B$#6$*C

```

Try it online! Link includes test cases. Outputs nothing unless the input is one of the axioms. Explanation: Another regex-based answer.

```
T`()`{}

```

Translate the `()`s to `{}`s to avoid 14 `\`s.

```
{((.+)>{.+>\2}|(.+)>{(.+)>(.+)}}>{{\3>\4}>{\3>\5}|!(.+)>!(.+)}>{\7>\6)}$|.+

```

Try to match one of the three axioms, but if there isn't an immediate match then just match everything.

```
$#2$*A$#4$*B$#6$*C

```

Output the corresponding letter if one of the capture groups in the relevant axiom exists. (Axiom `A` only has one capture group but for the others any representative capture group works.)
> 2 votes

# Answer
## PERL, ~~116~~114 bytes

```
#!/usr/bin/perl -p
y/()/XY/;s/^(.+)>X(.+)>\1Y$/A/;s/(X.+>)X(.+)>(.+YY)>X\1\2Y>\1\3$/B/;s/X!(.+)>!(.+)Y>X\2>\1Y/C/

```

This comes with a shebang line, so is suitable for a standalone executable script. If you are willing to execute it as `perl -p scriptfilename`, the shebang line can be dropped, or to execute as `perl scriptfilename`, the shebang line can be replaced with a final `;print`

The behaviour for the "not an axiom instance" case is to print the input with parentheses replaced by X and Y, respectively. This certainly counts as "do something else" because this output is guaranteed to be different from A, B, C (e.g., it is guaranteed to contain a lowercase letter)
> 1 votes

---
Tags: code-golf, decision-problem, parsing, classification, logic
---


title: Generate all polyiamonds

text:
# Question
Title: Generate all polyiamonds
A polyiamond of size \\$n\\$ is a contiguous shape formed by joining \\$n\\$ equilateral triangles side by side.

Your output should consist of two distinct characters, plus whitespace as necessary (▲ and ▼ work great!). Trailing whitespace is acceptable. You may use any other characters - but you may count ▲▼ as 1 byte each regardless of code page. If you use other characters, you must indicate which character corresponds to the up-facing triangle and which to the down-facing triangle.

You may not output duplicates - rotations and reflections of the same polyiamond are considered the same.

n=1:

n=2: `▲▼`

Note that

```
▼
▲

```

is not a valid polyiamond - which is why the distinct characters are necessary!

n=3

```
▲▼▲

```

n=4

```
 ▲
▲▼▲

▲▼▲▼

▲▼▲
▼

```

### Challenge

* You may either take no input and output polyiamonds indefinitely or take a number \\$n\\$ as input and output all distinct polyiamonds of size \\$n\\$.
* Standard rules apply. The shortest code wins.

# Answer
> 4 votes
# Ruby, 277 bytes

```
f=->p=[[2]],s=1{w=45;q=[]
p.map{|a|t=(?.*~-w+$/)*s;a.map{|k|t[k]="AV"[k%2]};$><<t
(s*3).times{|i|a.index(d=[-1,1,w*~0**e=a[i/3]][i%3]+e)||(c=a+[d];r=[]
12.times{|j|c=c.map!{|k|j%2<1?k%w*2+~k:k/w+k%w*w-(k/w+k%w)/2*~-w}.sort!.map{|m|m-c[0]/2*2+20}
r<<c*1}
q<<r.min)}}
f[q&q,s+1]}

```

Try it online!

First golfed version. Runs indefinitely

# Ruby, 316 bytes

```
f=->n,p=[[2]],s=1{w=n*4+1
p.map{|a|t=(?.*~-w+$/)*s;a.map{|k|t[k]="AV"[k%2]};puts t,$/}
s<n&&(q=[]
p.map{|a|(s*3).times{|i|d=[-1,1,w*~0**e=a[i/3]][i%3]+e
a.index(d)||(c=a+[d];r=[]
12.times{|j|c=c.map!{|k|j%2<1?k%w+~(k/w)*w:(k/w+k%w*w)-(k/w+k%w)/2*~-w}.sort!.map{|m|m-(c[0]&-2)+n*2};r<<c*1}
q<<r.min)}}
f[n,q&q,s+1])
}

```

Try it online!

This is a first working version, drawing heavily on my answer to Sticky polyhexes

It's a function, taking the max size as input. Letting the code run indefinitely would probably be shorter.

**Explanation**

The code is a function taking one required and 2 optional inputs as follows:

* `n` max size of polyiamond
* `p` an array of polyiamonds
* `s` the size of the polyiamonds in the array.

If `p` and `s` are not given it is assumed that `s=1` and p contains the polyiamond `[2]` as a seed.

The board is `w` characters wide in the `x` direction and for calculation purposes is infinite in the `y` direction. Polyiamonds are represented as arrays of integers, one per triangle, of the form `d=x+wy`. It's important that `w` be odd, since this means that the oddness or evenness of `d` will determine whether upward pointing `A` or downward pointing `V` will be displayed. Therefore `w` is chosen as `n*4+1`.

The first task is to display the polyiamonds fed to the function as arguments. It is assumed that up to `s` lines may be needed to display these. This version uses `.` as a background, so the number of lines can be conveniently used to count the number of triangles in the polyiamond if this is not obvious.

If `s<n` we have not finished so we need to generate the list of polyiamonds of one size greater. To do this we start an empty array and run through all polyiamonds `a` in the input `p`. We take each triangle `e` in `a` and generate new triangles at `e+1`,`e-1` and `e+/-w`. To determine the correct sign for the last of these, -1 (represented as `~0` due to Ruby priority rules) is raised to the power `e`. If the new triangle is already in `a` it is an overlap and can be rejected. If it is not in `a` we have increased the size of the polyiamond, so we form a new polyiamond `c`.

We apply 12 symmetry operations to `c` (see below) forming an array `r` and add the lexically lowest one to `q`. Once the process is finished for all polyiamonds in `p` we find the intersection `q&q` of `q` with itself to eliminate duplicates and then call `f` again with the new list of polyiamonds of size `s+1`.

**Symmetry**

The most challenging part was working out the symmetry operations. These are actually done at 45 degrees to my answer to the sticky polyhexes question above. The triangle grid can be considered as two interpenetrating hex grids, one of all upward pointing triangles and the other of all downward pointing triangles, so it's similar but different.

All 12 symmetries can be generated by alternating two reflections. The first (parallel to a triangle edge) is a negation of the `y` axis. But rather than a change of sign, a bitflip of the y coordinate is employed. This changes the oddness/evennness of all triangles, causing the symbol to flip at the same time.

`k` = `k%w+~(k/w)*w`

The second (perpendicular to a triangle edge)is a transposition of the x and y axes. However a skew correction term is required, since opposite corners of a diamond `VA` are 2 units across in the `x` direction and 1 unit down in the `y` direction. Therefore the half the manhattan distance from the origin `x+y/2` is calculated and coordinates are adjusted by `-w-1` times this, causing a skew in a northeasterly direction.

`k` = `(k/w+k%w*w)-(k/w+k%w)/2*~-w`

Overall this looks like this:

```
  start pattern        flip vertical    flip diagonal  skew correction
  012 AVA                543 AVA        50 AV          501 AVA
  543 VAV     ----->     012 VAV   -->  41 VA   -->    432 VAV
                                        32 AV

```

---
Tags: code-golf, ascii-art, polyomino
---


title: Golfing Expressions

text:
# Question
Title: Golfing Expressions
We can write mathematical expressions using the standard math operators `(`,`)`,`+`,`*`,`/`,`-` available pretty much universally. We allow the symbols `a`, `b`, `c`, `d` and integers (e.g. `1`, `45`, etc.) but will restrict to just these four symbols. (Bonus points if you can handle more.) The goal is to take an expression as input and output a shorter expression that is mathematically equivalent to the input.

Edit: implicit multiplication such as `2a` is not valid. It should be `2*a`.

\[To make this a bit easier, we will only ever divide by integers, and never the symbols. In other words, an expression is a polynomial in 4 variables with rational coefficients.\]

# Examples

```
input  1: 1+1/2  (5 characters)
output 1: 3/2    (3 characters)

input  2: a*(1-b)*(1+b)  (13 characters)
output 2: a-a*b*b        (7 characters)

input  3: a*b*2/7-a*b*b/7  (15 characters)
output 3: a*b*(2-b)/7      (11 characters)

input  4: b*c*c+2*a*c*d-2*a*c-2*b*c-c*c-2*a*d-2*c*d+4*c+2*d  (49 characters)
output 4: c*(b*c-2*a-2*b-c+4)+2*d*(1-a)*(1-c)                (35 characters)

input  5: a*c+b*c+a*d+b*d+3*a+3*b+c+d+4  (29 characters)
output 5: (1+a+b)*(3+c+d)+1              (17 characters)

```

# Scoring

Shortest (valid) output wins. As a result, whoever has the shortest *total* (valid) output from the 20 randomly generated expressions is the winner. I will also verify that the winning solution actually works by creating 20 more, similar expressions and testing those.

There is a shortest solution in each case, so if multiple people come up with a solution that finds the shortest answer for every input, and not just the ones below, whoever got it first wins.

# "Random" Inputs

```
(2*a*a*a-2*a*a*d+2*b*d*d+d*d*d-2*a*a+2*a*b-b*c-a*d+b*d+a+c)/2
(-d*d*d+2*c+d)/2
-b*c*c-2*a*c*d+2*a*c+2*b*c+2*a*d
2*a*a*c+2*a*c*d-2*c*d*d-2*b*b+2*a*c+2*b*c-2*c*d-2*d*d-2*a-b+2*c+d+1
-b*c*c-2*a*c*d+c*c+2*c*d+2*a+b
(-2*a*a*b*b+a*a*a*c+b*c*c*d+2*c*d*d*d-d*d*d-2*a*c+2*b*c+2*c*c+d*d)/3
(-2*a*a+b*c-2*b*d+2*a-2*b-1)/2
(b*b*c+a*c*c-2*b*d*d-c*d*d-a*a-2*a*b-b*b-a*c+c*c+2*a*d-b*d-2*d*d)/4
(a*a+b*d-c*d-c-2*d)/2
-a*a+2*a*b+2*b*b+2*a*c-a*d-2
-b*c*c-2*a*c*d+2*a+b
(a*b*b+2*a*b*c-b*c*c-a*d*d-b*b+a*c+b*c-c*c+2*a*d+a+2*b+d)/4
(-8*a*b*c-4*a*a*d+4*a*a+8*a*b+4*a*c+4*b*c+4*a*d-8*a-4*b+3)/3
(-2*a*a*a*a+c*c*c*c-a*b*c*d+2*b*b*c*d-a*c*c*d-2*c*c*c*d+a*a-2*b*b+2*a*c+a*d)/3
b*c*c+2*a*c*d-2*a*c-2*b*c-c*c-2*a*d-2*c*d+4*c+2*d
(-2*a*b*b*b+c*c*c*c-2*a*a)/3

```

# Answer
# Python 3.10

```
import copy, collections
import math, itertools

REDUCE_COUNT = itertools.count(1)

def parse_expr(s, paren=False):
    expr_vars, expr_val, expr_demoninator, expr_groups = [], None, 1, []
    expr_container, flag = [], True
    while s and (not paren or s[0] != ')'):
        if s[0].isdigit():
            expr_val = (expr_val or 1) * int(s[0])
        elif s[0].isalpha():
            expr_vars.append(s[0])
        elif s[0] == '*':
            pass
        elif s[0] == '/':
            expr_demoninator *= int(s[1])
            s, flag = s[2:], False
        elif s[0] in {'+', '-'}:
            if expr_val is not None or expr_vars or expr_groups:
                expr_container.append({'type':'expr', 'coefficient':expr_val or 1, 'denominator':expr_demoninator, 'vars':sorted(expr_vars, key=lambda x:(isinstance(x, (dict, list)), str(x))), 'groups':sorted(expr_groups, key=str)})
            expr_vars, expr_val, expr_demoninator, expr_groups = [], 1 if s[0] == '+' else -1, 1, []
        elif s[0] == '(':
            container, s = parse_expr(s[1:], True)
            expr_groups.append(container)
        elif s[0] == ' ':
            pass
        if flag:
            s = s[1:]
        flag = True
    if expr_val is not None or expr_vars or expr_groups:
        expr_container.append({'type':'expr', 'coefficient':expr_val or 1, 'denominator':expr_demoninator, 'vars':sorted(expr_vars, key=lambda x:(isinstance(x, (dict, list)), str(x))), 'groups':sorted(expr_groups, key=str)})
    return {'type':'container', 'exprs':expr_container}, s

def expand_expr(expr):
    def update_expr_vars(expr, expr_vars):
        expr['coefficient'], expr['vars'], expr['denominator'] = expr['coefficient']*expr_vars['coefficient'], sorted(expr['vars']+expr_vars['vars']), expr['denominator']*expr_vars['denominator']
        return expr

    def to_expr_var(expr):
        return {'coefficient':expr['coefficient'], 'vars':expr['vars'], 'denominator':expr['denominator']}

    def distribute(expr, expr_vars={'coefficient':1, 'vars':[], 'denominator':1}):
        if expr['type'] == 'container':
            for i in expr['exprs']:
                yield from distribute(i, expr_vars)
        else:
            new_expr = update_expr_vars(eval(str(expr)), expr_vars)
            if not new_expr['groups']:
                yield new_expr
            else:
                all_vars = [to_expr_var(new_expr)]
                for i in new_expr['groups']:
                    all_vars = [x for y in all_vars for x in distribute(i, y)]
                yield from all_vars

    return {'type':'container', 'exprs':[*distribute(expr)]}

def reduce_terms(expr):
    lcm, d = math.lcm(*[i['denominator'] for i in expr['exprs']]), collections.defaultdict(int)
    for i in expr['exprs']:
        d[str([i['vars'], i['groups'], i.get('reduce', 0)])] += i['coefficient']*(lcm/i['denominator'])

    return {'type':'container', 'exprs':[{'type':'expr', 'coefficient':int(b), 'denominator':lcm, 'vars':eval(a)[0], 'groups':eval(a)[1]} for a, b in d.items() if b]}

def render_expr(expr, d=0):
    if expr['type'] == 'container':
        r_s = ''
        for i in expr['exprs']:
            if (v:=render_expr(i, 1)):
                if v[0] == '-' and r_s and r_s[-1] == '+':
                    r_s = r_s[:-1]+v+'+'
                else:
                    r_s += v + '+'
        if r_s and r_s[-1] == '+':
            r_s = r_s[:-1]
        return '' if not r_s else '('*d + r_s + ')'*d

    if not any([expr['vars'], expr['groups']]):
        return str(expr['coefficient'])+('/'+str(expr['denominator']) if expr['denominator'] != 1 else '')

    result = ('' if abs(expr['coefficient']) == 1 else str(expr['coefficient'])) + ('-' if expr['coefficient'] == -1 else '')
    if expr['vars']:
        result += ('*'*(bool(result) and result[-1] != '-'))+'*'.join(expr['vars'])
    if expr['groups']:
        result += ('*'*(bool(result) and result[-1] != '-'))+'*'.join(render_expr(i, 1) for i in expr['groups'])
    if expr['denominator'] != 1:
        result += '/'+str(expr['denominator'])

    return result

def factor_combos(all_combos, c = []):
    if c: yield c
    if all_combos:
        for i in all_combos[0]:
            yield from factor_combos(all_combos[1:], c+[i])

        yield from factor_combos(all_combos[1:])

def expr_factors(expr):
    assert expr['type'] == 'expr'
    yield from factor_combos([
        [{'type':'coefficient', 'v':i} for i in range(2, abs(expr['coefficient'])+1) if not expr['coefficient']%i],
        [{'type':'vars', 'v':[*j]} for x in range(len(expr['vars'])+1) for j in itertools.combinations(expr['vars'], x)],
        [{'type':'groups', 'v':[*j]} for x in range(len(expr['groups'])+1) for j in itertools.combinations(expr['groups'], x)]
        ])

def factor_match(expr, factor):
    new_expr = eval(str(expr))
    if 'coefficient' in factor:
        if expr['coefficient']%factor['coefficient']:
            return False
        new_expr['coefficient'] = int(new_expr['coefficient']/factor['coefficient'])
    if 'vars' in factor:
        c1, c2 = collections.Counter(expr['vars']), collections.Counter(factor['vars'])
        for a, b in c2.items():
            if a not in c1 or b > c1[a]:
                return False
            c1[a] -= b
        new_expr['vars'] = sorted([x for a, b in c1.items() for x in ([a]*b)])

    if 'groups' in factor:
        c1, c2 = collections.Counter(map(str, expr['groups'])), collections.Counter(map(str, factor['groups']))
        for a, b in c2.items():
            if a not in c1 or b > c1[a]:
                return False
            c1[a] -= b

        new_expr['groups'] = sorted([eval(x) for a, b in c1.items() for x in ([a]*b)], key=str)

    return new_expr

def group_common_factor(exprs, factor):
    factor = {i['type']:i['v'] for i in factor}
    matched, non_matched = [], []
    for expr in exprs:
        if (m:=factor_match(expr, factor)):
            matched.append(m)
        else:
            non_matched.append(expr)

    if len(matched) < 2:
        return [], non_matched

    old_denominator = matched[0]['denominator']
    for i in matched:
        i['denominator'] = 1

    new_expr_var = {'type':'expr', 'coefficient':factor.get('coefficient', 1), 'denominator':old_denominator, 'vars':sorted(factor.get('vars', []), key=str), 'groups': sorted(factor.get('groups', [])+[{'type':'container', 'exprs':matched}], key=str)}
    return new_expr_var, non_matched

def factor_ints(d, c = []):
    def gen_num(n, denom):
        return {'type':'expr', 'coefficient':n, 'denominator':denom, 'vars':[], 'groups':[], 'reduce':next(REDUCE_COUNT)}

    if not d:
        yield c

    else:
        yield from factor_ints(d[1:], c+[d[0]])
        if not any([d[0]['vars'], d[0]['groups']]):
            for i in range(1, d[0]['coefficient']//2):
                yield from factor_ints(d[1:], c+[gen_num(i, d[0]['denominator']), gen_num(d[0]['coefficient'] - i, d[0]['denominator'])])

def base_factor_combos(d, c = []):
    if len(c) > 1 and len(c) < len(d):
        yield sorted(c)
    for i in d:
        if i not in c:
            yield from base_factor_combos(d, c+[i])

def full_base_factors(d):
    return list(map(eval, set(map(str, base_factor_combos(d)))))

def produce_factor_combinations(exprs, c = [], f = 0):
    yield {'type':'container', 'exprs':sorted(c+exprs, key=str)}
    if exprs:
        seen_factors = []
        for i in exprs:
            for _factor_group in expr_factors(i):
                if (factor_group:=[*filter(lambda x:x['v'], _factor_group)]) and factor_group not in seen_factors:
                    seen_factors.append(factor_group)
                    matched, non_matched = group_common_factor(exprs, factor_group)
                    if matched:
                        yield from produce_factor_combinations(non_matched, c = c+[matched], f=f)
                        if not f:
                            for base_factor in full_base_factors([*range(len(non_matched))]):
                                if len(base_factor) > 2:
                                    yield from produce_factor_combinations([a for j, a in enumerate(non_matched) if j not in base_factor], c = c+[matched]+[{'type':'expr', 'coefficient':1, 'denominator':matched['denominator'], 'vars':[], 'groups': [{'type':'container', 'exprs':[non_matched[j] for j in base_factor]}], 'base_factor':1}], f = 1)

def run_transformation(expr, len_cache):
    queue, seen = collections.deque([(0, expr)]), []
    while queue:
        level, expr = queue.popleft()
        reduced = reduce_terms(expr)
        s = render_expr(reduced)
        len_cache[len(s)]= s
        if s not in seen and (not len_cache or (len(s) < min(len_cache) or level < 2)):
            seen.append(s)
            for i in produce_factor_combinations(reduced['exprs']):
                queue.append((level+1, i))

def main(expr):
    full_len_cache = {}
    parse_result, _ = parse_expr(expr)
    expanded = expand_expr(parse_result)
    for i, _expr in enumerate(factor_ints(expanded['exprs'])):
        len_cache = {}
        run_transformation({'type': 'container', 'exprs':_expr}, len_cache)
        full_len_cache.update(len_cache)

    return full_len_cache[min(full_len_cache)]

if __name__ == '__main__':
    print(main('1+1/2'))
    print(main('a*(1-b)*(1+b)'))
    print(main('a*b*2/7-a*b*b/7'))
    print(main('a*c+b*c+a*d+b*d+3*a+3*b+c+d+4'))
    print(main('b*c*c+2*a*c*d-2*a*c-2*b*c-c*c-2*a*d-2*c*d+4*c+2*d'))

```

This solution takes in an expression, parses it, and then repeats a process of grouping on possible factors and then combining like terms. While the code is somewhat verbose, the overall idea is very simple. It is somewhat slow on large inputs, and could be optimized further.
> 9 votes

---
Tags: string, parsing, polynomials, test-battery, expression-building
---


title: Arrange a Haft-Sin table

text:
# Question
Title: Arrange a Haft-Sin table
It's Nowruz and you want to set up a Haft-Sin table by words. This means finding seven words that start with letter *s*.

# The Challenge

Write a program which its input is a list of words separated by space, and output at most first 7 words which starts by letter *s*. If the *s* is before letter *h* it doesn't count because it would not pronounce /s/.

### Input

An arbitrary length string containing words separated by space. Words must not contain anything other than letters (uppercase or lowercase) and numbers and `_`.

These inputs are valid:

```
hello Puzzle code_golf 12
Start say_hello separating_by_space_is_right
I am a valid word list

```

And these inputs are invalid:

```
code-golf, #invalid_word, separating_by_comma_is_wrong
I'm an invalid word list

```

### Output

The first 7 words which starts by letter *S-s* and not followed by letter *H-h*, in every acceptable way (comma separated, space separated, new-line etc) and in any order.

* If two words are duplicate don't count them twice. Every single word is count once.
* If the input contains less that 7 word starting with *s* output nothing. Don't output the words.
* The output must contain the exact word which is in the input. So if the input contains `SuPER`, output should be `SuPER` and not `SUPER` or `super` or any other form of lower and upper case.
* Words pronunciation matter. The word `Speed` and `SPEED` both count the same. You may want to lowercase all the input and unique the words and then check for words.

### test-cases

input:

```
speed speed new car book seven sad sum power fun super sister silver silly start

```

output:

```
speed seven sad sum super sister silver

```

input:

```
speed SpEEd new book seven sad sum power fun super sister silver silly start

```

output:

```
speed seven sad sum super sister silver

```

input:

```
sheep speed new car book seven sad sum power fun super sister silver silly start

```

output:

```
speed seven sad sum super sister silver

```

input:

```
first second third

```

output:

## Edited

This was my first question and I missed many special cases. I try to clarify them.

# Answer
> 2 votes
# Jelly, 24 bytes

Assuming that we must handle uppercase `S` and `H` too and that we must/may return the leftmost distinct "s-words"

```
ḣ2ŒliⱮ⁼Ø.
ḲQçƇ⁾hsḣJf7ḢƊ$

```

A monadic Link that accepts a list of characters and yields a list of the words.

**Try it online!**

### How?

```
ḣ2ŒliⱮ⁼Ø. - Helper Link, valid word?: list of characters, Word; identifiers ("hs")
ḣ2        - head Word to index two   - e.g. "Child" -> "Ch"
  Œl      - lower-case -> X                     -> X = "ch"
     Ɱ    - map across C in identifiers with:
    i     -   first (1-indexed) index of C in X     -> [2,0]
                                                    ('h' at index 2, no 's' exists)
       Ø. - [0,1]
      ⁼   - equal?

ḲQçƇ⁾hsḣJf7ḢƊ$ - Link get s-words: list of characters, T
Ḳ              - split T at space characters -> Words
 Q             - deduplicate
    ⁾hs        - set the right argument to "hs"
   Ƈ           - filter keep those Words for which:
  ç            -   call the helper Link as a dyad - f(Word, "hs")
             $ - last two links as a monad - f(ValidWords):
            Ɗ  -   last three links as a monad - g(ValidWords):
        J      -     range of length -> [1,2,...,number of valid words]
          7    -     seven
         f     -     filter-keep -> [7] or [] if less than seven valid words
           Ḣ   -     head        -> 7   or 0
       ḣ       -   head of ValidWords to that index

```

# Answer
> 5 votes
# Vyxal, 28 bytes

```
⌈'⇩ḣh\h≠$h\s=∧;:ɽ:vḟUİ₅6>7*Ẏ

```

Try it Online! or Try some testcases! Mis-deduplication should be fixed now.

```
⌈'⇩ḣh\h≠$h\s=∧;:ɽ:vḟUİ₅6>7*Ẏ
⌈'             ;                 Filter input, split on spaces, by:
  ⇩ḣ                                 Push (input lowercased)([0], [1:])
    h\h≠                             Second character (input[1:][0]) isn't `h`
        $h\s=∧                       and first character isn `s`

                :ɽ               Duplicate, lowercase each
                  :vḟ            Find first occurrences of each of ^ in ^
                     U           Uniquify ^
                      İ          Index ^ into filtered list, resulting
                                 in the properly deduplicated list

                       ₅6>       1 if len(^) is 7 or more, otherwise 0
                          7*Ẏ    Multiply by 7 and slice [0:that]

```

# Answer
> 4 votes
# , ~~57~~ ~~61~~ ~~58~~ 79 bytes

*Edit: -2 bytes thanks to "regex stealing" by pajonk*

*Edit2: +21 bytes to remove case-sensitive duplicates, while returning the originally cased input*

```
q=(o=grep("^s(?!h)",scan(,""),T,T,T))[!duplicated(tolower(o))];if(q[7]>F)q[1:7]

```

Try it online!

Outputs the first 7 unique words starting with 's' or 'S' but not 'sh' or 'Sh', if there are at least 7.
Otherwise errors without outputting anything.

---

# , ~~59~~ ~~63~~ ~~61~~ 82 bytes

```
(q=(o=grep("^s(?!h)",scan(,""),T,T,T))[!duplicated(tolower(o))])[1:7][length(q)>6]

```

Try it online!

As above, but exits quietly without erroring if there are less than 7 valid words.

# Answer
> 3 votes
# JavaScript (ES6),  ~~62~~  61 bytes

*Saved 1 byte thanks to @l4m2*

```
s=>(a=[...new Set(s.match(/\bs(?!h)\w*/g))]).slice(a[6]||7,7)

```

Try it online!

# Answer
> 3 votes
# Retina 0.8.2, 47 bytes

```
+msi`(^(.+)$.+)^\2$
$1
Gi`^s(?!h)
1!`.+(¶.+){6}

```

Try it online! Explanation:

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

```

Delete case-insensitive duplicates.

```
Gi`^s(?!h)

```

Keep only words beginning with `s` but not `sh`.

```
1!`.+(¶.+){6}

```

Select the first seven words.

# Answer
> 2 votes
# 05AB1E, 27 (or 22?) bytes

```
#ʒlć'sQsн'hÊ*}DlDÙkèDg7@7*£

```

Assumes differently cased words (e.g. `speed`/`SPEED`/`sPeEd`) are all the same for the uniquify. Otherwise this could have been 22 bytes by replacing the `DlDÙkè` with `Ù`.

Try it online or verify some more test cases.

**Explanation:**

```
#          # Split the (implicit) input-string by spaces
 ʒ         # Filter this list of words by:
  l        #  Convert it to lowercase
   ć       #  Extract head; pop remainder-string and first char separated
    'sQ   '#  Check if this head is an "s"
   s       #  Swap so the remainder-string is at the top
    н      #  Pop and push its first character
     'hÊ  '#  Check that it's NOT equal to a "h"
   *       #  Check that both were truthy
 }D        # After the filter: duplicate the resulting list of words
   l       # Convert each to lowercase
    D      # Duplicate it again
     Ù     # Uniquify the top copy
      k    # Get all its indices in the lowercase list
       è   # Use it to index in the regular case-insensitive list
   D       # Duplicate the list
    g      # Pop and push its length
     7@    # Check if it's >=7
       7*  # Multiply that 0/1 by 7 (either 0 or 7)
         £ # Leave that many leading words from the list
           # (after which the resulting list is output implicitly)

```

# Answer
> 2 votes
# Perl 5, 60 bytes

```
my%s;$_=(@r=grep!$s{lc$_}++,/\bs(?!h)\w*/gi)<7?"":"@r[0..6]"

```

Try it online!

# Answer
> 1 votes
# Python 3, ~~111~~ ~~102~~ 103 bytes

I am pretty sure this isn't a perfect solution, as my regex skills are far from perfect and this seems an unnecessarily long way to check for "any word character that is not h or H", but it works. Takes a list of the words, and returns a set of the seven words, or nothing if it cannot find seven words.

```
import re
def f(x):
 r=set()
 for i in x:
  if re.match("[Ss](?![Hh])",i):r|={i}
  if len(r)>6:return r

```

Edit -9 bytes: realized that it didn't have to check if the words only contained alphanumerics

Edit +1 bytes: @a stone arachnid pointed out my regex failed for input of `s`

Try it online!

# Answer
> 1 votes
# PowerShell Core, ~~78~~ 75 bytes

```
($r=-split$args-match'^s[^h]*$'|?{!($_-in$u);$u+=,$_})[0..6]*($r.count-ge7)

```

Try it online!

-3 bytes thanks to *mazzy*!

# Answer
> 1 votes
# PowerShell Core for Windows, 68 bytes

*Thanks @Julian for the inspiration*

```
($r=$args|sls '\bs(?!h)\S*'-a|% m*|% v*e|sort -u -t 7)*!($r.count-7)

```

Try it online!

The alias `sort` is not defined for Linux PowerShell and TIO. Linux requires `sort-object`.

Less golfed:

```
$result = $args|select-string '\bs(?!h)\S*' -allMatches|% matches|% value|sort -unique -top 7
$result*($result.count-eq7)

```

# Answer
> 0 votes
# Charcoal, 38 bytes

```
ＷＳ⊞υι≔Φυ∧›⁼↧§ι⁰s⁼↧§ι¹h⁼κ⌕↧υ↧ιυ…υ∧‹⁶Ｌυ⁷

```

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

```
ＷＳ⊞υι

```

Input the list of words.

```
≔Φυ∧›⁼↧§ι⁰s⁼↧§ι¹h⁼κ⌕↧υ↧ιυ

```

Case-insensitively filter out all words that don't start with an `s` or start with `sh` or are duplicate.

```
…υ∧‹⁶Ｌυ⁷

```

Output the first seven remaining words if there are more than six of them.

# Answer
> 0 votes
# Japt, 21 bytes

I think this is right; it's been a *long* day so I'm not at all sure!

```
¸fÈÎos «XÅÎohÃòk mÎ¯7

```

Try it

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

```
s=>(a=s.match(/(\bs(?!h)\w*\b)(?<!\b\1 .*)/gi)).slice(a[6]||7,7)

```

Try it online!

Fixed Arnauld's uppercase problem with 3 bytes

# Answer
> 0 votes
# PHP, ~~134~~ 131 bytes

```
$a=explode(" ",$argn);foreach($a as$v){$l=strtolower($v);if($l[0]=="s"&&$l[1]<>"h"){$b[$l]="$v ";if(count($b)==7){echo join($b);}}}

```

Try it online!

Explanation: Used associative array key to prevent dups instead of in\_array function.

----- Previous answer -----

```
$a=explode(" ",$argn);foreach($a as$v){if($v[0]=="s"&&$v[1]<>"h"&&!in_array($v,$b)&&$i<7){$b[]=$v;$i++;}}if($i==7){echo join($b," ");}

```

Try it online!

Explanation: Straightforward conversion of input to array, step through array testing each word against the rules, if a word passes the test add it to second array, and only print second array if 7 words pass the test.

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


# Question
Title: Inject arbitrary code into a compiler (robbers)
**This is the robbers' challenge. To post a cop, go here.**

In this challenge, cops will invent a (likely simple) programming language, and write an interpreter, transpiler, or compiler that allows you to run it. Robbers will write a program in this language that manages to inject arbitrary code into the interpreter, transpiler, or compiler.

## Cops

Cops should design a language. This language should be "pure"; its programs can take input and/or produce output, but cannot affect files, make network requests, behave non-deterministically (based on something like randomness or the system time), or otherwise impact or be impacted by the outside world (within reason).

Cops must then implement this language, with one of:

* **An interpreter:** This will take the code and input as arguments/input, and produce the programs's output as output.
* **A transpiler:** This will take the code and input, and produce code in some other language which does the same task. When run using that language's interpreter/compiler with input, the correct output is produced.
* **A compiler:** Similar to a transpiler, but with machine code instead of another language.

There must be an intended "crack", or way to inject arbitrary code.

## Robbers

Robbers should find a way to do one of the following:

* Write a program that, when interpreted, transpiled, or compiled, can run arbitrary code as the interpreter/transpiler/compiler (e.g., if written in Python, you could run arbitrary Python, manipulate files, and so on)
* Write a program that, when transpiled or compiled, injects arbitrary code into the resulting program/machine code (e.g., if your transpiler converts the language to Node.js, you could inject arbitrary JS into the transpiler output)

## Robber Posts

Robbers should include code which can be given to the cop, which allows injecting arbitrary code. For example:

> # Cracks Print1Lang
>
> ```
>
> eval("...") # arbitrary Python, with 1s replaced with \x31
> ```
>
> This exploits the fact that `.` in regexes does not match newlines.

This exploit should allow injecting **any** code, in some language or situation that allows performing arbitrary computations and interacting with the computer's files, running shell commands, system calls, or anything like that. Simply printing a nondeterministic value does not count, as it does not give you unrestricted access to the environment the code or transpilation/compilation output is being run or transpiled/compiled in.

For an interpreter, this is likely going to be running code in the language the interpreter is written in. For a transpiler or compiler, the vulnerability can occur at either compile time or run time, and for the latter, the vulnerability would most likely consist of being able to inject arbitrary code or machine code into the compiled code.

## Other

All the boring stuff. Nothing malicious, no crypto stuff.

Winner for cops is the user with the most safe cops, winner for robbers is the user who cracks the most cops.

# Answer
# Cracks Javastack

```
0);
<!--　place　your　code　here
console.log(`42`)
//
```
> 5 votes

# Answer
# Cracks Vyxal 2.10

```
`f"{print(1)}"`∆i

```

Prints `1` then errors. Sadly does not work online, but does offline. Exploits the fact that `∆i` uses sympy, similar to this. Injected code is everything between the `{` and `}`.
> 4 votes

# Answer
# Cracks Exceptionally

```
{exec
\"wrap"
}FUNCS
{"print(5)"
\0

```

Your code can go where the `print(5)` is.

So, all variables are accessible by the program, so we can load `exec` into the register, but we can't easily execute it. We'd have to load it into `FUNCS`, but `FUNCS` needs to be something that can be indexed into...

We can make it an array! By using the builtin `\"wrap"` on `exec` we can load that into `FUNCS` and execute it with `\0`. The line before that stores our code to the register so it gets run.
> 3 votes

# Answer
# Cracks Jyxal

```
@=0,this["FUNC_"+arity]={},eval("console.log(\"pwned\")"),FUNC_x|;

```

This creates a function with the name...well, everything between `@` and `|;`. Normally, if the function name was something reasonable and the code looked like `@xyz|;`, the transpiled output would look like this:

```
var arity = 'xyz';FUNC_xyz = (stack) => {return pop(stack)}; this['FUNC_' + arity.split(':')[0]].arity = arity;

```

So, with my crack, it looks like this:

```
var arity = '=0,this["FUNC_"+arity]={},eval("console.log(\"pwned\")"),FUNC_x';FUNC_=0,this["FUNC_"+arity]={},eval("console.log(\"pwned\")"),FUNC_x = (stack) => {return pop(stack)}; this['FUNC_' + arity.split(':')[0]].arity = arity;

```

As you can see, it sets `FUNC_` to `0`, sets `this["FUNC_"+arity]` to `{}` (to avoid a syntax error later, you could also just use `//` at the end), and then `eval`s basically arbitrary code. You can't include some characters, but you can just use `\x` to insert them in the eval'd string.
> 2 votes

# Answer
# Cracks Exceptionally v0.2

```
<"\"?\")) or exit('GET ACE LOL')#"
```

Attempt This Online!

Yeet your code where the `exit('GET ACE LOL')` is. Will print some junk first.

This gets transpiled into:

```
(print("\")) ? (reg := program.FUNCS[")) or exit('GET ACE LOL')#"](reg))

```

Exceptionally doesn't escape backslashes in strings, so it parses it as two seperate statements combined by the `?` operator. However, the second `"` is escaped and the string won't end until reaching another `"`. We include some code to close the parentheses opened by the `print` and a comment at the end to throw away the rest, then whatever goes in the middle is arbitrary code.
> 1 votes

---
Tags: cops-and-robbers, interpreter, language-design, compiler
---


title: Help me prove the Four Color Theorem!

text:
# Question
Title: Help me prove the Four Color Theorem!
This is not just another challenge asking you to color random maps... In this challenge, you are asked to write a program that is **actually used** in the formal proof of the Four Color Theorem.

First I shall describe the challenge without any background or motivation, for the impatient.

A **chromogram** is a list made of the symbols `-` `[` `]0` `]1`, where the brackets are required to match. A **coloring** is just a list made of 1, 2 and 3's whose bitwise sum (i.e. XOR) is zero. A coloring is said to **fit** a chromogram if:

* They are of the same length.
* `-`'s in the chromogram corresponds to `1`'s in the coloring at the same positions.
* Brackets corresponds to `2`'s and `3`'s. For matching brackets, if they are `[ ]0` then they correspond to the same color, and different colors if they are `[ ]1`.

Some examples:

```
Chromogram      <-> Coloring
[ [ - ]1 - ]0 - <-> 2 3 1 2 1 2 1
[ [ - ]1 - ]0 - <-> 3 3 1 2 1 3 1
[ ]1 -          <-> 2 3 1
[ ]1 -          <-> 3 2 1

```

Given colorings \\$C\\$, a **compatible** coloring is one such that each of its chromograms fits with some \\$c\in C\\$ (different chromograms can fit different colorings). More formally, we define "\\$c'\\$ is compatible with \\$C\\$" as the logical proposition "for each chromogram \\$\gamma\\$ that fits \\$c'\\$, there exists \\$c\in C\\$ such that \\$\gamma\\$ fits \\$c\\$." We define a **suitable** coloring with the following rules:

* All colors in \\$C\\$ are suitable.
* For a suitable coloring, switching 1, 2 and 3's consistently produces another suitable coloring. E.g. `12321 -> 21312 or 32123 or 13231`, but not `11311` or `12331`. Formally, if \\$\rho\\$ is a permutation of \\$\\{1,2,3\\}\\$, then if \\$\langle c\_1, c\_2, \dots, c\_n \rangle\\$ is a suitable coloring, \\$\langle \rho c\_1, \rho c\_2, \dots, \rho c\_n \rangle\\$ is also one.
* For a set of suitable coloring \\$D\\$, all its compatible colorings are suitable. Note that if you put more suitable colorings into the set \\$D\\$, an originally compatible coloring will never cease to be compatible. So in your code, you can greedily add suitable colorings without worrying that you will "miss the chance" to apply this rule.
* All the suitable colorings are generated by the rules above.

As an example, take \\$C\\$ to have two colorings `1111, 2323`. You can use the second rule to claim that `2222` is suitable. Then `2233` is suitable using the third rule, because it fits two chromograms `[ ]0 [ ]0` and `[ [ ]1 ]1`, the first of which fits `2222`, and the second fits `2323`.

Now the challenge:

> **Challenge**. Input a set of coloring \\$C\\$, determine if all the colorings of the same length are suitable. This is .

A hint: A sequence of 1, 2 and 3's have the bitwise sum (XOR) zero if and only if the parity of each kind of number are the same, i.e. the numbers of occurrences of 1's, 2's and 3's are all odd or all even. But probably XOR'ing all of them is more golfy.

---

Now it's time for stories. The **Four Color Theorem** states that any planar map can be colored with four colors, so that the regions that meet at boundaries are colored differently. I'll try to briefly describe the proof of the Four Color Theorem, in steps.

1. First, if you create a tiny region at every corner (i.e. where three or more regions meet), you get a map where no more than three regions meet at a point, and if you can color these kind of maps, you can remove the added region and recover a coloring of the original map. These special maps are called **cubic**.
2. Now we reason by reductio ad absurdum. Consider the *smallest* cubic counterexample. Any map smaller than that will be 4-colorable.
3. Next, by a method of **discharging**, we compute a score for each region, ensuring that the average score is less than 6. This means that there must be at least one region with score less than 6. In this way we locate a "weak spot" of the putative counterexample, where we are going to attack.
4. We, by the aid of a program (not related to this challenge), prove that the neighborhood of the weak spots that we may find always falls in one of the 633 possibilities. This allows us to do a case-by-case analysis.
5. In each case, we remove some boundaries in the neighborhood of the weak spot, creating a smaller map. By hypothesis, this map is 4-colorable. We then try to recolor the original map based on the smaller map, only adjusting the colors in the neighborhood. This is not always possible. So we try to adjust the outer regions also. This is difficult because changing one regions's color may affect other regions. We now develop a more convenient tool.
6. Notice that if, instead of coloring the regions by colors \\$0,1,2,3\\$, we color the *boundaries* of the map, by computing the bitwise sum of the two regions on either side of the boundaries, we can color the boundaries with \\$1,2,3\\$. It can be proven that the original coloring can always be recovered from the boundary coloring. Now the situation is clearer. Note that exactly 3 boundaries meet at a corner, and they always have different colors. Suppose we want to change an boundary color from 2 to 3 (the boundary sticks out from the neighborhood we just considered, so it will be consistent with the colors in the neighborhood), the only hinderance is the edge colored 3 connected to it (there is only one such edge extending outwards, can you see why?). If we change that 3 into 2, a further edge colored 2 will protest! In this way, we can go on and on in a chain. And the key insight is that **the chain cannot intersect itself**, so it will always come back sticking into the neighborhood again.
7. So now, the boundaries colored 2/3 will form *arches* standing on the edge of the neighborhood we are considering. These arching structures are captured by our **chromograms**, and the colors of the boundaries sticking out of the neighborhood are represented by the **colorings** in our challenge. Now if you reread the challenge, you will understand that, given the recoloring that we have for the neighborhood, the challenge is to determine if every possible coloring for the outer map can be adjusted to match.

---

Phew! That was, alas, the briefest that I can manage without losing too much detail! You can see that our challenge is only concerned with the *last* step, and there are more potential challenges lurking about. But this I leave to those who are interested. You can consult this paper for a more detailed account. I hope this challenge can kindle some interest in the four color theorem and its proof.

---

Routine code-golf test cases:

```
T 123
T 1111,2323
F 1111,2332
T 11123,12113,12311
F 11123,12113,12131
T 111111,123132,123231,123312,123213,112323,121222,122122,122212
F 123132,123231,123312,123213,112323,121222,122122,122212
F 123231,123312,123213,112323,121222,122122,122212
F 111111,123312,123213,112323,121222,122122,122212
T 111111,123231,123213,112323,121222,122122,122212
F 111111,123231,123312,112323,121222,122122,122212
F 111111,123231,123312,123213,121222,122122,122212
F 111111,123231,123312,123213,112323,122122,122212
T 111111,123231,123312,123213,112323,121222,122212
F 111111,123231,123312,123213,112323,121222,122122
F 111111,123132,123312,123213,112323,121222,122122,122212
T 111111,123132,123231,123213,112323,121222,122122,122212
F 111111,123132,123231,123312,112323,121222,122122,122212
F 111111,123132,123231,123312,123213,121222,122122,122212
F 111111,123132,123231,123312,123213,112323,122122,122212
T 111111,123132,123231,123312,123213,112323,121222,122212
F 111111,123132,123231,123312,123213,112323,121222,122122

```

I hesitate to include larger test cases, because to do those in reasonable time, some algorithm other than the most naive one is needed. I don't want to complicate things too much, since they are already so complicated. Better algorithms can be found in the linked paper.

# Answer
# Python 3.8 (pre-release), 835 bytes

```
E=enumerate
G=len
def m(c,o):
 i=o;b=0
 for v in c[o:]:
  b+=(v==1)-(v>1)
  if b==0:break
  i+=1
 return i
f=lambda c,C:G(c)==G(C)and all(C[i]<2if V<1else V!=1or(h:=m(c,i))<G(C)and eval(f'1<C[i]{"  =!"[c[h]]}=C[h]>1')for i,V in E(c))
def N(l,L):
 if L<2:return[[V]for V in l]
 r=[]
 for V in l:
  for g in N(l,L-1):r+=[[V,*g]]
 return r
def A(s,B=[]):
 W=[C for C in N([1,2,3],G(s[0]))if eval('^'.join(str(Q)for Q in C))==0]
 S=s+[C for C in W if all(any(f(c,T)for T in s)for c in N([0,1,2,3],G(C))if all(V!=1or m(c,i)<G(c)for i,V in E(c))and c.count(1)==c.count(2)+c.count(3)and f(c,C))]
 for C in[*S]:
  for p in[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]:S+=[[p[o-1]for o in C]]
 S=[''.join(str(o)for o in C)for C in S];S=[*{*S}];S=[[int(Y)for Y in C] for C in S];D=[G(B),G(W)]
 if G(S)in D:return D.index(G(S))
 return A(S,s)

```

Try it online!

Thanks @Steffan for -11 bytes.

Not exactly the golfiest version that could be produced. I will continue to golf this code.

Not very efficient. Takes at least ~~15~~ 3 minutes to complete all 22 testcases. Thus, don't expect the TIO link to work. You can, however, run it locally if Python is on your machine. The TIO link includes a test suite that compares the outputs against the expected outputs.

## Explanation

Just implements the question's spec literally. Defines a helper function `f` that checks if a chromogram fits a coloring. In the main function `A`, starts off with the inputted set plus set of compatible colorings (implemented based on the question's definition, making sure to check that lists that are purportedly chromograms and colorings are actually chromograms and colorings), then adds the permutations, removes duplicates, then:

* if every coloring of the same length as each coloring of the inputted set is in the set generated according to the above, then return 1.
* if no new colorings were added (i.e. length of generated set is the same as that of the previous set \[c.f. below\]), return 0. (once we add all the colorings of the same length, the function returns 1 before calling itself, thus avoiding returning 0)
* otherwise, recall the function with the new set and passing the previous set (which starts empty).

Ungolfed version (2778 bytes):

def matching_bracket(c,o):
 index = opening
 bracket_level = 0
 for value in chromogram[opening:]:
  if value == 1:
   bracket_level += 1
  if value > 1:
   bracket_level -= 1
  if bracket_level == 0:
   break
  index += 1
 return index

def valid_brackets(chromogram, coloring, opening):
 index = matching_bracket(chromogram, opening)
 try:
  if chromogram[index] == 2:
   return 1 < coloring[opening] == coloring[index]
  return 1 < coloring[opening] != coloring[index] > 1
 except IndexError:
  return False

def fits(chromogram, coloring):
 return (len(chromogram) == len(coloring)) and \
        (all([coloring[i] == 1 if value == 0 else value != 1 or valid_brackets(chromogram, coloring, i) for i, value in enumerate(chromogram)]))

def generate_nary(l, length):
 if length < 2:
  return [[val] for val in l]
 return_list = []
 for val in l:
  for generated in generate_nary(l, length - 1):
   return_list.append([val, *generated])
 return return_list

def generate_all_chromograms(length):
 return generate_nary([0, 1, 2, 3], length)

def all_fitted_chromograms(coloring):
 return [chromogram for chromogram in generate_all_chromograms(len(coloring)) if [value != 1 or matching_bracket(chromogram, i) < len(chromogram) for i, value in enumerate(chromogram)] and chromogram.count(1) == chromogram.count(2) + chromogram.count(3) and fits(chromogram, coloring)]

def is_compatible(coloring, _set):
 all_chromos = all_fitted_chromograms(coloring)
 return all([
  any([fits(chromo, c) for c in _set])
  for chromo in all_chromos
 ])

def all_colorings(length):
 return [c for c in generate_nary([1, 2, 3], length) if eval('^'.join([str(num) for num in c])) == 0]

def permutations_of_coloring(coloring):
 colorings = []
 for permutation in [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]:
  colorings.append([permutation[num - 1] for num in coloring])
 return colorings

def all_suitable_colorings(_set, before = []):
 # 1) all colorings in _set are suitable.
 colorings = all_colorings(len(_set[0]))
 # let us add our compatible colorings.
 initial_set = _set + [coloring for coloring in colorings if is_compatible(coloring, _set)]
 # then, we get all the permutations of each of those colorings.
 for coloring in [*initial_set]:
  for permutated in permutations_of_coloring(coloring):
   initial_set.append(permutated)
 initial_set = [''.join([str(num) for num in coloring]) for coloring in initial_set]
 initial_set = [*{*initial_set}] # remove duplicates
 initial_set = [[int(char) for char in coloring] for coloring in initial_set]
 if len(initial_set) in [len(before), len(colorings)]:
  return initial_set
 return all_suitable_colorings(initial_set, _set)

def main(_set):
 return len(all_suitable_colorings(_set)) == len(all_colorings(len(_set[0])))
```

> 5 votes

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


title: Convert J brackets back to 2-D list

text:
# Question
Title: Convert J brackets back to 2-D list
Let's say we have a 2-D list, like the following one:

\\$ \begin{bmatrix} \color{red}{1} & \color{red}{2} & \color{red}{3} & \color{red}{4} \\ \color{blue}{5} & \color{blue}{6} & \color{blue}{7} & \color{red}{8} \\ \color{green}{9} & \color{green}{10} & \color{blue}{11} & \color{red}{12} \end{bmatrix} \\$

Notice how the top row and the right column is red. For the purposes of this question, let's call this a J-bracket. The *2nd* J-bracket is highlighted in blue, and the 3rd J-bracket is highlighted in green. Your challenge is not to *find* the J-brackets, but given the J-bracket list, you need to return the original 2-D list.

In many cases, there will be more than one 2-D list possible based on the J-brackets. In this case, you can return either of the possible 2-D lists, or you can return a list of the possiblities.

Let's say you are given the list `[[1,2,3,4,5,6], [1,2,3,4], [1,2]]`. This means the 1st J-bracket is `[1,2,3,4,5,6]`, the 2nd J-bracket is `[1,2,3,4]`, and the 3rd one is `[1,2]`. There are two different possible matrixes that can be created from these J-brackets:

\\$ \begin{bmatrix} \color{red}{1} & \color{red}{2} & \color{red}{3} & \color{red}{4} \\ \color{blue}{1} & \color{blue}{2} & \color{blue}{3} & \color{red}{5} \\ \color{green}{1} & \color{green}{2} & \color{blue}{4} & \color{red}{6} \end{bmatrix} \\$

OR:

\\$ \begin{bmatrix} \color{red}{1} & \color{red}{2} & \color{red}{3} \\ \color{blue}{1} & \color{blue}{2} & \color{red}{4} \\ \color{green}{1} & \color{blue}{3} & \color{red}{5} \\ \color{green}{2} & \color{blue}{4} & \color{red}{6} \end{bmatrix} \\$

## Test cases

```
[[1,2,3,4,5], [1,2,3], [1]] => [[1,2,3], [1,2,4], [1,3,5]]
[[1,2,3,4,5,6], [1,2,3,4], [1,2]] => [[1,2,3], [1,2,4], [1,3,5], [2,4,6]]
                                  OR [[1,2,3,4], [1,2,3,5], [1,2,4,6]]
[[6,8,9,6,5,8,2],[1,7,4,3,2],[2,3,1]] => [[6,8,9,6,5], [1,7,4,3,8], [2,3,1,2,2]]
                                      OR [[6,8,9], [1,7,6], [2,4,5], [3,3,8], [1,2,2]]
[] => []

```

## Rules

✝ The name J-bracket was robbed from this question.

# Answer
# APL(Dyalog Unicode), 20 bytes SBCS

```
{(↓∘⍺⍪⍵,∘⍪↑∘⍺)-≢⍵}/⊆

```

Try it on APLgolf!

Nest if simple (if the input is `[]`). This is necessary to deal with the empty case.
`/` Reduce the list of J-brackets from right to left with:
`{ ... }` Takes the current matrix as ⍵ and the new J-bracket as ⍺.
`-≢⍵` Number of rows, negated
`( ... )` Call the tacit function with this as a right argument.
`↑∘⍺` Take that many values from ⍺ (taking a negative amount gets values from the end)
`⍵,∘⍪` Append to ⍵ as a column.
`↓∘⍺⍪` Drop `-≢⍵` values from ⍺, prepend that as a row.
> 7 votes

# Answer
# , 33 26 bytes

```
((}.~-@#),],.({.~-@#))&.>/

```

Try it online!

A single reduction, where each iteration adds another "J layer". Consider left and right parts like `1 2 3 4 (...) 8 9`:

* `({.~-@#)` From the tail of the left list take as many elements as are in the right list:

```
3 4

```
* `],.` Zip with right list

```
8 3
9 4

```
* `(}.~-@#),` Append the remaining front elements of the left list:

```
1 2
8 3
9 4

```
> 6 votes

# Answer
# Curry (PAKCS), 60 bytes

```
f[]=[]
f((a++b):c)=a:f c!b
[]![]=[]
(a:b)!(c:d)=(a++[c]):b!d

```

Try it online!
> 5 votes

# Answer
# K (ngn/k), ~~41~~ ~~40~~ ~~29~~ ~~27~~ 26 bytes

```
{((,i#y),x),'(i:#*x)_y}/|:

```

Try it online!

Simply aping ovs' APL solution.
> 5 votes

# Answer
# PARI/GP, 60 bytes

```
a->matrix(if(w=#a,#a[1]+1-w),w,i,j,a[x=min(w-j+1,i)][i+j-x])
```

Attempt This Online!

Returns the one with height ≥ width, e.g. `[[1,2,3,4,5,6], [1,2,3,4], [1,2]] => [[1,2,3], [1,2,4], [1,3,5], [2,4,6]]`.

---

# PARI/GP, 62 bytes

```
a->matrix(#a,w=if(#a,#a[1]+1-#a),i,j,a[x=min(w-j+1,i)][i+j-x])
```

Attempt This Online!

Returns the one with width ≥ height, e.g. `[[1,2,3,4,5,6], [1,2,3,4], [1,2]] => [[1,2,3,4], [1,2,3,5], [1,2,4,6]]`.

---

In both case, the formula is \\$output\[i,j\]=input\[i+\min(w-i-j+1,0),j-\min(w-i-j+1,0)\]\\$, where \\$w\\$ is the width of the output matrix.
> 2 votes

# Answer
# Charcoal, 17 bytes

```
⮌Ａ«Ｆυ⊞κ⊟ι⊞υι»Ｉ⮌υ

```

Try it online! Link is to verbose version of code. Outputs in Charcoal's default one-element-per-line format. Explanation: Based on my original answer to Find the J twin which has since been superseded by an alternative approach.

```
⮌Ａ«

```

Loop over the J-brackets in reverse order.

```
Ｆυ⊞κ⊟ι

```

Append the end elements of the bracket to the existing rows of the predefined empty array.

```
⊞υι

```

Append the remainder of the bracket to the predefined empty array.

```
»Ｉ⮌υ

```

Output the reverse of the final array.
> 2 votes

# Answer
# JavaScript (ES6), 69 bytes

A `reduceRight()` with a recursive callback function.

```
a=>a.reduceRight(g=(p,c,i)=>i--?g(p,[...c,a[i].pop()],i):[c,...p],[])

```

Try it online!
> 1 votes

# Answer
# , ~~84~~ 83 bytes

```
function(j){m[]=unsplit(j,pmin(row(m<-matrix(unlist(j),length(j))),rev(col(m))))
m}

```

Try it online!

The `unsplit` strategy corresponding to this answer.

-1 thanks to pajonk.
> 1 votes

# Answer
# Python, 69 bytes

```
f=lambda L:L and L[-1:1]or[*zip(*zip(L[0],*f(L[1:])),L[0][-len(L):])]
```

Attempt This Online!
> 1 votes

# Answer
# Jelly, 14 bytes

```
ȯWṚUṭḢ;¥Ɱ¥@/ṚU

```

Try it online! (The TIO comes with a footer that prints the Python repr, to ensure empty arrays are visible; but the bare link works as a function.)

This is very likely to be suboptimal, since I do four (!) reversals of arrays, but I couldn't find a better solution with Jelly's functions. There could also be a shorter way to handle `[]` than `ȯW`, and I might be able to drop the `@`. However, it feels like this challenge *really* happened to hit some weak points in Jelly, as the core of the solutions is tiny.

* The first  (and the `@`) gives us a right-associative reduce. There's no single-byte right-associative reduce in Jelly.
* The `@` also allows us to use / to pop stuff from the new J-bracket, since we can only apply monads to the left arg of dyadic chains.
* The last  reverses the order of the output lines. Since things popped from the J-bracket's end go to the bottom, we have build the output backwards. Also, unfortunately, there's no *prepend to* like , so we have to append the "rest" of the J-bracket to the bottom of the matrix (`;` would require a `W`).
* The `U`'s reverse each input and output line. `ȯWṚṭṪṭ¥Ɱ¥@/Ṛ` is *very* close to correct, but unfortunately gets the innermost J-bracket in the wrong order. I'd need to `U` or `W` it somehow to make the output correct.

```
ȯW                ȯr Wrap (replace [] with [[]])
  Ṛ               Ṛeverse order of J-brackets
   U              Upend (reverse) each J-bracket
           /      reduce lines with:
          @         (swap args: left=next J-bracket, right=matrix)
        Ɱ           Ɱap over lines of matrix:
     Ḣ                remove Ḣead (first) of J-bracket
      ;               append that to matrix line
    ṭ               ṭack (append) remaining J-bracket to matrix
            Ṛ     Ṛeverse order of lines
             U    Upend (reverse) each line

```
> 1 votes

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


title: Find the next 1-sparse binary number

text:
# Question
Title: Find the next 1-sparse binary number
A positive integer N is *K*-sparse if there are at least *K* 0s between any two consecutive 1s in its binary representation.

So, the number 1010101 is 1-sparse whereas 101101 is not.

Your task is to find the next 1-sparse number for the given input number. For example, if the input is 12 (`0b1100`) output should be 16 (`0b10000`) and if the input is 18 (`0b10010`) output should be 20 (`0b10100`).

Smallest program or function (in bytes) wins! Standard loopholes disallowed.

# Answer
> 13 votes
# Pyth, 9 bytes

My first attempt at Pyth:

```
f!.&TyThQ

```

Try it here

```
               implicit: Q = input()
f      hQ      find the first integer T >= Q + 1,
               that satisfies the condition:
 !.&TyT        T & (T * 2) is 0

```

# Answer
> 9 votes
# CJam, ~~14~~ 11 bytes

3 bytes saved thanks to DigitalTrauma.

```
l~{)___+&}g

```

Test it here.

## Explanation

```
l~          "Read and eval input.";
  {      }g "Do while...";
   )_       "Increment and duplicate (call this x).";
     __+    "Get two more copies and add them to get x and 2x on the stack.";
        &   "Take their bitwise AND. This is non-zero is as long as x's base-2
             representation contains '11'.";

```

This leaves the last number on the stack which is printed automatically at the end of the program.

# Answer
> 8 votes
# Python 2, 44 bytes

This is a complete python program that reads in n, and prints the answer. I think it does quite well in the readability sub-competition.

```
n=input()+1
while'11'in bin(n):n+=1
print n

```

The test results:

```
$ echo 12 | python soln.py
16
$ echo 18 | python soln.py
20

```

# Answer
> 6 votes
# Pyth, ~~12~~ 11 bytes

```
f!}`11.BThQ

```

Try it online: Pyth Compiler/Executor.

```
               implicit: Q = input()
f        hQ    find the first integer T >= Q + 1,
               that satisfies the condition:
 !}`11.BT         "11" is not in the binary representation of T

```

# Answer
> 5 votes
# Mathematica, ~~41~~ 30 bytes

Saved 11 bytes thanks to Martin Büttner.

```
#+1//.i_/;BitAnd[i,2i]>0:>i+1&

```

# Answer
> 4 votes
# Perl, 31

```
#!perl -p
sprintf("%b",++$_)=~/11/&&redo

```

Or from the command line:

```
 perl -pe'sprintf("%b",++$_)=~/11/&&redo' <<<"18"

```

# Answer
> 4 votes
## J, 20 characters

A monadic verb. Fixed to obey the rules.

```
(+1 1+./@E.#:)^:_@>:

```

### Explanation

First, this is the verb with spaces and then a little bit less golfed:

```
(+ 1 1 +./@E. #:)^:_@>:
[: (] + [: +./ 1 1 E. #:)^:_ >:

```

Read:

```
    ]                             The argument
      +                           plus
        [: +./                    the or-reduction of
               1 1 E.             the 1 1 interval membership in
                      #:          the base-2 representation of the argument,
[: (                    )^:_      that to the power limit of
                             >:   the incremented argument

```

> The argument plus the or-reduction of the `1 1` interval membership in the base-2 representation of the argument, that to the power limit applied to the incremented argument.

I basically compute if `1 1` occurs in the base-2 representation of the input. If it does, I increment the input. This is put under a power-limit, which means that it is applied until the result doesn't change any more.

# Answer
> 4 votes
# APL, 18 bytes

```
1∘+⍣{~∨/2∧/⍺⊤⍨⍺⍴2}

```

This evaluates to a monadic function. Try it here. Usage:

```
   1∘+⍣{~∨/2∧/⍺⊤⍨⍺⍴2} 12
16

```

## Explanation

```
1∘+                    ⍝ Increment the input ⍺
   ⍣{            }     ⍝ until
     ~∨/               ⍝ none of
        2∧/            ⍝ the adjacent coordinates contain 1 1 in
           ⍺⊤⍨⍺⍴2      ⍝ the length-⍺ binary representation of ⍺.

```

# Answer
> 4 votes
# Javascript, 25 19

Using the fact that, for a 1-sparse binary number, `x&2*x == 0`:

```
f=x=>x++&2*x?f(x):x

```

# Answer
> 3 votes
# JavaScript (ES6), 39 ~~43~~

No regexp, no strings, recursive:

```
R=(n,x=3)=>x%4>2?R(++n,n):x?R(n,x>>1):n

```

Iterative version:

```
F=n=>{for(x=3;x%4>2?x=++n:x>>=1;);return n}

```

It's very simple, just using right shift to find a sequence of 11. When I find it, skip to next number. The recursive version is directly derived from the iterative one.

**Ungolfed** and more obvious. To golf, the trickiest part is merging the inner and outer loops (having to init x to 3 at start)

```
F = n=>{
  do {
    ++n; // next number
    for(x = n; x != 0; x >>= 1) {
      // loop to find 11 in any position
      if ((x & 3) == 3) { // least 2 bits == 11
        break;
      }
    }
  } while (x != 0) // if 11 was found,early exit from inner loop and x != 0
  return n
}

```

# Answer
> 3 votes
# Python 2, 37 bytes

```
f=input()+1
while f&2*f:f+=1
print f

```

Used the logic `x & 2*x == 0` for 1-sparse number.
Thanks to @Nick and @CarpetPython.

# Answer
> 2 votes
# JavaScript, ~~75~~ ~~66~~ 62 bytes

Thanks to Martin Büttner for saving 9 bytes and Pietu1998 for 4 bytes!

```
function n(a){for(a++;/11/.test(a.toString(2));a++);return a;}

```

How it works: it runs a `for` loop starting from `a + 1` as long as the current number is not 1-sparse, and if it is, the loop is interrupted and it returns the current number. To check whether a number is 1-sparse, it converts it to binary and checks whether it does not contain `11`.

Un-golfed code:

```
function nextOneSparseNumber(num) {
    for (num++; /11/.test(num.toString(2)); num++);
    return num;
}

```

# Answer
> 2 votes
# Julia, 40 bytes

```
n->(while contains(bin(n+=1),"11")end;n)

```

This creates an anonymous function that accepts a single integer as input and returns the next highest 1-sparse integer. To call it, give it a name, e.g. `f=n->...`, and do `f(12)`.

Ungolfed + explanation:

```
function f(n)

    # While the string representation of n+1 in binary contains "11",
    # increment n. Once it doesn't, we've got the answer!

    while contains(bin(n += 1), "11")
    end

    return(n)
end

```

Examples:

```
julia> f(12)
16

julia> f(16)
20

```

Suggestions and/or questions are welcome as always!

# Answer
> 2 votes
# Python, ~~39~~ 33 bytes

Try it here: http://repl.it/gpu/2

In lambda form (thanks to xnor for golfing):

```
f=lambda x:1+x&x/2and f(x+1)or-~x

```

Standard function syntax ~~turned out to be shorter than a lambda for once!~~

```
def f(x):x+=1;return x*(x&x*2<1)or f(x)

```

# Answer
> 2 votes
# \>\<\> (Fish), 31 + 3 = 34 bytes

```
1+:>:  4%:3(?v~~
;n~^?-1:,2-%2<

```

Usage:

```
>python fish.py onesparse.fish -v 12
16

```

3 bytes added for the `-v` flag.

# Answer
> 1 votes
# JavaScript (ECMAScript 6), 40

By recursion:

```
g=x=>/11/.test((++x).toString(2))?g(x):x

```

# JavaScript, 56

Same without arrow functions.

```
function f(x){return/11/.test((++x).toString(2))?f(x):x}

```

# Answer
> 1 votes
# Scala, 65 bytes

```
(n:Int)=>{var m=n+1;while(m.toBinaryString.contains("11"))m+=1;m}

```

(if a named function is required, solution will be 69 bytes)

# Answer
> 1 votes
# Java, 33 bytes.

Uses the method in this answer

```
n->{for(;(n++&2*n)>0;);return n;}

```

TIO

# Answer
> 1 votes
# Vyxal, 6 bytes

```
λd⋏[›x

```

Try it Online!

## How?

```
λd⋏[›x
λ      # Open a lambda for recursion
 d     #  Double
  ⋏    #  Bitwise AND the doubled input with the input
   [   #  If this is truthy (non-zero):
    ›x #   Increment and recurse

```

# Answer
> 0 votes
## Ruby, 44

```
->(i){loop{i+=1;break if i.to_s(2)!~/11/};i}

```

Pretty basic. A lambda with an infinite loop and a regexp to test the binary representation. I wish that `loop` yielded and index number.

# Answer
> 0 votes
# Matlab (77 74 bytes)

```
m=input('');for N=m+1:2*m
if ~any(regexp(dec2bin(N),'11'))
break
end
end
N

```

Notes:

* It suffices to test numbers `m+1` to `2*m`, where `m` is the input.
* `~any(x)` is `true` if `x` contains all zeros *or* if `x` is empty

# Answer
> 0 votes
**C (32 bytes)**

```
f(int x){return 2*++x&x?f(x):x;}

```

Recursive implementation of the same algorithm as so many other answers.

# Answer
> 0 votes
# Perl, 16 bytes

Combining the `x&2*x` from various answers (I think Nick's first) with nutki's `redo` yields:

```
perl -pe'++$_&2*$_&&redo'

```

Tested in Strawberry 5.26.

# Answer
> 0 votes
# Japt, 8 bytes

```
_&ZÑ}fUÄ

```

Run it online.

# Answer
> 0 votes
# Jelly, 7 bytes

```
‘&Ḥ¬Ɗ1#

```

A full program accepting a single, non-negative integer which prints a positive integer (as a monadic link it yields a list containing a single positive integer).

**Try it online!**

### How?

Starting at `v=n+1`, and incrementing, double `v` to shift every bit up one place and bit-wise AND with `v` and then perform logical NOT to test if `v` is 1-sparse until one such number is found.

```
‘&Ḥ¬Ɗ1# - Main Link: n   e.g. 12
‘       - increment           13
     1# - 1-find (start with that as v and increment until 1 match is found) using:
    Ɗ   -   last three links as a dyad:
  Ḥ     -   double v
 &      -   (v) bit-wise AND (with that)
   ¬    -   logical NOT (0->1 else 1)
        - implicit print (a single item list prints as just the item would)

```

# Answer
> 0 votes
# Stax, 5 bytes

```
╦>ù╤x

```

Run and debug it

It works using this procedure. The input starts on top of the stack.

* Increment and copy twice.
* Halve the top of the stack.
* Bitwise-and top two elements on the stack.
* If the result is truthy (non-zero) repeat the entire program.

---
Tags: code-golf, number, arithmetic, base-conversion, binary
---