Today your goal is to shuffle the first 1018 integers ({0, 1, ..., 1018-1}).
A shuffle function takes a seed, and returns one of the permutations of the array, uniformly chosen from the possible permutations, based on the seed. E.g., if were to shuffle the first 5 integers, these might be 5 poss...
@Maltysen I mean, I feel it's pretty strongly implied from the title and "However, 10^18 numbers is way too big to hold in memory, and shuffling all those numbers would take way too long."
@orlp but then, "As 1018 is way too big to test, your answer must include some explanation as to why your algorithm works. It is preferred if you also include a non-golfed implementation with a tweakable limit (e.g. 100 instead of 1018) that can be examined & tested."
reservoir sampling is not the solution to this problem
@Maltysen A very important ingredient that the solution I made uses is a PRF, a pseudo-random oracle. Given some inputs it always returns the same, random, answer - think like a hash.
@orlp I actually had that problem about unique ids. I ended up using the time, base-converting it and using only the least few significant digits. I wish I knew about this back then :P
Replace magic numbers
Tags: code-gold string
Introduction
Magic numbers are a common problem in software development, since they tend to make software hard to maintain. Best practise is to use named constants instead of raw numbers in the source code. In this challenge you have to clean up som...
@Downgoat It depends on the implementation. In Python, .pop() is O(1) while .pop(0) is O(n), but with collections.deque, you get .popleft() which is also O(1).
This is a chess-KOTH with simplified rules (because chess itself is already complicated, playing it via a simple program doesn't make it easier). At the moment it is limited to java (version 8), but creating a wrapper-class isn't that difficult (in case someone wants to do this).
Chessboard
The...
The barrier for entry for new users to write challenges is too high. I think there's a problem with how we are closing challenges. There are only two reasons we can close a challenge as "off-topic":
This site is for programming contests and challenges. General programming questions are off-topi...
Given a list of integers, output the number of permutations of the integers, with indistinguishable permutations counted once. If there are n integers, and each group of indistinguishable numbers has length n_i, this is n! / (n_1! * n_2! * ...)
Rules
Input will be some form of list as argument...
@Maltysen SO is currently developing the XYX problem. This happens when answers try so hard to find Y that they ignore the possibility that the question is really about X.
Let's say I have an array A with n unique elements on the range [0, n). In other words, I have a permutation of the integers [0, n).
Is possible to transform A into B using O(1) extra space (AKA in-place) such that B[A[i]] = i?
For example:
A B
[3, 1, 0, 2, 4] -> [2, 1,...
@flawr Yeah, that's what I was thinking. Say something like but more eloquent than "The popcon description sucks here's some related posts how should we make it better pls suggest text"
I'm Stéphane, a senior product designer at Stack Exchange. First, I wanted to announce that this site is now starting the process of moving out of beta to become a fully-graduated site!
Congratulations!
Graduation and Your Site Design
Graduation comes with a few perks, which should come out...
@Downgoat That part of the graduation process hasn't happened yet. "I wanted to announce that this site is now starting the process of moving out of beta" I guess means that the process has started but not much has happened yet.
@Maltysen ok fixed the scoreboard thing. I also worked out the alien movement equations Just y =mx+b but with the weird default coordinate system that took some time. Plus aliens are coming in from the right -> left so it was weird.
@El'endiaStarman I believe that the way it works is that repr is by default the class, name, and memory location and __str__ default is just calling __repr__
Replace magic numbers
Tags: code-gold string
Introduction
Magic numbers are a common problem in software development, since they tend to make software hard to maintain. Best practise is to use named constants instead of raw numbers in the source code. In this challenge you have to clean up som...
The barrier for entry for new users to write challenges is too high. I think there's a problem with how we are closing challenges. There are only two reasons we can close a challenge as "off-topic":
This site is for programming contests and challenges. General programming questions are off-topi...
Given a list of integers, output the number of permutations of the integers, with indistinguishable permutations counted once. If there are n integers, and each group of indistinguishable numbers has length n_i, this is n! / (n_1! * n_2! * ...)
Rules
Input will be some form of list as argument...
I'm Stéphane, a senior product designer at Stack Exchange. First, I wanted to announce that this site is now starting the process of moving out of beta to become a fully-graduated site!
Congratulations!
Graduation and Your Site Design
Graduation comes with a few perks, which should come out...
