algos-and-data-structs

[edgy otter]

Previous version of the code I was actually keeping track of a count for each iteration and adding that to the list. So I would have to update every element in the list every calculation. That became a problem quickly which is when I switched to using the mod and subtracting the start value. Nice thing there is I can actually save the list and pick it up from any point now 🙂

looking at how I can apply the chinese remainder theorem. It looks like it would apply here but need to make sure I am understanding it correctly.

[runic tinsel]

but what does it do?

[edgy otter]

Searching for a counter example to a conjecture (or prove it if all the numbers end up falling into the pattern).

[vocal gorge]

also check if pypy can give you a speedup on this one

[edgy otter]

Hmm seems like it should, didn't realize python had a JIT compiler.

[loud trail]

i think global lookups are slower than local lookups. why use a global? @edgy otter

apparently it can be a significant difference in hot loops, although that would need benchmarking

[edgy otter]

Easy, I was unaware of any performance hits based on the scope of the variable and it was being (initially) passed around a couple times so it just made the code easier to write. Now that isn't the case though and it could be easily passed to the skip method.

[loud trail]

yeah that would probably be both faster and easier to reason about

how much faster? hard to say

[edgy otter]

Well considering the number of items in the list at this point and the number of times it will loop through the list nano seconds would add up quick 🙂

[loud trail]

there's a known "hack" in python to avoid global name lookups for function calls

def skip(intervals, n):
    ...

def main():
    _skip = skip
    _skip(x, n)

you might want to "inline" the entire skip function anyway since function calls have nontrivial overhead too (even in pypy)... but this is definitely "chasing nanoseconds"

[edgy otter]

yeah the inital skip method did quite a bit more

chasing nanoseconds is definitely the name of the game at this point. A nano second saved a few trillion times adds up 🙂

[loud trail]

how's this? might be worth benchmarking

def main():
    steps_table = calculate_steps_table(1000)
    steps_table = calculate_intervals(steps_table)
    intervals_list = []
    for i in range(2, 10_000_000_000):
        steps_cnt, breadcrumb = steps(i)
        intervals_list.append([steps_table[steps_cnt], i])
        if any((n - hi) % lo == 0 for lo, hi in intervals_list):
            continue

also you might want to use tuples instead of length-2 lists?

def main():
    steps_table = calculate_steps_table(1000)
    steps_table = calculate_intervals(steps_table)
    intervals_list = []
    for i in range(2, 10_000_000_000):
        steps_cnt, breadcrumb = steps(i)
        intervals_list.append((steps_table[steps_cnt], i))
        if any((n - hi) % lo == 0 for lo, hi in intervals_list):
            continue

(sorry if that logic isn't quite the same, just eyeballing it)

have to run to a meeting, i'll be back in around 2 hours. i feel like using python to process 1 trillion data points without any parallelization is kind of hitting an upper limit of what makes sense before switching to a different language (or at least a different runtime like pypy)

[edgy otter]

Yeah I think I am going to switch to pypy and make some of these tweaks

[loud trail]

there is also graalpython, might be fun to compare with pypy

you might also want to evaluate numba or even cython

[edgy otter]

Also going to make the list sorted while I figure out the next performance upgrades and add in state saves.

[edgy otter]

looking at this it looks like the logic is the same. Does any just iterate through the list from 0 -> len or is it able to do it in a smart fashion?

[austere sparrow]

last time I checked (quite a while ago) it was slightly slower than CPython, did it change?

[edgy otter]

Which one?

[austere sparrow]

graalpython

[edgy otter]

ah ok

[covert ember]

where can i learn ds and algorithms?

[loud trail]

i did some light benchmarking a while ago, it was comparable to pypy on "simple" tasks like looping and string operations

a while = a couple weeks

[austere sparrow]

ah, well, then they're improving, that's good to hear

[loud trail]

maybe it was slower, but same order of magnitude. and faster than cpython for sure

[austere sparrow]

does that mean that there could be some compatibility between Java-on-GraalVM and Python-on-GraalVM in future? 🤔

or does it not work like that?

[loud trail]

no idea, that'd be pretty cool

isn't there already another python-on-jvm

jython?

is that still a thing

[austere sparrow]

it's on python 2

[mint jewel]

yeah, graal will probably eventually implement python further, which should in theory be quite fast (the JS implementation matches V8 at peak perf, but has a slower windup time)

[edgy otter]

switching to pypy and removing the function call for the skip seems to have improved the performance dramatically even though I am writing to a file for each new pattern found.

I tried adding the sort for each new item added and that seems to have slowed things down pretty quick. Going to try just adding a sort on re-runs after loading the previous results from the file.

[rocky wasp]

hi can i know what is the problem plz

[mint jewel]

missing closing parethesis

[rocky wasp]

print("thank you")

[loud trail]

any will stop as soon as it finds a True, but possibly more efficiently than writing out the loop

The more I look at this logic the less I understand what's happening. Is this really not parallelizable?

Or at least can be rewritten so as to be closer to linear time?

That (n-a)%b check could get really slow once the interval list gets big

I must have misread your original code

[edgy otter]

It might be parallelizable but the trick is making sure the patterns don't get doubled up. The (n-a)%b check does get really slow as the list gets bigger even with sorting.

[edgy otter]

There are 988369 items in the list currently

[edgy otter]

        while any((i - hi) % lo == 0 for lo, hi in intervals_list):
            i += 2```

Incrementing by 2 instead of one since I can skip even integers

[slim citrus]

{
{0, 0, 0, 0},
{0, 1, 0, 0},
{0, 0, 0, 0}
}``` what would be the most efficient way to check if the numbers surrounding "1" are 0

[tender atlas]

0-1 BFS with 8-neighbor

If you know the 1's point x,y

You can only do 8-neighbor check

neighbors = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]

[edgy otter]

Yeah definitely going to need to use Chinese Number Theory to optimize these checks. Just need to figure out how best to implement it, assuming that it will work. The list currently has 1.42 million checks...

[azure gulch]

hi i have two coordinate and i draw a line from them, but i want to put a block between them and creat new route

[loud trail]

Maybe pre-compute those values and store them in a data structure of some kind? And/or use some data structure that supports faster lookups than O(n)

You know what has native bigints, a fast runtime, and is dynamic and high-level like python? Common Lisp

[edgy otter]

Hmm I haven't messed around with Common lisp. And I can't really pre compute the values since that is kind of what the algorithm is doing 🙂 Or at least determining the start points for the intervals. I can take the ones that are already computed though and put them into a new data structure.

[loud trail]

That's what i meant, sorry

If you aren't constrained by storing an extra few million integers

[loud trail]

The for loop with range and continue might be faster

I might want to experiment with this. Can you share an algorithm to generate some sample data? Or better yet share the full code if you can

[edgy otter]

Sent you a friend request. Working on Collatz Conjecture which is one of the long standing unproven conjecture 🙂 So if this thing works it would be a pretty big break through.

[loud trail]

Would be pretty cool to see "Salt Rock Lamp" as a coauthor on one of the greatest discoveries in mathematics

[edgy otter]

Lol stupid veritasium video got me started on the darn thing 🙂 Then I noticed a pattern to the numbers which hasn't been documented yet.

[meager slate]

can i ask what you're doing? are you brute forcing a lot of numbers to find a counter example?

[edgy otter]

A number that either goes up indefinitely or one that exists in a set that forms it's own loop that doesn't go to 0

[edgy otter]

I have spotted a pattern in the recurrence of the drop times for the numbers that allows me to calculate every other number that will fall into that pattern.

[meager slate]

ooo thats interesting

is it some secret sauce you're not supposed to share?

[edgy otter]

Not really it is just me in my home office working on this for fun but if this does make a break through kind of hard to make sure you get credit for it if everyone knows about it before you publish lol. 🙂

[edgy otter]

That said I am totally cool with sharing the "secret sauce" with a controlled group of people 🙂

[meager slate]

sure, as you wish 😄

[edgy otter]

Right now the code is working just slowly 🙂 And it has eliminated 98.6% of all numbers in the first 84 million calculations.

[meager slate]

i'd expect slowness if you're doing it in python

[edgy otter]

Which isn't surprising since we know every number from 2^68 drops to 0

[meager slate]

c++ with a bigint library should absolutely smoke python here

damn thats big

[edgy otter]

I haven't written c++ in 20 years lol. Did they increase their decimal precision as well?

[meager slate]

no as i said, you'd need a bigint library

[edgy otter]

right

[meager slate]

unsigned long longs would be till 2**64 - 1

[edgy otter]

Yeah I think that if there is a set of numbers that breaks Collatz it is supposed to be in the 2^300 range based on current estimates. Way too many numbers to brute force considering the base function for one number can take tons hundreds of steps.

[meager slate]

you should really get in touch with some math guy

looks like you've got some nice method

[edgy otter]

Been reaching out in math forums as well 🙂

[meager slate]

nice

i imagine you'd get a lot more benefit doing this in c++

since the collatz conjecture isn't that complicated

it shouldn't be very tough to learn the parts that matter to you

[edgy otter]

Yeah I might convert over to that if things start to get too painful lol

Yeah it is mostly remembering it 🙂

[meager slate]

currently, how much time does it take for your programs to run?

i'd expect c++ to bring a minimum 20-30x speedup in a hot loop

maybe even 100x who knows

[edgy otter]

getting through about 10k calcs in 4 seconds

[meager slate]

hmm

[edgy otter]

The list of patterns is over 1.5 million

[meager slate]

could you share some of your code

i'll try to implement a barebones c++ version of it

if not me, someone who is good at c++ could help you

[loud trail]

I was going to do a lisp version 🙂

[edgy otter]

        while any((i - hi) % lo == 0 for lo, hi in intervals_list):
            i += 2

        steps_cnt, breadcrumb = steps(i)
        list_cnt += 1
        try:
            intervals_list.append([steps_table[steps_cnt], i])
            percent = percent + (Decimal(1) / Decimal(steps_table[steps_cnt]))
            f.write(str(i) + "," + str(steps_table[steps_cnt]) + "\n")
        except KeyError as ke:
            print(str(steps_cnt))
            print(i)
            return```

that is the main method

[meager slate]

hmm

first step is finding a bigint library

[edgy otter]

yeah that percent is currently at 0.9862984213056635027949356446304206832191582243310264246787243489015748155471579408691581261133107593719744557602463422484109384456772992348693008875920559421401367758198152657226957852793629601629744236454122393392357930308402127373603903796769895659519093315287660355920745034119140954147067977811670518017628392375827986202915399608671942477400307325297035276889801025390625

[meager slate]

whats this number

[edgy otter]

that is the precision to the decimal to know how close it is to finding all the patterns

some of them repeat once every 680564733841876926926749214863536422912 integers...

[meager slate]

holy cow

[edgy otter]

yeah it gets freaking stupid which is why things appear random

Also why I chose python cause I know that it will just get as big as it needs 🙂

Still need to figure out the correlation between the drop times and the starting integers. I don't see a pattern there yet hence the brute force of just finding all the start positions (which hopefully exist in finite space).

[loud trail]

@edgy otter ```python
while n < 10_000_000_000:
n += 2 * sum((n - b) % a == 0 for a, b in intervals_list)

~~this could be a bit faster~~ edit: it's wrong

the more work you let the python runtime do for you in c, the faster things will go

[edgy otter]

hmm interesting would that also reduce the number of times it has to loop through the list?

[edgy otter]

I think that might end up skipping too many numbers. For all but one of the items in the list there will be a remainder (potentially). Maybe I am reading it wrong

[loud trail]

oh you're right, hang on

yep never mind me

what does steps do now?

[edgy otter]

steps runs 3n+1 on a number and calculates the drop time for that number

[loud trail]

and what's the drop time?

[edgy otter]

The drop time is the number of operations it takes f(n) < n

https://oeis.org/A122437

[loud trail]

thanks

[edgy otter]

all possible drop times fall into a(n) = floor(n+(n-1)*(log(3)/log(2))

Also the remaining numbers I am calculating have huge drop times

So I might be able to get some more perf just by changing that up a bit

[loud trail]

there's this version on OEIS:

a(1) = 1, a(n+1) = a(n)+A022921(n-1)+1.

maybe you can do some caching of A022921 values?

[edgy otter]

I do that is what is in the steps table

[loud trail]

ahh

[edgy otter]

combined with the pattern I found to the intervals

[south umbra]

i've decided to start with ds algo , and decided (By ignoring peeps who said py is not for ds algo)that i'll do it by python so can any1 guide me plz?,

[crystal root]

print ("Hello")

print("I am new to this server")

[quiet jay]

can someone explain what happens to a tail pointer in a linked list queue when you dequeue?

obviously the old head is removed and returned

but im just not getting what happens to the tail pointer

[vocal gorge]

It just doesn't change, unless the queue only has one element and the head and tail are the same (in which case you should probably null out both of them, to represent an empty queue).

[quiet jay]

the problem seems to be that the head is None but then the tail doesn't update in a 1 length queue

not sure how to implement it

[vocal gorge]

the head shouldn't be None either unless the queue is empty

[quiet jay]

Failed example:
    print(q.tail)
Expected:
    None
Got:
    <__main__.Node object at 0x000002097DAB87C0>```

this is the error im getting

wait its not even dequeue

in a empty queue self.tail is not None

its a Node

I got it

[south umbra]

do anybody have resource of dsa with py not a pdf or something vid lectures + quiz+ docs too

why r ppl not showing us practical of ds algo

[trim fiber]

How about pinned messages?

[south umbra]

I saw its all docs

N books

[trim fiber]

Try Introduction to Algorithms by T. Cormen

[south umbra]

It's in python? Right

[trim fiber]

Hmm, as far as I remember nope

It's a book about data structures at all

Programming language is just an addon

[south umbra]

Ohh

[tacit canyon]

am i alloud to ask coding questions in this chat ?

hey I'm trying to learn the Floyd Algorithm.
I found an implementation of the Floyd Algorithm on the website GeeksforGeeks(https://www.geeksforgeeks.org/floyd-warshall-algorithm-dp-16/)
So I tried to implement it off-head ...
Is this implementation OK? Because I left out some parts of the original implementation.

INF = 999999
graph = [[0,2,INF,1],
        [1,0,3,INF],
        [INF,1,0,5],
        [INF,4,16,0]]


def myFloydAlgorithm(graph,vertex):
    shortestGraph = graph
    V = vertex
    for i in range(V):
        for k in range(V):
            for j in range(V):
                shortestGraph[i][j] = min(shortestGraph[i][j],
                                          shortestGraph[i][k]+
                                          shortestGraph[k][j])
    printMatrix(graph)
    return shortestGraph
def printMatrix(graph):
    for row in graph:
        print(row)

myFloydAlgorithm(graph,4)

[random hornet]

hey there i want to remove left direct and indirect recursion from grammar ( context : compiler designing ) how to code it in python

@oblique panther

[oblique panther]

what

I haven't made a compiler

[random hornet]

okay np , thanks for replying

i think we can add the channel for this topic ? @oblique panther

[oblique panther]

I'm not sure

[loud trail]

@random hornet compiler stuff i think belongs here, but "how do i X in python" questions don't tend to attract a lot of answers

[old rover]

def merge_sort(a_list):
  if len(a_list) > 1:
    mid_point = len(a_list)// 2
    left = a_list[:mid_point]
    right = a_list[mid_point:]

    #recursive call on each half
    merge_sort(left)
    merge_sort(right)

    #two iterators for traversing both halves
    i = 0
    j = 0

    #Iterator for the main list
    k = 0

    while i < len(left) and j < len(right):
      #while 0 is less than the length of the left and 0 is less than the length of the right
      if left[i] <= right[j]:
        #value from the left half has been used
        a_list[k] = left[i]
        #move the iterator forward
        i += 1
      else:
        a_list[k] = right[j]
        j += 1
      #Move to the next slot
      k += 1
    
    #assembling new list from partitions

    while i < len(left):
      a_list[k] = left[i]
      i += 1
      k +=1
    
    while j < len(right):
      a_list[j] = right[j]
      j += 1
      k += 1
  
  return a_list

print(merge_sort([2,9,8,3,99,50]))

alright i'm a bit confused

this returns [50, 99, 50, 3, 99, 50]

it's not supposed to do that

ah fuck it i don't need help

i didn't like the implementation in the first place

[austere sparrow]

@old rover Write a separate function that merges two sorted lists

oh, you're making an in-place sort

[old rover]

yeah the implementation i wrote five months ago

was way better

i'm just gonna look at that

i'm a bit confused by [:]

if you do [5:]

does it go to the end of whatever you're trying to slice?

like if you do [:5] it starts at 0 and goes till 5 but stops at 4 right?

[slender notch]

How to find good GitHub repository related with data python and algo practice ?

[fiery cosmos]

guys can anyone help me

hey I'm new to python and I have a question:

this is my code

i = 1
for i in range(5):
  i = i**i
  print(i)

and I was wondering why the output is always:

1
1
4
27
256

[mint jewel]

0 ** 0 == 1 (don't think about it too much)
1 ** 1 == 1
2 ** 2 == 4
3 ** 3 == 27
4 ** 4 == 256

[fiery cosmos]

thx

[austere sparrow]

I think I just lost the Game

[mint jewel]

oh no

[austere sparrow]

hehe

[old rover]

is it bad that i can only do three pomodoros of coding a day

that's only like an hour and 15 minutes

it's a productive hour and 15 at least

algos and data structs are draining

[muted shoal]

I don't think so, programming takes a lot of mental energy to constantly resolve new problems and come up with new solutions.

[mint jewel]

I know mathematicians who only research 4 hours a week, because anything more just yields to worse results

don't worry about it

[dapper sapphire]

I imagined people would build up momentum and stamina to be able to think on complexed problems for hours

[mint jewel]

generally no, your mind get faster, but also gets exhausted faster

[south umbra]

oo

hello sir can u tell me from where i can get good vid lecture (no one is showing by writing code all are teaching in board) i want a course of dsa in py in which teacher teachs while really showing things not only by writing @mint jewel

[mint jewel]

I don't know of one

[south umbra]

how u learned

[mint jewel]

I read pseudocode on wikipedia and wrote it in python

[south umbra]

wow

[fiery cosmos]

Looks like https://youtu.be/09_LlHjoEiY shows code examples ... or pseudocode

[austere sparrow]

yeah, the answer is "it depends" or "it's usually undefined" 🙂

This is probably my favourite edge case:
For all non-empty sets A to B, there are|B|^|A| functions from A to B.
If A is empty but B isn't, there's one function, just like anything^0 = 1
if B is empty but A isn't, there are zero functions, just like 0^anything = 1
However, if A and B are both empty, then there's a single function A -> B. So in this context, 0^0 = 1

i.e. {} ^ {} = {{}}

[mint jewel]

depending on context, different definitions are useful

[fiery cosmos]

Hey, is there a way to get the points which are the furthes apart in a multi-dimensinal env?PS: It doesn't has to be perfect

[mint jewel]

what to you mean by furthest apart?

[fiery cosmos]

the distance between those too points should rly huge

but it's in a env which has a border

[mint jewel]

are the points grid aligned?

[fiery cosmos]

yes

[mint jewel]

the best solution I can find online is build a convex hull, then take that hull and compute all pairwise distances

[fiery cosmos]

ok thx didn't find that on my research

[mint jewel]

but I have never seen a Nd convex hull solver, so I hope it isn't too insane

[fiery cosmos]

ty. it might be a bit more than just 3d

[mint jewel]

good luck!

[golden sparrow]

why is v necessary for the minimax alg

[loud trail]

it sounds like they're using it for dynamic programming

example:

def dynamic_max(values):
    max_val = math.inf
    for value in values:
        if value > max_val:
            max_val = value
    return max_val

in their notation, it looks like v is the max_val

[raven geode]

yo is anybody good at linked binary trees?

i need help debugging ?

[south umbra]

https://youtu.be/8hly31xKli0
Is this good for a guy who's new to dsa and wanted to do it in visual way not my books

New to ds algo but intermidiate in python and
Good at Development

[south umbra]

The thing is I'm a school student my maths is not that good and I've working on python from a long time i just Learned all the topics then gone to flask and then too django and rest Framework n all
But now as I'm good in development i wanted to inhance my logical/problem solving ability more and increase my connection to foundations of python too
Before time i was thinking python isn't a gr8 choice for ds algo but then after some experts suggestion I choosed python for ds algo as I'm a kid i dont like too read books n all the board work i like practical things like vids and lol bit docs
And guess what there are very less resources to learn ds algo in py

[ivory yacht]

Data structures and algorithms aren't programming language specific, they apply to any language really. The only difference in a course teaching with the language is any examples they give.

It's not too math heavy, there's a bit of math involved in accurately determining time/space complexity, but usually we estimate the rough shape of the graph.

[vernal estuary]

https://www.hackerrank.com/challenges/compare-the-triplets/problem

can someone help me with this?

[runic tinsel]

there's no trick here

learn to zip or remember how to index

[trim fiber]

Like @runic tinsel said, you can use zip or enumerate

!d zip

[halcyon plank]

zip

zip(*iterables)```
Make an iterator that aggregates elements from each of the iterables.

Returns an iterator of tuples, where the *i*-th tuple contains the *i*-th element from each of the argument sequences or iterables. The iterator stops when the shortest input iterable is exhausted. With a single iterable argument, it returns an iterator of 1-tuples. With no arguments, it returns an empty iterator. Equivalent to:

Similar names: 2to3fixer.zip

[trim fiber]

!d enumerate

[halcyon plank]

enumerate

enumerate(iterable, start=0)```
Return an enumerate object. *iterable* must be a sequence, an [iterator](https://docs.python.org/3/glossary.html#term-iterator), or some other object which supports iteration. The [`__next__()`](https://docs.python.org/3/library/stdtypes.html#iterator.__next__ "iterator.__next__") method of the iterator returned by [`enumerate()`](https://docs.python.org/3/library/functions.html#enumerate "enumerate") returns a tuple containing a count (from *start* which defaults to 0) and the values obtained from iterating over *iterable*.

```py
>>> seasons = ['Spring', 'Summer', 'Fall', 'Winter']
>>> list(enumerate(seasons))
[(0, 'Spring'), (1, 'Summer'), (2, 'Fall'), (3, 'Winter')]
>>> list(enumerate(seasons, start=1))
[(1, 'Spring'), (2, 'Summer'), (3, 'Fall'), (4, 'Winter')]
```  Equivalent to...

[vernal estuary]

thanks

i was trying to avoid zip because i never learned it perfectly tbh

[trim fiber]

zip is very easy!

!e

x = [0, 1, 2]
y = ["a", "b", "c"]
z = list(zip(x, y))
print(z)

[halcyon plank]

@trim fiber :white_check_mark: Your eval job has completed with return code 0.

[(0, 'a'), (1, 'b'), (2, 'c')]

[runic tinsel]

for index in range(3):
   a_score = alice_scores[index]
   b_score = bob_scores[index]
   rest of the loop
```when you avoid zip, you do this

yeah, there's like no reason to avoid zip, you still have to zip, you're only avoiding typing the word itself I guess

[rain viper]

Hey algo friends

[wind bluff]

for x in loop:
  .... o(n)

for y in loop:
  .... o(n)

if I have 2 loops right after each other like this, is it still o(n) i.e does o(n) + o(n) = o(n)?

[knotty magnet]

yes

[austere sparrow]

Yes, O(2N), O(N + log(N)), O(420N + 69), O(N) are all equivalent.

[coarse stump]

i understand

[golden sparrow]

Im having a hard time implementing alpha beta pruning I get the concept but it stops making sense when I try to program it

[fair prairie]

Any resource to learn dsa in python

[knotty magnet]

check the pins

[keen hearth]

Are you confident you understand the idea behind alpha-beta pruning? And are you implementing the algorithm recursively?

[golden sparrow]

I think so and yes

[meager slate]

check out the alpha beta reference implementation on wikipedia

function alphabeta(node, depth, α, β, maximizingPlayer) is
    if depth = 0 or node is a terminal node then
        return the heuristic value of node
    if maximizingPlayer then
        value := −∞
        for each child of node do
            value := max(value, alphabeta(child, depth − 1, α, β, FALSE))
            if value ≥ β then
                break (* β cutoff *)
            α := max(α, value)
        return value
    else
        value := +∞
        for each child of node do
            value := min(value, alphabeta(child, depth − 1, α, β, TRUE))
            if value ≤ α then
                break (* α cutoff *)
            β := min(β, value)
        return value

ripped off from wikipedia

this helped me a lot in implementing it properly

[shell knoll]

Hello

I have a string representation lf bytes

And i want it to be converted into bytes, not a string

Do you know how to do it?

[runic cobalt]

@shell knoll Caveat, I wrote my first Python code less than a week ago, so verify everything I offer -- and this will perhaps do until some expert helps you:
Python has 'byte strings': b'I am a string'.decode('ASCII')
You can encode and decode them from character strings, with limitations since normally Python uses Unicode for characters. However any strictly ASCII code will be valid Unicode.
This question and the answer with >500 upvotes will get you started probably, but be sure to read the Docs or a more detailed answer:
https://stackoverflow.com/questions/6224052/what-is-the-difference-between-a-string-and-a-byte-string

Now that you know the keyword to search you probably can find what you need. byte string

>> type(b'this is a bytes string')
<class 'bytes'>

[shell knoll]

I did not explain correctly, and i got my question answered here:

#help-croissant message

Today 2021/08/12 at 16:16 Madrid time

[old rover]

  # placeElement is the value of the current place value
    # of the current element, e.g. if the current element is
    # 123, and the place value is 10, the placeElement is
    # equal to 2
    for i in range(inputSize): 
        placeElement = (inputArray[i] // placeValue) % 10
        countArray[placeElement] += 1

i'm a bit confused

place element is a number in the input array

what is the place value?

the specific place used to sort the numbers?

[knotty magnet]

what's the context for this code

[old rover]

def countingSortForRadix(inputArray, placeValue):
    # We can assume that the number of digits used to represent
    # all numbers on the placeValue position is not grater than 10
    countArray = [0] * 10
    inputSize = len(inputArray)

    # placeElement is the value of the current place value
    # of the current element, e.g. if the current element is
    # 123, and the place value is 10, the placeElement is
    # equal to 2
    for i in range(inputSize): 
        placeElement = (inputArray[i] // placeValue) % 10
        countArray[placeElement] += 1

    for i in range(1, 10):
        countArray[i] += countArray[i-1]

    # Reconstructing the output array
    outputArray = [0] * inputSize
    i = inputSize - 1
    while i >= 0:
        currentEl = inputArray[i]
        placeElement = (inputArray[i] // placeValue) % 10
        countArray[placeElement] -= 1
        newPosition = countArray[placeElement]
        outputArray[newPosition] = currentEl
        i -= 1
        
    return outputArray

def radixSort(inputArray):
    # Step 1 -> Find the maximum element in the input array
    maxEl = max(inputArray)

    # Step 2 -> Find the number of digits in the `max` element
    D = 1
    while maxEl > 0:
        maxEl /= 10
        D += 1
    
    # Step 3 -> Initialize the place value to the least significant place
    placeVal = 1

    # Step 4
    outputArray = inputArray
    while D > 0:
        outputArray = countingSortForRadix(outputArray, placeVal)
        placeVal *= 10  
        D -= 1

    return outputArray
    
input = [2,20,61,997,1,619]
print(input)
sorted = radixSort(input)
print(sorted)

radix sort

[old rover]

def insertion_sort(a_list):
  list_len = len(a_list)
  for i in range(1, list_len -1 ):
    j = i
    while j > 0 and a_list[j-1] > a_list[j]:
      a_list[j], a_list[j -1] = a_list[j-1], a_list[j]
      j = j-1

what's the point of saying while j >0?

as in the index is bigger than zero?

oh i think i know

bc you don't want to mess with the zeroth element and you want to focus on the elements past that index?

def bucket_sort(input_list):
    # Find maximum value in the list and use length of the list to determine which value in the list goes into which bucket 
    max_value = max(input_list)
    size = max_value/len(input_list)

what do they mean by size?

if you had a list of [5,10,2]

the size would 3.3333

size of the list??

maybe it'll be clear as i go further

[lament quiver]

Hello, has anyone read this book? I have doubts from the last 2 days which I am unable to tackle..
https://pragprog.com/titles/jbmaze/mazes-for-programmers/

or if anybody has any good resources on Mazes generation using python, please do share!

[fiery cosmos]

!e idk if this counts as a resource but here's a simple maze generator I happen to have on hand ```py
import random
def maze(width, height=None, wall=u"\u2588\u2588", space=' '):
def is_space(x, y):
return x < 0 or x >= width or y < 0 or y >= height or grid[y][x] == space

if height is None:
    height = width

grid = [[wall for _ in range(width)] for _ in range(height)]
if width > 2 and height > 2:
    start = random.randint(1, height - 2)
    grid[start][0] = space
    fringe = [(1, start)]
    visited = set()

    while fringe:
        index = random.randrange(len(fringe))
        x, y = fringe.pop(index)
        visited.add((x, y))

        neighbors = (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)
        spaces = [is_space(nx, ny) for nx, ny in neighbors]

        # Valid if only neighboring one space.
        if sum(spaces) == 1:
            grid[y][x] = space

            # Potentially continue path on all non-space neighbors.
            for n, s in zip(neighbors, spaces):
                if not s and n not in visited:
                    fringe.append(n)

    ends = [y for y in range(1, height - 1) if grid[y][-2] == space]
    end = random.choice(ends)
    grid[end][-1] = space

return '\n'.join(''.join(row) for row in grid)

print(maze(40, 17))```

[halcyon plank]

@fiery cosmos :white_check_mark: Your eval job has completed with return code 0.

001 | ████████████████████████████████████████████████████████████████████████████████
002 | ██  ██    ██████  ██    ██    ██  ██████    ██    ██            ████      ██████
003 | ██      ██  ██        ██  ██        ██  ██    ██  ██  ██  ████        ████  ████
004 | ████  ██      ██  ██      ██  ██  ██      ██  ██  ██    ██      ████          ██
005 | ██      ████    ██████  ██      ██    ██████  ██      ████████████    ████  ████
006 | ████  ██    ██    ██    ████  ██    ██            ████  ██        ██      ██████
007 | ██      ██  ██  ██  ██    ██  ████      ████  ██  ██    ████  ████████  ██  ████
008 | ██  ████    ██  ██    ██        ██  ██      ██        ██      ██  ██  ██      ██
009 | ██    ██  ██    ██  ██  ████  ██      ████    ██  ██    ██  ██            ██  ██
010 | ██  ██      ██  ██                ████    ██  ██  ████          ██  ██  ██    ██
011 |         ██          ██  ████  ██████  ██  ██  ██    ██  ██  ██    ██  ██  ██████
... (truncated - too many lines)

Full output: https://paste.pythondiscord.com/onegiremay.txt?noredirect

[lament quiver]

Thank you! Actually, I had developed generators, simple and multipath ones, the issue is the cell blocks are linked to each other, but sometimes they didn't get link properly. If you or anyone can look into the source code, that would be really appreciated! I tried everything and now i am on the verge of giving up 😞

[halcyon plank]

Hey @lament quiver!

It looks like you tried to attach a Python file - please use a code-pasting service such as https://paste.pythondiscord.com

[lament quiver]

https://paste.pythondiscord.com/meropihoqi.py

[stable pecan]

!e

import numpy as np, networkx as nx

G = nx.grid_graph((5, 5))
for e in G.edges: G.edges[e]['weight'] = np.random.random()
maze = nx.algorithms.minimum_spanning_tree(G)
array = np.full((11, 11), "█")
for u, v in maze.edges: array[tuple((2 * i + 1, i + j + 1, 2 * j + 1) for i, j in zip(u, v))] = " "
array[(0, -1), (1, -2)] = " "
print("\n".join(map("".join, array)))

[halcyon plank]

@stable pecan :white_check_mark: Your eval job has completed with return code 0.

001 | █ █████████
002 | █   █ █   █
003 | ███ █ █ █ █
004 | █     █ █ █
005 | █ █████ █ █
006 | █       █ █
007 | █ █ ███████
008 | █ █ █     █
009 | ███ █ ███ █
010 | █       █ █
011 | █████████ █

[stable pecan]

cheap way to leverage networkx to create a maze for you

[fiery cosmos]

using libraries to be more efficient

!e ```py
import numpy as np, networkx as nx

G = nx.grid_graph((5, 5))
for e in G.edges: G.edges[e]['weight'] = np.random.random()
maze = nx.algorithms.minimum_spanning_tree(G)
array = np.full((20, 13), "██")
for u, v in maze.edges: array[tuple((2 * i + 1, i + j + 1, 2 * j + 1) for i, j in zip(u, v))] = " "
array[(0, -1), (1, -2)] = " "
print("\n".join(map("".join, array)))```

[halcyon plank]

@fiery cosmos :white_check_mark: Your eval job has completed with return code 0.

001 | ██ ██████████████████████
002 | ██                  ██████
003 | ██████  ██████████████████
004 | ██          ██      ██████
005 | ██████████  ██████  ██████
006 | ██                  ██████
007 | ██████  ██████  ██████████
008 | ██  ██      ██      ██████
009 | ██  ██  ██  ██████  ██████
010 | ██      ██      ██  ██████
011 | ██████████████████████████
... (truncated - too many lines)

Full output: https://paste.pythondiscord.com/alenororev.txt?noredirect

[fiery cosmos]

I broke it

I was confused what the (5, 5) was for

[lament quiver]

ohh that looks good, thank you! will look into networkx

[keen hearth]

Well it's initially ```
███████████
█ █ █ █ █ █
███████████
█ █ █ █ █ █
███████████
█ █ █ █ █ █
███████████
█ █ █ █ █ █
███████████
█ █ █ █ █ █
███████████

Which appears to give nice solid-looking walls.

[dapper sapphire]

How are you guys able to generate these mazes out of thin air!?

[keen hearth]

I think salt-die is a wizard 👀

But actually, they're connecting all adjacent cells with random-weighted edges, then using networkx to find the 'minimum spanning tree'.

[lament quiver]

yeah, maze is a binary tree

[keen hearth]

Which means you can always solve mazes generated this way by hugging the wall on your right 😄

Because no loops.

[dapper sapphire]

Does it have to be right wall, can we use left wall instead?

[keen hearth]

Yeah either, as long as you pick one and stick to it. A helpful tip if you ever find yourself lost in a hedge-maze.

[dapper sapphire]

ok

[mighty onyx]

can someone help me with this problem

this is what I have right now

[night lichen]

1. Covert tree into single dict with sequence as key and decide msg as value
   This will give
   dict = {0:a 10:n, 11:b}
   Dmsg = ''
   for i in compressed:
   j = j + i
   If j in dict:
   Dmsg = Dmsg + dict[j]
   j = ''

[mighty onyx]

@night lichen

like this?

it didnt work like that

I really appreciate you helping me

[mighty onyx]

how do I convert tree into a single dict

[sage coral]

I have an idea for a path finding algorithm. I’m using A* and I want to train a neural network as the heuristic. What would you recommend I use as inputs to the network? The environment is just a 2d grid with some obstacles

[gaunt tangle]

@stable pecan Do you know how to solve this DP? https://leetcode.com/discuss/interview-question/710305/quora-online-coding-challenge-choosing-shops

[distant sierra]

So I'm making a pathfinder for a small grid-based text input game drawn below, where:

• black lines = travellable roads
• player starts on a road edge and can only move to adjacent road edges (see black dots for example path)
• player starts off with some stats, which decrease every move
• if player is next to a powerup (colored dot), they can use the powerup to increase stats
• game ends after x amount of moves (winning) or you run out of a stat (losing)
• objective: maximize stats by end of game

Right now I'm just planning on looping thru all possible winning solutions and picking the one with highest stats. My question is, how do I even set up the grid when I'm doing calculations? Should I do one big array that has null values for every intersection, or one for the powerups + another for the roads? Either way, I won't end up with arrays with values that don't take up the whole thing, so I'm not sure. I plan to use numpy arrays, but if there's a networking library I can use to make this easier, please suggest it.

[golden sparrow]

I feel like if the wiki page didn't have the pseudocode I wouldnt be able to implement it

[keen hearth]

Am I missing something, or are the days actually independent of one-another? Because the actions you take on day-1 don't appear to have any affect on the actions you would take on day-2.

[keen hearth]

Did you make any progress with the implementation?

[tender atlas]

This is a picture where a shortest path is defined. I need a help of total turning angle calculation

i am able to get two cell node of the turning . But i can not get how many possible of turning point and how to calculated the turning angle from int path

[gaunt tangle]

days are independent as the shops bring in the same amount of quantities of products in the starting of each day.

[somber pivot]

Hi I'm trying to make a text-based game ^^

[tender atlas]

use #game-development

[somber pivot]

thanks

[open flume]

Is anyone a compression wizz here

I'm trying to find more info on block compression

Something like this

but in 3 dimension

So it aggregates similar blocks together into a specified size n chunk, n being a user specified number

[fiery cosmos]

is Heapsort better than mergesort?

[knotty magnet]

maybe in certain cases?

i think mergesort is better in practice in general though

[golden sparrow]

yes i was able to implement it looking at the pseudocode but i dont really understand it

[arctic beacon]

I need to make an algo to find a input() next palindrome. This is fairly simple if you have max 10 digits. Anyone know which angle I need to take for 100+ digits?

for reference: (code)

s = input()

def isPalindrome(n):
    return str(n) == str(n)[::-1]

s1 = int(s) + 1
while not isPalindrome(s1):
    s1 = int(s1)+1
print(s1)

My test cases which are failing are 128+ digits till 1000000 digits

What is reasonable with my algo

[knotty magnet]

i don't see why that would stop working

[arctic beacon]

I mean It takes way too long if you have 200 digits for instance

It will work, but is inefficient with larger numbers

[knotty magnet]

i guess i should have clarified. i'm guessing the tests are failing because TLE?

[arctic beacon]

What's that?

[knotty magnet]

time limit exceeded

[arctic beacon]

yes, that's why it's failing

[fervent saddle]

Isn’t the way it works like, for example, if the number is 12345xxxxx then the next palindrome is 1234554321 if the last half is less than 54321, otherwise it’s 1234664321? Or if the number is 12345xxxxxx, the next palindrome is either 12345xxxxxx or 12345(x+1)xxxxx, assuming the first x isn’t 9?

Maybe that’s wrong

But I’m pretty sure there’s some formula for it which could make it O(n) with the amount of digits

[arctic beacon]

It should be fine... Is there any way there could be another palindrome in between the mirrored version of the first half? I don't think so. I will try to implement this. Thanks

hmmm, I would suck if the length of the number changes... (99 --> 101) this but on a bigger scale

bc 99 is a palindrome, 100 isn't, 101 is

[fervent saddle]

I wonder if you’ll ever have to deal with that since all 9s is a palindrome

If the input is all 9s then I guess you would

Then the palindrome would be whatever you input plus 2

[arctic beacon]

Wait I think this doesn't work, you can't go down in value...

[fervent saddle]

Wdym

I thought you were only increasing it to find the next palindrome

[arctic beacon]

nevermind I didn't read correctly

basically you go from the middle to the start to check if its a palindrome & its greater then first number

[fervent saddle]

Yeah

[fiery cosmos]

The hashing function of the first table returns the lowest two bits: h1(x) = x & 0b11. sorry what does this & 0b11 mean? like is & bitwise and? that doesnt make sense to me how does this equation get the last two bits

yeah, & is bitwise and, and 0b11 is 3 in binary. When you do something & 00000011 (leading zeros for effect) you end up with the last two bits of something

ohhhh

ya because only where it's 1 you get the output got it

>>> bin(2 & b)
'0b10'
>>> bin(3 & b)
'0b11'

neat!

[lean dome]

3 & x is equivalent to x % 4, at least for non-negative integers

[tender atlas]

#algos-and-data-structs message

Need a help. Yesterday message

[keen hearth]

Hello. The question isn't entirely clear. Is there more information you could provide?

[tender atlas]

Question is to calculate the total turning angle in rad.

Answer should be 6.2832

[keen hearth]

I came up with this implementation that might make it a bit clearer: ```py
INF = float('inf')

def mini(state, alpha=-INF, beta=INF):
if is_terminal(state):
return utility(state)
for successor in successors(state):
if alpha >= beta:
break
beta = min(beta, maxa(successor, alpha, beta))
return beta

def maxa(state, alpha=-INF, beta=INF):
if is_terminal(state):
return utility(state)
for successor in successors(state):
if alpha >= beta:
break
alpha = max(alpha, mini(successor, alpha, beta))
return alpha

`alpha` is the current best (i.e. maximum) score for the maximising agent in all ancestor nodes.
`beta` is the current best (i.e. minimum) score for the minimising agent in all ancestor nodes.
Values less than or equal to `alpha` don't matter -- the maximising agent will reject them, as they've already found something at least as good.
Values greater than or equal to `beta` don't matter -- the minimising agent will reject them, as they've already found something at least as good.
So if at any point while considering the successors of a node, `alpha >= beta`, then the remaining successors don't matter, as their values have to be either at least as large as `beta`, or at least as small as `alpha`.

[keen hearth]

By turning angle, do you mean the total amount by which the agent turns in either direction over the entire path?

[magic tapir]

it runs and get close automatically after running

[tender atlas]

yes all angle of agent turns

[keen hearth]

Sorry, this was meant to be a reply to your message @golden sparrow

[keen hearth]

Right, so it looks as if it can move diagonally or vertically. So any turn is a multiple of 45 degrees (pi/4 radians).

[tender atlas]

I was calculating by using two coordinates

i mean by slope and convert it to tan for each turn agent

[keen hearth]

Oh, that was a reply to the person asking about minimax search, sorry!

[tender atlas]

but i am failed to get exact result

[tender atlas]

its ok. my fault

[keen hearth]

How is a path represented?

[tender atlas]

path is represented with 4 neighbor or 8 neighbor.

[keen hearth]

I mean, in Python what would it look like?

E.g. a list of coordinates?

[tender atlas]

yes

a list of coordinates entire of the path

[keen hearth]

Sorry, responding to something...

[tender atlas]

the path was found by using dijskra

[keen hearth]

Right. For example [(3, 4), (3, 5), ...]?

[tender atlas]

yes

[keen hearth]

Why don't we invent our own units of angle, where 1 unit = 45 degrees.

[tender atlas]

each unit cell to 45 degree?

[keen hearth]

Well it seems the total turning angle going to be a multiple of 45 degrees. It will make things nicer to use integers for the angles.

[brave oak]

like gradians?

[tender atlas]

what will you say when its 4 neigbour based?

[keen hearth]

In that case it would be a multiple of...?

[tender atlas]

90

[keen hearth]

Yep

For the 8-neighbour version, you could imagine labelling the eight points of the compass from 0 to 7. Then if you want to get the (positive) turning angle between two directions, you take the difference of these numbers modulo 8.

[tender atlas]

https://tenor.com/view/stanley-sleeping-the-office-gif-10555880

Let me try now

[keen hearth]

Right ok 😄

[pseudo sapphire]

Can i have help pls

[fiery cosmos]

shh black

[granite folio]

with regards to data structures, is it fair to say that most if not all implementations of graphs will take the form of adjacency lists? (ie adjacency matrix etc. won't be used in terms of interview problems etc. ?)

[vocal gorge]

<@&831776746206265384>

[austere sparrow]

!rule 5 Hello @inner wagon, we cannot help you with this project as it likely breaks international law

[halcyon plank]

Rules

5. Do not provide or request help on projects that may break laws, breach terms of services, or are malicious or inappropriate.

[bold lake]

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        if not prerequisites:
            return 1
        visited = [0 for i in range(numCourses)]
        
        courses = [[0]*numCourses for i in range(numCourses)]
        
        for i, j in prerequisites:
            courses[i][j] = 1

        cycle  = 1 
        
        for i in range(numCourses):
            for j in range(i + 1, numCourses):
                if courses[i][j] == 1 and courses[j][i] == 1:
                    cycle  = 0
                    break
        return cycle            
                    
            ```

why is this wrong?

approach is: find cycle in graph

that in a directed graph is when mat[i][j] == mat[j][i]

[vocal gorge]

that in a directed graph is when mat[i][j] == mat[j][i]
No? That's a very simple cycle (on only two vertices), but there can be far longer cycles.

[slender sparrow]

One message removed from a suspended account.

One message removed from a suspended account.

[raven kraken]

Can someone help me my solution have passed half of the cases and failing on "leetcode"

[knotty magnet]

are you sure you're supposed to return a string there

[tranquil barn]

Can someone help me in #help-orange

[golden sparrow]

yea it did make it a lot clearer lol thank you

[tawdry whale]

dont return a string

also you should check if len(s) == 26

[tawdry whale]

also the range check is unnecessary

[keen hearth]

Bear in mind that this implementation is a little bit different from the standard one. It will return (I think) the correct mini-max value for the root node, but the intermediate results returned by the recursive calls aren't necessarily the same as they would be for the standard algorithm.

But it uses the same idea for the pruning.

[halcyon plank]

:incoming_envelope: :ok_hand: applied mute to @lavish lark until <t:1628994681:f> (9 minutes and 59 seconds) (reason: burst rule: sent 10 messages in 10s).

[fiery cosmos]

https://upload.wikimedia.org/wikipedia/commons/f/f0/Adjacency_List_variation_one.png

why isnt it (v) -> f e

isnt it missing the e edge?

from https://en.wikipedia.org/wiki/Adjacency_list

[half lotus]

I normally see lists store vertices rather than edges. I can't really make sense of this example either. It's missing edge e for vertex v and edge f for vertex w yet it has no problem including edge h in both vertices w and z.

The caption says

The sequence contains all the vertex which stores the list of all edges that it connects to.

But that is clearly not the case.

[fiery cosmos]

weird lemme check my textbook maybe it's just bad wiki article

[half lotus]

The addition of this image to the article is in fact the most recent change to the article, done just last week.

I think it's just a case of a bad edit.

[fiery cosmos]

ya that's weird that they made such a bad edit lol

[half lotus]

A coincidence that your book uses the same graph 🤔

[fiery cosmos]

ya it's... literally the same lol
its data structures and algos in python

[ivory iron]

Hi.

Did anyone ever use Spotipy?

[arctic beacon]

Hey guys. I have this exercise to find the max gcd pair out of 2 lists. I have a working algorithm, but this is waaaaay to slow for big data (list size 1≤N≤500000 and list elements 1≤ai,bj≤1000000). Could anyone give some tips to make it more efficient? I tried simplifying the list size and some other tricks, but they don't seem to work. here is the code: https://pastebin.com/d3Qvw4cp

Any help is appreciated !

basically I have TLE error with the bigger lists

[meager slate]

i believe you're checking all possible combinations

[arctic beacon]

Yeah, I am.

All unique combinations

(2,1) and (1,2) is not unique for instance

[meager slate]

you have to realise a property of gcd is gcd(n, multiple of n) is n

does this ring some bells for you?

now you have to find the maximum number in the array that has its multiple in the same array

[arctic beacon]

Oh ok, so If I just remove all but 1 of multiple's of n in unique_combinations then it will be way faster?

and that one needs to be the biggest

[meager slate]

also i looked at your code

you want to check alll pairs of numbers right?

 for i in range(len(nums)):
     for j in range(i+1, len(nums)):
       ...
``` is a good way to check all pairs

[arctic beacon]

Well I need to find the biggest gcd of a pair while the sum of that pair is max

[meager slate]

oh i see

can you give a link to this problem

i'll try to solve this myself

[arctic beacon]

so if 2 pairs have the same gcd, then I need to print the sum of biggest pair

[arctic beacon]

It's a university website, but i'll make a pastebin for you

[meager slate]

oh

[arctic beacon]

https://pastebin.com/rP4grjhs

[arctic beacon]

^

[meager slate]

i'll take a look

let me try a naive brute force

from math import gcd

def max_gcd_pair(La, Lb):
     max_pair = La[0], Lb[0]
     max_gcd = gcd(*max_pair)
     n = len(La)

     for i in range(n):
         for j in range(n):

             a,b = La[i], Lb[j]
             pair_gcd = gcd(a,b)

             if pair_gcd > max_gcd:
                 max_pair = a,b
                 max_gcd = pair_gcd

             elif pair_gcd == max_gcd:
                 if a+b > max_pair[0] + max_pair[1]:
                    max_pair = a,b

     return max_pair

i don't if O(n^2) is good enough

[last cosmos]

is overhead accounted for in the big O notation?

[knotty magnet]

it's not n^2, gcd is logn

[knotty magnet]

wdym overhead?

[meager slate]

n^2 + log(n) is still n^2

[knotty magnet]

right, but then how does your logic come up with n^2

[meager slate]

2 nested loops

[arctic beacon]

brute force will work for smaller lists, but will 100% get a TLE error for the bigger lists

[knotty magnet]

and a gcd is nested inside both of them

and also, max_gcd is unlikely to actually find the max gcd

[meager slate]

why would be that?

[knotty magnet]

!e

from math import gcd
print(gcd(1, 100, 100))

[halcyon plank]

@knotty magnet :white_check_mark: Your eval job has completed with return code 0.

1

[knotty magnet]

if i understand the problem correctly, the answer here would be 100, not 1

[meager slate]

i'm taking the gcd of pairs here

[knotty magnet]

ah shit, sorry i'm wrong. i read your code wrong

you're right. although you do duplicate work there since you calculate that on the first iteration anyway

[meager slate]

also, about your gcd comment, gcd doesn't scale with the size of the inputs, but rather with the size of the integer itself, i don't think it should be counted as log(n)

[knotty magnet]

hm, you're also right about that 🤔

should be n^2 * log(A)

[meager slate]

does it TLE @arctic beacon

[meager slate]

since A is guaranteed to be less than a 32 bit integer, i think we can neglect it as O(1), no?

[arctic beacon]

I am changing your algo, bc input() is a String. give me a sec

[knotty magnet]

is it? i didn't read the problem

huh, yeah you're right

actually those constraints are quite generous, i'd be surprised if that brute force TLEd

[meager slate]

pretty sure there has to be better way than naive brute forcing

let me search on this topic

[meager slate]

but this is python here, so i'd keep my fingers crossed 😅

[arctic beacon]

yes.

Let me send my changes.

[meager slate]

:(

thats to be expected, it was a naive brute force 😔

[arctic beacon]

from math import gcd

def max_gcd_pair(La, Lb):
     max_pair = int(La[0]), int(Lb[0])
     max_gcd = gcd(*max_pair)
     n = len(La)

     for i in range(n):
         for j in range(n):

             a,b = int(La[i]), int(Lb[j])
             pair_gcd = gcd(a,b)

             if pair_gcd > max_gcd:
                 max_pair = a,b
                 max_gcd = pair_gcd

             elif pair_gcd == max_gcd:
                 if a+b > max_pair[0] + max_pair[1]:
                    max_pair = a,b

     return max_pair[0] + max_pair[1]

La = input()
Lb = input()
La = La.split(" ")
Lb = Lb.split(" ")
print(max_gcd_pair(La,Lb))

[arctic beacon]

Your algo went to test case 7, mine went to 5...

so I mean you did better in 5mins, then I did in 2 days ahahhaha

[meager slate]

La is still a list of strings, how does that not give an error?

shouldn't it be [int(x) for x in La.split()]

[arctic beacon]

La is string (ex. La = "1 2 13 15")

[meager slate]

yes, the split would be ['1', '2', '13', '15']

you need to convert everything to an int, no?

[arctic beacon]

yeah, that's what I did

[meager slate]

you converted to int right?

a property of gcd is gcd(n, multiple of n) is n

lets try to use this somehow

[arctic beacon]

This is cleaner, but fails at same TLE

Is there maybe a way to only change to an int if it's needed? Isn't it punishable to change everything to an int in the whole list?

[arctic beacon]

Also if ai or bi in the pair is a prime number then gcd is 1.

[knotty magnet]

you need to check every pair though, so you might as well do them all at the same time

[arctic beacon]

I mean that's the thing, checking every pair is too slow. no?

[knotty magnet]

err, maybe not check every pair, but you have to look at each number

[arctic beacon]

@meager slate The last test case that was successful had a list length of 500. so it's failing >500. and it goes up to 500000.

[arctic beacon]

@meager slate I found something, but my brain can't handle these methods. I have no idea what's happening. https://www.geeksforgeeks.org/find-pair-maximum-gcd-array/

[balmy pawn]

can anybody help me with a simple BST recursion method?

#help-kiwi

[meager slate]

that problem still is slightly different, since both the numbers are from 2 different arrays, but i guess it serves as a good starting point

[jovial sphinx]

when performing a DFS, I can think of two approaches:

• using recursion
• maintaining a stack

The main reason(imo) to use a stack is because one doesn't have to worry about maximum recursion depth, but recursion is much faster.

I'm working on a grid pathfinding algorithm and I'm wondering if there is a way to have the flexibility of the stack approach and the good performance of recursion at the same time?

[knotty magnet]

in python, recursion is slower

so, just use a stack

[faint sentinel]

what is the time complexity of finding total elements in a linked list?

can it be done like say , initialize count = 0 , whenever a insertion takes place , count += 1, and for deletion
, count -= 1 , so it will be a constant time operation O(1) ,

or will it be O(n) , simply by traversing all elements

if you are making a restaurant order app will it be a good choice

[ivory yacht]

Yes, if you added that auxiliary part of the data structure, normally it'd be O(n).

Do you need to insert/remove items in the middle of the list?

[faint sentinel]

can we do it by the other way , initializing a count = 0 , and incrementing and decrementing it

[faint sentinel]

only deletion in middle , no insertions

insertion will be at end only , and in regular flow deletion will b e in beginning only , but if a user cancels a order , in middle or at end , then we have to delete that

anyone here please answer

[gaunt tangle]

How do you people implement multiset <int, greater <int> > ms; in C++ in Python3? (I'd like to see an exact representation of multiset<int,greater<int>>)

[vocal gorge]

In Python one just uses a Dict[int,int], pretty much.

If you need the low memory usage that comes with using that exact data structure, it's not really possible in Python - you'd need to see if there's Python bindings for a multiset library written in C, say.

[gaunt tangle]

can you write some code using Dict[int,int]?

[vocal gorge]

Dict[int,int] is a typehint - it specifies a dict with int keys and int values. It's just a normal dict, though.

multiset = {}
multiset[5] = 5
multiset[2] = 3

If you also need operations like multiset subtraction and the like, you can implement them yourself, or I believe collections.Counter (a class intended for counting things - it's a subclass of Dict[Any, int], essentially) has some implemented

[austere sparrow]

doesn't multiset preserve order?

no, nvm, it's sorted

[vocal gorge]

in C++? that's really weird, a multiset should just be a set with integer counts instead of bool ones, essentially

[gaunt tangle]

dict() in python3 are not sorted.

The multiset that I declared is always sorted in descending order.

[austere sparrow]

@gaunt tangle http://www.grantjenks.com/docs/sortedcontainers/sorteddict.html

[gaunt tangle]

It's a library that someone created not an actual inbuilt python functionality?

I actually wanted something inbuilt in python

[austere sparrow]

No, Python doesn't have built-in sorted containers

I don't think I ever needed one

[jovial sphinx]

Uh no actually I'm writing in python and I wrote a recursion version and a stack version of the same search function. The stack version is SIGNIFICANTLY slower.

[halcyon plank]

@fiery cosmos :white_check_mark: Your eval job has completed with return code 0.

001 | {9: 1, 8: 1, 7: 1, 6: 1, 5: 1, 4: 1, 3: 1, 2: 1, 1: 1, 0: 1}
002 | {0: 1, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1, 6: 1, 7: 1, 8: 1, 9: 1}

[austere sparrow]

Can you show the code?

It preserves order, not sorts

[jovial sphinx]

do you want the full version or just the search functions

[austere sparrow]

Full version would be better, but just the search functions if they make the point clear

!paste

[halcyon plank]

Pasting large amounts of code

If your code is too long to fit in a codeblock in discord, you can paste your code here:
https://paste.pydis.com/

After pasting your code, save it by clicking the floppy disk icon in the top right, or by typing ctrl + S. After doing that, the URL should change. Copy the URL and post it here so others can see it.

[austere sparrow]

Can you please use this?

[jovial sphinx]

oh sry

https://paste.pythondiscord.com/famudufela.pl this is the stack version

https://paste.pythondiscord.com/xeyagufoso.md this is the recursion version

[austere sparrow]

@knotty magnet In the recursive version, you don't deepcopy visited_tiles

[jovial sphinx]

yeah and that's what makes it super slow

[austere sparrow]

but why do you deepcopy it in the stack verision?

ah

no, that's probably not what makes it slow

can you give some test data?

[jovial sphinx]

actually I'll copy the entire 2 scripts

sry it took a while

https://paste.pythondiscord.com/iyejabaliw.py recursion version

all you have to do is run the code

and it'll go through all the (x, y) values from -99 to 99

https://paste.pythondiscord.com/jetoxusitu.py stack version

oh I think you need to remove stuff in input_

wait mb I tried to remove unnecessary stuff in the recursion version but forgot to do that for the stack version

but do u see the difference in efficiency

[austere sparrow]

@jovial sphinx Can you send the version that I can run?

[jovial sphinx]

ok 1 moment this time im only gonna include the search

[austere sparrow]

btw, I'm pretty sure this is not A* 🤔

[jovial sphinx]

dfs?

[austere sparrow]

yes, this is just dfs

[jovial sphinx]

ok

https://paste.pythondiscord.com/iqujeyawih.pl stack version

[gaunt tangle]

But is there a way to tell python how to sort the keys?

[jovial sphinx]

https://paste.pythondiscord.com/ewiwipotor.py recursion version

it's so much faster

[austere sparrow]

No, Python doesn't have built-in sorted collections.

@jovial sphinx what is ```py
if md > previous_distance:
continue

[jovial sphinx]

so the algorithm only calculates paths that always reduce the distance to the center (0, 0) with every rotation

do you need more context to the original problem

[austere sparrow]

Yea

[gaunt tangle]

Alright here is a scenario you have a list [2,1,3,2,4,9] how would you create a sorted dict?
Use keys as the list values and frequency as values to those keys

[jovial sphinx]

so in the original problem:

given a coordinate (x, y) where both x and y are integers between -99 and 99 inclusive, find the shortest path to the centre (0, 0) such that the cube end up having the same side facing up

[austere sparrow]

Why do you need it sorted?

[jovial sphinx]

the hardest part imo is actually to keep track of the state of the cube (which I found an innovative solution for that I believe does not exist on the internet)

[austere sparrow]

I don't think DFS is the right solution here, why can't you just make two straight lines and adjust them depending on the modulo?

[jovial sphinx]

no so

[halcyon plank]

@fiery cosmos :white_check_mark: Your eval job has completed with return code 0.

001 | {1: 1, 2: 2, 3: 1, 4: 1, 9: 1}
002 | {1: 1, 2: 2, 3: 1, 4: 1, 9: 1}

[jovial sphinx]

you start with a cube facing up

and you can roll it in one of the 4 directions

you must find the shortest path such that when it arrives at 0, 0 it's facing up again

[austere sparrow]

so you have to make 4N movements horizontally and 4N movements vertically, right?

[jovial sphinx]

I'm not sure what you mean by 4N

so basically what the search algorithm does is that it goes through each path of length x + y within the rectangle formed by the corners (0, 0) and (x, y)

until it finds a valid path

[gaunt tangle]

You have some cool skills. But can you sort the keys in descending order?

[austere sparrow]

Why do you need them sorted? What's your original problem?

[gaunt tangle]

How do one do that in Python3?

[halcyon plank]

@fiery cosmos :white_check_mark: Your eval job has completed with return code 0.

001 | {9: 1, 4: 1, 3: 1, 2: 2, 1: 1}
002 | {9: 1, 4: 1, 3: 1, 2: 2, 1: 1}

[gaunt tangle]

wow that's what I wanted to see. Good job

[austere sparrow]

the first one's time complexity is O(N^2), second one's is O(N log N)

[austere sparrow]

I'm thinking that there's some way to compute the path in constant time, but I'm not sure how

[jovial sphinx]

yeah it's like

a very unusual problem

even just the task of keeping track of the state of a dice

https://math.stackexchange.com/questions/389590/a-mathematical-model-for-rotations-of-a-die
https://math.stackexchange.com/questions/3678975/is-there-a-mathematical-model-to-work-out-which-face-of-a-dice-will-appear-when

this is what I received from one of the helpers yesterday

I mean after all I encountered this problem in a programming competition so

and it's the final problem

[austere sparrow]

...and there's an O(N * k) solution (if all numbers are bound by log2 k) with radix sort

[jovial sphinx]

that goes beyond my knowledge but could you explain why stack is n^2 and why recursion is only n log n

[austere sparrow]

oh, I was talking about the sorting

[jovial sphinx]

oh

nvm xd

[drifting drum]

Haven't seen your code but following along from this and what fix error says, I think the 4n idea is very close?

So you've gotta go from (x, y) to (0, 0)
First roll the dice from (x,y) to (0,y), then from (0, y) to (0, 0)
Since you mentioned you already had a model to determine what face is up at all times, you would know what face is up at (0, 0) after this sequence of steps, correct?

Now, if the face that we want is already at top, we're done.
If it's opposite to the face currently at top, we would be 6 steps to get it right(One way is two steps down, one step right, two steps up, one step left).
If it's adjacent, we would need 4 steps

So that should be the answer?

[jovial sphinx]

oh yes if that's what the 4n idea meant then yes it could be close

however consider the case (2, 3)
if you just roll it west by 2 tiles (facing bottom) and then roll it south 3 times (facing north), you would have to then spend 4 extra moves e.g. SENW to get to (0, 0) and end up facing top again

but the search algorithm searches all paths where each tile in the path is somewhere between (x, y) or (2, 3) in this case and (0, 0), which is as short as the path can be, and returns the correct answer SSWSW

Let's compare them side by side
4N approach: WWSSSSENW (9 moves)
Search algorithm: SSWSW (5 moves)

the idea is that search always return a path of x+y length if it can find one

in fact I ran an exhaustive test for all values of x and y between -99 and 99 and the only cases the search cannot solve have one common property: either x or y or both are either 1 or -1

I handled those cases manually by adjusting the rotation using the trick as you mentioned above

so that it's aligned to the axis

[drifting drum]

oh just realised, atleast for the 4 steps thing, it balances out by moving in a diagonal manner like you did with the search algorithm, so that's why those weren't needed

hm

either x or y or both are either 1 or -1
So (1, y), (-1, y), (x, 1) and (x, -1) never have a solution?

[jovial sphinx]

yeah

oh

no

they do have a solution

[drifting drum]

that doesn't sound right

[jovial sphinx]

as you said

[drifting drum]

everything

has a solution

yeah

[jovial sphinx]

yes everything has a solution

as you said earlier what we can do

let's consider the example of (1, 1)

what we'll have to do first is say do NWS

so that it's aligned with the x axis

then we do let's say WSE

so it arrives the center while facing up

so instead of the shortest theoretical path x+y which in this case is 2, we have a path NWSWSE which is of length 6

so for each axis that is a 1 or a -1 the answer will be 2 tiles longer

[drifting drum]

yeah 2 + 4 by the method earlier

I think when the md is > 4, it can balance out

[jovial sphinx]

but that is only for cases where x or y or both are either 1 or -1

[drifting drum]

possibly with 6 too

[jovial sphinx]

6 is when the diagonal works

but the search algorithm encompasses the diagonal

[drifting drum]

No I mean if you have 41, 43

[jovial sphinx]

ye

[drifting drum]

it's going to be 41 + 43 steps in total

[jovial sphinx]

yes it does

[drifting drum]

the 4 at the end can be balanced

so anytime the distance is greater than 4 it gets balanced, and when it isn't like in (1,1) or whatever, we get to add it at the end

So I think this isn't just true for 4, but also 6

hm, this is now really a math problem, are you required to do with the graph search and all of that?

[jovial sphinx]

it came up in a programming competition as the last problem

[drifting drum]

do you have a link to it?

[jovial sphinx]

it's surprisingly diffic

ofc no

it's a programming comp

[drifting drum]

and?

huh

[jovial sphinx]

sry it's not accessibe

[drifting drum]

Programming competitions are held publicly too you know that right?

[jovial sphinx]

yes they are but the pages are shut down after the timer runs out

[drifting drum]

well then, how even are you asking for help on something you're not allowed to discuss?

[jovial sphinx]

well I am allowed to discuss it actually

[drifting drum]

Please stop deleting messages

[jovial sphinx]

it's just

no mb for saying that

I don't think it's forbidden to discuss that

it's just it's no longer publicly available

it's like the hackerrank contests

after the contest ends you can no longer find the problems in them

[drifting drum]

sorry fam you've just made it a bit too sus, I'll let someone else take you up on it.

[jovial sphinx]

I'm not sure what you mean by sus

it is a problem programming competition I personally participated in and I just came back to it a day ago

[slate dust]

If there's no way for us to verify the competition has ended (which there doesn't seem to be) then this isn't something we can help with any further, as per our rules @jovial sphinx

!rule 8

[halcyon plank]

Rules

8. Do not help with ongoing exams. When helping with homework, help people learn how to do the assignment without doing it for them.

[slate dust]

Competitions would fall under this too ^

[jovial sphinx]

oh

ok ic what u guys mean now

http://cgi.cse.unsw.edu.au/~cupcake/progcomp/flask.cgi/2021/dates

it's from this competition

besides I have already solved the task I'm just enquiring other people's approaches to gain more insight

[jovial sphinx]

btw for anyone asking, it is a problem from Main Round

[knotty magnet]

why do you need to deepcopy it though?

[lament quiver]

Hello, does anyone how to go for finding the longest path in a maze, I have the shortest path using dfs, but not able to figure out the longest one, tried with recursion but was unable to get it. Any help is much appreciated.

or we can say all the paths in a maze

[vocal gorge]

The longest path would be one that endlessly circles somewhere. You'd need some sort of constraint to make it exist, like "visit a cell no more than once" - in which case wiki tells me it's NP-hard https://en.wikipedia.org/wiki/Longest_path_problem

apparently it's solvable in polynomial time for some classes of graphs

https://cdsmith.wordpress.com/2011/06/08/finding-the-longest-path-in-a-maze/
This seems to suggest an algorithm, based on considering the maze cells a tree and recursively constructing longer paths out of smaller ones

[lament quiver]

Yeah I track which cells are visited or not, and yes it is NP hard. will see the resource. Thank you!

[knotty magnet]

isn't this like traveling salesman?

ah

The NP-hardness of the unweighted longest path problem can be shown using a reduction from the Hamiltonian path problem:
from the wiki you linked

[lament quiver]

and for rest??

I wrote that part, now for small maze it works but as size increases, its not working, getting stuck in the recursion tree 🤧

[winged trench]

which is the best DSA course in C++?

[trim fiber]

It's Python server lol

[pearl drum]

I'm experimenting a bit with monte carlo methods and have implemented a n-particle random walk simulation. After a long enough duration the initially random distributed particles are somehow starting to unmix.

Can I blame my random number generator for this, as its based on the Sobol sequence?

[keen hearth]

Erm, it's been a while since I've looked at this topic. But I remember something about accidentally losing entropy.

Is it also possible that your RNG is looping?

[pearl drum]

the sobol sequence definitely loops

but thats after 2^30 samples - so shouldn't matter that quickly

[jovial sphinx]

So I just tried using copy instead of deepcopy (which shouldn't make a difference since visited tiles hold (x, y) tuples) and the stack version became just as fast if not faster than the recursion version. I guess that's my original question answered 😄

[pearl drum]

I'm just drawing about 40k samples a second

[late bay]

any complete python dsa/algo playlist on YouTube? if yea, plz share

[keen hearth]

I highly recommend the MIT course in the pins. It has lectures to go with it.

[last cosmos]

whats the difference between a queue and a circular queue

[fervent saddle]

A circular queue is something that’s used as if the start and end are connected

I mean I guess they really would be connected if it was a node thing

But if it’s like an array then it’s just used as if both ends are connected

And a queue is just something where you insert at one end and remove at the other end

[lyric geyser]

hi

[frail jackal]

Hey guys where do u think is tge best place to learn algos and data structures. I'm just starting out

U guys have any courses in mind ?

[knotty magnet]

check the pins

[frail jackal]

Okay thanks

[dapper sapphire]

Wondering if it's possible to do:

nums = [11, 22, 33, 44, 55]
for num in nums:
  # but num would start at 22

I mean we can do:

nums = [11, 22, 33, 44, 55]
for i in range(1, len(nums)):
  # nums[i] would start at 22

I guess we can do:

!e

nums = [11, 22, 33, 44, 55]
for num in nums[1:]:
  print(num)

[halcyon plank]

@dapper sapphire :white_check_mark: Your eval job has completed with return code 0.

001 | 22
002 | 33
003 | 44
004 | 55

[knotty magnet]

or islice

[runic tinsel]

islice is proper

[runic tinsel]

when this is too slow

[dapper sapphire]

Is this how we use it?

!e

import itertools

string = "abcdef"
slices = itertools.islice(string, 1, len(string))
for _slice in slices:
    print(_slice)

[halcyon plank]

@dapper sapphire :white_check_mark: Your eval job has completed with return code 0.

001 | b
002 | c
003 | d
004 | e
005 | f

[vocal gorge]

yeah, it works like normal slices, but without copying (instead, it iterates while skipping some elements)

so when used for stuff like [1:] slices, it's far more efficient

[dapper sapphire]

oh itertools.islice is efficient/faster than the regular python slicing via [1:]?

I imagined regular slicing to be more efficient, maybe because they are used a lot.

[vocal gorge]

Depends what you do, but not copying the slice definitely makes it at least more memory-efficient, and I'd expect it to be more efficient simply because this:

for el in els[1:]

iterates over els twice (the first being a C loop to copy that slice), while islice only iterates once

[sage coral]

    def tournament(self, nets, probability):
        new = deepcopy(nets)
        new.sort()

        p = probability
        for i in range(len(new)):
            prob_i = p * ((1 - p) ** i)
            selection = new[i] if random.uniform(0, 1) < prob_i else None
            if selection:
                break
        else:
            selection = new[-1]
        
        return selection

Would this be a correct implementation of a genetic algorithm tournament? I'm not sure if this is correct, as the probabilities seem off to me...

[chrome stratus]

If you have a mxn grid, how many possible connected shapes are there
(a connected shape is for instance, a line, but not a smiley face because the eyes are disconnected, so I suppose a good rule would be "when each point has at least one adjacent point" (except for the case with only 1 point, which i guess would be the exception to this, but there would be only m*n of those anyways))

(am actually trying to do this the math way with pen and paper and THEN maybe code it but cant figure it out)

[meager slate]

i understand how to get the maximum price from knapsack, but how do you actually find the items that lead to that maximum price?

[keen hearth]

Usually with these kinds of algorithms, you can save information that can be used to re-construct the solution (after finding the optimum cost). What does your current algorithm look like?

[meager slate]

the usual making a table and filling it up from bottom to top (its called tabulation, i think?)

im looking for resources on how to actually get the solution

[main flower]

@meager slate https://www.geeksforgeeks.org/printing-items-01-knapsack/

if ur talking about discrete knapsack

[thin vector]

!e

print(“hi”)

Wut

[meager slate]

ah, thanks 🙂

[formal charm]

Hi can someone take a look at my problem in #help-pear

Its related to a data structure

[shadow canyon]

Greetings, hopefully this isn't too difficult. I am trying to convert this article (https://towardsdatascience.com/scraping-nfl-stats-to-compare-quarterback-efficiencies-4989642e02fe) and it works. However, when I convert it to defense with the exact same code but different sources I get the following error:

# Function to get QB data def get_qb_data(data, team):
return np.asarray(data[data['Tm'] == team])[0]
File "Z:\Personal\user\Scripts\nfl_fantasy\Scripts\dev\stats_def.py", line 208, in get_qb_data return np.asarray(data[data['Tm'] == team])[0]
`IndexError: index 0 is out of bounds for axis 0 with size 0

Anyone familiar with what this may be? If I run the exact same code from the site and the passing, it works flawlessly.

[vocal gorge]

It seems there's a team for which there's zero rows in the data.

[shadow canyon]

I am looking but it isn't appearing to be so. At least not on the website. The script runs up until I get to the plt, and prints off a filtered head() with results 0-4,34 without issue. Confounded thing. The axis has been set appropriately, the same manner it was in the QB section and RB section but those are working fine. Back to the drawing board it appears.

[vocal gorge]

I'd check what team it is that has no rows (by using a debugger to inspect the state when this exception happens, say)

[formal charm]

How do i traverse an n degree tree?

Like i have an object with is nested recursively

How do i start from an ancestor and get all the children?

[vocal gorge]

BFS/DFS, essentially

[gray tulip]

Hi guys, do you know by which datastructure we can range with a better time than O(n)?

range over data

[austere sparrow]

What do you mean by 'range'?

if you mean iterate, you can't go over N items in less than O(N) time

but maybe you mean something else

[brave oak]

parallelism?

🙏

[austere sparrow]

that's still O(N / k) 😔

[brave oak]

assume infinite processors

[austere sparrow]

unless you have unlimited computational power

ah...

[austere sparrow]

well, then you can use the 'Imagination' data structure and the 'Wishful thinking' algorithm

[brave oak]

😔 I just want to be a good mathematician

[austere sparrow]

I thought that's what mathematics is 😦

(λ f. f f) (λ f. f f)

🌈🧽

[dapper sapphire]

I think it depends on the problem you are trying to solve and what the data looks like.
If you are trying to search for an element in unsorted list, then you cant do better than O(n). You have to visit each element.
But if you are trying to search for an element in sorted list, then you can achieve O(log n) by implementing binary search.

[gray tulip]

Ok thanks a lot

[vast rivet]

hi

[cinder wigeon]

Totally Spies

[winged trench]

Yea Ik...
You know what nvm..
Tell me any good dsa course in python only..

[granite olive]

Hi, can anyone recommend me some python course? (I m not begginer in programming, I'm usually program in node.js) Generally I need python for algorithms so the best option will be course with algorithms

[cinder wigeon]

https://docs.python.org/3/tutorial/

[fiery cosmos]

ive got an algo that isnt getting me the result i expect it to , can someone catch the problem

its meant to count the ways you can construct a str from a bank of substrings

this gives a result of 4

but i would have thought there would be many more ways to construct it

im stupid

like honestly

ignore everything

deleting the code but keeping this here as a symbal of my stupidity

[jolly lantern]

Please help

Somebody good with Binary Tree and Recursion and Tuple??

I need some quick concept help

[jolly lantern]

pythondsa.com

[echo ore]

what are pros/cons of a array based heap vs a tree based heap?

what is the recommend heap implementation for python?

[vocal gorge]

Python has a builtin heapq, which uses a list

[knotty magnet]

array saves space on pointers

heapq uses any mutable sequence i thought?

[echo ore]

right but if we build from scratch

is array based always superior vs tree based?

array seems more efficient is there any pro to treee based heap?

[knotty magnet]

easier to do as a continuation from learning binary trees in a dsa class

[keen hearth]

Also, pointer-based data structures just generally tend not to be as efficient as array-based in practice.

Arrays (not python lists) keep all the in information close together in memory. They meet the CPUs expectation that data which is accessed close together in time, is stored close together in space (spacial locality).

The CPU needs this to be the case in order to perform caching (storing recently accessed memory addresses, and the surrounding memory addresses, in smaller faster memory close to the CPU).

CPU caching makes a huge difference to the performance of programs.

In Python though, everything is done with pointers 😄

Which is part of the reason why it's a relatively slow language.

[dusk estuary]

In my opinion for almost all languages I would implement it as a list. Also the maths required to find the index of a parent and children's is actually quite simple and quick.

[jolly lantern]

Who can vc and help with a Python conceptual and logic query?

with me

pls

[formal charm]

What are you looking for ?
I'm not an expert by any means but i can take a look.

[torn pasture]

can anyone recommend some good resources for learning more about big o and time/space complexity?

[formal charm]

Paste the code don't do photos

It makes it hard to read

[jolly lantern]

I'm sorry, now can you read?

[fiery cosmos]

def flatten(args):
    l = []
    for e in args:
        if not isinstance(e, list):
            l.append(e)
        else:
             l.extend(flatten(e))
    return l

Any way to avoid recursion

[knotty magnet]

yes

[jolly lantern]

    if node is None:
        return True, 0
    balanced_l, height_l = is_balanced(node.left)
    balanced_r, height_r = is_balanced(node.right)
    balanced = balanced_l and balanced_r and abs(height_l - height_r) <=1
    height = 1 + max(height_l, height_r)
    return balanced, height```

The following tree is balanced:

<img src="https://i.imgur.com/JZeF9ix.png" width="520">

Balanced Binary Trees

QUESTION 14: Write a function to determine if a binary tree is balanced.

Here's a recursive strategy:

1. Ensure that the left subtree is balanced.
2. Ensure that the right subtree is balanced.
3. Ensure that the difference between heights of left subtree and right subtree is not more than 1.

[jolly lantern]

Please tell me how this recursion code works at is_balanced(node.left)

[grim sun]

context? what are you doing with args? what type is it?

[fiery cosmos]

flatten the list into one

[fiery cosmos]

you can use the code i just sent but use an integer value

loop through all, if a node is a parent then i += function(parent)

[grim sun]

oh gotcha,

def flatten(jagged_matrix:list) -> list:
  output = []  
  for row in jagged_matrix:
    if type(row) != type(int):
      output.extend(row)
    else:
      output.append(row)
    return output

will this work?

[fiery cosmos]

nvm my version is the only way

[grim sun]

are you working with a tree? it'd be unusual for a list to be more than one layer deep

[knotty magnet]

it's not, you can do it without recursion

[jolly lantern]

thanx i just want to know how code @ is_balanced(node.left) works

[winged vale]

Can someone help with this please #help-pancakes message

[fiery cosmos]

then show me?

[knotty magnet]

this exercise is left to the reader :)

[fiery cosmos]

You are no help at all

[knotty magnet]

if you say so ¯_(ツ)_/¯

[shadow canyon]

I have a dataset, NFL stats, and am trying to do a few different things. The df outputs correctly. I am trying to do a count (re: sum in excel) of touchdowns where criteria is met but also do a mean for the 'epa' and 'yards_gained' fields in the same script block. Is this possible? This is what I have for the script block that does the heavy lifting.

if I can't, than I'll have to separate out the different things I want to count / mean and combine them later into a single new df, right?

`rbs = data.loc[(data.play_type == 'run') & (data.down <= 4)].groupby(by='rusher_player_name')[['posteam', 'epa', 'success', 'yards_gained', 'touchdown']].mean()

[brave oak]

try #data-science-and-ml

[somber hatch]

would this work? py sum(list, [])

[austere sparrow]

That's O(N^2)

[somber hatch]

ahh

[fallow viper]

Could someone help?

# Expected outcome:
# 17  16  15  14  13
# 18   5   4   3  12
# 19   6   1   2  11  28
# 20   7   8   9  10  27
# 21  22  23  24  25  26 

# Expected return:
[
  [17, 16, 15, 14, 13],
  [18, 5, 4, 3, 12],
  [19, 6, 1, 2, 11, 28],
  [20, 7, 8, 9, 10, 27],
  [21, 22, 23, 24, 25, 26]
]
``` Using range(1, 29)

But if i change the range it should also scale up

[keen hearth]

Hello @fallow viper I'm not sure you've provided enough information to understand what you're asking sorry.

[fallow viper]

Basically using a range of numbers 1, 29 then generate a 2d grid like a spiral.

[keen hearth]

Oh right. So you want to implement a function (e.g. spiral) that takes a sequence and arranges it into a spiral like this?

Perhaps you could use deques for the rows, keep track of the coordinates of the current position, and walk around in a spiral pattern. This might be a little tricky to implement in practice 🤔

[fiery cosmos]

in trees, how can I move a node?

[timid garden]

import torch
def brightness(img:torch.tensor, value:torch.float):
    min = torch.min(img)
    max = torch.max(img)
    return torch.clamp(img, min=min+value, max=max+value)

I dont know why I have a different results than PIL.... I would like to make a own function for increasing brightness
The same goes for contrast function

[desert stratus]

Hiii

Can anyone help on how to solve this

[devout gust]

given an array you can probably just use Arrays.sort()

your problem only uses integer arrays so do Arrays.sort(aa) and then System.out.println(aa[aa.length - 1], aa[0])

last element is max

first is min

considering this is the python discord, in python you'd want to use sorted(aa) for a list in ascending order and sorted(aa, reverse = True) for a list in descending order

and print out the max and min that way

[knotty magnet]

Your goal in this problem is to do better!

[vocal gorge]

huh, that's quite a task actually

oh, I see I guess, but it's in the worst case not a big change - they probably want you to ||omit the if el < min check if the if el > max happened, since they are mutually exclusive||

EDIT: cool, I googled and apparently there really is a faster-than-2n-worstcase way

[devout gust]

i know theres a method for exactly 3n/2 but i have no idea with fewer

[runic tinsel]

maybe it's that

it's 3n/2 - 1½

worst case

[knotty magnet]

half a comparison?

[devout gust]

if the array is odd sized

take the array elements in pairs

take the larger one and compare it to the current max, take the smaller and compare it to the current min

3 comparisons, n/2 iterations if the array is even

half a comparison is just a way of saying it could be 0 or 1 extra

[runic tinsel]

if n is even it's 3n/2 - 2

if it's odd, 3n/2- 1½ which is worse, so that's the worst case

it's not averaging between 1 and 2, it's just actually minus one and a half

[fallow viper]

hmm thanks i will try and beat it.

[dapper sapphire]

Is it better to concatenate a string using + or f string, or it doesnt matter?

[vocal gorge]

If you have more than two parts, f-string is faster I believe since it does it all at once, instead of doing many copies. But there's the CPython 2.7+ optimization that tries to avoid copying when possible, so it might not be a major effect

[dapper sapphire]

It will be concatenating three parts

ok

thanks!

[real rover]

Hi guys i have a problem when i use import pandas as pd

i have this error ModuleNotFoundError: No module named 'pandas'

how can i fix it please

[knotty magnet]

install pandas

[real rover]

How can i install it ?

i installed python so i think there are also python modules

[fervent saddle]

It’s not in the standard library, you have to install it separately

[old rover]

pip install pandas

[zenith wasp]

not specifically python-related but what optimizations can I make for a chess engine other than alpha-beta pruning? after converting my code to C++ it still takes ~10 minutes to generate a move on depth 6

[knotty magnet]

i used this when i was making mine https://www.cs.cornell.edu/boom/2004sp/ProjectArch/Chess/algorithms.html#alphabeta

[zenith wasp]

oh I see, initially sorting by ply 1

that's not a bad idea

I wonder what makes it so slow though

[keen hearth]

I had a go at implementing it myself 👀

[keen hearth]

Well the real answer today would be Monte Carlo tree search, which is a bit more intelligent about deciding which branches of the game tree to explore. It's actually not all that much harder to implement than minimax search either.

[zenith wasp]

oh so you just pick a few random ones and try them out rather than trying all possible moves?

that'd certainly be faster but it also seems pretty reliant on luck

oh wait and it checks the percentage of outcomes where it gains an advantage and passes that back?

so effectively optimizing for chances of winning rather than gaining an advantage at a certain depth

I think I might mix that with searching the top n results on ply 1 and add k random searches

or I just make k fairly big

[zenith wasp]

hmm, performance is still not quite what I'd hoped

[keen hearth]

It expands out a search tree node-by-node. Each time a new node is added, it plays a random game from that node to the end. It maintains statistics for each node that allow it to calculate an 'upper confidence bound' on the value of that node. Nodes that have a greater upper-bound (either because they have not been explored much, or because they have consistently returned good values) are searched first.

[fiery cosmos]

anyone heard of a website called w3schools ? for coding help ?

[austere sparrow]

what's your question?

[languid barn]

Man I just wanna instant the mersenne twister but I gotta read 20 other wiki articles first

[naive cloak]

Question about efficiency. I'm calculating things like moving averages for very large datasets. Which is faster, transform data from list to dataframe and compute there, or from list to numpy arrays?

[real rover]

thanks

[real rover]

Thanks

[real rover]

when i write this i have an error in my cmd

i just want to collect data can someone help me

pandas.errors.ParserError: Expected 21 fields in line 10, saw 22. Error could possibly be due to quotes being ignored when a multi-char delimiter is used.

Thanks i changed the code

but i have this error pandas.errors.ParserError: Expected 21 fields in line 10, saw 22. Error could possibly be due to quotes being ignored when a multi-char delimiter is used.

it's big error message

[spice turtle]

well hi i have started learning python recently and iam just stuck in a while loop program and iam not able to understand the codes can someone explain it to me>?

x = int(input('enter number x'))
y = x
while (y>0):
y = y*x
x = x-1
print('x',x)

[magic orbit]

Every iteration, x decreases by 1. The only way for y>0 to be false is if x==0. So it decreases x until 0, decreases it 1 more time, and exits

[zenith wasp]

Each time a new node is added
Wait but couldn't picking random moves go out to a possibly infinitely repeating game?
or because they have consistently returned good values
Where would I store the nodes?

My current code (if I translate to python):

def monteCarlo(board, wonProp, totalProp, depth):
    eval_ = evaulate(board)
    if (d == 0 or board.state != State.PLAYING):
        totalProp += 1
        if ((board.blackToMove and board.state == State.MATE_BLACK) or (not board.blackToMove and board.state == State.MATE_WHITE)):
            # We actually won
            wonProp += 1
        elif ((board.blackToMove and eval_ < 0) or (not board.blackToMove and eval_ > 0)):
            # We (naively) have the advantage
            wonProp += 1

    mvs = []

    for (i in range(20, 100)):  # 12x10 board representation
        p = board.pieces[i];
        if (p.type != PieceType.INVALID and p.type != PieceType.EMPTY and p.black != board.blackToMove):
            findMovesSmart(board, i, mvs);  # All legal moves, appends to mvs

    # randomize
    shuffle(mvs);

    for (i, mv in enumerate(mvs)):
        testBoard = board.copy()
        move(testBoard, mv)

        # Repeat recursively
        monteCarlo(ptr, won, total, depth-1)

        if (i+1 == k):  # k = maximum branches from here
            break

[zenith wasp]

I thought maybe you only wanted to spread k paths at the first node, but that didn't work out very well

[crystal oak]

Instal Anaconda IDE. It comes with most of the tools you need including numpy and pandas

[zenith wasp]

one problem I found with montecarlo is also that it manages to hang its queen if it doesn't check the move to capture back

[fiery cosmos]

when traversing through a tree do you use recursion alot ?

is it common to use that technique

[magic orbit]

Yes

[fiery cosmos]

is it a good idea to integrate an advanced data structure like wavl tree and merge it with the hashmap?

[knotty magnet]

how would that work

[thin vector]

!e

print("E")

[halcyon plank]

@thin vector :white_check_mark: Your eval job has completed with return code 0.

E

[thin vector]

!e

await ctx.send("E")

[halcyon plank]

@thin vector :x: Your eval job has completed with return code 1.

001 |   File "<string>", line 1
002 | SyntaxError: 'await' outside function

[thin vector]

sorry wrong channel

[knotty magnet]

?

[fiery cosmos]

Since wavl is a combination of AVL and red-black, I would say the key will always be the hash.

But I think I will discard the idea of ​​merging it with the hashmap because I think it is unnecessary to digest the key as a hash unless the processor takes the conditions faster when it comes to int

[fiery cosmos]

I just started experimenting with pandas and was wondering if it's the right framework to display data on screen that requires to be redrawn/refreshed each 0.5 seconds? The reason I'm asking is the screen sometimes "blinks" when I do os.system('clear') print(mypandasDataFrame)

I'm working on a similar tool to airmon-ng so I need to display up to date information on screen each fraction of a second.

In short ^^^

[keen hearth]

You might have better luck in #user-interfaces. Although I'd recommend using a TUI library, like Rich (https://rich.readthedocs.io). It has support for tables, and for the live display of information: https://rich.readthedocs.io/en/stable/live.html

Try out the two examples on that last link and let me know if they produce the kind of thing you want.

[keen hearth]

You probably want #data-science-and-ml