[math-fun] Combinatorics of shell substitution
I posted the below puzzle to Twitter, where no one has solved it. I think it’s too hard. Although it’s a silly question, the method of solution is quite interesting IMHO. (The computation would be doable by hand, if one were patient and careful, but can be done more easily and reliably by a computer.) I know some of you are aware of a related problem I solved a few years ago. The method of solution of this one is related, but not identical. Cheers, Robin A Unix shell puzzle. If you were to run this script – which I don’t recommend doing – how many occurrences of $x would appear in the output? x=\"\'\$x\'\"\$x\'\"\$x\"\' eval x=$x eval x=$x eval x=$x eval x=$x eval x=$x eval x=$x eval x=$x eval x=$x eval x=$x eval x=$x echo "$x"
robin - which unix shell? sh, bash, ksh, csh tcsh, zsh, lotsa choices - i do know that sh barfs on it more later, chris On Tue, Aug 25, 2020 at 8:01 AM Robin Houston <robin.houston@gmail.com> wrote:
I posted the below puzzle to Twitter, where no one has solved it. I think it’s too hard. Although it’s a silly question, the method of solution is quite interesting IMHO.
(The computation would be doable by hand, if one were patient and careful, but can be done more easily and reliably by a computer.)
I know some of you are aware of a related problem I solved a few years ago. The method of solution of this one is related, but not identical.
Cheers, Robin
A Unix shell puzzle. If you were to run this script – which I don’t recommend doing – how many occurrences of $x would appear in the output?
x=\"\'\$x\'\"\$x\'\"\$x\"\' eval x=$x eval x=$x eval x=$x eval x=$x eval x=$x eval x=$x eval x=$x eval x=$x eval x=$x eval x=$x echo "$x" _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- dr. christopher landauer topcy house consulting thousand oaks, california
Sorry, I should have explicitly specified a Bourne-type shell. I’ve tried it with bash, dash and zsh, all of which behave the same AFAICT. The sequence should begin: 3, 7, 37, 973, 642493; which is probably as far as you can get experimentally. Cheers, Robin On Tue, 25 Aug 2020 at 16:44, Christopher Landauer <topcycal@gmail.com> wrote:
robin - which unix shell? sh, bash, ksh, csh tcsh, zsh, lotsa choices - i do know that sh barfs on it more later, chris
On Tue, Aug 25, 2020 at 8:01 AM Robin Houston <robin.houston@gmail.com> wrote:
I posted the below puzzle to Twitter, where no one has solved it. I think it’s too hard. Although it’s a silly question, the method of solution is quite interesting IMHO.
(The computation would be doable by hand, if one were patient and careful, but can be done more easily and reliably by a computer.)
I know some of you are aware of a related problem I solved a few years ago. The method of solution of this one is related, but not identical.
Cheers, Robin
A Unix shell puzzle. If you were to run this script – which I don’t recommend doing – how many occurrences of $x would appear in the output?
x=\"\'\$x\'\"\$x\'\"\$x\"\' eval x=$x eval x=$x eval x=$x eval x=$x eval x=$x eval x=$x eval x=$x eval x=$x eval x=$x eval x=$x echo "$x" _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- dr. christopher landauer topcy house consulting thousand oaks, california _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
For those who are interested in the combinatorics half of this puzzle, but not in the figure-out-how-the-unix-shell-works part, here is a spoiler for the first half, presenting this as a problem about substitution operations on strings without reference to UNIX. Consider the following partial-function f operating on (some) pairs of strings and returning a string: (the double quotes and plus sign here are metanotation, and not part of the string; I've used d and s instead of single and double quotes to avoid confusion). f("$x", x) = x f("dSd", y) = f(S, y) , where S is any string not containing a d.\ f("sSs", y) = S, where S is any string not containing an s f(A+B, x) = f(A, x) + f(B, x), where + denotes concatenation. Or in words, substitute the value of the variable x for the string $x. Quoted strings, whether single or double quoted, are copied, with the quotes removed, but variable substitution occurs in single quotes, but not in double quotes. Single quotes inside double quotes, and vice versa, are not nested applications of this rule: they are simply copied like any other character. Now define g(x) = f(x, x) The question is how many occurences of "$x" there are in g^7("ds$xsd $x sd$xds") where I've inserted some spaces for readability, so I suppose I need to add the rule f(" ", y) = " " I'm pretty sure this is the right translation of the puzzle from the language of the unix shell to the language of math, since I've verified that g^3("ds$xsd $x sd$xds") = 973. So I think I've solved the unix-shell part of the puzzle correctly, but haven't yet a clue how to solve the mathematica part. On Tue, Aug 25, 2020 at 11:54 AM Robin Houston <robin.houston@gmail.com> wrote:
Sorry, I should have explicitly specified a Bourne-type shell.
I’ve tried it with bash, dash and zsh, all of which behave the same AFAICT.
The sequence should begin: 3, 7, 37, 973, 642493; which is probably as far as you can get experimentally.
Cheers, Robin
On Tue, 25 Aug 2020 at 16:44, Christopher Landauer <topcycal@gmail.com> wrote:
robin - which unix shell? sh, bash, ksh, csh tcsh, zsh, lotsa choices - i do know that sh barfs on it more later, chris
On Tue, Aug 25, 2020 at 8:01 AM Robin Houston <robin.houston@gmail.com> wrote:
I posted the below puzzle to Twitter, where no one has solved it. I think it’s too hard. Although it’s a silly question, the method of solution is quite interesting IMHO.
(The computation would be doable by hand, if one were patient and careful, but can be done more easily and reliably by a computer.)
I know some of you are aware of a related problem I solved a few years ago. The method of solution of this one is related, but not identical.
Cheers, Robin
A Unix shell puzzle. If you were to run this script – which I don’t recommend doing – how many occurrences of $x would appear in the output?
x=\"\'\$x\'\"\$x\'\"\$x\"\' eval x=$x eval x=$x eval x=$x eval x=$x eval x=$x eval x=$x eval x=$x eval x=$x eval x=$x eval x=$x echo "$x" _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- dr. christopher landauer topcy house consulting thousand oaks, california _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
I get 328...881 with some various digits between the 328 and the 881.
On Tue, Aug 25, 2020 at 11:11 AM Andy Latto <andy.latto@pobox.com> wrote:
> For those who are interested in the combinatorics half of this puzzle, but
> not in the figure-out-how-the-unix-shell-works part, here is a spoiler for
> the first half, presenting this as a problem about substitution operations
> on strings without reference to UNIX.
>
> Consider the following partial-function f operating on (some) pairs of
> strings and returning a string: (the double quotes and plus sign here are
> metanotation, and not part of the string; I've used d and s instead of
> single and double quotes to avoid confusion).
>
> f("$x", x) = x
> f("dSd", y) = f(S, y) , where S is any string not containing a d.\
> f("sSs", y) = S, where S is any string not containing an s
> f(A+B, x) = f(A, x) + f(B, x), where + denotes concatenation.
>
> Or in words, substitute the value of the variable x for the string $x.
> Quoted strings, whether single or double quoted, are copied, with the
> quotes removed, but variable substitution occurs in single quotes, but not
> in double quotes. Single quotes inside double quotes, and vice versa, are
> not nested applications of this rule: they are simply copied like any other
> character.
>
> Now define
>
> g(x) = f(x, x)
>
> The question is how many occurences of "$x" there are in g^7("ds$xsd $x
> sd$xds")
>
> where I've inserted some spaces for readability, so I suppose I need to add
> the rule
> f(" ", y) = " "
>
> I'm pretty sure this is the right translation of the puzzle from the
> language of the unix shell to the language of math, since I've verified
> that g^3("ds$xsd $x sd$xds") = 973. So I think I've solved the unix-shell
> part of the puzzle correctly, but haven't yet a clue how to solve the
> mathematica part.
>
>
>
> On Tue, Aug 25, 2020 at 11:54 AM Robin Houston <robin.houston@gmail.com>
> wrote:
>
> > Sorry, I should have explicitly specified a Bourne-type shell.
> >
> > I’ve tried it with bash, dash and zsh, all of which behave the same
> AFAICT.
> >
> > The sequence should begin: 3, 7, 37, 973, 642493; which is probably as
> far
> > as you can get experimentally.
> >
> > Cheers,
> > Robin
> >
> > On Tue, 25 Aug 2020 at 16:44, Christopher Landauer <topcycal@gmail.com>
> > wrote:
> >
> > > robin - which unix shell? sh, bash, ksh, csh tcsh, zsh, lotsa choices
> - i
> > > do know that sh barfs on it
> > > more later,
> > > chris
> > >
> > >
> > > On Tue, Aug 25, 2020 at 8:01 AM Robin Houston <robin.houston@gmail.com
> >
> > > wrote:
> > >
> > > > I posted the below puzzle to Twitter, where no one has solved it. I
> > think
> > > > it’s too hard. Although it’s a silly question, the method of solution
> > is
> > > > quite interesting IMHO.
> > > >
> > > > (The computation would be doable by hand, if one were patient and
> > > careful,
> > > > but can be done more easily and reliably by a computer.)
> > > >
> > > > I know some of you are aware of a related problem I solved a few
> years
> > > ago.
> > > > The method of solution of this one is related, but not identical.
> > > >
> > > > Cheers,
> > > > Robin
> > > >
> > > >
> > > > A Unix shell puzzle. If you were to run this script – which I don’t
> > > > recommend doing – how many occurrences of $x would appear in the
> > output?
> > > >
> > > > x=\"\'\$x\'\"\$x\'\"\$x\"\'
> > > > eval x=$x
> > > > eval x=$x
> > > > eval x=$x
> > > > eval x=$x
> > > > eval x=$x
> > > > eval x=$x
> > > > eval x=$x
> > > > eval x=$x
> > > > eval x=$x
> > > > eval x=$x
> > > > echo "$x"
> > > > _______________________________________________
> > > > math-fun mailing list
> > > > math-fun@mailman.xmission.com
> > > > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
> > > >
> > >
> > >
> > > --
> > > dr. christopher landauer
> > > topcy house consulting
> > > thousand oaks, california
> > > _______________________________________________
> > > math-fun mailing list
> > > math-fun@mailman.xmission.com
> > > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
> > >
> > _______________________________________________
> > math-fun mailing list
> > math-fun@mailman.xmission.com
> > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
> >
>
>
> --
> Andy.Latto@pobox.com
> _______________________________________________
> math-fun mailing list
> math-fun@mailman.xmission.com
> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
>
--
-- http://cube20.org/ -- http://golly.sf.net/ --
participants (4)
-
Andy Latto -
Christopher Landauer -
Robin Houston -
Tomas Rokicki