Win a copy of Reactive Streams in Java: Concurrency with RxJava, Reactor, and Akka Streams this week in the Reactive Progamming forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Junilu Lacar
  • Jeanne Boyarsky
  • Bear Bibeault
Sheriffs:
  • Knute Snortum
  • Tim Cooke
  • Devaka Cooray
Saloon Keepers:
  • Ron McLeod
  • Stephan van Hulst
  • Tim Moores
  • Tim Holloway
  • Carey Brown
Bartenders:
  • Piet Souris
  • Frits Walraven
  • Ganesh Patekar

Easy programming problem, but head(and tail)-ache

 
Ranch Foreman
Posts: 266
12
IntelliJ IDE Firefox Browser Java
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?
the_problem_in_question.jpg
[Thumbnail for the_problem_in_question.jpg]
 
Ranch Hand
Posts: 125
1
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Bartender
Posts: 3509
150
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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!
           

 
D.J. Quavern
Ranch Foreman
Posts: 266
12
IntelliJ IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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:


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?
 
Piet Souris
Bartender
Posts: 3509
150
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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!
 
D.J. Quavern
Ranch Foreman
Posts: 266
12
IntelliJ IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?
 
Piet Souris
Bartender
Posts: 3509
150
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Use whatever makes you feel comfortable. Can you describe the treestructure?
 
D.J. Quavern
Ranch Foreman
Posts: 266
12
IntelliJ IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A root with (0,0). A right leaf with (1,0), then a left leaf with (0,1)... etc.
 
Piet Souris
Bartender
Posts: 3509
150
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I can see some problems with that, but do go ahead and let us know what your experiences are!
 
D.J. Quavern
Ranch Foreman
Posts: 266
12
IntelliJ IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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...")
_20190706_161111.JPG
[Thumbnail for _20190706_161111.JPG]
 
Piet Souris
Bartender
Posts: 3509
150
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?
 
Marshal
Posts: 14031
234
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Note that the input has constraints:

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


So you'll never have a case where you start with no tails or no heads.
 
D.J. Quavern
Ranch Foreman
Posts: 266
12
IntelliJ IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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!



And how do I get you a cow Piet?  
 
Sheriff
Posts: 24654
58
Eclipse IDE Firefox Browser MySQL Database
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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.
 
D.J. Quavern
Ranch Foreman
Posts: 266
12
IntelliJ IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you so much! My second cow Yooohooooo!
 
Marshal
Posts: 65772
250
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

D.J. Quavern wrote:. . . Yooohooooo!

It's Moooooooooooooooooohoooooooooooooo!

Well done
 
Piet Souris
Bartender
Posts: 3509
150
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@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.
 
Campbell Ritchie
Marshal
Posts: 65772
250
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Mentioned in despatches?

Congratulations For starting a thread quoted in the July 2019 CodeRanch Journal, you have been awarded a cow.
 
Get off me! Here, read this tiny ad:
Java file APIs (DOC, XLS, PDF, and many more)
https://products.aspose.com/total/java
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!