7
\$\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\$
12
  • 3
    \$\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, 2019 at 18:56
  • 6
    \$\begingroup\$ Please add test cases. \$\endgroup\$
    – Jonah
    Apr 24, 2019 at 21:15
  • 11
    \$\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, 2019 at 21:38
  • 5
    \$\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, 2019 at 21:46
  • 12
    \$\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, 2019 at 21:55

13 Answers 13

5
\$\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\$
3
  • \$\begingroup\$ I think this works for 104 bytes, but I'm not totally sure if it's guaranteed to find an optimal solution. \$\endgroup\$
    – user
    Nov 28, 2020 at 21:37
  • \$\begingroup\$ @user This is indeed not optimal for, say, (4,1) which can be done in 4 moves. \$\endgroup\$
    – Arnauld
    Nov 28, 2020 at 23:23
  • \$\begingroup\$ Oh, that's too bad. \$\endgroup\$
    – user
    Nov 28, 2020 at 23:31
5
\$\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\$
4
\$\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\$
2
  • \$\begingroup\$ Could you do it so the input is separated by a space not a comma? \$\endgroup\$
    – user86525
    Apr 24, 2019 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, 2019 at 7:33
4
\$\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\$
4
\$\begingroup\$

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\$.

\$\endgroup\$
3
\$\begingroup\$

Wolfram Language (Mathematica), 104 91 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]&
\$\endgroup\$
2
  • \$\begingroup\$ H takes (1,0) to (0,1), not (2,0). You can also use infix on the left side of Set. \$\endgroup\$
    – att
    Nov 28, 2020 at 22:10
  • \$\begingroup\$ 77 bytes \$\endgroup\$
    – att
    Nov 29, 2020 at 7:55
3
\$\begingroup\$

Java 8, 194 167 164 163 140 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
  ^
Heads

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"
\$\endgroup\$
0
3
+100
\$\begingroup\$

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. enter image description here

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.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ 0=⍺+⍵ => ⍺=-⍵ for -1 byte \$\endgroup\$
    – ovs
    Dec 14, 2020 at 15:59
  • \$\begingroup\$ 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...) \$\endgroup\$
    – Neil
    Dec 17, 2020 at 10:20
  • \$\begingroup\$ Never mind, those rows don't make sense, as you're guaranteed at least one head and one tail. \$\endgroup\$
    – Neil
    Dec 17, 2020 at 12:28
  • \$\begingroup\$ @Neil I didn't notice that! I should probably update it, even if it's a case that will never be reached. \$\endgroup\$
    – user
    Dec 17, 2020 at 14:05
1
\$\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\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 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! \$\endgroup\$ Dec 18, 2020 at 10:38
  • 1
    \$\begingroup\$ @Dom Hastings: Thank you for your hint! \$\endgroup\$
    – Donat
    Dec 18, 2020 at 10:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.