The Nineteenth Byte

quartata

2:00 PM

?

user202729

> A state register that stores the state of the Turing machine, one of finitely many.

Dennis

If that was directed at me, I don't understand the question.

user202729

Of course it can be infinite, but it's no longer a TM.

Anush

new version made codegolf.meta.stackexchange.com/a/16377/9207

please let me know what is confusing about it

quartata

@user202729 ok I think I see the problem

user202729

2:05 PM

@Anush Of course arithmetic on 64 bit integers can be performed in constant time.

Anush

@user202729 yes I know :)

Dennis

@Anush This means that the running time per output should not grow with the size of k or the size of the integers in I. That's impossible, because both affect the output size.

Anush

@Dennis each output is a pair of numbers

ah you mean the index grows?

quartata

"Finite-state machines" are distinct from the higher level computational models because they have no memory, just the state

user202729

@quartata Uh oh, I thought it was something else...

Nevermind.

So it's like a TM but with finite memory.

quartata

2:09 PM

No tape. It reads one symbol at a time and moves to a new state based on it

Anush

@Dennis how is it now?

quartata

But yeah if the number of state transitions or something were infinite that's essentially like saying the program was infinitely long

Dennis

I think calculating the time complexity for each individual output is confusing.

And I really wish it wasn't restricted complexity at all, but that's your call.

quartata

so a bit of a different distinction

Anush

@Dennis oh I am sorry it is confusing. What I don't want is code that computes all the answers in one go and then outputs them

Dennis

2:12 PM

That's not at all clear from your requirements, and a rather bad idea imho.

user202729

@Anush ...? So for all (x) the (x)'th answer must be outputted in O(x) time? That's an even stricter requirement.

Anush

@Dennis oh that's a helpful comment

user202729

Apr 23 at 14:49, by Anush

how does anyone ask a question on ppcg!

Anush

@user202729 O(1) per output does indeed imply that outputting the first x answers
takes O(x) time

@Dennis which part is the bad idea? Banning batch solutions?

quartata

Heh this is a classic quandary

user202729

2:15 PM

Now it becomes much harder. Not sure if it's possible now.

quartata

Do you want answers to be short, or do you want them to be fast?

You pretty much only get to pick one, in my experience

fastest code contests are very popular here too

user202729

I think that O(output size × k) is reasonably good already. O(1) per output strictly (not amortized) is... a bit overkill.

quartata

so you could do that

disclaimer haven't read challenge yet

Anush

@user202729 ok.. I can change it to O(output size × k)

user202729

So you're not even allowed to allocate a k-words array before outputting the first value.

Anush

2:17 PM

@user202729 I was going to make an exception for the first value :)

Dennis

@Anush Yes. If you want something like that, I'd suggest a program that takes the arrays I and O as input and computes the "next" O.

Anush

@Dennis makes sense

I like that

user202729

@Dennis Then it can't take amortized constant time per array.

@Anush You can just edit message...

Anush

@user202729 thanks

Erik the Outgolfer

@EsolangingFruit the joke is my comment...

@EriktheOutgolfer It's wasn't intended as a joke; it's an infinite number of test cases! — Esolanging Fruit 1 min ago

Poke

2:19 PM

wowsers sql gave me a giant middle finger yesterday

apparently the driver i'm using defaults to sending nvarchar character data

so if the column i'm querying contains varchar

then the whole column gets implicitly converted before using an index scan instead of a seek

the good ole double "fuck you"

user202729

@Poke Be careful of flags...

Dennis

@user202729 Why not?

user202729

@Dennis Reading the array takes O(k) already.

Poke

@user202729 i don't believe that warrants any

Dennis

Neither do I, but it only takes 6 users (or one mod) to think otherwise.

Poke

2:23 PM

aye

Anush

ok modified again

please take a look

user202729

@Anush So solutions that will only output at program exit are not acceptable?

quartata

@Dennis except that it only takes one mod here to think differently differently

Anush

@user202729 right

@user202729 I added that to the question

it's harder to write these questions than I expected :)

Erik the Outgolfer

that's why the sandbox exists

Anush

2:31 PM

a very good point

user202729

Some things are easier to write than others.

Anush

I see that trying to specify any restriction on time or space needs careful thought

and the help of a chat room!

ngn

@EriktheOutgolfer I don't like writing "shortest wins" in all my challenges, either. Is there anything we can do to challenge that policy?

Erik the Outgolfer

@ngn well, just post an answer yourself, I've never had time to do so myself yet :P

then hope it gets upvoted

ngn

@EriktheOutgolfer OK, will do. Vote ngn! :)

Anush

2:35 PM

:)

Erik the Outgolfer

@ngn you'll not decide what I vote! :P

btw you can also downvote an answer you disagree with

user202729

@ngn That is to make sure that the OP actually know what they're doing.

Anush

I like the language of the month idea

18

Q: Language of the Month for May 2018: MATL

In accordance with our meta agreement to have a Language of the Month, and since the list of nominations had a single highest-voted entry at the beginning of May, we have a new featured language! Throughout May 2018, our Language of the Month, nominated by DJMcMayhem and Sanchises, will be: M...

user202729

We have a lot of users who don't know what the site is for and just choose the most popular tag, it can make some problems.

Anush

I hope it stretches to underused by non-eso langs

ngn

2:37 PM

@user202729 then why have the tag at all?

user202729

@ngn Uh... to classify challenges?

Erik the Outgolfer

if you know of a language that you think should be used more in here then feel free to post an answer here :)

Anush

quickbasic! I can't compete with that :)

Erik the Outgolfer

although it could help, you don't need to know the language yourself

ngn

@user202729 duplication of information is bad

Erik the Outgolfer

2:41 PM

@ngn searchability is a thing

ngn

@EriktheOutgolfer I would prefer to have just the tag and a detailed explanation of what "code golf" means in the tag description. There's no need to re-state the same thing over and over again in all such challenges.

user202729

5 mins ago, by user202729

We have a lot of users who don't know what the site is for and just choose the most popular tag, it can make some problems.

If you don't want to type them you can make an userscript or copy-and-paste...

Erik the Outgolfer

@ngn that explanation already exists

and yes, I agree with you here

however, let's not fight please...

Pavel

> Try to build ZAPM
> Requires SDL_image-devel package
> Install SDL_image-devel
> Build fails for unrelated reasons
> Give up
> Try to remove now unneeded SDL_image-devel package
> sudo dnf remove SDL*
> Everything breaks as around 100 packages are removed

ngn

@user202729 Users who don't know what the site is for should learn what it's for, but not at other users' expense.

user202729

2:46 PM

@ngn I don't see how repeating the information is bad.

Erik the Outgolfer

well, basically, if a user doesn't bother to read what stuff is about (it comes as a pop-up right after they type the tag), then it's not our fault

ngn

@user202729 verbosity is distracting

user202729

@ngn After a while you will get used to ignoring them. For me, I consider that insignificant.

They usually just fall under the "General rules" section.

Pavel

Annyone know what packages provides libpanel.so.5 on Fedora?

Dennis

dnf provides /usr/lib64/libpanel.so.5

Pavel

2:52 PM

Thanks

Dennis

Or dnf install /usr/lib64/libpanel.so.5, if you want to install it and golf one invocation of dnf.

Pavel

Says ncurses-compat-libs is already installed, but... ./zapm: error while loading shared libraries: libpanel.so.5: cannot open shared object file: No such file or directory

Oh, I need 32 bit. Lovely.

Dennis

So dnf install /usr/lib/libpanel.so.5.

I really like this feature of dnf.

Pavel

It is awesome and I will definitely be using it from now on.

New Sandboxed Posts

0

A: Sandbox for Proposed Challenges

Orthodiagonal steps It's a common problem to navigate in 2d matrix. We've seen it many times and will see again. So lets help future us and develope shortest solutions to generate all eight possible steps in 2d matrix. Challenge Your code takes no input. Your code must output next 8 pairs of -...

0

A: Sandbox for Proposed Challenges

Multidimensional orthodiagonal steps Step further in step generation. Navigation in 2d matrix is common, but something uncommon is even more insteresting. Now I'll ask you to develope shortest solutions to generate all possible steps in N-dimensional matrix. Challenge Your code takes positive ...

Luis Mendo

3:07 PM

The force is strong with this bookend

2

New Main Posts

0

Q: Devu and Minimizing Runs of a String

I was confused whether to ask this question here or SO; as I am not looking for optimal solution/minimum bytes for this problem; instead have someone review my algorithm, which I am not sure where it goes wrong With that said, I came across following problem on HackerRank Devu likes to play wit...

string math code-challenge programming-puzzle algorithm

Pavel

I just got an update to Python 2
Insert "What year is it" meme

I think they should stop releasing Python 2 patches. If it stops getting security fixes, people will eventually move on to Python 3.

Dennis

pythonclock.org

I wonder what that means for PyPI.

Poke

@Pavel that's not really true, ha

Soaku

3:23 PM

@Pavel You mean, you updated your Python 2 or updated to Python 2?

Poke

there's a reason "long term support" exists

Pavel

@Soaku My Python2 package got updated

AdmBorkBork

@Pavel "If it stops getting security fixes, people will eventually move on." As someone who works in Corporate IT ... haha ... hahahahaha .... hahahahahahaha, oh that is funny. :D

Pavel

@Poke It's been a decade, that's long enough

Poke

^^

Pavel

3:24 PM

@AdmBorkBork Ok, the people who won't move on will pretty much deserve what happens to them when they get affected by a security exploit.

Poke

if there's one thing i've learned in my career so far

it's that people don't give a shit about security

and it's not just people

Pavel

Then don't support these people with security fixes they don't care about.

Poke

it's also businesses as a whole

a business typically prioritizes and pushes for features and stuff they can sell

good security just costs money and takes time

Pavel

It's wasted effort that could be used to make py3 better.

Poke

also not necessarily true

quartata

3:27 PM

they've put a massive amount of effort into python3

i don't think they're losing out by throwing a bone to legacy users

Pavel

Why not release security fixes for Python 1 while we're at it? I'm sure the bank still uses it for something.

quartata

...??

people actually use Python 2 in production

and, for a reason

Poke

a major version change to any piece of software is a big deal. on ppcg we even treat python 2 and 3 as different languages

quartata

For one PyPy3 still sucks ass

Poke

why should people rewrite working software in what is essentially a new language

Pavel

3:30 PM

Well the people using PyPy won't benefit from CPython fixes, right?

El'endia Starman

At my work, we actually recently forked a Python 2 library into a private repo so we could make it actually support Python 3, which we migrated our whole stack to only a few months ago.

Pavel

@Poke Because it's actually quite easy, and there are even automated tools (futurize) that do it for you.

quartata

@Pavel Uhhhhhhhhh

It's not easy

Oh dear is it not easy

2to3 is good but not a magic bullet

Dennis

@quartata No kidding. There are even Python 3 libraries that depend on Python 2.

quartata

indeed

Also a lot of build scripts for even non-Python stuff are written in Python 2 because it comes by default with most distros

Indeed most GNOME apps depend on Python 2 one way or another

Pavel

3:34 PM

So what happens in 2020?

quartata

probably nothing

Dennis

We'll see. People don't have to stop using it just because it reached EOL.

quartata

moving away from Python 2 as the default is tricky because of GNOME, and GNOME moving away from Python 2 is tricky because it's the default

it's probably fine

they should have just used Perl but meh

Dennis

Well, Fedora considers Python 3 the default now. It doesn't even come with Python 2.

quartata

really?

well in that case they've probably made those changes by now then

Dennis

3:36 PM

For at least one year now.

quartata

other DEs will follow suit

Pavel

@Dennis Is that just server

quartata

(it still runs GNOME 3 right?)

Dennis

Not sure tbh.

I haven't used desktop Fedora in years.

Anush

I am thinking of posting codegolf.meta.stackexchange.com/a/16377/9207

Pavel

3:37 PM

IDK if my Fedora Workstation came with it or if it just got installed nearly immediately as a dependency to something.

Anush

unless there are last minute objections

Pavel

@Dennis I keep reading articles about how they're going to deprecate Py2 sometime 2018 for RHEL land Fedora, so I'm guessing it's only server.

@quartata Doesn't have to, mine came with KDE.

Dennis

xorg-x11-server-common has python2 as a dependency, so yeah.

Anush

annoyingly python 3 is slower than python 2 in quite a lot of cases

and python 2 is already very very slow

Pavel

I have no idea why but Wayland is disabled on my machine and I can't figure out how to enable it.

Dennis

3:40 PM

Python 3 and its generators can be a lot faster than Python 2 though.

It all depends on the problem size, I guess.

Luis Mendo

Matlab is said to be usually faster. Runs

@Anush What does this mean? running time per new output should be no greater than O(k) Perhaps you should clarify that sentence

Anush

@LuisMendo thanks

wizzwizz4

@Anush list used to be hardcoded faster.

And Python 3.6 made a change to the compiler so it now supports changing the order of stuff for speed reasons.

So I think they're working on the compiler now.

And if you want speed, PyPy's always been the way to go.

Dennis

Well, PyPy2. PyPy3 got a lot better, but it's still bad.

Anush

@wizzwizz4 I love pypy but it does really need your code to be pure python for the speed advantages

@LuisMendo better now?

Pavel

3:47 PM

According the the Fedora docs, only Py3 support for a package is considered better than both Py3 and Py2 compatibility.

wizzwizz4

@Anush I'm making a pure Python Python modification program.

@Pavel I think that means "it's better to use the new Python 3 features instead of trying to keep backwards-compatibility".

Pavel

@wizzwizz4 Right, but packages that support both are marked as needed to be fixed even if no other development on them is happening.

wizzwizz4

@Pavel Erm... Odd, but I suppose they want to completely phase out all Python 2 support to force people to use Python 3.

Pavel

Exactly

Dennis

Well, polyglots are usually bloaty and suboptimal in both languages.

2

user202729

4:01 PM

Except for trivial ones.

What Wizard

@Dennis citation needed

New Main Posts

0

Q: Generalized Gray codes

Input: An array I of k positive integers. The integers will be no larger than 100 and k <= 100. Output: Your code must output all possible arrays O of non-negative integers of length k with the restriction that 0 <= O_i <= I_i. To get from one array to the next you may add or subtract 1 to one...

code-golf restricted-complexity

user202729

I forgot to complain about the 64 bit thing.

Now there are ... then ... ?

Theorical limits are hard to get right.

Anush

what is the complaint?

user202729

Nothing.

Dennis

4:08 PM

@WhatWizard Counterexamples don't really work for usually. I choose my weasel words wisely.

4

Anush

ok :)

hmm..one down and one up vote :)

Luis Mendo

@Anush I still don't understand running time per new output. Shouldn't it just be running time? Also, are you sure there is an O(k) algorithm? (I don't know, I just fear it may be too restrictive)

Anush

@LuisMendo each output is an array of length k

but there are lots of lots of those arrays to output

does that make sense?

wizzwizz4

That would be O(k*n) where n is the number of arrays to output.

Luis Mendo

So, running time O(k) per new output is total running time O(N*k) where is the number of outputs?

Ah, ninja'd

Anush

4:14 PM

yes except see "One consequence of the restricted-complexity is that solutions that only output at program exit are not acceptable."

Luis Mendo

Why is that so?

wizzwizz4

I don't see how that's a consequence of your restrict... ninja'd.

Anush

because it would take you O(n*k) time just to output the first output array

Luis Mendo

...and?

Anush

but the rule is O(k) for each new output

wizzwizz4

4:15 PM

O(3*n*k) = O(n*k)

Anush

O(n * k) is much larger than O(k)

What Wizard

presumably it would take constant time for all the other arrays, so it would average to O(k)

Anush

so the number of output arrays is 2^k... if you wait until you have computed them all before outputting one, then it takes you 2^k * k time to output the first one

wizzwizz4

The algorithm includes output, and is O(n*k).

Anush

which is much worse than k time

wizzwizz4

4:16 PM

The order doesn't affect the complexity.

Anush

let's say I want to out the numbers 1 to n.

1

2

3

wizzwizz4

You're measuring something that isn't complexity in the traditional sense.

Luis Mendo

If I understand correcltly, you should say that you (1) require each output to be displayed on the fly, as opposed to on program exit, and (2) with O(k). I don't see how (1) is a consequence of anything @Anush

Anush

I can put a restriction on the time per number I output

user202729

@wizzwizz4 Why?...

Anush

4:16 PM

which is not the same as putting a restriction on the total time for all of them

do you see?

wizzwizz4

@user202729 See the surrounding two messages.

What Wizard

When you say "per" do you mean the average complexity or the complexity of each?

Anush

@WhatWizard the latter

What Wizard

You should then say that.

Anush

I thought I did :)

but I am happy to add more clarification

user202729

4:18 PM

What's hard to understand about it? At any moment, the time before you receive the next output is O(k).

What Wizard

per implies a division.

user202729

@WhatWizard I think it means "for each".

What Wizard

yes it seems that it does, but that could be much clearer

Anush

@WhatWizard edited

wizzwizz4

@user202729 What variation is allowed? And generally O(k) is referring to the whole algorithm.

Mr. Xcoder

4:19 PM

BTW @WhatWizard do you now understand what you have to output in my bee challenge?

Anush

is everyone happy now?

What Wizard

@Mr.Xcoder yes, I'll delete my comment in a moment

Luis Mendo

@Mr.Xcoder Bee challenge, please :-)

user202729

@wizzwizz4 How else would you say it? ...

Luis Mendo

3 mins ago, by Luis Mendo

If I understand correcltly, you should say that you (1) require each output to be displayed on the fly, as opposed to on program exit, and (2) with O(k). I don't see how (1) is a consequence of anything @Anush

user202729

4:20 PM

@Anush Can I use the (index,change) format?

What Wizard

@Anush The newest edit has made me even more confused

Mr. Xcoder

@LuisMendo status-completed :D

Anush

@WhatWizard why??

wizzwizz4

> Note this is not the average time per output but the worst case time for each array outputted.

One way of saying it.

Anush

@user202729 hmm...It's not that I care but I would need to edit the question

wizzwizz4

4:21 PM

This eliminates caching-based algorithms.

user202729

@wizzwizz4 Caching?

Anush

@wizzwizz4 it eliminates algorithms that compute all the output arrays in a batch

wizzwizz4

@Anush Well, not quite.

What Wizard

Ok now I think this is clear, but still very circuitously worded

Anush

@WhatWizard I am open to suggestions for better wording of course

wizzwizz4

4:22 PM

An algorithm that calculates everything for every possible input value in the allowed range, then only returns the ones for the chosen input...

user202729

@WhatWizard Perhaps you can help with the wording?

Pavel

Whenever I see a message that reads "@WhatWizard why??" I immediatly assume he has a new profile pic.

16

J. Sallé

@Pavel relatable

What Wizard

> Every new array should be output with time on the order of O(k) elapsing since the last result (or the start of the program for the first result). That is it should take time proportion to k and not, for example k^2 or 2^k. Note this is not the average time per output but the worst case time for each and every array outputted.

How is that?

wizzwizz4

Let's say I have an algorithm:

Anush

4:27 PM

@wizzwizz4 thanks.. I used a version of that

nimi's answer is mysterious!

does anyone understand it?

wizzwizz4

do_half_of_the_thing_whilst_outputting
for i in range(k):
    for j in range(k):
        clean_cache(i, j)
do_other_half_of_the_thing

user202729

@Anush That's... Haskell has a built in for Cartesian product.

wizzwizz4

This algorithm would fail.

Anush

oh dear my example is broken

I mean it misses lots of arrays out

wizzwizz4

@Anush I stole that from your post. :-p

Anush

4:31 PM

@wizzwizz4 sorry stole what?

ngn

@EriktheOutgolfer @user202729 in relation to our conversation two hours ago, I've posted an answer in the hope of reversing the policy of re-explaining what code golf means in every code-golf challenge

Anush

nimi's answer is completely wrong

wizzwizz4

@Anush The quoted wording that I thought you were saying thanks about.

Anush

ah ok :)

I thought it was too good to be true

@user202729 can you compute a correct set out of output arrays for [2,1,3] by any chance?

I am worried about the sequence I made by hand

Pavel

6:07 PM

Anyone know how to use jq to filter out only those objects with a certain property equalling a given value

Dennis

select(.property==value)

Pavel

Thanks

AdmBorkBork

6:56 PM

The OEIS is weird sometimes

Pavel

CMC: Output ^

dzaima

@Pavel output all or get the nth element?

Pavel

Either

Whichever is shorter

dzaima

@Pavel SOGL, 8 bytes

AdmBorkBork

@(3,6,4,8,10,5,5,7) ... probably as short as it gets in PowerShell.

DJMcMayhem

7:05 PM

@Pavel (((((((((()()())){})[[]])[]())()())[[]]))()())

Adám

@Pavel APL (Dyalog Unicode), 13 bytes ⎕A⍳'CFDHJEEG'

Poke

@Pavel just use this handy dandy polynomial y = -19/2520 x^7 +1/5 x^6 -181/90 x^5 +223/24 x^4 -6313/360 x^3 -179/120 x^2 +17453/420 x -27

2

Adám

CMC: [19,17,13,11]

dzaima

7:23 PM

@Adám SOGL, 5 bytes

Adám

@dzaima Explanation? Just compression or actual reverse sequence of primes, or?

dzaima

@Adám 1st 4 chars codepoints are 19,17,13,11, last marks a char decode string

Adám

@dzaima Meh. What would it take to get the 8th-5th primes?

Mr. Xcoder

@Adám Pyth, 6 bytes (prime factors of 46189)

dzaima

@Adám making a prime number generator..

Adám

7:26 PM

@dzaima Oh dear.

@Mr.Xcoder Nice.

Mr. Xcoder

@Adám Does the order matter, though?

DJMcMayhem

@Adám BrainFlak, 36 (((((()()()()()){}())()())[][])()())

Mr. Xcoder

If that’s the case, then prepend _ for 7 bytes

AdmBorkBork

Feature-Request: Change the name of the language to BrainFla

dzaima

@Adám Ρ`“Μ would work for 4 (what Mr.Xcoder did) if Μ was implemented..

DJMcMayhem

7:27 PM

In pseudocode: push(push(push(push(11) + 2) + stackHeight * 2) + 2) #implicitly print

Adám

@Mr.Xcoder I guess not. Nobody is around to tell us in which direction they meant the bone to be read.

DJMcMayhem

Or in more detail, push(push(push(push(push(5) + pop() + 1) + 2) + stackHeight * 2) + 2) (and note that push(n) evaluates to n)

Adám

@Mr.Xcoder J, 7 bytes q:46189

Cows quack

@Adám how many bytes do you have for apl?

Adám

@Cowsquack I'm afraid it'd have to be same method as my previous answer.

Dennis

7:39 PM

@Adám Jelly, 4 bytes: ⁵æRḤ

Mr. Xcoder

Very straight-forward. Nice.

Cows quack

@Adám I have 9 bytes

Adám

@Cowsquack Yup: ⎕A⍳'SQMK'

Cows quack

9+2×3~⍨⍳5

Adám

@Cowsquack Ha! That's neat.

Zacharý

7:43 PM

What is this for?

Cows quack

@Dennis how does that work?

Zacharý

Ah, I see the CMC now.

Dennis

@Cowsquack ⁵ sets the argument to 10, Ḥ unhalves (yielding 20), and æR creates a prime range from 10 to 20.

Adám

@Dennis Really cool. ANd I thought my CMC was boring.

Mr. Xcoder

It’s very convenient to solve in Jelly because tacit + appropriate atoms :P

5 bytes, 05AB1E

Second solution, 5 bytes too

AdmBorkBork

7:59 PM

unhalves, hehe

Transcript for