title: Happy new year string builder

text:
# Question
Title: Happy new year string builder
This question is inspired by this awesome answer.

The challenge is to write a program or function which takes in a positive integer, and outputs "Happy new year to you" or a slight variation thereof, such that the character codes of that string add up to the inputted number. The space counts towards the sum of character codes too.

The case does not matter at all; you may output `HappY New yEAR` or something so long as it satisfies the specifications below.

The specifications are as follows:

The outputted string must contain `happy new year`. As stated above, the case does not matter.

The `happy new year` component of the string may optionally be preceded by `have a` , again in any case. However, there must be a space before `happy` if the string starts with `have a` .

The `happy new year` string may optionally be followed by  `to you`, again in any case. The space before `to` is mandatory.

Note that `Have a happy new year to you`, while not grammatically correct, is an acceptable output for the purposes of this challenge.

Finally, at the very end of the string, any number of exclamation marks can be outputted.

In summary, the outputted string must satisfy the following regular expression:

```
/^(have a )?happy new year( to you)?!*$/i

```

You may assume while writing your program or function that you will only be given numbers for which it is possible to construct a "happy new year" string.

I won't allow outputting in array or list format because it defeats the purpose of the challenge.

If there are multiple solutions, feel free to output any one of them, any subset of them, or all of them.

As this challenge is , the shortest code, measured in bytes, wins.

## Test cases

```
2014
-> Happy new year to you!

1995
-> HAPPY NEW YEAR TO You!!!!!!!!!!!!!!

989
-> HAPPY NEW YEAR

1795
-> Have a HAPPY new year!

2997
-> Have a HAppY new year to YOU!!!!!!!!!!!!!!!!!!!

```

# Answer
# JavaScript (Node.js),  ~~159~~  148 bytes

This code builds the string without resorting to brute force.

```
y=>Buffer((s="happy new year",r=n=y%33)>17&n<20?(n-=7,r-=5,"have a "+s):n<18?s+" to you":(n-=20,s)).map(c=>c-32*(c>32&&n-->0))+'!'.repeat(y/33+r-61)

```

Try it online!

### How?

Let \\$y\\$ be the input year.

Because we can add \\$k\times33,k\ge0\\$ to the result by adding as many trailing exclamation marks as we want, we need to focus on \\$n=y\bmod33\\$.

The method that is used here can be split into the 4 following cases:

* If \\$n\le17\\$:
    + We use the base string `"happy new year to you"` and put \\$n\\$ characters in upper case, for a base score of \\$2013-32n\\$.
    + We add \\$\lfloor y/33\rfloor+n-61\\$ exclamation marks.
    + The final score is: $$2013-32n+33\times(\lfloor y/33\rfloor+n-61)\\\=33\times\lfloor y/33\rfloor+n=33\times\lfloor y/33\rfloor+(y \bmod 33)=y$$
* If \\$n=18\\$:
    + We use the base string `"HAVE A HAPPY New year"`, for a base score of \\$1602\\$.
    + We add \\$\lfloor y/33\rfloor-48\\$ exclamation marks.
    + The final score is: $$1602+33\times(\lfloor y/33\rfloor-48)\\\=33\times\lfloor y/33\rfloor+18=33\times\lfloor y/33\rfloor+(y \bmod 33)=y$$
* If \\$n=19\\$:
    + We use the base string `"HAVE A HAPPY NEw year"`, for a base score of \\$1570\\$.
    + We add \\$\lfloor y/33\rfloor-47\\$ exclamation marks.
    + The final score is: $$1570+33\times(\lfloor y/33\rfloor-47)\\\=33\times\lfloor y/33\rfloor+19=33\times\lfloor y/33\rfloor+(y \bmod 33)=y$$
* If \\$n\ge20\\$, we use the base string `"happy new year"` and put \\$n-20\\$ characters in upper case, for a base score of \\$2013-32n\\$.
    + We add \\$\lfloor y/33\rfloor+n-61\\$ exclamation marks.
    + The computation of the final score is similar to the 1st case.

Obviously, it's not possible to add a negative number of exclamation marks, which is why only some years before 1981 have a happy new year string (as pointed out by @AnttiP).
> 11 votes

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

```
f=(n,s='',...a)=>n|!/^(have a )?happy new year( to you)?!*$/i.test(s)?f(...a,...[...f+f].map(_=>(a=!a)?s+Buffer([i++]):n-i,i=2)):s

```

Try it online!

Run out of memory on any computer as it use \>128^14 args, but theoretically it works
> 6 votes

# Answer
# Excel, 219 bytes

```
=LET(r,MOD(A1,33),m,(r<20)+(r<18)+1,s,REPT("HAVE A ",m=2)&"HAPPY NEW YEAR"&REPT(" TO YOU",m=3),a,INDEX({989;1410;1469},m),b,MOD(a-r,33),d,b+SUM((b>{5,8,12,14})*1),LOWER(LEFT(s,d))&MID(s,d+1,26)&REPT("!",(A1-a-b*32)/33))

```

Inspired by @Arnauld 's answer. One of the ingenious things about his solution is that the numbers of cases that start with "HAVE A" is so small, that a different test to account for the spaces is not needed.

Link to Spreadsheet

`=LET(r,MOD(A1,33),` Set r = \\$n \mod 33\\$.

`m,(r<20)+(r<18)+1,` Set mode. Mode 1 \\$\> 19\\$; Mode 2 \\$\[18, 19\]\\$; mode 3 \\$\< 18\\$.

`s,REPT("HAVE A ",m=2)&"HAPPY NEW YEAR"&REPT(" TO YOU",m=3),` if mode 2, prepend "HAVE A "; if mode 3, append " TO YOU".

`a,INDEX({989;1410;1469},m),` Sum of character values for base string

`b,MOD(a-r,33),` distance of base string from \\$n \mod 33\\$

`d,b+SUM((b>{5,8,12,14})*1),` portion of base string to be converted to lower case. The numbers in the brackets account for the spaces.

`LOWER(LEFT(s,d))&MID(s,d+1,26)&REPT("!",(A1-a-b*32)/33))` return the string with the appropriate number of characters converted to lower case plus the number of "!" to reach the target number.
> 5 votes

# Answer
# Charcoal, 83 bytes

```
ＮθＦ²Ｆ²«≔⁺⁺×ιHAVE A ”＆±″/⍘=↧5"ＳA”×κ TO YOUκＦ⊕Ｌκ⊞υ⭆κ⎇‹νλμ↧μ»Ｗ⬤υ⁻θΣＥκ℅μ≔⁺υ!υ⊟Φυ⁼θΣＥι℅λ

```

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

```
Ｎθ

```

Input the desired year.

```
Ｆ²Ｆ²«

```

Loop over the possibilities of prefixes and suffixes.

```
≔⁺⁺×ιHAVE A ”＆±″/⍘=↧5"ＳA”×κ TO YOUκ

```

Take the compressed string `HAPPY NEW YEAR` and optionally prefix or suffix it as appropriate.

```
Ｆ⊕Ｌκ⊞υ⭆κ⎇‹νλμ↧μ

```

Generate more than enough permutations of the case of the characters in the strings. (In particular, unnecessary extra copies are created for each space in the string, because it's golfer not to filter them out.)

```
»Ｗ⬤υ⁻θΣＥκ℅μ

```

While none of the strings has the desired character sum...

```
≔⁺υ!υ

```

... append an `!` to each string.

```
⊟Φυ⁼θΣＥι℅λ

```

Output one of the strings with the desired character sum.

74 bytes for a version that's too slow for TIO:

```
ＮθＦθＦ²Ｆ²«≔⁺⁺×κHAVE A ”＆±″/⍘=↧5"ＳA”×λ TO YOUλＦ⊕Ｌλ⊞υ⁺⭆λ⎇‹ξμν↧ν×ι!»⊟Φυ⁼θΣＥι℅λ

```

Try it online! with the second `θ` changed to `χ` so it does at least work for some years.
> 3 votes

# Answer
# Jelly, 52 bytes

```
“ṭ½IṾFhĿ_)Wẓȷ⁻⁸ẉ»ḲŒP“7dx‘ịK€ŒuƤŻoƊ€Ẏ;þḶ”!xⱮƊẎOS⁼ɗƇ⁸Ḣ

```

A monadic Link accepting a positive integer that yields a list of characters (or 0). Or a full program that prints a valid result (or 0).

Don't Try it online! (it won't finish)

Rather, see this slightly altered **test-suite** which considers fewer possible strings (by using \\$\frac{1}{33}\\$ as many optional trailing `!`s).

### How?

```
“...»ḲŒP“7dx‘ịK€ŒuƤŻoƊ€Ẏ;þḶ”!xⱮƊẎOS⁼ɗƇ⁸Ḣ - Link: integer, N
“...»                                    - "have a happy new year to you"
     Ḳ                                   - split at spaces
      ŒP                                 - powerset
        “7dx‘                            - [55,100,120]
             ị                           - index into -> [["happy", "new", "year"], ["have", "a", "happy", "new", "year"], {"happy", "new", "year", "to", "you"]]
              K€                         - join each with spaces -> ["happy new year", "have a happy new year", "happy new year to you"]
                     Ɗ€                  - last three links as a monad for each:
                ŒuƤ                      -   upper-case prefixes
                   Ż                     -   prefix with a zero
                    o                    -   logical OR (the full lower-case)
                       Ẏ                 - tighten
                               Ɗ         - last three links as a monad - f(N):
                          Ḷ              -   [0..N-1]
                           ”!            -   '!'
                             xⱮ          -   map with times -> ["", "!", "!!", ..., '!'*(N-1)]
                        ;þ               - table with concatenate
                                Ẏ        - tighten
                                      ⁸  - use N as the right argument of...
                                     Ƈ   - filter keep those for which:
                                    ɗ    -   last three links as a dyad - f(possibles, N):
                                 O       -     ordinals
                                  S      -     sum
                                   ⁼     -     equals N?
                                       Ḣ - head -> valid result or 0 if none exists

```
> 2 votes

# Answer
# Ruby, 128 bytes

```
->y{n=y%33
s="HAVE A HAPPY NEW YEAR TO YOU"[n/2==9?0:7,w=21-n/20*7]
w.times{|i|(n=y-s.sum)%33>0&&s[i]=s[i].downcase}
s+?!*n/=33}

```

Try it online!

Similar to Arnauld's answer. Some notes on how it works:

* `"HAPPY NEW YEAR".sum % 33` is 32. Converting a letter to lowercase adds 32, reducing the remainder by 1 for each letter down to a minimum of 20 when all 12 letters are in lowercase.
* `"HAVE A HAPPY NEW YEAR".sum % 33` is 24. We convert 5 or 6 letters to lowercase to cover years of remainder 19 and 18.
* `"HAPPY NEW YEAR TO YOU".sum % 33` is 17. We convert 0 to 17 letters to lowercase to cover years of remainder 17 down to 0.

It's a fairly simple approach, avoiding the sophisticated formulas in Arnauld's answer (although it wouldn't work without them being true).

* Select the appropriate substring from `HAVE A HAPPY NEW YEAR TO YOU` as above
* Convert characters from uppercase to lowercase until `(y-s.sum)%33` is zero
* Append `(y-s.sum)/33` exclamation marks

`n` is used in two different ways. First it represents `y%33`. Later it represents `y-s.sum`. The reason for the re-use of `n` is that the second assignment occurs inside a loop and if a new variable were used (implicitly declared) inside the loop, it would not be recognised outside the loop, causing an error.
> 1 votes

# Answer
# Python3, 211 bytes:

```
lambda y:next(f(y,'',s:='happy new year to you'),0)or next(f(y,'','have a '+s))
def f(y,s,j):
 if(v:=sum(map(ord,s)))==y:yield s
 if v<y:
  for i in{(k:=['!',j][j!=''])[0],k[0].upper()}:yield from f(y,s+i,k[1:])

```

Try it online!
> 1 votes

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


title: Mandoline quine

text:
# Question
Title: Mandoline quine
Write a quine... from which every other character can be removed it still be a valid quine. You can specify whether to start removing characters at the first or second character.

Scoring criteria (add bonuses/penatly percentages together for total percentage):

* Answers must be at least 4 characters long
* Program must contain at least one alphabetical character in its source, so for example, `12345!@#$%^&*()` is disqualified
* +750% if the language used is not Turing-complete (I'm looking at you, HTML!)
* -15% if the solution does not read its source from anywhere in any form
* -20% if you can also keep only every 5th character and still form a quine

The score is measured by the number of characters in the first program.

Example (not real programs):

If `123456789abcdef` and `13579bdf` are both quines, the score is 15. Additionally, if `159d` is also a quine, then the final score is 12.

This is code-golf, so lowest score wins.

# Answer
> 26 votes
## PHP, 4 chars − 15% − 20% = ~~2.72~~ 2.6 points

```
ABCD

```

Yes, PHP is a Turing-complete language. Nobody said I have to *use* any of its actual programming features. ;-)

<sub>**Edit:** Changed the score based on the clarification that bonuses are additive, not multiplicative.</sub>

# Answer
> 14 votes
# Python - 95

Great challenge. I thought this was pretty clever, and actually a legit solution!

```
00;"#";print(open(__file__).read())
0#;XpXrXiXnXtX(XoXpXeXnX(X_X_XfXiXlXeX_X_X)X.XrXeXaXdX(X)X)

```

# Answer
> 14 votes
## TI BASIC 4 - 35% = 2.6

*I might understand them wrong, but I think I am also eligible for the -15% and the -20% bonusses, meaning I have the lowest possible score.*

I can write the program:

```
123i

```

which will output `123i` where i is of course the imaginary unit. When you remove the 1st and the 3rd character all that remains is `2i` which outputs `2i`

# Answer
> 11 votes
## Golfscript, 5 points

```
{hai}

```

is a function that, when executed, will run the (non-existing) function `hai`. It's not executed, however, but rather printed when the program ends - including the outer brackets. Removing each other character yields:

```
{a}

```

Lame, I know :-)

# Answer
> 9 votes
## HQ9+ - 4 * 7.5 * 0.8 = 24 points

```
Q+++

```

Still a quine with every second character:

```
Q+

```

...and every fifth:

```
Q

```

Sorry, I couldn't resist. :)

# Answer
> 7 votes
# HTML/Markdown, 4\*7.5 = 30

```
HHHH

```

I admit this is lame, but it doesn't really go against any rule in the question. Except that HTML/Markdown may not be considered a real programming language.

# Answer
> 5 votes
# !/bin/sh

I liked qwr's solution so much, I shamelessly made a port for POSIX shell. Please don't save it into a filename containing spaces.

```
: '#';cat $0

#c a t   $ 0

```

Start removing at character number 1, and count newlines as characters. The second quine is of course:

```
 #;a 0
cat $0

```

*Please upvote qwr's answer instead of this one!*

# Answer
> 3 votes
# Bash, 23

Newline is a character!

Some messy comment work, so that when every other character starting from the first is removed, the comment becomes code and the code becomes a comment:

```
#cRaRtR R$R0R R#
cat $0

```

After every other character (*including the new line*) is removed:

```
cat $0 #ct$

```

# Answer
> 3 votes
# Vyxal, 8 bytes -15% = 6.8

```
` I,` I,

```

Try it Online!

## Every other char

```
`I`I

```

Try it Online!

## Explanation :

```
` I,`    # push ` I,`
      I  # quote and prepend
       , # print

`I`  # push `I`
   I # quote and prepend
     # implicit output

```

# Answer
> 2 votes
## Brainf\**k, 37 - 15% = 31.45

Abusing the Portable Brainfuck Interpreter

```
+A[B-C<D+E]F-GÿH<I<J<K<L<M<N<O[P.Q>R]

```

Start removing from the second character.

# Answer
> 2 votes
# Python 3, ~~145~~ 94 bytes -15% : Score = 79.9

```
s ="'psr=i%nrt;(p'rsi n=t%(rs;%e%xse)c;(xsc[s11:::2  2']; p)r'i%nst)(#s#%#s#)";exec(s[1:: 2] )

```

Try it online!

## every other char:

```
s='s=%r;print(s%%s);xcs1:2 ';print(s%s);xcs1:2

```

Try it online!

## How it works :

The ugly string is the blending of :

* `print('s =%r;exec(s[1::2 ] )'%s)####` for the normal quine
* `'s=%r;print(s%%s);xcs1:2 ';print(s%s)` for the every-other-char quine

`xcs1:2`  is an annotation and doesn't throw any error as the part after the semicolumn can compile. Otherwise it would throw a `SyntaxError` and the program wouldn't run at all.

# Python 3, with reading code source: ~~70~~ 62 bytes

```
s ="p-r-i-n-t-(-*-o-p-e-n-(-_-_-f-i-l-e-_-_-)-)";exec(s[::2] )

```

Try it online!

## every other char:

```
s=print(*open(__file__));xcs:2

```

Try it online!

# Answer
> 0 votes
# HQ9+T, - 4 * 0.8 = 3.2 points

```
qqqq

```

It's a valid quine (ish) and a quine every second and fifth char. I couldn't resist . . . .

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


title: Lean golf: Pascal vs. Fibonacci

text:
# Question
Title: Lean golf: Pascal vs. Fibonacci
The Pascal's triangle and the Fibonacci sequence have an interesting connection:

*Source: Math is Fun - Pascal's triangle*

Your job is to prove this property in Lean theorem prover (Lean 3 + mathlib). Shortest code in bytes wins.

```
import data.nat.choose.basic
import data.nat.fib
import data.list.defs
import data.list.nat_antidiagonal

theorem X (n : ℕ) :
  ((list.nat.antidiagonal n).map (function.uncurry nat.choose)).sum
  = n.succ.fib :=
sorry -- replace this with actual proof

```

Since the statement itself depends on the current version of mathlib, it is encouraged to use Lean web editor (as opposed to TIO) to demonstrate that your answer is correct.

Some primer on the built-ins used:

* `nat` or  is the set/type of natural numbers including zero.
* `list.nat.antidiagonal n` creates a list of all pairs that sum to `n`, namely `[(0,n), (1,n-1), ..., (n,0)]`.
* `nat.choose n k` or `n.choose k` is equal to \\$\_nC\_k\\$.
* `nat.fib n` or `n.fib` is the Fibonacci sequence defined with the initial terms of \\$f\_0 = 0, f\_1 = 1\\$.

In mathematics notation, the equation to prove is

$$ \forall n \in \mathbb{N},\\; \sum^{n}\_{i=0}{\_iC\_{n-i}} = f\_{n+1} $$

## Rules

* Your code should provide a named theorem or lemma `X` having the exact type as shown above. Any kind of sidestepping is not allowed.
* The score of your submission is the length of your entire source code in bytes (including the four imports given and any extra imports you need).

# Answer
# Lean, 299 bytes

```
import data.list data.nat.fib
open nat
def s(n k):=((list.nat.antidiagonal n).map$λa:_×_,choose(a.1+k)a.2).sum
def X:∀n,s n 0=fib(n+1)|0:=rfl|1:=rfl|(n+2):=by{let:∀k,s(n+2)k=choose k(n+2)+s n k+s(n+1)k,induction
n;intro;simp[s,(∘),<-add_one,add_assoc,*]at*;ring,rw[one_add,choose],ring,safe}

```

Try it on Lean Web Editor
> 10 votes

# Answer
# Lean, ~~247~~ 243 bytes

```
import data.nat.fib data.list
open nat list.nat
def X:∀n,((antidiagonal n).map$function.uncurry
choose).sum=fib(n+1)|0:=rfl|1:=rfl|(n+2):=by
rw[fib_add_two,antidiagonal_succ_succ'];simpa[<-X,antidiagonal_succ',<-add_assoc,<-list.sum_map_add]

```

Try it on Lean Web Editor *(Note 2/15/2022: this will work within 24 hours)*

Perhaps it's cheating, since I contributed very relevant lemmas about antidiagonals to mathlib that were just merged this morning, but I added them for other reasons, I promise! The Lean Web Editor is updated daily, so it should eventually work.
> 6 votes

---
Tags: code-golf, math, combinatorics, fibonacci, lean
---


title: Spinning Word Search

text:
# Question
Title: Spinning Word Search
## Introduction:

Pete likes doing word search puzzles. Despite that, he has trouble searching for words vertically, (anti-)diagonally, or reversed. Because of that, he'll always search for the words left-to-right, and rotates the entire puzzle in increments of 45 degrees clockwise.
In addition to that, he'll also always search for the words in (alphabetical) order.

## Challenge:

Given a word search grid and a list of (alphabetically ordered) words, output how many rotations are necessary to find all the words.

### 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.

**For example:**

```
Grid:
 ABCD
 EFGH
 IJKL
 MNOP

Words:
 AFK
 BCD
 FC
 PONM

```

Here, the first string `AFK` can be found diagonally from the topleft-to-bottomright; the second word `BCD` horizontally from the left-to-right; etc.:

```
AFK    BCD    FC     PONM

aBCD   Abcd   ABcD   ABCD
EfGH   EFGH   EfGH   EFGH
IJkL   IJKL   IJKL   IJKL
MNOP   MNOP   MNOP   mnop

```

## Challenge example:

If we take the same example grid and list of words above, we find `AFK` after 7 clockwise rotations of 45 degrees; `BCD` after 1 more rotation; `FC` after 1 more rotation; and `PONM` after 3 more rotations. So the result for the example grid and four words will be `12` (7+1+1+3).

Here a visual representation of these steps:

```
            A                    M                    P                    D
           E B                  N I                  L O                  C H
ABCD      I F C      MIEA      O J E      PONM      H K N      DHLP      B G L
EFGH  →  M J G D  →  NJFB  →  P K F A  →  LKJI  →  D G J M  →  CGKO  →  A F K P  ⮌
IJKL      N K H      OKGC      L G B      HGFE      C F I      BFJN      E J O
MNOP       O L       PLHD       H C       DCBA       B E       AEIM       I N
            P                    D                    A                    M

      1           2        3           4        5           6        7  A F K
 BCD                                                                             8
      9     F C
                  10       11          12 PONM

```

## Challenge rules:

* Input can be in any reasonable format. The input-grid could be a character-matrix; list/stream of lines; taken from STDIN; etc. The same applies to the list of words.
* The inputs are guaranteed to only contain regular letters (in the same casing, unless you prefer otherwise).
* You're allowed to take the inputs in uppercase; lowercase; mixed case; or even as 0- or 1-based alphabet indices as integers if you'd want.
* You can assume the input-words will always be in alphabetical order.
* You can assume the words will always be present in the grid, and will only occur once.
* All words are guaranteed to have at least two letters (because single-letter words could be found in multiple directions, adding annoying edge cases).
* You can assume neither the grid nor list of words will be empty.
* No need to deal with the remaining letters or partial overlapping of word. Just look for the words one at a time and output the amount of 45 degree clockwise rotations that are necessary.
* The grid will not necessarily be a square, but it's guaranteed to be a rectangle.

## 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:

```
Inputs:
ABCD
EFGH
IJKL
MNOP

AFK
BCD
FC
PONM

Output: 12

```

```
Inputs:
ABC

AB
ABC
BC

Output: 0

```

```
Inputs:
AB

BA

Output: 4

```

```
Inputs:
WVERTICALL
ROOAFFLSAB
ACRILIATOA
NDODKONWDC
DRKESOODDK
OEEPZEGLIW
MSIIHOAERA
ALRKRRIRER
KODIDEDRCD
HELWSLEUTH

BACKWARD
DIAGONAL
FIND
HORIZONTAL
RANDOM
SEEK
SLEUTH
VERTICAL
WIKIPEDIA
WORDSEARCH

Output: 39

```

# Answer
# Jelly,  ~~26 22~~  21 bytes

-1 thanks to ovs! (Use the outer-product quick, `þ` rather thank `€Ɱ`.)

```
ŒdU$ŒḌƭƬw€þ§T€F’ŻI%8S

```

A dyadic Link accepting the Wordsearch on the left and the sorted word-list on the right that yields an integer.

**Try it online!**

### How?

This would need tweaking to handle multiple instances of a word in the Wordsearch (would need to account for multiple results in the result of `T€`) but luckily, we don't need to handle that.

```
ŒdU$ŒḌƭƬw€þ§T€F’ŻI%8S - Link: Wordsearch grid, G; word-list W
       Ƭ              - collect input (initially G) while distinct applying:
      ƭ               -   alternating calls to:
   $                  -   ...1: last two links as a monad:
Œd                    -           anti-diagonals
  U                   -           reverse each
    ŒḌ                -   ...2: reconstruct from forward-diagonals
          þ           - table - i.e. [[f(o,w) for o in orientations] for w in W]:
        w€            -   first index of w in each row of o
           §          - sums (sum each of the orientation results)
            T€        - truthy (1-indexed) indices of each
              F       - flatten
               ’      - decrement
                Ż     - prepend a zero
                 I    - forward differences
                  %8  - modulo eight
                    S - sum

```
> 3 votes

# Answer
# JavaScript (ES6), 149 bytes

Expects `(m)(a)`, where `m` is a matrix of characters and `a` is a list of lists of characters.

```
m=>a=>a.map(w=>t+=m.some((r,y)=>r.some((_,x)=>j=~[..."21036785"].findIndex(d=>w.every((c,i)=>(m[y+~-(d/3)*i]||0)[x+d%3*i-i]==c))))*n-(n=j)&7,t=n=0)|t

```

Try it online!

### How?

For each word \\$w\\$, we look for a starting position \\$(x,y)\\$ and a direction \\$d\\$ from the string `"21036785"` for which the word is matched along the following vector:

$$(dx,\\:dy)=((d\bmod3)-1,\\:\lfloor d/3\rfloor-1)$$

Hence the following directions for each \\$d\\$:

$$\begin{matrix}0&1&2\\3&&5\\6&7&8\end{matrix}$$

We define \\$j\\$ as the ones' complement of the index of \\$d\\$ in the string, which gives:

$$\begin{matrix}-3&-2&-1\\\-4&&-8\\\-5&-6&-7\end{matrix}$$

(NB: We use the ones' complement so that the inner `some()` is not triggered when `findIndex()` returns \\$-1\\$.)

Given the previous orientation \\$n\\$ (starting with \\$n=0\\$), the number of 45° clockwise turns that are needed to reach the new orientation is:

$$(n-j)\operatorname{AND}7$$

We add the result of the above expression to the accumulator \\$t\\$ and update \\$n\\$ to \\$j\\$.
> 5 votes

# Answer
# Python 3, ~~265~~ 260 bytes

-5 thanks to KevinCruijssen

## Golfed code

```
def f(G,W):
 r=0;f=range;g=len
 for w in W:
  while any(w in l for l in G)<1:r+=1;m=g(G[0]);H,G=G[:],["".join(G[j][i-j]for j in f(max(i-m+1,0),min(i+1,g(G))))[::-1]for i in f(g(G)+m-1)]if r%2 else["".join(H[~j][i]for j in f(g(H)))for i in f(g(H[0]))]
 return r

```

Try it online!

## Formatted and commented code

```
def find_rotations(grid, words):
    rotations = 0
    for word in words:
        while not any(word in line for line in grid):
            rotations += 1
            if rotations % 2 == 1:  # If rotations is odd, rotate rectangular grid by 45deg
                old_grid = grid[:]  # Keep a copy of the old grid
                new_grid = []                                  #
                for i in range(len(grid) + len(grid[0]) - 1):  #
                    new_line = ""                              #
                    for j in range(                            #
                        max(i - len(grid[0]) + 1, 0),          # Equivalent to first list comprehension
                        min(i + 1, len(grid))                  # Rotates rectangular grid by 45deg
                        ):                                     #
                        new_line += grid[j][i-j]               #
                    new_grid.append(new_line[::-1])            #
                grid = new_grid[:]                             #
            else:                   # If rotations is even, rotate copy of old rectangular grid by 90deg
                                    # (Much easier than rotating diamond-shaped grid by 45deg)
                new_grid = []                                  #
                for i in range(len(old_grid[0])):              #
                    new_line = ""                              # Equivalent to second list comprehension
                    for j in range(len(old_grid)):             # Rotates rectangular grid by 90deg
                        new_line += old_grid[~j][i]            # (Rotates old_grid because that is the last rectangluar grid)
                    new_grid.append(new_line)                  #
                grid = new_grid[:]                             #
    return rotations

```
> 3 votes

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

```
f=lambda n,k,N=0,E=enumerate:k and f(n,k[(A:=any(any(all(-1<(Y:=r+(R:=[0,*[-K]*3,0,K,K,K])[N%8])<len(n)>-1<(Z:=c+R[N%8-2])<len(_)!=C==n[Y][Z]for K,C in E(k[0]))for c,H in E(_))for r,_ in E(n))):],N+1-A)or N

```

Try it online!

Recursive solution.

## Explanation

Initialize `N`, the number of rotations. Set it to 0.

At each iteration, we attempt to identify the first word in `k`, the list of words to find, by going through every cell in the grid and pointing in the direction that `N` corresponds to. For instance, if `N` is 0, meaning the grid is not rotated at all, we go 0 rows down and 1 column to the right, `len(k[0])` times at each cell.

If such a word is identified, then we delete the first element and recall `f` with `n`, the now smaller `k`, and the same `N`. `N` does not change, because there might still be words in the same orientation.

If no such word is identified, then no deletion is done and instead we recall `f` with `n`, the same `k`, and an incremented `N`.

Eventually, `k` will be empty, and in such a case, we return `N`.
> 1 votes

# Answer
# Python 3, 406 bytes

```
R=range
L=len
e=lambda b:'\n'.join(map(''.join,b))
r=lambda b,x,y:[b[x][y]]+(r(b,x-1,y+1)if x and y<L(b[0])-1 else[])
def s(b,c=1):
 t=[[i[::-1]for i in zip(*b)],[[i]for i in b[0]]][L(b)==1]
 yield[r(b,i,0)for i in R(L(b))]+[r(b,L(b)-1,i)for i in R(1,L(b[0]))]if c%2 else t
 yield from s([t,b][c%2],c+1)
o=lambda b,w:w!=[]and w[0]in b and 1+o(b,w[1:])
g=lambda b,w,u:1+g(next(u),w[o(e(b),w):],u)if w else-1

```

Try it online!
> 1 votes

# Answer
# Charcoal, 59 bytes

```
ＷＳ⊞υι≔⟦⟧ηＷＳ⊞ηιυＦ⁸ＦＬυＦＬθ«ＪλκＵＭη⎇⁼μ⪫ＫＤＬμ✳ιωιμ»⎚ＩΣＥη﹪⁻ι∧κ§η⊖κ⁸

```

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

```
ＷＳ⊞υι

```

Read in the grid.

```
≔⟦⟧ηＷＳ⊞ηι

```

Read in the words.

```
υ

```

Output the grid.

```
Ｆ⁸

```

Loop over each direction.

```
ＦＬυＦＬθ«Ｊλκ

```

Loop over each cell.

```
ＵＭη

```

Looping over each word...

```
⎇⁼μ⪫ＫＤＬμ✳ιωιμ

```

... if it matches the word in the current direction starting from the current cell, replace it with the current direction.

```
»⎚ＩΣＥη﹪⁻ι∧κ§η⊖κ⁸

```

Pairwise subtract the directions, reduce them all modulo `8`, and output the sum.
> 1 votes

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

```
f=lambda G,L,*H:L>[]and 1-(d:=L[0]in" ".join(map("".join,G)))+f(d*G or[*zip(*((x:=H)or[(x:=x+s)+g+s*len(G)for g in G])[::-1])],L[d:],*[G*(H==()),H][d])
s=" ",

```

Try it online!

Takes a sequence of tuples of characters for the grid and a sequence of strings for the search list.

Test harness nicked from @ophact.

### How?

More or less does actually rotate the grid and then searches in normal row major order.

90° rotations are implemented as up down flip followed by transpose (aka `zip`).

If we first shear by prepending a linearly (w.r.t. line number) increasing amount of white space and then do the same 90° rotation we get essentially the same lines as we would have doing a 45° rotation.

The main "loop" is recursion. `G` is the current grid `L` the leftover word list and `H` alternates between being empty and a backup of `G` because every 90° rotation must be based not on the current `G` but its predecessor.
> 1 votes

# Answer
# JavaScript, 144 bytes

```
f=(a,b,d=0,[w,...r]=b)=>w?a.some((r,y)=>r.some((c,x)=>w.every((p,i)=>p==a[d%4?d<4?y-i:y+i:y]?.[x+i-'00122210'[d]*i])))?f(a,r,d):f(a,b,-~d%8)+1:0

```

Try it online!

TIO is 147 bytes as `?.` syntax is not available on it.

Input grid as 2d character array. Input words as an array of array of characters. Output a number. `f(grid: string[][], words: string[][]) -> number`
> 1 votes

---
Tags: code-golf, string, grid, word-search
---


title: Simulating Bombs

text:
# Question
Title: Simulating Bombs
More advanced version of this

The aim of this puzzle is to simulate the impact of the shock wave of bombs on a square grid. The grid initially contains cells labelled `0` along with several bombs of type `A`, `H`, or `B`. Display the greatest intensity of shockwaves felt at each cell after the bombs explode.

The three bombs have different explosion patterns. Consider the following generic configuration, where the `X` will be replaced by the different types of bombs. Note that for each bomb, the bomb's location is not replaced by a number.

```
000000000
000000000
000000000
000000000
0000X0000
000000000
000000000
000000000
000000000

```

For the `A`-bomb:

```
000000000
011111110
012222210
012333210
0123A3210
012333210
012222210
011111110
000000000

```

For the `H`-bomb:

```
000000000
055555550
055555550
055555550
0555H5550
055555550
055555550
055555550
000000000

```

For the `B`-bomb:

```
000000000
000010000
000020000
000030000
0123B3210
000030000
000020000
000010000
000000000

```

Unlike the other bombs, the `B`-bomb will not explode unless it is within the shockwave of another exploding bomb

## Input & Output

* You are given an integer `n`, representing the grid size of `n*n`
* You are then given the grid of `n*n`
* You may take in the input as a list of `n` lines
* Output the shock waves of all bombs
* You may output as a matrix/list/array

## Test cases

```
1
H
->
H

15
000000000000000
A00A0000000000A
000000000000000
000000000000000
000000000000000
000000000000000
000000000000000
000000000000000
0000000A0000000
000000000000000
000000000000000
000000000000000
000000000000000
000000000000000
A000000000000AA
->
333332100001233
A33A3210000123A
333332100001233
222222100001222
111111100001111
000011111110000
000012222210000
000012333210000
0000123A3210000
000012333210000
000012222210000
111111111111111
222100000012222
332100000012333
A321000000123AA

18
000000000000000000
0AAAA00000000AAAA0
000000000000000000
000000000000000000
000000000000000000
000000000000000000
AA0000000000000000
000000000000000000
000000000000000000
000000000000000000
00000000000000A000
000000000000000000
000000000000000000
00000A000000000000
000000000000000000
000000000000000000
00000000000000000A
A00A000A0000A00000
->
333333210012333333
3AAAA32100123AAAA3
333333210012333333
222222210012222222
222211110011111111
333210000000000000
AA3210000000000000
333210000001111111
222210000001222221
111110000001233321
00111111100123A321
001222221001233321
001233321001222221
00123A321001111111
111233321111111222
222222222222222233
33333233322333223A
A33A323A3223A32233

18
H00000000000000000
000000000000000H00
000000000000000000
00000000H000000000
000000000000000000
000000000000000000
000000000000000000
000000HH0000000000
000000000000000000
000000000000000000
000000000000000H00
000000000000000000
000000000000000000
000000000000000000
HHH00000000H000000
000000000000000000
000000000000000000
000000000000000000
->
H55505555555555555
555505555555555H55
555505555555555555
55550555H555555555
000555555555555555
000555555555000000
000555555555000000
000555HH5550555555
000555555550555555
000555555550555555
000555555550555H55
555555005555555555
555555005555555555
555555005555555555
HHH55500555H555000
555555005555555000
555555005555555000
555555005555555000

22
000000000000000000000A
00000B0000000000000000
0000000000000000000000
0B0000000000000000000B
000000000000000000B000
0000000000000000000000
000000000000000000000B
0000000000000000000000
000000B00000000A000000
000000000000000000000B
0000000000000000000000
000000B000000000000000
000000000000000000000B
0000000000000000000000
000000000H000000000000
000000000000000000000B
0000000000000000000000
A000000000000000000000
A00000000000B000000000
A000000000000000000000
HHHH00000000000000A00H
00000000A0000000000000
->
000000000000000000123A
00000B0000000000001233
0000000000000000001223
0B0000000000000000123B
000000000000000000B003
0000001000001111111003
000000200000122222123B
0000003000001233321003
000123B32100123A321003
000000300000123332123B
0000003000001222221003
000123B555555111111003
000000555555500000123B
0000005555555000000003
111100555H555000000003
222100555555500000123B
3321005555555000000003
A555555555555001115555
A55555511111B001225555
A555555222210001235555
HHHH55533321000123A55H
55555553A3210001235555

10
0000000000
0A00000000
0000000000
000B00B000
0000000000
000B00B00B
0000000000
0B00B00000
0000000000
0000000000
->
3332101000
3A32102000
3333103001
223B33B322
1113103003
123B33B33B
0003003003
0B02B02002
0001001001
0000000000

```

## Others

¤ The place may already have felt the effect of other bombs before the grid bombs exploded. In this case the number of the cell will be different from `0` as soon as the grid is given

¤ There are only three types of bomb: `A`, `B`, `H`

¤ There may be no explosion

¤ For overlapping of bomb explosions, please note that the highest intensity will outshine the lower intensity shock waves. E.g. a shockwave of `3` emitted by the `A`-bomb, will be replaced by a `5` if there is a `H`-bomb nearby

¤ For the order of checking the bombs, you can do a left to right, top to bottom checking system for easy checking (the 4th rule ensures overlapping will not cause any problems)

## Scoring

This is code-golf, you know the rules ;)

## Credits

Credits to this puzzle

# Answer
> 2 votes
# Charcoal, 118 bytes

```
ＷＳ«ＦAHＦ⌕Ａικ⊞υ⟦ⅉλκ⟧⟦ι⟧»Ｆυ«≔§ι⁰ζ≔§ι¹ε≔§ι²δＦ⁷Ｆ⁷¿¬∧∧⁻κ³⁻λ³⁼Bδ«Ｊ⁺ε⁻λ³⁺ζ⁻κ³¿⁼BＫＫＦ¬№υ⟦ⅉⅈB⟧⊞υ⟦ⅉⅈB⟧¿⁼ＫＫＩΣＫＫ⎇⁼Hδ5⌈⟦ＫＫＩ⁻⁴⌈↔⁻⟦κλ⟧³

```

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

```
ＷＳ«

```

Loop over the rows of the grid.

```
ＦAHＦ⌕Ａικ⊞υ⟦ⅉλκ⟧

```

Collect the positions of the `A`s and `H`s.

```
⟦ι⟧

```

Print the row to the canvas on its own line.

```
»Ｆυ«

```

Loop over the positions of the letters.

```
≔§ι⁰ζ≔§ι¹ε≔§ι²δ

```

Extract the current position and letter.

```
Ｆ⁷Ｆ⁷

```

Process a square of size `7` centred on the current position.

```
¿¬∧∧⁻κ³⁻λ³⁼Bδ«

```

Skip this cell if the current letter is `B` and the cell isn't orthogonal to the current position.

```
Ｊ⁺ε⁻λ³⁺ζ⁻κ³

```

Jump to the cell.

```
¿⁼BＫＫＦ¬№υ⟦ⅉⅈB⟧⊞υ⟦ⅉⅈB⟧

```

If this cell is a `B` that hasn't been seen before then add it to the list of letter positions.

```
¿⁼ＫＫＩΣＫＫ⎇⁼Hδ5⌈⟦ＫＫＩ⁻⁴⌈↔⁻⟦κλ⟧³

```

If this cell is a digit then calculate the shock wave and update the cell if it is greater than its current value.

# Answer
> 4 votes
# Java 10, ~~312~~ ~~310~~ ~~308~~ 307 bytes

```
n->m->{for(int i=n*n,b;i-->0;)if((b=m[i/n][i%n])>57)e(m,i/n,i%n,b);}int e(char[][]m,int x,int y,int b){for(int j=-4,k,u,r,X,Y;++j<4;m[x][y]*=b/~-b)for(k=-4;++k<4;)try{u=m[X=x-j][Y=y-k];r=b>67?53:52-Math.max(j<0?-j:j,k<0?-k:k);m[X][Y]+=b==j*k|b%7==2?u>r?u==66?e(m,X,Y,0):0:r-u:0;}finally{continue;}return 0;}

```

-2 bytes thanks to *@Neil*.
-1 byte thanks to *@ceilingcat*.

Input as a matrix of characters, and it modifies it directly. Also takes the dimension `n` as additional input, since it's shorter.

Try it online.

**Explanation:**

```
n->m->{                  // Method with integer & character-matrix parameters
  for(int i=n*n,b;i-->0;)//  Loop `i` over all cells in the range (n²,0]:
    if((b=m[i/n][i%n])   //   Save the current cell's value in `b`
       >57)              //   If `b` is a bomb:
      e(m,i/n,i%n,b);}   //    Explode it with the method below

// Separated recursive method to explode a bomb
// Takes the matrix, current x,y, and `b` as parameters (and always returns 0)
int e(char[][]m,int x,int y,int b){
  for(int j=-4,k,u,r,X,Y;++j<4;
                         //  Loop `j` in the range (-4,4):
  m[x][y]*=b/~-b)        //    If the current cell is an exploding B-bomb:
                         //     Remove the B-bomb so we know it's exploded
                         //    Else:
                         //     Keep the cell's value unchanged
    for(k=-4;++k<4;)     //   Inner loop `k` in the range (-4,4) as well:
      try{u=m[X=x-j]     //    Set `X` to x-j
             [Y=y-k]     //    Set `Y` to y-k
                    ;    //    Set `u` to the value at cell X,Y
      r=b>67?            //    If we're exploding an H-bomb:
         53              //     Set `r` to 53 (unicode value for 5)
        :                //    Else:
         52-             //     Set `r` to 52, subtracted by:
            Math.max(    //      The max of:
              j<0?-j:j,  //       The absolute value of `j`
              k<0?-k:k); //       and the absolute value of `k`
      m[X][Y]+=          //    Change the value at cell X,Y to:
         b==j*k          //     If we're exploding a B-bomb
                         //     and either `j` or `k` is 0
                         //     (which means X,Y shares a row/column with x,y)
        |                //     OR
         b%7==2?         //     We're exploding an A- or H-bomb:
          u>r?           //      If the current value `u` is larger than `r`:
            u==66?       //       If `u` is a B-bomb that has yet to explode:
             e(m,X,Y,0)  //        Do a recursive call with `b`=0 to explode it
            :0           //        And keep the current cell's value unchanged
          :              //      Else (`u` is smaller than `r`):
           r-u           //       Change the current cell's value to `r`
        :                //     Else (it's an already exploded B-bomb or digit):
         0;              //      Keep the current cell's value unchanged
      }finally{continue;}//    Catch and ignore ArrayIndexOutOfBoundsExceptions
                         //    (which is shorter than manual in-bounds checks)
  return 0;}             //  Always return 0

```

# Answer
> 3 votes
# JavaScript (ES7), 180 bytes

Modifies the input matrix.

```
f=(m,X,Y,t)=>m.map((r,y)=>r.map((c,x)=>t?(d=4-((h=(x-X)**2)>(v=(y-Y)**2)?h:v)**.5)>0?(n=t==b?h*v?0:d:t<b?d:5)?r[c==b&&f(m,x,y,c,r[x]=f),x]=c<n?n:c:0:0:1/c||c==b||f(m,x,y,c)),b='B')

```

Try it online!

# Answer
> 1 votes
# Python3, 747 bytes:

```
from math import*
R=range
L=len
p={'A':(k:=[3,2,1],1),'H':([5]*3,1),'B':(k,0)}
g=lambda x,i:[j[i] for j in x]
m=lambda x,y,X,Y:max(map(abs,[X-x,Y-y]))
def u(b,x,y,l,r,o,Q,i=0,H=0):
 if i and(j:=b[x][y])not in p and int(j)<l[(P:=m(*o[0],x,y)-1)]:b[x][y]=l[P]
 if i and j=='B' and m(*o[0],x,y)-1 < 3:Q.append((x,y))
 for q,w in[(0,1),(1,0),(0,-1),(-1,0)]:
  if(X:=x+q)>=0 and(Y:=y+w)>=0 and (X,Y)not in o and(r or 1 in[L(set(g(O:=o+[(X,Y)],0))),L(set(g(O,1)))]):
   try:
    if(K:=dist(o[0],(X,Y)))>=H:u(b,X,Y,l,r,o+[(X,Y)],Q,1,K)
   except:1
def f(b):
 Q,S=[],[]
 for x in R(L(b)):
  for y in R(L(b[0])):
   if(E:=b[x][y])in['A','H']:u(b,x,y,*p[E],[(x,y)],Q)
 while Q:
  S+=Q;q=[]
  for i in Q:u(b,*i,*p['B'],[i],q)
  Q=[j for j in q if j not in S]

```

Try it online!

# Answer
> -1 votes
# Python 3.8, 457 bytes

```
import itertools as t
g={}
b={}
R=range(int(input()))
for i in R:
 for j,v in enumerate(input()):
  g[i,j]=v
  if v in"AH":b[i,j]=v
def d(i,j,v):
 g[i,j]=v.lower()
 for x,y in t.product(range(-3,4),repeat=2):
  if x==y==0 or v=="B"and x*y!=0:continue
  if(o:=(i+x,j+y))in g:
   if"B"==g[o]:d(*o,"B")
   if g[o].isdigit():g[o]=max("5"if v=="H"else str(4-max(abs(x),abs(y))),g[o])
for i,j in b:d(i,j,b[i,j])
for i in R:print("".join(g[i,j].upper()for j in R))

```

Try it online!

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


title: Print a NxN integer involute

text:
# Question
Title: Print a NxN integer involute
Given an integer \\$N\\$, you must print a \\$N\times N\\$ integer involute with the numbers increasing in a clockwise rotation. You can start with either 0 or 1 at the top left, increasing as you move towards the centre.

## Examples

```
Input => 1
Output =>
0

Input => 2
Output =>
0 1
3 2

Input => 5
Output =>
 0  1  2  3 4
15 16 17 18 5
14 23 24 19 6
13 22 21 20 7
12 11 10  9 8

Input => 10
Output =>
 0  1  2  3  4  5  6  7  8  9
35 36 37 38 39 40 41 42 43 10
34 63 64 65 66 67 68 69 44 11
33 62 83 84 85 86 87 70 45 12
32 61 82 95 96 97 88 71 46 13
31 60 81 94 99 98 89 72 47 14
30 59 80 93 92 91 90 73 48 15
29 58 79 78 77 76 75 74 49 16
28 57 56 55 54 53 52 51 50 17
27 26 25 24 23 22 21 20 19 18

```

You may output a 2 dimensional array, or a grid of numbers.

Challenge inspired by Article by Eugene McDonnell

This is so the goal is to minimize your source code with answers being scored in bytes.

# Answer
> 15 votes
# Jelly, 13 bytes

```
⁸JW;ṚZ+LƲƲ2¡¡

```

Try it online!

A nilad function or full program that takes a number from stdin and returns the 1-based involute of size n × n.

### How it works

```
⁸JW;ṚZ+LƲƲ2¡¡
⁸                Empty list ([])
          2¡¡    Take n from stdin and repeat 2n times starting from the above:
                   Given previous matrix m,
    ṚZ+LƲ          Rotate m and add the number of rows of m
 JW;     Ʋ         Prepend a row of 1..(number of rows of m)

```

The involute can be constructed iteratively as follows:

```
Start with m = [] (think of it as 0-row, 0-col matrix)
Repeat 2n times:
    If m has r rows, add r to every cell of m
    Rotate m 90deg clockwise
    Attach 0..r-1 (or 1..r) as a new row at the top of m

```

After every step, the matrix `m` is always an involute for some rectangular size (square at even steps). For example, using 1-based indexing, doing a single step on

```
1 2 3
8 9 4
7 6 5

```

gives

```
 1  2  3
10 11  4
 9 12  5
 8  7  6

```

and then

```
 1  2  3  4
12 13 14  5
11 16 15  6
10  9  8  7

```

# Answer
> 11 votes
# MATL, ~~12~~ 11 bytes

```
UG1YL-GoQ&P

```

Try it online!

MATL (like MATLAB) has a `spiral` matrix which spirals clockwise from the center, so this performs the necessary flips and subtracts the matrix from `N^2`.

~~Probably Luis Mendo knows how to golf this...~~ Thanks to Luis Mendo for −1 byte.

```
	% Implicit input N
U	% Square
G1YL	% Push the N×N spiral matrix (S)
	% clockwise from the center, starting at 1
-	% N^2 - S, element-wise
GoQ	% Push mod(N,2)+1
&P	% Flip along that dimension:
	% for odd N, flips the rows; for even N, flips the columns
	% Implicit output

```

# Answer
> 8 votes
# APL (Dyalog Unicode), ~~18~~ ~~17~~ 16 bytes

```
(⍉⍳⍨,⊖+≢)⍣2⍣⎕⊤⍨⍬

```

Try it online!

Full program. TIO uses  instead of  for easier test case demonstration. For the core algorithm, refer to my Jelly answer.

The only additional trick here is the `⊤⍨⍬`, which is one of the shortest expressions that give a 0-by-0 matrix (`0 0⍴0`). This one in particular is handy because it doesn't mess up by stranding with the input value.

-1 byte using `⍳∘≢ → ⍳⍨`; the rows are guaranteed to be distinct, so finding indices of items in itself gives the vector of indices for the leading axis.

Also -1 byte by moving  to the end of the train to save a . Add first row to a transposed matrix == Add first column and then transpose it.

# Answer
> 7 votes
# Python, 73 bytes (@ovs)

```
f=lambda n,m=0,p=-1:n*[n]and((*range(m,n),),*zip(*f(2*n-m+p,n,~p)[::-1]))
```

Attempt This Online!

#### Old Python, 74 bytes (@DialFrost)

```
f=lambda n,m=0,p=-1:n and((*range(m,n),),*zip(*f(2*n-m+p,n,~p)[::-1]))or()
```

Attempt This Online!

#### Old Python, 76 bytes

```
f=lambda n,m=0,p=-1:n>m and((*range(m,n),),*zip(*f(2*n-m+p,n,~p)[::-1]))or()
```

-15 by reversing order of recursion.

Attempt This Online!

#### Old Python, 91 bytes

```
lambda n:g((n*n-1,))
g=lambda*s:(l:=s[0][0])and g((*range(l-len(s),l),),*zip(*s[::-1]))or s
```

Attempt This Online!

Builds the spiral from inside to out by recursively rotating 90° and adding a row on the top.

# Answer
> 6 votes
# BQN, 29 bytesSBCS

```
{⍉⌽∘⍉∘∾´≍¨⌽(/«⥊2↕↕+1)⊔⌽↕⋆2}

```

Run online!

A port of Bubbler's Jelly answer comes in at 20 bytes:

```
{(⊒˜∾⍉∘⌽+≠)⍟2⍟↕0‿0}

```

Run online!

# Answer
> 5 votes
# Charcoal, ~~48~~ ~~41~~ 40 bytes

```
Ｆ⊗Ｎ≔⁺⟦Ｅυλ⟧Ｅ∧υ⌊υ⁺ＬυＥ⮌υ§μλυＥυ⪫Ｅι◧ＩλＬ⌈Ｅυ⌈ν

```

Try it online! Link is to verbose version of code. Edit: Saved 4 bytes by porting @Bubbler's observation that you can vectorised add the current length of the array to all of its elements on each iteration, 3 bytes by special-casing an empty array to avoid having to perform the first step manually, and 1 byte by golfing my rotation code. Explanation:

```
Ｆ⊗Ｎ

```

Repeat `2n` times.

```
≔⁺⟦Ｅυλ⟧Ｅ∧υ⌊υ⁺ＬυＥ⮌υ§μλυ

```

Rotate the spiral while adding its length to it values and prefix an additional row of numbers from `0` up to its length. (Unfortunately Charcoal won't let me vectorised add the length to the whole matrix at once but fortunately I can at least do it a row at a time as part of the rotation.) Also handle the edge case of the initially empty spiral which produces a zero-length array.

```
Ｅυ⪫Ｅι◧ＩλＬ⌈Ｅυ⌈ν

```

Display the final spiral as a grid.

# Answer
> 5 votes
# , ~~84~~ ~~81~~ 67 bytes

Or **\>=4.1, 60 bytes** by replacing the word `function` with a `\`.

*Edit: -14 bytes thanks to @Giuseppe inspired by @Bubbler's Jelly answer.*

```
function(n){m=t(1)
while(T<n)m=rbind(1:n,(T=nrow(m))+t(m[T:1,]))
m}

```

Try it online!

Uses the common "rotate and add a row on top" approach.

See also @Giuseppe's direct construction of the matrix.

# Answer
> 5 votes
# , 78 bytes

```
function(n)matrix(order(cumsum(rep(rep(c(n,1,-n,-1),,x<-2*n-1),n-1:x%/%2))),n)

```

Try it online!

Direct construction of the matrix, no rotations required.

# Answer
> 4 votes
# APL (Dyalog Unicode), 35 bytes

```
{(⍵*2)-⌽{⍉⌽⍵,(⌈/,⍵)+⍳≢⍵}⍣(2×⍵-1)⍪0}

```

Try it online!

# Answer
> 4 votes
# JavaScript (Node.js), 91 bytes

```
f=(n,s=[[n*n-1]],[l]=t=s[0])=>l?f(n,[0,...t].map((_,i)=>s.map(r=>r[i-1]||--l).reverse())):s

```

Try it online!

A port of loopy walt's Python answer. Although I don't really understand what happening.

# Answer
> 3 votes
# JavaScript (ES7),  ~~111~~  101 bytes

*Saved 9 bytes thanks to @tsh*

Returns a matrix. The results are 1-indexed.

```
n=>[...Array(n)].map((x=-n/2,y,a)=>a.map(_=>n*n-(i=4*(++x*x>y*y?x:y)**2)+(x>y||-1)*(i**.5+x+y),y+=x))

```

Try it online!

# Answer
> 3 votes
# Julia, 46 bytes

```
m\n=[1:n n.+rotl90(m')]'
!n=[n<2||!~-n\~-n\n;]

```

Try it online!

the simple rotate and add row, with some trickery with `'` (transpose)
starts with 1

# Answer
> 2 votes
# Jelly,  ~~34 33~~  32 bytes

I would have thought Jelly would be better at this, maybe a more mathematical approach will triumph?

```
ŒMḢḢ
+þ`¬ZṚ$ṛ¬Ç$¦€Ç¦‘ɼ$ḣÇȦƊ?ƬȦƇṂ

```

A monadic Link accepting a positive integer that yields a list of lists of positive integers (top-left `1` option).

**Try it online!**

### How?

Start with an \\$N\times N\\$ table of zeros, then repeatedly either fill in the next number in the first zero of the first row that contains a maximal value, unless that row is filled in which case rotate. This process terminates with a full table but rotated further than we want, so we collect all the states along the way then pick the one we need out (using `ȦƇṂ`).

```
ŒMḢḢ - Helper Link: list of list of integers (current state)
ŒM   - multidimensional indices of maximal elements
  Ḣ  - head
   Ḣ - head -> row index containing the maximum value

+þ`¬ZṚ$ṛ¬Ç$¦€Ç¦‘ɼ$ḣÇȦƊ?ƬȦƇṂ - Link: positive integer, N
+þ`                         - [1..N] addition table with [1..N]
   ¬                        - logical NOT -> N×N table of zeros
                       Ƭ    - collect inputs while distinct applying:
                      ?     -   if...
                     Ɗ      -   ...condition: last three links as a monad:
                   Ç        -     call our helper link
                  ḣ         -     head (the current state) to that index
                    Ȧ       -     all truthy when flattened?
      $                     -   ...then: last two links as a monad:
    Z                       -     transpose
     Ṛ                      -     reverse
                                  - this rotates when we've finished a row
                 $          -   ...else: last two links as a monad:
                ɼ           -     apply to the register (initially 0) & yield:
               ‘            -       increment
              ¦             -     sparse application...
             Ç              -     ...to indices: call our helper link
            €               -     ...apply: for each:
           ¦                -       sparse application...
          $                 -       ...to indices: last two links as a monad:
        ¬                   -         logical NOT (vectorises)
         Ç                  -         call our helper link
       ṛ                    -       ...apply: the incremented register value
                         Ƈ  - filter keep those for which:
                        Ȧ   -   all truthy when flattened?
                          Ṃ - minimum (of the rotate tables we have left)

```

---

Another approach, but even more lengthy at 39:

```
RµṚĖm€0F;Ɱ"ḊṚ’$ṖṚ4ƭ³’Ḥ¤Ð¡UÐeẎIƇŒṬ€×"J$S

```

Try this one

This one works by building a list of the two-dimensional indices ordered by their final value then composing the table by adding up tables that are all zeros except the bottom-rightmost entry which is the number we want there in the end.

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

```
n=>[...Array(n)].map((_,Y,a)=>a.map(g=(y=Y,x,_,s=n)=>y?--s-x?s-y?x?s*4+g(y-1,x-1,_,s-1):4*s-y:3*s-x:s+y:x));

```

Try it online!

# Answer
> 2 votes
# 05AB1E, 13 bytes

```
¯I·FāUøí¬g+Xš

```

1-based.

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

Try it online or verify all test cases.

**Explanation:**

```
¯             # Start with an empty list []
 I·           # Push the input and double it
   F          # Pop and loop that many times:
    ā         #  Push a list in the range [1,length] (without popping the matrix)
     U        #  Pop and store this list in variable `X`
      øí      #  Rotate the matrix 90 degrees clockwise:
      ø       #   Zip/transpose; swapping rows/columns
       í      #   Reverse each row
        ¬     #  Push the first row (without popping the matrix)
         g    #  Pop and push its length
          +   #  Add that to each value in the matrix
           Xš #  Prepend `X` as first row
              # (after the loop, the resulting matrix is output implicitly)

```

# Answer
> 2 votes
# , ~~187~~ ~~183~~ 151 bytes

```
function(n){w=which
X=diag(0,n)
X[n,]=m=n:1
while(!min(X)){i=w(!X)[1]
j=w(!!X[-1:-i])
X[i-1+1:j]=max(X)+j:1
X=t(X)[m,]}
`if`(n%%2,t(t(X)[m,])[m,],X)-1}

```

Try it online!

A clumsier version of rotate and fill!

# Answer
> 1 votes
# Factor \+ `math.matrices`, ~~82~~ 79 bytes

```
[ 2 * { } [ dup length [ m+n flip [ reverse ] map ] keep iota prefix ] repeat ]

```

Try it online!

Port of @Bubbler's excellent Jelly answer.

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

-8 bytes thanks to @att.

```
Nest[Join[{l=0;l++&/@#},Reverse@#+l]&,{{}},2#-1]&

```

Try it online!

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


title: Check if the string is reshaped

text:
# Question
Title: Check if the string is reshaped
## Challenge

Given an input string `X`, determine if `X` can be obtained from reshaping a *strict prefix* of itself (a prefix that is not `X` itself).

Reshaping a string to a length `N` means repeating the string as many times as needed and then taking the first `N` characters of it.

## Examples:

The string `"abba"` returns Truthy becacause `"abb"` can be reshaped to length 4 to obtain `"abba"`.

The string "acc" returns Falsy becacause none of its strict prefixes (`"a"`, `"ac"`) can be reshaped to obtain `"acc"`.

(Outputs must be consistent)

## Test cases:

```
AA => 1
ABAba => 0
!@#$%&()_+! => 1
AAc => 0
ababababba => 1
abcdeabc => 1
abacabec => 0
@|#|#|@#|@||@#@||@|#| => 1
10101101101010110101011101111011110110110101101101010110010101101101010110 => 1
17436912791279205786716328174301174187417348216070707180471896347218574617954278517034215720138543912791279205786716328174301174187417348216070707180471896347218574617954278517034215720286716328174301174187417348216070707180471896347218574617954278517034219127912792057867163281743011741874173482160707071804718963472185746179542785170342157205720475941259275912791279205786716328174301174187417348216070707180471896347218574617954278517034215720475941252867163281743011741874173482160707071804718963472185746179542785170342157204759412517436912791279205786716328174301174187417348216070707180471896347218574617954278517034215720138543912791279205786716328174301174187417348216070707180471896347218574617954278517034215720286716328174301174187417348216070707180471896347218574617954278517034219127912792057867163281743011741874173482160707071804718963472185746179542785170342157205720475941259275912791279205786716328174301174187417348216070707180471896347218574617954278517034215720475941252867163 => 1

```

# Answer
# Jelly, 5 bytes

```
ṁƤinL

```

Try it online!

## How it works

```
ṁƤinL - Main link. Takes a string S on the left
 Ƥ    - Over each prefix P of S:
ṁ     -   Mold to length S
  i   - First index of S
    L - Length of S
   n  - Are these two unequal?

```

Essentially, the index and length will only be equal if the only reshaped prefix equal to S is the full prefix i.e. a non-proper prefix
> 5 votes

# Answer
# Retina, 10 bytes

```
^(.+).*\1$

```

Try it online!

Works in any flavor of regex that supports backreferences.
> 14 votes

# Answer
# Charcoal, 10 bytes

```
⊙θ⁼…θκ✂θ±κ

```

Try it online! Link is to verbose version of code. Explanation: Simply checks whether any prefix of the input is also a suffix. The edge case of the empty prefix is ignored because you can't slice an empty suffix using a negative slice offset.

```
 θ          Input string
⊙           All indices satisfy
    θ       Input string
   …        Truncated to length
     κ      Current index
  ⁼          Equals
       θ    Input string
      ✂     Sliced from
         κ  Current index
        ±   Negated

```
> 9 votes

# Answer
# Ruby -n, 15+1 bytes

```
p ~/^(.+).*\1$/

```

Try it online!
> 7 votes

# Answer
# Haskell, 56 bytes

```
f s=any(and.zipWith(==)s.cycle.(`take`s))[1..length s-1]

```

Try it online!

---

# Haskell, ~~54~~ 53 bytes

Based on Neil's answer: Checks if any proper prefix is a suffix.

```
import Data.List
f s=init(1<$s)>(1<$inits s\\tails s)

```

Try it online!
> 7 votes

# Answer
# Haskell, 57 bytes

```
f x|l<-length x=or[x==take l(cycle$take n x)|n<-[1..l-1]]

```

Try it Online!

-2 bytes thanks to ovs
> 5 votes

# Answer
# BQN, 11 bytesSBCS

```
⊑⋈∊≠⥊¨2↓»∘↑

```

Run online!

Notes:

A train which roughly translates to `{⊑(⋈)∊(≠)⥊¨2↓»∘↑}` akin to APL, except we have a single byte prefixes builtin.

-1 from ovs.
> 4 votes

# Answer
# Vyxal `r`, 7 bytes

```
L?¦ṪvẎc

```

Try it Online!

```
   Ṫ    # All but last
  ¦     # Of prefixes
 ?      # Of the input
    v   # Each
     Ẏ  # Extended to...
L       # Input length
      c # Includes input

```
> 4 votes

# Answer
# Brachylog, 5 bytes

```
~ca₀ᵈ

```

Try it online!

Ungodly slow on even mid-sized failing inputs; the essentially equivalent `~c₂a₀ᵈ` is much more performant: Try it online!

```
~c       Some partition of the input
    ᵈ    is a list of two elements such that the first has the second as
  a₀     a nonempty prefix.

```
> 4 votes

# Answer
# Husk, 7 bytes

```
ṁȯ€tṫ¹ḣ

```

Try it online!

Same approach as Neil's answer and tsh's comment: 'is any prefix of input string also one of its suffixes?'

```
ṁȯ    ḣ  # map over each of the prefixes of the input:
  €      #  is it present within...
   t     #  the tail of (=drop the first element of)...
    ṫ¹   #  the suffixes of the input?
ṁ        # sum the answers
         # (so output is non-zero (truthy) for re-shapable strings)

```
> 3 votes

# Answer
# Haskell \+ hgl, 13 bytes

```
cP$h_<*h'>~ʃ

```

If you can simply submit a parser object, then that can be 10 bytes:

```
h_<*h'>~ʃ

```

## Explanation

* `h_` parses at least one thing off the front of a list (think `.+` in regex).
* `h'` parses any amount off the front of a list (think `.*` in regex).
* `ʃ` is a function which takes an string and produces a parser which matches exactly that string.

We combine the two with `<*` which runs both sequentially giving the result of the first. Then we bind this to `ʃ`, so that the result of `h_` is passed as the input to `ʃ`.

In do notation this would be

```
do x<-h_;h';ʃ x

```

Described in plain English this matches any string that contains the same non-empty section at both the start and end.

# Non-parser, ~~17~~ 15 bytes

The parsers are obviously the way to go for this challenge, but I thought I'd give it a go without them to see how good hgl does.

```
lt 2<(cn**sw)sx

```

## Explanation

* `sx` gets all prefixes of a list
* `sw` checks if a particular list starts with another.
* `cn` counts the number of elements that satisfy a predicate.
* `(**)` is an infix for `liftA2`.

So altogether `(cn**sw)sx` counts the number of suffixes of the list are also prefixes.

Now, the empty string and the input string should always pass this test. So we want to test if there is *another* string which also is both a prefix and a suffix. So we use `lt 2` to check that's greater than `2`.

## Notes

Some things that could have been better for hgl in this challenge.

* There should be a function `lt2=lt 2` (and `gt1`, `lt3` etc.). That would have saved a byte here.
* `(**)` has the default precedence which although not causing any issues here, could probably be improved.
* Variants of `px` and `sx` that give for example non-empty or strict prefixes / suffixes would probably be useful. If I had a function that specifically gave non-empty and strict suffixes then I could just do `ay**sw$sxS` (where `sxS` is the imagined function) for 10 bytes.
> 3 votes

# Answer
# APL (Dyalog Unicode), 10 bytes

```
⊂∊≢⍴¨¯1↓,\

```

Try it online!

From Kamila's answer and upvote that!
> 2 votes

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

```
s=>s.replace(/./g,c=>((p+=c)+p).indexOf(s)+1,p='')>1

```

Try it online!

Partial based on Redwolf Programs's answer.

---

# JavaScript (Node.js), 56 bytes

```
s=>(g=p=>s[0]&&(p+=s.shift())==(q=s.pop()+q)|g(p))(q='')

```

Try it online!
> 2 votes

# Answer
# , 11 bytes

```
e.#$&><\@}:

```

Try it online!

This one is kind of tailor made for J.

* `e.` Is the input an element of...
* `<\@}:` Each prefix except the last...
* `#$&>` Shaped to the original input's length.
> 2 votes

# Answer
# JavaScript (ES6), 23 bytes

```
x=>/^(.+).*\1$/.test(x)

```

Try it online!

Or if a function that can't be bound to a variable is allowed, 17 bytes:

```
/^(.+).*\1$/.test

```

Try it online!

Regex completely stolen from G B's answer, go upvote that!
> 2 votes

# Answer
# Python 3, 55 bytes

```
lambda s:any(s in s[:x]*len(s)for x in range(1,len(s)))

```

Try it online!

Porting regexes are boring, so non regex one
> 2 votes

# Answer
# Python 3, 49 bytes

```
f=lambda s,i=1:s>s[:i]and(s[i:]==s[:-i])|f(s,i+1)

```

Try it online!
> 2 votes

# Answer
# , ~~77~~ ~~73~~ 69 bytes

```
function(s)any(grepl(s,paste0(r<-substring(s,0,nchar(s):1-1),r),f=T))

```

Try it online!

Outputs `TRUE`/`FALSE`.
> 2 votes

# Answer
# , ~~74~~ ~~72~~ 70 bytes

Or **\>=4.1, 63 bytes** by replacing the word `function` with a `\`.

*Edit: -2 bytes thanks to @Dominic van Essen.*

```
function(s,n=sum(s|1)){for(i in 2:n)T=T&any(s[1:i-1]-s[n+2-i:1]);!T+1}

```

Try it online!

Non-regex approach (that would be simple port of other answers: `function(s)grepl("^(.+).*\\1$",s)`).

Takes input as a vector of char codes.

Outputs `NA` as truthy and `FALSE` as falsy.
> 2 votes

# Answer
# 05AB1E, ~~8~~ 7 bytes

```
.sI¨ηåà

```

-1 byte by porting *@Neil*'s Charcoal answer.

Try it online or verify all test cases.

**Original 8 bytes answer:**

```
¨ηIgδ∍Iå

```

Try it online or verify all test cases.

**Explanation:**

```
.s        # Get the suffixes of the (implicit) input
  I¨      # Push the input-string, and remove its last character
    η     # Get the prefixes of this string
     åà   # And check if any is in the suffixes-list
          # (after which the result is output implicitly)

¨         # Remove the last character of the (implicit) input-string
 η        # Take its prefixes
    δ     # Map over each prefix:
     ∍    #  And extend each to a length equal to
  Ig      #  the length of the input
      Iå  # Then check if the input is in this list
          # (after which the result is output implicitly)

```

The second program could have been 7 bytes if the input is never an integer by removing the `g`, because  will extend to the length of given string and list arguments: verify (almost) all test cases without `g`, and see how it now fails for `1001` and `1101`.
> 2 votes

# Answer
# Excel, 72 bytes

```
=LET(x,SEQUENCE(LEN(A1)/2),OR(SUBSTITUTE(LEFT(A1,x),RIGHT(A1,x),"")=""))

```

Link to Spreadsheet

String comparisons in Excel are not case sensitive but `SUBSTITUTE` is.
> 2 votes

# Answer
# JavaScript (ES6), 64 bytes

*-13 thanks to @pxeger*

```
s=>[...s].some((_,i)=>!s.slice(0,i).repeat(s.length).indexOf(s))

```
> 1 votes

# Answer
# Vyxal, 9 bytes

```
K'?~•f⁼;₃

```

Try it Online!

Ah yes, the limitations of type overloading. Returns `0` for Truthy inputs and `1` for Falsey inputs.

## Explained

```
K'?~•f⁼;₃  # Takes input as a list of characters
K          # Prefixes of the input
 '         # Keep items where:
  ?~•      #   The item molded to the shape of the input
     f⁼    #   is the same as the input (i.e. non-vectorised equality)
       ;   # Close filter.
        ₃  # Is the length of the list 1? For falsey inputs, the resulting list will just contain the input meaning it doesn't have any truthy prefixes.

```
> 1 votes

# Answer
# Wolfram Language (Mathematica), 82 Characters

Try Online Practically the most basic answer I could think of. Tried some fancy things like converting into a list of characters or using some sort of trick instead of StringRepeat, but the bytes came out better this way.

```
Or@@Table[
StringRepeat[StringTake[#,i],∞,StringLength@#]==#,{i,StringLength@#-1}]&

```

Explanation: Iterates i from 1 to the length of the string - 1, and repeats the first i characters until it matches the length of the original. Then, it compares this value to the original and computes whether any of them are true.

I don't know/remember how many characters Infinity counts as, so if that's a problem, I have an 88 character solution without any special chars:

```
Block[{v=Characters@#},
Or@@Table[
    PadRight[v~Take~i,Tr[1^v],v~Take~i]==v,{i,Tr[1^v]-1}]]&

```

This converts the string into a list and saves it as a variable, which costs 24 characters, but makes the rest far shorter. I can't just define v as a global variable since that messes up the pure function, and writing out Characters@# is far too long to not be a variable.
> 1 votes

# Answer
# Factor \+ `grouping.extras math.unicode sequences.repeating`, 59 bytes

```
[ dup head-clump 1 head* [ over length cycle = ] with ∃ ]

```

Try it online!

## Explanation

```
                         ! "abba"
dup                      ! "abba" "abba"
head-clump               ! "abba" { "a" "ab" "abb" "abba" }
1 head*                  ! "abba" { "a" "ab" "abb" }
[ over length cycle = ]  ! "abba" { "a" "ab" "abb" } [ over length cycle = ]
with                     ! { "a" "ab" "abb" } [ "abba" [ over length cycle = ] swapd call ]

```

Alias for `any?` -- Does the quotation return `t` for any elements in the sequence? Inside the quotation now for the first element...

```
                         ! "abba" "a"
over                     ! "abba" "a" "abba"
length                   ! "abba" "a" 4
cycle                    ! "abba" "aaaa"
=                        ! f

```

Second element

```
                         ! "abba" "ab"
over                     ! "abba" "ab" "abba"
length                   ! "abba" "ab" 4
cycle                    ! "abba" "abab"
=                        ! f

```

Third

```
                         ! "abba" "abb"
over                     ! "abba" "abb" "abba"
length                   ! "abba" "abb" 4
cycle                    ! "abba" "abba"
=                        ! t

```
> 1 votes

# Answer
# Japt `-d`, 6 bytes

```
W¶îVîW

```

Try it
> 1 votes

# Answer
# Canvas, 9 bytes

```
［；Ｌｍ≡］ｋ∑‼

```

Try it here!

Can remove  to save a byte if *any* truthy output (not necessarily consistent) is allowed.
> 1 votes

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


title: Matching ABACABA-type patterns

text:
# Question
Title: Matching ABACABA-type patterns
(This challenge is related to the challenge "Generate the Abacaba sequence.")

Zimin words (also called "sesquipowers") are an important idea in the subject of "combinatorics on words". This is because every Zimin word is "unavoidable", meaning that every sufficiently long word over a finite alphabet has a substring that is an "instance" (defined below) of the Zimin word. Remarkably, *every* binary word of length 29 has a substring that is an instance of the pattern \\$ABACABA\\$.

### Definitions

Zimin words are recursively defined:

* \\$Z\_1 = A\\$
* \\$Z\_2 = ABA\\$
* \\$Z\_3 = ABACABA\\$
* \\$Z\_4 = ABACABADABACABA\\$
* \\$\vdots\\$
* \\$Z\_{n+1} = Z\_n X Z\_n\\$

It's a little tricky to formally define what it means to be an "instance" for a word without talking about free monoids and homomorphisms, but it's easy enough to see from some examples. At a hand-wave-y level, a word \\$w\\$ is said to be an "instance" of a pattern if there's a way to assign a (non-empty) string to each letter of the pattern and recover \\$w\\$.

### Examples

Consider the word `"11211212211221"` on two letters.

* It has \\$105\\$ substrings that are instances of the Zimin word \\$Z\_1 = A\\$ because every substring is an instance of \\$A\\$.
* It has \\$54\\$ substrings that are instances of the Zimin word \\$Z\_2 = ABA\\$—for example, the substring `"212211221"`: $$ 11211\underbrace{21}\_A\underbrace{22112}\_B\underbrace{21}\_A. $$
* It has \\$1\\$ substring that is an instance of the Zimin word \\$Z\_3 = ABACABA\\$: $$ 11 \underbrace{2}\_A \underbrace{11}\_B \underbrace{2}\_A \underbrace{12}\_C \underbrace{2}\_A \underbrace{11}\_B \underbrace{2}\_A 21. $$
* It has \\$0\\$ substrings that are instances of the Zimin word \\$Z\_4 = ABACABADABACABA\\$.

Thus if you are given `"11211212211221"`, you should return `[105, 54, 1]`.

### Challenge

This challenge will give you a word as an an input, and asks you to output a list of the number of substrings that are instances \\$Z\_1, Z\_2, \cdots, Z\_n\\$ until there are not any substrings that are instances. That is, your program should never output `0`.

You can take the word in any reasonable way: as a string, as a list of strings, as a list of appropriately coded integers, as a pair of integers \\$(b,i)\\$ where \\$i\\$ is base-\\$b\\$ encoded integer, etc.

### Test Data

```
word                           | zimin_counts(word)
-------------------------------+-------------------
""                             | []
"P"                            | [1]
"MOM"                          | [6,1]
"alfalfa"                      | [28, 8]
"aha aha!"                     | [36, 9, 1]
"xxOOOxxxxxOOOxxx"             | [136, 64, 9]
"3123213332331112232"          | [190, 55, 1]
"2122222111111121221"          | [190, 80, 3]
"13121311213121311212"         | [210, 114, 25, 2]
"344112222321431121114"        | [231, 48]
"141324331112324224341"        | [231, 49]
"344342224124222122433"        | [231, 61, 1]
"331123321122132312321"        | [231, 74]
"11221112211212122222122"      | [276, 149, 4]
"2222222112211121112212121"    | [325, 166, 6]
"AAAaaAAAAAAAaAaAAaAaAAAAA"    | [325, 198, 30]
"1100000010010011011011111100" | [406, 204]
"1111221211122111111221211121" | [406, 261, 56, 2]

```

# Answer
# Brachylog, 30 bytes

```
{s{h∧1|~cṪ↺₁hʰb=h↰ᶠ⌉+₁}ᵘ}ᶠcọtᵐ

```

Try it online!

* `{s … }ᶠ` for every substring:
* `{h∧1| …}` on every non-empty string, return 1. Also try …
* `~c` input split into groups, so that …
* `Ṫ↺₁…b=` it unifies with `[A,B,A]` (this works, too, but is sadly longer).
* B is non-empty
* `h↰ᶠ` take `A` and call the predicate recursively, finding all results
* `⌉+₁` get the highest number and add 1
* Find all unique values. So for `aha aha` we get `[1,2,3]` from `[aha aha, aha, a]`.
* `cọtᵐ` join the results from all the substrings, count the occurrences of each number, and return them
> 6 votes

# Answer
# , 63 58 53 52 51 47 bytes

```
_1}.1#.a:~:[:([#~[e.&,(],,)&.>/)^:a:~@;<@(<\)\.

```

Try it online!

-2 bytes thanks to Bubbler

-3 bytes thanks to FrownyFrog for golfier way to create all substrings of a string.

## how

We'll use `MOM` as our example:

* `[:...;<@(<\)\.` All substrings of the input, boxed.

```
┌─┬─┬─┬──┬──┬───┐
│M│O│M│MO│OM│MOM│
└─┴─┴─┴──┴──┴───┘

```
* `(...)^:a:~` Using the substrings as both the left and right args `~`, apply the verb in parens until a fixed point, keeping track of each iteration's results `^:a:`.
* `(...(],,)&.>/)` To create the next "level" of candidates, create all possible combinations that look like `<level_n><orig substring><level_n>` where `level_n` is any element from the current level, and `<orig substring>` is one of the original input substrings (level 0). Then the 1st level looks like:

```
┌─────┬─────┬─────┬───────┬───────┬─────────┐
│MMM  │OMO  │MMM  │MOMMO  │OMMOM  │MOMMMOM  │
├─────┼─────┼─────┼───────┼───────┼─────────┤
│MOM  │OOO  │MOM  │MOOMO  │OMOOM  │MOMOMOM  │
├─────┼─────┼─────┼───────┼───────┼─────────┤
│MMM  │OMO  │MMM  │MOMMO  │OMMOM  │MOMMMOM  │
├─────┼─────┼─────┼───────┼───────┼─────────┤
│MMOM │OMOO │MMOM │MOMOMO │OMMOOM │MOMMOMOM │
├─────┼─────┼─────┼───────┼───────┼─────────┤
│MOMM │OOMO │MOMM │MOOMMO │OMOMOM │MOMOMMOM │
├─────┼─────┼─────┼───────┼───────┼─────────┤
│MMOMM│OMOMO│MMOMM│MOMOMMO│OMMOMOM│MOMMOMMOM│
└─────┴─────┴─────┴───────┴───────┴─────────┘

```
* `[#~[e.&,...` Check if each original substring is an element of this candidate list `[e.&,`, and use that to filter the original substrings `[#~`. In the above example, only `MOM` passes.
* After the above process iterates to its fixed point (no more matches), the result is:

```
┌───┬─┬─┬──┬──┬───┐
│M  │O│M│MO│OM│MOM│
├───┼─┼─┼──┼──┼───┤
│MOM│ │ │  │  │   │
├───┼─┼─┼──┼──┼───┤
│   │ │ │  │  │   │
└───┴─┴─┴──┴──┴───┘

```
* `a:~:` Since we don't want to count empty boxes, we perform an elementwise test for "not equal to the empty box `a:`", giving us a 0-1 matrix:

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

```
* `1#.` Sum rows:

```
6 1 0

```
* `_1}.` And kill the last element:

```
6 1

```
> 10 votes

# Answer
# JavaScript (ES6),  ~~148 142~~  141 bytes

*Saved 6 bytes thanks to @user81655*

Expects an array of characters.

```
f=(a,o=[],s='')=>a.map(c=>{for(s+=c,i=p='';s.match(`^${p+='(.+)'+p.replace(/\(.../g,_=>"\\"+n++)}$`);n=1)o[+i]=-~o[i++]})+a?f(a.slice(1),o):o

```

Try it online!

### How?

For each substring in the input string, we apply the following patterns while they match:

```
P₀  ^(.+)$
P₁  ^(.+)(.+)\1$
P₂  ^(.+)(.+)\1(.+)\1\2\1$
P₃  ^(.+)(.+)\1(.+)\1\2\1(.+)\1\2\1\3\1\2\1$
    ...

```

Apart from the delimiters `^` and `$` which are ignored below, these patterns are built recursively as follows:

* \\$P\_0\\$ is `(.+)`
* \\$P\_{k+1}\\$ is \\$P\_{k}\\$, followed by `(.+)`, followed by \\$P\_k\\$ with each \\$n\\$-th group `(.+)` replaced with the back reference `\{n}` (1-indexed)

e.g. for \\$P\_2 \rightarrow P\_3\\$:

```
(.+)(.+)\1(.+)\1\2\1 -> (.+)(.+)\1(.+)\1\2\1 (.+) ~~(.+)(.+)~~\1~~(.+)~~\1\2\1
                                                   \1  \2    \3
```

It's worth noting that:

* if a substring matches some \\$P\_i\\$, it also matches all \\$P\_j,\\:j\i\\$

We keep track of the results in the array `o[]`, which is eventually returned. Whenever \\$P\_i\\$ matches a substring, we increment `o[i]`.
> 8 votes

# Answer
# Retina, 77 bytes

```
K`(.+)
/\(/{G`
%"$+"~`^
w`
"¶0"(Am`^0
K`

$+2
(.*?\))+(.*)$
$&¶$&(.+)$2\$#1$2

```

Try it online! No test suite because of the advanced use of result history. Explanation:

```
K`(.+)

```

Start by considering matches of Z₁.

```
/\(/{`

```

Repeat while the working area contains a `(`.

```
G`

```

Do nothing. This is here solely to record the value at the start of each pass of the loop in the stage history, so that it can be referred to later on.

```
%"$+"~`^
w`

```

Processing each line of regex separately, evaluate it as an overlapped count command on the original input, thereby returning a list of counts.

```
"¶0"(`

```

If the list contains a `0` (strictly speaking this can only happen on the second pass, as I use a newline to check that it's a leading 0)...

```
Am`^0

```

... then delete all `0` values (including the first if the input string was empty), otherwise:

```
K`

$+2

```

Retrieve the value saved in step 2. (Because Retina numbers stages in post-order traversal, this is the `G` command.) Unfortunately `$` doesn't work directly in a `K` command, so the easiest way to do this is to delete the result and then substitute the empty string with the saved value.

```
(.*?\))+(.*)$
$&¶$&(.+)$2\$#1$2

```

Append an additional regex that matches the next Zimin word.
> 2 votes

# Answer
# 05AB1E, 31 bytes

```
āεo<VŒε.œYùεĆ4ô€¨yªεÂQ}P}1å]O0Ü

```

Try it online or verify some more test cases (pretty slow, so the larger test cases are omitted in the test suite).

**Explanation:**

Step 1: Loop over the possible sizes \\$n\\$ of the \\$Z\_n\\$ based on the input-length.

We can calculate the valid \\$n\\$ to check with the following formula: \\$m = \left\lceil\log\_2(L)\right\rceil\\$, where \\$L\\$ is the input-length, and the result \\$m\\$ indicates the range \\$\[1,m\]\\$ to check for Zimin 'words': \\$Z\_{n=1}^m\\$.

In 05AB1E code, this would have resulted in `g.²îLεo<VŒε.œYùεĆ4ô€¨yªεÂQ}P}1å]O0Ü` (**35 bytes**): try it online.

Since we have to strip trailing 0s at the end in case no \\$Z\\$ were found for them anyway, we simply don't calculate this maximum. Instead, we'll just check in the range \\$\[1,L\]\\$ for Zimin words. Less efficient in terms of performance, but 4 bytes shorter, which is all we care about with . :)

We can also calculate the amount of parts in the resulting Zimin 'word' (\\$Z\_n\\$), which is the oeis sequence A000225: \\$2^n-1\\$.

```
ā              # Push a list in the range [1, (implicit) input-length]
 ε             # Map over each of these integers:
  o            #  Take 2 to the power this integer
   <           #  Decrease it by 1
    V          #  Pop and store this in variable `Y`

```

Step 2: For each of these amount of parts \\$Y\\$, we check how many substrings of the input are valid Zimin 'words' (\\$Z\_Y\\$).

Step 2a: We do this by first generating all substrings of the input, and mapping over them:

```
  Œ            #  Get all substrings of the (implicit) input-list
   ε           #  Inner map over each substring:

```

Step 2b: Then we'll get all partitions of the current substring of exactly \\$Y\\$ amount of parts:

```
    .œ         #   Get all partitions of this subtring
      Yù       #   Only leave the partitions of `Y` amount of parts

```

Step 2c: We then check for each of these (correctly sized) partitions of this substring if it's a valid Zimin 'word'.
We do this by checking two things:

1. Is the current list of parts in this partition a palindrome?
2. Is every \\$ABA\\$ part within the current partition a palindrome?

As for step 2c2, we do so by first adding a dummy trailing item to the partition; then splitting the partition-list into sublists of size 4; then we remove the trailing item from each of these sublists; after which we can check for each \\$\[A,B,A\]\\$ sublist whether it's a palindrome.

```
        ε      #   Inner map over each remaining partition:
         Ć     #    Enclose the partition; append its own first part at the end
          4ô   #    Split the partition into parts of size 4
            €¨ #    Remove the final part of each quartet
         yª    #    Append the full partition to this list of triplets as well
           ε   #    Inner map over this list of lists:
               #     Check if the current list is a palindrome by:
            Â  #      Bifurcating: short for Duplicate & Reverse copy
             Q #      Check if the list and reversed copied list are the same
           }   #    After this inner-most map:
            P  #    Check if all were truthy by taking the product

```

Alternatively for step 2c2, `Ć4ô€¨` could have been `4ô3δ∍` instead: Split the partition-list into sublists of size 4 (with 3 in the trailing sublist); shorten each sublist to size 3 by removing trailing item(s); same as above. Try it online.

Step 2d: And we then check if there is at least one valid Zimin 'word' (\\$Z\_Y\\$) among the mapped partitions for this substring:

```
       }       #   After the map over the partitions of the current substring:
        1å     #   Check if any were truthy by checking if it contains a 1
               #   (NOTE: we can't use the max builtin `à` here like we usually do when
               #    we want to mimic an `any` builtin, because lists could be empty here,
               #    resulting in an empty string)

```

Step 3: Now we sum the amount of truthy results per size \\$Y\\$:

```
]              # Close all remaining nested maps
 O             # Sum the inner-most lists together

```

Step 4: And finally we clean-up all trailing 0s (both the \\$\geq m\\$ sizes we've checked in our golfed approach, as well as any trailing \\$Z\\$ within the \\$\[1,m\]\\$ range that simply resulted in \\$0\\$), before outputting the result:

```
  0Ü           # Remove any trailing 0s from this list
               # (after which the resulting list is output implicitly)

```
> 2 votes

# Answer
# Python 3, 205 bytes

```
def f(w):
 R=range(len(w));s=[w[i:j+1]for i in R for j in R[i:]];v=[*s];n=len(s);r=[]
 while n:r+=[n];s={i+j+i for i in s for j in v if i+j+i in w};n=sum(len({w.find(a,b)for b in R})-1for a in s)
 return r

```

Try it online!

*Quite* verbose.
Inputs a string and returns a list of the number of substrings that are instances \\$Z\_1, Z\_2, \dots, Z\_n\\$.
> 1 votes

# Answer
# Wolfram Language (Mathematica), 66 bytes

```
Counts@Level[z@@@Subsequences@#,-3]&
z[Longest@a___,__,a___]:=z@a!

```

Try it online!

Returns an `Association` with corresponding values. Prepend `List@@` for list output.
> 1 votes

---
Tags: code-golf, math, combinatorics, pattern-matching
---


title: Find the nth Fibohexaprime

text:
# Question
Title: Find the nth Fibohexaprime
The challenge this time is to find the *n*th *Fibohexaprime*. The definition of a *Fibohexaprime* is as following:

We first observe a list with Fibonacci numbers:

```
N  | Fibonacci number
1  | 1
2  | 1
3  | 2
4  | 3
5  | 5
6  | 8
7  | 13
8  | 21
9  | 34
10 | 55
11 | 89
12 | 144
13 | 233
14 | 377
15 | 610
16 | 987
17 | 1597

```

After that, we convert the numbers to hexadecimal:

```
N  | Fib  | Hex
1  | 1    | 1
2  | 1    | 1
3  | 2    | 2
4  | 3    | 3
5  | 5    | 5
6  | 8    | 8
7  | 13   | D
8  | 21   | 15
9  | 34   | 22
10 | 55   | 37
11 | 89   | 59
12 | 144  | 90
13 | 233  | E9
14 | 377  | 179
15 | 610  | 262
16 | 987  | 3DB
17 | 1597 | 63D

```

From the hexadecimal numbers, we filter out the letters. All we are left with are numbers. We need to check if these numbers are prime:

```
hex |  filtered |  is prime? |  N =
1   >  1        >  false
1   >  1        >  false
2   >  2        >  true         1
3   >  3        >  true         2
5   >  5        >  true         3
8   >  8        >  false
D   >  0        >  false
15  >  15       >  false
22  >  22       >  false
37  >  37       >  true         4
59  >  59       >  true         5
90  >  90       >  false
E9  >  9        >  false
179 >  179      >  true         6
262 >  262      >  false
3DB >  3        >  true         7
63D >  63       >  false

```

If the filtered number is a prime, we call this a **Fibohexaprime**. You can see that for `N = 7`, the related fibonacci number is 987.

The task is simple, when given an input using STDIN or an acceptable alternative, write a program or a function which outputs the nth Fibohexaprime using STDOUT or an acceptable alternative.

Test cases

```
Input - Output
1     - 2
2     - 3
3     - 5
4     - 55
5     - 89
6     - 377
7     - 987
8     - 28657
9     - 75025
10    - 121393
11    - 317811
12    - 5702887
13    - 9227465
14    - 39088169
15    - 102334155
16    - 32951280099
17    - 4052739537881
18    - 806515533049393
19    - 7540113804746346429

```

The rules:

* Given an integer between `1` and `19` (the values above `20` exceed the max value for a 64-bit signed integer), output the corresponding value.
* You may write a function or a program.
* This is , so the submission with the least amount of bytes wins!

# Answer
# Pyth, 27 bytes

```
Leu,eGsGbU2ye.fq1lPs-.HyZGQ

```

Demonstration

`y` computes the nth Fibonacci number. A `.f` loop finds the fibohexaprime according to the input.
> 4 votes

# Answer
## MATL, 28 bytes

This uses MATL version 1.0.0, which was published in Esolangs on December 12, earlier than this challenge.

```
1Hi:"`tb+t16YAt58<)YtZp~]]1$

```

### Example

```
>> matl 1Hi:"`tb+t16YAt58<)YtZp~]]1$
> 10
121393

```

### Explanation

The code is similar to that in Martin Büttner's answer.

```
1           % number literal
H           % paste from clipboard H. Initial contents: 2
i:          % vector of equally spaced values from 1 to input value
"           % for
  `         % do...while
    t       % duplicate
    b       % bubble up element in stack
    +       % addition
    t       % duplicate
    16YA    % convert integer to string representation in base 16
    t       % duplicate
    58      % number literal: first ASCII code after '9'
    <       % is less than? (element-wise)
    )       % reference () indexing with logical index from previous comparison
    Yt      % convert string to number
    Zp      % true for prime numbers
    ~       % logical 'not'
  ]         % end
]           % end
1$          % input specification for final implicit display function

```
> 12 votes

# Answer
## CJam, 28 bytes

```
TXri{{_@+_Gb{A<},Abmp!}g}*p;

```

Test it here.

### Explanation

```
TX        e# Push 0 and 1 to initialise Fibonacci computation.
ri        e# Read input and convert to integer N.
{         e# Run this block N times...
  {       e#   While the condition on top of the stack is truthy...
    _@+   e#     Compute next Fibonacci number (dropping the second-to-last one).
    _Gb   e#     Duplicate and convert to base 16.
    {A<}, e#     Keep only digits less than 10.
    Ab    e#     Convert from base 10.
    mp!   e#     Check that it's not a prime.
  }g
}*
p;        e# Print the last number we found and discard the one before.

```
> 8 votes

# Answer
# Perl 6, 62 bytes

My first pass of just get it to work was:

```
{(grep *[1].is-prime,map {$_,+[~] .base(16)~~m:g/\d/},(1,1,*+*...*))[$_-1;0]} # 77

```

By combining the `grep` and the `map`, I can remove 10 bytes

```
{(map {$_ if is-prime [~] .base(16)~~m:g/\d/},(1,1,*+*...*))[$_-1]} # 67

```

If I use `grep` instead of `map`, I save 5 more bytes:

```
{(grep {is-prime [~] .base(16)~~m:g/\d/},(1,1,*+*...*))[$_-1]} # 62

```

usage:

```
# give it a name
my &code = {...}

say code $_ for 1..^20;

2
3
5
55
89
377
987
28657
75025
121393
317811
5702887
9227465
39088169
102334155
32951280099
4052739537881
806515533049393
7540113804746346429

```
> 7 votes

# Answer
# Mathematica 111 bytes

There may still be room for additional golfing.

```
t=Table[Fibonacci@k,{k,1600}];f@n_:=PrimeQ@FromDigits[Select[n~IntegerDigits~16,#<10&]];
g@k_:=Select[t,f][[k]]

```

---

```
g[7]

```

> 987

---

```
g[19]

```

> 7540113804746346429
> 3 votes

# Answer
# Julia, 123 bytes

```
n->(a=[];i=1;while endof(a)<n b=([1 1;1 0]^i)[1];(s=filter(isdigit,hex(b)))>""&&isprime(parse(s))&&push!(a,b);i+=1end;a[n])

```

This is an anonymous function that accepts an integer and returns an integer. To call it, give it a name, e.g. `f=n->...`.

Ungolfed:

```
function f(n::Integer)
    # Initialize an array and an index
    a = []
    i = 1

    # Loop while we've generated fewer than n fibohexaprimes
    while endof(a) < n
        # Get the ith Fibonacci number
        b = ([1 1; 1 0]^i)[1]

        # Filter the hexadecimal representation to digits only
        s = filter(isdigit, hex(b))

        # If there are digits to parse, parse them into an
        # integer, check primality, and push the Fibonacci
        # number if prime
        s > "" && isprime(parse(s)) && push!(a, b)

        # Next
        i += 1
    end

    # Return the last generated
    return a[n]
end

```
> 3 votes

# Answer
## C, ~~186~~ 183 bytes

```
#include<stddef.h>
size_t a,b,c,d,m,x;size_t F(n){a=0,b=1;while(n){x=b;b+=a;a=x;c=0,m=1;while(x)d=x%16,m*=d<10?c+=m*d,10:1,x/=16;d=c>1;x=2;while(x<c)if(c%x++==0)d=0;d&&--n;}return a;}

```

The primality test is very inefficient, so the computation will struggle a bit for `n > 16` and become painfully long for `n = 19`. Nevertheless it works and gives the expected results.

The code assumes that `size_t` is a 64bit type, which is true for both 64bit Linux and Windows.

---

Bonus: unfortunately we are required to use 64bit types, which lead to an overhead of 33 bytes. The following version works for `n <= 15` using `int` and is 150 byte long:

```
a,b,c,d,m,x;F(n){a=0,b=1;while(n){x=b;b+=a;a=x;c=0,m=1;while(x)d=x%16,m*=d<10?c+=m*d,10:1,x/=16;d=c>1;x=2;while(x<c)if(c%x++==0)d=0;d&&--n;}return a;}

```

---

Test main:

```
#include <stdio.h>

int main() {
  printf("Input - Output\n");
  for (int i = 1; i < 20; ++i) {
    printf("%2d    - %ld\n", i, F(i));
  }
}

```
> 3 votes

# Answer
# GAP, 204 Bytes

This answer is pretty unremarkable, except that GAP is cool enough to be able to find the next couple fibohexaprimes (and cooler still, it finds these in milliseconds with the given code).

```
gap>f(20);
31940434634990099905
gap> f(21);
12776523572924732586037033894655031898659556447352249
gap> f(22);
971183874599339129547649988289594072811608739584170445
gap> f(23);
1324695516964754142521850507284930515811378128425638237225
gap> f(24);
187341518601536966291015050946540312701895836604078191803255601777

```

Note that f(24) is between 2^216 and 2^217.

Here is the code:

```
f:=function(n)local c,i,x;c:=1;i:=0;while c<=n do x:=HexStringInt(Fibonacci(i));RemoveCharacters(x,"ABCDEFGHIJKLMNOPQRSTUVWXYZ");x:=Int(x);if IsPrime(x) then c:=c+1;fi;i:=i+1;od;Print(Fibonacci(i-1));end;

```

There's probably still some golfing that could be done. I think the implementation is pretty straightforward.

Ungolfed:

```
f:=function(n)
    local counter,i,x;
    counter:=1;i:=0;
    while counter<=n do
        x:=HexStringInt(Fibonacci(i));
        RemoveCharacters(x,"ABCDEFGHIJKLMNOPQRSTUVWXYZ");
        x:=Int(x);
        if IsPrime(x) then
            counter:=counter+1;
        fi;
        i:=i+1;
    od;
    Print(Fibonacci(i-1));
end;

```
> 3 votes

# Answer
## Python 2, 127 bytes

```
N=input();a,b=0,1
while N:a,b=b,a+b;t=int(''.join(c for c in hex(b)if ord(c)<65));N-=(t>1)*all(t%x for x in range(2,t))
print b

```

The algorithm could be a lot more efficient. In particular, the primality check `(t>1)*all(t%x for x in range(2,t))` checks potential factors all the way up to `t-1`, when really it would only have to check up to the floor of the square root. Since `range` stores an entire list in memory in Python 2 , this leads to a `MemoryError` at `N=17` (on my machine using default settings).
> 2 votes

# Answer
# Ruby, 160 bytes

```
->i{t,o,k=[],[],0;f=->n{t[n]||=n<3?1:f[n-2]+f[n-1]};(r=('%x'%f[k]).scan(/\d/).join.to_i;(r>1&&(r==2||(2...r).none?{|j|r%j==0}))&&o<<r;k+=1)while !o[i-1];t[k-1]}

```

**Ungolfed:**

```
-> i {
  t, o, k = [], [], 0
  f = -> n {
    t[n] ||= n < 3 ? 1 : f[n-2] + f[n-1]
  }
  while !o[i-1] do
    r=('%x'%f[k]).scan(/\d/).join.to_i
    o << r if (r > 1 && (r == 2 || (2...r).none?{|j| r%j == 0 }))
    k+=1
  end
  t[k-1]
}

```

**Usage:**

```
# Assign the anonymous function to a variable
m = ->i{t,o,k=[],[],0;f=->n{t[n]||=n<3?1:f[n-2]+f[n-1]};(r=('%x'%f[k]).scan(/\d/).join.to_i;(r>1&&(r==2||(2...r).none?{|j|r%j==0}))&&o<<r;k+=1)while !o[i-1];t[k-1]}

m[2]
=> 3
m[19]
=> 7540113804746346429

```
> 2 votes

# Answer
# R, 164 bytes

```
g=function(n){f=function(m)ifelse(m<3,1,f(m-1)+f(m-2));p=0;while(n){p=p+1;x=gsub("\\D","",sprintf("%x",f(p)));x[x==""]=1;y=1:x;if(sum(!tail(y,1)%%y)==2)n=n-1};f(p)}

```

Indented, with new lines:

```
g=function(n){
    f = function(m)ifelse(m<3,1,f(m-1)+f(m-2)) #Fibonacci function
    p = 0
    while(n){
        p = p+1
        x = gsub("\\D","",sprintf("%x",f(p))) #To Hex, and get rid of non-digits
        x[x==""] = 1 #If x is empty string
        y = 1:x #Converts to integer(!) and save the 1-to-x sequence to a variable
        if(sum(!tail(y,1)%%y)==2) n = n-1 #If prime, decrements counter
        }
    f(p)
    }

```

Examples:

```
> g(1)
[1] 2
> g(5)
[1] 89
> g(10)
[1] 121393
> g(12)
[1] 5702887

```
> 2 votes

# Answer
# Husk, 13 bytes

```
!föṗdf≤9B16İf

```

Try it online!

Using Husk here is just about cheating cause it has an infinite fibonacci sequence builtin.

## Explanation

```
!föṗdf≤9B16İf
           İf infinite list of fibonacci numbers
 fö           filtered on the following four functions:
        B16   base 16 digits of the number
     f≤9      filter out the digits > 9
    d         interpret in base 10
   ṗ          is that prime?
!             get element at input index

```
> 1 votes

# Answer
# Jelly, 14 bytes

```
ÆḞb⁴<Ƈ⁵ḌẒµ#ṪÆḞ

```

Try it online!

Husk's infinite lists just beating me out.

## How it works

```
ÆḞb⁴<Ƈ⁵ḌẒµ#ṪÆḞ - Main link. Takes no arguments
         µ#    - Read an integer n from STDIN and do the following for each integer, i = 0, 1, 2, ... until n return true and return the i's that return true:
ÆḞ             -   The ith Fibonacci number...
        Ẓ      -   ...is prime when...
  b⁴           -   ...converted to base-16,...
    < ⁵        -   ...values less than 10...
     Ƈ         -   ...are removed...
       Ḍ       -   ...then is converted back to base-10
           Ṫ   - Take the last i
            ÆḞ - Return the ith Fibonacci number

```
> 1 votes

# Answer
# Vyxal, 11 bytes

```
ÞF'Hkd↔⌊æ;i

```

Try it Online!

Infinite Fibonacci *and* hexadecimal conversion builtins go brr

```
ÞF          # All fibonacci numbers
  '      ;i # Find the nth where...
   H        # In hexadecimal
    kd↔     # Keeping only digits
       ⌊æ   # Is it prime?

```
> 1 votes

---
Tags: code-golf, math, primes, base-conversion, fibonacci
---