10
\$\begingroup\$

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

enter image description here

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} $$

Task

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
Improve this question
\$\endgroup\$
2
  • \$\begingroup\$ 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) \$\endgroup\$ Commented Apr 12, 2020 at 10:13
  • \$\begingroup\$ @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.\$ \$\endgroup\$ Commented Apr 12, 2020 at 15:05

10 Answers 10

Reset to default
3
\$\begingroup\$

Wolfram Language (Mathematica), 38 bytes

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

Try it online!

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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] $ - last two links as a monad: Ṁ - maximum 9 c - choose (vectorises) [126, 1, 126] (9c4=9c5=126 and 9c9=1) Ṁ - maximum 126
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ -1 byte \$\endgroup\$ Commented Apr 12, 2020 at 10:34
  • \$\begingroup\$ @newbie Jump to the end. Nice one - thanks! :-) \$\endgroup\$ Commented Apr 12, 2020 at 11:35
2
\$\begingroup\$

APL (Dyalog), 13 12 bytes

1 byte saved thanks to @ngn!

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

Try it online!

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ ( )(f g h i) -> ( )∘f g h i \$\endgroup\$ Commented Apr 12, 2020 at 14:16
  • \$\begingroup\$ @ngn right, thanks! \$\endgroup\$ Commented Apr 12, 2020 at 14:19
1
\$\begingroup\$

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

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.

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

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.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

05AB1E, 7 bytes

¥«ÄZscà

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

Try it online or verify all test cases.

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)
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Io, 79 bytes

Port of most answers.

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

Try it online!

Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.