# Kill The Dragon!

John, a knight wants to kill a dragon to escape the castle! The dragon has A heads and B tails.

He knows, that:

• if you cut off one tail, two new tails grow
• if you cut off two tails, one new head grows
• if you cut off one head, one new tail grows
• if you cut off two heads, nothing grows

To defeat the dragon, John needs to cut off all his heads and all his tails. Help the knight to do this by making no more than 1000 strikes.

Input

The input contains two integers A and B (1 ≤ A, B ≤ 100).

Output

Print the sequence of strikes in the order in which they should be performed by encoding them with the following combinations of letters: T (one tail), TT (two tails), H (one head), HH (two heads) in the most optimal order.

Example

3 1

T
TT
HH
HH


The winning condition is the least number of bytes!

UPDATE: Bounty on offer for answers with Python

• Do we have to use T, TT, H, HH or can we use other values (such as 0 1 2 3)? – TFeld Apr 24 at 18:56
• This is basically pathfinding from $(a, b)$ to $(0, 0)$ on a $\mathbb{N}^2$ grid, where the valid moves are $\{(0,1),(1,-2),(-1,1),(-2,0)\}$ (with a minor caveat: you can't make the first move at $b=1$). – Lynn Apr 24 at 21:38
• Visually, these are the steps you can make ("more tails" is $\uparrow$, "more heads" is $\rightarrow$, you're trying to go $\swarrow$): $$\begin{bmatrix}\cdot&\cdot&\cdot&\cdot&\cdot\\\cdot&\text{H}&\text{T}&\cdot&\cdot\\\text{HH}&\cdot&\text{you}&\cdot&\cdot\\\cdot&\cdot&\cdot&\cdot&\cdot\\\cdot&\cdot&\cdot&\text{TT}&\cdot\end{bmatrix}$$ – Lynn Apr 24 at 21:46
• I see this problem appears as brain teaser on other sites such as this one, and it seems to be originally from a book of brainteasers. Do you have the author's permission to post it? – xnor Apr 24 at 21:55

# Python 2, 121 bytes

Outputs to stderr, tries all possible sequences until the first one succeeds.

r=[([],)+input()]
for s,h,t in r:h==t==0>exit(s);r+=[(s+['HT'[i/9]*(2-i%2)],h+i/4-2,t+i%4-2)for i in 11,12,7,2 if h>-1<t]


Try it online!

I don't think the if h>-1<t part is necessary, without it it would be 111 bytes.

• Could you do it so the input is separated by a space not a comma? – user86525 Apr 24 at 21:29
• Without h>-1<t, I think the algorithm will always find a solution with the correct length. It may however result in negative heads or tails (e.g. 2,1 -> ['TT', 'H', 'HH']) and would therefore be invalid. – Arnauld Apr 25 at 7:33

# Python 2, 122121 117 bytes

def f(a,b):x=a+b/2;b+=1;return b%2*x%2and['H']+a%2*['TT']+f(a-~a%2,b-a%2*2)or~b%2*['HT'[x%2]]+b/2*['TT']+-~x/2*['HH']


Try it online!

# JavaScript (ES6),  136  134 bytes

Takes input as (heads)(tails). Naive brute force search.

h=>F=(t,x=0)=>(g=(h,t,p=[],i=-6)=>h|t?h<0|t<0||p[x]?0:['HH','H','T','TT'].some(m=>g(h+i+4,i++%5%4-~t,[...p,m]))&&P:P=p)(h,t)||F(t,x+1)


Try it online!

# Jelly, 71 bytes

⁴HḞ
“TT¶”ẋ¢
³ḂḤ⁴+
“H¶TT¶“H¶H¶TT¶“T¶TT¶“”¢ị
Ø+ŻUŻ3£ị+1£+³H
“HH¶”ẋ¢
2£4£¢


Try it online!

I'm quite new to Jelly, so this is not optimal, but here's my explanation:

                         (1st link)
⁴                        starting number of tails
H                       halved
Ḟ                      and floored

“TT¶”                    take the string "TT\n"
ẋ¢                  and repeat it (last link) amount of times

Ḃ                       mod 2
Ḥ                      doubled
+                    plus
⁴                     starting number of tails

“H¶TT¶“H¶H¶TT¶“T¶TT¶“”   array of actions
¢  based on the last link
ị get the (n % len(array))th element

Ø+                       [1, -1]
Ż                      prepend 0 ([0, 1, -1])
U                     reverse the array ([-1, 1, 0])
Ż                    prepend 0 ([0, -1, 1, 0])
ị                 index
+                plus
+           plus
³H            half the number of heads

“HH¶”                    take the string "HH\n"
ẋ¢                  repeat it (last link) amount of times



## Batch, 199 bytes

@set/aa=%1,b=%2,c=(b+a+a)%%4
@if %1%2==14 echo TT&set/aa=b=c=2
@if %c%==3 echo T&set/ab+=1,c=0
@set/ab+=c,a+=b/2-c,c+=c
@for %%v in (%c%.H %b%.TT %a%.HH)do @for /l %%i in (2,2,%%~nv)do @echo%%~xv


Works by directly calculating the number of H, TT and HH strikes required. This handles all cases except where $$\2a+b\equiv3\pmod4\$$ (which requires an initial T) and the case $$\a=1,b=4\$$ (which requires an initial TT).

# Java 8, 194 bytes

(h,t)->{var r="";for(;h+t>0;)if(t+h%2<1){r+="HH ";h-=2;}else if(h<1&t%4<3||h%2<1&t%4<1||h%2>0&t%4==2){r+="TT ";t-=2;h++;}else if(h%2<1?t%4>2:t%4==1){r+="T ";t++;}else{r+="H ";h--;t++;}return r;}


Try it online.

Explanation:

I first tried all possible cases by hand:

Heads     Tails        Steps

1 (odd)   5 (%4==1)    1,5 → T(1,6) TT(2,4) TT(3,2) TT(4,0) HH(2,0) HH(0,0)
1 (odd)   6 (%4==2)    1,6 → see above after first step

2 (even)  6 (%4==2)    2,6 → H(1,7) H(0,8) TT(1,6) TT(2,4) TT(3,2) TT(4,0) HH(2,0) HH(0,0)
1 (odd)   7 (%4==3)    1,7 → see above after first step

3 (odd)   8 (%4==0)    3,8 → H(2,9) H(1,10) TT(2,8) TT(3,6) TT(4,4) TT(5,2) TT(6,0) HH(4,0) HH(2,0) HH(0,0)
2 (even)  9 (%4==1)    2,9 → see above after first step

2 (even)  7 (%4==3)    2,7 → T(2,8) TT(3,6) TT(4,4) TT(5,2) TT(6,0) HH(4,0) HH(2,0) HH(0,0)
2 (even)  8 (%4==0)    2,8 → see above after first step

0 (zero)  6 (%4==2)    0,6 → TT(1,4) H(0,5) TT(1,3) H(0,4) TT(1,2) TT(2,0) HH(0,0)
0 (zero)  5 (%4==1)    0,5 → see above after second step
0 (zero)  4 (%4==0)    0,4 → see above after fourth step

0 (zero)  7 (%4==3)    0,7 → T(0,8) TT(1,6) TT(2,4) TT(3,2) TT(4,0) HH(2,0) HH(0,0)

5 (odd)   0 (zero)     5,0 → H(4,1) H(3,2) TT(4,0) HH(2,0) HH(0,)
4 (even)  0 (zero)     4,0 → see above after third step


After that I knew the first moves for every possibility. Which I displayed here in table form:

      | 0   %4==0    %4==1    %4==2    %4==3  < Tails
------|-------------------------------------
0     | -   TT       TT       TT       T
%2==0 | HH  TT       H        H        T
%2==1 | H   H        T        TT       H
^


As for my code:

(Assumes the parameters are always positive, which fortunately enough is also true for the challenge.)

(h,t)->{                 // Method with two integer parameters and String return-type
var r="";              //  Result-String, starting empty
for(;h+t>0;)           //  Loop until both the amount of heads and tails are 0:
if(t+h%2<1){         //   If there are 0 tails and an even amount of heads:
r+="HH ";          //    Append "HH " to the result-String
h-=2;}             //    Decrease the amount of heads by 2
else if(h<1&t%4<3    //   Else if there are 0 heads and tails modulo 4 is 0, 1, or 2
||h%2<1&t%4<1    //   Or there is an even amount of heads and tails modulo 4 is 0
||h%2>0&t%4==2){ //   Or there is an odd amount of heads and tails modulo 4 is 2:
r+="TT ";          //    Append "TT " to the result-String
t-=2;              //    Decrease and amount of tails by 2
h++;}              //    And increase the amount of heads by 1
else if(h%2<1?       //   Else-if there an are even amount of heads
t%4>2       //   and tails modulo-4 is 3:
:            //   Or there are an odd amount of heads
t%4==1){    //   and tails modulo-4 is 1:
r+="T ";           //    Append "T " to the result-String
t++;}              //    Increase the amount of tails by 1
else{                //   Else:
r+="H ";           //    Append "H " to the result-String
h--;               //    Decrease the amount of heads by 1
t++;}              //    And increase the amount of tails by 1
return r;}             //  After the loop, return the result-String


The H-check would have been 1 byte longer than the TT-check, which is why it's used as the else-statement: h%2>0&t%4<1||h%2<1&-~t%4>1||h%2+t%4>4.

# 05AB1E, 75 71 bytes

[UVXY+_#XÈY_*i„HHYXÍëY4%©X_i3‹ëXÈi_ë2Q}}i„TTYÍX>ë®XÈi3Q}i'TY>Xë'HY>X<]»


Port of my Java answer. Can definitely be golfed, though (probably by using a different approach all-together more suitable to 05AB1E..)

Explanation:

[                  # Start an infinite loop:
U                 #  Pop and save the top of the stack (or the first (implicit) input
#  in the first iteration) in variable X (the heads)
V                 #  Pop and save the top of the stack (or the second (implicit) input
#  in the first iteration) in variable Y (the tails)
XY+_              #  If the amount of heads and tails are both 0:
#             #   Stop the infinite loop
XÈ   i            #  If there is an even amount of heads
Y_*             #  and there are 0 tails:
„HH         #   Push "HH" to the stack
Y           #   Leave Y the same
XÍ          #   Decrease X by 2
ë                 #  Else:
Y4%              #   Push tails modulo-4 to the stack
©             #   (and add it to the register without popping as well)
X_i          #   If there are 0 heads:
3‹        #    Check if tails modulo-4 is 0, 1, or 2
ëXÈi         #   Else-if there are an even amount of heads (but not 0)
_        #    Check if tails modulo-4 is 0
ë            #   Else (there are an odd amount of heads)
2Q          #    Check if tails modulo-4 is 2
}}i     #   And if it is truthy:
„TT  #    Push "TT" to the stack
YÍ   #    Decrease Y by 2
X>   #    Increase X by 1
ë                 #   Else:
®                #    Push tails modulo-4 to the stack again (from the register)
XÈi             #    If there are an even amount of heads:
3Q           #     Check if tails modulo-4 is 3
}i         #    If this is truthy or tails modulo-4 is 1:
'T      '#     Push "T" to the stack
Y>       #     Increase Y by 1
X        #     Leave X the same
ë                 #    Else:
'H              '#     Push "H" to the stack
Y>               #     Increase Y by 1
X<               #     Decrease X by 1
]                  # After all if-else statements and the loop:
»                 # Join everything on the stack by newlines
# (which is output implicitly as result)