Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

AppGameKit Classic Chat / Creating a set of random but unique binary numbers

Author
Message
Timshark
16
Years of Service
User Offline
Joined: 30th Jun 2007
Location: Oslo, Norway
Posted: 30th Apr 2013 20:25 Edited at: 30th Apr 2013 20:31
I'm trying to patch together a way to create 26 unique 16 bit random binary numbers with a fixed amount of allowed 1's. I'm almost home I think...
but the numbers stops updating in my main loop...

Is there any brainy math crunchers out there that can tell me what I'm doing wrong?

Markus
Valued Member
20
Years of Service
User Offline
Joined: 10th Apr 2004
Location: Germany
Posted: 30th Apr 2013 21:30
its //duplicate=1
if duplicate=0 then done=1
Timshark
16
Years of Service
User Offline
Joined: 30th Jun 2007
Location: Oslo, Norway
Posted: 30th Apr 2013 21:50
Hi Markus

What do you suggest I do?
There is a test to check if this works by setting the oneamount to 15 - since it's impossible to create 26 unique 16 bit binaries with 15 1's.

I'm not sure what to do...
Timshark
16
Years of Service
User Offline
Joined: 30th Jun 2007
Location: Oslo, Norway
Posted: 30th Apr 2013 22:00
I discovered an error

//if oneDone<=oneAmount
should be
if oneDone<oneAmount

But this doesn't help either. If I set the oneamount to 7 or 8 the screen will print new numbers for a short while and then stop... I don't understand why it's stopping.
Phaelax
DBPro Master
21
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 30th Apr 2013 22:02
Wouldn't it be more efficient to just generate random numbers and THEN convert them to binary strings?

"You're all wrong. You're all idiots." ~Fluffy Rabbit
Timshark
16
Years of Service
User Offline
Joined: 30th Jun 2007
Location: Oslo, Norway
Posted: 30th Apr 2013 22:11 Edited at: 30th Apr 2013 22:14
Hi Phaelax

Ok. But how do you now if the binary produced by bin(i) only contains the fixed limit of 1's?

Let's say I want 4 random unique 16 bit binaries like this:

1100101000000000
1100100000001000
1100001000000010
1100100000100000

But they HAVE to only have 4 one's.
Kevin Picone
21
Years of Service
User Offline
Joined: 27th Aug 2002
Location: Australia
Posted: 30th Apr 2013 22:38
There's a bunch of ways, one path might be masking powers of 2 together.



Timshark
16
Years of Service
User Offline
Joined: 30th Jun 2007
Location: Oslo, Norway
Posted: 30th Apr 2013 23:55 Edited at: 30th Apr 2013 23:56
Kevin,

If I understand you correctly (and please remember - I'm a beginner)
and I translate this to tier1
it will be:


Yes, this give me only 4 1's - but not 12 zeroes everytime. (I'm sure I can figure out a way to add those zeroes)

But I'm still lost when it comes to my original code and I know It's probably cumbersome -

I'm trying to come up with a method of creating an array of 26 unique random 16 bit numbers (with all 16 digits) with a fixed set of 1's. My problem is that I can't find a way to check if those 26 random numbers are indeed unique.
Phaelax
DBPro Master
21
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 1st May 2013 05:02 Edited at: 1st May 2013 05:29
If you want a 16bit number, limit your numbers to 0-65535 (2^16). Which according to AppGameKit help files, random() is limited to that range anyway.

Quote: "But how do you now if the binary produced by bin(i) only contains the fixed limit of 1's?"

I had missed that part. You could use bitmasking here.

I just now noticed Kevin already posted the same method I was thinking.


Quote: "Yes, this give me only 4 1's - but not 12 zeroes everytime"

Unfortunately, that's just the way the BIN function works. It'll only return from the most significant digit. Leading 0's to mean anything so it drops them from the string, unlike Darkbasic which returns 32 bits regardless. You could either write a function to pad it (which I'll provide since I already wrote one for another program) or write your own BIN function.



To check for duplicates, since AppGameKit doesn't have any kind of HashSet functions, you'll have to search the array every time you want to insert a new value to make sure it's not already there.



"You're all wrong. You're all idiots." ~Fluffy Rabbit
Timshark
16
Years of Service
User Offline
Joined: 30th Jun 2007
Location: Oslo, Norway
Posted: 1st May 2013 06:11 Edited at: 1st May 2013 06:16
Phaelax,

Thank you, oh so much.

This has been a real lesson to me. After Kevin posted his code I googled bitwise operations and learned a lot.

I also tried to implement Kevins code into my own and ran into the same problem as before. The program stopped producing numbers after a while. Now, when you mention that random numbers has a limit of 65534 I think that this is the problem with my code. In some way I manage to feed the random function too high a number - and then the program just halts without crashing.

And now you have given me EVERYTHING. I'm so spoiled.

Thank you so much for your help
JimHawkins
14
Years of Service
User Offline
Joined: 26th Jul 2009
Location: Hull - UK
Posted: 2nd May 2013 00:39 Edited at: 2nd May 2013 01:04
This is an interesting little problem, but a great demonstration of why doing as much as possible with off-line tools is so much better.

I've made a little program using Delphi to show why using the super-computer on your desk might be a better idea than asking a mobile to do it:

http://youtu.be/LwKXSxpK6VM

Part 2 is at (in case the link in part 1 didn't work):

http://youtu.be/BG4G70GXEPE

Don't be put off by the fact that this program is written in Pascal. It can produce an output that can be used in AppGameKit Basic as well.

I've attached a zip file with the program in. It has no dependencies, so you can run straight out of the zip.

-- Jim DO IT FASTER, EASIER AND BETTER WITH AppGameKit FOR PASCAL

Attachments

Login to view attachments
JimHawkins
14
Years of Service
User Offline
Joined: 26th Jul 2009
Location: Hull - UK
Posted: 2nd May 2013 01:08
One thing I didn't mention is that using a Random() function to generate something and then checking is very dangerous. It is possible that the result will never be unique, and then you have an infinite loop.

Infinite loops are DEATH!

-- Jim DO IT FASTER, EASIER AND BETTER WITH AppGameKit FOR PASCAL
Marl
12
Years of Service
User Offline
Joined: 19th Nov 2011
Location: Bradford, UK
Posted: 2nd May 2013 03:14
I wouldn't have done it that way, for a start it overlooks certain shortcuts;

For example, the smallest possible number to check would be 2^n - 1 where n is the number of bits

So if n were 7 for example - ie you want 7 bits set - the smallest possible number which matches this criteria is the one with the lowest 7 bits set -

0000000001111111

127 ( or 2^7 - 1);

This has to be true, since moving any bit would result in a larger number.

I would have started by looking at the number as a list of bits, with all the ones at the bottom and the zeros at the top - so the bottom entry is the lowest bit.

Then do something similar to a sort on the list - each step of the sort represents a different number. It wouldn't be a sort, more like a series of waves.

Step 1 - move the bottom zero down to the bottom - each step produces a unique number

0000000010111111
0000000011011111
0000000011101111
...
0000000011111110

Step 2 - move the next zero down 1 place and move the first zero up next to it - in one move

0000000100111111

Step 3 - repeat the movement of the bottom zero

0000000101011111
0000000101101111
0000000101110111
...
0000000101111110

Step 4 - move the second zero down one, bring the other back

0000000110011111

repeat again

0000000110101111
0000000110110111
0000000110111011

..and so on.

It looks long winded, but with recursion it gets much simpler - particularly when you see the pattern.

This way you only process numbers which match the initial criteria
Phaelax
DBPro Master
21
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 2nd May 2013 03:52
Quote: "One thing I didn't mention is that using a Random() function to generate something and then checking is very dangerous. It is possible that the result will never be unique, and then you have an infinite loop."

While I agree that possibility is there, it's very unlikely. One possible solution would be to look at a deck of cards. There's plenty of examples on the net for pulling a card from a deck and removing it so it doesn't get pulled twice. When grabbing the 4 bites, you'd make a deck of 16 cards in this case.


Quote: "why doing as much as possible with off-line tools is so much better."

I think that depends on what the intended application is for. If he just needs a static set then yes.


Quote: "If you want a 16bit number, limit your numbers to 0-65535 (2^16)"


Just a little more info. 2^16 returns 65,536, so that's why the random number range is 2^0 to 2^15. The exponent basically represents the bit place in your binary string.

2^0 = 1
2^1 = 2
2^2 = 4
2^3 = 8
2^4 = 16
2^5 = 32
2^6 = 64
2^7 = 128
2^8 = 256
2^9 = 512
2^10 = 1,024
2^11 = 2,048
2^12 = 4,096
2^13 = 8,192
2^14 = 16,384
2^15 = 32,768

Basically, what the random number does is grab 4 of those 16 numbers above and adds them together. Add all 16 together and you'll get 65,535.


Timshark, since you mentioned you weren't familiar with bitwise operation, I'm curious to know what exactly you needed this for?

"You're all wrong. You're all idiots." ~Fluffy Rabbit
JimHawkins
14
Years of Service
User Offline
Joined: 26th Jul 2009
Location: Hull - UK
Posted: 2nd May 2013 09:16
Fair enough - but why use a complex solution when a simple and robust one is available?

As far as the cards go, that's a predetermined set, just like the list I generated. Picking from a list is NOT the same as rolling a dice until you get a six - which could go on for ever!

-- Jim DO IT FASTER, EASIER AND BETTER WITH AppGameKit FOR PASCAL
Markus
Valued Member
20
Years of Service
User Offline
Joined: 10th Apr 2004
Location: Germany
Posted: 2nd May 2013 09:43 Edited at: 2nd May 2013 09:51
i understand you AmountOne as limit.
say AmountOne=7 can contains 1-7 one's,
or did you want 7 one's?

my example
Phaelax
DBPro Master
21
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 2nd May 2013 12:24
Quote: "As far as the cards go, that's a predetermined set, just like the list I generated. Picking from a list is NOT the same as rolling a dice until you get a six - which could go on for ever!"

Didn't say it was. I think you misunderstood what I was trying to say. The deck of cards in this case would be the predetermined list of the 16 numbers I posted above. Pull 4 'cards' from the list. This method I was implying only to create the initial number, not check for dupes against the other 16bit numbers. So at best it would at least eliminate the inner REPEAT block in my code, but not the outer.

"You're all wrong. You're all idiots." ~Fluffy Rabbit
Timshark
16
Years of Service
User Offline
Joined: 30th Jun 2007
Location: Oslo, Norway
Posted: 2nd May 2013 19:06 Edited at: 2nd May 2013 19:07
PHAELAX,

Quote: "Timshark, since you mentioned you weren't familiar with bitwise operation, I'm curious to know what exactly you needed this for?"


Right now, this:


The red dots are the 1's. This will represent letters in the alphabet. A sort of code that will be randomized every time.

I'm a big fan of random and procedural algoritm creations in games. These days I'm (re)learning to program with agk and currently I'm exploring different ways of creating random graphics based on a set of rules (algorithms).

I'm not sure how I will implement what I've learned with this topic but bits and bytes sure is closely related to image manipulation - Especially with the new great memblock commands.
Ancient Lady
Valued Member
20
Years of Service
User Offline
Joined: 17th Mar 2004
Location: Anchorage, Alaska, USA
Posted: 2nd May 2013 19:23
Well, assuming that you will be doing a random set several times during game play, how about this.

Create a text file for each grid size (4 across, 5 across, etc.) and number of 1's in each row.
In each file is all combinations 0's and 1's for that combination. The first line will have the number of lines to follow.
Have a string array for everything (assume max number of lines) into which you will read the file.
Have an integer array for everything to indicate the number of actual rows for the combination.
Then, when you need a random string, use the random function with the actual lines as the max and then just pluck out the value.

The file read/initialization only needs to be done once and then you have all the string combinations available.

The files can be manually created.

You could even use one file that has information in the first line like '<grid size>,<max 1's>,<num lines>'. Then, you would read the first line and know the array indices to work with and how many lines to store. After the indicated number of lines, there would be another line with the next set of values indicating array indices and number of lines.

How about that?

Cheers,
Ancient Lady
AGK Community Tester and AppGameKit Master
Timshark
16
Years of Service
User Offline
Joined: 30th Jun 2007
Location: Oslo, Norway
Posted: 2nd May 2013 19:41 Edited at: 2nd May 2013 21:41
Ancientlady,

This is what Jimhawkins proposed and showed in his videos. I think this method is a great way to relieve agk of too much work at runtime.

My question has been answered in spades, and I have learned so much with this post.

I hope it was useful for others out there as well.

Thank you all. Code long and prosper.

EDIT: Jimhawkins, I'm not sure if your'e promoting DelphiXe here. But making that program in agk is also possible. That would have been great - if the focus is on learning agk. And it is.
AgentSam
12
Years of Service
User Offline
Joined: 14th Mar 2012
Location: Virtual Space
Posted: 17th May 2013 04:30
Saw this thread and got addicted to playing with the bits. Then decided that for completeness sake, I'll convert Jim's code to AppGameKit TIER 1.

So, grab the zip from the attachment.

The source also gives a glimpse of my coding style, which has evolved around certain personal preferences and the tools I use. Oh, the code is a bit longer than necessary because I used a code template as the basis of the project and didn't bother cleaning it up much.

I think Jim provided the most elegant solution to this problem.

Cheers,
AgentSam

Attachments

Login to view attachments
JimHawkins
14
Years of Service
User Offline
Joined: 26th Jul 2009
Location: Hull - UK
Posted: 18th May 2013 15:27
Thanks, AgentSam. Very nice code!

I'm not sure it's the most "elegant" solution, but I always work on Einstein's principle "Keep it as simple as possible, but no simpler."

An elegant solution is to run a permutation on the bits. So I did this, and it's ten times slower than the simple numeric method. That's understandable, because permutations are complex, whereas sticking a number in a field is simple and processor-friendly.

I modified the computation routine either to use or not use and array. In both cases I have used Phaelax's sensible suggestion to start from the lowest and go to the highest possible numbers.



There is no significant difference between the run time of the two approaches - 18 milliseconds on a AMD quadcore and 15 milliseconds on an i5. Most of the cost here is adding to the stringlist. Using a TList and not outputting strings would be radically faster.

This code is completely OS-agnostic, and will run on Windows, Android, OS X, or iOS.

-- Jim DO IT FASTER, EASIER AND BETTER WITH AppGameKit FOR PASCAL
AgentSam
12
Years of Service
User Offline
Joined: 14th Mar 2012
Location: Virtual Space
Posted: 20th May 2013 00:30 Edited at: 20th May 2013 00:57
Hi Jim,

Indeed, Phealax's (or was it Marl's) suggestion is sensible, and saves a large number of iterations inside the loop; especially when the result values need to contain more than 8 enabled bits... (so, it saves more the larger the number of enabled bits is).

And here's the AppGameKit TIER 1 code with the latest tweaks, and a new function for TIER1 called "SetBits", which takes a starting bit position and the number of bits to enable, and returns a value based on those parameters. (This is used to compute the minimum and maximum possible values in the result set, which serve as the beginning and end of the loop.)

(I think I'm taking my eyes off this thread now. The fun has passed, and the solutions have been provided.)

Cheers,
AgentSam

Attachments

Login to view attachments
JimHawkins
14
Years of Service
User Offline
Joined: 26th Jul 2009
Location: Hull - UK
Posted: 20th May 2013 08:53
Quote: "I think I'm taking my eyes off this thread now. The fun has passed, and the solutions have been provided."


I know what you mean - but it's an unusual problem, and a nice distraction from what I'm doing otherwise!

-- Jim DO IT FASTER, EASIER AND BETTER WITH AppGameKit FOR PASCAL
Phaelax
DBPro Master
21
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 20th May 2013 12:57
Agreed. It's fun to attack an unusual problem and get away from all the common coding quirks.

"You're all wrong. You're all idiots." ~Fluffy Rabbit

Login to post a reply

Server time is: 2024-05-04 18:25:17
Your offset time is: 2024-05-04 18:25:17