Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

From Wikipedia Set-theoretic definition of natural numbers

The set N of natural numbers is defined as the smallest set containing 0 and closed under the successor function S defined by S(n) = n ∪ {n}.

The first few numbers defined this way are 0 = {}, 1 = {0} = {{}}, 2 = {0,1} = {{},{{}}}, 3 = {0,1,2} = {{},{{}},{{},{{}}}}.

Using this definition of natural numbers count the length of a string.

Input a string of characters from a-zA-Z of any length

Output the length of the string in set notation without separators


Input Empty string

Output {}

Input a

Output {{}}

Input aaaa

Output {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}

For readability output for 'aaaa' with separators is

    {{} {{}} } 
    {{}   {{}}   {{} {{} } }   }


  1. No digits 0 to 9 to appear in the code;
  2. No use of character code conversion to generate numbers;
  3. No use of +-*/ for arithmetic calculations including increment and decrement;
  4. No mathematical operations other than Boolean Logic;
  5. Input string does not count in determining byte length;

Winner Shortest code length in bytes.

As this is my first question I hope I have made it clear and rigorous enough. Friendly advice accepted.

share|improve this question
Hm, can you implement a recursive definition without calling f(n-1)? –  Martin Büttner Apr 10 '14 at 10:27
I have a solution (non-optimal in terms of byte length) that does not use recursion. If A is an array then A.pop();f(A) is recursive. –  jing3142 Apr 10 '14 at 10:34
That's a good point. –  Martin Büttner Apr 10 '14 at 10:37
@jing3142 Kudos for implementing a solution yourself to make sure it's possible. +1 for great question. –  Kyle Strand Apr 10 '14 at 18:49
What does the restriction to a-zA-Z mean? Should we detect whitespace/rubish? or should we just expect this and report the length of the string, regardles on the content? –  V-X Apr 11 '14 at 8:44

21 Answers 21

up vote 7 down vote accepted

GolfScript (18 17 bytes)


Takes input on the stack (so if run as a program, via stdin). Leaves the output as two strings on the stack (so if run as a program, the correct output is sent to stdout).

To leave a single string on the stack, either append + to concat, or use the alternative



# Stack: input-str
# Stack: <0< input-str  where <0< means the string representing 0 without its final }
# Loop over each character of the input string
    # Stack: <n< char
    # Discard the input character
    # Concatenate two copies of <n< and a }
# Push the final } to the stack


# Stack: input-str
# Stack: <0> input-str  (where <0> means the string representing 0)
# Loop over each character of the input string
    # Stack: <n> char
    # Discard the input character
    # Duplicate <n> and remove the final '}'
    # Stack manipulations
    # Stack: <n>-less-final-'}' <n> '}'
    # Concatenate the three strings to get <n+1>

Impact of the restrictions

If decrement were allowed, it would permit the 15-byte solution

share|improve this answer

Haskell function, 35 34 characters

f[]="{}";f(_:x)='{':f x++tail(f x)

Haskell program with hardcoded input, 48 or 49 47 or 48 characters

 f[]="{}";f(_:x)='{':f x++tail(f x);main=print$f"aaaa"

(47 characters if you don't mind extra quotes around the output; if you do, use putStr instead of print for a total of 48 characters)

Haskell program, 51 50 characters

f[]="{}";f(_:x)='{':f x++tail(f x);main=interact f
share|improve this answer
If you're OK with reversing the order, since it's a set, you can use: f[]="{}";f(_:x)='{':f x++(tail.f)x to save a character. –  isaacg Apr 10 '14 at 11:12
@isaacg Nice one. OP should tell us if he minds, though. –  Jan Dvorak Apr 10 '14 at 12:13
As its a set order does not matter so @isaacg 's suggestion is good –  jing3142 Apr 10 '14 at 12:40

Python 3 - 64

for a in input():o+=['{'+''.join(o)+'}']

If inlining the input is allowed:

Python 2 - 54

for a in'whatever':o+=['{'+''.join(o)+'}']
print o.pop()
share|improve this answer
Isn't raw-input() the method of inputing not the input string itself. Not being familiar with the range of languages possible I was disallowing the string length if something like w='aaaaaaaaaaaa' was necessary within the code. Sorry if not clear. Any help in re-wording question accepted. –  jing3142 Apr 10 '14 at 10:52
I see. I'll rewrite my code accordingly. In general, however, I think you should just leave that line out. Essentially every language has an I/O system. –  isaacg Apr 10 '14 at 10:55
You can save a symbol by using o[-1] instead of o.pop() –  aland Apr 11 '14 at 11:06
"No digits 0 to 9 to appear in the code;" –  isaacg Apr 11 '14 at 18:06
A strange character-save for the first one: Initialize o=[], which becomes o=['{}'] after one step, and lengthen the input by one by replacing it with '_'+input(), cutting the space after in. –  xnor Jul 18 '14 at 13:41

Javascript 70 (chars)


This was my effort before setting the question. I would assume someone with more knowledge of Javascript than me can probably beat it.

Thank you Jan Dvorak and Peter Taylor for further reductions

now 62


and now 61


Explanation of Original Code

set s to be empty

input string into c and split into an array

while it is possible to pop() a character from c do so and reset s=s{s} as successor

output current s but need to surround with set brackets.

share|improve this answer
You don't need braces after while (saves one character). –  Jan Dvorak Apr 10 '14 at 13:00
There's a 7-char saving without any more knowledge of JS required: initialise s='{' and ditch the two '{'+. (This then behaves like my GS solution). There's a further 1-char saving by using for instead of while and pulling in one of the two initialisations to the for-loop initialisation. –  Peter Taylor Apr 10 '14 at 13:00
@peter-taylor not sure how you mean to apply for-loop. I have only ever used it for counting. –  jing3142 Apr 10 '14 at 16:00
for(a;b;c){d} is directly equivalent to a;while(b){d;c} in most languages which have both. So while for(;b;) is identical to while(b) in effect and character count, for(a;b;) saves one char over a;while(b) and is identical in effect. –  Peter Taylor Apr 10 '14 at 16:26
@peter-taylor +1 for very clear and concise explanation within a comment –  jing3142 Apr 10 '14 at 17:21

J - 22 20 char

'{','}' '{'&(,,~)~#

How this can be derived:

   #'123'                      NB. string length
   'Left' (,,~) 'Right'        NB. dyad to concat L,R,R
   '{' (,,~) '}'               NB. using braces
   '{'&(,,~) '}'               NB. bind left argument, now it's a monad
   '{'&(,,~) '{'&(,,~) '}'     NB. twice
   '{'&(,,~)^:2 '}'            NB. ^: is monad functional power
   '{'&(,,~)^:3 '}'            NB. any integer
   3 '{'&(,,~) '}'             NB. convenient feature of dyadic &
   '}' '{'&(,,~)~ 3            NB. swap argument order
   '}' '{'&(,,~)~ #'123'       NB. using string length
   '{', '}' '{'&(,,~)~ #'123'  NB. add final brace
   ('{','}' '{'&(,,~)~#) '123' NB. works as a verb

Alternatively, this can be written '{','{'&(,,~)&'}'@#, meaning the same thing.


   '{','}' '{'&(,,~)~# 'aaaa'
   f =: '{','}' '{'&(,,~)~#  NB. can be assigned to a function
   f 'VeryBig'
share|improve this answer

Haskell - 35 charactes

g[]="{}";g(_:x)=(init.g)x++g x++"}"

Solution is influenced by Jan Dvorak's one, but without reversing the order.

share|improve this answer

Scala, 64 characters

def f(s:String):String=s"{${s.tails.toSeq.tail.map(f)mkString}}"

Note the dual roles that both the braces and s play in this code.

EDIT: removed a digit

share|improve this answer
There is a digit in the code –  jing3142 Apr 10 '14 at 15:48
@jing3142 Oops. Not any more. –  Karol S Apr 10 '14 at 18:02

Python 3 (44)

for _ in input():s+=s+'}'

At each step, s is the string representing the set with the final } removed. We create the set representing n+1 from the set representing n via the relationship f(n+1) = f(n) ∪ {f(n)}. To implement the union with strings, we append the string for {f(n)}, which is exactly s but with the final } returned, and neglect to include the final } in the result. Finally, we add back a final '}' before printing.

If I may hardcode the string, the character count cuts down to 35 character, switching to Python 2 to save parantheses on the print.

for _ in'string':s+=s+'}'
print s+'}'

There might be a way to save the space after the print by doing something like print'{'+s with a reversed s, but this messes up with the += appending on the right.

share|improve this answer

Mathematica, 115 characters

StringReplace[ToString@Function[s,NestWhile[#~Append~#&,{},(s~Read~Character//StringQ)&]]@StringToStream@"test",", "->""]

The complete code as shown has 121 characters, but 6 of them are used for the input string ("test") which, according to the rules, doesn't count.

Without the requirement that there are no delimiters, the code length could be reduced further by 24 characters; without explicit conversion to string then another 9 characters could be removed.

share|improve this answer
I thought that removing the need for deliminators, which are usually are required in set notation, I was helping to reduce code size. So if using them reduces your code size go ahead and use them. –  jing3142 Apr 11 '14 at 7:45

Ruby, 27, kind of cheating

p a

Questionable things:

  1. Output looks like [[], [[]], [[], [[]]], [[], [[]], [[], [[]]]]]
  2. Most methods of input to ruby will include a trailing newline, which inflates the count by 1.
share|improve this answer
It should be perfectly legit if you inspect the array manually and tr the result. –  Jan Dvorak Apr 15 '14 at 18:08

Pure Bash, 54

f()([ $@ ]&&(a=`f ${@%?}`
echo $a{$a}))
echo {`f $@`}


$ ./strlenset.sh
$ ./strlenset.sh a
$ ./strlenset.sh aa
$ ./strlenset.sh aaa
$ ./strlenset.sh aaaa
share|improve this answer

Julia 43


The construct {z...} expands the string z into an array. Fold loops over all elements of the array ignoring the contents and instead building up from the empty string. The function foldl is available in Julia 0.30.

Sample Output

julia> f("")
julia> f("aa")
julia> f("aaaa")
julia> f("aaaaaa")
share|improve this answer

Mathematica, 45 57 48 bytes


A 36 bytes solution:


However, it uses some arithmetic calculations.

share|improve this answer

Delphi XE3 (264)

Ok I dont even come close to the other but it was fun to do :)
Probably overthinking it. Going to see if there is a better way to do this.


uses System.SysUtils;var s,f:string;a:TArray<char>;b:TArray<string>;i,x:integer;begin readln(s);a:=s.ToCharArray;f:='{';setlength(b,Length(a));for I:=Low(a)to High(a) do begin s:='{';for x:=Low(b)to High(b)do s:=s+b[x];b[i]:=s+'}';f:=f+b[i];end;writeln(f+'}');end.


    for I:=Low(a)to High(a) do
      for x:=Low(b)to High(b)do

Testing results

Tested strings with length 0..10

{{} }
{{} {{}} }
{{} {{}} {{}{{}}} }
{{} {{}} {{}{{}}} {{}{{}}{{}{{}}}} }
{{} {{}} {{}{{}}} {{}{{}}{{}{{}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}} }
{{} {{}} {{}{{}}} {{}{{}}{{}{{}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}} }
{{} {{}} {{}{{}}} {{}{{}}{{}{{}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}} }
{{} {{}} {{}{{}}} {{}{{}}{{}{{}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}} }
{{} {{}} {{}{{}}} {{}{{}}{{}{{}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}}} }
{{} {{}} {{}{{}}} {{}{{}}{{}{{}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}}}} }
share|improve this answer
Thanks for trying. In my mind I was considering length as a mathematical operation as it returns a number and as is the use of a 'for' loop which involves counting. –  jing3142 Apr 10 '14 at 12:37

Perl 5: 33 characters

It's not quite clear which characters I should count as part of the solution. Probably not the echo ... | part because that's just used to feed a line in to stdin. Probably not the name of the perl binary, because you could rename that whatever you wanted.

So I've counted the command-line switches passed to perl, the quote marks wrapped around the Perl code, and the Perl code itself.

#                                1         2         3
#                     12  3456789012345678901234567890123
$ echo "aaaa" | perl -ple'$s.="{$s}"while s/.//;$_="{$s}"'

Also, related.

share|improve this answer
You should count pl as astandard, but you get -e and the quotes around the code for free. Ref –  Peter Taylor Apr 10 '14 at 14:53
Thanks @PeterTaylor. Updated. –  tobyink Apr 10 '14 at 16:51

Perl 6: 37 characters

say ({"\{@_.join()\}"}...*)["(input string)".chars]

or from STDIN:

say ({"\{@_.join()\}"}...*)[get.chars]

{"\{@_.join()\}"}...* makes a lazy list of the set forms of the natural numbers, and we just grab the one we need with get.chars.

The lazy list might be more readably written:

-> *@prev { '{'~ @prev.join ~'}' } ... *

Which reads pretty similarly to the definition.

share|improve this answer

Dart: 85 characters


(with extra newline for readability).

The requirement of not using "0" really bites, otherwise .first would be [0] and (..).isNegative would be ..<0.

share|improve this answer

Pyth, 13 bytes


This is the golfed Pyth equivalent of @xnor's Python answer. Note that Pyth is newer than this question, so this answer is not eligible to win this challenge.


share|improve this answer

Haskell, 31 bytes

foldl(\s _->init s++s++"}")"{}"
share|improve this answer

gs2, 12 bytes

7b 7d 05 27 a0 42 30 30 e4 43 2e 32


right-uncons @0 swap + + b5
rot length times
share|improve this answer

Javascript, 171 149 147 142 bytes

(Will likely be golfed further later)

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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