#algos-and-data-structs

1 messages · Page 55 of 1

spiral sorrel
#

The next question I think is even worse

#

Doesn’t literally any 4 number work

#

I think what they’re asking for is the values to be removed the same way they were in the beginning

#

So I’d say (1,1,1,1)?!

#

Feels too easy

shadow glen
#

guys, i'm having a problem with my regex thing

    pattern = r"(?<=\[)([^\[\]]*?)(\s+)(?=[^\[\]]*?\])"
    macro = re.sub(pattern, r"\\0", macro)
    pattern = r"(?<=\{)([^\{\}]*?)(\\0)(?=[^\{\}]*?\})"
    macro = re.sub(pattern, r" ", macro)

At theory it should substitute all " " for "\\0"
But instead it's substituting "Olá " to "\\0"

args = '!echo [(Olá todos os { !roll 1d100 } Mundos),(Bem vindo a terra { !roll 1d10 })]'
<traceback object at 0x0000021214EC16C0>
!echo [\0todos os { !roll 1d100 } Mundos***)***,(Bem vindo a terra { !roll 1d10 })]
This character is not compatible with compiler or you mistyped something

Here it should be like this:
!echo [(Olá\\0todos\\0os\\0{\\0!roll\\01d100\\0}\\0Mundos),(Bem\\0vindo\\0a\\0terra\\0{\\0!roll\\01d10\\0})]
then this:
!echo [(Olá\\0todos\\0os\\0{ !roll 1d100 }\\0Mundos),(Bem\\0vindo\\0a\\0terra\\0{ !roll 1d10 })]

#

the responsi should be like this

deep rune
#

in c, sets are made using red black trees
so your insert complexity would be O(logn)

#

actually thats c++

haughty mountain
rigid trench
#

I've got a file thats about 1.5 megabytes and it's taking 1.5 seconds to search it for a 6 character string... I don't understand why. It's pretty small, shouldn't that be blazing fast?

#

my profiler says

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
      318    2.180    0.007    2.180    0.007 {method 'read' of '_ssl._SSLSocket' objects}
      646    0.000    0.000    2.143    0.003 {method 'readline' of '_io.BufferedReader' objects}
haughty mountain
haughty mountain
rigid trench
#

Yeah I'm just feeling confused because I dunno why it's being slow. I'm just gonna move on

#

I guess the server is responding slowly or something

rare crescent
#

what's the best way to learn DSA. I am a high school, student, and i like computer science, but recently i feel tired and confused while learning DSA

lilac cradle
#

Society if there was an ‘expression’ datatype in base py

#

Like storing a math function (without it just being a function, since allowing arbitrary function execution is unsecure lol)

jolly mortar
#

what language has that pithink

lilac cradle
#

idk

#

i would just like that

#

like for the idea of a calculator app, if i enter ‘x+2y’ as an expression it would interpret that as an expression (a strictly mathematical expression) and evaluate it

#

I dont know how well that’d work in py tho

jolly mortar
#

there's sympy which is more general than that

outer rain
lilac cradle
#

is that secure?

outer rain
#

it's somewhat secure

#

it can crash the interpeter or raise an exception

#

but it cannot run arbitrary code

jolly mortar
#

ast.literal_eval can only eval literals

#

!e import ast; print(ast.literal_eval("1 + 2*3"))

halcyon plankBOT
# jolly mortar !e import ast; print(ast.literal_eval("1 + 2*3"))

:x: Your 3.12 eval job has completed with return code 1.

001 | Traceback (most recent call last):
002 |   File "/home/main.py", line 1, in <module>
003 |     import ast; print(ast.literal_eval("1 + 2*3"))
004 |                       ^^^^^^^^^^^^^^^^^^^^^^^^^^^
005 |   File "/lang/python/default/lib/python3.12/ast.py", line 112, in literal_eval
006 |     return _convert(node_or_string)
007 |            ^^^^^^^^^^^^^^^^^^^^^^^^
008 |   File "/lang/python/default/lib/python3.12/ast.py", line 105, in _convert
009 |     right = _convert_num(node.right)
010 |             ^^^^^^^^^^^^^^^^^^^^^^^^
... (truncated - too many lines)

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

jolly mortar
#

it can't do arith expressions

outer rain
#

oh

#

I thought it was way more powerful..

#

I see

#

well...

#

in Lisp we trust then 🫡

stray fractal
# 
import ast

def literal_eval(x):
    return ast.literal_eval(ast.parse(x, mode="eval", optimize=1))

print(literal_eval("1 + 2*3")) # 7
haughty mountain
stray fractal
#

why it's not allowed in ast.literal_eval() i have no clue..

hoary kindle
#

Does anybody have a good resource for studying AVL BSTs? The course materials for my class doesnt make much sense to me and Ive watched a few Youtube videos but Im having a hard time understanding how to get the balance factor right at each node

haughty mountain
#

what's the worse crime? that or the act of being actively off-topic by posting that in this channel? :^)

hoary kindle
young totem
hoary kindle
young totem
#

yep

#

each node has one except the leaf nodes

young totem
#

which will give u a value indicating wether u need to perform rotations or not

hoary kindle
#

so the height of the root node for each subtree starts at 0 right?

young totem
#

so do u know at which particular threshold u need to preform the rotation to balance the tree?

young totem
#

in both these cases the trees are balanced avl trees

#

do u follow so far?

#

basically for each node u calculate maximum possible height of left subtree - maximum possible height of right subtree, which gives u ur balance factor

hoary kindle
#

So in the second example, you dont have to calculate the balance factor for the node with value 2 right? just the maximum height?

young totem
#

u have to, u will calculate balance factor for each node, thats how u determine which node is out of balance and u correct that

hoary kindle
shadow glen
lilac cradle
#

so im working with blocks as mentioned previously, but i have a problem
id like to be able to predictably rotate and position them but some blocks have a rotation origin in different places, do you guys know how i can account for this?

#

oh wait actually most of them are at the end but still
so i want to get a centered rotation and position from a non-centered one

lilac cradle
haughty mountain
lilac cradle
#

lemme try that

#

oh wait

#

you mean actually rotating the position?

#

im talking about more like

#

its an offset

#

i can rotate it just fine with a quaternion or euler angle, but the center of rotation isnt, well, centered

#

its kinda weird

haughty mountain
lilac cradle
#

ah

#

lemme try that

#

im just gonna do it with some vectors before i do actual blocks for convenience

#

hm maybe i should start using quaternions natively for some of this stuff
i have a conversion TO since the game im interfacing with is a unity game but apparently rotations in quat are faster?

gray sorrel
#

QUICK QUESTION:
In a priority queue (in python), when 2 elements are "equal", which one is choosen, the oldest (FIFO) or youngest (LIFO)?
thanks for the help

young totem
#

!d queue.PriorityQueue

halcyon plankBOT
#
queue.PriorityQueue 

class queue.PriorityQueue(maxsize=0)```
Constructor for a priority queue. *maxsize* is an integer that sets the upperbound limit on the number of items that can be placed in the queue. Insertion will block once this size has been reached, until queue items are consumed. If *maxsize* is less than or equal to zero, the queue size is infinite.

The lowest valued entries are retrieved first (the lowest valued entry is the one that would be returned by `min(entries)`). A typical pattern for entries is a tuple in the form: `(priority_number, data)`.

If the *data* elements are not comparable, the data can be wrapped in a class that ignores the data item and only compares the priority number:
shadow glen
calm token
#

People, quick question

# 
List1 = [1,2,3,4,5]

if (1 or 2 or 3 or 4) in List1:
  print("Hi)
#

Is it possible to change the (1 or 2 or 3 or 4) to range(1,4) ?

narrow mica
#

and also your code probably doesn't do what you think it does as is

#

!or

halcyon plankBOT
#
The or-gotcha

When checking if something is equal to one thing or another, you might think that this is possible:

# Incorrect...
if favorite_fruit == 'grapefruit' or 'lemon':
    print("That's a weird favorite fruit to have.")

While this makes sense in English, it may not behave the way you would expect. In Python, you should have complete instructions on both sides of the logical operator.

So, if you want to check if something is equal to one thing or another, there are two common ways:

# Like this...
if favorite_fruit == 'grapefruit' or favorite_fruit == 'lemon':
    print("That's a weird favorite fruit to have.")

# ...or like this.
if favorite_fruit in ('grapefruit', 'lemon'):
    print("That's a weird favorite fruit to have.")
narrow mica
calm token
#

Hmm

#

In this case, favorite fruit is a list, correct?

narrow mica
calm token
#

Ooooo

#

It's because I want to check if a number is in the list heheCutie

#

Ohhhhh

#

I see

#

I have to use the set() function to use the range

#

I mean, if I want to use a range

#

Interesting Purplys! Thanks for the help! hypeE

narrow mica
#

s <= U means "everything in s is in U" (if both are sets)

calm token
#

Ooooo

#

So I can say that s = range(1,4) and then use the <= to compare if it is true or false

narrow mica
#

you can also do something like

>>> List1 = [1,2,3,4,5]
>>> [v in List1 for v in range(5)]
[False, True, True, True, True]
>>> all( [v in List1 for v in range(1, 5)] )
True
>>>
narrow mica
calm token
#

Oh yeah, I can do a for loop for that too!

#

Got it got it got it!

#

Thanks for helping Purplys and make it clear PeepoCoffee

#

Have a good timezone! o7

haughty mountain
lilac cradle
#

is this better for getting the angle between two vectors than atan2? cause atan2 can only work in 2d right?

image.png
outer rain
#

it's bad computationally and has worse precision

lilac cradle
#

ah

outer rain
#

also ugly division

#

in 2d you can do atan2(x % y, x * y) where x % y = x.x * y.y - x.y * y.x

#

well, abs(atan2(...))

lilac cradle
worn mountain
lucid rose
#

I wrote this code of inserting a node in binary heap and was testing it out by comparing it to my instructor's code . the 1st output is mine , 2nd output is of my instructor . I have a feeling that my instructor's code is somewhere is wrong since his code didnt changed the rootnode according to a MAXIMUM binary heap and mine did. I just want it to be confirmed by some senior dev that whos code is actually correct
Image

haughty mountain
formal lily
#

how do u remove the states in a GNFA i'm so confused

solemn moss
solemn moss
# haughty mountain what loses you precision with the arcccos? <:pithink:652247559909277706>

as the easiest example if you will get acos(1.000000000000001) due to precision problems you will get "math domain error"
you can do min(1, x) but still

also (since we are in algos-and-data-structs) you usually need to know a directed angle, not it's absolute value

and i would guess that using two sqrts (for lengths) can give bigger error, but that's hard to say exactly

#
  • if you have all calculating in integers for atan2 you can calculate everything as integers and only atan2 will give float
    and for acos you will need already making calculations with floats before passing them to acos
fluid siren
#

how do we get 0.0 in the code because im not getting the decimal point

image.png
outer rain
#

but, I, mean, there is no reason for acos to be better in any way

#

it accepts argument from -1 to 1, what if floating point errors result in a larger value?

#

and it does more work too

#

to measure the angle between 2 vertices you need at least 6 multiplications, 1 sqrt, 1 division, 3 additions vs 4 multiplications and 2 additions

#

and the function itself considers twice as much data

#

the whole precision loss occurs because acos acts bad around 0, and atan2 doesn't: it has y as a fallback

fiery cosmos
# 
volatile const int* coolest_func(int const* const (*func)(int const* const (*[])(volatile const int*), int const* const(*[])(volatile const int*)));

if you dont know what this does then thats a skill issue

stray fractal
outer rain
stray fractal
#

for anyone wondering it's a function coolest_func that returns a volatile const int * and accepts an argument func which is a function that returns a volatile const int * and accepts 2 arrays/pointers to functions that return const int * and accept a volatile const int * as an arguments

#

oh

#

also it errors in C++

solemn moss
#

that's C

#

(i guess, at least it compiles there)

narrow mica
#

not enough pointer to functions that return pointer to arrays of function pointers

fiery cosmos
#

nope

#

they are constant pointers to constant ints

#

its another way of writing int const* const

haughty mountain
#

const binds to the left, unless there is nothing to the left

stray fractal
#

maybe you mean a const int *const

#

that's a constant pointer to a constant int

haughty mountain
stray fractal
#

i've never seen it written that way

fiery cosmos
haughty mountain
stray fractal
#

haha.

haughty mountain
#

const const int* is just const int*

fiery cosmos
#

my bad

#

i realised i typed it wrong

haughty mountain
#

skill issue, to quote your former self

fiery cosmos
#

it is tbh

#

when im 70 and decide to make a language

#

constant will apply to the leftmost thing

#

so const int* = pointer to constant integer

#

const const int* = constant pointer to constant integer

#

const const const int*[] = constant pointer to constant array of constant integers which is just const const int** im pretty sure

#

this is a real interview question btw

#

i saw a variation of it at jane street and palantir

haughty mountain
#

const mutable const int*[] 🥴

agile sundial
#

make it 2d tbh. put it above

fiery cosmos
#

const int* const[]

#

sike

#

const* int const[]

#

acc

#

const* int[const]

#

constant pointer to array of constant integers

lilac cradle
#

is there a way to detect if a variable has changed other than having a 'old' copy of that variable?

i.e like

if var != old_var:
  do_something()
  old_var = var
shadow glen
#

guys, how do i insert keys in fstring outside of insertion?

#

like f"{{i}}"?

lean walrus
lilac cradle
#

by 'i' do you mean like an iterator

outer rain
#

but please don't

lilac cradle
#

honestly a shame there isnt some default thing for that but i guess tracking states of all vars would be a bit much

outer rain
#

in my rust CP template I have a bunch of methods which are used like var.if_ne_patch_and(&mut old_var, |_| do_something()) but python can't do that

lilac cradle
#

one language i learned before py, Expression 2 (a language meant for ingame programming in gmod) was generally kind of shit but it did have changed() which was nice

lilac cradle
#

also rust uses snakecase (or something like it) ?

outer rain
#

yeah

#

exactly same as in python, actually

#

snake_case for variables and functions, CamelCase for types, and SCREAMING_CASE_OR_WHATEVER for constants

lilac cradle
#

its kinda funny, i went from using camelcase for everything when i first started learning py (bad) to using snake case for EVERYTHING in py (kind of an overcorrection from that initial state i guess) and now i have started naming things properly

#

i still think having my vectors lowercased is easier to do though

outer rain
#

I sometimes name type which feel primitive in lowercase

#

i.e. mat33

lilac cradle
#

this is kinda stinky probably, but sometimes when i use Decimal, i'll import it as something like 'dec' because writing Decimal each time is kinda annoying

outer rain
#

oh I like it actually

#

Fraction is too long too

lilac cradle
#

yeah i'd probably import that as 'frac' or smth

#

also interestingly it seems f-strings 'compile' immediately after declaration

# 
a = 1
s = f"{a}"
print(list(s)) #['1']
outer rain
#

yeah they aren't lazy

#

this means stuff like logger.log(f"something {some_var}") is inefficient

#

(because it interpolates even if the log level is high enough that this message will not be logged)

lilac cradle
#

oh huh py has default logging

#

ive literally never used this i think

#

neat!

outer rain
#

yeah

lilac cradle
#

ye i looked it up when i saw that

#

what's the 'log level' then, actually?

outer rain
#

it's like a thing you can configure

lilac cradle
#

ah

#

kk

#

oh neat this works per module

outer rain
#

like imagine having a server

#

you probably don't want this server to log every debug message of every library is uses

lilac cradle
#

right

outer rain
#

so you can configure what messages you want to see

#

for instance, only warnings

#

or only errors

#

and for debuging you enable everything

#

and you only need to change that one config parameter, no need to remove logging lines everywhere

#

convenient

lilac cradle
#

nice

fiery cosmos
#

whats more important while doing leetcode?
solving the question? or beating the number of users who already did?

narrow mica
mint jewel
#

if you're talking about the performance metrics on leetcode, they're completely irrelevant

keen hearth
#

They're only really relevant when the run-times have a multi-modal distribution, where different approaches fall into different clusters. It can be informative to click on the histogram to see examples of solutions with different run-times. Otherwise, within each cluster, the variation in runtime is essentially random (i.e. caused by factors that aren't of interest to you).

#

The memory usage histogram seems to be completely uninformative.

haughty mountain
#

but alas

wild reef
#

I need help regarding programming for tg tapping projects..can anybody provide suggestion how can i do it

stiff quartz
#

When using a O(n^2) memory solution you can see the O(n) solutions to the left and vice versa

#

But only when the constraints aren’t a joke and the test cases not particularly weak

ancient escarp
coarse flare
#

Does anyone know about quadtrees? In this screenshot, I've given each quad a one point capacity and added them in the order shown. Also drawn a line from each point to the center of the quad it belongs to

image.png
#

My main question now is what is supposed to happen when a point moves throughout the grid?

#

Rebuilding the tree every frame defeats the purpose, at least in my current implementation

lean walrus
#

when i was using quadtree for collision checking, i was rebuilding it every frame

#

you might try to implement removal of point from a tree
and then movement is just a removal if point from old position and addition to new position

coarse flare
#

Maybe each point checks if it's left the bounds of its rect and if so, removes itself from it then reinserts into the tree...lemme see what happens...

vocal gorge
#

if you're using a quadtree to e.g. simplify computing n-body gravity to O(n log n), then it's worth it even if you recompute it every frame
naively I think this is also true for collision checking

coarse flare
#

When you say rebuilding is worth it, does that mean re-instancing a new tree and inserting all the points (in their updated positions) into it? Or having a method that does something to empty the existing tree then re-add all the points?

vocal gorge
#

I meant the former, but I don't see how these two are particularly different - either way it's less-than-quadratic.

lilac cradle
#

do you guys ever get lazy and instead of calling math.pi (well not really calling but accessing) you just assign it to some variable and use that

#

ive taken to just using a variable called 'mp' (i.e Math.Pi) and its probably not good but whatever

vocal gorge
#

I don't think this is bad at all, but also I'd use pi or π as the variable name.

lilac cradle
#

fair

#

does doing 'math.pi' have any significant overhead over calling a local var btw

lean walrus
#

no significant overhead

#

some overhead - sure

vocal gorge
#

it does have a tiny bit, that's why you see the standard library sometimes store attributes in a local variable before using them in a hot loop

lean walrus
warm marten
#

hey guys I just studied the Euclidienne algorithm , I just want to solve a probleme that i had in my code to translate the algorithm into a code

euclide.PNG
haughty mountain
#

other than not doing this in a loop or whatever

slender sandal
#

And is an opportunity to use divmod

stray fractal
#

is there a difference between collections.OrderedDict and simply dict?

#

other than their implementation

gilded fulcrum
narrow mica
agile sundial
#

their comparison is order aware

fervent saddle
#

If you're unlucky with reallocation then accessing the front of a normal dict can be O(n) because it needs to go past all the deleted spaces.

fervent saddle
#

What would be a good way to fix that?

from timeit import timeit


setup = """
d1 = dict.fromkeys(range(10000001))
d2 = d1.copy()
d3 = d1.copy()
d4 = d1.copy()
d5 = d1.copy()
d6 = d1.copy()
d7 = d1.copy()
d8 = d1.copy()


def dict_delete(d, n):
    for k in range(n):
        del d[k]


def f(d):
    for _ in d: break


dict_delete(d1, 10**0)
dict_delete(d2, 10**1)
dict_delete(d3, 10**2)
dict_delete(d4, 10**3)
dict_delete(d5, 10**4)
dict_delete(d6, 10**5)
dict_delete(d7, 10**6)
dict_delete(d8, 10**7)
"""


for n in range(1, 9):
    print(timeit(setup=setup, stmt=f"f(d{n})", number=1000))

print("done")
#

Avoiding the linear increase while still maintaining amortized O(1) time.

#

The current way to avoid it is to just know not to use normal dict for this.

#

Rehashing at the start of iteration if there's been some constant number of deletes since the last rehash could cause O(n^2) runtime complexity.

#

Like if you had a dict with a large number of keys, and the rehash limit was 1000 deletes. If you deleted 1001 keys, iterated, deleted 1001 more keys, iterated, and so on until the dict was empty, that would be O(n^2).

regal spoke
fervent saddle
versed root
versed root
fervent saddle
# versed root https://paste.pythondiscord.com/XUZGHZL3XLWZCF5IF4FJ6KCLDA

It doesn't understand the question. It's also wrong, all it did was copy the keys to a list instead of iterating over a range object during the setup step. Also, dicts don't rehash from deletion anyways.
People overhype chatgpt, it's really bad at coding unless it's coding some extremely common program.

versed root
fervent saddle
#

There might not be any good way to do it.

wide marlin
#

a question about lru cache:

so we were talking yesteday about how I would have key duplications in my list, and yesterday oldlygeek said to have the nodes in the hasmap along with the value.

thing is, for every cache hit i am going to update the list so that key is at the tail. say if a particular key is hit multiple times in the row, this means i will be pushing that same to the tail for every cache hit right? (or am i wrong?)

we talked about moving keys to the end. The problem is I have still yet to make the connection between having the nodes in the hashmap and moving the keys around in the list efficiently after racking my brain last night.

agile sundial
#

no. you find the particular key in the list and move that existing key. the hashmap is used for quickly finding the existing key in the list

wide marlin
#

but searching in a linked list is just O(n) no

agile sundial
#

the hashmap is used for quickly finding the existing key in the list

#

your hashmap would be set up with your cache keys as the keys and a reference to a linked list node as the value (could also be a tuple of the cache value and the reference but whatever). that linked list node would contain the cached data

wide marlin
agile sundial
#

not exactly, because you're moving to the end, but yeah

wide marlin
#

oh yeah im moving to the end
so say i have a linked list like this
(node1, node2, node3, node4)

say, node2 is a cache hit, so through the hashmap:

node2 = hashmap.get(key2)[1]
node4 = linked_list.last_node

# get the neighbors of node2
node2_previous_node = node2.previous_node
node2_next_node = node2.next_node

# move node2 to the end
node2.previous_node = node4
node2.next_node = none

~~# nudge node4 back in the list
node4.next_node = node2~~ 

# connect node1 and node3 together:
node2_previous_node.next_node = node2_next_node
node2_next_node.previous_node = node2_previous_node

# node2 is now the most recently used
linked_list.push_to_back(node2)

in hindsight i don't think i need to nudge node4 myself, pushing to the back of the list already does that

lean dome
#

every time you insert or remove a node, you need to adjust 4 pointers (the previous node's next, the next node's previous, and the removed or inserted node's next and previous)

#

but yeah, that algorithm looks basically right

wide marlin
#

i don't think i need these two operations here

# move node2 to the end
node2.previous_node = node4
node2.next_node = none

~~# nudge node4 back in the list
node4.next_node = node2~~

the last operation (pushing node2 to the end of the list) already does these two

lean dome
# 
# Remove node2 from where it was
node2_prev_node = node2.prev_node
node2_next_node = node2.next_node
node2_prev_node.next_node = node2_next_node
node2_next_node.prev_node = node2_prev_node

# Put node2 at the end
old_tail = the_list.tail
old_tail.next_node = node2
node2.prev_node = old_tail
node2.next_node = None
the_list.tail = node2
lean dome
#

the "put node2 at the end" operation in mine is just a linked list append

wide marlin
#

alright, i'll move on with this and will probably need another night of reading.
it just occured to me that, since linked list nodes are not stored like an array which are beside each other in some contiguous memory space, i cannot really think of a linked list as a list but rather as separate pieces of data, connected by nodes

i was having a hard time understanding using hashmaps to store the nodes, because in this case then the linked list seems to be 'separate' from the nodes, but really what a linked list class give me are simply methods to mutate the values of the next and previous nodes

lean dome
#

yep

#

it's ok for the linked list to be "separate" from its nodes, because your cache always knows the list, so if someone hands you a node, you can splice it out of its current position in the list (just by its next/prev links, and their prev/next links), and put it into the new position in the list (by calling self.the_list.append(the_node) or whatever, to add it at the end, updating the old end and the list's tail attribute)

wide marlin
#

alright, thanks a lot @agile sundial @lean dome 🫡 now to put it into practice

haughty mountain
wide marlin
covert thorn
wide marlin
#

🤣

haughty mountain
#

exposed

raw zealot
#

all the unordered map and set of cpp are hacked i suppose

#

i used a python set

#

apparently the generator test works well in <200ms (i didnt try hacking my own solution lol) with it but welp i am not sure it will pass system test

# 
for _ in range(int(input())):
    n = int(input())
    arr = list(map(int, input().split()))
    prefix = [0] * n
    prefix[0] = arr[0]
    for i in range(1, n):
        prefix[i] = prefix[i - 1] + arr[i]

    hset = set()
    ans = 0
    for i in range(n):
        hset.add(arr[i])
        if (prefix[i]/2).is_integer() and prefix[i]//2 in hset:
            ans += 1

    print(ans)
#

does python set handle hash collision better than cpp unordered set/map

#

thats the ultimate question lol, i should have custom xor hashed it i thought it would be overkill 😩

haughty mountain
raw zealot
#

I couldn't find a set hack but welp

solemn moss
raw zealot
#

oh lmao

image.png
#

so it boils down to if there is a testcase which checks x,x+1 .. x+9

#

anyways i will always use the wrapper now, i underestimated a div4c because was so focused in solving quick

haughty mountain
#

this kind of hack is...unfortunate

agile sundial
#

they do be punching down 😔

raw zealot
#

🥺

#

welp

#

this is the second time

#

i cant green because of this shite

#

i will rewrite complete collections library and set now

#

enough brainmon

#

(switching to cpp is not an option )

solemn moss
#

well, task C could be solved without any sets

# 
for _ in range(int(input())):
    n = int(input())
    A = list(map(int, input().split()))
    s = mx = ans = 0
    for i in range(n):
        mx = max(mx, A[i])
        s += A[i]
        ans += s - mx == mx
    print(ans)
#

Not sure how good it is in reality

raw zealot
#

Yeah xor hashing

raw zealot
#

Idk why sets struck my mind first

narrow mica
raw zealot
#

Yep that's what I do , xor with random number its in separate file and i didn't think i need

#

Didn't think a d4c will also be problematic without it

#

Another reason to create a template

#

😢

haughty mountain
#

TLE doesn't suggest a hack, does it?

raw zealot
#

No it was in system test

haughty mountain
#

unless the authors added such test data

raw zealot
#

Wait

#

I think it was added due to hacks

#

But no one hacked me

#

People were busy in hacking F binary search lol

haughty mountain
#

oh right, those are added to the test cases

raw zealot
#

Yeah unfortunately

haughty mountain
#

test 10 seems too early though

raw zealot
#

I have become too informative for someone who is a newbie 🤡

#

1180s

haughty mountain
raw zealot
#

yeah ikr

#

Maybe it was the author

#

Why do they have so less pretests man

haughty mountain
#

(prefix[i]/2).is_integer() eww

raw zealot
#

lol

#

You can also mod 2

#

💀

haughty mountain
#

I wouldn't call that "also", you should do the mod 2

raw zealot
#

yeah

#

I should give a minute to code quality

#

Not like it will destroy rank

#

🗿

solemn moss
#

Nowadays there are so much grays and greens who know some hard datastructures xd

haughty mountain
#

just knowing some stray datastructures doesn't help that much

glacial elm
#

hey guys,
im fairly new to python and this breaks my current understanding and I cant find anything on google.

I use jsondiff and it produces this dict. When trying to json dump this it says "keys must be str, int, float, bool or None, not Symbol" So, apparently $insert and $delete are symbols.

Can someone clarify what that means? How can I access them? What are they good for?

Bildschirmfoto_2024-06-12_um_15.44.50.png
misty oak
#

anyone have any pointers on how to organize data from apis ?

#

struggling to organize it in a certian way

vocal gorge
glacial elm
# vocal gorge Seems like the dev of that package chose to use a custom type for the "insert" a...

thx. meanwhile i solved it, as always just after one asks...

it's a symbol declared by
delete = Symbol('delete') within the library.
And one needs to use
differences[jsondiff.delete] to access it.

I agree with you, It's presumably to prevent name collision. While this is the super safe way, a prefixed key would have been okay too, making it much easier to comprehend and instantly serializable.

glacial elm
misty oak
#

Im using the amadeus api

glacial elm
misty oak
#

iposted my question in python-help

slim galleon
#

// Given an integer array "arr" with length n

    print(num)
}```
This algorithm has a space complexity of 

O(1). The only space allocated is an integer variable num, which is constant relative to 
𝑛

```/ Given an integer array "arr" with length n

Array doubledNums = int[]

for (int num: arr) {
    doubledNums.add(num * 2)
}```
This algorithm has a space complexity of 
𝑂(𝑛)
O(n). The array doubledNums stores 
𝑛
n integers at the end of the algorithm.

// Given an integer array "arr" with length n

Array nums = int[]
int oneHundredth = n / 100

for (int i = 0; i < oneHundredth; i++) {
nums.add(arr[i])
}```
This algorithm has a space complexity of
𝑂(𝑛)
O(n). The array nums stores the first 1% of numbers in arr. This gives a space complexity of
𝑂
(𝑛/
100)
O( 100n) =
𝑂(𝑛)
O(n).

can anyone explain where to look to check order n / order 1 space complexity

sharp steeple
#

#1250528709929336832 Any help will be appriciated. I have added my approach but finding it hard to code. Open to new apporaches. Thanks

lilac cradle
#

is there a way to store something like a matrix so that you can get its rows and columns equally efficiently?

#

i guess like, i could do it in a dict with tuple entries but that means i'd need to iterate to get both

opal oriole
vocal gorge
haughty mountain
tame fractal
#

not sure where this falls,

I'm having a class which has a file attribute. Is it bad to close the file in __del__ method?

#

why doesn't my editor have autocomplete for __del__?

#

vs code

regal spoke
regal spoke
#

Making anti hash tests for CPython is trickier that for PyPy, since in CPython dicts and sets are different, but in PyPy they work the same way

raw zealot
#

oh i see

#

neverthless i am planning to use this as permanent

import random

# Custom HashMap and Set for Anti-hash-table test
class CustomHashMap:
    def __init__(self, *args, **kwargs):
        self.RANDOM = random.randrange(2**62)
        self.dict = dict(*args, **kwargs)
    def wrapper(self,num):
        return num ^ self.RANDOM
    def __setitem__(self, key, value):
        self.dict[self.wrapper(key)] = value
    def __getitem__(self, key):
        return self.dict[self.wrapper(key)]
    def __contains__(self, key):
        return self.wrapper(key) in self.dict
    def __iter__(self):
        return iter(self.wrapper(i) for i in self.dict)
    def items(self):
        return [(self.wrapper(i),j) for i,j in self.dict.items()]
    def __repr__(self):
        return repr({self.wrapper(i):j for i,j in self.dict.items()})

class CustomSet:
    def __init__(self, *args, **kwargs):
        self.RANDOM = random.randrange(2**62)
        self.set = set(*args, **kwargs)
    def wrapper(self,num):
        return num ^ self.RANDOM
    def add(self, key):
        self.set.add(self.wrapper(key))
    def remove(self, key):
        self.set.remove(self.wrapper(key))
    def __contains__(self, key):
        return self.wrapper(key) in self.set
    def __iter__(self):
        return iter(self.wrapper(i) for i in self.set)
    def __len__(self):
        return len(self.set)
    def __repr__(self):
        return repr({self.wrapper(i) for i in self.set})
#

not using collections/standard dict/set anymore apart from deque, other stuff

#

it should not affect runtime right

regal spoke
#

I've asked the developers of PyPy of wha is a "good" solution for this

raw zealot
#

1 more test with python3 😂

regal spoke
#

The response I got was to key the set/dict with strings instead of integers

raw zealot
#

yeah right because the hash of integer is itself so prolly easy to hack

regal spoke
#

So run str(x) before adding it to the set

regal spoke
raw zealot
#

so many ways damn

#

i will test the fastest

#
  1. string key 2) xor hashing
#
  1. treemap probably (std::map implementation)
#

but that is logn so ig will be slower

regal spoke
#

Dont call it xor hashing, thats something different

raw zealot
#

oh

regal spoke
#

also, I'm not so sure that random xor will make things safe

raw zealot
#

it did work against the hacks in the recent div3

regal spoke
#

Yes, but I'm not sure it is impossible to design other tests for it

#

I would not recommend it

raw zealot
#

is str'ing a 1e9 integer not time taking

raw zealot
regal spoke
regal spoke
raw zealot
#

oh welp

regal spoke
#

So any bit higher than like 20th bit will be ignored

raw zealot
#

ah i see

#

so string is the way for now

#

not sure how it would affect time for large nums

hybrid goblet
#

@fiery cosmos vanakkam Kallu

regal spoke
#

I've ranted about Pythons hashtables here before

#

!e

from timeit import timeit

def f():
    A = [i * (2**61 - 1) for i in range(5000)]
    set(A)

def g():
    A = [i * (2**61 + 1) for i in range(5000)]
    set(A)

print('f took', timeit("f()", number=1, globals=globals()))
print('g took', timeit("g()", number=1, globals=globals()))
halcyon plankBOT
regal spoke
#

Just look at this

#

Python hashes ints by taking mod 2^61 - 1

#

So in f(), all the numbers have the same hash=0.

#

The hash of an int is about as stupid as making the hash of a string only depend on the first 8 characters

#

It is bad, and very "hackable"

raw zealot
#

💀

#

this is too bad holy shit

#

and this number is smaller than 1e9 right

#

!e

print(2**61)
halcyon plankBOT
regal spoke
raw zealot
#

smh

#

alright

regal spoke
#

2**60 is about 1e18

raw zealot
regal spoke
#

String hashes have been fixed in Python

#

They are random

raw zealot
#

ah

#

got it

#

random is fine

regal spoke
#

What I said is that the int hash in Python is really badly implemented. The analogue to string hashing would be to have a hash only dependent on the first 8 characters

raw zealot
#

but generally since integers are given upto 1e9 and they mod with 2^61 - 1,

regal spoke
raw zealot
#

oh yeah

regal spoke
#

I'm sure there are tons of Python scripts vulnerable to this "ddos" attack

#

Python really should hash big integers in the same way as they do strings, but for whatever reason they dont

raw zealot
#

exactly

#

how does c++ handle this

#

but anyways they have map

regal spoke
#

C++ standard library handles this really badly too

raw zealot
#

true

#

thereforce the hacks

#

they just have good stl

regal spoke
#

There were like 500 sucessful hacks for that problem C, and most of them were C++ submission hacks

raw zealot
#

but i dont want to switch to cpp rn

#

does python template worth 300 lines really affect runtime

raw zealot
#

my solution was spared until sys test lol

regal spoke
raw zealot
#

perhaps but it did kill my rank 4k->8k ;-;

regal spoke
#

Funnily enough, the script the hacker used to hack them was made by me holyfuck

raw zealot
#

lmao this

image.png
regal spoke
raw zealot
#

i tried few generator code it worked locally

#

missed this i guess

regal spoke
#

My script doesn't work for CPython sets, but it works for CPython dicts

#

It also works for PyPy dicts and PyPy sets

raw zealot
#

damn

regal spoke
#

A funny thing, something I realized reading the source code of PyPy and CPython, is that PyPy actually has a small bug here

#

Which makes the hack for PyPy slightly different

#

I think the difference between CPython and PyPy is completely unintended

raw zealot
#

woah

#

all this just to hack an innocent soul

#

for the good

regal spoke
#

My hope is that by spreading the knowledge of hacking, maybe one day Python will fix this

raw zealot
#

welp as long as it is less than 1 second / 2 i dont really care

raw zealot
#

python should do something for this

#

it is already very infamous for cp for no reason but half knowledge

regal spoke
#

The only template I care about is

import sys
input = lambda:sys.stdin.readline().rstrip()
#

Using this makes all the difference

raw zealot
#

lmaooo

#

this is what i use

#

fastio

regal spoke
#

What exactly are you using?

raw zealot
#

i would need seg trees

#

also multiset

#

most important

#

since python doesnt have that

#

i just wanted a template which has these handy things so you don't have to copy paste from other files

#

neverthless div2 A,B,C,D should not need it idk

regal spoke
#

Things like segment trees, I usually code by hand

raw zealot
#

i figured

#

you submissions are clean and smol

#

no template gang

regal spoke
#

ye

raw zealot
#

but you use c++ in parallel i think for later problems

#

will see

#

i should also use both actually

regal spoke
raw zealot
#

oh so entirely cpp or entirely pypy

regal spoke
#

I've kinda challenged my self to not switch to C++

#

Even though I could probably do it

raw zealot
#

wow

#

thats cool

#

apparently there are claims that there exists problems on cf which can never be solved in python

jolly lance
regal spoke
#

But maybe there is some really hard problem out there that I havent attempted

raw zealot
#

oh

regal spoke
#

That being said, it can take a lot of work to code fast enough Python solutions to some problems

raw zealot
#

yeah

#

you reach a point where the code looks so unpythonic

regal spoke
# jolly lance Explain more about it ?

Most of the standard data structures and algorithms are implmented in this library (many done by me). The implementations have been designed to run fast in Python.

jolly lance
regal spoke
#

I see my own code

raw zealot
#

lmao

#

then it should be fine

#

this of some python CM

haughty mountain
#

CM?

regal spoke
#

candidate master

haughty mountain
#

I know that

#

but who?

regal spoke
raw zealot
#

redheadphone from errichto server

haughty mountain
#

ah

regal spoke
#

I feel like people should link to where they copied their implementation from

#

But I guess thats not how CP works

haughty mountain
#

I usually did that

#

e.g. link to a kactl impl or whatnot

agile sundial
raw zealot
#

copyright

lime cairn
#

yo where can i ask for help about a scripting module where automaticly fills in something?

#

in a browser

haughty mountain
#

not here, which should be clear if you read the channel title

#

if only there was some channel for general python discussion

tulip sky
#

hey

tulip sky
#

I attend my university in india and have been struggling with Python. I enrolled in this course because of the AI hype, but now I'm finding it difficult. While I'm comfortable with the basics, delving into advanced Python feels like diving into the deep end without knowing how to swim. I'm genuinely scared and would appreciate a helping hand. It's like I'm in the middle of a stormy sea, desperately trying to stay afloat amidst the waves of complex coding concepts.

lilac cradle
#

what basics do you know?

fiery cosmos
#

Problem Statement

Given an array of lowercase letters sorted in ascending order, find the smallest letter in the given array greater than a given ‘key’.

Assume the given array is a circular list, which means that the last letter is assumed to be connected with the first letter. This also means that the smallest letter in the given array is greater than the last letter of the array and is also the first letter of the array.

Write a function to return the next letter of the given ‘key’.

Example 1:

Input: ['a', 'c', 'f', 'h'], key = 'f'
Output: 'h'
Explanation: The smallest letter greater than 'f' is 'h' in the given array.

Example 2:

Input: ['a', 'c', 'f', 'h'], key = 'b'
Output: 'c'
Explanation: The smallest letter greater than 'b' is 'c'.

Example 3:

Input: ['a', 'c', 'f', 'h'], key = 'm'
Output: 'a'
Explanation: As the array is assumed to be circular, the smallest letter greater than 'm' is 'a'.

Example 4:

Input: ['a', 'c', 'f', 'h'], key = 'h'
Output: 'a'
Explanation: As the array is assumed to be circular, the smallest letter greater than 'h' is 'a'.

Here greater means just right to particular letter, right?

lilac cradle
solemn moss
lilac cradle
#

the 'smallest'/'greatest' bits are quite a weird way of saying it

fiery cosmos
fervent saddle
#

Isn't it just binary search, but you return the lowest/highest index if you can't find the value?

solemn moss
lilac cradle
#

hm, how would you check if a nested list has consistent length?
i.e

[1,1,1] -> True
[[1,1],[1,1],[1,1]] -> True
[1,[1,1],[1,1]] -> False
#

other than just iterating through and checking the length of each compared to the first

regal spoke
lilac cradle
#

just one

#

trying to do matrices

#

im a bit tired rn but for clarity this is what i have rn

class Matrix:
    def __init__(self,rows,check_size=True):
        row_count = len(rows)
        r_len = check_length(rows[0])
        if check_size:
            for row in rows:
                l = check_length(row)
                if l != r_len:
                    raise ValueError(f"all Matrix rows must be the same length")
        row_size = r_len
        self.size = (row_count,row_size)
        self.rows = rows
keen hearth
#

If you know it's a list of list, you could do: py if len(set(map(len, list_of_lists))) == 1: ... (technically <= 1 if you want to account for the case where there aren't any elements in the outer list)

lilac cradle
#

no because i want to be able to input vectors

#

or lists

#

regardless with some weird conditional logic i got it to work, i rotated a point around and plotted points wherever it 'landed' so to speak and it drew out a circle

image.png
bitter vault
#

I'm in need of a data structure that supports FIFO access (head, popfront, append, etc.) but also support O(1) membership tests. OrderedDict almost works, but has no head operation.

fervent saddle
#

You can iterate and break immediately.

head = None
for head in reversed(ordereddict): break

tail = None
for tail in ordereddict: break
#

Or use iter and next if you prefer how that looks

bitter vault
#

That works. Kinda wish they exposed all of the typical sequence operations, but I guess things like .pop() and indexing would collide... oh well.

#

But now, I need a bi-directional multimap. One side is a unique set of As and the other a unique set of Bs. There can be multiple Bs associated with each A. I need to be able to lookup all Bs associated with an A, and lookup the A associated with a B.

narrow mica
#

as for head, you can also do something like this instead of a for loop and breaking immediately:

>>> od = OrderedDict([('a', 5), ('b', 10)])
>>> od
OrderedDict([('a', 5), ('b', 10)])
>>> next(iter(od))
'a'
>>> next(iter(od.items()))
('a', 5)
>>>
#

not exactly pretty either but yknow

pale gull
#

I implemented this min_sum_subarray using sliding window technique
is this code correct and will it handle all test cases including corner cases

import time
def min_sum_subArray(arr, k):
    min_sum = sum(arr)
    window_sum = 0
    left = 0
    for right in range(len(arr)):
        window_sum += arr[right]
        print("window_sum", window_sum)
        if right >= k - 1:
            min_sum = min(min_sum, window_sum)
            print("Min Sum: ", min_sum)
            window_sum -= arr[left]
            left += 1
        print("---")
        time.sleep(1)
    return min_sum
result = min_sum_subArray([28, 3738, 289, 38, 11, 11, 11, 48, 48, 81], 3)
print(result)
fiery cosmos
naive ridge
#

wow

obsidian echo
#

hello

#

how can i satrt

#

leaning django

#

?

fluid siren
#

does anyone know what is the error in this

image.png
upbeat sequoia
fluid siren
#

ohh...i thought return works the same as a print statement

upbeat sequoia
fluid siren
#

okayy thank you

#

even this is showing an error...is it better that in the body if the function i just write print ("true") ?

image.png
narrow mica
#

same with False

fluid siren
#

ohhh...okayy thank youu

#

i tried it and it worked

#

yay

halcyon plankBOT
#
Print and return

Here's a handy animation demonstrating how print and return differ in behavior.

See also: /tag return

chilly latch
#

where do i start learning algos?

keen hearth
sacred rivet
#

hello, i need to visualise an n-ary tree (think of it as a family tree of sorts?). is there any module that helps with it? i tried NetworkX and it sorta does the job, but i need a tree-like visualisation instead of the graph-like visualisation that NetworkX provides

narrow rivet
#

it provides great drawing functions

#

networkx.drawing.layout function is specifically designed for drawing trees and may provide it more situable

#

fpr

#

for*

#

visualization for your n-ary tree

narrow rivet
sacred rivet
dull prism
halcyon plankBOT
#

addon.py line 182

self._push((right - 1) >> i)```
steel pivot
#

can you calculate levenshtein distance using breadth first search?

shut breach
#

breadth first search of what?

steel pivot
#

imagine each node in the graph is one state of the word and each edge represents an action/transition that you perform on the word (e.g. substitute one letter for another)

#

and therefore you can find the shortest path from one word to the next and hence compute the levenshtein distance

shut breach
#

seems like it'd work

steel pivot
#

how much slower is this compared to a dynamic programming approach?

keen hearth
# steel pivot how much slower is this compared to a dynamic programming approach?

Probably quite a lot slower. Because the frontier of the search will grow really quickly as you expand outwards from the initial node, as there's quite a large branching factor. Starting with the word saturday, it's an eight letter word, so there are 8 possible deletions, 208 possible substitutions (8 * 26), and 234 possible insertions (9 * 26), assuming a 26 letter alphabet.

#

I tested it, and that word would expand out to a frontier of 11406081 nodes after just three steps.

#

If you want to try it yourself: ```py
def one_edit_neighbours(string, alphabet='abcdefghijklmnopqrstuvwxyz'):
# Insertions
for i in range(len(string) + 1):
for letter in alphabet:
yield string[:i] + letter + string[i:]

# Deletions
for i, c in enumerate(string):
    yield string[:i] + string[i+1:]

# Substitutions
for i, c in enumerate(string):
    for letter in alphabet:
        yield string[:i] + letter + string[i+1:]

frontier = {'saturday'}
for i in range(3):
frontier = {
new_word
for word in frontier
for new_word in one_edit_neighbours(word)
}
print(len(frontier))

subtle sonnet
# 
sortable = [5, 4, 2, 3, 1, 4, 2, 9]
new_list = []

for i in range(len(sortable)):
    lowest = 0
    for j in range(len(sortable)):
        if sortable[j] < sortable[lowest]:
            lowest = j
    item = sortable.pop(lowest)
    new_list.append(item)

print(new_list)
#

made a sorting algorithm with no prior knowledge to what an algorithm is or how to make one, how bad is it 😔

fervent saddle
#

It looks like selection sort

inland agate
#

not sure which sub chat to post this to but

#

how do you reference a global variable within a function?

#

because i think the way i've written my program

#

makes it think that when i reference the global variable in the function

#

that i actually want to define another (local) variable of the same the name

lament totem
#

@inland agate

#

But generally, global variables should just be avoided

#

!global

halcyon plankBOT
#
Globals

When adding functions or classes to a program, it can be tempting to reference inaccessible variables by declaring them as global. Doing this can result in code that is harder to read, debug and test. Instead of using globals, pass variables or objects as parameters and receive return values.

Instead of writing

def update_score():
    global score, roll
    score = score + roll
update_score()

do this instead

def update_score(score, roll):
    return score + roll
score = update_score(score, roll)

For in-depth explanations on why global variables are bad news in a variety of situations, see this Stack Overflow answer.

inland agate
lament totem
#

You mean you have a local variable with the same variable name as the global one, and you want to keep those separate?

inland agate
#

i want the function to reference the one outside of the function and treat it as the same

lament totem
#

I'm not sure I get what you mean.

#

!e

x = 5

def increment_x():
  global x
  x += 1

print(x)
increment_x()
print(x)
halcyon plankBOT
lament totem
#

This is an example using global

#

After putting global x, x will be the global variable x in the function

#

So it will change the variable "outside of the function" as well.

inland agate
#

should i try and type out what i'm trying to do

lament totem
#

Yes

inland agate
#

!e

halcyon plankBOT
#
Missing required argument

code

inland agate
#

inputVar = input('type smth')

lament totem
#

!code

halcyon plankBOT
#
Formatting code on Discord

Here's how to format Python code on Discord:

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

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

For long code samples, you can use our pastebin.

inland agate
#

will try that

#

inputVar = input('type smth')

def someFunc():
# do something to inputVar's inputed data

#

the reason i need the function is so i can easily run it as many times as i need

#

and so the code is more modular

lament totem
#

Modifying the value of a global variable

#

But like I said, there is almost no good reason to use global variables inside functions

lament totem
#

If you are still unsure, it's probably best to open a help channel and ping me there, as it's not really an algorithm/data structure question 😉

inland agate
#

how do i do that

lament totem
inland agate
#

gtg i'll get back to you

lilac cradle
#

how would one implement a sort of 'biome map' using perlin noise? i have a perlin noise based map but its all the same, i'd like to color it and potentially add features based on a biome type (like in minecraft)

also, is there a way to check the 'smoothness' of a heightmap? i'm primarily using primitives for this (ideally as many cubes as is reasonable, since the other ones are more performance heavy) and i'd like sort of assign the type of object based off of that so i can have actually 'walkable' terrain

image.png image.png image.png
vocal gorge
#

i'd like to color it and potentially add features based on a biome type (like in minecraft)
Minecraft generates several (3, IIRC) independent noise fields, and the combination of them determines the biome.

lilac cradle
#

gotcha

#

i was actually thinking about something like that but for stats like 'humidity', 'mountainousness', etc
however that sounds more reasonable

#

lemme try implementing this with just one 'biome field' and then work my way from there

vocal gorge
#

for stats like 'humidity', 'mountainousness', etc
That's pretty much right - in minecraft it's "Temperature, Humidity (aka. Vegetation), Continentalness (aka. Continents), Erosion, Weirdness (aka. Ridges) and Depth". (though Depth isn't a noise field).

#

and it's complicated because some of these are used only to determine the biome, but some affect terrain generation.

vocal gorge
# lilac cradle lemme try implementing this with just one 'biome field' and then work my way fro...

So it seems to me that naively, you could get a decent worldgen with just... three, maybe, noisefields:

  • continentalness, to determine where's ocean and where's land (that's important because ocean terrain is kind of massively different from land and mountains)
  • temperature
  • humidity
    with the last two determining the biome without directly affecting terrain. E.g. "if inland, low humidity and high temperature, that's a desert".
lilac cradle
#

gotcha

#

i dont intend this to be super realistic i just want terrain gen
also i probably need to figure out a way to use less 'tiles' because the map in that second screenshot literally crashes the game when i unpause (it's like 40,000 pyramids lol)

vocal gorge
#

also, is there a way to check the 'smoothness' of a heightmap?
I don't fully get this, but you could calculate the gradient of it, perhaps, and use sharp slopes if the magnitude of the gradient is high enough

lean walrus
#

smoothness is proportional to radius of curvature, which can be calculated using first and second derivative

lilac cradle
#

ok so i should just like, check each point compared to its neighbors so to speak? like an edge detection algorithm

#

also, it's not evenly distributed but i figured out how to (roughly) fill a triangle with points
you can just start with one point, then lerp between the other two points
the obvious problem is that one corner is more filled than the others

image.png
#

and because of that it also leaves gaps

image.png
fallow agate
#

For https://datalemur.com/questions/sql-bloomberg-stock-min-max-1
pls let me know, where the below solution is getting deviating from the problem.

SELECT ticker,
TO_CHAR(date, 'Mon-YYYY') highest_mth,
MAX(open) highest_open,
MIN(low) lowest_mth,
MIN(open) lowest_open
FROM stock_prices
GROUP BY ticker, TO_CHAR(date, 'Mon-YYYY')
lilac cradle
#

i think my perlin noise is off lol

#

the mean and median are correct it seems but the mode (using a value 0-255) is 251?

lean walrus
#

is that a problem?

lilac cradle
#

im not sure

#

oh wait

#

it should be evenly distributed, maybe it's just that one is slightly more?

lean walrus
#

mode of sin(x) is either +1 or -1, so i think it is kinda expected

lilac cradle
#

lemme get the counts of them

#

all the values it can spit out that is

#

looks seemingly random

#

the most common values im getting from this sample are 251, 55, 250, 243, and 101

#

this is from the noise generation (that im using for the perlin noise) btw

#

not the perlin noise

#

but yeah the issue overall is that i dont get extreme values for my noise maps
i seem to mainly be getting values in the range 0.25 to 0.8 (i remapped it from [-1,1] to [0,1])

weak terrace
#

Hello! how can i run python in a super computer? i have a function f(n) that has a large time complexity and i can only perform values up to 30 in a reasonable amount of time in my computer. how can i get more values? would colab's gpu work for this?

haughty mountain
#

try finding a better algo for computing it pithink

#

if your time complexity is terrible a faster computer will only give you so much extra

lean walrus
#

can only perform values up to 30 in a reasonable amount of time
sounds like you are computing fibonacci numbers recursively 💀

narrow mica
weak terrace
#

Im pretty sure my current complexity is really bad. It uses partitions of integers which is bad plus more nested stuff. I think I might need to fix the math a bit more

steel pivot
# 
@cache
def f(remaining_sum, coins, curr=0):
    if curr == len(coins):
        if remaining_sum == 0:
            return 1
        else:
            return 0
    count = 0
    for i in range(0, (remaining_sum // coins[curr]) + 1):
        new_sum = remaining_sum - coins[curr] * i
        count += f(new_sum, coins, curr + 1)
    return count

Would this approach work for Coin Combinations 2 CSES?
How can I implement it using tabulation instead of memoization?

tight cedar
#

I don't think the cache will work here

fluid siren
#

does anyone know why my first result is not proper

image.png image.png
tight cedar
#

you hardcoded the return values

#

you are supposed to calculate them

#

1 takes 0 full block and 1 partial block

fluid siren
#

im sorry i didnt quite understand

tight cedar
#

it should take 4096 * (full_blocks + 1) if there is any remainder

#

otherwise just 4096 * full_blocks

lean walrus
fluid siren
#

okayy

stiff quartz
#

Looking for advice for micro-optimisation of radix sort if a pro Python person has a few minutes to spare 🙂 https://stackoverflow.com/questions/78638998/optimization-of-radix-sort-implementation-slower-than-expected-compared-to-stan

Stack Overflow
Optimization of Radix Sort Implementation: Slower than Expected Com...

I've implemented two versions of radix sort (the version that allows sorting integers whose values go up to n² where n is the size of the list to sort) in Python for benchmarking against the standard

lilac cradle
#

i dont know if i can help with actual optimization but im curious, why are you typehinting only for integers? (also ngl i didn't actually know you could typehint without the typing module since i havent really used typing much before)

stiff quartz
#

So no particular reason as to why only the integers were type hinted

steel pivot
tight cedar
#

How do you verify it? Did you pass the judge on cses? On hindsight I don't see any repeated function calls with duplicate parameters

steel pivot
#

I verified it by testing my code with a very high sum. With the cache it ran significantly faster than without.

frozen canopy
#

hey everyone ! anyone interested in doing DSA together?

fiery cosmos
#

Anyone participated in today codechef contest ?

agile sundial
#

<@&831776746206265384>

desert cedar
#

!cban 854751853463601152 pornography

halcyon plankBOT
#

:incoming_envelope: :ok_hand: applied ban to @weak thunder permanently.

lean dome
#

!cban 854751853463601152 pornography

halcyon plankBOT
#

:x: User is already permanently banned (#97974).

obtuse wyvern
#

Will linear algebra help me to dp and dsa?

keen hearth
# obtuse wyvern Will linear algebra help me to dp and dsa?

It's not directly relevant to most basic algorithms, although useful for some more advanced algorithms. It's very useful for algorithms in the fields of graphics and machine learning. However linear algebra is usually your first introduction to university level mathematics, so its where you learn the kind of mathematical reasoning you need for other mathematical courses like algorithms (e.g. constructing and understanding proofs and rigorous arguments).

fervent saddle
#

They never made me do anything past calculus 3.

keen hearth
#

At the university I went to, the linalg course doubled as the like "introduction to mathmatical thinking" course.

fervent saddle
#

Where you write proofs?

keen hearth
#

Yeah

fervent saddle
#

They only made us write proofs in discrete math.

keen hearth
#

I want to go back and re-learn linear algebra at some point.

opal oriole
# fervent saddle They only made us write proofs in discrete math.

Euclidean geometry has been removed from many schools and so many student's first proof is far later in university. They need to introduce it somewhere for CS students, since it's technically a branch of mathematics, even though it's treated like a hybrid vocational school for coding / some of the math (but without counting towards a math degree, even though it should, since it's the mathematical theory of computation).

opal oriole
fiery cosmos
#

What is a data table?

regal spoke
# stiff quartz Looking for advice for micro-optimisation of radix sort if a pro Python person h...

The standard way to implement a fast (stable) sort for small (non-negative) integers is to start by counting, then do prefix sum, then finally create the sorted list

# Sort list A of non-negative integers in O(len(A) + max(A)) time
# Note: Sort is stable
def sorter(A):
  count = [0] * (max(A) + 2)
  for a in A:
    count[a + 1] += 1
  
  # Prefix sum count
  for i in range(len(count) - 1):
    count[i + 1] += count[i]
  
  # Use count to place each element of A in sorted order
  sortedA = [0] * len(A)
  for a in A:
    sortedA[count[a]] = a
    count[a] += 1
  return sortedA
#

This way you only need a couple of lists of integers, and can completely avoid using nested list of lists

#

This is what you should use as the underlying subroutine for radix sort

#

I've found that this kind of sorting algorithm can easily beat the built in sort in Python in the case where you want to sort tuples.

#

Sorting tuples is notoriously slow in Python

stiff quartz
#

I see
Why do you use prefix sum?

#

Couldn't you do:

for i in range(len(count)):
    sortedA += [i] * count[i]
#

(with sortedA initialized as an empty list)

#

is it to avoid using the dynamic operations which are costly on our array?

regal spoke
stiff quartz
#

Oh I didn't think about that

regal spoke
#

It is important

stiff quartz
#

Ah I see

#

That's a really smart way to be stable

#

I'm impressed

regal spoke
#

This sorting algorithm with counting + prefix sum is very standard. You'll find it in tons of implementations if you look around.

stiff quartz
#

in its state it doesn't work with tuples though right?

regal spoke
#

Ye you need to modify two lines

stiff quartz
#

when you mean sorting tuples do you mean sorting on the first key of the tuple

#

or sorting on both keys

#

(or both)

regal spoke
#

To sort k-tuples using a stable sort as a subroutine, start by stable sorting based on the kth (last) value

#

Then stable sort based on the (k-1) value

#

...

#

Finally stable sort based on the first value

stiff quartz
#

ok yes it's the same as sorting big numbers

#

and using base n to make tuples

#

and then using count sort, right?

regal spoke
stiff quartz
#

amazing

#

thank you!!!

lean walrus
regal spoke
regal spoke
lean walrus
#

i dont see why you would use prefix sums here
just go over the counts and append that many values to the output

regal spoke
#

I want a stable sort

#

Thats important if you want to use this for sorting more general objects, like tuples

lean walrus
#

all numbers are identical, so any number sorting algo is stable

lean walrus
lean walrus
regal spoke
# 
# Sort list A with respect to key:A->[m] in O(len(A) + m) time
# Note: Sort is stable
def sorter(A, key):
  count = [0] * (max(map(key, A)) + 2)
  for b in map(key, A):
    count[b + 1] += 1
  
  # Prefix sum count
  for i in range(len(count) - 1):
    count[i + 1] += count[i]
  
  # Use count to place each element of A in sorted order
  sortedA = [0] * len(A)
  for a in A:
    b = key(a)
    sortedA[count[b]] = a
    count[b] += 1
  return sortedA
#

If A contains 3-tuples, then you can sort it like this

A = sorted(A, lambda a:a[2])
A = sorted(A, lambda a:a[1])
A = sorted(A, lambda a:a[0])
lean walrus
#

i see, that's an interesting algo

#

you have a bug: you should do max(A, key=key)
but i get the point

regal spoke
#

fixed

#

This implementation could probably be speed up by storing the call to key, intead of calling it multiple times.

lean walrus
#

https://ru.wikipedia.org/wiki/Сортировка_подсчётом?wprov=sfla1

Сортировка подсчётом

Сортировка подсчётом (англ. counting sort; сортировка посредством подсчёта англ. sorting by counting) — алгоритм сортировки, в котором используется диапазон чисел сортируемого массива (списка) для подсчёта совпадающих элементов. Применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют (или их можно отобразить в) ди...

#

i was originally thinking of this, this is what i was teached

stable variation is mentioned later, i learned that it exists only today

#

kinda weird that english wiki doesnt mention "simple" variation at all

regal spoke
#

This algorithm pops up from time to time. For example, when I was learning SA-IS algorithm for creating suffix arrays in linear time (a rather complicated and fast string algorithm), it appears as a subroutine in the code https://zork.net/~st/jottings/sais.html

#

This sorting algorithm is a nice fundamental algorithm to know about

fiery cosmos
#

I am new at DSA, I am learning about how to solve DSA problems from one course and I stumbled upon Bitwise XOR section.

For me using XOR to solve problems is really not intuitive. Does that become intuitive after some time? Maybe I have narrow picture about problems where XOR is used, but for example I stumbled upon this problem

In a non-empty array of integers, every number appears twice except for one, find that single number.

Example 1:

Input: 1, 4, 2, 1, 3, 2, 3
Output: 4
Example 2:

Input: 7, 9, 7
Output: 9

This is solution

class Solution:
    def findSingleNumber(self, arr):
        num = 0  # Initialize a variable to store the result
        for i in arr:
            num ^= i  # XOR operation to find the single number
        return num

def main():
    sol = Solution()
    arr = [1, 4, 2, 1, 3, 2, 3]
    print(sol.findSingleNumber(arr))

main()

This is result of num variables through program

First element: i = 1
num = 0 ^ 1 = 1
Second element: i = 4
num = 1 ^ 4 = 5 (binary: 0001 ^ 0100 = 0101)
Third element: i = 2
num = 5 ^ 2 = 7 (binary: 0101 ^ 0010 = 0111)
Fourth element: i = 1
num = 7 ^ 1 = 6 (binary: 0111 ^ 0001 = 0110)
Fifth element: i = 3
num = 6 ^ 3 = 5 (binary: 0110 ^ 0011 = 0101)
Sixth element: i = 2
num = 5 ^ 2 = 7 (binary: 0101 ^ 0010 = 0111)
Seventh element: i = 3
num = 7 ^ 3 = 4 (binary: 0111 ^ 0011 = 0100)

So it is somehow intuitive why non duplicate number would be result of that program...are other problems where I need to use XOR generally more intuitive, so I stumbled upon problem that is not intuitive?

vocal gorge
#

XOR operations are commutative and XORing with the same number twice is an identity operation, so all of the numbers that appear twice in the sequence cancel out, leaving only the target.

#

I don't think tricks like that are common, but I think I've seen some in competitive programming.

fiery cosmos
# vocal gorge XOR operations are commutative and XORing with the same number twice is an ident...

I do not know if this make sense, but this solution is not somehow intuitive for me because in this example numbers are not sorted, so XOR-ing number that is for example at second iteration of the loop with third element of array result in different number and that could happen at each iteration (like it is shown in my example), so it is somehow not intuitive how in the end correct result is obtained.

jolly mortar
#

there's some xor tricks summarized in https://florian.github.io/xor-trick

That XOR Trick

There are a whole bunch of popular interview questions that can be solved in one of two ways: Either using common data structures and algorithms in a sensible manner, or by using some properties of...

jolly mortar
haughty mountain
#

if the question is tweaked even a slight bit the solution can't be adapted

regal spoke
#

I think xor is super nice of an operator.

a xor b = b xor a
a xor 0 = a
a xor a = 0

a xor b = c <=> a xor c = b
a,b < 2^n => a xor b < 2^n
fiery cosmos
regal spoke
#

Start by writing down the bit representation of the numbers in a matrix

#

Each column corresponds to a numbers

#

The numbers are 1,4,2,1,3,2,3,

image.png
#

You can find the xor of all numbers by taking the sum of each row and checking if it is odd or even

#

The sums are

#

So the xor of all the numbers is

image.png
#

So 4

fiery cosmos
# regal spoke Here is how I think about the xor of those numbers.

I explained it to myself that because ordering of XOR does not matter, that I can then place two same numbers next to each other, same for all other duplicate numbers and then at the end I can place number that is not duplicate...then XOR for all duplicates will return 0 and 0 with non duplicate will return that number

jolly mortar
#

yeah

fiery cosmos
#

Hi I know python a bit. but need a friend to learn and dicuss python in god level

naive oak
regal spoke
naive oak
#

oh so the first bucket starts at 0

#

ic

regal spoke
#

Yes

naive oak
#

cool

#

i will keep that in mind

lilac cradle
#

is there a way to play with the individual bits of a float? or just to see them

unborn sundial
#

Does someone have implementation of parallel Floyd Warshal for all shortest paths finding in a graph?

#

Compiling list of solutions i was able to find, but so far all of them in languages i barely know, or with no code examples how to interact with it
Could be cool finding smth more documented

#

my goal to implement Parallel Floyd in Golang, but i am well versed with Python too.
Java version as example would be okay too. Probably i can handle C# version too.
C and C++ i would struggle but very hardly able to read and interact with
Heck... i would be glad even for Javascript/Typescript version
Just smth in... Common enough normal language for more or less regular mortals.

snow ledge
#

i’m using tkinter to create text boxes and buttons and i’m trying to use a dictionary to separate the buttons so they can have separate text but the every time the code is run it updates the text in all previous text boxes as well


def BoxAdd(col, row, Col, Row, Location, Number, STRtext = "", width=50, Done=True):
    #STRtext = ExcelLoader.cellInfo(Col, Row)
    if Location == widget_frame:
        textBox[Number] = tk.Entry(Location, width=width, textvariable=inputString)
        ButtonNew = ttk.Button(Location, text="Done", command=lambda: GetString(1))
        ButtonNew.grid(column=col + 1, row=row, pady=5, sticky='ew')
    else:
        textBox[Number] = tk.Entry(Location, width=width, textvariable=infoString)
        ButtonNew = ttk.Button(Location, text="Done", command=lambda: GetString())
        ButtonNew.grid(column=col + 1, row=row, pady=5, sticky='ew')
    print(Number)
    textBox[Number].delete(0, tk.END)
    textBox[Number].insert(0, STRtext)
    textBox[Number].bind("<FocusIn>", lambda e: textBox.delete('0', 'end'))
    textBox[Number].grid(column=col, row=row, pady=5, sticky="ew")
fiery cosmos
unborn sundial
lean walrus
#

because ChatGPT is stupid

lean walrus
fiery cosmos
#

I see, I was using it several times for DSA and I haven't had bad experience

unborn sundial
# lean walrus can you post implementations you found somewhere? i may be able to help to trans...

I found those scientist papers explaning it and showing different pseudocodes
https://cse.buffalo.edu/faculty/miller/Courses/CSE633/Asmita-Gautam-Spring-2019.pdf
https://moorejs.github.io/APSP-in-parallel/
https://en.wikipedia.org/wiki/Parallel_all-pairs_shortest_path_algorithm

I found this version in C. with code example/tests how to launch
https://github.com/domdicarlo/parallel-floyd-warshall/blob/master/src/floyd_warshall.c
this version in Java. but no code examples how to work with it
https://rma350.github.io/2012/06/13/all-pairs-shortest-path-in-parallel-with-floyd-warshall-in-java.html
this version in Cuda language (first time seeing such language)
https://github.com/koallen/parallel-floyd-warshall

The goal is ...identifying is it real Parallel Floyd? if yes... then implementing it ^_^
I have final target set in Golang, that i can solve currently with best method as parallelized (in trivial method according to wiki page) through Johnson/Dijstra method in just 6 seconds for 2150 vertixes and 15k edges

#

i have sequential Johnson in golang that can solve the data in 30 seconds

#

i have sequential algorithm for Floyd that can solve the data in 2 minutes

#

So.. if the algorithm for parallelized Floyd will be implemented correctly, it should be showing same results as other algos, and definitely faster than 2 minutes of its sequential Floyd version

lean walrus
#

java version should be pretty easy to translate to python

unborn sundial
#

yeah.... i somewhat thinking about using Java version first too

lean walrus
#

you posted wrong link for cuda lang version
but i dont think i wanna see it anyway 😄

unborn sundial
unborn sundial
lean walrus
#

no :(
but i probably have java installed, and it should not be too hard

unborn sundial
#

ergh.. i have java installed too and at this level can launch stuff, nvm

lean walrus
unborn sundial
#

that is an interesting choice

unborn sundial
unborn sundial
#

it does work. and i managed to run it locally

#

For some interesting reason it completely crashes if trying to change matrix size though

#

i find this version suspicious as it is not matching scientist papers too much though

warm steeple
#

can you recommend any good python e-book about data structures and algorithms. Also for OPP as well

unborn sundial
#

u should give a try regardless of its language

haughty mountain
warm steeple
haughty mountain
#

!e @lilac cradle

import ctypes
i = ctypes.cast((ctypes.c_double*1)(1234.0), ctypes.POINTER(ctypes.c_uint64)).contents.value
print(f'{i:064b}')
halcyon plankBOT
haughty mountain
#

maybe looking at a double is a tad overkill

#

!e

import ctypes
i = ctypes.cast((ctypes.c_float*1)(1234.0), ctypes.POINTER(ctypes.c_uint32)).contents.value
print(f'{i:032b}')
halcyon plankBOT
unborn sundial
#

@lean walrus Wait a second...

#

...what if there are different versions of Parallel floyd implementation

#

and others just bruteforced in some way hmm

#

uh... i need a good understanding of Floyd parallel algo to understand if the found answer is correct

#

The scientist paper does hint there are different versions of Floyd parallelizations.

figure18.png
lean walrus
#

i have no idea, i never heard of this algo before

unborn sundial
#

yeah.. don't try translating it to python. it is very questionable to find what is the answer
resources are rather scarce about it

lean walrus
#

first java version says this:

On a graph of 3000 nodes, the single threaded mode took 130 seconds, while the multithreaded mode (on an 8 core machine) took 37 seconds.

isnt this suspicious?
i expect it to be around 8 times faster

unborn sundial
haughty mountain
#

I wonder what's the chance I got this correctly

#

!e

import ctypes

def get(n, i, s):
  return (n >> i) & (2**s - 1)

def decompose(f):
  i = ctypes.cast((ctypes.c_float*1)(f), ctypes.POINTER(ctypes.c_uint32)).contents.value
  return get(i, 0, 23), get(i, 23, 8), get(i, 31, 1)

mantissa, exp, sign = decompose(-3.14)
mantissa |= 1<<23
print((-1)**sign * 2**(exp - 150) * mantissa)
halcyon plankBOT
haughty mountain
#

neat

lean walrus
#

nice

haughty mountain
#

@lilac cradle this

unborn sundial
#

that is bizarre

lean walrus
#

sequential = single-threaded?

lilac cradle
#

neat

unborn sundial
#

sequential = single-threaded?
yeah, plus algo is not paralellized
wtf such time difference

lilac cradle
#

can you get nan from that?

haughty mountain
#

I mean, the reconstruction will fail

#

but you can get the parts

unborn sundial
lean walrus
haughty mountain
#

!e

import ctypes

def get(n, i, s):
  return (n >> i) & (2**s - 1)

def decompose(f):
  i = ctypes.cast((ctypes.c_float*1)(f), ctypes.POINTER(ctypes.c_uint32)).contents.value
  return get(i, 0, 23), get(i, 23, 8), get(i, 31, 1)

mantissa, exp, sign = decompose(float('nan'))
mantissa |= 1<<23
print((-1)**sign * 2**(exp - 150) * mantissa)


mantissa, exp, sign = decompose(float('inf'))
mantissa |= 1<<23
print((-1)**sign * 2**(exp - 150) * mantissa)
halcyon plankBOT
haughty mountain
#

err

#

oh, messed up copy

lean walrus
#

it feels nan enough

haughty mountain
#

bot please

#

let me re-execute

#

!e

import ctypes

def get(n, i, s):
  return (n >> i) & (2**s - 1)

def decompose(f):
  i = ctypes.cast((ctypes.c_float*1)(f), ctypes.POINTER(ctypes.c_uint32)).contents.value
  return get(i, 0, 23), get(i, 23, 8), get(i, 31, 1)

mantissa, exp, sign = decompose(float('nan'))
mantissa |= 1<<23
print((-1)**sign * 2**(exp - 150) * mantissa)

mantissa, exp, sign = decompose(float('inf'))
mantissa |= 1<<23
print((-1)**sign * 2**(exp - 150) * mantissa)
halcyon plankBOT
haughty mountain
#

nan, and +inf

#

well, one possible nan

#

the parts will be more interesting probably

#

!e

import ctypes

def get(n, i, s):
  return (n >> i) & (2**s - 1)

def decompose(f):
  i = ctypes.cast((ctypes.c_float*1)(f), ctypes.POINTER(ctypes.c_uint32)).contents.value
  return get(i, 0, 23), get(i, 23, 8), get(i, 31, 1)

mantissa, exp, sign = decompose(float('inf'))
mantissa |= 1<<23

print(f'{sign:01b} {exp:08b} {mantissa:024b}')
halcyon plankBOT
haughty mountain
#

yeah, inf has a very specific pattern

#

largest exponent, mantissa bits are all zero, positive sign

lean walrus
#

-inf is the same, but with negative sign?

haughty mountain
#

!e nan is probably weirder

import ctypes

def get(n, i, s):
  return (n >> i) & (2**s - 1)

def decompose(f):
  i = ctypes.cast((ctypes.c_float*1)(f), ctypes.POINTER(ctypes.c_uint32)).contents.value
  return get(i, 0, 23), get(i, 23, 8), get(i, 31, 1)

mantissa, exp, sign = decompose(float('nan'))
mantissa |= 1<<23

print(f'{sign:01b} {exp:08b} {mantissa:024b}')
halcyon plankBOT
haughty mountain
#

ok, the one used is pretty similar

haughty mountain
#

!e

import ctypes

def get(n, i, s):
  return (n >> i) & (2**s - 1)

def decompose(f):
  i = ctypes.cast((ctypes.c_float*1)(f), ctypes.POINTER(ctypes.c_uint32)).contents.value
  return get(i, 0, 23), get(i, 23, 8), get(i, 31, 1)

mantissa, exp, sign = decompose(-float('inf'))
mantissa |= 1<<23

print(f'{sign:01b} {exp:08b} {mantissa:024b}')
halcyon plankBOT
haughty mountain
#

yup

lean walrus
#

i guess nan is a number with largest exponent~~, but not an inf~~ and nonzero mantissa

haughty mountain
#

yeah, there are many many nans

lean walrus
#

so there should be 2^24-2 nans

unborn sundial
#

calculating in a fast way Graphs to find all shortest paths is a such wormhole
that i feel incredibly lucky accidentally discovering parallelizing Johnson algo and receiving 6 seconds results.

#

Floyd is full of... incorrect answers.

#

Incredible. I just changed float64 to int64, and algorithm became 60% faster for floyd 😄

lean walrus
#

in go?

unborn sundial
lean walrus
#

well, integer arithmetic always was faster than float arithmetic

unborn sundial
#

that is interesting to find... what if using lesser integer size in addition
will the be worthy speed up ^_^ lets see

#

55seconds over 60seconds. not really worthy and may be accidental decrease.

lilac cradle
#

Might try implementing floats from scratch in py, just to understand them better

haughty mountain
outer rain
#

I've done it

#

it's.... a little fun

unborn sundial
#

I don't recommend it
I've done it
same

haughty mountain
#

breaking floats apart is fun

unborn sundial
lean walrus
#

i never liked graph algos :(

unborn sundial
#

First earned money. 4 thousands of roubles in total and tripple hot dog. Those were good times.

haughty mountain
#

some are nice, some are pain

outer rain
#

I like graphs

lean walrus
#

i like graphs of functions, but not graphs that are related to graph theory

outer rain
#

I can't even name a single graph algorithm I don't like

#

there are a few garbage algorithms ofc (micro-macro tree comes to mind), but aside from that, it's genuently fun

lean walrus
#

it is kinda confusing to call two different things "graphs"
in russian it is simpler: graph is a thing with vertices and edges, "graphic" is a visual representation of a function

lilac cradle
#

Graph algorithm? smh just go through whatever function and get its value for a given dx (i joke but this IS usually how i graph stuff lol)

haughty mountain
#

wrong graph 🙃

lilac cradle
#

ye

lilac cradle
#

btw is there a good pseudorandom noise function in python? ive been using this to generate random values from coordinates for my perlin noise:

def hash_noise(x,y,seed=0,use_float=True,n_bytes=1):
    hsh = hashlib.shake_128(f"{x}{y}{seed}".encode())
    n = int.from_bytes(hsh.digest(length=n_bytes))
    if use_float:return n/(2**(n_bytes*8))
    return n

this seems to work well, but im wondering if there's a more 'optimal' way to do it
(if you're wondering why i use hashlib and don't just call hash() it's because hash() is randomized on program start)

also, would using struct for getting the value from the bytes be better or should i just get the int value and then divide it if necessary? i assume the latter since getting float requires me to use 4 bytes and then can give me literally any float value so i need to divide anyway

exotic parrot
#

hi! I have some issues with my code,

 def get_entries_on_day(self,day):
        list_of_activities = []
        for i in self.entries:
            if i.day == day:
                list_of_activities.append(i.description)
        print(list_of_activities)

I created this method inside of a class called "Agenda"
I want to retrieve the acitivities that are happening on the same day, I tested it but it always returns []

#

I can't seem to find why it's happening

#

the code I execute is basically

entry1 = Entry("w","2","5","12","loc1")
entry2 = Entry("u","2","1","22","loc2")
agenda = Agenda()
agenda.add_entry(entry1)
agenda.add_entry(entry2)
agenda.get_entries_on_day(2)
#

the day is the second attribute of Entry

#

self.entries returns a location for some reason apearantly?

naive oak
#

is there a name for when you have a dp table and you're doing bottom up dp, but instead of filling up the table by iterating and setting each element to something computed from previous values, you iterate and for each cell you adjust the values ahead of the current cell that would be affected by that cell?

#

like say you have a recurrence a[n] = 2*a[n-1] - a[n-3]
the first way would be something like

for i in range(3, n):
    a[i] = 2*a[i-1] - a[i-3]

and the second way would be something like

for i in range(n):
    a[i+1] += 2*a[i]
    a[i+3] -= a[i]
#

that's just a rough sketch of what it'd look like

opal oriole
#

Often mentioned in neural network implementations, you can either loop over all the outputs in the next layer and compute their value based on the previous layer values and the weights (fan-in), or you can loop over the inputs and add to each output the product of the input and the weight (fan-out).

#

(naming comes from looking at it as a (compute) graph (dp specifically represents things as a DAG)) (not referring to a fan graph in graph theory, but rather it being shaped like an open hand fan)

opal oriole
#

Fibonacci example (fan-out approach):

image.png
unborn sundial
#

@lean walrus yay. I concluded my madness with those all shortest paths graph searching.
From original 2 minutes and 20 seconds with Floyd... i calculate now all shorest paths in 1.5 second 🙂
More than good enough speed

#

As end result => i just optimized further johnson's algorithm i already used

#

i realized i can exclude from calculations searching all shortest paths originating from vertex i don't care about it (Johnson's Algorithm using Dijkstra under the hood is flexible enough to exclude such stuff in an easy way)

#

that gave me the last push to receive very satisfying speed of calculations

#

probably i can even do it even in 1 second, if i exclude some extra objects

solemn moss
outer rain
#

no fcb is ok

unborn sundial
regal spoke
unborn sundial
#

it is not taking time to care about. shrugs.

regal spoke
#

uhm

regal spoke
unborn sundial
regal spoke
#

Yes

#

Johnson's algorithm is a technique for removing nagative edge weights from the graph, so you can use dijkstra

#

But if you have no negative edge weights to begin with, then you can just straight up use dijkstra

unborn sundial
#

thanks. i should refactor not used code then
And add note about it into further optimziation => That i need only DijstraAPSP part of Johnson for me

#

That also opens room to utilize this wiki page for different solutions more directly
https://en.wikipedia.org/wiki/Parallel_all-pairs_shortest_path_algorithm
As it literally recounts all options to parallel stuff for exactly my usage case more or less
Except i doubt that i will receive at this point with parallel Floyd better speed than with DijkstraAPSP optimized
the alternative way to parallel Dijkstra is interesting though, but probably no big points too may be for me.

Parallel all-pairs shortest path algorithm

A central problem in algorithmic graph theory is the shortest path problem. Hereby, the problem of finding the shortest path between every pair of nodes is known as all-pair-shortest-paths (APSP) problem. As sequential algorithms for this problem often yield long runtimes, parallelization has shown to be beneficial in this field. In this article...

regal spoke
#

You could parallelize DijkstraAPSP

#

Just run multiple dijkstras at the same time starting at different nodes

unborn sundial
#

ergh? I have it already parallelized. Article provides it

# 
type DijkstraResult struct {
    source      int
    dist_result []int
}

func (g *Johnson) Johnsons() [][]int {
        // ..other code before...
    is_sequential := false

    if is_sequential {
        for s := 0; s < g.vertices; s++ {
            distances[s] = g.dijkstra(s)
        }
    } else {
        dijkstra_results := make(chan *DijkstraResult)
        for s := 0; s < g.vertices; s++ {
            go func(s int) {
                dist_result := g.dijkstra(s)
                dijkstra_results <- &DijkstraResult{
                    source:      s,
                    dist_result: dist_result,
                }
            }(s)
        }
        for s := 0; s < g.vertices; s++ {
            result := <-dijkstra_results
            distances[result.source] = result.dist_result
        }
    }
        // ..other code after...
}
#

just added parallelization to Johnson ^_^

#

really simple parallelization with golang go routines and channels

#

for some sanity providing switch back to sequential choice, in case of need for debugging or smth

regal spoke
#

ok

unborn sundial
regal spoke
#

Just to be clear about the names. Johnson's algorithm is a kind of obscure technique used for graphs with negative edge weights, I don't think mentioning Johnson's algorithm in the article makes any sense. The algorithm you actually want to talk about is DijkstraAPSP.

#

Btw about an idea for speeding things up. Is your graph directed?

unborn sundial
#

is there a simplified algo for indirected graphs?

regal spoke
#

I don't think so, no. Other than dist(s->t) being the same as dist(t->s). So sometimes you can save a factor of 2

haughty mountain
unborn sundial
# haughty mountain channels is interesting design for doing parallelism <:pithink:65224755990927770...

they are very lazy convenience to make things sure there are no racings
golang is not complaining you that u have racings (it will complain if u try data writing to shared hashmap for example) (there is special data racing protected hashmap though)
So i am kind of forced to use them in the situation when i wish to collected data results in the least problematic way

Otherwise i could have used things like mutexes though
to lock final shared data structure during writing operatoins
that probably would have worked too
plus using sync.WaitGroup thing to syncronize awaiting of parallel calculations.
Alternative are available, but they are less elegant (and more "traditional" for other languages)

regal spoke
#

There are some interesting heuristics that might speed things up depending on the structure of the graph

#

For example, suppose there is an edge that if removed splits the graph in two

#

Then you effectively only need to solve the APSP on each part seperately

#

If the graph is "dense", then these kind of heuristics wont work

#

Another thing to consider is if there are edges that are never useful for any shortest path (edges with very high weight). Removing them could help speed things up (if they exists).

unborn sundial
#

i calculate distances for trading routes between different space bases

#

which are located across the galaxy in a more or less uniform way