reset password
Author Message
fumjum
Posts: 27
Posted 12:39 Nov 01, 2019 |

How do we tell if a problem from the website is easy, medium, hard, or difficult? I didn't see any indication in the puzzle description at first glance.

justinch0w
Posts: 5
Posted 12:58 Nov 01, 2019 |

I believe it is self evaluation. Choose the estimated difficulty for the puzzle you choose.

fumjum
Posts: 27
Posted 13:05 Nov 01, 2019 |

Ok thanks.

rabbott
Posts: 1649
Posted 13:15 Nov 01, 2019 |

That's a good question. You might look at the size of the state space as a function of the size of the input. For example, Wolf-Goat-Cabbage has a state space of 2^n, where n is the number of things that have to be transported across the river. The n-jugs problem has a state space of approximately k^n where k is the size of the largest jug. (This is similar in form to to WGC.)

On the other hand, the n-puzzle has a state space of n! (Normally n is 8 or 15.)  n! has a very rough approximation of n^n, which grows much faster than k^n.

Light's Out is 2^(n*n), which is somewhere in between the previous two.

Planning problems involve finding a path through a state space. So the size of the state space is not really the size of the problem. A space of paths would be of size s^n where n is the number of states and n is the maximum of steps. If there is no limit, it could be at worst s^s.

These are all worst-case estimates, but they may help get a sense of the problem difficulty if you were to try to solve it using some sort of brute force enumeration. 

I would also suggest playing with the problem and getting a feel for how one might solve it by brute force enumeration and see what that looks like.

iamrajakumar
Posts: 9
Posted 15:53 Nov 01, 2019 |

It is still not clear on the boundary on how to choose easy vs medium vs hard.

Can you define limits for those s^n like

Easy is < 250 (Considering Farmer Boat (WGC) problem is 2 ^ 3 = 8)

Medium is between 250 and 1000 (inclusive)

Hard is >1000

**Feel free to change the numbers but we would like to define a boundary that helps us choose and define the difficulty of the problems we choose. That will help us plan for 3 points.

And also wanted to know if we solve sub puzzles of the same problem given on that website and solve all of them in a general way then is it counted.

Eg. For FourSum problem there are 6 puzzle in the given website. And if we solve all 6 of them in a general way with different puzzle inputs is that considered as the (s^n) * 6 where 6 is the no. of puzzles solved on that problem in the given website. Is that the case or just the s ^ n should be counted.

Link to FourSum: https://www.transum.org/Software/SW/Starter_of_the_day/Students/Hot/FourSum.asp

For FouSum problem : s = 4, n = 4 and no. of puzzle is 6. Thus (4 ^ 4) * 6 = 256 * 6 = 1536 

or 

should only take 4 ^ 4 as 256.

 

By defining the counts, it will be very easy for us to calculate and know the difficulty better and plan for the points.