{Curly Numbers};

Question

In the esoteric programming language Curly, programs consist solely of curly braces {} and semicolons ;. Despite this humble toolset, Curly has literals that can represent any nonnegative integer. The format is a little hard for the uninitiated to read, though, so let's write some code to do the conversion for us.

Format of numbers

Curly numbers are structured according to the following rules:

1. Adding a semicolon adds one to the number.
2. A number enclosed in curly braces is multiplied by four.
3. Curly-brace groups may be nested but not concatenated. Braces must match properly.
4. Semicolons outside a set of curly braces must come afterward, not before.
5. To avoid ambiguity in parsing, a number must always start with a curly brace.

Some examples:

{;;}     2*4 = 8
{{;};};  (1*4+1)*4+1 = 21
{};;;    0*4+3 = 3

(Note that rule 5 means the numbers 0 to 3 must start with an empty pair of curly braces.)

And some invalid examples:

{{;}{;;}}  Curly brace groups side-by-side, not nested
{;}}       Unmatched brace
{;{;}}     Semicolon before curly-brace group
;;;        Number does not start with curly brace

Here's a BNF grammar for Curly numbers:

<number> ::= "{" <inner> "}" <semis>
<inner>  ::= <semis>
           | <number>
<semis>  ::= ";" <semis>
           | ""

Numbers like {;;;;} (more than 3 semicolons in a row) or {{};} (unnecessary empty brace groups) are called improper Curly numbers. They obey the above grammar and can be evaluated in the usual way, but they are also capable of shorter representations (for the above examples, {{;}} and {;} respectively).

The challenge

Write a program or function that inputs/receives a string. If the string is a nonnegative decimal integer, output/return the proper (i.e. shortest possible) Curly representation for that integer. If the string is a Curly number, output/return its decimal representation.

Input can be received via STDIN, command-line argument, or function parameter. It must be a string; that is, you may not write a function that accepts strings for Curly numbers but integers for decimal numbers.

Output can be printed to STDOUT or returned from the function. A function may return an integer when appropriate, or it may return strings in all situations.

Your program does not have to handle bad input (Curly numbers that break the formatting rules, floating point numbers, negative integers, random text), and it is not required to handle improper Curly numbers (but see below). Input will consist only of printable ASCII characters.

Scoring

The shortest code in bytes wins. If your program can do both of the following:

1. correctly handle improper Curly numbers, and
2. when given a Curly number, ignore any extra characters that aren't {};

then subtract 10% from your score. (Integer input will never have extraneous characters, even for the bonus.)

Test cases

Input       Output
{;;}        8
{{;};};     21
{};;;       3
{{{{;}}};}  260
{}          0
4           {;}
17          {{;}};
1           {};
0           {}
96          {{{;};;}}

For the bonus:

{};;;;;     5
{{;;;;};;}  72
c{u;r;l}y;! 9
42{;} ;;;;  8

_{Note: Curly is not yet implemented. But if this question does well, I may develop it further.}

Answer 1

Pyth, 35 32 bytes - 10% = 28.8

.x.U+jb`HZ*R\;.[Z2jsz4i/R\;cz\}4

Try it online: Demonstration or Test Suite

edit: As it turned out, I accidentally can also handle improper Curly Numbers. Wasn't planned at all. ;-)

Explanation:

There are two expressions in the code. The first one converts a number into a Curly Number, and the second one converts a Curly Number into a regular number. .x handles, which expression gets printed. It will try to print the first expression. If there are any non-digits in the input, the first expression fails (via Exception). .x catches the Exception and prints the second one.

.U+jb`HZ*R\;.[Z2jsz4   # number to Curly Number
                 sz    read the input and converts it to an int
                j  4   convert to base 4
            .[Z2       pad zeros on the left, until length is >= 2
        *R\;           convert each digit to ";"s
                       lets call this list of ";"s Y
.U                     reduce this list, start with b=Y[0], 
                       Z iterates over Y[1], Y[2], ..., 
                       update b in each step with:
   jb`H                   put b into curly brackets
  +    Z                  and append Z

i/R\;cz\}4             # Curly Number to regular number
     cz\}              split the input by "}"
 /R\;                  count the ";"s in each string
i        4             convert this list from base 4 to base 10

Answer 2

CJam, 51 47 44 41 bytes

r_'{-_@={i4bYUe[';f*{{}s@*\+}*}{'}/:,4b}?

Try it online: sample run | test suite

How it works

r        e# Read a token from STDIN.
_'{-     e# Remove all left curly brackets from a copy of the token.
_@       e# Copy the modified token and rotate the original on top of it.
=        e# Check for equality.
{        e# If the strings were equal:
  i4b    e#   Convert to integer, then to base 4.
  YUe[   e#   Left-pad the resulting array with zeroes to a length of 2.
  ';f*   e#   Replace each digit with that many semicolons.
  {      e#   For each string of semicolons but the first:
    {}s  e#     Push the string "{}".
    @    e#     Rotate the first string or the result of the previous 
         e#     iteration on top of the stack.
    *    e#     Join, i.e., surround the string with curly brackets.
    \+   e#     Append the current string of semicolons to the result.
  }*     e#
}{       e# Else:
  '}/    e#   Split the modified input at right curly brackets.
  :,     e#   Replace each run of 0 to 3 semicolons by its length.
  4b     e#   Convert from base 4 to integer.
}?       e#

Answer 3

Python 2, 167 bytes - 10% = 150.3

d=lambda x:("{"+d(x//4)+"}"if x>3 else"")+";"*(x%4)
c=lambda n:"{}"*(int(n)<4)+d(int(n))if n.isdigit()else reduce(lambda x,y:x*4+y,[x.count(";")for x in n.split("}")])

In this implementation, c is the function that satisfies the requirements. It returns a string if given an nonnegative integer as input, or an integer if given a curly number as input.

Answer 4

Python 266 bytes - 10% = 1268.1 326.7 239.4 bytes

Boy am I not a code golfer yet =/, but that 10% helped me out a lot when my score was still over 1000!

I have a fully fleshed out (and verbose) version of this code here. It will recognize the validity of curly numbers, and provide a looped interface to enter numbers for testing.

(Comments just for clarification)

See this code in action

def c(t):                           # curly to int function
 v=0                                #  int value of input
 for a in t:                        #  for each character of input
  if a==';':v+=1                    #   if you find a ';', add one to total
  if a=='}':v*=4                    #   if you find a '}', multiply total by 4
 print v                            #  print value
def i(t):                           # int to curly function
 v=int(t);f,b="{}"if v<4 else"",""  #  get integer value. initialize front (f) and back (b) strings
 while 1:                           #  loop until stopped
  r,v=v%4,int(v/4)                  #   get remainder of v/4 and int value of v/4
  if r>0:b=';'*r+b                  #   if remainder exists, prepend that many ';' to back string
  if v>0:f=f+'{';b='}'+b            #   if remaining value > 4, append '{' to front and prepend '}' to back
  if v<4:b=';'*v+b;break            #   if remaining value < 4, prepend that many ';' to back string and break
 print f+b                          #  print result
t=raw_input()                       # get raw input
try:int(t);i(t)                     # use try block to determine which function to call
except:c(t)                         # 

Thanks to Erik Konstantopoulos for a major byte reduction! You could say... he really took a... byte... out of my code... *self five*

Answer 5

CJam, 87 bytes 80.1 score (89 bytes - 10% bonus)

Update version that qualifies for the bonus while growing by 2 bytes:

l_'{#){VX@{";{}"#)" _@+\ 4* 4/"S/=~}/;}{i_4<{"{}"\';*}{{4md\_{F'{\+'}+}{;L}?\';*+}:F~}?}?

Try it online

First time I used recursion in CJam! The whole thing may look kind of lengthy, but the two completely separate conversions add up.

I used a completely separate case for converting numbers smaller than 4 to Curly. It's probably possible to avoid that, but folding the special case handling into the recursive function wouldn't be entirely trivial. And adding the extra {} as a post-processing step didn't really look any better, even though I should try again if it might be slightly shorter.

Answer 6

C#, 173 - 10% = 155.7 171.0, 177.3

This does no validation and only looks for ; and } characters. It assumes all { characters come before any ; characters. The hardest thing I found was to not insert a {} in the middle of a Curly number.

Line breaks and indents for clarity:

string C(string a,int b=0){
    int n;
    if(int.TryParse(a,out n))
        a=(n>=b?"{"+C(""+n/4,4)+"}":"")+";;;".Remove(n%4);
    else
        foreach(int c in a)
            a=""+(c==59?++n:c==125?n*=4:n);
    return a;
}

Answer 7

Java 326 bytes - 10% = 294 bytes

It is complete program written in java,

public class a{static String c(long a,int v){if(a==0)return v==0?"{}":"";String x="";for(int i=0;i<a%4;i++)x+=";";return "{"+c(a/4,v+1)+"}"+x;}public static void main(String[]c){try{System.out.println(c(Long.parseLong(c[0]),0));}catch(Exception e){System.out.println(c[0].chars().reduce(0,(a,b)->b==';'?a+1:b=='}'?a*4:a));}}}

I'm sure it can be much shorter but i cant have much time now to optimize it

Answer 8

GNU sed, 330 326 - 10% = 293.4

(I added one for the use of -r before claiming the bonus 10%; I hope that's correct)

/;/{
s/[^};]//g
:c
s/(;*)\}/\1\1\1\1/
tc
:d
/;/{
s/;;;;;/v/g
s/vv/x/g
/[;v]/!s/\b/0/2
s/;;/b/g
s/bb/4/
s/b;/3/
s/v;/6/
s/vb/7/
s/v3/8/
s/v4/9/
y/;bvx/125;/
td
}
n
}
:u
s/\b9/;8/
s/\b8/;7/
s/\b7/;6/
s/\b6/;5/
s/\b5/;4/
s/\b4/;3/
s/\b3/;2/
s/\b2/;1/
s/\b1/;0/
s/\b0//
/[^;]/s/;/&&&&&&&&&&/g
tu
:v
s/;;;;/v/g
s/v+/{&}/
y/v/;/
tv

The full version shows that most of the above is conversion between decimal and unary:

#!/bin/sed -rf

/;/{

# Delete non-Curly characters
s/[^};]//g

# Curly to unary
:c
s/(;*)\}/\1\1\1\1/
tc

# unary to decimal
:d
/;/{
s/;;;;;/v/g
s/vv/x/g
/[;v]/!s/\b/0/2
s/;;/b/g
s/bb/4/
s/b;/3/
s/v;/6/
s/vb/7/
s/v3/8/
s/v4/9/
y/;bvx/125;/
td
}

# done
n

}


# Decimal to unary
:u
s/\b9/;8/
s/\b8/;7/
s/\b7/;6/
s/\b6/;5/
s/\b5/;4/
s/\b4/;3/
s/\b3/;2/
s/\b2/;1/
s/\b1/;0/
s/\b0//
/[^;]/s/;/&&&&&&&&&&/g
tu

# Unary to Curly
:v
s/;;;;/v/g
s/v+/{&}/
y/v/;/
tv

Answer 9

Perl, 183 177

This might not be the shortest Perl answer, but I think it's interesting enough to post (input in $_, output as return value):

sub f{if(/}/){s/[{}]/00/g;oct'0b'.s/00(;+)/sprintf'%02b',length$1/ger}else{$_=sprintf'%064b',$_;s/../oct"0b$&"/ge;s/^0+(?!$)//;$_='{'x length.$_;s/\d/'}'.';'x$&/ge;s/\Q{{}/{/r}}

We observe that Curly is simply quaternary (base-4) notation. We're slightly hampered by Perl's lack of native support for quaternary, but luckily, each quaternit is two bits in binary, and we can read and write binary. So we have the following:

1. Curly to decimal: convert each Curly digit to 2 binary digits, concatenate and convert to decimal
2. Decimal to Curly: print the number in binary (forcing an even number of digits), then convert each bit-pair to Curly.

Expanded version

sub f
{
    if (/}/) {
        s/[{}]/00/g;     # digits are now 00 00; 00;; 00;;;
                         # and opening braces become harmless leading zeros
        s/00(;+)/sprintf'%02b',length $1/ge;
                         # convert semicolons to binary, leaving zeros alone
        oct "0b$_"       # now to decimal
    } else {
        $_=sprintf'%064b',$_;   # decimal to binary
        s/../oct"0b$&"/ge;      # bit-pair to quaternit
        s/^0+(?!$)//;           #/remove leading zeros
        $_='{'x length.$_;      # prefix enough opening braces
        s/\d/'}'.';'x$&/ge;     #/digit to semicolons
        s/{{}/{/r               # first empty brace, unless $_ <= {};;;
    }
}

Answer 10

Retina, 69 64 bytes

+`{(;*)}
$1$1$1$1
^\d+|^(;*)
$*;$.1
+`(;+)\1\1\1
{$1}
^;|^$
{}$&

Try Test Suite

---

Explanation

+`{(;*)}
$1$1$1$1

Decompose the innermost braces to just ;s. Loop until no more braces.

^\d+|^(;*)
$*;$.1

Convert between decimal and unary ;

+`(;+)\1\1\1
{$1}

Find the longest run of ; that is a multiple of 4 and nest into braces, loop until no more runs of 4+ exist.

^;|^$
{}$&

If the resulting curly number begins with ; or is empty string, add {} in front.

Answer 11

Python 2, 157 bytes -10% = 141.3

lambda n:'{}'*(int(n)<4)+g(int(n))if n.isdigit()else sum((v==';')*4**n.count('}',i)for i,v in enumerate(n))
g=lambda n:'{%s}'%g(n/4)+';'*(n%4)if n>3else';'*n

Try it online!

A more golfed Python 2 answer that handles the bonus cases. Didn't want to necro dead posts with this as a comment, so here it is.

It works from the inside in on curly numbers, adding 4^(the number of end curly brackets left in the string) to the sum for each semicolon found. If the string is a number, then it recursively creates the curly number in the same way as the grammar provided.

Answer 12

Perl 5, 154 (185 170 Bytes - 10% + 1 Penalty)

$e=$/;if($_=~/{/){s/[^{};]//g;s/;/+1/g;s/{/+4*(/g;s/}/+0)/g;$b=eval}else{$r=$_;$b=$r<4?"{}":"";while($r>0){if($r%4>0){$r--;$e=";$e"}else{$b.="{";$e="}$e";$r/=4}}}$_=$b.$e

Regex & eval resolve the curlies.
The generation of the curlies is done differently.

Test

Test file contains also the bonus cases

$ cat curlytestcases.txt
{}
{};
{};;
{};;;
{;;}
{{;};};
{{{{;}}};}
0
1
2
3
4
17
96
{};;;;;
42{;} ;;;;
c{u;r;l}y;!
{{;;;;};;}

$ cat curlytestcases.txt |perl -p curlies.pl
0
1
2
3
8
21
260
{}
{};
{};;
{};;;
{;}
{{;}};
{{{;};;}}
5
8
9
72

Answer 13

JavaScript (ES6), 95 (105-10%)

f=(n,r='{}')=>-1-n?(n>3?'{'+f(n>>2,'')+'}':r)+';'.repeat(n&3):n.replace(/[;}]/g,c=>c>';'?n*=4:++n,n=0)&&n

Test running the snippet below

f=(n,r='{}')=>-1-n?(n>3?'{'+f(n>>2,'')+'}':r)+';'.repeat(n&3)
:n.replace(/[;}]/g,c=>c>';'?n*=4:++n,n=0)&&n

// Test
function out(x) { O.innerHTML=x+'\n'+O.innerHTML; }

function go() { out(I.value + ' --> ' + f(I.value)) }

;[ 
  ['{;;}', 8]
, ['{{;};};', 21 ]
, ['{};;;', 3 ]
, ['{{{{;}}};}', 260 ]
, ['{}', 0 ]
, [ 4, '{;}' ]
, [ 17, '{{;}};' ]
, [ 1,'{};' ]
, [ 0, '{}' ]
, [ 96, '{{{;};;}}' ]
, ['{};;;;;', 5 ]
, ['{{;;;;};;}' , 72 ]
, ['c{u;r;l}y;!', 9 ]
, ['42{;} ;;;;', 8 ]
].forEach(t => {
  r=f(t[0])
  k=t[1]
  out('Test ' +(r==k?'OK':'Fail')+'\nInput:  '+t[0]+'\nResult: '+r+'\nCheck:  '+k+'\n')
})

Custom test <input id=I><button onclick='go()'>-></button>
<pre id=O></pre>

Answer 14

Ruby, 126.9 129.6 (144 - 10%)

Uses recursion to convert decimal into curly form. Removing the check for ignoring characters outside of /[;{}]/ increases the score by 0.4 at the moment.

f=->s{s=~/^\d+$/?(n=s.to_i
"{#{n<1?'':f[(n/4).to_s].gsub('{}','')}}#{?;*(n%4)}"):eval(s.tr("^{;}","").gsub(/./){|c|c<?A?"+1":c>?|?")*4":"+(0"})}