algos-and-data-structs

[feral hound]

@stable pecan does any return as soon as it finds that an argument evaluated to true or does it wait for the comprehension to finish first?

[slender sandal]

what does a tile mean in this function

[stable pecan]

not word is the same as word == ""

[dawn pebble]

this is pretty good

[oblique urchin]

I don’t understand almost nothing in it

[feral hound]

nvm you already answered lol

@dawn pebble if you understand the code I wrote this is essentially doing the same thing

[feral hound]

tiles =  ["foob", "foo", "ba", "ba", "r", "z"]
word = "foobarbaz"

[slender sandal]

I would imagine it does, assuming it breaks on the first True it finds in an iterable, and it's not a comprehension, but rather a generator expression, so yeah it all is not costly (memory-wise).

[dawn pebble]

how do I implement this sort of clean code?

I want to learn how to code like @stable pecan

[stable pecan]

this is correct

[slender sandal]

yay i feel very praised rn lol

[stable pecan]

the only slow part of this code really, is that we're remaking the tile-list every call

you can do better with back-tracking and using a set

but the code will get a bit more involved

[feral hound]

using a set would remove identical tiles though no?

[stable pecan]

well, can use a multi-set

[dawn pebble]

what is a multi set

a hash?

[stable pecan]

this is collections.Counter

is a multi-set

[dawn pebble]

ah

ok

[cobalt stag]

if I have a list of lists like so indeces = [[0, 0], [-1, 0], [....], ...] how could I use the elements of the nested lists as indeces for a grid gird = [[(False) for i in range(len(indices))] for j in range(len(indices))]?

[vocal gorge]

a multiset is a math concept much like a set - essentially a set, but with possibly multiple copies of the same item. It's usually implemented as a dict (aka associative array, hash, hashmap...) mapping an item to the number of times it's present, yes

[stable pecan]

in fact, you can iterate over prefixes of the word to search the multi-set, which should be faster than iterating over the tiles!

but, this will make the solution seem less elegant

[feral hound]

do you know what the time complexity of this solution is?

[stable pecan]

same as DFS as mentioned above

[feral hound]

the issue is im not sure what the time complexity is for that either and I know these 2 are essentially equivalent

yours is just much nicer

[slender sandal]

a = []
for i in range(10):
    for j in range(50):
         a.append(i * j)

is the same as

a = [i * j for i in range(10) for j in range(50)]

(just to help your brain get the hang of it)

it's basically leftover of the looping or whatever, then start looping one layer at a time starting from above, and you may also put a condition or several conditions with consecutive ifs

[stable pecan]

just one if

my_list = [ ]
for i in iterable:
  if condition:
    my_list.append(do_something_with(i))

same as:

my_list = [do_something_with(i) for i in iterable if condition]

[slender sandal]

Well then this is weird

>>> [i * j for i in range(10) for j in range(50) if i % 2 if j % 3]
[1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26, 28, 29, 31, 32, 34, 35, 37, 38, 40, 41, 43, 44, 46, 47, 49, 3, 6, 12, 15, 21, 24, 30, 33, 39, 42, 48, 51, 57, 60, 66, 69, 75, 78, 84, 87, 93, 96, 102, 105, 111, 114, 120, 123, 129, 132, 138, 141, 147, 5, 10, 20, 25, 35, 40, 50, 55, 65, 70, 80, 85, 95, 100, 110, 115, 125, 130, 140, 145, 155, 160, 170, 175, 185, 190, 200, 205, 215, 220, 230, 235, 245, 7, 14, 28, 35, 49, 56, 70, 77, 91, 98, 112, 119, 133, 140, 154, 161, 175, 182, 196, 203, 217, 224, 238, 245, 259, 266, 280, 287, 301, 308, 322, 329, 343, 9, 18, 36, 45, 63, 72, 90, 99, 117, 126, 144, 153, 171, 180, 198, 207, 225, 234, 252, 261, 279, 288, 306, 315, 333, 342, 360, 369, 387, 396, 414, 423, 441]
>>> 

It's basically the same as [i * j for i in range(10) for j in range(50) if i % 2 and j % 3] btw

[stable pecan]

that's an if for each loop

yes

[slender sandal]

Wait, what? I don't get you.

>>> [i * j for i in range(10) for j in range(50) if i % 2 if i % (j + 1)]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 3, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54, 57, 60, 63, 66, 69, 72, 75, 78, 81, 84, 87, 90, 93, 96, 99, 102, 105, 108, 111, 114, 117, 120, 123, 126, 129, 132, 135, 138, 141, 144, 147, 5, 10, 15, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100, 105, 110, 115, 120, 125, 130, 135, 140, 145, 150, 155, 160, 165, 170, 175, 180, 185, 190, 195, 200, 205, 210, 215, 220, 225, 230, 235, 240, 245, 7, 14, 21, 28, 35, 49, 56, 63, 70, 77, 84, 91, 98, 105, 112, 119, 126, 133, 140, 147, 154, 161, 168, 175, 182, 189, 196, 203, 210, 217, 224, 231, 238, 245, 252, 259, 266, 273, 280, 287, 294, 301, 308, 315, 322, 329, 336, 343, 9, 27, 36, 45, 54, 63, 81, 90, 99, 108, 117, 126, 135, 144, 153, 162, 171, 180, 189, 198, 207, 216, 225, 234, 243, 252, 261, 270, 279, 288, 297, 306, 315, 324, 333, 342, 351, 360, 369, 378, 387, 396, 405, 414, 423, 432, 441]
>>> 

[stable pecan]

In [2]:  l = [i * j for i in range(10) for j in range(50) if i % 2 if j % 3]

In [3]: print(l)
[1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26, 28, 29, 31, 32, 34, 35, 37, 38, 40, 41, 43, 44, 46, 47, 49, 3, 6, 12, 15, 21, 24, 30, 33, 39, 42, 
48, 51, 57, 60, 66, 69, 75, 78, 84, 87, 93, 96, 102, 105, 111, 114, 120, 123, 129, 132, 138, 141, 147, 5, 10, 20, 25, 35, 40, 50, 55, 65, 70, 80, 85, 95, 100, 110, 115, 125, 130, 140, 145, 155, 160, 170, 175, 185, 190, 200, 205, 215, 220, 230, 235, 245, 7, 14, 28, 35, 49, 56, 70, 77, 91, 98, 112, 119, 133, 140, 154, 161, 175, 182, 196, 203, 217, 224, 238, 245, 259, 266, 280, 287, 301, 308, 322, 329, 343, 9, 18, 36, 45, 63, 72, 90, 99, 117, 126, 144, 153, 171, 180, 198, 207, 225, 234, 252, 261, 279, 288, 306, 315, 333, 342, 360, 369, 387, 396, 414, 423, 441]

In [4]: l = [ ]
   ...: for i in range(10):
   ...:     if i % 2:
   ...:         for j in range(50):
   ...:             if j % 3:
   ...:                 l.append(i * j)
   ...: 

In [5]: print(l)
[1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26, 28, 29, 31, 32, 34, 35, 37, 38, 40, 41, 43, 44, 46, 47, 49, 3, 6, 12, 15, 21, 24, 30, 33, 39, 42, 
48, 51, 57, 60, 66, 69, 75, 78, 84, 87, 93, 96, 102, 105, 111, 114, 120, 123, 129, 132, 138, 141, 147, 5, 10, 20, 25, 35, 40, 50, 55, 65, 70, 80, 85, 95, 100, 110, 115, 125, 130, 140, 145, 155, 160, 170, 175, 185, 190, 200, 205, 215, 220, 230, 235, 245, 7, 14, 28, 35, 49, 56, 70, 77, 91, 98, 112, 119, 133, 140, 154, 161, 175, 182, 196, 203, 217, 224, 238, 245, 259, 266, 280, 287, 301, 308, 322, 329, 343, 9, 18, 36, 45, 63, 72, 90, 99, 117, 126, 144, 153, 171, 180, 198, 207, 225, 234, 252, 261, 279, 288, 306, 315, 333, 342, 360, 369, 387, 396, 414, 423, 441]

technically i got the conditions backwards

or did i

[slender sandal]

I just swapped the places of the two ifs and got the same result. So I am guessing order doesn't matter (first if doesn't necessarily correspond to the first for). It actually behaves more like the return value for each item.

Weird that we can stack ifs instead of using ands, I wonder if that makes any difference. It probably does, operation-order-wise.

[stable pecan]

apparently this does work for a single loop though:

In [6]: [i for i in range(10) if i % 2 if i % 3]
Out[6]: [1, 5, 7]

so TIL

though probably you should just use and

[idle pier]

Hello folks, for this line of code

for i in nums[1:]:```
Its basically saying we are starting at index 1 and it goes all the way through lenght of the list
Am I correct?

[fervent saddle]

Yeah

And it makes a copy of the whole list except for the first value

And iterates through that

iter_nums = iter(nums)
next(iter_nums)
for i in iter_nums:```

You can do this to skip the first value without copying the whole list. You can also use itertools.islice

[idle cairn]

guys i'm trying to collect data from a online game, so i was thinking about how i can do a reverse engineering with python to collect data from a online game, someone know where i can start to learn about that?

[gusty pawn]

can someone test my code and see what's wrong with it?

a = "n"
b = "e"
c = "v"
d = "r"
e = "g"
f = "o"
g = "a"
i = "i"
h = "y"
j = "u"
k = "p"

print (a+b+c+b+d,"", e+f+a+a+g,"", e+i+c+b,"", h+f+j,"", j+k)

wth

ur an absolute madlad

oh sorry ok

[boreal flint]

Hello guys.

I want help

even tho the file "requirements.txt" exist and I am trying to install it with this command-
pip install -r requirements.txt

but it is giving me this error-

This

Can anyone help by pinging me??

pls

[knotty magnet]

check out #❓｜how-to-get-help , this is the wrong channel for this type of question. (i would strongly suggest checking to make sure it's actually there, though)

[boreal flint]

Ah-

ok

[fiery cosmos]

as talked earlier please don't ask for help in case of this precise project, also please keep this channel to #algos-and-data-structs

question:
is there a well defined algo to check if N matrices commute?

[jolly zealot]

Guys,

how to check such a condition in python: a < b but not more than 1?

[trim fiber]

!e

for a, b in [(-1, 0), (5, 8), (3, 0)]:
  print(f"a = {a}, b = {b}")
  if a < b < 1:
    print("less than 1")
  elif a < b:
    print("not less than 1")
  else:
    print("?")

[halcyon plank]

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

001 | a = -1, b = 0
002 | less than 1
003 | a = 5, b = 8
004 | not less than 1
005 | a = 3, b = 0
006 | ?

[flat sorrel]

I think b can be equal to 1

[fiery cosmos]

It would be better to check a < b first and if it returns true then again check a < 1. This code fails for all cases with b = 1 and as DarkLight said b can be 1

[trim fiber]

All depends on the requirements

!e

for a in range(3):
  a -= 1
  for b in range(3):
    if 1 > a < b:
      print(f"a = {a}, b={b}!")

[halcyon plank]

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

001 | a = -1, b=0!
002 | a = -1, b=1!
003 | a = -1, b=2!
004 | a = 0, b=1!
005 | a = 0, b=2!

[fiery cosmos]

👍

[edgy steeple]

guys iv just started learning python, can u pplease help me with this,

What will be printed when following code is executed?

import random
Max=3
Div=1+random.randrange(0,Max)
for N in range(1,5):
print(100%Div, end="#")
print( )

[glossy breach]

sounds like graded exam

[edgy steeple]

tisnt

[unborn mist]

aww man great work

[spiral crown]

aww man crepper !

[fiery cosmos]

!e ```py
print("testing")

[halcyon plank]

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

testing

[fiery cosmos]

🤔

[desert stratus]

Can anyone please help

    public static int[] takeEvery(int arr[], int stride) {
        return takeEvery(arr, stride, 0);
        }

        int takeEvery(int arr[], int stride, int start) {
        int ans[] = new int[arr.length]; // this could be more memory efficient my calculating size of answer
        int c = 0;
        for (int i = start; i < arr.length && i >= 0; i = i + stride) {
        ans[c++] = arr[i];
        }
        return ans;
        }
}```

ping me too

[trim fiber]

This is not Python

[desert stratus]

Ik it’s Java

[trim fiber]

But it's Python server

[glossy breach]

:v

I think they want you to output the array with the exact length

resize it down

[desert stratus]

Hahaha but there’s this channel so I asked

[desert stratus]

Like how

[glossy breach]

I don't know much Java

I mean

You can just calculate the size first

[desert stratus]

Ohhh

[trim fiber]

def take_every(a, s, b):
  return [a[b + i * s] for i in range((len(a) - b) // s)]

Python solution, not tested

!ot Use offtopic channels to talk about languages different than Python

[halcyon plank]

Off-topic channels

There are three off-topic channels:
• #ot0-psvm’s-eternal-disapproval
• #ot1-perplexing-regexing
• #ot2-never-nester’s-nightmare

Their names change randomly every 24 hours, but you can always find them under the OFF-TOPIC/GENERAL category in the channel list.

Please read our off-topic etiquette before participating in conversations.

[desert stratus]

Onnn ok

[trim fiber]

You can also pick help channel #❓｜how-to-get-help

[slender sandal]

Actually I think they meant:

def take_every(a: list[int], stride: int, begin_with: int = 0) -> list[int]:
    return a[begin_with::stride]

[trim fiber]

Yeah, maybe. I am not so good with :: notation

[slender sandal]

start, stop, step (in this case it's called stride because why not)

[trim fiber]

start:stop:step? Excluding stop index?

!e

import string

print(string.digits[1:5:2])

[halcyon plank]

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

13

[slender sandal]

Because they say we stop when we hit the boundaries of the array, leaving stop is optimal

[trim fiber]

!e

import string

print(string.digits[1::2])

[halcyon plank]

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

13579

[trim fiber]

Thx

+1 to knowledge today

[slender sandal]

!e print(0)

[halcyon plank]

@slender sandal :white_check_mark: Your eval job has completed with return code 0.

0

[slender sandal]

!e

def take_every(a: list[int], stride: int, begin_with: int = 0) -> list[int]:
    return a[begin_with::stride]
print(take_every([3, 1, 4, 5, 9, 2, 6, 5], -1, 5))

[halcyon plank]

@slender sandal :white_check_mark: Your eval job has completed with return code 0.

[2, 9, 5, 4, 1, 3]

[slender sandal]

This is funny, I didn't even need the function, because it's literally just a simple slicing notation.

In Python, that is.

[trim fiber]

Yeah, it's wonderful

[fiery cosmos]

why the image is not opening!

[acoustic river]

!e

[halcyon plank]

Command Help

!eval [code]
Can also use: e

*Run Python code and get the results.

This command supports multiple lines of code, including code wrapped inside a formatted code
block. Code can be re-evaluated by editing the original message within 10 seconds and
clicking the reaction that subsequently appears.

We've done our best to make this sandboxed, but do let us know if you manage to find an
issue with it!*

[acoustic river]

!e discord

[trim fiber]

Use #bot-commands channel to deal with bots

[acoustic river]

ok thx

[trim fiber]

Probably your file is in different directory

#game-development is more suitable channel for pygame

[idle pier]

Hello folks am currently doing rotate array on leetcode

def rotate(self, nums: List[int], k: int) -> None:
    
        k = k%len(nums)
        l,r = 0,len(nums)-1
        
        while l < r:
            nums[l],nums[r] = nums[r],nums[l]
            l,r = l+1,r-1
            
        l,r = 0,k-1
        while l < r:
            nums[l],nums[r] = nums[r],nums[l]
            l,r = l+1,r-1
            
        l,r = k,len(nums)-1
        while l < r:
            nums[l],nums[r] = nums[r],nums[l]
            l,r = l+1,r-1```
I dont understand what exactly is happening for the `r` pointer, the `r = k-1` and also the `l` pointer, the `l = k`

[feral hound]

why dont you just use slicing to do this?

will be much faster

@idle pier have a look at this

you can see what each loop is doing there

the first loop swaps the numbers to the sections they should be in but it also reverses their order

so the second loop reverses the order of the numbers in the first section again to make it right

and the third loop does the same for the second section

but yeah using slicing will be a lot more straightforward and faster

[tropic glacier]

What's the goal of the algorithm?

[feral hound]

https://leetcode.com/problems/rotate-array/

rotate an array to the right

the current solution that he posted is one of the slower and most unintuitive solutions ive seen though

[tropic glacier]

Yeah, slicing would be one line

Although it would not be in-place

[feral hound]

well slicing passed all the test cases so it works out I guess

[fiery cosmos]

I saw somewhere, that if the python file and the image file is in same place then i just need to put the name of the picture

is there a way to loop over objects and get a group of them at a time? like a group of three then the next group of three? Not to be confused with window that does something a lil different

i know how to do it with indexes but i was wondering if there is already a solution like in itertools

[shut breach]

there is probably a solution in itertools

[shut breach]

had to go to more_itertools smh
https://more-itertools.readthedocs.io/en/latest/api.html#more_itertools.chunked

[fiery cosmos]

i opted for this

        for i in range(0, len(self.components), len(self.type)):
            entity = []
            for component in self.components[i:i+len(self.type)]:

[keen hearth]

So like [0, 1, 2, 3, 4, 5] -> [(0, 1, 2), (3, 4, 5)]?

If so, there's kind of a trick, which is to pass the same iterator multiple times to zip.

[fiery cosmos]

yep i saw that too

[keen hearth]

!eval ```py
def groups_of_three(iterable):
it = iter(iterable)
return zip(it, it, it)

print(list(groups_of_three('abcdefghijklmnop')))

[halcyon plank]

@keen hearth :white_check_mark: Your eval job has completed with return code 0.

[('a', 'b', 'c'), ('d', 'e', 'f'), ('g', 'h', 'i'), ('j', 'k', 'l'), ('m', 'n', 'o')]

[keen hearth]

Note that you will lose elements if the length of the iterable is not a multiple of three.

You could probably also do something with itertools.groupby 🤔

[jolly mortar]

whoa that's neat, never seen that before

[austere sparrow]

this is quite neat

it's like tee but in reverse

[lapis storm]

when you for loop through an list slice i.e. for idx in list[3:], is a new list being generated, or are you just starting the iterator at 3

[fervent saddle]

It makes a new list

[lapis storm]

thanks

[fervent saddle]

itertools.islice can be used to start at a specific spot. But underneath, it just iterates until it reaches the position

You could also use iter to get an iterator and then pass it to next until it’s at the right position

[finite pond]

hello, I hope this is the right place to ask this, but I have the following weirdness:
I have a 3x3 numpy array of (eigen)vectors. I want to stratify them such that the first one is always x positive, the second one is y positive etc. and be right-handed

the following simple code solves makes this happen but I noticed that its awfully slow

for i in range(3):
        if eigVec[i,i]<0:
            eigVec[:,i] = -eigVec[:,i]

Is there anything inherently wrong or inefficient with this? Because I don't see it

[flat sorrel]

Technically you could vectorize the loop, but since you're only looping over 3 elements it doesn't really matter

Since you're only dealing with a 3x3 array, speed isn't a concern if you only have to do it once

Are you running this inside an outer loop?

[finite pond]

yeah, this is part of my dataloader for each label. it runs very often

but it feels like this part is slower than resizing images and performing the eigen value/vector decomposition in the first place

[flat sorrel]

How do you know?

[finite pond]

before I added these three lines it ran at ~2.4 it/s and since I added this it heavily fluctuates down to 1 it/s.

I just didnt expect such a seemingly light function to affect this compared to some heavier operations

[flat sorrel]

well, you can try vectorizing the loop and see if it's better

I really doubt it though

mask = np.diag(eigVec) < 0
eigVec[:, mask] *= -1

[finite pond]

for reference, the difference between adding a big layer to the network or doing/not doing the image resizing is in the range of 0.5 it/s. also the fluctuation indicates to me that it is the inplace operation that only occasionally needs to be performed

oh, that's what you meant with vectorization, that's nifty. thank you!

[flat sorrel]

Python loops are really slow, so converting loops into vectorized operations (which NumPy runs in C) can dramatically increase speed

[finite pond]

it still fluctuates, but with a lower amplitude? so I'll take it. maybe I'm blind and missed something elsewhere. Thank you very much!

[flat sorrel]

No problem 🙂

[fiery cosmos]

+1 to that. I've seen andrew just performing dot operation with their functions and by loops the difference was oh my god!!!

[woeful siren]

my_list = ["A", "B", "C", "D", "E", "F"]
my_list2 = [1, 2, 3]

for i in my_list and my_list2:
    print(i)

Why it printed the following, rather than 1A, B2, C3:
1
2
3

[flat sorrel]

(My bad, ignore what I said before.)
To achieve what you want, you should use this instead:

!zip

[halcyon plank]

The zip function allows you to iterate through multiple iterables simultaneously. It joins the iterables together, almost like a zipper, so that each new element is a tuple with one element from each iterable.

letters = 'abc'
numbers = [1, 2, 3]
# zip(letters, numbers) --> [('a', 1), ('b', 2), ('c', 3)]
for letter, number in zip(letters, numbers):
    print(letter, number)

The zip() iterator is exhausted after the length of the shortest iterable is exceeded. If you would like to retain the other values, consider using itertools.zip_longest.

For more information on zip, please refer to the official documentation.

[winged plover]

!e ```py
my_list = ["A", "B", "C", "D", "E", "F"]
my_list2 = [1, 2, 3]

print(my_list and my_list2)

Like darklight said correct method to get what u want would be zip

[halcyon plank]

@winged plover :white_check_mark: Your eval job has completed with return code 0.

[1, 2, 3]

[woeful siren]

no

[winged plover]

Huh?

[raven kraken]

Hey, Can anyone tell me why my code is failing for test case s = "textbook", it should return False but it is returning True?

[austere sparrow]

@raven kraken What values will the i and j variables take?

[raven kraken]

I am iterating i through first half of string and j to another half

both the halves are equal

[austere sparrow]

So what values will i and j have? Can you give examples?

[devout delta]

Anybody else do all their leetcode code golf stuff in 1-2 lines with list comprehensions and filters and maps?

and have the speed be 5% because of it LOL

[raven kraken]

Yeah sure if for example s = "book" i will iterate through 'b' and 'o' and check if they are present in the vowels array if yes then it will add 1 to count_left, similarly with j it will have look at other half 'o' and 'k' and add 1 to count_right.

[austere sparrow]

But what values will be in the i and j variables? Lists? Dicts? Tuples? Integers? Strings?

[raven kraken]

Dammmmmmmmm got it, let me try

[raven kraken]

Thank you so much man it worked

[fiery cosmos]

Hey guys. I'm very new to data structures and I'm confused as to why the answer to the first example in this leetcode question isn't 1, since root -> 9 is one edge. Isn't 9 a leaf node? It has no children. https://leetcode.com/problems/minimum-depth-of-binary-tree/

[devout delta]

They are counting the root as depth 1

if the tree was None the depth would be 0

[shut breach]

a fun thing about trees is that you can measure the depth as counting nodes or edges, and often people don't specify

it doesn't matter in asymptotics, but you get off-by-one errors

[fiery cosmos]

Ooh I see, thank you.

[stray magnet]

wheres the general chat

[grizzled schooner]

in case you haven’t found it already, #python-discussion it’s easy to get lost in a server with so many channels

[stray magnet]

oh thanks

[idle pier]

Hello folks, I found this problem and I find it interesting

[fervent saddle]

It’s impossible if a number appears more than twice? just finished reading it, it says yeah that’s the case

You could use collections.Counter in some way

[idle pier]

is using collections in a interview ok?

[fervent saddle]

Probably

But if it’s not then you can just do the same thing without the Counter

[fiery cosmos]

Making your own counter is pretty simple anyway

[fervent saddle]

yeah it would be weird to mark someone down for it

It’s sort of just a convenience thing

[idle pier]

yea I havent tried to solve yet but I first thought

1. need a counter
2. need a hash or set(not sure which) to check if we have seen the integer already

[fiery cosmos]

yeah, mostly convenience (this is just the setup)

a = [2, 1, 2, 3, 3, 4]

# without counter:

counts = {}
for x in a:
    if x not in counts:
        counts[x] = 0
    counts[x] += 1
    
# with counter:

from collections import Counter
counts = Counter(a)```

[idle pier]

just lost on how to return a split array with unique integers in it

[fiery cosmos]

though here without the counter you can short circuit right away if you see a count more than 2

[fiery cosmos]

You can build the arrays based on the counter. If there's 2 of the num put it in both. If only 1 alternate back and forth where you put the num

!e ```py

def divideArray(a): # a assumed to be even len
counts = {}
for x in a:
if x not in counts:
counts[x] = 0
counts[x] += 1
if counts[x] > 2:
return []
a1, a2 = [], []
add_to_a1 = True
for num, count in counts.items(): # count can only be 1 or 2
if count == 2:
a1.append(num)
a2.append(num)
else:
if add_to_a1:
a1.append(num)
else:
a2.append(num)
add_to_a1 = not add_to_a1
return [a1, a2]

print(divideArray([2, 1, 2, 3, 3, 4]))
print(divideArray([1, 2, 3, 4, 5, 6]))
print(divideArray([2, 1, 2, 3, 3, 2, 4]))

[halcyon plank]

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

001 | [[2, 1, 3], [2, 3, 4]]
002 | [[1, 3, 5], [2, 4, 6]]
003 | []

[fiery cosmos]

there might be a shorter way though

btw the Counter is the hashmap (aka dictionary), you don't need a counter and a hashmap

collections.Counter is just a very thin wrapper around normal python dicts

is there a strategy to remove the first added node in the tree?

and then the one that follows.

Can you give an example of what you mean

[fiery cosmos]

I try to remove the first node that was added to the tree, and then the second and then the third, to keep a limited number of nodes in the tree.

[idle pier]

@fiery cosmos random question here lol
how did you get so good at DS and Algo?

[idle pier]

for add_to_a1 = True, what exactly is it doing?

[fiery cosmos]

I do code challenges every day and studied them in school

That's just saying that for numbers with only 1 copy we'll add to a1 first (but False would work too since add_to_a1 alternates and we know a is even length so a1 and a2 will end up the same length)

[idle pier]

ahhh ok, I see

[cloud bridge]

Hey guys, i have a question regarding an long running algorithm that i'm working on. Better said i'm trying to estimate the runtime of said algorithm.

The algorithm generates a world in a spiral pattern.

I start in the center with x = 0, z = 0 as coordinates
A step is of one of the first two segments in the spiral (from the center). So the spiral goes 1 step, 1 step, 2 * 1 step, 2 * 1 step, ...

Each step has a configured length (as of now 160 units)
Each step takes ~5 seconds.

I want to calculate the time it takes to arrive at X = 50,000 and Z = 50,000

Do you have any idea how this can be easily calculated?
My brain is toast right now 🙃

[feral hound]

so the sequence goes

1 1 2 2 3 3 4 4 5 5 6 6.. 50000 50000

?

@cloud bridge

[fiery cosmos]

That's how I read it too. So 2 times the 50000th triangular number, aka 50000*50001

or maybe the 49999th

[feral hound]

sum of the series * time should give them what they want if its what im understanding

sum of the series would be
50000 * (1 + 50000)

[fiery cosmos]

yeah, somewhere around 5sec*50000*50001

[feral hound]

^^

[cloud bridge]

The 50k is the destination coordinates

The Sequence 1,1.. is 160 units up 160 units left

[feral hound]

then its

160 * 161 * 5

[fiery cosmos]

right but that takes 10 seconds since it's 2 steps?

or is it 5 sec per pixel of the 160 👀

[cloud bridge]

'Phase' 2 would take 2 * 5 seconds and equal 2 * 160 units
'Phase' 3 would take 3 * 5 seconds and equal 3 * 160 units

[feral hound]

so how many phases is it?

or is that part of your question?

[cloud bridge]

N really.

I want to
a) Know how many steps i have to go until i reach coordinates above 50,000
b) steps * 5 seconds (how long it'll take)

Center is 0,0
Step 1 (up) -> 0, -160
Step 2 (left) -> -160, -160
Step 3 (first down) -> -160, 0
Step 4 (second down) -> -160, 160

[feral hound]

looking at this I think its 100000 steps to reach coords of 50000

actually mb based on what your doing

its
100000 * 100001

[cloud bridge]

@feral hound
Hmm ... so that would be 13889027 hours or 1585 years?! 🤔

I'm testing it on small scale right now but that seems a bit ... long ^^

[feral hound]

if it seems like it wont take that long then maybe your steps dont take 5 seconds

but yeah that would take a while lol

[fiery cosmos]

hey, so im trying to self learn DSA, what do you all suggest me to do

[trim fiber]

Have you seen pinned messages?

[fiery cosmos]

Oops, nope

Ill check it out

[worn shard]

Hey guys. Does anyone know how to code the genetic algorithm?

[vocal gorge]

what do you have trouble with?

[rain temple]

does anyone know a good way to visualize a trie?

in the command line

[devout delta]

maybe level order traversal with 1 line of / and \ between ?

[idle pier]

hello folks, am currently doing middle of the linked list on leetcode. I did it differently than this solution am going to show y'all. I having trouble understanding what exactly is going on

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        fast = slow = head
        
        while fast and fast.next:
            fast,slow = fast.next.next,slow.next
        return slow```

[fervent saddle]

It looks like you go through the linked list one node at a time with slow, and you go through it but two nodes at a time with fast, and that makes it so when fast reaches the end, slow is half way through

[idle pier]

this problem must return the middle node but if there's two middle nodes then we return the second middle node. I just don't understand how does the slow return the exact middle node

[fervent saddle]

Like why it can’t be one off?

Idk

I guess it’s one of those things where you’d need to stare at it and think about it for a while

[idle pier]

so in other words, once the fast reaches the end of the list, the slow will end up in the middle?
Is this whats happening? lol

[fervent saddle]

Seems like it, yeah

If it’s a two-way linked list, I think you could start iterating inwards from both ends, and then stop when both directions reach each other

I mean, it’s O(n) no matter what, but it might be a faster O(n)

[shut breach]

when fast has reached the end let's say we went through n iterations, and since it does two nodes per iteration, it will have gone through 2n nodes
in the same n iterations slow will have gone through n nodes
n/2n = 1/2

[idle pier]

ohhhhhhhh ok ok, I understand it much better now

the n/2n = 1/2 really helped out a lot

so basically the fast goes through the linked list twice and once the fast goes through it twice, where ever the slow is, will be the middle of the linked list
Is this correct? @shut breach

[shut breach]

it only goes through once

if fast went through twice, slow would reach the end of the list

the key is that slow is going exactly half the speed, so when fast reaches two halves, slow reaches one

[idle pier]

hmmm I see

[keen hearth]

@idle pier I made a diagram 😄

Odd number of nodes:

Even number of nodes: <incorrect diagram>

The two pointers make the same number of hops, but because the fast pointer travels twice as far per hop, by the time it reaches the end of the list the slow pointer has only made it half way.

And you can see just by examining cases that in the event of a list with an even number of nodes, this process selects the latter former of the two middle nodes.

To be clear, the process stops as soon as the fast node is no longer able to make another hop: either the current node has no successor, or the successor of the current node has no successor.

[feral hound]

        while fast and fast.next:
            fast,slow = fast.next.next,slow.next

isnt next called 3 times on fast here?

so its not going 2 but 3 per iteration or am i missing something?

nvm I get it now I was confusing it with next()

[devout delta]

when in doubt draw examples on paper of each case

[keen hearth]

Oh wait, this is wrong 🤦‍♂️

Should have been:

[vocal gorge]

if you're generating all paths anyway, wouldn't this just mean that you can't pass through that node (and so should ignore it)?

[devout delta]

ya you'd just treat that property as the node having further paths

[vocal gorge]

hmm, I guess you can have the blockage lead to the node you came from, but then you need to make sure to prevent the path from returning to the blockade again.

[devout delta]

i mean if ur just running DFS u just check the properties as you go along and it'd be the same logic as when you hit deadends from DFS

[devout delta]

maybe i'm wrong but i thought both DFS and BFS generate all paths through a graph just with a different selection strategy

[feral hound]

^^ they do

can you show us your code rn?

also if you can draw the graph to show us what you mean that would be helpful

i.getVisited() == False:

ok then how about doing this

yeah its where the else was

can you draw a diagram because I dont think im understanding what you mean tbh

ahh I see what you mean now with it going back

I would say call the function again passing in the parent node and continue again from there

[keen hearth]

🤔

[feral hound]

actually based on how ur doing this it wont work

[vocal gorge]

all paths not traversing the same edge twice?

[feral hound]

you have it so that you only visit unvisited nodes

[vocal gorge]

now that I think of it, you can also just

split B

for every node X that has a connection to B, add a new node B_X that connects to X and back.

and eliminate B entirely

[keen hearth]

Take the set of nodes comprising all the "blocking" nodes, and the start and end nodes. It sounds like you're looking to find all paths between every pair of nodes in this set, then to join these paths together to get paths from the start node to the end node?

[vocal gorge]

ooh, though that's not equivalent since you can't visit B more than once. I see.

[feral hound]

just to be clear you mean not visit the same node twice in the same path correct?

only exception being a block which will set you back

ok yeah what I told you should work then

make it so that your function also takes in the parent node

[keen hearth]

Oh right. So the path backtracking from a blocking node should only ever have a single edge?

[feral hound]

and if you reach a block set it to visited then make the path continue again from the parent

btw can you go to the same block twice so for example
ABAEBEF

[keen hearth]

I guess generate all paths that don't encounter a blocking node. Then if in a path you have a node A that is adjacent to a blocking node B, you can replace A in the path with ABA?

[vocal gorge]

You can? Then I'd use the approach I mentioned above

ABAEBEF would be instead written as A B_A A E B_E E F, visiting two "copies" of the block B - one for A and one for E

B_A and B_E are completely normal nodes, just connected only to their parent node with a double link

that way, you translate a task from having few "blocks" which are special nodes (you can visit them many times, but not from the same direction), to many "copied blocks" which are normal nodes (you can visit each not more than once, and that's it)

[feral hound]

try this

[vocal gorge]

here, say

my claim is that the right graph (where B_A, B_E, B_F are normal nodes) is equivalent to the left one (where B is a block)

[coral obsidian]

back reading, what do you mean the B_ variants are normal nodes, are you implying the E,A,F are "blocks"?

[vocal gorge]

No, B is a block

[feral hound]

damn too much recursion

need to look at it a bit more but i think I might have caused it to loop which caused that

[vocal gorge]

basically, the transformation I propose is as follows:

1) For each block B in the graph...
    2) For each node X that connects to B...
        3) Add a new normal node B_X that connects with an undirected edge to X
    4) Eliminate B

[coral obsidian]

Just re-read, do you mean b_, variants are blocks and the others are regular nodes?

[feral hound]

what does
pathBuilder.pop()
cur.clearVisited()
do?

[vocal gorge]

No, I call them B_... because they are derived from the block B. But they are regular nodes. The idea is that we just get rid of blocks entirely.

[coral obsidian]

ty

[vocal gorge]

Like, get rid of it and edges connected to it.

My claim is that the result is equivalent to the original graph, but the result doesn't have any blocks - only normal nodes.

[coral obsidian]

by "getting rid of it", it will still need to be there no?

B will just act as a node that will cause it to go back to the origin node where it comes from, thats what hmm is trying to do i presume

unless im reading the whole situation wrong

[feral hound]

ngl the way you've coded this makes it seem a lot more complicated to me lol

[vocal gorge]

After you get a path in the transformed graph, like A B_A A E B_E E F, we transform it back to the original representation by replacing each B_... with B. So that path would be A B A E B E F

[feral hound]

cur.clearVisited() is making the node that we havent visited it

what do you mean by it?

[vocal gorge]

That's the thing - since a block is "such a node that, having gone to it, you can only go back where you came from", we can, for each node X connected to B, replace B with a normal node that's only connected to X.

[feral hound]

isnt that what this is doing
cur.setVisited()

ohh wait nvm I get what your doing now

try this

this makes sense no?

it visited each node once for a path

if you want I can make it so it only considers blocks once

the reason it wasnt working before was because I misunderstood what
pathBuilder.pop()
cur.clearVisited()
were doing lol

[coral obsidian]

no

hes right

b isnt visted twice

[feral hound]

do you understand why it works though?

so if its not a block everything continues as normal

the else executes when it is a block

and it calls the _generatePathsRec function with its parent as the next node instead of its children

does that explain it or still a bit unsure?

yeah parent is the node it came from

thats what I added to make it work

btw im doing this on the assumption that your root node can not be a block

it is modified look at the for loop

cur is passed in the for loop as the parent node

for i

none is just there for when you dont know the parent or if there is no parent

and we only actually care about the parent on a block anyway

since we need to go back to it

ABAEF

here A is the parent of B

gl 🙂

btw now that I think about it calling it prev instead of parent might be more consistent with your naming since you use cur as a name for the current node

prev for previous node

[feral hound]

send me the code you used

just to make sure

@stark bronze

this is what I sent you before

yeah looks the same

other than you returning at generate paths

cur.setVisited()

this sets visited to true right?

ABFHFGDCBFEFIJ

I dont see how this could have happened tbh

it first goes wrong when it vists B the second time

but if B was marked as visited then it shouldnt have gone there

try this rq

what line was that in?

aight

[azure matrix]

Curious if anyone has any thoughts on this...

Given a list of numeric sequences, return the one that is easiest to memorize
Obviously that's going to be subjective but... does anyone have any thoughts about an approach to such a program? I think there could be a lot of useful (and amusing) applications, like memorizing solutions to single player games

[feral hound]

I would think something is either wrong with the nodes or just the B node in general

or your setVisted and getVisited functions

I cant see why it wouldnt work other than that

aight np gl 🙂

feel free to @ me when you wana work on it again

[feral hound]

well as you say this is quite subjective

if you lay down some rules for evaluating how memorizable a sequence is this is fairly simple

[azure matrix]

Yeah -- some things I've considered looking at:

1. Finding the most-sorted sequence
2. Cross-referencing http://oeis.org/
3. Symmetry
4. Alternation
5. Fewest unique elements

[feral hound]

other things you can look at is if the sequence follows a pattern or not as well

for example if its an arithmetic sequence or a geometric sequence

[azure matrix]

yeaah, that's what I was thinking about with oeis.org

it's a large database of numeric sequences, so if it's one of those that'd definitely be a good one

[feral hound]

not sure why you say it would be good if its there but yeah if you just set up some rules either to give each sequence a score

or to directly compare 2 sequences then you can do this

for now you could always start with a very simple algorithm and improve on it with time

for example just set a sequences score to be its length and search for the lowest score

[azure matrix]

I mean I guess it depends on what the sequence is -- if it's one of the ones that you can calculate easily in your head, like powers of 2, then great. If it's "number of trees with n unlabeled nodes" then maybe not

[feral hound]

as I said its really up to you how many rules/checks you add

I can show you how to check if a sequence is arithmetic or geometric if you want

you could also set it so that arithmetic sequences with larger difference between terms are harder to memorize things like that

[azure matrix]

There's a lot of research on "memorability scores" for images, apparently: https://arxiv.org/pdf/1901.11420.pdf -- I wonder if there's any research out there for something like that for general sequences

[feral hound]

now that I think of it an easy way to do this as well would be to first compile data on a bunch of sequences and how memorable they are then train a neural netowork for the task

easy as in you wont have to come up with a bunch of rules btw not that its actually gona be easy to get the data

[azure matrix]

yeaaah, I wonder if that's already been done for me somewhere 🙂 -- indeed that data sounds annoying to collect

Maybe I could train it as a classifier -- "memorable" vs "not memorable" -- then just take memorable sequences and compare them to noise.

highest probabilities of being memorable == most memorable? I don't necessarily care about it putting the most memorable ones at the very top, just that it can filter out most of the garbage and show some good candidates

[feral hound]

yeah could work

your gona have to look into sequence models btw since I'm assuming your sequences can have varying lengths

[azure matrix]

Yeah I was wondering about that. "Should I train something for each possible length I want to support? That sounds annoying" -- makes sense there's a solution for that, I haven't played with any models that have varying lengths but I've done plenty of ML with fixed lengths

[feral hound]

^^ same here never done any work with sequence models either lol

[azure matrix]

So probably gonna try scraping OEIS for sequences that have "simple" formulas (I'll have to define what simple means but I'll try to filter for things that only involve math you could easily do in your head, so no logarithms etc)

[feral hound]

if your gona do that then the neural network isnt needed

unless you do something else with those scraped sequences to determine which ones are easier to memorise

[azure matrix]

Yeah, the latter

[feral hound]

that might make your network very bad for difficult sequences it hasnt seen though

you would want to make sure that the data you extract will be similar to the data that your model will see in production

otherwise it probably wont work very well

[azure matrix]

Right -- well, when you're hoping for a "general" solution it's super hard to think about what data you'll see in production. The idea came from being confronted with 29760 solutions to triangle solitaire :P

[feral hound]

lol

well if your going for a general solution then make it as general as possible

at the end of the day you can just use this as a proof of concept and train more specific models when you have an application for them

[feral hound]

this means dont only target the easy sequences unless thats what you want for now

[halcyon plank]

Hey @azure matrix!

Uh-oh! It looks like your message got zapped by our spam filter. We currently don't allow .json attachments, so here are some tips to help you travel safely:

• If you attempted to send a message longer than 2000 characters, try shortening your message to fit within the character limit or use a pasting service (see below)

• If you tried to show someone your code, you can use codeblocks
(run !code-blocks in #bot-commands for more information) or use a pasting service like:

https://paste.pythondiscord.com

[feral hound]

lol

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

[azure matrix]

lol my sequences are too strong

[feral hound]

damn thats a lot of sequences

although a lot of them seem to be very similar

[azure matrix]

yeah, they're all paths to a winning solution

[feral hound]

ahh

if you wana use those I would say make a little game where you show a sequence for like 10 seconds then give the 30secs to rewrite it

add a few rules to how you want to evaluate the data for example a longer time to respond means a harder sequence

more wrong terms in a response means a harder sequence etc

also if your sequences are all constant length then just use a normal NN for now and look into sequential models later

[feral hound]

make sure you select the sequences at random as well

[keen hearth]

Probably related to algorithmic entropy.

[tropic glacier]

Maybe something similar to the scoring system used by Mathematica's Simplify

1. Assign some intrinsic scores to the basic arithmetic operations. 2. Fit the first n elements of the sequence to a formula using those operations (the fit must be exact so that the formula reproduces the sequence). 3. Rate the complexity of the formula.

Of course, if you're only given the first n elements of the sequence, it's possible you may get the (n+1)-th element wrong.

[idle pier]

hello folks, I came into a realization that I struggle with 2d array problems. I run into this problem

def print_classification(raw_data):```

I have difficulties accessing the elements of a 2d arrays

[modest ember]

@idle pier are you still online?

[idle pier]

of course. My life now is breath,eat, and sleep DS and Algo lol

[modest ember]

lol

I probably won't read the entire problem, but I can help if you have any specific questions abt working with arrays

[feral hound]

@idle pier I just read the problem but what exactly are you struggling with?

[idle pier]

I was struggling with how to access the points to compare it with the maxSize @feral hound

[maiden timber]

Hey all -- is this space complexity(because of the set), O(N+M), or O(N), because its still the same input?

    map = {}

    inputs = str_input.split()
    input_set = set()
    for input in inputs:
        input_set.add(input)
        try:
            count = map[input]
            map[input] = count + 1
        except KeyError:
            map[input] = 1
    return map, input_set```

[feral hound]

what do you mean by compare it with maxSize?

[idle pier]

whoops sorry confused with a different question

I meant I was struggling on how to compare the total points of each racer

[feral hound]

ok since the data is quite convenient and they say you cant have more than 100 racers

I would say first make a list of 100 zeros called points

now to index points you can do points[racer_id - 1001]

and just add the points the racer gets like that

now as for how you can access the data you need which is the racer id and their position in the race

you can do something like this

!e

data = [[2001, 1001, 2], [2001, 1002, 1]]

for record in data:
    print(record)
    print(record[1])
    print(record[2])

[halcyon plank]

@feral hound :white_check_mark: Your eval job has completed with return code 0.

001 | [2001, 1001, 2]
002 | 1001
003 | 2
004 | [2001, 1002, 1]
005 | 1002
006 | 1

[feral hound]

I would also store the scores for each place in a list as well

and you can add an if statement so that you only add to the score if the racers position was 6 or higher so you will only need a 6 element list

@idle pier did that explain everything?

[feral hound]

I would say O(N) since you know that worst case the set will also be N so its 2N which is still N

[maiden timber]

@feral hound 2N because we have two separate stores that store both forms of input?

[feral hound]

yeah

worst case would be if each input was different btw

that also applies to the dict btw

and tbh it wouldnt really be 2N since dicts take up a bit more space then that but in big O notation we dont care about the constants anyway so its still N

you could say N + M if you want aswell but it doesnt really matter in this particular case

best case would be O(1) btw

thats if all inputs are the same

actually now that I look at it again your only storing something for the unique inputs anyway so its
best case O(1)
average case O(M) M number of unique inputs
worst case O(N) N number of inputs

@maiden timber

[maiden timber]

yeah, no repeating values

Why is avg case O(M), rather than O(N)?

[feral hound]

because in both the dict and the set your only storing something for the unique inputs

[maiden timber]

@feral hound Got it -- really helpful, thanks

[maiden timber]

@feral hound When is a algo O(N+M) ? When I have two inputs, or if I break up a single input into another segment?

[bright halo]

This is the code but the part of the error is where is the extraction of the substrings after validating the regex pattern structure

def name_and_img_identificator(input_text, text):
    input_text = re.sub(r"([^n\u0300-\u036f]|n(?!\u0303(?![\u0300-\u036f])))[\u0300-\u036f]+", r"\1", normalize("NFD", input_text), 0, re.I)
    input_text = normalize( 'NFC', input_text) # -> NFC
    input_text_to_check = input_text.lower() #Convierte a minuscula todo


    #Regex in english
    regex_patron_01 = r "\ s * \ ¿? (?: tell me the | tell me some| tell me | say | which are the | which are the | which are | which | which animes | which | top) \ s * ((?: \ w + \ s *) +) \ s * (?: anime series | anime series | anime | anime | anime | anime) \ s * (?: similar to | similar to | similar to | similar to | similar to | similar to | similar to | similar to) \ s * (?: the anime series | anime series | the anime series | the series | anime |) \ s * (called | known like | whose name is | which is called |) \ s * ((?: \ w + \ s *) +) \ s * \ ?? "

    m = re.search(regex_patron_01, input_text_to_check, re.IGNORECASE) #Con esto valido la regex haber si entra o no en el bloque de code

    if m:
        num, anime_name = m.groups()[:2]

        num = num.strip()
        anime_name = anime_name.strip()
        print(num)
        print(anime_name)

    return text

input_text_str = input("ingrese: ")
text = ""

print(name_and_img_identificator(input_text_str, text))

It gives me this error, and the truth is I don't know how to structure this regex pattern so that it only extracts those 2 values (substrings) from that input

If I put an input like this:
'Give me the top 8 anime like Gundam'

I need you to extract:

num = '8'
anime_name = 'Gundam'

How do I have to fix my regex sequence in that case?

I was trying that but I have num = '8' and anime_name = ''. But I need num = '8' and anime_name = 'Gundam'

[wheat flare]

@stable pecan hey long time no see, networkx was working well for my needs previously

just wanted to ask is there a way for networkx to find shortest paths without a source?

just the goal is known

[stable pecan]

i think if you don't provide a source it will just computer all shortest paths

which could be a long computation

depending on your graph

[wheat flare]

its a 17k node graph which might take a very long time huh

i guess i need to offload it

but i cant find the sources >.>

so its like

n=nx.all_shortest_paths(graph, [source i left empty] ,goal)

i assume

[stable pecan]

i think just nx.all_shortest_paths(g) will give all pair-wise shortest paths, and then you can comb it for your goal

[wheat flare]

oh theres no way to just put goal?

to shorten the thing

[wheat flare]

i think if i do it it might take too long

sorry for the pings

[stable pecan]

if the graph is undirected just put the source as the goal

otherwise, flip the directions of all the edges and put the source as the goal

[wheat flare]

sorry i dont follow

its a directed graph, source as goal?

theres no source

[stable pecan]

yes, if u is the goal --- then flip the orientation of all the edges and use source=u

[wheat flare]

then i leave goal empty?

[stable pecan]

yes

[wheat flare]

hmm...

need to figure out how to flip then

make all json file keys value and vice versa

[stable pecan]

i think there's a builtin for that

[wheat flare]

oh is there

[stable pecan]

https://networkx.org/documentation/stable/reference/classes/generated/networkx.DiGraph.reverse.html#networkx.DiGraph.reverse

[wheat flare]

oooh

then it'll just search the goal as the source

then it'll be like

goal -> x -> x -> source

i assume

[stable pecan]

yep, you'll have to reverse the path you get at the end

[wheat flare]

might need to change it to all paths now since i dont know sources

https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.simple_paths.all_simple_paths.html

i assume this is the method?

[stable pecan]

oh it looks like there's a function for what you want without reversing

https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.shortest_paths.unweighted.single_target_shortest_path_length.html#networkx.algorithms.shortest_paths.unweighted.single_target_shortest_path_length

[wheat flare]

oh?

damn thats cool

just a bit curious is it possible to like

specify the length of the path

o the cutoff

[stable pecan]

yep that's the the cutoff parameter

[wheat flare]

is literally what i asked

aight

thank you

[stable pecan]

np

[tropic glacier]

I don't even understand what this would mean. Shortest path from where to where?

[wheat flare]

i have a goal lets say x

i dont know the sources

i want the paths where they reach x

does that make sense?

[tropic glacier]

The paths from where to X?

[wheat flare]

yes but i dont know the sources i mean

cause networkx is (graph, source,goal)

i dont have the source

https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.shortest_paths.unweighted.single_target_shortest_path_length.html#networkx.algorithms.shortest_paths.unweighted.single_target_shortest_path_length so this is what i wanted

[tropic glacier]

Your question is easy then. Just look at the neighbors of X, and pick the one with the lowest weight.

[wheat flare]

i think i need to test it out

[tropic glacier]

Your question is incoherent, I'm not sure what there is to test

[stable pecan]

pretty sure the graph is unweighted

[wheat flare]

its unweighted and a directed graph

[stable pecan]

the question isn't incoherent, i understood what he wanted

[tropic glacier]

Then all the neighbors of X are shortest distance from X

[wheat flare]

i could have explained it better

[tropic glacier]

I still don't understand it. Do you have multiple candidate sources?

[wheat flare]

yes

[tropic glacier]

Then you do have sources

[wheat flare]

i dont know what the sources are though, its a gigantic graph

[tropic glacier]

What?

Are the candidate sources every node in the graph?

[wheat flare]

erm

actually yea its possible, i dont know which source leads to X

my graph is a combined version of many separate graphs

[tropic glacier]

How is that relevant?

[wheat flare]

i dont really know how to explain it

[tropic glacier]

Which nodes are possible sources, and which aren't?

[wheat flare]

uh i dont know the sources thats the thing

so using that function i wanted to find them

i only know my goal

[stable pecan]

i'm going to bed, if you have anymore questions, just ping me them to me, i'll look at them when i wake up!

[wheat flare]

thank you

[fluid prism]

Rest in peace 😈

[feral hound]

two inputs would make sense for O(N+M) breaking up an input that really depends on how you do it but will probably stay O(N) in that case

the idea of big O notation is that you look at how things scale so as N gets bigger how much longer will my program take to run or how much more space will it take

so if you only have 1 input it doesnt make sense to split it for big O notation unless it has a significant impact

[burnt spade]

https://media.discordapp.net/attachments/878398801314975824/889203094729150524/unknown.png

[fallen sable]

Can any tell me how to write a recursive function for selection sort? ( using no loops)

[feral hound]

just to check first why are you doing this?

is it a school assignment?

@fallen sable

[feral hound]

this took me a while but I think I finally understood what they want, they want to find which nodes can be used as sources to the goal

so its essentially a reverse search for all valid paths

[fallen sable]

My friend has been asked in his interview.

[feral hound]

do you understand recursion?

[fallen sable]

Yeah!

[feral hound]

ok how about passing in a deep copy of the original array and a sorted array with the length of the original array

then on each recursive call you append the minimum of the array to the sorted array

and remove the element you appended from the array

then when the sorted ararys length is the same as the original arrays length you return the sorted array

does that make sense?

[fallen sable]

I didn't get you complete

[feral hound]

!e

import copy
def recursive_selection_sort(array):
    array = copy.deepcopy(array)
    def selection_sort(array, sorted_array, length):
        if length == len(sorted_array):
            return sorted_array

        min_value = float('inf')
        index = 0
        for i, num in enumerate(array):
            if num < min_value:
                min_value = num
                index = i
        sorted_array.append(array.pop(index))
        return selection_sort(array, sorted_array, length)

    return selection_sort(array, [], len(array))


print(recursive_selection_sort([5, 2, 6, 5, 9, 8]))

[halcyon plank]

@feral hound :white_check_mark: Your eval job has completed with return code 0.

[2, 5, 5, 6, 8, 9]

[feral hound]

you might not have seen this before but you can nest functions in python

[fallen sable]

But we aren’t suppose to use any loops

[feral hound]

oops

!e

import copy
def recursive_selection_sort(array):
    array = copy.deepcopy(array)
    def selection_sort(array, sorted_array, length):
        if length == len(sorted_array):
            return sorted_array

        min_value = min(array)
        index = array.index(min_value)
        sorted_array.append(array.pop(index))
        return selection_sort(array, sorted_array, length)

    return selection_sort(array, [], len(array))


print(recursive_selection_sort([5, 2, 6, 5, 9, 8]))

[halcyon plank]

@feral hound :white_check_mark: Your eval job has completed with return code 0.

[2, 5, 5, 6, 8, 9]

[feral hound]

no explicit loops here

[fallen sable]

Thanks

[feral hound]

do you understand how this code works?

[fallen sable]

Yeah I got it

Basically you are appending the min value in the sorted array from the original array

[feral hound]

yup

do you know why I had to use deepcopy?

[fallen sable]

That’s pretty nice approach

Yeah python doesn’t support overloading

So we have to create a copy

Correct me if I’m wrong pls

[feral hound]

this part im not sure what you mean

[fallen sable]

Okay ! Can you tell the reason?

[feral hound]

lists in python and pretty much every other programming language are passed by reference not by value

so if we dont make a deep copy we will modify the original list

!e

import copy
def recursive_selection_sort(array):
    array = copy.deepcopy(array)
    def selection_sort(array, sorted_array, length):
        if length == len(sorted_array):
            return sorted_array

        min_value = min(array)
        index = array.index(min_value)
        sorted_array.append(array.pop(index))
        return selection_sort(array, sorted_array, length)

    return selection_sort(array, [], len(array))

my_array = [5, 2, 6, 5, 9, 8]
print(recursive_selection_sort(my_array))
print(my_array)

[halcyon plank]

@feral hound :white_check_mark: Your eval job has completed with return code 0.

001 | [2, 5, 5, 6, 8, 9]
002 | [5, 2, 6, 5, 9, 8]

[feral hound]

with deep copy

!e

import copy
def recursive_selection_sort(array):
    def selection_sort(array, sorted_array, length):
        if length == len(sorted_array):
            return sorted_array

        min_value = min(array)
        index = array.index(min_value)
        sorted_array.append(array.pop(index))
        return selection_sort(array, sorted_array, length)

    return selection_sort(array, [], len(array))

my_array = [5, 2, 6, 5, 9, 8]
print(recursive_selection_sort(my_array))
print(my_array)

[halcyon plank]

@feral hound :white_check_mark: Your eval job has completed with return code 0.

001 | [2, 5, 5, 6, 8, 9]
002 | []

[feral hound]

without deep copy

[fallen sable]

Ohokay I got it

Thanks

Well I tried to do swapping

Of min value to the starting index of array everytime

That didn’t work I don’t know why

[feral hound]

show me what you tried

[fallen sable]

i is start index for swapping

And j is no of iteration we have to perform

Number*

[feral hound]

well you have a lot of different errors here

[fallen sable]

Can you help?

[feral hound]

@fallen sable this is how to make it work with something similar to your method

i is the current iteration

j is the index for the current minimum

k is the current index we need to find the minimum for

!e

def sel(arr, i=0, j=0, k=0):
    if k >= len(arr) - 1:
        return arr

    if arr[i] < arr[j]:
        j = i

    if i >= len(arr) - 1:
        arr[k], arr[j] = arr[j], arr[k]
        k += 1
        i = k
        j = k
    
    return sel(arr, i+1, j, k)

print(sel([5, 2, 6, 5, 9, 8]))

[halcyon plank]

@feral hound :white_check_mark: Your eval job has completed with return code 0.

[2, 5, 5, 6, 8, 9]

[fallen sable]

Wow !

Thanks a lot

[feral hound]

its equivalent to this btw

!e

def sel2(arr):
    for k in range(len(arr)):
        j = k
        for i in range(k, len(arr)):
            if arr[i] < arr[j]:
                j = i
        arr[k], arr[j] = arr[j], arr[k]

    return arr

print(sel2([5, 2, 6, 5, 9, 8]))

[halcyon plank]

@feral hound :white_check_mark: Your eval job has completed with return code 0.

[2, 5, 5, 6, 8, 9]

[feral hound]

if that helps you understand a bit more whats going on

[fallen sable]

@feral hound yeah I got it! Thanks for your help.

[twin tiger]

Stuck with this : https://hastebin.com/raw/iyopujenaz

[maiden timber]

Got it -- but is there a case where I could split an input and it becomes N+M? Maybe having an input where each array has an array of characters? But, that to me still seems O^2.

[shut breach]

big O is just a classification for functions; it's up to you to choose a function that describes something useful

if you just arbitrarily change variables from n to n+m, all you've done is obscured the relevant measure of the size of the input

whereas eg there are graph algorithms that are O(v+e) because the number of edges and number of vertices in a graph can vary independently, and v+e describes how they contribute to the runtime of the function

[idle pier]

hello folks, am currently doing Top K frequent words on leetcode, this is my solution

class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        seen = {}
        count = 0
        
        for i in range(len(words)):
            if words[i] not in seen:
                seen[words[i]] = i
                count += 1           
            
            if count == k:
                return sorted(seen)
            ```
It returns the most frequent words but it doesn't return them in order, the return should be sorted from the highest frequency of words all the way to the lowest frequency

[feral hound]

this doesnt return the most frequent words btw

it just returns the first k unique words

[idle pier]

🤔 I see

[vocal gorge]

    for i in range(len(predicted)):
        predicted[i,:,:] = torch.sort(predicted[i,:,:],dim=0)[0]

Is there any way to speed this pytorch operation up?

This is a (N,n,2) array, and for each [i,:,:] slice (so a subarray of n 2-vectors) I sort the n two-vectors in ascending order.

this isn't equivalent to sort(predicted, dim=1), I believe, as that considers all N slices for sorting

so it'd be very nice to represent it as a single vectorized operation, but I don't see how.

[peak wadi]

A frog wants to maximize their probability of reaching 1 on a number line from 0.00000001 after 100 turns. Each turn they can choose a number f between 0 and 1 and have 0.55 chance of multiplying their position by 1+f and a 0.45 chance of multiplying their position by 1-f.

[vocal gorge]

Actually, it does seem to be the same, nevermind

[peak wadi]

A frog wants to maximize their probability of reaching 1 on a number line from 0.00000001 after 100 turns. Each turn they can choose a number f between 0 and 1 and have 0.55 chance of multiplying their position by 1+f and a 0.45 chance of multiplying their position by 1-f.

[idle pier]

Many times I get confused when adding onto a dictionary.
whats the difference between this

for i in range(len(words)):
  if words[i] not in seen:
    seen[words[i]] = i```
and this
```py
for word in words:
  if word in seen:
    seen[word] += 1
  else:
    seen[word] = 1```

[tender atlas]

nothing so much difference! approaches are different

[idle pier]

so I found a solution to top k frequent words on leetcode that is similar to what I was trying to do

for word in words:
  if word in seen:
    seen[word] += 1
  else:
    seen[word] = 1
                
return(sorted(seen.keys(),key = lambda w: (-seen[w],w)))[:k]```
I'm having trouble understanding `return(sorted(seen.keys(),key = lambda w: (-seen[w],w)))[:k]`

[feral hound]

well the only real difference is that you add new key value pairs to the array with the word as the key and the index of its first occurence as the value in the first one

but the second one adds words as keys and sets the value to 1 if they arent in the dictionary to begin with

and if they are it increments the value by 1 essentially keeping count of the number of occurrences for that word in the list words

!e

seen = {'a': 2, 'b': 1} # the dictionary
print(seen.keys()) # the keys in the dictionary
print(sorted(seen.keys(), key=lambda w : (-seen[w],w))) # the sorted function in this case is taking 2 arugments 1 what it needs to sort 2 the key which is how it should sort it the key is expressed as a lambda function here w represents a key in the dictionary (-seen[w], w) this creates a tuple with the negative of the frequency for the word w as the first value and the word w as the second value and this is used what sort uses as a rule to compare items so it can sort ie (-4, "hello") compared to (-3, "bye") 

[halcyon plank]

@feral hound :white_check_mark: Your eval job has completed with return code 0.

001 | dict_keys(['a', 'b'])
002 | ['a', 'b']

[feral hound]

the [:k ] at the end just takes the first k elements of the returned list

@idle pier does that explain it?

[idle pier]

sort of, Just having a little trouble understanding the (-seen[w],w))) part 😫

[feral hound]

this is just a tuple

(-frequency, word)

you do -frequency instead of frequency because we need to sort in descending order ie bigger numbers first

[idle pier]

🔥

@feral hound what would I do without you lol

[feral hound]

btw you can do

sorted(seen, key=lambda w : (-seen[w],w))
instead of 
sorted(seen.keys(), key=lambda w : (-seen[w],w))

[idle pier]

is the key a key word or something? I barely used lambda

[feral hound]

key is one of the optional arguments in the function sorted

lambda is just used to make a function

[tropic glacier]

key= is super nice

[idle pier]

hmmm I see
man am almost there with the DS and Algo's, I can feel it lol. I just need about 3-4 weeks more and I'll be just good enough for interviews lol

[feral hound]

!e

def my_func(arr, add=None, mul=None):
    for i in range(len(arr)):
        if add != None:
            arr[i] += add
        if mul != None:
            arr[i] *= mul
    return arr
arr = [1, 2, 3, 4]
print(my_func(arr))

arr = [1, 2, 3, 4]
print(my_func(arr, 1, 2))


arr = [1, 2, 3, 4]
print(my_func(arr, add=1, mul=2))

arr = [1, 2, 3, 4]
print(my_func(arr, 1))

arr = [1, 2, 3, 4]
print(my_func(arr, mul=2))

[halcyon plank]

@feral hound :white_check_mark: Your eval job has completed with return code 0.

001 | [1, 2, 3, 4]
002 | [4, 6, 8, 10]
003 | [4, 6, 8, 10]
004 | [2, 3, 4, 5]
005 | [2, 4, 6, 8]

[feral hound]

took me long enough...

!e

mul = lambda a, b : a * b
print(mul(5, 6))

def mul2(a, b):
    return a * b

print(mul(5, 6))

[halcyon plank]

@feral hound :white_check_mark: Your eval job has completed with return code 0.

001 | 30
002 | 30

[cinder yacht]

How is it possible to bit shift an integer in python more than 32 bits? Currently solving a leetcode question where you have to find the ONLY value in an array that has a duplicate in constant space and without modifying input array (https://leetcode.com/problems/find-the-duplicate-number/). I determined which repeated using bitshifting, but the constraints of the question say that numbers can get as large as 10^5. My solution works, but how am I able to bitshift an integer by up to 10^5 without getting an issue? Would this even be considered constant space?

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        doesExistInt = 0
        for num in nums:
            if doesExistInt >> num & 1 != 0: 
                return num
            else:
                doesExistInt |= 1 << num
        
        return -1

[tropic glacier]

Python 3.9.4 (default, Apr  9 2021, 16:34:09) 
[GCC 7.3.0] :: Anaconda, Inc. on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> 1 << 64
18446744073709551616
>>> 1 << 128
340282366920938463463374607431768211456

I don't see any such limitation for bit shifts

Python integers are BigNums

However, I'm not convinced this is a good way to solve this problem

I have a solution that runs in linear time and uses constant space 🙂

[knotty magnet]

yeah, that's the best possible

[tropic glacier]

It's important to read the actual problem statement, and not try to solve a more general problem than asked.

Also, wow, are these things actually supposed to be representative of "interview questions"? Because that's a fun logic puzzle, but a terrible interview question.

[ivory yacht]

This wouldn't be constant space, since integers allocate extra longs to accomodate the data.

[knotty magnet]

the value of the ints and the size of the list is capped, so it would be constant

[feral hound]

by that logic all solutions are constant since the size of the list is capped

[knotty magnet]

yeah

[idle pier]

Currently trying to solve this problem but am stuck

def maxTickets(tickets):
    tickets.sort()
    _hashmap = {}
    l,r = 0,1
    
    for i in range(len(tickets)):
        diff = tickets[r] - tickets[l]
        if diff == 0 or diff == 1:
            l += 1
            r += 1
            _hashmap[tickets] = i
            
    return _hashmap```

[glossy breach]

Why are you returning a hashmap and not an int

[idle pier]

cuz I dont know any better 😩

[glossy breach]

I mean it straight up told you to return an int

:)

[idle pier]

lol I meant idk how to

how do I do that? @glossy breach

[alpine arch]

What is wrong with my last line of code getting a syntax error?

highway_number = int(input())
   
if highway_number > 0 and highway_number < 100:
    if (highway_number % 2) == 0:
        print('I-{} is primary, going east/west.'.format(highway_number))
    else:
        print('I-{} is primary, going north/south.'.format(highway_number))
        
elif highway_number > 100 and highway_number <= 999:
    if (highway_number % 2) == 0:
        print('I-{} is auxiliary, serving I-90, going east/west.'.format(highway_number))
    else:
        print('I-{} is auxiliary, serving I-5, going east/west.'.format(highway_number))
        else:
            print(highway_number, 'is not a valid interstate highway number.')

[fiery cosmos]

The last else is not attached to an if @alpine arch

[wheat flare]

@stable pecan hello, the previous function you linked worked great, just a bit curious i expected it to return a path but it returns the sources only?

[stable pecan]

n is a dictionary and you're printing the keys

[wheat flare]

ohhh

ok im dumb i expected it to be a list

hm i wonder why it has itself in the value pairs

nwm the dict has it

i guess i can just store the keys and do all pairs shortest path after to avoid this

[stable pecan]

the paths should be the values in the dict

[wheat flare]

no i just print values

yea sorry haha im barely awake

[quiet jay]

#help-lollipop

[visual palm]

I want to separate the date from Testing1 and Testing2 in this string. What should I do?
ex)Testing1/20210910~20210925Testing2/20210910~20210914

[brave oak]

define "separate"

show expected output

[faint sentinel]

hello

i am trying to understand the basics of big-oh from a course on coursera

one of the rules is that mulitplicative constants can be nelgected , i am having a hard time to understand this , is anyone here who can offer some insight into it

[peak wadi]

A frog wants to maximize their probability of reaching 1 on a number line from 0.00000001 after 100 turns. Each turn they can choose a number f between 0 and 1 and have 0.55 chance of multiplying their position by 1+f and a 0.45 chance of multiplying their position by 1-f.

[feral hound]

big O is all about how a solution scales as the input grows

so you dont really care about the exact time or number of operations just the relationship of the input size with the time/space the algorithm takes

so for example I might implement a simple linear search algorithm in 5 lines which is O(N)

and a binary search algorithm in 30 lines which is O(logN)

the binary search algorithm scales much better since every time my input doubles my code only needs to do 1 more operation

but if the input doubles for linear search It will take twice as long since it has to do N more operations

however if we take each line as taking 1 second then each iteration of linear search is 5 operations aka 5N

and each iteration of binary search is 30 operations aka 30logN

so really if our input(N) is small linear search is actually a bit faster than binary search

but it doesnt scale anywhere near as well

so conclusion big O is about how things scale with input so constants really dont matter in that relation which is why we only look at the variables

and if your doing two operations on an input for example one takes N and the other takes logN

the big O would not be O(N + logN) but O(N) instead

because N grows a lot faster than logN so logN is insignificant in this case

keep in mind though this only applies on operations on the same input if its a different input M then you do take it into account since that input could grow much faster than input N and you dont know that

so it would be O(N + logM) in that case

@faint sentinel does that explain it?

[modest ember]

(I haven’t been formally introduced to big O so this did help me a lot actually, thank you lol)

[raven kraken]

You can see this video on Time complexity, One of the best video out there - https://youtu.be/mV3wrLBbuuE

[fossil relic]

lol i just learned this

[merry aurora]

Hey, anyone heard of ECP data files? They come in .txt formats, and apparently you can work with them in MATLAB, however, that didn't work well for me lol

[halcyon plank]

Hey @merry aurora!

Uh-oh! It looks like your message got zapped by our spam filter. We currently don't allow .txt attachments, so here are some tips to help you travel safely:

• If you attempted to send a message longer than 2000 characters, try shortening your message to fit within the character limit or use a pasting service (see below)

• If you tried to show someone your code, you can use codeblocks
(run !code-blocks in #bot-commands for more information) or use a pasting service like:

https://paste.pythondiscord.com

[vocal gorge]

google says it's either from something called eCourse Planner, or from something called EasyC

never heard of either

what does the structure look like?

[merry aurora]

the server doesn't allow .txt files unfortunately, but ill send a pic

Can I read the data like any other text file? and use the values as floats or integers not strings?

[feral hound]

dont see why you cant

[vocal gorge]

weird format

it looks kinda like Fixed Width Format, except for that [ symbol

and the ; at the end of each line I guess

you can certainly write a parser of your own for it, though.

[feral hound]

the format seems to be consistent as well and looks fairly easy to read just remove the headings and the [ ] and you can pretty much just read it straight up with split

[merry aurora]

yeah it's weird for sure, but ill write a parser as you said, i only need one column after all, but i got 4 more files to work with, so it'll help shorten the time

[merry aurora]

Sounds good I'll try that, just wanted to make sure first

thanks guys

[upper solstice]

Hello! I apologize for asking the same question here as in #python-discussion but I just can't figure out why the last element does not get sorted in this selection sort algorithm. When I run my code, the output list is all sorted but the last element stays in it's place regardless whether it's the biggest or not, it's as if it skips it..
def selSort(list_a):
sorted = False
index = 0
while not sorted:
for i in range(index, len(list_a)-1):
if list_a[index] > list_a[i]:
list_a[index], list_a[i] = list_a[i], list_a[index]
index += 1
if index == len(list_a):
sorted = True
return list_a

print(selSort([10,8,9,-1,0]))

[feral hound]

len(list_a)-1 change this to len(list_a)

and see if that works

python range is inclusive for the start but not for the end

!e

for i in range(5):
    print(i)

[halcyon plank]

@feral hound :white_check_mark: Your eval job has completed with return code 0.

001 | 0
002 | 1
003 | 2
004 | 3
005 | 4

[upper solstice]

Yea I had it as len-1 at first with the same output

[feral hound]

no i mean get rid of the -1

[upper solstice]

ohh the range one, gotcha one second

🙂 Thanks Murtada it worked!

[hardy meadow]

can someone help me with this

Human civilisation now has its base on another planet called
Geekland, all credit goes to Geeklon Gusk.
There are N communication towers numbered from 0 to N-1 on the
whole planet which are connected by M wires, each wire connects
two different towers, more formally ith wire connects connections[i]
[O] and connections[i][1] tower. All towers run on 9G technology.
Geeklon Gusk has decided to upgrade the technology of some towers
to 106, the newest and fastest technology ever made. If tower a is
upgraded to 10G, then all towers which are connected to tower a
should also be upgraded. More formally two towers should have
same technology if they are connected.
Geeklon only has enough budget to upgrade atmost X towers. Find
maximum number of towers which can be upgraded

Input:
N = 4, M = 2, X = 3
connections[][] = {{1, 2},
{0, 3}}
Output:
2
Explanation:
Either tower 1 and 2 or tower 3 and 4
can be upgraded.

Input:
N = 4, M = 3, X = 3
connections[][] = {{0, 1},
{1, 2},
{2, 3}}
Output:
0
Explanation:
No tower can be upgraded.

[winged plover]

A good way to deal with this would be linked list or a well in this case it might look like a tree as well so yeah I'll call it a linked tree
So basically the structure would basically looks like tower a : all connected towers
And then further each tower in all connected towers will act as tower a next and so on
So it will look something like :
Case 1 : ```py
{1: (2, ), 2: (,) }
{0: (3, ), 3:(,) }

In case 2 it will look like : ```py
{0: (1, ), 1: (2, ), 2: (3, ), 3: (,)}

So for each structure are you can see that the number of towers connected is numbers of elements in the values of each item of the dictionary ( I used a dictionary to well uk make the linked tree structure)
Now you can easily use number of towers in a link to find out which all groups can be used

[feral hound]

no need for this

you can just loop over connections

and then do a while loop to keep looping for the chain of connections

then return the length of the longest chain <= X

[feral hound]

wait actually this isnt possible you cant have a set of sets

[edgy dune]

trying to take derivative of elastic net function for ML implementation in python

[edgy dune]

and i need to split the range of w when optimizing

the splitting of the range makes no sense to me for this case

[feral hound]

I was wrong about what I said earlier btw I kinda glossed over a few things

I have a brute force solution now but pretty sure there is a better way to solve this since you have N and M

!e

def max_connections(connections, N, M, X, chains):
    for connection in connections:
        for chain in chains:
            if connection[0] in chain:
                chain.add(connection[1])
                break
            elif connection[1] in chain:
                chain.add(connection[0])
                break
        else:
            chains.append({connection[0], connection[1]})
    
    for chain1 in chains:
        for i, chain2 in enumerate(chains):
            if chain1 != chain2:
                for tower in chain2:
                    if tower in chain1:
                        chain1 |= chains.pop(i)
                        break

    longest_possible_chain = 0
    for chain in chains:
        if longest_possible_chain < len(chain) <= X: 
            longest_possible_chain = len(chain)
    
    return longest_possible_chain

connections = {(1, 2), (0, 3)}
print(max_connections(connections, 4, 2, 3, []))

connections = {(0, 1), (1, 2), (2, 3)}
print(max_connections(connections, 4, 2, 3, []))

[halcyon plank]

@feral hound :white_check_mark: Your eval job has completed with return code 0.

001 | 2
002 | 0

[feral hound]

!e

def max_connections2(connections, N, M, X, chains):
    connections = sorted(connections, key=lambda x : (x[0], x[1]) if x[0] < x[1] else ((x[1], x[0])))
    for connection in connections:
        for chain in chains:
            if connection[0] in chain:
                chain.add(connection[1])
                break
            elif connection[1] in chain:
                chain.add(connection[0])
                break
        else:
            chains.append({connection[0], connection[1]})

    longest_possible_chain = 0
    for chain in chains:
        if longest_possible_chain < len(chain) <= X: 
            longest_possible_chain = len(chain)
    
    return longest_possible_chain

connections = {(1, 2), (0, 3)}
print(max_connections2(connections, 4, 2, 3, []))

connections = {(0, 1), (1, 2), (2, 3)}
print(max_connections2(connections, 4, 2, 3, []))

[halcyon plank]

@feral hound :white_check_mark: Your eval job has completed with return code 0.

001 | 2
002 | 0

[feral hound]

another solution

as for which one is better it depends on how many "chains" or connections there are

first one is O(NM + M^2 L ) L being the number of towers in these chains
second one is O(NM + NlogN )

btw M here is the number of chains not the number of connections to be clear

and N is the number of connections not the number of towers

[hardy meadow]

@feral hound thanks dude 👍🏿

[feral hound]

woops just realised I added an unneeded input parameters chains

def max_connections(connections, N, M, X):
    chains = []

change either function to this they will still work

[idle pier]

Hello folks, am currently practicing on my 2d arrays

"""
Are rooks safe in this board?(Should be True)
[
    [1,0,0,0],
    [0,1,0,0],
    [0,0,0,1],
    [0,0,0,0]
]
"""
def rooks_are_safe(chessboard):
    n = len(chessboard)

    for row_i in range(n):
        row_count = 0
        for col_i in range(n):
            row_count += chessboard[row_i][col_i]
        if row_count > 1:
            return False
    for col_i in range(n):
        col_count = 0
        for row_i in range(n):
            col_count += chessboard[row_i][col_i]
        if col_count > 1:
            return False
    return True```
I don't fully understand what `row_count += chessboard[row_i][col_i]` is doing

[fiery cosmos]

it's the same as row_count = row_count + chessboard[row_i][col_i]

you are summing up the numbers in that particular row

makes sense as if the 1s are rooks then any row (or column) with 2 or more and they'll be unsafe

[idle pier]

ok so for the first row [1,0,0,0], row_count is basicall doing this 1+0+0+0

[fiery cosmos]

yeah

[idle pier]

and row_count is greater than 1, then are 2 rooks in that particular row

[fiery cosmos]

2 or more, yeah

[idle pier]

ohhhh ok I get it now, the for col_i in range(n): inside the for row_i in range(n): was getting me confused. we basically need this to move from left to right, 1 -> 0 -> 0-> 0 in that specific row

[fiery cosmos]

yep, in fact the code py for row_i in range(n): row_count = 0 for col_i in range(n): row_count += chessboard[row_i][col_i] if row_count > 1: return False could be simplified to py for row_i in range(n): if sum(chessboard[row_i]) > 1: return False (and even shorter with any)

though the column part is a bit trickier to simplify because of the indexing order

[idle pier]

if wanted to find out whats the biggest sum out of all the three rows, how would I go about it?
Am actually having trouble to implement it, I thought it would be easier

[fiery cosmos]

biggest = max(sum(row) for row in chessboard)

[raven kraken]

Hey guys I find stack, queue and Linkedlist problems really boring. Can you guys suggest me any video that you prefered while learning them?

[feral hound]

idk about videos for these structures but if you want problems where you can use these

linkedlist: https://leetcode.com/problems/find-the-duplicate-number/ you dont actually have to use linkedlists but the idea comes in for the best solution

stack: any DFS problem (assuming you dont use recursion)

queue: any BFS problem

difference between BFS and DFS is literally just that one uses a stack and the other uses a queue
https://www.youtube.com/watch?v=WbzNRTTrX0g
video for search problems with this idea of a queue or stack

@raven kraken

https://cs50.harvard.edu/ai/2020/weeks/0/ link to the full course btw (you can also take it on edx)

[feral hound]

could you post the path that was failing again?

I remember there was something about node B being visited twice

also could you post all your code because I really do think there is a problem somewhere else

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

[feral hound]

@stark bronze

ah could you also include the failing test case so I can run it myself

just make sure it still runs this part properly

[feral hound]

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

[feral hound]

ahh mb thought it was 1 file dm me the zip or post the 3 in different bins

[feral hound]

Aight we found the issue it was because of how we were backtracking

when the path was something like
AEBCGDG

when it backtracks and removes the second G it sets its visited to False even though there is another G still in the path

which messed everything up for the paths afterwards since they could now visit G even though it was already in the path

adding an if statement to check if the node was already in the path solved the issue

[gritty marsh]

Hey folks, could anyone point me to any papers about high-resolution route planning optimizing for distance with time of departure being a parameter?

Basic route optimization optimizes for distance with time of departure being right now

Anyone know of any implementation where the time of departure can vary?

[wide lake]

Can anyone tell me how to receive this as input:

1)size ,2) matrix 1 ,3) matrix 2 if i try to receive the matrix as input thr are empty lists coming

[winged plover]

uh if you are doing this on some site they usually tell how they are going to give the input to your function

[wide lake]

we need to receive them as input they will give in the exact same format for every test cases only the size of the matrix changes m*m but the problem is the empty line between them i get the matrix as [[1,2,3],[1,2,3]] and [[],[],[]]

[winged plover]

then you can use a dummy input instead

something like

size = input()
input()
matrix1r1 = input()
matrix1r2 = input()
matrix1r3 = input()
input()
matrix2r1 = input()
matrix2r2 = input()
matrix2r3 = input()

matrix1 = [list(map(int, i.split(" ")) for i in [matrix1r1, matrix1r2, matrix1r3]]
matrix1 = [list(map(int, i.split(" ")) for i in [matrix2r1, matrix2r2, matrix2r3]]

[wide lake]

thks👍

[raven kraken]

@feral hound Thank you so much

[limber cypress]

hi i need help i need to change in text some letters

[pastel root]

can you be more specific? whats your code?

[brave owl]

yo my prof is making us do time complexity and big o complexity and he's saying nested for loops are (n^2)+n

is this correct?

[gritty marsh]

Depends on the nested loop honestly

But if it's a nested loop that executes some O(1) operation each iteration, then yes it's O(n^2)

[brave owl]

aight ima just do what he says and get the grade

[fervent saddle]

It depends on how many iterations happen too

for x in range(n):
    for y in range(1000):
        # do some O(1) thing```
That’s O(n)

[gritty marsh]

Actually yes, not all nested loops are O(n^2)

[fervent saddle]

Because the inner loop is O(1)

[gritty marsh]

some are O(n*m), some are O(n)

you can't really generalize

[brave owl]

there's no operations in the loop

it just has the loop header

[fervent saddle]

Also O(n^2 + n) is just O(n^2)

[brave owl]

yes but we have to give the time complexity and big o complexity

so basically write out the full thing then simplify it to O(n)

[gritty marsh]

Simplify it by removing lower order terms

[brave owl]

yes but we have to write the unsimplified version too

[fervent saddle]

Wdym

[brave owl]

like if a loop is 5n

we have to write 5n and o(n)

[fervent saddle]

Big-O doesn’t do that

[brave owl]

i understand that

[fervent saddle]

But, I think when people are talking about something that’s O(n), and they want to describe how many times the algorithm looks through the data, they say it’s a “n-pass” algorithm

Like one time, it’s 1-pass. Two times, it’s 2-pass

Etc

[brave owl]

my prof is saying the unsimplified time complexity of a nested loop is n^2 + n

but i dont see where the +n comes from

[shut breach]

that'd be true if one of the loops runs n+1 times

[brave owl]

theres no meat in the loops tho

its just n times each loop

[shut breach]

so?

[fervent saddle]

It sounds like he’s asking you to write out the different time complexities of different sections of code, or something like that

Like

[brave owl]

This is the specific problem

He says T(n) is the actual run time

[fervent saddle]

for x in range(n):
    for y in range(n):
        # do something
for z in range(n):
    # do something```
One part is O(n^2), then the next is O(n), so write O(n^2) + O(n) = O(n^2)

[brave owl]

But there’s only 2 loops

[fervent saddle]

Oh, yeah

“For each loop”

[fervent saddle]

So, it looks like it wants something like this

[brave owl]

Okay

I’m still confused but I’m gonna ask him tomorrow

[shut breach]

ohh

i think it's about the little dots, like they're a stand-in for code

so there's some little dots inside the outer loop above the inner loop

those are executed n times, and the dots inside the inner loop are executed n^2 times

so n^2 + n

[brave owl]

Oh ok

Yeah that makes sense now I didn’t notice the first dots

Thank you sir

[fervent saddle]

Wait

[gritty marsh]

wouldn't that be n * (n - 1)?

[fervent saddle]

This specific problem is O(n^2) + O(n)?

[brave owl]

Yes

[fervent saddle]

I don’t get it

[gritty marsh]

so the "accurate" runtime is n^2 - n not n^2 + n

[brave owl]

Oh yeah I started at 1

I

J

[fervent saddle]

Oh wait, yeah, I get it

Why are they telling you to do this? It seems like it will just confuse people on what Big-O is supposed to say

[brave owl]

no clue

i knew big o before this class so im straight but most of the people in my class are doofuses

[fervent saddle]

It’s not even their fault if they’re confused on it if that’s the exercises they’re being given

[marsh flame]

how would one write a bubble sort that actually sorts unlike mine that i have been working on for 4 hours

[brave owl]

post the code

[gritty marsh]

I'm not sure if it will confuse people; if anything it'll give more clarity on what big-O actually is

[marsh flame]

def bubbleSort():
mylist = []
n = len(mylist)
for i in range(1, n):
for j in range(1, n - i + 1):
if (list[j] < list[j - 1]):
temp = list[j]
list[j] = list[j - 1]
list[j - 1] = temp
return bubbleSort()

[fervent saddle]

But you’re not supposed to write things like O(n^2 + n), it doesn’t make sense to think about it that way

[gritty marsh]

but they aren't

they're delegating it to a separate function T(n)

[brave owl]

just to make your code cleaner you can do var swaps like
list[j], list[j-1] = list[j-1], list[j]

cuts it down to 1 line

[gritty marsh]

Which is what a lot of algorithms books do

[fervent saddle]

Hmm

Ok

[brave owl]

also you dont wanna return the function, you need to return mylist

and you should prob pass a list into the function and set it equal to mylist

[marsh flame]

i have an update, i need to be able print the bubble sort

from random import randint, seed

creates the list using the seed provided by the user

def getList():
seed(theseed)
global mylist
mylist = []
for i in range(1, 10):
mylist.append(randint(1, 100))
return mylist

the bubble sort function

def bubbleSort():
mylist = []
n = len(mylist)
for i in range(1, n):
for j in range(1, n - i + 1):
if (list[j] < list[j - 1]):
list[j], list[j-1] = list[j-1], list[j]
return mylist

input: a list of integers

output: a number of comparisons and swaps

the main part of the program

theseed = input("What do you want to use as the seed? ")

insert your main code below.

getList()
bubbleSort()
print("The list: ", mylist)

[brave owl]

you need to pass the list into the bubblesort

and set a parameter

nvm i see the global variable

its generally not a good programming practice to use globals

for the first loop you also need to start it at the first index and go until the 2nd to last index

rn your code never checks the first index

[gritty marsh]

!code

[halcyon plank]

Here's how to format Python code on Discord:

```py
print('Hello world!')
```

These are backticks, not quotes. Check this out if you can't find the backtick key.

[brave owl]

well ig it does but it's better to do it like this

[marsh flame]

we arent supposed to use global but i could not get it to print out the randomly generated list

[brave owl]

and then for the 2nd loop you start at i+1 and go to the end of the list

for i in range(0,n-1):
  for j in range(i+1, n):

[marsh flame]

im gonna sound stupid but how do i do all this without the global variable and pass the list into the bubble sort

[gritty marsh]

create a parameter that the function takes in

[brave owl]

nah you're good

do you know what parameters are

[gritty marsh]

def bubbleSort(a_list):
  sorted_list = ... a_list ...
  return sorted_list

[brave owl]

a_list can be whatever you want to call it btw

it doesnt have to be the name of what you pass into the functoin

so when you call the function you can do
bubblesort(list)

[marsh flame]

im still doing it wrong i keep getting the error ive been getting all night

bubbleSort(a_list)
NameError: name 'a_list' is not defined

[brave owl]

Put a_list in the parenthesis up there by def

Then pass the getlist function into bubble sort at the bottom

[marsh flame]

I sorry i dont understand what you mean this is what i currently have thought this was what yall said

        seed(theseed)
        mylist = []
        for i in range(1, 10):
            mylist.append(randint(1, 100))
        return mylist
# the bubble sort function
def bubbleSort(a_list):
        a_list = []
        n = len(a_list)
        for i in range(1, n):
                for j in range(1, n - i + 1):
                        if (list[j] < list[j - 1]):
                                list[j], list[j-1]  =  list[j-1], list[j]
                return list
# input: a list of integers
# output: a number of comparisons and swaps

# the main part of the program
theseed = input("What do you want to use as the seed? ")
# insert your main code below.
getList()
bubbleSort(a_list)
print("The list: ", a_list)

[brave owl]

Replace the a list in the 2nd to last line with getlist()

[marsh flame]

bubbleSort(getlist)
NameError: name 'getlist' is not defined

same problem ive been having

wait