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

3
\$\begingroup\$

05AB1E, 6 bytes

ÇÂs{αß

Only 1 is truthy in 05AB1E, and it'll output 0 (or "" for the empty string) as falsey.

Try it online or verify all test cases.

Explanation:

Ç       # Convert the (implicit) input-string to a list of integer codepoints
        #  i.e. "aaabbb" → [97,97,97,98,98,98]
        #  i.e. "baba" → [98,97,98,97]
        #  i.e. "aab" → [97,97,98]
        #  i.e. "" → []
 Â      # Bifurcate this list (short for Duplicate & Reverse copy)
        #  STACK: [[97,97,97,98,98,98], [98,98,98,97,97,97]]
        #  STACK: [[98,97,98,97], [97,98,97,98]]
        #  STACK: [[97,97,98], [98,97,97]]
        #  STACK: [[], []]
  s     # Swap to get the duplicated list
        #  STACK: [[98,98,98,97,97,97], [97,97,97,98,98,98]]
        #  STACK: [[97,98,97,98], [98,97,98,97]]
        #  STACK: [[98,97,97], [97,97,98]]
        #  STACK: [[], []]
   {    # Sort it
        #  STACK: [[98,98,98,97,97,97], [97,97,97,98,98,98]]
        #  STACK: [[97,98,97,98], [97,97,98,98]]
        #  STACK: [[98,97,97], [97,97,98]]
        #  STACK: [[], []]
    α   # Take the absolute difference at the same positions
        #  STACK: [[1,1,1,1,1,1]]
        #  STACK: [[0,1,1,0]]
        #  STACK: [[1,0,1]]
        #  STACK: [[], []]
     ß  # And take the minimum, which will be 1 if all were truthy;
        # 0 if any were falsey; or an empty string if the list is empty
        #  STACK: [1]
        #  STACK: [0]
        #  STACK: [0]
        #  STACK: [""]
        # (after which it is output implicitly as result)
\$\endgroup\$
3
\$\begingroup\$

Java 8, 69 37 bytes

 s->s.matches("(a(?=a*(\\2?+b)))+\\2")

Regex shamelessly 'borrowed' from here.
-6 bytes thanks to @Deadcode, plus a bit more by converting Java 7 to 8

Try it online.

Explanation:

s->                   // Method with String parameters and boolean return-type
  s.matches("...")    //  Check if the String matches the regex explained below

Regex explanation:

^                   $ # (implicit by String#matches: match entire String)
                 +    # Repeat one or more times:
 (              )     #  Capture group 1, which does:
  a                   #   Match an 'a'
   (?=         )      #    With a positive look-ahead to:
      a*              #     0 or more 'a's
        (     )       #     Followed by, in capture group 2:
         \2           #      The value of capture group 2,
           ?+         #      zero or one times, giving prio to one, without backtracking
             b        #      Following by a 'b'
                  \2  # Followed by the value of capture group 2 (the 'b's)
\$\endgroup\$
6
  • 1
    \$\begingroup\$ -6 bytes. The eXtended flag isn't needed, as there's no whitespace in the regex. \$\endgroup\$
    – Deadcode
    Jul 7, 2022 at 7:40
  • \$\begingroup\$ And of course, 37 bytes in Java 8. \$\endgroup\$
    – Deadcode
    Jul 7, 2022 at 7:41
  • \$\begingroup\$ Why does the static get to be excluded from the Java 7 version's byte length? It doesn't work without it, at least in the code snippet you provided. \$\endgroup\$
    – Deadcode
    Jul 7, 2022 at 7:43
  • 1
    \$\begingroup\$ Before you ask about the downvote, it was a misclick that I didn't notice until it showed up as a rep change... \$\endgroup\$ Jul 7, 2022 at 13:28
  • 1
    \$\begingroup\$ @UnrelatedString I've made a minor edit in case you want to change your downvote to an upvote. \$\endgroup\$ Jul 7, 2022 at 14:39
2
\$\begingroup\$

C (Ansi), 65 75 Bytes

Golfed:

l(b,i,j,k)char*b;{for(i=j=0;(k=b[i++])>0&k<=b[i];)j+=2*(k>97)-1;return !j;}

Explanation:

Sets a value j and increments j on each b and decrements j on anything else. Checked if the letter before is less than or equal the next letter so prevent abab from working

Edits

Added checks for abab cases.

\$\endgroup\$
2
  • \$\begingroup\$ Won't this give false positives on strings like ba or abab? \$\endgroup\$
    – Zgarb
    Jul 20, 2016 at 19:43
  • \$\begingroup\$ Ahh yes, I misread the post since I could not see the picture since its blocked for me. Fixing it! \$\endgroup\$
    – dj0wns
    Jul 20, 2016 at 19:50
2
\$\begingroup\$

Batch, 133 bytes

@if ""=="%1" exit/b1        Fail if the input is empty
@set a=%1                   Grab the input into a variable for processing
@set b=%a:ab=%              Remove all `ab` substrings
@if "%a%"=="%b%" exit/b1    Fail if we didn't remove anything
@if not %a%==a%b%b exit/b1  Fail if we removed more than one `ab`
@if ""=="%b%" exit/b0       Success if there's nothing left to check
@%0 %b%                     Rinse and repeat

Returns an ERRORLEVEL of 0 on success, 1 on failure. Batch doesn't like to do substring replacement on empty strings, so we have to check that up front; if an empty parameter was legal, line 6 wouldn't be necessary.

\$\endgroup\$
2
\$\begingroup\$

PowerShell v2+, 61 52 bytes

param($n)$x=$n.length/2;$n-and$n-match"^a{$x}b{$x}$"

Takes input $n as a string, creates $x as half the length. Constructions an -and Boolean comparison between $n and a -match regex operator against the regex of an equal number of a's and b's. Outputs Boolean $TRUE or $FALSE. The $n-and is there to account for ""=$FALSE.

Alternate, 35 bytes

$args-match'^(a)+(?<-1>b)+(?(1)c)$'

This uses the regex from Leaky's answer, based on .NET balancing groups, just encapsulated in the PowerShell -match operator. Returns the string for truthy, or empty string for falsey.

\$\endgroup\$
2
  • \$\begingroup\$ In the alternate version you should evaluate -match against $args[0], otherwise -match will work as a filter \$\endgroup\$ Jul 24, 2016 at 18:18
  • \$\begingroup\$ @MathiasR.Jessen In production code, yes, but we can golf the [0] here because we're only given one input and we only need one truthy/falsey value as output. Since an empty string is falsey and a non-empty string is truthy, we can filter against the array and either get the input string back or nothing back, which satisfies the challenge requirements. \$\endgroup\$ Jul 25, 2016 at 12:30
2
\$\begingroup\$

Pyth - 13 bytes

&zqzS*/lz2"ab

Explained:

  qz          #is input equal to
          "ab #the string "ab"
     *        #multiplied by
      /lz2    #length of input / 2
    S         #and sorted?
&z            #(implicitly) print if the above is true and z is not empty
\$\endgroup\$
3
  • \$\begingroup\$ You can use a string as input and then make it &qS*/lQ2"ab \$\endgroup\$
    – Leaky Nun
    Jul 20, 2016 at 20:25
  • \$\begingroup\$ @LeakyNun thanks for the tip! Can you explain how/why that works? This is my first time ever using Pyth \$\endgroup\$ Jul 20, 2016 at 20:46
  • \$\begingroup\$ For example, +4 will expand to +4Q (implicit filling of arguments) \$\endgroup\$
    – Leaky Nun
    Jul 21, 2016 at 4:07
2
\$\begingroup\$

Haskell, 39 bytes

p x=elem x$scanl(\s _->'a':s++"b")"ab"x

Usage example: p "aabb" -> True.

scanl(\s _->'a':s++"b")"ab"x build a list of all ["ab", "aabb", "aaabbb", ...] with a total of (length x) elements. elem checks if x is in this list.

\$\endgroup\$
2
\$\begingroup\$

Octave, 28 bytes

@(m)diff(+m)>=0&~sum(m-97.5)

This defines an anonymous function. It works also for empty input. Falsy and truthy are as described in my MATL answer.

Try it at ideone.

Explanation

diff(+m)>0 checks if the input string (consisting of 'a' and 'b') is sorted, that is, all characters 'a' come before all 'b'.

The other condition that needs to be checked is whether the numbers of characters 'a' and 'b' are the same. Since their ASCII codes are 97 ansd 98, this is done subtracting 97.5 and chacking if the the sum is zero.

For empty input the result is empty, which is falsy.

\$\endgroup\$
2
\$\begingroup\$

Mathematica 83 80 68 54 bytes

#&@@@#<>""=="ab"&&Equal@@Length/@#&@*Split@*Characters

Thanks @MartinEnder for shortening it by 26 bytes :)

If input can be a list of characters instead of a string, 39 bytes is possible:

#&@@@#=={a,b}&&Equal@@Length/@#&@*Split

eg:

#&@@@#=={a,b}&&Equal@@Length/@#&@*Split@{a,b,a,b,a,b}

(*False*)
\$\endgroup\$
3
  • 1
    \$\begingroup\$ It's probably shortest with a recursive regex: #~StringMatchQ~RegularExpression@"(a(?1)?b)"& \$\endgroup\$ Jul 21, 2016 at 9:41
  • \$\begingroup\$ @MartinEnder Ah yes - much better - I'll delete & let you post that, since it doesn't resemble my awful attemp in the slightest! \$\endgroup\$
    – martin
    Jul 21, 2016 at 9:43
  • 2
    \$\begingroup\$ No, don't delete yours. A regex-less solution is still interesting. :) \$\endgroup\$ Jul 21, 2016 at 9:43
2
\$\begingroup\$

Racket, 91 bytes

(λ(x)((λ(y)(equal?(append(make-list(- 1 y)#\a)(make-list y #\b))(cdr x)))(/(length x)2)))

Expects input in the form of a list of characters. If you really need to put it in as a raw string, that adds 21 extra characters (for 112 bytes):

(λ(x)((λ(y)(equal?(append(make-list(- 1 y)#\a)(make-list y #\b))(cdr(string->list x))))(/(string-length x)2)))

An even longer (102 bytes with list input) way, but I think it's creative so I'm leaving it here:

(λ(x)(and(eqv?(/(length x)2)(length(member #\b x)))(eqv?(length(remove-duplicates(member #\b x)))1)))

Explanation to follow.

\$\endgroup\$
2
\$\begingroup\$

JavaScript, 34 bytes

s=>(s=s.match`^a(.*)b$`[1])?f(s):1

In true automata fashion, this function returns 1 if it's true, and fails if it's not.

f=s=>(s=s.match`^a(.*)b$`[1])?f(s):1

let test_strings = ["ab", "aabb", "", "a", "abb", "abc", "abab", "abba"];
test_strings.map(s => {
try {console.log("f(\"" + s + "\") returned " + f(s));}
catch(e) {console.log("f(\"" + s + "\") threw " + e);}
});

\$\endgroup\$
2
\$\begingroup\$

Excel, 55 bytes

=AND(A1<>"",A1=REPT("a",LEN(A1)/2)&REPT("b",LEN(A1)/2))

Test string in cell A1, formula above in any other cell. Generates a comparison string of the appropriate length and checks for a match. Shows TRUE or FALSE as appropriate.

\$\endgroup\$
2
\$\begingroup\$

PHP, 61 40 bytes

new approach inspired by Didz´ answer: regexp with a recursive pattern

<?=preg_match('#^(a(?1)?b)$#',$argv[1]);

P.S.: I see now that I am not the first one with this pattern. You never stop learning.


Josh´s C solution translated to PHP comes at the same size (with one byte lost in translation, one byte golfed for PHP with bitwise and, one byte golfed for C and PHP):

<?=strlen($s=$argv[1])==2*strspn($s,a)&$s[strrpos($s,a)+1]>a; (61 bytes)


My second own approach, a little longer: build a string with (input length / 2) of a, one of b and compare the concatenation to input:
<?=str_repeat(a,$n=strlen($s=$argv[1])/2).str_repeat(b,$n)==$s; (63 bytes)
Could save 3 bytes on that if I could use ($r=str_repeat) for a function call directly ... if.


all versions:

  • take the string as argument from cli
  • print 1 for true, nothing for false

testing

  • replace <?= with <?function f($s){return
  • remove =$argv[1] (or replace $argv[1] with $s)
  • append } and my test suite (below)
  • call in a web browser

function out($a){if(is_object($a)){foreach($a as$v)$r[]=$v;return'{'.implode(',',$r).'}';}if(!is_array($a))return$a;$r=[];foreach($a as$v)$r[]=out($v);return'['.join(',',$r).']';}
function test($x,$e,$y){static $h='<table border=1><tr><th>input</th><th>output</th><th>expected</th><th>ok?</th></tr>';echo"$h<tr><td>",out($x),'</td><td>',out($y),'</td><td>',out($e),'</td><td>',$e==$y?'Y':'N',"</td></tr>";$h='';}
$cases=[
    1=>[ab,aabb,aaabbb,aaaabbbb,aaaaabbbbb,aaaaaabbbbbb],
    0=>['',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]
];
foreach($cases as$e=>$a)foreach($a as$x)test($x,$e,f($x)|0);
\$\endgroup\$
2
\$\begingroup\$

Pyth, 7 bytes

.AanV_S

Try it online

How it works

      SQ     sorted input
     _       reverse
   nV   Q    vectorized not-equal with input
  a      Q   append input
.A           test whether all elements are truthy
\$\endgroup\$
2
\$\begingroup\$

C, 65 bytes

m,t;C(char*c){for(m=1,t=0;*c;)m>0&*c++-97&&(m-=2),t+=m;return!t;}
\$\endgroup\$
4
  • \$\begingroup\$ m---- doesn't compile. \$\endgroup\$
    – ugoren
    Jul 31, 2016 at 14:33
  • \$\begingroup\$ @ugoren what compiler are you using? \$\endgroup\$ Aug 8, 2016 at 9:31
  • \$\begingroup\$ gcc on Linux says error: invalid lvalue in decrement. Does any compiler compile this? \$\endgroup\$
    – ugoren
    Aug 8, 2016 at 14:56
  • \$\begingroup\$ Whoopsie, correct, nice catch @ugoren, I must have missed the error among the warnings. Reverted to the 65 byte solution. \$\endgroup\$ Aug 10, 2016 at 9:09
2
\$\begingroup\$

Brainfuck, 77 bytes

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

Expects input without a trailing newline. Outputs \x00 for false and \x01 for true.

Try it online.

The idea is to increment n for initial a characters and decrement n for subsequent b characters and then check whether n is zero at the end, short-circuiting to print false if the input does not match /^a+b+$/. Since the input is guaranteed to match /^[ab]*$/, we can ignore the fact that ord('a') = 97 and just use ord('b') = ord('a') + 1 to check for /^a+b/.

\$\endgroup\$
2
\$\begingroup\$

Cubically, 109 98 70 60 bytes

+52/1+55~=7!6&(:7UR'UF'D2~=7)6>7?6&(:7D2FU'RU'~=7)6>7!6&!8%6

-11 bytes thanks to TehPers

-10 bytes thanks to new language feature

Try it online!

Prints 1 if the string matches L, otherwise prints nothing.

Explanation:

+52/1+55            Sets the notepad to 97 ('a')
        ~           takes input
         =7!6&      exits if input is not 'a'

(             )6    While the notepad is truthy
 :7                 Save the current character value
   UR'UF'D2         Perform a cube operation
           ~=7      Set notepad to true if next character is the same

>7?6&               Exit if next character is end of input (-1)

(             )6    While the notepad is truthy
 :7                 Save the current character
   D2FU'RU'         Reverse one iteration of the previous operation
            ~=7     Set notepad to true if next character is the same

>7!6&               Exit if next character is NOT end of input
!8%6                Print 1 if the cube is solved

The looping operation has been replaced with a new sequence with a period of 1260, which will still never give a false negative but now is guaranteed to work for inputs of less than 1260 characters.

I've replaced the previous check for solved cube with !8%6. 8 is a recently added pseudo-face which is always equal to "Is the cube solved?" so I can just branch on that directly.

\$\endgroup\$
2
  • \$\begingroup\$ Why not do -6>7?6& instead of -6>7!6{...}? Also, couldn't you replace -6+111=3!6& with -6+21=3!6&, -6+1111=4!6& with -6+22=4!6&, and -6+11111=5!6& with -6+32=5!6&? You checked those faces earlier in the program. Also, you can replace -6=0!6& with -6>0?6& and remove the next -6 because 0 isn't greater than 0. Rather than =#!6&-6..., try =#0?6&.... I'm also pretty sure you can remove one or two of those checks, but I'm not a mathematician. I had a solution similar to this in mind, but I didn't think to compare the notepad to the previous value. Nice job! \$\endgroup\$
    – TehPers
    Aug 7, 2017 at 21:10
  • \$\begingroup\$ Also, you can remove the -6 in -6=0!6& because to exit the loop before it, the notepad must be 0. \$\endgroup\$
    – TehPers
    Aug 7, 2017 at 21:15
2
\$\begingroup\$

Ruby, 17 bytes (16 + '-n' flag)

p~/^(a\g<1>?b)$/

Try it online!

The recursive regex solution ported to ruby.

\$\endgroup\$
2
\$\begingroup\$

Nearly 5 months later, decided to come back to my first answer here to see if I could golf it more. Here's the results!

Zsh, 28 bytes

eval ${${${1:?}//a/( }//b/)}

Just as I posted my 29 byte answer, I thought "what about if we handle the empty case specially?" Turns out, it's one byte shorter! Try it online!

Successful cases: ( ( ( ... ( ( ))...))).

Unsuccessful cases:

  • Unmatched/uneven parens: obviously fails
  • /ba/ case: ( )( ) is a "parse error" in the eval, but gives unknown file attribute: if run directly.
  • Empty case: ${1:?} handles exactly this.

Zsh, 29 bytes

eval \(${${1//a/(+}//b/+i)}\)

Try it online!

Same "eval matching delimiters" principle, but this time using math mode instead of parameter expansions:

eval \(${${1//a/(+}//b/+i)}\)
     \(                    \)   # literal ( )
         ${1//a/(+}             # replace 'a' with '(+'
       ${          //b/+i)}     # replace 'b' with '+i)'

A successful result looks like: ((+(+(...+(++i)+...i)+i)+i)), incrementing i to 1 and adding it repeatedly. This will result in a positive integer, which (( )) evaluates truthy.

An unsuccessful result looks like one of the following:

  • Uneven/unmatched parens (obviously fails)
  • /^b(a{n}b{n})?a$/ case: (+i)(...)(+) fails with "missing identifier after +"
  • Any other /ba/ case: (...)(...) errors in math mode
  • Empty case: () is an anonymous function with no body, and errors

Original answer:

Zsh, 35 bytes

eval '${'${${1//a/'${'}//b/'}'}'#}'

Try it online! (More examples)

Inspired by xnor's post, this outputs via exit code. Zsh will happlily handle nested ${}s, but will err on ${${...}${...}} or unmatched braces. There are two caveats which makes this longer:

  • We need the outer ${...}, since ${}${} is valid zsh.
  • We need a # at then end, which causes an error when the input is the empty string:
    • ${${}#} is prefix removal, which is fine.
    • ${#} evaluates to the number of parameters, which will be an integer and not a valid command.
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Welcome to PPCG! Nice first answer \$\endgroup\$
    – Jo King
    Mar 21, 2019 at 3:23
2
\$\begingroup\$

Curry (PAKCS), 24 bytes

f('a':s++"b")=s==""||f s

Try it online!

Returns True for truth, and nothing otherwise.

\$\endgroup\$
2
\$\begingroup\$

Python 2, 43 40 Bytes

lambda s:''<s==len(s)/2*"a"+len(s)/2*"b"

Try it online! - considered the obvious solution thanks to Leaky Nun

other idea, 45 bytes:

lambda s:s and list(s)==sorted(len(s)/2*"ab")

Try it online!

-4 bytes by using len/2 (i get an error when the half comes last)

now gives false for the empty string

-3 bytes thanks to xnor

\$\endgroup\$
11
  • \$\begingroup\$ Yes, lambdas don't have to be named. \$\endgroup\$
    – Leaky Nun
    Jul 20, 2016 at 19:51
  • \$\begingroup\$ lambda s:list(s)==sorted("ab"*len(s)//2) (Python 3) \$\endgroup\$
    – Leaky Nun
    Jul 20, 2016 at 19:52
  • \$\begingroup\$ lambda s:s=="a"*len(s)//2+"b"*len(s)//2 (Python 3) \$\endgroup\$
    – Leaky Nun
    Jul 20, 2016 at 19:52
  • \$\begingroup\$ yeah, I realized that while posting it. lol, the obvious solution is shorter in Python 2: \$\endgroup\$
    – KarlKastor
    Jul 20, 2016 at 19:57
  • 1
    \$\begingroup\$ You can do ''< instead of s and to rule out the empty case. \$\endgroup\$
    – xnor
    Jul 20, 2016 at 22:54
2
\$\begingroup\$

Thunno 2, 10 bytes

Ṡ=s`abdcạ&

Attempt This Online!

Explanation

Ṡ=s`abdcạ&  # Implicit input
Ṡ=          # Is the input sorted?
  s         # Swap so the input is back on top
   `ab      # Push the string "ab"
      dc    # Count the occurrences of "a" and "b"
        ạ   # Are they equal to each other?
         &  # Logical AND
            # Implicit output
\$\endgroup\$
1
\$\begingroup\$

Pyke, 10 bytes

le"ab"*Sq&

Try it here!

Or 9 bytes if null input isn't valid

le"ab"*Sq
\$\endgroup\$
1
\$\begingroup\$

Ruby, 33 bytes

Try it online

->s{s==?a*(l=s.size/2)+?b*l&&l>0}
\$\endgroup\$
1
\$\begingroup\$

Actually, 14 bytes

"[]""ab"(t≡#ÆY

This uses the same strategy as xnor's solution for the first part: transform the input into a nested iterable.

Try it online!

Explanation:

"[]""ab"(t≡#ÆY
"[]""ab"(t      translate "a" -> "[", "b" -> "]"
          ≡     eval (since this is evaluating a literal, it still works in the online interpreter) - leaves a list if the string is valid, else a string
           #    listify (does nothing to a list, makes a list of characters for a string)
            Æ   filter strings (take all string elements in the list - so an empty list if there are none)
             Y  boolean negate (an empty list is falsey and a non-empty list is truthy, so negation gets the correct value)
\$\endgroup\$
1
\$\begingroup\$

Ruby, 31 bytes

Aw, that poor syntax highlighter :)

->s{s=~/^a+/&&$&.tr(?a,?b)==$'}

Does s begin with one or more a? Is also that bunch of as ($&) the same as the rest of the string ($') if we replace all those as with bs?

test here

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

C#, 78 67 bytes

bool f(string s)=>Regex.IsMatch(s,"^(?'o'a)+(?'-o'b)+(?(o)(?!))$");

This implementation uses .NET Regex's "Balancing Group Definitions" to match the same number of 'a' and 'b' characters while ensuring that the input isn't an empty string by using the + quantifier.

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

Python, 101 bytes

def q(s):  
 a=len(s)/2  
 for x in range(a):  
  if s[x]!='a' or s[a+x]!='b' or a*2!=len(s):a=0
return a

Not the most efficient, had some trouble with 0 being even. Could probably get it lower with python tricks.
Returns 0 if false, a positive integer if true. (which will be half len(s))

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

k (21 bytes)

Can probably be shorter

{|/0,(=).(#:'=x)"ab"}

Example

k){|/0,(=).(#:'=x)"ab"}""
0b
k){|/0,(=).(#:'=x)"ab"}"ab"
1b
k){|/0,(=).(#:'=x)"ab"}"aab"
0b
\$\endgroup\$
1
  • \$\begingroup\$ Gives the wrong answer for "abba" \$\endgroup\$
    – geocar
    Jul 31, 2016 at 13:02
1
\$\begingroup\$

PHP bounty version, 31 bytes

for PHP 4.1, call php-cgi -f <scriptname> s=<argument> (or in browser with ?s=<argument>)

for current PHP, use $_GET[s] instead of $s


31 bytes

<?eval(strtr("do$s;",ab,'{}'));

unexpected ';' for valid, unexpected end of file or unexpected '}' for invalid

<?eval(strtr("1|$s;",ab,'[]'));

ok for valid, unexpected ';' or unexpected ']' for invalid

26 bytes

if empty input was undefined or valid:

<?eval(strtr($s,ab,'{}'));

29 bytes, if empty input was undefined or valid:

<?eval(strtr("$s;",ab,'[]'));

Abusing other control structures:

32 bytes

<?eval(strtr("$c=$s;",ab,'[]'));

ok for valid, Parse error for invalid: unexpected ';', unexpected ']' or Cannot use [] for reading (for abab)

33 bytes

<?eval(strtr("1 or$s;",ab,'[]'));

same as 1|

<?eval(strtr("if(0)$s",ab,'{}'));

ok for valid, unexpected end of file or unexpected '}' for invalid input

35 bytes:

<?eval(strtr("for(;;)$s",ab,'{}'));

infinite loop for valid (use for(;0;) to make finite), same as if for invalid

36 bytes

<?eval(strtr("while(0)$s",ab,'{}'));

same as if

39 bytes

<?eval(strtr("function()$s;",ab,'{}'));

unexpected ';' for empty, same as if for other input

\$\endgroup\$

Your Answer

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