algos-and-data-structs

[lilac cradle]

I just did it for fun

I’ll see if i can fix it tomorrow tbh

That peak at magenta is super interesting tbh, you’d think green would be the highest but whatever, pink on top 💪💪💪

[uncut crater]

Anyone here who can help me with my chess engine? I created 2 Help forum posts but no one answered...

[fiery cosmos]

how much math have i to know to get into to cp?

[haughty mountain]

basically just start, you'll be forced to research and learn new stuff as you go

[fiery cosmos]

you consider yourself better than pajenagod?

[haughty mountain]

god no

[fiery cosmos]

:/

[haughty mountain]

I brought pajenegod into the cp world, he surpassed me quickly 😛

[fiery cosmos]

ohhh

yeah i think everything's about talent

[fiery cosmos]

i realized codewars and codingame are a waste of time if you actually want to be good at cp

[haughty mountain]

I think I'm stronger in other areas of programming

[marble mountain]

🤓

[fiery cosmos]

you guys i'm so confused, i am using rstrip() on a string and it is seemingly just failing to work

its working on an element in a list

then i'm trying to append that as an int after stripping away the non numeric char

are the elements of a regular expression findall list somehow different and/or not standard strings?

i cannot possibly see how this is failing to work

[agile sundial]

check your assumptions

[fiery cosmos]

is it possible that the letter is somehow a different underlying type? like different unicode or something?

i'm trying to strip a single letter from a single element in a list with some very rudimentary code and it's just not performing the strip function. printing it right after i try to and its there

oh

they're immutable

need to assign to variable

[regal spoke]

You don't need to rstrip the input to int

int is ok with pre whitespace and trailing whitespace

[jolly mortar]

omg lore

[regal spoke]

Ye. The first competition I ever did was google codejam using matlab after @haughty mountain told me to try it out

Those were the days

[lean walrus]

what does "cp" mean?
competitional programming?

[haughty mountain]

competitive programming yeah

the best shortening, clearly

[slender sandal]

Also stands for codepage

[regal spoke]

Didn't we have to change a channel name in the AC server cause discord marked it as inappropriate?

[fiery cosmos]

anyone here use google cloud?

i'm having issues downloading from google cloud via ssh-in-browser

what channel might this be more appropriate for

[haughty mountain]

we didn't strictly have to, it was related to some discord verification or whatever

after a bit we just decided to name it back and ignore it

[buoyant badger]

class Solution:
    def isValid(self, s: str) -> bool:
        if s[0] == ']' or  s[0] == '}' or  s[0] == ')':
            return False
        stack = []
        for c in s:
            if c == '(' or c == '[' or c == '{':
                stack.append(c)
            if c == ')' and len(stack) != 0 and stack[-1] == '(':
                stack.pop()
            if c == ']' and len(stack) != 0 and stack[-1] == '[':
                stack.pop()
            if c == '}' and len(stack) != 0 and stack[-1] == '{':
                stack.pop()
        if len(stack) == 0:
            return True
        else:
            return False 
            
            ``` Does any see what the issue is I fail case "(])"

[regal spoke]

Just do stack instead of len(stack) != 0

Makes the code a lot nicer to read

[buoyant badger]

if c == ')' and stack and stack[-1] == '(':
stack.pop()

?

sorry I come from java

I did if stack == 0 and all the cases failed

[regal spoke]

Python is a truethy language

[buoyant badger]

does you see a problem with my algo?

[regal spoke]

Empty lists are false

Non-empty lists are true

[regal spoke]

Do not stack

[buoyant badger]

i still get the same error

i pass 89/95

and it still the same case so its not how i have it its an actuall error in my algo

    def isValid(self, s: str) -> bool:
        if s[0] == ']' or  s[0] == '}' or  s[0] == ')':
            return False
        stack = []
        for c in s:
            if c == ')' and len(stack) != 0 and stack[-1] == '(':
                stack.pop()
            if c == ']' and len(stack) != 0 and stack[-1] == '[':
                stack.pop()
            if c == '}' and len(stack) != 0 and stack[-1] == '{':
                stack.pop()
            if c == '(' or c == '[' or c == '{':
                stack.append(c)
        if stack:
            return False
        else:
            return True ```

[regal spoke]

I'm just pointing out that you can make your code a lot nicer to read

[buoyant badger]

Thank you I will do that to save time but I need to remember that its false

[unreal summit]

I have a very dumb question for class hierarchy:
I have the following class

class Object:
  def __init__(self, something):
    self.something = something

  def print_som(self, operation):
     _build_something(operation)

  def _build_something(self, operation):
     pass

What I want to do is for the class in the hierarchy to be able to customize the _build_something function for its own needs. Is this possible with just the super() function?

I still need to call the more general print_some function

[regal spoke]

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for c in s:
            if c in '([{':
                stack.append(c)
            elif c == ')' and stack and stack[-1] == '(':
                stack.pop()
            elif c == ']' and stack and stack[-1] == '[':
                stack.pop()
            elif c == '}' and stack and stack[-1] == '{':
                stack.pop()
            else:
                return False
        return not stack 

Here is a simpler coded version, and I've also fixed your bug

I think your bug was that you sometimes reported an invalid string as valid

For example the string ())

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for c in s:
            if c in '([{':
                stack.append(c)
            elif stack and stack[-1] + c in '()[]{}':
                stack.pop()
            else:
                return False
        return not stack 

Here is an even more compact solution

[serene schooner]

I want to make the tick values bold (the numbers on the left.)
Apparently, plt.bar() doesn't have that and even:

for tick in ax.get_xticklabels():
   x.set_color('red') #this works
   x.set_fontweight('bold') #doesn't work```

what can be a good workaround to fix is this issue?

[buoyant badger]

THank you sorru got busy with life

[buoyant badger]

I also thought about the idea of returning false if the len of the string was not even since you need a pair

[manic kite]

How do I perform an inclusion check on a merkle tree? Like should I have the path for every single leaf in the tree?

[fiery cosmos]

Given two strings containing backspaces (identified by the character ‘#’), check if the two strings are equal.

Input: str1="xy#z", str2="xzz#"
Output: true
Explanation: After applying backspaces the strings become "xz" and "xz" respectively.

Input: str1="xy#z", str2="xyz#"
Output: false
Explanation: After applying backspaces the strings become "xz" and "xy" respectively.

Input: str1="xp#", str2="xyz##"
Output: true
Explanation: After applying backspaces the strings become "x" and "x" respectively.
In "xyz##", the first '#' removes the character 'z' and the second '#' removes the character 'y'.

Is there any better solution than this

def compare(self, str1, str2):
    # TODO: Write your code here
    str1_final = ""
    str2_final = ""
    left = 0
    right = left + 1
    while right <= len(str1):
        if str1[left] != "#":
            str1_final = str1_final + str1[left]
        if right < len(str1) and str1[right] == "#":
            str1_final = str1_final[:-1]
        left += 1
        right += 1
    left = 0
    right = left + 1
    while right <= len(str2):
        if str2[left] != "#":
            str2_final = str2_final + str2[left]
        if right < len(str2) and str2[right] == "#":
            str2_final = str2_final[:-1]
        left += 1
        right += 1
    print(str1_final)
    print(str2_final)
    if str1_final == str2_final:
        return True
    else:
        return False

[jolly mortar]

i think going right to left might be easier to handle

like i feel you could compare character by character, just advancing the indices more when theres a #, all in one pass

[fiery cosmos]

Currently tired but will think about that tomorrow, thanks

[haughty mountain]

and that approach isn't great, you're adding to and slicing the string over and over

easily quadratic behavior

rather than being linear

[fiery cosmos]

For linear behaviour, I need to loop from right to left?

[haughty mountain]

that's a neat option yeah

[haughty mountain]

no

don't work on a string

use a list

[fiery cosmos]

Hmm, so what to do after I convert string to list?

[fiery cosmos]

Wdym?

[haughty mountain]

just append and pop

instead of concatenating and slicing strings

wrt the other approach:
the one downside is that going left to right is O(n) memory

right to left you can do in O(1) memory

[fiery cosmos]

So to convert string to list, then loop through list, if there is #, then just remove last element?

[haughty mountain]

don't convert to list

append/pop from the list as you iterate through the string

[fiery cosmos]

Yeah I understand

Can you explain why exactly it is better to use list rather than add and then remove from string? Is it because adding and removing from the list is O(1) while adding to the string is O(n) and removing one letter from the string is O(n)?

btw what do you think about this solution

Given an array containing 0s, 1s and 2s, sort the array in-place. You should treat numbers of the array as objects, hence, we can’t count 0s, 1s, and 2s to recreate the array.

Input: [2, 2, 0, 1, 2, 0]
Output: [0 0 1 2 2 2 ]

def sort(arr):
    # TODO: Write your code here
    j = 0
    n = len(arr) - 1
    i = 0
    while i <= n:
        if arr[i] == 0:
            arr[i] = arr[j]
            arr[j] = 0
            j = j + 1
        i += 1
    i = j
    while i <= n:
        if arr[i] == 1:
            arr[i] = arr[j]
            arr[j] = 1
            j = j + 1
        i += 1
    return arr

[haughty mountain]

yes

[haughty mountain]

!e

from itertools import zip_longest

def rev_bs(s: str):
  n_skip = 0
  for c in reversed(s):
    if c == '#':
      n_skip += 1
    elif n_skip > 0:
      n_skip -= 1
    else:
      yield c

def solve(s1: str, s2: str):
  return all(
      a == b
      for a, b in zip_longest(rev_bs(s1), rev_bs(s2))
  )

s1 = 'hello wonder####rlf#d'
s2 = 'hell owo rld########o world'

print(list(rev_bs(s1))[::-1])
print(list(rev_bs(s2))[::-1])
print(solve(s1, s2))

[halcyon plank]

@haughty mountain :white_check_mark: Your 3.12 eval job has completed with return code 0.

001 | ['h', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd']
002 | ['h', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd']
003 | True

[haughty mountain]

you indeed can

[past flare]

why does this give me the sin?

def sin(x):
  return (x - (x**3)/6 + (x**5)/120)

[haughty mountain]

it doesn't

it's just approximately correct around x=0

and you're looking for
https://en.wikipedia.org/wiki/Taylor_series

[fiery cosmos]

s = input()
current_letter = s[0]
ans = 1
ans2 = s[0]
current_amount = 1
for i in s:
    if i == current_letter:
        current_amount +=1
        if current_amount > ans:
            ans = current_amount
            ans2 = i

    else:
        current_amount = 1
        current_letter = i
print(ans2, ans)```


```c
Input
HHHHheellllloooo
Output
l 5```

Find out the longest sequence of repeating characters. For the above example, the longest sequence is l, repeating 5 times.


well... I'm just trying to improve my optimization/reduce code skills
i think my solution is a very vague and poor solution, if someone can give me an advice or how would you do it, i would appreciate it

[summer fossil]

Well it's look optimize!

[limber bison]

I'm looking for a way to collect REST API requests response statistics. I'd like to collect them into bins (in addition to the trivial min, max, avg). Is there a way/algorithm that can allow me to start collect the data into bins without knowing up front the distribution of the data? So it changes the bin sizes as data collection progresses? Anything like that exists already?

[obsidian vale]

What is the best EDX course to learn DSA from for leet code

Not just python

[oblique jacinth]

For now im learning DSA using a python app snippet

https://apps.apple.com/app/pycard/id6466706952

[fiery cosmos]

I have created a new sorting algo.
I don't know how to compute its complexity

[past mirage]

Interesting..

[neon dagger]

Hi all, I have one project I do not know how to finish it I am not strong in programming, the project is associated with pdf files to find errors I can not understand how to make it so that it notarized and found errors on the accounting report, I seem to have added in the library modules that are related to this subject are those who have done similar tasks or can now help, can be someone who has developed such projects and they are saved or there are some library modules paid trained, please discount please.

[fiery cosmos]

ouch

[solemn moss]

How to solve it in under n^2?

You have Christmas tree decorations: balls painted in n different colors. For each color i
From 1 to n there are exactly xi balls of this color. You play a game of action. In one
action you can take k balls in pairs of different colors and throw them away. What is the largest
how many actions can you take?

The first line contains two integers n and k: the number of colors and the number of balls thrown out during each action (1 ≤ k ≤ n ≤ 2e5). The second line contains n numbers xi, separated by spaces — the number of balls of the i-th color (1 ≤ xi ≤ 1e9).

4 3
5 8 9 4

8

10 5
1 2 3 4 5 6 239 239 239 239

21

Stupid solve

n, k = map(int, input().split())
A = sorted(map(int, input().split()))
result = 0
while len(A) >= k:
    result += A[0]
    for i in range(len(A) - k, len(A)):
        A[i] -= A[0]

    A.sort()  # Here it's n^2log, for n^2 just need to change it to merge
    while 0 in A:
        A.remove(0)
print(result)

[outer rain]

lmao where did you take this problem from?

(it's from a contest I attended today)

[solemn moss]

)))

[outer rain]

I see

I don't actually know, my teammates solved it

I know that it's binary search over answer, don't know the details

[solemn moss]

well, that's already something

[haughty mountain]

isn't this just greedy?

[outer rain]

greedy is slow

[solemn moss]

mhm

i guess it works

n, k = map(int, input().split())
A = list(map(int, input().split()))

def check(mid):
    have = mid * k
    for x in A:
        have -= min(x, mid)
    return have <= 0

l = 0
r = 10 ** 15
while r - l > 1:
    mid = (l + r) // 2
    if check(mid):
        l = mid
    else:
        r = mid
print(l)

[vocal gorge]

Well, O and o and Ω and ω and Θ are just math notations - they mean stuff like "f(n) is called O(g(n)) if it's true that lim_(n→∞) f(n)/g(n) < ∞".
They are used most commonly to denote asymptotic complexity of algorithms - how quickly the time (or memory) they take scale with the size of the input.
In theory, that's useless because it's only true for infinitely high input sizes - but in practice, quite often when you compare an Θ(n^2) and a Θ(n) algorithm, the latter will be faster even for not-so-big n.

[regal spoke]

k balls in pairs of different colors

k balls in pairs of different colors?
What do you mean by pair here?

[solemn moss]

Just weird wording + google translate

k balls with unique colors / k different balls

[vocal gorge]

Are you familiar with limits?

[haughty mountain]

btw Θ(log(10*15)×n) is the same as Θ(n)

but it's a bit weird to describe the complexity of that code like that

[vocal gorge]

ah, I see. I'm not sure there's an actually-true explanation of how asymptotic complexities work that doesn't involve limits (or stuff that's basically limits in a trenchcoat).
As a not-very-correct-but-mathematically-simpler explanation, think of it this way: suppose you have a function that consists of a number of factors: f(n) = n^3 + 200*n + 1/100000 * exp(n). These terms grow (with increasing n) at different rates - the n^3 term will be less than the 200n term at first, but it grows much faster and soon it'll eclipse it. And this will happen no matter the factors in front of them. And the last term, the exponential one, will eventually eclipse both of the previous terms.
The asymptotic notation Θ is about how fast the function grows - which is determined only by the fastest-growing term in it. For example, this one grows exponentially - for large enough n only the last term will matter. So we can write f(n) is Θ(exp(n)). It's also valid to write f(n) is Θ(1/100000*exp(n)) - but it's exactly the same thing, so the constants are typically dropped.
The O notation is... well, if Θ means "as fast as", kind of like =, then O means "not faster than", like <=. So we can write f(n) is O(exp(n)) and it'll be correct (in fact, it's always true that f(n) is Θ(g(n)) implies f(n) is O(g(n)), just like how a = b implies a <= b). But we could also write f(n) is O(exp(n**2)), because exp(n**2) grows faster than exp(n) and so faster than f. Note that f(n) is not Θ(exp(n**2)) - it grows slower than that.

[haughty mountain]

Θ(log(r - l)×n) would be a better description

[haughty mountain]

there really isn't, unless you want to basically use limits with out explicitly mentioning you use limits

the usual description of big O basically includes the definition of a limit

[vocal gorge]

Not sure I can write a better explanation, unless you have specific questions. One thing you could do is try to learn limits ahead of time (you'll have to do it eventually if you study anything even slightly STEM-related, calculus is everywhere) on something like khanacademy: https://www.khanacademy.org/math/precalculus/x9e81a4f98389efdf:limits-and-continuity, https://www.khanacademy.org/math/ap-calculus-ab

[regal spoke]

@fiery cosmos
Take this as an example:

f(x) = (2 * x^2 + x + 1)/(x + 1)

How would you expect this function to "behave" for large values of x?

Like lets say x = 1000000

Can you guess roughly what f(1000000) is, without using a calculator?

nope

When I see f(x) = (2 * x^2 + x + 1)/(x + 1), then what I see is 2 * x

The reason for this is that when x = 1000000, then 2 * x^2 + x + 1 = 2000000000000 + 1000000 + 1 which is roughtly 2 * x^2

and x + 1 = 1000001, which is roughly x

So f(x) is approximately 2 * x^2 / x = 2 * x when x is large

So the correct answer is that it is very close to 2000000

The big O analysis is a generalization of what we just did

In my example, the function grows as 2 * x

In general what we care about is if a function behaves like c * x or c * x^2 or c * x^3 ... where c is some constant. The exact constant doesn't matter.

This is the what the big O notation is trying to capture

[haughty mountain]

it's not

these notations are all about understanding what parts actually matter when inputs get large

there is no guessing there

[cobalt mirage]

Guys, no matter how many problems I do, I dont seem to be getting at "adhoc" type of problems or thinking in creative ways to solve codeforces/leetcode questions, can anyone give me good advice

[runic tinsel]

I'm not sure it's really a thing, it has to be something you've seen before

you see how a problem is like another problem, that's creativity

but yeah, what if that doesn't happen

i think the fundamental part is generating hypotheses

so you read it, it makes you think of 15 different things it could be, already ordered by similarity

[cobalt mirage]

I guess you're saying just do a lot of variety of problems?

[runic tinsel]

yeah, that has to be important

that you've actually seen "the answer" in another form

you don't generate it from nothing, it's part of your past experience

[cobalt mirage]

I mean you're right, I just have hard time finding those problems that are in different forms, any tips on that

[runic tinsel]

i'm not sure what you mean, you're saying you've been doing the same 4 problems in different forms?

like normal problem sites have a variety

i started with codesignal, no one recommends it though

then codewars

and that's it

so i guess i'm saying it's not "there's 1000 wildly different approaches, so it's impossible to learn them and you have to be creative and come up with an approach from nothing"

it's somewhat like "there's only 15 types of approaches and you will evetually learn them and then you just try them in order"

but i understand that's kinda obvious, and you're saying like, you have trouble solving a problem even being certain which approach is correct

because you still have to stretch and mold it

and that is actually about "searching" through 1000 things

and then there is no way to learn them one by one

[cobalt mirage]

Nah like problems that require different approach that I've never seen b4

[runic tinsel]

yeah, so there's no chance

[cobalt mirage]

Yeah, I won't be doin codesignal nor codewars 😭

doggy platforms

[runic tinsel]

idk the word

there's https://codegolf.stackexchange.com/ technically

[cobalt mirage]

Might just go through a list

[sick tangle]

Can somebody please take a look at my fft implementation and tell me where i messed up? https://paste.pythondiscord.com/7I3Q

[fiery cosmos]

What is wrong with my solution

#class Node:
#  def __init__(self, value, next=None):
#    self.val = value
#    self.next = next

class Solution:
  def findCycleStart(self, head):
    #TODO Write your code here
    visited_nodes = []
    head1 = head
    head2 = head.next
    id1 = 1000
    id2 = 1000
    while head1 is not None and head2.next is not None:
      try:
        id1 = visited_nodes.index(head1)
        id2 = visited_nodes.index(head2)
        return visited_nodes[min(id1, id2)]
      except ValueError:
        if id1 != 1000:
          return visited_nodes[id1]
        elif id2 != 1000:
          return visited_nodes[id2] 
      
      visited_nodes.append(head1)
      visited_nodes.append(head2)
      head1 = head1.next.next
      head2 = head2.next.next 

Input is [1,2,3,6,4,3,2,0,3,4,4]

my output is 2 but expected output is 0

I tried to loop in my notebook and I got 0 in my solution when I try to solve

I tried to solve it by hand and passings are (1, 2), (3, 6), (4, 3), (2, 0), (3, 4), (4, 0)

[haughty mountain]

if this is what I think it is, why are you doing the same thing with head1 and head2?

also doing visited nodes like that is quite inefficient

[fiery cosmos]

If that way of solving that problem is correct, what would be more efficient to check if node was visited?

[fiery cosmos]

I do not think (intuitively) that way is efficient but was wondering whether first I can solve with that approach, so I can try with better one

I do same thing with head1 and head2 in order to visit all nodes, head1 is if I am right at beginning at "index" 0 while head2 is at index 1, next time head1 is at index/position 2, head3 is at position/index three

[haughty mountain]

if you're ok with storing the visited nodes, aren't you just interested when you first see a repeat?

so no need to walk with two nodes

the walking with two nodes made me think you were doing https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_tortoise_and_hare

which walks in parallel but at two different rates

[fiery cosmos]

I tried like this

visited_nodes = []
while head is not None:
  if head in visited_nodes:
    return head
  visited_nodes.append(head)
  head = head.next

but it is not correct solution

[haughty mountain]

you know it's generally helpful to actually link the problem rather than having people have to backtrack to find the problem statement?

[haughty mountain]

!e wdym?

values = [1, 2, 3, 6, 4, 3, 2, 0, 3, 4, 5]
loopback = 7

class Node:
    def __init__(self, value):
        self.value = value
        self.next = next

nodes = [Node(value) for value in values]

for i in range(1, len(values)):
    nodes[i-1].next = nodes[i]
nodes[-1].next = nodes[loopback]

###

def find_loop_node(head):
    visited_nodes = []
    while head is not None:
      if head in visited_nodes:
        return head
      visited_nodes.append(head)
      head = head.next

print(find_loop_node(nodes[0]).value)

[halcyon plank]

@haughty mountain :white_check_mark: Your 3.12 eval job has completed with return code 0.

0

[haughty mountain]

and again, this is inefficient for no reason

from using a list

[fiery cosmos]

Sorry, I assumed you would remember what kind of problem I was dealing with (if I understood what you meant to say (that explain again problem which I was solving))

[haughty mountain]

you didn't link the problem to begin with

[fiery cosmos]

It is from the paid course

[haughty mountain]

so the sample input makes no sense out of context

[haughty mountain]

really? a paid course that just uses a leetcode problem?

https://leetcode.com/problems/linked-list-cycle-ii/

[fiery cosmos]

Yeah I just took that course because that course explains programming patterns in DSA and use problems as means, like there is solution for every problem

[fiery cosmos]

Yeah, that is that problem just I think here is guaranteed that there is cycle

[haughty mountain]

here meaning what?

[fiery cosmos]

I mean in problem from that website where I took course

and this solution doesn't pass

You have same code and same input and you got 0 as result, if I correctly understood your code and example in Discord

(I thought about solving problem with first solution that came to mind regardless of whether it is efficient and then try to solve it it more efficient way)

Also, how so that you use this code find_loop_node(nodes[0]).value instead of find_loop_node(nodes[0]). like is not it a that with .value you get value but you need object because you are using next on object? My assumption is that with .value you get value and that it can't be looped as value is passed rather than object

[haughty mountain]

what?

I just get the value of the node to print it

[fiery cosmos]

my mistake, didn't read it correctly

so you got also 0 as result with same code as me, so I guess it is problem with their solver

[haughty mountain]

works fine on leetcode

good paid course where the problems are just broken

probably less a question for me and more a question for others actually trying to learn stuff 😛

[haughty mountain]

did they really remove the hash impl? that's just annoying

you can use id(head) instead to work around it

or look into a proper algo for cycle detection

[livid holly]

Hi, what are the steps for syncing my postgres database to mongodb? The plan is as soon as the instance of a django model which uses postgres is saved, the same should be replicated on mongodb.

[deep wagon]

Can anyone tell me how to calculate heuristic value in an A* search algorithm

[outer rain]

ask here #databases

[outer rain]

you choose whatever you find the most appropriate. That's why it is a "heuristic". It's basically a way of prioritizing some graph edges over others. If you work on a grid, a manhattan distance probably makes the most sense. On 2d/3d/Nd space euclidian distance will probably make the most sense.

experiment and find the one that works for you

[deep wagon]

Ok thanks

[haughty mountain]

importantly your heuristic must underestimate the actual length

otherwise you might get the wrong result

[keen hearth]

A good way to come up with an admissible heuristic is to relax some of the constraints of the problem. For example, if the problem is to find the shortest path from one point to another in a city, the heuristic could be "what would the shortest path be if I could travel directly to the destination in a straight line?". That heuristic is efficient to calculate, correlated with the true path distance, and never over-estimates the true path distance (in technical language, it's admissible).

Technically, for graph search, the heuristic also needs to be consistent, which is a stronger requirement than admissibility. It essentially means it has to be admissible for each step. Details here: https://en.wikipedia.org/wiki/Consistent_heuristic

But I think heuristics designed though constraint-relaxation tend to be consistent (or possibly they're always consistent).

For A* search, the heuristic has to be hand-crafted for the particular problem you're trying to solve.

What's the problem btw? @deep wagon

[fiery cosmos]

Hey guys i'm trying to do a refresher course about data structure and algo in python. Does anyone know if there is any free refresher course out there?

[deep wagon]

Well i was given a graph and was asked to calculate heuristic using the euclidean formula however there were no x or y-axis values given so that is why I wasn't able to understand the question

But thankfully it is now updated and the values are provided

[keen hearth]

Is it more algorithms you want to refresh, or python?

It might be a bit easier to find separate resources for them. There are a few resources linked in this channel's pinned messages.

[fervent topaz]

Hi,

So this is quite basic I guess, but got tired of bashing my head.
I got a WSL installation on Windows.
And I'm trying to load a xlsx into a dataframe, but the file is located on the Google Drive folder on windows.

Windows Location would be "C:\Users\Jack Reacher\Google Drive\Stock Tracker.xlsx"
Or /mnt/c/users/.......

Either way I keep getting "[Errno 2] No such file or directory:".

Already tried os.path and pathlib etc etc
Can't figure out what I'm doing wrong.

After that.....the xlsx file does have 4 sheets.
Was wondering if some could help

(Note: Couldn't find a better section)

[haughty mountain]

#data-science-and-ml would be a much much better fit

or just #python-discussion and/or #1035199133436354600

[thorn marten]

how to write python code here?

[narrow mica]

Do this
```py
put your python code in here...
```
And note that ` is a backtick character, not a quote ' nor a double quote "

[thorn marten]

class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        hashmap = {}
        for i in range(len(nums)):
            complement = target - nums[i]
            if complement in hashmap:
                return [i, hashmap[complement]]
            hashmap[nums[i]] = i

can someone help me break this down.
from what i understand we are creating a new class called Solutions and then defining a method within it called twoSum. (btw im beginner python). We need self in there because function stuff, and then we are making sure nums can only be a list of integers and target can only be an integer. However, what is the last part on that line for? -> list[int]

chat gpt to the rescue, it specifies the return type as a list of integers

[tropic wyvern]

hello

[distant orchid]

@tropic wyvern hello

[distant orchid]

I'd ask this in a ml channel

@somber snow Well, if you can to convert an image into an excel requires OCR which ueses deep learning

There's probably a bunch of libraries that can do all this for you

[regal spoke]

The : list[int] and -> list[int] are just type hints

They don't actually do anything

The code runs perfectly well without them

They are mostly just there to make the code more readable. nums: list[int] means that nums is expected to be a list of integers, and -> list[int] means the function is expected to return a list of integers

This is equivavlent to the code you sent

class Solution:
    def twoSum(self, nums, target):
        hashmap = {}
        for i in range(len(nums)):
            complement = target - nums[i]
            if complement in hashmap:
                return [i, hashmap[complement]]
            hashmap[nums[i]] = i
        return None

[opal crest]

Hey guys. Anyone know where I can start learning the basics of algorithms. Free (preferably) or paid

[haughty mountain]

well, you can do stuff with them

but you usually don't, and I feel like in most cases it's a bad idea

though in some cases it's executed well, e.g. dataclass

[thorn marten]

class Example:
  def __init__(self):

so def init is usedd to add some attributes to all objects of the example class?

so we can write something like

class Example:
  def __init__(self,x,y):
  self.x = x
  self.y = y

perhaps what i mean to ask what is the purpose of __init__ because ive seen functions/methods work without it

[haughty mountain]

wdym functions/methods working without __init__?

init does whatever initialization is needed

if any

[languid thistle]

people I've found some magic and I don't get it. https://leetcode.com/problems/3sum/solutions/3109452/c-easiest-beginner-friendly-sol-set-two-pointer-approach-o-n-2-logn-time-and-o-n-space/ this guy here - I've verified that it doesn't add identical triplets, but I cannot see where it is checking for this.

I'm using python3, and having just ran the example python3 code there, I'm troubling over it

I can use a set and add (2,1) to the set {(1,2)}. What is stopping the code I've linked there from doing so in the case of an input like [-3, 1, 2, 2] ?

given an input like [-1, 1, 15, 15, 14, 14, -29, -29], what is preventing the solution I linked from adding multiple sets of the same values in different orders?

nvm I got it!

because it sorts the array and the indices maintain the underlying ordinality by not crossing over each other, all solutions can only be put in as a set of items in the same order.

I UNDERSTAND IT

easiest beginner friendly my butt how about a comment about why set is chosen lol

[paper lotus]

Who wants to help me out with a websocket

On something not even gpt4 can figure out

[fallen kelp]

import random
import time

def isSorted(nums):
if len(nums) < 2:
return True
for i in range(len(nums) - 1):
if nums[i] > nums[i + 1]:
return False
return True

def bogosort(nums):
times = 0
while not isSorted(nums):
random.shuffle(nums)
print(nums)
times += 1
return nums, times

if name == "main":
st = time.time()
print(bogosort([1, 3, 5, 4, 2, 7, 8, 9, 6, 10]))
end = time.time()
print()
print(end - st)

:)

my new favorite sort

[glacial compass]

O(1) for sure

[lusty herald]

1. init is used to create objects of the class. Just like constructor. Simply putting have you seen object works without init ? And you can call the method with classname (cls) also, so that's why they must be working. And the reason of the class in first place is to create objects.

[summer fossil]

Any good resources for learning dp?

[thorn marten]

message1 = ['1','2','3','4','5']
sentlist=[]
def print_message(message1):
    while message1:
        sent = message1.pop()
        sentlist.append(sent)
        print(f"we have sent message {sent}")
    
print_message(message1=message1[:])
print(message1)
print(sentlist)

i have this code but the sentlist becomes reverse message 1 list. Is that because .pop() works from back to front?

[pseudo tangle]

Hello guys, is there a way to sort ip addresses in a list in ascending order?
Like if i have list = ['192.168.2.5', '8.8.8.8', '172.16.2.2'] then the sorted order after sorting should be list = [''8.8.8.8', '172.16.2.2', '192.168.2.5']
Is that possible?

[vocal gorge]

That'd be a natural sorting: https://en.wikipedia.org/wiki/Natural_sort_order

there's third-party packages for it.

[pseudo tangle]

Ohh cool! I'll check those packages about natural sorting! Thank you 🙂

[stray fractal]

TIL

[vocal gorge]

To just sort ips (which consist entirely of 4 integers separated by dots), what you could do is turn each into a tuple of 4 integers. That'd also be the same sort order.

[pseudo tangle]

Wow!, didn't think about that, I'll try it

[chrome spruce]

hey guys is there some who can help me to slove this question

The value sum of the encrypted files is the sum of all values of the files where the corresponding values of the files is the sum of all values of the files where the corresponding value in the binary list 1. In s single operation, a group of up to k encrypted files can be decrypted simultaneously. The values of the encrypted files and the binary list are given, along with the maximum number of encrypted files that can be decrypted in a single operation. 
Find the maximum possible value sum of the decrypted files. 
Notes:
 A group ,i.e., subarry is defined as any contiguous segment of the array. 
Example 
Given 
n = 4, k=2, encrypted_file = [7,4,3,5], and binary = [1,0,0,0].
 hence the answer is 15. function 

Description

 def getMaxValueSum(encrypted_file,binary, k):


returns int: the maximum possible value sum
STDIN FUNCTION
----- --------
5 → encrypted_file[] size n = 5
1 → encrypted_file = [1 , 3 , 2 , 3 , 6]
3
2
3
6
5 → binary[] size n = 5
0 → binary = [0 , 0 , 0 , 1 , 0]
0
0
1
0
2 → k = 2
Output 9
STDIN FUNCTION
----- --------
6 → encrypted_file[] size n = 6
1 → encrypted_file = [1 , 3 , 5 , 2 , 5 , 4]
3
5
2
5
4
6 → binary[] size n = 6
1 → binary = [1 , 1 , 0 , 1 , 0 , 0]
1
0
1
0
0
3 → k = 3
Output = 16

[haughty mountain]

let me introduce you to weird ipv4 addresses

these ip-addresses are correctly sorted

1.0.0.0
1.1
16777219
1.0.0.3

[thorn marten]

if you have a class with a method thats not the _ _ init _ _ method, does the creation of a class instance run init in the background on its own?

so does it run init(self) by default ?

[thorn marten]

init function is just to assign attributed to every instance of a class?

[haughty mountain]

this is also not #algos-and-data-structs

[lusty herald]

just read the question yourself once

[fiery cosmos]

Any number will be called a happy number if, after repeatedly replacing it with a number equal to the sum of the square of all of its digits, leads us to the number 1. All other (not-happy) numbers will never reach 1. Instead, they will be stuck in a cycle of numbers that does not include 1.

Given a positive number n, return true if it is a happy number otherwise return false.

Is there any better solution than this

class Solution:
  def get_sum_of_digits(self, num):
    suma = 0
    while num != 0:
      suma = suma + int(num%10) * int(num%10)
      num = int(num/10)
    return suma
  
  def find(self, num):
    if num == 1:
        return True
    if num == 0:
        return False
    sum1 = num
    sum2 = num
    sums = {}
    while 1:
      sum1 = self.get_sum_of_digits(sum1)
      sum2 = self.get_sum_of_digits(self.get_sum_of_digits(sum2))
      if sum1 == 1 or sum2 == 1:
          return True
      if sum1 in sums or sum2 in sums:
          return False
      sums[sum1] = True
      sums[sum2] = True

[chrome spruce]

@lusty herald I read that question by myself and got solution using two pointer method and priority queue but I'm not getting the right expected output for all the test case

[lusty herald]

can you share your code?

[chrome spruce]

yes why not

def getMaxValueSum(encrypted_file, binary, k):
    n = len(encrypted_file)
    max_sum = 0
    z = 0
    for i in range(n):
        if binary[i] == 1:
            max_sum += z
            z = 0
        else:
            z += encrypted_file[i]
            
            if i >= k:
                z -= encrypted_file[i-k]
    max_sum += z
    
    return max_sum

here that's my code

[lusty herald]

    max_sum = 0
    start = 0
    for i in range(0,len(binary)):
        if (curr_sum := sum(encrypted_file[start:i+k])) > max_sum:
            cur_range = (start,i+k)
            max_sum = curr_sum
        start+=1
    
    for i in range(len(binary)):
        if (cur_range[0] >  i < cur_range[1]) and binary[i] :
            max_sum += encrypted_file[i]
    return max_sum
# ans = getMaxValueSum([1 , 3 , 5 , 2 , 5 , 4], [1 , 1 , 0 , 1 , 0 , 0], 3)
ans = getMaxValueSum([1 , 3 , 2 , 3 , 6], [0 , 0 , 0 , 1 , 0], 2)
print(ans)```

[chrome spruce]

@lusty herald hey thanks a lot bro the code is working well for both test case let me run this code see it is working fine with all the test case are not

[chrome spruce]

hey @lusty herald

Test case 3: 
encrypted_file=[3 , 5 , 7 , 1 , 2 , 9] 
binary = [1 , 0 , 1 , 0 , 1 , 0], 
k = 2
Output= 15 (wrong)
Expected Output = 22

getting the wrong output for test case no. 3

[lusty herald]

expected output is 21 or 22 because (3+7+2+9) = 21
as A group ,i.e., subarry is defined as any contiguous segment of the array.
so we prefer file 9 to be decrypted.
Am I missing something?

[chrome spruce]

yes you are right

[lusty herald]

    max_sum = 0
    # ones_sum stores sum of all initial decrypted files i.e 1's in binary
    ones_sum = sum((encrypted_file[i] for i in range(len(binary)) if binary[i]))
    # convert 1's of binary to 0 in enc.._file  i.e [3,5,7,1,2,9] -> [0,5,0,1,0,9]
    encrypted_file = [encrypted_file[i] if binary[i] == 0 else 0 for i in range(len(binary)) ]
    
    for i in range(0,len(encrypted_file)):
        if (curr_sum := sum(encrypted_file[i:i+k])) > max_sum:
            max_sum = curr_sum
    return max_sum + ones_sum


# ans = getMaxValueSum([1 , 3 , 5 , 2 , 5 , 4], [1 , 1 , 0 , 1 , 0 , 0], 3)
# ans = getMaxValueSum([1 , 3 , 2 , 3 , 6], [0 , 0 , 0 , 1 , 0], 2)
ans = getMaxValueSum([3,5,7,1,2,9],  [1,0,1,0,1,0], 2)```

[fiery cosmos]

ik nobody will help me
but ill post it again

the problem is basically cout the minimum replacements for sorting
plus you need in some way print also the index of the values you are exchanging

the numbers in the array are always 1 2 3

i was reading and it says you can do it in wharever order, but it has to be the same amount of replacements

[modern gulch]

What’s the question you’re asking?

[fiery cosmos]

how to?

what to use? what would you use?

btw ive googled but their answer is most based on inputs of differents elements and not duplicated ones

[modern gulch]

Well , you could sort it, then compare unsorted vs sorted, and see how many position changes are needed

So iterate from left to right, and find next value that needs to be swapped

[fiery cosmos]

yeah but how could i get the index that they ask me to

[modern gulch]

!enumerate

[halcyon plank]

The `enumerate` function

Ever find yourself in need of the current iteration number of your for loop? You should use enumerate! Using enumerate, you can turn code that looks like this:

index = 0
for item in my_list:
    print(f"{index}: {item}")
    index += 1

into beautiful, pythonic code:

for index, item in enumerate(my_list):
    print(f"{index}: {item}")

For more information, check out the official docs, or PEP 279.

[fiery cosmos]

6 replacements for the 3rd case would take that

instead of 4

i did thiz

!e

arr = [2, 2, 1, 3, 3, 3, 2, 3, 1]

total = 0
pos = []
for i in range(len(arr)):
    b = arr[i]
    for h in range(i, len(arr)):
        if arr[h] < b:
            arr[i], arr[h] = arr[h], arr[i]
            pos += [(h+1,i+1)]
            total+=1
print(total)
for i in pos:
    print(*i)```

[halcyon plank]

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

001 | 6
002 | 3 1
003 | 9 1
004 | 9 2
005 | 7 4
006 | 9 4
007 | 9 5

[fiery cosmos]

i know is a noobie solution but i just wanted you to know i already did the o(n^2) solution

[modern gulch]

My proposal was to iterate over a sorted list and the unsorted list, and swap if needed

[fiery cosmos]

let me try it rq and tell me if i did it wrong

[haughty mountain]

you have only numbers 1 2 3 right?

discount everything already in the right place, start fixing the ones part by swapping with 1s in the 2s section and 3s section, trying to send stuff to the right place

after this just swap everything wrong among 2s and 3s

[haughty mountain]

!e
proof of concept which doesn't actually bother computing the needed swaps

def f(arr):
  arr = [x-1 for x in arr]
  arr_sort = [0]*arr.count(0) + [1]*arr.count(1) + [2]*arr.count(2)

  count = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
  for a, s in zip(arr, arr_sort):
    count[a][s] += 1

  fixed02 = min(count[0][2], count[2][0])
  fixed01 = min(count[0][1], count[1][0])
  misplaced = count[1][0] + count[2][0] - fixed02 - fixed01
  return max(count[1][2], count[2][1]) + fixed02 + fixed01 + misplaced

print(f([1, 2, 3]))
print(f([3, 3, 2, 2, 1, 1]))
print(f([2, 2, 1, 3, 3, 3, 2, 3, 1]))

[halcyon plank]

@haughty mountain :white_check_mark: Your 3.12 eval job has completed with return code 0.

001 | 0
002 | 2
003 | 4

[haughty mountain]

shouldn't be super hard to extend to compute the swaps too

a bit more book keeping

[regal spoke]

Dont ever use num = int(num/10), instead do num = num // 10

Also int(num%10) is the same as num%10 (if num is an integer)

[cinder heath]

what are some ways i can sort this list in the desired descending order here is a manual approach to the problem and after 12 runs it gets the desired output. At best I have been able to get with 36 using a more automated approach and further attempts to try and get down to 12 like below leads me into some infinite loops lol.

def cycle_list(LIST, POS, LEN, MOVE_R):
    n = len(LIST)
    POS %= n
    sublist = LIST[POS:POS + LEN]
    sublist_2 = sublist[-MOVE_R:] + sublist[:-MOVE_R]
    LIST[POS:POS + LEN] = sublist_2

    return LIST
my_list = [7, 6, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 7, 6, 5, 3, 3, 3, 3, 3, 3, 3, 3, 7, 6, 5, 2, 2, 2, 2, 2, 2, 2, 7, 6, 5, 1, 1, 1, 1, 1, 1, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 5]
my_list = cycle_list(my_list, 3, 12, 3)
my_list = cycle_list(my_list, 6, 20, 3)
my_list = cycle_list(my_list, 9, 27, 3)
my_list = cycle_list(my_list, 12, 48, 18)
my_list = cycle_list(my_list, 1, 3, 1)
my_list = cycle_list(my_list, 2, 5, 1)
my_list = cycle_list(my_list, 3, 7, 1)
my_list = cycle_list(my_list, 5, 2, 1)
my_list = cycle_list(my_list, 6, 3, 1)
my_list = cycle_list(my_list, 7, 4, 1)
my_list = cycle_list(my_list, 4, 14, 6)
my_list = cycle_list(my_list, 14, 10, 6)
print(my_list)

def compute_positions(lst, target):
    start_idx = lst.index(target) if target in lst else -1
    end_idx = len(lst) - lst[::-1].index(target) - 1 if target in lst else -1
    return start_idx, end_idx

def optimize_cycles(lst):
    targets = [7, 6, 5, 4, 3, 2, 1]
    
    desired_positions = {}
    start = 0
    for target in targets:
        count = lst.count(target)
        desired_positions[target] = (start, start + count - 1)
        start += count

    instructions = []
    for target in targets:
        curr_start, curr_end = compute_positions(lst, target)
        des_start, des_end = desired_positions[target]

        while curr_end != des_end:
            incorrect_item = lst[des_end]
            incorrect_pos = lst[curr_start:curr_end+1].index(incorrect_item) + curr_start
            cycle_length = curr_end - incorrect_pos + 1
            lst = cycle_list(lst, incorrect_pos, cycle_length, 1)
            instructions.append(f"Cycle from {incorrect_pos} to {curr_end}, move right by 1")
            curr_start, curr_end = compute_positions(lst, target)
        
        while curr_start != des_start:
            incorrect_item = lst[des_start]
            incorrect_pos_in_segment = lst[curr_start:curr_end+1].index(incorrect_item)
            incorrect_pos = incorrect_pos_in_segment + curr_start
            cycle_length = incorrect_pos_in_segment + 1
            lst = cycle_list(lst, curr_start, cycle_length, 1)
            instructions.append(f"Cycle from {curr_start} to {incorrect_pos}, move right by 1")
            curr_start, curr_end = compute_positions(lst, target)
            
    return lst, instructions

[pseudo tangle]

Thanks again, I was able to solve it using: from natsort import natsorted, and using the function natsorted()

[fiery cosmos]

i need to study what you just said me, thanks fenix

[fiery cosmos]

there is a way to get the indexes you are swappin?

!e

a = 9
arr = [2, 2, 1, 3, 3, 3, 2, 3, 1]
arr_sorted = sorted(arr)
swaps = []

for i in range(len(arr)):
    if arr[i] != arr_sorted[i]:
        for j in range(i + 1, len(arr)):
            if arr[j] == arr_sorted[i] and arr[j] != arr[j - 1]:
                arr[i], arr[j] = arr[j], arr[i]
                swaps.append((i + 1, j + 1))
                break
print(len(swaps))

if arr:
    for i in swaps:
        print(*i)

[halcyon plank]

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

001 | 4
002 | 1 3
003 | 2 9
004 | 4 7
005 | 5 9

[fiery cosmos]

here i implemented the billybobby idea

but i dont know if taking your idea would be possible to get the index

but thanks man, this is actually what i want, i want to expand my logic for this kind of things

[austere crag]

I'm starting a longer-ish term project, trying to create an alogrithm that calculates someone's mood over a month, averaging their weekly and monthly scores out of 10, does anyone have any tips and or how feasible is this project?

[haughty mountain]

oh, it's possible

just requires keeping track of some more data

[haughty mountain]

tl;dr:
in my code I use 0 1 2 instead of 1 2 3 for convenience

fixed02 is the number of swaps you can make with 0s in a 2s place where you can swap in a 2 (fixing both at once

fixed01 is the same but for 0s in the 1s place

you now have some 0s you need to swap in but you can't fix two things at once

now swap all 1s in the 2s place with 2s in the 1s place, which fixes two at once

so instead of counts you could track lists of indices and actually "perform" the swaps

[haughty mountain]

btw that isn't optimal

e.g. [2, 3, 1, 1]

it can be done in 2 swaps

that code reports 3

[full yarrow]

Is there any consensus on where and how to best learn DSA? I'm not looking to become a super pro just yet. I'm simply looking for a fast way to grasp the basics in order to get an entry level job. So far I've just been doing easy leetcode, but I'm thinking if that's a good approach? Maybe I should study the theory first, and then practice solving problems? Should I just go with the pinned MIT course, or has something "better" maybe popped up since then?

[chrome spruce]

Hey guys can you help me with this question. I passed 7 test cases out of 20

The following task can be performed on an array of integers: 
1.Choose a subarray of arr of size 1 at most x times. 
2.Choose a subarray of arr of size 2 at most y times. 
3.Choose a subaray of arr of size 3 at most z times. 
The chosen subarrays should benon-overlapping. The profit is calculated as the sum of the elements in the chosen subarrays. What is the maxximum profit that can be obtained? 
For example, 
consider the array [1,2,3,4,5] for x,y and z each equal 1. for x = 1, choose any one element from the array. Them maximum element is 5, so choose that one. It is the maximum profit under this scenario. for y = 1, choose any subarray of two elements:[1,2],[2,3],[3,4] or [4,5]. 
The last subarray has the highest sum (profit) of 9. for z = 1, the maximum profit is obtained with the subarray [2,3,5] with a sum of 12. if you can choose one of each, maximum profit would be obtained by ignoring x then using y and z to capture [1,2] and [3,4,5] or [1,2,3] and [4,5] for a total profit of 15. 

Function Description: 
def calculateProfit(arr,x,y,z): 
constraints: 
1<=n<=200 
-10^5 <=arr[i] <= 10^5

Sample Input 0
5
3
1
0
0
Sample Output 0
5
Sample Input 1
4
-7
4
0
-7
0
1
0
Sample Output 1
4
Sample Input 2
4
-6
-3
-3
10
0
0
1
Sample Output 2
4

Here is my Solution:-

def calculateProfit(arr, x, y, z):
    n = len(arr)
    max_prr = 0
    if x > 0:
        max_prr = max(max_prr, max(arr))
    if y > 0:
        for i in range(n - 1):
            max_prr = max(max_prr, arr[i] + arr[i+1])
    if z > 0:
        for i in range(n - 2):
            max_prr = max(max_prr, arr[i] + arr[i+1] + arr[i+2])
    if x > 0 and y > 0 and z > 0:
        for i in range(n - 2):
            max_prr = max(max_prr, arr[i] + arr[i+1], arr[i] + arr[i+1] + arr[i+2])

    return max_prr

[scarlet mango]

hi, I'm proficient in algorithm and data structure

I can help you

[chrome spruce]

then please help me

[languid thistle]

lol

[languid thistle]

hmm for x = 1, choose any one element from the array.
"for y = 1, choose any subarray of two elements:[1,2],[2,3],[3,4] or [4,5]. "
so, clearly, they arrays chosen between x / y / z can overlap.

Them maximum element is 5, so choose that one. this implies that the "1.2.3." steps are actually not the task, the task Is 1 + choose max, 2+choose max, 3 +choose max, then rest of algo

number of test cases passed is not helpful. If each test case provides information, they can be useful. # passed tells you nothing useful. You are right to think that code review is the way forward.

i have to go to work :/ luck

[narrow mica]

Is there a constraint on x y z?

It looks to me like you're only choosing 1 subarray, so any testcase with x + y + z > 1 will most likely fail

[chrome spruce]

@narrow mica sorry I don't remember the x,y,z constraint

[chrome spruce]

I have updated my code now please look into

def calculateProfit(arr, x, y, z):
    n = len(arr)
    max_prr = 0
    if x > 0:
        max_prr = max(max_prr, max(arr))
    if y > 0:
        for i in range(n - 1):
            subarr = arr[i:i+2]
            max_prr = max(max_prr, sum(subarr) + (max(arr) if len(subarr) == 1 else 0))
    if z > 0:
        for i in range(n - 2):
            subarr = arr[i:i+3]
            max_prr = max(max_prr, sum(subarr) + (max(arr[i+2:]) if len(subarr) == 1 else (max(arr[i:i+2]) if len(subarr) == 2 else 0)))
    return max_prr

arr = list(map(int, input().split()))
x,y,z = map(int, input().split())

[fiery cosmos]

Hello everyone 🙂
I wrote a script in python to process multiple text tables with pandas, rapidfuzz and joblib for multithreading.
It works but if anyone here knows anything about python, I would need advice and opinions to actually improve my script and make it more efficient.
If anyone is willing to give me their time to help me improve, that would be very nice of them!

[haughty mountain]

they matter

it will dictate the kind of approach that can be used

[haughty mountain]

try a more general chat like #python-discussion, it doesn't seem too related to #algos-and-data-structs

[chrome spruce]

yeah I know but the thing is now I can't look into that question again. the window is close now

[haughty mountain]

I'm pretty sure the actual task is that you can place a bunch of non-overlapping intervals of size 1, 2 and 3, maximize the overall sum

the problem statement doesn't make that awfully clear...

[chrome spruce]

yeah I know and I apologies for that But know I can't access this question again

[haughty mountain]

afaict the cases that the statement talks about are (x, y, z) equal to (1, 0, 0), (0, 1, 0), (0, 0, 1) and then (1, 1, 1)

[chrome spruce]

yes

[scenic socket]

hey i have a question about my max heap

could someone maybe help?

https://paste.pythondiscord.com/3OBA

[lusty herald]

what is query?

[scenic socket]

its in the python help thing

max heap implmentation

[lusty herald]

python help thing?

[scenic socket]

It's all good got it sorted out

[fiery cosmos]

What does it mean that array has cycle if there are no pointers?

Problem Statement
We are given an array containing positive and negative numbers. Suppose the array contains a number ‘M’ at a particular index. Now, if ‘M’ is positive we will move forward ‘M’ indices and if ‘M’ is negative move backwards ‘M’ indices. You should assume that the array is circular which means two things:

If, while moving forward, we reach the end of the array, we will jump to the first element to continue the movement.
If, while moving backward, we reach the beginning of the array, we will jump to the last element to continue the movement.
Write a method to determine if the array has a cycle. The cycle should have more than one element and should follow one direction which means the cycle should not contain both forward and backward movements.

Input: [1, 2, -1, 2, 2]
Output: true
Explanation: The array has a cycle among indices: 0 -> 1 -> 3 -> 0

Input: [2, 2, -1, 2]
Output: true
Explanation: The array has a cycle among indices: 1 -> 3 -> 1

Input: [2, 1, -1, -2]
Output: false
Explanation: The array does not have any cycle.

I think I understood it

Now, if ‘M’ is positive we will move forward ‘M’ indices

For input [1, 2, -1, 2, 2]

First number is 1, we move one index so it is 2, then we move from two two index and that is again 2, then we move again two indexes and we come again to 1

Input: [2, 2, -1, 2]

Cycle is 1 -> 3 -> 1 because from first index we can come to third index and from third index we come to first index

[haughty mountain]

huh, not allowing cycles that mix forward and backward is such an arbitrary choice

[outer rain]

makes sense to me 🤔

that's a fun problem for an interview btw

[haughty mountain]

could have at least given it a fun name

"unicycles in array"

because uni(directional) cycle

[cold vessel]

Hello, I need help with my password protected tool.

I would like the password gui to close and the main gui to open after the successful password entry.

does anyone have a moment ? in PM

[haughty mountain]

not #algos-and-data-structs

[slender ember]

Hello guys
Please recommend portfolio project for python beginner

[patent heart]

Hey all,
Anyone fimiliar with scipy basinhopping?
Struggling to understand something about it

[hidden rock]

Hi everyone!

I'm grinding leetdoe and looking for codemate!
I've current solved 89 problems (https://leetcode.com/mauer9/)
I do 3 hours sessions every day between 6 am UTC to 12 pm UTC (I'm from Kazakhstan)

If you are interested, please text me on telegram (https://t.me/carmonx)

[chrome spruce]

I think I got the solution for that problem

def getMaxValueSum(a, b, k):
  result = 0
  s = 0
  for i in range(len(b)):
    if b[i] == 1:
        s += a[i]
  for i in range(len(b)):
    if b[i] == 1:
        a[i] = 0
  temp = sum(a[:k])
  for i in range(k, len(a)):
    temp -= a[i - k]
    temp += a[i]
    result = max(result, temp)

  return result + s

[cedar ermine]

is there any value of n that would get 0

print(n+2^-(n^n+2)%3)```

im not even sure if its possible

[fiery cosmos]

https://www.facebook.com/codingcompetitions/hacker-cup/2023/round-2

[scenic socket]

i need some help with my max heap could anyoe help

[modest sentinel]

any1 know how to implement the meissel-lehmer algorithm?

[haughty mountain]

mission accomplished, got shirt

[fiery cosmos]

congrats my brother!!!

@regal spoke how did you fail the A

[regal spoke]

I was the only one who solved everything but A1

[fiery cosmos]

XDD

[regal spoke]

Had a stupid bug on A1 which I only realized when I was about to submit to A2

[fiery cosmos]

i'm following some python exactly as it's written and it's erroring out, any ideas? i'm using pandas, plotly express.

[regal spoke]

Problems ordered by difficulty: A||2|| < D < B < C || < A1||

[fiery cosmos]

i'm following this:
https://plotly.com/python/line-and-scatter/

and trying to build visuals, and its throwing a fuss when it gets to color

literally following it exactly

might my install of the package be corrupted somehow?

the weird thing is that it works otherwise..

[modern gulch]

Throwing a ‘fuss’ doesn’t really tell us anything. Could you share code and error?

[fiery cosmos]

Yeah for sure, tomorrow I’ll share the exact code and error. So weird

[chrome spruce]

I need some help with hashmap question

Sorting Songs

As part of enhancing a music streaming platform's user exprerice, implement a feature that ranks songs by their popularity. Given n users and m songs, each user i has a perference list, pref[i], which is permutation of numbers 0 and m-1, indicating the user's perference for a song. if a < b, the user perfers song perf[i][a] over song perf[i][b].

To rank the songs, use the following approach. Song x is said to beat song y if x is preferred over y by more than half of the users or if exactly half of the users prefer x over y, and x has a smaller id. Song x is considered more popular than song y if x beats more songs than y. If x and y beat the same number of songs, select the song with lower id.

Example 
Suppose n = 3, m = 3 perf = [[0,1,2],[0,2,1],[1,2,0]]
user            song Perference 
0               Song 0 > Song 1 > Song 2
1               Song 0 > Song 2 > Song 1
2               Song 1 > Song 2 > Song 0

Comparisons:
Song Pair           users who prefer
Song 0 > Song 1     0,1 
Song 0 > Song 2     0,1
Song 1 > Song 2     0,2
It establish that Song 0 > Song 1 > Song 2. Hence the answer is [0,1,2]

Constraints
1 <=n<=400
1 <=m<=400
song_preferencers[i] is permutation of numbers 0,1,...m-1

n = 5;
m = 4;
songPreferences = [
  [0, 1, 3, 2],
  [0, 2, 3, 1],
  [1, 0, 3, 2],
  [2, 1, 0, 3],
  [0, 3, 1, 2],
];

for this test case I'm getting [0,1,2,3] which is wrong the output should be [0,1,3,2]
because song0 [1,2,3] > song1 [2,3] > song3[2] > song2[-]

song        beat songs(s)           number of songs beaten
0           1,2,3                   3
1           2,3                     2
2           -                       0
3           2                       1

Here is my code

from typing import List

def rank_songs(n: int, m: int, s: List[List[int]]) -> List[int]:
    b = {i: 0 for i in range(m)}
    for i in range(m):
        for j in range(i + 1, m):
            count = 0
            for k in range(n):
                if s[k].index(i) < s[k].index(j):
                    count += 1
            if count > n // 2:
                b[i] += 1
            elif count == n // 2 and i < j:
                b[i] += 1
            else:
                b[j] += 1
    return sorted(range(m), key=lambda x: (-b[x], x))

[fiery cosmos]

fig = pe.scatter(tokpos_df, x='tokens', y='positions', title='Tokenization Visualization', color='blue')

ValueError: Value of 'color' is not the name of a column in 'data_frame'. Expected one of ['tokens', 'positions'] but received: blue

https://plotly.com/python/line-and-scatter/

following the package documentation exactly

tried moving it before the title var declaration

i think it's in the way i'm building my pandas df?

i have two lists, i make a dictionary with a name for the list as a key and the list as the value, then i call pds.DataFrame() on that dictionary

i think that must be it bc i'm getting other weird attribute errors

like: 'str' object has no attribute 'copy'

[vocal gorge]

color='blue' tries coloring each point according to the values of the column tokpos_df["blue"], which you don't have.

(much like how, in the documentation, they do color="species" to color the points by species)

[fiery cosmos]

oh wow ok

thank you!

@vocal gorge do you happen to know how plotly libraries can be shared so that the interactive aspect can be viewed by others? the way fig.show() works simply opens it up in a web browser locally with some ip for the address

[vocal gorge]

I've never used plotly but when I look at https://plotly.com/python/getting-started/ one of the first examples I see involves fig.write_html which seems like the right way.

[fiery cosmos]

ok ty

[modern gulch]

In a notebook, fig.show() or display(fig) should work

But there are display options: there are different renderers. In environments I use, the appropriate renderer is selected so that the figures shows inline the cell. See the section here about setting the default renderer: https://plotly.com/python/renderers/

[foggy fiber]

Hi i've been struggling with this question for sometime, i found it from a test of my class from a few years ago while i was studying. Could someone help me solve it?
Currently in a national park, the park ranger team is conducting a simulation of a catastrophe with multiple intentionally caused fire outbreaks. The park rangers are dispersed throughout the park and are in constant contact via radio. Thanks to a rapid response, the fire outbreaks are small enough for a single park ranger to extinguish on their own. The park can be represented as a series of different adjacent zones. There are N park rangers, with park ranger i located in zone gi. In the simulation, there are M fire outbreaks, with outbreak i located in zone fi. Each minute, each park ranger can move independently. A park ranger in zone gi can move to zone gi - 1, zone gi + 1, or stay in the same zone. There can be multiple park rangers in the same zone. The fires can be extinguished in a negligible amount of time since it's a simulation. The team wants to know the minimum number of minutes in which the entire team can extinguish all the fire outbreaks to evaluate their performance.

Input:
The first line contains two integers N and M (1 ≤ N, M ≤ 105).
The second line contains the positions of the park rangers gi (1 ≤ gi ≤ 1010, gi < gi+1), and the third line contains the positions of the fire outbreaks fi (1 ≤ fi ≤ 1010, fi < fi+1).

Output:
The output should be an integer, representing the minimum number of minutes required to extinguish all the fire outbreaks.

Expected Time:
The solution is expected to run in a time less than or equal to 2 seconds for any input instance according to the given constraints.

Expected Complexity:
The expected complexity of the solution is O((N + M) · log(max(gi, fi))).

Hint:
Use a greedy solution.

Example Input 1:
2 2
3 4
1 10
Example Output 1:
6
Example Input
3 4
1 10 20
1 8 12 17
Example Output 2
6

[haughty mountain]

soundns like a shortest path problem

so Dijkstra

(the statement is somewhat vague though)

[regal spoke]

I'm also confused about the statement

You can toss either 1, 2 or 4 coins at a time?

Is the idea that you fill up the basket with single tosses for a while, then do a 4 toss, and then a two toss?

[languid thistle]

confused about a problem - find the nth element from the end of al linked list - example. ```
slow = head
fast = head
for _ in range(n):
fast = fast.next
if not fast:
return head.next()

why is this returning head.next() If not fast? I think that would return the second item in the list for any n >= the length of the list, which doesn't make any sense to me.

logging the head of their input -> ListNode{val: 1, next: ListNode{val: 2, next: ListNode{val: 3, next: ListNode{val: 4, next: ListNode{val: 5, next: None}}}}}. So it's not some non-recursive implementation wherein the head is different from any other node.

[haughty mountain]

I think yeah

my read is that it's something like

coins   1 1 1 4 2 2 ...
lilies 0 1 2 3 3 6 9 ...

4 coins stores the current amount, 2 adds that amount

[regal spoke]

Ok but in that case it is just a relatively standard bfs/dijkstra problem

I don't see any greedy approach

[cunning bison]

What is the standard way to add to a linked list?

[shadow oyster]

I created a list that contains all possible 5 card hands using deck that has 40 cards using the following code:

hand_samples_test = list(combinations(deck, 5))

This creates a list of 658008 hands and it takes less than 3 seconds.

Now, I am iterating each card in each hand so I am iterating 658008*5 times because there are 5 cards in each hand.
When a card in a hand meets a condition, I remove the hand from the original list (hand_samples_test) and add it to a new list. However, this is taking a long time to compute (15 minutes and has only iterated 240000 hands)

def pop_bad_hands(hand_samples):
bad_hands = []
for hand in hand_samples:
for card in hand:
if card.type == 'bad':
hand_samples.remove(hand)
bad_hands(hand)
break
return bad_hands

Is it normal for it to take such a long time?

EDIT: Okay so it seems that the remove function is super slow! So I'll try a different approach.

[dapper ember]

Use threading or multiprocessing to achieve faster results

Which will run the same program in 4 kind of windows, allowing you to gain up to 4x speed

Also, based on your CPU/Computer hardware Multiprocessing will process things faster

Or slower

[outer rain]

remove is slow because you iterate over the entire list until you find the correct card, remove it, and shift the rest of the list by one. It is said that function like this works in O(n) time, or that time grows linearly with the size of the input. If you want to make this faster, you need to get rid of this O(n) procedure. The most obvious way to me, is to write a two-pass algorithm. The first pass creates an array of booleans: whether the hand is bad or not for each hand. The second pass filters out bad hands. This will be order of magnitudes faster. Only after that consider other non-algorithmic optimizations.

actually, why bother about two passes when language can do this for you

!timeit

a = list(range(100_000)) # imagine that it's a million of "hands"

def is_not_bad(hand):
    # placeholder implementation
    return hand % 3 != 1

a = list(filter(is_not_bad, a))

[halcyon plank]

@outer rain :white_check_mark: Your 3.12 eval job has completed with return code 0.

10 loops, best of 5: 24.9 msec per loop

[haughty mountain]

why is the remove needed anyway?

you intentionally want to modify the argument?

[outer rain]

considering that the function is called pop_..., yes

(but the question is valid)

[haughty mountain]

ah

[outer rain]

I forgot to return the bad ones here... well...

[haughty mountain]

but yeah, even then I wouldn't do it in the loop

"subtract" the bad_hands afterwards

[outer rain]

Generally, no one except #esoteric-python people should modify the structure one is iterating on, because god knows how that works in the inside. Maybe it will skip elements all of the sudden.

oh god it does

!e

a = list(range(10))
for x in a: a.remove(x)
print(a)

[haughty mountain]

ask @regal spoke about his darling bfs

[halcyon plank]

@outer rain :white_check_mark: Your 3.12 eval job has completed with return code 0.

[1, 3, 5, 7, 9]

[outer rain]

I saw that

I hate it with passion

<sorry rust rant>
This is also why I love rust so much. When you do

for x in &a { ... }

you can't modify a because you just borrowed it, and borrow checker prevents you from touching a in any way, other than read-only access to it.
</sorry rust rant>

[regal spoke]

If you ever see people do bfs by appening to a live list, then you know who started the trend

    bfs = [0]
    depth = [0] * n
    for node in bfs:
        for child in graph[node]:
            graph[child].remove(node)
            bfs.append(child)
            depth[child] = depth[node] + 1

❤️

[haughty mountain]

doing this with C++ vector would be totally UB

deque...might work

[outer rain]

  let q = VecDeque::new();
  let dist = vec![inf; n];
  q.push_back(0);
  while let Some(v) = q.pop_front() {
    for u in graph[v] {
      (dist[v] + 1).if_lt_patch_and(&mut dist[u], |_| q.push_back(v));
    }
  }

also

the fuck is graph[child].remove(node)???????

this is so bad

[regal spoke]

That part isn't weird? It just removes the edge from the child to its parent from graph

I only do it if I want to root a tree

[outer rain]

you can check the depths...

[regal spoke]

Just so you know, the bfs I posted was specifically for a tree

A bfs for a general graph cant use graph[child].remove(node)

The cool thing about using graph[child].remove(node) is that it makes it so I don't need to store any additional information about which nodes I've visited

[outer rain]

can't it be O(n^2)?

[regal spoke]

I should write an FAQ for this question

I get it a lot

The answer is no

It is O(n)

[outer rain]

no you should reconsider your implementation instead

[regal spoke]

Each node has at most one parent. So graph[node].remove will be called at most once per node

So it is linear

[outer rain]

https://tenor.com/view/disappointed-disappointed-fan-seriously-what-are-you-doing-judging-you-gif-17485289

how many unsuccessful attempts of hacking have you encountered with this... functioning implementation?

[regal spoke]

Let me try to sell you on this.

Suppose you start some solution of a tree problem with this

bfs = [0]
for node in bfs:
  for child in graph[node]:
    graph[child].remove(node)
    bfs.append(child)

Then you can in a 3-liner do tons of operations on the tree, for example

subtree_size = [0] * n
for node in bfs[::-1]:
  subtree_size[node] = 1 + sum(subtree_size[child] for child in graph[node])

or

depth = [0] * n
for node in bfs:
  for child in graph[node]:
    depth[child] = 1 + depth[node]

or

height = [0] * n
for node in bfs[::-1]:
  if graph[node]:
    height[node] = 1 + max(depth[child] for child in graph[node])

Most algorithms on trees become super nice and easy using this

[outer rain]

this is what small stack does to good people...

[regal spoke]

This runs really fast too

[outer rain]

... in python

[shadow oyster]

Thank you so much, I did not know that method existed. Run time went from... (probably 45 minutes?) to less than 5 sec.

[outer rain]

... and that's why big O matters!

[opaque apex]

Btw there is a neat little trick to do this if you dont care about the order of the elements, you swap the last element in your list with the one you want to remove, and then you remove the last element ( which is now the element you want to remove)

[naive oak]

how is the tree stored?

[regal spoke]

Originally graph is an adjecency list, meaning it is a list of lists, where graph[node] is a list containing all the neighbours of node.

[naive oak]

ah ok

[regal spoke]

The graph[child].remove(node) removes all of the edges between child and parent in the graph. So afterwars graph[node] is a list containing all of the children of node, with the root placed at node=0 since bfs = [0].

[naive oak]

ahh i see

that's pretty neat

do you have a variant for general graphs, not just for trees?

[regal spoke]

For general graphs I would do this

bfs = [0]
P = [-1] * n
P[0] = 0
for u in bfs:
  for v in graph[u]:
    if P[v] == -1:
      P[v] = u
      bfs.append(v)

Then if you want to compute something like shortest distance from 0 to any other node u, then you can do

dist = [0] * n
for u in bfs[1:]:
  dist[u] = dist[P[u]] + 1

[naive oak]

did you mean for v in graph[u] here?

[regal spoke]

oh ye ops

ok fixed it

[naive oak]

that's neat

never thought about decoupling the bfs logic with the computation logic like that before

[regal spoke]

Ye it is pretty sweet. In Python I really prefer doing bfs instead of dfs because of this.

This is a bit ironic, since in C++ it usually goes the other way around. People prefer dfs over bfs.

[haughty mountain]

as soon as you go iterative the choice becomes basically whatever you prefer at that moment

and switching is trivial

(your thing is very bfs though)

[naive oak]

i still struggle to do iterative dfs

well, converting recursive dfs into iterative dfs

if it's just iterative bfs vs iterative dfs that's just a ds change

[agile sundial]

iterative dfs is 🤮

[regal spoke]

What I usually resort to is to do this

dfs = [0]
found = [False] * n
while dfs:
  u = dfs.pop()
  if u < 0:
    u = ~u
    # We are back at node u

    # Add code here

  elif not found[u]:
    # This is the first time we've reached node u
    found[u] = True
  
    # Add code here
  
    dfs.append(~u)
    dfs += graph[u]

Is it nice? No

But is it good enough to be used in 80 % of cases? Yes

If I really need recursion but I'm forced to do it iteratively, then I use my funky bootstrap solution

!e

from types import GeneratorType

def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        to = f(*args, **kwargs)
        while True:
            if type(to) is GeneratorType:
                stack.append(to)
                to = next(to)
            else:
                stack.pop()
                if not stack:
                    break
                to = stack[-1].send(to)
        return to

    return wrappedfunc

@bootstrap
def fib(n):
  if n <= 2:
    yield 1
  else:
    yield (yield fib(n - 1)) + (yield fib(n - 2))

print(fib(5))

[halcyon plank]

@regal spoke :white_check_mark: Your 3.12 eval job has completed with return code 0.

5

[final chasm]

it's not a python problem but it's a math problem

i have homework due tomorrow i just dont know what to do

idk if i can ask here

[snow anvil]

dont ask to ask just ask

[shadow oyster]

I am making a function to find out if all of the items in list_two are found in list_one.

list_one = [a,a,b,d]
list_two = [a, b]

def list_contains_list(list_one, list_two):
    boolean_list = []
    for item in list_one:
        for item_aux in list_two:
            if item == item_aux:
                boolean_list.append(1)
                list_two.pop(item_aux)
                if len(boolean_list) == len(list_two):
                  # Returns true if all of the items in list_two were found in list_one
                  return True
                # Skip to next item in list_one
                break
    # If all of the items from list_two are not found in list_one return False
    return False

However, if list_two was a larger list (over 100k items) this would take a long time since pop() and remove() are very slow. Should I consider turning the lists into a dictionary to improve the performance or is there a different way around this?

[outer rain]

yes, you should consider it

and do everything to remove the nested loops

if your lists are over 100k items, the inner loop can do over 10 billion operations worst case

!timeit

list_one = [x for x in range(10 ** 5) if x % 2 == 0]
list_two = [x for x in range(10 ** 5) if x % 6 == 0]
set_one = set(list_one)
print(all(map(lambda x: x in set_one, list_two)))

[halcyon plank]

@outer rain :white_check_mark: Your 3.12 timeit job has completed with return code 0.

10 loops, best of 5: 21.3 msec per loop

[outer rain]

(literally first try)

[outer rain]

also this seems bugged to me

you only push to bolean_list and never clean it

this should not be a list at all, tbf

just a counter, since you only push 1s to it

[haughty mountain]

return Counter(list_two) <= Counter(list_one)

[outer rain]

this is actually a quite nice operator overload 🤔

[haughty mountain]

it is

[shadow oyster]

Thank you guys. I think I will take the dictionary approach. Sometimes lists will contain items that appear once or twice and that's fine. I want to count those too.

[outer rain]

I would suggest following this approach then, it handles this too

[slender sandal]

If the lists contain only hashable items, which I suppose is true because your plan is to turn the lists into dictionaries whose keys must be hashable objects, then you should consider using set methods. set objects have cool methods that can do what you described:

def list_contains_list(list_one, list_two):
    return set(list_one).issuperset(list_two)

[smoky raptor]

does anybody speak Portuguese here? I am building a project and need some help, please

[regal spoke]

That code looks buggy to me. Why do you have list_two.pop(item_aux)?

That looks extremely weird

You are popping index item_aux out of list_two

[shadow oyster]

Thank you guys for your feedback about my code.

1. Removed the nested loops.
2. Added dictionaries as counters instead of a list.
3. The function no longer needs pop/remove.

def hand_contains_cards(hand, cards):
    counter_hand = {}
    counter_cards = {}
    for card in hand:
        counter_hand[card.name] = counter_hand.get(card.name, 0) + 1
    for card in cards:
        counter_cards[card.name] = counter_cards.get(card.name, 0) + 1

    for card_name in counter_cards:
        if counter_cards[card_name] != counter_hand.get(card_name, 0):
            return False
    return True

def hand_contains_cards_v2(hand, cards):
    hand_list = [card.name for card in hand]
    cards_list = [card.name for card in cards]
    return Counter(cards_list) <= Counter(hand_list)

[shadow oyster]

I made two versions that should output the same result since I am not 100% sure about how Counter(list_a)<=Counter(list_b) works.

From what I've found:

Counters support rich comparison operators for equality, subset, and superset relationships: ==, !=, <, <=, >, >=. All of those tests treat missing elements as having zero counts so that Counter(a=1) == Counter(a=1, b=0) returns true. Equality and inclusion compare corresponding counts

Does this mean in counter_a<=counter_b, counter_a (keys and values) are included in counter_b?

edit: According to the tests I've run, yes. The value for each key in counter_a needs to be less than or equal to the value for the same key in counter_b.

[keen hearth]

It is the same as: ```py
all(counter_a[key] <= counter_b[key] for key in counter_a)

A counter is like a defaultdict(lambda: 0), but with some nice convenience methods and operators.

You can also think of it like a multiset: https://en.wikipedia.org/wiki/Multiset

[full sonnet]

Any idea on how to speed up the code below ? Ideally I'd like to change the split_digits() to be able to return digits in normal order, right now it returns (4,3,2,1) for n=1234 and I have to invert the output using [::-1] .

def split_digits(n:int, base=10):
    """Generator to split number into digits

    Parameters:
    --------------
    n(int):                             integer to split into digits
    base(int)=10                        base to split integer to

    Return Values:
    --------------
    function:                           function to split ints into digits

    #! the digits this returns are in descending order !
    """
    if n == 0:
        yield 0
    while n:
        n, d = divmod(n, base)
        yield d

#main part of code, this is re-run N times:
        digit_tuple = tuple(split_digits(i))[::-1]

[haughty mountain]

a stupid but probably quite fast way in python is going via string

!e

n = 1234
print([int(d) for d in str(n)])

[halcyon plank]

@haughty mountain :white_check_mark: Your 3.12 eval job has completed with return code 0.

[1, 2, 3, 4]

[full sonnet]

mh, is that faster than the generator ?

[haughty mountain]

in python, probably

in a lower level language going via a string is very silly

but in python you generally win out by avoiding doing work in python code itself

[full sonnet]

mhm, just tested the string approach and it seems to be same - worse, either they are actually similar bad or that piece of code is actually not what's causing problems for me

[haughty mountain]

these are kinda as good as you get

if you have issues they will be elsewhere

like calling this cheap thing way too much

[full sonnet]

mhm, I should be pretty optimized in how often I call this code but this should be by far the most inefficient code I have, tryna 10x my speed but it's getting difficult after already having increased my speed 30x

[chrome spruce]

can somebody help me with my coding question.

The following task can be performed on an array of integers: 
1.Choose a subarray of arr of size 1 at most x times. 
2.Choose a subarray of arr of size 2 at most y times. 
3.Choose a subaray of arr of size 3 at most z times. 
The chosen subarrays should benon-overlapping. The profit is calculated as the sum of the elements in the chosen subarrays. What is the maxximum profit that can be obtained? 
For example, 
consider the array [1,2,3,4,5] for x,y and z each equal 1. 
for x = 1, choose any one element from the array. Them maximum element is 5, so choose that one. It is the maximum profit under this scenario. 
for y = 1, choose any subarray of two elements:[1,2],[2,3],[3,4] or [4,5]. The last subarray has the highest sum (profit) of 9. 
for z = 1, the maximum profit is obtained with the subarray [3,4,5] with a sum of 12. 

if you can choose one of each, maximum profit would be obtained by ignoring x then using y and z to capture [1,2] and [3,4,5] or [1,2,3] and [4,5] for a total profit of 15. 

```py
Function Description: 
def calculateProfit(arr,x,y,z): 
constraints: 
1<=n<=200 
-10^5 <=arr[i] <= 10^5
0 <=x,y,z <= 20 

Sample Input 1
n = 4
arr = [-7, 4, 0, -7]
x = 0
y = 1
z = 0
Sample Output 1
4
Sample Input 2
n = 4
arr = [-6, -3, -3, 10]
x = 0
y = 0
z = 1
Sample Output 2
4

here is my code but my problem is failing for edge cases

def calculateProfit(arr, x, y, z):
    n = len(arr)
    result = 0
    def profit(size):
        nonlocal result
        curr = 0
        start = 0
        end = 0
        while end < n:
            if end - start < size:
                curr += arr[end]
                end += 1
            else:
                curr -= arr[start]
                start += 1
            if end - start == size:
                result = max(result, curr)
    for _ in range(x):
        profit(1)
    for _ in range(y):
        profit(2)
    for _ in range(z):
        profit(3)
    return result

my code is not working for edge cases

[regal spoke]

If you want something faster, you could try

!e

n = 1234
ascii0 = b'0'[0]
print([d-ascii0 for d in b'%d'%n])

[halcyon plank]

@regal spoke :white_check_mark: Your 3.12 eval job has completed with return code 0.

[1, 2, 3, 4]

[full sonnet]

wow, gonna test that, what exactly does the code do ?

[regal spoke]

It just uses ascii

!e

print(b'0'[0])

[halcyon plank]

@regal spoke :white_check_mark: Your 3.12 eval job has completed with return code 0.

48

[regal spoke]

Is this faster than calling int? Probably yes
Is this a lot faster than calling int? Probably no

[full sonnet]

from the few tests I've just done it's quite a lot quicker but I got to admit I still don't quite get it. So it converts int into a string and then uses acii to get it back to int ??

[lean walrus]

it converts int to bytes object, which return ints when it is iterated over

[full sonnet]

ah okay, and where does the ascii part come into play ?

[lean walrus]

'%d'%x

[haughty mountain]

when you iterate over the bytes object you get an int: the ascii value of the character

e.g. '2' is 50

[full sonnet]

mh, and that is converted back to 2 with the ascii0 thing that is just set to the first 'number' in the ascii table ?

[lean walrus]

!e print(*b'1234')

[halcyon plank]

@lean walrus :white_check_mark: Your 3.12 eval job has completed with return code 0.

49 50 51 52

[full sonnet]

hm and the ascii0 thing turns it back to normal ints ?

[fiery cosmos]

who can help me with python?

[full sonnet]

depends on the type of problem

[lean walrus]

isnt 49 a normal int?
ascii0 is a normal int too
x-ascii0 just subtracts two values

[full sonnet]

mhm, okay, makes sense I guess

[fiery cosmos]

how do i start any python project like what do i start with?

[swift breach]

that only works for the base10 case though, considering that's a parameter there [in your original], do you need something faster for the general case?

[full sonnet]

I guess start with what problem you want to solve ?

[full sonnet]

nope, base10 is fine for my code, just kept it in there as it didn't cost much performance

[lean walrus]

you can also do this: ```py
list(map(int,str(x)))
list(map(ascii0.rsub,'%d'%x))

[fiery cosmos]

i just wanted to create a simple script that helps with roblox

so how do i start

[lean walrus]

!rule tos

[halcyon plank]

Rules

5. Do not provide or request help on projects that may violate terms of service, or that may be deemed inappropriate, malicious, or illegal.

[fiery cosmos]

oh my bad

[fiery cosmos]

bro for creating games

not for executors

[shadow oyster]

Not a question, it's just, it's nice I was able to improve the code thanks to Counter. Thank you guys.

# This function returns True if the hand contains cards in the same count

def cards_subset_of_hand_same_count(hand, cards):
    counter_hand = {}
    counter_cards = {}
    for card in hand:
        counter_hand[card.name] = counter_hand.get(card.name, 0) + 1
    for card in cards:
        counter_cards[card.name] = counter_cards.get(card.name, 0) + 1

    for card in counter_cards:
        if counter_cards[card] != counter_hand.get(card, 0):
            return False
    return True

def cards_subset_of_hand_same_count(hand, cards):
    counter_hand = Counter([card.name for card in hand])
    counter_cards = Counter([card.name for card in cards])

    intersection = counter_hand & counter_cards
    
    if not intersection==counter_cards:
        return False
    
    hand_minus_cards = counter_hand-counter_cards

    return len(intersection & hand_minus_cards) == 0

[scenic socket]

hey i need some help implmenting a resizeable hashtablle

anyone have any vids or sites that could help me?

[fiery cosmos]

Can someone help me as to why the time exceeds on my algo? Someones answer - which is really similar to mine - works for some reason? Question page: https://leetcode.com/problems/container-with-most-water/description/

hey, i need help when i trying to open a python file it open and closes automatically

[fiery cosmos]

wrong channel

[haughty mountain]

that len call seems quite expensive

why do you do the expensive slice and then do len on the slice?

the length is r - l assuming you're not slicing weirdly out of bounds (which I don't think you're doing)

[fiery cosmos]

Isn't len() at big O(1) call?

but i think the slice is whats causing it

[lean walrus]

it is

but you are copying height list over and over just to do simple len() call

[fiery cosmos]

oh so it becoms an O(n) complexity

making it n^2 ig

[lean walrus]

yes

[fiery cosmos]

yeah that fixed it, thanks!

[fiery cosmos]

this too ^

[regal spoke]

If you want to compute the length of a slice height[l:r] in O(1) time (and want something that works even in the case of weird out of bounds edge cases), then you can do len(range(len(height))[l:r])

Since ranges can be sliced and taken len of in O(1) time

[hardy palm]

What are basic data struct every CS student should know

[lean walrus]

ints

[haughty mountain]

*cries in js*

[fiery cosmos]

Can anyone explain me Tower of Hanoi problem with recusion as simple as possible. I just can't get it.

[lean walrus]

Lets pretend we want to move tower from peg A to peg B, using additional peg C.
To achieve that we will:

1. move everything except biggest disk from A to C
2. move biggest disk from A to B
3. move everything except biggest disk from C to B
   now the problem is solved
   note that steps 1 and 3 are equivalent to our main task, but operates on smaller towers

[fiery cosmos]

That I know but how to imagine the behaviour of the recursion when there are 4+ disk.

[narrow mica]

Imagine everything but the biggest disk as just 1 thing, and do the steps denball said

[lean walrus]

imagining whole process at once is not very productive

[haughty mountain]

the point of the recursion is the abstraction

that you can reason in terms of smaller instances of the same problem

[shadow oyster]

A = [1,2]
B = [1,2,3,2]

What would be a good name for a function that returns true when A⊆B and n((B-A)∩B) == 0 A⊆B and n((B-A)∩A)=0?

[vocal gorge]

hmm, isn't it equivalent to A==B? or do you mean in a non-set sense, but e.g. as multisets?

[shadow oyster]

Yeah, in a non-set sense. In this case, since B has two "2", C=B-A = [3,2] and n(C∩B) = 1 since both C and B have "2" in common.

I think it would be too complex to explain it in a name so I may just have to include A⊆B and n((B-A)∩B) == 0 A⊆B and n((B-A)∩A) as a comment

[vocal gorge]

Shouldn't n(C∩B) be 2, since [3,2]⊆[1,2,3,2] and hence C∩B=C?

[shadow oyster]

My bad, I meant to say A⊆B and n((B-A)∩A).

[vocal gorge]

Ah, that makes more sense. So it's A and B such that B-A removes some keys from the multiset B entirely without leaving any leftovers. I think it'd be equivalent to write:

def f(a: Counter[int], b: Counter[int]) -> bool:
    # return a.keys() <= b.keys() and all(a[k] == b[k] for k in a.keys())
    return all(a[k] == b[k] for k in a.keys())

no obvious name comes to my mind either.

[outer rain]

the first condition seems redundant

[vocal gorge]

true, actually.

[ebon finch]

Does Python cache computed values.

For example if I have a function f1 that has O(n) complexity and returns n-1 then I run this piece of code

i=0
while i<n:
f1() == i:
Return True
i+=1

Is this O(n) overall or does Python call f1() for each iteration making it O(n^2)

[agile sundial]

it does not cache

[ebon finch]

Even if I have something like this?

If f2()[0]==1 and f2[1]==2
Will Python call the function twice?

[agile sundial]

yep

Python can't tell if that's a correct thing to do

[outer rain]

it is practically impossible: python can't proof that function is pure

if you can, you can add a fancy @functools.cache decorator on it, and cache it yourself

(but just introducing a variable might be a better solution in your context)

[foggy fiber]

hi could some help me out with this problem
The path to the university can be considered as a sequence of blocks in a straight line, with Alicia's home located at block 0 and the university at block N. There are M trams that travel along this path. Tram i starts at block li and goes to block ri (li < ri). Alicia can board each tram from the block where it starts or while it's in motion, meaning she can board tram i between blocks [li, ri - 1]. When Alicia boards a tram, she only gets off at the destination block ri. A route consists of a sequence of trams that Alicia takes to reach the university from her home. Alicia only uses trams for transportation, so once she gets off a tram, she must board another one at the same block. Two routes are considered different if they use different trams. Since the number of routes can be very large, the result should be returned modulo 1,000,000,009.

Input:
The first line contains two integers N and M (1 ≤ N ≤ 1,000,000,000, 1 ≤ M ≤ 100,000).
The following M lines contain integers li and ri (0 ≤ li < ri ≤ N) indicating the starting and destination blocks of tram i.

Output:
An integer representing the number of possible routes.

Expected Time Complexity:
The solution should execute in a time less than or equal to 1 second for any input instance according to the given constraints.

Expected Complexity:
The solution should have a complexity of O(M * log(M)).

Examples:

Example 1:
Input:
3 3
0 1
1 2
2 3
Output:
1

Example 2:
Input:
5 4
0 3
0 2
2 5
3 5
Output:
5

n, m = map(int, input().split())
segments = []

for i in range(1, m + 1):
    l, r = map(int, input().split())

    segments.append((l, i))
    segments.append((r, -i))  # negative index means right point

segments.sort(key=lambda x: (x[0], x[1]))
# print(segments)

prefix1 = [0] * (m + 1)
prefix2 = [0] * (m + 1)
prefix = 0
add = 0
ans = 0

for pt, idx in segments:
    if idx > 0:  # is left point
        if pt == 0:
            prefix2[idx] = 1
        else:
            prefix1[idx] = prefix

        prefix += add
        add = 0
    else:
        idx = abs(idx)
        prefix2[idx] += prefix - prefix1[idx]
        add += prefix2[idx]
        if pt == n:
            ans += prefix2[idx]

print(ans)

ive managed to write this up, but it fails for this case

14 10
0 1
3 14
11 14
5 9
0 10
4 13
7 14
2 6
3 8
3 12

any help is apreciated

[foggy fiber]

the correct answer is 22

[modern gulch]

How would python know that the function is a pure function (no side effects / same value every time, etc)?

If you know that, you can add a cache / memoize the function.

[true osprey]

i have an object at pos [0,0] i want it to go to a random position at 1 distance from is current position (example : [0.5,0.5] , [0.9,0.1]) how do i do that.

[tight cedar]

pick a random number x from 0 to 1 then calculate sqrt(1 - x^2) for the y position?

nvm it is not the same kind of distance

[naive oak]

i don't think that would be uniform either

[solemn moss]

That's umm.. Manhattan distance?

Pick a number x from 0 to 1, y will be 1 - x.
Then multiply x and y by random 1 or -1

[jolly mortar]

r = 1
t = random.uniform(0, 2*pi)
dx = r*cos(t)
dy = r*sin(t)

add dx and dy to x and y

oh wait

distance is fixed at 1

[slender sandal]

The arclength of one radian in the unit circle is equal to its radius

Um

[slender sandal]

That seems right

[haughty mountain]

based on the example it's in manhattan distance

[haughty mountain]

swap with

man_cos(x) = 2/pi*arcsin(cos(x))
man_sin(x) = 2/pi*arcsin(sin(x))
```and it should work

it's silly, but y'know

[tulip bone]

so i calculated T(n) by simply subs the value of n
now, I should multiply it by 10 and then divide the answer by 3.2 GHz?

[haughty mountain]

work with units

T(n) operations * x cycles/operation * y seconds/cycle

= T(n) x y seconds

now put the proper x and y for the first expression

x = 10

I guess the nicer way to write the second is

second/(y' cycles)

y' = 1/y = 3.2*10^9

[tulip bone]

thanks

[misty kindle]

Hey guys, trying to use Alpha Tensor in all pairs shortest path problem for Floyd Warshall and Johnson, does anybody have experience with it?

[arctic ginkgo]

ik its theta(n log n)

but how does one write it in master theorem form

[summer fossil]

master theorem has 3 cases u need to check which cases is this

[fiery cosmos]

FREE PALESTINE 🇵🇸

[halcyon plank]

:incoming_envelope: :ok_hand: applied timeout to @marsh pecan until <t:1698597628:f> (10 minutes) (reason: duplicates spam - sent 4 duplicate messages).

The <@&831776746206265384> have been alerted for review.

:incoming_envelope: :ok_hand: applied timeout to @misty saffron until <t:1698597625:f> (10 minutes) (reason: duplicates spam - sent 4 duplicate messages).

The <@&831776746206265384> have been alerted for review.

:incoming_envelope: :ok_hand: applied timeout to @fiery cosmos until <t:1698597644:f> (10 minutes) (reason: duplicates spam - sent 4 duplicate messages).

The <@&831776746206265384> have been alerted for review.

[lean walrus]

something suspicious is going on there

[brittle gate]

Can anyone tell me a video tutorial from where I can learn Data structures and algorithms? I finished Bro codes 12 hour video on python and tried to go on leetcode and do some questions but didn't understand jack shit so anyone who knows something?

[lean walrus]

!res check this

[halcyon plank]

Resources

The Resources page on our website contains a list of hand-selected learning resources that we regularly recommend to both beginners and experts.

[lean walrus]

and check pins in this channel

[old rover]

Write a short Python function, is even(k), that takes an integer value and returns True if k is even, and False otherwise. However, your function cannot use the multiplication, modulo, or division operators.

🤔

how do you do this without using modulus?

it never mentioned that you can't use a bitwise operator

[agile sundial]

or recursion

[old rover]

i think the book doesn't want me to use recursion this early on

[agile sundial]

binary search

[old rover]

this is like the first chapter before any of that is introduced

data structures and algorithms by michael something

michael t goodrich

[agile sundial]

¯_(ツ)_/¯

[old rover]

rip me ig

#R-1.2. compares to last character in the string.

def is_even(k):
  b = bin(k)
  print(b)
  return b[-1] == "0"

print(is_even(1))
print(is_even(2))

oh hang on

Write a short Python function, minmax(data), that takes a sequence of one or more numbers, and returns the smallest and largest numbers, in the form of a tuple of length two. Do not use the built-in functions min or max in implementing your solution.

#R - 1.3 -> two pointer approach

def minmax(data):
  min_val = data[0]
  max_val = data[0]
  for x in data:
    if x < min_val:
      min_val = x
    elif x > max_val:
      max_val = x
  return (min_val, max_val)

classic two pointer approach here

[fervent saddle]

Isn't that just one pointer?

[old rover]

oh is it considered two pointers if they start from opposite sides?

[fervent saddle]

You could subtract 2 until you reach either 0 or 1.

I think just any situation with two pointers in the array.

Like sliding window is a type of two pointer solution as well.

[old rover]

i see

i haven't coded in so long

but for some reason my brain is trying to code again

plus it's a bad look for a product/project manager to not have any coding skills

[haughty mountain]

opposite sides not needed

just two different pointers (or really indices in the python case) that walk through the list in different ways

[old rover]

so in this code there isn't two pointers?

[haughty mountain]

you're just doing one straight iteration through the data

[old rover]

right

[glossy echo]

is this the channel to ask for algos? I made a little algo and I would like some suggestions

[regal spoke]

To me, two pointer refers to a specific method. For example, the standard algorithm to solve this problem is called two pointer:

Given a sorted list of n integers and a goal number g. Find if there exists a pair of integers in the list that sum to g.

One of the possible tags for problems on codeforces.com is "two pointer". That tag specifically refers to problems solved using this kind of method ^

[old rover]

right i guess this isn't even a two pointer problem

either way, still kicked my ass

[regal spoke]

There are tons of ways to do this with bit operations. For example x & 1 == 0, x + 1 == x | 1, x ^ 1 == x | 1, (x >> 1) << 1 == x, ...

There is also (-1) ** x >= 0

[olive badge]

leetcode can be easy, maybe you dont know how to filter

[olive badge]

no one will beg you to send your problem, people here tend to have a bit of superiority, so if you want to ask something be direct

[agile sundial]

the 12 hour video will not be enough to prepare you for leetcode. you'll need programming fundamentals before trying to learn dsa

[glossy echo]

thank you, I asked that way because of the same thing, I didn't want to be attacked because of unrelated content hahah

I made a little "algorithm" to calculate how much points a song should get based on how much it has been played, and I would like to get some suggestions on how to improve it. Here's the code:

def calculate_points(playcount):
    if playcount == 1:
        return 1

    adjusted_playcount = min(playcount, 10)
    total_points = 1
    next_point_amount = 0.5

    for _ in range(2, adjusted_playcount + 1):
        total_points += next_point_amount
        next_point_amount *= 0.25

    return total_points

[olive badge]

your code is working as you expect?

why did you started in 2 if you are not using a variable

!e

def calculate_points(playcount):
    if playcount == 1:
        return 1

    adjusted_playcount = min(playcount, 10)
    total_points = 1

    next_point_amount = 0.5 * (1 - (0.25 ** (adjusted_playcount - 1))) / (1 - 0.25)

    total_points += next_point_amount

    return total_points

print(calculate_points(100))

[halcyon plank]

@olive badge :white_check_mark: Your 3.12 eval job has completed with return code 0.

1.6666641235351562

[olive badge]

this givethe same result without creating a loop

btw, i dont understood exactly what you wanted i just tried to simplified

[olive badge]

If you already know the basics, I would recommend that you always try solving problems that are harder than those you can currently handle, https://neetcode.io/roadmap
this is a roadmap for solving leetcode, (not enough for competitive programming) but if you want to solve only leetcode problems you can try it, also, every problem in that roadmap has its video explaining how to solve it, but obviously you wont watch the video first, it wouldnt make senses

[narrow mica]

Besides the bit magics, one may overlook the fact that you can also just turn it into a string and check if the last digit is 0, 2, 4, 6 or 8

[naive oak]

if exponentiation isn't banned then (-1)**n == 1 is a pretty easy check

[calm juniper]

yeah that's a good point you should go with that,

def is_even(k):
  return k&1==0

[glossy echo]

The whole code basically sorts songs based on the points. And the points are calculated by user. So, the adjusted playcount is that the max plays they can give a song is 10, and then calculate how much points a song would get. The first play is 1 and then after that it should have the same points.

[brittle gate]

Any ideas on where I could learn more? or is it just practice after the tutorials

[brittle gate]

I think I know the basics decently, Thanks for the roadmap and the advice

[lean walrus]

math.cos(math.pi * x) > 0

[exotic bolt]

do all constructs in Backus–Naur form correspond to a construct in pyparsing? i'm willing to put in the time necessary to learn the theory (linguistics? comp sci?) to be able to use pyparsing for more complicated parsing tasks, where should I start?

[haughty mountain]

it's basically the same as in other channels where "don't ask to ask, just ask" is a thing

[indigo imp]

Hey, I got the challenge to sub 1s

with just math module

339ms

[haughty mountain]

I got it to 120ms

[indigo imp]

import time
import math
# import numpy
# from decimal import Decimal, getcontext

# getcontext().prec = 100000000
 
def checkprime(end:int)->list[int]:
    primes,used_primes = [2], [2]
    len1, len2 = 1, 1
    if end>=2:
        yield 2
    for num in range(3,end+1,2):
        isprime = True
        if num != 3 and num % 3 == 0:
            continue
        if num != 5 and num % 5 == 0:
            continue
        if num != 7 and num % 7 == 0:
            continue
        # sqrtv = int(math.sqrt(num))
        sqrtv = int(num**(1/2))
        while len1 > len2 and primes[len2] <= sqrtv:
            used_primes += [primes[len2]]
            len2 += 1
        for prime in used_primes:
            if num % prime == 0:
                isprime = False
                break
        if isprime:
            primes += [num]
            len1 += 1
            yield num
     
 
to = 250000

start = time.perf_counter()
value = 1
all_prime = checkprime(to)
sqrtv =int(to**0.5)
# print(time.perf_counter()-start)
for prime in all_prime:
    times = int(math.log(to,prime))
    value *= prime ** times
    if times == 1:
        break
# print(time.perf_counter()-start)
value *= math.prod(list(all_prime))
# value = Decimal(value)
#for prime in all_prime:
#    value *= prime

end = time.perf_counter()
print(value)
print(end-start)

[haughty mountain]

I mean, worst case you would have been told "not on topic, try this other channel"

[indigo imp]

with just builtin and math?

[haughty mountain]

yeah

[indigo imp]

do you mind to show your approach?

[haughty mountain]

and 40ms with one changed line to use gmpy2 line

[indigo imp]

idk if I was limit by my prime generator or multiplying speed

[haughty mountain]

seems I had ~120ms on my computer before inlining my logic into the sieve itself, this was slightly faster

import time

def solve(n):
    res = 1
    pr = [True] * (n + 1)
    pr[0] = pr[1] = False
    for i in range(2, n + 1):
        if pr[i]:
            for j in range(i * i, n + 1, i):
                pr[j] = False
            fac = i
            while fac * i <= n:
                fac *= i
            res *= fac

    return res

n = 250000

start = time.perf_counter()
res = solve(n)
end = time.perf_counter()

print(res)

print(f"{1000*(end - start):0.2f} ms")

[indigo imp]

but yeah, I should probably code a better prime gen with some math investigation

[indigo imp]

thx

[haughty mountain]

and 1 line change with gmp

import time
import gmpy2

def solve(n):
    res = gmpy2.mpz(1)
    pr = [True] * (n + 1)
    pr[0] = pr[1] = False
    for i in range(2, n + 1):
        if pr[i]:
            for j in range(i * i, n + 1, i):
                pr[j] = False
            fac = i
            while fac * i <= n:
                fac *= i
            res *= fac

    return res

n = 250000

start = time.perf_counter()
res = solve(n)
end = time.perf_counter()

print(res)

print(f"{1000*(end - start):0.2f} ms")

[indigo imp]

lmao, I think it is my computer fault

it show me 367 ms

And 257 ms on my phone

Still faster, but less difference than I thought

(and if you are curious, yes my phone is faster than my laptop, consider my phone is more expensive than my second handed laptop)

[haughty mountain]

the sieve part is a pretty small part, most of the time is just dealing with the big numbers

[indigo imp]

yeah, my prime gen took half of the 339ms on my phone

like 160ms

i think

and that is probably the gap that could fix if I use sieve prime gen

[haughty mountain]

half seems like way too much

[haughty mountain]

try commenting out the res *= fac in my code

that is the sieve + calculating the prime power that should be included

[indigo imp]

yeah, by using sieve prime gen

my code runtime bring down to 265ms

which can seem as equal

but yeah, yours still better

since you didn't use math

I am using math.log (and math.prod but it could be easily replaced)

[haughty mountain]

!e and as further proof the multiplication is the thing bogging things down, here is with a version that's a tad smarter about what multiplications are made

import time

def solve(n):
    res = []
    pr = [True] * (n + 1)
    pr[0] = pr[1] = False
    for i in range(2, n + 1):
        if pr[i]:
            for j in range(i * i, n + 1, i):
                pr[j] = False
            fac = i
            while fac * i <= n:
                fac *= i
            res.append(fac)

    while len(res) > 1:
      tmp = []
      if len(res)%2 == 1:
        tmp.append(res.pop())
      tmp += [res[i]*res[i+1] for i in range(0, len(res), 2)]
      res = tmp

    return res[0]

def solve_old(n):
    res = 1
    pr = [True] * (n + 1)
    pr[0] = pr[1] = False
    for i in range(2, n + 1):
        if pr[i]:
            for j in range(i * i, n + 1, i):
                pr[j] = False
            fac = i
            while fac * i <= n:
                fac *= i
            res *= fac

    return res

n = 250000

start = time.perf_counter()
res = solve(n)
end = time.perf_counter()

start_old = time.perf_counter()
res_old = solve_old(n)
end_old = time.perf_counter()

assert res == res_old

print(f"new {1000*(end - start):0.2f} ms")
print(f"old {1000*(end_old - start_old):0.2f} ms")

[halcyon plank]

@haughty mountain :white_check_mark: Your 3.12 eval job has completed with return code 0.

001 | new 87.45 ms
002 | old 208.84 ms

[haughty mountain]

it's not even that clever

just trying to keep numbers roughly the same size to avoid lopsided multiplication which is generally slower

[indigo imp]

That a great idea that I was trying to add

[haughty mountain]

and with that I think the sieve speed is actually starting to be noticable again, like half the time

[indigo imp]

But I need to thing how would I do it

Since I get stuff directly from generator

[regal spoke]

!e

import time

def solve(n):
    res = 1
    pr = [True] * (n + 1)
    pr[0] = pr[1] = False
    for i in range(n + 1):
        if pr[i]:
            for j in range(i * i, n + 1, i):
                pr[j] = False
            fac = i
            while fac * i <= n:
                fac *= i
            if fac == i != n:
              break
            res *= fac
    
    A = [i for i in range(i, n + 1) if pr[i]]
    A[1::2] = A[1::2][::-1]   

    while len(A) > 1:
      A = [A[i] * A[i + 1] if i != len(A) - 1 else A[i] for i in range(0, len(A), 2)]
    return res * A[0] if A else res

n = 250000

start = time.perf_counter()
res = solve(n)
end = time.perf_counter()

print(f"{1000*(end - start):0.2f} ms")

[halcyon plank]

@regal spoke :white_check_mark: Your 3.12 eval job has completed with return code 0.

75.87 ms

[haughty mountain]

there is a bunch of stuff that could be improved

[regal spoke]

I did two changes. I only do the smart multiplication for numbers >= sqrt(n)

Secondly I try to keep the product roughly the same size

I do this by running A[1::2] = A[1::2][::-1] before starting to multiply everything

[haughty mountain]

don't all the numbers end up >= sqrt(n)?

[regal spoke]

Hmm ok ye

[haughty mountain]

fac is the highest power of the prime that's <= n

[old rover]

Python allows negative integers to be used as indices into a sequence, such as a string. If string s has length n, and expression s[k] is used for in- dex −n ≤ k < 0, what is the equivalent index j ≥ 0 such that s[j] references the same element?

https://tenor.com/view/huh-cat-huh-m4rtin-huh-huh-meme-what-cat-gif-27377993

[haughty mountain]

you could just try it out

[old rover]

oh this is easy actually

just create a string

yeah

i'm dumb lol

[haughty mountain]

but fwiw the negative and non-negative index differ by len(s)

I can sense a ||~|| coming

[regal spoke]

!e

import time

def solve(n):
    res = 1
    pr = [True] * (n + 1)
    pr[0] = pr[1] = False
    i = 0
    while i * i <= n:
        if pr[i]:
            for j in range(i * i, n + 1, i):
                pr[j] = False
        i += 1
    
    A = []
    for i in range(n + 1):
      if pr[i]:
        j = i
        while j * i <= n:
          j *= i
        A.append(j)
    A.sort()
    A[1::2] = A[1::2][::-1]

    while len(A) > 1:
      A = [A[i] * A[i + 1] if i != len(A) - 1 else A[i] for i in range(0, len(A), 2)]
    return A[0]

n = 250000

start = time.perf_counter()
res = solve(n)
end = time.perf_counter()

print(f"{1000*(end - start):0.2f} ms")

[halcyon plank]

@regal spoke :white_check_mark: Your 3.12 eval job has completed with return code 0.

108.09 ms

[regal spoke]

Didn't expect that to be slower

[haughty mountain]

do you expect to gain much from this?

A[1::2] = A[1::2][::-1]

all numbers should be close-ish to n

within a factor of the prime

hmm, I guess for primes > sqrt(n) you will be quite a bit off

since you can't get another factor in at all

but I suspect just doing every other number is pretty good, it's not important that they are really close in size, the main thing is just to avoid the really lopsided multiplications

[sand sequoia]

Hi. I have an issue in commenting out multiple lines of code. I'm using PyCharm and am aware that I have to do ctrl + shift + / yet it doesn't work for me. Anyone has an idea as to how I'm supposed to fix my issue ?

[solemn moss]

Help -> Find Action -> search for comment -> check your hotkey for it
By me it's ctrl + /

[sand sequoia]

It shows the same thing for me. My / is with a : so i have to press shift to actually write /. I tried ctrl+/ and ctrl+shift+/ but it doesn't work for me 😭

[solemn moss]

Just comment it with multiline?

!e

"""
A big 
comment
with multiple
lines
"""

[halcyon plank]

@solemn moss :warning: Your 3.12 eval job has completed with return code 0.

[No output]

[solemn moss]

Or change your hotkey to something different

[sand sequoia]

Yes the multiline option i'm aware of but I just thought pressing ctrl+/ was just so much faster. How do I change my hotkey to smtg different? (sry im a beginner)

[solemn moss]

Settings - Keymap - find there comment

[slender sandal]

The / key is m's third right neighbor

[sand sequoia]

Yess finally works. I changed it to ctrl+: and ctrl+shift+: since : and / are in the same key and shift somehow doesnt activate /.

[sand sequoia]

That key is a downward arrow for me hh

[slender sandal]

What weird physical keyboard has the arrow keys on the same area where there are characters

[sand sequoia]

Well I don't exactly know what it is but my keyboard is "azerty" and the arrow has 3 horizontal stripes on it. (dunno what it is tbh)

[slender sandal]

TIL an AZERTY layout exists and it combines arrow keys where there are character keys

[haughty mountain]

it usually doesn't afaik

the layout of the punctuation is interesting though

M is on the middle row

/ would be 3 right of N

but it's possible it's some more exotic variant of this, idk

[sand sequoia]

It's pretty close to this yes but a few variants on the right side. Also, I'm just getting started with this 12h beginnner course and I have another issue. I do not have greater than or lesser than keys so I'm kind of in a pinch specially since i'm currently learning the if statements 😦

[slender sandal]

They are left to your W

[slender sandal]

Assuming this layout

[sand sequoia]

This keyboard is annoying af 😫

[haughty mountain]

I'm scared of the layout of you rkeyboard if it's missing all these keys 🥴

[sand sequoia]

wait lemme try send my layout

[slender sandal]

Why not change layout

[haughty mountain]

for everyone's sanity 😛

[sand sequoia]

hhh

[haughty mountain]

this looks painful

[agile sundial]

this is an #algos-and-data-structs moment

[sand sequoia]

I'm just realizing this is hell

[slender sandal]

Find the time complexity of writing code in that keyboard layout

[haughty mountain]

it somehow manages to be so much worse than the keyboard layout I learned on

[slender sandal]

I think it's amazing that your tech store sold you a laptop with this keyboard layout

It even has hang up and answer phone keys

[haughty mountain]

I'm surprised to see an ansi azerty keyboard

[sand sequoia]

😂 and I just bought it as well. Reconditioned. I didn't buy it with the thought of learning code initially but it just came to me. Turns out this was worst timing 😩

[haughty mountain]

but given it's an ansi keyboard you could actually try to switch the layout in your OS to be the usual US layout which is quite nice for programming

[slender sandal]

Maybe <> exist as some cursed combination of modifier keys

[haughty mountain]

if you're ok with learning a new layout I can really recommend doing this

[sand sequoia]

looked around and apparently alt + 6 + 0/2 is the solution. doesnt work for me tho unsurprisingly

[haughty mountain]

I switched to US layout when I started working and it's so much nicer when you get used to it

[slender sandal]

Right Alt key

Discord hotkeys be wild

[sand sequoia]

I am too used to azerty since I'm french tho but aside from the letters the rest I could

[slender sandal]

Make sure you're using numlock on

[haughty mountain]

there probably exists some unholy azerty US layout

[slender sandal]

I always find missing universally recognized keys on foreign keyboard layouts hard to believe

Don't the French know < and > as "less than" and "greater than"?

[haughty mountain]

they do in their normal layout

but this is some fun ansi variant

which lacks the key that's usually <>

[slender sandal]

ANSI - American National Standards Institute
I guess he is an American French... Canadian?

[sand sequoia]

Yes believe even I am surpised there are no such keys as I just realised it trying to learn code. (on top of everything else that's weird). Still getting used to this keyboard. (tho i'd rather not get used to this if I do plan on learning coding).

[haughty mountain]

yeah

[slender sandal]

I'm trying to figure out how to switch keyboard layouts on Windows 11

[sand sequoia]

Just bought this reconditioned pc in the meantime as my mac's motherboard fried

[slender sandal]

Time & language > Language & region > Options (... on any language) > Add a keyboard

[slender sandal]

Oh is it MacOS

Well RIP

[sand sequoia]

MacBook Air

[slender sandal]

AYO NO WAY

TF IS A PROGRAMMER LAYOUT

[haughty mountain]

possibly something a bit more sane for programming than the usual international layouts

[slender sandal]

French (neither Belgian nor Canadian) has only one keyboard layout which is AZERTY

[haughty mountain]

and french french?

[slender sandal]

Doesn't exist

[haughty mountain]

it...must

[slender sandal]

Belgian French kinds, Canadian French kinds, French (AZERTY)

[haughty mountain]

ah, the latter is that then

[sand sequoia]

My visual keyboard has it 💀

[slender sandal]

Apparently many languages have this kind of layout installable

[haughty mountain]

hey, iso

[slender sandal]

It matches the language layout, not your physical keyboard keys

It's cursed that your physical keyboard keys don't match a language layout

[sand sequoia]

ugh..

[slender sandal]

So happy my native language layout is similar to English US QWERTY

For non letter keys

For the most part

[sand sequoia]

anyways i might just postpone learning coding w/ this keyboard layout for now. Just consecrating an 1h30 at the end of my study sessions anyways hh hopefully i'll get a better layout. Any keyboard layout recommandation that's (AZERTY) for me to look for in the future?

[haughty mountain]

I don't really know much about azerty keyboards tbh

[slender sandal]

What happens when you press the < or > key

[sand sequoia]

That's programming-friendly

nothing lol

[slender sandal]

You literally don't have any key mapped to it

What non standard physical French keyboard is this lol

[sand sequoia]

Next time I'll look out for the keyboard layout b4 buying a pc from backmarket 😂

[haughty mountain]

lmao https://www.reddit.com/r/ProgrammerHumor/comments/e7z8pl/is_there_a_keyboard_layout_worse_than_azerty_for/

[slender sandal]

It's weirdly palindromic on the top row, ye

With parentheses

[haughty mountain]

I would genuinely recommend trying the US layout for programming

[sand sequoia]

dang now im thinking of switching to a qwerty layout lol.

What does it look like?

[haughty mountain]

you have a physical layout that works for it

[sand sequoia]

bruh this is so much better

[haughty mountain]

yeah

[sand sequoia]

it's like everything is where it's meant to be hh

[haughty mountain]

you can set up so you can switch between two layouts on windows

so you should be able to set up whatever is the default and then US ansi

and then you can switch for typing in french if you need that

[sand sequoia]

but i dont understand how that works. I'd still have the same physical layout which would be very confusing no?

[slender sandal]

@sand sequoia #algos-and-data-structs message

Switching installed layouts is done by Windows + Spacebar

[haughty mountain]

basically yeah it will be confusing until you learn the layout

keep an image of the layout around for reference 😛

[sand sequoia]

Like until i woudln't even have to look at my keyboard basically

[haughty mountain]

technically there are labels you can buy

[sand sequoia]

Yeah i see

[haughty mountain]

but that's probably more hassle than it's worth

[slender sandal]

Your physical keyboard keys seem standard except for what they should be mapped for

So switching a language layout will work but you'll have to rememorize most keys

That stage is inevitable anyway

You will be blind typing with your current physical keyboard

Unless you buy stickers or something

[haughty mountain]

but you actually have an ansi keyboard that fits US ansi

which is actually nice

[sand sequoia]

Ok I'll consider it. I was thinking buying a usb keyboard with the layout but that'd look goofy w/ my laptop lol

[haughty mountain]

I did actually buy a crappy US layout keyboard to be able to try it out and practice

but I can imagine it's a bit awkward with a laptop

[sand sequoia]

Exactly yes. Anyways thanks for helping me 🙂

[slender sandal]

I'm literally using an old Chicony®️ keyboard which is connected to one of my laptop's USB ports

This sorry thing

[old rover]

#R-1.14



def reverse_list_of_integers(data):
    reversed_array=[]
    for i in range(0, len(data)):
        reversed_array.append(data[len(data)-i-1])
    return reversed_array

print(reverse_list_of_integers([1,2,3]))

so i'm looking at this

and what's inside the for loop is kind of confusing

it takes the length of the data, subtracts the index, and then subtracts 1

[haughty mountain]

It's an awkward way of doing it in python, that's for sure

[old rover]

"Write a pseudo-code description of a function that reverses a list of n integers, so that the numbers are listed in the opposite order than they were before, and compare this method to an equivalent Python function for doing the same thing."

[haughty mountain]

but this is indexing backwards from the end of the list

the last element is at len(data) - 1

[old rover]

right bc indexes start from 0

[haughty mountain]

which should hopefully make subtracting i from that make sense

[old rover]

yeah

i think if i step into the function that should help

[old rover]

my idea was to multiply each index by a negative number and then somehow flip the list but then i realized it was impossible

so i searched for a solution

[haughty mountain]

the kinda canonical way of reversing a list/tuple/str/... in python is

return data[::-1]