As I’m wrapping up my master’s degree, I have somehow managed to find a large amount of time to pursue personal interests. One of those interests is Julia, a technical computing language with C-comparable speed. I’m not exactly sure where I stumbled on it, but it stuck with me. Of course, the best way to learn something is to do something cool with it, and FiveThiryEight’s Riddler often tends to supply great cannon fodder for programming. This past week’s one was a computationally difficult one:

From Itay Bavly, a chain-link number problem:

You start with the integers from one to 100, inclusive, and you want to organize them into a chain. The only rules for building this chain are that you can only use each number once and that each number must be adjacent in the chain to one of its factors or multiples. For example, you might build the chain:

4, 12, 24, 6, 60, 30, 10, 100, 25, 5, 1, 97

You have no numbers left to place after 97, leaving you with a finished chain of length 12.

What is the longest chain you can build?

There really doesn’t appear to be an easy answer to the problem – my brother noted this:

Friend of mine says that traversing a directed graph is NP-Complete, so brute-force is the way to do it. Probably¹.

I thought it seemed like a perfect time to try out Julia. The past two weeks or so I’ve been idly combing through Julia’s fantastic documentation, and I’ve been really impressed by the syntax² and ease at which you can handle very fast processes.

What I wanted to do was basically try and brute force the problem. Here’s my pseudocode.

1. Pick a random number.
2. Pick a valid number to follow it.
3. Repeat until you can’t find a number.
4. Do steps 1-3 with new chains, discarding the shortest chain.

Mathematically, it’s very simple to define what’s a multiple and what’s a factor, here’s two functions that do that. valid is a function where you pass an x and a y and return true if x can be followed by y.

# Test if x can be followed by y
function valid(x, y, limit)
	# Determine if y is a multiple of x
	mul = multiples(x, limit) # Get multiples of x
	index = findin(mul, y) # Find if y is in the list of x's multiples
	if index != [] # If the index isn't zero
		return true
	end

	# Now determine if y is a factor of x
	if x % y == 0
		return true
	end
	return false
end

Multiples generates a list of multiples and returns it.

function multiples(x, limit)
	vals = [0]
	for i in 1:limit
		#print(i, "\n")
		if (i % x == 0) & (i != x)
			append!(vals, i)
		end
	end
	if vals == [0]
		print("No multiples of ", x, ".", "\n")
	end

	return vals
end

These two functions are called by makechain, which picks the first number³, and then tests if subsequent random numbers are valid. When it runs out of valid numbers, it spits out the answer.

function makechain(limit::Int64)
  possible = Array(1:limit)
  first = rand(possible)
  remove = getindex(possible, first)
  deleteat!(possible,remove)

  chain = [first]

	# Pick a random number.
	# Check if that number is valid.
	# If it isn't pick a new one, until they're all gone.
	testPosition = possible
	shuffle!(testPosition)
	for i in testPosition
		v = valid(chain[end], i, limit)
		if v == true
			append!(chain, i)
		end
	end

  return chain
end

Finally, the final function just runs makechain a bunch of times and finds the longest chain it can.

function find_longest(iterations::Int64, limit=100)
	longest = []
	for i in 1:iterations
		chain = makechain(limit)
		if length(chain) > length(longest)
			longest = chain
		end
	end
	return longest
end

My biggest output was something like 27 integers long after building 10 million chains, which was far below the 77 found by two other contestants. One guy apparently solved it with some nifty combinatorics software.

Even though I didn’t get the right answer, I had a lot of fun working with Julia for the first time and I’m looking forward to finding neat things to do with it. Also, Julia is wicked fast.