Reset makes no sense...


  • 3

    I don't get the point of reset. Does anyone? Nobody is going to actually shuffle the given original if "reset" needs to be supported. But then there's nothing to reset.


  • 3

    @StefanPochmann The reason I designed it that way is to increase the likelihood that when shuffle is called it is shuffling based on the original array, not the previously shuffled array. This will increase the chance of detecting bugs in the main algorithm in shuffle.


  • 0

    @StefanPochmann Yes, for algorithm I don't think this reset() is necessary. Perhaps that's just a conventional function for a shuffle machine :)


  • 0

    @1337c0d3r Ah, ok, that does make sense.


  • 0
    O

    @1337c0d3r @StefanPochmann
    Just my feeling about the problem description.

    The problem clearly specifies "Shuffle the array" and "Resets the array back to its original configuration", so I thought the OJ will actually check the original array itself, and the class is supposed to be a wrapper of the input array.

    But it is not. It only checks the return value of the functions, and that makes it really bizarre to me because even if you don't "Resets the array back to its original configuration" at all, you can still get AC.


  • 0

    @1337c0d3r said in Reset makes no sense...:

    @StefanPochmann The reason I designed it that way is to increase the likelihood that when shuffle is called it is shuffling based on the original array, not the previously shuffled array. This will increase the chance of detecting bugs in the main algorithm in shuffle.

    I am pretty much always generating a new sequence from a previously shuffled array. When reset is called I simple return a copy of the original array that I've kept stored. Since all shuffles need to be random and with equal probability, resetting the array would hold no meaning.


  • 0

    @babhishek21 @1337c0d3r

    I do this as well. It's faster than creating a new array every time I shuffle(), as some others solutions are doing. I don't see the point of reset() either since the problem says "each permutation must be equally likely to be returned - AKA, perfect shuffle. It doesn't matter whether you shuffle the original array or an already shuffled permutation.


  • 0

    @babhishek21 @DeusVult

    Not sure whether you didn't understand what @1337c0d3r said, but here's a demonstration. This code gets Accepted even though it's obviously bad because there's no randomness whatsoever:

    class Solution {
        vector<int> nums, original;
    public:
        Solution(vector<int> nums) : nums(nums), original(nums) {}
        
        vector<int> reset() {
            return original;
        }
        
        vector<int> shuffle() {
            next_permutation(nums.begin(), nums.end());
            return nums;
        }
    };
    

    But if I do what I'm told, then the judge does detect the bad shuffling and I get Wrong Answer:

    class Solution {
        vector<int> nums, original;
    public:
        Solution(vector<int> nums) : nums(nums), original(nums) {}
        
        vector<int> reset() {
            nums = original;
            return nums;
        }
        
        vector<int> shuffle() {
            next_permutation(nums.begin(), nums.end());
            return nums;
        }
    };
    

    And that is good, because then I'm aware that I did something wrong.

    That's of course an extreme example, where I intentionally used a bad shuffle to make it obvious. But I've already seen someone's wrong solution they probably thought was correct, where the wrongness wasn't detected by the judge only because they didn't reset properly as told.

    In other words, yes, if the shuffle is correct, then it doesn't really matter, but if it isn't, then properly resetting helps pointing out bugs.


  • 0
    O

    @StefanPochmann I agree, and I was adding the point that it makes even more sense if the OJ checks the correctness of reset as well. It's not very helpful if people can get around reset that easily (as shown in many posted solutions) without actually resetting anything.


  • 0

    @StefanPochmann

    Interesting, thanks!

    Is that why most solutions take hundreds of ms? Is the judge running the shuffle() millions of times, categorizing output, and seeing whether there's a trend of one permutation appearing more often than another? That explains a lot...


  • 0

    @o_sharp What would a really proper C++ solution look like, though? I suspect it would get a little ugly and distract from the actual task.


  • 0

    @StefanPochmann said in Reset makes no sense...:

    In other words, yes, if the shuffle is correct, then it doesn't really matter, but if it isn't, then properly resetting helps pointing out bugs.

    Agreed. Funnily enough I tried the following on a 3 element sequence:

    shuffle
    reset
    shuffle
    reset
    shuffle
    

    Both times I used the inbuilt C++ random_shuffle. One time I properly reset my array. The other time, I simply returned a copy of the original array without actually resetting anything.

    In the first case (proper reset), the sequence returned by shuffle was always the same! In the second case (no actual reset), I got different results (which is expected and desirable.)

    I repeated the experiment with 5 element arrays and the results were much more desirable. I don't know if it was chance, or because I left the random seed to be determined by the standard implementation. The judge accepted both solutions.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.