algos-and-data-structs

[lean walrus]

If it is for work you definitely should optimize it

Otherwise you are not a good worker

[tepid pivot]

Looking for study buddy , so we can start learning python “Data structures and algorithms “ together

[haughty mountain]

there are only a few cases
knights that block 0 squares (only appears for small k)
knights that block 2-4 squares (around corners)
knights that block 8 squares (everything in the center)

you can count the contribution from each

[urban kiln]

oh

i was able to do cases with n <=4 only

ok0 ty

[haughty mountain]

I think a neater solution could be starting with everything k²*8 and then subtract the invalid moves that goes outside the board

[urban kiln]

oh ok

ill just redo the question in a few days

[haughty mountain]

e.g. for k=6 I look at the border around the board and see how many squares inside the board can be reached

0112222110
1223443221
12......21
23......23
  ......
  ......
  ......
  ......

(ignoring the lower part of the board, the pattern is symmetric)

[urban kiln]

oh

[haughty mountain]

so 8k² minus the sum of all those

actually, maybe it's worth is just to count the moves in a particular direction

and then mult by 8, because symmetry

e.g all down-down right moves from + ends at a -

++++++
++++++
+±±±±±-
+±±±±±-
+±±±±±-
+±±±±±-
 ------
 ------

[urban kiln]

i thought grandmaster is an elo rank

[haughty mountain]

during the holidays cf has this thing where you can pick whatever rank for a few weeks

[urban kiln]

ah

[haughty mountain]

so (k-1)(k-2) squares can make a valid move down-down-right, which blocks another square

though I feel counting like this will overcount a bunch

hmm, I guess there will be a nice inductive way to derive the formula

[urban kiln]

the amount of legal moves is always even right?

0/2/4/6/8

0/2 moves is only on a board n<=3

4/6/8 is for any board n>=4

[haughty mountain]

3 is possible

..*.
X...
..*.
.*..
....

[urban kiln]

oh

ty

oh and 2 is also possible on a normal board

given a 8x8 board

cornors have 2 legal moves

a2 b1 a7 b8 g1 h2 g8 h7 have 3 legal moves

[urban kiln]

it knights were allowed to attack each other, would the solution be:
(n*(n-1))/2 ?
n = number of squares

and then subtracting all the positions which would attack each other

[haughty mountain]

yes

[urban kiln]

i think this problem isnt even that difficult

[urban kiln]

only n<=3 are special cases i think

[urban kiln]

edge was the outer part of a square right? or is it called border?

google translate is saying that the thing i want is called edge-border

but that doesnt sound right

[urban kiln]

i solved it

[finite siren]

I have to render a program which is on tree merge algorithm, and i have to turn this equation (picture 1 ) into merge tree. Here is the graphic representation of that tree ( picture 2 )

Picture 1

Picture 2

I already do that

But i'm stuck at the node part, because i don't have any idea of how translate picture 1 into code
Can someone please help me ? It's very urgent

[urban kiln]

i skipped it

time limit exceeded

and i dont know how the heapq library works fwhich i think is used for priiority queue

i havent done muc htoday

https://leetcode.com/problems/champagne-tower/ i want to solve this one

rn

but i havent started yet

and https://cses.fi/problemset/task/1092 (probably the easier one)

[haughty mountain]

that should just be about using a priority queue

doable in O(n log n) worst case

[crystal merlin]

def my_towers(N, from_tower, to_tower, alt_tower):
    """
    Displays the moves required to move a tower of size N from the
    'from_tower' to the 'to_tower'. 
    
    'from_tower', 'to_tower' and 'alt_tower' are uniquely either 
    1, 2, or 3 referring to tower 1, tower 2, and tower 3. 
    """
    
    if N != 0:
        # recursive call that moves N-1 stack from starting tower
        # to alternate tower
        my_towers(N-1, from_tower, alt_tower, to_tower)
        
        # display to screen movement of bottom disk from starting
        # tower to final tower
        print("Move disk %d from tower %d to tower %d."\
                  %(N, from_tower, to_tower))
        
        # recursive call that moves N-1 stack from alternate tower
        # to final tower
        my_towers(N-1, alt_tower, to_tower, from_tower)

why is this considerd divide and conquer?

don't you need to break it in half or something?

[urban kiln]

# set1 and set2 aren't actually sets, that's just how they were called in the question
if n % 2 == 0:
    set1 = [i for i in range(1, n+1) if i <= n // 4 or i > n // 4 * 3]
    set2 = [i for i in range(1, n+1) if n // 4 < i <= n // 4 * 3]

given these two list comprehensions(i think thats how it is called), i noticed that i am looping through one thing twice

would it be better:

for i in range(1, n+1):
  if ...: set1.append(i)
  else: set2.append(i)

[brazen python]

Which should I use if I expect the word to not be present most of the time (aka get a KeyError from the Trie Dict) ?

    def contains_word(self, word: str) -> bool:
        """
        Check if each character from the given word is present in the Trie Dict,
        and that the last node is marked as a keyword.
        (so 'mac' wouldn't be present if 'machine' is the only word in the Trie Dict)
        """
        node = self.trie_dict
        for char in word:
            node = node.get(char)
            if node is None:
                return False
        return node.get(TrieDict._word) == word

    def contains_word(self, word: str) -> bool:
        node = self.trie_dict
        for char in word:
            try:
                node = node[char]
            except KeyError:
                return False
        return node.get(TrieDict._word) == word

and I will be calling this thousands of times (once for each word in a sentence)

[sage flame]

https://leetcode.com/problems/longest-consecutive-sequence/solutions/127576/longest-consecutive-sequence/

In the third approach I'm still confused how it's O(n) and not O(n*n) cause of the while loop inside

[lean walrus]

If word is not present most of the time, then you will frequently handle occuring exceptions. Exception handling is slow (idk how much slow it is, if you want, i can provide some benchmarks).So i think it would be faster if you do it without try-except

[urban kiln]

is there a reason why this number is often used for modulo solution output

[lean walrus]

It is also easy to remember

[urban kiln]

oh

ok ty

[brazen python]

I suspected that an exception would slow down the program by a tiny bit, if you have some benchmarks on it I'd love to have a look at them

but the disadvantage with the first option is that I need to do this check on each iteration: if node is None: ...

[robust dagger]

I once benchmarked some code—a long time ago, so take this with a grain of salt—and found that if the key was not in the dictionary 50% the time, then using .get and testing for None was faster than try ... except. But if the key was not in the dictionary 1% of the time, then try ... except was faster than .get and testing for None. There's no perfect solution; somehow, on every iteration, you have to test whether the key was in the dictionary.

[clever fable]

if I have a bunch of data points that follow piecewise constant functions save for a few outliers (so for x=1 to x=a, y=some constant, then from x=a+1 to x=b, y=some other constant, etc. save for outliers) how do I find those outliers?

[robust dagger]

There is no reliable way to do this without assumptions on the outliers.

Or assumptions on the piecewise constant functions. Or something like that.

The problem is that, unless you know something about the outliers and the piecewise constant functions, you can't tell an outlier from a really short piece.

But if you have guarantees like, "Each piece of the function has length at least ..." or "steps between pieces are no larger than ... but outliers always differ from other values by ..." then you can get somewhere.

[urban kiln]

ive only done one question in the past few days because i was lazy

did some cses

[urban kiln]

https://leetcode.com/problems/distinct-prime-factors-of-product-of-array/description/
have you done this one?

https://leetcode.com/problems/closest-prime-numbers-in-range/description/
i wasnt able to solve this one

my code exceeded time limit since i tried getting all prime numbers between left and right

https://leetcode.com/problems/count-the-digits-that-divide-a-number/description/
this one was easy

We store those primes in a global array, so we can reuse it between test cases.
can stuff from an earlier test case be reused for another test case in leetcode problems?

[haughty mountain]

that's more leetcode weirdness

[haughty mountain]

getting all prime numbers <=10**6 can be done quickly

what are you doing to get them?

[urban kiln]

def isPrime(n):
    if n < 2: return False
    for x in range(2, int(n ** 0.5) + 1):
        if n % x == 0:
            return False
    return True

for all odd numbers between left and right

but maybe the looking for the closest numbers was bottlenecking

and i think the looking for prime numbers couldve been stopped as soon as 2primes with a difference of 2 were found

or if l=2 and r>3 then 2,3 would be the closest primes

[haughty mountain]

look into the sieve of eratosthenes

[urban kiln]

ok

and is math.sqrt() faster than **0.5 because alot of peoples solutions contain it

[vocal gorge]

time it yourself, they are probably all about as fast but I'd expect sqrt or isqrt to be slightly faster

there are other speedups you could do, like only checking odd numbers above 2

but ultimately it's a sieve task

[brazen python]

Hey guys, I'm working on a function that replaces a bunch of keywords from a given string.
Now I already have a function that iterates through all the keywords and tells the start and end position that needs to be replaced:

>>> kp.get_keywords  # keywords to replace
{'py': 'python', 'go': 'golan', 'hello': 'hey'}

s = 'Hello how are you? I love learning Py, aka: Python, and I plan to learn about Go as well'
>>> kp.extract_keywords(s, True)
[('hey', 0, 5), ('python', 35, 37), ('python', 44, 46), ('golan', 78, 80)]

The question is now that I know where and what to replace how do I go about doing that?
Maybe loop though all the chars and then do: new_sentence += char ...
or I can do list(s) and then simple assign all the ranges, i.e: list(s)[0:5] = 'hey', but from my limited knowledge about DS,
that will rebuild a list each time. any ideas? what do yall recommend?

[brazen python]

Im using a Trie Dict to replace all the values, this is the algorithm if you want to have a look at it (flashtext):
https://github.com/shner-elmo/FlashText2.0/blob/43406e2c8034f78ddf0d93f66a2187de45474e51/flashtext2/keyword_processor.py#L20

[high lintel]

Heyo, does anybody know how to change a specific element in a tuple which is a part of a list, and return the new list?

I don't quite get how to do it, i've tried referencing it's index, but it doesn't seem to be working.

[silent kraken]

I am quite new to Python but I am pretty sure Tuples are immutable

meaning that you can't change the elements

[high lintel]

Should I use a list instead?

[wicked frost]

Yes,
Once the tuple is created ,you can't change it.
If you want to alter the elements it is better to use list.

[fiery cosmos]

hiii

[silent kraken]

Hi

[thorn echo]

I gues you cam convert thsi tuple to list then change it and again reconvet it

[urban kiln]

is o(n!) ok for n <= 20

[haughty mountain]

!e

import math
print(math.factorial(20))

[halcyon plank]

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

2432902008176640000

[haughty mountain]

no, 20! is god damn huge

if you want to ballpark estimate, in a fast compiled language you might be able to do 10**8 to 10**9 cheap operations per second

!e

import math
print(math.factorial(20)/1e9/3600, 'hours')

[halcyon plank]

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

675806.1133824 hours

[haughty mountain]

so...no way

[urban kiln]

ih

oh

10fac is somethin like 3.6m right?

10!

!e

from math import factorial
print(factorial(15))

[halcyon plank]

@urban kiln :white_check_mark: Your 3.11 eval job has completed with return code 0.

1307674368000

[urban kiln]

!e

import math
print(math.factorial(13)/1e9/3600, 'hours')

[halcyon plank]

@urban kiln :white_check_mark: Your 3.11 eval job has completed with return code 0.

0.001729728 hours

[urban kiln]

ig 14!-15! is the max

oh compiled langs

[haughty mountain]

and it's a very optimistic estimate

[urban kiln]

ig 10!-12! is the max

12! ≈ 4.7 * 10^9

[nimble basin]

I'm trying to come up with an algorithm that finds the nearest RBGA value given a pixel input. I have exactly 1536 possible nearest points. I think what would work best is to find the nearest neighbor in each channel alone. As in find spot with nearest R value, find spot with nearest B value, same with G and A. Then I think I could just find which of those 4 is closest to my input pixel and go with that. Any thoughts on that approach? It saves me from doing time expensive trig to do 4th dimensional nearest neighbor searching.

Plotting the 1536 points has not been done yet because honestly that's a harder issue but I want to make sure this approach makes sense.

[nimble basin]

python string have a string.find(substring) method for finding substring locations within a string. It will output the starting location of the first instance of the substring found. I've done something sorta like what you're doing when coding a hangman game.

I hope that makes sense and helps? I kinda explained that poorly lol.

[ember igloo]

@nimble basin how is it not simply euclidean distance?

[nimble basin]

what is that

[haughty mountain]

how would that be much cheaper? how do you intend to find the closest points in R, G and B?

just iterating over points and checking?

[nimble basin]

starting at the input R, G, B, or A and going down until it finds something, then going up until it finds something, then choosing the closer of the two

[haughty mountain]

how would you implement that?

also, what expensive trig is it that you're trying to avoid?

you don't need any expensive operations to find the closest point in the usual euclidean distance

[nimble basin]

I have a big fucking list of all the points, I go through each set of RGBA and mark the first time one of those values are above my input pixel then after i've marked 4 points one for each value, I can grab that point and the one below it and save that location for comparison

I figured i'd use this for distance if I had to

this is what would be expensive lol

where input RGBA is the distance from the input pixel

so delta RGBA

[haughty mountain]

sqrt(R² + G² + B² + A²) is euclidean distance, but you don't need to compare that

you can compare the square of euclidean distance instead

[nimble basin]

how so?

[haughty mountain]

in math speech, because x² is monotonic, just like x

basically, if x and y are positive, then if x < y holds x² < y² holds as well

[nimble basin]

so I can cut out the square and square root parts and just sum for total distance?

[haughty mountain]

just summing isn't right

sum of squares

if you want to compare euclidean distance

R² + G² + B² + A²

[nimble basin]

gotchya

that would be pretty cheap then haha

[haughty mountain]

there are also nice data structures for doing nearest neighbor searches faster

[nimble basin]

I wanna do it all myself. I'm trying to use as few libraries as possible

[haughty mountain]

like kd trees and whatever one would call the 4d version of octrees

I mean, I didn't say use a library

[nimble basin]

oh I get what you mean

maybe i'll look into it

I think I will actually lol

may help me get a better sense of this

[haughty mountain]

though with 1.5k points you could just do the simpler thing

it's not that many points

[nimble basin]

no?

What would be many?

[haughty mountain]

10-100x of that maybe?

of course it depends on how much time you can spare to do computations

and how many times you need to compute this

[nimble basin]

once per pixel which the image size will be about 1000 x 1000 px

and then one image per frame

I'll probably do all the math BEFORE showing it though

for all the images

basically i'm making a video to colored ASCII program that works in cmd prompt

[haughty mountain]

oh, if so the rgba colors you compare against don't change?

then kd trees is a nice fit

[nimble basin]

correct they don't change

i'll look that up

i've never used a data structure before

this looks complex

[haughty mountain]

the idea isn't too weird

basically pick one axis (e.g. R), split it in two equal size halves

then for both halves keep halving (in varying axis directions)

computerphile did a pretty good video to introduce the ideas https://www.youtube.com/watch?v=BK5x7IUTIyU

[nimble basin]

thank you thank you

[brazen python]

I'm familiar with str.count and str.find, but the extract_keywords(sentence: str) -> list[str]: function from flashtext is much more powerful as it allows you to first split the string in words so you dont get substrings that arent words

the best alternative is regex, but its magnitudes of times slower

[umbral gulch]

[
[cat,dog,hamster],
[hamster,cat, turtle],
[dog]
[cat, dog]
]

[
[cat,dog,hamster],
[hamster,cat, turtle],
[dog]
[dog, turtle]
]

say you have these 2 arrays. and you wanted to pick one item from each inner array such that it does not appear in any of the other arrays.
as you can see from the top array, this is impossible because you cannot pick one item from each that does not appear in any of the other inner arrays. the closest you could get would be
[ [hamster], [cat], [dog], [dog] ] or [ [cat], [hamster], [dog], [cat] ]
but because dog/cat appears in 2 of the resulting arrays this is not a valid answer

however with the second array. it is possible to get 1 unique item from each inner array such that it does not appear in any of the other inner array
this answer would be
[ [hamster], [cat], [dog], [turtle] ] or [ [cat], [hamster], [dog], [turtle] ]
as you can see from these answers. there is a unique item in each inner array that does not appear in any of the other inner arrays

[broken tiger]

hey guys sup , i'm tryign to solve flow scedualing problem using genetic algorithm https://github.com/suyunu/Flow-Shop-Scheduling i already found a code but i can't understand much from it

can someone take a look please

i just have some questions about some parts of the code , what is this and that

[haughty mountain]

hamster, turtle, dog, cat for the top one?

this smells like a question about bipartite graphs

which is close to 2SAT

[urban kiln]

if int(per_team) != per_team: return -1
is the above way slower than:
if per_team % 1 != 0: return -1

[frank bluff]

!e

from timeit import timeit

tests = ["not x.is_integer()", "x % 1 != 0", "int(x) != x"]

setup = "x = 0.5"
exec(setup)
for test in tests:
  print(eval(test), timeit(test, setup))

setup = "x = 1.0"
exec(setup)
for test in tests:
  print(eval(test), timeit(test, setup))

[halcyon plank]

@frank bluff :white_check_mark: Your 3.11 eval job has completed with return code 0.

001 | True 0.05052291299216449
002 | True 0.09663061890751123
003 | True 0.1375825849827379
004 | False 0.042399035999551415
005 | False 0.09298638999462128
006 | False 0.14875313104130328

[urban kiln]

oh thats how you time stuff

[frank bluff]

while it is slower, it shouldn't matter
these are the times for running those tests 1 000 000 times

[urban kiln]

ok

[frank bluff]

but I'd probably stick with not x.is_integer() to make it easier to see what you're doing

[urban kiln]

oh ok

[prisma sky]

damn i am currently working on a qr code maker (i’m making it from scratch), and i hit a roadblock with the error correction codeword generation. basically i need to find a way to handle multi variable polynomials eg. x^2*y^3. I need to be able to somehow store it, and multiply it by another polynomial. Any ideas?

[robust dagger]

I'm familiar with a related problem. You said you were trying to avoid libraries; I wasn't, so I was able to use the k-d tree implementation in SciPy. I was working with 2^24 points, and it went plenty fast for me. I wrote a little about this at https://chromophile.readthedocs.io/en/latest/design/approximation.html, though most of that page is about other issues. The actual code is at https://github.com/kylehofmann/chromophile_dev/blob/main/src/chromophile_dev/conversion.py but it's mixed with a ton of other stuff, so it's kinda hard to read.

[ember igloo]

this is like a graph colouring question, each array is a node and each allowed colour for a node is an animal, and @haughty mountain is right in that its related to n-partite graphs because a graph is n-colorable iff it is n-partite

but the issue is some nodes don't have options to some colours

for example array 1 in the first example doesn't have a turtle

well that's easily remedied

by adding a turtle-colored node adjacent to the first array

so you could construct this alternative graph

and form it as a proper n-colorability problem

where n is the total number of animal types

and then run whatever the state of the art coloring algorithm is

[haughty mountain]

it feels like an easier version of the assignment problem, which is already a not so hard problem

the assignment problem is to optimize overall cost

while this is just about some assignment existing

[ember igloo]

it's NP-hard

for existence

[haughty mountain]

I guess you could throw the hungarian algorithm on it and it would work, though it's using a sledgehammer on a nail

[ember igloo]

but it's a very well studied problem

[haughty mountain]

the assignment problem is in P

[ember igloo]

what's the assignment problem

[haughty mountain]

https://en.wikipedia.org/wiki/Assignment_problem

[ember igloo]

🤔

ooo

yeah it's not NP-hard for k=0,1,2

assignment problem is k=2

heh my brain is melting trying to intuit whether the problems are comparable

[haughty mountain]

basically you could reduce it to the assignment problem with matrix

#
        1 2 3 4
cat     1 1 0 1
dog     1 0 1 1
hamster 1 1 0 0
turtle  0 1 0 0

[ember igloo]

oh am i simply wrong

[haughty mountain]

and you can ask whether there exist an assignment with weight >=4

but I'm sure there will be better algos than reducing it to this

[ember igloo]

yes i think i reduce it to class of slightly modified complete graphs

which is not the same as the n-colouring problem which considers arbitrary graphs

[nimble basin]

This will help greatly, thanks.

[random finch]

I need to decrypt it

The algorithem takes a number of rows and a string and encrypts it in the way showed

[haughty mountain]

this will loop forever if the element doesn't exist

oh wait...

you do an O(n) check before the binary search...

don't do that...

and will this even work if the element you're looking for is the last one?

I tend to write something like

l = 0
r = len(numbers)
while r - l > 1:
  mid = (l + r)//2
  if target < numbers[mid]:
    r = mid
  else:
    l = mid
# if numbers[l] == target, you're good
# else it doesn't exist

[urban kiln]

!e

from math import factorial
print(factorial(120) > 120''120)

[halcyon plank]

@urban kiln :x: Your 3.11 eval job has completed with return code 1.

001 |   File "<string>", line 2
002 |     print(factorial(120) > 120''120)
003 |           ^^^^^^^^^^^^^^^^^^^^^^
004 | SyntaxError: invalid syntax. Perhaps you forgot a comma?

[urban kiln]

!e

from math import factorial
print(factorial(120) > 120**120)

[halcyon plank]

@urban kiln :white_check_mark: Your 3.11 eval job has completed with return code 0.

False

[urban kiln]

oh bruh

that was obvious

my bad

[jolly mortar]

yes

[broken tiger]

anyone knows genetic algorithm

[shy path]

I'm currently tackling the following problem and need some help.

I am given a coordinate on in a grid (2x2 array) with a radius, r. I need to iterate through all of the points in the grid that are at most r moves away from the given coordinate (no diagonal moves allowed).

Example:

• given coordinate (4, 2) and radius 3
• 1s below show the points I need to iterate through

[[0 0 0 0 1 0 0 0 0 0 0]
 [0 0 0 1 1 1 0 0 0 0 0]
 [0 0 1 1 1 1 1 0 0 0 0]
 [0 0 0 1 1 1 0 0 0 0 0]
 [0 0 0 0 1 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0]]

Any thoughts on how to efficiently do this?

[vocal gorge]

something like

for di in range(-r,r+1):
    for dj in range(-r+abs(di),r-abs(di)+1):
        

would do.

[shy path]

Perfect! Thanks

[urban kiln]

(lines should be straight ik)
given 3 points, is it the law of cosines which is used to determinate the angle?

[vocal gorge]

plenty of stuff you could use, but sure, that'd work

e.g. if you don't care about phi vs -phi, you could take the scalar product of the BA and BC vectors and that's the cosine of the angle

[urban kiln]

hmm ok

[opal oriole]

Law of Cosines or stuff that comes from it / another way of writing it, such as the dot product (geometric).

Or other trig identities, some will be more roundabout than others.

[opal oriole]

The lists I could find don't seem to go past 1/12, so IDK, sedectree/sexdectree/hexadectree?

(The fractional names don't mirror the none fractions, so I think it just needs to be made up)

[midnight pivot]

hey i got a problem when manipulating list, i do a copy of it because i will delete things, intentionally, and reset it when i need but i found that the thing i deleted in the first list got deleted in the copy too, pls help

[urban kiln]

def distance(x1, y1, x2, y2):
    return ((x2 - x1)**2 + (y2 - y1)**2)**0.5
```this is the correct way to calculate the distance between two points right?

[vocal gorge]

that's a correct formula for euclidean distance, sure. though you could have used math.dist or math.hypot.

[urban kiln]

oh

i didnt know that those existed

ig buildins are optimized

[haughty mountain]

because you didn't make a copy

!e

x = ['orig']
same_list = x
copy = x.copy()
slice = x[:]

x[0] = 'new'

print(f'{x = }')
print(f'{same_list = }')
print(f'{copy = }')
print(f'{slice = }')

[halcyon plank]

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

001 | x = ['new']
002 | same_list = ['new']
003 | copy = ['orig']
004 | slice = ['orig']

[midnight pivot]

Thanks

Wth is up whit that anyway

[haughty mountain]

assignment never copies

it just gives a new name to something

so you have two names for the same list

[urban kiln]

i want to know if
var >= 90

but var is a calculation with floats

i was wondering if the float claculation inaccuracy only makes numbers bigger(like real sol + 10**-10)

or can the solution be smaller due to float inaccuracy than it should be

[haughty mountain]

it can go both ways

basically if you check float equality you're likely doing something iffy

and you should check if it's close enough

[urban kiln]

ok

ty

ig ill try to change something

[haughty mountain]

and generally if you can use ints and avoid working with floats that's preferable most of the time

since you know int calculations are always exact

[urban kiln]

ill try to find a different approach

[queen furnace]

Can someone help me this code:
`def pancake_stack(syrup):
soaked_pancakes = []
for i, pancake in enumerate(syrup):
if syrup[i] > 0:
soaked_pancakes.append(1)
else:
soaked_pancakes.append(0)
return soaked_pancakes

print(pancake_stack([0, 0, 2])) # should print [0, 1, 1]
print(pancake_stack([0, 0, 0])) # should print [0, 0, 0]
print(pancake_stack([0, 0, 3])) # should print [1, 1, 1]`

It's displaying wrong values

[rocky tree]

what is the logic?

[rocky tree]

tell how the first example is supposed to work

[agile sundial]

ig the syrup soaks down the stack?

[rocky tree]

then the parmeter should be single number instead of a list

[agile sundial]

not if you can have an input like [0, 2, 0, 2]

[rocky tree]

hmm

this seems pretty simple but depends on what is being expected

[haughty mountain]

or the more interesting case
[0, 2, 0, 0, 2] -> [1, 1, 0, 1, 1]

[urban kiln]

    for i in nodes:
        for j in nodes:
            if i != j:
                i.distances.append([math.dist((i.x, i.y), (j.x, j.y)), j])
        i.distances = sorted(i.distances)
``` is this just O(n^2) ?

class Node:
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.distances = []
``` this is the node class

[haughty mountain]

O(n² log n) with the sorting

[urban kiln]

oh ok

[agile sundial]

why is that more interesting?

[haughty mountain]

it shows that things happen independently

[agile sundial]

I thought that's what mine did also

[haughty mountain]

yours looks the same as [0, 0, 0, 4]

[agile sundial]

fair enough

[haughty mountain]

I suspect [0, 2, 2] is an interesting one to know the answer of

idk if the answer should be [2, 1, 1], [1, 1, 1] or [1, 2, 1]

I expect the first one, but we don't know the problem formulation

[urban kiln]

the time complexity of the nearest neighbour approach in tsp is O(n^2) right?

[wise kernel]

def min_max(position, turn=True):
    filled = True
    num_1 = 0
    values = []
    for row in position:
        num_2 = 0
        num_1 += 1
        for space in row:
            num_2 += 1
            if space == "-":
                filled = False
                dupe = position.copy()
                dupe[num_1][num_2] = get_turn(turn)
                num_3 = min_max(dupe, swap_turn(turn))
                values.append(num_3)
    if filled:
        # return 100 for win -100 for loss and 0 for draw
        print(position)
        return check_if_game_over(position.copy())
    if turn:
        return max(values)
    return min(values)


def check_if_game_over(board):
    # returns either 100 for win -100 for loss or 0


def get_turn(turn):
    if turn:
        return "x"
    else:
        return "o"


def swap_turn(turn):
    if turn:
        return False
    else:
        return True

I have this minimax bot for tic tac toe

but now im hitting my max recursion limit 😐

it tried this

import sys
sys.setrecursionlimit(1000000)

but now i get this

Process finished with exit code -1073741571 (0xC00000FD)

[agile sundial]

changing the recursion limit is not the solution

[haughty mountain]

yeah, if you hit recursion limits here you have a bug

your depth should go to like...9

[urban kiln]

checking if an item is in a set is O(1) right?

[broken tiger]

any one knows genetic algorithm

or flow shop scheduling problem

[urban kiln]

can there be different starts in tsp nearest neighbour approach depending on where you start?

[urban kiln]

for tsp:
should i jsut make a MST and return the first value which is n% close to it or should i just return the best value after n attempts

i mean the improvement:time will get less and less and there wont be big improvements after being like 15% close to the mst value

[haughty mountain]

why not just ask the question in this channel? so anyone might look at it and help

[haughty mountain]

idk much about heuristics/approximations about TSP, I'm assuming that's what you're trying to do?

I recall an MST being involved in some approximation

like, the optimum is <= 2*MST

[urban kiln]

yes

(a**2 + b**2 - c**2) / (2 * a * b) can this even return > 1

im trying to find out if it is a problem with floats or if i implemented it wrong

1.0000000000000002
probably a float problem

[haughty mountain]

yes? you can easily make that happen
a=3, b=1
(10 - c²)/6

this is >1 for a bunch of c

[urban kiln]

hmm

the values are the length of the sides of a triangle

wait

forgot to say that sry

[haughty mountain]

well, it's >= -1, idk how interesting that is

c <= a + b  # triangle inequality

   (a² + b² - c²) / (2ab)
>= (a² + b² - (a + b)²) / (2ab)
 = (a² + b² - (a² + 2ab + b²)) / (2ab)
 = -2ab / (2ab)
 = -1

[urban kiln]

it was the formula which was on law of cosine wikipedia

idk how it works and why it works

[haughty mountain]

oh, if it's used in arccos then it better be between -1 and 1

[urban kiln]

yea

rechnung = (a**2 + b**2 - c**2) / (2 * a * b)
if rechnung > 1: rechnung = 1

ill just do this now

[haughty mountain]

but yeah I would have recognized
c² = a² + b² - 2ab cos γ

yeah, clamping the value should be fine

[urban kiln]

ty

[haughty mountain]

you're german?

[urban kiln]

yes

[haughty mountain]

it's always interesting seeing non-english names in code 😛

[urban kiln]

yea

i normally use english variable names

[haughty mountain]

I would probably call it cos_gamma or something rather than just calling it calculation

[urban kiln]

but i used german names for this one because i have to write a documentation in german about it later which will make it easier to read i think(staying in one language)

[urban kiln]

ok

[haughty mountain]

cos_gamma makes it a lot clearer what it actually is, and why the value should be between -1 and 1

[urban kiln]

ah ok

👍 t

y

[urban kiln]

https://leetcode.com/problems/maximum-ice-cream-bars/description/
how is this a medium problem

@cobalt mirage have you done this one?

wait i dont have to sort the list?

oh

ah

if sum(costs) <= coins: return len(costs) is sum() O(n)?

yea

ah u mean o(n) for space?

huh

most of the solutions do the same as i

yea ik

oh bucketsort is O(n)?

idk how to use that

ig

[haughty mountain]

as mentioned, you can make it O(n + k) where n is the number of ice creams and k is the range of prices

calling this O(n) is a bit iffy since it has another scaling

There is a better than O(n log n) solution even if the costs are allowed to be large, you can get the smallest m elements in either O(n + m log n) or O(n log m) time (with different space requirements for the two options)

Both those option would be using a heap, in slightly different ways

So you can have a solution that scales with the answer

[haughty mountain]

sort and then some sliding window stuff?

my first idea:

1. sort
2. sliding window to get the largest valid interval starting at each index i (call it A)
3. go backwards through A and compute the largest interval starting at i or later (call it B)
4. go forwards through A and try each interval starting at i, and look in B for the largest window starting at or after i + size
5. the max combined size you find in 3 is your answer

why is their N so small if there is an N log N solution?

50000 is quite small for N log N

you could probably squeeze in N sqrt N or something with so small input

when I want to make ballpark runtime estimates I assume you can do 10**9 cheap operations in 1s

(in a compiled language)

!e

from math import *
n = 50000
print(f'{n*log(n) = }')
print(f'{n*sqrt(n) = }')
print(f'{n**2 = }')

[halcyon plank]

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

001 | n*log(n) = 540988.9142205141
002 | n*sqrt(n) = 11180339.887498949
003 | n**2 = 2500000000

[haughty mountain]

so 1 and 2 seem feasible

3 not so much

it's good for knowing roughly where to aim complexity-wise

[hollow remnant]

algos

[nova hazel]

hi I have a question about numpy

I understand that np.random.rand() produces random numbers from 0 to 1 but if i type in np.random.rand(150) does the numbers that i produced add up to 150?

[covert thorn]

no, you just get 150 random numbers

[nova hazel]

thanks

[covert thorn]

!e

import numpy
a = numpy.random.rand(5)
print(a, sum(a))

[halcyon plank]

@covert thorn :white_check_mark: Your 3.11 eval job has completed with return code 0.

[0.49536493 0.10583609 0.86184596 0.02234967 0.39323677] 1.8786334225826695

[nova hazel]

ohh

doesnt even get over 2

[covert thorn]

i would guess that the sum of n random elements follows a normal distribution (aka a bell curve), with an expected value of n/2

turns out it's called an irwin-hall distribution, but it does approach a normal distribution as n increases

[nova hazel]

thanks and im sorry i didnt respond

[haughty mountain]

to be fair, most things do

as per CLT

https://en.wikipedia.org/wiki/Central_limit_theorem

[tiny briar]

has anyone here ever done nand2tetris? i have a question about how the Hack Stack Machine is supposed to work.

given the following code:

push constant 5
push constant 7
sub

i'd expect that the answer would be "2", but their VM emulator shows "-2" instead. Why?

if we pop the top 2 arguments off the stack we get [7, 5] so why is the subtraction method doing 5 - 7 instead of 7 - 5?

I was expecting to be able to implement a stack in python using a simple list, and use .append() and .pop() to simulate a stack, but I"m guessing that's too naive an assumption?

[tiny briar]

also, would division work the same way? if the operation were div instead of sub would it be doing it be 5 / 7 and not 7 / 5?

[past gyro]

I am trying to simulate key presses for the symbols:

    '~': 0x29,
    '!': 0x02,
    '@': 0x03,
    '#': 0x04,
    '$': 0x05
}```
With the function below:
```def KeyPress(key, intervals=0.01):
    hexKeyCode = VK_CODE[key.lower()]
    extra = ctypes.c_ulong(0)
    ii_ = Input_I()
    ii_.ki = KeyBdInput(0, hexKeyCode, 0x0008, 0, ctypes.pointer(extra))
    x = Input(ctypes.c_ulong(1), ii_)
    ctypes.windll.user32.SendInput(1, ctypes.pointer(x), ctypes.sizeof(x))```
So when I use the function
```KeyPress('$')```
It returns
```4```

[urban kiln]

whats that

[urban kiln]

for the tsp greedy algorithm, does it matter at which node you start

!e

from math import log
n = 120
print(n**2*log(n, 2)//1) # if it doesnt
print(n**3*log(n, 2)//1) # if it matters

[halcyon plank]

@urban kiln :white_check_mark: Your 3.11 eval job has completed with return code 0.

001 | 99459.0
002 | 11935106.0

[jade mountain]

If we have 100 numbers between 33-126 in float value
We make a Fibonacci sequence out of some numbers between 100-200 we get some values we then implement those numbers to existing numbers we get a extra number that does disagree pigeonhole principle cuz the values we got are more than the amount of values we inserted we get a cool random digit

Crazy encryptor can be made using pigeonhole principle violate

[vocal gorge]

i don't see a single questionmark here

[jade mountain]

Ah sorry i added the question here

[haughty mountain]

I have no clue what's trying to be said there...

[proven citrus]

Sup!

Anyone currently here?

def myPow(self, x: float, n: int) -> float:
def yourPow(x,n):
if x == 0:
return 0
if n == 0:
return 1
res = yourPow(x * x, n // 2)
return res * x if n % 2 else res

    res = yourPow(x, abs(n))
    return res if n >= 0 else 1/res

having some problems with recursion

how does res every have a value other than 1

ping me when replying

[agile sundial]

it's like what you get when you google translate the same thing a bunch of times. the words are recognizable, but there's no content

[ember igloo]

shouldn't it be

            res = yourPow(x * x, n - 1)

you multiplied by a factor of x, so your exponent decreases by 1

[urban kiln]

but after the third run its x^2^2 and not x^3 ?@ember igloo

[ember igloo]

you're right, you would have to pass the base along too

[haughty mountain]

no, the thing used is that x**(2*n) == (x**2)**n

I'm pretty sure the code is correct

[proven citrus]

Nope

The code is perfectly correct

I am not asking its correctness i am asking how?

How does pow have a value?

Way i see it

Recursion calls till base case is reached and then you get 1

And after that I'm sort of lost

What happens after base case has been reached

[haughty mountain]

it gets multiplied by a bunch of things in the chain of returns

!e

def myPow(x: float, n: int) -> float:
        def yourPow(x,n):
            print(f'called with {x=}, {n=}')
            if x == 0:
                return 0 
            if n == 0:
                return 1
            print(f'recursing into {x**2=}, {n//2=}')
            res = yourPow(x * x, n // 2)
            print(f'result for {x**2=}, {n//2=} is {res}')
            if n%2:
              print(f'multiplied by {x=} because {n=} is odd')
            return res * x if n % 2 else res
        
        res = yourPow(x, abs(n))
        return res if n >= 0 else 1/res

myPow(2.0, 13)

[halcyon plank]

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

001 | called with x=2.0, n=13
002 | recursing into x**2=4.0, n//2=6
003 | called with x=4.0, n=6
004 | recursing into x**2=16.0, n//2=3
005 | called with x=16.0, n=3
006 | recursing into x**2=256.0, n//2=1
007 | called with x=256.0, n=1
008 | recursing into x**2=65536.0, n//2=0
009 | called with x=65536.0, n=0
010 | result for x**2=65536.0, n//2=0 is 1
011 | multiplied by x=256.0 because n=1 is odd
... (truncated - too many lines)

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

[haughty mountain]

welp, I guess look at the full output

[plain folio]

For kNN when inspecting the features of the dataset, I have done a histogram and boxplot to check for normality/skewness and outliers. Is there anything else I should be doing visually?

[haughty mountain]

#data-science-and-ml is probably the better place

[broken tiger]

any one knows genetic algorithm
or flow shop scheduling problem

[merry hamlet]

Does anybody know what is best algorithm to find chunk of progressive numbers in array of numbers...for example [1,3,4,5,7,9,11]Where I should extract only 3,4,5

[agile sundial]

don't you just loop and check

[urban kiln]

!e

print(120**3)

[halcyon plank]

@urban kiln :white_check_mark: Your 3.11 eval job has completed with return code 0.

1728000

[urban kiln]

is this doable

n=120 at max

wait ill implement it and ask again

[thin parrot]

any ideas what the solution to this question is looking for?

I was thinking decrease nodes by two until they either reach 0 or 1.

is this a bad question?

[urban kiln]

nvm i hate my life

everything is bugging

nothing makes sense

im tired

[urban kiln]

i just copied some solution

i was too lazy tzo do it

and i wanted those 10 leetcoins

had to do other stuff

code still not working

my code is saying that the distance from:
x=0 y=0 to x=1 y=1 is 1

the first part works

and im using math.dist()

i probably fucked some var name up

ill just delete the code and rewrite all of it after sleeping

    for bef in nodes:
        for cur in nodes:
            if bef != cur:
                if cur in bef.distances.keys() and bef.distances[cur] != []:
                    cur.distances[bef] = bef.distances[cur]
                else:
                    cur.distances[bef] = []
                    for after in nodes:
                        if cur != after:
                            if kosinussatz(math.dist((bef.x, bef.y), (cur.x, cur.y)),
                                           math.dist((cur.x, cur.y), (after.x, after.y)),
                                           math.dist((bef.x, bef.y), (after.x, after.y))) >= 90:
                                cur.distances[bef].append([math.dist((cur.x, cur.y), (after.x, after.y)), (after.x, after.y)])
                    cur.distances[bef] = sorted(cur.distances[bef], key=lambda p: p[0])
```this cant be the way to do it 💀

idk @cobalt mirage

wait

i can describe what it was supposed to be

class Node:
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.distances = {"no_bef": []}  # {node_before: [distance, node after]}

the self.distances hashmap was supposed to be storing the edges

which are different, depending on which node you come from

(my problem didnt allow angles smaller than 90°)

i thought that i needed this list

idk if i even need it

ill retry it tomorrow

but i thought that i need it, to check if there is even a route in the first place

(hamiltonian path problem)

idk if i should just go to sleep now or try again

i hope that there is an easier way to find out if a route is even possible to find

[sage flame]

is the reason why it's O(n^2) because the first Loop is O(n) and the second loop is O(n-i)

and then when you multiply you get O(n)*O(n-i)

so o(n^2 -ni)

so o(n^2)

[glossy breach]

its just n * (n - 1)/2 = O(n^2)

[vocal gorge]

saying the inner loop is O(n-i) isn't very correct because i changes with the outer loop.
There are two ways to consider this:

1. Exact. The inner loop does n-i-1 iterations each time as i goes from 0 to n-1. So the total number of iterations of the inner loop is the sum n-1 + n-2 + n-3 + .. + 0, which is equal to n*(n-1)/2, which is O(n^2).
2. Upper bound. n-i is at most n, so the inner loop is O(n) regardless of i, hence O(n^2) total.

The latter way is the one that's more useful in general - there are plenty of cases where calculating the exact number of iterations is very complicated, but getting an upper bound is easy and gives you the right answer.

[bronze lichen]

Anyone help me to solve this.

[polar shoal]

That is copy-paste :/
How we can help you if you dont know how to program it. Maybe its difficult to understand for you.

[urban kiln]

you just have to print "*" i times

per loop

!e

n = 16
for i in range(1, 8): print(n**i)

[halcyon plank]

@urban kiln :white_check_mark: Your 3.10 eval job has completed with return code 0.

001 | 16
002 | 256
003 | 4096
004 | 65536
005 | 1048576
006 | 16777216
007 | 268435456

[urban kiln]

n**6 is probaböy the max for n<=16

!e

n = 16
for i in range(1, 8): print(i**n)

[halcyon plank]

@urban kiln :white_check_mark: Your 3.11 eval job has completed with return code 0.

001 | 1
002 | 65536
003 | 43046721
004 | 4294967296
005 | 152587890625
006 | 2821109907456
007 | 33232930569601

[sage flame]

what do you mean by n-i is at most n

[haughty mountain]

n-i <= n

[haughty mountain]

assuming you know what's fine to ignore and still get a tight bound

[sage flame]

wouldn't it be like n-i <= n-1

because worst case it will start from 1 after the begginning

[haughty mountain]

both statements are true

[fiery cosmos]

How can I print the sequence 1,2,4,8,16 and so on

[urban kiln]

wait what was the difference betweeen paths and tours in graph theory

one was i think each vertex only once and the other each edge at most once right?

[sage flame]

so with n-1 I can just get rid of the -1 since its a constant making it n

[sage flame]

wouldn't it be like n-i <= n-1 so that is also correct

[haughty mountain]

if i >= 1 then n-i <= n-1 is a tight bound

bit n-i <= n is also true

and we don't really care about the -1 here

[sage flame]

because it's a constant right and we should always just remove those from big O

[haughty mountain]

lower order terms can be ignored yeah

as well as multiplicative constants

[sage flame]

you think there's any website that will help me get better at big oh notation like they give me code and I respond with the big oh

[haughty mountain]

it's a common question, but idk of good resources for practicing it

you can probably find some problem sheets if you search a bit

overall I recommend getting comfortable doing the more proper calculations first, where you just try to count the number of operations

[fluid sand]

        if not  root:
            return true
        def height(root):
            if not root:
                return False
            l=height(root.left)
           
            r=height(root.right)
            if  not l  or not r:
                return False
            
            if abs(l-r)>1:
                
                return False
            return max(l,r)+1
        a=height(root)
        if a==-1:
            return False
        return True

I'm trying to check if the binary tree is balanced or not ,But the above code is failing when has only left nodes or only right nodes

[haughty mountain]

when you've done that a bit you learn what parts you can be a bit sloppy with and still get the right result, like the n-i <= n thing in this case

(some people don't learn things properly and start going "two loops, n²" which is just not true in general)

[sage flame]

but in general it still does make sense to say the first loop is O(n) and the second loop is O(n-i) right?

[haughty mountain]

sure, though I probably wouldn't write O(n-i)

[sage flame]

Yeah I know because O(n-i) is just O(n)

that's what I was trying to say

[haughty mountain]

outer loop runs n times, inner loop runs n-i times, loop body does O(1) work, do the math and it's O(n²)

[haughty mountain]

there are cases where you can't just simplify too early

[sage flame]

ok thx

[haughty mountain]

e.g. what's the time complexity of this?

for i in range(1, n):
  for j in range(0, n, i):
    ... some O(1) work

[haughty mountain]

why is height returning True/False? seems like an odd thing to do

[sage flame]

I would still say O(n^2) because first loop is O(n) and inner loop in worst case will still go until n going up by 1 so that makes it O(n) and then multiplying will be O(n^2)

[fluid sand]

i need to return if tree is balanced or not

so i returned boolean value

[haughty mountain]

you're not, the last return in the function returns an int

[haughty mountain]

outer loop runs n times, inner loop runs n/i times, loop body does O(1) work

[sage flame]

but it still makes it n^2

[haughty mountain]

it doesn't

that /i matters

[fluid sand]

i updated it to -1

now all condition failed

[haughty mountain]

it's O(n log n)

n/1 + n/2 + n/3 + ... + n/n is O(log n)

an harmonic series

[haughty mountain]

hence why I said

[sage flame]

so for addition,subtraction,multiplication you can simplify earlier but for division you should wait?

[haughty mountain]

it's not that simple
if the inner loop was i*n the whole thing would be O(n³)

it's not just a constant

[sage flame]

ok thanks

[robust dagger]

I think it's good to bear in mind that any time you write O(-), you're making an approximation. You're saying you don't know, or you're not going to figure out, or you're not going to say, precisely how many operations happen. Part of the art of using big-O notation is knowing how to get a good approximation.

[haughty mountain]

why not rewrite the function to return both the min and max height of a leaf?

then the answer is just

min, max = minmax_height(tree)
is_balanced = max - min <= 1

[haughty mountain]

in particular what details you can drop without it mattering

[haughty mountain]

which is why my recommendation is

[robust dagger]

Yeah, I think that's good advice.

[haughty mountain]

it takes some practice to get a feel for what matters when

[fluid sand]

for every sub tree?

[haughty mountain]

and doing the working out ultimately means doing the math, getting a feel for sums and recurrences

[robust dagger]

And for what's going to be small and what's going to be large.

[haughty mountain]

no, for the whole tree, a tree is balanced if the height of leafs doesn't vary by more than 1, right?

[fluid sand]

yes

but also on every levels

[haughty mountain]

wdym?

only the height from the root should matter

[fluid sand]

A tree is height balanced if difference between heights of left and right subtrees is not more than one for all nodes of tree.

[haughty mountain]

one of my favorites is deriving the complexity for the sieve of eratosthenes, O(n log n) is easy to derive (boils down to my example earlier) but proving the tight bound of O(n log log n) is a bit more delicate 😄

[haughty mountain]

if it's true for the whole tree it's true for all the subtrees though, isn't it?

what is this even computing

[sage flame]

solution("Wed",5)

so it would return "Mon"

[fluid sand]

for the above tree for root it is balanced

but for node 3 it is not balanced

[haughty mountain]

no it's not?

[fluid sand]

height of left subtree is 4 and right subtree is 3

but of node 3 height left subtree is 0 and right subtree is 2

[haughty mountain]

that doesn't make it balanced

[fluid sand]

huh?

[haughty mountain]

one way of phrasing things is, if root has two subtrees x and y then

root is balanced if
x is balanced and
y is balanced and
abs(height(x) - height(y)) <= 1

in your example x and y aren't balanced

(or maybe I miss some extra constraint )

(or there are many definitions of a balanced tree)

actually, my definition on the tree level is a different one from the one I just gave, huh?

I think both are used though, and called the same thing

[fluid sand]

The one i reffered has mentioned that the height difference at every level must not be greater than 1

also finding min height and max height is very time consuming to solve this problem

I missed the condition to check when left subtree or right subtree is ubalanced

[plain folio]

thanks didnt see that channel, very much what i needed

[upper hearth]

Hi Guys I'm new to python when should I start learning data structures and algorithm

[main pulsar]

[urban kiln]

cos_gamma = (a**2 + b**2 - c**2) / (2 * a * b)
return cos_gamma <= 0
``` this should return True if the angle is 90°+ right? (all angles are <= 180

!e

from math import acos, degrees
print(degrees(acos(0)))
print(degrees(acos(0.0001)))
print(degrees(acos(-0.0001)))

[halcyon plank]

@urban kiln :white_check_mark: Your 3.11 eval job has completed with return code 0.

001 | 90.0
002 | 89.99427042203915
003 | 90.00572957796086

[opal oriole]

Consider the angle 300 degrees.

[cold slate]

Can anyone that understands coefficients for linear regression take a look of this when they get a chance?

#1061405019796152380 message

[urban kiln]

i care about the inner angle(idk if it is called that way)

300 would be 60

on the other side

[opal oriole]

cos_gamma <= 0 tells you that gamma is between 90 and 270.

[urban kiln]

yea i shouldve asked differently

[opal oriole]

Ah yes, inside a triangle, it would be true for 90 to 180.

[urban kiln]

👍

[cold slate]

Is my question fit for this channel? Coefficients/linear regression?

[opal oriole]

Ask in #data-science-and-ml

[cold slate]

Thanks 🙂

[bronze lichen]

Thank you I did it.

[bronze lichen]

s = int(input("Enter an number:"))
for i in range(s,s+1):
for j in range(s+1,0,-1):
print(j*"*")

[urban kiln]

id just do:
for i in range(1, s+1): print("*"*i)

[halcyon plank]

@urban kiln :white_check_mark: Your 3.11 eval job has completed with return code 0.

001 | *
002 | **
003 | ***
004 | ****

[bronze lichen]

It is for inverted right angle triangle.

[stray fractal]

!e center triangle ```py
s=4*2 # 2 separate so it can be customizable later
for i in range(1,s,2):print(f"{''*i:^{s}}")

[halcyon plank]

@stray fractal :white_check_mark: Your 3.11 eval job has completed with return code 0.

001 |    *    
002 |   ***   
003 |  *****  
004 | ******* 

[urban kiln]

oh my bad

didnt know that a center one was the goal

[stray fractal]

idk too

i'm just showing a center version

[urban kiln]

👍

[stray fractal]

!e but here's a right-sided triangle ```py
s=4
for i in range(1,s+1):print(f"{'*'*i:>{s}}")

[halcyon plank]

@stray fractal :white_check_mark: Your 3.11 eval job has completed with return code 0.

001 |    *
002 |   **
003 |  ***
004 | ****

[urban kiln]

is the only way to know if there is a path(all nodes visited once) in a graph(its directed i think), to try all combinations?

[urban kiln]

like bfs

[robust dagger]

@urban kiln https://en.wikipedia.org/wiki/Dijkstra's_algorithm

[urban kiln]

its not about shortest

[robust dagger]

I thought that was your question? You asked about the existence of paths.

[urban kiln]

nvm

you are right

[robust dagger]

You said "all nodes visited once". Do you mean https://en.wikipedia.org/wiki/Hamiltonian_path_problem?

[urban kiln]

@cobalt mirage have you done todays one

[urban kiln]

todays one was fun

why is this problem ranked hard

oh i couldve solved it using the GCD

[fiery cosmos]

where can i learn about the time complexity of built in functions like sum(), max(), the "in" keyword etc? nobody really teaches this; where do people learn about it?

[severe lance]

well you can kind of assume what the function definition looks like

def in(something, the_list):
  for value in the_list:
    if something == value:
      return True # found
  
  return False # not found```

[urban kiln]

i just assume some stuff

[severe lance]

for example this is what in might look like

which is O(n)

[urban kiln]

like somelist.index(idk) is probably O(n)

oh

its a list

[severe lance]

yeah

therefore it's O(n)

same for max and sum

how could sum possibly work without looking at each element individually

therefore it is O(n)

Yes

No because of two reasons

1. Operating systems support memory "reallocation" which allows you to extend an existing memory allocation without needing to move the existing values (usually, sometimes the values are moved anyway)

2. Python allocates in powers of 2

so when you have a list with 8 elements, and you do list.append(9)

python doesn't allocate only one more space

it actually allocates 16 spaces total

so the next 7 appends will not require any memory allocations

then when you append the 17th element, python will allocate for 32 elements

then you get 16 more free appends

then you get 32 free appends, etc.

the asymptotic behavior is that you get infinite free appends

thus O(1)

[robust dagger]

(This is not actually true, but it's close. See Objects/listobject.c for the details.)

[severe lance]

I'm just simplifying it so it makes more sense

I'm not trying to be technically accurate about implementation details

[wheat laurel]

That's interesting, I never knew this - but I can't think of a time where one might make use of it

[severe lance]

you make use of it every time that you call list.append

(or list.extend etc.)

[wheat laurel]

Ok yeah I get that, I mean when someone might need to consider something like this... I guess it feels low levelish so I immediately think of a different language to python being used

[severe lance]

yeah it's not super useful knowledge honestly

it's only useful when you try to figure out why list.append is O(1)

[wheat laurel]

All good, I don't do low level stuff so wasn't sure what I was missing 🙂

[stray fractal]

(only in hashtables)

[severe lance]

let me just add in a nutshell to this explanation so that people stop correcting me 😭

[stray fractal]

basically growth pattern is 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...

[wheat laurel]

🤔 ok... Why wouldn't it be O(1) if this didn't happen? And what would it be instead?

If every additional appended required addition of memory it'd be slower I guess?

[stray fractal]

so it's only "powers of 2" at the very start

somewhere in the middle the gap expands

and you definitely can not say it's just powers of 2

[severe lance]

it would be O(n) because it would need to reallocate on every append, which is O(n) in the worst case

since realloc might need to copy the entire list to a new memory page

but I'm out of my depth there as to why that might happen

[stray fractal]

amortized O(1), that is

because of dynamic resizing which we're talking about rn

[haughty mountain]

I think it's fair to basically assume that realloc copies as long as you grow the allocation

[severe lance]

yeah, in worst case realloc is definitely O(n)

I think on most modern hardware it is basically always O(1) but you have to assume the worst here

the key is that asymptotically, realloc is called increasing far between

so asymptotically it is "never called"

[haughty mountain]

huh, I recognize the listobject.c code

from investigating fun cases where smaller lists take more space

#python-discussion message

!e

print('list with len  0:', [].__sizeof__())
print('list with len  1:', [1].__sizeof__())
print('list with len  2:', [1, 2].__sizeof__())
print('list with len  3:', [1, 2, 3].__sizeof__())
print('list with len  4:', [1, 2, 3, 4].__sizeof__())
print('list with len  5:', [1, 2, 3, 4, 5].__sizeof__())
print('list with len  6:', [1, 2, 3, 4, 5, 6].__sizeof__())
print('list with len  7:', [1, 2, 3, 4, 5, 6, 7].__sizeof__())
print('list with len  8:', [1, 2, 3, 4, 5, 6, 7, 8].__sizeof__())

[halcyon plank]

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

001 | list with len  0: 40
002 | list with len  1: 48
003 | list with len  2: 56
004 | list with len  3: 72
005 | list with len  4: 72
006 | list with len  5: 88
007 | list with len  6: 88
008 | list with len  7: 104
009 | list with len  8: 104

[haughty mountain]

huh?

did things change?

[severe lance]

maybe your test code was broken

you didn't actually !e, you just pasted the output

[haughty mountain]

I wasn't even the one that initially mentioned it

[haughty mountain]

wth, the repro code I had doesn't work now

maybe it was something version specific

#python-discussion message

[bronze lichen]

Help me to solve this ?

[fluid sand]

while n:
    n= n+1 if not n%2 else n+2
    for  x in range(2,n):
        if n%x==0:
           break
    else:
         print(n)
         break```

This should work but i don't think its the efficient way to solve it

[urban kiln]

why would you test even numbers for prime

[fluid sand]

if we handle base case for >=1,i guess we can skip all the even numbers

[naive oak]

you could sieve the numbers between n and 2n and then grab the next prime

[bronze lichen]

Can you please describe this code, I can't understand your code,

[sudden rampart]

Can someone tell me the difference between binary search and binary search tree? Or is it the same thing

[nova hazel]

hello
I have a question about this code right here

iris2=iris[(iris['species']=='versicolor')|(iris['species']=='virginica')]

What is this saying?

[halcyon plank]

@bitter orchid Per Rule 6, your invite link has been removed. If you believe this was a mistake, please let staff know!

Our server rules can be found here: https://pythondiscord.com/pages/rules

[raw wharf]

hi i have a big issue

[mellow linden]

what are the best resources to learn DSA ?

[worldly jolt]

hi, I am going insane,
can someone tell me what is the maximum amount of necessary array accesses in a binary search?
I remembered ceiling of log2(n)
but it's wrong,
for example in an array of 0..9 (top exclusive) searching for the number 8
where the expected maximum should be 4 checks
0+9 / 2 = 4, 4 is too small
look for 8 in 5..9
5+9 / 2 = 7, 7 is too small
8..9,
8+9 / 2 = 8, check 8, and it's found.

but this was 3 checks...

[half lotus]

I think this is because you're using floored division to find the middle value, which creates a bias such that there are fewer values to search for on the right. I believe if you were to use the same logic but search for 0 instead of 8, it would take 4 comparisons.

If your data resulted in a completely filled tree like this, then what it shows in the image as the worst case would be correct https://en.wikipedia.org/wiki/Binary_search_algorithm#/media/File:Binary_search_complexity.svg

I suppose then we could say that in your example, searching for "8" is not the worst case, just like searching for "4" is not the worst case.

[worldly jolt]

oh, you are right

thanks 🙂

[half lotus]

You're welcome

[bronze lichen]

Dhanush please elaborate the code. I can't understand.

[fiery cosmos]

I got a leetcode problem

it is preorder tree traversal

I did recursive

but now i want to do it iteratively like with for loops

I think the basic idea is to add the root node to an array

loop over this area and add children to it

but each time the array has to be cleared of the parent nodes

am i on the right track?

just want a better way than making a new array each time

ah oh well

I will post my answer and look at the other answers

[worn laurel]

I have a function that returns the most frequent item in an array

def FreqItemCheck(arr: list) -> str:
    holder = {}
    for i in arr:
        if i in holder:
            holder[i] += 1
        else:
            holder[i] = 1

    # Initialize variables to store the most frequent items and their counts
    freq_items = []
    freq_counts = []

    # Iterate over the items in the holder dictionary
    for item in holder:
        # If the count for the current item is greater than the current maximum count,
        # update the maximum count and reset the list of most frequent items
        if holder[item] > max(freq_counts):
            freq_counts = [holder[item]]
            freq_items = [str(item)]
        # If the count for the current item is equal to the current maximum count,
        # add the item to the list of most frequent items
        elif holder[item] == max(freq_counts):
            freq_items.append(str(item))

    # Print the most frequent items and their counts
    for i in range(len(freq_items)):
        print(f"{freq_items[i]} : {freq_counts[i]}")

in this line.

    # Iterate over the items in the holder dictionary
    for item in holder:
        # If the count for the current item is greater than the current maximum count,
        # update the maximum count and reset the list of most frequent items
        if holder[item] > max(freq_counts):
            freq_counts = [holder[item]]
            freq_items = [str(item)]
        # If the count for the current item is equal to the current maximum count,
        # add the item to the list of most frequent items
        elif holder[item] == max(freq_counts):
            freq_items.append(str(item))

The time complexity should be O(n**2) right? Since for = O(n) and max = O(n)

[haughty mountain]

1. will this even run? seems it takes max of an empty list
2. freq_counts is at most 1 long, so taking max of it is O(1)

why is freq_counts even a list?

it should really be the max count seen so far, so you can start it at 0

!e

def FreqItemCheck(arr: list) -> str:
    # Could use Counter or defaultdict
    # from collections here
    counts = {}
    for i in arr:
        if i in counts:
            counts[i] += 1
        else:
            counts[i] = 1

    freq_items = []
    freq_max = 0
    for item, count in counts.items():
        if count > freq_max:
            freq_max = count
            freq_items = [item]
        elif count == freq_max:
            freq_items.append(item)

    for item in freq_items:
        print(f"{item}: {freq_max}")

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

[halcyon plank]

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

001 | 3: 2
002 | 1: 2
003 | 5: 2

[worn laurel]

Ohh I sent the outdated one, should have been ```py
freq_items = [0]
freq_counts = [0]

but what you wrote is definitely more efficient. Thanks!

[rough dune]

which library is better for handling CSV's ? python's csv library or pandas ?

[haughty mountain]

not the right channel for this, but if you want to use pandas dataframes use pandas. if you just want to read a csv the standard module is fine

[manic kite]

Hi, sorry if this is not the right channel, but can someone give some article or something where they explain how list comprehensions work

[naive oak]

!listcomp

[halcyon plank]

Do you ever find yourself writing something like this?

>>> squares = []
>>> for n in range(5):
...    squares.append(n ** 2)
[0, 1, 4, 9, 16]

Using list comprehensions can make this both shorter and more readable. As a list comprehension, the same code would look like this:

>>> [n ** 2 for n in range(5)]
[0, 1, 4, 9, 16]

List comprehensions also get an if clause:

>>> [n ** 2 for n in range(5) if n % 2 == 0]
[0, 4, 16]

For more info, see this pythonforbeginners.com post.

[manic kite]

I meant how theu work, like what's the difference between them and doing it with a for loop

[haughty mountain]

they are basically equivalent to the loop with the append, idk what kind of difference you're after

[manic kite]

I'm sort of more interested in memory usage. If you dont mind maybe you can check this stackoverflow question, it has only one answer and a few comments, and maybe point out any inaccuracies or shed light on something

https://stackoverflow.com/questions/75023405/explain-size-capacity-of-lists-in-python/75023474?noredirect=1#comment132457828_75023474

[haughty mountain]

!e why not look at some bytecode to see what it does?

import dis
dis.dis('[i**2 for i in range(100)]')

[halcyon plank]

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

001 |   0           0 RESUME                   0
002 | 
003 |   1           2 LOAD_CONST               0 (<code object <listcomp> at 0x7f0f1e168c60, file "<dis>", line 1>)
004 |               4 MAKE_FUNCTION            0
005 |               6 PUSH_NULL
006 |               8 LOAD_NAME                0 (range)
007 |              10 LOAD_CONST               1 (100)
008 |              12 PRECALL                  1
009 |              16 CALL                     1
010 |              26 GET_ITER
011 |              28 PRECALL                  0
... (truncated - too many lines)

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

[manic kite]

I don't really understand it but i'll try

[haughty mountain]

if you want to see what's exactly going on, learning to read the bytecode is quite helpful, along with reading the relevant python source code

(anything else is kinda guesswork)

[manic kite]

Yeah, btw do you know why it's hard to know the length of a list comprehension, if that's true?

[haughty mountain]

if you have a conditional knowing the length is basically impossible

and iterables might have lengths not known before they are evaluated

[manic kite]

So if the length of the list comprehension was known then python can allocate the needed memory at once instead of a series of append and resizing i guess

[haughty mountain]

it could, idk if it does

that's why you look at the bytecode

I don't actually see anything about that in the bytecode, so I'm a bit sceptical

[manic kite]

Yeah, it makes wonder why not if that's the case

Thanks!

[bronze lichen]

How to find next prime number in python?

This is the question.

[bronze lichen]

def nextPrime(n):
while True:
n += 1
for i in range(2,n):
if (n % 2 == 0):
break
else:
return n

Please help me to find the false.

[bronze lichen]

In this code when I print 7 it return 9. but it should return 11.

Please help me to correct it.

[lean walrus]

n % i

[vocal sluice]

p

y

t

h

o

n

[halcyon plank]

:incoming_envelope: :ok_hand: applied mute to @vocal sluice until <t:1673359947:f> (10 minutes) (reason: duplicates rule: sent 4 duplicated messages in 10s).

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

[vocal sluice]

T

R

E

E

[hazy leaf]

from datetime import datetime
from icalendar import Calendar, Event

def days_between_recurring_events(ics_file):
    with open(ics_file, 'rb') as f:
        cal = Calendar.from_ical(f.read())

    # Extract the events from the calendar
    events = [event for event in cal.walk() if event.name == 'VEVENT']

    # Initialize a list to store the days between events
    days_between = []

    for event in events:
        # Get the start and end date of the event
        start = event.get('dtstart').dt
        end = event.get('dtend').dt

        # Check if the event is recurring
        if event.get('RRULE'):
            # Get the recurrence rule of the event
            rrule = event.get('RRULE').to_ical().decode()

            # Extract the frequency and interval of the recurrence
            freq, interval = rrule.split(';')[:2]

            # Get the next recurrence of the event
            next_recurrence = start + interval 

            # Calculate the number of days between the current event and the next recurrence
            days_between.append((next_recurrence - start).days)

    return days_between```

Hi guys

Trying to calculate days between events from an ICS calendar

So I store the ICS file, update it once a week and get the changes in days if any

changes

[tame cobalt]

import itertools

def mandelbrot_set(width, height, zoom=1.0, x_offset=0, y_offset=0):
    x_min, x_max, y_min, y_max = -2.5, 1.5, -2, 2
    x_step = (x_max - x_min) / width * zoom
    y_step = (y_max - y_min) / height * zoom
    x_offset = x_min + x_offset * x_step
    y_offset = y_min + y_offset * y_step
    for y in range(height):
        for x in range(width):
            zx, zy = x * x_step + x_offset, y * y_step + y_offset
            c = zx + zy * 1j
            z = c
            for i in range(255):
                if abs(z) > 2.0:
                    break 
                z = z * z + c
            yield i

width, height = 100, 100
image = list(itertools.islice(mandelbrot_set(width, height), width * height))

[white river]

guys anyone here know any type of document to read to help me understand how create an system to distribute AD to my users based on user profile created by user actions? i know it's a bit complex topic, but i think some people here have this knowledge
like, what actions should i log, how to analyze this logs, the formulas to define a "user profile" and etc
PS: the ads are intern from my own platform, i do not get ads from google ads or any third party

[vital scaffold]

class Doubt:
    def __init__(self, entry):
        self._entry = entry


ss = Doubt(3)
print(ss)
ss = Doubt(3)
print(ss)

Output

<__main__.Doubt object at 0x7f5f0de95480>
<__main__.Doubt object at 0x7f5f0de949d0>

As you can see a new object is created when called again.
Can somebody explain what happen to the previous object ?

[outer rain]

Wrong chat + see this #1061372783256416266

(self ad hehehe😈 )

Also, can anyone help me with cycle index polynomials of wreath products (group theory thing)? I feel like that's too specific to ask in help channels

[tiny jay]

if the previous object has no other references, it will be deallocated by the garbage collector

[vital scaffold]

Thanks

[hasty bronze]

hey, can anyone help me with json ?

[bright geyser]

why does the solution with one line of code have almost double the time complexity then the other soln. Also how does use a bit more memory??

[agile sundial]

the time complexity is the same

lines of code has no relation to time complexity

[bright geyser]

oh wtf

okokok tyy @agile sundial @cobalt mirage

[bright geyser]

wht bout space complexity? Doesn't tht determine the memory used?

[agile sundial]

space complexity doesn't tell you anything about how much memory was actually used

[bright geyser]

oh? Oh alright, seems I had it confused with something else, thanks!

[bright geyser]

no no I wish I do, I just started lc!!

tytytyytyt

[agile sundial]

no

[calm eagle]

Hello people, I would like to learn data structures and algorithms in python from scratch to get ready for coding interviews can anyone help me or guide me to effectively learn dsa.

[haughty mountain]

time complexity is about how run time grows as the input grows

for a given input two solutions with the same time complexity can have very different run time, and two solutions with different time complexity could have very similar run time

so growth, not exact values

[gentle trellis]

Hello, I am having trouble understanding the difference between a Set ADT being implemented with a bitvector and a set ADT being implemented with an array

[halcyon ridge]

guys, some advice of learn programming python and develope the Logic!!

[fiery cosmos]

hello, idk if this is the right channel for this question. So i have a txt file it is like unformatted, i want to remove any line that contains an # in it. Is it possible to do is there like any function? I couldn't find anything on google

[patent spire]

Yup

with open("txt.txt", "w+") as f:
 lines = [line for line in f.readlines() if not "#" in line]
 f.writelines(lines)```

[fiery cosmos]

thanks i will try to use it and understand it

why do i feel like i am getting trolled i read it like 1000 times and i don't get it

[agile sundial]

it also doesn't work

[agile sundial]

w+ truncates the file

[agile sundial]

you need to use "r+" instead

[naive oak]

why r+?

[stray fractal]

read and write mode maybe?

[naive oak]

they'd want to reopen the file to truncate it after they've traffic it right?

[stray fractal]

oh it's read and append

[stray fractal]

they can just do ```py
f.seek(f.truncate(0))

or

f.truncate(0)
f.seek(0)

[naive oak]

does f.truncate() return something?

[stray fractal]

>>> help(io.StringIO.truncate)
Help on method_descriptor:

truncate(self, pos=None, /)
    Truncate size to pos.

    The pos argument defaults to the current file position, as
    returned by tell().  The current file position is unchanged.
    Returns the new absolute position.

[naive oak]

huh

[stray fractal]

maybe just returns 0 in that case

[naive oak]

I mean the file got wiped

not many positions it could be in

[stray fractal]

w mode does that i think

[fiery cosmos]

    reading = read.readlines()
    for reado in reading:
        if not "#" in reado:
            write = open("output.txt", "a")
            write.write(reado)```

i fixed my problem with this, this time it just creates a new file

[bright geyser]

Thaf nakes sense thx

[patent spire]

Forgot

[manic kite]

Does anyone know why namedtuple used to return OrderedDict instead of a normal dict? Like doesn't the fact that we transformed it into a dict means that we don't care about order anymore?

[haughty mountain]

idk, ask Raymond, he made that change

[manic kite]

Hettinger ?

[haughty mountain]

before that things were built using string replacements 🥴

[haughty mountain]

yes

[manic kite]

What is it?

[manic kite]

Haha. Where can i find him

[haughty mountain]

this is the relevant commit https://github.com/python/cpython/commit/a4f52b

[haughty mountain]

iirc he is on twitter a bit

[manic kite]

Ok. Thanks!

[haughty mountain]

not that kind of ordering

[dusk elbow]

Can someone help me with an algorithm ????????????????

length = [10, 20, 10, 8, 9, 30, 5, 15, 25, 10] i have a list it called "length" and i want that separate into different list. Require is current number must bigger than nubber behind just like “Continnue decending sequence" and i want it in to new liist. List = [ [10, 10], [20, 8], [9, 5], [30, 15], [25, 10] ]

[lean walrus]

Find first number X from array such that X <= arr[0]. Then add arr[0] and X to the result. Then remove arr[0] and X from arr. Repeat while arr is not empty.

(This might work, but I'm not sure)

@dusk elbow

[dusk elbow]

ohhh that sound like great idea thanks

[haughty mountain]

can't you just sort and then take pairs?

[dusk comet]

https://youtu.be/D_YC6DSPpQE?t=379

so in this video it shows the binary code to be 001110110111 in the code even though you dont need it

is their a reason its not just 111011111

[floral pumice]

It could be 1110110111
It can't be 111011111
Assuming you dropped a zero on accident, there isn't really any reason

Something to note is that typically integers are stored in a number that is a multiple of 8 bits (or bytes)

[dusk comet]

like with the

7 you only use the first 3

like 111

not 0111

right ?

[floral pumice]

yes

but

[floral pumice]

with this in mind

it might be represented as

00000111

because that has a bit count that is a multiple of 8

[dusk comet]

ohhh so you have to do that so the last goes 2^4

[floral pumice]

which is typically a byte or char datatype, depending on language

[dusk comet]

=8

[floral pumice]

Well it's because things are stored in bytes

so that's a 1 byte long number

which is 8 bits

[dusk comet]

right but how would 0111 be still 8 bits if 00000111 is also 8 bits

[floral pumice]

nonono

A byte is 8 bits

a bit is 1 or 0

0111 isn't 8 bits

it's 4

but because the minimum amount of memory you can allocate is a byte on a lot of systems, it ends up becoming 00000111 internally and so it might be represented as such

[dusk comet]

so going back to the original question you answered

It could be 1110110111
It can't be 111011111

the original problem was 3B7

[floral pumice]

You are correct, any leading zeros can be removed

[dusk comet]

so 3 would be 11

B would be 1011

[floral pumice]

you can remove leading zeros
it's similar to how 00000119 = 119 in decimal
so therefore 000111 = 111 in binary

[dusk comet]

and 7 would be 111

all together you get 111011111

[floral pumice]

yep

oh no

[dusk comet]

so how is my answer wrong

[floral pumice]

you're missing a zero

you probably forgot to carry a one

[dusk comet]

how

i just explained tho

[floral pumice]

ohhhh I see what you're missing

[dusk comet]

like 3 = 11
B= 1011
7 = 111

is it not ?

[floral pumice]

7 = 0111

3 = 0011

each hexadecimal number is 4 bits

[dusk comet]

whats the difference tho like the 0 dont mean anything anyways

[floral pumice]

Yeah they are important here

[dusk comet]

is that a requirement for hexadecimals

?

[floral pumice]

so hex is base 16, pow(2, 4) = 16

each number must be 4 bytes

Lemme give an example in decimal

let's say you have

10 and 7

because

it's base 10

you need to store it so that each digit can have 1 of 10 possibilities

(0123456789)

you could store 7

in 8 possibilities

and 10 in two possibilties

but it wouldn't be correct

because you would then have the wrong base

so 3 = 11 only works for a base 4 system

because 2 ^ 2 = 4

so you need those two zeros

to get 16 for a base 16 system

0011 = 4 bits = 2 ^ 4 = 16

11 = 2 bits = 2 ^ 2 = 4

[dusk comet]

my professor told me their was only the base 10,2,8, and 16

is their also a base 4 then ?

[floral pumice]

Technically you can have any base

[dusk comet]

like computers use 2

humans use 10

and hexa use 16

[floral pumice]

but typically only 10, 2, 8, and 16 are used

!e print(int("13", base=4))

[halcyon plank]

@floral pumice :white_check_mark: Your 3.11 eval job has completed with return code 0.

7

[floral pumice]

or something crazy

!e print(int("crazy", base=36))

[halcyon plank]

@floral pumice :white_check_mark: Your 3.11 eval job has completed with return code 0.

21429358

[dusk comet]

how could you store 7 in 8 possibilities

[floral pumice]

01234567

[dusk comet]

isnt 7 only 111

[floral pumice]

I'm not talking about binary

with that you already converted it 7 != 111 in base 8

!e print(int("7", base=8), int("111", base=8))

[halcyon plank]

@floral pumice :white_check_mark: Your 3.11 eval job has completed with return code 0.

7 73

[dusk comet]

wait so in base 8 111 is 73 ?

[floral pumice]

Yep

[dusk comet]

how

like equation wise

[floral pumice]

well

[dusk comet]

like i thought it goes 2^2+2^1+2^0

[floral pumice]

coincidentally 8 is actually just octal

[floral pumice]

that's binary

[dusk comet]

i am way to confused rn

[floral pumice]

ok back to your original conversion issues

you can't convert 7 to 111 in base 16 because you wouldn't have enough bits to be in the right base

2 ^ 3 = 8

[dusk comet]

ohhh

so you are Required since 2^4 = 16

so like if you were to convert 5

it cant be 101

it has to be 0101

?

[floral pumice]

yes

because then it would be base 8

[dusk comet]

gotcha that makes a lot more sense

and thats only if their is a hexadecimal right >

?

if it is only numbers like (1)(3)(4)

[floral pumice]

Yeah so the base is actually related to the number of bits

[dusk comet]

you can do 111100

[floral pumice]

for what base

[dusk comet]

i didnt think bout that

so the base matters then ?

[floral pumice]

Yeah the base is very important

and actually the octal example can be very helpful here

[dusk comet]

in a real world application how would that affect a pc

[floral pumice]

well internally every computer is base 2

so it's not super important to the computer

watch this

so for having n bits