Octally Balanced Braces with Raku

by Arne Sommer

Octally Balanced Braces with Raku

Published 6. January 2020

This is my response to the Perl Weekly Challenge #42.

Challenge #42.1: Octal Number System

Write a script to print decimal number 0 to 50 in Octal Number System.

For example:

Decimal 0 = Octal 0
Decimal 1 = Octal 1
Decimal 2 = Octal 2
Decimal 3 = Octal 3
Decimal 4 = Octal 4
Decimal 5 = Octal 5
Decimal 6 = Octal 6
Decimal 7 = Octal 7
Decimal 8 = Octal 10
and so on.

As a one-line program:

File: octal-fmt
say "Decimal $_ = Octal { $_.fmt('%o') }" for ^51;
############ 2  ######### 3           #### 1     #

[1] For each of the integers 0, 1 .. 50

[2] • print the integer

[3] • and the octal version, as specified with the format string '%o' to fmt.

See docs.raku.org/routine/sprintf for details about the format string directives.

See docs.raku.org/routine/fmt for more information about fmt.

Note that you can get away with double quoting the format string ("%o"), as long as it isn't followed by an element lookup. But stick with single quotes, unless you absolutely need interpolation.

> my %h = (A => 12, B => 13);  # -> {A => 12, B => 13}
> say "%h";                    # -> %h
> say "%h<>".raku;             # -> "A\t12\nB\t13"
> say "%h";                 # -> 12
> say "%h{}";                  # -> "A\t12\nB\t13"

Running it:

$ raku octal-fmt
Decimal 0 = Octal 0
Decimal 1 = Octal 1
Decimal 2 = Octal 2
Decimal 3 = Octal 3
Decimal 4 = Octal 4
Decimal 5 = Octal 5
Decimal 6 = Octal 6
Decimal 7 = Octal 7
Decimal 8 = Octal 10
Decimal 9 = Octal 11
Decimal 10 = Octal 12
Decimal 11 = Octal 13
Decimal 12 = Octal 14
Decimal 13 = Octal 15
Decimal 14 = Octal 16
Decimal 15 = Octal 17
Decimal 16 = Octal 20
Decimal 17 = Octal 21
Decimal 18 = Octal 22
Decimal 19 = Octal 23
Decimal 20 = Octal 24
Decimal 21 = Octal 25
Decimal 22 = Octal 26
Decimal 23 = Octal 27
Decimal 24 = Octal 30
Decimal 25 = Octal 31
Decimal 26 = Octal 32
Decimal 27 = Octal 33
Decimal 28 = Octal 34
Decimal 29 = Octal 35
Decimal 30 = Octal 36
Decimal 31 = Octal 37
Decimal 32 = Octal 40
Decimal 33 = Octal 41
Decimal 34 = Octal 42
Decimal 35 = Octal 43
Decimal 36 = Octal 44
Decimal 37 = Octal 45
Decimal 38 = Octal 46
Decimal 39 = Octal 47
Decimal 40 = Octal 50
Decimal 41 = Octal 51
Decimal 42 = Octal 52
Decimal 43 = Octal 53
Decimal 44 = Octal 54
Decimal 45 = Octal 55
Decimal 46 = Octal 56
Decimal 47 = Octal 57
Decimal 48 = Octal 60
Decimal 49 = Octal 61
Decimal 50 = Octal 62

That looks ok.

There is more than one way to do it...

The fmt call may not be especially intuitive, but the base method should be easier to understand:

File: octal-base
say "Decimal $_ = Octal { $_.base(8) }" for ^51;

See docs.raku.org/routine/base for more information about base.

The result of running it is the same as for «octal-fmt».

Challenge #42.2: Balanced Brackets

Write a script to generate a string with random number of ( and ) brackets. Then make the script validate the string if it has balanced brackets.

For example:

() - OK
(()) - OK
)( - NOT OK
())() - NOT OK

File: brackets-mono
unit sub MAIN (:$maxchars = 6, :$iterations = 10);   # [1]
############## # 1a ########## # 1b #############

sub brackets ($count = (1 .. $maxchars).pick)        # [5]
{
  return (^$count).map({ <( )>.pick }).join;         # [6]
}

sub is-balanced ($brackets)                          # [7]
{
  my $count = 0;                                     # [8]

  for $brackets.comb -> $char                        # [9]
  {
    if    $char eq '(' { $count++; }                 # [10]
    elsif $char eq ')' { $count--; }                 # [11]
    else { die "Illegal character $char"; }          # [12]
    
    return False if $count < 0; # Unbalanced inside  # [13]
  }
  
  return $count == 0;                                # [14]
}

for ^$iterations                                     # [2]
{
  my $brackets = brackets;                           # [3]
  say "$brackets - { is-balanced($brackets) ?? "OK" !! "NOT OK" }";  # [4]
}

[1] The default values, which can be overriden, are: 6 (maximum number of brackets to generate; string length) [1a], and 10 (number of iterations; number of lines) [1b].

[2] Iterate the specified number of times [1b].

[3] Get a line with a random selection of brackets, with a random length from 1 to the upper limit [1a].

[4] Is the string balanced?

[5] When called without an argument (as in [3]), it does as said in [3]. (If we were to call it with a value, that is the exact number of characters to use.)

[6] We start with a list of numbers (^$count). The actual values doesn't matter, but the number of elements does as that is the length of the resulting string of brackets. Then we use map to pick (randomly) one of the two brackets (<( )> expands to a list with two elements; ( and )) for each element. And finally we use join to get a string that we return.

[7] Is the string balanced?

[8] We use this variable to hold the indentation level (number of opening brackets).

[9] Iterate over the individual brackets:

[10] • if it as (, increase the counter (added a level).

[11] • if it as ), decrease the counter (remove a level).

[12] • if another character, kill off the program.

[13] • if the level is negative (caused by a closing bracket that didn't have a preceding opening bracket), we have an error and return False.

[14] When finished, return True if we are at level zero (all the opening brackets have been closed), and False otherwise.

I chose the value 6 as the upper limit of the numbers of characters, as that gives us a reasonable chance of getting balanced brackets. (But this can be changed with the «--maxchars» command line argument.)

Running it:

$ raku brackets-mono
( - NOT OK
()))( - NOT OK
((( - NOT OK
( - NOT OK
)()(() - NOT OK
))) - NOT OK
() - OK
))))) - NOT OK
(((() - NOT OK
) - NOT OK
$ raku brackets-mono
)( -  NOT OK 
(()(( -  NOT OK 
)(()( -  NOT OK 
) -  NOT OK 
((() -  NOT OK 
) -  NOT OK 
(()( -  NOT OK 
(()(( -  NOT OK 
( -  NOT OK 
()))(( -  NOT OK 
$ raku brackets-mono
)()) -  NOT OK 
()))( -  NOT OK 
())( -  NOT OK 
)( -  NOT OK 
( -  NOT OK 
) -  NOT OK 
))) -  NOT OK 
)((()) -  NOT OK 
(() -  NOT OK 
)()(() -  NOT OK

It is easier to see the (few) validated strings if we add colour (as I did in challenge 21):

File: brackets (with the changes highlighted)
unit sub MAIN (:$maxchars = 6, :$iterations = 10, :$color);  [1]

sub brackets ($count = (1 .. $maxchars).pick)
{
  return (^$count).map({ <( )>.pick }).join;
}

sub is-balanced ($brackets)
{
  return False if $brackets.chars % 2;                 # [2]
  return False if $brackets.substr(0,  1) eq ')';      # [3]
  return False if $brackets.substr(*-1,1) eq '(';      # [4]

  my $count = 0;

  for $brackets.comb -> $char
  {
    if    $char eq '(' { $count++; }
    elsif $char eq ')' { $count--; }
    else { die "Illegal character $char"; }
    
    return False if $count < 0; # Unbalanced inside
  }
  
  return $count == 0;
}

for ^$iterations
{
  my $brackets = brackets;

  $color  # [5]
    ?? say "$brackets - { is-balanced($brackets) ?? "\x1b[42m" ~ "OK" !! "\x1b[41m" ~ "NOT OK" }" ~ "\x1b[0m"
    !!  say "$brackets - { is-balanced($brackets) ?? "OK" !! "NOT OK" }";
}

I have also added some shortcuts, so that we can detect unbalanced brackets without traversing the entire string. They don't change the outcome of the program, but will speed it up if we were to use very long strings (a hight value for «--maxchars«).

[1] Specify «--color» on the command line to activate colour.

[2] The brackets are unbalanced if the total number of charcater are odd.

[3] The first character must be (.

[4] The last character must be ).

[5] Colour code the OK/NOT OK strings.

See e.g. www.lihaoyi.com/post/BuildyourownCommandLinewithANSIescapecodes.html for a description of the ANSI codes.

Running it:

$ raku brackets --color
() - OK
) - NOT OK
()((( - NOT OK
)()()) - NOT OK
() - OK
() - OK
))))(( - NOT OK
((())) - OK
) - NOT OK
)( - NOT OK

Much nicer.

And that's it.