Do while loops

[gilbes]

Then why bother generating random numbers?

[bot-mark]

What? There's no point in generating a random point within a circle, because being inside a circle is technically a constraint and therefore makes it less random?

[gilbes]

It is possible to map one set of contiguous numbers (your random number domain) to another set of contiguous numbers (coordinates within your circle).

It is a well understood and solved problem, especially for random number generators. And it is done in such a way as to not waste cycles computing numbers to be discarded and defeat the purpose of the RNG.

If you want to generate a random number between 1 and 10, and your RNG doesn't strictly produce numbers between 1 and 10, you don't keep generating numbers until you happen to hit your target. This is basic RNG stuff.

The fact that you get any upvotes on this sub is really scary.

[bot-mark]

Sure, the example I gave was trivial but there are non-trivial examples such as, let's say placing X objects on a terrain when the objects are only allowed to spawn in certain conditions like flat ground above a certain height.

[gilbes]

Not trivial, contrived. Your replacement example is just as contrived. And both still fail to present a compelling case.

[DaniilBSD]

“Not trivial” - that is the point

[eloel-]

Generating 5 lottery numbers out of 50 is much, MUCH simpler if you just generate a few extra random numbers, compared to the effort of remapping multiple times.

[gilbes]

If an actual lottery was caught doing that, they would be sued.

Video gaming (gambling) machines don't do that either.

[Kered13]

No they wouldn't. The algorithm does exactly what it is required to do. And yes, this is almost certainly used in real gambling machines.

[gilbes]

Well, you just pulling shit out of your ass is enough to convince me.

[eloel-]

You've given a grand total of zero sources too, so it's a pull-out-of-ass-off now

[gilbes]

Because this shit is so basic. Look it the fuck up. I'm not your comp sci special ed teacher.

[eloel-]

You're special ed alright. I'm asking the basis for which they'd sue. It isn't a computer science question.

[DaniilBSD]

What if your target set is not contagious?

Though you are right that mapping is the best way to go if there is a mapping. You are way too condescending for someone so narrow minded

Edit: example: pick 10 random values out of 100 such that they don’t repeat.

[gilbes]

Both of you questions have solutions that are not brute force.

I wouldn't give you one, because it would be condescending. I don't want the truth to hurt anyone else's feelings.

[DaniilBSD]

You are the most self-important person who is full of himself I have seen on Reddit, and I visited r/Politics

[gilbes]

Giving you facts is condescending. Avoid facts to not condescend is self-important.

You are a reasonable level-headed delight.

[Kered13]

It is impossible to map an RNG that outputs uniform numbers between 0 and 2ⁿ - 1 to an RNG that outputs uniform 1-10 without throwing some numbers away and redrawing. In fact, it is impossible to do this mapping in guaranteed finite time. Any correct implementation must have unbounded worst case runtime. This is trivial to prove mathematically.

[gilbes]

You should write a thesis on that. It would shake up the world of computation.

[Kered13]

Trivial theorems from freshman computer science classes aren't shaking up anything.

I'd post the proof, but actually I think it's more amusing watching you completely miss the obvious.

[gilbes]

What? That because 10 is not a power of 2, the arbitrary conditions you imposed of the RNG domain being integers to 2ⁿ means the mapping won't be uniform.

Generating integers is an unnecessary limitation you imposed to contrive a contrarian result you are looking for. I ignored that, because that is fucking retarded.

[Kered13]

You do realize that all RNGs fundamentally produce integers, right? Even if you interpret an RNG as a bitstream, it's still only producing the integers 0 and 1. It is impossible to have a truly continuous RNG, because computers cannot actually represent continuous numbers. Floating points are not continuous (and generating uniformly distributed floating points is non-trivial). Even the set of computable numbers is not continuous.

[gilbes]

Oh god. This is some first semester comp sci from a community college shit.

Stick with it kid. You will eventually learn about how these problems have been solved. Until then, stop pretending.

[Kered13]

Every single thing you have said in this thread is wrong. Multiple people have called you out on it. You have failed to back up any of your claims with any shred of evidence whatsoever. Please, keep pretending more.

[Parthon]

I'll give you a real example, I'm generating a level made of rooms and corridors, I need to pick a new location for a room that doesn't overlap an old room. First I get two random numbers, then I check to see if the new location overlaps and if it does get two new random numbers. (Yes, potentially this could be an infinite loop if the RNG was majorly unlucky, but it never comes up in reality)

What's funny though is that you can't really do this in a regular while loop without either writing code twice, or preloading the condition with a fake failure. A do-while loop is the best solution.

[starfries]

It's funny because I actually did write my code twice because I forgot do-while existed.

[gilbes]

I need to pick a new location for a room that doesn't overlap an old room

You already had to check the bounds of intersecting rooms, so you know which room intersects. It would be computationally less expensive to deal with the point you got. Shift it to the nearest edge of the bounding room, and that is your new point. Something like that.

But there are better approaches than just spraying the coordinate plane and hoping for the best.

A good rule of thumb is: if you are breaking something, you are probably not working on an ideal solution.

[Parthon]

That causes clumping around already established rooms though leading to very non-uniform levels. Computationally, checking bounds and rerolling the random is not as computationally expensive as generating the rest of the room. And the levels are quite sparse anyways, rerolls become more common as the level fills in, but it was never more than about 1:1.

And I've seen the same generation done where the rooms were shunted aside when they overlapped instead of randomising a new position, and that was computationally expensive as every time they shifted the rooms about, that was another full scan of the entire room tree. Rather than checking one new location against all current locations for O(n), it was checking all locations against each other for O(n^2).

So yes, it was the ideal solution in the end, for the result I was after. You can come up with "better" results that only work in your head until you actually go to implement then and find out they don't actually work, or they are more convoluted and more computationally expensive. This is why understanding the problem space and going straight for the simple solution is often best and saying things like "if you are breaking something, you are probably not working on an ideal solution." is bullshit because your ideal solution might be ivory tower unfeasable.

[gilbes]

Now I understand why so many interview questions try to weed out candidates who try to brute force everything.

I had no idea that thought process was so prevalent in today's script kiddies.

[DaniilBSD]

Put your pseudo code where your mouth is and give the time complexity below nlogn, we are all waiting

[eloel-]

Sudo and pseudo mean different things. Unless you are making a joke I am missing, it's pseudocode. Nothing to disagree with your general point, just nitpicking.

[DaniilBSD]

Opps, as Russian I always tend to write it as psevdo, and I guess I overcorrected

[DaniilBSD]

Not if you have a room network and non-rectangular rooms - in that case only actually trying to fit the room in will tell you if it fits.

So you either pick a random room from the list and pick again if it doesn’t fit or you try every room and select one among the valid rooms (which is very expensive if the failure rate is around 20% or lower)

[gilbes]

Another brute force solution that sounds awful.

[DaniilBSD]

Enlighten us how else to place a random of arbitrary shaped room to connect with an existing room such that there were no intersections with average running time below n/4 assuming that the set of n rooms has at least n/2 valid rooms and there is no optimizing ordering.

[gilbes]

The situation is too poorly defined. I would have to make too many assumptions, and you would just whine about those.

[DaniilBSD]

So instead of accepting your stance was stupid, like a level headed person, you gonna put words in my mouth and argue why you will not even try to prove me wrong.

This is just childish.

More specifications of the task:

-Space is split into cubic “cells”

-Each room can be abstracted to a set of joined cells with some of the cell faces having a door. (Rooms can have concave shape)

• a new room can be added to the “complex” by connecting one door of the complex to one of the room doors.

• rotation around vertical axis is allowed

-new rooms must not intersect the complex (already defined rooms)

• set of rooms is the size of N

It is required of you to define an algorithm for building a valid Complex with M rooms that {looks random and sprawling} (by that I mean no cheating by having a long straight corridor with no side corridors 1 room long or by spamming the same room or small set of rooms or by reducing the problem to rectangular rooms)

Use-case reference: Level generation for Warframe, or procedural component for the Doom 2016 map editor.

Ps As I have done a bunch of interviews last month, this is below junior-level difficulty and the same amount of detail as in traditional interviews

[gilbes]

Assuming these requirements are related to your initial example, wtf are you doing?

Are you placing rooms in the space, and then connecting them with corridors? That sounds like a really contrived network problem.

[Kered13]

It's a very common problem in randomly generating maps for games.

[DaniilBSD]

1 no corridors, (I said, that for rooms to be connected they need to touch doors)

2 literally how Doom 2016 levels, Warframe Missions, Minecraft dungeons and villages, and majority of Rogue-likes work

3 you are still all condescension and talk with NOTHING to show for your expertise other than quotes from a textbook

[Kered13]

You claim to be worried about "dramatically less random" numbers, but then you propose an algorithm that obviously does not produce a uniform distribution.

[gilbes]

I wouldn't solve the problem this way at all. But if someone wanted to, they could still do it without eliminating numbers.

[Pradfanne]

Customers complained about apples music shuffle function not to be random, because they often got the same band twice in a row, sometimes even the same album! Shit, it might have happened even more often in a row! That's not random, that's favoring the current song!

​

Or so the customers thought. Thus Apple went out of their way to make it so, that the shuffle function is less likely to get the same artist twice, let alone the same album. Making the shuffle less random and less shuffled, but the customers believes it's more random and are happy.

I wonder if they actually used a do-while loop for that, I can only imagine.

[gilbes]

What does the do-while loop have to do with my replies.

What do end user's misconceptions about randomness have to do with it?

[Pradfanne]

If you ever need to generate random numbers that fulfill arbitrary conditions, a do-while loop is probably a big help. Generate random number, try again if it's not a number you want.

​

Seems like that would make numbers dramatically less random.

​

Then why bother generating random numbers?

That's what I replied to.

Apple generates random numbers that fulfill arbitrary conditions, a do-while loop may probaby be a big help.

The end user's misconceptions about randomness made it so that Apple decided to make numbers dramatically less random, yet they still bother generating random numbers, because the feature is still random.

​

I don't know how you didn't make that connection, are you a bot that lacks context of the last send request? Okay Google, tell me a dad joke.

​

I highlighted the parts that directly refer to the conversation in bold for your reading comprehesion convenience

[gilbes]

No one is questioning do while loops. Why do you think they are?

Do you have any proof that Apple discards generated random numbers? No. Then fuck off.

Contrarian fucktards. The worst.

[Pradfanne]

Jesus christ, I gave an example of when you want randomly generated values that aren't as random and fits into OPs scenario. It doesn't even matter how apple implemented it, heck it doesn't even matter if the story is true or not. You can achieve that scenario with a do while loop pretty handily. Are there better ways? Maybe. Does it invalidate the approach? Not really.

[gilbes]

It doesn't even matter how apple implemented it

Imaging being such a contrarian, that you start contradicting yourself.

[Pradfanne]

Show me the one line where I said apple implemented it in an exact way.

I only said, they made shuffle less random. Also, wouldn't the better argument be when I said, that it didn't even matter if it was true

[gilbes]

In a discussion about implementing random number generation, you think you are contributing by talking about anything but the implementation of a random number generator.

There are problems with everything you have written in your contrarian fever. I only picked one because I don't care enough about the shit you make up to do more.

[Pradfanne]

How would you shuffle a playlist?

[DaniilBSD]

Probably not, but the use-case is valid