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

[D.J. Quavern]

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:

head, tail = input().split(' ') head = int(head) tail = int(tail) moves = 0 while head > 0 or tail > 0:    if head >= 2:        head = head - 2        moves += 1    elif head == 1 and tail >= 2:        tail = tail - 2        head = head + 1        moves += 1    elif tail >= 2:        tail = tail - 2        head = head + 1        moves += 1    elif tail >= 1:        tail = tail + 1        moves += 1 print(moves)

Can anyone help me out with a possible strategy?

[Salil Wadnerkar]

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.

[Piet Souris]

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]

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]

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]

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]

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

[D.J. Quavern]

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

[Piet Souris]

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

[D.J. Quavern]

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...")

[Piet Souris]

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):

class HeadTail {
    final int heads;
    final int tails;
    final int movesToSolution;

    public HeadTail(int heads, int tails, int moves) {
        if (heads < 0 || tails < 0) throw new RuntimeException(
            "illegal arguments in constructor!!"
        );
        this.heads = heads;
        this.tails = tails;
        this.movesToSolution = moves;
    }

    public boolean hasSolution() {
        return movesToSolution >= 0;
    }

    public int movesToSolution() {
        return movesToSolution;
    }

    public List<HeadTail> determineSuccessors() {
        List<HeadTail> successors = new ArrayList<>();
        if (heads > 1) successors.add(
            new HeadTail(heads - 2, tails, movesToSolution - 1)
        );
        //et cetera       
        return successors;
    }

    public List<HeadTail> determinePredecessors() {
        // to implement
        return null;
    }

    @Override
    public boolean equals(Object o) {...}
    
    @Override
    public int hashCode() {...}
}

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?

[Junilu Lacar]

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]

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):

class HeadTail {
    final int heads;
    final int tails;
    final int movesToSolution;

    public HeadTail(int heads, int tails, int moves) {
        if (heads < 0 || tails < 0) throw new RuntimeException(
            "illegal arguments in constructor!!"
        );
        this.heads = heads;
        this.tails = tails;
        this.movesToSolution = moves;
    }

    public boolean hasSolution() {
        return movesToSolution >= 0;
    }

    public int movesToSolution() {
        return movesToSolution;
    }

    public List<HeadTail> determineSuccessors() {
        List<HeadTail> successors = new ArrayList<>();
        if (heads > 1) successors.add(
            new HeadTail(heads - 2, tails, movesToSolution - 1)
        );
        //et cetera       
        return successors;
    }

    public List<HeadTail> determinePredecessors() {
        // to implement
        return null;
    }

    @Override
    public boolean equals(Object o) {...}
    
    @Override
    public int hashCode() {...}
}

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!

while True:    [head, tail] = [int(x) for x in input().split(' ')]    if [head, tail] == [0, 0]:        break    moves = 0    while not ([head, tail] == [1, 1] or [head, tail] == [0, 2] or [head, tail] == [1, 0] or [head, tail] == [0, 0]):        if head >= 2:            moves = moves + 1            head = head - 2        elif tail >= 2:            moves = moves + 1            head = head + 1            tail = tail - 2        elif tail >= 1:            tail = tail + 1            moves = moves + 1    if [head, tail] == [1, 1]:        moves = moves + 3    elif [head, tail] == [0, 2]:        moves = moves + 5    elif [head, tail] == [1, 0]:        moves = -1    print(moves)

And how do I get you a cow Piet?  

[Paul Clapham]

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]

Thank you so much! My second cow Yooohooooo!

[Campbell Ritchie]

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

It's Moooooooooooooooooohoooooooooooooo!

Well done

[Piet Souris]

@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]

Mentioned in despatches?

Congratulations For starting a thread quoted in the July 2019 CodeRanch Journal, you have been awarded a cow.