Primes and Squares

« first day (982 days earlier) ← previous day next day → last day (242 days later) »

Nathan Merrill

01:56

In gift rotations, people are assigned a recipient they are to purchase a gift for. There are usually a couple of restrictions you see:

1. You don't get assigned yourself
2. You don't get assigned the person you were assigned last year.

However, let's take rule #2 to the extreme: You are never assigned to a person you've ever been assigned to before

Obvious, with such a rule, this can only last so long. So my question is: Given a party of size N, and assuming random assignments, how many times can you do a gift rotation (on average)?

Sriotchilism O'Zaic

N-1 years

Nathan Merrill

that's the ideal solution. This is assuming random assignments.

Sriotchilism O'Zaic

I don't think the on average changes anything, it always goes N-1 years

Nathan Merrill

Hmm...I should define random: Each possible assignment set is equally likely

Sriotchilism O'Zaic

Including invalid ones?

Nathan Merrill

02:01

oh! I forgot the last rule!

You need a complete cycle

It's not allowed for A -> B and B -> A

Sriotchilism O'Zaic

You need a complete cycle or exactly one complete cycle?

Nathan Merrill

Each assignment set has to be a complete cycle of the entire party

Sriotchilism O'Zaic

This sounds like a number crunching problem.

Nathan Merrill

sure, you could get actually percentages. I have a script that runs the algorithm above, so getting actual numbers wouldn't be hard

I'm looking for an equation. Maybe that's a bit hard

Sriotchilism O'Zaic

I don't think it is very hard.

Nathan Merrill

02:04

Oh, actually, it doesn't do random properly. It might be a bit biased on its randomness

Sriotchilism O'Zaic

All the difficulty seems to step from arithmetic.

Nathan Merrill

If you don't think it's hard, I'd love to see a proof :)

Sriotchilism O'Zaic

It does seem very number crunchy though.

Nathan Merrill

1 => 0
2 => 1
3 => 2
4 => 2

El'endia Starman

02:47

I.e. for N=3 it's (1, 2, 3) and (1, 3, 2), and for N=4 it's (1, 2, 3, 4) and (1, 4, 3, 2)?

Nathan Merrill

correct

I started down the path of N=5, and it gets complicated fast to do by hand

some paths are longer than others

12345, 13254, 14352 is one path, while 12345, 13524, 14253, 154321 is another

El'endia Starman

03:03

I think it'd be easier and more interesting to simply count the number of possible paths.

(I must say, this is a very welcome distraction from the modship fiasco blowing up all over SE.)

This initially reminded me of derangements, where a shuffle leaves no element in its original position. But that's not quite what's relevant here; what's important is that a cycle never has two adjacent elements remain adjacent after a shuffle.

Every shuffle must be one of these particular transforms, and the additional condition is that any given cycle must not repeat adjacency pairs from previous cycles.

Nathan Merrill

@El'endiaStarman sure, I can go along with that.

El'endia Starman

Ooooh wait, these are directed adjacency pairs.

Still, the logic still applies.

1 hour later…

El'endia Starman

04:33

Great breakdown of the fracas leading to the impeachment inquiry of Trump:

Ukraine Whistleblower, Transcript, Complaint & Impeachment -- Real Law Review

►

4 hours later…

flawr

08:55

@xnor I've seen more or less this example of an example in ML where the model fits the data with arbitrary accuracy, but does not generalize in any way.

flawr

09:23

I think I've only ever yeen it with y = +- 1

@El'endiaStarman yes, it is unfortunate

3 hours later…

flawr

11:58

@xnor Are you actually work on an implementation? :)

xnor

12:12

@flawr No, I usually wait to do my golfing in other people's comment sections :-)

And the challenge was edited to kill my sin-overfitting idea in any case

3 hours later…

flawr

14:52

@xnor maybe there is some number with a low score?:)

I thought about projecting the points onto a line (finding some nice scalar product) and then maybe use a fourier series

that would at least be easy to compute

2 hours later…

Nathan Merrill

16:30

Ok, there are several options I think are reasonable: Matrix, Discord, Telegram, Gitter.

I like Matrix the best. That said, Matrix can integrate with any of the other 3 options I listed, so I can be swayed.

That said, I'm not going to move yet. But I've already seen other communities broken up, and regrouping is tough because you don't know where others are heading.

Which is why I'm discussing this now

2 hours later…

flawr

18:15

What about ICR?

Nathan Merrill

you mean IRC? IRC has a couple of things I hate: No history, no formatting. Both of those have workarounds. One of those workarounds is Matrix, so I'd be using IRC through Matrix, but I'd still hate to force IRC on everybody else

flawr

oops, yes, this one:)

ah I see, yes history is a must

1 hour later…

El'endia Starman

19:26

@NathanMerrill I use Discord somewhat but never heard of the others.

Nathan Merrill

Matrix and Telegram are privacy focused. I like Matrix because it also works with others.
Discord is the most popular.
Gitter is Github-focused, which feels adjacent to our room's many topics

1 hour later…

flawr

20:36