Random ASCII Art of the Day #5: Diamond Tilings

21

5

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

Martin Ender

Posted 2015-06-03T14:14:48.643

Reputation: 184 808

3Is it just me who keeps seeing the example image in 3D? – LegionMammal978 – 2015-06-03T22:06:39.017

3@LegionMammal978 No that's perfectly normal. ;) (And is probably also a good way to approach the challenge.) – Martin Ender – 2015-06-03T22:07:11.680

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 – edc65 – 2015-06-04T16:14:01.937

@edc65 Good point, let me rephrase that. – Martin Ender – 2015-06-04T16:15:59.160

Answers

10

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

aditsu quit because SE is EVIL

Posted 2015-06-03T14:14:48.643

Reputation: 22 326

+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 :) ) – Alex A. – 2015-06-04T18:42:23.307

A great analysis on the patterns! I'll use it for my answer. – anatolyg – 2015-06-10T11:07:40.520

6

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)

Matty

Posted 2015-06-03T14:14:48.643

Reputation: 471

1I just noticed that your output seems wrong. You've got triangles in your two exaple results (top right and bottom right). – Martin Ender – 2016-07-08T09:58:00.067

1@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. – Matty – 2016-07-20T07:23:46.427

Ohhh I see, that makes sense. Thanks for the clarification. – Martin Ender – 2016-07-20T07:24:34.443

2I think you can shorten randint(0,1)*(p<n*3+i*2-j) to randint(0,p<n*3+i*2-j). – 12Me21 – 2018-03-06T18:29:04.243

Oooh yes, thanks! – Matty – 2018-03-08T17:45:57.130

4

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.

nutki

Posted 2015-06-03T14:14:48.643

Reputation: 3 634

It always seems to generate the same tiling (at least on ideone) – aditsu quit because SE is EVIL – 2015-06-04T13:52:19.300

@aditsu, Ideone shows a cached result if you just click on the link. You need to fork to actually run it again. – nutki – 2015-06-04T13:57:20.180

2

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>

edc65

Posted 2015-06-03T14:14:48.643

Reputation: 31 086

In Chromium 42 I get "Uncaught SyntaxError: Unexpected token =>" and "Uncaught ReferenceError: go is not defined" – aditsu quit because SE is EVIL – 2015-06-05T11:51:05.020

1@aditsu it's ES6, Chrome: no Firefox: yes. Isn't it a well known fact? – edc65 – 2015-06-05T12:13:11.597

I had no idea, I expected Chromium to use the latest and greatest whatever-its-called-apparently-not-javascript. Thanks for explaining. – aditsu quit because SE is EVIL – 2015-06-05T12:19:34.810

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) – aditsu quit because SE is EVIL – 2015-06-05T12:29:36.690

@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. – edc65 – 2015-06-05T12:34:51.050

What do you know.. mine was set to 10 :) Changed it to 60 now and it worked (took about 22 sec). – aditsu quit because SE is EVIL – 2015-06-05T13:07:12.437

1

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

12Me21

Posted 2015-06-03T14:14:48.643

Reputation: 6 110