algos-and-data-structs

[old rover]

oh i see

[haughty mountain]

but maybe it's good at least knowing what's going on in the code you shared

it just goes through the list backwards and appending elements to a new list

[old rover]

yep

what is that site where i can step through my code

i forgot the name

[haughty mountain]

some other ways of doing the same thing

def reverse_list_of_integers(data):
    reversed_array=[]
    for element in reversed(data):
        reversed_array.append(element)
    return reversed_array

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

[old rover]

algorithm visualizer or something

[haughty mountain]

I mean, there is not a lot going on here

[old rover]

yeah

found the site

https://pythontutor.com/visualize.html#mode=edit

[haughty mountain]

idk if that helps much more than just running it through in your head

data: [1, 2, 3]  reversed_data: [3]
             ^
data: [1, 2, 3]  reversed_data: [3, 2]
          ^
data: [1, 2, 3]  reversed_data: [3, 2, 1]
       ^

[old rover]

i took a look at the code and instantly knew what it did, i just feel like if i had to write it alone without anything i wouldn't be able to

[lean walrus]

!e

easy way to convert list to tuple:

a = [1,2,3,4,5]
b = next(zip(*map(lambda x:[x],a)))
print(a)
print(b)

[halcyon plank]

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

001 | [1, 2, 3, 4, 5]
002 | (1, 2, 3, 4, 5)

[haughty mountain]

borderline esopy

[old rover]

?

[lean walrus]

another way: sum(zip(a),start=()), less esopy-ish

[olive spear]

can someone help me

pls

i need someone to help me program a rock paper scissors game with replit

if anyone can helpp me/

[normal gull]

Here in 🇳🇿 we use the US keyboard layout. For typing accented characters and other useful stuff, I define a compose key http://wiki.wlug.org.nz/ComposeKey .

[modern gulch]

Happy to, but wrong channel. Head over to #python-discussion or open a help thread: #❓｜how-to-get-help

[fiery cosmos]

Is there a good book on the practical implementation and edge cases of A&DS

[haughty mountain]

compose key is great for typing weirder stuff

also nice and customizable, I added a bunch of stuff like greek characters since I ended up writing a bunch of that for math related stuff

[exotic bolt]

is there such a thing as a tool that allows you to define a context-free grammar then helps you write a grammatically correct sentence through features like suggestions and autocompletion?

or at least tells you the nature of the token you're currently writing

[muted hound]

import numpy as np
from sklearn.model_selection import train_test_split
import tensorflow.keras as keras

# path to json file that stores MFCCs and genre labels for each processed segment
#DATA_PATH = "path/to/dataset/in/json/file"

def load_data():

    # convert lists to numpy arrays
    X = np.array(df_train_normal1["mfcc1_mean"])
    y = np.array(df_train_normal1["label"])

    print("Data succesfully loaded")

    return  X, y


if __name__ == "__main__":

    # load data
    X, y = load_data()
    print(X.shape[0])

    # create train/test split
    X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)

    # build network topology
    model = keras.Sequential([

        # input layer
        keras.layers.InputLayer(input_shape=(X.shape[0],1)),



        # 1st dense layer
        keras.layers.Dense(512, activation='relu'),

        # 2nd dense layer
        keras.layers.Dense(256, activation='relu'),

        # 3rd dense layer
        keras.layers.Dense(64, activation='relu'),

        # output layer
        keras.layers.Dense(10, activation='softmax')
    ])

    # compile model
    optimiser = keras.optimizers.Adam(learning_rate=0.0001)
    model.compile(optimizer=optimiser,
                  loss='sparse_categorical_crossentropy',
                  metrics=['accuracy'])

    model.summary()

    # train model
    history = model.fit(X_train, y_train, validation_data=(X_test, y_test), batch_size=32, epochs=50)```

I am trying to classify music into genres and am using an ANN
I have error in this line ``keras.layers.InputLayer(input_shape=(X.shape[0],1)),``
Anyone know what I should do

[slender sandal]

Maybe the people at #data-science-and-ml

[sand echo]

I want to update my excel sheet with nifty spot price along with India Vix using python, could someone help me to get it done?

[slender sandal]

It seems niche enough so you can claim your own help channel

[exotic bolt]

anyone have suggested readings on language design with python? is there like a standard reference on the conceptual aspect of language design? i'm making a database query/insertion grammar and I wonder if there's more sophisticated stuff that would help me understand the bigger picture

[fiery cosmos]

method to quickly enumerate duplicate entries in a list and their quantity?

i'm thinking enumerate..

[vocal gorge]

!docs collections.Counter

[halcyon plank]

collections.Counter

class collections.Counter([iterable-or-mapping])```
A [`Counter`](https://docs.python.org/3/library/collections.html#collections.Counter) is a [`dict`](https://docs.python.org/3/library/stdtypes.html#dict) subclass for counting [hashable](https://docs.python.org/3/glossary.html#term-hashable) objects. It is a collection where elements are stored as dictionary keys and their counts are stored as dictionary values. Counts are allowed to be any integer value including zero or negative counts. The [`Counter`](https://docs.python.org/3/library/collections.html#collections.Counter) class is similar to bags or multisets in other languages.

Elements are counted from an *iterable* or initialized from another *mapping* (or counter):

```py
>>> c = Counter()                           # a new, empty counter
>>> c = Counter('gallahad')                 # a new counter from an iterable
>>> c = Counter({'red': 4, 'blue': 2})      # a new counter from a mapping
>>> c = Counter(cats=4, dogs=8)             # a new counter from keyword args

[fiery cosmos]

ty

[gray copper]

just recently did a practice test for an interview but I struggled a lot with it.

Quest was: Write a function that, given a string S consisting of N lowercase English letters, returns the length of the longest substring in which every letter occurs an even number of times. A substring is defined as a contiguous segment of a string. If no such substring exists, retum 0.

Given S = "bdaaadadb", the function should return 6. Substrings in which every letter occurs an
even number of times are "aa”, “adad", "daaada" and "aaadad”. The length of the longest of them is 6.

Given S = "abacb, the function should return O. There is no non-empty substring in which every
letter occurs an even number of times.

Given S = "zthtzh", the function should return 6. Every letter in the whole string occurs an even
number of times.

My approach was looping through the string, adding the letter to a dictionary and incrementing the value by 1 whenever it appeared, and checking if the dictionary[char] % 2 was equal to 0 or 1, to see if it occurs even time or not. But after that, I didn’t know what to do. Can anyone help or guide me to the right direction?

[snow anvil]

# find the longest substring with an even amount of every letter

def findSubSring(string):
    charDict = {}
    strlen = len(string)
    start = 0
    end = strlen


    for char in string:
        if not (char in charDict.keys()):
            charDict[char] = 1
            continue
        charDict[char] += 1


    sublen = strlen
    found = False


    while sublen != 0:


        if start + sublen == strlen - 1:
            start = 0

        if sublen > strlen//2:
            dict_copy = charDict.copy()
            print(f"substr = {string[start: start + strlen]}")
            print(f"start = {string[0: start - 1]}")
            print(f"end = {string[start + sublen + 1: strlen - 1]}")

            for char in string[0: start - 1 - strlen]:
                #print(string[0: start - 1])
                dict_copy[char] -= 1
            for char in string[start + sublen + 1: strlen - 1]:
                #print(string[start + sublen + 1: strlen - 1])
                dict_copy[char] -= 1
            print(dict_copy)
            for char in dict_copy:
                if dict_copy[char] % 2 != 0:
                    found = False
                    break
                found = True

        else:
            newDict = {}
            for char in string[start: start + sublen]:
                if not (char in newDict.keys()):
                    newDict[char] = 1
                    continue
                newDict[char] += 1
            print(newDict)
            for char in newDict:
                if newDict[char] % 2 != 0:
                    found = False
                    break
                found = True

        if found:
            return sublen
        sublen -= 1
  return 0

I have only tested your first 2 examples and dont know if it works in general but hopefully the idea I am going for is clear

also the code is hella ugly

🤷‍♂️

there is most likely a better approach though but I will leave that for someone smarter than myself

any critiques of my code are welcome

[gray copper]

I’m still tryna wrap my head around it, but may I ask; what was your approach to this? Cuz for the for loop I would have never thought of using slicing, which makes sense to use tbh

[snow anvil]

I dont even think it works correctly but whatever I have other things to do

[snow anvil]

well even if this code does not exactly work(idk lol) my approach was I have the letters saved in the dictionary and I just start from the largest substring which is the string itself check if it fulfils the criteria then I look at [strin] and [tring] all I have to do there is subtract 1 g and t from the dictionary respectively

the statement after else is just doing it iteratively because if the substring is too small it would take more time to compute the strings on either side than it would be to just compute the substring

[gray copper]

Ahh I see okay. I kinda understand what you’re tryna do. Tbh it’s better than my approach. Thank you for your answer. I think I have an idea of tackling this now :d

[snow anvil]

👍

[olive badge]

hey guys do you know where can i get the main algorithms for dsa? for example dfs,dsa, dijkstra

i´ve googled but i can´t find something relevant

[agile sundial]

there aren't "main algorithms", it's not really a thing

[narrow mica]

Not sure what you mean by "main algorithms", but here's a site (in C++) for competitive programming algos (which has dfs/dijkstra/etc.) https://cp-algorithms.com/

[loud niche]

my code for a binary search tree doesn't print anything

    def __init__(self, rootNode) -> None:
        self.rootNode = rootNode
        self.left = None
        self.right = None
    
    def insertNode(self, nodeToInsert):
        if nodeToInsert < self.rootNode:
            if self.left is None:
                self.left = treeNode(nodeToInsert)
            else:
                self.left.insertNode(nodeToInsert)
        if nodeToInsert > self.rootNode:
            if self.right is None:
                self.right = treeNode(nodeToInsert)
            else:
                self.right.insertNode(nodeToInsert)

    # Far left to far right
    def inOrderTraversal(self):
        if self.left:
            self.left.inOrderTraversal()
        print(self.rootNode)
        if self.right:
            self.right.inOrderTraversal()

tree = treeNode(5)
tree.insertNode(6)
tree.insertNode(7)
tree.insertNode(8)
tree.insertNode(9)```

[regal spoke]

Well you need to call inOrderTraversal to make it print

[regal spoke]

If you are looking for Python implementations, then you could take a look here https://github.com/cheran-senthil/PyRival
Most of the standard algorithms and data structures can be found here.

[loud niche]

right

[loud niche]

thank you

[modern gulch]

See the pin for the Mit ocw course. The syllabus/curriculum there is probably a good start.

[unique jasper]

is there such a thing as an educated binary search tree? Basically, instead of going to the middle of the current scope each turn, the alg could keep track of frequencies and choose better indexes, maybe more to the left or the right of the exact middle, as if it was trying to guess where the target should be

[ebon finch]

You have to solve the specific question that leetcode set for the day, you can access it from the problem list since it automatically sits at the top or just click on the fire icon on the top right of the nav bar

[haughty mountain]

do you actually mean a binary search tree or just binary search?

[unique jasper]

not sure about the terminology. Its the "go to middle, if more then go to 3/4 and if less then go to 1/4 and repeat till done"

[haughty mountain]

a binary search tree is a specific structure, I'm guessing you really mean binary search

and you're curious if you can do better by adding a bias when doing the binary search

[unique jasper]

yes

maybe a bias thats specific to every iteration or grows more accurate at every execution

[haughty mountain]

if you know about the distribution of data you can usually do better guesses

this seems related https://en.wikipedia.org/wiki/Interpolation_search

[unique jasper]

That's an interesting one! Thank you

[fickle adder]

so like i want add a number to some length now i want that number to be large if the length is small like 2 or 3 is length then the number i want can be like 3 or 4 but if the length is large like 10,000 then the number should be small like 10 or 20 and if the number is very large then then addition should be nill how should i do this using simple math.

[modern gulch]

You want a function that given a ‘length’ n, returns maybe n*2 when n is < some threshold, or n/1000 when n is > the threshold?

[fickle adder]

yes that can be done but i thought there should be a more mathematical way like when we add length * 0.2 then the number i got increase with the size of length but i want it to increase first then decrease like this

[fiery cosmos]

My implementation:

public class Queue {
   private int capacity;
   private int currentSize;
   private int[] arr;
   
   public Queue(int capacity) {
      this.capacity = capacity;
      this.arr = new int[capacity];
      this.currentSize = -1;
   }
   
   public int size() {
      return currentSize + 1;
   }
   
   public boolean isEmpty() {
      return currentSize == -1;
   }
   
   public boolean isFull() {
      return currentSize == capacity - 1;
   }
   
   public void enqueue(int data) {
      if(isFull()) {
         System.out.println("Queue is full!");
      } else {
         arr[++currentSize] = data;
      }
   }
   
   public int dequeue() {
      int temp = arr[0];
      if(!isEmpty()) {
         for(int i = 0; i < size()-1; i++) {
            arr[i] = arr[i+1];
         }
         currentSize--;
      }
      return temp;
   }
//...

Other implementation:

public class Queue {
    private int front, rear, size;
    private int capacity;
    private int[] array;

    public Queue(int capacity) {
        this.capacity = capacity;
        this.front = this.size = 0;
        this.rear = capacity - 1;
        this.array = new int[this.capacity];
    }

    // Method to add an element to the queue
    public void enqueue(int item) {
        if (isFull()) {
            System.out.println("Queue is full, cannot enqueue");
            return;
        }
        this.rear = (this.rear + 1) % this.capacity;
        this.array[this.rear] = item;
        this.size++;
        System.out.println(item + " enqueued to queue");
    }

    // Method to remove an element from the queue
    public int dequeue() {
        if (isEmpty()) {
            System.out.println("Queue is empty, cannot dequeue");
            return Integer.MIN_VALUE;
        }
        int item = this.array[this.front];
        this.front = (this.front + 1) % this.capacity;
        this.size--;
        return item;
    }
//...

Is my queue implementation effective? I often see other implementations like the second block of code I sent, but it seems confusing to me. Should I stick to my own implementation, or is it better to follow the second block of code?

[keen hearth]

The second example is a "circular buffer". The Wikipedia page has a pretty nice explanation: https://en.wikipedia.org/wiki/Circular_buffer

The first example is inefficient, because every time you get an element from the queue, you have to shift all the other elements over one-by-one. So the time it takes to get an element from the queue is proportional to the number of elements there are currently in the queue.

With a circular buffer, the time it takes to get an element from the front of the queue does not depend on the number of items currently in the queue.

[fiery cosmos]

class Queue
{
  private int maxSize;
  private long[] queArray;
  private int front;
  private int rear;
  private int nItems;
  
  public Queue(int s) // constructor
  {
    maxSize = s;
    queArray = new long[maxSize];
    front = 0;
    rear = -1;
    nItems = 0;
  }
  
  public void insert(long j) // put item at rear of queue
  {
    if(rear == maxSize-1) // deal with wraparound
      rear = -1;
    queArray[++rear] = j; // increment rear and insert
    nItems++; // one more item
  }
  
  public long remove() // take item from front of queue
  {
    long temp = queArray[front++]; // get value and incr front
    if(front == maxSize) // deal with wraparound
      front = 0;
    nItems--; // one less item
    return temp;
  }
//...

How about this? Do you think this is more effective than the 2nd block of code I sent before this?

[robust bolt]

Hey all. I was trying to find out a multistructured file's last 2 actually unknown fields. This is basically impossible for me because I am not a wise reverse engineer who spends 25 hours a day splitting a huge chunk of bytes into an actual structure. I don't even know how that one person who did it managed to actually do it. When I asked, he said that he just read a lot of documentation. I know he is also very very smart as well.

Anyway, so, I may not be smart and wise like him but we are so close to actually finding this structure that I want to do my best: getting help lol

So, the structure is actually here: https://www.3dbrew.org/wiki/Nintendo_Video#File_format
I have made myself a parser and builder using python Construct library. I can extract many information from the file and have a collection of all the unknown fields and the associated file names.

When I was editing a file which was supposed to be at box 3 (controlled by the unknown value in metadata section: https://www.3dbrew.org/wiki/Nintendo_Video#Metadata) the file moved to box 4. Normally this should not have happened without me changing that unknown value in metadata section. So, maybe it does more things than storing box placement... I merely changed video data without changing video size (yes, I truncated to match) which means what exactly? I also swapped values with other files, one got successfully changed to intended box while the other stayed in the same box... Weird.

Finally, we have the unknown value in interactive links' structure. I don't know how it works at all. Never played with it due to me naming it wrongly and then forgetting about it.

SO, I have this that extracts some data. What else do you propose I do? ChatGPT got so terrible it can't help me with new ideas, just repeats my words.

 data[file] = {
                "unknown2_idk":eb(structure["mv"]["unknown2_idk"]),
                # unknown3_idk must have been "unknown4_idk" actually...
                "unknown4_idk(s)":[eb(ilink["unknown3_idk"]) for ilink in structure["ilinks"]],
                "video_len":structure["mv"]["video_len"],
                "num_ilinks":structure["hdr"]["num_ilinks"]
                }

eb is just base64.b64encode and structure is a dict of this file. mv.unknown2_idk is the unknown value in metadata section and unknown4_idk(s) are values in every interactive link's unknown value. i dont know what kind of statistics i can apply to get some output i can use to predict something out. please help me out.

note: there are 4 boxes to place a video in the app but there is a chance that there may be 9-10 boxes the file supports or maybe even more? idk what to do fr.

[fiery cosmos]

Given a string with lowercase letters only, if you are allowed to replace no more than ‘k’ letters with any letter, find the length of the longest substring having the same letters after replacement.

Example 1:

Input: String="aabccbb", k=2
Output: 5
Explanation: Replace the two 'c' with 'b' to have a longest repeating substring "bbbbb".

Example 2:

Input: String="abbcb", k=1
Output: 4
Explanation: Replace the 'c' with 'b' to have a longest repeating substring "bbbb".

Example 3:

Input: String="abccde", k=1
Output: 3
Explanation: Replace the 'b' or 'd' with 'c' to have the longest repeating substring "ccc".

I solve that with this code

def find_length(str1, k):
    max_length = 0
    n = len(str1)
    for window_start, current_character in enumerate(str1):
        num_of_occurences_of_current_character = 1
        aux_k = k
        window_end = window_start + 1
        while window_end < n:
            if current_character != str1[window_end]:
                aux_k -= 1
            if aux_k == -1 and current_character != str1[window_end]:
                break
            num_of_occurences_of_current_character += 1
            window_end += 1
        max_length = max(num_of_occurences_of_current_character, max_length)          
    return max_length

Can I make my solution somehow better?

[haughty mountain]

you can pretty easily do this in O(alphabet_size * n) rather than O(n²) which I assume that is

it's probably possible to do better though

[fiery cosmos]

Can you explain how?

Like somehow with hash maps?

[haughty mountain]

no

just sliding window for each unique character in the string

[fiery cosmos]

I will try to think about that tomorrow, currently have other duties

Thanks

[haughty mountain]

basically solve the same problem but with only two possible values

abbcb k=1

solve for a: 10000 k=1
solve for b: 01101 k=1
solve for c: 00010 k=1

just my first idea of improvements

you can probably do better

[languid thistle]

hey, what's the correct way to deal with the end of a stack when you're popping from a list?

https://softwareengineering.stackexchange.com/questions/189222/are-exceptions-as-control-flow-considered-a-serious-antipattern-if-so-why

I've some doubts about using exceptions, but I also find it really unwieldly in recursive functions to pass indices and increment them as I go

[haughty mountain]

not really a ds&a topic

[rich apex]

Is the depth of a successor or predecessor of the root node the height of a unbalanced BST?

[languid thistle]

where would you put it?

it really only comes up in the fine grain of for example solving a leetcode

[haughty mountain]

exceptions as control flow is a quite general topic

[languid thistle]

I think, technically, an algorithm would include logic like checking for the end of a list. And in such a context is where the operation would occur.

that's fine, I'm not asking about exceptions.

i'm asking about the right way to deal with processing a list as a stack and the base case of emptiness

[haughty mountain]

your link is about exactly that

[languid thistle]

are you unable to understand context?

[languid thistle]

read this

[haughty mountain]

why did you post the link if it's not relevant?

[languid thistle]

you sir lol

it is relevant. It presents an implementation, and a discussion about in what cases it would make sense.

is it exactly my question?

well I dunno

it'd take a huge brain to read this

[languid thistle]

this here

and understand it as anythign other than

the link pretty close to it

[haughty mountain]

I wouldn't blindly pop from a list and rely on exceptions

if it's easy to check the thing, just use an if

if checking is hard, just try and deal with the exception

[rich apex]

anyone?

[haughty mountain]

e.g. "is this convertible to int?"

[languid thistle]

kind of a confusing one there.

in one sense, the root node doesn't have a predecessor

in the recursive sense, all nodes are roots

or hang on, you're talking not of children but of what, traversal-lateral nodes?

[haughty mountain]

this judgement is a more general question, python tends to be more ok with exceptions as control flow than many other languages

[rich apex]

If I want to find the height of the tree, then finding the depth of successor or predecessor of the root node and returning the maximum of them will be height right?

[languid thistle]

find the depth of the successor and predecessor, yeah, that's correct

[rich apex]

Will it be correct?, either the depth of the successor or the predecessor will be the height of the tree

[languid thistle]

yes

that's how you get the height of the tree. Usually do it recursively.

[rich apex]

The tree is not balanced

then would the answer change?

[languid thistle]

doesn't need to be

no.

you compare in the recursive call

[rich apex]

Cause I asked chatgpt and it said the following:

If the Binary Search Tree (BST) is not balanced, meaning it has a skewed or unbalanced structure, the depth of either the successor or the predecessor can still be equal to the height of the tree, but this isn't always the case.

In an unbalanced BST, one subtree of a node can be significantly deeper than the other subtree. In this situation, when you find the successor or predecessor, you might need to traverse the deep subtree, which can make the depth of the successor or predecessor significantly different from the overall height of the tree.

For example, if you have a skewed BST (either left-skewed or right-skewed), the depth of the successor or predecessor can be close to the height of the tree because you are essentially traversing the longest path from the root to find them. However, it's possible that the depth of the successor or predecessor could be much smaller if the skew is not extreme and you don't need to traverse the full depth of the tree to reach them.

In the worst-case scenario, where the BST is highly unbalanced, finding the successor or predecessor could require traversing the entire height of the tree, which would be equal to the height of the tree. But in other cases, it might be closer to the average depth of nodes in the tree.

So, the depth of the successor or predecessor in an unbalanced BST can vary, but in the worst case, it's still equal to the height of the tree.

And I'm confused

[languid thistle]

like depth = max(_getLeftDepth, _getRightDepth)

[languid thistle]

why are you asking chatgpt?

[languid thistle]

it's a BST. Go look at a graph of one.

that should answer most of your questions.

[rich apex]

just thought it might be a generic question and asked chat gpt first

Is what chatgpt saying correct?

[languid thistle]

it is a very generic question, chatgpt is just not good at helping you get fundamentals

[rich apex]

So the depth of the successor or the predecessor of the root node will always be the height of the BST, no matter balenced or unbalanced?

[languid thistle]

I don't think it is. How would any successor or predecessor of the root ( the only node by which you'd care to assess direct neighbors for height of the tree) be equal to the height of the tree?

it just sounds like idiocy man. Also, "successor" and "predecessor" are not good terms to mess with unless you in context define if you are talking about a depth-first search or a breadth-first search

[languid thistle]

no.

[rich apex]

successor is the minimum value in the right subtree, and predecessor is the maximum value in the left subtree

[languid thistle]

I was incorrect earlier

I was confused because it is so hard to read that

[rich apex]

Can you tell me why?

any examples?

[languid thistle]

just draw a tree dude

hang on are you defining depth as being 1 at the child? cause then yes. E.

I acknowledge my own bias here, I had that explanation

and I just thought wow that's terrible. The biggest issue is that the deep subtree traversal deal is absolutely wrong.

"In an unbalanced BST, one subtree of a node can be significantly deeper than the other subtree. In this situation, when you find the successor or predecessor, you might need to traverse the deep subtree, which can make the depth of the successor or predecessor significantly different from the overall height of the tree." this is beyond ass

it is just wrong

[rich apex]

Here's what I wrote for depth and height:

    def depth(self, node: Node) -> int:
        """
        The depth of a node is the number of edges present in path from the root node of a tree to that node
        """
        currentNode = self.root
        currentDepth = 0

        while currentNode:
            # Found the node
            if node.value == currentNode.value:
                return currentDepth
            # Go left
            elif node.value <= currentNode.value:
                currentNode = currentNode.left
            # Go right
            else:
                currentNode = currentNode.right
            # The node is further down
            currentDepth += 1

        # Node doesn't exist
        return -1

    def height(self, node: Node) -> int:
        """
        The height of a node is the number of edges present in the longest path connecting that node to a leaf node.
        """
        if node is None:
            return -1

        # Get the depth of the predecessor of node `node`
        leftHeight = self.depth(self.predecessor(node))
        # Get the depth of the successor of node `node`
        rightHeight = self.depth(self.successor(node))

        # Return the maximum depth
        return max(leftHeight, rightHeight)

[languid thistle]

like to clarify: if you have an unbalanced BST, and one subtree is way deeper than the others, that tree will define the height of the tree

[rich apex]

is my code correct?

[rich apex]

yeah so either the depth of predecessor or successor depending on the side its skewed

[languid thistle]

that's a search for a specific value, which is passed as a part of a node. Does your tree allow duplicates?

[rich apex]

nope

[haughty mountain]

depth and height are different things

depth is measured relative to the root

height is measured relative to the leaves

[languid thistle]

depth looks good to me

[rich apex]

How would you find the height of the tree

[haughty mountain]

max path length to any leaf

[rich apex]

but aren't predecessor or successor leaves??

[haughty mountain]

you can easily find it recursively, the height of a node is related to the height of its children

[haughty mountain]

depends? not generally

[rich apex]

when would it not be?

[haughty mountain]

leaves are nodes with no children

when the node has children

[agile sundial]

when the predecessor has a left child

or the successor has a right child

[rich apex]

oh

[haughty mountain]

can't both have both?

[rich apex]

then it wont be a predecessor or a successor I think

[haughty mountain]

oh, I'm not used to the BST terminology then

it's something that's hardly ever actually used

[rich apex]

well then, I need to find the height recursively, got it, thanks guys

[haughty mountain]

finding height and depth has nothing to do with BSTs in particular

it's a general thing for trees

[rich apex]

oh I was asking only for unbalanced BST

[haughty mountain]

I don't see how that matters, it's a tree

depth and height doesn't care about what the tree represents

[rich apex]

ok got it

[cunning bison]

Does formal languages and formal grammar have any practical application at all?

Because right now it is second on the short list of useless CS concepts behind functional programming

Which conveniently is taught in the same class

[raw mortar]

bruh

bass discord

[slender sandal]

Otherwise you'd have to learn dialects. JSON has barely any dialects and I bet it is used a lot in web requests. SQL has several dialects and it is only used at the back-end so the mindset is that you can do whatever you want there

Python has a formal grammar

[tulip bone]

Algorithm A uses 10nlogn operations, while algorithm B uses n^2 operations. Determine the value of c and n0, such that A is better than B for n ≥ n0.

This is how I had gone about the solution:

Since, A is better than B; we can say that the time complexity of A is less than that of B for n>nO such that A is the lower bound of B. The equation that follows is given by:

10nlogn < cn^2
10logn<cn; n<0 (invalid)
logn<cn/10
Now we have two unknowns

I don’t know how to continue further

[lean walrus]

just take some stupid large n0
like 10^10 * c^(+1 if c > 1 else -1)

[tulip bone]

But we need the closest lower bound

[narrow mica]

You'll have an infinite set of solutions that all look horrible though

[viral frigate]

Hi can someone explain unionfind to me like im five years old? I have no clue how this find is supposed to work

class UF:
    def __init__(self, N):
        self.parents = list(range(N))
    def union(self, child, parent):
        self.parents[self.find(child)] = self.find(parent)
    def find(self, x):
        if x != self.parents[x]:
            self.parents[x] = self.find(self.parents[x])
        return self.parents[x]```

[stable bough]

Sure 👌, let's imagine a scenario where you're at a big family reunion. You have a lot of relatives there, but you don't know everyone. You want to find out who is the oldest ancestor of a particular relative. This is similar to what the find function does in the Union-Find data structure.

Here's how it works:

1. Initialization (__init__ method): When the family reunion starts, everyone is considered their own oldest ancestor. This is like the initialization step where each element is in its own set.

2. Union (union method): As the reunion goes on, you start learning about relationships between people. For example, you learn that person A is the child of person B. So, you update your records to show that person B is the oldest known ancestor of person A. This is similar to the union operation, which merges two sets.

3. Find (find method): Now, if you want to find out who is the oldest known ancestor of person A, you start by asking person A who their parent is, then you ask that person who their parent is, and so on, until you find someone who is their own parent (i.e., they don't have a known parent at the reunion). This person is the oldest known ancestor of person A. This is what the find operation does.

In your code, the find function works as follows:

• It takes an element x as input.
• If x is not its own parent (i.e., x != self.parents[x]), it means x has a known parent at the reunion. So, we recursively call find on x's parent (self.parents[x]). This is like asking x's parent who their parent is.
• We also use path compression here for efficiency. By setting self.parents[x] = self.find(self.parents[x]), we are saying that x's parent is not just x's immediate parent, but x's oldest known ancestor. This speeds up future find operations.
• If x is its own parent, it means x is the oldest known ancestor of itself, so we return x.

I hope this helps! 😊

[narrow mica]

Are you sure they didn't give you c? If not... well, here you go:

Given c, choose n > that monstrosity, where W is the lambert W function
Won't work for bigger c though because W isn't defined for x < -1

[tulip bone]

Ou right

I asked mu professor

She said we can suppose c

[tulip bone]

Still thanks for this

i=0
while i * i < n
// perform 5 basic operations
//i= i + 1
end while

How do i find its big O notation?

[narrow mica]

O(√n)

i * i < n is equivalent to i < sqrt(n)

[tulip bone]

sum=0, i=0
while i < n
j=0
while j < n sum=0
sum + i * j
j= j + 1
end while
i=i + 1
end while

[tulip bone]

Then this will be O(n2)?

Thanks a lot ❤️

[runic birch]

I have one row from 1 - N and a second row which consists of shuffled bumpers from 1 - N. Between those rows are lines always connecting the same numbers. How to find the maximum number of connections which can be made with least amount of crosses?

I have thought of a solution which recursively tries to and fails until it finds the maximum number but it seems rather slow.

[lean walrus]

i dont think it is solvable in basic functions
also, it is not stated in your task, your task requires only some n0, not smallest n0

[tulip bone]

Yea i understand now thanks

Can i ask digital logic design questions here?

I can’t find a dedicated channel since

[lean walrus]

sure

[tulip bone]

I solved it this way but the problem is I’m getting only one solution

Even using k maps

Ig ive made my initial equation incorrectly

Nvm

Found it

[haughty mountain]

@regal spoke I can see how this problem could be reduced to something like MAXSAT, but do you know if there is something nicer off the top of your head. Seems there might be enough structure for something nicer

[regal spoke]

I'm a bit confused by the question. "How to find the maximum number of connections which can be made with least amount of crosses?"

Do you mean no crosses?

The " least amount of crosses" is 0, right?

[regal spoke]

If I understand the problem correctly, then I think there is a relatively simple DP solution.

The naive implementation running in something like O(n^2)

It is maybe possible to get it down to O(n)

The idea is that initially you've got 2 choices, either you match the upper 1

Or you don't match the upper 1

In the first case you are left with

[runic birch]

Hey! Wait i can explain the problem if you want

[regal spoke]

In the 2nd case you are left with

[runic birch]

I have found out that you can topologically sort the graph. But so far thats quite unreliable

[regal spoke]

I still wonder what you mean by "How to find the maximum number of connections which can be made with least amount of crosses?"

[runic birch]

But that would be O(n)

[runic birch]

I will explain

You have two rows:

Top one which goes from 1 - N.
Bottom one which is shuffled first.

You connect elements of same value. Meaning if in top one is one. You connect it with 1 in bottom.

[runic birch]

Now look at the image. That will help. Bold ones are solution, dotten ones are not. We pick bold ones so theres the largest possible ammont. But no bold arrows can overlap.

[regal spoke]

The numbers at the bottom of the image do not really agree with your description, but ok

[runic birch]

meaning that theoretically best possible solution is just row of paralel arrows

[runic birch]

wym?

Oh i see

I didnt notice that Lol. Thatsw okay. You get the second row as vector. The numbers would otherwise match

[regal spoke]

So no overlap ("crossing") is allowed in the solution?

[runic birch]

yes

Example input

[regal spoke]

Then you should have said "No crosses" instead of "least amount of crosses"

[runic birch]

I now get the confusion sorry for that.

[regal spoke]

Anyways, the natural solution to this problem is DP

[runic birch]

agreeed

[runic birch]

wym?

[regal spoke]

Do you know what DP is?

[runic birch]

Nope.

[regal spoke]

DP is an abreviation for dynamic programming.

It is a common type of algorithm

[runic birch]

Oh of course

I have used it and didnt really find good solution

perhaps you are better at it

at least not O(N) solution

[regal spoke]

I tried to explain the idea for a simple O(n^2) DP algorithm here #algos-and-data-structs message

I think this is a good starting point, even if you want a O(n) algorithm

[runic birch]

Dont really understand it.

[regal spoke]

Think about that first 1 in the upper left

Either you will include its edge in the solution, or you wont

right?

[runic birch]

yep

[regal spoke]

Lets assume now that you include it

[runic birch]

it simplifies the porblem

[regal spoke]

Yes

[runic birch]

problem*

I have thought of that

[regal spoke]

Now you are left with the problem

[runic birch]

But for input of N = 300000 i assumed its too slow. But i didnt really optimise it or even implemented

[regal spoke]

It is too slow for N = 300000, yes

But it is a good starting point

[runic birch]

Indeed

[haughty mountain]

fleshing out a n² solution you might find stuff you can improve

[runic birch]

Well sure. I guess i will need to do some n^2 solution anyway to verify the more unusual ones

For example my current one uses Topological sort. Which is for some inputs okay and others it fails. But when N = 1000 i cant really confirm that its right by hand

For N <= 10 i can but otherwise its maddness

[regal spoke]

Don't just guess algorithms

Try to prove that they work first

Btw I think I see the O(n) solution now

[runic birch]

Thats the ideal case. Getting it bellow O(n) is too ambitious i think

[regal spoke]

Obviously going below O(n) is impossible

[runic birch]

Yeah with this problem for sure

Anyway whats your solution candidate?

[regal spoke]

It is DP, where the state depends only on the last edge taken

[runic birch]

yes. Agreed

[stiff quartz]

Hello, has anyone done today's codeforces' contest?
My code passes with PyPy (for Problem C https://codeforces.com/contest/1895/problem/C) but not with Python so I was wondering if I got lucky or if I genuinely got it down to a O(n) complexity which I was not entirely sure about, my code is:

n_tickets: int = get_int()  # Get the number of tickets
a: list[str] = get_string().split(" ")  # Get the string of tickets and split into a list

n_lucky_tickets: int = 0  # Initialize the count of lucky tickets

# list_hashmaps_totals[i][j] = number of tickets with i+1 elements and sum j
list_hashmaps_totals: list[dict[int, int]] = [
    defaultdict(int),
    defaultdict(int),
    defaultdict(int),
    defaultdict(int),
    defaultdict(int)
]
for ticket_idx in range(len(a)):
    for i in range(5):
        if len(a[ticket_idx]) == i + 1:
            list_hashmaps_totals[i][sum(int(digit) for digit in a[ticket_idx])] += 1

for ticket_idx in range(len(a)):
    sums = [sum(int(digit) for digit in a[ticket_idx][:i]) for i in range(1, len(a[ticket_idx]) + 1)]  # prefix sums
    sums_ = [sum(int(digit) for digit in a[ticket_idx][len(a[ticket_idx]) - i:]) for i in range(1, len(a[ticket_idx]) + 1)]  # suffix sums
    for total_length in range(len(a[ticket_idx]) + 1, len(a[ticket_idx]) * 2 + 1):
        if total_length % 2 == 0:
            sum_missing_on_right: int = (
                sums[total_length // 2 - 1] - (sums[-1] - sums[total_length // 2 - 1])
            )
            count_missing_on_right: int = total_length - len(a[ticket_idx]) - 1
            n_lucky_tickets += list_hashmaps_totals[
                count_missing_on_right
                ][
                sum_missing_on_right
            ]
            if count_missing_on_right + 1 != len(a[ticket_idx]):
                # so that we do not count it twice (if we need 4 elements and we had 4 elements, putting them on the left or on the right will be counted twice)
                sum_missing_on_left: int = (
                    sums_[total_length // 2 - 1] - (sums_[-1] - sums_[total_length // 2 - 1])
                )
                count_missing_on_left: int = total_length - len(a[ticket_idx]) - 1
                n_lucky_tickets += list_hashmaps_totals[
                    count_missing_on_left
                    ][
                    sum_missing_on_left
                ]

# Smaller then larger
print(n_lucky_tickets)

[regal spoke]

You shouldn't describe the time complexity of your algorithm purely in terms of n

I think your code runs fast because the number of different possible sums of 5 digits numbers is small

The biggest sum possible for a 5 digit number is 9+9+9+9+9 = 5 * 9 = 45

So your list_hashmaps_totals is kinda tiny

My guess is that your time complexity is something like n * 9 * (5 + 4 + 3 + 2 + 1) = 135 * n

In my opinion, an easier solution would be to first decide on the length of the first part and second part of the lucky ticket

[stiff quartz]

It is five elements anyway right?

It's just there are five dictionaries in it

[regal spoke]

meant that the dictionaries in it are kind of tiny in size

[stiff quartz]

does it matter how big the dictionaries are? apart from building them

[regal spoke]

I havent carefully read you code, so maybe it wont matter

[stiff quartz]

Yeah fair enough, I think the problem is that it's O(kn) with k around 100

thanks!

[stiff quartz]

So that'd probably be O(25n) and faster

[regal spoke]

https://codeforces.com/contest/1895/submission/231215276

Here is the solution

[regal spoke]

Actually it is possible to make it run in O(5 * n)

[stiff quartz]

sum(num1[:mid1]) - sum(num1[mid1:]) this is sum to the mid (or a if the mid is too big meaning we joining a little ticket with a big one)

But then how do we verify they have matching sums?

if we are joining 5 with 555, mid is 2 and in sum_num1 we increment 5

[regal spoke]

Take this as an example, the lucky ticket consisting of 123 and 44411

It is lucky because

1 + 2 + 3 + 4 = 4 + 4 + 1 + 1
Which is the same condition as

1 + 2 + 3 = -4 + 4 + 1 + 1

[stiff quartz]

ahhhh

-4 +4 +4 +1 +1 but yess

i understand

[regal spoke]

Here is a shorter solution https://codeforces.com/contest/1895/submission/231217918

[stiff quartz]

yeah i mean harder to digest

[regal spoke]

yep

[stiff quartz]

so it's actually O(50n)

but enough for Python to pass (PyPy always passes ofc)

[stiff quartz]

because we do for _ in A twice

and the last for loop is negligible anyway

[regal spoke]

https://codeforces.com/contest/1895/submission/231229136 Here is a faster solution
https://codeforces.com/contest/1895/submission/231230346 This is even faster

It runs in time (number of digits in the input) + 5^3 * 9

It also doesn't use any hashtables at all

[regal spoke]

It runs faster than any other Python submission

[solemn moss]

I will lose my blue color again for this round :D

[olive badge]

hey guys how's it going

[olive badge]

did you participate today in the div2?

[regal spoke]

nope

[olive badge]

bro, all problems were about maths

that's not funny haha

[regal spoke]

Dunno if I would call C a maths problem

[runic birch]

@regal spoke This is the final sololution to the problem we talked about. It uses LIS and for N = 300000 works instantly:

idk how to upload code lol

@regal spoke https://paste.pythondiscord.com/FUQA

[narrow mica]

```py
code
```

Though that code looks really long so it probably won't be sent anway

[runic birch]

Hey thankts to you I got the code!

[runic birch]

Yeah

I used a solution recomened by the server

[narrow mica]

For c++ replace py with cpp or smthn

[runic birch]

If you want the code I can also provide .in to test it. WOrks wonderfully

I just had to optimise it a fair bit to work for large Ns but for smaller ones it worked out of the box

Well i will soon move on the next exercise. Hopefully it will go as well as this one. Otherwise I will have to pull out allnighter tommorow 🙂

[fiery cosmos]

Help me learn

[haughty mountain]

either cpp or cc works I think

cc```cc
template<typename T>

cpp```cpp
template<typename T>

cxx```cxx
template<typename T>

any of these it seems

and these are the common file endings

hh```hh
template<typename T>

hpp```hpp
template<typename T>

hxx```hxx
template<typename T>

and the header variants apparently

[keen hearth]

Hey 👋 Your best bet would be to check out some of the resources linked in the pinned messages. If you get stuck on anything, feel free to ask for assistance in this channel.

[smoky raptor]

Hello world, i am a beginner at Python development but already building my first program.

I need to build one calculator that shows to the user how long it will be to achieve the amount of money he wants, based on the amount that he can save monthly.

I have a doubt on how to run Django with my Python code. Need to show this to the teacher.

Sorry if i am not clear, my English is from Brazil.

Kind regards

[fiery cosmos]

Kk

[tulip bone]

Ig there’s an error in the indentation

[haughty mountain]

using tables?

[tulip bone]

😦 i dunno what they mean by that

[haughty mountain]

also that code is terrible wtf

it's technically valid with that indentation but so so weird

[tulip bone]

Lol
Isnt that else statement supposed to be inside the for branch?

[haughty mountain]

presumably, but even then it's weirdly written code

[tulip bone]

Probably they tried to make it more complex

[haughty mountain]

it's just kinda wrong

I'm assuming this is what they mean

largest = A[0]
smallest = A[0]
for i in range(1, n, 1):
    if A[i] > largest:
        largest = A[i]
    elif A[i] < smallest:
        smallest = A[i]

[tulip bone]

It doesn’t work the way its supposed to?

Yes thats what i thought

[haughty mountain]

but this is technically valid code, even though is doesn't do anything sensible with smallest

largest = A[0]
smallest = A[0]
for i in range(1, n, 1):
    if A[i] > largest:
        largest = A[i]
else:
    if A[i] < smallest:
        smallest = A[i]

I guess regardless it doesn't matter for the time complexity

but that code is bad

talking about a "worst case" here is also very silly

[tulip bone]

Okay so for the worst case, the list passed must be in ascending order?

[tulip bone]

Lol but we gotta do the assignment :((

[haughty mountain]

it doesn't matter

that's why it's silly

[tulip bone]

Huh? But if it’s in ascending order, the if statement would be true for each iteration na?

[haughty mountain]

you're still doing the comparison

[tulip bone]

So I shouldn’t?

[haughty mountain]

huh?

I'm saying regardless if the if triggers or not the overall time complexity is the same

[narrow mica]

The thing is, no matter what that list looks like, you're always iterating through the entirety of it; That's what fiery festive fenix means by "not mattering"

[haughty mountain]

sure you do more work, but not asymptotically worse

[tulip bone]

Umm i mean that’s why it would be the worst case since an extra code statement would have to get executed each time the condition is true

[haughty mountain]

doesn't matter for the asymptotics

[tulip bone]

Oof

[narrow mica]

Sure the actual run time might be worse, but time complexity doesn't care about that

[haughty mountain]

the difference is basically just "do I do 1 or 2 things in the loop"

n or 2n total

[narrow mica]

Both O(100n) and O(10n) simplify down to O(n). You can roughly think of them as "doing 100 things in a loop" vs "doing 10 things in a loop"

[haughty mountain]

asymptotics doesn't care

both are O(n)

[tulip bone]

Okay so what I understand is that no matter how the list is ordered, I’ll have to run through the loop for every element
The statement inside the if is of constant complexity hence its execution does not add any big difference to the overall time complexity

Correct?

Thanks a alot guys

[narrow mica]

It'd be a different story if your function looked like

def function():
    if condition:
        very_expensive_function()
    else:
        very_simple_function()

[haughty mountain]

yeah

or that in a loop

but in this case either branch is just a constant number of operations

e.g. if the code was something like this

s = 0
for i in range(n):
  if cond(i):
    for j in range(i):
      s += 1

whether we take the branch or not matters

[tulip bone]

Ookay

Ig it has something to do with the table thing

I dunno maybe they want us to mention the primitive operations in each line

Add them and then find the complexity

[haughty mountain]

idk maybe

[tulip bone]

Yea because then the worst case would be n2

[haughty mountain]

doing it that way is just annoying for no good reason

[tulip bone]

Okay thanku

[tulip bone]

For part c, g(n) would be O(f(n)) right?

Or the opposite?

[lament perch]

pls help

can someone recommend an course, book or smth for learning algo

[fierce shore]

Hey you guys

I would like to learn problem solving with programming but I find it a quite complicated

Because if it's not too easy, it's too hard and my mind gets like fhasf dlkjfasdjcjcms

[fierce shore]

but what are you reffering about?

Python, there are thousands on YouTube, just pick one

[lament perch]

yeah nvm

xD

but thank you

[fierce shore]

Or Idk, get something with pygame for example

I made these two guys with tutorials

They are a quite bugged but it doesn't matter

The idea is about learning and making mistakes

It's kinda funny after a time

[livid helm]

can I not have these in the same line

when looking to put a new node in between 2 nodes.

[lean walrus]

# 0
node = Node(value, curr)
prev._next = node
self._count += 1

# 1
prev._next = Node(value, curr)
self._count += 1

# 2
prev._next, self._count = Node(value, curr), self._count + 1

[livid helm]

thank you so much

i like what u did in #2

ill prob use #1 for less overall typing xD

[haughty mountain]

don't do 2 for readability reasons, pls

[dim seal]

can someone help me with a math + coding problem

[modern gulch]

Depends on the problem. Ask away

[dim seal]

cards, and on top of each card are 4 (non-negative) integers: a, b, c, and d, laid out like this:

a is at the top left corner
b is at the bottom left corner, c is at the middle, d is at the bottom right corner

Here is an example card (2nd card in sample input 1):

4 is at the top left corner
9 is at the bottom left corner, 1 is at the middle, 2 is at the bottom right corner

Each card has its own values of a, b, c and d
. Now, Evirir will choose m cards, and put them down like this in any order they want:

a and b are visible from the first m card until the nth m card and in the last card a, b, c, and d are all four visible.



After this, Evirir will gain points equal to the sum of all visible numbers. What is the maximum amount of points Evirir can gain if he chooses the m
cards and arrange them optimally?

 Input Format
Let ai, bi, ci, and di denote the values of a�, b�, c�, and d� on the i�-th card. The input will be formatted as follows:

n m
a1 b1 c1 d1
a2 b2 c2 d2
…
an bn cn dn

Constraints:

1≤m≤n≤200001≤�≤�≤20000.
0≤ai,bi,ci,di≤1090≤��,��,��,��≤109.
Output Format
Output a single integer, the maximum amount of points Evirir can gain.

Sample Input 1
5 3
3 5 6 6
4 9 1 2
1 2 3 4
2 2 9 8
8 10 2 3

Sample Output 1
52

Sample 1 Explanation
Evirir can put the 2nd, 5th, and 4th card from bottom to top as follows:

(a1 = 4 ) (a2 = 8) (a3 = 2 )
(b1 = 9 ) (b2 =10) (b3 = 2) (c3 = 9) (d3 = 8)

The sum of visible numbers is 52. It can be proven that this is the maximum amount of points Evirir can get.```

I really dont know what the sequence is since the next input contains multiple a + b values that are high

cards = []

for _ in range(n):
    a, b, c, d = map(int, input().split())
    cards.append((a, b, c, d))

# Sort the cards based on the maximum of a and b in descending order
cards.sort(key=lambda card: max(card[0], card[1]), reverse=True)

max_points = 0
sum_ab = 0

# Iterate through the first `m-1` cards and sum their a and b values
for i in range(m - 1):
    a, b, _, _ = cards[i]
    sum_ab += a + b

# Iterate through the remaining cards, considering their c and d values
for i in range(m - 1, n):
    a, b, c, d = cards[i]
    max_points = max(max_points, sum_ab + a + b + c + d)

print(max_points)```

This is a college assignment that i have to turn in by tommorow so i really need help rnn

[narrow mica]

Maybe not the correct solution, but what if you first picked the max a+b+c+d card to be the last card, then picked m-1 others with the highest a+b?

Actually I guess it wouldn't work for something like 1 1 9 9 and 6 6 6 6

[dim seal]

I did try that but it wouldnt give the correct output for a input like this:

7 10 7 6
6 5 3 10
9 2 9 4
4 10 3 6
8 7 5 3
7 8 5 7
9 5 4 6
9 2 4 7```

This input has multiple high a + b values so i believe the way its arrange isnt based on that

[dim seal]

I found out, that if the a + b value is high but the same value it can still be summed up 🤞

[narrow mica]

One thing, since all we may care about is a+b and a+b+c+d, you might as well make two values u=a+b, v=c+d, and just use that
Question now is basically maximize u1+u2+u3+u4+...+u(m-1)+um+v

[tulip bone]

?

[jolly mortar]

both, f(n) = Theta(g(n)) and vice versa

[runic birch]

I tried solving it with DFS and that didnt really work. It doesnt find the longest route possible all the time.

I have a start, destination and a 2D grid of size R x S. R x S can be as high as 700 x 700. Grid is consisting integers representing height of a certain point. I have to find the following path:

1. Start at start -> every new height has to be BIGGER than previous.
2. Finish in the end so that -> every new height has to be LOWER than previous.

Find LONGEST possible route. If same length pick one with highest height achieved.

[tulip bone]

But that would mean almost every part in this question could have a theta notation :((

[jolly mortar]

a b and c would be

[haughty mountain]

Just thinking out loud, thinking along the lines of, assuming I pick card i as my top card, what's the best m-1 other cards I can pick? Seems quite sensible

I guess dealing with 4 values here is completely not needed

[tulip bone]

Is this the correct way to do it?

Also, in part d, should i use the big O notation or the small O notation?

[haughty mountain]

Let me actually try implementing this, shouldn't be too hard

[tulip bone]

I meant slower than polynomial funcs*

[haughty mountain]

!e

import io
import sys


def solve() -> None:
    n, m = map(int, input().split())

    def read_card(s: str) -> tuple[int, int]:
        a, b, c, d = map(int, s.split())
        return a + b, c + d

    # cards = [[a, b, c, d], ...]
    # WLOG we can combine as left=a+b and right=c+d
    cards = [read_card(input()) for _ in range(n)]

    cards.sort(key=lambda x: x[0], reverse=True)

    # Let's assume we pick the top m cards by a+b
    sum_a = sum([x[0] for x in cards[:m]])

    # Now, consider picking each possible card to be the top card.
    res = 0

    # Case 1: The top card is among the top a+b cards.
    for i in range(m):
        _, right = cards[i]
        # Add in the missing right part of top card.
        res = max(res, sum_a + right)

    # Case 2: The top card is not among the top a+b cards.
    sum_a -= cards[m - 1][0]  # Unpick the mth card
    for i in range(m, n):
        left, right = cards[i]
        # Add in the values for the top card.
        res = max(res, sum_a + left + right)

    print(res)


def test_solve(inp: str, answer: int) -> None:
    """Just a helper function for testing purposes."""
    sys.stdin = io.StringIO(inp.strip())
    solve()
    sys.stdin = sys.__stdin__


test_solve(
    """
5 3
3 5 6 6
4 9 1 2
1 2 3 4
2 2 9 8
8 10 2 3
""",
    52,
)

[halcyon plank]

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

52

[haughty mountain]

Correctness is basically by construction

We try every possible top card, and pick the remaining top m-1 cards greedily, which is optimal

[haughty mountain]

So there are a few mistakes overall wrt inequalities, and I wouldn't set things up quite like this

So, to show both are Θ of each other you would (naively) need to show 4 things, O and Ω both ways

for the first one you would want to show all of these

8n - 2 <= c n   # 8n - 2 = O(n)
8n - 2 >= c n   # 8n - 2 = Ω(n)
n <= c(8n - 2)  # n = O(8n - 2)
n >= c(8n - 2)  # n = Ω(8n - 2)

note that the c is included in the expression

[haughty mountain]

in reality you don't need to show all 4

f(x) = Ω(g(x)) is equivalent to g(x) = O(f(x))

so you only need to show it one way

so these two would be enough

8n - 2 <= c n   # 8n - 2 = O(n)
8n - 2 >= c n   # 8n - 2 = Ω(n)

and they are easy to do

1. c = 8, n0 = 0
   8n - 2 <= 8n  for  n >= 0
2. c = 1, n0 = 1, done
   8n - 2 >= n  for  n >= 1

This is more about the general setup of what you need to show, include the c in the inequality (it's part of how the thing is defined)

So you might want to re-do with that setup

There were also some math mistakes, let me annotate your images...

[haughty mountain]

and the point for c) about looser inequalities

if you wanted to show

9n^2 <= 4n^2 + 7n
```showing

9n^2 <= 4n^2 + 7n^2

since

9n^2 <= 4n^2 + 7n <= 4n^2 + 7n^2

you want to show something sticter

rephrasing this with a c as I suggested

9n^2 <= c(4n^2 + 7n)
9n^2 <= 4c n^2        # stricter inequality, made large side smaller
9n^2 <= 12 n^2        # let c = 3
                      # done

similarly

9n^2 >= c(4n^2 + 7n)
9n^2 >= c(4n^2 + 7n^2) = 11c n^2  # stricter inequality, made small side larger
9n^2 >= 5.5n^2                    # pick c = 0.5
                                  # done

actually, I guess you did the right bounding technique but in the wrong case, huh?

[tulip bone]

Oh my gosh
My basics are all muddled up

[tulip bone]

Now i get most of the part

@haughty mountain thank you so soo much

Also, for the parts after c, i should use the small O or small omega notations instead right?

[haughty mountain]

no?

[tulip bone]

When do we exactly use them then?

[haughty mountain]

so O, Ω and Θ are basically the asymptotical versions of ≤, ≥ and =

e.g. f(x) = O(g(x)) means f(x) "is asymptotically ≤" g(x)

[tulip bone]

Mhm
And < and > for small o and small omega

[haughty mountain]

right

it's not that usual for me to see those, but they exist

[tulip bone]

Like here in part f, both the functions are different

And since g(x) > f(x) for n>=no then can i say that g(x) is o(f(x) )

Or should i use the big O notation

[haughty mountain]

up to you I guess

using the small versions is more precise, but it's pretty rare for me to see them

sometimes you see small o(1) in exponents for various reasons

which acts as basically adding some small ε (from what I remember)

[haughty mountain]

that inequality is the wrong way around I think

technically if you want to show g(x) = o(f(x))
you need to show that for all c > 0 there exists some x0 such that

• g(x) < c f(x) for x≥xo

like, even if you pick c to be some arbitrarily small constant, eventually f(x) dominates

tbh, when I think of these things I usually don't use the c, n0 definitions even though those are the definitions

I usually use the limit definitions since those are easier to just apply when I don't care about the specific c or n0

i.e. look at f(n)/g(n) as n → ∞

does it tend to zero, a positive constant, or infinity?

leaving some technicalities out:
zero means o
positive constant means Θ
infinity means ω

either zero or positive constant means O
either positive constant or infinity means Ω

i.e. the limit definitions here (minus the ~ one)

https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann–Landau_notations

[low compass]

Can someone please help me get this python script to work?

import requests
from bitcoinlib.transactions import *

Replace with a valid transaction hash

tx_hash = '9d2d91b764ba2559b098cdd30525e2160bb15c6e27d6869e7b121a9037d8bd86'

Fetch the raw transaction data from the blockchain.info API

response = requests.get(f'https://blockchain.info/rawtx/{tx_hash}?format=hex')

Parse the transaction data

mytrans = Transaction.parse_hex(response.text, strict=True, network='bitcoin')

Verify the transaction ID

txid_validity = mytrans.verify()

Print the result

print(txid_validity)

[haughty mountain]

not #algos-and-data-structs try #python-discussion or use the help system

[low compass]

Honestly man I tried that and no luck and when I posted the question on the help system it got removed

[tulip bone]

Okay so i’ll just check by applying the limit then in case of different functions

[tulip bone]

Mhm got it

[haughty mountain]

you can use that in general

but idk what's expected in your course

if they ask for explicit c and n0 then you'll need to go the more formal route

[tulip bone]

Yes my course expects us to use c and no for similar functions

Also thank you so muchh

[fiery cosmos]

is there any way to use node js with vsc on chromebook

[haughty mountain]

not #algos-and-data-structs and not even python related...

[modern walrus]

Lets say that there is a perfect binary tree with height h, and the binary tree is filled with consequtive numbers from 1

Example, with a h of 3 the tree will be

 .       7
    3       6
1     2   4    5

Now, i need to find parent of a given number eg: 4, then the result will be 6

How to get the parent?

Yeah, the numbers are in post order

What should be done 🤔

[lean walrus]

if it is filled from top to bottom - just //2

here you can kinda do the same

n = 4
h = 3
n0 = 2 ** h

n0 - (n0 - n) // 2

it reverser order, finds parent and reverses it back

[modern walrus]

Wow, I was working in this literally 4 hours now, how does this work?

[modern walrus]

Uhh no, sorry it isn't working

[modern walrus]

It's filled in post order

[lean walrus]

you probably need to slap +1 or -1 somewhere

[modern walrus]

Nah, + - 1 won't be able to do it

[regal spoke]

Is there are reason to why you are using post order? The standard order (bfs from the root) is so much nicer

With that order, you can do //2 to reach your parent (assuming you are using 1 indexing)

This is for example the order that python internally uses for heapq

[waxen summit]

Hello people

i'm searching for someone that can help me to write something in python

i'm really sucking in python programmation so ...

[modern gulch]

#python-discussion is where you should start.

[runic birch]

Can someone here help me with my implementation of DAG and toposort? Ive already done that but my algorithm fails to find longest possible path from given start to given end. Works only for super small inputs

[modern walrus]

It's the problem that was given to me

[regal spoke]

Are you able to manually change the format?

[modern walrus]

I saw the answer for this, but it's hard for understand it..

[modern walrus]

Actually, you don't even have time to build the tree, as it can go up to height of 30 (2^30 - 1 nodes) as it's a perfect tree

[regal spoke]

?

Is this a leetcoder problem?

[modern walrus]

Kinda yes

[modern walrus]

https://www.geeksforgeeks.org/find-parent-of-given-node-in-a-binary-tree-with-given-postorder-traversal/

This is the answer, but i would like to learn how is it working

[regal spoke]

Anyways, if you really want to work with postorder, then think about it like this

[post order right subtree] [post order left subtree] [root]

Using this you can recursive dig down until your node is the root

[sly scroll]

Hello - is there like a website where they visualize how each step of data structures and algorithms work?

Like for linked list, insert at ceratin index, they will show like a picture step of how it works kind of. I know there was one I was able to find in the past, lost in the shadow realm

[hybrid flicker]

Can someone explain how exactly am I supposed to use Floyd's cycle algorithm to solve the figure provided on the right page?

[modern walrus]

You can use pythontutor.com for this, it won't be crystal clear, but will help some more in visualising

[narrow mica]

There's a lot of visualization in here, though idk if it has the specific one you're looking for

[compact beacon]

<@&831776746206265384> can anyone of u people please open the last thread i closed, it would be this one

[oblique panther]

you can just open another thread with that content

[compact beacon]

i would like to open this one again if it is possible, i saw that moderators can open it again

i closed it but it was dumb to close it

[oblique panther]

Sorry, but we won't do that. If you have any questions, you can ask @fallow ginkgo

[compact beacon]

okay, thank you still

[charred gull]

Is there any article which gives some guidelines to build a data structure

[fiery cosmos]

Does the python code below solve the question? Can anyone help?

'''
You have a travel plan for the next N days (numbered from 1 to N). During day i, you need to drink exactly Pi mL of water. Alternatively, you can consume a vitamin pill instead, as a replacement for water on that day. Currently, you only have M mL of water and K vitamins. If there is not enough water to drink on a day and you run out of vitamins, then your travel plan ends. Determine the maximum number of days you can travel.

Input
The first line consists of three integers N M K (1 ≤ N ≤ 100; 0 ≤ M, K ≤ 100).
The next line consists of N integers Pi (1 ≤ Pi ≤ 100).

Output
Output a single integer representing the maximum number of days you can travel with the appropriate rations.
'''

def max_travel_plan(N, M, K, P):
    days = 0

    max_days = sorted(range(N), key=lambda x: -P[x])[:K]
    for i in range(N):
        if i in max_days:
            K -= 1
            days += 1  # use vitamin for highest days
        elif M >= P[i]:
            M -= P[i]
            days += 1  # water is used
        elif K > 0:  # worst scenario, no water and not max days
            K -= 1
            days += 1
            max_days = []
        else:
            break  # Not enough rations, quit
    return days

# Sample inputs and expected outputs
inputs_outputs = [
    ((7, 100, 2, [70, 30, 20, 40, 40, 50, 10]), 5),
    ((7, 100, 2, [70, 80, 20, 40, 40, 50, 10]), 5),
    ((7, 20, 2, [20, 20, 20, 40, 40, 50, 70]), 3),
    ((7, 100, 0, [20, 20, 20, 40, 40, 50, 70]), 4),
    ((7, 70, 1, [70, 30, 40, 20, 50, 10, 60]), 3),
    ((7, 0, 100, [100, 100, 100, 100, 100, 100, 100]), 7),
    ((7, 0, 0, [1, 1, 1, 1, 1, 1, 1,]), 0)
]

# Test the function with the provided sample inputs
results = [max_travel_plan(*inp) == out for inp, out in inputs_outputs]
all(results), results

[modern gulch]

I dunno, it looks like you pick the K max days, and allocate pills for those days, right?

But, what if you've run out of water before -and the local maximum was not the last day-?

I think the problem here is: You only use the pills either for a global maximum days, or when you've run out of water... but: what if your water consumption is something like:

90, 1, 1, 1, 1, 1, 1, 1, ... etc

You should use the vitamin pill for the local maximum visited so far (90), not for the day you ran out.

[native adder]

Anyone good with Iterative deepening A*

[brazen python]

wasnt there a trick to do this in one-line?

        def node_seen(self, node: int) -> bool:
            if node not in self.seen:
                self.seen.add(node)
                return False
            return True

perhaps I can just do return (node in self.seen, self.seen.add(node))[0]

[haughty mountain]

node in self.seen or self.seen.add(node) or False
```would work

but oh god why

!e

def f(b):
  return b or print('hi') or False

print(f(False))
print('---')
print(f(True))

[halcyon plank]

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

001 | hi
002 | False
003 | ---
004 | True

[haughty mountain]

essentially the same case as yours

[brazen python]

ok I see now how it works, I think I could do return node in self.seen or self.seen.add(node)

and do you like you did, or wrap it with bool()

thanks man

[kind mica]

Hello anyone can explain the problem ? And sorry if i'm not in the good channel.

[cyan basin]

Can't file

Open with

ciphertext.bin

Can't read

[kind mica]

ho ok

thank you

[cunning bison]

Idk who u are but okay lol

[cunning bison]

What are dialects? Or is this a joke

[raw mortar]

From the bass server

😔

We’ve talked before

I just change my profile a lot

[cunning bison]

Oh okay

[cunning bison]

sorry lol

What were u called before

[raw mortar]

Nezoomer

Smh

I always came in and asked what bass I should buy

[fringe gull]

let's say I want to save some bytes as a pure binary file. Deciding between structs or bytearray. Am I right to say that structs will allow me to save those bytes as they are, e.g. 100 bytes input will be a 100 byte file, while bytearray will have some additional size?

[slender sandal]

Are you saving the bytes or are you saving pickled Python objects? Bytes are bytes, no matter the form. If you store 100 bytes in a struct or a bytearray and you save either's bytes into a file, the file will have 100 bytes

[native adder]

Anyone good with Iterative deepening A*

[fringe gull]

saving the bytes. thanks for the clarification

[haughty mountain]

ask an actual question or you'll probably keep being ignored

[thorny tendon]

Hello, please tell me if it is good to do DSA in Python or not, I have researched and got to know that c++ has memory managment thing, and Python has not

[thorny tendon]

also to write complete logic from scratch in c++ is good whereas in Python, builtin functions are used. Please anyone, clear my doubts

[deft bay]

If I have 2 lists: that are [1,2,3,4,5] and [2,3,4,5,6], can I return a list that contains all of the differences, which is 25 results? Something like a dictionary?
1: -1,-2,-3,-4,-5
2: 0, -1,-2,-3,-4
3: 1,0,-1,-2,-3,
4: 2,1,0,-1,-2
5: 3,2,1,0,-1

[agile sundial]

i don't understand the question

[haughty mountain]

!e

A = [1,2,3,4,5]
B = [2,3,4,5,6]
for i in range(len(A)):
  print(*(f'{A[i] - B[j]:2}' for j in range(len(B))))

[halcyon plank]

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

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

[haughty mountain]

something like this?

[manic lotus]

my code wont do what i want . and i want to make the table print from the min num to the large num

[fiery cosmos]

hi all,

please see my ? in data science and AI: #data-science-and-ml message

[crude iris]

i've got an idea but I can't figure out how to code it... I want essentially to create all possible permutations of a list with replacement but no immediate repeats...
Examples:
List = (A, B, C, D)
Some Valid Permutations(length 3 for sanity)
(A,B,C) ; (A,B,A) ; (A,C,D) ; (D,C,A)
Invalid example:
(A,B,B)

[haughty mountain]

recursion is your friend for this kind of thing

and generator functions are nice

!e

def _impl(seq, n, res):
    if len(res) == n:
        yield tuple(res)
        return
    for x in seq:
        if not res or x != res[-1]:
            res.append(x)
            yield from _impl(seq, n, res)
            res.pop()

def picks_without_repeats(seq, n = None):
    if n is None:
        n = len(seq)
    return _impl(seq, n, [])



s = ['A', 'B', 'C', 'D']
for x in picks_without_repeats(s, 3):
    print(x)

[halcyon plank]

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

001 | ('A', 'B', 'A')
002 | ('A', 'B', 'C')
003 | ('A', 'B', 'D')
004 | ('A', 'C', 'A')
005 | ('A', 'C', 'B')
006 | ('A', 'C', 'D')
007 | ('A', 'D', 'A')
008 | ('A', 'D', 'B')
009 | ('A', 'D', 'C')
010 | ('B', 'A', 'B')
011 | ('B', 'A', 'C')
... (truncated - too many lines)

Full output: https://paste.pythondiscord.com/NWKCVAS3CCXCGK64C6IMKOW3AE

[haughty mountain]

the impl separation is just there to make the user facing interface nicer

[crude iris]

🤯 wow!

[fiery cosmos]

how

[fiery cosmos]

i'd love to know how this works

[haughty mountain]

it's nothing fancy

just recursively walk through all possibilities

adding picks to the res list, and then popping while backtracking

[fiery cosmos]

what does res stand for

[haughty mountain]

just result

this is probably going to be very much not helpful for understanding
['A', 'B', 'C']

[]
[A] # Can add A
  [A]
  # Can't add another A
  [A, B] # Can add B
    [A, B]
    [A, B, A] # Can add A
      yield that
    [A, B] # Backtrack
    # Can't add another B
    [A, B, C] # Can add C
      yield that
    [A, B] # Backtrack
  [A] # Backtrack
  [A, C] # Can add C
    ...basically same procedure as above
  [A] # Backtrack
[] # Backtrack
[B] # Can add B
  ...basically same procedure as above
[] # Backtrack
[C] # Can add B
  ...basically same procedure as above
[] # Backtrack
# Done

I guess the more helpful thing is to just to look at the recursive function

the base case is just "if I have generated the correct length, just yield that and return"

if you haven't reached the full length you can add another element, you just can't add the thing that was just before it, i.e.

    for x in seq:
        if not res or x != res[-1]:
            ...

if we are allowed to add x, we append, call the recursive thing, and then pop when we are done

just typical backtracking where we undo what we just did on the way out

[fiery cosmos]

you're a wizard

[haughty mountain]

this one if very much just "do the thing"

• maybe be a bit neat and do it with generators

an even simpler example 'generate all ways to pick n times from this set"

which is just removing the if

!e maybe let's do ABC and n=2

def _impl(seq, n, res):
    if len(res) == n:
        yield tuple(res)
        return
    for x in seq:
        res.append(x)
        yield from _impl(seq, n, res)
        res.pop()

def picks_without_repeats(seq, n = None):
    if n is None:
        n = len(seq)
    return _impl(seq, n, [])



s = ['A', 'B', 'C']
for x in picks_without_repeats(s, 2):
    print(x)

[halcyon plank]

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

001 | ('A', 'A')
002 | ('A', 'B')
003 | ('A', 'C')
004 | ('B', 'A')
005 | ('B', 'B')
006 | ('B', 'C')
007 | ('C', 'A')
008 | ('C', 'B')
009 | ('C', 'C')

[haughty mountain]

the original thing isn't really harder than this

and this thing you can hopefully try to wrap your head around

[fiery cosmos]

what is the yield from _impl(seq, n, res) all about

[haughty mountain]

to maybe remove the mystique of the generators

def picks_without_repeats(seq, n = None):
    if n is None:
        n = len(seq)

    results = []

    def _impl(seq, n, res):
        if len(res) == n:
            results.append(tuple(res))
            return
        for x in seq:
            res.append(x)
            _impl(seq, n, res)
            res.pop()

    return _impl(seq, n, [])

s = ['A', 'B', 'C']
for x in picks_without_repeats(s, 2):
    print(x)

[haughty mountain]

"yield all of the elements from this thing"

!e dumb generator example with yield from

def hello(thing):
  yield 'hello'
  yield thing

def hellos():
  yield from hello('world')
  yield from hello('mum')
  yield from hello('pydis')

for s in hellos():
  print(s)

[halcyon plank]

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

001 | hello
002 | world
003 | hello
004 | mum
005 | hello
006 | pydis

[modern walrus]

Do you guys know a good implementation of maximum graph matching algorithm, that uses numpy?

[solemn moss]

How to find any local maximum in array by checking <= 35 elements of the array (with size <= 10^6)?
Local maximum is an element that is greater or equal both his (or only one if second doesn't exist) neighbors
Binary search like this

while r - l:
    mid = (l + r) / 2;
    if ask(mid) < ask(mid - 1):
        r = mid - 1;
    elif ask(mid) < ask(mid + 1):
        l = mid + 1;
    else:
        l = r = mid
# l is answer

Will check ~55 elements in the worst case (repeated calls aren't counted)

[paper lotus]

Do you guys know about avl trees?

[olive badge]

there are a bunch of professional competitive programmers here, just ask the question

[paper lotus]

What does AVL stand for

Some guys in a java server already helped me out lol

[olive badge]

wikipedia said it was named because of the creators

, Georgii Adelson-Velskii and Yevgeniy Landis.

[haughty mountain]

unique elements, right?

otherwise this is impossible in general

I think you can split in thirds

or something like it

if you find i < j < k such that a_i < a_j > a_k then there exists a local maxima in interval (i, k)

this should end up being the insight that solves the problem

some special cases for the endpoints

or possibly you can imagine padding with -∞ on both sides

a = -∞, 10, 20, 40, 35, 33, 30, 25, 20, -∞
     l          m1          m2           r

a[l] < a[m1] > a[m2]

a = -∞, 10, 20, 40, 35, 33, 30, 25, 20, -∞
     l      m1      m2       r
    
a[m1] < a[m2] > a[r]
    
a = -∞, 10, 20, 40, 35, 33, 30, 25, 20, -∞
             l  m1      m2   r
    
a[l] < a[m1] > a[m2]
    
a = -∞, 10, 20, 40, 35, 33, 30, 25, 20, -∞
             l  m1       r
    
a[l] < a[m1] > a[m2]
    
a = -∞, 10, 20, 40, 35, 33, 30, 25, 20, -∞
             l  m1  m2   r
    
r - l <= 2, we're done

random example, hopefully the idea comes across

l and r are indices such that there exists a local maxima in range (l, r)

that's the invariant being upheld

this is rejecting 1/3 over and over

!e print(10**6 * (2/3)**35)

[halcyon plank]

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

0.6867614881773239

[haughty mountain]

<1, so it should be enough

fwiw, this is just ternary search applied to a possibly not unimodal function

[ripe kayak]

need help with my code if someone is available i seem to keep getting duplicates. I am getting live data from an API and I am trying to tell the code if value does not exists in results list append new values to the new_values list. the data that results list contains is a list of dictionaries.

results = []
new_values = []
window_size = 30
while True:

    getLiveData_Body = {
        'userToken': userToken,
        'liveDataToken': userLiveDataToken,
        'continuation': None
    }

    response = session.get(f"{api_url}getLiveData", data=json.dumps(getLiveData_Body))

    liveData = response.json()

    if liveData['statusCode'] != 'Good':
        session.get(f"{api_url}revokeLiveDataToken",
                    data=json.dumps({'userToken': userToken, 'liveDataToken': userLiveDataToken}))

    Tag_LiveData = liveData['data']

    continuation = liveData['continuation']
    recordIndex = 0

    with open(csvFileName, 'a', newline='') as outputFile:

        for tagKey, tagTvqs in Tag_LiveData.items():
            for recordIndex in range(len(tagTvqs)):
                record = tagTvqs[recordIndex]

                csvObj = dict()
                csvObj['Timestamp'] = record[0]
                csvObj['Meter'] = tagKey
                csvObj['Values'] = record[1]
                csvObj['Data_Quality'] = record[-1]
                results.append(csvObj)

[haughty mountain]

actually, would doing m1 m2 in the middle work for a better split?

[orchid violet]

#❓｜how-to-get-help

[solemn moss]

But each time that checks 2 values (a[m1] and a[m2]), so that would be multiplied by two, no? Except if we do something like golden ternary search (though I am not sure how to do it with whole numbers)

I tried it and it runs >35 requests if I input just 1, 2, 3, 4, 5 ... for each new ask

[solemn moss]

It actually uses about 3-5 requests more than this as I can see

And yeah, elements can be not unique
But same elements can be maximum too

Like

10 5 3 3 3 5 10
       ^ is a local maximum

[narrow mica]

Hmm... set the condition to "the next element is smaller," then

  [10 5 3 3 3 5 10]
> [ T T F F F F  F]
```So I think you can easily binary search this to find the first `F`. Its worst case(number of calls) is better than the original I'm pretty sure, as it only does 2 instead of 3 `ask`s per iteration; though it won't break prematurely if it finds the extrema early

[solemn moss]

But here it is a very pretty array that is first only decreasing then increasing

What about array like

  [1 2 3 2 1 2 3 2]
> [F F T T F F F T]

[haughty mountain]

ah, right

[haughty mountain]

but this means you need to do something better than ternary search for a unimodal list?

[solemn moss]

Yes

[haughty mountain]

err, golden section search maybe

[narrow mica]

Right... what should the answer be in this case, btw? all local maxima?
Well it's all 3 in this case, but what if you had something like 2 3 2 1 4 1

[solemn moss]

Any local maxima

one of 3s here

[solemn moss]

3 or 4

and for example for
5 3 3 3 6
5, 3 or 6

[haughty mountain]

I think that enables re-using the previous probe in the next iteration

it's ternary search but with a non-uniform probing

[solemn moss]

I know
But how to use it on whole numbers, not floats?

I mean i understand that we need to find some good numbers, but which 😅

[haughty mountain]

would doing some rounding not work?

I guess regardless, fibonacci comes to mind

[brazen willow]

small fool

let me tell you

[haughty mountain]

this matched terribly with my array from before...padding galore to make r - l a fibonacci number

a = -∞ 10 20 40 35 33 30 25 20 -∞ -∞ -∞ -∞ -∞
     l             m1       m2              r
     l       m1    m2        r
     l    m1 m2     r
           l m1 m2  r

regardless, the point is just showing off the overlapping

spacings

8 5 8
5 3 5
3 2 3
2 1 2
1 1 1

[solemn moss]

Yeah, that works

Thanks for the help 👍

[fiery cosmos]

kindly suggest a book regarding DSA which contains topics to an advance level

[agile sundial]

clrs

[fiery cosmos]

is it a book?

[agile sundial]

indeed

[fiery cosmos]

this one?

[agile sundial]

indeed

[fiery cosmos]

thanks

[modern gulch]

That's a good one... been around a long time. I've also heard some reviews of Goodrich's: https://www.amazon.com/Structures-Algorithms-Python-Michael-Goodrich/dp/1118290275. I actually think that (the one you posted) was my college book (many many moons ago)

[swift phoenix]

No really a question and I'm not sure if this is truly the correct channel:

def __getitem__(self, idx):
        # slicing
        if isinstance(idx, slice):
            start = idx.start if idx.start is not None else 0
            stop = idx.stop if idx.stop is not None else -1
            step = idx.step if idx.step is not None else 1
        if isinstance(idx, int):
            start = idx
            stop = idx
            step = 1

Is this the "correct" way to allow for slicing in your __getitem__() methods?

It definitely works I'm just wondering if I am overcomplicating things

[lean walrus]

replace ... if idx.X else ... with ... if idx.X is None else ..., because otherwise 0 will be treated in the same way as None

also i dont think you are handling int indices correctly
for example, slice of list always returns list, but int-indexing list returns value, not a list with one value

i would just do two separate routines for two cases, because they have not much in common

[fiery cosmos]

thanks

[shadow glen]

guys, i discovered a good algorithm to find stuffs in a list

lst = [1, 3, 3, 2]
sel = lst
selected = list()
while 3 in sel:
   ind = sel.index(3)
   selected.append(sel[ind])
   sel.pop[ind]
print(selected)

will it works with a list of dictionaries?

[agile sundial]

it doesn't even work for a list of anything

[narrow mica]

I don't think that even runs, as

sel.pop[ind]
```will cause an error

[agile sundial]

but it would work for anything after being fixed, yes

it's valid, but will error

[shadow glen]

like this?

lst = [1, 3, 3, 2]
sel = lst
selected = list()
while 3 in sel:
   ind = sel.index(3)
   selected.append(sel[ind])
   sel.pop(ind)
print(selected)

[shadow glen]

see above

i wonder if this way would be faster than the usual way

[fiery cosmos]

this was my college book as well

[agile sundial]

certainly not

[fiery cosmos]

anyone have an idea of a good algo to or script to classify hierarchical data? like for example, let's say it is in the form:
PC hardware hardware type subtype part number
or any similar structure. now let's imagine there is a file with thousands of entries, but you want a unique list of every entry. also for this data visualization software i'm using, i would need lists of the form
pc_hardware = [] hardware_type = [] subtype = [] part_no = []
which would be populated such that each index of each list contains the necessary information. so for example querying each list for index 0 would return all the necessary information for a single part

[shadow glen]

oh, so it wouldn't be faster than using for

[fiery cosmos]

the trick is i want to only create unique entries, where there are duplicates of one or more of the above categories

[shadow glen]

like, for a huge list of dicts

that form the 1000 dicts you just want 2 or

3 of them

[haughty mountain]

pop with an index always raises red flags for me

possibly linear time per pop

also that in check is expensive

[shadow glen]

i see, so i need to make the index in a separated variable

then use pop

[haughty mountain]

do you care about sel after this?

[shadow glen]

sel?

wdym?

[haughty mountain]

your sel list

[shadow glen]

you got a better idea?

if yes sure, show me then

[haughty mountain]

do you care about sel after that code?

[shadow glen]

i don't mind you use a different from sell

*sel

[haughty mountain]

or is sel just used in that code an nowhere later?

[shadow glen]

just in that code

like, it's just to make a separated variable to operate the search

like discardable plastic cup

[haughty mountain]

!e why not just

lst = [1, 3, 3, 2]
selected = [x for x in lst if x == 3]
print(selected)

[halcyon plank]

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

[3, 3]

[haughty mountain]

or even [3]*lst.count(3)

[shadow glen]

uhmm, and if i want the 3 from a giant list

like a list with 1000 contents for example

?

[haughty mountain]

what about it?

[shadow glen]

like, you have a database and inside your database you have a list with thousands of dictionaries

which could cause for to be slow

and from those 1000 dicts you just want 3 or 4 of those dictionaries

with a specific thing

[haughty mountain]

regardless, the approach you did is just a bad idea

potentially O(n²) work

compared to O(n) in my example

if you have some structure that actually allows you to have faster lookup/deletion then sure you might be able to do better

[shadow glen]

O(n) O(n^2), uhmm, I wonder what those represents

[fiery cosmos]

time complexity

the time an algorithm takes to execute. big oh ("O") being one measure among others

[haughty mountain]

try running your code with lst = [3]*10000

and then mine

one does a lot more work than the other

!timeit

lst = [3]*10000
sel = lst
selected = list()
while 3 in sel:
   ind = sel.index(3)
   selected.append(sel[ind])
   sel.pop(ind)

[halcyon plank]

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

20 loops, best of 5: 16.3 msec per loop

[haughty mountain]

err

that doesn't seem right

[shadow glen]

!timeit

lst = [1, 3, 3, 2]
selected = [x for x in lst if x == 3]

[halcyon plank]

@shadow glen :white_check_mark: Your 3.12 timeit job has completed with return code 0.

500000 loops, best of 5: 437 nsec per loop

[shadow glen]

!timeit
lst = [3]*10000
sel = lst
selected = list()
while 3 in sel:
ind = sel.index(3)
selected.append(sel[ind])
sel.pop(ind)

[halcyon plank]

@shadow glen :white_check_mark: Your 3.12 timeit job has completed with return code 0.

20 loops, best of 5: 17.4 msec per loop

[haughty mountain]

!timeit

lst = [3]*10000
selected = [x for x in lst if x == 3]

[halcyon plank]

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

500 loops, best of 5: 449 usec per loop

[haughty mountain]

I mean ok, it's faster, but it should be oceans faster

[shadow glen]

guess my algo is more niche

like how while and for is both niche

[haughty mountain]

!timeit

lst = [3]*100000
selected = [x for x in lst if x == 3]

[halcyon plank]

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

50 loops, best of 5: 5.28 msec per loop

[haughty mountain]

!timeit

lst = [3]*100000
sel = lst
selected = list()
while 3 in sel:
   ind = sel.index(3)
   selected.append(sel[ind])
   sel.pop(ind)

[halcyon plank]

@haughty mountain :warning: Your 3.12 timeit job timed out or ran out of memory.

[No output]

[haughty mountain]

that's more like it

[fiery cosmos]

and this is a good time to introduce

memory complexity?

[haughty mountain]

your thing scales really bad with large inputs with many 3s

[fiery cosmos]

what would this be technically

i dont think memory complexity is the right word. i believe it is space complexity

[shadow glen]

yeah, thought that's a good beginning for my research

[haughty mountain]

space complexity is fine here

[shadow glen]

small stuffs it's faster

but if it needs big stuffs it's slower

[haughty mountain]

not really faster than what I suggested

the thing I showed is basically as good as you get for a list

if you have a different structure with fast lookup and fast deletion then maybe you can do better

[shadow glen]

uhmm... so it can be done better in some way unknown. UHmm... Do you recomend any library that i can implement to improve my algo?

[haughty mountain]

if your input is actually a list you really can't do this better than what I suggested

i.e. just go through and filter the list

[shadow glen]

oh, so the classic for thing, the best that can be done

[haughty mountain]

if you have a list

you need to at least look at every element

[fiery cosmos]

really struggling with my thing here. i feel i may need to write a class

this format is weird in that i need some way to inherit prior running information when the level of classification changes

there is probably some obvious way to do it that i'm not seeing

clyde bot told me i couldnt send my example data

not sure what that's about

oh class is reserved keyword 🤦🏻‍♂️

class_
``` it is

how can i enter time between my print statements

i'll begin by importing time

i thought you could test if a variable exists with if var

i'm getting an error

wow i love time.sleep(0.5) for slowing print statements

[main vortex]

Is there any algorithm to compute the similarity between Abstract Syntax Trees? I am trying to match code patterns. I thought of using tree edit distance but I don't know if it works well for structured trees.

[fiery cosmos]

any easy way to transpose lists

eg i have a list of tuples of len 6 and i want to convert this into 6 lists where tup[0][0] is element 0 in list 1, tup[1][0] is element 0 in list 2, et cetera?

right now i'm sort of 'manually' building them in an obnoxious way

[haughty mountain]

zip

!e

A = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print(A)
A_t = list(zip(*A))
print(A_t)

[halcyon plank]

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

001 | [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
002 | [(1, 4, 7), (2, 5, 8), (3, 6, 9)]

[fiery cosmos]

perfect, thanks

what is the *A

for all in A?

[haughty mountain]

unpacking

zip takes multiple arguments

!e

print(list(zip([1, 2, 3], [4, 5, 6], [7, 8, 9])))

[halcyon plank]

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

[(1, 4, 7), (2, 5, 8), (3, 6, 9)]

[haughty mountain]

that's what it ends up as

[fiery cosmos]

unpack list A?

oh it takes mult args, and one list is singular ds

so you have to 'unpack' it

[twin jasper]

is it correct guys? im trying to get the big picture of the trade offs between the data structs

[agile sundial]

what's wrong with just a normal table 😭. but no. searching a hash table is also O(1). as is insertion and deletion

[twin jasper]

hahaha it's just easier for me to understand if there's a graphical representation 🤣 , ty gonna fix it

[jolly mortar]

also note deletion and insertion in a linked list are only O(1) if you already have access to the node at which you want to insert/delete

otherwise if you only have the head and want to insert at index i then that can take O(n) to find the ith node

[twin jasper]

Oh you're right, I was thinking only about the operation itself compared to array.

But if you don't know what index the thing you wanna delete/insert is, linked list is still better than the array right? Because it takes search O(n) and delete/insert O(1), but array takes search O(n) and insert/delete O (n)

[jolly mortar]

both are O(n)

if you are talking about actual runtime, then arrays perform much better than linkedlists in most cases even in operations where linkedlists have better complexity

the elements being stored next to each other in memory makes them much faster

[twin jasper]

oh right, O(n) dominates O(1) i forgot about that for a sec, so what kind of situation a linked list would be used in real life problems ? (even tho all the odds)

[dull mist]

[naive oak]

linked lists are rare outside of just being a thing you learn in school afaik

[outer rain]

I hate big-O tables, because they hide a lot of complexity inside of them, and distract from what is actually important (which is how structures actually work). But I also like this circle format a lot, so here is my (opinionated somehow) version.

[solemn moss]

For example i used list in this task
https://codeforces.com/contest/1886/problem/C

though it can be solved without it /

[haughty mountain]

lol, that's so hard to parse

[haughty mountain]

it makes for a pretty good deque

[outer rain]

circular vector makes for a pretty better deque 💀

[haughty mountain]

circular vector is only amortized O(1) right?

which might be something that mattera

[twin jasper]

i like it! i has thinking about make three radar chart for the best, avereage and worst case but it put all of them together in just one!

[haughty mountain]

granted, if you know an actual upper bound on the queue size it's a really good option

[naive oak]

good point

[fiery cosmos]

Given the head of a Singly LinkedList, write a method to check if the LinkedList is a palindrome or not.

Your algorithm should use constant space and the input LinkedList should be in the original form once the algorithm is finished. The algorithm should have O(N) time complexity where ‘N’ is the number of nodes in the LinkedList.

Example 1:

Input: 2 -> 4 -> 6 -> 4 -> 2 -> null
Output: true

Example 2:

Input: 2 -> 4 -> 6 -> 4 -> 2 -> 2 -> null
Output: false

What would it mean here that algorithms should use constant space?

[haughty mountain]

the process of making such a table or chart 's probably much more helpful than trying to just read such a chart

[haughty mountain]

constant auxilliary/extra space

e.g. creating a new list of the items is O(n) extra space

[fiery cosmos]

Like not use any extra space? Like additional array?

[haughty mountain]

having a fixed number of variables would be fine for O(1) extra space

[fiery cosmos]

Yes, but I shouldn't make a new list of the items, right?

Because that is O(n) extra space

So I can use just variables like pointers or something like that

[haughty mountain]

right

sure

even using recursion would violate things

the way the question is phrased I can kinda guess what the intended thing is, and it's...not exactly pretty

[fiery cosmos]

How do you mean it is not pretty?

I think that I know how to solve it without extra space

Like reverse second half, loop from the first element of second half and then see whether each next element is same as from the first pointer element

[haughty mountain]

[...] and the input LinkedList should be in the original form once the algorithm is finished.

[twin jasper]

yup, gonna do that for the algorithms aswell

[fiery cosmos]

Ah

[haughty mountain]

Yeah, it would allow reversing one of the halves in place and then undoing it

[fiery cosmos]

Yes

[haughty mountain]

It makes it a bit of a gotcha problem, if you miss that tiny bit of phrasing you're screwed at solving the problem

[fiery cosmos]

What does a "gotcha problem" mean?

[haughty mountain]

it's a subtlety that just invites being missed

[fiery cosmos]

So I used this code

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

class LinkedList:
    def __init__(self):
        self.head = None

    def is_empty(self):
        return self.head is None

    def append(self, value):
        new_node = Node(value)
        if self.is_empty():
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

    def display(self):
        current = self.head
        while current:
            print(current.val, end=" -> ")
            current = current.next
        print("None")

def reverse_list(head):
    aux_pointer = None
    while head is not None:
        next_element = head.next
        head.next = aux_pointer
        aux_pointer = head
        head = next_element
    return aux_pointer

How so that

my_list = LinkedList()
my_list.append(1)
my_list.append(2)
my_list.append(3)
print("Original list:")
my_list.display()
reversed_list_head = reverse_list(my_list.head)
my_list.display()

Prints 1 -> None

But if I do

print("\nReversed list:")
reversed_list = LinkedList()
reversed_list.head = reversed_list_head
reversed_list.display()

Then it is okay

[haughty mountain]

Why? Because your LinkedList points to the old head

You want something that points to the new head

I would make the reverse_list return a LinkedList that points to the start node, makes things easier to use

and maybe make the LinkedList constructor actually take an optional Node as an argument

!e

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

class LinkedList:
    def __init__(self, head=None):
        self.head = head

    def is_empty(self):
        return self.head is None

    def append(self, value):
        new_node = Node(value)
        if self.is_empty():
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

    def display(self):
        current = self.head
        while current:
            print(current.val, end=" -> ")
            current = current.next
        print("None")

def reverse_list(head):
    aux_pointer = None
    while head is not None:
        next_element = head.next
        head.next = aux_pointer
        aux_pointer = head
        head = next_element
    return LinkedList(aux_pointer)

my_list = LinkedList()
my_list.append(1)
my_list.append(2)
my_list.append(3)

print("Original list:")
my_list.display()

print("Reversed list:")
reversed_list = reverse_list(my_list.head)
reversed_list.display()

[halcyon plank]

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

001 | Original list:
002 | 1 -> 2 -> 3 -> None
003 | Reversed list:
004 | 3 -> 2 -> 1 -> None

[fiery cosmos]

Thanks for explaining

[shadow oyster]

my_fruits = [apple,banana,banana,banana,strawberry,strawberry,orange] # multiset
recipe_needs = [apple, banana,banana] # multiset
friend_a_wants = (orange,banana, apple) # set
friend_b_wants = (strawberry,banana,apple) # set

counter_fruits = Counter(my_fruits)
counter_recipe = Counter(recipe_needs)
counter_friend_a = Counter(friend_a_wants)
counter_friend_b = Counter(friend_b_wants)

fruits_left = counter_fruits - counter_recipe 
fruits_left_aux = fruits_left

possible_fruits_for_a = fruits_left & counter_friend_a

# A function that verifies if my_fruits has all fruits from recipe_needs and also has extra fruits to at least give one
# fruit to each friend from the fruits they want. 

Case: n(friend_one_wants  ∩ friend_two_wants) > 1 

# One solution for this problem is:
for fruit in possible_fruits_for_a:
  fruits_left = fruits_left - fruit
  if fruits_left & counter_friend_b:
    return True
   else:
    # resets fruits left
    fruits_left = fruits_left_aux
    return False

This is pseudocode. Would it be possible to solve this problem without iterating through each possible solution? I was trying to think of a solution using only Counters but it seems it is not possible here.

[opal oriole]

They show up in systems programming. However, usually not with just one integer per node or something (like found in educational examples (those are very rare since you are more than doubling the memory usage)). It's usually chunks of data linked together, so kind of a hybrid between a linked list and an array. Still is a linked list though, they just are not often used in isolation, but combined with other things.

Systems programming is also relatively rare these days.

The ratio of people that make the systems to those that use them is very small.

Linked lists can also often be the easiest and cleanest way to implement some feature. So not really used for performance or anything (not super performance sensitive), but production speed.

Another use case is when you are tight on memory but want growing (unknown) number of nodes. Using a dynamic array with doubling (allocating a bunch extra) may end up wasting a lot of memory / overshooting the upper memory budget.

(Lots of older programs on older hardware used them over dynamic arrays for this reason)

(Can still come up in embedded)

[turbid lodge]

hey Is anyone able to help me get any futher with this idea. I'm an algo that gets more personlize with you based off the input you feed it

[eager bolt]

can someone help me write asearch algorithm?

[halcyon plank]

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

001 | [8, 6, 1, 4, 3, 5, 9, 7, 2]
002 | [8, 3, 1, 7, 2, 6, 9, 5, 4]
003 | [2, 5, 7, 6, 3, 4, 9, 8, 1]
004 | [6, 5, 3, 9, 4, 1, 2, 8, 7]
005 | [2, 6, 3, 7, 4, 1, 5, 8, 9]
006 | [9, 4, 5, 1, 3, 6, 8, 7, 2]
007 | [5, 3, 1, 7, 8, 9, 6, 2, 4]
008 | [4, 1, 6, 8, 9, 5, 2, 3, 7]
009 | [7, 6, 8, 4, 3, 2, 9, 1, 5]

[fierce shore]

hey Houston we have a GOTCHA

[fiery shard]

[True, True, True] = True
[True, True, False] = False

I'm trying to create a function which would get a list of bool and return True just when all are True. How can I do it?

[narrow mica]

Use the built-in all()

There's also any(), which returns True if any of the bools in a list is True

[tranquil kindle]

Hi guys, is there any example of network, where the push–relabel maximum flow algorithm wont find the maximal flow, if I initialize label(source)=|V|-2, because I cannot find an example where the algorithm would fail.

[fiery cosmos]

Can anyone help on this?

'''
You have a travel plan for the next N days (numbered from 1 to N). During day i, you need to drink exactly Pi mL of water. Alternatively, you can consume a vitamin pill instead, as a replacement for water on that day. Currently, you only have M mL of water and K vitamins. If there is not enough water to drink on a day and you run out of vitamins, then your travel plan ends. Determine the maximum number of days you can travel.

Input
The first line consists of three integers N M K (1 ≤ N ≤ 100; 0 ≤ M, K ≤ 100).
The next line consists of N integers Pi (1 ≤ Pi ≤ 100).

Output
Output a single integer representing the maximum number of days you can travel with the appropriate rations.
'''

[solemn moss]

You can iterate over all possible days and check if sum of n - k minimum elements (you want to spend as less water as possible, because vitamins can replace any amount of water) is <= M

That can be done faster but with these constraints you can just check all possible days and sort the array each time to find the minimums

[brazen python]

With a bloom filter you can only store 64 items in your set, right?

Using an int64

[lean walrus]

no

bloom filter consists of several bitarrays (several int64's)
you can store a lot of data in them

i guess if you have k bitarrays of len n, you can store approximately n^k values

oh wait, maybe im confusing it with something else

[haughty mountain]

"store" is a bit misleading for bloom filters

you don't store items, but store a hash based fingerprint of sorts, to try to allow you to reject things

[lean walrus]

if you have only one prefect (no collisions) hash function, you can store up to 64 items
(actually it is pretty similar to what pascal did a century ago - there were builtin sets which were implemented as bit arrays)

[haughty mountain]

not bloom filters, but for hash tables sure

bloom filters is a fun case where some collisions are ok (maybe even good)

as long as a handful of hashes don't collide you have a decent chance of being able to reject

[haughty mountain]

(which Pascal is a century old?)

[lean walrus]

iirc, free pascal (or turbo pascal) had this feature

pascal was developed in 1970, so it is half a century old

almost entire century 😄

[haughty mountain]

in the time scale of the universe, sure 😛

[haughty mountain]

I was a tad confused whether you were 3.5x too low or 2x too high

[lean walrus]

lmao

[fiery cosmos]

hii

can someone help me to solve a problem with python ??

@hybrid barn can you ?? :3

[summer fossil]

#1035199133436354600

[north haven]

I don't see a cryptography channel, so I thought I might ask here:

How do I encrypt two strings into one so that I can use two keys to get two different messages from a single string?
I need a method that should work kind of like this:

key1 = "asdf"
key2= "xcvb"
encrypted_message = "qpoweiurtz"

decrypt(encrypted_message, key1)
decrypt(encrypted_message, key2)

Output:

apple
pear

Is something like that possible?

[modern gulch]

I remember reading about a hard drive encryption tool that did something like this. A quick google yielded VeraCrypt (I don't remember if this is what I read, but take a look)

[lean walrus]

the trivial way to do so would be to encrypt two strings to two messages and then concatenate them
then if you are using 1st key, you decrypt 1st part of the message, if not - the 2nd
you can determine which key is currently used by looking at some checksum of it - for example if it has even number of set bits - it is key1, if odd - key2

[paper lotus]

2-3-4 trees are fun

[sly spindle]

yes

[brazen python]

hey guys, I'm using this code for BFS, I wonder if its possible to keep track of the number of descandants each node has.
so for example the root node can have 10 descandants, its child will have even less than that, and a node that is a leaf will have zero descandants, how can I do that?

def bfs(*root_nodes: str) -> Iterator[tuple[int, str]]:
    level = 1
    visited_nodes = {*root_nodes}
    queue = root_nodes
    while queue:
        level += 1
        next_level = []
        for x in get_children(*queue):
            if x not in visited_nodes:
                next_level.append(x)
                visited_nodes.add(x)
                yield level, x
        queue = next_level

[haughty mountain]

Do the traversal and store a bfs (or dfs) order of nodes.

Go through this order backwards and fill in a list of descendants counts.

for cur in reversed(bfs_order):
  descendants[cur] = sum(descendants[child] for child in children)

Doing it in one pass is quite a bit more annoying in the iterative version since the natural thing to compute this is from the leaves up

For a recursive impl it would be natural to do in one pass

[brazen python]

I'm not exactly understanding your code, but I did something that calls the bfs function once for each node, and as you can imagine its reaaaally slow, its I think O(N^2)

oh so doing the bfs from the bottom up, you mean

[haughty mountain]

no

[brazen python]

natural thing to compute this is from the leaves up

[haughty mountain]

whatever traversal you do from the root visits the nodes in some order

[brazen python]

yeah?

[haughty mountain]

store that order

[brazen python]

how?

[haughty mountain]

in a list?

[brazen python]

the issue is knowing if a node is a child of who

[haughty mountain]

why?

you need that info to be able to do any traversal

[brazen python]

i'm too confused, isnt the level itself the number of nodes it has as ancestors? I think so

oh no, its different

by the number of descandants, I mean everything, so in one level it can have 5 desandants for example

like the whole sub-tree under a specific node

[haughty mountain]

yes

[brazen python]

I dont understand how your code does that

[haughty mountain]

oh wait, my code is a tad off

for cur in reversed(bfs_order):
  descendants[cur] = sum(descendants[child]+1 for child in children[cur])

missed a +1

if the results were already calculated correctly, can you see how this is true?

descendants[cur] == sum(descendants[child]+1 for child in children[cur])

the number of descendants is all the descendants of your children, and then you need to include the child itself in the count

[brazen python]

can you show me how you create bfs_order?