The Nineteenth Byte

PyGamer0

3:00 AM

@mousetail and let your machines slowly break :P

NoHaxJustRadvylf

3:16 AM

YESSSSSSSS finally got a simple WebSocket chat program running in Rust

It's almost certainly extremely buggy (unwrap spam) and full of memory leaks though

Steffan

Nice

graffe

@Jonah hi

Bubbler

Memory Leak is Safe in Rust(TM)

graffe

Hi @Bubbler

Bubbler

For unwrap spam, I'd guess you can't do much other than writing out what might go wrong in each step (mostly "unexpected IO error" of some kind maybe?)

Hi

graffe

3:25 AM

Anyone got any views on codegolf.meta.stackexchange.com/a/25023/108721 please

I really want to check it isn't stupid/trivial etc before posting

Bubbler

You have the freedom of choosing one of four agents after every step, right?

graffe

@Bubbler yes

I'll clarify that, thanks

Bubbler

Also you might want to write your own basic strategy and check that it runs in a few seconds or minutes.

NoHaxJustRadvylf

Removed the memory leak and made sure all my unwraps are reasonable. Surprisingly painless.

Bubbler

Pushing a random walker to 20 can take pretty long

graffe

3:34 AM

@Bubbler if you choose one and just push that it should take about 400 steps

The reason it isn't too slow is that it always moves right at the origin

Actually slightly less than 400 iirc

@Bubbler thanks for looking at it!

Jonah

@graffe Hi. You should probably also stipulate that if two posts have the same strategy, the eariler one wins. Btw, maybe I am not fully getting it, but it's not clear to me why you wouldn't just always move the agent farthest to the right. And together with the "0 always move right" rule, also not clear to me why 4 agents would be any better than 1 agent?

graffe

@Jonah I will do that. Let me try to explain

If agent 1 has moved 10 steps but is at position 1 and agent 2 hasn't moved at all, it costs 11^2-10^2 to move agent 1 and 1^1 = 1 to move agent 2

So it looks like you should move the agent that is further away from 20

Jonah

ah, ok, i missed that

graffe

It was a very good question

Bubbler

If you have moved agent 1 twice but it is still at the origin (it moved right then left), you surely want to move another agent

which likely reduces the sum of squares in the end

Jonah

3:45 AM

Maybe a short explanation like that to the post. Anyway, now that i understand, I wonder if moving the agent whose expected final number of moves is least would be optimal?

graffe

@Bubbler yes

@Jonah added. Thanks

@Jonah maybe :)

Jonah

Rather, expected cost to finish from where he is now is lowest.

Bubbler

The actual problem is that calculating it is not easy

graffe

At least I don't know how to

Hmm... maybe it is computable in fact

I am tempted to post the challenge or shall I wait a bit longer ?

Steffan

I'd suggest waiting another day or more

Bubbler

3:56 AM

Maybe wait for a couple days

graffe

Ok I'll wait for at least 12 hours more :)

Thanks so much for the comments so far

Steffan

that must be quite an urge lol

Bubbler

The art of challenge writing is in waiting for feedback :P

Jonah

"The actual problem is that calculating it is not easy" @Bubbler Is that true? Is there not a closed form solution for the case of expected number of moves for a single agent at any position? Or at least a markov chain that boils down to multiplying a matrix some number of times? I agree calculating the solution to the overall problem would be hard (maybe impossible) to do exactly...

Bubbler

expected number of moves != expected cost when it reaches the goal

Jonah

4:04 AM

true, but from that you'd get a distribution of probabilites with tuples (numMoves, prob), with a tail that falls off fairly fast (I think), and you could use those to estimate with good accuracy for each agent "expected cost to finish from where he is now"

i guess i'm wondering if there is some weird unintuitive thing where "move the bot with lowest expected cost to finish from where is now" is not the same as "optimal move for the entire group"....

Unrelated String

iirc the expected cost is infinite, so there's a bit of a trick to that to begin with

:P

Jonah

So actually running it is effectively changing the mathematical question to something like "choose the strategy that has the lowest EV when restricting to trials that finish in fewer than N moves". Reminds me of the st petersburg paradox.

graffe

4:23 AM

@Jonah for hard probability questions we can often get very good answers by simulation of course

@UnrelatedString are you referring to symmetric randomly walks? My random walk reflects off the origin so the mean number of steps is definitely finite and computable

Unrelated String

oh does it this time

nice

i did not read the sandbox post clearly :P

graffe

:)

In fact now I want to know what it is exactly

Bubbler

It is almost certainly finite and likely it can be calculated as infinite sum but I'm too lazy to work it out right now :P

graffe

It quadratic iirc

Jonah

"the mean number of steps is definitely finite and computable" doesn't necessarily imply in the general case that the EV of the cost is finite though... eg, you could imagine some faster-than-exponential-growth cost function. But with your cost function pretty sure it is.

graffe

4:29 AM

@Bubbler :) if instead of reflecting off the origin you just stay still if you try to move left at the origin it is x(x+1) so it is a little less than that

That is the expected time to reach x from the origin

@Jonah yes you are right

I am glad my problem isn't trivial at least!

Jonah

i am still really curious if the greedy strategy of "move the guy with lowest expected cost to finish" is optimal. it's one of those things that seems "obvious" but i've been burned by before in probability.

DialFrost

Hi guys!

graffe

@Jonah please try it out!

@Bubbler in fact I think it is x(x+1)-1

Bubbler

I mean the formula would involve three variables if such a formula exists - the current position, distance to the goal, and the number of steps already spent

graffe

I was solving a much simpler problem. The expected number of steps from the origin to x

What does 3/4+5/8+7/16+9/32 +... sum to?

Jonah

4:46 AM

Here is one of the probability facts that absolutely blew my mind and why I will always be skeptical now of my intuitions.

graffe

2.5?

Bubbler

I think so

graffe

Thanks

@Jonah yes. probability is where intuition goes to die :)

New Posts

5:02 AM

0

Q: Golf python code?

I have this challenge to make a prime factorization tree, and I got this far with golfing it: b=int(input()) c=d=0 for i in range(2,b): if b%i==0:d+=1 if d==0:print('/ \\');print('1',str(b)) else: while b!=1: for i in range(2,b): if b%i==0:print(c*' '+'/ \\');print(c*' '+str(i),str(b//i));...

pxeger

7:36 AM

Why do I not get an inbox ping when a bounty is set on my question?

New Posts

8:48 AM

2

Q: Python: can I shorten this code further for checking substrings

So the golf question was like this: You are given a number T and then a total of T number of 17-character strings. For each of the strings, output yes if it contains four consecutive identical characters or contains the substring DX, else output no. The following constraints are promised for ea...

code-golf string tips python pattern-matching

emanresu A

9:05 AM

What's our consensus on incorrect answers in implementationless languages?

Adám

@emanresuA Two issues: Implementationless languages are not OK. Incorrect answers are not OK.

emanresu A

9:54 AM

47

Q: Highlight a Wordle guess

In Wordle, you try to guess a secret word, and some letters in your guess are highlighted to give you hints. If you guess a letter which matches the letter in the same position in the secret word, the letter will be highlighted green. For example, if the secret word is LEMON and you guess BEACH, ...

code-golf string game word-puzzle

Since when did this have so many updoots

mousetail

10:53 AM

Is there a compact way to find the coordinates of a point from a triagular number?

Like 1 = (0,0), 2=(0,1), 3=(1,1), 4=(2,0), 5=(2,1), 6=(2,2), 7=(2,3) etc.

Side length increases by one each time

emanresu A

Let me guess: This is for weekgolf?

mousetail

Yes

emanresu A

I think I can create a formula, one moment

If t is the number, k = sqrt(2t-1/4) - 1/2, the y is floor(k) and x is t - T_y where T_x is the nth triangle number

Kinda bulky tho

Unrelated String

if you can get the greatest triangular number =< it you can just divmod by that i think

after decrementing

er wait no

fuck yeah this does seem like it should be fairly simple somehow but that ain't it

Sandbox Posts

11:19 AM

0

A: Sandbox for Proposed Challenges

Polyglot quiz code-golfcops-and-robberspolyglot In this challenge as a cop you will choose two programming languages A and B, as well as a non-empty string S. You are then going to write 4 programs: A program which outputs exactly S when run in both A and B. A program which outputs S in A but n...

graffe

12:19 PM

Hello all!

lyxal

hello there!

graffe

Anyone got any comments about codegolf.meta.stackexchange.com/a/25023/108721 ?

Please :)

lyxal

why isn't the strategy just to move one bot repeatedly until it reaches 10?

because moving other bots means you might be wasting moves

graffe

@lyxal great question. Imagine you move the first agent twice and
it returns to the origin

You now want to move any of the other ones as they are cheaper

So it's not so simple

lyxal

wait wait the cost to move each individual agent goes up each time?

graffe

12:28 PM

Does that make sense?

@lyxal see the scoring system

And the example in the "why isn't it trivial" part

mousetail

@emanresuA Thanks

lyxal

@graffe That wasn't immediately obvious to me that there was a cost to moving an agent, and that the cost increases each time

but it does make sense

graffe

@lyxal what can I add to make this clearer? I was hoping the "why isn't it trivial" section covered it

lyxal

let me think on that for a second

> It is tempting to think we should always move the agent that is closest to 10. However, if agent 1 has moved 10 steps but is at position 1 and agent 2 hasn't moved at all, it costs 11^2 - 10^2 and 1^1=1 to move agent 2. In this case it looks like you should move the agent that is further away from 10.

Shouldn't the cost to move agent 1 be 11, not 11^2?

graffe

It was 10^2 and it is now 11^2

So the cost of the move is the difference

lyxal

12:35 PM

why is it squared though?

graffe

Look at the scoring system

It is the sum of the square of the total number of moves of each agent

lyxal

> The cost is the sum of the square of the total number of moves (left or right) taken by all four agents until the first agent gets to 10. You want to minimise the expected cost

all four agents seems to be a little confusing here

"each individual agent" might work better

graffe

How would you clarify it?

Ok

lyxal

other than that, I like the idea!

graffe

Thanks!

I applied your edit

I'll post it in about 6 hours from now I think

I would like to know the average you get by always moving the agent closest to 10 but I am on my phone currently

lyxal

12:40 PM

the scoring system makes me nostalgic for a KoTH I once answered - it was rock paper scissors but you could inspect the opponent's code. The riffing on other people's strategies and incremental improvement this challenge should have reminds me of it :)

graffe

@lyxal that sounds cool!

If you had time to implement it...:)

lyxal

9

Q: Rock Paper Scissors Meta-Gaming Tournament

This is a rock paper scissors competition. Algorithms will face each other in 100 rounds of rock paper scissors. Except that the algorithms will also be able to read the source code of each other! Leaderboard 1. Chaos Bot (by Aiden4) - 27 Points, 168 bytes 2. Anti-99%-of-posts (by Lyxal) - 24 Poi...

king-of-the-hill

@graffe give me a second

graffe

Thanks!

thejonymyster

i love seeing "Chaos Bot" at the top

graffe

What is it doing to win?

thejonymyster

12:43 PM

haven't gotten that far :P

graffe

:)

thejonymyster

tbh i dont actually know what most of these bots do :/

lyxal

@graffe 1000 games will take a while to run, but (if my implementation is right), the average of 10 games is 176.6

vyxal.pythonanywhere.com/…

it's not every day I get to write literate vyxal :p

mousetail

@emanresuA I figured out how to at least iterate over them using " i++-j||(i-=++j) "

lyxal

@thejonymyster well I can explain what the "Anti-99%-of-posts" bot does - it just checks for certain characteristics within the source code of the bots and returns the winning letter

I know this because I wrote it :p

thejonymyster

12:54 PM

that feels like the only answer lol

lyxal

well it kind of is

it's basically answer-chaining with the possibility of future-proofing

but it's still my favourite KoTH ever

@graffe for your challenge idea, I think 1000 runs is too many

it'll take too long

100 might be more reasonable

because even that takes a few minutes

I ran it 100 times and printed averages at 10 runs:

⟨ 10 | `5.3` ⟩
⟨ 20 | `5.65` ⟩
⟨ 30 | `8.7` ⟩
⟨ 40 | `2.625` ⟩
⟨ 50 | `1.38` ⟩
⟨ 60 | `8.216666666666667` ⟩
⟨ 70 | `2.0714285714285716` ⟩
⟨ 80 | `2.2625` ⟩
⟨ 90 | `0.32222222222222224` ⟩
⟨ 100 | `0.49` ⟩

graffe

1:41 PM

@lyxal those numbers are much too low

@lyxal also it should be quick. About 100 steps to get to the end

How do you get numbers less than 1?

lyxal

I honestly don't know

graffe

Are you squaring the total numbers of steps of each agent and adding these up and do they always all start from 0?

The fact your code is so slow also suggests a bug to me

graffe

1:59 PM

Hi @Adám

Adam

Hello

thejonymyster

is this a dupe of this? IMO it's pretty close, definitely a related tag if not a dupe, but there are some differences worth note

Adam

I just came to ask if people could look at codegolf.meta.stackexchange.com/a/25019/113573 and say if the challenge has been done before

graffe

@Adam its built in in python

Well itertools

thejonymyster

Wow do we actually not have a straight "output all permutations" challenge

Adam

2:03 PM

We do, actually

Adám

@graffe Hello.

thejonymyster

@Adam oh, then I don't see what "generate the range yourself" adds to it, but also i'd like to see the challenge we do have since I can't find it for some reason oops

Adam

10

Q: Output all distinct permutations of a vector

Challenge: Output all distinct permutations of a, potentially long, list of positive integers. You may assume that the vector has less than 1,000 numbers when testing, but the process should in theory work for any vector with more than one number regardless of size. Restrictions: You must res...

code-golf number permutations restricted-complexity restricted-time

thejonymyster

ok well the fact that itll never have any duplicates is important imo hm

Adam

True

thejonymyster

2:07 PM

maybe adopt the sequence rules too?

not sure if that makes sense though actually xd nvm

graffe

@Adam do you have a moment to implement a naive solution to my sandboxed challenge? I feel it should be fast but some concern has been expressed that 1000 is too much

Please :)

thejonymyster

random thought: search for -[tagname] tagname for a list of questions to potentially retag lol

Zion mycelia adamancy

2:38 PM

@Adam This also has restrictions on time/complexity

Adam

2:55 PM

@graffe I have work I should be doing instead, but onecompiler.com/python/3ycdt728e

Which gets an average score of 7932.101

Wheat Wizard

3:21 PM

CMQ (chat mini quiz): What is the rule for the following sequence: [1,11,111,1111,11111,111111,410256,1111111,11111111,111111111,1111111111,111111111111,410256410256,1111111111111,8101265822784]

PyGamer0

@WheatWizard how about cmz for chat mini quiz

Wheat Wizard

Hm, I think that overlaps with "Chat Militarized Zone"

Adam

CMExam? CMTest? CMAssessment?

Zion mycelia adamancy

@WheatWizard Is that what happens when two chat rooms brigade each other? :P

thejonymyster

3:39 PM

radvylf would know all about that

PyGamer0

lol

i just found out the relationship between a polynomial's coefficients and roots and its beautiful

thejonymyster

4:04 PM

well what is it :P

graffe

@Adam thank you!

Seggan

@PyGamer0 the quadratic equation?

graffe

4:24 PM

Challenge set!

@PyGamer0 now you have to tell us what you have learned!

PyGamer0

@Seggan any polynomial

@graffe i can't explain properly i will try tomorrow:P

o/

graffe

Shouldn't new challenges appear here?

@PyGamer0 cool

PyGamer0

@graffe (the bots are down so there are temporary feeds)

graffe

@PyGamer0 ah... I am not sure what temporary feeds means but

0

Q: Optimal strategy for wandering robots

Consider four agents sitting on four different number lines, all starting at the origin. In this game your only move is to choose one of the four agents to move. When you do that the agent you have chosen moves left or right by 1 with prob 1/2. You must choose which agent to move at each step. If...

code-challenge

I am doing the job of a bot :)

@Adam it looks like your code doesn't always move to position 1 from position 0.

NoHaxJustRadvylf

@graffe It means SE's default new post feeds are being used right now, which take like an hour to post anything

New Posts

4:44 PM

0

Q: Optimal strategy for wandering robots

Consider four agents sitting on four different number lines, all starting at the origin. In this game your only move is to choose one of the four agents to move. When you do that the agent you have chosen moves left or right by 1 with prob 1/2. You must choose which agent to move at each step. If...

code-challenge

graffe

@NoHaxJustRadvylf ah ok thanks

That was less than an hour :)

@Adam I fixed the code and increased the number of runs to 10,000. Otherwise the variance was too high. In fact it still might be a little high

Adam

@graffe Oops, sorry onecompiler.com/python/3yce446fp (Average 6748.854)

graffe

@Adam no problem. But try it without a seed again

I tried a fixed version of your other code with 10,000 and the true mean seems close to 6400

@Adam I have to comment out the print statement in the loop to get it to run with 10,000

PyGamer0

@thejonymyster @Seggan @graffe dzaima.github.io/paste#0dY9NS8QwEIbv/…

^ the thing

DLosc

5:07 PM

@NewPosts Disappointing that this is far too specific for QBasic to handle. I'm tempted to write a knockoff question that doesn't require inputting a color or handling transparency.

graffe

@PyGamer0 that's cool!

DLosc

@pxeger The holiest language is clearly Perl. I don't see why we need a new one. ;P

graffe

@DLosc wow!

@DLosc can't you mimic transparency in code?

DLosc

5:51 PM

@graffe In general, yes (though I'm not sure whether that question allows it; I didn't read it very carefully). However, QBasic basically only has 16 colors.

graffe

6:02 PM

@DLosc do you get to choose a palette out of which you can use 16 colours?

Has anyone got a working computer they could run onecompiler.com/python/3yce446fp on with num_cases set to 100,000 please

You can't do it in that online system

(maybe delete the random seed line too)

Managed to run it in colab

Added a target mean cost to beat

thejonymyster

6:26 PM

challenge concept idea: all slices of a list which include that slice's length

graffe

6:45 PM

@att hi

att

hi

graffe

I didn't understand what sort of information you were thinking of

att

for example, if you have no history

graffe

You mean at the start?

att

I mean if you cannot take history into account when selecting a move

that obviously would change things

graffe

6:49 PM

Oh right. Yes you can

You can do what you like basically as long as you don't cheat :)

Sandbox Posts

0

A: Sandbox for Proposed Challenges

Longest N-Sum Sub-Array Write a program or function which when given an array of non-negative integers and a number N, output the longest contiguous sub-sequence of said array whose sum adds up to N. Constraints If there are multiple such sub-sequences, output any of them or all of them (duplica...

graffe

@att if you can beat the score I have in the question that is already great

@att Do you have any ideas how to do that?

thejonymyster

wow one of you needs to get an icon i thought one of you was talking to yourself :P

att

it's not our fault SE gave us similar shades of green

graffe

:)

graffe

7:28 PM

I don't understand ruby. Is this don't 10,000 iterations ? tio.run/…

emanresu A

,.;.l]]]]];pl
"AFGDCXCFB

Sorry, cat on keyboard

thejonymyster

no, keep them on, i like what they had to say

DLosc

7:53 PM

@graffe I think maybe in theory? I've never figured out how to have more than the standard 16 in practice. Part of the issue is that QBasic's graphics commands are specific to the type of display hardware you're using, so not all of them are usable on any given setup, and I'm never sure how they're going to map to a modern setup.

graffe

@DLosc ah ok

The first answer to my challenge is amazingly good

I am constantly impressed by how clever people are here

NoHaxJustRadvylf

8:25 PM

@emanresuA I wonder if you could use footstep-width-to-cat-size statistics to estimate your cat's size (and age) based on those keystrokes

I know you can estimate someone's height based on the distance between their footsteps, so maybe you can do that with cats

New Posts

8:54 PM

-1

Q: Find number components with lowest distribution in Javascript

Let us assume that we have number X. Let us assume that we have components (C) of this X number. We can add these components together like C1+C2+...+Cn = X. We have N as limit of number of components. We have B as limit of biggest component Examples X = 17 N = 3 B = 8 Then possible component ...

code-golf integer javascript

Adam

9:05 PM

@graffe I ran a modified version which may or may not be faster (because that version is clearly not optimized for speed), and after a million iterations I got an average of 5427.119384

The modified code is onecompiler.com/python/3ycemc9hf, in case you are curious -- there are probably other changes one can to speed it up, but whatever

graffe

9:24 PM

@Adam nice improvement! You should post an answer

NoHaxJustRadvylf

I made a thing, it's a chat program where what you type is streamed live instead of being broken up into discrete messages

8

Adam

@graffe It's literally the same exact code, just slightly faster lol

I'm considering posting it as a reference point... I don't have strong feelings about it

emanresu A

9:45 PM

@NoHaxJustRadvylf I changed my name to <script>alert(1)</script> and now it's broken

NoHaxJustRadvylf

No, it just wasn't allowed as a name and I totally forgot to handle that situation in the front-end

thejonymyster

@thejonymyster CMC: given a list of posints, return every contiguous slice of the list which includes the length of that slice. example: [2, 1, 2, 3, 4, 7] => [[2, 1], [1], [1, 2], [2, 3], [1, 2, 3], [2, 3, 4], [3, 4, 7], [1, 2, 3, 4], [2, 3, 4, 7]]

DLosc

@thejonymyster Brachylog, 4 bytes (generator): s.l∈

thejonymyster

wowy!

DLosc

Literally "the output is a contiguous sublist of the input and its length is a member of the output"

thejonymyster

9:54 PM

i figured a logic lang would be a good choice lol

DLosc

@thejonymyster Pip -xp, 19 bytes: #_N_FI_MFa@$\,GMC#a

Most of that is generating the sublists, since Pip doesn't have a builtin for that. Probably can be golfed further.

DLosc

10:12 PM

@thejonymyster BQN, tacit function, 16 bytes: (⊑≠∊⊢)¨⊸/·∾´↓¨∘↑

Zion mycelia adamancy

10:42 PM

@thejonymyster Jelly 5 bytes

Lit. sublists, filter on "length is in?"

hyper-neutrino

@thejonymyster Vyxal, 6 bytes: ÞS':Lc (Try It Online!)

literally what caird did, but "get all slices" is 2 bytes in vyxal :P

and requires a duplicate (:), otherwise this would actually be shorter cuz of the filter lambda auto-closing saving a byte over jelly needing grouping

wait actually, Vyxal, 5 bytes: ÞS'Lc (Try It Online!), because the : isn't needed :P

thejonymyster

11:09 PM

yay!

Adam

I'm trying to think of a graph-theoretic approach to the "wandering robot" problem, but I don't know if tiny brain is capable

The main issue is that, e.g. a graph where each node represents a state of the "board" would be infinite

Steffan

11:31 PM

@graffe Yes, that's 10,000 iterations

@NoHaxJustRadvylf Where on earth are u supposed to type

Adam

11:48 PM

@Steffan The top bar

lyxal

@NoHaxJustRadvylf very epic mobile support

Definitely lets me get past the username selection screen

Totally doesn't just not recognise that I'm pressing enter

Steffan

@thejonymyster Python, 77 bytes: lambda a:[a[x:y]for x in range(len(a))for y in range(len(a))if y-x in a[x:y]]

@Adam Oh. It's confusing because there's no input box or cursor in the input, you just have to hammer on your keyboard

Also, I was looking at the left of my screen, not the right lol

Transcript for