Partitioning the grid into triangles
up vote
18
down vote
favorite
Goal
The goal of this challenge is to produce a function of n
which computes the number of ways to partition the n X 1
grid into triangles where all of the vertices of the triangles are on grid points.
Example
For example, there are 14 ways to partition the 2 x 1 grid, so f(2) = 14
via the following partitions
where the partitions have 2, 2, 2, 2, 4, and 2 distinct orientations respectively.
Scoring
This is code-golf, so shortest code wins.
code-golf geometry combinatorics grid
add a comment |
up vote
18
down vote
favorite
Goal
The goal of this challenge is to produce a function of n
which computes the number of ways to partition the n X 1
grid into triangles where all of the vertices of the triangles are on grid points.
Example
For example, there are 14 ways to partition the 2 x 1 grid, so f(2) = 14
via the following partitions
where the partitions have 2, 2, 2, 2, 4, and 2 distinct orientations respectively.
Scoring
This is code-golf, so shortest code wins.
code-golf geometry combinatorics grid
10
Some additional test cases would be beneficial, so we can verify our submissions are correct.
– AdmBorkBork
Nov 27 at 21:19
8
You may want to specify non-degenerate triangles.
– Arnauld
Nov 27 at 21:24
I've made edits to OEIS sequence A051708 to reflect this interpretation.
– Peter Kagey
Nov 30 at 18:32
add a comment |
up vote
18
down vote
favorite
up vote
18
down vote
favorite
Goal
The goal of this challenge is to produce a function of n
which computes the number of ways to partition the n X 1
grid into triangles where all of the vertices of the triangles are on grid points.
Example
For example, there are 14 ways to partition the 2 x 1 grid, so f(2) = 14
via the following partitions
where the partitions have 2, 2, 2, 2, 4, and 2 distinct orientations respectively.
Scoring
This is code-golf, so shortest code wins.
code-golf geometry combinatorics grid
Goal
The goal of this challenge is to produce a function of n
which computes the number of ways to partition the n X 1
grid into triangles where all of the vertices of the triangles are on grid points.
Example
For example, there are 14 ways to partition the 2 x 1 grid, so f(2) = 14
via the following partitions
where the partitions have 2, 2, 2, 2, 4, and 2 distinct orientations respectively.
Scoring
This is code-golf, so shortest code wins.
code-golf geometry combinatorics grid
code-golf geometry combinatorics grid
edited Nov 27 at 21:29
asked Nov 27 at 21:10
Peter Kagey
642516
642516
10
Some additional test cases would be beneficial, so we can verify our submissions are correct.
– AdmBorkBork
Nov 27 at 21:19
8
You may want to specify non-degenerate triangles.
– Arnauld
Nov 27 at 21:24
I've made edits to OEIS sequence A051708 to reflect this interpretation.
– Peter Kagey
Nov 30 at 18:32
add a comment |
10
Some additional test cases would be beneficial, so we can verify our submissions are correct.
– AdmBorkBork
Nov 27 at 21:19
8
You may want to specify non-degenerate triangles.
– Arnauld
Nov 27 at 21:24
I've made edits to OEIS sequence A051708 to reflect this interpretation.
– Peter Kagey
Nov 30 at 18:32
10
10
Some additional test cases would be beneficial, so we can verify our submissions are correct.
– AdmBorkBork
Nov 27 at 21:19
Some additional test cases would be beneficial, so we can verify our submissions are correct.
– AdmBorkBork
Nov 27 at 21:19
8
8
You may want to specify non-degenerate triangles.
– Arnauld
Nov 27 at 21:24
You may want to specify non-degenerate triangles.
– Arnauld
Nov 27 at 21:24
I've made edits to OEIS sequence A051708 to reflect this interpretation.
– Peter Kagey
Nov 30 at 18:32
I've made edits to OEIS sequence A051708 to reflect this interpretation.
– Peter Kagey
Nov 30 at 18:32
add a comment |
9 Answers
9
active
oldest
votes
up vote
19
down vote
Haskell, 60 55 54 52 bytes
After a drawing and programming a lot of examples, it occured to me that this is the same as the problem of the rooks:
On a $(n+1) times (n+1)$ chessboard, how many ways are there for a rook to go from $(0,0)$ to $(n,n)$ by just moving right $+(1,0)$ or up $+(0,1)$?
Basically you have the top and the bottom line of the $1 times n$ grid. Now you have to fill in the non-horizontal line. Each triangle must have two non-horizontal lines. Whether one of its sides is part of the top or the bottom line corresponds to the direction and length you'd go in the rooks problem. This is OEIS A051708. As an illustration of this correspondence consider following examples. Here the top line corresponds to up-moves, while the bottom line corresponds to right-moves.
Thanks @PeterTaylor for -6 bytes and @PostLeftGarfHunter for -2 bytes!
b 0=1
b 1=2
b n=div((10*n-6)*b(n-1)-9*(n-2)*b(n-2))n
Try it online!
I found the OEIS sequence by searching with the first few values. Nice explanation for why it matches. Do you want to edit it to add a comment about this alternative combinatorial interpretation? If not, I might.
– Peter Taylor
Nov 27 at 22:36
BTW you need to adjust the indexing, because the correct answer here isA051708(n+1)
. So I posted the first correct answer :-P
– Peter Taylor
Nov 27 at 22:39
I take it the rook moves map to triangles by making triangles with top and bottom edges correspond to up or right moves?
– Neil
Nov 27 at 22:40
@PeterTaylor Damn, thanks for pointing out my mistake :)
– flawr
Nov 27 at 22:41
5
@Neil I added a graphical explanation.
– flawr
Nov 27 at 23:10
|
show 2 more comments
up vote
8
down vote
Haskell, 42 bytes
0?0=1
a?b=sum[a?i+i?a|i<-[0..b-1]]
f n=n?n
Try it online!
A fairly direct implementation that recurses over 2 variables.
Here's how we can obtain this solution. Start with code implementing a direct recursive formula:
54 bytes
0%0=1
a%b=sum$map(a%)[0..b-1]++map(b%)[0..a-1]
f n=n%n
Try it online!
Using flawr's rook move interpretation ,a%b
is the number of paths that get the rook from (a,b)
to (0,0)
, using only moves the decrease a coordinate. The first move either decreases a
or decreases b
, keeping the other the same, hence the recursive formula.
49 bytes
a?b=sum$map(a%)[0..b-1]
0%0=1
a%b=a?b+b?a
f n=n%n
Try it online!
We can avoid the repetition in map(a%)[0..b-1]++map(b%)[0..a-1]
by noting that the two halves are the same with a
and b
swapped. The auxiliary call a?b
counts the paths where the first move decreases a
, and so b?a
counts those where the first move decreases b
. These are in general different, and they add to a%b
.
The summation in a?b
can also be written as a list comprehension a?b=sum[a%i|i<-[0..b-1]]
.
42 bytes
0?0=1
a?b=sum[a?i+i?a|i<-[0..b-1]]
f n=n?n
Try it online!
Finally, we get rid of %
and just write the recursion in terms of ?
by replacing a%i
with a?i+i?a
in the recursive call.
The new base case causes this ?
to give outputs double that of the ?
in the 49-byte version, since with 0?0=1
, we would have 0%0=0?0+0?0=2
. This lets use define f n=n?n
without the halving that we'd other need to do.
Your 49-byte solution uses the same recursion as my answer, but I haven't yet figured out the 42-byte one. An explanation would be nice.
– Peter Taylor
Nov 28 at 8:57
I think I used the same approach in one of my earlier programs: The idea is generating (or counting) all partitions by generating the non-horizontal lines from right to left. You start out with the vertical line. Then you can recurse: Take one of the end nodes of the previous line and connect it to a node on the opposite horizontal line that is farther to the left of all previous nodes on this line.
– flawr
Nov 28 at 9:14
The operatora%b
counts the number of partitions using the nodes0,1,...,a
on the top line, and the nods0,1,..,b
on the bottom line. The operatora?b
counts the number of ways you can add a new line from the top nodea
if the bottom nodeb
is already in use. (You can connecta
to all of the nodes[0,1,...,b-1]
, but you then have to recurse for each of those.)
– flawr
Nov 28 at 9:14
@flawr, that's the 49-byte one, which I understand. It's the?
of the 42-byte one which I don't, and what's particularly curious is that it's not symmetric.
– Peter Taylor
Nov 28 at 11:12
@PeterTaylor Sorry for the confusion, I somehow mixed up the two solutions. I think we can quite easily transform the two solutions into eachother: In the first step we can replacemap...
with a list comprehension, in the second step we just plug in the definition of%
:a?b=sum$map(a%)[0..b-1], a%b=a?b+b?a
$ iff $a?b=sum[a%i|i<-[0..b-1]], a%b=a?b+b?a
$ iff $a?b=sum[a?i+i?a|i<-[0..b-1]]
– flawr
Nov 28 at 19:24
|
show 3 more comments
up vote
7
down vote
CJam (24 bytes)
{2,*e!{e`0f=:(1b2#}%1b}
Online demo
This uses Bubbler's approach of summing over permutations of n
0s and n
1s.
Dissection
{ e# Define a block
2,* e# Given input n, create an array of n 0s and n 1s
e! e# Generate all permutations of that array
{ e# Map:
e` e# Run-length encode
0f=:( e# Extract just the lengths and decrement them
1b e# Sum
2# e# Raise 2 to the power of that sum
}%
1b e# Sum the mapped values
}
Alternative approach (28 bytes)
{_1aa{_2$,f{j}@@,f{j}+1b}2j}
Online demo
Dissection
The triangles all have one horizontal edge and two edges which link the horizontal lines. Label the non-horizontal edges by a tuple of their two x-coords and sort lexicographically. Then the first edge is (0,0)
, the last edge is (n,n)
, and two consecutive edges differ in precisely one of the two positions. This makes for a simple recursion, which I've implemented using the memoised recursion operator j
:
{ e# Define a block
_ e# Duplicate the argument to get n n
1aa e# Base case for recursion: 0 0 => 1
{ e# Recursive body taking args a b
_2$,f{j} e# Recurse on 0 b up to a-1 b
@@,f{j} e# Recurse on a 0 up to a b-1
+1b e# Combine and sum
}2j e# Memoised recursion with 2 args
}
Note
This is not the first time I've wanted fj
to be supported in CJam. Here it would bring the score down to 24 bytes also. Perhaps I should try to write a patch...
Yay, I beat you by 10 seconds, I don't think I was ever that close :)
– flawr
Nov 27 at 22:32
@flawr, I did consider posting before writing a dissection, but I thought I had time to knock it out quickly. Then I saw "New answer", so I deleted my part-written dissection, posted, and edited.
– Peter Taylor
Nov 27 at 22:34
1
Thanks for -5 bytes btw :D
– flawr
Nov 27 at 22:47
add a comment |
up vote
4
down vote
Jelly, 15 14 bytes
Ø.xŒ!QŒɠ€’§2*S
Try it online!
-1 byte based on Peter Taylor's comment.
Uses flawr's illustration directly, instead of the resulting formula.
How it works
Ø.xŒ!QŒɠ€’§2*S Main link (monad). Input: positive integer N.
Ø.x Make an array containing N zeros and ones
Œ!Q All unique permutations
Œɠ€ Run-length encode on each permutation
’§ Decrement and sum each
2*S Raise to power of 2 and sum
Take every possible route on a square grid. The number of ways to move L units in one direction as a rook is 2**(L-1)
. Apply this to every route and sum the number of ways to traverse each route.
Nice approach. When I ported it to CJam it was shorter to decrement the lengths, sum, and then raise 2 to the sum; rather than raising 2 to the length, halving, and then multiplying. Don't know whether it might save you a byte.
– Peter Taylor
Nov 28 at 11:27
add a comment |
up vote
3
down vote
Charcoal, 44 31 bytes
crossed out 44 is still regular 44
F⊕θ«≔⟦⟧ηF⊕θ⊞ηΣ∨⁺ηEυ§λκ¹⊞υη»I⊟⊟υ
Try it online! Explanation: Works by calculating the number of ways to partition a trapezium of opposite side lengths m,n
into triangles which all lie on integer offsets. This is simply a general case of the rectangle of size n
in the question. The number of partitions is given recursively as the sums of the numbers of partitions for all sides m,0..n-1
and n,0..m-1
. This is equivalent to generalised problem of the rooks, OEIS A035002. The code simply calculates the number of partitions working from 0,0
up to n,n
using the previously calculated values as it goes.
F⊕θ«
Loop over the rows 0..n
.
≔⟦⟧η
Start with an empty row.
F⊕θ
Loop over the columns in the row 0..n
.
⊞ηΣ∨⁺ηEυ§λκ¹
Take the row so far and the values in the previous rows at the current column, and add the sum total to the current row. However, if there are no values at all, then substitute 1
in place of the sum.
⊞υη»
Add the finished row to the list of rows so far.
I⊟⊟υ
Output the final value calculated.
add a comment |
up vote
2
down vote
JavaScript (ES6), 45 44 42 bytes
Uses the recursive formula found by Peter Taylor and flawr.
f=n=>n<2?n+1:(10-6/n)*f(--n)+9/~n*f(--n)*n
Try it online!
add a comment |
up vote
2
down vote
Pari/GP, 43 bytes
According to OEIS, the generating function of this sequence is
$$frac{1}{2}left(sqrt{frac{1-x}{1-9x}}+1right)$$
n->Vec(sqrt((1-x)/(1-9*x)+O(x^n++))+1)[n]/2
Try it online!
add a comment |
up vote
1
down vote
Python 3, 51 bytes
lambda n:-~n*(n<2)or(10-6/n)*f(n-1)-(9-18/n)*f(n-2)
Try it online!
Port of flawr's answer
add a comment |
up vote
0
down vote
05AB1E, 13 bytes
·LÉœÙεÅγo;P}O
Port of @Bubbler's Jelly answer.
Very slow due to the permutations builtin.
Try it online or verify the first four inputs.
Explanation:
· # Double the (implicit) input
L # Create a list in the range [1, doubled_input]
É # Check for each if they're odd (1 if truthy, 0 is falsey)
# We now have a list of n 0s and n 1s (n being the input)
œ # Get all permutations of that list
Ù # Only leave the unique permutations
ε } # Map each permutation to:
Åγ # Run-length encode the current value (short for `γ€g`)
o # Take 2 to the power for each
; # Halve each
P # Take the product of the mapped permutation
O # Sum all mapped values together (and output implicitly)
add a comment |
9 Answers
9
active
oldest
votes
9 Answers
9
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
19
down vote
Haskell, 60 55 54 52 bytes
After a drawing and programming a lot of examples, it occured to me that this is the same as the problem of the rooks:
On a $(n+1) times (n+1)$ chessboard, how many ways are there for a rook to go from $(0,0)$ to $(n,n)$ by just moving right $+(1,0)$ or up $+(0,1)$?
Basically you have the top and the bottom line of the $1 times n$ grid. Now you have to fill in the non-horizontal line. Each triangle must have two non-horizontal lines. Whether one of its sides is part of the top or the bottom line corresponds to the direction and length you'd go in the rooks problem. This is OEIS A051708. As an illustration of this correspondence consider following examples. Here the top line corresponds to up-moves, while the bottom line corresponds to right-moves.
Thanks @PeterTaylor for -6 bytes and @PostLeftGarfHunter for -2 bytes!
b 0=1
b 1=2
b n=div((10*n-6)*b(n-1)-9*(n-2)*b(n-2))n
Try it online!
I found the OEIS sequence by searching with the first few values. Nice explanation for why it matches. Do you want to edit it to add a comment about this alternative combinatorial interpretation? If not, I might.
– Peter Taylor
Nov 27 at 22:36
BTW you need to adjust the indexing, because the correct answer here isA051708(n+1)
. So I posted the first correct answer :-P
– Peter Taylor
Nov 27 at 22:39
I take it the rook moves map to triangles by making triangles with top and bottom edges correspond to up or right moves?
– Neil
Nov 27 at 22:40
@PeterTaylor Damn, thanks for pointing out my mistake :)
– flawr
Nov 27 at 22:41
5
@Neil I added a graphical explanation.
– flawr
Nov 27 at 23:10
|
show 2 more comments
up vote
19
down vote
Haskell, 60 55 54 52 bytes
After a drawing and programming a lot of examples, it occured to me that this is the same as the problem of the rooks:
On a $(n+1) times (n+1)$ chessboard, how many ways are there for a rook to go from $(0,0)$ to $(n,n)$ by just moving right $+(1,0)$ or up $+(0,1)$?
Basically you have the top and the bottom line of the $1 times n$ grid. Now you have to fill in the non-horizontal line. Each triangle must have two non-horizontal lines. Whether one of its sides is part of the top or the bottom line corresponds to the direction and length you'd go in the rooks problem. This is OEIS A051708. As an illustration of this correspondence consider following examples. Here the top line corresponds to up-moves, while the bottom line corresponds to right-moves.
Thanks @PeterTaylor for -6 bytes and @PostLeftGarfHunter for -2 bytes!
b 0=1
b 1=2
b n=div((10*n-6)*b(n-1)-9*(n-2)*b(n-2))n
Try it online!
I found the OEIS sequence by searching with the first few values. Nice explanation for why it matches. Do you want to edit it to add a comment about this alternative combinatorial interpretation? If not, I might.
– Peter Taylor
Nov 27 at 22:36
BTW you need to adjust the indexing, because the correct answer here isA051708(n+1)
. So I posted the first correct answer :-P
– Peter Taylor
Nov 27 at 22:39
I take it the rook moves map to triangles by making triangles with top and bottom edges correspond to up or right moves?
– Neil
Nov 27 at 22:40
@PeterTaylor Damn, thanks for pointing out my mistake :)
– flawr
Nov 27 at 22:41
5
@Neil I added a graphical explanation.
– flawr
Nov 27 at 23:10
|
show 2 more comments
up vote
19
down vote
up vote
19
down vote
Haskell, 60 55 54 52 bytes
After a drawing and programming a lot of examples, it occured to me that this is the same as the problem of the rooks:
On a $(n+1) times (n+1)$ chessboard, how many ways are there for a rook to go from $(0,0)$ to $(n,n)$ by just moving right $+(1,0)$ or up $+(0,1)$?
Basically you have the top and the bottom line of the $1 times n$ grid. Now you have to fill in the non-horizontal line. Each triangle must have two non-horizontal lines. Whether one of its sides is part of the top or the bottom line corresponds to the direction and length you'd go in the rooks problem. This is OEIS A051708. As an illustration of this correspondence consider following examples. Here the top line corresponds to up-moves, while the bottom line corresponds to right-moves.
Thanks @PeterTaylor for -6 bytes and @PostLeftGarfHunter for -2 bytes!
b 0=1
b 1=2
b n=div((10*n-6)*b(n-1)-9*(n-2)*b(n-2))n
Try it online!
Haskell, 60 55 54 52 bytes
After a drawing and programming a lot of examples, it occured to me that this is the same as the problem of the rooks:
On a $(n+1) times (n+1)$ chessboard, how many ways are there for a rook to go from $(0,0)$ to $(n,n)$ by just moving right $+(1,0)$ or up $+(0,1)$?
Basically you have the top and the bottom line of the $1 times n$ grid. Now you have to fill in the non-horizontal line. Each triangle must have two non-horizontal lines. Whether one of its sides is part of the top or the bottom line corresponds to the direction and length you'd go in the rooks problem. This is OEIS A051708. As an illustration of this correspondence consider following examples. Here the top line corresponds to up-moves, while the bottom line corresponds to right-moves.
Thanks @PeterTaylor for -6 bytes and @PostLeftGarfHunter for -2 bytes!
b 0=1
b 1=2
b n=div((10*n-6)*b(n-1)-9*(n-2)*b(n-2))n
Try it online!
edited Nov 28 at 20:22
answered Nov 27 at 22:30
flawr
26.4k662186
26.4k662186
I found the OEIS sequence by searching with the first few values. Nice explanation for why it matches. Do you want to edit it to add a comment about this alternative combinatorial interpretation? If not, I might.
– Peter Taylor
Nov 27 at 22:36
BTW you need to adjust the indexing, because the correct answer here isA051708(n+1)
. So I posted the first correct answer :-P
– Peter Taylor
Nov 27 at 22:39
I take it the rook moves map to triangles by making triangles with top and bottom edges correspond to up or right moves?
– Neil
Nov 27 at 22:40
@PeterTaylor Damn, thanks for pointing out my mistake :)
– flawr
Nov 27 at 22:41
5
@Neil I added a graphical explanation.
– flawr
Nov 27 at 23:10
|
show 2 more comments
I found the OEIS sequence by searching with the first few values. Nice explanation for why it matches. Do you want to edit it to add a comment about this alternative combinatorial interpretation? If not, I might.
– Peter Taylor
Nov 27 at 22:36
BTW you need to adjust the indexing, because the correct answer here isA051708(n+1)
. So I posted the first correct answer :-P
– Peter Taylor
Nov 27 at 22:39
I take it the rook moves map to triangles by making triangles with top and bottom edges correspond to up or right moves?
– Neil
Nov 27 at 22:40
@PeterTaylor Damn, thanks for pointing out my mistake :)
– flawr
Nov 27 at 22:41
5
@Neil I added a graphical explanation.
– flawr
Nov 27 at 23:10
I found the OEIS sequence by searching with the first few values. Nice explanation for why it matches. Do you want to edit it to add a comment about this alternative combinatorial interpretation? If not, I might.
– Peter Taylor
Nov 27 at 22:36
I found the OEIS sequence by searching with the first few values. Nice explanation for why it matches. Do you want to edit it to add a comment about this alternative combinatorial interpretation? If not, I might.
– Peter Taylor
Nov 27 at 22:36
BTW you need to adjust the indexing, because the correct answer here is
A051708(n+1)
. So I posted the first correct answer :-P– Peter Taylor
Nov 27 at 22:39
BTW you need to adjust the indexing, because the correct answer here is
A051708(n+1)
. So I posted the first correct answer :-P– Peter Taylor
Nov 27 at 22:39
I take it the rook moves map to triangles by making triangles with top and bottom edges correspond to up or right moves?
– Neil
Nov 27 at 22:40
I take it the rook moves map to triangles by making triangles with top and bottom edges correspond to up or right moves?
– Neil
Nov 27 at 22:40
@PeterTaylor Damn, thanks for pointing out my mistake :)
– flawr
Nov 27 at 22:41
@PeterTaylor Damn, thanks for pointing out my mistake :)
– flawr
Nov 27 at 22:41
5
5
@Neil I added a graphical explanation.
– flawr
Nov 27 at 23:10
@Neil I added a graphical explanation.
– flawr
Nov 27 at 23:10
|
show 2 more comments
up vote
8
down vote
Haskell, 42 bytes
0?0=1
a?b=sum[a?i+i?a|i<-[0..b-1]]
f n=n?n
Try it online!
A fairly direct implementation that recurses over 2 variables.
Here's how we can obtain this solution. Start with code implementing a direct recursive formula:
54 bytes
0%0=1
a%b=sum$map(a%)[0..b-1]++map(b%)[0..a-1]
f n=n%n
Try it online!
Using flawr's rook move interpretation ,a%b
is the number of paths that get the rook from (a,b)
to (0,0)
, using only moves the decrease a coordinate. The first move either decreases a
or decreases b
, keeping the other the same, hence the recursive formula.
49 bytes
a?b=sum$map(a%)[0..b-1]
0%0=1
a%b=a?b+b?a
f n=n%n
Try it online!
We can avoid the repetition in map(a%)[0..b-1]++map(b%)[0..a-1]
by noting that the two halves are the same with a
and b
swapped. The auxiliary call a?b
counts the paths where the first move decreases a
, and so b?a
counts those where the first move decreases b
. These are in general different, and they add to a%b
.
The summation in a?b
can also be written as a list comprehension a?b=sum[a%i|i<-[0..b-1]]
.
42 bytes
0?0=1
a?b=sum[a?i+i?a|i<-[0..b-1]]
f n=n?n
Try it online!
Finally, we get rid of %
and just write the recursion in terms of ?
by replacing a%i
with a?i+i?a
in the recursive call.
The new base case causes this ?
to give outputs double that of the ?
in the 49-byte version, since with 0?0=1
, we would have 0%0=0?0+0?0=2
. This lets use define f n=n?n
without the halving that we'd other need to do.
Your 49-byte solution uses the same recursion as my answer, but I haven't yet figured out the 42-byte one. An explanation would be nice.
– Peter Taylor
Nov 28 at 8:57
I think I used the same approach in one of my earlier programs: The idea is generating (or counting) all partitions by generating the non-horizontal lines from right to left. You start out with the vertical line. Then you can recurse: Take one of the end nodes of the previous line and connect it to a node on the opposite horizontal line that is farther to the left of all previous nodes on this line.
– flawr
Nov 28 at 9:14
The operatora%b
counts the number of partitions using the nodes0,1,...,a
on the top line, and the nods0,1,..,b
on the bottom line. The operatora?b
counts the number of ways you can add a new line from the top nodea
if the bottom nodeb
is already in use. (You can connecta
to all of the nodes[0,1,...,b-1]
, but you then have to recurse for each of those.)
– flawr
Nov 28 at 9:14
@flawr, that's the 49-byte one, which I understand. It's the?
of the 42-byte one which I don't, and what's particularly curious is that it's not symmetric.
– Peter Taylor
Nov 28 at 11:12
@PeterTaylor Sorry for the confusion, I somehow mixed up the two solutions. I think we can quite easily transform the two solutions into eachother: In the first step we can replacemap...
with a list comprehension, in the second step we just plug in the definition of%
:a?b=sum$map(a%)[0..b-1], a%b=a?b+b?a
$ iff $a?b=sum[a%i|i<-[0..b-1]], a%b=a?b+b?a
$ iff $a?b=sum[a?i+i?a|i<-[0..b-1]]
– flawr
Nov 28 at 19:24
|
show 3 more comments
up vote
8
down vote
Haskell, 42 bytes
0?0=1
a?b=sum[a?i+i?a|i<-[0..b-1]]
f n=n?n
Try it online!
A fairly direct implementation that recurses over 2 variables.
Here's how we can obtain this solution. Start with code implementing a direct recursive formula:
54 bytes
0%0=1
a%b=sum$map(a%)[0..b-1]++map(b%)[0..a-1]
f n=n%n
Try it online!
Using flawr's rook move interpretation ,a%b
is the number of paths that get the rook from (a,b)
to (0,0)
, using only moves the decrease a coordinate. The first move either decreases a
or decreases b
, keeping the other the same, hence the recursive formula.
49 bytes
a?b=sum$map(a%)[0..b-1]
0%0=1
a%b=a?b+b?a
f n=n%n
Try it online!
We can avoid the repetition in map(a%)[0..b-1]++map(b%)[0..a-1]
by noting that the two halves are the same with a
and b
swapped. The auxiliary call a?b
counts the paths where the first move decreases a
, and so b?a
counts those where the first move decreases b
. These are in general different, and they add to a%b
.
The summation in a?b
can also be written as a list comprehension a?b=sum[a%i|i<-[0..b-1]]
.
42 bytes
0?0=1
a?b=sum[a?i+i?a|i<-[0..b-1]]
f n=n?n
Try it online!
Finally, we get rid of %
and just write the recursion in terms of ?
by replacing a%i
with a?i+i?a
in the recursive call.
The new base case causes this ?
to give outputs double that of the ?
in the 49-byte version, since with 0?0=1
, we would have 0%0=0?0+0?0=2
. This lets use define f n=n?n
without the halving that we'd other need to do.
Your 49-byte solution uses the same recursion as my answer, but I haven't yet figured out the 42-byte one. An explanation would be nice.
– Peter Taylor
Nov 28 at 8:57
I think I used the same approach in one of my earlier programs: The idea is generating (or counting) all partitions by generating the non-horizontal lines from right to left. You start out with the vertical line. Then you can recurse: Take one of the end nodes of the previous line and connect it to a node on the opposite horizontal line that is farther to the left of all previous nodes on this line.
– flawr
Nov 28 at 9:14
The operatora%b
counts the number of partitions using the nodes0,1,...,a
on the top line, and the nods0,1,..,b
on the bottom line. The operatora?b
counts the number of ways you can add a new line from the top nodea
if the bottom nodeb
is already in use. (You can connecta
to all of the nodes[0,1,...,b-1]
, but you then have to recurse for each of those.)
– flawr
Nov 28 at 9:14
@flawr, that's the 49-byte one, which I understand. It's the?
of the 42-byte one which I don't, and what's particularly curious is that it's not symmetric.
– Peter Taylor
Nov 28 at 11:12
@PeterTaylor Sorry for the confusion, I somehow mixed up the two solutions. I think we can quite easily transform the two solutions into eachother: In the first step we can replacemap...
with a list comprehension, in the second step we just plug in the definition of%
:a?b=sum$map(a%)[0..b-1], a%b=a?b+b?a
$ iff $a?b=sum[a%i|i<-[0..b-1]], a%b=a?b+b?a
$ iff $a?b=sum[a?i+i?a|i<-[0..b-1]]
– flawr
Nov 28 at 19:24
|
show 3 more comments
up vote
8
down vote
up vote
8
down vote
Haskell, 42 bytes
0?0=1
a?b=sum[a?i+i?a|i<-[0..b-1]]
f n=n?n
Try it online!
A fairly direct implementation that recurses over 2 variables.
Here's how we can obtain this solution. Start with code implementing a direct recursive formula:
54 bytes
0%0=1
a%b=sum$map(a%)[0..b-1]++map(b%)[0..a-1]
f n=n%n
Try it online!
Using flawr's rook move interpretation ,a%b
is the number of paths that get the rook from (a,b)
to (0,0)
, using only moves the decrease a coordinate. The first move either decreases a
or decreases b
, keeping the other the same, hence the recursive formula.
49 bytes
a?b=sum$map(a%)[0..b-1]
0%0=1
a%b=a?b+b?a
f n=n%n
Try it online!
We can avoid the repetition in map(a%)[0..b-1]++map(b%)[0..a-1]
by noting that the two halves are the same with a
and b
swapped. The auxiliary call a?b
counts the paths where the first move decreases a
, and so b?a
counts those where the first move decreases b
. These are in general different, and they add to a%b
.
The summation in a?b
can also be written as a list comprehension a?b=sum[a%i|i<-[0..b-1]]
.
42 bytes
0?0=1
a?b=sum[a?i+i?a|i<-[0..b-1]]
f n=n?n
Try it online!
Finally, we get rid of %
and just write the recursion in terms of ?
by replacing a%i
with a?i+i?a
in the recursive call.
The new base case causes this ?
to give outputs double that of the ?
in the 49-byte version, since with 0?0=1
, we would have 0%0=0?0+0?0=2
. This lets use define f n=n?n
without the halving that we'd other need to do.
Haskell, 42 bytes
0?0=1
a?b=sum[a?i+i?a|i<-[0..b-1]]
f n=n?n
Try it online!
A fairly direct implementation that recurses over 2 variables.
Here's how we can obtain this solution. Start with code implementing a direct recursive formula:
54 bytes
0%0=1
a%b=sum$map(a%)[0..b-1]++map(b%)[0..a-1]
f n=n%n
Try it online!
Using flawr's rook move interpretation ,a%b
is the number of paths that get the rook from (a,b)
to (0,0)
, using only moves the decrease a coordinate. The first move either decreases a
or decreases b
, keeping the other the same, hence the recursive formula.
49 bytes
a?b=sum$map(a%)[0..b-1]
0%0=1
a%b=a?b+b?a
f n=n%n
Try it online!
We can avoid the repetition in map(a%)[0..b-1]++map(b%)[0..a-1]
by noting that the two halves are the same with a
and b
swapped. The auxiliary call a?b
counts the paths where the first move decreases a
, and so b?a
counts those where the first move decreases b
. These are in general different, and they add to a%b
.
The summation in a?b
can also be written as a list comprehension a?b=sum[a%i|i<-[0..b-1]]
.
42 bytes
0?0=1
a?b=sum[a?i+i?a|i<-[0..b-1]]
f n=n?n
Try it online!
Finally, we get rid of %
and just write the recursion in terms of ?
by replacing a%i
with a?i+i?a
in the recursive call.
The new base case causes this ?
to give outputs double that of the ?
in the 49-byte version, since with 0?0=1
, we would have 0%0=0?0+0?0=2
. This lets use define f n=n?n
without the halving that we'd other need to do.
edited Nov 30 at 1:12
answered Nov 28 at 0:10
xnor
89.4k18184437
89.4k18184437
Your 49-byte solution uses the same recursion as my answer, but I haven't yet figured out the 42-byte one. An explanation would be nice.
– Peter Taylor
Nov 28 at 8:57
I think I used the same approach in one of my earlier programs: The idea is generating (or counting) all partitions by generating the non-horizontal lines from right to left. You start out with the vertical line. Then you can recurse: Take one of the end nodes of the previous line and connect it to a node on the opposite horizontal line that is farther to the left of all previous nodes on this line.
– flawr
Nov 28 at 9:14
The operatora%b
counts the number of partitions using the nodes0,1,...,a
on the top line, and the nods0,1,..,b
on the bottom line. The operatora?b
counts the number of ways you can add a new line from the top nodea
if the bottom nodeb
is already in use. (You can connecta
to all of the nodes[0,1,...,b-1]
, but you then have to recurse for each of those.)
– flawr
Nov 28 at 9:14
@flawr, that's the 49-byte one, which I understand. It's the?
of the 42-byte one which I don't, and what's particularly curious is that it's not symmetric.
– Peter Taylor
Nov 28 at 11:12
@PeterTaylor Sorry for the confusion, I somehow mixed up the two solutions. I think we can quite easily transform the two solutions into eachother: In the first step we can replacemap...
with a list comprehension, in the second step we just plug in the definition of%
:a?b=sum$map(a%)[0..b-1], a%b=a?b+b?a
$ iff $a?b=sum[a%i|i<-[0..b-1]], a%b=a?b+b?a
$ iff $a?b=sum[a?i+i?a|i<-[0..b-1]]
– flawr
Nov 28 at 19:24
|
show 3 more comments
Your 49-byte solution uses the same recursion as my answer, but I haven't yet figured out the 42-byte one. An explanation would be nice.
– Peter Taylor
Nov 28 at 8:57
I think I used the same approach in one of my earlier programs: The idea is generating (or counting) all partitions by generating the non-horizontal lines from right to left. You start out with the vertical line. Then you can recurse: Take one of the end nodes of the previous line and connect it to a node on the opposite horizontal line that is farther to the left of all previous nodes on this line.
– flawr
Nov 28 at 9:14
The operatora%b
counts the number of partitions using the nodes0,1,...,a
on the top line, and the nods0,1,..,b
on the bottom line. The operatora?b
counts the number of ways you can add a new line from the top nodea
if the bottom nodeb
is already in use. (You can connecta
to all of the nodes[0,1,...,b-1]
, but you then have to recurse for each of those.)
– flawr
Nov 28 at 9:14
@flawr, that's the 49-byte one, which I understand. It's the?
of the 42-byte one which I don't, and what's particularly curious is that it's not symmetric.
– Peter Taylor
Nov 28 at 11:12
@PeterTaylor Sorry for the confusion, I somehow mixed up the two solutions. I think we can quite easily transform the two solutions into eachother: In the first step we can replacemap...
with a list comprehension, in the second step we just plug in the definition of%
:a?b=sum$map(a%)[0..b-1], a%b=a?b+b?a
$ iff $a?b=sum[a%i|i<-[0..b-1]], a%b=a?b+b?a
$ iff $a?b=sum[a?i+i?a|i<-[0..b-1]]
– flawr
Nov 28 at 19:24
Your 49-byte solution uses the same recursion as my answer, but I haven't yet figured out the 42-byte one. An explanation would be nice.
– Peter Taylor
Nov 28 at 8:57
Your 49-byte solution uses the same recursion as my answer, but I haven't yet figured out the 42-byte one. An explanation would be nice.
– Peter Taylor
Nov 28 at 8:57
I think I used the same approach in one of my earlier programs: The idea is generating (or counting) all partitions by generating the non-horizontal lines from right to left. You start out with the vertical line. Then you can recurse: Take one of the end nodes of the previous line and connect it to a node on the opposite horizontal line that is farther to the left of all previous nodes on this line.
– flawr
Nov 28 at 9:14
I think I used the same approach in one of my earlier programs: The idea is generating (or counting) all partitions by generating the non-horizontal lines from right to left. You start out with the vertical line. Then you can recurse: Take one of the end nodes of the previous line and connect it to a node on the opposite horizontal line that is farther to the left of all previous nodes on this line.
– flawr
Nov 28 at 9:14
The operator
a%b
counts the number of partitions using the nodes 0,1,...,a
on the top line, and the nods 0,1,..,b
on the bottom line. The operator a?b
counts the number of ways you can add a new line from the top node a
if the bottom node b
is already in use. (You can connect a
to all of the nodes [0,1,...,b-1]
, but you then have to recurse for each of those.)– flawr
Nov 28 at 9:14
The operator
a%b
counts the number of partitions using the nodes 0,1,...,a
on the top line, and the nods 0,1,..,b
on the bottom line. The operator a?b
counts the number of ways you can add a new line from the top node a
if the bottom node b
is already in use. (You can connect a
to all of the nodes [0,1,...,b-1]
, but you then have to recurse for each of those.)– flawr
Nov 28 at 9:14
@flawr, that's the 49-byte one, which I understand. It's the
?
of the 42-byte one which I don't, and what's particularly curious is that it's not symmetric.– Peter Taylor
Nov 28 at 11:12
@flawr, that's the 49-byte one, which I understand. It's the
?
of the 42-byte one which I don't, and what's particularly curious is that it's not symmetric.– Peter Taylor
Nov 28 at 11:12
@PeterTaylor Sorry for the confusion, I somehow mixed up the two solutions. I think we can quite easily transform the two solutions into eachother: In the first step we can replace
map...
with a list comprehension, in the second step we just plug in the definition of %
: a?b=sum$map(a%)[0..b-1], a%b=a?b+b?a
$ iff $ a?b=sum[a%i|i<-[0..b-1]], a%b=a?b+b?a
$ iff $ a?b=sum[a?i+i?a|i<-[0..b-1]]
– flawr
Nov 28 at 19:24
@PeterTaylor Sorry for the confusion, I somehow mixed up the two solutions. I think we can quite easily transform the two solutions into eachother: In the first step we can replace
map...
with a list comprehension, in the second step we just plug in the definition of %
: a?b=sum$map(a%)[0..b-1], a%b=a?b+b?a
$ iff $ a?b=sum[a%i|i<-[0..b-1]], a%b=a?b+b?a
$ iff $ a?b=sum[a?i+i?a|i<-[0..b-1]]
– flawr
Nov 28 at 19:24
|
show 3 more comments
up vote
7
down vote
CJam (24 bytes)
{2,*e!{e`0f=:(1b2#}%1b}
Online demo
This uses Bubbler's approach of summing over permutations of n
0s and n
1s.
Dissection
{ e# Define a block
2,* e# Given input n, create an array of n 0s and n 1s
e! e# Generate all permutations of that array
{ e# Map:
e` e# Run-length encode
0f=:( e# Extract just the lengths and decrement them
1b e# Sum
2# e# Raise 2 to the power of that sum
}%
1b e# Sum the mapped values
}
Alternative approach (28 bytes)
{_1aa{_2$,f{j}@@,f{j}+1b}2j}
Online demo
Dissection
The triangles all have one horizontal edge and two edges which link the horizontal lines. Label the non-horizontal edges by a tuple of their two x-coords and sort lexicographically. Then the first edge is (0,0)
, the last edge is (n,n)
, and two consecutive edges differ in precisely one of the two positions. This makes for a simple recursion, which I've implemented using the memoised recursion operator j
:
{ e# Define a block
_ e# Duplicate the argument to get n n
1aa e# Base case for recursion: 0 0 => 1
{ e# Recursive body taking args a b
_2$,f{j} e# Recurse on 0 b up to a-1 b
@@,f{j} e# Recurse on a 0 up to a b-1
+1b e# Combine and sum
}2j e# Memoised recursion with 2 args
}
Note
This is not the first time I've wanted fj
to be supported in CJam. Here it would bring the score down to 24 bytes also. Perhaps I should try to write a patch...
Yay, I beat you by 10 seconds, I don't think I was ever that close :)
– flawr
Nov 27 at 22:32
@flawr, I did consider posting before writing a dissection, but I thought I had time to knock it out quickly. Then I saw "New answer", so I deleted my part-written dissection, posted, and edited.
– Peter Taylor
Nov 27 at 22:34
1
Thanks for -5 bytes btw :D
– flawr
Nov 27 at 22:47
add a comment |
up vote
7
down vote
CJam (24 bytes)
{2,*e!{e`0f=:(1b2#}%1b}
Online demo
This uses Bubbler's approach of summing over permutations of n
0s and n
1s.
Dissection
{ e# Define a block
2,* e# Given input n, create an array of n 0s and n 1s
e! e# Generate all permutations of that array
{ e# Map:
e` e# Run-length encode
0f=:( e# Extract just the lengths and decrement them
1b e# Sum
2# e# Raise 2 to the power of that sum
}%
1b e# Sum the mapped values
}
Alternative approach (28 bytes)
{_1aa{_2$,f{j}@@,f{j}+1b}2j}
Online demo
Dissection
The triangles all have one horizontal edge and two edges which link the horizontal lines. Label the non-horizontal edges by a tuple of their two x-coords and sort lexicographically. Then the first edge is (0,0)
, the last edge is (n,n)
, and two consecutive edges differ in precisely one of the two positions. This makes for a simple recursion, which I've implemented using the memoised recursion operator j
:
{ e# Define a block
_ e# Duplicate the argument to get n n
1aa e# Base case for recursion: 0 0 => 1
{ e# Recursive body taking args a b
_2$,f{j} e# Recurse on 0 b up to a-1 b
@@,f{j} e# Recurse on a 0 up to a b-1
+1b e# Combine and sum
}2j e# Memoised recursion with 2 args
}
Note
This is not the first time I've wanted fj
to be supported in CJam. Here it would bring the score down to 24 bytes also. Perhaps I should try to write a patch...
Yay, I beat you by 10 seconds, I don't think I was ever that close :)
– flawr
Nov 27 at 22:32
@flawr, I did consider posting before writing a dissection, but I thought I had time to knock it out quickly. Then I saw "New answer", so I deleted my part-written dissection, posted, and edited.
– Peter Taylor
Nov 27 at 22:34
1
Thanks for -5 bytes btw :D
– flawr
Nov 27 at 22:47
add a comment |
up vote
7
down vote
up vote
7
down vote
CJam (24 bytes)
{2,*e!{e`0f=:(1b2#}%1b}
Online demo
This uses Bubbler's approach of summing over permutations of n
0s and n
1s.
Dissection
{ e# Define a block
2,* e# Given input n, create an array of n 0s and n 1s
e! e# Generate all permutations of that array
{ e# Map:
e` e# Run-length encode
0f=:( e# Extract just the lengths and decrement them
1b e# Sum
2# e# Raise 2 to the power of that sum
}%
1b e# Sum the mapped values
}
Alternative approach (28 bytes)
{_1aa{_2$,f{j}@@,f{j}+1b}2j}
Online demo
Dissection
The triangles all have one horizontal edge and two edges which link the horizontal lines. Label the non-horizontal edges by a tuple of their two x-coords and sort lexicographically. Then the first edge is (0,0)
, the last edge is (n,n)
, and two consecutive edges differ in precisely one of the two positions. This makes for a simple recursion, which I've implemented using the memoised recursion operator j
:
{ e# Define a block
_ e# Duplicate the argument to get n n
1aa e# Base case for recursion: 0 0 => 1
{ e# Recursive body taking args a b
_2$,f{j} e# Recurse on 0 b up to a-1 b
@@,f{j} e# Recurse on a 0 up to a b-1
+1b e# Combine and sum
}2j e# Memoised recursion with 2 args
}
Note
This is not the first time I've wanted fj
to be supported in CJam. Here it would bring the score down to 24 bytes also. Perhaps I should try to write a patch...
CJam (24 bytes)
{2,*e!{e`0f=:(1b2#}%1b}
Online demo
This uses Bubbler's approach of summing over permutations of n
0s and n
1s.
Dissection
{ e# Define a block
2,* e# Given input n, create an array of n 0s and n 1s
e! e# Generate all permutations of that array
{ e# Map:
e` e# Run-length encode
0f=:( e# Extract just the lengths and decrement them
1b e# Sum
2# e# Raise 2 to the power of that sum
}%
1b e# Sum the mapped values
}
Alternative approach (28 bytes)
{_1aa{_2$,f{j}@@,f{j}+1b}2j}
Online demo
Dissection
The triangles all have one horizontal edge and two edges which link the horizontal lines. Label the non-horizontal edges by a tuple of their two x-coords and sort lexicographically. Then the first edge is (0,0)
, the last edge is (n,n)
, and two consecutive edges differ in precisely one of the two positions. This makes for a simple recursion, which I've implemented using the memoised recursion operator j
:
{ e# Define a block
_ e# Duplicate the argument to get n n
1aa e# Base case for recursion: 0 0 => 1
{ e# Recursive body taking args a b
_2$,f{j} e# Recurse on 0 b up to a-1 b
@@,f{j} e# Recurse on a 0 up to a b-1
+1b e# Combine and sum
}2j e# Memoised recursion with 2 args
}
Note
This is not the first time I've wanted fj
to be supported in CJam. Here it would bring the score down to 24 bytes also. Perhaps I should try to write a patch...
edited Nov 28 at 11:25
answered Nov 27 at 22:30
Peter Taylor
38.9k453142
38.9k453142
Yay, I beat you by 10 seconds, I don't think I was ever that close :)
– flawr
Nov 27 at 22:32
@flawr, I did consider posting before writing a dissection, but I thought I had time to knock it out quickly. Then I saw "New answer", so I deleted my part-written dissection, posted, and edited.
– Peter Taylor
Nov 27 at 22:34
1
Thanks for -5 bytes btw :D
– flawr
Nov 27 at 22:47
add a comment |
Yay, I beat you by 10 seconds, I don't think I was ever that close :)
– flawr
Nov 27 at 22:32
@flawr, I did consider posting before writing a dissection, but I thought I had time to knock it out quickly. Then I saw "New answer", so I deleted my part-written dissection, posted, and edited.
– Peter Taylor
Nov 27 at 22:34
1
Thanks for -5 bytes btw :D
– flawr
Nov 27 at 22:47
Yay, I beat you by 10 seconds, I don't think I was ever that close :)
– flawr
Nov 27 at 22:32
Yay, I beat you by 10 seconds, I don't think I was ever that close :)
– flawr
Nov 27 at 22:32
@flawr, I did consider posting before writing a dissection, but I thought I had time to knock it out quickly. Then I saw "New answer", so I deleted my part-written dissection, posted, and edited.
– Peter Taylor
Nov 27 at 22:34
@flawr, I did consider posting before writing a dissection, but I thought I had time to knock it out quickly. Then I saw "New answer", so I deleted my part-written dissection, posted, and edited.
– Peter Taylor
Nov 27 at 22:34
1
1
Thanks for -5 bytes btw :D
– flawr
Nov 27 at 22:47
Thanks for -5 bytes btw :D
– flawr
Nov 27 at 22:47
add a comment |
up vote
4
down vote
Jelly, 15 14 bytes
Ø.xŒ!QŒɠ€’§2*S
Try it online!
-1 byte based on Peter Taylor's comment.
Uses flawr's illustration directly, instead of the resulting formula.
How it works
Ø.xŒ!QŒɠ€’§2*S Main link (monad). Input: positive integer N.
Ø.x Make an array containing N zeros and ones
Œ!Q All unique permutations
Œɠ€ Run-length encode on each permutation
’§ Decrement and sum each
2*S Raise to power of 2 and sum
Take every possible route on a square grid. The number of ways to move L units in one direction as a rook is 2**(L-1)
. Apply this to every route and sum the number of ways to traverse each route.
Nice approach. When I ported it to CJam it was shorter to decrement the lengths, sum, and then raise 2 to the sum; rather than raising 2 to the length, halving, and then multiplying. Don't know whether it might save you a byte.
– Peter Taylor
Nov 28 at 11:27
add a comment |
up vote
4
down vote
Jelly, 15 14 bytes
Ø.xŒ!QŒɠ€’§2*S
Try it online!
-1 byte based on Peter Taylor's comment.
Uses flawr's illustration directly, instead of the resulting formula.
How it works
Ø.xŒ!QŒɠ€’§2*S Main link (monad). Input: positive integer N.
Ø.x Make an array containing N zeros and ones
Œ!Q All unique permutations
Œɠ€ Run-length encode on each permutation
’§ Decrement and sum each
2*S Raise to power of 2 and sum
Take every possible route on a square grid. The number of ways to move L units in one direction as a rook is 2**(L-1)
. Apply this to every route and sum the number of ways to traverse each route.
Nice approach. When I ported it to CJam it was shorter to decrement the lengths, sum, and then raise 2 to the sum; rather than raising 2 to the length, halving, and then multiplying. Don't know whether it might save you a byte.
– Peter Taylor
Nov 28 at 11:27
add a comment |
up vote
4
down vote
up vote
4
down vote
Jelly, 15 14 bytes
Ø.xŒ!QŒɠ€’§2*S
Try it online!
-1 byte based on Peter Taylor's comment.
Uses flawr's illustration directly, instead of the resulting formula.
How it works
Ø.xŒ!QŒɠ€’§2*S Main link (monad). Input: positive integer N.
Ø.x Make an array containing N zeros and ones
Œ!Q All unique permutations
Œɠ€ Run-length encode on each permutation
’§ Decrement and sum each
2*S Raise to power of 2 and sum
Take every possible route on a square grid. The number of ways to move L units in one direction as a rook is 2**(L-1)
. Apply this to every route and sum the number of ways to traverse each route.
Jelly, 15 14 bytes
Ø.xŒ!QŒɠ€’§2*S
Try it online!
-1 byte based on Peter Taylor's comment.
Uses flawr's illustration directly, instead of the resulting formula.
How it works
Ø.xŒ!QŒɠ€’§2*S Main link (monad). Input: positive integer N.
Ø.x Make an array containing N zeros and ones
Œ!Q All unique permutations
Œɠ€ Run-length encode on each permutation
’§ Decrement and sum each
2*S Raise to power of 2 and sum
Take every possible route on a square grid. The number of ways to move L units in one direction as a rook is 2**(L-1)
. Apply this to every route and sum the number of ways to traverse each route.
edited Nov 28 at 23:21
answered Nov 28 at 0:42
Bubbler
6,179759
6,179759
Nice approach. When I ported it to CJam it was shorter to decrement the lengths, sum, and then raise 2 to the sum; rather than raising 2 to the length, halving, and then multiplying. Don't know whether it might save you a byte.
– Peter Taylor
Nov 28 at 11:27
add a comment |
Nice approach. When I ported it to CJam it was shorter to decrement the lengths, sum, and then raise 2 to the sum; rather than raising 2 to the length, halving, and then multiplying. Don't know whether it might save you a byte.
– Peter Taylor
Nov 28 at 11:27
Nice approach. When I ported it to CJam it was shorter to decrement the lengths, sum, and then raise 2 to the sum; rather than raising 2 to the length, halving, and then multiplying. Don't know whether it might save you a byte.
– Peter Taylor
Nov 28 at 11:27
Nice approach. When I ported it to CJam it was shorter to decrement the lengths, sum, and then raise 2 to the sum; rather than raising 2 to the length, halving, and then multiplying. Don't know whether it might save you a byte.
– Peter Taylor
Nov 28 at 11:27
add a comment |
up vote
3
down vote
Charcoal, 44 31 bytes
crossed out 44 is still regular 44
F⊕θ«≔⟦⟧ηF⊕θ⊞ηΣ∨⁺ηEυ§λκ¹⊞υη»I⊟⊟υ
Try it online! Explanation: Works by calculating the number of ways to partition a trapezium of opposite side lengths m,n
into triangles which all lie on integer offsets. This is simply a general case of the rectangle of size n
in the question. The number of partitions is given recursively as the sums of the numbers of partitions for all sides m,0..n-1
and n,0..m-1
. This is equivalent to generalised problem of the rooks, OEIS A035002. The code simply calculates the number of partitions working from 0,0
up to n,n
using the previously calculated values as it goes.
F⊕θ«
Loop over the rows 0..n
.
≔⟦⟧η
Start with an empty row.
F⊕θ
Loop over the columns in the row 0..n
.
⊞ηΣ∨⁺ηEυ§λκ¹
Take the row so far and the values in the previous rows at the current column, and add the sum total to the current row. However, if there are no values at all, then substitute 1
in place of the sum.
⊞υη»
Add the finished row to the list of rows so far.
I⊟⊟υ
Output the final value calculated.
add a comment |
up vote
3
down vote
Charcoal, 44 31 bytes
crossed out 44 is still regular 44
F⊕θ«≔⟦⟧ηF⊕θ⊞ηΣ∨⁺ηEυ§λκ¹⊞υη»I⊟⊟υ
Try it online! Explanation: Works by calculating the number of ways to partition a trapezium of opposite side lengths m,n
into triangles which all lie on integer offsets. This is simply a general case of the rectangle of size n
in the question. The number of partitions is given recursively as the sums of the numbers of partitions for all sides m,0..n-1
and n,0..m-1
. This is equivalent to generalised problem of the rooks, OEIS A035002. The code simply calculates the number of partitions working from 0,0
up to n,n
using the previously calculated values as it goes.
F⊕θ«
Loop over the rows 0..n
.
≔⟦⟧η
Start with an empty row.
F⊕θ
Loop over the columns in the row 0..n
.
⊞ηΣ∨⁺ηEυ§λκ¹
Take the row so far and the values in the previous rows at the current column, and add the sum total to the current row. However, if there are no values at all, then substitute 1
in place of the sum.
⊞υη»
Add the finished row to the list of rows so far.
I⊟⊟υ
Output the final value calculated.
add a comment |
up vote
3
down vote
up vote
3
down vote
Charcoal, 44 31 bytes
crossed out 44 is still regular 44
F⊕θ«≔⟦⟧ηF⊕θ⊞ηΣ∨⁺ηEυ§λκ¹⊞υη»I⊟⊟υ
Try it online! Explanation: Works by calculating the number of ways to partition a trapezium of opposite side lengths m,n
into triangles which all lie on integer offsets. This is simply a general case of the rectangle of size n
in the question. The number of partitions is given recursively as the sums of the numbers of partitions for all sides m,0..n-1
and n,0..m-1
. This is equivalent to generalised problem of the rooks, OEIS A035002. The code simply calculates the number of partitions working from 0,0
up to n,n
using the previously calculated values as it goes.
F⊕θ«
Loop over the rows 0..n
.
≔⟦⟧η
Start with an empty row.
F⊕θ
Loop over the columns in the row 0..n
.
⊞ηΣ∨⁺ηEυ§λκ¹
Take the row so far and the values in the previous rows at the current column, and add the sum total to the current row. However, if there are no values at all, then substitute 1
in place of the sum.
⊞υη»
Add the finished row to the list of rows so far.
I⊟⊟υ
Output the final value calculated.
Charcoal, 44 31 bytes
crossed out 44 is still regular 44
F⊕θ«≔⟦⟧ηF⊕θ⊞ηΣ∨⁺ηEυ§λκ¹⊞υη»I⊟⊟υ
Try it online! Explanation: Works by calculating the number of ways to partition a trapezium of opposite side lengths m,n
into triangles which all lie on integer offsets. This is simply a general case of the rectangle of size n
in the question. The number of partitions is given recursively as the sums of the numbers of partitions for all sides m,0..n-1
and n,0..m-1
. This is equivalent to generalised problem of the rooks, OEIS A035002. The code simply calculates the number of partitions working from 0,0
up to n,n
using the previously calculated values as it goes.
F⊕θ«
Loop over the rows 0..n
.
≔⟦⟧η
Start with an empty row.
F⊕θ
Loop over the columns in the row 0..n
.
⊞ηΣ∨⁺ηEυ§λκ¹
Take the row so far and the values in the previous rows at the current column, and add the sum total to the current row. However, if there are no values at all, then substitute 1
in place of the sum.
⊞υη»
Add the finished row to the list of rows so far.
I⊟⊟υ
Output the final value calculated.
edited Nov 28 at 0:25
answered Nov 28 at 0:02
Neil
78.6k744175
78.6k744175
add a comment |
add a comment |
up vote
2
down vote
JavaScript (ES6), 45 44 42 bytes
Uses the recursive formula found by Peter Taylor and flawr.
f=n=>n<2?n+1:(10-6/n)*f(--n)+9/~n*f(--n)*n
Try it online!
add a comment |
up vote
2
down vote
JavaScript (ES6), 45 44 42 bytes
Uses the recursive formula found by Peter Taylor and flawr.
f=n=>n<2?n+1:(10-6/n)*f(--n)+9/~n*f(--n)*n
Try it online!
add a comment |
up vote
2
down vote
up vote
2
down vote
JavaScript (ES6), 45 44 42 bytes
Uses the recursive formula found by Peter Taylor and flawr.
f=n=>n<2?n+1:(10-6/n)*f(--n)+9/~n*f(--n)*n
Try it online!
JavaScript (ES6), 45 44 42 bytes
Uses the recursive formula found by Peter Taylor and flawr.
f=n=>n<2?n+1:(10-6/n)*f(--n)+9/~n*f(--n)*n
Try it online!
edited Nov 28 at 6:49
answered Nov 27 at 23:06
Arnauld
70.8k688298
70.8k688298
add a comment |
add a comment |
up vote
2
down vote
Pari/GP, 43 bytes
According to OEIS, the generating function of this sequence is
$$frac{1}{2}left(sqrt{frac{1-x}{1-9x}}+1right)$$
n->Vec(sqrt((1-x)/(1-9*x)+O(x^n++))+1)[n]/2
Try it online!
add a comment |
up vote
2
down vote
Pari/GP, 43 bytes
According to OEIS, the generating function of this sequence is
$$frac{1}{2}left(sqrt{frac{1-x}{1-9x}}+1right)$$
n->Vec(sqrt((1-x)/(1-9*x)+O(x^n++))+1)[n]/2
Try it online!
add a comment |
up vote
2
down vote
up vote
2
down vote
Pari/GP, 43 bytes
According to OEIS, the generating function of this sequence is
$$frac{1}{2}left(sqrt{frac{1-x}{1-9x}}+1right)$$
n->Vec(sqrt((1-x)/(1-9*x)+O(x^n++))+1)[n]/2
Try it online!
Pari/GP, 43 bytes
According to OEIS, the generating function of this sequence is
$$frac{1}{2}left(sqrt{frac{1-x}{1-9x}}+1right)$$
n->Vec(sqrt((1-x)/(1-9*x)+O(x^n++))+1)[n]/2
Try it online!
edited Nov 28 at 13:53
answered Nov 28 at 9:49
alephalpha
21k32888
21k32888
add a comment |
add a comment |
up vote
1
down vote
Python 3, 51 bytes
lambda n:-~n*(n<2)or(10-6/n)*f(n-1)-(9-18/n)*f(n-2)
Try it online!
Port of flawr's answer
add a comment |
up vote
1
down vote
Python 3, 51 bytes
lambda n:-~n*(n<2)or(10-6/n)*f(n-1)-(9-18/n)*f(n-2)
Try it online!
Port of flawr's answer
add a comment |
up vote
1
down vote
up vote
1
down vote
Python 3, 51 bytes
lambda n:-~n*(n<2)or(10-6/n)*f(n-1)-(9-18/n)*f(n-2)
Try it online!
Port of flawr's answer
Python 3, 51 bytes
lambda n:-~n*(n<2)or(10-6/n)*f(n-1)-(9-18/n)*f(n-2)
Try it online!
Port of flawr's answer
edited Nov 27 at 23:17
answered Nov 27 at 23:11
lirtosiast
15.6k436107
15.6k436107
add a comment |
add a comment |
up vote
0
down vote
05AB1E, 13 bytes
·LÉœÙεÅγo;P}O
Port of @Bubbler's Jelly answer.
Very slow due to the permutations builtin.
Try it online or verify the first four inputs.
Explanation:
· # Double the (implicit) input
L # Create a list in the range [1, doubled_input]
É # Check for each if they're odd (1 if truthy, 0 is falsey)
# We now have a list of n 0s and n 1s (n being the input)
œ # Get all permutations of that list
Ù # Only leave the unique permutations
ε } # Map each permutation to:
Åγ # Run-length encode the current value (short for `γ€g`)
o # Take 2 to the power for each
; # Halve each
P # Take the product of the mapped permutation
O # Sum all mapped values together (and output implicitly)
add a comment |
up vote
0
down vote
05AB1E, 13 bytes
·LÉœÙεÅγo;P}O
Port of @Bubbler's Jelly answer.
Very slow due to the permutations builtin.
Try it online or verify the first four inputs.
Explanation:
· # Double the (implicit) input
L # Create a list in the range [1, doubled_input]
É # Check for each if they're odd (1 if truthy, 0 is falsey)
# We now have a list of n 0s and n 1s (n being the input)
œ # Get all permutations of that list
Ù # Only leave the unique permutations
ε } # Map each permutation to:
Åγ # Run-length encode the current value (short for `γ€g`)
o # Take 2 to the power for each
; # Halve each
P # Take the product of the mapped permutation
O # Sum all mapped values together (and output implicitly)
add a comment |
up vote
0
down vote
up vote
0
down vote
05AB1E, 13 bytes
·LÉœÙεÅγo;P}O
Port of @Bubbler's Jelly answer.
Very slow due to the permutations builtin.
Try it online or verify the first four inputs.
Explanation:
· # Double the (implicit) input
L # Create a list in the range [1, doubled_input]
É # Check for each if they're odd (1 if truthy, 0 is falsey)
# We now have a list of n 0s and n 1s (n being the input)
œ # Get all permutations of that list
Ù # Only leave the unique permutations
ε } # Map each permutation to:
Åγ # Run-length encode the current value (short for `γ€g`)
o # Take 2 to the power for each
; # Halve each
P # Take the product of the mapped permutation
O # Sum all mapped values together (and output implicitly)
05AB1E, 13 bytes
·LÉœÙεÅγo;P}O
Port of @Bubbler's Jelly answer.
Very slow due to the permutations builtin.
Try it online or verify the first four inputs.
Explanation:
· # Double the (implicit) input
L # Create a list in the range [1, doubled_input]
É # Check for each if they're odd (1 if truthy, 0 is falsey)
# We now have a list of n 0s and n 1s (n being the input)
œ # Get all permutations of that list
Ù # Only leave the unique permutations
ε } # Map each permutation to:
Åγ # Run-length encode the current value (short for `γ€g`)
o # Take 2 to the power for each
; # Halve each
P # Take the product of the mapped permutation
O # Sum all mapped values together (and output implicitly)
answered Nov 28 at 17:36
Kevin Cruijssen
34.9k554184
34.9k554184
add a comment |
add a comment |
If this is an answer to a challenge…
…Be sure to follow the challenge specification. However, please refrain from exploiting obvious loopholes. Answers abusing any of the standard loopholes are considered invalid. If you think a specification is unclear or underspecified, comment on the question instead.
…Try to optimize your score. For instance, answers to code-golf challenges should attempt to be as short as possible. You can always include a readable version of the code in addition to the competitive one.
Explanations of your answer make it more interesting to read and are very much encouraged.…Include a short header which indicates the language(s) of your code and its score, as defined by the challenge.
More generally…
…Please make sure to answer the question and provide sufficient detail.
…Avoid asking for help, clarification or responding to other answers (use comments instead).
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f176646%2fpartitioning-the-grid-into-triangles%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
10
Some additional test cases would be beneficial, so we can verify our submissions are correct.
– AdmBorkBork
Nov 27 at 21:19
8
You may want to specify non-degenerate triangles.
– Arnauld
Nov 27 at 21:24
I've made edits to OEIS sequence A051708 to reflect this interpretation.
– Peter Kagey
Nov 30 at 18:32