The Nineteenth Byte

New Sandboxed Posts

00:43

0

What order(s) can I fire my tonics in? code-golf game Helsing's Fire is a classic mobile game about light. You fire blasts of holy retribution (from chemicals called tonics), using cover to selectively hit enemies in the right sequence. For this challenge, we're going to ignore the line-of-s...

Jono 2906

05:06

8

Q: How can I salvage jelly that does not set?

This is related but not a duplicate of this question. Apparently, I used fresh kiwi and mango in my jelly, and now it does not set. I know what I did wrong; but what can I do about it? E.g. Can I add gelatin powder to the mixture to improve the chances of it setting? I know that as a last reso...

jelly

The answer is clearly to ask Dennis for help

I mean, he made Jelly

:P

(╭☞´• ͜ʖ •`)╭☞ Humour!

Adám

06:48

@ChristianSievers The markdown syntax for a link is [display text](url)

Pavel

07:35

I wish Dennis was still around

Jono 2906

11:06

@Pavel same

Anush

12:22

hi all

New Main Posts

-1

Q: Average number of strings with Levenshtein distance up to 4

This is a version of this question which should not have such a straightforward solution and so should be more of an interesting coding challenge. It seems, for example, very likely there is no easy to find closed form solution, even though we have only increased the bound by one from the previou...

string math combinatorics fastest-code

Christian Sievers

15:35

@Adám Thanks, don't know why I tried Wiki markup

@Anush oh, hadn't seen your math.SE questions before

Anush

16:01

@ChristianSievers I even put a bounty on it!

Anush

16:29

@ChristianSievers do you think you need more than 10 points to fit it?

as in (4+1)*2

DJMcMayhem

16:43

CMC: DJ's Made Up Binary is a base system that works like this: Start with the counter at 1. For each digit, if it's a 1, double the counter. If it's a 0, subtract 1 from the counter. Given an integer N (which may be negative), output the shortest representation of N in DJMUB

6 -> 1101
10 -> 110101

-10 -> 0011100 or 0001100

Christian Sievers

@Anush Where does (4+1)*2 come from? I think you need one point for each coefficient of each polynomial, of which I suggested three.

Anush

@ChristianSievers I was thinking a degree 4 poly + 2^{-n}* a degree 4 poly . That needs 10 points ?

oh you suggested three polynomials in the sum.

so we need 15 points?

we need more julia and nim coders here.... just saying

Christian Sievers

@Anush And in finding the formula, at first I tried values from n=1 (I knew 0 is a special case), but it didn't work because the formula is only correct for n>=2. Now I wouldn't trust values <distance.

Anush

@ChristianSievers do you have 15 points to try now?

Christian Sievers

16:59

@Anush Maybe the one polynimial keeps being of lower degree, and I see a chance to get the coefficient of the most growing part by other means

Anush

this sounds pretty exciting. Surely at some point a general formula for all k might become apparent. Or is that too optimistic?

Christian Sievers

@Anush No, I'd try my method again, then I'll have arbitrary many... But that will have to wait

Anush

I look forward to whatever you discover!

Christian Sievers

@Anush Yes, I do think that it might be possible to derive enough formula to conjecture a general one

Anush

@ChristianSievers that would be pretty cool!

New Main Posts

17:19

0

Q: What is the correct complexity of All paths from Source to Target DFS solution

The question: "Given a directed, acyclic graph of N nodes. Find all possible paths from node 0 to node N-1, and return them in any order." The DFS solution is described here. https://leetcode.com/articles/all-paths-from-source-to-target/ I feel like the author likely got the time complexity a...

graph-theory algorithm

Adám

17:37

@DJMcMayhem Why is -10 not 000101?

@DJMcMayhem Besides for ^, Dyalog APL, 45 bytes: {0::⍺∇1+⍵⋄c⌷⍨⍺⍳⍨(⊣-∘~⍨⊢+×)/⌽1,c←⍉2⊥⍣¯1⍳2*⍵}∘0

DJMcMayhem

18:12

@Adám Oversight on my part

Pavel

@Adám What's your algorithm?

Adám

@DJMcMayhem The correct answer for 1 is the empty list, right?

@Pavel [[],[[0],[1]],[[0,0],[0,1],[1,0],[1,1]],…]

Pavel

so brute force?

Adám

yup.

Pavel

I always forget that's a valid approach

I was trying to think up a clever formula

Thomas Ward

18:15

@Pavel "Just Brute Force Everything!" :p

Adám

I'm sure there is a clever formula, but I couldn't immediately see it, so BF FTW.

John Dvorak

Here's an observation for ya: x001y == x10y

Adám

@JohnDvorak If I understand your notation right, then that isn't correct.

0{0 0 1}0 1 is -10 but 0{1 0}0 1 is -4

John Dvorak

correction: x01y == x100y

Adám

Or better, x100y → x01y

John Dvorak

18:19

that, yeah

Adám

It is pretty obvious. 2x-2=2(x-1)

@JohnDvorak Also, x110000y → x011y

John Dvorak

that's a corollary of the above

Adám

So I think in general you want at every step to use 0 to move closer to a power-of-2th of the target if possible, else just go with 1

dzaima

@Adám (⊢-*⍨∘-)/

Adám

@dzaima Nice. 43 then.

dzaima

18:27

huh, {≢∪{(⊢-*⍨∘-)/⌽1,⍵}⍉(a⌿2)⊤⍳2*a←⍵}¨⍳20 is ~3x faster in dzaima/APL than Dyalog ((⊣-∘~⍨⊢+×)/ brings the two closer though)

John Dvorak

Ruby, untested x->{(0...x.bit_length).map{|i|%w{1 01}[x[i]]}.join.chop}

Adám

@dzaima What are you computing there? Why the assignment to a?

dzaima

@Adám amount of numbers representable in n bits of DJMUB; a is a remnant of what i previously used it as

Adám

@dzaima And also the inner dfn, I presume.

dzaima

18:43

@Adám aka (in positive numbers) there shouldn't be more than one 0 in a row

Adám

right

Nick Kennedy

18:59

Would it be possible please to have some more feedback on my Sandbox post codegolf.meta.stackexchange.com/a/18414/42248 prior to posting to live? In particular, should I make it code golf or fastest code? The challenge involves counting the number of different buildings that can be made from n identical cubes without overhangs, and I think represents a new integer sequence.

Adám

@NickKennedy If you go for fastest code, do you have a plan for actually timing solutions in all kinds of (platform-specific) languages?

dzaima

@NickKennedy as a nitpick, those example images are huge. maybe put the comparisons side-by-side?

(<img src="..." height="250"> is a way to change the image size in SE, but just merging into one image is probably a better solution)

El'endia Starman

@dzaima I went ahead and edited it since there's a trick: you can append s, m, or l to an Imgur link to get small/medium/large versions of images.

FrownyFrog

@DJMcMayhem J, 29 Try it online!

dzaima

19:15

hm, how hard would it be to make a J→APL transpiler? would be a nice way to learn more about J too (as i can't read ^ at all :|)

Adám

@FrownyFrog Please explain!

@dzaima For most primitives, pretty easy. Some of them more difficult.

FrownyFrog

I uh, turn the negative input to binary, and then I remove a leading 1, and then I turn each 0 into 1, and 1 into 10, and add 00 if it was negative

and it's kinda long

Adám

Huh, how did you come up with that>

FrownyFrog

oh wait, it's the wrong answer for _10

dzaima

@Adám the question's less about the primitives (just using words would suffice), more about the syntax and if there'd be any mismatches just not representable in apl

e.g. gerunds or whatever they're called

Adám

19:18

@dzaima Yeah, gerunds are a problems, and also enclosed simple scalars.

dzaima

@Adám ah, well there's my answer.

Adám

J → SAX should be fairly easy though.

@dzaima Naive transliteration: 0∘> 0 0∘⍮ 1 ⊂⍤⊤⍤+ (⊃↓⊢)⍤⊤⍤-⍤|

FrownyFrog

yeah, so it just works for n > 1

Adám

Wait, that doesn't make sense. Parity is off, no?

FrownyFrog

although at some point I got the right answer for 1

ignore 0∘> 0 0∘⍮

it's that power thing if you're confused about it

Adám

19:26

Ah, right, & is ⍣ sometimes.

FrownyFrog

I still get correct answer for 1, that's a small relief

Adám

@FrownyFrog are these not the pieces? 0&> 0 0&; 1 <@#:@+ ({.}.])@#:@-@|

FrownyFrog

yeah why

Adám

Wouldn't 0 0&; be used dyadically then?

FrownyFrog

0 0&; is one piece

that is the power thing

do 0 0&; 1 or 0 times

(3) 0 0&; 1 -> │0 0│0 0│0 0│1│

Adám

19:32

Yes yes, but somehow I fail to find it in NuVoc

Blind me. It is right there!

FrownyFrog

it's here https://www.jsoftware.com/help/dictionary/d630n.htm
on the right side, it doesn't even have an English gloss

Adám

@FrownyFrog That's why I missed it.

Here too.

FrownyFrog

and at the bottom it literally gives a golfing tip

one shorter than f@]^:[

the idea is to get the difference from the next power, and interleave it with the next power (1 1 1 1 for 16) so that 1s are 0s and 0s are erased
14 is 16 - 2
2 is 1 0, flip it, we get 0 1
1
1
1 0
1 1 nub each row and we're done: 1, 1, 1 0, 1 = 14

I noticed that -14 is 0 0 1 0

so I can add 1 and I get 1 1 10 1 in binary

then it turned out that powers of 2 get output with a useless 1 0 at the start, so I removed leading 1

a brute force approach of a different kind

Nick Kennedy

19:57

@Adám I was planning to get the highest valid n possible with a 10 minute run time on Linux. This would restrict it to languages with a freely available implementation. The expectation would be that the answerer gives an indication of n on their own machine and then I would verify it. Does that seem reasonable? I’m also still happy to stick to Code Golf, and note that they tend to attract more answers.

Adám

@NickKennedy I guess that's reasonable.

AdmBorkBork

20:14

> The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do. -- Ted Nelson

FrownyFrog

20:44

I think it works as is, just remove the @|

27 bytes

dzaima

@FrownyFrog huh, you beat DJ's original length 7 -10 :D

Adám

3 hours ago, by DJMcMayhem

@Adám Oversight on my part

dzaima

oh. ¯\_(ツ)_/¯

@Adám seems like just following that gets you the best answer

FrownyFrog

21:00

just noticed 0 is wrong

FrownyFrog

21:24

Golfed 4 bytes and used them to patch the zero in Try it online!

I remembered that # with complex numbers intersperses zeroes

so no more boxes

Adám

I was just about to ask what j. was doing there

Adám

22:52

CMQ: We're merging our APL JSON server and RESTful server software. What should we call the joint server?

FrownyFrog

23:32

apl gives an empty space for 2⊥⍣¯1 ⊢0?

That's very convenient

28 bytes

Adám

@FrownyFrog Empty list.

Transcript for