2:00 PM
?

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

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

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

@user202729 ok I think I see the problem

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

@user202729 yes I know :)

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

@Dennis each output is a pair of numbers
ah you mean the index grows?

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

@quartata Uh oh, I thought it was something else...
Nevermind.
So it's like a TM but with finite memory.

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

@Dennis how is it now?

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

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.

so a bit of a different distinction

@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

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

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

@Dennis oh that's a helpful comment

Apr 23 at 14:49, by Anush
how does anyone ask a question on ppcg!

@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?

Heh this is a classic quandary

2:15 PM
Now it becomes much harder. Not sure if it's possible now.

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

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

so you could do that

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

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

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

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

@Dennis makes sense
I like that

@Dennis Then it can't take amortized constant time per array.
@Anush You can just edit message...

@user202729 thanks

@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

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"

@Poke Be careful of flags...

@user202729 Why not?

@user202729 i don't believe that warrants any

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

2:23 PM
aye

ok modified again

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

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

@user202729 right
@user202729 I added that to the question
it's harder to write these questions than I expected :)

that's why the sandbox exists

2:31 PM
a very good point

Some things are easier to write than others.

I see that trying to specify any restriction on time or space needs careful thought
and the help of a chat room!

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

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

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

2:35 PM
:)

@ngn you'll not decide what I vote! :P
btw you can also downvote an answer you disagree with

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

I like the language of the month idea
18

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

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.

I hope it stretches to underused by non-eso langs

2:37 PM
@user202729 then why have the tag at all?

@ngn Uh... to classify challenges?

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

quickbasic! I can't compete with that :)

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

@user202729 duplication of information is bad

2:41 PM
@ngn searchability is a thing

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

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

and yes, I agree with you here

> 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

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

2:46 PM
@ngn I don't see how repeating the information is bad.

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

@user202729 verbosity is distracting

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

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

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

2:52 PM
Thanks

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

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.

So `dnf install /usr/lib/libpanel.so.5`.
I really like this feature of dnf.

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

0

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

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

3:07 PM
The force is strong with this bookend
2

0

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

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.

I wonder what that means for PyPI.

@Pavel that's not really true, ha

3:23 PM
@Pavel You mean, you updated your Python 2 or updated to Python 2?

there's a reason "long term support" exists

@Soaku My Python2 package got updated

@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

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

^^

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.

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

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

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

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

also not necessarily true

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

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

...??
people actually use Python 2 in production
and, for a reason

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

For one PyPy3 still sucks ass

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

3:30 PM
Well the people using PyPy won't benefit from CPython fixes, right?

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.

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

@Pavel Uhhhhhhhhh
It's not easy
Oh dear is it not easy
2to3 is good but not a magic bullet

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

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

3:34 PM
So what happens in 2020?

probably nothing

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

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

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

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

3:36 PM
For at least one year now.

@Dennis Is that just server

(it still runs GNOME 3 right?)

Not sure tbh.
I haven't used desktop Fedora in years.

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

unless there are last minute objections

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

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

annoyingly python 3 is slower than python 2 in quite a lot of cases
and python 2 is already very very slow

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

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.

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

@LuisMendo thanks

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

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

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

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

@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".

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

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

Exactly

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

4:01 PM
Except for trivial ones.

0

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

I forgot to complain about the 64 bit thing.
Now there are ... then ... ?
Theorical limits are hard to get right.

what is the complaint?

Nothing.

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

ok :)
hmm..one down and one up vote :)

@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)

@LuisMendo each output is an array of length k
but there are lots of lots of those arrays to output
does that make sense?

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

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

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

Why is that so?

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

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

...and?

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

4:15 PM
`O(3*n*k) = O(n*k)`

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

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

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

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

which is much worse than k time

4:16 PM
The order doesn't affect the complexity.

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

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

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

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

@wizzwizz4 Why?...

4:16 PM
which is not the same as putting a restriction on the total time for all of them
do you see?

@user202729 See the surrounding two messages.

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

@WhatWizard the latter

You should then say that.

I thought I did :)
but I am happy to add more clarification

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

per implies a division.

@WhatWizard I think it means "for each".

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

@WhatWizard edited

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

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

is everyone happy now?

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

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

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

4:20 PM
@Anush Can I use the (index,change) format?

@LuisMendo :D

@WhatWizard why??

> Note this is not the average time per output but the worst case time for each array outputted.
One way of saying it.

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

4:21 PM
This eliminates caching-based algorithms.

@wizzwizz4 Caching?

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

@Anush Well, not quite.

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

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

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

@WhatWizard Perhaps you can help with the wording?

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

@Pavel relatable

> 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?

Let's say I have an algorithm:

4:27 PM
@wizzwizz4 thanks.. I used a version of that
does anyone understand it?

```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```

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

This algorithm would fail.

oh dear my example is broken
I mean it misses lots of arrays out

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

4:31 PM
@wizzwizz4 sorry stole what?

@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 The quoted wording that I thought you were saying thanks about.

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?

1 hour later…
6:07 PM
Anyone know how to use jq to filter out only those objects with a certain property equalling a given value

`select(.property==value)`

Thanks

6:56 PM

CMC: Output ^

@Pavel output all or get the nth element?

Either
Whichever is shorter

@Pavel SOGL, 8 bytes

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

7:05 PM

@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

CMC: `[19,17,13,11]`

7:23 PM

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

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

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

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

@Adám making a prime number generator..

7:26 PM
@dzaima Oh dear.
@Mr.Xcoder Nice.

@Adám Does the order matter, though?

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

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

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

7:27 PM
In pseudocode: `push(push(push(push(11) + 2) + stackHeight * 2) + 2) #implicitly print`

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

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

@Mr.Xcoder J, 7 bytes `q:46189`

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

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

7:39 PM
@Adám Jelly, 4 bytes: `⁵æRḤ`

Very straight-forward. Nice.

@Cowsquack Yup: `⎕A⍳'SQMK'`

`9+2×3~⍨⍳5`

@Cowsquack Ha! That's neat.

7:43 PM
What is this for?

@Dennis how does that work?

Ah, I see the CMC now.

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

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

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

7:59 PM
unhalves, hehe