The Nineteenth Byte

ETHproductions

19:00

Oh, OK

How long did it take to complete 5?

fəˈnɛtɪk

about 15 seconds

ETHproductions

that's not too bad

Poke

@ETHproductions hmm, is that the feature that chrome has had since it was created?

ETHproductions

but 6 must be incredibly more complex

@Poke probably :P

fəˈnɛtɪk

this code is running in O(n^n) time and space complexity

Poke

19:01

;) welcome back to the present, mozilla!

fəˈnɛtɪk

It is technically (n+1)^3n

Riker

@AdmBorkBork I used to, mainly for his tf2 stuff, still do sometimes

ETHproductions

>> (6+1)**(3*6)
< 1628413597910449

OK then

That's a little more substantial than 46656

Lembik

hi @ETHproductions

@fəˈnɛtɪk that's bad :)

fəˈnɛtɪk

Well the tab finally crashed.

ETHproductions

19:05

Not sure if that's a good thing or a bad thing

Lembik

surely someone has to submit a non javascript answer!

not that I don't know javascript of course :)

ETHproductions

Let's see... the optimal algorithm would generate all hamming distance arrays, then take all combinations and find the largest one that has no close pairs

So I'm trying to figure out the time complexity of that...

Lembik

it's bad.. but why not be greedy instead?

who needs optimal :)

fəˈnɛtɪk

@ETHproductions O(n^(n^2)) I think

ETHproductions

Is there a... uh... polynomial formula for the number of possible combinations of any size of n items?

Oh, it's just 2^n

:P

Jan Dvorak

19:12

almost

fəˈnɛtɪk

From my conversion to a graph I got a theoretical fastest program of about O(1.3^(n^n)) as I had converted it into the NP-complete problem of Maximal independent subset. For solving perfectly.

@ETHproductions The number of possible hamming arrays is exponential to begin with...

ETHproductions

I know

fəˈnɛtɪk

So brute force looks like it will end up being something like O(n^n^n).

ETHproductions

Which is just insane

The greedy algorithm should give the best answer IMHO, but I don't know enough higher mathematics to know if this is accurate or even feasible

Wheat Wizard

Is there an existing Lenguage compiler anywhere?

fəˈnɛtɪk

19:18

By greedy algorithm do you mean remove the points which have the most close points?

ETHproductions

Yes, that's how I got 2,5,21

fəˈnɛtɪk

Because that fails at n=4, giving 67

ETHproductions

Wait... really?

Huh

Helka Homba

CMC: Name an RPG video game (one where you generally play as one main/hero character) that has no "infinite" drops anywhere in the game (i.e. the void in Minecraft, huge chasm in the landscape of Zelda, etc.)

fəˈnɛtɪk

It was the original algorithm I was using. I made some changes to restore points if they fell below the maximum

Jan Dvorak

19:19

Factori... oh. RPG.

AdmBorkBork

@HelkaHomba Original Legend of Zelda for the NES.

Jan Dvorak

@HelkaHomba Frog fable

Kritixi Lithos

@HelkaHomba NetHack?

Helka Homba

Uhh, cannot confirm any of these since haven't played

ETHproductions

@fəˈnɛtɪk The maximum meaning... the number of points on the new [item with the most points]?

Basic Sunset

19:21

Pretty much any turn-based battle RPG?

Jan Dvorak

Does Spelunky count as an RPG?

Basic Sunset

And Skyrim (as well other ES presumabely) certainly doesn't have any of those

AdmBorkBork

There aren't any drops in the original Zelda, it's entirely flat two-dimensional top-down.

ETHproductions

s/points/connections/g

fəˈnɛtɪk

At each step it finds the point with the most connections. It then removes that point and adds back any points which had less remaining connections

ETHproductions

19:22

Interesting

New Main Posts

4

Q: How great is your land?

In this challenge, you'll calculate how great your land is. Write a program or function that calculates the size of your land, give a wall you have built. You're given a non-empty input string containing a set of 4 distinct characters of your choice that represent the four directions "up", "do...

Helka Homba

@BasicSunset Paper mario had plenty of drops

Basic Sunset

@HelkaHomba Oh that's true. But most don't.

Kritixi Lithos

I thought Paper Mario wasn't turn-based

Jan Dvorak

It has turn-based combat

Helka Homba

19:24

@JanDvorak Sure

Jan Dvorak

Great. Because spel... oh. Area 3. Nvm.

Wheat Wizard

Is there a binaryfuck compiler?

fəˈnɛtɪk

I turned it into a graph so it is removing the vertex with the most adjacent vertices and replacing removed vertices which had less than the one which was just removed.

ETHproductions

Honestly I think I might just attempt to figure out the formula for the number of Hamming distance arrays of length n

Lembik had a program that calculated this for any n, lemme see if I can find it

The first few are 1, 2, 9, 48, 297, 2040, 15425, 125232

fəˈnɛtɪk

1070553

ETHproductions

19:31

Alright, that should be enough to go on, for now

Lembik

hmm.. the numbers 2,5,21,81,372 start at a different n?

it's 372 out of 2040?

ok that makes sense

@ETHproductions so did you try a less expensive greedy approach?

exhaustive enumeration can't be the way forward

it's too exhausting :)

ETHproductions

@Lembik hmm... "less expensive"? If you're talking about complexity, I don't think you can get less expensive

I think fəˈnɛtɪk's approach might be optimal, but of course I was wrong about my own being optimal

fəˈnɛtɪk

I know that my approach is going to start failing for higher values.

Lembik

@ETHproductions Why not be greedy? Here is a method. Choose a random P and T and see if the resulting hamming distance sequence is far from all the ones you have seen. If it is, add it to the set

ETHproductions

@fəˈnɛtɪk Oh OK, why's that?

Lembik

19:36

@ETHproductions that's much cheaper

ETHproductions

(ignoring e.g. memory issues, of course)

fəˈnɛtɪk

Otherwise I have solved an NP-complete problem in polynomial time...

Jan Dvorak

You haven't

ETHproductions

@Lembik Ohhh, for generating the Hamming distance arrays.... my bad

Lembik

4graphix

ETHproductions

19:37

Wait, now I've confused myself

@fəˈnɛtɪk I'm assuming NP-complete means something along the lines of "can't be solved optimally without brute-force"

fəˈnɛtɪk

@ETHproductions NP-complete as in this problem is known to belong to Nondeterministic polynomial time. If I somehow managed to solve it in polynomial time (I haven't), I have proven that P=NP

AdmBorkBork

Congrats! Can I have some of your prize money?

New Main Posts

-2

Q: Find a Four-Leaf Clover!

Since today is St. Patrick's day, you will try to find a four leaf clover. And because you don't want to sit in the grass and sort by hand, you will write some code to do it for you. Your challenge: write a program that output the coordinate location of the following character: 🍀, in a field of...

code-golf ascii-art

ETHproductions

So let's see... NP = solvable in polynomial time, NP-hard = at least as hard as the hardest NP problem, whether NP or not, and NP-complete is both? So... an NP-complete problem is in the set of the hardest polynomial-time problems. Am I understanding correctly?

fəˈnɛtɪk

Also, I made a mistake. It's a NP-hard problem and not a NP-complete problem.

Lembik

19:50

@ETHproductions It means something similar.

Jan Dvorak

@ETHproductions np = solution can be verified in polynomial time

Lembik

but we don't need provably optimal solutions and the problem isn't np-hard anyway :)

it's just hard

ETHproductions

@JanDvorak oh, ok

fəˈnɛtɪk

The provably optimal solution for what I turned it into is NP-hard. But you can get pretty close with polynomial time

ETHproductions

Ah, P = solvable in polynomial time

Jan Dvorak

19:52

So, you discovered a PTAS for the maximum independent set problem?

Because Wikipedia says you didn't

Lembik

@JanDvorak I don't anyone claimed that

Jan Dvorak

I'm just asking if they did

Lembik

do people just not like my greedy approach?

fəˈnɛtɪk

What I meant is that for the values we are working with it is pretty close

AdmBorkBork

> It might have made sense when people used shell accounts on vaxes with globally readable password files attached to thick ethernets that ran through unlocked janitors closets in student housing, but it makes little sense now.

Lembik

19:56

or is it not clear what I am actually suggestnig?

Jan Dvorak

I like fast approximate solutions

Lembik

@JanDvorak ok so that's what I am suggesting

fast, greedy and randomized

it just needs a little coding, but not much

Jan Dvorak

for example, "yes" approximates the solution to the Collatz conjecture to a very high degree.

6

Lembik

of course my method may be nowhere near optimal but this needs to be tested

I am just hoping someone will code it up and see!

fəˈnɛtɪk

@Lembik My initial solution was a non-random implementation of the greedy algorithm for the Maximum Independent Set problem.

Lembik

19:59

@fəˈnɛtɪk ok.. the point about the random one is that you can just run it for as long as you can bear

and the answer will get slowly better

ETHproductions

@JanDvorak I have most of a proof that infinite divergent trajectories can't exist, but for obvious reasons I'm 99% sure that something's wrong with it

AdmBorkBork

20:16

> The Get-ExBlog cmdlet opens your default browser to display the Exchange Team blog. This cmdlet works only if the Exchange management tools are installed.

5

Why is that a thing?!

Mendeleev

@AdmBorkBork whaaaaaat

AdmBorkBork

I mean, on the flipside, I can open a browser window just by typing exblog ... so, yay?

Mendeleev

Why not just type chrome?

or iexplore or MicrosoftEdge or whatever you use

AdmBorkBork

exblog is golfier

:p

Riker

ie? or edge?

Jan Dvorak

20:31

I call it IEdge

Down Christopher

Holy crap. Younger Sister A is wrong about something we were talking about. Gets mad at me since she was wrong. Younger Sister B gets mad at me since I was right

Anonymous

@JanDvorak IEdge, YouChrome

Down Christopher

Siblings do you even logic?

AdmBorkBork

@Mego Nice.

DJMcMayhem

I'm not sure how far ranting about siblings will get you in here. Especially since we don't know them

Down Christopher

20:33

Why can I VTC but not VTO

@DJMcMayhem Didn't mean it as a rant :P just confused as it is a daily thing

AdmBorkBork

@DownChristopher Wizard's Third Rule.

DJMcMayhem

I have a lot of sisters so I know what that's like

Down Christopher

@AdmBorkBork what?

AdmBorkBork

@DownChristopher From The Sword of Truth series. Wizard's Third Rule is "Passion rules reason."

Down Christopher

@AdmBorkBork I got to the Sword Of truth link but never found the excact tnaks

AdmBorkBork

20:38

The books feature a series of "Wizard's Rules"

One of them, the Third Rule, is "Passion rules reason."

DJMcMayhem

It's a good rule

Down Christopher

Yeah. It explains a lot of PPCG

I mean have you looked back at the answers and pretended that you have no idea what code is?

Wheat Wizard

CMC: What is the rank (bronze/silver/gold) of everyone's most exclusive badge (badge that the least amount of other people have achieved)

ETHproductions

Silver for me (Strunk & White)

Runner-up would be gold code-golf

DJMcMayhem

Bronze (Proofreader)

Wheat Wizard

20:45

For myself it is Bronze (Proofreader)

ETHproductions

> Sheriff: Served as an elected moderator for at least 1 year

DJMcMayhem

Oh wait, that's not true

ETHproductions

I can't remember whether or not we've had a moderator election :P

Helka Homba

@WheatWizard Probably gold - socratic codegolf.stackexchange.com/help/badges/93/socratic

DJMcMayhem

There are 11 with proofreader and only 10 with synonymizer. That's my rarest

New Main Posts

20:47

-1

Q: Jagged Mountaintop

a.) Given an input integer n, output an array of random integers from 0 to n without repeating any integers. The array should be n + 1 in length. Assign the array created to the variable y. input: 7 y: 6 2 1 7 0 3 5 4 input: 12 output: 3 11 0 7 6 8 2 1 10 12 4 5 9 b.) Ass...

code-challenge javascript code-generation calculus matlab

AdmBorkBork

@WheatWizard Inquisitive, silver -- codegolf.stackexchange.com/help/badges/92/inquisitive

Doorknob

Mine's Socratic also (surprisingly not Constable).

Poke

Silver (Outspoken)

DJMcMayhem

@HelkaHomba I am gonna get that eventually. :)

It might take me a while though

data.stackexchange.com/codegolf/query/427292/…

ETHproductions

Oh, my bad, I have bronze decision-problem with a total population of 12

DJMcMayhem

20:49

I hope to be the first to get steward, but Martin will probably beat me

Doorknob

Apparently Socratic is tied for bronze [graphical-output], heh

DJMcMayhem

I bet I can get second though

Down Christopher

codegolf.stackexchange.com/help/badges/32/altruist bronze

AdmBorkBork

@HelkaHomba I'm closing in on that, currently at 41

Down Christopher

kinda lame

Wheat Wizard

20:49

Martin is really close

I'm gaining on him but I'm really far behind

Helka Homba

Does anyone know for certain they were the first to get a particular type of badge (any rank) on PPCG? (socratic for me :D)

DJMcMayhem

We all are

AdmBorkBork

@HelkaHomba Martin was the first Legendary.

New Sandboxed Posts

0

A: Sandbox for Proposed Challenges

Island golf #1: Circumnavigation code-golf path-finding ascii-art optimization grid Given an island in ASCII-art, output an optimal path to circumnavigate it. Input Your input will be a rectangular grid consisting of two characters, representing land and water. In the examples below, land is ...

Down Christopher

I was first in nothing

DJMcMayhem

20:51

@Doorknob That'll be sheriff pretty soon here

ETHproductions

@HelkaHomba I was close on the bronze decision-problem (there were six who got it originally), but I didn't earn it right away

Doorknob

@HelkaHomba I was the first bronze [popularity-contest], apparently. Not sure how proud of that I am :P

ETHproductions

I'm fairly certain I was way late on all the others I have

Down Christopher

Going for codegolf.stackexchange.com/help/badges/35/unsung-hero

AdmBorkBork

@DownChristopher Good luck

ETHproductions

20:53

It's near impossible to get a 0-score accepted answer, though I have one I think

fəˈnɛtɪk

We can help by downvoting all your accepted answers :P

Down Christopher

@fəˈnɛtɪk So none?

fəˈnɛtɪk

If you ever get any

ETHproductions

Tip: build boring answers that piggyback off the existing ones, but in a language where the technique is shorter

Down Christopher

:P

Wheat Wizard

20:54

Its hard to get an accepted answer. The one time I did it was an accident

Down Christopher

How long does a question have to be up before an answer can be accepted?

20 min?

ETHproductions

I don't know that there's a time limit (there probably is though)

betseg

AdmBorkBork

I was rather close to getting Tumbleweed a few months ago. The first upvote on my question came over 24 hours after I posted it.

betseg

updated chromium... and 2 gb ram usage with 3 tabs

fəˈnɛtɪk

20:55

@ETHproductions you have 2 0 score accepted

Helka Homba

@DownChristopher Not sure there is a limit but on PPCG I'd wait at least a week

DJMcMayhem

I wonder if I could be third to a gold string badge

Down Christopher

@HelkaHomba No a real time limit

ETHproductions

@fəˈnɛtɪk Do I? I've no clue how to check that

Down Christopher

I think it is 20 minute

fəˈnɛtɪk

20:56

Go to your answers tab and sort by votes?

ETHproductions

Besides going to my answer tab and... yes :P

There must be a quick way to see all your accepted answers, a query if nothing else

Wow... do I really have 15? I thought I had about 5

Down Christopher

I have 0

I think I have 1 over the network...

AdmBorkBork

@ETHproductions I have 422 answers, 3 of them accepted.

Yay verbose languages.

ETHproductions

Were those 3 in PowerShell? (I don't know if you use any other languages)

DJMcMayhem

I have 12. Every single one of them is in V

No wait, that's not true

2 in MATL, 2 in Vim

AdmBorkBork

21:07

@ETHproductions I've written a couple answers in BATCH, I think one or two in Vbscript, and I think one each in Python and Java. So, yes, almost exclusively PowerShell.

All my accepted answers were in PS

Wheat Wizard

I have two accepted answers and both of them are in Brain-Flak

Dennis

@ETHproductions codegolf.stackexchange.com/search?q=isaccepted%3A1+user%3Ame

Poke

I have zero accepted answers because there's not enough love for Java

shame on all of you

DJMcMayhem

@Dennis Oh, I just went through mine manually, haha

Nathan Merrill

esolang idea: a language that can look at previously executed commands and re-execute them

AdmBorkBork

21:16

@NathanMerrill PowerShell can do that.

technet.microsoft.com/en-us/library/…

Nathan Merrill

how does that work with loops?

Poke

@NathanMerrill related

DJMcMayhem

Vim can do that. :)

Nathan Merrill

I was more thinking along the lines of passing them a multi-dimensional array. The first element would be the main function, and then its children would be each of the commands its executed. If any of those commands were functions, it would have more children for its contents

so, instead of restricting languages to a 2D line of commands executed, you really have the entire history and stack trace of execution

Helka Homba

Is that different from goto statements? (effectively functions)

TuxCopter

21:29

> The next revision of the language (Fortran 2015) is intended to be a minor revision and is planned for release in mid-2018.

2

what

Down Christopher

much lazy

ETHproductions

@Dennis Oh cool, thanks!

Lembik

21:45

@Poke I have a new challenge that is crying out of a Java solution!

Poke

orly

Down Christopher

@Geobits You live!

DJMcMayhem

22:05

Huh? It doesn't look like he's in here now

fəˈnɛtɪk

@DJMcMayhem Don't you remember, he's dead

Geobits

@DownChristopher Do I?

My internet won't be turned on until the 27th, so I'm not sure this is what you'd call living

3

Helka Homba

6 is being difficult

Down Christopher

@Geobits Oh nevermind i guess you are not living

New Meta Posts

22:30

0

Q: "Windows" as a programming language?

I was going to give the green tick mark to the winning submission of this language, but I am unsure what to do. The shortest submission is this, which claims to use "Windows language", but I doubt that Windows can be considered a language. What do you think? I know our official definition of pro...

discussion policy answers

0

Q: Is Ctrl-C one keystroke or two?

Preliminary question: is it valid to score Excel in keystrokes? I guess it is, but I'm not sure what our policy is. Assuming it is (or, in general, for languages that are scored in keystrokes), does Ctrl-C count as one keystroke or two? If it is two, would uppercase "A" be two keystrokes as wel...

discussion policy code-golf answers

New Sandboxed Posts

0

A: Sandbox for Proposed Challenges

Find the optimal pattern code-golf string Given a string s composed of lowercase letters, such as aabaaababbbbaaba and a positive integer n, such as 4, output a length-n string t such that when t is repeated to the length of s, they have as many chars in common as possible. For the given e...

ETHproductions

Wow, that was literally instantaneous

Jan Dvorak

It wasn't. I see a ... -3 seconds delay???

Wow

New Main Posts

-4

Q: Golf you some subtraction!

You must subtract 2 numbers that are inputted and output the result. Rules are standard golf and I/O rules

code-golf

quartata

22:55

@NewMainPosts I'm amazed this stayed open that long

Anonymous

@quartata It took me forever to find the dupe

Anonymous

My search-fu is apparently weak today

Luis Mendo

I searched for a duplicate but couldn't find it. And personally I don't see how "add" is a dupe of "subtract" :-)

@Mego and your spelling too :-P

Anonymous

@LuisMendo a-b == a+-b

Anonymous

@LuisMendo Huh?

Luis Mendo

22:58

But that would be pre-processing the input

^^ Sorry, it's my spelling which is wrong

Anonymous

@LuisMendo That's not what I meant

Luis Mendo

I confused "weak" / "week"

Anonymous

Swapping the sign of one of the inputs is a trivial change

quartata

It's really just restricting the domain

Luis Mendo

^^ Of course. I agree the challenge is trivial, and maybe even deserves being closed. I just don't see it's a dupe of that one

Not that it matters much, anyway

Down Christopher

23:15

To quote Stewi @Mego & cc/Wheat Wizard... This is quite different in binary, unless the language can do binary maths. Nowhere is it said that this should be done in decimal. I'm attempting to solve this with simply bit-wise operations, although I'm struggling to keep it short, while handling negative results. (And no, that's not a loophole. I believe the loophole is to use a base that makes the challenge trivial

Anonymous

23:42

@DownChristopher "It's not a trivial modification in this one instance where I've intentionally crippled myself" doesn't mean it's not a trivial modification in general.

Transcript for