9
\$\begingroup\$

Alternatively: That one challenge I forgot I had in the sandbox and is about stuff from Discrete Mathematics I learned like 5-6 months ago and kinda don't remember

Given a path of vertices that form a cycle on a graph, output a simple version of the cycle. That is, if a vertex appears twice, snip out the part in between the two appearances.

Context

Let \$u\$ and \$v\$ be vertices of graph \$G\$. If there is a cycle from \$u\$ to \$v\$ of length \$n\$, then there exists a simple cycle from \$u\$ to \$v\$ with length \$\le n\$.

This is because any cycle \$v_1, e_1, v_2, e_2, ..., e_m, v_m\$ with a vertex visited twice (that is, \$v_i = v_j\$ for some \$v_i\$ and \$v_j\$ in \$G\$, where \$ i < j\$), can be reduced to \$v_1, e_1, ..., e_i, v_j, e_{j+1}\$ and still be a valid cycle between \$u\$ and \$v\$.

For the sake of this challenge, the edges connecting vertices will be ignored, as the edge taken when going between vertices will be assumed arbitrary.

Worked Example

Take the graph \$K_5\$:

enter image description here

One cycle between vertices \$1\$ and \$3\$ might look like:

enter image description here

That is, the path taken is [1, 2, 5, 4, 2, 3, 5]. However, that cycle can be simplified to:

enter image description here

Which has path [1, 2, 3, 5]. This cycle is a simple cycle, as only the first and last vertices are equal.

Note that cycles are snipped in the order they come.

Rules

  • There will always be a simpler cycle in the input.

  • The input will be a list of vertices in a graph. Whether you take those as numbers, characters or some other way is up to you.

  • There will always be at least 2 vertices.

  • Each vertex has degree >= 2.

  • Input and output can be given in any reasonable and convenient format.

  • As the input represents a cycle, the vertex that is the start and end of the cycle will not be in the input.

  • There won't be multiple overlapping simplified paths in the input.

  • There'll be one and only one output for each input.

Note that the simple cycle may not be the shortest cycle, and the shortest cycle may not be the simple cycle.

Test Cases

Assuming that numbers are used as vertex labels

[1,2,3,4,2,5] -> [1,2,5]
[4,3,6,2,3,8,5,2,8,7] -> [4,3,8,7]
[1,1,2] -> [1,2]
[1,2,7,2,7,2,3,7] -> [1,2,3,7]

This is code golf, so make sure you simplify the byte count of your answers.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ Are the test cases unique? I might've misunderstood the problem, but wouldn't [1, 2, 7] be a valid answer as well for [1,2,7,2,7,2,3,7], if you choose to snip the 7 first? \$\endgroup\$ Commented Jan 20, 2023 at 12:50
  • \$\begingroup\$ To expand on @CommandMaster 's comment, what's the expected output for [1,2,1,3,4,5,6,2]? It seems like the shortest cycle is [1,2]. But a simple left-to-right approach would return [1,3,4,5,6,2]. \$\endgroup\$
    – Arnauld
    Commented Jan 20, 2023 at 13:33
  • 1
    \$\begingroup\$ @Arnauld [1, 3, 4, 5, 6, 2]. Remember that the simplest cycle may not be the shortest for this challenge \$\endgroup\$
    – lyxal
    Commented Jan 20, 2023 at 13:36
  • 1
    \$\begingroup\$ @CommandMaster it would be but it snips in order of how the input came \$\endgroup\$
    – lyxal
    Commented Jan 20, 2023 at 13:37
  • 1
    \$\begingroup\$ @Arnauld I've added that extra clarification. Sorry for the confusion over that aspect of the challenge \$\endgroup\$
    – lyxal
    Commented Jan 20, 2023 at 13:42

14 Answers 14

11
\$\begingroup\$

Wolfram Mathematica, 36 35 bytes

#//.{a___,b_,___,b_,c___}:>{a,b,c}&

-1 byte thanks to @att.

Explanation:

  • # and & define an anonymous function, e.g., #+1& is a function that adds 1 to its argument.

  • //. is ReplaceRepeated, and keeps applying the pattern on the right to the expression on the left until its no longer changing

  • :> is pattern replacement, it replaces the expression on the left with the expression on the right

  • Finally, _ means "any element" and ___ means any sequence of elements (including empty sequences). The variable before _ or ___ assigns the matched expression to the variable.

\$\endgroup\$
3
  • 3
    \$\begingroup\$ Welcome to Code Golf, and nice answer! \$\endgroup\$ Commented Jan 20, 2023 at 19:41
  • 2
    \$\begingroup\$ you don't need to name c \$\endgroup\$
    – att
    Commented Jan 21, 2023 at 1:33
  • \$\begingroup\$ Indeed! It saves a character. That’s shows how new I am to this code gold thing. \$\endgroup\$
    – Victor K.
    Commented Jan 21, 2023 at 1:44
8
\$\begingroup\$

><> (Fish), 43 39 bytes

i:0(?v:l3p:l$4p
  /2~/
1+>3g:?!;:nao:4g

Try it

Explanation

enter image description here

Top row copies every element. The raw data will be stored in the third row of the code box. (:l2-3p) The fourth row stores the last index each character is encountered. (l2-$4p).

The third row prints the data based on the value stored. First, get the number at the specified position. 3g. Check if it's 0, if so exit. ?!;. Print the number followed by a line break nao. Then we jump to the last occurrence of that character plus one 4g1+

\$\endgroup\$
7
\$\begingroup\$

Vyxal, 9 7 bytes

≬h€÷↔∩h

Try it Online!

≬       # three element lambda:
 h      #   head
  €     #   split by
   ÷    #   push each item to stack

This lambda takes a list. If length > 0 it splits by the first element and returns the last chunk. If length == 0 it does nothing.

    ↔   # apply the lambda and collect results until the the result doesn't change
     ∩  # transpose
      h # head
\$\endgroup\$
1
  • \$\begingroup\$ The ; is unnecessary, as functions are full programs. \$\endgroup\$
    – emanresu A
    Commented Jan 20, 2023 at 20:36
4
\$\begingroup\$

Retina 0.8.2, 11 bytes

(\w).*\1
$1

Try it online! Link includes test cases. Takes input as a list of letters (or digits or _). If input as a string of non-newline characters is acceptable, then for 10 bytes:

(.).*\1
$1

Try it online! Link includes test cases.

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

Nibbles, 6 bytes (12 nibbles)

.`.$/%$/$$@/

Approach based on AndrovT's Vyxal answer: upvote that!

Vertices are represented by characters.

 `.             # iterate while unique
   $            # (starting with input):
     %$         #   split the result-so-far
       /$$      #   on its first element
    /     @     #   and get the last part
.               # now map over results of each iteration
           /    # returning the first element each time.

enter image description here

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

JavaScript (Node.js), 35 bytes

f=a=>a&&a[0]+f(a.split(a[0]).pop())

Try it online! Link includes test cases. Takes input as a string of characters.

\$\endgroup\$
3
\$\begingroup\$

05AB1E, 14 bytes

.œR.Δε¬Qθ}P}€н

Try it online or verify all test cases.

Explanation:

.œ         # Get all partitions of the (implicit) input-list
  R.Δ      # Find the last one (first one of the reversed list) that's truthy for:
     ε     #  Map over each part of the current partition:
      ¬    #   Get the head (without popping the list)
       Qθ  #   Check if it's equal to the last item in the list
     }P    #  After the map: check if all parts were truthy by taking the product
    }€     # After the findFirst, map over the parts of the found partition:
      н    #  Only leave their first integer
           # (after which this list is output implicitly as result)
\$\endgroup\$
3
\$\begingroup\$

Python 3.8 (pre-release), 67 bytes

f=lambda x,b=[]:x and f(x[len(x)-x[::-1].index(x[0]):],b+x[:1])or b

Try it online!

Reverse lookup approach. We find the last occurrence and jump to it

Python 3.8 (pre-release), 78 bytes

f=lambda x,b=[]:x and f(x[1:],(b[:b.index(x[0])]if x[0]in b else b)+x[:1])or b

Try it online!

Takes a list of integers.

Idea is if we encounter an element we already passed through, we prune all elements between them

\$\endgroup\$
0
3
\$\begingroup\$

Haskell, 53 bytes

q(_,_:y)=f y
q(y,_)=f y
f(a:b)=a:q(break(==a)b)
f x=x

Try it online!

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

JavaScript (Node.js), 53 52 bytes

a=>a.filter(u=(x,i)=>a.lastIndexOf(u=+u||x)-i?0:u=a)

Try it online!

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

Charcoal, 17 13 bytes

WΦθ¬λ«ι≔⊟⪪θιθ

Try it online! Link is to verbose version of code. Explanation:

WΦθ¬λ«

Repeat until the input string is empty, but calculated as the input string excluding any characters with a non-zero index, so that the result of the calculation becomes the loop variable.

ι

Output the first character of the input string.

≔⊟⪪θιθ

Split the string on its first character and take the last part. Edit: Saved 4 bytes by copying this approach from @DominicvanEssen (who based it on another answer but I found his answer clearer).

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

Curry (PAKCS), 40 bytes

f(a:_++a:b?a:b)|notElem a b=a:f b
f[]=[]

Attempt This Online!

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

Scala, 121 bytes

Golfed version, try it online!

def f(l:List[Int])=l.foldLeft(List.empty[Int]){(a,i)=>if(a.contains(i))a.dropRight(a.length-a.lastIndexOf(i)-1)else a:+i}

Ungolfed version

object Main {
  def main(args: Array[String]): Unit = {
    val testCases = List(
      List(1, 2, 3, 4, 2, 5),
      List(4, 3, 6, 2, 3, 8, 5, 2, 8, 7),
      List(1, 1, 2),
      List(1, 2, 7, 2, 7, 2, 3, 7)
    )

    testCases.foreach { input =>
      val result = f(input)
      println(s"Input: $input, Result: $result")
    }
  }

  def f(input: List[Int]): List[Int] = {
    input.foldLeft(List.empty[Int]) { (acc, item) =>
      if (acc.contains(item)) {
        acc.dropRight(acc.length - acc.lastIndexOf(item) - 1)
      } else {
        acc :+ item
      }
    }
  }
}
\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 53 bytes

Version 1

f=(a,i=0,v=a[i])=>v?[v,...f(a,a.lastIndexOf(v)+1)]:[]

Try it online!

Version 2

f=a=>a+a?[v=a[0],...f(a.slice(a.lastIndexOf(v)+1))]:a

Try it online!

\$\endgroup\$
0

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.