90
\$\begingroup\$

In the popular (and essential) computer science book, An Introduction to Formal Languages and Automata by Peter Linz, the following formal language is frequently stated:

$$\large{L=\{a^n b^n:n\in\mathbb{Z}^+\}}$$

mainly because this language can not be processed with finite-state automata. This expression mean "Language L consists all strings of 'a's followed by 'b's, in which the number of 'a's and 'b's are equal and non-zero".

Challenge

Write a working program/function which gets a string, containing "a"s and "b"s only, as input and returns/outputs a truth value, saying if this string is valid the formal language L.

  • Your program cannot use any external computation tools, including network, external programs, etc. Shells are an exception to this rule; Bash, e.g., can use command line utilities.

  • Your program must return/output the result in a "logical" way, for example: returning 10 instead of 0, "beep" sound, outputting to stdout etc. More info here.

  • Standard code golf rules apply.

This is a . Shortest code in bytes wins. Good luck!

Truthy test cases

"ab"
"aabb"
"aaabbb"
"aaaabbbb"
"aaaaabbbbb"
"aaaaaabbbbbb"

Falsy test cases

""
"a"
"b"
"aa"
"ba"
"bb"
"aaa"
"aab"
"aba"
"abb"
"baa"
"bab"
"bba"
"bbb"
"aaaa"
"aaab"
"aaba"
"abaa"
"abab"
"abba"
"abbb"
"baaa"
"baab"
"baba"
"babb"
"bbaa"
"bbab"
"bbba"
"bbbb"

Leaderboard

Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.

/* Configuration */

var QUESTION_ID = 85994; // Obtain this from the url
// It will be like https://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 48934; // This should be the user ID of the challenge author.

/* App */

var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;

function answersUrl(index) {
  return "https://api.stackexchange.com/2.2/questions/" +  QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

function commentUrl(index, answers) {
  return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}

function getAnswers() {
  jQuery.ajax({
    url: answersUrl(answer_page++),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      answers.push.apply(answers, data.items);
      answers_hash = [];
      answer_ids = [];
      data.items.forEach(function(a) {
        a.comments = [];
        var id = +a.share_link.match(/\d+/);
        answer_ids.push(id);
        answers_hash[id] = a;
      });
      if (!data.has_more) more_answers = false;
      comment_page = 1;
      getComments();
    }
  });
}

function getComments() {
  jQuery.ajax({
    url: commentUrl(comment_page++, answer_ids),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      data.items.forEach(function(c) {
        if (c.owner.user_id === OVERRIDE_USER)
          answers_hash[c.post_id].comments.push(c);
      });
      if (data.has_more) getComments();
      else if (more_answers) getAnswers();
      else process();
    }
  });  
}

getAnswers();

var SCORE_REG = /<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;

var OVERRIDE_REG = /^Override\s*header:\s*/i;

function getAuthorName(a) {
  return a.owner.display_name;
}

function process() {
  var valid = [];
  
  answers.forEach(function(a) {
    var body = a.body;
    a.comments.forEach(function(c) {
      if(OVERRIDE_REG.test(c.body))
        body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>';
    });
    
    var match = body.match(SCORE_REG);
    if (match)
      valid.push({
        user: getAuthorName(a),
        size: +match[2],
        language: match[1],
        link: a.share_link,
      });
    
  });
  
  valid.sort(function (a, b) {
    var aB = a.size,
        bB = b.size;
    return aB - bB
  });

  var languages = {};
  var place = 1;
  var lastSize = null;
  var lastPlace = 1;
  valid.forEach(function (a) {
    if (a.size != lastSize)
      lastPlace = place;
    lastSize = a.size;
    ++place;
    
    var answer = jQuery("#answer-template").html();
    answer = answer.replace("{{PLACE}}", lastPlace + ".")
                   .replace("{{NAME}}", a.user)
                   .replace("{{LANGUAGE}}", a.language)
                   .replace("{{SIZE}}", a.size)
                   .replace("{{LINK}}", a.link);
    answer = jQuery(answer);
    jQuery("#answers").append(answer);

    var lang = a.language;
    if (/<a/.test(lang)) lang = jQuery(lang).text();
    
    languages[lang] = languages[lang] || {lang: a.language, user: a.user, size: a.size, link: a.link};
  });

  var langs = [];
  for (var lang in languages)
    if (languages.hasOwnProperty(lang))
      langs.push(languages[lang]);

  langs.sort(function (a, b) {
    if (a.lang > b.lang) return 1;
    if (a.lang < b.lang) return -1;
    return 0;
  });

  for (var i = 0; i < langs.length; ++i)
  {
    var language = jQuery("#language-template").html();
    var lang = langs[i];
    language = language.replace("{{LANGUAGE}}", lang.lang)
                       .replace("{{NAME}}", lang.user)
                       .replace("{{SIZE}}", lang.size)
                       .replace("{{LINK}}", lang.link);
    language = jQuery(language);
    jQuery("#languages").append(language);
  }

}
body { text-align: left !important}

#answer-list {
  padding: 10px;
  width: 290px;
  float: left;
}

#language-list {
  padding: 10px;
  width: 290px;
  float: left;
}

table thead {
  font-weight: bold;
}

table td {
  padding: 5px;
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">
<div id="answer-list">
  <h2>Leaderboard</h2>
  <table class="answer-list">
    <thead>
      <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>
    </thead>
    <tbody id="answers">

    </tbody>
  </table>
</div>
<div id="language-list">
  <h2>Winners by Language</h2>
  <table class="language-list">
    <thead>
      <tr><td>Language</td><td>User</td><td>Score</td></tr>
    </thead>
    <tbody id="languages">

    </tbody>
  </table>
</div>
<table style="display: none">
  <tbody id="answer-template">
    <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>
<table style="display: none">
  <tbody id="language-template">
    <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>

\$\endgroup\$
18
  • 24
    \$\begingroup\$ Can the input be empty? (You're saying it's not part of the language, but not whether it's an input we need to consider.) \$\endgroup\$ Jul 20, 2016 at 20:04
  • 1
    \$\begingroup\$ What if our language doesn't have truthy or falsy? Would empty string == truthy and non-empty string == falsy be acceptable? \$\endgroup\$
    – DJMcMayhem
    Jul 20, 2016 at 20:20
  • 5
    \$\begingroup\$ Nice challenge, but I think the title could be a little less ambiguous (i.e. a mention of a^n b^n or similar, rather than just the number of as equalling the number of bs) \$\endgroup\$
    – Sp3000
    Jul 21, 2016 at 12:28
  • 1
    \$\begingroup\$ @Sp3000 I choosed this title because it looked fun . I may change it later to sth else ... \$\endgroup\$
    – user55673
    Jul 21, 2016 at 13:27
  • 2
    \$\begingroup\$ I'm a little surprised that in 50+ answers I'm the only one to use a paser generator. To be sure it's not strictly competitive on length, but the problem posed is one of parsing a simple but non-trivial language. I'd very much like to see answers in other compiler-compiler syntaxes because I am not widely familiar with the choices. \$\endgroup\$ Jul 22, 2016 at 22:47

108 Answers 108

1 2 3
4
0
\$\begingroup\$

Batch, 50 bytes

@set x=%1
@if %x:b=%%x%%x:a=% neq %x:b=a%%x:a=b% *

Output nothing and return 0 for true and something returning 9009 for false

If %x% contain a as and b bs, %x:b=%%x%%x:a=% contains 2a as and 2b bs, while %x:b=a%%x:a=b% contain a+b as and a+b bs, so if they're equal, a=b. Meanwhile, %x% in %x:b=%%x%%x:a=% occupies the middle part, which in %x:b=a%%x:a=b% is a as and a bs, so they can be and will be equal if it matchs {a}^n{b}^n.

For empty string, the IF statement fails to parse and echo about that.

\$\endgroup\$
0
\$\begingroup\$

Python 2.7, 37 bytes

lambda s:s.count('a')==s.count('b')>0
\$\endgroup\$
0
\$\begingroup\$

Gol><>, 26 bytes

&TiE!tlF:`a=Q&P&~{|}|l&-zh

Wow, five minutes and it is already smaller, 4 bytes knocked off!

Try it online!

Older version, 30 bytes

&TiE!tlF:`a=:Q&P&~|zQ}||l&-0=h

Wow! This was going to be alot larger than this, but I realized that I can combine 2 checks in one towards the end. This can be golfed alot more, but I will be working on that soon!!!

&TiE!t                           //Get all of the characters
      lF                         //Loop through the entire stack
        :`a=:                    //Check if it is equal to a
             Q&P&~|              //If so, increment a variable and delete that character
                   zQ}|          //Otherwise, continue
                       |         //end of loop
                        l&-0=h   //the remaining b# is subtracted from the # of a, if it is zero it will output 1, otherwise 0

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ abab should be falsey. I know the title is misleading, but truthy cases are only as followed by only bs. e.g. aaabbb is true, ababab is false \$\endgroup\$
    – Jo King
    Mar 20, 2019 at 23:41
  • \$\begingroup\$ @JoKing Well then, I will fix that, it should be an easy fix where I do the deleting process, delete the previous letter rather than itself, and then check if the previous and itself are the same. Thanks for pointing that out, I'll fix it as soon as I have time \$\endgroup\$ Mar 21, 2019 at 0:12
0
\$\begingroup\$

Perl 6 (33 bytes)

{?/^(a+)(b+)$/&&$0.ords==$1.ords}
\$\endgroup\$
3
  • \$\begingroup\$ Fixed the first problem. And I'm sure chrs works, because == coerces its arguments into numbers before performing the comparison. \$\endgroup\$
    – bb94
    Mar 21, 2019 at 2:07
  • \$\begingroup\$ You're right; I was thinking of ords. \$\endgroup\$
    – bb94
    Mar 21, 2019 at 2:13
  • 1
    \$\begingroup\$ 30 bytes \$\endgroup\$
    – Jo King
    Mar 21, 2019 at 2:22
0
\$\begingroup\$

APL(NARS), 23 chars, 46 bytes

{⍵≡'':0⋄⍵≡'ab'/⍨⌈2÷⍨≢⍵}

test:

  f←{⍵≡'':0⋄⍵≡'ab'/⍨⌈2÷⍨≢⍵}
  f ''
0
  f¨(,'a')(,'b')('aa')('ba')
0 0 0 0 
  f¨('ab')('aabb')('aaabbb')('aaaabbbb')
1 1 1 1 
  f¨('abb')('aabbb')('aaaabbb')('aaaaabbbb')
0 0 0 0 
\$\endgroup\$
0
\$\begingroup\$

C# (Visual C# Interactive Compiler), 54 bytes

x=>x!=""&!x.OrderBy(y=>-y).Where((y,i)=>y==x[i]).Any()

Try it online!

Port of Dennis's MATL solution. Below is a 48 byte version that matches the empty string.

x=>!x.OrderBy(y=>-y).Where((y,i)=>y==x[i]).Any()

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Python 2, 42 bytes

f=lambda s:s=='ab'or s<s[-1:]>0<f(s[1:-1])

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Stax, 8 bytes

é«<òαøòâ

Run and debug it

It compares the input with "ab" having its characters repeated inputLength / 2 times.

\$\endgroup\$
0
\$\begingroup\$

C, 85 bytes

n,d;f(char*v){while(*v)if(*v++&1){if(n++,d)return 0;}else d?n--:(n--,d=1);return!n;}

Pretty long. Seems to handle all edge cases correctly.

Ungolfed:

n, d;
f (char *v) {
    while (*v)
        if (*v++ & 1) {
            if(n++, d)
                return 0;
        } else
            d ? n-- : (n-- , d = 1);
    return !n;
}
\$\endgroup\$
0
\$\begingroup\$

brainfuck and bfasm, 995 and 119 bytes

Quite easy to outgolf.

Generated using following assembly code:

mov r4,.a
lbl 1
in_ r1
jz_ r1,3
eq_ r1,r4
jnz r1,2
inc r3
dec r2
lbl 2
inc r2
jmp 1
lbl 3
eq_ r2,r3
out r2

And then optimized by hand.

+>+[<[>>+>+<<<-]>>[<<+>>-]>[[-]>>>>--[----->+<]>-----<<<<<]>+<<+<<[>>->+<<<-]>>>[<<<+>>>-]<[->+<<[>>>-<<+<-]>[<+>-]>>[<->[-]]<[<<<+>>>-]<]<<[>>+>+<<<-]>>[<<+>>-]>[[-]>>,>>>>+++<<<<<<+>>[<<[-]<+>>>-]<<<[>>>+<<<-]>[<<<[-]>[-]>>>>>>>>[<<<<<<<<+>+>>>>>>>-]<<<<<<<[>>>>>>>+<<<<<<<-]>[-]]>>>>>>[-]<<<<<<]<<<[>>+>+<<<-]>>[<<+>>-]>[[-]>>[<<+>>-]+>>>[<<<<<-<+>>>>>>-]<<<<<<[>>>>>>+<<<<<<-]>[>>-<<[-]]>>>>>>++<<<<[<<<+>+>>-]<<<[>>>+<<<-]>[<<<[-]>[-]>>>>>>>>[<<<<<<<<+>+>>>>>>>-]<<<<<<<[>>>>>>>+<<<<<<<-]>[-]]>>>>>>[-]<<<<<<]<<<[>>+>+<<<-]>>[<<+>>-]>[[-]>>>>+<-<<<]>++<<+<<[>>->+<<<-]>>>[<<<+>>>-]<[->+<<[>>>-<<+<-]>[<+>-]>>[<->[-]]<[<<<+>>>-]<]>>[-]<<<<[>>+>+<<<-]>>[<<+>>-]>[[-]>>>+>>>+<<<<<<<<<[-]>[-]>>>>>>>>[<<<<<<<<+>+>>>>>>>-]<<<<<<<[>>>>>>>+<<<<<<<-]>>>>>>>[-]<<<<<<]>+++<<+<<[>>->+<<<-]>>>[<<<+>>>-]<[->+<<[>>>-<<+<-]>[<+>-]>>[<->[-]]<[<<<+>>>-]<]>>[-]<<<<[>>+>+<<<-]>>[<<+>>-]>[[-]>>>[<<<+>>>-]+>[<<<<-<+>>>>>-]<<<<<[>>>>>+<<<<<-]>[>>>-<<<[-]]>>>.<<<]<<<[>>+>+<<<-]>>[<<+>>-]>[[-]<<<[-]>[-]>>]<<]

Try it online!

\$\endgroup\$
0
\$\begingroup\$

C# .NET 135 bytes

public class P{public static void Main(string[]a){System.Console.Write(a[0]!=""&&a[0].Split('a').Length-1==a[0].Split('b').Length-1);}}

Try online

\$\endgroup\$
0
\$\begingroup\$

GolfScript, 20 bytes

.,2//zip{"ab"=}%{&}*

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Unix TMG, 64 bytes

p:<a>f((<b>))parse((any(!<<>>)|={<1>}));f:proc(x)<a>f((<b>x))|x;

Works by recursive-descent parsing. It outputs "1" for match, nothing otherwise.

Expanded:

prog:   <a> recurs(( <b> )) parse(( any(!<<>>) | = { <1> } ));
recurs: proc(x) <a> recurs(( <b> x )) 
      | x;

The solution is based on the one in McIlroy's Tmg Manual (1972) for anbncn.

\$\endgroup\$
0
\$\begingroup\$

shortC, 41 bytes

AIa,b;K"%*[a]%n%*[b]%n",&a,&b);T++b-2*a+G

Try it online!

C (gcc), 69 bytes

main(){int a,b;scanf("%*[a]%n%*[b]%n",&a,&b);return 2*a/b+getchar();}

Try it online!

returns 0 if correct. I think I made it very hard to read when debugging, here is explanation:

int main(){
    int a,b;
    scanf("%*[a]%n%*[b]%n",&a,&b);      // skips As, assigns count to a, skips Bs, assigns total to b
    return 2*a/b                // checks to make sure As and Bs are equal. Should give 1  (a/b = 1 if a=b)
    +getchar();             // adds return of getchar, EOF if no trailing chars so checks for possibilities like abab
}                       // they add together to make 0, which is normally an "all clear" exit code

                second post!
\$\endgroup\$
2
  • \$\begingroup\$ As you might see, the meat is in using (abusing) scanf's hidden powers. There is a problem with the first c version, because when dividing a/b it may say 'aab' is correct because it truncates the fractional part. fortunately, I fixed it in the shortC version. \$\endgroup\$
    – Wezl
    Apr 17, 2020 at 17:52
  • \$\begingroup\$ 63 bytes \$\endgroup\$
    – ceilingcat
    Aug 20, 2020 at 5:40
0
\$\begingroup\$

Shue, 83 bytes

y
n
a=ay
b=yb
ayb=y
=L
=R
ayR=yR
Lyb=Ly
ayR=n
Lyb=n
ba=#
#a=#
#b=#
a#=#
b#=#
#=n
=n

Try it online!

Outputs y for yes and n for no

\$\endgroup\$
0
\$\begingroup\$

Lua, 46 bytes

a,b=(...):match"^(a+)(b+)$";return a and#a==#b

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Go, 126 bytes

func f(s string)bool{l:=len(s)-1
if l<1{return false}
x,y:=s[0]==97,s[l]==98
if l<2&&x&&y{return true}
return x&&y&&f(s[1:l])}

Attempt This Online!

Recursive function, input is a string and returns a boolean. This checks the first and last characters, and recurses on the middle string.

Ungolfed:

func f(s string) bool {
    l := len(s)
    if l<2 {
        return false
    }
    x, y := s[0]=='a', s[l-1]=='b'
    if l==2 && x && y {
        return true
    }
    return x && y && f(s[1:l-1])
}

Attempt This Online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ I see a lot of improvements that can be done to this function without changing its underlying algorithm. You can lose the x and y variables. Everything can be in two statements, one of them being the return. There's no need to refer to 97 and 98; the challenge guarantees that input only contains 'a' and 'b', so you can compare them against each other (note that 97 < 98). \$\endgroup\$
    – Deadcode
    Jul 11, 2022 at 5:01
0
\$\begingroup\$

TypeScript’s type system, 80 bytes

type F<S>=S extends`a${infer A}b${infer B}`?B extends`a${any}`?B:F<`${A}${B}`>:S

Try it at the TS playground! Returns falsey (empty string) if there is an equal number of As and Bs, non-empty string otherwise.

This is a generic type F<S> which takes a string type and recursively removes a leading a and the first b, unless there’s an a after the first b.

This is the kind of challenge where TS types can really be competitive with actual programming languages!

\$\endgroup\$
1 2 3
4

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.