6
\$\begingroup\$

In this challenge you will receive a list of positive integers \$W\$ called a word, and a square symmetric matrix \$M\$. Your task is to determine if the word can be turned into the empty list by applying a series of valid moves.

The valid moves are:

  1. If two consecutive values in the list are equal you may remove them from the list. e.g. [2,6,6,2,1] to [2,2,1]
  2. For any positive integer \$n\$ you may insert two \$n\$s at any place in the list. e.g. [1,2,3] to [1,3,3,2,3]
  3. For two positive integers \$i\$ and \$j\$, if \$M_{i,j} = l\$ (i.e. the value of \$M\$ at the \$i\$th row and \$j\$th column) and there is a contiguous substring of length \$l\$ alternating between \$i\$ and \$j\$, you may replace all the \$i\$s with \$j\$s and vice versa within that substring. e.g. [1,2,1,2] to [2,1,2,2] if and only if \$M_{i,j} = 3\$

Values in the matrix will be on the range \$[2,\infty]\$. ∞ of course represents that there is no valid application of rule 3 for that pair. you may use 0 or -1 in place of ∞.

In addition the input will always satisfy the following properties:

  • \$M\$ will always be square.
  • \$M\$ will always be a symmetric matrix.
  • The diagonal of \$M\$ will always be entirely 2.
  • The maximum value of \$W\$ will not exceed the number of rows/columns of \$M\$

You should take \$M\$ and \$W\$ in any reasonable format, you should output one of two distinct values if the word can be reduced to the empty word and the other value if not.

Use zero indexing for your word if you wish.

This is . The goal is to minimize the size of your source code as measured in bytes.

Worked examples

Here are some examples with working for the solution. You do not have to output any working just the end result.

  1. \$W\$ = [3,2,3,3,1,2,3] any value of \$M\$: Each rule changes the number of symbols by a multiple of 2, however \$W\$ has an odd number of symbols, therefor by parity we can never reach the empty word so this case is False

  2. \$W\$ = [1,3], \$M_{1,3}\$ is even: Similar to the last case we observe that both 1 and 3 appear an odd number of times. Each rule can only change the count of 1s and 3s by an even amount, but in our desired end state we have 0 of each, an even amount. Therefor by parity we can never reach this case is False

  3. \$W\$ = [1,3], any value of \$M\$: In this case we consider 4 values:

    • \$a_1\$, the number of 1s at even indexes
    • \$b_1\$, the number of 1s at odd indexes
    • \$a_3\$, the number of 3s at even indexes
    • \$b_3\$, the number of 3s at odd indexes

    We note that rules 1 and 2 do not change the values of \$a_n-b_n\$. Rule 3 changes both them by the value of \$M_{1,3}\$. Since each begins at 1 and the goal is 0 it would require \$M_{1,3}\$ to equal 1. This is forbidden, so this case is False.

  4. \$W\$ = [2,1,3,2], any value of \$M\$: This is a conjugate of [1,3], which by 3. we know is irreducible. Conjugates always have the same order, thus its order must be greater than 1. False

  5. \$W\$ = [1,2,1,2], \$M_{1,2} = 3\$: We can apply rule 3 to the last 3 symbols of the word get [1,1,2,1], from here we can apply rule 1 to get [2,1]. We can use the argument in 3 to show [2,1] is irreducible thus \$W\$ is irreducible. False

  6. \$W\$ = [1,4,1,4], \$M_{1,4}\$ = 2:

    [1,4,1,4]

    [4,1,1,4] (rule 3)

    [4,4] (rule 1)

    [] (rule 1)

    True

\$\endgroup\$
18
  • \$\begingroup\$ This is a Coxeter system, right? \$\endgroup\$ Commented Dec 11, 2023 at 5:58
  • \$\begingroup\$ Can I return a truthy/falsey value, or can there only be two options? \$\endgroup\$ Commented Dec 11, 2023 at 7:47
  • \$\begingroup\$ Can I take, say, |1||4||1||4| (as a string), for [1,4,1,4]? Also, can I have the matrix (and accordingly the generators) be 0-indexed? \$\endgroup\$ Commented Dec 11, 2023 at 7:50
  • \$\begingroup\$ Can I take the matrix as a set of triplets, with (i, j, a) meaning \$M_{ij} = a\$? If yes, do I have to include triplets with infinity in this or can I assume those just aren't in the input? \$\endgroup\$ Commented Dec 11, 2023 at 7:57
  • \$\begingroup\$ @CommandMaster I don't know how the matrix can be 0 indexed, the values it holds are not indexes as I see it. What do you mean? \$\endgroup\$
    – Wheat Wizard
    Commented Dec 11, 2023 at 18:29

0

Your Answer

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