« first day (4081 days earlier)      last day (868 days later) » 

3:10 AM
Hi! Was discussing python elsewhere and the topic came up where the order of operations for a, b = b, a in python can screw things up where if you write while reading the same variables
such as a, L[a] = L[a], a (notice where a is used in both assignment and reading it to use as index)
 
 
2 hours later…
5:37 AM
@Unihedron That's because the Python VM is a stack machine. It performs the swap by rotating the top 2 items on the stack.
    from dis import dis
    dis('a, L[a] = L[a], a')

      1           0 LOAD_NAME                0 (L)
                  2 LOAD_NAME                1 (a)
                  4 BINARY_SUBSCR
                  6 LOAD_NAME                1 (a)
                  8 ROT_TWO
                 10 STORE_NAME               1 (a)
                 12 LOAD_NAME                0 (L)
                 14 LOAD_NAME                1 (a)
                 16 STORE_SUBSCR
                 18 LOAD_CONST               0 (None)
 
Avv
Hello @PM2Ring.
How are you?
 
Hi, Avra. I'm ok. I'm actually on my computer right now. I'm usually using my phone these days.
 
Avv
Great. Have a nice holiday
 
I haven't seen you in the Maths chat for a little while...
 
Avv
Hopfully you enjoy holidays
I am afraind of Prof Ted
hahaha
 
5:39 AM
Well, we still have Covid restrictions here. I don't think I'll be seeing any of my family over Christmas.
 
Avv
Wow!
In the US, it's almost open, but people are now afraid of new COVID wave!
But still it's almost open
Most people got vaccines here
Hopefully you all be safe and see each other
Just want to say hi :)
 
Prof Ted's actually a very kind guy. But he doesn't want you to waste your time doing a course that you aren't prepared for. And he doesn't like it when people are disorganized and unclear when they ask questions in the chat.
 
Avv
thank you Prof Ring. Again, happy new year. Good night
 
Goodnight, Avra.
 
 
2 hours later…
7:48 AM
I'm trying pattern search on str data
if data is less (i.e. 20-40 records), code is executing within a seconds
if data is huge like 2000+ records its taking 2hrs+ to produce the result

Is there any better way to write this code ???
```
ss = '''
A B
B C
C D
D E
E F
C I
'''.strip()

lst = []
for r in ss.split('\n'):
    lst.append(r.split())

################

paths = []
for e in lst:
    # each row in source data
    pnew = []  # new path
    for p in paths:
        if e[0] in p:  # if start in existing path
 
8:23 AM
just curious, did you make that solution on your own?
if so, nicely done!
So i'd suggest switching to networkx, essentially, a graph datastructure will be much more suited to this kind of task. The issue with your code as is, is that it's time complexity is too high. each for loop is an O(n) operation, so when you nest it, it's O(n^2). Then, in search in a list is O(n), same thing with .index
So unless ive missed something, your code is O(n^3). essentially, each doubling of the list causes a 8 times growth in time (cubed growth)
Generally, you speed things like this up by using datastructures that are more suited to lookups, such as sets or dictionaries, when appropriate. A "graph" datastructure such as one provided by networkx is also really excellent for handling edges and connections efficiently by just storing that information as and when a node is created
So again, if you wish to learn, you could actually explore how graph datastructures work and try to make a simplified version of it on your own
Or if you just want results, go networkx
 
@assassinezio You may be able to speed things up a little. Your inner loop searches for e[0] in p 3 times, and each time it has to scan the whole p list looking for a match. Also, it's more efficient if you don't lookup e[0] 3 times.
I agree with @ParitoshSingh that you probably should be using a different data structure for this, eg a trie.
But anyway, here are a few minor optimizations to your existing code.
ss = '''\
A B
B C
C D
D E
E F
C I
'''

lst = [r.split() for r in ss.splitlines()]
paths = []
for e, f in lst:
    pnew = []
    for p in paths:
        try:
            idx = p.index(e)
        except ValueError:
            continue
        if idx == len(p)-1:
            p.append(f)
        else:
            pnew.append(p[:idx+1]+[f])
    else:
        paths.append([e, f])
    if pnew:
        paths.extend(pnew)

print(*[' -> '.join(e) for e in paths], sep='\n')
I just noticed that our code prints "C -> I" twice. You probably don't want that...
 
oh good spot, that must be a bug in the logic somewhere
 
8:52 AM
@Kevin If your players are using a 64 byte crypto hash like SHA-512 or Blake2b, a birthday attack is going to take a long time. ;) With a small block size, you can speed the process up by saving all the hashes to see if you get any matches, but that doesn't help much when you need to generate 2**256 hashes to get a single collision with probability ~50%.
I recommend Blake2b because it makes it convenient to supply a hash key
(upto 64 bytes). You can give it a salt too (upto 16 bytes), if you
like. Here's one way to do it.
Each player generates (as bytes strings) their secret data, a 64 byte
key, and a 16 byte salt. It's probably best to use a crypto RNG to make
the key & salt. They then publish their salts and combine the salts by
XORing the bytes together, `salt = salt_alice ^ salt_bob` Each then
calculates the hash, `h = hash(data, key, salt)`, and publishes it.
Here's a little demo:
Changing a single bit in the data, key, or salt should flip 256 ± 16 bits of the hash.
 
@PM2Ring Thank you for the optimization
@ParitoshSingh 👍 Okay .... thank you for the Info...
 
@assassinezio This doesn't do exactly what you want, but here's my take
 
9:11 AM
@Aran-Fey Thank you πŸ‘πŸ‘πŸ‘
 
 
7 hours later…
4:34 PM
In relation to this question: stackoverflow.com/q/70404616/5431791, which I am not going to answer, I was just playing around with it, I tried this:
from random import choice, seed as setseed
from string import ascii_uppercase as uppercase
from string import ascii_lowercase as lowercase
from string import digits

PATTERN = [uppercase, digits, uppercase, digits, uppercase, digits, lowercase]

def random_product(*args):
    "Random selection from itertools.product(*args, **kwds)"
    pools = [tuple(pool) for pool in args]
    setseed(0)
    while True:
        val = ''.join(map(choice, pools))
        setseed(val)
        yield val


random_strings = random_product(*PATTERN)
My question is, does setting different random.seed guarantee different patterns?
 
"guarantee" is a bit strong, but for practical conditions yes, it does.
but random will change its internal state on every call anyways, so there isn't really a point to this.
Note that random uses a PRNG by default. That means for the same input and seed, it will produce the same sequence of outputs. So feeding the result of a random call back as the random seed will just select a different but still deterministic sequence.
 
"but random will change its internal state on every call anyways, so there isn't really a point to this."
So, IIUC, different calls to random.choice will be more or less equally random as setting different seeds in-between?
Yes, I am not concerned about determinism.
 
I would assume that not setting the seed gives you "better" randomness, yes.
Python's default PRNG has 2**19937-1 states. Your choice (and thus seed) from the pools has less than 2**29 states.
 
4:53 PM
That helps. Thanks 😊
 
5:10 PM
TIL * is and and + is or (condition keywords golfing)
 
more like True is 1 and False is 0
 
5:51 PM
@PM2Ring Oh good. Birthday attacks were the one category I was most worried about. Thanks for doing the math :-)
@12944qwerty If your goal is to reduce character count, consider also the bitwise operators & and |
It's not really Pythonic to use them on booleans in regular code, but anything goes in code golf challenges
 
@SayandipDutta depending on your use - you might also want to look at docs.python.org/3/library/secrets.html#module-secrets
 
@Kevin It's a fun little problem. If you had a billion computers, each generating a billion 512 bit hashes per second, you can expect a collision with probability 50% in around 10**52 years (using 1 billion ~= 2**32).
A related problem is Shamir's Secret Sharing
 
6:06 PM
or just for some very, very weird reason, get extremely (as in expletively lucky) - happen to find something on your first try
I remember about 20 years ago... the network admin I was working for was doing a security thingy... mine was the only password it didn't break within 2 minutes...
was it lopht crack? Something like that seems to ring a bell...
 
I've heard about Shamir's Secret Sharing, but I don't know its inner workings. I admire it just for enabling a kind of secrecy that I didn't know existed
 
think it worked on the fact that NT broke passwords into two separate MD5's or something really weird that made it much easier to break
 
@SayandipDutta What My Miyagi said. Reseeding the randomizer inside the loop makes the randomness worse. I'd remove the seeding from the function entirely. Let the caller call seteed before they call random_product. BTW, choice doesn't need tuples, it works on strings too.
from itertools import islice

def random_product(*pools):
    while True:
        yield ''.join(map(choice, pools))

setseed(0)
random_strings = random_product(*PATTERN)
print(*islice(random_strings, 5), sep='\n')
 
A lot of the crypto tech I read about boils down to "a box that you can't open unless you have the key" but SSS is like a magic key that works even if 3/7ths of it is missing
 
Yeah, it's pretty neat.
 
6:12 PM
Sounds like something you could get at a wizard's garage sale
 
Oh the tuple thing is because I was feeling lazy and and copied the random_product function from the itertools recipe section ;)
 
Fair enough. :)
 
When random.seed is called with no arguments, it uses the system time to seed the RNG. I wonder if this is also the case if you don't call random.seed at all.
 
@Kevin Not quite. It only uses system time if the system doesn't provide an entropy pool, which is pretty unlikely, unless it's a tiny embedded system.
But yes, not calling seed is equivalent to seed(None)
 
There's os.urandom(...) but that's a different beast altogether
 
6:20 PM
Tsk, the documentation authors should have known that I would parse sentences left-to-right, and discard the rest of the buffer once I found a complete segment of information.
In other words, Put the if condition at the beginning next time, dear authors
 
BTW, Numpy has upgraded to a better default randomizer than Mersenne Twister. The new one, PCG64 is faster, simpler, and has better randomness, although the difference in randomness is only significant if you need lots of random numbers, eg a big Monte Carlo sim. See numpy.org/doc/stable/reference/random/… & pcg-random.org
@JonClements It's easier to just use random.SystemRandom
 
Based on the documentation of random.seed without arguments, does it mean, the only usecase for random.seed() is when you want to ensure irreproducibility in certain section of code, after some operations with a specific seed?
 
When you want to ensure reproducibility, so the opposite
 
Well, that's one use case. :) I can't think of any others, off the top of my head. OTOH, "Explicit is better than implicit", so I almost always have a seed(myseed) call in any of my code that uses the standard random number generator.
 
6:33 PM
In which case, I'm confused. I set a seed when I want reproducible examples based on randomness e.g. a heuristic search algorithm that swaps jobs
 
@roganjosh He's asking about seed() with no args.
 
Ah, sorry. That's my fault for jumping in
 
So in Sayandip's scenario, the 1st section of code uses a fixed seed to generate a reproducible sequence, then the 2nd section uses seed(None) to get an irreproducible sequence.
One feature of the random module that doesn't get used much is that it allows you to have multiple independent streams of random numbers. From the docs:
The functions supplied by this module are actually bound methods of a hidden instance of the random.Random class. You can instantiate your own instances of Random to get generators that don’t share state.
Eg, if you're making random shapes, at random locations, with random colours, you could have 3 different streams, so you can eg change the colours without affecting the shapes or locations.
 
6:50 PM
Neat! I definitely didn't take much heed of that sentence when I originally read the docs
 
7:38 PM
@Kevin but those check the binary... it won't always be right then right?
 
@12944qwerty If you use the bitwise operators & and | on values of False and True, you'll just get False and True in the results. Try this:
print(False | True)
Another interesting one is:
print(False ^ True)
 
7:56 PM
It's true that * is more flexible than & though. * works with any pair of numbers, unlike & which requires them to be ints and share at least 1 bit.
 
True. The bitwise operators real strength is when you're using them to operate on all the bits in each arg, in parallel.
 
 
1 hour later…
9:17 PM
hm
 

« first day (4081 days earlier)      last day (868 days later) »