22
\$\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\$
4
  • 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\$
2
  • \$\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\$
5
  • 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
5
\$\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\$
2
  • \$\begingroup\$ It always seems to generate the same tiling (at least on ideone) \$\endgroup\$ – aditsu quit because SE is EVIL 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
3
\$\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\$
6
  • \$\begingroup\$ In Chromium 42 I get "Uncaught SyntaxError: Unexpected token =>" and "Uncaught ReferenceError: go is not defined" \$\endgroup\$ – aditsu quit because SE is EVIL 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 quit because SE is EVIL 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 quit because SE is EVIL 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\$
1
\$\begingroup\$

x86 machine code, 155 bytes

Hexdump:

60 8b fa 51 b0 20 f3 aa 59 51 b0 5f 03 c9 f3 aa
5e b0 0a aa 57 5f 57 b7 2f 8d 14 36 8b ce 2b ca
75 03 80 f7 73 7d 02 f7 d1 51 b0 20 f3 aa 59 8a
c7 aa 8b ee 53 6b d9 fe 8d 5c b3 ff 53 6b de fc
8b 5c 1f fe 8b 47 fe 80 fc 5f 74 23 8a c4 34 73
3c 2f 75 0a 80 ff 5f 74 3e 80 ff 5c 74 37 c1 eb
08 66 81 fb 2f 5c 74 2f 0f c7 f3 d1 eb 72 24 aa
3c 5f 75 01 4d 5b 4b 75 c3 5b 85 ed 75 97 32 c7
3c 73 75 91 b0 20 f3 aa b0 0a aa 4a 75 8e 88 17
5f 61 c3 b3 5f 8a fb 8a c7 eb d4

Explanation:

It's a fastcall function. It takes the size of the hexagon, n, in ecx, and a pointer to output string in edx.

First of all, it prints the first line: a few spaces and a few underscores. Then, it goes into a double loop: outer loop of lines, and inner loop of chars.

Each line starts with a few spaces and a border char (either / or \, depending on whether we are in upper or lower half of the output). Last chars in each line are spaces and a newline byte. The chars in the middle are generated according to the following rules. They guarantee that the output is a valid tiling.

  1. If previous char is _, current char must be the same as the one to the left of it:

    (case 1) /_/
    
    (case 2) \_\
    
  2. If previous char is \ and upper char is _, current char must be _:

     _
    \_
    
  3. If previous and upper chars are \, current char must be equal to upper-left char:

    (case 1) _\
             \_
    
    (case 2) /\
             \/
    
  4. If upper char is / and upper-right char is \, current char must be \:

    /\
    \
    
  5. If none of the above holds, choose one of the following two possibilities for current char randomly:

    • Underscore _
    • Slash with opposite direction from the previous slash: /\ or \/

To implement these rules, it loads 4 bytes from the upper line into ebx and 4 bytes from current line into eax. Then, ah is the previous char, while al is the one preceding it. Also, bl is the upper-left char, bh is the upper char, and the byte in ebx above bh is the upper-right char. After taking into account the upper-left char, it shifts ebx right by 8 bits so the upper-right char becomes accessible in bh.

To flip the direction of a slash, it does XOR with 0x73.

After finishing a line, it checks two conditions:

  1. Last char must be a slash in the appropriate direction (opposite to the direction of the first slash in line)
  2. There must be exactly n underscores in the line

If either condition is violated, it starts over from first line. So for large n, the output will be very slow, because successful execution requires luck in each line. The following example output for n = 8 takes about a minute to calculate:

        ________________
       /_/_/_/\_\_\_\_\_\
      /_/_/_/\/_/\_\_\_\_\
     /_/_/\_\/\_\/_/_/_/\_\
    /_/_/\/\_\/_/_/_/_/\/_/\
   /_/\_\/\/_/_/_/\_\_\/_/\/\
  /\_\/\_\/_/\_\_\/_/_/_/\/\/\
 /\/_/\/_/\_\/_/\_\_\_\_\/\/\/\
/\/\_\/_/\/_/\_\/_/_/\_\_\/\/\/\
\/\/_/\_\/\_\/\_\_\_\/\_\_\/\/\/
 \/_/\/_/\/\_\/_/_/_/\/_/\_\/\/
  \_\/_/\/\/_/_/_/\_\/_/\/_/\/
   \_\_\/\/_/\_\_\/\_\_\/_/\/
    \_\_\/_/\/\_\_\/_/_/_/\/
     \_\_\_\/\/_/_/_/_/_/\/
      \_\_\_\/_/\_\_\_\_\/
       \_\_\_\_\/_/_/_/_/

Here is assembly source code mixed with disassembly. I took it while stopped at a breakpoint in Visual Studio.

        pushad;
10014190 60                   pushad  
        mov edi, edx;
10014191 8B FA                mov         edi,edx  

        push ecx;
10014193 51                   push        ecx  
        mov al, ' ';
10014194 B0 20                mov         al,20h  
        rep stosb;
10014196 F3 AA                rep stos    byte ptr es:[edi]  
        pop ecx;
10014198 59                   pop         ecx  

        push ecx;
10014199 51                   push        ecx  
        mov al, '_';
1001419A B0 5F                mov         al,5Fh  
        add ecx, ecx;
1001419C 03 C9                add         ecx,ecx  
        rep stosb;
1001419E F3 AA                rep stos    byte ptr es:[edi]  
        pop esi; // esi = n
100141A0 5E                   pop         esi  

        mov al, '\n';
100141A1 B0 0A                mov         al,0Ah  
        stosb;
100141A3 AA                   stos        byte ptr es:[edi]  

        push edi;
100141A4 57                   push        edi  
    again:
        pop edi;
100141A5 5F                   pop         edi  
        push edi;
100141A6 57                   push        edi  

        mov bh, '/'; // bh = first char in line
100141A7 B7 2F                mov         bh,2Fh  
        lea edx, [esi + esi]; // edx = line index
100141A9 8D 14 36             lea         edx,[esi+esi]  

    line_loop:
        mov ecx, esi;
100141AC 8B CE                mov         ecx,esi  
        sub ecx, edx;
100141AE 2B CA                sub         ecx,edx  
        jnz skip1;
100141B0 75 03                jne         doit+25h (100141B5h)  
        xor bh, '\\' ^ '/';
100141B2 80 F7 73             xor         bh,73h  
    skip1:
        jge skip2;
100141B5 7D 02                jge         doit+29h (100141B9h)  
        not ecx;    // ecx = spaces before and after chars
100141B7 F7 D1                not         ecx  
    skip2:

        push ecx;
100141B9 51                   push        ecx  
        mov al, ' ';
100141BA B0 20                mov         al,20h  
        rep stosb;
100141BC F3 AA                rep stos    byte ptr es:[edi]  
        pop ecx;
100141BE 59                   pop         ecx  

        mov al, bh;
100141BF 8A C7                mov         al,bh  
        stosb;
100141C1 AA                   stos        byte ptr es:[edi]  

        mov ebp, esi; // ebp = underscore counter
100141C2 8B EE                mov         ebp,esi  

        push ebx;
100141C4 53                   push        ebx  
        imul ebx, ecx, -2;
100141C5 6B D9 FE             imul        ebx,ecx,0FFFFFFFEh  
        lea ebx, [ebx + 4 * esi - 1]; // ebx = char counter
100141C8 8D 5C B3 FF          lea         ebx,[ebx+esi*4-1]  

    i_loop:
        push ebx;
100141CC 53                   push        ebx  

        imul ebx, esi, -4;
100141CD 6B DE FC             imul        ebx,esi,0FFFFFFFCh  
        mov ebx, [edi + ebx - 2];
100141D0 8B 5C 1F FE          mov         ebx,dword ptr [edi+ebx-2]  
        mov eax, [edi - 2];
100141D4 8B 47 FE             mov         eax,dword ptr [edi-2]  

        cmp ah, '_';
100141D7 80 FC 5F             cmp         ah,5Fh  
        je x_done;
100141DA 74 23                je          doit+6Fh (100141FFh)  
        mov al, ah;
100141DC 8A C4                mov         al,ah  
        xor al, '/' ^ '\\';
100141DE 34 73                xor         al,73h  

        cmp al, '/';
100141E0 3C 2F                cmp         al,2Fh  
        jne al_diff;
100141E2 75 0A                jne         doit+5Eh (100141EEh)  

        cmp bh, '_';
100141E4 80 FF 5F             cmp         bh,5Fh  
        je mov_al_bh;
100141E7 74 3E                je          skip5+22h (10014227h)  

        cmp bh, '\\';
100141E9 80 FF 5C             cmp         bh,5Ch  
        je mov_al_bl;
100141EC 74 37                je          skip5+20h (10014225h)  

    al_diff:
        shr ebx, 8;
100141EE C1 EB 08             shr         ebx,8  
        cmp bx, '\\' << 8 | '/';
100141F1 66 81 FB 2F 5C       cmp         bx,5C2Fh  
        je mov_al_bh;
100141F6 74 2F                je          skip5+22h (10014227h)  

        rdrand ebx;
100141F8 0F C7 F3             rdrand      ebx  
        shr ebx, 1;
100141FB D1 EB                shr         ebx,1  
        jc mov_al_underscore;
100141FD 72 24                jb          skip5+1Eh (10014223h)  

    x_done:
        stosb;
100141FF AA                   stos        byte ptr es:[edi]  
        cmp al, '_';
10014200 3C 5F                cmp         al,5Fh  
        jne skip5;
10014202 75 01                jne         skip5 (10014205h)  
        dec ebp;
10014204 4D                   dec         ebp  

    skip5:
        pop ebx;
10014205 5B                   pop         ebx  
        dec ebx;
10014206 4B                   dec         ebx  
        jnz i_loop;
10014207 75 C3                jne         doit+3Ch (100141CCh)  

        pop ebx;
10014209 5B                   pop         ebx  
        test ebp, ebp;
1001420A 85 ED                test        ebp,ebp  
        jne again;
1001420C 75 97                jne         doit+15h (100141A5h)  
        xor al, bh;
1001420E 32 C7                xor         al,bh  
        cmp al, '/' ^ '\\';
10014210 3C 73                cmp         al,73h  
        jne again;
10014212 75 91                jne         doit+15h (100141A5h)  

        mov al, ' ';
10014214 B0 20                mov         al,20h  
        rep stosb;
10014216 F3 AA                rep stos    byte ptr es:[edi]  

        mov al, '\n';
10014218 B0 0A                mov         al,0Ah  
        stosb;
1001421A AA                   stos        byte ptr es:[edi]  

        dec edx;
1001421B 4A                   dec         edx  
        jne line_loop;
1001421C 75 8E                jne         doit+1Ch (100141ACh)  

        mov [edi], dl; // terminating zero byte
1001421E 88 17                mov         byte ptr [edi],dl  

        pop edi;
10014220 5F                   pop         edi  
        popad;
10014221 61                   popad  
        ret;
10014222 C3                   ret  

    mov_al_underscore:
        mov bl, '_';
10014223 B3 5F                mov         bl,5Fh  
    mov_al_bl:
        mov bh, bl;
10014225 8A FB                mov         bh,bl  
    mov_al_bh:
        mov al, bh;
10014227 8A C7                mov         al,bh  
        jmp x_done;
10014229 EB D4                jmp         doit+6Fh (100141FFh)  

Here is C++ code which I used to develop my assembly code:

#include <stdio.h>
#include <iostream>
#include <random>
#include <set>
#include <string>

#define MY 1

std::random_device rd;
std::mt19937 gen(rd());
std::bernoulli_distribution distr(0.5);

#if MY
__declspec(naked) void __fastcall doit(int, char*)
{
    _asm {
        pushad;
        mov edi, edx;

        push ecx;
        mov al, ' ';
        rep stosb;
        pop ecx;

        push ecx;
        mov al, '_';
        add ecx, ecx;
        rep stosb;
        pop esi; // esi = n

        mov al, '\n';
        stosb;

        push edi;
    again:
        pop edi;
        push edi;

        mov bh, '/'; // bh = first char in line
        lea edx, [esi + esi]; // edx = line index

    line_loop:
        mov ecx, esi;
        sub ecx, edx;
        jnz skip1;
        xor bh, '\\' ^ '/';
    skip1:
        jge skip2;
        not ecx;    // ecx = spaces before and after chars
    skip2:

        push ecx;
        mov al, ' ';
        rep stosb;
        pop ecx;

        mov al, bh;
        stosb;

        mov ebp, esi; // ebp = underscore counter

        push ebx;
        imul ebx, ecx, -2;
        lea ebx, [ebx + 4 * esi - 1]; // ebx = char counter

    i_loop:
        push ebx;

        imul ebx, esi, -4;
        mov ebx, [edi + ebx - 2];
        mov eax, [edi - 2];

        cmp ah, '_';
        je x_done;
        mov al, ah;
        xor al, '/' ^ '\\';

        cmp al, '/';
        jne al_diff;

        cmp bh, '_';
        je mov_al_bh;

        cmp bh, '\\';
        je mov_al_bl;

    al_diff:
        shr ebx, 8;
        cmp bx, '\\' << 8 | '/';
        je mov_al_bh;

        rdrand ebx;
        shr ebx, 1;
        jc mov_al_underscore;

    x_done:
        stosb;
        cmp al, '_';
        jne skip5;
        dec ebp;

    skip5:
        pop ebx;
        dec ebx;
        jnz i_loop;

        pop ebx;
        test ebp, ebp;
        jne again;
        xor al, bh;
        cmp al, '/' ^ '\\';
        jne again;

        mov al, ' ';
        rep stosb;

        mov al, '\n';
        stosb;

        dec edx;
        jne line_loop;

        mov [edi], dl; // terminating zero byte

        pop edi;
        popad;
        ret;

    mov_al_underscore:
        mov bl, '_';
    mov_al_bl:
        mov bh, bl;
    mov_al_bh:
        mov al, bh;
        jmp x_done;
    }
}
#else // not MY
void doit(int n, char* s)
{
    for (int i = 0; i < n; ++i)
        *s++ =' ';
    for (int i = 0; i < n * 2; ++i)
        *s++ ='_';
    *s++ ='\n';
    char* save = s;
again:
    for (int line = 2 * n; line > 0; --line)
    {
        int spaces = n - line;
        char border1 = '\\';
        if (n - line < 0)
        {
            border1 = '/';
            spaces = ~spaces;
        }
        for (int i = 0; i < spaces; ++i)
            *s++ = ' ';
        *s++ = border1;
        int check = n;
        for (int i = 4 * n - 1 - 2 * spaces; i; --i)
        {
            char al = s[-2];
            char ah = s[-1];
            char bl = s[-4 * n - 2];
            char bh = s[-4 * n - 1];
            char bk = s[-4 * n - 0];

            if (ah == '_')
                goto x_done;
            al = ah ^ '/' ^ '\\';
            if (al != '/')
                goto al_diff;
            if (bh == '_')
            {
                al = bh;
                goto x_done;
            }
            else if (bh == '\\')
            {
                al = bl;
                goto x_done;
            }

        al_diff:
            bl = bh;
            bh = bk;
            if (bl == '/' && bh == '\\')
            {
                al = bh;
            }
            else if (distr(gen))
            {
                al = '_';
            }

        x_done:
            *s++ = al;
            if (al == '_')
                --check;
        }
        if (check)
        {
            s = save;
            goto again;
        }
        if (s[-1] != (border1 ^ '/' ^ '\\'))
        {
            s = save;
            goto again;
        }
        for (int i = 0; i < spaces; ++i)
            *s++ = ' ';
        *s++ ='\n';
    }
    *s++ ='\0';
}
#endif // MY

int main(void)
{
    char s[1000];
    std::set<std::string> results;
    while (true)
    {
        doit(3, s);
        if (!results.count(s))
        {
            puts(s);
            results.insert(s);
            std::cout << results.size() << '\n';
        }
    }
}
\$\endgroup\$
2
  • \$\begingroup\$ What are distr and gen? \$\endgroup\$ – S.S. Anne Mar 22 '20 at 0:19
  • 1
    \$\begingroup\$ Oops, I forgot - I had to change random number generation to C++ because rand() wasn't good enough. I added my whole testing environment to make it clearer. \$\endgroup\$ – anatolyg Mar 22 '20 at 8:14

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.