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

Examples

Input Empty string

Output {}

Input a

Output {{}}

Input aaaa

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

For readability output for 'aaaa' with separators is

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

Conditions

  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 at 10:27
1  
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 at 10:34
    
That's a good point. –  Martin Büttner Apr 10 at 10:37
1  
@jing3142 Kudos for implementing a solution yourself to make sure it's possible. +1 for great question. –  Kyle Strand Apr 10 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 at 8:44
show 1 more comment

16 Answers 16

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

'{}'\{;.);\'}'++}/

Dissection

# 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
'}'

Alternative:

# 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
add comment

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 at 11:12
    
@isaacg Nice one. OP should tell us if he minds, though. –  Jan Dvorak Apr 10 at 12:13
    
As its a set order does not matter so @isaacg 's suggestion is good –  jing3142 Apr 10 at 12:40
add comment

Python 3 - 64

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

If inlining the input is allowed:

Python 2 - 54

o=['{}']
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 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 at 10:55
    
You can save a symbol by using o[-1] instead of o.pop() –  aland Apr 11 at 11:06
    
"No digits 0 to 9 to appear in the code;" –  isaacg Apr 11 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 at 13:41
add comment

Javascript 70 (chars)

s='';c=prompt().split('');while(c.pop()){s+='{'+s+'}'}alert('{'+s+'}')

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

s='{';c=prompt().split('');while(c.pop())s+=s+'}';alert(s+'}')

and now 61

s='{';for(c=prompt().split('');c.pop();)s+=s+'}';alert(s+'}')

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 at 13:00
1  
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 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 at 16:00
3  
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 at 16:26
    
@peter-taylor +1 for very clear and concise explanation within a comment –  jing3142 Apr 10 at 17:21
add comment

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 at 15:48
    
@jing3142 Oops. Not any more. –  Karol S Apr 10 at 18:02
add comment

J - 22 20 char

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

How this can be derived:

   #'123'                      NB. string length
3
   'Left' (,,~) 'Right'        NB. dyad to concat L,R,R
LeftRightRight
   '{' (,,~) '}'               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.

Usage:

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

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
add comment

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
1  
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 at 7:45
add comment

Ruby, 27, kind of cheating

a=*a
gets.chars{a=*a,a}
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 at 18:08
add comment

Pure Bash, 54

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

Output:

$ ./strlenset.sh
{}
$ ./strlenset.sh a
{{}}
$ ./strlenset.sh aa
{{}{{}}}
$ ./strlenset.sh aaa
{{}{{}}{{}{{}}}}
$ ./strlenset.sh aaaa
{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}
$ 
share|improve this answer
add comment

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.

Golfed

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.

Ungolfed

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.

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 at 12:37
add comment

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
1  
You should count pl as astandard, but you get -e and the quotes around the code for free. Ref –  Peter Taylor Apr 10 at 14:53
    
Thanks @PeterTaylor. Updated. –  tobyink Apr 10 at 16:51
add comment

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
add comment

Mathematica, cheating, 54 chars

Fold[y~Function~{y##&@@y},{},Characters@InputString[]]

Mathematica, not cheating, 56 chars

Fold[StringInsert[#,#,2]&,"{}",Characters@InputString[]]
share|improve this answer
add comment

Julia 43

f(z)="{"foldl((x,y)->"$x{$x}","",{z...})"}"

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
add comment

Python 3 (44)

s='{'
for _ in input():s+=s+'}'
print(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.

s='{'
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
add comment

Your Answer

 
discard

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.