Abstract Rewriting Challenge (Robbers)

9

This is a somewhat -like challenge. This is the robbers' thread; the cops' thread is here.

Robbers

The cops will post abstract rewriting systems. Your task is to crack their submissions by proving that the target string either can or can not be reached from the source string by applying their rewrite rules. (You can do this either by posting a sequence of rewrite rules that starts with the source string and ends with the target, or by proving mathematically that this does, or does not, exist.)

See the cops' thread for details and definitions.

Nathaniel

Posted 2018-03-03T00:03:46.263

Reputation: 6 641

Do'h! I put a bounty on the wrong question, this was meant to be on the cops' challenge. So somebody will get a random bounty. – Nathaniel – 2018-03-18T07:14:56.957

No worries, I have refunded the bounty. – James – 2018-03-18T15:25:50.093

@DJMcMayhem: Huh... so that's why the SE API is listing this question as featured, but with no bounty amount or closing date. :o Oh well, time to add some input validation to my user script.

– Ilmari Karonen – 2018-03-18T19:37:12.383

Answers

16

jimmy23013

Let's work backwards for this one. We first turn the digits into their binary representations. We go from VW626206555675126212043640270477001760465526277571600601 to VW++__+_++__+____++_+_++_++_+++_++++_+__+_+_++__+___+_+____+___++++_+______+_+++___+__++++++________++++++____+__++_+_++_+_+_++__+_+++++++_++++__+++_______++______+. Next, we keep applying the inverse of DCW:W+ and DW:W_ until we clear all symbols. Our result is now VDCDCDDDCDDCDCDDDCDDDDDCDCDDCDDCDCDDCDCDDCDCDCDDCDCDCDCDDCDDDCDDCDDCDCDDDCDDDDCDDCDDDDDCDDDDCDCDCDCDDCDDDDDDDCDDCDCDCDDDDCDDDCDCDCDCDCDCDDDDDDDDDCDCDCDCDCDCDDDDDCDDDCDCDDCDDCDCDDCDDCDDCDCDDDCDDCDCDCDCDCDCDCDDCDCDCDCDDDCDCDCDDDDDDDDCDCDDDDDDDCW. We now want to make this string match VD+C+W; that is, we want to move all of the Ds to the left of all of the Cs. This can be done by reversing DCC:CD. We do this by repeating the following algorithm:

  1. Find the first D that is to the right of a block of Cs.
  2. Move the D to the left of that block.
  3. Double the number of Cs.

Through some math, we can determine that we will end up with 123 Ds and 4638704741628490670592103344196019722536654143873 Cs (you were right about this not fitting in an SE answer... I doubt this would fit if stored as states of all of the atoms in the Earth combined :P).

If we keep applying the reverse of V:VD, we can get rid of all of the Ds now, so we get VCCC.......CCCW. We convert the V back into YZ. Now we have YZCCC.......CCCW.

We want to be able to get rid of all of the Cs and have it in the form YAAA...AAABBB...BBBZW. Fortunately, this can be done by the following method. Firstly, we inverse-apply YB:Y 587912508217580921743211 times to get YBBB.......BBBZCCC.......CCCW. Then, we repeat the following sequence of steps (where [?*] means any number of ?, not necessarily greater than zero):

  1. Inverse-apply CZ:ZC 587912508217580921743211 times to get Y[A*]BBB.......BBBCCC.......CCCZCCC.......CCCW
  2. Inverse-apply CB:BC many times to get Y[A*]BCBCBC.......BCBCBCZCCC.......CCCW
  3. Inverse-apply AZ:Z and AB:BCA many times to get Y[A*]ABBB.......BBBZCCC.......CCCW

Through induction, we see that we can move the BZ combination all the way to the end (except before the W) and then the number of As is 1/587912508217580921743211 of the number of Cs, leaving us with 7890127658096618386747843 As. We now have YAAA.......AAABBB.......BBBZW. Convert the ZW back to a U, then inverse-apply U:BU many times to keep only 2 Bs and then convert the BBU to a T, and you now have YAAA.......AAAT. Then, you can inverse-apply T:AAAAAT many times to get YAAAT because the number of As was 3 larger than a multiple of 5.

Thanks for the challenge!

HyperNeutrino

Posted 2018-03-03T00:03:46.263

Reputation: 26 575

Is it stated anywhere or is it by default that inverse apply is allowed? – Weijun Zhou – 2018-03-04T01:48:02.490

2@WeijunZhou I mean, if applying A:B to ABC gives BBC, it's obvious that applying the inverse of A:B to BBC can give ABC. It's not specifically stated that it's allowed, but I can easily just reverse my steps and have a "conventional" solution, it's just that it's easier to go backwards IMO. – HyperNeutrino – 2018-03-04T01:49:49.550

I mean ,for example, if there is only one rule A:B and it is not stated that inverse apply is allowed then I don't think you can go from BBC to ABC. This specific case may be different and there are some way to go in the other direction. I will check it later. – Weijun Zhou – 2018-03-04T01:53:37.647

@WeijunZhou he's not going from BBC to ABC, he's saying that if the current string is BBC then a possible previous string is ABC. – Nathaniel – 2018-03-04T02:00:30.150

@WeijunZhou I'm not applying the inverse as a forward step, I'm entirely working backwards. If I reverse everything (all steps and make inverse-apply into a forward application) it will look more like a conventional solution. – HyperNeutrino – 2018-03-04T02:01:43.230

@Nathaniel I see. Thank you for your clarification. – Weijun Zhou – 2018-03-04T02:01:50.817

2@HyperNeutrino ^^ – Weijun Zhou – 2018-03-04T02:02:23.553

1Which program did you use to factorize this and how long did it take? – user202729 – 2018-03-04T09:47:10.533

@user202729 wolfram alpha :D – HyperNeutrino – 2018-03-04T17:12:55.157

9

boboquack

For a given string, take all the letters (a = 0, b = 1, c = 2), sum them up and take the modulo 3. Then none of the rewrite rules change that value. The source string has a value of 1, and the target has a value of 2. Therefore, no combination of rules will transform the source string to the target string.

bb94

Posted 2018-03-03T00:03:46.263

Reputation: 1 831

9

feersum

This is a sokoban puzzle. The starting position is:

          ___#
#___####_____#
#_#_#_##_#_!##
##______##_###
##__####_#_###
###__###__

The ending position is:

          ___#
#___####_____#
#_#_#_##_#_###
##____!__#_###
##__####_#_###
###__###__

It can be solved using the following key sequence:

←←→↓↓←↑←←←←←←↓↓→↑←↑↑↑←←↓→↑→↓↓→→→→→→↓→↑↑↓↓←↓←↑→↑←←←←↑←←↓→→→→→↓→→↑↑→↑↑←↓←←↓↓→↑←↑→→↑→→↓←↓←←↓↓→↑←←←←←←←↑↑←←↓→→↓→↓↓←↑←↑→↑↑←←↓→↑→↓↓←↓→↑→→→→→→↓↓←↑→↑←←←←←←→→→→→→↑↑←↓→↓←↑↑→→↑→→↓←↓←→↑↑←↓←↓↑→→↓←↑←←↓↓↓→→↑↑↓↓←←↑↑→↓↑↑→↑→→↓←↓←↓←←↑↑→→↑→↓←↓↓←←←←←↑←←↓→→→→→←←←←←↑↑←←↓→→↓↓←↑→→→→

Here is a bash program that converts the key sequence to sed commands and applies them. The sed commands contains only replacing commands using the rewrite rules defined in the cop's answer, and labelling and branching commands that doesn't modify the string. It confirms that you can get the target string using only the rewrite rules.

s="___##___####_____##_#_#_##_#_!####______##_#####__####_#_######__###__"
input=

while
    printf '\n%80s\n' "$s"|fold -w14
    read -n 1
    [ "$REPLY" = $'\e' ]
do
    read -n 2
    case "$REPLY" in
    [A)
        s="$(sed '
s:!:wLW_:
        :a
s:L:<<<<<<<<<<<<<:
s:#w<:w#:
s:_w<:w_:
s:_<:<_:
s:#<:<#:
s:#wW:wLX!:
s:_W:W_:
s:#W:W#:
s:_wW:!:
s:_X:X_:
s:#X:X#:
s:_wX:#:
        ta' <<<"$s")";;
    [B)
        s="$(sed '
s:!:_VRv:
        :a
s:R:>>>>>>>>>>>>>:
s:>v#:#v:
s:>v_:_v:
s:>_:_>:
s:>#:#>:
s:Vv#:!URv:
s:U_:_U:
s:U#:#U:
s:Uv_:#:
s:V_:_V:
s:V#:#V:
s:Vv_:!:
        ta' <<<"$s")";;
    [C)
        s="$(sed '
s:!#_:_!#:
        te
s:!_:_!:
        :e' <<<"$s")";;
    [D)
        s="$(sed '
s:_#!:#!_:
        te
s:_!:!_:
        :e' <<<"$s")";;
    esac
    input="$input${REPLY:1}"
done

echo "$input"

Try it online!

Try it online (with escape code removed)!

For up and down, !:wLW_ or !:_VRv is applied for once correspondingly, and the relevant rules are applied repeatedly until the ! appeared again. For right, one of !#_:_!# and !_:_! is applied. For left, one of _#!:#!_ and _!:!_ is applied.

See the output in the links for the position after each move.

jimmy23013

Posted 2018-03-03T00:03:46.263

Reputation: 34 042

6

xnor

Rule 1 x:xn Rule 2 no:oon Rule 3 nr:r Rule 4 ooooooooooo:

We use [X,Y] to indicate a run of Y Xs

Starting from xn[o,A]r,

  1. Applying Rule 2 once we have x[o,2]n[o,A-1]r.
  2. Applying Rule 2 once more we have x[o,4]n[o,A-2]r
  3. Applying until the os between n and r becomes 0, we have x[o,2*A]nr.
  4. Applying Rule 3 once we have x[o,2*A]r.
  5. Applying Rule 1 once we have xn[o,2*A]r.

So, we have an algorithm to generate from xn[o,A]r to xn[o,2*A]r.

Starting from xnor = xn[o,1]r, repeating 10 times the algorithm -- except in the 10th loop we stop at Step 4, having x[o,1024]r.

Applying Rule 4, this clears 1023 = 11 * 93 os, leaving xor.

Shieru Asakoto

Posted 2018-03-03T00:03:46.263

Reputation: 4 445

2

VortexYT

There is no way of eliminating Fs without creating/using other characters; thus, we must use I:F as the last step to get to the target. No rule gives a single I without other unwanted characters thus you can't get to the target string.

Equivalently, if you try to map backwards from the source, you can only get from F to I before you have no more options.

HyperNeutrino

Posted 2018-03-03T00:03:46.263

Reputation: 26 575

Ooch, that hurts. There is another solution though... – VortexYT – 2018-03-07T17:10:14.557

@VortexYT oh really, there is? hm, did not know. but yeah the target can't map back more than one step which probably made this a ton easier than you intended :P – HyperNeutrino – 2018-03-07T17:15:06.277

2x easier to be exact – VortexYT – 2018-03-08T01:30:43.933