A teaser. HHHHHMMMM...

Baz_

Well here is a teaser for ye, you don't even have to be actual programmers all I want is a bit of pseudocode.

Using random number generation, generate 20 numbers between 1 and 20 (inclusive of both) and store the numbers in an array. (heres the teaser). The program should use the smallest possible array to store the numbers produced.

To be done in C. What I don't see is how you can do it without actually declaring an array of 20 elements but the way the question is phrased (in the book) it sounds like they want you to use a smaller array. What if however you get all numbers from 1 to 20, you will then need to use a full twenty elements. If anyone has come accross this problem before then I would appreciate an answer, if not give me your answer, and most of all tell me of any illogic in my answer.

Hobbes

Hmm,

I guess the easiest way would be to use Binary.

5 bit per number, but that would be too easy and extremly wasteful.

I'm sure there is some way to compress that down. Maybe having the high bit set something or other (it's late).

dogs

You could just store the srand seed, with
the same seed the sequence should always
be the same.



--dogs

Cerberus

Are you sure the exercise isn't just testing your grasp of declaring arrays e.g. you know the way that some people think that an array with 20 elements is numbered 0-20 instead of 0-19 and in your question the "inclusive" part is thrown in just to confuse people more. If the question is not about this then I would go with dogs idea. I was thinking about a way you could get away with just a 19 element array and while it would work, retrieving the numbers again would be a ***** in terms of the amount of code needed. Any saving got by reducing the size of the array would be lost in size of the extra code needed.

Baz_

So I'm kinda right??

Hobbes

Originally posted by Cerberus:
Any saving got by reducing the size of the array would be lost in size of the extra code needed.

Ahh the mysteries of the DB. While it might be true for the experiment it would make a lot of sense when you have a couple of 100,000 records.

Dogs is a cute method, but not really portable and changing any of the code will destroy your current db of random numbers?

Cerberus

True Hobbes, true..

El_Presidente

OK, if you generate 20 numbers and want to record all of them you just declare an array of 20 elements and fill it right on up.

If however the question is asking you to fill it in such a way that if a number is already stored then dont bother recording it again you would construct a linked list, only adding an element if the number to be entered has not alrady appeared.

When 20 numbers have been generated you declare an array of whatever number of elemens you have and dump em in.

easy


(that may all be utter crap btw.)

Baz_

Well thats kinda good, cept that in c all declarations have to be done at the start of a body of code, also the book advocates only using constructs which have already been covered in the book when answering a question, and lists do not appear before arrays.

quozl

you can make an array whenever you want, just malloc some memory.
Have a pointer defined at start to array then when you work out size needed malloc it.

Shiminay

Don't forget to free after you malloc

---

All the best,

Dav
@B^)
My page of stuff

Keeks

I would have to aggree with Cerberus.

There are a million ways to solve the problem but the question asks to use an Array to store the twenty numbers in the smallest possible array. to do this you would declare an array like

int array[19]

This will store 20 numbers (0-19).

But this isn't the smallest possible array that can be achieved. This is one that is smaller.

char array[19]

Can you spot why? ;-)

Draco

Originally posted by Keeks:

int array[19]

This will store 20 numbers (0-19).

No it won't. It will store 19 number - 0 to 18.

Originally posted by Keeks:

char array[19]

'Cause a char is usually a byte. An int is 4 (I think..) so you're using 1/4 of the memory

Draco



[This message has been edited by Draco (edited 18-08-2000).]

Hobbes

Originally posted by Draco:
'Cause a char is usually a byte. An int is 4 (I think..) so you're using 1/4 of the memory

Draco

Char = 8 bits (1 byte).
Int = 16 bits (2 bytes) although most machines default to Long Ints which is 32bits (4 bytes).

4 bits = Nibble.

Just my 2 bits

DeVore

This question is badly phrased.

The smallest array in elements is a single "row" array of a struct something like this (pseudo code)
begin struct
one as bit
two as bit
.
.
.
twenty as bit
end struct

Then assign Array[0].four to be true if you generate "4" as the random number and so on...

This will probably be considered a cheat but it does hold them in the smallest memory as per the array....


DeV

Hobbes

Originally posted by DeVore:
This question is badly phrased.

DeV

You assume that you only pick one random number once (eg. You can't have 20 "4"s). In which case that would be the correct thing to do.

Your array would be 20 bits long ( 2 Bytes, 1 Nibble).

If you were storing each number as an individual then it would be 5 bits to number (12 Bytes, 1 Nibble).

Both leave 1 Nibble in waste. You could probably compress this down more using some kind of compression (Run line encoding?)

But I still think dogs wins the award.

Baz_

Originally posted by DeVore:
This question is badly phrased.
DeV

Well then here it is exactly as it appears in the book:

6.28 (Duplicate elimination) In Chapter 12 we explore the high-speed binary search tree data structure. One feature of a binary search tree is that duplicate values are discarded when insertions are made into the tree. This is referred to as duplicate elimination. Write a program that produces 20 random numbers between 1 and 20. The program should store all non-duplicate values in an array. Use the smallest possible array to accomplish this task.

Now you'll notice that the question doesn't actually say 1 and 20 are inclusive, but I still would assume that they are [inclusive] because they want you to generate 20 numbers. However that is just an assumption and as they say assumption is teh mother of all **** ups.

I feel I should also repeat that the book advocates using only programming constructs already covered in the book which are: selection structures, repetition structures, functions and arrays.

But this post was mainly to clear up the ambiguity from my original post, sorry.

DeVore

Ok, I slightly misunderstood you.
I thought the program was to produce random numbers until it produced AT LEAST one of each of 1-20 (a dumb program I know but these exams are usually bent out of shape).

My question remains.... How are they measuring "Smallest".
Smallest by memmory it takes?
Smallest by the number of elements in it?

They might not be considered the same thing.


Here's another point:

Who the hell cares!

These sort of questions spring from a time when you really needed to salvage memory...
I'm sorry but I'll employ a guy who understands the concept of "has to be done by Friday evening" faster then someone who will spend ages agonising over the "right" way to do it.

Wtf is this trivia important?

Pick any one of the solutions offered here, they may not be perfect but they are more then acceptible... and move one.

College. Sometimes you have to wonder if it would be different if CS depts had to produce real software to support their budgets... hehe

DeV.

dogs

> College. Sometimes you have to wonder if it would be different if CS
> depts had to produce real software to support their budgets... hehe
>
> DeV.

good idea, but then how would you keep
philosophy courses running ? and would the
law students have to keep tripping in the
corridoors just to survive ?

ecksor

Originally posted by DeVore:
Who the hell cares!

These sort of questions spring from a time when you really needed to salvage memory...
I'm sorry but I'll employ a guy who understands the concept of "has to be done by Friday evening" faster then someone who will spend ages agonising over the "right" way to do it.

Well, saving memory in storage isn't as big an issue as it was when you were a nipper DeV, but there is the modern bottleneck of time taken to travel across the network. If you can get the same info across in less bytes, then you're going to save time.

X_OR (bloke who DeV employed :P )

Draco

Originally posted by DeVore:
Who the hell cares!

'Cause it makes you think.

When you do have the time to do something, it is nice to do it in an elegant way rather than some piece of crap thrown together that just about does the job. Of course, once deadlines start looming, elegance goes out the window.

Draco

Baz_

Thank you to the last three posts. Yes Dev I care because I have the time to care, I could've just thrown the 'proggie' toghether in a minute if I just took the easy way and used 20 elements, you know just in case the random number generator was a little too perfect, but I was trying to see if anyone had a better solution, which they did and thanks to all who contributed, but what I didn't expect was a flamer of a post such as yours. A very enlightened opinion that, ta.

LoLth

If you're not worried about using the number for anything afterwards and just want the result to appear on the screen could you use something like,

(needs to be translated from english to pooterspeak)

an array of 10 numbers 0-9
each random choice will also randomly choose whether to choose one or two numbers but the first number cannot be bigger than 2.

eg: 01 , 11, 21, 02, 12, 22 then your array would be smaller.

or, if you're not limited to only one array,
use 2 arrays, the first with [0,1,2] and the second with [0-9].
then pick one from each array, if the first pick = 0 it doesn't get displayed.

probably useless but it would be smaller than using all twenty numbers. would it?

Hobbes

Originally posted by DeVore:
I'm sorry but I'll employ a guy who understands the concept of "has to be done by Friday evening" faster then someone who will spend ages agonising over the "right" way to do it.

I wouldn't. While being able to program quickly might be a bonus, having a cowboy coder on the job can give you serious headaches and costs further down the road (normally after they have left).

Likewise with Textbook coders. I would be more likely to hire a person who was an average coder and able to think "outside the box". Learning the languages is easy and just takes a bit of study. It takes actual skill to write good code.

Wtf is this trivia important?

Because none of the answers are really *wrong* or *right*, they are different ways at looking at the same problem. Like I said already, Dogs answer was totally left field and kind of the thinking these problems should promote and I hope we see more of them on here.

spod

beer and ubb and late nights after a nightmare couple of days in work are bad.

that is all.


[This message has been edited by spod (edited 22-08-2000).]

ecksor

Originally posted by Hobbes:
I wouldn't. While being able to program quickly might be a bonus, having a cowboy coder on the job can give you serious headaches and costs further down the road (normally after they have left).

Well, I don't think he was advocating cowboy programming by any means. More to the point is that some ways of solving a problem may be more efficient than others, but are not generally worth it if it means a significant amount of time spent by the programmer. In the above instance, I think DeVore would have just declared the array with 20 elements and not wasted time pondering how he could save a few bytes. If problems can be solved with more disk space, or more RAM, then nowadays it makes far more sense to do that, as programmer time has become very expensive, and there isn't enough of it to go around. That hardly makes someone a cowboy programmer, and in some people's eyes it makes them a more professional programmer.

The trick is to know when you these issues _are_ important, and can't be better solved by other means.

Gavin

hum, maybe just turd but anyhoo..

create an array of 20 elements,
then if you get a number, you mark that location in the array with a 1

eg, array[0] = 1
means you have a single zero.
array[0] = 2, u got 2 zero's.

?

( or else do a multi d array.. haha)
look it's only got 1 element in it !!

Gav

Hobbes

Originally posted by X_OR:
The trick is to know when you these issues _are_ important, and can't be better solved by other means.

so what your saying is your answer to the problem is "Get a bigger hard drive" ?

logic1

Ahhh i may be totally wrong but my understanding of the question is that the numbers are generated randomly and therefore repitition of any number is possible. What we want to achieve is an array which will hole one of each number generated, i.e. if two 4's are generated we only allocate mem for one. To do this we would have to know the outcome of the generation before we allocate memory alternatively loop the allocation routine with each generation i.e. 4 is generated allocate memory and store it, if another 4 is generated cross check this with the numbers already stored and if any repitition occurs discard the newly generated int without allocating any memory.

Again I'm probably wrong.

.logic.

DeVore

Baz, sorry man, I wasnt flaming you, in fact I wasnt flaming anyone. X_OR has it bang on the head.

If this were a 2.5Million array problem, then it would be worthy of time in consideration because the potential savings are large.

If you choose to use these as brain teaser, fire ahead! I love them to be honest (and YES I realise the thread is called "teaser")
My annoyance comes from people who DONT see the world the way X_OR does and spend ages agonising over the "right" way to do it to save a few bytes.

Take *everything* into consideration including your own time constraints and costs and then make a value judgement as to whether its worth the diminishing return to continue to contemplate a better solution then the one you already have.

But I wasnt flaming anyone
hugz!

DeV.