# 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)? Apr 24 '19 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 '19 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 '19 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 '19 at 21:55

# 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!

• I think this works for 104 bytes, but I'm not totally sure if it's guaranteed to find an optimal solution.
– user
Nov 28 '20 at 21:37
• @user This is indeed not optimal for, say, (4,1) which can be done in 4 moves. Nov 28 '20 at 23:23
– user
Nov 28 '20 at 23:31

# 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!

# 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 '19 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. Apr 25 '19 at 7:33

# 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, 201 bytes

@set/aa=%1,b=%2,c=(b+a+a)%%4
@if %1%c%==12 echo TT&set/ab-=a=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=4k\$$ (which requires an initial TT). Edit: Fixed second special case for $$\k>1\$$.

# Wolfram Language (Mathematica), 10491 77 bytes

-14 bytes thanks to @att

Table@@@Join[{H,b=1-#~Mod~2},{T,q=Mod[2-#2-b,4]},{TT,n=(#2+q)/2},HH|(#+n)/2]&


Try it online!

A 74 byte version, but can't be run in TIO, as it fakes Put. Put is the only valid operator with a higher precedence than Set, so it can be used in place of List in each pair, save a byte over each.

Table@@@Join[H>>b=1-#~Mod~2,T>>q=Mod[2-#2-b,4],TT>>n=(#2+q)/2,HH|(#+n)/2]&

• H takes (1,0) to (0,1), not (2,0). You can also use infix on the left side of Set.
– att
Nov 28 '20 at 22:10
• 77 bytes
– att
Nov 29 '20 at 7:55

# Java 8, 194167164163140 135 bytes

(h,t)->{for(;t>-h;)System.out.println(t+h%2<1&&h>(h-=2)?"HH":h<1&t%4<3|t%4==h%2*2&&h<++h&t>(t-=2)?"TT":t++%4!=3-h%2*2&&h>--h?"H":"T");}


-51 bytes thanks to @ceilingcat.

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:

(h,t)->{                // Method with two integer parameters and String return-type
for(;t>-h;)           //  Loop until both the amount of heads and tails are 0:
System.out.println( //   Print with trailing newline:
t+h%2<1&&         //    If there are 0 tails and an even amount of heads:
h>(h-=2)?       //     Decrease the amount of heads by 2
"HH"            //     And print "HH"
:h<1&t%4<3        //    Else if there are 0 heads and tails modulo 4 is 0, 1, or 2
|t%4==h%2*2&&    //    Or there is an even amount of heads and tails modulo 4 is 0
//    Or there is an odd amount of heads and tails modulo 4 is 2:
h<++h&          //     Increase the amount of heads by 1
t>(t-=2)?       //     Decrease the amount of tails by 2
"TT"            //     And print "TT"
:t++%4!=3-h%2*2&& //    Else-if there are an odd amount of heads and tails modulo-4 is NOT 1
//    Or there are an even amount of heads and tails modulo-4 is NOT 3:
//    (and increase t by 1 with t++ right after this check)
h>--h?          //     Decrease the amount of heads by 1
"H"             //     And print "H"
:                 //    Else:
"T");}          //     Print "T"


# APL (Dyalog Unicode), 91 79 bytes

Saved 1 byte thanks to @ovs

{⍺=-⍵:⍬⋄⍵>1:'TT ',(⍺+1)∇⍵-2⋄3=⍺+⍵:'H ',(⍺-1)∇⍵+1⋄1=⍺⌈⍵:'T ',⍺∇⍵+1⋄'HH ',⍵∇⍨⍺-2}


Try it online!

Here is my "research." The x-axis is heads, y-axis is tails. Each cell contains the minimum number of moves to get to (0, 0), and the optimal move(s) you can make from there. There are multiple ways you can divide it up, but I am going to hold t>=2 to be one section (TT); (2, 1) and (3, 0) to be another (H); (1, 0), (0, 1), and (1, 1) to be another (T), and the rest to be HH.

The first case is if the dragon has no heads or tails (h==-t), in which case we return the empty set (⍬).

As you can see, the optimal move if the dragon has 2 or more tails is a double tail-chop, and that is our second case. We prepend 'TT ' to the result of calling the function again with one more head and two less tails. ∇ refers to the current function, ⍺ is heads, and ⍵ is tails.

The third case is the single head chop. The only two times when the only option available is H is at (3,0) and (2,1). Our condition here is that h+t is 3 (this condition is also met with (1,2) and (0,3), but those were covered in the second case).

The third case is the single tail chop. Only one square requires it - (1, 1), so we check if the maximum of h and t is 1.

The last case doesn't need any condition checking, so we can go ahead and decapitate the dragon twice.

• 0=⍺+⍵ => ⍺=-⍵ for -1 byte
– ovs
Dec 14 '20 at 15:59
• @ovs Cool, thanks!
– user
Dec 14 '20 at 16:09
• How can the optimal move for 1 head, 0 tails be a tail chop? (Although I can't talk; my script outputs two head chops and a double tail chop...)
– Neil
Dec 17 '20 at 10:20
• Never mind, those rows don't make sense, as you're guaranteed at least one head and one tail.
– Neil
Dec 17 '20 at 12:28
• @Neil I didn't notice that! I should probably update it, even if it's a case that will never be reached.
– user
Dec 17 '20 at 14:05

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


# Scala, 154 147 bytes

a=>b=>{var(h,t,s)=(a,b,"")
while(-t<h)s+=(if(t>1){h+=1;t-=2
"TT "}else if(3==h+t){h-=1;t+=1
"H "}else if(2>h.max(t)){t+=1
"T "}else{h-=2
"HH "})
s}


Try it online!

Uses a completely different approach, but it's still longer than Java. :(

See my APL answer for an explanation.

### Previous solution, 182 bytes

h=>t=>{var m=Map(0->0->"")
while(!m.keySet(h->t)){for{g->s->p<-m
i->u->q<-Map(g+2->s->"HH",(g+1,s-1)->"H",(g,s-1)->"T",(g-1,s+2)->"TT")--m.keySet
if-1<i*u}m+=i->u->s"$q$p"}
m(h->t)}


Try it online!

Uses the pathfinding approach Lynn suggested in the comments.

# Python 3, 107 bytes

def f(a,b):return'TT '+f(a+1,b-2)if b>2else'HH '+f(a-2,b)if a>2else'H '+f(1,b+1)if a>1else'T TT HH'[2*b-2:]


Try it online!

The only way to reduce the tails is TT. You can safely do this as long as b > 2.

You can also safely reduce heads by HH as long as a > 2. I do this after reducing the tails, so it does not mix with TT operations.

When no more than 2 heads and tails are left, there are two cases:

1. a = 2: Cut off a head (H) then call recursively (with a = 1 now).
2. a = 1: Manually coded using a constant string.

# Java (JDK), 110 bytes

String f(int a,int b){return b>2?"TT "+f(a+1,b-2):a>2?"HH "+f(a-2,b):a>1?"H "+f(1,b+1):b>1?"TT HH":"T TT HH";}


Try it online!

# Perl 5, 102 bytes

sub f($a,$b){$b>2?"TT ".f($a+1,$b-2):$a>2?"HH ".f($a-2,$b):$a>1?"H ".f(1,$b+1):\$b>1?"TT HH":"T TT HH"}


Try it online!

6 Chars less due to hint by Dom Hastings.

• Nice! You can save 6 bytes with the flag -Mfeature+signatures (which changes the 'language' from Perl to Perl + -Mfeature+signatures instead of adding bytes) and using function signatures: Try it online! Dec 18 '20 at 10:38
• @Dom Hastings: Thank you for your hint! Dec 18 '20 at 10:45