4
\$\begingroup\$

Mary has given John two sticks of lengths a and b respectively, where a and b are positive integers.

John is very curious.

He would like to know how many triangles with integer perimeter can be formed, by having one additional side.

Please help him find it out.

(This is my first time composing this kind of stupid stories in coding problems, so forgive me if it is too stupid.)

Specs

  • Given two integers a and b, find the number of triangles with integer perimeter that can be formed, by having one additional side.

Details

  • Congruent triangles are congruent.
  • Flat triangles are flat out uncounted.
  • Zero-sided triangles are counted zero times.

Scoring

This is . Shortest solution in bytes wins.

Testcases

a b output
1 2 1
3 3 5
9 7 13
\$\endgroup\$
  • \$\begingroup\$ I like your wording. \$\endgroup\$ – Bálint May 1 '16 at 12:43
  • 1
    \$\begingroup\$ Also, is a full program needed or just a function? It makes a big difference in java. Even in javascript. \$\endgroup\$ – Bálint May 1 '16 at 12:46
  • 2
    \$\begingroup\$ @Bálint There are default rules for this. \$\endgroup\$ – Martin Ender May 1 '16 at 13:16
  • \$\begingroup\$ For a=1 and b=2, why can't I have two triangles, 1,1,2 and 1,2,2? \$\endgroup\$ – Neil May 1 '16 at 13:52
  • \$\begingroup\$ @Neil 1,1,2 is flat. \$\endgroup\$ – Leaky Nun May 1 '16 at 13:53

15 Answers 15

7
\$\begingroup\$

Jelly, 3 bytes

«Ḥ’

Try it online!

Explanation

«   min(a,b)
 Ḥ          *2
  ’           -1

(Not quite rigorous) proof of correctness:

  • Let x = min(a,b) and y = max(a,b), and let z be a potential third side.
  • We can't have z ≤ y-x, because for z < y-x the triangle can't be closed and for z = y-x it would be degenerate. See triangle inequality.
  • We can't have z ≥ y+x, for the same reasons.
  • Every integer z in between is valid and gives a different triangle. That means we've got (y+x) - (y-x) - 1 = 2x - 1 different triangles.
\$\endgroup\$
  • \$\begingroup\$ Could you please prove your algorithm? \$\endgroup\$ – Leaky Nun May 1 '16 at 13:03
  • \$\begingroup\$ Let's say we have a and b, and a>b. The minimum length triangle is a-b+1, the maximum length is a+b-1. The amount of triangles is maximum-minimum+1=a+b-1-(a-b+1)+1=2b-2+1=2b-1 \$\endgroup\$ – Bálint May 1 '16 at 13:11
  • \$\begingroup\$ Could you at least cite the triangle inequality? :) \$\endgroup\$ – Leaky Nun May 1 '16 at 13:14
  • 1
    \$\begingroup\$ @KennyLau If you insist... \$\endgroup\$ – Martin Ender May 1 '16 at 13:15
4
\$\begingroup\$

CJam, 7 bytes

l~e<2*(

Test it here.

Explanation

l~  e# Read and evaluate input.
e<  e# min(a,b).
2*  e# Double.
(   e# Decrement.

For a proof of correctness, see my Jelly answer which uses the same algorithm.

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

05AB1E, 3 bytes

Using @MartinBüttner's algorithm. Code:

·<ß

Explanation:

·    # Double the input.
 <   # Decrement by 1.
  ß  # Take the smallest value.

Uses CP-1252 encoding. Try it online!.

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

Retina, 14 bytes

M!`(1+) \1
 1

Input and output in unary.

Try it online! (Modified to run multiple decimal test cases at once.)

Explanation

Still the same approach as my CJam and Jelly answers (the latter contains a proof of correctness), but this time using string processing of unary representations.

M!`(1+) \1

This finds min(a,b) by matching the first string of 1s that can be found in both of them. This being a match stage and using the ! the result is actually min(a,b) min(a,b) since the entire match is written back.

 1

This simply matches the separating a space and a single 1 and removes them. This leaves a string of 2*min(a,b) - 1 characters, which is the desired result.

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

Labyrinth, 20 bytes

Thanks to Sp3000 for some help while golfing this.

<""-}:?:?
"`
{
++(!@

Try it online!

Explanation

It turns out that the 2*min(a,b)-1 approach isn't the shortest in Labyrinth. Instead it's easier to compute (a+b)-|a-b|-1.

Labyrinth primer:

  • Labyrinth has two stacks of arbitrary-precision integers, main and aux(iliary), which are initially filled with an (implicit) infinite amount of zeros. I will usually represent these like Main [... a b | c d ...] Aux, where Main grows to the right, Aux grows to the left and ... represents the implicit zeros at the bottom.
  • The source code resembles a maze, where the instruction pointer (IP) follows corridors when it can (even around corners). The code starts at the first valid character in reading order, i.e. in the top left corner in this case. When the IP comes to any form of junction (i.e. several adjacent cells in addition to the one it came from), it will pick a direction based on the top of the main stack. The basic rules are: turn left when negative, keep going ahead when zero, turn right when positive. And when one of these is not possible because there's a wall, then the IP will take the opposite direction. The IP also turns around when hitting dead ends.
  • The source code can be modified at runtime using <>^v which cyclically shift a row or column of the grid.

The code starts on the < which immediately modifies the source code. This is a common golfing trick in Labyrinth whenever a program starts with a long-ish bit of linear code. Afterwards, the source looks like this, with the IP still on the <:

""-}:?:?<
"`
{
++(!@

Since the IP is now in a dead end, it has to start moving left. The linear code does the following:

Op      Explanation                    Stacks
?       Read integer a from STDIN.     Main [... a | ...] Aux
:       Duplicate.                     Main [... a a | ...] Aux
?       Read integer b from STDIN.     Main [... a a b | ...] Aux
:       Duplicate.                     Main [... a a b b | ...] Aux
}       Move b over to aux.            Main [... a a b | b ...] Aux
-       Subtract b from a on main.     Main [... a (a-b) | b ...] Aux

The code now enters the only nonlinear part of the code which compues -abs(x), (where I'm now using < and v to indicate entry and exit points):

""<
"`
v

The " is a no-op (i.e. it does nothing), whereas the ` multiplies the top of the main stack by -1. Let's go through the three possible cases of control flow:

  • If a == b, i.e. a-b is zero, the IP keeps moving west on the first ". Then it hits a corner on the the second " and has to turn south. Again, it keeps moving south on the third " and leaves this 2x2 block. All in all, nothing happens to zeros at all.
  • If a > b, i.e. a-b is positive, the IP turns south on the first ". The ` then switches the top of the main stack to b-a and the IP has to take a turn west. On the next " the top of the stack is now negative, and the IP turns south. Therefore, if the top of the stack is positive, its sign will be negated by this block.
  • If a < b, i.e. a-b is negative, then the IP also turns towards the ` , which now makes it positive. That means the IP turns north on the next no-op. It hits the corner and turns east, and turns south once more so that it reaches the ` a second time. At this point, the control flow is no different from a positive input, so after applying ` twice, we're back at a-b which is negative and leaves the loop. Despite doing a lot more stuff, negative inputs are also unaffected by this part of the code.

Now that we've computed -abs(a-b), the remainder of the code is all linear again:

Op      Explanation                    Stacks
                                       [... a -|a-b| | b ...]
{       Move b back to main.           [... a -|a-b| b | ...]
+       Add.                           [... a (-|a-b|+b) | ...]
+       Add.                           [... (a+b-|a-b|) | ...]
(       Decrement.                     [... (a+b-|a-b|-1) | ...]
!       Print as integer.              [... | ...]
@       Terminate program.
\$\endgroup\$
2
\$\begingroup\$

Cubix, 18 19 bytes

Not overly short, but a tad more interesting to do due to a lack of a minimum function.
Saved a byte with a big thanks to Martin Büttner

-@IOIU>wu+..U;?;2*

This wraps onto a cube with edge length 2 and ends up looking like this

    - @
    I O
I U > w u + . .
U ; ? ; 2 * . .
    . .
    . .

Explanation that hopefully can be followed. Try it here

Getting parameters from STDIN

    -                # This section gets input, u-turns onto top face,
    I                # heading up, gets another input and performs a subtraction.
I U                  # Carries on around the bottom of the cube upto the next part.

Determine least and leaving it at TOS

    > w              # Hits the ? going up.  if TOS is negative turn left, pop stack
U ; ? ;              # and U-turn onto bottom face heading back up to ?.  
    .                # If 0 redirect through > and w to ; popping stack, heading right.  
    .                # If positive redirect right to ; which pops TOS

Output the answer and end

      @              # Push 2 onto the stack, multiply, U-turn onto input which
      O              # gives us -1 for the stack, add it then u-turn to the left 
I       u +          # onto the top face, output the TOS as number and end
U       2 * 
\$\endgroup\$
  • \$\begingroup\$ -@IOIU>wu+..U;?;2* saves a byte. \$\endgroup\$ – Martin Ender May 3 '16 at 7:29
  • \$\begingroup\$ @MartinBüttner Thank you very much. Beautiful use of the input to get the -1. I would never have thought of that. \$\endgroup\$ – MickyT May 3 '16 at 8:19
1
\$\begingroup\$

k (8 bytes)

Using the Jelly/CJam algorithm

-1+2*min

e.g.

k)-1+2*(&). 10 10
19
\$\endgroup\$
1
\$\begingroup\$

Java 55 42 bytes

int c(int a,int b){return (a<b?a:b)*2-1);}
\$\endgroup\$
  • 1
    \$\begingroup\$ Java has lambdas; use them to save bytes! :) \$\endgroup\$ – Leaky Nun May 1 '16 at 13:26
1
\$\begingroup\$

APL, 6 bytes

1-⍨2×⌊

This is a dyadic function train that accepts integers on the right and left and returns an integer. It uses the 2 min(a, b) - 1 approach.

Try it here (includes all test cases)

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

Javascript full program 88 42 bytes

a=prompt();b=prompt();alert((a<b?a:b)*2-1)

I hate prompts, even java is better in that aspect.

Javascript function 73 31 21 bytes

(a,b)=>(a<b?a:b)*2-1

Testable version:

c=(a,b)=>(a<b?a:b)*2-1

var d = prompt("enter first number");
var e = prompt("enter second number");
alert(c(d, e));

Thanks to @Neil for saving 8 bytes. Thanks goes to @MartinBüttner for the algorithm and for saving 1 byte.

\$\endgroup\$
  • \$\begingroup\$ I'll add an answer in java then. (Java is my first language actually...) \$\endgroup\$ – Leaky Nun May 1 '16 at 12:48
  • \$\begingroup\$ What's the space doing in max=a- -b-1;? \$\endgroup\$ – Leaky Nun May 1 '16 at 12:48
  • \$\begingroup\$ Why not use a lambda? You can always use functions instead of full programs unless explicitly forbidden. \$\endgroup\$ – Denker May 1 '16 at 12:48
  • \$\begingroup\$ @DenkerAffe I always work on full programs before going on to lamdas, I did that one too. \$\endgroup\$ – Bálint May 1 '16 at 12:51
  • \$\begingroup\$ @KennyLau If I don't put it there, it throws a syntax error, as -- is the decrement operator. doing a- -b casts both of them to numbers, then subtracts the negative of b from a, thus it's doing the same as adding it. \$\endgroup\$ – Bálint May 1 '16 at 12:52
1
\$\begingroup\$

Actually, 3 bytes

mτD

Try it online or verify all test cases at once

This uses the same 2*min(a,b)-1 approach that basically every other solutions uses. Each operation (minimum, double, decrement) is its own single-byte command.

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

J, 7 bytes

1-~2*<.

This is a tacit verb.

1-~2*<.
1-~      reflexive minus (i.e. R - 1)
   2*    double
     <.  lesser of
\$\endgroup\$
1
\$\begingroup\$

Jolf, 4 bytes

m±♀j

Replace ♀ with a literal \x12 byte, or try it here!

Explanation

m±♀j
  ♀j  min of j and implicit input
m±    2*(^)-1
\$\endgroup\$
0
\$\begingroup\$

PHP 36 bytes

function($a,$b){echo min($a,$b)*2-1}

Thanks goes to @MartinBüttner for the algorithm

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

C# 6.0 - 34 bytes

int a(int b,int c)=>(b<c?b:c)*2-1;
\$\endgroup\$
  • \$\begingroup\$ Wow, C# has lambdas?! :o \$\endgroup\$ – Leaky Nun May 2 '16 at 6:37
  • \$\begingroup\$ Unbalanced parentheses... \$\endgroup\$ – Leaky Nun May 2 '16 at 6:37
  • \$\begingroup\$ @KennyLau Thanks for telling. It's fixed now :). And yes, C# does have lambdas. C# 6.0 allows named functions to have an lambda expressions their bodies. This saved me from using the 'return' keyword and brackets. \$\endgroup\$ – Yytsi May 2 '16 at 18:54

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.