Programming is about elegance. Yesterday someone asked me how to write a program that displays six unique random numbers (1 to 9). The beauty of this problem is that it is exceedingly simple to solve, but still leaves room for some awesome-source.
Here’s the simple solution in PHP (I make no claims to this being awesome):
$used = array();
for($i=0; $i<6; $i++){
$x=rand(1,10);
while(in_array($x,$used)){
$x=rand(1,10);
}
$used[] = $x;
echo $x . ' ';
}
Notice that this isn't a battle for who can do this in the least lines.
I duly expect to be beaten on the head for some or other bad PHP habit. I'm also expecting people to submit the solution in Perl, Python, Erlang, Ruby, C, C++, Java and anything else you feel like trying your hand at.
ps. Wrap your solutions in <pre> tags.
#1 by Neil Garb on June 25, 2008 - 10:09 am
Quote
Is there a prize for the most convoluted solution?
#2 by Michael on June 25, 2008 - 10:11 am
Quote
#!/usr/bin/env python
import random
print random.sample(range(1, 10), 6)
#3 by Jonathan Hitchcock on June 25, 2008 - 10:13 am
Quote
Your code could theoretically loop forever (since you have a loop that goes “while the random number you chose is one of these things, do this”), and is ridiculously inefficient anyway. You can’t go “keep picking random numbers until they match some sort of criteria”.
$used = array(); for($i=1; $i<10; $i++){ $used[] = $i; } for($i=0; $i<4; $i++) { array_splice($used, rand(0, count($used)-1), 1); }(P.S. My code’s shorter than yours, nya nya nya.)
#4 by arbitraryuser on June 25, 2008 - 10:16 am
Quote
@Hitchcock,
Yes, I suppose it is *possible* that random would never hit another unique number…
I also think it’s *possible* that you just got served by Mike…
#5 by Jonathan Hitchcock on June 25, 2008 - 10:23 am
Quote
Endersby: Yes: the point is, your code swings and swings until it gets it right, and is thus a really inefficient way to do things. My PHP code was to fix your bad method, in your horrendous language, not to write the shortest most efficient one (in which case I would have done exactly what Michael did). So, no, I do believe it was you who got served by both of us. Thanks for playing.
#6 by Shayan on June 25, 2008 - 10:23 am
Quote
Darn, I had….
#!/usr/bin/env python
import random
x = set()
while len(x) < 6:
x.add(random.randint(0,10))
print x
Didn’t know about the sample function, that’ll be useful sometime.
#7 by arbitraryuser on June 25, 2008 - 10:35 am
Quote
Hitchcock: If you were teaching someone to program would you teach them with your method?
Also, your code didn’t actually achieve the end goal:
1. You have an ‘off-by-one’ bug that results in it only printing out 5 numbers instead of six.
2. It doesn’t display anything (as per the specification).
I like your different way of tackling the problem though. I wouldn’t have thought of doing it that way.
#8 by Jonathan Hitchcock on June 25, 2008 - 10:41 am
Quote
Like I said, I wasn’t trying to make a good method, I was trying to fix your bad method ;-) I wouldn’t teach anybody to program in a language so limited. And, yeah, you’re right, originally I had it from 0 to 9, so I had to remove four numbers – I took zero out and didn’t decrease how many I removed. My bad. (Feel free to add ‘print_r($used)’ at the end.
#9 by Michael on June 25, 2008 - 10:44 am
Quote
Endersby: To be fair, my Python version doesn’t print out what your PHP version does either.
You’d have to use:
print ” “.join(random.sample(range(1, 10), 6))
(assuming you don’t really need the space at the end anyway.)
#10 by arbitraryuser on June 25, 2008 - 10:48 am
Quote
Actually a more elegant solution would be “implode(‘ ‘, $used);”
I guess this raises an interesting question about teaching people how to program. Do you teach them the absolute shortest way possible or the way where they’ll be able to understand what’s going on? Is using sample() the correct way to teach a complete noob how to program? I think Jerith will have something to say about this… I await his most level headed answer.
#11 by Brad on June 25, 2008 - 10:58 am
Quote
Not the most efficient, but a short php solution:
$fu = array();
while (sizeof($fu)<6) {
$fu[rand(1,10)] = ‘nom’;
}
print_r(array_keys($fu));
#12 by Brad on June 25, 2008 - 11:06 am
Quote
My solution also wins because it includes nomnomnomnomnomnom
#13 by Michael on June 25, 2008 - 11:07 am
Quote
I’d say random.sample() is easier to understand than a couple of loops, nested or otherwise :)
It’s still useful to know how to do it if your language doesn’t have a random.sample() equivalent.
#14 by Michael on June 25, 2008 - 11:08 am
Quote
Oh, and ” “.join(…) is equivalent to implode(‘ ‘, …).
#15 by jerith on June 25, 2008 - 11:18 am
Quote
Good thing my Firefox crashed halfway through my duplication of Michael’s solution, thus forcing a reload and giving me this most excellent comment thread.
I shall address the education question when I have more time to consider it, but here is the Erlang implementation you asked for. I specifically chose a method not yet used here:
uniquerandoms(Min, Max, Count) -> ShuffledList = shuffle(lists:seq(Min, Max)), lists:sublist(ShuffledList, Count). %% The shuffling implementation below was found on the interwebs: %% http://www.trapexit.org/RandomShuffle shuffle(List) -> %% Determine the log n portion then randomize the list. randomize(round(math:log(length(List)) + 0.5), List). randomize(1, List) -> randomize(List); randomize(T, List) -> lists:foldl(fun(_E, Acc) -> randomize(Acc) end, randomize(List), lists:seq(1, (T - 1))). randomize(List) -> D = lists:map(fun(A) -> {random:uniform(), A} end, List), {_, D1} = lists:unzip(lists:keysort(1, D)), D1.Printing out the answer is left as an exercise for the reader.
#16 by Brad on June 25, 2008 - 12:06 pm
Quote
Another PHP solution, using only array functions:
$nums = array_keys(array_pad(array(),10,’nom’));
array_shift($nums);
shuffle($nums);
$nums = array_splice($nums,0,6);
print(implode(‘ ‘,$nums));
#17 by Jonathan Hitchcock on June 25, 2008 - 12:34 pm
Quote
So, we have three basic methods for doing it so far:
1. Keep picking random numbers, discarding duplicates, until we have as many as we need.
2. Generate a list of all possible numbers, and throw away random ones until you have as many as you need.
3. Generate a list of all possible numbers, shuffle it, and throw away the first/last however many you don’t need.
Oh, four: 4. Use the builtin function to do what we need.
This is what I’d explain to the kid I was teaching to code, rather than showing him array_splice()s and samples().
#18 by jerith on June 25, 2008 - 1:02 pm
Quote
On education:
Your goal, when teaching programming, is to teach programming. You should not be teaching a specific language (although you need a language to teach in, the distinction is subtle but important) and you should not be teaching particular techniques except where they are important more generally.
With this in mind, you want a language that gets out of your way when you want it to but is flexible enough to demonstrate advanced concepts when necessary. Obrant: Java is not this language. Neither is Delphi. Python’s a reasonable choice. (Yes, this is a dig at the local education department.)
With this in mind, you probably don’t want to be teaching the One Right Way To Do It for pretty much anything. What methods you teach should depend on what concepts you are teaching. In this case, if the selection is incidental to the lesson, use the standard library function that does the hard work for you. If the implementation is central to the lesson for some reason, you need to cover that.
It is fairly important, in my opinion, to be able to ignore anything that isn’t central to the concept being taught. This will never be universally possible, but it is far easier in some cases than in others. To use an example I’m rather fond of, consider a student’s first introduction to a programming language.
In Python:
In Pascal:
program HelloWorld; begin writeln('Hello world!'); end.In Java:
class HelloWorld { public static void main(String args[]) { System.out.println("Hello World!"); } }The first two are fine. Neither contain more concepts than “this is a program” and “we want to print ‘Hello World!’”. Java, on the other hand, requires either explanation or glossing-over of classes, public/private methods, static methods, functions and parameters. All of these are important, to be sure, but the student should not have to deal with them all at once.
In conclusion, you need balance. Teach what it makes sense to teach. You don’t want to gloss over everything, but neither do you want to dive immediately into the details of everything.
I should actually turn this into a post on my blog. Prod me with something appropriately pointy if I forget…
#19 by Wynand Karsten on June 26, 2008 - 3:06 pm
Quote
Brilliant. I’m no programmer, but the concepts and ideas was nice to see in print (Nothing to do with the code).
#20 by Cyclone on June 26, 2008 - 3:17 pm
Quote
Here is another php version
function uniqRand($count=6, $from=1, $to=10, $maxInstances=1){
$count=abs($count);
$from=abs($from);
$to=abs($to);
$maxInstances=abs($maxInstances);
$extracted=array();
if(($to-$from+1)*$maxInstances=0){
$r=mt_rand($from, $to);
if(!isset($extracted[$r]) || $extracted[$r]<$maxInstances){$output[]=$r;}
else{++$count;};
++$extracted[$r];
};
return $output;
}