chamcham Wrote:I thought about wrap around and it actually makes the problem easier.

Point A= random point in the square
Point B = take point A, move 2 points in the x-direction and choose any y-coordinate
Point C = take point A, move 2 points in the y-direction and choose any x-coordinate

It's a right triangle and none of the points will ever be adjacent to one another.

That algorithm won't ever generate configurations like this one:
● ○ ○ ●
○ ○ ○ ○
○ ○ ○ ○
● ○ ○ ○
which I assume are supposed to be OK...

Also, the C and C# for dummies books are nice and easily findable on the web.

IceCream Wrote:How to not puke while trying to learn to program

Sounds like a New York Times #1 best seller to me!

bombpersons Wrote:If you're trying to get into programming, I wouldn't suggest starting with Visual Basic. Basic isn't well designed to incorporate a OOP design, which VB.NET tries to do.

Remember that she's starting. OOP is at least 500km from where she's at and where she'll ever probably want to go.

IceCream Wrote:hihiii!

so, i've got to learn to program. I'm downloaded VB10, & i'm trying to do a WPF windows application thingy, and using XAML.

Yesterday someone helped me a lot, which was great!!! So, i get some stuff. But, whenever i go to ANY TUTORIAL about WPF or XAML online, no matter how beginner they say they are they start going blahblahblah about Binding or Dependency Properties using language that only someone who's already a programmer is going to understand. And when i try to search for something specific that i want to do, i can never find it.

Congratulations! You've chosen possibly the most complicated intro to programming that there is with WPF WPF is a madness when you first try to learn it (I know, I'm a pro c#/wpf developer)

VB.net is pretty simple to get your head around, and will do fine for what you want to do. I would recommend having a go at C# later though, mostly because for a beginner, Head First C# 2nd ed (Book), kicks ass (there isn't a VB one) and you will actually have a good time learning from it, and come out the other end with a reasonable grounding. Without puking!

As for WPF. It is probably a bit overkill for what you want to do. You could do it easier, and find a lot more tutorials and resources on-line, if you just did it in bog standard WinForms.

Anyway, if you get something knocked up in VB/WPF/c#, or need a hand with something, give me a PM init and I'll give you some help.

Edit: Just noticed you're using a touch screen... so yeah, WPF is a good choice, but definitely not an easy ride for a beginner.
also:
I'm guessing you've downloaded the visual studio express edition for VB? please ignore anyone who tells you not to use an IDE. In Visual Studio, typing propdp then hitting tab twice will bring up a templated dependency property for you to just fill in the gaps - this is an epic time saver!

IceCream Wrote:pm, your general post was really helpful! So, if i learn the basic concepts, they are transferable across different programming languages? (of course, the exact thing to write is different, but are there generally the same level of functionality between different languages?).

Well, mostly. Some languages are a bit poorer in features and some a bit richer, so if you're using a less featured one you might have to do things manually. But I think a lot of the conceptual difficulty of learning to program is working out how to break your problem up into the right pieces, and what the right set of steps is to do each sub-piece correctly.

If you're an experienced programmer then the transition between different languages is not too hard; for a beginner it will be a bit less straightforward, though.

[There are some languages which do things in a radically different way; but I don't think that you're likely to need to use them or that anybody is likely to suggest them as something you might want to learn with.]

pm215 Wrote:

chamcham Wrote:I thought about wrap around and it actually makes the problem easier.

Point A= random point in the square
Point B = take point A, move 2 points in the x-direction and choose any y-coordinate
Point C = take point A, move 2 points in the y-direction and choose any x-coordinate

It's a right triangle and none of the points will ever be adjacent to one another.

That algorithm won't ever generate configurations like this one:
● ○ ○ ●
○ ○ ○ ○
○ ○ ○ ○
● ○ ○ ○
which I assume are supposed to be OK...

With wraparound that pattern is invalid. All of the dots are one square away.

chamcham Wrote:

pm215 Wrote:That algorithm won't ever generate configurations like this one:
● ○ ○ ●
○ ○ ○ ○
○ ○ ○ ○
● ○ ○ ○
which I assume are supposed to be OK...

With wraparound that pattern is invalid. All of the dots are one square away.

This subthread is a nice demonstration of the problems you can get into with an unclear set of requirements :-)

chamcham Wrote:

pm215 Wrote:

chamcham Wrote:I thought about wrap around and it actually makes the problem easier.

Point A= random point in the square
Point B = take point A, move 2 points in the x-direction and choose any y-coordinate
Point C = take point A, move 2 points in the y-direction and choose any x-coordinate

It's a right triangle and none of the points will ever be adjacent to one another.

That algorithm won't ever generate configurations like this one:
● ○ ○ ●
○ ○ ○ ○
○ ○ ○ ○
● ○ ○ ○
which I assume are supposed to be OK...

With wraparound that pattern is invalid. All of the dots are one square away.

From IceCream's desription of the problem, I think that's a perfectly valid pattern. And there are lots of others your algorithm won't generate, like this one:
● ○ ○ ○
○ ○ ○ ●
○ ● ○ ○
○ ○ ○ ○

Icecream, some good advice in this thread. I agree with one thing - learn the programming fundamentals (variables, arrays, loops, objects?) first, then worry about this WPF (not used it, but being from Microsoft it's probably very poorly documented).

Thing is, don't pull your hair out if you're not getting it yet - it's well know fact that most so called programmers can't actually program..

How can this be? Well it boils down to one simple thing; writing a program from scratch is difficult, where as taking an existing program and modifying it is fairly straight-forward (once you've worked out going on). This "cut and paste" coding style is how alot of coders stay in jobs.

So in your case, get as many examples as you can from your colleagues and the internet, and just cobble something together. Your actual problems sounds a little bit similar to naughts and crosses (putting circles in a grid), so maybe try a WPF tic-tac-toe tutorial and then changing it? Here's one that looks nice, with lots of explaining and pictures:

http://www.cespage.com/vb/tutorials.html

The grid issue seems to have been solved above, but yeh don't be afraid to hard code all responses if it's easier.

Good luck, let us know how you get on

Quote:From IceCream's desription of the problem, I think that's a perfectly valid pattern. And there are lots of others your algorithm won't generate, like this one:
● ○ ○ ○
○ ○ ○ ●
○ ● ○ ○
○ ○ ○ ○

I was assuming wraparound horizontally, veritcally, and diagonally.
With those requirements, that pattern is invalid too.

The points on the first and second row are one square away diagonally (up-right or
down-left depending on how you look at it).

Yes, requirements are key here. They completely change how this
problem can be solved. Just imagine the real world, where you're
handed vague, half-assed, incomplete requirements to someone just learning
to program.

Scary when you think about it....and yet it happens all the time in industry...... :-(

iSoron Wrote:EDIT: Here's a python implementation. Squares are numbered from 0 to 15 like this:
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15

Code:

from random import randint
def dist(p1, p2):
    return max(abs(p1%4-p2%4), abs(p1/4-p2/4))

available = range(16)
for i in range(3):
    pick = available[randint(0, len(available)-1)]
    available = [x for x in available if dist(x,pick) > 1]
    print pick

Hmm I hacked this into a PyQt gui, but it often produces O's in adjacent (horizontally or vertically) positions. Here's the code (had to move as the code tags here can't handle it), and here's a pretty picture:


One problem with your solution iSoron is that it doesn't compare the third pick to the first one, which would allow two adjacent circles. But also this code sometimes generates a stack of three circles above one another.

Blahah Wrote:stuff.

There is something VERY wrong with your program. It will make ice puke more than necessary.

Hint (steve jobs).

Blahah Wrote:One problem with your solution iSoron is that it doesn't compare the third pick to the first one, which would allow two adjacent circles.

Actually, it does. There's a typo in your code (line 54):
- available = [x for x in av if dist(x,pick) > 1]
+ av = [x for x in av if dist(x,pick) > 1]

I have little experience with programming outside my research. But here's what I noticed when I read your post:

First, if my intuition is right, the probability that a cell gets a circle shouldn't be uniform. For example, if you put a circle on cell A1 first, then you have fairly large room for the other two, resulting in many possible configurations with a circle on A1. But if you have the first circle on B2, more cells are blocked; all the 8 adjacent cells mustn't have circles. So if you make a list of all possible configurations meeting the no-adjacent-circle criterion, A1 will be marked more frequently than B2. Hence, a program that treats each cell equally will probably give "biased" results, i.e., you'll get a rarer configuration more frequently than you should. So, for example, "putting a circle with a fixed probability if no adjacent cell has a circle" may not be a good move (unless you implement a sophisticated process to fix the bias) if randomness of the configurations shown to your chimp is important, e.g., you want to use statistics.

So I don't think your first idea is very bad. It's just you don't need to use Excel to make a list. In fact, you don't need a list per sa. For example, you can just put three circles on a 4x4 matrix at random and check if the resulting configuration has no adjacent circles. If it doesn't meet the condition, you throw it away and generate another until you get a good one; you only show chimps the one that happened to meet the criterion. (What I mean here is that you code a program that does this automatically, which should be super simple and runs quite fast.)

If you can count the exact number of all the configurations meeting the condition beforehand by using math or a little program, you can replace the random generation process by using "any" sequence of 4x4 matrices with three circles as long as it contains each good configuration exactly once:

1. Pick a random number, say, "r", between 1 and the number of all configurations meeting the criterion.

2. Pick the first matrix with circles from your sequence and check if it meets the criterion. If it's a bad one, you ignore it. You also ignore good ones until you hit the "r"th good one.

This way, you don't need a random three circle generator. You only need a three circle (sequential) generator which produces each good one exactly once. The random part will be taken care of at the first step by a pseudo-random number generator, which you need anyway.

Using a complete list (such as made by Excel) simply means applying the latter method to a sequence without bad ones. But actually you can use any list containing bad ones as long as it contains every good one once because checking if each item is ok is quite easy. So a simple algorithm which sequentially generates matrices with three circles (such as backtracking) will suffice. You can also count the total number of good ones you need at the first step by running that generator once. It's less than 16-choose-3 = 560, which I think is fairly small.

If I were you, I'd do simple backtracking to get a list of all possible good coordinates (such as (A1, A3, C1)...(B4, D2, D4) of the patterns of circles) and then use some reliable pseudo-random number generator to randomly draw items from the list. The rest is a miscellaneous technical part, I think. If the list is too large for your device, you can shrink it by using symmetry (e.g., the mirrored pattern/rotated versions of a good configuration should be good again so you only need one representation for each equivalent class. You code a program in such a way that if you happen to get a random number which isn't correspond to one of stored good coordinates, it picks up on it and generates the right one by mirroring/rotating the symmetric equivalent you already have.). Backtracking and using pseudo-random numbers are one of the most basic things, so you might want to start with these.

Programing seems to be very similar to playing 囲碁

chamcham Wrote:I was assuming wraparound horizontally, veritcally, and diagonally.
With those requirements, that pattern is invalid too.

The points on the first and second row are one square away diagonally (up-right or
down-left depending on how you look at it).

Yes, requirements are key here. They completely change how this
problem can be solved. Just imagine the real world, where you're
handed vague, half-assed, incomplete requirements to someone just learning
to program.

I think it's strange to assume wraparound applied when there was no mention of it. If I handed you a piece of graph paper and told you to fill in two non-adjacent cells, would you assume filling cells on opposite ends of the paper was wrong?

The original description of the problem doesn't seem vague, half-assed, or incomplete to me.

iSoron Wrote:

Blahah Wrote:One problem with MY BRAIN iSoron is that it doesn't compare the third pick to the first one, which would allow two adjacent circles.

Actually, it does. There's a typo in your code (line 54):
- available = [x for x in av if dist(x,pick) > 1]
+ av = [x for x in av if dist(x,pick) > 1]

Hooray! It works! And stupid me for trying to replace available with av and then not doing it thoroughly

liosama Wrote:There is something VERY wrong with your program. It will make ice puke more than necessary.

Hint (steve jobs).

It's cross-platform, I just happened to run it on a Mac.

IceCream Wrote:So, if i learn the basic concepts, they are transferable across different programming languages? (of course, the exact thing to write is different, but are there generally the same level of functionality between different languages?). If so then yeah, maybe learning one with a lot of beginner info available would be better, and then just tranfer that knowledge to what everyone else uses afterwards if i need to...?

I think so, logic is pretty universal, so it's probably a good idea to learn the basics in a simpler language. Something like Python, LUA or Ruby would probably be good. No reason to start with a graphical interface. It's not too hard to print a simple grid on a command line.

And I agree that most coding is being able to break down big problems into lots of smaller problems that are easier to handle.

I've used a lot of Programming languages before but my preferences are C# or C++, but that's just me.

magamo Wrote:First, if my intuition is right, the probability that a cell gets a circle shouldn't be uniform.

You're absolutely right. JimmySeal's algorithm (and my implementation) is biased towards configurations with circles in the center. It's better to just generate random configurations and then check their validity. You'll have to generate ~5 configurations on average to get a valid one.

iSoron Wrote:

magamo Wrote:First, if my intuition is right, the probability that a cell gets a circle shouldn't be uniform.

You're absolutely right. JimmySeal's algorithm (and my implementation) is biased towards configurations with circles in the center. It's better to just generate random configurations and then check their validity. You'll have to generate ~5 configurations on average to get a valid one.

This new algorithm is biased towards circles in the corners, not through any fault of the algorithm, but because the problem itself is biased towards configurations with corner circles, for the reasons magamo stated.
In 100,000 iterations, this is how many times each cell occurs:
27901, 18679, 18492, 27777
18492, 9818, 10113, 18538
18478, 10127, 9934, 18677
28012, 18646, 18412, 27901

While your original algorithm gives:
24463, 18860, 18758, 24588
18788, 12842, 12701, 18842
18951, 12803, 12583, 18744
24738, 18844, 18775, 24717

Could you make it so each cell had an equal chance of being selected?

Blahah Wrote:Could you make it so each cell had an equal chance of being selected?

Is this close enough?

18373, 19239, 18999, 18232
18780, 18649, 18634, 19124
19142, 18677, 18543, 19166
18127, 18897, 19167, 18251

I think a more precise algorithm would be rather complicated; but maybe I'm wrong.

iSoron Wrote:

magamo Wrote:First, if my intuition is right, the probability that a cell gets a circle shouldn't be uniform.

You're absolutely right. JimmySeal's algorithm (and my implementation) is biased towards configurations with circles in the center. It's better to just generate random configurations and then check their validity. You'll have to generate ~5 configurations on average to get a valid one.

Or you could generate all possible sequences, and check each one.
There are 16 cells and you have choose 3 cells.

So there are "16 choose 3" possible configurations.
Generate them. Check each one. Store the good ones somewhere.
Pick a random one.

There are standard computer science algorithms to generate all possible configurations.
A lot of computer science problems involve just finding the right algorithm to use.

Also, since there are 16 cells, you can represent it as a 16-bit number.
Each bit would represent a circle.

So your list of valid configurations could just be a list of 16-bit numbers.

chamcham Wrote:So there are "16 choose 3" possible configurations.
Generate them. Check each one. Store the good ones somewhere.
Pick a random one.

8 lines in python. :whistle:

iSoron Wrote:

Blahah Wrote:Could you make it so each cell had an equal chance of being selected?

Is this close enough?

18373, 19239, 18999, 18232
18780, 18649, 18634, 19124
19142, 18677, 18543, 19166
18127, 18897, 19167, 18251

I think a more precise algorithm would be rather complicated; but maybe I'm wrong.

That seems to have handled it quite nicely. I don't really understand what's happening though: why is p an int in rnd()?

Code:

p = [0,1,1,2,2,3,3,3,3,3,3,3,3][randint(0,12)]

It looks to my n00b eyes like you've assigned two lists to p, and it magically ended up as the number 3.