# Counting shortest paths on a triangular grid

## Background

An Eisenstein integer is a complex number of the form $$\ z = a + b\omega \$$ where $$\a, b\$$ are integers and $$\\omega\$$ is the third root of unity $$\\frac{1-\sqrt3i}{2}\$$. The Eisenstein integers can be viewed as the triangular lattice points, as shown in the image below (from Wikipedia):

Following the triangular grid, one step of movement can be done in six directions:

$$\begin{array}{r|r} \text{Direction} & \text{Step} \\ \hline E & 1 \\ NE & 1 + \omega \\ NW & \omega \\ W & -1 \\ SW & -1 - \omega \\ SE & -\omega \end{array}$$

Given an Eisenstein integer $$\z\$$, count all shortest paths from the origin ($$\0\$$) to the point equivalent to $$\z\$$ on the triangular grid.

Since $$\z = a + b \omega\$$ can be represented by two integers $$\ a, b \$$, you can take the input as two integers $$\a, b\$$ in any consistent order and structure of your choice.

One way to compute this is (thanks to @xnor):

Take the absolute values of [a, b, a-b], and call it L
Calculate binomial(max(L), any other value in L)


## Test cases

 a  b  ans
0  0    1
2  0    1
5  3   10
4  4    1
2  3    3
0  2    1
-2  2    6
-4  0    1
-5 -3   10
-1 -1    1
-3 -5   10
0 -3    1
4 -1    5
-4 -9  126
7 -4  330
8  1    8
3 -3   20

• Can you point me to an explanation of this? Take the absolute values of [a, b, a-b], and call it L. Calculate binomial(max(L), any other value in L) Commented Apr 12, 2020 at 10:13
• @jonrandy First convince yourself that it's true for points in the first quadrant, using a combinatorial argument. Then, for points elsewhere in the plane, use the fact that the value for that point is the same as the value for the three other points symmetrically located about the origin. If $a+b\omega$ is the first point, those other three points are $-a-b\omega, b-a+b\omega,$ and $a-b-b\omega.$ Commented Apr 12, 2020 at 15:05

# Wolfram Language (Mathematica), 38 bytes

Max[l=Abs@{#,#2,#-#2}]~Binomial~Min@l&


Try it online!

# Jelly, 7 bytes

;IAṀc$Ṁ  Try it online! ### How? ;IAṀc$Ṁ - Link: list of two integers   e.g. [-4, -9]
I      - incremental differences           [-5]           (since -9 - -4 = -5)
;       - concatenate                       [-4, -9, -5]
A     - absolute values                   [4, 9, 5]
Ṁ    -   maximum                         9
c   -   choose (vectorises)             [126, 1, 126]  (9c4=9c5=126 and 9c9=1)
Ṁ - maximum                           126


# Python 3.8, 69 68 bytes

Saved a byte thanks to newbie!!!

lambda a,b:math.comb(*sorted(map(abs,[a,b,a-b]))[2::-2])
import math


Try it online!

• -1 byte Commented Apr 12, 2020 at 10:34
• @newbie Jump to the end. Nice one - thanks! :-) Commented Apr 12, 2020 at 11:35

# APL (Dyalog), 13 12 bytes

1 byte saved thanks to @ngn!

(⌊/!⌈/)∘|,,-


Try it online!

• ( )(f g h i) -> ( )∘f g h i
– ngn
Commented Apr 12, 2020 at 14:16
• @ngn right, thanks! Commented Apr 12, 2020 at 14:19

# Pyth, 11 bytes

Seems rather long.

.cF_tSa0+aF


Test suite

### Explanation

Uses xnor's description.

.cF_tSa0+aF           Full program. Input: a 2-element list [a,b].
+aF           Add |a-b| to the list of inputs. Produces [|a-b|,a,b]
a0              Absolute difference with 0 (i.e. absolute value). Vectorizes.
tS                Sort the list of absolute values and remove the first element.
.cF_                  Reverse the above and apply nCr to its elements.


# C (gcc), 92 82 bytes

g(n,k){k=k<0?n=-n,-k:k;n=n<0?k-n:n;k^=n<k?n^=k^=n:0;n=n---k&&k?g(n,k-1)+g(n,k):1;}


Try it online!

10 bytes shorter thanks to ceilingcat!

This is longer than most of the other entries, but I think it's respectable since C doesn't have a built-in for binomial coefficients.

The code uses the fact that the four Eisenstein integers $$n+k\omega,$$ $$-n-k\omega,$$ $$k-n+k\omega,$$ and $$n-k-k\omega$$ are symmetrically located about the origin. Since the original triangular lattice is symmetrical about the origin, all four of those points will have the same number of paths to the origin.

Because of this, we can replace the input point with a point with non-negative Eisenstein coordinates which has the same number of paths to the origin, and that simplifies the computation.

Here's how it works:

1. If k < 0, replace n by -n, and k by -k. So now k is non-negative, but the output will be the same as for the original values of n and k.

2. If n < 0, replace n by k-n. Now n is also non-negative, but again the output will be the same.

3. If k > n, swap n and k, so that n is the larger of the two (or they're equal).

4. Compute the binomial coefficient $$\\binom{n}{k}\$$ using the recursive formula for it.

• @ceilingcat Thanks! I had tried all of those ideas, but didn't set them up right to get a reduction in bytes :( . Commented Apr 14, 2020 at 15:29

# Charcoal, 33 bytes

⊞υＮ⊞υ±Ｎ⊞υΣυ≔…⌊↔υ⌈↔υθＩ∨¬θ÷Π⊕θΠ⊕Ｅθκ


Try it online! Link is to verbose version of code. Uses @xnor's formula. Explanation:

⊞υＮ


Input a and push it to the list.

⊞υ±Ｎ


Input b and push -b to the list.

⊞υΣυ


Take the sum of the list, a-b, and push that to the list.

≔…⌊↔υ⌈↔υθ


Take the minimum and maximum of the list and form a range between the two.

Ｉ∨¬θ


If the range is empty then just output 1 (unfortunately in Charcoal the product of an empty list isn't 1)...

÷Π⊕θΠ⊕Ｅθκ


... otherwise output the quotient of the products of the ranges min+1..max and 1..max-min.

# JavaScript (ES6), 83 bytes

Takes input as (a)(b). Uses @xnor's formula.

with(Math)f=a=>g=(b,k=min(...a=[a,b,a-b].map(abs),n=max(...a)))=>k?n--*g(0,k-1)/k:1


Try it online!

# 05AB1E, 7 bytes

¥«ÄZscà


Port of @JonathanAllan's Jelly answer, so make sure to upvote him as well!!

Explanation:

¥        # Get deltas / forward-difference of the (implicit) input-pair
«       # Merge it to the (implicit) input-pair
Ä      # Take the absolute value of each
Z     # Push the maximum of this list (without popping)
s    # Swap so the list is at the top of the stack again
c   # Choose; get the binomial coefficient of each value with this maximum
à  # And pop and push the maximum of those result
# (after which it is output implicitly)


# Io, 79 bytes

method(a,b,list(2,0)map(i,list(a,b,a-b)map(abs)sort at(i))reduce(combinations))