#algos-and-data-structs

1 messages ยท Page 96 of 1

drifting marsh
#

I see. thanks! Hopefully I can get this working now! ๐Ÿ˜€

wispy hare
#

don't forget from collection import defaultdict

sterile basalt
#

hello everyone
who help plz
Choose the first note randomly or consider the first note of the
original score (e.g. G) ;
See in the table the notes that succeed it (Ex: for the note G, the successors
are : G, G i, D, D, C, A) ;
Choose a random note among these successors;
Repeat this process, as many times as necessary, starting from step b) by considering
each time the successors of the last selected note.
it's my pb in python

wispy hare
pallid phoenix
#

hello, not sure if i should ask this here or in data-science, i'm trying to generate all the permutations given 12 numbers, and using between 12 and 6 at a time
so if i had [1,3,5,7,9,11,13,15,17,19,21,23],and length 8 i would want for example, ('3', '7', '13', '11', '9', '5', '1', '15')
but once i try for length 10,11 or 12, my pc freezes
a length of 10 has 239,500,800 permutations, and 11 and 12 lengths have 479,001,600

#

also, whenmever i click on a Topical chat/help, and click on a different one, the previous one disappears from the list

oblique panther
oblique panther
#

It looks like you found your way back to the data science channel; hopefully itertools.permutations suited your needs.

pallid phoenix
#

yes i store all the permutations in a list, fortunately it seems i wont have to do permutations longer than 9

agile sundial
#

that's a lot of stuff to store

oblique panther
devout flower
#

anyone have a good article on hash functions?

oblique panther
#

The basic idea is that you take a value, and you have a function that converts that value to an arbitrary number. But it has to be the same arbitrary number every time for that function and that value.

#

Sometimes you do this for security. But it's also very useful for storing and finding data.

spring jasper
#

And its also hard to reverse

oblique panther
#

though I certainly don't have to tell you that.

#

Python has some randomization in the initial setup of its hash functions, but the hash of a given value is consistent during a given interpreter session. Apparently that's for security. Not entirely sure why.

cloud moth
#

i am trying to implement sobel operator algorithm using python without using external libraries. I am bit stuck. The image produced after sobel operations is bit crappy.

#

Please provide some suggestions, of what i am doing wrong. i based it off on this video, i assume, i had done correctly as per this video https://www.youtube.com/watch?v=uihBwtPIBxM

YouTube
Computerphile
Finding the Edges (Sobel Operator) - Computerphile

Our eyes can spot edges with no problems, but how do computers determine what's an edge and what's not? Image Analyst Dr Mike Pound explains the Sobel Edge detector.

How Blurs & Filters work: https://youtu.be/C_zFhWdM4ic
The Problem with JPEG: https://youtu.be/yBX8GFqt6GA
Secrets Hidden in Images (Steganography): https://youtu.be/TWEXCYQKyDc
M...

โ–ถ Play video
cloud moth
#

am i asking this question in wrong place ?

sick oar
#

Hi all. I am trying to solve an optimization problem for a group of my friends playing game ...

I feel lost - not sure if the problem is too complicated or just I get a wrong direction.

Each player can form up to 3 teams (A, B, C), each team can be used once to deal damage to 1 of 5 bosses (1,2,3,4,5).

So a player can have a list like (A, 2, 50), (A, 3, 80), (B, 4, 70) ...

The last number is damage.

This example means that player can hit boss 2 with 50 dmg or boss 3 with 80 dmg with team A.

What I want to do is try to allocate the team and damage before we actually fight.

Imagine the boss 1 has 1000 hp. The goal of allocation is to sum up our team damage and reduce overkill

#

I feel like solving the coin charge problem and create a large decision tree for all the possible team combination. It seems like solving 2 hard problems together. Any hints or thoughts on this problem?

#

I think I can solve the coin charge problem (sum up damage to minimize overkill and still enough to beat the boss).

But the constraint of same team can only be used once - and there are so many teams combination when there are many players - I have no idea how to deal with it

north cosmos
#

can u sort a number faster than n log n, i just heard it somewhere that you can't.
Don't remember where

wispy hare
dusk estuary
brave oak
#

assuming you mean a collection of numbers

north cosmos
#

yes

#

so u can't?

brave oak
#

if

#

like I said

#

not in the general case

north cosmos
#

i don't get what u mean by that

brave oak
#

you can for certain special classes of input if you know they fall into those classes beforehand

#

but if you don't know anything about the input, then no

#

also assuming no parallelisation

sick oar
# dusk estuary How does the team composition affect the damage of the team?

Just assume it is simple summation and subtraction for counting damage and overkill.

Boss hp
1 100
2 200
3 300
4 400
5 500

Player team and damage

Player Cat [(A, 1, 55), (A, 4, 300), (B ,1, 20), (C, 5, 350)]

Player Duck [(A, 1, 90), (A,2, 100), (B, 5, 200)]

Player Ethan [(A, 1, 70), (A, 3, 300), (B, 5, 480)]

Recommended damage allocation to reduce overkill while trying to beat the boss:

1: Cat B, Duck A (90+20)
2: Duck B (100) [Best effort] No team to deal dmg
3: Ethan A (300)
4: no team to deal dmg Cat A 300 [Best effort, cannot beat boss 4]
5: Duck B and Cat C (350+200)

#

I try to find the closest to optimal solution and come up with above numbers.

wispy hare
#

can a player hit twice?

#

Like for boss A, could we take Cat A 1 55 and Cat B 1 20?

#

I know it wouldn't be enough, but what if Cat B 1 was making 50 dmg for example

sick oar
#

I fixed the 2 boss case.

fiery cosmos
#

hey

wispy hare
#

okay then my idea would be that for each boss, you keep taking the maximum hit from a player, you sort them, then you keep taking until you deal enough damage

fiery cosmos
#

i wanted to ask if i attempted a challenge on codechef but am able to solve only few of the given problems will my rating increase?

sick oar
#

I misread your message, sorry

wispy hare
#

oh okay

#

and it can't hit twice with the same team right?

sick oar
#

Yes. Same team can only hit once

wispy hare
# 
for player in players:
  for hit in hits:
    boss, team, dmg = hit
    hit_map[boss].append((player, boss, team, dmg))
for boss in hit_map:
  hit_map[boss] = sorted(hit_map[boss], key=lambda hit: hit[3]) # sort by damage
  total_dmg = sum([hit[0] for hit in hit_map[boss])
  while hit_map[boss]:
    smallest_dmg = hit_map[boss][-1]
    if total_dmg - smallest_dmg >= hp_map[boss]:
      hit_map[boss].pop()
#

not hit_map should contain each boss and the optimal hits to kill it

#

didn't try the code, try it and tell me

sick oar
#

Let me try ... It takes some time

sick oar
#

It freezes for boss 4 in the case (no enough dmg to beat the boss)

from collections import defaultdict 

hp_map = {
  1: 100,
  2: 200,
  3: 300,
  4: 400,
  5: 500
}

players = {
  # simple case
  "Cat": [("A",1,55), ("A",4,300), ("B",1,20), ("C",5,350)],
  "Duck": [("A",1,90), ("A",2,100), ("B",5,200)],
  "Ethan": [("A",1,70), ("A",3,300), ("B",5,480)]
}

hit_map = defaultdict(lambda: [])

for player, hits in players.items():
  for hit in hits:
    team, boss, dmg = hit
    hit_map[boss].append((player, team, boss, dmg))

for boss in hit_map:
  hit_map[boss] = sorted(hit_map[boss], key=lambda hit: hit[3]) # sort by damage
  total_dmg = sum([hit[3] for hit in hit_map[boss]])

  while hit_map[boss]:
    smallest_dmg = hit_map[boss][-1][3]
    # print(total_dmg, smallest_dmg, "sd") - infinite loop here for boss 4
    if total_dmg - smallest_dmg >= hp_map[boss]:
      hit_map[boss].pop()
wispy hare
# sick oar It freezes for boss 4 in the case (no enough dmg to beat the boss) ```python fro...

hey I fixed it:


hp_map = {
  1: 100,
  2: 200,
  3: 300,
  4: 400,
  5: 500
}

players = {
  # simple case
  "Cat": [("A",1,55), ("A",4,300), ("B",1,20), ("C",5,350)],
  "Duck": [("A",1,90), ("A",2,100), ("B",5,200)],
  "Ethan": [("A",1,70), ("A",3,300), ("B",5,480)]
}

hit_map = defaultdict(lambda: [])

for player, hits in players.items():
  for hit in hits:
    team, boss, dmg = hit
    hit_map[boss].append((player, team, boss, dmg))

for boss in hit_map.keys():
  hit_map[boss] = sorted(hit_map[boss], key=lambda hit: hit[3], reverse=True) # sort by damage
  total_dmg = sum([hit[3] for hit in hit_map[boss]])
  while hit_map[boss]:
    smallest_dmg = hit_map[boss][-1][3]
    if total_dmg - smallest_dmg >= hp_map[boss]:
      hit_map[boss].pop()
      total_dmg -= smallest_dmg
    else:
      break
print(hit_map)```
#

I forgot to:

  • add else case to break the loop
  • set reverse parameter to true while sorting to get decreasing order
  • subtract the dmg of the hit we popped from total dmg
#

If n is the number of players, m the number of bosses, k the maximum hits for a player, I'd say that the time complexity would be O(nklognk)

sick oar
#

Something wrong with the team re-use in this case:

1: [('Duck', 'A', 1, 90), ('Ethan', 'A', 1, 70)], # <= Ethan A used here
4: [('Cat', 'A', 4, 300)],
5: [('Ethan', 'B', 5, 480), ('Cat', 'C', 5, 350)],
2: [('Duck', 'A', 2, 100)],
3: [('Ethan', 'A', 3, 300)] # and here

wispy hare
#

hmm that's right

#

I'll try to think about it again later

#

tell me if you found a solution

sick oar
#

That is one of the hardest problem in this part - no team re-use (assignment problem as I searched)

Then we try to do the coin charge problem to determine if the assignment problem solution is good enough or not

#

The worst case would be ... each player has all the 15 combinations (3 teams x 5 bosses). And there are more players

#

Thanks for the attempt anyway @wispy hare

fiery cosmos
wispy hare
# 
  john_sum = sum(john)
  jack_sum = sum(jack)
  john.sort()
  jack.sort(reverse=True)
  i = 0
  while i < len(john) and i < len(jack) and john_sum <= jack_sum:
    diff = jack[i] - john[i]
    john_sum += diff
    jack_sum -= diff
    i += 1
  return i if john_sum > jack_sum else 'IMPOSSIBLE' ```
#

time complexity: O(nlogn+mlogm) where n is len(john) and m is len(jack)

fiery cosmos
#

And once again thank you so much!

wispy hare
#

I just thought of what move would have the most impact on the difference between number of votes

#

I find out that swapping the smallest pack of john with the greatest pack of jack would have a great impact

#

so the solution would be to keep swapping between min(john) and max(jack)

#

and to avoid always searching for min and max, I sorted john in ascending order and jack in descending order

fiery cosmos
#

Ah, I see. So instead of calculating the john_sum, jack_sum, min, max at every step it is better to sort them.

wispy hare
#

exactly

pine cliff
#

Need a code for assembly language can some one help me kindly

trim fiber
pine cliff
#

Sorry I am new to discord where should i ask assembly language question?

oblique panther
pine cliff
oblique panther
split obsidian
#

Is there a good way to think about structuring DP problems? I can tell when to use DP, but I'm not as confident determining what (and where) the recursive relationship should be

oblique panther
#

The goal is to save the answer from earlier instances of the same recursive call so that you don't have to re-explore branches of the decision tree you've been to before, so to speak.

#

Perhaps I'm missing the point of your question

split obsidian
# oblique panther Perhaps I'm missing the point of your question

Most of the time when I see a DP problem, I instinctively think of some sort of recursive tree process, and I need to store the results.

My intuition is to have an outer function that gets called and handles state, and an inner function that will get called recursively and store the values. (Not 100% if this is correct, but it sounds right to me)

I usually trip up when it comes to the state. How do I traverse the state from the recursive call, how do I know where to even put the recursive call, etc.

wispy hare
#

a DP solution doesn't need a recursive function

oblique panther
wispy hare
#

we have two approaches for dynamic programming:

#

we have the top-down approach (memoization), where we start by solving the initial problem, and for that we need to solve smaller and smaller instances until we reach the base case, this one is usually done recursively by using a lookup map

oblique panther
wispy hare
#

and we have the bottom-up approach (tabulation), where we use an array or a matrix or something like this, we initialize cells whose we know the value (base cases), and we keep generating the next value from ones we already computed, this one is usually done iteratively

wispy hare
oblique panther
wispy hare
#

we have 4 easy steps to implement memoization on a recursive function

#

1- add a parameter lookup, which is a dict where we will store values that we computed before
2- inside the function, create the key, the key is something that characterizes that call, we can for example put a string that contains the concatenation of all changing parameters separated by a space, or we can just use a tuple that contains all changing parameters
(by changing parameter I mean a parameter whose value can change between the different calls)
3- add a condition that checks if we already computer the value before, so we write: if key in lookup: return lookup[key]
4- before every return statement in recursive cases, store the output in lookup[key] then return it
and because in Python a default value of a parameter shouldn't be mutable, we need to create a function that creates the lookup map, and calls the recursive function

#

Example: longest common subsequence

def lcs(str1, str2, i = 0, j = 0):
  if i == len(str1) or j == len(str2):
    return 0
  elif str1[i] == str2[j]:
    return 1 + lcs(str1, str2, i+1, j+1)
  else:
    return max(lcs(str1, str2, i+1, j), lcs(str1, str2, i, j+1))

# with memoization:
def rec(str1, str2, i, j, lookup):
  key = str(i) + " " + str(j)
  if key in lookup:
    return lookup[key]
  elif i == len(str1) or j == len(str2):
    return 0
  elif str1[i] == str2[j]:
    lookup[key] = 1 + rec(str1, str2, i+1, j+1, lookup)
    return lookup[key]
  else:
    lookup[key] = max(rec(str1, str2, i+1, j, lookup), rec(str1, str2, i, j+1, lookup))
    return lookup[key]
  
def lcs(str1, str2):
  lookup = {}
  return rec(str1, str2, 0, 0, lookup)```
lean dome
#

or @functools.lru_cache(maxsize=None) before Python 3.9

calm spade
#

How do i make a list print like

[['0','0','0'], 
['0','0','0'], 
['0','0','0']]

Instead of

[['0','0','0'], ['0','0','0'], ['0','0','0']]
#

?

runic tinsel
#

str(), then replace "," โ†’ ",\n"

#

you can just print(*lst, sep ='\n'), that looks different tho

wispy hare
#

or

arr = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
print(np.array(arr))```
calm spade
#

Ty

lean dome
calm spade
#

Owh

#

Alr

split obsidian
split obsidian
wispy hare
#

there surely exist books about problems, but I didn't learn through so I can't suggest some sorry

hollow quest
#

Hello! I've stumbled upon a problem that I don't know how to solve.
So I've stored some data in a json file that would look like this:

{
    "cars": [
        {
            "190z": {
                "price": "$900,000"
            }
        },
        {
            "9F": {
                "price": "$120,000"
            }
        },
        {
            "9F Cabrio": {
                "price": "$130,000"
            }
        }
    ]
}

My question is: How can I loop trough all the price elements of the json file? What I want to do is to remove the $ and the comma with the .replace() but I don't know how can I loop trough all the price elements.

#

Doesn't work. Throws me this error Exception has occurred: KeyError

#

I think it's because the json is something like cars -> name -> price

#

That's what I want to do, to skip the name and just search for the price

#

Now I get this one haha list indices must be integers or slices, not dict

#

Thanks for the help!

#

'dict_items' object is not subscriptable

#

Damn. Harder than I thought it'd be

#

ok

#

Same error

#

'dict_keys' object is not subscriptable

#

'dict_itemiterator' object is not subscriptable

#

unhashable type: 'dict'

#

Damn

#

The thing is that there are more elements

#

after the car name

#

I only put price because I wanted to be more explicit. One element looks like this:

        {
            "FQ 2": {
                "spawn": "fq2",
                "speed": "72.43",
                "seats": "4",
                "acceleration": "45.00",
                "braking": "8.33",
                "handling": "60.61",
                "image1": "https://www.gtabase.com/images/gta-5/vehicles/suvs/main/fq-2.jpg",
                "image2": "https://www.gtabase.com/igallery/6401-6500/GTA5_Fq2_Online-6450-108.jpg",
                "real-life": "Infiniti QX70",
                "class": "SUVs",
                "manufacturer": "Fathom",
                "traction": "AWD",
                "price": "$50,000"
            }
        },```
#

Hell yeah! It worked! Thanks man!

knotty gate
#

I have a neural network doubt

#

In implementing logistic regression

#

So my teacher was telling me implementation of this if we didnt use for loop

#

He updated the parameter in the end

#

And said this is one step of logistic regression

#

Can someone plz tell me that why are we updating the value just once?

eager hamlet
knotty gate
#

Ok

#

Yeah i guess so

eager hamlet
#

say i had 2 arrays, A and B
how would i go about finding the Kth greatest pairwise sum that could be made from an element of A and an element of B?
(ping 2 help plz)

knotty gate
#

The long way (may not be favourable)

#

Loop element of a over elements of b

#

And check sum

#

And keep on adding it to an array

#

Then sort the array

#

Then kth largest sum if k-1 th array element

#

@eager hamlet

eager hamlet
#

yeah

#

too slow

#

O(n^2) complexity

knotty gate
#

@eager hamlet

#

There one other way also

#

So u put just one for loop on any one arrat

#

Array*

#

Then using numpy and element to other array ......so that you get and array that has each element of array added by that looping number

#

Then concatenate those all arrays

#

Then find kth highest number in that array

#

Using numpy you will be able to do one for loop only

half lotus
#

But what would be the cost of the numpy operation

agile sundial
#

sort both then walk through them sorta like the merge part in merge sort

half lotus
#

That was my idea that would be n * nlogn I believe

agile sundial
#

yeah

half lotus
#

Which is slower than n^2

agile sundial
#

wait no, it would be nlog n + n

half lotus
#

Oh yeah

#

Never mind

#

If there are no duplicates, I wonder if there is a good way to get roughly the right index to start at

#

Cause you know that -1, -1 is the largest sum and -1,-2 and -2,-1 would be the 2nd and 3rd largest (but not which one is which)

#

Well the exception being that one of those could also have the same sum as -1,-1

#

No that actually wouldn't be possible of there aren't duplicates

fiery cosmos
#

I have created a reddit bot that gave me a bunch of submissions, I am looking to write a program that reads all of them, and than writes its own submission, a sort of general summary of everything its read. I have seen similar programs do so with movies and stories. I am not looking for help with the specific code, just a general plan of how to do this

eager hamlet
agile sundial
#

since both lists are sorted, then adding the last elements in both ists is the biggest number

eager hamlet
#

ok? yeah?

agile sundial
#

since it's sorted, the next biggest is either A[-2] + B[-1] or A[-1] + B[-2]

eager hamlet
#

go on?

agile sundial
#

then you just count until you reach K

eager hamlet
#

so let's say it's A[-2] + B[-1] is the smallest

#

then there's now 3 possibilities?

#

A[-3]+B[-1], A[-3]+B[-2], and A[-1]+B[-2]?

agile sundial
#

no since A[-3] + B[-1] >= A[-3] + B[-2]

runic tinsel
#

Also you want to heapify

#

So you don't sort both arrays completely

#

Just somewhat

cloud bough
#

does someone know a good implementation of a hash function

#

im confused on how to code it up

# 
class HashTable:
    def __init__(self):
        self.max = 100
        self.arr = [None for _ in range(self.max)]

    def hash(self, key):
        c = 0
        for char in key:
            c += ord(char)
        return c % self.max

    def insert(self, key, value):
        h = self.hash(key)
        self.arr[h] = value
#

am i on the right track here

mint jewel
#

you will want lists on each element of self.arr, since you can get hash collisions. Python also automatically increases max when there are too many collisions

cloud bough
cloud bough
eager hamlet
#

oh yeah i'm dumb lol

#

A[-3]+B[-1], A[-2]+B[-2], and A[-1]+B[-2]?

#

and even then

#

linear time wouldn't be good enough

agile sundial
#

linear time isn't good enough?

runic tinsel
#

Combine them into one

#

Then do the heap thing

eager hamlet
#

what

runic tinsel
#

I don't know

lean dome
eager hamlet
#

the thing is this TLEs on a test case

#

complexity is n log n so it should pass

#

so now it's just matter of constnat factor optimization

#

any pointers?

lean junco
#

@half lotus numpy would be even faster

#

as numpy.dot is linear ie O(n)

#

u would just have to sort it thats it

trail oracle
#

hello guys !
I want little help with programming in python
I want to get input from the user using the command line and I want to get multiple integer values as input and set it inside a list. I want the user to enter each number and then press enter and again enter another number and press enter. how to do this way?

#

here is the code I am trying right now:

fiery cosmos
#

This is not the appropriate channel for that

fiery cosmos
#

sorting a dictionary by the value of the keys transforms it into a list. why?

agile sundial
#

dictionaries are unordered

oblique panther
#

Why do you need them to be ordered? If it's for human readability, you don't have to think about how they're ordered in the dictionary until you go to transform the dictionary into a table of some kind. But if you're doing a computation where order matters, you probably want to think of a different data structure, like a queue.

#

Thanks for including samples of the data you're talking about. You probably could have used even fewer rows for each so that your original question wouldn't be off-screen.

As I understand your question, you want to select the Symbol, Date, and Close/Last columns from each csv, regardless of what other columns exist in each csv, and put all that data in one csv?

This is a question for #data-science-and-ml, so ping me there if you want to continue with this question.

eager hamlet
#

but how do you like do this without it being near exponential

hollow quest
#

Hello!
I'm trying to sort data form a JSON file that I have that looks like this:

"cars": [
        {
            "190z": {
                "spawn": "z190",
                "speed": "75.12",
                "seats": "2",
                "acceleration": "67.50",
                "braking": "31.67",
                "handling": "69.70",
                "image1": "https://www.gtabase.com/images/gta-5/vehicles/sports-classic/main/190z.jpg",
                "image2": "https://www.gtabase.com/igallery/6301-6400/GTA5_190z_Online-6347-108.jpg",
                "real-life": "Datsun 240Z/Nissan Fairlady Z/Nissan S30, Toyota 2000GT",
                "class": "Sports Classics",
                "manufacturer": "Karin",
                "traction": "RWD",
                "price": "$900,000"
            }
        },
        {
            "811": {
                "spawn": "pfister811",
                "speed": "85.47",
                "seats": "2",
                "acceleration": "89.00",
                "braking": "37.33",
                "handling": "81.45",
                "image1": "https://www.gtabase.com/images/gta-5/vehicles/super/main/811.jpg",
                "image2": "https://www.gtabase.com/igallery/6401-6500/GTA5_Pfister811_Online-6412-108.jpg",
                "real-life": "Porsche 918 Hypercar, Koenigsegg Regera",
                "class": "Super",
                "manufacturer": "Pfister",
                "traction": "AWD",
                "price": "$1,135,000"
            }
        }, ```
It has more data like that in it but I want to store in another json file the cars sorted by manufacturers. Something like this:

```json
{
  "manufacturers":[{
          "Pfister":[{
            ["here a list with all the cars that have 'Pfister' as manufacturer with the specs above"]
]}
}```
#

One way that I was thinking about solving this is looping trough all the cars, see the manufacturer and if the manufacturer is of a certain value store the whole data accordingly. What I don't really know is to how get the whole car specs after I found a matching manufacturer.

fiery cosmos
#

help pls

agile sundial
#

what did you expect
if("Y")
to do

#

also, this isn't the right channel

fiery cosmos
#

got it

bronze sail
#

๐Ÿ˜’ every time I solve problem at hacker rank, and apply solution it works only for test inputs

wispy hare
#

is this what you're searching for?

eager hamlet
fiery cosmos
hoary bronze
#

can anyone recommend me a source that i can learn d-s in python ?

hollow quest
fiery cosmos
#

lambda: [] could be list btw, since list produces a new empty list

hollow quest
mint jewel
#

missing ]

#

on the line with the if

hollow quest
#

oh yes thank you! It got me really confused

ashen pilot
#

where can i ask help with a selenium related problem?

mint jewel
bronze sail
#

but for some reason, when I apply my solution it always fails ๐Ÿ˜•

hollow quest
#

Stumbled upon this error:
TypeError: list indices must be integers or slices, not str
On this code:

        with open('manufacturers.json') as json_file:
                temp = json.load(json_file)
                data = temp['manufacturers']
                sumspecs = manufact['manufacturer']
                for key in data:
                    if sumspecs in key:
                        data[sumspecs].append(specs)#error on this line
                        ```
Why?
`sumspecs = 'karin'`

JSON looks like this:
```json
{   
    "manufacturers":[
        {
            "Overflod": []
        },
        {
            "Vysser": []
        },
        {
            "BF": []
        },
        {
            "Unspecified": []
        },
]}
#

'karin' does exist in there but all I want to do is to put all the data that on the specs IN the Karin key.

#

Or whatever value the variable might have

wispy hare
hollow quest
#

And how can I manage that?

hollow quest
wispy hare
#

it depends on what you want to do

hollow quest
#

To append this specs in the matching key.
So it'd look something like this:

{   
    "manufacturers":[
        {
            "Overflod": [{
            "190z": {
                "spawn": "z190",
                "speed": "75.12",
                "seats": "2",
                "acceleration": "67.50",
                "braking": "31.67",
                "handling": "69.70",
                "image1": "...",
                "image2": "...",
                "real-life": "Datsun 240Z/Nissan Fairlady Z/Nissan S30, Toyota 2000GT",
                "class": "Sports Classics",
                "manufacturer": "Karin",
                "traction": "RWD",
                "price": "$900,000"
            }
        },
        }]
        },
        {
            "Vysser": []
        },
        {
            "BF": []
        },
        {
            "Unspecified": []
        },
]}```
wispy hare
#

try to replace if sumspecs in key by if sumspecs == key.keys()[0]

hollow quest
#

I get this error 'dict_keys' object is not subscriptable

wispy hare
#

if sumspecs == list(key.keys())[0] then

keen tusk
#

i had problem with my tkinter code

#

can i ask?

hollow quest
#

Still list indices must be integers or slices, not str on the data = temp['manufacturers'][sumspecs] line

keen tusk
#

i'm just getting an empty string in N,Ag and the rest

#

someone plz help

wispy hare
wispy hare
#

temp['manufacturers'] is actually a list of one-key dictionaries, it's different from a dictionary, this is why you're getting errors

#

dictionary:
{'a': 4, 't': 10, 'e': 3}

list of one-key dictionaries:
[{'a': 4}, {'t': 10}, {'e': 3}]

hollow quest
wispy hare
# hollow quest Yes, I see that but how can I solve it?

you can either convert it to a dict

for d in temp['manufacturers']:
  key = list(d.keys())[0]
  manuf[key] = d[key]```
or dealing with that list by knowing that you can't directly access by key, in the example I gave, you can't directly write `l['a']`, you first have to search for the dict whose key is 'a'
eager hamlet
calm mortar
trim fiber
#

Why you use while instead of for?

wispy hare
calm mortar
#

Show me the optimized solutions ! For loops welcome

shrewd cosmos
#

Hi

#

I have only two functions implemented so far

# 
    return point[i] + k

def decriment(i,k):
    return point[i] - k```
#

i was thinking of brute force but it looks like its gonna be too long. Could anyone please help?

wispy hare
wispy hare
shrewd cosmos
#

thank u. Lemme try

wispy hare
#

okay tell me if it's the right answer

shrewd cosmos
wispy hare
shrewd cosmos
wispy hare
shrewd cosmos
#

For a few test cases yes

#

Seems to fail 10^5

wispy hare
#

10^5 what?

wispy hare
shrewd cosmos
#

K=10^5

wispy hare
shrewd cosmos
#

Wdym?

wispy hare
#

like if we have [2, 3]

#

and k = 10^5

#

here the average 2.5, so our algorithm would subtract k from 3 and k to 2

shrewd cosmos
#

I see

wispy hare
#

but it just increased the difference

#

in this case we should add (or subtract) k for both

#

so I think that

shrewd cosmos
#

Any clue how to handle that ?

wispy hare
#

we should compare the difference between max and min and the difference between (max-k) and (min+k)

#

if different between max and min is smaller, we should add k to all elements (or subtract, as you want)

#

else, we do the average thing

shrewd cosmos
#

Thanks

#

It worked

small drift
#

can someone explain how the entropy formula works for decision trees? Ive watched videos on it, but its not helping so far.

glossy needle
#

hi i am new

#

i dont understand if condition pls help

wicked coyote
oblique panther
quiet viper
#

The police department is trying to use AI to detect which car license plates belong to stolen cars. Which of the following AI approaches is best suited?

oblique panther
quasi hinge
tawny shore
#

@calm mortar why not just ```py
def find(needle, haystack):
idx = haystack.index(needle)
return idx, idx + len(needle) - 1

calm mortar
#

@tawny shore that's nice! what's the runtime of str.index(str)

tawny shore
#

this details the implementation of str (its from py2, find is index in py3)

#

the algo is the same

eager hamlet
#

the editorial says use dp but idk how lol

calm mortar
#

@tawny shore In terms of run-time, it seems that your solution is no better

tawny shore
#

it should be just by the fact that it is running in C, not python

calm mortar
#

Maybe. That's arbitrary tho. The run-time seems to me that O(mn) is worst case performance, as per the last link you attached. However, someone earlier mentions KMP algo can be used for better performance.

tawny shore
#

that answer was explaining that str.index uses a slightly more optimized implementation (where the worst case is still the same)

cursive minnow
#

Hi, I have to give a presentation about sorting algorithms. It lasts 20 minutes. If you have interesting topics to cover feel free to post them. Thanks for your help!

bronze sail
#

Do you guys think, that using numpy is efficient for calculating minimal distance of the point? if the box will have very many points? ๐Ÿค”

def find_closest(pt):
    if len(pt) == 2:
        pt = [*pt, 0]
    elif len(pt) != 3:
        raise ValueError("Point has incorrect shape")

    pt = np.array([pt]).T
    dist = box - pt

    dist = dist * dist
    dist = dist.sum(axis=0)
    dist = np.sqrt(dist)
    hidist = np.min(dist)

    loc = np.where(hidist == dist)[0]
    loc = box[:, loc].T[0]

    return loc, hidist
brave oak
#

on if you want to do it for one point

#

or many points

#

if many points

#

you should find a data structure

#

that allows you to do this more efficiently

bronze sail
#

i want to find closest point of shape to my point, so its 1 and many, I was thinking about divide and conquer

#

F(find_closest) mean duration: 0.036 ms of finding one point

bronze sail
north cosmos
#

wow that's so cool

wild bobcat
#

Yeahh it supberb

bronze sail
fiery cosmos
bronze sail
#

is Pyrr better than numpy? its built on top of it ๐Ÿค”

bleak burrow
#

hi am sai a am 15 years old and i am learning python i want some friends to join me to learn python and do some program togeather

#

pin me if intrested

wary harness
#

Excuse me, good night, I'm from Peru and I have a question about how I can solve this problem. Implement an algorithm to find the permutations r of n elements.
I do not understand well the topic of functions

reef cliff
#

can someone help me with ga and pso

modern walrus
wet furnace
#

Hello!

#

May I ask about algorithm for machine learning here?

feral wadi
#

hey guys i do really suck in learning algos like greedy , dp what can i do to make it better?

#

i do understand the algos but what should i do to make it better ?

lost rampart
#

And then, you need to learn how to identify if a problem can be solved using DP

carmine anvil
#

Oh my god DP

#

Been trying problems for ages

#

Can't get the hang of it

wispy hare
carmine anvil
#

I try that, but formulating it as subproblems isn't always easy either

wispy hare
#

can you show me an example of a problem that you consider as hard to decompose into subproblems?

carmine anvil
wispy hare
#

I don't think that this problem needs decomposition into subproblems

#

we can do so

#

but I think that here it's not necessary since we are just asked to find the numbers of possible arrays, not generating them

carmine anvil
#

It's under the DP topic

#

And usually PnC tends to be DP

feral wadi
lost rampart
feral wadi
#

ohh i get it

#

well thanks dude.

fiery cosmos
# 
def insereaza_cifra_control(lista):
    lungime = len(lista)
    for i in range(0, lungime, 2):
        lista.insert(i + 1, cifra_de_control(lista[i]))
        lungime = len(lista)

lista = [10, 78, 8051, 91]

the list after the call should be
10 1
78 6
8051 5
91 1
why does it stops at 10 1 78 6 8051 91

void valve
#

I need a library that allows me to plot lines on a graph (does not need to be visualised) and count points in range of certain lines eg all points >= x+y. Does anyone have any experience with this or know of any librarys?

shut osprey
#

@fiery cosmos your call to the range function only runs once

#

it returns a range object

#

Changing lungtime after making that object won't change the range object

#

you are making the list twice as long though, so you can just multiply lungtime by 2 in your call to range

serene girder
#

hey, wondering if anyone can help me with ssml's pitch contour

#

i need to adjust the pitch of individual words, but ssml doesn't really support that unless using contour from my understanding

sage quartz
#

where can I find some good resources for classes?

vast spear
#

im makeing a menu for a mc name sniper and i dont know how i stop in from repetting

worn sun
sage quartz
#

Anything about classes would help a lot. I tried to learn Dijkstra's algorithm, but even though I understand the idea and I could memorize the code, I don't understand how classes work

round halo
#

where do you recommend learning datastructures and algorithms as a beginner

shrewd rampart
#

I dont know if this is the right place to ask competitive programming questions, is it?

brave oak
shrewd rampart
#

I saw this question in one of the job interviews, could not solve it. Still trying to figure out

๐Ÿ“Ž unknown.png
kindred sinew
woven girder
#

function with three parameters a, b, and c, which swaps the biggest one with the smallest one, and returns average of both swapped elements.

example: a=5, b=1, c=2 -> 3

[c++]

trim fiber
pearl schooner
woven girder
# pearl schooner do you need help writing that or are you just writing an algorithm?

I actually wrote it, but I need optimization now,

#include <stdio.h>
#include <stdlib.h>
#include <iostream>

using namespace std;

void swap(int *i, int *j) {
    int t = *i;
    *i = *j;
    *j = t;
}

void print_values(int x, int y, int z) {
    cout << "x=" << x << ", y=" << y << ", z=" << z << "\n";
}

float min_max(int x, int y, int z) {
    float avg = 0;
    if(x<y && x<z){
            if (y < z) {
                swap(&x, &z);
                print_values(x, y, z);
                avg = (x + z) / 2.0;
                return avg;
            }

            else {
                swap(&x, &y);
                print_values(x, y, z);
                avg = (x + y) / 2.0;
                return avg;
            }
    }

    else if(y<x && y<z){
            if (x < z) {
                swap(&y, &z);
                print_values(x, y, z);
                avg = (y + z) / 2.0;
                return avg;
            }

            else {
                swap(&y, &x);
                print_values(x, y, z);
                avg = (y + x) / 2.0;
                return avg;
            }
    }

    else if(z<y && z<x){
            if (x < y) {
                swap(&z, &y);
                print_values(x, y, z);
                avg = (z + y) / 2.0;
                return avg;
            }

            else {
                swap(&z, &x);
                print_values(x, y, z);
                avg = (z + x) / 2.0;
                return avg;
            }
    }

    return avg;
    
}

int main()
{
    float value = min_max(5, 1, 2);
    cout << value << "\n";
}
woven girder
#

how do I reduce it

pearl schooner
#

ah

#

i see what's your problem, why do you need to swap the nums?

woven girder
#

function with three parameters a, b, and c, which swaps the biggest one with the smallest one, and returns average of both swapped elements.

#

this is what they want

pearl schooner
#

alright, a crude-ish way you could do this is by passing in a vector<int>. in your function, you loop through each element in the vect. if element for index is > max val or < min val you set that as the min/max val and record the index. after the loop you swap v[max index] and v[min index] and return the avg of the two recorded vals

#

this is over complicating things but i really can't think of something that takes less code than this

fringe charm
#

Just one thing isn't this a python server ? Or can we post anything regarding dsa here ?

#

i'm a newbie here

bronze sail
bronze sail
zenith pagoda
#

I'm not sure if this is the right channel. In binary why the negate of 0 (i.e. ~0) is a series of 1s ?

agile sundial
#

because two's complement

gusty grove
bronze sail
gusty grove
#

yup! octrees are usually the way to go

#

or quadtree depending on your dimensions

bronze sail
#

quadtree? ๐Ÿค”

#

8 tree?

#

ah right, 2x2x2 is 8

noble vector
velvet plume
#

Hello!

#

I do not understand the question at all. If someone can run through a sample example with me...it'll be much appreciated

worn sun
worn sun
# velvet plume I do not understand the question at all. If someone can run through a sample exa...

Check out this video: https://www.youtube.com/watch?v=K2gLEnwW2ps It might help if you try to construct huffman encoding first and then do decoding

YouTube
IDeserve
Huffman Coding

Huffman Coding Algorithm is a lossless data compression algorithm. In lossless data compression, the originalย dataย can be perfectly reconstructed from the compressed data.

This algorithm is developed by David A. Huffmanย in 1952 while he was aย Ph.D.ย student atย MIT. This algorithm is widely used in mainstream compression formats such as JPEG, PN...

โ–ถ Play video
fiery cosmos
#

does windows have a problem with really big input lists or is the problem how I'm implementing my mergesort because when I try to sort a list of 1000000 numbers it just freezes

#

hmmm I think it's just too much for my code to do relatively quickly nvm

fiery cosmos
#

if anyone wants to schedule a weekly voice chat to discuss data structures where we review several on stream each week to learn, ping me and i'll set it up

fiery cosmos
#

Looks interesting

#

Do you have any pdfs on the same? Or any documentation?

dim dune
#

Any pair programming channel in here or something like that?

#

I would like to have a coding buddy that also do python while doing wfh.

rose shoal
fiery cosmos
#

As I mentioned yesterday in the #data-science-and-ml channel, I'm having some issues using SciPy's solve_ivp function. I posted the question on Stack Overflow to hopefully get some help. https://stackoverflow.com/questions/65632575/scipy-solve-ivp-fails-to-converge-for-large-system-of-ordinary-differential-equa

Stack Overflow
SciPy solve_ivp fails to converge for large system of ordinary diff...

I'm trying to use SciPy's solve_ivp function to solve a large system of coupled ODEs. The system of equations represent temperature, mass concentrations, and flows along a one-dimensional grid. The

stable pecan
halcyon plankBOT
#
Aye aye, cap'n!

Your reminder will arrive in 1 day!

ID: 1217, Due: 2021-01-09T17:10:37
stable pecan
#

i can try to look at it tomorrow

fiery cosmos
#

@stable pecan Thanks. Let me know if you have any questions or just ask them on the Stack Overflow post.

# 
>>> import struct
>>>
>>> struct.pack('i i f 3s', 1, 2, 3.5, b'abc')
b'\x01\x00\x00\x00\x02\x00\x00\x00\x00\x00`@abc'
>>>  
``` is that big endian ?
lean dome
#

struct defaults to your machine's native endianness. If you want big endian, you need to ask for it by starting the format string with >

#

!e ```py
import struct
print("big", struct.pack('>i i f 3s', 1, 2, 3.5, b'abc'))
print("little", struct.pack('<i i f 3s', 1, 2, 3.5, b'abc'))
print("native", struct.pack('i i f 3s', 1, 2, 3.5, b'abc'))

halcyon plankBOT
#

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

001 | big b'\x00\x00\x00\x01\x00\x00\x00\x02@`\x00\x00abc'
002 | little b'\x01\x00\x00\x00\x02\x00\x00\x00\x00\x00`@abc'
003 | native b'\x01\x00\x00\x00\x02\x00\x00\x00\x00\x00`@abc'
fiery cosmos
#

How do I get the point of intersection between two rectangles?

lean dome
#

The intersection of 2 rectangles is a rectangle, not a point

#

It's the rectangle bounded on the top by the topmost point that's in both rectangles, on the bottom by the bottommost point that's in both, on the left by the leftmost point that's in both, and on the right by the rightmost point that's in both

graceful cove
#

Hey, I'd like to change the args in a thread in "threading" package, change args during the course of the thread, before thread.start()
How do I do that ?

#

Actually it's just because I'd like to create my thread before, because it seems to take some time to create them all

#

And since my args are only there during runtime , id like to be able to change them then start them all !

lean dome
#

You have this backwards... Creating a threading.Thread without starting it is nearly free, it's calling start() that actually reaches out to the OS to do real work (create the OS thread) and is slow

#

On my machine, creating a Thread without starting it takes 0.0000057 seconds, according to the timeit module

#

That's 5.7 microseconds

quiet viper
eager hamlet
oblique panther
#

whether or not a decision made by an ai is "fair" depends on what one thinks of as fair.

kindred sinew
graceful cove
grand zenith
#

how to print character array using for loop in cpp

mild cape
#

Which part of that are you struggling with? Can you show what you tried @grand zenith

grand zenith
mild cape
# 
#include <iostream>
#include <cstring>

int main(int argc, char **argv) {
    const char *msg = "Hello world!";
    for(const char *c = msg; *c != '\0'; c++) {
        std::cout << *c << '\n';
    }
    
    size_t msg_len = std::strlen(msg);
    for(int i = 0; i < msg_len; i++) {
        std::cout << msg[i] << '\n';
    }
}
#

Here are two ways you might consider doing it.

pulsar imp
#

the index of the list

#

@fiery cosmos Have you ever worked with lists and indexes before?

#

It's rows

#

idk

#

I don't know how the module works

#

No problem

devout forge
#

Hello, i am looking for a good course, book about data structures and algorithms. Peak Finding, merge Sort, rolling hashes etc.

#

Maybe something that complements these lectures

mighty gorge
#

Hello friends, I am taking probability and statistics lessons. I need to write code in python. If someone knows can it help?

#

If someone knows can it help?

amber heart
#

can anyone explain me how to implement graphs in python?

mighty gorge
#

Hello friends, I am taking probability and statistics lessons. I need to write code in python. If someone knows can it help?

worn sun
fiery cosmos
oblique panther
bronze sail
#

how accurate are nearest search algos?

#

I got 2 plots, one saying green-ish good values, and red purple shadows of bad algo ouput,
and second plot, is that I beat pure matric multiplication over 11k elements

halcyon plankBOT
#

@stable pecan

It has arrived!

Here's your reminder: [#algos-and-data-structs message](/guild/267624335836053506/channel/650401909852864553/).
[Jump back to when you created the reminder](#algos-and-data-structs message)

halcyon plankBOT
#

:incoming_envelope: :ok_hand: applied mute to @agile compass until 2021-01-09 17:53 (9 minutes and 59 seconds) (reason: discord_emojis rule: sent 31 emojis in 10s).

agile sundial
#

nice

fading grail
#

I want to learn more about data science and data structure, do you know of any place or book where you have all the topics, or the knowledge base on these subjects?

worn sun
# fading grail I want to learn more about data science and data structure, do you know of any p...

Data Science and Data Structures are typically pretty different subjects and very broad. Data Structures tends to be how data is stored, most often referring to things like arrays, lists, trees, sets, etc... Typically you learn about Data Structures alongside Algorithms. I like Algorithms by Robert Sedgewick and Kevin Wayne, though I wouldn't really suggest it as a great sit down and read book, I'd suggest taking one of Coursera algorithms courses/specializations instead. For Data Science, are you thinking more data analytics, machine learning, statistics...?

gusty perch
#

Can I create a python program that detects whether the source code of another python program gets into an infinite loop

#

I want to make a dynamic debugger of sorts

mild cape
#

It's not possible to always be able to detect if there is an infinite loop.

trim fiber
#

@gusty perch Right, https://en.wikipedia.org/wiki/Halting_problem

Halting problem

In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist.
For ...

dire cipher
#

is there a way to sum all squared number rather than looping one by one?
1^2 +2 ^2 + 3^2 .... until >= given number

atomic kraken
#

for n numbers, sum of 1^2 + 2^2 ... + n^2 is equal to [n * (n+1) * (2n+1)] / 6 iirc

dire cipher
#

no, i meant until the sum is equal or greater than the given number

queen ruin
#

how do i play nice with the in keyword in a list of custom classes

class test:
   def __init__ (self,name):
      self.name = name
   #i need something here
x = [test('tom'),test('harry')]

print('tom' in x)
print('nottom' in x)
#

so i expect the output to be

True
False
#

(ping me pls)

frank fossil
queen ruin
#

tysm.. so ill need to override __contains__ to return true if the given str is self.name rit?

frank fossil
#

Yep

queen ruin
#

!e

class test:
    def __init__ (self,name):
        self.name = name
    def __contains__(self,item):
        return item == self.name
    
x = [test('tom'),test('harry')]
print('tom' in x)
print('nottom' in x)
halcyon plankBOT
#

You are not allowed to use that command here. Please use the #bot-commands channel instead.

queen ruin
#

oh..anyways, this does not seem to work..

#

says it's

False
False
frank fossil
#

@queen ruin

queen ruin
#

ohh __eq__ worked perfectly...tysm

atomic fractal
#

Hello guys,
im not sure if this is the right place to post this question, just tell me if im wrong here ๐Ÿ™‚

I got an Json file and i want to read it as a pyspark dataframe. The Json is nested and im not sure what is the best practice to get the data our of the json.

this is the Schema

 |-- payment_phase: array (nullable = true)
 |    |-- element: struct (containsNull = true)
 |    |    |-- credit: double (nullable = true)
 |    |    |-- month_of_prime: long (nullable = true)
 |    |    |-- user_id: long (nullable = true)```
 
1. way would be to use the Flatten function then drop element and root ? 
2. use Explode function 
3. explicit to get data out of the json and write it in a new DF
atomic fractal
#

swrong chanel for this topic ?

gusty perch
trim fiber
graceful cove
#

what do you guys use / recommand as a python GUI lib ?
I need it to represent lots of different datas with historic etc etc to be clearer than on a console

trim fiber
graceful cove
#

ty !

strange olive
#

command do I do on cmd to install something?

wraith valve
#

check if pip is on path

#

prob one of the most frequent causes of problems

radiant ridge
#

DAng oui you're a really nice guy

#

Really glad to meet you

tawdry shard
#

hey, can someone check what is wrong in this code?
start, end = 2, 7
for num in range(start, end+1):
if num % 2 != 0:
print(num, end = " ")

austere sparrow
#

!e

start, end = 2, 7
for num in range(start, end+1):
    if num % 2 != 0: 
        print(num, end = " ")
halcyon plankBOT
#

@austere sparrow :white_check_mark: Your eval job has completed with return code 0.

3 5 7
austere sparrow
tawdry shard
#

i just tested it in e-olymp and it says it is wrong and counted it as 0%

lean dome
#

the code does something, and does it successfully

#

without knowing what it's supposed to do, we can't know why it isn't doing that and is instead doing what it does.

austere sparrow
brittle spoke
#

hey

#

I want to learn python to analyze data on stocks. How do you guys think I should learn?

#

alr u can dm me ima gtb

trim fiber
fiery cosmos
#

aww yeah successful LDU factorization of any square matrix

#

the three matrices in the middle are factors of the matrix up top

fluid palm
#

hello

#

is there anyway i can get an index from a random row from a csv file?

#

like, say i have a csv of ten rows and six columns, is there any way for me to take a number from randint and take index zero from row randint?

trim fiber
halcyon plankBOT
#

You are not allowed to use that command here. Please use the #bot-commands channel instead.

trim fiber
#

Pff, randint(a, b) returns numbers in range [a; b] inclusive.

fluid palm
#

could i do this right after i call out csv.reader? or are there other prerequisites?

trim fiber
#

You can call randint whenever you want

fluid palm
#

then how about printing index 0 from the csv now that i have a line number from the randint?

fiery cosmos
#

!e

dynamic programming approach towards the solution

def canSum(target, numbers, memo = {}):
if(target in memo):
return memo[target]
if(target < 0):
return False
if(target == 0):
return True

for num in numbers:
    if(canSum(target-num, numbers, memo) == True):
        memo[target] = True
        return True
memo[target] = False
return False

here .... I have defined this thing in the jupyter... now I have impleameted multiple print statement executing the test cases.... instaed of the first one ... others are not working.... pls any one can help me?

halcyon plankBOT
#

You are not allowed to use that command here. Please use the #bot-commands channel instead.

fiery cosmos
#

!e

halcyon plankBOT
#

You are not allowed to use that command here. Please use the #bot-commands channel instead.

fiery cosmos
charred drum
#

hi everyone, can u help me?
I need a list that performs an arithmetic expression inserted by input
former. 2 * 2- (4 + 5) (2 + 3)

#

sorry about my english, im italian

#

with former i mean the example

agile sundial
#

what do you mean by list

#

do you just mean parsing a mathematical expression?

charred drum
#

take every element of the list and perform the operation

#

so we have: list=[element, operation, element, operation, operation, element....], something like this

#

how i can get a rapid solution to this? i knew by a function that solve the problem, but i cant use it

agile sundial
#

you could try parsing it using shunting yard

charred drum
#

i never use that

#

let me check on web

steep wadi
charred drum
dim summit
#

is kadanes algorithm the same as sliding window technique?

sudden phoenix
#

Hi!

#

Next week i have exam

#

is there any website where I can create Algos using blocks

#

and test them ?

agile sundial
#

blocks?

sudden phoenix
#

something like this

agile sundial
#

i don't know of any websites for that

#

there are definitely many websites where you can write code to solve algorithms questions

sudden phoenix
#

damn...

#

anyway

#

thanks for answer!

hallow vortex
#

Hi - I have a question for python (python3).
I'm confused by the following issue

#

For matrix transpose, I used naive solution for it, when I use set list of list with multiplication of row_length and col_length, it does not assign properly. Could anyone help me with this? I don't understand it why

wispy hare
#

and a list in Python is mutable

#

the problem is that all your rows have the same reference now, there is only one array in memory, this is why all of them have the same value

hallow vortex
#

Then when I use result=[[0,0,0],[0,0,0]] why does this works?

#

I'm not convinced that it is the same reference in this case.

brave oak
#

Then when I use result=[[0,0,0],[0,0,0]] why does this works?
@hallow vortex because then you have separate lists

fiery cosmos
#

I need some help with using SciPy ODE solvers. If anyone has experience, please see the #help-bread channel.

quasi trellis
ancient rock
#

anyone can help me for opencv disparity mapping
I am trying to understand parameters of StereoSGBM_create function

fiery cosmos
#

given 2 string, i need to compute the number of transpositions between them. what algorithm should i use?

hallow vortex
hallow vortex
wispy hare
fiery cosmos
wispy hare
#

oh okay

fiery cosmos
elfin shore
#

Hello is anyone here familiar with balanced Binary Search Trees, specifically the AVL tree

velvet plume
#

Hello!

#

Is anyone online here?

#

Here is my solution for it -

#

def decodeHuff(root, s):
string = []
position = root
for element in s:
if element==1 and position.right!= None:
position = position.right
elif element ==0 and position.left!= None:
position = position.left
else:
string.append(position.data)
position = root
print(string)

#

Please tell what am I doing wrong ๐Ÿ˜ฆ

runic tinsel
#

you're not stepping, when you append

# 
    string = []
    position = root
    for element in s:
        if element==1 and position.right!= None:
            position = position.right
        elif element ==0 and position.left!= None:
            position = position.left
        else:
            string.append(position.data)
            if element == 1:
                position = root.right
            else:
                position = root.left
    print(string)
```like this maybe
eager hamlet
#

any help? (ping 2 reply thx)

zenith pagoda
#

Hi, I'm trying to solve a bit manipulation problem. And the problem is

Given a positive integer, print the next smallest and the next largest number that have the same number of 1 bits in their binary representation .

The number given is 13948 which in binary 11 0110 0111 1100. The solution in the book gives that the next largest number is 13967 which in binary is 11 0110 1000 1111. My understanding is that the next largest number is 11 1111 1110 0000. Can someone help me to explain why the solution given by the book is different or if my understanding is wrong?

brave oak
#

explain your reasoning please

zenith pagoda
brave oak
zenith pagoda
#

So the book is wrong?

brave oak
#

no

#

the book is correct

#

your answer is wrong

#

I don't really see how what you said changes anything

runic tinsel
#

you understood it correctly then the book did it

#

you;re both right

half lotus
#

His answer would be correct if it wanted the largest possible number using the same number of bits

#

But the book seems to want to closest number to 13948 that is larger than it and uses same no of bits

brave oak
#

it says next largest though

runic tinsel
#

yeah, you want smallest larger

#

not largest larger

zenith pagoda
#

Oh

#

wait

brave oak
#

I didn't think of that

half lotus
#

"next largest" is kind of confusing terminology

zenith pagoda
half lotus
#

It implies that the current number is already the "largest" of something to me

zenith pagoda
#

The solution given by the book is not the next largest, isn't?

brave oak
#

huh.

#

maybe it's an idiomatic thing

brave oak
runic tinsel
#

that really makes no sense

half lotus
#

I don't think it's idiomatic I just think it can be read in a wrong way that can also be justified as correct in some twisted way.

#

it lends itself to that

brave oak
#

which suggests to me it's a regional difference

brave oak
brave oak
zenith pagoda
#

If the book wants the next largest number, then 11 0110 1000 1111 (13967) should not be the right answer, right? Because there could be a larger number than that with the same number of 1s and 0s. Example 11 1110 1000 1110 (16โ€‰014), and it is still consider next? Am I wrong?

brave oak
#

okay, let's use smaller numbers

zenith pagoda
#

How should I interpret it?

brave oak
#

say the given number is 4 (100). it has 1 1; imagine you list the numbers that come after it in binary...

5 - 101 (2 1s)
6 - 110 (2 1s)
7 - 111 (3 1s)
8 - 1000 (1 1)
#

in other words, if the input was 4, you'd expect 8

#

because it is the first number that is bigger than 4 and has the same number of 1s (1) in its binary representation

#

so "next largest", in this case, means "there is a sequence of integers with x 1s in their binary representation; what is the number immediately after 13967?"

zenith pagoda
brave oak
half lotus
#

I thought about it, it's confusing for 2 reasons

  1. When thinking about "largest", one tends to thing of a single value since its the superlative. There can only be one largest, and the rest are relatively smaller.
  2. If I gave you a sequence 1-5 and said 5 is the largest, then I could say 4 is the next largest i.e. the penultimate. In this case, "next largest" actually means a smaller number. This is what I mean when I said it implied the number is already the "largest" of something.

If it said "next larger" that would have been much clearer.

brave oak
#

"next largest" does indeed commonly mean "immediately preceding in magnitude"

zenith pagoda
brave oak
half lotus
#

Well since they say both smallest and largest I guess they may have been using it in that sense, but it's confusing since it's flipped. Anyway, I need to stop derailing this.

brave oak
#

the question doesn't say "same number of bits"

#

it says "same number of 1 bits"

#

nothing about the 0s

zenith pagoda
half lotus
#

The way to figure it out is to shift the right most 1 bit to the left

brave oak
brave oak
#

just think of listing the numbers after that in increasing order, counting the number of 1s in the binary representation, until you get the same vallue

zenith pagoda
brave oak
#

1101110 (110)

zenith pagoda
#

Wait. I don't really understand. How about 11 0110 0111 1100 ?

brave oak
zenith pagoda
#

Quite a bit. But when the number gets bigger I can't apply it anymore.

brave oak
#

in the case of 11011001111100 it is the same thing

# 
13948 - 11011001111100 (9)
13949 - 11011001111101 (10)
13950 - 11011001111110 (10)
13951 - 11011001111111 (11)
13952 - 11011010000000 (5)
#

so notice that at 13952 we carry the 1

#

and are left with 5 0s

zenith pagoda
#

Yes.

brave oak
#

now

#

the task is simple

#

we just need to replace 0s with 1s

#

as far on the right as possible

#

until we get 9 1s

#

because, as you said earlier

#

1s on the right are lower value than 1s on the left

#

so we just replace the rightmost 4 0s with 1s

#

that gives us 11011010001111 which is, of course, 13967

#

does that make sense @zenith pagoda?

zenith pagoda
#

Oh.

#

Yeah

#

hahaha

#

I understand now.

brave oak
#

okays

#

that's good

#

๐Ÿ†

zenith pagoda
#

Yes thanks.

brave oak
#

yw

zenith pagoda
#

Great

brave oak
#

same concept for going down

zenith pagoda
#

Ok.

#

Thanks again.

brave oak
#

no worries!

wispy hare
#

when converting n into bits, we have 3 cases:

fiery cosmos
#

Just started learning this area, had a friend give me the pointers to make these loops. How do you guys develop a brain for this stuff?

๐Ÿ“Ž unknown-20.png
#

Also laugh at my spaghetti

wispy hare
#

if the string is full of ones, we just insert a 0 after the first 1

#

example: 11111 -> 101111

#

else if we can split the bits into a part of ones and a part of zeroes (e.g.: 1111000), then the next number is 1 + the part of zeroes + 0 + the part of ones except the first one

#

example 1111000 -> '1' + '000' + '0' + '111' -> 10000111

#

else, we just replace the last zero before the last one by 1, and we replace the last one by 0

#

example: 10011011000 -> 10011110000

# 

def next_greater(n):
  bits = '{0:b}'.format(n)
  nb_ones = bits.count('1')
  if nb_ones == len(bits):
    return int('10'+bits[1:], 2)
  elif re.fullmatch(r'[1]+[0]+', bits):
    return int('1'+bits[bits.index('0'):]+'0'+bits[:bits.rindex('1')], 2)
  else:
    last_one = bits.rindex('1')
    last_zero_before_last_one = bits.rindex('0', 0, last_one)
    bits = list(bits)
    bits[last_one] = '0'
    bits[last_zero_before_last_one] = '1'
    return int(''.join(bits), 2)```
stiff pewter
#

Hello everyone. I'd like to write a tree structure so I can traverse it using this program. My python is a bit rusty, can you help me out?
Like in all the other problems I can copy the solution and if the input is an array I can just do array = [] and run the thing. Now, the input is not an arary, it's a binary tree stored as an object

๐Ÿ“Ž PythonThing.png
twilit locust
wispy hare
keen stump
#

@stiff pewter your code looks complete. Do you just want to make a function that sorts a list and stores the elements in the data dict in a valid tree?

stiff pewter
#

@wispy hare @keen stump My code is complete indeed. The functions are fine. The thing is that I want to test this code using this as
an input: ```js
{
"tree": {
"nodes": [
{"id": "10", "left": "5", "right": "15", "value": 10},
{"id": "15", "left": "13", "right": "22", "value": 15},
{"id": "22", "left": null, "right": null, "value": 22},
{"id": "13", "left": null, "right": "14", "value": 13},
{"id": "14", "left": null, "right": null, "value": 14},
{"id": "5", "left": "2", "right": "5-2", "value": 5},
{"id": "5-2", "left": null, "right": null, "value": 5},
{"id": "2", "left": "1", "right": null, "value": 2},
{"id": "1", "left": null, "right": null, "value": 1}
],
"root": "10"
}
}

#

My functions take a tree as an input, and that's the tree I want to execute the functions upon

#

If my functions were taking arrays as input for example I'd do: array = [1, ,4 6, 4, 2, 5,]. Now the input is not a function but a Binary search tree with this structure

wispy hare
# stiff pewter My functions take a tree as an input, and that's the tree I want to execute the ... 

class Tree:
  def __init__(self, val=None, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right

  def print_tree(self, indent=''):
    print(indent + str(self.val))
    if self.left:
      self.left.print_tree(indent + '----')
    else:
      print(indent + '---- None')
    if self.right:
      self.right.print_tree(indent + '----')
    else:
      print(indent + '---- None')

def by_id(dict, id):
  return [node for node in dict['tree']['nodes'] if node['id'] == id][0]

def dict_to_tree(dict, root_id=None):
  if root_id is None:
    root_id = dict['tree']['root']
  root = by_id(dict, root_id)
  left = dict_to_tree(dict, root['left']) if root['left'] is not None else None
  right = dict_to_tree(dict, root['right']) if root['right'] is not None else None
  return Tree(root['value'], left, right)

json_text = """{
  "tree": {
    "nodes": [
      {"id": "10", "left": "5", "right": "15", "value": 10},
      {"id": "15", "left": "13", "right": "22", "value": 15},
      {"id": "22", "left": null, "right": null, "value": 22},
      {"id": "13", "left": null, "right": "14", "value": 13},
      {"id": "14", "left": null, "right": null, "value": 14},
      {"id": "5", "left": "2", "right": "5-2", "value": 5},
      {"id": "5-2", "left": null, "right": null, "value": 5},
      {"id": "2", "left": "1", "right": null, "value": 2},
      {"id": "1", "left": null, "right": null, "value": 1}
    ],
    "root": "10"
  }
}"""

dict = json.loads(json_text)
dict_to_tree(dict).print_tree()```
stiff pewter
# wispy hare ```import json class Tree: def __init__(self, val=None, left=None, right=None...

That's not really what I want to do. I' just looking for a way to always be able and simulate coding interview questions on my PC so I can run them in the debugger and get better info. It's not just a one time thing so writing a program each and every time won't work. How do I represent the strucutre I showed you in python and use it as an input? Is that even possible in python ?

wispy hare
#

you need a function that transforms that array to a tree

stiff pewter
#

Hm, I see

#

Thank you very much

wispy hare
#

you're welcome

cursive sonnet
#

does anyone have a an explanation of jump point search for a*? all i can find are either people just using it, people explaining a* or very in depth code reviews

#

i'd like to know what happens and why q.q

keen stump
#

Anyone know any good algos/structs for sorting/searching posets? I made a sort of double linked list for posets with insert in O(n), but deletion is O(n^2) worst case and so is sort (which is just insertion sort). I am also searching for all the elements of the poset that are less than a certain value that is not in the poset, and my current search is worst case (and average I think) O(n)

jolly trellis
# keen stump Anyone know any good algos/structs for sorting/searching posets? I made a sort o...

There a pretty well known white paper on this
https://www.stat.berkeley.edu/~mossel/publications/POSET_SODA09.pdf
https://core.ac.uk/download/pdf/132271822.pdf
You can also try this video on topological sorting a poset
https://www.showme.com/sh/?h=qovixPc

ShowMe
ProfessorZer
A topological sorting of a poset

We construct a topological sorting of a poset, starting with the Hasse diagram of the poset. The example is inspired by what happens when you bake brownies.

lean glade
twilit locust
lean glade
#

I dont know what youre doing, the only thing I can tell you is that youre trying to access an empty array

eager hamlet
sharp steeple
#

anyone know about a server where hashing like base64 or rot13 is talked about?

trim fiber
sharp steeple
trim fiber
sharp steeple
trim fiber
#

You can use base64.b64decode to decode Base64

#

ROT13 you can write simply on your own

median hazel
fiery cosmos
cedar jacinth
#

@fiery cosmos well looks liek Steganography then

keen stump
#

@eager hamlet I didnโ€™t look at your problem too much, but it sounds very similar to boolean satisfiability, which is a famous NP-complete problem

eager hamlet
#

uh ok...?

half lotus
# wispy hare if the string is full of ones, we just insert a 0 after the first 1

If you're curious, here's a more generalised algorithm that doesn't rely on string manipulation. It's what I was alluding to yesterday by saying the right-most set bit needs to be shifted left.

def next_greater(n):
    current_bit = n & -n  # get the right-most set bit
    right_most_unset = 1

    while True:
        n &= ~current_bit  # unset the right-most set bit
        current_bit <<= 1  # left shift to move on to the next bit

        # End the loop if the next right-most bit is not set
        if not n & current_bit:
            n |= current_bit  # Manually carry over the set bit
            break
        else:
            # A bit was unset, so it has to be set elsewhere to preserve the
            # same number of set bits.
            n |= right_most_unset  # set the right-most unset bit
            right_most_unset <<= 1  # left shift to move on to the next bit

    return n

I wouldn't be surprised if there's a way to do it without a loop. Bit manipulation can get crazy. This is just what makes sense to me.

raw quest
#

Guys do you have any idea of basic problem which can be solve with genetic algorithm? Something like the tsp where you only have to deal with basic object as list

fiery cosmos
#

Hello everyone, is there any good sources you have for me to learn algorithms and data structures ?

#

and books or anything for me

raw quest
velvet plume
#

@fiery cosmos - If you are a complete begineer, I'd say look into some of the courses at Courseera or Udacity or Udemy

fiery cosmos
#

@velvet plume thank you I will be sure to check it out

fiery cosmos
half lotus
rustic valley
#

Hi guys some one help me please
I will write a python algorithm that circulates all its edges in an undetermined graph, which will return from U to V once from V to U.
if I change DFS, will anything come out?
what do you think I should add

fickle crypt
#

Is it possible to save data in json from python to use later

agile sundial
#

yes

fickle crypt
# 
import json

my_details = {
    'name': 'John Doe',
    'age': 29
}

with open('personal.json', 'w') as json_file:
    json.dump(my_details, json_file)
# 
Traceback (most recent call last):
  File "c:/Users/Penny/Desktop/py/GravityAdventures/json_test.py", line 18, in <module>
    json.load(after_loaded)
  File "C:\Users\Penny\AppData\Local\Programs\Python\Python38\lib\json\__init__.py", line 293, in load
    return loads(fp.read(),
AttributeError: 'dict' object has no attribute 'read'
#

is that bug or error

gusty grove
#

Swap the Arguments

brazen geyser
#

Having some problems with regular expressions using re and re.search. This seems to be my error message.

TypeError: cannot use a string pattern on a bytes-like object

# 
ifconfig_result = subprocess.check_output(["ifconfig", options.interface])
print(ifconfig_result)

mac_address_search_results = re.search(r"\w\w:\w\w:\w\w:\w\w:\w\w:\w\w", ifconfig_result)

if mac_address_search_results:
    print(str(mac_address_search_results))
else:
    print("no mac address.")```
#

my expression is also trying to filter for mac address.

fast salmon
#

What is the the type of ipconfig_result ? Can you cast it to a string /

teal birch
#

subprocess.check_output returns byte strings. You need to decode that byte string before passing to re.search

#

Is there any way to manipulate(like append, remove chars) strings without creating a new object every time? LikeStringBuilderclass in java or string class in c++.

half lotus
#

StringBuilder in Java just creates a new string anyway. Internally it has a character array that only gets converted to a string once you request it.

#

In Python, I believe f-strings are the most efficient method by which to concatenate strings.

agile sundial
#

you could use a list to store the pieces then join them together

half lotus
#

Yeah it's reasonable to assume that would perform better than f-strings if one needs to incrementally build the string.

#

Though probably only with relatively large lists

#

I've been surprised by benchmarks before

fast salmon
#

f strings provide the easiest way for string interpolation

#

However, it's a general pattern to keep things immutable as much as possible for easier bug tracking

half lotus
#

The syntax can be cumbersome in certain situations, like when incrementally building a string.

#

+= is much more convenient in that case syntax-wise

fast salmon
#

only works if it's the same type

fiery cosmos
#

helo anyone familiar with hash functions got a ctf from one and the answer and am trying to understand it

#

its a collision

brazen geyser
#

utf worked! thanks guys

green geode
timid owl
#

Why is OOP in python so weird, i mean compare Python to javascript:

class Car extends Vehicle {
  constructor(args) {
    super(args);
  }
}

class Car (Vehicle):
  def __init__(self, args):
    super().__init__(args)

I mean the first one seems like the best and most beginner friendly way

north cosmos
#

uh no?

atomic kraken
#

Looks basically the same to me

eager hamlet
eager hamlet
#

(ping 2 help thx)

fiery cosmos
#

I'm trying to find a Python implementation of Matlab's ode23tb solver. It is an implementation of the TR-BDF2 algorithm. SciPy doesn't offer a solver for this algorithm. Are there any other Python packages that have this type of solver? https://www.mathworks.com/help/matlab/ref/ode23tb.html

Solve stiff differential equations โ€” trapezoidal rule + backward di...

This MATLAB function, where tspan = [t0 tf], integrates the system of differential equations y'=f(t,y) from t0 to tf with initial conditions y0.

eager hamlet
#

(nvm i read the problem wrong lol)

wicked coyote
#

sooooooo

#

Need help on this problem, easy silver, basic graph theory

#

I get the problem all right, just not the solution

#

Any help would be much appreciated, been on this for hours ๐Ÿ˜ฆ

eager hamlet
#

usaco gang!!!!

eager hamlet
#

(also imo this problem is easier with dsu instead of graph theory)

wraith valve
#

@fiery cosmos does sci py have it?

#

i think julia or c/c++ libraries like sundials have significantly better integrators than scipy

fiery cosmos
#

@wraith valve No SciPy does not have an ode23tb (TR-BDF2) solver. Is there a Python version of Sundials?

wraith valve
#

@fiery cosmos i think they actually have a python wrapper

#

basically it python code but it calls c code in the background

wicked coyote
wicked coyote
# eager hamlet what don't you get about it?

so they binary search by finding the correct number of wormholes. The binary search takes log(n) time so i'm confused of how seeing if a certain number of wormholes will be enough take linear time. Sorry if this is a dumb question ๐Ÿ˜ฆ

wicked coyote
eager hamlet
eager hamlet
wicked coyote
#

I think so? I am very confused on this problem, so if you could explain the gist of the process they used that would be very helpful. I think they are binsearching for the correct number of wormholes, but I could be wrong.

fiery cosmos
#

There are n applicants and m free apartments.
Your task is to distribute the apartments so that as many applicants as possible will get an apartment.

Each applicant has a desired apartment size,
and they will accept any apartment whose size is close enough to the desired size.

Input

The first input line has three integers n, m, and
k: the number of applicants, the number of apartments, and the maximum allowed difference.

The next line contains n integers a1,a2,โ€ฆ,an: the desired apartment size of each applicant.
If the desired size of an applicant is x,
he or she will accept any apartment whose size is between xโˆ’k and x+k.

The last line contains m integers b1,b2,โ€ฆ,bm: the size of each apartment.

4 3 5
60 45 80 60
30 60 75

Out: 2

# 
n = int(input())
m = int(input())
k = int(input())


applicants = input().split()
applicants = [int(x) for x in applicants]
sizes = input().split()
sizes = [int(x) for x in sizes]

ans = 0

applicants = sorted(applicants)
sizes = sorted(sizes)

for applicant in applicants:
    if applicant in sizes:
        ans += 1
        sizes.pop(sizes.index(applicant))
    else:
        p1 = applicant - k
        p2 = applicant + k

        while p1 <= p2:
            if p1 in sizes:
                ans += 1
                sizes.pop(sizes.index(p1))
                break
            
            elif p2 in sizes:
                ans += 1
                sizes.pop(sizes.index(p2))
                break

            p1 += 1
            p2 -= 1

print(ans)
#

it gives me 1, why?

reef cliff
#

can someone send me a index/schedule like thing to learn dsa like in order

#

eg learn arrays, then something else that kinda thing

eager hamlet
fiery cosmos
#

๐Ÿ˜ฎ

#

wow, never thought of that

fiery cosmos
#

will sorting help

fiery cosmos
# 
Bit Manipulation
Recursion
Arrays
Searching
Sorting
Matrix
Hashing
Strings
Linked List
Stack
Queue
Deque
Tree
Binary Search Tree
Heap
Graph
Greedy
Backtracking
Dynamic Programming
Trie
Segment and Binary Indexed Trees
Disjoint Set
#

But personally, if you are a beginner, just start with a course on Udemy or follow a book

eager hamlet
#

an idea would be t go through all 1 mil colors

#

and see if they could be painted first

#

but that would involve

#

O(1) validation

#

so there's probably some preprocessing involved

#

any help? (ping 2 reply thx)

lean dome
# eager hamlet any help? (ping 2 reply thx)

You don't need to go through all 1 million possible colors, only the <= 1 million that actually appear on the final canvas. For each color that is on the canvas, if it does not form a contiguous rectangle, it must have been painted before any colors that interrupt that rectangle, so you can build up a list of which colors could not have been painted first: any color that falls between the top leftmost and bottom rightmost instance of another color can only have been painted after that other color, and therefore couldn't be first.

eager hamlet
#

well they could still give a test case where it's like 1000x1000, and then each color takes up 1 or 2 cells

lean dome
#

Actually, that's not quite right: any color X that occurs between the leftmost and rightmost column that another color Y occurs in, and that occurs between the topmost and bottommost row that Y occurs in, means X must have been painted after Y

eager hamlet
#

as long as it doesn't overlap anything, it could've been painted first, right?

lean dome
#

The only way for there to be 1 million distinct colors on the canvas is for each color to be in a single cell, which means none is interrupting any other and any one could have been painted first.

eager hamlet
lean dome
#

Right, don't special case it.

#

One loop over the input array can find you what colors occur in the canvas, and what the topmost row, bottommost row, leftmost column, and rightmost column each occurs in is. A second loop over the canvas can find you which colors interrupt another color. Your answer is the number of colors that don't.

#

If you need something faster, the simplest optimization would be that you can completely drop and ignore any color that occurs in a 1x1 or 1x2 or 2x1 shape after the first loop over the array. They cannot be interrupted by anything, so you don't need to check whether they've been interrupted.

#

If you need something faster than that, there's a data structure optimized for locating overlapping ranges... It's called an interval tree. I'm betting that's overkill here, though

fiery cosmos
#

anyone who knows a good source for greedy, backtracking, dynamic programming problems for python?

#

Eventually without graphs, trees, stuff like that

#

and eventually not CSES

fiery cosmos
# fiery cosmos anyone who knows a good source for greedy, backtracking, dynamic programming pro...

https://www.youtube.com/watch?v=oBt53YbR9Kk&t=18s really good and long video on DP.

YouTube
freeCodeCamp.org
Dynamic Programming - Learn to Solve Algorithmic Problems & Coding ...

Learn how to use Dynamic Programming in this course for beginners. It can help you solve complex programming problems, such as those often seen in programming interview questions about data structures and algorithms.

This course was developed by Alvin Zablan from Coderbyte. Coderbyte is one of the top websites for technical interview prep and c...

โ–ถ Play video
fiery cosmos
fiery cosmos
# fiery cosmos ^

The video is broken down into specific problem sections, you can skip any of the ones you want

wispy hare
fiery cosmos
wispy hare
agile sundial
#

dsa aren't a beginner topic in the first place, so i think it's fine

fiery cosmos
fiery cosmos
#

okay it s cool i guess

scarlet maple
#

i like that vid

#

bookmarked*

wraith valve
#

i mean recursive functions can be written as non recursive

#

but then i would say that knowing what it is would help alot with tree structures and such

austere sparrow
#

yeah, sort of

#

if it's a tail-recursive function, you can refactor it to a simple while loop

#

and if it's a non-tail-recursive function, you can keep track of the call stack yourself

#

!e
For example, here's an atrociously slow and silly way of writing the recursive solution to fibonacci with a loop

import re


def f(match):
    n = int(match[1])
    if n <= 1:
        return f"{n} "
    else:
        return f"{n - 1} fib {n - 2} fib "

def fibonacci(n):
    s = f"{n} fib"
    while "fib" in s:
        s = re.sub(r"(\d+) fib", f, s)
    return sum(map(int, s.strip().split()))

for i in range(20):
    print(fibonacci(i), end=" ")
halcyon plankBOT
#

@austere sparrow :white_check_mark: Your eval job has completed with return code 0.

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
austere sparrow
#

It works like this:

5
4 fib 3 fib
3 fib 2 fib 2 fib 1 fib 
2 fib 1 fib 1 fib 0 fib 1 fib 0 fib 1
1 fib 0 fib 1 1 0 1 0 1
1 0 1 1 0 1 0 1
#=> 5
bronze sail
austere sparrow
#

In Python, yes, that's generally true

bronze sail
#

just in python?

austere sparrow
#

Well, other languages can introduce optimizations that make recursive and non-recursive functions indistinguishable.

bronze sail
#

as I remeber my bench, recursion was almost twice as slow ๐Ÿค”

lean dome
#

if you have something that isn't tail recursive and you want to make an iterative version, you'd use a stack or a queue to track the intermediate results.

austere sparrow
#

...and in some languages, the only looping construct in recursion, so pretty hard to benchmark there

#

but those languages usually have those recursive optimizations

lean dome
#

C++ template metaprogramming falls into that category - no way to loop without recursion.

austere sparrow
lean dome
#

quicksort is a pretty good example of something that's usually faster when written recursively than iteratively. The extra work that you need to do in order to track the intermediate results is more than the extra cost of the recursive function calls.

austere sparrow
#

well, I guess it's just that the hardware stack is faster than a software stack ๐Ÿ™‚

lean dome
#

the call stack isn't exactly implemented in hardware - but there are specific assembly instructions that are primarily designed for manipulating it, so that's fair.

austere sparrow
#

yeah, the stack is still in RAM

fast flicker
eager hamlet
lean dome
eager hamlet
#

wait what's m

#

and even then when n could be as large as a million

lean dome
#

M is the number of colors that appear on the canvas but not as a 1x1 or 2x1 or 1x2 rectangle

#

if N is 1000000, then M is 0.

#

the only way for every color to appear on the canvas is if every color is used only in a 1x1 cell, so there are no colors that are not a 1x1 or 2x1 or 1x2 rectangle

eager hamlet
#

what about if N was say 100000

#

just 10^5

lean dome
#

the number of colors that a) appear on the canvas and b) do not only occur in a 1x1 or 2x1 or 1x2 configuration is strictly smaller than the number of colors that could appear on the canvas.

#

In the example the problem gives, M would be 4, while the total number of possible colors is 17 (including the 0 for "no paint")

eager hamlet
#

oh ok

fiery cosmos
#

Any dynamic programming lessons for Python?

scarlet maple
#

someone posted a really good video earlier

#

i bookmarked it for when i have time

scarlet maple
# fiery cosmos Any dynamic programming lessons for Python?

https://www.youtube.com/watch?v=oBt53YbR9Kk&t=18s&ab_channel=freeCodeCamp.org

YouTube
freeCodeCamp.org
Dynamic Programming - Learn to Solve Algorithmic Problems & Coding ...

Learn how to use Dynamic Programming in this course for beginners. It can help you solve complex programming problems, such as those often seen in programming interview questions about data structures and algorithms.

This course was developed by Alvin Zablan from Coderbyte. Coderbyte is one of the top websites for technical interview prep and c...

โ–ถ Play video
#

oh wait you said python

#

it uses JS but the same concept applies

#

especially the visualization portion of problems

#

that part would be the same

dreamy bay
#

Hi everybody, I'm new to Python so I'm not sure if a question relates to pathlib is suitable at this channel?

#

Somehow the output is not E:\test field\BAK\file
but I don't know why. Can anybody explain this to me? Thank you

from pathlib import Path

folderPath = Path("E:/test field")
fileList = folderPath.glob("*.tga")
for child in fileList:
    bakpath = folderPath / "BAK" / child
    print(bakpath)

Output:

E:\test field\T_M_M_Countess_Lace_2_Normal.TGA
E:\test field\T_M_M_Countess_Lace_2_OpacityMask.TGA```
wraith valve
#

@dreamy bay i prefer using os.path.join to append paths together

dreamy bay
#

well, I'm studying the pathlib because there will be some situation that I need to run the app on both unix/window environment. So its path is better

wraith valve
#

yeah os.path.join

#

is os independent

#

it uses a delimiter based on ur os

#

quite sure

#

at least thats how i made my bot in a windows enviornment and deployed in a linux one @dreamy bay

dreamy bay
#

yeah, I already did it successfully with os.path
I just trying to replace it with pathlib ๐Ÿ˜„

wraith valve
#

oh

fiery cosmos
scarlet maple
#

np

wispy hare
livid moss
#

def extract_did(line): for x in line: x = re.findall(r'\d+', line) return [x for x in x if len(x) == 10]

``def extract_did(line):
for x in line:
x = re.findall(r'\d+', line)

    if (x for x in x if len(x)) == 10:
        return x 
    else:
        return 0 
    ``

hello in first function i was able to get the numbers with len of 10
i made the 2nd function to return 0 if there's no numbers with len of 10
the 2nd function return all the numbers instead
Kindly help me where and how my 2nd function got wrong .
Apologies if this is not the correct channel for my question .

fiery cosmos
#

Why not \d{10} ?

tough stump
#

How can i code an random algorythm who create random math task like 11 + 4 or 6 + 9...?

dreamy bay
tough stump
#

Have you an examole?

livid moss
tough stump
#

*example

wispy hare
dreamy bay
# tough stump Have you an examole?

yeah, as like syph said: you can use random module to generate 2 random integer or float numbers

import random

a = random.randint(0,100)
b = random.randint(0,100)

print("{}+{} = {}".format(a,b,a+b))```
#

output

84+65 = 149
16+20 = 36```
stoic sluice
#

How can i code an random algorythm who create random math task like 11 + 4 or 6 + 9...?

#

Are you talking about 'how is random implemented' ?

#

If this is your question. the keyword you are looking for is 'PRNG', pseudo-random number generator

livid moss
# livid moss ``def extract_did(line): for x in line: x = re.findall(r'\d+', line)...

solved, i was able to extract the integers to different column, not the most efficient way though.

``def extract_did(line):
for x in line:
x = re.findall(r'\d{10}', line)
x = list(dict.fromkeys(x))
x = ' '.join(map(str, x))
return (x)

df['dids']= df.apply(lambda row :extract_did(row['comments']),axis=1 )
df['did1']=df['dids'].str.split(' ',10,expand=True)[0]
df['did2']=df['dids'].str.split(' ',10,expand=True)[1]
df['did3']=df['dids'].str.split(' ',10,expand=True)[2] ``

rose shoal
#

Hey, any good resources for learning data structures, algorithms in python after learning python basics ???

sage coral
#

How should I go about figuring out what tree search algorithm to use?

#

*In general

muted grove
#

Ill be using this channel one day, and ill understand this stuff... Not yet

autumn path
#

SO about trie, can anyone provide me a good resource for the thing. I am not able to find a good one.

quasi crystal
#

whats wrong in here

wispy hare
quasi crystal
#

then how do i do the program

wispy hare
#

You first need to convert them to integers to be able to perform the subtraction

quasi crystal
#

oh

#

ok

#

thanks

wispy hare
#

you're welcome

winter solar
#

hey guys. what's the equivalent of heapq's heapify for queue.PriorityQueue? I have an array i want heapified. should I just stick to heapq?

molten shale
#

Say I want to store words from dictionary to a tree and I want to show all words that starts with S, which tree should I store it to? AVL tree or BST?

eager hamlet
winter solar
eager hamlet
#

ah

#

i don't think so

#

is your program that performance critical?

winter solar
#

it's for learning purposes. just doing some leetcode stuff

eager hamlet
#

oh ok

winter solar
#

thanks anyway ๐Ÿ™‚

rare prism
#

Is there a way I can exclude 0 in a random interger?

random.randint(-16, 16)```
wraith valve
#

one approach would be to make a list of -16 to 16 without the 0

#

and do a random choice

rare prism
#

And kind of annoying if I expand the amount of numbers are all

wraith valve
#

yeah sth like range(-16,0) to generate the first part

#

and a range(1,17) for the second part

#

and add them together

#

eh its two parts and its longer than just randomint

#

it works i guess

rare prism
#

Okay

feral wadi
#

i have a doubt guys

# 
def fib(n,memo = {}):
    if n in memo:
        return memo[n]
    if n<=2:
        return 1
    memo[n]= fib(n-1)+fib(n-2)
    return memo[n]
print(fib(100))```
#

how does the memo stores the value ?

#

does it returns the value in recursion?

#

first the memo[n] = fib(n-1)+fib(n-2) works out and then it checks if n in memo and returns the value?

lean dome
#

Does that make it any easier for you to understand?

feral wadi
#

i can understand it and where it really confuses me is the dictionairy part memo[n]=fib(n-1)+fib(n-2) how does the dict stores the value ?

#

like if dict[5] = 4 + 3

#

doesnt dict works like

#

{4:5}

#

like that format ???

lean dome
#

!e ```py
d = {}
d[5] = 4 + 3
print(d[5])

halcyon plankBOT
#

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

7
lean dome
#

you can create a dict using d = {5: 7}, but you can update an existing dict using d[5] = 7

feral wadi
#

ohh i get it so whatver i am doing is updating the dict?

#

which is already created

lean dome
#

right

feral wadi
#

thanks for your help

#

can i ping you here if i got some doubt else ?

lean dome
#

I'd rather you not ping me with questions - ask in a channel, and if I'm online and trying to help people I'm sure I'll notice it.

feral wadi
#

yeah thanks no worries

wispy hare
feral wadi
#

so i can have an normal parameter?

#

`def fib(n, memo):
if n in memo:
return memo[n]
if n<=2:
return 1
memo[n]= fib(n-1, memo)+fib(n-2, memo)
return memo[n]

default_memo = {}
print(fib(100), memo)`

#

and implement code like this ?

wispy hare
feral wadi
#

oh i get that now

wispy hare
#

this implementation doesn't require you to create a dict before calling fib()

austere sparrow
#

Or you can make a function that takes another function and caches its result: