i think they are definitely not linear
#algos-and-data-structs
haughty mountain
ok, so value(100%)-value(10%) is roughly value(10%) - value(1%)
so yeah, looks logarithmic
max being (0, 240) is kinda bizarre though
haughty mountain
wrong way around I think
x = log(61440)
with some scaling factor
err, maybe I'm dumb
azure osprey
these things confuse me too
azure osprey
e**10 is 22k60 nowhere close to 33920
haughty mountain
should be log, right?
main peak
I need help for an exercice, Idk if it's the right place to ask it ??
worthy escarp
probably better to use one of the help channels, under AVAILABLE HELP CHANNELS
azure osprey
prediction: 50% would be roughly 57297
lemme check quick
stray fractal
why the hell is there no `float.to_bytes`?
what would that do
azure osprey
prediction: 50% would be roughly 57297
57344 but close yea, what formula did you use
azure osprey
get the byte representation of the float
oh its a float?
azure osprey
wtf is that
stray fractal
get the byte representation of the float
ah so like õ¼º?
haughty mountain
wtf is that
idk, log10(percentage) gives a straight line plotting, so I know it's basically right
the rest is just scaling things
stray fractal
ah so like `õ¼º`?
maybe you mean bit representation idk
azure osprey
the rest is just scaling things
well its exactly 0.5 but yea its close
haughty mountain
`(log10(0.5) + 2) / 2 * (61440 - 33920) + 33920`
the values here are just based on the values of 1% and 100% you provided
azure osprey
`(log10(0.5) + 2) / 2 * (61440 - 33920) + 33920`
that gives me 51902, how did you arrive at 52797?
haughty mountain
In [52]: (log10(0.5) + 2) / 2 * (61440 - 33920) + 33920
Out[52]: 57297.827259663616
the 1% gets approximated (float precision issues)
azure osprey
```py
In [52]: (log10(0.5) + 2) / 2 * (61440 - 33920) + 33920
Out[52]: 57297.827...
is math.log different from log10?
haughty mountain
math.log is the base e log
you can scale it and it will be correct
math.log(x)/math.log(e)
azure osprey
ok
haughty mountain
let me work out if the formula ends up any nice
azure osprey
sure thaks
haughty mountain
fwiw, they are interesting values
>>> bin(57344)
'0b1110000000000000'
>>> bin(61440)
'0b1111000000000000'
the 50% and 100% points
stray fractal
the 50% and 100% points
one bit flip away
azure osprey
hmm
haughty mountain
(log2(x) + 1) * 2**12 + 57344
I guess that's nicer?
but still some magic values
azure osprey
why are you adding 57344
haughty mountain
because I'm fitting my range to match your measured values
azure osprey
is it not possible to do this without adding magic values at all?
haughty mountain
log(percentage) is proportional to the values
that's all I'm basing my things on
the multiplying and adding is to scale to fit the measured values
(0.5, 57344) and (1.0, 61440)
the 2**12 is 61440 - 57344
azure osprey
well 33920 is not for 0.01 but its for 0.010009765625 which is why the formulas are giving slight deviations
4096
haughty mountain
well 33920 is not for 0.01 but its for `0.010009765625` which is why the formula...
that's why I wanted to use 0.5 and 1.0
which are exact in floating point
sadly things are still a bit off
!e
from math import log2
print((log2(0.010009765625) + 1) * 2**12 + 57344)
halcyon plankBOT
@haughty mountain :white_check_mark: Your 3.11 eval job has completed with return code 0.
34232.53301091567
i guess its probably better to leave it at that and add a note about it in the docstring
this formula is very accurate tho
and it is probably used at tons of more places (knobs)
haughty mountain
except it's wrong for a bunch of values, no?
like the value close to 0.01
it's not far off, but still off
azure osprey
!e
```py
from math import log2
print((log2(0.010009765625) + 1) * 2**12 + 57344)...
its off for the exact value as well
haughty mountain
yes, that's what I mean
azure osprey
FL is coded in delphi so dunno what type of floats or encoding that uses
stray fractal
!e
```py
from math import log2
print((log2(0.010009765625) + 1) * 2**12 + 57344)...
it should be log2'ing a value between 0.009494 and 0.009495
azure osprey
yes, that's what I mean
maybe there's some hard constant left to add to
haughty mountain
it should be `log2`'ing a value between `0.009494` and `0.009495`
right
In [66]: x = 33920
...: 2**((x - 57344) / 2**12 - 1)
Out[66]: 0.009494119999847414
so this is why I'm quite certain it's logarithmic
octave:35> data = [0.01 33920; 0.1 47512; 0.5 57344; 1.0 61440];
octave:36> plot(log10(data(:,1)), data(:, 2), 'o-')
very nice line
(log base is irrelevant, I used log10 because it was convenient at the time)
azure osprey
so this is why I'm quite certain it's logarithmic
```m
octave:35> data = [0.01 3...
oh this is awesome
i always wanted a tool that could build a graph like that from data
haughty mountain
there are loads of options for that
octave is basically open source matlab
you can use matplotlib from python
and there are heaps of other tools for generating some quick plots
azure osprey
so this is why I'm quite certain it's logarithmic
```m
octave:35> data = [0.01 3...
so what's the formula for this then?
reverse formula
i.e get 0.5 from 57344
lean walrus
so this is why I'm quite certain it's logarithmic
```m
octave:35> data = [0.01 3...
what language is this?
haughty mountain
what language is this?
see left hand side of the prompt 😛
haughty mountain
```
(log2(x) + 1) * 2**12 + 57344
```
just solve this for x
haughty mountain
right
```py
In [66]: x = 33920
...: 2**((x - 57344) / 2**12 - 1)
Out[66]: 0....
i.e. this, though it could probably be simplified a tad
lean walrus
see left hand side of the prompt 😛
smart, thanks 😄
haughty mountain
I can get it down to this, but it's not exactly easy to figure out where it comes from
perc = 2**(x / 2**12) / 2**15
or the reverse
x = 2**12 * log2(perc*2**15)
= 2**12 * (log2(perc) + 15)
these numbers come out very clean, which I guess is a good sign
I guess the third byte is still unexplained
though it might just be a flag
azure osprey
I guess the third byte is still unexplained
do you think its some kind of factor useful for the formula?
it might as well be some delphi logarithmic integer encoding
haughty mountain
probably not useful for the value itself
granted 63 is also an interesting binary number
azure osprey
you are indeed good at math
haughty mountain
0b00111111
haughty mountain
try verifying 0.25 and 0.125
azure osprey
ok hang on
haughty mountain
those should be exact floating point values
haughty mountain
In [83]: 2**12 * (log2(0.25) + 15)
Out[83]: 53248.0
In [84]: 2**12 * (log2(0.125) + 15)
Out[84]: 49152.0
neat
haughty mountain
I mean, I can step through the whole process. I plotted and saw that log(perc) ~ x
I have two values I assume to be exact
(0.5, 57344) and (1.0, 61440)
ok, so log2(1.0) = 0 and log2(0.5) = -1
I would like to scale and translate this to match my values
i.e. I want to translate the range [-1, 0] to [57344, 61440]
haughty mountain
[-1, 0]
[0, 1] # + 1 nice thing to start with
[0, 4096] # *(61440 - 57344) fix the scaling
[57344, 61440] # + 57344 shift to the correct place
x = (log2(perc) + 1) * (61440 - 57344) + 57344
the rest is just trying to simplify this
azure osprey
```
x = (log2(perc) + 1) * (61440 - 57344) + 57344
```
yea you had calculated that formula earlier
haughty mountain
that is quite a process
it's pretty standard I would say
try to figure out a relation that makes things proportional, and then scale things appropriately
azure osprey
with this formula now all I hopefully need is an adapter
haughty mountain
granted, this is the kind of thing I encountered a bunch when studying in uni
azure osprey
unless the 3rd byte 63 does some of its own magic
haughty mountain
because physics and numerical analysis
azure osprey
i never was quite a math guy
haughty mountain
idk what the 3rd byte is
given that it's always either 0 or 63 it feels like some kind of flag
azure osprey
i am very suspicious that it is related somehow to the actual formula (if it might be different or some conditional thing)
haughty mountain
maybe it encodes what kind of value it is
azure osprey
given that it's always either 0 or 63 it feels like some kind of flag
63 is not a single flag though its a bunch of them
haughty mountain
if it's logarithmic/linear
azure osprey
maybe it encodes what kind of value it is
yea like a unit
azure osprey
if it's logarithmic/linear
oh that's a good line of thinking
haughty mountain
if it's logarithmic/linear
granted, this doesn't make too much sense
because 0 means very different things for linear and logarithmic
idk
azure osprey
maybe there are more types as well, which i misinterpreted as just a combined 4 byte integer
haughty mountain
I feel pretty certain the first two bytes is the value though
azure osprey
but on a whole, 63 is the majority
languid forum
holy shit u guys r big brains
azure osprey
not me
azure osprey
I feel pretty certain the first two bytes is the value though
might as well make you a contributor for this formula you found out, big discovery! 😄
half crag
hi
my name is Pulkit Sharma
I'm amateur coder
right now i know CPP and a little Python
nice to meet you all
azure osprey
@haughty mountain hi there
You had mentioned you knew some binary parsing libraries before
haughty mountain
I know about stuff like kaitai that's kinda made for this
there should be a few others
glass river
anyone know backtracking
stack = []
res = []
def backtrack(numbs):
res.append(stack)
for i in range(len(numbs)):
stack.append(numbs[i])
backtrack(numbs[i:])
stack.pop()
backtrack(nums)
return res
trying to return power set but its not working
for example nums is [0] and the power set is [[],[0]] but it returns set with two empty sets
first it puts the empty set into the res list
then it iterates over the set, the example set only contains one element
it adds 0 to stack then recursive call
the recursive call should add [0] to the stack as the stack contains [0], even the recursive call prints [0] for stack but it appends an empty list
azure osprey
I know about stuff like kaitai that's kinda made for this
Kaitai doesn't support serialisation tho
glass river
solved it but am wondering why the former didnt work
stack = []
res = []
def backtrack(numbs,curr):
res.append(curr)
for i in range(len(numbs)):
backtrack(numbs[i+1:],curr + [numbs[i]])
backtrack(nums,[])
return res
its the same idea implemented differently but the first implementation is more intuitive to me
dont want to make the same mistake onna test
fiery cosmos
hi! is this sorting algorithm a quicksort?
dze ccf bkw hwy pjk xce aux qtr xpa atm
ccf dze bkw hwy pjk xce aux qtr xpa atm
bkw ccf dze hwy pjk xce aux qtr xpa atm
aux bkw ccf dze hwy pjk xce qtr xpa atm
aux bkw ccf dze hwy pjk qtr xce xpa atm
atm aux bkw ccf dze hwy pjk qtr xce xpa
fiery cosmos
Where will I insert a key 25 in this AVL tree?
haughty mountain
hi! is this sorting algorithm a quicksort?
dze ccf bkw hwy pjk xce aux qtr xpa ...
for sure not, e.g. you can't get from line 1 to 2 though a quick sort partitioningstep
also, what you have there is not a description of an algorithm...
bright geyser
I'm confused whts goin on in this removeFirstNode method(removes the head of the Linked List, sort of mimicking a stack).
They set, temp = head
but then, head = head.next, and then temp = None.
However, since temp = head, isn't temp = head.next as well?
And if you're setting temp = None, aren't you setting head.next = None as well?? How does Python even work here.
what the fuk is goin on
dreamy valley
I'm confused whts goin on in this removeFirstNode method(removes the head of the...
This looks like it was poorly translated from another language by someone who didn't understand it
bright geyser
yes mb I don't get Python at all, so I was only able to muster up tht much to explain wht im confused at
man this looks like simple shit I should alreayd know wtf
dreamy valley
unless I'm completely missing something, it's equivalent to ```py
if not head:
return None
return head.next
what about deleting the first node?
dreamy valley
temp isn't even doing anything
dreamy valley
what about deleting the first node?
it'll get garbage collected if nobody is using it anymore
dreamy valley
but if you keep the original head around you will still be able to access the whole original list
dreamy valley
whts that? Is that like a built-in clean-up service in Python?
basically, yes
bright geyser
oooo so if I return the 2nd node only, then thts the same as taking out the first node completely
dreamy valley
anything that you aren't keeping a reference to gets deleted eventually
cloud island
Im a noob so this should be a simple question.
if "sample 1" or "sample 2" in submission.selftext.lower() or submission.name.lower() and submission.id not in posts_replied_to and post.author != r.user.me():
I want this to run if either "sample 1" OR "sample 2" is in either one of the two lists, as long as the last 2 and statements are true. Did I do this right?
I use Arduino language (similar to C/C++) so Im used to putting everything in parenthesis for order.
if (("sample 1" or "sample 2") in (submission.selftext.lower() or submission.name.lower())) and (submission.id not in posts_replied_to) and (post.author != r.user.me()):
Here I added parenthesis to demenstrate how I want it to behave.
cloud island
Apparently, that's not correct. I may or may not have spammed the same test comment to the last 30 posts on the r/test subreddit. How do I fix this to work correctly?
stuck wind
Hi, I don't quite understand this question. If there is "aabc" shouldn't the output be "a0bc" since b is not repeating ?
scarlet sonnet
What is the answer of this?
The if statement consists of two part: and?
halcyon plankBOT
Hey @sturdy vapor!
agile sundial
is that even a question
sturdy vapor
https://paste.pythondiscord.com/abugaxivux
Hey there. I'm playing around with ways of optimizing run time for Monte Carlo simulations in Python using a basic dice game simulator. I'm trying to make this thing run as fast as possible on one core before I start trying to implement multiprocessing. Are there any ways which I can make this run faster than it already does? I've switched all while loops I previously had to for loops, removed a loop in roll_dice() by passing it trial_number and generated all the random numbers that will be used in the simulation beforehand using numpy.
hybrid epoch
```py
stack = []
res = []
def backtrack(numbs):
...
I'm no backtracking expert but I can tell you a few things wrong with your code. You're appending reference copies of the list stack into res. Your backtracking algorithm eventually clears the contents of the list stack. You must copy the list by value and append that into res instead.
Anyway, I tried running your algorithm but it recurses indefinitely. It needs a proper stopping condition
haughty mountain
I'm no backtracking expert but I can tell you a few things wrong with your code....
it should be numbs[i+1:] in the recursive call
that should fix the infinite recursion
cinder cedar
So for time complexity we use Big O and omega and theta, but they are not related to worst average best cases right?
Like Big O isn’t worst
Theta isn’t average
Omega isn’t best
?
cinder cedar
Yes I know
haughty mountain
think of them as <=, >= and =
cinder cedar
I know but they are not related to worst best average?
haughty mountain
I can give upper/lower/tight bounds on the average running time
cinder cedar
Or another question how I know worst best avg
haughty mountain
if you consider all possible inputs (and not an average over them) then O is the worst case and Ω is the best case
so what they end up meaning depends on what you're bounding
cinder cedar
So O is not always mean worst case?
haughty mountain
what do you mean by worst case?
I can give an upper bound on average complexity that's better than the overall worst case
azure osprey
@haughty mountain
remember the formula you gave me?
2**12 * (math.log2(obj) + 15)
well log2 doesn't work for 0
raises ValueError: math domain error
haughty mountain
well yeah
azure osprey
it took me a day to figure that one out because construct was swallowing the exception
and serialising incorrectly
haughty mountain
if anything it's -∞
haughty mountain
you probably need to special case it, yeah
azure osprey
well 0 is the minimum value in uint16 representation
so I can just do if value == 0.0: return [0, 63] something like that
actually [0, 0] because the 63 comes down to 0 for a value of 0
haughty mountain
so I can just do `if value == 0.0: return [0, 63]` something like that
0.0 shouldn't become zero, should it?
azure osprey
0.0 shouldn't become zero, should it?
i mean that's what get stored when the knob is at absolute 0
haughty mountain
yeah, I guess that's one way to get rid of the -inf issues
put a special value instead
azure osprey
but then what about for 0.00000001 type of extremely close to 0 values?
i should probably use math.isclose but then it might cause a change in values when serialised as-is which is undesired
fucking floats
haughty mountain
you can for sure get values outside the valid range
it's not really a float issue
0.0 is special
that't about it
the other results should be clamped to the correct range
azure osprey
Not quite expected huh
haughty mountain
it's what I expected 😛
azure osprey
the other results should be clamped to the correct range
maybe i should check if result is negative and just set it to 0 instead?
haughty mountain
why not just special case zero and clamp the value?
unless you want the behavior you described
azure osprey
wdym by clamp the value?
haughty mountain
what does the actual tool do?
azure osprey
maybe i should check if result is negative and just set it to 0 instead?
is this different
azure osprey
what does the actual tool do?
if i set the knob value to 0.000001 something?
haughty mountain
if i set the knob value to 0.000001 *something*?
right
clamping means you have a valid range [a, b] you put the closest valid point
haughty mountain
ok, then what you propose matches their behavior
azure osprey
0.0001 gets set to something close by but not 0, 0.00001 gets set to plain 0
haughty mountain
clamping means you have a valid range [a, b] you put the closest valid point
if valid range is [2, 4]
0 -> 2
1 -> 2
2 -> 2
3 -> 3
4 -> 4
5 -> 4
6 -> 4
that's a clamp operation
haughty mountain
if valid range is [2, 4]
```
0 -> 2
1 -> 2
2 -> 2
3 -> 3
4 -> 4
5 -> 4
6 -> 4
``...
I don't think python has clamp, but you can implement it like
max(2, min(4, x))
@haughty mountain Have another scaling problem, this time for frequency:
90 Hz is 5777
1500 Hz is 33145
8000Hz is 55825
min 0 - 0hz
max 65536
(not 61440 😛
haughty mountain
could you give some nice values? like some powers of 2
haughty mountain
power of 2 frequencies I meant
since that's the side that I'm afraid will have rounding issues
azure osprey
yea right my bad
its just that this knob accepts a float from 0 to 1 too
128Hz (approx) is 7832
can't set it very exactly, in float its 0.1195
azure osprey
2048Hz - 37218 - 0.5679
azure osprey
<:pithink:652247559909277706>
but atleast its some curve
haughty mountain
could be log(constant + x) 
do you have some smaller values as well?
like 128, 64, ...
azure osprey
like 128, 64, ...
haughty mountain
the small values are the ones that will tell me if my guess is all wrong or not
azure osprey
4096Hz - 46565 - 0.710525512695313
azure osprey
the small values are the ones that will tell me if my guess is all wrong or not
ok its hard to go accurate with low values margin of error is high
haughty mountain
just roughly correct is fine
I just want some nice spread over orders of magnitude
haughty mountain
interesting looking value
azure osprey
but not a good number
haughty mountain
interesting becausae
>>> 2**6
64
>>> 4**6
4096
exactly 10 and exactly 16000?
azure osprey
exactly 10 and exactly 16000?
yes
azure osprey
what is 16384 in Hz?
not even close
haughty mountain
(log(constant + freq), value) is so close to a line
azure osprey
maybe that's it?
azure osprey
(log(constant + freq), value) is so close to a line
ahh its not khz likely
haughty mountain
no, that's log(constant + freq) on x axis
where constant = 160 for now
which is just a random guess
azure osprey
that's good for a random guess 😄
haughty mountain
do you have any values outside 10 and 16000 where you are completely sure they are exact?
I guess 4096 and 63 was one?
haughty mountain
so the range is (10Hz - 0, 16khz - 65536)
err, you meant 65535 right?
azure osprey
err, you meant 65535 right?
no 65536
haughty mountain
wat
azure osprey
its a 4 byte integer
haughty mountain
do they use a 4 byte integer to be able to represent exactly 2**16?
but nothing above?
azure osprey
do they use a 4 byte integer to be able to represent exactly 2**16?
idk its everywhere around the format, spread like a plague
they use 2 bytes for storing 0-256
similarly 4 bytes for 0-65536
here is a test which passes (uses 65536 checks)
https://github.com/demberto/PyFLP/blob/596dcde80e7740a9219d4c233ddc219ac0846ac5/tests/test_mixer.py#L82-L92
halcyon plankBOT
tests/test_mixer.py lines 82 to 92
def test_insert_eq(get_insert: InsertFixture):
eq = get_insert("post-eq.fst").eq
assert eq.low.freq == 0
assert eq.low.gain == 1800
assert eq.low.reso == 0
assert eq.mid.freq == 33145
assert eq.mid.gain == 0
assert eq.mid.reso == 17500
assert eq.high.freq == 65536
assert eq.high.gain == -1800
assert eq.high.reso == 65536```or maybe its harder to notice changes in tuples:
(0, 0, 0, 0)
and
(0, 0, 1, 0)
than
(255, 255, 0, 0)
is super hard to see when manually checking big chunks of bytearrays
azure osprey
I guess 4096 and 63 was one?
4096 is integer representation for 63 hz
azure osprey
do you have any values outside 10 and 16000 where you are completely sure they a...
the knob only moves that much
haughty mountain
I'm a fraction of a % off 😭
looks close at a glance with all the constants roughly fitted
azure osprey
still close enough ig
azure osprey
looks close at a glance with all the constants roughly fitted
yea that looks accurate af
the frequency values were approx, as it was impossible to set the frequency exactly
haughty mountain
my values are consistently off
first 2 and last 1 point was used for computing constants
which is why they are at 0
or close to 0 anyway
not beautiful 🙂
-71718.57858698638 + 14165.208975887555*log(148.065401 + freq)
a different regression fit https://www.desmos.com/calculator/flxuyqogc7
rather than my manual hacky one 😛
that used only 3 points
granted this regression kinda has issues
since we have both very large and small numbers
but yknow, it's quite close
though it's a pretty weird format
azure osprey
Why wouldn't they just simple store 10 to 16000 if they had 4 bytes to begin with
It can be even done in 2
haughty mountain
it seems a bit suspect that the max would be at 16000Hz
azure osprey
It is
haughty mountain
since that's still in quite audible range
azure osprey
The filters it uses are old and CPU cheap
Ig never updated since they were coded back in 2000s sometime
Nobody really uses that feature, its just there. I only myself use if I am running low on CPU
native stratus
Any course for learn data strutture and algos from zero?
fiery cosmos
Is there an answer to if top down or bottom up dynamic programming is faster.
Or it just depends
fiery cosmos
Any course for learn data strutture and algos from zero?
Some in pinned messages
native stratus
Thanks
haughty mountain
Is there an answer to if top down or bottom up dynamic programming is faster.
depends, top down might not need to evaluate all states, if you need to evaluate everything bottom up avoids recursion overhead and the dp array is nice and compact in memory which gives you good cache usage
fiery cosmos
That still means no conclusive answer without more information right?
haughty mountain
yes, depends on the task
I prefer bottom up is that version is sensible
in part because python recursion is terrible
inland crane
Does anyone know what the worst case scenario is for the shell sort algorithm?
dreamy valley
which shell sort algorithm?
wikipedia has a whole table of gap sequences and their complexities
inland crane
oh that's a good question...
spare maple
can anyone here help me with a complex number python assignment i have ?
inland crane
I'm not sure, but I'll find out
haughty mountain
the stack for keeping track of free space is trivial, no?
start with all indices in the stack
if you need a free space to put something in, pop
if you delete an element push the newly free index on the stack
fiery cosmos
right right that's exactly what i'm attempting to do. i think what is tripping me up is how to do the chaining pointers. also i'm getting list index out of range errors so i must be going wrong somewhere. one good thing is that i was able to implement my quadratic probing going properly on my own
sorry that's not my current error, current error is int object has no attribute keys
so.. i'm reading a bucket incorrectly i suppose
fiery cosmos
i'll need to maintain a linked list of pointers (the chain) to support searches, i think
its not really clear if we have to support all the standard operations of hash tables like delete, insert, etc from the handout
here's what i have so far:
and after reading i'm sure you can see where this logic came from
but i want to tease out the error before going and further changing or possibly breaking things
last fulcrum
Hi guys. I got this question. Can anyone help me to figure out why my output is wrong please?
Question
Given a dict of accounts and a threshold int, make sure that all the accounts balance to meet the threshold
Example with threshold of 100
dict { "Acct1": 130, "Acct2": 90, "Acct3": 120, "Acct4": 70, }
Expected Output
Acct 1 -> Acct 2: 10 Acct 1 -> Acct 4: 20 Acct 3 -> Acct 4: 10
My code which is not working well
!e
def account_balance(account: dict, threshold: int) -> None:
temp_account = {}
accounts_list = []
for key, value in account.items():
if value > threshold:
temp_account[key] = abs(value - threshold)
accounts_list.append(key)
if value < threshold:
diff = abs(value - threshold)
for curr in accounts_list:
if curr != 0:
temp_account[curr] = temp_account[curr] - diff
print(f"{curr} -> {key} : {diff}")
dd = {
"Acct1": 130,
"Acct2": 90,
"Acct3": 120,
"Acct4": 70,
}
account_balance(dd, 100)
@last fulcrum :white_check_mark: Your 3.11 eval job has completed with return code 0.
001 | Acct1 -> Acct2 : 10
002 | Acct1 -> Acct4 : 30
003 | Acct3 -> Acct4 : 30
why do you need to maintain a linked list?
at least you don't need a separate linked list
your table is (several) linked lists already
with the pointers
fiery cosmos
why do you need to maintain a linked list?
i'm thinking of the series of pointers as a linked list where each pointer will point to the next array location if a given location is full
haughty mountain
look at anywhere you assign to keys
fiery cosmos
wdym
haughty mountain
or wait
you replaced a bucket with a key somewhere
look at any assignment to table[...] then
fiery cosmos
yes, you were correct
i have a new error, let me try to sort it
also, can i change
to include the for loop
to support when i have bucketsize > 1?
ah crap
then i'll have to return which bucket slot is open
so i'll need to also return i
haughty mountain
huh? == vs is doesn't matter here
oh hey, my previous answer is probably relevant
haughty mountain
look at anywhere you assign to `keys`
fiery cosmos
i'm having issue passing variables from one function to another
maybe i make it an attribute of openslot?
sry poor naming
gonna change openslot function name to isopen
i just want to be able to yield that to another function
haughty mountain
you could have it return an index or None
the return you have now is very awkward to use
fiery cosmos
concise
haughty mountain
well, you can't do that with the code you posted
fiery cosmos
i know
fiery cosmos
should i change my else: return False to else: return None?
fiery cosmos
i'm not following 😦
haughty mountain
I'm suggesting you return an optional result
i.e. on success return an int value (the index) on failure return None
because there is no such index
fiery cosmos
ok ok
looks like chaininsert has no scope for it
ah crap it doesn't color in here
oh i didn't implement your suggestion above yet 1s
haughty mountain
it's a fairly recent thing
walrus operator
basically assign and return the assigned value
fiery cosmos
oh wow
haughty mountain
you could also write the assignment above the if to do it without :=
fiery cosmos
well not the to n bit but it gets you closer with an in line assignment
hmm now i just need to fix up my else clause and figure out the pointer situation
lol this is getting confusing with all of the attributes and various functions and variables
hmm
got an error i've never seen
pop from empty list
fiery cosmos
hmm
so it is inside of a for loop but i don't really seem to be handling the case when isopen(newbucket) returns None
so perhaps i should wrap everything in the else statement in a while loop?
haughty mountain
so perhaps i should wrap everything in the `else` statement in a `while` loop?
and that would solve what?
fiery cosmos
hmm no idk
haughty mountain
how many elements should be popped in chaininsert?
fiery cosmos
as many as it takes until self.isopen(newbucket) returns an openslot
newbucket being a pop from a stack
the stack just being the integers of the array indices
haughty mountain
actually you have several problems here
fiery cosmos
oof
haughty mountain
you're not following the links at all
and the stack should be popped at most once
if you actually need a new bucket to link to
fiery cosmos
🤦♂️
ok, so i had p = 0 so that after i write a key somewhere, i can keep track of where with p and then set table[loc].pointer = whatever my insertion location ends up being
ohhh
i just remembered, i only have to implement chaining for when bucketsize = 1
so i don't have to worry about updating individual slots for the pointers
last fulcrum
@haughty mountain can you help me with my problem?
haughty mountain
your second if is pretty badly wrong
you can take more than is valid from an account, you can also end up taking more than you need
fiery cosmos
i guess i don't need that p var
fiery cosmos
haughty mountain
do you follow links?
fiery cosmos
ohhh
i'm picking up what you're laying down
obviously i need to check the bucket pointer
haughty mountain
and you should only give a new bucket if you absolutely need to
fiery cosmos
i should just go ahead and write key if the bucket pointer is None
haughty mountain
you still have a big bug on top of that
fiery cosmos
i'll get there
haughty mountain
how many times should you insert the key?
fiery cosmos
1
haughty mountain
how many times could your code insert the key?
fiery cosmos
datalen
haughty mountain
right
fiery cosmos
sheesh i am bad at this
haughty mountain
hint: ||break||
fiery cosmos
oh duh, i have break in my other insert loops
ok, how far off am i from something viable
nvm
i see error
i'm just trying to get this running so i have plenty of time for the analysis and adding collision counting and stuff
fiery cosmos
the pointer doesn't tell where to insert, only used for lookup, correct?
haughty mountain
the pointer doesn't tell where to insert, only used for lookup, correct?
not only lookup
you might hash to bucket h,
if h has room you can insert
if h is full but tells you that it's linked to bucket h', you'll need to check there
if h is full and not linked to anything...
fiery cosmos
so that logic nullifies my "if a pointer is None I should go ahead and write the key" statement
if h is full and not linked to anything, pop a new bucket from the stack
ok my slot = None is giving me trouble
haughty mountain
slot being None means the bucket is full
fiery cosmos
but that's the same as when theres nothing there and i want to write somewhere
oh, nevermind
if there is nothing there i return the empty index as openslot
damn i was really close then i lost my logic trail
im basically breaking up your conditions above into 3 if elif else statements
haughty mountain
fwiw you can also add functions to bucket to make the code easier to understand
e.g. why is isopen a function of the hash table?
it's kinda the bucket's job to know that
haughty mountain
and you could even add operations to bucket like "try_insert"
fiery cosmos
oh you know why, so then it has scope of bucketsize and other stuff
haughty mountain
and you could even add operations to bucket like "try_insert"
which could return True/False depending on if the insert succeeded
if insert failed, try linked bucket if it exists
fiery cosmos
yeah that's obviously a more logical approach, though adding those conditionals would make the mental tracking of what's happening more difficult, for me anyhow
maybe not
haughty mountain
maybe not
probably not
you can have the bucket perform a simple operation on itself
and then you can write the rest of the code using that abstraction
fiery cosmos
what like bucket.isfull
fiery cosmos
ok, but then i'd need to modify my existing linearinsert and quadinsert functions
haughty mountain
ok, but then i'd need to modify my existing `linearinsert` and `quadinsert` func...
it might make them simpler even
fiery cosmos
I liked try_insert
alright, i'll try implementing this this evening
it's running now without errors so i'll probably start a v2 version
haughty mountain
alright, i'll try implementing this this evening
good abstractions can simplify code a lot
fiery cosmos
running without errors != working, i know
fiery cosmos
good abstractions can simplify code a lot
hmm that's helpful to know
so write a try_insert function for my Bucket class.. any other tips / tricks
haughty mountain
try_insert will be very helpful in the hash table insert
you could probably imagine search having similarly good operations on the bucket
fiery cosmos
ok
weary gyro
You are given an array of strings arr. A string s is formed by the concatenation of a subsequence of arr that has unique characters.
Return the maximum possible length of s.
A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
``` Can anyone help me with this, I am thinking to use DP but I am not sure about the right approachthis feels like https://en.wikipedia.org/wiki/Exact_cover which is NP-complete
or similar at least
find biggest vs find a full cover
but they are the same problem is a full cover exists
so I doubt you'll find an efficient solution
hybrid epoch
Oof, like O(2^n) perhaps?
As an aside, it might be fun (or trivial) to think about if, using the exact cover definition, we could determine the compactness of a proper subset of a discrete space. I assume yes, since the subsets in this particular cover should be closed and bounded.. but.. idk. Fun to think about tho. Maybe.
hardy tapir
Could anyone explain how to approach this problem for me?
I don't understand when doing dfs, when I've found the optimal edge (solution)
haughty mountain
also is the idea that i will no longer need my `isopen` func
basically yes
fiery cosmos
i've gotten myself confused regarding how to mark the bucket pointers, but i think i can figure this out
haughty mountain
i've gotten myself confused regarding how to mark the bucket pointers, but i thi...
mark?
fiery cosmos
you might hash to bucket h,
if h has room you can insert
if h is full but tells ...
still referring back to this as a guide
not mark them but how and when to designate a given bucket.pointer. my logic is as follows: if i try_insert and fail due to finding no None in my loop, then the bucket is full, and i should save that bucket table location in p so that later, after I successfully insert, I can go back to the original bucket I had first tried (the one thats full), and assign its pointer to point at the bucket that ultimately got the key written to it.
haughty mountain
you don't need p for that part
fiery cosmos
oh right, i have h(key)
haughty mountain
you should already have a variable for the current bucket, no?
for when you're following links
fiery cosmos
there are no links yet
i'm just trying to get a chaininsert going, nowhere near like deletion or lookup just yet. just trying to build the table
oh
are you saying, if try_insert fails, go and pop from the stack and assign current bucket's pointer to that, because being on the stack, we know it will not fail try_insert
haughty mountain
there are no links yet
chaininsert needs links though
fiery cosmos
yeah i'll make the buckets point from one to another with a singly linked list via bucket.pointer
haughty mountain
currently you don't have logic for following the links though
fiery cosmos
i can save that for when i build a lookup function, unless i am misunderstanding
haughty mountain
describe what happens if you insert 3 things with the same hash (bucket size 1)
fiery cosmos
with chaining for collision resolution?
haughty mountain
yes
fiery cosmos
so the first one gets written directly to the bucket to which it hashes
the second one, i'll go there, do a try_insert, fail, pop a newbucket from my stack, go and write the second key to newbucket.keys. then i can write the original bucket pointer to newbucket, building a chain i can follow. i think what you're wanting me to find is that i need a bucket.pointer check during chaininsert itself
haughty mountain
you do indeed
fiery cosmos
yeah i'm having a bit of a chicken and egg logic problem
haughty mountain
and when adding a new bucket you can assign the index of the new bucket to pointer and then move to the new bucket
fiery cosmos
haven't used p yet i know
haughty mountain
let p be the current bucket location
fiery cosmos
hmm it'll have to go after the hash calc then
haughty mountain
technically yes
but not in the way you think
what should the initial value of p be?
haughty mountain
itself?
fiery cosmos
oh maybe None?
idk. you're talking about the variable p to update bucket.pointer yes
not the .pointer attribute itself
haughty mountain
you need to keep track of which bucket index you're working with
what's the first bucket index to look at?
fiery cosmos
self.table[hash]
fiery cosmos
so p = h
haughty mountain
well, you don't really need the h
fiery cosmos
where h = primary_hash(key, self.modulo_int)
haughty mountain
p = <the hash value>
fiery cosmos
hmm ok. i'm going to keep them separate for now but i see how p = h = hash value
fiery cosmos
it's just easy for me to see that and know i'm looking at the hashvalue
wait what
ok well yes i am populating the table with a for datum in data loop
ok if i can pull that out of the loop, i must be able to pull the hash out as well
bc i'm never rehashing for a given insert attempt
oh wow this was really inefficient huh
haughty mountain
actually. why are you taking datalen as an argument?
fiery cosmos
good ?
i guess in my head i was structuring it like the for loops of the other insert functions, but this one is fundamentally different
haughty mountain
actually. why are you taking datalen as an argument?
why is datalen relevant to anything?
fiery cosmos
do i not need a loop to follow all the possible pointers?
haughty mountain
why is datalen relevant for that?
fiery cosmos
idk i will remove
haughty mountain
shouldn't it just be the table size?
fiery cosmos
lms
so the problem statement sort of confuses me in this regard, it seemingly has conflicting statements about the size of the table
i guess for the bucket size 3 approach i'll just make the table length 40. but they say "There will be 120 table slots for all the schemes."
fiery cosmos
i'll make the loop run through tablesize
haughty mountain
so the idea of p is to have it be the current bucket you look at
the start point is based on the hash
if you have a full bucket with a link, what should happen to p?
fiery cosmos
update it to the current bucket location
fiery cosmos
are you saying, if `try_insert` fails, go and pop from the stack and assign curr...
this
still curious about this
haughty mountain
update it to the current bucket location
elaborate?
fiery cosmos
update p to the bucket.pointer from where try_insert failed
haughty mountain
are you saying, if `try_insert` fails, go and pop from the stack and assign curr...
and not quite, since this ignores links
haughty mountain
`update p to the bucket.pointer from where try_insert failed`
yes
fiery cosmos
yeah so i'm trying that and sort of caught in an infinite loop like in the case that self.table[p] itself has a pointer
which i can check with if self.table[p].pointer
haughty mountain
how is the loop infinite?
fiery cosmos
it's not infinite. i just need to find the proper checks to enable following each next pointer successfully
i feel like there is a recursive solution staring me in the face
where i call chaininsert again
haughty mountain
like, the logic in the loop should be fairly straightforward
haughty mountain
you might hash to bucket h,
if h has room you can insert
if h is full but tells ...
i.e. this
no need for a recursive call
fiery cosmos
ok good lol cause that'd get complex passing p and everything
haughty mountain
the idea is recursive though
fiery cosmos
for sure
haughty mountain
the loop is basically the recursion unfolded
fiery cosmos
can i ask a dumb question
nvm i think i know the answer
why is this not seeing a pointer at that location:
haughty mountain
it'll probably work still
also, why are you using h?
h is not relevant
the hash value only serves as the first bucket position
also, what's up with that if elif?
calling try_insert twice
fiery cosmos
h helps me visualize things. i could put in the primary hash call in for the index but i don't prefer to. the elif is because, there's going to (i think) be a third else clause in the logic. the way its written now, i call it again for visualization purpose so i can follow the steps
shoot i need a while loop huh
not seeing how to follow every bucket's pointer while they are all not None
i feel like i'm if elsing myself into oblivion rn
hmmm
i have an i running through tablesize
perhaps i can use self.table[i].pointer somehow
haughty mountain
`h` helps me visualize things. i could put in the primary hash call in for the i...
but h is the wrong thing
in anything after iteration 1
fiery cosmos
perhaps i can use `self.table[i].pointer` somehow
is this remotely in the right direction
i will drop h after checking the bucket and getting it's pointer
haughty mountain
is this remotely in the right direction
no
fiery cosmos
maybe a nextbucket variable?
haughty mountain
the loop is only there because you couldn't make more than tablesize steps
why do you need nextbucket?
fiery cosmos
the thing im struggling with is the syntax for "follow the pointer to the next bucket, and if it also has a pointer, follow that pointer to the next, and so on."
haughty mountain
you have p the current bucket
maybe think through a recursive formulation
not in code, but just on a a wordy description level
fiery cosmos
if table location at hash has a pointer, set p equal to pointer, call chaininsert on the key at table location p
haughty mountain
so I will stress again, don't use h/hash for the indexing
it only serves as the first value of p
fiery cosmos
oooh
i need like a table[pointer] type jaun
still unable to grasp how to continuously follow pointers 🤦♂️
its sort of painful how bad i am at this at times
other times, it feels easy
haughty mountain
still unable to grasp how to continuously follow pointers 🤦♂️
did you remove h yet?
fiery cosmos
yeah i just used p there
haughty mountain
so at the beginning of the loop p is always the current relevant node
so if you are updating p to follow the link in bucket p you are following the pointers
low robin
pls help
low robin
I suspect `emails` is empty
hmm
low robin
I suspect `emails` is empty
oh lol im stupid xD thx
fiery cosmos
the most highly sought after user in this server lol
azure osprey
the overlord
azure osprey
you need to if slot is not None
fiery cosmos
i want to insert there if i find that its currently None
keys is a list populated with None in each array location
hardy tapir
Could anyone explain how to approach this problem for me?
Anyone?
fiery cosmos
we're kind of all at the mercy of more talented coders lol
azure osprey
i want to insert there if i find that its currently None
def try_insert(self, key):
for idx, slot in enumerate(self.keys):
if slot is None:
self.keys[idx] = key
return True
return False
bleak burrow
hi
forest tundra
@vast adder I've managed a considerable improvement in my image finder
when we were talking it took 8.8 seconds to find 7 instances of the same object
forest tundra
used several tricks specific to my images
didn't use any library or anything
I'm filtering through the big image 8 pixels at a time because the game is that way
wrote my own comparison function to skip a bunch of unnecessary steps
and other stuff
the transparency thing is working aswell
i feel like that has to be the way
because if there's no patterns you can exploit you're basically forced to go pixel by pixel
vast adder
if you have time, could you provide some test code? would love to give this another try 😛
forest tundra
test code as in the code?
vast adder
test code as in the code?
a minimal reproducible example that sufficiently explain what you are trying to optimise!
forest tundra
https://paste.pythondiscord.com/uqazutayek this would be a basic version of the code
halcyon plankBOT
Hey @forest tundra!
fiery cosmos
hi all, need help with my hash table program
fiery cosmos
bruh why is argparser so difficult to understand
haughty mountain
why are you duplicating logic for the different hash functions?
the only difference is the primary_hash used
why not move that out and deduplicate the logic?
code duplication means editing stuff is more work, more error prone and more annoying
as a first step linearinsert can become
#
def linearinsert(self, key):
if self.hashtype == 'division':
primary_hash = primary_div_hash
elif self.hashtype == 'multiplication':
primary_hash = primary_mult_hash
for i in range(self.tablesize):
h = primary_hash(key, self.modulo_int)
j = ((h + i) % self.modulo_int)
if self.table[j].try_insert(key):
break
already the logic is deduplicated
now, why even do the hashtype check in the function?
we could do that outside the class and pass the hash function to the HashTable instead
fiery cosmos
boy am i glad you showed up
code is a mess rn
trying to write the main() bit with argparser
haughty mountain
and your function might just become
#
def linearinsert(self, key):
for i in range(self.tablesize):
h = self.primary_hash(key, self.modulo_int)
j = ((h + i) % self.modulo_int)
if self.table[j].try_insert(key):
break
i'm not used to setting variables to existing functions, i'll need to do somthing like
primary_hash = primary_div_hash() correct
ok i made the change to linearinsert
fiery cosmos
and your function might just become
```py
#
def linearinsert(self, key):
...
so with this i can call from main and not need another for datum in data loop?
haughty mountain
so with this i can call from `main` and not need another `for datum in data` loo...
wdym?
nothing change other than moving the if conditions for the hash type out
to dedupe code
fiery cosmos
while i was testing, i was testing with
for datum in data: mytable.linearinsert(datum)
haughty mountain
the thing I wrote doesn't change that
haughty mountain
my point is you have a lot of duplicated code
fiery cosmos
im with you
haughty mountain
which is annoying to maintain and edit
you should be able to also move the linear vs quadratic probing out, but that could come later
fiery cosmos
yeah there are a lot of different combinations of logic arising due to all the arguments im passing
haughty mountain
getting rid of the hashtype ifs already helps a bunch
btw, your repr isn't ok
it should be returning a string
fiery cosmos
return str(self.table)
haughty mountain
yeah, that works
your Bucket repr should probably be updated to include the pointer
that won't work, and why not format it in some nice way?
fiery cosmos
do you recall how they're asking for print statements
haughty mountain
e.g.
return f'Bucket(keys={self.keys}, pointer={self.pointer})'
i think the pointer will make that difficult
haughty mountain
how so?
fiery cosmos
they just want newlines with either 5 or 3 of the keys printed across so the format is nice for the grader. i guess i don't have to use the __repr__ and i can simply use the keys where necessary
haughty mountain
you can override __str__ if you want to
fiery cosmos
let's not overcomplicate things
what i don't understand rn is the main() logic
the main like for data in datum loop
when i try to write it its just duplicated logic like if collision_resolution = 'linear' type thing
haughty mountain
why are you opening a file before reading arguments?
aren't the file name you want among the args?
haughty mountain
the main like `for data in datum` loop
that's not in the main you posted
fiery cosmos
that's not in the main you posted <:pithink:652247559909277706>
i'm trying to write this loop into my main, since that was the driver of my test line
fiery cosmos
why are you opening a file before reading arguments?
idk, what should i be doing
haughty mountain
idk, what should i be doing
you're taking the input and output files as command line arguments, no?
currently you use neither
fiery cosmos
yes. alternatively i could write a defaultname_out.txt
alright i've changed input to be equal to args.input
haughty mountain
and the output?
fiery cosmos
taking out this line: print(args.accumulate(args.integers))
ah frick
missing a with open('output.txt') as output:
where should i put that
haughty mountain
and why the try?
fiery cosmos
🤷♂️
opal oriole
Move both prints to the same place and put the open right above. Opening should happen right before you do the printing, not long before.
haughty mountain
before when you need it :^)
fiery cosmos
Move both prints to the same place and put the open right above. Opening should ...
yeah thanks, i've done this.
i think the main thing i'm missing is a loop to write each datum into the table?
opal oriole
The idea is that you don't want to hold the file longer than needed.
fiery cosmos
right, no reason to keep a file open while you determine the input arguments won't work
opal oriole
Imagine you have a physical file on a clipboard and you want to eat lunch. You could either grab the clipboard, then eat lunch, then fill out the file. Or eat lunch, the grab the clipboard and fill it out. Someone else might want the clipboard and the first option would block them for a long time. It's not super relevant right now. But it also makes that part of the code feel like a complete thought / paragraph (one idea instead of multiple).
fiery cosmos
i see what you're saying. its about not tying up shared resources
opal oriole
It's easier to reason about non-interleaved things. And opening the file early is now something the reader needs to keep in the back of their mind the whole time even though it does not really come up until the end.
fiery cosmos
right of course
why is this not writing an output file:
running from command line with this argument:
oof
opal oriole
You can move the open closer to the prints.
haughty mountain
keep scopes as small as possible 🙂
haughty mountain
keep scopes as small as possible 🙂
(sadly python kinda makes that weird because of its variable scoping)
fiery cosmos
You can move the open closer to the prints.
ok im on it
hmm i need to implement some sort of collision counting i think for stats
just tested "my" hashing method (multiplication), appears to be working with linear probing
going to test with quadratic probing
appears to be working
is this chaining logic sound:
haughty mountain
fwiw, you can do what I suggested and move that if-elif out further
you can have it outside the class and pass a function to the class
err, why do you have multiple try_insert?
opal oriole
The function seems very strange to me in multiple ways is really all I can say, if it is trying to do what I think it is.
fiery cosmos
one case is to try there, next case is to check if there is a pointer
opal oriole
self.stack seems to be a resource that can be depleted, as it never gets anything pushed to it except at initialization, and it seems to be just a range.
haughty mountain
idk if your thing is correct, but you should only need one try_insert in the loop
opal oriole
for i in ..., yet i is never used.
haughty mountain
`self.stack` seems to be a resource that can be depleted, as it never gets anyth...
think of it as a free list
haughty mountain
yes
fiery cosmos
idk if your thing is correct, but you should only need one try_insert in the loo...
how can i confirm correctness
opal oriole
While failing to insert...
fiery cosmos
yeah that'd make more sense if i could figure that out
haughty mountain
the one nice thing about a for loop is if you fall through, insertion is impossible
fiery cosmos
but rather than optimize, i need to get the core functionality of this thing going
haughty mountain
but you can detect that in a while loop and a counter as well
fiery cosmos
like building the hashtable, writing it to an out, and doing their required print statement format
haughty mountain
for loop vs while with counter
opal oriole
Yeah in another language like C I would go for while count < ... and failed to insert.
Or well, in C, I can put the failed to insert in the for.
fiery cosmos
yeah thats like pseudocode
@haughty mountain just told me about the new walrus operator
which i suppose you could use in such a structure
eg declaring variables in a loop header
haughty mountain
how can i confirm correctness
write test cases where you validate that things are correct
fiery cosmos
like smaller input size and track the logic?
opal oriole
I think the main thing is the try to insert multiple times (in a single iteration) when we are looping for that.
haughty mountain
in any case, the logic in the loop is quite weird, I think I can easily construct a case that makes it fail
I think 4 elements hashing to the same thing breaks it
actually, it's more broken than that
you never assign any pointers
haughty mountain
do you actually have a mental model of what the thing should do?
ignoring the code
fiery cosmos
for chain insertion?
haughty mountain
do you actually have a mental model of what the thing should do?
if you do, walk through the code and see if the code actually does what you want it to do
haughty mountain
for chain insertion?
yes
fiery cosmos
ok
haughty mountain
I asked yesterday, what is the behavior when you insert 3 elements with the same hash?
This simple sequence of operation will actually cover most logic
haughty mountain
yeah, sure
fiery cosmos
i think i am missing updating the original collision location table[p].pointer
upon successful insertion
haughty mountain
why would you update any pointer on successful insertion?
that's not the operation that means you need to update a pointer
fiery cosmos
is it like, if bucket == full, update bucket.pointer to point at the very next bucket?
haughty mountain
no
fiery cosmos
if bucket == full, update it's pointer to be the free bucket popped from the stack
haughty mountain
you might hash to bucket h,
if h has room you can insert
if h is full but tells ...
and for the logic in the loop, it all comes back to
haughty mountain
if bucket == full, update it's pointer to be the free bucket popped from the sta...
correct pointer update, wrong logic
fiery cosmos
if try_insert fails, update bucket[p].pointer = free bucket location popped from stack
haughty mountain
if try_insert fails, update bucket[p].pointer = free bucket location popped from...
still wrong
go back to my old statement I replied to earlier
re-think things...
you only need 1 try_insert
what you have is way overcomplicating it
fiery cosmos
hmm ok
haughty mountain
and yeah, I can trivially break that code, two elements with the same hash breaks that code
fiery cosmos
i'm studying this:
you might hash to bucket h
a. if h has room you can insert
b. if h is full but tells you that it's linked to bucket h', you'll need to check there
c. if h is full and not linked to anything...
i could see how if there was a full flag, i wouldn't need try_insert more than once
maybe, a pointer existing indicates it is full
haughty mountain
try_insert already tells you
what does try_insert respond if the bucket is full?
fiery cosmos
False
haughty mountain
cool, so you have that info
a. is your if ... break
that part is fine
(though I would make it a return)
opal oriole
A bucket has two parts to it. One is being full or not...
haughty mountain
so you have b and c left
fiery cosmos
i don't see how i can do it without using try_insert again
haughty mountain
why do you need try_insert again?
haughty mountain
let the "recursion" deal with that
a. not working means you need to find another bucket to put things in
there are two possibilities
b and c
haughty mountain
no, doing it with a break/return if true is fine
haughty mountain
a. not working means you need to find another bucket to put things in
to be blunt the rest of the loop logic is just about "find another bucket"
no insertion in the rest of the loop
close?
there you go, though you want an is not None for the pointer check
fiery cosmos
what about the chaining?
haughty mountain
there you go, though you want an `is not None` for the pointer check
(because 0 can be a valid pointer)
haughty mountain
what about the chaining?
what about it?
fiery cosmos
you said i wasn't doing it before, does this remedy that?
haughty mountain
think through the scenario of inserting 3 elements with the same hash
walk through the code in your head
opal oriole
Draw it.
haughty mountain
drawing/writing down how the table changes over time is helpful, yes
fiery cosmos
yeah no it makes sense. during the second insert, the initial if fails, we therefore continue to the elif. if the bucket we tried to insert in has a pointer (is not none), p is reassigned and we go back to the beginning of the loop, and try a new insertion with our new p value (the collision bucket's pointer location). if we fail an insert, and the collision bucket's pointer is None, we go and select a new location from the free stack
haughty mountain
right
fiery cosmos
i mean, it makes sense that we're following a chain, idk about updating pointers
fiery cosmos
that's what i was on about
opal oriole
Well you have to set it at some point in the loop.
And you have 3 cases.
Would you do it in the first?
fiery cosmos
should that be a part of the insert functions or bucket defs
fiery cosmos
i think i am missing updating the original collision location `table[p].pointer`
this
fiery cosmos
upon successful insertion
here
haughty mountain
if try_insert fails, update bucket[p].pointer = free bucket location popped from...
ah, here
your overall logic was wrong then, but...
opal oriole
In your loop's 3 cases you can use process of elimination. Where should you NOT update the pointers?
fiery cosmos
i need to remember where something has a collision, so i can update that buckets pointer to point at the bucket where i finally successfully insert
fiery cosmos
In your loop's 3 cases you can use process of elimination. Where should you NOT ...
let me look
haughty mountain
i need to remember where something has a collision, so i can update that buckets...
you don't need to remember anything
fiery cosmos
by the way, this'd be a great time to implement the required collision counters
fiery cosmos
In your loop's 3 cases you can use process of elimination. Where should you NOT ...
definitely not case 1
haughty mountain
if you're following a pointer, do you need to update that pointer?
fiery cosmos
no
opal oriole
If it's not None, do I want to change it?
fiery cosmos
no
haughty mountain
lol, same case as I asked about yes
opal oriole
Two eliminated, only 3 options...
haughty mountain
almost
haughty mountain
right
fiery cosmos
got it
how can i track collisions? btw that has to be for all collision strategies, so this function likely isn't the place for it
haughty mountain
you could technically do this I think, but it's not exactly obvious
p = self.table[p].pointer = self.stack.pop()
oh i see why
i thought you meant simply bc it was a double assignment. but i've got you
btw i ran this and i think there is something wrong, im also printing a count which counts my None's in my out, and i'm getting 92 when it should be 60. so i am failing to insert some elements
let me see if it works with the division hash
haughty mountain
the hash shouldn't matter
fiery cosmos
something is off there as well
haughty mountain
I would recommend throwing an exception after the loop
you should never get there
but as written your code would just silently fail if it does
fiery cosmos
like raise Exception
haughty mountain
raise Exception('message') yeah
fiery cosmos
like same indentation as the for
haughty mountain
it shouldn't happen, but you will want to know if it does
fiery cosmos
correct
haughty mountain
after the for
haughty mountain
after the for, not in it