10
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ 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. \$\endgroup\$
    – N. Virgo
    Commented Mar 18, 2018 at 7:14
  • \$\begingroup\$ No worries, I have refunded the bounty. \$\endgroup\$
    – DJMcMayhem
    Commented Mar 18, 2018 at 15:25
  • \$\begingroup\$ @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. \$\endgroup\$ Commented Mar 18, 2018 at 19:37

6 Answers 6

18
\$\begingroup\$

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!

\$\endgroup\$
9
  • \$\begingroup\$ Is it stated anywhere or is it by default that inverse apply is allowed? \$\endgroup\$ Commented Mar 4, 2018 at 1:48
  • 2
    \$\begingroup\$ @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. \$\endgroup\$
    – hyperneutrino
    Commented Mar 4, 2018 at 1:49
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Mar 4, 2018 at 1:53
  • 2
    \$\begingroup\$ @HyperNeutrino ^^ \$\endgroup\$ Commented Mar 4, 2018 at 2:02
  • 1
    \$\begingroup\$ Which program did you use to factorize this and how long did it take? \$\endgroup\$
    – user202729
    Commented Mar 4, 2018 at 9:47
10
+300
\$\begingroup\$

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.

\$\endgroup\$
9
\$\begingroup\$

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.

\$\endgroup\$
6
\$\begingroup\$

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.

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

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.

\$\endgroup\$
3
  • \$\begingroup\$ Ooch, that hurts. There is another solution though... \$\endgroup\$
    – Xetrov
    Commented Mar 7, 2018 at 17:10
  • \$\begingroup\$ @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 \$\endgroup\$
    – hyperneutrino
    Commented Mar 7, 2018 at 17:15
  • \$\begingroup\$ 2x easier to be exact \$\endgroup\$
    – Xetrov
    Commented Mar 8, 2018 at 1:30
1
\$\begingroup\$

The Empty String Photographer

The target string cannot be reached because there is no right-to-left override in the rules. That's even easier than the effort I put into formatting the original answer. Very unfunny. :p

\$\endgroup\$
3
  • \$\begingroup\$ @TheEmptyStringPhotographer how is it wrong? \$\endgroup\$
    – lyxal
    Commented Nov 30, 2023 at 11:55
  • \$\begingroup\$ still not seeing it \$\endgroup\$
    – lyxal
    Commented Nov 30, 2023 at 11:56
  • \$\begingroup\$ @TheEmptyStringPhotographer > please don't use whitespace, or symbols that are hard to distinguish from each other \$\endgroup\$
    – lyxal
    Commented Nov 30, 2023 at 12:01

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.