-2
\$\begingroup\$

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

\$\endgroup\$
  • 2
    \$\begingroup\$ Do we have to use T, TT, H, HH or can we use other values (such as 0 1 2 3)? \$\endgroup\$ – TFeld Apr 24 at 18:56
  • 6
    \$\begingroup\$ Please add test cases. \$\endgroup\$ – Jonah Apr 24 at 21:15
  • 7
    \$\begingroup\$ 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\$). \$\endgroup\$ – Lynn Apr 24 at 21:38
  • 4
    \$\begingroup\$ 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} $$ \$\endgroup\$ – Lynn Apr 24 at 21:46
  • 11
    \$\begingroup\$ 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? \$\endgroup\$ – xnor Apr 24 at 21:55
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Could you do it so the input is separated by a space not a comma? \$\endgroup\$ – user86525 Apr 24 at 21:29
  • \$\begingroup\$ 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. \$\endgroup\$ – Arnauld Apr 25 at 7:33
3
\$\begingroup\$

Python 2, 122 121 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!

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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

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

                         (3rd link)
³                        starting number of heads
 Ḃ                       mod 2
  Ḥ                      doubled
    +                    plus
   ⁴                     starting number of tails

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

                         (5th link)
Ø+                       [1, -1]
  Ż                      prepend 0 ([0, 1, -1])
   U                     reverse the array ([-1, 1, 0])
    Ż                    prepend 0 ([0, -1, 1, 0])
       ị                 index
     3£                  of the 3rd link
        +                plus
         1£              1st link
             +           plus
           ³H            half the number of heads

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

                         (Main link)
2£                       2nd link
  4£                     4th link
    ¢                    last link
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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
  ^
Heads

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.

\$\endgroup\$
0
\$\begingroup\$

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

Try it online or verify some more test cases.

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)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy