The Nineteenth Byte

Quintec

00:25

My cmc got buried

yesterday, by Quintec

CMC: Given an integer n as input, output the kth prime such that the difference between the kth and (k +/- 1)th prime is at least n

ais523

that seems like the sort of challenge Husk would be really good at, but I don't know the language

Pavel

Also Prolog

ais523

it seems about average, it has the right primitives but fitting them into the syntax is hard

and evaluation order would be a problem

let me have a go in Brachylog, I know that pretty well

bleh, this is a pain, you can't easily express "two consecutive primes" or "nth prime"

you'd have to word it as "on some prefix of the sequence of primes…"

and then you're stringing together way too many primitives

H.PWiz

@ais523 Preliminary 10 bytes Husk: !V≥⁰Ẋ-İpİp. Annoying "nth prime" isn't short. I can probably golf it away though

Quintec

My solution in any language is far longer than I expected

H.PWiz

00:52

@Quintec I think that is phrased is a confusing way. I'm assuming you want the first prime such that the difference between it and the next/prev prime is at least n

ais523

@H.PWiz my attempt after learning Husk produced the very similar !Vo≥⁰`-İpİp

which is one byte longer

H.PWiz

@ais523 I think you can use ≠ as absolute difference.

ais523

oh, then it's the same length (and a very similar program)

if only there was some easy way to get V to return the value itself, rather than its index…

H.PWiz

Lol, I found 8 bytes, now you said that.

ais523

01:12

down to 9 using an entirely different approach: ←€mṗNR←⁰0

oh, duh, I can see an obvious byte saving

nope, doesn't work, because R can't figure out its argument order without some character to disambiguate

the two off-by-ones are annoying…

H.PWiz

I recall being of the opinion that the default argument order for R was wrong

ais523

also it doesn't work for very small inputs due to, effectively, treating -1 as prime

H.PWiz

(I'm still trying to understand it)

been a while since i've read husk

ais523

€mṗtNR←⁰0 works for input 2, but not lower inputs

(because it treats 0 as prime rather than -1)

the basic idea is to construct an infinite list of booleans specifying whether the number at that index is prime

then look for a sequence of sufficiently many zeroes (i.e. "composite") in a row

H.PWiz

Oh, cool solution. Mine is much easier

ais523

01:29

here's a 9-byte solution that works for all inputs: →←ġo<⁰-İp

is that at all close to yours?

(form groups of primes that differ by less than the input, then take the last element of the first group)

H.PWiz

Sort, mine is closest to your 10 byte solution.

ais523

this question could probably make main

H.PWiz

(my solution is straight-forward but uses an obscure command)

ais523

01:44

η, perhaps? I can't figure out what it does from the description

meanwhile, →V≥⁰Σm´RẊ-İp is a fun solution but way too long

H.PWiz

Mine has a levenshtein distance of 4 from your (first) 10 byte solution

ais523

S!Vo≥⁰≠İp gets rid of the İp repetition from that answer, but that's 9 bytes

Quintec

@ais523 Are you talking about mine? Can't read husk lol

ais523

yes, your question

finding a good language to solve it is interesting, golfing is also interesting

you made me learn a language to solve it, that's the sign of a good question

Quintec

Hm... okay, will do

Okay, posted

ais523

02:03

here's an 8-byte solution that only works for even numbers as inputs: -⁰LU⁰mṗN

if you give it an odd number as input, it returns 1 less than the second solution for the input below

restricting the challenge to even input would probably increase the range of potential solutions, not sure if that's a good or a bad thing

New Main Posts

0

Q: Prime Difference

Given an integer n, output the smallest prime such that the difference between it and the next prime is at least n. For example, if n=5, you would output 23, since the next prime is 29, and 29-23>=5. More Input/Output Examples 1 -> 2 (2 - 1 >= 1) 2 -> 3 (5 - 3 >= 2) 3 -> 7 (11 - 7 >= 3) 4 -> 7...

Veskah

Slo-bot

ASCII-only

04:50

@ais523 hmm. would using a match/switch not be more complex? especially if the language intends to have a more powerful switch statement (function)?

Pavel

@ais523 And then you get reference.wolfram.com/language/ref/For.html?q=For and it's weird

ASCII-only

05:12

@Pavel weird?

Pavel

Actually Switch is way worse as a function

ASCII-only

@Pavel oi. excuse me

it's only because mathematica doesn't have postfix blocks in the argument list (like... groovy i think it is?)...

in fact, I don't think Mathematica has blocks at all... so there's the real reason they're bad

@Pavel how weird would it be if it looked exactly the same as normal loops (i.e. how you're used to)

Pavel

It kinda does, (statement; statement; statement)

That's not really a block, it's more like Perl's do

But Mathematica lets you keep args unevaluated so you can use that like a block

ASCII-only

but it still doesn't allow for args after the arglist. which is not the most readable

Pavel

@ASCII-only Try it online!

ASCII-only

05:21

@Pavel hmm?

Pavel

@ASCII-only Arglist, then arg

Unless I don't understand what your point is

ASCII-only

not like that

If[foo](body)

Pavel

ah

Something like If[foo][body] would be possible I guess

Which I guess is Curry[If, {1, 2, 3}], or If[cond][true][false]

Jo King

05:47

@Deadcode I've been trying out programming in EMCA regex and been banging my head against the wall, since I'm not that smart.

H.PWiz

Me too. Not gone any further than regexgolf (alf.nu) though

Jo King

I've been trying to do this question, but I'm stuck on how to check if one capture is larger than another >.<

ASCII-only

@JoKing is there even any way to do it other than ((.+).+)?

Jo King

?

@ASCII-only I've made two captures \1 (2^n) and \4 (k) and I can't figure out how to compare the lengths of the two using the original number

ASCII-only

@JoKing is it not possible to assume one is 2^n and the other is k, but capturing them as ((.+).+) wherever you capture the longer one? or does the longer one appear later in the regex/do i have no idea what you're doing

Jo King

05:54

wait, I think I might have it...

nvm

@ASCII-only Here's what I've got so far. ^x(?=(((?=(x+)\3$)\3)*x)(x*)$)x*$, where 2^n and k are captured in the lookahead and the rest of the number is free (at least, I think that's how this is working). I just can't get around the backtracking

ASCII-only

oh btw have you tried using regex101 to see what the engine is doing

Jo King

yeah, but I think I'm still confused

i realise that i'm not capturing 2^n :(

ASCII-only

06:28

@JoKing :| ok so it turns out this is very different from matching a polynomial

Deadcode

@JoKing I'd be happy to help by giving hints of whatever level of vagueness you'd like :)

Just saw your message

H.PWiz

For me it's quite easy to divide by the largest power of two, but capturing that power of two is difficult

Deadcode

Interesting coincidence. I was just preparing to post a regex having to do with powers of 2.

So do you know how to match powers of 2?

H.PWiz

Yes.

I divide by the largest power of two, and check if one is left (It's the same length as the ones on regexgolf)

Deadcode

How are you dividing?

Do you mean you're dividing by 2?

/me analyzes the regex Jo King pasted above

H.PWiz

06:33

I find this confusing to talk about as we probably think about what the regexes (regecies?) do in different ways

Let me think for a bit

Deadcode

Okay, I see the power of 2 test in the center of the loop

Nicely done figuring that part out.

Most people (including me) first matched powers of 2 in a different wa

Jo King

I figured out how to check if a capture is longer than another btw. Negative lookaheads are the way to go

Deadcode

*way. One that can't be generalized to all other powers.

Yes, that's a length-efficient way.

Jo King

Now i just have to get 2^n...

Deadcode

Okay, you are subtracting the largest power of 2

But you want to divide by a power of two, not subtract it.

Also, why are you capturing it in \1?

Jo King

06:37

i don't know

crap

Deadcode

Also, I think this is a bit too ambitious to start with

Have you done perfect squares yet?

Jo King

never give in

No, i just started clicking random ppcg challenges until I found one I thought I could do

ASCII-only

perfect squares is probably one of the easiest ones (at least, easy enough that i can understand it >_>)

Deadcode

How would you go about it?

I'm pretty sure the "Is it a Proth number?" would require using the generalized-division algorithm for dividing by the power of 2, and that takes quite a deal of thought to come up with

I can't think of any other way to do it offhand

BTW have I done well with the spoiler warnings?

Jo King

darn

Deadcode

06:42

If you want to jump ahead like that, I'd suggest starting with figuring out a way to match correct multiplication statements

But it'd be better to start with perfect squares

H.PWiz

It appears that Retina's ecmascript is faulty. ^x(x(xx\2))*$ matches perfect squares

Deadcode

OH hey

I just realized, you don't need to actually know the value of k, right?

@JoKing Maybe you can do this one after all

(Proth numbers)

Jo King

don't say how, let's see if I can figure it out

Deadcode

Oh wow, good find @H.PWiz - that is indeed a bug

tested it in my engine and that regex indeed doesn't work (as I could tell at a glance it shouldn't)

Use my regex engine

H.PWiz

I can do it without 2^n > k in 23 bytes, but need to think more about the problem to do it better

Deadcode

06:48

github.com/Davidebyzero/RegexMathEngine

H.PWiz

Should I just run make?

Deadcode

@H.PWiz How did you even find that bug?

Yes

And then use the engine's numerical mode -nx

H.PWiz

tools.h:43:41: error: missing binary operator before token "("
#elif defined(__GNUC__) || __has_builtin(__builtin_unreachable)

First error

Deadcode

./regex -nx 'pattern to test' -t 0..100

Hmm, it worked in two gcc's I tried

H.PWiz

g++ (GCC) 8.2.1 20181127

Deadcode

06:50

Oh, some new compile issues from my latest changes. Lemme fix those. (I mainly use MSVC)

blargh

g++ -Wno-invalid-offsetof -Ofast -flto -fwhole-program -c matcher.cpp -o matcher.o
matcher.cpp:1340:83: error: specialization of `void RegexMatcher<<anonymous> >::fprintCapture(FILE*, Uint64, const char*) [with bool USE_STRINGS = false; FILE = __sFILE64; Uint64 = long long unsigned int]' after instantiation
void RegexMatcher<false>::fprintCapture(FILE *f, Uint64 length, const char *offset)

H.PWiz

With clang, I get a bunch of errors like this:
./matcher.h:130:64: error: null non-type template argument must be cast to template parameter type 'const char *'
friend class Backtrack_Verb<USE_STRINGS, RegexVerb_Skip , NULL >;
^
static_cast<const char *>( )
/usr/lib/clang/7.0.0/include/stddef.h:100:18: note: expanded from macro 'NULL'
# define NULL __null

Deadcode

Oh, I get it

Okay almost fixed

Done

Pushed

@H.PWiz

H.PWiz

g++ errors, clang almost works, but I get horrible linker errors

Deadcode

Show me

H.PWiz

https://tio.run/##3V1tb@M2Ev6eX6FPXSfXJKbeZRQFuldfEVx2ESRF71BjofJllKiRJVeWvXb//FZSnMRJZFl2OHoxFvDaIjl8ZjiceUiJyjSg0zuYfvt2PpvG58wPzwMxUM6T8eQ8SKLTIJiPTy3TFqp@Fg0UP1S8WcgTPwqVP67hFhafaMLvIP4hiWfw42CQ/@zlJb/E0Wzy3ffKLJz6tyGItHGy8VcQhbf5R9G17wovHn8YHAXiNIHxJIXWO0tgkZy5v38m6jqwi0tGhkMj/zW8Jv1naH/@ubxe3mjuaI82X/7VX@j68SDFJcDzM2AxeBBDyEFJIuWPaAIxTaJYERBAAqMvvXnki5PjD0cv7Nwofq8K/hC@puBfmL9NSmgeVB@F9o2B4TnddiKzDwfgRaba9WHQyCEMg651fBiM/iEMg6l2fBgs/RCGwek4wTDpQQQlTjs@DOIQZoNF7W4Pg8XUAxgGjxwC3yN9OITFDyGqhExdfa1/ReMpxIMBD6Ip/BQkEIc08efwsN6/WY5ZFJycpKv1aSIGg79mMIMf1otWBQL@Ki6gQRDxDPGLwh@V9N/m1T5Zg0bM19C…

Deadcode

07:01

Yikes

Does that g++ work on other projects?

H.PWiz

I actually don't know

Deadcode

Try using gcc instead of g++ (edit the makefile to change this)

H.PWiz

g++ does work elsewhere

Deadcode

Oh, that doesn't work for me. Linker error if I use gcc instead of g++

H.PWiz

Same error with gcc as g++

Deadcode

07:05

$(CPP) $(CFLAGS) -o $@ $(OBJ) -llibstdc++

with this line in the makefile, it works with gcc

CPP = gcc

i.e. add the "-llibstdc++"

H.PWiz

Never mind. Got it to build. I was using clang instead of clang++ (which is the only thing that has worked)

Deadcode

Awesome!

What are the changes to the makefile to compile it with clang? (I don't have it installed, but I could add those in, commented out)

H.PWiz

CPP = clang++. Lots of warnings though

Deadcode

$ ./regex -x pbr -nx '^x(x(xx\2))*$' -t 0..200
1 -> 1
4 -> 4
9 -> 9
16 -> 16
25 -> 25
36 -> 36
49 -> 49
64 -> 64
81 -> 81
100 -> 100
121 -> 121
144 -> 144
169 -> 169
196 -> 196

damn, .NET's ECMAScript mode doesn't disable forward backreferences.

Enabling them in my engine makes that regex match perfect squares

H.PWiz

Yes, that was what I thought

Adám

07:09

face, meet desk is like a computing meme, right?

Jo King

wait, do I just need to find if k>N/2?

Deadcode

@JoKing You were actually on the right track with subtracting a power of two... do you want a larger hint than that?

Well, I'd better solve it myself to make sure I'm not giving you false hope

Jo King

hmm, let me lose hope first

*k>sqrt N

Deadcode

Oh. 2^n > k

Yeah so I guess you need to know the value of k...

H.PWiz

Without 2^n > k, it's just the odd numbers > 1. (took me far too long to see that)

Deadcode

07:28

Yeah, I mean I know that, but explicitly writing the code to do it would take more than 23 bytes, wouldn't it? Did you actually do it in 23?

Jo King

^(..)+.$

Deadcode

Also, isn't it all of the numbers? 1 is a power of 2.

Yeah, that's not 23 bytes. 23 implies that you actually did something

the regex would actually be .

Jo King

Doesn't ^x(?=((?=(x+)\2$)\2)*) give me k?

H.PWiz

Well, I had ^x((x+)(?=\2$))+x(xx)*$ as my "23"

Deadcode

Okay, neither of those are even close

You're both just repeatedly subtracting an arbitrary power of 2

not enforcing that it's the same one each time

H.PWiz

07:32

Yeah, mine basically matches everything except for k, then makes sure k is odd.

Deadcode

I mean, a correct regex implementing this would match everything

but still :)

you could return the power of 2 as a match

the largest power of 2 that divides into N-1 an odd number of times

I suggest doing that!

It's actually rather difficult without molecular lookahead. I'm trying to think of a way

Well, you could do it with molecular lookahead using my engine.

it would be good practice at least.

$ ./regex -xml -nx --fs+ -f 'regex for matching Proth numbers.txt' -t 0..100
2 -> 1
3 -> 2
4 -> 1
5 -> 4
6 -> 1
7 -> 2
8 -> 1
9 -> 8
10 -> 1
11 -> 2
12 -> 1
13 -> 4
14 -> 1
15 -> 2
16 -> 1
17 -> 16
18 -> 1
19 -> 2
20 -> 1
21 -> 4
22 -> 1
23 -> 2
24 -> 1
25 -> 8
26 -> 1
27 -> 2
28 -> 1
29 -> 4
30 -> 1
31 -> 2
32 -> 1
33 -> 32
34 -> 1
35 -> 2
36 -> 1
37 -> 4

(the filename is not the real thing, it's just the thing I just described)

returns the largest power of 2 that divides into N-1 an odd number of times

@H.PWiz @JoKing What do you think of tackling this sub-problem to begin with?

That regex is 43 bytes

H.PWiz

My difficulty is that I can't match a power of two without $.

Deadcode

Do it inside a molecular lookahead.

Jo King

I think I've got 2^n now

Deadcode

Then do things with the power of two once you're outside the molecular lookahead

It wouldn't work in a normal atomic lookahead because it'd only match one power of 2, and not try others

@JoKing What do you have?

Jo King

07:46

^x(?=(x+)(\1\1)+$) ?

Deadcode

No

Now you're just dividing by some arbitrary odd number

Jo King

right, I see

Deadcode

But that method could be used to do it without molecular lookahead

divide first, then check to see if you really had a power of 2

but don't do it in a lookahead, because if you do, it'll only try 1 value

(I mean, if it's an atomic lookahead)

Hmmm, without a molecular lookahead, k=1 must be treated as a special case

$ ./regex -nx --fs+ -f 'regex for matching Proth numbers.txt' -t 0..100
2 -> 1
3 -> 2
4 -> 1
5 -> 4
6 -> 1
7 -> 2
8 -> 1
9 -> 8
10 -> 1
11 -> 2
12 -> 1
13 -> 4
14 -> 1
15 -> 2
16 -> 1
17 -> 16
18 -> 1
19 -> 2
20 -> 1
21 -> 4
22 -> 1
23 -> 2
24 -> 1
25 -> 8
26 -> 1
27 -> 2
28 -> 1
29 -> 4
30 -> 1
31 -> 2
32 -> 1
33 -> 32
34 -> 1
35 -> 2
36 -> 1
37 -> 4

This regex is 70 bytes but doesn't use molecular lookahead

H.PWiz

^(?*x*(((x+)(?=\3$))*x$))\1(?=(\1\1)*x$)

Deadcode

Good job! :D

And in fewer bytes than I did it

^(?=x(?*.*?(((x+)(?=\3$))*x$))\1(\1\1)*$)\1 this is what I had

Now can you do it without -xml?

H.PWiz

08:00

Do I need a different way to match powers of 2?

Deadcode

Nope

Also good job finding the optimal way to match powers of 2

Okay, you already had that back at 'Well, I had ^x((x+)(?=\2$))+x(xx)*$ as my "23"'

Jo King

what's ?* ?

Deadcode

Non-atomic lookahead.

Molecular lookahead.

The engine can backtrack into it, unlike (?=)

H.PWiz

Is it something other engines have?

Deadcode

and thus try a range of values, if you capture something inside (?*)

Nope

Jo King

08:03

oh, that would have been useful

Deadcode

It can be emulated using .NET's variable-length lookbehind

Adám

Would this be suitable or is it too hard to spec right? Only for languages that allow the user to assign values to names. Given a string, determine if it is a valid name. If your language requires a prefix which depends on data type (e.g. some BASICs), you may choose to only support a single data type. If your language supports namespace syntax (e.g. C#), you must not regard a compound name (e.g. MyClass.Foo) as valid. Are there more special rules needed?

H.PWiz

I'll come back to this some other time. Thanks for the support @Deadcode

Deadcode

@H.PWiz You're very welcome. I'm impressed at your work.

Maybe you'll eventually be able to compete in golf against me :D

Jo King

I'm going to go play with squares

Deadcode

08:10

Cool :)

Jo King

09:27

@Deadcode is ^x(x(xx\2))*$ meant to be valid EMCAscript?

H.PWiz

I wrote it, and it wasn't my intention for it to be valid

Jo King

@H.PWiz oh, that's what i came up with too! I couldn't figure out another way to keep a counter for odd numbers

Deadcode

09:43

It's a hybrid between ECMAScript and nested-backreferences

it wouldn't work in either engine's default mode

it uses ECMAScript unset-capture behavior, of matching zero-width

whereas PCRE and .NET match nothing with an unset capture

$ ./regex -xpbr --npcg+ -nx '^x(x(xx\2))*$' -t 0..200
1 -> 1
4 -> 4
9 -> 9
16 -> 16
25 -> 25
36 -> 36
49 -> 49
64 -> 64
81 -> 81
100 -> 100
121 -> 121
144 -> 144
169 -> 169
196 -> 196

$ ./regex -xpbr --npcg- -nx '^x(x(xx\2))*$' -t 0..200
1 -> 1

In my engine's ECMAScript mode, it just matches 3n+1:
$ ./regex -nx '^x(x(xx\2))*$' -t 0..64
1 -> 1
4 -> 4
7 -> 7
10 -> 10
13 -> 13
16 -> 16
19 -> 19
22 -> 22
25 -> 25
28 -> 28
31 -> 31
34 -> 34
37 -> 37
40 -> 40
43 -> 43
46 -> 46
49 -> 49
52 -> 52
55 -> 55
58 -> 58
61 -> 61
64 -> 64

.NET does appear to disable forward backreferences in it ECMA mode, but not nested backreferences, which that squares regex uses.

Using the 2n+1 difference thing to detect perfect squares was the first thing I tried when initially working on the problem. I finally came up with a regex that seemed to work, even for numbers as large as I could test with a C program compiled natively, but it probably would be harder than Fermat's Last Theorem to prove that algorithm correct or incorrect. I had a feeling that there could be counterexample numbers that'd be very huge.

@JoKing Did you get my engine working?

I'm guessing maybe you're still using Retina, if you made a regex that uses a nested backreference?

Well, g'night :)

feersum

10:21

Does anyone understand the point of haveibeenpwned.com? It just says "you have been in N breaches" which could be a random number for all I care.

primo

10:35

if it's of any iterest, a regex for matching lengths of a power of two: ^(^x|\1\1)*x$

and squares: ^(^x|\1xx)*$

Deadcode

11:02

Hi @primo! :D

Your regex is beautiful, but we were discussing one that uses both nested backreferences and zero-width-matching unset captures. Can you optimize that version any better? :)

$ ./regex -xpbr --npcg+ -nx '^(^x|\1xx)*$' -t 0..200
0 -> 0
1 -> 1
2 -> 2
4 -> 4
6 -> 6
9 -> 9
12 -> 12
16 -> 16
20 -> 20
25 -> 25
30 -> 30
36 -> 36
42 -> 42
49 -> 49
56 -> 56
64 -> 64
72 -> 72
81 -> 81
90 -> 90
100 -> 100
110 -> 110
121 -> 121
132 -> 132
144 -> 144
156 -> 156
169 -> 169
182 -> 182
196 -> 196

As you can see it does not work in this mode :)

primo

tio.run/##K0gtyjH9r16hXqESr1BX918/TiOuoibGsKJCU0tF/…

in which mode? :p

Deadcode

I'd love to have my regex engine appear on tio.run

But maybe I want to fix a couple more bugs first

github.com/Davidebyzero/RegexMathEngine

H.PWiz

That would be good, quite easy to do as well. Just ask in the chat room on this site when you're ready

Deadcode

just run it from the command line :)

Cool, ^(^x|\1\1)*x$ works for powers of two with both NPCG behaviors. And in .NET's ECMA mode.

Note that ^(^x|\1xx)*+$ does work in -xpbr,pq mode. So it's backtracking that's killing it. The engine backtracks to the first iteration, and can take the \1xx path instead of ^x.

primo

hmm

Adám

11:12

Any .NET wizards here?

primo

i'm no Jon Skeet, but it is my primary job

Deadcode

@primo tio.run/##HckxCsMwDEDRXbcIyEWSUandplMh9B7GOJAMXTqUDhp6Lh/… actually

(Note the e in the %e(`)

Adám

@primo Can you think of a .NET class that can be instantiated with no arguments?

primo

there's got to be plenty

Adám

@primo I just need one for an example. From the core library would be best.

primo

11:19

Exception

Adám

@primo Hm, unfortunately, that seems to throw an exception when trying to get its value :-(

primo

generic lists of any kind

List<string>

most controls in System.Windows.Forms

StringBuilder

Adám

@primo Great, thanks. System.Collections.ArrayList seems to work.

primo

@Deadcode i think i've spent too many years using pcre, i honestly don't understand how this regex engine works

although, i'd probably tack in a (!^)

Deadcode

@primo Right, but that makes it longer, doesn't it? ^x(x(xx\2))*$ is 13 bytes but ^(^x|(?!^)\1xx)*$ is 17 bytes

H.PWiz

11:32

@Deadcode I got a segfault doing ^(?=(xx+?)\1+$)(?=(xx+)(\2+)$)\3\1$ for 0..10 in your engine

primo

yeah, it does

Deadcode

And even ^(^x|\B\1xx)*$ is still 14 bytes

@H.PWiz Thanks! I didn't know any segfaults were possible without enabling the PCRE extensions

primo

yeah, that's a better option ;)

Deadcode

echo 'aaaab' | ./regex --pcre -o '^(?>ab|aa|a){3}+'

this segfaults too

echo 'aaaab' | ./regex --pcre -o '^(?>ab|aa|a){3}'

possessive quantifier not needed to get the segfault

@H.PWiz Wow, very nice job... missing some matches but you got the idea

Also that does not segfault for me

What's your exact command line?

Might be an issue only happening when compiled with the compiler you used

H.PWiz

% ./regex -nx '^(?=(xx+?)\1+$)(?=(xx+)(\2+)$)\3\1$' -t 0..10
4 -> 4
zsh: segmentation fault (core dumped) ./regex -nx '^(?=(xx+?)\1+$)(?=(xx+)(\2+)$)\3\1$' -t 0..10

@Deadcode I think it matches prime squares at the moment, only a little more thinking left to do

Deadcode

11:39

$ ./regex -nx '^(?=(xx+?)\1+$)(?=(xx+)(\2+)$)\3\1$' -t 0..16384
4 -> 4
9 -> 9
25 -> 25
49 -> 49
121 -> 121
169 -> 169
289 -> 289
361 -> 361
529 -> 529
841 -> 841
961 -> 961
1369 -> 1369
1681 -> 1681
1849 -> 1849
2209 -> 2209
2809 -> 2809
3481 -> 3481
3721 -> 3721
4489 -> 4489
5041 -> 5041
5329 -> 5329
6241 -> 6241
6889 -> 6889
7921 -> 7921
9409 -> 9409
10201 -> 10201
10609 -> 10609
11449 -> 11449
11881 -> 11881
12769 -> 12769
16129 -> 16129

@H.PWiz What's the output of ./regex -nx '^(?=(xx+?)\1+$)(?=(xx+)(\2+)$)\3\1$' -t 5..10 --trace

Just the end of the output

or the whole thing, if you want to paste it somewhere

H.PWiz

\1$
Step 24: {3|3} \1=2, \2=3, \3=3
[3]

$
Step 25: {5|1} \1=2, \2=3, \3=3
[3]: non-matchzsh: segmentation fault

Deadcode

okay, segfault on -t 6

does this segfault? ./regex -nx '^(?=(xx+?)\1+$)(?=(xx+)(\2+)$)\3\1$' -t 6

H.PWiz

Yes

Deadcode

```

\1$
Step 24: {3|3} \1=2, \2=3, \3=3
Backtrack_AtomicCapture: numCaptured=2
Backtrack_AtomicCapture: numCaptured=1
[3]

$
Step 25: {5|1} \1=2, \2=3, \3=3
Backtrack_AtomicCapture: numCaptured=2
Backtrack_AtomicCapture: numCaptured=1
[3]: non-match
No match found

that's how it's supposed to go (with --trace --trace)

So it crashed on the last step

H.PWiz

With --trace --trace it doesn't even get past step 23

Deadcode

11:43

What happens if you do ./regex -nx '^(?=(xx+?)\1+$)(?=(xx+)(\2+)$)\3\1$|z' -t 6 --trace --trace

Oh, that's interesting. So the backtrack stack printout itself causes a crash earlier.

Could you please show me the last few steps of --trace --trace?

H.PWiz

tio.run/##3Zhfb5swFMXf@RRXWqaCEhi2gbWRULVV0162p@1tdBMiXhs1/…

Deadcode

Oh, and I just noticed a bug. numSteps resets to 0 after switching to a root-group alternative

@H.PWiz Thanks. And that is compiled with clang?

H.PWiz

Yes

Deadcode

What version?

H.PWiz

clang version 7.0.0 (tags/RELEASE_700/final)

Deadcode

11:50

Thanks. I'll see if I can reproduce it

Oh, that numSteps thing isn't a bug.

That's a new match attempt from a different position, because I didn't anchor the z

New Main Posts

0

Q: Exploding Numbers

Sandbox Post Lets define a matrix of 9s as: $$ N = \begin{bmatrix} 9&9&9\\9&9&9\\9&9&9 \end{bmatrix} $$ Lets define an exploding number as a number at position \$(x,y)\$ that can be decomposed into equal parts greater than 0 between all its adjacent neighbors (including itself). From the previ...

code-golf matrix

H.PWiz

@Deadcode I have 49 bytes for matching square numbers (Doesn't match 0)

And segfaults locally

Deadcode

12:06

Nice! What's the shortest version you can come up with that does match zero?

@H.PWiz And did you come up with that algorithm from your own head? You didn't see that technique being used in my fourth-power, smooth numbers, or Cullen numbers regexes on PPCG?

H.PWiz

Right now, 52

@Deadcode I read some of your description on the fourth power post earlier this week. Didn't really examine the regex though

Deadcode

Okay, good memory then :)

And you're just 2 bytes shy of the best that algorithm has been golfed to

H.PWiz

It was the approach, "repeatedly divide n by its smallest square divisor", that I got

Deadcode

yep, the implicit division

New Meta Posts

12:45

0

Q: Community Promotion Ads — 2019

2019 is here! And with the new year, as usual, comes a new iteration of Community Promotion Ads! Let’s refresh these for the coming year :) What are Community Promotion Ads? Community Promotion Ads are community-vetted advertisements that will show up on the main site, in the right sidebar. The...

discussion community-ads

Luis felipe De jesus Munoz

12:57

Guys, question. Can I delete my post from main to make it better? I think it is not ready yet

Arnauld

@LuisfelipeDejesusMunoz I was just about to suggest exactly that. :)

Luis felipe De jesus Munoz

@Arnauld Cool and sorry, I just got lost on my own challenge

Erik the Outgolfer

@NewMetaPosts hm, better let @Dennis post the TIO ad, he can update it when another hundred of languages get added :P

@LuisfelipeDejesusMunoz yeah, you can delete your own challenge like that (also, what are natural numbers?)

Luis felipe De jesus Munoz

@EriktheOutgolfer Non-negative integers (including 0)

Dennis

@EriktheOutgolfer Done.

> JNat♦ is a new contributor. Be nice, and check out our Code of Conduct.

Erik the Outgolfer

13:08

yeah, a bit of a sin to say that for our beloved JNat...

@LuisfelipeDejesusMunoz better include that in the challenge (otherwise I can't say for sure if you mean N or N*)

Luis felipe De jesus Munoz

@EriktheOutgolfer sure thing. Thanks

J. Sallé

I've been taught at school that the term "natural numbers" always means N, not N*. TIL not everyone's been taught that :p

Erik the Outgolfer

for example, Luis wanted N* here

J. Sallé

Exactly

Deadcode

13:36

@H.PWiz It might take a while to fix it under clang, but I pushed a commit that allowed me to compile it with GCC 8.2.1, and it does not segfault. Does it work for you now?

and -lstdc++ added to make the linking line $(CPP) $(CFLAGS) -o $@ $(OBJ) -lstdc++

H.PWiz

Yeah, works great now. Also, I figured out how to account for 0 with only one more byte.

Deadcode

Cool.

So 51 bytes now?

Or 50?

Yep, 50 is the best possible AFAIK. Congrats. :)

For that algorithm, I mean.

A completely different algorithm can be 49 bytes.

Well, for squares it's much smaller.

49 is for generalized Nth power.

So the next task is to figure out generalized multiplication.

Match correct statements of multiplication.

A*B=C in unary

H.PWiz

(I'll probably refrain doing more of this today)

Jo King

heyo, I got 60 bytes for square matching yay

Deadcode

14:01

Awesome, congrats @JoKing.

Did you come up with it on your own, or remember reading about it on my fourth-power regex post?

(the general algorithm)

Jo King

14:24

@Deadcode i read your post earlier today, but I did my best to figure it out on my own

took forever to realise I should match the smallest factor...

Conor O'Brien

15:33

TIL ruby's okay with this

moonheart08

15:55

Well, i really like my insane concept now, but implementing it is going to be hell

(For reference, here's my insane concept: chat.stackexchange.com/transcript/message/48631828#48631828)

a weird hybrid of APL and dataflow based languages

numbers 99 through 0 without a builtin might look like `99R-/1+[>0]|`
I'll explain it on request (It's a wall of text(tm))

quartata

@ConorO'Brien is it like a block

Quintec

17:13

@ConorO'Brien Without knowing ruby, what is wrong with that

New Main Posts

17:30

1

Q: Pointer jumping

Suppose we have an array \$\texttt{ps}\$ of length \$n\$ with pointers pointing to some location in the array: The process of "pointer jumping" will set every pointer to the location the pointer it points to points to. For the purpose of this challenge a pointer is the (zero-based) index of an e...

code-golf array-manipulation graph-theory

New Sandboxed Posts

18:30

0

A: Sandbox for Proposed Challenges

Partition and Restructure code-golf math grid geometry Given two contiguous shapes of the same area, determine the optimal way to divide the first shape into a minimum number of contiguous segments such that they can be rearranged to form the second shape. In other words, find the minimum number...

HyperNeutrino

I wonder if my sandbox challenge is too hard... It seems very difficult and I don't have any idea what solution I'd use other than the trivial bitmask O(2^N) one.

wait

that's like O((2^N)!), nvm

Transcript for