The Challenge

Build a N-Leveled Cantor Set.

The Cantor ternary set is created by repeatedly deleting the open middle thirds of a set of line segments.

The program receives one parameter N (a integer number) and then prints (in console or similar way) a Cantor Set of N levels. The print can only contain undescore (_) and whithe spaces characters. The parameter can be positive or negative and the sign indicates the Cantor Set construction orientation: If N > 0 the Cantor Set is constructed downwards and if N < 0 the Cantor Set is constructed upwards. If N = 0 then the program prints a single line (_).

For example:

N = 2

___   ___
_ _   _ _

N = -2

_ _   _ _
___   ___

N = 3

_________         _________
___   ___         ___   ___
_ _   _ _         _ _   _ _

N = -3

_ _   _ _         _ _   _ _
___   ___         ___   ___
_________         _________

Winning criteria

As it is a code golf challenge, the shortest code wins.

Edited: Modify 0 input by ugoren's suggestion.

  • \$\begingroup\$ Why print nothing when N=0? This makes 0 a special case, and makes it harder to use recursion. General handling would be to print a single _ (but print it downward when getting -0). \$\endgroup\$ – ugoren Jan 30 '12 at 9:55
  • \$\begingroup\$ Right. I have modified the specs already. \$\endgroup\$ – Averroes Jan 30 '12 at 10:11

17 Answers 17


GolfScript, 49 42 40 chars

~.abs.3\?'_'*\{.3%..,' '*\++}*](0>2*(%n*

With thanks to hammar for 42->40.

My best attempt yet at a more number-theoretic approach is sadly much longer:

~.abs:^3\?,{3^)?+3base(;1+1?.'_'*^@-)' '*+}%zip\0>2*(%n*


~.abs 3\?:^,{6^*+3base.1+1?.('_'*@,@-' '*+}%zip\0>2*(%n*

and I suspect that the length of base and zip will make it impossible to catch up.

  • \$\begingroup\$ ~.abs.@/\.3\?'_'*\{.3%..,' '*\++}*](%n* is 39 chars, but crashes on input 0. :-( \$\endgroup\$ – Ilmari Karonen Feb 2 '12 at 17:12
  • \$\begingroup\$ @IlmariKaronen, yes, division by zero was a pain for the C implementation I wrote too, because it meant you can't do n/abs(n) to get signum(n). \$\endgroup\$ – Peter Taylor Feb 2 '12 at 22:43

Python, 116 113 104 103 chars

d=n>0 or-1
for i in range(n*d+1)[::d]:
 while i<n*d:s+=len(s)*' '+s;i+=1
 print s

Older algorithm topped out at 113 characters

for _ in abs(r)*u:o=len(l[0]);l=[s+o*' '+s for s in l]+[u*o*3]
print'\n'.join(l[::r>0 or-1])

Ruby (97)

Based on Steven Rumbalski's python version:

n.abs.times{z=r[0].size;r=r.map{|s|s+' '*z+s}+[?_*z*3]}
puts n<0?r:r.reverse

Previous attempts, both same length (112)

Build lines from parts:

c=->x,n{n<1??_*x :(z=c[s=x/3,n-1])+' '*s+z}
puts n<0?r.reverse: r

Start with one line, make holes in it:

a.times{|c|r<<r[-1].gsub((x=?_*o=3**(a-c-1))*3,x+' '*o+x)}
puts n<0?r.reverse: r

Perl, 93 chars

@x=($t=$x=_ x 3**($a=abs($n=<>)),map$x.=$"x($x=~s/(.)../$1/g).$x,1..$a);say for$n<0?sort@x:@x

I thought I'd try to see how well Peter Taylor's GolfScript solution would port to Perl. Notable features include the use of sort instead of reverse to save three chars, using the fact that a space sorts before _.


Common Lisp, 217 210 characters

(defun m(x)(flet((c(n v)(if(= n 0)`((,v))(cons(substitute v nil(make-list(expt 3 n)))(mapcar #'append(c(1- n)v)(c(1- n)" ")(c(1- n)v))))))(format t "~{~{~a~}~%~}"(let((r(c(abs x)'_)))(if(< x 1)(reverse r)r)))))


(defun m(x)
  (flet((c(n v)
    (if(= n 0)
       (cons(substitute v nil(make-list(expt 3 n)))
            (mapcar #'append
                    (c(1- n)v)
                    (c(1- n)" ")
                    (c(1- n)v))))))
   (format t "~{~{~a~}~%~}"(let((r(c(abs x)'_)))(if(< x 1)(reverse r)r)))))

I figure if the Lisp code manages to beat any initial count for another language (C, 219) I'm doing OK :)


C (163 161 chars)


Borrows a couple of tricks from ugoren's answer, but the core logic is quite different. I couldn't follow his for loop, so it may be possible to hybridise and save a few more.


C, 219 193 179 143 136 131 characters

Followed another of Petyer Taylor's ideas, plus an improvement of my own, saved 6 more.
Integrated some tips from @PeterTaylor, plus copied his main function, with slight changes, which save a character (is it fair to copy it? Since neither of us will win this one, I guess it isn't too bad).
I thought of a significant improvement in how my recursion works, and after seeing Peter Taylor's answer, I implemented it to regain the lead. When reading his answer again, I saw that I did almost exactly what he did. So this seems like the hybridization he suggested.
Also simplified the loop in main, keeping the same length.
And took Peter's trick to print newline, instead of puts("") - saves a character.

Removed int from variable declaration - a warning, but saves 4 chars.
New algorithm doesn't calculate 3^x in advance, but uses a single loop to print 3^x characters.
Can save one more by defining int*v, but then 64bit won't work.
Characters count excludes whitespace (which can be removed).

p(c) {
    n-- ?
main(c,v)int**v; {

Older algorithm, 219 chars:

p(l,o,i,m,c,j) {
    for (;i<=n;i++)p(l,o,0),c?o*=3:(o/=3);
  • \$\begingroup\$ @PeterTaylor, I can't remove the i parameter, because using the global would interfere with main. l-- will interfere with o>=l, and I'll have to replace it with > (so why do I write it as if it's a bad thing?) I could also copy you main, which is simpler and shorter than mine. \$\endgroup\$ – ugoren Feb 4 '12 at 20:04
  • \$\begingroup\$ @PeterTaylor, you were right about i - I missed the fact that I really no longer use it (I thought you mean I don't pass it). \$\endgroup\$ – ugoren Feb 4 '12 at 20:12
  • \$\begingroup\$ By the way, I don't mind you taking my main function. My rule of thumb is that copying someone else's solution to change a single character is overly aggressive, copying someone else's solution to rewrite half of it is perfectly fair, and there's a grey area somewhere in between. We should perhaps try to agree some community standards on meta. \$\endgroup\$ – Peter Taylor Feb 5 '12 at 13:35
  • \$\begingroup\$ @PeterTaylor, I think we reached a sort of stalemate. My p seems quite optimal now, and your main was better (I'm not sure it's optimal, but can't improve it further). So except for a new ingenious program structure, the only way to go was either of us copying the other's code. \$\endgroup\$ – ugoren Feb 5 '12 at 14:09
  • \$\begingroup\$ BTW How are you counting your characters? Because I make your latest version 138 chars, not 136. \$\endgroup\$ – Peter Taylor Feb 5 '12 at 14:38

J, 44 39 38 37 bytes

' _'{~0&>_&(]|.)(,:1)1&(,],.0&*,.])~|

Uses iteration to build the next set starting with 1 (representing _) initially.


   f =: ' _'{~0&>_&(]|.)(,:1)1&(,],.0&*,.])~|
   f 0
   f 1
_ _
   f _1
_ _
   f 2
___   ___
_ _   _ _
   f _2
_ _   _ _
___   ___
   f 3
_________         _________
___   ___         ___   ___
_ _   _ _         _ _   _ _
   f _3
_ _   _ _         _ _   _ _
___   ___         ___   ___
_________         _________


' _'{~0&>_&(]|.)(,:1)1&(,],.0&*,.])~|  Input: integer n
                                    |  Absolute value of n
                (,:1)                  The array [1]
                     1&(          )~   Repeat abs(n) times starting with x = [1]
                                 ]       Identity function, gets x
                            0&*          Multiply x by 0
                               ,.        Join the rows together
                         ]               Identity function, gets x
                          ,.             Join the rows together
                     1  ,                Prepend a row of 1's and return
      0&>                              Test if n is negative, 1 if true else 0
         _&(   )                       If n is negative
             |.                          Reverse the previous result
            ]                            Return that
                                       Else pass the previous result unmodified
' _'                                   The string ' _'
    {~                                 Select from the string using the result
                                       as indices and return
  • \$\begingroup\$ Nice! I haven't personally tried, but I love using the agenda @.--perhaps it, combined with $:, could be of some use here? E.g. something like (zero case)`(positive case)`(negative case)@.*, or even maybe ":@_:`(positive case)`(|."1@$:)@.*. \$\endgroup\$ – Conor O'Brien Sep 19 '16 at 18:47
  • \$\begingroup\$ I haven't attempted a recursive solution, but I could try it. \$\endgroup\$ – miles Sep 19 '16 at 19:20

R, 141 139 137 bytes

m=abs(n<-scan());write("if"(n<m,rev,c)(c(" ","_")[Reduce(`%x%`,rep(list(matrix(c(1,1,1,1,0,1),3)),m),t(1))[,1+2^m-2^(m:0)]+1]),1,3^m,,"")

Try it online!

-15 bytes thanks too Giuseppe's use of '(' as the identity function; write instead of cat to print output; clever use of%x%.

-2 bytes thanks to Kirill L. by using c instead of '(' as the identity function.

  • \$\begingroup\$ could a Kronecker product work here? %x%? There might be some issues with taking alternating rows perhaps... \$\endgroup\$ – Giuseppe May 23 '18 at 19:18
  • \$\begingroup\$ @Giuseppe I tried, building on your "Create an “H” from smaller “H”s" answer... I'll give it another try. \$\endgroup\$ – JayCe May 23 '18 at 19:25
  • \$\begingroup\$ Ah, so it was you who upvoted that. that's the only reason I thought of kron too! I'd imagine this should be able to go down to like 125 bytes if we can find the right approach. \$\endgroup\$ – Giuseppe May 23 '18 at 19:27
  • \$\begingroup\$ you can use `(` as the identity function so you can use write directly instead of cat and a for loop. 141 bytes \$\endgroup\$ – Giuseppe May 23 '18 at 19:58
  • \$\begingroup\$ @Giuseppe I had no idea ( could be used this way, or that if could be used to select from two functions. And I will start using write... saves a lot of "\n". \$\endgroup\$ – JayCe May 23 '18 at 20:07

Python, 177 164 characters

c=lambda x:0if x<1 else x%3==1or c(x/3)
r=["".join([["_"," "][c(x/3**i)]for x in range(3**n)])for i in range(n+1)]
print"\n".join(r[::N>0 or-1])
  • \$\begingroup\$ Since you are using Python 2 you don't need to cast the results of input as int. Your last two lines could be shortened to print"\n".join(r[::N>0 or-1]) \$\endgroup\$ – Steven Rumbalski Feb 1 '12 at 15:39
  • \$\begingroup\$ @Steven I made changes. Thank you. \$\endgroup\$ – Ante Feb 1 '12 at 16:46

Perl, 113 chars

$i=abs($I=<>);@w=$_='_'x3**$i;while($i--){$x=3**$i;s/(__){$x}/'_'x$x.' 'x$x/eg;push@w,$_}say for$I>0?reverse@w:@w


    s/(__){$x}/'_'x$x.' 'x$x/eg;
say for$I>0?reverse@w:@w

JavaScript 121 bytes

Inner recursive function, then take care of backward output if needed

n=>(f=(n,t=n&&f(n-1),r=t[0])=>n?[r+r+r,...t.map(x=>x+t[n]+x)]:['_',' '],f=f(n<0?-n:n),f.pop(),n<0?f.reverse():f).join`\n`

Less golfed

  var f = n => { // recursive function
    var t = n && f(n-1), r = t[0]
    return n 
      ? [r+r+r, ...t.map(x => x+t[n]+x)]
      : ['_',' ']
  f = f(n < 0 ? -n : n);
  f.pop(); // last row is all blanks
  if (n<0) f.reverse();
  return f.join`\n`


var F=
n=>(f=(n,t=n&&f(n-1),r=t[0])=>n?[r+r+r,...t.map(x=>x+t[n]+x)]:['_',' '],f=f(n<0?-n:n),f.pop(),n<0?f.reverse():f).join`\n`

function go()
  var n=+I.value
  O.textContent = F(n)

<input id=I type=number value=3 oninput='go()'>
<pre id=O></pre>


Batch, 265 262 242 236 235 bytes

@echo off
set c=%n%,-1,0
if %n% lss 0 set c=0,1,%n:-=%
for /l %%i in (%c%)do call:l %%i
set s=_
for /l %%j in (1,1,%n:-=%)do call:m %1 %%j
echo %s%
set t=%s%
if %1 lss +%2 set t=%s:_= %
set s=%s%%t%%s%

Edit: Saved 12 19 bytes thanks to @l4m2. Saved 8 bytes by removing the unnecessary %a% variable.

  • \$\begingroup\$ This for 247 bytes. \$\endgroup\$ – Conor O'Brien Sep 19 '16 at 18:14
  • \$\begingroup\$ @ConorO'Brien Mind you it would be 261 if I counted all the CRs as well as the LFs (which I'm sure you're not required to do but I'm lazy like that). \$\endgroup\$ – Neil Sep 19 '16 at 18:52
  • \$\begingroup\$ So you're not removing CR's from your code? Even though it's not required by .BAT files and stripped by SE anyhow? :P \$\endgroup\$ – Conor O'Brien Sep 19 '16 at 18:53
  • \$\begingroup\$ @ConorO'Brien It's a penalty I accept of using Notepad to write Batch files. \$\endgroup\$ – Neil Sep 19 '16 at 20:58
  • \$\begingroup\$ Can you do something like set c=%n%,-1,0 [LF] if %n% lss 0 set c=0,1,%a% [LF] for /l %%i in (%c%)do call:l %%i? \$\endgroup\$ – l4m2 May 24 '18 at 11:59

JavaScript (Node.js), 148 bytes

n=>f=(L=n<0&&n,R=n>0&&n)=>[...Array(r=3**(n>0?n:-n))].map(_=>((j++).toString(3)+1).indexOf(1)>(L>0?L:-L)?'_':' ',j=r+r).join``+`

Try it online!


Python 2, 102 bytes

lambda n:'\n'.join(eval("[i+' '*len(i)+i for i in"*abs(n)+"'_'"+"]+['___'*len(i)]"*abs(n))[::n<1or-1])

Try it online!


Prolog (SWI), 265 232 213 bytes

N+R:-(N>0->O is N-1,O+S,S/[]/R;R=`_`).
-N:-(0-N-J,K is N-J;N-0-I,J is -I,K is I-N),L is 3^K,J+R,L*R,1=0;1=1.

Try it online!


PowerShell, 111 bytes

filter f{if($s=[math]::Sign($_)){($x=$_-$s|f|%{$_+' '*($l=$_|% Le*)+$_})|?{$s-1};'_'*3*$l;$x|?{$s+1}}else{'_'}}

Try it online!

Less golfed:

filter f{
            $_+' '*($length=$_|% Length)+$_
        $x|?{$sign-1}  # output $x if $_ is negative
        $x|?{$sign+1}  # output $x if $_ is positive

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.