33
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ how it should handle case if you have not matching number of parenthesis ? or shall i assume it will never happened? \$\endgroup\$ – user902383 Sep 14 '15 at 14:39
  • \$\begingroup\$ @user902383 You can assume that non-matching curly braces will never happen. \$\endgroup\$ – DLosc Sep 14 '15 at 14:47
  • 2
    \$\begingroup\$ I was going to make a Retina solution, but after making it handle a Curly string (only 20 bytes), I realized it also needs to handle positive integers -> Curly, so I gave up. \$\endgroup\$ – mbomb007 Sep 14 '15 at 20:55
  • \$\begingroup\$ @DLosc Yeah, it wouldn't win, so I'm not going to spend the time. \$\endgroup\$ – mbomb007 Sep 14 '15 at 21:02
  • \$\begingroup\$ @mbomb007 I meant on this question specifically, where the Pyth solution is already 22% shorter than the shortest CJam solution and qualifies for the bonus. Anyway, it was a rhetorical question attempting to say, "No, but it could still be fun and garner some upvotes." If you disagree with the "fun" part, though, that's fine. \$\endgroup\$ – DLosc Sep 14 '15 at 21:11

14 Answers 14

15
\$\begingroup\$

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
\$\endgroup\$
  • 2
    \$\begingroup\$ Fastest gun in the west :( I had this exact solution except I had forgotten that the .[Z2 was necessary. \$\endgroup\$ – orlp Sep 14 '15 at 9:07
12
\$\begingroup\$

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#
\$\endgroup\$
7
\$\begingroup\$

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.

\$\endgroup\$
6
\$\begingroup\$

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*

\$\endgroup\$
  • 4
    \$\begingroup\$ Welcome to PPCG! Your code contains a lot of unrequired print statements and a comment, your variable names are too long and some whitespace can be eliminated. I also recommend reading Tips for golfing in Pyrhon. \$\endgroup\$ – Dennis Sep 15 '15 at 14:34
  • \$\begingroup\$ Great resource, thanks! I'll make the appropriate changes to this code and see how far it gets me. Looks like if I want to be anybody on this site, I either need to learn CJam or Pyth, or write my own language lol. \$\endgroup\$ – Taylor Lopez Sep 15 '15 at 14:50
  • 3
    \$\begingroup\$ @iAmMortos Not necessarily. Do if you find it enjoyable, or stick with Python if not. :) \$\endgroup\$ – DLosc Sep 15 '15 at 15:13
  • 2
    \$\begingroup\$ Usually, golfing is done in three steps: 1) make your program like you would do normally, as minimal as possible (i.e., no debug statements, no need to handle invalid input, minimal output) 2) remove as much as possible: whitespace, rename variables (value to v etc), 3) do clever golfing stuff: this is the point where you need to look at Dennis' link. I'm curious to see how much you can cut this down! \$\endgroup\$ – Sanchises Sep 15 '15 at 15:18
  • 1
    \$\begingroup\$ Never have I received such a warm welcome on a community. lol, I think I like it here. \$\endgroup\$ – Taylor Lopez Sep 15 '15 at 15:47
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Wouldn't your score be 80.1? \$\endgroup\$ – PurkkaKoodari Sep 14 '15 at 4:29
  • 4
    \$\begingroup\$ @Pietu1998 Thanks. Not only are my solutions too long, apparently I also fail at basic arithmetic... \$\endgroup\$ – Reto Koradi Sep 14 '15 at 5:05
3
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ You can save one Byte by using var instead of char in the foreach loops. \$\endgroup\$ – raznagul Sep 14 '15 at 13:33
  • \$\begingroup\$ @DLosc, sorry, I was confused by bonus #1. I though that applied to output rather than input. \$\endgroup\$ – Hand-E-Food Sep 14 '15 at 22:19
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ @DLosc damn, right, and thought i can have a nice result with java:( \$\endgroup\$ – user902383 Sep 14 '15 at 15:05
  • \$\begingroup\$ also: common optimisation on java is to avoid the public before class \$\endgroup\$ – masterX244 Sep 14 '15 at 15:52
  • \$\begingroup\$ replace the public static void main(String[]c){ with static{ \$\endgroup\$ – das_j Sep 17 '15 at 14:14
2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Unfortunately, this question explicitly says decimal is required, which is why I bothered converting. \$\endgroup\$ – Toby Speight Sep 16 '15 at 13:14
  • \$\begingroup\$ You're right, which is a bit astonishing to me since excluding unary wasn't my intention. Oh well, guess it's too late to change the question now. I reaffirm my +1, sir. \$\endgroup\$ – DLosc Sep 16 '15 at 18:51
2
\$\begingroup\$

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 $_ <= {};;;
    }
}
\$\endgroup\$
1
\$\begingroup\$

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>

\$\endgroup\$
  • \$\begingroup\$ Could you please post your actual code? Also, your score is 94.5. \$\endgroup\$ – Erik the Outgolfer Apr 12 '16 at 11:50
  • \$\begingroup\$ @ErikKonstantopoulos my actual code was posted at top of the test snippet. Now it is at top of the answer too. About the score (that should be in bytes), I always feel funny measuring half (or less) byte and prefer rouniding up \$\endgroup\$ – edc65 Apr 12 '16 at 12:35
  • \$\begingroup\$ edc65: Yeah, but rounding up is bad for you! 94.5<95 thus smaller score, which means that it probably beats more submissions. Also, the "top of the snippet" is not the place to show your code. \$\endgroup\$ – Erik the Outgolfer Apr 12 '16 at 12:40
1
\$\begingroup\$

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"})}
\$\endgroup\$
  • \$\begingroup\$ It's fixed now. Thanks for reporting the bug; score has been updated. \$\endgroup\$ – Value Ink Apr 16 '16 at 6:39
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Added the -1 penalty for -p. The $b=$r<2?"{}":""; was added for the exception of 0 & 1. {};;; is the input in the test. \$\endgroup\$ – LukStorms Sep 16 '15 at 6:58
  • \$\begingroup\$ Needed some time to test it. It's fixed now. :) \$\endgroup\$ – LukStorms Sep 16 '15 at 7:45
  • \$\begingroup\$ I think the +1 penalty comes after -10% bonus. \$\endgroup\$ – Erik the Outgolfer Apr 12 '16 at 11:47
  • \$\begingroup\$ Interesting observation. Not sure if that's now it should be, but it makes sense so I changed it anyway. Not that it changes the end score. \$\endgroup\$ – LukStorms Apr 19 '16 at 15:11
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ That's awkward. I even had test cases in there for numbers less than 2. Fixed for +5 bytes total. \$\endgroup\$ – Arnold Palmer Jul 20 '17 at 20:07
  • \$\begingroup\$ @DLosc I swear I'm normally not this bad. Fixed, and golfed a bit to make it a bit more competitive. \$\endgroup\$ – Arnold Palmer Jul 21 '17 at 2:12

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.