algos-and-data-structs

[worthy spoke]

hi

[cloud timber]

Im currently taking DSA and even though I’ve been practicing a lot of problems I feel like I still am having problems coming up with solutions

Im struggling to imagine how to apply pointers and the over all thought process for dsa

Does anyone have an recommendations on maybe where Im going wrong

(I also have an exam on tuesday and I really want to get a high grade)

[opal oriole]

Are you nearing the end of the course or did you just start? Trying to get a better idea of where you are having difficulty.

Is the difficulty in giving any solutions at all, or for more advanced problems?

You mentioned pointers. Are you comfortable using pointers outside of DSA problems? Like just writing some app?

[cloud timber]

its my first midterm

[cloud timber]

so its very bipolar sometimes I can write out a solution in english but no python

somestimes

both

[cloud timber]

the concept of pointers makes sense to me but i can't always apply it

[opal oriole]

This combined with being able to write it in English but not Python indicates to me that you perhaps need more experience writing code in general, not specifically DSA problems. Do you have some side project(s) that you work on in your spare time? Such as making a TODO list terminal application or something like that (small projects).

[cloud timber]

No I dont

I learned python back on july

[opal oriole]

Ok, I would work through a bunch of projects, read through existing code, etc. You need a massive volume of code/projects to get enough experience such you can focus on the abstract problems of DSA and not the code itself.

[cloud timber]

I see

[opal oriole]

Simply following a course's work is not enough.

[cloud timber]

I see

BecauseI understand time complexities and runtimes

its just straight up solving specific problems

Is there really no quick solution?

[opal oriole]

No, there are certain periods in learning where it feels like no progress is being made, and can even feel like you are going backwards. It's just more grinding, more data (you need many examples to learn from, and to just go through them). But I can give some generic useful tips for DSA specifically. Although it's not very useful without that large volume of practice.

But being good at something requires doing it a lot, all the time.

[cloud timber]

I see

can you give me the general useful tips

Im considering taking a one day break and studying a bit more tomorrow for my exam

Because I have been doing a lot of data for the past 2 weeks

[opal oriole]

Yeah, I can give some random ones: ```

1. If stuck, instead of trying to solve the problem directly, go on a detour by solving different problems. One way of doing this is either just coming back to it way later, or asking yourself the more simple version of the same problem (by removing things that make it hard, but sometimes by adding something in).
2. Instead of giving the clever solution that is optimal, just give the simple bad solution first and write the code for it. That process will often reveal that you did not properly understand the problem.
3. The constraints/variables/properties given in artificial problems (made by humans, e.g. for an exam) are there for a reason. If your solution is not taking them into account to somehow exploit for a better solution, it's probably wrong.
4. The constraints given implicitly form an underlying structure that you must realize/visualize/understand to properly solve the problem. How you represent that structure can often be key, as a shift in perspective may be all you need to make the solution obvious.
5. Math is largely about what (4) is about, learn a lot math, as it gives you the tools to do that shift.
6. Does the problem have nice subproblems that combine together to solve the whole? This is what many problems are in practice in various forms, since programs are about doing a bunch of little things/operations and combining that into a final result.

A common stumbling block is recursion. https://www.youtube.com/watch?v=ngCos392W4w

As is dynamic programming. https://www.youtube.com/watch?v=aPQY__2H3tE

[cloud timber]

Thank you so much

[opal oriole]

Here is a big list of Python projects for you to get more comfortable with programming in general: https://inventwithpython.com/bigbookpython/

I recommend trying to implement it first, see how far you get, and then read through their code.

[opal oriole]

Oh, another random tip. Play around with simple concrete cases. So if the problem is to sort a list with N elements. Try messing around with a list of 1, 2, 3, 4, 5 elements and doing it on paper by hand.

Play around with it first, before writing a solution.

[cloud timber]

I see

[opal oriole]

Also to properly learn, as with tip (1) given, it's better to try to solve it, and if stuck, not look up the solution, instead realize you can't solve it yet and come back later. Solve something easier first (sometimes many problems needed before that one can be solved later).

If you give up quickly and look up the solution, you have wasted that problem for learning (you don't internalize the solution by just reading it, it gives the illusion of learning).

But initially, yes, you do need some examples.

[cloud timber]

Thank you I'll keep that in mind

[alpine bane]

I am confused why are there so many sorting techniques in general

[shut kernel]

Because shorting is hard and inefficient so different people explored different wants to do it.

[swift coral]

Sorting efficiency also depends on how mixed the input is. Sometimes an algorithm that is less efficient for homogenous data is better to use on almost sorted data than some other algorithms that work well on homogenous data.

[haughty mountain]

to be fair, quite few are actually useful

some are born as just variations on other ones, some are genuinely trying new stuff, and some from people just wanting to create some silly way of sorting

for useful algorithms there are only a handful I would say are useful to know about

• quick sort, merge sort, heap sort
• insertion sort

the sorting algorithms you'll see in actual use is largely some hybrid of some variations of those

[verbal oar]

IS there anyone who wwant to teach me the "way"?

[dreamy tulip]

Young padawan, you are the way.

[formal eagle]

bimbimbambim

[formal eagle]

which one wym

[verbal oar]

Nthing

[lilac cradle]

ez

[formal eagle]

fr

[fallow helm]

https://github.com/abderrahim-ai/TP_Pytho.git

[blazing snow]

move = wasd

[formal eagle]

auahahha

[still mulch]

Is there any way to master linked list those are my worst topics.. I came across leetcode puzzle of like copy list with random pointer and it was the worst I couldn't get over it for some reason I asked chatgpt and still couldn't get it and then checked the solution in the end and understood

[runic tinsel]

that sounds ideal

if you can keep doing that

you would understand all solutions

eventually

[still mulch]

Ohhhhh okk I guess I would learn linked list gradually 😭

[runic tinsel]

linked list means you have two options, look at the first element, or get a different list that doesn't have the first element but otherwise it's the same

so if you want to look at the 5th element, you do the second thing 4 times, and then do the first thing

[tiny briar]

Years ago I read a blog post about algorithms that said that all algorithms do one of three techniques one of which was called sliding window. Would anyone happen to know the other two?

I've never taken a formal dsa class so I don't even know where to start looking for this kind of thing

[narrow mica]

never heard of this tbh, the "all algos do one of three" part

[tiny briar]

It was a while ago I may be misremembering

Like almost 10 years ago

[empty echo]

Sliding window is a ratelimiting algorithm

[agile sundial]

"use graph theory" is a good guess

[haughty mountain]

Sliding window is a very general concept

[empty echo]

hmm, i guess I have only seen it in ratelimiting so far

[olive hazel]

how can i use claude code with notebooklm for free

[astral finch]

Which is the best YouTube channel for learning cybersecurity?

[blissful cypress]

https://discord.com/channels/267624335836053506/366674035876167691

[naive oak]

sliding window for ratelimiting and sliding window the algorithm technique are kinda two different things?

the ratelimiting method is a specific case i guess

[haughty mountain]

A specific application of the technique, afaict

[indigo loom]

Stack > queue

Hot take

[haughty mountain]

stack < deque > queue

[indigo loom]

I see what you did there

[regal spoke]

Another hot take
list should have O(1) append_left and append_right

[desert cedar]

Linked lists do, but i don't see how that would work for regular lists

[regal spoke]

One could easily apply the same trick that list currently use

To preallocate extra slots on the left side too.

That would result in a list being fast to modify both on the left and the right.

[cloud timber]

does anyone know a free website that teaches you data structures

I tried using neetcode and leetcode but thats all blocked with a paywall

[violet pier]

https://cs161-stanford.github.io/

[cloud timber]

tyy

[dreamy tulip]

I think you have just re-invented the deque.

[haughty mountain]

It's not how deques tend to be done

[regal spoke]

No. Typically deque is implemented as some kind of linked list, making indexing very slow

[thick granite]

if it runs out it will have to move the entire list though, right?

[regal spoke]

Thats how a list works to begin with

[thick granite]

i see

so just a less expensive way to .insert(0)

[regal spoke]

A significantly less expensive way, yes

[real whale]

Add a sound

[jolly mortar]

i believe julia's impl of Vector does this

O(1) pushfirst and popfirst

by overallocating on both left and right

[regal spoke]

Are you sure? I'm finding it surprisingly hard to confirm this.

Also, the fact that deque is a thing in Julia is making me doubt this fact

Had Julias vector already effectively been a deque, then there should not be any need for a deque

However googling Julia deque, I get something very similar to c++ deque

[jolly mortar]

https://github.com/JuliaLang/julia/blob/master/base/array.jl#L1161-L1179

[regal spoke]

Ohh seems you are correct

The "unshift" and "shift" operations

[tight cedar]

Julia instantly becomes the best competitive programming language

[jolly mortar]

countered by 1 indexing

well

[tight cedar]

damn

[jolly mortar]

ig a bunch of cp problems are 1 indexed too

[regal spoke]

How come AI tools think this is not a thing?

[jolly mortar]

i dont think the complexity is documented anywhere

i just remembered someone telling me this on the julia discord a while back

[tight cedar]

If you search Julia front insert vector the ai will say it is O(1)

but it didn't give any source

[regal spoke]

Why wouldnt this be better documented?

[regal spoke]

Google's search AI thing told me O(n)

[tight cedar]

I couldn't replicate it now for some reason

lol it says O(n) when I say vectors and O(1) when I say vector

[regal spoke]

Even when I explicity ask chatgpt/gemini to double check its answer. Both confirm it is O(n)

Maybe they are really sold on the idea that stored in contigiuous memory => append_left/pop_left is always O(n), or at least those are the vibes Im getting

[stiff quartz]

Idk why but my GPT seems to get it

I don’t ask it to do anything like I didn’t enable thinking nor did it enable web search and it still goes on to look at the source code itself

It’s getting good

[regal spoke]

You hinted it the answer

Thats not a good way to prompt an ai

[stiff quartz]

Even if you give a wrong hint it gets it tbf

[regal spoke]

thats still arguably a hint

[stiff quartz]

Well less than saying « double check please »

Sometimes it doesn’t bother going online

And gets it wrong

[stiff quartz]

With the same prompt lol

[crystal smelt]

https://github.com/BlackCatOfficialytb/CatFind-Lib

som1 review it plz

[swift coral]

<@&831776746206265384> spam/scam message. Feel free to delete my message too

[lusty crest]

True python:

I64 A[200005][20],B[200005],C[200005];
U0 (){I64 T=GetI64,N,I,J,P,L,S,V,W,X,Y;char Z[64];
for(;T--;){N=GetI64,I=1,P=1;while(P<N)I++,P*=3;
for(L=0;L<N;L++){for(S=0,P=L,J=0;J<I-1;J++)A[L][J]=P%3,S+=A[L][J],P/=3;
A[L][I-1]=(300-S)%3;}Print("%d\n",I);
for(J=0;J<I;J++){for(V=0,W=0,P=0;P<N;P++)A[P][J]-1||(B[V++]=P+1),A[P][J]-2||(C[W++]=P+1);
Print("%d",V+W);for(P=0;P<V;P++)Print(" %d",B[P]);for(P=0;P<W;P++)Print(" %d",C[P]);Print("\n");}
Yield;GetS(Z,64);for(P=0;P<N;P++){for(X=1,J=0;J<I;J++)
Y=(Z[J]-76?Z[J]-82?Z[J]-78?-1:0:2:1),X&=Y<0||A[P][J]==Y;
if(X){Print("%d\n",P+1);Yield;break;}}}};

None of u will ever know

The peace

[radiant birch]

can someone explain me why does 1100 & 1 give 0 here?

>>> 1100 & 1
0
>>> 1100 & 1000
72
>>> 1100 & 0001
  File "<stdin>", line 1
    1100 & 0001
           ^^^
SyntaxError: leading zeros in decimal integer literals are not permitted; use an 0o prefix for octal integers
>>> 1100 & Oo1
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
NameError: name 'Oo1' is not defined
>>> 1100 & 0o1
0

[tight cedar]

because 1100 is even so the last bit is 0?

[thick granite]

this looks suspiciously like C and not python

[lusty crest]

because it is holy C

“True python”

[burnt swift]

has any one have an idea of a tech startup

[worn oyster]

make a hammer app which has a hammer pic in it so people could use it nail the nails in wall

[regal spoke]

That error message is not missleading since you want binary numbers. What you should be using is the 0b prefix

>>> 0b1100 & 0b1000
8

Infact, it is weird that python's error message suggests to use octal integers. I think the probability of someone actually wanting to use octal integers when they write 0001 is quite low.

[haughty mountain]

It's not weird, it was allowed syntax for octal that was later removed

[regal spoke]

What was the syntax, just a leading 0 or multiple 0s?

[haughty mountain]

just a leading 0

though probably multiple leading zeroes was allowed

I expect the parser just goes "this looks like leading zero octal, that's not supported anymore" and errors

[lilac cradle]

https://www.youtube.com/watch?v=ldxFjLJ3rVY
anyone know how you can actaully implement this to get the shape they get?? i cannot replicate it

im converting the pixel coordinates to a complex number and taking the log, then scaling it back up to image size and i do not get anything remotely like this

https://paste.pythondiscord.com/VTPQ

[haughty mountain]

log is only part of it, right?

[lilac cradle]

maybe but i cant figure out what they’re doing to get the effect

[haughty mountain]

are you just looking at doing the first step in the transformation?

do you have a good test image?

[lilac cradle]

i used the same as they did and looked at their github and it seems to just be ln(z)? but their code is weird

[haughty mountain]

random fun fact, I watch a talk on this topic from one of the authors many years ago

Bart de Smit

[haughty mountain]

So the first step going from rectangular to logarithmic is something like

import cmath
import math

from PIL import Image


def zmap(z: complex):
  return cmath.exp(z) 

im = Image.open('droste2.png')
px = im.load()
w, h = im.size
sz = 3.0
def sample(x: float, y: float):
  ix = round((x/sz + .5)*w)
  iy = round((y/sz + .5)*h)
  assert px is not None
  if 0 <= ix < w and 0 <= iy < h:
    return px[ix, iy]
  return 255, 0, 255

out = Image.new('RGB', (w, h), (255, 0, 255))
px2 = out.load()
sc_x = math.log(16)
sc_y = 2*math.pi
off = -sc_x/2, -sc_y/2

for y in range(h):
  y_ = y / h * sc_y
  for x in range(w):
    x_ = (x / w - 1.0) * sc_x  # Offset here is arbitrary, effectively controls zoom.
    z = complex(x_, y_)
    z2 = zmap(z)

    x2 = z2.real
    y2 = z2.imag
    px2[x, y] = sample(x2, y2)

out.save('log_map_img.png')

starting from

[haughty mountain]

@lilac cradle I did manage it, but the logic is funnily backwards

(and I really need a higher res image)

https://paste.pythondiscord.com/FIIQ

when tracking where a pixel in the final image should be sampled from, you need to undo the transformations in sequence

undo the exp, then undo the rotation/scaling, then undo the log

[lilac cradle]

sweet

thanks

[haughty mountain]

I also did some fun to sample the image a bit nicer, when you sampling from within the nested image, rescale and recurse

[round jungle]

hello, is there any one who is good at proogramming actually and ca, help me to learn fast with som free courses???

[unreal swallow]

!learn from one of the recommended resource below 👇

[halcyon plank]

Go-to beginner resources

Here are the top free resources we recommend for people who are new to programming:

• Automate the Boring Stuff — an online book (also available to purchase as a physical book)
• Harvard’s CS50P course — video lectures (slides and notes provided) with exercises
• Python Programming MOOC 2026 course — text-based lessons with exercises
• Corey Schafer's YouTube playlist

For a full, curated list of educational resources we recommend, please see our resources page!

[oak cypress]

Any resources for learning MIPS assembly?

[candid parrot]

can someone with a better rig than me run a simulation code?

its for theoretical physics

[proud geode]

https://tube-sciences-technologies.apps.education.fr/w/bd31a30a-26a8-4f13-811f-129517b2254e
I found this on Peertube, a general-purpose database simulation engine. Pretty impressive for people their age.

[glacial basin]

I’m currently a half time Phyton scripter this is my first time for hire I have projects I can show you and I am for hire if you want to hire me or have problems you can ask me

[limber lintel]

Yes

[candid parrot]

im gunna have to get back to ya, managed to consolidate that one, but im sure it wont be long till the hands needed, mind if i drop a contactline

[limber lintel]

Alright 👌

[fiery cosmos]

gfhycrtseqwtyruti

[toxic junco]

Is double-imports something I should handle when working on a library where I expose a singleton?

I can't think of a reasonable case where the library would be mistakenly inconsistently imported - once via absolute import and another time via relative import

maybe in the context I have it in right now, which is that I keep it under src/lib as opposed to src/project_name which is the consumer project

also what's a preferred way of making singletons in python?

overriding __new__() and __init__() or exposing an instance in __init__.py?

[olive hazel]

why AI is useless to guide me in learning cs

[austere sparrow]

all modules are singletons and are cached

so if you import it twice, it's the same module

[toxic junco]

yeah I guess all non-standard import methods that actually cause duplication shouldn't be handled in the library

like importlib maybe

[olive hazel]

is there here any faang employee

[nimble canyon]

Rather than a prebuilt eviction algorithm, i made a dynamic eviction system based on temporal and relational clustering, tracking relationships across entries and types and using that for prefetch accuracy. Would that be appropriate for this chat?

Its inspired by ARC and does use the eviction algorithm as a helper. Its based on contextual frequency vs recency rather than frequency vs recency

[stone garnet]

hello friends .
Actually Iam in begein in my programming carrer,i learn well the foundation of python and i apply these simple project like calculator ,etc . can anyone share with me what's next?

[pure crater]

watchu need

[fading rover]

Try to build something async, like parser for website from scratch(with something like aiohttp and bs4)

[shrewd lynx]

I know this is a longshot, but, does anyone know how to contact the maintainers of onlinejudge. org? (UVa Online Judge)

I know the site is still live and people are submitting solutions, but I cannot login or recover my password. When I try to reset my password, I never get the email, nor is it in my spam filter. I have also tried to create a new account and have had a few different friends that have tried. None of us ever get the email with the account information.

I have also submitted to the "contact us" webform, however, I suspect that it also might not be working as I did not get a "confirmation" email.

I have been trying to figure this out since early January and cannot seem to get this squared away. Thanks!

[flint lodge]

Hey, how do i learn DSA the right way?, when i get a resource to learn, i discover more strange topics that i didn't see from the previous resource

[stiff quartz]

#algos-and-data-structs message

[blissful cypress]

That class is good but has a high math pre-req

May not be the best first pass at DSA for a lot of people

[blissful cypress]

How long have you been programming?

[nimble canyon]

I think i finished my cache design. My render speed has increased 12x from cold render to cached render. Is anyone else working on a cache system or is interested in talking about my design?

[jade kelp]

hey guys, i built this visual cheatsheet for dsa leetcode prep, if you're looking for a pattern-focused cheatsheet check it out and lmk if there's more i should add? 👉 https://github.com/maryamtb/rook/tree/main/community-notes/dsa-python

[main pagoda]

hey guys, i was wondering if anyone has any experience in making a robust monte carlo simulation to test theirs or another's trading strategy, i have made one but am looking for a bit of advice on how too make this more robust and more testing, thank you!

[haughty mountain]

(this reads like an ad)

[shut breach]

given {a, b, c} and {1, 2, 3} and there exists an unknown bijection between them
and a set of possible mappings for each e.g. a: {1, 2} b: {1, 2} c: {1, 2, 3}
you can reduce possibilities, e.g. conclude that c: {3}

is there a name for that reduction problem/algorithm?

[opal oriole]

https://en.wikipedia.org/wiki/Constraint_satisfaction_problem

See domain reduction as a way to solve this.

The most simple and straight forward way is search with backtracking. Assign some value to a from the set of its possible values, then assign some value to b from its set (note that b can't be one that was already taken, so its set (domain) shrinks as some value is chosen for a), then for c. If you get to say, c, and its set is empty, then the choices so far can't work, so you backtrack and try another.

This is trying all combinations but tracking the sets / reducing them.

In more complicated setups, choices taken affect the set of more than 1 variable. For example in game world generation it's common to use this method. For example having a grid world (tiles) and each tile has a set of possible values it can take (templates), and once one is chosen, the neighbor's sets reduce to values that can be adjacent (so the choice affects 4-8 other neighbor tile sets). This choice then affects the neighbor's neighbors too possibly, in which case you have a constraint propagation algorithm.

[shut breach]

i meant like problems where the constraints are only the given domains and the goal is to reduce the domains like in the example i gave

i think i was thinking of gaussian elimination

[opal oriole]

If you do exhaustive search you can find all valid assignments, that then tells you the sets of each variable.

[opal oriole]

What is the idea there?

[shut breach]

not sure, i'm trying to remember things i used to know about linear algebra

[opal oriole]

Are you thinking of integer linear programming?

[shut breach]

hmm i dont think so

[zenith crow]

​Coding against the odds in Gaza 📱💻
​My name is Omar, a self-taught Python developer and programmer from Gaza. I lost my laptop during the war when my home was bombed, but my passion for technology remains unbroken.
​I am currently using my phone to write and debug Python scripts, and I have recently started my journey into Cybersecurity. However, my progress is significantly hindered because I don't have a laptop to run the necessary tools and environments.
​I am looking for any organization or person who can help me acquire a laptop so I can continue my technical education and build my future in the field of Cybersecurity.

[haughty mountain]

I found
https://www.andrew.cmu.edu/user/vanhoeve/papers/alldiff.pdf

[shut breach]

ty 👍

[trim thorn]

Guys, do anyone have a list of best problems on arrays and strings (from basic to advanced) ?

[deep snow]

Try leetcode ig

[safe hinge]

Does anyone know how to cut Quiescence Nodes efficiently for a chess bot? Currently I'm getting about 6 times more qnodes than normal nodes in the evaluation tree and I feel like I could really cut that down

[jade lantern]

Currently starting on data structures, any hints on how to sort a txt file into a list, the split() function is required when I write the code. unfortunately the editor will only accept the format of python v3.13 or older...(thanks coursera) any help would be appreciated.

[sly nacelle]

is there a big list of calc/stats algos/models (physics/engineering/quant)?

[weary gyro]

Is there any chance that i can discuss about and talk about like brainstorm about the question I'm praticing about on leetcode like im totally a newbie and i don't want to talk to claude or deepseek and got direct ans to that question and enjoying solving question that i didn't solved actually.

[austere sparrow]

what question are you struggling with?

(it's usually better to ask the full question from the start)

[thorny gorge]

i am learning dsa using python , while exploring the array and the type code used while using them is bit confusing, can anyone explain them with suitable example for each type code of it

[zinc mountain]

While it can be explained, a LLM or any resource on the sites like RealPython would explain it better, with better examples.

[trim atlas]

Hey, has anyone ever coded anything in finance and quantitative finance? I have some question to ask about the topic!

[fading rover]

Just fucking ask

No one going to wait for u

[trim atlas]

Just fucking relax

[trim atlas]

Then don’t go ahead with your day

[fading rover]

Ask in python-help

They like interesting questions

[thorny gorge]

Will look into it , thank you @zinc mountain

[bronze gazelle]

Because it's new

[scenic mason]

coolio

[opaque portal]

oh wow epic

first message 😎

[royal kestrel]

I'm having some trouble with octal numbers

[scenic mason]

shoot

[fiery cosmos]

[frank nest]

🤔

[bronze gazelle]

Yes, the channel exists, we don't need to spam it with emojis

[clear plaza]

sorry boss

[main flower]

yes

[gusty grove]

oh awesome! i love this new channel!!

[odd pelican]

looks like an interesting channel

[ionic niche]

oh hey, just as I was creating a binary tree in python, this channel pops up

what a coincidence

[whole wadi]

@ionic niche excellent, do let us know if you need help in anyway with it. Except at 12am EST, as I and many others will be busy at that time lol

[tender wedge]

so guys and gals, how to calculate complexity of Advent of Code part 2 if you did it recursively

i always suck at guessing them whenever it include recursion

[gusty grove]

well the summing part will always be O(n). but lets take a look at the rest.

[plain ocean]

@whole wadi why 12est?

[gusty grove]

this is the graph for how many times you have to call recursively for the number n

@tender wedge it seems to do these jumps. no idea why really lol

this is a resolution of 1 so i expected something smoother tbh

[tender wedge]

Only 8 times wow

[gusty grove]

at the end its actually 9

for numbers until 10_000_000 with a resolution of 10

[turbid zephyr]

Aren't those jumps just going to be where the input becomes 3**n or greater?

Or 3**(n - 1) 🙂

[gusty grove]

hmm maybe

also you dont have to worry about exceeding the max recursion depth. that happens at around 1.79769e+308

[stark summit]

(this may be off-topic but) what's the time complexity of //? it's a / with a int() right?

[gusty grove]

no! its way faster

[stark summit]

hmmm

[gusty grove]

i posted a comparison earlier today in #517745814039166986

let me repeat it real quick 🙂

[stark summit]

cause in ruby / is //-like behaviour so that might be a built-in thing

[gusty grove]

%timeit 5//3
12.4 ns ± 0.655 ns per loop (mean ± std. dev. of 7 runs, 100000000 loops each)
%timeit int(5/3)
164 ns ± 1.59 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
%timeit int(5.0)
161 ns ± 3.62 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)```

[stark summit]

oh okay

[gusty grove]

// is actually just as fast as /

%timeit 5/3
12.1 ns ± 0.639 ns per loop (mean ± std. dev. of 7 runs, 100000000 loops each)```

[stark summit]

oh wow

oh okay it's a C thing

https://stackoverflow.com/questions/3602827/what-is-the-behavior-of-integer-division

[whole wadi]

@plain ocean advent of code my boy!

[gusty grove]

@whole wadi hm?

ah i see

@turbid zephyr how would 3**(n-1) be different from 3**n?

the first jump is between 6 and 23 so that would be a power of 3 difference!

[turbid zephyr]

The n I was referring to was the recursion level, I realized afterwards n had been mentioned as the input.

[gusty grove]

the next one is 24-81!

ahh

ok that makes more sense

yup looks like you are right

which means you can write a just as efficient iterative solution!

[turbid zephyr]

I'll use k instead 🙂 I just figured because we're dividing the number by three k times. It would be 3**k.

[gusty grove]

yeah, i had a hunch it was something like that but just couldnt think of anything haha

[turbid zephyr]

I forgot about the subtracting 2 though, so not sure if that has an impact 🙂

[gusty grove]

to figure out how many times you have to call the function you can then use log(n,3)-1

@tender wedge ok! so that function follows int(log(n,3))-1

so your time complexity should be O(log3 n)

[tender wedge]

Ahah thanks

I was thinking of this just because it's /3 but i wasn't sure cause i'm bad at math and no CS classes

[gusty grove]

i've never taken a single cs class 😉 thats not a excuse!

[tender wedge]

Ahah

Alright

[gusty grove]

or a uni math class for that matter

in blue the actual value, in green log3(n)-1 and in orange log3(n)

[half lotus]

can just be logn

[gusty grove]

are you allowed to generalize that much?

[half lotus]

I believe yes because the intent is to describe how a function grows rather than to what extent

[gusty grove]

ahh ok

[half lotus]

But please anyone correct me if that's wrong

[gusty grove]

i think you are correct

[half lotus]

cause log3n = log10(n)/log10(3)

so log10(3) is a constant

[gusty grove]

ahhh

yeah makes sense

i knew you were allowed to leave constants away, just didnt think of log3 that way

[lusty vault]

you omit the base ftr

since log_n(x) = log_e(x)/log_e(n)

so you change it to ln(x)

[gusty grove]

yeah mark said that

[tender wedge]

I feel like log2 and log10 grows very differently though, enough to precise it ?

Apparently not :0

[half lotus]

Yup the shape of the function is still logarithmic

a base of 3 would mean it grows about twice as fast as base 10

it can just be though of as a transformation on the function

[fiery cosmos]

Hi

[dark moss]

So for this part of the chat

if i'm doing OOP in my c.s undergrad with cpp and I'm on a concept like polymorphism, it's appropriate to ask questions about a concept like that in this specific channel?

[low palm]

I'd think concepts like polymorphism falls under "general computer science". Go ahead 🙂

[dark moss]

Oh not yet haha

I'm actually in my introduction to programming

but I read next semester's topics and heard polymorphism and pointers give students some trouble

when I go on break, I would like to practice it, and then I will definitely return

[low palm]

Sounds good! Welcome back anytime ^_^

Python is pretty much all I know. But if this is not going to be a discussion about computer science, we're in the wrong channel

[dark moss]

oh right

[main flower]

Could somebody explain why

a = []
b = a
a.append(1)

This changes the list b, but this

a = "Hello"
b = a
a += " world"

doesn't change the b string?

[half lotus]

because a string is an immutable type

any modifications results in a new object

[main flower]

Hmmm

Ok

[warm marsh]

https://nedbatchelder.com/text/names.html might be an interesting read to understand the concept

[outer lake]

There's also a video on the topic from nedbat: https://www.youtube.com/watch?v=_AEJHKGk9ns

[acoustic fox]

Oh cool! The system works!

Going though computer science 101 book learning big o notation. I will contribute soon

[placid sun]

Hello, I have a question , I want to code a L - game . It's a table game with 2 tetris L pieces that you move turn by turn in a grid (with 2 neutral pieces ) . A player wins when the other one cannot move it's piece. If I want to check if a player won, I thought about checking every position his piece can take and verify if it is occupied by something or not.

Is this the only way to verify if someone won ?

Thanks in advance ^^

[weary obsidian]

Literally a week late to the big O notation chat but yeah, you strip all the constants out, so log(100000n) -> log(n), which also means that having the complexity isn't necessarily indicative of how long it'll take

Just the order of the function

As the goal is to describe end behavior

[whole wadi]

i'm not entirely sure what you mean by end behavior. It's meant to estimate how it will scale as the input changes

[feral shale]

^
when you double your input, sometimes it takes twice as long, sometimes you come back on Monday and the program is still running - big O tells you which to expect

[stark bridge]

nicely said

[low palm]

I'd like to re-raise @placid sun 's question as I'm curious too. It seems the game in question is the one presented here: https://www.youtube.com/watch?v=64pA31_WJa0

So there's a 4x4 2D grid, and we want to check whether or not the grid contains 4 unoccupied cells in which we can place a tetrisy L-shape (which can be rotated and/or flipped). Since the grid is small (there's only 48 possible placements for an L on an empty grid), checking each option seems viable, but what is a good scalable approach?

I suppose the problem could be stated as: Given a set P (possible positions for an L-shape on an empty grid) of sets L (the cells occupied by an L-shape), and a set U (unoccupied cells on the current grid), how do we efficiently check whether any L in P is a subset of U?

Since different L's can still share some of the same cells, it would be nice to trim down the options for every exclusion, instead of repeating lookups as a bruteforce approach would. Some googling led me to https://xlinux.nist.gov/dads/HTML/unlimitedBranchingTree.html but I can't really tell if it's applicable. Thoughts?

[tender wedge]

this makes me think of a dynamic programming problem but instead of L shapes, you have squares

hmm maybe the idea is too far away https://www.geeksforgeeks.org/maximum-size-sub-matrix-with-all-1s-in-a-binary-matrix/

checking every position would "just" take grid_size x grid_size though?

[scenic iris]

@low palm I guess you need a sliding window here 3x3 over given NxM matrix, you could optimize it by increasing a step on certain conditions, but apart form that I'm not sure if it could be done in any better way. I would also be interested to see the best solution to this problem.

[placid sun]

@low palm After thinking a bit, I think I have a slightly better approach than checking everything, for example the orientations of the L pieces have a 3 squares in common each time, so after checking where it is on the grid, I know that if it is on the edge it cannot be 2 positions because that would go off the grid. So i only check with 2. It's still far from perfect though. If the piece is in the middle of the board it is still 4 positions possible

[placid sun]

I made a little image about what I was saying ^^

[royal kestrel]

Doesn't the game include two "stones"

https://en.wikipedia.org/wiki/L_game

[placid sun]

Yes but what does it change ? When you are trying to see the 'free' spaces on the grid . The L of the other player and the stones are processed the same way I think

What I was trying to know was, to check if someone won the only way to check that is to try to see whether he can move his piece somewhere and which is the most efficient way to do this instead of checking if every possibility is possible.

[royal kestrel]

You can limit your search space by first getting the row- and column-wise amounts of contiguous free spaces and then checking only the ones that have 3 or more spaces available for the "body"

[tender wedge]

the cost of checking the 4 rotation and the 4 square is probaby nearly the same?

also you could just generate all possible winning board at the start or saved somewhere and compare if the game state and the winning ones are equal ? 😮

[placid sun]

That's a great idea ColdEmber but i want to do it more algortihmically

and i will try to check this Ava THANKS

I don't know if i understood what you were saying but there is always at least 1 space in every row column in general

I think I don't get what you saying

[royal kestrel]

Since the piece has 3 blocks next to each other and then the one block next to it as the L-shape, somewhere on the board you need 3 spots next to each other in order to place it

So if you do not check the spots where there are not 3 in a row at all by calculating them beforehand you save many iterations over just trying to check every single space

[placid sun]

AH

Thanks I get it now I think

I just do 2 checks per row if there is 3 empty spa ces

and I can stop depending if I find 2 and not empty or 1 and not empty

Thanks

and for the columns I do the same ok thank you ^^

[fiery cosmos]

Can anyone recommend education projects for Python CompSci?

Building a Web Application to manage a Todo List

It's a nice starting point to discover a lot of things

[open cloak]

Currently studying Comp. Sci & we've got an assignment with Python Networking, anyone have experience with it?

[gusty grove]

@open cloak yeah ive done some tcp stuff

@mossy gorge im not quite sure myself, is this the right channel for that question? i mean its his/her comp sci homework but its networking... i thought this channel was more about math/science etc

[open cloak]

We've to create a TCP socket which the user uploads a document to the server and the server has to count the characters and words contained in the file & return them to the client. I don't even know how to tackle this.

[gusty grove]

id rather answer any questions here, not in dms 🙂

[open cloak]

No worries.

[gusty grove]

python has the socket lib: https://docs.python.org/3/library/socket.html

i actually have a script for sending files, but i think you should try it yourself before i just post it 🙂

[open cloak]

I've been looking at my screen for like 30 mins, I've a little bit wrote, I'll get back to you.

[gusty grove]

you might also be interested in https://docs.python.org/3/library/socketserver.html#module-socketserver

[mossy gorge]

Yeah doesn't fit here per say, would likely be better in one of the regular help channels. #help-croissant is for sure free

[gusty grove]

its a slightly higher level lib/wrapper

ok, sounds good to me. feel free to ping me there if you have any questions miller

[last blaze]

finding the count of a given character in a string is O(n) right? theres not some weird tricky way of going about it?

[royal kestrel]

yes

If it's a frequent operator you can create a LUT with pre-computed values, which means subsequent operations are O(1) assuming the string doesn't change

a cache, basically

[last blaze]

Unless I'm misunderstanding, you still need to do at least one pass of the whole string right?

[gusty grove]

yes

[last blaze]

Oh - I misunderstood Ava yeah. Am dumb

[tender wedge]

what's a LUT ?

last used .... ?

[half lotus]

look up table

[tender wedge]

ah yeah thanks

[quaint wing]

Any video tutorial or book recommendation on algorithms?

[last blaze]

MIT 6.006 Introduction to Algorithms is a pretty good set of video lectures

Then I've also heard good things about this video https://www.youtube.com/watch?v=RBSGKlAvoiM&t=4s

[gusty grove]

@quaint wing for me the best way has been to pick a algorithm and then implement it in some way that I can also visualize it

So for something like pathfinding you can do a maze solver etc

[tender wedge]

MIT 6.006 Introduction to Algorithms is a pretty good set of video lectures

yeah the professors are pretty cool

i hated math and i was like "hurh" computer are for nerds

then it appeared on my youtube feed and i watched a lot of them

@gusty grove#0140 i tried visualising BFS some time ago with arcade python but performance were meh : o https://i.imgur.com/0Wfj07B.gifv

[gusty grove]

ive done A* with extreme speeeed!

i have a gif around here somewhere 🙂

[tender wedge]

i should learn processibng a bit tbh

but i'm lazyyyy

[gusty grove]

i just used kivy.

[tender wedge]

too many projects

[gusty grove]

pygame was slow-ish but not really the limiting factor..

[tender wedge]

the slowness in image above, is it draws the thing on a big list

i should redoit with sprite

the gif not animating for me :c

[gusty grove]

yeah not sure why

this should work

[tender wedge]

ahah yeah fast

[gusty grove]

its really slowed down here

[tender wedge]

how do you generate the maze

[gusty grove]

you notice the speed when you got up to 5kx5k mazes 🙂

let me record a larger maze 🙂

[tender wedge]

then tell me :p

[gusty grove]

ofc gif recording is a pain

and i have 0 of the dependencies installed

yay

@tender wedge

oh yikes

what are those colors

i guess thats compression for you haha

so red is where it looked and blue is the fastest path then

i have it to slowly reveal the path but im just skipping that here so the gif isnt too long

im also doing some secret magic behind the scenes to get the maze to generate that quickly 😉

i also have a mode where you can draw your own maze, but as you can imagine it would be kinda hard for those large scale mazes 😉

@tender wedge how did you go about your solver?

[tender wedge]

oh wow it's super fast 😮

oh it's not really a solver on the gif i show, just bfs, but i gess it's imple enough to retrieve the path once it hit x

[gusty grove]

yeah

dijkstra’s does something similar to yours

i rewrote that same algo in cpp and that was even faster

like instant.

pythons slow iteration really kills it here...

[half lotus]

that kind of looks like a 2d map of a world being generated

has a nice river

[gusty grove]

youre right!

now i almost have to use it to generate some nice terrain 😉

[fiery cosmos]

dude that visualisation tool is slick

what is it?

[gusty grove]

It's called "Astar"

[tender wedge]

You could take the red parts to generate continent in a fantasy map :D

[acoustic fox]

@tender wedge I am going through that class right now

I have gone through 17 lectures

It's a pretty good/easy to follow class.

The problem I had with just going through the lectures is that I didn't know how to pragmatically implement the data structs, and so I am currently going through the book, I am on chapter 4.

[tender wedge]

Yeah

Have to train after, following is not enough

[acoustic fox]

UH

I took extensive notes from the lectures

but it's not necessarily about training as much as like

How do you form a graph in python ?

How do you insert numbers, rotate groups, ect.

[fiery cosmos]

thx @gusty grove

[fiery cosmos]

can someone help me understand Dijkstra's algorithm?

[native tiger]

anyone know some good recourses on quantum computing

[acoustic fox]

Taking a look at it @fiery cosmos

So, you already know about relaxing edges, right ?

[fiery cosmos]

a little, what confuses me is that some approaches don't use the relaxing approach

or is that a key part of the algo?

[acoustic fox]

Dijkstra's uses relaxing

It's used to deal with negative weight cycles I think

https://www.youtube.com/watch?v=2E7MmKv0Y24&t=33m30s

[fiery cosmos]

so cycles you mean refreshing for each updated node?

[acoustic fox]

Nonoo

If you try to relax the edges over and over and over again

when you update the values starting from the '1' circle' you can get an arbitrary low value to any node in that cycle

Which is an issue

This creates firstly, a problem of infinite recursion so your algo never terminates, it also means that you will/might weigh all those nodes at -infinity which can break the graph because any node that you need to travel through the negative weight cycle to get to will also have -infinity value

Dijkstra's algo solves this problem in an approximate way

(It doesn't solve the problem, but it pushes the problem aside. )

(Technically in my opinion if you have negative weight cycles that allow for arbitrarily low weights to get to the node, that represents a real problem that your model isn't handling well enough, so we are just sweeping that problem under the rug)

Does this make sense so far?

[fiery cosmos]

Yeah understanding the problem helps a bit, by arbitary do you mean all neighbouring nodes based on the group, or selected node ? So by selecting one as not having infinity this cancels the cycle?

[acoustic fox]

So

[fiery cosmos]

I'm a bit of an algorithm noob so it's a little hard to grasp

[acoustic fox]

Algorithms are just a series of instructions that you tell a computer to follow

And what you want are robust series of instructions that can tackle general classes of problems

In this case you want to figure out shortest path through an arbitrary graph that consists of Nodes (circles) and edges (the cost of traveling between circles)

(Nodes have no 'value' as much as they are place holders for some object, you can imagine nodes as cities, and edges as roads between cities. You might ask, what is the shortest path between one node and another node (shortest road distance that costs you gass/time/money, whatever)

So when you typically approach this problem what you'll do is look how many edges are coming off a node, and then assign a value to each connected node through the roads that lead to them indicating the 'cost it takes' to get to that node

in my picture, you start at (1) and there are two roads (edges) where one costs 7, the other costs 1

You assign those values and then you travel to the (7) node and repeat the process

So, we see taht there are two paths to

A problem that we see is that there are two paths to that square, so what is the shortest path? when traveling to 7, then 2, the total path is 9, and we put (9) in the value of that node

but then we travel through (1) then (1) again, we check if 2 is < 9, it is, so we update the value. Great! We have the shortest path cost to that value

The problem with negative weight cycles is that we travel -1, then -3, then 2, so the total value of a node is( -1+-3+2)+ initial value of that node ( 2) = 1 the initial value of that node

Since 1< 2 , we update the value and go to that node to count how many vertexes go out from that node and we repeat

the next time we go through the cycle, the value of that node becomes 0, then -1, then -2

[fiery cosmos]

oooooooh okay and then it just repeats

[acoustic fox]

(The end condition of this algo is that if you can't relax any edges, the algo completes)

[fiery cosmos]

until all is visited

[acoustic fox]

until all is visited (wrong)

This is a fundamental problem of the algo at the moment that we have laid out

It works perfectly for graphs with no Negative Weight Cycles

Dijkstra's algo solves the problem through what you just said , goes until all is visited

[fiery cosmos]

so it would work in some situations, like calculating real distances but not in certain data which uses negative values

[acoustic fox]

Right

Technically in the real world, negative weight cycles never really exist

But because graphs are models and approximations and are over simplified

These things come up

(Imagine when you visit a city, they pay you 20, so you experience a -20 decrease when you visit )

Technically the optimal strategy is just visit the city, go back and visit it again infinitely many times.)

(Technically going through roads takes time, not just money, so when we represent this in a graph where we exclude other costs, it presents as an issue )

You still want to capture the benefit of traveling through this city to get to your destination without being bogged down by the negative cycle telling you to go only to that city, to another, and back over and over and over again)

[fiery cosmos]

yeah that makes sense, very interesting thing to consider if there are other algo's suffering from this

thanks for your explanation it was very helpful

[acoustic fox]

This is the point of learning algos/data structures

Every structure/algos only solves certain classes of problems

Knowing when they work, when they don't and knowing how you must formulate the problem in order for the algo to digest it is all apart of data struct

To understand the benefit

Imagine you have 50 cities

There are 50! ways the cities are interconnected which means there are 3*10^64 possible connections

which would take a computer 2*10^53 years to brute force and find the shortest path

Instead, we run this algo and solve this problem in .000002 seconds or something

[fiery cosmos]

but can algos work with multiple dimensions apart from just graphs?

[acoustic fox]

Hyper graphs ?

People work on problems that can and can't be solved by a computer

There is the most famous example called the 'Halting Problem' where you might ask, 'Can a computer decide if the algo will ever complete or not'

An example might be

While(True):
print("Hello World" )

[fiery cosmos]

So algo's primary use is for sorting data, use in mapping finance etc. Wondering how else they could be used

[acoustic fox]

A computer can't decide of that program ever terminates

An algo is just a series of steps

My while look is a 'algo'

All of programming uses algos to create desirable behavior

[fiery cosmos]

I see

[acoustic fox]

You can use algos to create art, finance, websites, finance, whatever

Finance twice, cuz why not

The study of Algos deals with the 'run times' of programs

you might ask "How long would it take to sort a list of a given size (N) "

Maybe I have a problem where I want to predict/ autofill people's text responses when they type in a cell phone

So it has to run faster than it takes for someone to 'type a word'

Through brute force using a 1 billion word dictionary, it would take something around 30 seconds for one word

but you can arrange the data in such a way that you can traverse a tree of dictionary values that it takes only 30-40 steps to get to the right approx answers (takes about .00000001 seconds

[fiery cosmos]

i see i see

you've really let me see this differently man thanks

[acoustic fox]

When you setup a tree like this, one question is 'How do you insert a new word into the tree'. Like, when 'Yeet' comes along, how does that get inserted into this mess?

And how do you priorities more common use words

I'm glad to help

[fiery cosmos]

would more trees, or edges be split off from parents?

if those letters where supposed to represent the alphabet

or just another tree

or it would just be entered as nonsense

[acoustic fox]

When you talk about trees, you talk about 'levels' , first level is [a, b,c,d,e, ..]

you might look at a-> second level would be [aa,ab,ac,ad]

third would be [aardvark, aab, whatever]

(there are no words that start with aaaaaa for instance)

So if you saw someone typing with 'a', you then look at the second, third, fourth level and apply probabilitiy weights to those most likely predicted results and return those, as you get more information, you go down the tree and keep doing the same thing )

[fiery cosmos]

and this would repeat and repeat until there is a match to yeet?

[acoustic fox]

In my example

WELL

how about this

instead of yeet

you have 'dab'

Before 'dab' there were no words that started with only 'dab', and you only had words that start with dabb <for dablle, dabber, dabbed, ect

(The tree might only be made up of real words and not partial words, maybe

now you have to insert 'dab' into the tree that lots of words 'depend on'

that you must search through 'dab' before you go to 'dabble'

You have to insert 'dab' now into the tree and make all the words that previously depend on lets say 'Da' (for dad) now depend on 'dab'

Inserting a word isn't like inserting a new word in a dictionary where you find the place, insert it, and move all the words down by one

It's more complicated

(We haven't even talked about balancing a tree )

(A dictionary is actually a tree structure btw)

[fiery cosmos]

so then for this example would there just be a huge alphabet listing all possible word combinations

[acoustic fox]

'All word combinations' ?

[fiery cosmos]

i mean

all alphabetical combinations

[acoustic fox]

No

26 letters

there are 14 letter words

[fiery cosmos]

so a,b,c, then aplit into a,c,b , a,ie, etc

oh no mb

[acoustic fox]

Here is a 14 letter word

abstractionists

each position there are 26 possibilities (26 letters) 14 positions,

there are 26^14 possible 14 letter words in english

which means there are 6,400,000,000,000,000,000 possible 14 letter words

in that list contains aaaaaaaaaaaaaa,aaaaaaaaaaaaab,aaaaaaaaaaaaac, ect ect

You want to list only real words that people can use

It would take 7,509,949,466 GB to store that list btw

actually, a bit more, but w/e

75,099,494,660 GB

[fiery cosmos]

out of just the word abstractionists?

[acoustic fox]

I mean to say there are that many possibilities to create 14 letter words

[fiery cosmos]

i see

and eventually we'll run into dab?

[acoustic fox]

In my example, no

Because that is only containing all possible 14 letter words

[fiery cosmos]

oh yeeea

[acoustic fox]

26^1 + 26^2 +26^3, ect ect

[fiery cosmos]

ohh yea i think i got a feel for the concept

ty again man I've been awake all night trying to blast that stuff

i don't feel so vengeful against djisktra now

or algo's in general

[acoustic fox]

Oh yah

I mean

[fiery cosmos]

2 hours ago I was shouting about how i wanted to fight him irl if he was still alive

[acoustic fox]

This is a huge subject that is worth billions and billions and billions of dollars

We haven't even talked about Dikstras or whatever

Or talked through how he does it

If you want to learn algos, start at the begging of the lecture series

You should know about lists, dictionaries, sorting, ect

[fiery cosmos]

all I managed to do was bubblesort

some of the data structures especially with djiks really throws me off

how nodes are referenced and stuff

[acoustic fox]

I don't know how to put it into python yet

I have guesses

Right now I am going through the book of the course video I posted

[fiery cosmos]

i'll have a peek

[acoustic fox]

That whole course is 99% great

[fiery cosmos]

i can understand psuedocode and demonstrations okay, just translating into code can be a pain

can get lost in some of the logic

or something

but I'll give it one more blast

got to get ready for my class anyways also, thanks very much for your time and help

nice insights

and yea I'll take that recommendation

[acoustic fox]

npnp

[long sleet]

Idk if this could fit here but, has anyone made an stream labs chatbot script for twitch on python?

If so, could u explain me the bascis pls? Reading the wiki and example i understood nothing

[acoustic fox]

This isn't really the place for that

This more about the study of algos and data structures

[distant maple]

Is it possible to make a game in F#, or would that be a difficult task for a functional programming language?

[acoustic fox]

Not so much a computer science question

[timber zinc]

ffs

[acoustic fox]

but you can make a functional game

[timber zinc]

forget it

[acoustic fox]

MACS

YOU BELONG

@timber zinc GET BACK HERE

[timber zinc]

i thought u were saying

not much of a cs question here lmao

i was like oh ffs

anyways

[distant maple]

Okay I'll post it in off-topic next time 👌

[acoustic fox]

LOL

It's chily

I'm just trying to make this a comp-sci channel because that is what I am learning at the moment 😛

[timber zinc]

i know numpy shuffle is way faster for large arrays than random.shuffle(). I think they still use Fisher-Yates but I was wondering if there are algorithms faster

[distant maple]

Yup about 30 degrees chilly indeed

[timber zinc]

its somehow like 60 here

but was 32 yesterday

[acoustic fox]

I'm trying to find any background on how numpy does it

[timber zinc]

I cant figure out what algo they use

[distant maple]

Is the source code on github?

[timber zinc]

I could maybe use sattalo's but im not sure if that is any faster of a Fisher-Yates

It seems it's faster to use random but not use shuffle and just use something like randrange to pull and check in memory

I may do some timeit tests

[acoustic fox]

The source code wont help us much dertien

[timber zinc]

the docs arent very clear on what algo they are using however

[acoustic fox]

We want to know the method/ what algo is being implemented

[timber zinc]

i mean if we check source for the shuffle func we would

[acoustic fox]

I am not familiar with all the possible methods

I would guess at least for me it is something that I haven't been exposed to yet

[timber zinc]

What about xorshift implementation in python

[acoustic fox]

http://web.mit.edu/dvp/Public/numpybook.pdf#page=181&zoom=100,0,230

Large paper on Numpy by MIT

[timber zinc]

love how that link to the algorithm info is a 404

sweet

[acoustic fox]

LOl

yeah

[timber zinc]

http://web.archive.org/web/20031021004344/http://cgm.cs.mcgill.ca/~luc/rnbookindex.html

here it is

[acoustic fox]

This list makes me feel stupid

I love it

[fiery cosmos]

If a binary number until 127 means either a decimal number or a letter at the ASCII, how can the computer differentiate these numbers from the letters?

[half lotus]

it just depends on context

the computer interprets the data how a programmer tells it to interpret it

[fiery cosmos]

oh, I get it

like when we put a number as string

[long sleet]

Guys

I have a question

How many operations (+, *, /, %) are considered to much per frame too make a render laggy?

Because i am doing 900000 and my app goes at 2 fps

[acoustic fox]

That seems really weird

typically a computer can perform 300,000,000 operations a second

I wonder if the size of the inputs of the operations are the issue

like, 10001000 takes more time than 1010 ?

HMmmmmmm

10 * 10

[long sleet]

No lol

The inputs are between 0 and 1 or between 0 255 or between 0 360

[acoustic fox]

HMM

You aren't just doing .9M operations

You are doing something with those, right?

Updating locations ?

And rendering objects ?

I can perform that many operations a second pretty trivially

So there must be something else going on

[long sleet]

Yes, im rendering

I am doing a color wheel

I have a func that given x,y returns polar form

And another one that transforms hsv to rgb

So my circle has center, min r, and max r

And it is only being filled in between (like a disc)

So i have a while loop (angle < 360)

And inside, a for from r to R

And inside that for, i render the point getting the rgb from the hsv (using the angle and the radius)

Nothing rlly complicated

So if my disc has 250 pixels width

And my angle increases by 0.1

I have 250*360*10

= 900.000

[trim flare]

Has anybody worked with geometric algorithms in Python such as Packing Problem etc.? I'm working on something similar but missing the right mathematical terms/jargon

I'm looking to work on an agent-based packing problem, as in packing a grid with rectangles but only with the path of an agent and overlap is allowed

[gusty grove]

@long sleet could you send me a pic of the output?

[pallid coral]

Why are you rerendering it every frame? Does it change on every frame?

It also seems like you're rendering at a given angular accuracy--instead, render the 250x250 circle of pixels as inputs instead of the angle

"what color is pixel 50, 50" instead of "What pixel is at radius 10, angle 0.145"

[long sleet]

Output? What output

It is an image

U want the pic?

@Leterax#0140

@Leterax#0140 .

O.o

Why not mentioning?

[gusty grove]

yeah

the img

[long sleet]

Hold on

but it is a color wheel

https://gyazo.com/5b485e0938eebda9ecb7e5d89f0fd1ee

[gusty grove]

well that shouldnt change over time right?

so just generate it once 🙂

[long sleet]

it will

https://color.method.ac/

i was trying to make that game :D

[gusty grove]

something like this>

i just made it rotate for fun

ignore the horrible gif quality hah

[long sleet]

why my fps are so low

:(

my program runs at 2 fps

[gusty grove]

well its kinda unfair. this is on the gpu 😉

[long sleet]

mmm

could u try on cpu?

i mean, is just a fckin circle

[gusty grove]

this runs at 2496.85 FPS for me 🙂

[long sleet]

...

[gusty grove]

at that point its more the displaying that takes time not the calculations

[long sleet]

could u share code?

[gusty grove]

yeah one sec

[long sleet]

i can share mine, but mine is on java u.u

[gusty grove]

oh if you know java i dont have to translate it to python!

void main() {
    vec2 uv = (gl_FragCoord.xy/wnd_size - vec2(.5)) * 2.;
    float dst = length(uv);

    if (dst > .4 && dst < .7){
        vec3 color = hsv2rgb(vec3(mod((atan(uv.y, uv.x)/(3.14159265359*2)+time*speed)+1., 2.)-1., dst*2., 1));
        fragColor = vec4(color, 1.);
    }
    else {
        fragColor = vec4(0., 0., 0., 1.);
    }


}```

thats the shader code that runs on the gpu

@long sleet feel free to check out the rest of the code under "HSV" in https://github.com/Leterax/Visualization/

[long sleet]

u arent painting anything at all :D

is all the shader

void drawDisc(float x, float y, float r, float R) {

  float angle = 0;

  while (angle < 360) {

    for (float i = r; i < R; i++) {

      float[] point = cart(i, radians(angle));

      float[] rgb = hsv2rgb(angle, 1, i/(R-r));

      stroke(rgb[0], rgb[1], rgb[2]);

      point(x + point[0], y + point[1]);

    }

    angle += 0.1;

  }

}


float[] cart(float r, float a){

  float x = r * cos(a);

  float y = r * sin(a);

  

  return new float[]{x,y};

}


float[] hsv2rgb(float h, float s, float v) {

  h = min(max(0, h), 360);

  s = min(max(0, s), 1);

  v = min(max(0, v), 1);


  int i = floor((h/60) % 6);

  float f = ((h/60) % 6) - i;

  float p = v * (1 - s);

  float q = v * (1 - f * s);

  float t = v * (1 - (1 - f) * s);


  p *= 255;

  q *= 255;

  t *= 255;

  v *= 255;


  switch(i) {

    case(0):

      return new float[]{v, t, p};

    case(1):

      return new float[]{q, v, p};

    case(2):

      return new float[]{p, v, t};

    case(3):

      return new float[]{p, q, v};

    case(4):

      return new float[]{t, p, v};

    default:

      return new float[]{v, p, q};

  }

}

[gusty grove]

@long sleet hmm?

The file main.py runs it all

[long sleet]

i paint pixel by pixel

[gusty grove]

Yeah me too

Thats what a fragmentshader does :)

It paints all the pixels at once ;)

[long sleet]

but u didnt implement it

my problem is the optimization

[latent jewel]

find the kth element (in sort order) of a binary search tree

what is in sort order? I know pre post and in order

but im not sure what sort order is

[feral shale]

it means in order

[latent jewel]

oh ok

[azure shard]

why i am getting None as elements in d[] when i am trying to flatten a[]

a=[[2,[4]],5]
d=[]
def flatten(arr):

print("{} is the input".format(arr))

if type(arr) != list:
    #print("{} is not an array".format(arr))
    return arr
for i in arr:
    #print("flattening {}".format(i))
    fl=flatten(i)
   # print("fl: {}".format(fl))
    d.append(fl)
    #print("d: {}".format(d))

flatten(a)

print(d)

[half lotus]

This question is better suited to a regular help channel

[fleet crow]

I've been given an array which tells me to write it out as a binary tree. I've been working on this problem for an hour now and I've still no clue how to solve this.

Is there any resources I can use to help me with this - as I don't really want an answer, rather a clue of some sort.

[acoustic fox]

I am looking for what the fuck it is asking

[gray blaze]

I am doing an assignment on Using AI to detect good and bad reviews has anyone got any good ideas on how I could improve this idea also any good literature I could use

This is for a Computer Science degree so I thought it would go in here

[candid bear]

I have a sample paper for an exam on Computer Architecture where it gives us a question asking for the number of bits in the tag, block index and block offset fields of the memory address, just looking for help with how the block index is calculated

the specifications are 16-bit memory addresses, 2K-bytes cache with 64 bytes per cache block, direct mapped cache

the number of blocks doesnt divide evenly into the cache, gives me 31.25 times, do i take this as 32, or do i use the next lowest value that fits 2^n?

if anybody thinks of something could you please @ me, gonna be away for awhile and i dont want to risk missing something if this gets buried, thanks

[surreal geyser]

how do you draw a flowchart for a for range loop?

[gusty grove]

@fleet crow havs you tried sorting the array?

The its rather easy to convert to a bin tree

[tender wedge]

I don't think you need? It will fell by itself at the right place?

A sorted binary tree isnt degenerate ?

[fierce inlet]

im working on a shared memory queue and at the moment it's basically suballocating one large chunk of memory using the buddy system

to keep track of the state of the blocks in this chunk im using a dict as a kind of makeshift linked list.

at the moment this dict needs to be pickled/unpickled to be updated every time a block is allocated/freed

all this is to say: i very much doubt this is the best way to go about solving this problem overall

so im wondering, is there a known allocation method that ideally:

• causes minimal fragmentation
• requires no extra metadata about the blocks (except maybe some info contained within the block itself)
• has amortized O(1) allocation/deallocation

[worthy jay]

Good morning guys

Is there anyone offering programming fundamental

[acoustic fox]

??

@worthy jay there are MIT open courseware classes

I'm going through a book atm

[earnest surge]

@acoustic fox Which book?

[fleet crow]

I'm stuck on a question asking me to simplify the Boolean equation:

Ive managed to simplify it to

but im a bit stuck on where to go next

[low palm]

Isn't (E ^ B ^ -E) just impossible, because it requires E to be both True and False? @fleet crow

[acoustic fox]

Introduction to Algorithms, Third Edition

from MIT open course 2.006 (or is it 1.006? ) the fall 2011 intro to algs class

[last blaze]

I highly reccomend the MIT 6.006 introduction to algorithms https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/

[royal kestrel]

@fleet crow for the right side you can use the distributivity of disjunction over conjunction, as in A ∨ (B ∧ C) is equivalent to (A ∨ B) ∧ (A ∨ C)

Once you transform with that the right side should be obvious

[fleet crow]

@royal kestrel would that become (¬A ∨ A) ∧ (A ∨ C) which then simplifies to 1 ∧ (A ∨ C because (¬A ∨ A) = 1 ?

that would become (A n 1) u (C n 1), which becomes A v C?

[royal kestrel]

yep

[fleet crow]

cool

Would E n ( B n ¬E) be able to be expanded to (E n B) n (E n ¬E)?

[royal kestrel]

yes

[fleet crow]

Ok

[royal kestrel]

https://canary.discordapp.com/channels/267624335836053506/650401909852864553/655096051233062918

[fleet crow]

Cool, i got the answer correct

thanks for the help

[acoustic fox]

@last blaze That is the course who's book I am currently going through. I made it to lecture 17 with a lot of notes, but I realized I wasn't able to implement the structures I learned so I am reading the book

[last blaze]

My strategy has been to try and implement the structures I'm not 100% on as I go through the lectures - but I do already have some experience with this sort of thing

I wasted like 2 hours because I didn't 0 index my heap properly and was incredibly confused - so a book definitely has merit

[acoustic fox]

The problem I have is that I can imagine ways to implement them through nested dictionaries, touples, other kinds of code structures, but I don't want to do something stupid and get stuck in that way.

For trivial basic algos, we should already have the best way to impiment them in code and it is a better use of time I think just getting the best thing under your belt instead of having to reinvent the wheel (Obviously you should know how they work, but that doesn't mean that you should do a shotty implementation )

I do think getting over humps is where the real learning happens if that is any consolation

For introductory stages, I think treating these things as tools to put in your belt is the right way to go about the subject.

[last blaze]

One thing thats been good for me to do, is to implement it, then ask someone who knows waaay more about this stuff for their thoughts

[acoustic fox]

And you wouldn't for instance learn about a hammer, then go into the back yard to chop down a tree, get some metal, glue them together and say you have a hammer, you know ?

UHH

I think coding exercises is 100% necessary to learn the subject mater for the purposes of applying to jobs

I get to ask a person who has been studying computational complexity about some of the analysis of algo stuff

[last blaze]

Yeah, I agree. My current course of action is do this course and maybe some more, then complete every problem on CodeSignal

by which point I should have a pretty solid foundation

about the excercises that is

[acoustic fox]

What are your goals with learning comp-sci? (I want to get a FAANG job for the $_$)

(I am business oriented )

[last blaze]

Well - I'm doing a degree. After that I just want a job with a good salary

[gusty grove]

faang?

[last blaze]

Facebook Apple Amazon Netlix and Google

or some such

[gusty grove]

ah

[acoustic fox]

entry level jobs pay 150k +)

[gusty grove]

yikes

get me one of those!

heh

[acoustic fox]

It's hard because you need to have excellent fundamentals )

[last blaze]

In the UK FBs grad salary is £70k which is pretty great compared to like £24k at a lot of companies

[acoustic fox]

I am in the bay area

It's a bit different here.

[last blaze]

Yeah, although London is one of the biggest tech hotspots in the world at the moment

but nothing compared to the biggest

[acoustic fox]

Prices are also relative

United states is just so weird

[royal kestrel]

I'm sorry but in what universe is an entry level job 150k+

Also this really isn't related to computer science so I think we should move to #ot0-psvm’s-eternal-disapproval

[feral shale]

there's #career-advice too

[acoustic fox]

...

[gusty grove]

For a N body gravitational sim, are there any optimizations to get it below O((n*(n-1))/2)

[solid cloud]

if you're willing to do a crude-ish approximation, you can get it to O(N) with a solution like SPH

https://en.wikipedia.org/wiki/Smoothed-particle_hydrodynamics#Astrophysics_2

[gusty grove]

hmm looks kinda difficult haha

[solid cloud]

SPH is actually really easy

the 2D case is basically 'draw a gaussian falloff where each particle is, and add them up'

the 3D case is same thing except on a volume instead of a plane

for gravitation it'd be a 1/r^2 falloff

[gusty grove]

does it have any downsides?

[solid cloud]

it's not super accurate

[gusty grove]

why not?

[solid cloud]

https://academic.oup.com/mnras/article/448/4/3628/972284

you need to decide how accurate you need a sim to be for your application

if you want to simulate a bunch of matter accreting into a planet, SPH will do that

and also yeah if you want to get into situations where special relativity becomes relevant, things get fucky

https://en.wikipedia.org/wiki/N-body_problem

this is a computationally demanding domain and depending on how accurate you want to get, n>4 is not currently realistic

[gusty grove]

huh i thought n > 2 was impossible analytically..

well i only want something that looks cool 😉 it doesnt have to be very accurate.

it should just look believable

[solid cloud]

then SPH is the main candidate

[gusty grove]

im gonna try the n**2 first just to see if it works and then ill try sph

[solid cloud]

if you go with SPH, this is a decent intro: http://www.yuwang-cg.com/2_0_SPH_WebGL_WebCL/sph_webgl_webcl.html

[gusty grove]

thanks!

[solid cloud]

it is for the fluid case but easy to modify for gravitation

[acoustic fox]

I wonder if it gets highly accurate if you have super dense objects that are only a meter across that you're total relativistic 'speed' is like, 10m/s

[solid cloud]

it still has a bunch of tradeoffs

single step discrete time

cost highly dependent on max influence range

which can't be infinite

and discrete force volume which eats more ram for more accuracy

[acoustic fox]

WELL

Mostly three body problems are chaotic in nature and so everything is fucked on some time scale

I don't know for sure, but I don't believe there is an exact solution for 3 body problems ??

(At some point you need to take into the account the tidal forces between bodies as well for which there are only approximate solutions )

[solid cloud]

there's no exact solution for anything because we still lack the fundamental physics to describe the behaviour of things

[acoustic fox]

Uhhhh

Just a fancy way to say everything is approximate

[solid cloud]

no this is really important. a 2-body analytical solution actually diverges from reality pretty quickly

this might change if we ever have a unified theory

in the meantime all you can do is decide what level of accuracy your application requires and decide whether or not you have enough compute to achieve it

within some reasonable but nonetheless tight bounds

[acoustic fox]

The two body problem in mathematics is 'solved'

[solid cloud]

it's solved in the sense that there's a fixed equation governing the motion of the two bodies given a large number of assumptions

not in the sense that it accurately models reality

just like checkers is solved but chess is not despite computers absolutely shitting on humans at chess

[acoustic fox]

Again, given that physics can only measure things so accurately this objection is just saying that at least fundamentally our models are limited

[solid cloud]

it's not that we can measure things so accurately, it's that we don't understand the rules that govern how things behave

e.g. dark matter

e.g. wave/particle disparity at scales

e.g. observer problem

[acoustic fox]

Of course there are still unanswered questions (Gaping holes) in physics

[solid cloud]

tl;dr we can't write a sim that accounts for <magical quantum effect> if we haven't figured out the rules of that effect. The n-body problem doesn't even try to address this

so comes back to how accurate do ya wanna be

[acoustic fox]

Any analytical solution has this problem

[solid cloud]

analytical solution just means we can write an equation that leads to the answer instead of having to explore a search space to find it

[acoustic fox]

(I might be wrong) But from my computational physics class typically you model a system through a taylor series with infinite terms

[solid cloud]

you can model anything with a taylor series of infinite terms

or a neural network of infinite depth

anything computable* things get a bit funky there

[acoustic fox]

(I don't know anything about neural nets, but that is danke as fuck) but you are limited to how many terms you can use to model a system given finite time, so everything becomes an approximation that deviates

It becomes a mater of the timescale of interest

[solid cloud]

yeah there's a whole field of study dedicated to figuring out things that in theory could be computed but actually can't even if you turned the whole universe into a perfectly efficient computer

[acoustic fox]

Yeah, there is a phd stupid floating about this server who got their PHD in comp physics

The halting problem can't be computed, and the study of computation times of algos is the reason why this channel exists

[solid cloud]

yeah there's non-computable

but there's also computable but can't actually be computed even if universe was a computer

i personally found that really interesting

[acoustic fox]

I mean, computing every combination of 200 unique cards is impossible

[solid cloud]

god damnit google

[acoustic fox]

LOL

It's like 7*10^375

[solid cloud]

in that case its fine

because there's like 10e80 atoms in the observable universe

and we could at least encode a bit in an atom, probably closer to a byte

[warm marsh]

>>> math.factorial(200)
788657867364790503552363213932185062295135977687173263294742533244359449963403342920304284011984623904177212138919638830257642790242637105061926624952829931113462857270763317237396988943922445621451664240254033291864131227428294853277524242407573903240321257405579568660226031904170324062351700858796178922222789623703897374720000000000000000000000000000000000000000000000000

[solid cloud]

legend

[warm marsh]

just saying...

[solid cloud]

surprised it switched to bigint all on its own

[warm marsh]

Python handles infinitely large integers natively. Only limit is your RAM.

even 20000! still responds nearly instantly

[solid cloud]

maybe i've been smoking the wrong stuff but my python does most things in double floats

[warm marsh]

although the number fills out a whole terminal page

[acoustic fox]

Seems like the computational time is 10^362 years

On a standard computer

It just seems like because of combinatorics it becomes super easy to have computable / non computable functions

[solid cloud]

yeah that's basically the deal with the np-hard class

but figuring out the exact limits of what could be computed if the entire universe was an ideal computer is neat

[fierce inlet]

is there a way to use semaphores to build event primitives?

vaguely remember something like it

by event primitives i mean the ones where you can have multiple threads waiting and notify all of them at once from another.

guess it depends on exactly how much control/info you can get out of the semaphores too

[acoustic fox]

For python you have threading which you use Queue to communicate between threads

I don't know asyncio

(I am unfamiliar with semaphore /event primitive words, so there could be things I am missing )

[fierce inlet]

im asking in general terms, not in terms of any particular language

[acoustic fox]

Oh, interesting

[fierce inlet]

i.e. can event be reduced to semaphore(s). if so how.

i know you can build mutexes with a semaphore with an initial value of 1

what else can they do yknow?

[acoustic fox]

I don't know actually. I'm not quite there in terms of programming language architecture 😛

[royal kestrel]

You can implement a semaphore as a mutex + condition variable

You can use a semaphore to let's say only have 10 connections open at any given time

[fierce inlet]

im wondering how/if its possible to make one of these https://en.wikipedia.org/wiki/Event_(synchronization_primitive) with a semaphore

cause i vaguely remember being told that semaphores are the basic building block of synchronization

that you can always somehow reduce the other primitives to one or more semaphores

i can think of at least one way but it would be dependent on the implementation of the semaphore. it would require either: being able to directly query the semaphore's current count, or nonblocking acquisition thatll error out if semaphore is busy