81
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 ...
49
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.)
answered Jun 9 '15 at 21:54
Martin Ender
188k6262 gold badges416416 silver badges923923 bronze badges
34
Mathematica, 11 bytes
PartitionsP
Explanation
¯\_(ツ)_/¯
31
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
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....
answered Jan 12 '17 at 12:16
Martin Ender
188k6262 gold badges416416 silver badges923923 bronze badges
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 ...
26
Ruby, 26 bytes
->n{~-n*12-496/4**n%4+1/n}
Try it online!
Revised version adding 1/n and subtracting 496/4**n%4 to get the +1,-3,-3,-1 offset for the first 4 terms.
Ruby, 32 bytes
->n{n>4?~-n*12:[0,1,9,21,35][n]}
Try it online!
After 4, the sequence settles down to (n-1)*12. See diagram below (the equilateral triangles have been distorted into ...
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,#}]&
24
APL (Dyalog Unicode), 39 bytes
+/⊢{∨/⍺⍵<⍵0:0⋄⍺=0:1⋄+/∊∇¨/⍺(⍵*2)-⊂⍳⍺}¨⍳
Try it online!
A tacit function containing an inner dfn to use recursion. Does not use floating point numbers at all.
How it works
First of all, observe that
$$
\displaystyle
\sqrt{a_1+\sqrt{a_2 + \cdots + \stackrel{\vdots}{\sqrt{a_t}}}} \le \cdots \le \sqrt{a_1+a_2 + \cdots + a_t} \...
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 ...
22
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 ...
20
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 ...
20
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.
20
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 ...
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 ...
answered Mar 26 '17 at 18:59
Martin Ender
188k6262 gold badges416416 silver badges923923 bronze badges
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}*{1,...
answered Sep 22 '14 at 23:19
Digital Trauma
66.2k77 gold badges9999 silver badges235235 bronze badges
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, 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.
answered Dec 10 '16 at 20:03
Jonathan Allan
78.9k55 gold badges5656 silver badges224224 bronze badges
16
J, 7,6 3 bytes
-1 byte thanks to FrownyFrog !
-3 bytes thanks to Grimmy!
*-+
Try it online!
- subtract
+ the sum of the arguments
* from their product
16
Scratch 3.0, 65 blocks / 637 632 bytes
Look at y'all, having fun with your fancy shmancy permutation functions/map tools. Well, not I! No, not I! When using Scratch, one has to do things themselves! You won't find any built-ins around these parts! I'm just glad there still ain't any gotos ;)
But more seriously, the image is split into 4 parts because it's ...
16
JavaScript (ES6), 116 112 107 bytes
Expects an array of entries in the following format: [[a,b,c,d], "XY"], where a to d are integers in [0..7], X is the number of correct digits and Y is the number of near-misses.
Returns 0 or 1.
f=(a,n)=>n>>12?0:!a.some(([a,x])=>!a.every(o=(d,i)=>o[x-=d^(v=n>>i*3&7)?a.includes(v):10,v]^...
15
Mathematica 16
Code
Subsets is native to Mathematica.
Column@Subsets@s
The code (without column) can be verified on WolframAlpha. (I had to use brackets instead of @; they mean the same thing.
Usage
s={1,2,3}
Column@Subsets@s
This method (55 chars) uses the approach suggested by @w0lf.
s #&/@Tuples[{0,1},Length@s]/.{0:>Sequence[]}//Column
...
15
APL, 7
In APL you can choose if you want to work with index 0 or index 1.
You do this by setting global variable ⎕IO←0
If we choose to work in index 0 we have:
+\3⌊1⌈⍳
Explanation:
⍳ creates a sequence 0...n (0 1 2 3 4 5)
1⌈ takes whichever is bigger, number in sequence or 1 (1 1 2 3 4 5)
3⌊ takes whichever is lower, number in sequence or 3 (1 ...
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, 0, 8, 0, 0, ...
Only top voted, non community-wiki answers of a minimum length are eligible
Related Tags
combinatorics × 304code-golf × 249
math × 69
sequence × 53
permutations × 35
fastest-code × 27
number × 24
grid × 22
code-challenge × 21
geometry × 21
string × 18
number-theory × 17
set-partitions × 15
integer-partitions × 13
graph-theory × 12
tiling × 11
array-manipulation × 10
arithmetic × 10
decision-problem × 9
polyomino × 9
random × 8
counting × 7
ascii-art × 6
game × 6
probability-theory × 6