79
Algebra, graph theory, Möbius inversion, research, and Java
The symmetry group of the hexagon is the dihedral group of order 12, and is generated by a 60 degree rotation and a mirror flip across a diameter. It has 16 subgroups, but some of them are in non-trivial conjugacy groups (the ones which only have reflections have 3 choices of axis), so there are 10 ...
46
Python 2, 43 bytes
f=lambda n,k=1:k/n or n*f(n,k+1)+k*f(n-1,k)
Try it online!
A different approach
Ever since I posted this challenge, I tried to come up with a recursive solution to this problem. While I failed using nothing more than pen and paper, I managed to turn the formula to golf into a practical problem – at least for certain definitions of ...
34
Mathematica, 25 bytes
Image/@{0,1}~Tuples~{3,3}
Gives an array with all the grids as images, which is also directly displayed on screen:
(Cropped so as not to blow up the post unnecessarily.)
34
Mathematica, 11 bytes
PartitionsP
Explanation
¯\_(ツ)_/¯
30
J, 12 characters
":@(!{:)\@i.
i.5
0 1 2 3 4
{:i.5
4
(i.5)!{:i.5
1 4 6 4 1
(!{:)i.5
1 4 6 4 1
(!{:)\i.5
1 0 0 0 0
1 1 0 0 0
1 2 1 0 0
1 3 3 1 0
1 4 6 4 1
":@(!{:)\i.5
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
(":@(!{:)\@i.)`''
+----------------------------------+
|+-+------------------------------+|
||@|+-------------------------+--+||
|| ||+-+-----...
30
34 Languages, 19 bytes, Score: 38,832,018,459,912,437,760,000
Here is a quick answer I threw together to show that it is possible to get an answer scoring better than 1.
12233echo*+--@#..;
1. NTFJ
#*22331+..@o;-- ech
This outputs via character code, which is allowed by meta consensus.
Try it here
2. Tcsh
echo 2;#..1@2+33*--
3. 05AB1E
2231*+..@echo ...
answered May 9 '17 at 20:02
Sriotchilism O'Zaic
37.4k10 gold badges168 silver badges382 bronze badges
28
Mathematica, 72 65 61 bytes
Print@@@Tuples@{a=##/(b=#5#9#15#21#25#)&@@Alphabet[],b,a,b,a}
For testing, I recommend replacing Print@@@ with ""<>#&/@. Mathematica will then display a truncated form showing the first few and last few words, instead of taking forever to print 288,000 lines.
Explanation
I finally found a use for dividing strings....
26
C, 78 52 39 34 33 bytes
Even more C magic (thanks xsot):
c(n){return!n?:(4+6./~n)*c(n-1);}
?: is a GNU extension.
This time by expanding the recurrence below (thanks xnor and Thomas Kwa):
c(n){return n?(4+6./~n)*c(n-1):1;}
-(n+1) is replaced by ~n, which is equivalent in two's complement and saves 4 bytes.
Again as a function, but this time exploiting ...
25
Mathematica, 40 28 23 22 bytes
Using the famous formula n*ζ(1−n)=−Bn, where ζ is the Riemann Zeta function.
If[#>0,-Zeta[1-#]#,1]&
The same length:
B@0=1;B@n_=-Zeta[1-n]n
Original solution, 40 bytes, using the generating function of Bernoulli numbers.
#!SeriesCoefficient[t/(1-E^-t),{t,0,#}]&
23
Jelly, 4 bytes
Ḥc÷‘
Try it online!
How it works
Ḥc÷‘ Left argument: z
Ḥ Compute 2z.
c Hook; apply combinations to 2z and z.
÷‘ Divide the result by z+1.
23
Haskell, 25 24 23 17 bytes
mapM$min"^v".pure
Try it online!
-1 byte thanks to @H.PWiz
-1 byte thanks to @nimi
Returns a list of strings. The TIO has 2 extra bytes for the function declaration - I've seen other people leave it off when they write the function pointfree so I'm doing the same unless told otherwise.
Previous Answer (25 bytes)
g 'v'="v^"
g ...
21
Jelly, 7 6 bytes
;_/!:/
Look ma, no Unicode! This program takes a single list as input, with n at its first index.
Try it online! or verify all test cases at once.
How it works
;_/!:/ Input: A (list)
_/ Reduce A by subtraction. This subtracts all other elements from the first.
; Concatenate A with the result to the right.
! Apply ...
19
Python (59 57 56 bytes)
lambda n:0**n+sum((-(n%(x-~x)<1))**x*4for x in range(n))
Online demo
As with my CJam answer, this uses Möbius inversion and runs in pseudoquasilinear time.
Thanks to Sp3000 for 2 bytes' savings, and feersum for 1.
19
Smalltalk, 1098 primes
First off, nice hard question - as evidenced by the lack of non-trivial responses thus far.
I had a solution cooking at work, but had to wait for the long weekend to have time to clean it up a bit. Even so, it's quite "heavy", so excuse the length of this answer - thankfully this isn't a code-golf question. There were plenty of ...
19
Funciton, 336 bytes
Byte count assumes UTF-16 encoding with BOM.
┌─╖┌─╖ ┌─╖
│f╟┤♭╟┐┌┤♭╟┐
╘╤╝╘═╝├┘╘═╝├────┐
│┌─╖ │ ┌┐┌┘╔═╗╓┴╖
││f╟─┴┐└┴┼─╢0║║f║
│╘╤╝ │ │ ╚═╝╙─╜
│┌┴╖ ┌┴╖┌┴╖ ╔═╗
││+╟┐│×╟┤?╟┐║1║
│╘╤╝│╘╤╝╘╤╝┘╚╤╝
└─┘ └─┘ └───┘
This defines a function f which takes one integer and outputs another integer at a 90 degree turn to the left. It works for ...
19
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 ...
18
Pure Bash, 32 bytes
eval echo \$[{1,${1// /\}*{1,}}]
Reads input list (single space separated) passed as a command-line arg.
Three different shell expansions are used:
${1// /\}*{1,} is a parameter expansion that replaces spaces in 2 3 5 7 with }*{1, to give 2}*{1,3}*{1,5}*{1,7. \$[{1, and }] are added to the start and end respectively to give \$[{1,2}*{...
18
CJam (56 bytes)
q~4@:Nm*:$_&{:+1$\-N),&},f{1$1$:+-\0-:(_e`0f=+++:m!:/}:+
Online demo
This is an optimised version of the reference implementation I wrote for the sandbox. Note: I use N in the code because in a Real Combinatorics Question™ the parameters are \$n\$ and \$k\$, not m and n, but I'll use \$M\$ and \$N\$ in the explanation to ...
18
Haskell, 37 34 bytes
s#l@(c:d)|s>=c=(s-c)#l+s#d
s#_=0^s
Usage example: 26 # [1,5,10,25] -> 13.
Simple recursive approach: try both the next number in the list (as long as it is less or equal to the amount) and skip it. If subtracting the number leads to an amount of zero, take a 1 else (or if the list runs out of elements) take a 0. Sum those 1s and 0s....
17
Python, 56 Bytes
a=[1];exec"print a;a=map(sum,zip([0]+a,a+[0]));"*input()
Sample usage:
echo 9 | python filename.py
Produces:
[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]
[1, 6, 15, 20, 15, 6, 1]
[1, 7, 21, 35, 35, 21, 7, 1]
[1, 8, 28, 56, 70, 56, 28, 8, 1]
16
Python, 52
Input is a set. Output is a list of lists.
f=lambda a:[p+[x]for x in a for p in f(a-{x})]or[[]]
This is shorter than the answer that does all the work with a builtin.
16
K, 11 bytes
(3 3#)'!9#2
Output example:
((0 0 0
0 0 0
0 0 0)
(0 0 0
0 0 0
0 0 1)
(0 0 0
0 0 0
0 1 0)
(0 0 0
0 0 0
0 1 1)
…
This is K's native prettyprinted representation of a list of matrices, which I think is sufficient for the problem spec. Each matrix is delimited by an enclosing set of parentheses.
And a quick sanity check to ...
16
Jelly, 1 byte
ṗ
TryItOnline
Cartesian power built-in atom, as a dyadic link with left argument the items and right argument the count, or as a full program with first argument the items and second argument the count.
15
Python, 94 91 88 70 63 characters
x=[1]
for i in input()*x:
print x
x=map(sum,zip([0]+x,x+[0]))
15
C
Introduction
As commented by David Carraher, the simplest way of analysing the hexagon tiling seemed to be to take advantage of its isomorphism with the 3 dimensional Young Diagram, essentially an x,y square filled with integer height bars whose z heights must stay the same or increase as the z axis is approached.
I started with an algorithm for finding ...
15
Mathematica, 13 bytes
If built-ins are allowed, this is how to do it in Mathematica.
2~SquaresR~#&
For 0 < = n <= 100
2~SquaresR~# & /@ Range[0, 100]
{1, 4, 4, 0, 4, 8, 0, 0, 4, 4, 8, 0, 0, 8, 0, 0, 4, 8, 4, 0, 8, 0, 0,
0, 0, 12, 8, 0, 0, 8, 0, 0, 4, 0, 8, 0, 4, 8, 0, 0, 8, 8, 0, 0, 0, 8,
0, 0, 0, 4, 12, 0, 8, 8, 0, 0, 0, 0, 8, 0, ...
15
MATL, 13 14 bytes
i-2/t.5+hH4Zh
Example:
>> matl i-2/t.5+hH4Zh
> 6
51
EDIT (June 16, 2017): you can try it online! Note also that in modern versions of the language (that post-date this challenge) the i could be removed.
Explanation
Pretty straightforward, using the equivalence (see equation (10)) with the hypergeometric function:
From the ...
15
Mathematica, 35 22 bytes
Thanks to miles for suggesting FrobeniusSolve and saving 13 bytes.
Length@*FrobeniusSolve
Evaluates to an unnamed function, which takes the list of coins as the first argument and the target value as the second. FrobeniusSolve is a shorthand for solving Diophantine equations of the form
a1x1 + a2x2 + ... + anxn = b
for the xi ...
15
Perl, 47 bytes
#!perl -l
/((^|[aeiouy])[^aeiouy]){3}/&&print for a..1x5
Counting the shebang as one.
Try it online!
14
Mathematica: 36 (41?)
Mathematica has the Binomial function, but that takes the fun out of this. I propose:
NestList[{0,##}+{##,0}&@@#&,{1},n-1]
The line above will render a ragged array such as:
{{1}, {1, 1}, {1, 2, 1}, {1, 3, 3, 1}, {1, 4, 6, 4, 1},
{1, 5, 10, 10, 5, 1}, {1, 6, 15, 20, 15, 6, 1}}
Since this is a basic format in Mathematica I ...
Only top voted, non community-wiki answers of a minimum length are eligible
