- Post Reply Bookmark Topic Watch Topic
- New Topic

this forum made possible by our volunteer staff, including ...

Marshals:

- Campbell Ritchie
- Liutauras Vilda
- Jeanne Boyarsky
- Devaka Cooray
- Paul Clapham

Sheriffs:

- Tim Cooke
- Knute Snortum
- Bear Bibeault

Saloon Keepers:

- Ron McLeod
- Tim Moores
- Stephan van Hulst
- Piet Souris
- Ganesh Patekar

Bartenders:

- Frits Walraven
- Carey Brown
- Tim Holloway

posted 2 weeks ago

- 1

Hello everyone!

I don't know how to approach this problem. I did a series of if-statements, trying to my way to the best moves (like, cutting heads as long as they are even). But more often then not I end up in an infinite loop, when it's not a false result! One of my typical tries:

**Can anyone help me out with a possible strategy?**

I don't know how to approach this problem. I did a series of if-statements, trying to my way to the best moves (like, cutting heads as long as they are even). But more often then not I end up in an infinite loop, when it's not a false result! One of my typical tries:

"If you lie to the computer, it will get you."

Favorite Granny's Wisdom Pearl

posted 2 weeks ago

- 2

Your interpretation of moves doesn't seem correct to me. Depending upon the existing heads and tails, you need to choose the move. And there are only 4 moves that you can choose.

Also, it's a dynamic programming question, I think. Because from the solution to the sample problem, it doesn't look like greedy solution will solve this.

Also, it's a dynamic programming question, I think. Because from the solution to the sample problem, it doesn't look like greedy solution will solve this.

posted 2 weeks ago

- 2

hi DJ,

nice problem! But I disagree: it is not as easy as you mention.

I agree with Salil that your strategy looks suspicious.

For instance: where do you check that you are not in an infinite loop situation? Suppose you have three Heads, you cut off two of them. So, one head left. Do you think there is a solution now? And what if there are five heads?

Suppose you have one Head and one Tail. Cutting of the Head leads to the same position. So, the way to go is to cut off one Tail, giving you two Tails, that can be cut off to get two Heads, and you're done.

Likewise, if you have one Head and three tails, you can cut off one tail to get four tails, leading to two tails and 2 Heads. A strategy would be:

H2 T2 ->

T2 ->

T3 ->

H1 T1 ->

H1 T2 ->

H2 ->

finished. Taking 5 moves.

So, we get:

1 H, 0 T -> no solution

1 H, 2 T -> 2 moves

1 H, 1 T -> cut the tail, you the get the above situation, so 1 + 2 = 3 Moves

et cetera.

I agree with Salil that it looks like dynamic programming. Build a map with basic situations, and denote the number of moves.

Then slowly enlarge your situations, see if you can get a situation that is already present in your table, and so you have a new solution.

Alternatively, you can try to derive some rules for the strategy-to-follow. For instance: if you have an odd number of Heads and no Tails, then there is no solution.

If you have any number of Heads, and one Tail, then cut off two Heads until one or zero Heads remain. We then have the situation (Head, Tail) = (0, 1) or (1, 1). (1, 1) has the above mentioned solution. What (if any) is the solution to (0, 1)?

Some food for thought. Succes!

nice problem! But I disagree: it is not as easy as you mention.

I agree with Salil that your strategy looks suspicious.

For instance: where do you check that you are not in an infinite loop situation? Suppose you have three Heads, you cut off two of them. So, one head left. Do you think there is a solution now? And what if there are five heads?

Suppose you have one Head and one Tail. Cutting of the Head leads to the same position. So, the way to go is to cut off one Tail, giving you two Tails, that can be cut off to get two Heads, and you're done.

Likewise, if you have one Head and three tails, you can cut off one tail to get four tails, leading to two tails and 2 Heads. A strategy would be:

H2 T2 ->

T2 ->

T3 ->

H1 T1 ->

H1 T2 ->

H2 ->

finished. Taking 5 moves.

So, we get:

1 H, 0 T -> no solution

1 H, 2 T -> 2 moves

1 H, 1 T -> cut the tail, you the get the above situation, so 1 + 2 = 3 Moves

et cetera.

I agree with Salil that it looks like dynamic programming. Build a map with basic situations, and denote the number of moves.

Then slowly enlarge your situations, see if you can get a situation that is already present in your table, and so you have a new solution.

Alternatively, you can try to derive some rules for the strategy-to-follow. For instance: if you have an odd number of Heads and no Tails, then there is no solution.

If you have any number of Heads, and one Tail, then cut off two Heads until one or zero Heads remain. We then have the situation (Head, Tail) = (0, 1) or (1, 1). (1, 1) has the above mentioned solution. What (if any) is the solution to (0, 1)?

Some food for thought. Succes!

posted 2 weeks ago

Thank you for your replies!

Also, I have no idea how dynamic programming is and works except what I just read on wiki. You say:

What are the base situations supposed to be? Does it starts at H:3 and T:3, and all combinatorics ? Or is it from H:2, T:2?

Also, I have no idea how dynamic programming is and works except what I just read on wiki. You say:

Build a map with basic situations, and denote the number of moves.

Then slowly enlarge your situations, see if you can get a situation that is already present in your table, and so you have a new solution.

What are the base situations supposed to be? Does it starts at H:3 and T:3, and all combinatorics ? Or is it from H:2, T:2?

"If you lie to the computer, it will get you."

Favorite Granny's Wisdom Pearl

Piet Souris

Saloon Keeper

Posts: 3297

146

posted 2 weeks ago

- 1

A sytematic way to produce all positions that have a solution is this:

Start with the position (0, 0) (= (H, T), that has a solution of 0 moves). Now, from what possible positions can we get to (0, 0), given the rules? The only way I can think of is from (2, 0). So, we can mark (2, 0) as having a solution of 1 move. From what positions can we arrive at (2, 0)? Well, (4, 0) and (1, 2). Et cetera, until we have tackled all (x, y) that are allowed according to the input specs.

A way to handle this growing number of 'predecessors' is to use a Queue. Having marked (0, 0) as having a solution of 0, put it in a Queue. Then, while the Queue is not empty or the (H, T) does not exceed the input specs, or as far as you like to go), pull the head of the queue, determine its predecessors, put these in the Queue, et cetera. It seems best to have a class for a position, containg fields for the number of Heads and the number of Tails, and a field that has the number of moves to (0, 0). You might also have a field that denotes the move(s) to make.

A crtiticism would be that you only derive positions that have a solution. What about positions that have no solution? Well, they simply do not appear in the list of solvable positions! But, I hear you say, I have solutions up to (100, 100), and (30, 21) is missing. Is that because it has indeed no solution, or has the solution not yet been reached? Would you, say, only find (30, 21) if we go to (300, 300)? Good question. What do you think? But I do not think you need to be worried about this!

Start with the position (0, 0) (= (H, T), that has a solution of 0 moves). Now, from what possible positions can we get to (0, 0), given the rules? The only way I can think of is from (2, 0). So, we can mark (2, 0) as having a solution of 1 move. From what positions can we arrive at (2, 0)? Well, (4, 0) and (1, 2). Et cetera, until we have tackled all (x, y) that are allowed according to the input specs.

A way to handle this growing number of 'predecessors' is to use a Queue. Having marked (0, 0) as having a solution of 0, put it in a Queue. Then, while the Queue is not empty or the (H, T) does not exceed the input specs, or as far as you like to go), pull the head of the queue, determine its predecessors, put these in the Queue, et cetera. It seems best to have a class for a position, containg fields for the number of Heads and the number of Tails, and a field that has the number of moves to (0, 0). You might also have a field that denotes the move(s) to make.

A crtiticism would be that you only derive positions that have a solution. What about positions that have no solution? Well, they simply do not appear in the list of solvable positions! But, I hear you say, I have solutions up to (100, 100), and (30, 21) is missing. Is that because it has indeed no solution, or has the solution not yet been reached? Would you, say, only find (30, 21) if we go to (300, 300)? Good question. What do you think? But I do not think you need to be worried about this!

posted 2 weeks ago

I guess I would use modulo to come to the desirable outcomes, but I did not visualise the solutions in a queue, but in a tree structure. Is it wrong?

"If you lie to the computer, it will get you."

Favorite Granny's Wisdom Pearl

Piet Souris

Saloon Keeper

Posts: 3297

146

posted 2 weeks ago

Use whatever makes you feel comfortable. Can you describe the treestructure?

posted 2 weeks ago

A root with (0,0). A right leaf with (1,0), then a left leaf with (0,1)... etc.

"If you lie to the computer, it will get you."

Favorite Granny's Wisdom Pearl

Piet Souris

Saloon Keeper

Posts: 3297

146

posted 2 weeks ago

I can see some problems with that, but do go ahead and let us know what your experiences are!

posted 2 weeks ago

Hello again!

My experiences have been very painful so far.

Can you please help me a bit more? I can't figure out how do I get to the right "optimal cases". I am really confused and my family is ignoring my grumbling ("three heads...one tail... fifty one tail... five heads...")

My experiences have been very painful so far.

Can you please help me a bit more? I can't figure out how do I get to the right "optimal cases". I am really confused and my family is ignoring my grumbling ("three heads...one tail... fifty one tail... five heads...")

"If you lie to the computer, it will get you."

Favorite Granny's Wisdom Pearl

Piet Souris

Saloon Keeper

Posts: 3297

146

posted 1 week ago

- 1

hi DJ,

well, having such a lovin'and understanding family is a great boon!

First of all: you might be forgiven to think that what we proposed, is like using a canon to shoot a mosquito. You could argue that, if there are no tails, the outcome will be decided by whether the heads are even or odd. If we have at leat one tail, we can expand that to any number of tails, and thus we can chop any number of heads accordingly. So, having one head and 51 ails, can you come up with a strategy that delivers you the number of moves as well?

But let's try the OOP approach a little. Your drawing looks daunting and a bit chaotic, so I can imagine you lost track of where you were going. I said that a tree structure would be good for some difficulties, but I wanted you to try it anyway, because I think it is a great way to expand your experience.

How do you present the possible situations of heads and tails? There are several ways. A simple way would be to have a 2D array headtail[x][y], with value the moves to succes. A headtail[x][y] with value -1 or so, would indicate no solution. Or you could use an existing class that has two integer fields, likeJava's Point and Dimension, and use a dictionary<Point, Integer>, where the value indicates the number of moves to succes.

But what about a class that represents all this? For instance the class HeadTail (I use Javacode here, because my Python knowledge is a little bit very rusty):

Now, set up a Queue<HeadTail> (I always use a LinkedList for that, I'm not sure what python has for this) and a Set<HeadTail> setOfAllHeadTails (a HashSet/dictionary would be nice).

Put HeadTail(0, 0, 0) in the queue and in result, and there goes:

while the queue is not empty

remove the head H

get H's predecessors

remove all predecessors already present in 'result'

remove all predecessors that have more heads and/or tails than according to specs

put the remaining predecessors back in the queue

It would be a bit tedious to create that Set for evey query that they will ask. As with HackerRank, can you edit the code so that you make this resultset static, i.e. so that you only need to create it once?

Last but by no means leasT;

see the 'determineSuccessors()' method in the HeadTail class. It says rhat when the number of Heads > 1 a successor would be HeadTail(head - 2, ...). Can you think of a situation where that is plain wrong?

well, having such a lovin'and understanding family is a great boon!

First of all: you might be forgiven to think that what we proposed, is like using a canon to shoot a mosquito. You could argue that, if there are no tails, the outcome will be decided by whether the heads are even or odd. If we have at leat one tail, we can expand that to any number of tails, and thus we can chop any number of heads accordingly. So, having one head and 51 ails, can you come up with a strategy that delivers you the number of moves as well?

But let's try the OOP approach a little. Your drawing looks daunting and a bit chaotic, so I can imagine you lost track of where you were going. I said that a tree structure would be good for some difficulties, but I wanted you to try it anyway, because I think it is a great way to expand your experience.

How do you present the possible situations of heads and tails? There are several ways. A simple way would be to have a 2D array headtail[x][y], with value the moves to succes. A headtail[x][y] with value -1 or so, would indicate no solution. Or you could use an existing class that has two integer fields, likeJava's Point and Dimension, and use a dictionary<Point, Integer>, where the value indicates the number of moves to succes.

But what about a class that represents all this? For instance the class HeadTail (I use Javacode here, because my Python knowledge is a little bit very rusty):

Now, set up a Queue<HeadTail> (I always use a LinkedList for that, I'm not sure what python has for this) and a Set<HeadTail> setOfAllHeadTails (a HashSet/dictionary would be nice).

Put HeadTail(0, 0, 0) in the queue and in result, and there goes:

while the queue is not empty

remove the head H

get H's predecessors

remove all predecessors already present in 'result'

remove all predecessors that have more heads and/or tails than according to specs

put the remaining predecessors back in the queue

It would be a bit tedious to create that Set for evey query that they will ask. As with HackerRank, can you edit the code so that you make this resultset static, i.e. so that you only need to create it once?

Last but by no means leasT;

see the 'determineSuccessors()' method in the HeadTail class. It says rhat when the number of Heads > 1 a successor would be HeadTail(head - 2, ...). Can you think of a situation where that is plain wrong?

posted 1 week ago

Note that the input has constraints:

So you'll never have a case where you start with no tails or no heads.

integers H and T (1≤ H,T ≤100)

So you'll never have a case where you start with no tails or no heads.

*Practice only makes habit, only perfect practice makes perfect.*—every music teacher ever
*Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

posted 1 week ago

Yeah one can say that !

Thank you, that actually clicked for me. I understood the point of doing modulo as long as I did not have the ideal solutions. Another problem is that I identified an ideal solution to break the loop as [0,1] instead of [0,2]. I got an infinite loop with test case [100,100].

There was a few technics that I was not aware of, so I could not implement the parts you left blank . I implemented something similar, and kept the "steps" principle, as it really clicked for me!

**And how do I get you a cow Piet? **

Piet Souris wrote:hi DJ,

well, having such a lovin'and understanding family is a great boon!

Yeah one can say that !

Piet Souris wrote:

First of all: you might be forgiven to think that what we proposed, is like using a canon to shoot a mosquito. You could argue that, if there are no tails, the outcome will be decided by whether the heads are even or odd. If we have at leat one tail, we can expand that to any number of tails, and thus we can chop any number of heads accordingly. So, having one head and 51 ails, can you come up with a strategy that delivers you the number of moves as well?

Thank you, that actually clicked for me. I understood the point of doing modulo as long as I did not have the ideal solutions. Another problem is that I identified an ideal solution to break the loop as [0,1] instead of [0,2]. I got an infinite loop with test case [100,100].

Piet Souris wrote:

But let's try the OOP approach a little. Your drawing looks daunting and a bit chaotic, so I can imagine you lost track of where you were going. I said that a tree structure would be good for some difficulties, but I wanted you to try it anyway, because I think it is a great way to expand your experience.

How do you present the possible situations of heads and tails? There are several ways. A simple way would be to have a 2D array headtail[x][y], with value the moves to succes. A headtail[x][y] with value -1 or so, would indicate no solution. Or you could use an existing class that has two integer fields, likeJava's Point and Dimension, and use a dictionary<Point, Integer>, where the value indicates the number of moves to succes.

But what about a class that represents all this? For instance the class HeadTail (I use Javacode here, because my Python knowledge is a little bit very rusty):

Now, set up a Queue<HeadTail> (I always use a LinkedList for that, I'm not sure what python has for this) and a Set<HeadTail> setOfAllHeadTails (a HashSet/dictionary would be nice).

Put HeadTail(0, 0, 0) in the queue and in result, and there goes:

while the queue is not empty

remove the head H

get H's predecessors

remove all predecessors already present in 'result'

remove all predecessors that have more heads and/or tails than according to specs

put the remaining predecessors back in the queue

It would be a bit tedious to create that Set for evey query that they will ask. As with HackerRank, can you edit the code so that you make this resultset static, i.e. so that you only need to create it once?

Last but by no means leasT;

see the 'determineSuccessors()' method in the HeadTail class. It says rhat when the number of Heads > 1 a successor would be HeadTail(head - 2, ...). Can you think of a situation where that is plain wrong?

There was a few technics that I was not aware of, so I could not implement the parts you left blank . I implemented something similar, and kept the "steps" principle, as it really clicked for me!

"If you lie to the computer, it will get you."

Favorite Granny's Wisdom Pearl

posted 1 week ago

I gave Piet a (well-deserved) cow on your behalf. And I gave you one, too, for posting such an interesting question.

- 2

D.J. Quavern wrote:

And how do I get you a cow Piet?

I gave Piet a (well-deserved) cow on your behalf. And I gave you one, too, for posting such an interesting question.

posted 1 week ago

Thank you so much! My second cow Yooohooooo!

"If you lie to the computer, it will get you."

Favorite Granny's Wisdom Pearl

posted 1 week ago
__M__oooooooooooooooooohoooooooooooooo!

Well done

It'sD.J. Quavern wrote:. . . Yooohooooo!

Well done

Piet Souris

Saloon Keeper

Posts: 3297

146

posted 1 week ago

- 1

@Paul

Thanks!

@DJ

It was a pleasure for me to help.

@Salil

And thank you for mentioning dynamic programming, I would never have come up with the idea.

Thanks!

@DJ

It was a pleasure for me to help.

@Salil

And thank you for mentioning dynamic programming, I would never have come up with the idea.

It is sorta covered in the JavaRanch Style Guide. |

- Post Reply Bookmark Topic Watch Topic
- New Topic

Boost this thread!