title: Line Islands in a Word Search

text:
# Question
Title: Line Islands in a Word Search
My third word search related challenge in a row. :)

## Challenge:

#### Brief explanation of what a word search is:

In a word search you'll be given a grid of letters and a list of words. The idea is to cross off the words from the list in the grid. The words can be in eight different directions: horizontally from left-to-right or right-to-left; vertically from top-to-bottom or bottom-to-top; diagonally from the topleft-to-bottomright or bottomright-to-topleft; or anti-diagonally from the topright-to-bottomleft or bottomleft-to-topright.

#### Actual challenge:

Given a list of coordinates indicating the crossed out words within a grid (in any reasonable format), output how many line-islands there are.

We've had challenges involving finding the amount of islands in a matrix. But in this case it's different: just looking at the grid, words could be right next to each other, but would still be two separated line-islands. E.g. In the following partially solved word search, we have four separated line-islands, even though the letters of the words are right next to each other.

This partially solved word search above would result in an output of `4`.

If 'word' `FG` was `FGH` like this:

The output would have been `3` instead, because the `FGH`+`NKH` now form a single connected line-island.

In this challenge we'll only be taking the coordinates of the words in a grid as input, and output the amount of line-islands.

## Challenge rules:

* You're allowed to take the input in any reasonable format. It could be pair of coordinates per word to indicate their start/end positions (e.g. `[[[0,0],[0,2]],[[1,1],[1,3]],[[3,1],[1,3]],[[3,2],[2,3]]]` for the second example above); it could be a full list of coordinates per word (e.g. `[[[0,0],[0,1],[0,2]],[[1,1],[1,2],[1,3]],[[3,1],[2,2],[1,3]],[[3,2],[2,3]]]`); a list of bit-mask matrices per word (e.g. `[[[1,1,1,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]],[[0,0,0,0],[0,1,1,1],[0,0,0,0],[0,0,0,0]],[[0,0,0,0],[0,0,0,1],[0,0,1,0],[0,1,0,0]],[[0,0,0,0],[0,0,0,0],[0,0,0,1],[0,0,1,0]]]`); etc. If you're unsure if a possible input-format is valid, leave a comment down below.
* All 'words' are guaranteed to have at least two letters.
* You can assume the input won't be empty.
* You can optionally take the dimensions of the grid as additional input.
* Note that coordinates of 'words' are not guaranteed to be in the same positions to still form a single line-island! E.g. this grid would result in `1` because the lines cross, but neither 'word' share the same letter-positions:

## General rules:

* This is , so the shortest answer in bytes wins.
Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
* Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
* Default Loopholes are forbidden.
* If possible, please add a link with a test for your code (e.g. TIO).
* Also, adding an explanation for your answer is highly recommended.

## Test cases:

* Input as start/ending coordinates of the 'words': `[[[0,0],[0,2]],[[1,1],[1,2]],[[3,1],[1,3]],[[3,2],[2,3]]]`
* Input as coordinates of the complete 'words': `[[[0,0],[0,1],[0,2]],[[1,1],[1,2]],[[3,1],[2,2],[1,3]],[[3,2],[2,3]]]`
* Input as bit-mask matrices of the 'words': `[[[1,1,1,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]],[[0,0,0,0],[0,1,1,0],[0,0,0,0],[0,0,0,0]],[[0,0,0,0],[0,0,0,1],[0,0,1,0],[0,1,0,0]],[[0,0,0,0],[0,0,0,0],[0,0,0,1],[0,0,1,0]]]`

**Output: `4`**

---

* Input as start/ending coordinates of the 'words': `[[[0,0],[0,2]],[[1,1],[1,3]],[[3,1],[1,3]],[[3,2],[2,3]]]`
* Input as coordinates of the complete 'words': `[[[0,0],[0,1],[0,2]],[[1,1],[1,2],[1,3]],[[3,1],[2,2],[1,3]],[[3,2],[2,3]]]`
* Input as bit-mask matrices of the 'words': `[[[1,1,1,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]],[[0,0,0,0],[0,1,1,1],[0,0,0,0],[0,0,0,0]],[[0,0,0,0],[0,0,0,1],[0,0,1,0],[0,1,0,0]],[[0,0,0,0],[0,0,0,0],[0,0,0,1],[0,0,1,0]]]`

**Output: `3`**

---

* Input as start/ending coordinates of the 'words': `[[[0,0],[1,1]],[[0,1],[1,0]]]`
* Input as coordinates of the complete 'words': `[[[0,0],[1,1]],[[0,1],[1,0]]]`
* Input as bit-mask matrices of the 'words': `[[[1,0],[0,1]],[[0,1],[1,0]]]`

**Output: `1`**

---

* Input as start/ending coordinates of the 'words': `[[[1,9],[8,9]],[[8,6],[1,6]],[[1,4],[4,7]],[[9,0],[0,9]],[[1,0],[6,0]],[[6,1],[3,4]],[[9,4],[9,9]],[[0,1],[0,8]],[[9,3],[1,3]],[[0,0],[9,9]]]`
* Input as coordinates of the complete 'words': `[[[1,9],[2,9],[3,9],[4,9],[5,9],[6,9],[7,9],[8,9]],[[8,6],[7,6],[6,6],[5,6],[4,6],[3,6],[2,6],[1,6]],[[1,4],[2,5],[3,6],[4,7]],[[9,0],[8,1],[7,2],[6,3],[5,4],[4,5],[3,6],[2,7],[1,8],[0,9]],[[1,0],[2,0],[3,0],[4,0],[5,0],[6,0]],[[6,1],[5,2],[4,3],[3,4]],[[9,4],[9,5],[9,6],[9,7],[9,8],[9,9]],[[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8]],[[9,3],[8,3],[7,3],[6,3],[5,3],[4,3],[3,3],[2,3],[1,3]],[[0,0],[1,1],[2,2],[3,3],[4,4],[5,5],[6,6],[7,7],[8,8],[9,9]]]`
* Input as bit-mask matrices of the 'words': pastebin

**Output: `4`**

---

* Input as start/ending coordinates of the 'words': `[[[8,6],[1,6]],[[1,4],[4,7]],[[9,0],[0,9]],[[6,1],[3,4]],[[9,4],[9,9]],[[9,3],[1,3]],[[0,0],[9,9]]]`
* Input as coordinates of the complete 'words': `[[[8,6],[7,6],[6,6],[5,6],[4,6],[3,6],[2,6],[1,6]],[[1,4],[2,5],[3,6],[4,7]],[[9,0],[8,1],[7,2],[6,3],[5,4],[4,5],[3,6],[2,7],[1,8],[0,9]],[[6,1],[5,2],[4,3],[3,4]],[[9,4],[9,5],[9,6],[9,7],[9,8],[9,9]],[[9,3],[8,3],[7,3],[6,3],[5,3],[4,3],[3,3],[2,3],[1,3]],[[0,0],[1,1],[2,2],[3,3],[4,4],[5,5],[6,6],[7,7],[8,8],[9,9]]]`
* Input as bit-mask matrices of the 'words': pastebin

**Output: `1`**

# Answer
> 3 votes
# Jelly,  ~~22~~  20 bytes

```
żSH$ƝẎ)ṭfƇ@ẎQʋ€ÐL`QL

```

A monadic Link that accepts a list of lists of pairs of integers - the full list of coordinates for each word - and yields the island count.

**Try it online!** (Two islands each being two words crossing at cell corners, where equal-island words are non-adjacent in the input list.)

Or see the test-suite.

### How?

*Needs updating*:

```
ṭfƇ@ẎṢQ - Link 1, add crossing words: Coordinates, (all) Word Coordinates
   @    - with swapped arguments:
  Ƈ     -   filter keep (those Word Coordinate lists) for which:
 f      -     filter keep (i.e. contain some of the same entries)
ṭ       - tack to Coordinates
    Ẏ   - tighten
     Ṣ  - sort
      Q - deduplicate

żSH$ƝẎ)ç€ÐL`QL - Main Link: Word Coordinates
      )        - for each list in Word Coordinates:
   $Ɲ          -   for neighbours:
 S             -     sum (vectorises)
  H            -     halve
ż              - Word Coordinates zip-with those "intermediate coordinates"
     Ẏ         - tighten
           `   - use as both arguments of:
         ÐL    -   loop until no change with:
       ç€      -     call Link 1 for each
            Q  - deduplicate
             L - length

```

# Answer
> 1 votes
# Python3, 560 bytes:

```
lambda w:len({str(i[0])for i in g(w)})
S=lambda a:[(t:=(a[1][0]-a[0][0])/([1,(k:=a[1][1]-a[0][1])][k!=0])*(k>0)),[a[0][1],t*-1*a[0][1]+a[0][0]][k!=0]]
M=lambda j,k:[(x:=(k[1]-j[1])/(j[0]-k[0])),j[0]*x+j[1]][::-1]
N=lambda s,p:min(t:=[s[0][0],s[1][0]])<=p[0]<=max(t)and min(t:=[s[0][1],s[1][1]])<=p[1]<=max(t)
V=lambda a,b:(j:=S(a))[0]!=(k:=S(b))[0]and N(a,m:=M(j,k))and N(b,m)
def g(w):
 Q,S=[[i]for i in w],[]
 while Q:
  if(v:=Q.pop(0))[-1]not in S:
   if[]==(j:=[i for i in w if i not in S and V(v[-1],i)]):yield v
   else:Q=[v+[i]for i in j]+Q
   S+=v[-1:]

```

Try it online!

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

```
Length@ConnectedComponents@Graph[#->If[#⋂#2=={},##]&@@@Tuples[Total/@#~Tuples~2&/@#,2]]&

```

Try it online!

A simple set intersection between the lists of coordinates would detect almost all the cases except the 'phantom intersection' of two diagonal 'words'.
In this special case, these phantom intersecting diagonals, have both 2 coordinates that add up to a same one.

```
+---------+---------+
|A        |B        |
|  x   y  | x+1  y  |
|         |         |
+---------X---------+         A coords.          B coords.
|B        |A        |    (x,y) + (x+1,y+1) = (x,y+1) + (x+1,y)
|  x  y+1 | x+1 y+1 |
|         |         |
+---------+---------+

```

Unfortunately a test for this would not detect the standard intersection of two words that actually have one common coordinate. As such my first implementation combined two test:

* the intersection between the plain lists of coordinates `#`
* the intersection between the lists of the **sums of consecutive coordinates** `Partition[#,2,1]` (this also assumed the lists would always be in order).

But then I thought why not **sum every pair of coordinates** (multisets) of a 'word'?
Also pushed by the fact that `Tuples[#,2]` is shorter than `Partition[#,2,1]`

## Technicalities

The only doubt: can there be false positives?
That is, can two 'words' that do not share any coordinate be mapped into 'words' that do share some coordinates?

To sum all the coordinates in a 'word' with themselves is essentially a x2 scaling done in a redundant fashion.

So, for each mapped coordinate of a 'word' \\$(x\_i+x\_j,y\_i+y\_j)\\$ we can infer its preimage: a pair of coordinates of 'word' that yield the mapped one. Hence if two 'words' share a mapped coordinate they also have to share the relative pair of 'core coordinates'.

This pair of 'core coordinates' (`P`,`b`) are the two coordinates around the possibly 'phantom point' (`@`) \\$(\frac{x\_i+x\_j}{2},\frac{y\_i+y\_j}{2})\\$

```
+---------+---------+   +---------+---------+   +---------+---------+   +---------+---------+    +---------+---------+
|BBBBBBBBB|         |   |PPPPPPPPP|         |   |         |         |   |PPPPPPPPP|         |    |         |PPPPPPPPP|
|BBBB@BBBB|         |   |PPPPPPPPP|         |   |         |         |   |PPPPPPPPP|         |    |         |PPPPPPPPP|
|BBBBBBBBB|         |   |PPPPPPPPP|         |   |         |         |   |PPPPPPPPP|         |    |         |PPPPPPPPP|
+---------+---------+ , +----@----+---------+ , +---------+---------+ , +---------@---------+ OR +---------@---------+
|         |         |   |bbbbbbbbb|         |   |PPPPPPPPP|bbbbbbbbb|   |         |bbbbbbbbb|    |bbbbbbbbb|         |
|         |         |   |bbbbbbbbb|         |   |PPPPPPPPP@bbbbbbbbb|   |         |bbbbbbbbb|    |bbbbbbbbb|         |
|         |         |   |bbbbbbbbb|         |   |PPPPPPPPP|bbbbbbbbb|   |         |bbbbbbbbb|    |bbbbbbbbb|         |
+---------+---------+   +---------+---------+   +---------+---------+   +---------+---------+    +---------+---------+

```

---
Tags: code-golf, integer, grid, matrix, word-search
---


# Question
Title: Output this string from the `kolmogorov-complexity` tag info page
is one of the tags on this site, representing challenges that test how much code is needed to output a given fixed result (usually a piece of text). The info page for this tag lists the string `4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfd` as an example of a string with a high Kolmogorov complexity, stating that printing this string literally is probably the shortest way to output it. I would like to test this statement, and thus your challenge is to output this string, without using a literal representation of it.

## Rules

* You must write a full program that takes no input, and outputs exactly the result string, with a single optional trailing newline. Output may be in any format allowed by default IO rules (writing to STDOUT, writing to a file, displaying to the screen, etc)
* No submitting the trivial solution of your language's equivalent of `print "4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfd"`, however, I will create a community wiki answer to list trivial solutions for comparison, so if you answer in a language not added to that answer, please edit that language's trivial solution (if it exists) into that post.
* Use of built-ins is allowed, if your language somehow has a built-in that contains or can easily generate this string, I would love to see that.

, so lowest bytecount is best score, but please also list the difference in length between your bytecount and the bytecount of your language's trivial solution with your score.

# Answer
> 4 votes
# Trivial Solutions

If you answer this question and the trivial solution to this problem is not currently listed here, please edit it into this post, to serve as a point of comparison against non-trivial solutions in that language. For purposes of clarity, the trivial solution to this problem is defined as your language's equivalent of a `print` statement, plus your language's equivalent of a string literal, containing `4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfd`, and being passed to the `print` statement, plus whatever boilerplate is necessary to make it a full program.

When adding a language to this, please format with a level three heading containing the language name and bytecount (formatting: `### Language Name, XX bytes ###`). Follow this with a codeblock (formatting: ```` code here ````) containing the code of the trivial solution. Please try to keep the list in alphabetical order by language name.

**Place solutions below this line:**

---

### 05AB1E, 41 bytes

```
"4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfd

```

### Charcoal, 29 bytes

```
”E#-¡2e·ⅉÀθº,"ＧＥσＧ>υ[C=↥↗μω⮌ψ

```

It's a compressed string literal, but it's still a string literal, so I guess this counts as a trivial solution. The link is to the equivalent Verbose Charcoal, which is an even more trivial solution, but the Charcoal deverbosifier helpfully prints the actual solution before executing it.

### Java 8, 45 bytes

```
v->"4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfd"

```

### Jelly, 41 bytes

```
“4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfd

```

### Julia, 49 bytes

```
print("4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfd")

```

### Python 2, 47 bytes

```
print"4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfd"

```

### Python 3, 49 bytes

```
print("4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfd")

```

### Retina, 41 bytes

```

4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfd

```

### Rust, 61 bytes

```
fn main(){print!("4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfd")}

```

### APL, 42 bytes

```
'4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfd'

```

# Answer
> 3 votes
# Jelly,  ~~35~~  34 bytes

```
ØBḟØA“÷ȯḋ²÷Œmṗ)¿+¹ỊỴ7ĠYṖP0ṡẋœ{ỵC’ṃ

```

**Try it online!**

### How?

```
ØBḟØA“...’ṃ - Main Link: no arguments
ØB          - base-62 digits = "0..9A..Za..z"
   ØA       - uppercase characters = "A..Z"
  ḟ         - filter-discard -> "0..9a..z"
     “...’  - big integer in a base 250 representation
          ṃ - base decompress (use the characters as base 62 digits of the integer)
            - implicit print

```

# Answer
> 2 votes
# Julia, 49 bytes

```
print(4,:c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfd)

```

Try it online!

Same length as the trivial solution. I guess it's not trivial ? And it's technically not concatenation. It prints the number 4 and then a Symbol (technically not a string).

Feel free to debate whether this is too trivial or not

# Answer
> 1 votes
# Charcoal, 36 bytes

```
⍘⍘AN%)~:0+VJEkbeQYeRX!$2_[^}8g?\xγ³⁵

```

Try it online! Explanation: Converts the literal string `AN%)~:0+VJEkbeQYeRX!$2_[^}8g?\x` from base 95 (using printable ASCII) to base 35 (using `0-9a-y`).

If the compressed string literal form of the above literal string is allowed, then for 34 bytes:

```
⍘⍘“\`"Ｚζ﹪⊕↙84¤κq≡ＩT⁵⭆℅?R¤Ｂg÷φm⊙”γ³⁵

```

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

Alternatively, the compressed string literal form of the numeric value of the base 35 conversion also results in 34 bytes:

```
⍘Ｉ”)¶＆Ｋ‖◨"Ｓγ]ιＪG÷φïzjμp⬤ＸχφωqE·”³⁵

```

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

# Answer
> 1 votes
# Vyxal, ~~35~~ 34 bytes

```
»gtWŀż⌊l,∇ɖ∩꘍√ṘȮ∞*"Cβ1⋎ʀv@Ḃ»kakd+τ

```

Try it Online!

-1 thanks to @whqwert

Ez

```
»gtWŀż⌊l,∇ɖ∩꘍√ṘȮ∞*"Cβ1⋎ʀv@Ḃ»kakd+τ # Full program
                                 τ # Convert the number to base len(str) using the number...
»gtWŀż⌊l,∇ɖ∩꘍√ṘȮ∞*"Cβ1⋎ʀv@Ḃ»       # 149288472330050833510329217157030174401240445325930074868876423
                            kakd+  # And the string "abcdefghijklmnopqrstuvwxyz0123456789"

```

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


title: Cracking the Enigma?

text:
# Question
Title: Cracking the Enigma?
### Introduction

The Enigma was one of the first electro-mechanical rotor cipher machines used in World War II. That means that after a single letter is coded, it would change the key for the next letter. This was considered *unbreakable* by the Germans, due to the enormous key space. Even brute-forcing was almost impossible. However, there was a design error in the Enigma. Encrypting a letter would never result into itself. That means that the letter `A` can encrypt to every letter except the letter `A`.

Let's take an example of a coded message:

```
BHGEFXWFTIUPITHHLPETTTCLOEWOELMRXXPAKAXMAMTXXUDLTWTNHKELEPPLHPRQ

```

A typical German word was `WETTERBERICHT`, or weather report in English. With the principe above, we can determine at which locations the word could possibly be:

```
BHGEFXWFTIUPITHHLPETTTCLOEWOELMRXXPAKAXMAMTXXUDLTWTNHKELEPPLHPRQ
WETTERBERICHT
         ^

```

This is not possible, because the `I` can't be encrypted to itself, so we move on 1 place:

```
BHGEFXWFTIUPITHHLPETTTCLOEWOELMRXXPAKAXMAMTXXUDLTWTNHKELEPPLHPRQ
 WETTERBERICHT
             ^

```

This is also not possible, so we move another place again:

```
BHGEFXWFTIUPITHHLPETTTCLOEWOELMRXXPAKAXMAMTXXUDLTWTNHKELEPPLHPRQ
  WETTERBERICHT
   ^

```

This again is not possible. In fact, the first possible occurence of `WETTERBERICHT` is:

```
BHGEFXWFTIUPITHHLPETTTCLOEWOELMRXXPAKAXMAMTXXUDLTWTNHKELEPPLHPRQ
             WETTERBERICHT
0123456789012345678901234567890123456789012345678901234567890123
             ^
             13

```

So, we return the 0-indexed position of the first possible occurence, which is **13**.

### The Task

* Given a coded message and a word, find the index of the **first possible occurence**.
* Assume that only basic uppercase alphabetic characters will be used (`ABCDEFGHIJKLMNOPQRSTUVWXYZ`).
* If no occurence is found, you can output any **negative** integer, character, or nothing (e.g. `-1`, `X`).
* Input may be accepted as argument, on seperate newlines, lists or anything else.
* This is , so the submission with the least amount of bytes wins!

### Test cases

```
Input: BHGEFXWFTIUPITHHLPETTTCLOEWOELM, WETTERBERICHT
Output: 13

Input: ABCDEFGHIJKL, HELLO
Output: 0

Input: EEEEEEEEEEEE, HELLO
Output: -1

Input: XEEFSLBSELDJMADNADKDPSSPRNEBWIENPF, DEUTSCHLAND
Output: 11

Input: HKKH, JJJJJ
Output: -1

```

# Answer
> 10 votes
# Pyth, 14 bytes

```
f!s.eqb@>zTkQ0

```

I'm not sure if this is Ok but if the input is impossible, nothing is written to stdout and a zero division error is written to stderr. Takes the input on 2 lines, the second one is surrounded by quotes.

Explanation:

```
               - autoassign z to first input
               - autoassign Q to second input
f            0 - The first value starting from 0 where the output is truthy
   .e       Q  - Enumerate over the second value
        >zT    - z[T:]
       @   k   - The kth item (number in enumeration)
      b        - The character in the enumeration
     q         - Are the two characters equal?
  s            - Sum the values
 !             - Invert them (want first where there isn't a collision)

```

Try it here!

# Answer
> 57 votes
# JavaScript, 40

```
(c,p)=>c.search(p.replace(/./g,"[^$&]"))

```

Using `replace`, this maps the plaintext input into a regular expression of form `/[^H][^E][^L][^L][^O]/` (e.g., for plaintext input `HELLO`) and then uses `search` to test for the first index of the ciphertext substring that matches that regex. This regex means "a pattern where the first character is not `H`, the second character is not `E`, etc."

`$&` is a special sequence for `replace` output that substitutes in the value matched by the first `replace` argument (in this case, each single character matched by `/./`).

# Answer
> 46 votes
## Turing Machine Simulator \- 15660 bytes (Non-Competing)

Can't have an Enigma challenge without turing machine code.

```
0 * * l 0
0 _ _ l ,
, _ , l 1
1 _ 0 r 2
2 * * r 2
2 , * r 3
3 * * r 3
3 , * r 4
4 * * r 4
4 _ * r 13
4 A a l a'
4 B b l b'
4 C c l c'
4 D d l d'
4 E e l e'
4 F f l f'
4 G g l g'
4 H h l h'
4 I i l i'
4 J j l j'
4 K k l k'
4 L l l l'
4 M m l m'
4 N n l n'
4 O o l o'
4 P p l p'
4 Q q l q'
4 R r l r'
4 S s l s'
4 T t l t'
4 U u l u'
4 V v l v'
4 W w l w'
4 X x l x'
4 Y y l y'
4 Z z l z'
a' * * l a'
a' , * l a
b' * * l b'
b' , * l b
c' * * l c'
c' , * l c
d' * * l d'
d' , * l d
e' * * l e'
e' , * l e
f' * * l f'
f' , * l f
g' * * l g'
g' , * l g
h' * * l h'
h' , * l h
i' * * l i'
i' , * l i
j' * * l j'
j' , * l j
k' * * l k'
k' , * l k
l' * * l l'
l' , * l l
m' * * l m'
m' , * l m
n' * * l n'
n' , * l n
o' * * l o'
o' , * l o
p' * * l p'
p' , * l p
q' * * l q'
q' , * l q
r' * * l r'
r' , * l r
s' * * l s'
s' , * l s
t' * * l t'
t' , * l t
u' * * l u'
u' , * l u
v' * * l v'
v' , * l v
w' * * l w'
w' , * l w
x' * * l x'
x' , * l x
y' * * l y'
y' , * l y
z' * * l z'
z' , * l z

a * * l a
a _ * r A
a a * r A
a b * r A
a c * r A
a d * r A
a e * r A
a f * r A
a g * r A
a h * r A
a i * r A
a j * r A
a k * r A
a l * r A
a m * r A
a n * r A
a o * r A
a p * r A
a q * r A
a r * r A
a s * r A
a t * r A
a u * r A
a v * r A
a w * r A
a x * r A
a y * r A
a z * r A
b * * l b
b _ * r B
b a * r B
b b * r B
b c * r B
b d * r B
b e * r B
b f * r B
b g * r B
b h * r B
b i * r B
b j * r B
b k * r B
b l * r B
b m * r B
b n * r B
b o * r B
b p * r B
b q * r B
b r * r B
b s * r B
b t * r B
b u * r B
b v * r B
b w * r B
b x * r B
b y * r B
b z * r B
c * * l c
c _ * r C
c a * r C
c b * r C
c c * r C
c d * r C
c e * r C
c f * r C
c g * r C
c h * r C
c i * r C
c j * r C
c k * r C
c l * r C
c m * r C
c n * r C
c o * r C
c p * r C
c q * r C
c r * r C
c s * r C
c t * r C
c u * r C
c v * r C
c w * r C
c x * r C
c y * r C
c z * r C
d * * l d
d _ * r D
d a * r D
d b * r D
d c * r D
d d * r D
d e * r D
d f * r D
d g * r D
d h * r D
d i * r D
d j * r D
d k * r D
d l * r D
d m * r D
d n * r D
d o * r D
d p * r D
d q * r D
d r * r D
d s * r D
d t * r D
d u * r D
d v * r D
d w * r D
d x * r D
d y * r D
d z * r D
e * * l e
e _ * r E
e a * r E
e b * r E
e c * r E
e d * r E
e e * r E
e f * r E
e g * r E
e h * r E
e i * r E
e j * r E
e k * r E
e l * r E
e m * r E
e n * r E
e o * r E
e p * r E
e q * r E
e r * r E
e s * r E
e t * r E
e u * r E
e v * r E
e w * r E
e x * r E
e y * r E
e z * r E
f * * l f
f _ * r F
f a * r F
f b * r F
f c * r F
f d * r F
f e * r F
f f * r F
f g * r F
f h * r F
f i * r F
f j * r F
f k * r F
f l * r F
f m * r F
f n * r F
f o * r F
f p * r F
f q * r F
f r * r F
f s * r F
f t * r F
f u * r F
f v * r F
f w * r F
f x * r F
f y * r F
f z * r F
g * * l g
g _ * r G
g a * r G
g b * r G
g c * r G
g d * r G
g e * r G
g f * r G
g g * r G
g h * r G
g i * r G
g j * r G
g k * r G
g l * r G
g m * r G
g n * r G
g o * r G
g p * r G
g q * r G
g r * r G
g s * r G
g t * r G
g u * r G
g v * r G
g w * r G
g x * r G
g y * r G
g z * r G
h * * l h
h _ * r H
h a * r H
h b * r H
h c * r H
h d * r H
h e * r H
h f * r H
h g * r H
h h * r H
h i * r H
h j * r H
h k * r H
h l * r H
h m * r H
h n * r H
h o * r H
h p * r H
h q * r H
h r * r H
h s * r H
h t * r H
h u * r H
h v * r H
h w * r H
h x * r H
h y * r H
h z * r H
i * * l i
i _ * r I
i a * r I
i b * r I
i c * r I
i d * r I
i e * r I
i f * r I
i g * r I
i h * r I
i i * r I
i j * r I
i k * r I
i l * r I
i m * r I
i n * r I
i o * r I
i p * r I
i q * r I
i r * r I
i s * r I
i t * r I
i u * r I
i v * r I
i w * r I
i x * r I
i y * r I
i z * r I
j * * l j
j _ * r J
j a * r J
j b * r J
j c * r J
j d * r J
j e * r J
j f * r J
j g * r J
j h * r J
j i * r J
j j * r J
j k * r J
j l * r J
j m * r J
j n * r J
j o * r J
j p * r J
j q * r J
j r * r J
j s * r J
j t * r J
j u * r J
j v * r J
j w * r J
j x * r J
j y * r J
j z * r J
k * * l k
k _ * r K
k a * r K
k b * r K
k c * r K
k d * r K
k e * r K
k f * r K
k g * r K
k h * r K
k i * r K
k j * r K
k k * r K
k l * r K
k m * r K
k n * r K
k o * r K
k p * r K
k q * r K
k r * r K
k s * r K
k t * r K
k u * r K
k v * r K
k w * r K
k x * r K
k y * r K
k z * r K
l * * l l
l _ * r L
l a * r L
l b * r L
l c * r L
l d * r L
l e * r L
l f * r L
l g * r L
l h * r L
l i * r L
l j * r L
l k * r L
l l * r L
l m * r L
l n * r L
l o * r L
l p * r L
l q * r L
l r * r L
l s * r L
l t * r L
l u * r L
l v * r L
l w * r L
l x * r L
l y * r L
l z * r L
m * * l m
m _ * r M
m a * r M
m b * r M
m c * r M
m d * r M
m e * r M
m f * r M
m g * r M
m h * r M
m i * r M
m j * r M
m k * r M
m l * r M
m m * r M
m n * r M
m o * r M
m p * r M
m q * r M
m r * r M
m s * r M
m t * r M
m u * r M
m v * r M
m w * r M
m x * r M
m y * r M
m z * r M
n * * l n
n _ * r N
n a * r N
n b * r N
n c * r N
n d * r N
n e * r N
n f * r N
n g * r N
n h * r N
n i * r N
n j * r N
n k * r N
n l * r N
n m * r N
n n * r N
n o * r N
n p * r N
n q * r N
n r * r N
n s * r N
n t * r N
n u * r N
n v * r N
n w * r N
n x * r N
n y * r N
n z * r N
o * * l o
o _ * r O
o a * r O
o b * r O
o c * r O
o d * r O
o e * r O
o f * r O
o g * r O
o h * r O
o i * r O
o j * r O
o k * r O
o l * r O
o m * r O
o n * r O
o o * r O
o p * r O
o q * r O
o r * r O
o s * r O
o t * r O
o u * r O
o v * r O
o w * r O
o x * r O
o y * r O
o z * r O
p * * l p
p _ * r P
p a * r P
p b * r P
p c * r P
p d * r P
p e * r P
p f * r P
p g * r P
p h * r P
p i * r P
p j * r P
p k * r P
p l * r P
p m * r P
p n * r P
p o * r P
p p * r P
p q * r P
p r * r P
p s * r P
p t * r P
p u * r P
p v * r P
p w * r P
p x * r P
p y * r P
p z * r P
q * * l q
q _ * r Q
q a * r Q
q b * r Q
q c * r Q
q d * r Q
q e * r Q
q f * r Q
q g * r Q
q h * r Q
q i * r Q
q j * r Q
q k * r Q
q l * r Q
q m * r Q
q n * r Q
q o * r Q
q p * r Q
q q * r Q
q r * r Q
q s * r Q
q t * r Q
q u * r Q
q v * r Q
q w * r Q
q x * r Q
q y * r Q
q z * r Q
r * * l r
r _ * r R
r a * r R
r b * r R
r c * r R
r d * r R
r e * r R
r f * r R
r g * r R
r h * r R
r i * r R
r j * r R
r k * r R
r l * r R
r m * r R
r n * r R
r o * r R
r p * r R
r q * r R
r r * r R
r s * r R
r t * r R
r u * r R
r v * r R
r w * r R
r x * r R
r y * r R
r z * r R
s * * l s
s _ * r S
s a * r S
s b * r S
s c * r S
s d * r S
s e * r S
s f * r S
s g * r S
s h * r S
s i * r S
s j * r S
s k * r S
s l * r S
s m * r S
s n * r S
s o * r S
s p * r S
s q * r S
s r * r S
s s * r S
s t * r S
s u * r S
s v * r S
s w * r S
s x * r S
s y * r S
s z * r S
t * * l t
t _ * r T
t a * r T
t b * r T
t c * r T
t d * r T
t e * r T
t f * r T
t g * r T
t h * r T
t i * r T
t j * r T
t k * r T
t l * r T
t m * r T
t n * r T
t o * r T
t p * r T
t q * r T
t r * r T
t s * r T
t t * r T
t u * r T
t v * r T
t w * r T
t x * r T
t y * r T
t z * r T
u * * l u
u _ * r U
u a * r U
u b * r U
u c * r U
u d * r U
u e * r U
u f * r U
u g * r U
u h * r U
u i * r U
u j * r U
u k * r U
u l * r U
u m * r U
u n * r U
u o * r U
u p * r U
u q * r U
u r * r U
u s * r U
u t * r U
u u * r U
u v * r U
u w * r U
u x * r U
u y * r U
u z * r U
v * * l v
v _ * r V
v a * r V
v b * r V
v c * r V
v d * r V
v e * r V
v f * r V
v g * r V
v h * r V
v i * r V
v j * r V
v k * r V
v l * r V
v m * r V
v n * r V
v o * r V
v p * r V
v q * r V
v r * r V
v s * r V
v t * r V
v u * r V
v v * r V
v w * r V
v x * r V
v y * r V
v z * r V
w * * l w
w _ * r W
w a * r W
w b * r W
w c * r W
w d * r W
w e * r W
w f * r W
w g * r W
w h * r W
w i * r W
w j * r W
w k * r W
w l * r W
w m * r W
w n * r W
w o * r W
w p * r W
w q * r W
w r * r W
w s * r W
w t * r W
w u * r W
w v * r W
w w * r W
w x * r W
w y * r W
w z * r W
x * * l x
x _ * r X
x a * r X
x b * r X
x c * r X
x d * r X
x e * r X
x f * r X
x g * r X
x h * r X
x i * r X
x j * r X
x k * r X
x l * r X
x m * r X
x n * r X
x o * r X
x p * r X
x q * r X
x r * r X
x s * r X
x t * r X
x u * r X
x v * r X
x w * r X
x x * r X
x y * r X
x z * r X
y * * l y
y _ * r Y
y a * r Y
y b * r Y
y c * r Y
y d * r Y
y e * r Y
y f * r Y
y g * r Y
y h * r Y
y i * r Y
y j * r Y
y k * r Y
y l * r Y
y m * r Y
y n * r Y
y o * r Y
y p * r Y
y q * r Y
y r * r Y
y s * r Y
y t * r Y
y u * r Y
y v * r Y
y w * r Y
y x * r Y
y y * r Y
y z * r Y
z * * l z
z , * r Z
z a * r Z
z b * r Z
z c * r Z
z d * r Z
z e * r Z
z f * r Z
z g * r Z
z h * r Z
z i * r Z
z j * r Z
z k * r Z
z l * r Z
z m * r Z
z n * r Z
z o * r Z
z p * r Z
z q * r Z
z r * r Z
z s * r Z
z t * r Z
z u * r Z
z v * r Z
z w * r Z
z x * r Z
z y * r Z
z z * r Z
A * * * 5
A A * l 6
B * * * 5
B B * l 6
C * * * 5
C C * l 6
D * * * 5
D D * l 6
E * * * 5
E E * l 6
F * * * 5
F F * l 6
G * * * 5
G G * l 6
H * * * 5
H H * l 6
I * * * 5
I I * l 6
J * * * 5
J J * l 6
K * * * 5
K K * l 6
L * * * 5
L L * l 6
M * * * 5
M M * l 6
N * * * 5
N N * l 6
O * * * 5
O O * l 6
P * * * 5
P P * l 6
Q * * * 5
Q Q * l 6
R * * * 5
R R * l 6
S * * * 5
S S * l 6
T * * * 5
T T * l 6
U * * * 5
U U * l 6
V * * * 5
V V * l 6
W * * * 5
W W * l 6
X * * * 5
X X * l 6
Y * * * 5
Y Y * l 6
Z * * * 5
Z Z * l 6
5 , * r 15
5 A a r 7
5 B b r 7
5 C c r 7
5 D d r 7
5 E e r 7
5 F f r 7
5 G g r 7
5 H h r 7
5 I i r 7
5 J j r 7
5 K k r 7
5 L l r 7
5 M m r 7
5 N n r 7
5 O o r 7
5 P p r 7
5 Q q r 7
5 R r r 7
5 S s r 7
5 T t r 7
5 U u r 7
5 V v r 7
5 W w r 7
5 X x r 7
5 Y y r 7
5 Z z r 7
7 * * r 7
7 , * r 4
6 * * l 6
6 _ * r 8
8 * _ r 9
9 * * r 9
9 _ * l 10
9 a A r 9
9 b B r 9
9 c C r 9
9 d D r 9
9 e E r 9
9 f F r 9
9 g G r 9
9 h H r 9
9 i I r 9
9 j J r 9
9 k K r 9
9 l L r 9
9 m M r 9
9 n N r 9
9 o O r 9
9 p P r 9
9 q Q r 9
9 r R r 9
9 s S r 9
9 t T r 9
9 u U r 9
9 v V r 9
9 w W r 9
9 x X r 9
9 y Y r 9
9 z Z r 9
10 * * l 10
10 , * l 11
11 * * l 11
11 , * l 12
12 _ 1 r 2
12 0 1 r 2
12 1 2 r 2
12 2 3 r 2
12 3 4 r 2
12 4 5 r 2
12 5 6 r 2
12 6 7 r 2
12 7 8 r 2
12 8 9 r 2
12 9 0 l 12
13 * _ l 13
13 , _ l 14
14 * _ l 14
14 , _ l halt
15 * * r 15
15 _ * l 16
16 * _ l 16
16 , _ l 17
17 * _ l 17
17 , _ l 18
18 * _ l 18
18 _ x * halt

```

Test it out here

Brief overview:

1. Set up a counter on the left
2. Find first uppercase letter in target and make it lowercase. If all letters are lowercase move to step 5.
3. Find first uppercase letter in code. If most recent letter matches, move on to step 4. Else make letter lowercase and go back to step 2.
4. Increment counter, make all letters capital, delete first letter in code. Go back to step 2. If no letters are left in code, return clear tape and print x.
5. Clear all the tape but the counter.

# Answer
> 8 votes
# SWI-Prolog, 115 bytes

```
a(S,W,R):-length(S,L),length(W,M),N is L-M,between(0,N,I),\+ (between(0,M,J),K is I+J,nth0(J,W,A),nth0(K,S,A)),R=I.

```

Usage example: `a(`ABCDEFGHIJKL`,`HELLO`,R).`. This uses the character codes strings declared with backticks. The answer is unified with `R`. If no match is found, this outputs `false.`.

### Explanation:

```
a(S,W,R):-
    length(S,L),length(W,M),
    N is L-M,
    between(0,N,I),             % I is successively unified with an integer between 0
                                % and the last possible index of the coded message

    \+ (                        % This will only be true if what's inside the parentheses
                                % cannot be proven to be true

        between(0,M,J),         % J is successively unified with an integer between 0
                                % and the length of the desired word
        K is I+J,
        nth0(J,W,A),nth0(K,S,A) % Check if one letter is the same in both string at
                                % the same index
    ),                          % If it the case, then it will be 'true' and thus
                                % the predicate \+ will be false, meaning we need to
                                % backtrack to try a different value of I

    R=I.                        % If we get here it means it didn't find any matching
                                % letter for this value of I, which is then the answer.

```

Try it here

# Answer
> 7 votes
# CJam, ~~17~~ 16 bytes

```
ll:A,ew{A.=:+!}#

```

Try it here.

Thanks to @PeterTaylor for saving a byte.

Explanation:

```
ll:A,ew    e# Finds every slice in the coded message with the length of the word
{A.=:+     e# Compare the characters in each slice to the characters in the word, and add up the result. If the sum is zero, then the slice and the word have no characters in common.
!}#        e# Invert truthiness (0 -> 1, non-0 -> 0) Return index of first truthy value.

```

# Answer
> 7 votes
## Ruby, ~~91~~ 79 bytes

```
->a,b{[*a.chars.each_cons(b.size)].index{|x|x.zip(b.chars).all?{|y|y.uniq==y}}}

```

Curse you, `Enumerator`! Why do I have to convert from string to array to Enumerator to array and waste precious bytes? \>:(

```
->a,b{                  # define lambda
[*                      # convert to array...
  a.chars               # get enumerator from string
  .each_cons(b.size)    # each consecutive group of (b.size) letters
]
.index{|x|              # find index of...
  x.zip(b.chars)        # zip group with second input string
  .all?{|y|             # is the block true for every element?
    y.uniq==y           # uniqueify results in same array (no dups)
}}}

```

# Answer
> 6 votes
# MATL, 27 bytes

```
jYbZ)tnb!wlhYCw!=a~ftn?1)1-

```

### Examples

```
>> matl jYbZ)tnb!wlhYCw!=a~ftn?1)1-
> EEEEEEEEEEEE, HELLO

>> matl jYbZ)tnb!wlhYCw!=a~ftn?1)1-
> XEEFSLBSELDJMADNADKDPSSPRNEBWIENPF, DEUTSCHLAND
11

```

### Explanation

```
j           % input string
YbZ)        % split into two strings based on space. Trailing comma is not a problem
tnb!wlhYC   % arrange first string into sliding columns of the size of the second
w!=         % compare with transposed second string, element-wise with broadcast
a~          % detect columns where all values are 0 (meaning unequal characters)
f           % find indices of such columns
tn?         % if there's at least one such column
1)1-        % pick index of the first and subtract 1 for 0-based indexing

```

# Answer
> 4 votes
## Haskell, 72 bytes

```
l=length
h i w s|l s<l w= -1|and$zipWith(/=)w s=i|1<2=h(i+1)w$tail s
h 0

```

Usage: `h 0 "DEUTSCHLAND" "XEEFSLBSELDJMADNADKDPSSPRNEBWIENPF"` -\> `11`.

Simple recursive approach: if the word `w`can be placed at the beginning of the string `s`, return the index counter `i`, else repeat with `i` incremented and the tail of `s`. Stop and return `-1` if the length of `s` is less than the length of `w`.

# Answer
> 4 votes
## Python 2.7, 111 characters

Tries all starting positions (a) and checks of any of the letters match (using the list comprehension). It returns "None" (Python's "NULL") if nothing is found (the for loop end and nothing is returned, which defaults to "None".

```
def d(c,s):
 for a in range(len(c)):
  if a not in [((c+s)[a+i:]).index(l)+a for i,l in enumerate(s)]:
   return a

```

Testsuite:

```
cases = {
         ("BHGEFXWFTIUPITHHLPETTTCLOEWOELM","WETTERBERICHT"):13,
         ("ABCDEFGHIJKL","HELLO"):0,
         ("EEEEEEEEEEEE","HELLO"):-1,
         ("XEEFSLBSELDJMADNADKDPSSPRNEBWIENPF","DEUTSCHLAND"):11
        }

for idx,(code,string) in enumerate(cases):
    output=d(code,string)
    print "Case: {}: d({:<35},{:<16}) gives: {}. Correct answer is: {}.".format(idx+1,code,string,output,cases[(code,string)])

```

# Answer
> 4 votes
# Brachylog, 48 bytes

```
[S:W]hlL,WlM,L-M=:0reI,'(0:MeJ+I=:SrmA,W:JmA),I.

```

This is a direct translation of my Prolog answer. The `brachylog_main/2` generated predicate expects a list of two character codes strings with the coded string first as input, and returns the index as output, e.g. `brachylog_main([`ABCDEFGHIJKL`,`HELLO`],R).`.

### Explanation

```
[S:W]                                            § Unify the input with the list [S,W]

     hlL,WlM,                                    § L and M are the length of S and W

             L-M=:0reI,                          § Enumerate integers between 0 and the
                                                 § last possible index

                       '(                   ),I. § Unify the output with the current
                                                 § enumerated integer if what's inside the
                                                 § parenthesis cannot be proven to be true

                         0:MeJ                   § Enumerate integers between 0 and the
                                                 § length of the word desired

                              +I=:SrmA,W:JmA     § Check if both strings contain at matching
                                                 § indexes the same letter (unified with A)

```

# Answer
> 3 votes
# JavaScript, ~~129~~ ~~121~~ ~~118~~ ~~119<sup>*</sup>~~ 118 bytes

```
(w,t){for(j=0;(x=t.length)<(y=w.length);t=' '+t,j++){for(a=i=0;++i<y;)w[i]==t[i]?a=1:a;if(!a)break}return x==y?-1:j}

```

`w` is the coded message, `t` is the test string. This doesn't use regexes, but just compares letter by letter, shifting the test string (i.e. "WETTERBERICHT") by appending space before it. Easy and boring.

---

<sup>* test case with no match didn't work, now it does</sup>

# Answer
> 3 votes
# Japt, 12 bytes (non-competitive)

```
UàVr'."[^$&]

```

I'm gonna need some help with this one.

# Answer
> 3 votes
# 05AB1E, ~~14~~ ~~13~~ 11 bytes

```
ŒIgùÅΔø€Ëà≠

```

-1 byte thanks to *@ovs*.

Try it online or verify all test cases.

**Explanation:**

```
Œ            # Get all substrings of the first (implicit) input
 Ig          # Get the length of the second input
   ù         # Only leave the substrings of that length
    ÅΔ       # Find the first (0-based) index which is truthy for:
             # (which results in -1 if none are truthy)
      ø      #  Zip/transpose; create pairs of the characters in the current substring
             #  and the second (implicit) input
       €Ë    #  Check for each if both characters are equal (1 if truthy; 0 if falsey)
         à   #  Get the maximum (basically equal to an `any` builtin)
          ≠  #  And invert the boolean (!= 1)
             # (after which the result is output implicitly)

```

# Answer
> 2 votes
# PHP – 155 bytes

```
<?php for($p=$argv[1],$q=$argv[2],$l=strlen($q),$i=0,$r=-1;$i<strlen($p)-$l;$i++)if(levenshtein($q,substr($p,$i,$l),2,1,2)==$l){$r=$i;break;}echo$r."\n";

```

Save as `crack.php` and run with the arguments in the command line. E.g.:

```
$ php crack.php BHGEFXWFTIUPITHHLPETTTCLOEWOELM WETTERBERICHT
13

```

# Answer
> 2 votes
# TeaScript, 14 bytes ~~20~~

```
xc(yl#`[^${l}]

```

Similar to @aspillers clever JavaScript solution.

## Explanation

```
             // Implicit: x = 1st input, y = 2nd input
x            // First input
 c           // returns index of regex match
 yl#         // Loop through every char in `y`
    `[^${l}] // Replace template, ${l} because current char in `y`

```

# Answer
> 2 votes
# , 14 chars / 25 bytes

```
îĊⱮ(í,↪`⁅⦃$}]`

```

`Try it here (Firefox only).`

Kudos to @apsillers for the idea.

# Explanation

```
               // implicit: î = input1, í = input2
îĊ             // search for first occurrence of:
  Ɱ(í,↪`⁅⦃$}]` // regex created by wrapping each word in [^ and ] (negation matches)

```

# Answer
> 2 votes
# Ruby, ~~43~~ 36 bytes

edit: String interpolation inside string interpolation inside a regex, yikes.

The lazy approach: translates the word to a "negative" regex -- The `=~` operator does the rest.

```
->m,w{m=~/#{"[^#{w.chars*'][^'}]"}/}

```

Test:

```
f=->m,w{m=~/#{"[^#{w.chars*'][^'}]"}/}

require "minitest/autorun"

describe :f do
  it "works for the given test cases" do
    assert_equal 13, f["BHGEFXWFTIUPITHHLPETTTCLOEWOELM", "WETTERBERICHT"]
    assert_equal 0, f["ABCDEFGHIJKL", "HELLO"]
    assert_equal nil, f["EEEEEEEEEEEE", "HELLO"]
    assert_equal 11, f["XEEFSLBSELDJMADNADKDPSSPRNEBWIENPF", "DEUTSCHLAND"]
    assert_equal nil, f["HKKH", "JJJJJ"]
  end
end

```

# Answer
> 2 votes
# Python 3, 79 bytes

```
lambda x,y:[sum(map(str.__eq__,x[i:],y))for i in range(len(x)-len(y))].index(0)

```

Try it online!

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

```
{**&(#y)(~|/y=)':x}

```

Try it online!

Takes the encoded message as `x` and the word as `y`. Returns `0N` (the integer null) if no possible occurrence was found.

* `(#y)(~|/y=)':x` use `i f':x stencil` to apply `(~|/y=)` to each `(#y)`-length window of the input `x`
    + `(#y)` get the length of the input word
    + `(~|/y=)` check if any letters are in the same position in the word and the slice of the encoded message; then negate the resulting bitmask
* `**&` return the index of the first possible occurrence of the word in the encoded message

# Answer
> 2 votes
# Husk, ~~14~~ 13 bytes

Or **12 bytes** using 1-based indexing and returning `0` for no-occurrence.

```
←VoΠz≠⁰↓_L⁰ṫ²

```

Try it online!

```
←                   # subtract 1 to get 0-based indexing
 V                  # index of first element of
            ṫ²      # all suffixes of arg 2,
        ↓_          # with n elements removed from the end,
          L⁰        # where n is the length of arg 1,
                    # that satisfies
  ȯ¬                # NOT
    Σ               # any
     z=⁰            # elements are equal when zipped with arg 1

```

# Answer
> 2 votes
# Jelly, ~~9~~ 7 bytes

```
t"ƑÐƤi1

```

Try it online!

```
   ÐƤ      For each suffix,
  Ƒ        is it the same after
t          trimming off
 "         the corresponding letter of the word from each of its letters?
     i1    Find the first index of 1.

```

### Wait, what?

This beats the original, `W€ḟ"ƑÐƤi1`, by completely dropping the step of wrapping each letter into a singleton list. As for *how*:

A Jelly string is a list of characters, which is to say it's a Python list of length-1 Python strings. For example, `“this”` is really `["t","h","i","s"]`.

Most list builtins are built to handle lists whether that's what they got or not, by passing all arguments through `iterable`, and in the case of a single character this wraps it in a singleton list to obtain a length-1 Jelly string.  does this, and as a result its output is also always a list--so `ḟ"`, mapped over corresponding pairs, gives a list of lists, and for it to ever not change a suffix of the ciphertext each of its characters has to be pre-wrapped to match.

However, `t` *does not call `iterable` on its left argument*, so here `t"` operates on *the Python string characters themselves* of the ciphertext suffix, and either leaves them alone or trims them to `''`.

Finally, `Ƒ` performs a strict, non-vectorizing equality check, and `"` only maps its given link over pairs of corresponding elements up to the length of the shorter argument, placing the remainder of the longer argument into the result verbatim. If the ciphertext suffix is longer, the remainder automatically matches itself leaving only the prefix of length equal to the word to be considered, but if the word is longer, the result cannot be equal to the suffix because it is itself longer than the suffix.

# Answer
> 2 votes
# Vyxal, 20 bytes

```
:ǎ'⁰l;ƛ⁰Zƛ≈;aßn;~ḃhḟ

```

Try it Online!

I wrote this so long ago, waiting for  to work on strings, that I forgot how this even works

# Answer
> 1 votes
# Jolf, 14 bytes

Try it here!

```
 siρI".'[^$&]
_s            search
  i            input 1 for
    I          input 2
   ρ            replacing (2 byte rho character)
     ".'         all characters
        [^$&]    with that

```

# Answer
> 1 votes
# Perl, 38 + 1 = 39 bytes

```
perl -E "$r=<>=~s!.![^$&]!gr;say@-if<>=~/$r/x" < input

```

where input looks like:

```
WETTERBERICHT
BHGEFXWFTIUPITHHLPETTTCLOEWOELMRXXPAKAXMAMTXXUDLTWTNHKELEPPLHPRQ

```

This is the same idea as the javascript one.

# Answer
> 1 votes
## Java, 136 Characters

Regex-based solution inspired by apsillers JavaScript version.

```
class L{public static void main(String[]a){a=a[0].split(a[1].replaceAll("(.)","[^$1]"));System.out.print(a.length>1?a[0].length():-1);}}

```

# Answer
> 1 votes
# Brachylog (v2), ~~16~~ 13 bytes

```
{sʰz₂}ᶠ∋↙.≠ᵐ∧

```

Try it online!

Takes input as a list `[message, word]`. The header prints it all very prettily but the output of the actual predicate is just a 0-index if it succeeds and declarative failure if it doesn't.

```
{    }ᶠ          Find every possible
   z             zip of the word with
    ₂            an equal-length
 sʰ              contiguous substring of the ciphertext.
       ∋         One of those
          ≠ᵐ     contains no pair the elements of which are equal,
        ↙.  ∧    and its index is the output.

```

# Answer
> 1 votes
# Perl 5, 46 bytes

Uses @apsillers' regex idea.

```
$a=<>=~s/./[^$&]/gr;/$a/g;$_=(length$a)/-4+pos

```

Try it online!

# Answer
> 1 votes
# Jelly, ~~10~~ 9 bytes

```
ṡ⁹L¤=S€i0

```

Try it online!

Uses 1-indexing, which is Jelly's default. 10 bytes to use 0-indexing. This returns \\$0\\$ if no occurrence is found (\\$-1\\$ for the 0-indexed version)

## How it works

```
ṡ⁹L¤=S€i0 - Main link. Takes M on the left and W on the right
   ¤      - Create a nilad:
 ⁹        -   W
  L       -   Length
ṡ         - Overlapping slices of length W of M
    =     - Compare for equality with W
     S€   - Count the number of 1s in each
       i0 - First index of 0, else 0 if not found

```

# Answer
> 1 votes
# SM83/Z80, 30 bytes

First input (encrypted) in `hl`, second (unencrypted) in `de`. Output in `bc`.

```
01 00 00 E5 D5 09 7E A7
28 11 1A A7 28 0A BE 23
13 20 F3 03 D1 E1 18 EB
02 FF FF D1 E1 C9

```

```
ecr:
 ld bc,0                // 01 00 00 setup bc
oloop:
 push hl                // E5       store originals
 push de                // D5
 add hl,bc              // 09       handle offset
iloop:
 ld a,(hl)              // 7E
 and a                  // A7       test if at end of arg 2
 jr z,succ              // 28 11    if so succeed
 ld a,(de)              // 1A       load encrypted char
 and a                  // A7       if at end
 jr z,fail              // 28 0A    fail
 cp (hl)                // BE       compare to other side
 inc hl                 // 23
 inc de                 // 13       next char
 jr nz,iloop            // 20 F3    if unequal, loop
 inc bc                 // 03       else inc offset
 pop de                 // D1
 pop hl                 // E1       reload originals
 jr oloop               // 18 EB    and jump back
fail:
 ld bc,-1               // 02 FF FF insert failure
succ:
 pop de                 // D1
 pop hl                 // E1       reload original args
 ret                    // C9       return

```

# Answer
> 1 votes
# , 56 bytes

```
\(x,y)match(T,Map(\(i)all(x[i+seq(y)]!=y),seq(x)-1),0)-1
```

Attempt This Online!

Counterintuitively (at least to me), `match(TRUE,NA,nomatch=0)` returns `0`, rather than `NA`, but this is actually helpful here.
We could save 2 bytes (delete `-1`) by using R's native 1-based indexing; and a further 1 or 2 bytes by returning nothing (using `which()[1]`) or `NA` (delete `,0`) to indicate no occurrence.

# Answer
> 0 votes
# C++ (gcc), ~~160~~ ~~153~~ 150 bytes

```
#include<map>
int f(std::string c,std::string w){int i=-1,k,e=1;while(e&&w.size()+i++<c.size())for(e=k=0;k<w.size();)e+=c[i+k]==w[k++];return e?-1:i;}

```

Try it online!

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


title: High throughput prime numbers

text:
# Question
Title: High throughput prime numbers
This challenge is inspired by the High throughput Fizz Buzz challenge.

## The goal

Generate a list of prime numbers up to **10,000,000,000,000,000**. The output of primes should be in decimal digits followed by a newline character `'\n'` in ascending order starting from the lowest prime **2**. You may not skip a prime number or output a composite number.

## Scoring

Your program's throughput will be measured on my Linux machine by the following command.

```
(timeout 1m ./your-program) | pv > /dev/null

```

At the timeout after 1 minute, your score will be the total size of output measured by `pv`.

## An example

This is a simple example of a conforming program in C. It produces `49.6MiB` of data in total for a minute, on my machine with 2.4GHz 4-core CPU and 4GiB RAM.

```
#include <stdio.h>

int main() {
    puts("2");
    for (long long i = 3; i < 10000000000000000; i += 2) {
        for (long long j = 3; j * j <= i; j += 2) {
            if (i % j == 0) {
                goto next;
            }
        }
        printf("%lld\n", i);
    next:;
    }
    return 0;
}

```

## Rules

You should only print what's specified in **the goal**. You may not print garbage characters including ones that do not appear on the terminal.

The maximum size of your source code is `64Kib`.

Otherwise, I'll accept any code that can be run on my Linux machine with 4 cores and AVX2 support.

---

## Leaderboard

| Contestant | Language | Score |
| --- | --- | --- |
| xiver77 | C + asm | 9.71GiB |
| alephalpha | C + PARI/GP | 6.85GiB |
| Neil | C | 5.47GiB |
| Seggan | Jyxal | 120MiB |
| (example) | C | 56.2MiB |
| emanresu A | Vyxal | 21.8MiB |

# Answer
> 7 votes
# Vyxal, ~7.3Mb

```
0 { 200 ( ∆Ṗ : ) W ṫ $ ⁋,

```

Vyxal really isn't fast.

Because Vyxal is stack-based, an operation such as `1 +` (incrementing) is actually `push(1), push(add(pop(),pop()))`, which makes it incredibly difficult to optimize anything.

Vyxal uses Sympy's `isprime`, which looks for small factors, then for numbers \\$ n \< 2^{64}\\$ it runs a set of Miller-Rabin tests. In other words, no optimization there.

So, the above program optimizes by buffering the output into groups of 200, which through experimentation produces the most output.

This version

`{` is loop forever.  `200 ( ∆Ṗ : )` means "200 times, get the prime after the top of stack and push a copy of it". `W ṫ $` gets all but the last one (which we use for the next iteration of the forever loop), then `⁋,` prints that joined by newlines.

## Other attempts

## ~10Kb

```
0 {›:ǎ,

```

This one's "forever, print the nth prime and increment n". It's kinda slow.

## ~165Kb

```
0 { ∆Ṗ …

```

This one's "forever, get the next prime and print it". It's an order of magnitude faster than the previous, but still slow.

## ~780Kb

```
Þp(n,

```

5x faster than the previous, but still not very fast, this one loops through an infinite generator of primes and prints each one.

## ~4.3Mb

```
0 { ⟨⟩ →primes 100 ( ∆Ṗ : ←primes $ J →primes) ←primes ⁋ ,

```

Like the main submission but uses an array instead of the stack, making it slower.

* amounts approximated with online interpreter, unreliable

# Answer
> 6 votes
### C + assembly (nasm) 9.71GiB

I got to know a program called primesieve from a comment and was impressed to know that it can generate prime numbers so fast. Somehow the existence of the program triggered me in a weird way that I felt I should and can build a program that is faster than `primesieve`. I don't know why, but really *somehow* it felt like an easy opponent, and it wasn't. Over a month the goal of building a faster program than `primesieve` drained so much of my energy, but unfortunately, the best I could reach was about 0.8 times the speed of `primesieve` (1).

Well, I could still make a faster one if I just copy the same algorithm `primesieve` used, and apply some of optimization techniques I gathered while trying to beat it. Maybe I will do that later in time, but for now I feel that just re-implementing the same algorithm is not a fun task. Also, one of the reasons why I didn't use the same algorithm is because that algorithm is quite complex and thus difficult to implement it efficiently. I really thought a simpler approach will be faster, but now it is apparent why `primesieve` took the hard route of implementing such a complex algorithm. It was obviously worth it.

Anyway the simpler route still took me more than a month of my free time and a lot of sleeplessness. The result is just a slower program than `primesieve` but it is still enough as a fast program here.

I didn't do any IO optimizations, but just a loop of `printf`s. There are many ways to make the output faster, but I don't have the energy to do it now.

---

(1) If you're interested this is an alternative `main.c` which actually counts primes like `primesieve`. The gap in speed is about 10~30%, which gets bigger as the sieving range gets larger, which is why my choice of algorithm was wrong and `primesieve`'s was right.

#### prime.h

```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <inttypes.h>
#include <math.h>
#include <unistd.h>

typedef unsigned char v16b
__attribute__((vector_size(16), aligned(16), may_alias));

extern unsigned BC;
extern unsigned L1C;
extern unsigned char PADD[];
extern unsigned char WIX[];
extern unsigned char countPrimes_bf[];
extern unsigned char countPrimes_rm[];
extern v16b sieve_7_13_M7[];
extern v16b sieve_7_13_M11[];
extern v16b sieve_7_13_M13[];

void sieve_7_13(unsigned char *, uint64_t);
void sieve_17(unsigned char *, uint64_t);
void sieve_19(unsigned char *, uint64_t);
void sieve_23(unsigned char *, uint64_t);
void sieve_29(unsigned char *, uint64_t);
void sieve_31(unsigned char *, uint64_t);
void sieve_37(unsigned char *, uint64_t);
void sieve_41(unsigned char *, uint64_t);
void sieve_43(unsigned char *, uint64_t);
void sieve_47(unsigned char *, uint64_t);
void sieve_53(unsigned char *, uint64_t);
void sieve_59(unsigned char *, uint64_t);
void sieve_61(unsigned char *, uint64_t);
void sieve_67(unsigned char *, uint64_t);
void sieve_71(unsigned char *, uint64_t);
void sieve_73(unsigned char *, uint64_t);
void sieve_79(unsigned char *, uint64_t);
void sieve_83(unsigned char *, uint64_t);
void sieve_89(unsigned char *, uint64_t);
void sieve_93_(unsigned char *, uint64_t, uint32_t *, unsigned);

static inline uint64_t sq(uint64_t a) {
    return a * a;
}

```

#### main.c

```
#include "prime.h"

typedef struct {
    uint64_t p;
    uint64_t sp;
} np_t;

static np_t fillBase(uint32_t *p, np_t n, unsigned char *f, uint64_t st,
uint64_t end, uint64_t lim) {
    #define push(a) do {\
        *p_ = st + i * 30 + a;\
        if (*p_ < L1C / 8) ++n.sp;\
        if (sq(*p_++) > lim) return (np_t){p_ - p + n.p, n.sp};\
    } while (0)
    p += n.p;
    uint32_t *p_ = p;
    unsigned i = 0;
    do {
        if (f[i] & 1 << 0) {
            push(1);
        }
        if (f[i] & 1 << 1) {
            push(7);
        }
        if (f[i] & 1 << 2) {
            push(11);
        }
        if (f[i] & 1 << 3) {
            push(13);
        }
        if (f[i] & 1 << 4) {
            push(17);
        }
        if (f[i] & 1 << 5) {
            push(19);
        }
        if (f[i] & 1 << 6) {
            push(23);
        }
        if (f[i] & 1 << 7) {
            push(29);
        }
    } while (st + ++i * 30 < end);
    return (np_t){p_ - p + n.p, n.sp};
    #undef push
}

static void sieve(unsigned char *f, uint64_t st, uint32_t *p, unsigned nsp) {
    memset(f, -1, BC);
    unsigned i = 0;
    do {
        uint64_t sti30 = st + i * 30;
        sieve_7_13(f + i, sti30);
        sieve_17(f + i, sti30);
        sieve_19(f + i, sti30);
        sieve_23(f + i, sti30);
        sieve_29(f + i, sti30);
        sieve_31(f + i, sti30);
        sieve_37(f + i, sti30);
        sieve_41(f + i, sti30);
        sieve_43(f + i, sti30);
        sieve_47(f + i, sti30);
        sieve_53(f + i, sti30);
        sieve_59(f + i, sti30);
        sieve_61(f + i, sti30);
        sieve_67(f + i, sti30);
        sieve_71(f + i, sti30);
        sieve_73(f + i, sti30);
        sieve_79(f + i, sti30);
        sieve_83(f + i, sti30);
        sieve_89(f + i, sti30);
        sieve_93_(f + i, sti30, p, nsp);
    } while ((i += L1C) < BC);
    sieve_93_(f, st, p + nsp, -1);
}

static void print(unsigned char *f, uint64_t st) {
    #define p(a) printf("%"PRIu64"\n", st + i * 30 + a);
    uint64_t i = 0;
    do {
        if (f[i] & 1 << 0) {
            p(1);
        }
        if (f[i] & 1 << 1) {
            p(7);
        }
        if (f[i] & 1 << 2) {
            p(11);
        }
        if (f[i] & 1 << 3) {
            p(13);
        }
        if (f[i] & 1 << 4) {
            p(17);
        }
        if (f[i] & 1 << 5) {
            p(19);
        }
        if (f[i] & 1 << 6) {
            p(23);
        }
        if (f[i] & 1 << 7) {
            p(29);
        }
    } while (++i < BC);
    #undef p
}

static void printPrimes(uint64_t lim) {
    _Alignas(64) unsigned char f[BC + 256];
    uint32_t *p = aligned_alloc(64, sqrt(lim));
    unsigned bfsz = 256;
    np_t n = fillBase(p, (np_t){0}, countPrimes_bf, 0, bfsz * 30, -1);
    sieve(f, 0, p, n.sp);
    *f &= ~1;
    print(f, 0);
    unsigned r = lim % 30;
    if (!r) {
        --lim;
    } else if (1 < r && r < 7) {
        lim -= r - 1;
    } else if (7 < r && r < 11) {
        lim -= r - 7;
    } else if (13 < r && r < 17) {
        lim -= r - 13;
    } else if (r == 18) {
        --lim;
    } else if (19 < r && r < 23) {
        lim -= r - 19;
    } else if (23 < r && r < 29) {
        lim -= r - 23;
    }
    unsigned bc30 = BC * 30;
    r = lim % bc30;
    uint64_t lim_ = lim - r + bc30;
    n = fillBase(p, n, f + bfsz, bfsz * 30, bc30, lim_);
    uint64_t st = bc30;
    for (; st + bc30 < lim_; st += bc30) {
        sieve(f, st, p, n.sp);
        if (sq(st + 1) < lim_) {
            n = fillBase(p, n, f, st, st + bc30, lim_);
        }
        print(f, st);
    }
    sieve(f, st, p, n.sp);
    unsigned q = r / 30;
    memset(f + q + 1, 0, BC - q);
    f[q] &= countPrimes_rm[r % 30 / 2];
    print(f, st);
}

int main() {
    L1C = sysconf(_SC_LEVEL1_DCACHE_SIZE) - (1 << 12);
    BC = L1C * 8;
    puts("2\n3\n5\n7\n11\n13");
    printPrimes(1e16);
    return 0;
}

```

#### lut.s

```
    align 16
global PADD
PADD:
    db 1, 7, 7, 7, 7, 7, 7, 11, 11, 11, 11, 13, 13, 17, 17, 17, 17
    db 19, 19, 23, 23, 23, 23, 29, 29, 29, 29, 29, 29, 31, -1, -1
global WIX
WIX:
    db 0, -1, -1, 1, -1, 2, 3, -1, 4, 5, -1, 6, -1, -1, 7, -1
global countPrimes_bf
countPrimes_bf:
    dq 0xf93ddbb67e000000, 0x9eeda6eaf31e4fd5, 0xa559dd3bd3d30ce6
    dq 0x56a61e78bd92676a, 0x554c2ade2dade356, 0xf8a154039ff0a3d9,
    dq 0x3a13f666e944fd2e, 0x54bf11453a2b4cb8, 0x4f8cbcc8b37ac18c,
    dq 0xef17c19b71715821, 0x468c83e5081a9654, 0x87588f9265aefb72,
    dq 0xa0e3266581d892d2, 0x99eb813c26c73811, 0x4d33f3243e88518d,
    dq 0x4c58b42aa71c8b5a, 0xc383dc8219f6264e, 0x02cdcdb50238f12c,
    dq 0x307a4c570c944ab2, 0xf8246c44cbf10b43, 0x8dea735ca8950119,
    dq 0xc41e22a6502b9624, 0x9c742f3ad40648d1, 0x2e1568bf88056a07,
    dq 0x14089851b7e35560, 0x2770494d45aa5a86, 0x618302abcad593d2,
    dq 0xada9c22287ce2405, 0xb01689d1784d8c18, 0x522434c0a262c757,
    dq 0x4308218d32405aae, 0x60e119d9b6d2b634
global countPrimes_rm
countPrimes_rm:
    db 0x01, 0, 0, 0x03, 0, 0x07, 0x0f, 0, 0x1f, 0x3f, 0, 0x7f, 0, 0, 0xff, 0
global sieve_7_13_M7
sieve_7_13_M7:
    db 0xfd, 0xdf, 0xef, 0x7e, 0xf7, 0xfb, 0xbf, 0xfd, 0xdf, 0xef, 0x7e, 0xf7
    db 0xfb, 0xbf, 0xfd, 0xdf
    db 0xef, 0x7e, 0xf7, 0xfb, 0xbf, 0xfd, 0xdf, 0xef, 0x7e, 0xf7, 0xfb, 0xbf
    db 0xfd, 0xdf, 0xef, 0x7e
    db 0xf7, 0xfb, 0xbf, 0xfd, 0xdf, 0xef, 0x7e, 0xf7, 0xfb, 0xbf, 0xfd, 0xdf
    db 0xef, 0x7e, 0xf7, 0xfb
    db 0xbf, 0xfd, 0xdf, 0xef, 0x7e, 0xf7, 0xfb, 0xbf, 0xfd, 0xdf, 0xef, 0x7e
    db 0xf7, 0xfb, 0xbf, 0xfd
    db 0xdf, 0xef, 0x7e, 0xf7, 0xfb, 0xbf, 0xfd, 0xdf, 0xef, 0x7e, 0xf7, 0xfb
    db 0xbf, 0xfd, 0xdf, 0xef
    db 0x7e, 0xf7, 0xfb, 0xbf, 0xfd, 0xdf, 0xef, 0x7e, 0xf7, 0xfb, 0xbf, 0xfd
    db 0xdf, 0xef, 0x7e, 0xf7
    db 0xfb, 0xbf, 0xfd, 0xdf, 0xef, 0x7e, 0xf7, 0xfb, 0xbf, 0xfd, 0xdf, 0xef
    db 0x7e, 0xf7, 0xfb, 0xbf
global sieve_7_13_M11
sieve_7_13_M11:
    db 0xfb, 0xff, 0xef, 0xff, 0xbe, 0xff, 0x7d, 0xff, 0xf7, 0xff, 0xdf, 0xfb
    db 0xff, 0xef, 0xff, 0xbe
    db 0xff, 0x7d, 0xff, 0xf7, 0xff, 0xdf, 0xfb, 0xff, 0xef, 0xff, 0xbe, 0xff
    db 0x7d, 0xff, 0xf7, 0xff
    db 0xdf, 0xfb, 0xff, 0xef, 0xff, 0xbe, 0xff, 0x7d, 0xff, 0xf7, 0xff, 0xdf
    db 0xfb, 0xff, 0xef, 0xff
    db 0xbe, 0xff, 0x7d, 0xff, 0xf7, 0xff, 0xdf, 0xfb, 0xff, 0xef, 0xff, 0xbe
    db 0xff, 0x7d, 0xff, 0xf7
    db 0xff, 0xdf, 0xfb, 0xff, 0xef, 0xff, 0xbe, 0xff, 0x7d, 0xff, 0xf7, 0xff
    db 0xdf, 0xfb, 0xff, 0xef
    db 0xff, 0xbe, 0xff, 0x7d, 0xff, 0xf7, 0xff, 0xdf, 0xfb, 0xff, 0xef, 0xff
    db 0xbe, 0xff, 0x7d, 0xff
    db 0xf7, 0xff, 0xdf, 0xfb, 0xff, 0xef, 0xff, 0xbe, 0xff, 0x7d, 0xff, 0xf7
    db 0xff, 0xdf, 0xfb, 0xff
    db 0xef, 0xff, 0xbe, 0xff, 0x7d, 0xff, 0xf7, 0xff, 0xdf, 0xfb, 0xff, 0xef
    db 0xff, 0xbe, 0xff, 0x7d
    db 0xff, 0xf7, 0xff, 0xdf, 0xfb, 0xff, 0xef, 0xff, 0xbe, 0xff, 0x7d, 0xff
    db 0xf7, 0xff, 0xdf, 0xfb
    db 0xff, 0xef, 0xff, 0xbe, 0xff, 0x7d, 0xff, 0xf7, 0xff, 0xdf, 0xfb, 0xff
    db 0xef, 0xff, 0xbe, 0xff
    db 0x7d, 0xff, 0xf7, 0xff, 0xdf, 0xfb, 0xff, 0xef, 0xff, 0xbe, 0xff, 0x7d
    db 0xff, 0xf7, 0xff, 0xdf
global sieve_7_13_M13
sieve_7_13_M13:
    db 0xf7, 0xff, 0xff, 0xfe, 0xbf, 0xdf, 0xff, 0xfb, 0xfd, 0x7f, 0xff, 0xff
    db 0xef, 0xf7, 0xff, 0xff
    db 0xfe, 0xbf, 0xdf, 0xff, 0xfb, 0xfd, 0x7f, 0xff, 0xff, 0xef, 0xf7, 0xff
    db 0xff, 0xfe, 0xbf, 0xdf
    db 0xff, 0xfb, 0xfd, 0x7f, 0xff, 0xff, 0xef, 0xf7, 0xff, 0xff, 0xfe, 0xbf
    db 0xdf, 0xff, 0xfb, 0xfd
    db 0x7f, 0xff, 0xff, 0xef, 0xf7, 0xff, 0xff, 0xfe, 0xbf, 0xdf, 0xff, 0xfb
    db 0xfd, 0x7f, 0xff, 0xff
    db 0xef, 0xf7, 0xff, 0xff, 0xfe, 0xbf, 0xdf, 0xff, 0xfb, 0xfd, 0x7f, 0xff
    db 0xff, 0xef, 0xf7, 0xff
    db 0xff, 0xfe, 0xbf, 0xdf, 0xff, 0xfb, 0xfd, 0x7f, 0xff, 0xff, 0xef, 0xf7
    db 0xff, 0xff, 0xfe, 0xbf
    db 0xdf, 0xff, 0xfb, 0xfd, 0x7f, 0xff, 0xff, 0xef, 0xf7, 0xff, 0xff, 0xfe
    db 0xbf, 0xdf, 0xff, 0xfb
    db 0xfd, 0x7f, 0xff, 0xff, 0xef, 0xf7, 0xff, 0xff, 0xfe, 0xbf, 0xdf, 0xff
    db 0xfb, 0xfd, 0x7f, 0xff
    db 0xff, 0xef, 0xf7, 0xff, 0xff, 0xfe, 0xbf, 0xdf, 0xff, 0xfb, 0xfd, 0x7f
    db 0xff, 0xff, 0xef, 0xf7
    db 0xff, 0xff, 0xfe, 0xbf, 0xdf, 0xff, 0xfb, 0xfd, 0x7f, 0xff, 0xff, 0xef
    db 0xf7, 0xff, 0xff, 0xfe
    db 0xbf, 0xdf, 0xff, 0xfb, 0xfd, 0x7f, 0xff, 0xff, 0xef, 0xf7, 0xff, 0xff
    db 0xfe, 0xbf, 0xdf, 0xff
    db 0xfb, 0xfd, 0x7f, 0xff, 0xff, 0xef, 0xf7, 0xff, 0xff, 0xfe, 0xbf, 0xdf
    db 0xff, 0xfb, 0xfd, 0x7f
    db 0xff, 0xff, 0xef, 0xf7, 0xff, 0xff, 0xfe, 0xbf, 0xdf, 0xff, 0xfb, 0xfd
    db 0x7f, 0xff, 0xff, 0xef

section .bss
global L1C
L1C:
    resb 4
global BC
BC:
    resb 4

```

#### sieve\_7\_13.c

```
#include "prime.h"

#define am7(_0, _1, _2, _3, _4, _5, _6) do {\
    m0 = M7[_0]; m1 = M7[_1]; m2 = M7[_2]; m3 = M7[_3]; m4 = M7[_4];\
    m5 = M7[_5]; m6 = M7[_6];\
} while (0)

#define am11(_0, _1, _2, _3, _4, _5, _6, _7, _8, _9, _10) do {\
    m0 = M11[_0]; m1 = M11[_1]; m2 = M11[_2]; m3 = M11[_3]; m4 = M11[_4];\
    m5 = M11[_5]; m6 = M11[_6]; m7 = M11[_7]; m8 = M11[_8]; m9 = M11[_9];\
    m10 = M11[_10];\
} while (0)

#define am13(_0, _1, _2, _3, _4, _5, _6, _7, _8, _9, _10, _11, _12) do {\
    m0 = M13[_0]; m1 = M13[_1]; m2 = M13[_2]; m3 = M13[_3]; m4 = M13[_4];\
    m5 = M13[_5]; m6 = M13[_6]; m7 = M13[_7]; m8 = M13[_8]; m9 = M13[_9];\
    m10 = M13[_10]; m11 = M13[_11]; m12 = M13[_12];\
} while (0)

void sieve_7_13(unsigned char *f, uint64_t st) {
    static const void *L[] = {
        &&_7_0, &&_7_1, &&_7_2, &&_7_3, &&_7_4, &&_7_5, &&_7_6,
        &&_11_0, &&_11_1, &&_11_2, &&_11_3, &&_11_4, &&_11_5, &&_11_6, &&_11_7,
        &&_11_8, &&_11_9, &&_11_10,
        &&_13_0, &&_13_1, &&_13_2, &&_13_3, &&_13_4, &&_13_5, &&_13_6, &&_13_7,
        &&_13_8, &&_13_9, &&_13_10, &&_13_11, &&_13_12
    };
    uint64_t stb = st / 30;
    v16b *M7 = sieve_7_13_M7;
    v16b *M11 = sieve_7_13_M11;
    v16b *M13 = sieve_7_13_M13;
    v16b m0, m1, m2, m3, m4, m5, m6, m7, m8, m9, m10, m11, m12;
    v16b *vf;
    goto *L[stb % 7];
_7_0:
    am7(0, 1, 2, 3, 4, 5, 6);
    goto _7;
_7_1:
    am7(4, 5, 6, 0, 1, 2, 3);
    goto _7;
_7_2:
    am7(1, 2, 3, 4, 5, 6, 0);
    goto _7;
_7_3:
    am7(5, 6, 0, 1, 2, 3, 4);
    goto _7;
_7_4:
    am7(2, 3, 4, 5, 6, 0, 1);
    goto _7;
_7_5:
    am7(6, 0, 1, 2, 3, 4, 5);
    goto _7;
_7_6:
    am7(3, 4, 5, 6, 0, 1, 2);
_7:
    vf = (v16b *)f;
    do {
        vf[0] &= m0;
        vf[1] &= m1;
        vf[2] &= m2;
        vf[3] &= m3;
        vf[4] &= m4;
        vf[5] &= m5;
        vf[6] &= m6;
    } while ((unsigned char *)(vf += 7) < f + L1C);
    goto *(L + 7)[stb % 11];
_11_0:
    am11(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
    goto _11;
_11_1:
    am11(9, 10, 0, 1, 2, 3, 4, 5, 6, 7, 8);
    goto _11;
_11_2:
    am11(7, 8, 9, 10, 0, 1, 2, 3, 4, 5, 6);
    goto _11;
_11_3:
    am11(3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 2);
    goto _11;
_11_4:
    am11(5, 6, 7, 8, 9, 10, 0, 1, 2, 3, 4);
    goto _11;
_11_5:
    am11(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0);
    goto _11;
_11_6:
    am11(10, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9);
    goto _11;
_11_7:
    am11(8, 9, 10, 0, 1, 2, 3, 4, 5, 6, 7);
    goto _11;
_11_8:
    am11(6, 7, 8, 9, 10, 0, 1, 2, 3, 4, 5);
    goto _11;
_11_9:
    am11(4, 5, 6, 7, 8, 9, 10, 0, 1, 2, 3);
    goto _11;
_11_10:
    am11(2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1);
_11:
    vf = (v16b *)f;
    do {
        vf[0] &= m0;
        vf[1] &= m1;
        vf[2] &= m2;
        vf[3] &= m3;
        vf[4] &= m4;
        vf[5] &= m5;
        vf[6] &= m6;
        vf[7] &= m7;
        vf[8] &= m8;
        vf[9] &= m9;
        vf[10] &= m10;
    } while ((unsigned char *)(vf += 11) < f + L1C);
    goto *(L + 18)[stb % 13];
_13_0:
    am13(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12);
    goto _13;
_13_1:
    am13(9, 10, 11, 12, 0, 1, 2, 3, 4, 5, 6, 7, 8);
    goto _13;
_13_2:
    am13(5, 6, 7, 8, 9, 10, 11, 12, 0, 1, 2, 3, 4);
    goto _13;
_13_3:
    am13(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 0);
    goto _13;
_13_4:
    am13(10, 11, 12, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9);
    goto _13;
_13_5:
    am13(6, 7, 8, 9, 10, 11, 12, 0, 1, 2, 3, 4, 5);
    goto _13;
_13_6:
    am13(2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 0, 1);
    goto _13;
_13_7:
    am13(11, 12, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
    goto _13;
_13_8:
    am13(7, 8, 9, 10, 11, 12, 0, 1, 2, 3, 4, 5, 6);
    goto _13;
_13_9:
    am13(3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 0, 1, 2);
    goto _13;
_13_10:
    am13(12, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11);
    goto _13;
_13_11:
    am13(8, 9, 10, 11, 12, 0, 1, 2, 3, 4, 5, 6, 7);
    goto _13;
_13_12:
    am13(4, 5, 6, 7, 8, 9, 10, 11, 12, 0, 1, 2, 3);
_13:
    vf = (v16b *)f;
    do {
        vf[0] &= m0;
        vf[1] &= m1;
        vf[2] &= m2;
        vf[3] &= m3;
        vf[4] &= m4;
        vf[5] &= m5;
        vf[6] &= m6;
        vf[7] &= m7;
        vf[8] &= m8;
        vf[9] &= m9;
        vf[10] &= m10;
        vf[11] &= m11;
        vf[12] &= m12;
    } while ((unsigned char *)(vf += 13) < f + L1C);
}

```

#### sieve\_17\_89.c

```
#include "prime.h"

#define eb8(c0, c1, c2, c3, c4, c5, c6, c7, d1, d2, d3, d4, d5, d6, d7) do {\
    *f_ &= ~(1 << c0);\
    f_[q * 3 + d1] &= ~(1 << c1);\
    f_[q * 5 + d2] &= ~(1 << c2);\
    f_[q * 6 + d3] &= ~(1 << c3);\
    f_[q * 8 + d4] &= ~(1 << c4);\
    f_[q * 9 + d5] &= ~(1 << c5);\
    f_[q * 11 + d6] &= ~(1 << c6);\
    f_[q * 14 + d7] &= ~(1 << c7);\
} while (0)

#define eb(m, i, a) do {\
    *f_ &= ~(1 << i);\
    if ((f_ += q * m + a) >= f + c) return;\
} while (0)

#define eb0(i, a) eb(3, i, a)
#define eb1(i, a) eb(2, i, a)
#define eb2(i, a) eb(1, i, a)
#define eb3(i, a) eb(2, i, a)
#define eb4(i, a) eb(1, i, a)
#define eb5(i, a) eb(2, i, a)
#define eb6(i, a) eb(3, i, a)
#define eb7(i, a) eb(1, i, a)

static void sieve(unsigned char *f, uint64_t st, unsigned p) {
    unsigned c = L1C;
    uint64_t psq = sq(p);
    int64_t d = psq - st;
    unsigned char *f_ = f;
    unsigned w;
    if (__builtin_expect(psq > st, 0)) {
        f_ += (unsigned)d / 30;
        w = WIX[p % 30 / 2];
    } else {
        uint64_t p30 = (uint64_t)p * 30;
        uint64_t n = st / p30 * 30 + PADD[st % p30 / p];
        f_ += (unsigned)(p * n - st) / 30;
        w = WIX[n % 30 / 2];
    }
    unsigned q = p / 30 * 2;
    switch (p % 30) {
    case 1:
        switch (w) {
            for (;;) {
            case 0:
                for (; f_ + p < f + c; f_ += p) {
                    eb8(0, 1, 2, 3, 4, 5, 6, 7, 0, 0, 0, 0, 0, 0, 0);
                }
                eb0(0, 0);
            case 1:
                eb1(1, 0);
            case 2:
                eb2(2, 0);
            case 3:
                eb3(3, 0);
            case 4:
                eb4(4, 0);
            case 5:
                eb5(5, 0);
            case 6:
                eb6(6, 0);
            case 7:
                eb7(7, 1);
            }
        default:
            __builtin_unreachable();
        }
    case 7:
        switch (w) {
            for (;;) {
            case 0:
                for (; f_ + p < f + c; f_ += p) {
                    eb8(1, 5, 4, 0, 7, 3, 2, 6, 1, 2, 3, 3, 4, 5, 6);
                }
                eb0(1, 1);
            case 1:
                eb1(5, 1);
            case 2:
                eb2(4, 1);
            case 3:
                eb3(0, 0);
            case 4:
                eb4(7, 1);
            case 5:
                eb5(3, 1);
            case 6:
                eb6(2, 1);
            case 7:
                eb7(6, 1);
            }
        default:
            __builtin_unreachable();
        }
    case 11:
        switch (w) {
            for (;;) {
            case 0:
                for (; f_ + p < f + c; f_ += p) {
                    eb8(2, 4, 0, 6, 1, 7, 3, 5, 2, 4, 4, 6, 6, 8, 10);
                }
                eb0(2, 2);
            case 1:
                eb1(4, 2);
            case 2:
                eb2(0, 0);
            case 3:
                eb3(6, 2);
            case 4:
                eb4(1, 0);
            case 5:
                eb5(7, 2);
            case 6:
                eb6(3, 2);
            case 7:
                eb7(5, 1);
            }
        default:
            __builtin_unreachable();
        }
    case 13:
        switch (w) {
            for (;;) {
            case 0:
                for (; f_ + p < f + c; f_ += p) {
                    eb8(3, 0, 6, 5, 2, 1, 7, 4, 3, 4, 5, 7, 8, 9, 12);
                }
                eb0(3, 3);
            case 1:
                eb1(0, 1);
            case 2:
                eb2(6, 1);
            case 3:
                eb3(5, 2);
            case 4:
                eb4(2, 1);
            case 5:
                eb5(1, 1);
            case 6:
                eb6(7, 3);
            case 7:
                eb7(4, 1);
            }
        default:
            __builtin_unreachable();
        }
    case 17:
        switch (w) {
            for (;;) {
            case 0:
                for (; f_ + p < f + c; f_ += p) {
                    eb8(4, 7, 1, 2, 5, 6, 0, 3, 3, 6, 7, 9, 10, 13, 16);
                }
                eb0(4, 3);
            case 1:
                eb1(7, 3);
            case 2:
                eb2(1, 1);
            case 3:
                eb3(2, 2);
            case 4:
                eb4(5, 1);
            case 5:
                eb5(6, 3);
            case 6:
                eb6(0, 3);
            case 7:
                eb7(3, 1);
            }
        default:
            __builtin_unreachable();
        }
    case 19:
        switch (w) {
            for (;;) {
            case 0:
                for (; f_ + p < f + c; f_ += p) {
                    eb8(5, 3, 7, 1, 6, 0, 4, 2, 4, 6, 8, 10, 12, 14, 18);
                }
                eb0(5, 4);
            case 1:
                eb1(3, 2);
            case 2:
                eb2(7, 2);
            case 3:
                eb3(1, 2);
            case 4:
                eb4(6, 2);
            case 5:
                eb5(0, 2);
            case 6:
                eb6(4, 4);
            case 7:
                eb7(2, 1);
            }
        default:
            __builtin_unreachable();
        }
    case 23:
        switch (w) {
            for (;;) {
            case 0:
                for (; f_ + p < f + c; f_ += p) {
                    eb8(6, 2, 3, 7, 0, 4, 5, 1, 5, 8, 9, 13, 14, 17, 22);
                }
                eb0(6, 5);
            case 1:
                eb1(2, 3);
            case 2:
                eb2(3, 1);
            case 3:
                eb3(7, 4);
            case 4:
                eb4(0, 1);
            case 5:
                eb5(4, 3);
            case 6:
                eb6(5, 5);
            case 7:
                eb7(1, 1);
            }
        default:
            __builtin_unreachable();
        }
    case 29:
        switch (w) {
            for (;;) {
            case 0:
                for (; f_ + p < f + c; f_ += p) {
                    eb8(7, 6, 5, 4, 3, 2, 1, 0, 6, 10, 12, 16, 18, 22, 28);
                }
                eb0(7, 6);
            case 1:
                eb1(6, 4);
            case 2:
                eb2(5, 2);
            case 3:
                eb3(4, 4);
            case 4:
                eb4(3, 2);
            case 5:
                eb5(2, 4);
            case 6:
                eb6(1, 6);
            case 7:
                eb7(0, 1);
            }
        default:
            __builtin_unreachable();
        }
    default:
        __builtin_unreachable();
    }
}

void sieve_17(unsigned char *f, uint64_t st) {
    sieve(f, st, 17);
}

void sieve_19(unsigned char *f, uint64_t st) {
    sieve(f, st, 19);
}

void sieve_23(unsigned char *f, uint64_t st) {
    sieve(f, st, 23);
}

void sieve_29(unsigned char *f, uint64_t st) {
    sieve(f, st, 29);
}

void sieve_31(unsigned char *f, uint64_t st) {
    sieve(f, st, 31);
}

void sieve_37(unsigned char *f, uint64_t st) {
    sieve(f, st, 37);
}

void sieve_41(unsigned char *f, uint64_t st) {
    sieve(f, st, 41);
}

void sieve_43(unsigned char *f, uint64_t st) {
    sieve(f, st, 43);
}

void sieve_47(unsigned char *f, uint64_t st) {
    sieve(f, st, 47);
}

void sieve_53(unsigned char *f, uint64_t st) {
    sieve(f, st, 53);
}

void sieve_59(unsigned char *f, uint64_t st) {
    sieve(f, st, 59);
}

void sieve_61(unsigned char *f, uint64_t st) {
    sieve(f, st, 61);
}

void sieve_67(unsigned char *f, uint64_t st) {
    sieve(f, st, 67);
}

void sieve_71(unsigned char *f, uint64_t st) {
    sieve(f, st, 71);
}

void sieve_73(unsigned char *f, uint64_t st) {
    sieve(f, st, 73);
}

void sieve_79(unsigned char *f, uint64_t st) {
    sieve(f, st, 79);
}

void sieve_83(unsigned char *f, uint64_t st) {
    sieve(f, st, 83);
}

void sieve_89(unsigned char *f, uint64_t st) {
    sieve(f, st, 89);
}

```

#### sieve\_93\_.s

```
%define MD30 -2004318071
%define MD30Q -8608480567731124087

%define f rdi
%define st rsi
%define pp r8
%define nsp ecx
%define c r9
%define c_d r9d
%define fc r9
%define p r10
%define p_d r10d
%define f_ r11
%define q r12
%define fp r13
%define psq rbx
%define d rbp
%define d_d ebp
%define md30 rsp
%define md30_d esp
%define w rbx
%define w_d ebx

%macro eb8 16
    mov fp, f_
    add fp, p
    cmp fp, fc
    jae _%1_0_
    lea rax, [q + q * 2 + %10]
    lea rbx, [q + q * 4 + %11]
    lea rdx, [rax * 2 + %12]
    lea rbp, [q * 8 + %13]
    lea rsp, [q + q * 8 + %14]
    lea r14, [rax + q * 8 + %15]
    lea r15, [rdx + q * 8 + %16]
    jmp _%1_0_1
_%1_0_0:
    mov fp, f_
    add fp, p
    cmp fp, fc
    jae _%1_0_
_%1_0_1:
    and byte [f_], ~(1 << %2)
    and byte [f_ + rax], ~(1 << %3)
    and byte [f_ + rbx], ~(1 << %4)
    and byte [f_ + rdx], ~(1 << %5)
    and byte [f_ + rbp], ~(1 << %6)
    and byte [f_ + rsp], ~(1 << %7)
    and byte [f_ + r14], ~(1 << %8)
    and byte [f_ + r15], ~(1 << %9)
    mov f_, fp
    jmp _%1_0_0
%endmacro

%macro eb 3
    and byte [f_], ~(1 << %2)
    lea f_, [f_ + q * %1 + %3]
    cmp f_, fc
    jae next_
%endmacro

%macro eb_4 2
    and byte [f_], ~(1 << %1)
    lea rax, [q + q * 2 + %2]
    add f_, rax
    cmp f_, fc
    jae next_
%endmacro

%macro eb0 2
    eb_4 %1, %2
%endmacro

%macro eb1 2
    eb 2, %1, %2
%endmacro

%macro eb2 2
    eb 1, %1, %2
%endmacro

%macro eb3 2
    eb 2, %1, %2
%endmacro

%macro eb4 2
    eb 1, %1, %2
%endmacro

%macro eb5 2
    eb 2, %1, %2
%endmacro

%macro eb6 2
    eb_4 %1, %2
%endmacro

%macro eb7 2
    eb 1, %1, %2
%endmacro

extern L1C
extern BC
extern PADD
extern WIX
    align 64
L:
    dq _1, 0, 0, _7, 0, _11, _13, 0, _17, _19, 0, _23, 0, 0, _29, 0
    dq _1_0, _1_1, _1_2, _1_3, _1_4, _1_5, _1_6, _1_7
    dq _7_0, _7_1, _7_2, _7_3, _7_4, _7_5, _7_6, _7_7
    dq _11_0, _11_1, _11_2, _11_3, _11_4, _11_5, _11_6, _11_7
    dq _13_0, _13_1, _13_2, _13_3, _13_4, _13_5, _13_6, _13_7
    dq _17_0, _17_1, _17_2, _17_3, _17_4, _17_5, _17_6, _17_7
    dq _19_0, _19_1, _19_2, _19_3, _19_4, _19_5, _19_6, _19_7
    dq _23_0, _23_1, _23_2, _23_3, _23_4, _23_5, _23_6, _23_7
    dq _29_0, _29_1, _29_2, _29_3, _29_4, _29_5, _29_6, _29_7
    align 16
global sieve_93_
sieve_93_:
    push rbx
    push rbp
    push r12
    push r13
    push r14
    push r15
    movq xmm0, rsp
    mov r8, rdx
    mov c_d, [rel L1C]
    mov eax, [rel BC]
    cmp nsp, -1
    cmove c_d, eax
    mov p_d, [rel pp]
    mov psq, p
    imul psq, p
    mov d, psq
    sub d, st
L0:
    imul rax, c, 30
    cmp d, rax
    jge end
    mov f_, f
    mov md30_d, MD30
    cmp psq, st
    ja L00
    mov rax, st
    xor rdx, rdx
    imul rbx, p, 30
    div rbx
    imul rax, 30
    mov rbx, rax
    mov eax, edx
    shr rdx, 32
    div p_d
    movzx eax, byte [rax + PADD]
    add rax, rbx
    mov rbx, rax
    imul rax, p
    sub rax, st
    imul rax, md30
    shr rax, 36
    cmp eax, c_d
    jae next
    add f_, rax
    mov rax, MD30Q
    mul rbx
    shr rdx, 4
    imul rdx, -30
    add rdx, rbx
    shr edx, 1
    movzx w_d, byte [rdx + WIX]
    mov eax, p_d
    imul rax, md30
    shr rax, 36
    imul edx, eax, -30
    add edx, p_d
    shr edx, 1
L1:
    shl eax, 1
    mov q, rax
    add c, f
    jmp [rdx * 8 + L]
    align 16
_1:
    jmp [w * 8 + L + 16 * 8]
    align 16
_1_0:
    eb8 1, 0, 1, 2, 3, 4, 5, 6, 7, 0, 0, 0, 0, 0, 0, 0
_1_0_:
    eb0 0, 0
_1_1:
    eb1 1, 0
_1_2:
    eb2 2, 0
_1_3:
    eb3 3, 0
_1_4:
    eb4 4, 0
_1_5:
    eb5 5, 0
_1_6:
    eb6 6, 0
_1_7:
    eb7 7, 1
    jmp _1_0
    align 16
_7:
    jmp [w * 8 + L + 24 * 8]
    align 16
_7_0:
    eb8 7, 1, 5, 4, 0, 7, 3, 2, 6, 1, 2, 1, 3, 4, 4, 3
_7_0_:
    eb0 1, 1
_7_1:
    eb1 5, 1
_7_2:
    eb2 4, 1
_7_3:
    eb3 0, 0
_7_4:
    eb4 7, 1
_7_5:
    eb5 3, 1
_7_6:
    eb6 2, 1
_7_7:
    eb7 6, 1
    jmp _7_0
    align 16
_11:
    jmp [w * 8 + L + 32 * 8]
    align 16
_11_0:
    eb8 11, 2, 4, 0, 6, 1, 7, 3, 5, 2, 4, 0, 6, 6, 6, 6
_11_0_:
    eb0 2, 2
_11_1:
    eb1 4, 2
_11_2:
    eb2 0, 0
_11_3:
    eb3 6, 2
_11_4:
    eb4 1, 0
_11_5:
    eb5 7, 2
_11_6:
    eb6 3, 2
_11_7:
    eb7 5, 1
    jmp _11_0
    align 16
_13:
    jmp [w * 8 + L + 40 * 8]
    align 16
_13_0:
    eb8 13, 3, 0, 6, 5, 2, 1, 7, 4, 3, 4, -1, 7, 8, 6, 7
_13_0_:
    eb0 3, 3
_13_1:
    eb1 0, 1
_13_2:
    eb2 6, 1
_13_3:
    eb3 5, 2
_13_4:
    eb4 2, 1
_13_5:
    eb5 1, 1
_13_6:
    eb6 7, 3
_13_7:
    eb7 4, 1
    jmp _13_0
    align 16
_17:
    jmp [w * 8 + L + 48 * 8]
    align 16
_17_0:
    eb8 17, 4, 7, 1, 2, 5, 6, 0, 3, 3, 6, 1, 9, 10, 10, 9
_17_0_:
    eb0 4, 3
_17_1:
    eb1 7, 3
_17_2:
    eb2 1, 1
_17_3:
    eb3 2, 2
_17_4:
    eb4 5, 1
_17_5:
    eb5 6, 3
_17_6:
    eb6 0, 3
_17_7:
    eb7 3, 1
    jmp _17_0
    align 16
_19:
    jmp [w * 8 + L + 56 * 8]
    align 16
_19_0:
    eb8 19, 5, 3, 7, 1, 6, 0, 4, 2, 4, 6, 0, 10, 12, 10, 10
_19_0_:
    eb0 5, 4
_19_1:
    eb1 3, 2
_19_2:
    eb2 7, 2
_19_3:
    eb3 1, 2
_19_4:
    eb4 6, 2
_19_5:
    eb5 0, 2
_19_6:
    eb6 4, 4
_19_7:
    eb7 2, 1
    jmp _19_0
    align 16
_23:
    jmp [w * 8 + L + 64 * 8]
    align 16
_23_0:
    eb8 23, 6, 2, 3, 7, 0 ,4, 5, 1, 5, 8, -1, 13, 14, 12, 13
_23_0_:
    eb0 6, 5
_23_1:
    eb1 2, 3
_23_2:
    eb2 3, 1
_23_3:
    eb3 7, 4
_23_4:
    eb4 0, 1
_23_5:
    eb5 4, 3
_23_6:
    eb6 5, 5
_23_7:
    eb7 1, 1
    jmp _23_0
    align 16
_29:
    jmp [w * 8 + L + 72 * 8]
    align 16
_29_0:
    eb8 29, 7, 6, 5, 4, 3, 2, 1, 0, 6, 10, 0, 16, 18, 16, 16
_29_0_:
    eb0 7, 6
_29_1:
    eb1 6, 4
_29_2:
    eb2 5, 2
_29_3:
    eb3 4, 4
_29_4:
    eb4 3, 2
_29_5:
    eb5 2, 4
_29_6:
    eb6 1, 6
_29_7:
    eb7 0, 1
    jmp _29_0
    align 16
next_:
    sub c, f
next:
    dec nsp
    jz end
    add pp, 4
    mov p_d, [rel pp]
    mov psq, p
    imul psq, p
    mov d, psq
    sub d, st
    jmp L0
    align 16
L00:
    mov eax, d_d
    imul rax, md30
    shr rax, 36
    add f_, rax
    mov eax, p_d
    imul rax, md30
    shr rax, 36
    imul edx, eax, -30
    add edx, p_d
    shr edx, 1
    movzx w_d, byte [rdx + WIX]
    jmp L1
    align 16
end:
    movq rsp, xmm0
    pop r15
    pop r14
    pop r13
    pop r12
    pop rbp
    pop rbx
    ret

```

#### build.sh

```
#!/bin/sh -x

SRC="main.c sieve_7_13.o sieve_17_89.o sieve_93_.o lut.o -lm"
C="gcc"
O="-O3 -march=native"
$C $O -c sieve_7_13.c
$C $O -c sieve_17_89.c
nasm -felf64 sieve_93_.s
nasm -felf64 lut.s
$C $O -or $SRC
rm *.o

```

# Answer
> 5 votes
# Jyxal 0.4.1, 46 MiB on my computer, official score 120 MiB

```
{500(&›¥æß¥)W⁋₴

```

Read the README to see how to run this

For reference, the example program outputted 21.8 MiB on my computer.

I had a blast micro-optimizing the compiler. The old Jyxal answer was disqualified because it considered multiples of 5 prime. The new version of Jyxal is almost completely rewritten in Koltin (barring the math library) and contains a new post-compilation optimizer (powered by Proguard™). This allows Jyxal to move to Java 11. It also optimizes for loops. The needless push-pops are optimized away and the JVM operand stack is used whenever possible.

```
{500(&›¥æß¥)W⁋₴ # Takes no input
{               # Infinite loop
 500(      )    # Repeat 500 times
     &›         # Increment the register
       ¥æ       # And check it for primality
         ß      # If it is prime...
          ¥     # Push the number
            W   # Wrap the stack in a list
             ⁋  # Join by newlines
              ₴ # And then print the result
                # Implicitly loops back

```

The primality test is nothing as elaborate as Vyxal's. For numbers that are smaller than 9,223,372,036,854,775,807, the BigComplex object is converted into a long, and then the last bit is tested. If it is 0, that means the number is even and that the number is not prime. Then using an optimization I found on SO, I use a brute-force division algorithm that skips multiples of 2 and 3, lessening the number of divisors I need to check.

Compiled with

```
java -jar Jyxal.v.0.4.1.jar code.txt t

```

The `t` flag disables vectorisation of monads, which removes the need for `MethodHandles` and allows the monad to be inlined.

If you are interested, here is the bytecode decompiled into Java:

```
public final class Main {
    private static Object register;

    static {
        register = BigComplex.ZERO;
    }

    public static void main(String[] var0) {
        ProgramStack stack = new ProgramStack(var0);

        while(true) {
            for(int var1 = 500; var1 != 0; --var1) {
                if (RuntimeHelpers.truthValue(RuntimeMethods.isPrime(register = RuntimeMethods.increment(register)))) {
                    stack.push(register);
                }
            }

            System.out.print(RuntimeMethods.joinByNewlines(JyxalList.create(stack)));
        }
    }
}

```

# Answer
> 4 votes
# C (gcc -O3)

```
#include <stdio.h>
#include <string.h>
#define MAX_SQRT 100000000ULL
unsigned long composites[MAX_SQRT >> 7UL] = { 1 };
unsigned long primes[10000000] = { 2 };
int main(int argc, char **argv) {
  unsigned long *last = primes;
  printf("2\n");
  for (unsigned long i = 3; i < MAX_SQRT; i += 2) {
    if (composites[i >> 7UL] & 1UL << (i >> 1UL)) continue;
    printf("%lu\n", i);
    *++last = i;
    for (unsigned long j = i * i >> 1UL; j < MAX_SQRT >> 1UL; j += i) composites[j >> 6UL] |= 1UL << j;
  }
  for (unsigned long long i = MAX_SQRT + 1; i < MAX_SQRT * MAX_SQRT; i += MAX_SQRT) {
    memset(composites, 0, sizeof(composites));
    for (unsigned long *j = primes; ++j <= last; ) {
      unsigned long k = (unsigned long)(*j - 1 - ((*j - 1 + i) % (*j * 2) >> 1UL));
      while (k < MAX_SQRT >> 1UL) {
        composites[k >> 6UL] |= 1UL << k;
        k += *j;
      }
    }
    for (unsigned long j = 0; j < MAX_SQRT >> 1UL; j++) if (!(composites[j >> 6UL] & 1UL << j)) printf("%llu\n", i + j * 2);
  }
}

```

Outputs 6.2GB in 1 minute on my fast PC, for a speed of 105 MB/s. Note that I timed using `(timeout 1m ./a.out) | pv > /dev/null`, which avoids timing out `pv` itself.

# Answer
> 3 votes
## C++

```
#include <stdio.h>
#include <array>

// ~~ Algorithm Description ~~
// Since sqrt(max) = 100000000 = M, we should precompute primes until M,
// because all factors of N are always smaller or equal to sqrt(N).
// There are 5761455 primes smaller than M.

// After these maneuvers, assuming that `ull' is 8 bytes large, the binary
// will grow by approximately 46 megabytes.

// Notice that this solution largely makes use of the C++ compile-time features
// and the fact that the program's compile-time isn't timed nor the binary size
// isn't measured.

// BUILDING:
// g++ -O3 -std=c++20 pgen.cpp -o pgen -fconstexpr-ops-limit=1000000000000 -fconstexpr-loop-limit=1000000000

typedef unsigned long long ull;

template <std::size_t N>
constexpr std::array<ull, N> get_ptab() {
    std::array<ull, N> ptab;
    ull gen = 3;
    ptab[0] = 2; ptab[1] = 3; ptab[2] = 5;
    for(std::size_t i = 7; gen < N; i += 2) {
        bool ok = true;
        if(i % 3 == 0 || i % 5 == 0)
            continue;
        for(std::size_t j = 2; j * j <= i; j++) {
            if(i % j == 0) {
                ok = false;
                break;
            }
        }
        if(ok)
            ptab[gen++] = i;
    }
    return ptab;
}

constexpr std::array<ull, 5761455> ptab = get_ptab<5761455>();

int main(void) {
    // Step 1: print all the primes that we've hardcoded already.
    for(std::size_t i = 0; i < ptab.size(); i++)
        printf("%llu\n", ptab[i]);
    // Step 2: starting with ptab.back(), go up until max, checking if
    // N is divisible by any of the primes we've hardcoded.
    // If it is, skip it. If it isn't, print it.
    for(std::size_t i = ptab.back(); i < 10000000000000000; i+=2) {
        bool ok = true;
        for(std::size_t j = 0; j < ptab.size() && i <= ptab[j]; j++) {
            if(i % ptab[j] == 0) {
                ok = false;
                break;
            }
        }
        if(ok)
            printf("%llu\n", i);
    }
    return 0;
}

```

The performance is yet unknown since the code still compiles on my machine. If you manage to compile, run and time it, let me know how quickly it performs.

# Answer
> 2 votes
# PARI/GP, 929MiB on my computer

```
forprime(p=2, 10^16, print(p))

```

The package name for PARI/GP is `pari-gp` on Ubuntu, Debian, Arch Linux and some other distros.

Runs as `gp -qf ./file_name.gp`.

---

# PARI/GP \+ gp2c, 3.76GiB on my computer

gp2c compiles PARI/GP functions to C codes, where the generated `.so` file can be called in another PARI/GP script.

So there are two files:

`a.gp`:

```
a() = forprime(p=2, 10^16, print(p))

```

`b.gp`:

```
install("a","v","a","./a.gp.so");
a()

```

### How to run

The package name for gp2c is `pari-gp2c` on Ubuntu and Debian, `gp2c` on Arch Linux (AUR).

First compile `a.gp` with gp2c:

```
gp2c a.gp > a.gp.c

```

The command to compile the generated C code is in the first comment of the generated C code. It should look like:

```
cc -c -o a.gp.o -g -O3 -Wall -fomit-frame-pointer -fno-strict-aliasing -fPIC -I"/usr/include/x86_64-linux-gnu" a.gp.c && cc -o a.gp.so -shared -g -O3 -Wall -fomit-frame-pointer -fno-strict-aliasing -fPIC -Wl,-shared -Wl,-z,relro a.gp.o -lc -lm -L/usr/lib/x86_64-linux-gnu -lpari

```

After that you can run `b.gp` and measure the throughput:

```
(timeout 1m gp -qf ./b.gp) | pv > /dev/null

```

---

# C + PARI/GP's C library, 4.81GiB on my computer

Modified from the C code generated by gp2c.

```
#include <pari/pari.h>

int main()
{
    pari_init(8000000, 500000);

    forprime_t iter;
    u_forprime_init(&iter, 2, 10000000000000000);
    long p;
    while (p = u_forprime_next(&iter))
        printf("%ld\n", p);
}

```

If you are using Ubuntu or Debian, you need to install the package `libpari-dev`. For Arch Linux, `pari-gp` is enough.

Compiles with `gcc -O3 -lpari`.

---
Tags: number-theory, primes, fastest-code, optimization
---


title: Recreate Minecraft's lighting

text:
# Question
Title: Recreate Minecraft's lighting
Minecraft has a fairly unique lighting system. Each block's light value is either one less than the brightest one surrounding it, or it is a light source itself. Your task is to write a method that takes in a 2D array of light source values, and then returns a 2D array with spread out lighting, where 0 is the minimum value.

**Examples**

```
Input1 = [
         [0, 0, 4, 0],
         [0, 0, 0, 0],
         [0, 2, 0, 0],
         [0, 0, 0, 0]
        ]

Output1 = [
         [2, 3, 4, 3],
         [1, 2, 3, 2],
         [1, 2, 2, 1],
         [0, 1, 1, 0]
        ]

Input2 = [
         [2, 0, 0, 3],
         [0, 0, 0, 0],
         [0, 0, 0, 0],
         [0, 0, 0, 0]
        ]

Output2 = [
         [2, 1, 2, 3],
         [1, 0, 1, 2],
         [0, 0, 0, 1],
         [0, 0, 0, 0]
        ]

```

**Notes**

You can assume:

1. Input will not be empty
2. The y axis will be the same length
3. All numbers will be integers; no nulls, doubles, or floats
4. All numbers will be between 0 and 15 (inclusive).

Rules:

1. Return a 2D array following the above mechanics
2. No value can be less than 0
3. If there are two highest neighbors, just subtract one from them
4. Light sources do not change, unless a surrounding block is brighter than it.
5. No standard loopholes
6. This is code golf, so shortest code wins!

# Answer
> 6 votes
# BQN, 21 bytesSBCS

```
(⊢⌈¯1+«⌈»⌈«˘⌈»˘)⍟(≠⥊)

```

Run online!

`«⌈»⌈«˘⌈»˘` computes the element-wise maximum of:

* `«` Push in 0's from the bottom
* `»` Push in 0's from the top
* `«˘` Push in 0's from right
* `»˘` Push in 0's from the left

Then substract 1 from this / add ¯1 (`¯1+`) and take the maximum with the input matrix ().

`≠⥊` gives the number of element in the flattened matrix and `(...)⍟` iterates the function on the left that many times.

# Answer
> 6 votes
# R \>=4.1, ~~377~~ ~~215~~ ~~182~~ 150 bytes

```
f=\(m,w=T,n=1:ncol(m),z=Reduce(pmax,Map(\(j){o=outer(m[p][j]-abs(n-i[j,1]),abs(n-i[j,2]),`-`);o*(o>0)},1:nrow(i<-which(p<-m>1,a=T)))))`if`(w,f(z,F),z)

```

I sure learned a lot.

Thanks to June Choe for the `outer()` tip which enabled a significant optimisation, and then some cleanup.

Also thanks to @pajonk for some additional savings, use of `Map`, and for introducing me to 'attempt this online'

# Answer
> 5 votes
# JavaScript (ES6),  ~~99 94~~  93 bytes

Modifies the input matrix in-place.

```
m=>{for(d=64;d--;m.map((r,y)=>r.map((v,x)=>r[x]=(q=~-(m[y+D%2]||0)[x+~-D%2])>v?q:v)))D=d%4-1}

```

Try it online!

### Commented

```
m => {                   // m[] = input matrix
  for(                   // repeat 64 times,
    d = 64;              // using d as a counter:
    d--;                 //
    m.map((r, y) =>      //   for each row r[] at position y in m[]:
      r.map((v, x) =>    //     for each value v at position x in r[]:
        r[x] = (         //       update r[x]:
          q =            //         q is the value of the neighbor cell
          ~-(            //         located at m[y + dy][x + dx],
            m[y + D % 2] //         using D as the current direction
            || 0         //         (-1 = North, 0 = West, 1 = South,
          )[x + ~-D % 2] //         2 = East), minus 1
        ) > v ? q        //         keep the maximum of q and the
              : v        //         current value v
      )                  //     end of inner map()
    )                    //   end of outer map()
  ) D = d % 4 - 1        //   set D to (d mod 4) - 1
}                        // implicit end of for()

```

# Answer
> 5 votes
# MATL, 24 bytes

```
Xz,G@+&fh]&1ZP-TYaX>GZye

```

Try it online! Or verify all test cases.

### Explanation

```
Xz       % Implicit input. Get nonzeros as a column vector (*)
,        % Do twice
  G      %   Push input
  @      %   Push iteration index: 0 or 1
  +      %   Add, element-wise
  &f     %   Two-output find: gives row and column indices of nonzeros
  h      %   Concatenate horizontally. Gives a 2-row matrix where each
         %   row contains the coordinates of nonzeros (first iteration)
         %   or of all entries (second iteration)
]        % End
&1ZP     % Cityblock distance between rows
-        % Subtract from (*), element-wise with broadcast
TYa      % Extend with two rows of zeros. This serves two purposes:
         % making sure that the maximum of each row is at least 0; and
         % making sure that each column has more than 1 entry, so that
         % the following function (maximum) operates along the first
         % dimension (compute maximum of each column)
X>       % Maximum along the first (non-singleton) dimension (**)
GZy      % Push input. Size
e        % Reshape (**) with the specified size. Implicit display

```

# Answer
> 5 votes
# C(gcc) 230 227 220 172 171 128 97 bytes

smaller thanks to @Muskovets an @engineergaming, and now @ceilingcat

```
i,j;f(n,x,y)int*n;{for(i=x*y;i--;)for(j=x*y;j--;n[j]=fmax(n[j],n[i]-abs(i%x-j%x)-abs(i/x-j/x)));}

```

Try it Online!

# Answer
> 4 votes
# JavaScript (Node.js), ~~100~~ ~~98~~ 94 bytes

```
A=Math.abs
f=(a,i,j)=>a.map((r,y)=>r.map((c,x)=>1/i?t=t>(u=c-A(i-y)-A(j-x))?t:u:f(t=a,y,x)|t))

```

Try it online!

-4 byte from ophact

# Answer
> 4 votes
# Python 3 with numpy, 93 bytes

```
f=lambda a,n=0:f(rot90(fmax(a,r_[a[1:],a[-1:]]-1)),n+1)if n<len(a)*4else a
from numpy import*

```

Try it online!

Each iteration spreads light upwards, then rotates the array by 90 degrees.

# Answer
> 3 votes
# , 28 27 bytes

```
(>./@,((,-)=1 2)|.!.0<:)^:_

```

Try it online!

Consider input:

```
0 0 4 0
0 0 0 0
0 2 0 0
0 0 0 0

```
* `(,-)=1 2)` 4 directions of movement:

```
 1  0
 0  1
_1  0
 0 _1

```
* `|.!.0<:` Rotate the input minus 1 in those directions:

```
_1 _1 _1 _1
_1  1 _1 _1
_1 _1 _1 _1
 0  0  0  0

_1  3 _1  0
_1 _1 _1  0
 1 _1 _1  0
_1 _1 _1  0

 0  0  0  0
_1 _1  3 _1
_1 _1 _1 _1
_1  1 _1 _1

 0 _1 _1  3
 0 _1 _1 _1
 0 _1  1 _1
 0 _1 _1 _1

```
* `>./@,` Prepend input and max reduce the 5 "planes":

```
0 3 4 3
0 1 3 0
1 2 1 0
0 1 0 0

```
* `(...)^:_` Repeat that process until a fixed point:

```
2 3 4 3
1 2 3 2
1 2 2 1
0 1 1 0

```

# Answer
> 3 votes
# Python 3, ~~207~~ 205 bytes

Once I first saw this challenge posted, I started having some ideas for python solutions bouncing around in my head. This solution turned out to be way longer than I would have hoped, but I did find away to do this without `numpy`, which the other python solution uses:

```
f=lambda x:[[eval(f"max(max({i*'x[i-1][j],'}{j*'x[i][j-1],'}{~i%len(x)*'x[i+1][j],'}{~j%len(x)*'x[i][j+1],'})-1,x[i][j])")for j in range(len(x))]for i in range(len(x))]
g=lambda x:x if f(x)==x else g(f(x))

```

Try it online!

I wanted to be able to fit this into one lambda, but I simply couldn't seem to get the conditional to work, so `g(x)` is the function that is actually called to get the result. The main bulk of the code is in the giant `eval()` statement, which basically calculates the highest adjacent block, subtracts 1 from that, and takes the the max of that and the blocks current value. The rest of the code just iterates that over each block, and then recursively does that until all light levels have been calculated.

# Answer
> 2 votes
# Haskell, 107 bytes

```
r x=[0..length x-1]
f a=let(w,h)=(r$head a,r a)in[[maximum[a!!y!!x-abs(x-j)-abs(y-i)|x<-w,y<-h]|j<-w]|i<-h]
```

Attempt This Online!

# Answer
> 2 votes
# Charcoal, 22 bytes

```
ＩＥθＥι⌈Ｅθ⌈Ｅν⁻π⁺↔⁻ξκ↔⁻ρμ

```

Try it online! Link is to verbose version of code. Explanation: Same algorithm as @alephalpha's PARI/GP answer.

```
 ＥθＥι                   Map over input array
      Ｅθ Ｅν             Map over input array
            π           Innermost value
           ⁻            Subtract
              ↔⁻ξκ      Absolute row difference
             ⁺          Plus
                  ↔⁻ρμ  Absolute column difference
     ⌈  ⌈               Take the maximum
Ｉ                       Cast to string
                        Implicitly print

```

Note that Charcoal's default I/O format is rather ugly so I've also written a 26-byte prettier version which unfortunately only works up to 9:

```
ＷＳ⊞υιＥυ⭆ι⌈Ｅυ⌈Ｅν⁻π⁺↔⁻ξκ↔⁻ρμ

```

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

# Answer
> 1 votes
# PARI/GP, 73 bytes

```
m->matrix(#m~,#m,i,j,vecmax(matrix(#m~,#m,k,l,m[k,l]-abs(k-i)-abs(l-j))))
```

Attempt This Online!

\\$output\[i,j\]=\underset{k,l}\max(input\[k,l\]-|k-i|-|l-j|)\\$

# Answer
> 1 votes
# 05AB1E, ~~22~~ 21 bytes

```
Δ<U4FøíXøíDUćaª‚øεø€à

```

Port of *@Jonah*'s J answer, so make sure to upvote him as well!

Try it online or verify all test cases.

**Explanation:**

```
Δ           # Loop until the result no longer changes:
 <          #  Decrease each value in the matrix by 1
            #  (which will be the implicit input-matrix in the first iteration)
  U         #  Pop and store it in variable `X`
 4F         #  Loop 4 times:
   øí       #   Rotate the matrix once clockwise:
   ø        #    Zip/transpose; swapping rows/columns
    í       #    Reverse each inner row
            #   (which will be the implicit input-matrix in the first iteration)
   X        #   Push matrix `X`
    øí      #   Rotate it once clockwise as well
      DU    #   Store a copy as new value for `X`
        ć   #   Extract head; pop remainder-matrix and first row separated
         a  #   Convert all values in this row to 0 (with an is_letter check)
          ª #   Append this list of 0s as trailing row
   ‚øεø€à   #   Reduce the two matrices by maximum:
   ‚        #    Pair the two matrices together
    ø       #    Zip/transpose; creating pair of rows
     εø     #    Zip/transpose each inner pair of rows to pair of cell-values
       €à   #    Leave the maximum of each inner-most pair of cell-values
            # (after which the resulting matrix is output implicitly)

```

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