title: Classify a graph

text:
# Question
Title: Classify a graph
## Challenge

Given a graph (a structure consisting of nodes and vertices), classify it according to a few categories.

Specifically, you will be given an unweighted directed graph, which is a set of nodes and edges from one node to another (but not necessarily both ways). You can take this in any reasonable and consistent format, like an adjacency list/matrix. You may take a list of nodes, but it is unnecessary. *No edge will appear twice exactly* (however, \\$A\rightarrow B\\$ and \\$B\rightarrow A\\$ might both appear). Every node will be a part of at least one edge, so you can gather all needed information from the edges and don't need a list of nodes if you don't want it.

Then, you must classify it according to the following categories:

1. If every pair of connected nodes is connected both ways, the graph is **undirected**. Otherwise, it is **directed**.
2. A **cycle** is a path in the graph from one node to another where the first and last nodes are the same, no other nodes appear multiple times in the path, and there are at least three distinct nodes in the path. If a such cycle exists, the graph is **cyclic**, and otherwise, it is **acyclic**.
3. If, for every pair of nodes \\$A, B\\$, there exists either a path from \\$A\\$ to \\$B\\$, the graph is **strongly connected**. If replacing every edge with an undirected edge (that is, substituting each edge \\$A\rightarrow B\\$ with \\$A\leftrightarrow B\\$) makes the aforementioned condition true but the graph isn't strongly connected, then the graph is **weakly connected**. Otherwise, the graph is **disconnected**.

Note that it is impossible to construct a strongly connected acyclic directed graph; if every pair of nodes has a path in both directions, either they are the same, and it is undirected, or they are different, and it is cyclic. It is impossible to construct a weakly connected undirected graph by definition (replacing the edges with undirected edges doesn't mean anything on an undirected graph, so the graph would've been strongly connected already).

### Formal specification

If the first part made sense and you understand the graph theory, this part is probably not worth reading. It is just here to be exceedingly clear about the definitions.

To be extremely formal, a graph \\$G\\$ is a set of nodes \\$N\\$ and edges \\$E\\$ where each edge connects a node \\$A\\$ to a node \\$B\\$. The first condition asks if \\$(A\rightarrow B)\in E\Leftrightarrow(B\rightarrow A)\in E\\$ for all \\$A,B\in N\\$. If so, the graph is **undirected**, and otherwise, it is **directed**. Then, we define a path as the following:

There exists a path from \\$A\\$ to \\$B\\$ if and only if \\$(A\rightarrow B)\in E\\$ or there exists some node \\$C\\$ such that there is a path from \\$A\\$ to \\$C\\$ and a path from \\$C\\$ to \\$B\\$.

The second condition asks the following: does there exist a node \\$A\\$ such that there is a path \\$A\rightarrow B\rightarrow C\rightarrow\dots\rightarrow A\\$ where no node appears more than once except for \\$A\\$ and there are at least three distinct nodes in the path? If so, the graph is **cyclic**, and otherwise, it is **acyclic**. (Note that the "at least three distinct nodes" condition prevents \\$A\rightarrow B\rightarrow A\\$ from being treated as a cycle in both undirected and directed graphs.)

The final condition asks the following: for every \\$A,B\in N\\$, does there exist a path from \\$A\\$ to \\$B\\$? If so, the graph is **strongly connected**. If not, if we add \\$(B\rightarrow A)\\$ to \\$E\\$ for every \\$(A\rightarrow B)\in E\\$, does this condition become true? If so, the graph is **weakly connected**. Otherwise, it is **disconnected**.

## Formatting

As mentioned above, you can take the graph in any reasonable format. You should output one of 9 distinct values for each possible combination of (undirected, directed) × (cyclic, acyclic) × (strongly connected, weakly connected, disconnected); these can be any 9 consistent and distinct outputs, including erroring. For example, you may choose to output 7 various values for 7 of the categories, output nothing for the 8th, and crash on the 9th. You cannot error for more than one category (this is to prevent needing to formally define distinct classes of errors). Outputting the same value to STDOUT and STDERR count as two different outputs.

**There will be at least one edge.** This means that a graph containing a single node is also invalid.

## Test Cases

You can find an image representation of these test cases here, which includes an example for each of the categories in a table format.

These test cases are given as a list of edges in the format `[[src, dest], [src, dest], ...]`. The output is descriptive, but you don't need to output the full name, of course.

```
[[1, 2], [2, 3], [3, 4], [4, 1]]                                   -> Directed,   Cyclic,  Strongly Connected
[[1, 2], [2, 1], [2, 3], [3, 2]]                                   -> Undirected, Acyclic, Strongly Connected
[[1, 2], [2, 1], [2, 3], [3, 2], [3, 1], [1, 3]]                   -> Undirected, Cyclic,  Strongly Connected
[[1, 2], [2, 3]]                                                   -> Directed,   Acyclic, Weakly Connected
[[1, 2], [2, 3], [3, 4], [4, 2]]                                   -> Directed,   Cyclic,  Weakly Connected
[[1, 2], [3, 4]]                                                   -> Directed,   Acyclic, Disconnected
[[1, 2], [3, 4], [4, 5], [5, 3]]                                   -> Directed,   Cyclic,  Disconnected
[[1, 2], [2, 1], [3, 4], [4, 3]]                                   -> Undirected, Acyclic, Disconnected
[[1, 2], [2, 1], [3, 4], [4, 3], [4, 5], [5, 4], [5, 3], [3, 5]]   -> Undirected, Cyclic,  Disconnected

```
* Is the graph acyclic? \- determines if a directed graph is acyclic (input format is required to be an adjacency list)
* Is this figure connected? \- determines if an undirected grid graph is connected (input format is required to be a list of grid coordinates)

This is , so the shortest solution in bytes wins per language category.

# Answer
> 5 votes
# Jelly, 65 bytes

```
;U,Ɗṭ;Ɱ¥0ị⁹ẹ@ịƭƒƲḟḊƊ$€ẎQɗƬZṪƊ€.ịⱮfƑ@ɗ€;ṪL>3ƊƇ.ịⱮƲE€ẸɗɗFQœ!2Ʋ;fƑU$

```

Try it online!

A monadic link taking a list of edges in the same format as the question and returning a list of zeros and ones in the order `[connected, strongly connected, cyclic, undirected]`. Strongly connected graphs will have both of the first two list members set whereas weakly connected will just have the first of those two set.

## Explanation

A monadic link taking argument `x`, a list of edges in the format `[src, dest],[src, dest],…` and returning a list of 4 integers as specified above. Works by generating all possible paths through the graph and through the graph with the opposite direction edges added before running some tests. Apologies if this is a bit tricky to follow - Jelly’s tacit style of programming can get a bit convoluted when as long as this!

```
   Ɗ                                                              | Following as a monad:
;U                                                                | - Concatenate x to x with each of its members reversed
  ,                                                               | - Pair with x
                            Ɗ€                                    | For each of these (call each one y) do the following:
                        ɗƬZ                                       | - Do the following to y until no change, using the transposed version of y as the right argument
                    $€                                            | - For each member of the list z:
                   Ɗ                                              |   - Following as a monad:
                Ʋ                                                 |     - Following as a monad:
        0ị                                                        |       - Last member (call this a)
          ⁹    ƒ                                                  |       - Reduce the transposed version of y using a as the initial argument and the following:
              ƭ                                                   |         - Alternate between:
           ẹ@                                                     |           - Indices of a in the first member of the transposed y
             ị                                                    |           - Index into the second member of the transposed y
                 ḟḊ                                               |     - Filter out members of z except for the first
       ¥                                                          |   - Using the above as the right argument (call this b) and z as the left:
    ṭ                                                             |     - Tag z onto
     ;Ɱ                                                           |       - The result of concatenating each of b onto z
                      Ẏ                                           |   - Tighten (concatenate outer lists)
                       Q                                          |     - Unique
                           Ṫ                                      | - Tail (call this w)
                                                           Ʋ      | Following as a monad applied to x:
                                                      F           | - Flatten
                                                       Q          | - Unique
                                                        œ!2       | - Permutations length 2 (call this v)
                                                     ɗ            | Using v as the right argument and w as the left argumemt
                                    ɗ€                            | - For each member u of w:
                              .ịⱮ                                 |   - Take the last and first members of the list
                                 fƑ@                              |   - Check whether filtering v just to the members of u leaves v unchanged (gives the connected and strongly connected results)
                                      ;             ɗ             | - Concatenate to the following:
                                                Ʋ                 |   - Following as a monad
                                       Ṫ                          |     - Tail
                                        L>3ƊƇ                     |     - Filter to keep only lists of length at least 4
                                             .ịⱮ                  |     - Last and first members
                                                 E€               |     - Check if each is equal (returns whether x is cyclic)
                                                   Ẹ              |     - Any
                                                            ;   $ | Concatenate to:
                                                             fƑU  | - Check whether x left unchanged if filtering only to the x with each member reversed (undirected)

```

# Answer
> 5 votes
# Julia 1.0, ~~138~~ 130 bytes

```
!a=(z=1:size(a,1);~a=all(sum([a].^z).>0);a/i=any(j->a[i,j]>0&&(a[[j,i],i]=0:1;a[j,j]>0||+a/j),z);[a!=a',any([+a]./z),~a,~(a.|a')])

```

Try it online!

Takes input as an adjacency matrix (In TIO footer it is constructed from edge list by `adj` function), outputs a boolean array with the following members:

```
[directed? cyclic? strongly_connected? connected?]

```

### Explanation

Checking directedness is trivial: if adjacency matrix is equal to its transpose: \\$(A = A^T)\\$, then all nodes are bidirectional and the entire graph is undirected.

Connectedness can be checked using a known property of matrix powers: the elements of \\$A^n\\$ indicate the number of \\$n\\$-length walks between the respective nodes. Therefore, if we calculate \\$A^n\\$ for all \\$n\\$ from \\$1\\$ to size of \\$A\\$ and find a non-zero element in each position at least once (this function is assigned to `~` operator in the code), it means that we can reach any node starting from any other node and the graph is strongly connected. Repeating this test with the analogous undirected adjacency matrix, where all edges are set to bidirectional `(a.|a')` shows whether the graph is at least weakly connected.

Finally, presence of cycles is detected using depth-first search (`/` operator taking a copy of `a` and a starting node `i`). The nodes are marked as visited by setting the respective diagonal positions `a[i,i]=1`, and when passing through the edge `i->j` we also temporarily set `a[j,i]=0` to prevent going back through the same edge in opposite direction and detecting a pseudo-cycle. Since we can have multiple disconnected components, the search procedure is repeated for every possible starting node to ensure that no cycles are missed.

*Note: The number of connected components can also be determined algebraically as the number of zeroes among eigenvalues of Laplacian matrix. And according to this Math.SE answer, Laplacian can also be used to check for cycles. However, that formula works for undirected graphs only, and importing LinearAlgebra module is too costly for golfing anyway.*

---
Tags: code-golf, graph-theory, classification
---


title: Calculate the (n x "super")factorial

text:
# Question
Title: Calculate the (n x "super")factorial
## Introduction

Factorials are one of the most frequently used examples to show how a programming language works. A factorial, denoted \\$n!\\$, is \\$1⋅2⋅3⋅…⋅(n-2)⋅(n-1)⋅n\\$.

There is also the superfactorial (there are other definitions of this, but I chose this one because it looks more like the factorial), denoted \\$n$\\$, which is equal to \\$1!⋅2!⋅3!⋅…⋅(n-2)!⋅(n-1)!⋅n!\\$.

From that you can create an infinity of (super)\*factorials (means *any number of times `super` followed by one `factorial`*) (supersuperfactorial, supersupersuperfactorial, etc...) which all can be represented as a function \\$‼(x,y)\\$, which has two parameters, \\$x\\$ the number to (super)\*factorialize, and y, the number of times plus one that you add the prefix *super* before *factorial* (So if \\$y=1\\$ it would be a factorial (\\$x!=\space‼(x,1)\\$), with \\$y=2\\$ a superfactorial, and with \\$y=4\\$ a supersupersuperfactorial).

\\$!!\\$ is defined as such:
\\$‼(x,0)=x\\$ (if \\$y\\$ is 0, return \\$x\\$)
\\$‼(x,y)\space=\space‼(1,y-1)\space⋅\space‼(2,y-1)\space⋅\space‼(3,y-1)\space⋅…⋅\space‼(x-2,y-1)\space⋅\space‼(x-1,y-1)\\$
The second definition would have looked cleaner with a pi product \\$\prod\\$, but it does not display properly. (image here)

In Python, \\$!!\\$ could be implemented this way:

```
from functools import reduce
def n_superfactorial(x, supers):
    if x == 0:
        return 1
    elif supers == 0:
        return x
    return reduce(lambda x,y:x*y, [n_superfactorial(i, supers-1) for i in range(1, x+1)])

```

## Challenge

Create a function/program that calculates \\$!!(x,y)\\$.
Your code is *not* required to support floats or negative numbers.
\\$x\\$ will always be \\$≥1\\$ and \\$y\\$ will always be \\$≥0\\$.
It is not required to compute \\$!!\\$ via recursion.
Your program may exit with a recursion error given large numbers, but should at least *theoretically* be able to calculate in finite time any (super)\*factorial.

## Test cases

```
Format : [x, y] -> result
[1, 1]    -> 1
[2, 2]    -> 2
[3, 3]    -> 24
[3, 7]    -> 384
[4, 4]    -> 331776
[5, 3]    -> 238878720
[2232, 0] -> 2232
[3, 200]  -> 4820814132776970826625886277023487807566608981348378505904128

```

Note: if your language does not support integer types that are that large, you are not required to support the last test case.

## Scoring

This is , so shortest answer in bytes wins.

# Answer
# APL (Dyalog Unicode), 18 bytes

A naïve recursive implementation.

```
{×⍺:×/(⍺-1)∇¨⍳⍵⋄⍵}

```

Try it online!
> 3 votes

---
Tags: code-golf, factorial
---


title: Tips for restricted source in zsh

text:
# Question
Title: Tips for restricted source in zsh
Adapted from tips for restricted-source in Python

Just like , pushes one to exploit quirks and hidden features of the zsh language. While we already have a place to collect all these for , those for remain transmitted by word of mouth or hidden deep within the manual pages.

So, what are some for solving challenges in zsh?

**Please only include 1 tip per answer.** Please downvote answers with multiple tips in them.

---

**What makes a good tip here?** There are a couple of criteria I think a good tip should have:

1. It should be (somewhat) non obvious.

Similar to the tips, it should be something that someone who has golfed in zsh (or bash) a bit and read the tips page would not immediately think of. For example, "replace `a + b` with `a+b` to avoid using spaces" is obvious to any golfer since it is already a way to make your code shorter and thus not a good tip.
2. It should not be too specific.

Since there are many different types of source restrictions, answers here should be at least somewhat applicable to multiple source restrictions, or one common source restriction. For example tips of the form "How to X without using character(s) Y" are generally useful since banned characters is a common source restriction. The thing your tip helps to do should also be somewhat general. For example tips of the form "How to create numbers with X restriction" are useful since many programs utilize numbers regardless of the challenge. Tips of the form "How to implement Shor's algorithm with X restriction" are basically just answers to a challenge you just invented and not very helpful to people solving other challenges.

# Answer
# Globbing

Globs are patterns used to match files and other strings. If you can't use a particular character but you need to access a command with that character in its name, you can often approximate it with a glob, like `/*/ls`

The full description of glob syntax is under `Filename Generation` in `zshexpn(1)`, but here is a summary:

* `?` matches any single character
* `*` matches zero or more characters
* `<1-10>` matches any number between 1 and 10
    + `<->` matches any number
* `[a-d]` matches any character in the set `abcd`
* `[:name:]` matches any character in the named set (full details in the man-page)
* `[^a]` or `[!a]` matches any character except `a`
    + `[^]` or `[!]` matches any single character
* `(a|b)` matches `a` or `b`
* With the option `--nocaseglob`, globbing is case-insensitive. This allows you to do `/*/LS` instead of `ls`
* With the option `--extendedglob`, you can use the additional syntax:
    + `^pattern` matches anything except `pattern`
    + `a~b` matches pattern `a` but not `b`
    + `a~^b` matches both patterns `a` and `b`
    + `a#` matches zero or more instances of `a`
    + `a##` matches one or more instances of `a`
> 5 votes

# Answer
# Alternatives to common commands

* `echo` can be replaced by:
    + `print`
    + `<<<string` (limited syntax)
    + `printf %s` (joins with no whitespace and doesn't have a trailing new-line)
* `printf` and `print -f` are identical
* `ls` can be replaced by:
    + `dir -w1` is exactly the same
    + `vdir` is almost the same, except that its output format is different
    + `echo *`
    + `echo ?#` (requires `--extendedglob`)
* `cat` can be replaced by:
    + `<file` or `<&1` where `1` is a file descriptor (also shorter and does't use any external commands!)
    + `cut -f1-`
    + `sed ""`
    + `dd` (but has a different syntax)
    + `tee` (only for stdin)
    + `grep $`
    + `head -X` or `tail -X`, where `X` is known to be greater than the number of lines (or without a `-X` if `X < 10`)
    + `fold -X`, where `X` is known to be greater than the maximum line length (or without a `-X` if `X < 80`)
    + `expand`, when there are known to be no spaces
    + `tac`, when there is only one line
    + `tac|tac`
    + `rev`, when there is only one character per line
    + `rev|rev`
    + `sort`, when the lines are known to be sorted
    + `uniq`, when there are known not to be any repeated lines
> 4 votes

# Answer
# Syntax in which (nearly) any character can be used

Yes, even control characters. Yes, even the null byte. Replace `%` in the following expressions:

* Delimiters for PE flags: `${(s%foo%)1}` (exceptions: one of `<` `(` `[` `{` must have the associated paired delimiter `>` `)` `]` `}`)
* Similarly, delimiters for the `F`, `W`, and `s` modifiers: `${1:F%expr%}`, `${1:s%str%repl}` (same exceptions)
* Zsh's equivalent to `ord` (as already mentioned): `$[##%]` (exceptions: `]` must be `\`-escaped, as does `\`)
> 2 votes

# Answer
# ASCII character conversion

zsh has no explicit `chr` and `ord` functions, but they are achievable in various ways.

## `ord`:

* `$[#A]` \- the value of the first character in the variable `A`
* `$[##x]` \- the value of `x`
* `chars=({!..~}); $chars[(i)$A]` \- construct an ASCII array and find the index of a value in it (doesn't work for control characters, whitespace, or Unicode)

## `chr`:

* `${(#)A}` \- the character with the codepoint stored in the variable `A`
* `$'\157'`, `$'\x6f'` \- literals with codepoint octal 157 or hexadecimal 6F
    + this syntax doesn't allow variable substitutions, but we could be use an `eval`, like `eval "echo $'\\$A'"`
* `echo \\157` \- literal octal/hex escape sequences
    + can also use `print` or `printf` instead of `echo`
    + variable substitution is possible, so we can use a decimal value by converting to octal: `\\$(printf %o $A)` or `\\$[[##8]A]`
* `chars=({!..~}); $chars[A]` \- construct an ASCII array and index into it (doesn't work for control characters, whitespace, or Unicode)
> 1 votes

# Answer
# Variables without a `$`

Here are a variety of techniques for storing and accessing data without using the typical `$variable` expansion syntax.

## Listing

The `set` builtin lists all variables and their values, which you can explicitly sift through to find the one you want. For example, `set|grep my_var_name|cut -d= -f2-`.

You can also use `typeset`, `declare`, `local`, `float`, or `integer` in place of `set` (those last two operate only on their namesake types, which are assigned implicitly when used in arithmetic expressions)

This may be unreliable if the variable is an array of if its value has special characters.

## Named Directories

Detailed in `zshexpn(1)` § Filename Expansion, named directories are intended as shortcuts for typing whole paths in an interactive shell, but they work in scripts too.

"Assignment" is done with `hash -d name=value`, and expansion is done with `~name`. The expansion only works when at the start of a whole word and can't be followed by anything except a `/`.

You can also use `hash -dm name` or `hash -dv name` which finds the value of `name`, or use `hashs -d` on its own to list all the values, and then find the right one using a similar technique to above.

## Fake command names

Similar to named directories, but without the `-d`. The `hash` builtin would ordinarily add the `value` as the cached lookup path for the "command" `name` when it is looked up in `$PATH`.

Expansion can be done with one of:

* `which name`
* `where name`
* `whence name`
* `hash`, with `-v` or `-m`, as detailed above
* `command -v name`
* `command -V name` (has a weird locale-dependent prosaic output format which needs to be parsed)
> 1 votes

---
Tags: restricted-source, tips
---


# Question
Title: How to ignore first user input in Python 3
I have 2 inputs: 1 single number and some numbers separated by whitespace:

```
1
1 2 3 4 5

```

I want to loop over the second input, and I don't need the first input. I did this, which works:

```
input()
for x in input().split():somecode()

```

But can I go directly to the second input without doing the `input()` at the beginning or with shorter code?

I tried this code (-2 bytes) but it doesn't work, it needs two `input()` to work:

```
a,b=input()
for x in b.split():somecode() #Error : not enough values to unpack (expected 2, got 1)

a,b=input(),input()
for x in b.split():somecode() #OK

```

# Answer
# `open(0)`, 40 bytes

The builtin function `open` returns a file object which can be iterated over, line by line. Usually you pass a path to `open`, but it also takes *file descriptor*, which are integers that refer to special files.

`0` is the file descriptor for the standard input (source), and this allows you to open the input as file with `open(0)`.

Converting this file to a list (of lines) and accessing the second entry saves 3 bytes in this case:

```
for x in[*open(0)][1].split():somecode()

```

Other than `input()` this does not remove trailing newline characters (`\n`), but in this case `split` takes care of it. Another downside is that you can not combine `input()` and `open(0)`. The same technique often helps when you need to read multiple lines of input, example:

```
# a is the first line of input, b the seconds and r contains all remaining lines.
a,b,*r=open(0)

```
> 16 votes

# Answer
# Python 3, 42 bytes

You can use `open(0)` to read all the inputs in once and unpack them.

```
_,a=open(0)
for i in a.split():somecode(i)

```

Try it online!

if the inputs contains more than two lines you can also use:

```
_,*a=open(0)

```

Try it online!

but it will append a trailing newline to all the elements but the last
> 4 votes

---
Tags: tips, python
---


title: A quantum quine

text:
# Question
Title: A quantum quine
Your challenge is to write a program that is a quine, meaning it prints out its own source code.

For at least one individual character, when it is removed from the program's source, a single different character is removed from the output.

By different, I mean that the character removed from the code is distinct from the character removed from the output - not just in a different place, but a different character altogether.

Your program, modified or unmodified, may output to stderr as long as it also outputs the correct text to stdout.

# Scoring

Your score is the number of character this *doesn't* work for, with lower being better.

For example, if the program `abc` is a quine in your language, and the program `ac` prints `ab`, your score is 2, because removing one of the chars works and removing the other two doesn't.

~~I have a 200-point bounty for anyone who gets score = 0. This may be increased, depending on how hard it appears to be.~~ Bounty has been awarded to Jo King's answer.

### ***IMPORTANT***

I updated the criterion to reflect the fact that scores can converge to 1 by adding a large amount of characters.

# Answer
> 31 votes
# Backhand, Score 0, 137 bytes

```
""###:::[[[:::::::::)))))))))888999***EEE666***333+++ssscccjjjlll222%%%]]]333***xxx(((sss~~~rrr~~~'''   sss---***333aaa000~~~rrr:::rrrHHH

```

Try it online!

I've included the interpreter here because the version on TIO is a bit out of date (in this case missing the instructions `E`qual and `s`kip). `E` could be compensated for with `-!`, but you'd need to do a lot of fiddling around with `j`ump to replace `s`kip.

This code outputs itself if no changes are made, the original code missing a trailing `H` if any character other than `H` is removed, and if the `H` is removed, it removes the leading `"` instead.

### Explanation

Basically, each instruction is duplicated three times (except for the leading `"`, which is only doubled). This is used as a form of radiation hardening, so that even if one instruction is removed, it can still regenerate it from the others. Backhand is especially good at this, since by default it executes every third instruction. Removing the duplicates, we get:

```
"#:[:::)))89*E6*3+scjl2%]3*x(s~r~' s-*3a0~r:rH
"       Push the rest of the code, forwards then backwards
 #      No-op
  :[    Dupe the # and decrement it to get "
Start loop
    :::               Make three copies of the top of stack
       )))            Push those to the other stack
          89*E        Is the value a `H`?
              3+scj   If not, jump back to the start of the loop
End loop
                   l2%]3*           If the length of the pushed code is odd (i.e. a character is missing)
                         x(         Flip to the other stack
                           s~       and pop the H if so
                             r~     Reverse the stack and pop the extra "
                               ' s  Skip forwards 32 spaces, i.e. the instruction three from the end
                                    This is the H if all Hs are still present, so it halts and outputs
                                         :r   Otherwise, reverse and duplicate the H
                                       ~r     And pop the "
                                 s-*3a0       And skip back to the H to halt and output

```

# Answer
> 10 votes
# Python 2, 338 bytes, score = ~~16~~ 11

```
exec"aabb==''''''iimmppoorrtt  ssyyss;;dd==cchhrr((3399))**33;;ssyyss..ssttddoouutt..wwrriittee((''eexxeecc''''%%cc''%%3344++''''..jjooiinn((ii**22ffoorr  ii  iinn''aabb==''++dd++aabb++dd++'';;aa==aabb[[::4466]]++aabb[[5533::]];;eexxeecc  aa''))++''bb%%cc[[::::22]]''%%3344))'''''';;aa==aabb[[::4466]]++aabb[[5533::]];;eexxeecc  aab"[::2]

```

Try it online!

when any of the char of inside the string is removed, then the first `"` is removed

## How it works :

* for a string like `"aabbccddee"`, when we take one char every two char, we get `"abcde"` even if it has a missing char.

I then applied this principle on the quine `a="print('a=%r;exec(a)'%a)";exec(a)`

* if the code has a deletion: the end of the string will be `exec a` instead of `exec ab` which result of the deletion of the first `"`.

Note: I could reduce the number of byte by using `input` instead of `sys.stdout.write` to print without a newline but it would throws an error (still valid but uglyer)

# Python 3.8 (pre-release), 187 bytes, score = 16

```
exec(a:="pprriinntt((eenndd==''eexxeecc((aa::==''++((''%%rr[[::::22]]))''%%((''''..jjooiinn((ii**22ffoorr  ii  iinn  aa  iiff''##''!!==ii))++''##''))))[[aa[[--11]]====''))''::]]))#"[::2])

```

Try it online!

# Answer
> 7 votes
# Python 2, score: 206 - 178 = 28

If you remove any single character in the two long strings, the first `"` in the output is omitted.

```
a="print('a=%r,%r;exec max(a,key=len)'%((max(a,key=len),)*2)).replace(chr(34),'',a[0]!=a[1])","print('a=%r,%r;exec max(a,key=len)'%((max(a,key=len),)*2)).replace(chr(34),'',a[0]!=a[1])";exec max(a,key=len)

```

Try it online!

Based on this quine, this executes the longer, and therefore unmodified, string of `a`.

# Answer
> 6 votes
# , 58 bytes; score = 58-2 = 56

```
'->a;cat(sQuote(a),a,2*11)#' ->a;cat(sQuote(a),a,2*11)# 22

```

Try it online!

Pretty boring, but now scores better than my original version (below).
Either of the `1` characters near the end of the code can be deleted, resulting in deletion of one of teh two `2` characters at the end of the output.

---

# , ~~271~~ 253 bytes; score = ~~101~~ 253-160 = 93

(Previous solution, better optimized for the initial 'code length divided by changeable characters' scoring method)

```
a=';`+`=nchar;`!`=sQuote;cat("a=",!(c<-`if`(+a>+b,a,b)),";b=",!c,c,"#"[a==b],sep="")';b=';`+`=nchar;`!`=sQuote;cat("a=",!(c<-`if`(+a>+b,a,b)),";b=",!c,c,"#"[a==b],sep="")';`+`=nchar;`!`=sQuote;cat("a=",!(c<-`if`(+a>+b,a,b)),";b=",!c,c,"#"[a==b],sep="")#

```

Try it online!

If any of the two sets of 80 single-quoted non-`#` characters are removed from the code, the final `#` character is removed from the output.

---
Tags: code-challenge, quine
---


# Question
Title: What if function application was right-associative?
## Background

In Haskell and many other functional languages, function application `f(x)` is simply written as `f x`. Also, this form of function application is left-associative, which means `f x y z` is `((f x) y) z`, or `((f(x))(y))(z)`.

Haskell also has a binary operator called `$`. `f $ x` does function application just like `f x`, but it is right-associative, which means you can write `f $ g $ h $ x` to mean `f(g(h(x)))`. If you used Haskell enough, you might have once wondered, "would it be nice if `f x` itself were right-associative?"

Now it's about time to see this in action. For the sake of simplicity, let's assume all the identifiers are single-character and omit the spaces entirely.

## Challenge

Given a valid expression written using left-associative function application, convert it to the minimal equivalent expression where function application is right-associative. The result must not contain any unnecessary parentheses.

An expression is defined using the following grammar:

```
expr := [a-z] | "(" expr ")" | expr expr

```

To explain this in plain English, a valid expression is a lowercase English letter, another expression wrapped in a pair of parens, or multiple expressions concatenated.

I/O can be done as a string, a list of chars, or a list of codepoints. The input is guaranteed to have minimal number of parens under left-associative system.

Standard rules apply. The shortest code in bytes wins.

## Test cases

```
input -> output
---------------
foo -> (fo)o
b(ar) -> bar
q(uu)x -> (quu)x
abcde -> (((ab)c)d)e
f(g(hx)) -> fghx
g(fx)(hy) -> (gfx)hy

```

# Answer
> 8 votes
# JavaScript, 71 bytes

*Saved 2 bytes by Arnauld.*

```
f=(e,l='',r=e.shift())=>(r=r>{}?r:r<f&&f(e))?f(e,l[1]?`(${l})`+r:l+r):l

```

Try it online!

* `l`, `r` are two operand

# Answer
> 6 votes
# Perl 5 `-p`, 73 bytes

```
1while$e='(\w|\((?1)*\))',s/$e$e(?=$e)/($&)/;1while s/\(($e*)\)(?!$e)/$1/

```

Try it online!

# Answer
> 1 votes
# Jelly, 60 bytes

```
;Ṫ$FL$¡1ĿØ(jƊ¹ŒḊ?€
=þØ(Ä_Ż}ỊṖʋ/aSƲœp⁸;2ĿW$}¥2/Ẏ3œṖW;¥2/ẎƲÐLÇ

```

Try it online!

A full program taking a string argument and printing the result to STDOUT. Uses recursion in both links, but in both cases replacing `1Ŀ` or `2Ŀ` with `ß` fails to work.

# Answer
> 1 votes
# Retina 0.8.2, 94 bytes

```
+1`((\w|(\()|(?<-3>\)))+?(?(3)^)){2}(?!\))
($&)
+`\(((\w|(\()|(?<-3>\)))+)\)(?(3)^)(?=\)|$)
$1

```

Try it online! Link includes test cases. Explanation:

```
+1`

```

Make the first possible substitution each time, looping until no more substitutions are possible. This means that in the case of `abcde`, only `ab` is surrounded the first time, then `(ab)c` the second time, et cetera.

```
((\w|(\()|(?<-3>\)))+?(?(3)^)){2}(?!\))
($&)

```

Put parentheses around any pair of expressions that does not already have one.

```
+`\(((\w|(\()|(?<-3>\)))+)\)(?(3)^)(?=\)|$)
$1

```

Remove any parentheses not needed under right association.

# Answer
> 0 votes
# Charcoal, 53 bytes

```
Ｆ⁺(Ｓ¿⁼ι(⊞υ⟦⟧«Ｆ⁼ι)≔⪫⊟υωιＦ‹¹Ｌ§υ±¹⊞υ⟦⪫()⪫⊟υω⟧⊞§υ±¹ι»⪫⊟υω

```

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

```
Ｆ⁺(Ｓ

```

Loop over the input with an extra `(` prefixed as this is golfier then setting up the stack manually.

```
¿⁼ι(⊞υ⟦⟧«

```

For each `(`, push a new empty list to the stack.

```
Ｆ⁼ι)

```

If the next character is a `)`, then...

```
≔⪫⊟υωι

```

the next term is actually the joined list at the top of the stack.

```
Ｆ‹¹Ｌ§υ±¹

```

If the list at the top of the stack already has two terms, then...

```
⊞υ⟦⪫()⪫⊟υω⟧

```

... replace it with a list of a `()` wrapped term.

```
⊞§υ±¹ι

```

Push the current term to the list at the top of the stack.

```
»⪫⊟υω

```

Join and output any remaining terms.

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


# Question
Title: A Suitable Mission — The Professor's Revenge
Summer Klerance turned in her term assignment for this **challenge**. Her professor was miffed (but also amused) when he overheard a disgruntled classmate of Summer's saying she got her answers by simulation rather than by the probabilistic methods covered in the course. Summer received a note to see the prof during his next office hours.

"OK, Miss Smarty-Pants\*, I'll admit your problem was harder than any of the others I assigned. However, I'm not ready to give you full credit...Have a seat! If we order the goals by increasing difficulty of achievement, which you already, um, "found," we have:

> The Prof's *New* Order:
>
> **1** (Any) one complete suit **\[7.7 hands\]**
> **3** (Any) two complete suits \[10.0 hands\]
> **2** One given complete suit \[11.6 hands\]
> **5** (Any) three complete suits \[12.4 hands\]
> **4** Two given complete suits \[14.0 hands\]
> **6** Three given complete suits \[15.4 hands\]
> **7** The complete deck (all four suits) **\[16.4 hands\]**

**The Challenge**:

"I'd like you to modify your program. Keep track of the number of hands needed to see each of the seven goals as you deal, just as before. Let's define one ***trial*** as being completed on the hand when you've achieved *all seven goals*, i.e. a complete deck. The *order* in which you achieved each of the seven goals during a trial *may or may not match the New Order* I've shown you. To receive full credit for you term problem, I'd like you to tack a *single number* onto your output: **the percentage of total trials in which the order of goal achievement *exactly* matches the New Order**. And let's change our sample from 1 million deals to **20,000 trials** to ensure there is no partial trial at the end."

**Input:** None

**Output**: Same format as the original challenge with two changes: (a) the addition of the new percentage at the end of the output, and (b) a program run of exactly 20,000 trials, instead of the 1 million deals in the previous challenge.

**Rules** (revised):

(1) The results for the seven goals should be output in the **Old** Order (1-7) and not the New Order above. However, the percentage of interest is based on the **New Order** above, that of strictly increasing difficulty of achievement.

(2) Runs are no longer based on 1 million deals, but rather **20,000 completed trials** (roughly 330,000 deals).

(3) A tie resulting from achieving two or more goals on the same deal counts as a Yes, since it (also) fulfills the New Order requirement.

(4) The new number should come at the end of the output and needn't have a % sign.

(5) Show the result of *three* program runs, as in the original challenge. The data requested for each of the seven goals remains analogous to the original challenge: goal number; average number of hands needed in the 20,000 trials (rounded to one decimal place); minimum number of hands needed; and the maximum number of hands needed. The newly requested percentage should be at the end of the output.

(6) Code golf, so shortest ~~club~~ code in bytes wins.

---

\*He didn't actually say that, but it was what he was thinking.

# Answer
> 2 votes
# Jelly, ~~96~~ 78 bytes

```
%4‘ċⱮ4=13ḣḞƑ}¡S<
⁸;52Ẋḣ13¤Q$ç4$Ð¿çþ7H€¤§µ“Þ2ị’D¤ịṢƑ×³;@
2ȷ5¢€ZµÆmær1;Ṃ;Ṁ)µṪḢṭĖ

```

Try it online!

A full program which is called as with no arguments and returns a list of lists of numbers. Each goal is represented in order as `[goal number, [mean, min, max]]` while the eighth list member is the percentage of trials matching the specified order. This is an extension of my previous Jelly answer to the first part. The TIO link runs three lots of 500 (5E2) trials rather than 20,000 (2E5).

# Answer
> 0 votes
# Charcoal, 170 bytes

```
≔Ｅ⁷⟦⟧εＦ×²⁰φ«≔Ｅε⁰ζ≔⁰δ≔⁰ηＷ№ζ⁰«≔⟦⟧θＦ¹³⊞θ‽⁻Ｅ⁵²μθ≧｜ΣＸ²θη≦⊕δ≔↨⁻⊖Ｘ²¦⁵³η⁸¹⁹²θＦΦ⁷‹§ζλ⎇﹪λ²⁼¹Σ…θ⊘⁺³λ›⊗№θ⁰λ§≔ζλδ»Ｆ⁷⊞§εκ§ζκ⊞υ∧¬⊙241536‹§ζＩκ§ζλ¹⁰⁰»Ｅε⪫⟦⊕κ⟦∕÷⁺×χΣι⊘ＬιＬιχ⌊ι⌈ι⟧⟧ ﹪%.1f∕ΣυＬυ

```

Try it online! Link is to verbose version of code. Note: TIO link limited to 200 trials as 20,000 is too slow. +1 byte if you want to output a `%` sign. Explanation:

```
≔Ｅ⁷⟦⟧ε

```

Start with an array of 7 empty lists of counts needed to reach the goal.

```
Ｆ×²⁰φ«

```

Loop 20,000 times.

```
≔Ｅε⁰ζ

```

Start with no goals found yet.

```
≔⁰δ

```

Start with no deals yet.

```
≔⁰η

```

Start with no cards yet.

```
Ｗ№ζ⁰«

```

Repeat until all goals have been found.

```
≔⟦⟧θＦ¹³⊞θ‽⁻Ｅ⁵²μθ

```

Deal 13 different cards at random.

```
≧｜ΣＸ²θη

```

Convert the cards into a bitmask and mark them as having been seen for this trial.

```
≦⊕δ

```

Increment the count for each trial.

```
≔↨⁻⊖Ｘ²¦⁵³η⁸¹⁹²θ

```

Find the suits for which all of the cards have now been seen.

```
ＦΦ⁷‹§ζλ⎇﹪λ²⁼¹Σ…θ⊘⁺³λ›⊗№θ⁰λ§≔ζλδ»

```

For each goal, mark it as satisfied if it is now but wasn't before. The flag is actually the count of deals for this trial so far.

```
Ｆ⁷⊞§εκ§ζκ

```

Push the counts to the lists.

```
⊞υ∧¬⊙241536‹§ζＩκ§ζλ¹⁰⁰»

```

Also keep track of whether this trial's results are in the desired order.

```
Ｅε⪫⟦⊕κ⟦∕÷⁺×χΣι⊘ＬιＬιχ⌊ι⌈ι⟧⟧

```

Format the averages as desired.

```
﹪%.1f∕ΣυＬυ

```

Format the percentage of trials in the desired order. Sample outputs (from TIO):

```
1 [7.6, 5, 14]  [7.8, 4, 16]  [7.8, 4, 14]
2 [11.8, 6, 27] [11.9, 5, 33] [12.3, 5, 34]
3 [10.1, 6, 16] [10.0, 6, 17] [10.0, 6, 16]
4 [14.0, 8, 31] [14.4, 6, 33] [14.0, 7, 34]
5 [12.2, 8, 21] [12.6, 7, 22] [12.7, 7, 21]
6 [15.0, 8, 31] [16.1, 9, 35] [15.4, 7, 37]
7 [16.0, 8, 31] [17.2, 9, 35] [16.3, 9, 37]
  53.0          48.0          51.0

```

---
Tags: code-golf, probability-theory, simulation
---


title: Park, Lake, Santa Fe

text:
# Question
Title: Park, Lake, Santa Fe
Given a long multi-sentence string, the goal is the count the occurrences of the following words: `park`, `lake`, `Santa Fe`.

The words can appear as substrings of other words, i.e, `parked` counts as an instance of `park`.

`Santa Fe` counts as one word (so the space matters). Both `Santa` and `Fe` appearing alone or out of order does **not** count as an instance of `Santa Fe`.

The output should be counts of the number of times the words `park`, `lake`, and `Santa Fe` appear in the input string, in any consistent and readable format and order.

For example, for an input of

```
I'm just parked out by the lake; the lake 80 miles from Santa Fe. That's where i'm parked, out by the lake.

```

the output would resemble

```
2 3 1

```

as there are \\$2\\$ occurrences of `park`, \\$3\\$ of `lake` and \\$1\\$ of `Santa Fe`.

Good luck! If you want a fun song to test this on you can use the lyrics to Parked by the lake - Dean Summerwind (below) and use it as the input; The output ought to be `20 24 14`.

Winning submission is the least number of bytes.

---

Lyrics to Parked by the Lake

# Answer
> 5 votes
# 05AB1E, 14 bytes

```
„†¹Š°#„š´º´™ª¢

```

Try it online!

```
„†¹Š°            -- compressed string  => "park lake"
     #           -- split on spaces    => ["park", "lake"]
      „š´º´      -- compressed string  => "santa fe"
           ™     -- title cased        => "Santa Fe"
            ª    -- append to the list => ["park", "lake", "Santa Fe"]
             ¢   -- for each word, count the number of occurences in the input

```

# Answer
> 7 votes
# , 36 30 bytes

```
1#.('Santa Fe';park`lake)E.&><

```

Try it online!

*-5 thanks to Bubbler!*

Returns count in order "Santa Fe", "park", "lake".

* `E.` Does all the matching work, returning three rows of ones and zeros, where ones represent the start of each match.
* `1#.` Sums row-wise.

# Answer
> 6 votes
# Python 2, 48 bytes

```
lambda k:map(k.count,["park","lake","Santa Fe"])

```

Try it online!

-7 bytes thanks to tsh

# Answer
> 5 votes
# Jelly, ~~19~~ 17 bytes

```
ẆċⱮ“£Ḟœ“ċẈ“¡ç1Ḋı»

```

Try it online!

-2 bytes thanks to Nick Kennedy

## How it works

```
ẆċⱮ“£Ḟœ“ċẈ“¡ç1Ḋı» - Main link. Takes a string S on the left
Ẇ                 - Yield all contiguous sublists of S
   “£Ḟœ“ċẈ“¡ç1Ḋı» - Compressed string list; ["park", "lake", "Santa Fe"]
  Ɱ               - Over each string:
 ċ                -   Count the occurrences in the sublists

```

# Answer
> 5 votes
# Vyxal `r`, 16 bytes

```
`⟇æ
»¥
ʁ∨ Fe`↵vO

```

Try it Online!

## Explained

```
`...`↵vo
`...`      # the string "park\nlake\Santa Fe"
     ↵     # split on newlines to form a list
      vo   # for each in that list, get the count in the input

```

# Answer
> 5 votes
# Factor, 58 bytes

```
[ { "park" "lake" "Santa Fe" } [ count-subseq ] with map ]

```

`count-subseq`:

* Doesn't exist in build 1525 (the one TIO uses).
* Has stack effect `( subseq seq -- n )` in every build that permits the omission of whitespace after strings.
* Has stack effect `( seq subseq -- n )` in the current build, which means we don't need an extra `swap`.

Therefore, the code retains the whitespace after strings but it's still shorter than the alternatives. Also, have a picture.

# Answer
> 5 votes
# C (gcc), ~~124~~ \\$\cdots\\$ ~~106~~ 103 bytes

```
*f(int*s){int c[3]={},i;for(;*s;++s)for(i=3;i--;)c[i]+=!wcsncmp(s,L"parklakeSanta Fe"+i*4,4<<i/2);s=c;}

```

Try it online!

Saved ~~a~~ 2 bytes and fixed a bug thanks to ceilingcat!!!

Inputs a string.
Return a pointer to an array of occurrence counts for `park`, `lake`, and `Sante Fe`.

# Answer
> 4 votes
# Brachylog, 33 bytes

```
g;"park
lake
Santa Fe"ṇᵗz{{sᵈ}ᶜ}ᵐ

```

Try it online!

I'm not sure if this feels very golfable, or not even remotely golfable... `⟨s≡⟩ᶜ` happens to tie `{sᵈ}ᶜ`, so maybe there's some shenanigan to pull there, but that seems doubtful.

```
g;                    Wrap the input in a list, and pair it with
  "..."               "park\nlake\nSanta Fe"
       ṇᵗ             split on newlines.
         z            Cycling zip.
          {     }ᵐ    For each pair [input, park/lake/Santa Fe]:
           {  }ᶜ      in how many ways
            sᵈ        is park/lake/Santa Fe a substring of the input?

```

# Answer
> 4 votes
# Bash, 59 51 bytes

```
grep -Eo 'park|lake|Santa Fe'|sort|uniq -c|awk NF=1

```

Try it online!

*-8 bytes thanks to user41805's nice awk trick!*

Returns in order "lake", "park", "Santa Fe".

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

```
s=>["park","lake","Santa Fe"].map(w=>s.split(w).length-1)

```

Try it online!

```
s=>[(g=w=>s.split(w).length-1)`park`,g`lake`,g`Santa Fe`]

```

Try it online!

# Answer
> 3 votes
# Japt, 21 bytes

```
`pk
lake
SÂ Fe`·£èX

```

Try it

# Answer
> 2 votes
# Ruby, 49 bytes

```
p %w[park lake Santa\ Fe].map{|r|$_.scan(r).size}

```

Try it online!

# Answer
> 2 votes
# WolframLanguage (Mathematica), 50 bytes

```
(f|->f~StringCount~#&/@{"park","lake","Santa Fe"})

```

The above won't work in tio.run because |-\> is too new (introduced in MMA v. 12.2, while tio.run uses MMA 12.0).

Thus here's a 51-byte version that does:

```
(f=#;f~StringCount~#&/@{"park","lake","Santa Fe"})&

```

Try it online!

# Answer
> 2 votes
# Clojure, 55 bytes

```
#(for[r[#"park"#"lake"#"Santa Fe"]](count(re-seq r %)))

```

Try it online!

# Answer
> 2 votes
# PHP, 73 bytes

```
foreach([park,lake,'Santa Fe']as$r)echo~-count(explode($r,$argv[1])).' ';

```

Try it online!

# Answer
> 2 votes
# PHP -F, ~~71~~ ~~66~~ 65 bytes

```
foreach([park,lake,"Santa Fe"]as$w)echo~_.substr_count($argn,$w);

```

Try it online!

Just using dedicated function and usual tricks..

EDIT: 5 bytes saved using a `foreach` like in Guillermo Phillips's answer

EDIT 2: another byte the dust thanks to Guillermo Phillips again!

# Answer
> 2 votes
# K (ngn/k), 39 bytes

```
{+/`park`lake`"Santa Fe"=/:`$(4'x),8'x}

```

Try it online!

* `(4'x),8'x` build a list containing all 4-length sliding windows, and all 8-length sliding windows, of the input
* ``$` convert the slices from strings to symbols
* ``park`lake`"Santa Fe"=/:` build a matrix with each of its three columns indicating whether or not each slice of the input is equal to one of the search terms
* `+/` sum column-wise, returning the number of times `park`, `lake`, and `Santa Fe` appear in the input (respectively)

# Answer
> 2 votes
# Perl 5, 44 bytes

```
for$w("park","lake","Santa Fe"){say s/$w//g}

```

Try it online!

# Answer
> 1 votes
# Zsh, 45 bytes

```
for x (park lake Santa\ Fe)grep -o $x F|wc -l
```

Attempt This Online!

# Answer
> 1 votes
# Excel, 63 bytes

```
Cells A3:C3 = park, lake, Santa Fe (16 bytes)
=(LEN(A1)-LEN(SUBSTITUTE(A1,A3:C3,"")))/{4,4,8}  (47 bytes)

```

Link to Spreadsheet

The easiest way to count occurrences of a substring is to substitute the substring with "" and then divide the difference in length by the length of the substring.

## Self contained formula, 68 bytes

```
=(LEN(A1)-LEN(SUBSTITUTE(A1,{"park","lake","Santa Fe"},"")))/{4,4,8}

```

# Answer
> 1 votes
# Retina 0.8.2, 24 bytes

```
*M`park
*M`lake
Santa Fe

```

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

```
*M`park

```

Explicitly print the count of matches of the word `park` without changing the input buffer.

```
*M`lake

```

Explicitly print the count of matches of the word `lake` without changing the input buffer.

```
Santa Fe

```

Count the matches and implicitly print the result.

# Answer
> 1 votes
# Charcoal, 24 bytes

```
ＩＥ⪪”&/‽∕“⎇⊙g…3ＣπΦＰ6”¶№θι

```

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

```
   ”...”        Compressed string `park\nlake\Santa Fe`
  ⪪     ¶       Split on newlines
 Ｅ              Map over each substring
         №      Count of
           ι    Current substring
          θ     In original input
Ｉ               Cast to string
                Implicitly print

```

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


# Question
Title: Potential nonzero entries in an irregular sequence
## Background

**A338268** is a sequence related to a challenge by Peter Kagey. It defines a two-parameter function \\$T(n,k)\\$, which counts the number of integer sequences \\$b\_1, \cdots, b\_t\\$ where \\$b\_1 + \cdots + b\_t = n\\$ and \\$\sqrt{b\_1 + \sqrt{b\_2 + \cdots + \sqrt{b\_t}}} = k\\$. Since \\$k\\$ cannot be larger than \\$\sqrt{n}\\$, the relevant "grid" has an odd shape:

```
  n\k| 1  2 3 4
  ---+---------
   1 | 1
   2 | 0
   3 | 0
   4 | 0  2
   5 | 0  0
   6 | 0  2
   7 | 0  0
   8 | 0  2
   9 | 0  0 2
  10 | 0  4 0
  11 | 0  0 2
  12 | 0  6 0
  13 | 0  0 2
  14 | 0  8 0
  15 | 0  0 4
  16 | 0 12 0 2

```

More precisely, \\$n\\$-th row is limited to \\$1 \le k \le \lfloor \sqrt{n} \rfloor\\$.

Furthermore, this part of the grid has many known zero entries, as written in the OEIS page:

* \\$ T(n,1) = 0 \\$ for \\$n \> 1\\$.
* \\$ T(n,k) = 0 \\$ if \\$n + k\\$ is odd, i.e. \\$n\\$ and \\$k\\$ have a different parity.

In this challenge, **potential nonzero entries** means the terms whose \\$(n,k)\\$ pair satisfies none of the above, i.e. \\$n+k\\$ is even, and either \\$n \> 1\\$ or \\$(n,k) = (1,1)\\$.

Also, every sequence on the OEIS must be linearly laid out, so the numbers are "read by rows" as follows:

```
1, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 2, 0, 4, 0, 0, 0, 2, 0, 6, 0,
0, 0, 2, 0, 8, 0, 0, 0, 4, 0, 12, 0, 2, ...

```

In this sequence, the potential nonzero entries are at the following indices:

```
1-based: 1, 5, 9, 13, 16, 18, 22, 24, 28, 30, 34, 36, 38, ...
0-based: 0, 4, 8, 12, 15, 17, 21, 23, 27, 29, 33, 35, 37, ...

```

## Challenge

Output the 1-based or 0-based version of the sequence above.

I/O methods apply. You may use one of the following I/O methods:

* Take no input and output the sequence indefinitely,
* Take a (0- or 1-based) index \\$i\\$ and output the \\$i\\$-th term, or
* Take a non-negative integer \\$i\\$ and output the first \\$i\\$ terms.

Standard rules apply. The shortest code in bytes wins.

# Answer
# Python 3, 67 bytes

Prints the 0-based sequence forever.

```
d=n=k=0
while 1:k+=1;k**=k*k<=n;n+=k<2;k+n&1<(k>1%n)!=print(d);d+=1

```

Try it online!

**Commented**:

```
d=n=k=0
while 1:
  k+=1                      # increment k
  k**=k*k<=n                # k=k**1=k if k*k<=n, else k=k**0=1
  n+=k<2                    # increment n if k is equal to 1
  k+n&1<(k>1%n)!=print(d)   # print index d if k+n&1==0 (same parity) and k>1%n (k>0 for n==1 and k>1 for n>1)
  d+=1                      # increment the index

```

Try it online!
> 4 votes

# Answer
# ARM T32 machine code, 34 bytes

```
b510 0001 d00c 2001 2204 3204 2302 3302
3001 001c 4364 1b14 d4f7 07a4 41a1 d1f6
bd10

```

Following the AAPCS, this takes a 0-based index in r0 and returns the 0-based entry at that index in r0.

Assembly:

```
.section .text
.syntax unified
.global sequence
.thumb_func
sequence:
    push {r4, lr}     @ Save r4 and lr to the stack
    movs r1, r0       @ Copy the index to r1
    beq end           @ Special case: 0 -> 0; return immediately
    movs r0, #1       @ Counter of grid entries processed, initialised to 1
    movs r2, #4       @ r2 holds 4*n, for reasons to be seen later
nextrow:
    adds r2, #4       @ Advance to the next row: r2 is increased by 4...
    movs r3, #2       @ and r3, which holds 2*k, is set to 2.
nextcol:              @ With r3 being advanced immediately, this will skip k=1.
    adds r3, #2       @ Increase r3 by 2 (increase k by 1)
    adds r0, #1       @ Increment the counter
    movs r4, r3       @ Duplicate the value of 2*k...
    muls r4, r4, r4   @ square it, yielding 4*k^2...
    subs r4, r2, r4   @ and subtract the square from 4*n.
    bmi nextrow       @ If that's negative, the row is over;
      @ the counter has already been incremented, counting for the k=1 entry in the next row.
    lsls r4, r4, #30  @ The criterion is the parity of n+k, which is the same as that of n-k^2,
      @ and hence bit #2 of 4*n-4*k^2. Shifting it 30 places left puts that bit in the carry flag,
      @ and leaves r4 with a value of 0. (This is why the rescaling is needed: LSL 32 is invalid.)
    sbcs r1, r4       @ Subtract from r1 the value of r4 (0) plus the inverted carry flag.
                      @ This counts down the number of potential nonzero entries needed.
    bne nextcol       @ If it hasn't reached 0 yet, repeat.
end:
    pop {r4, pc}      @ Restore the value of r4 from the stack and return.

```
> 4 votes

# Answer
# Jelly, 18 bytes

```
²‘½€RḂ¬ÐeḊŻ$€FT1;ḣ

```

Try it online!

A monadic link taking an integer \\$n\\$ and returning the first \\$n\\$ terms of the sequence.
> 1 votes

# Answer
# 05AB1E, 19 bytes

Prints an infinite list of the 1-based sequence.

```
∞ε©tLε®+Éy®≠›‹]˜ƶ0K

```

Try it online!

```
∞ε            ]        # for n in [1, 2, ...]:
  ©                    #   store n in the register
   tL                  #   range from 1 to sqrt(n)
     ε        ]        #   for k in this range:
      ®+É              #     is n+k odd?
         y®≠›          #     k > (n!=1)
             ‹         #     (n+k odd) < (k > (n!=1))
              ]        # close all loops
               ˜       # flatten the result into a single list
                ƶ0K    # indices of 1's: multiply by index, remove 0's

```

---

A more literal port of my python answer is one byte longer:

```
[>Dn¾›i¼1}Ð¾+És¾≠›‹–

```

Try it online!

```
                       # d is the iteration index
                       # n is the counter variable
                       # k is on top of the stack
[                      # infinite loop, iteration index starts at 0
 >                     # increment k
  Dn¾›i  }             # if k**2 > n
       ¼1              # increment n and reset k to 1
          Ð            # push two copies of k
           ¾+É         # is n+k odd?
              s¾≠›     # is k > (n!=1)
                  ‹    # (n+k odd?) < (k > (n!=1))
                   –   # if this is true, print the current iteration index

```
> 1 votes

# Answer
# Jelly, 15 bytes

```
Ḥ½ḶoƊ€ḊŻĖS€ḂFTḣ

```

A monadic Link accepting \\$i\\$ which yields a list of the first \\$i\\$ terms.

**Try it online!**

### How?

```
Ḥ½ḶoƊ€ḊŻĖS€ḂFTḣ - Link: positive integer, i
Ḥ               - double -> 2i
     €          - for each (x in [1..2i]):
    Ɗ           -   last three links as a monad, f(x):
 ½              -     square root (x) -> r
  Ḷ             -     lowered range -> [0,1,2,3,4,...,floor(r)-1]
   o            -     logical OR -> [x,1,2,3,4,...,floor(r)-1]
      Ḋ         - dequeue (drops the leading [1] from that list of lists)
       Ż        - prepend a zero
        Ė       - enumerate -> [[1,0],[2,[2]],[3,[3]],[4,[4,1]],...,[9,[9,1,2]],...,[16,[16,1,2,3]],...]
         S€     - sum each -> [[1,[4],[6],[8,5]...[18,10,11],...[32,17,18,19],...]
           Ḃ    - mod 2 -> [[1,[0],[0],[0,1],...,[0,0,1],...,[0,1,0,1],...]
            F   - flatten
             T  - truthy indices (1-indexed)
              ḣ - head to index (i)

```
> 1 votes

---
Tags: code-golf, math, sequence, integer
---


title: Group binary shapes together

text:
# Question
Title: Group binary shapes together
Consider the following binary matrix:

$$\begin{matrix} 1 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 1 \end{matrix}$$

The (1-indexed) co-ordinates of the \\$1\\$s here are \\$(1,1), (1,3), (2,1), (3, 2), (3, 3)\\$. We can also notice that there are three "shapes" of \\$1\\$s in the matrix, made of orthogonally connected \\$1\\$s:

$$\begin{matrix} \color{red}{1} & 0 & \color{cyan}{1} \\ \color{red}{1} & 0 & 0 \\ 0 & \color{blue}{1} & \color{blue}{1} \end{matrix}$$

We can then group the coordinates into those shapes: \\$((1, 1), (2, 1)), ((3, 2), (3, 3)), ((1,3))\\$.

Given a non-empty list of coordinates, group them into the shapes that can be found in the binary matrix represented by those coordinates. You may take the input as any reasonable format for a list of pairs, including complex numbers. You may also choose to use 0 or 1 indexing.

You may also instead choose to take the binary matrix as input, rather than the coordinates. In this case, the output should still be the groups.

The output may be any format where the groups (lists of pairs) are clearly recognisable, as are the pairs themselves. One example may be newline delimited lists of complex numbers. You may also output the groups as lists of indices (0 or 1 indexed, your choice) from the original input (so the example would be `[[1,3], [4,5], [2]]`)

This is , so the shortest code in bytes wins.

## Test cases

I've used `(a, b)` for the output to try to show some distinction

```
input ->
output
lines

[[1, 2], [2, 1], [2, 3], [3, 2]] ->
[(1, 2)]
[(2, 1)]
[(2, 3)]
[(3, 2)]

[[1, 1], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2], [3, 3]] ->
[(1, 1), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2), (3, 3)]

[[1, 1], [1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2], [3, 3]] ->
[(1, 1), (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2), (3, 3)]

[[1, 3], [1, 4], [3, 1], [3, 2], [5, 2]] ->
[(1, 3), (1, 4)]
[(3, 1), (3, 2)]
[(5, 2)]

[[1, 3], [3, 1], [3, 2], [4, 2], [5, 2], [5, 3]] ->
[(1, 3)]
[(3, 1), (3, 2), (4, 2), (5, 2), (5, 3)]

[[2, 2]] ->
[(2, 2)]

[[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [2, 4], [3, 1], [4, 1], [4, 3], [4, 4], [4, 5], [5, 1], [5, 4], [5, 5], [6, 4], [6, 5]] ->
[(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 4)]
[(3, 1), (4, 1), (5, 1)]
[(4, 3), (4, 4), (4, 5), (5, 4), (5, 5), (6, 4), (6, 5)]

[[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [2, 1], [3, 1], [3, 2], [3, 3], [3, 4], [3, 5], [4, 5], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5], [5, 6]] ->
[(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 1), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (4, 5), (5, 1), (5, 2), (5, 3), (5, 4), (5, 5), (5, 6)]

[[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [2, 5], [3, 1], [3, 4], [4, 1], [4, 2], [4, 4], [4, 5], [4, 6], [5, 1], [5, 4], [5, 5], [6, 1], [6, 4], [6, 5]] ->
[(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 5)]
[(3, 1), (4, 1), (4, 2), (5, 1), (6, 1)]
[(3, 4), (4, 4), (4, 5), (4, 6), (5, 4), (5, 5), (6, 4), (6, 5)]

```

And this is a visualisation of the matrices themselves

# Answer
# APL (Dyalog Unicode), 18 bytes

Full program. Takes input as list of complex numbers. Returns list of lists of indices into the input.

```
⍸¨↓∪∨.∧⍣≡⍨1≥|∘.-⍨⎕

```

Try it online!

prompt for evaluated input via stdin

`∘.-⍨` differences between all pairs of indices

`|` absolute value

`1≥` Boolean matrix indicating where no more than 1 (points have 0 distance from themselves)

`∨.∧⍣≡⍨` transitive closure

unique rows

split into list of lists

`⍸¨` indices where true in each
> 7 votes

# Answer
# , 24 bytes

```
</.~[:+./ .*^:_~1>:|@-/~

```

Try it online!

Very similar approach to Adam's APL answer, though arrived at independently. Input as complex numbers:

* `|@-/~` Table of absolute differences.
* `1>:` Is it elementwise less than or equal to 1? Returns a 0-1 matrix representing direct neighbors.
* `[:+./ .*^:_` Do a matrix multiply replacing sum with boolean OR until a fixed point. The rows now represent connected groups.
* `</.~` Use those groups to group the original input.
> 5 votes

# Answer
# Jelly, 9 bytes

```
ạþ`Ịæ*LṠĠ

```

Try it online!

### How it works

```
ạþ`Ịæ*LṠĠ    Monadic link. Input: list of coordinates in complex
ạþ`          Table of absolute differences
   Ị         <= 1
    æ*L      Raise the matrix to the power equal to length
       Ṡ     Sign (mat[i][j] == 1 if a path exists between i and j)
        Ġ    Group indices by identical rows of the matrix

```
> 5 votes

# Answer
# Wolfram Language (Mathematica), 61 bytes

```
Xor@@List/@#//.a_⊻b_/;Min@DistanceMatrix[a,b]==1:>a~Join~b&

```

Try it online!

Returns an `Xor` of coordinate lists, unless there is only one group, in which case just a single coordinate lists is returned (since `Xor[something]==something`). Repeatedly concatenates adjacent groups. Runtime balloons quickly.

### Also 61 bytes

```
Thread[Sign@MatrixExp@Ramp[1.1-DistanceMatrix@#]->#]~Merge~D&

```

Try it online!

Returns an association with coordinate lists as its values. Same approach as several other answers: build an adjacency matrix by zeroing entries of a distance matrix that are greater than 1, take the closure, group.

---

Alternate approach with a built-in that performs most of the task: **63 bytes**

```
ConnectedComponents@Subgraph[##&@@Table[#->#+I^i,{i,4}]&/@#,#]&

```

Try it online! Input a list of complex numbers. Returns a list of complex number lists. With `ConnectedComponents`, all that remains is building the adjacency graph.
> 2 votes

# Answer
# Charcoal, ~~91~~ 81 bytes

```
≔Ｅ²⊕⌈Ｅθ§λιηＥ§η¹⭆§η⁰℅¬№θ⟦λι⟧≔²ζＦ⊟ηＦΣη«Ｊκι¿¬℅ＫＫ«¤℅ζ≦⊕ζ»»Ｆ…²ζ⊞υ⌕ＡＫＡ℅ι⎚ＩＥυＥι⟦﹪λΣη÷λΣη

```

Try it online! Link is to verbose version of code. Output is a triple-spaced list of double-spaced list of pairs of coordinates, each on their own line. Explanation:

```
≔Ｅ²⊕⌈Ｅθ§λιη

```

Find the size of the matrix.

```
Ｅ§η¹⭆§η⁰℅¬№θ⟦λι⟧

```

Create an area of that size on the canvas with holes at all of the points provided.

```
≔²ζ

```

Start tracking the next shape.

```
Ｆ⊟ηＦΣη«

```

Loop through the matrix.

```
Ｊκι¿¬℅ＫＫ«

```

If there is a hole at this position, then...

```
¤℅ζ≦⊕ζ»»

```

... fill it in and increment the shape tracker.

```
Ｆ…²ζ

```

Loop through the found shapes.

```
⊞υ⌕ＡＫＡ℅ι

```

Get the flattened list of coordinates of each shape.

```
⎚ＩＥυＥι⟦﹪λΣη÷λΣη

```

Clear the canvas and convert the coordinates back to pairs.
> 2 votes

# Answer
# JavaScript, 103 bytes

```
a=>new Set(a.map(p=>a[r=a.reduce(b=>a.filter(q=>b.some(([x,y])=>(x-=q[0])*x+(y-=q[1])*y<2)),[p])]??=r))

```

```
f=

a=>new Set(a.map(p=>a[r=a.reduce(b=>a.filter(q=>b.some(([x,y])=>(x-=q[0])*x+(y-=q[1])*y<2)),[p])]??=r))

console.log(JSON.stringify([...f([[1, 2], [2, 1], [2, 3], [3, 2]])]));
console.log(JSON.stringify([...f([[1, 1], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2], [3, 3]])]));
console.log(JSON.stringify([...f([[1, 1], [1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2], [3, 3]])]));
console.log(JSON.stringify([...f([[1, 3], [1, 4], [3, 1], [3, 2], [5, 2]])]));
console.log(JSON.stringify([...f([[1, 3], [3, 1], [3, 2], [4, 2], [5, 2], [5, 3]])]));
console.log(JSON.stringify([...f([[2, 2]])]));
console.log(JSON.stringify([...f([[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [2, 4], [3, 1], [4, 1], [4, 3], [4, 4], [4, 5], [5, 1], [5, 4], [5, 5], [6, 4], [6, 5]])]));
console.log(JSON.stringify([...f([[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [2, 1], [3, 1], [3, 2], [3, 3], [3, 4], [3, 5], [4, 5], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5], [5, 6]])]));
console.log(JSON.stringify([...f([[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [2, 5], [3, 1], [3, 4], [4, 1], [4, 2], [4, 4], [4, 5], [4, 6], [5, 1], [5, 4], [5, 5], [6, 1], [6, 4], [6, 5]])]));
```

Input `Array<[number, number]>`. Output `Set<Array<[number, number]>>`.

18 bytes are used to remove duplicate groups, maybe someone may find out a better way to golf it down.

---

# Python 2, 100 bytes

```
lambda a:set(tuple(reduce(lambda b,_:[P for P in a if any(abs(P-Q)<=1for Q in b)],a,[p]))for p in a)

```

Try it online!

Input `List[complex]`. Output `Set[Tuple[complex, ...]]`.

Try to port above JavaScript codes to Python results 100 bytes.
> 1 votes

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


# Question
Title: Will Alice win in this Stick Bomber game?
## Background

**Stick Bomber** is a two-player game I just made up. Initially, some sticks are placed in one or more groups, and the sticks in each group are laid out in a straight line. So a configuration with three groups of 3, 5, and 8 sticks each may look like the following. For conciseness, we can call it a `(3,5,8)` configuration.

```
|||  |||||  ||||||||

```

Let's call the two players Alice (the one who plays first) and Bob (second). At each turn, the player selects one stick anywhere on the board, and removes that stick along with the ones directly adjacent to it (left or right within the group).

For example, if Alice chooses the 3rd stick in the 5-stick group, the board becomes `(3,1,1,8)` (sticks removed in the middle split the group into two):

```
|||  |xXx|  ||||||||

```

Then, if Bob chooses the first stick in the 8-stick group, the board becomes `(3,1,1,6)`:

```
|||  |  |  Xx||||||

```

Then if Alice chooses the 2nd stick in the 3-stick group, that group is entirely removed and the state becomes `(1,1,6)`:

```
xXx  |  |  ||||||

```

The one who eliminates all the sticks from the board wins the game.

For single-pile initial states, Alice can win in 1 turn for `(1)` through `(3)`, and `(5)` in three turns by removing the middle. However, Alice cannot win for `(4)` because any move will result in a `(1)` or `(2)`, where Bob can win in 1 turn.

## Challenge

Given an initial configuration of Stick Bomber, determine whether Alice can win the game. Assume that both Alice and Bob play perfectly, i.e. each player always plays a winning move whenever possible.

The input is guaranteed to be a non-empty sequence of positive integers, but it is not guaranteed to be sorted. For output, you can choose to

1. output truthy/falsy using your language's convention (swapping is allowed), or
2. use two distinct, fixed values to represent true (affirmative) or false (negative) respectively.

Standard rules apply. The shortest code in bytes wins.

## Test cases

**Single-group configurations**

For `n < 70`, Alice wins for `(n)` unless `n` is one of the following. This result was generated using this Python code. This sequence and its inversion (the list of `n`'s where Alice wins) are not yet part of the OEIS.

```
4, 8, 14, 20, 24, 28, 34, 38, 42, 54, 58, 62

```

**Multi-group truthy**

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

```

**Multi-group falsy**

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

```

# Answer
> 3 votes
# JavaScript (Node.js), ~~110~~ ~~101~~ ~~99~~ 90 bytes

*Thanks to @tsh for -9 bytes!*

```
g=s=>s.some((a,i)=>!a&&!g(t=[...s],t.splice(i-1,3,1)))
i=>g(i.flatMap(n=>[1,...Array(n)]))

```

Try it online! (with test cases)

# Answer
> 3 votes
# Python 2, 84 bytes

```
f=lambda a:0in[f(a[:i]+[v-1,x-v-2]+a[i+1:])for i,x in enumerate(a)for v in range(x)]

```

Try it online!

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

```
ḟⱮ’r‘Ɗß€Ạ¬
Rj0TÇ

```

Try it online!

Slow as hell.

### Explanation

```
Rj0TÇ    Main link.
             [1, 3, 5]
R          For each n in the array, create an array of n sticks.
             [[1], [1, 2, 3], [1, 2, 3, 4, 5]]
 j0        Join by 0 (non-sticks).
             [1, 0, 1, 2, 3, 0, 1, 2, 3, 4, 5]
   T       Indices of truthy values (sticks).
             [1, 3, 4, 5, 7, 8, 9, 10, 11]
    Ç      Call the helper link.

ḟⱮ’r‘Ɗß€Ạ¬    Helper link.
 Ɱ     €        For each stick n in the array:
  ’               n-1
    ‘             n+1
   r              Inclusive range [n-1,n,n+1]
ḟ                 Remove those three sticks if present
      ß           Call this link recursively on the remainder
        Ạ       See if there is nothing or only 1's in the list
                (i.e. if the opponent won before this turn, or can
                force a victory whatever we do)
         ¬      Invert to see if we can force a victory from here

```

# Answer
> 0 votes
# JavaScript, 72 bytes

```
f=a=>a.some(g=(v,i,a)=>v-->0&&!f(b=[...a,v-1,a[i]-v-2],b[i]=0)+g(v,i,a))

```

Try it online!

A port of current Python answer by dingledooper.

# Answer
> 0 votes
# Charcoal, 63 bytes

```
⊞υ⮌⌕Ａ⪫ＸχＡω0ＦυＦι⊞υ⁻ι…·⊖κ⊕κ≔⟦⟧ζＷ⁻υＥζ§κ⁰⊞ζ⟦⌊ι⊙⌊ι№ζ⟦⁻⌊ι…·⊖κ⊕κ⁰⟧⟧⊟⊟ζ

```

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

```
⊞υ⮌⌕Ａ⪫ＸχＡω0

```

Start enumerating all positions reachable from the starting position, which is calculated by taking `10` to the power of the input groups, concatenating the result, and taking the indices of the `0`s from highest to lowest (i.e. reverse of the usual order).

```
ＦυＦι⊞υ⁻ι…·⊖κ⊕κ

```

For each position and stick, calculate the result of bombing that stick and add the result to the list of reachable positions.

```
≔⟦⟧ζＷ⁻υＥζ§κ⁰

```

Enumerate the list of reachable positions in ascending order, so that all positions reachable from a given position have been enumerated before that position. Additionally, the enumeration deduplicates the positions.

```
⊞ζ⟦⌊ι⊙⌊ι№ζ⟦⁻⌊ι…·⊖κ⊕κ⁰⟧⟧

```

For each position, check whether any play results in a losing position. Push that position plus the win flag to the enumeration.

```
⊟⊟ζ

```

Output the win flag for the original position.

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


title: The knight's next tour

text:
# Question
Title: The knight's next tour
We've all heard of the Knight's Tour puzzle: find a route for a knight that passes through all the squares on a chess board. But let's be honest, it's a little bit boring. So, let's give the knight a bit of a challenge.

## Task

Write a program that takes the knight through all the squares on an arbitrary-sized, arbitrary-shaped chess board. It should take the chess board as input and output the set of moves and the starting position. In the event of an impossible board, it should output the set of moves and starting position for a tour with the longest possible length. Note: the knight doesn't need to take a round trip; assume they have another way to get home.

Chess pieces are small, so your code needs to be small enough for the knight to carry around.

## Input

The input will be a string-based or array-based representation of a chess board, where a non-blank / truthy value is a square, and a blank / falsy value is an empty space. For simplicity's sake I will use `#`s and s arranged in a grid for the examples.

## Output

The output will be two large integers, followed by a series of 4-bit integers, or your language's equivalent. The two large integers will represent the starting co-ordinates, and the following numbers will represent a move like so:

```
 7 0
6   1
  K
5   2
 4 3

```

where `K` is the position before the move, and the number is the position after the move.

## Examples

As there are a lot of possible solutions to the Knight's Tour puzzle, I will only provide example outputs. There may be more outputs.

```
###
# #
###
0 0 3 0 5 2 7 4 1
AFC
D H
GBE

## ##
  ##
 ##
(4, 0) [5, 6, 3, 1, 6, 3, 0]
CF HA
  BE
 DG

```

New challenge: Come up with more examples

# Answer
> 5 votes
# Python 3.8 (pre-release), 254 bytes

```
n=-2,-1,1,2,2,1,-1,-2
l=len
e=enumerate
s=lambda b,x,y,t:max([1>((a:=[p:=x+_,q:=y+n[i-6]])in t)<l(b)>p>-1<q<l(b[p])>0<b[p][q]and[i]+s(b,p,q,t+[a])or[]for i,_ in e(n)],key=l)
f=lambda b:max([(z:=[x,y])+s(b,*z,[z])for x,r in e(b)for y,c in e(r)if c],key=l)

```

Try it online!

Pass input to the function `f` as a 2d array of truthy/falsey values.

Thanks to ovs and wizzwizz4

---
Tags: code-golf, chess
---


title: Unfold a list using a function

text:
# Question
Title: Unfold a list using a function
# Task

Haskell's and Scala's standard libraries have an `unfold` function that builds a list from an initial state `s` and a function `f`. This is done with the following steps (explained in an imperative way to be simpler):

1. Apply `f` to `s`.
2. If the result
    * is empty, we're done building the list!
    * Otherwise, the result should contain the next state `t` and the next element `e` of the list.
        1. Add `e` to the list
        2. Set `s` to `t` and go back to step 1

Here, we will only be considering lists made of integers. `s` will be an integer, `f` will take an integer as input, and the result of your `unfold` function will be a list of integers. The output of `f` will either be

* A fixed value representing that the list has ended
* A class of values (distinct from the fixed value above) that hold an integer representing the next state and an integer representing the next element.

## Example

Let's take the example of converting a number to base 5. The initial state would be the number to convert. The output would be a list of the digits in base 5, but reversed. The function would look something like this:

```
function f(s)
   if s equals 0
      return null
   else
      digit = s mod 5
      nextState = s ÷ 5 (÷ is integer division here)
      return [nextState, digit]

```

Using this function and an example initial state of 137, we go through the following steps:

* `s = 137` and the result is `[]`
* `digit = 2`, `nextState = 27`. The result is now the list `[2]` and `s` is `27`.
* `digit = 2`, `nextState = 5`. The result is now the list `[2, 2]` and `s` is `5`.
* `digit = 0`, `nextState = 1`. The result is now the list `[2, 2, 0]` and `s` is `1`.
* `digit = 1`, `nextState = 0`. The result is now the list `[2, 2, 0, 1]` and `s` is `0`.
* Since `s` is 0, we return the list `[2, 2, 0, 1]`

Reversed, that's `[1, 0, 2, 2]` or `1022`, which, in base 5, equals 137. Note that this algorithm does not work with 0 or negative integers.

Here is an implementation in Scala.

As a test case, your `unfold` function should be able to convert positive integers from a base 10 to another base (as a reversed list of digits).

# Answer
# APL (Dyalog Unicode), ~~32~~ 29 bytes

Full program, prompting for `s` and then for `f`.

```
¯1↓r⊣⎕{1↓r,∘⊃←⍺⍺⍵}⍣{⍬≡⍺}⎕⊣r←⍬

```

Try it online!

`r←⍬` initialise the **r**esult variable to the empty list

`⎕⊣` dismiss that in favour of `s` from stdin

`⎕{``}⍣{⍬≡⍺}` get `f` from std and use it as follows until the result is the empty list:

`⍺⍺⍵` apply `f` to the current `s` (returning `[e,t]` or `[]`)

`r,∘⊃←` extend `r` with the first value from that (`e` or `0`)

`1↓` drop the first value from that (leaving `[t]` or `[]`)

`r⊣` discard that (i.e. the last computed value, i.e. `[]`) in favour of `r`

`¯1↓` drop the last value (`0`)
> 6 votes

# Answer
# Factor, <sup>~~37~~</sup> 36 bytes

```
[ collector [ follow ] dip 1 head* ]

```

Try it online!

*-1 byte thanks to @chunes*

Takes `initial-value` and `quotation` on the stack, and returns a vector. The input quotation should return `next-state next-value` on the stack, or `f f` to terminate.

`some-quot collector [ high-order-func ] dip` is a pattern to snatch the top of the stack of every call of `some-quot` into a vector. Unfortunately, it collects the top of the stack before `follow` can detect that the loop has ended, so the resulting vector has a dummy element at the end. `1 head*` removes it.
> 6 votes

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

```
{-1_1_*'|'{x}(y@*:)\x}

```

Try it online!

call with `f[n,s]`.

`s` should return an array `(nextState;digit)` and return a falsy value when it's supposed to end.

I can remove `{x}` but that would make the function stop on a repeated state. Although that is unlikely, it doesn't seem right to reject that.

# Explanation

```
{-1_1_*'|'{x}(y@*:)\x}
                   \x
                       iterate on first arg, producing array
             (y@*:)    apply second arg(function) to the first elem of the iteration
          {x}          stop if the iteration is falsy
        |'             reverse each array
      *'               take first element of each
 -1_1_                 remove first and last element

```
> 5 votes

# Answer
# Wolfram Language (Mathematica), 26 bytes

```
f=#@#2/.{a_,b_}:>b<>#~f~a&

```

Try it online!

Input `[f, s]`. Returns a `StringJoin` of elements. Expects an empty list to indicate the list has ended.

To output a list, **+6 bytes**:

```
f=#@#2/.{a_,b_}:>{b,##&@@#~f~a}&

```

Try it online!
> 4 votes

# Answer
# , 27 bytes

```
1 :'[:(#~2|i.@#)(,u@{:)^:_'

```

Try it online!

This is J adverb, which modifies a verb returning `(new element, new state)` to create the required unfold verb.

* `(,u@{:)^:_` Keep appending unfold's results until a fixed point, re-applying the verb to the last element on every iteration.
* `[:(#~2|i.@#)` Keep only odd indexed elements, ie, the elements only, and discard the states and the starting value.
> 4 votes

# Answer
# tinylisp, 46 bytes

```
(d U(q((S F)(i(F S)(c(h(t(F S)))(U(h(F S))F))(

```

Try it online!

### Ungolfed

Implements the spec directly:

```
(load library)

(def unfold
  (lambda (val func)
    (if (func val)
      (cons
        (head (tail (func val)))
        (unfold (head (func val)) func))
      nil)))

```

This approach is pretty inelegant: it's not tail-recursive, and it calls the function three times at each step. If I were going to implement `unfold` for the standard library, it would look more like this (using a helper function `_unfold`):

```
(def _unfold
  (lambda (func return-val accum)
    (if return-val
      (_unfold func
        (func (head return-val))
        (cons (head (tail return-val)) accum))
      (reverse accum))))

(def unfold
  (lambda (func val)
    (_unfold func (func val) nil)))

```
> 4 votes

# Answer
# JavaScript, 37 bytes

```
f=>g=s=>(a=f(s))?[a[1],...g(a[0])]:[]

```

Try it online!

`((state: T) => [next_state: T, val: S]?) => (state: T) => S[]`
> 3 votes

# Answer
# Jelly, 7 bytes

```
Ṫv@¥ƬFḊ

```

Try it online!

A dyadic link taking the start value as its left argument and the Jelly code for the relevant function to unfold as its right. It expects the return value of this link to be an empty list if we’re done, otherwise a list of `[next value for result, next value for function]`. Returns a list of integers.
> 3 votes

# Answer
# Haskell, 22 bytes

```
f#x=do(s,v)<-f x;v:f#s

```

Try it online!

Function is expected to return a list `[(state, value)]` or an empty list. (Footer converts from the conventional/expected use of `Maybe`.)

```
f#x=                      Define a function (#) on arguments f and x, returning
    do     <-f x;         the concatenation for each element of f called on x
      (s,v)               providing the new state and value
                 v:       of the value prepended to
                   f#s    (f#) called on the new state.

```

Was this before I remembered `MonadFail` is a thing (never mind I'm not even using it anymore):

# Haskell, 26 bytes

```
f#x|s:v<-f x=v++f#s|1>0=[]

```

Try it online!

Function is expected to return a list `[state, value]` or an empty list.
> 3 votes

# Answer
# PowerShell Core, 36 bytes

```
for($k,$a=$args;$a){$a,$u=&$k $a;$u}

```

Try it online!

Takes two parameters, a function `$k` and the initial value `$a`

-1 byte thanks to *mazzy*!
> 3 votes

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

```
u=lambda f,x:(r:=f(x))and[r[1],*u(f,r[0])]

```

Try it online!

-1 byte thanks to Noodle9
-4 bytes thanks to Shaggy

Assumes falsy output for the end case and a pair otherwise (any subscriptable value with at least two elements). Since a list of falsy values is still truthy, this works perfectly fine.
> 2 votes

# Answer
# Perl 5, 45 bytes

```
sub u{@f=$_[1]->(@_);@f?(pop@f,u(@f,pop)):()}

```

Try it online!
> 2 votes

# Answer
# Racket, `#lang racket`, 57 bytes

```
(define(u s f)(match(f s)[`(,z,x)(cons x(u z f))][_'()]))

```

Try it online!

The function `f` can return anything other than a list of two values to indicate stop.

---

Not the most interesting racket solution: no tail-call recursion, so is bounded by memory usage. It would be more fun (and not difficult) to write a `#lang` that supplies `unfold` as part of its runtime—then there would be a 0-byte solution :)

We (unexpectedly?) save a few bytes by eliminating spaces between `,z,x` and `_'()` in `match` clauses. I expected each to coalesce into a single identifier, but (un)quoting took precedence. The remaining whitespace (6 spaces, by my count) is required.
> 1 votes

# Answer
# , ~~43~~ 42 bytes

```
u=function(s,l=f(s))if(1/l)c(l[2],u(l[1]))

```

Try it online!

Recursive function using helper function `f` to to the unfolding.

`f` must output the fixed non-integer value `Inf` to represent that the list has ended (a more natural value in  would be `NULL` or `NA`, but the functions `is.null()` and `is.na()` are each much less golfy than the simple test `1/x` \[truthy for all integers, falsy only for `Inf`\])
> 1 votes

---
Tags: code-golf, functional-programming
---


title: Code 3k to Codee k

text:
# Question
Title: Code 3k to Codee k
# Write some code...

Write a program that takes **no input** and outputs an integer `n` which is a multiple of `3`. So `n=3k`, where `k` is a positive integer.
**Double** the **last character** of your code.
Your code should then output `k`.

# Examples

Here is my program `hui#2(21+4)//lm`, which outputs `81`. Because of that, `hui#2(21+4)//lmm` should output `27`.
or
If `p8$w2*8` outputs `9`, `p8$w2*88` should output `3`.

# Rules

This is , shortest answer in bytes wins!

# Answer
# Mathematica, 2 bytes

```
4!

```

4! returns 24
4!! returns 8
> 41 votes

# Answer
## Many languages, 4 bytes

```
16-1

```

Outputs 15.

```
16-11

```

Outputs 5.

This is a CW answer for many languages it works for. Edit to add to the list:

* APL
* bc
* Dyvil
* Haskell
* I
* J
* Japt
* Javascript REPL
* Java REPL
* Julia REPL
* Mathematica
* Python REPL
* R REPL
* Ruby REPL
* Scala REPL
* Swift REPL
* TI-83/84 Basic
> 36 votes

# Answer
# Lost, ~~52~~, 18 bytes

```
\(@>>>
\>>%?
\(13$

```

Try it online!

```
\(@>>>
\>>%?
\(13$$

```

Try it online!

## Explanation

Lost is a language in which the start location and direction of the pointer are entirely random. Thus making a deterministic program can be tough.

The code we want to execute is either `13$(@` or `13$$(@`.

* `31` pushes 3 and 1 to the stack
* `$` will swap them
* `$` will swap them back if present
* `(` will pop the top element
* `@` will halt and output

We want to insert the `$` at the end so we have to split this

```
\(@
v
\31$

```

The rest of this is a careful orchestration to make sure that every possible pointer executes this code and only this code.
> 15 votes

# Answer
# Operation Flashpoint scripting language, 19 bytes

```
a="3";aa="1";hint a

```

**Outputs:**

```
a="3";aa="1";hint aa

```

**Outputs:**
> 10 votes

# Answer
# Jelly, 2 bytes

Try it online!

Outputs 3000.  is a numeric literal for 3000.

`3ȷȷ` outputs 1000:  is 3000, which is thrown away and replaced by `ȷ`, 1000.

This is the only two-byte solution, and it is optimal; I found it by trying every possible program.
> 10 votes

# Answer
# Actually, 2 bytes

Try it online!

Repeating the last character: `5¬¬`.

Explanation:

```
5¬
5   push 5
 ¬  subtract 2

```

Adding another `¬` causes 2 to be subtracted from 3, yielding 1.
> 9 votes

# Answer
# Python 2, 9 bytes

```
print 3&3

```

Try it online! Prints 3.

```
print 3&33

```

Try it online! Prints 1.
> 7 votes

# Answer
# Pyke, 2 bytes

This prints `3` and `6ee` prints `1`.

```
6e

```

**Try it here!**

```
6ee

```

**Try it here!**

```
6  - Push 6.
 e - Floor halve.
   - Print Implicitly.

```

---

# How?

Not much to explain. The whole point of this solution is that:
> 5 votes

# Answer
# CJam, 4 bytes

```
2_5+

```

Outputs `27`. Try it online!

```
2_5++

```

Outputs `9`. Try it online!
> 5 votes

# Answer
# Jelly, 3 bytes

```
81½

```

Try it online!

Outputs 9.

```
81½½

```

Try it online!

Outputs 3.
> 4 votes

# Answer
## Haskell, 8 bytes

```
gcd 3 21

```

Outputs `3`, and `gcd 3 211` outputs `1`.
> 4 votes

# Answer
# 05AB1E, 3 bytes

```
3Xr

```

Outputs 3.

Try it online!

```
3Xrr

```

Outputs 1.

Try it online!
> 4 votes

# Answer
# Cubix, 6 bytes

Works by changing the path based on cubes with different edge sizes. None of that tricky math stuff. The starting numbers could be also 1 3 or 2 6

```
39O@W@

```

Cubified

```
  3
9 O @ W
  @

```

Try it online!

Only executes `9O@` which is Push 9, Output as number, Halt.

```
39O@W@

```

Cubified

```
    3 9
    O @
W @ @ . . . . .
. . . . . . . .
    . .
    . .

```

This now executes `W3O@`, which is Left shift, Push 3, Output as number, Halt.

Try it online!
> 4 votes

# Answer
# Mathematica, 13 bytes

```
PrimeOmega@27

```

Not the shortest solution but y'know...
> 3 votes

# Answer
# C, ~~60~~ 45 bytes

*Thanks to @nwellnhof for saving 15 bytes!*

```
#define AA"5");}
#define A"1"AA
main(){puts(A

```

Outputs 15

```
#define AA"5");}
#define A"1"AA
main(){puts(AA

```

Outputs 5
> 3 votes

# Answer
# Polyglot, 05AB1E / 2sable, 3 bytes

This one prints `9`. `81tt` prints `3`.

```
81t

```

**Try it online!** **Try it online!**

```
81tt

```

**Try it online!** **Try it online!**
> 3 votes

# Answer
# Befunge-98, 6 bytes

```
<q%5b'

```

Try it online!

Outputs via exit code.

Explanation: On program start the IP is immediately sent leftwards, so it wraps to the right end and executes commands from right to left. So, in this program, it encounters `'b5%`, which pushes 98, the value of the character `b`, and then computes the remainder of 98 when divided by 5, which is 3. Finally, with `q`, it quits with this exit code.

With the last character doubled, it encounters `''b5%`, which pushes the value of the character `'` but then immediately pushes `b`, which is 11. It then computes the remainder of 11 when divided by 5, which is 1, and quits with this exit code.
> 3 votes

# Answer
# Pyth, 4 bytes

This prints `9`. `x8 11` prints `3`.

```
x8 1

```

**Try it online!**

```
x8 11

```

**Try it online!**

---

# How?

```
x8 1  - Full program.

x     - Bitwise XOR.
 8 1  - Of 8 and 1.
      - Implicitly print.

```
> 2 votes

# Answer
# Befunge-98 (PyFunge), 5 bytes

```
[q/3g

```

Try it online!

Outputs via exit code.

### Explanation

First, the IP hits the "turn left" instruction (`[`) twice, which wraps it back around to the back of the code, going right.

The "get" instruction (`g`) takes the first 2 values and pushes the ASCII value of the character at that x and y position. The first time it is executed, there are only zeros on the stack, meaning we get the value 91. If we don't double the `g`, we divide 91 by 3, with integer division, truncating it to 30, which is returned.

If we do duplicate the `g`, it gets the ASCII value at (0, 91), which isn't anywhere near the code. Because the grid is initialized to be filled with spaces, this returns the value 32. if we integer divide by 3, we get 10, one third of 30.
> 2 votes

# Answer
# Python 2, 16 bytes

```
a=3;aa=1;print a

```

outputs 3

```
a=3;aa=1;print aa

```

outputs 1
> 1 votes

# Answer
# , 5 bytes

```
é52ñ

```

Try it online!

Outputs 3

```
é52ñ

```

Try it online!

Outputs 1
> 1 votes

# Answer
# Ly, 6 bytes

```
3>1<<>

```

Try it online!

Outputs `3`.

With the second character duplicated:

```
3>1<<>>

```

Try it online!

Outputs `1`.
> 1 votes

# Answer
# Recursiva, 5 bytes

```
+16-1

```

Try it online!

* Ripped off from Many languages solution, only a byte more since Recursiva is prefix and `-` sign and subtract operator are the same. This is actually adding `16` and `-1`.

# Other solution:

# Recursiva, 10 bytes

```
Y_+B5A3IH1

```

Try it online!
> 1 votes

# Answer
# Jelly, 5 bytes

This one outputs `3`. By doubling the last character, you get `1`.

```
HḞ
6Ç

```

**Try it online!**

```
HḞ
6ÇÇ

```

**Try it online!**
> 1 votes

# Answer
# Japt, 3 bytes

Still on the hunt for a 2 byte solution.

`#Q` is 81 and `¬` is square root, which gives `9`. Adding another `¬` at the end gives `3`

```
#Q¬

```

Try it

```
#Q¬¬

```

Try it
> 1 votes

# Answer
# \>\<\>, 6 bytes

```
",n;c!

```

Try it online!

```
",n;c!!

```

Try it online!

### Explanation

```
",n;c!  : Put each character onto the stack;
          [110, 59, 99, 33]
 ,n;    : Divide the top two stack items, print as a number and end.
          99/33 = 3

```

---

```
",n;c!! : Put each chat onto the stack;
          [110, 59, 99, 33, 33]
 ,n;    : Divide the top two stack items, print as a number and end.
          99/33 = 3

```
> 1 votes

# Answer
# Pyt, 2 bytes

```
9₃

```

Returns 9/3

Try it online!

---

```
9₃₃

```

Returns (9/3)/3

Try it online!

---

Alternatively, also 2 bytes:

```
6₂

```

This works due to Python 2's integer division
> 1 votes

# Answer
# Pyth, 5 bytes

```
-16 1

```

Try it online!
> 0 votes

# Answer
# Charcoal, 6 bytes

This one prints `15`. The other version prints `5`.

```
Ｉ⁻¹⁶¦¹

```

**Try it online!**

```
Ｉ⁻¹⁶¦¹¹

```

**Try it online!**
> 0 votes

# Answer
# Neim, 2 bytes

```
ηᚠ

```

Outputs 3. Doubled, outputs 1.

Try it online!

Doubled
> 0 votes

# Answer
**Ruby, 5 bytes**

```
3/0b1

```

Division by one or three, written in binary.
> 0 votes

# Answer
# RProgN 2, 2 bytes

```
6›

```

`6›` takes `6` and shifts it right. `110 -> 11` which gives 3. `6››` shifts 6 twice, which gives `110 -> 1`, or 1.

Try it online!
> 0 votes

# Answer
# Forth (gforth), 10 bytes

Feels cheap to just overwrite the `33` numeric literal, but it's the shortest way I know of to make this work in forth

```
: 33 1 ; 3

```

Try it online!

outputs 3

```
: 33 1 ; 33

```

Try it online!

outputs 1

### Explanation

```
: 33 1 ;  \ defines a new word 33 that puts a 1 on the stack.
          \ In forth explicit word definitions are parsed before numeric literals

```
> 0 votes

# Answer
# Klein 0X0, 8 bytes

*Works in 000 (torus) and 010 (Klein bottle)*

```
\(@
\13$

```

Try it online!

```
\(@
\13$$

```

Try it online!

# 1XX, 9 bytes

*Works in 100, 101, 110 and 111*

```
\>(@
\13$

```

Try it online!

```
\>(@
\13$$

```

Try it online!
> 0 votes

---
Tags: code-golf, source-layout
---