# Simplify a Cycle

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\$$:

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

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

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.

• 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? Commented Jan 20, 2023 at 12:50
• 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]. Commented Jan 20, 2023 at 13:33
• @Arnauld [1, 3, 4, 5, 6, 2]. Remember that the simplest cycle may not be the shortest for this challenge Commented Jan 20, 2023 at 13:36
• @CommandMaster it would be but it snips in order of how the input came Commented Jan 20, 2023 at 13:37
• @Arnauld I've added that extra clarification. Sorry for the confusion over that aspect of the challenge Commented Jan 20, 2023 at 13:42

# 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.

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

# ><> (Fish), 43 39 bytes

i:0(?v:l3p:l$4p /2~/ 1+>3g:?!;:nao:4g  Try it ## Explanation 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+

# Vyxal, 9 7 bytes

≬h€÷↔∩h


Try it Online!

≬       # three element lambda:
€     #   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

• The ; is unnecessary, as functions are full programs. Commented Jan 20, 2023 at 20:36

# 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.

# 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.


# 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.

# 05AB1E, 14 bytes

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


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)


# 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

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


Try it online!

# JavaScript (Node.js), 53 52 bytes

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


Try it online!

# Charcoal, 17 13 bytes

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


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

ＷΦθ¬λ«


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).

# Curry (PAKCS), 40 bytes

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


Attempt This Online!

# 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
}
}
}
}


# 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!