16
\$\begingroup\$

In this challenge you will be asked to take a knot and determine if it can be colored in a particular way.

First we draw a diagram of the knot. We use the standard way of drawing knots where we put gaps in strands where they pass under each other. Here is an example of some knots drawn this way:

Some knots

Taken with permission from wikimedia user Jkasd

Once we have drawn the knot we want to color the knot with three colors such that:

  • Every contiguous length of string in the knot's diagram is colored with the same color (String on the opposite ends gaps where we pass under do not need to be the same color)
  • The three strands that meet at an intersection are either
    • all the same color
    • or all different colors
  • At least two colors must be used in total

Some knots can be drawn in this way for example:

Granny Knot

Taken with permission from wikimedia user n4nojohn

and some cannot for example

Figure 8

Taken with permission from wikimedia user n4nojohn

Your task is to take a knot as input and determine whether or not it can be colored. You may take a knot in any reasonable format (some examples listed below) and you may output two distinct consistent values one indicating that it can be colored one that it cannot.

This is so answers will be scored in bytes with fewer bytes being better.


Example input formats

Some nice ways of taking knots as input:

\$\endgroup\$
5
\$\begingroup\$

Haskell, 249 246 bytes

(i#x)a=[head$[x|j==i]++[s]|(j,s)<-zip[0..]a]
(s%i)[]=i<2&&elem 2(concat s)
(s%i)((l,a):b)|l,[]<-s!!a=or[(a#[i,x]$s)%x$b|x<-[1..3]]|[]<-s!!a=(a#[i]$s)%i$b|[x]<-s!!a,x==i=s%i$b|[x]<-s!!a=s%(6-i-x)$b|u<-s!!a=mod(sum$i:u)3<1&&(s%i)b
f x=(x>>[[]])%1$x

Try it online!

Takes input as a Gauss Code, ([(Bool, Int)]) where False represents crossing over and True represents under

Explanation

This algorithm works by stepping though each intersection and trying to resolve the colors of that intersection. It keeps track of what color the strand is and branches if multiple colors are possible at a given point.

The function that we build to do this is called r. It takes, 3 arguments:

  • The Gauss Code of the knot we are working on (which it will consume in order)
  • A list of "intersections" and what colors we have already filled in
  • The color of the strand where we are currently processing.

Our intersections are represented as a list of colors (Int), which we know to be at that intersection. There are three possible states for this:

  • It is empty, meaning we have not visited this intersection yet.
  • It has one element, meaning we visited the intersection going over.
  • It has two elements (possibly equal), meaning we visited the intersection going under.

We can't have 3 elements because when we visit an intersection the second time we don't have to add the third element since we are never coming back. Since we don't have to and this is code-golf, we don't.

At each step of the way we can use a very simple case analysis to determine how to branch. Here is a diagram showing each case and the possible outputs (no possible outputs is a contradiction and return False if we reach it). Incoming color and location are indicated with the small arrow.

Knot diagram

Here are some sample paths of execution on the granny knot and the figure 8 knot as shown in the question. I skip over steps where we went over a unvisited intersection, since they are quite trivial and the diagrams are quite large even without them.

Granny Execution

Since Haskell is lazy we only ever evaluate two of these paths, the left-most path, and when that fails because the result doesn't have two colors we evaluate the second left-most. Since that one passes we exit without further evaluation.

Figure 8 execution

Here the only branch that does not encounter an error colors everything the same way.

Here is my code ungolfed a bit and commented. I will expand this a little bit shortly.

-- Update an element of a list
q i x a=[head$[x|j==i]++[s]|(j,s)<-zip[0..]a]
-- Perform the algorithm
-- Iterates through the intersections in order
-- It records colors at each intersection and searches for a contradiction
r[]s i=i<2&&elem 2(concat s)
r((l,a):b)s i
  -- If we reach a new intersection passing under
  -- Branch on the three possible colors
  -- label the intersection with the incoming and outgoing colors
  |l,[]<-s!!a=or[r b(q a[i,x]s)x|x<-[1..3]]
  -- If we reach a new intersection passing over
  -- label the intersection with the incoming color
  |[]<-s!!a=r b(q a[i]s)i
  -- If we reach an intersection going under where the over strand is the same color as the incoming
  -- The outgoing strand is the same color
  |[x]<-s!!a,x==i=r b s i
  -- If we reach an intersection going under where the over strand is different from the incoming
  -- The outgoing strand is the third color
  |[x]<-s!!a=r b s(6-i-x)
  -- If we reach an intersection going under
  -- Check that the three strands have either all the same or all different colors
  -- Since we use 1,2 and 3 for the colors this is the same as checking if their sum is divisible by 3
  |u<-s!!a=mod(sum$i:u)3<1&&r b s i
f x=r x(x>>[[]])1
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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