34
\$\begingroup\$

Overview

Write a program that prints out simple fractal patterns given a bit pattern encoding the fractal, plus the per-generation scale factor of the fractal and number of generations.

Explanation

Here is an ASCII representation of the Sierpinski Carpet:

Generation 0:

# 

Generation 1:

# # # 
#   # 
# # # 

Generation 2:

# # # # # # # # # 
#   # #   # #   # 
# # # # # # # # # 
# # #       # # # 
#   #       #   # 
# # #       # # # 
# # # # # # # # # 
#   # #   # #   # 
# # # # # # # # # 

Generation n+1 of the ASCII Sierpinski Carpet is made up of a 3x3 grid containing 8 copies of generation n, with the central element of the grid missing.

So, because it is defined using a 3x3 grid and gets 3 times bigger in width and height each generation, we can say it has a scale factor of 3.

We could define a bit pattern for the Sierpinski carpet by numbering the elements in the 3x3 grid from 0 to 8, top-to-bottom, left-to-right, and setting the corresponding bit of an integer if generation n+1 contains a copy of generation n at that grid position:

bit:       place value:   bit pattern:   bit value:

0 1 2      1    2    4    1 1 1          1    2    4
3 4 5      8   16   32    1 0 1          8    0   32 
6 7 8      64 128  256    1 1 1          64 128  256 

integer value = 1 + 2 + 4 + 8 + 32 + 64 + 128 + 256 = 495

For a scale factor of 2, the bit pattern would be arranged like this:

0 1
2 3

and so on.

Your task is to write a program that accepts a bit pattern in this form, a scale factor (e.g. 3 for the Sierpinski Carpet) and a generation number and outputs an ASCII fractal.

Input

Your program should accept 3 integers in the following order: a bit pattern, a scale factor (ranging from 2 to 5, inclusive) and a generation count (ranging from 0 to 5, inclusive).

You do not need to perform any input validation on these values and it's perfectly fine if the program works for values larger than the ranges specified.

The inputs can be passed in any form (tuples, comma/space-separated list, etc)

Output

The program should output a fractal made up of the # character followed by a space in positions where the fractal is defined, double-spaces where it is not, and a newline character at the end of each line, either printing them out or returning a string from a function.

Examples

Input:

495,3,3

Output (Sierpinski Carpet generation 3):

# # # # # # # # # # # # # # # # # # # # # # # # # # # 
#   # #   # #   # #   # #   # #   # #   # #   # #   # 
# # # # # # # # # # # # # # # # # # # # # # # # # # # 
# # #       # # # # # #       # # # # # #       # # # 
#   #       #   # #   #       #   # #   #       #   # 
# # #       # # # # # #       # # # # # #       # # # 
# # # # # # # # # # # # # # # # # # # # # # # # # # # 
#   # #   # #   # #   # #   # #   # #   # #   # #   # 
# # # # # # # # # # # # # # # # # # # # # # # # # # # 
# # # # # # # # #                   # # # # # # # # # 
#   # #   # #   #                   #   # #   # #   # 
# # # # # # # # #                   # # # # # # # # # 
# # #       # # #                   # # #       # # # 
#   #       #   #                   #   #       #   # 
# # #       # # #                   # # #       # # # 
# # # # # # # # #                   # # # # # # # # # 
#   # #   # #   #                   #   # #   # #   # 
# # # # # # # # #                   # # # # # # # # # 
# # # # # # # # # # # # # # # # # # # # # # # # # # # 
#   # #   # #   # #   # #   # #   # #   # #   # #   # 
# # # # # # # # # # # # # # # # # # # # # # # # # # # 
# # #       # # # # # #       # # # # # #       # # # 
#   #       #   # #   #       #   # #   #       #   # 
# # #       # # # # # #       # # # # # #       # # # 
# # # # # # # # # # # # # # # # # # # # # # # # # # # 
#   # #   # #   # #   # #   # #   # #   # #   # #   # 
# # # # # # # # # # # # # # # # # # # # # # # # # # # 

Input:

7,2,5

Output (Sierpinski Triangle):

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # 
#   #   #   #   #   #   #   #   #   #   #   #   #   #   #   #   
# #     # #     # #     # #     # #     # #     # #     # #     
#       #       #       #       #       #       #       #       
# # # #         # # # #         # # # #         # # # #         
#   #           #   #           #   #           #   #           
# #             # #             # #             # #             
#               #               #               #               
# # # # # # # #                 # # # # # # # #                 
#   #   #   #                   #   #   #   #                   
# #     # #                     # #     # #                     
#       #                       #       #                       
# # # #                         # # # #                         
#   #                           #   #                           
# #                             # #                             
#                               #                               
# # # # # # # # # # # # # # # #                                 
#   #   #   #   #   #   #   #                                   
# #     # #     # #     # #                                     
#       #       #       #                                       
# # # #         # # # #                                         
#   #           #   #                                           
# #             # #                                             
#               #                                               
# # # # # # # #                                                 
#   #   #   #                                                   
# #     # #                                                     
#       #                                                       
# # # #                                                         
#   #                                                           
# #                                                             
#                                                               

Input:

325,3,3

Output (Cantor Dust):

#   #       #   #                   #   #       #   # 

#   #       #   #                   #   #       #   # 



#   #       #   #                   #   #       #   # 

#   #       #   #                   #   #       #   # 









#   #       #   #                   #   #       #   # 

#   #       #   #                   #   #       #   # 



#   #       #   #                   #   #       #   # 

#   #       #   #                   #   #       #   # 

Input

186,3,3

Output (Vicsek fractal):

                          #                           
                        # # #                         
                          #                           
                    #     #     #                     
                  # # # # # # # # #                   
                    #     #     #                     
                          #                           
                        # # #                         
                          #                           
        #                 #                 #         
      # # #             # # #             # # #       
        #                 #                 #         
  #     #     #     #     #     #     #     #     #   
# # # # # # # # # # # # # # # # # # # # # # # # # # # 
  #     #     #     #     #     #     #     #     #   
        #                 #                 #         
      # # #             # # #             # # #       
        #                 #                 #         
                          #                           
                        # # #                         
                          #                           
                    #     #     #                     
                  # # # # # # # # #                   
                    #     #     #                     
                          #                           
                        # # #                         
                          #                           

Input:

279,3,3

Output (example of an asymmetrical fractal):

# # # # # # # # # # # # # # # # # # # # # # # # # # # 
  #     #     #     #     #     #     #     #     #   
    #     #     #     #     #     #     #     #     # 
      # # #             # # #             # # #       
        #                 #                 #         
          #                 #                 #       
            # # #             # # #             # # # 
              #                 #                 #   
                #                 #                 # 
                  # # # # # # # # #                   
                    #     #     #                     
                      #     #     #                   
                        # # #                         
                          #                           
                            #                         
                              # # #                   
                                #                     
                                  #                   
                                    # # # # # # # # # 
                                      #     #     #   
                                        #     #     # 
                                          # # #       
                                            #         
                                              #       
                                                # # # 
                                                  #   
                                                    # 

etc.

Notes:

  • This is so the shortest answer in bytes wins
  • Your program can be either a stand-alone or a function that is called with the 3 input parameters and returns (or prints) a string
  • Generation 0 is defined as # (a # followed by a space) even for a bit pattern of 0.
  • A trailing newline on the last line is optional but permitted, as is any amount of trailing white-space on each line.
\$\endgroup\$
  • 3
    \$\begingroup\$ +1, I liked this in sandbox and I like it more here, with the symbol changed from "##" to "# ". I see the one trailing space at end of line is included in your examples, is it required? . Per the last rule I would assume it's optional, but the fact that you require a trailing space for generation 0 makes me wonder. Also I think you should indicate the max whitespace and newlines (you have it plural) allowed. As an extreme example I could always start with an array of 5^6=15625 lines of 2*5^6 spaces then substitute the #s. In most input cases that's an enormous amount of unused whitespace \$\endgroup\$ – Level River St Aug 11 '15 at 6:36
  • \$\begingroup\$ @steveverrill I don't require the trailing space when outputting generation 0, however the trailing space is part of its definition, which subsequent generations are defined in terms of. The plural of newlines was a typo, fixed. \$\endgroup\$ – samgak Aug 11 '15 at 7:17
  • \$\begingroup\$ Could you post the expected output for something less symmetric, such as 279,3,3? \$\endgroup\$ – aditsu Oct 10 '15 at 17:28
  • \$\begingroup\$ @aditsu sure, see edited question \$\endgroup\$ – samgak Oct 11 '15 at 6:50

10 Answers 10

3
\$\begingroup\$

APL (Dyalog Unicode), 37 bytesSBCS

'# '{⊃⍪/,/⍺\⍤1⊂⍉⍪⍉⍵}⍣⎕⍨(2⍴⎕)⍴⌽⎕⊤⍨99⍴2
                              ⎕       ⍝ input the bit pattern
                               ⊤⍨99⍴2 ⍝ decode 99 binary digits from it
                                      ⍝  (53 is the limit for floating point)
                             ⌽        ⍝ reverse, least significant bit goes first
                          ⎕           ⍝ input the scale factor
                       (2⍴ )          ⍝ twice, to use as dimensions of a matrix
                            ⍴         ⍝ reshape bit pattern into such a matrix
                     ⎕                ⍝ input the number of generations
'# '{              }⍣ ⍨               ⍝ apply that many times, starting from '# '
               ⍉⍪⍉⍵                   ⍝ make sure the argument is a matrix
              ⊂                       ⍝ enclose
          ⍺\⍤1                        ⍝ expand using rows of bit-pattern matrix
                                      ⍝  (1 for identical copy, 0 for zeroed out)
     ⊃⍪/,/                            ⍝ concat all horizontally and vertically

Try it online!

\$\endgroup\$
11
\$\begingroup\$

Common Lisp, 248 242 bytes

(lambda(n r g &aux(s(expt r g)))(labels((f(g x y s)(or(= g 0)(#2=multiple-value-bind(q x)(floor x s)(#2#(p y)(floor y s)(if(logbitp(+ q(* p r))n)(f(1- g)x y(/ s r))))))))(#3=dotimes(y s)(#3#(x s)(princ(if(f g x y(/ s r))"# ""  ")))(terpri))))

Ungolfed

(defun fractal (n r g &aux (s (expt r g)))
  (labels((f(g x y s)
            (or(= g 0)
               (multiple-value-bind (px x) (truncate x s)
                 (multiple-value-bind (py y) (truncate y s)
                   (and
                    (logbitp (+ px (* py r)) n)
                    (f (1- g) x y (/ s r))))))))
    (fresh-line)
    (dotimes(y s)
      (dotimes(x s)
        (princ
         (if (f g x y(/ s r))
             "# "
             "  ")))
      (terpri))))

Explanation

  • Input:
    • N is the encoded pattern
    • R is the size of the pattern
    • G is the generation
  • The output is an implicit square matrix of length S=RG
  • We iterate over each row y, column x (nested dotimes) and compute whether each cell should be drawn (raycasting-like approach). This is done by recursively looking inside the fractal with the f auxiliary function.
  • If the fractal at position (x,y) shall be drawn, print "# ", or else print " ". Of course we also print newlines at the end of each row.

For example, Sierpinsky's triangle is represented by S=7 and R=2. At generation 3 the square size is 23=8. For each cell (x,y), the following happen:

  • f is called with x, y, g bound to 3 and s bound to 4 (8/2)
  • We truncate x by s, in order to know if x belongs to the left or right side of the implicit matrix. truncate returns both the quotient and the remainder, which are bound respectively to px and x (we reuse the same symbol x, but this not a problem).
  • The same goes for y which gives py and new y.
  • In this example, px and py can be either 0 or 1 (because the pattern is a square of length 2). They identify where is (x,y) in the fractal's pattern: when the bit at position py.R + px of N is 0, x and y represent a position where nothing should be drawn.
  • Otherwise, we must "zoom" into the corresponding part of the fractal and we call f recursively with the new bindings for x and y. Those are now the relative position inside the inner fractal. We pass G-1 for the generation and s/2 to represent the half-length of the fractal.
  • The base case of the recursion is encountered when G is zero, in which case the current (x,y) position should be drawn.

Example

(fractal 186 3 3)

                          #                           
                        # # #                         
                          #                           
                    #     #     #                     
                  # # # # # # # # #                   
                    #     #     #                     
                          #                           
                        # # #                         
                          #                           
        #                 #                 #         
      # # #             # # #             # # #       
        #                 #                 #         
  #     #     #     #     #     #     #     #     #   
# # # # # # # # # # # # # # # # # # # # # # # # # # # 
  #     #     #     #     #     #     #     #     #   
        #                 #                 #         
      # # #             # # #             # # #       
        #                 #                 #         
                          #                           
                        # # #                         
                          #                           
                    #     #     #                     
                  # # # # # # # # #                   
                    #     #     #                     
                          #                           
                        # # #                         
                          #                           

Computing the 8th generation of the Sierpinski Carpet using (fractal 495 3 8) takes 24.7 seconds and generates an output text file of 83 MB. I wrote a slightly modifed version which outputs an image. For the same parameters, the GIF file weights 1.5MB (same computation time):

Sierpinsky's Carpet, generation 8

Vicsek (click to see original size):

Vicsek fractal

\$\endgroup\$
  • 1
    \$\begingroup\$ +1 for what looks like a concise program in a horribly verbose language. 8 nested ) in a row! \$\endgroup\$ – Level River St Aug 11 '15 at 13:32
  • \$\begingroup\$ @steveverrill I never win code golfs... but still, I think the syntax pays off for larger programs. And honestly, I almost do not see parenthesis anymore, just a nice tree. \$\endgroup\$ – coredump Aug 11 '15 at 13:43
  • \$\begingroup\$ That gif image actually crashes my phone's web browser... Great golfing with a more unusual language \$\endgroup\$ – Glenn Smith Aug 13 '15 at 18:51
  • \$\begingroup\$ @HiGuy Thanks. Does CodeGolf has a badge for making other people's browser crash? It should :-) \$\endgroup\$ – coredump Aug 13 '15 at 19:47
5
\$\begingroup\$

Pyth, 38 bytes

VJ^UQvwjdm@" #".A@L_.[0^Q2jvz2+V*RQNdJ

Try it online: Regular Input / Test Suite

Explanation follows later.

\$\endgroup\$
  • \$\begingroup\$ 1+ I am still waiting for the output of 186 3 5 (online interpreter), but apart from that I am truly impressed by how short this is. \$\endgroup\$ – coredump Aug 11 '15 at 15:50
  • 1
    \$\begingroup\$ @coredump I don't think you'll get such a big output using the online interpreter. If you want to test it, you would have to download the Pyth compiler. It takes about 10 seconds on my laptop. \$\endgroup\$ – Jakube Aug 11 '15 at 16:04
4
\$\begingroup\$

Ruby,154

Score is for the function only. Presented ungolfed below in test program. The only golfing I'm claiming at the moment is removal of comments and indents. I will golf later. At the moment, I'm having fun playing with the program.

The function takes six arguments, but on the initial call only the first 3 are provided per the spec. This causes the three remaining arguments to be set to default values, and in particular the string a where the output is stored is created and initialized to lines of spaces terminated by newlines. As a side effect the global variable $w is also created, indicating the number of symbols per line.

When the function calls itself recursively, it provides all six arguments, including the string a and the x and y coordinates of the top left corner of the next recursion

The rest of the program is pretty straightforward, as indicated in the comments.

#function
f=->b,s,g,x=0,y=0,a=(' '*(-1+2*$w=s**g)+'
')*$w{                                         #accept arguments, if x,y,a are not provided create them. $w = number of symbols per row 
  v=s**g/s                                     #v=width of blocks for this recursion depth
  if g==0
    a[2*y*$w+2*x]=?#                           #if g==0 plot a #
  else                                         #else iterate s*s times through the bits of b, and recurse as necessary
    (s*s).times{|i|b>>i&1>0&&f.call(b,s,g-1,x+i%s*v,y+i/s*v,a)} 
  end
  a
}

#test program (requires 3 input numbers separated by newlines)
b=gets.to_i
s=gets.to_i
g=gets.to_i
#get return value and output to stdout
puts f.call(b,s,g)

Output

Here's a set of fractals loosely based on the form of the letters of the word GOLF. More realistic letters could be achieved with larger bitmaps. As the last example shows, the most interesting fractals are discovered by accident.

63775,4,2 (G)

# # # # # # # # # # # # # # # #
#       #       #       #      
#     # #     # #     # #     #
# # # # # # # # # # # # # # # #
# # # #                        
#                              
#     #                        
# # # #                        
# # # #                 # # # #
#                       #      
#     #                 #     #
# # # #                 # # # #
# # # # # # # # # # # # # # # #
#       #       #       #      
#     # #     # #     # #     #
# # # # # # # # # # # # # # # #

495,3,3 (O, sierpinski carpet)

# # # # # # # # # # # # # # # # # # # # # # # # # # #
#   # #   # #   # #   # #   # #   # #   # #   # #   #
# # # # # # # # # # # # # # # # # # # # # # # # # # #
# # #       # # # # # #       # # # # # #       # # #
#   #       #   # #   #       #   # #   #       #   #
# # #       # # # # # #       # # # # # #       # # #
# # # # # # # # # # # # # # # # # # # # # # # # # # #
#   # #   # #   # #   # #   # #   # #   # #   # #   #
# # # # # # # # # # # # # # # # # # # # # # # # # # #
# # # # # # # # #                   # # # # # # # # #
#   # #   # #   #                   #   # #   # #   #
# # # # # # # # #                   # # # # # # # # #
# # #       # # #                   # # #       # # #
#   #       #   #                   #   #       #   #
# # #       # # #                   # # #       # # #
# # # # # # # # #                   # # # # # # # # #
#   # #   # #   #                   #   # #   # #   #
# # # # # # # # #                   # # # # # # # # #
# # # # # # # # # # # # # # # # # # # # # # # # # # #
#   # #   # #   # #   # #   # #   # #   # #   # #   #
# # # # # # # # # # # # # # # # # # # # # # # # # # #
# # #       # # # # # #       # # # # # #       # # #
#   #       #   # #   #       #   # #   #       #   #
# # #       # # # # # #       # # # # # #       # # #
# # # # # # # # # # # # # # # # # # # # # # # # # # #
#   # #   # #   # #   # #   # #   # #   # #   # #   #
# # # # # # # # # # # # # # # # # # # # # # # # # # #

457,3,3 (L)

#                                                    
#                                                    
# # #                                                
#                                                    
#                                                    
# # #                                                
#     #     #                                        
#     #     #                                        
# # # # # # # # #                                    
#                                                    
#                                                    
# # #                                                
#                                                    
#                                                    
# # #                                                
#     #     #                                        
#     #     #                                        
# # # # # # # # #                                    
#                 #                 #                
#                 #                 #                
# # #             # # #             # # #            
#                 #                 #                
#                 #                 #                
# # #             # # #             # # #            
#     #     #     #     #     #     #     #     #    
#     #     #     #     #     #     #     #     #    
# # # # # # # # # # # # # # # # # # # # # # # # # # #

7967,4,2 (F)

# # # # # # # # # # # # # # # #
#       #       #       #      
# # # # # # # # # # # # # # # #
#       #       #       #      
# # # #                        
#                              
# # # #                        
#                              
# # # # # # # # # # # # # # # #
#       #       #       #      
# # # # # # # # # # # # # # # #
#       #       #       #      
# # # #                        
#                              
# # # #                        
#      

1879,3,3 (skull and crossbones discovered by accident)

# # # # # # # # # # # # # # # # # # # # # # # # # # #
  #     #     #     #     #     #     #     #     #  
#   # #   # #   # #   # #   # #   # #   # #   # #   #
      # # #             # # #             # # #      
        #                 #                 #        
      #   #             #   #             #   #      
# # #       # # # # # #       # # # # # #       # # #
  #           #     #           #     #           #  
#   #       #   # #   #       #   # #   #       #   #
                  # # # # # # # # #                  
                    #     #     #                    
                  #   # #   # #   #                  
                        # # #                        
                          #                          
                        #   #                        
                  # # #       # # #                  
                    #           #                    
                  #   #       #   #                  
# # # # # # # # #                   # # # # # # # # #
  #     #     #                       #     #     #  
#   # #   # #   #                   #   # #   # #   #
      # # #                               # # #      
        #                                   #        
      #   #                               #   #      
# # #       # # #                   # # #       # # #
  #           #                       #           #  
#   #       #   #                   #   #       #   #
\$\endgroup\$
3
\$\begingroup\$

CJam, 45

3aaq~@2b2$_*0e[W%@/a*{ffff*:.+:.+}/' ff+Sf*N*

Implementation of my first idea. Try it online

Basically, it starts with a 1*1 matrix containing 3 (the difference between '#' and ' '), then repeatedly multiplies each number in the matrix with the bit pattern (0/1 matrix), and combines the resulting matrices into one bigger matrix. At the end, it adds a space to each number, and joins with spaces and newlines.

2nd idea, 49

q~@2bW%2$/z@@m*_,\_m*:z@f{3@@f{\~@==*}~' +}/Sf*N*

Try it online

This generates all the coordinates of the output matrix as arrays of <generation count> pairs of numbers smaller than the scale factor (all such combinations), then for each pair of numbers it gets the corresponding bit from the pattern, and for each coordinate array it multiplies the bits and multiplies by 3. The final processing is the same.

There's probably room for more golfing.

\$\endgroup\$
2
\$\begingroup\$

C, 316 bytes

main(a,_,b,s,g,i,w,o,z,x,y)char**_,*o;{b=atoi(_[1]);s=atoi(_[2]);g=atoi(_[3]);w=1;for(i=0;i<g;++i){w*=s;}o=malloc(w*w);for(i=0;i<w*w;++i)o[i]=35;z=w/s;while(z){for(y=0;y<w;++y)for(x=0;x<w;++x)if(!((b>>((y/z)%s*s+(x/z)%s))&1))o[y*w+x]=32;z/=s;}for(y=0;y<w;++y){for(x=0;x<w;++x)printf("%c ",o[y*w+x]);printf("\n");}}

Un-golfed:

#include <stdio.h>

int main(int argc, char *argv[]) 
{
    int bitpattern;
    int scale;
    int generation;

    bitpattern = atoi(argv[1]);
    scale = atoi(argv[2]);
    generation = atoi(argv[3]);

    int i;
    int width = 1;
    for (i=0; i<generation; ++i) {width*=scale;}

    char *out=malloc(width*width);

    for (i=0; i<width*width; ++i) out[i]='#';


    int blocksize = width/scale;
    for (i=0; i<generation; ++i) {
        int x,y;
        for (y=0; y<width; ++y) {
            for (x=0; x<width; ++x) {
                int localX = x/blocksize;
                localX %= scale;
                int localY = y/blocksize;
                localY %= scale;
                int localPos = localY*scale+localX;
                if (!((bitpattern>>localPos)&1))out[y*width+x]=' ';
            }
        }
        blocksize/=scale;
    }

    int x,y;
    for (y=0; y<width; ++y) {
        for (x=0; x<width; ++x)
            printf("%c ",out[y*width+x]);
        printf("\n");
    }
    return 0;
}
\$\endgroup\$
  • 3
    \$\begingroup\$ According to the bullet points at the end of the spec a function is allowed instead of a program. Change it to a function and just pass the three input parameters to it - that would get rid of all that atoi stuff and save you about 40 bytes. \$\endgroup\$ – Level River St Aug 12 '15 at 9:19
2
\$\begingroup\$

Scala 293 299

(e:Int,s:Int,g:Int)=>{def b(x:Int,y:Int)=(1<<x*s+y&e)>0;def f(n:Int):Seq[Seq[Char]]=if(n<1)Seq(Seq('#'))else if(n<2)Seq.tabulate(s,s)((i,j)=>if(b(i,j))'#'else' ')else{val k=f(n-1);val t=k.size;Seq.tabulate(t*s,t*s)((i,j)=>if(b(i/t,j/t))k(i%t)(j%t)else' ')};f(g).map(_.mkString(" ")).mkString(" \n")}

ungolfed:

//create an anonymous function
(encoded: Int, size: Int, generation: Int) => {

  // method will return true if coords (x,y) should be drawn as '#'
  def isBlackInPattern(x: Int, y: Int): Boolean = (1 << x * size + y & encoded) > 0

  // recurse until generation is 1
  def fillRecursively(gen: Int): Seq[Seq[Char]] = {

    // this is just to satisfy OP requirements.
    // if the stopping condition were generation = 1,
    // I could have spared this line...
    if(gen < 1) Seq(Seq('#'))

    //actual stopping condition (generation 1). 
    // fill a matrix of characters with spaces
    // and hashes acording to the pattern.
    else if(gen < 2) Seq.tabulate(size, size)((i, j) => 
      if (isBlackInPattern(i,j)) '#' 
      else ' '
    )

    // recurse, and use previously created fractals to fill
    // the current generation according to the `isBlackInPattern` condition
    else {
      val previousGeneration = fillRecursively(gen-1)
      val previousSize = previousGeneration.size
      // create the current matrix and fill it
      Seq.tabulate(previousSize*size,previousSize*size)((i,j)=>
        if(isBlackInPattern(i/previousSize,j/previousSize))
          previousGeneration(i%t)(j%t)
        else ' '
      )
    }
  }
  // call to recursive function and format matrix of characters to string
  fillRecursively(generation).map(_.mkString(" ")).mkString(" \n")
}

examples:

val f = (e:Int,s:Int,g:Int)=>{def b(x:Int,y:Int)=(1<<x*s+y&e)>0;def f(n:Int):Seq[Seq[Char]]=if(n<1)Seq(Seq('#'))else if(n<2)Seq.tabulate(s,s)((i,j)=>if(b(i,j))'#'else' ')else{val k=f(n-1);val t=k.size;Seq.tabulate(t*s,t*s)((i,j)=>if(b(i/t,j/t))k(i%t)(j%t)else' ')};f(g).map(_.mkString(" ")).mkString(" \n")}
f: (Int, Int, Int) => String = <function3>

scala> println(f(495,3,3))
# # # # # # # # # # # # # # # # # # # # # # # # # # # 
#   # #   # #   # #   # #   # #   # #   # #   # #   # 
# # # # # # # # # # # # # # # # # # # # # # # # # # # 
# # #       # # # # # #       # # # # # #       # # # 
#   #       #   # #   #       #   # #   #       #   # 
# # #       # # # # # #       # # # # # #       # # # 
# # # # # # # # # # # # # # # # # # # # # # # # # # # 
#   # #   # #   # #   # #   # #   # #   # #   # #   # 
# # # # # # # # # # # # # # # # # # # # # # # # # # # 
# # # # # # # # #                   # # # # # # # # # 
#   # #   # #   #                   #   # #   # #   # 
# # # # # # # # #                   # # # # # # # # # 
# # #       # # #                   # # #       # # # 
#   #       #   #                   #   #       #   # 
# # #       # # #                   # # #       # # # 
# # # # # # # # #                   # # # # # # # # # 
#   # #   # #   #                   #   # #   # #   # 
# # # # # # # # #                   # # # # # # # # # 
# # # # # # # # # # # # # # # # # # # # # # # # # # # 
#   # #   # #   # #   # #   # #   # #   # #   # #   # 
# # # # # # # # # # # # # # # # # # # # # # # # # # # 
# # #       # # # # # #       # # # # # #       # # # 
#   #       #   # #   #       #   # #   #       #   # 
# # #       # # # # # #       # # # # # #       # # # 
# # # # # # # # # # # # # # # # # # # # # # # # # # # 
#   # #   # #   # #   # #   # #   # #   # #   # #   # 
# # # # # # # # # # # # # # # # # # # # # # # # # # #

scala> println(f(7,2,5))
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # 
#   #   #   #   #   #   #   #   #   #   #   #   #   #   #   #   
# #     # #     # #     # #     # #     # #     # #     # #     
#       #       #       #       #       #       #       #       
# # # #         # # # #         # # # #         # # # #         
#   #           #   #           #   #           #   #           
# #             # #             # #             # #             
#               #               #               #               
# # # # # # # #                 # # # # # # # #                 
#   #   #   #                   #   #   #   #                   
# #     # #                     # #     # #                     
#       #                       #       #                       
# # # #                         # # # #                         
#   #                           #   #                           
# #                             # #                             
#                               #                               
# # # # # # # # # # # # # # # #                                 
#   #   #   #   #   #   #   #                                   
# #     # #     # #     # #                                     
#       #       #       #                                       
# # # #         # # # #                                         
#   #           #   #                                           
# #             # #                                             
#               #                                               
# # # # # # # #                                                 
#   #   #   #                                                   
# #     # #                                                     
#       #                                                       
# # # #                                                         
#   #                                                           
# #                                                             
# 

scala> println(f(18157905,5,2))
#       #                               #       # 
  #   #                                   #   #   
    #                                       #     
  #   #                                   #   #   
#       #                               #       # 
          #       #           #       #           
            #   #               #   #             
              #                   #               
            #   #               #   #             
          #       #           #       #           
                    #       #                     
                      #   #                       
                        #                         
                      #   #                       
                    #       #                     
          #       #           #       #           
            #   #               #   #             
              #                   #               
            #   #               #   #             
          #       #           #       #           
#       #                               #       # 
  #   #                                   #   #   
    #                                       #     
  #   #                                   #   #   
#       #                               #       # 

first cut, probably can be golfed a bit further...

\$\endgroup\$
  • \$\begingroup\$ You are missing a space between each of your #'s. Besides being required by the spec, it really enhances the appearance of your output. \$\endgroup\$ – Level River St Aug 14 '15 at 13:10
  • \$\begingroup\$ @steveverrill your'e right. I didn't noticed that at first. I edited with a quick fix. thanks :) \$\endgroup\$ – gilad hoch Aug 14 '15 at 13:44
2
\$\begingroup\$

Matlab, 115 bytes

The Kronecker kron product makes everything much easier:

function f(p,f,g);z=nan(f);z(:)=de2bi(p,f*f);x=3;for k=1:g;x=kron(x,z);end;disp([reshape([x;0*x],f^g,2*f^g)+32,''])

# # # # # # # # # # # # # # # # # # # # # # # # # # # 
#   # #   # #   # #   # #   # #   # #   # #   # #   # 
# # # # # # # # # # # # # # # # # # # # # # # # # # # 
# # #       # # # # # #       # # # # # #       # # # 
#   #       #   # #   #       #   # #   #       #   # 
# # #       # # # # # #       # # # # # #       # # # 
# # # # # # # # # # # # # # # # # # # # # # # # # # # 
#   # #   # #   # #   # #   # #   # #   # #   # #   # 
# # # # # # # # # # # # # # # # # # # # # # # # # # # 
# # # # # # # # #                   # # # # # # # # # 
#   # #   # #   #                   #   # #   # #   # 
# # # # # # # # #                   # # # # # # # # # 
# # #       # # #                   # # #       # # # 
#   #       #   #                   #   #       #   # 
# # #       # # #                   # # #       # # # 
# # # # # # # # #                   # # # # # # # # # 
#   # #   # #   #                   #   # #   # #   # 
# # # # # # # # #                   # # # # # # # # # 
# # # # # # # # # # # # # # # # # # # # # # # # # # # 
#   # #   # #   # #   # #   # #   # #   # #   # #   # 
# # # # # # # # # # # # # # # # # # # # # # # # # # # 
# # #       # # # # # #       # # # # # #       # # # 
#   #       #   # #   #       #   # #   #       #   # 
# # #       # # # # # #       # # # # # #       # # # 
# # # # # # # # # # # # # # # # # # # # # # # # # # # 
#   # #   # #   # #   # #   # #   # #   # #   # #   # 
# # # # # # # # # # # # # # # # # # # # # # # # # # # 
\$\endgroup\$
  • \$\begingroup\$ Though de2bi only works if you have the Communications Systems Toolbox. Doesn't work without it. It would need dec2bin. \$\endgroup\$ – Tom Carpenter Oct 11 '15 at 13:40
  • \$\begingroup\$ It seems this toolbox is included in my standard student version, so I think this is acceptable. (Note that de2bi does not the same as dec2bin.) \$\endgroup\$ – flawr Oct 11 '15 at 15:10
2
\$\begingroup\$

C, 158 bytes

f(p,s,g,h,i,j,c){for(j=1;g--;j*=s);for(h=j;h;){h--;for(i=j;i;){i--;for(c=35,g=j/s;g;g/=s)c=!((p>>((h/g)%s*s+(i/g)%s))&1)?32:c;printf("%c ",c);}printf("\n");}}
\$\endgroup\$
1
\$\begingroup\$

K5, 70 bytes

It's a start:

{,/'("  ";"# ")$[z;(z-1){,/'+,/'+x@y}[(0*t;t)]/t:(2#y)#|(25#2)\x;,,1]}

In action:

{,/'("  ";"# ")$[z;(z-1){,/'+,/'+x@y}[(0*t;t)]/t:(2#y)#|(25#2)\x;,,1]}[186;3]'!4
(,"# "
 ("  #   "
  "# # # "
  "  #   ")
 ("        #         "
  "      # # #       "
  "        #         "
  "  #     #     #   "
  "# # # # # # # # # "
  "  #     #     #   "
  "        #         "
  "      # # #       "
  "        #         ")
 ("                          #                           "
  "                        # # #                         "
  "                          #                           "
  "                    #     #     #                     "
  "                  # # # # # # # # #                   "
  "                    #     #     #                     "
  "                          #                           "
  "                        # # #                         "
  "                          #                           "
  "        #                 #                 #         "
  "      # # #             # # #             # # #       "
  "        #                 #                 #         "
  "  #     #     #     #     #     #     #     #     #   "
  "# # # # # # # # # # # # # # # # # # # # # # # # # # # "
  "  #     #     #     #     #     #     #     #     #   "
  "        #                 #                 #         "
  "      # # #             # # #             # # #       "
  "        #                 #                 #         "
  "                          #                           "
  "                        # # #                         "
  "                          #                           "
  "                    #     #     #                     "
  "                  # # # # # # # # #                   "
  "                    #     #     #                     "
  "                          #                           "
  "                        # # #                         "
  "                          #                           "))
\$\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.