21
\$\begingroup\$

Mash Up Time!

This is instalment #5 of both my Random Golf of the Day and Optimizer's ASCII Art of the Day series. Your submission(s) in this challenge will count towards both leaderboards (which you can find the linked posts). Of course, you may treat this like any other code golf challenge, and answer it without worrying about either series at all.

Hole 5: Diamond Tilings

A regular hexagon can always be tiled with diamonds like so:

We will use an ASCII art representation of these tilings. For a hexagon of side-length 2, there are 20 such tilings:

   ____     ____     ____     ____     ____     ____     ____     ____     ____     ____  
  /\_\_\   /\_\_\   /\_\_\   /\_\_\   /_/\_\   /_/\_\   /\_\_\   /_/\_\   /_/\_\   /_/\_\ 
 /\/\_\_\ /\/_/\_\ /\/_/_/\ /\/_/\_\ /\_\/\_\ /\_\/_/\ /\/_/_/\ /\_\/\_\ /\_\/_/\ /_/\/\_\
 \/\/_/_/ \/\_\/_/ \/\_\_\/ \/_/\/_/ \/\_\/_/ \/\_\_\/ \/_/\_\/ \/_/\/_/ \/_/\_\/ \_\/\/_/
  \/_/_/   \/_/_/   \/_/_/   \_\/_/   \/_/_/   \/_/_/   \_\/_/   \_\/_/   \_\/_/   \_\/_/ 
   ____     ____     ____     ____     ____     ____     ____     ____     ____     ____  
  /_/_/\   /\_\_\   /_/\_\   /_/_/\   /_/\_\   /_/\_\   /_/_/\   /_/_/\   /_/_/\   /_/_/\ 
 /\_\_\/\ /\/_/_/\ /_/\/_/\ /\_\_\/\ /\_\/_/\ /_/\/_/\ /_/\_\/\ /\_\_\/\ /_/\_\/\ /_/_/\/\
 \/\_\_\/ \/_/_/\/ \_\/\_\/ \/_/\_\/ \/_/_/\/ \_\/_/\/ \_\/\_\/ \/_/_/\/ \_\/_/\/ \_\_\/\/
  \/_/_/   \_\_\/   \_\/_/   \_\/_/   \_\_\/   \_\_\/   \_\/_/   \_\_\/   \_\_\/   \_\_\/ 

Given a side length N, you should generate such a tiling for a hexagon of side length N at random. The exact distribution doesn't matter, but each tiling must be returned with non-zero probability.

For N ≤ 4, your submission must produce a tiling within 1 minute at least 80% of the time and at least 80% of the tilings must potentially be generated within 1 minute. Most approaches won't have to worry about this rule (it's very lenient) - this is just to rule out very naive rejection-based algorithms that generate arbitrary strings until one happens to be a tiling.

You might like to know that the total number of possible tilings for given N can be found in OEIS A008793.

You may write a full program or a function and take input via STDIN (or closest alternative), command-line argument or function argument and produce output via STDOUT (or closest alternative), function return value or function (out) parameter.

You must not output more leading spaces than necessary to align the hexagon (that is the left corner of the hexagon should have no spaces in front of it). Each line may contain up to N trailing spaces (not necessarily consistently, so you could e.g. have a rectangular output, printing the hexagon's bounding box).

This is code golf, so the shortest submission (in bytes) wins. And of course, the shortest submission per user will also enter into the overall leaderboard of the series.

Leaderboards

The first post of each series generates a leaderboard.

To make sure that your answers show up, please start every answer with a headline, using the following Markdown template:

# Language Name, N bytes

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

# Ruby, <s>104</s> <s>101</s> 96 bytes

(The language is not currently shown, but the snippet does require and parse it, and I may add a by-language leaderboard in the future.)

\$\endgroup\$
  • 3
    \$\begingroup\$ Is it just me who keeps seeing the example image in 3D? \$\endgroup\$ – LegionMammal978 Jun 3 '15 at 22:06
  • 3
    \$\begingroup\$ @LegionMammal978 No that's perfectly normal. ;) (And is probably also a good way to approach the challenge.) \$\endgroup\$ – Martin Ender Jun 3 '15 at 22:07
  • \$\begingroup\$ For N ≤ 4, your submission must produce a tiling within 1 minute at least 80% of the time. too easy: 80% of time the same, basic tiling, otherwise I find another tiling in whatever time I want \$\endgroup\$ – edc65 Jun 4 '15 at 16:14
  • \$\begingroup\$ @edc65 Good point, let me rephrase that. \$\endgroup\$ – Martin Ender Jun 4 '15 at 16:15
10
\$\begingroup\$

CJam, 105 bytes

ri:A" __"e*A,2f*:B,[W1]{J+B:):B,{N1$S*"\/"J%A2*4$-:D*
0{;B{_1&!2mr+J*m1e>D(2*e<}%__:)&}g:B{'_t}/+@J+}*}fJ;

Newline added to avoid scrolling. Try it online

Explanation:

This solution starts each line as a zigzag, then places N underscores on it, based on their position on the previous line and a couple of rules. I got this from a series of observations while looking at the output as a plain 2D matrix of characters:

  • each line has exactly N underscores
  • the underscores can be replaced with / or \ to make a perfectly repeating zigzag pattern (/\ in the top half, \/ in the bottom half)
  • underscores can not touch the sides, and can't be adjacent to another underscore
  • when going to the next line, the position of each underscore changes by -1, 0 or 1
  • more than that, /_/ can only change by -1 or 0, and \_\ can only change by 0 or 1
  • for the initial underscore positions we can either use a "_ " pattern or a " _" pattern, both are fine
  • the above rules are sufficient to obtain all the tilings

So I decided to implement it by keeping the previous underscore positions, modifying them with a random factor (2 choices for each underscore) and repeating until the rules are satisfied. In the process of optimizing, I switched to underscore positions relative to the left side of the hexagon (not including spaces).

ri:A" __"e*       read the input (A) and generate the top line
A,2f*:B           make an array [0 2 4 ... 2A-2] and store in B
                  these are the initial positions for the underscores
,                 B's length = A, used as the initial number of leading spaces
                  let's call it C
[W1]{…}fJ         for J in [-1 1] (top half, bottom half)
  J+              add J to C
  B:):B           increment the underscore positions (adjustment before each half)
  ,{…}*           repeat A times
    N1$S*         add a newline and C spaces
    "\/"J%        take "\/" and reverse it if J=-1 (zigzag pattern)
    A2*4$-:D*     calculate D=A*2-C and repeat the pattern
    0             dummy value (for the next loop)
    {…}g          do-while
      ;B          pop last value and push B
      {…}%        apply block to each item (say x)
        _1&!      duplicate x and calculate !(x&1) (for /_/ vs \_\)
        2mr+      randomly add 0 or 1
        J*m       multiply by J and subtract from x
        1e>       limit the minimum value to 1
        D(2*e<    and the maximum value to 2*(D-1)
      __:)&       check if the modified array has any adjacent values
    :B            store the new positions in B
    {'_t}/        place underscores over the zigzag pattern
    +@J+          bring C to the top and add J to it
;                 pop C

Old "3D" version, 189 bytes:

ri:A" __"e*aA4*S*aA2**+[0-2XXW1]:C;"/\_\\\/_/":D;A3m*{{C2/.f*:.+~
A(2*+:V;A+:U;2{UI+1$1$=4{_V+D4/I=@=t}/t}fI}:F~}/[0Y1WWW]:C;
"/_/\\\_\/":D;AaA*:B;A{A[_{_BI=e<)mr}fI]:B;{BQ={[PQR]F}fR}fQ}fPN*

Try it online

\$\endgroup\$
  • \$\begingroup\$ +1 for awesome work and also because one more vote would put you at 10k rep, but mostly for the awesome work. (Oh hey, look at that. Congrats on 10k :) ) \$\endgroup\$ – Alex A. Jun 4 '15 at 18:42
  • \$\begingroup\$ A great analysis on the patterns! I'll use it for my answer. \$\endgroup\$ – anatolyg Jun 10 '15 at 11:07
6
\$\begingroup\$

Python 2, 337 335 324 318 311 300 296 bytes

from random import*
n=input()
R=range(n*2)
b=[]
l=[]
for i in R:o=abs(i-n)-(i<n);b+=[o];l+=[list(' '*o+'\//\\'[i<n::2]*(n*2-o))]
for i in R[:n]:
 o=1;p=n+i*2
 for j in R:r=randint(0,p<n*3+i*2-j);p+=(r or-1)*(o==r);q=p<=b[j];o=r|q;p+=q;l[j][p]='_';b[j]=p+1
for s in[' '*n+'__'*n]+l:print''.join(s)

The idea is to first create a hexagon of diamonds, like this:

  ____
 /\/\/\
/\/\/\/\
\/\/\/\/
 \/\/\/

And then fill it up with downward paths of underscores, like this:

  ____                          ____
 /_/\/\                        /\_\/\
/_/\/\/\    or maybe this:    /\/_/\/\
\_\/\/\/                      \/_/\/\/
 \_\/\/                        \_\/\/

The final result with all paths added would then look something like this:

  ____                          ____  
 /_/\_\                        /\_\_\ 
/_/\/_/\    or maybe this:    /\/_/\_\
\_\/_/\/                      \/_/\/_/
 \_\_\/                        \_\/_/ 

Quite a bit of code goes into making sure these paths don't go out of bounds or cross eachother.

The ungolfed code:

# Initialize l with all diamonds
blocked = []
l = [[] for _ in range(n*2)]
for i in range(n*2):
    offset = n-i-1 if i<n else i-n
    blocked.append(offset)
    l[i] += ' '*offset + ('/\\' if i<n else '\/')*(2*n - offset)

# Generate the random _'s
for i in range(n):
    oldright = True
    pos = n + i*2
    for j in range(n*2):
        # Go randomly right (true) or left (false), except when you out of bounds on the right side
        right = randint(0, 1) and pos < n*3 + i*2 - j
        if right == oldright:
            pos += 1 if right else -1
        if pos <= blocked[j]:
            right = True
            pos += 1
        l[j][pos] = '_'
        blocked[j] = pos + 1
        oldright = right

# Print the result
print ' '*n + '__'*n
for s in l:
    print ''.join(s)
\$\endgroup\$
  • 1
    \$\begingroup\$ I just noticed that your output seems wrong. You've got triangles in your two exaple results (top right and bottom right). \$\endgroup\$ – Martin Ender Jul 8 '16 at 9:58
  • 1
    \$\begingroup\$ @MartinEnder The examples showed only one 'path of underscores', to show the idea of the algorithm. The final output has all paths (in this case 2), which eliminates the triangles. I added in examples of the final output as well. \$\endgroup\$ – Matty Jul 20 '16 at 7:23
  • \$\begingroup\$ Ohhh I see, that makes sense. Thanks for the clarification. \$\endgroup\$ – Martin Ender Jul 20 '16 at 7:24
  • 2
    \$\begingroup\$ I think you can shorten randint(0,1)*(p<n*3+i*2-j) to randint(0,p<n*3+i*2-j). \$\endgroup\$ – 12Me21 Mar 6 '18 at 18:29
  • \$\begingroup\$ Oooh yes, thanks! \$\endgroup\$ – Matty Mar 8 '18 at 17:45
4
\$\begingroup\$

Perl, 174 168 166 161

#!perl -n
for$l(-$_..$_){$t=/_/?join'',map'/_'x($%=rand
1+(@z=/__?/g)).'/\\'.'_\\'x(@z-$%),split/\/\\/:__
x$_;$l>0&&$t!~s!^.(\\.*/).$!$1!?redo:print$"x abs$l-.5,$_=$t.$/}

Try me.

\$\endgroup\$
  • \$\begingroup\$ It always seems to generate the same tiling (at least on ideone) \$\endgroup\$ – aditsu Jun 4 '15 at 13:52
  • \$\begingroup\$ @aditsu, Ideone shows a cached result if you just click on the link. You need to fork to actually run it again. \$\endgroup\$ – nutki Jun 4 '15 at 13:57
2
\$\begingroup\$

JavaScript (ES6), 376 416 494

Just to be there ...

This build all the tilings, then choose a random one. Time for the 232848 tilings for N=4 is ~45 sec on my laptop. I did not try N=5.

Being EcmaScript 6 it runs on Firefox only.

F=n=>{
  for(i=s=r=b='';i<n;i++)
    s='\n'+b+'/\\'[R='repeat'](n-i)+'_\\'[R](n)+s,
    r+='\n'+b+'\\/'[R](n-i)+'_/'[R](n),
    b+=' ';
  for(h=[t=0],x=[s+r];s=x[t];t++)
    for(d='';!d[n*3];d+='.')
      if(l=s.match(r=RegExp("(\n"+d+"/)\\\\_(.*\n"+d+"\\\\)/_","g")))
        for(j=2<<l.length;j-=2;h[z]||(h[z]=x.push(z)))
          z=s.replace(r,(r,g,h)=>(k+=k)&j?g+'_/'+h+'_\\':r,k=1);
  return b+'__'[R](n)+x[Math.random()*t|0]
}


function go()
{
  var n = N.value | 0,
  t0 = performance.now(),
  r = F(n),
  t1 = performance.now();
  
  O.innerHTML = r+'\n\nTime (msec): '+(t1-t0)
}
N: <input id=N value=3><button onclick="go()">GO</button>
<pre id=O></pre>

\$\endgroup\$
  • \$\begingroup\$ In Chromium 42 I get "Uncaught SyntaxError: Unexpected token =>" and "Uncaught ReferenceError: go is not defined" \$\endgroup\$ – aditsu Jun 5 '15 at 11:51
  • 1
    \$\begingroup\$ @aditsu it's ES6, Chrome: no Firefox: yes. Isn't it a well known fact? \$\endgroup\$ – edc65 Jun 5 '15 at 12:13
  • \$\begingroup\$ I had no idea, I expected Chromium to use the latest and greatest whatever-its-called-apparently-not-javascript. Thanks for explaining. \$\endgroup\$ – aditsu Jun 5 '15 at 12:19
  • \$\begingroup\$ I ran it now in firefox (31.5.3) and it works for N=1, 2 or 3, but for N=4 it runs for about 10 sec, finishes and doesn't show anything (and there's no error in the console) \$\endgroup\$ – aditsu Jun 5 '15 at 12:29
  • \$\begingroup\$ @aditsu not sure ... maybe javascript in a sandbox is quietly killed when exceeds the time limit dom.max_script_run_time. It's a global preference in about:config, mine is set to 30. \$\endgroup\$ – edc65 Jun 5 '15 at 12:34
1
\$\begingroup\$

SmileBASIC, 241 bytes

INPUT N
T=N*2CLS?" "*N;"__"*N
DIM B[T]FOR I=-1TO N-1O=1P=N+I*2FOR J=0TO T-1IF I<0THEN O=ABS(J0N+.5)<<0B[J]=O?" "*O;MID$("\/\",J<N,2)*(T-O)ELSE R=P<N*3+I*2-J&&RND(2)P=P+(R*2-1)*(O==R)A=P<=B[J]R=R||A:P=P+A:LOCATE P,J+1?"_"B[J]=P+1O=R
NEXT
NEXT

Heavily based off of Matty's answer

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.